[LoopDeletion] Break backedge of loops when known not taken

[reames]

Summary

This is an extension to LoopDeletion that came up recently in another review discussion (D93734).

The basic idea is that if SCEV can prove the backedge isn't taken, we can go ahead and get rid of the backedge (and thus the loop) while leaving the rest of the control in place. This nicely handles cases with dispatch between multiple exits and internal side effects.

I'd appreciate a careful review of the LoopInfo handling here. I tried to parallel the existing deleteDeadLoop handling, but this code has subtle invariants and stale comments. Definitely room for error.

[reames]

ping

[nikic]

Isn't this already covered by the zero exit count optimization in IndVars?

[jdoerfert]

LGTM, one nit. I haven't run it but it looks reasonable. Unclear if there is much we can do by staring at it longer.

llvm/lib/Transforms/Utils/LoopUtils.cpp

764

Nit: Add a message to the assert.

[fhahn]

llvm/lib/Transforms/Utils/LoopUtils.cpp

774

I realize this is similar to what is done in deleteDeadLoop, but MSSA is only passed so it can be kept up-to-date, right? Can we just pass a pointer to the updater instead (making the intended use more explicit and avoids a dynamic allocation here)

[reames]

In D93906#2476680, @nikic wrote:

Isn't this already covered by the zero exit count optimization in IndVars?

No. I believe you're referring to optimizeLoopExits. That does not modify the CFG, it just folds conditions to constants. This will specifically modify the CFG and remove the loop.

llvm/lib/Transforms/Utils/LoopUtils.cpp

774

Not quite sure I follow your request here. I'm happy to address this in a separate cleanup (if you clarify what you're looking for), but I'm going to land as is since the same pattern is already used in existing code.

[nikic]

In D93906#2476763, @reames wrote:

In D93906#2476680, @nikic wrote:

Isn't this already covered by the zero exit count optimization in IndVars?

No. I believe you're referring to optimizeLoopExits. That does not modify the CFG, it just folds conditions to constants. This will specifically modify the CFG and remove the loop.

Yes, that's the transform I had in mind. I see the difference now, but I'm not sure I understand the larger picture / motivation behind this. The true/false branches will get folded away by SimplifyCFG -- so is this a phase ordering problem where SimplifyCFG runs too late (if so, can we add a PhaseOrdering test)? Should we also try to fold away (to unreachable) dead exits, rather than just dead backedges?

[reames]

In D93906#2477485, @nikic wrote:

In D93906#2476763, @reames wrote:

In D93906#2476680, @nikic wrote:

Isn't this already covered by the zero exit count optimization in IndVars?

No. I believe you're referring to optimizeLoopExits. That does not modify the CFG, it just folds conditions to constants. This will specifically modify the CFG and remove the loop.

Yes, that's the transform I had in mind. I see the difference now, but I'm not sure I understand the larger picture / motivation behind this. The true/false branches will get folded away by SimplifyCFG -- so is this a phase ordering problem where SimplifyCFG runs too late (if so, can we add a PhaseOrdering test)? Should we also try to fold away (to unreachable) dead exits, rather than just dead backedges?

You can view this as a phase ordering issue, but really I see it as "this pass is supposed to delete dead loops" + "a case came up in discussion which we'd missed" + "easy no-cost fix".

The phase ordering is magnified by the fact that SimplifyCFG is not a loop pass and thus requires a DT/LI rebuild. (The in flight DT work for SimplifyCFG looks like it might help there.)

Also, JFYI, deleting dead exits is actually pretty non-trivial (while preserving loop info). See the code in SimplifyLoopCFG which tries. The basic problem is that sibling loops can become unreachable when removing any exit edge.

[reames]

Context: This patch was reverted following failures in stage2 builders (only). Still investigating root cause. Reproduction is a bit of a pain.

Rebasing over landed test file to simplify my life.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 ///
 /// This also updates the relevant analysis information in \p DT, \p SE, \p LI
 /// and \p MSSA if pointers to those are provided.
 /// It also updates the loop PM if an updater struct is provided.
 
 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
                     LoopInfo *LI, MemorySSA *MSSA = nullptr);
 
+/// Remove the backedge of the specified loop.  Handles loop nests and general
+/// loop structures subject to the precondition that the loop has a single
+/// latch block.  Preserves all listed analyses.
+void breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
+                       LoopInfo &LI, MemorySSA *MSSA);
+
 /// Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
 /// vector, loop exit blocks insertion point vector, PredIteratorCache,
 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
 /// of the loop and loop safety information as arguments.
 /// Diagnostics is emitted via \p ORE. It returns changed status.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
