Re: [PATCH, devirtualization] Detect the new type in type change detection

[Richard Guenther <richard dot guenther at gmail dot com>]

On Tue, Nov 1, 2011 at 10:02 PM, Martin Jambor <mjambor@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 <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.
>>
>
> 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 ?<mjambor@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.