diff mbox

Refactoring shared code in jump threading/dom

Message ID 55315E19.8010802@redhat.com
State New
Headers show

Commit Message

Jeff Law April 17, 2015, 7:25 p.m. UTC
DOM and jump threading both want to manipulate the SSA_NAME equivalency 
tables.  Right now DOM passes its table into the threader and the 
threader manipulates the table directly (knowing its really just a 
vector stack).

This results in duplicated code and a general lack of encapsulation.

This patch creates a class to hold the equivalency stack and the obvious 
methods needed by DOM and threading.  This should not change the code we 
generate.

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

The next step on the path to resolving 47679 is to make a similar change 
for the expression table.   That's far more interesting because to fix 
47679 we need to be able to add and remove entries in the expression 
table within the threader and it seems the natural way to do that is to 
encapsulate the table in a class with reasonable methods and pass that 
into the threader instead of having the threader know intimate details 
about the hash table.

Jeff
commit 5c9aacc9ad269f59480dc87bfae60c3eb73f7cd4
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Fri Apr 17 19:24:17 2015 +0000

    	PR tree-optimization/47679
    	* Makefile.in (OBJS); Add tree-ssa-scopedtables.o.
    	* tree-ssa-scopedtables.c: New file.
    	* tree-ssa-scopedtables.h: New file.
    	* tree-ssa-dom.c: Include tree-ssa-scopedtables.h.
    	(const_and_copies): Change name/type.
    	(record_const_or_copy): Move into tree-ssa-scopedtables.c
    	(record_const_or_copy_1): Similarly.
    	(restore_vars_to_original_value): Similarly.
    	(pass_dominator::execute): Create and destroy const_and_copies table.
    	(thread_across_edge): Update passing of const_and_copies.
    	(record_temporary_equivalence): Use method calls rather than
    	manipulating const_and_copies directly.
    	(record_equality, cprop_into_successor_phis): Similarly.
    	(dom_opt_dom_walker::before_dom_children): Similarly.
    	(dom_opt_dom_walker::after_dom_children): Similarly.
    	(eliminate_redundant_computations): Similarly.
    	* tree-ssa-threadedge.c (remove_temporary_equivalences): Delete.
    	(record_temporary_equivalence): Likewise.
    	(invalidate_equivalences): Likewise.
    	(record_temporary_equivalences_from_phis): Update due to type
    	change of const_and_copies.  Use method calls rather than
    	manipulating the stack directly.
    	(record_temporary_equivalences_from_stmts_at_dest): Likewise.
    	(thread_through_normal_block, thread_across_edge): Likewise.
    	(thread_across_edge): Likewise.
    	* tree-ssa-threadedge.h (thread_across_edge): Update prototype.
    	* tree-vrp.c: Include tree-ssa-scopedtables.h.  Change type
    	of equiv_stack.
    	(identify_jump_threads): Update due to type change of equiv_stack.
    	(finalize_jump_threads): Delete the equiv_stack when complete.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@222195 138bc75d-0d04-0410-961f-82ee72b054a4
diff mbox

Patch

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4fbb70b..e0a4cbf 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,37 @@ 
+2015-04-17  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/47679
+	* Makefile.in (OBJS); Add tree-ssa-scopedtables.o.
+	* tree-ssa-scopedtables.c: New file.
+	* tree-ssa-scopedtables.h: New file.
+	* tree-ssa-dom.c: Include tree-ssa-scopedtables.h.
+	(const_and_copies): Change name/type.
+	(record_const_or_copy): Move into tree-ssa-scopedtables.c
+	(record_const_or_copy_1): Similarly.
+	(restore_vars_to_original_value): Similarly.
+	(pass_dominator::execute): Create and destroy const_and_copies table.
+	(thread_across_edge): Update passing of const_and_copies.
+	(record_temporary_equivalence): Use method calls rather than
+	manipulating const_and_copies directly.
+	(record_equality, cprop_into_successor_phis): Similarly.
+	(dom_opt_dom_walker::before_dom_children): Similarly.
+	(dom_opt_dom_walker::after_dom_children): Similarly.
+	(eliminate_redundant_computations): Similarly.
+	* tree-ssa-threadedge.c (remove_temporary_equivalences): Delete.
+	(record_temporary_equivalence): Likewise.
+	(invalidate_equivalences): Likewise.
+	(record_temporary_equivalences_from_phis): Update due to type
+	change of const_and_copies.  Use method calls rather than
+	manipulating the stack directly.
+	(record_temporary_equivalences_from_stmts_at_dest): Likewise.
+	(thread_through_normal_block, thread_across_edge): Likewise.
+	(thread_across_edge): Likewise.
+	* tree-ssa-threadedge.h (thread_across_edge): Update prototype.
+	* tree-vrp.c: Include tree-ssa-scopedtables.h.  Change type
+	of equiv_stack.
+	(identify_jump_threads): Update due to type change of equiv_stack.
+	(finalize_jump_threads): Delete the equiv_stack when complete.
+
 2015-04-17  Uros Bizjak  <ubizjak@gmail.com>
 
 	* config/i386/i386.h (LEGITIMIZE_RELOAD_ADDRESS): Remove.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 4ab7405..80c91f0 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1452,6 +1452,7 @@  OBJS = \
 	tree-ssa-propagate.o \
 	tree-ssa-reassoc.o \
 	tree-ssa-sccvn.o \
+	tree-ssa-scopedtables.o \
 	tree-ssa-sink.o \
 	tree-ssa-strlen.o \
 	tree-ssa-structalias.o \
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 907fa97..8eec5d9 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -70,6 +70,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-threadupdate.h"
 #include "langhooks.h"
 #include "params.h"
+#include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
 #include "tree-ssa-dom.h"
 #include "inchash.h"
@@ -235,11 +236,8 @@  expr_elt_hasher::remove (value_type &element)
    in this table.  */
 static hash_table<expr_elt_hasher> *avail_exprs;
 
-/* Stack of dest,src pairs that need to be restored during finalization.
-
-   A NULL entry is used to mark the end of pairs which need to be
-   restored during finalization of this block.  */
-static vec<tree> const_and_copies_stack;
+/* Unwindable const/copy equivalences.  */
+static const_and_copies *const_and_copies;
 
 /* Track whether or not we have changed the control flow graph.  */
 static bool cfg_altered;
@@ -268,14 +266,12 @@  static hashval_t avail_expr_hash (const void *);
 static void htab_statistics (FILE *,
 			     const hash_table<expr_elt_hasher> &);
 static void record_cond (cond_equivalence *);
-static void record_const_or_copy (tree, tree);
 static void record_equality (tree, tree);
 static void record_equivalences_from_phis (basic_block);
 static void record_equivalences_from_incoming_edge (basic_block);
 static void eliminate_redundant_computations (gimple_stmt_iterator *);
 static void record_equivalences_from_stmt (gimple, int);
 static void remove_local_expressions_from_table (void);
-static void restore_vars_to_original_value (void);
 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
 
 
@@ -1196,7 +1192,7 @@  pass_dominator::execute (function *fun)
   /* Create our hash tables.  */
   avail_exprs = new hash_table<expr_elt_hasher> (1024);
   avail_exprs_stack.create (20);
-  const_and_copies_stack.create (20);
+  const_and_copies = new class const_and_copies (dump_file, dump_flags);
   need_eh_cleanup = BITMAP_ALLOC (NULL);
   need_noreturn_fixup.create (0);
 
@@ -1319,7 +1315,7 @@  pass_dominator::execute (function *fun)
   BITMAP_FREE (need_eh_cleanup);
   need_noreturn_fixup.release ();
   avail_exprs_stack.release ();
-  const_and_copies_stack.release ();
+  delete const_and_copies;
 
   /* Free the value-handle array.  */
   threadedge_finalize_values ();
@@ -1420,36 +1416,6 @@  remove_local_expressions_from_table (void)
     }
 }
 
-/* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore
-   CONST_AND_COPIES to its original state, stopping when we hit a
-   NULL marker.  */
-
-static void
-restore_vars_to_original_value (void)
-{
-  while (const_and_copies_stack.length () > 0)
-    {
-      tree prev_value, dest;
-
-      dest = const_and_copies_stack.pop ();
-
-      if (dest == NULL)
-	break;
-
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "<<<< COPY ");
-	  print_generic_expr (dump_file, dest, 0);
-	  fprintf (dump_file, " = ");
-	  print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0);
-	  fprintf (dump_file, "\n");
-	}
-
-      prev_value = const_and_copies_stack.pop ();
-      set_ssa_name_value (dest, prev_value);
-    }
-}
-
 /* A trivial wrapper so that we can present the generic jump
    threading code with a simple API for simplifying statements.  */
 static tree
@@ -1479,7 +1445,7 @@  record_temporary_equivalences (edge e)
 
       /* If we have a simple NAME = VALUE equivalence, record it.  */
       if (lhs && TREE_CODE (lhs) == SSA_NAME)
-	record_const_or_copy (lhs, rhs);
+	const_and_copies->record_const_or_copy (lhs, rhs);
 
       /* If we have 0 = COND or 1 = COND equivalences, record them
 	 into our expression hash tables.  */
@@ -1505,7 +1471,7 @@  dom_opt_dom_walker::thread_across_edge (edge e)
      current state.  */
   avail_exprs_stack.safe_push
     (std::pair<expr_hash_elt_t, expr_hash_elt_t> (NULL, NULL));
-  const_and_copies_stack.safe_push (NULL_TREE);
+  const_and_copies->push_marker ();
 
   /* Traversing E may result in equivalences we can utilize.  */
   record_temporary_equivalences (e);
@@ -1513,7 +1479,7 @@  dom_opt_dom_walker::thread_across_edge (edge e)
   /* With all the edge equivalences in the tables, go ahead and attempt
      to thread through E->dest.  */
   ::thread_across_edge (m_dummy_cond, e, false,
-		        &const_and_copies_stack,
+		        const_and_copies,
 		        simplify_stmt_for_jump_threading);
 
   /* And restore the various tables to their state before
@@ -1752,48 +1718,6 @@  record_cond (cond_equivalence *p)
     free_expr_hash_elt (element);
 }
 
-/* A helper function for record_const_or_copy and record_equality.
-   Do the work of recording the value and undo info.  */
-
-static void
-record_const_or_copy_1 (tree x, tree y, tree prev_x)
-{
-  set_ssa_name_value (x, y);
-
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    {
-      fprintf (dump_file, "0>>> COPY ");
-      print_generic_expr (dump_file, x, 0);
-      fprintf (dump_file, " = ");
-      print_generic_expr (dump_file, y, 0);
-      fprintf (dump_file, "\n");
-    }
-
-  const_and_copies_stack.reserve (2);
-  const_and_copies_stack.quick_push (prev_x);
-  const_and_copies_stack.quick_push (x);
-}
-
-/* Record that X is equal to Y in const_and_copies.  Record undo
-   information in the block-local vector.  */
-
-static void
-record_const_or_copy (tree x, tree y)
-{
-  tree prev_x = SSA_NAME_VALUE (x);
-
-  gcc_assert (TREE_CODE (x) == SSA_NAME);
-
-  if (TREE_CODE (y) == SSA_NAME)
-    {
-      tree tmp = SSA_NAME_VALUE (y);
-      if (tmp)
-	y = tmp;
-    }
-
-  record_const_or_copy_1 (x, y, prev_x);
-}
-
 /* Return the loop depth of the basic block of the defining statement of X.
    This number should not be treated as absolutely correct because the loop
    information may not be completely up-to-date when dom runs.  However, it
@@ -1863,7 +1787,7 @@  record_equality (tree x, tree y)
 	  || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
     return;
 
-  record_const_or_copy_1 (x, y, prev_x);
+  const_and_copies->record_const_or_copy (x, y, prev_x);
 }
 
 /* Returns true when STMT is a simple iv increment.  It detects the
@@ -1940,7 +1864,7 @@  cprop_into_successor_phis (basic_block bb)
 
       /* Push the unwind marker so we can reset the const and copies
 	 table back to its original state after processing this edge.  */
-      const_and_copies_stack.safe_push (NULL_TREE);
+      const_and_copies->push_marker ();
 
       /* Extract and record any simple NAME = VALUE equivalences.
 
@@ -1953,7 +1877,7 @@  cprop_into_successor_phis (basic_block bb)
 	  tree rhs = edge_info->rhs;
 
 	  if (lhs && TREE_CODE (lhs) == SSA_NAME)
-	    record_const_or_copy (lhs, rhs);
+	    const_and_copies->record_const_or_copy (lhs, rhs);
 	}
 
       indx = e->dest_idx;
@@ -1982,7 +1906,7 @@  cprop_into_successor_phis (basic_block bb)
 	    propagate_value (orig_p, new_val);
 	}
 
-      restore_vars_to_original_value ();
+      const_and_copies->pop_to_marker ();
     }
 }
 
@@ -1998,7 +1922,7 @@  dom_opt_dom_walker::before_dom_children (basic_block bb)
      far to unwind when we finalize this block.  */
   avail_exprs_stack.safe_push
     (std::pair<expr_hash_elt_t, expr_hash_elt_t> (NULL, NULL));
-  const_and_copies_stack.safe_push (NULL_TREE);
+  const_and_copies->push_marker ();
 
   record_equivalences_from_incoming_edge (bb);
 
@@ -2064,7 +1988,7 @@  dom_opt_dom_walker::after_dom_children (basic_block bb)
 
   /* These remove expressions local to BB from the tables.  */
   remove_local_expressions_from_table ();
-  restore_vars_to_original_value ();
+  const_and_copies->pop_to_marker ();
 }
 
 /* Search for redundant computations in STMT.  If any are found, then
@@ -2128,7 +2052,7 @@  eliminate_redundant_computations (gimple_stmt_iterator* gsi)
        This should be sufficient to kill the redundant phi.  */
     {
       if (def && cached_lhs)
-	record_const_or_copy (def, cached_lhs);
+	const_and_copies->record_const_or_copy (def, cached_lhs);
       return;
     }
   else
diff --git a/gcc/tree-ssa-loop-ch.c b/gcc/tree-ssa-loop-ch.c
index c6441b8..82340c4 100644
--- a/gcc/tree-ssa-loop-ch.c
+++ b/gcc/tree-ssa-loop-ch.c
@@ -53,6 +53,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "cfgloop.h"
 #include "tree-inline.h"
 #include "flags.h"
+#include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
 
 /* Duplicates headers of loops if they are small enough, so that the statements
diff --git a/gcc/tree-ssa-scopedtables.c b/gcc/tree-ssa-scopedtables.c
new file mode 100644
index 0000000..c336a90
--- /dev/null
+++ b/gcc/tree-ssa-scopedtables.c
@@ -0,0 +1,152 @@ 
+/* Header file for SSA dominator optimizations.
+   Copyright (C) 2013-2015 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "hash-table.h"
+#include "tm.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "vec.h"
+#include "double-int.h"
+#include "input.h"
+#include "alias.h"
+#include "symtab.h"
+#include "wide-int.h"
+#include "inchash.h"
+#include "real.h"
+#include "tree.h"
+#include "tree-pretty-print.h"
+#include "tree-pass.h"
+#include "tree-ssa-scopedtables.h"
+#include "tree-ssa-threadedge.h"
+
+const_and_copies::const_and_copies (FILE *file, int flags)
+{
+  stack.create (20);
+  dump_file = file;
+  dump_flags = flags;
+}
+
+/* Pop entries off the stack until we hit the NULL marker.
+   For each entry popped, use the SRC/DEST pair to restore
+   SRC to its prior value.  */
+
+void
+const_and_copies::pop_to_marker (void)
+{
+  while (stack.length () > 0)
+    {
+      tree prev_value, dest;
+
+      dest = stack.pop ();
+
+      /* A NULL value indicates we should stop unwinding, otherwise
+	 pop off the next entry as they're recorded in pairs.  */
+      if (dest == NULL)
+	break;
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "<<<< COPY ");
+	  print_generic_expr (dump_file, dest, 0);
+	  fprintf (dump_file, " = ");
+	  print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0);
+	  fprintf (dump_file, "\n");
+	}
+
+      prev_value = stack.pop ();
+      set_ssa_name_value (dest, prev_value);
+    }
+}
+
+/* Record that X has the value Y.  */
+
+void
+const_and_copies::record_const_or_copy (tree x, tree y)
+{
+  record_const_or_copy (x, y, SSA_NAME_VALUE (x));
+}
+
+/* Record that X has the value Y and that X's previous value is PREV_X.  */
+
+void
+const_and_copies::record_const_or_copy (tree x, tree y, tree prev_x)
+{
+  /* Y may be NULL if we are invalidating entries in the table.  */
+  if (y && TREE_CODE (y) == SSA_NAME)
+    {
+      tree tmp = SSA_NAME_VALUE (y);
+      y = tmp ? tmp : y;
+    }
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "0>>> COPY ");
+      print_generic_expr (dump_file, x, 0);
+      fprintf (dump_file, " = ");
+      print_generic_expr (dump_file, y, 0);
+      fprintf (dump_file, "\n");
+    }
+
+  set_ssa_name_value (x, y);
+  stack.reserve (2);
+  stack.quick_push (prev_x);
+  stack.quick_push (x);
+}
+
+/* A new value has been assigned to LHS.  If necessary, invalidate any
+   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.   */
+void
+const_and_copies::invalidate (tree lhs)
+{
+
+  /* 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_const_or_copy ((stack)[i], NULL_TREE);
+
+      /* 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_const_or_copy (lhs, NULL_TREE);
+}
diff --git a/gcc/tree-ssa-scopedtables.h b/gcc/tree-ssa-scopedtables.h
new file mode 100644
index 0000000..bc30ee6
--- /dev/null
+++ b/gcc/tree-ssa-scopedtables.h
@@ -0,0 +1,40 @@ 
+/* Header file for SSA dominator optimizations.
+   Copyright (C) 2013-2015 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_TREE_SSA_SCOPED_TABLES_H
+#define GCC_TREE_SSA_SCOPED_TABLES_H
+
+class const_and_copies
+{
+ public:
+  const_and_copies (FILE *, int);
+  ~const_and_copies (void) { stack.release (); }
+  void push_marker (void) { stack.safe_push (NULL_TREE); }
+  void pop_to_marker (void);
+  void record_const_or_copy (tree, tree);
+  void record_const_or_copy (tree, tree, tree);
+  void invalidate (tree);
+
+ private:
+  vec<tree> stack;
+  FILE *dump_file;
+  int dump_flags;
+};
+
+#endif /* GCC_TREE_SSA_SCOPED_TABLES_H */
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 90c1e2a..acbbb67 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -60,6 +60,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-threadupdate.h"
 #include "langhooks.h"
 #include "params.h"
+#include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
 #include "tree-ssa-loop.h"
 #include "builtins.h"
@@ -163,57 +164,6 @@  lhs_of_dominating_assert (tree op, basic_block bb, gimple stmt)
   return op;
 }
 
-/* We record temporary equivalences created by PHI nodes or
-   statements within the target block.  Doing so allows us to
-   identify more jump threading opportunities, even in blocks
-   with side effects.
-
-   We keep track of those temporary equivalences in a stack
-   structure so that we can unwind them when we're done processing
-   a particular edge.  This routine handles unwinding the data
-   structures.  */
-
-static void
-remove_temporary_equivalences (vec<tree> *stack)
-{
-  while (stack->length () > 0)
-    {
-      tree prev_value, dest;
-
-      dest = stack->pop ();
-
-      /* A NULL value indicates we should stop unwinding, otherwise
-	 pop off the next entry as they're recorded in pairs.  */
-      if (dest == NULL)
-	break;
-
-      prev_value = stack->pop ();
-      set_ssa_name_value (dest, prev_value);
-    }
-}
-
-/* Record a temporary equivalence, saving enough information so that
-   we can restore the state of recorded equivalences when we're
-   done processing the current edge.  */
-
-static void
-record_temporary_equivalence (tree x, tree y, vec<tree> *stack)
-{
-  tree prev_x = SSA_NAME_VALUE (x);
-
-  /* Y may be NULL if we are invalidating entries in the table.  */
-  if (y && TREE_CODE (y) == SSA_NAME)
-    {
-      tree tmp = SSA_NAME_VALUE (y);
-      y = tmp ? tmp : y;
-    }
-
-  set_ssa_name_value (x, y);
-  stack->reserve (2);
-  stack->quick_push (prev_x);
-  stack->quick_push (x);
-}
-
 /* Record temporary equivalences created by PHIs at the target of the
    edge E.  Record unwind information for the equivalences onto STACK.
 
@@ -225,7 +175,7 @@  record_temporary_equivalence (tree x, tree y, vec<tree> *stack)
    traversing back edges less painful.  */
 
 static bool
-record_temporary_equivalences_from_phis (edge e, vec<tree> *stack)
+record_temporary_equivalences_from_phis (edge e, const_and_copies *const_and_copies)
 {
   gphi_iterator gsi;
 
@@ -252,7 +202,7 @@  record_temporary_equivalences_from_phis (edge e, vec<tree> *stack)
       if (!virtual_operand_p (dst))
 	stmt_count++;
 
-      record_temporary_equivalence (dst, src, stack);
+      const_and_copies->record_const_or_copy (dst, src);
     }
   return true;
 }
@@ -307,45 +257,6 @@  fold_assignment_stmt (gimple stmt)
     }
 }
 
-/* A new value has been assigned to LHS.  If necessary, invalidate any
-   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)
-{
-
-  /* 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);
-}
-
 /* Try to simplify each statement in E->dest, ultimately leading to
    a simplification of the COND_EXPR at the end of E->dest.
 
@@ -365,7 +276,7 @@  invalidate_equivalences (tree lhs, vec<tree> *stack)
 
 static gimple
 record_temporary_equivalences_from_stmts_at_dest (edge e,
-						  vec<tree> *stack,
+						  const_and_copies *const_and_copies,
 						  tree (*simplify) (gimple,
 								    gimple),
 						  bool backedge_seen)
@@ -425,7 +336,7 @@  record_temporary_equivalences_from_stmts_at_dest (edge e,
 
 	  if (backedge_seen)
 	    FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
-	      invalidate_equivalences (op, stack);
+	      const_and_copies->invalidate (op);
 
 	  continue;
 	}
@@ -465,7 +376,7 @@  record_temporary_equivalences_from_stmts_at_dest (edge e,
 	      if (backedge_seen)
 		{
 		  tree lhs = gimple_get_lhs (stmt);
-		  invalidate_equivalences (lhs, stack);
+		  const_and_copies->invalidate (lhs);
 		}
 	      continue;
 	    }
@@ -541,9 +452,9 @@  record_temporary_equivalences_from_stmts_at_dest (edge e,
       if (cached_lhs
 	  && (TREE_CODE (cached_lhs) == SSA_NAME
 	      || is_gimple_min_invariant (cached_lhs)))
-	record_temporary_equivalence (gimple_get_lhs (stmt), cached_lhs, stack);
+	const_and_copies->record_const_or_copy (gimple_get_lhs (stmt), cached_lhs);
       else if (backedge_seen)
-	invalidate_equivalences (gimple_get_lhs (stmt), stack);
+	const_and_copies->invalidate (gimple_get_lhs (stmt));
     }
   return stmt;
 }
@@ -1264,7 +1175,7 @@  static int
 thread_through_normal_block (edge e,
 			     gcond *dummy_cond,
 			     bool handle_dominating_asserts,
-			     vec<tree> *stack,
+			     const_and_copies *const_and_copies,
 			     tree (*simplify) (gimple, gimple),
 			     vec<jump_thread_edge *> *path,
 			     bitmap visited,
@@ -1281,13 +1192,13 @@  thread_through_normal_block (edge e,
      Note that if we found a PHI that made the block non-threadable, then
      we need to bubble that up to our caller in the same manner we do
      when we prematurely stop processing statements below.  */
-  if (!record_temporary_equivalences_from_phis (e, stack))
+  if (!record_temporary_equivalences_from_phis (e, const_and_copies))
     return -1;
 
   /* Now walk each statement recording any context sensitive
      temporary equivalences we can detect.  */
   gimple stmt
-    = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify,
+    = record_temporary_equivalences_from_stmts_at_dest (e, const_and_copies, simplify,
 							*backedge_seen_p);
 
   /* There's two reasons STMT might be null, and distinguishing
@@ -1434,7 +1345,7 @@  void
 thread_across_edge (gcond *dummy_cond,
 		    edge e,
 		    bool handle_dominating_asserts,
-		    vec<tree> *stack,
+		    const_and_copies *const_and_copies,
 		    tree (*simplify) (gimple, gimple))
 {
   bitmap visited = BITMAP_ALLOC (NULL);
@@ -1452,13 +1363,13 @@  thread_across_edge (gcond *dummy_cond,
 
   int threaded = thread_through_normal_block (e, dummy_cond,
 					      handle_dominating_asserts,
-					      stack, simplify, path,
+					      const_and_copies, simplify, path,
 					      visited, &backedge_seen);
   if (threaded > 0)
     {
       propagate_threaded_block_debug_into (path->last ()->e->dest,
 					   e->dest);
-      remove_temporary_equivalences (stack);
+      const_and_copies->pop_to_marker ();
       BITMAP_FREE (visited);
       register_jump_thread (path);
       return;
@@ -1482,7 +1393,7 @@  thread_across_edge (gcond *dummy_cond,
       if (threaded < 0)
 	{
 	  BITMAP_FREE (visited);
-	  remove_temporary_equivalences (stack);
+	  const_and_copies->pop_to_marker ();
 	  return;
 	}
     }
@@ -1508,7 +1419,7 @@  thread_across_edge (gcond *dummy_cond,
     FOR_EACH_EDGE (taken_edge, ei, e->dest->succs)
       if (taken_edge->flags & EDGE_ABNORMAL)
 	{
-	  remove_temporary_equivalences (stack);
+	  const_and_copies->pop_to_marker ();
 	  BITMAP_FREE (visited);
 	  return;
 	}
@@ -1518,7 +1429,7 @@  thread_across_edge (gcond *dummy_cond,
       {
 	/* Push a fresh marker so we can unwind the equivalences created
 	   for each of E->dest's successors.  */
-	stack->safe_push (NULL_TREE);
+	const_and_copies->push_marker ();
      
 	/* Avoid threading to any block we have already visited.  */
 	bitmap_clear (visited);
@@ -1553,7 +1464,7 @@  thread_across_edge (gcond *dummy_cond,
 	if (!found)
 	  found = thread_through_normal_block (path->last ()->e, dummy_cond,
 					       handle_dominating_asserts,
-					       stack, simplify, path, visited,
+					       const_and_copies, simplify, path, visited,
 					       &backedge_seen) > 0;
 
 	/* If we were able to thread through a successor of E->dest, then
@@ -1570,10 +1481,10 @@  thread_across_edge (gcond *dummy_cond,
 	  }
 
 	/* And unwind the equivalence table.  */
-	remove_temporary_equivalences (stack);
+	const_and_copies->pop_to_marker ();
       }
     BITMAP_FREE (visited);
   }
 
-  remove_temporary_equivalences (stack);
+  const_and_copies->pop_to_marker ();
 }
diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h
index 63eca79..521fd0e 100644
--- a/gcc/tree-ssa-threadedge.h
+++ b/gcc/tree-ssa-threadedge.h
@@ -31,6 +31,6 @@  extern void threadedge_finalize_values (void);
 extern bool potentially_threadable_block (basic_block);
 extern void propagate_threaded_block_debug_into (basic_block, basic_block);
 extern void thread_across_edge (gcond *, edge, bool,
-				vec<tree> *, tree (*) (gimple, gimple));
+				const_and_copies *, tree (*) (gimple, gimple));
 
 #endif /* GCC_TREE_SSA_THREADEDGE_H */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 41d7316..e7ab23c 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -88,6 +88,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "expr.h"
 #include "insn-codes.h"
 #include "optabs.h"
+#include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
 
 
@@ -10054,12 +10055,8 @@  vrp_fold_stmt (gimple_stmt_iterator *si)
   return simplify_stmt_using_ranges (si);
 }
 
-/* Stack of dest,src equivalency pairs that need to be restored after
-   each attempt to thread a block's incoming edge to an outgoing edge.
-
-   A NULL entry is used to mark the end of pairs which need to be
-   restored.  */
-static vec<tree> equiv_stack;
+/* Unwindable const/copy equivalences.  */
+const_and_copies *equiv_stack;
 
 /* A trivial wrapper so that we can present the generic jump threading
    code with a simple API for simplifying statements.  STMT is the
@@ -10140,7 +10137,7 @@  identify_jump_threads (void)
 
   /* Allocate our unwinder stack to unwind any temporary equivalences
      that might be recorded.  */
-  equiv_stack.create (20);
+  equiv_stack = new const_and_copies (dump_file, dump_flags);
 
   /* To avoid lots of silly node creation, we create a single
      conditional and just modify it in-place when attempting to
@@ -10198,7 +10195,7 @@  identify_jump_threads (void)
 	      if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
 		continue;
 
-	      thread_across_edge (dummy, e, true, &equiv_stack,
+	      thread_across_edge (dummy, e, true, equiv_stack,
 				  simplify_stmt_for_jump_threading);
 	    }
 	}
@@ -10219,7 +10216,7 @@  static void
 finalize_jump_threads (void)
 {
   thread_through_all_blocks (false);
-  equiv_stack.release ();
+  delete equiv_stack;
 }