[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

770

Nit: Add a message to the assert.

[fhahn]

llvm/lib/Transforms/Utils/LoopUtils.cpp

780

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

780

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 no parent
+/// loop and 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;
+
+  // For non-outermost loops, the tricky case is that we can drop blocks
+  // out of both inner and outer loops at the same time.  This results in
+  // new exiting block for the outer loop appearing, and possibly needing
+  // an lcssa phi inserted.  (See loop_nest_lcssa test case in zero-btc.ll)
+  // TODO: We can handle a bunch of cases here without much work, revisit.
+  if (!L->isOutermost())
+    return LoopDeletionResult::Unmodified;
+
+  breakLoopBackedge(L, DT, SE, LI, MSSA);
+  return LoopDeletionResult::Deleted;
+}
+
 /// Remove a loop if it is dead.
 ///
 /// A loop is considered dead either if it does not impact the observable
 /// behavior of the program other than finite running time, or if it is
 /// required to make progress by an attribute such as 'mustprogress' or
 /// 'llvm.loop.mustprogress' and does not make any. This may remove
 /// infinite loops that have been required to make progress.
 ///
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) {
+
+  assert(L->isOutermost() && "Can't yet preserve LCSSA for this case");
+  auto *Latch = L->getLoopLatch();
+  assert(Latch && "multiple latches not yet supported");
+  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/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 ]
   call void @sideeffect(i32 %and.lcssa)
   %inc12 = add nsw i32 %val, 1
   %tobool = icmp eq i32 %inc12, 0
   br i1 %tobool, label %for.cond14, label %for.body
 

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]], label [[EXIT:%.*]]
+; 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:%.*]] ], [ [[IV_INC:%.*]], [[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:    [[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-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:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ]
+; 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:    [[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-NEXT:    br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]
 ; CHECK:       latch:
-; CHECK-NEXT:    br label [[LOOP]]
+; 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:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ]
+; 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:    [[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-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 [[LOOP]], label [[EXIT]]
+; 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 ]

 ; 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 [[LOOP]], label [[EXIT]]
+; 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

 ; 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 [[LOOP]], label [[EXIT2:%.*]]
+; 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
 

 ; 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 [[LOOP]], label [[EXIT:%.*]]
+; 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
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
 }
+
+; Key point is that inner_latch drops out of the outer loop when
+; the inner loop is deleted, and thus the lcssa phi needs to be
+; in the inner_latch block to preserve LCSSA.  We either have to
+; insert the LCSSA phi, or not break the inner backedge.
+define void @loop_nest_lcssa() {
+; CHECK-LABEL: @loop_nest_lcssa(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 1, 2
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       outer_header:
+; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
+; CHECK:       inner_header:
+; CHECK-NEXT:    br i1 false, label [[INNER_LATCH:%.*]], label [[OUTER_LATCH:%.*]]
+; CHECK:       inner_latch:
+; CHECK-NEXT:    br i1 false, label [[INNER_HEADER]], label [[LOOPEXIT:%.*]]
+; CHECK:       outer_latch:
+; CHECK-NEXT:    br label [[OUTER_HEADER]]
+; CHECK:       loopexit:
+; CHECK-NEXT:    [[DOTLCSSA32:%.*]] = phi i32 [ [[TMP0]], [[INNER_LATCH]] ]
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br label %outer_header
+
+outer_header:
+  %0 = add i32 1, 2
+  br label %inner_header
+
+inner_header:
+  br i1 false, label %inner_latch, label %outer_latch
+
+inner_latch:
+  br i1 false, label %inner_header, label %loopexit
+
+outer_latch:
+  br label %outer_header
+
+loopexit:
+  %.lcssa32 = phi i32 [ %0, %inner_latch ]
+  unreachable
+}