Re: [VRP][PATCH] Improve value range for loop index

[Richard Biener <richard dot guenther at gmail dot com>]

On Fri, Apr 25, 2014 at 9:13 AM, Kugan
<kugan.vivekanandarajah@linaro.org> wrote:
>
>
> On 24/04/14 23:05, Richard Biener wrote:
>> On Wed, Apr 9, 2014 at 10:07 PM, Kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> Value range propagation simplifies convergence in vrp_visit_phi_node by
>>> setting minimum to TYPE_MIN when the computed minimum is smaller than
>>> the previous minimum. This can however result in pessimistic value
>>> ranges in some cases.
>>>
>>> for example,
>>>
>>>         unsigned int i;
>>>         for (i = 0; i < 8; i++)
>>>         {
>>>           ....
>>>         }
>>>
>>>         # ivtmp_19 = PHI <ivtmp_17(5), 8(2)>
>>>         ...
>>>         <bb 5>:
>>>         ivtmp_17 = ivtmp_19 - 1;
>>>         if (ivtmp_17 != 0)
>>>         ....
>>>         goto <bb 5>;
>>>
>>> min value of ivtmp_19  is simplified to 0 (in tree-vrp.c:8465) where as
>>> it should have been 1. This prevents correct value ranges being
>>> calculated for ivtmp_17 in the example.
>>>
>>> We should be able to see the step (the difference from previous minimum
>>> to computed minimum) and if there is scope for more iterations (computed
>>> minimum is greater than step), and then we should be able set minimum to
>>> do one more iteration and converge to the right minimum value.
>>>
>>> Attached patch fixes this. Is this OK for stage-1?
>>
>> In principle the code in adjust_range_with_scev is supposed to
>> fix this up by using number-of-iteration analysis.  I can see this is not
>> working for the testcase but I'm curious exactly why.
>
> Thanks for pointing me to adjust_range_with_scev.  I will look into it.
>
>
>> Your patch basically makes us converge to the correct value by
>> iterating (but faster than by just iterating).  That's an interesting
>> idea but the way you do it looks very special.  If we really want to
>> go down this route (instead of fixing up adjust_range_with_scev for IVs)
>> then I'd like to see a more general solution - like by making the code
>> skip to TYPE_MIN/MAX_VALUE +-1.  I'm also not sure the case
>> handling the supposed bouncing needs to bump to MIN/MAX at all,
>> it could simply retain the old values.
>
> TYPE_MIN/MAX_VALUE +-1 might not always work as there might be some
> cases where the stride (or the steps in convergence) is not 1 but more
> than 1 (?). In those cases, if we set it to TYPE_MIN/MAX_VALUE +-1, they
> will not converge from there. therefore should that be,
> TYPE_MIN/MAX_VALUE +- stride?

I don't see how stride matters here.  Surely with any value you choose you
will never converge to the exact optimal minimum/maximum value.  But
a more conservative range is always also a convergence point (otherwise
VRPs correctness would fall apart).

Richard.

>
> Thanks,
> Kugan