* tree-scalar-evolution.c (analyze_scalar_evolution_in_loop):

	Extend comments.
	(simple_iv):  Take loop as an argument instead of statement.
	* tree-scalar-evolution.h (simple_iv): Declaration changed.
	* tree-ssa-loop-niter.c (number_of_iterations_exit): Update calls
	to simple_iv.
	* tree-ssa-loop-ivopts.c (determine_biv_step, find_givs_in_stmt_scev):
	Ditto.
	* tree-parloops.c (loop_parallel_p, canonicalize_loop_ivs): Ditto.
	* matrix-reorg.c (analyze_transpose): Ditto.
	* tree-data-ref.c (dr_analyze_innermost): Ditto.
	* tree-vect-analyze.c (vect_analyze_data_refs): Ditto.
	* tree-predcom.c (ref_at_iteration): Ditto.
	* tree-ssa-loop-prefetch.c (idx_analyze_ref): Ditto.



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

11 files changed, 129 insertions, 39 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index b75d2ddb3fa..451eafaddda 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,20 @@
+2009-03-04  Zdenek Dvorak  <ook@ucw.cz>
+
+	* tree-scalar-evolution.c (analyze_scalar_evolution_in_loop):
+	Extend comments.
+	(simple_iv):  Take loop as an argument instead of statement.
+	* tree-scalar-evolution.h (simple_iv): Declaration changed.
+	* tree-ssa-loop-niter.c (number_of_iterations_exit): Update calls
+	to simple_iv.
+	* tree-ssa-loop-ivopts.c (determine_biv_step, find_givs_in_stmt_scev):
+	Ditto.
+	* tree-parloops.c (loop_parallel_p, canonicalize_loop_ivs): Ditto.
+	* matrix-reorg.c (analyze_transpose): Ditto.
+	* tree-data-ref.c (dr_analyze_innermost): Ditto.
+	* tree-vect-analyze.c (vect_analyze_data_refs): Ditto.
+	* tree-predcom.c (ref_at_iteration): Ditto.
+	* tree-ssa-loop-prefetch.c (idx_analyze_ref): Ditto.
+
 2009-03-04  Richard Guenther  <rguenther@suse.de>
 
 	PR tree-optimization/39358
diff --git a/gcc/matrix-reorg.c b/gcc/matrix-reorg.c
index c1d5ca0caa3..7ea185ced20 100644
--- a/gcc/matrix-reorg.c
+++ b/gcc/matrix-reorg.c
@@ -930,7 +930,7 @@ analyze_transpose (void **slot, void *data ATTRIBUTE_UNUSED)
 	      free (acc_info);
 	      continue;
 	    }
-	  if (simple_iv (loop, acc_info->stmt, acc_info->offset, &iv, true))
+	  if (simple_iv (loop, loop, acc_info->offset, &iv, true))
 	    {
 	      if (iv.step != NULL)
 		{
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index bc9737dd951..7c062602a1a 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -698,7 +698,7 @@ dr_analyze_innermost (struct data_reference *dr)
     }
 
   base = build_fold_addr_expr (base);
-  if (!simple_iv (loop, stmt, base, &base_iv, false))
+  if (!simple_iv (loop, loop_containing_stmt (stmt), base, &base_iv, false))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "failed: evolution of base is not affine.\n");
@@ -709,7 +709,8 @@ dr_analyze_innermost (struct data_reference *dr)
       offset_iv.base = ssize_int (0);
       offset_iv.step = ssize_int (0);
     }
-  else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
+  else if (!simple_iv (loop, loop_containing_stmt (stmt),
+		       poffset, &offset_iv, false))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "failed: evolution of offset is not affine.\n");
diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c
index f2d0ff63f17..4e9b102973a 100644
--- a/gcc/tree-parloops.c
+++ b/gcc/tree-parloops.c
@@ -385,7 +385,7 @@ loop_parallel_p (struct loop *loop, htab_t reduction_list,
       tree def = PHI_RESULT (phi);
       affine_iv iv;
 
-      if (is_gimple_reg (def) && !simple_iv (loop, phi, def, &iv, true))
+      if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
 	{
 	  struct reduction_info *red;
 
@@ -1380,7 +1380,7 @@ canonicalize_loop_ivs (struct loop *loop, htab_t reduction_list, tree *nit)
 	  continue;
 	}
 
-      ok = simple_iv (loop, phi, res, &iv, true);
+      ok = simple_iv (loop, loop, res, &iv, true);
 
       if (reduction_list)
 	red = reduction_phi (reduction_list, phi);
diff --git a/gcc/tree-predcom.c b/gcc/tree-predcom.c
index 5ce8c3ea066..bd82a8016fb 100644
--- a/gcc/tree-predcom.c
+++ b/gcc/tree-predcom.c
@@ -1374,7 +1374,7 @@ ref_at_iteration (struct loop *loop, tree ref, int iter)
   else
     return NULL_TREE;
 
-  ok = simple_iv (loop, first_stmt (loop->header), idx, &iv, true);
+  ok = simple_iv (loop, loop, idx, &iv, true);
   if (!ok)
     return NULL_TREE;
   iv.base = expand_simple_operations (iv.base);
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index d7f97d705a1..8e12c2b32ab 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -1915,12 +1915,54 @@ analyze_scalar_evolution (struct loop *loop, tree var)
 }
 
 /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
