[PATCH PR68911]Check overflow when computing range information from loop niter bound

[PATCH PR68911]Check overflow when computing range information from loop niter bound

[Bin Cheng]

[-- Attachment #1: Type: text/plain, Size: 2250 bytes --]

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.



[-- Attachment #2: pr68911-20160107.txt --]
[-- Type: text/plain, Size: 1712 bytes --]

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

Re: [PATCH PR68911]Check overflow when computing range information from loop niter bound

[Richard Biener]

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.
>
>