2008-09-05 Sebastian Pop <sebastian.pop@amd.com>

	PR tree-optimization/37375
	* tree-scalar-evolution.c (scev_info_str): Add field instantiated_below.
	(new_scev_info_str, eq_scev_info, find_var_scev_info,
	set_scalar_evolution, get_scalar_evolution, get_instantiated_value,
	set_instantiated_value): Pass instantiated_below.
	(analyze_scalar_evolution_1, analyze_scalar_evolution): Update calls to
	above functions.
	(instantiate_scev_1, instantiate_scev): Pass a basic block above which the
	definitions are not instantiated.

	* tree-scalar-evolution.h (instantiate_scev): Update declaration.
	(block_before_loop): New.
	* tree-data-ref.c (dr_analyze_indices): Update uses of instantiate_scev.
	* graphite.c (block_before_scop): New.
	(loop_affine_expr, stmt_simple_for_scop_p, harmful_stmt_in_bb): Pass a 
	basic block, not a loop for determining the parameters.
	(scopdet_edge_info, build_scops_1): Do not pass outermost loop in the
	scop.
	(idx_record_params, find_params_in_bb, find_scop_parameters,
	build_loop_iteration_domains, add_conditions_to_domain): Update calls 
	to instantiate_scev.
	
	* Makefile.in (cfgloopmanip.o): Add missing dependency on TREE_FLOW_H.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@140164 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 70 insertions, 75 deletions

diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index 67fcd08dda0..64d628a1adf 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -175,8 +175,8 @@ along with GCC; see the file COPYING3.  If not see
    value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
    {0, +, 1}_1.  To obtain the evolution function in loop_3 and
    instantiate the scalar variables up to loop_1, one has to use:
-   instantiate_scev (loop_1, loop_3, "j + k").  The result of this
-   call is {{0, +, 1}_1, +, 1}_2.
+   instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
+   The result of this call is {{0, +, 1}_1, +, 1}_2.
 
    Example 3: Higher degree polynomials.
      
@@ -278,11 +278,13 @@ along with GCC; see the file COPYING3.  If not see
 
 static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
 
-/* The cached information about a ssa name VAR, claiming that inside LOOP,
-   the value of VAR can be expressed as CHREC.  */
+/* The cached information about an SSA name VAR, claiming that below
+   basic block INSTANTIATED_BELOW, the value of VAR can be expressed
+   as CHREC.  */
 
 struct scev_info_str GTY(())
 {
+  basic_block instantiated_below;
   tree var;
   tree chrec;
 };
@@ -306,22 +308,21 @@ tree chrec_dont_know;
    happen, then it qualifies it with chrec_known.  */
 tree chrec_known;
 
-static bitmap already_instantiated;
-
 static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
 
 
-/* Constructs a new SCEV_INFO_STR structure.  */
+/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW.  */
 
 static inline struct scev_info_str *
-new_scev_info_str (tree var)
+new_scev_info_str (basic_block instantiated_below, tree var)
 {
   struct scev_info_str *res;
   
   res = GGC_NEW (struct scev_info_str);
   res->var = var;
   res->chrec = chrec_not_analyzed_yet;
-  
+  res->instantiated_below = instantiated_below;
+
   return res;
 }
 
@@ -341,7 +342,8 @@ eq_scev_info (const void *e1, const void *e2)
   const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
   const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
 
-  return elt1->var == elt2->var;
+  return (elt1->var == elt2->var
+	  && elt1->instantiated_below == elt2->instantiated_below);
 }
 
 /* Deletes database element E.  */
@@ -352,22 +354,22 @@ del_scev_info (void *e)
   ggc_free (e);
 }
 
-/* Get the index corresponding to VAR in the current LOOP.  If
-   it's the first time we ask for this VAR, then we return
-   chrec_not_analyzed_yet for this VAR and return its index.  */
+/* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
+   A first query on VAR returns chrec_not_analyzed_yet.  */
 
 static tree *
-find_var_scev_info (tree var)
+find_var_scev_info (basic_block instantiated_below, tree var)
 {
   struct scev_info_str *res;
   struct scev_info_str tmp;
   PTR *slot;
 
   tmp.var = var;
+  tmp.instantiated_below = instantiated_below;
   slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
 
   if (!*slot)
-    *slot = new_scev_info_str (var);
+    *slot = new_scev_info_str (instantiated_below, var);
   res = (struct scev_info_str *) *slot;
 
   return &res->chrec;
@@ -570,20 +572,22 @@ chrec_is_positive (tree chrec, bool *value)
 /* Associate CHREC to SCALAR.  */
 
 static void
-set_scalar_evolution (tree scalar, tree chrec)
+set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
 {
   tree *scalar_info;
  
   if (TREE_CODE (scalar) != SSA_NAME)
     return;
 
-  scalar_info = find_var_scev_info (scalar);
+  scalar_info = find_var_scev_info (instantiated_below, scalar);
   
   if (dump_file)
     {
       if (dump_flags & TDF_DETAILS)
 	{
 	  fprintf (dump_file, "(set_scalar_evolution \n");
+	  fprintf (dump_file, "  instantiated_below = %d \n",
+		   instantiated_below->index);
 	  fprintf (dump_file, "  (scalar = ");
 	  print_generic_expr (dump_file, scalar, 0);
 	  fprintf (dump_file, ")\n  (scalar_evolution = ");
@@ -597,10 +601,11 @@ set_scalar_evolution (tree scalar, tree chrec)
   *scalar_info = chrec;
 }
 
-/* Retrieve the chrec associated to SCALAR in the LOOP.  */
+/* Retrieve the chrec associated to SCALAR instantiated below
+   INSTANTIATED_BELOW block.  */
 
 static tree
-get_scalar_evolution (tree scalar)
+get_scalar_evolution (basic_block instantiated_below, tree scalar)
 {
   tree res;
   
@@ -620,7 +625,7 @@ get_scalar_evolution (tree scalar)
   switch (TREE_CODE (scalar))
     {
     case SSA_NAME:
-      res = *find_var_scev_info (scalar);
+      res = *find_var_scev_info (instantiated_below, scalar);
       break;
 
     case REAL_CST:
@@ -1845,7 +1850,7 @@ analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
     res = var;
 
   if (loop == def_loop)
-    set_scalar_evolution (var, res);
+    set_scalar_evolution (block_before_loop (loop), var, res);
 
   return res;
 }
@@ -1879,7 +1884,8 @@ analyze_scalar_evolution (struct loop *loop, tree var)
       fprintf (dump_file, ")\n");
     }
 
-  res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
+  res = get_scalar_evolution (block_before_loop (loop), var);
+  res = analyze_scalar_evolution_1 (loop, var, res);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, ")\n");
@@ -1926,14 +1932,17 @@ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
     }
 }
 
-/* Returns instantiated value for VERSION in CACHE.  */
+/* Returns from CACHE the value for VERSION instantiated below
+   INSTANTIATED_BELOW block.  */
 
 static tree
-get_instantiated_value (htab_t cache, tree version)
+get_instantiated_value (htab_t cache, basic_block instantiated_below,
+			tree version)
 {
   struct scev_info_str *info, pattern;
   
   pattern.var = version;
+  pattern.instantiated_below = instantiated_below;
   info = (struct scev_info_str *) htab_find (cache, &pattern);
 
   if (info)
@@ -1942,10 +1951,12 @@ get_instantiated_value (htab_t cache, tree version)
     return NULL_TREE;
 }
 
-/* Sets instantiated value for VERSION to VAL in CACHE.  */
+/* Sets in CACHE the value of VERSION instantiated below basic block
+   INSTANTIATED_BELOW to VAL.  */
 
 static void
-set_instantiated_value (htab_t cache, tree version, tree val)
+set_instantiated_value (htab_t cache, basic_block instantiated_below,
+			tree version, tree val)
 {
   struct scev_info_str *info, pattern;
   PTR *slot;
@@ -1954,7 +1965,7 @@ set_instantiated_value (htab_t cache, tree version, tree val)
   slot = htab_find_slot (cache, &pattern, INSERT);
 
   if (!*slot)
-    *slot = new_scev_info_str (version);
+    *slot = new_scev_info_str (instantiated_below, version);
   info = (struct scev_info_str *) *slot;
   info->chrec = val;
 }
@@ -1989,7 +2000,7 @@ loop_closed_phi_def (tree var)
   return NULL_TREE;
 }
 
-/* Analyze all the parameters of the chrec, between INSTANTIATION_LOOP
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
    and EVOLUTION_LOOP, that were left under a symbolic form.  
 
    CHREC is the scalar evolution to instantiate.
@@ -2004,7 +2015,7 @@ loop_closed_phi_def (tree var)
    instantiated, and to stop if it exceeds some limit.  */
   
 static tree
-instantiate_scev_1 (struct loop *instantiation_loop,
+instantiate_scev_1 (basic_block instantiate_below,
 		    struct loop *evolution_loop, tree chrec,
 		    bool fold_conversions, htab_t cache, int size_expr)
 {
@@ -2030,7 +2041,7 @@ instantiate_scev_1 (struct loop *instantiation_loop,
 	 evolutions in outer loops), nothing to do.  */
       if (!def_bb
 	  || loop_depth (def_bb->loop_father) == 0
-	  || !flow_bb_inside_loop_p (instantiation_loop, def_bb))
+	  || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
 	return chrec;
 
       /* We cache the value of instantiated variable to avoid exponential
@@ -2042,31 +2053,17 @@ instantiate_scev_1 (struct loop *instantiation_loop,
 
 	 | a_2 -> {0, +, 1, +, a_2}_1  */
 
-      res = get_instantiated_value (cache, chrec);
+      res = get_instantiated_value (cache, instantiate_below, 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 (instantiation_loop, def_bb) 
-	? chrec : chrec_dont_know;
-      set_instantiated_value (cache, chrec, res);
-
-      /* To make things even more complicated, instantiate_scev_1
-	 calls analyze_scalar_evolution that may call # of iterations
-	 analysis that may in turn call instantiate_scev_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)))
-	return res;
+      res = chrec_dont_know;
+      set_instantiated_value (cache, instantiate_below, chrec, res);
 
       def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
 
       /* If the analysis yields a parametric chrec, instantiate the
 	 result again.  */
-      bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
       res = analyze_scalar_evolution (def_loop, chrec);
 
       /* Don't instantiate loop-closed-ssa phi nodes.  */
@@ -2085,23 +2082,21 @@ instantiate_scev_1 (struct loop *instantiation_loop,
 	}
 
       else if (res != chrec_dont_know)
-	res = instantiate_scev_1 (instantiation_loop, evolution_loop, res,
+	res = instantiate_scev_1 (instantiate_below, evolution_loop, res,
 				  fold_conversions, cache, size_expr);
 
-      bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
-
       /* Store the correct value to the cache.  */
-      set_instantiated_value (cache, chrec, res);
+      set_instantiated_value (cache, instantiate_below, chrec, res);
       return res;
 
     case POLYNOMIAL_CHREC:
-      op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				CHREC_LEFT (chrec), fold_conversions, cache,
 				size_expr);
       if (op0 == chrec_dont_know)
 	return chrec_dont_know;
 
-      op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				CHREC_RIGHT (chrec), fold_conversions, cache,
 				size_expr);
       if (op1 == chrec_dont_know)
@@ -2117,13 +2112,13 @@ instantiate_scev_1 (struct loop *instantiation_loop,
 
     case POINTER_PLUS_EXPR:
     case PLUS_EXPR:
-      op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 0), fold_conversions, cache,
 				size_expr);
       if (op0 == chrec_dont_know)
 	return chrec_dont_know;
 
-      op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 1), fold_conversions, cache,
 				size_expr);
       if (op1 == chrec_dont_know)
@@ -2139,13 +2134,13 @@ instantiate_scev_1 (struct loop *instantiation_loop,
       return chrec;
 
     case MINUS_EXPR:
-      op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 0), fold_conversions, cache,
 				size_expr);
       if (op0 == chrec_dont_know)
 	return chrec_dont_know;
 
-      op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 1),
 				fold_conversions, cache, size_expr);
       if (op1 == chrec_dont_know)
@@ -2161,13 +2156,13 @@ instantiate_scev_1 (struct loop *instantiation_loop,
       return chrec;
 
     case MULT_EXPR:
-      op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 0),
 				fold_conversions, cache, size_expr);
       if (op0 == chrec_dont_know)
 	return chrec_dont_know;
 
-      op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 1),
 				fold_conversions, cache, size_expr);
       if (op1 == chrec_dont_know)
@@ -2183,7 +2178,7 @@ instantiate_scev_1 (struct loop *instantiation_loop,
       return chrec;
 
     CASE_CONVERT:
-      op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 0),
 				fold_conversions, cache, size_expr);
       if (op0 == chrec_dont_know)
@@ -2221,19 +2216,19 @@ instantiate_scev_1 (struct loop *instantiation_loop,
   switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
     {
     case 3:
-      op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 0),
 				fold_conversions, cache, size_expr);
       if (op0 == chrec_dont_know)
 	return chrec_dont_know;
 
-      op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 1),
 				fold_conversions, cache, size_expr);
       if (op1 == chrec_dont_know)
 	return chrec_dont_know;
 
-      op2 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op2 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 2),
 				fold_conversions, cache, size_expr);
       if (op2 == chrec_dont_know)
@@ -2248,13 +2243,13 @@ instantiate_scev_1 (struct loop *instantiation_loop,
 			  TREE_TYPE (chrec), op0, op1, op2);
 
     case 2:
-      op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 0),
 				fold_conversions, cache, size_expr);
       if (op0 == chrec_dont_know)
 	return chrec_dont_know;
 
-      op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 1),
 				fold_conversions, cache, size_expr);
       if (op1 == chrec_dont_know)
@@ -2266,7 +2261,7 @@ instantiate_scev_1 (struct loop *instantiation_loop,
       return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
 	    
     case 1:
-      op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+      op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
 				TREE_OPERAND (chrec, 0),
 				fold_conversions, cache, size_expr);
       if (op0 == chrec_dont_know)
@@ -2287,12 +2282,13 @@ instantiate_scev_1 (struct loop *instantiation_loop,
 }
 
 /* Analyze all the parameters of the chrec that were left under a
-   symbolic form.  INSTANTIATION_LOOP is the loop in which symbolic
-   names have to be instantiated, and EVOLUTION_LOOP is the loop in
-   which the evolution of scalars have to be analyzed.  */
+   symbolic form.  INSTANTIATE_BELOW is the basic block that stops the
+   recursive instantiation of parameters: a parameter is a variable
+   that is defined in a basic block that dominates INSTANTIATE_BELOW or
+   a function parameter.  */
 
 tree
-instantiate_scev (struct loop *instantiation_loop, struct loop *evolution_loop,
+instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
 		  tree chrec)
 {
   tree res;
@@ -2301,14 +2297,14 @@ instantiate_scev (struct loop *instantiation_loop, struct loop *evolution_loop,
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "(instantiate_scev \n");
-      fprintf (dump_file, "  (instantiation_loop = %d)\n", instantiation_loop->num);
+      fprintf (dump_file, "  (instantiate_below = %d)\n", instantiate_below->index);
       fprintf (dump_file, "  (evolution_loop = %d)\n", evolution_loop->num);
       fprintf (dump_file, "  (chrec = ");
       print_generic_expr (dump_file, chrec, 0);
       fprintf (dump_file, ")\n");
     }
  
-  res = instantiate_scev_1 (instantiation_loop, evolution_loop, chrec, false,
+  res = instantiate_scev_1 (instantiate_below, evolution_loop, chrec, false,
 			    cache, 0);
 
   if (dump_file && (dump_flags & TDF_DETAILS))
@@ -2332,7 +2328,8 @@ tree
 resolve_mixers (struct loop *loop, tree chrec)
 {
   htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
-  tree ret = instantiate_scev_1 (loop, loop, chrec, true, cache, 0);
+  tree ret = instantiate_scev_1 (block_before_loop (loop), loop, chrec, true,
+				 cache, 0);
   htab_delete (cache);
   return ret;
 }
@@ -2677,7 +2674,6 @@ scev_initialize (void)
 					     del_scev_info,
 					     ggc_calloc,
 					     ggc_free);
-  already_instantiated = BITMAP_ALLOC (NULL);
   
   initialize_scalar_evolutions_analyzer ();
 
@@ -2791,7 +2787,6 @@ scev_finalize (void)
   if (!scalar_evolution_info)
     return;
   htab_delete (scalar_evolution_info);
-  BITMAP_FREE (already_instantiated);
   scalar_evolution_info = NULL;
 }