This is the mail archive of the
mailing list for the GCC project.
Re: [VRP][PATCH] Improve value range for loop index
- From: Kugan <kugan dot vivekanandarajah at linaro dot org>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: "gcc-patches at gcc dot gnu dot org" <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 25 Apr 2014 17:13:36 +1000
- Subject: Re: [VRP][PATCH] Improve value range for loop index
- Authentication-results: sourceware.org; auth=none
- References: <5345A879 dot 5070406 at linaro dot org> <CAFiYyc0nQQJGnSvS038SfMj5sd8_PO5gLL4nHwmNzZgdW=meXw at mail dot gmail dot com>
On 24/04/14 23:05, Richard Biener wrote:
> On Wed, Apr 9, 2014 at 10:07 PM, Kugan
> <email@example.com> 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?