[IRCE] Parse range checks in the form of "LHS - RHS vs Limit"

[aleksandr.popov]

Summary

Introduced the following range checks forms parsing:

• IV - Offset vs Limit
• Offset - IV vs Limit

Range's end boundary is computed as (Offset +/- Limit ).

If it's not possible to prove at compile time that computed upper bound
will not overflow, then scale boundary computation to a wider type to
perform overflow check at runtime.

Runtime overflow will be implemented in the next patch. In the meantime
safe range for such kind of checks isn't computed.

[skatkov]

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

386

More context here in comment. Why with this restriction failed we cannot process.

405

What exactly overflow you can expect?
Does it makes sense to check, may be we can prove that overflow is not possible and we can avoid scaling?

434

Add some message

1747

Can we add some LLVM_DEBUG output here and add a test which tests whether it is printed and check the values of getBegin(), getEnd() and IndVar?

It would be nice to have tests for this functionality?

[aleksandr.popov]

Update according to review comments

[aleksandr.popov]

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

386

I removed the check that initial subtraction will not overflow and added explanation why we don't need that check

405

Good point, done

1747

Done, thanks!

[skatkov]

One comment, other looks good...

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

474

what if you did not scale and Limit == S_INT_MAX? Limit + 1 will overflow then?

[aleksandr.popov]

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

474

Then we will scale Limit + 1, if we can't prove that if doesn't overflow

[aleksandr.popov]

Add more tests

[aleksandr.popov]

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

474

I've added 2 tests:

• In first one we have IV < N + 2;
• in the second one we have IV <= N + 2;

In both cases 8-bit N < 126.

In the first example we can prove that (N + 2) will not overflow and we don't scale.
In the second one we are adding 1 to the (N + 2), since predicate is not-strict. Afterwards no-overflow becomes unprovable and we scale.

[JonChesterfield]

This may have taken down the openmp amdgpu bot https://lab.llvm.org/buildbot/#/builders/193 - @jhuber6 @jdoerfert @ronlieb we don't seem to get any information from the failing tests about what went wrong, e.g.

******************** TEST 'libomptarget :: amdgcn-amd-amdhsa :: api/assert.c' FAILED ********************
Script:
--
: 'RUN: at line 1';   /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./bin/clang -fopenmp    -I /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.src/openmp/libomptarget/test -I /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src -L /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/libomptarget -L /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./lib -L /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src  -Wl,-rpath,/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/libomptarget -Wl,-rpath,/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src -Wl,-rpath,/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./lib -fopenmp-targets=amdgcn-amd-amdhsa /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.src/openmp/libomptarget/test/api/assert.c -o /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/libomptarget/test/amdgcn-amd-amdhsa/api/Output/assert.c.tmp && /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/libomptarget/test/amdgcn-amd-amdhsa/api/Output/assert.c.tmp | /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./bin/FileCheck /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.src/openmp/libomptarget/test/api/assert.c
--
Exit Code: 2
Command Output (stdout):
--
$ ":" "RUN: at line 1"
$ "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./bin/clang" "-fopenmp" "-I" "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.src/openmp/libomptarget/test" "-I" "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src" "-L" "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/libomptarget" "-L" "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./lib" "-L" "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src" "-Wl,-rpath,/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/libomptarget" "-Wl,-rpath,/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/runtime/src" "-Wl,-rpath,/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./lib" "-fopenmp-targets=amdgcn-amd-amdhsa" "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.src/openmp/libomptarget/test/api/assert.c" "-o" "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/libomptarget/test/amdgcn-amd-amdhsa/api/Output/assert.c.tmp"
$ "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/runtimes/runtimes-bins/openmp/libomptarget/test/amdgcn-amd-amdhsa/api/Output/assert.c.tmp"
note: command had no output on stdout or stderr
error: command failed with exit status: -11
$ "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./bin/FileCheck" "/home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.src/openmp/libomptarget/test/api/assert.c"
# command stderr:
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.build/./bin/FileCheck /home/ompworker/bbot/openmp-offload-amdgpu-runtime/llvm.src/openmp/libomptarget/test/api/assert.c
error: command failed with exit status: 2
--
********************

Kicked the bot to see if it fails again.

[llvm-commits]

It looks like next bot failed in the same way.
Could you please provide steps to reproduce the failure?

@Aleksandr Popov, could you please revert patch for a while we figure out what happens...

[JonChesterfield]

Thanks for the revert, has taken us back to green. Repro is build openmp and run check-openmp, most of them failed, but I'd guess this was a problem in codegen. Openmp isn't always very easy to build, hopefully someone has some spare cycles to see what's gone wrong.

[jhuber6]

In D154069#4485286, @JonChesterfield wrote:

Thanks for the revert, has taken us back to green. Repro is build openmp and run check-openmp, most of them failed, but I'd guess this was a problem in codegen. Openmp isn't always very easy to build, hopefully someone has some spare cycles to see what's gone wrong.

Seems the libc tests for AMDGPU were fine during that period, so it's probably something specific to OpenMP unfortunately https://lab.llvm.org/staging/#/builders/247/builds/2795.

[aleksandr.popov]

Repro is build openmp and run check-openmp

I've tried to reproduce the tests, but AMDGPU ones (which were actually failed) were not generated:

...
-- LIBOMPTARGET: Not generating AMDGPU tests, no supported devices detected.

Do you know how to fix that?

[jhuber6]

In D154069#4486045, @aleksandr.popov wrote:

Repro is build openmp and run check-openmp

I've tried to reproduce the tests, but AMDGPU ones (which were actually failed) were not generated:

...
-- LIBOMPTARGET: Not generating AMDGPU tests, no supported devices detected.

Do you know how to fix that?

It should (ideally) depend on whether or not you have ROCm and a functional GPU on your system. It basically just calls amdgpu-arch to see if there's any output. This is to prevent OpenMP from running GPU tests on a machine that can't support it. Either make sure that the system is configured at build time, or us LIBOMPTARGET_FORCE_AMDGPU_TESTS=ON to override.

[aleksandr.popov]

It should (ideally) depend on whether or not you have ROCm and a functional GPU on your system. It basically just calls amdgpu-arch to see if there's any output.

Unfortunately amdgpu-arch not found on my machine. I've got amdgpu-install tool but what exactly should I install to execute AMDGPU tests?

BTW, without installed amdgpu all tests failed the same way as they failed in the https://lab.llvm.org/buildbot/#/builders/193

And one more question: my changes relate to InductiveRangeCheckElimination only. How does OpenMP use IRCE which caused the tests to fail?

[aleksandr.popov]

Hi @jplehr! Could you please help with reproducing AMDGPU tests locally?

[nikic]

IRCE isn't used in-tree at all, so it's very weird that it affects OpenMP -- or anything at all.

[jplehr]

In D154069#4488452, @aleksandr.popov wrote:

Hi @jplehr! Could you please help with reproducing AMDGPU tests locally?

Sure. I'll check locally and see what happens.

[jhuber6]

In D154069#4488376, @aleksandr.popov wrote:

It should (ideally) depend on whether or not you have ROCm and a functional GPU on your system. It basically just calls amdgpu-arch to see if there's any output.

Unfortunately amdgpu-arch not found on my machine. I've got amdgpu-install tool but what exactly should I install to execute AMDGPU tests?

BTW, without installed amdgpu all tests failed the same way as they failed in the https://lab.llvm.org/buildbot/#/builders/193

And one more question: my changes relate to InductiveRangeCheckElimination only. How does OpenMP use IRCE which caused the tests to fail?

amdgpu-arch should be built unconditionally by clang. So generally to build OpenMP we'd recommend CMake like -DLLVM_ENABLE_PROJECTS=clang;lld -DLLVM_ENABLE_RUNTIMES=openmp -DLIBOMPTARGET_FORCE_AMDGPU_TESTS=ON

[jhuber6]

Chances are that a recent patch I made broke something in libomptarget and this and other patches spuriously trigger the failure. Currently looking into it.

[aleksandr.popov]

@jhuber6 Does https://reviews.llvm.org/D154971 fix my case? Could I try to reland the patch?

[jhuber6]

In D154069#4490018, @aleksandr.popov wrote:

@jhuber6 Does https://reviews.llvm.org/D154971 fix my case? Could I try to reland the patch?

Worth a shot, go for it.

[aleksandr.popov]

Worth a shot, go for it.

Thanks, let's try

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

 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 cl::opt<unsigned> MaxTypeSizeForOverflowCheck(
+    "irce-max-type-size-for-overflow-check", cl::Hidden, cl::init(32),
+    cl::desc(
+        "Maximum size of range check type for which can be produced runtime "
+        "overflow check of its limit's computation"));
+
+static cl::opt<bool>
+    PrintScaledBoundaryRangeChecks("irce-print-scaled-boundary-range-checks",
+                                   cl::Hidden, cl::init(false));
+
 static const char *ClonedLoopTag = "irce.loop.clone";
 
 #define DEBUG_TYPE "irce"
 
 namespace {
 
 /// An inductive range check is conditional branch in a loop with
 ///
extractRangeChecksFromCond(Loop *L, ScalarEvolution &SE, Use &ConditionUse,
                              SmallVectorImpl<InductiveRangeCheck> &Checks,
                              SmallPtrSetImpl<Value *> &Visited);
 
   static bool parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
                                   ICmpInst::Predicate Pred, ScalarEvolution &SE,
                                   const SCEVAddRecExpr *&Index,
                                   const SCEV *&End);
 
+  static bool reassociateSubLHS(Loop *L, Value *VariantLHS, Value *InvariantRHS,
+                                ICmpInst::Predicate Pred, ScalarEvolution &SE,
+                                const SCEVAddRecExpr *&Index, const SCEV *&End);
+
 public:
   const SCEV *getBegin() const { return Begin; }
   const SCEV *getStep() const { return Step; }
   const SCEV *getEnd() const { return End; }
 
   void print(raw_ostream &OS) const {
     OS << "InductiveRangeCheck:\n";
     OS << "  Begin: ";
if (IsLoopInvariant(LHS)) {
     Pred = CmpInst::getSwappedPredicate(Pred);
   } else if (!IsLoopInvariant(RHS))
     // Both LHS and RHS are loop variant
     return false;
 
   if (parseIvAgaisntLimit(L, LHS, RHS, Pred, SE, Index, End))
     return true;
 
+  if (reassociateSubLHS(L, LHS, RHS, Pred, SE, Index, End))
+    return true;
+
+  // TODO: support ReassociateAddLHS
   return false;
 }
 
 // Try to parse range check in the form of "IV vs Limit"
 bool InductiveRangeCheck::parseIvAgaisntLimit(Loop *L, Value *LHS, Value *RHS,
                                               ICmpInst::Predicate Pred,
                                               ScalarEvolution &SE,
                                               const SCEVAddRecExpr *&Index,
if (SE.willNotOverflow(Instruction::BinaryOps::Add, Signed, RHSS, One)) {
       return true;
     }
     return false;
   }
 
   llvm_unreachable("default clause returns!");
 }
 
+// Try to parse range check in the form of "IV - Offset vs Limit" or "Offset -
+// IV vs Limit"
+bool InductiveRangeCheck::reassociateSubLHS(
+    Loop *L, Value *VariantLHS, Value *InvariantRHS, ICmpInst::Predicate Pred,
+    ScalarEvolution &SE, const SCEVAddRecExpr *&Index, const SCEV *&End) {
+  Value *LHS, *RHS;
+  if (!match(VariantLHS, m_Sub(m_Value(LHS), m_Value(RHS))))
+    return false;
+
+  const SCEV *IV = SE.getSCEV(LHS);
+  const SCEV *Offset = SE.getSCEV(RHS);
+  const SCEV *Limit = SE.getSCEV(InvariantRHS);
+
+  bool OffsetSubtracted = false;
+  if (SE.isLoopInvariant(IV, L))
+    // "Offset - IV vs Limit"
+    std::swap(IV, Offset);
+  else if (SE.isLoopInvariant(Offset, L))
+    // "IV - Offset vs Limit"
+    OffsetSubtracted = true;
+  else
+    return false;
+
+  const auto *AddRec = dyn_cast<SCEVAddRecExpr>(IV);
+  if (!AddRec)
+    return false;
+
+  // In order to turn "IV - Offset < Limit" into "IV < Limit + Offset", we need
+  // to be able to freely move values from left side of inequality to right side
+  // (just as in normal linear arithmetics). Overflows make things much more
+  // complicated, so we want to avoid this.
+  //
+  // Let's prove that the initial subtraction doesn't overflow with all IV's
+  // values from the safe range constructed for that check.
+  //
+  // [Case 1] IV - Offset < Limit
+  // It doesn't overflow if:
+  //     SINT_MIN <= IV - Offset <= SINT_MAX
+  // In terms of scaled SINT we need to prove:
+  //     SINT_MIN + Offset <= IV <= SINT_MAX + Offset
+  // Safe range will be constructed:
+  //     0 <= IV < Limit + Offset
+  // It means that 'IV - Offset' doesn't underflow, because:
+  //     SINT_MIN + Offset < 0 <= IV
+  // and doesn't overflow:
+  //     IV < Limit + Offset <= SINT_MAX + Offset
+  //
+  // [Case 2] Offset - IV > Limit
+  // It doesn't overflow if:
+  //     SINT_MIN <= Offset - IV <= SINT_MAX
+  // In terms of scaled SINT we need to prove:
+  //     -SINT_MIN >= IV - Offset >= -SINT_MAX
+  //     Offset - SINT_MIN >= IV >= Offset - SINT_MAX
+  // Safe range will be constructed:
+  //     0 <= IV < Offset - Limit
+  // It means that 'Offset - IV' doesn't underflow, because
+  //     Offset - SINT_MAX < 0 <= IV
+  // and doesn't overflow:
+  //     IV < Offset - Limit <= Offset - SINT_MIN
+  //
+  // For the computed upper boundary of the IV's range (Offset +/- Limit) we
+  // don't know exactly whether it overflows or not. So if we can't prove this
+  // fact at compile time, we scale boundary computations to a wider type with
+  // the intention to add runtime overflow check.
+
+  auto getExprScaledIfOverflow = [&](Instruction::BinaryOps BinOp,
+                                     const SCEV *LHS,
+                                     const SCEV *RHS) -> const SCEV * {
+    const SCEV *(ScalarEvolution::*Operation)(const SCEV *, const SCEV *,
+                                              SCEV::NoWrapFlags, unsigned);
+    switch (BinOp) {
+    default:
+      llvm_unreachable("Unsupported binary op");
+    case Instruction::Add:
+      Operation = &ScalarEvolution::getAddExpr;
+      break;
+    case Instruction::Sub:
+      Operation = &ScalarEvolution::getMinusSCEV;
+      break;
+    }
+
+    if (SE.willNotOverflow(BinOp, ICmpInst::isSigned(Pred), LHS, RHS,
+                           cast<Instruction>(VariantLHS)))
+      return (SE.*Operation)(LHS, RHS, SCEV::FlagAnyWrap, 0);
+
+    // We couldn't prove that the expression does not overflow.
+    // Than scale it to a wider type to check overflow at runtime.
+    auto *Ty = cast<IntegerType>(LHS->getType());
+    if (Ty->getBitWidth() > MaxTypeSizeForOverflowCheck)
+      return nullptr;
+
+    auto WideTy = IntegerType::get(Ty->getContext(), Ty->getBitWidth() * 2);
+    return (SE.*Operation)(SE.getSignExtendExpr(LHS, WideTy),
+                           SE.getSignExtendExpr(RHS, WideTy), SCEV::FlagAnyWrap,
+                           0);
+  };
+
+  if (OffsetSubtracted)
+    // "IV - Offset < Limit" -> "IV" < Offset + Limit
+    Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Offset, Limit);
+  else {
+    // "Offset - IV > Limit" -> "IV" < Offset - Limit
+    Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Sub, Offset, Limit);
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+
+  if (Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE) {
+    // "Expr <= Limit" -> "Expr < Limit + 1"
+    if (Pred == ICmpInst::ICMP_SLE && Limit)
+      Limit = getExprScaledIfOverflow(Instruction::BinaryOps::Add, Limit,
+                                      SE.getOne(Limit->getType()));
+    if (Limit) {
+      Index = AddRec;
+      End = Limit;
+      return true;
+    }
+  }
+  return false;
+}
+
 void InductiveRangeCheck::extractRangeChecksFromCond(
     Loop *L, ScalarEvolution &SE, Use &ConditionUse,
     SmallVectorImpl<InductiveRangeCheck> &Checks,
     SmallPtrSetImpl<Value *> &Visited) {
   Value *Condition = ConditionUse.get();
   if (!Visited.insert(Condition).second)
     return;
 

 std::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 = dyn_cast<IntegerType>(IndVar->getType());
   auto *RCType = dyn_cast<IntegerType>(getBegin()->getType());
+  auto *EndType = dyn_cast<IntegerType>(getEnd()->getType());
   // Do not work with pointer types.
   if (!IVType || !RCType)
     return std::nullopt;
   if (IVType->getBitWidth() > RCType->getBitWidth())
     return std::nullopt;
+
+  auto PrintRangeCheck = [&](raw_ostream &OS) {
+    auto L = IndVar->getLoop();
+    OS << "irce: in function ";
+    OS << L->getHeader()->getParent()->getName();
+    OS << ", in ";
+    L->print(OS);
+    OS << "there is range check with scaled boundary:\n";
+    print(OS);
+  };
+
+  if (EndType->getBitWidth() > RCType->getBitWidth()) {
+    assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
+    if (PrintScaledBoundaryRangeChecks)
+      PrintRangeCheck(errs());
+    // End is computed with extended type but will be truncated to a narrow one
+    // type of range check. Therefore we need a check that the result will not
+    // overflow in terms of narrow type.
+    // TODO: Support runtime overflow check for End
+    return std::nullopt;
+  }
+
   // 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
   //

llvm/test/Transforms/IRCE/iv-plus-offset-range-check.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
-; RUN: opt -verify-loop-info -passes=irce -S < %s 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -passes=irce -irce-print-scaled-boundary-range-checks -S < %s 2>&1 | FileCheck %s
+
+
+; CHECK: irce: in function test1, in Loop at depth 1 containing: %loop<header><exiting>,%inbounds<latch><exiting>
+; CHECK-NEXT: there is range check with scaled boundary:
+; CHECK-NEXT: InductiveRangeCheck:
+; CHECK-NEXT:   Begin: 0  Step: 1  End: (-1 + (sext i8 %n to i16))<nsw>
+; CHECK-NEXT:   CheckUse:   br i1 %check, label %inbounds, label %out_of_bounds Operand: 0
+;
+; CHECK-NEXT: irce: in function test4, in Loop at depth 1 containing: %loop<header><exiting>,%inbounds<latch><exiting>
+; CHECK-NEXT: there is range check with scaled boundary:
+; CHECK-NEXT: InductiveRangeCheck:
+; CHECK-NEXT:   Begin: 0  Step: 1  End: (-2 + (sext i8 %n to i16))<nsw>
+; CHECK-NEXT:   CheckUse:   br i1 %check, label %inbounds, label %out_of_bounds Operand: 0
+;
 
 ; IV = 0; IV <s limit; IV += 1;
 ;   Check(N - IV >= 2)
 ; TODO: IRCE is allowed.
 define i8 @test1(i8 %limit, i8 %n) {
 ; CHECK-LABEL: define i8 @test1
 ; CHECK-SAME: (i8 [[LIMIT:%.*]], i8 [[N:%.*]]) {
 ; CHECK-NEXT:  entry:

 define i8 @test1a(i8 %limit, ptr %p) {
 ; CHECK-LABEL: define i8 @test1a
 ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG0:![0-9]+]]
 ; CHECK-NEXT:    [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
 ; CHECK-NEXT:    br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i8 [[N]], -1
+; CHECK-NEXT:    [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP0]], i8 0)
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i8 [[SMIN]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = mul i8 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    [[SMIN2:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP2]])
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN2]], i8 0)
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_PREHEADER4:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader4:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER4]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp sge i8 [[SUB]], 2
-; CHECK-NEXT:    br i1 [[CHECK]], label [[INBOUNDS]], label [[OUT_OF_BOUNDS:%.*]]
+; CHECK-NEXT:    br i1 true, label [[INBOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT5:%.*]]
 ; CHECK:       inbounds:
 ; CHECK-NEXT:    [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i8 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK:       main.exit.selector:
+; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i8 [ [[IDX_NEXT]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA3:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp slt i8 [[IDX_NEXT_LCSSA]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[TMP5]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       main.pseudo.exit:
+; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
+; CHECK:       exit.loopexit.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA1_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX_LCSSA3]], [[MAIN_EXIT_SELECTOR]] ], [ [[IDX_LCSSA1_PH]], [[EXIT_LOOPEXIT_LOOPEXIT:%.*]] ]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK:       out_of_bounds.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP]], [[LOOP_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
+; CHECK:       out_of_bounds.loopexit5:
+; CHECK-NEXT:    [[IDX_LCSSA_PH6:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 ; CHECK:       out_of_bounds:
-; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX_LCSSA_PH]], [[OUT_OF_BOUNDS_LOOPEXIT:%.*]] ], [ [[IDX_LCSSA_PH6]], [[OUT_OF_BOUNDS_LOOPEXIT5]] ]
 ; CHECK-NEXT:    ret i8 [[IDX_LCSSA]]
+; CHECK:       postloop:
+; CHECK-NEXT:    br label [[LOOP_POSTLOOP]]
+; CHECK:       loop.postloop:
+; CHECK-NEXT:    [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
+; CHECK-NEXT:    [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
+; CHECK-NEXT:    [[CHECK_POSTLOOP:%.*]] = icmp sge i8 [[SUB_POSTLOOP]], 2
+; CHECK-NEXT:    br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
+; CHECK:       inbounds.postloop:
+; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
+; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP1:![0-9]+]], !irce.loop.clone [[META6:![0-9]+]]
 ;
 entry:
   %n = load i8, ptr %p, !range !0
   %precheck = icmp sgt i8 %limit, 0
   br i1 %precheck, label %loop, label %exit
 
 loop:
   %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]

 ; CHECK:       loop.postloop:
 ; CHECK-NEXT:    [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
 ; CHECK-NEXT:    [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2
 ; CHECK-NEXT:    [[CHECK_POSTLOOP:%.*]] = icmp sle i8 [[ADD_POSTLOOP]], [[N]]
 ; CHECK-NEXT:    br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
 ; CHECK:       inbounds.postloop:
 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
 ; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP1:![0-9]+]], !irce.loop.clone !6
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP7:![0-9]+]], !irce.loop.clone [[META6]]
 ;
 entry:
   %n = load i8, ptr %p, !range !0
   %precheck = icmp sgt i8 %limit, 0
   br i1 %precheck, label %loop, label %exit
 
 loop:
   %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]

 define i8 @test4a(i8 %limit, ptr %p) {
 ; CHECK-LABEL: define i8 @test4a
 ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG0]]
 ; CHECK-NEXT:    [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
 ; CHECK-NEXT:    br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.preheader:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i8 [[N]], -2
+; CHECK-NEXT:    [[TMP1:%.*]] = add nuw i8 [[N]], 127
+; CHECK-NEXT:    [[SMAX:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 0)
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 [[TMP0]], [[SMAX]]
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i8 [[N]], -2
+; CHECK-NEXT:    [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP3]], i8 0)
+; CHECK-NEXT:    [[SMAX2:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 -1)
+; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i8 [[SMAX2]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul i8 [[TMP2]], [[TMP4]]
+; CHECK-NEXT:    [[SMIN3:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP5]])
+; CHECK-NEXT:    [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN3]], i8 0)
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP6]], label [[LOOP_PREHEADER6:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
+; CHECK:       loop.preheader6:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER6]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp sgt i8 [[SUB]], 2
-; CHECK-NEXT:    br i1 [[CHECK]], label [[INBOUNDS]], label [[OUT_OF_BOUNDS:%.*]]
+; CHECK-NEXT:    br i1 true, label [[INBOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT7:%.*]]
 ; CHECK:       inbounds:
 ; CHECK-NEXT:    [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[TMP7:%.*]] = icmp slt i8 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
+; CHECK-NEXT:    br i1 [[TMP7]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
+; CHECK:       main.exit.selector:
+; CHECK-NEXT:    [[IDX_NEXT_LCSSA:%.*]] = phi i8 [ [[IDX_NEXT]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA5:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[TMP8:%.*]] = icmp slt i8 [[IDX_NEXT_LCSSA]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[TMP8]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
+; CHECK:       main.pseudo.exit:
+; CHECK-NEXT:    [[IDX_COPY:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    [[INDVAR_END:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
+; CHECK-NEXT:    br label [[POSTLOOP:%.*]]
+; CHECK:       exit.loopexit.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA1_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[EXIT_LOOPEXIT]]
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
+; CHECK-NEXT:    [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX_LCSSA5]], [[MAIN_EXIT_SELECTOR]] ], [ [[IDX_LCSSA1_PH]], [[EXIT_LOOPEXIT_LOOPEXIT:%.*]] ]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK:       out_of_bounds.loopexit:
+; CHECK-NEXT:    [[IDX_LCSSA_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP]], [[LOOP_POSTLOOP:%.*]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS:%.*]]
+; CHECK:       out_of_bounds.loopexit7:
+; CHECK-NEXT:    [[IDX_LCSSA_PH8:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    br label [[OUT_OF_BOUNDS]]
 ; CHECK:       out_of_bounds:
-; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
+; CHECK-NEXT:    [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX_LCSSA_PH]], [[OUT_OF_BOUNDS_LOOPEXIT:%.*]] ], [ [[IDX_LCSSA_PH8]], [[OUT_OF_BOUNDS_LOOPEXIT7]] ]
 ; CHECK-NEXT:    ret i8 [[IDX_LCSSA]]
+; CHECK:       postloop:
+; CHECK-NEXT:    br label [[LOOP_POSTLOOP]]
+; CHECK:       loop.postloop:
+; CHECK-NEXT:    [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
+; CHECK-NEXT:    [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
+; CHECK-NEXT:    [[CHECK_POSTLOOP:%.*]] = icmp sgt i8 [[SUB_POSTLOOP]], 2
+; CHECK-NEXT:    br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
+; CHECK:       inbounds.postloop:
+; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
+; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP8:![0-9]+]], !irce.loop.clone [[META6]]
 ;
 entry:
   %n = load i8, ptr %p, !range !0
   %precheck = icmp sgt i8 %limit, 0
   br i1 %precheck, label %loop, label %exit
 
 loop:
   %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]

 ; CHECK:       loop.postloop:
 ; CHECK-NEXT:    [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
 ; CHECK-NEXT:    [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2
 ; CHECK-NEXT:    [[CHECK_POSTLOOP:%.*]] = icmp slt i8 [[ADD_POSTLOOP]], [[N]]
 ; CHECK-NEXT:    br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
 ; CHECK:       inbounds.postloop:
 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
 ; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP7:![0-9]+]], !irce.loop.clone !6
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP9:![0-9]+]], !irce.loop.clone [[META6]]
 ;
 entry:
   %precheck = icmp sgt i8 %limit, 0
   br i1 %precheck, label %loop, label %exit
 
 loop:
   %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
   %add = add i8 %idx, 2

 ; CHECK:       loop.postloop:
 ; CHECK-NEXT:    [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
 ; CHECK-NEXT:    [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2
 ; CHECK-NEXT:    [[CHECK_POSTLOOP:%.*]] = icmp slt i8 [[ADD_POSTLOOP]], [[N]]
 ; CHECK-NEXT:    br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
 ; CHECK:       inbounds.postloop:
 ; CHECK-NEXT:    [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
 ; CHECK-NEXT:    [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
-; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP8:![0-9]+]], !irce.loop.clone !6
+; CHECK-NEXT:    br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP10:![0-9]+]], !irce.loop.clone [[META6]]
 ;
 entry:
   %n = load i8, ptr %p, !range !0
   %precheck = icmp sgt i8 %limit, 0
   br i1 %precheck, label %loop, label %exit
 
 loop:
   %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]