Merge from trunk revision 104c05c5284b7822d770ee51a7d91946c7e56d50.

1 files changed, 623 insertions, 478 deletions

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 515a94b..805b7ac 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -36,40 +36,420 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-phinodes.h"
 #include "tree-inline.h"
 #include "tree-vectorizer.h"
+#include "value-range.h"
+#include "gimple-range.h"
+#include "tree-ssa-threadedge.h"
+#include "gimple-range-path.h"
+#include "ssa.h"
+#include "tree-cfgcleanup.h"
+#include "tree-pretty-print.h"
+#include "cfghooks.h"
+
+// Path registry for the backwards threader.  After all paths have been
+// registered with register_path(), thread_through_all_blocks() is called
+// to modify the CFG.
+
+class back_threader_registry
+{
+public:
+  back_threader_registry (int max_allowable_paths);
+  bool register_path (const vec<basic_block> &, edge taken);
+  bool thread_through_all_blocks (bool may_peel_loop_headers);
+private:
+  back_jt_path_registry m_lowlevel_registry;
+  const int m_max_allowable_paths;
+  int m_threaded_paths;
+};
 
-class thread_jumps
-{
- public:
-  void find_jump_threads_backwards (basic_block bb, bool speed_p);
- private:
-  edge profitable_jump_thread_path (basic_block bbi, tree name, tree arg,
-				    bool *creates_irreducible_loop);
-  void convert_and_register_current_path (edge taken_edge);
-  void register_jump_thread_path_if_profitable (tree name, tree arg,
-						basic_block def_bb);
-  void handle_assignment (gimple *stmt, tree name, basic_block def_bb);
-  void handle_phi (gphi *phi, tree name, basic_block def_bb);
-  void fsm_find_control_statement_thread_paths (tree name);
-  bool check_subpath_and_update_thread_path (basic_block last_bb,
-					     basic_block new_bb,
-					     int *next_path_length);
-
-  /* Maximum number of BBs we are allowed to thread.  */
-  int m_max_threaded_paths;
-  /* Hash to keep track of seen bbs.  */
-  hash_set<basic_block> m_visited_bbs;
-  /* Current path we're analyzing.  */
+// Class to abstract the profitability code for the backwards threader.
+
+class back_threader_profitability
+{
+public:
+  back_threader_profitability (bool speed_p)
+    : m_speed_p (speed_p)
+  { }
+  bool profitable_path_p (const vec<basic_block> &, tree name, edge taken,
+			  bool *irreducible_loop = NULL);
+private:
+  const bool m_speed_p;
+};
+
+class back_threader
+{
+public:
+  back_threader (bool speed_p);
+  ~back_threader ();
+  void maybe_thread_block (basic_block bb);
+  bool thread_through_all_blocks (bool may_peel_loop_headers);
+private:
+  void find_paths (basic_block bb, tree name);
+  edge maybe_register_path ();
+  bool find_paths_to_names (basic_block bb, bitmap imports);
+  bool resolve_def (tree name, bitmap interesting, vec<tree> &worklist);
+  bool resolve_phi (gphi *phi, bitmap imports);
+  edge find_taken_edge (const vec<basic_block> &path);
+  edge find_taken_edge_cond (const vec<basic_block> &path, gcond *);
+  edge find_taken_edge_switch (const vec<basic_block> &path, gswitch *);
+  virtual void debug ();
+  virtual void dump (FILE *out);
+
+  back_threader_registry m_registry;
+  back_threader_profitability m_profit;
+  gimple_ranger m_ranger;
+  path_range_query m_solver;
+
+  // Current path being analyzed.
   auto_vec<basic_block> m_path;
-  /* Tracks if we have recursed through a loop PHI node.  */
-  bool m_seen_loop_phi;
-  /* Indicate that we could increase code size to improve the
-     code path.  */
-  bool m_speed_p;
+  // Hash to mark visited BBs while analyzing a path.
+  hash_set<basic_block> m_visited_bbs;
+  // The set of SSA names, any of which could potentially change the
+  // value of the final conditional in a path.
+  bitmap m_imports;
+  // The last statement in the path.
+  gimple *m_last_stmt;
+  // This is a bit of a wart.  It's used to pass the LHS SSA name to
+  // the profitability engine.
+  tree m_name;
+  // Marker to differentiate unreachable edges.
+  static const edge UNREACHABLE_EDGE;
 };
 
-/* Simple helper to get the last statement from BB, which is assumed
-   to be a control statement.   Return NULL if the last statement is
-   not a control statement.  */
+// Used to differentiate unreachable edges, so we may stop the search
+// in a the given direction.
+const edge back_threader::UNREACHABLE_EDGE = (edge) -1;
+
+back_threader::back_threader (bool speed_p)
+  : m_registry (param_max_fsm_thread_paths),
+    m_profit (speed_p),
+    m_solver (m_ranger)
+{
+  m_last_stmt = NULL;
+  m_imports = BITMAP_ALLOC (NULL);
+}
+
+back_threader::~back_threader ()
+{
+  m_path.release ();
+  BITMAP_FREE (m_imports);
+}
+
+// Register the current path for jump threading if it's profitable to
+// do so.
+//
+// Return the known taken edge out of the path, even if the path was
+// not registered, or NULL if the taken edge could not be determined.
+
+edge
+back_threader::maybe_register_path ()
+{
+  edge taken_edge = find_taken_edge (m_path);
+
+  if (taken_edge && taken_edge != UNREACHABLE_EDGE)
+    {
+      bool irreducible = false;
+      bool profitable
+	= m_profit.profitable_path_p (m_path, m_name, taken_edge, &irreducible);
+
+      if (profitable)
+	{
+	  m_registry.register_path (m_path, taken_edge);
+
+	  if (irreducible)
+	    vect_free_loop_info_assumptions (m_path[0]->loop_father);
+	}
+    }
+  return taken_edge;
+}
+
+// Return the known taken edge out of a path.  If the path can be
+// determined to be unreachable, return UNREACHABLE_EDGE.  If no
+// outgoing edge can be calculated, return NULL.
+
+edge
+back_threader::find_taken_edge (const vec<basic_block> &path)
+{
+  gcc_checking_assert (path.length () > 1);
+  switch (gimple_code (m_last_stmt))
+    {
+    case GIMPLE_COND:
+      return find_taken_edge_cond (path, as_a<gcond *> (m_last_stmt));
+
+    case GIMPLE_SWITCH:
+      return find_taken_edge_switch (path, as_a<gswitch *> (m_last_stmt));
+
+    default:
+      return NULL;
+    }
+}
+
+// Same as find_taken_edge, but for paths ending in a switch.
+
+edge
+back_threader::find_taken_edge_switch (const vec<basic_block> &path,
+				       gswitch *sw)
+{
+  tree name = gimple_switch_index (sw);
+  int_range_max r;
+
+  m_solver.precompute_ranges (path, m_imports);
+  m_solver.range_of_expr (r, name, sw);
+
+  if (r.undefined_p ())
+    return UNREACHABLE_EDGE;
+
+  if (r.varying_p ())
+    return NULL;
+
+  tree val;
+  if (r.singleton_p (&val))
+    return ::find_taken_edge (gimple_bb (sw), val);
+
+  return NULL;
+}
+
+// Same as find_taken_edge, but for paths ending in a GIMPLE_COND.
+
+edge
+back_threader::find_taken_edge_cond (const vec<basic_block> &path,
+				     gcond *cond)
+{
+  int_range_max r;
+
+  m_solver.precompute_ranges (path, m_imports);
+  m_solver.range_of_stmt (r, cond);
+
+  if (m_solver.unreachable_path_p ())
+    return UNREACHABLE_EDGE;
+
+  int_range<2> true_range (boolean_true_node, boolean_true_node);
+  int_range<2> false_range (boolean_false_node, boolean_false_node);
+
+  if (r == true_range || r == false_range)
+    {
+      edge e_true, e_false;
+      basic_block bb = gimple_bb (cond);
+      extract_true_false_edges_from_block (bb, &e_true, &e_false);
+      return r == true_range ? e_true : e_false;
+    }
+  return NULL;
+}
+
+// Populate a vector of trees from a bitmap.
+
+static inline void
+populate_worklist (vec<tree> &worklist, bitmap bits)
+{
+  bitmap_iterator bi;
+  unsigned i;
+
+  EXECUTE_IF_SET_IN_BITMAP (bits, 0, i, bi)
+    {
+      tree name = ssa_name (i);
+      worklist.quick_push (name);
+    }
+}
+
+// If taking any of the incoming edges to a PHI causes the final
+// conditional of the current path to be constant, register the
+// path(s), and return TRUE.
+
+bool
+back_threader::resolve_phi (gphi *phi, bitmap interesting)
+{
+  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
+    return true;
+
+  bool done = false;
+  for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
+    {
+      edge e = gimple_phi_arg_edge (phi, i);
+
+      // This is like path_crosses_loops in profitable_path_p but more
+      // restrictive, since profitable_path_p allows threading the
+      // first block because it would be redirected anyhow.
+      //
+      // If we loosened the restriction and used profitable_path_p()
+      // here instead, we would peel off the first iterations of loops
+      // in places like tree-ssa/pr14341.c.
+      bool profitable_p = m_path[0]->loop_father == e->src->loop_father;
+      if (!profitable_p)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "  FAIL: path through PHI in bb%d (incoming bb:%d) crosses loop\n",
+		     e->dest->index, e->src->index);
+	  continue;
+	}
+
+      tree arg = gimple_phi_arg_def (phi, i);
+      if (TREE_CODE (arg) == SSA_NAME)
+	{
+	  unsigned v = SSA_NAME_VERSION (arg);
+
+	  // Avoid loops as in: x_5 = PHI <x_5(2), ...>.
+	  if (bitmap_bit_p (interesting, v))
+	    continue;
+
+	  bitmap_set_bit (interesting, v);
+	  bitmap_set_bit (m_imports, v);
+	  done |= find_paths_to_names (e->src, interesting);
+	  bitmap_clear_bit (interesting, v);
+	}
+      else if (TREE_CODE (arg) == INTEGER_CST)
+	{
+	  m_path.safe_push (e->src);
+	  edge taken_edge = maybe_register_path ();
+	  if (taken_edge && taken_edge != UNREACHABLE_EDGE)
+	    done = true;
+	  m_path.pop ();
+	}
+    }
+  return done;
+}
+
+// If the definition of NAME causes the final conditional of the
+// current path to be constant, register the path, and return TRUE.
+
+bool
+back_threader::resolve_def (tree name, bitmap interesting, vec<tree> &worklist)
+{
+  gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+  // Handle PHIs.
+  if (is_a<gphi *> (def_stmt)
+      && resolve_phi (as_a<gphi *> (def_stmt), interesting))
+    return true;
+
+  // Defer copies of SSAs by adding the source to the worklist.
+  if (gimple_assign_single_p (def_stmt)
+      && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME)
+    {
+      tree rhs = gimple_assign_rhs1 (def_stmt);
+      bitmap_set_bit (m_imports, SSA_NAME_VERSION (rhs));
+      bitmap_set_bit (interesting, SSA_NAME_VERSION (rhs));
+      worklist.safe_push (rhs);
+    }
+  return false;
+}
+
+// Find jump threading paths to any of the SSA names in the
+// INTERESTING bitmap, and register any such paths.
+//
+// Return TRUE if no further processing past this block is necessary.
+// This is because we've either registered a path, or because there is
+// nothing of interesting beyond this block.
+//
+// BB is the current path being processed.
+
+bool
+back_threader::find_paths_to_names (basic_block bb, bitmap interesting)
+{
+  if (m_visited_bbs.add (bb))
+    return true;
+
+  m_path.safe_push (bb);
+
+  if (m_path.length () > 1
+      && !m_profit.profitable_path_p (m_path, m_name, NULL))
+    {
+      m_path.pop ();
+      m_visited_bbs.remove (bb);
+      return false;
+    }
+
+  auto_bitmap processed;
+  unsigned i;
+  bool done = false;
+
+  // We use a worklist instead of iterating through the bitmap,
+  // because we may add new items in-flight.
+  auto_vec<tree> worklist (bitmap_count_bits (interesting));
+  populate_worklist (worklist, interesting);
+  while (!worklist.is_empty ())
+    {
+      tree name = worklist.pop ();
+      unsigned i = SSA_NAME_VERSION (name);
+      basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
+
+      // Process any names defined in this block.
+      if (def_bb == bb)
+	{
+	  bitmap_set_bit (processed, i);
+
+	  if (resolve_def (name, interesting, worklist))
+	    {
+	      done = true;
+	      goto leave_bb;
+	    }
+	}
+      // Examine blocks that define or export an interesting SSA,
+      // since they may compute a range which resolve this path.
+      if ((def_bb == bb
+	   || bitmap_bit_p (m_ranger.gori ().exports (bb), i))
+	  && m_path.length () > 1)
+	{
+	  if (maybe_register_path ())
+	    {
+	      done = true;
+	      goto leave_bb;
+	    }
+	}
+    }
+
+  // If there are interesting names not yet processed, keep looking.
+  bitmap_and_compl_into (interesting, processed);
+  if (!bitmap_empty_p (interesting))
+    {
+      edge_iterator iter;
+      edge e;
+      FOR_EACH_EDGE (e, iter, bb->preds)
+	if ((e->flags & EDGE_ABNORMAL) == 0)
+	  done |= find_paths_to_names (e->src, interesting);
+    }
+
+ leave_bb:
+  bitmap_iterator bi;
+  EXECUTE_IF_SET_IN_BITMAP (processed, 0, i, bi)
+    bitmap_set_bit (interesting, i);
+
+  m_path.pop ();
+  m_visited_bbs.remove (bb);
+  return done;
+}
+
+// Search backwards from BB looking for paths where the final
+// conditional out of BB can be determined.  NAME is the LHS of the
+// final conditional.  Register such paths for jump threading.
+
+void
+back_threader::find_paths (basic_block bb, tree name)
+{
+  gimple *stmt = last_stmt (bb);
+  if (!stmt
+      || (gimple_code (stmt) != GIMPLE_COND
+	  && gimple_code (stmt) != GIMPLE_SWITCH))
+    return;
+
+  if (EDGE_COUNT (bb->succs) > 1
+      || single_succ_to_potentially_threadable_block (bb))
+    {
+      m_last_stmt = stmt;
+      m_visited_bbs.empty ();
+      m_path.truncate (0);
+      m_name = name;
+      bitmap_clear (m_imports);
+
+      auto_bitmap interesting;
+      bitmap_copy (m_imports, m_ranger.gori ().imports (bb));
+      bitmap_copy (interesting, m_imports);
+      find_paths_to_names (bb, interesting);
+    }
+}
+
+// Simple helper to get the last statement from BB, which is assumed
+// to be a control statement.  Return NULL if the last statement is
+// not a control statement.
 
 static gimple *
 get_gimple_control_stmt (basic_block bb)
@@ -86,99 +466,139 @@ get_gimple_control_stmt (basic_block bb)
   return NULL;
 }
 
-/* Return true if the CFG contains at least one path from START_BB to
-   END_BB.  When a path is found, record in PATH the blocks from
-   END_BB to START_BB.  LOCAL_VISITED_BBS is used to make sure we
-   don't fall into an infinite loop.  Bound the recursion to basic
-   blocks belonging to LOOP.  */
+// Search backwards from BB looking for paths where the final
+// conditional maybe threaded to a successor block.  Record such paths
+// for jump threading.
 
-static bool
-fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
-		      vec<basic_block> &path,
-		      hash_set<basic_block> &local_visited_bbs,
-		      loop_p loop)
+void
+back_threader::maybe_thread_block (basic_block bb)
+{
+  gimple *stmt = get_gimple_control_stmt (bb);
+  if (!stmt)
+    return;
+
+  enum gimple_code code = gimple_code (stmt);
+  tree name;
+  if (code == GIMPLE_SWITCH)
+    name = gimple_switch_index (as_a <gswitch *> (stmt));
+  else if (code == GIMPLE_COND)
+    name = gimple_cond_lhs (stmt);
+  else if (code == GIMPLE_GOTO)
+    name = gimple_goto_dest (stmt);
+  else
+    name = NULL;
+
+  find_paths (bb, name);
+}
+
+// Perform the actual jump threading for the all queued paths.
+
+bool
+back_threader::thread_through_all_blocks (bool may_peel_loop_headers)
 {
-  if (loop != start_bb->loop_father)
-    return false;
+  return m_registry.thread_through_all_blocks (may_peel_loop_headers);
+}
+
+// Dump a sequence of BBs through the CFG.
 
-  if (start_bb == end_bb)
+DEBUG_FUNCTION void
+dump_path (FILE *dump_file, const vec<basic_block> &path)
+{
+  for (size_t i = 0; i < path.length (); ++i)
     {
-      path.safe_push (start_bb);
-      return true;
+      fprintf (dump_file, "BB%d", path[i]->index);
+      if (i + 1 < path.length ())
+	fprintf (dump_file, " <- ");
     }
+  fprintf (dump_file, "\n");
+}
+
+DEBUG_FUNCTION void
+debug (const vec <basic_block> &path)
+{
+  dump_path (stderr, path);
+}
+
+void
+back_threader::dump (FILE *out)
+{
+  m_solver.dump (out);
+  fprintf (out, "\nCandidates for pre-computation:\n");
+  fprintf (out, "===================================\n");
+
+  bitmap_iterator bi;
+  unsigned i;
 
-  if (!local_visited_bbs.add (start_bb))
+  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
     {
-      edge e;
-      edge_iterator ei;
-      FOR_EACH_EDGE (e, ei, start_bb->succs)
-	if (fsm_find_thread_path (e->dest, end_bb, path, local_visited_bbs,
-				  loop))
-	  {
-	    path.safe_push (start_bb);
-	    return true;
-	  }
+      tree name = ssa_name (i);
+      print_generic_expr (out, name, TDF_NONE);
+      fprintf (out, "\n");
     }
+}
 
-  return false;
+void
+back_threader::debug ()
+{
+  dump (stderr);
 }
 
-/* Examine jump threading path PATH to which we want to add BBI.
+back_threader_registry::back_threader_registry (int max_allowable_paths)
+  : m_max_allowable_paths (max_allowable_paths)
+{
+  m_threaded_paths = 0;
+}
 
-   If the resulting path is profitable to thread, then return the
-   final taken edge from the path, NULL otherwise.
+bool
+back_threader_registry::thread_through_all_blocks (bool may_peel_loop_headers)
+{
+  return m_lowlevel_registry.thread_through_all_blocks (may_peel_loop_headers);
+}
+
+/* Examine jump threading path PATH and return TRUE if it is profitable to
+   thread it, otherwise return FALSE.
 
    NAME is the SSA_NAME of the variable we found to have a constant
-   value on PATH.  ARG is the constant value of NAME on that path.
+   value on PATH.  If unknown, SSA_NAME is NULL.
 
-   BBI will be appended to PATH when we have a profitable jump
-   threading path.  Callers are responsible for removing BBI from PATH
-   in that case.  */
+   If the taken edge out of the path is known ahead of time it is passed in
+   TAKEN_EDGE, otherwise it is NULL.
 
-edge
-thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
-					   tree arg,
-					   bool *creates_irreducible_loop)
+   CREATES_IRREDUCIBLE_LOOP, if non-null is set to TRUE if threading this path
+   would create an irreducible loop.
+
+   ?? It seems we should be able to loosen some of the restrictions in
+   this function after loop optimizations have run.  */
+
+bool
+back_threader_profitability::profitable_path_p (const vec<basic_block> &m_path,
+						tree name,
+						edge taken_edge,
+						bool *creates_irreducible_loop)
 {
-  /* Note BBI is not in the path yet, hence the +1 in the test below
-     to make sure BBI is accounted for in the path length test.  */
+  gcc_checking_assert (!m_path.is_empty ());
 
-  /* We can get a length of 0 here when the statement that
-     makes a conditional generate a compile-time constant
-     result is in the same block as the conditional.
+  /* We can an empty path here (excluding the DEF block) when the
+     statement that makes a conditional generate a compile-time
+     constant result is in the same block as the conditional.
 
      That's not really a jump threading opportunity, but instead is
      simple cprop & simplification.  We could handle it here if we
      wanted by wiring up all the incoming edges.  If we run this
      early in IPA, that might be worth doing.   For now we just
      reject that case.  */
-  if (m_path.is_empty ())
-      return NULL;
+  if (m_path.length () <= 1)
+      return false;
 
-  if (m_path.length () + 1
-      > (unsigned) param_max_fsm_thread_length)
+  if (m_path.length () > (unsigned) param_max_fsm_thread_length)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "FSM jump-thread path not considered: "
+	fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
 		 "the number of basic blocks on the path "
 		 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
-      return NULL;
-    }
-
-  if (m_max_threaded_paths <= 0)
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "FSM jump-thread path not considered: "
-		 "the number of previously recorded FSM paths to "
-		 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
-      return NULL;
+      return false;
     }
 
-  /* Add BBI to the path.
-     From this point onward, if we decide we the path is not profitable
-     to thread, we must remove BBI from the path.  */
-  m_path.safe_push (bbi);
-
   int n_insns = 0;
   gimple_stmt_iterator gsi;
   loop_p loop = m_path[0]->loop_father;
@@ -214,6 +634,14 @@ thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
 	  if (bb->loop_father != loop)
 	    {
 	      path_crosses_loops = true;
+
+	      // Dump rest of blocks.
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		for (j++; j < m_path.length (); j++)
+		  {
+		    bb = m_path[j];
+		    fprintf (dump_file, " bb:%i", bb->index);
+		  }
 	      break;
 	    }
 
@@ -246,6 +674,8 @@ thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
 		     SSA_NAMEs, then we do not have enough information
 		     to consider them associated.  */
 		  if (dst != name
+		      && name
+		      && TREE_CODE (name) == SSA_NAME
 		      && (SSA_NAME_VAR (dst) != SSA_NAME_VAR (name)
 			  || !SSA_NAME_VAR (dst))
 		      && !virtual_operand_p (dst))
@@ -266,10 +696,7 @@ thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
 	      gimple *stmt = gsi_stmt (gsi);
 	      if (gimple_call_internal_p (stmt, IFN_UNIQUE)
 		  || gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
-		{
-		  m_path.pop ();
-		  return NULL;
-		}
+		return false;
 	      /* Do not count empty statements and labels.  */
 	      if (gimple_code (stmt) != GIMPLE_NOP
 		  && !(gimple_code (stmt) == GIMPLE_ASSIGN
@@ -302,7 +729,11 @@ thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
 	 the last entry in the array when determining if we thread
 	 through the loop latch.  */
       if (loop->latch == bb)
-	threaded_through_latch = true;
+	{
+	  threaded_through_latch = true;
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, " (latch)");
+	}
     }
 
   gimple *stmt = get_gimple_control_stmt (m_path[0]);
@@ -320,75 +751,52 @@ thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
 	     "  Overall: %i insns\n",
 	     stmt_insns, n_insns);
 
-  /* We have found a constant value for ARG.  For GIMPLE_SWITCH
-     and GIMPLE_GOTO, we use it as-is.  However, for a GIMPLE_COND
-     we need to substitute, fold and simplify so we can determine
-     the edge taken out of the last block.  */
-  if (gimple_code (stmt) == GIMPLE_COND)
-    {
-      enum tree_code cond_code = gimple_cond_code (stmt);
-
-      /* We know the underyling format of the condition.  */
-      arg = fold_binary (cond_code, boolean_type_node,
-			 arg, gimple_cond_rhs (stmt));
-    }
-
-  /* If this path threaded through the loop latch back into the
-     same loop and the destination does not dominate the loop
-     latch, then this thread would create an irreducible loop.
-
-     We have to know the outgoing edge to figure this out.  */
-  edge taken_edge = find_taken_edge (m_path[0], arg);
-
-  /* There are cases where we may not be able to extract the
-     taken edge.  For example, a computed goto to an absolute
-     address.  Handle those cases gracefully.  */
-  if (taken_edge == NULL)
+  if (creates_irreducible_loop)
     {
-      m_path.pop ();
-      return NULL;
+      /* If this path threaded through the loop latch back into the
+	 same loop and the destination does not dominate the loop
+	 latch, then this thread would create an irreducible loop.  */
+      *creates_irreducible_loop = false;
+      if (taken_edge
+	  && threaded_through_latch
+	  && loop == taken_edge->dest->loop_father
+	  && (determine_bb_domination_status (loop, taken_edge->dest)
+	      == DOMST_NONDOMINATING))
+	*creates_irreducible_loop = true;
     }
 
-  *creates_irreducible_loop = false;
-  if (threaded_through_latch
-      && loop == taken_edge->dest->loop_father
-      && (determine_bb_domination_status (loop, taken_edge->dest)
-	  == DOMST_NONDOMINATING))
-    *creates_irreducible_loop = true;
-
   if (path_crosses_loops)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "FSM jump-thread path not considered: "
+	fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
 		 "the path crosses loops.\n");
-      m_path.pop ();
-      return NULL;
+      return false;
     }
 
   /* Threading is profitable if the path duplicated is hot but also
      in a case we separate cold path from hot path and permit optimization
      of the hot path later.  Be on the agressive side here. In some testcases,
      as in PR 78407 this leads to noticeable improvements.  */
-  if (m_speed_p && (optimize_edge_for_speed_p (taken_edge) || contains_hot_bb))
+  if (m_speed_p
+      && ((taken_edge && optimize_edge_for_speed_p (taken_edge))
+	  || contains_hot_bb))
     {
       if (n_insns >= param_max_fsm_thread_path_insns)
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    fprintf (dump_file, "FSM jump-thread path not considered: "
+	    fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
 		     "the number of instructions on the path "
 		     "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
-	  m_path.pop ();
-	  return NULL;
+	  return false;
 	}
     }
-  else if (n_insns > 1)
+  else if (!m_speed_p && n_insns > 1)
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "FSM jump-thread path not considered: "
+	fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
 		 "duplication of %i insns is needed and optimizing for size.\n",
 		 n_insns);
-      m_path.pop ();
-      return NULL;
+      return false;
     }
 
   /* We avoid creating irreducible inner loops unless we thread through
@@ -400,7 +808,9 @@ thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
      the path -- in that case there's little the traditional loop
      optimizer would have done anyway, so an irreducible loop is not
      so bad.  */
-  if (!threaded_multiway_branch && *creates_irreducible_loop
+  if (!threaded_multiway_branch
+      && creates_irreducible_loop
+      && *creates_irreducible_loop
       && (n_insns * (unsigned) param_fsm_scale_path_stmts
 	  > (m_path.length () *
 	     (unsigned) param_fsm_scale_path_blocks)))
@@ -408,30 +818,24 @@ thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
-		 "FSM would create irreducible loop without threading "
+		 "  FAIL: Would create irreducible loop without threading "
 		 "multiway branch.\n");
-      m_path.pop ();
-      return NULL;
+      return false;
     }
 
-
-  /* If this path does not thread through the loop latch, then we are
-     using the FSM threader to find old style jump threads.  This
-     is good, except the FSM threader does not re-use an existing
-     threading path to reduce code duplication.
-
-     So for that case, drastically reduce the number of statements
-     we are allowed to copy.  */
+  /* The generic copier used by the backthreader does not re-use an
+     existing threading path to reduce code duplication.  So for that
+     case, drastically reduce the number of statements we are allowed
+     to copy.  */
   if (!(threaded_through_latch && threaded_multiway_branch)
       && (n_insns * param_fsm_scale_path_stmts
 	  >= param_max_jump_thread_duplication_stmts))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
-		 "FSM did not thread around loop and would copy too "
+		 "  FAIL: Did not thread around loop and would copy too "
 		 "many statements.\n");
-      m_path.pop ();
-      return NULL;
+      return false;
     }
 
   /* When there is a multi-way branch on the path, then threading can
@@ -442,26 +846,55 @@ thread_jumps::profitable_jump_thread_path (basic_block bbi, tree name,
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file,
-		 "FSM Thread through multiway branch without threading "
+		 "  FAIL: Thread through multiway branch without threading "
 		 "a multiway branch.\n");
-      m_path.pop ();
-      return NULL;
+      return false;
     }
-  return taken_edge;
+
+  /* Threading through an empty latch would cause code to be added to
+     the latch.  This could alter the loop form sufficiently to cause
+     loop optimizations to fail.  Disable these threads until after
+     loop optimizations have run.  */
+  if ((threaded_through_latch
+       || (taken_edge && taken_edge->dest == loop->latch))
+      && !(cfun->curr_properties & PROP_loop_opts_done)
+      && empty_block_p (loop->latch))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "  FAIL: Thread through latch before loop opts would create non-empty latch\n");
+      return false;
+
+    }
+  return true;
 }
 
 /* The current path PATH is a vector of blocks forming a jump threading
    path in reverse order.  TAKEN_EDGE is the edge taken from path[0].
 
    Convert the current path into the form used by register_jump_thread and
-   register it.   */
+   register it.
 
-void
-thread_jumps::convert_and_register_current_path (edge taken_edge)
+   Return TRUE if successful or FALSE otherwise.  */
+
+bool
+back_threader_registry::register_path (const vec<basic_block> &m_path,
+				       edge taken_edge)
 {
-  vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();
+  if (m_threaded_paths > m_max_allowable_paths)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  FAIL: Jump-thread path not considered: "
+		 "the number of previously recorded paths to "
+		 "thread exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
+      return false;
+    }
+
+  vec<jump_thread_edge *> *jump_thread_path
+    = m_lowlevel_registry.allocate_thread_path ();
 
-  /* Record the edges between the blocks in PATH.  */
+  // The generic copier ignores the edge type.  We can build the
+  // thread edges with any type.
   for (unsigned int j = 0; j + 1 < m_path.length (); j++)
     {
       basic_block bb1 = m_path[m_path.length () - j - 1];
@@ -469,317 +902,21 @@ thread_jumps::convert_and_register_current_path (edge taken_edge)
 
       edge e = find_edge (bb1, bb2);
       gcc_assert (e);
-      jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
+      jump_thread_edge *x
+	= m_lowlevel_registry.allocate_thread_edge (e, EDGE_COPY_SRC_BLOCK);
       jump_thread_path->safe_push (x);
     }
 
-  /* Add the edge taken when the control variable has value ARG.  */
   jump_thread_edge *x
-    = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
+    = m_lowlevel_registry.allocate_thread_edge (taken_edge,
+						EDGE_NO_COPY_SRC_BLOCK);
   jump_thread_path->safe_push (x);
 
-  register_jump_thread (jump_thread_path);
-  --m_max_threaded_paths;
-}
-
-/* While following a chain of SSA_NAME definitions, we jumped from a
-   definition in LAST_BB to a definition in NEW_BB (walking
-   backwards).
-
-   Verify there is a single path between the blocks and none of the
-   blocks in the path is already in VISITED_BBS.  If so, then update
-   VISISTED_BBS, add the new blocks to PATH and return TRUE.
-   Otherwise return FALSE.
-
-   Store the length of the subpath in NEXT_PATH_LENGTH.  */
-
-bool
-thread_jumps::check_subpath_and_update_thread_path (basic_block last_bb,
-						    basic_block new_bb,
-						    int *next_path_length)
-{
-  edge e;
-  int e_count = 0;
-  edge_iterator ei;
-  auto_vec<basic_block> next_path;
-
-  FOR_EACH_EDGE (e, ei, last_bb->preds)
-    {
-      hash_set<basic_block> local_visited_bbs;
-
-      if (fsm_find_thread_path (new_bb, e->src, next_path,
-				local_visited_bbs, e->src->loop_father))
-	++e_count;
-
-      /* If there is more than one path, stop.  */
-      if (e_count > 1)
-	return false;
-    }
-
-  /* Stop if we have not found a path: this could occur when the recursion
-     is stopped by one of the bounds.  */
-  if (e_count == 0)
-    return false;
-
-  /* Make sure we haven't already visited any of the nodes in
-     NEXT_PATH.  Don't add them here to avoid pollution.  */
-  for (unsigned int i = 0; i + 1 < next_path.length (); i++)
-    {
-      if (m_visited_bbs.contains (next_path[i]))
-	return false;
-    }
-
-  /* Now add the nodes to VISISTED_BBS.  */
-  for (unsigned int i = 0; i + 1 < next_path.length (); i++)
-    m_visited_bbs.add (next_path[i]);
-
-  /* Append all the nodes from NEXT_PATH to PATH.  */
-  m_path.safe_splice (next_path);
-  *next_path_length = next_path.length ();
-
+  if (m_lowlevel_registry.register_jump_thread (jump_thread_path))
+    ++m_threaded_paths;
   return true;
 }
 
-/* If this is a profitable jump thread path, register it.
-
-   NAME is an SSA NAME with a possible constant value of ARG on PATH.
-
-   DEF_BB is the basic block that ultimately defines the constant.  */
-
-void
-thread_jumps::register_jump_thread_path_if_profitable (tree name, tree arg,
-						       basic_block def_bb)
-{
-  if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
-    return;
-
-  bool irreducible = false;
-  edge taken_edge = profitable_jump_thread_path (def_bb, name, arg,
-						 &irreducible);
-  if (taken_edge)
-    {
-      convert_and_register_current_path (taken_edge);
-      m_path.pop ();
-
-      if (irreducible)
-	vect_free_loop_info_assumptions (m_path[0]->loop_father);
-    }
-}
-
-/* Given PHI which defines NAME in block DEF_BB, recurse through the
-   PHI's arguments searching for paths where NAME will ultimately have
-   a constant value.
-
-   PATH contains the series of blocks to traverse that will result in
-   NAME having a constant value.  */
-
-void
-thread_jumps::handle_phi (gphi *phi, tree name, basic_block def_bb)
-{
-  /* Iterate over the arguments of PHI.  */
-  for (unsigned int i = 0; i < gimple_phi_num_args (phi); i++)
-    {
-      tree arg = gimple_phi_arg_def (phi, i);
-      basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
-
-      /* Skip edges pointing outside the current loop.  */
-      if (!arg || def_bb->loop_father != bbi->loop_father)
-	continue;
-
-      if (TREE_CODE (arg) == SSA_NAME)
-	{
-	  m_path.safe_push (bbi);
-	  /* Recursively follow SSA_NAMEs looking for a constant
-	     definition.  */
-	  fsm_find_control_statement_thread_paths (arg);
-
-	  m_path.pop ();
-	  continue;
-	}
-
-      register_jump_thread_path_if_profitable (name, arg, bbi);
-    }
-}
-
-/* Return TRUE if STMT is a gimple assignment we want to either directly
-   handle or recurse through.  Return FALSE otherwise.
-
-   Note that adding more cases here requires adding cases to handle_assignment
-   below.  */
-
-static bool
-handle_assignment_p (gimple *stmt)
-{
-  if (is_gimple_assign (stmt))
-    {
-      enum tree_code def_code = gimple_assign_rhs_code (stmt);
-
-      /* If the RHS is an SSA_NAME, then we will recurse through it.
-	 Go ahead and filter out cases where the SSA_NAME is a default
-	 definition.  There's little to be gained by trying to handle that.  */
-      if (def_code == SSA_NAME
-	  && !SSA_NAME_IS_DEFAULT_DEF (gimple_assign_rhs1 (stmt)))
-	return true;
-
-      /* If the RHS is a constant, then it's a terminal that we'll want
-	 to handle as well.  */
-      if (TREE_CODE_CLASS (def_code) == tcc_constant)
-	return true;
-    }
-
-  /* Anything not explicitly allowed is not handled.  */
-  return false;
-}
-
-/* Given STMT which defines NAME in block DEF_BB, recurse through the
-   PHI's arguments searching for paths where NAME will ultimately have
-   a constant value.
-
-   PATH contains the series of blocks to traverse that will result in
-   NAME having a constant value.  */
-
-void
-thread_jumps::handle_assignment (gimple *stmt, tree name, basic_block def_bb)
-{
-  tree arg = gimple_assign_rhs1 (stmt);
-
-  if (TREE_CODE (arg) == SSA_NAME)
-    fsm_find_control_statement_thread_paths (arg);
-
-  else
-    {
-      /* register_jump_thread_path_if_profitable will push the current
-	 block onto the path.  But the path will always have the current
-	 block at this point.  So we can just pop it.  */
-      m_path.pop ();
-
-      register_jump_thread_path_if_profitable (name, arg, def_bb);
-
-      /* And put the current block back onto the path so that the
-	 state of the stack is unchanged when we leave.  */
-      m_path.safe_push (def_bb);
-    }
-}
-
-/* We trace the value of the SSA_NAME NAME back through any phi nodes
-   looking for places where it gets a constant value and save the
-   path.  */
-
-void
-thread_jumps::fsm_find_control_statement_thread_paths (tree name)
-{
-  /* If NAME appears in an abnormal PHI, then don't try to trace its
-     value back through PHI nodes.  */
-  if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
-    return;
-
-  gimple *def_stmt = SSA_NAME_DEF_STMT (name);
-  basic_block def_bb = gimple_bb (def_stmt);
-
-  if (def_bb == NULL)
-    return;
-
-  /* We allow the SSA chain to contains PHIs and simple copies and constant
-     initializations.  */
-  if (gimple_code (def_stmt) != GIMPLE_PHI
-      && gimple_code (def_stmt) != GIMPLE_ASSIGN)
-    return;
-
-  if (gimple_code (def_stmt) == GIMPLE_PHI
-      && (gimple_phi_num_args (def_stmt)
-	  >= (unsigned) param_fsm_maximum_phi_arguments))
-    return;
-
-  if (is_gimple_assign (def_stmt)
-      && ! handle_assignment_p (def_stmt))
-    return;
-
-  /* Avoid infinite recursion.  */
-  if (m_visited_bbs.add (def_bb))
-    return;
-
-  int next_path_length = 0;
-  basic_block last_bb_in_path = m_path.last ();
-
-  if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt))
-    {
-      /* Do not walk through more than one loop PHI node.  */
-      if (m_seen_loop_phi)
-	return;
-      m_seen_loop_phi = true;
-    }
-
-  /* Following the chain of SSA_NAME definitions, we jumped from a definition in
-     LAST_BB_IN_PATH to a definition in DEF_BB.  When these basic blocks are
-     different, append to PATH the blocks from LAST_BB_IN_PATH to DEF_BB.  */
-  if (def_bb != last_bb_in_path)
-    {
-      /* When DEF_BB == LAST_BB_IN_PATH, then the first block in the path
-	 will already be in VISITED_BBS.  When they are not equal, then we
-	 must ensure that first block is accounted for to ensure we do not
-	 create bogus jump threading paths.  */
-      m_visited_bbs.add (m_path[0]);
-      if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb,
-						 &next_path_length))
-	return;
-    }
-
-  gcc_assert (m_path.last () == def_bb);
-
-  if (gimple_code (def_stmt) == GIMPLE_PHI)
-    handle_phi (as_a <gphi *> (def_stmt), name, def_bb);
-  else if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
-    handle_assignment (def_stmt, name, def_bb);
-
-  /* Remove all the nodes that we added from NEXT_PATH.  */
-  if (next_path_length)
-    m_path.truncate (m_path.length () - next_path_length);
-}
-
-/* Search backwards from BB looking for paths where NAME (an SSA_NAME)
-   is a constant.  Record such paths for jump threading.
-
-   It is assumed that BB ends with a control statement and that by
-   finding a path where NAME is a constant, we can thread the path.
-   SPEED_P indicates that we could increase code size to improve the
-   code path.  */
-
-void
-thread_jumps::find_jump_threads_backwards (basic_block bb, bool speed_p)
-{     
-  gimple *stmt = get_gimple_control_stmt (bb);
-  if (!stmt)
-    return;
-
-  enum gimple_code code = gimple_code (stmt);
-  tree name = NULL;
-  if (code == GIMPLE_SWITCH)
-    name = gimple_switch_index (as_a <gswitch *> (stmt));
-  else if (code == GIMPLE_GOTO)
-    name = gimple_goto_dest (stmt);
-  else if (code == GIMPLE_COND)
-    {
-      if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
-	  && TREE_CODE_CLASS (TREE_CODE (gimple_cond_rhs (stmt))) == tcc_constant
-	  && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
-	      || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
-	name = gimple_cond_lhs (stmt);
-    }
-
-  if (!name || TREE_CODE (name) != SSA_NAME)
-    return;
-
-  /* Initialize pass local data that's different for each BB.  */
-  m_path.truncate (0);
-  m_path.safe_push (bb);
-  m_visited_bbs.empty ();
-  m_seen_loop_phi = false;
-  m_speed_p = speed_p;
-  m_max_threaded_paths = param_max_fsm_thread_paths;
-
-  fsm_find_control_statement_thread_paths (name);
-}
-
 namespace {
 
 const pass_data pass_data_thread_jumps =
@@ -813,23 +950,32 @@ pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
   return flag_expensive_optimizations;
 }
 
+// Try to thread blocks in FUN.  Return TRUE if any jump thread paths were
+// registered.
 
-unsigned int
-pass_thread_jumps::execute (function *fun)
+static bool
+try_thread_blocks (function *fun)
 {
-  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
-
   /* Try to thread each block with more than one successor.  */
-  thread_jumps threader;
+  back_threader threader (/*speed_p=*/true);
   basic_block bb;
   FOR_EACH_BB_FN (bb, fun)
     {
       if (EDGE_COUNT (bb->succs) > 1)
-	threader.find_jump_threads_backwards (bb, true);
+	threader.maybe_thread_block (bb);
     }
-  bool changed = thread_through_all_blocks (true);
+  return threader.thread_through_all_blocks (/*peel_loop_headers=*/true);
+}
+
+unsigned int
+pass_thread_jumps::execute (function *fun)
+{
+  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
+
+  bool changed = try_thread_blocks (fun);
 
   loop_optimizer_finalize ();
+
   return changed ? TODO_cleanup_cfg : 0;
 }
 
@@ -874,21 +1020,20 @@ pass_early_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
   return true;
 }
 
-
 unsigned int
 pass_early_thread_jumps::execute (function *fun)
 {
   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
 
   /* Try to thread each block with more than one successor.  */
-  thread_jumps threader;
+  back_threader threader (/*speed_p=*/false);
   basic_block bb;
   FOR_EACH_BB_FN (bb, fun)
     {
       if (EDGE_COUNT (bb->succs) > 1)
-	threader.find_jump_threads_backwards (bb, false);
+	threader.maybe_thread_block (bb);
     }
-  thread_through_all_blocks (true);
+  threader.thread_through_all_blocks (/*peel_loop_headers=*/true);
 
   loop_optimizer_finalize ();
   return 0;