Re: [PATCH, PR 45934 2/6] Remove devirtualizations that cannot be done

[Richard Guenther <rguenther at suse dot de>]

On Wed, 1 Dec 2010, Martin Jambor wrote:

> This patch removes parts of the current devirtualization machinery
> that cannot work because of potential dynamic type change which might
> be under way during sub-object construction and destruction.  In the
> general case we simply cannot know this about global objects and we do
> not want to proceed with the necessary detection when folding.  So
> devirtualization based on global decls, global IPA-CP constants is
> being removed and devirtualization in folding is dumbed down to never
> work on sub-objects.
> 
> This patch removes the two testcases that test devirtualization based
> on global variables.  After this patch, g++.dg/otr-fold-[12].C,
> g++.dg/tree-ssa/pr43411.C and g++.dg/tree-ssa/pr45605.C fail, this is
> addressed by the very last patch in the series.
> 
> Bootstrapped and tested separately on x86-64-linux, I think I also did
> make check-c++ on i686 but I am no longer really sure, it certainly
> passed along with the rest.
>

Comments inline

> Thanks,
> 
> Martin
> 
> 
> 2010-11-30  Martin Jambor  <mjambor@suse.cz>
> 
> 	PR tree-optimization/45934
> 	PR tree-optimization/46302
> 	* 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.
> 	* gimple.h (gimple_get_relevant_ref_binfo): Remove declaration.
> 	* ipa-cp.c (ipcp_propagate_types): Do not derive types from constants.
> 	(ipcp_discover_new_direct_edges): Do not do devirtualization based on
> 	constants.
> 	* ipa-prop.c (mem_ref_offset): New variable base to store the result
> 	of get_ref_base_and_extent.
> 	(compute_known_type_jump_func): Use get_ref_base_and_extent and
> 	get_binfo_at_offset instead of gimple_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.
> 	* tree.c (get_binfo_at_offset): Get type from non-artificial fields.
> 	* 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_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/gimple.h
> ===================================================================
> --- icln.orig/gcc/gimple.h
> +++ icln/gcc/gimple.h
> @@ -892,7 +892,6 @@ unsigned get_gimple_rhs_num_ops (enum tr
>  gimple gimple_alloc_stat (enum gimple_code, unsigned MEM_STAT_DECL);
>  const char *gimple_decl_printable_name (tree, int);
>  bool gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace);
> -tree gimple_get_relevant_ref_binfo (tree ref, tree known_binfo);
>  tree gimple_get_virt_mehtod_for_binfo (HOST_WIDE_INT, tree, tree *, bool);
>  void gimple_adjust_this_by_delta (gimple_stmt_iterator *, tree);
>  /* Returns true iff T is a valid GIMPLE statement.  */
> Index: icln/gcc/ipa-cp.c
> ===================================================================
> --- icln.orig/gcc/ipa-cp.c
> +++ icln/gcc/ipa-cp.c
> @@ -781,26 +781,16 @@ ipcp_propagate_types (struct ipa_node_pa
>  		      struct ipa_node_params *callee_info,
>  		      struct ipa_jump_func *jf, int i)
>  {
> -  tree cst, binfo;
> -
>    switch (jf->type)
>      {
>      case IPA_JF_UNKNOWN:
>      case IPA_JF_CONST_MEMBER_PTR:
> +    case IPA_JF_CONST:
>        break;
>  
>      case IPA_JF_KNOWN_TYPE:
>        return ipcp_add_param_type (callee_info, i, jf->value.base_binfo);
>  
> -    case IPA_JF_CONST:
> -      cst = jf->value.constant;
> -      if (TREE_CODE (cst) != ADDR_EXPR)
> -	break;
> -      binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (cst, 0), NULL_TREE);
> -      if (!binfo)
> -	break;
> -      return ipcp_add_param_type (callee_info, i, binfo);
> -
>      case IPA_JF_PASS_THROUGH:
>      case IPA_JF_ANCESTOR:
>        return ipcp_copy_types (caller_info, callee_info, i, jf);
> @@ -1292,35 +1282,13 @@ ipcp_discover_new_direct_edges (struct c
>    for (ie = node->indirect_calls; ie; ie = next_ie)
>      {
>        struct cgraph_indirect_call_info *ici = ie->indirect_info;
> -      tree target, delta = NULL_TREE;
>  
>        next_ie = ie->next_callee;
> -      if (ici->param_index != index)
> +      if (ici->param_index != index
> +	  || ici->polymorphic)
>  	continue;
>  
> -      if (ici->polymorphic)
> -	{
> -	  tree binfo;
> -	  HOST_WIDE_INT token;
> -
> -	  if (TREE_CODE (cst) != ADDR_EXPR)
> -	    continue;
> -
> -	  binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (cst, 0),
> -						 NULL_TREE);
> -	  if (!binfo)
> -	    continue;
> -	  gcc_assert (ie->indirect_info->anc_offset == 0);
> -	  token = ie->indirect_info->otr_token;
> -	  target = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta,
> -						     true);
> -	  if (!target)
> -	    continue;
> -	}
> -      else
> -	target = cst;
> -
> -      ipa_make_edge_direct_to_target (ie, target, delta);
> +      ipa_make_edge_direct_to_target (ie, cst, NULL_TREE);
>      }
>  }
>  
> Index: icln/gcc/ipa-prop.c
> ===================================================================
> --- icln.orig/gcc/ipa-prop.c
> +++ icln/gcc/ipa-prop.c
> @@ -362,7 +362,7 @@ compute_complex_assign_jump_func (struct
>  				  gimple stmt, tree name)
>  {
>    HOST_WIDE_INT offset, size, max_size;
> -  tree op1, op2, type;
> +  tree op1, op2, base, type;
>    int index;
>  
>    op1 = gimple_assign_rhs1 (stmt);
> @@ -404,20 +404,21 @@ compute_complex_assign_jump_func (struct
>    type = TREE_TYPE (op1);
>    if (TREE_CODE (type) != RECORD_TYPE)
>      return;
> -  op1 = get_ref_base_and_extent (op1, &offset, &size, &max_size);
> -  if (TREE_CODE (op1) != MEM_REF
> +  base = get_ref_base_and_extent (op1, &offset, &size, &max_size);
> +  if (TREE_CODE (base) != MEM_REF
>        /* If this is a varying address, punt.  */
>        || max_size == -1
>        || max_size != size)
>      return;
> -  offset += mem_ref_offset (op1).low * BITS_PER_UNIT;
> -  op1 = TREE_OPERAND (op1, 0);
> -  if (TREE_CODE (op1) != SSA_NAME
> -      || !SSA_NAME_IS_DEFAULT_DEF (op1)
> +  offset += mem_ref_offset (base).low * BITS_PER_UNIT;
> +  base = TREE_OPERAND (base, 0);
> +  if (TREE_CODE (base) != SSA_NAME
> +      || !SSA_NAME_IS_DEFAULT_DEF (base)
>        || offset < 0)
>      return;
>  
> -  index = ipa_get_param_decl_index (info, SSA_NAME_VAR (op1));
> +  /* Dynamic types are changed only in constructors and destructors and  */
> +  index = ipa_get_param_decl_index (info, SSA_NAME_VAR (base));
>    if (index >= 0)
>      {
>        jfunc->type = IPA_JF_ANCESTOR;
> @@ -530,13 +531,26 @@ compute_complex_ancestor_jump_func (stru
>  static void
>  compute_known_type_jump_func (tree op, struct ipa_jump_func *jfunc)
>  {
> -  tree binfo;
> +  HOST_WIDE_INT offset, size, max_size;
> +  tree base, binfo;
>  
> -  if (TREE_CODE (op) != ADDR_EXPR)
> +  if (TREE_CODE (op) != ADDR_EXPR
> +      || TREE_CODE (TREE_TYPE (TREE_TYPE (op))) != RECORD_TYPE)
>      return;
>  
>    op = TREE_OPERAND (op, 0);
> -  binfo = gimple_get_relevant_ref_binfo (op, NULL_TREE);
> +  base = get_ref_base_and_extent (op, &offset, &size, &max_size);
> +  if (!DECL_P (base)
> +      || max_size == -1
> +      || max_size != size
> +      || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE
> +      || is_global_var (base))
> +    return;
> +
> +  binfo = TYPE_BINFO (TREE_TYPE (base));
> +  if (!binfo)
> +    return;
> +  binfo = get_binfo_at_offset (binfo, offset, TREE_TYPE (op));
>    if (binfo)
>      {
>        jfunc->type = IPA_JF_KNOWN_TYPE;
> @@ -1346,6 +1360,9 @@ ipa_analyze_node (struct cgraph_node *no
>    struct param_analysis_info *parms_info;
>    int i, param_count;
>  
> +  push_cfun (DECL_STRUCT_FUNCTION (node->decl));
> +  current_function_decl = node->decl;
> +

Why do we need to push/pop cfun now?

>    ipa_initialize_node_params (node);
>  
>    param_count = ipa_get_param_count (info);
> @@ -1358,6 +1375,9 @@ ipa_analyze_node (struct cgraph_node *no
>    for (i = 0; i < param_count; i++)
>      if (parms_info[i].visited_statements)
>        BITMAP_FREE (parms_info[i].visited_statements);
> +
> +  current_function_decl = NULL;
> +  pop_cfun ();
>  }
>  
>  
> @@ -1416,17 +1436,6 @@ update_jump_functions_after_inlining (st
>  	  src = ipa_get_ith_jump_func (top, dst->value.ancestor.formal_id);
>  	  if (src->type == IPA_JF_KNOWN_TYPE)
>  	    combine_known_type_and_ancestor_jfs (src, dst);
> -	  else if (src->type == IPA_JF_CONST)
> -	    {
> -	      struct ipa_jump_func kt_func;
> -
> -	      kt_func.type = IPA_JF_UNKNOWN;
> -	      compute_known_type_jump_func (src->value.constant, &kt_func);
> -	      if (kt_func.type == IPA_JF_KNOWN_TYPE)
> -		combine_known_type_and_ancestor_jfs (&kt_func, dst);
> -	      else
> -		dst->type = IPA_JF_UNKNOWN;
> -	    }
>  	  else if (src->type == IPA_JF_PASS_THROUGH
>  		   && src->value.pass_through.operation == NOP_EXPR)
>  	    dst->value.ancestor.formal_id = src->value.pass_through.formal_id;
> @@ -1539,15 +1548,6 @@ try_make_edge_direct_virtual_call (struc
>  
>    if (jfunc->type == IPA_JF_KNOWN_TYPE)
>      binfo = jfunc->value.base_binfo;
> -  else if (jfunc->type == IPA_JF_CONST)
> -    {
> -      tree cst = jfunc->value.constant;
> -      if (TREE_CODE (cst) == ADDR_EXPR)
> -	binfo = gimple_get_relevant_ref_binfo (TREE_OPERAND (cst, 0),
> -					       NULL_TREE);
> -      else
> -  	return NULL;
> -    }
>    else
>      return NULL;
>  
> Index: icln/gcc/tree.c
> ===================================================================
> --- icln.orig/gcc/tree.c
> +++ icln/gcc/tree.c
> @@ -10950,8 +10950,7 @@ get_binfo_at_offset (tree binfo, HOST_WI
>  
>        if (type == expected_type)
>  	  return binfo;
> -      if (TREE_CODE (type) != RECORD_TYPE
> -	  || offset < 0)
> +      if (offset < 0)
>  	return NULL_TREE;
>  
>        for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))

Please keep the record-type check, using TYPE_FIELDS isn't valid
for other kinds.

Otherwise ok.

Thanks,
Richard.

> @@ -10964,12 +10963,18 @@ get_binfo_at_offset (tree binfo, HOST_WI
>  	  if (pos <= offset && (pos + size) > offset)
>  	    break;
>  	}
> -      if (!fld || !DECL_ARTIFICIAL (fld))
> +      if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
>  	return NULL_TREE;
>  
> +      if (!DECL_ARTIFICIAL (fld))
> +	{
> +	  binfo = TYPE_BINFO (TREE_TYPE (fld));
> +	  if (!binfo)
> +	    return NULL_TREE;
> +	}
>        /* Offset 0 indicates the primary base, whose vtable contents are
>  	 represented in the binfo for the derived class.  */
> -      if (offset != 0)
> +      else if (offset != 0)
>  	{
>  	  tree base_binfo, found_binfo = NULL_TREE;
>  	  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
> Index: icln/gcc/testsuite/g++.dg/ipa/ipcp-ivi-1.C
> ===================================================================
> --- icln.orig/gcc/testsuite/g++.dg/ipa/ipcp-ivi-1.C
> +++ /dev/null
> @@ -1,65 +0,0 @@
> -/* Verify that simple virtual calls are inlined even without early
> -   inlining.  */
> -/* { dg-do run } */
> -/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining"  } */
> -
> -extern "C" void abort (void);
> -
> -class A
> -{
> -public:
> -  int data;
> -  virtual int foo (int i);
> -};
> -
> -class B : public A
> -{
> -public:
> -  virtual int foo (int i);
> -};
> -
> -class C : public A
> -{
> -public:
> -  virtual int foo (int i);
> -};
> -
> -int A::foo (int i)
> -{
> -  return i + 1;
> -}
> -
> -int B::foo (int i)
> -{
> -  return i + 2;
> -}
> -
> -int C::foo (int i)
> -{
> -  return i + 3;
> -}
> -
> -int __attribute__ ((noinline)) middleman (class A *obj, int i)
> -{
> -  return obj->foo (i);
> -}
> -
> -int __attribute__ ((noinline,noclone)) get_input(void)
> -{
> -  return 1;
> -}
> -
> -class B b;
> -
> -int main (int argc, char *argv[])
> -{
> -  int i;
> -
> -  for (i = 0; i < get_input (); i++)
> -    if (middleman (&b, get_input ()) != 3)
> -      abort ();
> -  return 0;
> -}
> -
> -/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int.*middleman"  "inline"  } } */
> -/* { dg-final { cleanup-ipa-dump "inline" } } */
> Index: icln/gcc/testsuite/g++.dg/ipa/ivinline-6.C
> ===================================================================
> --- icln.orig/gcc/testsuite/g++.dg/ipa/ivinline-6.C
> +++ /dev/null
> @@ -1,58 +0,0 @@
> -/* Verify that virtual call inlining works also when it has to get the
> -   type from an ipa invariant and that even in this case it does not
> -   pick a wrong method when there is a user defined ancestor in an
> -   object.  */
> -/* { dg-do run } */
> -/* { dg-options "-O3 -fdump-ipa-inline -fno-early-inlining -fno-ipa-cp"  } */
> -
> -extern "C" void abort (void);
> -
> -class A
> -{
> -public:
> -  int data;
> -  virtual int foo (int i);
> -};
> -
> -class B : public A
> -{
> -public:
> -  class A confusion;
> -  virtual int foo (int i);
> -};
> -
> -int A::foo (int i)
> -{
> -  return i + 1;
> -}
> -
> -int B::foo (int i)
> -{
> -  return i + 2;
> -}
> -
> -int middleman (class A *obj, int i)
> -{
> -  return obj->foo (i);
> -}
> -
> -int __attribute__ ((noinline,noclone)) get_input(void)
> -{
> -  return 1;
> -}
> -
> -class B b;
> -
> -int main (int argc, char *argv[])
> -{
> -  int i, j = get_input ();
> -
> -  for (i = 0; i < j; i++)
> -    if ((middleman (&b, j) + 100 * middleman (&b.confusion, j)) != 203)
> -      abort ();
> -  return 0;
> -}
> -
> -/* { dg-final { scan-ipa-dump "A::foo\[^\\n\]*inline copy in int main"  "inline"  } } */
> -/* { dg-final { scan-ipa-dump "B::foo\[^\\n\]*inline copy in int main"  "inline"  } } */
> -/* { dg-final { cleanup-ipa-dump "inline" } } */
> 
> 

-- 
Richard Guenther <rguenther@suse.de>
Novell / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex