* tree-ssa-loop-niter.c (record_estimate): Add "upper" argument.

	Update constant estimates of number of iterations.
	(record_nonwrapping_iv): Add "upper" argument.  "data_size_bounds_p"
	argument renamed to "realistic".
	(compute_estimated_nb_iterations): Removed.
	(record_niter_bound): New function.
	(idx_infer_loop_bounds): For possible but unlikely tail arrays,
	call record_nonwrapping_iv with upper = false.
	(infer_loop_bounds_from_signedness): Pass upper argument to
	record_nonwrapping_iv.
	(estimate_numbers_of_iterations_loop): Do not call
	compute_estimated_nb_iterations.  Record estimate based on profile
	information.  Initialize the constant estimates of number of
	iterations.
	* tree-data-ref.c (estimated_loop_iterations): Return the recorded
	estimates.
	* tree-ssa-loop-prefetch.c (loop_prefetch_arrays): Add dump when
	number of iterations is too small.
	* cfgloop.h (struct nb_iter_bound): Remove "realistic" field.
	(EST_NOT_AVAILABLE): Removed.
	(struct loop): Replace estimated_nb_iterations by any_upper_bound,
	nb_iterations_upper_bound, any_estimate and nb_iterations_estimate
	fields.

	* gcc.dg/tree-ssa/prefetch-5.c: New test.



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

7 files changed, 235 insertions, 104 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 0825b1b8439..520f824c6f5 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,31 @@
 2007-03-15  Zdenek Dvorak  <dvorakz@suse.cz>
 
+	* tree-ssa-loop-niter.c (record_estimate): Add "upper" argument.
+	Update constant estimates of number of iterations.
+	(record_nonwrapping_iv): Add "upper" argument.  "data_size_bounds_p"
+	argument renamed to "realistic".
+	(compute_estimated_nb_iterations): Removed.
+	(record_niter_bound): New function.
+	(idx_infer_loop_bounds): For possible but unlikely tail arrays,
+	call record_nonwrapping_iv with upper = false.
+	(infer_loop_bounds_from_signedness): Pass upper argument to
+	record_nonwrapping_iv.
+	(estimate_numbers_of_iterations_loop): Do not call
+	compute_estimated_nb_iterations.  Record estimate based on profile
+	information.  Initialize the constant estimates of number of
+	iterations.
+	* tree-data-ref.c (estimated_loop_iterations): Return the recorded
+	estimates.
+	* tree-ssa-loop-prefetch.c (loop_prefetch_arrays): Add dump when
+	number of iterations is too small.
+	* cfgloop.h (struct nb_iter_bound): Remove "realistic" field.
+	(EST_NOT_AVAILABLE): Removed.
+	(struct loop): Replace estimated_nb_iterations by any_upper_bound,
+	nb_iterations_upper_bound, any_estimate and nb_iterations_estimate
+	fields.
+
+2007-03-15  Zdenek Dvorak  <dvorakz@suse.cz>
+
 	* tree-ssa-loop-niter.c (refine_bounds_using_guard, bound_difference):
 	Handle NE_EXPR guards.
 
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index c6cd7221aa7..c5c1cf25b42 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -65,12 +65,6 @@ struct nb_iter_bound
      are executed at most BOUND times.  */
   bool is_exit;
 
-  /* True if the bound is "realistic" -- i.e., most likely the loop really has
-     number of iterations close to the bound.  Exact bounds (if the number of
-     iterations of a loop is a constant) and bounds derived from the size of
-     data accessed in the loop are considered realistic.  */
-  bool realistic;
-
   /* The next bound in the list.  */
   struct nb_iter_bound *next;
 };
@@ -148,12 +142,18 @@ struct loop
     {
       /* Estimate was not computed yet.  */
       EST_NOT_COMPUTED,
-      /* Estimate was computed, but we could derive no useful bound.  */
-      EST_NOT_AVAILABLE,
       /* Estimate is ready.  */
       EST_AVAILABLE
     } estimate_state;
-  double_int estimated_nb_iterations;
+
+  /* An integer guaranteed to bound the number of iterations of the loop
+     from above.  */
+  bool any_upper_bound;
+  double_int nb_iterations_upper_bound;
+
+  /* An integer giving the expected number of iterations of the loop.  */
+  bool any_estimate;
+  double_int nb_iterations_estimate;
 
   /* Upper bound on number of iterations of a loop.  */
   struct nb_iter_bound *bounds;
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index b56294f0df6..8e8b8e70884 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2007-03-15  Zdenek Dvorak  <dvorakz@suse.cz>
+
+	* gcc.dg/tree-ssa/prefetch-5.c: New test.
+
 2007-03-15  Manuel Lopez-Ibanez  <manu@gcc.gnu.org>
 
 	PR c++/30891
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/prefetch-5.c b/gcc/testsuite/gcc.dg/tree-ssa/prefetch-5.c
new file mode 100644
index 00000000000..643ac8053e4
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/prefetch-5.c
@@ -0,0 +1,60 @@
+/* { dg-do compile { target i?86-*-* x86_64-*-* } } */
+/* { dg-require-effective-target ilp32 } */
+/* { dg-options "-O2 -fprefetch-loop-arrays -march=athlon -fdump-tree-aprefetch-details" } */
+
+/* These are common idioms for writing variable-length arrays at the end
+   of structures.  We should not deduce anything about the number of iterations
+   of the loops from them.  */
+
+struct tail0
+{
+  int xxx;
+  int yyy[0];
+};
+
+int loop0 (int n, struct tail0 *x)
+{
+  int i, s = 0;
+
+  for (i = 0; i < n; i++)
+    s += x->yyy[i];
+
+  return s;
+}
+
+struct tail1
+{
+  int xxx;
+  int yyy[1];
+};
+int loop1 (int n, struct tail1 *x)
+{
+  int i, s = 0;
+
+  for (i = 0; i < n; i++)
+    s += x->yyy[i];
+
+  return s;
+}
+
+/* It is unlikely that this should be a tail array.  We may deduce that most
+   likely, the loop iterates about 5 times, and the array is not worth prefetching.  */
+
+struct tail5
+{
+  int xxx;
+  int yyy[5];
+};
+int loop5 (int n, struct tail5 *x)
+{
+  int i, s = 0;
+
+  for (i = 0; i < n; i++)
+    s += x->yyy[i];
+
+  return s;
+}
+
+/* { dg-final { scan-tree-dump-times "Issued prefetch" 2 "aprefetch" } } */
+/* { dg-final { scan-tree-dump-times "Not prefetching" 1 "aprefetch" } } */
+/* { dg-final { cleanup-tree-dump "aprefetch" } } */
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index d59278c89f5..01bb71b5907 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -2556,33 +2556,23 @@ static bool
 estimated_loop_iterations (struct loop *loop, bool conservative,
 			   double_int *nit)
 {
-  tree numiter = number_of_exit_cond_executions (loop);
-
-  /* If we have an exact value, use it.  */
-  if (TREE_CODE (numiter) == INTEGER_CST)
+  estimate_numbers_of_iterations_loop (loop);
+  if (conservative)
     {
-      *nit = tree_to_double_int (numiter);
-      return true;
-    }
+      if (!loop->any_upper_bound)
+	return false;
 
-  /* If we have a measured profile and we do not ask for a conservative bound,
-     use it.  */
-  if (!conservative && loop->header->count != 0)
-    {
-      *nit = uhwi_to_double_int (expected_loop_iterations (loop) + 1);
-      return true;
+      *nit = loop->nb_iterations_upper_bound;
     }
-
-  /* Finally, try using a reliable estimate on number of iterations according
-     to the size of the accessed data, if available.  */
-  estimate_numbers_of_iterations_loop (loop);
-  if (loop->estimate_state == EST_AVAILABLE)
+  else
     {
-      *nit = loop->estimated_nb_iterations;
-      return true;
+      if (!loop->any_estimate)
+	return false;
+
+      *nit = loop->nb_iterations_estimate;
     }
 
-  return false;
+  return true;
 }
 
 /* Similar to estimated_loop_iterations, but returns the estimate only
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 688bc3910f6..909f5fcd30a 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -2386,46 +2386,110 @@ derive_constant_upper_bound (tree val)
     }
 }
 
+/* Records that every statement in LOOP is executed I_BOUND times.
+   REALISTIC is true if I_BOUND is expected to be close the the real number
+   of iterations.  UPPER is true if we are sure the loop iterates at most
+   I_BOUND times.  */
+
+static void
+record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
+		    bool upper)
+{
+  /* Update the bounds only when there is no previous estimation, or when the current
+     estimation is smaller.  */
+  if (upper
+      && (!loop->any_upper_bound
+	  || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
+    {
+      loop->any_upper_bound = true;
+      loop->nb_iterations_upper_bound = i_bound;
+    }
+  if (realistic
+      && (!loop->any_estimate
+	  || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
+    {
+      loop->any_estimate = true;
+      loop->nb_iterations_estimate = i_bound;
+    }
+}
+
 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP.  IS_EXIT
    is true if the loop is exited immediately after STMT, and this exit
    is taken at last when the STMT is executed BOUND + 1 times.
-   REALISTIC is true if the estimate comes from a reliable source
-   (number of iterations analysis, or size of data accessed in the loop).
-   I_BOUND is an unsigned double_int upper estimate on BOUND.  */
+   REALISTIC is true if BOUND is expected to be close the the real number
+   of iterations.  UPPER is true if we are sure the loop iterates at most
+   BOUND times.  I_BOUND is an unsigned double_int upper estimate on BOUND.  */
 
 static void
 record_estimate (struct loop *loop, tree bound, double_int i_bound,
-		 tree at_stmt, bool is_exit, bool realistic)
+		 tree at_stmt, bool is_exit, bool realistic, bool upper)
 {
-  struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
+  double_int delta;
+  edge exit;
 
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
       print_generic_expr (dump_file, at_stmt, TDF_SLIM);
-      fprintf (dump_file, " is executed at most ");
+      fprintf (dump_file, " is %sexecuted at most ",
+	       upper ? "" : "probably ");
       print_generic_expr (dump_file, bound, TDF_SLIM);
       fprintf (dump_file, " (bounded by ");
       dump_double_int (dump_file, i_bound, true);
       fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
     }
 
-  elt->bound = i_bound;
-  elt->stmt = at_stmt;
-  elt->is_exit = is_exit;
-  elt->realistic = realistic && TREE_CODE (bound) == INTEGER_CST;
-  elt->next = loop->bounds;
-  loop->bounds = elt;
+  /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
+     real number of iterations.  */
+  if (TREE_CODE (bound) != INTEGER_CST)
+    realistic = false;
+  if (!upper && !realistic)
+    return;
+
+  /* If we have a guaranteed upper bound, record it in the appropriate
+     list.  */
+  if (upper)
+    {
+      struct nb_iter_bound *elt = XNEW (struct nb_iter_bound);
+
+      elt->bound = i_bound;
+      elt->stmt = at_stmt;
+      elt->is_exit = is_exit;
+      elt->next = loop->bounds;
+      loop->bounds = elt;
+    }
+
+  /* Update the number of iteration estimates according to the bound.
+     If at_stmt is an exit, then every statement in the loop is
+     executed at most BOUND + 1 times.  If it is not an exit, then
+     some of the statements before it could be executed BOUND + 2
+     times, if an exit of LOOP is before stmt.  */
+  exit = single_exit (loop);
+  if (is_exit
+      || (exit != NULL
+	  && dominated_by_p (CDI_DOMINATORS,
+			     exit->src, bb_for_stmt (at_stmt))))
+    delta = double_int_one;
+  else
+    delta = double_int_two;
+  i_bound = double_int_add (i_bound, delta);
+
+  /* If an overflow occured, ignore the result.  */
+  if (double_int_ucmp (i_bound, delta) < 0)
+    return;
+
+  record_niter_bound (loop, i_bound, realistic, upper);
 }
 
 /* Record the estimate on number of iterations of LOOP based on the fact that
    the induction variable BASE + STEP * i evaluated in STMT does not wrap and
-   its values belong to the range <LOW, HIGH>.  DATA_SIZE_BOUNDS_P is true if
-   LOW and HIGH are derived from the size of data.  */
+   its values belong to the range <LOW, HIGH>.  REALISTIC is true if the
+   estimated number of iterations is expected to be close to the real one.
+   UPPER is true if we are sure the induction variable does not wrap.  */
 
 static void
 record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
-		       tree low, tree high, bool data_size_bounds_p)
+		       tree low, tree high, bool realistic, bool upper)
 {
   tree niter_bound, extreme, delta;
   tree type = TREE_TYPE (base), unsigned_type;
@@ -2471,55 +2535,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
      would get out of the range.  */
   niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
   max = derive_constant_upper_bound (niter_bound);
-  record_estimate (loop, niter_bound, max, stmt, false, data_size_bounds_p);
-}
-
-/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
-   approximation of the number of iterations for LOOP.  */
-
-static void
-compute_estimated_nb_iterations (struct loop *loop)
-{
-  struct nb_iter_bound *bound;
-  double_int bnd_val, delta;
-  edge exit;
- 
-  gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE);
-
-  for (bound = loop->bounds; bound; bound = bound->next)
-    {
-      if (!bound->realistic)
-	continue;
-
-      bnd_val = bound->bound;
-      /* If bound->stmt is an exit, then every statement in the loop is
-	 executed at most BND_VAL + 1 times.  If it is not an exit, then
-	 some of the statements before it could be executed BND_VAL + 2
-	 times, if an exit of LOOP is before stmt.  */
-      exit = single_exit (loop);
-
-      if (bound->is_exit
-	  || (exit != NULL
-	      && dominated_by_p (CDI_DOMINATORS,
-				 exit->src, bb_for_stmt (bound->stmt))))
-	delta = double_int_one;
-      else
-	delta = double_int_two;
-      bnd_val = double_int_add (bnd_val, delta);
-
-      /* If an overflow occured, ignore the result.  */
-      if (double_int_ucmp (bnd_val, delta) < 0)
-	continue;
-
-      /* Update only when there is no previous estimation, or when the current
-	 estimation is smaller.  */
-      if (loop->estimate_state == EST_NOT_AVAILABLE
-	  || double_int_ucmp (bnd_val, loop->estimated_nb_iterations) < 0)
-	{
-	  loop->estimate_state = EST_AVAILABLE;
-	  loop->estimated_nb_iterations = bnd_val;
-	}
-    }
+  record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
 }
 
 /* Returns true if REF is a reference to an array at the end of a dynamically
@@ -2579,13 +2595,18 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta)
   struct ilb_data *data = dta;
   tree ev, init, step;
   tree low, high, type, next;
-  bool sign;
+  bool sign, upper = true;
   struct loop *loop = data->loop;
 
-  if (TREE_CODE (base) != ARRAY_REF
-      || array_at_struct_end_p (base))
+  if (TREE_CODE (base) != ARRAY_REF)
     return true;
 
+  /* For arrays at the end of the structure, we are not guaranteed that they
+     do not really extend over their declared size.  However, for arrays of
+     size greater than one, this is unlikely to be intended.  */
+  if (array_at_struct_end_p (base))
+    upper = false;
+
   ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
   init = initial_condition (ev);
   step = evolution_part_in_loop_num (ev, loop->num);
@@ -2609,7 +2630,13 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta)
     return true;
   sign = tree_int_cst_sign_bit (step);
   type = TREE_TYPE (step);
-  
+
+  /* The array of length 1 at the end of a structure most likely extends
+     beyond its bounds.  */
+  if (!upper
+      && operand_equal_p (low, high, 0))
+    return true;
+
   /* In case the relevant bound of the array does not fit in type, or
      it does, but bound + step (in type) still belongs into the range of the
      array, the index may wrap and still stay within the range of the array
@@ -2633,7 +2660,7 @@ idx_infer_loop_bounds (tree base, tree *idx, void *dta)
       && tree_int_cst_compare (next, high) <= 0)
     return true;
 
-  record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true);
+  record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
   return true;
 }
 
@@ -2722,7 +2749,7 @@ infer_loop_bounds_from_signedness (struct loop *loop, tree stmt)
   low = lower_bound_in_type (type, type);
   high = upper_bound_in_type (type, type);
 
-  record_nonwrapping_iv (loop, base, step, stmt, low, high, false);
+  record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
 }
 
 /* The following analyzers are extracting informations on the bounds
@@ -2776,11 +2803,14 @@ estimate_numbers_of_iterations_loop (struct loop *loop)
   unsigned i;
   struct tree_niter_desc niter_desc;
   edge ex;
+  double_int bound;
 
   /* Give up if we already have tried to compute an estimation.  */
   if (loop->estimate_state != EST_NOT_COMPUTED)
     return;
