Re: [PATCH 4/4] Devirtualization based on global objects

[Martin Jambor <mjambor@suse.cz>]

Hi,

On Fri, Apr 15, 2011 at 05:38:50PM +0200, Richard Guenther wrote:
> On Fri, 15 Apr 2011, Martin Jambor wrote:
> 
> > Hi,
> > 
> > this is the patch that actually speeds up astar (together with the
> > previous one).  It implements devirtualization based on global
> > objects.  In the past we have refrained from doing this because in
> > general it is difficult to say whether the object is currently being
> > constructed and so it might have a dynamic type of one of its
> > ancestors.  However, if the object's class does not have any ancestors
> > that obviously cannot happen.
> > 
> > Devirtualizing in such conditions is enough to change a virtual call
> > to regwayobj::isaddtobound in 473.astar to a direct one which can and
> > should be inlined.  That seemed a good justification to implement this
> > and so the patch below does so and brings about 3.1% speedup for that
> > benchmark with LTO.
> > 
> > I acknowledge that instead of discarding all classes with ancestors it
> > would be better to check that the called virtual method has the same
> > implementation in all ancestors instead.  That is perhaps something
> > for later.
> > 
> > It took me surprisingly long to realize that this technique can be
> > used for folding virtual calls based on local automatically allocated
> > objexts too and so can be used to un-XFAIL g++.dg/opt/devirt1.c that
> > regressed in 4.6.
> > 
> > Bootstrapped and tested on x86_64-linux.  OK for trunk?
> > 
> > Thanks,
> > 
> > Martin
> > 
> > 
> > 2011-04-15  Martin Jambor  <mjambor@suse.cz>
> > 
> > 	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Devirtualize
> > 	also according to actual contants.
> > 	* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): New function.
> > 	(gimple_fold_obj_type_ref_call): New function.
> > 	(gimple_fold_call): Call gimple_fold_obj_type_ref_call on
> > 	OBJ_TYPE_REFs.
> > 	* gimple.h (gimple_extract_devirt_binfo_from_cst): Declare.
> > 
> > 	* testsuite/g++.dg/opt/devirt1.C: Bump to -O2, remove XFAIL.
> > 	* testsuite/g++.dg/opt/devirt2.C: New test.
> > 	* testsuite/g++.dg/ipa/devirt-g-1.C: Likewise.
> > 
> > 

...

> > Index: src/gcc/gimple-fold.c
> > ===================================================================
> > --- src.orig/gcc/gimple-fold.c
> > +++ src/gcc/gimple-fold.c
> > @@ -1438,6 +1438,95 @@ gimple_adjust_this_by_delta (gimple_stmt
> >    gimple_call_set_arg (call_stmt, 0, tmp);
> >  }
> >  
> > +/* Return a binfo to be used for devirtualization of calls based on an object
> > +   represented by a declaration (i.e. a global or automatically allocated one)
> > +   or NULL if it cannot be found or is not safe.  CST is expected to be an
> > +   ADDR_EXPR of such object or the function will return NULL.  Currently it is
> > +   safe to use such binfo only if it has no base binfo (i.e. no ancestors).  */
> > +
> > +tree
> > +gimple_extract_devirt_binfo_from_cst (tree cst)
> > +{
> > +  HOST_WIDE_INT offset, size, max_size;
> > +  tree base, type, expected_type, binfo;
> > +  bool last_artificial = false;
> > +
> > +  if (!flag_devirtualize
> > +      || TREE_CODE (cst) != ADDR_EXPR
> > +      || TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) != RECORD_TYPE)
> > +    return NULL_TREE;
> > +
> > +  cst = TREE_OPERAND (cst, 0);
> > +  expected_type = TREE_TYPE (cst);
> > +  base = get_ref_base_and_extent (cst, &offset, &size, &max_size);
> > +  type = TREE_TYPE (base);
> > +  if (!DECL_P (base)
> > +      || max_size == -1
> > +      || max_size != size
> > +      || TREE_CODE (type) != RECORD_TYPE)
> > +    return NULL_TREE;
> > +
> > +  while (true)
> > +    {
> > +      HOST_WIDE_INT pos, size;
> > +      tree fld;
> > +
> > +      if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (expected_type))
> > +	break;
> > +      if (offset < 0)
> > +	return NULL_TREE;
> > +
> > +      for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
> > +	{
> > +	  if (TREE_CODE (fld) != FIELD_DECL)
> > +	    continue;
> > +
> > +	  pos = int_bit_position (fld);
> > +	  size = tree_low_cst (DECL_SIZE (fld), 1);
> > +	  if (pos <= offset && (pos + size) > offset)
> > +	    break;
> > +	}
> > +      if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
> > +	return NULL_TREE;
> > +
> > +      last_artificial = DECL_ARTIFICIAL (fld);
> > +      type = TREE_TYPE (fld);
> > +      offset -= pos;
> > +    }
> 
> Please add come comments on what this loop does.  It looks like
> it searches for the FIELD_DECL that corresponds to the incoming
> constant address (but it doesn't have to exactly point to its
> beginning?). 

