| Message ID | HE1PR08MB0507A5BC86DA1C7F0C761A6EE7C90@HE1PR08MB0507.eurprd08.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
On Mon, Jan 11, 2016 at 5:11 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > Hi, > A wrong code bug is reported in PR68911, which GCC generates infinite loop for below example after loop niter analysis changes. After that change, scev_probably_wraps_p identifies that e_1 in below case never overflow/wrap: > <bb 8>: > e_15 = e_1 + 1; > > <bb 13>: > # e_1 = PHI <e_2(3), e_15(8), e_12(7)> > if (e_1 <= 93) > goto <bb 8>; > else > goto <bb 10>; > > The loop niter analysis gives us: > Analyzing # of iterations of loop 2 > exit condition [e_8, + , 1] <= 93 > bounds on difference of bases: -4294967202 ... 93 > result: > zero if e_8 > 94 > # of iterations 94 - e_8, bounded by 94 > > I think the analysis is good. When scev_probably_wraps_p returns false, it may imply two possible cases. > CASE 1) If loop's latch gets executed, then we know the SCEV doesn't overflow/wrap during loop execution. > CASE 2) If loop's latch isn't executed, i.e., the loop exits immediately at its first check on exit condition. In this case the SCEV doesn't overflow/wrap because it isn't increased at all. > > The real problem I think is VRP only checks scev_probably_wraps_p then assumes SCEV won't overflow/wrap after niter.bound iterations. This is not true for CASE 2). If we have a large enough starting value for e_1, for example, 0xfffffff8 in this example, e_1 is guaranteed not overflow/wrap only because the loop exits immediately, not after niter.bound interations. Here VRP assuming "e_1 + niter.bound" doesn't overflow/wrap is wrong. > > This patch fixes the issue by adding overflow check in range information computed for "e_1 + niter.bound". It catches overflow/wrap of the expression when loop may exit immediately. > > With this change, actually I think it may be possible for us to remove the call to scev_probably_wraps_p, though I didn't do that in this patch. > > Bootstrap and test on x86_64 and AArch64. Is it OK? Ok. Thanks, Richard. > Thanks, > bin > > 2016-01-10 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/68911 > * tree-vrp.c (adjust_range_with_scev): Check overflow in range > information computed for expression "init + nit * step". > > gcc/testsuite/ChangeLog > 2016-01-10 Bin Cheng <bin.cheng@arm.com> > > PR tree-optimization/68911 > * gcc.c-torture/execute/pr68911.c: New test. > >
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index acbb70b..811a7e4 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -4259,6 +4259,27 @@ adjust_range_with_scev (value_range *vr, struct loop *loop, /* Likewise if the addition did. */ if (maxvr.type == VR_RANGE) { + value_range initvr = VR_INITIALIZER; + + if (TREE_CODE (init) == SSA_NAME) + initvr = *(get_value_range (init)); + else if (is_gimple_min_invariant (init)) + set_value_range_to_value (&initvr, init, NULL); + else + return; + + /* Check if init + nit * step overflows. Though we checked + scev {init, step}_loop doesn't wrap, it is not enough + because the loop may exit immediately. Overflow could + happen in the plus expression in this case. */ + if ((dir == EV_DIR_DECREASES + && (is_negative_overflow_infinity (maxvr.min) + || compare_values (maxvr.min, initvr.min) != -1)) + || (dir == EV_DIR_GROWS + && (is_positive_overflow_infinity (maxvr.max) + || compare_values (maxvr.max, initvr.max) != 1))) + return; + tmin = maxvr.min; tmax = maxvr.max; } diff --git a/gcc/testsuite/gcc.c-torture/execute/pr68911.c b/gcc/testsuite/gcc.c-torture/execute/pr68911.c new file mode 100644 index 0000000..f245a11 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr68911.c @@ -0,0 +1,27 @@ +extern void abort (void); + +char a; +int b, c; +short d; + +int main () +{ + unsigned e = 2; + unsigned timeout = 0; + + for (; c < 2; c++) + { + int f = ~e / 7; + if (f) + a = e = ~(b && d); + while (e < 94) + { + e++; + if (++timeout > 100) + goto die; + } + } + return 0; +die: + abort (); +}
Hi, A wrong code bug is reported in PR68911, which GCC generates infinite loop for below example after loop niter analysis changes. After that change, scev_probably_wraps_p identifies that e_1 in below case never overflow/wrap: <bb 8>: e_15 = e_1 + 1; <bb 13>: # e_1 = PHI <e_2(3), e_15(8), e_12(7)> if (e_1 <= 93) goto <bb 8>; else goto <bb 10>; The loop niter analysis gives us: Analyzing # of iterations of loop 2 exit condition [e_8, + , 1] <= 93 bounds on difference of bases: -4294967202 ... 93 result: zero if e_8 > 94 # of iterations 94 - e_8, bounded by 94 I think the analysis is good. When scev_probably_wraps_p returns false, it may imply two possible cases. CASE 1) If loop's latch gets executed, then we know the SCEV doesn't overflow/wrap during loop execution. CASE 2) If loop's latch isn't executed, i.e., the loop exits immediately at its first check on exit condition. In this case the SCEV doesn't overflow/wrap because it isn't increased at all. The real problem I think is VRP only checks scev_probably_wraps_p then assumes SCEV won't overflow/wrap after niter.bound iterations. This is not true for CASE 2). If we have a large enough starting value for e_1, for example, 0xfffffff8 in this example, e_1 is guaranteed not overflow/wrap only because the loop exits immediately, not after niter.bound interations. Here VRP assuming "e_1 + niter.bound" doesn't overflow/wrap is wrong. This patch fixes the issue by adding overflow check in range information computed for "e_1 + niter.bound". It catches overflow/wrap of the expression when loop may exit immediately. With this change, actually I think it may be possible for us to remove the call to scev_probably_wraps_p, though I didn't do that in this patch. Bootstrap and test on x86_64 and AArch64. Is it OK? Thanks, bin 2016-01-10 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/68911 * tree-vrp.c (adjust_range_with_scev): Check overflow in range information computed for expression "init + nit * step". gcc/testsuite/ChangeLog 2016-01-10 Bin Cheng <bin.cheng@arm.com> PR tree-optimization/68911 * gcc.c-torture/execute/pr68911.c: New test.