[PR,tree-optimization/68580] Throttle size of PHI nodes we'll walk in FSM threader

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index a551069..60e229f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,11 @@ 
+2016-02-01  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/68580
+	* params.def (FSM_MAXIMUM_PHI_ARGUMENTS): New param.
+	* tree-ssa-threadbackward.c
+	(fsm_find_control_statement_thread_paths): Do not try to walk
+	through large PHI nodes.
+
 2016-02-01  Jakub Jelinek  <jakub@redhat.com>
 
 	* ifcvt.c (bb_ok_for_noce_convert_multiple_sets): Return false
diff --git a/gcc/params.def b/gcc/params.def
index 0722ad7..c0494fa 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -1150,6 +1150,11 @@  DEFPARAM (PARAM_FSM_SCALE_PATH_STMTS,
 	  "Scale factor to apply to the number of statements in a threading path when comparing to the number of (scaled) blocks.",
 	  2, 1, 10)
 
+DEFPARAM (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS,
+	  "fsm-maximum-phi-arguments",
+	  "Maximum number of arguments a PHI may have before the FSM threader will not try to thread through its block.",
+	  100, 1, 999999)
+
 DEFPARAM (PARAM_FSM_SCALE_PATH_BLOCKS,
 	  "fsm-scale-path-blocks",
 	  "Scale factor to apply to the number of blocks in a threading path when comparing to the number of (scaled) statements.",
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 735009c..55dbcad 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -114,7 +114,9 @@  fsm_find_control_statement_thread_paths (tree name,
      eventually one of the phi arguments will be an integer constant.  In the
      future, this could be extended to also handle simple assignments of
      arithmetic operations.  */
-  if (gimple_code (def_stmt) != GIMPLE_PHI)
+  if (gimple_code (def_stmt) != GIMPLE_PHI
+      || (gimple_phi_num_args (def_stmt)
+	  >= (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS)))
     return;
 
   /* Avoid infinite recursion.  */
@@ -200,247 +202,253 @@  fsm_find_control_statement_thread_paths (tree name,
 
   /* Iterate over the arguments of PHI.  */
   unsigned int i;
-  for (i = 0; i < gimple_phi_num_args (phi); i++)
+  if (gimple_phi_num_args (phi)
+      < (unsigned) PARAM_VALUE (PARAM_FSM_MAXIMUM_PHI_ARGUMENTS))
     {
-      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 || var_bb->loop_father != bbi->loop_father)
-	continue;
-
-      if (TREE_CODE (arg) == SSA_NAME)
+      for (i = 0; i < gimple_phi_num_args (phi); i++)
 	{
-	  vec_safe_push (path, bbi);
-	  /* Recursively follow SSA_NAMEs looking for a constant definition.  */
-	  fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
-						   seen_loop_phi);
+	  tree arg = gimple_phi_arg_def (phi, i);
+	  basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
 
-	  path->pop ();
-	  continue;
-	}
+	  /* Skip edges pointing outside the current loop.  */
+	  if (!arg || var_bb->loop_father != bbi->loop_father)
+	    continue;
 
-      if (TREE_CODE (arg) != INTEGER_CST)
-	continue;
+	  if (TREE_CODE (arg) == SSA_NAME)
+	    {
+	      vec_safe_push (path, bbi);
+	      /* Recursively follow SSA_NAMEs looking for a constant
+		 definition.  */
+	      fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
+						       seen_loop_phi);
+
+	      path->pop ();
+	      continue;
+	    }
 
-      /* 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.  */
-      int path_length = path->length ();
-      if (path_length + 1 > 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");
-	  continue;
-	}
+	  if (TREE_CODE (arg) != INTEGER_CST)
+	    continue;
 
-      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");
-	  continue;
-	}
+	  /* 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.  */
+	  int path_length = path->length ();
+	  if (path_length + 1 > 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");
+	      continue;
+	    }
 
