[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

237 ↗

(On Diff #174730)

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.

240 ↗

(On Diff #174730)

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

237 ↗

(On Diff #174730)

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.

240 ↗

(On Diff #174730)

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

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

240 ↗

(On Diff #174730)

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

228 ↗

(On Diff #174872)

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

228 ↗

(On Diff #174872)

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

228 ↗

(On Diff #174872)

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

441 ↗

(On Diff #176080)

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));
}

240 ↗

(On Diff #174730)

yes, I see that. thanks for the clarification.

[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.

llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 
 #define DEBUG_TYPE "loop-simplifycfg"
 
 static cl::opt<bool> EnableTermFolding("enable-loop-simplifycfg-term-folding",
                                        cl::init(true));
 
 STATISTIC(NumTerminatorsFolded,
           "Number of terminators folded to unconditional branches");
+STATISTIC(NumLoopBlocksDeleted,
+          "Number of loop blocks deleted");
 
 /// If \p BB is a switch or a conditional branch, but only one of its successors
 /// 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())
void analyze() {
 
     // Sanity check: header must be in loop.
     assert(BlocksInLoopAfterFolding.count(L.getHeader()) &&
            "Header not in loop?");
     assert(BlocksInLoopAfterFolding.size() <= LiveLoopBlocks.size() &&
            "All blocks that stay in loop should be live!");
   }
 
+  /// 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);
+    if (MSSAU)
+      MSSAU->removeBlocks(DeadLoopBlocks);
+    for (auto *BB : DeadLoopBlocks) {
+      assert(BB != L.getHeader() &&
+             "Header of the current loop cannot be dead!");
+      LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
+                        << "\n");
+      if (LI.isLoopHeader(BB)) {
+        assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
+        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);
if (DeleteCurrentLoop) {
       LLVM_DEBUG(
           dbgs()
           << "Give up constant terminator folding in loop "
           << L.getHeader()->getName()
           << ": we don't currently support deletion of the current loop.\n");
       return false;
     }
 
-    // TODO: Support deletion of dead loop blocks.
-    if (!DeadLoopBlocks.empty()) {
-      LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
-                        << L.getHeader()->getName()
-                        << ": we don't currently"
-                           " support deletion of dead in-loop blocks.\n");
-      return false;
-    }
-
     // TODO: Support dead loop exits.
     if (!DeadExitBlocks.empty()) {
       LLVM_DEBUG(dbgs() << "Give up constant terminator folding in loop "
                         << L.getHeader()->getName()
                         << ": we don't currently support dead loop exits.\n");
       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()) {
       LLVM_DEBUG(
           dbgs() << "Give up constant terminator folding in loop "
                  << L.getHeader()->getName()
                  << ": we don't currently"
                     " support blocks that are not dead, but will stop "
                     "being a part of the loop after constant-folding.\n");
       return false;
     }
 
     // Dump analysis results.
     LLVM_DEBUG(dump());
 
     LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
                       << " terminators in loop " << L.getHeader()->getName()
                       << "\n");
 
     // Make the actual transforms.
     foldTerminators();
 
+    if (!DeadLoopBlocks.empty()) {
+      LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
+                    << " dead blocks in loop " << L.getHeader()->getName()
+                    << "\n");
+      deleteDeadLoopBlocks();
+    }
+
 #ifndef NDEBUG
     // Make sure that we have preserved all data structures after the transform.
     DT.verify();
     assert(DT.isReachableFromEntry(L.getHeader()));
     LI.verify(DT);
 #endif
 
     return true;

llvm/trunk/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: