[ScalarEvolution] Handle <= and >= in non infinite loops

[wsmoses]

Summary

Extend scalar evolution to handle >= and <= if a loop is known to be finite and the induction variable guards the condition. Specifically, with these assumptions lhs <= rhs is equivalent to lhs < rhs + 1 and lhs >= rhs to lhs > rhs -1.

In the case of lhs <= rhs, this is true since the only case these are not equivalent
is when rhs == unsigned/signed intmax, which would have resulted in an infinite loop.

In the case of lhs >= rhs, this is true since the only case these are not equivalent
is when rhs == unsigned/signed intmin, which would again have resulted in an infinite loop.

[nikic]

Why does this add a FiniteLoops flag to SCEV, rather than using mustprogress attributes/metadata? I'm not convinced that should be added, and in either case this change is independent from the change to exit limit logic.

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

1750

Is there any particular reason these can't use normal print<scalar-evolution> tests? See various llvm/test/Analysis/ScalarEvolution/trip-count*.ll tests for example.

[reames]

I second @nikic comments. Also, we already have quite similar in SimplifyICmpOperands, so if there's a way to common the code to use the mustprogress/guarded exit fact there, that would be preferred.

[wsmoses]

Can do regarding SimplifyICmp and also the trip count tests.

As for the flag, a question for you all:
The existing llvm metadata for mustprogress is insufficient as it only implies the loop is finite if it does not interact with the environment of memory. Here, however, it would be nice if we could more strongly apply this to codes (e.g. if there was a call in the loop). This code came from a project where we did so with an additional flag (in that case all loops can be assumed finite), though I concur an existing way in the IR would be nice. Perhaps a finite loop metadata?

[wsmoses]

Move logic into simplifyicmp

[nikic]

In D118090#3269683, @wsmoses wrote:

As for the flag, a question for you all:
The existing llvm metadata for mustprogress is insufficient as it only implies the loop is finite if it does not interact with the environment of memory. Here, however, it would be nice if we could more strongly apply this to codes (e.g. if there was a call in the loop). This code came from a project where we did so with an additional flag (in that case all loops can be assumed finite), though I concur an existing way in the IR would be nice. Perhaps a finite loop metadata?

Adding loop metadata for this purpose sounds sensible to me.

[wsmoses]

Use isFinite

[wsmoses]

@nikic, mind taking another look here. I've gone ahead and made the requisite changes and set up the relevant infrastructure.

This now does not have a dependency on the langref change (though once that lands this should automatically become more powerful whenever that loop metadata is available).

[lebedev.ri]

llvm/lib/Analysis/ScalarEvolution.cpp

10120

[wsmoses]

Change order evaluating condition

[jdoerfert]

llvm/lib/Analysis/ScalarEvolution.cpp

10123

Nit: format above.

[wsmoses]

Fix format

[lebedev.ri]

Conceptually, this makes sense to me, but it would be much better to first get the langref change codified,
because this makes the same legality reasoning, and clearly langref is the place for legality wording.

[reames]

llvm/lib/Analysis/LoopInfo.cpp

1122 ↗

(On Diff #403739)

This is - in the current patch - a form of attribute inference. We prefer inference be done once - either in the core API itself, or explicitly via materialization in IR - not duplicated for each consumer.

i.e. Calling code should assume that willreturn loops are mustprogress, not check for that case explicitly.

llvm/lib/Analysis/ScalarEvolution.cpp

7020

This change by itself should be testable and profitable. I'd advise separating the SimplifyICmpOperands bits into a following change.

Or said differently, a patch which causes loopIsFiniteByAssumption for loops in willreturn functions seems entirely reasonable on it's own without any new metadata.

[wsmoses]

llvm/lib/Analysis/ScalarEvolution.cpp

7020

I've made a version of this PR that just contains the isFinite component here (https://reviews.llvm.org/D118429) though frankly I'm not sure how to set up a test for it.

[wsmoses]

Remove mustprogress if willreturn

[wsmoses]

Rebase after removing/landing the willreturn finite

[lebedev.ri]

LG, but please wait for @nikic / @reames / @mkazantsev.

[nikic]

Looks fine to me as well.

llvm/include/llvm/Analysis/ScalarEvolution.h

1120

controlling

llvm/lib/Analysis/ScalarEvolution.cpp

8478

As the same check is repeated below, extract it into a variable?

10120

controlling

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

9 ↗

(On Diff #404102)

Please avoid attribute groups for test input, just put the willreturn directly here.

It would also be good to have a negative test that shows that the BECount is not inferred without willreturn.

[wsmoses]

Address comments

[mtrofin]

This change has the side-effect of making SCEVExpander::isHighCostExpansion return true and thus block loop unrolling, which is the root cause of the performance degradation that led to 7e3606f43c63.

Before, the expression was:

(1 + ((-2 + %1) /u 2))<nuw>

with this change, the expression becomes:

(1 + ((-3 + (4 smax (1 + %1)<nsw>))<nsw> /u 2))<nuw><nsw>

The Budget is always 4, but the second expression trips over it (the (4 smax (1 + %1)<nsw>) subexpression raises the cost to 5)

@wsmoses, is there a follow-up for mitigating cost estimate implications?

[nikic]

In D118090#3351623, @mtrofin wrote:

This change has the side-effect of making SCEVExpander::isHighCostExpansion return true and thus block loop unrolling, which is the root cause of the performance degradation that led to 7e3606f43c63.

Before, the expression was:

(1 + ((-2 + %1) /u 2))<nuw>

with this change, the expression becomes:

(1 + ((-3 + (4 smax (1 + %1)<nsw>))<nsw> /u 2))<nuw><nsw>

The Budget is always 4, but the second expression trips over it (the (4 smax (1 + %1)<nsw>) subexpression raises the cost to 5)

Could you please provide the input IR that is affected? We'd probably want to generate a better BECount than try to adjust cost modelling.

[mtrofin]

In D118090#3351651, @nikic wrote:

In D118090#3351623, @mtrofin wrote:

This change has the side-effect of making SCEVExpander::isHighCostExpansion return true and thus block loop unrolling, which is the root cause of the performance degradation that led to 7e3606f43c63.

Before, the expression was:

(1 + ((-2 + %1) /u 2))<nuw>

with this change, the expression becomes:

(1 + ((-3 + (4 smax (1 + %1)<nsw>))<nsw> /u 2))<nuw><nsw>

The Budget is always 4, but the second expression trips over it (the (4 smax (1 + %1)<nsw>) subexpression raises the cost to 5)

Could you please provide the input IR that is affected? We'd probably want to generate a better BECount than try to adjust cost modelling.

Ack - let me try to distill it down to something shareable (so it can easily become a testcase, I imagine we'd want that). Wanted to first check if this was expected and there was a plan, before spending more time.

[wsmoses]

I concur with @nikic

[mtrofin]

In D118090#3351732, @wsmoses wrote:

I concur with @nikic

Sorry for the delay, I managed to extract a repro, please see https://github.com/llvm/llvm-project/issues/54191

The repro could be smaller, but I wasn't successful at shrinking it any further. It's down to the 1 function though, and I left additional pointers in the issue.

Thanks!

[jaykang10]

I am also getting performance degradation from this patch. The backedge count with the max is considered as high cost and it blocks to rewrite exit value in IndVarSimplify pass. It affects LSR's decision to rewrite IV and it causes additional instructions in loop...
As far as I understand, the expression of backedge count describes (max(End,Start)-Start)/Stride normally. If the expression satisfies with (max(RHS,Start) > Start - Stride, the expression is refined simply.
In order to prove (max(RHS,Start) > Start - Stride, SCEV is using below code.

// Can we prove (max(RHS,Start) > Start - Stride?
if (isLoopEntryGuardedByCond(L, Cond, OrigStartMinusStride, OrigStart) &&
    isLoopEntryGuardedByCond(L, Cond, OrigStartMinusStride, OrigRHS)) {

Let's see the reduced example of @nikic on https://github.com/llvm/llvm-project/issues/54191 with above code.

; RUN: opt -S -passes='print<scalar-evolution>' < %s
define void @test(i64 %n) mustprogress {
entry:
  %guard = icmp sgt i64 %n, 1
  br i1 %guard, label %loop, label %exit
  
loop:
  %iv = phi i64 [ 2, %entry ], [ %iv.next, %loop ]
  %iv.next = add nuw nsw i64 %iv, 2
  %cmp = icmp sle i64 %iv.next, %n
  br i1 %cmp, label %loop, label %exit
  
exit:
  ret void
}

With this patch, the second isLoopEntryGuardedByCond is failed because the loop condition's upper bound has been changed from %n to %n + 1 and it is over the guard condition's upper bound which is %n.
Without this patch, on SimplifyICmpOperands, the lower bound is changed from 4 to 3because it is not minimum signed value and upper bound is maximum signed value.
At this point, I have questions.

1. Can we check LHS first on SimplifyICmpOperands as below?

    if (!getSignedRangeMin(LHS).isMinSignedValue()) {
...
    } else if (ControllingFiniteLoop || !getSignedRangeMax(RHS).isMaxSignedValue()) {
...
    }

2. Can we change the default value of SCEVCheapExpansionBudget to bigger value?
   • The smax's cost checks the cost of Instruction::ICmp and Instruction::Select. The default value 4 could not be good enough for the smax.
3. If the upper bound is signed maximum signed value, the upper bound change with +1 could cause overflow and isLoopEntryGuardedByCond returns false...
   • It could be safe to check just maximum signed value of upper bound !getSignedRangeMax(RHS).isMaxSignedValue() without ControllingFiniteLoop .

How do you think about it? If I missed something, please let me know.

[efriedma]

This appears to have caused https://github.com/llvm/llvm-project/issues/60944

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) {
     return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
   }
   LLVM_NODISCARD static bool hasFlags(SCEV::NoWrapFlags Flags,
                                       SCEV::NoWrapFlags TestFlags) {
     return TestFlags == maskFlags(Flags, TestFlags);
   };
 
+  /// A boolean denoting whether all loops are finite by assumption.
+  bool FiniteLoops;
+
   ScalarEvolution(Function &F, TargetLibraryInfo &TLI, AssumptionCache &AC,
-                  DominatorTree &DT, LoopInfo &LI);
+                  DominatorTree &DT, LoopInfo &LI, bool FiniteLoops = false);
   ScalarEvolution(ScalarEvolution &&Arg);
   ~ScalarEvolution();
 
   LLVMContext &getContext() const { return F.getContext(); }
 
   /// Test if values of the given type are analyzable within the SCEV
   /// framework. This primarily includes integer types, and it can optionally
   /// include pointer types if the ScalarEvolution class has access to
getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate Pred,
                                                 const SCEV *MaxIter);
 
   /// Simplify LHS and RHS in a comparison with predicate Pred. Return true
   /// iff any changes were made. If the operands are provably equal or
   /// unequal, LHS and RHS are set to the same value and Pred is set to either
   /// ICMP_EQ or ICMP_NE.
   bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
                             const SCEV *&RHS, unsigned Depth = 0);
 
   /// Return the "disposition" of the given SCEV with respect to the given
   /// loop.
   LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L);
 
   /// Return true if the value of the given SCEV is unchanging in the
   /// specified loop.
   bool isLoopInvariant(const SCEV *S, const Loop *L);
 

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getLoopProperties(const Loop *L) {
 
   return Itr->second;
 }
 
 bool ScalarEvolution::loopIsFiniteByAssumption(const Loop *L) {
   // A mustprogress loop without side effects must be finite.
   // TODO: The check used here is very conservative.  It's only *specific*
   // side effects which are well defined in infinite loops.
-  return isMustProgress(L) && loopHasNoSideEffects(L);
+  return FiniteLoops || isMustProgress(L) && loopHasNoSideEffects(L);
 }
 
 const SCEV *ScalarEvolution::createSCEV(Value *V) {
   if (!isSCEVable(V->getType()))
     return getUnknown(V);
 
   if (Instruction *I = dyn_cast<Instruction>(V)) {
     // Don't attempt to analyze instructions in blocks that aren't
if (isLoopInvariant(LHS, L) && !isLoopInvariant(RHS, L)) {
     std::swap(LHS, RHS);
     Pred = ICmpInst::getSwappedPredicate(Pred);
   }
 
   // Simplify the operands before analyzing them.
   (void)SimplifyICmpOperands(Pred, LHS, RHS);
 
   // If we have a comparison of a chrec against a constant, try to use value
   // ranges to answer this query.
   if (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS))
     if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
       if (AddRec->getLoop() == L) {
         // Form the constant range.
         ConstantRange CompRange =
             ConstantRange::makeExactICmpRegion(Pred, RHSC->getAPInt());
 
         const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(InnerLHS)) {
         Flags = setFlags(Flags, SCEV::FlagNW);
         SmallVector<const SCEV*> Operands{AR->operands()};
         Flags = StrengthenNoWrapFlags(this, scAddRecExpr, Operands, Flags);
         setNoWrapFlags(const_cast<SCEVAddRecExpr *>(AR), Flags);
       }
     }
   }
 
+  // Moreover, if the loop is assumed to be finite, and controls the exit, then
+  // lhs <= rhs is equivalent to lhs < rhs + 1 and lhs >= rhs to lhs > rhs -1.
+  // In the case of lhs <= rhs, this is true since the only case these are not
+  // equivalent is when rhs == unsigned/signed intmax, which would have resulted
+  // in an infinite loop. In the case of lhs >= rhs, this is true since the only
+  // case these are not equivalent is when rhs == unsigned/signed intmin, which
+  // would again have resulted in an infinite loop.
+  if (ControlsExit && isLoopInvariant(RHS, L) && loopIsFiniteByAssumption(L)) {
+    switch (Pred) {
+    case ICmpInst::ICMP_SLE: {
+      Pred = ICmpInst::ICMP_SLT;
+      auto One =
+          getConstant(ConstantInt::get(cast<IntegerType>(RHS->getType()), 1));
+      RHS = getAddExpr(RHS, One, SCEV::FlagNSW);
+      break;
+    }
+    case ICmpInst::ICMP_ULE: {
+      Pred = ICmpInst::ICMP_ULT;
+      auto One =
+          getConstant(ConstantInt::get(cast<IntegerType>(RHS->getType()), 1));
+      RHS = getAddExpr(RHS, One, SCEV::FlagNUW);
+      break;
+    }
+    case ICmpInst::ICMP_SGE: {
+      Pred = ICmpInst::ICMP_SGT;
+      auto MinusOne =
+          getConstant(ConstantInt::get(cast<IntegerType>(RHS->getType()), -1));
+      RHS = getAddExpr(RHS, MinusOne, SCEV::FlagNSW);
+      break;
+    }
+    case ICmpInst::ICMP_UGE: {
+      Pred = ICmpInst::ICMP_UGT;
+      auto MinusOne =
+          getConstant(ConstantInt::get(cast<IntegerType>(RHS->getType()), -1));
+      RHS = getAddExpr(RHS, MinusOne, SCEV::FlagNUW);
+      break;
+    }
+    }
+  }
+
   switch (Pred) {
   case ICmpInst::ICMP_NE: {                     // while (X != Y)
     // Convert to: while (X-Y != 0)
     if (LHS->getType()->isPointerTy()) {
       LHS = getLosslessPtrToIntExpr(LHS);
       if (isa<SCEVCouldNotCompute>(LHS))
         return LHS;
     }
if (HasSameValue(LHS, RHS)) {
     if (ICmpInst::isFalseWhenEqual(Pred))
       return TrivialCase(false);
   }
 
   // If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by
   // adding or subtracting 1 from one of the operands.
   switch (Pred) {
   case ICmpInst::ICMP_SLE:
     if (!getSignedRangeMax(RHS).isMaxSignedValue()) {
       RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
                        SCEV::FlagNSW);
       Pred = ICmpInst::ICMP_SLT;
       Changed = true;
     } else if (!getSignedRangeMin(LHS).isMinSignedValue()) {
       LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS,
                        SCEV::FlagNSW);
       Pred = ICmpInst::ICMP_SLT;
       Changed = true;
     }
     break;
ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
   : CallbackVH(V), SE(se) {}
 
 //===----------------------------------------------------------------------===//
 //                   ScalarEvolution Class Implementation
 //===----------------------------------------------------------------------===//
 
 ScalarEvolution::ScalarEvolution(Function &F, TargetLibraryInfo &TLI,
                                  AssumptionCache &AC, DominatorTree &DT,
-                                 LoopInfo &LI)
-    : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI),
+                                 LoopInfo &LI, bool FiniteLoops)
+    : F(F), TLI(TLI), AC(AC), DT(DT), LI(LI), FiniteLoops(FiniteLoops),
       CouldNotCompute(new SCEVCouldNotCompute()), ValuesAtScopes(64),
       LoopDispositions(64), BlockDispositions(64) {
   // To use guards for proving predicates, we need to scan every instruction in
   // relevant basic blocks, and not just terminators.  Doing this is a waste of
   // time if the IR does not actually contain any calls to
   // @llvm.experimental.guard, so do a quick check and remember this beforehand.
   //
   // This pessimizes the case where a pass that preserves ScalarEvolution wants
   // to _add_ guards to the module when there weren't any before, and wants
   // ScalarEvolution to optimize based on those guards.  For now we prefer to be
   // efficient in lieu of being smart in that rather obscure case.
 
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
 }
 
 ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
     : F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
-      LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)),
+      LI(Arg.LI), FiniteLoops(Arg.FiniteLoops),
+      CouldNotCompute(std::move(Arg.CouldNotCompute)),
       ValueExprMap(std::move(Arg.ValueExprMap)),
       PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
       PendingPhiRanges(std::move(Arg.PendingPhiRanges)),
       PendingMerges(std::move(Arg.PendingMerges)),
       MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),

llvm/unittests/Analysis/ScalarEvolutionTest.cpp

protected:
   TargetLibraryInfo TLI;
 
   std::unique_ptr<AssumptionCache> AC;
   std::unique_ptr<DominatorTree> DT;
   std::unique_ptr<LoopInfo> LI;
 
   ScalarEvolutionsTest() : M("", Context), TLII(), TLI(TLII) {}
 
-  ScalarEvolution buildSE(Function &F) {
+  ScalarEvolution buildSE(Function &F, bool FiniteLoops = false) {
     AC.reset(new AssumptionCache(F));
     DT.reset(new DominatorTree(F));
     LI.reset(new LoopInfo(*DT));
-    return ScalarEvolution(F, TLI, *AC, *DT, *LI);
+    return ScalarEvolution(F, TLI, *AC, *DT, *LI, FiniteLoops);
   }
 
   void runWithSE(
       Module &M, StringRef FuncName,
-      function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test) {
+      function_ref<void(Function &F, LoopInfo &LI, ScalarEvolution &SE)> Test,
+      bool FiniteLoops = false) {
     auto *F = M.getFunction(FuncName);
     ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
-    ScalarEvolution SE = buildSE(*F);
+    ScalarEvolution SE = buildSE(*F, FiniteLoops);
     Test(*F, *LI, SE);
   }
 
   static Optional<APInt> computeConstantDifference(ScalarEvolution &SE,
                                                    const SCEV *LHS,
                                                    const SCEV *RHS) {
     return SE.computeConstantDifference(LHS, RHS);
   }
runWithSE(*M, "foo", [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
     auto *ScevIV = SE.getSCEV(getInstructionByName(F, "iv"));
     const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
 
     const SCEV *ITC = SE.getConstantMaxTripCountFromArray(L);
     EXPECT_TRUE(isa<SCEVCouldNotCompute>(ITC));
   });
 }
 
+TEST_F(ScalarEvolutionsTest, ComputeTripForFiniteSLE) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M =
+      parseAssemblyString("define void @foo(i32 %len) { "
+                          "entry: "
+                          "  br label %for.body "
+                          "for.body: "
+                          "  %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ] "
+                          "  %inc = add i32 %iv, 1"
+                          "  %cmp = icmp sle i32 %iv, %len "
+                          "  br i1 %cmp, label %for.body, label %for.end "
+                          "for.end: "
+                          "  ret void "
+                          "} ",
+                          Err, C);
+  ASSERT_TRUE(M && "Could not parse module?");
+  ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(
+      *M, "foo",
+      [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        auto *IV = getInstructionByName(F, "iv");
+        auto *ScevIV = SE.getSCEV(IV);
+        const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
+        const SCEV *ITC = SE.getExitCount(L, IV->getParent());
+        // Assert exit count == smax(0, 1 + %len);
+        auto MaxExpr = dyn_cast<SCEVSMaxExpr>(ITC);
+        EXPECT_TRUE(MaxExpr);
+        auto AddOne = dyn_cast<SCEVAddExpr>(MaxExpr->getOperand(1));
+        EXPECT_TRUE(AddOne);
+        auto One = dyn_cast<SCEVConstant>(AddOne->getOperand(0));
+        EXPECT_TRUE(One);
+        EXPECT_TRUE(One->getAPInt().isOne());
+        auto Len = dyn_cast<SCEVUnknown>(AddOne->getOperand(1));
+        EXPECT_TRUE(Len);
+        EXPECT_TRUE(Len->getValue()->getName() == "len");
+      },
+      /*FiniteLoops=*/true);
+}
+
+TEST_F(ScalarEvolutionsTest, ComputeTripForFiniteULE) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M =
+      parseAssemblyString("define void @foo(i32 %len) { "
+                          "entry: "
+                          "  br label %for.body "
+                          "for.body: "
+                          "  %iv = phi i32 [ %inc, %for.body ], [ 0 , %entry ] "
+                          "  %inc = add i32 %iv, 1"
+                          "  %cmp = icmp ule i32 %iv, %len "
+                          "  br i1 %cmp, label %for.body, label %for.end "
+                          "for.end: "
+                          "  ret void "
+                          "} ",
+                          Err, C);
+  ASSERT_TRUE(M && "Could not parse module?");
+  ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(
+      *M, "foo",
+      [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        auto *IV = getInstructionByName(F, "iv");
+        auto *ScevIV = SE.getSCEV(IV);
+        const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
+        const SCEV *ITC = SE.getExitCount(L, IV->getParent());
+        // Assert exit count == umax(0, 1 + %len) == 1 + %len;
+        auto AddOne = dyn_cast<SCEVAddExpr>(ITC);
+        EXPECT_TRUE(AddOne);
+        auto One = dyn_cast<SCEVConstant>(AddOne->getOperand(0));
+        EXPECT_TRUE(One);
+        EXPECT_TRUE(One->getAPInt().isOne());
+        auto Len = dyn_cast<SCEVUnknown>(AddOne->getOperand(1));
+        EXPECT_TRUE(Len);
+        EXPECT_TRUE(Len->getValue()->getName() == "len");
+      },
+      /*FiniteLoops=*/true);
+}
+
+TEST_F(ScalarEvolutionsTest, ComputeTripForFiniteSGE) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(
+      "define void @foo(i32 %len) { "
+      "entry: "
+      "  br label %for.body "
+      "for.body: "
+      "  %iv = phi i32 [ %inc, %for.body ], [ %len, %entry ] "
+      "  %inc = add i32 %iv, -1"
+      "  %cmp = icmp sge i32 %iv, 1 "
+      "  br i1 %cmp, label %for.body, label %for.end "
+      "for.end: "
+      "  ret void "
+      "} ",
+      Err, C);
+  ASSERT_TRUE(M && "Could not parse module?");
+  ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(
+      *M, "foo",
+      [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        auto *IV = getInstructionByName(F, "iv");
+        auto *ScevIV = SE.getSCEV(IV);
+        const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
+        const SCEV *ITC = SE.getExitCount(L, IV->getParent());
+        // Assert exit count == -1 * (0 smin %len) + %len == if %len <= 0 then 0
+        // else len
+        auto AddExpr = dyn_cast<SCEVAddExpr>(ITC);
+        EXPECT_TRUE(AddExpr);
+        auto MulMinusOne = dyn_cast<SCEVMulExpr>(AddExpr->getOperand(0));
+        EXPECT_TRUE(MulMinusOne);
+        auto MinusOne = dyn_cast<SCEVConstant>(MulMinusOne->getOperand(0));
+        EXPECT_TRUE(MinusOne);
+        EXPECT_TRUE(MinusOne->getAPInt().isAllOnes());
+        auto SMin = dyn_cast<SCEVSMinExpr>(MulMinusOne->getOperand(1));
+        EXPECT_TRUE(SMin);
+        auto Zero = dyn_cast<SCEVConstant>(SMin->getOperand(0));
+        EXPECT_TRUE(Zero);
+        EXPECT_TRUE(Zero->getAPInt().isZero());
+        auto Len1 = dyn_cast<SCEVUnknown>(SMin->getOperand(1));
+        EXPECT_TRUE(Len1);
+        EXPECT_TRUE(Len1->getValue()->getName() == "len");
+        auto Len2 = dyn_cast<SCEVUnknown>(AddExpr->getOperand(1));
+        EXPECT_TRUE(Len2);
+        EXPECT_TRUE(Len2->getValue()->getName() == "len");
+      },
+      /*FiniteLoops=*/true);
+}
+
+TEST_F(ScalarEvolutionsTest, ComputeTripForFiniteUGE) {
+  LLVMContext C;
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(
+      "define void @foo(i32 %len) { "
+      "entry: "
+      "  br label %for.body "
+      "for.body: "
+      "  %iv = phi i32 [ %inc, %for.body ], [ %len , %entry ] "
+      "  %inc = add i32 %iv, -1"
+      "  %cmp = icmp uge i32 %iv, 1 "
+      "  br i1 %cmp, label %for.body, label %for.end "
+      "for.end: "
+      "  ret void "
+      "} ",
+      Err, C);
+  ASSERT_TRUE(M && "Could not parse module?");
+  ASSERT_TRUE(!verifyModule(*M) && "Must have been well formed!");
+
+  runWithSE(
+      *M, "foo",
+      [](Function &F, LoopInfo &LI, ScalarEvolution &SE) {
+        auto *IV = getInstructionByName(F, "iv");
+        auto *ScevIV = SE.getSCEV(IV);
+        const Loop *L = cast<SCEVAddRecExpr>(ScevIV)->getLoop();
+        const SCEV *ITC = SE.getExitCount(L, IV->getParent());
+        // Assert exit count == len
+        auto Len = dyn_cast<SCEVUnknown>(ITC);
+        EXPECT_TRUE(Len);
+        EXPECT_TRUE(Len->getValue()->getName() == "len");
+      },
+      /*FiniteLoops=*/true);
+}
+
 }  // end namespace llvm