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.ch...@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.ch...@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 ();
+}