-   WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
-   of VERSION).
+   WRTO_LOOP (which should be a superloop of USE_LOOP)
 
    FOLDED_CASTS is set to true if resolve_mixers used
    chrec_convert_aggressive (TODO -- not really, we are way too conservative
-   at the moment in order to keep things simple).  */
+   at the moment in order to keep things simple). 
+   
+   To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
+   example:
+
+   for (i = 0; i < 100; i++)			-- loop 1
+     {
+       for (j = 0; j < 100; j++)		-- loop 2
+         {
+	   k1 = i;
+	   k2 = j;
+
+	   use2 (k1, k2);
+
+	   for (t = 0; t < 100; t++)		-- loop 3
+	     use3 (k1, k2);
+
+	 }
+       use1 (k1, k2);
+     }
+
+   Both k1 and k2 are invariants in loop3, thus
+     analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
+     analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
+
+   As they are invariant, it does not matter whether we consider their
+   usage in loop 3 or loop 2, hence
+     analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
+       analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
+     analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
+       analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
+
+   Similarly for their evolutions with respect to loop 1.  The values of K2
+   in the use in loop 2 vary independently on loop 1, thus we cannot express
+   the evolution with respect to loop 1:
+     analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
+       analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
+     analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
+       analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
+
+   The value of k2 in the use in loop 1 is known, though:
+     analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
+     analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
+   */
 
 static tree
 analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
@@ -1929,6 +1971,25 @@ analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
   bool val = false;
   tree ev = version, tmp;
 
+  /* We cannot just do 
+
+     tmp = analyze_scalar_evolution (use_loop, version);
+     ev = resolve_mixers (wrto_loop, tmp);
+
+     as resolve_mixers would query the scalar evolution with respect to
+     wrto_loop.  For example, in the situation described in the function
+     comment, suppose that wrto_loop = loop1, use_loop = loop3 and
+     version = k2.  Then
+
+     analyze_scalar_evolution (use_loop, version) = k2
+
+     and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
+     is 100, which is a wrong result, since we are interested in the
+     value in loop 3.
+
+     Instead, we need to proceed from use_loop to wrto_loop loop by loop,
+     each time checking that there is no evolution in the inner loop.  */
+
   if (folded_casts)
     *folded_casts = false;
   while (1)
@@ -2743,17 +2804,31 @@ scev_reset (void)
     }
 }
 
-/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
-   its base and step in IV if possible.  If ALLOW_NONCONSTANT_STEP is true, we
-   want step to be invariant in LOOP.  Otherwise we require it to be an
-   integer constant.  IV->no_overflow is set to true if we are sure the iv cannot
-   overflow (e.g.  because it is computed in signed arithmetics).  */
+/* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
+   respect to WRTO_LOOP and returns its base and step in IV if possible
+   (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
+   and WRTO_LOOP).  If ALLOW_NONCONSTANT_STEP is true, we want step to be
+   invariant in LOOP.  Otherwise we require it to be an integer constant.
+   
+   IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
+   because it is computed in signed arithmetics).  Consequently, adding an
+   induction variable
+   
+   for (i = IV->base; ; i += IV->step)
+
+   is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
+   false for the type of the induction variable, or you can prove that i does
+   not wrap by some other argument.  Otherwise, this might introduce undefined
+   behavior, and
+   
+   for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
+
+   must be used instead.  */
 
 bool
-simple_iv (struct loop *loop, gimple stmt, tree op, affine_iv *iv,
-	   bool allow_nonconstant_step)
+simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
+	   affine_iv *iv, bool allow_nonconstant_step)
 {
-  basic_block bb = gimple_bb (stmt);
   tree type, ev;
   bool folded_casts;
 
@@ -2766,13 +2841,13 @@ simple_iv (struct loop *loop, gimple stmt, tree op, affine_iv *iv,
       && TREE_CODE (type) != POINTER_TYPE)
     return false;
 
-  ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
+  ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
 					 &folded_casts);
