[patch] tree-outof-ssa.c: Speed up perform_edge_inserts.

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi,

Attached is a patch to speed up perform_edge_inserts.

perform_edge_inserts has a call tree like so:

perform_edge_inserts
  analyze_edges_for_bb
    make_forwarder_block
      iterate_fix_dominators

If we have a lot of edge insertions, we would need to call
iterate_fix_dominators a lot, which isn't very fast.  What matters
worse, despite the efforts that iterate_fix_dominators make to
maintain the dominator information up-to-date, we do

  if (changed)
    {
      free_dominance_info (CDI_DOMINATORS);
      free_dominance_info (CDI_POST_DOMINATORS);
    }

That is, all the efforts are wasted.

The patch solves this problem by unconditonally calling
free_dominance_info before perform_edge_inserts.  AFAIK, no tree pass
needs dominator information after the out-of-ssa, so it should be OK
to call free_dominance_info.

Since we don't need the the return value of analyze_edges_for_bb, the
patch changes the return type to void.

Here is a timing in seconds for five runs of ./cc1 -quiet -O2
-fomit-frame-pointer -o /dev/null.

               original patched   diff%
c-common.i       13.833  13.832 -0.007%
combine.i        16.908  16.847 -0.360%
fold-const.i     18.409  18.382 -0.146%
reload1.i        12.033  12.011 -0.182%
reload.i         11.925  11.918 -0.058%
insn-attrtab.i  208.203 205.239 -1.423%

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

Kazu Hirata

2005-03-10  Kazu Hirata  <kazu@cs.umass.edu>

	* tree-outof-ssa.c (analyze_edges_for_bb): Make the return
	type void.
	(perform_edge_inserts): Unconditionally call
	free_dominator_info.

Index: tree-outof-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-outof-ssa.c,v
retrieving revision 2.49
diff -u -d -p -r2.49 tree-outof-ssa.c
--- tree-outof-ssa.c	9 Mar 2005 11:34:38 -0000	2.49
+++ tree-outof-ssa.c	10 Mar 2005 17:19:12 -0000
@@ -2026,7 +2026,7 @@ identical_stmt_lists_p (edge e1, edge e2
    any debug information to DEBUG_FILE.  Return true if anything other than a 
    standard edge insertion is done.  */
 
-static bool 
+static void
 analyze_edges_for_bb (basic_block bb, FILE *debug_file)
 {
   edge e;
@@ -2057,7 +2057,7 @@ analyze_edges_for_bb (basic_block bb, FI
       FOR_EACH_EDGE (e, ei, bb->preds)
 	if (PENDING_STMT (e))
 	  bsi_commit_one_edge_insert (e, NULL);
-      return false;
+      return;
     }
   /* Find out how many edges there are with interesting pending stmts on them.  
      Commit the stmts on edges we are not interested in.  */
@@ -2094,7 +2094,7 @@ analyze_edges_for_bb (basic_block bb, FI
     {
       if (single_edge)
         bsi_commit_one_edge_insert (single_edge, NULL);
-      return false;
+      return;
     }
 
   /* Ensure that we have empty worklists.  */
@@ -2156,7 +2156,7 @@ analyze_edges_for_bb (basic_block bb, FI
       VARRAY_POP_ALL (edge_leader);
       VARRAY_POP_ALL (stmt_list);
       bitmap_clear (leader_has_match);
-      return false;
+      return;
     }
 
 
@@ -2221,8 +2221,6 @@ analyze_edges_for_bb (basic_block bb, FI
   VARRAY_POP_ALL (edge_leader);
   VARRAY_POP_ALL (stmt_list);
   bitmap_clear (leader_has_match);
-
-  return true;
 }
 
 
@@ -2236,26 +2234,26 @@ static void
 perform_edge_inserts (FILE *dump_file)
 {
   basic_block bb;
-  bool changed = false;
 
   if (dump_file)
     fprintf(dump_file, "Analyzing Edge Insertions.\n");
 
+  /* analyze_edges_for_bb calls make_forwarder_block, which tries to
+     incrementally update the dominator information.  Since we don't
+     need dominator information after this pass, go ahead and free the
+     dominator information.  */
+  free_dominance_info (CDI_DOMINATORS);
+  free_dominance_info (CDI_POST_DOMINATORS);
+
   FOR_EACH_BB (bb)
-    changed |= analyze_edges_for_bb (bb, dump_file);
+    analyze_edges_for_bb (bb, dump_file);
 
-  changed |= analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
+  analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
 
   /* Clear out any tables which were created.  */
   edge_leader = NULL;
   BITMAP_FREE (leader_has_match);
 
-  if (changed)
-    {
-      free_dominance_info (CDI_DOMINATORS);
-      free_dominance_info (CDI_POST_DOMINATORS);
-    }
-
 #ifdef ENABLE_CHECKING
   {
     edge_iterator ei;