[PATCH][tree-ssa]: Speed up PRE a bit

[Daniel Berlin]

This knocks a few seconds off some cases with lots of phi nodes that share
preds (we were generating the expression for the same phi pred 500 times,
for about 10-20 preds).

We still won't make heavy gains until we can control the memory usage of
generating expressions, which is harder than it looks.

Bootstrapped and regtested on x86.
--Dan
2003-10-18  Daniel Berlin  <dberlin@dberlin.org>

	* tree-ssa-pre.c (pre_expression): Free and allocate the
	ephi_pindex_htab and phi_pred_cache in this function only.
	(phi_pred_cache): New array to store cached phi preds, to avoid
	recomputation and unnecessary copying.
	(subst_phis): Use it.

Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-pre.c,v
retrieving revision 1.1.4.91
diff -u -3 -p -r1.1.4.91 tree-ssa-pre.c
--- tree-ssa-pre.c	18 Oct 2003 03:09:47 -0000	1.1.4.91
+++ tree-ssa-pre.c	20 Oct 2003 20:16:59 -0000
@@ -311,6 +311,11 @@ struct expr_info
   tree temp;
 };

+
+/* Cache of expressions generated for given phi operand, to avoid
+   recomputation and wasting memory.  */
+tree *phi_pred_cache;
+
 /* Trying to lookup ephi pred operand indexes takes forever on graphs
    that have high connectivity because it's an O(n) linked list
    traversal.  Thus, we set up a hashtable that tells us the operand
@@ -1046,6 +1051,7 @@ generate_expr_as_of_bb (struct expr_info
      simplify the result lest we crash in get_expr_operands.  */
   if (replaced_constants)
     fold_stmt (&expr);
+
 }

 /* Make a copy of Z as it would look in BB j, using the PHIs in BB.  */
@@ -1053,6 +1059,8 @@ static tree
 subst_phis (struct expr_info *ei, tree Z, basic_block j, basic_block bb)
 {
   tree stmt_copy;
+  if (phi_pred_cache[j->index] != NULL_TREE)
+    return phi_pred_cache[j->index];
   stmt_copy = unshare_expr (Z);
   create_stmt_ann (stmt_copy);
   modify_stmt (stmt_copy);
@@ -1061,6 +1069,7 @@ subst_phis (struct expr_info *ei, tree Z
   set_bb_for_stmt (stmt_copy, bb);
   modify_stmt (stmt_copy);
   get_stmt_operands (stmt_copy);
+  phi_pred_cache[j->index] = stmt_copy;
   return stmt_copy;
 }

@@ -2819,6 +2828,7 @@ pre_expression (struct expr_info *slot,
   add_referenced_tmp_var (ei->temp);
   bitmap_clear (created_phi_preds);
   ephi_pindex_htab = htab_create (500, ephi_pindex_hash, ephi_pindex_eq, free);
+  phi_pred_cache = xcalloc (last_basic_block, sizeof (tree));

   if (!expr_phi_insertion ((bitmap *)data, ei))
     goto cleanup;
@@ -2866,6 +2876,12 @@ pre_expression (struct expr_info *slot,
       code_motion (ei);
     }
  cleanup:
+  free (phi_pred_cache);
+  if (ephi_pindex_htab)
+    {
+      htab_delete (ephi_pindex_htab);
+      ephi_pindex_htab = NULL;
+    }
   FOR_EACH_BB (bb)
   {
     bb_ann_t ann = bb_ann (bb);
@@ -3007,11 +3023,6 @@ tree_perform_ssapre (tree fndecl, enum t
       pre_expression (VARRAY_GENERIC_PTR (bexprs, k), pre_dfs);
       free_expr_info (VARRAY_GENERIC_PTR (bexprs, k));
       clear_all_eref_arrays ();
-      if (ephi_pindex_htab)
-	{
-	  htab_delete (ephi_pindex_htab);
-	  ephi_pindex_htab = NULL;
-	}
       ggc_collect ();
       if (redo_dominators)
 	{