Index: lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp =================================================================== --- lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp +++ 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,19 +47,51 @@ StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesCFG(); AU.addRequired(); - AU.addPreserved(); AU.addRequired(); - AU.addPreserved(); + AU.addRequired(); 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 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 BeginToEnd; + // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY. + DenseMap EndToBegin; + // map + DenseMap TryToEHPad; + // map + DenseMap EHPadToTry; + // map + DenseMap BeginToBottom; + + // Helper functions to register / unregister scope information created by + // marker instructions. + void registerScope(MachineInstr *Begin, MachineInstr *End); + void registerTryScope(MachineInstr *Begin, MachineInstr *End, + MachineBasicBlock *EHPad); + void unregisterScope(MachineInstr *Begin); + + 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 @@ -73,22 +112,123 @@ 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. +static MachineBasicBlock::iterator +GetEarliestInsertPos(MachineBasicBlock *MBB, + const SmallPtrSet &BeforeSet, + const SmallPtrSet &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. +static MachineBasicBlock::iterator +GetLatestInsertPos(MachineBasicBlock *MBB, + const SmallPtrSet &BeforeSet, + const SmallPtrSet &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; +} + +void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) { + assert(BeginToEnd.count(Begin)); + MachineInstr *End = BeginToEnd[Begin]; + assert(EndToBegin.count(End)); + BeginToEnd.erase(Begin); + EndToBegin.erase(End); + MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin); + if (EHPad) { + assert(EHPadToTry.count(EHPad)); + TryToEHPad.erase(Begin); + EHPadToTry.erase(EHPad); + } + MachineBasicBlock *Bottom = BeginToBottom.lookup(Begin); + if (Bottom) + BeginToBottom.erase(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(); + const auto &WEI = getAnalysis(); + 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 &ScopeTops, - DenseMap &BlockTops, - DenseMap &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(); + const auto &TII = *MF.getSubtarget().getInstrInfo(); + const auto &MFI = *MF.getInfo(); + // 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. @@ -125,43 +265,89 @@ } // 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 BeforeSet; + // Instructions that should go after the BLOCK. + SmallPtrSet 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 (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 +357,11 @@ } /// 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, - DenseMap &LoopTops, - const WebAssemblyInstrInfo &TII, const MachineLoopInfo &MLI) { +void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { + MachineFunction &MF = *MBB.getParent(); + const auto &MLI = getAnalysis(); + const auto &TII = *MF.getSubtarget().getInstrInfo(); + MachineLoop *Loop = MLI.getLoopFor(&MBB); if (!Loop || Loop->getHeader() != &MBB) return; @@ -193,22 +379,43 @@ } 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 BeforeSet; + SmallPtrSet 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 +424,176 @@ 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(); + const auto &TII = *MF.getSubtarget().getInstrInfo(); + const auto &WEI = getAnalysis(); + const auto &MFI = *MF.getInfo(); + + // 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 BeforeSet; + // Instructions that should go after the BLOCK. + SmallPtrSet 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 (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 &Stack, const MachineBasicBlock *MBB) { @@ -237,11 +614,8 @@ /// 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 &BlockTops, - DenseMap &LoopTops) { +void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { + const auto &MFI = *MF.getInfo(); assert(MFI.getResults().size() <= 1); if (MFI.getResults().empty()) @@ -266,11 +640,11 @@ 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. @@ -290,51 +664,87 @@ } /// 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 ScopeTops(MF.getNumBlockIDs() + 1); - - // For each LOOP_END, the corresponding LOOP. - DenseMap LoopTops; - - // For each END_BLOCK, the corresponding BLOCK. - DenseMap 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); - } +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().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 Stack; + SmallVector 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: + 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(Stack.size()); + MI.eraseFromParent(); + I = MachineBasicBlock::reverse_iterator(Rethrow); + break; + } + default: if (MI.isTerminator()) { // Rewrite MBB operands to be depth immediates. @@ -352,15 +762,15 @@ } } 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. - if (!MF.getSubtarget() - .getTargetTriple().isOSBinFormatELF()) - AppendEndToFunction(MF, TII); +void WebAssemblyCFGStackify::releaseMemory() { + ScopeTops.clear(); + BeginToEnd.clear(); + EndToBegin.clear(); + TryToEHPad.clear(); + EHPadToTry.clear(); + BeginToBottom.clear(); } bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { @@ -368,15 +778,27 @@ "********** Function: " << MF.getName() << '\n'); - const auto &MLI = getAnalysis(); - auto &MDT = getAnalysis(); + releaseMemory(); + // Liveness is not tracked for VALUE_STACK physreg. - const auto &TII = *MF.getSubtarget().getInstrInfo(); - WebAssemblyFunctionInfo &MFI = *MF.getInfo(); 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().getInstrInfo(); + if (!MF.getSubtarget() + .getTargetTriple() + .isOSBinFormatELF()) + AppendEndToFunction(MF, TII); return true; } Index: test/CodeGen/WebAssembly/cfg-stackify-eh.mir =================================================================== --- /dev/null +++ test/CodeGen/WebAssembly/cfg-stackify-eh.mir @@ -0,0 +1,322 @@ +# RUN: llc -mtriple=wasm32-unknown-unknown -exception-model=wasm -run-pass wasm-cfg-stackify %s -o - | FileCheck %s + +--- | + target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128" + target triple = "wasm32-unknown-unknown" + + @__wasm_lpad_context = external global { i32, i8*, i32 } + + declare void @may_throw() + ; Function Attrs: nounwind + declare void @dont_throw() #0 + declare i8* @__cxa_begin_catch(i8*) + declare void @__cxa_end_catch() + declare void @__cxa_rethrow() + ; Function Attrs: nounwind + declare i32 @__gxx_wasm_personality_v0(...) + declare i32 @_Unwind_CallPersonality(i8*) #0 + + define void @test0() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { + unreachable + } + define void @test1() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { + unreachable + } + define void @test2() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { + unreachable + } + define void @test3() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) { + unreachable + } + + attributes #0 = { nounwind } + +--- +# Simplest try-catch +# try { +# may_throw(); +# } catch (...) { +# } +name: test0 +# CHECK-LABEL: name: test0 +liveins: + - { reg: '$arguments', reg: '$value_stack' } +body: | + bb.0: + successors: %bb.2, %bb.1 + + CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + BR %bb.2, implicit-def $arguments + ; CHECK-LABEL: bb.0: + ; CHECK: TRY + ; CHECK-NEXT: CALL_VOID @may_throw + + bb.1 (landing-pad): + ; predecessors: %bb.0 + successors: %bb.2 + + %2:i32 = CATCH_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %3:i32 = CALL_I32 @__cxa_begin_catch, %2:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def $value_stack, implicit $value_stack + DROP_I32 killed %3:i32, implicit-def $arguments + CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + + bb.2: + ; predecessors: %bb.0, %bb.1 + + RETURN_VOID implicit-def dead $arguments + ; CHECK-LABEL: bb.2: + ; CHECK-NEXT: END_TRY + ; CHECK: RETURN_VOID +... +--- + +# Nested try-catch inside another catch +# try { +# may_throw(); +# } catch (int n) { +# try { +# may_throw(); +# } catch (int n) { +# } +# } +name: test1 +# CHECK-LABEL: name: test1 +liveins: + - { reg: '$arguments', reg: '$value_stack' } +body: | + bb.0: + successors: %bb.9, %bb.1 + + CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + BR %bb.9, implicit-def $arguments + ; CHECK-LABEL: bb.0: + ; CHECK: TRY + ; CHECK-NEXT: CALL_VOID @may_throw + + bb.1 (landing-pad): + ; predecessors: %bb.0 + successors: %bb.2, %bb.7 + + %30:i32 = CATCH_I32 0, implicit-def dead $arguments + SET_LOCAL_I32 0, %30:i32, implicit-def $arguments + %16:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %27:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + STORE_I32 2, @__wasm_lpad_context + 4, %16:i32, %27:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (store 4 into `i8** getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 1)`) + %26:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %25:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + STORE_I32 2, @__wasm_lpad_context, %26:i32, %25:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (store 4 into `i32* getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 0)`) + %32:i32 = GET_LOCAL_I32 0, implicit-def $arguments + %31:i32 = CALL_I32 @_Unwind_CallPersonality, %32:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + DROP_I32 killed %31:i32, implicit-def $arguments + %24:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %17:i32 = LOAD_I32 2, @__wasm_lpad_context + 8, %24:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (dereferenceable load 4 from `i32* getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 2)`) + %18:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %19:i32 = NE_I32 %17:i32, %18:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + BR_IF %bb.7, %19:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack + + bb.2: + ; predecessors: %bb.1 + successors: %bb.8, %bb.3, %bb.6 + + %34:i32 = GET_LOCAL_I32 0, implicit-def $arguments + %33:i32 = CALL_I32 @__cxa_begin_catch, %34:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + DROP_I32 killed %33:i32, implicit-def $arguments + CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + BR %bb.8, implicit-def $arguments + ; CHECK-LABEL: bb.2: + ; CHECK: DROP_I32 + ; CHECK-NEXT: TRY + ; CHECK-NEXT: TRY + ; CHECK-NEXT: CALL_VOID @may_throw + + bb.3 (landing-pad): + ; predecessors: %bb.2 + successors: %bb.4, %bb.5 + + %35:i32 = CATCH_I32 0, implicit-def dead $arguments + SET_LOCAL_I32 0, %35:i32, implicit-def $arguments + %21:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %20:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + STORE_I32 2, @__wasm_lpad_context, %21:i32, %20:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (store 4 into `i32* getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 0)`) + %37:i32 = GET_LOCAL_I32 0, implicit-def $arguments + %36:i32 = CALL_I32 @_Unwind_CallPersonality, %37:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + DROP_I32 killed %36:i32, implicit-def $arguments + %29:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %22:i32 = LOAD_I32 2, @__wasm_lpad_context + 8, %29:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (dereferenceable load 4 from `i32* getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 2)`) + %28:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %23:i32 = NE_I32 %22:i32, %28:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + BR_IF %bb.5, %23:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack + + bb.4: + ; predecessors: %bb.3 + successors: %bb.8 + + %39:i32 = GET_LOCAL_I32 0, implicit-def $arguments + %38:i32 = CALL_I32 @__cxa_begin_catch, %39:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + DROP_I32 killed %38:i32, implicit-def $arguments + CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + BR %bb.8, implicit-def $arguments + + bb.5: + ; predecessors: %bb.3 + successors: %bb.6 + + CALL_VOID @__cxa_rethrow, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + RETHROW %bb.6, implicit-def $arguments + + bb.6 (landing-pad): + ; predecessors: %bb.2, %bb.5 + + CATCH_ALL implicit-def $arguments + CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + RETHROW_TO_CALLER implicit-def $arguments + ; CHECK-LABEL: bb.6 (landing-pad): + ; CHECK-NEXT: END_TRY + + bb.7: + ; predecessors: %bb.1 + + CALL_VOID @__cxa_rethrow, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + RETHROW_TO_CALLER implicit-def $arguments + ; CHECK-LABEL: bb.7: + ; CHECK-NEXT: END_TRY + ; CHECK: RETHROW 3 + + bb.8: + ; predecessors: %bb.2, %bb.4 + successors: %bb.9 + + CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + + bb.9: + ; predecessors: %bb.0, %bb.8 + + RETURN_VOID implicit-def dead $arguments + ; CHECK-LABEL: bb.9: + ; CHECK-NEXT: END_TRY +... +--- + +# A loop within a try. +# try { +# for (int i = 0; i < n; ++i) +# may_throw(); +# } catch (...) { +# } +name: test2 +# CHECK-LABEL: name: test2 +liveins: + - { reg: '$arguments', reg: '$value_stack' } +body: | + bb.0: + successors: %bb.1, %bb.4 + + %18:i32 = CONST_I32 0, implicit-def dead $arguments + SET_LOCAL_I32 1, %18:i32, implicit-def $arguments + %14:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %19:i32 = GET_LOCAL_I32 0, implicit-def $arguments + %9:i32 = GE_S_I32 %14:i32, %19:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + BR_IF %bb.4, %9:i32, implicit-def $arguments + + bb.1: + ; predecessors: %bb.0, %bb.3 + successors: %bb.3, %bb.2 + + CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + BR %bb.3, implicit-def $arguments + ; CHECK-LABEL: bb.1: + ; CHECK: LOOP + ; CHECK: TRY + ; CHECK-NEXT: CALL_VOID @may_throw + + bb.2 (landing-pad): + ; predecessors: %bb.1 + successors: %bb.4 + + %11:i32 = CATCH_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %22:i32 = CALL_I32 @__cxa_begin_catch, %11:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def $value_stack, implicit $value_stack + DROP_I32 killed %22:i32, implicit-def $arguments + CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + BR %bb.4, implicit-def $arguments + + bb.3: + ; predecessors: %bb.1 + successors: %bb.1, %bb.4 + + %20:i32 = GET_LOCAL_I32 1, implicit-def $arguments + %17:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %16:i32 = ADD_I32 %20:i32, %17:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %15:i32 = TEE_LOCAL_I32 1, %16:i32, implicit-def $arguments + %21:i32 = GET_LOCAL_I32 0, implicit-def $arguments + %10:i32 = GE_S_I32 %15:i32, %21:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + BR_UNLESS %bb.1, %10:i32, implicit-def $arguments + ; CHECK-LABEL: bb.3: + ; CHECK: END_TRY + + bb.4: + ; predecessors: %bb.2, %bb.0, %bb.3 + + RETURN_VOID implicit-def dead $arguments +... +--- + +# A loop within a catch +# try { +# may_throw(); +# } catch (...) { +# for (int i = 0; i < n; ++i) +# dont_throw(); +# } +name: test3 +# CHECK-LABEL: name: test3 +liveins: + - { reg: '$arguments', reg: '$value_stack' } +body: | + bb.0: + successors: %bb.4, %bb.1 + + CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + BR %bb.4, implicit-def $arguments + ; CHECK-LABEL: bb.0: + ; CHECK: TRY + ; CHECK-NEXT: CALL_VOID @may_throw + + bb.1 (landing-pad): + ; predecessors: %bb.0 + successors: %bb.2, %bb.3 + + %9:i32 = CATCH_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %18:i32 = CALL_I32 @__cxa_begin_catch, %9:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def $value_stack, implicit $value_stack + DROP_I32 killed %18:i32, implicit-def $arguments + %19:i32 = CONST_I32 0, implicit-def dead $arguments + SET_LOCAL_I32 1, %19:i32, implicit-def $arguments + %14:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %20:i32 = GET_LOCAL_I32 0, implicit-def $arguments + %10:i32 = GE_S_I32 %14:i32, %20:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + BR_IF %bb.3, %10:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack + + bb.2: + ; predecessors: %bb.1, %bb.2 + successors: %bb.2, %bb.3 + + CALL_VOID @dont_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + %21:i32 = GET_LOCAL_I32 1, implicit-def $arguments + %17:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %16:i32 = ADD_I32 %21:i32, %17:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + %15:i32 = TEE_LOCAL_I32 1, %16:i32, implicit-def $arguments + %22:i32 = GET_LOCAL_I32 0, implicit-def $arguments + %11:i32 = GE_S_I32 %15:i32, %22:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack + BR_UNLESS %bb.2, %11:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack + + bb.3: + ; predecessors: %bb.1, %bb.2 + successors: %bb.4 + + CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64 + + bb.4: + ; predecessors: %bb.0, %bb.3 + + RETURN_VOID implicit-def dead $arguments + ; CHECK-LABEL: bb.4: + ; CHECK: END_TRY