diff options
Diffstat (limited to 'contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp')
| -rw-r--r-- | contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp | 239 |
1 files changed, 16 insertions, 223 deletions
diff --git a/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp index 49b9754..21e0f6b 100644 --- a/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp +++ b/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp @@ -10,12 +10,7 @@ /// \file /// \brief This file implements a CFG stacking pass. /// -/// This pass reorders the blocks in a function to put them into topological -/// order, ignoring loop backedges, and without any loop being interrupted -/// by a block not dominated by the loop header, with special care to keep the -/// order as similar as possible to the original order. -/// -/// Then, it inserts BLOCK and LOOP markers to mark the start of scopes, since +/// This pass inserts BLOCK and LOOP markers to mark the start of scopes, since /// scope boundaries serve as the labels for WebAssembly's control transfers. /// /// This is sufficient to convert arbitrary CFGs into a form that works on @@ -23,13 +18,11 @@ /// //===----------------------------------------------------------------------===// -#include "WebAssembly.h" #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" +#include "WebAssembly.h" #include "WebAssemblyMachineFunctionInfo.h" #include "WebAssemblySubtarget.h" #include "WebAssemblyUtilities.h" -#include "llvm/ADT/PriorityQueue.h" -#include "llvm/ADT/SetVector.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -68,217 +61,6 @@ FunctionPass *llvm::createWebAssemblyCFGStackify() { return new WebAssemblyCFGStackify(); } -/// 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; -} - -static void MaybeUpdateTerminator(MachineBasicBlock *MBB) { -#ifndef NDEBUG - bool AnyBarrier = false; -#endif - bool AllAnalyzable = true; - for (const MachineInstr &Term : MBB->terminators()) { -#ifndef NDEBUG - AnyBarrier |= Term.isBarrier(); -#endif - AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch(); - } - assert((AnyBarrier || AllAnalyzable) && - "AnalyzeBranch needs to analyze any block with a fallthrough"); - if (AllAnalyzable) - MBB->updateTerminator(); -} - -namespace { -/// Sort blocks by their number. -struct CompareBlockNumbers { - bool operator()(const MachineBasicBlock *A, - const MachineBasicBlock *B) const { - return A->getNumber() > B->getNumber(); - } -}; -/// Sort blocks by their number in the opposite order.. -struct CompareBlockNumbersBackwards { - bool operator()(const MachineBasicBlock *A, - const MachineBasicBlock *B) const { - return A->getNumber() < B->getNumber(); - } -}; -/// Bookkeeping for a loop to help ensure that we don't mix blocks not dominated -/// by the loop header among the loop's blocks. -struct Entry { - const MachineLoop *Loop; - unsigned NumBlocksLeft; - - /// List of blocks not dominated by Loop's header that are deferred until - /// after all of Loop's blocks have been seen. - std::vector<MachineBasicBlock *> Deferred; - - explicit Entry(const MachineLoop *L) - : Loop(L), NumBlocksLeft(L->getNumBlocks()) {} -}; -} - -/// Sort the blocks, taking special care to make sure that loops are not -/// interrupted by blocks not dominated by their header. -/// TODO: There are many opportunities for improving the heuristics here. -/// Explore them. -static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI, - const MachineDominatorTree &MDT) { - // Prepare for a topological sort: Record the number of predecessors each - // block has, ignoring loop backedges. - MF.RenumberBlocks(); - SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0); - for (MachineBasicBlock &MBB : MF) { - unsigned N = MBB.pred_size(); - if (MachineLoop *L = MLI.getLoopFor(&MBB)) - if (L->getHeader() == &MBB) - for (const MachineBasicBlock *Pred : MBB.predecessors()) - if (L->contains(Pred)) - --N; - NumPredsLeft[MBB.getNumber()] = N; - } - - // Topological sort the CFG, with additional constraints: - // - Between a loop header and the last block in the loop, there can be - // no blocks not dominated by the loop header. - // - It's desirable to preserve the original block order when possible. - // We use two ready lists; Preferred and Ready. Preferred has recently - // processed sucessors, to help preserve block sequences from the original - // order. Ready has the remaining ready blocks. - PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>, - CompareBlockNumbers> - Preferred; - PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>, - CompareBlockNumbersBackwards> - Ready; - SmallVector<Entry, 4> Loops; - for (MachineBasicBlock *MBB = &MF.front();;) { - const MachineLoop *L = MLI.getLoopFor(MBB); - if (L) { - // If MBB is a loop header, add it to the active loop list. We can't put - // any blocks that it doesn't dominate until we see the end of the loop. - if (L->getHeader() == MBB) - Loops.push_back(Entry(L)); - // For each active loop the block is in, decrement the count. If MBB is - // the last block in an active loop, take it off the list and pick up any - // blocks deferred because the header didn't dominate them. - for (Entry &E : Loops) - if (E.Loop->contains(MBB) && --E.NumBlocksLeft == 0) - for (auto DeferredBlock : E.Deferred) - Ready.push(DeferredBlock); - while (!Loops.empty() && Loops.back().NumBlocksLeft == 0) - Loops.pop_back(); - } - // The main topological sort logic. - for (MachineBasicBlock *Succ : MBB->successors()) { - // Ignore backedges. - if (MachineLoop *SuccL = MLI.getLoopFor(Succ)) - if (SuccL->getHeader() == Succ && SuccL->contains(MBB)) - continue; - // Decrement the predecessor count. If it's now zero, it's ready. - if (--NumPredsLeft[Succ->getNumber()] == 0) - Preferred.push(Succ); - } - // Determine the block to follow MBB. First try to find a preferred block, - // to preserve the original block order when possible. - MachineBasicBlock *Next = nullptr; - while (!Preferred.empty()) { - Next = Preferred.top(); - Preferred.pop(); - // If X isn't dominated by the top active loop header, defer it until that - // loop is done. - if (!Loops.empty() && - !MDT.dominates(Loops.back().Loop->getHeader(), Next)) { - Loops.back().Deferred.push_back(Next); - Next = nullptr; - continue; - } - // If Next was originally ordered before MBB, and it isn't because it was - // loop-rotated above the header, it's not preferred. - if (Next->getNumber() < MBB->getNumber() && - (!L || !L->contains(Next) || - L->getHeader()->getNumber() < Next->getNumber())) { - Ready.push(Next); - Next = nullptr; - continue; - } - break; - } - // If we didn't find a suitable block in the Preferred list, check the - // general Ready list. - if (!Next) { - // If there are no more blocks to process, we're done. - if (Ready.empty()) { - MaybeUpdateTerminator(MBB); - break; - } - for (;;) { - Next = Ready.top(); - Ready.pop(); - // If Next isn't dominated by the top active loop header, defer it until - // that loop is done. - if (!Loops.empty() && - !MDT.dominates(Loops.back().Loop->getHeader(), Next)) { - Loops.back().Deferred.push_back(Next); - continue; - } - break; - } - } - // Move the next block into place and iterate. - Next->moveAfter(MBB); - MaybeUpdateTerminator(MBB); - MBB = Next; - } - assert(Loops.empty() && "Active loop list not finished"); - MF.RenumberBlocks(); - -#ifndef NDEBUG - 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) { - 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 { - // Not a loop header. All predecessors should be sorted above. - for (auto Pred : MBB.predecessors()) - assert(Pred->getNumber() < MBB.getNumber() && - "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 -} - /// Test whether Pred has any terminators explicitly branching to MBB, as /// opposed to falling through. Note that it's possible (eg. in unoptimized /// code) for a branch instruction to both branch to a block and fallthrough @@ -488,6 +270,15 @@ static void FixEndsAtEndOfFunction( } } +// WebAssembly functions end with an end instruction, as if the function body +// were a block. +static void AppendEndToFunction( + MachineFunction &MF, + const WebAssemblyInstrInfo &TII) { + BuildMI(MF.back(), MF.back().end(), DebugLoc(), + TII.get(WebAssembly::END_FUNCTION)); +} + /// Insert LOOP and BLOCK markers at appropriate places. static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI, const WebAssemblyInstrInfo &TII, @@ -555,6 +346,11 @@ static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI, // Fix up block/loop signatures at the end of the function to conform to // WebAssembly's rules. FixEndsAtEndOfFunction(MF, MFI, BlockTops, LoopTops); + + // Add an end instruction at the end of the function body. + if (!MF.getSubtarget<WebAssemblySubtarget>() + .getTargetTriple().isOSBinFormatELF()) + AppendEndToFunction(MF, TII); } bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { @@ -569,9 +365,6 @@ bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); MF.getRegInfo().invalidateLiveness(); - // Sort the blocks, with contiguous loops. - SortBlocks(MF, MLI, MDT); - // Place the BLOCK and LOOP markers to indicate the beginnings of scopes. PlaceMarkers(MF, MLI, TII, MDT, MFI); |
