[SCEV] Handle zero stride correctly in howManyLessThans

[reames]

Summary

This is split from D105216, but the code is hoisted much earlier into the path where we can actually get a zero stride flowing through. Some fairly simple proofs handle the cases which show up in practice. The only test changes are the cases where we really do need a non-zero divider to produce the right result.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

11675

We make exactly the same isLoopEntryGuardedByCond() call later; can we avoid calling it twice?

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

11675

I assume you're concerned about compile time? If so, I'd prefer to land the simple change (this one), and then revisit if needed. I would not be surprised if the later one changed form anyways.

[efriedma]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

11675

As a practical matter, I'm not really concerned about compile-time here, I guess; we should be hitting wouldZeroStrideBeUB() very rarely in real code. Just feels a little weird. I'm okay landing this as-is for now, and we can consider refactoring once we're confident we're actually performing all the checks we need.

[aeubanks]

I've bisected a crash to this change

$ opt -passes='default<O3>' reduced.ll
opt: ../../llvm/lib/Analysis/ScalarEvolution.cpp:10521: bool llvm::ScalarEvolution::isLoopEntryGuardedByCond(const llvm::Loop *, ICmpInst::Predica
te, const llvm::SCEV *, const llvm::SCEV *): Assertion `isAvailableAtLoopEntry(RHS, L) && "RHS is not available at Loop Entry"' failed.

reduced.ll45 KBDownload

[efriedma]

Maybe we should look at threading the actual branch through to howManyLessThans, so we can use isKnownPredicateAt() or something like that. In the meantime, I'll recommit with an appropriate isLoopInvariant() check.

[efriedma]

Committed 205ed009

[reames]

Artur, Eli, thanks to each of you!

llvm/lib/Analysis/ScalarEvolution.cpp

if (!PositiveStride) {
     //
     // unsigned char i;
     // for(i=127; i<128; i+=129)
     //   A[i] = i;
     //
     if (PredicatedIV || !NoWrap || isKnownNonPositive(Stride) ||
         !loopIsFiniteByAssumption(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 = [&]() {
+      // 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()) {
+      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.body:                                         ; preds = %entry, %for.body
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 
 ; Check that we are able to compute trip count of a loop without an entry guard.
-; CHECK-LABEL: Determining loop execution counts for: @foo2
-; CHECK: backedge-taken count is ((-1 + (%n smax %s)) /u %s)
+; CHECK: Determining loop execution counts for: @foo2
+; CHECK: backedge-taken count is ((-1 + (-1 * %s) + (1 umax %s) + (%n smax %s)) /u (1 umax %s))
 
 ; We should have a conservative estimate for the max backedge taken count for
 ; loops with unknown stride.
 ; CHECK: max backedge-taken count is -1
 
 define void @foo2(i32* nocapture %A, i32 %n, i32 %s) mustprogress {
 entry:
   br label %for.body
for.body:                                         ; preds = %entry, %for.body
   %cmp = icmp slt i32 %add, %n
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ; Same as foo2, but with mustprogress on loop, not function
-; CHECK-LABEL: Determining loop execution counts for: @foo4
-; CHECK: backedge-taken count is ((-1 + (%n smax %s)) /u %s)
+; CHECK: Determining loop execution counts for: @foo4
+; CHECK: backedge-taken count is ((-1 + (-1 * %s) + (1 umax %s) + (%n smax %s)) /u (1 umax %s))
 ; CHECK: max backedge-taken count is -1
 
 define void @foo4(i32* nocapture %A, i32 %n, i32 %s) {
 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
   %0 = load i32, i32* %arrayidx, align 4
   %inc = add nsw i32 %0, 1
   store i32 %inc, i32* %arrayidx, align 4
   %add = add nsw i32 %i.05, %s
   %cmp = icmp slt i32 %add, %n
   br i1 %cmp, label %for.body, label %for.end, !llvm.loop !8
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
 ; A more complex case with pre-increment compare instead of post-increment.
 ; CHECK-LABEL: Determining loop execution counts for: @foo5
-; CHECK: Loop %for.body: backedge-taken count is ((-1 + (-1 * %start) + (%n smax %start) + %s) /u %s)
+; CHECK: Loop %for.body: backedge-taken count is ((-1 + (-1 * %start) + (1 umax %s) + (%n smax %start)) /u (1 umax %s))
 
 ; We should have a conservative estimate for the max backedge taken count for
 ; loops with unknown stride.
 ; CHECK: max backedge-taken count is -1
 
 define void @foo5(i32* nocapture %A, i32 %n, i32 %s, i32 %start) mustprogress {
 entry:
   br label %for.body