Patch for bug 20742

[Sebastian Pop]

Hi, 

This is a possible solution for limiting the size of the expressions
we deal with in the scev analyzer.  As it is implemented in this
patch, the biggest expression that does not contain other chrecs is
10: i.e. on the testcase this corresponds to

b_13 + b_212 + b_15 + b_17 + b_19 + b_21 + b_23 + b_25 + b_27 + b_29

and after this it returns chrec_don_know.  Better solutions for
chosing this magic number are welcome.

I'm bootstrapping it on mainline and gcc-4.0 on amd64.

Sebastian

	* tree-chrec.c (chrec_fold_plus_1): Fail with a chrec_don_know
	when the size of the expression exceeds 20.
	(tree_contains_chrecs): Compute an estimation of the size of the
	given expression.
	* tree-chrec.h (tree_contains_chrecs): Modify its declaration.
	(tree_does_not_contain_chrecs): Update the use of tree_contains_chrecs.
	* tree-scalar-evolution.c (simple_iv): Ditto.

Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 2.14
diff -d -u -p -r2.14 tree-chrec.c
--- tree-chrec.c	5 Apr 2005 07:06:23 -0000	2.14
+++ tree-chrec.c	7 Apr 2005 07:19:08 -0000
@@ -286,11 +286,17 @@ chrec_fold_plus_1 (enum tree_code code, 
 				    build_int_cst_type (type, -1)));
 
 	default:
-	  if (tree_contains_chrecs (op0)
-	      || tree_contains_chrecs (op1))
-	    return build (code, type, op0, op1);
-	  else
-	    return fold (build (code, type, op0, op1));
+	  {
+	    int size = 0;
+	    if ((tree_contains_chrecs (op0, &size)
+		 || tree_contains_chrecs (op1, &size))
+		&& size < 20)
+	      return build (code, type, op0, op1);
+	    else if (size < 20)
+	      return fold (build (code, type, op0, op1));
+	    else
+	      return chrec_dont_know;
+	  }
 	}
     }
 }
@@ -862,29 +868,34 @@ chrec_contains_undetermined (tree chrec)
     }
 }
 
-/* Determines whether the tree EXPR contains chrecs.  */
+/* Determines whether the tree EXPR contains chrecs, and increment
+   SIZE if it is not a NULL pointer by an estimation of the depth of
+   the tree.  */
 
 bool
-tree_contains_chrecs (tree expr)
+tree_contains_chrecs (tree expr, int *size)
 {
   if (expr == NULL_TREE)
     return false;
+
+  if (size)
+    (*size)++;
   
   if (tree_is_chrec (expr))
     return true;
-  
+
   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
     {
     case 3:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 2)))
+      if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
 	return true;
       
     case 2:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 1)))
+      if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
 	return true;
       
     case 1:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 0)))
+      if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
 	return true;
       
     default:
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.h,v
retrieving revision 2.6
diff -d -u -p -r2.6 tree-chrec.h
--- tree-chrec.h	17 Nov 2004 22:06:00 -0000	2.6
+++ tree-chrec.h	7 Apr 2005 07:19:08 -0000
@@ -87,7 +87,7 @@ extern bool chrec_is_positive (tree, boo
 extern bool chrec_contains_symbols (tree);
 extern bool chrec_contains_symbols_defined_in_loop (tree, unsigned);
 extern bool chrec_contains_undetermined (tree);
-extern bool tree_contains_chrecs (tree);
+extern bool tree_contains_chrecs (tree, int *);
 extern bool evolution_function_is_affine_multivariate_p (tree);
 extern bool evolution_function_is_univariate_p (tree);
 extern unsigned nb_vars_in_chrec (tree);
@@ -183,7 +183,7 @@ evolution_function_is_affine_or_constant
 static inline bool
 tree_does_not_contain_chrecs (tree expr)
 {
-  return !tree_contains_chrecs (expr);
+  return !tree_contains_chrecs (expr, NULL);
 }
 
 /* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.  
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.18
diff -d -u -p -r2.18 tree-scalar-evolution.c
--- tree-scalar-evolution.c	30 Mar 2005 12:14:49 -0000	2.18
+++ tree-scalar-evolution.c	7 Apr 2005 07:19:09 -0000
@@ -2563,7 +2563,7 @@ simple_iv (struct loop *loop, tree stmt,
   if (TREE_CODE (*step) != INTEGER_CST)
     return false;
   *base = CHREC_LEFT (ev);
-  if (tree_contains_chrecs (*base)
+  if (tree_contains_chrecs (*base, NULL)
       || chrec_contains_symbols_defined_in_loop (*base, loop->num))
     return false;