[PATCH 0/4] Devirtualization fix and improvements

[PATCH 0/4] Devirtualization fix and improvements

[Martin Jambor]

Hi,

the following set of patches is a bunch of early fixups and improvements
to the current devirtualization mechanism which are semi-related but are
meant to be applied on top of each other.  One nice thing about them is
that they improve SPEC 2006 473.astar by over 3% with LTO.

More comments above the individual patches.

Thanks,

Martin

[PATCH 2/4] Handle calls to ancestor objects in IPA-CP devirtualization

[Martin Jambor]

[-- Attachment #1: ancestor_otr_analysis.diff --]
[-- Type: text/plain, Size: 11100 bytes --]

Hi,

early inlining can create virtual calls based on the part of an object
that represents an ancestor.  This patch makes ipa-prop analysis able
to recognize such calls and store the required offset along with such
calls (the field is already there for similar purposes of indirect
inlining).  The constant propagation is then made aware of the offset
field and takes it into account when looking up the proper BINFO.

Bootstrapped and tested on x86_64-linux. OK for trunk?

Thanks,

Martin



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

	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Take into
	account anc_offset and otr_type from the indirect edge info.
	* ipa-prop.c (get_ancestor_addr_info): New function.
	(compute_complex_ancestor_jump_func): Assignment analysis moved to
	get_ancestor_addr_info, call it.
	(ipa_note_param_call): Do not initialize information about polymorphic
	calls, return the indirect call graph edge.  Remove the last
	parameter, adjust all callers.
	(ipa_analyze_virtual_call_uses): Process also calls to ancestors of
	parameters.  Initialize polymorphic information in the indirect edge.

	* testsuite/g++.dg/ipa/devirt-7.C: New test.


Index: src/gcc/ipa-cp.c
===================================================================
--- src.orig/gcc/ipa-cp.c
+++ src/gcc/ipa-cp.c
@@ -1246,8 +1246,8 @@ ipcp_process_devirtualization_opportunit
   for (ie = node->indirect_calls; ie; ie = next_ie)
     {
       int param_index, types_count, j;
-      HOST_WIDE_INT token;
-      tree target, delta;
+      HOST_WIDE_INT token, anc_offset;
+      tree target, delta, otr_type;
 
       next_ie = ie->next_callee;
       if (!ie->indirect_info->polymorphic)
@@ -1259,14 +1259,23 @@ ipcp_process_devirtualization_opportunit
 	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;
-	  tree t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
+	  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;
Index: src/gcc/ipa-prop.c
===================================================================
--- src.orig/gcc/ipa-prop.c
+++ src/gcc/ipa-prop.c
@@ -576,6 +576,49 @@ compute_complex_assign_jump_func (struct
     }
 }
 
+/* Extract the base, offset and MEM_REF expression from a statement ASSIGN if
+   it looks like:
+
+   iftmp.1_3 = &obj_2(D)->D.1762;
+
+   The base of the MEM_REF must be a default definition SSA NAME of a
+   parameter.  Return NULL_TREE if it looks otherwise.  If case of success, the
+   whole MEM_REF expression is returned and the offset calculated from any
+   handled components and the MEM_REF itself is stored into *OFFSET.  The whole
+   RHS stripped off the ADDR_EXPR is stored into *OBJ_P.  */
+
+static tree
+get_ancestor_addr_info (gimple assign, tree *obj_p, HOST_WIDE_INT *offset)
+{
+  HOST_WIDE_INT size, max_size;
+  tree expr, parm, obj;
+
+  if (!gimple_assign_single_p (assign))
+    return NULL_TREE;
+  expr = gimple_assign_rhs1 (assign);
+
+  if (TREE_CODE (expr) != ADDR_EXPR)
+    return NULL_TREE;
+  expr = TREE_OPERAND (expr, 0);
+  obj = expr;
+  expr = get_ref_base_and_extent (expr, offset, &size, &max_size);
+
+  if (TREE_CODE (expr) != MEM_REF
+      /* If this is a varying address, punt.  */
+      || max_size == -1
+      || max_size != size)
+    return NULL_TREE;
+  parm = TREE_OPERAND (expr, 0);
+  if (TREE_CODE (parm) != SSA_NAME
+      || !SSA_NAME_IS_DEFAULT_DEF (parm)
+      || *offset < 0)
+    return NULL_TREE;
+
+  *offset += mem_ref_offset (expr).low * BITS_PER_UNIT;
+  *obj_p = obj;
+  return expr;
+}
+
 
 /* Given that an actual argument is an SSA_NAME that is a result of a phi
    statement PHI, try to find out whether NAME is in fact a
@@ -603,7 +646,7 @@ compute_complex_ancestor_jump_func (stru
 				    struct ipa_jump_func *jfunc,
 				    gimple call, gimple phi)
 {
-  HOST_WIDE_INT offset, size, max_size;
+  HOST_WIDE_INT offset;
   gimple assign, cond;
   basic_block phi_bb, assign_bb, cond_bb;
   tree tmp, parm, expr, obj;
@@ -626,29 +669,12 @@ compute_complex_ancestor_jump_func (stru
 
   assign = SSA_NAME_DEF_STMT (tmp);
   assign_bb = gimple_bb (assign);
-  if (!single_pred_p (assign_bb)
-      || !gimple_assign_single_p (assign))
+  if (!single_pred_p (assign_bb))
     return;
-  expr = gimple_assign_rhs1 (assign);
-
-  if (TREE_CODE (expr) != ADDR_EXPR)
-    return;
-  expr = TREE_OPERAND (expr, 0);
-  obj = expr;
-  expr = get_ref_base_and_extent (expr, &offset, &size, &max_size);
-
-  if (TREE_CODE (expr) != MEM_REF
-      /* If this is a varying address, punt.  */
-      || max_size == -1
-      || max_size != size)
+  expr = get_ancestor_addr_info (assign, &obj, &offset);
+  if (!expr)
     return;
-  offset += mem_ref_offset (expr).low * BITS_PER_UNIT;
   parm = TREE_OPERAND (expr, 0);
-  if (TREE_CODE (parm) != SSA_NAME
-      || !SSA_NAME_IS_DEFAULT_DEF (parm)
-      || offset < 0)
-    return;
-
   index = ipa_get_param_decl_index (info, SSA_NAME_VAR (parm));
   if (index < 0)
     return;
@@ -675,7 +701,7 @@ compute_complex_ancestor_jump_func (stru
       jfunc->type = IPA_JF_ANCESTOR;
       jfunc->value.ancestor.formal_id = index;
       jfunc->value.ancestor.offset = offset;
-      jfunc->value.ancestor.type = TREE_TYPE (obj);;
+      jfunc->value.ancestor.type = TREE_TYPE (obj);
     }
 }
 
@@ -1162,29 +1188,20 @@ ipa_is_ssa_with_stmt_def (tree t)
     return false;
 }
 
-/* Find the indirect call graph edge corresponding to STMT and add to it all
-   information necessary to describe a call to a parameter number PARAM_INDEX.
-   NODE is the caller.  POLYMORPHIC should be set to true iff the call is a
-   virtual one.  */
+/* Find the indirect call graph edge corresponding to STMT and mark it as a
+   call to a parameter number PARAM_INDEX.  NODE is the caller.  Return the
+   indirect call graph edge.  */
 