Yes, an object can be within another.  Like S within R in the added
testcase g++/opt/devirt2.C.  Then it checks it is not a representative
of an ancestor but a user-defined object by looking at DECL_ARTIFICIAL.

> Note that you miss to handle the case where the
> declaration is view-converted to a different type and you
> instead use the declared type.  Which ISTR was correct as
> placement new on decls is kind of invalid.

Yes, I know I'm assuming that.

> 
> > +  if (last_artificial)
> > +    return NULL_TREE;
> > +  binfo = TYPE_BINFO (type);
> > +  if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
> > +    return NULL_TREE;
> > +  else
> > +    return binfo;
> > +}
> > +
> > +/* Fold a call statement to OBJ_TYPE_REF to a direct call if possible.  Return
> > +   true iff the statement was changed.  GSI determines the statement.  */
> > +
> > +static bool
> > +gimple_fold_obj_type_ref_call (gimple_stmt_iterator *gsi)
> > +{
> > +  gimple stmt = gsi_stmt (*gsi);
> > +  tree ref = gimple_call_fn (stmt);
> > +  tree binfo, fndecl, delta;
> > +  HOST_WIDE_INT token;
> > +
> > +  binfo = gimple_extract_devirt_binfo_from_cst (OBJ_TYPE_REF_OBJECT (ref));
> > +  if (!binfo)
> > +    return false;
> > +
> > +  token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
> 
> Either use TREE_INT_CST_LOW or first check with host_integerp.
> 
> Ok with that change.
> 

OK.

Unfortunately I have conflicted with your patch folding OBJ_TYPE_REFs
and since you did not introduce a special function for OBJ_TYPE_REFs,
I kept the functionality within gimple_fold_call too.

So this is what I am testing and what I intend to commit if all goes
well.

Thanks a lot,

Martin


2011-04-18  Martin Jambor  <mjambor@suse.cz>

	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Devirtualize
	also according to actual contants.
	* gimple-fold.c (gimple_extract_devirt_binfo_from_cst): New function.
	(gimple_fold_call): Use it.
	* gimple.h (gimple_extract_devirt_binfo_from_cst): Declare.

	* testsuite/g++.dg/opt/devirt1.C: Bump to -O2, remove XFAIL.
	* testsuite/g++.dg/opt/devirt2.C: New test.
	* testsuite/g++.dg/ipa/devirt-g-1.C: Likewise.

Index: src/gcc/ipa-cp.c
===================================================================
*** src.orig/gcc/ipa-cp.c
--- src/gcc/ipa-cp.c
*************** ipcp_process_devirtualization_opportunit
*** 1246,1296 ****
  
    for (ie = node->indirect_calls; ie; ie = next_ie)
      {
!       int param_index, types_count, j;
        HOST_WIDE_INT token, anc_offset;
        tree target, delta, otr_type;
  
        next_ie = ie->next_callee;
        if (!ie->indirect_info->polymorphic)
  	continue;
        param_index = ie->indirect_info->param_index;
!       if (param_index == -1
! 	  || ipa_param_cannot_devirtualize_p (info, param_index)
! 	  || ipa_param_types_vec_empty (info, param_index))
  	continue;
  
        token = ie->indirect_info->otr_token;
        anc_offset = ie->indirect_info->anc_offset;
        otr_type = ie->indirect_info->otr_type;
        target = NULL_TREE;
!       types_count = VEC_length (tree, info->params[param_index].types);
!       for (j = 0; j < types_count; j++)
  	{
! 	  tree binfo = VEC_index (tree, info->params[param_index].types, j);
! 	  tree d, t;
! 
  	  binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
  	  if (!binfo)
! 	    {
! 	      target = NULL_TREE;
! 	      break;
! 	    }
  
! 	  t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
! 	  if (!t)
! 	    {
! 	      target = NULL_TREE;
! 	      break;
! 	    }
! 	  else if (!target)
! 	    {
! 	      target = t;
! 	      delta = d;
! 	    }
! 	  else if (target != t || !tree_int_cst_equal (delta, d))
  	    {
! 	      target = NULL_TREE;
! 	      break;
  	    }
  	}
  
--- 1246,1316 ----
  
    for (ie = node->indirect_calls; ie; ie = next_ie)
      {
!       int param_index;
        HOST_WIDE_INT token, anc_offset;
        tree target, delta, otr_type;
+       struct ipcp_lattice *lat;
  
        next_ie = ie->next_callee;
        if (!ie->indirect_info->polymorphic)
  	continue;
        param_index = ie->indirect_info->param_index;
!       if (param_index == -1)
  	continue;
  
+       lat = ipcp_get_lattice (info, param_index);
        token = ie->indirect_info->otr_token;
        anc_offset = ie->indirect_info->anc_offset;
        otr_type = ie->indirect_info->otr_type;
        target = NULL_TREE;
!       if (lat->type == IPA_CONST_VALUE)
  	{
! 	  tree binfo = gimple_extract_devirt_binfo_from_cst (lat->constant);
! 	  if (!binfo)
! 	    continue;
  	  binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
  	  if (!binfo)
! 	    continue;
! 	  target = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta,
! 						     false);
! 	}
!       else
! 	{
! 	  int  types_count, j;
  
! 	  if (ipa_param_cannot_devirtualize_p (info, param_index)
! 	      || ipa_param_types_vec_empty (info, param_index))
! 	    continue;
! 
! 	  types_count = VEC_length (tree, info->params[param_index].types);
! 	  for (j = 0; j < types_count; j++)
  	    {
! 	      tree binfo = VEC_index (tree, info->params[param_index].types, j);
! 	      tree d, t;
! 
! 	      binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
! 	      if (!binfo)
! 		{
! 		  target = NULL_TREE;
! 		  break;
! 		}
! 
! 	      t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
! 	      if (!t)
! 		{
! 		  target = NULL_TREE;
! 		  break;
! 		}
! 	      else if (!target)
! 		{
! 		  target = t;
! 		  delta = d;
! 		}
! 	      else if (target != t || !tree_int_cst_equal (delta, d))
! 		{
! 		  target = NULL_TREE;
! 		  break;
! 		}
  	    }
  	}
  
Index: src/gcc/gimple-fold.c
===================================================================
*** src.orig/gcc/gimple-fold.c
--- src/gcc/gimple-fold.c
*************** gimple_adjust_this_by_delta (gimple_stmt
*** 1441,1446 ****
--- 1441,1514 ----
    gimple_call_set_arg (call_stmt, 0, tmp);
  }
  
+ /* Return a binfo to be used for devirtualization of calls based on an object
+    represented by a declaration (i.e. a global or automatically allocated one)
+    or NULL if it cannot be found or is not safe.  CST is expected to be an
+    ADDR_EXPR of such object or the function will return NULL.  Currently it is
+    safe to use such binfo only if it has no base binfo (i.e. no ancestors).  */
+ 
+ tree
+ gimple_extract_devirt_binfo_from_cst (tree cst)
+ {
+   HOST_WIDE_INT offset, size, max_size;
+   tree base, type, expected_type, binfo;
+   bool last_artificial = false;
+ 
+   if (!flag_devirtualize
+       || TREE_CODE (cst) != ADDR_EXPR
+       || TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) != RECORD_TYPE)
+     return NULL_TREE;
+ 
+   cst = TREE_OPERAND (cst, 0);
+   expected_type = TREE_TYPE (cst);
+   base = get_ref_base_and_extent (cst, &offset, &size, &max_size);
+   type = TREE_TYPE (base);
+   if (!DECL_P (base)
+       || max_size == -1
+       || max_size != size
+       || TREE_CODE (type) != RECORD_TYPE)
+     return NULL_TREE;
+ 
+   /* Find the sub-object the constant actually refers to and mark whether it is
+      an artificial one (as opposed to a user-defined one).  */
+   while (true)
+     {
+       HOST_WIDE_INT pos, size;
+       tree fld;
+ 
+       if (TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (expected_type))
+ 	break;
+       if (offset < 0)
+ 	return NULL_TREE;
+ 
+       for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
+ 	{
+ 	  if (TREE_CODE (fld) != FIELD_DECL)
+ 	    continue;
+ 
+ 	  pos = int_bit_position (fld);
+ 	  size = tree_low_cst (DECL_SIZE (fld), 1);
+ 	  if (pos <= offset && (pos + size) > offset)
+ 	    break;
+ 	}
+       if (!fld || TREE_CODE (TREE_TYPE (fld)) != RECORD_TYPE)
+ 	return NULL_TREE;
+ 
+       last_artificial = DECL_ARTIFICIAL (fld);
+       type = TREE_TYPE (fld);
+       offset -= pos;
+     }
+   /* Artifical sub-objects are ancestors, we do not want to use them for
+      devirtualization, at least not here.  */
+   if (last_artificial)
+     return NULL_TREE;
+   binfo = TYPE_BINFO (type);
+   if (!binfo || BINFO_N_BASE_BINFOS (binfo) > 0)
+     return NULL_TREE;
+   else
+     return binfo;
+ }
+ 
  /* Attempt to fold a call statement referenced by the statement iterator GSI.
     The statement may be replaced by another statement, e.g., if the call
     simplifies to a constant value. Return true if any changes were made.
*************** gimple_fold_call (gimple_stmt_iterator *
*** 1469,1478 ****
  
    /* Check for virtual calls that became direct calls.  */
    callee = gimple_call_fn (stmt);
!   if (TREE_CODE (callee) == OBJ_TYPE_REF
!       && gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
      {
!       gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
        return true;
      }
  
--- 1537,1563 ----
  
    /* Check for virtual calls that became direct calls.  */
    callee = gimple_call_fn (stmt);
!   if (TREE_CODE (callee) == OBJ_TYPE_REF)
      {
!       tree binfo, fndecl, delta, obj;
!       HOST_WIDE_INT token;
! 
!       if (gimple_call_addr_fndecl (OBJ_TYPE_REF_EXPR (callee)) != NULL_TREE)
! 	{
! 	  gimple_call_set_fn (stmt, OBJ_TYPE_REF_EXPR (callee));
! 	  return true;
! 	}
! 
!       obj = OBJ_TYPE_REF_OBJECT (callee);
!       binfo = gimple_extract_devirt_binfo_from_cst (obj);
!       if (!binfo)
! 	return false;
!       token = TREE_INT_CST_LOW (OBJ_TYPE_REF_TOKEN (callee));
!       fndecl = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta, false);
!       if (!fndecl)
! 	return false;
!       gcc_assert (integer_zerop (delta));
!       gimple_call_set_fndecl (stmt, fndecl);
        return true;
      }
  
Index: src/gcc/gimple.h
===================================================================
*** src.orig/gcc/gimple.h
--- src/gcc/gimple.h
*************** const char *gimple_decl_printable_name (
*** 898,903 ****
--- 898,904 ----
  bool gimple_fold_call (gimple_stmt_iterator *gsi, bool inplace);
  tree gimple_get_virt_mehtod_for_binfo (HOST_WIDE_INT, tree, tree *, bool);
  void gimple_adjust_this_by_delta (gimple_stmt_iterator *, tree);
+ tree gimple_extract_devirt_binfo_from_cst (tree);
  /* Returns true iff T is a valid GIMPLE statement.  */
  extern bool is_gimple_stmt (tree);
  
Index: src/gcc/testsuite/g++.dg/opt/devirt2.C
===================================================================
*** /dev/null
--- src/gcc/testsuite/g++.dg/opt/devirt2.C
***************
*** 0 ****
--- 1,11 ----
+ // { dg-do compile }
+ // { dg-options "-O2" }
+ // { dg-final { scan-assembler-times "xyzzy" 2 } }
+ 
+ struct S { S(); virtual void xyzzy(); };
+ struct R { int a; S s; R(); };
+ S s;
+ R r;
+ inline void foo(S *p) { p->xyzzy(); }
+ void bar() {foo(&s);}
+ void bah() {foo(&r.s);}
Index: src/gcc/testsuite/g++.dg/ipa/devirt-g-1.C
===================================================================
*** /dev/null
--- src/gcc/testsuite/g++.dg/ipa/devirt-g-1.C
***************
*** 0 ****
--- 1,24 ----
+ // { dg-do compile }
+ // { dg-options "-O2 -fdump-ipa-cp -fdump-tree-optimized" }
+ 
+ struct S { S(); virtual void xyzzy(); void otherstuff(); };
+ struct R { int a; S s; R(); };
+ S s;
+ R r;
+ 
+ void S::xyzzy ()
+ {
+   otherstuff ();
+   otherstuff ();
+ }
+ 
+ static void __attribute__ ((noinline)) foo(S *p) { p->xyzzy(); }
+ void bar() {foo(&s); }
+ 
+ static void __attribute__ ((noinline)) foh(S *p) { p->xyzzy(); }
+ void bah() {foh(&r.s); }
+ 
+ /* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*S::xyzzy" "cp"  } } */
+ /* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "optimized"} } */
+ /* { dg-final { cleanup-ipa-dump "cp" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: src/gcc/testsuite/g++.dg/opt/devirt1.C
===================================================================
*** src.orig/gcc/testsuite/g++.dg/opt/devirt1.C
--- src/gcc/testsuite/g++.dg/opt/devirt1.C
***************
*** 1,6 ****
  // { dg-do compile }
! // { dg-options "-O" }
! // { dg-final { scan-assembler "xyzzy" { xfail *-*-* } } }
  
  struct S { S(); virtual void xyzzy(); };
  inline void foo(S *s) { s->xyzzy(); }
--- 1,6 ----
  // { dg-do compile }
! // { dg-options "-O2" }
! // { dg-final { scan-assembler "xyzzy" } }
  
  struct S { S(); virtual void xyzzy(); };
  inline void foo(S *s) { s->xyzzy(); }