+
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-delete"
 
 STATISTIC(NumDeleted, "Number of loops deleted");
 
 enum class LoopDeletionResult {
   Unmodified,
   Modified,
   Deleted,
 };
 
+static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) {
+  if (A == LoopDeletionResult::Deleted || B == LoopDeletionResult::Deleted)
+    return LoopDeletionResult::Deleted;
+  if (A == LoopDeletionResult::Modified || B == LoopDeletionResult::Modified)
+    return LoopDeletionResult::Modified;
+  return LoopDeletionResult::Unmodified;
+}
+
 /// Determines if a loop is dead.
 ///
 /// This assumes that we've already checked for unique exit and exiting blocks,
 /// and that the code is in LCSSA form.
 static bool isLoopDead(Loop *L, ScalarEvolution &SE,
                        SmallVectorImpl<BasicBlock *> &ExitingBlocks,
                        BasicBlock *ExitBlock, bool &Changed,
                        BasicBlock *Preheader) {
if (Taken == Preheader)
       return false;
   }
   assert(!pred_empty(Preheader) &&
          "Preheader should have predecessors at this point!");
   // All the predecessors have the loop preheader as not-taken target.
   return true;
 }
 
+/// If we can prove the backedge is untaken, remove it.  This destroys the
+/// loop, but leaves the (now trivially loop invariant) control flow and
+/// side effects (if any) in place.
+static LoopDeletionResult
+breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
+                        LoopInfo &LI, MemorySSA *MSSA,
+                        OptimizationRemarkEmitter &ORE) {
+  assert(L->isLCSSAForm(DT) && "Expected LCSSA!");
+
+  if (!L->getLoopLatch())
+    return LoopDeletionResult::Unmodified;
+
+  auto *BTC = SE.getBackedgeTakenCount(L);
+  if (!BTC->isZero())
+    return LoopDeletionResult::Unmodified;
+
+  breakLoopBackedge(L, DT, SE, LI, MSSA);
+  return LoopDeletionResult::Deleted;
+}
+
 /// Remove a loop if it is dead.
 ///
 /// A loop is considered dead if it does not impact the observable behavior of
 /// the program other than finite running time. This never removes a loop that
 /// might be infinite (unless it is never executed), as doing so could change
 /// the halting/non-halting nature of a program.
 ///
 /// This entire process relies pretty heavily on LoopSimplify form and LCSSA in
static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
   }
   // We can't remove loops that contain subloops.  If the subloops were dead,
   // they would already have been removed in earlier executions of this pass.
   if (L->begin() != L->end()) {
     LLVM_DEBUG(dbgs() << "Loop contains subloops.\n");
     return LoopDeletionResult::Unmodified;
   }
 
-
   BasicBlock *ExitBlock = L->getUniqueExitBlock();
 
   if (ExitBlock && isLoopNeverExecuted(L)) {
     LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
     // We need to forget the loop before setting the incoming values of the exit
     // phis to undef, so we properly invalidate the SCEV expressions for those
     // phis.
     SE.forgetLoop(L);
PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM,
   LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
   LLVM_DEBUG(L.dump());
   std::string LoopName = std::string(L.getName());
   // For the new PM, we can't use OptimizationRemarkEmitter as an analysis
   // pass. Function analyses need to be preserved across loop transformations
   // but ORE cannot be preserved (see comment before the pass definition).
   OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
   auto Result = deleteLoopIfDead(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE);
+
+  // If we can prove the backedge isn't taken, just break it and be done.  This
+  // leaves the loop structure in place which means it can handle dispatching
+  // to the right exit based on whatever loop invariant structure remains.
+  if (Result != LoopDeletionResult::Deleted)
+    Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI,
+                                                   AR.MSSA, ORE));
+
   if (Result == LoopDeletionResult::Unmodified)
     return PreservedAnalyses::all();
 
   if (Result == LoopDeletionResult::Deleted)
     Updater.markLoopAsDeleted(L, LoopName);
 
   auto PA = getLoopPassPreservedAnalyses();
   if (AR.MSSA)
bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
   // but ORE cannot be preserved (see comment before the pass definition).
   OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
 
   LLVM_DEBUG(dbgs() << "Analyzing Loop for deletion: ");
   LLVM_DEBUG(L->dump());
 
   LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE);
 
+  // If we can prove the backedge isn't taken, just break it and be done.  This
+  // leaves the loop structure in place which means it can handle dispatching
+  // to the right exit based on whatever loop invariant structure remains.
+  if (Result != LoopDeletionResult::Deleted)
+    Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE));
+
   if (Result == LoopDeletionResult::Deleted)
     LPM.markLoopAsDeleted(*L);
 
   return Result != LoopDeletionResult::Unmodified;
 }

llvm/lib/Transforms/Utils/LoopUtils.cpp

if (Loop *ParentLoop = L->getParentLoop()) {
       Loop::iterator I = find(*LI, L);
       assert(I != LI->end() && "Couldn't find loop");
       LI->removeLoop(I);
     }
     LI->destroy(L);
   }
 }
 
+void llvm::breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
+                             LoopInfo &LI, MemorySSA *MSSA) {
+
+  auto *Latch = L->getLoopLatch();
+  assert(Latch);
+  auto *Header = L->getHeader();
+
+  SE.forgetLoop(L);
+
+  // Note: By splitting the backedge, and then explicitly making it unreachable
+  // we gracefully handle corner cases such as non-bottom tested loops and the
+  // like.  We also have the benefit of being able to reuse existing well tested
+  // code.  It might be worth special casing the common bottom tested case at
+  // some point to avoid code churn.
+
+  std::unique_ptr<MemorySSAUpdater> MSSAU;
+  if (MSSA)
+    MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
+
+  auto *BackedgeBB = SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
+
+  DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
+  (void)changeToUnreachable(BackedgeBB->getTerminator(), /*UseTrap*/false,
+                            /*PreserveLCSSA*/true, &DTU, MSSAU.get());
+
+  // Erase (and destroy) this loop instance.  Handles relinking sub-loops
+  // and blocks within the loop as needed.
+  LI.erase(L);
+}
+
+
 /// Checks if \p L has single exit through latch block except possibly
 /// "deoptimizing" exits. Returns branch instruction terminating the loop
 /// latch if above check is successful, nullptr otherwise.
 static BranchInst *getExpectedExitLoopLatchBranch(Loop *L) {
   BasicBlock *Latch = L->getLoopLatch();
   if (!Latch)
     return nullptr;
 

llvm/test/Transforms/IndVarSimplify/X86/pr45360.ll

 @e = dso_local global i32 0, align 4
 
 define dso_local i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I6:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[I24:%.*]] = load i32, i32* @b, align 4
 ; CHECK-NEXT:    [[D_PROMOTED9:%.*]] = load i32, i32* @d, align 4
-; CHECK-NEXT:    br label [[BB1:%.*]]
-; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB13_PREHEADER:%.*]]
+; CHECK:       bb13.preheader:
 ; CHECK-NEXT:    [[I8_LCSSA10:%.*]] = phi i32 [ [[D_PROMOTED9]], [[BB:%.*]] ], [ [[I8:%.*]], [[BB19_PREHEADER:%.*]] ]
 ; CHECK-NEXT:    [[I8]] = and i32 [[I8_LCSSA10]], [[I6]]
 ; CHECK-NEXT:    [[I21:%.*]] = icmp eq i32 [[I8]], 0
 ; CHECK-NEXT:    br i1 [[I21]], label [[BB13_PREHEADER_BB27_THREAD_SPLIT_CRIT_EDGE:%.*]], label [[BB19_PREHEADER]]
 ; CHECK:       bb19.preheader:
 ; CHECK-NEXT:    [[I26:%.*]] = urem i32 [[I24]], [[I8]]
 ; CHECK-NEXT:    store i32 [[I26]], i32* @e, align 4
 ; CHECK-NEXT:    [[I30_NOT:%.*]] = icmp eq i32 [[I26]], 0
-; CHECK-NEXT:    br i1 [[I30_NOT]], label [[BB32_LOOPEXIT:%.*]], label [[BB1]]
+; CHECK-NEXT:    br i1 [[I30_NOT]], label [[BB32_LOOPEXIT:%.*]], label [[BB13_PREHEADER]]
 ; CHECK:       bb13.preheader.bb27.thread.split_crit_edge:
 ; CHECK-NEXT:    store i32 -1, i32* @f, align 4
 ; CHECK-NEXT:    store i32 0, i32* @d, align 4
 ; CHECK-NEXT:    store i32 0, i32* @c, align 4
 ; CHECK-NEXT:    br label [[BB32:%.*]]
 ; CHECK:       bb32.loopexit:
 ; CHECK-NEXT:    store i32 -1, i32* @f, align 4
 ; CHECK-NEXT:    store i32 [[I8]], i32* @d, align 4

llvm/test/Transforms/IndVarSimplify/exit_value_test2.ll

while.end:                                        ; preds = %while.cond.while.end_crit_edge, %entry
   ret i32 %t4
 }
 
 define i32 @zero_backedge_count_test(i32 %unknown_init, i32* %unknown_mem) {
 ; CHECK-LABEL: @zero_backedge_count_test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[UNKNOWN_NEXT:%.*]] = load volatile i32, i32* [[UNKNOWN_MEM:%.*]]
-; CHECK-NEXT:    br i1 false, label [[LOOP]], label [[LEAVE:%.*]]
+; CHECK-NEXT:    [[UNKNOWN_NEXT:%.*]] = load volatile i32, i32* [[UNKNOWN_MEM:%.*]], align 4
+; CHECK-NEXT:    br i1 false, label [[LOOP_LOOP_CRIT_EDGE:%.*]], label [[LEAVE:%.*]]
+; CHECK:       loop.loop_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       leave:
 ; CHECK-NEXT:    ret i32 [[UNKNOWN_INIT:%.*]]
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry], [ %iv.inc, %loop ]

llvm/test/Transforms/LoopDeletion/update-scev.ll

for.body6:                                        ; preds = %for.body6, %for.body
   %conv7 = zext i1 %cmp to i32
   %add.i = add nsw i32 %conv7, %h.039
   %sext = shl i32 %add.i, 24
   %conv8 = ashr exact i32 %sext, 24
   %cmp9 = icmp eq i32 %conv8, %f.0
   %conv10 = zext i1 %cmp9 to i32
   %and = and i32 %conv10, %g.138
   %inc = add i32 %h.039, 1
-  br i1 undef, label %for.inc11, label %for.body6
+  %exit = icmp eq i32 %inc, 20000
+  br i1 %exit, label %for.inc11, label %for.body6
 
 for.inc11:                                        ; preds = %for.body6
   %and.lcssa = phi i32 [ %and, %for.body6 ]
   %inc12 = add nsw i32 %val, 1
   %tobool = icmp eq i32 %inc12, 0
   br i1 %tobool, label %for.cond14, label %for.body
 
 for.cond14:                                       ; preds = %for.cond14, %for.inc11

llvm/test/Transforms/LoopDeletion/zero-btc.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -loop-deletion -S | FileCheck %s
+
+@G = external global i32
+
+define void @test_trivial() {
+; CHECK-LABEL: @test_trivial(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    br i1 false, label [[LOOP_LOOP_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.loop_crit_edge:
+; CHECK-NEXT:    unreachable
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  store i32 0, i32* @G
+  br i1 false, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+
+define void @test_bottom_tested() {
+; CHECK-LABEL: @test_bottom_tested(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
+; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LOOP_LOOP_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
+; CHECK:       loop.loop_crit_edge:
+; CHECK-NEXT:    unreachable
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry], [ %iv.inc, %loop ]
+  store i32 0, i32* @G
+  %iv.inc = add i32 %iv, 1
+  %be_taken = icmp ne i32 %iv.inc, 1
+  br i1 %be_taken, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_early_exit() {
+; CHECK-LABEL: @test_early_exit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
+; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    br label [[LATCH_SPLIT:%.*]]
+; CHECK:       latch.split:
+; CHECK-NEXT:    unreachable
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
+  store i32 0, i32* @G
+  %iv.inc = add i32 %iv, 1
+  %be_taken = icmp ne i32 %iv.inc, 1
+  br i1 %be_taken, label %latch, label %exit
+latch:
+  br label %loop
+
+exit:
+  ret void
+}
+
+define void @test_multi_exit1() {
+; CHECK-LABEL: @test_multi_exit1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    [[IV_INC:%.*]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
+; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store i32 1, i32* @G, align 4
+; CHECK-NEXT:    [[COND2:%.*]] = icmp ult i32 [[IV_INC]], 30
+; CHECK-NEXT:    br i1 [[COND2]], label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT]]
+; CHECK:       latch.loop_crit_edge:
+; CHECK-NEXT:    unreachable
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
+  store i32 0, i32* @G
+  %iv.inc = add i32 %iv, 1
+  %be_taken = icmp ne i32 %iv.inc, 1
+  br i1 %be_taken, label %latch, label %exit
+latch:
+  store i32 1, i32* @G
+  %cond2 = icmp ult i32 %iv.inc, 30
+  br i1 %cond2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_multi_exit2() {
+; CHECK-LABEL: @test_multi_exit2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    br i1 true, label [[LATCH:%.*]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store i32 1, i32* @G, align 4
+; CHECK-NEXT:    br i1 false, label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT]]
+; CHECK:       latch.loop_crit_edge:
+; CHECK-NEXT:    unreachable
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  store i32 0, i32* @G
+  br i1 true, label %latch, label %exit
+latch:
+  store i32 1, i32* @G
+  br i1 false, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; TODO: SCEV seems not to recognize this as a zero btc loop
+define void @test_multi_exit3(i1 %cond1) {
+; CHECK-LABEL: @test_multi_exit3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LATCH]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store i32 1, i32* @G, align 4
+; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1
+; CHECK-NEXT:    br i1 [[BE_TAKEN]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]
+  store i32 0, i32* @G
+  br i1 %cond1, label %latch, label %exit
+latch:
+  store i32 1, i32* @G
+  %iv.inc = add i32 %iv, 1
+  %be_taken = icmp ne i32 %iv.inc, 1
+  br i1 %be_taken, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Subtle - This is either zero btc, or infinite, thus, can't break
+; backedge
+define void @test_multi_exit4(i1 %cond1, i1 %cond2) {
+; CHECK-LABEL: @test_multi_exit4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store i32 1, i32* @G, align 4
+; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  store i32 0, i32* @G
+  br i1 %cond1, label %latch, label %exit
+latch:
+  store i32 1, i32* @G
+  br i1 %cond2, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; A simple case with multiple exit blocks
+define void @test_multi_exit5() {
+; CHECK-LABEL: @test_multi_exit5(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    br i1 true, label [[LATCH:%.*]], label [[EXIT1:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    store i32 1, i32* @G, align 4
+; CHECK-NEXT:    br i1 false, label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT2:%.*]]
+; CHECK:       latch.loop_crit_edge:
+; CHECK-NEXT:    unreachable
+; CHECK:       exit1:
+; CHECK-NEXT:    ret void
+; CHECK:       exit2:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  store i32 0, i32* @G
+  br i1 true, label %latch, label %exit1
+latch:
+  store i32 1, i32* @G
+  br i1 false, label %loop, label %exit2
+
+exit1:
+  ret void
+exit2:
+  ret void
+}
+
+define void @test_live_inner() {
+; CHECK-LABEL: @test_live_inner(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    br label [[INNER:%.*]]
+; CHECK:       inner:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[LOOP]] ], [ [[IV_INC:%.*]], [[INNER]] ]
+; CHECK-NEXT:    store i32 [[IV]], i32* @G, align 4
+; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200
+; CHECK-NEXT:    br i1 [[CND]], label [[INNER]], label [[LATCH:%.*]]
+; CHECK:       latch:
+; CHECK-NEXT:    br i1 false, label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
+; CHECK:       latch.loop_crit_edge:
+; CHECK-NEXT:    unreachable
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  store i32 0, i32* @G
+  br label %inner
+
+inner:
+  %iv = phi i32 [0, %loop], [%iv.inc, %inner]
+  store i32 %iv, i32* @G
+  %iv.inc = add i32 %iv, 1
+  %cnd = icmp ult i32 %iv.inc, 200
+  br i1 %cnd, label %inner, label %latch
+
+latch:
+  br i1 false, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_live_outer() {
+; CHECK-LABEL: @test_live_outer(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    br label [[INNER:%.*]]
+; CHECK:       inner:
+; CHECK-NEXT:    store i32 0, i32* @G, align 4
+; CHECK-NEXT:    br i1 false, label [[INNER_INNER_CRIT_EDGE:%.*]], label [[LATCH]]
+; CHECK:       inner.inner_crit_edge:
+; CHECK-NEXT:    unreachable
+; CHECK:       latch:
+; CHECK-NEXT:    store i32 [[IV]], i32* @G, align 4
+; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200
+; CHECK-NEXT:    br i1 [[CND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %entry], [%iv.inc, %latch]
+  br label %inner
+
+inner:
+  store i32 0, i32* @G
+  br i1 false, label %inner, label %latch
+
+latch:
+  store i32 %iv, i32* @G
+  %iv.inc = add i32 %iv, 1
+  %cnd = icmp ult i32 %iv.inc, 200
+  br i1 %cnd, label %loop, label %exit
+
+exit:
+  ret void
+}