[SCEV] Fix finite loop non-strict predicate simplification (PR60944)

[nikic]

Summary

There are a number of issues with the current code for converting ule -> ult (etc) predicates for comparisons controlling finite loops:

• It sets nowrap flags, which may only hold for that particular comparison, not globally. (PR60944)
• It doesn't check that the RHS is invariant. (I'm not sure this can cause practical issues independently of the previous point.)
• It runs before simplifications that may be more profitable. (PR54191)

This patch moves the handling for this into computeExitLimitFromICmp(), because it is somewhat tightly coupled with assumptions in that code, and addresses the aforementioned issues.

Fixes https://github.com/llvm/llvm-project/issues/60944.
Fixes https://github.com/llvm/llvm-project/issues/54191.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9172

Can this overflow?

[StephenFan]

llvm/lib/Analysis/ScalarEvolution.cpp

9172

Yes, it can. Although it can't overflow in loop L, it still may overflow somewhere out of the loop. See test file pr60944.ll below.
In loop2, %iv + 1 can not overflow as a result of mustprogress attribute, but %iv + 1 can still overflow in loop.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9172

I don't quite get the logic here. Imagine that the loops has two exits, one exit is iv <= MAX_INT (so it is never taken) and another exit is guaranteed to exit in 100 iterations (so the loop is finite). Then you just turn this first exit condition into iv < MIN_INT which is trivially false and immediately exit on the 1st iteration. To me it doesn't matter if the loop is finite or not, you cannot add one here.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

9172

ControllingFiniteLoop is ControlsExit && loopHasNoAbnormalExits(L) && loopIsFiniteByAssumption(L). This means that the lopo is finite *and* only has one exit.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

9172

I don't understand. Here is what ControlsExit is from the comment of computeExitLimitFromCond:

/// \p ControlsExit is true if ExitCond directly controls the exit
/// branch. In this case, we can assume that the loop exits only if the
/// condition is true and can infer that failing to meet the condition prior
/// to integer wraparound results in undefined behavior.

It doesn't mean that there is only one exit. It only means that, no matter what exit is taken, the condition is going to be true. How do you infer ability to add 1 and guarantee the new (non-equivalent) condition under the same circumstances?

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

9172

Clarified in https://github.com/llvm/llvm-project/commit/6d70812789c2583333c25ff15c5e2b166d66ce1b. See https://github.com/llvm/llvm-project/blob/6d70812789c2583333c25ff15c5e2b166d66ce1b/llvm/lib/Analysis/ScalarEvolution.cpp#L8826 for how this flag is set.

[mkazantsev]

Ok, thanks for clarification. Maybe rename this into IsOnlyExit or ControlsOnlyExit?

[efriedma]

I'm seeing a regression for the following loop:

define void @foo1(ptr %A, i32 %m, i32 %n) mustprogress {
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %inc = add i32 %i.06, 1
  %cmp.not = icmp ugt i32 %inc, %m
  br i1 %cmp.not, label %for.end, label %for.body

for.end:                                          ; preds = %for.body
  ret void
}

We used to produce a backedge-taken count of %m, but now we produce (-1 + (1 umax (1 + %m))).

[reames]

In D145510#4259519, @efriedma wrote:

We used to produce a backedge-taken count of %m, but now we produce (-1 + (1 umax (1 + %m))).

On your reduced example, it's interesting the the loop backedge is guaranteed to execute when %m is defined. This might be an over-reduction, but we might be able to do a corrected version of D148107 based on the defining scope bound of RHS being guaranteed to reach the backedge test. I'm a bit worried about both the compile time of that, and that I'm over specializing for your possible over-reduced example.

[efriedma]

The original C code is something like for (unsigned i = 0; i <= m; i++). The reduction just cut out the loop body.

At a high level, determining that the "max" is unnecessary shouldn't be hard; the only reason it's tricky is that howManyLessThans doesn't know that "m+1" doesn't overflow. If we had a dedicated howManyLessThanOrEquals, we would do the right thing without any special logic.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   std::optional<LoopInvariantPredicate>
   getLoopInvariantExitCondDuringFirstIterationsImpl(
       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. ControllingFiniteLoop is set if this comparison
-  /// controls the exit of a loop known to have a finite number of iterations.
+  /// ICMP_EQ or ICMP_NE.
   bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, const SCEV *&LHS,
-                            const SCEV *&RHS, unsigned Depth = 0,
-                            bool ControllingFiniteLoop = false);
+                            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

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, /*Depth=*/0,
-                             (EnableFiniteLoopControl ? ControllingFiniteLoop
-                                                     : false));
+  (void)SimplifyICmpOperands(Pred, LHS, RHS, /*Depth=*/0);
 
   // 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 =
if (RHS->getType()->isPointerTy()) {
       RHS = getLosslessPtrToIntExpr(RHS);
       if (isa<SCEVCouldNotCompute>(RHS))
         return RHS;
     }
     ExitLimit EL = howFarToNonZero(getMinusSCEV(LHS, RHS), L);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
+  case ICmpInst::ICMP_SLE:
+  case ICmpInst::ICMP_ULE:
+    // Since the loop is finite, an invariant RHS cannot include the boundary
+    // value, otherwise it would loop forever.
+    if (!EnableFiniteLoopControl || !ControllingFiniteLoop ||
+        !isLoopInvariant(RHS, L))
+      break;
+    RHS = getAddExpr(getOne(RHS->getType()), RHS);
+    [[fallthrough]];
   case ICmpInst::ICMP_SLT:
   case ICmpInst::ICMP_ULT: {                    // while (X < Y)
-    bool IsSigned = Pred == ICmpInst::ICMP_SLT;
+    bool IsSigned = ICmpInst::isSigned(Pred);
     ExitLimit EL = howManyLessThans(LHS, RHS, L, IsSigned, ControlsExit,
                                     AllowPredicates);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
+  case ICmpInst::ICMP_SGE:
+  case ICmpInst::ICMP_UGE:
+    // Since the loop is finite, an invariant RHS cannot include the boundary
+    // value, otherwise it would loop forever.
+    if (!EnableFiniteLoopControl || !ControllingFiniteLoop ||
+        !isLoopInvariant(RHS, L))
+      break;
+    RHS = getAddExpr(getMinusOne(RHS->getType()), RHS);
+    [[fallthrough]];
   case ICmpInst::ICMP_SGT:
   case ICmpInst::ICMP_UGT: {                    // while (X > Y)
-    bool IsSigned = Pred == ICmpInst::ICMP_SGT;
+    bool IsSigned = ICmpInst::isSigned(Pred);
     ExitLimit EL =
         howManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit,
                             AllowPredicates);
     if (EL.hasAnyInfo()) return EL;
     break;
   }
   default:
     break;
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,
-                                           bool ControllingFiniteLoop) {
+                                           unsigned Depth) {
   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. 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).
+  // adding or subtracting 1 from one of the operands.
   switch (Pred) {
   case ICmpInst::ICMP_SLE:
-    if (ControllingFiniteLoop || !getSignedRangeMax(RHS).isMaxSignedValue()) {
+    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;
   case ICmpInst::ICMP_SGE:
-    if (ControllingFiniteLoop || !getSignedRangeMin(RHS).isMinSignedValue()) {
+    if (!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 (ControllingFiniteLoop || !getUnsignedRangeMax(RHS).isMaxValue()) {
+    if (!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 (ControllingFiniteLoop || !getUnsignedRangeMin(RHS).isMinValue()) {
+    if (!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,
-                                ControllingFiniteLoop);
+    return SimplifyICmpOperands(Pred, LHS, RHS, Depth + 1);
 
   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: backedge-taken count is (0 smax (1 + %len))
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is 2147483647
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (0 smax (1 + %len)<nsw>)
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len)<nsw>)
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (0 smax (1 + %len))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (0 smax (1 + %len))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]

 
 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: backedge-taken count is (1 + %len)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -1
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (1 + %len)<nuw>
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (1 + %len)<nuw>
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (1 + %len)
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (1 + %len)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 0, %entry ]

 
 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: backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2147483548
-; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
-; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end)<nsw>)))
+; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (100 + (-1 * (100 smin (-1 + %end))))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %for.body: Trip multiple is 1
 ;
 entry:
   br label %for.body
 
 for.body:
   %iv = phi i32 [ %inc, %for.body ], [ 100, %entry ]
for.body:
   %inc = add i32 %iv, -1
   %cmp = icmp uge i32 %iv, %end
   br i1 %cmp, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 
