Inductive unrolling pass

[mkazantsev]

Summary

This patch demonstrates an optimization LLVM is currently missing. It is
related to elimination of checks for which we know exact symbolic exit
count via unrolling. Imagine the loop where we have an exit with known
exit count:

do {
  ...
  if (cond()) break; // if iteration № EC is reached, we must break here.
  ...
} while (true);

Here is what happens if we unroll it with a factor of UF

do {
  ...
  if (cond()) break; // Corresponds to iterations №№ N * UF + 0 in the initial loop.
  ...
  if (cond()) break; // Corresponds to iterations №№ N * UF + 1 in the initial loop.
  ...
  if (cond()) break; // Corresponds to iterations №№ N * UF + 2 in the initial loop.
  <...>
  if (cond()) break; // Corresponds to iterations №№ N * UF + UF - 1 in the initial loop.
  ...
} while (true);

Important fact: let Rem be EC urem UF. Then, if we know its value (for example, Rem = 2),
then we know that only the exit in the unrolled loop which corresponds to N * UF + 2 may
possibly exit, and no other exit corresponds to the exiting iteration of the original loop, so
they never exit the loop. So we can remove UF - 1 checks leaving only one of them. So overall,
we save up to EC / UF * (UF - 1) checks over all loop iterations.

The problem is that we do not actually know value of Rem statically in most cases. But we always
know it in runtime if we know the exit count and selected the UF. We can insert a preloop which
will make sure that we enter the unrolled version of the loop with the iteration number corresponding
to Rem (of the original loop). So we always know that only the first cloned check in the unrolled
loop needs to be executed. The resulting solution would be:

for (i = 0; i < Rem; i++) {
  ...
  if (cond()) goto exit;
  ...
}
do {
  ...
  if (cond()) break; // Corresponds to iterations №№ N * UF + Rem + 0 in the initial loop.
  ...
  if (false) break; // Corresponds to iterations №№ N * UF + Rem + 1 in the initial loop and may never happen.
  ...
  if (false) break; // Corresponds to iterations №№ N * UF + Rem + 2 in the initial loop and may never happen.
  <...>
  if (false) break; // Corresponds to iterations №№ N * UF + Rem + UF - 1 in the initial loop and may never happen.
  ...
} while (true);
exit:
  ...

This patch adds implementation for this pass for experimental use.

[mkazantsev]

Hi everyone,

Here is the idea of optimization we are currently missing, but unfortunately I could not find a really good place in any of the existing passes to integrate it into. The loop unrolling looks like a (more or less) proper place but not sure if it's where it truly belongs. Unrolling here is just a tool that we use to eliminate something which is (in most cases) an inductive check. So maybe it may be split between unrolling and IndVarSimplify.

Anyways, I'd appreciate any ideas and hints on where should we integrate this. As a fallback, we can always leave it as a separate pass until we find a place for it.

[reames]

Wrapping my head around this, just sharing some initial thoughts. Don't take anything here to be stronger than me thinking aloud.

The sub-piece of this which doesn't require a prologue loop looks like a natural extension to the existing loop unrolling. I think - but you should experimentally confirm - that existing runtime unrolling + indvars should prune all but one of the exits when the exiting lane is statically known. The missing piece would be to update the cost model. I'd had another idea for a change in the same area, you could look at my https://reviews.llvm.org/D91481 for ideas on how to possibly structure that.

That same sub-piece is also interesting in the loop vectorizer. If we know the exiting lane is zero, and that no control dependent potentially faulting operations are above said exit, we can widen the exit condition (as a simple scale check of lane 0) and vectorize the loop (if other exits meet the current conditions.)

Continuing to think about the vectorizer, a generalization of that may also be useful in that we can cheaply form a predicate mask for the whole loop. If we know lane X exits (and said exit dominates latch), then we can widen loads before said exit with a predicate mask which disables all lanes X+1 onward. We can do the same thing for multiple analyzeable loops (though we instead fold together the exit conditions), but this is interesting in allowing one unanalyzeable exit in the set.

Out of the above, the unrolling support seems easy to motivate, and not terrible invasive. The case of trip count being known TC mod UF == C for some C doesn't seem uncommon, and the costing checks should be cheap,

The more general transformation - which uses a prologue loop to ensure C == 0 for otherwise arbitrary TC - seems trickier. I really like the power, but we don't have other cases where the unroller needs a preload right now. (I don't think?) If we could find other cases which motivate a preloop and the costing thereof, having this in the unroller (as an alternative to peeling) seems reasonable. There's a bunch of code structure pieces - we really need this well abstracted, generic, and tested - but we can return to the details later.

I'm also hesitant about how to handle the case of multiple exits which have computable exit lanes C, and C2, but where C != C2. (E.g. exit 0 might exit on lane 1, exit 1 might exit on lane 2). Note that C1 and C2 in this case aren't known until runtime, so we can't tell exit 2 is dead. Figuring out something for the multiple exit case seems worthwhile, and needs more thought.

It seems like we might be able to adjust the trip count of the preloop to the minimum of the required rotation for the two exits, but that needs a bit more thought to confirm there's not some cornercase there.

Again, interesting, but a few additional moving parts. I'd probably start with the first sub-case costing changes in the unroller, get that worked through and enabled, then return to the second case.

Mostly for my own sanity later, I believe the costing code for this should end up as simple as:
auto *EC = SE->getExitCount(L, ExitingBlock);
if (!isa<SCEVUnknown>(EC)) {

// get TC from EC
auto *Rem = SE->getURemExpr(TC, UF as SCEVConstant);
if (isa<SCEVConstant>(Rem)) {
  // discount cost of exit by (UF-1)/UF
}

}

[mkazantsev]

To be merged into Loop Unroll.

[mkazantsev]

I have no plans to enable this, anyone who cares feel free to take over.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// Update no-wrap flags of an AddRec. This may drop the cached info about
   /// this AddRec (such as range info) in case if new flags may potentially
   /// sharpen it.
   void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags);
 
   /// Try to apply information from loop guards for \p L to \p Expr.
   const SCEV *applyLoopGuards(const SCEV *Expr, const Loop *L);
 
+  /// Test whether the condition described by Pred, LHS, and RHS is true
+  /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
+  /// true in given Context. If Context is nullptr, then the found predicate is
+  /// true everywhere.
+  bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
+                     ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
+                     const SCEV *FoundRHS,
+                     const Instruction *Context = nullptr);
+
 private:
   /// A CallbackVH to arrange for ScalarEvolution to be notified whenever a
   /// Value is deleted.
   class SCEVCallbackVH final : public CallbackVH {
     ScalarEvolution *SE;
 
     void deleted() override;
     void allUsesReplacedWith(Value *New) override;
private:
   /// everywhere. LHS and FoundLHS must have same type width.
   bool isImpliedCondBalancedTypes(ICmpInst::Predicate Pred, const SCEV *LHS,
                                   const SCEV *RHS,
                                   ICmpInst::Predicate FoundPred,
                                   const SCEV *FoundLHS, const SCEV *FoundRHS,
                                   const Instruction *Context);
 
   /// Test whether the condition described by Pred, LHS, and RHS is true
-  /// whenever the condition described by FoundPred, FoundLHS, FoundRHS is
-  /// true in given Context. If Context is nullptr, then the found predicate is
-  /// true everywhere.
-  bool isImpliedCond(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS,
-                     ICmpInst::Predicate FoundPred, const SCEV *FoundLHS,
-                     const SCEV *FoundRHS,
-                     const Instruction *Context = nullptr);
-
-  /// Test whether the condition described by Pred, LHS, and RHS is true
   /// whenever the condition described by Pred, FoundLHS, and FoundRHS is
   /// true in given Context. If Context is nullptr, then the found predicate is
   /// true everywhere.
   bool isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS,
                              const SCEV *RHS, const SCEV *FoundLHS,
                              const SCEV *FoundRHS,
                              const Instruction *Context = nullptr);
 

llvm/include/llvm/Transforms/Scalar/InductiveUnrolling.h

+#ifndef LLVM_TRANSFORMS_SCALAR_INDUCTIVEUNROLLING_H
+#define LLVM_TRANSFORMS_SCALAR_INDUCTIVEUNROLLING_H
+
+#include "llvm/Analysis/LoopAnalysisManager.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class Loop;
+class LPMUpdater;
+
+class InductiveUnrollingPass : public PassInfoMixin<InductiveUnrollingPass> {
+public:
+  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
+                        LoopStandardAnalysisResults &AR, LPMUpdater &U);
+};
+
+
+}
+
+#endif // LLVM_TRANSFORMS_SCALAR_INDUCTIVEUNROLLING_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/DivRemPairs.h"
 #include "llvm/Transforms/Scalar/EarlyCSE.h"
 #include "llvm/Transforms/Scalar/Float2Int.h"
 #include "llvm/Transforms/Scalar/GVN.h"
 #include "llvm/Transforms/Scalar/GuardWidening.h"
 #include "llvm/Transforms/Scalar/IVUsersPrinter.h"
 #include "llvm/Transforms/Scalar/IndVarSimplify.h"
 #include "llvm/Transforms/Scalar/InductiveRangeCheckElimination.h"
+#include "llvm/Transforms/Scalar/InductiveUnrolling.h"
 #include "llvm/Transforms/Scalar/InferAddressSpaces.h"
 #include "llvm/Transforms/Scalar/InstSimplifyPass.h"
 #include "llvm/Transforms/Scalar/JumpThreading.h"
 #include "llvm/Transforms/Scalar/LICM.h"
 #include "llvm/Transforms/Scalar/LoopAccessAnalysisPrinter.h"
 #include "llvm/Transforms/Scalar/LoopDataPrefetch.h"
 #include "llvm/Transforms/Scalar/LoopDeletion.h"
 #include "llvm/Transforms/Scalar/LoopDistribute.h"

llvm/lib/Passes/PassRegistry.def

 LOOP_PASS("loop-interchange", LoopInterchangePass())
 LOOP_PASS("loop-rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))
 LOOP_PASS("loop-deletion", LoopDeletionPass())
 LOOP_PASS("loop-simplifycfg", LoopSimplifyCFGPass())
 LOOP_PASS("loop-reduce", LoopStrengthReducePass())
 LOOP_PASS("indvars", IndVarSimplifyPass())
+LOOP_PASS("inductive-unroll", InductiveUnrollingPass())
 LOOP_PASS("loop-unroll-full", LoopFullUnrollPass())
 LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs()))
 LOOP_PASS("print<ddg>", DDGAnalysisPrinterPass(dbgs()))
 LOOP_PASS("print<iv-users>", IVUsersPrinterPass(dbgs()))
 LOOP_PASS("print<loopnest>", LoopNestPrinterPass(dbgs()))
 LOOP_PASS("print<loop-cache-cost>", LoopCachePrinterPass(dbgs()))
 LOOP_PASS("loop-predication", LoopPredicationPass())
 LOOP_PASS("guard-widening", GuardWideningPass())

llvm/lib/Transforms/Scalar/CMakeLists.txt

add_llvm_component_library(LLVMScalarOpts
   FlattenCFGPass.cpp
   Float2Int.cpp
   GuardWidening.cpp
   GVN.cpp
   GVNHoist.cpp
   GVNSink.cpp
   IVUsersPrinter.cpp
   InductiveRangeCheckElimination.cpp
+  InductiveUnrolling.cpp
   IndVarSimplify.cpp
   InferAddressSpaces.cpp
   InstSimplifyPass.cpp
   JumpThreading.cpp
   LICM.cpp
   LoopAccessAnalysisPrinter.cpp
   LoopSink.cpp
   LoopDeletion.cpp

llvm/lib/Transforms/Scalar/InductiveUnrolling.cpp

+#include "llvm/Transforms/Scalar/InductiveUnrolling.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/UnrollLoop.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "inductive-unroll"
+
+struct InductiveCheck {
+  InductiveCheck(BranchInst *Br, ICmpInst::Predicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS) : Br(Br), Pred(Pred), LHS(LHS), RHS(RHS) {}
+  BranchInst *Br;
+  ICmpInst::Predicate Pred;
+  const SCEVAddRecExpr *LHS;
+  const SCEV *RHS;
+};
+
+bool skipLoop(const Loop &L, ScalarEvolution &SE) {
+  if (!L.isInnermost())
+    return true;
+  if (!L.getLoopLatch() || !L.getLoopPreheader())
+    return true;
+  auto *ExitCount = SE.getBackedgeTakenCount(&L);
+  if (isa<SCEVUnknown>(ExitCount))
+    return true;
+  // TODO: support switches.
+  for (auto *BB : L.getBlocks())
+    if (!isa<BranchInst>(BB->getTerminator()))
+      return true;
+  return false;
+}
+
+bool collectCandidates(SmallVectorImpl<InductiveCheck> &Checks, Loop &L, ScalarEvolution &SE, DominatorTree &DT) {
+  assert(Checks.empty() && "Supposed to be an empty vector!");
+  if (!L.isInnermost())
+    return false;
+  BasicBlock *Latch = L.getLoopLatch();
+  assert(Latch && "Should have a latch!");
+
+  for (BasicBlock *BB : L.getBlocks()) {
+    if (!DT.dominates(BB, Latch))
+      continue;
+    using namespace PatternMatch;
+    ICmpInst::Predicate Pred;
+    Value *LHS, *RHS;
+    if (!match(BB->getTerminator(), m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), m_BasicBlock(), m_BasicBlock())))
+      continue;
+    // TODO: Support case with inductive RHS.
+    auto *LHSS = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(LHS));
+    if (!LHSS || !LHSS->isAffine() || LHSS->getLoop() != &L)
+      continue;
+    auto *RHSS = SE.getSCEV(RHS);
+    if (!SE.isAvailableAtLoopEntry(RHSS, &L))
+      continue;
+    const SCEV *Step = LHSS->getOperand(1);
+    const SCEV *Next = SE.getAddExpr(LHSS, Step);
+    auto *Br = cast<BranchInst>(BB->getTerminator());
+    if (!SE.isImpliedCond(Pred, LHSS, RHSS, Pred, Next, RHSS, Br))
+      continue;
+    Checks.push_back(InductiveCheck(Br, Pred, LHSS, RHSS));
+  }
+  return !Checks.empty();
+}
+
+static void cloneLoop(SmallVectorImpl<InductiveCheck> &Checks, Loop &L, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, AssumptionCache &AC, const TargetTransformInfo &TTI) {
+  SmallVector<BasicBlock *, 4> NewBlocks;
+  DenseMap<BasicBlock *, BasicBlock *> BlockMap;
+  ValueToValueMapTy VMap;
+
+  LoopBlocksRPO RPOT(&L);
+  RPOT.perform(&LI);
+  for (auto *BB : RPOT) {
+    auto *NewBB = CloneBasicBlock(BB, VMap, ".fallback", BB->getParent());
+    BlockMap[BB] = NewBB;
+    NewBlocks.push_back(NewBB);
+  }
+
+  // Add new inputs to exit blocks.
+  SmallVector <BasicBlock *, 4> ExitBlocks;
+  L.getExitBlocks(ExitBlocks);
+  for (auto *ExitBB : ExitBlocks) {
+    SmallVector <BasicBlock *, 4> Preds;
+    for (auto *Pred : predecessors(ExitBB))
+      Preds.push_back(Pred);
+    for (auto *Pred : Preds) {
+      if (!L.contains(Pred))
+        continue;      
+      for (auto &Insn : *ExitBB) {
+        auto *PN = dyn_cast<PHINode>(&Insn);
+        if (!PN) break;
+        Value *V = PN->getIncomingValueForBlock(Pred);
+        if (VMap.count(V))
+          V = VMap[V];
+        PN->addIncoming(V, BlockMap[Pred]);
+      }
+    }
+  }
+
+  // Fixup in-loop blocks.
+  for (auto *BB : NewBlocks) {
+    auto *BI = cast<BranchInst>(BB->getTerminator());
+    for (size_t I = 0; I < BI->getNumSuccessors(); I++) {
+      auto *Succ = BI->getSuccessor(I);
+      if (L.contains(Succ))
+        // For loop blocks, bind the successors.
+        BI->setSuccessor(I, BlockMap[Succ]);
+    }
+
+    for (auto &Insn : *BB)
+      for (size_t I = 0; I < Insn.getNumOperands(); I++)
+        if (VMap.count(Insn.getOperand(I)))
+          Insn.setOperand(I, VMap[Insn.getOperand(I)]);
+  }
+
+  // Channel the preheader.
+  auto *Preheader = L.getLoopPreheader();
+  Function *F = Preheader->getParent();
+  auto &Context = Preheader->getContext();
+  BasicBlock *NewPreheader = BasicBlock::Create(Context, "preheader.fallback", F);
+  IRBuilder<> Builder(NewPreheader);
+  BasicBlock *NewHeader = BlockMap[L.getHeader()];
+
+  for (auto &Check : Checks) {
+    auto *Br = Check.Br;
+    size_t ExitIndex = L.contains(Br->getSuccessor(0)) ? 1 : 0;
+    Br->setSuccessor(ExitIndex, NewPreheader);
+  }
+  for (auto &Insn : *L.getHeader()) {
+    auto *PN = dyn_cast<PHINode>(&Insn);
+    if (!PN) break;
+    auto *NewPN = cast<PHINode>(VMap[PN]);
+    for (size_t I = 0; I < NewPN->getNumIncomingValues(); I++)
+      if (NewPN->getIncomingBlock(I) == Preheader) {
+        auto *LCSSA = Builder.CreatePHI(PN->getType(), Checks.size(), PN->getName() + ".lcssa");
+        for (auto &Check : Checks) {
+          auto *Br = Check.Br;
+          LCSSA->addIncoming(PN, Br->getParent());
+        }
+        NewPN->setIncomingValue(I, LCSSA);
+        NewPN->setIncomingBlock(I, NewPreheader);
+        break;
+      }
+  }
+
+  Builder.CreateBr(NewHeader);
+  DT.recalculate(*F);
+  assert(DT.verify() && "Bad dom tree!");
+  assert(L.isLCSSAForm(DT) && "LCSSA form broken");
+}
+
+static bool removeChecks(Loop &L, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT, AssumptionCache &AC, const TargetTransformInfo &TTI) {
+  if (skipLoop(L, SE))
+    return false;
+  SmallVector<InductiveCheck, 4> Checks;
+  if (!collectCandidates(Checks, L, SE, DT))
+    return false;
+  cloneLoop(Checks, L, LI, SE, DT, AC, TTI);
+
+  const size_t UnrollFactor = 4;
+  UnrollLoopOptions ULO;
+  ULO.Count = UnrollFactor;
+  ULO.TripCount = 0;
+  ULO.Force = true;
+  ULO.AllowRuntime = true;
+  ULO.AllowExpensiveTripCount = true;
+  ULO.PreserveCondBr = true;
+  ULO.PreserveOnlyFirst = false;
+  ULO.TripMultiple = 1;
+  ULO.PeelCount = 0;
+  ULO.UnrollRemainder = false;
+  ULO.ForgetAllSCEV = true;
+
+//  UnrollLoop(&L, ULO, &LI, &SE, &DT, &AC, &TTI, /*OptimizationRemarkEmitter*/ nullptr, /*PreserveLCSSA*/ true);
+
+  return false;
+}
+
+PreservedAnalyses InductiveUnrollingPass::run(Loop &L, LoopAnalysisManager &AM,
+                                          LoopStandardAnalysisResults &AR,
+                                          LPMUpdater &LU) {
+  if (removeChecks(L, AR.LI, AR.SE, AR.DT, AR.AC, AR.TTI))
+    return PreservedAnalyses::none();
+  return PreservedAnalyses::all();
+}

llvm/test/Transforms/InductiveUnroll/motivation.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=inductive-unroll %s | FileCheck %s
+
+target datalayout = "n8:16:32:64"
+
+define i32 @test_01(i32 %end, i32 %len) {
+; CHECK-LABEL: @test_01(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[RC:%.*]] = icmp slt i32 [[IV]], [[LEN:%.*]]
+; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[PREHEADER_FALLBACK:%.*]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
+; CHECK-NEXT:    [[END_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[END:%.*]]
+; CHECK-NEXT:    br i1 [[END_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK:       done:
+; CHECK-NEXT:    [[IV_NEXT_LCSSA:%.*]] = phi i32 [ [[IV_NEXT]], [[BACKEDGE]] ], [ [[IV_NEXT_FALLBACK:%.*]], [[BACKEDGE_FALLBACK:%.*]] ]
+; CHECK-NEXT:    ret i32 [[IV_NEXT_LCSSA]]
+; CHECK:       failure:
+; CHECK-NEXT:    unreachable
+; CHECK:       loop.fallback:
+; CHECK-NEXT:    [[IV_FALLBACK:%.*]] = phi i32 [ [[IV_LCSSA:%.*]], [[PREHEADER_FALLBACK]] ], [ [[IV_NEXT_FALLBACK]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[RC_FALLBACK:%.*]] = icmp slt i32 [[IV_FALLBACK]], [[LEN]]
+; CHECK-NEXT:    br i1 [[RC_FALLBACK]], label [[BACKEDGE_FALLBACK]], label [[FAILURE:%.*]]
+; CHECK:       backedge.fallback:
+; CHECK-NEXT:    [[IV_NEXT_FALLBACK]] = add nsw i32 [[IV_FALLBACK]], 1
+; CHECK-NEXT:    [[END_COND_FALLBACK:%.*]] = icmp slt i32 [[IV_NEXT_FALLBACK]], [[END]]
+; CHECK-NEXT:    br i1 [[END_COND_FALLBACK]], label [[LOOP_FALLBACK:%.*]], label [[DONE]]
+; CHECK:       preheader.fallback:
+; CHECK-NEXT:    [[IV_LCSSA]] = phi i32 [ [[IV]], [[LOOP]] ]
+; CHECK-NEXT:    br label [[LOOP_FALLBACK]]
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %backedge, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %rc = icmp slt i32 %iv, %len
+  br i1 %rc, label %backedge, label %failure
+
+backedge:                                         ; preds = %loop
+  %iv.next = add nsw i32 %iv, 1
+  %end.cond = icmp slt i32 %iv.next, %end
+  br i1 %end.cond, label %loop, label %done
+
+done:                                             ; preds = %backedge
+  %iv.next.lcssa = phi i32 [ %iv.next, %backedge ]
+  ret i32 %iv.next.lcssa
+
+failure:                                          ; preds = %loop
+  unreachable
+}
+
+define i32 @test_02(i32 %end, i32 %len, i32* %p) {
+; CHECK-LABEL: @test_02(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[RC:%.*]] = icmp slt i32 [[IV]], [[LEN:%.*]]
+; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[PREHEADER_FALLBACK:%.*]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[ADDR:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i32 [[IV]]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[ADDR]], align 4
+; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[X]]
+; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], 1
+; CHECK-NEXT:    [[END_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[END:%.*]]
+; CHECK-NEXT:    br i1 [[END_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK:       done:
+; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ], [ [[SUM_NEXT_FALLBACK:%.*]], [[BACKEDGE_FALLBACK:%.*]] ]
+; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
+; CHECK:       failure:
+; CHECK-NEXT:    [[SUM_LCSSA:%.*]] = phi i32 [ [[SUM]], [[LOOP]] ], [ [[SUM_FALLBACK:%.*]], [[LOOP_FALLBACK:%.*]] ]
+; CHECK-NEXT:    ret i32 [[SUM_LCSSA]]
+; CHECK:       loop.fallback:
+; CHECK-NEXT:    [[IV_FALLBACK:%.*]] = phi i32 [ [[IV_LCSSA:%.*]], [[PREHEADER_FALLBACK]] ], [ [[IV_NEXT_FALLBACK:%.*]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[SUM_FALLBACK]] = phi i32 [ [[SUM_LCSSA1:%.*]], [[PREHEADER_FALLBACK]] ], [ [[SUM_NEXT_FALLBACK]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[RC_FALLBACK:%.*]] = icmp slt i32 [[IV_FALLBACK]], [[LEN]]
+; CHECK-NEXT:    br i1 [[RC_FALLBACK]], label [[BACKEDGE_FALLBACK]], label [[FAILURE:%.*]]
+; CHECK:       backedge.fallback:
+; CHECK-NEXT:    [[ADDR_FALLBACK:%.*]] = getelementptr inbounds i32, i32* [[P]], i32 [[IV_FALLBACK]]
+; CHECK-NEXT:    [[X_FALLBACK:%.*]] = load i32, i32* [[ADDR_FALLBACK]], align 4
+; CHECK-NEXT:    [[SUM_NEXT_FALLBACK]] = add i32 [[SUM_FALLBACK]], [[X_FALLBACK]]
+; CHECK-NEXT:    [[IV_NEXT_FALLBACK]] = add nsw i32 [[IV_FALLBACK]], 1
+; CHECK-NEXT:    [[END_COND_FALLBACK:%.*]] = icmp slt i32 [[IV_NEXT_FALLBACK]], [[END]]
+; CHECK-NEXT:    br i1 [[END_COND_FALLBACK]], label [[LOOP_FALLBACK]], label [[DONE]]
+; CHECK:       preheader.fallback:
+; CHECK-NEXT:    [[IV_LCSSA]] = phi i32 [ [[IV]], [[LOOP]] ]
+; CHECK-NEXT:    [[SUM_LCSSA1]] = phi i32 [ [[SUM]], [[LOOP]] ]
+; CHECK-NEXT:    br label [[LOOP_FALLBACK]]
+;
+entry:
+  br label %loop
+
+loop:                                             ; preds = %backedge, %entry
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %sum = phi i32 [0, %entry], [%sum.next, %backedge]
+  %rc = icmp slt i32 %iv, %len
+  br i1 %rc, label %backedge, label %failure
+
+backedge:                                         ; preds = %loop
+  %addr = getelementptr inbounds i32, i32* %p, i32 %iv
+  %x = load i32, i32* %addr
+  %sum.next = add i32 %sum, %x
+  %iv.next = add nsw i32 %iv, 1
+  %end.cond = icmp slt i32 %iv.next, %end
+  br i1 %end.cond, label %loop, label %done
+
+done:                                             ; preds = %backedge
+  %sum.next.lcssa = phi i32 [%sum.next, %backedge ]
+  ret i32 %sum.next.lcssa
+
+failure:                                          ; preds = %loop
+  %sum.lcssa = phi i32 [%sum, %loop ]
+  ret i32 %sum.lcssa
+}