-static void
-ipa_note_param_call (struct cgraph_node *node, int param_index, gimple stmt,
-		     bool polymorphic)
+static struct cgraph_edge *
+ipa_note_param_call (struct cgraph_node *node, int param_index, gimple stmt)
 {
   struct cgraph_edge *cs;
 
   cs = cgraph_edge (node, stmt);
   cs->indirect_info->param_index = param_index;
   cs->indirect_info->anc_offset = 0;
-  cs->indirect_info->polymorphic = polymorphic;
-  if (polymorphic)
-    {
-      tree otr = gimple_call_fn (stmt);
-      tree type, token = OBJ_TYPE_REF_TOKEN (otr);
-      cs->indirect_info->otr_token = tree_low_cst (token, 1);
-      type = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (otr)));
-      cs->indirect_info->otr_type = type;
-    }
+  cs->indirect_info->polymorphic = 0;
+  return cs;
 }
 
 /* Analyze the CALL and examine uses of formal parameters of the caller NODE
@@ -1263,7 +1280,7 @@ ipa_analyze_indirect_call_uses (struct c
       tree var = SSA_NAME_VAR (target);
       index = ipa_get_param_decl_index (info, var);
       if (index >= 0)
-	ipa_note_param_call (node, index, call, false);
+	ipa_note_param_call (node, index, call);
       return;
     }
 
@@ -1361,7 +1378,7 @@ ipa_analyze_indirect_call_uses (struct c
   index = ipa_get_param_decl_index (info, rec);
   if (index >= 0 && !is_parm_modified_before_call (&parms_info[index],
 						   call, rec))
-    ipa_note_param_call (node, index, call, false);
+    ipa_note_param_call (node, index, call);
 
   return;
 }
@@ -1375,24 +1392,48 @@ ipa_analyze_virtual_call_uses (struct cg
 			       struct ipa_node_params *info, gimple call,
 			       tree target)
 {
+  struct cgraph_edge *cs;
+  struct cgraph_indirect_call_info *ii;
   struct ipa_jump_func jfunc;
   tree obj = OBJ_TYPE_REF_OBJECT (target);
-  tree var;
   int index;
+  HOST_WIDE_INT anc_offset;
 
   if (!flag_devirtualize)
     return;
 
-  if (TREE_CODE (obj) != SSA_NAME
-      || !SSA_NAME_IS_DEFAULT_DEF (obj))
+  if (TREE_CODE (obj) != SSA_NAME)
     return;
 
-  var = SSA_NAME_VAR (obj);
-  index = ipa_get_param_decl_index (info, var);
+  if (SSA_NAME_IS_DEFAULT_DEF (obj))
+    {
+      anc_offset = 0;
+      index = ipa_get_param_decl_index (info, SSA_NAME_VAR (obj));
+      if (index < 0
+	  || detect_type_change_ssa (obj, call, &jfunc))
+	return;
+    }
+  else
+    {
+      gimple stmt = SSA_NAME_DEF_STMT (obj);
+      tree expr;
+
+      expr = get_ancestor_addr_info (stmt, &obj, &anc_offset);
+      if (!expr)
+	return;
+      index = ipa_get_param_decl_index (info,
+					SSA_NAME_VAR (TREE_OPERAND (expr, 0)));
+      if (index < 0
+	  || detect_type_change (obj, expr, call, &jfunc, anc_offset))
+	return;
+    }
 
-  if (index >= 0
-      && !detect_type_change_ssa (obj, call, &jfunc))
-    ipa_note_param_call (node, index, call, true);
+  cs = ipa_note_param_call (node, index, call);
+  ii = cs->indirect_info;
+  ii->anc_offset = anc_offset;
+  ii->otr_token = tree_low_cst (OBJ_TYPE_REF_TOKEN (target), 1);
+  ii->otr_type = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (target)));
+  ii->polymorphic = 1;
 }
 
 /* Analyze a call statement CALL whether and how it utilizes formal parameters
Index: src/gcc/testsuite/g++.dg/ipa/devirt-7.C
===================================================================
--- /dev/null
+++ src/gcc/testsuite/g++.dg/ipa/devirt-7.C
@@ -0,0 +1,87 @@
+/* Verify that IPA-CP can do devirtualization even if the virtual call
+   comes from a method that has been early-inlined into a descendant.  */
+/* { dg-do run } */
+/* { dg-options "-O3 -fdump-ipa-cp"  } */
+
+extern "C" void abort (void);
+
+class Distraction
+{
+public:
+  float f;
+  double d;
+  Distraction ()
+  {
+    f = 8.3;
+    d = 10.2;
+  }
+  virtual float bar (float z);
+};
+
+class A
+{
+public:
+  int data;
+  virtual int foo (int i);
+  int middleman_1 (int i);
+};
+
+
+class B : public Distraction, public A
+{
+public:
+  virtual int foo (int i);
+  int middleman_2 (int i);
+  __attribute__ ((noinline)) B();
+};
+
+float Distraction::bar (float z)
+{
+  f += z;
+  return f/2;
+}
+
+int A::foo (int i)
+{
+  return i + 1;
+}
+
+int B::foo (int i)
+{
+  return i + 2;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+int __attribute__ ((always_inline))
+A::middleman_1 (int i)
+{
+  return this->foo (i);
+}
+
+int __attribute__ ((noinline))
+B::middleman_2 (int i)
+{
+  return this->middleman_1 (i);
+}
+
+B::B ()
+{
+}
+
+int main (int argc, char *argv[])
+{
+  class B b;
+  int i;
+
+  for (i = 0; i < get_input(); i++)
+    if (b.middleman_2 (get_input ()) != 3)
+      abort ();
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo"  "cp"  } } */
+/* { dg-final { cleanup-ipa-dump "cp" } } */

Re: [PATCH 2/4] Handle calls to ancestor objects in IPA-CP devirtualization

[Richard Guenther]

On Fri, 15 Apr 2011, Martin Jambor wrote:

> Hi,
> 
> early inlining can create virtual calls based on the part of an object
> that represents an ancestor.  This patch makes ipa-prop analysis able
> to recognize such calls and store the required offset along with such
> calls (the field is already there for similar purposes of indirect
> inlining).  The constant propagation is then made aware of the offset
> field and takes it into account when looking up the proper BINFO.
> 
> Bootstrapped and tested on x86_64-linux. OK for trunk?
> 
> Thanks,
> 
> Martin
> 
> 
> 
> 2011-04-13  Martin Jambor  <mjambor@suse.cz>
> 
> 	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Take into
> 	account anc_offset and otr_type from the indirect edge info.
> 	* ipa-prop.c (get_ancestor_addr_info): New function.
> 	(compute_complex_ancestor_jump_func): Assignment analysis moved to
> 	get_ancestor_addr_info, call it.
> 	(ipa_note_param_call): Do not initialize information about polymorphic
> 	calls, return the indirect call graph edge.  Remove the last
> 	parameter, adjust all callers.
> 	(ipa_analyze_virtual_call_uses): Process also calls to ancestors of
> 	parameters.  Initialize polymorphic information in the indirect edge.
> 
> 	* testsuite/g++.dg/ipa/devirt-7.C: New test.
> 
> 
> Index: src/gcc/ipa-cp.c
> ===================================================================
> --- src.orig/gcc/ipa-cp.c
> +++ src/gcc/ipa-cp.c
> @@ -1246,8 +1246,8 @@ ipcp_process_devirtualization_opportunit
>    for (ie = node->indirect_calls; ie; ie = next_ie)
>      {
>        int param_index, types_count, j;
> -      HOST_WIDE_INT token;
> -      tree target, delta;
> +      HOST_WIDE_INT token, anc_offset;
> +      tree target, delta, otr_type;
>  
>        next_ie = ie->next_callee;
>        if (!ie->indirect_info->polymorphic)
> @@ -1259,14 +1259,23 @@ ipcp_process_devirtualization_opportunit
>  	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;
> -	  tree t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
> +	  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;
> Index: src/gcc/ipa-prop.c
> ===================================================================
> --- src.orig/gcc/ipa-prop.c
> +++ src/gcc/ipa-prop.c
> @@ -576,6 +576,49 @@ compute_complex_assign_jump_func (struct
>      }
>  }
>  
> +/* Extract the base, offset and MEM_REF expression from a statement ASSIGN if
> +   it looks like:
> +
> +   iftmp.1_3 = &obj_2(D)->D.1762;
> +
> +   The base of the MEM_REF must be a default definition SSA NAME of a
> +   parameter.  Return NULL_TREE if it looks otherwise.  If case of success, the
> +   whole MEM_REF expression is returned and the offset calculated from any
> +   handled components and the MEM_REF itself is stored into *OFFSET.  The whole
> +   RHS stripped off the ADDR_EXPR is stored into *OBJ_P.  */
> +
> +static tree
> +get_ancestor_addr_info (gimple assign, tree *obj_p, HOST_WIDE_INT *offset)
> +{
> +  HOST_WIDE_INT size, max_size;
> +  tree expr, parm, obj;
> +
> +  if (!gimple_assign_single_p (assign))
> +    return NULL_TREE;
> +  expr = gimple_assign_rhs1 (assign);
> +
> +  if (TREE_CODE (expr) != ADDR_EXPR)
> +    return NULL_TREE;
> +  expr = TREE_OPERAND (expr, 0);
> +  obj = expr;
> +  expr = get_ref_base_and_extent (expr, offset, &size, &max_size);
> +
> +  if (TREE_CODE (expr) != MEM_REF
> +      /* If this is a varying address, punt.  */
> +      || max_size == -1
> +      || max_size != size)
> +    return NULL_TREE;
> +  parm = TREE_OPERAND (expr, 0);
> +  if (TREE_CODE (parm) != SSA_NAME
> +      || !SSA_NAME_IS_DEFAULT_DEF (parm)

Might be an uninitialized variable, so also check
TREE_CODE (SSA_NAME_VAR (parm)) == PARM_DECL?

> +      || *offset < 0)

Check this above where you check max_size/size.

> +    return NULL_TREE;
> +
> +  *offset += mem_ref_offset (expr).low * BITS_PER_UNIT;

At some point it might be worth switching to
get_addr_base_and_unit_offsets and not use bit but unit offsets
throughout the code.

> +  *obj_p = obj;
> +  return expr;
> +}
> +
>  
>  /* Given that an actual argument is an SSA_NAME that is a result of a phi
>     statement PHI, try to find out whether NAME is in fact a
> @@ -603,7 +646,7 @@ compute_complex_ancestor_jump_func (stru
>  				    struct ipa_jump_func *jfunc,
>  				    gimple call, gimple phi)
>  {
> -  HOST_WIDE_INT offset, size, max_size;
> +  HOST_WIDE_INT offset;
>    gimple assign, cond;
>    basic_block phi_bb, assign_bb, cond_bb;
>    tree tmp, parm, expr, obj;
> @@ -626,29 +669,12 @@ compute_complex_ancestor_jump_func (stru
>  
>    assign = SSA_NAME_DEF_STMT (tmp);
>    assign_bb = gimple_bb (assign);
> -  if (!single_pred_p (assign_bb)
> -      || !gimple_assign_single_p (assign))
> +  if (!single_pred_p (assign_bb))
>      return;
> -  expr = gimple_assign_rhs1 (assign);
> -
> -  if (TREE_CODE (expr) != ADDR_EXPR)
> -    return;
> -  expr = TREE_OPERAND (expr, 0);
> -  obj = expr;
> -  expr = get_ref_base_and_extent (expr, &offset, &size, &max_size);
> -
> -  if (TREE_CODE (expr) != MEM_REF
> -      /* If this is a varying address, punt.  */
> -      || max_size == -1
> -      || max_size != size)
> +  expr = get_ancestor_addr_info (assign, &obj, &offset);
> +  if (!expr)
>      return;
> -  offset += mem_ref_offset (expr).low * BITS_PER_UNIT;
>    parm = TREE_OPERAND (expr, 0);
> -  if (TREE_CODE (parm) != SSA_NAME
> -      || !SSA_NAME_IS_DEFAULT_DEF (parm)
> -      || offset < 0)
> -    return;
> -
>    index = ipa_get_param_decl_index (info, SSA_NAME_VAR (parm));
>    if (index < 0)
>      return;
> @@ -675,7 +701,7 @@ compute_complex_ancestor_jump_func (stru
>        jfunc->type = IPA_JF_ANCESTOR;
>        jfunc->value.ancestor.formal_id = index;
>        jfunc->value.ancestor.offset = offset;
> -      jfunc->value.ancestor.type = TREE_TYPE (obj);;
> +      jfunc->value.ancestor.type = TREE_TYPE (obj);
>      }
>  }
>  
> @@ -1162,29 +1188,20 @@ ipa_is_ssa_with_stmt_def (tree t)
>      return false;
>  }
>  
> -/* Find the indirect call graph edge corresponding to STMT and add to it all
> -   information necessary to describe a call to a parameter number PARAM_INDEX.
> -   NODE is the caller.  POLYMORPHIC should be set to true iff the call is a
> -   virtual one.  */
> +/* Find the indirect call graph edge corresponding to STMT and mark it as a
> +   call to a parameter number PARAM_INDEX.  NODE is the caller.  Return the
> +   indirect call graph edge.  */
>  
> -static void
> -ipa_note_param_call (struct cgraph_node *node, int param_index, gimple stmt,
> -		     bool polymorphic)
> +static struct cgraph_edge *
> +ipa_note_param_call (struct cgraph_node *node, int param_index, gimple stmt)
>  {
>    struct cgraph_edge *cs;
>  
>    cs = cgraph_edge (node, stmt);
>    cs->indirect_info->param_index = param_index;
>    cs->indirect_info->anc_offset = 0;
> -  cs->indirect_info->polymorphic = polymorphic;
> -  if (polymorphic)
> -    {
> -      tree otr = gimple_call_fn (stmt);
> -      tree type, token = OBJ_TYPE_REF_TOKEN (otr);
> -      cs->indirect_info->otr_token = tree_low_cst (token, 1);
> -      type = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (otr)));
> -      cs->indirect_info->otr_type = type;
> -    }
> +  cs->indirect_info->polymorphic = 0;
> +  return cs;
>  }
>  
>  /* Analyze the CALL and examine uses of formal parameters of the caller NODE
> @@ -1263,7 +1280,7 @@ ipa_analyze_indirect_call_uses (struct c
>        tree var = SSA_NAME_VAR (target);
>        index = ipa_get_param_decl_index (info, var);
>        if (index >= 0)
> -	ipa_note_param_call (node, index, call, false);
> +	ipa_note_param_call (node, index, call);
>        return;
>      }
>  
> @@ -1361,7 +1378,7 @@ ipa_analyze_indirect_call_uses (struct c
>    index = ipa_get_param_decl_index (info, rec);
>    if (index >= 0 && !is_parm_modified_before_call (&parms_info[index],
>  						   call, rec))
> -    ipa_note_param_call (node, index, call, false);
> +    ipa_note_param_call (node, index, call);
>  
>    return;
>  }
> @@ -1375,24 +1392,48 @@ ipa_analyze_virtual_call_uses (struct cg
>  			       struct ipa_node_params *info, gimple call,
>  			       tree target)
>  {
> +  struct cgraph_edge *cs;
> +  struct cgraph_indirect_call_info *ii;
>    struct ipa_jump_func jfunc;
>    tree obj = OBJ_TYPE_REF_OBJECT (target);
> -  tree var;
>    int index;
> +  HOST_WIDE_INT anc_offset;
>  
>    if (!flag_devirtualize)
>      return;
>  
> -  if (TREE_CODE (obj) != SSA_NAME
> -      || !SSA_NAME_IS_DEFAULT_DEF (obj))
> +  if (TREE_CODE (obj) != SSA_NAME)
>      return;
>  
> -  var = SSA_NAME_VAR (obj);
> -  index = ipa_get_param_decl_index (info, var);
> +  if (SSA_NAME_IS_DEFAULT_DEF (obj))

Check for PARM_DECL.

Otherwise ok.

Thanks,
Richard.

> +    {
> +      anc_offset = 0;
> +      index = ipa_get_param_decl_index (info, SSA_NAME_VAR (obj));
> +      if (index < 0
> +	  || detect_type_change_ssa (obj, call, &jfunc))
> +	return;
> +    }
> +  else
> +    {
> +      gimple stmt = SSA_NAME_DEF_STMT (obj);
> +      tree expr;
> +
> +      expr = get_ancestor_addr_info (stmt, &obj, &anc_offset);
> +      if (!expr)
> +	return;
> +      index = ipa_get_param_decl_index (info,
> +					SSA_NAME_VAR (TREE_OPERAND (expr, 0)));
> +      if (index < 0
> +	  || detect_type_change (obj, expr, call, &jfunc, anc_offset))
> +	return;
> +    }
>  
> -  if (index >= 0
> -      && !detect_type_change_ssa (obj, call, &jfunc))
> -    ipa_note_param_call (node, index, call, true);
> +  cs = ipa_note_param_call (node, index, call);
> +  ii = cs->indirect_info;
> +  ii->anc_offset = anc_offset;
> +  ii->otr_token = tree_low_cst (OBJ_TYPE_REF_TOKEN (target), 1);
> +  ii->otr_type = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (target)));
> +  ii->polymorphic = 1;
>  }
>  
>  /* Analyze a call statement CALL whether and how it utilizes formal parameters
> Index: src/gcc/testsuite/g++.dg/ipa/devirt-7.C
> ===================================================================
> --- /dev/null
> +++ src/gcc/testsuite/g++.dg/ipa/devirt-7.C
> @@ -0,0 +1,87 @@
> +/* Verify that IPA-CP can do devirtualization even if the virtual call
> +   comes from a method that has been early-inlined into a descendant.  */
> +/* { dg-do run } */
> +/* { dg-options "-O3 -fdump-ipa-cp"  } */
> +
> +extern "C" void abort (void);
> +
> +class Distraction
> +{
> +public:
> +  float f;
> +  double d;
> +  Distraction ()
> +  {
> +    f = 8.3;
> +    d = 10.2;
> +  }
> +  virtual float bar (float z);
> +};
> +
> +class A
> +{
> +public:
> +  int data;
> +  virtual int foo (int i);
> +  int middleman_1 (int i);
> +};
> +
> +
> +class B : public Distraction, public A
> +{
> +public:
> +  virtual int foo (int i);
> +  int middleman_2 (int i);
> +  __attribute__ ((noinline)) B();
> +};
> +
> +float Distraction::bar (float z)
> +{
> +  f += z;
> +  return f/2;
> +}
> +
> +int A::foo (int i)
> +{
> +  return i + 1;
> +}
> +
> +int B::foo (int i)
> +{
> +  return i + 2;
> +}
> +
> +int __attribute__ ((noinline,noclone)) get_input(void)
> +{
> +  return 1;
> +}
> +
> +int __attribute__ ((always_inline))
> +A::middleman_1 (int i)
> +{
> +  return this->foo (i);
> +}
> +
> +int __attribute__ ((noinline))
> +B::middleman_2 (int i)
> +{
> +  return this->middleman_1 (i);
> +}
> +
> +B::B ()
> +{
> +}
> +
> +int main (int argc, char *argv[])
> +{
> +  class B b;
> +  int i;
> +
> +  for (i = 0; i < get_input(); i++)
> +    if (b.middleman_2 (get_input ()) != 3)
> +      abort ();
> +  return 0;
> +}
> +
> +/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo"  "cp"  } } */
> +/* { dg-final { cleanup-ipa-dump "cp" } } */
> 
> 

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

Re: [PATCH 2/4] Handle calls to ancestor objects in IPA-CP devirtualization

[Martin Jambor]

Hi,

On Fri, Apr 15, 2011 at 05:26:44PM +0200, Richard Guenther wrote:
> On Fri, 15 Apr 2011, Martin Jambor wrote:
> 
> > Hi,
> > 
> > early inlining can create virtual calls based on the part of an object
> > that represents an ancestor.  This patch makes ipa-prop analysis able
> > to recognize such calls and store the required offset along with such
> > calls (the field is already there for similar purposes of indirect
> > inlining).  The constant propagation is then made aware of the offset
> > field and takes it into account when looking up the proper BINFO.
> > 
> > Bootstrapped and tested on x86_64-linux. OK for trunk?
> > 
> > Thanks,
> > 
> > Martin
> > 
> > 
> > 
> > 2011-04-13  Martin Jambor  <mjambor@suse.cz>
> > 
> > 	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Take into
> > 	account anc_offset and otr_type from the indirect edge info.
> > 	* ipa-prop.c (get_ancestor_addr_info): New function.
> > 	(compute_complex_ancestor_jump_func): Assignment analysis moved to
> > 	get_ancestor_addr_info, call it.
> > 	(ipa_note_param_call): Do not initialize information about polymorphic
> > 	calls, return the indirect call graph edge.  Remove the last
> > 	parameter, adjust all callers.
> > 	(ipa_analyze_virtual_call_uses): Process also calls to ancestors of
> > 	parameters.  Initialize polymorphic information in the indirect edge.
> > 
> > 	* testsuite/g++.dg/ipa/devirt-7.C: New test.
> > 
> > 

...

> > Index: src/gcc/ipa-prop.c
> > ===================================================================
> > --- src.orig/gcc/ipa-prop.c
> > +++ src/gcc/ipa-prop.c
> > @@ -576,6 +576,49 @@ compute_complex_assign_jump_func (struct
> >      }
> >  }
> >  
> > +/* Extract the base, offset and MEM_REF expression from a statement ASSIGN if
> > +   it looks like:
> > +
> > +   iftmp.1_3 = &obj_2(D)->D.1762;
> > +
> > +   The base of the MEM_REF must be a default definition SSA NAME of a
> > +   parameter.  Return NULL_TREE if it looks otherwise.  If case of success, the
> > +   whole MEM_REF expression is returned and the offset calculated from any
> > +   handled components and the MEM_REF itself is stored into *OFFSET.  The whole
> > +   RHS stripped off the ADDR_EXPR is stored into *OBJ_P.  */
> > +
> > +static tree
> > +get_ancestor_addr_info (gimple assign, tree *obj_p, HOST_WIDE_INT *offset)
> > +{
> > +  HOST_WIDE_INT size, max_size;
> > +  tree expr, parm, obj;
> > +
> > +  if (!gimple_assign_single_p (assign))
> > +    return NULL_TREE;
> > +  expr = gimple_assign_rhs1 (assign);
> > +
> > +  if (TREE_CODE (expr) != ADDR_EXPR)
> > +    return NULL_TREE;
> > +  expr = TREE_OPERAND (expr, 0);
> > +  obj = expr;
> > +  expr = get_ref_base_and_extent (expr, offset, &size, &max_size);
> > +
> > +  if (TREE_CODE (expr) != MEM_REF
> > +      /* If this is a varying address, punt.  */
> > +      || max_size == -1
> > +      || max_size != size)
> > +    return NULL_TREE;
> > +  parm = TREE_OPERAND (expr, 0);
> > +  if (TREE_CODE (parm) != SSA_NAME
> > +      || !SSA_NAME_IS_DEFAULT_DEF (parm)
> 
> Might be an uninitialized variable, so also check
> TREE_CODE (SSA_NAME_VAR (parm)) == PARM_DECL?
> 

This was already handled by checking the return value of
ipa_get_param_decl_index but I guess that the code will be more
readable with that check explicit and an assert that
ipa_get_param_decl_index can indeed find an index for the decl so I
changed both places accordingly.

> > +      || *offset < 0)
> 
> Check this above where you check max_size/size.

OK

...

> > -  var = SSA_NAME_VAR (obj);
> > -  index = ipa_get_param_decl_index (info, var);
> > +  if (SSA_NAME_IS_DEFAULT_DEF (obj))
> 
> Check for PARM_DECL.
> 

Like above.

> Otherwise ok.
> 

Thanks, this is what I'm currently testing and what I intend to commit
if all goes well.

Martin


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

	* ipa-cp.c (ipcp_process_devirtualization_opportunities): Take into
	account anc_offset and otr_type from the indirect edge info.
	* ipa-prop.c (get_ancestor_addr_info): New function.
	(compute_complex_ancestor_jump_func): Assignment analysis moved to
	get_ancestor_addr_info, call it.
	(ipa_note_param_call): Do not initialize information about polymorphic
	calls, return the indirect call graph edge.  Remove the last
	parameter, adjust all callers.
	(ipa_analyze_virtual_call_uses): Process also calls to ancestors of
	parameters.  Initialize polymorphic information in the indirect edge.

	* testsuite/g++.dg/ipa/devirt-7.C: New test.


Index: src/gcc/ipa-cp.c
===================================================================
*** src.orig/gcc/ipa-cp.c
--- src/gcc/ipa-cp.c
*************** ipcp_process_devirtualization_opportunit
*** 1247,1254 ****
    for (ie = node->indirect_calls; ie; ie = next_ie)
      {
        int param_index, types_count, j;
!       HOST_WIDE_INT token;
!       tree target, delta;
  
        next_ie = ie->next_callee;
        if (!ie->indirect_info->polymorphic)
--- 1247,1254 ----
    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)
*************** ipcp_process_devirtualization_opportunit
*** 1260,1273 ****
  	continue;
  
        token = ie->indirect_info->otr_token;
        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;
! 	  tree t = gimple_get_virt_mehtod_for_binfo (token, binfo, &d, true);
  
  	  if (!t)
  	    {
  	      target = NULL_TREE;
--- 1260,1282 ----
  	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;
Index: src/gcc/ipa-prop.c
===================================================================
*** src.orig/gcc/ipa-prop.c
--- src/gcc/ipa-prop.c
*************** compute_complex_assign_jump_func (struct
*** 576,581 ****
--- 576,625 ----
      }
  }
  
+ /* Extract the base, offset and MEM_REF expression from a statement ASSIGN if
+    it looks like:
+ 
+    iftmp.1_3 = &obj_2(D)->D.1762;
+ 
+    The base of the MEM_REF must be a default definition SSA NAME of a
+    parameter.  Return NULL_TREE if it looks otherwise.  If case of success, the
+    whole MEM_REF expression is returned and the offset calculated from any
+    handled components and the MEM_REF itself is stored into *OFFSET.  The whole
+    RHS stripped off the ADDR_EXPR is stored into *OBJ_P.  */
+ 
+ static tree
+ get_ancestor_addr_info (gimple assign, tree *obj_p, HOST_WIDE_INT *offset)
+ {
+   HOST_WIDE_INT size, max_size;
+   tree expr, parm, obj;
+ 
+   if (!gimple_assign_single_p (assign))
+     return NULL_TREE;
+   expr = gimple_assign_rhs1 (assign);
+ 
+   if (TREE_CODE (expr) != ADDR_EXPR)
+     return NULL_TREE;
+   expr = TREE_OPERAND (expr, 0);
+   obj = expr;
+   expr = get_ref_base_and_extent (expr, offset, &size, &max_size);
+ 
+   if (TREE_CODE (expr) != MEM_REF
+       /* If this is a varying address, punt.  */
+       || max_size == -1
+       || max_size != size
+       || *offset < 0)
+     return NULL_TREE;
+   parm = TREE_OPERAND (expr, 0);
+   if (TREE_CODE (parm) != SSA_NAME
+       || !SSA_NAME_IS_DEFAULT_DEF (parm)
+       || TREE_CODE (SSA_NAME_VAR (parm)) != PARM_DECL)
+     return NULL_TREE;
+ 
+   *offset += mem_ref_offset (expr).low * BITS_PER_UNIT;
+   *obj_p = obj;
+   return expr;
+ }
+ 
  
  /* Given that an actual argument is an SSA_NAME that is a result of a phi
     statement PHI, try to find out whether NAME is in fact a
*************** compute_complex_ancestor_jump_func (stru
*** 603,609 ****
  				    struct ipa_jump_func *jfunc,
  				    gimple call, gimple phi)
  {
!   HOST_WIDE_INT offset, size, max_size;
    gimple assign, cond;
    basic_block phi_bb, assign_bb, cond_bb;
    tree tmp, parm, expr, obj;
--- 647,653 ----
  				    struct ipa_jump_func *jfunc,
  				    gimple call, gimple phi)
  {
!   HOST_WIDE_INT offset;
    gimple assign, cond;
    basic_block phi_bb, assign_bb, cond_bb;
    tree tmp, parm, expr, obj;
*************** compute_complex_ancestor_jump_func (stru
*** 626,657 ****
  
    assign = SSA_NAME_DEF_STMT (tmp);
    assign_bb = gimple_bb (assign);
!   if (!single_pred_p (assign_bb)
!       || !gimple_assign_single_p (assign))
      return;
!   expr = gimple_assign_rhs1 (assign);
! 
!   if (TREE_CODE (expr) != ADDR_EXPR)
!     return;
!   expr = TREE_OPERAND (expr, 0);
!   obj = expr;
!   expr = get_ref_base_and_extent (expr, &offset, &size, &max_size);
! 
!   if (TREE_CODE (expr) != MEM_REF
!       /* If this is a varying address, punt.  */
!       || max_size == -1
!       || max_size != size)
      return;
-   offset += mem_ref_offset (expr).low * BITS_PER_UNIT;
    parm = TREE_OPERAND (expr, 0);
-   if (TREE_CODE (parm) != SSA_NAME
-       || !SSA_NAME_IS_DEFAULT_DEF (parm)
-       || offset < 0)
-     return;
- 
    index = ipa_get_param_decl_index (info, SSA_NAME_VAR (parm));
!   if (index < 0)
!     return;
  
    cond_bb = single_pred (assign_bb);
    cond = last_stmt (cond_bb);
--- 670,683 ----
  
    assign = SSA_NAME_DEF_STMT (tmp);
    assign_bb = gimple_bb (assign);
!   if (!single_pred_p (assign_bb))
      return;
!   expr = get_ancestor_addr_info (assign, &obj, &offset);
!   if (!expr)
      return;
    parm = TREE_OPERAND (expr, 0);
    index = ipa_get_param_decl_index (info, SSA_NAME_VAR (parm));
!   gcc_assert (index >= 0);
  
    cond_bb = single_pred (assign_bb);
    cond = last_stmt (cond_bb);
*************** compute_complex_ancestor_jump_func (stru
*** 675,681 ****
        jfunc->type = IPA_JF_ANCESTOR;
        jfunc->value.ancestor.formal_id = index;
        jfunc->value.ancestor.offset = offset;
!       jfunc->value.ancestor.type = TREE_TYPE (obj);;
      }
  }
  
--- 701,707 ----
        jfunc->type = IPA_JF_ANCESTOR;
        jfunc->value.ancestor.formal_id = index;
        jfunc->value.ancestor.offset = offset;
!       jfunc->value.ancestor.type = TREE_TYPE (obj);
      }
  }
  
*************** ipa_is_ssa_with_stmt_def (tree t)
*** 1162,1190 ****
      return false;
  }
  
! /* Find the indirect call graph edge corresponding to STMT and add to it all
!    information necessary to describe a call to a parameter number PARAM_INDEX.
!    NODE is the caller.  POLYMORPHIC should be set to true iff the call is a
!    virtual one.  */
  
