On Wed, Apr 9, 2014 at 10:07 PM, Kugan
<kugan.vivekanandara...@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 <kug...@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 <kug...@linaro.org>
> +
> + * gcc.dg/tree-ssa/vrp91.c: New test
> +
