From: Dan Gohman Date: Mon, 14 Dec 2015 22:51:54 +0000 (+0000) Subject: [WebAssembly] Implement a new algorithm for placing BLOCK markers X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=4fe3f079fbc7ada006da829034228e12ed0f7042;hp=003f0f0bad2f0f769a221deebba3e6db69a7b842 [WebAssembly] Implement a new algorithm for placing BLOCK markers Implement a new BLOCK scope placement algorithm which better handles early-return blocks and early exists from nested scopes. Differential Revision: http://reviews.llvm.org/D15368 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@255564 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp index 110316ba57b..6412442176d 100644 --- a/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp +++ b/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp @@ -29,6 +29,7 @@ #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" @@ -152,8 +153,23 @@ POStackEntry::POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF, }); } +/// 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 @@ -198,40 +214,52 @@ static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) { 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 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) { + assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative."); + + 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 &ScopeTops, + const WebAssemblyInstrInfo &TII, + 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(); @@ -247,67 +275,112 @@ static void PlaceBlockMarkers(MachineBasicBlock &MBB, 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 a LOOP marker for a loop starting at MBB (if it's a loop header). +static void PlaceLoopMarker(MachineBasicBlock &MBB, MachineFunction &MF, + SmallVectorImpl &ScopeTops, + const WebAssemblyInstrInfo &TII, + 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); + 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)); + } + MachineBasicBlock *AfterLoop = &*Iter; + BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP)) + .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)); + + 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 ScopeTops(MF.getNumBlockIDs() + 1); + 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); - - // 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)); - } + 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); } } @@ -365,8 +438,12 @@ bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 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; } diff --git a/test/CodeGen/WebAssembly/cfg-stackify.ll b/test/CodeGen/WebAssembly/cfg-stackify.ll index 4c86c55a8f8..7717f35fec0 100644 --- a/test/CodeGen/WebAssembly/cfg-stackify.ll +++ b/test/CodeGen/WebAssembly/cfg-stackify.ll @@ -1,5 +1,5 @@ -; RUN: llc < %s -asm-verbose=false -disable-block-placement | FileCheck %s -; RUN: llc < %s -asm-verbose=false | FileCheck -check-prefix=OPT %s +; RUN: llc < %s -asm-verbose=false -disable-block-placement -verify-machineinstrs | FileCheck %s +; RUN: llc < %s -asm-verbose=false -verify-machineinstrs | FileCheck -check-prefix=OPT %s ; Test the CFG stackifier pass. @@ -12,18 +12,20 @@ declare void @something() ; 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{{$}} @@ -51,18 +53,20 @@ back: ; 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{{$}} @@ -416,8 +420,17 @@ exit: ; 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 @@ -443,3 +456,601 @@ 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 +}