[PATCH, PR 45934 5/5] Intraprocedural type-based devirtualization

[Martin Jambor <mjambor at suse dot cz>]

This patch does intraprocedural devirtualization as a part of cgraph
rebuilding pass.  I'm now quite confident this is one of the better
places where to put if not the best - as usual I'm opened to
alternative suggestions here.  However, this placement minimizes the
overhead, allows for subsequent early inlining and dealing with
potential eh cfg cleanups is much less ugly.

This patch compensates for not devirtualizing when folding.  It looks
for OBJ_TYPE_REF calls, and tries to deduce their type by watching out
for dynamic type changes.  If the type is known and the call can be
converted to a direct one with that knowledge, it is done so.

This patch is quite simplified since the last time since I realized
some of the more complex code paths just did not run or could never
work to a known type jump function anyway.  Also I deferred some minor
cleanups which were originally part of this for later.

This patch is necessary for (modified variants of) testcases
g++.dg/otr-fold-[12].C (re-introduced as imm-devirt[12].C),
g++.dg/tree-ssa/pr43411.C and g++.dg/tree-ssa/pr45605.C to pass again.
Without it, early inlining can be detrimental to devirtualization by
making it a purely intraprocedural issue and slow down simple
testcases three-fold.
 
This patch also passes bootstrap and testing on x86_64-linux and make
check-c++ on i686.  I'm looking forward to all comments and
suggestions.

Thanks,

Martin



2010-12-13  Martin Jambor  <mjambor@suse.cz>

	* ipa-prop.c (get_ancestor_base_and_offset): New function.
	(compute_complex_assign_jump_func): Use it, check that op2 is NULL
	in the ancestor case.
	(compute_complex_ancestor_jump_func): Likewise.
	(ipa_try_devirtualize_immediately): New fuction.
	* cgraphbuild.c: Include flags.h and ipa-prop.h.
	(rebuild_cgraph_edges): Renamed to rebuild_cgraph_edges_1, new
	parameter devirtualize, call ipa_try_devirtualize_immediately
	if it is true.
	(rebuild_cgraph_edges): New function.
	(rebuild_cgraph_edges_devirtualize): Likewise.
	(pass_rebuild_cgraph_edges_and_devirt): New variable.
	* passes.c (init_optimization_passes): Use it.
	* tree-pass.h (pass_rebuild_cgraph_edges_and_devirt): Declare.
	* ipa-prop.h (ipa_try_devirtualize_immediately): Declare.
	* Makefile.in (cgraphbuild.o): Add FLAGS_H and IPA_PROP_H to
	dependencies.

	* testsuite/g++.dg/ipa/imm-devirt-1.C: New test.
	* testsuite/g++.dg/ipa/imm-devirt-2.C: Likewise.
	* testsuite/g++.dg/tree-ssa/pr45605.C: Compile with O2, scan optimized
	dump. Un-xfail dump scan.
	* g++.dg/tree-ssa/pr43411.C: Un-xfail dump scan.


Index: icln/gcc/ipa-prop.c
===================================================================
--- icln.orig/gcc/ipa-prop.c
+++ icln/gcc/ipa-prop.c
@@ -1447,6 +1447,59 @@ ipa_analyze_indirect_call_uses (struct c
   return;
 }
 
+/* If a call to an OBJ_TYPE_REF given by GSI can be turned into a direct one
+   according to the type of its object right away and if so, do it and return
+   true.  If CFG is changed in the process, *CFG_CHANGED is set to true.  */
+
+tree
+ipa_try_devirtualize_immediately (gimple_stmt_iterator *gsi, bool *cfg_changed)
+{
+  struct ipa_jump_func jfunc;
+  tree fndecl, delta, token;
+  gimple call = gsi_stmt (*gsi);
+  tree target = gimple_call_fn (call);
+
+  if (TREE_CODE (target) != OBJ_TYPE_REF)
+    return NULL_TREE;
+  jfunc.type = IPA_JF_UNKNOWN;
+  compute_known_type_jump_func (OBJ_TYPE_REF_OBJECT (target), &jfunc, call);
+  if (jfunc.type != IPA_JF_KNOWN_TYPE)
+    return NULL_TREE;
+
+  token = OBJ_TYPE_REF_TOKEN (target);
+  fndecl = gimple_get_virt_mehtod_for_binfo (tree_low_cst (token, 1),
+					     jfunc.value.base_binfo,
+					     &delta, true);
+  if (!fndecl)
+    return NULL_TREE;
+  if (cgraph_dump_file)
+    {
+      fprintf (cgraph_dump_file, "ipa-prop: Immediately devirtualizing call ");
+      print_gimple_expr (cgraph_dump_file, call, 0, 0);
+      fprintf (cgraph_dump_file, "\n          in function ");
+      print_generic_expr (cgraph_dump_file, current_function_decl, 0);
+    }
+
+  if (integer_nonzerop (delta))
+    gimple_adjust_this_by_delta (gsi, delta);
+  gimple_call_set_fndecl (call, fndecl);
+  update_stmt (call);
+  if (maybe_clean_eh_stmt (call)
+      && gimple_purge_dead_eh_edges (gimple_bb (call)))
+    *cfg_changed = true;
+
+  if (cgraph_dump_file)
+    {
+      fprintf (cgraph_dump_file, "\n          into ");
+      print_gimple_expr (cgraph_dump_file, call, 0, 0);
+      fprintf (cgraph_dump_file, "\n          with delta ");
+      print_generic_expr (cgraph_dump_file, delta, 0);
+      fprintf (cgraph_dump_file, "\n");
+    }
+
+  return fndecl;
+}
+
 /* Analyze a CALL to an OBJ_TYPE_REF which is passed in TARGET and if the
    object referenced in the expression is a formal parameter of the caller
    (described by INFO), create a call note for the statement. */
Index: icln/gcc/testsuite/g++.dg/ipa/imm-devirt-1.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/imm-devirt-1.C
@@ -0,0 +1,76 @@
+/* Verify that virtual calls are folded even when a typecast to an
+   ancestor is involved along the way.  */
+/* { dg-do run } */
+/* { dg-options "-O2 -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 __attribute__ ((noinline)) A::foo (int i)
+{
+  return i + 1;
+}
+
+int __attribute__ ((noinline)) B::foo (int i)
+{
+  return i + 2;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+static inline int middleman_1 (class A *obj, int i)
+{
+  return obj->foo (i);
+}
+
+static inline 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" } } */
Index: icln/gcc/testsuite/g++.dg/ipa/imm-devirt-2.C
===================================================================
--- /dev/null
+++ icln/gcc/testsuite/g++.dg/ipa/imm-devirt-2.C
@@ -0,0 +1,88 @@
+/* Verify that virtual calls are folded even when a typecast to an
+   ancestor is involved along the way.  */
+/* { dg-do run } */
+/* { dg-options "-O2 -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 A_2 : public A
+{
+public:
+  int data_2;
+  virtual int baz (int i);
+};
+
+
+class B : public Distraction, public A_2
+{
+public:
+  virtual int foo (int i);
+};
+
+float __attribute__ ((noinline)) Distraction::bar (float z)
+{
+  f += z;
+  return f/2;
+}
+
+int __attribute__ ((noinline)) A::foo (int i)
+{
+  return i + 1;
+}
+
+int __attribute__ ((noinline)) A_2::baz (int i)
+{
+  return i * 15;
+}
+
+int __attribute__ ((noinline)) B::foo (int i)
+{
+  return i + 2;
+}
+
+int __attribute__ ((noinline,noclone)) get_input(void)
+{
+  return 1;
+}
+
+static inline int middleman_1 (class A *obj, int i)
+{
+  return obj->foo (i);
+}
+
+static inline int middleman_2 (class A *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" } } */
Index: icln/gcc/testsuite/g++.dg/tree-ssa/pr45605.C
===================================================================
--- icln.orig/gcc/testsuite/g++.dg/tree-ssa/pr45605.C
+++ icln/gcc/testsuite/g++.dg/tree-ssa/pr45605.C
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O1 -fdump-tree-ssa" } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
 extern "C" void abort(); 
 bool destructor_called = false; 
 
