From patchwork Sat Nov 15 23:56:45 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 411239 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 2969A1400B6 for ; Sun, 16 Nov 2014 10:57:00 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=p5mhKcO9lJZGdFusKBe82P9cwf16U7y0eeXPrFnVVG21OF1RK2jqC ipDNvn0ApA4HBxF9/7ZbKiPLGOloet9oyNXedT4vVo3txgyAg7PXnjHrOBueKzGu LBinQ+LBgmHfB/0Qip7HoUAO3ce3vgHG0wHYbxuCE3GyzCrybi0oks= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=Ns6wDR7JtP8wcaKg9/P4I+Lm3iA=; b=BNOukMsQ5HSnxwa3arrJ faJnn+nyq4mQNVJ+DjzCdq56/XXzhDOOxTniVt9tnlvJ4Q+pzO+Yc+e/rPjPT2gB q2mO2l6k5ZMxKUQroQXppTHZPS/hxSCGwR62GNLArSD3Tw5SRBDMSJz8/vSL57+4 E9AcVUoste4x3Ca1i1mlXWc= Received: (qmail 6890 invoked by alias); 15 Nov 2014 23:56:52 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 6880 invoked by uid 89); 15 Nov 2014 23:56:51 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.1 required=5.0 tests=AWL, BAYES_00, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: nikam.ms.mff.cuni.cz Received: from nikam.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Sat, 15 Nov 2014 23:56:49 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id C03D654096D; Sun, 16 Nov 2014 00:56:45 +0100 (CET) Date: Sun, 16 Nov 2014 00:56:45 +0100 From: Jan Hubicka To: gcc-patches@gcc.gnu.org, mjambor@suse.de Subject: Fix speculation in ipa-cp Message-ID: <20141115235645.GB13765@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) Hi, this patch enables propagation of speculative contextes I promised to fix after Martin's merge. There were few bugs that ended up disturbing testsuite: 1) ipa_polymorphic_call_context::combine_with did not handle very well case where the incomming type is in construction and it's current type is known. This made us to drop the ball on one of devirt-*.C testcases 2) ipa_get_indirect_edge_target_1 did not correctly apply the offset adjustment and type_preserved prior using the known context. This caused an ICE while building Firefox 3) propagate_context_accross_jump_function cut&paste the logic where for constants we track if the function may be called externally with a unknown parameter (and thus we need to clone). In the case of contextes we do not really need to set this flag if we did not use the incomming information. Also I think it would be better to handle these by speculation rather than clonning, but I hope Martin will followup on this. 4) I noticed that find_more_scalar_values_for_callers_subset seems to contain a bug when searching if all incomming edges do contribute a same constant to a given parameter. The code seems to set the constant to NULL and then set it to non-NULL at first occurence. When it however hits two different constants it resets back to NULL and later it may get again non-NULL. Otherwise the patch just disable parts where speculation si cleared; it makes equal_to to work better and it also add meet operation that is used to compute context of edges that have multiple callers. Bootstrapped/regtested x86_64-linux, tested with Firefox, plan to commit it shortly. Honza * ipa-polymorphic-call.c (ipa_polymorphic_call_context::speculation_consistent_p): Constify. (ipa_polymorphic_call_context::meet_speculation_with): New function. (ipa_polymorphic_call_context::combine_with): Handle types in construction better. (ipa_polymorphic_call_context::equal_to): Do not bother about useless speculation. (ipa_polymorphic_call_context::meet_with): New function. * cgraph.h (class ipa_polymorphic_call_context): Add meet_width, meet_speculation_with; constify speculation_consistent_p. * ipa-cp.c (ipa_context_from_jfunc): Handle speculation; combine with incomming context. (propagate_context_accross_jump_function): Likewise; be more cureful. about set_contains_variable. (ipa_get_indirect_edge_target_1): Fix handling of dynamic type changes. (find_more_scalar_values_for_callers_subset): Fix. (find_more_contexts_for_caller_subset): Perform meet operation. Index: ipa-polymorphic-call.c =================================================================== --- ipa-polymorphic-call.c (revision 217609) +++ ipa-polymorphic-call.c (working copy) @@ -1727,7 +1727,7 @@ bool ipa_polymorphic_call_context::speculation_consistent_p (tree spec_outer_type, HOST_WIDE_INT spec_offset, bool spec_maybe_derived_type, - tree otr_type) + tree otr_type) const { if (!flag_devirtualize_speculatively) return false; @@ -1873,6 +1873,102 @@ ipa_polymorphic_call_context::combine_sp return false; } +/* Make speculation less specific so + NEW_OUTER_TYPE, NEW_OFFSET, NEW_MAYBE_DERIVED_TYPE is also included. + If OTR_TYPE is set, assume the context is used with OTR_TYPE. */ + +bool +ipa_polymorphic_call_context::meet_speculation_with + (tree new_outer_type, HOST_WIDE_INT new_offset, bool new_maybe_derived_type, + tree otr_type) +{ + if (!new_outer_type && speculative_outer_type) + { + clear_speculation (); + return true; + } + + /* restrict_to_inner_class may eliminate wrong speculation making our job + easeier. */ + if (otr_type) + restrict_to_inner_class (otr_type); + + if (!speculative_outer_type + || !speculation_consistent_p (speculative_outer_type, + speculative_offset, + speculative_maybe_derived_type, + otr_type)) + return false; + + if (!speculation_consistent_p (new_outer_type, new_offset, + new_maybe_derived_type, otr_type)) + { + clear_speculation (); + return true; + } + + else if (types_must_be_same_for_odr (speculative_outer_type, + new_outer_type)) + { + if (speculative_offset != new_offset) + { + clear_speculation (); + return true; + } + else + { + if (!speculative_maybe_derived_type && new_maybe_derived_type) + { + speculative_maybe_derived_type = true; + return true; + } + else + return false; + } + } + /* See if one type contains the other as a field (not base). */ + else if (contains_type_p (new_outer_type, new_offset - speculative_offset, + speculative_outer_type, false, false)) + return false; + else if (contains_type_p (speculative_outer_type, + speculative_offset - new_offset, + new_outer_type, false, false)) + { + speculative_outer_type = new_outer_type; + speculative_offset = new_offset; + speculative_maybe_derived_type = new_maybe_derived_type; + return true; + } + /* See if OUTER_TYPE is base of CTX.OUTER_TYPE. */ + else if (contains_type_p (new_outer_type, + new_offset - speculative_offset, + speculative_outer_type, false, true)) + { + if (!speculative_maybe_derived_type) + { + speculative_maybe_derived_type = true; + return true; + } + return false; + } + /* See if CTX.OUTER_TYPE is base of OUTER_TYPE. */ + else if (contains_type_p (speculative_outer_type, + speculative_offset - new_offset, new_outer_type, false, true)) + { + speculative_outer_type = new_outer_type; + speculative_offset = new_offset; + speculative_maybe_derived_type = true; + return true; + } + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Giving up on speculative meet\n"); + clear_speculation (); + return true; + } +} + /* Assume that both THIS and a given context is valid and strenghten THIS if possible. Return true if any strenghtening was made. If actual type the context is being used in is known, OTR_TYPE should be @@ -2065,6 +2161,16 @@ ipa_polymorphic_call_context::combine_wi fprintf (dump_file, "First context does not permit base -> invalid\n"); goto invalidate; } + /* Pick the base type. */ + else if (maybe_in_construction) + { + outer_type = ctx.outer_type; + maybe_in_construction = ctx.maybe_in_construction; + maybe_derived_type = ctx.maybe_derived_type; + offset = ctx.offset; + dynamic = ctx.dynamic; + updated = true; + } } } /* TODO handle merging using hiearchy. */ @@ -2160,19 +2266,220 @@ ipa_polymorphic_call_context::equal_to else if (x.outer_type) return false; - if (speculative_outer_type) + + if (speculative_outer_type + && speculation_consistent_p (speculative_outer_type, speculative_offset, + speculative_maybe_derived_type, NULL_TREE)) { - if (!x.speculative_outer_type - || !types_odr_comparable (speculative_outer_type, - x.speculative_outer_type) + if (!x.speculative_outer_type) + return false; + + if (!types_odr_comparable (speculative_outer_type, + x.speculative_outer_type) || !types_same_for_odr (speculative_outer_type, - x.speculative_outer_type) + x.speculative_outer_type) || speculative_offset != x.speculative_offset || speculative_maybe_derived_type != x.speculative_maybe_derived_type) return false; } - else if (x.speculative_outer_type) + else if (x.speculative_outer_type + && x.speculation_consistent_p (x.speculative_outer_type, + x.speculative_offset, + x.speculative_maybe_derived_type, + NULL)) return false; return true; } + +/* Modify context to be strictly less restrictive than CTX. */ + +bool +ipa_polymorphic_call_context::meet_with (ipa_polymorphic_call_context ctx, + tree otr_type) +{ + bool updated = false; + + if (useless_p () || ctx.invalid) + return false; + + /* Restricting context to inner type makes merging easier, however do not + do that unless we know how the context is used (OTR_TYPE is non-NULL) */ + if (otr_type && !useless_p () && !ctx.useless_p ()) + { + restrict_to_inner_class (otr_type); + ctx.restrict_to_inner_class (otr_type); + if(invalid) + return false; + } + + if (equal_to (ctx)) + return false; + + if (ctx.useless_p () || invalid) + { + *this = ctx; + return true; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Polymorphic call context meet:"); + dump (dump_file); + fprintf (dump_file, "With context: "); + ctx.dump (dump_file); + if (otr_type) + { + fprintf (dump_file, "To be used with type: "); + print_generic_expr (dump_file, otr_type, TDF_SLIM); + fprintf (dump_file, "\n"); + } + } + + if (!dynamic && ctx.dynamic) + { + dynamic = true; + updated = true; + } + + /* If call is known to be invalid, we are done. */ + if (!outer_type) + ; + else if (!ctx.outer_type) + { + clear_outer_type (); + updated = true; + } + /* If types are known to be same, merging is quite easy. */ + else if (types_must_be_same_for_odr (outer_type, ctx.outer_type)) + { + if (offset != ctx.offset + && TYPE_SIZE (outer_type) + && TREE_CODE (TYPE_SIZE (outer_type)) == INTEGER_CST) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Outer types match, offset mismatch -> clearing\n"); + clear_outer_type (); + return true; + } + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Outer types match, merging flags\n"); + if (!maybe_in_construction && ctx.maybe_in_construction) + { + updated = true; + maybe_in_construction = true; + } + if (!maybe_derived_type && ctx.maybe_derived_type) + { + updated = true; + maybe_derived_type = true; + } + if (!dynamic && ctx.dynamic) + { + updated = true; + dynamic = true; + } + } + /* See if one type contains the other as a field (not base). */ + else if (contains_type_p (ctx.outer_type, ctx.offset - offset, + outer_type, false, false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Second type contain the first as a field\n"); + + /* The second type is more specified, so we keep the first. + We need to set DYNAMIC flag to avoid declaring context INVALID + of OFFSET ends up being out of range. */ + if (!dynamic + && (ctx.dynamic + || (!otr_type + && (!TYPE_SIZE (ctx.outer_type) + || !TYPE_SIZE (outer_type) + || !operand_equal_p (TYPE_SIZE (ctx.outer_type), + TYPE_SIZE (outer_type), 0))))) + { + dynamic = true; + updated = true; + } + } + else if (contains_type_p (outer_type, offset - ctx.offset, + ctx.outer_type, false, false)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "First type contain the second as a field\n"); + + if (!dynamic + && (ctx.dynamic + || (!otr_type + && (!TYPE_SIZE (ctx.outer_type) + || !TYPE_SIZE (outer_type) + || !operand_equal_p (TYPE_SIZE (ctx.outer_type), + TYPE_SIZE (outer_type), 0))))) + dynamic = true; + outer_type = ctx.outer_type; + offset = ctx.offset; + dynamic = ctx.dynamic; + maybe_in_construction = ctx.maybe_in_construction; + maybe_derived_type = ctx.maybe_derived_type; + updated = true; + } + /* See if OUTER_TYPE is base of CTX.OUTER_TYPE. */ + else if (contains_type_p (ctx.outer_type, + ctx.offset - offset, outer_type, false, true)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "First type is base of second\n"); + if (!maybe_derived_type) + { + maybe_derived_type = true; + updated = true; + } + if (!maybe_in_construction && ctx.maybe_in_construction) + { + maybe_in_construction = true; + updated = true; + } + if (!dynamic && ctx.dynamic) + { + dynamic = true; + updated = true; + } + } + /* See if CTX.OUTER_TYPE is base of OUTER_TYPE. */ + else if (contains_type_p (outer_type, + offset - ctx.offset, ctx.outer_type, false, true)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Second type is base of first\n"); + outer_type = ctx.outer_type; + offset = ctx.offset; + updated = true; + if (!maybe_derived_type) + maybe_derived_type = true; + if (!maybe_in_construction && ctx.maybe_in_construction) + maybe_in_construction = true; + if (!dynamic && ctx.dynamic) + dynamic = true; + } + /* TODO handle merging using hiearchy. */ + else + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Giving up on meet\n"); + clear_outer_type (); + updated = true; + } + + updated |= meet_speculation_with (ctx.speculative_outer_type, + ctx.speculative_offset, + ctx.speculative_maybe_derived_type, + otr_type); + + if (updated && dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Updated as: "); + dump (dump_file); + fprintf (dump_file, "\n"); + } + return updated; +} Index: cgraph.h =================================================================== --- cgraph.h (revision 217609) +++ cgraph.h (working copy) @@ -1384,6 +1389,7 @@ public: If actual type the context is being used in is known, OTR_TYPE should be set accordingly. This improves quality of combined result. */ bool combine_with (ipa_polymorphic_call_context, tree otr_type = NULL); + bool meet_with (ipa_polymorphic_call_context, tree otr_type = NULL); /* Return TRUE if context is fully useless. */ bool useless_p () const; @@ -1401,9 +1407,10 @@ public: private: bool combine_speculation_with (tree, HOST_WIDE_INT, bool, tree); + bool meet_speculation_with (tree, HOST_WIDE_INT, bool, tree); void set_by_decl (tree, HOST_WIDE_INT); bool set_by_invariant (tree, tree, HOST_WIDE_INT); - bool speculation_consistent_p (tree, HOST_WIDE_INT, bool, tree); + bool speculation_consistent_p (tree, HOST_WIDE_INT, bool, tree) const; void make_speculative (tree otr_type = NULL); }; Index: ipa-cp.c =================================================================== --- ipa-cp.c (revision 217609) +++ ipa-cp.c (working copy) @@ -946,17 +946,17 @@ ipa_context_from_jfunc (ipa_node_params { ipa_polymorphic_call_context srcctx; int srcidx; + bool type_preserved = true; if (jfunc->type == IPA_JF_PASS_THROUGH) { - if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR - || !ipa_get_jf_pass_through_type_preserved (jfunc)) + if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) return ctx; + type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc); srcidx = ipa_get_jf_pass_through_formal_id (jfunc); } else { - if (!ipa_get_jf_ancestor_type_preserved (jfunc)) - return ctx; + type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc); srcidx = ipa_get_jf_ancestor_formal_id (jfunc); } if (info->ipcp_orig_node) @@ -981,7 +981,10 @@ ipa_context_from_jfunc (ipa_node_params return ctx; if (jfunc->type == IPA_JF_ANCESTOR) srcctx.offset_by (ipa_get_jf_ancestor_offset (jfunc)); - ctx.combine_with (srcctx); + if (!type_preserved) + srcctx.possible_dynamic_type_change (cs->in_polymorphic_cdtor); + srcctx.combine_with (ctx); + return srcctx; } return ctx; @@ -1298,15 +1301,13 @@ propagate_context_accross_jump_function return false; bool ret = false; bool added_sth = false; + bool type_preserved = true; ipa_polymorphic_call_context edge_ctx, *edge_ctx_ptr = ipa_get_ith_polymorhic_call_context (args, idx); if (edge_ctx_ptr) - { - edge_ctx = *edge_ctx_ptr; - edge_ctx.clear_speculation (); - } + edge_ctx = *edge_ctx_ptr; if (jfunc->type == IPA_JF_PASS_THROUGH || jfunc->type == IPA_JF_ANCESTOR) @@ -1320,15 +1321,14 @@ propagate_context_accross_jump_function not set instead of punting. */ if (jfunc->type == IPA_JF_PASS_THROUGH) { - if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR - || !ipa_get_jf_pass_through_type_preserved (jfunc)) + if (ipa_get_jf_pass_through_operation (jfunc) != NOP_EXPR) goto prop_fail; + type_preserved = ipa_get_jf_pass_through_type_preserved (jfunc); src_idx = ipa_get_jf_pass_through_formal_id (jfunc); } else { - if (!ipa_get_jf_ancestor_type_preserved (jfunc)) - goto prop_fail; + type_preserved = ipa_get_jf_ancestor_type_preserved (jfunc); src_idx = ipa_get_jf_ancestor_formal_id (jfunc); } @@ -1338,21 +1338,24 @@ propagate_context_accross_jump_function && (src_lat->contains_variable || (src_lat->values_count > 1))) goto prop_fail; - if (src_lat->contains_variable) - ret |= dest_lat->set_contains_variable (); ipcp_value *src_val; for (src_val = src_lat->values; src_val; src_val = src_val->next) { ipa_polymorphic_call_context cur = src_val->value; + + if (!type_preserved) + cur.possible_dynamic_type_change (cs->in_polymorphic_cdtor); if (jfunc->type == IPA_JF_ANCESTOR) cur.offset_by (ipa_get_jf_ancestor_offset (jfunc)); - /* TODO: Perhaps attempt to look up some used OTR type? */ - cur.clear_speculation (); - if (!edge_ctx.useless_p ()) - cur.combine_with (edge_ctx); + /* TODO: In cases we know how the context is going to be used, + we can improve the result by passing proper OTR_TYPE. */ + cur.combine_with (edge_ctx); if (!cur.useless_p ()) { + if (src_lat->contains_variable + && !edge_ctx.equal_to (cur)) + ret |= dest_lat->set_contains_variable (); ret |= dest_lat->add_value (cur, cs, src_val, src_idx); added_sth = true; } @@ -1848,6 +1851,10 @@ ipa_get_indirect_edge_target_1 (struct c if (known_contexts.length () > (unsigned int) param_index) { context = known_contexts[param_index]; + context.offset_by (anc_offset); + if (ie->indirect_info->vptr_changed) + context.possible_dynamic_type_change (ie->in_polymorphic_cdtor, + ie->indirect_info->otr_type); if (t) { ipa_polymorphic_call_context ctx2 = ipa_polymorphic_call_context @@ -3160,6 +3167,7 @@ find_more_scalar_values_for_callers_subs struct cgraph_edge *cs; tree newval = NULL_TREE; int j; + bool first = true; if (ipa_get_scalar_lat (info, i)->bottom || known_csts[i]) continue; @@ -3178,13 +3186,15 @@ find_more_scalar_values_for_callers_subs t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func); if (!t || (newval - && !values_equal_for_ipcp_p (t, newval))) + && !values_equal_for_ipcp_p (t, newval)) + || (!first && !newval)) { newval = NULL_TREE; break; } else newval = t; + first = false; } if (newval) @@ -3226,7 +3236,7 @@ find_more_contexts_for_caller_subset (cg continue; ipa_polymorphic_call_context newval; - bool found = false; + bool first = true; int j; FOR_EACH_VEC_ELT (callers, j, cs) @@ -3238,21 +3248,18 @@ find_more_contexts_for_caller_subset (cg ipa_polymorphic_call_context ctx; ctx = ipa_context_from_jfunc (IPA_NODE_REF (cs->caller), cs, i, jfunc); - ctx.clear_speculation (); - if (ctx.useless_p () - || (found && !values_equal_for_ipcp_p (newval, ctx))) + if (first) { - found = false; - break; - } - else if (!found) - { - found = true; newval = ctx; + first = false; } + else + newval.meet_with (ctx); + if (newval.useless_p ()) + break; } - if (found) + if (!newval.useless_p ()) { if (dump_file && (dump_flags & TDF_DETAILS)) {