[IRCE] Change min value safety check

[samparker]

Summary

CanBeMin is currently used which will report true for any unknown values, but often a check is performed outside the loop which covers this situation:

for (int i = 0; i < N; ++i)
  ...

if (N > 0)
  for (int i = 0; i < N; ++i)
    ...

So I've add 'LoopGuardedAgainstMin' which reports whether the loop is guarded by a greater than the minimum check, which then allows loop with a variable count to be optimised. And also enable SGT to be converted to UGT, which has lead me to change one of the tests. Another one of the existing tests has been changed because I believe that the range metadata was preventing the test from performing as desired.

[samparker]

Added forgotten test.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

311

Please submit it as a separate patch.

705

Can we now remove this function and replace its usages with LoopGuardedAgainstMin? I don't mind if it goes as a follow-up change.

713

I would suggest calling it CannotBeMinInLoop and reorder args like S, L, Signed, SE.

878

Please submit it as a separate change.

908

Why do you need non-negativity here? In unsigned, "negative" only means that the first bit is 1 and the value is still seen as big positive.

951

Please submit it as a separate patch.

991

Do you plan to do the same for max value? I'm OK if it will be done in a separate patch.

1787

Please submit it as a separate patch.

1813

Same.

1847

Same.

test/Transforms/IRCE/eq_ne.ll

147

What is the reason of this change? If it demonstrates something new you can just create a new test identical to this one but without the range.

[fhahn]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

713

Maybe there's a more descriptive name for S, e.g. BoundSCEV or something.

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

705

I will have a look at the other uses.

908

Ah, guess I was trying to be overly cautious, FlagNUW will do.

991

Yes, I can do that.

test/Transforms/IRCE/eq_ne.ll

147

From the description, the existing test didn't seem like it was testing what it should have been. Given the range values, IRCE should be able to be performed and with this patch it does. So I wanted to change the test to match up with the description with IRCE being prevented.

[samparker]

Thanks for the comments, I've made these changes:

• CanBeMin has now been replaced with CannotBeMinInLoop.
• The function arguments have been renamed and reordered.
• KnownNonNegative check removed.
• debug comments removed.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

940

This doesn't look correct. RightSCEV + Step - 1 = Max means that RightSCEV + Step exceeds Max. We should bail with SLT/UGT as well. Please correct me if I'm wrong.

And in any case, if you still think it should be done, it should go as a separate patch.

1474

{ } not needed here (yes, I hate this code style rule, too :)).

1502

Same.

1804

What was the reason of that?

test/Transforms/IRCE/eq_ne.ll

147

I would still prefer to not touch old tests for sake of this. Please create a new one, it doesn't hurt anyone and will help us to make sure that everything works OK if the range is there.

test/Transforms/IRCE/variable-loop-bounds.ll

14

Could you please rename it to %iv for better readability?

[samparker]

I've replaced SumCanReachMax with SumCannotBeMaxInLoop, which uses similar logic to the new CannotBeMinInLoop, querying SCEV's LoopBackedgeGuardedBy. These two updated checks are need together to get this to work. Other changes:

• Removed whitespace.
• re-inserted the range metadata into test.
• bracket style changes

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

690

You are making this function for SCEVs regardless of their semantics, please rename BoundSCEV and StepMinusOne into something more general.

697

This is incorrect. You need to prove that BoundSCEV < Limit, so you should use SLT/ULT predicates, not SGT/ULT.

698

It is also potentially incorrect. You need to check this condition not on loop backedge but on loop entry. Otherwise it can be in theory wrong on 1st iteration. It is checked with isLoopEntryGuardedByCond.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

697

SLT/ULT predicates, not SGT/UGT**

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

697

We do, but as far as I can tell, this is called from where the exit successor is the 'true' successor, whereas we want to confirm the condition of the header being the 'true' successor.

For example, SumCannotBeMax could produce:
ICMP_UGT {-1, + %N}, -1

The original predicate would have been EQ and SCEV will inverse and simplify the predicate to target the header into:
ICMP_NE {1, +1}, %N

Which gets further simplified into:
ICMP_ULT {0, +1}, (-1 + %N)

Which is what you're suggesting. I find the logic in the parseLoopStructure hard to follow, so please tell me if I'm missing something here.

698

I think this is already handled on line 943.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

697

My point is that you are making a separate static function which can later be moved to some Utils file. It must not rely something that is true in that particular place where it is invoked now.

What I can read from this function's name is that it is a function that takes two SCEVs and returns true if it proves that sum of these two SCEVs does not reach signed/unsigned max. And this is not in agreement with what is happening inside. If that is *not* what this function is supposed to do, then maybe it needs a better name.

698

Likewise, if you rely on something from outside your function then you should add an assert on it. If this function goes to utils and someone reuses it, it can be not obvious for them.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

698

And clearly, I don't see why you should check guard on backedge and not on entry. Any arguments in favour of that?

[samparker]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

697

Okay, I see your point. I will have a go at extracting some functionality from parseLoopStructure and into a combined helper function that could be used in a standalone fashion.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

697

Fine for me!

[samparker]

Thanks Max, I've now:

• corrected the loop guard logic, including using the entry instead of backedge guard.
• extracted the bound checking into one function, merging the Max check into it.

[samparker]

Slight format change and added AvailableAtLoopEntry check in CannotBeMinInLoop.

[mkazantsev]

Code looks fine with minor nits inlined. Please add more tests, I want to be adamant that it also works for other latch predicates.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

688–689

I think I got what this function does, but do you mind adding an explanatory comment since it is not completely trivial?

690

Please rename S1 to something more sound, it is unclear how it is connected to Start and Step. I propose Bound or something of this nature.

708–709

Assert that LatchBrExitIdx == 0 at this point.

713

Please clang-format this.

716

Availabllity of S1 can be checked in very beginning since you check it for both LatchBrExitIdx == 0 and 1. I also think that this can actually be an assert, but not sure about the latter.

739

This maybe also can be an assert, but not 100% sure about it. It's up to you.

test/Transforms/IRCE/variable-loop-bounds.ll

38

Do you mind adding similar tests with equivalent exit conditions defined by different predicates? (i.e. ne, slt, ult etc)

[samparker]

Hi Max,

I've left the AvailableAtLoopEntry as conditionals and not asserts, as it seems safer at the moment. Things done:

• added more tests
• renamed the argument
• added an assert for LatchBrExit == 0
• exit early, only checking once, that AvailableAtLoopEntry is true
• added debug messages into the new function

[mkazantsev]

LGTM with nit inlined.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

704

This is usually done as DEBUG(dbgs() << "irce: Start: " << *Start << '\n');

[mkazantsev]

test/Transforms/IRCE/eq_ne.ll

140

Please add checks for positive test just like in test_03. Also do the same for your new tests.

[samparker]

Thanks for the review and your help. I'll make the changes and commit at the start of next week. I'll also prepare the patch for the decreasing case.

[samparker]

Committed in https://reviews.llvm.org/rL328480

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

 
 static bool CanBeMax(ScalarEvolution &SE, const SCEV *S, bool Signed) {
   APInt Max = Signed ?
       APInt::getSignedMaxValue(cast<IntegerType>(S->getType())->getBitWidth()) :
       APInt::getMaxValue(cast<IntegerType>(S->getType())->getBitWidth());
   return SE.getSignedRange(S).contains(Max) &&
          SE.getUnsignedRange(S).contains(Max);
 }
 
-static bool SumCanReachMax(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
-                           bool Signed) {
-  // S1 < INT_MAX - S2 ===> S1 + S2 < INT_MAX.
-  assert(SE.isKnownNonNegative(S2) &&
-         "We expected the 2nd arg to be non-negative!");
-  const SCEV *Max = SE.getConstant(
-      Signed ? APInt::getSignedMaxValue(
-                   cast<IntegerType>(S1->getType())->getBitWidth())
-             : APInt::getMaxValue(
-                   cast<IntegerType>(S1->getType())->getBitWidth()));
-  const SCEV *CapForS1 = SE.getMinusSCEV(Max, S2);
-  return !SE.isKnownPredicate(Signed ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
-                              S1, CapForS1);
+/// Given a loop with an increasing induction variable, is it possible to
+/// safely calculate the bounds of a new loop using the given Predicate.
+static bool isSafeIncreasingBound(const SCEV *Start,
+                                  const SCEV *BoundSCEV, const SCEV *Step,
+                                  ICmpInst::Predicate Pred,
+                                  unsigned LatchBrExitIdx,
+                                  Loop *L, ScalarEvolution &SE) {
+  if (Pred != ICmpInst::ICMP_SLT && Pred != ICmpInst::ICMP_SGT &&
+      Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_UGT)
+    return false;
+
+  if (!SE.isAvailableAtLoopEntry(BoundSCEV, L))
+    return false;
+
+  DEBUG(dbgs() << "irce: isSafeIncreasingBound with:\n");
+  DEBUG(dbgs() << "irce: Start: "; Start->dump());
+  DEBUG(dbgs() << "irce: Step: "; Step->dump());
+  DEBUG(dbgs() << "irce: BoundSCEV: "; BoundSCEV->dump());
+  DEBUG(dbgs() << "irce: Pred: " << ICmpInst::getPredicateName(Pred) << "\n");
+  DEBUG(dbgs() << "irce: LatchExitBrIdx: " << LatchBrExitIdx << "\n");
+
+  bool IsSigned = ICmpInst::isSigned(Pred);
+  // The predicate that we need to check that the induction variable lies
+  // within bounds.
+  ICmpInst::Predicate BoundPred =
+      IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
+
+  if (LatchBrExitIdx == 1)
+    return SE.isLoopEntryGuardedByCond(L, BoundPred, Start, BoundSCEV);
+
+  assert(LatchBrExitIdx == 0 && "LatchBrExitIdx should be 0 or 1");
+
+  const SCEV *StepMinusOne =
+    SE.getMinusSCEV(Step, SE.getOne(Step->getType()));
+  unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
+  APInt Max = IsSigned ? APInt::getSignedMaxValue(BitWidth) : 
+    APInt::getMaxValue(BitWidth);
+  const SCEV *Limit = SE.getMinusSCEV(SE.getConstant(Max), StepMinusOne);
+
+  return (SE.isLoopEntryGuardedByCond(L, BoundPred, Start,
+                                      SE.getAddExpr(BoundSCEV, Step)) &&
+          SE.isLoopEntryGuardedByCond(L, BoundPred, BoundSCEV, Limit));
 }
 
-static bool CanBeMin(ScalarEvolution &SE, const SCEV *S, bool Signed) {
-  APInt Min = Signed ?
-      APInt::getSignedMinValue(cast<IntegerType>(S->getType())->getBitWidth()) :
-      APInt::getMinValue(cast<IntegerType>(S->getType())->getBitWidth());
-  return SE.getSignedRange(S).contains(Min) &&
-         SE.getUnsignedRange(S).contains(Min);
+static bool CannotBeMinInLoop(const SCEV *BoundSCEV, Loop *L,
+                              ScalarEvolution &SE, bool Signed) {
+  unsigned BitWidth = cast<IntegerType>(BoundSCEV->getType())->getBitWidth();
+  APInt Min = Signed ? APInt::getSignedMinValue(BitWidth) : 
+    APInt::getMinValue(BitWidth);
+  auto Predicate = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
+  return SE.isAvailableAtLoopEntry(BoundSCEV, L) &&
+         SE.isLoopEntryGuardedByCond(L, Predicate, BoundSCEV,
+                                     SE.getConstant(Min));
 }
 
 static bool SumCanReachMin(ScalarEvolution &SE, const SCEV *S1, const SCEV *S2,
                            bool Signed) {
   // S1 > INT_MIN - S2 ===> S1 + S2 > INT_MIN.
   assert(SE.isKnownNonPositive(S2) &&
          "We expected the 2nd arg to be non-positive!");
   const SCEV *Max = SE.getConstant(

 
     // Currently we only work with induction variables that have been proved to
     // not wrap.  This restriction can potentially be lifted in the future.
 
     if (!HasNoSignedWrap(AR))
       return false;
 
     if (const SCEVConstant *StepExpr =
             dyn_cast<SCEVConstant>(AR->getStepRecurrence(SE))) {
       StepCI = StepExpr->getValue();
       assert(!StepCI->isZero() && "Zero step?");
       IsIncreasing = !StepCI->isNegative();
       return true;
     }
 
     return false;
   };

   const SCEV *StartNext = IndVarBase->getStart();
   const SCEV *Addend = SE.getNegativeSCEV(IndVarBase->getStepRecurrence(SE));
   const SCEV *IndVarStart = SE.getAddExpr(StartNext, Addend);
   const SCEV *Step = SE.getSCEV(StepCI);
 
   ConstantInt *One = ConstantInt::get(IndVarTy, 1);
   if (IsIncreasing) {
     bool DecreasedRightValueByOne = false;
     if (StepCI->isOne()) {
       // Try to turn eq/ne predicates to those we can work with.
       if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
         // while (++i != len) {         while (++i < len) {
         //   ...                 --->     ...
         // }                            }
         // If both parts are known non-negative, it is profitable to use
         // unsigned comparison in increasing loop. This allows us to make the
         // comparison check against "RightSCEV + 1" more optimistic.
         if (SE.isKnownNonNegative(IndVarStart) &&
             SE.isKnownNonNegative(RightSCEV))
           Pred = ICmpInst::ICMP_ULT;
         else
           Pred = ICmpInst::ICMP_SLT;
-      else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
-               !CanBeMin(SE, RightSCEV, /* IsSignedPredicate */ true)) {
+      else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0) {
         // while (true) {               while (true) {
         //   if (++i == len)     --->     if (++i > len - 1)
         //     break;                       break;
         //   ...                          ...
         // }                            }
-        // TODO: Insert ICMP_UGT if both are non-negative?
-        Pred = ICmpInst::ICMP_SGT;
-        RightSCEV = SE.getMinusSCEV(RightSCEV, SE.getOne(RightSCEV->getType()));
-        DecreasedRightValueByOne = true;
+        if (IndVarBase->getNoWrapFlags(SCEV::FlagNUW) &&
+            CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/false)) {
+          Pred = ICmpInst::ICMP_UGT;
+          RightSCEV = SE.getMinusSCEV(RightSCEV,
+                                      SE.getOne(RightSCEV->getType()));
+          DecreasedRightValueByOne = true;
+        } else if (CannotBeMinInLoop(RightSCEV, &L, SE, /*Signed*/true)) {
+          Pred = ICmpInst::ICMP_SGT;
+          RightSCEV = SE.getMinusSCEV(RightSCEV,
+                                      SE.getOne(RightSCEV->getType()));
+          DecreasedRightValueByOne = true;
+        }
       }
     }
 
     bool LTPred = (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_ULT);
     bool GTPred = (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_UGT);
     bool FoundExpectedPred =
         (LTPred && LatchBrExitIdx == 1) || (GTPred && LatchBrExitIdx == 0);
 
     if (!FoundExpectedPred) {
       FailureReason = "expected icmp slt semantically, found something else";
       return None;
     }
 
-    IsSignedPredicate =
-        Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SGT;
-
+    IsSignedPredicate = ICmpInst::isSigned(Pred);
     if (!IsSignedPredicate && !AllowUnsignedLatchCondition) {
       FailureReason = "unsigned latch conditions are explicitly prohibited";
       return None;
     }
 
-    // The predicate that we need to check that the induction variable lies
-    // within bounds.
-    ICmpInst::Predicate BoundPred =
-        IsSignedPredicate ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
-
+    if (!isSafeIncreasingBound(IndVarStart, RightSCEV, Step, Pred,
+                               LatchBrExitIdx, &L, SE)) {
+      FailureReason = "Unsafe loop bounds";
+      return None;
+    }
     if (LatchBrExitIdx == 0) {
-      const SCEV *StepMinusOne = SE.getMinusSCEV(Step,
-                                                 SE.getOne(Step->getType()));
-      if (SumCanReachMax(SE, RightSCEV, StepMinusOne, IsSignedPredicate)) {
-        // TODO: this restriction is easily removable -- we just have to
-        // remember that the icmp was an slt and not an sle.
-        FailureReason = "limit may overflow when coercing le to lt";
-        return None;
-      }
-
-      if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
-          !SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart,
-                                       SE.getAddExpr(RightSCEV, Step))) {
-        FailureReason = "Induction variable start not bounded by upper limit";
-        return None;
-      }
-
       // We need to increase the right value unless we have already decreased
       // it virtually when we replaced EQ with SGT.
       if (!DecreasedRightValueByOne) {
         IRBuilder<> B(Preheader->getTerminator());
         RightValue = B.CreateAdd(RightValue, One);
       }
     } else {
-      if (!SE.isAvailableAtLoopEntry(RightSCEV, &L) ||
-          !SE.isLoopEntryGuardedByCond(&L, BoundPred, IndVarStart, RightSCEV)) {
-        FailureReason = "Induction variable start not bounded by upper limit";
-        return None;
-      }
       assert(!DecreasedRightValueByOne &&
              "Right value can be decreased only for LatchBrExitIdx == 0!");
     }
   } else {
     bool IncreasedRightValueByOne = false;
     if (StepCI->isMinusOne()) {
       // Try to turn eq/ne predicates to those we can work with.
       if (Pred == ICmpInst::ICMP_NE && LatchBrExitIdx == 1)
         // while (--i != len) {         while (--i > len) {
         //   ...                 --->     ...
         // }                            }
         // We intentionally don't turn the predicate into UGT even if we know
         // that both operands are non-negative, because it will only pessimize
         // our check against "RightSCEV - 1".
         Pred = ICmpInst::ICMP_SGT;
       else if (Pred == ICmpInst::ICMP_EQ && LatchBrExitIdx == 0 &&
                !CanBeMax(SE, RightSCEV, /* IsSignedPredicate */ true)) {
         // while (true) {               while (true) {
         //   if (--i == len)     --->     if (--i < len + 1)
         //     break;                       break;
         //   ...                          ...
         // }                            }
         // TODO: Insert ICMP_ULT if both are non-negative?
         Pred = ICmpInst::ICMP_SLT;
         RightSCEV = SE.getAddExpr(RightSCEV, SE.getOne(RightSCEV->getType()));
         IncreasedRightValueByOne = true;
       }
     }

   bool NeedsPostLoop =
       Increasing ? SR.HighLimit.hasValue() : SR.LowLimit.hasValue();
 
   Value *ExitPreLoopAt = nullptr;
   Value *ExitMainLoopAt = nullptr;
   const SCEVConstant *MinusOneS =
       cast<SCEVConstant>(SE.getConstant(IVTy, -1, true /* isSigned */));
 
   if (NeedsPreLoop) {
     const SCEV *ExitPreLoopAtSCEV = nullptr;
 
     if (Increasing)
       ExitPreLoopAtSCEV = *SR.LowLimit;
     else {
-      if (CanBeMin(SE, *SR.HighLimit, IsSignedPredicate)) {
+      if (CannotBeMinInLoop(*SR.HighLimit, &OriginalLoop, SE,
+                            IsSignedPredicate))
+        ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
+      else {
         DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
                      << "preloop exit limit.  HighLimit = " << *(*SR.HighLimit)
                      << "\n");
         return false;
       }
-      ExitPreLoopAtSCEV = SE.getAddExpr(*SR.HighLimit, MinusOneS);
     }
 
     if (!isSafeToExpandAt(ExitPreLoopAtSCEV, InsertPt, SE)) {
       DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
                    << " preloop exit limit " << *ExitPreLoopAtSCEV
                    << " at block " << InsertPt->getParent()->getName() << "\n");
       return false;
     }
 
     ExitPreLoopAt = Expander.expandCodeFor(ExitPreLoopAtSCEV, IVTy, InsertPt);
     ExitPreLoopAt->setName("exit.preloop.at");
   }
 
   if (NeedsPostLoop) {
     const SCEV *ExitMainLoopAtSCEV = nullptr;
 
     if (Increasing)
       ExitMainLoopAtSCEV = *SR.HighLimit;
     else {
-      if (CanBeMin(SE, *SR.LowLimit, IsSignedPredicate)) {
+      if (CannotBeMinInLoop(*SR.LowLimit, &OriginalLoop, SE,
+                            IsSignedPredicate))
+        ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
+      else {
         DEBUG(dbgs() << "irce: could not prove no-overflow when computing "
                      << "mainloop exit limit.  LowLimit = " << *(*SR.LowLimit)
                      << "\n");
         return false;
       }
-      ExitMainLoopAtSCEV = SE.getAddExpr(*SR.LowLimit, MinusOneS);
     }
 
     if (!isSafeToExpandAt(ExitMainLoopAtSCEV, InsertPt, SE)) {
       DEBUG(dbgs() << "irce: could not prove that it is safe to expand the"
                    << " main loop exit limit " << *ExitMainLoopAtSCEV
                    << " at block " << InsertPt->getParent()->getName() << "\n");
       return false;
     }

   return true;
 }
 
 /// Computes and returns a range of values for the induction variable (IndVar)
 /// in which the range check can be safely elided.  If it cannot compute such a
 /// range, returns None.
 Optional<InductiveRangeCheck::Range>
 InductiveRangeCheck::computeSafeIterationSpace(
     ScalarEvolution &SE, const SCEVAddRecExpr *IndVar,

test/Transforms/IRCE/eq_ne.ll

 ; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
 
 ; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_01u: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
-; CHECK-NOT: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
+; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK: irce: in function test_07: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 ; CHECK-NOT: irce: in function test_08: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting>
 
 ; Show that IRCE can turn 'ne' condition to 'slt' in increasing IV when the IV
 ; can be negative at some point.
 define void @test_01(i32* %arr, i32* %a_len_ptr) #0 {

 }
 
 ; Show that IRCE can turn 'eq' condition to 'sge' in increasing IV.
 define void @test_03(i32* %arr, i32* %a_len_ptr) #0 {
 
 ; CHECK: test_03(
 ; CHECK:        main.exit.selector:
 ; CHECK-NEXT:     [[PSEUDO_PHI:%[^ ]+]] = phi i32 [ %idx.next, %in.bounds ]
-; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp slt i32 [[PSEUDO_PHI]], 100
+; CHECK-NEXT:     [[COND:%[^ ]+]] = icmp ult i32 [[PSEUDO_PHI]], 100
 ; CHECK-NEXT:     br i1 [[COND]]
 
 entry:
   %len = load i32, i32* %a_len_ptr, !range !0
   br label %loop
 
 loop:
   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]

 
 out.of.bounds:
   ret void
 
 exit:
   ret void
 }
 
-; Show that if n is not known to be greater than the starting value, IRCE
-; doesn't apply.
 define void @test_04(i32* %arr, i32* %a_len_ptr) #0 {
 
-; CHECK: test_04(
-
 entry:
   %len = load i32, i32* %a_len_ptr, !range !0
   br label %loop
 
 loop:
   %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ]
   %idx.next = add i32 %idx, 1
   %abc = icmp slt i32 %idx, %len
   br i1 %abc, label %in.bounds, label %out.of.bounds
 

test/Transforms/IRCE/variable-loop-bounds.ll

+; RUN: opt -irce -S -verify-loop-info -irce-print-changed-loops -irce-skip-profitability-checks < %s 2>&1 | FileCheck %s
+
+; CHECK: irce: in function test_inc_eq: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
+define void @test_inc_eq(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
+entry:
+  %cmp16 = icmp sgt i32 %N, 0
+  br i1 %cmp16, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ]
+  %cmp1 = icmp ult i32 %i.017, 512
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017
+  %1 = load i32, i32* %arrayidx2, align 4
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %sub = sub i32 %0, %1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %sub, %2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+if.else:
+  %add6 = add nsw i32 %1, %0
+  %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  store i32 %add6, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i32 %i.017, 1
+  %exitcond = icmp eq i32 %inc, %N
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK: irce: in function test_inc_ne: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
+define void @test_inc_ne(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
+entry:
+  %cmp16 = icmp sgt i32 %N, 0
+  br i1 %cmp16, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ]
+  %cmp1 = icmp ult i32 %i.017, 512
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017
+  %1 = load i32, i32* %arrayidx2, align 4
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %sub = sub i32 %0, %1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %sub, %2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+if.else:
+  %add6 = add nsw i32 %1, %0
+  %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  store i32 %add6, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i32 %i.017, 1
+  %exitcond = icmp ne i32 %inc, %N
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}
+
+; CHECK: irce: in function test_inc_slt: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
+define void @test_inc_slt(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
+entry:
+  %cmp16 = icmp sgt i32 %N, 0
+  br i1 %cmp16, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ]
+  %cmp1 = icmp ult i32 %i.017, 512
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017
+  %1 = load i32, i32* %arrayidx2, align 4
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %sub = sub i32 %0, %1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %sub, %2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+if.else:
+  %add6 = add nsw i32 %1, %0
+  %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  store i32 %add6, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i32 %i.017, 1
+  %exitcond = icmp slt i32 %inc, %N
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}
+
+; CHECK: irce: in function test_inc_ult: constrained Loop at depth 1 containing: %for.body<header>,%if.else,%if.then,%for.inc<latch><exiting>
+define void @test_inc_ult(i32* nocapture %a, i32* nocapture readonly %b, i32* nocapture readonly %c, i32 %N) {
+entry:
+  %cmp16 = icmp ugt i32 %N, 0
+  br i1 %cmp16, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:
+  ret void
+
+for.body:
+  %i.017 = phi i32 [ %inc, %for.inc ], [ 0, %entry ]
+  %cmp1 = icmp ult i32 %i.017, 512
+  %arrayidx = getelementptr inbounds i32, i32* %b, i32 %i.017
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx2 = getelementptr inbounds i32, i32* %c, i32 %i.017
+  %1 = load i32, i32* %arrayidx2, align 4
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:
+  %sub = sub i32 %0, %1
+  %arrayidx3 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  %2 = load i32, i32* %arrayidx3, align 4
+  %add = add nsw i32 %sub, %2
+  store i32 %add, i32* %arrayidx3, align 4
+  br label %for.inc
+
+if.else:
+  %add6 = add nsw i32 %1, %0
+  %arrayidx7 = getelementptr inbounds i32, i32* %a, i32 %i.017
+  store i32 %add6, i32* %arrayidx7, align 4
+  br label %for.inc
+
+for.inc:
+  %inc = add nuw nsw i32 %i.017, 1
+  %exitcond = icmp ult i32 %inc, %N
+  br i1 %exitcond, label %for.body, label %for.cond.cleanup
+}