[LoopSimplifyCFG] Support blocks that are live, but no longer a part of current loop

[mkazantsev]

Summary

Adds support for situations when block don't become dead after the
folding, but stop being a part of the current loop. In this case, we
should do proper upates to Loop Info to keep it consistent.

[mkazantsev]

Still WIP, some bug with subloops.

[mkazantsev]

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

[mkazantsev]

Rebased, ready for review since underlying patches are now merged.

[mkazantsev]

I plan to hold it off before current implementation is enabled and works without issues for some time.

[mkazantsev]

Rebased.

llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

if (Loop *OuterLoop = LI.getLoopFor(Preheader)) {
         // We need all DT updates to be done before forming LCSSA.
         DTU.applyUpdates(DTUpdates);
         DTUpdates.clear();
         formLCSSARecursively(*FixLCSSALoop, DT, &LI, &SE);
       }
     }
   }
 
+  /// Update loop info for blocks from the original loop that remain live but
+  /// are no longer a part of the current loop after the folding.
+  void updateLiveBlocksInfo() {
+    // If there is no blocks that are no longer in current loop, nothing to do.
+    if (BlocksInLoopAfterFolding.size() == LiveLoopBlocks.size())
+      return;
+
+    assert(DFS.isComplete() && "Must be!");
+
+    // Block needs update if will be live but will not be a part of the current
+    // loop after folding will be done.
+    auto NeedsUpdate = [&](BasicBlock *BB) {
+      return LiveLoopBlocks.count(BB) && !BlocksInLoopAfterFolding.count(BB);
+    };
+    SmallPtrSet<BasicBlock *, 8> Visited;
+    // Traverse blocks in Postorder to preserve the following invariant: by the
+    // moment when we process a block, all its successors already have correct
+    // loops set.
+    for (auto I = DFS.beginPostorder(), E = DFS.endPostorder(); I != E; ++I) {
+      BasicBlock *BB = *I;
+      if (!NeedsUpdate(BB) || Visited.count(BB))
+        continue;
+
+      // The entire child subloop will be handled together with its header.
+      Loop *BBL = LI.getLoopFor(BB);
+      bool ProcessingChildLoop = (BBL != &L);
+      if (ProcessingChildLoop)
+        if (!LI.isLoopHeader(BB))
+          continue;
+
+      // Now we process BB. If BB is a loop header, we also process all blocks
+      // from this loop. To identify which loop contains BB now, look at its
+      // successors and find innermost loop among their containing loops.
+      SmallVector<BasicBlock *, 4> BlocksToProcess;
+      SmallPtrSet<BasicBlock *, 4> Successors;
+      if (ProcessingChildLoop) {
+        for (auto *B : BBL->blocks()) {
+          Visited.insert(B).second;
+          BlocksToProcess.push_back(B);
+        }
+      } else {
+        Visited.insert(BB);
+        BlocksToProcess.push_back(BB);
+      }
+
+      for (BasicBlock *B : BlocksToProcess)
+        for (BasicBlock *Succ : successors(B))
+            Successors.insert(Succ);
+      // Exclude successors for which we haven't figured out the right loop.
+      for (BasicBlock *B : BlocksToProcess)
+        Successors.erase(B);
+
+#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 (BasicBlock *Succ : Successors)
+        if (NeedsUpdate(Succ))
+          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 = getInnermostLoopFor(Successors, L, LI);
+      for (BasicBlock *B : BlocksToProcess) {
+        // Remove blocks from loops that no longer contain it.
+        if (!ProcessingChildLoop)
+          LI.changeLoopFor(B, ReachableOuterLoop);
+        removeBlockFromLoops(B, &L, ReachableOuterLoop);
+      }
+
+      // If we are processing a child loop, reattach it to new parent.
+      if (ProcessingChildLoop) {
+        assert(BBL->getParentLoop() == &L && "Should be!");
+        L.removeChildLoop(BBL);
+        if (ReachableOuterLoop)
+          ReachableOuterLoop->addChildLoop(BBL);
+        else
+          LI.addTopLevelLoop(BBL);
+      }
+    }
+
+    // We have new exit blocks that have not been exit blocks before. Build
+    // LCSSA form for them.
+    formLCSSA(L, DT, &LI, nullptr);
+  }
+
   /// Delete loop blocks that have become unreachable after folding. Make all
   /// relevant updates to DT and LI.
   void deleteDeadLoopBlocks() {
     if (MSSAU) {
       SmallPtrSet<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
                                                      DeadLoopBlocks.end());
       MSSAU->removeBlocks(DeadLoopBlocksSet);
     }
bool run() {
     if (DeleteCurrentLoop) {
       LLVM_DEBUG(
           dbgs()
           << "Give up constant terminator folding in loop " << Header->getName()
           << ": we don't currently support deletion of the current loop.\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 "
-                 << Header->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;
-    }
-
     SE.forgetTopmostLoop(&L);
     // Dump analysis results.
     LLVM_DEBUG(dump());
 
     LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
                       << " terminators in loop " << Header->getName() << "\n");
 
     // Make the actual transforms.
     handleDeadExits();
     foldTerminators();
+    updateLiveBlocksInfo();
 
     if (!DeadLoopBlocks.empty()) {
       LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
                     << " dead blocks in loop " << Header->getName() << "\n");
       deleteDeadLoopBlocks();
     } else {
       // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
       DTU.applyUpdates(DTUpdates);

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; REQUIRES: asserts
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa < %s | FileCheck %s
 ; 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 < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 
 ; Make sure that we can eliminate a provably dead backedge.
 define i32 @dead_backedge_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_backedge_test_branch_loop(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_BE:%.*]], [[HEADER_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[I_1:%.*]] = add i32 [[I]], 1
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_1:%.*]], [[HEADER_BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[I_1]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[I_1]], 100
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[HEADER_BACKEDGE]], label [[DEAD_BACKEDGE:%.*]]
 ; CHECK:       header.backedge:
-; CHECK-NEXT:    [[I_BE]] = phi i32 [ [[I_1]], [[HEADER]] ], [ [[I_2:%.*]], [[DEAD_BACKEDGE]] ]
 ; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       dead_backedge:
-; CHECK-NEXT:    [[I_2]] = add i32 [[I_1]], 10
-; CHECK-NEXT:    br i1 false, label [[HEADER_BACKEDGE]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[I_1_LCSSA:%.*]] = phi i32 [ [[I_1]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I_1_LCSSA]], 10
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_2_LCSSA:%.*]] = phi i32 [ [[I_2]], [[DEAD_BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_2_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:

 }
 
 ; Make sure that we can eliminate a provably dead backedge with switch.
 define i32 @dead_backedge_test_switch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_backedge_test_switch_loop(
 ; CHECK-NEXT:  preheader:
 ; CHECK-NEXT:    br label [[HEADER:%.*]]
 ; CHECK:       header:
-; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_BE:%.*]], [[HEADER_BACKEDGE:%.*]] ]
-; CHECK-NEXT:    [[I_1:%.*]] = add i32 [[I]], 1
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_1:%.*]], [[HEADER_BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[I_1]] = add i32 [[I]], 1
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[I_1]], 100
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[HEADER_BACKEDGE]], label [[DEAD_BACKEDGE:%.*]]
 ; CHECK:       header.backedge:
-; CHECK-NEXT:    [[I_BE]] = phi i32 [ [[I_1]], [[HEADER]] ], [ [[I_2:%.*]], [[DEAD_BACKEDGE]] ]
 ; CHECK-NEXT:    br label [[HEADER]]
 ; CHECK:       dead_backedge:
-; CHECK-NEXT:    [[I_2]] = add i32 [[I_1]], 10
-; CHECK-NEXT:    switch i32 1, label [[EXIT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[HEADER_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[I_1_LCSSA:%.*]] = phi i32 [ [[I_1]], [[HEADER]] ]
+; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I_1_LCSSA]], 10
+; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_2_LCSSA:%.*]] = phi i32 [ [[I_2]], [[DEAD_BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[I_2_LCSSA]]
 ;
 preheader:
   br label %header
 
 header:

 ; CHECK-NEXT:    br label [[LOOP_2:%.*]]
 ; CHECK:       loop_2:
 ; CHECK-NEXT:    [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br label [[LOOP_3:%.*]]
 ; CHECK:       loop_3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
 ; CHECK:       intermediate:
-; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[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:    br label [[LOOP_3:%.*]]
 ; CHECK:       loop_3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
 ; CHECK:       intermediate:
-; CHECK-NEXT:    switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[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:    br label [[LOOP_3:%.*]]
 ; CHECK:       loop_3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
 ; CHECK:       intermediate:
-; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]]
+; CHECK-NEXT:    br label [[LOOP_2_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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]]
 ; CHECK:       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:    br label [[LOOP_3:%.*]]
 ; CHECK:       loop_3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
 ; CHECK:       intermediate:
-; CHECK-NEXT:    switch i32 1, label [[LOOP_2_BACKEDGE]] [
-; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[LOOP_2_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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]]
 ; CHECK:       loop_1_backedge:

 ; CHECK:       loop_3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
 ; CHECK:       intermediate:
 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
 ; CHECK:       intermediate_loop:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]]
 ; CHECK:       intermediate_exit:
-; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]

 ; CHECK:       loop_3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
 ; CHECK:       intermediate:
 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
 ; CHECK:       intermediate_loop:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]]
 ; CHECK:       intermediate_exit:
-; CHECK-NEXT:    switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]

 ; CHECK:       loop_3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
 ; CHECK:       intermediate:
 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
 ; CHECK:       intermediate_loop:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]]
 ; CHECK:       intermediate_exit:
-; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]]
+; CHECK-NEXT:    br label [[LOOP_2_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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]]
 ; CHECK:       loop_1_backedge:

 ; CHECK:       loop_3:
 ; CHECK-NEXT:    [[K:%.*]] = phi i32 [ 0, [[LOOP_2]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[INTERMEDIATE:%.*]]
 ; CHECK:       intermediate:
 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
 ; CHECK:       intermediate_loop:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP]], label [[INTERMEDIATE_EXIT:%.*]]
 ; CHECK:       intermediate_exit:
-; CHECK-NEXT:    switch i32 1, label [[LOOP_2_BACKEDGE]] [
-; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[LOOP_2_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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]]
 ; CHECK:       loop_1_backedge:

 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
 ; CHECK:       intermediate_loop:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE:%.*]], label [[INTERMEDIATE_BLOCK:%.*]]
 ; CHECK:       intermediate_loop.backedge:
 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP]]
 ; CHECK:       intermediate_block:
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]]
 ; CHECK:       intermediate_exit:
-; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_2_BACKEDGE]]
+; CHECK-NEXT:    br label [[LOOP_2_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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]]
 ; CHECK:       loop_1_backedge:

 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
 ; CHECK:       intermediate_loop:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE:%.*]], label [[INTERMEDIATE_BLOCK:%.*]]
 ; CHECK:       intermediate_loop.backedge:
 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP]]
 ; CHECK:       intermediate_block:
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]]
 ; CHECK:       intermediate_exit:
-; CHECK-NEXT:    switch i32 1, label [[LOOP_2_BACKEDGE]] [
-; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[LOOP_2_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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]]
 ; CHECK:       loop_1_backedge:

 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
 ; CHECK:       intermediate_loop:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE:%.*]], label [[INTERMEDIATE_BLOCK:%.*]]
 ; CHECK:       intermediate_loop.backedge:
 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP]]
 ; CHECK:       intermediate_block:
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]]
 ; CHECK:       intermediate_exit:
-; CHECK-NEXT:    br i1 false, label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]]
+; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]

 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP:%.*]]
 ; CHECK:       intermediate_loop:
 ; CHECK-NEXT:    br i1 [[COND3:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE:%.*]], label [[INTERMEDIATE_BLOCK:%.*]]
 ; CHECK:       intermediate_loop.backedge:
 ; CHECK-NEXT:    br label [[INTERMEDIATE_LOOP]]
 ; CHECK:       intermediate_block:
 ; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[INTERMEDIATE_LOOP_BACKEDGE]], label [[INTERMEDIATE_EXIT:%.*]]
 ; CHECK:       intermediate_exit:
-; CHECK-NEXT:    switch i32 1, label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[LOOP_3_BACKEDGE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[LOOP_1_BACKEDGE]]
 ; CHECK:       loop_3_backedge:
 ; CHECK-NEXT:    [[K_NEXT]] = add i32 [[K]], 1
 ; CHECK-NEXT:    br i1 [[COND2]], label [[LOOP_3]], label [[LOOP_2_BACKEDGE]]
 ; 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:    br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ]