This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]