| Message ID | 20130925102050.GB17377@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
On 2013.09.25 at 12:20 +0200, Jan Hubicka wrote: > this is updated version of http://gcc.gnu.org/ml/gcc-patches/2013-09/msg00936.html > > Bootstrapped/regtested x86_64-linux. The patch is tested by ipa-devirt9 > testcase. I have extra four, but I would like to first fix the case where the > devirtualization happens in TODO of early_local_passes that is not dumped > anywhere. So I plan to post these incrementally once this code is hooked also > into gimple folding. > > The patch results in 60% more devirtualizations on Firefox and 10% more > speculative devirtualization. I think main component missing now is code > determining dynamic type from a call to constructor. I have some prototype for > this, too, I would like to discuss incrementally. I am not 100% sure how much > harder tracking of dynamic type changes becomes here. Hi Honza, I've tested your patch and it failed during the "profile generate" phase of an LTO/PGO build of Firefox. Reduced: markus@x4 /tmp % cat test.ii class A { public: virtual void m_fn1(); }; class B final : A { ~B(); virtual void m_fn2() { m_fn1(); } }; B::~B() {} markus@x4 /tmp % g++ -c -std=c++11 -O2 -c test.ii test.ii: In member function ‘virtual void B::m_fn2()’: test.ii:7:16: error: stmt (0x7f85504c3130) marked modified after optimization pass: virtual void m_fn2() { m_fn1(); } ^ # .MEM_6 = VDEF <.MEM_2(D)> A::m_fn1 (_5); test.ii:7:16: internal compiler error: verify_ssa failed 0xc62364 verify_ssa(bool) ../../gcc/gcc/tree-ssa.c:1046 0xa305a1 execute_function_todo ../../gcc/gcc/passes.c:1834 0xa30d07 execute_todo ../../gcc/gcc/passes.c:1866 0xa32af9 execute_one_ipa_transform_pass ../../gcc/gcc/passes.c:2049 0xa32af9 execute_all_ipa_transforms() ../../gcc/gcc/passes.c:2079 0x7e3cc0 expand_function ../../gcc/gcc/cgraphunit.c:1743 0x7e5d96 expand_all_functions ../../gcc/gcc/cgraphunit.c:1855 0x7e5d96 compile() ../../gcc/gcc/cgraphunit.c:2192 0x7e6379 finalize_compilation_unit() ../../gcc/gcc/cgraphunit.c:2269 0x5f816e cp_write_global_declarations() ../../gcc/gcc/cp/decl2.c:4360 Please submit a full bug report,
> On 2013.09.25 at 12:20 +0200, Jan Hubicka wrote: > > this is updated version of http://gcc.gnu.org/ml/gcc-patches/2013-09/msg00936.html > > > > Bootstrapped/regtested x86_64-linux. The patch is tested by ipa-devirt9 > > testcase. I have extra four, but I would like to first fix the case where the > > devirtualization happens in TODO of early_local_passes that is not dumped > > anywhere. So I plan to post these incrementally once this code is hooked also > > into gimple folding. > > > > The patch results in 60% more devirtualizations on Firefox and 10% more > > speculative devirtualization. I think main component missing now is code > > determining dynamic type from a call to constructor. I have some prototype for > > this, too, I would like to discuss incrementally. I am not 100% sure how much > > harder tracking of dynamic type changes becomes here. > > Hi Honza, > > I've tested your patch and it failed during the "profile generate" phase of an > LTO/PGO build of Firefox. > > Reduced: > > markus@x4 /tmp % cat test.ii > class A { > public: > virtual void m_fn1(); > }; > class B final : A { > ~B(); > virtual void m_fn2() { m_fn1(); } > }; > B::~B() {} > > markus@x4 /tmp % g++ -c -std=c++11 -O2 -c test.ii > test.ii: In member function ???virtual void B::m_fn2()???: > test.ii:7:16: error: stmt (0x7f85504c3130) marked modified after optimization pass: Thanks, it looks like latent problem in remove_unreachable_nodes that does not update SSA after changing call to a direct call. I will fix it tomorrow. M:q Honza
Hi, sorry it took me so long, but it also took me quite a while to chew through. Please consider posting context diff in cases like this. Nevertheless, most of the patch is a nice improvement. On Wed, Sep 25, 2013 at 12:20:50PM +0200, Jan Hubicka wrote: > Hi, > this is updated version of http://gcc.gnu.org/ml/gcc-patches/2013-09/msg00936.html > > It updates the type inheritance graph walking algorithm to be context sensitive. > Contex is stored in ipa_polymorhic_call_context containing > - OUTER_TYPE > (a type of memory object that contains the object whose method is called, > NULL if unknown) > - OFFSET > offset withing OUTER_TYPE where object is located > - MAYBE_IN_CONSTRUCTION > true if the object may be in construction. I.e. it is local or static > variable. > At the moment we do not try to disprove construciton that is partly > done by ipa-prop and is planned to be merged here in future > - MAYBE_DERIVED_TYPE > if OUTER_TYPE object actually may be a derivation of a type. > For example when OUTER_TYPE was determined from THIS parameter of a method. > > There is cgraph_indirect_call_info that walks GIMPLE code and attempts to > determine the context of a given call. It looks for objects located in > declarations (static vars/ automatic vars/parameters), objects passed by > invisible references and objects passed as THIS pointers. > The second two cases are new, the first case is already done by > gimple_extract_devirt_binfo_from_cst and I assume we should really put the context there, rather than reconstructing it from the edge. Of course we must stop overloading the offset field for that, are there any other obstacles? > Context is determined by cgraph construction code and stored in cgraph edges. > In future I expect ipa-prop to manipulate and update the contextes and propagate > across them, but it is not implemented. For this reason I did not add context > itself into cgrpah edge, merely I added the new info and hacked ipa-prop (temporarily) > to simply throw away the actual info. > > The highlevel idea is to make get_class_context to fill in info for known type > and ancestor functions, too and then we can have function combining types + > doing propagation across them replacing the current code that deals with BINFOs > directly and thus can not deal with all the cases above very well. > > possible_polymorphic_call_targets is now bit more complex. it is split into > - get_class_context > this function walks the OUTER_TYPE (if present) and looks up the type > of class actually containing the method being called. > > Previously similar logic was part of gimple_extract_devirt_binfo_from_cst. > - walk_bases > When type is in construction, all base types are walked and for those containing > OTR_TYPE at proper memory location the corresponding virtual methods are added > to list > - record_binfos now walks the inner binfo from OUTER_TYPE to OTR_TYPE > via get_binfo_at_offset. > > Bootstrapped/regtested x86_64-linux. The patch is tested by ipa-devirt9 > testcase. I have extra four, but I would like to first fix the case where the > devirtualization happens in TODO of early_local_passes that is not dumped > anywhere. So I plan to post these incrementally once this code is hooked also > into gimple folding. > > The patch results in 60% more devirtualizations on Firefox and 10% more > speculative devirtualization. I think main component missing now is code > determining dynamic type from a call to constructor. I have some prototype for > this, too, I would like to discuss incrementally. I am not 100% sure how much > harder tracking of dynamic type changes becomes here. > > Martin, does it seem to make sense? > > Honza > > * cgraph.c (cgraph_create_indirect_edge): Use get_polymorphic_call_info. > * cgraph.h (cgraph_indirect_call_info): Add outer_type, maybe_in_construction > and maybe_derived_type. > * ipa-utils.h (ipa_polymorphic_call_context): New structure. > (ipa_dummy_polymorphic_call_context): New global var. > (possible_polymorphic_call_targets): Add context paramter. > (dump_possible_polymorphic_call_targets): Likewise; update > wrappers. > (possible_polymorphic_call_target_p): Likewise. > (get_polymorphic_call_info): New function. > * ipa-devirt.c (ipa_dummy_polymorphic_call_context): New function. > (add_type_duplicate): Remove forgotten debug output. > (method_class_type): Add sanity check. > (maybe_record_node): Add FINALP parameter. > (record_binfo): Add OUTER_TYPE and OFFSET; walk the inner > by info by get_binfo_at_offset. > (possible_polymorphic_call_targets_1): Add OUTER_TYPE/OFFSET parameters; > pass them to record-binfo. > (polymorphic_call_target_d): Add context and FINAL. > (polymorphic_call_target_hasher::hash): Hash context. > (polymorphic_call_target_hasher::equal): Compare context. > (free_polymorphic_call_targets_hash): > (get_class_context): New function. > (contains_type_p): New function. > (get_polymorphic_call_info): New function. > (walk_bases): New function. > (possible_polymorphic_call_targets): Add context parameter; honnor it. > (dump_possible_polymorphic_call_targets): Dump context. > (possible_polymorphic_call_target_p): Add context. > (update_type_inheritance_graph): Update comment.s > (ipa_set_jf_known_type): Assert that compoentn type is known. > (ipa_note_param_call): Do not tamper with offsets. > (ipa_analyze_indirect_call_uses): When offset is being changed; clear > outer type. > (update_indirect_edges_after_inlining): Likewise. > (ipa_write_indirect_edge_info): Stream new fields. > (ipa_read_indirect_edge_info): Stream in new fields. > > * ipa/devirt9.C: Verify that the optimization happens already before. > whole-program. > ... > Index: ipa-devirt.c > =================================================================== > --- ipa-devirt.c (revision 202838) > +++ ipa-devirt.c (working copy) > @@ -554,34 +558,49 @@ build_type_inheritance_graph (void) > timevar_pop (TV_IPA_INHERITANCE); > } > > -/* If TARGET has associated node, record it in the NODES array. */ > +/* If TARGET has associated node, record it in the NODES array. > + if TARGET can not be inserted (for example because its body was > + already removed and there is no way to refer to it), clear FINALP. */ > > static void > maybe_record_node (vec <cgraph_node *> &nodes, > - tree target, pointer_set_t *inserted) > + tree target, pointer_set_t *inserted, > + bool *finalp) > { > struct cgraph_node *target_node; > enum built_in_function fcode; > > - if (target > + if (!target > /* Those are used to mark impossible scenarios. */ > - && (fcode = DECL_FUNCTION_CODE (target)) > - != BUILT_IN_UNREACHABLE > - && fcode != BUILT_IN_TRAP > - && !pointer_set_insert (inserted, target) > - && (target_node = cgraph_get_node (target)) != NULL > + || (fcode = DECL_FUNCTION_CODE (target)) > + == BUILT_IN_UNREACHABLE > + || fcode == BUILT_IN_TRAP) > + return; > + > + target_node = cgraph_get_node (target); > + > + if (target_node != NULL > && (TREE_PUBLIC (target) > - || target_node->symbol.definition) > - && symtab_real_symbol_p ((symtab_node)target_node)) > + || target_node->symbol.definition)) > { > - pointer_set_insert (cached_polymorphic_call_targets, > - target_node); > - nodes.safe_push (target_node); > + gcc_assert (!target_node->global.inlined_to); > + gcc_assert (symtab_real_symbol_p ((symtab_node)target_node)); > + if (!pointer_set_insert (inserted, target)) > + { > + pointer_set_insert (cached_polymorphic_call_targets, > + target_node); > + nodes.safe_push (target_node); > + } > } > + else if (finalp > + && !type_in_anonymous_namespace_p > + (method_class_type (TREE_TYPE (target)))) > + *finalp = false; > } > > -/* See if BINFO's type match OTR_TYPE. If so, lookup method > - in vtable of TYPE_BINFO and insert method to NODES array. > +/* See if BINFO's type match OUTER_TYPE. If so, lookup > + BINFO of subtype of TYPE at OFFSET and in that BINFO find > + method in vtable and insert method to NODES array. > Otherwise recurse to base BINFOs. > This match what get_binfo_at_offset does, but with offset > being unknown. This function now needs a comprehensive update of the leading comment, we have the offset, so it is known. I also dislike the name a lot because it does not record binfo, but extracts and records the call target from it. Can we call it something like record_target_from_binfo or similar? > @@ -603,6 +622,8 @@ record_binfo (vec <cgraph_node *> &nodes > tree otr_type, > tree type_binfo, > HOST_WIDE_INT otr_token, > + tree outer_type, > + HOST_WIDE_INT offset, > pointer_set_t *inserted, > pointer_set_t *matched_vtables, > bool anonymous) > @@ -613,14 +634,15 @@ record_binfo (vec <cgraph_node *> &nodes > > gcc_checking_assert (BINFO_VTABLE (type_binfo)); > > - if (types_same_for_odr (type, otr_type) > - && !pointer_set_insert (matched_vtables, BINFO_VTABLE (type_binfo))) > + if (types_same_for_odr (type, outer_type)) > { > + tree inner_binfo = get_binfo_at_offset (type_binfo, > + offset, otr_type); OK, get_binfo_at_offset also traverses BINFO_BASEs, I wonder whether we need to iterate over them and recurse when types_same_for_odr return false, with offset, won't get_binfo_at_offset just handle both cases correctly? > /* For types in anonymous namespace first check if the respective vtable > is alive. If not, we know the type can't be called. */ > if (!flag_ltrans && anonymous) > { > - tree vtable = BINFO_VTABLE (type_binfo); > + tree vtable = BINFO_VTABLE (inner_binfo); > struct varpool_node *vnode; > > if (TREE_CODE (vtable) == POINTER_PLUS_EXPR) ... > @@ -753,6 +798,338 @@ devirt_node_removal_hook (struct cgraph_ > free_polymorphic_call_targets_hash (); > } > > +/* CONTEXT->OUTER_TYPE is a type of memory object where object of EXPECTED_TYPE > + is contained at CONTEXT->OFFSET. Walk the memory representation of > + CONTEXT->OUTER_TYPE and find the outermost class type that match > + EXPECTED_TYPE or contain EXPECTED_TYPE as a base. Update CONTEXT > + to represent it. > + > + For example when CONTEXT represents type > + class A > + { > + int a; > + class B b; > + } > + and we look for type at offset sizeof(int), we end up with B and offset 0. > + If the same is produced by multiple inheritance, we end up with A and offset > + sizeof(int). > + > + If we can not find corresponding class, give up by setting > + CONTEXT->OUTER_TYPE to EXPECTED_TYPE and CONTEXT->OFFSET to NULL. */ Return value of this function should be described as well. > + > +static bool > +get_class_context (ipa_polymorphic_call_context *context, > + tree expected_type) > +{ > + tree type = context->outer_type; > + HOST_WIDE_INT offset = context->offset; > + > + /* Find the sub-object the constant actually refers to and mark whether it is > + an artificial one (as opposed to a user-defined one). */ > + while (true) > + { > + HOST_WIDE_INT pos, size; > + tree fld; > + > + /* On a match, just return what we found. */ > + if (TREE_CODE (type) == TREE_CODE (expected_type) > + && types_same_for_odr (type, expected_type)) > + { > + gcc_assert (offset == 0); > + return true; > + } > + > + /* Walk fields and find corresponding on at OFFSET. */ > + if (TREE_CODE (type) == RECORD_TYPE) > + { > + for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld)) > + { > + if (TREE_CODE (fld) != FIELD_DECL) > + continue; > + > + pos = int_bit_position (fld); > + size = tree_low_cst (DECL_SIZE (fld), 1); > + if (pos <= offset && (pos + size) > offset) > + break; > + } > + > + if (!fld) > + goto give_up; > + > + type = TREE_TYPE (fld); > + offset -= pos; > + /* DECL_ARTIFICIAL represents a basetype. */ > + if (!DECL_ARTIFICIAL (fld)) > + { > + context->outer_type = type; > + context->offset = offset; > + /* As soon as we se an field containing the type, > + we know we are not looking for derivations. */ > + context->maybe_derived_type = false; > + } > + } > + else if (TREE_CODE (type) == ARRAY_TYPE) > + { > + tree subtype = TREE_TYPE (type); > + > + /* Give up if we don't know array size. */ > + if (!host_integerp (TYPE_SIZE (subtype), 0) > + || !tree_low_cst (TYPE_SIZE (subtype), 0) <= 0) > + goto give_up; > + offset = offset % tree_low_cst (TYPE_SIZE (subtype), 0); > + type = subtype; > + context->outer_type = type; > + context->offset = offset; > + context->maybe_derived_type = false; Nice. We should a have a testcase exercising this path as well, though. > + } > + /* Give up on anything else. */ > + else > + goto give_up; > + } > + > + /* If we failed to find subtype we look for, give up and fall back to the > + most generic query. */ > +give_up: > + context->outer_type = expected_type; > + context->offset = 0; > + context->maybe_derived_type = true; > + return false; > +} > + > +/* Return true if OUTER_TYPE contains OTR_TYPE at OFFSET. */ > + > +static bool > +contains_type_p (tree outer_type, HOST_WIDE_INT offset, > + tree otr_type) > +{ > + ipa_polymorphic_call_context context = {offset, outer_type, > + false, true}; > + return get_class_context (&context, otr_type); > +} > + > +/* Given REF call in FNDECL, determine class of the polymorphic > + call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT. > + Return pointer to object described by the context */ > + The return value is never used, Is it ever going to be useful? Especially since it can be NULL even in useful cases... > +tree > +get_polymorphic_call_info (tree fndecl, > + tree ref, > + tree *otr_type, > + HOST_WIDE_INT *otr_token, > + ipa_polymorphic_call_context *context) > +{ > + tree base_pointer; > + *otr_type = obj_type_ref_class (ref); > + *otr_token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1); > + > + /* Set up basic info in case we find nothing interesting in the analysis. */ > + context->outer_type = *otr_type; > + context->offset = 0; > + base_pointer = OBJ_TYPE_REF_OBJECT (ref); > + context->maybe_derived_type = true; > + context->maybe_in_construction = false; > + > + /* Walk SSA for outer object. */ > + do > + { > + if (TREE_CODE (base_pointer) == SSA_NAME > + && !SSA_NAME_IS_DEFAULT_DEF (base_pointer) > + && SSA_NAME_DEF_STMT (base_pointer) > + && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer))) > + { > + base_pointer = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (base_pointer)); > + STRIP_NOPS (base_pointer); If we want to put the context on the edges, we need to adjust the offset here. > + } > + else if (TREE_CODE (base_pointer) == ADDR_EXPR) > + { > + HOST_WIDE_INT size, max_size; > + HOST_WIDE_INT offset2; > + tree base = get_ref_base_and_extent (TREE_OPERAND (base_pointer, 0), > + &offset2, &size, &max_size); > + > + /* If this is a varying address, punt. */ > + if ((TREE_CODE (base) == MEM_REF || DECL_P (base)) > + && max_size != -1 > + && max_size == size) > + { > + /* We found dereference of a pointer. Type of the pointer > + and MEM_REF is meaningless, but we can look futher. */ > + if (TREE_CODE (base) == MEM_REF) > + { > + base_pointer = TREE_OPERAND (base, 0); > + context->offset > + += offset2 + mem_ref_offset (base).low * BITS_PER_UNIT; > + context->outer_type = NULL; > + } > + /* We found base object. In this case the outer_type > + is known. */ > + else if (DECL_P (base)) > + { > + context->outer_type = TREE_TYPE (base); > + gcc_assert (!POINTER_TYPE_P (context->outer_type)); > + > + /* Only type inconsistent programs can have otr_type that is > + not part of outer type. */ > + if (!contains_type_p (context->outer_type, > + context->offset, *otr_type)) > + { > + return base_pointer; > + } well, extraneous braces. > + context->offset += offset2; > + base_pointer = NULL; > + /* Make very conservative assumption that all objects > + may be in construction. > + TODO: ipa-prop already contains code to tell better. > + merge it later. */ > + context->maybe_in_construction = true; > + context->maybe_derived_type = false; > + return base_pointer; Perhaps just return NULL? > + } > + else > + break; > + } > + else > + break; > + } > + else if (TREE_CODE (base_pointer) == POINTER_PLUS_EXPR > + && host_integerp (TREE_OPERAND (base_pointer, 1), 1)) > + { > + context->offset += tree_low_cst (TREE_OPERAND (base_pointer, 1), 1) > + * BITS_PER_UNIT; > + base_pointer = TREE_OPERAND (base_pointer, 0); > + } > + else > + break; > + } > + while (true); > + > + /* Try to determine type of the outer object. */ > + if (TREE_CODE (base_pointer) == SSA_NAME > + && SSA_NAME_IS_DEFAULT_DEF (base_pointer) > + && TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL) > + { > + /* See if parameter is THIS pointer of a method. */ > + if (TREE_CODE (TREE_TYPE (fndecl)) == METHOD_TYPE > + && SSA_NAME_VAR (base_pointer) == DECL_ARGUMENTS (fndecl)) > + { > + context->outer_type = TREE_TYPE (TREE_TYPE (base_pointer)); > + gcc_assert (TREE_CODE (context->outer_type) == RECORD_TYPE); > + > + /* Dynamic casting has possibly upcasted the type > + in the hiearchy. In this case outer type is less > + informative than inner type and we should forget > + about it. */ > + if (!contains_type_p (context->outer_type, context->offset, > + *otr_type)) > + { > + context->outer_type = NULL; > + return base_pointer; > + } > + > + /* If the function is constructor or destructor, then > + the type is possibly in consturction, but we know > + it is not derived type. */ > + if (DECL_CXX_CONSTRUCTOR_P (fndecl) > + || DECL_CXX_DESTRUCTOR_P (fndecl)) > + { > + context->maybe_in_construction = true; > + context->maybe_derived_type = false; > + } > + else > + { > + context->maybe_derived_type = true; > + context->maybe_in_construction = false; > + } > + return base_pointer; > + } > + /* Non-PODs passed by value are really passed by invisible > + reference. In this case we also know the type of the > + object. */ > + if (DECL_BY_REFERENCE (SSA_NAME_VAR (base_pointer))) > + { > + context->outer_type = TREE_TYPE (TREE_TYPE (base_pointer)); > + gcc_assert (!POINTER_TYPE_P (context->outer_type)); > + /* Only type inconsistent programs can have otr_type that is > + not part of outer type. */ > + if (!contains_type_p (context->outer_type, context->offset, > + *otr_type)) > + { > + context->outer_type = NULL; > + gcc_unreachable (); > + return base_pointer; > + } > + context->maybe_derived_type = false; > + context->maybe_in_construction = false; > + return base_pointer; > + } > + } > + /* TODO: There are multiple ways to derive a type. For instance > + if BASE_POINTER is passed to an constructor call prior our refernece. > + We do not make this type of flow sensitive analysis yet. */ > + return base_pointer; > +} > + > +/* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET. > + Lookup their respecitve virtual methods for OTR_TOKEN and OTR_TYPE > + and insert them to NODES. > + > + MATCHED_VTABLES and INSERTED is used to avoid duplicated work. */ > + > +static void > +walk_bases (tree otr_type, record_targets_from_bases? > + HOST_WIDE_INT otr_token, > + tree outer_type, > + HOST_WIDE_INT offset, > + vec <cgraph_node *> nodes, > + pointer_set_t *inserted, > + pointer_set_t *matched_vtables, > + bool *finalp) > +{ > + while (true) > + { > + HOST_WIDE_INT pos, size; > + tree base_binfo; > + tree fld; > + > + if (types_same_for_odr (outer_type, otr_type)) > + return; > + > + for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld)) > + { > + if (TREE_CODE (fld) != FIELD_DECL) > + continue; > + > + pos = int_bit_position (fld); > + size = tree_low_cst (DECL_SIZE (fld), 1); > + if (pos <= offset && (pos + size) > offset) > + break; > + } > + /* Within a class type we should always find correcponding fields. */ > + gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE); > + > + /* Nonbasetypes should have been stripped by outer_class_type. */ > + gcc_assert (DECL_ARTIFICIAL (fld)); > + > + outer_type = TREE_TYPE (fld); > + offset -= pos; > + > + base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type), > + offset, otr_type); > + gcc_assert (base_binfo); > + if (!pointer_set_insert (matched_vtables, BINFO_VTABLE (base_binfo))) > + { > + tree target = gimple_get_virt_method_for_binfo (otr_token, base_binfo); > + if (target) > + maybe_record_node (nodes, target, inserted, finalp); > + /* The only way method in anonymous namespace can become unreferable > + is that it has been fully optimized out. */ > + else if (flag_ltrans || !type_in_anonymous_namespace_p (outer_type)) > + *finalp = false; > + pointer_set_insert (matched_vtables, BINFO_VTABLE (base_binfo)); > + } > + } > +} > + > /* When virtual table is removed, we may need to flush the cache. */ > > static void > @@ -766,8 +1143,14 @@ devirt_variable_node_removal_hook (struc > } > > /* Return vector containing possible targets of polymorphic call of type > - OTR_TYPE caling method OTR_TOKEN with OFFSET. If FINALp is non-NULL, > - store true if the list is complette. > + OTR_TYPE caling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET. > + If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containig > + OTR_TYPE and include their virtual method. This is useful for types > + possibly in construction or destruction where the virtual table may > + temporarily change to one of base types. INCLUDE_DERIVER_TYPES make > + us to walk the inheritance graph for all derivations. > + > + If FINALp is non-NULL, store true if the list is complette. I'd prefer if finalp was called completep, this way it sounds like it was dependent on the final keyword, which it isn't. > CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry > in the target cache. If user needs to visit every target list > just once, it can memoize them. > @@ -779,6 +1162,7 @@ devirt_variable_node_removal_hook (struc > vec <cgraph_node *> > possible_polymorphic_call_targets (tree otr_type, > HOST_WIDE_INT otr_token, > + ipa_polymorphic_call_context context, > bool *finalp, > void **cache_token) > { > @@ -786,25 +1170,36 @@ possible_polymorphic_call_targets (tree > pointer_set_t *inserted; > pointer_set_t *matched_vtables; > vec <cgraph_node *> nodes=vNULL; > - odr_type type; > + odr_type type, outer_type; > polymorphic_call_target_d key; > polymorphic_call_target_d **slot; > unsigned int i; > tree binfo, target; > + bool final; > > - if (finalp) > - *finalp = false; > + type = get_odr_type (otr_type, true); > > - type = get_odr_type (otr_type, false); > - /* If we do not have type in our hash it means we never seen any method > - in it. */ > - if (!type) > - return nodes; > + /* Lookup the outer class type we want to walk. */ > + if (context.outer_type) > + get_class_context (&context, otr_type); > > - /* For anonymous namespace types we can attempt to build full type. > - All derivations must be in this unit. */ > - if (type->anonymous_namespace && finalp && !flag_ltrans) > - *finalp = true; > + /* We now canonicalize our query, so we do not need extra hashtable entries. */ > + > + /* Without outer type, we have no use for offset. Just do the > + basic search from innter type */ > + if (!context.outer_type) > + { > + context.outer_type = otr_type; > + context.offset = 0; > + } > + /* We need to update our hiearchy if the type does not exist. */ > + outer_type = get_odr_type (context.outer_type, true); > + /* If outer and inner type match, there are no bases to see. */ > + if (type == outer_type) > + context.maybe_in_construction = false; > + /* If the type is final, there are no derivations. */ > + if (TYPE_FINAL_P (outer_type->type)) > + context.maybe_derived_type = false; > > /* Initialize query cache. */ > if (!cached_polymorphic_call_targets) > @@ -823,43 +1218,75 @@ possible_polymorphic_call_targets (tree > /* Lookup cached answer. */ > key.type = type; > key.otr_token = otr_token; > + key.context = context; > slot = polymorphic_call_target_hash.find_slot (&key, INSERT); > if (cache_token) > *cache_token = (void *)*slot; > if (*slot) > - return (*slot)->targets; > + { > + if (finalp) > + *finalp = (*slot)->final; > + return (*slot)->targets; > + } > + > + final = true; I don't understand this optimistic assumption. As far as I can see, final is cleared only in rather peculiar else if branches. Can you please explain the justification behind it? > > /* Do actual search. */ > timevar_push (TV_IPA_VIRTUAL_CALL); > *slot = XCNEW (polymorphic_call_target_d); > if (cache_token) > - *cache_token = (void *)*slot; > + *cache_token = (void *)*slot; > (*slot)->type = type; > (*slot)->otr_token = otr_token; > + (*slot)->context = context; > > inserted = pointer_set_create (); > matched_vtables = pointer_set_create (); > > /* First see virtual method of type itself. */ > > - binfo = TYPE_BINFO (type->type); > + binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type), > + context.offset, otr_type); > target = gimple_get_virt_method_for_binfo (otr_token, binfo); > if (target) > - maybe_record_node (nodes, target, inserted); > + { > + maybe_record_node (nodes, target, inserted, &final); > + > + /* In the case we get final method, we don't need > + to walk derivations. */ > + if (DECL_FINAL_P (target)) > + context.maybe_derived_type = false; > + } > + /* The only way method in anonymous namespace can become unreferable > + is that it has been fully optimized out. */ > + else if (flag_ltrans || !type->anonymous_namespace) > + final = false; > pointer_set_insert (matched_vtables, BINFO_VTABLE (binfo)); > > - /* TODO: If method is final, we can stop here and signaize that > - list is final. We need C++ FE to pass our info about final > - methods and classes. */ > + /* Next walk bases, if asked to. */ > + if (context.maybe_in_construction) > + walk_bases (otr_type, otr_token, outer_type->type, > + context.offset, nodes, inserted, > + matched_vtables, &final); > > - /* Walk recursively all derived types. Here we need to lookup proper basetype > - via their BINFO walk that is done by record_binfo */ > - for (i = 0; i < type->derived_types.length(); i++) > - possible_polymorphic_call_targets_1 (nodes, inserted, > - matched_vtables, > - otr_type, type->derived_types[i], > - otr_token); > + /* Finally walk recursively all derived types. */ > + if (context.maybe_derived_type) > + { > + /* For anonymous namespace types we can attempt to build full type. > + All derivations must be in this unit (unless we see partial unit). */ > + if (!type->anonymous_namespace || flag_ltrans) > + final = false; Doh, I have obviously missed this one, OK, never mind. > + for (i = 0; i < outer_type->derived_types.length(); i++) > + possible_polymorphic_call_targets_1 (nodes, inserted, > + matched_vtables, > + otr_type, outer_type->derived_types[i], > + otr_token, outer_type->type, > + context.offset); > + } > (*slot)->targets = nodes; > + (*slot)->final = final; > + if (finalp) > + *finalp = final; > > pointer_set_destroy (inserted); > pointer_set_destroy (matched_vtables); > @@ -871,8 +1298,9 @@ possible_polymorphic_call_targets (tree > > void > dump_possible_polymorphic_call_targets (FILE *f, > - tree otr_type, > - HOST_WIDE_INT otr_token) > + tree otr_type, > + HOST_WIDE_INT otr_token, > + const ipa_polymorphic_call_context &ctx) > { > vec <cgraph_node *> targets; > bool final; > @@ -882,16 +1310,25 @@ dump_possible_polymorphic_call_targets ( > if (!type) > return; > targets = possible_polymorphic_call_targets (otr_type, otr_token, > + ctx, > &final); > - fprintf (f, "Targets of polymorphic call of type %i ", type->id); > + fprintf (f, " Targets of polymorphic call of type %i:", type->id); > print_generic_expr (f, type->type, TDF_SLIM); > - fprintf (f, " token %i%s:", > - (int)otr_token, > - final ? " (full list)" : " (partial list, may call to other unit)"); > + fprintf (f, " token %i\n" > + " Contained in type:", > + (int)otr_token); > + print_generic_expr (f, ctx.outer_type, TDF_SLIM); > + fprintf (f, " at offset "HOST_WIDE_INT_PRINT_DEC"\n" > + " %s%s%s\n ", > + ctx.offset, > + final ? "This is full list." : > + "This is partial list; extra targets may be defined in other units.", > + ctx.maybe_in_construction ? " (base types included)" : "", > + ctx.maybe_derived_type ? " (derived types included)" : ""); > for (i = 0; i < targets.length (); i++) > fprintf (f, " %s/%i", cgraph_node_name (targets[i]), > targets[i]->symbol.order); > - fprintf (f, "\n"); > + fprintf (f, "\n\n"); > } > > > Index: ipa-prop.c > =================================================================== > --- ipa-prop.c (revision 202838) > +++ ipa-prop.c (working copy) > @@ -378,6 +378,7 @@ ipa_set_jf_known_type (struct ipa_jump_f > jfunc->value.known_type.offset = offset, > jfunc->value.known_type.base_type = base_type; > jfunc->value.known_type.component_type = component_type; > + gcc_assert (component_type); > } > > /* Set JFUNC to be a copy of another jmp (to be used by jump function > @@ -1727,8 +1728,6 @@ ipa_note_param_call (struct cgraph_node > > cs = cgraph_edge (node, stmt); > cs->indirect_info->param_index = param_index; > - cs->indirect_info->offset = 0; > - cs->indirect_info->polymorphic = 0; > cs->indirect_info->agg_contents = 0; > cs->indirect_info->member_ptr = 0; > return cs; > @@ -1825,6 +1824,8 @@ ipa_analyze_indirect_call_uses (struct c > &by_ref)) > { > struct cgraph_edge *cs = ipa_note_param_call (node, index, call); > + if (cs->indirect_info->offset != offset) > + cs->indirect_info->outer_type = NULL; > cs->indirect_info->offset = offset; > cs->indirect_info->agg_contents = 1; > cs->indirect_info->by_ref = by_ref; > @@ -1922,6 +1923,8 @@ ipa_analyze_indirect_call_uses (struct c > && parm_preserved_before_stmt_p (&parms_ainfo[index], call, rec)) > { > struct cgraph_edge *cs = ipa_note_param_call (node, index, call); > + if (cs->indirect_info->offset != offset) > + cs->indirect_info->outer_type = NULL; > cs->indirect_info->offset = offset; > cs->indirect_info->agg_contents = 1; > cs->indirect_info->member_ptr = 1; > @@ -2758,6 +2761,8 @@ update_indirect_edges_after_inlining (st > else > { > ici->param_index = ipa_get_jf_ancestor_formal_id (jfunc); > + if (ipa_get_jf_ancestor_offset (jfunc)) > + ici->outer_type = NULL; What problems does this cause? > ici->offset += ipa_get_jf_ancestor_offset (jfunc); > } > } > @@ -4072,12 +4077,15 @@ ipa_write_indirect_edge_info (struct out > bp_pack_value (&bp, ii->agg_contents, 1); > bp_pack_value (&bp, ii->member_ptr, 1); > bp_pack_value (&bp, ii->by_ref, 1); > + bp_pack_value (&bp, ii->maybe_in_construction, 1); > + bp_pack_value (&bp, ii->maybe_derived_type, 1); > streamer_write_bitpack (&bp); > > if (ii->polymorphic) > { > streamer_write_hwi (ob, ii->otr_token); > stream_write_tree (ob, ii->otr_type, true); > + stream_write_tree (ob, ii->outer_type, true); > } > } > > @@ -4099,10 +4107,13 @@ ipa_read_indirect_edge_info (struct lto_ > ii->agg_contents = bp_unpack_value (&bp, 1); > ii->member_ptr = bp_unpack_value (&bp, 1); > ii->by_ref = bp_unpack_value (&bp, 1); > + ii->maybe_in_construction = bp_unpack_value (&bp, 1); > + ii->maybe_derived_type = bp_unpack_value (&bp, 1); > if (ii->polymorphic) > { > ii->otr_token = (HOST_WIDE_INT) streamer_read_hwi (ib); > ii->otr_type = stream_read_tree (ib, data_in); > + ii->outer_type = stream_read_tree (ib, data_in); > } > } > Nice work. Thanks, Martin
> Hi, > > sorry it took me so long, but it also took me quite a while to chew > through. Please consider posting context diff in cases like this. > Nevertheless, most of the patch is a nice improvement. Uhm, sorry. Seems I diffed from a different users. > > There is cgraph_indirect_call_info that walks GIMPLE code and attempts to > > determine the context of a given call. It looks for objects located in > > declarations (static vars/ automatic vars/parameters), objects passed by > > invisible references and objects passed as THIS pointers. > > The second two cases are new, the first case is already done by > > gimple_extract_devirt_binfo_from_cst > > and I assume we should really put the context there, rather than > reconstructing it from the edge. Of course we must stop overloading > the offset field for that, are there any other obstacles? No, i think overloading of offset is the only obstackle. I just tried to keep the patch self-contained and do not dive into ipa-prop changes - it is long by itself. > > -/* See if BINFO's type match OTR_TYPE. If so, lookup method > > - in vtable of TYPE_BINFO and insert method to NODES array. > > +/* See if BINFO's type match OUTER_TYPE. If so, lookup > > + BINFO of subtype of TYPE at OFFSET and in that BINFO find > > + method in vtable and insert method to NODES array. > > Otherwise recurse to base BINFOs. > > This match what get_binfo_at_offset does, but with offset > > being unknown. > > This function now needs a comprehensive update of the leading comment, > we have the offset, so it is known. I also dislike the name a lot > because it does not record binfo, but extracts and records the call > target from it. Can we call it something like > record_target_from_binfo or similar? OK, record_target_from_binfo works for me. We still do not know full offset (from start of the type being walked) just partial offset within one of bases of the type. But I will try to formulate the comment better - it is indeed result of incremental updates. > > - if (types_same_for_odr (type, otr_type) > > - && !pointer_set_insert (matched_vtables, BINFO_VTABLE (type_binfo))) > > + if (types_same_for_odr (type, outer_type)) > > { > > + tree inner_binfo = get_binfo_at_offset (type_binfo, > > + offset, otr_type); > > OK, get_binfo_at_offset also traverses BINFO_BASEs, I wonder whether > we need to iterate over them and recurse when types_same_for_odr > return false, with offset, won't get_binfo_at_offset just handle both > cases correctly? No, it is the difference I described above. get_binfo_at_offset assume that the offset is from start of the BINFO's type it is given. This is not true here. We have derived_type that has outer_type as a base that has otr_type at offset inside. We do not know the offset in between derived_type and outer_type. This is why one function wraps the other. > > +/* Given REF call in FNDECL, determine class of the polymorphic > > + call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT. > > + Return pointer to object described by the context */ > > + > > The return value is never used, Is it ever going to be useful? > Especially since it can be NULL even in useful cases... Yes, it is supposed to be used by ipa-prop. We return non-NULL when the base may be PARM_DECL that can be furhter propagated through. > > > > +tree > > +get_polymorphic_call_info (tree fndecl, > > + tree ref, > > + tree *otr_type, > > + HOST_WIDE_INT *otr_token, > > + ipa_polymorphic_call_context *context) > > +{ > > + tree base_pointer; > > + *otr_type = obj_type_ref_class (ref); > > + *otr_token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1); > > + > > + /* Set up basic info in case we find nothing interesting in the analysis. */ > > + context->outer_type = *otr_type; > > + context->offset = 0; > > + base_pointer = OBJ_TYPE_REF_OBJECT (ref); > > + context->maybe_derived_type = true; > > + context->maybe_in_construction = false; > > + > > + /* Walk SSA for outer object. */ > > + do > > + { > > + if (TREE_CODE (base_pointer) == SSA_NAME > > + && !SSA_NAME_IS_DEFAULT_DEF (base_pointer) > > + && SSA_NAME_DEF_STMT (base_pointer) > > + && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer))) > > + { > > + base_pointer = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (base_pointer)); > > + STRIP_NOPS (base_pointer); > > If we want to put the context on the edges, we need to adjust the > offset here. I do not follow here, strip nops should not alter offsets, right? > > + context->offset += offset2; > > + base_pointer = NULL; > > + /* Make very conservative assumption that all objects > > + may be in construction. > > + TODO: ipa-prop already contains code to tell better. > > + merge it later. */ > > + context->maybe_in_construction = true; > > + context->maybe_derived_type = false; > > + return base_pointer; > > Perhaps just return NULL? This is intended to be hooked into your code, but indeed the base_pointer = NULL above is leftover from earlier implementation. > > + If FINALp is non-NULL, store true if the list is complette. > > I'd prefer if finalp was called completep, this way it sounds like it > was dependent on the final keyword, which it isn't. Well, it originally did, but it is no longer the case, I will rename it. Thanks! I will address the comments and update patch. Honza
Index: tree-pretty-print.c =================================================================== --- tree-pretty-print.c (revision 202838) +++ tree-pretty-print.c (working copy) @@ -2040,6 +2040,12 @@ dump_generic_node (pretty_printer *buffe pp_string (buffer, "OBJ_TYPE_REF("); dump_generic_node (buffer, OBJ_TYPE_REF_EXPR (node), spc, flags, false); pp_semicolon (buffer); + if (virtual_method_call_p (node)) + { + pp_string (buffer, "("); + dump_generic_node (buffer, obj_type_ref_class (node), spc, flags, false); + pp_string (buffer, ")"); + } dump_generic_node (buffer, OBJ_TYPE_REF_OBJECT (node), spc, flags, false); pp_arrow (buffer); dump_generic_node (buffer, OBJ_TYPE_REF_TOKEN (node), spc, flags, false); Index: cgraph.c =================================================================== --- cgraph.c (revision 202888) +++ cgraph.c (working copy) @@ -940,16 +940,26 @@ cgraph_create_indirect_edge (struct cgra && (target = gimple_call_fn (call_stmt)) && virtual_method_call_p (target)) { - tree type = obj_type_ref_class (target); + tree otr_type; + HOST_WIDE_INT otr_token; + ipa_polymorphic_call_context context; + get_polymorphic_call_info (caller->symbol.decl, + target, + &otr_type, &otr_token, + &context); /* Only record types can have virtual calls. */ - gcc_assert (TREE_CODE (type) == RECORD_TYPE); + gcc_assert (TREE_CODE (otr_type) == RECORD_TYPE); + edge->indirect_info->polymorphic = true; edge->indirect_info->param_index = -1; - edge->indirect_info->otr_token - = tree_low_cst (OBJ_TYPE_REF_TOKEN (target), 1); - edge->indirect_info->otr_type = type; - edge->indirect_info->polymorphic = 1; + edge->indirect_info->otr_token = otr_token; + edge->indirect_info->otr_type = otr_type; + edge->indirect_info->outer_type = context.outer_type; + edge->indirect_info->offset = context.offset; + edge->indirect_info->maybe_in_construction + = context.maybe_in_construction; + edge->indirect_info->maybe_derived_type = context.maybe_derived_type; } edge->next_callee = caller->indirect_calls; Index: cgraph.h =================================================================== --- cgraph.h (revision 202838) +++ cgraph.h (working copy) @@ -430,7 +430,7 @@ struct GTY(()) cgraph_indirect_call_info /* OBJ_TYPE_REF_TOKEN of a polymorphic call (if polymorphic is set). */ HOST_WIDE_INT otr_token; /* Type of the object from OBJ_TYPE_REF_OBJECT. */ - tree otr_type; + tree otr_type, outer_type; /* Index of the parameter that is called. */ int param_index; /* ECF flags determined from the caller. */ @@ -451,6 +451,8 @@ struct GTY(()) cgraph_indirect_call_info /* When the previous bit is set, this one determines whether the destination is loaded from a parameter passed by reference. */ unsigned by_ref : 1; + unsigned int maybe_in_construction : 1; + unsigned int maybe_derived_type : 1; }; struct GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) cgraph_edge { Index: testsuite/g++.dg/ipa/devirt-9.C =================================================================== --- testsuite/g++.dg/ipa/devirt-9.C (revision 202838) +++ testsuite/g++.dg/ipa/devirt-9.C (working copy) @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-ipa-inline" } */ +/* { dg-options "-O2 -fdump-ipa-whole-program" } */ double foo (); struct B { @@ -27,5 +27,7 @@ bar () static C c; c.c1 (60, (int) foo ()); } -/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target" "inline" } } */ -/* { dg-final { cleanup-ipa-dump "inline" } } */ +/* We optimize out this call just after early passes. Unfortunately + this unreachable removal is not logged in dump file. */ +/* { dg-final { scan-ipa-dump 1 "OBJ_TYPE_REF" "whole-program" } } */ +/* { dg-final { cleanup-ipa-dump "whole-program" } } */ Index: ipa-utils.h =================================================================== --- ipa-utils.h (revision 202838) +++ ipa-utils.h (working copy) @@ -35,6 +35,21 @@ struct ipa_dfs_info { PTR aux; }; +/* Context of polymorphic call. This is used by ipa-devirt walkers of the + type inheritance graph. */ +struct ipa_polymorphic_call_context { + /* The called object appears in an object of type OUTER_TYPE + at offset OFFSET. */ + HOST_WIDE_INT offset; + tree outer_type; + /* True if outer object may be in construction or destruction. */ + bool maybe_in_construction; + /* True if outer object may be of derived type. */ + bool maybe_derived_type; +}; + +/* Context representing "I know nothing". */ +extern const ipa_polymorphic_call_context ipa_dummy_polymorphic_call_context; /* In ipa-utils.c */ void ipa_print_order (FILE*, const char *, struct cgraph_node**, int); @@ -59,13 +74,19 @@ void build_type_inheritance_graph (void) void update_type_inheritance_graph (void); vec <cgraph_node *> possible_polymorphic_call_targets (tree, HOST_WIDE_INT, + ipa_polymorphic_call_context, bool *final = NULL, void **cache_token = NULL); odr_type get_odr_type (tree, bool insert = false); -void dump_possible_polymorphic_call_targets (FILE *, tree, HOST_WIDE_INT); +void dump_possible_polymorphic_call_targets (FILE *, tree, HOST_WIDE_INT, + const ipa_polymorphic_call_context &); bool possible_polymorphic_call_target_p (tree, HOST_WIDE_INT, + const ipa_polymorphic_call_context &, struct cgraph_node *n); tree method_class_type (tree); +tree get_polymorphic_call_info (tree, tree, tree *, + HOST_WIDE_INT *, + ipa_polymorphic_call_context *); /* Return vector containing possible targets of polymorphic call E. If FINALP is non-NULL, store true if the list is complette. @@ -83,8 +104,27 @@ possible_polymorphic_call_targets (struc void **cache_token = NULL) { gcc_checking_assert (e->indirect_info->polymorphic); + ipa_polymorphic_call_context context = {e->indirect_info->offset, + e->indirect_info->outer_type, + e->indirect_info->maybe_in_construction, + e->indirect_info->maybe_derived_type}; return possible_polymorphic_call_targets (e->indirect_info->otr_type, e->indirect_info->otr_token, + context, + final, cache_token); +} + +/* Same as above but taking OBJ_TYPE_REF as an parameter. */ + +inline vec <cgraph_node *> +possible_polymorphic_call_targets (tree call, + bool *final = NULL, + void **cache_token = NULL) +{ + return possible_polymorphic_call_targets (obj_type_ref_class (call), + tree_low_cst + (OBJ_TYPE_REF_TOKEN (call), 1), + ipa_dummy_polymorphic_call_context, final, cache_token); } @@ -94,8 +134,13 @@ inline void dump_possible_polymorphic_call_targets (FILE *f, struct cgraph_edge *e) { gcc_checking_assert (e->indirect_info->polymorphic); + ipa_polymorphic_call_context context = {e->indirect_info->offset, + e->indirect_info->outer_type, + e->indirect_info->maybe_in_construction, + e->indirect_info->maybe_derived_type}; dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type, - e->indirect_info->otr_token); + e->indirect_info->otr_token, + context); } /* Return true if N can be possibly target of a polymorphic call of @@ -105,8 +150,13 @@ inline bool possible_polymorphic_call_target_p (struct cgraph_edge *e, struct cgraph_node *n) { + ipa_polymorphic_call_context context = {e->indirect_info->offset, + e->indirect_info->outer_type, + e->indirect_info->maybe_in_construction, + e->indirect_info->maybe_derived_type}; return possible_polymorphic_call_target_p (e->indirect_info->otr_type, - e->indirect_info->otr_token, n); + e->indirect_info->otr_token, + context, n); } /* Return true if N can be possibly target of a polymorphic call of @@ -118,7 +168,8 @@ possible_polymorphic_call_target_p (tree { return possible_polymorphic_call_target_p (obj_type_ref_class (call), tree_low_cst - (OBJ_TYPE_REF_TOKEN (call), 1), + (OBJ_TYPE_REF_TOKEN (call), 1), + ipa_dummy_polymorphic_call_context, n); } #endif /* GCC_IPA_UTILS_H */ Index: ipa-devirt.c =================================================================== --- ipa-devirt.c (revision 202838) +++ ipa-devirt.c (working copy) @@ -121,6 +121,11 @@ along with GCC; see the file COPYING3. #include "ipa-inline.h" #include "diagnostic.h" +/* Dummy polymorphic call context. */ + +const ipa_polymorphic_call_context ipa_dummy_polymorphic_call_context + = {0, NULL, false, true}; + /* Pointer set of all call targets appearing in the cache. */ static pointer_set_t *cached_polymorphic_call_targets; @@ -291,8 +296,6 @@ add_type_duplicate (odr_type val, tree t inform (DECL_SOURCE_LOCATION (TYPE_NAME (val->type)), "a type with the same name but different layout is " "defined in another translation unit"); - debug_tree (BINFO_VTABLE (TYPE_BINFO (type))); - debug_tree (BINFO_VTABLE (TYPE_BINFO (val->type))); if (cgraph_dump_file) { fprintf (cgraph_dump_file, "ODR violation or merging or ODR type bug?\n"); @@ -521,6 +524,7 @@ tree method_class_type (tree t) { tree first_parm_type = TREE_VALUE (TYPE_ARG_TYPES (t)); + gcc_assert (TREE_CODE (t) == METHOD_TYPE); return TREE_TYPE (first_parm_type); } @@ -554,34 +558,49 @@ build_type_inheritance_graph (void) timevar_pop (TV_IPA_INHERITANCE); } -/* If TARGET has associated node, record it in the NODES array. */ +/* If TARGET has associated node, record it in the NODES array. + if TARGET can not be inserted (for example because its body was + already removed and there is no way to refer to it), clear FINALP. */ static void maybe_record_node (vec <cgraph_node *> &nodes, - tree target, pointer_set_t *inserted) + tree target, pointer_set_t *inserted, + bool *finalp) { struct cgraph_node *target_node; enum built_in_function fcode; - if (target + if (!target /* Those are used to mark impossible scenarios. */ - && (fcode = DECL_FUNCTION_CODE (target)) - != BUILT_IN_UNREACHABLE - && fcode != BUILT_IN_TRAP - && !pointer_set_insert (inserted, target) - && (target_node = cgraph_get_node (target)) != NULL + || (fcode = DECL_FUNCTION_CODE (target)) + == BUILT_IN_UNREACHABLE + || fcode == BUILT_IN_TRAP) + return; + + target_node = cgraph_get_node (target); + + if (target_node != NULL && (TREE_PUBLIC (target) - || target_node->symbol.definition) - && symtab_real_symbol_p ((symtab_node)target_node)) + || target_node->symbol.definition)) { - pointer_set_insert (cached_polymorphic_call_targets, - target_node); - nodes.safe_push (target_node); + gcc_assert (!target_node->global.inlined_to); + gcc_assert (symtab_real_symbol_p ((symtab_node)target_node)); + if (!pointer_set_insert (inserted, target)) + { + pointer_set_insert (cached_polymorphic_call_targets, + target_node); + nodes.safe_push (target_node); + } } + else if (finalp + && !type_in_anonymous_namespace_p + (method_class_type (TREE_TYPE (target)))) + *finalp = false; } -/* See if BINFO's type match OTR_TYPE. If so, lookup method - in vtable of TYPE_BINFO and insert method to NODES array. +/* See if BINFO's type match OUTER_TYPE. If so, lookup + BINFO of subtype of TYPE at OFFSET and in that BINFO find + method in vtable and insert method to NODES array. Otherwise recurse to base BINFOs. This match what get_binfo_at_offset does, but with offset being unknown. @@ -603,6 +622,8 @@ record_binfo (vec <cgraph_node *> &nodes tree otr_type, tree type_binfo, HOST_WIDE_INT otr_token, + tree outer_type, + HOST_WIDE_INT offset, pointer_set_t *inserted, pointer_set_t *matched_vtables, bool anonymous) @@ -613,14 +634,15 @@ record_binfo (vec <cgraph_node *> &nodes gcc_checking_assert (BINFO_VTABLE (type_binfo)); - if (types_same_for_odr (type, otr_type) - && !pointer_set_insert (matched_vtables, BINFO_VTABLE (type_binfo))) + if (types_same_for_odr (type, outer_type)) { + tree inner_binfo = get_binfo_at_offset (type_binfo, + offset, otr_type); /* For types in anonymous namespace first check if the respective vtable is alive. If not, we know the type can't be called. */ if (!flag_ltrans && anonymous) { - tree vtable = BINFO_VTABLE (type_binfo); + tree vtable = BINFO_VTABLE (inner_binfo); struct varpool_node *vnode; if (TREE_CODE (vtable) == POINTER_PLUS_EXPR) @@ -629,9 +651,13 @@ record_binfo (vec <cgraph_node *> &nodes if (!vnode || !vnode->symbol.definition) return; } - tree target = gimple_get_virt_method_for_binfo (otr_token, type_binfo); - if (target) - maybe_record_node (nodes, target, inserted); + gcc_assert (inner_binfo); + if (!pointer_set_insert (matched_vtables, BINFO_VTABLE (inner_binfo))) + { + tree target = gimple_get_virt_method_for_binfo (otr_token, inner_binfo); + if (target) + maybe_record_node (nodes, target, inserted, NULL); + } return; } @@ -643,7 +669,7 @@ record_binfo (vec <cgraph_node *> &nodes /* In the case of single inheritance, the virtual table is shared with the outer type. */ BINFO_VTABLE (base_binfo) ? base_binfo : type_binfo, - otr_token, inserted, + otr_token, outer_type, offset, inserted, matched_vtables, anonymous); } @@ -658,19 +684,22 @@ possible_polymorphic_call_targets_1 (vec pointer_set_t *matched_vtables, tree otr_type, odr_type type, - HOST_WIDE_INT otr_token) + HOST_WIDE_INT otr_token, + tree outer_type, + HOST_WIDE_INT offset) { tree binfo = TYPE_BINFO (type->type); unsigned int i; - record_binfo (nodes, binfo, otr_type, binfo, otr_token, inserted, - matched_vtables, type->anonymous_namespace); + record_binfo (nodes, binfo, otr_type, binfo, otr_token, + outer_type, offset, + inserted, matched_vtables, type->anonymous_namespace); for (i = 0; i < type->derived_types.length(); i++) possible_polymorphic_call_targets_1 (nodes, inserted, matched_vtables, otr_type, type->derived_types[i], - otr_token); + otr_token, outer_type, offset); } /* Cache of queries for polymorphic call targets. @@ -681,9 +710,11 @@ possible_polymorphic_call_targets_1 (vec struct polymorphic_call_target_d { - odr_type type; HOST_WIDE_INT otr_token; + ipa_polymorphic_call_context context; + odr_type type; vec <cgraph_node *> targets; + bool final; }; /* Polymorphic call target cache helpers. */ @@ -702,8 +733,17 @@ struct polymorphic_call_target_hasher inline hashval_t polymorphic_call_target_hasher::hash (const value_type *odr_query) { - return iterative_hash_hashval_t (odr_query->type->id, - odr_query->otr_token); + hashval_t hash; + + hash = iterative_hash_host_wide_int + (odr_query->otr_token, + odr_query->type->id); + hash = iterative_hash_hashval_t (TYPE_UID (odr_query->context.outer_type), + hash); + hash = iterative_hash_host_wide_int (odr_query->context.offset, hash); + return iterative_hash_hashval_t + (((int)odr_query->context.maybe_in_construction << 1) + | (int)odr_query->context.maybe_derived_type, hash); } /* Compare cache entries T1 and T2. */ @@ -712,7 +752,12 @@ inline bool polymorphic_call_target_hasher::equal (const value_type *t1, const compare_type *t2) { - return t1->type == t2->type && t1->otr_token == t2->otr_token; + return (t1->type == t2->type && t1->otr_token == t2->otr_token + && t1->context.offset == t2->context.offset + && t1->context.outer_type == t2->context.outer_type + && t1->context.maybe_in_construction + == t2->context.maybe_in_construction + && t1->context.maybe_derived_type == t2->context.maybe_derived_type); } /* Remove entry in polymorphic call target cache hash. */ @@ -753,6 +798,338 @@ devirt_node_removal_hook (struct cgraph_ free_polymorphic_call_targets_hash (); } +/* CONTEXT->OUTER_TYPE is a type of memory object where object of EXPECTED_TYPE + is contained at CONTEXT->OFFSET. Walk the memory representation of + CONTEXT->OUTER_TYPE and find the outermost class type that match + EXPECTED_TYPE or contain EXPECTED_TYPE as a base. Update CONTEXT + to represent it. + + For example when CONTEXT represents type + class A + { + int a; + class B b; + } + and we look for type at offset sizeof(int), we end up with B and offset 0. + If the same is produced by multiple inheritance, we end up with A and offset + sizeof(int). + + If we can not find corresponding class, give up by setting + CONTEXT->OUTER_TYPE to EXPECTED_TYPE and CONTEXT->OFFSET to NULL. */ + +static bool +get_class_context (ipa_polymorphic_call_context *context, + tree expected_type) +{ + tree type = context->outer_type; + HOST_WIDE_INT offset = context->offset; + + /* Find the sub-object the constant actually refers to and mark whether it is + an artificial one (as opposed to a user-defined one). */ + while (true) + { + HOST_WIDE_INT pos, size; + tree fld; + + /* On a match, just return what we found. */ + if (TREE_CODE (type) == TREE_CODE (expected_type) + && types_same_for_odr (type, expected_type)) + { + gcc_assert (offset == 0); + return true; + } + + /* Walk fields and find corresponding on at OFFSET. */ + if (TREE_CODE (type) == RECORD_TYPE) + { + for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld)) + { + if (TREE_CODE (fld) != FIELD_DECL) + continue; + + pos = int_bit_position (fld); + size = tree_low_cst (DECL_SIZE (fld), 1); + if (pos <= offset && (pos + size) > offset) + break; + } + + if (!fld) + goto give_up; + + type = TREE_TYPE (fld); + offset -= pos; + /* DECL_ARTIFICIAL represents a basetype. */ + if (!DECL_ARTIFICIAL (fld)) + { + context->outer_type = type; + context->offset = offset; + /* As soon as we se an field containing the type, + we know we are not looking for derivations. */ + context->maybe_derived_type = false; + } + } + else if (TREE_CODE (type) == ARRAY_TYPE) + { + tree subtype = TREE_TYPE (type); + + /* Give up if we don't know array size. */ + if (!host_integerp (TYPE_SIZE (subtype), 0) + || !tree_low_cst (TYPE_SIZE (subtype), 0) <= 0) + goto give_up; + offset = offset % tree_low_cst (TYPE_SIZE (subtype), 0); + type = subtype; + context->outer_type = type; + context->offset = offset; + context->maybe_derived_type = false; + } + /* Give up on anything else. */ + else + goto give_up; + } + + /* If we failed to find subtype we look for, give up and fall back to the + most generic query. */ +give_up: + context->outer_type = expected_type; + context->offset = 0; + context->maybe_derived_type = true; + return false; +} + +/* Return true if OUTER_TYPE contains OTR_TYPE at OFFSET. */ + +static bool +contains_type_p (tree outer_type, HOST_WIDE_INT offset, + tree otr_type) +{ + ipa_polymorphic_call_context context = {offset, outer_type, + false, true}; + return get_class_context (&context, otr_type); +} + +/* Given REF call in FNDECL, determine class of the polymorphic + call (OTR_TYPE), its token (OTR_TOKEN) and CONTEXT. + Return pointer to object described by the context */ + +tree +get_polymorphic_call_info (tree fndecl, + tree ref, + tree *otr_type, + HOST_WIDE_INT *otr_token, + ipa_polymorphic_call_context *context) +{ + tree base_pointer; + *otr_type = obj_type_ref_class (ref); + *otr_token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1); + + /* Set up basic info in case we find nothing interesting in the analysis. */ + context->outer_type = *otr_type; + context->offset = 0; + base_pointer = OBJ_TYPE_REF_OBJECT (ref); + context->maybe_derived_type = true; + context->maybe_in_construction = false; + + /* Walk SSA for outer object. */ + do + { + if (TREE_CODE (base_pointer) == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (base_pointer) + && SSA_NAME_DEF_STMT (base_pointer) + && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer))) + { + base_pointer = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (base_pointer)); + STRIP_NOPS (base_pointer); + } + else if (TREE_CODE (base_pointer) == ADDR_EXPR) + { + HOST_WIDE_INT size, max_size; + HOST_WIDE_INT offset2; + tree base = get_ref_base_and_extent (TREE_OPERAND (base_pointer, 0), + &offset2, &size, &max_size); + + /* If this is a varying address, punt. */ + if ((TREE_CODE (base) == MEM_REF || DECL_P (base)) + && max_size != -1 + && max_size == size) + { + /* We found dereference of a pointer. Type of the pointer + and MEM_REF is meaningless, but we can look futher. */ + if (TREE_CODE (base) == MEM_REF) + { + base_pointer = TREE_OPERAND (base, 0); + context->offset + += offset2 + mem_ref_offset (base).low * BITS_PER_UNIT; + context->outer_type = NULL; + } + /* We found base object. In this case the outer_type + is known. */ + else if (DECL_P (base)) + { + context->outer_type = TREE_TYPE (base); + gcc_assert (!POINTER_TYPE_P (context->outer_type)); + + /* Only type inconsistent programs can have otr_type that is + not part of outer type. */ + if (!contains_type_p (context->outer_type, + context->offset, *otr_type)) + { + return base_pointer; + } + context->offset += offset2; + base_pointer = NULL; + /* Make very conservative assumption that all objects + may be in construction. + TODO: ipa-prop already contains code to tell better. + merge it later. */ + context->maybe_in_construction = true; + context->maybe_derived_type = false; + return base_pointer; + } + else + break; + } + else + break; + } + else if (TREE_CODE (base_pointer) == POINTER_PLUS_EXPR + && host_integerp (TREE_OPERAND (base_pointer, 1), 1)) + { + context->offset += tree_low_cst (TREE_OPERAND (base_pointer, 1), 1) + * BITS_PER_UNIT; + base_pointer = TREE_OPERAND (base_pointer, 0); + } + else + break; + } + while (true); + + /* Try to determine type of the outer object. */ + if (TREE_CODE (base_pointer) == SSA_NAME + && SSA_NAME_IS_DEFAULT_DEF (base_pointer) + && TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL) + { + /* See if parameter is THIS pointer of a method. */ + if (TREE_CODE (TREE_TYPE (fndecl)) == METHOD_TYPE + && SSA_NAME_VAR (base_pointer) == DECL_ARGUMENTS (fndecl)) + { + context->outer_type = TREE_TYPE (TREE_TYPE (base_pointer)); + gcc_assert (TREE_CODE (context->outer_type) == RECORD_TYPE); + + /* Dynamic casting has possibly upcasted the type + in the hiearchy. In this case outer type is less + informative than inner type and we should forget + about it. */ + if (!contains_type_p (context->outer_type, context->offset, + *otr_type)) + { + context->outer_type = NULL; + return base_pointer; + } + + /* If the function is constructor or destructor, then + the type is possibly in consturction, but we know + it is not derived type. */ + if (DECL_CXX_CONSTRUCTOR_P (fndecl) + || DECL_CXX_DESTRUCTOR_P (fndecl)) + { + context->maybe_in_construction = true; + context->maybe_derived_type = false; + } + else + { + context->maybe_derived_type = true; + context->maybe_in_construction = false; + } + return base_pointer; + } + /* Non-PODs passed by value are really passed by invisible + reference. In this case we also know the type of the + object. */ + if (DECL_BY_REFERENCE (SSA_NAME_VAR (base_pointer))) + { + context->outer_type = TREE_TYPE (TREE_TYPE (base_pointer)); + gcc_assert (!POINTER_TYPE_P (context->outer_type)); + /* Only type inconsistent programs can have otr_type that is + not part of outer type. */ + if (!contains_type_p (context->outer_type, context->offset, + *otr_type)) + { + context->outer_type = NULL; + gcc_unreachable (); + return base_pointer; + } + context->maybe_derived_type = false; + context->maybe_in_construction = false; + return base_pointer; + } + } + /* TODO: There are multiple ways to derive a type. For instance + if BASE_POINTER is passed to an constructor call prior our refernece. + We do not make this type of flow sensitive analysis yet. */ + return base_pointer; +} + +/* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET. + Lookup their respecitve virtual methods for OTR_TOKEN and OTR_TYPE + and insert them to NODES. + + MATCHED_VTABLES and INSERTED is used to avoid duplicated work. */ + +static void +walk_bases (tree otr_type, + HOST_WIDE_INT otr_token, + tree outer_type, + HOST_WIDE_INT offset, + vec <cgraph_node *> nodes, + pointer_set_t *inserted, + pointer_set_t *matched_vtables, + bool *finalp) +{ + while (true) + { + HOST_WIDE_INT pos, size; + tree base_binfo; + tree fld; + + if (types_same_for_odr (outer_type, otr_type)) + return; + + for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld)) + { + if (TREE_CODE (fld) != FIELD_DECL) + continue; + + pos = int_bit_position (fld); + size = tree_low_cst (DECL_SIZE (fld), 1); + if (pos <= offset && (pos + size) > offset) + break; + } + /* Within a class type we should always find correcponding fields. */ + gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE); + + /* Nonbasetypes should have been stripped by outer_class_type. */ + gcc_assert (DECL_ARTIFICIAL (fld)); + + outer_type = TREE_TYPE (fld); + offset -= pos; + + base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type), + offset, otr_type); + gcc_assert (base_binfo); + if (!pointer_set_insert (matched_vtables, BINFO_VTABLE (base_binfo))) + { + tree target = gimple_get_virt_method_for_binfo (otr_token, base_binfo); + if (target) + maybe_record_node (nodes, target, inserted, finalp); + /* The only way method in anonymous namespace can become unreferable + is that it has been fully optimized out. */ + else if (flag_ltrans || !type_in_anonymous_namespace_p (outer_type)) + *finalp = false; + pointer_set_insert (matched_vtables, BINFO_VTABLE (base_binfo)); + } + } +} + /* When virtual table is removed, we may need to flush the cache. */ static void @@ -766,8 +1143,14 @@ devirt_variable_node_removal_hook (struc } /* Return vector containing possible targets of polymorphic call of type - OTR_TYPE caling method OTR_TOKEN with OFFSET. If FINALp is non-NULL, - store true if the list is complette. + OTR_TYPE caling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET. + If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containig + OTR_TYPE and include their virtual method. This is useful for types + possibly in construction or destruction where the virtual table may + temporarily change to one of base types. INCLUDE_DERIVER_TYPES make + us to walk the inheritance graph for all derivations. + + If FINALp is non-NULL, store true if the list is complette. CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry in the target cache. If user needs to visit every target list just once, it can memoize them. @@ -779,6 +1162,7 @@ devirt_variable_node_removal_hook (struc vec <cgraph_node *> possible_polymorphic_call_targets (tree otr_type, HOST_WIDE_INT otr_token, + ipa_polymorphic_call_context context, bool *finalp, void **cache_token) { @@ -786,25 +1170,36 @@ possible_polymorphic_call_targets (tree pointer_set_t *inserted; pointer_set_t *matched_vtables; vec <cgraph_node *> nodes=vNULL; - odr_type type; + odr_type type, outer_type; polymorphic_call_target_d key; polymorphic_call_target_d **slot; unsigned int i; tree binfo, target; + bool final; - if (finalp) - *finalp = false; + type = get_odr_type (otr_type, true); - type = get_odr_type (otr_type, false); - /* If we do not have type in our hash it means we never seen any method - in it. */ - if (!type) - return nodes; + /* Lookup the outer class type we want to walk. */ + if (context.outer_type) + get_class_context (&context, otr_type); - /* For anonymous namespace types we can attempt to build full type. - All derivations must be in this unit. */ - if (type->anonymous_namespace && finalp && !flag_ltrans) - *finalp = true; + /* We now canonicalize our query, so we do not need extra hashtable entries. */ + + /* Without outer type, we have no use for offset. Just do the + basic search from innter type */ + if (!context.outer_type) + { + context.outer_type = otr_type; + context.offset = 0; + } + /* We need to update our hiearchy if the type does not exist. */ + outer_type = get_odr_type (context.outer_type, true); + /* If outer and inner type match, there are no bases to see. */ + if (type == outer_type) + context.maybe_in_construction = false; + /* If the type is final, there are no derivations. */ + if (TYPE_FINAL_P (outer_type->type)) + context.maybe_derived_type = false; /* Initialize query cache. */ if (!cached_polymorphic_call_targets) @@ -823,43 +1218,75 @@ possible_polymorphic_call_targets (tree /* Lookup cached answer. */ key.type = type; key.otr_token = otr_token; + key.context = context; slot = polymorphic_call_target_hash.find_slot (&key, INSERT); if (cache_token) *cache_token = (void *)*slot; if (*slot) - return (*slot)->targets; + { + if (finalp) + *finalp = (*slot)->final; + return (*slot)->targets; + } + + final = true; /* Do actual search. */ timevar_push (TV_IPA_VIRTUAL_CALL); *slot = XCNEW (polymorphic_call_target_d); if (cache_token) - *cache_token = (void *)*slot; + *cache_token = (void *)*slot; (*slot)->type = type; (*slot)->otr_token = otr_token; + (*slot)->context = context; inserted = pointer_set_create (); matched_vtables = pointer_set_create (); /* First see virtual method of type itself. */ - binfo = TYPE_BINFO (type->type); + binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type), + context.offset, otr_type); target = gimple_get_virt_method_for_binfo (otr_token, binfo); if (target) - maybe_record_node (nodes, target, inserted); + { + maybe_record_node (nodes, target, inserted, &final); + + /* In the case we get final method, we don't need + to walk derivations. */ + if (DECL_FINAL_P (target)) + context.maybe_derived_type = false; + } + /* The only way method in anonymous namespace can become unreferable + is that it has been fully optimized out. */ + else if (flag_ltrans || !type->anonymous_namespace) + final = false; pointer_set_insert (matched_vtables, BINFO_VTABLE (binfo)); - /* TODO: If method is final, we can stop here and signaize that - list is final. We need C++ FE to pass our info about final - methods and classes. */ + /* Next walk bases, if asked to. */ + if (context.maybe_in_construction) + walk_bases (otr_type, otr_token, outer_type->type, + context.offset, nodes, inserted, + matched_vtables, &final); - /* Walk recursively all derived types. Here we need to lookup proper basetype - via their BINFO walk that is done by record_binfo */ - for (i = 0; i < type->derived_types.length(); i++) - possible_polymorphic_call_targets_1 (nodes, inserted, - matched_vtables, - otr_type, type->derived_types[i], - otr_token); + /* Finally walk recursively all derived types. */ + if (context.maybe_derived_type) + { + /* For anonymous namespace types we can attempt to build full type. + All derivations must be in this unit (unless we see partial unit). */ + if (!type->anonymous_namespace || flag_ltrans) + final = false; + for (i = 0; i < outer_type->derived_types.length(); i++) + possible_polymorphic_call_targets_1 (nodes, inserted, + matched_vtables, + otr_type, outer_type->derived_types[i], + otr_token, outer_type->type, + context.offset); + } (*slot)->targets = nodes; + (*slot)->final = final; + if (finalp) + *finalp = final; pointer_set_destroy (inserted); pointer_set_destroy (matched_vtables); @@ -871,8 +1298,9 @@ possible_polymorphic_call_targets (tree void dump_possible_polymorphic_call_targets (FILE *f, - tree otr_type, - HOST_WIDE_INT otr_token) + tree otr_type, + HOST_WIDE_INT otr_token, + const ipa_polymorphic_call_context &ctx) { vec <cgraph_node *> targets; bool final; @@ -882,16 +1310,25 @@ dump_possible_polymorphic_call_targets ( if (!type) return; targets = possible_polymorphic_call_targets (otr_type, otr_token, + ctx, &final); - fprintf (f, "Targets of polymorphic call of type %i ", type->id); + fprintf (f, " Targets of polymorphic call of type %i:", type->id); print_generic_expr (f, type->type, TDF_SLIM); - fprintf (f, " token %i%s:", - (int)otr_token, - final ? " (full list)" : " (partial list, may call to other unit)"); + fprintf (f, " token %i\n" + " Contained in type:", + (int)otr_token); + print_generic_expr (f, ctx.outer_type, TDF_SLIM); + fprintf (f, " at offset "HOST_WIDE_INT_PRINT_DEC"\n" + " %s%s%s\n ", + ctx.offset, + final ? "This is full list." : + "This is partial list; extra targets may be defined in other units.", + ctx.maybe_in_construction ? " (base types included)" : "", + ctx.maybe_derived_type ? " (derived types included)" : ""); for (i = 0; i < targets.length (); i++) fprintf (f, " %s/%i", cgraph_node_name (targets[i]), targets[i]->symbol.order); - fprintf (f, "\n"); + fprintf (f, "\n\n"); } @@ -901,23 +1338,26 @@ dump_possible_polymorphic_call_targets ( bool possible_polymorphic_call_target_p (tree otr_type, HOST_WIDE_INT otr_token, + const ipa_polymorphic_call_context &ctx, struct cgraph_node *n) { vec <cgraph_node *> targets; unsigned int i; - bool final; + enum built_in_function fcode; + + /* Those represent impossible scenarios. */ + if (TREE_CODE (TREE_TYPE (n->symbol.decl)) == FUNCTION_TYPE + && ((fcode = DECL_FUNCTION_CODE (n->symbol.decl)) + == BUILT_IN_UNREACHABLE + || fcode == BUILT_IN_TRAP)) + return true; if (!odr_hash.is_created ()) return true; - targets = possible_polymorphic_call_targets (otr_type, otr_token, &final); + targets = possible_polymorphic_call_targets (otr_type, otr_token, ctx); for (i = 0; i < targets.length (); i++) - if (n == targets[i]) + if (symtab_semantically_equivalent_p ((symtab_node)n, (symtab_node)targets[i])) return true; - - /* At a moment we allow middle end to dig out new external declarations - as a targets of polymorphic calls. */ - if (!final && !n->symbol.definition) - return true; return false; } @@ -934,7 +1374,7 @@ update_type_inheritance_graph (void) return; free_polymorphic_call_targets_hash (); timevar_push (TV_IPA_INHERITANCE); - /* We reconstruct the graph starting of types of all methods seen in the + /* We reconstruct the graph starting from types of all methods seen in the the unit. */ FOR_EACH_FUNCTION (n) if (DECL_VIRTUAL_P (n->symbol.decl) Index: ipa-prop.c =================================================================== --- ipa-prop.c (revision 202838) +++ ipa-prop.c (working copy) @@ -378,6 +378,7 @@ ipa_set_jf_known_type (struct ipa_jump_f jfunc->value.known_type.offset = offset, jfunc->value.known_type.base_type = base_type; jfunc->value.known_type.component_type = component_type; + gcc_assert (component_type); } /* Set JFUNC to be a copy of another jmp (to be used by jump function @@ -1727,8 +1728,6 @@ ipa_note_param_call (struct cgraph_node cs = cgraph_edge (node, stmt); cs->indirect_info->param_index = param_index; - cs->indirect_info->offset = 0; - cs->indirect_info->polymorphic = 0; cs->indirect_info->agg_contents = 0; cs->indirect_info->member_ptr = 0; return cs; @@ -1825,6 +1824,8 @@ ipa_analyze_indirect_call_uses (struct c &by_ref)) { struct cgraph_edge *cs = ipa_note_param_call (node, index, call); + if (cs->indirect_info->offset != offset) + cs->indirect_info->outer_type = NULL; cs->indirect_info->offset = offset; cs->indirect_info->agg_contents = 1; cs->indirect_info->by_ref = by_ref; @@ -1922,6 +1923,8 @@ ipa_analyze_indirect_call_uses (struct c && parm_preserved_before_stmt_p (&parms_ainfo[index], call, rec)) { struct cgraph_edge *cs = ipa_note_param_call (node, index, call); + if (cs->indirect_info->offset != offset) + cs->indirect_info->outer_type = NULL; cs->indirect_info->offset = offset; cs->indirect_info->agg_contents = 1; cs->indirect_info->member_ptr = 1; @@ -2758,6 +2761,8 @@ update_indirect_edges_after_inlining (st else { ici->param_index = ipa_get_jf_ancestor_formal_id (jfunc); + if (ipa_get_jf_ancestor_offset (jfunc)) + ici->outer_type = NULL; ici->offset += ipa_get_jf_ancestor_offset (jfunc); } } @@ -4072,12 +4077,15 @@ ipa_write_indirect_edge_info (struct out bp_pack_value (&bp, ii->agg_contents, 1); bp_pack_value (&bp, ii->member_ptr, 1); bp_pack_value (&bp, ii->by_ref, 1); + bp_pack_value (&bp, ii->maybe_in_construction, 1); + bp_pack_value (&bp, ii->maybe_derived_type, 1); streamer_write_bitpack (&bp); if (ii->polymorphic) { streamer_write_hwi (ob, ii->otr_token); stream_write_tree (ob, ii->otr_type, true); + stream_write_tree (ob, ii->outer_type, true); } } @@ -4099,10 +4107,13 @@ ipa_read_indirect_edge_info (struct lto_ ii->agg_contents = bp_unpack_value (&bp, 1); ii->member_ptr = bp_unpack_value (&bp, 1); ii->by_ref = bp_unpack_value (&bp, 1); + ii->maybe_in_construction = bp_unpack_value (&bp, 1); + ii->maybe_derived_type = bp_unpack_value (&bp, 1); if (ii->polymorphic) { ii->otr_token = (HOST_WIDE_INT) streamer_read_hwi (ib); ii->otr_type = stream_read_tree (ib, data_in); + ii->outer_type = stream_read_tree (ib, data_in); } }
Hi, this is updated version of http://gcc.gnu.org/ml/gcc-patches/2013-09/msg00936.html It updates the type inheritance graph walking algorithm to be context sensitive. Contex is stored in ipa_polymorhic_call_context containing - OUTER_TYPE (a type of memory object that contains the object whose method is called, NULL if unknown) - OFFSET offset withing OUTER_TYPE where object is located - MAYBE_IN_CONSTRUCTION true if the object may be in construction. I.e. it is local or static variable. At the moment we do not try to disprove construciton that is partly done by ipa-prop and is planned to be merged here in future - MAYBE_DERIVED_TYPE if OUTER_TYPE object actually may be a derivation of a type. For example when OUTER_TYPE was determined from THIS parameter of a method. There is cgraph_indirect_call_info that walks GIMPLE code and attempts to determine the context of a given call. It looks for objects located in declarations (static vars/ automatic vars/parameters), objects passed by invisible references and objects passed as THIS pointers. The second two cases are new, the first case is already done by gimple_extract_devirt_binfo_from_cst Context is determined by cgraph construction code and stored in cgraph edges. In future I expect ipa-prop to manipulate and update the contextes and propagate across them, but it is not implemented. For this reason I did not add context itself into cgrpah edge, merely I added the new info and hacked ipa-prop (temporarily) to simply throw away the actual info. The highlevel idea is to make get_class_context to fill in info for known type and ancestor functions, too and then we can have function combining types + doing propagation across them replacing the current code that deals with BINFOs directly and thus can not deal with all the cases above very well. possible_polymorphic_call_targets is now bit more complex. it is split into - get_class_context this function walks the OUTER_TYPE (if present) and looks up the type of class actually containing the method being called. Previously similar logic was part of gimple_extract_devirt_binfo_from_cst. - walk_bases When type is in construction, all base types are walked and for those containing OTR_TYPE at proper memory location the corresponding virtual methods are added to list - record_binfos now walks the inner binfo from OUTER_TYPE to OTR_TYPE via get_binfo_at_offset. Bootstrapped/regtested x86_64-linux. The patch is tested by ipa-devirt9 testcase. I have extra four, but I would like to first fix the case where the devirtualization happens in TODO of early_local_passes that is not dumped anywhere. So I plan to post these incrementally once this code is hooked also into gimple folding. The patch results in 60% more devirtualizations on Firefox and 10% more speculative devirtualization. I think main component missing now is code determining dynamic type from a call to constructor. I have some prototype for this, too, I would like to discuss incrementally. I am not 100% sure how much harder tracking of dynamic type changes becomes here. Martin, does it seem to make sense? Honza * cgraph.c (cgraph_create_indirect_edge): Use get_polymorphic_call_info. * cgraph.h (cgraph_indirect_call_info): Add outer_type, maybe_in_construction and maybe_derived_type. * ipa-utils.h (ipa_polymorphic_call_context): New structure. (ipa_dummy_polymorphic_call_context): New global var. (possible_polymorphic_call_targets): Add context paramter. (dump_possible_polymorphic_call_targets): Likewise; update wrappers. (possible_polymorphic_call_target_p): Likewise. (get_polymorphic_call_info): New function. * ipa-devirt.c (ipa_dummy_polymorphic_call_context): New function. (add_type_duplicate): Remove forgotten debug output. (method_class_type): Add sanity check. (maybe_record_node): Add FINALP parameter. (record_binfo): Add OUTER_TYPE and OFFSET; walk the inner by info by get_binfo_at_offset. (possible_polymorphic_call_targets_1): Add OUTER_TYPE/OFFSET parameters; pass them to record-binfo. (polymorphic_call_target_d): Add context and FINAL. (polymorphic_call_target_hasher::hash): Hash context. (polymorphic_call_target_hasher::equal): Compare context. (free_polymorphic_call_targets_hash): (get_class_context): New function. (contains_type_p): New function. (get_polymorphic_call_info): New function. (walk_bases): New function. (possible_polymorphic_call_targets): Add context parameter; honnor it. (dump_possible_polymorphic_call_targets): Dump context. (possible_polymorphic_call_target_p): Add context. (update_type_inheritance_graph): Update comment.s (ipa_set_jf_known_type): Assert that compoentn type is known. (ipa_note_param_call): Do not tamper with offsets. (ipa_analyze_indirect_call_uses): When offset is being changed; clear outer type. (update_indirect_edges_after_inlining): Likewise. (ipa_write_indirect_edge_info): Stream new fields. (ipa_read_indirect_edge_info): Stream in new fields. * ipa/devirt9.C: Verify that the optimization happens already before. whole-program.