[lno] Remove INTERVAL_CHREC nodes

Sebastian Pop sebastian.pop@cri.ensmp.fr
Tue Jun 22 17:18:00 GMT 2004


Hi, 

This patch removes the INTERVAL_CHREC nodes and cleans some of the
optimizers that misused the information provided by the analyzer.  As
a general rule, a user pass has to check for undetermined elements
before using the information.

The patch has been bootstrapped on i686.

Sebastian


Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.198
diff -d -u -p -r1.1.2.198 ChangeLog.lno
--- ChangeLog.lno	22 Jun 2004 07:06:02 -0000	1.1.2.198
+++ ChangeLog.lno	22 Jun 2004 14:05:29 -0000
@@ -1,3 +1,52 @@
+2004-06-22  Sebastian Pop  <pop@cri.ensmp.fr>
+
+	* tree-chrec.c, tree-chrec.h, tree-data-ref.c, tree-dg.c, 
+	tree-elim-check.c, tree-scalar-evolution.c, tree-ssa-loop-niter.c, 
+	tree-vectorizer.c: Replace chrec_top with chrec_dont_know, 
+	and chrec_bot with chrec_known.  Replace the checks of chrec_top 
+	with calls to chrec_contains_undetermined.
+	* tree.def (INTERVAL_CHREC): Removed.  
+	* cfgloop.h (loop): Update comments around nb_iterations field.  
+	* lambda-code.c (gcc_loop_to_lambda_loop): Always check for 
+	undetermined chrec after calling number_of_iterations_in_loop.
+	* tree-chrec.c (chrec_fold_multiply_ival_cst, chrec_fold_multiply_ival_ival, 
+	chrec_merge_types, chrec_contains_intervals, chrec_evaluate, 
+	chrec_merge_intervals): Removed.
+	(chrec_fold_plus_1, chrec_fold_plus, chrec_fold_minus, 
+	chrec_fold_multiply, chrec_merge, 
+	evolution_function_is_affine_multivariat, chrec_convert): 
+	Remove uses of INTERVAL_CHREC nodes.
+	(chrec_apply): Classify as unknown all the non-affine cases.
+	* tree-fold-const.h (tree_fold_binomial): Removed.
+	* tree-chrec.h (CHREC_LOW, CHREC_UP, 
+	chrec_contains_intervals, build_interval_chrec, 
+	build_chrec_top_type, evolution_function_is_multivariate, 
+	chrec_should_remain_symbolic): Removed.
+	(tree_is_chrec, chrec_zerop, evolution_function_is_affine_p): 
+	Remove uses of INTERVAL_CHREC nodes.
+	* tree-data-ref.c (analyze_ziv_subscript, 
+	analyze_overlapping_iterations): Same.
+	* tree-pretty-print.c (dump_generic_node): Same.
+	* tree-scalar-evolution.c (chrec_is_positive, 
+	instantiate_parameters_1, gather_chrec_stats, 
+	initialize_scalar_evolutions_analyzer): Same.
+	(analyze_scalar_evolution_in_loop): Make it static.
+	(resolve_mixers): Fix comments.
+	(chrec_stats, reset_chrecs_counters, dump_chrecs_stats):
+	Remove nb_interval_chrec counter.
+	(chrec_is_positive, simple_iv): Always check for undetermined after 
+	a call to number_of_iterations_in_loop or analyze_scalar_evolution.
+	* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables, 
+	canonicalize_loop_induction_variables): Same.
+	* tree-ssa-loop-ivopts.c (determine_biv_step): Same.
+	* tree-ssa-loop-niter.c (find_loop_niter_by_eval): Same.
+	(estimate_numbers_of_iterations_loop): Remove redundant call to 
+	number_of_iterations_in_loop.
+	* tree-scalar-evolution.h (analyze_scalar_evolution_in_loop): 
+	Remove declaration, the function is now static.
+	* tree-vectorizer.c (vect_analyze_loop_with_symbolic_num_of_iters):
+	Don't test for INTERVAL_CHREC nodes.
+
 2004-06-22  Devang Patel  <dpatel@apple.com>
 		
         PR 16105	
Index: cfgloop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.h,v
retrieving revision 1.2.4.9.2.18
diff -d -u -p -r1.2.4.9.2.18 cfgloop.h
--- cfgloop.h	14 Jun 2004 01:57:46 -0000	1.2.4.9.2.18
+++ cfgloop.h	22 Jun 2004 14:05:29 -0000
@@ -177,9 +177,10 @@ struct loop
   int exit_count;
 
   /* The probable number of times the loop is executed at runtime.
-     This is either an INTERVAL_CHREC or an INTEGER_CST.  Don't access
-     this field directly: number_of_iterations_in_loop computes and
-     caches the computed information in this field.  */
+     This is an INTEGER_CST or an expression containing symbolic
+     names.  Don't access this field directly:
+     number_of_iterations_in_loop computes and caches the computed
+     information in this field.  */
   tree nb_iterations;
 
   /* Upper bound on number of iterations of a loop.  */
Index: lambda-code.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/lambda-code.c,v
retrieving revision 1.1.2.10
diff -d -u -p -r1.1.2.10 lambda-code.c
--- lambda-code.c	17 Jun 2004 18:25:11 -0000	1.1.2.10
+++ lambda-code.c	22 Jun 2004 14:05:29 -0000
@@ -1135,6 +1135,8 @@ gcc_loop_to_lambda_loop (struct loop *lo
     return NULL;
   
   nb_iter = number_of_iterations_in_loop (loop);
+  if (chrec_contains_undetermined (nb_iter))
+    return NULL;
   nb_iter = chrec_fold_minus (chrec_type (nb_iter), nb_iter, 
 			      convert (chrec_type (nb_iter), integer_one_node));
   base = CHREC_LEFT (ev);
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.c,v
retrieving revision 1.1.2.26
diff -d -u -p -r1.1.2.26 tree-chrec.c
--- tree-chrec.c	21 Jun 2004 14:55:43 -0000	1.1.2.26
+++ tree-chrec.c	22 Jun 2004 14:05:29 -0000
@@ -84,7 +84,7 @@ chrec_fold_poly_cst (enum tree_code code
 	 chrec_fold_multiply (type, CHREC_RIGHT (poly), cst));
       
     default:
-      return chrec_top;
+      return chrec_dont_know;
     }
 }
 
@@ -163,44 +163,6 @@ chrec_fold_plus_poly_poly (enum tree_cod
 
 
 
-/* Fold the multiplication of an interval and a constant.  */
-
-static inline tree 
-chrec_fold_multiply_ival_cst (tree type, 
-			      tree ival, 
-			      tree cst)
-{
-  tree lowm, upm;
-
-#if defined ENABLE_CHECKING
-  if (ival == NULL_TREE
-      || cst == NULL_TREE
-      || TREE_CODE (ival) != INTERVAL_CHREC
-      || is_not_constant_evolution (cst))
-    abort ();
-#endif
- 
-  /* Don't modify abstract values.  */
-  if (ival == chrec_top)
-    return chrec_top;
-  if (ival == chrec_bot)
-    return chrec_bot;
-
-  lowm = chrec_fold_multiply (type, CHREC_LOW (ival), cst);
-  upm = chrec_fold_multiply (type, CHREC_UP (ival), cst);
-
-  /* When the fold resulted in an overflow, conservatively answer
-     chrec_top.  */
-  if (!evolution_function_is_constant_p (lowm)
-      || !evolution_function_is_constant_p (upm)
-      || TREE_OVERFLOW (lowm)
-      || TREE_OVERFLOW (upm))
-    return build_chrec_top_type (type);
-
-  return build_interval_chrec (tree_fold_min (type, lowm, upm),
-			       tree_fold_max (type, lowm, upm));
-}
-
 /* Fold the multiplication of two polynomial functions.  */
 
 static inline tree 
@@ -259,56 +221,6 @@ chrec_fold_multiply_poly_poly (tree type
       chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))));
 }
 
-/* Fold the multiplication of two intervals.  */
-
-static inline tree
-chrec_fold_multiply_ival_ival (tree type, 
-			       tree ival0,
-			       tree ival1)
-{
-  tree ac, ad, bc, bd;
-  
-#if defined ENABLE_CHECKING
-  if (ival0 == NULL_TREE
-      || ival1 == NULL_TREE
-      || TREE_CODE (ival0) != INTERVAL_CHREC
-      || TREE_CODE (ival1) != INTERVAL_CHREC)
-    abort ();
-#endif
-  
-  /* Don't modify abstract values.  */
-  if (automatically_generated_chrec_p (ival0)
-      || automatically_generated_chrec_p (ival1))
-    chrec_fold_automatically_generated_operands (ival0, ival1);
-  
-  ac = tree_fold_multiply (type, CHREC_LOW (ival0), CHREC_LOW (ival1));
-  ad = tree_fold_multiply (type, CHREC_LOW (ival0), CHREC_UP (ival1));
-  bc = tree_fold_multiply (type, CHREC_UP (ival0), CHREC_LOW (ival1));
-  bd = tree_fold_multiply (type, CHREC_UP (ival0), CHREC_UP (ival1));
-
-  /* When the fold resulted in an overflow, conservatively answer
-     chrec_top.  */
-  if (!evolution_function_is_constant_p (ac)
-      || !evolution_function_is_constant_p (ad)
-      || !evolution_function_is_constant_p (bc)
-      || !evolution_function_is_constant_p (bd)
-      || TREE_OVERFLOW (ac)
-      || TREE_OVERFLOW (ad)
-      || TREE_OVERFLOW (bc)
-      || TREE_OVERFLOW (bd))
-    return build_chrec_top_type (type);
-
-  /* [a, b] * [c, d]  ->  [min (ac, ad, bc, bd), max (ac, ad, bc, bd)],
-     for reference, see Moore's "Interval Arithmetic".  */
-  return build_interval_chrec 
-    (tree_fold_min 
-     (type, tree_fold_min
-      (type, tree_fold_min (type, ac, ad), bc), bd),
-     tree_fold_max
-     (type, tree_fold_max
-      (type, tree_fold_max (type, ac, ad), bc), bd));
-}
-
 /* When the operands are automatically_generated_chrec_p, the fold has
    to respect the semantics of the operands.  */
 
@@ -318,24 +230,24 @@ chrec_fold_automatically_generated_opera
 {
   /* TOP op x = TOP,
      x op TOP = TOP.  */
-  if (op0 == chrec_top
-      || op1 == chrec_top)
-    return chrec_top;
+  if (chrec_contains_undetermined (op0)
+      || chrec_contains_undetermined (op1))
+    return chrec_dont_know;
   
   /* BOT op TOP = TOP, 
      TOP op BOT = TOP, 
      BOT op x = BOT,
      x op BOT = BOT.  */
-  if (op0 == chrec_bot
-      || op1 == chrec_bot)
-    return chrec_bot;
+  if (op0 == chrec_known
+      || op1 == chrec_known)
+    return chrec_known;
   
   if (op0 == chrec_not_analyzed_yet
       || op1 == chrec_not_analyzed_yet)
     return chrec_not_analyzed_yet;
   
   /* The default case produces a safe result. */
-  return chrec_top;
+  return chrec_dont_know;
 }
 
 /* Fold the addition of two chrecs.  */
@@ -346,8 +258,6 @@ chrec_fold_plus_1 (enum tree_code code, 
 		   tree op0,
 		   tree op1)
 {
-  tree t1, t2;
-  
   if (automatically_generated_chrec_p (op0)
       || automatically_generated_chrec_p (op1))
     return chrec_fold_automatically_generated_operands (op0, op1);
@@ -373,58 +283,6 @@ chrec_fold_plus_1 (enum tree_code code, 
 	       CHREC_RIGHT (op0));
 	}
 
-    case INTERVAL_CHREC:
-      switch (TREE_CODE (op1))
-	{
-	case POLYNOMIAL_CHREC:
-	  return build_polynomial_chrec 
-	    (CHREC_VARIABLE (op1), 
-	     (code == PLUS_EXPR ? 
-	      chrec_fold_plus (type, op0, CHREC_LEFT (op1)) :
-	      chrec_fold_minus (type, op0, CHREC_LEFT (op1))),
-	     CHREC_RIGHT (op1));
-	  
-	case INTERVAL_CHREC:
-	  t1 = (code == PLUS_EXPR ? 
-		chrec_fold_plus (type, CHREC_LOW (op0), CHREC_LOW (op1)) :
-		chrec_fold_minus (type, CHREC_LOW (op0), CHREC_LOW (op1)));
-	  t2 = (code == PLUS_EXPR ? 
-		chrec_fold_plus (type, CHREC_UP (op0), CHREC_UP (op1)) :
-		chrec_fold_minus (type, CHREC_UP (op0), CHREC_UP (op1)));
-
-	  /* When the fold resulted in an overflow, conservatively answer
-	     chrec_top.  */
-	  if (!evolution_function_is_constant_p (t1)
-	      || !evolution_function_is_constant_p (t2)
-	      || TREE_OVERFLOW (t1)
-	      || TREE_OVERFLOW (t2))
-	    return build_chrec_top_type (type);
-
-	  return build_interval_chrec 
-	    (tree_fold_min (type, t1, t2),
-	     tree_fold_max (type, t1, t2));
-	  
-	default:
-	  t1 = (code == PLUS_EXPR ? 
-		chrec_fold_plus (type, CHREC_LOW (op0), op1) : 
-		chrec_fold_minus (type, CHREC_LOW (op0), op1));
-	  t2 = (code == PLUS_EXPR ? 
-		chrec_fold_plus (type, CHREC_UP (op0), op1) : 
-		chrec_fold_minus (type, CHREC_UP (op0), op1));
-	  
-	  /* When the fold resulted in an overflow, conservatively answer
-	     chrec_top.  */
-	  if (!evolution_function_is_constant_p (t1)
-	      || !evolution_function_is_constant_p (t2)
-	      || TREE_OVERFLOW (t1)
-	      || TREE_OVERFLOW (t2))
-	    return build_chrec_top_type (type);
-
-	  return build_interval_chrec 
-	    (tree_fold_min (type, t1, t2),
-	     tree_fold_max (type, t1, t2));
-	}
-      
     default:
       switch (TREE_CODE (op1))
 	{
@@ -442,26 +300,6 @@ chrec_fold_plus_1 (enum tree_code code, 
 				    convert (type,
 					     integer_minus_one_node)));
 
-	case INTERVAL_CHREC:
-	  t1 = (code == PLUS_EXPR ? 
-		chrec_fold_plus (type, op0, CHREC_LOW (op1)) : 
-		chrec_fold_minus (type, op0, CHREC_LOW (op1)));
-	  t2 = (code == PLUS_EXPR ? 
-		chrec_fold_plus (type, op0, CHREC_UP (op1)) :
-		chrec_fold_minus (type, op0, CHREC_UP (op1)));
-
-	  /* When the fold resulted in an overflow, conservatively answer
-	     chrec_top.  */
-	  if (!evolution_function_is_constant_p (t1)
-	      || !evolution_function_is_constant_p (t2)
-	      || TREE_OVERFLOW (t1)
-	      || TREE_OVERFLOW (t2))
-	    return build_chrec_top_type (type);
-
-	  return build_interval_chrec 
-	      (tree_fold_min (type, t1, t2),
-	       tree_fold_max (type, t1, t2));
-	  
 	default:
 	  if (tree_contains_chrecs (op0)
 	      || tree_contains_chrecs (op1))
@@ -479,15 +317,9 @@ chrec_fold_plus (tree type, 
 		 tree op0,
 		 tree op1)
 {
-  if (integer_zerop (op0)
-      || (TREE_CODE (op0) == INTERVAL_CHREC
-	  && integer_zerop (CHREC_LOW (op0))
-	  && integer_zerop (CHREC_UP (op0))))
+  if (integer_zerop (op0))
     return op1;
-  if (integer_zerop (op1)
-      || (TREE_CODE (op1) == INTERVAL_CHREC
-	  && integer_zerop (CHREC_LOW (op1))
-	  && integer_zerop (CHREC_UP (op1))))
+  if (integer_zerop (op1))
     return op0;
   
   return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
@@ -500,10 +332,7 @@ chrec_fold_minus (tree type, 
 		  tree op0, 
 		  tree op1)
 {
-  if (integer_zerop (op1)
-      || (TREE_CODE (op1) == INTERVAL_CHREC
-	  && integer_zerop (CHREC_LOW (op1))
-	  && integer_zerop (CHREC_UP (op1))))
+  if (integer_zerop (op1))
     return op0;
   
   return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1);
@@ -540,26 +369,6 @@ chrec_fold_multiply (tree type, 
 	     chrec_fold_multiply (type, CHREC_RIGHT (op0), op1));
 	}
       
