This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] More jump threading cleanups



Two cleanups I noticed late last week while working on the general case FSA optimization.

First, we were not cancelling jump threads through joiner blocks when there is any edge on the jump threading path with a recorded jump thread opportunity. We were not nearly as aggressive at pruning as we should have been resulting in useless block duplication.

Second, in the general form of the FSA optimization, we can have jump threading path which starts with a join point and traverses through a normal jump threading block (ie, has side effects and a compile-time determinable out-edge). To facilitate these opportunities, we want to call thread_through_normal_block after threading through a joiner block. Thus we need thread_through_normal_block to accept the bitmap of blocks we have already visited and check it appropriately.

Bootstrapped & regression tested on x86_64-unknown-linux-gnu. Installed on trunk.


diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index c5b794e..54298e4 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,15 @@
+2013-10-21  Jeff Law  <law@redhat.com>
+
+	* tree-ssa-threadedge.c (thread_through_normal_block): New argument VISITED.
+	Remove VISISTED as a local variable.  When we have a threadable jump, verify
+	the destination of the jump has not been visised.
+	(thread_across_edge): Allocate VISITED bitmap once at function scope and
+	use it throughout.  Make sure to set appropriate bits in VISITED for E (start
+	of jump thread path).
+
+	* tree-ssa-threadupdate.c (mark_threaded_blocks): Reject threading through
+	a joiner if any edge on the path has a recorded jump thread.
+
 2013-10-21  Ian Lance Taylor  <iant@google.com>
 
 	* doc/invoke.texi (Optimize Options): For -fno-toplevel-reorder,
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index f567557..ebd93cb 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -883,7 +883,8 @@ thread_through_normal_block (edge e,
 			     bool handle_dominating_asserts,
 			     vec<tree> *stack,
 			     tree (*simplify) (gimple, gimple),
-			     vec<jump_thread_edge *> *path)
+			     vec<jump_thread_edge *> *path,
+			     bitmap visited)
 {
   /* If E is a backedge, then we want to verify that the COND_EXPR,
      SWITCH_EXPR or GOTO_EXPR at the end of e->dest is not affected
@@ -922,11 +923,10 @@ thread_through_normal_block (edge e,
 	{
 	  edge taken_edge = find_taken_edge (e->dest, cond);
 	  basic_block dest = (taken_edge ? taken_edge->dest : NULL);
-	  bitmap visited;
 
 	  /* DEST could be NULL for a computed jump to an absolute
 	     address.  */
-	  if (dest == NULL || dest == e->dest)
+	  if (dest == NULL || dest == e->dest || bitmap_bit_p (visited, dest->index))
 	    return false;
 
           jump_thread_edge *x
@@ -944,7 +944,6 @@ thread_through_normal_block (edge e,
 	    {
 	      /* We don't want to thread back to a block we have already
  		 visited.  This may be overly conservative.  */
-	      visited = BITMAP_ALLOC (NULL);
 	      bitmap_set_bit (visited, dest->index);
 	      bitmap_set_bit (visited, e->dest->index);
 	      thread_around_empty_blocks (taken_edge,
@@ -953,7 +952,6 @@ thread_through_normal_block (edge e,
 					  simplify,
 					  visited,
 					  path);
-	      BITMAP_FREE (visited);
 	    }
 	  return true;
 	}
@@ -995,15 +993,21 @@ thread_across_edge (gimple dummy_cond,
 		    vec<tree> *stack,
 		    tree (*simplify) (gimple, gimple))
 {
+  bitmap visited = BITMAP_ALLOC (NULL);
+
   stmt_count = 0;
 
   vec<jump_thread_edge *> *path = new vec<jump_thread_edge *> ();
+  bitmap_clear (visited);
+  bitmap_set_bit (visited, e->src->index);
+  bitmap_set_bit (visited, e->dest->index);
   if (thread_through_normal_block (e, dummy_cond, handle_dominating_asserts,
-				   stack, simplify, path))
+				   stack, simplify, path, visited))
     {
       propagate_threaded_block_debug_into (path->last ()->e->dest,
 					   e->dest);
       remove_temporary_equivalences (stack);
+      BITMAP_FREE (visited);
       register_jump_thread (path);
       return;
     }
@@ -1030,7 +1034,6 @@ thread_across_edge (gimple dummy_cond,
     edge taken_edge;
     edge_iterator ei;
     bool found;
-    bitmap visited = BITMAP_ALLOC (NULL);
 
     /* Look at each successor of E->dest to see if we can thread through it.  */
     FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
diff --git a/gcc/tree-ssa-threadupdate.c b/gcc/tree-ssa-threadupdate.c
index e791269..737a6a2 100644
--- a/gcc/tree-ssa-threadupdate.c
+++ b/gcc/tree-ssa-threadupdate.c
@@ -1244,7 +1244,7 @@ mark_threaded_blocks (bitmap threaded_blocks)
      When this occurs ignore the jump thread request with the joiner
      block.  It's totally subsumed by the simpler jump thread request.
 
-     This results in less block copying, simpler CFGs.  More improtantly,
+     This results in less block copying, simpler CFGs.  More importantly,
      when we duplicate the joiner block, B, in this case we will create
      a new threading opportunity that we wouldn't be able to optimize
      until the next jump threading iteration.
@@ -1263,20 +1263,30 @@ mark_threaded_blocks (bitmap threaded_blocks)
 	}
     }
 
-
-  /* Now iterate again, converting cases where we threaded through
-     a joiner block, but ignoring those where we have already
-     threaded through the joiner block.  */
+  /* Now iterate again, converting cases where we want to thread
+     through a joiner block, but only if no other edge on the path
+     already has a jump thread attached to it.  */
   for (i = 0; i < paths.length (); i++)
     {
       vec<jump_thread_edge *> *path = paths[i];
 
-      if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK
-	  && (*path)[0]->e->aux == NULL)
+      
+      if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
 	{
-	  edge e = (*path)[0]->e;
-	  e->aux = path;
-	  bitmap_set_bit (tmp, e->dest->index);
+	  unsigned int j;
+
+	  for (j = 0; j < path->length (); j++)
+	    if ((*path)[j]->e->aux != NULL)
+	      break;
+
+	  /* If we iterated through the entire path without exiting the loop,
+	     then we are good to go, attach the path to the starting edge.  */
+	  if (j == path->length ())
+	    {
+	      edge e = (*path)[0]->e;
+	      e->aux = path;
+	      bitmap_set_bit (tmp, e->dest->index);
+	    }
 	}
     }
 

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]