[LoopSimplifyCFG] Delete dead in-loop blocks

[mkazantsev]

Summary

This patch teaches LoopSimplifyCFG to delete loop blocks that have
become unreachable after terminator folding has been done.

[mkazantsev]

Needs rebase.

[mkazantsev]

Rebased.

[mkazantsev]

Rebased

[anna]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

230

Looking at how DeadLoopBlocks get populated, these contain blocks within sub-loops as well.

So, there are 2 ways a subloop can become dead (either properly nested loop or a sibling loop). BB here belongs to a subloop and is:

1. header of that loop, which is the case you've handled here, i.e. that loop is removed from LI.
2. latch of that loop, which I don't see being handled. Once latch is removed, that subloop is no longer a loop either.

233

So, this removes the dead block and updates DT.
However, what about this case:

deadblock:
  br anotherblock:

anotherblock:
  <no phis, so we're guaranteed there's exactly one pred, which is deadblock>

DeleteDeadBlock does not recursively remove dead blocks. It handles the case where: dead block is *one of the predecessors* of anotherblock - see BasicBlock::removePredecessor.

I don't think DeadLoopBlocks contains anotherblock, since it became dead/unreachable when deadblock is dead.

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

230

When collecting fold candidates, we *only* collect candidates that immediately belong to the current loop. Therefore, we cannot modify inner loop's backedge while processing outer loop, assuming that we should have handled it while handling the inner loop.

233

DeadLoopBlocks must contain it by construction, otherwise it's a bug.
I'll add tests on that.

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

233

Actually we already test this in tests dead_block_propogate_test_branch_loop. In this test, block dead is dead because its predecessor goes to it by false condition, and dummy is dead because dead is its only predecessor.

It is all handled by the algorithm that collects our block sets: it knows what blocks will be dead after *all* folding will be done. It knows it all in advance.

[mkazantsev]

Rebased.

[fedor.sergeev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

221

Dont you want to add an assert here on

BlocksInLoopAfterFolding + DeadLoopBlocks <= NumBlocks ?

you seem to be relying on that invariant later on (when comparing this sum with numblocks for equality).

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

221

Well, by construction BlocksInLoopAfterFolding is a subset of LiveLoopBlocks (see IsEdgeLive), and we have this:

assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
       "Malformed block sets?");

Do you really think that what you propose is needed?

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

221

I've commited rL347458, along with the assert in my comment above they ensure what you need.

[anna]

There's an LCSSA not being preserved bug in the original landed change (@dmgreen added the test case). As part of fixing it, pls add the following options to your RUN command in the test "-verify-loop-info -verify-dom-info -verify-loop-lcssa". This will make sure all forms of verification are checked.

[mkazantsev]

Verification flags added at rL347483

[mkazantsev]

Underlying bug fixed, pass re-enabled and I have no failure reports for couple of days; I think we can go ahead and review this.

[mkazantsev]

Me bad, it seems that some tests from https://bugs.llvm.org/show_bug.cgi?id=39783 are still failing.

[mkazantsev]

Hold it until this bug is fixed.

[mkazantsev]

It will need a MemorySSA update when we delete blocks.

[mkazantsev]

Rebased, added removal of blocks from MSSA.

[anna]

Pls add -verify-memoryssa to the RUN command as well, now that MSSA is getting updated.
Comment inline.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

233

yes, I see that. thanks for the clarification.

361

Shouldn't we check here that L is still alive before calling mergeBlocksIntoPredecessors? When header is removed from the loop, the loop is removed from LI and no longer a loop (line 248).
If the case of the current loop being deleted is not handled in this patch, pls update the patch summary to state that.

... Ah, I see the deleteCurrentLoop early return at start of analyze().

Could you please add an assert like this before deleting the loop at line 248:

if (LI.isLoopHeader(BB)) {
    assert(L != LI.getLoopFor(BB) && "should not be current loop!");  
    LI.erase(LI.getLoopFor(BB));
}

[mkazantsev]

There is already a mode with memorySSA being constructed and verified in constant-fold-branch.ll:

; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s

[mkazantsev]

Added asserts that we do not delete current loop and its header while dealing with dead blocks.

[anna]

LGTM. Thanks for working through the revisions.

[mkazantsev]

Patch has been reverted, likely because it triggered a bug fixed by D55357 (underlying bug, not directly connected to this patch). Waiting for confirmation, if so, I will recommit it after the fix is merged.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-simplifycfg"
 
 STATISTIC(NumTerminatorsFolded,
           "Number of terminators folded to unconditional branches");
