[PATCH, PR 45934] Devirtualization aware of dynamic type changes
Martin Jambor
mjambor@suse.cz
Tue Nov 23 22:02:00 GMT 2010
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?
<...>
>
> > 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.
>
> 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.
>
> > 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.
>
> > + 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).
>
> 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).
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.
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.
>
> > + return true;
> > +}
> > +
> > +/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
> > + looking for assignments to its virtual table pointer. If it is, return true
> > + and fill in the jump function JFUNC with relevant type information. If
> > + ANC_TYPE is non-NULL, look for binfo of its ancestor of that type at offset
> > + ANC_OFFSET. ARG is supposed to be a dereferenced pointer or a
> > + declaration. */
> > +
> > +static bool
> > +detect_type_change_1 (tree arg, gimple call, struct ipa_jump_func *jfunc,
> > + tree anc_type, HOST_WIDE_INT anc_offset)
> > +{
> > + tree res = NULL_TREE;
> > + ao_ref ar;
> > +
> > + /* Const calls cannot call virtual methods through VMT and so type changes do
> > + not matter. */
> > + if (!gimple_vuse (call))
> > + return false;
> > + ao_ref_init (&ar, arg);
>
> arg will always be a decl here?
It is either a declaration or a component_ref of a declaration or a
dereferenced pointer (the function comment needs fixing).
> Do we always know at which offset the relevant vtable pointer is?
At the moment I cannot think of a situation when this would not be
zero (relative to arg, not ther decl). But to be sure I'd have to try
a few examples.
>
> > + walk_aliased_vdefs (&ar, gimple_vuse (call), check_type_change, &res, NULL);
> > + if (!res)
> > + return false;
> > +
> > + if (anc_type)
> > + {
> > + tree new_binfo = get_binfo_at_offset (TYPE_BINFO (res), anc_offset,
> > + anc_type);
> > +
> > + if (new_binfo)
> > + {
> > + jfunc->type = IPA_JF_KNOWN_TYPE;
> > + jfunc->value.base_binfo = new_binfo;
> > + }
> > + else
> > + jfunc->type = IPA_JF_UNKNOWN;
> > + }
> > + else
> > + {
> > + jfunc->type = IPA_JF_KNOWN_TYPE;
> > + jfunc->value.base_binfo = TYPE_BINFO (res);
> > + }
> > +
> > + return true;
> > +}
> > +
> > +/* Like detect_type_change_1 but ARG is supposed to be a non-dereferenced
> > + pointer SSA name. */
> > +
> > +static bool
> > +detect_type_change (tree arg, gimple call, struct ipa_jump_func *jfunc,
> > + tree anc_type, HOST_WIDE_INT anc_offset)
> > +{
> > + if (!POINTER_TYPE_P (TREE_TYPE (arg))
> > + || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
> > + return false;
> > + gcc_checking_assert (TREE_CODE (arg) != ADDR_EXPR);
> > + arg = build_simple_mem_ref (arg);
>
> You definitely screw TBAA here. You want to use
> ao_ref_init_from_ptr_and_size instead
I will have a look at that.
> (do you know the size of the object? remember that the type of SSA
> name pointers do not tell you anything about the pointed-to type.
The fact that dynamic type changes in reality really means that the
vptr points to a different table. The static type of the field
representing ancestor is still the same during the whole lifetime of
the (whole) object. Again, I am assuming no placement new is
involved.
>
> Stopping review here - I am not convinced that the above is
> conservatively correct (thus, you just make it harder to trigger
> the problems).
Well, I hope that I explained why I do the detection this way and
disregard conditional type changes and the like. Of course, if you do
not find that sufficient then I agree that devirtualization is much
more difficult and even perhaps an impossible thing to do (e.g if we
assume any function call can arbitrarily change the dynamic type of
anything then it really isn't worth implementing, fortunately I argue
that this is not what can happen).
> And if you are going to detect dynamic type changes
> by looking at vtable pointer stores you can IMHO as well go and
> propagate vtable addresses instead of types and then simply do
> the transformation at the vtable loads instead of the calls
> and do devirtualization only based on constant propagation from
> vtable loads.
Well, let me reiterate that propagating vptrs interprocedurally is a
more difficult thing to do, mainly because there is not one such
pointer but one for the whole object and one for each field
representing an ancestor with virtual methods. You would also need
return functions containing all of them (currently we can get away
without return functions rather well). And it wouldn't make the
problems discussed above any simpler... in fact it would make it more
difficult because we would have to catch all the assignments to vptrs
not just one (and because my patch extracts the type from DECL_CONTEXT
of the VMT it really does not matter which one we stumble upon first).
>
> For 4.6 please consider reverting back to the non-broken 4.5 state,
> I don't really feel comfortable with more experimenting during stage3.
If I need to introduce a new VTBL handled component then this is most
probably inevitable. I still think that the code dealing with dynamic
type changes should aim for dealing with the real situations only and
should not need to deal with things that do not happen with valid
input.
Martin
More information about the Gcc-patches
mailing list