-  if (chrec_contains_undetermined (ev))
+  if (chrec_contains_undetermined (ev)
+      || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
     return false;
 
-  if (tree_does_not_contain_chrecs (ev)
-      && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
+  if (tree_does_not_contain_chrecs (ev))
     {
       iv->base = ev;
       iv->step = build_int_cst (TREE_TYPE (ev), 0);
@@ -2781,22 +2856,16 @@ simple_iv (struct loop *loop, gimple stmt, tree op, affine_iv *iv,
     }
 
   if (TREE_CODE (ev) != POLYNOMIAL_CHREC
-      || CHREC_VARIABLE (ev) != (unsigned) loop->num)
+      || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
     return false;
 
   iv->step = CHREC_RIGHT (ev);
-  if (allow_nonconstant_step)
-    {
-      if (tree_contains_chrecs (iv->step, NULL)
-	  || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
-	return false;
-    }
-  else if (TREE_CODE (iv->step) != INTEGER_CST)
+  if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
+      || tree_contains_chrecs (iv->step, NULL))
     return false;
 
   iv->base = CHREC_LEFT (ev);
-  if (tree_contains_chrecs (iv->base, NULL)
-      || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
+  if (tree_contains_chrecs (iv->base, NULL))
     return false;
 
   iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h
index 072f25d2963..06324972ca5 100644
--- a/gcc/tree-scalar-evolution.h
+++ b/gcc/tree-scalar-evolution.h
@@ -36,7 +36,7 @@ extern void scev_analysis (void);
 unsigned int scev_const_prop (void);
 
 bool expression_expensive_p (tree);
-extern bool simple_iv (struct loop *, gimple, tree, affine_iv *, bool);
+extern bool simple_iv (struct loop *, struct loop *, tree, affine_iv *, bool);
 
 /* Returns the basic block preceding LOOP or ENTRY_BLOCK_PTR when the
    loop is function's body.  */
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index b1813d373dc..c7bfa07be80 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -884,7 +884,7 @@ determine_biv_step (gimple phi)
   if (!is_gimple_reg (name))
     return NULL_TREE;
 
-  if (!simple_iv (loop, phi, name, &iv, true))
+  if (!simple_iv (loop, loop, name, &iv, true))
     return NULL_TREE;
 
   return integer_zerop (iv.step) ? NULL_TREE : iv.step;
@@ -990,7 +990,7 @@ find_givs_in_stmt_scev (struct ivopts_data *data, gimple stmt, affine_iv *iv)
   if (TREE_CODE (lhs) != SSA_NAME)
     return false;
 
-  if (!simple_iv (loop, stmt, lhs, iv, true))
+  if (!simple_iv (loop, loop_containing_stmt (stmt), lhs, iv, true))
     return false;
   iv->base = expand_simple_operations (iv->base);
 
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 13b10c9f1c4..c67e638d58a 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1781,9 +1781,9 @@ number_of_iterations_exit (struct loop *loop, edge exit,
       && !POINTER_TYPE_P (type))
     return false;
      
-  if (!simple_iv (loop, stmt, op0, &iv0, false))
+  if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
     return false;
-  if (!simple_iv (loop, stmt, op1, &iv1, false))
+  if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
     return false;
 
   /* We don't want to see undefined signed overflow warnings while
diff --git a/gcc/tree-ssa-loop-prefetch.c b/gcc/tree-ssa-loop-prefetch.c
index 6da4bf232aa..d0e460cf92e 100644
--- a/gcc/tree-ssa-loop-prefetch.c
+++ b/gcc/tree-ssa-loop-prefetch.c
@@ -364,7 +364,8 @@ idx_analyze_ref (tree base, tree *index, void *data)
       || TREE_CODE (base) == ALIGN_INDIRECT_REF)
     return false;
 
-  if (!simple_iv (ar_data->loop, ar_data->stmt, *index, &iv, false))
+  if (!simple_iv (ar_data->loop, loop_containing_stmt (ar_data->stmt),
+		  *index, &iv, false))
     return false;
   ibase = iv.base;
   step = iv.step;
diff --git a/gcc/tree-vect-analyze.c b/gcc/tree-vect-analyze.c
index a4460b49168..0b947143c68 100644
--- a/gcc/tree-vect-analyze.c
+++ b/gcc/tree-vect-analyze.c
@@ -3622,7 +3622,8 @@ vect_analyze_data_refs (loop_vec_info loop_vinfo)
 	    }
 
 	  outer_base = build_fold_addr_expr (outer_base);
-	  if (!simple_iv (loop, stmt, outer_base, &base_iv, false))
+	  if (!simple_iv (loop, loop_containing_stmt (stmt), outer_base,
+			  &base_iv, false))
 	    {
 	      if (vect_print_dump_info (REPORT_DETAILS))
 		fprintf (vect_dump, "failed: evolution of base is not affine.\n");
@@ -3642,7 +3643,8 @@ vect_analyze_data_refs (loop_vec_info loop_vinfo)
 	      offset_iv.base = ssize_int (0);
 	      offset_iv.step = ssize_int (0);
 	    }
-	  else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
+	  else if (!simple_iv (loop, loop_containing_stmt (stmt), poffset,
+			       &offset_iv, false))
 	    {
 	      if (vect_print_dump_info (REPORT_DETAILS))
 	        fprintf (vect_dump, "evolution of offset is not affine.\n");