Type inheritance graph analysis & speculative devirtualization, part 4a/6 simple anonymous namespace devirtualization during cgraph construction

[Jan Hubicka <hubicka at ucw dot cz>]

Hi,
this patch makes cgraphunit.c to do very simple devirtualization when method
being called is from anonymous namespace class and none of its derivations
overwrite the method.  I do it in cgraph build only because later we need
http://gcc.gnu.org/ml/gcc-patches/2013-08/msg01007.html first so the code works
correctly during LTO.

To my surprise this actualy matches on firefox build and seems to help.  Once I
have final flag passed from FE.

The patch also modifies reachability walk to not look for methods of anonymous
types.  Here we know that if the method is used, its vtable is reachable and
therefore the method will be walked later.  This saves us from lowering the
method in the second testcase.

Once the final flag is passed to middle end I will be able to handle final
types the same way.

Honza

Bootstrapped/regtested x86_64-linux, will commit it shortly.

	* g++.dg/ipa/devirt-13.C: New testcase.
	* g++.dg/ipa/devirt-14.C: New testcase.
	* cgraphunit.c (analyze_functions): Do basic devirtualization;
	do not walk base classes of anonymous types.

Index: testsuite/g++.dg/ipa/devirt-13.C
===================================================================
--- testsuite/g++.dg/ipa/devirt-13.C	(revision 0)
+++ testsuite/g++.dg/ipa/devirt-13.C	(revision 0)
@@ -0,0 +1,22 @@
+/* { dg-do run } */
+/* Call to foo should be devirtualized because there are no derived types of A.  */
+/* { dg-options "-O2 -fdump-ipa-cgraph -fdump-tree-ssa"  } */
+namespace {
+class A {
+public:
+  virtual int foo(void)
+{
+  return 0;
+}
+};
+}
+class A a, *b=&a;
+main()
+{
+  return b->foo();
+}
+
+/* { dg-final { scan-ipa-dump "Devirtualizing call"  "cgraph"  } } */
+/* { dg-final { scan-tree-dump-times "OBJ_TYPE_REF" 0 "ssa"} } */
+/* { dg-final { cleanup-ipa-dump "cgraph" } } */
+/* { dg-final { cleanup-tree-dump "ssa" } } */
Index: testsuite/g++.dg/ipa/devirt-14.C
===================================================================
--- testsuite/g++.dg/ipa/devirt-14.C	(revision 0)
+++ testsuite/g++.dg/ipa/devirt-14.C	(revision 0)
@@ -0,0 +1,34 @@
+/* No devirtualization happens here, but A::foo should not end up as reachable
+   because the constructor of A is unreachable and therefore the virtual
+   method table referring to A::foo is optimized out.  */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-ssa"  } */
+class B {
+public:
+  virtual int foo(void)
+{
+  return 0;
+}
+};
+namespace {
+class A : public B {
+public:
+  virtual int foo(void)
+{
+  return 1;
+}
+};
+}
+class B a, *b=&a;
+main()
+{
+  if (0)
+    {
+    class A a;
+    a.foo();
+    }
+  return b->foo();
+}
+
+/* { dg-final { scan-tree-dump-nop "A::foo" 0 "ssa"} } */
+/* { dg-final { cleanup-tree-dump "ssa" } } */
Index: cgraphunit.c
===================================================================
--- cgraphunit.c	(revision 201919)
+++ cgraphunit.c	(working copy)
@@ -922,26 +922,73 @@ analyze_functions (void)
 		   enqueue_node ((symtab_node)edge->callee);
 	      if (optimize && flag_devirtualize)
 		{
-	          for (edge = cnode->indirect_calls; edge; edge = edge->next_callee)
-		    if (edge->indirect_info->polymorphic)
-		      {
-			unsigned int i;
-			void *cache_token;
-			vec <cgraph_node *>targets
-			  = possible_polymorphic_call_targets
-			      (edge, NULL, &cache_token);
+		  struct cgraph_edge *next;
+	          for (edge = cnode->indirect_calls; edge; edge = next)
+		    {
+		      next = edge->next_callee;
+		      if (edge->indirect_info->polymorphic)
+			{
+			  unsigned int i;
+			  void *cache_token;
+			  bool final;
+			  vec <cgraph_node *>targets
+			    = possible_polymorphic_call_targets
+				(edge, &final, &cache_token);
 
-			if (!pointer_set_insert (reachable_call_targets,
-						 cache_token))
-			  {
-			    if (cgraph_dump_file)
-			      dump_possible_polymorphic_call_targets 
-				(cgraph_dump_file, edge);
+			  if (!pointer_set_insert (reachable_call_targets,
+						   cache_token))
+			    {
+			      if (cgraph_dump_file)
+				dump_possible_polymorphic_call_targets 
+				  (cgraph_dump_file, edge);
 
-			    for (i = 0; i < targets.length(); i++)
-			      enqueue_node ((symtab_node) targets[i]);
-			  }
-		      }
+			      for (i = 0; i < targets.length(); i++)
+				{
+				  /* Do not bother to mark virtual methods in anonymous namespace;
+				     either we will find use of virtual table defining it, or it is
+				     unused.  */
+				  if (targets[i]->symbol.definition
+				      && TREE_CODE
+					  (TREE_TYPE (targets[i]->symbol.decl))
+					   == METHOD_TYPE
+				      && !type_in_anonymous_namespace_p
+					   (method_class_type
+					     (TREE_TYPE (targets[i]->symbol.decl))))
+				  enqueue_node ((symtab_node) targets[i]);
+				}
+			    }
+
+			  /* Very trivial devirtualization; when the type is
+			     final or anonymous (so we know all its derivation)
+			     and there is only one possible virtual call target,
+			     make the edge direct.  */
+			  if (final)
+			    {
+			      gcc_assert (targets.length());
+			      if (targets.length() == 1)
+				{
+				  if (cgraph_dump_file)
+				    {
+				      fprintf (cgraph_dump_file,
+					       "Devirtualizing call: ");
+				      print_gimple_stmt (cgraph_dump_file,
+							 edge->call_stmt, 0,
+							 TDF_SLIM);
+				    }
+				  cgraph_make_edge_direct (edge, targets[0]);
+				  cgraph_redirect_edge_call_stmt_to_callee (edge);
+				  if (cgraph_dump_file)
+				    {
+				      fprintf (cgraph_dump_file,
+					       "Devirtualized as: ");
+				      print_gimple_stmt (cgraph_dump_file,
+							 edge->call_stmt, 0,
+							 TDF_SLIM);
+				    }
+				}
+			    }
+			}
+		    }
 		}
 
 	      /* If decl is a clone of an abstract function,