10b57cec5SDimitry Andric //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric /// 90b57cec5SDimitry Andric /// \file 100b57cec5SDimitry Andric /// This file implements a CFG stacking pass. 110b57cec5SDimitry Andric /// 120b57cec5SDimitry Andric /// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes, 130b57cec5SDimitry Andric /// since scope boundaries serve as the labels for WebAssembly's control 140b57cec5SDimitry Andric /// transfers. 150b57cec5SDimitry Andric /// 160b57cec5SDimitry Andric /// This is sufficient to convert arbitrary CFGs into a form that works on 170b57cec5SDimitry Andric /// WebAssembly, provided that all loops are single-entry. 180b57cec5SDimitry Andric /// 190b57cec5SDimitry Andric /// In case we use exceptions, this pass also fixes mismatches in unwind 200b57cec5SDimitry Andric /// destinations created during transforming CFG into wasm structured format. 210b57cec5SDimitry Andric /// 220b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 230b57cec5SDimitry Andric 240b57cec5SDimitry Andric #include "WebAssembly.h" 250b57cec5SDimitry Andric #include "WebAssemblyExceptionInfo.h" 260b57cec5SDimitry Andric #include "WebAssemblyMachineFunctionInfo.h" 270b57cec5SDimitry Andric #include "WebAssemblySubtarget.h" 280b57cec5SDimitry Andric #include "WebAssemblyUtilities.h" 290b57cec5SDimitry Andric #include "llvm/ADT/Statistic.h" 300b57cec5SDimitry Andric #include "llvm/CodeGen/MachineDominators.h" 310b57cec5SDimitry Andric #include "llvm/CodeGen/MachineInstrBuilder.h" 328bcb0991SDimitry Andric #include "llvm/CodeGen/MachineLoopInfo.h" 330b57cec5SDimitry Andric #include "llvm/MC/MCAsmInfo.h" 345ffd83dbSDimitry Andric #include "llvm/Target/TargetMachine.h" 350b57cec5SDimitry Andric using namespace llvm; 360b57cec5SDimitry Andric 370b57cec5SDimitry Andric #define DEBUG_TYPE "wasm-cfg-stackify" 380b57cec5SDimitry Andric 390b57cec5SDimitry Andric STATISTIC(NumUnwindMismatches, "Number of EH pad unwind mismatches found"); 400b57cec5SDimitry Andric 410b57cec5SDimitry Andric namespace { 420b57cec5SDimitry Andric class WebAssemblyCFGStackify final : public MachineFunctionPass { 430b57cec5SDimitry Andric StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } 440b57cec5SDimitry Andric 450b57cec5SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override { 460b57cec5SDimitry Andric AU.addRequired<MachineDominatorTree>(); 470b57cec5SDimitry Andric AU.addRequired<MachineLoopInfo>(); 480b57cec5SDimitry Andric AU.addRequired<WebAssemblyExceptionInfo>(); 490b57cec5SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU); 500b57cec5SDimitry Andric } 510b57cec5SDimitry Andric 520b57cec5SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override; 530b57cec5SDimitry Andric 540b57cec5SDimitry Andric // For each block whose label represents the end of a scope, record the block 550b57cec5SDimitry Andric // which holds the beginning of the scope. This will allow us to quickly skip 560b57cec5SDimitry Andric // over scoped regions when walking blocks. 570b57cec5SDimitry Andric SmallVector<MachineBasicBlock *, 8> ScopeTops; 580b57cec5SDimitry Andric 590b57cec5SDimitry Andric // Placing markers. 600b57cec5SDimitry Andric void placeMarkers(MachineFunction &MF); 610b57cec5SDimitry Andric void placeBlockMarker(MachineBasicBlock &MBB); 620b57cec5SDimitry Andric void placeLoopMarker(MachineBasicBlock &MBB); 630b57cec5SDimitry Andric void placeTryMarker(MachineBasicBlock &MBB); 640b57cec5SDimitry Andric void removeUnnecessaryInstrs(MachineFunction &MF); 650b57cec5SDimitry Andric bool fixUnwindMismatches(MachineFunction &MF); 660b57cec5SDimitry Andric void rewriteDepthImmediates(MachineFunction &MF); 670b57cec5SDimitry Andric void fixEndsAtEndOfFunction(MachineFunction &MF); 680b57cec5SDimitry Andric 690b57cec5SDimitry Andric // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY). 700b57cec5SDimitry Andric DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd; 710b57cec5SDimitry Andric // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY. 720b57cec5SDimitry Andric DenseMap<const MachineInstr *, MachineInstr *> EndToBegin; 730b57cec5SDimitry Andric // <TRY marker, EH pad> map 740b57cec5SDimitry Andric DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad; 750b57cec5SDimitry Andric // <EH pad, TRY marker> map 760b57cec5SDimitry Andric DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry; 770b57cec5SDimitry Andric 780b57cec5SDimitry Andric // There can be an appendix block at the end of each function, shared for: 790b57cec5SDimitry Andric // - creating a correct signature for fallthrough returns 800b57cec5SDimitry Andric // - target for rethrows that need to unwind to the caller, but are trapped 810b57cec5SDimitry Andric // inside another try/catch 820b57cec5SDimitry Andric MachineBasicBlock *AppendixBB = nullptr; 830b57cec5SDimitry Andric MachineBasicBlock *getAppendixBlock(MachineFunction &MF) { 840b57cec5SDimitry Andric if (!AppendixBB) { 850b57cec5SDimitry Andric AppendixBB = MF.CreateMachineBasicBlock(); 860b57cec5SDimitry Andric // Give it a fake predecessor so that AsmPrinter prints its label. 870b57cec5SDimitry Andric AppendixBB->addSuccessor(AppendixBB); 880b57cec5SDimitry Andric MF.push_back(AppendixBB); 890b57cec5SDimitry Andric } 900b57cec5SDimitry Andric return AppendixBB; 910b57cec5SDimitry Andric } 920b57cec5SDimitry Andric 930b57cec5SDimitry Andric // Helper functions to register / unregister scope information created by 940b57cec5SDimitry Andric // marker instructions. 950b57cec5SDimitry Andric void registerScope(MachineInstr *Begin, MachineInstr *End); 960b57cec5SDimitry Andric void registerTryScope(MachineInstr *Begin, MachineInstr *End, 970b57cec5SDimitry Andric MachineBasicBlock *EHPad); 980b57cec5SDimitry Andric void unregisterScope(MachineInstr *Begin); 990b57cec5SDimitry Andric 1000b57cec5SDimitry Andric public: 1010b57cec5SDimitry Andric static char ID; // Pass identification, replacement for typeid 1020b57cec5SDimitry Andric WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} 1030b57cec5SDimitry Andric ~WebAssemblyCFGStackify() override { releaseMemory(); } 1040b57cec5SDimitry Andric void releaseMemory() override; 1050b57cec5SDimitry Andric }; 1060b57cec5SDimitry Andric } // end anonymous namespace 1070b57cec5SDimitry Andric 1080b57cec5SDimitry Andric char WebAssemblyCFGStackify::ID = 0; 1090b57cec5SDimitry Andric INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, 1100b57cec5SDimitry Andric "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false, 1110b57cec5SDimitry Andric false) 1120b57cec5SDimitry Andric 1130b57cec5SDimitry Andric FunctionPass *llvm::createWebAssemblyCFGStackify() { 1140b57cec5SDimitry Andric return new WebAssemblyCFGStackify(); 1150b57cec5SDimitry Andric } 1160b57cec5SDimitry Andric 1170b57cec5SDimitry Andric /// Test whether Pred has any terminators explicitly branching to MBB, as 1180b57cec5SDimitry Andric /// opposed to falling through. Note that it's possible (eg. in unoptimized 1190b57cec5SDimitry Andric /// code) for a branch instruction to both branch to a block and fallthrough 1200b57cec5SDimitry Andric /// to it, so we check the actual branch operands to see if there are any 1210b57cec5SDimitry Andric /// explicit mentions. 1220b57cec5SDimitry Andric static bool explicitlyBranchesTo(MachineBasicBlock *Pred, 1230b57cec5SDimitry Andric MachineBasicBlock *MBB) { 1240b57cec5SDimitry Andric for (MachineInstr &MI : Pred->terminators()) 1250b57cec5SDimitry Andric for (MachineOperand &MO : MI.explicit_operands()) 1260b57cec5SDimitry Andric if (MO.isMBB() && MO.getMBB() == MBB) 1270b57cec5SDimitry Andric return true; 1280b57cec5SDimitry Andric return false; 1290b57cec5SDimitry Andric } 1300b57cec5SDimitry Andric 1310b57cec5SDimitry Andric // Returns an iterator to the earliest position possible within the MBB, 1320b57cec5SDimitry Andric // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 1330b57cec5SDimitry Andric // contains instructions that should go before the marker, and AfterSet contains 1340b57cec5SDimitry Andric // ones that should go after the marker. In this function, AfterSet is only 1350b57cec5SDimitry Andric // used for sanity checking. 1360b57cec5SDimitry Andric static MachineBasicBlock::iterator 1370b57cec5SDimitry Andric getEarliestInsertPos(MachineBasicBlock *MBB, 1380b57cec5SDimitry Andric const SmallPtrSet<const MachineInstr *, 4> &BeforeSet, 1390b57cec5SDimitry Andric const SmallPtrSet<const MachineInstr *, 4> &AfterSet) { 1400b57cec5SDimitry Andric auto InsertPos = MBB->end(); 1410b57cec5SDimitry Andric while (InsertPos != MBB->begin()) { 1420b57cec5SDimitry Andric if (BeforeSet.count(&*std::prev(InsertPos))) { 1430b57cec5SDimitry Andric #ifndef NDEBUG 1440b57cec5SDimitry Andric // Sanity check 1450b57cec5SDimitry Andric for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos) 1460b57cec5SDimitry Andric assert(!AfterSet.count(&*std::prev(Pos))); 1470b57cec5SDimitry Andric #endif 1480b57cec5SDimitry Andric break; 1490b57cec5SDimitry Andric } 1500b57cec5SDimitry Andric --InsertPos; 1510b57cec5SDimitry Andric } 1520b57cec5SDimitry Andric return InsertPos; 1530b57cec5SDimitry Andric } 1540b57cec5SDimitry Andric 1550b57cec5SDimitry Andric // Returns an iterator to the latest position possible within the MBB, 1560b57cec5SDimitry Andric // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 1570b57cec5SDimitry Andric // contains instructions that should go before the marker, and AfterSet contains 1580b57cec5SDimitry Andric // ones that should go after the marker. In this function, BeforeSet is only 1590b57cec5SDimitry Andric // used for sanity checking. 1600b57cec5SDimitry Andric static MachineBasicBlock::iterator 1610b57cec5SDimitry Andric getLatestInsertPos(MachineBasicBlock *MBB, 1620b57cec5SDimitry Andric const SmallPtrSet<const MachineInstr *, 4> &BeforeSet, 1630b57cec5SDimitry Andric const SmallPtrSet<const MachineInstr *, 4> &AfterSet) { 1640b57cec5SDimitry Andric auto InsertPos = MBB->begin(); 1650b57cec5SDimitry Andric while (InsertPos != MBB->end()) { 1660b57cec5SDimitry Andric if (AfterSet.count(&*InsertPos)) { 1670b57cec5SDimitry Andric #ifndef NDEBUG 1680b57cec5SDimitry Andric // Sanity check 1690b57cec5SDimitry Andric for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos) 1700b57cec5SDimitry Andric assert(!BeforeSet.count(&*Pos)); 1710b57cec5SDimitry Andric #endif 1720b57cec5SDimitry Andric break; 1730b57cec5SDimitry Andric } 1740b57cec5SDimitry Andric ++InsertPos; 1750b57cec5SDimitry Andric } 1760b57cec5SDimitry Andric return InsertPos; 1770b57cec5SDimitry Andric } 1780b57cec5SDimitry Andric 1790b57cec5SDimitry Andric void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin, 1800b57cec5SDimitry Andric MachineInstr *End) { 1810b57cec5SDimitry Andric BeginToEnd[Begin] = End; 1820b57cec5SDimitry Andric EndToBegin[End] = Begin; 1830b57cec5SDimitry Andric } 1840b57cec5SDimitry Andric 1850b57cec5SDimitry Andric void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin, 1860b57cec5SDimitry Andric MachineInstr *End, 1870b57cec5SDimitry Andric MachineBasicBlock *EHPad) { 1880b57cec5SDimitry Andric registerScope(Begin, End); 1890b57cec5SDimitry Andric TryToEHPad[Begin] = EHPad; 1900b57cec5SDimitry Andric EHPadToTry[EHPad] = Begin; 1910b57cec5SDimitry Andric } 1920b57cec5SDimitry Andric 1930b57cec5SDimitry Andric void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) { 1940b57cec5SDimitry Andric assert(BeginToEnd.count(Begin)); 1950b57cec5SDimitry Andric MachineInstr *End = BeginToEnd[Begin]; 1960b57cec5SDimitry Andric assert(EndToBegin.count(End)); 1970b57cec5SDimitry Andric BeginToEnd.erase(Begin); 1980b57cec5SDimitry Andric EndToBegin.erase(End); 1990b57cec5SDimitry Andric MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin); 2000b57cec5SDimitry Andric if (EHPad) { 2010b57cec5SDimitry Andric assert(EHPadToTry.count(EHPad)); 2020b57cec5SDimitry Andric TryToEHPad.erase(Begin); 2030b57cec5SDimitry Andric EHPadToTry.erase(EHPad); 2040b57cec5SDimitry Andric } 2050b57cec5SDimitry Andric } 2060b57cec5SDimitry Andric 2070b57cec5SDimitry Andric /// Insert a BLOCK marker for branches to MBB (if needed). 2080b57cec5SDimitry Andric // TODO Consider a more generalized way of handling block (and also loop and 2090b57cec5SDimitry Andric // try) signatures when we implement the multi-value proposal later. 2100b57cec5SDimitry Andric void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) { 2110b57cec5SDimitry Andric assert(!MBB.isEHPad()); 2120b57cec5SDimitry Andric MachineFunction &MF = *MBB.getParent(); 2130b57cec5SDimitry Andric auto &MDT = getAnalysis<MachineDominatorTree>(); 2140b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 2150b57cec5SDimitry Andric const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 2160b57cec5SDimitry Andric 2170b57cec5SDimitry Andric // First compute the nearest common dominator of all forward non-fallthrough 2180b57cec5SDimitry Andric // predecessors so that we minimize the time that the BLOCK is on the stack, 2190b57cec5SDimitry Andric // which reduces overall stack height. 2200b57cec5SDimitry Andric MachineBasicBlock *Header = nullptr; 2210b57cec5SDimitry Andric bool IsBranchedTo = false; 2220b57cec5SDimitry Andric bool IsBrOnExn = false; 2230b57cec5SDimitry Andric MachineInstr *BrOnExn = nullptr; 2240b57cec5SDimitry Andric int MBBNumber = MBB.getNumber(); 2250b57cec5SDimitry Andric for (MachineBasicBlock *Pred : MBB.predecessors()) { 2260b57cec5SDimitry Andric if (Pred->getNumber() < MBBNumber) { 2270b57cec5SDimitry Andric Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 2280b57cec5SDimitry Andric if (explicitlyBranchesTo(Pred, &MBB)) { 2290b57cec5SDimitry Andric IsBranchedTo = true; 2300b57cec5SDimitry Andric if (Pred->getFirstTerminator()->getOpcode() == WebAssembly::BR_ON_EXN) { 2310b57cec5SDimitry Andric IsBrOnExn = true; 2320b57cec5SDimitry Andric assert(!BrOnExn && "There should be only one br_on_exn per block"); 2330b57cec5SDimitry Andric BrOnExn = &*Pred->getFirstTerminator(); 2340b57cec5SDimitry Andric } 2350b57cec5SDimitry Andric } 2360b57cec5SDimitry Andric } 2370b57cec5SDimitry Andric } 2380b57cec5SDimitry Andric if (!Header) 2390b57cec5SDimitry Andric return; 2400b57cec5SDimitry Andric if (!IsBranchedTo) 2410b57cec5SDimitry Andric return; 2420b57cec5SDimitry Andric 2430b57cec5SDimitry Andric assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors"); 2440b57cec5SDimitry Andric MachineBasicBlock *LayoutPred = MBB.getPrevNode(); 2450b57cec5SDimitry Andric 2460b57cec5SDimitry Andric // If the nearest common dominator is inside a more deeply nested context, 2470b57cec5SDimitry Andric // walk out to the nearest scope which isn't more deeply nested. 2480b57cec5SDimitry Andric for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 2490b57cec5SDimitry Andric if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 2500b57cec5SDimitry Andric if (ScopeTop->getNumber() > Header->getNumber()) { 2510b57cec5SDimitry Andric // Skip over an intervening scope. 2520b57cec5SDimitry Andric I = std::next(ScopeTop->getIterator()); 2530b57cec5SDimitry Andric } else { 2540b57cec5SDimitry Andric // We found a scope level at an appropriate depth. 2550b57cec5SDimitry Andric Header = ScopeTop; 2560b57cec5SDimitry Andric break; 2570b57cec5SDimitry Andric } 2580b57cec5SDimitry Andric } 2590b57cec5SDimitry Andric } 2600b57cec5SDimitry Andric 2610b57cec5SDimitry Andric // Decide where in Header to put the BLOCK. 2620b57cec5SDimitry Andric 2630b57cec5SDimitry Andric // Instructions that should go before the BLOCK. 2640b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> BeforeSet; 2650b57cec5SDimitry Andric // Instructions that should go after the BLOCK. 2660b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> AfterSet; 2670b57cec5SDimitry Andric for (const auto &MI : *Header) { 2680b57cec5SDimitry Andric // If there is a previously placed LOOP marker and the bottom block of the 2690b57cec5SDimitry Andric // loop is above MBB, it should be after the BLOCK, because the loop is 2700b57cec5SDimitry Andric // nested in this BLOCK. Otherwise it should be before the BLOCK. 2710b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::LOOP) { 2720b57cec5SDimitry Andric auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); 2730b57cec5SDimitry Andric if (MBB.getNumber() > LoopBottom->getNumber()) 2740b57cec5SDimitry Andric AfterSet.insert(&MI); 2750b57cec5SDimitry Andric #ifndef NDEBUG 2760b57cec5SDimitry Andric else 2770b57cec5SDimitry Andric BeforeSet.insert(&MI); 2780b57cec5SDimitry Andric #endif 2790b57cec5SDimitry Andric } 2800b57cec5SDimitry Andric 2815ffd83dbSDimitry Andric // If there is a previously placed BLOCK/TRY marker and its corresponding 2825ffd83dbSDimitry Andric // END marker is before the current BLOCK's END marker, that should be 2835ffd83dbSDimitry Andric // placed after this BLOCK. Otherwise it should be placed before this BLOCK 2845ffd83dbSDimitry Andric // marker. 2850b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::BLOCK || 2865ffd83dbSDimitry Andric MI.getOpcode() == WebAssembly::TRY) { 2875ffd83dbSDimitry Andric if (BeginToEnd[&MI]->getParent()->getNumber() <= MBB.getNumber()) 2880b57cec5SDimitry Andric AfterSet.insert(&MI); 2895ffd83dbSDimitry Andric #ifndef NDEBUG 2905ffd83dbSDimitry Andric else 2915ffd83dbSDimitry Andric BeforeSet.insert(&MI); 2925ffd83dbSDimitry Andric #endif 2935ffd83dbSDimitry Andric } 2940b57cec5SDimitry Andric 2950b57cec5SDimitry Andric #ifndef NDEBUG 2960b57cec5SDimitry Andric // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK. 2970b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_BLOCK || 2980b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_LOOP || 2990b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_TRY) 3000b57cec5SDimitry Andric BeforeSet.insert(&MI); 3010b57cec5SDimitry Andric #endif 3020b57cec5SDimitry Andric 3030b57cec5SDimitry Andric // Terminators should go after the BLOCK. 3040b57cec5SDimitry Andric if (MI.isTerminator()) 3050b57cec5SDimitry Andric AfterSet.insert(&MI); 3060b57cec5SDimitry Andric } 3070b57cec5SDimitry Andric 3080b57cec5SDimitry Andric // Local expression tree should go after the BLOCK. 3090b57cec5SDimitry Andric for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; 3100b57cec5SDimitry Andric --I) { 3110b57cec5SDimitry Andric if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 3120b57cec5SDimitry Andric continue; 3130b57cec5SDimitry Andric if (WebAssembly::isChild(*std::prev(I), MFI)) 3140b57cec5SDimitry Andric AfterSet.insert(&*std::prev(I)); 3150b57cec5SDimitry Andric else 3160b57cec5SDimitry Andric break; 3170b57cec5SDimitry Andric } 3180b57cec5SDimitry Andric 3190b57cec5SDimitry Andric // Add the BLOCK. 3200b57cec5SDimitry Andric 3210b57cec5SDimitry Andric // 'br_on_exn' extracts exnref object and pushes variable number of values 3220b57cec5SDimitry Andric // depending on its tag. For C++ exception, its a single i32 value, and the 3230b57cec5SDimitry Andric // generated code will be in the form of: 3240b57cec5SDimitry Andric // block i32 3250b57cec5SDimitry Andric // br_on_exn 0, $__cpp_exception 3260b57cec5SDimitry Andric // rethrow 3270b57cec5SDimitry Andric // end_block 3288bcb0991SDimitry Andric WebAssembly::BlockType ReturnType = WebAssembly::BlockType::Void; 3290b57cec5SDimitry Andric if (IsBrOnExn) { 3300b57cec5SDimitry Andric const char *TagName = BrOnExn->getOperand(1).getSymbolName(); 3310b57cec5SDimitry Andric if (std::strcmp(TagName, "__cpp_exception") != 0) 3320b57cec5SDimitry Andric llvm_unreachable("Only C++ exception is supported"); 3338bcb0991SDimitry Andric ReturnType = WebAssembly::BlockType::I32; 3340b57cec5SDimitry Andric } 3350b57cec5SDimitry Andric 3360b57cec5SDimitry Andric auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); 3370b57cec5SDimitry Andric MachineInstr *Begin = 3380b57cec5SDimitry Andric BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 3390b57cec5SDimitry Andric TII.get(WebAssembly::BLOCK)) 3400b57cec5SDimitry Andric .addImm(int64_t(ReturnType)); 3410b57cec5SDimitry Andric 3420b57cec5SDimitry Andric // Decide where in Header to put the END_BLOCK. 3430b57cec5SDimitry Andric BeforeSet.clear(); 3440b57cec5SDimitry Andric AfterSet.clear(); 3450b57cec5SDimitry Andric for (auto &MI : MBB) { 3460b57cec5SDimitry Andric #ifndef NDEBUG 3470b57cec5SDimitry Andric // END_BLOCK should precede existing LOOP and TRY markers. 3480b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::LOOP || 3490b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::TRY) 3500b57cec5SDimitry Andric AfterSet.insert(&MI); 3510b57cec5SDimitry Andric #endif 3520b57cec5SDimitry Andric 3530b57cec5SDimitry Andric // If there is a previously placed END_LOOP marker and the header of the 3540b57cec5SDimitry Andric // loop is above this block's header, the END_LOOP should be placed after 3550b57cec5SDimitry Andric // the BLOCK, because the loop contains this block. Otherwise the END_LOOP 3560b57cec5SDimitry Andric // should be placed before the BLOCK. The same for END_TRY. 3570b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_LOOP || 3580b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_TRY) { 3590b57cec5SDimitry Andric if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) 3600b57cec5SDimitry Andric BeforeSet.insert(&MI); 3610b57cec5SDimitry Andric #ifndef NDEBUG 3620b57cec5SDimitry Andric else 3630b57cec5SDimitry Andric AfterSet.insert(&MI); 3640b57cec5SDimitry Andric #endif 3650b57cec5SDimitry Andric } 3660b57cec5SDimitry Andric } 3670b57cec5SDimitry Andric 3680b57cec5SDimitry Andric // Mark the end of the block. 3690b57cec5SDimitry Andric InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); 3700b57cec5SDimitry Andric MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos), 3710b57cec5SDimitry Andric TII.get(WebAssembly::END_BLOCK)); 3720b57cec5SDimitry Andric registerScope(Begin, End); 3730b57cec5SDimitry Andric 3740b57cec5SDimitry Andric // Track the farthest-spanning scope that ends at this point. 3750b57cec5SDimitry Andric int Number = MBB.getNumber(); 3760b57cec5SDimitry Andric if (!ScopeTops[Number] || 3770b57cec5SDimitry Andric ScopeTops[Number]->getNumber() > Header->getNumber()) 3780b57cec5SDimitry Andric ScopeTops[Number] = Header; 3790b57cec5SDimitry Andric } 3800b57cec5SDimitry Andric 3810b57cec5SDimitry Andric /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header). 3820b57cec5SDimitry Andric void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { 3830b57cec5SDimitry Andric MachineFunction &MF = *MBB.getParent(); 3840b57cec5SDimitry Andric const auto &MLI = getAnalysis<MachineLoopInfo>(); 3850b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 3860b57cec5SDimitry Andric 3870b57cec5SDimitry Andric MachineLoop *Loop = MLI.getLoopFor(&MBB); 3880b57cec5SDimitry Andric if (!Loop || Loop->getHeader() != &MBB) 3890b57cec5SDimitry Andric return; 3900b57cec5SDimitry Andric 3910b57cec5SDimitry Andric // The operand of a LOOP is the first block after the loop. If the loop is the 3920b57cec5SDimitry Andric // bottom of the function, insert a dummy block at the end. 3930b57cec5SDimitry Andric MachineBasicBlock *Bottom = WebAssembly::getBottom(Loop); 3940b57cec5SDimitry Andric auto Iter = std::next(Bottom->getIterator()); 3950b57cec5SDimitry Andric if (Iter == MF.end()) { 3960b57cec5SDimitry Andric getAppendixBlock(MF); 3970b57cec5SDimitry Andric Iter = std::next(Bottom->getIterator()); 3980b57cec5SDimitry Andric } 3990b57cec5SDimitry Andric MachineBasicBlock *AfterLoop = &*Iter; 4000b57cec5SDimitry Andric 4010b57cec5SDimitry Andric // Decide where in Header to put the LOOP. 4020b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> BeforeSet; 4030b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> AfterSet; 4040b57cec5SDimitry Andric for (const auto &MI : MBB) { 4050b57cec5SDimitry Andric // LOOP marker should be after any existing loop that ends here. Otherwise 4060b57cec5SDimitry Andric // we assume the instruction belongs to the loop. 4070b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_LOOP) 4080b57cec5SDimitry Andric BeforeSet.insert(&MI); 4090b57cec5SDimitry Andric #ifndef NDEBUG 4100b57cec5SDimitry Andric else 4110b57cec5SDimitry Andric AfterSet.insert(&MI); 4120b57cec5SDimitry Andric #endif 4130b57cec5SDimitry Andric } 4140b57cec5SDimitry Andric 4150b57cec5SDimitry Andric // Mark the beginning of the loop. 4160b57cec5SDimitry Andric auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); 4170b57cec5SDimitry Andric MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos), 4180b57cec5SDimitry Andric TII.get(WebAssembly::LOOP)) 4198bcb0991SDimitry Andric .addImm(int64_t(WebAssembly::BlockType::Void)); 4200b57cec5SDimitry Andric 4210b57cec5SDimitry Andric // Decide where in Header to put the END_LOOP. 4220b57cec5SDimitry Andric BeforeSet.clear(); 4230b57cec5SDimitry Andric AfterSet.clear(); 4240b57cec5SDimitry Andric #ifndef NDEBUG 4250b57cec5SDimitry Andric for (const auto &MI : MBB) 4260b57cec5SDimitry Andric // Existing END_LOOP markers belong to parent loops of this loop 4270b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_LOOP) 4280b57cec5SDimitry Andric AfterSet.insert(&MI); 4290b57cec5SDimitry Andric #endif 4300b57cec5SDimitry Andric 4310b57cec5SDimitry Andric // Mark the end of the loop (using arbitrary debug location that branched to 4320b57cec5SDimitry Andric // the loop end as its location). 4330b57cec5SDimitry Andric InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet); 4340b57cec5SDimitry Andric DebugLoc EndDL = AfterLoop->pred_empty() 4350b57cec5SDimitry Andric ? DebugLoc() 4360b57cec5SDimitry Andric : (*AfterLoop->pred_rbegin())->findBranchDebugLoc(); 4370b57cec5SDimitry Andric MachineInstr *End = 4380b57cec5SDimitry Andric BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP)); 4390b57cec5SDimitry Andric registerScope(Begin, End); 4400b57cec5SDimitry Andric 4410b57cec5SDimitry Andric assert((!ScopeTops[AfterLoop->getNumber()] || 4420b57cec5SDimitry Andric ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) && 4430b57cec5SDimitry Andric "With block sorting the outermost loop for a block should be first."); 4440b57cec5SDimitry Andric if (!ScopeTops[AfterLoop->getNumber()]) 4450b57cec5SDimitry Andric ScopeTops[AfterLoop->getNumber()] = &MBB; 4460b57cec5SDimitry Andric } 4470b57cec5SDimitry Andric 4480b57cec5SDimitry Andric void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) { 4490b57cec5SDimitry Andric assert(MBB.isEHPad()); 4500b57cec5SDimitry Andric MachineFunction &MF = *MBB.getParent(); 4510b57cec5SDimitry Andric auto &MDT = getAnalysis<MachineDominatorTree>(); 4520b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 4530b57cec5SDimitry Andric const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); 4540b57cec5SDimitry Andric const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 4550b57cec5SDimitry Andric 4560b57cec5SDimitry Andric // Compute the nearest common dominator of all unwind predecessors 4570b57cec5SDimitry Andric MachineBasicBlock *Header = nullptr; 4580b57cec5SDimitry Andric int MBBNumber = MBB.getNumber(); 4590b57cec5SDimitry Andric for (auto *Pred : MBB.predecessors()) { 4600b57cec5SDimitry Andric if (Pred->getNumber() < MBBNumber) { 4610b57cec5SDimitry Andric Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 4620b57cec5SDimitry Andric assert(!explicitlyBranchesTo(Pred, &MBB) && 4630b57cec5SDimitry Andric "Explicit branch to an EH pad!"); 4640b57cec5SDimitry Andric } 4650b57cec5SDimitry Andric } 4660b57cec5SDimitry Andric if (!Header) 4670b57cec5SDimitry Andric return; 4680b57cec5SDimitry Andric 4690b57cec5SDimitry Andric // If this try is at the bottom of the function, insert a dummy block at the 4700b57cec5SDimitry Andric // end. 4710b57cec5SDimitry Andric WebAssemblyException *WE = WEI.getExceptionFor(&MBB); 4720b57cec5SDimitry Andric assert(WE); 4730b57cec5SDimitry Andric MachineBasicBlock *Bottom = WebAssembly::getBottom(WE); 4740b57cec5SDimitry Andric 4750b57cec5SDimitry Andric auto Iter = std::next(Bottom->getIterator()); 4760b57cec5SDimitry Andric if (Iter == MF.end()) { 4770b57cec5SDimitry Andric getAppendixBlock(MF); 4780b57cec5SDimitry Andric Iter = std::next(Bottom->getIterator()); 4790b57cec5SDimitry Andric } 4800b57cec5SDimitry Andric MachineBasicBlock *Cont = &*Iter; 4810b57cec5SDimitry Andric 4820b57cec5SDimitry Andric assert(Cont != &MF.front()); 4830b57cec5SDimitry Andric MachineBasicBlock *LayoutPred = Cont->getPrevNode(); 4840b57cec5SDimitry Andric 4850b57cec5SDimitry Andric // If the nearest common dominator is inside a more deeply nested context, 4860b57cec5SDimitry Andric // walk out to the nearest scope which isn't more deeply nested. 4870b57cec5SDimitry Andric for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 4880b57cec5SDimitry Andric if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 4890b57cec5SDimitry Andric if (ScopeTop->getNumber() > Header->getNumber()) { 4900b57cec5SDimitry Andric // Skip over an intervening scope. 4910b57cec5SDimitry Andric I = std::next(ScopeTop->getIterator()); 4920b57cec5SDimitry Andric } else { 4930b57cec5SDimitry Andric // We found a scope level at an appropriate depth. 4940b57cec5SDimitry Andric Header = ScopeTop; 4950b57cec5SDimitry Andric break; 4960b57cec5SDimitry Andric } 4970b57cec5SDimitry Andric } 4980b57cec5SDimitry Andric } 4990b57cec5SDimitry Andric 5000b57cec5SDimitry Andric // Decide where in Header to put the TRY. 5010b57cec5SDimitry Andric 5020b57cec5SDimitry Andric // Instructions that should go before the TRY. 5030b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> BeforeSet; 5040b57cec5SDimitry Andric // Instructions that should go after the TRY. 5050b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> AfterSet; 5060b57cec5SDimitry Andric for (const auto &MI : *Header) { 5070b57cec5SDimitry Andric // If there is a previously placed LOOP marker and the bottom block of the 5080b57cec5SDimitry Andric // loop is above MBB, it should be after the TRY, because the loop is nested 5090b57cec5SDimitry Andric // in this TRY. Otherwise it should be before the TRY. 5100b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::LOOP) { 5110b57cec5SDimitry Andric auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); 5120b57cec5SDimitry Andric if (MBB.getNumber() > LoopBottom->getNumber()) 5130b57cec5SDimitry Andric AfterSet.insert(&MI); 5140b57cec5SDimitry Andric #ifndef NDEBUG 5150b57cec5SDimitry Andric else 5160b57cec5SDimitry Andric BeforeSet.insert(&MI); 5170b57cec5SDimitry Andric #endif 5180b57cec5SDimitry Andric } 5190b57cec5SDimitry Andric 5200b57cec5SDimitry Andric // All previously inserted BLOCK/TRY markers should be after the TRY because 5210b57cec5SDimitry Andric // they are all nested trys. 5220b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::BLOCK || 5230b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::TRY) 5240b57cec5SDimitry Andric AfterSet.insert(&MI); 5250b57cec5SDimitry Andric 5260b57cec5SDimitry Andric #ifndef NDEBUG 5270b57cec5SDimitry Andric // All END_(BLOCK/LOOP/TRY) markers should be before the TRY. 5280b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_BLOCK || 5290b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_LOOP || 5300b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_TRY) 5310b57cec5SDimitry Andric BeforeSet.insert(&MI); 5320b57cec5SDimitry Andric #endif 5330b57cec5SDimitry Andric 5340b57cec5SDimitry Andric // Terminators should go after the TRY. 5350b57cec5SDimitry Andric if (MI.isTerminator()) 5360b57cec5SDimitry Andric AfterSet.insert(&MI); 5370b57cec5SDimitry Andric } 5380b57cec5SDimitry Andric 5398bcb0991SDimitry Andric // If Header unwinds to MBB (= Header contains 'invoke'), the try block should 5408bcb0991SDimitry Andric // contain the call within it. So the call should go after the TRY. The 5418bcb0991SDimitry Andric // exception is when the header's terminator is a rethrow instruction, in 5428bcb0991SDimitry Andric // which case that instruction, not a call instruction before it, is gonna 5438bcb0991SDimitry Andric // throw. 5448bcb0991SDimitry Andric MachineInstr *ThrowingCall = nullptr; 5458bcb0991SDimitry Andric if (MBB.isPredecessor(Header)) { 5468bcb0991SDimitry Andric auto TermPos = Header->getFirstTerminator(); 5478bcb0991SDimitry Andric if (TermPos == Header->end() || 5488bcb0991SDimitry Andric TermPos->getOpcode() != WebAssembly::RETHROW) { 5498bcb0991SDimitry Andric for (auto &MI : reverse(*Header)) { 5508bcb0991SDimitry Andric if (MI.isCall()) { 5518bcb0991SDimitry Andric AfterSet.insert(&MI); 5528bcb0991SDimitry Andric ThrowingCall = &MI; 5538bcb0991SDimitry Andric // Possibly throwing calls are usually wrapped by EH_LABEL 5548bcb0991SDimitry Andric // instructions. We don't want to split them and the call. 5558bcb0991SDimitry Andric if (MI.getIterator() != Header->begin() && 5568bcb0991SDimitry Andric std::prev(MI.getIterator())->isEHLabel()) { 5578bcb0991SDimitry Andric AfterSet.insert(&*std::prev(MI.getIterator())); 5588bcb0991SDimitry Andric ThrowingCall = &*std::prev(MI.getIterator()); 5598bcb0991SDimitry Andric } 5608bcb0991SDimitry Andric break; 5618bcb0991SDimitry Andric } 5628bcb0991SDimitry Andric } 5638bcb0991SDimitry Andric } 5648bcb0991SDimitry Andric } 5658bcb0991SDimitry Andric 5660b57cec5SDimitry Andric // Local expression tree should go after the TRY. 5678bcb0991SDimitry Andric // For BLOCK placement, we start the search from the previous instruction of a 5688bcb0991SDimitry Andric // BB's terminator, but in TRY's case, we should start from the previous 5698bcb0991SDimitry Andric // instruction of a call that can throw, or a EH_LABEL that precedes the call, 5708bcb0991SDimitry Andric // because the return values of the call's previous instructions can be 5718bcb0991SDimitry Andric // stackified and consumed by the throwing call. 5728bcb0991SDimitry Andric auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall) 5738bcb0991SDimitry Andric : Header->getFirstTerminator(); 5748bcb0991SDimitry Andric for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) { 5750b57cec5SDimitry Andric if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 5760b57cec5SDimitry Andric continue; 5770b57cec5SDimitry Andric if (WebAssembly::isChild(*std::prev(I), MFI)) 5780b57cec5SDimitry Andric AfterSet.insert(&*std::prev(I)); 5790b57cec5SDimitry Andric else 5800b57cec5SDimitry Andric break; 5810b57cec5SDimitry Andric } 5820b57cec5SDimitry Andric 5830b57cec5SDimitry Andric // Add the TRY. 5840b57cec5SDimitry Andric auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); 5850b57cec5SDimitry Andric MachineInstr *Begin = 5860b57cec5SDimitry Andric BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 5870b57cec5SDimitry Andric TII.get(WebAssembly::TRY)) 5888bcb0991SDimitry Andric .addImm(int64_t(WebAssembly::BlockType::Void)); 5890b57cec5SDimitry Andric 5900b57cec5SDimitry Andric // Decide where in Header to put the END_TRY. 5910b57cec5SDimitry Andric BeforeSet.clear(); 5920b57cec5SDimitry Andric AfterSet.clear(); 5930b57cec5SDimitry Andric for (const auto &MI : *Cont) { 5940b57cec5SDimitry Andric #ifndef NDEBUG 5950b57cec5SDimitry Andric // END_TRY should precede existing LOOP and BLOCK markers. 5960b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::LOOP || 5970b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::BLOCK) 5980b57cec5SDimitry Andric AfterSet.insert(&MI); 5990b57cec5SDimitry Andric 6000b57cec5SDimitry Andric // All END_TRY markers placed earlier belong to exceptions that contains 6010b57cec5SDimitry Andric // this one. 6020b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_TRY) 6030b57cec5SDimitry Andric AfterSet.insert(&MI); 6040b57cec5SDimitry Andric #endif 6050b57cec5SDimitry Andric 6060b57cec5SDimitry Andric // If there is a previously placed END_LOOP marker and its header is after 6070b57cec5SDimitry Andric // where TRY marker is, this loop is contained within the 'catch' part, so 6080b57cec5SDimitry Andric // the END_TRY marker should go after that. Otherwise, the whole try-catch 6090b57cec5SDimitry Andric // is contained within this loop, so the END_TRY should go before that. 6100b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_LOOP) { 6110b57cec5SDimitry Andric // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they 6120b57cec5SDimitry Andric // are in the same BB, LOOP is always before TRY. 6130b57cec5SDimitry Andric if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber()) 6140b57cec5SDimitry Andric BeforeSet.insert(&MI); 6150b57cec5SDimitry Andric #ifndef NDEBUG 6160b57cec5SDimitry Andric else 6170b57cec5SDimitry Andric AfterSet.insert(&MI); 6180b57cec5SDimitry Andric #endif 6190b57cec5SDimitry Andric } 6200b57cec5SDimitry Andric 6210b57cec5SDimitry Andric // It is not possible for an END_BLOCK to be already in this block. 6220b57cec5SDimitry Andric } 6230b57cec5SDimitry Andric 6240b57cec5SDimitry Andric // Mark the end of the TRY. 6250b57cec5SDimitry Andric InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet); 6260b57cec5SDimitry Andric MachineInstr *End = 6270b57cec5SDimitry Andric BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(), 6280b57cec5SDimitry Andric TII.get(WebAssembly::END_TRY)); 6290b57cec5SDimitry Andric registerTryScope(Begin, End, &MBB); 6300b57cec5SDimitry Andric 6310b57cec5SDimitry Andric // Track the farthest-spanning scope that ends at this point. We create two 6320b57cec5SDimitry Andric // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB 6330b57cec5SDimitry Andric // with 'try'). We need to create 'catch' -> 'try' mapping here too because 6340b57cec5SDimitry Andric // markers should not span across 'catch'. For example, this should not 6350b57cec5SDimitry Andric // happen: 6360b57cec5SDimitry Andric // 6370b57cec5SDimitry Andric // try 6380b57cec5SDimitry Andric // block --| (X) 6390b57cec5SDimitry Andric // catch | 6400b57cec5SDimitry Andric // end_block --| 6410b57cec5SDimitry Andric // end_try 6420b57cec5SDimitry Andric for (int Number : {Cont->getNumber(), MBB.getNumber()}) { 6430b57cec5SDimitry Andric if (!ScopeTops[Number] || 6440b57cec5SDimitry Andric ScopeTops[Number]->getNumber() > Header->getNumber()) 6450b57cec5SDimitry Andric ScopeTops[Number] = Header; 6460b57cec5SDimitry Andric } 6470b57cec5SDimitry Andric } 6480b57cec5SDimitry Andric 6490b57cec5SDimitry Andric void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) { 6500b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 6510b57cec5SDimitry Andric 6520b57cec5SDimitry Andric // When there is an unconditional branch right before a catch instruction and 6530b57cec5SDimitry Andric // it branches to the end of end_try marker, we don't need the branch, because 6540b57cec5SDimitry Andric // it there is no exception, the control flow transfers to that point anyway. 6550b57cec5SDimitry Andric // bb0: 6560b57cec5SDimitry Andric // try 6570b57cec5SDimitry Andric // ... 6580b57cec5SDimitry Andric // br bb2 <- Not necessary 6590b57cec5SDimitry Andric // bb1: 6600b57cec5SDimitry Andric // catch 6610b57cec5SDimitry Andric // ... 6620b57cec5SDimitry Andric // bb2: 6630b57cec5SDimitry Andric // end 6640b57cec5SDimitry Andric for (auto &MBB : MF) { 6650b57cec5SDimitry Andric if (!MBB.isEHPad()) 6660b57cec5SDimitry Andric continue; 6670b57cec5SDimitry Andric 6680b57cec5SDimitry Andric MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 6690b57cec5SDimitry Andric SmallVector<MachineOperand, 4> Cond; 6700b57cec5SDimitry Andric MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode(); 6710b57cec5SDimitry Andric MachineBasicBlock *Cont = BeginToEnd[EHPadToTry[&MBB]]->getParent(); 6720b57cec5SDimitry Andric bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond); 6735ffd83dbSDimitry Andric // This condition means either 6745ffd83dbSDimitry Andric // 1. This BB ends with a single unconditional branch whose destinaion is 6755ffd83dbSDimitry Andric // Cont. 6765ffd83dbSDimitry Andric // 2. This BB ends with a conditional branch followed by an unconditional 6775ffd83dbSDimitry Andric // branch, and the unconditional branch's destination is Cont. 6785ffd83dbSDimitry Andric // In both cases, we want to remove the last (= unconditional) branch. 6790b57cec5SDimitry Andric if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) || 6805ffd83dbSDimitry Andric (!Cond.empty() && FBB && FBB == Cont))) { 6815ffd83dbSDimitry Andric bool ErasedUncondBr = false; 6825ffd83dbSDimitry Andric (void)ErasedUncondBr; 6835ffd83dbSDimitry Andric for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin(); 6845ffd83dbSDimitry Andric I != E; --I) { 6855ffd83dbSDimitry Andric auto PrevI = std::prev(I); 6865ffd83dbSDimitry Andric if (PrevI->isTerminator()) { 6875ffd83dbSDimitry Andric assert(PrevI->getOpcode() == WebAssembly::BR); 6885ffd83dbSDimitry Andric PrevI->eraseFromParent(); 6895ffd83dbSDimitry Andric ErasedUncondBr = true; 6905ffd83dbSDimitry Andric break; 6915ffd83dbSDimitry Andric } 6925ffd83dbSDimitry Andric } 6935ffd83dbSDimitry Andric assert(ErasedUncondBr && "Unconditional branch not erased!"); 6945ffd83dbSDimitry Andric } 6950b57cec5SDimitry Andric } 6960b57cec5SDimitry Andric 6970b57cec5SDimitry Andric // When there are block / end_block markers that overlap with try / end_try 6980b57cec5SDimitry Andric // markers, and the block and try markers' return types are the same, the 6990b57cec5SDimitry Andric // block /end_block markers are not necessary, because try / end_try markers 7000b57cec5SDimitry Andric // also can serve as boundaries for branches. 7010b57cec5SDimitry Andric // block <- Not necessary 7020b57cec5SDimitry Andric // try 7030b57cec5SDimitry Andric // ... 7040b57cec5SDimitry Andric // catch 7050b57cec5SDimitry Andric // ... 7060b57cec5SDimitry Andric // end 7070b57cec5SDimitry Andric // end <- Not necessary 7080b57cec5SDimitry Andric SmallVector<MachineInstr *, 32> ToDelete; 7090b57cec5SDimitry Andric for (auto &MBB : MF) { 7100b57cec5SDimitry Andric for (auto &MI : MBB) { 7110b57cec5SDimitry Andric if (MI.getOpcode() != WebAssembly::TRY) 7120b57cec5SDimitry Andric continue; 7130b57cec5SDimitry Andric 7140b57cec5SDimitry Andric MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try]; 7150b57cec5SDimitry Andric MachineBasicBlock *TryBB = Try->getParent(); 7160b57cec5SDimitry Andric MachineBasicBlock *Cont = EndTry->getParent(); 7170b57cec5SDimitry Andric int64_t RetType = Try->getOperand(0).getImm(); 7180b57cec5SDimitry Andric for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator()); 7190b57cec5SDimitry Andric B != TryBB->begin() && E != Cont->end() && 7200b57cec5SDimitry Andric std::prev(B)->getOpcode() == WebAssembly::BLOCK && 7210b57cec5SDimitry Andric E->getOpcode() == WebAssembly::END_BLOCK && 7220b57cec5SDimitry Andric std::prev(B)->getOperand(0).getImm() == RetType; 7230b57cec5SDimitry Andric --B, ++E) { 7240b57cec5SDimitry Andric ToDelete.push_back(&*std::prev(B)); 7250b57cec5SDimitry Andric ToDelete.push_back(&*E); 7260b57cec5SDimitry Andric } 7270b57cec5SDimitry Andric } 7280b57cec5SDimitry Andric } 7290b57cec5SDimitry Andric for (auto *MI : ToDelete) { 7300b57cec5SDimitry Andric if (MI->getOpcode() == WebAssembly::BLOCK) 7310b57cec5SDimitry Andric unregisterScope(MI); 7320b57cec5SDimitry Andric MI->eraseFromParent(); 7330b57cec5SDimitry Andric } 7340b57cec5SDimitry Andric } 7350b57cec5SDimitry Andric 7365ffd83dbSDimitry Andric // Get the appropriate copy opcode for the given register class. 7375ffd83dbSDimitry Andric static unsigned getCopyOpcode(const TargetRegisterClass *RC) { 7385ffd83dbSDimitry Andric if (RC == &WebAssembly::I32RegClass) 7395ffd83dbSDimitry Andric return WebAssembly::COPY_I32; 7405ffd83dbSDimitry Andric if (RC == &WebAssembly::I64RegClass) 7415ffd83dbSDimitry Andric return WebAssembly::COPY_I64; 7425ffd83dbSDimitry Andric if (RC == &WebAssembly::F32RegClass) 7435ffd83dbSDimitry Andric return WebAssembly::COPY_F32; 7445ffd83dbSDimitry Andric if (RC == &WebAssembly::F64RegClass) 7455ffd83dbSDimitry Andric return WebAssembly::COPY_F64; 7465ffd83dbSDimitry Andric if (RC == &WebAssembly::V128RegClass) 7475ffd83dbSDimitry Andric return WebAssembly::COPY_V128; 7485ffd83dbSDimitry Andric if (RC == &WebAssembly::EXNREFRegClass) 7495ffd83dbSDimitry Andric return WebAssembly::COPY_EXNREF; 7505ffd83dbSDimitry Andric llvm_unreachable("Unexpected register class"); 7515ffd83dbSDimitry Andric } 7525ffd83dbSDimitry Andric 7538bcb0991SDimitry Andric // When MBB is split into MBB and Split, we should unstackify defs in MBB that 7548bcb0991SDimitry Andric // have their uses in Split. 7558bcb0991SDimitry Andric static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, 7568bcb0991SDimitry Andric MachineBasicBlock &Split, 7578bcb0991SDimitry Andric WebAssemblyFunctionInfo &MFI, 7585ffd83dbSDimitry Andric MachineRegisterInfo &MRI, 7595ffd83dbSDimitry Andric const WebAssemblyInstrInfo &TII) { 7608bcb0991SDimitry Andric for (auto &MI : Split) { 7618bcb0991SDimitry Andric for (auto &MO : MI.explicit_uses()) { 7628bcb0991SDimitry Andric if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg())) 7638bcb0991SDimitry Andric continue; 7648bcb0991SDimitry Andric if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg())) 7658bcb0991SDimitry Andric if (Def->getParent() == &MBB) 7668bcb0991SDimitry Andric MFI.unstackifyVReg(MO.getReg()); 7678bcb0991SDimitry Andric } 7688bcb0991SDimitry Andric } 7695ffd83dbSDimitry Andric 7705ffd83dbSDimitry Andric // In RegStackify, when a register definition is used multiple times, 7715ffd83dbSDimitry Andric // Reg = INST ... 7725ffd83dbSDimitry Andric // INST ..., Reg, ... 7735ffd83dbSDimitry Andric // INST ..., Reg, ... 7745ffd83dbSDimitry Andric // INST ..., Reg, ... 7755ffd83dbSDimitry Andric // 7765ffd83dbSDimitry Andric // we introduce a TEE, which has the following form: 7775ffd83dbSDimitry Andric // DefReg = INST ... 7785ffd83dbSDimitry Andric // TeeReg, Reg = TEE_... DefReg 7795ffd83dbSDimitry Andric // INST ..., TeeReg, ... 7805ffd83dbSDimitry Andric // INST ..., Reg, ... 7815ffd83dbSDimitry Andric // INST ..., Reg, ... 7825ffd83dbSDimitry Andric // with DefReg and TeeReg stackified but Reg not stackified. 7835ffd83dbSDimitry Andric // 7845ffd83dbSDimitry Andric // But the invariant that TeeReg should be stackified can be violated while we 7855ffd83dbSDimitry Andric // unstackify registers in the split BB above. In this case, we convert TEEs 7865ffd83dbSDimitry Andric // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals. 7875ffd83dbSDimitry Andric // DefReg = INST ... 7885ffd83dbSDimitry Andric // TeeReg = COPY DefReg 7895ffd83dbSDimitry Andric // Reg = COPY DefReg 7905ffd83dbSDimitry Andric // INST ..., TeeReg, ... 7915ffd83dbSDimitry Andric // INST ..., Reg, ... 7925ffd83dbSDimitry Andric // INST ..., Reg, ... 7935ffd83dbSDimitry Andric for (auto I = MBB.begin(), E = MBB.end(); I != E;) { 7945ffd83dbSDimitry Andric MachineInstr &MI = *I++; 7955ffd83dbSDimitry Andric if (!WebAssembly::isTee(MI.getOpcode())) 7965ffd83dbSDimitry Andric continue; 7975ffd83dbSDimitry Andric Register TeeReg = MI.getOperand(0).getReg(); 7985ffd83dbSDimitry Andric Register Reg = MI.getOperand(1).getReg(); 7995ffd83dbSDimitry Andric Register DefReg = MI.getOperand(2).getReg(); 8005ffd83dbSDimitry Andric if (!MFI.isVRegStackified(TeeReg)) { 8015ffd83dbSDimitry Andric // Now we are not using TEE anymore, so unstackify DefReg too 8025ffd83dbSDimitry Andric MFI.unstackifyVReg(DefReg); 8035ffd83dbSDimitry Andric unsigned CopyOpc = getCopyOpcode(MRI.getRegClass(DefReg)); 8045ffd83dbSDimitry Andric BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg) 8055ffd83dbSDimitry Andric .addReg(DefReg); 8065ffd83dbSDimitry Andric BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg); 8075ffd83dbSDimitry Andric MI.eraseFromParent(); 8085ffd83dbSDimitry Andric } 8095ffd83dbSDimitry Andric } 8108bcb0991SDimitry Andric } 8118bcb0991SDimitry Andric 8120b57cec5SDimitry Andric bool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) { 8130b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 8148bcb0991SDimitry Andric auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 8150b57cec5SDimitry Andric MachineRegisterInfo &MRI = MF.getRegInfo(); 8160b57cec5SDimitry Andric 8170b57cec5SDimitry Andric // Linearizing the control flow by placing TRY / END_TRY markers can create 8180b57cec5SDimitry Andric // mismatches in unwind destinations. There are two kinds of mismatches we 8190b57cec5SDimitry Andric // try to solve here. 8200b57cec5SDimitry Andric 8210b57cec5SDimitry Andric // 1. When an instruction may throw, but the EH pad it will unwind to can be 8220b57cec5SDimitry Andric // different from the original CFG. 8230b57cec5SDimitry Andric // 8240b57cec5SDimitry Andric // Example: we have the following CFG: 8250b57cec5SDimitry Andric // bb0: 8260b57cec5SDimitry Andric // call @foo (if it throws, unwind to bb2) 8270b57cec5SDimitry Andric // bb1: 8280b57cec5SDimitry Andric // call @bar (if it throws, unwind to bb3) 8290b57cec5SDimitry Andric // bb2 (ehpad): 8300b57cec5SDimitry Andric // catch 8310b57cec5SDimitry Andric // ... 8320b57cec5SDimitry Andric // bb3 (ehpad) 8330b57cec5SDimitry Andric // catch 8340b57cec5SDimitry Andric // handler body 8350b57cec5SDimitry Andric // 8360b57cec5SDimitry Andric // And the CFG is sorted in this order. Then after placing TRY markers, it 8370b57cec5SDimitry Andric // will look like: (BB markers are omitted) 8380b57cec5SDimitry Andric // try $label1 8390b57cec5SDimitry Andric // try 8400b57cec5SDimitry Andric // call @foo 8410b57cec5SDimitry Andric // call @bar (if it throws, unwind to bb3) 8420b57cec5SDimitry Andric // catch <- ehpad (bb2) 8430b57cec5SDimitry Andric // ... 8440b57cec5SDimitry Andric // end_try 8450b57cec5SDimitry Andric // catch <- ehpad (bb3) 8460b57cec5SDimitry Andric // handler body 8470b57cec5SDimitry Andric // end_try 8480b57cec5SDimitry Andric // 8490b57cec5SDimitry Andric // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it 8500b57cec5SDimitry Andric // is supposed to end up. We solve this problem by 8510b57cec5SDimitry Andric // a. Split the target unwind EH pad (here bb3) so that the handler body is 8520b57cec5SDimitry Andric // right after 'end_try', which means we extract the handler body out of 8530b57cec5SDimitry Andric // the catch block. We do this because this handler body should be 8540b57cec5SDimitry Andric // somewhere branch-eable from the inner scope. 8550b57cec5SDimitry Andric // b. Wrap the call that has an incorrect unwind destination ('call @bar' 8560b57cec5SDimitry Andric // here) with a nested try/catch/end_try scope, and within the new catch 8570b57cec5SDimitry Andric // block, branches to the handler body. 8580b57cec5SDimitry Andric // c. Place a branch after the newly inserted nested end_try so it can bypass 8590b57cec5SDimitry Andric // the handler body, which is now outside of a catch block. 8600b57cec5SDimitry Andric // 8610b57cec5SDimitry Andric // The result will like as follows. (new: a) means this instruction is newly 8620b57cec5SDimitry Andric // created in the process of doing 'a' above. 8630b57cec5SDimitry Andric // 8640b57cec5SDimitry Andric // block $label0 (new: placeBlockMarker) 8650b57cec5SDimitry Andric // try $label1 8660b57cec5SDimitry Andric // try 8670b57cec5SDimitry Andric // call @foo 8680b57cec5SDimitry Andric // try (new: b) 8690b57cec5SDimitry Andric // call @bar 8700b57cec5SDimitry Andric // catch (new: b) 8710b57cec5SDimitry Andric // local.set n / drop (new: b) 8720b57cec5SDimitry Andric // br $label1 (new: b) 8730b57cec5SDimitry Andric // end_try (new: b) 8740b57cec5SDimitry Andric // catch <- ehpad (bb2) 8750b57cec5SDimitry Andric // end_try 8760b57cec5SDimitry Andric // br $label0 (new: c) 8770b57cec5SDimitry Andric // catch <- ehpad (bb3) 8780b57cec5SDimitry Andric // end_try (hoisted: a) 8790b57cec5SDimitry Andric // handler body 8800b57cec5SDimitry Andric // end_block (new: placeBlockMarker) 8810b57cec5SDimitry Andric // 8820b57cec5SDimitry Andric // Note that the new wrapping block/end_block will be generated later in 8830b57cec5SDimitry Andric // placeBlockMarker. 8840b57cec5SDimitry Andric // 8850b57cec5SDimitry Andric // TODO Currently local.set and local.gets are generated to move exnref value 8860b57cec5SDimitry Andric // created by catches. That's because we don't support yielding values from a 8870b57cec5SDimitry Andric // block in LLVM machine IR yet, even though it is supported by wasm. Delete 8880b57cec5SDimitry Andric // unnecessary local.get/local.sets once yielding values from a block is 8890b57cec5SDimitry Andric // supported. The full EH spec requires multi-value support to do this, but 8900b57cec5SDimitry Andric // for C++ we don't yet need it because we only throw a single i32. 8910b57cec5SDimitry Andric // 8920b57cec5SDimitry Andric // --- 8930b57cec5SDimitry Andric // 2. The same as 1, but in this case an instruction unwinds to a caller 8940b57cec5SDimitry Andric // function and not another EH pad. 8950b57cec5SDimitry Andric // 8960b57cec5SDimitry Andric // Example: we have the following CFG: 8970b57cec5SDimitry Andric // bb0: 8980b57cec5SDimitry Andric // call @foo (if it throws, unwind to bb2) 8990b57cec5SDimitry Andric // bb1: 9000b57cec5SDimitry Andric // call @bar (if it throws, unwind to caller) 9010b57cec5SDimitry Andric // bb2 (ehpad): 9020b57cec5SDimitry Andric // catch 9030b57cec5SDimitry Andric // ... 9040b57cec5SDimitry Andric // 9050b57cec5SDimitry Andric // And the CFG is sorted in this order. Then after placing TRY markers, it 9060b57cec5SDimitry Andric // will look like: 9070b57cec5SDimitry Andric // try 9080b57cec5SDimitry Andric // call @foo 9090b57cec5SDimitry Andric // call @bar (if it throws, unwind to caller) 9100b57cec5SDimitry Andric // catch <- ehpad (bb2) 9110b57cec5SDimitry Andric // ... 9120b57cec5SDimitry Andric // end_try 9130b57cec5SDimitry Andric // 9140b57cec5SDimitry Andric // Now if bar() throws, it is going to end up ip in bb2, when it is supposed 9150b57cec5SDimitry Andric // throw up to the caller. 9160b57cec5SDimitry Andric // We solve this problem by 9170b57cec5SDimitry Andric // a. Create a new 'appendix' BB at the end of the function and put a single 9180b57cec5SDimitry Andric // 'rethrow' instruction (+ local.get) in there. 9190b57cec5SDimitry Andric // b. Wrap the call that has an incorrect unwind destination ('call @bar' 9200b57cec5SDimitry Andric // here) with a nested try/catch/end_try scope, and within the new catch 9210b57cec5SDimitry Andric // block, branches to the new appendix block. 9220b57cec5SDimitry Andric // 9230b57cec5SDimitry Andric // block $label0 (new: placeBlockMarker) 9240b57cec5SDimitry Andric // try 9250b57cec5SDimitry Andric // call @foo 9260b57cec5SDimitry Andric // try (new: b) 9270b57cec5SDimitry Andric // call @bar 9280b57cec5SDimitry Andric // catch (new: b) 9290b57cec5SDimitry Andric // local.set n (new: b) 9300b57cec5SDimitry Andric // br $label0 (new: b) 9310b57cec5SDimitry Andric // end_try (new: b) 9320b57cec5SDimitry Andric // catch <- ehpad (bb2) 9330b57cec5SDimitry Andric // ... 9340b57cec5SDimitry Andric // end_try 9350b57cec5SDimitry Andric // ... 9360b57cec5SDimitry Andric // end_block (new: placeBlockMarker) 9370b57cec5SDimitry Andric // local.get n (new: a) <- appendix block 9380b57cec5SDimitry Andric // rethrow (new: a) 9390b57cec5SDimitry Andric // 9400b57cec5SDimitry Andric // In case there are multiple calls in a BB that may throw to the caller, they 9410b57cec5SDimitry Andric // can be wrapped together in one nested try scope. (In 1, this couldn't 9420b57cec5SDimitry Andric // happen, because may-throwing instruction there had an unwind destination, 9430b57cec5SDimitry Andric // i.e., it was an invoke before, and there could be only one invoke within a 9440b57cec5SDimitry Andric // BB.) 9450b57cec5SDimitry Andric 9460b57cec5SDimitry Andric SmallVector<const MachineBasicBlock *, 8> EHPadStack; 9470b57cec5SDimitry Andric // Range of intructions to be wrapped in a new nested try/catch 9480b57cec5SDimitry Andric using TryRange = std::pair<MachineInstr *, MachineInstr *>; 9498bcb0991SDimitry Andric // In original CFG, <unwind destination BB, a vector of try ranges> 9500b57cec5SDimitry Andric DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges; 9510b57cec5SDimitry Andric // In new CFG, <destination to branch to, a vector of try ranges> 9520b57cec5SDimitry Andric DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> BrDestToTryRanges; 9530b57cec5SDimitry Andric // In new CFG, <destination to branch to, register containing exnref> 9540b57cec5SDimitry Andric DenseMap<MachineBasicBlock *, unsigned> BrDestToExnReg; 9550b57cec5SDimitry Andric 9565ffd83dbSDimitry Andric // Destinations for branches that will be newly added, for which a new 9575ffd83dbSDimitry Andric // BLOCK/END_BLOCK markers are necessary. 9585ffd83dbSDimitry Andric SmallVector<MachineBasicBlock *, 8> BrDests; 9595ffd83dbSDimitry Andric 9600b57cec5SDimitry Andric // Gather possibly throwing calls (i.e., previously invokes) whose current 9610b57cec5SDimitry Andric // unwind destination is not the same as the original CFG. 9620b57cec5SDimitry Andric for (auto &MBB : reverse(MF)) { 9630b57cec5SDimitry Andric bool SeenThrowableInstInBB = false; 9640b57cec5SDimitry Andric for (auto &MI : reverse(MBB)) { 9650b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::TRY) 9660b57cec5SDimitry Andric EHPadStack.pop_back(); 9670b57cec5SDimitry Andric else if (MI.getOpcode() == WebAssembly::CATCH) 9680b57cec5SDimitry Andric EHPadStack.push_back(MI.getParent()); 9690b57cec5SDimitry Andric 9700b57cec5SDimitry Andric // In this loop we only gather calls that have an EH pad to unwind. So 9710b57cec5SDimitry Andric // there will be at most 1 such call (= invoke) in a BB, so after we've 9720b57cec5SDimitry Andric // seen one, we can skip the rest of BB. Also if MBB has no EH pad 9730b57cec5SDimitry Andric // successor or MI does not throw, this is not an invoke. 9740b57cec5SDimitry Andric if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() || 9750b57cec5SDimitry Andric !WebAssembly::mayThrow(MI)) 9760b57cec5SDimitry Andric continue; 9770b57cec5SDimitry Andric SeenThrowableInstInBB = true; 9780b57cec5SDimitry Andric 9790b57cec5SDimitry Andric // If the EH pad on the stack top is where this instruction should unwind 9800b57cec5SDimitry Andric // next, we're good. 9810b57cec5SDimitry Andric MachineBasicBlock *UnwindDest = nullptr; 9820b57cec5SDimitry Andric for (auto *Succ : MBB.successors()) { 9830b57cec5SDimitry Andric if (Succ->isEHPad()) { 9840b57cec5SDimitry Andric UnwindDest = Succ; 9850b57cec5SDimitry Andric break; 9860b57cec5SDimitry Andric } 9870b57cec5SDimitry Andric } 9880b57cec5SDimitry Andric if (EHPadStack.back() == UnwindDest) 9890b57cec5SDimitry Andric continue; 9900b57cec5SDimitry Andric 9910b57cec5SDimitry Andric // If not, record the range. 9920b57cec5SDimitry Andric UnwindDestToTryRanges[UnwindDest].push_back(TryRange(&MI, &MI)); 9930b57cec5SDimitry Andric } 9940b57cec5SDimitry Andric } 9950b57cec5SDimitry Andric 9960b57cec5SDimitry Andric assert(EHPadStack.empty()); 9970b57cec5SDimitry Andric 9980b57cec5SDimitry Andric // Gather possibly throwing calls that are supposed to unwind up to the caller 9990b57cec5SDimitry Andric // if they throw, but currently unwind to an incorrect destination. Unlike the 10000b57cec5SDimitry Andric // loop above, there can be multiple calls within a BB that unwind to the 10010b57cec5SDimitry Andric // caller, which we should group together in a range. 10020b57cec5SDimitry Andric bool NeedAppendixBlock = false; 10030b57cec5SDimitry Andric for (auto &MBB : reverse(MF)) { 10040b57cec5SDimitry Andric MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive 10050b57cec5SDimitry Andric for (auto &MI : reverse(MBB)) { 10060b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::TRY) 10070b57cec5SDimitry Andric EHPadStack.pop_back(); 10080b57cec5SDimitry Andric else if (MI.getOpcode() == WebAssembly::CATCH) 10090b57cec5SDimitry Andric EHPadStack.push_back(MI.getParent()); 10100b57cec5SDimitry Andric 10110b57cec5SDimitry Andric // If MBB has an EH pad successor, this inst does not unwind to caller. 10120b57cec5SDimitry Andric if (MBB.hasEHPadSuccessor()) 10130b57cec5SDimitry Andric continue; 10140b57cec5SDimitry Andric 10150b57cec5SDimitry Andric // We wrap up the current range when we see a marker even if we haven't 10160b57cec5SDimitry Andric // finished a BB. 10170b57cec5SDimitry Andric if (RangeEnd && WebAssembly::isMarker(MI.getOpcode())) { 10180b57cec5SDimitry Andric NeedAppendixBlock = true; 10190b57cec5SDimitry Andric // Record the range. nullptr here means the unwind destination is the 10200b57cec5SDimitry Andric // caller. 10210b57cec5SDimitry Andric UnwindDestToTryRanges[nullptr].push_back( 10220b57cec5SDimitry Andric TryRange(RangeBegin, RangeEnd)); 10230b57cec5SDimitry Andric RangeBegin = RangeEnd = nullptr; // Reset range pointers 10240b57cec5SDimitry Andric } 10250b57cec5SDimitry Andric 10260b57cec5SDimitry Andric // If EHPadStack is empty, that means it is correctly unwind to caller if 10270b57cec5SDimitry Andric // it throws, so we're good. If MI does not throw, we're good too. 10280b57cec5SDimitry Andric if (EHPadStack.empty() || !WebAssembly::mayThrow(MI)) 10290b57cec5SDimitry Andric continue; 10300b57cec5SDimitry Andric 10310b57cec5SDimitry Andric // We found an instruction that unwinds to the caller but currently has an 10320b57cec5SDimitry Andric // incorrect unwind destination. Create a new range or increment the 10330b57cec5SDimitry Andric // currently existing range. 10340b57cec5SDimitry Andric if (!RangeEnd) 10350b57cec5SDimitry Andric RangeBegin = RangeEnd = &MI; 10360b57cec5SDimitry Andric else 10370b57cec5SDimitry Andric RangeBegin = &MI; 10380b57cec5SDimitry Andric } 10390b57cec5SDimitry Andric 10400b57cec5SDimitry Andric if (RangeEnd) { 10410b57cec5SDimitry Andric NeedAppendixBlock = true; 10420b57cec5SDimitry Andric // Record the range. nullptr here means the unwind destination is the 10430b57cec5SDimitry Andric // caller. 10440b57cec5SDimitry Andric UnwindDestToTryRanges[nullptr].push_back(TryRange(RangeBegin, RangeEnd)); 10450b57cec5SDimitry Andric RangeBegin = RangeEnd = nullptr; // Reset range pointers 10460b57cec5SDimitry Andric } 10470b57cec5SDimitry Andric } 10480b57cec5SDimitry Andric 10490b57cec5SDimitry Andric assert(EHPadStack.empty()); 10500b57cec5SDimitry Andric // We don't have any unwind destination mismatches to resolve. 10510b57cec5SDimitry Andric if (UnwindDestToTryRanges.empty()) 10520b57cec5SDimitry Andric return false; 10530b57cec5SDimitry Andric 10540b57cec5SDimitry Andric // If we found instructions that should unwind to the caller but currently 10550b57cec5SDimitry Andric // have incorrect unwind destination, we create an appendix block at the end 10560b57cec5SDimitry Andric // of the function with a local.get and a rethrow instruction. 10570b57cec5SDimitry Andric if (NeedAppendixBlock) { 10580b57cec5SDimitry Andric auto *AppendixBB = getAppendixBlock(MF); 10598bcb0991SDimitry Andric Register ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass); 10600b57cec5SDimitry Andric BuildMI(AppendixBB, DebugLoc(), TII.get(WebAssembly::RETHROW)) 10610b57cec5SDimitry Andric .addReg(ExnReg); 10620b57cec5SDimitry Andric // These instruction ranges should branch to this appendix BB. 10630b57cec5SDimitry Andric for (auto Range : UnwindDestToTryRanges[nullptr]) 10640b57cec5SDimitry Andric BrDestToTryRanges[AppendixBB].push_back(Range); 10650b57cec5SDimitry Andric BrDestToExnReg[AppendixBB] = ExnReg; 10660b57cec5SDimitry Andric } 10670b57cec5SDimitry Andric 10680b57cec5SDimitry Andric // We loop through unwind destination EH pads that are targeted from some 10690b57cec5SDimitry Andric // inner scopes. Because these EH pads are destination of more than one scope 10700b57cec5SDimitry Andric // now, we split them so that the handler body is after 'end_try'. 10710b57cec5SDimitry Andric // - Before 10720b57cec5SDimitry Andric // ehpad: 10730b57cec5SDimitry Andric // catch 10740b57cec5SDimitry Andric // local.set n / drop 10750b57cec5SDimitry Andric // handler body 10760b57cec5SDimitry Andric // ... 10770b57cec5SDimitry Andric // cont: 10780b57cec5SDimitry Andric // end_try 10790b57cec5SDimitry Andric // 10800b57cec5SDimitry Andric // - After 10810b57cec5SDimitry Andric // ehpad: 10820b57cec5SDimitry Andric // catch 10830b57cec5SDimitry Andric // local.set n / drop 10840b57cec5SDimitry Andric // brdest: (new) 10850b57cec5SDimitry Andric // end_try (hoisted from 'cont' BB) 10860b57cec5SDimitry Andric // handler body (taken from 'ehpad') 10870b57cec5SDimitry Andric // ... 10880b57cec5SDimitry Andric // cont: 10890b57cec5SDimitry Andric for (auto &P : UnwindDestToTryRanges) { 10908bcb0991SDimitry Andric NumUnwindMismatches += P.second.size(); 10910b57cec5SDimitry Andric 10920b57cec5SDimitry Andric // This means the destination is the appendix BB, which was separately 10930b57cec5SDimitry Andric // handled above. 10940b57cec5SDimitry Andric if (!P.first) 10950b57cec5SDimitry Andric continue; 10960b57cec5SDimitry Andric 10970b57cec5SDimitry Andric MachineBasicBlock *EHPad = P.first; 10980b57cec5SDimitry Andric 10990b57cec5SDimitry Andric // Find 'catch' and 'local.set' or 'drop' instruction that follows the 11000b57cec5SDimitry Andric // 'catch'. If -wasm-disable-explicit-locals is not set, 'catch' should be 11010b57cec5SDimitry Andric // always followed by either 'local.set' or a 'drop', because 'br_on_exn' is 11020b57cec5SDimitry Andric // generated after 'catch' in LateEHPrepare and we don't support blocks 11030b57cec5SDimitry Andric // taking values yet. 11040b57cec5SDimitry Andric MachineInstr *Catch = nullptr; 11050b57cec5SDimitry Andric unsigned ExnReg = 0; 11060b57cec5SDimitry Andric for (auto &MI : *EHPad) { 11070b57cec5SDimitry Andric switch (MI.getOpcode()) { 11080b57cec5SDimitry Andric case WebAssembly::CATCH: 11090b57cec5SDimitry Andric Catch = &MI; 11100b57cec5SDimitry Andric ExnReg = Catch->getOperand(0).getReg(); 11110b57cec5SDimitry Andric break; 11120b57cec5SDimitry Andric } 11130b57cec5SDimitry Andric } 11140b57cec5SDimitry Andric assert(Catch && "EH pad does not have a catch"); 11150b57cec5SDimitry Andric assert(ExnReg != 0 && "Invalid register"); 11160b57cec5SDimitry Andric 11170b57cec5SDimitry Andric auto SplitPos = std::next(Catch->getIterator()); 11180b57cec5SDimitry Andric 11190b57cec5SDimitry Andric // Create a new BB that's gonna be the destination for branches from the 11200b57cec5SDimitry Andric // inner mismatched scope. 11210b57cec5SDimitry Andric MachineInstr *BeginTry = EHPadToTry[EHPad]; 11220b57cec5SDimitry Andric MachineInstr *EndTry = BeginToEnd[BeginTry]; 11230b57cec5SDimitry Andric MachineBasicBlock *Cont = EndTry->getParent(); 11240b57cec5SDimitry Andric auto *BrDest = MF.CreateMachineBasicBlock(); 11250b57cec5SDimitry Andric MF.insert(std::next(EHPad->getIterator()), BrDest); 11260b57cec5SDimitry Andric // Hoist up the existing 'end_try'. 11270b57cec5SDimitry Andric BrDest->insert(BrDest->end(), EndTry->removeFromParent()); 11280b57cec5SDimitry Andric // Take out the handler body from EH pad to the new branch destination BB. 11290b57cec5SDimitry Andric BrDest->splice(BrDest->end(), EHPad, SplitPos, EHPad->end()); 11305ffd83dbSDimitry Andric unstackifyVRegsUsedInSplitBB(*EHPad, *BrDest, MFI, MRI, TII); 11310b57cec5SDimitry Andric // Fix predecessor-successor relationship. 11320b57cec5SDimitry Andric BrDest->transferSuccessors(EHPad); 11330b57cec5SDimitry Andric EHPad->addSuccessor(BrDest); 11340b57cec5SDimitry Andric 11350b57cec5SDimitry Andric // All try ranges that were supposed to unwind to this EH pad now have to 11360b57cec5SDimitry Andric // branch to this new branch dest BB. 11370b57cec5SDimitry Andric for (auto Range : UnwindDestToTryRanges[EHPad]) 11380b57cec5SDimitry Andric BrDestToTryRanges[BrDest].push_back(Range); 11390b57cec5SDimitry Andric BrDestToExnReg[BrDest] = ExnReg; 11400b57cec5SDimitry Andric 11410b57cec5SDimitry Andric // In case we fall through to the continuation BB after the catch block, we 11420b57cec5SDimitry Andric // now have to add a branch to it. 11430b57cec5SDimitry Andric // - Before 11440b57cec5SDimitry Andric // try 11450b57cec5SDimitry Andric // ... 11460b57cec5SDimitry Andric // (falls through to 'cont') 11470b57cec5SDimitry Andric // catch 11480b57cec5SDimitry Andric // handler body 11490b57cec5SDimitry Andric // end 11500b57cec5SDimitry Andric // <-- cont 11510b57cec5SDimitry Andric // 11520b57cec5SDimitry Andric // - After 11530b57cec5SDimitry Andric // try 11540b57cec5SDimitry Andric // ... 11550b57cec5SDimitry Andric // br %cont (new) 11560b57cec5SDimitry Andric // catch 11570b57cec5SDimitry Andric // end 11580b57cec5SDimitry Andric // handler body 11590b57cec5SDimitry Andric // <-- cont 11600b57cec5SDimitry Andric MachineBasicBlock *EHPadLayoutPred = &*std::prev(EHPad->getIterator()); 11610b57cec5SDimitry Andric MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 11620b57cec5SDimitry Andric SmallVector<MachineOperand, 4> Cond; 11630b57cec5SDimitry Andric bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond); 11640b57cec5SDimitry Andric if (Analyzable && !TBB && !FBB) { 11650b57cec5SDimitry Andric DebugLoc DL = EHPadLayoutPred->empty() 11660b57cec5SDimitry Andric ? DebugLoc() 11670b57cec5SDimitry Andric : EHPadLayoutPred->rbegin()->getDebugLoc(); 11680b57cec5SDimitry Andric BuildMI(EHPadLayoutPred, DL, TII.get(WebAssembly::BR)).addMBB(Cont); 11695ffd83dbSDimitry Andric BrDests.push_back(Cont); 11700b57cec5SDimitry Andric } 11710b57cec5SDimitry Andric } 11720b57cec5SDimitry Andric 11730b57cec5SDimitry Andric // For possibly throwing calls whose unwind destinations are currently 11740b57cec5SDimitry Andric // incorrect because of CFG linearization, we wrap them with a nested 11750b57cec5SDimitry Andric // try/catch/end_try, and within the new catch block, we branch to the correct 11760b57cec5SDimitry Andric // handler. 11770b57cec5SDimitry Andric // - Before 11780b57cec5SDimitry Andric // mbb: 11790b57cec5SDimitry Andric // call @foo <- Unwind destination mismatch! 11800b57cec5SDimitry Andric // ehpad: 11810b57cec5SDimitry Andric // ... 11820b57cec5SDimitry Andric // 11830b57cec5SDimitry Andric // - After 11840b57cec5SDimitry Andric // mbb: 11850b57cec5SDimitry Andric // try (new) 11860b57cec5SDimitry Andric // call @foo 11870b57cec5SDimitry Andric // nested-ehpad: (new) 11880b57cec5SDimitry Andric // catch (new) 11890b57cec5SDimitry Andric // local.set n / drop (new) 11900b57cec5SDimitry Andric // br %brdest (new) 11910b57cec5SDimitry Andric // nested-end: (new) 11920b57cec5SDimitry Andric // end_try (new) 11930b57cec5SDimitry Andric // ehpad: 11940b57cec5SDimitry Andric // ... 11950b57cec5SDimitry Andric for (auto &P : BrDestToTryRanges) { 11960b57cec5SDimitry Andric MachineBasicBlock *BrDest = P.first; 11970b57cec5SDimitry Andric auto &TryRanges = P.second; 11980b57cec5SDimitry Andric unsigned ExnReg = BrDestToExnReg[BrDest]; 11990b57cec5SDimitry Andric 12000b57cec5SDimitry Andric for (auto Range : TryRanges) { 12010b57cec5SDimitry Andric MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; 12020b57cec5SDimitry Andric std::tie(RangeBegin, RangeEnd) = Range; 12030b57cec5SDimitry Andric auto *MBB = RangeBegin->getParent(); 12045ffd83dbSDimitry Andric // Store the first function call from this range, because RangeBegin can 12055ffd83dbSDimitry Andric // be moved to point EH_LABEL before the call 12065ffd83dbSDimitry Andric MachineInstr *RangeBeginCall = RangeBegin; 12070b57cec5SDimitry Andric 12080b57cec5SDimitry Andric // Include possible EH_LABELs in the range 12090b57cec5SDimitry Andric if (RangeBegin->getIterator() != MBB->begin() && 12100b57cec5SDimitry Andric std::prev(RangeBegin->getIterator())->isEHLabel()) 12110b57cec5SDimitry Andric RangeBegin = &*std::prev(RangeBegin->getIterator()); 12120b57cec5SDimitry Andric if (std::next(RangeEnd->getIterator()) != MBB->end() && 12130b57cec5SDimitry Andric std::next(RangeEnd->getIterator())->isEHLabel()) 12140b57cec5SDimitry Andric RangeEnd = &*std::next(RangeEnd->getIterator()); 12150b57cec5SDimitry Andric 12160b57cec5SDimitry Andric MachineBasicBlock *EHPad = nullptr; 12170b57cec5SDimitry Andric for (auto *Succ : MBB->successors()) { 12180b57cec5SDimitry Andric if (Succ->isEHPad()) { 12190b57cec5SDimitry Andric EHPad = Succ; 12200b57cec5SDimitry Andric break; 12210b57cec5SDimitry Andric } 12220b57cec5SDimitry Andric } 12230b57cec5SDimitry Andric 12245ffd83dbSDimitry Andric // Local expression tree before the first call of this range should go 12255ffd83dbSDimitry Andric // after the nested TRY. 12265ffd83dbSDimitry Andric SmallPtrSet<const MachineInstr *, 4> AfterSet; 12275ffd83dbSDimitry Andric AfterSet.insert(RangeBegin); 12285ffd83dbSDimitry Andric AfterSet.insert(RangeBeginCall); 12295ffd83dbSDimitry Andric for (auto I = MachineBasicBlock::iterator(RangeBeginCall), 12305ffd83dbSDimitry Andric E = MBB->begin(); 12315ffd83dbSDimitry Andric I != E; --I) { 12325ffd83dbSDimitry Andric if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 12335ffd83dbSDimitry Andric continue; 12345ffd83dbSDimitry Andric if (WebAssembly::isChild(*std::prev(I), MFI)) 12355ffd83dbSDimitry Andric AfterSet.insert(&*std::prev(I)); 12365ffd83dbSDimitry Andric else 12375ffd83dbSDimitry Andric break; 12385ffd83dbSDimitry Andric } 12395ffd83dbSDimitry Andric 12400b57cec5SDimitry Andric // Create the nested try instruction. 12415ffd83dbSDimitry Andric auto InsertPos = getLatestInsertPos( 12425ffd83dbSDimitry Andric MBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet); 12430b57cec5SDimitry Andric MachineInstr *NestedTry = 12445ffd83dbSDimitry Andric BuildMI(*MBB, InsertPos, RangeBegin->getDebugLoc(), 12450b57cec5SDimitry Andric TII.get(WebAssembly::TRY)) 12468bcb0991SDimitry Andric .addImm(int64_t(WebAssembly::BlockType::Void)); 12470b57cec5SDimitry Andric 12480b57cec5SDimitry Andric // Create the nested EH pad and fill instructions in. 12490b57cec5SDimitry Andric MachineBasicBlock *NestedEHPad = MF.CreateMachineBasicBlock(); 12500b57cec5SDimitry Andric MF.insert(std::next(MBB->getIterator()), NestedEHPad); 12510b57cec5SDimitry Andric NestedEHPad->setIsEHPad(); 12520b57cec5SDimitry Andric NestedEHPad->setIsEHScopeEntry(); 12530b57cec5SDimitry Andric BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::CATCH), 12540b57cec5SDimitry Andric ExnReg); 12550b57cec5SDimitry Andric BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::BR)) 12560b57cec5SDimitry Andric .addMBB(BrDest); 12570b57cec5SDimitry Andric 12580b57cec5SDimitry Andric // Create the nested continuation BB and end_try instruction. 12590b57cec5SDimitry Andric MachineBasicBlock *NestedCont = MF.CreateMachineBasicBlock(); 12600b57cec5SDimitry Andric MF.insert(std::next(NestedEHPad->getIterator()), NestedCont); 12610b57cec5SDimitry Andric MachineInstr *NestedEndTry = 12620b57cec5SDimitry Andric BuildMI(*NestedCont, NestedCont->begin(), RangeEnd->getDebugLoc(), 12630b57cec5SDimitry Andric TII.get(WebAssembly::END_TRY)); 12640b57cec5SDimitry Andric // In case MBB has more instructions after the try range, move them to the 12650b57cec5SDimitry Andric // new nested continuation BB. 12660b57cec5SDimitry Andric NestedCont->splice(NestedCont->end(), MBB, 12670b57cec5SDimitry Andric std::next(RangeEnd->getIterator()), MBB->end()); 12685ffd83dbSDimitry Andric unstackifyVRegsUsedInSplitBB(*MBB, *NestedCont, MFI, MRI, TII); 12690b57cec5SDimitry Andric registerTryScope(NestedTry, NestedEndTry, NestedEHPad); 12700b57cec5SDimitry Andric 12710b57cec5SDimitry Andric // Fix predecessor-successor relationship. 12720b57cec5SDimitry Andric NestedCont->transferSuccessors(MBB); 12735ffd83dbSDimitry Andric if (EHPad) { 12740b57cec5SDimitry Andric NestedCont->removeSuccessor(EHPad); 12755ffd83dbSDimitry Andric // If EHPad does not have any predecessors left after removing 12765ffd83dbSDimitry Andric // NextedCont predecessor, remove its successor too, because this EHPad 12775ffd83dbSDimitry Andric // is not reachable from the entry BB anyway. We can't remove EHPad BB 12785ffd83dbSDimitry Andric // itself because it can contain 'catch' or 'end', which are necessary 12795ffd83dbSDimitry Andric // for keeping try-catch-end structure. 12805ffd83dbSDimitry Andric if (EHPad->pred_empty()) 12815ffd83dbSDimitry Andric EHPad->removeSuccessor(BrDest); 12825ffd83dbSDimitry Andric } 12830b57cec5SDimitry Andric MBB->addSuccessor(NestedEHPad); 12840b57cec5SDimitry Andric MBB->addSuccessor(NestedCont); 12850b57cec5SDimitry Andric NestedEHPad->addSuccessor(BrDest); 12860b57cec5SDimitry Andric } 12870b57cec5SDimitry Andric } 12880b57cec5SDimitry Andric 12890b57cec5SDimitry Andric // Renumber BBs and recalculate ScopeTop info because new BBs might have been 12900b57cec5SDimitry Andric // created and inserted above. 12910b57cec5SDimitry Andric MF.RenumberBlocks(); 12920b57cec5SDimitry Andric ScopeTops.clear(); 12930b57cec5SDimitry Andric ScopeTops.resize(MF.getNumBlockIDs()); 12940b57cec5SDimitry Andric for (auto &MBB : reverse(MF)) { 12950b57cec5SDimitry Andric for (auto &MI : reverse(MBB)) { 12960b57cec5SDimitry Andric if (ScopeTops[MBB.getNumber()]) 12970b57cec5SDimitry Andric break; 12980b57cec5SDimitry Andric switch (MI.getOpcode()) { 12990b57cec5SDimitry Andric case WebAssembly::END_BLOCK: 13000b57cec5SDimitry Andric case WebAssembly::END_LOOP: 13010b57cec5SDimitry Andric case WebAssembly::END_TRY: 13020b57cec5SDimitry Andric ScopeTops[MBB.getNumber()] = EndToBegin[&MI]->getParent(); 13030b57cec5SDimitry Andric break; 13040b57cec5SDimitry Andric case WebAssembly::CATCH: 13050b57cec5SDimitry Andric ScopeTops[MBB.getNumber()] = EHPadToTry[&MBB]->getParent(); 13060b57cec5SDimitry Andric break; 13070b57cec5SDimitry Andric } 13080b57cec5SDimitry Andric } 13090b57cec5SDimitry Andric } 13100b57cec5SDimitry Andric 13110b57cec5SDimitry Andric // Recompute the dominator tree. 13120b57cec5SDimitry Andric getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF); 13130b57cec5SDimitry Andric 13145ffd83dbSDimitry Andric // Place block markers for newly added branches, if necessary. 13155ffd83dbSDimitry Andric 13165ffd83dbSDimitry Andric // If we've created an appendix BB and a branch to it, place a block/end_block 13175ffd83dbSDimitry Andric // marker for that. For some new branches, those branch destination BBs start 13185ffd83dbSDimitry Andric // with a hoisted end_try marker, so we don't need a new marker there. 13195ffd83dbSDimitry Andric if (AppendixBB) 13205ffd83dbSDimitry Andric BrDests.push_back(AppendixBB); 13215ffd83dbSDimitry Andric 13220b57cec5SDimitry Andric llvm::sort(BrDests, 13230b57cec5SDimitry Andric [&](const MachineBasicBlock *A, const MachineBasicBlock *B) { 13240b57cec5SDimitry Andric auto ANum = A->getNumber(); 13250b57cec5SDimitry Andric auto BNum = B->getNumber(); 13260b57cec5SDimitry Andric return ANum < BNum; 13270b57cec5SDimitry Andric }); 13280b57cec5SDimitry Andric for (auto *Dest : BrDests) 13290b57cec5SDimitry Andric placeBlockMarker(*Dest); 13300b57cec5SDimitry Andric 13310b57cec5SDimitry Andric return true; 13320b57cec5SDimitry Andric } 13330b57cec5SDimitry Andric 13340b57cec5SDimitry Andric static unsigned 13350b57cec5SDimitry Andric getDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack, 13360b57cec5SDimitry Andric const MachineBasicBlock *MBB) { 13370b57cec5SDimitry Andric unsigned Depth = 0; 13380b57cec5SDimitry Andric for (auto X : reverse(Stack)) { 13390b57cec5SDimitry Andric if (X == MBB) 13400b57cec5SDimitry Andric break; 13410b57cec5SDimitry Andric ++Depth; 13420b57cec5SDimitry Andric } 13430b57cec5SDimitry Andric assert(Depth < Stack.size() && "Branch destination should be in scope"); 13440b57cec5SDimitry Andric return Depth; 13450b57cec5SDimitry Andric } 13460b57cec5SDimitry Andric 13470b57cec5SDimitry Andric /// In normal assembly languages, when the end of a function is unreachable, 13480b57cec5SDimitry Andric /// because the function ends in an infinite loop or a noreturn call or similar, 13490b57cec5SDimitry Andric /// it isn't necessary to worry about the function return type at the end of 13500b57cec5SDimitry Andric /// the function, because it's never reached. However, in WebAssembly, blocks 13510b57cec5SDimitry Andric /// that end at the function end need to have a return type signature that 13520b57cec5SDimitry Andric /// matches the function signature, even though it's unreachable. This function 13530b57cec5SDimitry Andric /// checks for such cases and fixes up the signatures. 13540b57cec5SDimitry Andric void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { 13550b57cec5SDimitry Andric const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 13560b57cec5SDimitry Andric 13570b57cec5SDimitry Andric if (MFI.getResults().empty()) 13580b57cec5SDimitry Andric return; 13590b57cec5SDimitry Andric 13608bcb0991SDimitry Andric // MCInstLower will add the proper types to multivalue signatures based on the 13618bcb0991SDimitry Andric // function return type 13628bcb0991SDimitry Andric WebAssembly::BlockType RetType = 13638bcb0991SDimitry Andric MFI.getResults().size() > 1 13648bcb0991SDimitry Andric ? WebAssembly::BlockType::Multivalue 13658bcb0991SDimitry Andric : WebAssembly::BlockType( 13668bcb0991SDimitry Andric WebAssembly::toValType(MFI.getResults().front())); 13670b57cec5SDimitry Andric 13680b57cec5SDimitry Andric for (MachineBasicBlock &MBB : reverse(MF)) { 13690b57cec5SDimitry Andric for (MachineInstr &MI : reverse(MBB)) { 13700b57cec5SDimitry Andric if (MI.isPosition() || MI.isDebugInstr()) 13710b57cec5SDimitry Andric continue; 13728bcb0991SDimitry Andric switch (MI.getOpcode()) { 13738bcb0991SDimitry Andric case WebAssembly::END_BLOCK: 13748bcb0991SDimitry Andric case WebAssembly::END_LOOP: 13758bcb0991SDimitry Andric case WebAssembly::END_TRY: 13760b57cec5SDimitry Andric EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType)); 13770b57cec5SDimitry Andric continue; 13788bcb0991SDimitry Andric default: 13790b57cec5SDimitry Andric // Something other than an `end`. We're done. 13800b57cec5SDimitry Andric return; 13810b57cec5SDimitry Andric } 13820b57cec5SDimitry Andric } 13830b57cec5SDimitry Andric } 13848bcb0991SDimitry Andric } 13850b57cec5SDimitry Andric 13860b57cec5SDimitry Andric // WebAssembly functions end with an end instruction, as if the function body 13870b57cec5SDimitry Andric // were a block. 13880b57cec5SDimitry Andric static void appendEndToFunction(MachineFunction &MF, 13890b57cec5SDimitry Andric const WebAssemblyInstrInfo &TII) { 13900b57cec5SDimitry Andric BuildMI(MF.back(), MF.back().end(), 13910b57cec5SDimitry Andric MF.back().findPrevDebugLoc(MF.back().end()), 13920b57cec5SDimitry Andric TII.get(WebAssembly::END_FUNCTION)); 13930b57cec5SDimitry Andric } 13940b57cec5SDimitry Andric 13950b57cec5SDimitry Andric /// Insert LOOP/TRY/BLOCK markers at appropriate places. 13960b57cec5SDimitry Andric void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { 13970b57cec5SDimitry Andric // We allocate one more than the number of blocks in the function to 13980b57cec5SDimitry Andric // accommodate for the possible fake block we may insert at the end. 13990b57cec5SDimitry Andric ScopeTops.resize(MF.getNumBlockIDs() + 1); 14000b57cec5SDimitry Andric // Place the LOOP for MBB if MBB is the header of a loop. 14010b57cec5SDimitry Andric for (auto &MBB : MF) 14020b57cec5SDimitry Andric placeLoopMarker(MBB); 14030b57cec5SDimitry Andric 14040b57cec5SDimitry Andric const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 14050b57cec5SDimitry Andric for (auto &MBB : MF) { 14060b57cec5SDimitry Andric if (MBB.isEHPad()) { 14070b57cec5SDimitry Andric // Place the TRY for MBB if MBB is the EH pad of an exception. 14080b57cec5SDimitry Andric if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 14090b57cec5SDimitry Andric MF.getFunction().hasPersonalityFn()) 14100b57cec5SDimitry Andric placeTryMarker(MBB); 14110b57cec5SDimitry Andric } else { 14120b57cec5SDimitry Andric // Place the BLOCK for MBB if MBB is branched to from above. 14130b57cec5SDimitry Andric placeBlockMarker(MBB); 14140b57cec5SDimitry Andric } 14150b57cec5SDimitry Andric } 14160b57cec5SDimitry Andric // Fix mismatches in unwind destinations induced by linearizing the code. 14178bcb0991SDimitry Andric if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 14188bcb0991SDimitry Andric MF.getFunction().hasPersonalityFn()) 14190b57cec5SDimitry Andric fixUnwindMismatches(MF); 14200b57cec5SDimitry Andric } 14210b57cec5SDimitry Andric 14220b57cec5SDimitry Andric void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { 14230b57cec5SDimitry Andric // Now rewrite references to basic blocks to be depth immediates. 14240b57cec5SDimitry Andric SmallVector<const MachineBasicBlock *, 8> Stack; 14250b57cec5SDimitry Andric for (auto &MBB : reverse(MF)) { 14260b57cec5SDimitry Andric for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) { 14270b57cec5SDimitry Andric MachineInstr &MI = *I; 14280b57cec5SDimitry Andric switch (MI.getOpcode()) { 14290b57cec5SDimitry Andric case WebAssembly::BLOCK: 14300b57cec5SDimitry Andric case WebAssembly::TRY: 14310b57cec5SDimitry Andric assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= 14320b57cec5SDimitry Andric MBB.getNumber() && 14330b57cec5SDimitry Andric "Block/try marker should be balanced"); 14340b57cec5SDimitry Andric Stack.pop_back(); 14350b57cec5SDimitry Andric break; 14360b57cec5SDimitry Andric 14370b57cec5SDimitry Andric case WebAssembly::LOOP: 14380b57cec5SDimitry Andric assert(Stack.back() == &MBB && "Loop top should be balanced"); 14390b57cec5SDimitry Andric Stack.pop_back(); 14400b57cec5SDimitry Andric break; 14410b57cec5SDimitry Andric 14420b57cec5SDimitry Andric case WebAssembly::END_BLOCK: 14430b57cec5SDimitry Andric case WebAssembly::END_TRY: 14440b57cec5SDimitry Andric Stack.push_back(&MBB); 14450b57cec5SDimitry Andric break; 14460b57cec5SDimitry Andric 14470b57cec5SDimitry Andric case WebAssembly::END_LOOP: 14480b57cec5SDimitry Andric Stack.push_back(EndToBegin[&MI]->getParent()); 14490b57cec5SDimitry Andric break; 14500b57cec5SDimitry Andric 14510b57cec5SDimitry Andric default: 14520b57cec5SDimitry Andric if (MI.isTerminator()) { 14530b57cec5SDimitry Andric // Rewrite MBB operands to be depth immediates. 14540b57cec5SDimitry Andric SmallVector<MachineOperand, 4> Ops(MI.operands()); 14550b57cec5SDimitry Andric while (MI.getNumOperands() > 0) 14560b57cec5SDimitry Andric MI.RemoveOperand(MI.getNumOperands() - 1); 14570b57cec5SDimitry Andric for (auto MO : Ops) { 14580b57cec5SDimitry Andric if (MO.isMBB()) 14590b57cec5SDimitry Andric MO = MachineOperand::CreateImm(getDepth(Stack, MO.getMBB())); 14600b57cec5SDimitry Andric MI.addOperand(MF, MO); 14610b57cec5SDimitry Andric } 14620b57cec5SDimitry Andric } 14630b57cec5SDimitry Andric break; 14640b57cec5SDimitry Andric } 14650b57cec5SDimitry Andric } 14660b57cec5SDimitry Andric } 14670b57cec5SDimitry Andric assert(Stack.empty() && "Control flow should be balanced"); 14680b57cec5SDimitry Andric } 14690b57cec5SDimitry Andric 14700b57cec5SDimitry Andric void WebAssemblyCFGStackify::releaseMemory() { 14710b57cec5SDimitry Andric ScopeTops.clear(); 14720b57cec5SDimitry Andric BeginToEnd.clear(); 14730b57cec5SDimitry Andric EndToBegin.clear(); 14740b57cec5SDimitry Andric TryToEHPad.clear(); 14750b57cec5SDimitry Andric EHPadToTry.clear(); 14760b57cec5SDimitry Andric AppendixBB = nullptr; 14770b57cec5SDimitry Andric } 14780b57cec5SDimitry Andric 14790b57cec5SDimitry Andric bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 14800b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n" 14810b57cec5SDimitry Andric "********** Function: " 14820b57cec5SDimitry Andric << MF.getName() << '\n'); 14830b57cec5SDimitry Andric const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 14840b57cec5SDimitry Andric 14850b57cec5SDimitry Andric releaseMemory(); 14860b57cec5SDimitry Andric 14870b57cec5SDimitry Andric // Liveness is not tracked for VALUE_STACK physreg. 14880b57cec5SDimitry Andric MF.getRegInfo().invalidateLiveness(); 14890b57cec5SDimitry Andric 14900b57cec5SDimitry Andric // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes. 14910b57cec5SDimitry Andric placeMarkers(MF); 14920b57cec5SDimitry Andric 14930b57cec5SDimitry Andric // Remove unnecessary instructions possibly introduced by try/end_trys. 14940b57cec5SDimitry Andric if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 14950b57cec5SDimitry Andric MF.getFunction().hasPersonalityFn()) 14960b57cec5SDimitry Andric removeUnnecessaryInstrs(MF); 14970b57cec5SDimitry Andric 14980b57cec5SDimitry Andric // Convert MBB operands in terminators to relative depth immediates. 14990b57cec5SDimitry Andric rewriteDepthImmediates(MF); 15000b57cec5SDimitry Andric 15010b57cec5SDimitry Andric // Fix up block/loop/try signatures at the end of the function to conform to 15020b57cec5SDimitry Andric // WebAssembly's rules. 15030b57cec5SDimitry Andric fixEndsAtEndOfFunction(MF); 15040b57cec5SDimitry Andric 15050b57cec5SDimitry Andric // Add an end instruction at the end of the function body. 15060b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 15070b57cec5SDimitry Andric if (!MF.getSubtarget<WebAssemblySubtarget>() 15080b57cec5SDimitry Andric .getTargetTriple() 15090b57cec5SDimitry Andric .isOSBinFormatELF()) 15100b57cec5SDimitry Andric appendEndToFunction(MF, TII); 15110b57cec5SDimitry Andric 15120b57cec5SDimitry Andric MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified(); 15130b57cec5SDimitry Andric return true; 15140b57cec5SDimitry Andric } 1515