[PATCH 3/6] Folding of virtual calls

[Martin Jambor <mjambor@suse.cz>]

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

Hi,

this patch has not changed at all since I posted it last time in
January but needs to be applied before the next one is so I send it
along again.

The purpose of the patch is to allow folding of more complex
OBJ_TYPE_REFs, as opposed to only the simple class we are able to fold
today.  This patch only implements devirtualization through statement
folding (which is also greatly improved, for example we can now fold
when early inlining makes type information available).  However, it
also facilitates interface necessary for IPA devirtualization
including indirect inlining of virtual calls.

The juggling with binfos is a bit bizarre and perhaps a C++ maintainer
should have a look at it but it has worked seamlessly in my tests for
a few months now so I'm becoming quite confident it is in fact
correct.

Thanks,

Martin


2010-02-10  Martin Jambor  <mjambor@suse.cz>

	* gimple.c (get_base_binfo_for_type): New function.
	(get_relevant_ref_binfo_single_inh): New function.
	(get_relevant_ref_binfo_multi_inh): New function.
	(gimple_fold_obj_type_ref_known_binfo): New function.
	(gimple_fold_obj_type_ref): Get binfo from
	get_relevant_ref_binfo_single_inh and
	get_relevant_ref_binfo_multi_inh and use
	gimple_fold_obj_type_ref_known_binfo.
	* gimple.h (gimple_fold_obj_type_ref): Declare.
	(gimple_fold_obj_type_ref_known_binfo): Declare.
	* tree-ssa-ccp.c (fold_gimple_call): Simplify condition for
	folding virtual calls and call gimple_fold_obj_type_ref.


Index: icln/gcc/gimple.c
===================================================================
--- icln.orig/gcc/gimple.c
+++ icln/gcc/gimple.c
@@ -4632,27 +4632,167 @@ gimple_decl_printable_name (tree decl, i
   return IDENTIFIER_POINTER (DECL_NAME (decl));
 }
 
+/* Search for a base binfo of BINFO that corresponds to TYPE and return it if
+   it is found or NULL_TREE if it is not. */
+
+static tree
+get_base_binfo_for_type (tree binfo, tree type)
+{
+  int i;
+  tree base_binfo;
+  tree res = NULL_TREE;
+
+  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
+    if (TREE_TYPE (base_binfo) == type)
+      {
+	gcc_assert (!res);
+	res = base_binfo;
+      }
+
+  return res;
+}
+
+/* Return a binfo describing the true type of object referenced by expression
+   REF if all component references access first ancestors.  REF can consist of
+   a series of COMPONENT_REFs of with a declaration or an INDIREC_REF.  It can
+   also be just a simple declaration, indirect reference or an SSA_NAME.  If
+   the function discoveres an INIDRECT_REF or an SSA_NAME, it will assume that
+   the encapsulating type is described by KNOWN_BINFO or return NULL_TREE if
+   KNOWN_BINFO is NULL_TREE.  Otherwise the first nonartifical field declaration
+   or the base declaration will be examined to get the encapsulating type.  If
+   a COMPONENT_REF referencing an ancestor which is not the first one, this
+   function returns NULL_TREE and sets *try_multi to true.  */
+
+static tree
+get_relevant_ref_binfo_single_inh (tree ref, tree known_binfo, bool *try_multi)
+{
+  while (true)
+    {
+      if (TREE_CODE (ref) == COMPONENT_REF)
+	{
+	  tree par_type;
+	  tree binfo, base_binfo;
+	  tree field = TREE_OPERAND (ref, 1);
+
+	  if (!DECL_ARTIFICIAL (field))
+	    {
+	      tree type = TREE_TYPE (field);
+	      if (TREE_CODE (type) == RECORD_TYPE)
+		return TYPE_BINFO (type);
+	      else
+		return NULL_TREE;
+	    }
+
+	  par_type = TREE_TYPE (TREE_OPERAND (ref, 0));
+	  binfo = TYPE_BINFO (par_type);
+	  if (!binfo
+	      || BINFO_N_BASE_BINFOS (binfo) == 0)
+	    {
+	      if (try_multi)
+		*try_multi = 1;
+	      return NULL_TREE;
+	    }
+	  base_binfo = BINFO_BASE_BINFO (binfo, 0);
+	  if (TREE_TYPE (base_binfo) != TREE_TYPE (field))
+	    {
+	      if (try_multi)
+		*try_multi = 1;
+	      return NULL_TREE;
+	    }
+
+	  ref = TREE_OPERAND (ref, 0);
+	}
+      else if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
+	return TYPE_BINFO (TREE_TYPE (ref));
+      else if (known_binfo
+	       && (TREE_CODE (ref) == SSA_NAME
+		   || TREE_CODE (ref) == INDIRECT_REF))
+	return known_binfo;
+      else
+	return NULL_TREE;
+    }
+}
 
-/* Fold a OBJ_TYPE_REF expression to the address of a function.
-   KNOWN_TYPE carries the true type of OBJ_TYPE_REF_OBJECT(REF).  Adapted
-   from cp_fold_obj_type_ref, but it tolerates types with no binfo
-   data.  */
+
+/* Return a binfo describing the part of object referenced by expression REF.
+   This can and often is a base_binfo of a descendatn binfo. REF can consist of
+   a series of COMPONENT_REFs of with a declaration or an INDIREC_REF.  It can
+   also be just a simple declaration, indirect reference or an SSA_NAME.  If
+   the function discoveres an INIDRECT_REF or an SSA_NAME, it will assume that
+   the encapsulating type is described by KNOWN_BINFO or return NULL_TREE if
+   KNOWN_BINFO is NULL_TREE.  Otherwise the first nonartifical field
+   declaration or the base declaration will be examined to get the
+   encapsulating type.  */
+
+static tree
+get_relevant_ref_binfo_multi_inh (tree ref, tree known_binfo)
+{
+  if (DECL_P (ref) && TREE_CODE (TREE_TYPE (ref)) == RECORD_TYPE)
+    return TYPE_BINFO (TREE_TYPE (ref));
+  else if (TREE_CODE (ref) == COMPONENT_REF)
+    {
+      tree desc_binfo;
+      tree field = TREE_OPERAND (ref, 1);
+
+      if (!DECL_ARTIFICIAL (field))
+	{
+	  tree type = TREE_TYPE (field);
+	  if (TREE_CODE (type) == RECORD_TYPE)
+	    return TYPE_BINFO (type);
+	  else
+	    return NULL_TREE;
+	}
+
+      desc_binfo = get_relevant_ref_binfo_multi_inh (TREE_OPERAND (ref, 0),
+						     known_binfo);
+      if (!desc_binfo)
+	return NULL_TREE;
+      return get_base_binfo_for_type (desc_binfo, TREE_TYPE (field));
+    }
+  else if (known_binfo
+	   && (TREE_CODE (ref) == SSA_NAME
+	       || TREE_CODE (ref) == INDIRECT_REF))
+    return known_binfo;
+  else
+    return NULL_TREE;
+}
+
+/* Return a binfo describing the part of object referenced by expression REF
+   using both get_relevant_ref_binfo_single_inh and
+   get_relevant_ref_binfo_multi_inh in this particular order.  */
 
 tree
-gimple_fold_obj_type_ref (tree ref, tree known_type)
+gimple_get_relevant_ref_binfo (tree ref, tree known_binfo)
+{
+  bool try_multi = false;
+  tree binfo;
+
+  binfo = get_relevant_ref_binfo_single_inh (ref, known_binfo, &try_multi);
+  if (!binfo && try_multi)
+    binfo = get_relevant_ref_binfo_multi_inh (ref, known_binfo);
+  return binfo;
+}
+
+
+/* Fold a OBJ_TYPE_REF expression to the address of a function. TOKEN is
+   integer form of OBJ_TYPE_REF_TOKEN of the reference expression.  KNOWN_BINFO
+   carries the binfo describing the true type of OBJ_TYPE_REF_OBJECT(REF).  */
+
+tree
+gimple_fold_obj_type_ref_known_binfo (HOST_WIDE_INT token, tree known_binfo)
 {
-  HOST_WIDE_INT index;
   HOST_WIDE_INT i;
-  tree v;
-  tree fndecl;
+  tree v, fndecl;
 
-  if (TYPE_BINFO (known_type) == NULL_TREE)
+  /* If binfo flag 2 is not set, this binfo does not "have its own virtual
+     table" (according to cp/cp-tree.h) and cannot be safely used for
+     devirtualization.  Purely empirical experience also shows that we can also
+     bail out if flag 5 is set.  This test also probably works in lto.  */
+  if (BINFO_FLAG_5 (known_binfo))
     return NULL_TREE;
-
-  v = BINFO_VIRTUALS (TYPE_BINFO (known_type));
-  index = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
+  v = BINFO_VIRTUALS (known_binfo);
   i = 0;
-  while (i != index)
+  while (i != token)
     {
       i += (TARGET_VTABLE_USES_DESCRIPTORS
 	    ? TARGET_VTABLE_USES_DESCRIPTORS : 1);
@@ -4660,15 +4800,34 @@ gimple_fold_obj_type_ref (tree ref, tree
     }
 
   fndecl = TREE_VALUE (v);
+  return build_fold_addr_expr (fndecl);
+}
 
-#ifdef ENABLE_CHECKING
-  gcc_assert (tree_int_cst_equal (OBJ_TYPE_REF_TOKEN (ref),
-				  DECL_VINDEX (fndecl)));
-#endif
 
-  cgraph_node (fndecl)->local.vtable_method = true;
+/* Fold a OBJ_TYPE_REF expression to the address of a function.  If KNOWN_TYPE
+   is not NULL_TREE, it is the true type of the outmost encapsulating object if
+   that comes from a pointer SSA_NAME.  If the true outmost encapsulating type
+   can be determined from a declaration OBJ_TYPE_REF_OBJECT(REF), it is used
+   regardless of KNOWN_TYPE (which thuc can be NULL_TREE).  */
 
-  return build_fold_addr_expr (fndecl);
+tree
+gimple_fold_obj_type_ref (tree ref, tree known_type)
+{
+  tree obj = OBJ_TYPE_REF_OBJECT (ref);
+  tree known_binfo = known_type ? TYPE_BINFO (known_type) : NULL_TREE;
+  tree binfo;
+
+  if (TREE_CODE (obj) == ADDR_EXPR)
+    obj = TREE_OPERAND (obj, 0);
+
+  binfo = gimple_get_relevant_ref_binfo (obj, known_binfo);
+  if (binfo)
+    {
+      HOST_WIDE_INT token = tree_low_cst (OBJ_TYPE_REF_TOKEN (ref), 1);
+      return gimple_fold_obj_type_ref_known_binfo (token, binfo);
+    }
+  else
+    return NULL_TREE;
 }
 
 #include "gt-gimple.h"
Index: icln/gcc/tree-ssa-ccp.c
===================================================================
--- icln.orig/gcc/tree-ssa-ccp.c
+++ icln/gcc/tree-ssa-ccp.c
@@ -3007,9 +3007,6 @@ fold_gimple_call (gimple_stmt_iterator *
     }
   else
     {
-      /* Check for resolvable OBJ_TYPE_REF.  The only sorts we can resolve
-         here are when we've propagated the address of a decl into the
-         object slot.  */
       /* ??? Should perhaps do this in fold proper.  However, doing it
          there requires that we create a new CALL_EXPR, and that requires
          copying EH region info to the new node.  Easier to just do it
@@ -3017,19 +3014,11 @@ fold_gimple_call (gimple_stmt_iterator *
       /* ??? Is there a good reason not to do this in fold_stmt_inplace?  */
       callee = gimple_call_fn (stmt);
       if (TREE_CODE (callee) == OBJ_TYPE_REF
-          && lang_hooks.fold_obj_type_ref
-          && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR
-          && DECL_P (TREE_OPERAND
-                     (OBJ_TYPE_REF_OBJECT (callee), 0)))
+          && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR)
         {
           tree t;
 
-          /* ??? Caution: Broken ADDR_EXPR semantics means that
-             looking at the type of the operand of the addr_expr
-             can yield an array type.  See silly exception in
-             check_pointer_types_r.  */
-          t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee)));
-          t = lang_hooks.fold_obj_type_ref (callee, t);
+          t = gimple_fold_obj_type_ref (callee, NULL_TREE);
           if (t)
             {
               gimple_call_set_fn (stmt, t);
Index: icln/gcc/gimple.h
===================================================================
--- icln.orig/gcc/gimple.h
+++ icln/gcc/gimple.h
@@ -864,7 +864,9 @@ unsigned get_gimple_rhs_num_ops (enum tr
 #define gimple_alloc(c, n) gimple_alloc_stat (c, n MEM_STAT_INFO)
 gimple gimple_alloc_stat (enum gimple_code, unsigned MEM_STAT_DECL);
 const char *gimple_decl_printable_name (tree, int);
+tree gimple_get_relevant_ref_binfo (tree ref, tree known_binfo);
 tree gimple_fold_obj_type_ref (tree, tree);
+tree gimple_fold_obj_type_ref_known_binfo (HOST_WIDE_INT, tree);
 
 /* Returns true iff T is a valid GIMPLE statement.  */
 extern bool is_gimple_stmt (tree);
Index: icln/gcc/testsuite/g++.dg/otr-fold-1.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/otr-fold-1.C
@@ -0,0 +1,77 @@
+/* Verify that simple virtual calls are inlined even without early
+   inlining, even when a typecast to an ancestor is involved along the
+   way.  */
+/* { dg-do run } */
+/* { dg-options "-O -fdump-tree-optimized-slim"  } */
+
+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);
+};
+
+
+class B : public Distraction, public A
+{
+public:
+  virtual int foo (int i);
+};
+
+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;
+}
+
+static int middleman_1 (class A *obj, int i)
+{
+  return obj->foo (i);
+}
+
+static int middleman_2 (class B *obj, int i)
+{
+  return middleman_1 (obj, i);
+}
+
+int main (int argc, char *argv[])
+{
+  class B b;
+
+  if (middleman_2 (&b, get_input ()) != 3)
+    abort ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "= B::foo"  "optimized"  } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */