[patch] tree-cfg.c: Clean up thread_jumps.

[Kazu Hirata]

Hi,

Attached is a patch to clean up thread_jumps.

thread_jumps calls tree_forwarder_block_p to check if a given basic
block is a forwarder block or not.  tree_forwarder_block_p uses
bb_ann (bb)->forwardable to cache its own result but uses a rather
strange semantics.  Specifically,

bb_ann (bb)->forwardable == 0 if bb is not a forwarder block.
bb_ann (bb)->forwardable == 1 if bb may or may not be a forwarder block.

That is, when forwardable is 0, it tells us something for sure, but
when forwardable is 1, it doesn't tell us anything useful.  The idea
is to clean this up so that both values of forwardable give us useful
information.  Specifically, the patch changes the semantics as
follows:

bb_ann (bb)->forwardable == 0 if bb is not a forwarder block.
bb_ann (bb)->forwardable == 1 if bb is a forwarder block.

In order to implement this semantics, the patch teaches thread_jumps
to initialize the forwardable marks for each basic block up front.  We
never have to change its value except when we have

<L1>
  if (COND) goto <L2>; else goto <L3>;

<L2>:;

<L3>:;

and want to thread "goto <L2>", in which case, we get

<L1>
  goto L3;

<L2>:;

<L3>:;

Note that the basic block starting with <L1> was originally not a
forwarder block, but now it is.  So I check for this case at the end
of thread_jumps and update the forwardable mark.

Other than that, the patch just mechanically replaces
tree_forwarder_block_p with bb_ann (bb)->forwardable.

Here is the timing for 10 runs of "cc1 -quiet -O2 -o /dev/null fold-const.i"

      original         patched
real:  183.081  183.162 (0.044% up)
user:  181.049  181.025 (0.013% down)
tfbp:   456868   193646

tfbp is the number of calls to tree_forwardable_blocks_p, which goes
down significantly.  The difference in the running time is negligible.

The forwardable marks are also used to detect an infinite loop.  You
might wonder how this patch affects the detection of an infinite loop.
Well, there is no effect because those forwardable marks that are
reset to 0 are immediately restored to 1.

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

p.s.
Once this patch goes in, it's very easy to remove the while loop in
cleanup_tree_cfg.  That is, we won't have to repeat thread_jumps in a
fixed point operation.

Kazu Hirata

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

	* tree-cfg.c (tree_forwarder_block_p): Don't set forwardable.
	(thread_jumps): Use forwardable as cache of
	tree_forwarder_block_p throughout the function.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.72
diff -u -r2.72 tree-cfg.c
--- tree-cfg.c	8 Oct 2004 13:20:39 -0000	2.72
+++ tree-cfg.c	8 Oct 2004 14:09:12 -0000
@@ -3706,11 +3706,6 @@
   edge e;
   edge_iterator ei;
 
-  /* If we have already determined that this block is not forwardable,
-     then no further checks are necessary.  */
-  if (! bb_ann (bb)->forwardable)
-    return false;
-
   /* BB must have a single outgoing edge.  */
   if (EDGE_COUNT (bb->succs) != 1
       /* BB can not have any PHI nodes.  This could potentially be
@@ -3721,10 +3716,7 @@
       || EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
       /* BB may not have an abnormal outgoing edge.  */
       || (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
-    {
-      bb_ann (bb)->forwardable = 0;
-      return false; 
-    }
+    return false; 
 
 #if ENABLE_CHECKING
   gcc_assert (bb != ENTRY_BLOCK_PTR);
@@ -3733,10 +3725,7 @@
   /* Successors of the entry block are not forwarders.  */
   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
     if (e->dest == bb)
-      {
-	bb_ann (bb)->forwardable = 0;
-	return false;
-      }
+      return false;
 
   /* Now walk through the statements.  We can ignore labels, anything else
      means this is not a forwarder block.  */
@@ -3752,7 +3741,6 @@
 	  break;
 
 	default:
-	  bb_ann (bb)->forwardable = 0;
 	  return false;
 	}
     }
@@ -3780,21 +3768,17 @@
   bool retval = false;
 
   FOR_EACH_BB (bb)
-    bb_ann (bb)->forwardable = 1;
+    bb_ann (bb)->forwardable = tree_forwarder_block_p (bb);
 
   FOR_EACH_BB (bb)
     {
       edge_iterator ei;
+      bool this_jump_threaded = false;
 
       /* Don't waste time on forwarders.  */
-      if (tree_forwarder_block_p (bb))
+      if (bb_ann (bb)->forwardable)
 	continue;
 
-      /* This block is now part of a forwarding path, mark it as not
-	 forwardable so that we can detect loops.  This bit will be
-	 reset below.  */
-      bb_ann (bb)->forwardable = 0;
-
       /* Examine each of our block's successors to see if it is
 	 forwardable.  */
       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
@@ -3805,7 +3789,7 @@
 	  /* If the edge is abnormal or its destination is not
 	     forwardable, then there's nothing to do.  */
 	  if ((e->flags & EDGE_ABNORMAL)
-	      || !tree_forwarder_block_p (e->dest))
+	      || !bb_ann (e->dest)->forwardable)
 	    {
 	      ei_next (&ei);
 	      continue;
@@ -3820,7 +3804,7 @@
 	  last = EDGE_SUCC (e->dest, 0);
 	  bb_ann (e->dest)->forwardable = 0;
 	  for (dest = EDGE_SUCC (e->dest, 0)->dest;
-	       tree_forwarder_block_p (dest);
+	       bb_ann (dest)->forwardable;
 	       last = EDGE_SUCC (dest, 0),
 	       dest = EDGE_SUCC (dest, 0)->dest)
 	    bb_ann (dest)->forwardable = 0;
@@ -3861,7 +3845,7 @@
 	    }
 
 	  /* Perform the redirection.  */
-	  retval = true;
+	  retval = this_jump_threaded = true;
 	  old_dest = e->dest;
 	  e = redirect_edge_and_branch (e, dest);
 
@@ -3941,9 +3925,13 @@
 	    }
 	}
 
-      /* Reset the forwardable bit on our block since it's no longer in
-	 a forwarding chain path.  */
-      bb_ann (bb)->forwardable = 1;
+      /* If we succeeded in threading a jump at BB, update the
+	 forwardable mark as BB may have become a new forwarder block.
+	 This could happen if we have a useless "if" statement whose
+	 two arms eventually merge without any intervening
+	 statements.  */
+      if (this_jump_threaded && tree_forwarder_block_p (bb))
+	bb_ann (bb)->forwardable = true;
     }
 
   return retval;