On 05/18/2011 11:11 PM, Zdenek Dvorak wrote:
> Hi,
> 
>> This patch attemps to estimate the number of iterations of the loop based on
>> nonwrapping arithmetic in the loop body.
>>
>> 2011-05-05  Tom de Vries  <tom@codesourcery.com>
>>
>> 	PR target/45098
>> 	* tree-ssa-loop-ivopts.c (struct ivopts_data): Add fields
>> 	max_iterations_p and max_iterations.
>> 	(is_nonwrap_use, max_loop_iterations, set_max_iterations): New function.
>> 	(may_eliminate_iv): Use max_iterations_p and max_iterations.
>> 	(tree_ssa_iv_optimize_loop): Use set_max_iterations.
> 
> what are the cases this handles better than the existing analysis of maximum numbers of iterations
> (estimate_numbers_of_iterations)?

Consider tr1:

extern int pfoo (int*)  __attribute__((pure));

int tr1 (int array[], unsigned int n)
{
  int sum = 0;
  unsigned int i;
  i = 0;
  while (1)
    {
      sum += pfoo (&array[i]);
      if (!(i < n))
        break;
      i++;
    }
  return sum;
}

The number of iterations is limited by &array[i]. &array[0x3fffffff] is still
ok, but &array[0x40000000] wraps. So i runs maximally from 0 to 0x3fffffff,
which is 0x40000000 loop iterations. Since &array[i] dominates the single
loop exit, any statement in the loop is executed at most 0x40000000 times.
That's also the amount registered in nb_iterations_upper_bound.
Since int *p has 0x40000000 distinct values, it's ok to replace the
exit test !(i < n) with p == &array[n].


On the other hand, consider tr6:

int tr6 (int array[], unsigned int n)
{
  int sum = 0;
  unsigned int i;
  for (i = 0; i < n; ++i)
      sum += pfoo (&array[i]);
  return sum;
}

The same holds as before, but &array[i] does not dominate the single
loop exit, so any statement in the loop is executed at most 0x40000001 times.
Note that the loop body is executed at most 0x40000000 times, and that only
the exit test is executed at most 0x40000001 times.
That's also the amount registered in nb_iterations_upper_bound.
Since int *p has only 0x40000000 distinct values, it's not ok to replace
the exit test in terms of p.


> Would it be possible to add the handling of these cases
> to estimate_numbers_of_iterations, rather than doing it just for ivopts?

Yes, I did that now.

Thanks,
- Tom

2011-05-05  Tom de Vries  <tom@codesourcery.com>

	PR target/45098
	* tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): New
	function.
	(infer_loop_bounds_from_undefined): Use new function.
	* tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix
	estimated_loop_iterations comparison.