re PR tree-optimization/23942 (loop problem / testcase takes very long time to compile)

	PR tree-optimization/23942
	* Makefile.in (SCEV_H): Depends on PARAMS_H.
	* tree-scalar-evolution.c: Include params.h.
	(t_bool): New enum.
	(follow_ssa_edge, follow_ssa_edge_in_rhs,
	follow_ssa_edge_in_condition_phi_branch,
	follow_ssa_edge_in_condition_phi, follow_ssa_edge_inner_loop_phi):
	Change return type to t_bool.  Use a parameter to limit the size of
	trees that are walked before stopping
	(analyze_evolution_in_loop): Initialize the limit to 0.
	(follow_ssa_edge): Give up by returning t_dont_know if the limit
	exceeds PARAM_SCEV_MAX_EXPR_SIZE.

From-SVN: r104653

1 files changed, 106 insertions, 81 deletions

diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 82f814e..b13cac1 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -251,6 +251,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "tree-scalar-evolution.h"
 #include "tree-pass.h"
 #include "flags.h"
+#include "params.h"
 
 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
 static tree resolve_mixers (struct loop *, tree);
@@ -1022,19 +1023,23 @@ select_loops_exit_conditions (struct loops *loops,
 
 /* Depth first search algorithm.  */
 
-static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
+typedef enum t_bool {
+  t_false,
+  t_true,
+  t_dont_know
+} t_bool;
+
+
+static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
 
 /* Follow the ssa edge into the right hand side RHS of an assignment.
    Return true if the strongly connected component has been found.  */
 
-static bool
-follow_ssa_edge_in_rhs (struct loop *loop,
-			tree at_stmt,
-			tree rhs, 
-			tree halting_phi, 
-			tree *evolution_of_loop)
+static t_bool
+follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs, 
+			tree halting_phi, tree *evolution_of_loop, int limit)
 {
-  bool res = false;
+  t_bool res = t_false;
   tree rhs0, rhs1;
   tree type_rhs = TREE_TYPE (rhs);
   
@@ -1050,20 +1055,20 @@ follow_ssa_edge_in_rhs (struct loop *loop,
     case NOP_EXPR:
       /* This assignment is under the form "a_1 = (cast) rhs.  */
       res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
-				    halting_phi, evolution_of_loop);
+				    halting_phi, evolution_of_loop, limit);
       *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
 					  *evolution_of_loop, at_stmt);
       break;
 
     case INTEGER_CST:
       /* This assignment is under the form "a_1 = 7".  */
-      res = false;
+      res = t_false;
       break;
       
     case SSA_NAME:
       /* This assignment is under the form: "a_1 = b_2".  */
       res = follow_ssa_edge 
-	(loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
+	(loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
       break;
       
     case PLUS_EXPR:
@@ -1081,26 +1086,32 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 		 "a = b + c".  */
 	      res = follow_ssa_edge 
 		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
-		 evolution_of_loop);
+		 evolution_of_loop, limit);
 	      
-	      if (res)
+	      if (res == t_true)
 		*evolution_of_loop = add_to_evolution 
 		  (loop->num, 
 		   chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 
 		   PLUS_EXPR, rhs1);
 	      
-	      else
+	      else if (res == t_false)
 		{
 		  res = follow_ssa_edge 
 		    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
-		     evolution_of_loop);
+		     evolution_of_loop, limit);
 		  
-		  if (res)
+		  if (res == t_true)
 		    *evolution_of_loop = add_to_evolution 
 		      (loop->num, 
 		       chrec_convert (type_rhs, *evolution_of_loop, at_stmt), 
 		       PLUS_EXPR, rhs0);
+
+		  else if (res == t_dont_know)
+		    *evolution_of_loop = chrec_dont_know;
 		}
+
+	      else if (res == t_dont_know)
+		*evolution_of_loop = chrec_dont_know;
 	    }
 	  
 	  else
@@ -1109,12 +1120,15 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 		 "a = b + ...".  */
 	      res = follow_ssa_edge 
 		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
-		 evolution_of_loop);
-	      if (res)
+		 evolution_of_loop, limit);
+	      if (res == t_true)
 		*evolution_of_loop = add_to_evolution 
 		  (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
 					     at_stmt),
 		   PLUS_EXPR, rhs1);
+
+	      else if (res == t_dont_know)
+		*evolution_of_loop = chrec_dont_know;
 	    }
 	}
       
@@ -1124,19 +1138,22 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 	     "a = ... + c".  */
 	  res = follow_ssa_edge 
 	    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
-	     evolution_of_loop);
-	  if (res)
+	     evolution_of_loop, limit);
+	  if (res == t_true)
 	    *evolution_of_loop = add_to_evolution 
 	      (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
 					 at_stmt),
 	       PLUS_EXPR, rhs0);
+
+	  else if (res == t_dont_know)
+	    *evolution_of_loop = chrec_dont_know;
 	}
 
       else
 	/* Otherwise, match an assignment under the form: 
 	   "a = ... + ...".  */
 	/* And there is nothing to do.  */
-	res = false;
+	res = t_false;
       
       break;
       
@@ -1152,18 +1169,20 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 	  /* Match an assignment under the form: 
 	     "a = b - ...".  */
 	  res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
-				 evolution_of_loop);
-	  if (res)
+				 evolution_of_loop, limit);
+	  if (res == t_true)
 	    *evolution_of_loop = add_to_evolution 
-		    (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
-					       at_stmt),
-		     MINUS_EXPR, rhs1);
+	      (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
+	       MINUS_EXPR, rhs1);
+
+	  else if (res == t_dont_know)
+	    *evolution_of_loop = chrec_dont_know;
 	}
       else
 	/* Otherwise, match an assignment under the form: 
 	   "a = ... - ...".  */
 	/* And there is nothing to do.  */
-	res = false;
+	res = t_false;
       
       break;
     
@@ -1182,18 +1201,18 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 		 "a = b * c".  */
 	      res = follow_ssa_edge 
 		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
-		 evolution_of_loop);
+		 evolution_of_loop, limit);
 	      
-	      if (res)
+	      if (res == t_true || res == t_dont_know)
 		*evolution_of_loop = chrec_dont_know;
 	      
-	      else
+	      else if (res == t_false)
 		{
 		  res = follow_ssa_edge 
 		    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
-		     evolution_of_loop);
+		     evolution_of_loop, limit);
 		  
-		  if (res)
+		  if (res == t_true || res == t_dont_know)
 		    *evolution_of_loop = chrec_dont_know;
 		}
 	    }
@@ -1204,8 +1223,8 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 		 "a = b * ...".  */
 	      res = follow_ssa_edge 
 		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
-		 evolution_of_loop);
-	      if (res)
+		 evolution_of_loop, limit);
+	      if (res == t_true || res == t_dont_know)
 		*evolution_of_loop = chrec_dont_know;
 	    }
 	}
@@ -1216,8 +1235,8 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 	     "a = ... * c".  */
 	  res = follow_ssa_edge 
 	    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
-	     evolution_of_loop);
-	  if (res)
+	     evolution_of_loop, limit);
+	  if (res == t_true || res == t_dont_know)
 	    *evolution_of_loop = chrec_dont_know;
 	}
       
@@ -1225,7 +1244,7 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 	/* Otherwise, match an assignment under the form: 
 	   "a = ... * ...".  */
 	/* And there is nothing to do.  */
-	res = false;
+	res = t_false;
       
       break;
 
@@ -1236,15 +1255,15 @@ follow_ssa_edge_in_rhs (struct loop *loop,
 	tree op0 = ASSERT_EXPR_VAR (rhs);
 	if (TREE_CODE (op0) == SSA_NAME)
 	  res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
-				 halting_phi, evolution_of_loop);
+				 halting_phi, evolution_of_loop, limit);
 	else
-	  res = false;
+	  res = t_false;
 	break;
       }
 
 
     default:
-      res = false;
+      res = t_false;
       break;
     }
   
@@ -1271,13 +1290,13 @@ backedge_phi_arg_p (tree phi, int i)
    true if the strongly connected component has been found following
    this path.  */
 
-static inline bool
+static inline t_bool
 follow_ssa_edge_in_condition_phi_branch (int i,
 					 struct loop *loop, 
 					 tree condition_phi, 
 					 tree halting_phi,
 					 tree *evolution_of_branch,
-					 tree init_cond)
+					 tree init_cond, int limit)
 {
   tree branch = PHI_ARG_DEF (condition_phi, i);
   *evolution_of_branch = chrec_dont_know;
@@ -1285,13 +1304,13 @@ follow_ssa_edge_in_condition_phi_branch (int i,
   /* Do not follow back edges (they must belong to an irreducible loop, which
      we really do not want to worry about).  */
   if (backedge_phi_arg_p (condition_phi, i))
-    return false;
+    return t_false;
 
   if (TREE_CODE (branch) == SSA_NAME)
     {
       *evolution_of_branch = init_cond;
       return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi, 
-			      evolution_of_branch);
+			      evolution_of_branch, limit);
     }
 
   /* This case occurs when one of the condition branches sets 
@@ -1301,27 +1320,28 @@ follow_ssa_edge_in_condition_phi_branch (int i,
      FIXME:  This case have to be refined correctly: 
      in some cases it is possible to say something better than
      chrec_dont_know, for example using a wrap-around notation.  */
-  return false;
+  return t_false;
 }
 
 /* This function merges the branches of a condition-phi-node in a
    loop.  */
 
-static bool
+static t_bool
 follow_ssa_edge_in_condition_phi (struct loop *loop,
 				  tree condition_phi, 
 				  tree halting_phi, 
-				  tree *evolution_of_loop)
+				  tree *evolution_of_loop, int limit)
 {
   int i;
   tree init = *evolution_of_loop;
   tree evolution_of_branch;
+  t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
+							halting_phi,
+							&evolution_of_branch,
+							init, limit);
+  if (res == t_false || res == t_dont_know)
+    return res;
 
-  if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
-						halting_phi,
-						&evolution_of_branch,
-						init))
-    return false;
   *evolution_of_loop = evolution_of_branch;
 
   for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
@@ -1329,19 +1349,20 @@ follow_ssa_edge_in_condition_phi (struct loop *loop,
       /* Quickly give up when the evolution of one of the branches is
 	 not known.  */
       if (*evolution_of_loop == chrec_dont_know)
-	return true;
+	return t_true;
 
-      if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
-						    halting_phi,
-						    &evolution_of_branch,
-						    init))
-	return false;
+      res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
+						     halting_phi,
+						     &evolution_of_branch,
+						     init, limit);
+      if (res == t_false || res == t_dont_know)
+	return res;
 
       *evolution_of_loop = chrec_merge (*evolution_of_loop,
 					evolution_of_branch);
     }
   
-  return true;
+  return t_true;
 }
 
 /* Follow an SSA edge in an inner loop.  It computes the overall
@@ -1349,11 +1370,11 @@ follow_ssa_edge_in_condition_phi (struct loop *loop,
    it follows the edges in the parent loop.  The inner loop is
    considered as a single statement.  */
 
-static bool
+static t_bool
 follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
 				tree loop_phi_node, 
 				tree halting_phi,
-				tree *evolution_of_loop)
+				tree *evolution_of_loop, int limit)
 {
   struct loop *loop = loop_containing_stmt (loop_phi_node);
   tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
@@ -1362,7 +1383,7 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
      result of the analysis is a symbolic parameter.  */
   if (ev == PHI_RESULT (loop_phi_node))
     {
-      bool res = false;
+      t_bool res = t_false;
       int i;
 
       for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
@@ -1373,13 +1394,15 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
 	  /* Follow the edges that exit the inner loop.  */
 	  bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
 	  if (!flow_bb_inside_loop_p (loop, bb))
-	    res = res || follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
-						 arg, halting_phi,
-						 evolution_of_loop);
+	    res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
+					  arg, halting_phi,
+					  evolution_of_loop, limit);
+	  if (res == t_true)
+	    break;
 	}
 
       /* If the path crosses this loop-phi, give up.  */
-      if (res == true)
+      if (res == t_true)
 	*evolution_of_loop = chrec_dont_know;
 
       return res;
@@ -1388,22 +1411,24 @@ follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
   /* Otherwise, compute the overall effect of the inner loop.  */
   ev = compute_overall_effect_of_inner_loop (loop, ev);
   return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
-				 evolution_of_loop);
+				 evolution_of_loop, limit);
 }
 
 /* Follow an SSA edge from a loop-phi-node to itself, constructing a
    path that is analyzed on the return walk.  */
 
-static bool
-follow_ssa_edge (struct loop *loop, 
-		 tree def, 
-		 tree halting_phi,
-		 tree *evolution_of_loop)
+static t_bool
+follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
+		 tree *evolution_of_loop, int limit)
 {
   struct loop *def_loop;
   
   if (TREE_CODE (def) == NOP_EXPR)
-    return false;
+    return t_false;
+  
+  /* Give up if the path is longer than the MAX that we allow.  */
+  if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+    return t_dont_know;
   
   def_loop = loop_containing_stmt (def);
   
@@ -1416,39 +1441,39 @@ follow_ssa_edge (struct loop *loop,
 	   information and set the approximation to the main
 	   variable.  */
 	return follow_ssa_edge_in_condition_phi 
-	  (loop, def, halting_phi, evolution_of_loop);
+	  (loop, def, halting_phi, evolution_of_loop, limit);
 
       /* When the analyzed phi is the halting_phi, the
 	 depth-first search is over: we have found a path from
 	 the halting_phi to itself in the loop.  */
       if (def == halting_phi)
-	return true;
+	return t_true;
 	  
       /* Otherwise, the evolution of the HALTING_PHI depends
 	 on the evolution of another loop-phi-node, i.e. the
 	 evolution function is a higher degree polynomial.  */
       if (def_loop == loop)
-	return false;
+	return t_false;
 	  
       /* Inner loop.  */
       if (flow_loop_nested_p (loop, def_loop))
 	return follow_ssa_edge_inner_loop_phi 
-	  (loop, def, halting_phi, evolution_of_loop);
+	  (loop, def, halting_phi, evolution_of_loop, limit);
 
       /* Outer loop.  */
-      return false;
+      return t_false;
 
     case MODIFY_EXPR:
       return follow_ssa_edge_in_rhs (loop, def,
 				     TREE_OPERAND (def, 1), 
 				     halting_phi, 
-				     evolution_of_loop);
+				     evolution_of_loop, limit);
       
     default:
       /* At this level of abstraction, the program is just a set
 	 of MODIFY_EXPRs and PHI_NODEs.  In principle there is no
 	 other node to be handled.  */
-      return false;
+      return t_false;
     }
 }
 
@@ -1491,7 +1516,7 @@ analyze_evolution_in_loop (tree loop_phi_node,
 
 	  /* Pass in the initial condition to the follow edge function.  */
 	  ev_fn = init_cond;
-	  res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
+	  res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
 	}
       else
 	res = false;