[PR tree-optimization/61515] Fix poor compile-time behaviour in tree-ssa-threadedge.c

[Jeff Law <law at redhat dot com>]

When we thread across a backedge, we have to do invalidations of 
equivalences.  This changes the method by which we identify which 
objects need invalidation.  Previously we'd walk all the SSA_NAMEs and 
see if any had a current value that needed invalidation.  That is 
obviously expensive if we have a lot of SSA_NAMEs.

This patch implements an idea from Richi, basically walk the equivalency 
unwinder stack, which has equivalences from both DOM and the threader. 
Check the current value of each object in that stack and see if it needs 
invalidation.  Even pathlogical cases this ought to be considerably 
faster than walking all the SSA_NAMEs.

For the reduced testcase, compilation time in the relevant parts of GCC 
go from 40 seconds to less than a second.

Bootstrapped and regression tested on x86_64-unknown-linux-gnu. 
Installed on the trunk.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 966c0b4..0c8eb79 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2014-11-07  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/61515
+	* tree-ssa-threadedge.c (invalidate_equivalences): Walk the unwinding
+	stack rather than looking at every SSA_NAME's value.
+
 2014-11-07  Richard Biener  <rguenther@suse.de>
 
 	PR tree-optimization/63605
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index de3c819..d5b9696 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -290,15 +290,40 @@ fold_assignment_stmt (gimple stmt)
 }
 
 /* A new value has been assigned to LHS.  If necessary, invalidate any
-   equivalences that are no longer valid.  */
+   equivalences that are no longer valid.   This includes invaliding
+   LHS and any objects that are currently equivalent to LHS.
+
+   Finding the objects that are currently marked as equivalent to LHS
+   is a bit tricky.  We could walk the ssa names and see if any have
+   SSA_NAME_VALUE that is the same as LHS.  That's expensive.
+
+   However, it's far more efficient to look at the unwinding stack as
+   that will have all context sensitive equivalences which are the only
+   ones that we really have to worry about here.   */
 static void
 invalidate_equivalences (tree lhs, vec<tree> *stack)
 {
 
-  for (unsigned int i = 1; i < num_ssa_names; i++)
-    if (ssa_name (i) && SSA_NAME_VALUE (ssa_name (i)) == lhs)
-      record_temporary_equivalence (ssa_name (i), NULL_TREE, stack);
+  /* The stack is an unwinding stack.  If the current element is NULL
+     then it's a "stop unwinding" marker.  Else the current marker is
+     the SSA_NAME with an equivalence and the prior entry in the stack
+     is what the current element is equivalent to.  */
+  for (int i = stack->length() - 1; i >= 0; i--)
+    {
+      /* Ignore the stop unwinding markers.  */
+      if ((*stack)[i] == NULL)
+	continue;
+
+      /* We want to check the current value of stack[i] to see if
+	 it matches LHS.  If so, then invalidate.  */
+      if (SSA_NAME_VALUE ((*stack)[i]) == lhs)
+	record_temporary_equivalence ((*stack)[i], NULL_TREE, stack);
+
+      /* Remember, we're dealing with two elements in this case.  */
+      i--;
+    }
 
+  /* And invalidate any known value for LHS itself.  */
   if (SSA_NAME_VALUE (lhs))
     record_temporary_equivalence (lhs, NULL_TREE, stack);
 }