[ScalarEvolution] Refine computeMaxBECountForLT to be accurate in more cases.

[efriedma]

Summary

Allow arbitrary strides, and make sure we return the correct result when the backedge-taken count is zero.

Inspired by D104140.

[reames]

LGTM w/minor comments.

llvm/lib/Analysis/ScalarEvolution.cpp

11549

This is harmless, but I believe we've already established this by the time this method is invoked.

llvm/test/Analysis/ScalarEvolution/max-trip-count.ll

459

Can you add a test case for the i1 case? I had to write it out to convince myself of your comment and I think having the test in the change would help clarify for later readers.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

11549

At the moment, yes, but we're probably going to drop that check?

llvm/test/Analysis/ScalarEvolution/max-trip-count.ll

459

I can add the test, but it will just return CouldNotCompute without further changes; isKnownNonPositive(Stride) is true if Stride is an i1.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

11549

I'd meant in the bit of code which forces stride to umin(1,stride) if we can't prove it non-zero in the caller.

llvm/test/Analysis/ScalarEvolution/max-trip-count.ll

459

Please add it anyways. :)

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::getUDivCeilSCEV(const SCEV *N, const SCEV *D) {
   return getAddExpr(MinNOne, getUDivExpr(NMinusOne, D));
 }
 
 const SCEV *ScalarEvolution::computeMaxBECountForLT(const SCEV *Start,
                                                     const SCEV *Stride,
                                                     const SCEV *End,
                                                     unsigned BitWidth,
                                                     bool IsSigned) {
+  // The logic in this function assumes we can represent a positive stride.
+  // If we can't, the backedge-taken count must be zero.
+  if (IsSigned && BitWidth == 1)
+    return getZero(Stride->getType());
 
-  assert(!isKnownNonPositive(Stride) &&
-         "Stride is expected strictly positive!");
   // Calculate the maximum backedge count based on the range of values
   // permitted by Start, End, and Stride.
   const SCEV *MaxBECount;
   APInt MinStart =
       IsSigned ? getSignedRangeMin(Start) : getUnsignedRangeMin(Start);
 
   APInt StrideForMaxBECount =
       IsSigned ? getSignedRangeMin(Stride) : getUnsignedRangeMin(Stride);
 
-  // We already know that the stride is positive, so we paper over conservatism
-  // in our range computation by forcing StrideForMaxBECount to be at least one.
-  // In theory this is unnecessary, but we expect MaxBECount to be a
-  // SCEVConstant, and (udiv <constant> 0) is not constant folded by SCEV (there
-  // is nothing to constant fold it to).
-  APInt One(BitWidth, 1, IsSigned);
-  StrideForMaxBECount = APIntOps::smax(One, StrideForMaxBECount);
+  // We assume either the stride is positive, or the backedge-taken count
+  // is zero. So force StrideForMaxBECount to be at least one.
+  APInt One(BitWidth, 1);
+  StrideForMaxBECount = IsSigned ? APIntOps::smax(One, StrideForMaxBECount)
+                                 : APIntOps::umax(One, StrideForMaxBECount);
 
   APInt MaxValue = IsSigned ? APInt::getSignedMaxValue(BitWidth)
                             : APInt::getMaxValue(BitWidth);
   APInt Limit = MaxValue - (StrideForMaxBECount - 1);
 
   // Although End can be a MAX expression we estimate MaxEnd considering only
   // the case End = RHS of the loop termination condition. This is safe because
   // in the other case (End - Start) is zero, leading to a zero maximum backedge
   // taken count.
   APInt MaxEnd = IsSigned ? APIntOps::smin(getSignedRangeMax(End), Limit)
                           : APIntOps::umin(getUnsignedRangeMax(End), Limit);
 
+  // MaxBECount = ceil((max(MaxEnd, MinStart) - MinStart) / Stride)
+  MaxEnd = IsSigned ? APIntOps::smax(MaxEnd, MinStart)
+                    : APIntOps::umax(MaxEnd, MinStart);
+
   MaxBECount = getUDivCeilSCEV(getConstant(MaxEnd - MinStart) /* Delta */,
                                getConstant(StrideForMaxBECount) /* Step */);
 
   return MaxBECount;
 }
 
 ScalarEvolution::ExitLimit
 ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,

llvm/test/Analysis/ScalarEvolution/max-trip-count.ll

loop:
   %iv.next = add i32 %iv, -1
   %n = load atomic i32, i32* %n_addr unordered, align 4
   %cmp = icmp sgt i32 %iv.next, %n
   br i1 %cmp, label %loop, label %loop.exit
 
 loop.exit:
   ret void
 }
+
+define void @max_overflow(i8 %n) mustprogress {
+; CHECK-LABEL: Determining loop execution counts for: @max_overflow
+; CHECK: Loop %loop: backedge-taken count is (-126 + (126 smax %n))<nsw>
+; CHECK: Loop %loop: max backedge-taken count is 0
+entry:
+  br label %loop
+
+loop:
+  %i = phi i8 [ 63, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i8 %i, 63
+  %t = icmp slt i8 %i.next, %n
+  br i1 %t, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Max backedge-taken count is zero.
+define void @bool_stride(i1 %s, i1 %n) mustprogress {
+; CHECK-LABEL: Determining loop execution counts for: @bool_stride
+; CHECK: Loop %loop: Unpredictable backedge-taken count.
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+entry:
+  br label %loop
+
+loop:
+  %i = phi i1 [ -1, %entry ], [ %i.next, %loop ]
+  %i.next = add nsw i1 %i, %s
+  %t = icmp slt i1 %i.next, %n
+  br i1 %t, label %loop, label %exit
+
+exit:
+  ret void
+}