[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 ↗

(On Diff #402726)

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

10082

[wsmoses]

Change order evaluating condition

[jdoerfert]

llvm/lib/Analysis/ScalarEvolution.cpp

10080

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

1118

controlling

llvm/lib/Analysis/ScalarEvolution.cpp

8475

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

10077

controlling

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

10

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

getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate Pred,
                                                 const SCEV *LHS,
                                                 const SCEV *RHS, const Loop *L,
                                                 const Instruction *CtxI,
                                                 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.
+  /// ICMP_EQ or ICMP_NE. ControllingFiniteLoop is set if this comparison
+  /// controls the exit of a loop known to have a finite number of iterations.
   bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
-                            const SCEV *&RHS, unsigned Depth = 0);
+                            const SCEV *&RHS, unsigned Depth = 0,
+                            bool ControllingFiniteLoop = false);
 
   /// 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 isFinite(L) || (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
ScalarEvolution::computeExitLimitFromICmp(const Loop *L,
   // At this point, we would like to compute how many iterations of the
   // loop the predicate will return true for these inputs.
   if (isLoopInvariant(LHS, L) && !isLoopInvariant(RHS, L)) {
     // If there is a loop-invariant, force it into the RHS.
     std::swap(LHS, RHS);
     Pred = ICmpInst::getSwappedPredicate(Pred);
   }
 
+  bool ControllingFiniteLoop =
+      ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L);
   // Simplify the operands before analyzing them.
-  (void)SimplifyICmpOperands(Pred, LHS, RHS);
+  (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0,
+                             ControllingFiniteLoop);
 
   // 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 (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
       }
 
   // If this loop must exit based on this condition (or execute undefined
   // behaviour), and we can prove the test sequence produced must repeat
   // the same values on self-wrap of the IV, then we can infer that IV
   // doesn't self wrap because if it did, we'd have an infinite (undefined)
   // loop.
-  if (ControlsExit && isLoopInvariant(RHS, L) && loopHasNoAbnormalExits(L) &&
-      loopIsFiniteByAssumption(L)) {
-
+  if (ControllingFiniteLoop && isLoopInvariant(RHS, L)) {
     // TODO: We can peel off any functions which are invertible *in L*.  Loop
     // invariant terms are effectively constants for our purposes here.
     auto *InnerLHS = LHS;
     if (auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS))
       InnerLHS = ZExt->getOperand();
     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(InnerLHS)) {
       auto *StrideC = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this));
       if (!AR->hasNoSelfWrap() && AR->getLoop() == L && AR->isAffine() && 
if (const SCEVUnknown *BU = dyn_cast<SCEVUnknown>(B))
             return true;
 
   // Otherwise assume they may have a different value.
   return false;
 }
 
 bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
                                            const SCEV *&LHS, const SCEV *&RHS,
-                                           unsigned Depth) {
+                                           unsigned Depth,
+                                           bool ControllingFiniteLoop) {
   bool Changed = false;
   // Simplifies ICMP to trivial true or false by turning it into '0 == 0' or
   // '0 != 0'.
   auto TrivialCase = [&](bool TriviallyTrue) {
     LHS = RHS = getConstant(ConstantInt::getFalse(getContext()));
     Pred = TriviallyTrue ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE;
     return true;
   };
bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred,
   if (HasSameValue(LHS, RHS)) {
     if (ICmpInst::isTrueWhenEqual(Pred))
       return TrivialCase(true);
     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.
+  // adding or subtracting 1 from one of the operands. This can be done for
+  // one of two reasons:
+  // 1) The range of the RHS does not include the (signed/unsigned) boundaries
+  // 2) The loop is finite, with this comparison controlling the exit. Since the
+  // loop is finite, the bound cannot include the corresponding boundary
+  // (otherwise it would loop forever).
   switch (Pred) {
   case ICmpInst::ICMP_SLE:
-    if (!getSignedRangeMax(RHS).isMaxSignedValue()) {
+    if (ControllingFiniteLoop || !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;
   case ICmpInst::ICMP_SGE:
-    if (!getSignedRangeMin(RHS).isMinSignedValue()) {
+    if (ControllingFiniteLoop || !getSignedRangeMin(RHS).isMinSignedValue()) {
       RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS,
                        SCEV::FlagNSW);
       Pred = ICmpInst::ICMP_SGT;
       Changed = true;
     } else if (!getSignedRangeMax(LHS).isMaxSignedValue()) {
       LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
                        SCEV::FlagNSW);
       Pred = ICmpInst::ICMP_SGT;
       Changed = true;
     }
     break;
   case ICmpInst::ICMP_ULE:
-    if (!getUnsignedRangeMax(RHS).isMaxValue()) {
+    if (ControllingFiniteLoop || !getUnsignedRangeMax(RHS).isMaxValue()) {
       RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS,
                        SCEV::FlagNUW);
       Pred = ICmpInst::ICMP_ULT;
       Changed = true;
     } else if (!getUnsignedRangeMin(LHS).isMinValue()) {
       LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS);
       Pred = ICmpInst::ICMP_ULT;
       Changed = true;
     }
     break;
   case ICmpInst::ICMP_UGE:
-    if (!getUnsignedRangeMin(RHS).isMinValue()) {
+    if (ControllingFiniteLoop || !getUnsignedRangeMin(RHS).isMinValue()) {
       RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS);
       Pred = ICmpInst::ICMP_UGT;
       Changed = true;
     } else if (!getUnsignedRangeMax(LHS).isMaxValue()) {
       LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS,
                        SCEV::FlagNUW);
       Pred = ICmpInst::ICMP_UGT;
       Changed = true;
     }
     break;
   default:
     break;
   }
 
   // TODO: More simplifications are possible here.
 
   // Recursively simplify until we either hit a recursion limit or nothing
   // changes.
   if (Changed)
-    return SimplifyICmpOperands(Pred, LHS, RHS, Depth+1);
+    return SimplifyICmpOperands(Pred, LHS, RHS, Depth + 1,
+                                ControllingFiniteLoop);
 
   return Changed;
 }
 
 bool ScalarEvolution::isKnownNegative(const SCEV *S) {
   return getSignedRangeMax(S).isNegative();
 }
 

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

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-max-iterations=0  -scalar-evolution-classify-expressions=0  2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @non_exit_use(i32 %i) #0
+
+define void @SLE(i32 %len) willreturn {
+; CHECK-LABEL: 'SLE'
+; CHECK-NEXT:  Determining loop execution counts for: @SLE
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (0 smax (1 + %len)<nsw>)
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is 2147483647
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len)<nsw>)
+; CHECK-NEXT:   Predicates:
+;
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  call void @non_exit_use(i32 %iv) nounwind willreturn
+  %inc = add i32 %iv, 1
+  %cmp = icmp sle i32 %iv, %len
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define void @SLE_infinite(i32 %len) {
+; CHECK-LABEL: 'SLE_infinite'
+; CHECK-NEXT:  Determining loop execution counts for: @SLE_infinite
+; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
+;
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  call void @non_exit_use(i32 %iv) nounwind willreturn
+  %inc = add i32 %iv, 1
+  %cmp = icmp sle i32 %iv, %len
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define void @ULE(i32 %len) willreturn {
+; CHECK-LABEL: 'ULE'
+; CHECK-NEXT:  Determining loop execution counts for: @ULE
+; CHECK-NEXT:  Loop %for.body: backedge-taken count is (1 + %len)<nuw>
+; CHECK-NEXT:  Loop %for.body: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (1 + %len)<nuw>
+; CHECK-NEXT:   Predicates:
+;
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  call void @non_exit_use(i32 %iv) nounwind willreturn
+  %inc = add i32 %iv, 1
+  %cmp = icmp ule i32 %iv, %len
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define void @ULE_infinite(i32 %len) {
+; CHECK-LABEL: 'ULE_infinite'
+; CHECK-NEXT:  Determining loop execution counts for: @ULE_infinite
+; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
+;
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]
+  call void @non_exit_use(i32 %iv) nounwind willreturn
+  %inc = add i32 %iv, 1
+  %cmp = icmp ule i32 %iv, %len
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define void @SGE(i32 %end) willreturn {
+; CHECK-LABEL: 'SGE'
+; CHECK-NEXT:  Determining loop execution counts for: @SGE
+; CHECK-NEXT: Loop %for.body: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
+; CHECK-NEXT: Loop %for.body: max backedge-taken count is -2147483548
+; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
+; CHECK-NEXT:   Predicates:
+;
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
+  call void @non_exit_use(i32 %iv) nounwind willreturn
+  %inc = add i32 %iv, -1
+  %cmp = icmp sge i32 %iv, %end
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define void @SGE_infinite(i32 %end) {
+; CHECK-LABEL: 'SGE_infinite'
+; CHECK-NEXT:  Determining loop execution counts for: @SGE_infinite
+; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
+;
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
+  call void @non_exit_use(i32 %iv) nounwind willreturn
+  %inc = add i32 %iv, -1
+  %cmp = icmp sge i32 %iv, %end
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define void @UGE(i32 %end) willreturn {
+; CHECK-LABEL: 'UGE'
+; CHECK-NEXT:  Determining loop execution counts for: @UGE
+; CHECK-NEXT: Loop %for.body: backedge-taken count is (100 + (-1 * (100 umin (-1 + %end)))<nsw>)<nsw>
+; CHECK-NEXT: Loop %for.body: max backedge-taken count is 100
+; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 umin (-1 + %end)))<nsw>)<nsw>
+; CHECK-NEXT:   Predicates:
+;
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
+  call void @non_exit_use(i32 %iv) nounwind willreturn
+  %inc = add i32 %iv, -1
+  %cmp = icmp uge i32 %iv, %end
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}
+
+define void @UGE_infinite(i32 %end) {
+; CHECK-LABEL: 'UGE_infinite'
+; CHECK-NEXT:  Determining loop execution counts for: @UGE_infinite
+; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
+;
+entry:
+  br label %for.body
+
+for.body:
+  %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
+  call void @non_exit_use(i32 %iv) nounwind willreturn
+  %inc = add i32 %iv, -1
+  %cmp = icmp uge i32 %iv, %end
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:
+  ret void
+}