-  loop->estimate_state = EST_NOT_AVAILABLE;
+  loop->estimate_state = EST_AVAILABLE;
+  loop->any_upper_bound = false;
+  loop->any_estimate = false;
 
   exits = get_loop_exit_edges (loop);
   for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
@@ -2796,12 +2826,27 @@ estimate_numbers_of_iterations_loop (struct loop *loop)
 			niter);
       record_estimate (loop, niter, niter_desc.max,
 		       last_stmt (ex->src),
-		       true, true);
+		       true, true, true);
     }
   VEC_free (edge, heap, exits);
   
   infer_loop_bounds_from_undefined (loop);
-  compute_estimated_nb_iterations (loop);
+
+  /* If we have a measured profile, use it to estimate the number of
+     iterations.  */
+  if (loop->header->count != 0)
+    {
+      bound = uhwi_to_double_int (expected_loop_iterations (loop) + 1);
+      record_niter_bound (loop, bound, true, false);
+    }
+
+  /* If an upper bound is smaller than the realistic estimate of the
+     number of iterations, use the upper bound instead.  */
+  if (loop->any_upper_bound
+      && loop->any_estimate
+      && double_int_ucmp (loop->nb_iterations_upper_bound,
+			  loop->nb_iterations_estimate) < 0)
+    loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
 }
 
 /* Records estimates on numbers of iterations of loops.  */
diff --git a/gcc/tree-ssa-loop-prefetch.c b/gcc/tree-ssa-loop-prefetch.c
index 53977d8bddd..a0d70cc382f 100644
--- a/gcc/tree-ssa-loop-prefetch.c
+++ b/gcc/tree-ssa-loop-prefetch.c
@@ -968,7 +968,13 @@ loop_prefetch_arrays (struct loop *loop)
      the loop rolls at least AHEAD times, prefetching the references does not
      make sense.  */
   if (est_niter >= 0 && est_niter <= (HOST_WIDE_INT) ahead)
-    goto fail;
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file,
+		 "Not prefetching -- loop estimated to roll only %d times\n",
+		 (int) est_niter);
+      goto fail;
+    }
 
   ninsns = tree_num_loop_insns (loop, &eni_size_weights);
   unroll_factor = determine_unroll_factor (loop, refs, ninsns, &desc,