diff mbox series

Overhaul jump thread state in forward threader.

Message ID 20210922184106.754820-1-aldyh@redhat.com
State New
Headers show
Series Overhaul jump thread state in forward threader. | expand

Commit Message

Aldy Hernandez Sept. 22, 2021, 6:41 p.m. UTC 
I've been pulling state from across the forward jump threader into the
jt_state class, but it it still didn't feel right.  The ultimate goal
was to keep track of candidate threading paths so that the simplifier
could simplify statements with the path as context.  This patch completes
the transition, while cleaning up a lot of things in the process.

I've revamped both state and the simplifier such that a base state class
contains only the blocks as they're registered, and any pass specific
knowledge is where it belongs... in the pass.  This allows VRP to keep
its const and copies business, and DOM to keep this as well as its evrp
client.  This makes the threader cleaner, as it will now have no knowledge
of either const/copies or evrp.

This also paves the wave for the upcoming hybrid threader, which will
just derive the state class and provide almost nothing, since the ranger
doesn't need to register any equivalences or ranges as it folds.

There is some code duplication in the simplifier, since both the DOM and
VRP clients use a vr_values based simplifier, but this is temporary as
the VRP client is about to be replaced with a hybrid ranger.

For a better view of what this patch achieves, here are the base
classes:

class jt_state
{
public:
  virtual ~jt_state () { }
  virtual void push (edge);
  virtual void pop ();
  virtual void register_equiv (tree dest, tree src, bool update_range =
false);
  virtual void register_equivs_edge (edge e);
  virtual void register_equivs_stmt (gimple *, basic_block,
				     class jt_simplifier *);
  virtual void record_ranges_from_stmt (gimple *stmt, bool temporary);
  void get_path (vec<basic_block> &);
  void append_path (basic_block);
  void dump (FILE *);
  void debug ();
private:
  auto_vec<basic_block> m_blocks;
};

class jt_simplifier
{
public:
  virtual ~jt_simplifier () { }
  virtual tree simplify (gimple *, gimple *, basic_block, jt_state *) =
0;
};

There are no functional changes.

OK pending tests?

p.s. It's sad that this is starting to look clean, just in time to get
wiped out.

gcc/ChangeLog:

	* tree-ssa-dom.c (class dom_jump_threader_simplifier): Rename...
	(class dom_jt_state): ...this and provide virtual overrides.
	(dom_jt_state::register_equiv): New.
	(class dom_jt_simplifier): Rename from
	dom_jump_threader_simplifier.
	(dom_jump_threader_simplifier::simplify): Rename...
	(dom_jt_simplifier::simplify): ...to this.
	(pass_dominator::execute): Use dom_jt_simplifier and
	dom_jt_state.
	* tree-ssa-threadedge.c (jump_threader::jump_threader):
	Clean-up.
	(jt_state::register_equivs_stmt): Abstract out...
	(jump_threader::record_temporary_equivalences_from_stmts_at_dest):
	...from here.
	(jump_threader::thread_around_empty_blocks): Update state.
	(jump_threader::thread_through_normal_block): Same.
	(jt_state::jt_state): Remove.
	(jt_state::push): Remove pass specific bits.  Keep block vector
	updated.
	(jt_state::append_path): New.
	(jt_state::pop): Remove pass specific bits.
	(jt_state::register_equiv): Same.
	(jt_state::record_ranges_from_stmt): Same.
	(jt_state::register_equivs_on_edge): Same.  Rename...
	(jt_state::register_equivs_edge):  ...to this.
	(jt_state::dump): New.
	(jt_state::debug): New.
	(jump_threader_simplifier::simplify): Remove.
	(jt_state::get_path): New.
	* tree-ssa-threadedge.h (class jt_simplifier): Make into a base
	class.  Expose common functionality as virtual methods.
	(class jump_threader_simplifier): Same.  Rename...
	(class jt_simplifier): ...to this.
	* tree-vrp.c (class vrp_jump_threader_simplifier): Rename...
	(class vrp_jt_simplifier): ...to this. Provide pass specific
	overrides.
	(class vrp_jt_state): New.
	(vrp_jump_threader_simplifier::simplify): Rename...
	(vrp_jt_simplifier::simplify): ...to this.  Inline code from
	what used to be the base class.
	(vrp_jump_threader::vrp_jump_threader): Use vrp_jt_state and
	vrp_jt_simplifier.
---
 gcc/tree-ssa-dom.c        | 134 ++++++++++++++--
 gcc/tree-ssa-threadedge.c | 322 ++++++++++++++++----------------------
 gcc/tree-ssa-threadedge.h |  51 +++---
 gcc/tree-vrp.c            |  81 ++++++++--
 4 files changed, 351 insertions(+), 237 deletions(-)

Comments

Jeff Law Sept. 22, 2021, 10:29 p.m. UTC | #1 
On 9/22/2021 12:41 PM, Aldy Hernandez wrote:
> I've been pulling state from across the forward jump threader into the
> jt_state class, but it it still didn't feel right.  The ultimate goal
> was to keep track of candidate threading paths so that the simplifier
> could simplify statements with the path as context.  This patch completes
> the transition, while cleaning up a lot of things in the process.
>
> I've revamped both state and the simplifier such that a base state class
> contains only the blocks as they're registered, and any pass specific
> knowledge is where it belongs... in the pass.  This allows VRP to keep
> its const and copies business, and DOM to keep this as well as its evrp
> client.  This makes the threader cleaner, as it will now have no knowledge
> of either const/copies or evrp.
>
> This also paves the wave for the upcoming hybrid threader, which will
> just derive the state class and provide almost nothing, since the ranger
> doesn't need to register any equivalences or ranges as it folds.
>
> There is some code duplication in the simplifier, since both the DOM and
> VRP clients use a vr_values based simplifier, but this is temporary as
> the VRP client is about to be replaced with a hybrid ranger.
>
> For a better view of what this patch achieves, here are the base
> classes:
>
> class jt_state
> {
> public:
>    virtual ~jt_state () { }
>    virtual void push (edge);
>    virtual void pop ();
>    virtual void register_equiv (tree dest, tree src, bool update_range =
> false);
>    virtual void register_equivs_edge (edge e);
>    virtual void register_equivs_stmt (gimple *, basic_block,
> 				     class jt_simplifier *);
>    virtual void record_ranges_from_stmt (gimple *stmt, bool temporary);
>    void get_path (vec<basic_block> &);
>    void append_path (basic_block);
>    void dump (FILE *);
>    void debug ();
> private:
>    auto_vec<basic_block> m_blocks;
> };
>
> class jt_simplifier
> {
> public:
>    virtual ~jt_simplifier () { }
>    virtual tree simplify (gimple *, gimple *, basic_block, jt_state *) =
> 0;
> };
>
> There are no functional changes.
>
> OK pending tests?
>
> p.s. It's sad that this is starting to look clean, just in time to get
> wiped out.
Sometimes you have to get it to this state so that it can get zapped.

>
> gcc/ChangeLog:
>
> 	* tree-ssa-dom.c (class dom_jump_threader_simplifier): Rename...
> 	(class dom_jt_state): ...this and provide virtual overrides.
> 	(dom_jt_state::register_equiv): New.
> 	(class dom_jt_simplifier): Rename from
> 	dom_jump_threader_simplifier.
> 	(dom_jump_threader_simplifier::simplify): Rename...
> 	(dom_jt_simplifier::simplify): ...to this.
> 	(pass_dominator::execute): Use dom_jt_simplifier and
> 	dom_jt_state.
> 	* tree-ssa-threadedge.c (jump_threader::jump_threader):
> 	Clean-up.
> 	(jt_state::register_equivs_stmt): Abstract out...
> 	(jump_threader::record_temporary_equivalences_from_stmts_at_dest):
> 	...from here.
> 	(jump_threader::thread_around_empty_blocks): Update state.
> 	(jump_threader::thread_through_normal_block): Same.
> 	(jt_state::jt_state): Remove.
> 	(jt_state::push): Remove pass specific bits.  Keep block vector
> 	updated.
> 	(jt_state::append_path): New.
> 	(jt_state::pop): Remove pass specific bits.
> 	(jt_state::register_equiv): Same.
> 	(jt_state::record_ranges_from_stmt): Same.
> 	(jt_state::register_equivs_on_edge): Same.  Rename...
> 	(jt_state::register_equivs_edge):  ...to this.
> 	(jt_state::dump): New.
> 	(jt_state::debug): New.
> 	(jump_threader_simplifier::simplify): Remove.
> 	(jt_state::get_path): New.
> 	* tree-ssa-threadedge.h (class jt_simplifier): Make into a base
> 	class.  Expose common functionality as virtual methods.
> 	(class jump_threader_simplifier): Same.  Rename...
> 	(class jt_simplifier): ...to this.
> 	* tree-vrp.c (class vrp_jump_threader_simplifier): Rename...
> 	(class vrp_jt_simplifier): ...to this. Provide pass specific
> 	overrides.
> 	(class vrp_jt_state): New.
> 	(vrp_jump_threader_simplifier::simplify): Rename...
> 	(vrp_jt_simplifier::simplify): ...to this.  Inline code from
> 	what used to be the base class.
> 	(vrp_jump_threader::vrp_jump_threader): Use vrp_jt_state and
> 	vrp_jt_simplifier.
OK
jeff
diff mbox series

Patch

diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 49d8f96408f..f58b6b78a41 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -585,31 +585,137 @@  record_edge_info (basic_block bb)
     }
 }
 
-class dom_jump_threader_simplifier : public jump_threader_simplifier
+class dom_jt_state : public jt_state
 {
 public:
-  dom_jump_threader_simplifier (vr_values *v,
-				avail_exprs_stack *avails)
-    : jump_threader_simplifier (v), m_avail_exprs_stack (avails) { }
+  dom_jt_state (const_and_copies *copies, avail_exprs_stack *avails,
+		evrp_range_analyzer *evrp)
+    : m_copies (copies), m_avails (avails), m_evrp (evrp)
+  {
+  }
+  void push (edge e) override
+  {
+    m_copies->push_marker ();
+    m_avails->push_marker ();
+    m_evrp->push_marker ();
+    jt_state::push (e);
+  }
+  void pop () override
+  {
+    m_copies->pop_to_marker ();
+    m_avails->pop_to_marker ();
+    m_evrp->pop_to_marker ();
+    jt_state::pop ();
+  }
+  void register_equivs_edge (edge e) override
+  {
+    record_temporary_equivalences (e, m_copies, m_avails);
+  }
+  void record_ranges_from_stmt (gimple *stmt, bool temporary) override
+  {
+    m_evrp->record_ranges_from_stmt (stmt, temporary);
+  }
+  void register_equiv (tree dest, tree src, bool update) override;
+private:
+  const_and_copies *m_copies;
+  avail_exprs_stack *m_avails;
+  evrp_range_analyzer *m_evrp;
+};
+
+void
+dom_jt_state::register_equiv (tree dest, tree src, bool update)
+{
+  m_copies->record_const_or_copy (dest, src);
+
+  /* If requested, update the value range associated with DST, using
+     the range from SRC.  */
+  if (update)
+    {
+      /* Get new VR we can pass to push_value_range.  */
+      value_range_equiv *new_vr = m_evrp->allocate_value_range_equiv ();
+      new (new_vr) value_range_equiv ();
+
+      /* There are three cases to consider:
+
+	 First if SRC is an SSA_NAME, then we can copy the value range
+	 from SRC into NEW_VR.
+
+	 Second if SRC is an INTEGER_CST, then we can just set NEW_VR
+	 to a singleton range.  Note that even if SRC is a constant we
+	 need to set a suitable output range so that VR_UNDEFINED
+	 ranges do not leak through.
+
+	 Otherwise set NEW_VR to varying.  This may be overly
+	 conservative.  */
+      if (TREE_CODE (src) == SSA_NAME)
+	new_vr->deep_copy (m_evrp->get_value_range (src));
+      else if (TREE_CODE (src) == INTEGER_CST)
+	new_vr->set (src);
+      else
+	new_vr->set_varying (TREE_TYPE (src));
+
+      /* This is a temporary range for DST, so push it.  */
+      m_evrp->push_value_range (dest, new_vr);
+    }
+}
+
+class dom_jt_simplifier : public jt_simplifier
+{
+public:
+  dom_jt_simplifier (vr_values *v, avail_exprs_stack *avails)
+    : m_vr_values (v), m_avails (avails) { }
 
 private:
   tree simplify (gimple *, gimple *, basic_block, jt_state *) override;
-  avail_exprs_stack *m_avail_exprs_stack;
+  vr_values *m_vr_values;
+  avail_exprs_stack *m_avails;
 };
 
 tree
-dom_jump_threader_simplifier::simplify (gimple *stmt,
-					gimple *within_stmt,
-					basic_block bb,
-					jt_state *state)
+dom_jt_simplifier::simplify (gimple *stmt, gimple *within_stmt,
+			     basic_block, jt_state *)
 {
   /* First see if the conditional is in the hash table.  */
-  tree cached_lhs =  m_avail_exprs_stack->lookup_avail_expr (stmt,
-							     false, true);
+  tree cached_lhs =  m_avails->lookup_avail_expr (stmt, false, true);
   if (cached_lhs)
     return cached_lhs;
 
-  return jump_threader_simplifier::simplify (stmt, within_stmt, bb, state);
+  if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
+    {
+      simplify_using_ranges simplifier (m_vr_values);
+      return simplifier.vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
+						  gimple_cond_lhs (cond_stmt),
+						  gimple_cond_rhs (cond_stmt),
+						  within_stmt);
+    }
+  if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
+    {
+      tree op = gimple_switch_index (switch_stmt);
+      if (TREE_CODE (op) != SSA_NAME)
+	return NULL_TREE;
+
+      const value_range_equiv *vr = m_vr_values->get_value_range (op);
+      return find_case_label_range (switch_stmt, vr);
+    }
+  if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
+    {
+      tree lhs = gimple_assign_lhs (assign_stmt);
+      if (TREE_CODE (lhs) == SSA_NAME
+	  && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+	      || POINTER_TYPE_P (TREE_TYPE (lhs)))
+	  && stmt_interesting_for_vrp (stmt))
+	{
+	  edge dummy_e;
+	  tree dummy_tree;
+	  value_range_equiv new_vr;
+	  m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree,
+						&new_vr);
+	  tree singleton;
+	  if (new_vr.singleton_p (&singleton))
+	    return singleton;
+	}
+    }
+  return NULL;
 }
 
 class dom_opt_dom_walker : public dom_walker
@@ -752,8 +858,8 @@  pass_dominator::execute (function *fun)
 
   /* Recursively walk the dominator tree optimizing statements.  */
   evrp_range_analyzer analyzer (true);
-  dom_jump_threader_simplifier simplifier (&analyzer, avail_exprs_stack);
-  jt_state state (const_and_copies, avail_exprs_stack, &analyzer);
+  dom_jt_simplifier simplifier (&analyzer, avail_exprs_stack);
+  dom_jt_state state (const_and_copies, avail_exprs_stack, &analyzer);
   jump_threader threader (&simplifier, &state);
   dom_opt_dom_walker walker (CDI_DOMINATORS,
 			     &threader,
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index 04138cb06fe..ae77e5eb396 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -33,12 +33,12 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-ssa-threadupdate.h"
 #include "tree-ssa-scopedtables.h"
 #include "tree-ssa-threadedge.h"
-#include "tree-ssa-dom.h"
 #include "gimple-fold.h"
 #include "cfganal.h"
 #include "alloc-pool.h"
 #include "vr-values.h"
 #include "gimple-ssa-evrp-analyze.h"
+#include "gimple-range.h"
 
 /* To avoid code explosion due to jump threading, we limit the
    number of statements we are going to copy.  This variable
@@ -61,8 +61,7 @@  set_ssa_name_value (tree name, tree value)
   ssa_name_values[SSA_NAME_VERSION (name)] = value;
 }
 
-jump_threader::jump_threader (jump_threader_simplifier *simplifier,
-			      jt_state *state)
+jump_threader::jump_threader (jt_simplifier *simplifier, jt_state *state)
 {
   /* Initialize the per SSA_NAME value-handles array.  */
   gcc_assert (!ssa_name_values.exists ());
@@ -228,8 +227,6 @@  jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
      when we're finished processing E.  */
   for (gsi = gsi_start_bb (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
     {
-      tree cached_lhs = NULL;
-
       stmt = gsi_stmt (gsi);
 
       /* Ignore empty statements and labels.  */
@@ -326,75 +323,7 @@  jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
 	    continue;
 	}
 
-      /* At this point we have a statement which assigns an RHS to an
-	 SSA_VAR on the LHS.  We want to try and simplify this statement
-	 to expose more context sensitive equivalences which in turn may
-	 allow us to simplify the condition at the end of the loop.
-
-	 Handle simple copy operations as well as implied copies from
-	 ASSERT_EXPRs.  */
-      if (gimple_assign_single_p (stmt)
-          && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
-	cached_lhs = gimple_assign_rhs1 (stmt);
-      else if (gimple_assign_single_p (stmt)
-               && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
-	cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
-      else
-	{
-	  /* A statement that is not a trivial copy or ASSERT_EXPR.
-	     Try to fold the new expression.  Inserting the
-	     expression into the hash table is unlikely to help.  */
-	  /* ???  The DOM callback below can be changed to setting
-	     the mprts_hook around the call to thread_across_edge,
-	     avoiding the use substitution.  The VRP hook should be
-	     changed to properly valueize operands itself using
-	     SSA_NAME_VALUE in addition to its own lattice.  */
-	  cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
-						       threadedge_valueize);
-          if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
-	      && (!cached_lhs
-                  || (TREE_CODE (cached_lhs) != SSA_NAME
-                      && !is_gimple_min_invariant (cached_lhs))))
-	    {
-	      /* We're going to temporarily copy propagate the operands
-		 and see if that allows us to simplify this statement.  */
-	      tree *copy;
-	      ssa_op_iter iter;
-	      use_operand_p use_p;
-	      unsigned int num, i = 0;
-
-	      num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
-	      copy = XALLOCAVEC (tree, num);
-
-	      /* Make a copy of the uses & vuses into USES_COPY, then cprop into
-		 the operands.  */
-	      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
-		{
-		  tree tmp = NULL;
-		  tree use = USE_FROM_PTR (use_p);
-
-		  copy[i++] = use;
-		  if (TREE_CODE (use) == SSA_NAME)
-		    tmp = SSA_NAME_VALUE (use);
-		  if (tmp)
-		    SET_USE (use_p, tmp);
-		}
-
-	      cached_lhs = m_simplifier->simplify (stmt, stmt, e->src, m_state);
-
-	      /* Restore the statement's original uses/defs.  */
-	      i = 0;
-	      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
-		SET_USE (use_p, copy[i++]);
-	    }
-	}
-
-      /* Record the context sensitive equivalence if we were able
-	 to simplify this statement.  */
-      if (cached_lhs
-	  && (TREE_CODE (cached_lhs) == SSA_NAME
-	      || is_gimple_min_invariant (cached_lhs)))
-	m_state->register_equiv (gimple_get_lhs (stmt), cached_lhs);
+      m_state->register_equivs_stmt (stmt, e->src, m_simplifier);
     }
   return stmt;
 }
@@ -899,6 +828,7 @@  jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
 	  if (!bitmap_bit_p (visited, taken_edge->dest->index))
 	    {
 	      m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+	      m_state->append_path (taken_edge->dest);
 	      bitmap_set_bit (visited, taken_edge->dest->index);
 	      return thread_around_empty_blocks (path, taken_edge, visited);
 	    }
@@ -940,6 +870,7 @@  jump_threader::thread_around_empty_blocks (vec<jump_thread_edge *> *path,
       bitmap_set_bit (visited, taken_edge->dest->index);
 
       m_registry->push_edge (path, taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+      m_state->append_path (taken_edge->dest);
 
       thread_around_empty_blocks (path, taken_edge, visited);
       return true;
@@ -970,7 +901,7 @@  int
 jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
 					    edge e, bitmap visited)
 {
-  m_state->register_equivs_on_edge (e);
+  m_state->register_equivs_edge (e);
 
   /* PHIs create temporary equivalences.
      Note that if we found a PHI that made the block non-threadable, then
@@ -1048,6 +979,7 @@  jump_threader::thread_through_normal_block (vec<jump_thread_edge *> *path,
 	    m_registry->push_edge (path, e, EDGE_START_JUMP_THREAD);
 
 	  m_registry->push_edge (path, taken_edge, EDGE_COPY_SRC_BLOCK);
+	  m_state->append_path (taken_edge->dest);
 
 	  /* See if we can thread through DEST as well, this helps capture
 	     secondary effects of threading without having to re-run DOM or
@@ -1290,26 +1222,18 @@  jump_threader::thread_outgoing_edges (basic_block bb)
     }
 }
 
-jt_state::jt_state (const_and_copies *copies,
-		    avail_exprs_stack *exprs,
-		    evrp_range_analyzer *evrp)
-{
-  m_copies = copies;
-  m_exprs = exprs;
-  m_evrp = evrp;
-}
+// Marker to keep track of the start of the current path.
+const basic_block jt_state::BB_MARKER = (basic_block) -1;
 
 // Record that E is being crossed.
 
 void
-jt_state::push (edge)
+jt_state::push (edge e)
 {
-  if (m_copies)
-    m_copies->push_marker ();
-  if (m_exprs)
-    m_exprs->push_marker ();
-  if (m_evrp)
-    m_evrp->push_marker ();
+  m_blocks.safe_push (BB_MARKER);
+  if (m_blocks.length () == 1)
+    m_blocks.safe_push (e->src);
+  m_blocks.safe_push (e->dest);
 }
 
 // Pop to the last pushed state.
@@ -1317,127 +1241,159 @@  jt_state::push (edge)
 void
 jt_state::pop ()
 {
-  if (m_copies)
-    m_copies->pop_to_marker ();
-  if (m_exprs)
-    m_exprs->pop_to_marker ();
-  if (m_evrp)
-    m_evrp->pop_to_marker ();
+  if (!m_blocks.is_empty ())
+    {
+      while (m_blocks.last () != BB_MARKER)
+	m_blocks.pop ();
+      // Pop marker.
+      m_blocks.pop ();
+    }
 }
 
-// Record an equivalence from DST to SRC.  If UPDATE_RANGE is TRUE,
-// update the value range associated with DST.
+// Add BB to the list of blocks seen.
 
 void
-jt_state::register_equiv (tree dst, tree src, bool update_range)
+jt_state::append_path (basic_block bb)
 {
-  if (m_copies)
-    m_copies->record_const_or_copy (dst, src);
+  gcc_checking_assert (!m_blocks.is_empty ());
+  m_blocks.safe_push (bb);
+}
 
-  /* If requested, update the value range associated with DST, using
-     the range from SRC.  */
-  if (m_evrp && update_range)
+void
+jt_state::dump (FILE *out)
+{
+  if (!m_blocks.is_empty ())
     {
-      /* Get new VR we can pass to push_value_range.  */
-      value_range_equiv *new_vr = m_evrp->allocate_value_range_equiv ();
-      new (new_vr) value_range_equiv ();
-
-      /* There are three cases to consider:
-
-	 First if SRC is an SSA_NAME, then we can copy the value range
-	 from SRC into NEW_VR.
-
-	 Second if SRC is an INTEGER_CST, then we can just set NEW_VR
-	 to a singleton range.  Note that even if SRC is a constant we
-	 need to set a suitable output range so that VR_UNDEFINED
-	 ranges do not leak through.
-
-	 Otherwise set NEW_VR to varying.  This may be overly
-	 conservative.  */
-      if (TREE_CODE (src) == SSA_NAME)
-	new_vr->deep_copy (m_evrp->get_value_range (src));
-      else if (TREE_CODE (src) == INTEGER_CST)
-	new_vr->set (src);
-      else
-	new_vr->set_varying (TREE_TYPE (src));
-
-      /* This is a temporary range for DST, so push it.  */
-      m_evrp->push_value_range (dst, new_vr);
+      auto_vec<basic_block> path;
+      get_path (path);
+      dump_ranger (out, path);
     }
 }
 
-// Record any ranges calculated in STMT.  If TEMPORARY is TRUE, then
-// this is a temporary equivalence and should be recorded into the
-// unwind table, instead of the global table.
+void
+jt_state::debug ()
+{
+  push_dump_file save (stderr, TDF_DETAILS);
+  dump (stderr);
+}
+
+// Convert the current path in jt_state into a path suitable for the
+// path solver.  Return the resulting path in PATH.
 
 void
-jt_state::record_ranges_from_stmt (gimple *stmt, bool temporary)
+jt_state::get_path (vec<basic_block> &path)
 {
-  if (m_evrp)
-    m_evrp->record_ranges_from_stmt (stmt, temporary);
+  path.truncate (0);
+
+  for (int i = (int) m_blocks.length () - 1; i >= 0; --i)
+    {
+      basic_block bb = m_blocks[i];
+
+      if (bb != BB_MARKER)
+	path.safe_push (bb);
+    }
 }
 
-// Record any equivalences created by traversing E.
+// Record an equivalence from DST to SRC.  If UPDATE_RANGE is TRUE,
+// update the value range associated with DST.
 
 void
-jt_state::register_equivs_on_edge (edge e)
+jt_state::register_equiv (tree dest ATTRIBUTE_UNUSED,
+			  tree src ATTRIBUTE_UNUSED,
+			  bool update_range ATTRIBUTE_UNUSED)
 {
-  if (m_copies && m_exprs)
-    record_temporary_equivalences (e, m_copies, m_exprs);
 }
 
-jump_threader_simplifier::jump_threader_simplifier (vr_values *v)
+// Record any ranges calculated in STMT.  If TEMPORARY is TRUE, then
+// this is a temporary equivalence and should be recorded into the
+// unwind table, instead of the global table.
+
+void
+jt_state::record_ranges_from_stmt (gimple *,
+				   bool temporary ATTRIBUTE_UNUSED)
 {
-  m_vr_values = v;
 }
 
-// Return the singleton that resolves STMT, if it is possible to
-// simplify it.
-//
-// STMT may be a dummy statement, not necessarily in the CFG, in which
-// case WITHIN_STMT can be used to determine the position in the CFG
-// where STMT should be evaluated as being in.
+// Record any equivalences created by traversing E.
 
-tree
-jump_threader_simplifier::simplify (gimple *stmt,
-				    gimple *within_stmt,
-				    basic_block,
-				    jt_state *)
+void
+jt_state::register_equivs_edge (edge)
 {
-  if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
-    {
-      simplify_using_ranges simplifier (m_vr_values);
-      return simplifier.vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
-						  gimple_cond_lhs (cond_stmt),
-						  gimple_cond_rhs (cond_stmt),
-						  within_stmt);
-    }
-  if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
-    {
-      tree op = gimple_switch_index (switch_stmt);
-      if (TREE_CODE (op) != SSA_NAME)
-	return NULL_TREE;
+}
 
-      const value_range_equiv *vr = m_vr_values->get_value_range (op);
-      return find_case_label_range (switch_stmt, vr);
-    }
-   if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
+void
+jt_state::register_equivs_stmt (gimple *stmt, basic_block bb,
+				jt_simplifier *simplifier)
+{
+  /* At this point we have a statement which assigns an RHS to an
+     SSA_VAR on the LHS.  We want to try and simplify this statement
+     to expose more context sensitive equivalences which in turn may
+     allow us to simplify the condition at the end of the loop.
+
+     Handle simple copy operations as well as implied copies from
+     ASSERT_EXPRs.  */
+  tree cached_lhs = NULL;
+  if (gimple_assign_single_p (stmt)
+      && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
+    cached_lhs = gimple_assign_rhs1 (stmt);
+  else if (gimple_assign_single_p (stmt)
+	   && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
+    cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
+  else
     {
-      tree lhs = gimple_assign_lhs (assign_stmt);
-      if (TREE_CODE (lhs) == SSA_NAME
-	  && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
-	      || POINTER_TYPE_P (TREE_TYPE (lhs)))
-	  && stmt_interesting_for_vrp (stmt))
+      /* A statement that is not a trivial copy or ASSERT_EXPR.
+	 Try to fold the new expression.  Inserting the
+	 expression into the hash table is unlikely to help.  */
+      /* ???  The DOM callback below can be changed to setting
+	 the mprts_hook around the call to thread_across_edge,
+	 avoiding the use substitution.  The VRP hook should be
+	 changed to properly valueize operands itself using
+	 SSA_NAME_VALUE in addition to its own lattice.  */
+      cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
+						   threadedge_valueize);
+      if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
+	  && (!cached_lhs
+	      || (TREE_CODE (cached_lhs) != SSA_NAME
+		  && !is_gimple_min_invariant (cached_lhs))))
 	{
-	  edge dummy_e;
-	  tree dummy_tree;
-	  value_range_equiv new_vr;
-	  m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree,
-						&new_vr);
-	  tree singleton;
-	  if (new_vr.singleton_p (&singleton))
-	    return singleton;
+	  /* We're going to temporarily copy propagate the operands
+	     and see if that allows us to simplify this statement.  */
+	  tree *copy;
+	  ssa_op_iter iter;
+	  use_operand_p use_p;
+	  unsigned int num, i = 0;
+
+	  num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
+	  copy = XALLOCAVEC (tree, num);
+
+	  /* Make a copy of the uses & vuses into USES_COPY, then cprop into
+	     the operands.  */
+	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+	    {
+	      tree tmp = NULL;
+	      tree use = USE_FROM_PTR (use_p);
+
+	      copy[i++] = use;
+	      if (TREE_CODE (use) == SSA_NAME)
+		tmp = SSA_NAME_VALUE (use);
+	      if (tmp)
+		SET_USE (use_p, tmp);
+	    }
+
+	  cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
+
+	  /* Restore the statement's original uses/defs.  */
+	  i = 0;
+	  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+	    SET_USE (use_p, copy[i++]);
 	}
     }
-   return NULL;
+
+  /* Record the context sensitive equivalence if we were able
+     to simplify this statement.  */
+  if (cached_lhs
+      && (TREE_CODE (cached_lhs) == SSA_NAME
+	  || is_gimple_min_invariant (cached_lhs)))
+    register_equiv (gimple_get_lhs (stmt), cached_lhs,
+		    /*update_range=*/false);
 }
diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h
index 18e6bd41aaa..0b47a521053 100644
--- a/gcc/tree-ssa-threadedge.h
+++ b/gcc/tree-ssa-threadedge.h
@@ -26,19 +26,31 @@  along with GCC; see the file COPYING3.  If not see
 class jt_state
 {
 public:
-  jt_state (class const_and_copies *,
-	    class avail_exprs_stack *,
-	    class evrp_range_analyzer *);
-  void push (edge);
-  void pop ();
-  void register_equiv (tree dest, tree src, bool update_range = false);
-  void register_equivs_on_edge (edge e);
-  void record_ranges_from_stmt (gimple *stmt, bool temporary);
+  virtual ~jt_state () { }
+  virtual void push (edge);
+  virtual void pop ();
+  virtual void register_equiv (tree dest, tree src, bool update_range);
+  virtual void register_equivs_edge (edge e);
+  virtual void register_equivs_stmt (gimple *, basic_block,
+				     class jt_simplifier *);
+  virtual void record_ranges_from_stmt (gimple *stmt, bool temporary);
+  void get_path (vec<basic_block> &);
+  void append_path (basic_block);
+  void dump (FILE *);
+  void debug ();
 
 private:
-  const_and_copies *m_copies;
-  avail_exprs_stack *m_exprs;
-  evrp_range_analyzer *m_evrp;
+  auto_vec<basic_block> m_blocks;
+  static const basic_block BB_MARKER;
+};
+
+// Statement simplifier callback for the jump threader.
+
+class jt_simplifier
+{
+public:
+  virtual ~jt_simplifier () { }
+  virtual tree simplify (gimple *, gimple *, basic_block, jt_state *) = 0;
 };
 
 // This is the high level threader.  The entry point is
@@ -49,7 +61,7 @@  private:
 class jump_threader
 {
 public:
-  jump_threader (class jump_threader_simplifier *, class jt_state *);
+  jump_threader (jt_simplifier *, class jt_state *);
   ~jump_threader ();
   void thread_outgoing_edges (basic_block);
   void remove_jump_threads_including (edge_def *);
@@ -76,23 +88,10 @@  private:
   gcond *dummy_cond;
 
   class fwd_jt_path_registry *m_registry;
-  jump_threader_simplifier *m_simplifier;
+  jt_simplifier *m_simplifier;
   jt_state *m_state;
 };
 
-// Statement simplifier callback for the jump threader.
-
-class jump_threader_simplifier
-{
-public:
-  jump_threader_simplifier (class vr_values *v);
-  virtual ~jump_threader_simplifier () { }
-  virtual tree simplify (gimple *, gimple *, basic_block, jt_state *);
-
-protected:
-  vr_values *m_vr_values;
-};
-
 extern void propagate_threaded_block_debug_into (basic_block, basic_block);
 extern bool single_succ_to_potentially_threadable_block (basic_block);
 
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 26e71e70c2a..a5079ee48aa 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -66,6 +66,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "range-op.h"
 #include "value-range-equiv.h"
 #include "gimple-array-bounds.h"
+#include "tree-ssa-dom.h"
 
 /* Set of SSA names found live during the RPO traversal of the function
    for still active basic-blocks.  */
@@ -4160,28 +4161,63 @@  vrp_folder::fold_stmt (gimple_stmt_iterator *si)
   return simplifier.simplify (si);
 }
 
-class vrp_jump_threader_simplifier : public jump_threader_simplifier
+class vrp_jt_state : public jt_state
 {
 public:
-  vrp_jump_threader_simplifier (vr_values *v, avail_exprs_stack *avails)
-    : jump_threader_simplifier (v), m_avail_exprs_stack (avails) { }
+  vrp_jt_state (const_and_copies *copies, avail_exprs_stack *avails)
+    : m_copies (copies), m_avails (avails)
+  {
+  }
+  void push (edge e) override
+  {
+    m_copies->push_marker ();
+    m_avails->push_marker ();
+    jt_state::push (e);
+  }
+  void pop () override
+  {
+    m_copies->pop_to_marker ();
+    m_avails->pop_to_marker ();
+    jt_state::pop ();
+  }
+  void register_equiv (tree dest, tree src, bool) override
+  {
+    m_copies->record_const_or_copy (dest, src);
+  }
+  void register_equivs_edge (edge e) override
+  {
+    record_temporary_equivalences (e, m_copies, m_avails);
+  }
+  void record_ranges_from_stmt (gimple *, bool) override
+  {
+  }
+private:
+  const_and_copies *m_copies;
+  avail_exprs_stack *m_avails;
+};
+
+class vrp_jt_simplifier : public jt_simplifier
+{
+public:
+  vrp_jt_simplifier (vr_values *v, avail_exprs_stack *avails)
+    : m_vr_values (v), m_avail_exprs_stack (avails) { }
 
 private:
-  tree simplify (gimple *, gimple *, basic_block, jt_state *) OVERRIDE;
+  tree simplify (gimple *, gimple *, basic_block, jt_state *) override;
+  vr_values *m_vr_values;
   avail_exprs_stack *m_avail_exprs_stack;
 };
 
 tree
-vrp_jump_threader_simplifier::simplify (gimple *stmt,
-					gimple *within_stmt,
-					basic_block bb,
-					jt_state *state)
+vrp_jt_simplifier::simplify (gimple *stmt, gimple *within_stmt,
+			     basic_block bb, jt_state *)
 {
   /* First see if the conditional is in the hash table.  */
   tree cached_lhs = m_avail_exprs_stack->lookup_avail_expr (stmt, false, true);
   if (cached_lhs && is_gimple_min_invariant (cached_lhs))
     return cached_lhs;
 
+  /* Next see if we can solve it with VRP's internal structures.  */
   if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
     {
       tree op0 = gimple_cond_lhs (cond_stmt);
@@ -4194,7 +4230,6 @@  vrp_jump_threader_simplifier::simplify (gimple *stmt,
       return simplifier.vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
 						  op0, op1, within_stmt);
     }
-
   if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
     {
       tree op = gimple_switch_index (switch_stmt);
@@ -4207,7 +4242,26 @@  vrp_jump_threader_simplifier::simplify (gimple *stmt,
       return find_case_label_range (switch_stmt, vr);
     }
 
-  return jump_threader_simplifier::simplify (stmt, within_stmt, bb, state);
+  /* Finally, try vr_values.  */
+  if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
+    {
+      tree lhs = gimple_assign_lhs (assign_stmt);
+      if (TREE_CODE (lhs) == SSA_NAME
+	  && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+	      || POINTER_TYPE_P (TREE_TYPE (lhs)))
+	  && stmt_interesting_for_vrp (stmt))
+	{
+	  edge dummy_e;
+	  tree dummy_tree;
+	  value_range_equiv new_vr;
+	  m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree,
+						&new_vr);
+	  tree singleton;
+	  if (new_vr.singleton_p (&singleton))
+	    return singleton;
+	}
+    }
+  return NULL;
 }
 
 /* Blocks which have more than one predecessor and more than
@@ -4256,7 +4310,7 @@  private:
   const_and_copies *m_const_and_copies;
   avail_exprs_stack *m_avail_exprs_stack;
   hash_table<expr_elt_hasher> *m_avail_exprs;
-  vrp_jump_threader_simplifier *m_simplifier;
+  vrp_jt_simplifier *m_simplifier;
   jump_threader *m_threader;
   jt_state *m_state;
 };
@@ -4284,10 +4338,9 @@  vrp_jump_threader::vrp_jump_threader (struct function *fun, vr_values *v)
   m_vr_values = v;
   m_avail_exprs = new hash_table<expr_elt_hasher> (1024);
   m_avail_exprs_stack = new avail_exprs_stack (m_avail_exprs);
-  m_state = new jt_state (m_const_and_copies, m_avail_exprs_stack, NULL);
+  m_state = new vrp_jt_state (m_const_and_copies, m_avail_exprs_stack);
 
-  m_simplifier = new vrp_jump_threader_simplifier (m_vr_values,
-						   m_avail_exprs_stack);
+  m_simplifier = new vrp_jt_simplifier (m_vr_values, m_avail_exprs_stack);
   m_threader = new jump_threader (m_simplifier, m_state);
 }