@@ -33,5 +33,5 @@ int main() {
 
 
 /* We should devirtualize call to D::Run */
-/* { dg-final { scan-tree-dump-times "D::Run \\(" 1 "ssa" { xfail *-*-* } } } */
-/* { dg-final { cleanup-tree-dump "ssa" } } */
+/* { dg-final { scan-tree-dump-times "D::Run \\(" 1 "optimized"} } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: icln/gcc/cgraphbuild.c
===================================================================
--- icln.orig/gcc/cgraphbuild.c
+++ icln/gcc/cgraphbuild.c
@@ -33,6 +33,8 @@ along with GCC; see the file COPYING3.
 #include "tree-pass.h"
 #include "ipa-utils.h"
 #include "except.h"
+#include "flags.h"
+#include "ipa-prop.h"
 
 /* Context of record_reference.  */
 struct record_reference_ctx
@@ -426,15 +428,18 @@ record_references_in_initializer (tree d
   pointer_set_destroy (visited_nodes);
 }
 
-/* Rebuild cgraph edges for current function node.  This needs to be run after
-   passes that don't update the cgraph.  */
+/* Remove callees call graph edges for the current function.  Afterwards scan
+   the body of the current function and create them anew for each call
+   statement.  If DEVIRTUALIZE is true, attempt to do turn virtual calls into
+   direct ones in the process.  */
 
-unsigned int
-rebuild_cgraph_edges (void)
+static unsigned int
+rebuild_cgraph_edges_1 (bool devirtualize)
 {
   basic_block bb;
   struct cgraph_node *node = cgraph_node (current_function_decl);
   gimple_stmt_iterator gsi;
+  bool cfg_changed = false;
 
   cgraph_node_remove_callees (node);
   ipa_remove_all_references (&node->ref_list);
@@ -453,6 +458,8 @@ rebuild_cgraph_edges (void)
 	      int freq = compute_call_stmt_bb_frequency (current_function_decl,
 							 bb);
 	      decl = gimple_call_fndecl (stmt);
+	      if (!decl && devirtualize)
+		decl = ipa_try_devirtualize_immediately (&gsi, &cfg_changed);
 	      if (decl)
 		cgraph_create_edge (node, cgraph_node (decl), stmt,
 				    bb->count, freq,
@@ -474,7 +481,28 @@ rebuild_cgraph_edges (void)
   record_eh_tables (node, cfun);
   gcc_assert (!node->global.inlined_to);
 
-  return 0;
+  if (cfg_changed)
+    return TODO_cleanup_cfg;
+  else
+    return 0;
+}
+
+/* Rebuild outgoing cgraph edges for current function node.  This needs to be
+   run after passes that don't update the cgraph.  */
+
+unsigned int
+rebuild_cgraph_edges (void)
+{
+ return rebuild_cgraph_edges_1 (false);
+}
+
+/* Variant of the above pass that also tries to do type-based devirtualization
+   while rebuilding the outgoing call graph edges.  */
+
+static unsigned int
+rebuild_cgraph_edges_devirtualize (void)
+{
+ return rebuild_cgraph_edges_1 (flag_devirtualize);
 }
 
 /* Rebuild cgraph edges for current function node.  This needs to be run after
@@ -518,6 +546,25 @@ struct gimple_opt_pass pass_rebuild_cgra
   NULL,					/* sub */
   NULL,					/* next */
   0,					/* static_pass_number */
+  TV_CGRAPH,				/* tv_id */
+  PROP_cfg,				/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  0,					/* todo_flags_finish */
+ }
+};
+
+struct gimple_opt_pass pass_rebuild_cgraph_edges_and_devirt =
+{
+ {
+  GIMPLE_PASS,
+  "*rebuild_cgraph_edges_d",		/* name */
+  NULL,					/* gate */
+  rebuild_cgraph_edges_devirtualize,    /* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
   TV_CGRAPH,				/* tv_id */
   PROP_cfg,				/* properties_required */
   0,					/* properties_provided */
Index: icln/gcc/ipa-prop.h
===================================================================
--- icln.orig/gcc/ipa-prop.h
+++ icln/gcc/ipa-prop.h
@@ -429,6 +429,9 @@ void ipa_initialize_node_params (struct
 bool ipa_propagate_indirect_call_infos (struct cgraph_edge *cs,
 					VEC (cgraph_edge_p, heap) **new_edges);
 
+/* Intraprocedural devirtualization. */
+tree ipa_try_devirtualize_immediately (gimple_stmt_iterator *, bool *);
+
 /* Indirect edge and binfo processing.  */
 struct cgraph_edge *ipa_make_edge_direct_to_target (struct cgraph_edge *, tree,
 						    tree);
Index: icln/gcc/passes.c
===================================================================
--- icln.orig/gcc/passes.c
+++ icln/gcc/passes.c
@@ -781,7 +781,7 @@ init_optimization_passes (void)
           NEXT_PASS (pass_split_functions);
 	}
       NEXT_PASS (pass_release_ssa_names);
-      NEXT_PASS (pass_rebuild_cgraph_edges);
+      NEXT_PASS (pass_rebuild_cgraph_edges_and_devirt);
       NEXT_PASS (pass_inline_parameters);
     }
   NEXT_PASS (pass_ipa_tree_profile);
Index: icln/gcc/tree-pass.h
===================================================================
--- icln.orig/gcc/tree-pass.h
+++ icln/gcc/tree-pass.h
@@ -436,6 +436,7 @@ extern struct gimple_opt_pass pass_uncpr
 extern struct gimple_opt_pass pass_return_slot;
 extern struct gimple_opt_pass pass_reassoc;
 extern struct gimple_opt_pass pass_rebuild_cgraph_edges;
+extern struct gimple_opt_pass pass_rebuild_cgraph_edges_and_devirt;
 extern struct gimple_opt_pass pass_remove_cgraph_callee_edges;
 extern struct gimple_opt_pass pass_build_cgraph_edges;
 extern struct gimple_opt_pass pass_local_pure_const;
Index: icln/gcc/Makefile.in
===================================================================
--- icln.orig/gcc/Makefile.in
+++ icln/gcc/Makefile.in
@@ -3030,7 +3030,8 @@ cgraphunit.o : cgraphunit.c $(CONFIG_H)
    tree-pretty-print.h gimple-pretty-print.h
 cgraphbuild.o : cgraphbuild.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TREE_H) langhooks.h $(CGRAPH_H) intl.h pointer-set.h $(GIMPLE_H) \
-   $(TREE_FLOW_H) $(TREE_PASS_H) $(IPA_UTILS_H) $(EXCEPT_H)
+   $(TREE_FLOW_H) $(TREE_PASS_H) $(IPA_UTILS_H) $(EXCEPT_H) $(FLAGS_H) \
+   $(IPA_PROP_H)
 varpool.o : varpool.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    $(TREE_H) $(CGRAPH_H) langhooks.h $(DIAGNOSTIC_CORE_H) $(HASHTAB_H) \
    $(GGC_H) $(TIMEVAR_H) debug.h $(TARGET_H) output.h $(GIMPLE_H) \
Index: icln/gcc/testsuite/g++.dg/tree-ssa/pr43411.C
===================================================================
--- icln.orig/gcc/testsuite/g++.dg/tree-ssa/pr43411.C
+++ icln/gcc/testsuite/g++.dg/tree-ssa/pr43411.C
@@ -25,5 +25,5 @@ void testInlinePsub() {
     sink1 = v(p);
 }
 
-// { dg-final { scan-tree-dump-not "OBJ_TYPE_REF" "optimized" { xfail *-*-* } } }
+// { dg-final { scan-tree-dump-not "OBJ_TYPE_REF" "optimized" } }
 // { dg-final { cleanup-tree-dump "optimized" } }