Re: [PATCH PR45098, 7/10] Nowrap limits iterations

[Tom de Vries <vries@codesourcery.com>]

On 05/30/2011 02:38 PM, Zdenek Dvorak wrote:
> Hi,
> 
>>> The header block of the loop is bb 4, the latch block is bb 3:
>>> ...
>>> (gdb) p loop.header.index
>>> $4 = 4
>>> (gdb) p loop.latch.index
>>> $5 = 3
>>> ...
>>>
>>> The number of times the latch edge is executed, is 10.
>>>
>>> But loop->nb_iterations_upper_bound, or max_niter is 11:
> 
> this is a bit strange, it looks like the # of iterations estimation is setting
> nb_iterations_upper_bound too conservatively (or I gave nb_iterations_upper_bound
> a different semantics than I remember -- but both my memory and the comment in cfgloop.h
> suggest that nb_iterations_upper_bound >= nb_iterations, i.e., that it should be 10 in your
> example),
> 

The actual values of nb_iterations_upper_bound are determined by this code
fragment in record_estimate.

/* 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 BOUND is expected to be close to 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,
		 gimple at_stmt, bool is_exit, bool realistic, bool upper)
{
  ...

  /* 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, gimple_bb (at_stmt))))
    delta = double_int_one;
  else
    delta = double_int_two;
  i_bound = double_int_add (i_bound, delta);


As far as I can tell, what is current calculated in i_bound (and assigned to
nb_iterations_upper_bound), is the maximum amount of times any statement in the
loop is executed, where any includes exit tests. Differently put, the maximum
amount of times the loop header is executed.

This is confirmed by this comment in tree-vrp.c:

  /* Try to use estimated number of iterations for the loop to constrain the
     final value in the evolution.
     We are interested in the number of executions of the latch, while
     nb_iterations_upper_bound includes the last execution of the exit test.  */

I modified the patch to improved the comment.

Ok for trunk?

Thanks,
- Tom

Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 173734)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -4391,8 +4391,14 @@ may_eliminate_iv (struct ivopts_data *da
             {
               if (!estimated_loop_iterations (loop, true, &max_niter))
                 return false;
-              /* The loop bound is already adjusted by adding 1.  */
-              if (double_int_ucmp (max_niter, period_value) > 0)
+              /* (a) loop->nb_iterations_upper_bound (assigned to max_niter)
+                     includes the last execution of the exit test.
+                 (b) The number of distinct values of the cand is
+                     period_value + 1.
+                 So, the transformation is allowed if
+                 max_niter <= period_value + 1.  */
+              period_value = double_int_add (period_value, double_int_one);
+              if (double_int_ucmp (max_niter, period_value) > 0)
                 return false;
             }
           else