[LoopSimplifyCFG] Delete dead exiting edges

[mkazantsev]

Summary

This patch teaches LoopSimplifyCFG to remove dead exiting edges
from loops.

[mkazantsev]

Needs rebase.

[mkazantsev]

Rebased, lifted limitation related to breaking connectivity between nested and parent loops.

[mkazantsev]

This might be buggy, I will add more tests and rebase it later.

[mkazantsev]

False alarm, seems OK. Rebased on new tests.

[fedor.sergeev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

261

need to have the label name matching the switch (new_preheader vs preheader-split)

267

%dead_exit_N ?

277

Stray comment?

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

109

We generate switches basing on this, and SmallPtrSet has a non-deterministic order. Need underlying NFC to make it a vector.

[mkazantsev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

109

rL347457

[mkazantsev]

Fixed messy comments, rebased on top of deterministic collection of exit blocks, tests updated accordingly.

[mkazantsev]

Underlying patch merged, opening for review.

[fedor.sergeev]

LGTM.

[fedor.sergeev]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

262

Minor nit - your current code splits preheader at terminator, so <preheader code> is left at preheader,
and preheader-split becomes just a block with a single branch and nothing else.
Please, correct the pseudo-code in comments here.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "loop-simplifycfg"
 
 STATISTIC(NumTerminatorsFolded,
           "Number of terminators folded to unconditional branches");
 STATISTIC(NumLoopBlocksDeleted,
           "Number of loop blocks deleted");
+STATISTIC(NumLoopExitsDeleted,
+          "Number of loop exiting edges 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())
private:
   // The blocks of the original loop that will become unreachable from entry
   // after the constant folding.
   SmallPtrSet<BasicBlock *, 8> DeadLoopBlocks;
   // The exits of the original loop that will still be reachable from entry
   // after the constant folding.
   SmallPtrSet<BasicBlock *, 8> LiveExitBlocks;
   // The exits of the original loop that will become unreachable from entry
   // after the constant folding.
   SmallVector<BasicBlock *, 8> DeadExitBlocks;
   // The blocks that will still be a part of the current loop after folding.
   SmallPtrSet<BasicBlock *, 8> BlocksInLoopAfterFolding;
   // The blocks that have terminators with constant condition that can be
   // folded. Note: fold candidates should be in L but not in any of its
   // subloops to avoid complex LI updates.
   SmallVector<BasicBlock *, 8> FoldCandidates;
 
   void dump() const {
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!");
   }
 
+  /// We need to preserve static reachibility of all loop exit blocks (this is)
+  /// required by loop pass manager. In order to do it, we make the following
+  /// trick:
+  ///
+  ///  preheader:
+  ///    <preheader code>
+  ///    br label %loop_header
+  ///
+  ///  loop_header:
+  ///    ...
+  ///    br i1 false, label %dead_exit, label %loop_block
+  ///    ...
+  ///
+  /// We cannot simply remove edge from the loop to dead exit because in this
+  /// case dead_exit (and its successors) may become unreachable. To avoid that,
+  /// we insert the following fictive preheader:
+  ///
+  ///  preheader:
+  ///    switch i32 0, label %preheader-split,
+  ///                  [i32 1, label %dead_exit_1],
+  ///                  [i32 2, label %dead_exit_2],
+  ///                  ...
+  ///                  [i32 N, label %dead_exit_N],
+  ///
+  ///  preheader-split:
+  ///    <preheader code>
+  ///    br label %loop_header
+  ///
+  ///  loop_header:
+  ///    ...
+  ///    br i1 false, label %dead_exit_N, label %loop_block
+  ///    ...
+  ///
+  /// Doing so, we preserve static reachibility of all dead exits and can later
+  /// remove edges from the loop to these blocks.
+  void handleDeadExits() {
+    // If no dead exits, nothing to do.
+    if (DeadExitBlocks.empty())
+      return;
+
+    // Construct split preheader and the dummy switch to thread edges from it to
+    // dead exits.
+    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+    BasicBlock *Preheader = L.getLoopPreheader();
+    BasicBlock *NewPreheader = Preheader->splitBasicBlock(
+        Preheader->getTerminator(),
+        Twine(Preheader->getName()).concat("-split"));
+    DTU.deleteEdge(Preheader, L.getHeader());
+    DTU.insertEdge(NewPreheader, L.getHeader());
+    DTU.insertEdge(Preheader, NewPreheader);
+    IRBuilder<> Builder(Preheader->getTerminator());
+    SwitchInst *DummySwitch =
+        Builder.CreateSwitch(Builder.getInt32(0), NewPreheader);
+    Preheader->getTerminator()->eraseFromParent();
+
+    unsigned DummyIdx = 1;
+    for (BasicBlock *BB : DeadExitBlocks) {
+      SmallVector<Instruction *, 4> DeadPhis;
+      for (auto &PN : BB->phis())
+        DeadPhis.push_back(&PN);
+
+      // Eliminate all Phis from dead exits.
+      for (Instruction *PN : DeadPhis) {
+        PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
+        PN->eraseFromParent();
+      }
+      assert(DummyIdx != 0 && "Too many dead exits!");
+      DummySwitch->addCase(Builder.getInt32(DummyIdx++), BB);
+      DTU.insertEdge(Preheader, BB);
+      ++NumLoopExitsDeleted;
+    }
+
+    assert(L.getLoopPreheader() == NewPreheader && "Malformed CFG?");
+    if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
+      OuterLoop->addBasicBlockToLoop(NewPreheader, LI);
+
+      // When we break dead edges, the outer loop may become unreachable from
+      // the current loop. We need to fix loop info accordingly. For this, we
+      // find the most nested loop that still contains L and remove L from all
+      // loops that are inside of it.
+      Loop *StillReachable = nullptr;
+      for (BasicBlock *BB : LiveExitBlocks) {
+        Loop *BBL = LI.getLoopFor(BB);
+        if (BBL && BBL->contains(L.getHeader()))
+          if (!StillReachable ||
+              BBL->getLoopDepth() > StillReachable->getLoopDepth())
+            StillReachable = BBL;
+      }
+
+      // Okay, our loop is no longer in the outer loop (and maybe not in some of
+      // its parents as well). Make the fixup.
+      if (StillReachable != OuterLoop) {
+        LI.changeLoopFor(NewPreheader, StillReachable);
+        for (Loop *NotContaining = OuterLoop; NotContaining != StillReachable;
+             NotContaining = NotContaining->getParentLoop()) {
+          NotContaining->removeBlockFromLoop(NewPreheader);
+          for (auto *BB : L.blocks())
+            NotContaining->removeBlockFromLoop(BB);
+        }
+        OuterLoop->removeChildLoop(&L);
+        if (StillReachable)
+          StillReachable->addChildLoop(&L);
+        else
+          LI.addTopLevelLoop(&L);
+      }
+    }
+  }
+
   /// 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))
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 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() + 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.
+    handleDeadExits();
     foldTerminators();
 
     if (!DeadLoopBlocks.empty()) {
       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
                     << " dead blocks in loop " << L.getHeader()->getName()
                     << "\n");
       deleteDeadLoopBlocks();
     }

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

exit:
   ret i32 %i.inc
 }
 
 ; Check that we preserve static reachibility of a dead exit block while deleting
 ; a branch.
 define i32 @dead_exit_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_exit_test_branch_loop(
 ; CHECK-NEXT:  preheader:
+; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[DEAD:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       preheader-split:
 ; 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-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[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_LOOPEXIT:%.*]]
 ; CHECK:       dead:
-; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[HEADER]] ]
 ; CHECK-NEXT:    br label [[DUMMY:%.*]]
 ; CHECK:       dummy:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
