[IRCE] Support narrow latch condition for wide range checks

[mkazantsev]

Summary

This patch relaxes restrictions on types of latch condition and range check.
In current implementation, they should match. This patch allows to handle
wide range checks against narrow condition. The motivating example is the
following:

int N = ...
for (long i = 0; (int) i < N; i++) {
  if (i >= length) deopt;
}

[mkazantsev]

We've run 3 days of dedicated fuzz tests for that, no issues found.

[reames]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1071

I can't convince myself this is correct when the IV would overflow. Can you explain why we don't need some form of overflow check here? Note that in LoopPredication in isSafeToTruncate, we *do* have an overflow check.

1398

I can't justify this change to myself. Can you explain why this is correct?

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1071

We should not be doing IRCE if IV overflows its type. This is guaranteed by functions isSafeIncreasingBound, isSafeDecreasingBound. I will add some more tests to ensure that, but I'm pretty sure that we already have plenty.

[mkazantsev]

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1398

Without this patch, the type of IndVarBase always matches with the type of range (and types of all range checks being affected). With this patch, we are dealing with something like:

for (i64 i = 0; trunc i64 i to i32 <s i32 n; i++) {
  if (i < i64 bound) deopt();
}

IVbase here is a i32 AddRec for trunc i64 i to i32, and range and SR are i64 ranges containing safe iteration bounds.

In this case, ExitMainLoopAt would be smin(sext i32 n to i64, i64 bound) which is basically a i64 value that doesn't exceed i32 max. We can trunc it to i32 and its value will not change. We would just make more truncations.

Basically, it doesn't matter. All values involved would also fit into the narrow type range. Using wider type has two benefits:

• It gives us less truncs that are only needed for comparisons;
• further transforms can completely get rid of the narrow type in the main loop (IVSimplify can then prove that sext(trunc(iv)) on latch check is a noop and we can use IV instead).

[reames]

Please land w/flag disabled. Wait until bots cycle, then enable flag separately.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

1071

I followed through the code, questions answered.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

static cl::opt<int> MaxExitProbReciprocal("irce-max-exit-prob-reciprocal",
                                           cl::Hidden, cl::init(10));
 
 static cl::opt<bool> SkipProfitabilityChecks("irce-skip-profitability-checks",
                                              cl::Hidden, cl::init(false));
 
 static cl::opt<bool> AllowUnsignedLatchCondition("irce-allow-unsigned-latch",
                                                  cl::Hidden, cl::init(true));
 
+static cl::opt<bool> AllowNarrowLatchCondition(
+    "irce-allow-narrow-latch", cl::Hidden, cl::init(true),
+    cl::desc("If set to true, IRCE may eliminate wide range checks in loops "
+             "with narrow latch condition."));
+
 static const char *ClonedLoopTag = "irce.loop.clone";
 
 #define DEBUG_TYPE "irce"
 
 namespace {
 
 /// An inductive range check is conditional branch in a loop with
 ///
LoopStructure::parseLoopStructure(ScalarEvolution &SE,
   Result.LoopExitAt = RightValue;
   Result.IsSignedPredicate = IsSignedPredicate;
 
   FailureReason = nullptr;
 
   return Result;
 }
 
+/// If the type of \p S matches with \p Ty, return \p S. Otherwise, return
+/// signed or unsigned extension of \p S to type \p Ty.
+static const SCEV *NoopOrExtend(const SCEV *S, Type *Ty, ScalarEvolution &SE,
+                                bool Signed) {
+  return Signed ? SE.getNoopOrSignExtend(S, Ty) : SE.getNoopOrZeroExtend(S, Ty);
+}
+
 Optional<LoopConstrainer::SubRanges>
 LoopConstrainer::calculateSubRanges(bool IsSignedPredicate) const {
   IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
 
-  if (Range.getType() != Ty)
+  auto *RTy = cast<IntegerType>(Range.getType());
+
+  // We only support wide range checks and narrow latches.
+  if (!AllowNarrowLatchCondition && RTy != Ty)
+    return None;
+  if (RTy->getBitWidth() < Ty->getBitWidth())
     return None;
 
   LoopConstrainer::SubRanges Result;
 
   // I think we can be more aggressive here and make this nuw / nsw if the
   // addition that feeds into the icmp for the latch's terminating branch is nuw
   // / nsw.  In any case, a wrapping 2's complement addition is safe.
-  const SCEV *Start = SE.getSCEV(MainLoopStructure.IndVarStart);
-  const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt);
+  const SCEV *Start = NoopOrExtend(SE.getSCEV(MainLoopStructure.IndVarStart),
+                                   RTy, SE, IsSignedPredicate);
+  const SCEV *End = NoopOrExtend(SE.getSCEV(MainLoopStructure.LoopExitAt), RTy,
+                                 SE, IsSignedPredicate);
 
   bool Increasing = MainLoopStructure.IndVarIncreasing;
 
   // We compute `Smallest` and `Greatest` such that [Smallest, Greatest), or
   // [Smallest, GreatestSeen] is the range of values the induction variable
   // takes.
 
   const SCEV *Smallest = nullptr, *Greatest = nullptr, *GreatestSeen = nullptr;
 
-  const SCEV *One = SE.getOne(Ty);
+  const SCEV *One = SE.getOne(RTy);
   if (Increasing) {
     Smallest = Start;
     Greatest = End;
     // No overflow, because the range [Smallest, GreatestSeen] is not empty.
     GreatestSeen = SE.getMinusSCEV(End, One);
   } else {
     // These two computations may sign-overflow.  Here is why that is okay:
     //
LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
   RRI.PseudoExit = BasicBlock::Create(Ctx, Twine(LS.Tag) + ".pseudo.exit", &F,
                                       BBInsertLocation);
 
   BranchInst *PreheaderJump = cast<BranchInst>(Preheader->getTerminator());
   bool Increasing = LS.IndVarIncreasing;
   bool IsSignedPredicate = LS.IsSignedPredicate;
 
   IRBuilder<> B(PreheaderJump);
+  auto *RangeTy = Range.getBegin()->getType();
+  auto NoopOrExt = [&](Value *V) {
+    if (V->getType() == RangeTy)
+      return V;
+    return IsSignedPredicate ? B.CreateSExt(V, RangeTy, "wide.start") :
+                               B.CreateZExt(V, RangeTy, "wide.start");
+  };
 
   // EnterLoopCond - is it okay to start executing this `LS'?
   Value *EnterLoopCond = nullptr;
   auto Pred =
       Increasing
           ? (IsSignedPredicate ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT)
           : (IsSignedPredicate ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT);
-  Value *IndVarStart = LS.IndVarStart;
-  Value *IndVarBase = LS.IndVarBase;
-  Value *LoopExitAt = LS.LoopExitAt;
+  Value *IndVarStart = NoopOrExt(LS.IndVarStart);
   EnterLoopCond = B.CreateICmp(Pred, IndVarStart, ExitSubloopAt);
 
   B.CreateCondBr(EnterLoopCond, LS.Header, RRI.PseudoExit);
   PreheaderJump->eraseFromParent();
 
   LS.LatchBr->setSuccessor(LS.LatchBrExitIdx, RRI.ExitSelector);
   B.SetInsertPoint(LS.LatchBr);
+  Value *IndVarBase = NoopOrExt(LS.IndVarBase);
   Value *TakeBackedgeLoopCond = B.CreateICmp(Pred, IndVarBase, ExitSubloopAt);
 
   Value *CondForBranch = LS.LatchBrExitIdx == 1
                              ? TakeBackedgeLoopCond
                              : B.CreateNot(TakeBackedgeLoopCond);
 
   LS.LatchBr->setCondition(CondForBranch);
 
   B.SetInsertPoint(RRI.ExitSelector);
 
   // IterationsLeft - are there any more iterations left, given the original
   // upper bound on the induction variable?  If not, we branch to the "real"
   // exit.
+  Value *LoopExitAt = NoopOrExt(LS.LoopExitAt);
   Value *IterationsLeft = B.CreateICmp(Pred, IndVarBase, LoopExitAt);
   B.CreateCondBr(IterationsLeft, RRI.PseudoExit, LS.LatchExit);
 
   BranchInst *BranchToContinuation =
       BranchInst::Create(ContinuationBlock, RRI.PseudoExit);
 
   // We emit PHI nodes into `RRI.PseudoExit' that compute the "latest" value of
   // each of the PHI nodes in the loop header.  This feeds into the initial
bool LoopConstrainer::run() {
   if (!MaybeSR.hasValue()) {
     LLVM_DEBUG(dbgs() << "irce: could not compute subranges\n");
     return false;
   }
 
   SubRanges SR = MaybeSR.getValue();
   bool Increasing = MainLoopStructure.IndVarIncreasing;
   IntegerType *IVTy =
-      cast<IntegerType>(MainLoopStructure.IndVarBase->getType());
+      cast<IntegerType>(Range.getBegin()->getType());
 
   SCEVExpander Expander(SE, F.getParent()->getDataLayout(), "irce");
   Instruction *InsertPt = OriginalPreheader->getTerminator();
 
   // It would have been better to make `PreLoop' and `PostLoop'
   // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
   // constructor.
   ClonedLoop PreLoop, PostLoop;

 
 /// 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,
     bool IsLatchSigned) const {
+  // We can deal when types of latch check and range checks don't match in case
+  // if latch check is more narrow.
+  auto *IVType = cast<IntegerType>(IndVar->getType());
+  auto *RCType = cast<IntegerType>(getBegin()->getType());
+  if (IVType->getBitWidth() > RCType->getBitWidth())
+    return None;
   // IndVar is of the form "A + B * I" (where "I" is the canonical induction
   // variable, that may or may not exist as a real llvm::Value in the loop) and
   // this inductive range check is a range check on the "C + D * I" ("C" is
   // getBegin() and "D" is getStep()).  We rewrite the value being range
   // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
   //
   // The actual inequalities we solve are of the form
   //
   //   0 <= M + 1 * IndVar < L given L >= 0  (i.e. N == 1)
   //
   // Here L stands for upper limit of the safe iteration space.
   // The inequality is satisfied by (0 - M) <= IndVar < (L - M). To avoid
   // overflows when calculating (0 - M) and (L - M) we, depending on type of
   // IV's iteration space, limit the calculations by borders of the iteration
   // space. For example, if IndVar is unsigned, (0 - M) overflows for any M > 0.
   // If we figured out that "anything greater than (-M) is safe", we strengthen
   // this to "everything greater than 0 is safe", assuming that values between
   // -M and 0 just do not exist in unsigned iteration space, and we don't want
   // to deal with overflown values.
 
   if (!IndVar->isAffine())
     return None;
 
-  const SCEV *A = IndVar->getStart();
-  const SCEVConstant *B = dyn_cast<SCEVConstant>(IndVar->getStepRecurrence(SE));
+  const SCEV *A = NoopOrExtend(IndVar->getStart(), RCType, SE, IsLatchSigned);
+  const SCEVConstant *B = dyn_cast<SCEVConstant>(
+      NoopOrExtend(IndVar->getStepRecurrence(SE), RCType, SE, IsLatchSigned));
   if (!B)
     return None;
   assert(!B->isZero() && "Recurrence with zero step?");
 
   const SCEV *C = getBegin();
   const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
   if (D != B)
     return None;
 
   assert(!D->getValue()->isZero() && "Recurrence with zero step?");
-  unsigned BitWidth = cast<IntegerType>(IndVar->getType())->getBitWidth();
+  unsigned BitWidth = RCType->getBitWidth();
   const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
 
   // Subtract Y from X so that it does not go through border of the IV
   // iteration space. Mathematically, it is equivalent to:
   //
   //    ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX).        [1]
   //
   // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to

test/Transforms/IRCE/wide_indvar.ll

+; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,loop(irce)' -S < %s 2>&1 | FileCheck %s
+
+; Check that we can remove trivially non-failing range check.
+define i32 @test_increasing_slt_slt_wide_simple_no_postloop() {
+
+; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_no_postloop(
+; CHECK-NOT:   preloop
+; CHECK-NOT:   postloop
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp slt i64 %iv, 100
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp slt i32 %narrow.iv, 100
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; This range check fails on the last iteration, so it needs a postloop.
+define i32 @test_increasing_slt_slt_wide_simple_postloop() {
+
+; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_postloop(
+; CHECK-NOT:   preloop
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp slt i64 %wide.start, 99
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp slt i64 %iv, 99
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp slt i32 %narrow.iv, 100
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; General case. If both %N and %M are non-negative, we do not need a preloop.
+define i32 @test_increasing_slt_slt_wide_non-negative(i32* %n_ptr, i64* %m_ptr) {
+
+; CHECK-LABEL: @test_increasing_slt_slt_wide_non-negative(
+; CHECK-NOT:   preloop
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp slt i64 %wide.start, %exit.mainloop.at
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  %N = load i32, i32* %n_ptr, !range !2
+  %M = load i64, i64* %m_ptr, !range !1
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp slt i64 %iv, %M
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp slt i32 %narrow.iv, %N
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; General case. Even though %M may be negative, we do not need a preloop because
+; we make a non-negativity runtime check against M and do not go to main loop if
+; M was negative.
+define i32 @test_increasing_slt_slt_wide_general(i32* %n_ptr, i64* %m_ptr) {
+
+; CHECK-LABEL: @test_increasing_slt_slt_wide_general(
+; CHECK-NOT:   preloop
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  %N = load i32, i32* %n_ptr, !range !2
+  %M = load i64, i64* %m_ptr
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp slt i64 %iv, %M
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp slt i32 %narrow.iv, %N
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; General case with preloop.
+define i32 @test_increasing_slt_slt_wide_general_preloop(i32* %n_ptr, i64* %m_ptr) {
+
+; CHECK-LABEL: @test_increasing_slt_slt_wide_general_preloop(
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       preloop
+; CHECK:       postloop
+
+entry:
+  %N = load i32, i32* %n_ptr, !range !2
+  %M = load i64, i64* %m_ptr
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp slt i64 %iv, %M
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv to i32
+  %latch.cond = icmp slt i32 %narrow.iv, %N
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; Same as above, multiple checks.
+define i32 @test_increasing_slt_slt_wide_multiple_checks(i32* %n_ptr, i64* %m1_ptr, i64* %m2_ptr, i64* %m3_ptr, i64* %m4_ptr) {
+; CHECK-LABEL: @test_increasing_slt_slt_wide_multiple_checks(
+; CHECK-NOT:   preloop
+; CHECK:       loop:
+; CHECK:       %c1 = and i1 true, true
+; CHECK:       %c2 = and i1 %c1, true
+; CHECK:       %rc = and i1 %c2, true
+; CHECK:       br i1 %rc, label %backedge, label %check_failed.loopexit
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp slt i64
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  %N = load i32, i32* %n_ptr, !range !2
+  %M1 = load i64, i64* %m1_ptr
+  %M2 = load i64, i64* %m2_ptr
+  %M3 = load i64, i64* %m3_ptr
+  %M4 = load i64, i64* %m4_ptr
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc1 = icmp slt i64 %iv, %M1
+  %rc2 = icmp slt i64 %iv, %M2
+  %rc3 = icmp slt i64 %iv, %M3
+  %rc4 = icmp slt i64 %iv, %M4
+  %c1 = and i1 %rc1, %rc2
+  %c2 = and i1 %c1, %rc3
+  %rc = and i1 %c2, %rc4
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp slt i32 %narrow.iv, %N
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; Wide IV against narrow range check. We don't currently support it.
+define i32 @test_increasing_slt_slt_wide_simple_negtest_narrow_rc() {
+
+; CHECK-LABEL: @test_increasing_slt_slt_wide_simple_negtest_narrow_rc(
+; CHECK-NOT:   i1 true
+; CHECK-NOT:   main
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %narrow.iv = trunc i64 %iv to i32
+  %rc = icmp slt i32 %narrow.iv, 101
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %latch.cond = icmp slt i64 %iv, 100
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; Check that we can remove trivially non-failing range check.
+define i32 @test_increasing_ult_ult_wide_simple_no_postloop() {
+
+; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_no_postloop(
+; CHECK-NOT:   preloop
+; CHECK-NOT:   postloop
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp ult i64 %iv, 100
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp ult i32 %narrow.iv, 100
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; This range check fails on the last iteration, so it needs a postloop.
+define i32 @test_increasing_ult_ult_wide_simple_postloop() {
+
+; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_postloop(
+; CHECK-NOT:   preloop
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp ult i64 %wide.start, 99
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp ult i64 %iv, 99
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp ult i32 %narrow.iv, 100
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; General case. If both %N and %M are non-negative, we do not need a preloop.
+define i32 @test_increasing_ult_ult_wide_non-negative(i32* %n_ptr, i64* %m_ptr) {
+
+; CHECK-LABEL: @test_increasing_ult_ult_wide_non-negative(
+; CHECK-NOT:   preloop
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp ult i64 %wide.start, %exit.mainloop.at
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  %N = load i32, i32* %n_ptr, !range !2
+  %M = load i64, i64* %m_ptr, !range !1
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp ult i64 %iv, %M
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp ult i32 %narrow.iv, %N
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; General case. Even though %M may be negative, we do not need a preloop because
+; we make a non-negativity runtime check against M and do not go to main loop if
+; M was negative.
+define i32 @test_increasing_ult_ult_wide_general(i32* %n_ptr, i64* %m_ptr) {
+
+; CHECK-LABEL: @test_increasing_ult_ult_wide_general(
+; CHECK-NOT:   preloop
+; CHECK:       loop:
+; CHECK:       br i1 true, label %backedge, label %check_failed
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp ult i64
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  %N = load i32, i32* %n_ptr, !range !2
+  %M = load i64, i64* %m_ptr
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp ult i64 %iv, %M
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp ult i32 %narrow.iv, %N
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; Same as above, multiple checks.
+define i32 @test_increasing_ult_ult_wide_multiple_checks(i32* %n_ptr, i64* %m1_ptr, i64* %m2_ptr, i64* %m3_ptr, i64* %m4_ptr) {
+; CHECK-LABEL: @test_increasing_ult_ult_wide_multiple_checks(
+; CHECK-NOT:   preloop
+; CHECK:       loop:
+; CHECK:       %c1 = and i1 true, true
+; CHECK:       %c2 = and i1 %c1, true
+; CHECK:       %rc = and i1 %c2, true
+; CHECK:       br i1 %rc, label %backedge, label %check_failed.loopexit
+; CHECK:       backedge
+; CHECK:       [[COND:%[^ ]+]] = icmp ult i64
+; CHECK:       br i1 [[COND]], label %loop, label %main.exit.selector
+; CHECK:       postloop
+
+entry:
+  %N = load i32, i32* %n_ptr, !range !2
+  %M1 = load i64, i64* %m1_ptr
+  %M2 = load i64, i64* %m2_ptr
+  %M3 = load i64, i64* %m3_ptr
+  %M4 = load i64, i64* %m4_ptr
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc1 = icmp ult i64 %iv, %M1
+  %rc2 = icmp ult i64 %iv, %M2
+  %rc3 = icmp ult i64 %iv, %M3
+  %rc4 = icmp ult i64 %iv, %M4
+  %c1 = and i1 %rc1, %rc2
+  %c2 = and i1 %c1, %rc3
+  %rc = and i1 %c2, %rc4
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %narrow.iv = trunc i64 %iv.next to i32
+  %latch.cond = icmp ult i32 %narrow.iv, %N
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+; Wide IV against narrow range check. We don't currently support it.
+define i32 @test_increasing_ult_ult_wide_simple_negtest_narrow_rc() {
+
+; CHECK-LABEL: @test_increasing_ult_ult_wide_simple_negtest_narrow_rc(
+; CHECK-NOT:   i1 true
+; CHECK-NOT:   main
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %backedge ]
+  %narrow.iv = trunc i64 %iv to i32
+  %rc = icmp ult i32 %narrow.iv, 101
+  br i1 %rc, label %backedge, label %check_failed
+
+backedge:
+  %iv.next = add i64 %iv, 1
+  %latch.cond = icmp ult i64 %iv, 100
+  br i1 %latch.cond, label %loop, label %exit
+
+exit:
+  ret i32 %narrow.iv
+
+check_failed:
+  ret i32 -1
+}
+
+!0 = !{i32 0, i32 2147483647}
+!1 = !{i64 0, i64 9223372036854775807}
+!2 = !{i32 1, i32 2147483647}