[PATCH] Speed up copyprop (part of PR26830)

[Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>]

Hello, PR26830 exposes cases in which SSA processing is made slow 
(quadratic or worse) by a basic block with a huge number of PHIs and a 
huge number of predecessors.

As a fix for the copyprop slowness, we can avoid processing memory-tag 
PHIs are useless to process unless doing store copyprop.  Another small 
optimization is to check the loop depth of copied variables only once in 
init_copy_prop, instead of doing that every time the statement is 
visited.  On x86 I get no difference in assembly language for the 
testcase in the PR and also for all of SPECcpu2000.

It may be possible to do further improvements (building in fact a 
union-find algorithm into copyprop), but it seems worthless for now.  
The patch in fact brings copyprop in the noise on the PR26830 testcase 
with -fno-tree-ch (the test case takes two hours to compile with loop 
header copying enabled!), trimming ~20% of the compile time.  What 
remains is (times by Richard Guenther on ia64):

tree PHI insertion    :  79.40 (13%) usr
tree SSA rewrite      :  94.23 (16%) usr
dominator optimization:  66.17 (11%) usr]

The first two are insanely higher with loop header copying enabled -- 
but they are still the only major offenders.

The patch has been bootstrapped/regtested i686-pc-linux-gnu.  Ok for 
4.1/4.2?

Paolo
2006-03-29  Paolo Bonzini  <bonzini@gnu.org>

	* tree-ssa-copy.c (copy_prop_visit_assignment): Do not check
	loop depth.
	(copy_prop_visit_stmt): Remove write-only variable ann.
	(init_copy_prop): Check variable loop depth here.  Do not
	simulate memory-tag PHIs except for store copy prop.

Index: tree-ssa-copy.c
===================================================================
--- tree-ssa-copy.c	(revision 112413)
+++ tree-ssa-copy.c	(working copy)
@@ -550,14 +563,6 @@ copy_prop_visit_assignment (tree stmt, t
       if (!may_propagate_copy (lhs, rhs))
 	return SSA_PROP_VARYING;
 
-      /* Avoid copy propagation from an inner into an outer loop.
-	 Otherwise, this may move loop variant variables outside of
-	 their loops and prevent coalescing opportunities.  If the
-	 value was loop invariant, it will be hoisted by LICM and
-	 exposed for copy propagation.  */
-      if (loop_depth_of_name (rhs) > loop_depth_of_name (lhs))
-	return SSA_PROP_VARYING;
-
       /* Notice that in the case of assignments, we make the LHS be a
 	 copy of RHS's value, not of RHS itself.  This avoids keeping
 	 unnecessary copy-of chains (assignments cannot be in a cycle
@@ -671,7 +676,6 @@ copy_prop_visit_cond_stmt (tree stmt, ed
 static enum ssa_prop_result
 copy_prop_visit_stmt (tree stmt, edge *taken_edge_p, tree *result_p)
 {
-  stmt_ann_t ann;
   enum ssa_prop_result retval;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -681,8 +685,6 @@ copy_prop_visit_stmt (tree stmt, edge *t
       fprintf (dump_file, "\n");
     }
 
-  ann = stmt_ann (stmt);
-
   if (TREE_CODE (stmt) == MODIFY_EXPR
       && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
       && (do_store_copy_prop
@@ -856,37 +858,54 @@ init_copy_prop (void)
   FOR_EACH_BB (bb)
     {
       block_stmt_iterator si;
-      tree phi;
+      tree phi, def;
+      int depth = bb->loop_depth;
 
       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 	{
 	  tree stmt = bsi_stmt (si);
+	  ssa_op_iter iter;
 
 	  /* The only statements that we care about are those that may
 	     generate useful copies.  We also need to mark conditional
 	     jumps so that their outgoing edges are added to the work
-	     lists of the propagator.  */
+	     lists of the propagator.
+
+	     Avoid copy propagation from an inner into an outer loop.
+	     Otherwise, this may move loop variant variables outside of
+	     their loops and prevent coalescing opportunities.  If the
+	     value was loop invariant, it will be hoisted by LICM and
+	     exposed for copy propagation.  */
 	  if (stmt_ends_bb_p (stmt))
 	    DONT_SIMULATE_AGAIN (stmt) = false;
-	  else if (stmt_may_generate_copy (stmt))
+	  else if (stmt_may_generate_copy (stmt)
+		   && loop_depth_of_name (TREE_OPERAND (stmt, 1)) <= depth)
 	    DONT_SIMULATE_AGAIN (stmt) = false;
 	  else
-	    {
-	      tree def;
-	      ssa_op_iter iter;
-
-	      /* No need to simulate this statement anymore.  */
-	      DONT_SIMULATE_AGAIN (stmt) = true;
+	    DONT_SIMULATE_AGAIN (stmt) = true;
 
-	      /* Mark all the outputs of this statement as not being
-		 the copy of anything.  */
-	      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
-		set_copy_of_val (def, def, NULL_TREE);
-	    }
+	  /* Mark all the outputs of this statement as not being
+	     the copy of anything.  */
+	  if (DONT_SIMULATE_AGAIN (stmt))
+	    FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
+	      set_copy_of_val (def, def, NULL_TREE);
 	}
 
       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
-	DONT_SIMULATE_AGAIN (phi) = false;
+	{
+	  def = PHI_RESULT (phi);
+	  if (!do_store_copy_prop && MTAG_P (SSA_NAME_VAR (def)))
+	    DONT_SIMULATE_AGAIN (phi) = true;
+	  else
+	    DONT_SIMULATE_AGAIN (phi) = false;
+
+	  if (DONT_SIMULATE_AGAIN (phi))
+	    set_copy_of_val (def, def, NULL_TREE);
+	}
     }
 }