PATCH RFC: Speed up compilation of 20001226-1.c

[Ian Lance Taylor <iant at google dot com>]

The irritating test case gcc.c-torture/compile/20001226-1.c takes a
long time to compile.  In particular, I noticed that there was a 0.5%
increase in compile time of that test case with my recently proposed
patch to VRP.  I looked into it a bit, and found that with a small
heuristic in the propagator I could speed up compilation of that test
case by 40% (really) at -O2.  It doesn't seem to make much difference
for other test cases, or for a bootstrap.

Basically, in that highly artificial test case there is a block with
over 8000 predecessors.  Each predecessor is a conditional with two
successors.  It so happens that for each conditional the propagator
puts the block with over 8000 predecessors first on the work list.
Each time that happens, VRP will spend time looking at each
predecessor edge.  Each time one more edge will be executable (which
in this context means that the propagation engine has seen them
already).  It's better for VRP to look at this block last, when all
the edges are executable.

My patch is to change the code which adds a block to the work list so
that, instead of always adding to the tail, it checks if the new block
has fewer predecessors than the tail block, and, if so, the new block
is added to the head instead.  This is a trivial heuristic which in
general tends to encourage faster convergence of the propagation
engine.  It would be possible to actually sort the work list by fewer
predecessors/more successors, but I doubt it's worth the time.  This
heuristic is cheap and has a good effect on extreme test cases like
this.

The patch has been bootstrapped and tested on i686-pc-linux-gnu.  I
plan to commit in a few days unless I hear some comments.

Ian


2007-04-15  Ian Lance Taylor  <iant@google.com>

	* tree-ssa-propagate.c (cfg_blocks_add): Insert blocks with fewer
	predecessors at head rather than tail.


Index: tree-ssa-propagate.c
===================================================================
--- tree-ssa-propagate.c	(revision 123724)
+++ tree-ssa-propagate.c	(working copy)
@@ -176,6 +176,8 @@ cfg_blocks_empty_p (void)
 static void 
 cfg_blocks_add (basic_block bb)
 {
+  bool head = false;
+
   gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
   gcc_assert (!TEST_BIT (bb_in_list, bb->index));
 
@@ -198,12 +200,26 @@ cfg_blocks_add (basic_block bb)
 	  cfg_blocks_head = 0;
 	  VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail);
 	}
-      else
+      /* Minor optimization: we prefer to see blocks with more
+	 predecessors later, because there is more of a chance that
+	 the incoming edges will be executable.  */
+      else if (EDGE_COUNT (bb->preds)
+	       >= EDGE_COUNT (VEC_index (basic_block, cfg_blocks,
+					 cfg_blocks_head)->preds))
 	cfg_blocks_tail = ((cfg_blocks_tail + 1)
 			   % VEC_length (basic_block, cfg_blocks));
+      else
+	{
+	  if (cfg_blocks_head == 0)
+	    cfg_blocks_head = VEC_length (basic_block, cfg_blocks);
+	  --cfg_blocks_head;
+	  head = true;
+	}
     }
 
-  VEC_replace (basic_block, cfg_blocks, cfg_blocks_tail, bb);
+  VEC_replace (basic_block, cfg_blocks,
+	       head ? cfg_blocks_head : cfg_blocks_tail,
+	       bb);
   SET_BIT (bb_in_list, bb->index);
 }