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 Tue, 23 Nov 2010, Martin Jambor wrote:
> Hi,
>
> On Tue, Nov 23, 2010 at 01:41:56PM +0100, Richard Guenther wrote:
> > On Mon, 22 Nov 2010, Martin Jambor wrote:
> >
> > > Hi,
> > >
> > > this patch fixes a wide range of issues including PR 45934 which are
> > > caused by the fact that the dynamic type of object changes during
> > > construction and destruction and devirtualization has to take these
> > > changes into account and has to avoid creating calls to descendants'
> > > implementation of a virtual functions when a constructor or a
> > > destructor of an ancestor is running. This is achieved by doing two
> > > things:
> > >
> > > 1) We cannot devirtualize OBJ_TYPE_REFs according to the static type
> > > of the object during folding. This code was dumbed down to what gcc
> > > 4.5 does, which basically devirtualizes only when the O_T_R object is
> > > a declaration - as opposed to an ancestor field within a declaration.
> > > This is necessary to make g++.dg/opt/devirt1.C pass and is safe. Note
> > > that we will want to fold O_T_Rs to their first parameter and we are
> > > currently not that far from it.
> > >
> > > Nevertheless, it also makes other testcases fail, specifically
> > > g++.dg/otr-fold-1.C, g++.dg/otr-fold-2.C, g++.dg/tree-ssa/pr43411.C
> > > and g++.dg/tree-ssa/pr45605.C. These testcases depend on type-based
> > > devirtualization and I will post a followup (RFC) patch that deals
> > > with them at -O2.
> >
> > This probably should be split out into a separate patch.
>
> Well, it was, I posted the patch separately after this one, even my
> paragraph above says so. Or do you mean some other part of this patch?
>
> <...>
I probably just was confused.
> >
> > > 3) Whenever IPA_JF_KNOWN_TYPE, no-op IPA_JF_PASS_THROUGH or
> > > IPA_JF_ANCESTOR jump functions are constructed, we also walk VDEFS and
> > > look for preceeding code that actually changes its dynamic type by
> > > assigning to its virtual method table pointer. From the RHS we can
> > > then identify the new type of the object and construct an appropriate
> > > IPA_JF_KNOWN_TYPE jump function instead.
> > >
> > > This patch does not attempt to limit walking of VDEFs, I left that for
> > > later. I am also not quite sure how to do that. During the body scan
> > > that ipa-prop.c does to do modification analysis it could look for
> > > assignments with a RHS that looks like a VMT address (address of an
> > > array ref into a variable declaration which is DECL_VIRTUAL), and walk
> > > VDEFS only if it finds one. The potentially inefficient VDEF walking
> > > would then happen only in constructors, destructors and functions into
> > > which they were inlined by early inlining (and we could punt for big
> > > functions like that).
> >
> > I doubt you can conservatively identify stores to virtual method
> > table pointers (well, w/o identifying every store as such). You
> > also have to assume there is such store elsewhere if you do _not_
> > find such a store.
>
> Well, I did what we agreed on in Ottawa, so I am a bit suprised that
> at least the general approach does not seem acceptable. Admittedly, it
> is basically pattern matching of what falls out of the front end for
> valid C++ code.
Well. I'm sort-of worried by the use of types and BINFOs by the
devirtualization machinery in general.
Also devirtualization happens in the middle-end and thus can't really
assume it was C++ originally (ok, only ObjC seems to use OBJ_TYPE_REF
and that in a weird way).
That said, I'm ok with trying to fix up devirtualization for 4.6
and not drop it to 4.5 functionality. Still in general I think
that not using types or binfos would be more appropriate for a
generic devirtualization machinery (I'm not convinced that you can't
construct a valid C++ testcase that would fail your constructor/destructor
matching by just wrapping another function call - I will try to
come up with a testcase for that).
> >
> > But anyway - this part doesn't seem to be addressed in the current
> > patch at all, right?
>
> The efficiency issue? No.
>
> >
> > > This patch also replaces all remaining uses of
> > > gimple_get_relevant_ref_binfo with a combination of
> > > get_base_ref_and_extent and get_binfo_at_offset because it is actually
> > > convenient and it is easy to have the two binfo searching functions
> > > diverge even though they should not.
> >
> > It probably makes sense to split this piece into a separate patch.
>
> It would be a bit artificial thing to do and wouldn't probably make a
> review any easier since all callers change too. It really was very
> convenient to do it with the rest of this patch.
Ok.
> >
> > > I assume there will be comments and suggestions. Nevertheless, the
> > > patch does pass bootstrap and regression tests (except for the
> > > testcases described above) on x86_64-linux and also make check-c++ on
> > > i686. Mind that it has to be applied on top of my fix for PR 46053
> > > (http://gcc.gnu.org/ml/gcc-patches/2010-11/msg02291.html).
> >
> > Indeed. Comments in-line.
> >
> > > Thanks,
> > >
> > > Martin
> > >
> > >
> > >
> > > 2010-11-19 Martin Jambor <mjambor@suse.cz>
> > >
> > > PR tree-optimization/45934
> > > * gimple-fold.c (get_base_binfo_for_type): Removed.
> > > (gimple_get_relevant_ref_binfo): Likewise.
> > > (gimple_fold_obj_type_ref_call): Dumb down to 4.5 functionality,
> > > removed parameter inplace, updated the caller.
> > > * ipa-cp.c (ipcp_propagate_types): Do not derive types from constants.
> > > (ipcp_discover_new_direct_edges): Do not do devirtualization based on
> > > constants.
> > > * gimple.h (gimple_get_relevant_ref_binfo): Remove declaration.
> > > * tree.c (get_binfo_at_offset): Get type from non-artificial fields.
> > > * ipa-prop.c (check_type_change): New function.
> > > (detect_type_change_1): Likewise.
> > > (detect_type_change): Likewise.
> > > (compute_complex_assign_jump_func): Check dynamic type change.
> > > (compute_complex_ancestor_jump_func): Likewise.
> > > (compute_scalar_jump_functions): Likewise.
> > > (compute_known_type_jump_func): Likewise, use get_ref_base_and_extent
> > > and get_binfo_at_offset instead of get_relevant_ref_binfo.
> > > (ipa_analyze_node): Push and pop cfun, set current_function_decl.
> > > (update_jump_functions_after_inlining): Do not derive types from
> > > constants.
> > > (try_make_edge_direct_virtual_call): Likewise.
> > >
> > > * testsuite/g++.dg/ipa/devirt-c-1.C: New test.
> > > * testsuite/g++.dg/ipa/devirt-c-2.C: Likewise.
> > > * testsuite/g++.dg/ipa/devirt-c-3.C: Likewise.
> > > * testsuite/g++.dg/ipa/devirt-c-4.C: Likewise.
> > > * testsuite/g++.dg/ipa/devirt-c-5.C: Likewise.
> > > * testsuite/g++.dg/ipa/devirt-d-1.C: Likewise.
> > > * testsuite/g++.dg/torture/pr45934.C: Likewise.
> > >
> > > The following removals are not part of the patch but I'll svn remove
> > > them when commiting the patch if approved:
> > >
> > > * testsuite/g++.dg/ipa/ipcp-ivi-1.C: Removed.
> > > * testsuite/g++.dg/ipa/ivinline-6.C: Likewise.
> > >
> > > Index: icln/gcc/gimple-fold.c
> > > ===================================================================
> > > --- icln.orig/gcc/gimple-fold.c
> > > +++ icln/gcc/gimple-fold.c
> > > @@ -1360,88 +1360,6 @@ gimple_fold_builtin (gimple stmt)
> > > return result;
> > > }
> > >
> > > -/* Search for a base binfo of BINFO that corresponds to TYPE and return it if
> > > - it is found or NULL_TREE if it is not. */
> > > -
> > > -static tree
> > > -get_base_binfo_for_type (tree binfo, tree type)
> > > -{
> > > - int i;
> > > - tree base_binfo;
> > > - tree res = NULL_TREE;
> > > -
> > > - for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
> > > - if (TREE_TYPE (base_binfo) == type)
> > > - {
> > > - gcc_assert (!res);
> > > - res = base_binfo;
> > > - }
> > > -
> > > - return res;
> > > -}
> > > -
> > > -/* Return a binfo describing the part of object referenced by expression REF.
> > > - Return NULL_TREE if it cannot be determined. REF can consist of a series of
> > > - COMPONENT_REFs of a declaration or of an INDIRECT_REF or it can also be just
> > > - a simple declaration, indirect reference or an SSA_NAME. If the function
> > > - discovers an INDIRECT_REF or an SSA_NAME, it will assume that the
> > > - encapsulating type is described by KNOWN_BINFO, if it is not NULL_TREE.
> > > - Otherwise the first non-artificial field declaration or the base declaration
> > > - will be examined to get the encapsulating type. */
> > > -
> > > -tree
> > > -gimple_get_relevant_ref_binfo (tree ref, tree known_binfo)
> > > -{
> > > - while (true)
> > > - {
> > > - if (TREE_CODE (ref) == COMPONENT_REF)
> > > - {
> > > - tree par_type;
> > > - tree binfo;
> > > - tree field = TREE_OPERAND (ref, 1);
> > > -
> > > - if (!DECL_ARTIFICIAL (field))
> > > - {
> > > - tree type = TREE_TYPE (field);
> > > - if (TREE_CODE (type) == RECORD_TYPE)
> > > - return TYPE_BINFO (type);
> > > - else
> > > - return NULL_TREE;
> > > - }
> > > -
> > > - par_type = TREE_TYPE (TREE_OPERAND (ref, 0));
> > > - binfo = TYPE_BINFO (par_type);
> > > - if (!binfo
> > > - || BINFO_N_BASE_BINFOS (binfo) == 0)
> > > - return NULL_TREE;
> > > -
> > > - /* Offset 0 indicates the primary base, whose vtable contents are
> > > - represented in the binfo for the derived class. */
> > > - if (int_bit_position (field) != 0)
> > > - {
> > > - tree d_binfo;
> > > -
> > > - /* Get descendant binfo. */
> > > - d_binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (ref, 0),
> > > - known_binfo);
> > > - if (!d_binfo)
> > > - return NULL_TREE;
> > > - return get_base_binfo_for_type (d_binfo, TREE_TYPE (field));
> > > - }
> > > -
> > > - ref = TREE_OPERAND (ref, 0);
> > > - }
> > > - else if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
> > > - return TYPE_BINFO (TREE_TYPE (ref));
> > > - else if (known_binfo
> > > - && (TREE_CODE (ref) == SSA_NAME
> > > - || TREE_CODE (ref) == MEM_REF))
> > > - return known_binfo;
> > > - else
> > > - return NULL_TREE;
> > > - }
> > > -}
> > > -
> > > /* Return a declaration of a function which an OBJ_TYPE_REF references. TOKEN
> > > is integer form of OBJ_TYPE_REF_TOKEN of the reference expression.
> > > KNOWN_BINFO carries the binfo describing the true type of
> > > @@ -1525,7 +1443,7 @@ gimple_adjust_this_by_delta (gimple_stmt
> > > INPLACE is false. Return true iff the statement was changed. */
> > >
> > > static bool
> > > -gimple_fold_obj_type_ref_call (gimple_stmt_iterator *gsi, bool inplace)
> > > +gimple_fold_obj_type_ref_call (gimple_stmt_iterator *gsi)
> > > {
> > > gimple stmt = gsi_stmt (*gsi);
> > > tree ref = gimple_call_fn (stmt);
> > > @@ -1533,27 +1451,21 @@ gimple_fold_obj_type_ref_call (gimple_st
> > > tree binfo, fndecl, delta;
> > > HOST_WIDE_INT token;
> > >
> > > - if (TREE_CODE (obj) == ADDR_EXPR)
> > > - obj = TREE_OPERAND (obj, 0);
> > > - else
> > > + if (TREE_CODE (obj) != ADDR_EXPR)
> > > return false;
> > > -
> > > - binfo = gimple_get_relevant_ref_binfo (obj, NULL_TREE);
> > > + obj = TREE_OPERAND (obj, 0);
> > > + if (!DECL_P (obj)
> > > + || TREE_CODE (TREE_TYPE (obj)) != RECORD_TYPE)
> > > + return false;
> > > + binfo = TYPE_BINFO (TREE_TYPE (obj));
> > > if (!binfo)
> > > return false;
> > > +
> > > token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
> > > - fndecl = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta,
> > > - !DECL_P (obj));
> > > + fndecl = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta, false);
> > > if (!fndecl)
> > > return false;
> > > -
> > > - if (integer_nonzerop (delta))
> > > - {
> > > - if (inplace)
> > > - return false;
> > > - gimple_adjust_this_by_delta (gsi, delta);
> > > - }
> > > -
> > > + gcc_checking_assert (integer_zerop (delta));
> > > gimple_call_set_fndecl (stmt, fndecl);
> > > return true;
> > > }
> > > @@ -1591,7 +1503,7 @@ gimple_fold_call (gimple_stmt_iterator *
> > > here where we can just smash the call operand. */
> > > callee = gimple_call_fn (stmt);
> > > if (TREE_CODE (callee) == OBJ_TYPE_REF)
> > > - return gimple_fold_obj_type_ref_call (gsi, inplace);
> > > + return gimple_fold_obj_type_ref_call (gsi);
> > > }
> > >
> > > return false;
> > > Index: icln/gcc/ipa-prop.c
> > > ===================================================================
> > > --- icln.orig/gcc/ipa-prop.c
> > > +++ icln/gcc/ipa-prop.c
> > > @@ -350,6 +350,107 @@ ipa_print_all_jump_functions (FILE *f)
> > > }
> > > }
> > >
> > > +/* 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?
> > 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. I considered
things like copy-initialization:
class A
{
public:
virtual ~A();
virtual void foo(void);
A(const A&x) { *this = x; foo(); }
};
class B : public A
{
public:
virtual ~B();
virtual void foo(void);
B(const A&x);
};
B::B(const A&x) : A(x) {}
but at least I see
;; Function B::B(const A&) (null)
;; enabled by -tree-original
{
<<cleanup_point <<< Unknown tree: expr_stmt
A::A (&((struct B *) this)->D.2125, (const struct A &) (const struct A
*) x) >>>>>;
try
{
<<cleanup_point <<< Unknown tree: expr_stmt
(void) (((struct B *) this)->D.2125._vptr.A = &_ZTV1B + 16) >>>>>;
}
catch
{
A::~A ((struct A *) this);
}
thus with -fnon-call-exceptions:
B::B(const A&) (struct B * const this, const struct A & x)
{
struct A * D.2145;
<bb 2>:
D.2145_2 = &this_1(D)->D.2125;
# .MEM_8 = VDEF <.MEM_4(D)>
D.2145_2->_vptr.A = &_ZTV1A[2];
# .MEM_9 = VDEF <.MEM_8>
A::foo (D.2145_2);
# .MEM_6 = VDEF <.MEM_9>
this_1(D)->D.2125._vptr.A = &_ZTV1B[2];
<bb 3>:
return;
<L0>:
# .MEM_7 = VDEF <.MEM_6>
A::~A (this_1(D));
resx 1
which means that walking from A::~A you see a vtable pointer store
but that actually hasn't happened when reaching the destructor
(and you would devirtualize to the wrong call?). Maybe the
FE can mark vtable pointer stores as non-trapping?
> Yes, disregarding C++ and looking at all the thing that are
> theoretically possible to do in gimple, this patch is not
> conservatively correct. I am not quite sure whether that is really
> worth the effort and what we should aim for because it is of course a
> much more difficult problem to tackle, both in terms of development
> and computational complexity.
I will try to sketch what I have in mind. I'm just not sure that
the situation even with C++ is as simple as it looks (just found
about the EH issue above, hopefully a non-issue).
Now with all of the above a way to go forward is to make
check_type_change more robust (and possibly build a more
precise ao_ref to walk aliases for to catch all and only
vtable pointer stores).
Btw, with VTT I meant virtual inheritance like
class C
{
public:
virtual ~C();
};
class A : virtual public C
{
public:
virtual ~A();
virtual void foo(void);
A(const A&x) { *this = x; foo(); }
};
class B : public A, virtual public C
{
public:
virtual ~B();
virtual void foo(void);
B(const A&x);
};
B::B(const A&x) : A(x) {}
you get more interesting control flow and vtable pointer modifications
from that (no idea if covariant returns would add even more).
Also consider people testing with -fno-tree-ccp -fno-tree-forwprop
(etc. ...) - using the alias oracle conservatively would just make
devirtualization fail in these cases (when you detect a
possible vtbl pointer store but the value stored isn't a vtable
based address -- you atm just assume that it wasn't a store to the
vtbl pointer).
Btw, it would be nice to have a flag to disable fancy devirtualization
(or to document that -fno-ipa-cp does that - does it?).
Richard.