Re: [PATCH, PR 45934] Devirtualization aware of dynamic type changes

[Richard Guenther <rguenther at suse dot de>]

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.

> 2) We can never devirtualize according to a type of a global object
> because we do not know whether or not the current function has been
> (perhaps indirectly) called from its constructor or destructor.  This
> also means that we cannot devirtualize according to types of constants
> propagated by IPA-CP because those are always global object.
> Therefore I removed code paths deriving types from constant IPA-CP
> lattices and I check that declarations are not global when extracting
> BINFOs from them.
>
> This also means that testcases g++.dg/ipa/ipcp-ivi-1.C and
> ivinline-6.C test something which cannot be safely done and therefore
> I propose to remove them.

Likewise.

> 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.

But anyway - this part doesn't seem to be addressed in the current
patch at all, right?

> 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.

> 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.

> +  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).

> +  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").

> +  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?  Do we always know at which offset the
relevant vtable pointer is?

> +  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 (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.

Stopping review here - I am not convinced that the above is
conservatively correct (thus, you just make it harder to trigger
the problems).  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.

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.

Thanks,
Richard.