+STATISTIC(NumLoopBlocksDeleted,
+          "Number of loop blocks deleted");
 
 /// If \p BB has multiple successors, but only one of them can be reached from
 /// this block in runtime, return this successor. Otherwise, return nullptr.
 static BasicBlock *getOnlyLiveSuccessor(BasicBlock *BB) {
   Instruction *TI = BB->getTerminator();
   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
     if (BI->isUnconditional())
       return nullptr;
if (LoopIsLive) {
         if (BlockIsInLoop(BB))
           BlocksInLoopAfterFolding.insert(BB);
       }
 
       // Sanity check: header must be in loop.
       assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
              "Header not in loop?");
     }
   }
 
+  /// Delete loop blocks that have become unreachable after folding. Make all
+  /// relevant updates to DT and LI.
+  void deleteDeadLoopBlocks() {
+    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+    for (auto *BB : DeadLoopBlocks) {
+      LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
+                        << "\n");
+      if (LI.isLoopHeader(BB))
+        LI.erase(LI.getLoopFor(BB));
+      LI.removeBlock(BB);
+      DeleteDeadBlock(BB, &DTU);
+      ++NumLoopBlocksDeleted;
+    }
+  }
+
   /// Constant-fold terminators of blocks acculumated in FoldCandidates into the
   /// unconditional branches.
   void foldTerminators() {
     DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
 
     for (BasicBlock *BB : FoldCandidates) {
       assert(LI.getLoopFor(BB) == &L && "Should be a loop block!");
       BasicBlock *TheOnlySucc = getOnlyLiveSuccessor(BB);

 public:
   ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT)
       : L(L), LI(LI), DT(DT) {
     analyze();
   }
   bool run() {
     assert(L.getLoopLatch() && "Should be single latch!");
 
-    // TODO: Support deletion of dead loop blocks.
-    if (!DeadLoopBlocks.empty())
-      return false;
-
     // TODO: Support dead loop exits.
     if (!DeadExitBlocks.empty())
       return false;
 
     // TODO: Support deletion of the current loop.
     if (!LoopIsLive)
       return false;
 
     // TODO: Support blocks that are not dead, but also not in loop after the
     // folding.
-    if (BlocksInLoopAfterFolding.size() != L.getNumBlocks())
+    if (BlocksInLoopAfterFolding.size() + DeadLoopBlocks.size() !=
+        L.getNumBlocks())
       return false;
 
     // Nothing to constant-fold.
     if (FoldCandidates.empty())
       return false;
 
     // Dump analysis results.
     LLVM_DEBUG(dump());
 
     // Make the actual transforms.
     foldTerminators();
 
+    deleteDeadLoopBlocks();
+
     return true;
   }
 };
 
 /// Turn branches and switches with known constant conditions into unconditional
 /// branches.
 static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI) {
   // To keep things simple, only process loops with single latch. We

 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
                             ScalarEvolution &SE, MemorySSAUpdater *MSSAU) {
   bool Changed = false;
 
   // Constant-fold terminators with known constant conditions.
   Changed |= constantFoldTerminators(L, DT, LI);
 
   // Eliminate unconditional branches by merging blocks into their predecessors.
   Changed |= mergeBlocksIntoPredecessors(L, DT, LI, MSSAU);
 
   if (Changed)
     SE.forgetTopmostLoop(&L);
 
   return Changed;
 }
 
 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,

test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll

 }
 
 ; Check that we can eliminate a triangle.
 define i32 @dead_block_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_block_test_branch_loop(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]]
-; CHECK:       dead:
-; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
-; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   br i1 true, label %backedge, label %dead

 }
 
 ; Check that we can eliminate dead branches of a switch.
 define i32 @dead_block_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_block_test_switch_loop(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    switch i32 1, label [[DEAD:%.*]] [
-; CHECK-NEXT:    i32 0, label [[DEAD]]
-; CHECK-NEXT:    i32 1, label [[BACKEDGE]]
-; CHECK-NEXT:    i32 2, label [[DEAD]]
-; CHECK-NEXT:    ]
-; CHECK:       dead:
-; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
-; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   switch i32 1, label %dead [i32 0, label %dead

 }
 
 ; Check that we can eliminate several dead blocks.
 define i32 @dead_block_propogate_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_block_propogate_test_branch_loop(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]]
-; CHECK:       dead:
-; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
-; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   br i1 true, label %backedge, label %dead

 }
 
 ; Check that we can eliminate several blocks while removing a switch.
 define i32 @dead_block_propogate_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_block_propogate_test_switch_loop(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    switch i32 1, label [[DEAD:%.*]] [
-; CHECK-NEXT:    i32 0, label [[DEAD]]
-; CHECK-NEXT:    i32 1, label [[BACKEDGE]]
-; CHECK-NEXT:    i32 2, label [[DEAD]]
-; CHECK-NEXT:    ]
-; CHECK:       dead:
-; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
-; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   switch i32 1, label %dead [i32 0, label %dead

 }
 
 ; Check that we can delete a dead inner loop entirely.
 define i32 @dead_sub_loop_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_sub_loop_test_branch_loop(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    br i1 true, label [[LIVE_PREHEADER:%.*]], label [[DEAD_PREHEADER:%.*]]
-; CHECK:       live_preheader:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[EXIT_A:%.*]] ]
 ; CHECK-NEXT:    br label [[LIVE_LOOP:%.*]]
 ; CHECK:       live_loop:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 0, [[LIVE_PREHEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ]
+; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 0, [[HEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ]
 ; CHECK-NEXT:    [[A_INC]] = add i32 [[A]], 1
 ; CHECK-NEXT:    [[CMP_A:%.*]] = icmp slt i32 [[A_INC]], [[END:%.*]]
-; CHECK-NEXT:    br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A]]
 ; CHECK:       exit.a:
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       dead_preheader:
-; CHECK-NEXT:    br label [[DEAD_LOOP:%.*]]
-; CHECK:       dead_loop:
-; CHECK-NEXT:    [[B:%.*]] = phi i32 [ 0, [[DEAD_PREHEADER]] ], [ [[B_INC:%.*]], [[DEAD_LOOP]] ]
-; CHECK-NEXT:    [[B_INC]] = add i32 [[B]], 1
-; CHECK-NEXT:    [[CMP_B:%.*]] = icmp slt i32 [[B_INC]], [[END]]
-; CHECK-NEXT:    br i1 [[CMP_B]], label [[DEAD_LOOP]], label [[EXIT_B:%.*]]
-; CHECK:       exit.b:
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[EXIT_A]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   br i1 true, label %live_preheader, label %dead_preheader
exit:
   ret i32 %i.inc
 }
 
 define i32 @dead_sub_loop_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_sub_loop_test_switch_loop(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    switch i32 1, label [[DEAD_PREHEADER:%.*]] [
-; CHECK-NEXT:    i32 0, label [[DEAD_PREHEADER]]
-; CHECK-NEXT:    i32 1, label [[LIVE_PREHEADER:%.*]]
-; CHECK-NEXT:    i32 2, label [[DEAD_PREHEADER]]
-; CHECK-NEXT:    ]
-; CHECK:       live_preheader:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[EXIT_A:%.*]] ]
 ; CHECK-NEXT:    br label [[LIVE_LOOP:%.*]]
 ; CHECK:       live_loop:
-; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 0, [[LIVE_PREHEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ]
+; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 0, [[HEADER]] ], [ [[A_INC:%.*]], [[LIVE_LOOP]] ]
 ; CHECK-NEXT:    [[A_INC]] = add i32 [[A]], 1
 ; CHECK-NEXT:    [[CMP_A:%.*]] = icmp slt i32 [[A_INC]], [[END:%.*]]
-; CHECK-NEXT:    br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A:%.*]]
+; CHECK-NEXT:    br i1 [[CMP_A]], label [[LIVE_LOOP]], label [[EXIT_A]]
 ; CHECK:       exit.a:
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       dead_preheader:
-; CHECK-NEXT:    br label [[DEAD_LOOP:%.*]]
-; CHECK:       dead_loop:
-; CHECK-NEXT:    [[B:%.*]] = phi i32 [ 0, [[DEAD_PREHEADER]] ], [ [[B_INC:%.*]], [[DEAD_LOOP]] ]
-; CHECK-NEXT:    [[B_INC]] = add i32 [[B]], 1
-; CHECK-NEXT:    [[CMP_B:%.*]] = icmp slt i32 [[B_INC]], [[END]]
-; CHECK-NEXT:    br i1 [[CMP_B]], label [[DEAD_LOOP]], label [[EXIT_B:%.*]]
-; CHECK:       exit.b:
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[EXIT_A]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   switch i32 1, label %dead_preheader [i32 0, label %dead_preheader

 define i32 @partial_sub_loop_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @partial_sub_loop_test_branch_loop(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 ; CHECK:       outer_header:
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]]
-; CHECK:       dead:
-; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
-; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END]]
 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 ;
 entry:

 define i32 @partial_sub_loop_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @partial_sub_loop_test_switch_loop(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 ; CHECK:       outer_header:
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
-; CHECK-NEXT:    switch i32 1, label [[DEAD:%.*]] [
-; CHECK-NEXT:    i32 0, label [[DEAD]]
-; CHECK-NEXT:    i32 1, label [[BACKEDGE]]
-; CHECK-NEXT:    i32 2, label [[DEAD]]
-; CHECK-NEXT:    ]
-; CHECK:       dead:
-; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
-; CHECK-NEXT:    br label [[BACKEDGE]]
-; CHECK:       backedge:
-; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
-; CHECK-NEXT:    [[I_INC]] = add i32 [[I_1]], 1
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[HEADER]], label [[OUTER_BACKEDGE]]
 ; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 ; CHECK-NEXT:    [[J_INC]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END]]
 ; CHECK-NEXT:    br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 ;
 entry: