re PR tree-optimization/19224 (Endless loop compiling simple file: Bug in tree-scalar-evolution.c (instantiate_parameters_1)?)

	PR tree-optimization/19224
	* tree-scalar-evolution.c (get_instantiated_value,
	set_instantiated_value): New functions.
	(instantiate_parameters_1): Cache the results.
	(instantiate_parameters, resolve_mixers): Initialize and free
	the cache.

From-SVN: r93106

2 files changed, 98 insertions, 36 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index d4395a0..5f6b14b 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2005-01-09  Zdenek Dvorak  <dvorakz@suse.cz>
+
+	PR tree-optimization/19224
+	* tree-scalar-evolution.c (get_instantiated_value,
+	set_instantiated_value): New functions.
+	(instantiate_parameters_1): Cache the results.
+	(instantiate_parameters, resolve_mixers): Initialize and free
+	the cache.
+
 2005-01-08  David Edelsohn  <edelsohn@gnu.org>
 
 	* config/i386/i386.md (addhi_4): Correct reference in comment.
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index dd4ea0b..1ffeb0b 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -1888,19 +1888,55 @@ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
     }
 }
 
+/* Returns instantiated value for VERSION in CACHE.  */
+
+static tree
+get_instantiated_value (htab_t cache, tree version)
+{
+  struct scev_info_str *info, pattern;
+  
+  pattern.var = version;
+  info = htab_find (cache, &pattern);
+
+  if (info)
+    return info->chrec;
+  else
+    return NULL_TREE;
+}
+
+/* Sets instantiated value for VERSION to VAL in CACHE.  */
+
+static void
+set_instantiated_value (htab_t cache, tree version, tree val)
+{
+  struct scev_info_str *info, pattern;
+  PTR *slot;
+  
+  pattern.var = version;
+  slot = htab_find_slot (cache, &pattern, INSERT);
+
+  if (*slot)
+    info = *slot;
+  else
+    info = *slot = new_scev_info_str (version);
+  info->chrec = val;
+}
+
 /* Analyze all the parameters of the chrec that were left under a symbolic form,
    with respect to LOOP.  CHREC is the chrec to instantiate.  If
    ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
-   outer loop chrecs is done.  */
+   outer loop chrecs is done.  CACHE is the cache of already instantiated
+   values.  */
 
 static tree
 instantiate_parameters_1 (struct loop *loop, tree chrec,
-			  bool allow_superloop_chrecs)
+			  bool allow_superloop_chrecs,
+			  htab_t cache)
 {
   tree res, op0, op1, op2;
   basic_block def_bb;
   struct loop *def_loop;
-  
+ 
   if (chrec == NULL_TREE
       || automatically_generated_chrec_p (chrec))
     return chrec;
@@ -1920,41 +1956,52 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
 	      && !flow_bb_inside_loop_p (loop, def_bb)))
 	return chrec;
 
-      /* Don't instantiate the SSA_NAME if it is in a mixer
+      /* We cache the value of instantiated variable to avoid exponential
+	 time complexity due to reevaluations.  We also store the convenient
+	 value in the cache in order to prevent infinite recursion -- we do
+	 not want to instantiate the SSA_NAME if it is in a mixer
 	 structure.  This is used for avoiding the instantiation of
 	 recursively defined functions, such as: 
 
 	 | a_2 -> {0, +, 1, +, a_2}_1  */
-	   
+
+      res = get_instantiated_value (cache, chrec);
+      if (res)
+	return res;
+
+      /* Store the convenient value for chrec in the structure.  If it
+	 is defined outside of the loop, we may just leave it in symbolic
+	 form, otherwise we need to admit that we do not know its behavior
+	 inside the loop.  */
+      res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
+      set_instantiated_value (cache, chrec, res);
+
+      /* To make things even more complicated, instantiate_parameters_1
+	 calls analyze_scalar_evolution that may call # of iterations
+	 analysis that may in turn call instantiate_parameters_1 again.
+	 To prevent the infinite recursion, keep also the bitmap of
+	 ssa names that are being instantiated globally.  */
       if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
-	{
-	  if (!flow_bb_inside_loop_p (loop, def_bb))
-	    {
-	      /* We may keep the loop invariant in symbolic form.  */
-	      return chrec;
-	    }
-	  else
-	    {
-	      /* Something with unknown behavior in LOOP.  */
-	      return chrec_dont_know;
-	    }
-	}
+	return res;
 
       def_loop = find_common_loop (loop, def_bb->loop_father);
 
       /* If the analysis yields a parametric chrec, instantiate the
-	 result again.  Avoid the cyclic instantiation in mixers.  */
+	 result again.  */
       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);
+      res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs, cache);
       bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
+
+      /* Store the correct value to the cache.  */
+      set_instantiated_value (cache, chrec, res);
       return res;
 
     case POLYNOMIAL_CHREC:
       op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       if (CHREC_LEFT (chrec) != op0
 	  || CHREC_RIGHT (chrec) != op1)
 	chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
@@ -1962,9 +2009,9 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
 
     case PLUS_EXPR:
       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       if (TREE_OPERAND (chrec, 0) != op0
 	  || TREE_OPERAND (chrec, 1) != op1)
       	chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
@@ -1972,9 +2019,9 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
 
     case MINUS_EXPR:
       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       if (TREE_OPERAND (chrec, 0) != op0
 	  || TREE_OPERAND (chrec, 1) != op1)
         chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
@@ -1982,9 +2029,9 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
 
     case MULT_EXPR:
       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       if (TREE_OPERAND (chrec, 0) != op0
 	  || TREE_OPERAND (chrec, 1) != op1)
 	chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
@@ -1994,7 +2041,7 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
     case CONVERT_EXPR:
     case NON_LVALUE_EXPR:
       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       if (op0 == chrec_dont_know)
         return chrec_dont_know;
 
@@ -2017,11 +2064,11 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
     {
     case 3:
       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       if (op0 == chrec_dont_know
 	  || op1 == chrec_dont_know
 	  || op2 == chrec_dont_know)
@@ -2037,9 +2084,9 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
 
     case 2:
       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       if (op0 == chrec_dont_know
 	  || op1 == chrec_dont_know)
         return chrec_dont_know;
@@ -2051,7 +2098,7 @@ instantiate_parameters_1 (struct loop *loop, tree chrec,
 	    
     case 1:
       op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
-				      allow_superloop_chrecs);
+				      allow_superloop_chrecs, cache);
       if (op0 == chrec_dont_know)
         return chrec_dont_know;
       if (op0 == TREE_OPERAND (chrec, 0))
@@ -2078,6 +2125,7 @@ instantiate_parameters (struct loop *loop,
 			tree chrec)
 {
   tree res;
+  htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -2088,7 +2136,7 @@ instantiate_parameters (struct loop *loop,
       fprintf (dump_file, ")\n");
     }
  
-  res = instantiate_parameters_1 (loop, chrec, true);
+  res = instantiate_parameters_1 (loop, chrec, true, cache);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
@@ -2096,6 +2144,8 @@ instantiate_parameters (struct loop *loop,
       print_generic_expr (dump_file, res, 0);
       fprintf (dump_file, "))\n");
     }
+
+  htab_delete (cache);
   
   return res;
 }
@@ -2106,7 +2156,10 @@ instantiate_parameters (struct loop *loop,
 static tree
 resolve_mixers (struct loop *loop, tree chrec)
 {
-  return instantiate_parameters_1 (loop, chrec, false);
+  htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
+  tree ret = instantiate_parameters_1 (loop, chrec, false, cache);
+  htab_delete (cache);
+  return ret;
 }
 
 /* Entry point for the analysis of the number of iterations pass.