-    case INTERVAL_CHREC:
-      switch (TREE_CODE (op1))
-	{
-	case POLYNOMIAL_CHREC:
-	  return build_polynomial_chrec 
-	    (CHREC_VARIABLE (op1), 
-	     chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
-	     chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
-	  
-	case INTERVAL_CHREC:
-	  return chrec_fold_multiply_ival_ival (type, op0, op1);
-	  
-	default:
-	  if (integer_onep (op1))
-	    return op0;
-	  if (integer_zerop (op1))
-	    return convert (type, integer_zero_node);
-	  return chrec_fold_multiply_ival_cst (type, op0, op1);
-	}
-      
     default:
       if (integer_onep (op0))
 	return op1;
@@ -575,9 +384,6 @@ chrec_fold_multiply (tree type, 
 	     chrec_fold_multiply (type, CHREC_LEFT (op1), op0),
 	     chrec_fold_multiply (type, CHREC_RIGHT (op1), op0));
 	  
-	case INTERVAL_CHREC:
-	  return chrec_fold_multiply_ival_cst (type, op1, op0);
-	  
 	default:
 	  if (integer_onep (op1))
 	    return op0;
@@ -592,45 +398,15 @@ chrec_fold_multiply (tree type, 
 
 /* Operations.  */
 
-/* Helper function.  Use the Newton's interpolating formula for
-   evaluating the value of the evolution function.  */
-
-static tree 
-chrec_evaluate (unsigned var,
-		tree chrec,
-		tree n,
-		tree k)
-{
-  tree type = chrec_type (chrec);
-  tree binomial_n_k = tree_fold_binomial (n, k);
-  
-  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
-    {
-      if (CHREC_VARIABLE (chrec) > var)
-	return chrec_evaluate (var, CHREC_LEFT (chrec), n, k);
-      
-      if (CHREC_VARIABLE (chrec) == var)
-	return chrec_fold_plus 
-	  (type, 
-	   chrec_fold_multiply (type, binomial_n_k, CHREC_LEFT (chrec)),
-	   chrec_evaluate (var, CHREC_RIGHT (chrec), n, 
-			   tree_fold_plus (type, k, integer_one_node)));
-      
-      return chrec_fold_multiply (type, binomial_n_k, chrec);
-    }
-  else
-    return chrec_fold_multiply (type, binomial_n_k, chrec);
-}
-
 /* Evaluates "CHREC (X)" when the varying variable is VAR.  
    Example:  Given the following parameters, 
    
    var = 1
-   chrec = {5, +, {3, +, 4}_1}_1
+   chrec = {3, +, 4}_1
    x = 10
    
    The result is given by the Newton's interpolating formula: 
-   5 * \binom{10}{0} + 3 * \binom{10}{1} + 4 * \binom{10}{2}.
+   3 * \binom{10}{0} + 4 * \binom{10}{1}.
 */
 
 tree 
@@ -639,7 +415,7 @@ chrec_apply (unsigned var,
 	     tree x)
 {
   tree type = chrec_type (chrec);
-  tree res = chrec_top;
+  tree res = chrec_dont_know;
 
   if (automatically_generated_chrec_p (chrec)
       || automatically_generated_chrec_p (x)
@@ -649,7 +425,7 @@ chrec_apply (unsigned var,
 	 constants with respect to the varying loop.  */
       || chrec_contains_symbols_defined_in_loop (chrec, var)
       || chrec_contains_symbols (x))
-    return chrec_top;
+    return chrec_dont_know;
   
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "(chrec_apply \n");
@@ -667,16 +443,8 @@ chrec_apply (unsigned var,
 						    CHREC_RIGHT (chrec), x));
     }
   
-  else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
-    res = chrec;
-  
-  else if (TREE_CODE (x) == INTEGER_CST
-	   && tree_int_cst_sgn (x) == 1)
-    /* testsuite/.../ssa-chrec-38.c.  */
-    res = chrec_evaluate (var, chrec, x, integer_zero_node);
-  
   else
-    res = chrec_top;
+    res = chrec_dont_know;
   
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -829,7 +597,7 @@ evolution_part_in_loop_num (tree chrec, 
 
 /* Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
    This function is essentially used for setting the evolution to
-   chrec_top, for example after having determined that it is
+   chrec_dont_know, for example after having determined that it is
    impossible to say how many times a loop will execute.  */
 
 tree 
@@ -867,44 +635,6 @@ chrec_merge_types (tree type0, 
     return NULL_TREE;
 }
 
-/* Merge the information contained in intervals or scalar constants. 
-   merge ([a, b], [c, d])  ->  [min (a, c), max (b, d)],
-   merge ([a, b], c)       ->  [min (a, c), max (b, c)],
-   merge (a, [b, c])       ->  [min (a, b), max (a, c)],
-   merge (a, b)            ->  [min (a, b), max (a, b)].  */
-
-static inline tree 
-chrec_merge_intervals (tree chrec1, 
-		       tree chrec2)
-{
-  tree type1 = chrec_type (chrec1);
-  tree type2 = chrec_type (chrec2);
-  tree type = chrec_merge_types (type1, type2);
-  
-  if (type == NULL_TREE)
-    return chrec_top;
-  
-  if (TREE_CODE (chrec1) == INTERVAL_CHREC)
-    {
-      if (TREE_CODE (chrec2) == INTERVAL_CHREC)
-	return build_interval_chrec 
-	  (tree_fold_min (type, CHREC_LOW (chrec1), CHREC_LOW (chrec2)),
-	   tree_fold_max (type, CHREC_UP (chrec1), CHREC_UP (chrec2)));
-      else
-	return build_interval_chrec 
-	  (tree_fold_min (type, CHREC_LOW (chrec1), chrec2),
-	   tree_fold_max (type, CHREC_UP (chrec1), chrec2));
-    }
-  else if (TREE_CODE (chrec2) == INTERVAL_CHREC)
-    return build_interval_chrec 
-      (tree_fold_min (type, CHREC_LOW (chrec2), chrec1),
-       tree_fold_max (type, CHREC_UP (chrec2), chrec1));
-  else
-    return build_interval_chrec 
-      (tree_fold_min (type, chrec1, chrec2),
-       tree_fold_max (type, chrec1, chrec2));
-}
-
 /* Merges two evolution functions that were found by following two
    alternate paths of a conditional expression.  */
 
@@ -912,15 +642,13 @@ tree
 chrec_merge (tree chrec1, 
 	     tree chrec2)
 {
-  tree type = chrec_type (chrec1);
-
-  if (chrec1 == chrec_top
-      || chrec2 == chrec_top)
-    return chrec_top;
+  if (chrec_contains_undetermined (chrec1)
+      || chrec_contains_undetermined (chrec2))
+    return chrec_dont_know;
 
-  if (chrec1 == chrec_bot 
-      || chrec2 == chrec_bot)
-    return chrec_bot;
+  if (chrec1 == chrec_known 
+      || chrec2 == chrec_known)
+    return chrec_known;
 
   if (chrec1 == chrec_not_analyzed_yet)
     return chrec2;
@@ -930,64 +658,7 @@ chrec_merge (tree chrec1, 
   if (operand_equal_p (chrec1, chrec2, 0))
     return chrec1;
 
-  switch (TREE_CODE (chrec1))
-    {
-    case INTEGER_CST:
-    case INTERVAL_CHREC:
-      switch (TREE_CODE (chrec2))
-	{
-	case INTEGER_CST:
-	case INTERVAL_CHREC:
-	  return chrec_merge_intervals (chrec1, chrec2);
-	  
-	case POLYNOMIAL_CHREC:
-	  return build_polynomial_chrec 
-	    (CHREC_VARIABLE (chrec2),
-	     chrec_merge (chrec1, CHREC_LEFT (chrec2)),
-	     chrec_merge (convert (type, integer_zero_node),
-			  CHREC_RIGHT (chrec2)));
-	  
-	default:
-	  return chrec_top;
-	}
-      
-    case POLYNOMIAL_CHREC:
-      switch (TREE_CODE (chrec2))
-	{
-	case INTEGER_CST:
-	case INTERVAL_CHREC:
-	  return build_polynomial_chrec 
-	    (CHREC_VARIABLE (chrec1),
-	     chrec_merge (CHREC_LEFT (chrec1), chrec2),
-	     chrec_merge (CHREC_RIGHT (chrec1),
-			  convert (type, integer_zero_node)));
-	  
-	case POLYNOMIAL_CHREC:
-	  if (CHREC_VARIABLE (chrec1) == CHREC_VARIABLE (chrec2))
-	    return build_polynomial_chrec 
-	      (CHREC_VARIABLE (chrec2),
-	       chrec_merge (CHREC_LEFT (chrec1), CHREC_LEFT (chrec2)),
-	       chrec_merge (CHREC_RIGHT (chrec1), CHREC_RIGHT (chrec2)));
-	  else if (CHREC_VARIABLE (chrec1) < CHREC_VARIABLE (chrec2))
-	    return build_polynomial_chrec 
-	      (CHREC_VARIABLE (chrec2),
-	       chrec_merge (chrec1, CHREC_LEFT (chrec2)),
-	       chrec_merge (convert (type, integer_zero_node),
-			    CHREC_RIGHT (chrec2)));
-	  else
-	    return build_polynomial_chrec 
-	      (CHREC_VARIABLE (chrec1),
-	       chrec_merge (CHREC_LEFT (chrec1), chrec2),
-	       chrec_merge (CHREC_RIGHT (chrec1),
-			    convert (type, integer_zero_node)));
-	  
-	default:
-	  return chrec_top;
-	}
-      
-    default:
-      return chrec_top;
-    }
+  return chrec_dont_know;
 }
 
 
@@ -1072,7 +743,7 @@ chrec_contains_symbols (tree chrec)
 bool 
 chrec_contains_undetermined (tree chrec)
 {
-  if (chrec == chrec_top
+  if (chrec == chrec_dont_know
       || chrec == chrec_not_analyzed_yet
       || chrec == NULL_TREE)
     return true;
@@ -1096,37 +767,6 @@ chrec_contains_undetermined (tree chrec)
     }
 }
 
-/* Determines whether the chrec contains interval coefficients.  */
-
-bool 
-chrec_contains_intervals (tree chrec)
-{
-  if (chrec == NULL_TREE
-      || automatically_generated_chrec_p (chrec))
-    return false;
-  
-  if (TREE_CODE (chrec) == INTERVAL_CHREC)
-    return true;
-  
-  switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
-    {
-    case 3:
-      if (chrec_contains_intervals (TREE_OPERAND (chrec, 2)))
-	return true;
-      
-    case 2:
-      if (chrec_contains_intervals (TREE_OPERAND (chrec, 1)))
-	return true;
-      
-    case 1:
-      if (chrec_contains_intervals (TREE_OPERAND (chrec, 0)))
-	return true;
-      
-    default:
-      return false;
-    }
-}
-
 /* Determines whether the tree EXPR contains chrecs.  */
 
 bool
@@ -1197,7 +837,6 @@ evolution_function_is_affine_multivariat
 	    return false;
 	}
       
-    case INTERVAL_CHREC:
     default:
       return false;
     }
@@ -1260,6 +899,8 @@ chrec_convert (tree type, 
     return chrec;
   
   ct = chrec_type (chrec);
+  if (ct == NULL_TREE)
+    return chrec_dont_know;
   if (ct == type)
     return chrec;
 
@@ -1275,11 +916,6 @@ chrec_convert (tree type, 
 				     chrec_convert (type,
 						    CHREC_RIGHT (chrec)));
 
-    case INTERVAL_CHREC:
-      return build_interval_chrec
-	(chrec_convert (type, CHREC_LOW (chrec)), 
-	 chrec_convert (type, CHREC_UP (chrec)));
-      
     default:
       {
 	tree res = convert (type, chrec);
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-chrec.h,v
retrieving revision 1.1.2.23
diff -d -u -p -r1.1.2.23 tree-chrec.h
--- tree-chrec.h	21 Jun 2004 14:55:43 -0000	1.1.2.23
+++ tree-chrec.h	22 Jun 2004 14:05:29 -0000
@@ -27,8 +27,6 @@ Software Foundation, 59 Temple Place - S
 #define CHREC_LEFT(NODE)          TREE_OPERAND (NODE, 1)
 #define CHREC_RIGHT(NODE)         TREE_OPERAND (NODE, 2)
 #define CHREC_VARIABLE(NODE)      TREE_INT_CST_LOW (CHREC_VAR (NODE))
-#define CHREC_LOW(NODE)           TREE_OPERAND (INTERVAL_CHREC_CHECK (NODE), 0)
-#define CHREC_UP(NODE)            TREE_OPERAND (INTERVAL_CHREC_CHECK (NODE), 1)
 
 
 
@@ -37,8 +35,8 @@ Software Foundation, 59 Temple Place - S
    and not on their value.  */
 
 extern tree chrec_not_analyzed_yet;
-extern GTY(()) tree chrec_top;
-extern GTY(()) tree chrec_bot;
+extern GTY(()) tree chrec_dont_know;
+extern GTY(()) tree chrec_known;
 
 /* After having added an automatically generated element, please
    include it in the following function.  */
@@ -47,8 +45,8 @@ static inline bool
 automatically_generated_chrec_p (tree chrec)
 {
   return (chrec == chrec_not_analyzed_yet 
-	  || chrec == chrec_top
-	  || chrec == chrec_bot);
+	  || chrec == chrec_dont_know
+	  || chrec == chrec_known);
 }
 
 /* The tree nodes aka. CHRECs.  */
@@ -56,8 +54,8 @@ automatically_generated_chrec_p (tree ch
 static inline bool
 tree_is_chrec (tree expr)
 {
-  if (TREE_CODE (expr) == INTERVAL_CHREC
-      || TREE_CODE (expr) == POLYNOMIAL_CHREC)
+  if (TREE_CODE (expr) == POLYNOMIAL_CHREC
+      || automatically_generated_chrec_p (expr))
     return true;
   else
     return false;
@@ -91,31 +89,12 @@ 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 chrec_contains_intervals (tree);
 extern bool tree_contains_chrecs (tree);
 extern bool evolution_function_is_affine_multivariate_p (tree);
 extern bool evolution_function_is_univariate_p (tree);
 
 
 
-/* Constructors.  */
-
-/* Build an interval.  */
-
-static inline tree 
-build_interval_chrec (tree low, 
-		      tree up)
-{
-  if (automatically_generated_chrec_p (low)
-      || automatically_generated_chrec_p (up))
-    return chrec_fold_automatically_generated_operands (low, up);
-  
-  if (integer_zerop (tree_fold_minus (chrec_type (low), up, low)))
-    return low;
-  else
-    return build (INTERVAL_CHREC, TREE_TYPE (low), low, up);
-}
-
 /* Build a polynomial chain of recurrence.  */
 
 static inline tree 
@@ -127,33 +106,6 @@ build_polynomial_chrec (unsigned loop_nu
 		build_int_2 (loop_num, 0), left, right);
 }
 
-/* Build a chrec top interval for type.  */
-
-static inline tree 
-build_chrec_top_type (tree type)
-{
-  /* Disabled for now: it is not used, and libjava fails to build on
-     amd64.  */
-  return chrec_top;
-
-  if (type != NULL_TREE)
-    {
-      enum tree_code code = TREE_CODE (type);
- 
-      if ((code == INTEGER_TYPE
-	   || code == ENUMERAL_TYPE
-	   || code == BOOLEAN_TYPE
-	   || code == CHAR_TYPE
-	   || code == REAL_TYPE)
-	  && TYPE_MIN_VALUE (type) != NULL_TREE 
-	  && TYPE_MAX_VALUE (type) != NULL_TREE)
-	return build_interval_chrec (TYPE_MIN_VALUE (type), 
-				     TYPE_MAX_VALUE (type));
-    }
-
-  return chrec_top;
-}
-
 
 
 /* Observers.  */
@@ -169,10 +121,6 @@ chrec_zerop (tree chrec)
   if (TREE_CODE (chrec) == INTEGER_CST)
     return integer_zerop (chrec);
   
-  if (TREE_CODE (chrec) == INTERVAL_CHREC)
-    return (integer_zerop (CHREC_LOW (chrec))
-	    && integer_zerop (CHREC_UP (chrec)));
-  
   return false;
 }
 
@@ -212,7 +160,6 @@ evolution_function_is_affine_p (tree chr
       else
 	return false;
       
-    case INTERVAL_CHREC:
     default:
       return false;
     }
@@ -228,27 +175,6 @@ evolution_function_is_affine_or_constant
     || evolution_function_is_constant_p (chrec);
 }
 
-/* Determine whether the given tree is a multivariate evolution.  */
-
-static inline bool
-evolution_function_is_multivariate (tree chrec)
-{
-  return !evolution_function_is_univariate_p (chrec);
-}
-
-/* Determines which expressions are simpler to be {handled | kept} in a 
-   symbolic form.  */
-
-static inline bool
-chrec_should_remain_symbolic (tree evfun)
-{
-  if (evfun == NULL_TREE
-      || evfun == chrec_top)
-    return true;
-  
-  return false;
-}
-
 /* Determines whether EXPR does not contains chrec expressions.  */
 
 static inline bool
@@ -266,7 +192,7 @@ no_evolution_in_loop_p (tree chrec, unsi
   tree scev;
   
   if (chrec == chrec_not_analyzed_yet
-      || chrec == chrec_top
+      || chrec == chrec_dont_know
       || chrec_contains_symbols_defined_in_loop (chrec, loop_num))
     return false;
 
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-data-ref.c,v
retrieving revision 1.1.2.21
diff -d -u -p -r1.1.2.21 tree-data-ref.c
--- tree-data-ref.c	14 Jun 2004 12:55:47 -0000	1.1.2.21
+++ tree-data-ref.c	22 Jun 2004 14:05:29 -0000
@@ -36,7 +36,7 @@ Software Foundation, 59 Temple Place - S
    The goals of this analysis are:
    
    - to determine the independence: the relation between two
-     independent accesses is qualified with the chrec_bot (this
+     independent accesses is qualified with the chrec_known (this
      information allows a loop parallelization),
      
    - when two data references access the same data, to qualify the
@@ -167,10 +167,10 @@ dump_data_dependence_relation (FILE *out
   
   fprintf (outf, "(Data Dep (A = %d, B = %d):", DR_ID (dra), DR_ID (drb));  
 
-  if (DDR_ARE_DEPENDENT (ddr) == chrec_top)
+  if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
     fprintf (outf, "    (don't know)\n");
   
-  else if (DDR_ARE_DEPENDENT (ddr) == chrec_bot)
+  else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
     fprintf (outf, "    (no dependence)\n");
   
   else
@@ -189,9 +189,9 @@ dump_data_dependence_relation (FILE *out
 	  chrec = SUB_CONFLICTS_IN_A (subscript);
 	  fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
 	  print_generic_stmt (outf, chrec, 0);
-	  if (chrec == chrec_bot)
+	  if (chrec == chrec_known)
 	    fprintf (outf, "    (no dependence)\n");
-	  else if (chrec == chrec_top)
+	  else if (chrec_contains_undetermined (chrec))
 	    fprintf (outf, "    (don't know)\n");
 	  else
 	    {
@@ -203,9 +203,9 @@ dump_data_dependence_relation (FILE *out
 	  chrec = SUB_CONFLICTS_IN_B (subscript);
 	  fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
 	  print_generic_stmt (outf, chrec, 0);
-	  if (chrec == chrec_bot)
+	  if (chrec == chrec_known)
 	    fprintf (outf, "    (no dependence)\n");
-	  else if (chrec == chrec_top)
+	  else if (chrec_contains_undetermined (chrec))
 	    fprintf (outf, "    (don't know)\n");
 	  else
 	    {
@@ -399,7 +399,7 @@ analyze_array_top (tree stmt)
   DR_BASE_NAME (res) = NULL_TREE;
 
   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 1, "access_fns");
-  VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), chrec_top);
+  VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), chrec_dont_know);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, ")\n");
@@ -434,7 +434,7 @@ compute_distance_vector (struct data_dep
  	    SUB_DISTANCE (subscript) = difference;
  	  
  	  else
- 	    SUB_DISTANCE (subscript) = chrec_top;
+ 	    SUB_DISTANCE (subscript) = chrec_dont_know;
  	}
     }
 }