-; FIXME: It would be better to compute ((-2 + %n) /u 2) as trip count here.
 define void @pr54191(i64 %n) mustprogress {
 ; CHECK-LABEL: 'pr54191'
 ; CHECK-NEXT:  Determining loop execution counts for: @pr54191
-; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-3 + (4 smax (1 + %n)<nsw>))<nsw> /u 2)
-; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4611686018427387901
-; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-3 + (4 smax (1 + %n)<nsw>))<nsw> /u 2)
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-3 + (4 smax (1 + %n)<nsw>))<nsw> /u 2)
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-2 + %n) /u 2)
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4611686018427387902
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-2 + %n) /u 2)
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-2 + %n) /u 2)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 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
 }

llvm/test/Transforms/IndVarSimplify/pr60944.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt -S -passes=indvars < %s | FileCheck %s
 
 @x = global i32 0
 
-; FIXME: This is a miscompile.
 ; %loop2 is never entered and we cannot derive any fact about %iv from it.
 define i32 @main(i32 %iv.start, i32 %arg2) mustprogress {
 ; CHECK-LABEL: define i32 @main
 ; CHECK-SAME: (i32 [[IV_START:%.*]], i32 [[ARG2:%.*]]) #[[ATTR0:[0-9]+]] {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ [[IV_START]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    br i1 false, label [[LOOP2_PREHEADER:%.*]], label [[LOOP_LATCH]]
 ; CHECK:       loop2.preheader:
 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 ; CHECK:       loop2:
 ; CHECK-NEXT:    br i1 true, label [[LOOP2_EXIT:%.*]], label [[LOOP2]]
 ; CHECK:       loop2.exit:
 ; CHECK-NEXT:    br label [[LOOP_LATCH]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    [[IV_NEXT]] = sdiv i32 [[ARG2]], [[IV]]
-; CHECK-NEXT:    br i1 false, label [[LOOP_EXIT:%.*]], label [[LOOP]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[IV]], -1
+; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP_EXIT:%.*]], label [[LOOP]]
 ; CHECK:       loop.exit:
 ; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[LOOP_LATCH]] ]
 ; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
 ;
 entry:
   br label %loop
 
 loop:

llvm/test/Transforms/IndVarSimplify/range-iter-threshold.ll

-; RUN: opt -passes=indvars -S %s | FileCheck --check-prefix=COMMON --check-prefix=DEFAULT %s
-; RUN: opt -passes=indvars -scev-range-iter-threshold=1 -S %s | FileCheck --check-prefix=COMMON --check-prefix=LIMIT %s
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -passes=indvars -S %s | FileCheck --check-prefix=COMMON %s
+; RUN: opt -passes=indvars -scev-range-iter-threshold=1 -S %s | FileCheck --check-prefix=COMMON %s
 
 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 define i32 @test(i1 %c.0, i32 %m) {
-; COMMON-LABEL: @test(
+; COMMON-LABEL: define i32 @test
+; COMMON-SAME: (i1 [[C_0:%.*]], i32 [[M:%.*]]) {
 ; COMMON-NEXT:  entry:
 ; COMMON-NEXT:    br label [[OUTER_HEADER:%.*]]
 ; COMMON:       outer.header:
-; COMMON-NEXT:    [[INDVARS_IV1:%.*]] = phi i64 [ [[INDVARS_IV_NEXT2:%.*]], [[OUTER_LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
-; DEFAULT-NEXT:    [[INDVARS_IV:%.*]] = phi i32 [ [[INDVARS_IV_NEXT:%.*]], [[OUTER_LATCH]] ], [ 2, [[ENTRY]] ]
-; COMMON-NEXT:    [[IV_1:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[IV_1_NEXT:%.*]], [[OUTER_LATCH]] ]
+; COMMON-NEXT:    [[IV_1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_1_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
 ; COMMON-NEXT:    [[MAX_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[MAX_1:%.*]], [[OUTER_LATCH]] ]
+; COMMON-NEXT:    [[TMP0:%.*]] = sext i32 [[IV_1]] to i64
 ; COMMON-NEXT:    br label [[INNER_1:%.*]]
 ; COMMON:       inner.1:
-; COMMON-NEXT:    [[C_1:%.*]] = icmp ult i64 0, [[INDVARS_IV1]]
+; COMMON-NEXT:    [[C_1:%.*]] = icmp slt i64 0, [[TMP0]]
 ; COMMON-NEXT:    br i1 [[C_1]], label [[INNER_1]], label [[INNER_2_HEADER_PREHEADER:%.*]]
 ; COMMON:       inner.2.header.preheader:
 ; COMMON-NEXT:    br label [[INNER_2_HEADER:%.*]]
 ; COMMON:       inner.2.header:
 ; COMMON-NEXT:    [[IV_3:%.*]] = phi i32 [ [[IV_3_NEXT:%.*]], [[INNER_2_LATCH:%.*]] ], [ 0, [[INNER_2_HEADER_PREHEADER]] ]
-; COMMON-NEXT:    br i1 [[C_0:%.*]], label [[OUTER_LATCH]], label [[INNER_2_LATCH]]
+; COMMON-NEXT:    br i1 [[C_0]], label [[OUTER_LATCH]], label [[INNER_2_LATCH]]
 ; COMMON:       inner.2.latch:
 ; COMMON-NEXT:    [[IV_3_NEXT]] = add i32 [[IV_3]], 1
-; DEFAULT-NEXT:   [[EXITCOND:%.*]] = icmp eq i32 [[IV_3_NEXT]], [[INDVARS_IV]]
-; LIMIT-NEXT:     [[EXITCOND:%.*]] = icmp ugt i32 [[IV_3]], [[IV_1]]
-; COMMON-NEXT:    br i1 [[EXITCOND]], label [[OUTER_LATCH]], label [[INNER_2_HEADER]]
+; COMMON-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[IV_3]], [[IV_1]]
+; COMMON-NEXT:    br i1 [[C_2]], label [[OUTER_LATCH]], label [[INNER_2_HEADER]]
 ; COMMON:       outer.latch:
-; COMMON-NEXT:    [[MAX_1]] = phi i32 [ [[M:%.*]], [[INNER_2_LATCH]] ], [ 0, [[INNER_2_HEADER]] ]
-; COMMON-NEXT:    [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], 1
-; COMMON-NEXT:    [[IV_1_NEXT]] = add nuw i32 [[IV_1]], 1
+; COMMON-NEXT:    [[MAX_1]] = phi i32 [ [[M]], [[INNER_2_LATCH]] ], [ 0, [[INNER_2_HEADER]] ]
+; COMMON-NEXT:    [[IV_1_NEXT]] = add i32 [[IV_1]], 1
 ; COMMON-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[IV_1]], [[MAX_0]]
-; DEFAULT-NEXT:   [[INDVARS_IV_NEXT]] = add i32 [[INDVARS_IV]], 1
 ; COMMON-NEXT:    br i1 [[C_3]], label [[EXIT:%.*]], label [[OUTER_HEADER]], !llvm.loop [[LOOP0:![0-9]+]]
 ; COMMON:       exit:
 ; COMMON-NEXT:    ret i32 0
 ;
 entry:
   br label %outer.header
 
 outer.header:

llvm/test/Transforms/IndVarSimplify/rewrite-loop-exit-value.ll

 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[INC8:%.*]] = phi i16 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[INC8]], 1
 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i16 [[INC8]], [[M:%.*]]
 ; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i16 [[MUL]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[CRIT_EDGE:%.*]], label [[FOR_BODY]]
 ; CHECK:       crit_edge:
-; CHECK-NEXT:    [[TMP0:%.*]] = call i16 @llvm.smax.i16(i16 [[END]], i16 -1)
-; CHECK-NEXT:    [[SMAX:%.*]] = add nsw i16 [[TMP0]], 1
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i16 [[SMAX]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = add i16 [[END]], 1
+; CHECK-NEXT:    [[SMAX:%.*]] = call i16 @llvm.smax.i16(i16 [[TMP0]], i16 0)
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i16 [[END]], 32767
 ; CHECK-NEXT:    [[UMIN:%.*]] = zext i1 [[TMP1]] to i16
 ; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i16 [[SMAX]], [[UMIN]]
 ; CHECK-NEXT:    [[UMAX:%.*]] = call i16 @llvm.umax.i16(i16 [[M]], i16 1)
 ; CHECK-NEXT:    [[TMP3:%.*]] = udiv i16 [[TMP2]], [[UMAX]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = add i16 [[TMP3]], [[UMIN]]
 ; CHECK-NEXT:    ret i16 [[TMP4]]
 ;
 entry: