[SCEV] Clarify requirements for zero-stride to be UB

[reames]

Summary

There's a silent bug in our reasoning about zero strides. We assume that having a single static exit implies that if that exit is not taken, then the loop must be infinite. This ignores the potential for abnormal exits via exceptions. Consider the following example:
for (uint_8 i = 0; i < 1; i += 0) {

throw_on_thousandth_call();

}

Our reasoning is such that we'd conclude this loop can't take the backedge as that would lead to a (presumed) infinite loop.

In practice, this is a silent bug because the loopIsFiniteByAssumption returns false strictly more often than the loopHaNoAbnormalExits property. We could reasonable want to change that in the future, so fixing the codeflow now is worthwhile.

[efriedma]

LGTM.

If a loop is finite by assumption, it doesn't have external side-effects. But then, how do we exit the loop? I guess throwing an exception doesn't involve an external side-effect. But we don't really have any incentive to try to model that, given that every place we call loopIsFiniteByAssumption() also calls loopHasNoAbnormalExits(), so this seems like it will stay a theoretical problem. I guess it serves as documentation, though.

llvm/lib/Analysis/ScalarEvolution.cpp

if (!PositiveStride) {
     // (max(end, start + stride) - start - 1) /u stride
     //
     // The additional preconditions that we need to check to prove correctness
     // of the above formula is as follows -
     //
     // a) IV is either nuw or nsw depending upon signedness (indicated by the
     //    NoWrap flag).
     // b) loop is single exit with no side effects.
+    // c) loop has no abnormal exits
     //
     //
     // Precondition a) implies that if the stride is negative, this is a single
     // trip loop. The backedge taken count formula reduces to zero in this case.
     //
-    // Precondition b) implies that if rhs is invariant in L, then unknown
-    // stride being zero means the backedge can't be taken without UB.
+    // Precondition b) and c) combine to imply that if rhs is invariant in L,
+    // then a zero stride means the backedge can't be taken without executing
+    // undefined behavior.
     //
     // The positive stride case is the same as isKnownPositive(Stride) returning
     // true (original behavior of the function).
     //
     // We want to make sure that the stride is truly unknown as there are edge
     // cases where ScalarEvolution propagates no wrap flags to the
     // post-increment/decrement IV even though the increment/decrement operation
     // itself is wrapping. The computed backedge taken count may be wrong in
     // such cases. This is prevented by checking that the stride is not known to
     // be either positive or non-positive. For example, no wrap flags are
     // propagated to the post-increment IV of this loop with a trip count of 2 -
     //
     // unsigned char i;
     // for(i=127; i<128; i+=129)
     //   A[i] = i;
     //
     if (PredicatedIV || !NoWrap || isKnownNonPositive(Stride) ||
-        !loopIsFiniteByAssumption(L))
+        !loopIsFiniteByAssumption(L) || !loopHasNoAbnormalExits(L))
       return getCouldNotCompute();
 
     if (!isKnownNonZero(Stride)) {
       // If we have a step of zero, and RHS isn't invariant in L, we don't know
       // if it might eventually be greater than start and if so, on which
       // iteration.  We can't even produce a useful upper bound.
       if (!isLoopInvariant(RHS, L))
         return getCouldNotCompute();