2011-06-14 Zdenek Dvorak <ook@ucw.cz>

	    Tom de Vries  <tom@codesourcery.com>

	PR target/45098
	* cfgloop.h (nb_iterations_upper_bound, nb_iterations_estimate):
	Document changed semantics.
	(max_stmt_executions, max_stmt_executions_int): Declare.
	* tree-data-ref.c (estimated_loop_iterations)
	(estimated_loop_iterations_int): Move functions...
	* tree-ssa-loop-niter.c (estimated_loop_iterations)
	(estimated_loop_iterations_int): here.
	(record_estimate): Change nb_iterations_upper_bound and
	nb_iterations_estimate semantics.
	(max_stmt_executions, max_stmt_executions_int): New function.
	* tree-data-ref.c (estimated_loop_iterations_tree): Rename to ...
	(max_stmt_executions_tree): this.
	(analyze_miv_subscript): Use max_stmt_executions_tree instead of
	estimated_loop_iterations_tree.
	tree-ssa-loop-ivopts.c (avg_loop_niter): Use
	max_stmt_executions_int instead of estimated_loop_iterations_int.
	* predict.c (predict_loops): Idem.
	* tree-parloops.c (parallelize_loops): Idem.
	* tree-data-ref.c (analyze_siv_subscript_cst_affine)
	(compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine)
	(init_omega_for_ddr_1): Idem.
	* tree-ssa-loop-prefetch.c (determine_loop_nest_reuse)
	(loop_prefetch_arrays): Idem
	* graphite-sese-to-poly.c (build_loop_iteration_domains): Use
	max_stmt_executions instead of estimated_loop_iterations.
	* tree-data-ref.c (estimated_loop_iterations_tree): Idem.
	* tree-vrp.c (adjust_range_with_scev): Use estimated_loop_iterations
	instead of nb_iterations_upper_bound.


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

1 files changed, 92 insertions, 6 deletions

diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 230593ad264..fa3ccc63f59 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -2568,18 +2568,17 @@ record_estimate (struct loop *loop, tree bound, double_int i_bound,
     }
 
   /* 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.  */
+     If at_stmt is an exit or dominates the single exit from the loop,
+     then the loop latch is executed at most BOUND times, otherwise
+     it can be executed BOUND + 1 times.  */
   exit = single_exit (loop);
   if (is_exit
       || (exit != NULL
 	  && dominated_by_p (CDI_DOMINATORS,
 			     exit->src, gimple_bb (at_stmt))))
-    delta = double_int_one;
+    delta = double_int_zero;
   else
-    delta = double_int_two;
+    delta = double_int_one;
   i_bound = double_int_add (i_bound, delta);
 
   /* If an overflow occurred, ignore the result.  */
@@ -3042,6 +3041,93 @@ estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
     loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
 }
 
+/* Sets NIT to the estimated number of executions of the latch of the
+   LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
+   large as the number of iterations.  If we have no reliable estimate,
+   the function returns false, otherwise returns true.  */
+
+bool
+estimated_loop_iterations (struct loop *loop, bool conservative,
+			   double_int *nit)
+{
+  estimate_numbers_of_iterations_loop (loop, true);
+  if (conservative)
+    {
+      if (!loop->any_upper_bound)
+	return false;
+
+      *nit = loop->nb_iterations_upper_bound;
+    }
+  else
+    {
+      if (!loop->any_estimate)
+	return false;
+
+      *nit = loop->nb_iterations_estimate;
+    }
+
+  return true;
+}
+
+/* Similar to estimated_loop_iterations, but returns the estimate only
+   if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
+   on the number of iterations of LOOP could not be derived, returns -1.  */
+
+HOST_WIDE_INT
+estimated_loop_iterations_int (struct loop *loop, bool conservative)
+{
+  double_int nit;
+  HOST_WIDE_INT hwi_nit;
+
+  if (!estimated_loop_iterations (loop, conservative, &nit))
+    return -1;
+
+  if (!double_int_fits_in_shwi_p (nit))
+    return -1;
+  hwi_nit = double_int_to_shwi (nit);
+
+  return hwi_nit < 0 ? -1 : hwi_nit;
+}
+
+/* Returns an upper bound on the number of executions of statements
+   in the LOOP.  For statements before the loop exit, this exceeds
+   the number of execution of the latch by one.  */
+
+HOST_WIDE_INT
+max_stmt_executions_int (struct loop *loop, bool conservative)
+{
+  HOST_WIDE_INT nit = estimated_loop_iterations_int (loop, conservative);
+  HOST_WIDE_INT snit;
+
+  if (nit == -1)
+    return -1;
+
+  snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
+
+  /* If the computation overflows, return -1.  */
+  return snit < 0 ? -1 : snit;
+}
+
+/* Sets NIT to the estimated number of executions of the latch of the
+   LOOP, plus one.  If CONSERVATIVE is true, we must be sure that NIT is at
+   least as large as the number of iterations.  If we have no reliable
+   estimate, the function returns false, otherwise returns true.  */
+
+bool
+max_stmt_executions (struct loop *loop, bool conservative, double_int *nit)
+{
+  double_int nit_minus_one;
+
+  if (!estimated_loop_iterations (loop, conservative, nit))
+    return false;
+
+  nit_minus_one = *nit;
+
+  *nit = double_int_add (*nit, double_int_one);
+
+  return double_int_ucmp (*nit, nit_minus_one) > 0;
+}
+
 /* Records estimates on numbers of iterations of loops.  */
 
 void