Hi,
On Tue, Nov 01, 2011 at 10:37:10AM +0100, Richard Guenther wrote:
> On Mon, Oct 31, 2011 at 5:58 PM, Martin Jambor <mjam...@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 <mjam...@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 <mjam...@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 <mjam...@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.
>
Fair enough, I did not take into account variable offsets. This is
the updated patch, re-bootstrapped and re-tested on x86_64-linux
without any issues.
Thanks,
Martin
2011-11-01 Martin Jambor <mjam...@suse.cz>
* ipa-prop.c (type_change_info): New fields offset, 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.
* testsuite/g++.dg/ipa/devirt-c-8.C: Likewise.
Index: src/gcc/ipa-prop.c
===================================================================
--- src.orig/gcc/ipa-prop.c
+++ src/gcc/ipa-prop.c
@@ -271,8 +271,20 @@ ipa_print_all_jump_functions (FILE *f)
struct type_change_info
{
+ /* Offset into the object where there is the virtual method pointer we are
+ looking for. */
+ HOST_WIDE_INT offset;
+ /* 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 +350,48 @@ 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, struct type_change_info *tci)
+{
+ HOST_WIDE_INT offset, size, max_size;
+ tree lhs, rhs, base;
+
+ if (!gimple_assign_single_p (stmt))
+ return NULL_TREE;
+
+ lhs = gimple_assign_lhs (stmt);
+ rhs = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (lhs) != COMPONENT_REF
+ || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
+ || TREE_CODE (rhs) != ADDR_EXPR)
+ return NULL_TREE;
+ rhs = get_base_address (TREE_OPERAND (rhs, 0));
+ if (!rhs
+ || TREE_CODE (rhs) != VAR_DECL
+ || !DECL_VIRTUAL_P (rhs))
+ return NULL_TREE;
+
+ base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
+ if (offset != tci->offset
+ || size != POINTER_SIZE
+ || max_size != POINTER_SIZE)
+ return NULL_TREE;
+ if (TREE_CODE (base) == MEM_REF)
+ {
+ if (TREE_CODE (tci->object) != MEM_REF
+ || TREE_OPERAND (tci->object, 0) != TREE_OPERAND (base, 0))
+ return NULL_TREE;
+ }
+ else if (tci->object != base)
+ return NULL_TREE;
+
+ return DECL_CONTEXT (rhs);
+}
+
/* 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 +406,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);
+ 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 +419,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 +440,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 +448,45 @@ detect_type_change (tree arg, tree base,
ao.ref_alias_set = -1;
ao.base_alias_set = -1;
+ tci.offset = offset;
+ 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 +494,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
@@ -2685,7 +2685,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;
+}
Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-8.C
===================================================================
--- /dev/null
+++ src/gcc/testsuite/g++.dg/ipa/devirt-c-8.C
@@ -0,0 +1,82 @@
+/* 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 -fdump-ipa-cp
-fdump-tree-optimized" } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+ int data;
+ A();
+ virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+ B();
+ virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+ virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+ return i + 1;
+}
+
+int B::foo (int i)
+{
+ return i + 2;
+}
+
+int C::foo (int i)
+{
+ return i + 3;
+}
+
+static int __attribute__ ((noinline))
+middleman (class A *obj, int i)
+{
+ return obj->foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+ return 1;
+}
+
+inline __attribute__ ((always_inline)) A::A ()
+{
+ if (middleman (this, get_input ()) != 2)
+ abort ();
+}
+
+inline __attribute__ ((always_inline)) B::B ()
+{
+}
+
+static void bah ()
+{
+ class B b;
+}
+
+int main (int argc, char *argv[])
+{
+ int i;
+
+ for (i = 0; i < 10; i++)
+ 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" } } */