@@ -453,13 +453,13 @@ initialize_data_dependence_relation (str
 
   if (DR_BASE_NAME (a) == NULL_TREE
       || DR_BASE_NAME (b) == NULL_TREE)
-    DDR_ARE_DEPENDENT (res) = chrec_top;    
+    DDR_ARE_DEPENDENT (res) = chrec_dont_know;    
 
   /* When the dimensions of A and B differ, we directly initialize
-     the relation to "there is no dependence": chrec_bot.  */
+     the relation to "there is no dependence": chrec_known.  */
   else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
 	   || array_base_name_differ_p (a, b))
-    DDR_ARE_DEPENDENT (res) = chrec_bot;
+    DDR_ARE_DEPENDENT (res) = chrec_known;
   
   else
     {
@@ -472,11 +472,11 @@ initialize_data_dependence_relation (str
 	  struct subscript *subscript;
 	  
 	  subscript = ggc_alloc (sizeof (struct subscript));
-	  SUB_CONFLICTS_IN_A (subscript) = chrec_top;
-	  SUB_CONFLICTS_IN_B (subscript) = chrec_top;
-	  SUB_LAST_CONFLICT_IN_A (subscript) = chrec_top;
-	  SUB_LAST_CONFLICT_IN_B (subscript) = chrec_top;
-	  SUB_DISTANCE (subscript) = chrec_top;
+	  SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
+	  SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
+	  SUB_LAST_CONFLICT_IN_A (subscript) = chrec_dont_know;
+	  SUB_LAST_CONFLICT_IN_B (subscript) = chrec_dont_know;
+	  SUB_DISTANCE (subscript) = chrec_dont_know;
 	  SUB_DIRECTION (subscript) = dir_star;
 	  VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
 	}
@@ -577,34 +577,16 @@ analyze_ziv_subscript (tree chrec_a, 
       else
 	{
 	  /* The accesses do not overlap.  */
-	  *overlaps_a = chrec_bot;
-	  *overlaps_b = chrec_bot;	  
-	}
-      break;
-      
-    case INTERVAL_CHREC:
-      if (integer_zerop (CHREC_LOW (difference)) 
-	  && integer_zerop (CHREC_UP (difference)))
-	{
-	  /* The difference is equal to zero: the accessed index 
-	     overlaps for each iteration in the loop.  */
-	  *overlaps_a = integer_zero_node;
-	  *overlaps_b = integer_zero_node;
-	}
-      else 
-	{
-	  /* There could be an overlap, conservative answer: 
-	     "don't know".  */
-	  *overlaps_a = chrec_top;
-	  *overlaps_b = chrec_top;	  
+	  *overlaps_a = chrec_known;
+	  *overlaps_b = chrec_known;	  
 	}
       break;
       
     default:
       /* We're not sure whether the indexes overlap.  For the moment, 
 	 conservatively answer "don't know".  */
-      *overlaps_a = chrec_top;
-      *overlaps_b = chrec_top;	  
+      *overlaps_a = chrec_dont_know;
+      *overlaps_b = chrec_dont_know;	  
       break;
     }
   
@@ -627,8 +609,8 @@ analyze_siv_subscript_cst_affine (tree c
   
   if (!chrec_is_positive (initial_condition (difference), &value0))
     {
-      *overlaps_a = chrec_top;
-      *overlaps_b = chrec_top;
+      *overlaps_a = chrec_dont_know;
+      *overlaps_b = chrec_dont_know;
       return;
     }
   else
@@ -637,8 +619,8 @@ analyze_siv_subscript_cst_affine (tree c
 	{
 	  if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
 	    {
-	      *overlaps_a = chrec_top;
-	      *overlaps_b = chrec_top;      
+	      *overlaps_a = chrec_dont_know;
+	      *overlaps_b = chrec_dont_know;      
 	      return;
 	    }
 	  else
@@ -665,8 +647,8 @@ analyze_siv_subscript_cst_affine (tree c
 		     no overlaps.  */
 		  else
 		    {
-		      *overlaps_a = chrec_bot;
-		      *overlaps_b = chrec_bot;      
+		      *overlaps_a = chrec_known;
+		      *overlaps_b = chrec_known;      
 		      return;
 		    }
 		}
@@ -678,8 +660,8 @@ analyze_siv_subscript_cst_affine (tree c
 		     chrec_b = {10, +, -1}
 		     
 		     In this case, chrec_a will not overlap with chrec_b.  */
-		  *overlaps_a = chrec_bot;
-		  *overlaps_b = chrec_bot;
+		  *overlaps_a = chrec_known;
+		  *overlaps_b = chrec_known;
 		  return;
 		}
 	    }
@@ -688,8 +670,8 @@ analyze_siv_subscript_cst_affine (tree c
 	{
 	  if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
 	    {
-	      *overlaps_a = chrec_top;
-	      *overlaps_b = chrec_top;      
+	      *overlaps_a = chrec_dont_know;
+	      *overlaps_b = chrec_dont_know;      
 	      return;
 	    }
 	  else
@@ -713,8 +695,8 @@ analyze_siv_subscript_cst_affine (tree c
 		     are no overlaps.  */
 		  else
 		    {
-		      *overlaps_a = chrec_bot;
-		      *overlaps_b = chrec_bot;      
+		      *overlaps_a = chrec_known;
+		      *overlaps_b = chrec_known;      
 		      return;
 		    }
 		}
@@ -725,8 +707,8 @@ analyze_siv_subscript_cst_affine (tree c
 		     chrec_b = {4, +, 1}
 		 
 		     In this case, chrec_a will not overlap with chrec_b.  */
-		  *overlaps_a = chrec_bot;
-		  *overlaps_b = chrec_bot;
+		  *overlaps_a = chrec_known;
+		  *overlaps_b = chrec_known;
 		  return;
 		}
 	    }
@@ -858,8 +840,8 @@ analyze_subscript_affine_affine (tree ch
 	{
 	  /* The "gcd-test" has determined that there is no integer
 	     solution, ie. there is no dependence.  */
-	  *overlaps_a = chrec_bot;
-	  *overlaps_b = chrec_bot;
+	  *overlaps_a = chrec_known;
+	  *overlaps_b = chrec_known;
 	}
       
       else
@@ -907,8 +889,8 @@ analyze_subscript_affine_affine (tree ch
 		 FIXME: The case "i0 > nb_iterations, j0 > nb_iterations" 
 		 falls in here, but for the moment we don't look at the 
 		 upper bound of the iteration domain.  */
-	      *overlaps_a = chrec_bot;
-	      *overlaps_b = chrec_bot;
+	      *overlaps_a = chrec_known;
+	      *overlaps_b = chrec_known;
   	    }
 	  
 	  else 
@@ -947,8 +929,8 @@ analyze_subscript_affine_affine (tree ch
 		    {
 		      /* FIXME: For the moment, the upper bound of the
 			 iteration domain for j is not checked. */
-		      *overlaps_a = chrec_top;
-		      *overlaps_b = chrec_top;
+		      *overlaps_a = chrec_dont_know;
+		      *overlaps_b = chrec_dont_know;
 		    }
 		}
 	      
@@ -956,8 +938,8 @@ analyze_subscript_affine_affine (tree ch
 		{
 		  /* FIXME: For the moment, the upper bound of the
 		     iteration domain for i is not checked. */
-		  *overlaps_a = chrec_top;
-		  *overlaps_b = chrec_top;
+		  *overlaps_a = chrec_dont_know;
+		  *overlaps_b = chrec_dont_know;
 		}
 	    }
 	}
@@ -966,8 +948,8 @@ analyze_subscript_affine_affine (tree ch
   else
     {
       /* For the moment, "don't know".  */
-      *overlaps_a = chrec_top;
-      *overlaps_b = chrec_top;
+      *overlaps_a = chrec_dont_know;
+      *overlaps_b = chrec_dont_know;
     }
   
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1014,8 +996,8 @@ analyze_siv_subscript (tree chrec_a, 
 				     overlaps_a, overlaps_b);
   else
     {
-      *overlaps_a = chrec_top;
-      *overlaps_b = chrec_top;
+      *overlaps_a = chrec_dont_know;
+      *overlaps_b = chrec_dont_know;
     }
   
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1082,8 +1064,8 @@ analyze_miv_subscript (tree chrec_a, 
         
 	 The difference is 1, and the evolution steps are equal to 2,
 	 consequently there are no overlapping elements.  */
-      *overlaps_a = chrec_bot;
-      *overlaps_b = chrec_bot;
+      *overlaps_a = chrec_known;
+      *overlaps_b = chrec_known;
     }
   
   else if (evolution_function_is_univariate_p (chrec_a)
@@ -1100,16 +1082,16 @@ analyze_miv_subscript (tree chrec_a, 
 					 overlaps_a, overlaps_b);
       else
 	{
-	  *overlaps_a = chrec_top;
-	  *overlaps_b = chrec_top;
+	  *overlaps_a = chrec_dont_know;
+	  *overlaps_b = chrec_dont_know;
 	}
     }
   
   else
     {
       /* When the analysis is too difficult, answer "don't know".  */
-      *overlaps_a = chrec_top;
-      *overlaps_b = chrec_top;
+      *overlaps_a = chrec_dont_know;
+      *overlaps_b = chrec_dont_know;
     }
   
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1146,12 +1128,10 @@ analyze_overlapping_iterations (tree chr
       || chrec_contains_undetermined (chrec_a)
       || chrec_contains_undetermined (chrec_b)
       || chrec_contains_symbols (chrec_a)
-      || chrec_contains_symbols (chrec_b)
-      || chrec_contains_intervals (chrec_a)
-      || chrec_contains_intervals (chrec_b))
+      || chrec_contains_symbols (chrec_b))
     {
-      *overlap_iterations_a = chrec_top;
-      *overlap_iterations_b = chrec_top;
+      *overlap_iterations_a = chrec_dont_know;
+      *overlap_iterations_b = chrec_dont_know;
     }
   
   else if (ziv_subscript_p (chrec_a, chrec_b))
@@ -1202,17 +1182,17 @@ subscript_dependence_tester (struct data
 				      DR_ACCESS_FN (drb, i),
 				      &overlaps_a, &overlaps_b);
       
-      if (overlaps_a == chrec_top
- 	  || overlaps_b == chrec_top)
+      if (chrec_contains_undetermined (overlaps_a)
+ 	  || chrec_contains_undetermined (overlaps_b))
  	{
- 	  finalize_ddr_dependent (ddr, chrec_top);
+ 	  finalize_ddr_dependent (ddr, chrec_dont_know);
 	  break;
  	}
       
-      else if (overlaps_a == chrec_bot
- 	       || overlaps_b == chrec_bot)
+      else if (overlaps_a == chrec_known
+ 	       || overlaps_b == chrec_known)
  	{
- 	  finalize_ddr_dependent (ddr, chrec_bot);
+ 	  finalize_ddr_dependent (ddr, chrec_known);
  	  break;
  	}
       
@@ -1249,7 +1229,7 @@ build_classic_dist_vector (struct data_d
     {
       struct subscript *subscript = DDR_SUBSCRIPT (res, i);
 
-      if (SUB_DISTANCE (subscript) == chrec_top)
+      if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	return;
 
       if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC)
@@ -1268,7 +1248,7 @@ build_classic_dist_vector (struct data_d
 	  if (init_v[loop_nb] != 0
 	      && dist_v[loop_nb] != dist)
 	    {
-	      finalize_ddr_dependent (res, chrec_bot);
+	      finalize_ddr_dependent (res, chrec_known);
 	      return;
 	    }
 
@@ -1343,7 +1323,7 @@ build_classic_dir_vector (struct data_de
 	  unsigned loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
 	  enum data_dependence_direction dir = dir_star;
 	  
-	  if (SUB_DISTANCE (subscript) == chrec_top)
+	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	    {
 	      
 	    }
@@ -1370,7 +1350,7 @@ build_classic_dir_vector (struct data_de
 	      && (enum data_dependence_direction) dir_v[loop_nb] != dir
 	      && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
 	    {
-	      finalize_ddr_dependent (res, chrec_bot);
+	      finalize_ddr_dependent (res, chrec_known);
 	      return;
 	    }
 	  
@@ -1435,12 +1415,12 @@ access_functions_are_affine_or_constant_
 }
 
 /* This computes the affine dependence relation between A and B.
-   CHREC_BOT is used for representing the independence between two
-   accesses, while CHREC_TOP is used for representing the unknown
+   CHREC_KNOWN is used for representing the independence between two
+   accesses, while CHREC_DONT_KNOW is used for representing the unknown
    relation.
    
    Note that it is possible to stop the computation of the dependence
-   relation the first time we detect a CHREC_BOT element for a given
+   relation the first time we detect a CHREC_KNOWN element for a given
    subscript.  */
 
 static void
@@ -1471,7 +1451,7 @@ compute_affine_dependence (struct data_d
 	 the dependence is considered too difficult to determine, answer
 	 "don't know".  */
       else
-	finalize_ddr_dependent (ddr, chrec_top);
+	finalize_ddr_dependent (ddr, chrec_dont_know);
     }
   
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1681,10 +1661,10 @@ analyze_all_data_dependences (struct loo
 	  struct data_dependence_relation *ddr;
 	  ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
 	  
-	  if (DDR_ARE_DEPENDENT (ddr) == chrec_top)
+	  if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
 	    nb_top_relations++;
 	  
-	  else if (DDR_ARE_DEPENDENT (ddr) == chrec_bot)
+	  else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 	    {
 	      struct data_reference *a = DDR_A (ddr);
 	      struct data_reference *b = DDR_B (ddr);
Index: tree-dg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dg.c,v
retrieving revision 1.1.2.10
diff -d -u -p -r1.1.2.10 tree-dg.c
--- tree-dg.c	13 Jun 2004 20:58:19 -0000	1.1.2.10
+++ tree-dg.c	22 Jun 2004 14:05:29 -0000
@@ -119,7 +119,7 @@ void dg_create_graph (struct loops *loop
       ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
 
       /* If there is no dependence than do not create an edge.  */
-      if (DDR_ARE_DEPENDENT (ddr) == chrec_bot)
+      if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 	continue;
 
       /* Get dependence references */
@@ -486,7 +486,7 @@ ddg_direction_between_stmts (tree stmt1,
   if (!ddr)
     return dir_independent;
 
-  if (DDR_ARE_DEPENDENT (ddr) == chrec_top)
+  if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
     return dir_star;
 
   /* Get subscript info.  */
@@ -561,10 +561,10 @@ dump_dg (FILE *file, int flags ATTRIBUTE
 	  fprintf (file,"  %d\t", DN_ID(e->src));
 	  fprintf (file,"%d\t", DN_ID(e->dst));
 
-	  if (DDR_ARE_DEPENDENT (e->ddr) == chrec_top)
+	  if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (e->ddr)))
 	    fprintf (file, "don't know\n");
 
-	  if (DDR_ARE_DEPENDENT (e->ddr) != chrec_top)
+	  if (DDR_ARE_DEPENDENT (e->ddr) != chrec_dont_know)
 	    {
 	      for (j = 0; j < DDR_NUM_SUBSCRIPTS (e->ddr); j++)
 	        {
Index: tree-elim-check.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-elim-check.c,v
retrieving revision 1.1.2.9
diff -d -u -p -r1.1.2.9 tree-elim-check.c
--- tree-elim-check.c	27 Apr 2004 14:10:14 -0000	1.1.2.9
+++ tree-elim-check.c	22 Jun 2004 14:05:29 -0000
@@ -265,18 +265,18 @@ prove_truth_value (enum tree_code code, 
       fprintf (dump_file, ")\n");
     }
   
-  if (nb_iters_in_then == chrec_top
-      || nb_iters_in_else == chrec_top)
+  if (chrec_contains_undetermined (nb_iters_in_then)
+      || chrec_contains_undetermined (nb_iters_in_else))
     return prove_truth_value_symbolic (code, chrec0, chrec1, value);
   
-  if (nb_iters_in_then == chrec_bot
+  if (nb_iters_in_then == chrec_known
       && integer_zerop (nb_iters_in_else))
     {
       *value = true;
       return true;
     }
   
-  if (nb_iters_in_else == chrec_bot
+  if (nb_iters_in_else == chrec_known
       && integer_zerop (nb_iters_in_then))
     {
       *value = false;
Index: tree-fold-const.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-fold-const.h,v
retrieving revision 1.1.2.8
diff -d -u -p -r1.1.2.8 tree-fold-const.h
--- tree-fold-const.h	27 Apr 2004 14:10:14 -0000	1.1.2.8
+++ tree-fold-const.h	22 Jun 2004 14:05:29 -0000
@@ -159,20 +159,6 @@ tree_fold_abs (tree type, 
   return fold (build1 (ABS_EXPR, type, a));
 }
 
-/* The binomial coefficient.  */
-
-static inline tree 
-tree_fold_binomial (tree n,
-		    tree k)
-{
-  return tree_fold_exact_div 
-    (integer_type_node, tree_fold_factorial (n), 
-     tree_fold_multiply 
-     (integer_type_node, tree_fold_factorial (k),
-      tree_fold_factorial 
-      (tree_fold_minus (integer_type_node, n, k))));
-}
-
 /* Determines whether (a divides b), or (a == gcd (a, b)).  */
 
 static inline bool 
Index: tree-pretty-print.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pretty-print.c,v
retrieving revision 1.1.2.70.2.9
diff -d -u -p -r1.1.2.70.2.9 tree-pretty-print.c
--- tree-pretty-print.c	21 Jun 2004 14:55:43 -0000	1.1.2.70.2.9
+++ tree-pretty-print.c	22 Jun 2004 14:05:29 -0000
@@ -1474,25 +1474,7 @@ dump_generic_node (pretty_printer *buffe
       dump_generic_node (buffer, CHREC_VAR (node), spc, flags, false);
       is_stmt = false;
       break;
-      
-    case INTERVAL_CHREC:
-      if (node == chrec_top)
-	pp_string (buffer, "[-oo, +oo]");
-      else if (node == chrec_bot)
-	pp_string (buffer, "[+oo, -oo]");
-      else if (node == chrec_not_analyzed_yet)
-	pp_string (buffer, "not_analyzed_yet");
-      else
-	{
-	  pp_string (buffer, "[");
-	  dump_generic_node (buffer, CHREC_LOW (node), spc, flags, false);
-	  pp_string (buffer, ", ");
-	  dump_generic_node (buffer, CHREC_UP (node), spc, flags, false);
-	  pp_string (buffer, "]");
-	}
-      is_stmt = false;
-      break;
-      
+
     default:
       NIY;
     }
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.59
diff -d -u -p -r1.1.2.59 tree-scalar-evolution.c
--- tree-scalar-evolution.c	21 Jun 2004 14:55:43 -0000	1.1.2.59
+++ tree-scalar-evolution.c	22 Jun 2004 14:05:29 -0000
@@ -267,11 +267,11 @@ tree chrec_not_analyzed_yet;
 
 /* Reserved to the cases where the analyzer has detected an
    undecidable property at compile time.  */
-tree chrec_top;
+tree chrec_dont_know;
 
 /* When the analyzer has detected that a property will never
-   happen, then it qualifies it with chrec_bot.  */
-tree chrec_bot;
+   happen, then it qualifies it with chrec_known.  */
+tree chrec_known;
 
 static bitmap already_instantiated;
 
@@ -481,8 +481,8 @@ compute_overall_effect_of_inner_loop (st
 {
   bool val = false;
 
-  if (evolution_fn == chrec_top)
-    return chrec_top;
+  if (chrec_contains_undetermined (evolution_fn))
+    return chrec_dont_know;
 
   else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
     {
@@ -492,8 +492,8 @@ compute_overall_effect_of_inner_loop (st
 	    loop_from_num (current_loops, CHREC_VARIABLE (evolution_fn));
 	  tree nb_iter = number_of_iterations_in_loop (inner_loop);
 
-	  if (nb_iter == chrec_top)
-	    return chrec_top;
+	  if (chrec_contains_undetermined (nb_iter))
+	    return chrec_dont_know;
 	  else
 	    {
 	      tree res;
@@ -522,7 +522,7 @@ compute_overall_effect_of_inner_loop (st
     return evolution_fn;
   
   else
-    return chrec_top;
+    return chrec_dont_know;
 }
 
 
@@ -543,14 +543,6 @@ chrec_is_positive (tree chrec, bool *val
   
   switch (TREE_CODE (chrec))
     {
-    case INTERVAL_CHREC:
-      if (!chrec_is_positive (CHREC_LOW (chrec), &value0)
-	  || !chrec_is_positive (CHREC_UP (chrec), &value1))
-	return false;
-
-      *value = value0;
-      return value0 == value1;
-
     case POLYNOMIAL_CHREC:
       if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
 	  || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
@@ -572,6 +564,10 @@ chrec_is_positive (tree chrec, bool *val
 
       nb_iter = number_of_iterations_in_loop
 	      (loop_from_num (current_loops, CHREC_VARIABLE (chrec)));
+
+      if (chrec_contains_undetermined (nb_iter))
+	return false;
+
       nb_iter = chrec_fold_minus 
 	(chrec_type (nb_iter), nb_iter,
 	 fold_convert (chrec_type (nb_iter), integer_one_node));
@@ -722,8 +718,8 @@ add_to_evolution_1 (unsigned loop_nb, 
       
     default:
       /* These nodes do not depend on a loop.  */
-      if (chrec_before == chrec_top)
-	return chrec_top;
+      if (chrec_contains_undetermined (chrec_before))
+	return chrec_dont_know;
       return build_polynomial_chrec (loop_nb, chrec_before, to_add);
     }
 }
@@ -878,7 +874,7 @@ add_to_evolution (unsigned loop_nb, 
      instantiated at this point.  */
   if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
     /* This should not happen.  */
-    return chrec_top;
+    return chrec_dont_know;
   
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -922,7 +918,7 @@ set_nb_iterations_in_loop (struct loop *
      representation of nb_iters that are equal to MAX_INT.  */
   if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0)
       || TREE_OVERFLOW (res))
-    res = chrec_top;
+    res = chrec_dont_know;
   
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -1269,7 +1265,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
 		 evolution_of_loop);
 	      
 	      if (res)
-		*evolution_of_loop = chrec_top;
+		*evolution_of_loop = chrec_dont_know;
 	      
 	      else
 		{
@@ -1278,7 +1274,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
 		     evolution_of_loop);
 		  
 		  if (res)
-		    *evolution_of_loop = chrec_top;
+		    *evolution_of_loop = chrec_dont_know;
 		}
 	    }
 	  
@@ -1290,7 +1286,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
 		(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, 
 		 evolution_of_loop);
 	      if (res)
-		*evolution_of_loop = chrec_top;
+		*evolution_of_loop = chrec_dont_know;
 	    }
 	}
       
@@ -1302,7 +1298,7 @@ follow_ssa_edge_in_rhs (struct loop *loo
 	    (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi, 
 	     evolution_of_loop);
 	  if (res)
-	    *evolution_of_loop = chrec_top;
+	    *evolution_of_loop = chrec_dont_know;
 	}
       
       else
@@ -1348,7 +1344,7 @@ follow_ssa_edge_in_condition_phi_branch 
 					 tree init_cond)
 {
   tree branch = PHI_ARG_DEF (condition_phi, i);
-  *evolution_of_branch = chrec_top;
+  *evolution_of_branch = chrec_dont_know;
 
   /* Do not follow back edges (they must belong to an irreducible loop, which
      we really do not want to worry about).  */
@@ -1369,7 +1365,7 @@ follow_ssa_edge_in_condition_phi_branch 
 	 
      FIXME:  This case have to be refined correctly: 
      in some cases it is possible to say something better than
-     chrec_top, for example using a wrap-around notation.  */
+     chrec_dont_know, for example using a wrap-around notation.  */
   return false;
 }
 
@@ -1443,7 +1439,7 @@ follow_ssa_edge_inner_loop_phi (struct l
 
       /* If the path crosses this loop-phi, give up.  */
       if (res == true)
-	*evolution_of_loop = chrec_top;
+	*evolution_of_loop = chrec_dont_know;
 
       return res;
     }
@@ -1566,7 +1562,7 @@ analyze_evolution_in_loop (tree loop_phi
 	 all the other iterations it has the value of ARG.  
 	 For the moment, PEELED_CHREC nodes are not built.  */
       if (!res)
-	ev_fn = chrec_top;
+	ev_fn = chrec_dont_know;
       
       /* When there are multiple back edges of the loop (which in fact never
 	 happens currently, but nevertheless), merge their evolutions. */
@@ -1623,7 +1619,7 @@ analyze_initial_condition (tree loop_phi
 
       if (TREE_CODE (branch) == SSA_NAME)
 	{
-	  init_cond = chrec_top;
+	  init_cond = chrec_dont_know;
       	  break;
 	}
 
@@ -1632,7 +1628,7 @@ analyze_initial_condition (tree loop_phi
 
   /* Ooops -- a loop without an entry???  */
   if (init_cond == chrec_not_analyzed_yet)
-    init_cond = chrec_top;
+    init_cond = chrec_dont_know;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -1690,7 +1686,7 @@ interpret_condition_phi (struct loop *lo
       
       if (backedge_phi_arg_p (condition_phi, i))
 	{
-	  res = chrec_top;
+	  res = chrec_dont_know;
 	  break;
 	}
 
@@ -1771,7 +1767,7 @@ interpret_rhs_modify_expr (struct loop *
       break;
       
     default:
-      res = chrec_top;
+      res = chrec_dont_know;
       break;
     }
   
@@ -1814,7 +1810,7 @@ analyze_scalar_evolution_1 (struct loop 
   struct loop *def_loop;
 
   if (loop == NULL)
-    return chrec_top;
+    return chrec_dont_know;
 
   if (TREE_CODE (var) != SSA_NAME)
     return interpret_rhs_modify_expr (loop, var, type);
@@ -1862,14 +1858,14 @@ analyze_scalar_evolution_1 (struct loop 
       break;
 
     default:
-      res = chrec_top;
+      res = chrec_dont_know;
       break;
     }
 
  set_and_end:
 
   /* Keep the symbolic form.  */
-  if (res == chrec_top)
+  if (chrec_contains_undetermined (res))
     res = var;
 
   if (loop == def_loop)
@@ -1910,7 +1906,8 @@ analyze_scalar_evolution (struct loop *l
 
   res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
 
-  if (TREE_CODE (var) == SSA_NAME && res == chrec_top)
+  if (TREE_CODE (var) == SSA_NAME && 
+      chrec_contains_undetermined (res))
     res = var;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -1923,7 +1920,7 @@ analyze_scalar_evolution (struct loop *l
    WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
    of VERSION).  */
 
-tree
+static tree
 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
 				  tree version)
 {
@@ -1943,7 +1940,7 @@ analyze_scalar_evolution_in_loop (struct
 	 but we do not have a user for it anyway)  */
       if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
 	  || !val)
-	return chrec_top;
+	return chrec_dont_know;
 
       use_loop = use_loop->outer;
     }
@@ -1997,16 +1994,14 @@ instantiate_parameters_1 (struct loop *l
 	  else
 	    {
 	      /* Something with unknown behavior in LOOP.  */
-	      return chrec_top;
+	      return chrec_dont_know;
 	    }
 	}
 
       def_loop = find_common_loop (loop, def_bb->loop_father);
 
-      /* If the analysis yields a parametric chrec, instantiate
-	 the result again.  Enqueue the SSA_NAME such that it will
-	 never be instantiated twice, avoiding the cyclic
-	 instantiation in mixers.  */
+      /* If the analysis yields a parametric chrec, instantiate the
+	 result again.  Avoid the cyclic instantiation in mixers.  */
       bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
       res = analyze_scalar_evolution (def_loop, chrec);
       res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
@@ -2020,13 +2015,6 @@ instantiate_parameters_1 (struct loop *l
 				      allow_superloop_chrecs);
       return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
 
-    case INTERVAL_CHREC:
-      op0 = instantiate_parameters_1 (loop, CHREC_LOW (chrec),
-				      allow_superloop_chrecs);
-      op1 = instantiate_parameters_1 (loop, CHREC_UP (chrec),
-				      allow_superloop_chrecs);
-      return build_interval_chrec (op0, op1);
-
     case PLUS_EXPR:
       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
 				      allow_superloop_chrecs);
@@ -2091,7 +2079,7 @@ instantiate_parameters_1 (struct loop *l
     }
 
   /* Too complicated to handle.  */
-  return chrec_top;
+  return chrec_dont_know;
 }
 
 /* Analyze all the parameters of the chrec that were left under a
@@ -2137,8 +2125,8 @@ resolve_mixers (struct loop *loop, tree 
 /* Entry point for the analysis of the number of iterations pass.  
    This function tries to safely approximate the number of iterations
    the loop will run.  When this property is not decidable at compile
-   time, the result is chrec_top: [-oo, +oo].  Otherwise the result is
-   a scalar, an interval, or a symbolic parameter.
+   time, the result is chrec_dont_know: [-oo, +oo].  Otherwise the result is
+   a scalar or a symbolic parameter.
    
    Example of analysis: suppose that the loop has an exit condition:
    
@@ -2166,7 +2154,7 @@ number_of_iterations_in_loop (struct loo
   res = loop_nb_iterations (loop);
   if (res)
     return res;
-  res = chrec_top;
+  res = chrec_dont_know;
   
   if (!loop_exit_edges (loop))
     goto end;
@@ -2181,7 +2169,7 @@ number_of_iterations_in_loop (struct loo
   else if (integer_zerop (niter_desc.may_be_zero))
     res = niter_desc.niter;
   else
-    res = chrec_top;
+    res = chrec_dont_know;
 
 end:
   return set_nb_iterations_in_loop (loop, res);
@@ -2195,15 +2183,15 @@ static void 
 number_of_iterations_for_all_loops (varray_type exit_conditions)
 {
   unsigned int i;
-  unsigned nb_chrec_top_loops = 0;
+  unsigned nb_chrec_dont_know_loops = 0;
   unsigned nb_static_loops = 0;
   
   for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
     {
       tree res = number_of_iterations_in_loop 
 	(loop_of_stmt (VARRAY_TREE (exit_conditions, i)));
-      if (res == chrec_top)
-	nb_chrec_top_loops++;
+      if (chrec_contains_undetermined (res))
+	nb_chrec_dont_know_loops++;
       else
 	nb_static_loops++;
     }
@@ -2212,7 +2200,7 @@ number_of_iterations_for_all_loops (varr
     {
       fprintf (dump_file, "\n(\n");
       fprintf (dump_file, "-----------------------------------------\n");
-      fprintf (dump_file, "%d\tnb_chrec_top_loops\n", nb_chrec_top_loops);
+      fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
       fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
       fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
       fprintf (dump_file, "-----------------------------------------\n");
@@ -2232,8 +2220,7 @@ struct chrec_stats 
   unsigned nb_affine;
   unsigned nb_affine_multivar;
   unsigned nb_higher_poly;
-  unsigned nb_chrec_top;
-  unsigned nb_interval_chrec;
+  unsigned nb_chrec_dont_know;
   unsigned nb_undetermined;
 };
 
@@ -2246,8 +2233,7 @@ reset_chrecs_counters (struct chrec_stat
   stats->nb_affine = 0;
   stats->nb_affine_multivar = 0;
   stats->nb_higher_poly = 0;
-  stats->nb_chrec_top = 0;
-  stats->nb_interval_chrec = 0;
+  stats->nb_chrec_dont_know = 0;
   stats->nb_undetermined = 0;
 }
 
@@ -2262,8 +2248,7 @@ dump_chrecs_stats (FILE *file, struct ch
   fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
   fprintf (file, "%d\tdegree greater than 2 polynomials\n", 
 	   stats->nb_higher_poly);
-  fprintf (file, "%d\tchrec_top chrecs\n", stats->nb_chrec_top);
-  fprintf (file, "%d\tinterval chrecs\n", stats->nb_chrec_top);
+  fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
   fprintf (file, "-----------------------------------------\n");
   fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
   fprintf (file, "%d\twith undetermined coefficients\n", 
@@ -2320,21 +2305,6 @@ gather_chrec_stats (tree chrec, struct c
 	}
       
       break;
-      
-    case INTERVAL_CHREC:
-      if (chrec == chrec_top)
-	{
-	  if (dump_file && (dump_flags & TDF_STATS))
-	    fprintf (dump_file, "  chrec_top\n");
-	  stats->nb_chrec_top++;
-	}
-      else
-	{
-	  if (dump_file && (dump_flags & TDF_STATS))
-	    fprintf (dump_file, "  interval chrec\n");
-	  stats->nb_interval_chrec++;
-	}
-      break;
 
     default:
       break;
@@ -2427,22 +2397,17 @@ gather_stats_on_scev_database (void)
 
 
 
-static void initialize_scalar_evolutions_analyzer (void);
-
 /* Initializer.  */
 
 static void
 initialize_scalar_evolutions_analyzer (void)
 {
-  /* The elements below are unique.  The values contained in these
-     intervals are not used.  */
-  if (chrec_top == NULL_TREE)
+  /* The elements below are unique.  */
+  if (chrec_dont_know == NULL_TREE)
     {
       chrec_not_analyzed_yet = NULL_TREE;
-      chrec_top = build_interval_chrec 
-	(build_int_2 (2222, 0), build_int_2 (3222, 0));
-      chrec_bot = build_interval_chrec 
-	(build_int_2 (3333, 0), build_int_2 (4333, 0));
+      chrec_dont_know = build_int_2 (2222, 0);
+      chrec_known = build_int_2 (3333, 0);
     }
 }
 
@@ -2503,6 +2468,9 @@ simple_iv (struct loop *loop, tree stmt,
     return false;
 
   ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
+  if (chrec_contains_undetermined (ev))
+    return false;
+
   if (tree_does_not_contain_chrecs (ev)
       && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
     {
Index: tree-scalar-evolution.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.h,v
retrieving revision 1.1.2.14
diff -d -u -p -r1.1.2.14 tree-scalar-evolution.h
--- tree-scalar-evolution.h	18 Jun 2004 20:52:32 -0000	1.1.2.14
+++ tree-scalar-evolution.h	22 Jun 2004 14:05:29 -0000
@@ -29,8 +29,6 @@ extern void scev_initialize (struct loop
 extern void scev_reset (void);
 extern void scev_finalize (void);
 extern tree analyze_scalar_evolution (struct loop *, tree);
-extern tree analyze_scalar_evolution_in_loop (struct loop *, struct loop *,
-					      tree);
 extern tree instantiate_parameters (struct loop *, tree);
 extern void eliminate_redundant_checks (void);
 extern void gather_stats_on_scev_database (void);
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivcanon.c,v
retrieving revision 1.1.2.12
diff -d -u -p -r1.1.2.12 tree-ssa-loop-ivcanon.c
--- tree-ssa-loop-ivcanon.c	11 Jun 2004 02:51:27 -0000	1.1.2.12
+++ tree-ssa-loop-ivcanon.c	22 Jun 2004 14:05:29 -0000
@@ -191,6 +191,8 @@ canonicalize_loop_induction_variables (s
   tree niter;
 
   niter = number_of_iterations_in_loop (loop);
+  if (chrec_contains_undetermined (niter))
+    return;
 
   if (TREE_CODE (niter) == INTEGER_CST)
     {
@@ -208,7 +210,8 @@ canonicalize_loop_induction_variables (s
   else if (try_eval)
     niter = find_loop_niter_by_eval (loop, &exit);
 
-  if (TREE_CODE (niter) != INTEGER_CST)
+  if (chrec_contains_undetermined (niter)
+      || TREE_CODE (niter) != INTEGER_CST)
     return;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.39
diff -d -u -p -r1.1.2.39 tree-ssa-loop-ivopts.c
--- tree-ssa-loop-ivopts.c	18 Jun 2004 20:52:32 -0000	1.1.2.39
+++ tree-ssa-loop-ivopts.c	22 Jun 2004 14:05:29 -0000
@@ -351,7 +351,8 @@ dump_use (FILE *file, struct iv_use *use
    fprintf (file, "\n");
 
    fprintf (file, "  at position ");
-   print_generic_expr (file, *use->op_p, TDF_SLIM);
+   if (use->op_p)
+     print_generic_expr (file, *use->op_p, TDF_SLIM);
    fprintf (file, "\n");
 
    if (iv->step)
@@ -1007,6 +1008,9 @@ determine_biv_step (tree phi)
     return NULL_TREE;
 
   ev = analyze_scalar_evolution (loop, name);
+  if (chrec_contains_undetermined (ev))
+    return NULL_TREE;
+
   if (TREE_CODE (ev) == INTEGER_CST
       || TREE_CODE (ev) == SSA_NAME)
     return convert (type, integer_zero_node);
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-niter.c,v
retrieving revision 1.1.2.6
diff -d -u -p -r1.1.2.6 tree-ssa-loop-niter.c
--- tree-ssa-loop-niter.c	17 Jun 2004 18:25:13 -0000	1.1.2.6
+++ tree-ssa-loop-niter.c	22 Jun 2004 14:05:29 -0000
@@ -792,7 +792,7 @@ loop_niter_by_eval (struct loop *loop, e
 
   cond = last_stmt (exit->src);
   if (!cond || TREE_CODE (cond) != COND_EXPR)
-    return chrec_top;
+    return chrec_dont_know;
 
   cnd = COND_EXPR_COND (cond);
   if (exit->flags & EDGE_TRUE_VALUE)
@@ -812,14 +812,14 @@ loop_niter_by_eval (struct loop *loop, e
       break;
 
     default:
-      return chrec_top;
+      return chrec_dont_know;
     }
 
   for (j = 0; j < 2; j++)
     {
       phi[j] = get_base_for (loop, op[j]);
       if (!phi[j])
-	return chrec_top;
+	return chrec_dont_know;
     }
 
   for (j = 0; j < 2; j++)
@@ -856,7 +856,7 @@ loop_niter_by_eval (struct loop *loop, e
 	val[j] = get_val_for (next[j], val[j]);
     }
 
-  return chrec_top;
+  return chrec_dont_know;
 }
 
 /* Finds the exit of the LOOP by that the loop exits after a constant
@@ -879,7 +879,8 @@ find_loop_niter_by_eval (struct loop *lo
 	continue;
 
       aniter = loop_niter_by_eval (loop, ex);
-      if (TREE_CODE (aniter) != INTEGER_CST)
+      if (chrec_contains_undetermined (aniter)
+	  || TREE_CODE (aniter) != INTEGER_CST)
 	continue;
 
       if (niter
@@ -892,7 +893,7 @@ find_loop_niter_by_eval (struct loop *lo
     }
   free (exits);
 
-  return niter ? niter : chrec_top;
+  return niter ? niter : chrec_dont_know;
 }
 
 /*
@@ -947,18 +948,6 @@ estimate_numbers_of_iterations_loop (str
   unsigned i, n_exits;
   struct tree_niter_desc niter_desc;
 
-  /* First, use the scev information about the number of iterations.  */
-  niter = number_of_iterations_in_loop (loop);
-  if (niter != chrec_top)
-    {
-      type = TREE_TYPE (niter);
-      niter = fold (build (MINUS_EXPR, type, niter,
-			   convert (type, integer_one_node)));
-      record_estimate (loop, niter, boolean_true_node,
-		       last_stmt (loop_exit_edge (loop, 0)->src));
-    }
-
-  /* Now use number_of_iterations_exit.  */
   exits = get_loop_exit_edges (loop, &n_exits);
   for (i = 0; i < n_exits; i++)
     {
Index: tree-vectorizer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-vectorizer.c,v
retrieving revision 1.1.2.43
diff -d -u -p -r1.1.2.43 tree-vectorizer.c
--- tree-vectorizer.c	22 Jun 2004 07:06:02 -0000	1.1.2.43
+++ tree-vectorizer.c	22 Jun 2004 14:05:29 -0000
@@ -3921,7 +3921,7 @@ vect_analyze_loop_with_symbolic_num_of_i
   
   niters = number_of_iterations_in_loop (loop);
 
-  if (niters == chrec_top)
+  if (chrec_contains_undetermined (niters))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
           fprintf (dump_file, "\nInfinite number of iterations.\n");
@@ -3941,13 +3941,6 @@ vect_analyze_loop_with_symbolic_num_of_i
       print_generic_expr (dump_file, niters, TDF_DETAILS);
     }
 
-  if (chrec_contains_intervals (niters))
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-          fprintf (dump_file, "\nniters contains interval.\n");
-      return false;
-    }
-
   /* debug_tree(niters); */ 
    
   /* Analyze phi functions of the loop header.  */
@@ -4024,6 +4017,7 @@ vect_get_loop_niters (struct loop *loop,
   niters = number_of_iterations_in_loop (loop);
 
   if (niters != NULL_TREE
+      && niters != chrec_dont_know
       && TREE_CODE (niters) == INTEGER_CST)
     {
       *number_of_iterations = TREE_INT_CST_LOW (niters);
Index: tree.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.def,v
retrieving revision 1.52.2.21.2.9
diff -d -u -p -r1.52.2.21.2.9 tree.def
--- tree.def	21 Jun 2004 14:55:43 -0000	1.52.2.21.2.9
+++ tree.def	22 Jun 2004 14:05:32 -0000
@@ -897,13 +897,6 @@ DEFTREECODE (CATCH_EXPR, "catch_expr", '
    expanding.  */
 DEFTREECODE (EH_FILTER_EXPR, "eh_filter_expr", 's', 2)
 
-/* Chains of recurrences.  */
-
-/* Intervals.
-   Under the form: cr = [CHREC_LOW (cr), CHREC_UP (cr)].  
-   CHREC_LOW and CHREC_UP contain INTEGER_CST nodes.  */
-DEFTREECODE (INTERVAL_CHREC, "interval_chrec", 'e', 2)
-
 /* Polynomial chains of recurrences.
    Under the form: cr = {CHREC_LEFT (cr), +, CHREC_RIGHT (cr)}.  */
 DEFTREECODE (POLYNOMIAL_CHREC, "polynomial_chrec", 'e', 3)



More information about the Gcc-patches mailing list