This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH, PR 45934] Devirtualization aware of dynamic type changes
On Wed, 24 Nov 2010, Richard Guenther wrote:
> On Tue, 23 Nov 2010, Martin Jambor wrote:
>
> > Hi,
> >
> > On Tue, Nov 23, 2010 at 01:41:56PM +0100, Richard Guenther wrote:
> > > > +/* Helper function for detect_type_change_1 to check whether a particular
> > > > + statement is indeed an assignment to the virtual table pointer. */
> > > > +
> > > > +static bool
> > > > +check_type_change (ao_ref *ao, tree vdef, void *data)
> > > > +{
> > > > + gimple def_stmt = SSA_NAME_DEF_STMT (vdef);
> > > > + tree t, l, b, *res = (tree *) data;
> > > > +
> > > > + if (!is_gimple_assign (def_stmt))
> > > > + return false;
> > >
> > > A memcpy can also be assigning to the virtual table pointer. Think
> > > of
> > >
> > > class A : public class B { virtual ... };
> > >
> > > A *p;
> > > B *q;
> > > p = new A();
> > > memcpy (p,q, sizeof(B));
> > > p->xxx();
> > >
> > > no idea if that's valid, but the middle-end could replace a
> > > pointer assignment by memcpy. That said, the is_gimple_assign
> > > check isn't conservatively correct.
> >
> > Well, I guess that memcpy could be one more thing to check for but...
> >
> > >
> > > > + t = gimple_assign_rhs1 (def_stmt);
> > > > + if (TREE_CODE (t) != ADDR_EXPR)
> > > > + return false;
> > >
> > > Likewise.
> > >
> > > > + t = TREE_OPERAND (t, 0);
> > > > + if (TREE_CODE (t) == ARRAY_REF)
> > > > + t = TREE_OPERAND (t, 0);
> > > > + if (TREE_CODE (t) != VAR_DECL
> > > > + || !DECL_VIRTUAL_P (t))
> > > > + return false;
> > >
> > > And it gets worse ;)
> > >
> > > You are assuming too much here. The above could be represented as
> > >
> > > vtbptr_1 = &VTBL + constant offset;
> > > MEM<&obj, vtable offset> = vtbptr_1;
> > >
> > > or in 100 other valid ways.
> > >
> > > Iff we want to recognize vtable pointer modifications we should
> > > make sure we have a single valid way to represent them, thus
> > > have special tree codes or statements for modification and access.
> > >
> > > I'm thinking of a handled-component we won't touch, like
> > >
> > > VTBL<obj, maybe we need a constant offset> = ...
> > >
> > > Of course Jason may want to comment here (esp. if we can really
> > > annotate all vtable pointer modifications and accesses this way,
> > > considering my eventually invalid testcase above).
> >
> > ... of course this would be much more invasive.
>
> Yep. I also suggest something else ...
>
> > >
> > > > + l = gimple_assign_lhs (def_stmt);
> > > > + while (handled_component_p (l))
> > > > + l = TREE_OPERAND (l, 0);
> > > > + if (TREE_CODE (l) == MEM_REF)
> > > > + l = TREE_OPERAND (l, 0);
> > > > + b = ao->ref;
> > > > + while (handled_component_p (b))
> > > > + b = TREE_OPERAND (b, 0);
> > > > + if (TREE_CODE (b) == MEM_REF)
> > > > + b = TREE_OPERAND (b, 0);
> > > > + if (l != b)
> > > > + return false;
> > >
> > > Well - see above.
> > >
> > > What you really need is for the object you want to know if its
> > > vtable is modified construct a ao_ref with base, offset and size
> > > and walk_aliased_vdefs_1 with that ref. If you ever get a callback
> > > then you are screwed and have to return true. That would be
> > > conservatively correct - but also likely not worth the effort
> > > (as in, you can as well just assume 'true' always).
>
> ... here. Basically use the aliasing infrastructure to tell
> if a stmt could clobber the vtbl pointer (the aliasing infrastructure
> is supposed to be conservatively correct).
>
> Now, if we declare virtual dispatch and devirtualization a C++ only
> feature (but implemented with really C++ private middle-end infrastucture)
> we might get away with more strict assumptions - but I know not
> enough of our C++ implementation details to review the pattern
> matching for correctness then. At least exact matching of
> component-refs and the like looks very fragile to my eye as it
> is a match that if it bogusly fails generates wrong code and
> not just a mere missed optimization. The matching code also
> needs more commentary on what you actually match. It looks
> like you look for
>
> (MEM<a>|a)... = &DECL; | &DECL[...];
>
> where a is pointer equal to ao->ref base (but a can be &decl,
> and &decl and &decl wouldn't be the same (they are not shared)).
>
> DECL is supposedly the virtual table. I'd get to it via
>
> + t = gimple_assign_rhs1 (def_stmt);
> + if (TREE_CODE (t) != ADDR_EXPR)
> + return false;
> t = get_base_address (TREE_OPERAND (t, 0));
> if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t))
> return false;
>
> as the array-ref could be substituted with a MEM_REF with offset
> for example.
>
> Likewise for the lhs I'd do
>
> + l = get_base_address (gimple_assign_lhs (def_stmt));
> if (!l)
> return false;
> + if (TREE_CODE (l) == MEM_REF)
> + l = TREE_OPERAND (l, 0);
> + if (TREE_CODE (b) == MEM_REF)
> + b = TREE_OPERAND (b, 0);
> /* Now we have either a decl or an SSA name, pointer comparison ok. */
> if (l != b)
> return false;
>
> which would at least match assignments of an address based on a
> virtual table somewhere into the object of ao->ref.
>
> Now - you do use that virtual table for optimization, so if I do
>
> class X : ... {
> virtual whatever();
> void *my_fake_vtable;
> };
> extern void *x[] __asm__(("mangled name for some vtable"));
> foo(X *p)
> {
> p->my_fake_vtable = &x;
> p->whatever();
> }
>
> and have LTO merge the decls for x and the vtable then you might
> get confused, right?
>
> So I think you need to verify the store actually happens to the
> vtable slot (what about vtt table pointer stores?).
>
> Now, you need check_type_change for both correctness and
> optimization (and it doesn't seem to have a way to say "don't know",
> does it?) - either it doesn't detect a vtable store, then it
> presumably makes static type assumptions, or it does, in which
> case it uses the type of the vtable that was stored. So you
> need to catch both 1) all possible vtable pointer stores,
> 2) and only real vtable pointer stores. Thus, there's no
> room for errors (or being conservative to either side) in this
> function - which makes me feel uncomfortable. Is it possible
> to do only 1)? Thus, do not make use of DECL_CONTEXT of the
> vtable but not devirtualize in that case?
To followup myself here - the following maybe clarifies the above.
You have to split check_type_change, one part,
bool stmt_may_be_vtbl_ptr_store (gimple stmt)
is never allowed to return false if the stmt is a vtbl pointer store.
A trivially correct implementation is just 'return true;'. The other
part,
bool stmt_must_be_vtbl_ptr_store (gimple stmt, tree *vtbl)
is never allowed to return true if the stmt is _not_ a vtbl pointer
store or the stored vtbl cannot be determined. A trivially correct
implementation is just 'return false'.
If stmt_may_be_vtbl_ptr_store returns true and stmt_must_be_vtbl_ptr_store
returns false you cannot devirtualize (and thus cannot create a
jump function). Your current implementation does not allow for
this case.
The stmt_may_be_vtbl_ptr_store can be implemented by just
walk_aliased_vdefs if the provided reference is correct.
> > > Note that walk_aliased_vdefs may not do what you think when
> > > walking PHIs:
> > >
> > > > + *res = DECL_CONTEXT (t);
> > >
> > > You have to consider that for
> > >
> > > if (x)
> > > store1;
> > > else
> > > store2;
> > >
> > > you can reach here for both store1 and store2 and thus have to
> > > merge *res (and have a proper state for "not mergeable").
> >
> > The code is specifically targeted at C++ constructors and destructors
> > and no other and situations such as the conditional type changes can
> > simply never happen in those scenarios. (They would be possible with
> > placement new but I did disregard those because those are constitute
> > undefined code).
>
> I'm always thinking of optimization passes creating this kind
> of situations. But well, maybe the above is not an issue (you
> could at least assert that *res is NULL before returning true).
>
> > If I understood the paragraph above that correctly, I also think it
> > discusses situations that simply cannot happen. I specifically look
> > for assignments only and for example intentionally disregard the
> > possibility that the vptr is modified by a called function because
> > such situation cannot happen or does not matter. If it was a
> > constructor or destructor, then either the current function is a
> > constructor/destructor of a descendant and therefore somewhere after
> > the call (in a post-dominance sense, before any call to any function,
> > virtual or not) there is a new assignment to all relevant vptrs, or it
> > is a call to the top-most constructor and then the static type can be
> > used without any problems. (The third option is that the code calls
> > the destructor explicitely and then it does not matter because if it
> > invokes a virtual function after the constructor finishes it is
> > clearly bogus.) I also disregard the possibility that the vptr is
> > modified through some alias because in constructors and destructors
> > they are also modified through the this pointer.
>
> Hm. I can't seem to generate a testcase that initially wraps
> a constructor or destructor call into a function.
But of course function splitting can trivially create such a case.
Richard.