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

login
register
mail settings
Submitter Jan Hubicka
Date Aug. 23, 2013, 3:12 p.m.
Message ID <20130823151254.GA6192@kam.mff.cuni.cz>
Download mbox | patch
Permalink /patch/269482/
State New
Headers show

Comments

Jan Hubicka - Aug. 23, 2013, 3:12 p.m.
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.
Graham Stott - Aug. 23, 2013, 3:48 p.m.
Jan,

This has broken all builds because method_type_class() is defined.

Graham
Paolo Carlini - Aug. 24, 2013, 12:51 a.m.
Hi,

On 08/23/2013 05:12 PM, Jan Hubicka wrote:
> +/* { dg-final { scan-tree-dump-nop "A::foo" 0 "ssa"} } */
This should be scan-tree-dump-not right?

Paolo.
Jan Hubicka - Aug. 24, 2013, 9:04 a.m.
> Hi,
> 
> On 08/23/2013 05:12 PM, Jan Hubicka wrote:
> >+/* { dg-final { scan-tree-dump-nop "A::foo" 0 "ssa"} } */
> This should be scan-tree-dump-not right?

Yes, thanks!  Seems that scan-tree-dump-nop does what name suggests.
I will fix it shortly.

Honza
> 
> Paolo.

Patch

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,