cfgloop.c (record_niter_bound): Record likely upper bounds.

	* cfgloop.c (record_niter_bound): Record likely upper bounds.
	(likely_max_stmt_executions_int, get_likely_max_loop_iterations,
	get_likely_max_loop_iterations_int): New.
	* cfgloop.h (struct loop): Add nb_iterations_likely_upper_bound,
	any_likely_upper_bound.
	(get_likely_max_loop_iterations_int, get_likely_max_loop_iterations):
	Declare.
	* cfgloopmanip.c (copy_loop_info): Copy likely upper bounds.
	* loop-unroll.c (unroll_loop_constant_iterations): Update likely
	upper bound.
	(unroll_loop_constant_iterations): Likewise.
	(unroll_loop_runtime_iterations): Likewise.
	* lto-streamer-in.c (input_cfg): Stream likely upper bounds.
	* lto-streamer-out.c (output_cfg): Likewise.
	* tree-ssa-loop-ivcanon.c (try_peel_loop): Update likely upper
	bounds.
	(canonicalize_loop_induction_variables): Dump likely upper bounds.
	* tree-ssa-loop-niter.c (record_estimate): Record likely upper bounds.
	(likely_max_loop_iterations): New.
	(likely_max_loop_iterations_int): New.
	(likely_max_stmt_executions): New.
	* tree-ssa-loop-niter.h (likely_max_loop_iterations,
	likely_max_loop_iterations_int, likely_max_stmt_executions_int,
	likely_max_stmt_executions): Declare.

From-SVN: r236816

10 files changed, 205 insertions, 5 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 14ba165..eb34a28 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,30 @@
+2016-05-27  Jan Hubicka  <hubicka@ucw.cz>
+
+	* cfgloop.c (record_niter_bound): Record likely upper bounds.
+	(likely_max_stmt_executions_int, get_likely_max_loop_iterations,
+	get_likely_max_loop_iterations_int): New.
+	* cfgloop.h (struct loop): Add nb_iterations_likely_upper_bound,
+	any_likely_upper_bound.
+	(get_likely_max_loop_iterations_int, get_likely_max_loop_iterations):
+	Declare.
+	* cfgloopmanip.c (copy_loop_info): Copy likely upper bounds.
+	* loop-unroll.c (unroll_loop_constant_iterations): Update likely
+	upper bound.
+	(unroll_loop_constant_iterations): Likewise.
+	(unroll_loop_runtime_iterations): Likewise.
+	* lto-streamer-in.c (input_cfg): Stream likely upper bounds.
+	* lto-streamer-out.c (output_cfg): Likewise.
+	* tree-ssa-loop-ivcanon.c (try_peel_loop): Update likely upper
+	bounds.
+	(canonicalize_loop_induction_variables): Dump likely upper bounds.
+	* tree-ssa-loop-niter.c (record_estimate): Record likely upper bounds.
+	(likely_max_loop_iterations): New.
+	(likely_max_loop_iterations_int): New.
+	(likely_max_stmt_executions): New.
+	* tree-ssa-loop-niter.h (likely_max_loop_iterations,
+	likely_max_loop_iterations_int, likely_max_stmt_executions_int,
+	likely_max_stmt_executions): Declare.
+
 2016-05-27  Marek Polacek  <polacek@redhat.com>
 
 	PR middle-end/71308
diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
index 0223417..27ccfb2 100644
--- a/gcc/cfgloop.c
+++ b/gcc/cfgloop.c
@@ -1790,6 +1790,11 @@ record_niter_bound (struct loop *loop, const widest_int &i_bound,
     {
       loop->any_upper_bound = true;
       loop->nb_iterations_upper_bound = i_bound;
+      if (!loop->any_likely_upper_bound)
+	{
+	  loop->any_likely_upper_bound = true;
+	  loop->nb_iterations_likely_upper_bound = i_bound;
+	}
     }
   if (realistic
       && (!loop->any_estimate
@@ -1798,6 +1803,13 @@ record_niter_bound (struct loop *loop, const widest_int &i_bound,
       loop->any_estimate = true;
       loop->nb_iterations_estimate = i_bound;
     }
+  if (!realistic
+      && (!loop->any_likely_upper_bound
+          || wi::ltu_p (i_bound, loop->nb_iterations_likely_upper_bound)))
+    {
+      loop->any_likely_upper_bound = true;
+      loop->nb_iterations_likely_upper_bound = i_bound;
+    }
 
   /* If an upper bound is smaller than the realistic estimate of the
      number of iterations, use the upper bound instead.  */
@@ -1806,6 +1818,11 @@ record_niter_bound (struct loop *loop, const widest_int &i_bound,
       && wi::ltu_p (loop->nb_iterations_upper_bound,
 		    loop->nb_iterations_estimate))
     loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
+  if (loop->any_upper_bound
+      && loop->any_likely_upper_bound
+      && wi::ltu_p (loop->nb_iterations_upper_bound,
+		    loop->nb_iterations_likely_upper_bound))
+    loop->nb_iterations_likely_upper_bound = loop->nb_iterations_upper_bound;
 }
 
 /* Similar to get_estimated_loop_iterations, but returns the estimate only
@@ -1847,6 +1864,25 @@ max_stmt_executions_int (struct loop *loop)
   return snit < 0 ? -1 : snit;
 }
 
+/* Returns an likely 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
+likely_max_stmt_executions_int (struct loop *loop)
+{
+  HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
+  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.  If we have no reliable estimate, the function returns false, otherwise
    returns true.  */
@@ -1905,6 +1941,40 @@ get_max_loop_iterations_int (struct loop *loop)
   return hwi_nit < 0 ? -1 : hwi_nit;
 }
 
+/* Sets NIT to an upper bound for the maximum number of executions of the
+   latch of the LOOP.  If we have no reliable estimate, the function returns
+   false, otherwise returns true.  */
+
+bool
+get_likely_max_loop_iterations (struct loop *loop, widest_int *nit)
+{
+  if (!loop->any_likely_upper_bound)
+    return false;
+
+  *nit = loop->nb_iterations_likely_upper_bound;
+  return true;
+}
+
+/* Similar to get_max_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
+get_likely_max_loop_iterations_int (struct loop *loop)
+{
+  widest_int nit;
+  HOST_WIDE_INT hwi_nit;
+
+  if (!get_likely_max_loop_iterations (loop, &nit))
+    return -1;
+
+  if (!wi::fits_shwi_p (nit))
+    return -1;
+  hwi_nit = nit.to_shwi ();
+
+  return hwi_nit < 0 ? -1 : hwi_nit;
+}
+
 /* Returns the loop depth of the loop BB belongs to.  */
 
 int
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index 173fda8..aba2988 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -160,6 +160,8 @@ struct GTY ((chain_next ("%h.next"))) loop {
      valid if any_upper_bound is true.  */
   widest_int nb_iterations_upper_bound;
 
+  widest_int nb_iterations_likely_upper_bound;
+
   /* An integer giving an estimate on nb_iterations.  Unlike
      nb_iterations_upper_bound, there is no guarantee that it is at least
      nb_iterations.  */
@@ -167,6 +169,7 @@ struct GTY ((chain_next ("%h.next"))) loop {
 
   bool any_upper_bound;
   bool any_estimate;
+  bool any_likely_upper_bound;
 
   /* True if the loop can be parallel.  */
   bool can_be_parallel;
@@ -776,8 +779,10 @@ loop_outermost (struct loop *loop)
 extern void record_niter_bound (struct loop *, const widest_int &, bool, bool);
 extern HOST_WIDE_INT get_estimated_loop_iterations_int (struct loop *);
 extern HOST_WIDE_INT get_max_loop_iterations_int (struct loop *);
+extern HOST_WIDE_INT get_likely_max_loop_iterations_int (struct loop *);
 extern bool get_estimated_loop_iterations (struct loop *loop, widest_int *nit);
 extern bool get_max_loop_iterations (struct loop *loop, widest_int *nit);
+extern bool get_likely_max_loop_iterations (struct loop *loop, widest_int *nit);
 extern int bb_loop_depth (const_basic_block);
 
 /* Converts VAL to widest_int.  */
diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c
index 2bffb80..707a130 100644
--- a/gcc/cfgloopmanip.c
+++ b/gcc/cfgloopmanip.c
@@ -1016,6 +1016,9 @@ copy_loop_info (struct loop *loop, struct loop *target)
   gcc_checking_assert (!target->any_upper_bound && !target->any_estimate);
   target->any_upper_bound = loop->any_upper_bound;
   target->nb_iterations_upper_bound = loop->nb_iterations_upper_bound;
+  target->any_likely_upper_bound = loop->any_likely_upper_bound;
+  target->nb_iterations_likely_upper_bound
+    = loop->nb_iterations_likely_upper_bound;
   target->any_estimate = loop->any_estimate;
   target->nb_iterations_estimate = loop->nb_iterations_estimate;
   target->estimate_state = loop->estimate_state;
diff --git a/gcc/loop-unroll.c b/gcc/loop-unroll.c
index 4d26e2f..97735a8 100644
--- a/gcc/loop-unroll.c
+++ b/gcc/loop-unroll.c
@@ -523,6 +523,11 @@ unroll_loop_constant_iterations (struct loop *loop)
 	    loop->nb_iterations_estimate -= exit_mod;
 	  else
 	    loop->any_estimate = false;
+	  if (loop->any_likely_upper_bound
+	      && wi::leu_p (exit_mod, loop->nb_iterations_likely_upper_bound))
+	    loop->nb_iterations_likely_upper_bound -= exit_mod;
+	  else
+	    loop->any_likely_upper_bound = false;
 	}
 
       bitmap_set_bit (wont_exit, 1);
@@ -566,6 +571,11 @@ unroll_loop_constant_iterations (struct loop *loop)
 	    loop->nb_iterations_estimate -= exit_mod + 1;
 	  else
 	    loop->any_estimate = false;
+	  if (loop->any_likely_upper_bound
+	      && wi::leu_p (exit_mod + 1, loop->nb_iterations_likely_upper_bound))
+	    loop->nb_iterations_likely_upper_bound -= exit_mod + 1;
+	  else
+	    loop->any_likely_upper_bound = false;
 	  desc->noloop_assumptions = NULL_RTX;
 
 	  bitmap_set_bit (wont_exit, 0);
@@ -619,6 +629,9 @@ unroll_loop_constant_iterations (struct loop *loop)
   if (loop->any_estimate)
     loop->nb_iterations_estimate
       = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
+  if (loop->any_likely_upper_bound)
+    loop->nb_iterations_likely_upper_bound
+      = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll + 1);
   desc->niter_expr = GEN_INT (desc->niter);
 
   /* Remove the edges.  */
@@ -1059,6 +1072,9 @@ unroll_loop_runtime_iterations (struct loop *loop)
   if (loop->any_estimate)
     loop->nb_iterations_estimate
       = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
+  if (loop->any_likely_upper_bound)
+    loop->nb_iterations_likely_upper_bound
+      = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll + 1);
   if (exit_at_end)
     {
       desc->niter_expr =
@@ -1070,6 +1086,11 @@ unroll_loop_runtime_iterations (struct loop *loop)
 	--loop->nb_iterations_estimate;
       else
 	loop->any_estimate = false;
+      if (loop->any_likely_upper_bound
+	  && loop->nb_iterations_likely_upper_bound != 0)
+	--loop->nb_iterations_likely_upper_bound;
+      else
+	loop->any_likely_upper_bound = false;
     }
 
   if (dump_file)
diff --git a/gcc/lto-streamer-in.c b/gcc/lto-streamer-in.c
index 3a353cd..00db94e 100644
--- a/gcc/lto-streamer-in.c
+++ b/gcc/lto-streamer-in.c
@@ -835,6 +835,9 @@ input_cfg (struct lto_input_block *ib, struct data_in *data_in,
       loop->any_upper_bound = streamer_read_hwi (ib);
       if (loop->any_upper_bound)
 	loop->nb_iterations_upper_bound = streamer_read_wi (ib);
+      loop->any_likely_upper_bound = streamer_read_hwi (ib);
+      if (loop->any_likely_upper_bound)
+	loop->nb_iterations_likely_upper_bound = streamer_read_wi (ib);
       loop->any_estimate = streamer_read_hwi (ib);
       if (loop->any_estimate)
 	loop->nb_iterations_estimate = streamer_read_wi (ib);
diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c
index 35e58fd..ed6f748 100644
--- a/gcc/lto-streamer-out.c
+++ b/gcc/lto-streamer-out.c
@@ -1925,6 +1925,9 @@ output_cfg (struct output_block *ob, struct function *fn)
       streamer_write_hwi (ob, loop->any_upper_bound);
       if (loop->any_upper_bound)
 	streamer_write_wi (ob, loop->nb_iterations_upper_bound);
+      streamer_write_hwi (ob, loop->any_likely_upper_bound);
+      if (loop->any_likely_upper_bound)
+	streamer_write_wi (ob, loop->nb_iterations_likely_upper_bound);
       streamer_write_hwi (ob, loop->any_estimate);
       if (loop->any_estimate)
 	streamer_write_wi (ob, loop->nb_iterations_estimate);
diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
index e8f6795..de447f4 100644
--- a/gcc/tree-ssa-loop-ivcanon.c
+++ b/gcc/tree-ssa-loop-ivcanon.c
@@ -1036,6 +1036,8 @@ try_peel_loop (struct loop *loop,
     }
   if (loop->any_upper_bound)
     loop->nb_iterations_upper_bound -= npeel;
+  if (loop->any_likely_upper_bound)
+    loop->nb_iterations_likely_upper_bound -= npeel;
   loop->nb_iterations_estimate = 0;
   /* Make sure to mark loop cold so we do not try to peel it more.  */
   scale_loop_profile (loop, 1, 0);
@@ -1107,6 +1109,12 @@ canonicalize_loop_induction_variables (struct loop *loop,
       fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
 	       (int)maxiter);
     }
+  if (dump_file && (dump_flags & TDF_DETAILS)
+      && likely_max_loop_iterations_int (loop) >= 0)
+    {
+      fprintf (dump_file, "Loop likely %d iterates at most %i times.\n", loop->num,
+	       (int)likely_max_loop_iterations_int (loop));
+    }
 
   /* Remove exits that are known to be never taken based on loop bound.
      Needs to be called after compilation of max_loop_iterations_int that
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 5afc9b3..e38d246 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -2289,7 +2289,11 @@ number_of_iterations_exit (struct loop *loop, edge exit,
 
   /* If NITER has simplified into a constant, update MAX.  */
   if (TREE_CODE (niter->niter) == INTEGER_CST)
-    niter->max = wi::to_widest (niter->niter);
+    {
+      niter->max = wi::to_widest (niter->niter);
+      record_niter_bound (loop, niter->max, loop_only_exit_p (loop, exit),
+			  true);
+    }
 
   if (integer_onep (niter->assumptions))
     return true;
@@ -2954,8 +2958,6 @@ record_estimate (struct loop *loop, tree bound, const widest_int &i_bound,
     realistic = false;
   else
     gcc_checking_assert (i_bound == wi::to_widest (bound));
-  if (!upper && !realistic)
-    return;
 
   /* If we have a guaranteed upper bound, record it in the appropriate
      list, unless this is an !is_exit bound (i.e. undefined behavior in
@@ -2977,7 +2979,7 @@ record_estimate (struct loop *loop, tree bound, const widest_int &i_bound,
   /* If statement is executed on every path to the loop latch, we can directly
      infer the upper bound on the # of iterations of the loop.  */
   if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
-    return;
+    upper = false;
 
   /* Update the number of iteration estimates according to the bound.
      If at_stmt is an exit then the loop latch is executed at most BOUND times,
@@ -3850,6 +3852,41 @@ max_loop_iterations_int (struct loop *loop)
   return hwi_nit < 0 ? -1 : hwi_nit;
 }
 
+/* Sets NIT to an likely upper bound for the maximum number of executions of the
+   latch of the LOOP.  If we have no reliable estimate, the function returns
+   false, otherwise returns true.  */
+
+bool
+likely_max_loop_iterations (struct loop *loop, widest_int *nit)
+{
+  /* When SCEV information is available, try to update loop iterations
+     estimate.  Otherwise just return whatever we recorded earlier.  */
+  if (scev_initialized_p ())
+    estimate_numbers_of_iterations_loop (loop);
+
+  return get_likely_max_loop_iterations (loop, nit);
+}
+
+/* Similar to max_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
+likely_max_loop_iterations_int (struct loop *loop)
+{
+  widest_int nit;
+  HOST_WIDE_INT hwi_nit;
+
+  if (!likely_max_loop_iterations (loop, &nit))
+    return -1;
+
+  if (!wi::fits_shwi_p (nit))
+    return -1;
+  hwi_nit = nit.to_shwi ();
+
+  return hwi_nit < 0 ? -1 : hwi_nit;
+}
+
 /* Returns an estimate for 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.  */
@@ -3869,7 +3906,7 @@ estimated_stmt_executions_int (struct loop *loop)
   return snit < 0 ? -1 : snit;
 }
 
-/* Sets NIT to the estimated maximum number of executions of the latch of the
+/* Sets NIT to the maximum number of executions of the latch of the
    LOOP, plus one.  If we have no reliable estimate, the function returns
    false, otherwise returns true.  */
 
@@ -3888,6 +3925,25 @@ max_stmt_executions (struct loop *loop, widest_int *nit)
   return wi::gtu_p (*nit, nit_minus_one);
 }
 
+/* Sets NIT to the estimated maximum number of executions of the latch of the
+   LOOP, plus one.  If we have no likely estimate, the function returns
+   false, otherwise returns true.  */
+
+bool
+likely_max_stmt_executions (struct loop *loop, widest_int *nit)
+{
+  widest_int nit_minus_one;
+
+  if (!likely_max_loop_iterations (loop, nit))
+    return false;
+
+  nit_minus_one = *nit;
+
+  *nit += 1;
+
+  return wi::gtu_p (*nit, nit_minus_one);
+}
+
 /* Sets NIT to the estimated number of executions of the latch of the
    LOOP, plus one.  If we have no reliable estimate, the function returns
    false, otherwise returns true.  */
diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h
index 84ff0ae..1b5d111 100644
--- a/gcc/tree-ssa-loop-niter.h
+++ b/gcc/tree-ssa-loop-niter.h
@@ -35,9 +35,13 @@ extern bool estimated_loop_iterations (struct loop *, widest_int *);
 extern HOST_WIDE_INT estimated_loop_iterations_int (struct loop *);
 extern bool max_loop_iterations (struct loop *, widest_int *);
 extern HOST_WIDE_INT max_loop_iterations_int (struct loop *);
+extern bool likely_max_loop_iterations (struct loop *, widest_int *);
+extern HOST_WIDE_INT likely_max_loop_iterations_int (struct loop *);
 extern HOST_WIDE_INT max_stmt_executions_int (struct loop *);
+extern HOST_WIDE_INT likely_max_stmt_executions_int (struct loop *);
 extern HOST_WIDE_INT estimated_stmt_executions_int (struct loop *);
 extern bool max_stmt_executions (struct loop *, widest_int *);
+extern bool likely_max_stmt_executions (struct loop *, widest_int *);
 extern bool estimated_stmt_executions (struct loop *, widest_int *);
 extern void estimate_numbers_of_iterations (void);
 extern bool stmt_dominates_stmt_p (gimple *, gimple *);