On Tue, Nov 1, 2011 at 10:02 PM, Martin Jambor <mjam...@suse.cz> wrote:
> 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.
Ok with ...
> 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))
|| !tree_int_cst_equal (TREE_OPERAND (tci->object, 1), TREE_OPERAND (base, 1))
Thanks,
Richard.
