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.
> > + 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 <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,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;
+}
