[WebAssembly] Implement a new algorithm for placing BLOCK markers

[sunfish]

Summary

Implement a new BLOCK scope placement algorithm which better handles early-return blocks and early exists from nested scopes.

[jfb]

lgtm overall, though I haven't dug into the stackifier enough to have a good grasp of how it works.

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

 /// [0] https://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings
 ///
 //===----------------------------------------------------------------------===//
 
 #include "WebAssembly.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssemblySubtarget.h"
 #include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
std::stable_sort(
           return false;
 
         // TODO: More sophisticated orderings may be profitable here.
 
         return false;
       });
 }
 
+/// Return the "bottom" block of a loop. This differs from
+/// MachineLoop::getBottomBlock in that it works even if the loop is
+/// discontiguous.
+static MachineBasicBlock *LoopBottom(const MachineLoop *Loop) {
+  MachineBasicBlock *Bottom = Loop->getHeader();
+  for (MachineBasicBlock *MBB : Loop->blocks())
+    if (MBB->getNumber() > Bottom->getNumber())
+      Bottom = MBB;
+  return Bottom;
+}
+
 /// Sort the blocks in RPO, taking special care to make sure that loops are
 /// contiguous even in the case of split backedges.
+///
+/// TODO: Determine whether RPO is actually worthwhile, or whether we should
+/// move to just a stable-topological-sort-based approach that would preserve
+/// more of the original order.
 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) {
   // Note that we do our own RPO rather than using
   // "llvm/ADT/PostOrderIterator.h" because we want control over the order that
   // successors are visited in (see above). Also, we can sort the blocks in the
   // MachineFunction as we go.
   SmallPtrSet<MachineBasicBlock *, 16> Visited;
   SmallVector<POStackEntry, 16> Stack;
 
for (;;) {
     if (Stack.empty())
       break;
   }
 
   // Now that we've sorted the blocks in RPO, renumber them.
   MF.RenumberBlocks();
 
 #ifndef NDEBUG
-  for (auto &MBB : MF)
-    if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) {
-      // Assert that all containing loops are contiguous.
-      for (MachineLoop *L = Loop; L; L = L->getParentLoop()) {
-        if (&MBB == L->getHeader()) {
-          assert(&MBB == L->getTopBlock());
-        } else {
-          assert(&MBB != L->getTopBlock());
-          assert(L->contains(
-                     MLI.getLoopFor(&*prev(MachineFunction::iterator(&MBB)))) &&
-                 "Loop isn't contiguous");
-        }
-      }
+  SmallSetVector<MachineLoop *, 8> OnStack;
+
+  // Insert a sentinel representing the degenerate loop that starts at the
+  // function entry block and includes the entire function as a "loop" that
+  // executes once.
+  OnStack.insert(nullptr);
+
+  for (auto &MBB : MF) {
+    MachineLoop *Loop = MLI.getLoopFor(&MBB);
+    if (Loop && &MBB == Loop->getHeader()) {
+      // Loop header. The loop predecessor should be sorted above, and the other
+      // predecessors should be backedges below.
+      for (auto Pred : MBB.predecessors())
+        assert(
+            (Pred->getNumber() < MBB.getNumber() || Loop->contains(Pred)) &&
+            "Loop header predecessors must be loop predecessors or backedges");
+      assert(OnStack.insert(Loop) && "Loops should be declared at most once.");
     } else {
-      // Assert that non-loops have no backedge predecessors.
+      // Not a loop header. All predecessors should be sorted above.
       for (auto Pred : MBB.predecessors())
         assert(Pred->getNumber() < MBB.getNumber() &&
-               "CFG still has multiple-entry loops");
-    }
+               "Non-loop-header predecessors should be topologically sorted");
+      assert(OnStack.count(MLI.getLoopFor(&MBB)) &&
+             "Blocks must be nested in their loops");
+    }
+    while (OnStack.size() > 1 && &MBB == LoopBottom(OnStack.back()))
+      OnStack.pop_back();
+  }
+  assert(OnStack.pop_back_val() == nullptr &&
+         "The function entry block shouldn't actually be a loop header");
+  assert(OnStack.empty() &&
+         "Control flow stack pushes and pops should be balanced.");
 #endif
 }
 
-static unsigned GetLoopDepth(const MachineLoop *Loop) {
-  return Loop ? Loop->getLoopDepth() : 0;
-}
-
 /// Insert a BLOCK marker for branches to MBB (if needed).
-static void PlaceBlockMarkers(MachineBasicBlock &MBB,
-                              const WebAssemblyInstrInfo &TII,
-                              MachineDominatorTree &MDT,
-                              const MachineLoopInfo &MLI) {
-  // Place the BLOCK for forward non-fallthrough branches. Put it at the nearest
-  // common dominator of all preceding predecesors so that we minimize the time
-  // that it's on the stack, which reduces overall stack height.
+static void PlaceBlockMarker(MachineBasicBlock &MBB, MachineFunction &MF,
+                             SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
+                             const MachineLoopInfo &MLI,
+                             MachineDominatorTree &MDT) {
+  // First compute the nearest common dominator of all forward non-fallthrough
+  // predecessors so that we minimize the time that the BLOCK is on the stack,
+  // which reduces overall stack height.
   MachineBasicBlock *Header = nullptr;
   bool IsBranchedTo = false;
   int MBBNumber = MBB.getNumber();
   for (MachineBasicBlock *Pred : MBB.predecessors())
     if (Pred->getNumber() < MBBNumber) {
       Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
       if (!Pred->isLayoutSuccessor(&MBB) ||
           !(Pred->empty() || !Pred->back().isBarrier()))
         IsBranchedTo = true;
     }
   if (!Header)
     return;
   if (!IsBranchedTo)
     return;
 
+  assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
+  MachineBasicBlock *LayoutPred = &*prev(MachineFunction::iterator(&MBB));
+
+  // If the nearest common dominator is inside a more deeply nested context,
+  // walk out to the nearest scope which isn't more deeply nested.
+  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
+    if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
+      if (ScopeTop->getNumber() > Header->getNumber()) {
+        // Skip over an intervening scope.
+        I = next(MachineFunction::iterator(ScopeTop));
+      } else {
+        // We found a scope level at an appropriate depth.
+        Header = ScopeTop;
+        break;
+      }
+    }
+  }
+
+  // If there's a loop which ends just before MBB which contains Header, we can
+  // reuse its label instead of inserting a new BLOCK.
+  for (MachineLoop *Loop = MLI.getLoopFor(LayoutPred);
+       Loop && Loop->contains(LayoutPred); Loop = Loop->getParentLoop())
+    if (Loop && LoopBottom(Loop) == LayoutPred && Loop->contains(Header))
+      return;
+
+  // Decide where in Header to put the BLOCK.
   MachineBasicBlock::iterator InsertPos;
   MachineLoop *HeaderLoop = MLI.getLoopFor(Header);
-  unsigned MBBLoopDepth = GetLoopDepth(MLI.getLoopFor(&MBB));
-  unsigned HeaderLoopDepth = GetLoopDepth(HeaderLoop);
-  if (HeaderLoopDepth > MBBLoopDepth) {
-    // The nearest common dominating point is more deeply nested. Insert the
-    // BLOCK just above the LOOP.
-    for (unsigned i = 0; i < HeaderLoopDepth - 1 - MBBLoopDepth; ++i)
-      HeaderLoop = HeaderLoop->getParentLoop();
-    Header = HeaderLoop->getHeader();
+  if (HeaderLoop && MBB.getNumber() > LoopBottom(HeaderLoop)->getNumber()) {
+    // Header is the header of a loop that does not lexically contain MBB, so
+    // the BLOCK needs to be above the LOOP.
     InsertPos = Header->begin();
-    // Don't insert a BLOCK if we can reuse a loop exit label though.
-    if (InsertPos != Header->end() &&
-        InsertPos->getOpcode() == WebAssembly::LOOP &&
-        InsertPos->getOperand(0).getMBB() == &MBB)
-      return;
   } else {
-    // Insert the BLOCK as late in the block as we can, but before any existing
-    // BLOCKs.
+    // Otherwise, insert the BLOCK as late in Header as we can, but before any
+    // existing BLOCKs.
     InsertPos = Header->getFirstTerminator();
     while (InsertPos != Header->begin() &&
-           std::prev(InsertPos)->getOpcode() == WebAssembly::BLOCK)
+           prev(InsertPos)->getOpcode() == WebAssembly::BLOCK)
       --InsertPos;
   }
 
+  // Add the BLOCK.
   BuildMI(*Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK))
       .addMBB(&MBB);
+
+  // Track the farthest-spanning scope that ends at this point.
+  int Number = MBB.getNumber();
+  if (!ScopeTops[Number] ||
+      ScopeTops[Number]->getNumber() > Header->getNumber())
+    ScopeTops[Number] = Header;
 }
 
-/// Insert LOOP and BLOCK markers at appropriate places.
-static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
+/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
+static void PlaceLoopMarker(MachineBasicBlock &MBB, MachineFunction &MF,
+                            SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
                             const WebAssemblyInstrInfo &TII,
-                         MachineDominatorTree &MDT) {
-  for (auto &MBB : MF) {
-    // Place the LOOP for MBB if MBB is the header of a loop.
-    if (MachineLoop *Loop = MLI.getLoopFor(&MBB))
-      if (Loop->getHeader() == &MBB) {
-        // The operand of a LOOP is the first block after the loop. If the loop
-        // is the bottom of the function, insert a dummy block at the end.
-        MachineBasicBlock *Bottom = Loop->getBottomBlock();
-        auto Iter = next(MachineFunction::iterator(Bottom));
-        if (Iter == MF.end()) {
-          MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
-          // Give it a fake predecessor so that AsmPrinter prints its label.
-          Label->addSuccessor(Label);
-          MF.push_back(Label);
-          Iter = next(MachineFunction::iterator(Bottom));
-        }
-        BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP))
-            .addMBB(&*Iter);
+                            const MachineLoopInfo &MLI) {
+  MachineLoop *Loop = MLI.getLoopFor(&MBB);
+  if (!Loop || Loop->getHeader() != &MBB)
+    return;
+
+  // The operand of a LOOP is the first block after the loop. If the loop is the
+  // bottom of the function, insert a dummy block at the end.
+  MachineBasicBlock *Bottom = LoopBottom(Loop);
+  MachineBasicBlock *AfterLoop = &*Iter;
+      .addMBB(AfterLoop);
 
-        // Emit a special no-op telling the asm printer that we need a label
-        // to close the loop scope, even though the destination is only
-        // reachable by fallthrough.
-        if (!Bottom->back().isBarrier())
-          BuildMI(*Bottom, Bottom->end(), DebugLoc(),
-                  TII.get(WebAssembly::LOOP_END));
-      }
+  // Emit a special no-op telling the asm printer that we need a label to close
+  // the loop scope, even though the destination is only reachable by
+  // fallthrough.
+    BuildMI(*Bottom, Bottom->end(), DebugLoc(), TII.get(WebAssembly::LOOP_END));
+
+  assert((!ScopeTops[AfterLoop->getNumber()] ||
+          ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
+         "With RPO we should visit the outer-most loop for a block first.");
+  if (!ScopeTops[AfterLoop->getNumber()])
+    ScopeTops[AfterLoop->getNumber()] = &MBB;
 
+/// Insert LOOP and BLOCK markers at appropriate places.
+static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
+                         const WebAssemblyInstrInfo &TII,
+                         MachineDominatorTree &MDT) {
+  // For each block whose label represents the end of a scope, record the block
+  // which holds the beginning of the scope. This will allow us to quickly skip
+  // over scoped regions when walking blocks. We allocate one more than the
+  // number of blocks in the function to accommodate for the possible fake block
+  // we may insert at the end.
+  SmallVector<MachineBasicBlock *, 8> ScopeTops(MF.getNumBlockIDs() + 1);
+
+  for (auto &MBB : MF) {
+    // Place the LOOP for MBB if MBB is the header of a loop.
+    PlaceLoopMarker(MBB, MF, ScopeTops, TII, MLI);
+
     // Place the BLOCK for MBB if MBB is branched to from above.
-    PlaceBlockMarkers(MBB, TII, MDT, MLI);
+    PlaceBlockMarker(MBB, MF, ScopeTops, TII, MLI, MDT);
   }
 }
 
 #ifndef NDEBUG
 static bool
 IsOnStack(const SmallVectorImpl<std::pair<MachineBasicBlock *, bool>> &Stack,
           const MachineBasicBlock *MBB) {
   for (const auto &Pair : Stack)
bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
   PlaceMarkers(MF, MLI, TII, MDT);
 
 #ifndef NDEBUG
   // Verify that block and loop beginnings and endings are in LIFO order, and
   // that all references to blocks are to blocks on the stack at the point of
   // the reference.
   SmallVector<std::pair<MachineBasicBlock *, bool>, 0> Stack;
   for (auto &MBB : MF) {
+    assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
     while (!Stack.empty() && Stack.back().first == &MBB)
       if (Stack.back().second) {
         assert(Stack.size() >= 2);
         Stack.pop_back();
         Stack.pop_back();
       } else {
         assert(Stack.size() >= 1);
         Stack.pop_back();
       }
     for (auto &MI : MBB)
       switch (MI.getOpcode()) {
       case WebAssembly::LOOP:
         Stack.push_back(std::make_pair(&MBB, false));
         Stack.push_back(std::make_pair(MI.getOperand(0).getMBB(), true));
         break;
       case WebAssembly::BLOCK:
         Stack.push_back(std::make_pair(MI.getOperand(0).getMBB(), false));
         break;
       default:
+        // Verify that all referenced blocks are in scope. A reference to a
+        // block with a negative number is invalid, but can happen with inline
+        // asm, so we shouldn't assert on it, but instead let CodeGen properly
+        // fail on it.
         for (const MachineOperand &MO : MI.explicit_operands())
-          if (MO.isMBB())
+          if (MO.isMBB() && MO.getMBB()->getNumber() >= 0)
             assert(IsOnStack(Stack, MO.getMBB()));
         break;
       }
   }
   assert(Stack.empty());
 #endif
 
   return true;
 }

test/CodeGen/WebAssembly/cfg-stackify.ll

 ; RUN: llc < %s -asm-verbose=false -disable-block-placement | FileCheck %s
 ; RUN: llc < %s -asm-verbose=false | FileCheck -check-prefix=OPT %s
 
 ; Test the CFG stackifier pass.
 
 target datalayout = "e-p:32:32-i64:64-n32:64-S128"
 target triple = "wasm32-unknown-unknown"
 
 declare void @something()
 
 ; Test that loops are made contiguous, even in the presence of split backedges.
 
 ; CHECK-LABEL: test0:
 ; CHECK: loop
-; CHECK: i32.add
 ; CHECK-NOT: br
-; CHECK: br_if
+; CHECK: i32.add
+; CHECK-NEXT: i32.ge_s
+; CHECK-NEXT: br_if
 ; CHECK-NOT: br
 ; CHECK: call
 ; CHECK: br BB0_1{{$}}
 ; CHECK: return{{$}}
 ; OPT-LABEL: test0:
 ; OPT: loop
-; OPT: i32.add
 ; OPT-NOT: br
-; OPT: br_if
+; OPT: i32.add
+; OPT-NEXT: i32.ge_s
+; OPT-NEXT: br_if
 ; OPT-NOT: br
 ; OPT: call
 ; OPT: br BB0_1{{$}}
 ; OPT: return{{$}}
 define void @test0(i32 %n) {
 entry:
   br label %header
 
back:
   call void @something()
   br label %header
 }
 
 ; Same as test0, but the branch condition is reversed.
 
 ; CHECK-LABEL: test1:
 ; CHECK: loop
-; CHECK: i32.add
 ; CHECK-NOT: br
-; CHECK: br_if
+; CHECK: i32.add
+; CHECK-NEXT: i32.ge_s
+; CHECK-NEXT: br_if
 ; CHECK-NOT: br
 ; CHECK: call
 ; CHECK: br BB1_1{{$}}
 ; CHECK: return{{$}}
 ; OPT-LABEL: test1:
 ; OPT: loop
-; OPT: i32.add
 ; OPT-NOT: br
-; OPT: br_if
+; OPT: i32.add
+; OPT-NEXT: i32.ge_s
+; OPT-NEXT: br_if
 ; OPT-NOT: br
 ; OPT: call
 ; OPT: br BB1_1{{$}}
 ; OPT: return{{$}}
 define void @test1(i32 %n) {
 entry:
   br label %header
 
ff:
   br label %exit
 exit:
   store volatile i32 5, i32* %p
   br label %header
 }
 
 ; Test that nested loops are handled.
 
+; CHECK-LABEL: test3:
+; CHECK: loop
+; CHECK-NEXT: br_if
+; CHECK-NEXT: BB{{[0-9]+}}_{{[0-9]+}}:
+; CHECK-NEXT: loop
+; OPT-LABEL: test3:
+; OPT: loop
+; OPT-NEXT: br_if
+; OPT-NEXT: BB{{[0-9]+}}_{{[0-9]+}}:
+; OPT-NEXT: loop
 declare void @bar()
-
 define void @test3(i32 %w)  {
 entry:
   br i1 undef, label %outer.ph, label %exit
 
 outer.ph:
   br label %outer
 
 outer:

 
 exit:
   ret void
 
 if.end:
   call void @bar()
   br label %outer
 }
+
+; Test switch lowering and block placement.
+
+; CHECK-LABEL: test4:
+; CHECK-NEXT: .param      i32{{$}}
+; CHECK:      block       BB13_8{{$}}
+; CHECK-NEXT: block       BB13_7{{$}}
+; CHECK-NEXT: block       BB13_4{{$}}
+; CHECK-NEXT: br_if       $pop{{[0-9]*}}, BB13_4{{$}}
+; CHECK-NEXT: block       BB13_3{{$}}
+; CHECK:      br_if       $pop{{[0-9]*}}, BB13_3{{$}}
+; CHECK:      br_if       $pop{{[0-9]*}}, BB13_7{{$}}
+; CHECK-NEXT: BB13_3:
+; CHECK-NEXT: return{{$}}
+; CHECK-NEXT: BB13_4:
+; CHECK:      br_if       $pop{{[0-9]*}}, BB13_8{{$}}
+; CHECK:      br_if       $pop{{[0-9]*}}, BB13_7{{$}}
+; CHECK-NEXT: return{{$}}
+; CHECK-NEXT: BB13_7:
+; CHECK-NEXT: return{{$}}
+; CHECK-NEXT: BB13_8:
+; CHECK-NEXT: return{{$}}
+; OPT-LABEL: test4:
+; OPT-NEXT: .param      i32{{$}}
+; OPT:      block       BB13_8{{$}}
+; OPT-NEXT: block       BB13_7{{$}}
+; OPT-NEXT: block       BB13_4{{$}}
+; OPT-NEXT: br_if       $pop{{[0-9]*}}, BB13_4{{$}}
+; OPT-NEXT: block       BB13_3{{$}}
+; OPT:      br_if       $pop{{[0-9]*}}, BB13_3{{$}}
+; OPT:      br_if       $pop{{[0-9]*}}, BB13_7{{$}}
+; OPT-NEXT: BB13_3:
+; OPT-NEXT: return{{$}}
+; OPT-NEXT: BB13_4:
+; OPT:      br_if       $pop{{[0-9]*}}, BB13_8{{$}}
+; OPT:      br_if       $pop{{[0-9]*}}, BB13_7{{$}}
+; OPT-NEXT: return{{$}}
+; OPT-NEXT: BB13_7:
+; OPT-NEXT: return{{$}}
+; OPT-NEXT: BB13_8:
+; OPT-NEXT: return{{$}}
+define void @test4(i32 %t) {
+entry:
+  switch i32 %t, label %default [
+    i32 0, label %bb2
+    i32 2, label %bb2
+    i32 4, label %bb1
+    i32 622, label %bb0
+  ]
+
+bb0:
+  ret void
+
+bb1:
+  ret void
+
+bb2:
+  ret void
+
+default:
+  ret void
+}
+
+; Test a case where the BLOCK needs to be placed before the LOOP in the
+; same basic block.
+
+; CHECK-LABEL: test5:
+; CHECK:       BB14_1:
+; CHECK-NEXT:  block BB14_4{{$}}
+; CHECK-NEXT:  loop BB14_3{{$}}
+; CHECK:       br_if {{[^,]*}}, BB14_4{{$}}
+; CHECK:       br_if {{[^,]*}}, BB14_1{{$}}
+; CHECK-NEXT:  BB14_3:
+; CHECK:       return{{$}}
+; CHECK-NEXT:  BB14_4:
+; CHECK:       return{{$}}
+; OPT-LABEL: test5:
+; OPT:       BB14_1:
+; OPT-NEXT:  block BB14_4{{$}}
+; OPT-NEXT:  loop BB14_3{{$}}
+; OPT:       br_if {{[^,]*}}, BB14_4{{$}}
+; OPT:       br_if {{[^,]*}}, BB14_1{{$}}
+; OPT-NEXT:  BB14_3:
+; OPT:       return{{$}}
+; OPT-NEXT:  BB14_4:
+; OPT:       return{{$}}
+define void @test5(i1 %p, i1 %q) {
+entry:
+  br label %header
+
+header:
+  store volatile i32 0, i32* null
+  br i1 %p, label %more, label %alt
+
+more:
+  store volatile i32 1, i32* null
+  br i1 %q, label %header, label %return
+
+alt:
+  store volatile i32 2, i32* null
+  ret void
+
+return:
+  store volatile i32 3, i32* null
+  ret void
+}
+
+; Test an interesting case of a loop with multiple exits, which
+; aren't to layout successors of the loop, and one of which is to a successors
+; which has another predecessor.
+
+; CHECK-LABEL: test6:
+; CHECK:       BB15_1:
+; CHECK-NEXT:  block BB15_6{{$}}
+; CHECK-NEXT:  block BB15_5{{$}}
+; CHECK-NEXT:  loop  BB15_4{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if {{[^,]*}}, BB15_6{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if {{[^,]*}}, BB15_5{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if {{[^,]*}}, BB15_1{{$}}
+; CHECK-NEXT:  BB15_4:
+; CHECK-NOT:   block
+; CHECK:       return{{$}}
+; CHECK-NEXT:  BB15_5:
+; CHECK-NOT:   block
+; CHECK:       BB15_6:
+; CHECK-NOT:   block
+; CHECK:       return{{$}}
+; OPT-LABEL: test6:
+; OPT:       BB15_1:
+; OPT-NEXT:  block BB15_6{{$}}
+; OPT-NEXT:  block BB15_5{{$}}
+; OPT-NEXT:  loop  BB15_4{{$}}
+; OPT-NOT:   block
+; OPT:       br_if {{[^,]*}}, BB15_6{{$}}
+; OPT-NOT:   block
+; OPT:       br_if {{[^,]*}}, BB15_5{{$}}
+; OPT-NOT:   block
+; OPT:       br_if {{[^,]*}}, BB15_1{{$}}
+; OPT-NEXT:  BB15_4:
+; OPT-NOT:   block
+; OPT:       return{{$}}
+; OPT-NEXT:  BB15_5:
+; OPT-NOT:   block
+; OPT:       BB15_6:
+; OPT-NOT:   block
+; OPT:       return{{$}}
+define void @test6(i1 %p, i1 %q) {
+entry:
+  br label %header
+
+header:
+  store volatile i32 0, i32* null
+  br i1 %p, label %more, label %second
+
+more:
+  store volatile i32 1, i32* null
+  br i1 %q, label %evenmore, label %first
+
+evenmore:
+  store volatile i32 1, i32* null
+  br i1 %q, label %header, label %return
+
+return:
+  store volatile i32 2, i32* null
+  ret void
+
+first:
+  store volatile i32 3, i32* null
+  br label %second
+
+second:
+  store volatile i32 4, i32* null
+  ret void
+}
+
+; Test a case where there are multiple backedges and multiple loop exits
+; that end in unreachable.
+
+; CHECK-LABEL: test7:
+; CHECK:       BB16_1:
+; CHECK-NEXT:  loop BB16_5{{$}}
+; CHECK-NOT:   block
+; CHECK:       block BB16_4{{$}}
+; CHECK-NEXT:  br_if {{[^,]*}}, BB16_4{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if {{[^,]*}}, BB16_1{{$}}
+; CHECK-NOT:   block
+; CHECK:       unreachable
+; CHECK_NEXT:  BB16_4:
+; CHECK-NOT:   block
+; CHECK:       br_if {{[^,]*}}, BB16_1{{$}}
+; CHECK-NEXT:  BB16_5:
+; CHECK-NOT:   block
+; CHECK:       unreachable
+; OPT-LABEL: test7:
+; OPT:       BB16_1:
+; OPT-NEXT:  loop BB16_5{{$}}
+; OPT-NOT:   block
+; OPT:       block BB16_4{{$}}
+; OPT-NOT:   block
+; OPT:       br_if {{[^,]*}}, BB16_4{{$}}
+; OPT-NOT:   block
+; OPT:       br_if {{[^,]*}}, BB16_1{{$}}
+; OPT-NOT:   block
+; OPT:       unreachable
+; OPT_NEXT:  BB16_4:
+; OPT-NOT:   block
+; OPT:       br_if {{[^,]*}}, BB16_1{{$}}
+; OPT-NEXT:  BB16_5:
+; OPT-NOT:   block
+; OPT:       unreachable
+define void @test7(i1 %tobool2, i1 %tobool9) {
+entry:
+  store volatile i32 0, i32* null
+  br label %loop
+
+loop:
+  store volatile i32 1, i32* null
+  br i1 %tobool2, label %l1, label %l0
+
+l0:
+  store volatile i32 2, i32* null
+  br i1 %tobool9, label %loop, label %u0
+
+l1:
+  store volatile i32 3, i32* null
+  br i1 %tobool9, label %loop, label %u1
+
+u0:
+  store volatile i32 4, i32* null
+  unreachable
+
+u1:
+  store volatile i32 5, i32* null
+  unreachable
+}
+
+; Test an interesting case using nested loops and switches.
+
+; CHECK-LABEL: test8:
+; CHECK:       BB17_1:
+; CHECK-NEXT:  loop     BB17_4{{$}}
+; CHECK-NEXT:  block    BB17_3{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if    {{[^,]*}}, BB17_3{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if    {{[^,]*}}, BB17_1{{$}}
+; CHECK-NEXT:  BB17_3:
+; CHECK-NEXT:  loop     BB17_4{{$}}
+; CHECK-NEXT:  br_if    {{[^,]*}}, BB17_3{{$}}
+; CHECK-NEXT:  br       BB17_1{{$}}
+; CHECK-NEXT:  BB17_4:
+; OPT-LABEL: test8:
+; OPT:       BB17_1:
+; OPT-NEXT:  loop     BB17_4{{$}}
+; OPT-NEXT:  block    BB17_3{{$}}
+; OPT-NOT:   block
+; OPT:       br_if    {{[^,]*}}, BB17_3{{$}}
+; OPT-NOT:   block
+; OPT:       br_if    {{[^,]*}}, BB17_1{{$}}
+; OPT-NEXT:  BB17_3:
+; OPT-NEXT:  loop     BB17_4{{$}}
+; OPT-NEXT:  br_if    {{[^,]*}}, BB17_3{{$}}
+; OPT-NEXT:  br       BB17_1{{$}}
+; OPT-NEXT:  BB17_4:
+define i32 @test8() {
+bb:
+  br label %bb1
+
+bb1:
+  br i1 undef, label %bb2, label %bb3
+
+bb2:
+  switch i8 undef, label %bb1 [
+    i8 44, label %bb2
+  ]
+
+bb3:
+  switch i8 undef, label %bb1 [
+    i8 44, label %bb2
+  ]
+}
+
+; Test an interesting case using nested loops that share a bottom block.
+
+; CHECK-LABEL: test9:
+; CHECK:       BB18_1:
+; CHECK-NEXT:  loop      BB18_5{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if     {{[^,]*}}, BB18_5{{$}}
+; CHECK-NEXT:  BB18_2:
+; CHECK-NEXT:  loop      BB18_5{{$}}
+; CHECK-NOT:   block
+; CHECK:       block     BB18_4{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if     {{[^,]*}}, BB18_4{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if     {{[^,]*}}, BB18_2{{$}}
+; CHECK-NEXT:  br        BB18_1{{$}}
+; CHECK-NEXT:  BB18_4:
+; CHECK-NOT:   block
+; CHECK:       br_if     {{[^,]*}}, BB18_2{{$}}
+; CHECK-NEXT:  br        BB18_1{{$}}
+; CHECK-NEXT:  BB18_5:
+; CHECK-NOT:   block
+; CHECK:       return{{$}}
+; OPT-LABEL: test9:
+; OPT:       BB18_1:
+; OPT-NEXT:  loop      BB18_5{{$}}
+; OPT-NOT:   block
+; OPT:       br_if     {{[^,]*}}, BB18_5{{$}}
+; OPT-NEXT:  BB18_2:
+; OPT-NEXT:  loop      BB18_5{{$}}
+; OPT-NOT:   block
+; OPT:       block     BB18_4{{$}}
+; OPT-NOT:   block
+; OPT:       br_if     {{[^,]*}}, BB18_4{{$}}
+; OPT-NOT:   block
+; OPT:       br_if     {{[^,]*}}, BB18_2{{$}}
+; OPT-NEXT:  br        BB18_1{{$}}
+; OPT-NEXT:  BB18_4:
+; OPT-NOT:   block
+; OPT:       br_if     {{[^,]*}}, BB18_2{{$}}
+; OPT-NEXT:  br        BB18_1{{$}}
+; OPT-NEXT:  BB18_5:
+; OPT-NOT:   block
+; OPT:       return{{$}}
+declare i1 @a()
+define void @test9() {
+entry:
+  store volatile i32 0, i32* null
+  br label %header
+
+header:
+  store volatile i32 1, i32* null
+  %call4 = call i1 @a()
+  br i1 %call4, label %header2, label %end
+
+header2:
+  store volatile i32 2, i32* null
+  %call = call i1 @a()
+  br i1 %call, label %if.then, label %if.else
+
+if.then:
+  store volatile i32 3, i32* null
+  %call3 = call i1 @a()
+  br i1 %call3, label %header2, label %header
+
+if.else:
+  store volatile i32 4, i32* null
+  %call2 = call i1 @a()
+  br i1 %call2, label %header2, label %header
+
+end:
+  store volatile i32 5, i32* null
+  ret void
+}
+
+; Test an interesting case involving nested loops sharing a loop bottom,
+; and loop exits to a block with unreachable.
+
+; CHECK-LABEL: test10:
+; CHECK:       BB19_1:
+; CHECK-NEXT:  loop     BB19_7{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if    {{[^,]*}}, BB19_1{{$}}
+; CHECK-NEXT:  BB19_2:
+; CHECK-NEXT:  block    BB19_6{{$}}
+; CHECK-NEXT:  loop     BB19_5{{$}}
+; CHECK-NOT:   block
+; CHECK:       BB19_3:
+; CHECK-NEXT:  loop     BB19_5{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if    {{[^,]*}}, BB19_1{{$}}
+; CHECK-NOT:   block
+; CHECK:       tableswitch  {{[^,]*}}, BB19_3, BB19_3, BB19_5, BB19_1, BB19_2, BB19_6{{$}}
+; CHECK-NEXT:  BB19_5:
+; CHECK-NEXT:  return{{$}}
+; CHECK-NEXT:  BB19_6:
+; CHECK-NOT:   block
+; CHECK:       br       BB19_1{{$}}
+; CHECK-NEXT:  BB19_7:
+; OPT-LABEL: test10:
+; OPT:       BB19_1:
+; OPT-NEXT:  loop     BB19_7{{$}}
+; OPT-NOT:   block
+; OPT:       br_if    {{[^,]*}}, BB19_1{{$}}
+; OPT-NEXT:  BB19_2:
+; OPT-NEXT:  block    BB19_6{{$}}
+; OPT-NEXT:  loop     BB19_5{{$}}
+; OPT-NOT:   block
+; OPT:       BB19_3:
+; OPT-NEXT:  loop     BB19_5{{$}}
+; OPT-NOT:   block
+; OPT:       br_if    {{[^,]*}}, BB19_1{{$}}
+; OPT-NOT:   block
+; OPT:       tableswitch  {{[^,]*}}, BB19_3, BB19_3, BB19_5, BB19_1, BB19_2, BB19_6{{$}}
+; OPT-NEXT:  BB19_5:
+; OPT-NEXT:  return{{$}}
+; OPT-NEXT:  BB19_6:
+; OPT-NOT:   block
+; OPT:       br       BB19_1{{$}}
+; OPT-NEXT:  BB19_7:
+define void @test10() {
+bb0:
+  br label %bb1
+
+bb1:
+  %tmp = phi i32 [ 2, %bb0 ], [ 3, %bb3 ]
+  %tmp3 = phi i32 [ undef, %bb0 ], [ %tmp11, %bb3 ]
+  %tmp4 = icmp eq i32 %tmp3, 0
+  br i1 %tmp4, label %bb4, label %bb2
+
+bb2:
+  br label %bb3
+
+bb3:
+  %tmp11 = phi i32 [ 1, %bb5 ], [ 0, %bb2 ]
+  br label %bb1
+
+bb4:
+  %tmp6 = phi i32 [ %tmp9, %bb5 ], [ 4, %bb1 ]
+  %tmp7 = phi i32 [ %tmp6, %bb5 ], [ %tmp, %bb1 ]
+  br label %bb5
+
+bb5:
+  %tmp9 = phi i32 [ %tmp6, %bb5 ], [ %tmp7, %bb4 ]
+  switch i32 %tmp9, label %bb2 [
+    i32 0, label %bb5
+    i32 1, label %bb6
+    i32 3, label %bb4
+    i32 4, label %bb3
+  ]
+
+bb6:
+  ret void
+}
+
+; Test a CFG DAG with interesting merging.
+
+; CHECK-LABEL: test11:
+; CHECK:       block        BB20_8{{$}}
+; CHECK-NEXT:  block        BB20_7{{$}}
+; CHECK-NEXT:  block        BB20_6{{$}}
+; CHECK-NEXT:  block        BB20_4{{$}}
+; CHECK-NEXT:  br_if        {{[^,]*}}, BB20_4{{$}}
+; CHECK-NOT:   block
+; CHECK:       block        BB20_3{{$}}
+; CHECK-NEXT:  br_if        {{[^,]*}}, BB20_3{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if        {{[^,]*}}, BB20_6{{$}}
+; CHECK-NEXT:  BB20_3:
+; CHECK-NOT:   block
+; CHECK:       return{{$}}
+; CHECK-NEXT:  BB20_4:
+; CHECK-NOT:   block
+; CHECK:       br_if        {{[^,]*}}, BB20_8{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if        {{[^,]*}}, BB20_7{{$}}
+; CHECK-NEXT:  BB20_6:
+; CHECK-NOT:   block
+; CHECK:       return{{$}}
+; CHECK-NEXT:  BB20_7:
+; CHECK-NOT:   block
+; CHECK:       return{{$}}
+; CHECK-NEXT:  BB20_8:
+; CHECK-NOT:   block
+; CHECK:       return{{$}}
+; OPT-LABEL: test11:
+; OPT:       block        BB20_8{{$}}
+; OPT-NEXT:  block        BB20_4{{$}}
+; OPT-NEXT:  br_if        $0, BB20_4{{$}}
+; OPT-NOT:   block
+; OPT:       block        BB20_3{{$}}
+; OPT-NEXT:  br_if        $0, BB20_3{{$}}
+; OPT-NOT:   block
+; OPT:       br_if        $0, BB20_8{{$}}
+; OPT-NEXT:  BB20_3:
+; OPT-NOT:   block
+; OPT:       return{{$}}
+; OPT-NEXT:  BB20_4:
+; OPT-NOT:   block
+; OPT:       block        BB20_6{{$}}
+; OPT-NOT:   block
+; OPT:       br_if        $pop9, BB20_6{{$}}
+; OPT-NOT:   block
+; OPT:       return{{$}}
+; OPT-NEXT:  BB20_6:
+; OPT-NOT:   block
+; OPT:       br_if        $0, BB20_8{{$}}
+; OPT-NOT:   block
+; OPT:       return{{$}}
+; OPT-NEXT:  BB20_8:
+; OPT-NOT:   block
+; OPT:       return{{$}}
+define void @test11() {
+bb0:
+  store volatile i32 0, i32* null
+  br i1 undef, label %bb1, label %bb4
+bb1:
+  store volatile i32 1, i32* null
+  br i1 undef, label %bb3, label %bb2
+bb2:
+  store volatile i32 2, i32* null
+  br i1 undef, label %bb3, label %bb7
+bb3:
+  store volatile i32 3, i32* null
+  ret void
+bb4:
+  store volatile i32 4, i32* null
+  br i1 undef, label %bb8, label %bb5
+bb5:
+  store volatile i32 5, i32* null
+  br i1 undef, label %bb6, label %bb7
+bb6:
+  store volatile i32 6, i32* null
+  ret void
+bb7:
+  store volatile i32 7, i32* null
+  ret void
+bb8:
+  store volatile i32 8, i32* null
+  ret void
+}
+
+; CHECK-LABEL: test12:
+; CHECK:       BB21_1:
+; CHECK-NEXT:  loop        BB21_8{{$}}
+; CHECK-NOT:   block
+; CHECK:       block       BB21_7{{$}}
+; CHECK-NEXT:  block       BB21_6{{$}}
+; CHECK-NEXT:  block       BB21_4{{$}}
+; CHECK-NEXT:  br_if       {{[^,]*}}, BB21_4{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if       {{[^,]*}}, BB21_7{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if       {{[^,]*}}, BB21_7{{$}}
+; CHECK-NEXT:  br          BB21_6{{$}}
+; CHECK-NEXT:  BB21_4:
+; CHECK-NOT:   block
+; CHECK:       br_if       {{[^,]*}}, BB21_7{{$}}
+; CHECK-NOT:   block
+; CHECK:       br_if       {{[^,]*}}, BB21_7{{$}}
+; CHECK-NEXT:  BB21_6:
+; CHECK-NEXT:  return{{$}}
+; CHECK-NEXT:  BB21_7:
+; CHECK-NOT:   block
+; CHECK:       br          BB21_1{{$}}
+; CHECK-NEXT:  BB21_8:
+; OPT-LABEL: test12:
+; OPT:       BB21_1:
+; OPT-NEXT:  loop        BB21_8{{$}}
+; OPT-NOT:   block
+; OPT:       block       BB21_7{{$}}
+; OPT-NEXT:  block       BB21_6{{$}}
+; OPT-NEXT:  block       BB21_4{{$}}
+; OPT-NEXT:  br_if       {{[^,]*}}, BB21_4{{$}}
+; OPT-NOT:   block
+; OPT:       br_if       {{[^,]*}}, BB21_7{{$}}
+; OPT-NOT:   block
+; OPT:       br_if       {{[^,]*}}, BB21_7{{$}}
+; OPT-NEXT:  br          BB21_6{{$}}
+; OPT-NEXT:  BB21_4:
+; OPT-NOT:   block
+; OPT:       br_if       {{[^,]*}}, BB21_7{{$}}
+; OPT-NOT:   block
+; OPT:       br_if       {{[^,]*}}, BB21_7{{$}}
+; OPT-NEXT:  BB21_6:
+; OPT-NEXT:  return{{$}}
+; OPT-NEXT:  BB21_7:
+; OPT-NOT:   block
+; OPT:       br          BB21_1{{$}}
+; OPT-NEXT:  BB21_8:
+define void @test12(i8* %arg) {
+bb:
+  br label %bb1
+
+bb1:
+  %tmp = phi i32 [ 0, %bb ], [ %tmp5, %bb4 ]
+  %tmp2 = getelementptr i8, i8* %arg, i32 %tmp
+  %tmp3 = load i8, i8* %tmp2
+  switch i8 %tmp3, label %bb7 [
+    i8 42, label %bb4
+    i8 76, label %bb4
+    i8 108, label %bb4
+    i8 104, label %bb4
+  ]
+
+bb4:
+  %tmp5 = add i32 %tmp, 1
+  br label %bb1
+
+bb7:
+  ret void
+}