-      /* Add BBI to the path.  */
-      vec_safe_push (path, bbi);
-      ++path_length;
-
-      int n_insns = 0;
-      gimple_stmt_iterator gsi;
-      int j;
-      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;
-
-      /* 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 (j = 0; j < path_length; j++)
-	{
-	  basic_block bb = (*path)[j];
-
-	  /* 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)
+	  if (max_threaded_paths <= 0)
 	    {
-	      if (bb->loop_father != loop)
-		{
-		  path_crosses_loops = true;
-		  break;
-		}
+	      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");
+	      continue;
+	    }
 
-	      for (gsi = gsi_after_labels (bb);
-		   !gsi_end_p (gsi);
-		   gsi_next_nondebug (&gsi))
+	  /* Add BBI to the path.  */
+	  vec_safe_push (path, bbi);
+	  ++path_length;
+
+	  int n_insns = 0;
+	  gimple_stmt_iterator gsi;
+	  int j;
+	  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;
+
+	  /* 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 (j = 0; j < path_length; j++)
+	    {
+	      basic_block bb = (*path)[j];
+
+	      /* 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)
 		{
-		  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;
+		  if (bb->loop_father != loop)
+		    {
+		      path_crosses_loops = true;
+		      break;
+		    }
+
+		  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;
+		    }
+
+		  /* 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;
+		    }
 		}
 
-	      /* 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;
 	    }
 
-	  /* 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 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);
 
-      gimple *stmt = get_gimple_control_stmt ((*path)[0]);
-      gcc_assert (stmt);
-      /* 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));
+	    }
 
-	  /* 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);
+	  bool 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;
+
+	  /* PHIs in the final target and only the final target will need
+	     to be duplicated.  So only count those against the number
+	     of statements.  */
+	  gphi_iterator gsip;
+	  for (gsip = gsi_start_phis (taken_edge->dest);
+	       !gsi_end_p (gsip);
+	       gsi_next (&gsip))
+	    {
+	      gphi *phi = gsip.phi ();
+	      tree dst = gimple_phi_result (phi);
+
+	      /* We consider any non-virtual PHI as a statement since it
+		 count result in a constant assignment or copy
+		 operation.  */
+	      if (!virtual_operand_p (dst))
+		++n_insns;
+	    }
 
-      /* 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);
-      bool 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;
-
-      /* PHIs in the final target and only the final target will need
-	 to be duplicated.  So only count those against the number
-	 of statements.  */
-      gphi_iterator gsip;
-      for (gsip = gsi_start_phis (taken_edge->dest);
-	   !gsi_end_p (gsip);
-	   gsi_next (&gsip))
-	{
-	  gphi *phi = gsip.phi ();
-	  tree dst = gimple_phi_result (phi);
-
-	  /* We consider any non-virtual PHI as a statement since it
-	     count result in a constant assignment or copy
-	     operation.  */
-	  if (!virtual_operand_p (dst))
-	    ++n_insns;
-	}
+	  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 ();
+	      continue;
+	    }
 
-      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 ();
-	  continue;
-	}
+	  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 ();
+	      continue;
+	    }
 
-      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 ();
-	  continue;
-	}
+	  /* 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 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 * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
+		  > path_length * PARAM_VALUE (PARAM_FSM_SCALE_PATH_BLOCKS)))
 
-	 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 * PARAM_VALUE (PARAM_FSM_SCALE_PATH_STMTS)
-	      > path_length * 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 ();
+	      continue;
+	    }
 
-	{
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    fprintf (dump_file,
-		     "FSM would create irreducible loop without threading "
-		     "multiway branch.\n");
-	  path->pop ();
-	  continue;
-	}
+	  /* 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 ();
+	      continue;
+	    }
 
-      /* 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 ();
-	  continue;
-	}
+	  vec<jump_thread_edge *> *jump_thread_path
+	    = new vec<jump_thread_edge *> ();
 
-      vec<jump_thread_edge *> *jump_thread_path
-	= new vec<jump_thread_edge *> ();
+	  /* Record the edges between the blocks in PATH.  */
+	  for (j = 0; j < path_length - 1; j++)
+	    {
+	      edge e = find_edge ((*path)[path_length - j - 1],
+				  (*path)[path_length - j - 2]);
+	      gcc_assert (e);
+	      jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
+	      jump_thread_path->safe_push (x);
+	    }
 
-      /* Record the edges between the blocks in PATH.  */
-      for (j = 0; j < path_length - 1; j++)
-	{
-	  edge e = find_edge ((*path)[path_length - j - 1],
-			      (*path)[path_length - j - 2]);
-	  gcc_assert (e);
-	  jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
+	  /* 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);
-	}
 
-      /* 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;
 
-      register_jump_thread (jump_thread_path);
-      --max_threaded_paths;
-
-      /* Remove BBI from the path.  */
-      path->pop ();
+	  /* Remove BBI from the path.  */
+	  path->pop ();
+	}
     }
 
   /* Remove all the nodes that we added from NEXT_PATH.  */