| Message ID | 20111027195454.GF26381@virgil.arch.suse.de |
|---|---|
| State | New |
| Headers | show |
On Thu, Oct 27, 2011 at 9:54 PM, Martin Jambor <mjambor@suse.cz> wrote: > Hi, > > On Thu, Oct 27, 2011 at 11:06:02AM +0200, Richard Guenther wrote: >> On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor <mjambor@suse.cz> wrote: >> > Hi, >> > >> > I've been asked by Maxim Kuvyrkov to revive the following patch which >> > has not made it to 4.6. Currently, when type based devirtualization >> > detects a potential type change, it simply gives up on gathering any >> > information on the object in question. This patch adds an attempt to >> > actually detect the new type after the change. >> > >> > Maxim claimed this (and another patch I'll post tomorrow) noticeably >> > improved performance of some real code. I can only offer a rather >> > artificial example in the attachment. When the constructors are >> > inlined but the function multiply_matrices is not, this patch makes >> > the produced executable run for only 7 seconds instead of about 20 on >> > my 4 year old i686 desktop (with -Ofast). >> > >> > Anyway, the patch passes bootstrap and testsuite on x86_64-linux. >> > What do you think, is it a good idea for trunk now? >> > >> > Thanks, >> > >> > Martin >> > >> > >> > 2011-10-21 Martin Jambor <mjambor@suse.cz> >> > >> > * ipa-prop.c (type_change_info): New fields object, known_current_type >> > and multiple_types_encountered. >> > (extr_type_from_vtbl_ptr_store): New function. >> > (check_stmt_for_type_change): Use it, set multiple_types_encountered if >> > the result is different from the previous one. >> > (detect_type_change): Renamed to detect_type_change_1. New parameter >> > comp_type. Set up new fields in tci, build known type jump >> > functions if the new type can be identified. >> > (detect_type_change): New function. >> > * tree.h (DECL_CONTEXT): Comment new use. >> > >> > * testsuite/g++.dg/ipa/devirt-c-1.C: Add dump scans. >> > * testsuite/g++.dg/ipa/devirt-c-2.C: Likewise. >> > * testsuite/g++.dg/ipa/devirt-c-7.C: New test. >> > >> > >> > Index: src/gcc/ipa-prop.c >> > =================================================================== >> > --- src.orig/gcc/ipa-prop.c >> > +++ src/gcc/ipa-prop.c >> > @@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f) >> > >> > struct type_change_info >> > { >> > + /* The declaration or SSA_NAME pointer of the base that we are checking for >> > + type change. */ >> > + tree object; >> > + /* If we actually can tell the type that the object has changed to, it is >> > + stored in this field. Otherwise it remains NULL_TREE. */ >> > + tree known_current_type; >> > /* Set to true if dynamic type change has been detected. */ >> > bool type_maybe_changed; >> > + /* Set to true if multiple types have been encountered. known_current_type >> > + must be disregarded in that case. */ >> > + bool multiple_types_encountered; >> > }; >> > >> > /* Return true if STMT can modify a virtual method table pointer. >> > @@ -338,6 +347,49 @@ stmt_may_be_vtbl_ptr_store (gimple stmt) >> > return true; >> > } >> > >> > +/* If STMT can be proved to be an assignment to the virtual method table >> > + pointer of ANALYZED_OBJ and the type associated with the new table >> > + identified, return the type. Otherwise return NULL_TREE. */ >> > + >> > +static tree >> > +extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj) >> > +{ >> > + tree lhs, t, obj; >> > + >> > + if (!is_gimple_assign (stmt)) >> >> gimple_assign_single_p (stmt) > > OK. > >> >> > + return NULL_TREE; >> > + >> > + lhs = gimple_assign_lhs (stmt); >> > + >> > + if (TREE_CODE (lhs) != COMPONENT_REF) >> > + return NULL_TREE; >> > + obj = lhs; >> > + >> > + if (!DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))) >> > + return NULL_TREE; >> > + >> > + do >> > + { >> > + obj = TREE_OPERAND (obj, 0); >> > + } >> > + while (TREE_CODE (obj) == COMPONENT_REF); >> >> You do not allow other components than component-refs (thus, for >> example an ARRAY_REF - that is for a reason?). Please add >> a comment why. Otherwise this whole sequence would look like >> it should be replaceable by get_base_address (obj). >> > > I guess I might have been overly conservative here, ARRAY_REFs are > fine. get_base_address only digs into MEM_REFs if they are based on > an ADDR_EXPR while I do so always. But I can check that either both > obj and analyzed_obj are a MEM_REF of the same SSA_NAME or they are > the same thing (i.e. the same decl)... which even feels a bit cleaner, > so I did that. Well, as you are looking for a must-change-type pattern I think you cannot simply ignore offsets. Consider T a[10]; new (T') (&a[9]); a[8]->foo(); where the must-type-change on a[9] is _not_ changing the type of a[8]! Similar cases might happen with class Compound { T a; T b; }; no? Please think about the difference must vs. may-type-change for these cases. I'm not convinced that the must-type-change code is correct. Richard. > >> > + if (TREE_CODE (obj) == MEM_REF) >> > + obj = TREE_OPERAND (obj, 0); >> > + if (TREE_CODE (obj) == ADDR_EXPR) >> > + obj = TREE_OPERAND (obj, 0); >> > + if (obj != analyzed_obj) >> > + return NULL_TREE; >> > + >> > + t = gimple_assign_rhs1 (stmt); >> > + if (TREE_CODE (t) != ADDR_EXPR) >> > + return NULL_TREE; >> > + t = get_base_address (TREE_OPERAND (t, 0)); >> >> Do we actually ever store sth else than the plain address of a >> virtual table (thus, &decl)? If so, what difference makes the offset >> into the virtual table we get in this way? I ask, because ... >> >> > + if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t)) >> > + return NULL_TREE; >> > + >> > + return DECL_CONTEXT (t); >> >> ... DECL_CONTEXT (t) is of course independent of any offset. >> >> Thus I think you should drop the call to get_base_address () and >> instead just look at TREE_OPERAND (t, 0). > > Even the simplest cases of assignments have basically a form like > this: > > this_1(D)->_vptr.A = &MEM[(void *)&_ZTV1A + 8B]; > > so I need to extract the actual VAR_DECL somehow. But of course I can > do that by looking through the MEM_REF and ADDR_EXPR by hand, if > preferable. > >> >> > +} >> > + >> > /* Callback of walk_aliased_vdefs and a helper function for >> > detect_type_change to check whether a particular statement may modify >> > the virtual table pointer, and if possible also determine the new type of >> > @@ -352,6 +404,12 @@ check_stmt_for_type_change (ao_ref *ao A >> > >> > if (stmt_may_be_vtbl_ptr_store (stmt)) >> > { >> > + tree type; >> > + type = extr_type_from_vtbl_ptr_store (stmt, tci->object); >> > + if (tci->type_maybe_changed >> > + && type != tci->known_current_type) >> > + tci->multiple_types_encountered = true; >> > + tci->known_current_type = type; >> > tci->type_maybe_changed = true; >> > return true; >> > } >> > @@ -359,19 +417,19 @@ check_stmt_for_type_change (ao_ref *ao A >> > return false; >> > } >> > >> > -/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by >> > - looking for assignments to its virtual table pointer. If it is, return true >> > - and fill in the jump function JFUNC with relevant type information or set it >> > - to unknown. ARG is the object itself (not a pointer to it, unless >> > - dereferenced). BASE is the base of the memory access as returned by >> > - get_ref_base_and_extent, as is the offset. */ >> > + >> > + >> > +/* Like detect_type_change but with extra argument COMP_TYPE which will become >> > + the component type part of new JFUNC of dynamic type change is detected and >> > + the new base type is identified. */ >> > >> > static bool >> > -detect_type_change (tree arg, tree base, gimple call, >> > - struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) >> > +detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call, >> > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) >> > { >> > struct type_change_info tci; >> > ao_ref ao; >> > + tree t; >> > >> > gcc_checking_assert (DECL_P (arg) >> > || TREE_CODE (arg) == MEM_REF >> > @@ -381,8 +439,6 @@ detect_type_change (tree arg, tree base, >> > if (!flag_devirtualize || !gimple_vuse (call)) >> > return false; >> > >> > - tci.type_maybe_changed = false; >> > - >> > ao.ref = arg; >> > ao.base = base; >> > ao.offset = offset; >> > @@ -391,15 +447,51 @@ detect_type_change (tree arg, tree base, >> > ao.ref_alias_set = -1; >> > ao.base_alias_set = -1; >> > >> > + t = arg; >> > + while (handled_component_p (t)) >> > + t = TREE_OPERAND (t, 0); >> >> Here you are using handled_component_p, thus allow ARRAY_REFs ... >> but you are not trying to distinguish a[1] from a[2] anywhere, so this >> looks bogus and instead should look like the case above (with a comment >> as to why looking at ARRAY_REFs would be bogus). > > I changed both to get_base_address as described above. > > This is the new version of the patch which I'm currently bootstrapping > and testing on an x86_64-linux. OK for trunk if it passes? Thanks. > > Martin > > > 2011-10-27 Martin Jambor <mjambor@suse.cz> > > * ipa-prop.c (type_change_info): New fields object, known_current_type > and multiple_types_encountered. > (extr_type_from_vtbl_ptr_store): New function. > (check_stmt_for_type_change): Use it, set multiple_types_encountered if > the result is different from the previous one. > (detect_type_change): Renamed to detect_type_change_1. New parameter > comp_type. Set up new fields in tci, build known type jump > functions if the new type can be identified. > (detect_type_change): New function. > * tree.h (DECL_CONTEXT): Comment new use. > > * testsuite/g++.dg/ipa/devirt-c-1.C: Add dump scans. > * testsuite/g++.dg/ipa/devirt-c-2.C: Likewise. > * testsuite/g++.dg/ipa/devirt-c-7.C: New test. > > > Index: src/gcc/ipa-prop.c > =================================================================== > --- src.orig/gcc/ipa-prop.c > +++ src/gcc/ipa-prop.c > @@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f) > > struct type_change_info > { > + /* The declaration or SSA_NAME pointer of the base that we are checking for > + type change. */ > + tree object; > + /* If we actually can tell the type that the object has changed to, it is > + stored in this field. Otherwise it remains NULL_TREE. */ > + tree known_current_type; > /* Set to true if dynamic type change has been detected. */ > bool type_maybe_changed; > + /* Set to true if multiple types have been encountered. known_current_type > + must be disregarded in that case. */ > + bool multiple_types_encountered; > }; > > /* Return true if STMT can modify a virtual method table pointer. > @@ -338,6 +347,44 @@ stmt_may_be_vtbl_ptr_store (gimple stmt) > return true; > } > > +/* If STMT can be proved to be an assignment to the virtual method table > + pointer of ANALYZED_OBJ and the type associated with the new table > + identified, return the type. Otherwise return NULL_TREE. */ > + > +static tree > +extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj) > +{ > + tree lhs, t, obj; > + > + if (!gimple_assign_single_p (stmt)) > + return NULL_TREE; > + > + lhs = gimple_assign_lhs (stmt); > + > + if (TREE_CODE (lhs) != COMPONENT_REF > + || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))) > + return NULL_TREE; > + > + obj = get_base_address (lhs); > + if (TREE_CODE (obj) == MEM_REF) > + { > + if (TREE_CODE (analyzed_obj) != MEM_REF > + || TREE_OPERAND (analyzed_obj, 0) != TREE_OPERAND (obj, 0)) > + return NULL_TREE; > + } > + else if (analyzed_obj != obj) > + return NULL_TREE; > + > + t = gimple_assign_rhs1 (stmt); > + if (TREE_CODE (t) != ADDR_EXPR) > + return NULL_TREE; > + t = get_base_address (TREE_OPERAND (t, 0)); > + if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t)) > + return NULL_TREE; > + > + return DECL_CONTEXT (t); > +} > + > /* Callback of walk_aliased_vdefs and a helper function for > detect_type_change to check whether a particular statement may modify > the virtual table pointer, and if possible also determine the new type of > @@ -352,6 +399,12 @@ check_stmt_for_type_change (ao_ref *ao A > > if (stmt_may_be_vtbl_ptr_store (stmt)) > { > + tree type; > + type = extr_type_from_vtbl_ptr_store (stmt, tci->object); > + if (tci->type_maybe_changed > + && type != tci->known_current_type) > + tci->multiple_types_encountered = true; > + tci->known_current_type = type; > tci->type_maybe_changed = true; > return true; > } > @@ -359,16 +412,15 @@ check_stmt_for_type_change (ao_ref *ao A > return false; > } > > -/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by > - looking for assignments to its virtual table pointer. If it is, return true > - and fill in the jump function JFUNC with relevant type information or set it > - to unknown. ARG is the object itself (not a pointer to it, unless > - dereferenced). BASE is the base of the memory access as returned by > - get_ref_base_and_extent, as is the offset. */ > + > + > +/* Like detect_type_change but with extra argument COMP_TYPE which will become > + the component type part of new JFUNC of dynamic type change is detected and > + the new base type is identified. */ > > static bool > -detect_type_change (tree arg, tree base, gimple call, > - struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) > +detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call, > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) > { > struct type_change_info tci; > ao_ref ao; > @@ -381,8 +433,6 @@ detect_type_change (tree arg, tree base, > if (!flag_devirtualize || !gimple_vuse (call)) > return false; > > - tci.type_maybe_changed = false; > - > ao.ref = arg; > ao.base = base; > ao.offset = offset; > @@ -391,15 +441,44 @@ detect_type_change (tree arg, tree base, > ao.ref_alias_set = -1; > ao.base_alias_set = -1; > > + tci.object = get_base_address (arg); > + tci.known_current_type = NULL_TREE; > + tci.type_maybe_changed = false; > + tci.multiple_types_encountered = false; > + > walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change, > &tci, NULL); > if (!tci.type_maybe_changed) > return false; > > - jfunc->type = IPA_JF_UNKNOWN; > + if (!tci.known_current_type > + || tci.multiple_types_encountered > + || offset != 0) > + jfunc->type = IPA_JF_UNKNOWN; > + else > + { > + jfunc->type = IPA_JF_KNOWN_TYPE; > + jfunc->value.known_type.base_type = tci.known_current_type; > + jfunc->value.known_type.component_type = comp_type; > + } > + > return true; > } > > +/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by > + looking for assignments to its virtual table pointer. If it is, return true > + and fill in the jump function JFUNC with relevant type information or set it > + to unknown. ARG is the object itself (not a pointer to it, unless > + dereferenced). BASE is the base of the memory access as returned by > + get_ref_base_and_extent, as is the offset. */ > + > +static bool > +detect_type_change (tree arg, tree base, gimple call, > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) > +{ > + return detect_type_change_1 (arg, base, TREE_TYPE (arg), call, jfunc, offset); > +} > + > /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer > SSA name (its dereference will become the base and the offset is assumed to > be zero). */ > @@ -407,16 +486,19 @@ detect_type_change (tree arg, tree base, > static bool > detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc) > { > + tree comp_type; > + > gcc_checking_assert (TREE_CODE (arg) == SSA_NAME); > if (!flag_devirtualize > || !POINTER_TYPE_P (TREE_TYPE (arg)) > || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE) > return false; > > + comp_type = TREE_TYPE (TREE_TYPE (arg)); > arg = build2 (MEM_REF, ptr_type_node, arg, > - build_int_cst (ptr_type_node, 0)); > + build_int_cst (ptr_type_node, 0)); > > - return detect_type_change (arg, arg, call, jfunc, 0); > + return detect_type_change_1 (arg, arg, comp_type, call, jfunc, 0); > } > > /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C > =================================================================== > --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-1.C > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C > @@ -1,7 +1,7 @@ > /* Verify that ipa-cp correctly detects the dynamic type of an object > under construction when doing devirtualization. */ > /* { dg-do run } */ > -/* { dg-options "-O3 -fno-early-inlining -fno-inline" } */ > +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */ > > extern "C" void abort (void); > > @@ -69,3 +69,8 @@ int main (int argc, char *argv[]) > bah (); > return 0; > } > + > +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo" "cp" } } */ > +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */ > +/* { dg-final { cleanup-ipa-dump "cp" } } */ > +/* { dg-final { cleanup-tree-dump "optimized" } } */ > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C > =================================================================== > --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-2.C > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C > @@ -1,7 +1,7 @@ > /* Verify that ipa-cp correctly detects the dynamic type of an object > under construction when doing devirtualization. */ > /* { dg-do run } */ > -/* { dg-options "-O3 -fno-early-inlining -fno-inline" } */ > +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */ > > extern "C" void abort (void); > > @@ -77,3 +77,8 @@ int main (int argc, char *argv[]) > bah (); > return 0; > } > + > +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo" "cp" } } */ > +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */ > +/* { dg-final { cleanup-ipa-dump "cp" } } */ > +/* { dg-final { cleanup-tree-dump "optimized" } } */ > Index: src/gcc/tree.h > =================================================================== > --- src.orig/gcc/tree.h > +++ src/gcc/tree.h > @@ -2678,7 +2678,9 @@ struct function; > nodes, this points to either the FUNCTION_DECL for the containing > function, the RECORD_TYPE or UNION_TYPE for the containing type, or > NULL_TREE or a TRANSLATION_UNIT_DECL if the given decl has "file > - scope". */ > + scope". In particular, for VAR_DECLs which are virtual table pointers > + (they have DECL_VIRTUAL set), we use DECL_CONTEXT to determine the type > + they belong to. */ > #define DECL_CONTEXT(NODE) (DECL_MINIMAL_CHECK (NODE)->decl_minimal.context) > #define DECL_FIELD_CONTEXT(NODE) \ > (FIELD_DECL_CHECK (NODE)->decl_minimal.context) > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C > =================================================================== > --- /dev/null > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C > @@ -0,0 +1,87 @@ > +/* Verify that ipa-cp will not get confused by placement new constructing an > + object within another one when looking for dynamic type change . */ > +/* { dg-do run } */ > +/* { dg-options "-O3 -Wno-attributes" } */ > + > +extern "C" void abort (void); > +namespace std { > + typedef __SIZE_TYPE__ size_t; > +} > +inline void* __attribute__ ((always_inline)) > +operator new(std::size_t, void* __p) throw() > +{ > + return __p; > +} > + > +class A > +{ > +public: > + char data[256]; > + A(); > + virtual int foo (int i); > +}; > + > +class B : public A > +{ > +public: > + virtual int foo (int i); > +}; > + > +class C > +{ > +public: > + C(); > + virtual double foo (double i); > +}; > + > +int A::foo (int i) > +{ > + return i + 1; > +} > + > +int B::foo (int i) > +{ > + return i + 2; > +} > + > +double C::foo (double i) > +{ > + return i + 3.5; > +} > + > +static int __attribute__ ((noinline)) middleman (class A *obj, int i) > +{ > + return obj->foo (i); > +} > + > +int __attribute__ ((noinline,noclone)) get_input(void) > +{ > + return 1; > +} > + > +__attribute__ ((always_inline)) C::C () > +{ > +} > + > +A::A () > +{ > +} > + > +static __attribute__ ((noinline)) void bah () > +{ > + class B b; > + > + C *c = new ((void *) &b.data) C; > + > + if (middleman (&b, get_input ()) != 3) > + abort (); > +} > + > +int main (int argc, char *argv[]) > +{ > + int i; > + > + for (i = 0; i < 10; i++) > + bah (); > + return 0; > +} >
On Fri, Oct 28, 2011 at 11:21:23AM +0200, Richard Guenther wrote: > On Thu, Oct 27, 2011 at 9:54 PM, Martin Jambor <mjambor@suse.cz> wrote: > > Hi, > > > > On Thu, Oct 27, 2011 at 11:06:02AM +0200, Richard Guenther wrote: > >> On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor <mjambor@suse.cz> wrote: > >> > Hi, > >> > > >> > I've been asked by Maxim Kuvyrkov to revive the following patch which > >> > has not made it to 4.6. Currently, when type based devirtualization > >> > detects a potential type change, it simply gives up on gathering any > >> > information on the object in question. This patch adds an attempt to > >> > actually detect the new type after the change. > >> > > >> > Maxim claimed this (and another patch I'll post tomorrow) noticeably > >> > improved performance of some real code. I can only offer a rather > >> > artificial example in the attachment. When the constructors are > >> > inlined but the function multiply_matrices is not, this patch makes > >> > the produced executable run for only 7 seconds instead of about 20 on > >> > my 4 year old i686 desktop (with -Ofast). > >> > > >> > Anyway, the patch passes bootstrap and testsuite on x86_64-linux. > >> > What do you think, is it a good idea for trunk now? > >> > > >> > Thanks, > >> > > >> > Martin > >> > > >> > > >> > 2011-10-21 Martin Jambor <mjambor@suse.cz> > >> > > >> > * ipa-prop.c (type_change_info): New fields object, known_current_type > >> > and multiple_types_encountered. > >> > (extr_type_from_vtbl_ptr_store): New function. > >> > (check_stmt_for_type_change): Use it, set multiple_types_encountered if > >> > the result is different from the previous one. > >> > (detect_type_change): Renamed to detect_type_change_1. New parameter > >> > comp_type. Set up new fields in tci, build known type jump > >> > functions if the new type can be identified. > >> > (detect_type_change): New function. > >> > * tree.h (DECL_CONTEXT): Comment new use. > >> > > >> > * testsuite/g++.dg/ipa/devirt-c-1.C: Add dump scans. > >> > * testsuite/g++.dg/ipa/devirt-c-2.C: Likewise. > >> > * testsuite/g++.dg/ipa/devirt-c-7.C: New test. > >> > > >> > > >> > Index: src/gcc/ipa-prop.c > >> > =================================================================== > >> > --- src.orig/gcc/ipa-prop.c > >> > +++ src/gcc/ipa-prop.c > >> > @@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f) > >> > > >> > struct type_change_info > >> > { > >> > + /* The declaration or SSA_NAME pointer of the base that we are checking for > >> > + type change. */ > >> > + tree object; > >> > + /* If we actually can tell the type that the object has changed to, it is > >> > + stored in this field. Otherwise it remains NULL_TREE. */ > >> > + tree known_current_type; > >> > /* Set to true if dynamic type change has been detected. */ > >> > bool type_maybe_changed; > >> > + /* Set to true if multiple types have been encountered. known_current_type > >> > + must be disregarded in that case. */ > >> > + bool multiple_types_encountered; > >> > }; > >> > > >> > /* Return true if STMT can modify a virtual method table pointer. > >> > @@ -338,6 +347,49 @@ stmt_may_be_vtbl_ptr_store (gimple stmt) > >> > return true; > >> > } > >> > > >> > +/* If STMT can be proved to be an assignment to the virtual method table > >> > + pointer of ANALYZED_OBJ and the type associated with the new table > >> > + identified, return the type. Otherwise return NULL_TREE. */ > >> > + > >> > +static tree > >> > +extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj) > >> > +{ > >> > + tree lhs, t, obj; > >> > + > >> > + if (!is_gimple_assign (stmt)) > >> > >> gimple_assign_single_p (stmt) > > > > OK. > > > >> > >> > + return NULL_TREE; > >> > + > >> > + lhs = gimple_assign_lhs (stmt); > >> > + > >> > + if (TREE_CODE (lhs) != COMPONENT_REF) > >> > + return NULL_TREE; > >> > + obj = lhs; > >> > + > >> > + if (!DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))) > >> > + return NULL_TREE; > >> > + > >> > + do > >> > + { > >> > + obj = TREE_OPERAND (obj, 0); > >> > + } > >> > + while (TREE_CODE (obj) == COMPONENT_REF); > >> > >> You do not allow other components than component-refs (thus, for > >> example an ARRAY_REF - that is for a reason?). Please add > >> a comment why. Otherwise this whole sequence would look like > >> it should be replaceable by get_base_address (obj). > >> > > > > I guess I might have been overly conservative here, ARRAY_REFs are > > fine. get_base_address only digs into MEM_REFs if they are based on > > an ADDR_EXPR while I do so always. But I can check that either both > > obj and analyzed_obj are a MEM_REF of the same SSA_NAME or they are > > the same thing (i.e. the same decl)... which even feels a bit cleaner, > > so I did that. > > Well, as you are looking for a must-change-type pattern I think you cannot > simply ignore offsets. Consider > > T a[10]; > > new (T') (&a[9]); > a[8]->foo(); > > where the must-type-change on a[9] is _not_ changing the type of a[8]! > > Similar cases might happen with > > class Compound { T a; T b; }; > > no? > > Please think about the difference must vs. may-type-change for these > cases. I'm not convinced that the must-type-change code is correct. > I did, even though it's not always easy because the patch is so old. However, the reasoning is as follows: 1) The callback will never report a known type if the "base address" of the RHS of the assignment is not exactly the same declaration or a MEM_REF of exactly the same SSA name. 2) The aliasing machinery is initialized to exactly the offset we are interested in and the size of one pointer: ao.offset = offset; ao.size = POINTER_SIZE; So, either the access which can alter the virtual table pointer is based on a different pointer and then we will not attempt to claim we know the type or the aliasing machinery invokes the callback only for the correct offset, because it can disambiguate between those based on the same thing. Does that make sense? (One further reason why I did not think about arrays that much is that we will currently never attempt to search for BINFOs if there are arrays involved in any way, though I understand we may change that in the future. BTW, I spent quite some time attempting to break this code on Thursday but did not succeed even when I removed the check 1 and the analysis produced clearly wrong results because of how we store the known type jump functions today and search for BINFOs only very much later on, checking the expected type is there at the expected offset in the type hierarchy of the type of the whole declaration. Of course, I understand the analysis has to be correct nevertheless and I tried to make it conservative.) Thanks, Martin > Richard. > > > > > >> > + if (TREE_CODE (obj) == MEM_REF) > >> > + obj = TREE_OPERAND (obj, 0); > >> > + if (TREE_CODE (obj) == ADDR_EXPR) > >> > + obj = TREE_OPERAND (obj, 0); > >> > + if (obj != analyzed_obj) > >> > + return NULL_TREE; > >> > + > >> > + t = gimple_assign_rhs1 (stmt); > >> > + if (TREE_CODE (t) != ADDR_EXPR) > >> > + return NULL_TREE; > >> > + t = get_base_address (TREE_OPERAND (t, 0)); > >> > >> Do we actually ever store sth else than the plain address of a > >> virtual table (thus, &decl)? If so, what difference makes the offset > >> into the virtual table we get in this way? I ask, because ... > >> > >> > + if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t)) > >> > + return NULL_TREE; > >> > + > >> > + return DECL_CONTEXT (t); > >> > >> ... DECL_CONTEXT (t) is of course independent of any offset. > >> > >> Thus I think you should drop the call to get_base_address () and > >> instead just look at TREE_OPERAND (t, 0). > > > > Even the simplest cases of assignments have basically a form like > > this: > > > > this_1(D)->_vptr.A = &MEM[(void *)&_ZTV1A + 8B]; > > > > so I need to extract the actual VAR_DECL somehow. But of course I can > > do that by looking through the MEM_REF and ADDR_EXPR by hand, if > > preferable. > > > >> > >> > +} > >> > + > >> > /* Callback of walk_aliased_vdefs and a helper function for > >> > detect_type_change to check whether a particular statement may modify > >> > the virtual table pointer, and if possible also determine the new type of > >> > @@ -352,6 +404,12 @@ check_stmt_for_type_change (ao_ref *ao A > >> > > >> > if (stmt_may_be_vtbl_ptr_store (stmt)) > >> > { > >> > + tree type; > >> > + type = extr_type_from_vtbl_ptr_store (stmt, tci->object); > >> > + if (tci->type_maybe_changed > >> > + && type != tci->known_current_type) > >> > + tci->multiple_types_encountered = true; > >> > + tci->known_current_type = type; > >> > tci->type_maybe_changed = true; > >> > return true; > >> > } > >> > @@ -359,19 +417,19 @@ check_stmt_for_type_change (ao_ref *ao A > >> > return false; > >> > } > >> > > >> > -/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by > >> > - looking for assignments to its virtual table pointer. If it is, return true > >> > - and fill in the jump function JFUNC with relevant type information or set it > >> > - to unknown. ARG is the object itself (not a pointer to it, unless > >> > - dereferenced). BASE is the base of the memory access as returned by > >> > - get_ref_base_and_extent, as is the offset. */ > >> > + > >> > + > >> > +/* Like detect_type_change but with extra argument COMP_TYPE which will become > >> > + the component type part of new JFUNC of dynamic type change is detected and > >> > + the new base type is identified. */ > >> > > >> > static bool > >> > -detect_type_change (tree arg, tree base, gimple call, > >> > - struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) > >> > +detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call, > >> > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) > >> > { > >> > struct type_change_info tci; > >> > ao_ref ao; > >> > + tree t; > >> > > >> > gcc_checking_assert (DECL_P (arg) > >> > || TREE_CODE (arg) == MEM_REF > >> > @@ -381,8 +439,6 @@ detect_type_change (tree arg, tree base, > >> > if (!flag_devirtualize || !gimple_vuse (call)) > >> > return false; > >> > > >> > - tci.type_maybe_changed = false; > >> > - > >> > ao.ref = arg; > >> > ao.base = base; > >> > ao.offset = offset; > >> > @@ -391,15 +447,51 @@ detect_type_change (tree arg, tree base, > >> > ao.ref_alias_set = -1; > >> > ao.base_alias_set = -1; > >> > > >> > + t = arg; > >> > + while (handled_component_p (t)) > >> > + t = TREE_OPERAND (t, 0); > >> > >> Here you are using handled_component_p, thus allow ARRAY_REFs ... > >> but you are not trying to distinguish a[1] from a[2] anywhere, so this > >> looks bogus and instead should look like the case above (with a comment > >> as to why looking at ARRAY_REFs would be bogus). > > > > I changed both to get_base_address as described above. > > > > This is the new version of the patch which I'm currently bootstrapping > > and testing on an x86_64-linux. OK for trunk if it passes? Thanks. > > > > Martin > > > > > > 2011-10-27 Martin Jambor <mjambor@suse.cz> > > > > * ipa-prop.c (type_change_info): New fields object, known_current_type > > and multiple_types_encountered. > > (extr_type_from_vtbl_ptr_store): New function. > > (check_stmt_for_type_change): Use it, set multiple_types_encountered if > > the result is different from the previous one. > > (detect_type_change): Renamed to detect_type_change_1. New parameter > > comp_type. Set up new fields in tci, build known type jump > > functions if the new type can be identified. > > (detect_type_change): New function. > > * tree.h (DECL_CONTEXT): Comment new use. > > > > * testsuite/g++.dg/ipa/devirt-c-1.C: Add dump scans. > > * testsuite/g++.dg/ipa/devirt-c-2.C: Likewise. > > * testsuite/g++.dg/ipa/devirt-c-7.C: New test. > > > > > > Index: src/gcc/ipa-prop.c > > =================================================================== > > --- src.orig/gcc/ipa-prop.c > > +++ src/gcc/ipa-prop.c > > @@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f) > > > > struct type_change_info > > { > > + /* The declaration or SSA_NAME pointer of the base that we are checking for > > + type change. */ > > + tree object; > > + /* If we actually can tell the type that the object has changed to, it is > > + stored in this field. Otherwise it remains NULL_TREE. */ > > + tree known_current_type; > > /* Set to true if dynamic type change has been detected. */ > > bool type_maybe_changed; > > + /* Set to true if multiple types have been encountered. known_current_type > > + must be disregarded in that case. */ > > + bool multiple_types_encountered; > > }; > > > > /* Return true if STMT can modify a virtual method table pointer. > > @@ -338,6 +347,44 @@ stmt_may_be_vtbl_ptr_store (gimple stmt) > > return true; > > } > > > > +/* If STMT can be proved to be an assignment to the virtual method table > > + pointer of ANALYZED_OBJ and the type associated with the new table > > + identified, return the type. Otherwise return NULL_TREE. */ > > + > > +static tree > > +extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj) > > +{ > > + tree lhs, t, obj; > > + > > + if (!gimple_assign_single_p (stmt)) > > + return NULL_TREE; > > + > > + lhs = gimple_assign_lhs (stmt); > > + > > + if (TREE_CODE (lhs) != COMPONENT_REF > > + || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))) > > + return NULL_TREE; > > + > > + obj = get_base_address (lhs); > > + if (TREE_CODE (obj) == MEM_REF) > > + { > > + if (TREE_CODE (analyzed_obj) != MEM_REF > > + || TREE_OPERAND (analyzed_obj, 0) != TREE_OPERAND (obj, 0)) > > + return NULL_TREE; > > + } > > + else if (analyzed_obj != obj) > > + return NULL_TREE; > > + > > + t = gimple_assign_rhs1 (stmt); > > + if (TREE_CODE (t) != ADDR_EXPR) > > + return NULL_TREE; > > + t = get_base_address (TREE_OPERAND (t, 0)); > > + if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t)) > > + return NULL_TREE; > > + > > + return DECL_CONTEXT (t); > > +} > > + > > /* Callback of walk_aliased_vdefs and a helper function for > > detect_type_change to check whether a particular statement may modify > > the virtual table pointer, and if possible also determine the new type of > > @@ -352,6 +399,12 @@ check_stmt_for_type_change (ao_ref *ao A > > > > if (stmt_may_be_vtbl_ptr_store (stmt)) > > { > > + tree type; > > + type = extr_type_from_vtbl_ptr_store (stmt, tci->object); > > + if (tci->type_maybe_changed > > + && type != tci->known_current_type) > > + tci->multiple_types_encountered = true; > > + tci->known_current_type = type; > > tci->type_maybe_changed = true; > > return true; > > } > > @@ -359,16 +412,15 @@ check_stmt_for_type_change (ao_ref *ao A > > return false; > > } > > > > -/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by > > - looking for assignments to its virtual table pointer. If it is, return true > > - and fill in the jump function JFUNC with relevant type information or set it > > - to unknown. ARG is the object itself (not a pointer to it, unless > > - dereferenced). BASE is the base of the memory access as returned by > > - get_ref_base_and_extent, as is the offset. */ > > + > > + > > +/* Like detect_type_change but with extra argument COMP_TYPE which will become > > + the component type part of new JFUNC of dynamic type change is detected and > > + the new base type is identified. */ > > > > static bool > > -detect_type_change (tree arg, tree base, gimple call, > > - struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) > > +detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call, > > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) > > { > > struct type_change_info tci; > > ao_ref ao; > > @@ -381,8 +433,6 @@ detect_type_change (tree arg, tree base, > > if (!flag_devirtualize || !gimple_vuse (call)) > > return false; > > > > - tci.type_maybe_changed = false; > > - > > ao.ref = arg; > > ao.base = base; > > ao.offset = offset; > > @@ -391,15 +441,44 @@ detect_type_change (tree arg, tree base, > > ao.ref_alias_set = -1; > > ao.base_alias_set = -1; > > > > + tci.object = get_base_address (arg); > > + tci.known_current_type = NULL_TREE; > > + tci.type_maybe_changed = false; > > + tci.multiple_types_encountered = false; > > + > > walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change, > > &tci, NULL); > > if (!tci.type_maybe_changed) > > return false; > > > > - jfunc->type = IPA_JF_UNKNOWN; > > + if (!tci.known_current_type > > + || tci.multiple_types_encountered > > + || offset != 0) > > + jfunc->type = IPA_JF_UNKNOWN; > > + else > > + { > > + jfunc->type = IPA_JF_KNOWN_TYPE; > > + jfunc->value.known_type.base_type = tci.known_current_type; > > + jfunc->value.known_type.component_type = comp_type; > > + } > > + > > return true; > > } > > > > +/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by > > + looking for assignments to its virtual table pointer. If it is, return true > > + and fill in the jump function JFUNC with relevant type information or set it > > + to unknown. ARG is the object itself (not a pointer to it, unless > > + dereferenced). BASE is the base of the memory access as returned by > > + get_ref_base_and_extent, as is the offset. */ > > + > > +static bool > > +detect_type_change (tree arg, tree base, gimple call, > > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) > > +{ > > + return detect_type_change_1 (arg, base, TREE_TYPE (arg), call, jfunc, offset); > > +} > > + > > /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer > > SSA name (its dereference will become the base and the offset is assumed to > > be zero). */ > > @@ -407,16 +486,19 @@ detect_type_change (tree arg, tree base, > > static bool > > detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc) > > { > > + tree comp_type; > > + > > gcc_checking_assert (TREE_CODE (arg) == SSA_NAME); > > if (!flag_devirtualize > > || !POINTER_TYPE_P (TREE_TYPE (arg)) > > || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE) > > return false; > > > > + comp_type = TREE_TYPE (TREE_TYPE (arg)); > > arg = build2 (MEM_REF, ptr_type_node, arg, > > - build_int_cst (ptr_type_node, 0)); > > + build_int_cst (ptr_type_node, 0)); > > > > - return detect_type_change (arg, arg, call, jfunc, 0); > > + return detect_type_change_1 (arg, arg, comp_type, call, jfunc, 0); > > } > > > > /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the > > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C > > =================================================================== > > --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-1.C > > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C > > @@ -1,7 +1,7 @@ > > /* Verify that ipa-cp correctly detects the dynamic type of an object > > under construction when doing devirtualization. */ > > /* { dg-do run } */ > > -/* { dg-options "-O3 -fno-early-inlining -fno-inline" } */ > > +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */ > > > > extern "C" void abort (void); > > > > @@ -69,3 +69,8 @@ int main (int argc, char *argv[]) > > bah (); > > return 0; > > } > > + > > +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo" "cp" } } */ > > +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */ > > +/* { dg-final { cleanup-ipa-dump "cp" } } */ > > +/* { dg-final { cleanup-tree-dump "optimized" } } */ > > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C > > =================================================================== > > --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-2.C > > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C > > @@ -1,7 +1,7 @@ > > /* Verify that ipa-cp correctly detects the dynamic type of an object > > under construction when doing devirtualization. */ > > /* { dg-do run } */ > > -/* { dg-options "-O3 -fno-early-inlining -fno-inline" } */ > > +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */ > > > > extern "C" void abort (void); > > > > @@ -77,3 +77,8 @@ int main (int argc, char *argv[]) > > bah (); > > return 0; > > } > > + > > +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo" "cp" } } */ > > +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */ > > +/* { dg-final { cleanup-ipa-dump "cp" } } */ > > +/* { dg-final { cleanup-tree-dump "optimized" } } */ > > Index: src/gcc/tree.h > > =================================================================== > > --- src.orig/gcc/tree.h > > +++ src/gcc/tree.h > > @@ -2678,7 +2678,9 @@ struct function; > > nodes, this points to either the FUNCTION_DECL for the containing > > function, the RECORD_TYPE or UNION_TYPE for the containing type, or > > NULL_TREE or a TRANSLATION_UNIT_DECL if the given decl has "file > > - scope". */ > > + scope". In particular, for VAR_DECLs which are virtual table pointers > > + (they have DECL_VIRTUAL set), we use DECL_CONTEXT to determine the type > > + they belong to. */ > > #define DECL_CONTEXT(NODE) (DECL_MINIMAL_CHECK (NODE)->decl_minimal.context) > > #define DECL_FIELD_CONTEXT(NODE) \ > > (FIELD_DECL_CHECK (NODE)->decl_minimal.context) > > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C > > =================================================================== > > --- /dev/null > > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C > > @@ -0,0 +1,87 @@ > > +/* Verify that ipa-cp will not get confused by placement new constructing an > > + object within another one when looking for dynamic type change . */ > > +/* { dg-do run } */ > > +/* { dg-options "-O3 -Wno-attributes" } */ > > + > > +extern "C" void abort (void); > > +namespace std { > > + typedef __SIZE_TYPE__ size_t; > > +} > > +inline void* __attribute__ ((always_inline)) > > +operator new(std::size_t, void* __p) throw() > > +{ > > + return __p; > > +} > > + > > +class A > > +{ > > +public: > > + char data[256]; > > + A(); > > + virtual int foo (int i); > > +}; > > + > > +class B : public A > > +{ > > +public: > > + virtual int foo (int i); > > +}; > > + > > +class C > > +{ > > +public: > > + C(); > > + virtual double foo (double i); > > +}; > > + > > +int A::foo (int i) > > +{ > > + return i + 1; > > +} > > + > > +int B::foo (int i) > > +{ > > + return i + 2; > > +} > > + > > +double C::foo (double i) > > +{ > > + return i + 3.5; > > +} > > + > > +static int __attribute__ ((noinline)) middleman (class A *obj, int i) > > +{ > > + return obj->foo (i); > > +} > > + > > +int __attribute__ ((noinline,noclone)) get_input(void) > > +{ > > + return 1; > > +} > > + > > +__attribute__ ((always_inline)) C::C () > > +{
On Mon, Oct 31, 2011 at 5:58 PM, Martin Jambor <mjambor@suse.cz> wrote: > On Fri, Oct 28, 2011 at 11:21:23AM +0200, Richard Guenther wrote: >> On Thu, Oct 27, 2011 at 9:54 PM, Martin Jambor <mjambor@suse.cz> wrote: >> > Hi, >> > >> > On Thu, Oct 27, 2011 at 11:06:02AM +0200, Richard Guenther wrote: >> >> On Thu, Oct 27, 2011 at 1:22 AM, Martin Jambor <mjambor@suse.cz> wrote: >> >> > Hi, >> >> > >> >> > I've been asked by Maxim Kuvyrkov to revive the following patch which >> >> > has not made it to 4.6. Currently, when type based devirtualization >> >> > detects a potential type change, it simply gives up on gathering any >> >> > information on the object in question. This patch adds an attempt to >> >> > actually detect the new type after the change. >> >> > >> >> > Maxim claimed this (and another patch I'll post tomorrow) noticeably >> >> > improved performance of some real code. I can only offer a rather >> >> > artificial example in the attachment. When the constructors are >> >> > inlined but the function multiply_matrices is not, this patch makes >> >> > the produced executable run for only 7 seconds instead of about 20 on >> >> > my 4 year old i686 desktop (with -Ofast). >> >> > >> >> > Anyway, the patch passes bootstrap and testsuite on x86_64-linux. >> >> > What do you think, is it a good idea for trunk now? >> >> > >> >> > Thanks, >> >> > >> >> > Martin >> >> > >> >> > >> >> > 2011-10-21 Martin Jambor <mjambor@suse.cz> >> >> > >> >> > * ipa-prop.c (type_change_info): New fields object, known_current_type >> >> > and multiple_types_encountered. >> >> > (extr_type_from_vtbl_ptr_store): New function. >> >> > (check_stmt_for_type_change): Use it, set multiple_types_encountered if >> >> > the result is different from the previous one. >> >> > (detect_type_change): Renamed to detect_type_change_1. New parameter >> >> > comp_type. Set up new fields in tci, build known type jump >> >> > functions if the new type can be identified. >> >> > (detect_type_change): New function. >> >> > * tree.h (DECL_CONTEXT): Comment new use. >> >> > >> >> > * testsuite/g++.dg/ipa/devirt-c-1.C: Add dump scans. >> >> > * testsuite/g++.dg/ipa/devirt-c-2.C: Likewise. >> >> > * testsuite/g++.dg/ipa/devirt-c-7.C: New test. >> >> > >> >> > >> >> > Index: src/gcc/ipa-prop.c >> >> > =================================================================== >> >> > --- src.orig/gcc/ipa-prop.c >> >> > +++ src/gcc/ipa-prop.c >> >> > @@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f) >> >> > >> >> > struct type_change_info >> >> > { >> >> > + /* The declaration or SSA_NAME pointer of the base that we are checking for >> >> > + type change. */ >> >> > + tree object; >> >> > + /* If we actually can tell the type that the object has changed to, it is >> >> > + stored in this field. Otherwise it remains NULL_TREE. */ >> >> > + tree known_current_type; >> >> > /* Set to true if dynamic type change has been detected. */ >> >> > bool type_maybe_changed; >> >> > + /* Set to true if multiple types have been encountered. known_current_type >> >> > + must be disregarded in that case. */ >> >> > + bool multiple_types_encountered; >> >> > }; >> >> > >> >> > /* Return true if STMT can modify a virtual method table pointer. >> >> > @@ -338,6 +347,49 @@ stmt_may_be_vtbl_ptr_store (gimple stmt) >> >> > return true; >> >> > } >> >> > >> >> > +/* If STMT can be proved to be an assignment to the virtual method table >> >> > + pointer of ANALYZED_OBJ and the type associated with the new table >> >> > + identified, return the type. Otherwise return NULL_TREE. */ >> >> > + >> >> > +static tree >> >> > +extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj) >> >> > +{ >> >> > + tree lhs, t, obj; >> >> > + >> >> > + if (!is_gimple_assign (stmt)) >> >> >> >> gimple_assign_single_p (stmt) >> > >> > OK. >> > >> >> >> >> > + return NULL_TREE; >> >> > + >> >> > + lhs = gimple_assign_lhs (stmt); >> >> > + >> >> > + if (TREE_CODE (lhs) != COMPONENT_REF) >> >> > + return NULL_TREE; >> >> > + obj = lhs; >> >> > + >> >> > + if (!DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))) >> >> > + return NULL_TREE; >> >> > + >> >> > + do >> >> > + { >> >> > + obj = TREE_OPERAND (obj, 0); >> >> > + } >> >> > + while (TREE_CODE (obj) == COMPONENT_REF); >> >> >> >> You do not allow other components than component-refs (thus, for >> >> example an ARRAY_REF - that is for a reason?). Please add >> >> a comment why. Otherwise this whole sequence would look like >> >> it should be replaceable by get_base_address (obj). >> >> >> > >> > I guess I might have been overly conservative here, ARRAY_REFs are >> > fine. get_base_address only digs into MEM_REFs if they are based on >> > an ADDR_EXPR while I do so always. But I can check that either both >> > obj and analyzed_obj are a MEM_REF of the same SSA_NAME or they are >> > the same thing (i.e. the same decl)... which even feels a bit cleaner, >> > so I did that. >> >> Well, as you are looking for a must-change-type pattern I think you cannot >> simply ignore offsets. Consider >> >> T a[10]; >> >> new (T') (&a[9]); >> a[8]->foo(); >> >> where the must-type-change on a[9] is _not_ changing the type of a[8]! >> >> Similar cases might happen with >> >> class Compound { T a; T b; }; >> >> no? >> >> Please think about the difference must vs. may-type-change for these >> cases. I'm not convinced that the must-type-change code is correct. >> > > I did, even though it's not always easy because the patch is so old. > However, the reasoning is as follows: > > 1) The callback will never report a known type if the "base address" > of the RHS of the assignment is not exactly the same declaration or > a MEM_REF of exactly the same SSA name. > > 2) The aliasing machinery is initialized to exactly the offset we are > interested in and the size of one pointer: > > ao.offset = offset; > ao.size = POINTER_SIZE; > > So, either the access which can alter the virtual table pointer is > based on a different pointer and then we will not attempt to claim we > know the type or the aliasing machinery invokes the callback only for > the correct offset, because it can disambiguate between those based on > the same thing. Does that make sense? Not for the latter - the alias machinery reports may-aliases, thus if you ask for [32, 36] then the alias machinery will invoke the callback for a[i].vptr as well (the access with a variable offset makes it [0, -1U], thus coverting [32, 46]). You have to check for a must-alias relationship explicitely, which you cannot with the information you have, once a possibly variable offset component is visited. Note that the alias machinery may validly invoke your callback for all stores, even those that trivially do not alias - saying they may-alias is still correct. > (One further reason why I did not think about arrays that much is that > we will currently never attempt to search for BINFOs if there are > arrays involved in any way, though I understand we may change that in > the future. BTW, I spent quite some time attempting to break this > code on Thursday but did not succeed even when I removed the check 1 > and the analysis produced clearly wrong results because of how we > store the known type jump functions today and search for BINFOs only > very much later on, checking the expected type is there at the > expected offset in the type hierarchy of the type of the whole > declaration. Of course, I understand the analysis has to be correct > nevertheless and I tried to make it conservative.) So I think you should explicitely not handle all variable-offset components and pass down the actual offset of the pointer to the walker callback so it can verify that the offsets match. Richard. > Thanks, > > Martin > > > >> Richard. >> >> >> > >> >> > + if (TREE_CODE (obj) == MEM_REF) >> >> > + obj = TREE_OPERAND (obj, 0); >> >> > + if (TREE_CODE (obj) == ADDR_EXPR) >> >> > + obj = TREE_OPERAND (obj, 0); >> >> > + if (obj != analyzed_obj) >> >> > + return NULL_TREE; >> >> > + >> >> > + t = gimple_assign_rhs1 (stmt); >> >> > + if (TREE_CODE (t) != ADDR_EXPR) >> >> > + return NULL_TREE; >> >> > + t = get_base_address (TREE_OPERAND (t, 0)); >> >> >> >> Do we actually ever store sth else than the plain address of a >> >> virtual table (thus, &decl)? If so, what difference makes the offset >> >> into the virtual table we get in this way? I ask, because ... >> >> >> >> > + if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t)) >> >> > + return NULL_TREE; >> >> > + >> >> > + return DECL_CONTEXT (t); >> >> >> >> ... DECL_CONTEXT (t) is of course independent of any offset. >> >> >> >> Thus I think you should drop the call to get_base_address () and >> >> instead just look at TREE_OPERAND (t, 0). >> > >> > Even the simplest cases of assignments have basically a form like >> > this: >> > >> > this_1(D)->_vptr.A = &MEM[(void *)&_ZTV1A + 8B]; >> > >> > so I need to extract the actual VAR_DECL somehow. But of course I can >> > do that by looking through the MEM_REF and ADDR_EXPR by hand, if >> > preferable. >> > >> >> >> >> > +} >> >> > + >> >> > /* Callback of walk_aliased_vdefs and a helper function for >> >> > detect_type_change to check whether a particular statement may modify >> >> > the virtual table pointer, and if possible also determine the new type of >> >> > @@ -352,6 +404,12 @@ check_stmt_for_type_change (ao_ref *ao A >> >> > >> >> > if (stmt_may_be_vtbl_ptr_store (stmt)) >> >> > { >> >> > + tree type; >> >> > + type = extr_type_from_vtbl_ptr_store (stmt, tci->object); >> >> > + if (tci->type_maybe_changed >> >> > + && type != tci->known_current_type) >> >> > + tci->multiple_types_encountered = true; >> >> > + tci->known_current_type = type; >> >> > tci->type_maybe_changed = true; >> >> > return true; >> >> > } >> >> > @@ -359,19 +417,19 @@ check_stmt_for_type_change (ao_ref *ao A >> >> > return false; >> >> > } >> >> > >> >> > -/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by >> >> > - looking for assignments to its virtual table pointer. If it is, return true >> >> > - and fill in the jump function JFUNC with relevant type information or set it >> >> > - to unknown. ARG is the object itself (not a pointer to it, unless >> >> > - dereferenced). BASE is the base of the memory access as returned by >> >> > - get_ref_base_and_extent, as is the offset. */ >> >> > + >> >> > + >> >> > +/* Like detect_type_change but with extra argument COMP_TYPE which will become >> >> > + the component type part of new JFUNC of dynamic type change is detected and >> >> > + the new base type is identified. */ >> >> > >> >> > static bool >> >> > -detect_type_change (tree arg, tree base, gimple call, >> >> > - struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) >> >> > +detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call, >> >> > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) >> >> > { >> >> > struct type_change_info tci; >> >> > ao_ref ao; >> >> > + tree t; >> >> > >> >> > gcc_checking_assert (DECL_P (arg) >> >> > || TREE_CODE (arg) == MEM_REF >> >> > @@ -381,8 +439,6 @@ detect_type_change (tree arg, tree base, >> >> > if (!flag_devirtualize || !gimple_vuse (call)) >> >> > return false; >> >> > >> >> > - tci.type_maybe_changed = false; >> >> > - >> >> > ao.ref = arg; >> >> > ao.base = base; >> >> > ao.offset = offset; >> >> > @@ -391,15 +447,51 @@ detect_type_change (tree arg, tree base, >> >> > ao.ref_alias_set = -1; >> >> > ao.base_alias_set = -1; >> >> > >> >> > + t = arg; >> >> > + while (handled_component_p (t)) >> >> > + t = TREE_OPERAND (t, 0); >> >> >> >> Here you are using handled_component_p, thus allow ARRAY_REFs ... >> >> but you are not trying to distinguish a[1] from a[2] anywhere, so this >> >> looks bogus and instead should look like the case above (with a comment >> >> as to why looking at ARRAY_REFs would be bogus). >> > >> > I changed both to get_base_address as described above. >> > >> > This is the new version of the patch which I'm currently bootstrapping >> > and testing on an x86_64-linux. OK for trunk if it passes? Thanks. >> > >> > Martin >> > >> > >> > 2011-10-27 Martin Jambor <mjambor@suse.cz> >> > >> > * ipa-prop.c (type_change_info): New fields object, known_current_type >> > and multiple_types_encountered. >> > (extr_type_from_vtbl_ptr_store): New function. >> > (check_stmt_for_type_change): Use it, set multiple_types_encountered if >> > the result is different from the previous one. >> > (detect_type_change): Renamed to detect_type_change_1. New parameter >> > comp_type. Set up new fields in tci, build known type jump >> > functions if the new type can be identified. >> > (detect_type_change): New function. >> > * tree.h (DECL_CONTEXT): Comment new use. >> > >> > * testsuite/g++.dg/ipa/devirt-c-1.C: Add dump scans. >> > * testsuite/g++.dg/ipa/devirt-c-2.C: Likewise. >> > * testsuite/g++.dg/ipa/devirt-c-7.C: New test. >> > >> > >> > Index: src/gcc/ipa-prop.c >> > =================================================================== >> > --- src.orig/gcc/ipa-prop.c >> > +++ src/gcc/ipa-prop.c >> > @@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f) >> > >> > struct type_change_info >> > { >> > + /* The declaration or SSA_NAME pointer of the base that we are checking for >> > + type change. */ >> > + tree object; >> > + /* If we actually can tell the type that the object has changed to, it is >> > + stored in this field. Otherwise it remains NULL_TREE. */ >> > + tree known_current_type; >> > /* Set to true if dynamic type change has been detected. */ >> > bool type_maybe_changed; >> > + /* Set to true if multiple types have been encountered. known_current_type >> > + must be disregarded in that case. */ >> > + bool multiple_types_encountered; >> > }; >> > >> > /* Return true if STMT can modify a virtual method table pointer. >> > @@ -338,6 +347,44 @@ stmt_may_be_vtbl_ptr_store (gimple stmt) >> > return true; >> > } >> > >> > +/* If STMT can be proved to be an assignment to the virtual method table >> > + pointer of ANALYZED_OBJ and the type associated with the new table >> > + identified, return the type. Otherwise return NULL_TREE. */ >> > + >> > +static tree >> > +extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj) >> > +{ >> > + tree lhs, t, obj; >> > + >> > + if (!gimple_assign_single_p (stmt)) >> > + return NULL_TREE; >> > + >> > + lhs = gimple_assign_lhs (stmt); >> > + >> > + if (TREE_CODE (lhs) != COMPONENT_REF >> > + || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))) >> > + return NULL_TREE; >> > + >> > + obj = get_base_address (lhs); >> > + if (TREE_CODE (obj) == MEM_REF) >> > + { >> > + if (TREE_CODE (analyzed_obj) != MEM_REF >> > + || TREE_OPERAND (analyzed_obj, 0) != TREE_OPERAND (obj, 0)) >> > + return NULL_TREE; >> > + } >> > + else if (analyzed_obj != obj) >> > + return NULL_TREE; >> > + >> > + t = gimple_assign_rhs1 (stmt); >> > + if (TREE_CODE (t) != ADDR_EXPR) >> > + return NULL_TREE; >> > + t = get_base_address (TREE_OPERAND (t, 0)); >> > + if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t)) >> > + return NULL_TREE; >> > + >> > + return DECL_CONTEXT (t); >> > +} >> > + >> > /* Callback of walk_aliased_vdefs and a helper function for >> > detect_type_change to check whether a particular statement may modify >> > the virtual table pointer, and if possible also determine the new type of >> > @@ -352,6 +399,12 @@ check_stmt_for_type_change (ao_ref *ao A >> > >> > if (stmt_may_be_vtbl_ptr_store (stmt)) >> > { >> > + tree type; >> > + type = extr_type_from_vtbl_ptr_store (stmt, tci->object); >> > + if (tci->type_maybe_changed >> > + && type != tci->known_current_type) >> > + tci->multiple_types_encountered = true; >> > + tci->known_current_type = type; >> > tci->type_maybe_changed = true; >> > return true; >> > } >> > @@ -359,16 +412,15 @@ check_stmt_for_type_change (ao_ref *ao A >> > return false; >> > } >> > >> > -/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by >> > - looking for assignments to its virtual table pointer. If it is, return true >> > - and fill in the jump function JFUNC with relevant type information or set it >> > - to unknown. ARG is the object itself (not a pointer to it, unless >> > - dereferenced). BASE is the base of the memory access as returned by >> > - get_ref_base_and_extent, as is the offset. */ >> > + >> > + >> > +/* Like detect_type_change but with extra argument COMP_TYPE which will become >> > + the component type part of new JFUNC of dynamic type change is detected and >> > + the new base type is identified. */ >> > >> > static bool >> > -detect_type_change (tree arg, tree base, gimple call, >> > - struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) >> > +detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call, >> > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) >> > { >> > struct type_change_info tci; >> > ao_ref ao; >> > @@ -381,8 +433,6 @@ detect_type_change (tree arg, tree base, >> > if (!flag_devirtualize || !gimple_vuse (call)) >> > return false; >> > >> > - tci.type_maybe_changed = false; >> > - >> > ao.ref = arg; >> > ao.base = base; >> > ao.offset = offset; >> > @@ -391,15 +441,44 @@ detect_type_change (tree arg, tree base, >> > ao.ref_alias_set = -1; >> > ao.base_alias_set = -1; >> > >> > + tci.object = get_base_address (arg); >> > + tci.known_current_type = NULL_TREE; >> > + tci.type_maybe_changed = false; >> > + tci.multiple_types_encountered = false; >> > + >> > walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change, >> > &tci, NULL); >> > if (!tci.type_maybe_changed) >> > return false; >> > >> > - jfunc->type = IPA_JF_UNKNOWN; >> > + if (!tci.known_current_type >> > + || tci.multiple_types_encountered >> > + || offset != 0) >> > + jfunc->type = IPA_JF_UNKNOWN; >> > + else >> > + { >> > + jfunc->type = IPA_JF_KNOWN_TYPE; >> > + jfunc->value.known_type.base_type = tci.known_current_type; >> > + jfunc->value.known_type.component_type = comp_type; >> > + } >> > + >> > return true; >> > } >> > >> > +/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by >> > + looking for assignments to its virtual table pointer. If it is, return true >> > + and fill in the jump function JFUNC with relevant type information or set it >> > + to unknown. ARG is the object itself (not a pointer to it, unless >> > + dereferenced). BASE is the base of the memory access as returned by >> > + get_ref_base_and_extent, as is the offset. */ >> > + >> > +static bool >> > +detect_type_change (tree arg, tree base, gimple call, >> > + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) >> > +{ >> > + return detect_type_change_1 (arg, base, TREE_TYPE (arg), call, jfunc, offset); >> > +} >> > + >> > /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer >> > SSA name (its dereference will become the base and the offset is assumed to >> > be zero). */ >> > @@ -407,16 +486,19 @@ detect_type_change (tree arg, tree base, >> > static bool >> > detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc) >> > { >> > + tree comp_type; >> > + >> > gcc_checking_assert (TREE_CODE (arg) == SSA_NAME); >> > if (!flag_devirtualize >> > || !POINTER_TYPE_P (TREE_TYPE (arg)) >> > || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE) >> > return false; >> > >> > + comp_type = TREE_TYPE (TREE_TYPE (arg)); >> > arg = build2 (MEM_REF, ptr_type_node, arg, >> > - build_int_cst (ptr_type_node, 0)); >> > + build_int_cst (ptr_type_node, 0)); >> > >> > - return detect_type_change (arg, arg, call, jfunc, 0); >> > + return detect_type_change_1 (arg, arg, comp_type, call, jfunc, 0); >> > } >> > >> > /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the >> > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C >> > =================================================================== >> > --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-1.C >> > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C >> > @@ -1,7 +1,7 @@ >> > /* Verify that ipa-cp correctly detects the dynamic type of an object >> > under construction when doing devirtualization. */ >> > /* { dg-do run } */ >> > -/* { dg-options "-O3 -fno-early-inlining -fno-inline" } */ >> > +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */ >> > >> > extern "C" void abort (void); >> > >> > @@ -69,3 +69,8 @@ int main (int argc, char *argv[]) >> > bah (); >> > return 0; >> > } >> > + >> > +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo" "cp" } } */ >> > +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */ >> > +/* { dg-final { cleanup-ipa-dump "cp" } } */ >> > +/* { dg-final { cleanup-tree-dump "optimized" } } */ >> > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C >> > =================================================================== >> > --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-2.C >> > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C >> > @@ -1,7 +1,7 @@ >> > /* Verify that ipa-cp correctly detects the dynamic type of an object >> > under construction when doing devirtualization. */ >> > /* { dg-do run } */ >> > -/* { dg-options "-O3 -fno-early-inlining -fno-inline" } */ >> > +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */ >> > >> > extern "C" void abort (void); >> > >> > @@ -77,3 +77,8 @@ int main (int argc, char *argv[]) >> > bah (); >> > return 0; >> > } >> > + >> > +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo" "cp" } } */ >> > +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */ >> > +/* { dg-final { cleanup-ipa-dump "cp" } } */ >> > +/* { dg-final { cleanup-tree-dump "optimized" } } */ >> > Index: src/gcc/tree.h >> > =================================================================== >> > --- src.orig/gcc/tree.h >> > +++ src/gcc/tree.h >> > @@ -2678,7 +2678,9 @@ struct function; >> > nodes, this points to either the FUNCTION_DECL for the containing >> > function, the RECORD_TYPE or UNION_TYPE for the containing type, or >> > NULL_TREE or a TRANSLATION_UNIT_DECL if the given decl has "file >> > - scope". */ >> > + scope". In particular, for VAR_DECLs which are virtual table pointers >> > + (they have DECL_VIRTUAL set), we use DECL_CONTEXT to determine the type >> > + they belong to. */ >> > #define DECL_CONTEXT(NODE) (DECL_MINIMAL_CHECK (NODE)->decl_minimal.context) >> > #define DECL_FIELD_CONTEXT(NODE) \ >> > (FIELD_DECL_CHECK (NODE)->decl_minimal.context) >> > Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C >> > =================================================================== >> > --- /dev/null >> > +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C >> > @@ -0,0 +1,87 @@ >> > +/* Verify that ipa-cp will not get confused by placement new constructing an >> > + object within another one when looking for dynamic type change . */ >> > +/* { dg-do run } */ >> > +/* { dg-options "-O3 -Wno-attributes" } */ >> > + >> > +extern "C" void abort (void); >> > +namespace std { >> > + typedef __SIZE_TYPE__ size_t; >> > +} >> > +inline void* __attribute__ ((always_inline)) >> > +operator new(std::size_t, void* __p) throw() >> > +{ >> > + return __p; >> > +} >> > + >> > +class A >> > +{ >> > +public: >> > + char data[256]; >> > + A(); >> > + virtual int foo (int i); >> > +}; >> > + >> > +class B : public A >> > +{ >> > +public: >> > + virtual int foo (int i); >> > +}; >> > + >> > +class C >> > +{ >> > +public: >> > + C(); >> > + virtual double foo (double i); >> > +}; >> > + >> > +int A::foo (int i) >> > +{ >> > + return i + 1; >> > +} >> > + >> > +int B::foo (int i) >> > +{ >> > + return i + 2; >> > +} >> > + >> > +double C::foo (double i) >> > +{ >> > + return i + 3.5; >> > +} >> > + >> > +static int __attribute__ ((noinline)) middleman (class A *obj, int i) >> > +{ >> > + return obj->foo (i); >> > +} >> > + >> > +int __attribute__ ((noinline,noclone)) get_input(void) >> > +{ >> > + return 1; >> > +} >> > + >> > +__attribute__ ((always_inline)) C::C () >> > +{ >
Index: src/gcc/ipa-prop.c =================================================================== --- src.orig/gcc/ipa-prop.c +++ src/gcc/ipa-prop.c @@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f) struct type_change_info { + /* The declaration or SSA_NAME pointer of the base that we are checking for + type change. */ + tree object; + /* If we actually can tell the type that the object has changed to, it is + stored in this field. Otherwise it remains NULL_TREE. */ + tree known_current_type; /* Set to true if dynamic type change has been detected. */ bool type_maybe_changed; + /* Set to true if multiple types have been encountered. known_current_type + must be disregarded in that case. */ + bool multiple_types_encountered; }; /* Return true if STMT can modify a virtual method table pointer. @@ -338,6 +347,44 @@ stmt_may_be_vtbl_ptr_store (gimple stmt) return true; } +/* If STMT can be proved to be an assignment to the virtual method table + pointer of ANALYZED_OBJ and the type associated with the new table + identified, return the type. Otherwise return NULL_TREE. */ + +static tree +extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj) +{ + tree lhs, t, obj; + + if (!gimple_assign_single_p (stmt)) + return NULL_TREE; + + lhs = gimple_assign_lhs (stmt); + + if (TREE_CODE (lhs) != COMPONENT_REF + || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))) + return NULL_TREE; + + obj = get_base_address (lhs); + if (TREE_CODE (obj) == MEM_REF) + { + if (TREE_CODE (analyzed_obj) != MEM_REF + || TREE_OPERAND (analyzed_obj, 0) != TREE_OPERAND (obj, 0)) + return NULL_TREE; + } + else if (analyzed_obj != obj) + return NULL_TREE; + + t = gimple_assign_rhs1 (stmt); + if (TREE_CODE (t) != ADDR_EXPR) + return NULL_TREE; + t = get_base_address (TREE_OPERAND (t, 0)); + if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t)) + return NULL_TREE; + + return DECL_CONTEXT (t); +} + /* Callback of walk_aliased_vdefs and a helper function for detect_type_change to check whether a particular statement may modify the virtual table pointer, and if possible also determine the new type of @@ -352,6 +399,12 @@ check_stmt_for_type_change (ao_ref *ao A if (stmt_may_be_vtbl_ptr_store (stmt)) { + tree type; + type = extr_type_from_vtbl_ptr_store (stmt, tci->object); + if (tci->type_maybe_changed + && type != tci->known_current_type) + tci->multiple_types_encountered = true; + tci->known_current_type = type; tci->type_maybe_changed = true; return true; } @@ -359,16 +412,15 @@ check_stmt_for_type_change (ao_ref *ao A return false; } -/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by - looking for assignments to its virtual table pointer. If it is, return true - and fill in the jump function JFUNC with relevant type information or set it - to unknown. ARG is the object itself (not a pointer to it, unless - dereferenced). BASE is the base of the memory access as returned by - get_ref_base_and_extent, as is the offset. */ + + +/* Like detect_type_change but with extra argument COMP_TYPE which will become + the component type part of new JFUNC of dynamic type change is detected and + the new base type is identified. */ static bool -detect_type_change (tree arg, tree base, gimple call, - struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) +detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call, + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) { struct type_change_info tci; ao_ref ao; @@ -381,8 +433,6 @@ detect_type_change (tree arg, tree base, if (!flag_devirtualize || !gimple_vuse (call)) return false; - tci.type_maybe_changed = false; - ao.ref = arg; ao.base = base; ao.offset = offset; @@ -391,15 +441,44 @@ detect_type_change (tree arg, tree base, ao.ref_alias_set = -1; ao.base_alias_set = -1; + tci.object = get_base_address (arg); + tci.known_current_type = NULL_TREE; + tci.type_maybe_changed = false; + tci.multiple_types_encountered = false; + walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change, &tci, NULL); if (!tci.type_maybe_changed) return false; - jfunc->type = IPA_JF_UNKNOWN; + if (!tci.known_current_type + || tci.multiple_types_encountered + || offset != 0) + jfunc->type = IPA_JF_UNKNOWN; + else + { + jfunc->type = IPA_JF_KNOWN_TYPE; + jfunc->value.known_type.base_type = tci.known_current_type; + jfunc->value.known_type.component_type = comp_type; + } + return true; } +/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by + looking for assignments to its virtual table pointer. If it is, return true + and fill in the jump function JFUNC with relevant type information or set it + to unknown. ARG is the object itself (not a pointer to it, unless + dereferenced). BASE is the base of the memory access as returned by + get_ref_base_and_extent, as is the offset. */ + +static bool +detect_type_change (tree arg, tree base, gimple call, + struct ipa_jump_func *jfunc, HOST_WIDE_INT offset) +{ + return detect_type_change_1 (arg, base, TREE_TYPE (arg), call, jfunc, offset); +} + /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer SSA name (its dereference will become the base and the offset is assumed to be zero). */ @@ -407,16 +486,19 @@ detect_type_change (tree arg, tree base, static bool detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc) { + tree comp_type; + gcc_checking_assert (TREE_CODE (arg) == SSA_NAME); if (!flag_devirtualize || !POINTER_TYPE_P (TREE_TYPE (arg)) || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE) return false; + comp_type = TREE_TYPE (TREE_TYPE (arg)); arg = build2 (MEM_REF, ptr_type_node, arg, - build_int_cst (ptr_type_node, 0)); + build_int_cst (ptr_type_node, 0)); - return detect_type_change (arg, arg, call, jfunc, 0); + return detect_type_change_1 (arg, arg, comp_type, call, jfunc, 0); } /* Callback of walk_aliased_vdefs. Flags that it has been invoked to the Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C =================================================================== --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-1.C +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C @@ -1,7 +1,7 @@ /* Verify that ipa-cp correctly detects the dynamic type of an object under construction when doing devirtualization. */ /* { dg-do run } */ -/* { dg-options "-O3 -fno-early-inlining -fno-inline" } */ +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */ extern "C" void abort (void); @@ -69,3 +69,8 @@ int main (int argc, char *argv[]) bah (); return 0; } + +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo" "cp" } } */ +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */ +/* { dg-final { cleanup-ipa-dump "cp" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C =================================================================== --- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-2.C +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C @@ -1,7 +1,7 @@ /* Verify that ipa-cp correctly detects the dynamic type of an object under construction when doing devirtualization. */ /* { dg-do run } */ -/* { dg-options "-O3 -fno-early-inlining -fno-inline" } */ +/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized" } */ extern "C" void abort (void); @@ -77,3 +77,8 @@ int main (int argc, char *argv[]) bah (); return 0; } + +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo" "cp" } } */ +/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */ +/* { dg-final { cleanup-ipa-dump "cp" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ Index: src/gcc/tree.h =================================================================== --- src.orig/gcc/tree.h +++ src/gcc/tree.h @@ -2678,7 +2678,9 @@ struct function; nodes, this points to either the FUNCTION_DECL for the containing function, the RECORD_TYPE or UNION_TYPE for the containing type, or NULL_TREE or a TRANSLATION_UNIT_DECL if the given decl has "file - scope". */ + scope". In particular, for VAR_DECLs which are virtual table pointers + (they have DECL_VIRTUAL set), we use DECL_CONTEXT to determine the type + they belong to. */ #define DECL_CONTEXT(NODE) (DECL_MINIMAL_CHECK (NODE)->decl_minimal.context) #define DECL_FIELD_CONTEXT(NODE) \ (FIELD_DECL_CHECK (NODE)->decl_minimal.context) Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C =================================================================== --- /dev/null +++ src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C @@ -0,0 +1,87 @@ +/* Verify that ipa-cp will not get confused by placement new constructing an + object within another one when looking for dynamic type change . */ +/* { dg-do run } */ +/* { dg-options "-O3 -Wno-attributes" } */ + +extern "C" void abort (void); +namespace std { + typedef __SIZE_TYPE__ size_t; +} +inline void* __attribute__ ((always_inline)) +operator new(std::size_t, void* __p) throw() +{ + return __p; +} + +class A +{ +public: + char data[256]; + A(); + virtual int foo (int i); +}; + +class B : public A +{ +public: + virtual int foo (int i); +}; + +class C +{ +public: + C(); + virtual double foo (double i); +}; + +int A::foo (int i) +{ + return i + 1; +} + +int B::foo (int i) +{ + return i + 2; +} + +double C::foo (double i) +{ + return i + 3.5; +} + +static int __attribute__ ((noinline)) middleman (class A *obj, int i) +{ + return obj->foo (i); +} + +int __attribute__ ((noinline,noclone)) get_input(void) +{ + return 1; +} + +__attribute__ ((always_inline)) C::C () +{ +} + +A::A () +{ +} + +static __attribute__ ((noinline)) void bah () +{ + class B b; + + C *c = new ((void *) &b.data) C; + + if (middleman (&b, get_input ()) != 3) + abort (); +} + +int main (int argc, char *argv[]) +{ + int i; + + for (i = 0; i < 10; i++) + bah (); + return 0; +}