-; 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_LOOPEXIT:%.*]]
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I_LCSSA]], [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ]
+; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ undef, [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i32 [[I_1]]
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   br i1 true, label %backedge, label %dead
exit:
   ret i32 %i.1
 }
 
 ; Check that we preserve static reachibility of a dead exit block while deleting
 ; a switch.
 define i32 @dead_exit_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_exit_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:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[DEAD:%.*]]
 ; CHECK-NEXT:    i32 2, label [[DEAD]]
+; CHECK-NEXT:    i32 3, label [[DEAD]]
 ; CHECK-NEXT:    ]
+; CHECK:       preheader-split:
+; CHECK-NEXT:    br label [[HEADER:%.*]]
+; CHECK:       header:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[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_LOOPEXIT:%.*]]
 ; CHECK:       dead:
-; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I]], [[HEADER]] ], [ [[I]], [[HEADER]] ]
 ; CHECK-NEXT:    br label [[DUMMY:%.*]]
 ; CHECK:       dummy:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
-; 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_LOOPEXIT:%.*]]
 ; CHECK:       exit.loopexit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[HEADER]] ]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ [[I_LCSSA]], [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ]
+; CHECK-NEXT:    [[I_1:%.*]] = phi i32 [ undef, [[DUMMY]] ], [ [[I_INC_LCSSA]], [[EXIT_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i32 [[I_1]]
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   switch i32 1, label %dead [i32 0, label %dead
exit:
   ret i32 %i.inc
 }
 
 ; Check that we preserve static reachability of an exit block even if we prove
 ; that the loop is infinite. Branch case.
 define i32 @inf_loop_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @inf_loop_test_branch_loop(
 ; CHECK-NEXT:  preheader:
+; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[EXIT:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       preheader-split:
 ; 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_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
-; CHECK-NEXT:    br i1 true, label [[HEADER]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
-; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
+; CHECK-NEXT:    ret i32 undef
 ;
 preheader:
   br label %header
 
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   br i1 true, label %backedge, label %dead
 

 
 exit:
   ret i32 %i.inc
 }
 
 define i32 @inf_loop_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @inf_loop_test_switch_loop(
 ; CHECK-NEXT:  preheader:
+; CHECK-NEXT:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[EXIT:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       preheader-split:
 ; 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_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
-; CHECK-NEXT:    br i1 true, label [[HEADER]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
-; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
+; CHECK-NEXT:    ret i32 undef
 ;
 preheader:
   br label %header
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]
   switch i32 1, label %dead [i32 0, label %dead
   i32 1, label %backedge
   i32 2, label %dead]

 }
 
 define i32 @full_sub_loop_test_branch_loop_inverse_2(i32 %end) {
 ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_2(
 ; 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:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[OUTER_BACKEDGE]]
+; CHECK-NEXT:    ]
+; CHECK:       preheader-split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
-; CHECK-NEXT:    br i1 false, 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:    br i1 true, label [[HEADER]], label [[OUTER_BACKEDGE]]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I_2]], 1
+; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 ; 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:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
   br label %preheader

 }
 
 define i32 @full_sub_loop_test_switch_loop_inverse_2(i32 %end) {
 ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_2(
 ; 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:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[OUTER_BACKEDGE]]
+; CHECK-NEXT:    ]
+; CHECK:       preheader-split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
-; CHECK-NEXT:    switch i32 1, label [[DEAD:%.*]] [
-; CHECK-NEXT:    i32 0, label [[BACKEDGE]]
-; 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:    switch i32 1, label [[HEADER]] [
-; CHECK-NEXT:    i32 0, label [[OUTER_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I_2]], 1
+; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 ; 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:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
   br label %preheader

 
 
 define i32 @full_sub_loop_test_branch_loop_inverse_3(i32 %end) {
 ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_3(
 ; 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:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[OUTER_BACKEDGE]]
+; CHECK-NEXT:    ]
+; CHECK:       preheader-split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
-; 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:    br i1 true, label [[HEADER]], label [[OUTER_BACKEDGE]]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
+; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 ; 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:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
   br label %preheader

 }
 
 define i32 @full_sub_loop_test_switch_loop_inverse_3(i32 %end) {
 ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_3(
 ; 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:    switch i32 0, label [[PREHEADER_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[OUTER_BACKEDGE]]
+; CHECK-NEXT:    ]
+; CHECK:       preheader-split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
-; CHECK-NEXT:    switch i32 1, label [[BACKEDGE]] [
-; CHECK-NEXT:    i32 0, 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:    switch i32 1, label [[HEADER]] [
-; CHECK-NEXT:    i32 0, label [[OUTER_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
+; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 ; 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:    [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
   br label %preheader

 ; CHECK-LABEL: @exit_branch_from_inner_to_grandparent(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
 ; CHECK:       loop_1:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
 ; CHECK:       loop_2:
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
+; CHECK-NEXT:    switch i32 0, label [[LOOP_2_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[LOOP_2_BACKEDGE]]
+; CHECK-NEXT:    ]
+; CHECK:       loop_2-split:
 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
 ; CHECK:       loop_3:
-; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2_SPLIT]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
-; CHECK-NEXT:    br i1 true, label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
+; CHECK-NEXT:    br label [[LOOP_3]]
 ; CHECK:       loop_2_backedge:
 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
 ; CHECK:       loop_1_backedge.loopexit:
 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
 ; CHECK:       loop_1_backedge.loopexit1:
 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]

 ; CHECK-LABEL: @exit_switch_from_inner_to_grandparent(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[LOOP_1:%.*]]
 ; CHECK:       loop_1:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
 ; CHECK:       loop_2:
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
+; CHECK-NEXT:    switch i32 0, label [[LOOP_2_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[LOOP_2_BACKEDGE]]
+; CHECK-NEXT:    ]
+; CHECK:       loop_2-split:
 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
 ; CHECK:       loop_3:
-; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2_SPLIT]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
-; CHECK-NEXT:    switch i32 1, label [[LOOP_3]] [
-; CHECK-NEXT:    i32 0, label [[LOOP_2_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[LOOP_3]]
 ; CHECK:       loop_2_backedge:
 ; CHECK-NEXT:    [[J_NEXT]] = add i32 [[J]], 1
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
 ; CHECK:       loop_1_backedge.loopexit:
 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
 ; CHECK:       loop_1_backedge.loopexit1:
 ; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]