[PATCH, devirtualization] Detect the new type in type change detection

[Martin Jambor <mjambor at suse dot cz>]

Hi,

I've been asked by Maxim Kuvyrkov to revive the following patch which
has not made it to 4.6.  Currently, when type based devirtualization
detects a potential type change, it simply gives up on gathering any
information on the object in question.  This patch adds an attempt to
actually detect the new type after the change.

Maxim claimed this (and another patch I'll post tomorrow) noticeably
improved performance of some real code.  I can only offer a rather
artificial example in the attachment.  When the constructors are
inlined but the function multiply_matrices is not, this patch makes
the produced executable run for only 7 seconds instead of about 20 on
my 4 year old i686 desktop (with -Ofast).

Anyway, the patch passes bootstrap and testsuite on x86_64-linux.
What do you think, is it a good idea for trunk now?

Thanks,

Martin


2011-10-21  Martin Jambor  <mjambor@suse.cz>

	* ipa-prop.c (type_change_info): New fields object, known_current_type
	and multiple_types_encountered.
	(extr_type_from_vtbl_ptr_store): New function.
	(check_stmt_for_type_change): Use it, set multiple_types_encountered if
        the result is different from the previous one.
	(detect_type_change): Renamed to detect_type_change_1. New parameter
	comp_type.  Set up new fields in tci, build known type jump
	functions if the new type can be identified.
	(detect_type_change): New function.
	* tree.h (DECL_CONTEXT): Comment new use.

	* testsuite/g++.dg/ipa/devirt-c-1.C: Add dump scans.
	* testsuite/g++.dg/ipa/devirt-c-2.C: Likewise.
	* testsuite/g++.dg/ipa/devirt-c-7.C: New test.


Index: src/gcc/ipa-prop.c
===================================================================
--- src.orig/gcc/ipa-prop.c
+++ src/gcc/ipa-prop.c
@@ -271,8 +271,17 @@ ipa_print_all_jump_functions (FILE *f)
 
 struct type_change_info
 {
+  /* The declaration or SSA_NAME pointer of the base that we are checking for
+     type change.  */
+  tree object;
+  /* If we actually can tell the type that the object has changed to, it is
+     stored in this field.  Otherwise it remains NULL_TREE.  */
+  tree known_current_type;
   /* Set to true if dynamic type change has been detected.  */
   bool type_maybe_changed;
+  /* Set to true if multiple types have been encountered.  known_current_type
+     must be disregarded in that case.  */
+  bool multiple_types_encountered;
 };
 
 /* Return true if STMT can modify a virtual method table pointer.
@@ -338,6 +347,49 @@ stmt_may_be_vtbl_ptr_store (gimple stmt)
   return true;
 }
 
+/* If STMT can be proved to be an assignment to the virtual method table
+   pointer of ANALYZED_OBJ and the type associated with the new table
+   identified, return the type.  Otherwise return NULL_TREE.  */
+
+static tree
+extr_type_from_vtbl_ptr_store (gimple stmt, tree analyzed_obj)
+{
+  tree lhs, t, obj;
+
+  if (!is_gimple_assign (stmt))
+    return NULL_TREE;
+
+  lhs = gimple_assign_lhs (stmt);
+
+  if (TREE_CODE (lhs) != COMPONENT_REF)
+    return NULL_TREE;
+  obj = lhs;
+
+  if (!DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
+    return NULL_TREE;
+
+  do
+    {
+      obj = TREE_OPERAND (obj, 0);
+    }
+  while (TREE_CODE (obj) == COMPONENT_REF);
+  if (TREE_CODE (obj) == MEM_REF)
+    obj = TREE_OPERAND (obj, 0);
+  if (TREE_CODE (obj) == ADDR_EXPR)
+    obj = TREE_OPERAND (obj, 0);
+  if (obj != analyzed_obj)
+    return NULL_TREE;
+
+  t = gimple_assign_rhs1 (stmt);
+  if (TREE_CODE (t) != ADDR_EXPR)
+    return NULL_TREE;
+  t = get_base_address (TREE_OPERAND (t, 0));
+  if (!t || TREE_CODE (t) != VAR_DECL || !DECL_VIRTUAL_P (t))
+    return NULL_TREE;
+
+  return DECL_CONTEXT (t);
+}
+
 /* Callback of walk_aliased_vdefs and a helper function for
    detect_type_change to check whether a particular statement may modify
    the virtual table pointer, and if possible also determine the new type of
@@ -352,6 +404,12 @@ check_stmt_for_type_change (ao_ref *ao A
 
   if (stmt_may_be_vtbl_ptr_store (stmt))
     {
+      tree type;
+      type = extr_type_from_vtbl_ptr_store (stmt, tci->object);
+      if (tci->type_maybe_changed
+	  && type != tci->known_current_type)
+	tci->multiple_types_encountered = true;
+      tci->known_current_type = type;
       tci->type_maybe_changed = true;
       return true;
     }
@@ -359,19 +417,19 @@ check_stmt_for_type_change (ao_ref *ao A
     return false;
 }
 
-/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
-   looking for assignments to its virtual table pointer.  If it is, return true
-   and fill in the jump function JFUNC with relevant type information or set it
-   to unknown.  ARG is the object itself (not a pointer to it, unless
-   dereferenced).  BASE is the base of the memory access as returned by
-   get_ref_base_and_extent, as is the offset.  */
+
+
+/* Like detect_type_change but with extra argument COMP_TYPE which will become
+   the component type part of new JFUNC of dynamic type change is detected and
+   the new base type is identified.  */
 
 static bool
-detect_type_change (tree arg, tree base, gimple call,
-		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call,
+		      struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
 {
   struct type_change_info tci;
   ao_ref ao;
+  tree t;
 
   gcc_checking_assert (DECL_P (arg)
 		       || TREE_CODE (arg) == MEM_REF
@@ -381,8 +439,6 @@ detect_type_change (tree arg, tree base,
   if (!flag_devirtualize || !gimple_vuse (call))
     return false;
 
-  tci.type_maybe_changed = false;
-
   ao.ref = arg;
   ao.base = base;
   ao.offset = offset;
@@ -391,15 +447,51 @@ detect_type_change (tree arg, tree base,
   ao.ref_alias_set = -1;
   ao.base_alias_set = -1;
 
+  t = arg;
+  while (handled_component_p (t))
+    t = TREE_OPERAND (t, 0);
+  if (TREE_CODE (t) == MEM_REF)
+    t = TREE_OPERAND (t, 0);
+  if (TREE_CODE (t) == ADDR_EXPR)
+    t = TREE_OPERAND (t, 0);
+  tci.object = t;
+  tci.known_current_type = NULL_TREE;
+  tci.type_maybe_changed = false;
+  tci.multiple_types_encountered = false;
+
   walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
 		      &tci, NULL);
   if (!tci.type_maybe_changed)
     return false;
 
-  jfunc->type = IPA_JF_UNKNOWN;
+  if (!tci.known_current_type
+      || tci.multiple_types_encountered
+      || offset != 0)
+    jfunc->type = IPA_JF_UNKNOWN;
+  else
+    {
+      jfunc->type = IPA_JF_KNOWN_TYPE;
+      jfunc->value.known_type.base_type = tci.known_current_type;
+      jfunc->value.known_type.component_type = comp_type;
+    }
+
   return true;
 }
 
+/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
+   looking for assignments to its virtual table pointer.  If it is, return true
+   and fill in the jump function JFUNC with relevant type information or set it
+   to unknown.  ARG is the object itself (not a pointer to it, unless
+   dereferenced).  BASE is the base of the memory access as returned by
+   get_ref_base_and_extent, as is the offset.  */
+
+static bool
+detect_type_change (tree arg, tree base, gimple call,
+		    struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+{
+  return detect_type_change_1 (arg, base, TREE_TYPE (arg), call, jfunc, offset);
+}
+
 /* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
    SSA name (its dereference will become the base and the offset is assumed to
    be zero).  */
@@ -407,16 +499,19 @@ detect_type_change (tree arg, tree base,
 static bool
 detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
 {
+  tree comp_type;
+
   gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
   if (!flag_devirtualize
       || !POINTER_TYPE_P (TREE_TYPE (arg))
       || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
     return false;
 
+  comp_type = TREE_TYPE (TREE_TYPE (arg));
   arg = build2 (MEM_REF, ptr_type_node, arg,
-                build_int_cst (ptr_type_node, 0));
+		build_int_cst (ptr_type_node, 0));
 
-  return detect_type_change (arg, arg, call, jfunc, 0);
+  return detect_type_change_1 (arg, arg, comp_type, call, jfunc, 0);
 }
 
 /* Callback of walk_aliased_vdefs.  Flags that it has been invoked to the
Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
===================================================================
--- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
+++ src/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
@@ -1,7 +1,7 @@
 /* Verify that ipa-cp correctly detects the dynamic type of an object
    under construction when doing devirtualization.  */
 /* { dg-do run } */
-/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized"  } */
 
 extern "C" void abort (void);
 
@@ -69,3 +69,8 @@ int main (int argc, char *argv[])
     bah ();
   return 0;
 }
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo"  "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/ipa/devirt-c-2.C
===================================================================
--- src.orig/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
+++ src/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
@@ -1,7 +1,7 @@
 /* Verify that ipa-cp correctly detects the dynamic type of an object
    under construction when doing devirtualization.  */
 /* { dg-do run } */
-/* { dg-options "-O3 -fno-early-inlining -fno-inline"  } */
+/* { dg-options "-O3 -fno-early-inlining -fno-inline -fdump-ipa-cp -fdump-tree-optimized"  } */
 
 extern "C" void abort (void);
 
@@ -77,3 +77,8 @@ int main (int argc, char *argv[])
     bah ();
   return 0;
 }
+
+/* { dg-final { scan-ipa-dump "Discovered a virtual call to a known target.*A::foo"  "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/tree.h
===================================================================
--- src.orig/gcc/tree.h
+++ src/gcc/tree.h
@@ -2678,7 +2678,9 @@ struct function;
     nodes, this points to either the FUNCTION_DECL for the containing
     function, the RECORD_TYPE or UNION_TYPE for the containing type, or
     NULL_TREE or a TRANSLATION_UNIT_DECL if the given decl has "file
-    scope".  */
+    scope".  In particular, for VAR_DECLs which are virtual table pointers
+    (they have DECL_VIRTUAL set), we use DECL_CONTEXT to determine the type
+    they belong to.  */
 #define DECL_CONTEXT(NODE) (DECL_MINIMAL_CHECK (NODE)->decl_minimal.context)
 #define DECL_FIELD_CONTEXT(NODE) \
   (FIELD_DECL_CHECK (NODE)->decl_minimal.context)
Index: src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
===================================================================
--- /dev/null
+++ src/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
@@ -0,0 +1,87 @@
+/* Verify that ipa-cp will not get confused by placement new constructing an
+   object within another one when looking for dynamic type change .  */
+/* { dg-do run } */
+/* { dg-options "-O3 -Wno-attributes"  } */
+
+extern "C" void abort (void);
+namespace std {
+  typedef __SIZE_TYPE__ size_t;
+}
+inline void* __attribute__ ((always_inline))
+operator new(std::size_t, void* __p) throw()
+{
+  return __p;
+}
+
+class A
+{
+public:
+  char data[256];
+  A();
+  virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+class C
+{
+public:
+  C();
+  virtual double foo (double i);
+};
+
+int A::foo (int i)
+{
+  return i + 1;
+}
+
+int B::foo (int i)
+{
+  return i + 2;
+}
+
+double C::foo (double i)
+{
+  return i + 3.5;
+}
+
+static int __attribute__ ((noinline)) middleman (class A *obj, int i)
+{
+  return obj->foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+__attribute__ ((always_inline)) C::C ()
+{
+}
+
+A::A ()
+{
+}
+
+static  __attribute__ ((noinline)) void bah ()
+{
+  class B b;
+
+  C *c = new ((void *) &b.data) C;
+
+  if (middleman (&b, get_input ()) != 3)
+    abort ();
+}
+
+int main (int argc, char *argv[])
+{
+  int i;
+
+  for (i = 0; i < 10; i++)
+    bah ();
+  return 0;
+}

#include <stdio.h>

class SquareMatrix
{
protected:
  int len;

public:

  SquareMatrix (int new_len)
  {
    len = new_len;
  }
  int getLen () const
  {
    return len;
  }
  virtual void Initialize() = 0;
  virtual void DeInitialize() = 0;

  virtual double getElement (int i, int j) const = 0;
  virtual void setElement (int i, int j, double d) = 0;
};

class DenseMatrix : public SquareMatrix
{
  double *data;

public:
  DenseMatrix (int new_len) : SquareMatrix (new_len) {}

  virtual void Initialize();
  virtual void DeInitialize();
  double getElement (int i, int j) const;
  void setElement (int i, int j, double d);
  void fill (double d);
};

void DenseMatrix::Initialize ()
{
  int i, j;
  data = new double[len * len];
}

void DenseMatrix::DeInitialize ()
{
  delete[] data;
}


double DenseMatrix::getElement (int i, int j) const
{
  int len = getLen ();
  return data[i*len+j];
}

void DenseMatrix::setElement (int i, int j, double d)
{
  int len = getLen ();
  data[i*len+j] = d;
}

void DenseMatrix::fill (double d)
{
  int len = getLen ();
  int i, j;

  for (i = 0; i < len; i++)
    {
      for (j = 0; j < len; j++)
	setElement (i, j, d);
      d += 0.5;
    }
}

static void multiply_matrices (SquareMatrix *res, SquareMatrix *a, SquareMatrix *b)
{
  int i, j, len = res->getLen ();

  for (i = 0; i < len; i++)
    for (j = 0; j < len; j++)
      {
	int k;
	double d = 0;

	for (k = 0; k < len; k++)
	  d += a->getElement (i, k) * b->getElement (k, j);

	res->setElement (i, j, d);
      }
}

#define N 1000

int main (int argc, char *argv[])
{
  DenseMatrix r(N), a(N), b(N);

  a.Initialize();
  b.Initialize();
  r.Initialize();

  a.fill(10);
  b.fill(-4);

  multiply_matrices (&r, &a, &b);

  printf ("Some value: %e\n", r.getElement (N/2, N/3));

  a.DeInitialize();
  b.DeInitialize();
  r.DeInitialize();

  return 0;
}