diff gcc/tree-ssa-threadbackward.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/tree-ssa-threadbackward.c	Fri Oct 27 22:46:09 2017 +0900
@@ -0,0 +1,904 @@
+/* SSA Jump Threading
+   Copyright (C) 2005-2017 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 "backend.h"
+#include "predict.h"
+#include "tree.h"
+#include "gimple.h"
+#include "fold-const.h"
+#include "cfgloop.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-ssa-threadupdate.h"
+#include "params.h"
+#include "tree-ssa-loop.h"
+#include "cfganal.h"
+#include "tree-pass.h"
+#include "gimple-ssa.h"
+#include "tree-phinodes.h"
+#include "tree-inline.h"
+#include "tree-vectorizer.h"
+
+static int max_threaded_paths;
+
+/* 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)
+{
+  gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+
+  if (gsi_end_p (gsi))
+    return NULL;
+
+  gimple *stmt = gsi_stmt (gsi);
+  enum gimple_code code = gimple_code (stmt);
+  if (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO)
+    return stmt;
+  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.  VISITED_BBS is used to make sure we don't fall
+   into an infinite loop.  Bound the recursion to basic blocks
+   belonging to LOOP.  */
+
+static bool
+fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
+		      vec<basic_block> &path,
+		      hash_set<basic_block> &visited_bbs, loop_p loop)
+{
+  if (loop != start_bb->loop_father)
+    return false;
+
+  if (start_bb == end_bb)
+    {
+      path.safe_push (start_bb);
+      return true;
+    }
+
+  if (!visited_bbs.add (start_bb))
+    {
+      edge e;
+      edge_iterator ei;
+      FOR_EACH_EDGE (e, ei, start_bb->succs)
+	if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop))
+	  {
+	    path.safe_push (start_bb);
+	    return true;
+	  }
+    }
+
+  return false;
+}
+
+/* Examine jump threading path PATH to which we want to add BBI.
+
+   If the resulting path is profitable to thread, then return the
+   final taken edge from the path, NULL otherwise.
+
+   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.
+
+   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.
+
+   SPEED_P indicate that we could increase code size to improve the
+   code path.  */
+
+static edge
+profitable_jump_thread_path (vec<basic_block> &path,
+			     basic_block bbi, tree name, tree arg,
+			     bool speed_p, 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.  */
+
+  /* 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.
+
+     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 (path.is_empty ())
+      return NULL;
+
+  if (path.length () + 1 > (unsigned) PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "FSM jump-thread path not considered: "
+		 "the number of basic blocks on the path "
+		 "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
+      return NULL;
+    }
+
+  if (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;
+    }
+
+  /* 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.  */
+  path.safe_push (bbi);
+
+  int n_insns = 0;
+  gimple_stmt_iterator gsi;
+  loop_p loop = path[0]->loop_father;
+  bool path_crosses_loops = false;
+  bool threaded_through_latch = false;
+  bool multiway_branch_in_path = false;
+  bool threaded_multiway_branch = false;
+  bool contains_hot_bb = false;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Checking profitability of path (backwards): ");
+
+  /* Count the number of instructions on the path: as these instructions
+     will have to be duplicated, we will not record the path if there
+     are too many instructions on the path.  Also check that all the
+     blocks in the path belong to a single loop.  */
+  for (unsigned j = 0; j < path.length (); j++)
+    {
+      basic_block bb = path[j];
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, " bb:%i", bb->index);
+      /* Remember, blocks in the path are stored in opposite order
+	 in the PATH array.  The last entry in the array represents
+	 the block with an outgoing edge that we will redirect to the
+	 jump threading path.  Thus we don't care about that block's
+	 loop father, nor how many statements are in that block because
+	 it will not be copied or whether or not it ends in a multiway
+	 branch.  */
+      if (j < path.length () - 1)
+	{
+	  int orig_n_insns = n_insns;
+	  if (bb->loop_father != loop)
+	    {
+	      path_crosses_loops = true;
+	      break;
+	    }
+
+	  /* PHIs in the path will create degenerate PHIS in the
+	     copied path which will then get propagated away, so
+	     looking at just the duplicate path the PHIs would
+	     seem unimportant.
+
+	     But those PHIs, because they're assignments to objects
+	     typically with lives that exist outside the thread path,
+	     will tend to generate PHIs (or at least new PHI arguments)
+	     at points where we leave the thread path and rejoin
+	     the original blocks.  So we do want to account for them.
+
+	     We ignore virtual PHIs.  We also ignore cases where BB
+	     has a single incoming edge.  That's the most common
+	     degenerate PHI we'll see here.  Finally we ignore PHIs
+	     that are associated with the value we're tracking as
+	     that object likely dies.  */
+	  if (EDGE_COUNT (bb->succs) > 1 && EDGE_COUNT (bb->preds) > 1)
+	    {
+	      for (gphi_iterator gsip = gsi_start_phis (bb);
+		   !gsi_end_p (gsip);
+		   gsi_next (&gsip))
+		{
+		  gphi *phi = gsip.phi ();
+		  tree dst = gimple_phi_result (phi);
+
+		  /* Note that if both NAME and DST are anonymous
+		     SSA_NAMEs, then we do not have enough information
+		     to consider them associated.  */
+		  if (dst != name
+		      && (SSA_NAME_VAR (dst) != SSA_NAME_VAR (name)
+			  || !SSA_NAME_VAR (dst))
+		      && !virtual_operand_p (dst))
+		    ++n_insns;
+		}
+	    }
+
+	  if (!contains_hot_bb && speed_p)
+	    contains_hot_bb |= optimize_bb_for_speed_p (bb);
+	  for (gsi = gsi_after_labels (bb);
+	       !gsi_end_p (gsi);
+	       gsi_next_nondebug (&gsi))
+	    {
+	      gimple *stmt = gsi_stmt (gsi);
+	      /* Do not count empty statements and labels.  */
+	      if (gimple_code (stmt) != GIMPLE_NOP
+		  && !(gimple_code (stmt) == GIMPLE_ASSIGN
+		       && gimple_assign_rhs_code (stmt) == ASSERT_EXPR)
+		  && !is_gimple_debug (stmt))
+		n_insns += estimate_num_insns (stmt, &eni_size_weights);
+	    }
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, " (%i insns)", n_insns-orig_n_insns);
+
+	  /* We do not look at the block with the threaded branch
+	     in this loop.  So if any block with a last statement that
+	     is a GIMPLE_SWITCH or GIMPLE_GOTO is seen, then we have a
+	     multiway branch on our path.
+
+	     The block in PATH[0] is special, it's the block were we're
+	     going to be able to eliminate its branch.  */
+	  gimple *last = last_stmt (bb);
+	  if (last && (gimple_code (last) == GIMPLE_SWITCH
+		       || gimple_code (last) == GIMPLE_GOTO))
+	    {
+	      if (j == 0)
+		threaded_multiway_branch = true;
+	      else
+		multiway_branch_in_path = true;
+	    }
+	}
+
+      /* Note if we thread through the latch, we will want to include
+	 the last entry in the array when determining if we thread
+	 through the loop latch.  */
+      if (loop->latch == bb)
+	threaded_through_latch = true;
+    }
+
+  gimple *stmt = get_gimple_control_stmt (path[0]);
+  gcc_assert (stmt);
+
+  /* We are going to remove the control statement at the end of the
+     last block in the threading path.  So don't count it against our
+     statement count.  */
+
+  int stmt_insns = estimate_num_insns (stmt, &eni_size_weights);
+  n_insns-= stmt_insns;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\n  Control statement insns: %i\n"
+	     "  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 (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)
+    {
+      path.pop ();
+      return NULL;
+    }
+
+  *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: "
+		 "the path crosses loops.\n");
+      path.pop ();
+      return NULL;
+    }
+
+  /* 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 (speed_p && (optimize_edge_for_speed_p (taken_edge) || contains_hot_bb))
+    {
+      if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "FSM jump-thread path not considered: "
+		     "the number of instructions on the path "
+		     "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
+	  path.pop ();
+	  return NULL;
+	}
+    }
+  else if (n_insns > 1)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "FSM jump-thread path not considered: "
+		 "duplication of %i insns is needed and optimizing for size.\n",
+		 n_insns);
+      path.pop ();
+      return NULL;
+    }
+
+  /* We avoid creating irreducible inner loops unless we thread through
+     a multiway branch, in which case we have deemed it worth losing
+     other loop optimizations later.
+
+     We also consider it worth creating an irreducible inner loop if
+     the number of copied statement is low relative to the length of
+     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
+      && (n_insns * (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
+	  > (path.length () *
+	     (unsigned) PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS))))
+
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "FSM would create irreducible loop without threading "
+		 "multiway branch.\n");
+      path.pop ();
+      return NULL;
+    }
+
+
+  /* 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.  */
+  if (!(threaded_through_latch && threaded_multiway_branch)
+      && (n_insns * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
+	  >= PARAM_VALUE (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 "
+		 "many statements.\n");
+      path.pop ();
+      return NULL;
+    }
+
+  /* When there is a multi-way branch on the path, then threading can
+     explode the CFG due to duplicating the edges for that multi-way
+     branch.  So like above, only allow a multi-way branch on the path
+     if we actually thread a multi-way branch.  */
+  if (!threaded_multiway_branch && multiway_branch_in_path)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "FSM Thread through multiway branch without threading "
+		 "a multiway branch.\n");
+      path.pop ();
+      return NULL;
+    }
+  return taken_edge;
+}
+
+/* PATH is vector of blocks forming a jump threading path in reverse
+   order.  TAKEN_EDGE is the edge taken from path[0].
+
+   Convert that path into the form used by register_jump_thread and
+   register the path.   */
+
+static void
+convert_and_register_jump_thread_path (vec<basic_block> &path, edge taken_edge)
+{
+  vec<jump_thread_edge *> *jump_thread_path = new vec<jump_thread_edge *> ();
+
+  /* Record the edges between the blocks in PATH.  */
+  for (unsigned int j = 0; j + 1 < path.length (); j++)
+    {
+      basic_block bb1 = path[path.length () - j - 1];
+      basic_block bb2 = path[path.length () - j - 2];
+
+      edge e = find_edge (bb1, bb2);
+      gcc_assert (e);
+      jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
+      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);
+  jump_thread_path->safe_push (x);
+
+  register_jump_thread (jump_thread_path);
+  --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.  */
+
+static bool
+check_subpath_and_update_thread_path (basic_block last_bb, basic_block new_bb,
+				      hash_set<basic_block> &visited_bbs,
+				      vec<basic_block> &path,
+				      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> visited_bbs;
+
+      if (fsm_find_thread_path (new_bb, e->src, next_path, 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 (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++)
+    visited_bbs.add (next_path[i]);
+
+  /* Append all the nodes from NEXT_PATH to PATH.  */
+  path.safe_splice (next_path);
+  *next_path_length = next_path.length ();
+
+  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.
+
+   SPEED_P indicate that we could increase code size to improve the
+   code path.
+*/
+
+static void
+register_jump_thread_path_if_profitable (vec<basic_block> &path,
+					 tree name,
+					 tree arg,
+					 basic_block def_bb,
+					 bool speed_p)
+{
+  if (TREE_CODE_CLASS (TREE_CODE (arg)) != tcc_constant)
+    return;
+
+  bool irreducible = false;
+  edge taken_edge = profitable_jump_thread_path (path, def_bb, name, arg,
+						 speed_p, &irreducible);
+  if (taken_edge)
+    {
+      convert_and_register_jump_thread_path (path, taken_edge);
+      path.pop ();
+
+      if (irreducible)
+	vect_free_loop_info_assumptions (path[0]->loop_father);
+    }
+}
+
+static void fsm_find_control_statement_thread_paths (tree,
+						     hash_set<basic_block> &,
+						     vec<basic_block> &,
+						     bool, bool);
+
+/* 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.
+
+   VISITED_BBS tracks the blocks that have been encountered.
+
+   PATH contains the series of blocks to traverse that will result in
+   NAME having a constant value.
+
+   SEEN_LOOP_PHI tracks if we have recursed through a loop PHI node.
+
+   SPEED_P indicates if we are optimizing for speed over space.  */
+
+static void
+handle_phi (gphi *phi, tree name, basic_block def_bb,
+	    hash_set<basic_block> &visited_bbs,
+	    vec<basic_block> &path,
+	    bool seen_loop_phi, bool speed_p)
+{
+  /* 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)
+	{
+	  path.safe_push (bbi);
+	  /* Recursively follow SSA_NAMEs looking for a constant
+	     definition.  */
+	  fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
+						   seen_loop_phi, speed_p);
+
+	  path.pop ();
+	  continue;
+	}
+
+      register_jump_thread_path_if_profitable (path, name, arg, bbi, speed_p);
+    }
+}
+
+/* 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.
+
+   VISITED_BBS tracks the blocks that have been encountered.
+
+   PATH contains the series of blocks to traverse that will result in
+   NAME having a constant value.
+
+   SEEN_LOOP_PHI tracks if we have recursed through a loop PHI node.
+
+   SPEED_P indicates if we are optimizing for speed over space.  */
+
+static void
+handle_assignment (gimple *stmt, tree name, basic_block def_bb,
+		   hash_set<basic_block> &visited_bbs,
+		   vec<basic_block> &path,
+		   bool seen_loop_phi, bool speed_p)
+{
+  tree arg = gimple_assign_rhs1 (stmt);
+
+  if (TREE_CODE (arg) == SSA_NAME)
+    fsm_find_control_statement_thread_paths (arg, visited_bbs,
+					     path, seen_loop_phi, speed_p);
+
+  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.  */
+      path.pop ();
+
+      register_jump_thread_path_if_profitable (path, name, arg, def_bb,
+					       speed_p);
+
+      /* And put the current block back onto the path so that the
+	 state of the stack is unchanged when we leave.  */
+      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.
+
+   SPEED_P indicate that we could increase code size to improve the
+   code path.  */
+
+static void
+fsm_find_control_statement_thread_paths (tree name,
+					 hash_set<basic_block> &visited_bbs,
+					 vec<basic_block> &path,
+					 bool seen_loop_phi, bool speed_p)
+{
+  /* 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_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS)))
+    return;
+
+  if (is_gimple_assign (def_stmt)
+      && ! handle_assignment_p (def_stmt))
+    return;
+
+  /* Avoid infinite recursion.  */
+  if (visited_bbs.add (def_bb))
+    return;
+
+  int next_path_length = 0;
+  basic_block last_bb_in_path = path.last ();
+
+  if (loop_containing_stmt (def_stmt)->header == gimple_bb (def_stmt))
+    {
+      /* Do not walk through more than one loop PHI node.  */
+      if (seen_loop_phi)
+	return;
+      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.  */
+      visited_bbs.add (path[0]);
+      if (!check_subpath_and_update_thread_path (last_bb_in_path, def_bb,
+						 visited_bbs, path,
+						 &next_path_length))
+	return;
+    }
+
+  gcc_assert (path.last () == def_bb);
+
+  if (gimple_code (def_stmt) == GIMPLE_PHI)
+    handle_phi (as_a <gphi *> (def_stmt), name, def_bb,
+		visited_bbs, path, seen_loop_phi, speed_p);
+  else if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
+    handle_assignment (def_stmt, name, def_bb,
+		       visited_bbs, path, seen_loop_phi, speed_p);
+
+  /* Remove all the nodes that we added from NEXT_PATH.  */
+  if (next_path_length)
+    path.truncate (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 indicate that we could increase code size to improve the
+   code path.  */
+
+void  
+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;
+
+  auto_vec<basic_block> bb_path;
+  bb_path.safe_push (bb);
+  hash_set<basic_block> visited_bbs;
+
+  max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
+  fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false,
+					   speed_p);
+}
+
+namespace {
+
+const pass_data pass_data_thread_jumps =
+{
+  GIMPLE_PASS,
+  "thread",
+  OPTGROUP_NONE,
+  TV_TREE_SSA_THREAD_JUMPS,
+  ( PROP_cfg | PROP_ssa ),
+  0,
+  0,
+  0,
+  TODO_update_ssa,
+};
+
+class pass_thread_jumps : public gimple_opt_pass
+{
+public:
+  pass_thread_jumps (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_thread_jumps, ctxt)
+  {}
+
+  opt_pass * clone (void) { return new pass_thread_jumps (m_ctxt); }
+  virtual bool gate (function *);
+  virtual unsigned int execute (function *);
+};
+
+bool
+pass_thread_jumps::gate (function *fun ATTRIBUTE_UNUSED)
+{
+  return flag_expensive_optimizations;
+}
+
+
+unsigned int
+pass_thread_jumps::execute (function *fun)
+{
+  loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES);
+
+  /* Try to thread each block with more than one successor.  */
+  basic_block bb;
+  FOR_EACH_BB_FN (bb, fun)
+    {
+      if (EDGE_COUNT (bb->succs) > 1)
+	find_jump_threads_backwards (bb, true);
+    }
+  bool changed = thread_through_all_blocks (true);
+
+  loop_optimizer_finalize ();
+  return changed ? TODO_cleanup_cfg : 0;
+}
+
+}
+
+gimple_opt_pass *
+make_pass_thread_jumps (gcc::context *ctxt)
+{
+  return new pass_thread_jumps (ctxt);
+}
+
+namespace {
+
+const pass_data pass_data_early_thread_jumps =
+{
+  GIMPLE_PASS,
+  "ethread",
+  OPTGROUP_NONE,
+  TV_TREE_SSA_THREAD_JUMPS,
+  ( PROP_cfg | PROP_ssa ),
+  0,
+  0,
+  0,
+  ( TODO_cleanup_cfg | TODO_update_ssa ),
+};
+
+class pass_early_thread_jumps : public gimple_opt_pass
+{
+public:
+  pass_early_thread_jumps (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_early_thread_jumps, ctxt)
+  {}
+
+  opt_pass * clone (void) { return new pass_early_thread_jumps (m_ctxt); }
+  virtual bool gate (function *);
+  virtual unsigned int execute (function *);
+};
+
+bool
+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.  */
+  basic_block bb;
+  FOR_EACH_BB_FN (bb, fun)
+    {
+      if (EDGE_COUNT (bb->succs) > 1)
+	find_jump_threads_backwards (bb, false);
+    }
+  thread_through_all_blocks (true);
+
+  loop_optimizer_finalize ();
+  return 0;
+}
+
+}
+
+gimple_opt_pass *
+make_pass_early_thread_jumps (gcc::context *ctxt)
+{
+  return new pass_early_thread_jumps (ctxt);
+}