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

[Bin Cheng <Bin dot Cheng at arm dot com>]

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: pr68911-20160107.txt
Description: pr68911-20160107.txt