[SCEV] Teach SCEV to find maxBECount when loop endbound is variant

[anna]

Summary

This patch teaches SCEV to calculate the maxBECount when the end bound
of the loop can vary. Note that we cannot calculate the exactBECount.

This will only be done when both conditions are satisfied:

1. the loop termination condition is strictly LT.
2. the IV is proven to not overflow.

This provides more information to users of SCEV and can be used to
improve identification of finite loops.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

9693 ↗

(On Diff #118703)

If the stride is known negative and IsSigned is true, can we return computeMaxBECount(End, -Stride, Start, BitWidth, IsSigned) instead of conservative estimate?

9694 ↗

(On Diff #118703)

Do we have a guarantee that stride is not zero? I think we should bail early unless we proved it or assert on that.

9710 ↗

(On Diff #118703)

Please add name for the last parameter in /* */

9808 ↗

(On Diff #118703)

Do we have a guarantee that the IV increment has no wrap flag set? Otherwise I don't believe it works for stride other than 1. For example:

L = load volatile ...
for (int i = 0; i < L; i += 2) {
  ...
  L = load volatile ...
}

If L is always SINT_MAX, this loop is infinite (if IV increment doesn't have nsw flag set).

For stride = 1 I think it should work fine even without nsw: we always stop when i = SINT_MAX at most, but for other step values we can leap across it.

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

345 ↗

(On Diff #118703)

Please add a test that if iv.next does not have nsw flag for this example then the max backage-taken count is unpredictable (this loop is infinite if start = 0, n is always SINT_MAX) because we leap across SINT_MAX.

[anna]

lib/Analysis/ScalarEvolution.cpp

9693 ↗

(On Diff #118703)

This code is never used for zero value stride or isKnownNegative. Please see line 9787 where we bail out on zero value and negative strides.

The computeMaxBE code is an NFC refactoring of existing maxBECount calculation when exactBECount is not known. This patch just uses the existing code for variant RHS as well, and relies on already existing overflow checks.

9694 ↗

(On Diff #118703)

yes, as mentioned in response above. I'll add an assert.

9808 ↗

(On Diff #118703)

All the overflow tests are already done above and it handles the case you mention: stride > 1, stride is not positive etc. For clarity, that's the comment added just above this code at line 9806.

Yes, for stride =1, we are fine without nsw because of the strictly LT condition. I've also added a testcase for that.

I will add a testcase for stride > 1, without nsw flag and confirm what I've said is true.

[anna]

Addressed reviewer comments: added more tests regarding overflow, stride negative, stride unknown.
Updated a failing test where we now have more granular max BECount taken
value (This test update was missed in the original diff).

[mkazantsev]

LGTM

lib/Analysis/ScalarEvolution.cpp

9701 ↗

(On Diff #118780)

Maybe make it

MaxValue = IsSigned ? APInt::getSignedMaxValue(BitWidth) : APInt::getMaxValue(BitWidth);
Limit = MaxValue - (StrideForMaxBECount - 1);

to reduce code duplication? Just a suggestion.

[sanjoy]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

9692

This logic is specific to {Start,+,Stride} SLT End, right? If so, please name it in a way to make that obvious and mention that in the comment.

[anna]

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

9692

The logic is specific to {Start,+,Stride} LT End, it can be s< or u<.

I'll change it to computeMaxBECountForLT and add a comment about the type of addrec and termination condition that's supported.

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

private:
   Optional<std::pair<const SCEV *, SmallVector<const SCEVPredicate *, 3>>>
   createAddRecFromPHIWithCastsImpl(const SCEVUnknown *SymbolicPHI);
 
   /// Compute the backedge taken count knowing the interval difference, the
   /// stride and presence of the equality in the comparison.
   const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
                              bool Equality);
 
+  // Compute the maximum backedge count based on the range of values
+  // permitted by Start, End, and Stride.
+  const SCEV *computeMaxBECount(const SCEV *Start, const SCEV *Stride,
+                                const SCEV *End, unsigned BitWidth,
+                                bool IsSigned);
+
   /// Verify if an linear IV with positive stride can overflow when in a
   /// less-than comparison, knowing the invariant term of the comparison,
   /// the stride and the knowledge of NSW/NUW flags on the recurrence.
   bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned,
                           bool NoWrap);
 
   /// Verify if an linear IV with negative stride can overflow when in a
   /// greater-than comparison, knowing the invariant term of the comparison,

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

 const SCEV *ScalarEvolution::computeBECount(const SCEV *Delta, const SCEV *Step,
                                             bool Equality) {
   const SCEV *One = getOne(Step->getType());
   Delta = Equality ? getAddExpr(Delta, Step)
                    : getAddExpr(Delta, getMinusSCEV(Step, One));
   return getUDivExpr(Delta, Step);
 }
 
+const SCEV *ScalarEvolution::computeMaxBECount(const SCEV *Start,
+                                               const SCEV *Stride,
+                                               const SCEV *End,
+                                               unsigned BitWidth,
+                                               bool IsSigned) {
+
+  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;
+
+  bool PositiveStride = isKnownPositive(Stride);
+  if (PositiveStride)
+    StrideForMaxBECount =
+        IsSigned ? getSignedRangeMin(Stride) : getUnsignedRangeMin(Stride);
+  else
+    // Using a stride of 1 is safe when computing max backedge taken count for
+    // a loop with unknown stride.
+    StrideForMaxBECount = APInt(BitWidth, 1, IsSigned);
+
+  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 = computeBECount(getConstant(MaxEnd - MinStart) /* Delta */,
+                              getConstant(StrideForMaxBECount) /* Step */,
+                              false /* Equality */);
+
+  return MaxBECount;
+}
+
 ScalarEvolution::ExitLimit
 ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS,
                                   const Loop *L, bool IsSigned,
                                   bool ControlsExit, bool AllowPredicates) {
   SmallPtrSet<const SCEVPredicate *, 4> Predicates;
-  // We handle only IV < Invariant
-  if (!isLoopInvariant(RHS, L))
-    return getCouldNotCompute();
 
   const SCEVAddRecExpr *IV = dyn_cast<SCEVAddRecExpr>(LHS);
   bool PredicatedIV = false;
 
   if (!IV && AllowPredicates) {
     // Try to make this an AddRec using runtime tests, in the first X
     // iterations of this loop, where X is the SCEV expression found by the
     // algorithm below.
if (!PositiveStride) {
     // conditions exploit NoWrapFlags, allowing to optimize in presence of
     // undefined behaviors like the case of C language.
     return getCouldNotCompute();
 
   ICmpInst::Predicate Cond = IsSigned ? ICmpInst::ICMP_SLT
                                       : ICmpInst::ICMP_ULT;
   const SCEV *Start = IV->getStart();
   const SCEV *End = RHS;
+  // When the RHS is not invariant, we do not know the end bound of the loop and
+  // cannot calculate the ExactBECount needed by ExitLimit. However, we can
+  // calculate the MaxBECount, given the start, stride and max value for the end
+  // bound of the loop (RHS), and the fact that IV does not overflow (which is
+  // checked above).
+  if (!isLoopInvariant(RHS, L)) {
+    const SCEV *MaxBECount = computeMaxBECount(
+        Start, Stride, RHS, getTypeSizeInBits(LHS->getType()), IsSigned);
+    return ExitLimit(getCouldNotCompute() /* ExactNotTaken */, MaxBECount,
+                     false /*MaxOrZero*/, Predicates);
+  }
   // If the backedge is taken at least once, then it will be taken
   // (End-Start)/Stride times (rounded up to a multiple of Stride), where Start
   // is the LHS value of the less-than comparison the first time it is evaluated
   // and End is the RHS.
   const SCEV *BECountIfBackedgeTaken =
     computeBECount(getMinusSCEV(End, Start), Stride, false);
   // If the loop entry is guarded by the result of the backedge test of the
   // first loop iteration, then we know the backedge will be taken at least
if (isa<SCEVConstant>(BECount))
     MaxBECount = BECount;
   else if (isa<SCEVConstant>(BECountIfBackedgeTaken)) {
     // If we know exactly how many times the backedge will be taken if it's
     // taken at least once, then the backedge count will either be that or
     // zero.
     MaxBECount = BECountIfBackedgeTaken;
     MaxOrZero = true;
   } else {
-    // Calculate the maximum backedge count based on the range of values
-    // permitted by Start, End, and Stride.
-    APInt MinStart = IsSigned ? getSignedRangeMin(Start)
-                              : getUnsignedRangeMin(Start);
-
-    unsigned BitWidth = getTypeSizeInBits(LHS->getType());
-
-    APInt StrideForMaxBECount;
-
-    if (PositiveStride)
-      StrideForMaxBECount =
-        IsSigned ? getSignedRangeMin(Stride)
-                 : getUnsignedRangeMin(Stride);
-    else
-      // Using a stride of 1 is safe when computing max backedge taken count for
-      // a loop with unknown stride.
-      StrideForMaxBECount = APInt(BitWidth, 1, IsSigned);
-
-    APInt Limit =
-      IsSigned ? APInt::getSignedMaxValue(BitWidth) - (StrideForMaxBECount - 1)
-               : APInt::getMaxValue(BitWidth) - (StrideForMaxBECount - 1);
-
-    // Although End can be a MAX expression we estimate MaxEnd considering only
-    // the case End = RHS. 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(RHS), Limit)
-               : APIntOps::umin(getUnsignedRangeMax(RHS), Limit);
-
-    MaxBECount = computeBECount(getConstant(MaxEnd - MinStart),
-                                getConstant(StrideForMaxBECount), false);
+    MaxBECount = computeMaxBECount(Start, Stride, RHS,
+                                   getTypeSizeInBits(LHS->getType()), IsSigned);
   }
 
   if (isa<SCEVCouldNotCompute>(MaxBECount) &&
       !isa<SCEVCouldNotCompute>(BECount))
     MaxBECount = getConstant(getUnsignedRangeMax(BECount));
 
   return ExitLimit(BECount, MaxBECount, MaxOrZero, Predicates);
 }

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

for.body:
   br i1 %cmp, label %for.body, label %loop.exit
 
 loop.exit:
   br label %exit
 
 exit:
   ret i32 0
 }
+
+; The end bound of the loop can change between iterations, so the exact trip
+; count is unknown, but SCEV can calculate the max trip count.
+define void @changing_end_bound(i32* %n_addr, i32* %addr) {
+; CHECK-LABEL: Determining loop execution counts for: @changing_end_bound
+; CHECK: Loop %loop: Unpredictable backedge-taken count.
+; CHECK: Loop %loop: max backedge-taken count is 2147483646
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+  %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
+  %val = load atomic i32, i32* %addr unordered, align 4
+  fence acquire
+  %acc.next = add i32 %acc, %val
+  %iv.next = add nsw i32 %iv, 1
+  %n = load atomic i32, i32* %n_addr unordered, align 4
+  %cmp = icmp slt i32 %iv.next, %n
+  br i1 %cmp, label %loop, label %loop.exit
+
+loop.exit:
+  ret void
+}
+
+; Similar test as above, but unknown start value.
+; Also, there's no nsw on the iv.next, but SCEV knows 
+; the termination condition is LT, so the IV cannot wrap.
+define void @changing_end_bound2(i32 %start, i32* %n_addr, i32* %addr) {
+; CHECK-LABEL: Determining loop execution counts for: @changing_end_bound2
+; CHECK: Loop %loop: Unpredictable backedge-taken count.
+; CHECK: Loop %loop: max backedge-taken count is -1
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
+  %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
+  %val = load atomic i32, i32* %addr unordered, align 4
+  fence acquire
+  %acc.next = add i32 %acc, %val
+  %iv.next = add i32 %iv, 1
+  %n = load atomic i32, i32* %n_addr unordered, align 4
+  %cmp = icmp slt i32 %iv.next, %n
+  br i1 %cmp, label %loop, label %loop.exit
+
+loop.exit:
+  ret void
+}
+
+; changing end bound and greater than one stride
+define void @changing_end_bound3(i32 %start, i32* %n_addr, i32* %addr) {
+; CHECK-LABEL: Determining loop execution counts for: @changing_end_bound3
+; CHECK: Loop %loop: Unpredictable backedge-taken count.
+; CHECK: Loop %loop: max backedge-taken count is 1073741823
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
+  %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
+  %val = load atomic i32, i32* %addr unordered, align 4
+  fence acquire
+  %acc.next = add i32 %acc, %val
+  %iv.next = add nsw i32 %iv, 4
+  %n = load atomic i32, i32* %n_addr unordered, align 4
+  %cmp = icmp slt i32 %iv.next, %n
+  br i1 %cmp, label %loop, label %loop.exit
+
+loop.exit:
+  ret void
+}
+
+; same as above test, but the IV can wrap around.
+; so the max backedge taken count is unpredictable.
+define void @changing_end_bound4(i32 %start, i32* %n_addr, i32* %addr) {
+; CHECK-LABEL: Determining loop execution counts for: @changing_end_bound4
+; CHECK: Loop %loop: Unpredictable backedge-taken count.
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
+  %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
+  %val = load atomic i32, i32* %addr unordered, align 4
+  fence acquire
+  %acc.next = add i32 %acc, %val
+  %iv.next = add i32 %iv, 4
+  %n = load atomic i32, i32* %n_addr unordered, align 4
+  %cmp = icmp slt i32 %iv.next, %n
+  br i1 %cmp, label %loop, label %loop.exit
+
+loop.exit:
+  ret void
+}
+
+; unknown stride. Since it's not knownPositive, we do not estimate the max
+; backedge taken count.
+define void @changing_end_bound5(i32 %stride, i32 %start, i32* %n_addr, i32* %addr) {
+; CHECK-LABEL: Determining loop execution counts for: @changing_end_bound5
+; CHECK: Loop %loop: Unpredictable backedge-taken count.
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
+  %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
+  %val = load atomic i32, i32* %addr unordered, align 4
+  fence acquire
+  %acc.next = add i32 %acc, %val
+  %iv.next = add nsw i32 %iv, %stride
+  %n = load atomic i32, i32* %n_addr unordered, align 4
+  %cmp = icmp slt i32 %iv.next, %n
+  br i1 %cmp, label %loop, label %loop.exit
+
+loop.exit:
+  ret void
+}
+
+; negative stride value
+define void @changing_end_bound6(i32 %start, i32* %n_addr, i32* %addr) {
+; CHECK-LABEL: Determining loop execution counts for: @changing_end_bound6
+; CHECK: Loop %loop: Unpredictable backedge-taken count.
+; CHECK: Loop %loop: Unpredictable max backedge-taken count.
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
+  %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
+  %val = load atomic i32, i32* %addr unordered, align 4
+  fence acquire
+  %acc.next = add i32 %acc, %val
+  %iv.next = add nsw i32 %iv, -1
+  %n = load atomic i32, i32* %n_addr unordered, align 4
+  %cmp = icmp slt i32 %iv.next, %n
+  br i1 %cmp, label %loop, label %loop.exit
+
+loop.exit:
+  ret void
+}

llvm/trunk/test/Transforms/LoopSimplify/preserve-scev.ll

 ; RUN: opt -S < %s -analyze -scalar-evolution -loop-simplify -scalar-evolution | FileCheck %s
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 @maxStat = external global i32
 
 ; LoopSimplify should invalidate SCEV when splitting out the
 ; inner loop.
 ;
 ; First SCEV print:
 ; CHECK-LABEL: Classifying expressions for: @test
 ; CHECK: %[[PHI:.*]] = phi i32 [ 0, %entry ], [ %{{.*}}, %if.then5 ], [ %[[PHI]], %if.end ]
 ; CHECK-LABEL: Determining loop execution counts for: @test
 ; CHECK: Loop %for.body18: Unpredictable backedge-taken count.
-; CHECK: Loop %for.body18: Unpredictable max backedge-taken count.
+; CHECK: Loop %for.body18: max backedge-taken count is 2147483646
 ; CHECK: Loop %for.body18: Unpredictable predicated backedge-taken count.
 ; CHECK: Loop %for.cond: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK: Loop %for.cond: Unpredictable max backedge-taken count.
 ; CHECK: Loop %for.cond: Unpredictable predicated backedge-taken count.
 ;
 ; Now simplify the loop, which should cause SCEV to re-compute more precise
 ; info here in addition to having preheader PHIs. Second SCEV print:
 ; CHECK-LABEL: Classifying expressions for: @test
 ; CHECK: phi i32 [ %{{.*}}, %if.then5 ], [ 0, %entry ]
 ; CHECK-LABEL: Determining loop execution counts for: @test
 ; CHECK: Loop %for.body18: Unpredictable backedge-taken count.
-; CHECK: Loop %for.body18: Unpredictable max backedge-taken count.
+; CHECK: Loop %for.body18: max backedge-taken count is 2147483646
 ; CHECK: Loop %for.body18: Unpredictable predicated backedge-taken count.
 ; CHECK: Loop %for.cond: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK: Loop %for.cond: max backedge-taken count is -2147483647
 ; CHECK: Loop %for.cond: Unpredictable predicated backedge-taken count.
 ; CHECK: Loop %for.cond.outer: <multiple exits> Unpredictable backedge-taken count.
 ; CHECK: Loop %for.cond.outer: Unpredictable max backedge-taken count.
 ; CHECK: Loop %for.cond.outer: Unpredictable predicated backedge-taken count.
 define i32 @test() nounwind {