[patch] tree-cfg.c: Speed up thread_jumps - Part 6

Kazu Hirata kazu@cs.umass.edu
Fri Oct 22 01:43:00 GMT 2004


Hi,

Attached is a patch to further speed up thread_jumps.

thread_jumps now uses a worklist, called worklist, to store indexes of
basic blocks from which we attempt to thread jumps.

Now, I had a mistake in thinking that some basic blocks whose indexes
are in worklist may be deleted during the course of thread_jumps.
Because of this mistake, I put a guard like this when I take a basic
block's index from worklist.

      bb = BASIC_BLOCK (worklist[size]);
      if (!bb)
	continue;

It turns out that basic blocks whose indexes are in worklist will
never be deleted.  Here is a quick proof.

A basic block BB is deleted during the course of thread_jumps if and
only if it is a forwarder block, and threading through BB makes it
unreachable.

We only put non-forwarder blocks into worklist.

A non-forwarder block BB may become a forwarder one, but that happens
only during thread_jumps_from_bb (BB), at which time BB is no longer
in worklist (i.e., just taken out of worklist).  Since worklist does
not contain duplicates, we know for sure that BB is not in worklist.

The patch removes the guard against deleted basic blocks.  Doing so
allows us to put basic blocks directly into worklist instead of their
indexes.

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2004-10-21  Kazu Hirata  <kazu@cs.umass.edu>

	* tree-cfg.c (thread_jumps): Speed up by putting basic blocks
	into worklist instead of their indexes.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.86
diff -u -p -r2.86 tree-cfg.c
--- tree-cfg.c	21 Oct 2004 16:06:31 -0000	2.86
+++ tree-cfg.c	21 Oct 2004 19:34:14 -0000
@@ -3942,7 +3942,7 @@ thread_jumps (void)
 {
   basic_block bb;
   bool retval = false;
-  int *worklist = xmalloc (sizeof (int) * last_basic_block);
+  basic_block *worklist = xmalloc (sizeof (basic_block) * last_basic_block);
   unsigned int size = 0;
 
   FOR_EACH_BB (bb)
@@ -3951,11 +3951,11 @@ thread_jumps (void)
       bb->flags &= ~BB_VISITED;
     }
 
-  /* Initialize WORKLIST by putting the indexes of non-forwarder
-     blocks that immediately precede forwarder blocks because those
-     are the ones that we know we can thread jumps from.  We use
-     BB_VISITED to indicate that whether a given basic block is in
-     WORKLIST or not, thereby avoiding duplicates in WORKLIST.  */
+  /* Initialize WORKLIST by putting non-forwarder blocks that
+     immediately precede forwarder blocks because those are the ones
+     that we know we can thread jumps from.  We use BB_VISITED to
+     indicate whether a given basic block is in WORKLIST or not,
+     thereby avoiding duplicates in WORKLIST.  */
   FOR_EACH_BB (bb)
     {
       edge_iterator ei;
@@ -3981,7 +3981,7 @@ thread_jumps (void)
 	      && (e->src->flags & BB_VISITED) == 0)
 	    {
 	      e->src->flags |= BB_VISITED;
-	      worklist[size] = e->src->index;
+	      worklist[size] = e->src;
 	      size++;
 	    }
 	}
@@ -3991,14 +3991,7 @@ thread_jumps (void)
   while (size > 0)
     {
       size--;
-      bb = BASIC_BLOCK (worklist[size]);
-
-      /* Check if BB is NULL because BB may have been deleted.  This
-	 could happen if BB is originally a non-forwarder block, later
-	 becomes a forwarder block, and it is deleted when a jump is
-	 threaded through it.  */
-      if (!bb)
-	continue;
+      bb = worklist[size];
 
       /* BB->INDEX is not longer in WORKLIST, so clear BB_VISITED.  */
       bb->flags &= ~BB_VISITED;
@@ -4029,7 +4022,7 @@ thread_jumps (void)
 		      && (f->src->flags & BB_VISITED) == 0)
 		    {
 		      f->src->flags |= BB_VISITED;
-		      worklist[size] = f->src->index;
+		      worklist[size] = f->src;
 		      size++;
 		    }
 		}



More information about the Gcc-patches mailing list