[LoopSimplifyCFG] Delete current loop

[mkazantsev]

Summary

This patch lifts the final limitation posed on LoopSimplifyCFG by
teaching it to delete current loop.

(Not adding reviewers because it needs too many underlying patches merged first).

[mkazantsev]

Just setting "Plan changes" to not confuse reviewers too much with amount of patches in progress.

[mkazantsev]

Rebased

[mkazantsev]

Rebased.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 
 /// Helper class that can turn branches and switches with constant conditions
 /// into unconditional branches.
 class ConstantTerminatorFoldingImpl {
 private:
   Loop &L;
   LoopInfo &LI;
   DominatorTree &DT;
+  ScalarEvolution &SE;
   LoopBlocksDFS DFS;
 
   // Whether or not the current loop will still exist after terminator constant
   // folding will be done. In theory, there are two ways how it can happen:
   // 1. Loop's latch(es) become unreachable from loop header;
   // 2. Loop's header becomes unreachable from method entry.
   // In practice, the second situation is impossible because we only modify the
   // current loop and its preheader and do not affect preheader's reachibility
for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
         BlocksToProcess.push_back(BB);
       }
 
 #ifndef NDEBUG
       // Make sure that all in-loop successors of the block(s) we are handling
       // now have already been processed by this moment.
       for (auto *B : BlocksToProcess)
         for (auto *Succ : successors(B))
-          if (!BlocksInLoopAfterFolding.count(Succ) && L.contains(Succ))
+          if (!BlocksInLoopAfterFolding.count(Succ) && L.contains(Succ) &&
+              Succ != L.getHeader())
             assert(Visited.count(Succ) && "Bad order!");
 #endif
 
       // Find the most nested ancestor loop that is still BB's successor. BB
       // also belongs to this loop.
       Loop *ReachableOuterLoop = nullptr;
       for (BasicBlock *B : BlocksToProcess)
         for (BasicBlock *Succ : successors(B)) {
#endif
           LI.addTopLevelLoop(BBL);
       }
     }
 
     return true;
   }
 
 public:
-  ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT)
-      : L(L), LI(LI), DT(DT), DFS(&L) {}
+  ConstantTerminatorFoldingImpl(Loop &L, LoopInfo &LI, DominatorTree &DT,
+                                ScalarEvolution &SE)
+      : L(L), LI(LI), DT(DT), SE(SE), DFS(&L) {}
+
+  bool isLoopDeleted() const { return DeleteCurrentLoop; }
+
   bool run() {
     assert(L.getLoopLatch() && "Should be single latch!");
 
     // Collect all available information about status of blocks after constant
     // folding.
     analyze();
 
     LLVM_DEBUG(dbgs() << "In function " << L.getHeader()->getParent()->getName()
                       << ": ");
 
     // Nothing to constant-fold.
     if (FoldCandidates.empty()) {
       LLVM_DEBUG(
           dbgs() << "No constant terminator folding candidates found in loop "
                  << L.getHeader()->getName() << "\n");
       return false;
     }
 
-    // TODO: Support deletion of the current loop.
-    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;
-    }
-
     // Dump analysis results.
+    L.getHeader()->getParent()->dump();
     LLVM_DEBUG(dump());
-
+    BasicBlock *Header = L.getHeader();
+    (void)Header;
     LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
-                      << " terminators in loop " << L.getHeader()->getName()
+                      << " terminators in loop " << Header->getName()
                       << "\n");
 
     // Make the actual transforms.
+    if (DeleteCurrentLoop)
+      SE.forgetTopmostLoop(&L);
     handleDeadExits();
     foldTerminators();
     bool NewExitsAppeared = updateLoopInfo();
 
     if (!DeadLoopBlocks.empty()) {
       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
-                    << " dead blocks in loop " << L.getHeader()->getName()
+                    << " dead blocks in loop " << Header->getName()
                     << "\n");
       deleteDeadLoopBlocks();
     }
 
+    if (DeleteCurrentLoop) {
+      assert(L.block_begin() == L.block_end() && "Removed loop should contain no blocks!");
+      assert(L.begin() == L.end() && "Removed loop should contain no subloops!");
+      LI.erase(&L);
+    } else if (NewExitsAppeared)
       // TODO: Is there a smarter way to do it?
-    if (NewExitsAppeared)
       formLCSSA(L, DT, &LI, nullptr);
 
 #ifndef NDEBUG
     // Make sure that we have preserved all data structures after the transform.
     DT.verify();
+    if (!DeleteCurrentLoop)
       assert(DT.isReachableFromEntry(L.getHeader()));
     LI.verify(DT);
 #endif
 
     return true;
   }
 };
 
 /// Turn branches and switches with known constant conditions into unconditional
 /// branches.