! static void
! ipa_note_param_call (struct cgraph_node *node, int param_index, gimple stmt,
! 		     bool polymorphic)
  {
    struct cgraph_edge *cs;
  
    cs = cgraph_edge (node, stmt);
    cs->indirect_info->param_index = param_index;
    cs->indirect_info->anc_offset = 0;
!   cs->indirect_info->polymorphic = polymorphic;
!   if (polymorphic)
!     {
!       tree otr = gimple_call_fn (stmt);
!       tree type, token = OBJ_TYPE_REF_TOKEN (otr);
!       cs->indirect_info->otr_token = tree_low_cst (token, 1);
!       type = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (otr)));
!       cs->indirect_info->otr_type = type;
!     }
  }
  
  /* Analyze the CALL and examine uses of formal parameters of the caller NODE
--- 1188,1207 ----
      return false;
  }
  
! /* Find the indirect call graph edge corresponding to STMT and mark it as a
!    call to a parameter number PARAM_INDEX.  NODE is the caller.  Return the
!    indirect call graph edge.  */
  
! static struct cgraph_edge *
! ipa_note_param_call (struct cgraph_node *node, int param_index, gimple stmt)
  {
    struct cgraph_edge *cs;
  
    cs = cgraph_edge (node, stmt);
    cs->indirect_info->param_index = param_index;
    cs->indirect_info->anc_offset = 0;
!   cs->indirect_info->polymorphic = 0;
!   return cs;
  }
  
  /* Analyze the CALL and examine uses of formal parameters of the caller NODE
*************** ipa_analyze_indirect_call_uses (struct c
*** 1263,1269 ****
        tree var = SSA_NAME_VAR (target);
        index = ipa_get_param_decl_index (info, var);
        if (index >= 0)
! 	ipa_note_param_call (node, index, call, false);
        return;
      }
  
--- 1280,1286 ----
        tree var = SSA_NAME_VAR (target);
        index = ipa_get_param_decl_index (info, var);
        if (index >= 0)
! 	ipa_note_param_call (node, index, call);
        return;
      }
  
*************** ipa_analyze_indirect_call_uses (struct c
*** 1361,1367 ****
    index = ipa_get_param_decl_index (info, rec);
    if (index >= 0 && !is_parm_modified_before_call (&parms_info[index],
  						   call, rec))
!     ipa_note_param_call (node, index, call, false);
  
    return;
  }
--- 1378,1384 ----
    index = ipa_get_param_decl_index (info, rec);
    if (index >= 0 && !is_parm_modified_before_call (&parms_info[index],
  						   call, rec))
!     ipa_note_param_call (node, index, call);
  
    return;
  }
*************** ipa_analyze_virtual_call_uses (struct cg
*** 1375,1398 ****
  			       struct ipa_node_params *info, gimple call,
  			       tree target)
  {
    struct ipa_jump_func jfunc;
    tree obj = OBJ_TYPE_REF_OBJECT (target);
-   tree var;
    int index;
  
    if (!flag_devirtualize)
      return;
  
!   if (TREE_CODE (obj) != SSA_NAME
!       || !SSA_NAME_IS_DEFAULT_DEF (obj))
      return;
  
!   var = SSA_NAME_VAR (obj);
!   index = ipa_get_param_decl_index (info, var);
  
!   if (index >= 0
!       && !detect_type_change_ssa (obj, call, &jfunc))
!     ipa_note_param_call (node, index, call, true);
  }
  
  /* Analyze a call statement CALL whether and how it utilizes formal parameters
--- 1392,1442 ----
  			       struct ipa_node_params *info, gimple call,
  			       tree target)
  {
+   struct cgraph_edge *cs;
+   struct cgraph_indirect_call_info *ii;
    struct ipa_jump_func jfunc;
    tree obj = OBJ_TYPE_REF_OBJECT (target);
    int index;
+   HOST_WIDE_INT anc_offset;
  
    if (!flag_devirtualize)
      return;
  
!   if (TREE_CODE (obj) != SSA_NAME)
      return;
  
!   if (SSA_NAME_IS_DEFAULT_DEF (obj))
!     {
!       if (TREE_CODE (SSA_NAME_VAR (obj)) != PARM_DECL)
! 	return;
! 
!       anc_offset = 0;
!       index = ipa_get_param_decl_index (info, SSA_NAME_VAR (obj));
!       gcc_assert (index >= 0);
!       if (detect_type_change_ssa (obj, call, &jfunc))
! 	return;
!     }
!   else
!     {
!       gimple stmt = SSA_NAME_DEF_STMT (obj);
!       tree expr;
! 
!       expr = get_ancestor_addr_info (stmt, &obj, &anc_offset);
!       if (!expr)
! 	return;
!       index = ipa_get_param_decl_index (info,
! 					SSA_NAME_VAR (TREE_OPERAND (expr, 0)));
!       gcc_assert (index >= 0);
!       if (detect_type_change (obj, expr, call, &jfunc, anc_offset))
! 	return;
!     }
  
!   cs = ipa_note_param_call (node, index, call);
!   ii = cs->indirect_info;
!   ii->anc_offset = anc_offset;
!   ii->otr_token = tree_low_cst (OBJ_TYPE_REF_TOKEN (target), 1);
!   ii->otr_type = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (target)));
!   ii->polymorphic = 1;
  }
  
  /* Analyze a call statement CALL whether and how it utilizes formal parameters
Index: src/gcc/testsuite/g++.dg/ipa/devirt-7.C
===================================================================
*** /dev/null
--- src/gcc/testsuite/g++.dg/ipa/devirt-7.C
***************
*** 0 ****
--- 1,87 ----
+ /* Verify that IPA-CP can do devirtualization even if the virtual call
+    comes from a method that has been early-inlined into a descendant.  */
+ /* { dg-do run } */
+ /* { dg-options "-O3 -fdump-ipa-cp"  } */
+ 
+ extern "C" void abort (void);
+ 
+ class Distraction
+ {
+ public:
+   float f;
+   double d;
+   Distraction ()
+   {
+     f = 8.3;
+     d = 10.2;
+   }
+   virtual float bar (float z);
+ };
+ 
+ class A
+ {
+ public:
+   int data;
+   virtual int foo (int i);
+   int middleman_1 (int i);
+ };
+ 
+ 
+ class B : public Distraction, public A
+ {
+ public:
+   virtual int foo (int i);
+   int middleman_2 (int i);
+   __attribute__ ((noinline)) B();
+ };
+ 
+ float Distraction::bar (float z)
+ {
+   f += z;
+   return f/2;
+ }
+ 
+ int A::foo (int i)
+ {
+   return i + 1;
+ }
+ 
+ int B::foo (int i)
+ {
+   return i + 2;
+ }
+ 
+ int __attribute__ ((noinline,noclone)) get_input(void)
+ {
+   return 1;
+ }
+ 
+ int __attribute__ ((always_inline))
+ A::middleman_1 (int i)
+ {
+   return this->foo (i);
+ }
+ 
+ int __attribute__ ((noinline))
+ B::middleman_2 (int i)
+ {
+   return this->middleman_1 (i);
+ }
+ 
+ B::B ()
+ {
+ }
+ 
+ int main (int argc, char *argv[])
+ {
+   class B b;
+   int i;
+ 
+   for (i = 0; i < get_input(); i++)
+     if (b.middleman_2 (get_input ()) != 3)
+       abort ();
+   return 0;
+ }
+ 
+ /* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*B::foo"  "cp"  } } */
+ /* { dg-final { cleanup-ipa-dump "cp" } } */

[PATCH 4/4] Devirtualization based on global objects

[Martin Jambor]

[-- Attachment #1: globals_devirtualization.diff --]
[-- Type: text/plain, Size: 10378 bytes --]

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/ipa-cp.c
===================================================================
--- src.orig/gcc/ipa-cp.c
+++ src/gcc/ipa-cp.c
@@ -1245,51 +1245,71 @@ ipcp_process_devirtualization_opportunit
 
   for (ie = node->indirect_calls; ie; ie = next_ie)
     {
-      int param_index, types_count, j;
+      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
-	  || ipa_param_cannot_devirtualize_p (info, param_index)
-	  || ipa_param_types_vec_empty (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;
-      types_count = VEC_length (tree, info->params[param_index].types);
-      for (j = 0; j < types_count; j++)
+      if (lat->type == IPA_CONST_VALUE)
 	{
-	  tree binfo = VEC_index (tree, info->params[param_index].types, j);
-	  tree d, t;
-
+	  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)
-	    {
-	      target = NULL_TREE;
-	      break;
-	    }
+	    continue;
+	  target = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta,
+						     false);
+	}
+      else
+	{
+	  int  types_count, j;
 
-	  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))
+	  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++)
 	    {
-	      target = NULL_TREE;
-	      break;
+	      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
@@ -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;
+    }
+  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);
+  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;
+}
+
+
 /* 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.
@@ -1463,6 +1552,13 @@ gimple_fold_call (gimple_stmt_iterator *
 	  return true;
 	}
     }
+  else
+    {
+      callee = gimple_call_fn (stmt);
+      if (TREE_CODE (callee) == OBJ_TYPE_REF)
+	return gimple_fold_obj_type_ref_call (gsi);
+    }
+
   return false;
 }
 
Index: src/gcc/gimple.h
===================================================================
--- src.orig/gcc/gimple.h
+++ src/gcc/gimple.h
@@ -894,6 +894,7 @@ const char *gimple_decl_printable_name (
 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,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,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 +1,6 @@
 // { dg-do compile }
-// { dg-options "-O" }
-// { dg-final { scan-assembler "xyzzy" { xfail *-*-* } } }
+// { dg-options "-O2" }
+// { dg-final { scan-assembler "xyzzy" } }
 
 struct S { S(); virtual void xyzzy(); };
 inline void foo(S *s) { s->xyzzy(); }

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

[Richard Guenther]

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/ipa-cp.c
> ===================================================================
> --- src.orig/gcc/ipa-cp.c
> +++ src/gcc/ipa-cp.c
> @@ -1245,51 +1245,71 @@ ipcp_process_devirtualization_opportunit
>  
>    for (ie = node->indirect_calls; ie; ie = next_ie)
>      {
> -      int param_index, types_count, j;
> +      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
> -	  || ipa_param_cannot_devirtualize_p (info, param_index)
> -	  || ipa_param_types_vec_empty (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;
> -      types_count = VEC_length (tree, info->params[param_index].types);
> -      for (j = 0; j < types_count; j++)
> +      if (lat->type == IPA_CONST_VALUE)
>  	{
> -	  tree binfo = VEC_index (tree, info->params[param_index].types, j);
> -	  tree d, t;
> -
> +	  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)
> -	    {
> -	      target = NULL_TREE;
> -	      break;
> -	    }
> +	    continue;
> +	  target = gimple_get_virt_mehtod_for_binfo (token, binfo, &delta,
> +						     false);
> +	}
> +      else
> +	{
> +	  int  types_count, j;
>  
> -	  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))
> +	  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++)
>  	    {
> -	      target = NULL_TREE;
> -	      break;
> +	      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
> @@ -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?).  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.

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

Thanks,
Richard.

> +  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;
> +}
> +
> +
>  /* 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.
> @@ -1463,6 +1552,13 @@ gimple_fold_call (gimple_stmt_iterator *
>  	  return true;
>  	}
>      }
> +  else
> +    {
> +      callee = gimple_call_fn (stmt);
> +      if (TREE_CODE (callee) == OBJ_TYPE_REF)
> +	return gimple_fold_obj_type_ref_call (gsi);
> +    }
> +
>    return false;
>  }
>  
> Index: src/gcc/gimple.h
> ===================================================================
> --- src.orig/gcc/gimple.h
> +++ src/gcc/gimple.h
> @@ -894,6 +894,7 @@ const char *gimple_decl_printable_name (
>  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,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,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 +1,6 @@
>  // { dg-do compile }
> -// { dg-options "-O" }
> -// { dg-final { scan-assembler "xyzzy" { xfail *-*-* } } }
> +// { dg-options "-O2" }
> +// { dg-final { scan-assembler "xyzzy" } }
>  
>  struct S { S(); virtual void xyzzy(); };
>  inline void foo(S *s) { s->xyzzy(); }
> 
> 

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

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

[Martin Jambor]

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(); }

[PATCH 3/4] Simple relaxation of dynamic type change detection routine

[Martin Jambor]

[-- Attachment #1: relax_dyn_type_non_pointers.diff --]
[-- Type: text/plain, Size: 2069 bytes --]

Hi,

in order to speed up astar, I had to persuade the function that
decides whether a statement potentially modifies the dynamic type of
an object by storing a new value to the VMT pointer to consider the
following statement harmless (all types are integers of some sort):

MEM[(i32 *)b2arp_3(D) + 8B] = 0;

I'd like to experiment with this routine a bit more once I have some
other IPA-CP infrastructure in place but at the moment I opted for a
simple solution:  All scalar non-pointer stores are deemed safe.

VMT pointer is a compiler generated field which is a pointer so legal
user code is not able to store stuff there through some fancy type
casts and compiler generated code should have no reason whatsoever to
that either.  Therefore I believe this change is safe and useful.

I have bootstrapped and tested the patch on x886_64-linux.  OK for
trunk?

Thanks,

Martin



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

	* ipa-prop.c (stmt_may_be_vtbl_ptr_store): Return false for scalar
	non-pointer assignments.

Index: src/gcc/ipa-prop.c
===================================================================
--- src.orig/gcc/ipa-prop.c
+++ src/gcc/ipa-prop.c
@@ -405,13 +405,18 @@ stmt_may_be_vtbl_ptr_store (gimple stmt)
     {
       tree lhs = gimple_assign_lhs (stmt);
 
-      if (TREE_CODE (lhs) == COMPONENT_REF
-	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
-	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
+      if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
+	{
+	  if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
 	    return false;
-      /* In the future we might want to use get_base_ref_and_offset to find
-	 if there is a field corresponding to the offset and if so, proceed
-	 almost like if it was a component ref.  */
+
+	  if (TREE_CODE (lhs) == COMPONENT_REF
+	      && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
+	    return false;
+	  /* In the future we might want to use get_base_ref_and_offset to find
+	     if there is a field corresponding to the offset and if so, proceed
+	     almost like if it was a component ref.  */
+	}
     }
   return true;
 }

Re: [PATCH 3/4] Simple relaxation of dynamic type change detection routine

[Richard Guenther]

On Fri, 15 Apr 2011, Martin Jambor wrote:

> Hi,
> 
> in order to speed up astar, I had to persuade the function that
> decides whether a statement potentially modifies the dynamic type of
> an object by storing a new value to the VMT pointer to consider the
> following statement harmless (all types are integers of some sort):
> 
> MEM[(i32 *)b2arp_3(D) + 8B] = 0;
> 
> I'd like to experiment with this routine a bit more once I have some
> other IPA-CP infrastructure in place but at the moment I opted for a
> simple solution:  All scalar non-pointer stores are deemed safe.
> 
> VMT pointer is a compiler generated field which is a pointer so legal
> user code is not able to store stuff there through some fancy type
> casts and compiler generated code should have no reason whatsoever to
> that either.  Therefore I believe this change is safe and useful.
> 
> I have bootstrapped and tested the patch on x886_64-linux.  OK for
> trunk?

I think this should be only done for -fstrict-aliasing.

Ok with that change.
Richard.

> Thanks,
> 
> Martin
> 
> 
> 
> 2011-04-14  Martin Jambor  <mjambor@suse.cz>
> 
> 	* ipa-prop.c (stmt_may_be_vtbl_ptr_store): Return false for scalar
> 	non-pointer assignments.
> 
> Index: src/gcc/ipa-prop.c
> ===================================================================
> --- src.orig/gcc/ipa-prop.c
> +++ src/gcc/ipa-prop.c
> @@ -405,13 +405,18 @@ stmt_may_be_vtbl_ptr_store (gimple stmt)
>      {
>        tree lhs = gimple_assign_lhs (stmt);
>  
> -      if (TREE_CODE (lhs) == COMPONENT_REF
> -	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
> -	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
> +      if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
> +	{
> +	  if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
>  	    return false;
> -      /* In the future we might want to use get_base_ref_and_offset to find
> -	 if there is a field corresponding to the offset and if so, proceed
> -	 almost like if it was a component ref.  */
> +
> +	  if (TREE_CODE (lhs) == COMPONENT_REF
> +	      && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
> +	    return false;
> +	  /* In the future we might want to use get_base_ref_and_offset to find
> +	     if there is a field corresponding to the offset and if so, proceed
> +	     almost like if it was a component ref.  */
> +	}
>      }
>    return true;
>  }
> 
> 

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

Re: [PATCH 3/4] Simple relaxation of dynamic type change detection routine

[Martin Jambor]

Hi,

On Fri, Apr 15, 2011 at 05:28:49PM +0200, Richard Guenther wrote:
> On Fri, 15 Apr 2011, Martin Jambor wrote:
> 
> > Hi,
> > 
> > in order to speed up astar, I had to persuade the function that
> > decides whether a statement potentially modifies the dynamic type of
> > an object by storing a new value to the VMT pointer to consider the
> > following statement harmless (all types are integers of some sort):
> > 
> > MEM[(i32 *)b2arp_3(D) + 8B] = 0;
> > 
> > I'd like to experiment with this routine a bit more once I have some
> > other IPA-CP infrastructure in place but at the moment I opted for a
> > simple solution:  All scalar non-pointer stores are deemed safe.
> > 
> > VMT pointer is a compiler generated field which is a pointer so legal
> > user code is not able to store stuff there through some fancy type
> > casts and compiler generated code should have no reason whatsoever to
> > that either.  Therefore I believe this change is safe and useful.
> > 
> > I have bootstrapped and tested the patch on x886_64-linux.  OK for
> > trunk?
> 
> I think this should be only done for -fstrict-aliasing.
> 
> Ok with that change.

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

Thanks,

Martin

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

	* ipa-prop.c (stmt_may_be_vtbl_ptr_store): Return false for scalar
	non-pointer assignments.

Index: src/gcc/ipa-prop.c
===================================================================
*** src.orig/gcc/ipa-prop.c
--- src/gcc/ipa-prop.c
*************** stmt_may_be_vtbl_ptr_store (gimple stmt)
*** 405,417 ****
      {
        tree lhs = gimple_assign_lhs (stmt);
  
!       if (TREE_CODE (lhs) == COMPONENT_REF
! 	  && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
! 	  && !AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
  	    return false;
!       /* In the future we might want to use get_base_ref_and_offset to find
! 	 if there is a field corresponding to the offset and if so, proceed
! 	 almost like if it was a component ref.  */
      }
    return true;
  }
--- 405,423 ----
      {
        tree lhs = gimple_assign_lhs (stmt);
  
!       if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
! 	{
! 	  if (flag_strict_aliasing
! 	      && !POINTER_TYPE_P (TREE_TYPE (lhs)))
  	    return false;
! 
! 	  if (TREE_CODE (lhs) == COMPONENT_REF
! 	      && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
! 	    return false;
! 	  /* In the future we might want to use get_base_ref_and_offset to find
! 	     if there is a field corresponding to the offset and if so, proceed
! 	     almost like if it was a component ref.  */
! 	}
      }
    return true;
  }

[PATCH 1/4] Remove usesess and wrong code from ipa_analyze_virtual_call_uses

[Martin Jambor]

[-- Attachment #1: ipa_otr_analysis_fixup.diff --]
[-- Type: text/plain, Size: 1658 bytes --]

Hi,

ipa_analyze_virtual_call_uses contains code that was meant to deal
with situation where OBJ_TYPE_REF_OBJECT is a (number of)
COMPONENT_REFs on top of a dereferenced default definition SSA_NAME of
a parameter.

The code is useless because that never happens in the IL, if an
ancestor object of a parameter is being used for a virtual call, the
object in the expression is always an SSA_NAME which is assigned the
proper value in a previous statement.

Moreover, if it ever triggered, it might lead to wrong code because in
cases like this it is necessary also to store the offset within the
parameter into the indirect call graph edge information (like we do in
indirect inlining).

The above is done in the next patch in the series.  I've split this
part from it because I would like to commit it also to the 4.6 branch.
I have bootstrapped and tested this on x86-64-linux without any
problems.  OK for trunk and the 4.6 branch?

Thanks,

Martin


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

	* ipa-prop.c (ipa_analyze_virtual_call_uses): Remove handling
	of ADR_EXPRs.


Index: src/gcc/ipa-prop.c
===================================================================
--- src.orig/gcc/ipa-prop.c
+++ src/gcc/ipa-prop.c
@@ -1383,18 +1383,6 @@ ipa_analyze_virtual_call_uses (struct cg
   if (!flag_devirtualize)
     return;
 
-  if (TREE_CODE (obj) == ADDR_EXPR)
-    {
-      do
-	{
-	  obj = TREE_OPERAND (obj, 0);
-	}
-      while (TREE_CODE (obj) == COMPONENT_REF);
-      if (TREE_CODE (obj) != MEM_REF)
-	return;
-      obj = TREE_OPERAND (obj, 0);
-    }
-
   if (TREE_CODE (obj) != SSA_NAME
       || !SSA_NAME_IS_DEFAULT_DEF (obj))
     return;

Re: [PATCH 1/4] Remove usesess and wrong code from ipa_analyze_virtual_call_uses

[Richard Guenther]

On Fri, 15 Apr 2011, Martin Jambor wrote:

> Hi,
> 
> ipa_analyze_virtual_call_uses contains code that was meant to deal
> with situation where OBJ_TYPE_REF_OBJECT is a (number of)
> COMPONENT_REFs on top of a dereferenced default definition SSA_NAME of
> a parameter.
> 
> The code is useless because that never happens in the IL, if an
> ancestor object of a parameter is being used for a virtual call, the
> object in the expression is always an SSA_NAME which is assigned the
> proper value in a previous statement.
> 
> Moreover, if it ever triggered, it might lead to wrong code because in
> cases like this it is necessary also to store the offset within the
> parameter into the indirect call graph edge information (like we do in
> indirect inlining).
> 
> The above is done in the next patch in the series.  I've split this
> part from it because I would like to commit it also to the 4.6 branch.
> I have bootstrapped and tested this on x86-64-linux without any
> problems.  OK for trunk and the 4.6 branch?

Ok for both.

Thanks,
Richard.

> Thanks,
> 
> Martin
> 
> 
> 2011-04-08  Martin Jambor  <mjambor@suse.cz>
> 
> 	* ipa-prop.c (ipa_analyze_virtual_call_uses): Remove handling
> 	of ADR_EXPRs.
> 
> 
> Index: src/gcc/ipa-prop.c
> ===================================================================
> --- src.orig/gcc/ipa-prop.c
> +++ src/gcc/ipa-prop.c
> @@ -1383,18 +1383,6 @@ ipa_analyze_virtual_call_uses (struct cg
>    if (!flag_devirtualize)
>      return;
>  
> -  if (TREE_CODE (obj) == ADDR_EXPR)
> -    {
> -      do
> -	{
> -	  obj = TREE_OPERAND (obj, 0);
> -	}
> -      while (TREE_CODE (obj) == COMPONENT_REF);
> -      if (TREE_CODE (obj) != MEM_REF)
> -	return;
> -      obj = TREE_OPERAND (obj, 0);
> -    }
> -
>    if (TREE_CODE (obj) != SSA_NAME
>        || !SSA_NAME_IS_DEFAULT_DEF (obj))
>      return;
> 
> 

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