ipa-prop.c (type_change_info): New fields offset, object, known_current_type and multiple_types_encountered.

2011-11-03  Martin Jambor  <mjambor@suse.cz>

	* ipa-prop.c (type_change_info): New fields offset, 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.
	* testsuite/g++.dg/ipa/devirt-c-8.C: Likewise.

From-SVN: r180825

8 files changed, 309 insertions, 16 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 9dd525e..0b95499 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,16 @@
+2011-11-03  Martin Jambor  <mjambor@suse.cz>
+
+	* ipa-prop.c (type_change_info): New fields offset, 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.
+
 2011-11-03  Richard Guenther  <rguenther@suse.de>
 
 	PR lto/48217
diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c
index e624426..0ca3f3a 100644
--- a/gcc/ipa-prop.c
+++ b/gcc/ipa-prop.c
@@ -271,8 +271,20 @@ ipa_print_all_jump_functions (FILE *f)
 
 struct type_change_info
 {
+  /* Offset into the object where there is the virtual method pointer we are
+     looking for.  */
+  HOST_WIDE_INT offset;
+  /* 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 +350,50 @@ 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, struct type_change_info *tci)
+{
+  HOST_WIDE_INT offset, size, max_size;
+  tree lhs, rhs, base;
+
+  if (!gimple_assign_single_p (stmt))
+    return NULL_TREE;
+
+  lhs = gimple_assign_lhs (stmt);
+  rhs = gimple_assign_rhs1 (stmt);
+  if (TREE_CODE (lhs) != COMPONENT_REF
+      || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
+      || TREE_CODE (rhs) != ADDR_EXPR)
+    return NULL_TREE;
+  rhs = get_base_address (TREE_OPERAND (rhs, 0));
+  if (!rhs
+      || TREE_CODE (rhs) != VAR_DECL
+      || !DECL_VIRTUAL_P (rhs))
+    return NULL_TREE;
+
+  base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
+  if (offset != tci->offset
+      || size != POINTER_SIZE
+      || max_size != POINTER_SIZE)
+    return NULL_TREE;
+  if (TREE_CODE (base) == MEM_REF)
+    {
+      if (TREE_CODE (tci->object) != MEM_REF
+	  || TREE_OPERAND (tci->object, 0) != TREE_OPERAND (base, 0)
+	  || !tree_int_cst_equal (TREE_OPERAND (tci->object, 1),
+				  TREE_OPERAND (base, 1)))
+	return NULL_TREE;
+    }
+  else if (tci->object != base)
+    return NULL_TREE;
+
+  return DECL_CONTEXT (rhs);
+}
+
 /* 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 +408,12 @@ check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
 
   if (stmt_may_be_vtbl_ptr_store (stmt))
     {
+      tree type;
+      type = extr_type_from_vtbl_ptr_store (stmt, tci);
+      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,16 +421,15 @@ check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
     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;
@@ -381,8 +442,6 @@ detect_type_change (tree arg, tree base, gimple call,
   if (!flag_devirtualize || !gimple_vuse (call))
     return false;
 
-  tci.type_maybe_changed = false;
-
   ao.ref = arg;
   ao.base = base;
   ao.offset = offset;
@@ -391,15 +450,45 @@ detect_type_change (tree arg, tree base, gimple call,
   ao.ref_alias_set = -1;
   ao.base_alias_set = -1;
 
+  tci.offset = offset;
+  tci.object = get_base_address (arg);
+  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 +496,19 @@ detect_type_change (tree arg, tree base, gimple call,
 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
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 305ba6a..841d7b0 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2011-11-03  Martin Jambor  <mjambor@suse.cz>
+
+	* g++.dg/ipa/devirt-c-1.C: Add dump scans.
+	* g++.dg/ipa/devirt-c-2.C: Likewise.
+	* g++.dg/ipa/devirt-c-7.C: New test.
+	* g++.dg/ipa/devirt-c-8.C: Likewise.
+
 2011-11-03  Ira Rosen  <ira.rosen@linaro.org>
 
 	PR tree-optimization/50912
diff --git a/gcc/testsuite/g++.dg/ipa/devirt-c-1.C b/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
index df2230d..dcd8046 100644
--- a/gcc/testsuite/g++.dg/ipa/devirt-c-1.C
+++ b/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" } } */
diff --git a/gcc/testsuite/g++.dg/ipa/devirt-c-2.C b/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
index d37fe50..b9a36e2 100644
--- a/gcc/testsuite/g++.dg/ipa/devirt-c-2.C
+++ b/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" } } */
diff --git a/gcc/testsuite/g++.dg/ipa/devirt-c-7.C b/gcc/testsuite/g++.dg/ipa/devirt-c-7.C
new file mode 100644
index 0000000..89d0432
--- /dev/null
+++ b/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;
+}
diff --git a/gcc/testsuite/g++.dg/ipa/devirt-c-8.C b/gcc/testsuite/g++.dg/ipa/devirt-c-8.C
new file mode 100644
index 0000000..309644d
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ipa/devirt-c-8.C
@@ -0,0 +1,82 @@
+/* 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 -fdump-ipa-cp -fdump-tree-optimized"  } */
+
+extern "C" void abort (void);
+
+class A
+{
+public:
+  int data;
+  A();
+  virtual int foo (int i);
+};
+
+class B : public A
+{
+public:
+  B();
+  virtual int foo (int i);
+};
+
+class C : public A
+{
+public:
+  virtual int foo (int i);
+};
+
+int A::foo (int i)
+{
+  return i + 1;
+}
+
+int B::foo (int i)
+{
+  return i + 2;
+}
+
+int C::foo (int i)
+{
+  return i + 3;
+}
+
+static int __attribute__ ((noinline))
+middleman (class A *obj, int i)
+{
+  return obj->foo (i);
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+inline __attribute__ ((always_inline)) A::A ()
+{
+  if (middleman (this, get_input ()) != 2)
+    abort ();
+}
+
+inline __attribute__ ((always_inline)) B::B ()
+{
+}
+
+static void bah ()
+{
+  class B b;
+}
+
+int main (int argc, char *argv[])
+{
+  int i;
+
+  for (i = 0; i < 10; i++)
+    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" } } */
diff --git a/gcc/tree.h b/gcc/tree.h
index 5dc1798..00b6637 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -2686,7 +2686,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)