Re: [PATCH GCC]Improve bound information in loop niter analysis

["Bin.Cheng" <amker dot cheng at gmail dot com>]

On Fri, Aug 14, 2015 at 6:08 AM, Jeff Law <law@redhat.com> wrote:
> On 07/28/2015 03:36 AM, Bin Cheng wrote:
>>
>> Hi,
>> Loop niter computes inaccurate bound information for different loops.
>> This
>> patch is to improve it by using loop initial condition in
>> determine_value_range.  Generally, loop niter is computed by subtracting
>> start var from end var in loop exit condition.  Moreover, loop bound is
>> computed using value range information of both start and end variables.
>> Basic idea of this patch is to check if loop initial condition implies
>> more
>> range information for both start/end variables.  If yes, we refine range
>> information and use that to compute loop bound.
>> With this improvement, more accurate loop bound information is computed
>> for
>> test cases added by this patch.
>>
>> Is it OK?
>>
>> Thanks,
>> bin
>>
>> 2015-07-28  Bin Cheng<bin.cheng@arm.com>
>>
>>         * tree-ssa-loop-niter.c (refine_value_range_using_guard): New.
>>         (determine_value_range): Call refine_value_range_using_guard for
>>         each loop initial condition to improve value range.
>>
>> gcc/testsuite/ChangeLog
>> 2015-07-28  Bin Cheng<bin.cheng@arm.com>
>>
>>         * gcc.dg/tree-ssa/loop-bound-1.c: New test.
>>         * gcc.dg/tree-ssa/loop-bound-3.c: New test.
>>         * gcc.dg/tree-ssa/loop-bound-5.c: New test.
>>
>>
>> improve-loop-bound-analysis-20150728.txt
>>
>>
>> Index: gcc/testsuite/gcc.dg/tree-ssa/loop-bound-3.c
>> ===================================================================
>> --- gcc/testsuite/gcc.dg/tree-ssa/loop-bound-3.c        (revision 0)
>> +++ gcc/testsuite/gcc.dg/tree-ssa/loop-bound-3.c        (revision 0)
>> @@ -0,0 +1,22 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fdump-tree-ivopts-details" } */
>> +
>> +int *a;
>> +
>> +int
>> +foo (unsigned char s, unsigned char l)
>> +{
>> +  unsigned char i;
>> +  int sum = 0;
>> +
>> +  for (i = s; i > l; i -= 1)
>
> So is this really bounded by 254 iterations?  ISTM it's bounded by 255
> iterations when called with s = 255, l = 0.   What am I missing here? Am I
> mis-interpreting the dump output in some way?

Thanks for the comment.
IIUC, the niter information in struct tree_niter_desc means the number
of executions of the latch of the loop, so it's 254, rather than 255.
And same the bound information.  Of course, statements in the loop
body could execute bound+1 times depending on its position in loop.
For example, struct nb_iter_bound is to describe number of iterations
of statements(exit conditions).
Moreover, if we modify the test as in below:

>> +int *a;
>> +
>> +int
>> +foo (void)
>> +{
>> +  unsigned char i;
>> +  int sum = 0;
>> +
>> +  for (i = 255; i > 0; i -= 1)

GCC now successfully analyzes the loop's bound as 254.

I might be wrong about the code, so please correct me.

Thanks,
bin
>
> Similarly for the other tests.
>
> Jeff
>