| Message ID | 5345A879.5070406@linaro.org |
|---|---|
| State | New |
| Headers | show |
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
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c index e69de29..26e857c 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp91.c @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-S -O2 -fdump-tree-vrp2" } */ + +unsigned short data; +void foo () +{ + unsigned char x16; + unsigned int i; + for (i = 0; i < 8; i++) + { + x16 = data & 1; + data >>= 1; + if (x16 == 1) + { + data ^= 0x4; + } + data >>= 1; + } +} + +/* { dg-final { scan-tree-dump "\\\[0, 7\\\]" "vrp2" } } */ +/* { dg-final { cleanup-tree-dump "vrp2" } } */ + diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 14f1526..c63f794 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -8461,7 +8461,30 @@ vrp_visit_phi_node (gimple phi) { 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)); + { + tree step = ((cmp_min > 0) && TYPE_UNSIGNED (TREE_TYPE (lhs))) ? + int_const_binop (MINUS_EXPR, lhs_vr->min, vr_result.min) : NULL_TREE; + + /* If the type minimum is zero, while avoiding repeated + iterations, let us stop at step and let the iterations take + it to zero (if necessary) from there. This will improve + value ranges for cases like below, when the value range + for ivtemp_17 is [0, 7] and range for ivtmp_19 is [1, 8]. + + # ivtmp_19 = PHI <ivtmp_17(5), 8(2)> + ... + <bb 5>: + ivtmp_17 = ivtmp_19 - 1; + if (ivtmp_17 != 0) + .... + goto <bb 5>; + */ + if ((cmp_min > 0) && (TYPE_UNSIGNED (TREE_TYPE (lhs))) + && (tree_int_cst_compare (vr_result.min, step) != -1)) + vr_result.min = step; + else + 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));
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 +