[SCEV] Fix bug involving zero step and non-invariant RHS in trip count logic

[reames]

Summary

Eli pointed out the issue when reviewing D104140. The max trip count logic makes an assumption that the value of IV changes. When the step is zero, the nowrap fact becomes trivial, and thus there's nothing preventing the loop from being nearly infinite. (The "nearly" part is because mustprogress may disallow an infinite loop while still allowing 999999999 iterations before RHS happens to allow an exit.)

This is very difficult to see in practice. You need a means to produce a loop varying RHS in a mustprogress loop which doesn't allow the loop to be infinite. In most cases, LICM or SCEV are smart enough to remove the loop varying expressions.

[reames]

Er, ignore this for the moment. I appear to have screwed something up in extracting and testing this - it doesn't pass make check for me now. Time to return to this with fresh eyes tomorrow.

[reames]

Local test failure was a stray change which had snuck in, not this patch. But still, probably time to return to the project tomorrow.

[efriedma]

Like I noted on the other review, I think you also need the isLoopInvariant(RHS, L) check if the stride is negative.

[reames]

In D106327#2889082, @efriedma wrote:

Like I noted on the other review, I think you also need the isLoopInvariant(RHS, L) check if the stride is negative.

Can we fix one bug at a time though? I'm happy to explore that one, but I'd prefer to do it on it's own with it's own discussion and tests.

[efriedma]

LGTM

I guess we can deal with the negative case separately, sure.

[reames]

Eli, just FYI, I'm going to be away from build env for most of the next couple days. I might get this in tonight, but if not, it'll likely wait until the weekend. Feel free to commit on my behalf if doing so would help you make progress.

llvm/lib/Analysis/ScalarEvolution.cpp

if (!PositiveStride) {
     // a) IV is either nuw or nsw depending upon signedness (indicated by the
     //    NoWrap flag).
     // b) loop is single exit with no side effects.
     //
     //
     // 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 the unknown stride cannot be zero otherwise
-    // we have UB.
+    // Precondition b) implies that if rhs is invariant in L, then unknown
+    // stride being zero means the backedge can't be taken without UB.
     //
     // 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))
       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();
+
       // We allow a potentially zero stride, but we need to divide by stride
       // below.  Since the loop can't be infinite and this check must control
       // the sole exit, we can infer the exit must be taken on the first
       // iteration (e.g. backedge count = 0) if the stride is zero.  Given that,
       // we know the numerator in the divides below must be zero, so we can
       // pick an arbitrary non-zero value for the denominator (e.g. stride)
       // and produce the right result.
       // FIXME: Handle the case where Stride is poison?
       auto wouldZeroStrideBeUB = [&]() {
-      // If RHS isn't loop invariant, bail out for now. This isn't necessary
-      // for the proof, but isLoopEntryGuardedByCond only works on
-      // loop-invariant values.
-      if (!isLoopInvariant(RHS, L))
-        return false;
-
         // Proof by contradiction.  Suppose the stride were zero.  If we can
         // prove that the backedge *is* taken on the first iteration, then since
         // we know this condition controls the sole exit, we must have an
         // infinite loop.  We can't have a (well defined) infinite loop per
         // check just above.
         // Note: The (Start - Stride) term is used to get the start' term from
         // (start' + stride,+,stride). Remember that we only care about the
         // result of this expression when stride == 0 at runtime.
         auto *StartIfZero = getMinusSCEV(IV->getStart(), Stride);
         return isLoopEntryGuardedByCond(L, Cond, StartIfZero, RHS);
       };
-    if (!isKnownNonZero(Stride) && !wouldZeroStrideBeUB()) {
+      if (!wouldZeroStrideBeUB()) {
         Stride = getUMaxExpr(Stride, getOne(Stride->getType()));
       }
+    }
   } else if (!Stride->isOne() && !NoWrap) {
     auto isUBOnWrap = [&]() {
       // Can we prove this loop *must* be UB if overflow of IV occurs?
       // Reasoning goes as follows:
       // * Suppose the IV did self wrap.
       // * If Stride evenly divides the iteration space, then once wrap
       //   occurs, the loop must revisit the same values.
       // * We know that RHS is invariant, and that none of those values

llvm/test/Analysis/ScalarEvolution/trip-count-unknown-stride.ll

 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 
 ; CHECK-LABEL: Determining loop execution counts for: @zero_stride_varying_rhs
 ; CHECK: Loop %for.body: Unpredictable backedge-taken count.
-; CHECK: Loop %for.body: max backedge-taken count is -1
+; CHECK: Loop %for.body: Unpredictable max backedge-taken count
 
 define void @zero_stride_varying_rhs(i32* nocapture %A, i32* %n_p, i32 %zero) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.body
   %i.05 = phi i32 [ %add, %for.body ], [ 0, %entry ]
   %arrayidx = getelementptr inbounds i32, i32* %A, i32 %i.05