diff options
Diffstat (limited to 'contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp')
| -rw-r--r-- | contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp | 693 |
1 files changed, 570 insertions, 123 deletions
diff --git a/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp b/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp index 70ce40cefed7..f8f5f4040c86 100644 --- a/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp +++ b/contrib/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp @@ -10,16 +10,21 @@ /// \file /// This file implements a CFG stacking pass. /// -/// 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 pass inserts BLOCK, LOOP, and TRY 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 /// WebAssembly, provided that all loops are single-entry. /// +/// In case we use exceptions, this pass also fixes mismatches in unwind +/// destinations created during transforming CFG into wasm structured format. +/// //===----------------------------------------------------------------------===// #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" #include "WebAssembly.h" +#include "WebAssemblyExceptionInfo.h" #include "WebAssemblyMachineFunctionInfo.h" #include "WebAssemblySubtarget.h" #include "WebAssemblyUtilities.h" @@ -29,6 +34,8 @@ #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/WasmEHFuncInfo.h" +#include "llvm/MC/MCAsmInfo.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; @@ -40,26 +47,57 @@ class WebAssemblyCFGStackify final : public MachineFunctionPass { StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesCFG(); AU.addRequired<MachineDominatorTree>(); - AU.addPreserved<MachineDominatorTree>(); AU.addRequired<MachineLoopInfo>(); - AU.addPreserved<MachineLoopInfo>(); + AU.addRequired<WebAssemblyExceptionInfo>(); MachineFunctionPass::getAnalysisUsage(AU); } bool runOnMachineFunction(MachineFunction &MF) override; + // 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. + SmallVector<MachineBasicBlock *, 8> ScopeTops; + + void placeMarkers(MachineFunction &MF); + void placeBlockMarker(MachineBasicBlock &MBB); + void placeLoopMarker(MachineBasicBlock &MBB); + void placeTryMarker(MachineBasicBlock &MBB); + void rewriteDepthImmediates(MachineFunction &MF); + void fixEndsAtEndOfFunction(MachineFunction &MF); + + // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY). + DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd; + // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY. + DenseMap<const MachineInstr *, MachineInstr *> EndToBegin; + // <TRY marker, EH pad> map + DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad; + // <EH pad, TRY marker> map + DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry; + // <LOOP|TRY marker, Loop/exception bottom BB> map + DenseMap<const MachineInstr *, MachineBasicBlock *> BeginToBottom; + + // Helper functions to register scope information created by marker + // instructions. + void registerScope(MachineInstr *Begin, MachineInstr *End); + void registerTryScope(MachineInstr *Begin, MachineInstr *End, + MachineBasicBlock *EHPad); + + MachineBasicBlock *getBottom(const MachineInstr *Begin); + public: static char ID; // Pass identification, replacement for typeid WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} + ~WebAssemblyCFGStackify() override { releaseMemory(); } + void releaseMemory() override; }; } // end anonymous namespace char WebAssemblyCFGStackify::ID = 0; INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, - "Insert BLOCK and LOOP markers for WebAssembly scopes", - false, false) + "Insert BLOCK and LOOP markers for WebAssembly scopes", false, + false) FunctionPass *llvm::createWebAssemblyCFGStackify() { return new WebAssemblyCFGStackify(); @@ -73,34 +111,121 @@ FunctionPass *llvm::createWebAssemblyCFGStackify() { static bool ExplicitlyBranchesTo(MachineBasicBlock *Pred, MachineBasicBlock *MBB) { for (MachineInstr &MI : Pred->terminators()) - for (MachineOperand &MO : MI.explicit_operands()) - if (MO.isMBB() && MO.getMBB() == MBB) - return true; + // Even if a rethrow takes a BB argument, it is not a branch + if (!WebAssembly::isRethrow(MI)) + for (MachineOperand &MO : MI.explicit_operands()) + if (MO.isMBB() && MO.getMBB() == MBB) + return true; return false; } +// Returns an iterator to the earliest position possible within the MBB, +// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet +// contains instructions that should go before the marker, and AfterSet contains +// ones that should go after the marker. In this function, AfterSet is only +// used for sanity checking. +static MachineBasicBlock::iterator +GetEarliestInsertPos(MachineBasicBlock *MBB, + const SmallPtrSet<const MachineInstr *, 4> &BeforeSet, + const SmallPtrSet<const MachineInstr *, 4> &AfterSet) { + auto InsertPos = MBB->end(); + while (InsertPos != MBB->begin()) { + if (BeforeSet.count(&*std::prev(InsertPos))) { +#ifndef NDEBUG + // Sanity check + for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos) + assert(!AfterSet.count(&*std::prev(Pos))); +#endif + break; + } + --InsertPos; + } + return InsertPos; +} + +// Returns an iterator to the latest position possible within the MBB, +// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet +// contains instructions that should go before the marker, and AfterSet contains +// ones that should go after the marker. In this function, BeforeSet is only +// used for sanity checking. +static MachineBasicBlock::iterator +GetLatestInsertPos(MachineBasicBlock *MBB, + const SmallPtrSet<const MachineInstr *, 4> &BeforeSet, + const SmallPtrSet<const MachineInstr *, 4> &AfterSet) { + auto InsertPos = MBB->begin(); + while (InsertPos != MBB->end()) { + if (AfterSet.count(&*InsertPos)) { +#ifndef NDEBUG + // Sanity check + for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos) + assert(!BeforeSet.count(&*Pos)); +#endif + break; + } + ++InsertPos; + } + return InsertPos; +} + +void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin, + MachineInstr *End) { + BeginToEnd[Begin] = End; + EndToBegin[End] = Begin; +} + +void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin, + MachineInstr *End, + MachineBasicBlock *EHPad) { + registerScope(Begin, End); + TryToEHPad[Begin] = EHPad; + EHPadToTry[EHPad] = Begin; +} + +// Given a LOOP/TRY marker, returns its bottom BB. Use cached information if any +// to prevent recomputation. +MachineBasicBlock * +WebAssemblyCFGStackify::getBottom(const MachineInstr *Begin) { + const auto &MLI = getAnalysis<MachineLoopInfo>(); + const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); + if (BeginToBottom.count(Begin)) + return BeginToBottom[Begin]; + if (Begin->getOpcode() == WebAssembly::LOOP) { + MachineLoop *L = MLI.getLoopFor(Begin->getParent()); + assert(L); + BeginToBottom[Begin] = WebAssembly::getBottom(L); + } else if (Begin->getOpcode() == WebAssembly::TRY) { + WebAssemblyException *WE = WEI.getExceptionFor(TryToEHPad[Begin]); + assert(WE); + BeginToBottom[Begin] = WebAssembly::getBottom(WE); + } else + assert(false); + return BeginToBottom[Begin]; +} + /// Insert a BLOCK marker for branches to MBB (if needed). -static void PlaceBlockMarker( - MachineBasicBlock &MBB, MachineFunction &MF, - SmallVectorImpl<MachineBasicBlock *> &ScopeTops, - DenseMap<const MachineInstr *, MachineInstr *> &BlockTops, - DenseMap<const MachineInstr *, MachineInstr *> &LoopTops, - const WebAssemblyInstrInfo &TII, - const MachineLoopInfo &MLI, - MachineDominatorTree &MDT, - WebAssemblyFunctionInfo &MFI) { +void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) { + // This should have been handled in placeTryMarker. + if (MBB.isEHPad()) + return; + + MachineFunction &MF = *MBB.getParent(); + auto &MDT = getAnalysis<MachineDominatorTree>(); + const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); + const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); + // 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()) + for (MachineBasicBlock *Pred : MBB.predecessors()) { if (Pred->getNumber() < MBBNumber) { Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; if (ExplicitlyBranchesTo(Pred, &MBB)) IsBranchedTo = true; } + } if (!Header) return; if (!IsBranchedTo) @@ -125,43 +250,93 @@ static void PlaceBlockMarker( } // Decide where in Header to put the BLOCK. - MachineBasicBlock::iterator InsertPos; - MachineLoop *HeaderLoop = MLI.getLoopFor(Header); - if (HeaderLoop && - MBB.getNumber() > WebAssembly::getBottom(HeaderLoop)->getNumber()) { - // Header is the header of a loop that does not lexically contain MBB, so - // the BLOCK needs to be above the LOOP, after any END constructs. - InsertPos = Header->begin(); - while (InsertPos->getOpcode() == WebAssembly::END_BLOCK || - InsertPos->getOpcode() == WebAssembly::END_LOOP) - ++InsertPos; - } else { - // Otherwise, insert the BLOCK as late in Header as we can, but before the - // beginning of the local expression tree and any nested BLOCKs. - InsertPos = Header->getFirstTerminator(); - while (InsertPos != Header->begin() && - WebAssembly::isChild(*std::prev(InsertPos), MFI) && - std::prev(InsertPos)->getOpcode() != WebAssembly::LOOP && - std::prev(InsertPos)->getOpcode() != WebAssembly::END_BLOCK && - std::prev(InsertPos)->getOpcode() != WebAssembly::END_LOOP) - --InsertPos; + + // Instructions that should go before the BLOCK. + SmallPtrSet<const MachineInstr *, 4> BeforeSet; + // Instructions that should go after the BLOCK. + SmallPtrSet<const MachineInstr *, 4> AfterSet; + for (const auto &MI : *Header) { + // If there is a previously placed LOOP/TRY marker and the bottom block of + // the loop/exception is above MBB, it should be after the BLOCK, because + // the loop/exception is nested in this block. Otherwise it should be before + // the BLOCK. + if (MI.getOpcode() == WebAssembly::LOOP || + MI.getOpcode() == WebAssembly::TRY) { + if (MBB.getNumber() > getBottom(&MI)->getNumber()) + AfterSet.insert(&MI); +#ifndef NDEBUG + else + BeforeSet.insert(&MI); +#endif + } + + // All previously inserted BLOCK markers should be after the BLOCK because + // they are all nested blocks. + if (MI.getOpcode() == WebAssembly::BLOCK) + AfterSet.insert(&MI); + +#ifndef NDEBUG + // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK. + if (MI.getOpcode() == WebAssembly::END_BLOCK || + MI.getOpcode() == WebAssembly::END_LOOP || + MI.getOpcode() == WebAssembly::END_TRY) + BeforeSet.insert(&MI); +#endif + + // Terminators should go after the BLOCK. + if (MI.isTerminator()) + AfterSet.insert(&MI); + } + + // Local expression tree should go after the BLOCK. + for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; + --I) { + if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) + continue; + if (WebAssembly::isChild(*std::prev(I), MFI)) + AfterSet.insert(&*std::prev(I)); + else + break; } // Add the BLOCK. + auto InsertPos = GetLatestInsertPos(Header, BeforeSet, AfterSet); MachineInstr *Begin = BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), TII.get(WebAssembly::BLOCK)) .addImm(int64_t(WebAssembly::ExprType::Void)); + // Decide where in Header to put the END_BLOCK. + BeforeSet.clear(); + AfterSet.clear(); + for (auto &MI : MBB) { +#ifndef NDEBUG + // END_BLOCK should precede existing LOOP and TRY markers. + if (MI.getOpcode() == WebAssembly::LOOP || + MI.getOpcode() == WebAssembly::TRY) + AfterSet.insert(&MI); +#endif + + // If there is a previously placed END_LOOP marker and the header of the + // loop is above this block's header, the END_LOOP should be placed after + // the BLOCK, because the loop contains this block. Otherwise the END_LOOP + // should be placed before the BLOCK. The same for END_TRY. + if (MI.getOpcode() == WebAssembly::END_LOOP || + MI.getOpcode() == WebAssembly::END_TRY) { + if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) + BeforeSet.insert(&MI); +#ifndef NDEBUG + else + AfterSet.insert(&MI); +#endif + } + } + // Mark the end of the block. - InsertPos = MBB.begin(); - while (InsertPos != MBB.end() && - InsertPos->getOpcode() == WebAssembly::END_LOOP && - LoopTops[&*InsertPos]->getParent()->getNumber() >= Header->getNumber()) - ++InsertPos; + InsertPos = GetEarliestInsertPos(&MBB, BeforeSet, AfterSet); MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos), TII.get(WebAssembly::END_BLOCK)); - BlockTops[End] = Begin; + registerScope(Begin, End); // Track the farthest-spanning scope that ends at this point. int Number = MBB.getNumber(); @@ -171,11 +346,11 @@ static void PlaceBlockMarker( } /// 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, - DenseMap<const MachineInstr *, MachineInstr *> &LoopTops, - const WebAssemblyInstrInfo &TII, const MachineLoopInfo &MLI) { +void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { + MachineFunction &MF = *MBB.getParent(); + const auto &MLI = getAnalysis<MachineLoopInfo>(); + const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); + MachineLoop *Loop = MLI.getLoopFor(&MBB); if (!Loop || Loop->getHeader() != &MBB) return; @@ -193,22 +368,43 @@ static void PlaceLoopMarker( } MachineBasicBlock *AfterLoop = &*Iter; - // Mark the beginning of the loop (after the end of any existing loop that - // ends here). - auto InsertPos = MBB.begin(); - while (InsertPos != MBB.end() && - InsertPos->getOpcode() == WebAssembly::END_LOOP) - ++InsertPos; + // Decide where in Header to put the LOOP. + SmallPtrSet<const MachineInstr *, 4> BeforeSet; + SmallPtrSet<const MachineInstr *, 4> AfterSet; + for (const auto &MI : MBB) { + // LOOP marker should be after any existing loop that ends here. Otherwise + // we assume the instruction belongs to the loop. + if (MI.getOpcode() == WebAssembly::END_LOOP) + BeforeSet.insert(&MI); +#ifndef NDEBUG + else + AfterSet.insert(&MI); +#endif + } + + // Mark the beginning of the loop. + auto InsertPos = GetEarliestInsertPos(&MBB, BeforeSet, AfterSet); MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos), TII.get(WebAssembly::LOOP)) .addImm(int64_t(WebAssembly::ExprType::Void)); - // Mark the end of the loop (using arbitrary debug location that branched - // to the loop end as its location). + // Decide where in Header to put the END_LOOP. + BeforeSet.clear(); + AfterSet.clear(); +#ifndef NDEBUG + for (const auto &MI : MBB) + // Existing END_LOOP markers belong to parent loops of this loop + if (MI.getOpcode() == WebAssembly::END_LOOP) + AfterSet.insert(&MI); +#endif + + // Mark the end of the loop (using arbitrary debug location that branched to + // the loop end as its location). + InsertPos = GetEarliestInsertPos(AfterLoop, BeforeSet, AfterSet); DebugLoc EndDL = (*AfterLoop->pred_rbegin())->findBranchDebugLoc(); - MachineInstr *End = BuildMI(*AfterLoop, AfterLoop->begin(), EndDL, - TII.get(WebAssembly::END_LOOP)); - LoopTops[End] = Begin; + MachineInstr *End = + BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP)); + registerScope(Begin, End); assert((!ScopeTops[AfterLoop->getNumber()] || ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) && @@ -217,6 +413,183 @@ static void PlaceLoopMarker( ScopeTops[AfterLoop->getNumber()] = &MBB; } +void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) { + if (!MBB.isEHPad()) + return; + + // catch_all terminate pad is grouped together with catch terminate pad and + // does not need a separate TRY and END_TRY marker. + if (WebAssembly::isCatchAllTerminatePad(MBB)) + return; + + MachineFunction &MF = *MBB.getParent(); + auto &MDT = getAnalysis<MachineDominatorTree>(); + const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); + const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); + const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); + + // Compute the nearest common dominator of all unwind predecessors + MachineBasicBlock *Header = nullptr; + int MBBNumber = MBB.getNumber(); + for (auto *Pred : MBB.predecessors()) { + if (Pred->getNumber() < MBBNumber) { + Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; + assert(!ExplicitlyBranchesTo(Pred, &MBB) && + "Explicit branch to an EH pad!"); + } + } + if (!Header) + return; + + // If this try is at the bottom of the function, insert a dummy block at the + // end. + WebAssemblyException *WE = WEI.getExceptionFor(&MBB); + assert(WE); + MachineBasicBlock *Bottom = WebAssembly::getBottom(WE); + + auto Iter = std::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 = std::next(MachineFunction::iterator(Bottom)); + } + MachineBasicBlock *AfterTry = &*Iter; + + assert(AfterTry != &MF.front()); + MachineBasicBlock *LayoutPred = + &*std::prev(MachineFunction::iterator(AfterTry)); + + // 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 = std::next(MachineFunction::iterator(ScopeTop)); + } else { + // We found a scope level at an appropriate depth. + Header = ScopeTop; + break; + } + } + } + + // Decide where in Header to put the TRY. + + // Instructions that should go before the BLOCK. + SmallPtrSet<const MachineInstr *, 4> BeforeSet; + // Instructions that should go after the BLOCK. + SmallPtrSet<const MachineInstr *, 4> AfterSet; + for (const auto &MI : *Header) { + // If there is a previously placed LOOP marker and the bottom block of + // the loop is above MBB, the LOOP should be after the TRY, because the + // loop is nested in this try. Otherwise it should be before the TRY. + if (MI.getOpcode() == WebAssembly::LOOP) { + if (MBB.getNumber() > Bottom->getNumber()) + AfterSet.insert(&MI); +#ifndef NDEBUG + else + BeforeSet.insert(&MI); +#endif + } + + // All previously inserted TRY markers should be after the TRY because they + // are all nested trys. + if (MI.getOpcode() == WebAssembly::TRY) + AfterSet.insert(&MI); + +#ifndef NDEBUG + // All END_(LOOP/TRY) markers should be before the TRY. + if (MI.getOpcode() == WebAssembly::END_LOOP || + MI.getOpcode() == WebAssembly::END_TRY) + BeforeSet.insert(&MI); +#endif + + // Terminators should go after the TRY. + if (MI.isTerminator()) + AfterSet.insert(&MI); + } + + // Local expression tree should go after the TRY. + for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; + --I) { + if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) + continue; + if (WebAssembly::isChild(*std::prev(I), MFI)) + AfterSet.insert(&*std::prev(I)); + else + break; + } + + // If Header unwinds to MBB (= Header contains 'invoke'), the try block should + // contain the call within it. So the call should go after the TRY. The + // exception is when the header's terminator is a rethrow instruction, in + // which case that instruction, not a call instruction before it, is gonna + // throw. + if (MBB.isPredecessor(Header)) { + auto TermPos = Header->getFirstTerminator(); + if (TermPos == Header->end() || !WebAssembly::isRethrow(*TermPos)) { + for (const auto &MI : reverse(*Header)) { + if (MI.isCall()) { + AfterSet.insert(&MI); + break; + } + } + } + } + + // Add the TRY. + auto InsertPos = GetLatestInsertPos(Header, BeforeSet, AfterSet); + MachineInstr *Begin = + BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), + TII.get(WebAssembly::TRY)) + .addImm(int64_t(WebAssembly::ExprType::Void)); + + // Decide where in Header to put the END_TRY. + BeforeSet.clear(); + AfterSet.clear(); + for (const auto &MI : *AfterTry) { +#ifndef NDEBUG + // END_TRY should precede existing LOOP markers. + if (MI.getOpcode() == WebAssembly::LOOP) + AfterSet.insert(&MI); + + // All END_TRY markers placed earlier belong to exceptions that contains + // this one. + if (MI.getOpcode() == WebAssembly::END_TRY) + AfterSet.insert(&MI); +#endif + + // If there is a previously placed END_LOOP marker and its header is after + // where TRY marker is, this loop is contained within the 'catch' part, so + // the END_TRY marker should go after that. Otherwise, the whole try-catch + // is contained within this loop, so the END_TRY should go before that. + if (MI.getOpcode() == WebAssembly::END_LOOP) { + if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) + BeforeSet.insert(&MI); +#ifndef NDEBUG + else + AfterSet.insert(&MI); +#endif + } + } + + // Mark the end of the TRY. + InsertPos = GetEarliestInsertPos(AfterTry, BeforeSet, AfterSet); + MachineInstr *End = + BuildMI(*AfterTry, InsertPos, Bottom->findBranchDebugLoc(), + TII.get(WebAssembly::END_TRY)); + registerTryScope(Begin, End, &MBB); + + // Track the farthest-spanning scope that ends at this point. + int Number = AfterTry->getNumber(); + if (!ScopeTops[Number] || + ScopeTops[Number]->getNumber() > Header->getNumber()) + ScopeTops[Number] = Header; +} + static unsigned GetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack, const MachineBasicBlock *MBB) { @@ -237,11 +610,8 @@ GetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack, /// that end at the function end need to have a return type signature that /// matches the function signature, even though it's unreachable. This function /// checks for such cases and fixes up the signatures. -static void FixEndsAtEndOfFunction( - MachineFunction &MF, - const WebAssemblyFunctionInfo &MFI, - DenseMap<const MachineInstr *, MachineInstr *> &BlockTops, - DenseMap<const MachineInstr *, MachineInstr *> &LoopTops) { +void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { + const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); assert(MFI.getResults().size() <= 1); if (MFI.getResults().empty()) @@ -249,16 +619,31 @@ static void FixEndsAtEndOfFunction( WebAssembly::ExprType retType; switch (MFI.getResults().front().SimpleTy) { - case MVT::i32: retType = WebAssembly::ExprType::I32; break; - case MVT::i64: retType = WebAssembly::ExprType::I64; break; - case MVT::f32: retType = WebAssembly::ExprType::F32; break; - case MVT::f64: retType = WebAssembly::ExprType::F64; break; - case MVT::v16i8: retType = WebAssembly::ExprType::I8x16; break; - case MVT::v8i16: retType = WebAssembly::ExprType::I16x8; break; - case MVT::v4i32: retType = WebAssembly::ExprType::I32x4; break; - case MVT::v4f32: retType = WebAssembly::ExprType::F32x4; break; - case MVT::ExceptRef: retType = WebAssembly::ExprType::ExceptRef; break; - default: llvm_unreachable("unexpected return type"); + case MVT::i32: + retType = WebAssembly::ExprType::I32; + break; + case MVT::i64: + retType = WebAssembly::ExprType::I64; + break; + case MVT::f32: + retType = WebAssembly::ExprType::F32; + break; + case MVT::f64: + retType = WebAssembly::ExprType::F64; + break; + case MVT::v16i8: + case MVT::v8i16: + case MVT::v4i32: + case MVT::v2i64: + case MVT::v4f32: + case MVT::v2f64: + retType = WebAssembly::ExprType::V128; + break; + case MVT::ExceptRef: + retType = WebAssembly::ExprType::ExceptRef; + break; + default: + llvm_unreachable("unexpected return type"); } for (MachineBasicBlock &MBB : reverse(MF)) { @@ -266,11 +651,11 @@ static void FixEndsAtEndOfFunction( if (MI.isPosition() || MI.isDebugInstr()) continue; if (MI.getOpcode() == WebAssembly::END_BLOCK) { - BlockTops[&MI]->getOperand(0).setImm(int32_t(retType)); + EndToBegin[&MI]->getOperand(0).setImm(int32_t(retType)); continue; } if (MI.getOpcode() == WebAssembly::END_LOOP) { - LoopTops[&MI]->getOperand(0).setImm(int32_t(retType)); + EndToBegin[&MI]->getOperand(0).setImm(int32_t(retType)); continue; } // Something other than an `end`. We're done. @@ -281,60 +666,108 @@ 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) { +static void AppendEndToFunction(MachineFunction &MF, + const WebAssemblyInstrInfo &TII) { BuildMI(MF.back(), MF.back().end(), MF.back().findPrevDebugLoc(MF.back().end()), TII.get(WebAssembly::END_FUNCTION)); } -/// Insert LOOP and BLOCK markers at appropriate places. -static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI, - const WebAssemblyInstrInfo &TII, - MachineDominatorTree &MDT, - WebAssemblyFunctionInfo &MFI) { - // 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 each LOOP_END, the corresponding LOOP. - DenseMap<const MachineInstr *, MachineInstr *> LoopTops; - - // For each END_BLOCK, the corresponding BLOCK. - DenseMap<const MachineInstr *, MachineInstr *> BlockTops; - - for (auto &MBB : MF) { - // Place the LOOP for MBB if MBB is the header of a loop. - PlaceLoopMarker(MBB, MF, ScopeTops, LoopTops, TII, MLI); - - // Place the BLOCK for MBB if MBB is branched to from above. - PlaceBlockMarker(MBB, MF, ScopeTops, BlockTops, LoopTops, TII, MLI, MDT, MFI); - } +/// Insert LOOP/TRY/BLOCK markers at appropriate places. +void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { + const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); + // 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. + ScopeTops.resize(MF.getNumBlockIDs() + 1); + // Place the LOOP for MBB if MBB is the header of a loop. + for (auto &MBB : MF) + placeLoopMarker(MBB); + // Place the TRY for MBB if MBB is the EH pad of an exception. + if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && + MF.getFunction().hasPersonalityFn()) + for (auto &MBB : MF) + placeTryMarker(MBB); + // Place the BLOCK for MBB if MBB is branched to from above. + for (auto &MBB : MF) + placeBlockMarker(MBB); +} +void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { + const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); // Now rewrite references to basic blocks to be depth immediates. + // We need two stacks: one for normal scopes and the other for EH pad scopes. + // EH pad stack is used to rewrite depths in rethrow instructions. SmallVector<const MachineBasicBlock *, 8> Stack; + SmallVector<const MachineBasicBlock *, 8> EHPadStack; for (auto &MBB : reverse(MF)) { - for (auto &MI : reverse(MBB)) { + for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) { + MachineInstr &MI = *I; switch (MI.getOpcode()) { case WebAssembly::BLOCK: - assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= MBB.getNumber() && - "Block should be balanced"); + assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= + MBB.getNumber() && + "Block/try should be balanced"); Stack.pop_back(); break; + + case WebAssembly::TRY: + assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= + MBB.getNumber() && + "Block/try marker should be balanced"); + Stack.pop_back(); + EHPadStack.pop_back(); + break; + + case WebAssembly::CATCH_I32: + case WebAssembly::CATCH_I64: + case WebAssembly::CATCH_ALL: + // Currently the only case there are more than one catch for a try is + // for catch terminate pad, in the form of + // try + // catch + // call @__clang_call_terminate + // unreachable + // catch_all + // call @std::terminate + // unreachable + // end + // So we shouldn't push the current BB for the second catch_all block + // here. + if (!WebAssembly::isCatchAllTerminatePad(MBB)) + EHPadStack.push_back(&MBB); + break; + case WebAssembly::LOOP: assert(Stack.back() == &MBB && "Loop top should be balanced"); Stack.pop_back(); break; + case WebAssembly::END_BLOCK: + case WebAssembly::END_TRY: Stack.push_back(&MBB); break; + case WebAssembly::END_LOOP: - Stack.push_back(LoopTops[&MI]->getParent()); + Stack.push_back(EndToBegin[&MI]->getParent()); + break; + + case WebAssembly::RETHROW: { + // Rewrite MBB operands to be depth immediates. + unsigned EHPadDepth = GetDepth(EHPadStack, MI.getOperand(0).getMBB()); + MI.RemoveOperand(0); + MI.addOperand(MF, MachineOperand::CreateImm(EHPadDepth)); break; + } + + case WebAssembly::RETHROW_TO_CALLER: { + MachineInstr *Rethrow = + BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(WebAssembly::RETHROW)) + .addImm(EHPadStack.size()); + MI.eraseFromParent(); + I = MachineBasicBlock::reverse_iterator(Rethrow); + break; + } + default: if (MI.isTerminator()) { // Rewrite MBB operands to be depth immediates. @@ -352,13 +785,15 @@ static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI, } } assert(Stack.empty() && "Control flow should be balanced"); +} - // 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. - AppendEndToFunction(MF, TII); +void WebAssemblyCFGStackify::releaseMemory() { + ScopeTops.clear(); + BeginToEnd.clear(); + EndToBegin.clear(); + TryToEHPad.clear(); + EHPadToTry.clear(); + BeginToBottom.clear(); } bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { @@ -366,15 +801,27 @@ bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { "********** Function: " << MF.getName() << '\n'); - const auto &MLI = getAnalysis<MachineLoopInfo>(); - auto &MDT = getAnalysis<MachineDominatorTree>(); + releaseMemory(); + // Liveness is not tracked for VALUE_STACK physreg. - const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); - WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); MF.getRegInfo().invalidateLiveness(); - // Place the BLOCK and LOOP markers to indicate the beginnings of scopes. - PlaceMarkers(MF, MLI, TII, MDT, MFI); + // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes. + placeMarkers(MF); + + // Convert MBB operands in terminators to relative depth immediates. + rewriteDepthImmediates(MF); + + // Fix up block/loop/try signatures at the end of the function to conform to + // WebAssembly's rules. + fixEndsAtEndOfFunction(MF); + + // Add an end instruction at the end of the function body. + const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); + if (!MF.getSubtarget<WebAssemblySubtarget>() + .getTargetTriple() + .isOSBinFormatELF()) + AppendEndToFunction(MF, TII); return true; } |