-static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI) {
+static bool constantFoldTerminators(Loop &L, DominatorTree &DT, LoopInfo &LI,
+                                    ScalarEvolution &SE, bool &IsLoopDeleted) {
   // To keep things simple, only process loops with single latch. We
   // canonicalize most loops to this form. We can support multi-latch if needed.
   if (!L.getLoopLatch())
     return false;
 
-  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT);
-  return BranchFolder.run();
+  ConstantTerminatorFoldingImpl BranchFolder(L, LI, DT, SE);
+  bool Changed = BranchFolder.run();
+  IsLoopDeleted = BranchFolder.isLoopDeleted();
+  return Changed;
 }
 
 static bool mergeBlocksIntoPredecessors(Loop &L, DominatorTree &DT,
                                         LoopInfo &LI, MemorySSAUpdater *MSSAU) {
   bool Changed = false;
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   // Copy blocks into a temporary array to avoid iterator invalidation issues
   // as we remove them.
for (auto &Block : Blocks) {
 
     Changed = true;
   }
 
   return Changed;
 }
 
 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
-                            ScalarEvolution &SE, MemorySSAUpdater *MSSAU) {
+                            ScalarEvolution &SE, MemorySSAUpdater *MSSAU,
+                            bool &IsLoopDeleted) {
   bool Changed = false;
 
   // Constant-fold terminators with known constant conditions.
-  Changed |= constantFoldTerminators(L, DT, LI);
+  Changed |= constantFoldTerminators(L, DT, LI, SE, IsLoopDeleted);
+
+  if (IsLoopDeleted) {
+    assert(Changed && "Must be!");
+    return true;
+  }
 
   // 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,
                                            LoopStandardAnalysisResults &AR,
-                                           LPMUpdater &) {
+                                           LPMUpdater &LPMU) {
   Optional<MemorySSAUpdater> MSSAU;
   if (EnableMSSALoopDependency && AR.MSSA)
     MSSAU = MemorySSAUpdater(AR.MSSA);
+  bool IsLoopDeleted = false;
   if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
-                       MSSAU.hasValue() ? MSSAU.getPointer() : nullptr))
+                       MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
+                       IsLoopDeleted))
     return PreservedAnalyses::all();
 
+  if (IsLoopDeleted)
+    LPMU.markLoopAsDeleted(L, "loop-simplifycfg");
+
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 class LoopSimplifyCFGLegacyPass : public LoopPass {
 public:
   static char ID; // Pass ID, replacement for typeid
   LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
     initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
-  bool runOnLoop(Loop *L, LPPassManager &) override {
+  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
 
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     Optional<MemorySSAUpdater> MSSAU;
     if (EnableMSSALoopDependency) {
       MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
       MSSAU = MemorySSAUpdater(MSSA);
       if (VerifyMemorySSA)
         MSSA->verifyMemorySSA();
     }
-    return simplifyLoopCFG(*L, DT, LI, SE,
-                           MSSAU.hasValue() ? MSSAU.getPointer() : nullptr);
+    bool IsLoopDeleted = false;
+    bool Changed = simplifyLoopCFG(*L, DT, LI, SE,
+                           MSSAU.hasValue() ? MSSAU.getPointer() : nullptr,
+                           IsLoopDeleted);
+    if (IsLoopDeleted)
+      LPM.markLoopAsDeleted(*L);
+    return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     if (EnableMSSALoopDependency) {
       AU.addRequired<MemorySSAWrapperPass>();
       AU.addPreserved<MemorySSAWrapperPass>();
     }
     AU.addPreserved<DependenceAnalysisWrapperPass>();

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

 }
 
 ; Check that we can completely eliminate the current loop, branch case.
 define i32 @dead_loop_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_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 [[BACKEDGE]], label [[DEAD:%.*]]
-; CHECK:       dead:
-; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
-; CHECK-NEXT:    br label [[BACKEDGE]]
+; 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_INC:%.*]] = add i32 0, 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
-; CHECK-NEXT:    br i1 false, label [[HEADER]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:

 }
 
 ; Check that we can completely eliminate the current loop, switch case.
 define i32 @dead_loop_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_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:%.*]] [
-; 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-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_INC:%.*]] = add i32 0, 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
-; CHECK-NEXT:    br i1 false, label [[HEADER]], label [[EXIT:%.*]]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_INC_LCSSA]]
 ;
 preheader:
   br label %header
 header:
   %i = phi i32 [0, %preheader], [%i.inc, %backedge]

 }
 
 ; Check that we can completely delete inner loop and preserve the outer loop.
 define i32 @full_sub_loop_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @full_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:    [[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 false, label [[HEADER]], label [[OUTER_BACKEDGE]]
-; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_HEADER]] ]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 0, 0
+; CHECK-NEXT:    [[I_2:%.*]] = add i32 0, 1
+; CHECK-NEXT:    [[I_INC:%.*]] = add i32 [[I_2]], 1
 ; 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 [ [[I_INC]], [[OUTER_HEADER]] ]
 ; 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
exit:
   ret i32 %i.inc
 }
 
 define i32 @full_sub_loop_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @full_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:    [[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 [[OUTER_BACKEDGE]] [
-; CHECK-NEXT:    i32 0, label [[HEADER]]
-; CHECK-NEXT:    ]
-; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_HEADER]] ]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 0, 0
+; CHECK-NEXT:    [[I_2:%.*]] = add i32 0, 1
+; CHECK-NEXT:    [[I_INC:%.*]] = add i32 [[I_2]], 1
 ; 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 [ [[I_INC]], [[OUTER_HEADER]] ]
 ; 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

 }
 
 ; Inverted condition in live_part.
 define i32 @full_sub_loop_test_branch_loop_inverse_1(i32 %end) {
 ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_1(
 ; 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:    [[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 false, label [[HEADER]], label [[OUTER_BACKEDGE]]
-; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_HEADER]] ]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 0, 0
+; CHECK-NEXT:    [[I_INC:%.*]] = add i32 0, 1
 ; 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 [ [[I_INC]], [[OUTER_HEADER]] ]
 ; 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
exit:
   ret i32 %i.inc
 }
 
 define i32 @full_sub_loop_test_switch_loop_inverse_1(i32 %end) {
 ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_1(
 ; 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:    [[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 [[OUTER_BACKEDGE]] [
-; CHECK-NEXT:    i32 0, label [[HEADER]]
-; CHECK-NEXT:    ]
-; CHECK:       outer_backedge:
-; CHECK-NEXT:    [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_HEADER]] ]
+; CHECK-NEXT:    [[MUL:%.*]] = mul i32 0, 0
+; CHECK-NEXT:    [[I_INC:%.*]] = add i32 0, 1
 ; 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 [ [[I_INC]], [[OUTER_HEADER]] ]
 ; 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

 
 exit:
   ret i32 %i.inc
 }
 
 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:    switch i32 0, label [[ENTRY_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[EXIT:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       entry-split:
 ; 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-NEXT:    br label [[PREHEADER:%.*]]
+; CHECK:       preheader:
+; CHECK-NEXT:    br label [[PREHEADER_SPLIT:%.*]]
 ; CHECK:       preheader-split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_2]], 1
 ; CHECK-NEXT:    br label [[HEADER]]
-; CHECK:       outer_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 [ undef, [[OUTER_BACKEDGE]] ]
-; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
+; CHECK-NEXT:    ret i32 undef
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
   br label %preheader
 

 
 exit:
   ret i32 %i.inc
 }
 
 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:    switch i32 0, label [[ENTRY_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[EXIT:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       entry-split:
 ; 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-NEXT:    br label [[PREHEADER:%.*]]
+; CHECK:       preheader:
+; CHECK-NEXT:    br label [[PREHEADER_SPLIT:%.*]]
 ; CHECK:       preheader-split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I_2]], 1
 ; CHECK-NEXT:    br label [[HEADER]]
-; CHECK:       outer_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 [ undef, [[OUTER_BACKEDGE]] ]
-; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
+; CHECK-NEXT:    ret i32 undef
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
   br label %preheader
 

 exit:
   ret i32 %i.inc
 }
 
 
 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:    switch i32 0, label [[ENTRY_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[EXIT:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       entry-split:
 ; 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-NEXT:    br label [[PREHEADER:%.*]]
+; CHECK:       preheader:
+; CHECK-NEXT:    br label [[PREHEADER_SPLIT:%.*]]
 ; CHECK:       preheader-split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    br label [[HEADER]]
-; CHECK:       outer_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 [ undef, [[OUTER_BACKEDGE]] ]
-; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
+; CHECK-NEXT:    ret i32 undef
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
   br label %preheader
 

 
 exit:
   ret i32 %i.inc
 }
 
 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:    switch i32 0, label [[ENTRY_SPLIT:%.*]] [
+; CHECK-NEXT:    i32 1, label [[EXIT:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       entry-split:
 ; 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-NEXT:    br label [[PREHEADER:%.*]]
+; CHECK:       preheader:
+; CHECK-NEXT:    br label [[PREHEADER_SPLIT:%.*]]
 ; CHECK:       preheader-split:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[I]], [[I]]
 ; CHECK-NEXT:    [[I_INC]] = add i32 [[I]], 1
 ; CHECK-NEXT:    br label [[HEADER]]
-; CHECK:       outer_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 [ undef, [[OUTER_BACKEDGE]] ]
-; CHECK-NEXT:    ret i32 [[I_INC_LCSSA_LCSSA]]
+; CHECK-NEXT:    ret i32 undef
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
   br label %preheader
 
exit:
   ret i32 %i.inc
 }
 
 define i32 @exit_branch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) {
 ; 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:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
 ; CHECK:       loop_3:
-; 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-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[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 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:       loop_1_backedge:
 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
-; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
+; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
+; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
 ;
 preheader:
   br label %loop_1
 
 loop_1:
   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
   br label %loop_2
exit:
   ret i32 %i
 }
 
 define i32 @exit_switch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) {
 ; 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:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
 ; CHECK:       loop_3:
-; 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-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[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 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:       loop_1_backedge:
 ; CHECK-NEXT:    [[I_NEXT]] = add i32 [[I]], 1
-; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]]
+; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]
+; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE_LOOPEXIT]] ]
 ; CHECK-NEXT:    ret i32 [[I_LCSSA]]
 ;
 preheader:
   br label %loop_1
 
 loop_1:
   %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
   br label %loop_2