[VRP] Improve value range for loop index

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?

Bootstrapped and regression tested on X86_64-unknown-linux-gnu with no
new regressions.

Thanks,
Kugan

gcc/

+2014-04-09  Kugan Vivekanandarajah  <kuganv@linaro.org>
+
+	* tree-vrp.c (vrp_visit_phi_node) : Improve value ranges of loop
+	index when simplifying convergence towards minimum.
+

gcc/testsuite

+2014-04-09  Kugan Vivekanandarajah  <kuganv@linaro.org>
+
+	* gcc.dg/tree-ssa/vrp91.c: New test
+

Ping?

On 10/04/14 06:07, Kugan 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?
> 
> Bootstrapped and regression tested on X86_64-unknown-linux-gnu with no
> new regressions.
> 
> Thanks,
> Kugan
> 
> gcc/
> 
> +2014-04-09  Kugan Vivekanandarajah  <kuganv@linaro.org>
> +
> +	* tree-vrp.c (vrp_visit_phi_node) : Improve value ranges of loop
> +	index when simplifying convergence towards minimum.
> +
> 
> gcc/testsuite
> 
> +2014-04-09  Kugan Vivekanandarajah  <kuganv@linaro.org>
> +
> +	* gcc.dg/tree-ssa/vrp91.c: New test
> +
>

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.

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.

For example with the following which also lets the next iteration choose
whether there was overflow or not.  That would be the main motivation
here - that we now handle a lower bound of -INF + 1 correctly is a
nice side-effect (but as we don't handle -INF + 2 the same it's only
a side-effect).

Like with the following.

@@ -8452,32 +8453,30 @@ vrp_visit_phi_node (gimple phi)
          && (cmp_min != 0 || cmp_max != 0))
        goto varying;

-      /* If the new minimum is smaller or larger than the previous
-        one, go all the way to -INF.  In the first case, to avoid
-        iterating millions of times to reach -INF, and in the
-        other case to avoid infinite bouncing between different
-        minimums.  */
-      if (cmp_min > 0 || cmp_min < 0)
-       {
-         if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
-             || !vrp_var_may_overflow (lhs, phi))
-           vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
-         else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
-           vr_result.min =
-               negative_overflow_infinity (TREE_TYPE (vr_result.min));
-       }
-
-      /* Similarly, if the new maximum is smaller or larger than
-        the previous one, go all the way to +INF.  */
-      if (cmp_max < 0 || cmp_max > 0)
-       {
-         if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
-             || !vrp_var_may_overflow (lhs, phi))
-           vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
-         else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
-           vr_result.max =
-               positive_overflow_infinity (TREE_TYPE (vr_result.max));
-       }
+      /* If the new minimum is larger than than the previous one
+        retain the old value.  If the new minimum value is smaller
+        than the previous one and not -INF go all the way to -INF + 1.
+        In the first case, to avoid infinite bouncing between different
+        minimums, and in the other case to avoid iterating millions of
+        times to reach -INF.  */
+      if (cmp_min < 0)
+       vr_result.min = lhs_vr->min;
+      else if (cmp_min > 0
+              && !vrp_val_is_min (vr_result.min))
+       vr_result.min
+         = int_const_binop (PLUS_EXPR,
+                            vrp_val_min (TREE_TYPE (vr_result.min)),
+                            build_int_cst (TREE_TYPE (vr_result.min), 1));
+
+      /* Similarly for the maximum value.  */
+      if (cmp_max > 0)
+       vr_result.max = lhs_vr->max;
+      else if (cmp_max < 0
+              && !vrp_val_is_max (vr_result.max))
+       vr_result.max
+         = int_const_binop (MINUS_EXPR,
+                            vrp_val_max (TREE_TYPE (vr_result.min)),
+                            build_int_cst (TREE_TYPE (vr_result.min), 1));

       /* If we dropped either bound to +-INF then if this is a loop
         PHI node SCEV may known more about its value-range.  */

I'm going to give this bootstrap and testing.

Richard.


> Bootstrapped and regression tested on X86_64-unknown-linux-gnu with no
> new regressions.
>
> Thanks,
> Kugan
>
> gcc/
>
> +2014-04-09  Kugan Vivekanandarajah  <kuganv@linaro.org>
> +
> +       * tree-vrp.c (vrp_visit_phi_node) : Improve value ranges of loop
> +       index when simplifying convergence towards minimum.
> +
>
> gcc/testsuite
>
> +2014-04-09  Kugan Vivekanandarajah  <kuganv@linaro.org>
> +
> +       * gcc.dg/tree-ssa/vrp91.c: New test
> +

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?


Thanks,
Kugan

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