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" 27e8d8bef9SDimitry Andric #include "WebAssemblySortRegion.h" 280b57cec5SDimitry Andric #include "WebAssemblySubtarget.h" 290b57cec5SDimitry Andric #include "WebAssemblyUtilities.h" 300b57cec5SDimitry Andric #include "llvm/ADT/Statistic.h" 310b57cec5SDimitry Andric #include "llvm/CodeGen/MachineDominators.h" 320b57cec5SDimitry Andric #include "llvm/CodeGen/MachineInstrBuilder.h" 338bcb0991SDimitry Andric #include "llvm/CodeGen/MachineLoopInfo.h" 340b57cec5SDimitry Andric #include "llvm/MC/MCAsmInfo.h" 355ffd83dbSDimitry Andric #include "llvm/Target/TargetMachine.h" 360b57cec5SDimitry Andric using namespace llvm; 37e8d8bef9SDimitry Andric using WebAssembly::SortRegionInfo; 380b57cec5SDimitry Andric 390b57cec5SDimitry Andric #define DEBUG_TYPE "wasm-cfg-stackify" 400b57cec5SDimitry Andric 410b57cec5SDimitry Andric STATISTIC(NumUnwindMismatches, "Number of EH pad unwind mismatches found"); 420b57cec5SDimitry Andric 430b57cec5SDimitry Andric namespace { 440b57cec5SDimitry Andric class WebAssemblyCFGStackify final : public MachineFunctionPass { 450b57cec5SDimitry Andric StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } 460b57cec5SDimitry Andric 470b57cec5SDimitry Andric void getAnalysisUsage(AnalysisUsage &AU) const override { 480b57cec5SDimitry Andric AU.addRequired<MachineDominatorTree>(); 490b57cec5SDimitry Andric AU.addRequired<MachineLoopInfo>(); 500b57cec5SDimitry Andric AU.addRequired<WebAssemblyExceptionInfo>(); 510b57cec5SDimitry Andric MachineFunctionPass::getAnalysisUsage(AU); 520b57cec5SDimitry Andric } 530b57cec5SDimitry Andric 540b57cec5SDimitry Andric bool runOnMachineFunction(MachineFunction &MF) override; 550b57cec5SDimitry Andric 560b57cec5SDimitry Andric // For each block whose label represents the end of a scope, record the block 570b57cec5SDimitry Andric // which holds the beginning of the scope. This will allow us to quickly skip 580b57cec5SDimitry Andric // over scoped regions when walking blocks. 590b57cec5SDimitry Andric SmallVector<MachineBasicBlock *, 8> ScopeTops; 60e8d8bef9SDimitry Andric void updateScopeTops(MachineBasicBlock *Begin, MachineBasicBlock *End) { 61e8d8bef9SDimitry Andric int EndNo = End->getNumber(); 62e8d8bef9SDimitry Andric if (!ScopeTops[EndNo] || ScopeTops[EndNo]->getNumber() > Begin->getNumber()) 63e8d8bef9SDimitry Andric ScopeTops[EndNo] = Begin; 64e8d8bef9SDimitry Andric } 650b57cec5SDimitry Andric 660b57cec5SDimitry Andric // Placing markers. 670b57cec5SDimitry Andric void placeMarkers(MachineFunction &MF); 680b57cec5SDimitry Andric void placeBlockMarker(MachineBasicBlock &MBB); 690b57cec5SDimitry Andric void placeLoopMarker(MachineBasicBlock &MBB); 700b57cec5SDimitry Andric void placeTryMarker(MachineBasicBlock &MBB); 710b57cec5SDimitry Andric void removeUnnecessaryInstrs(MachineFunction &MF); 720b57cec5SDimitry Andric bool fixUnwindMismatches(MachineFunction &MF); 730b57cec5SDimitry Andric void rewriteDepthImmediates(MachineFunction &MF); 740b57cec5SDimitry Andric void fixEndsAtEndOfFunction(MachineFunction &MF); 750b57cec5SDimitry Andric 760b57cec5SDimitry Andric // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY). 770b57cec5SDimitry Andric DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd; 780b57cec5SDimitry Andric // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY. 790b57cec5SDimitry Andric DenseMap<const MachineInstr *, MachineInstr *> EndToBegin; 800b57cec5SDimitry Andric // <TRY marker, EH pad> map 810b57cec5SDimitry Andric DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad; 820b57cec5SDimitry Andric // <EH pad, TRY marker> map 830b57cec5SDimitry Andric DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry; 840b57cec5SDimitry Andric 850b57cec5SDimitry Andric // There can be an appendix block at the end of each function, shared for: 860b57cec5SDimitry Andric // - creating a correct signature for fallthrough returns 870b57cec5SDimitry Andric // - target for rethrows that need to unwind to the caller, but are trapped 880b57cec5SDimitry Andric // inside another try/catch 890b57cec5SDimitry Andric MachineBasicBlock *AppendixBB = nullptr; 900b57cec5SDimitry Andric MachineBasicBlock *getAppendixBlock(MachineFunction &MF) { 910b57cec5SDimitry Andric if (!AppendixBB) { 920b57cec5SDimitry Andric AppendixBB = MF.CreateMachineBasicBlock(); 930b57cec5SDimitry Andric // Give it a fake predecessor so that AsmPrinter prints its label. 940b57cec5SDimitry Andric AppendixBB->addSuccessor(AppendixBB); 950b57cec5SDimitry Andric MF.push_back(AppendixBB); 960b57cec5SDimitry Andric } 970b57cec5SDimitry Andric return AppendixBB; 980b57cec5SDimitry Andric } 990b57cec5SDimitry Andric 1000b57cec5SDimitry Andric // Helper functions to register / unregister scope information created by 1010b57cec5SDimitry Andric // marker instructions. 1020b57cec5SDimitry Andric void registerScope(MachineInstr *Begin, MachineInstr *End); 1030b57cec5SDimitry Andric void registerTryScope(MachineInstr *Begin, MachineInstr *End, 1040b57cec5SDimitry Andric MachineBasicBlock *EHPad); 1050b57cec5SDimitry Andric void unregisterScope(MachineInstr *Begin); 1060b57cec5SDimitry Andric 1070b57cec5SDimitry Andric public: 1080b57cec5SDimitry Andric static char ID; // Pass identification, replacement for typeid 1090b57cec5SDimitry Andric WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} 1100b57cec5SDimitry Andric ~WebAssemblyCFGStackify() override { releaseMemory(); } 1110b57cec5SDimitry Andric void releaseMemory() override; 1120b57cec5SDimitry Andric }; 1130b57cec5SDimitry Andric } // end anonymous namespace 1140b57cec5SDimitry Andric 1150b57cec5SDimitry Andric char WebAssemblyCFGStackify::ID = 0; 1160b57cec5SDimitry Andric INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, 1170b57cec5SDimitry Andric "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false, 1180b57cec5SDimitry Andric false) 1190b57cec5SDimitry Andric 1200b57cec5SDimitry Andric FunctionPass *llvm::createWebAssemblyCFGStackify() { 1210b57cec5SDimitry Andric return new WebAssemblyCFGStackify(); 1220b57cec5SDimitry Andric } 1230b57cec5SDimitry Andric 1240b57cec5SDimitry Andric /// Test whether Pred has any terminators explicitly branching to MBB, as 1250b57cec5SDimitry Andric /// opposed to falling through. Note that it's possible (eg. in unoptimized 1260b57cec5SDimitry Andric /// code) for a branch instruction to both branch to a block and fallthrough 1270b57cec5SDimitry Andric /// to it, so we check the actual branch operands to see if there are any 1280b57cec5SDimitry Andric /// explicit mentions. 1290b57cec5SDimitry Andric static bool explicitlyBranchesTo(MachineBasicBlock *Pred, 1300b57cec5SDimitry Andric MachineBasicBlock *MBB) { 1310b57cec5SDimitry Andric for (MachineInstr &MI : Pred->terminators()) 1320b57cec5SDimitry Andric for (MachineOperand &MO : MI.explicit_operands()) 1330b57cec5SDimitry Andric if (MO.isMBB() && MO.getMBB() == MBB) 1340b57cec5SDimitry Andric return true; 1350b57cec5SDimitry Andric return false; 1360b57cec5SDimitry Andric } 1370b57cec5SDimitry Andric 1380b57cec5SDimitry Andric // Returns an iterator to the earliest position possible within the MBB, 1390b57cec5SDimitry Andric // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 1400b57cec5SDimitry Andric // contains instructions that should go before the marker, and AfterSet contains 1410b57cec5SDimitry Andric // ones that should go after the marker. In this function, AfterSet is only 1420b57cec5SDimitry Andric // used for sanity checking. 143e8d8bef9SDimitry Andric template <typename Container> 1440b57cec5SDimitry Andric static MachineBasicBlock::iterator 145e8d8bef9SDimitry Andric getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, 146e8d8bef9SDimitry Andric const Container &AfterSet) { 1470b57cec5SDimitry Andric auto InsertPos = MBB->end(); 1480b57cec5SDimitry Andric while (InsertPos != MBB->begin()) { 1490b57cec5SDimitry Andric if (BeforeSet.count(&*std::prev(InsertPos))) { 1500b57cec5SDimitry Andric #ifndef NDEBUG 1510b57cec5SDimitry Andric // Sanity check 1520b57cec5SDimitry Andric for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos) 1530b57cec5SDimitry Andric assert(!AfterSet.count(&*std::prev(Pos))); 1540b57cec5SDimitry Andric #endif 1550b57cec5SDimitry Andric break; 1560b57cec5SDimitry Andric } 1570b57cec5SDimitry Andric --InsertPos; 1580b57cec5SDimitry Andric } 1590b57cec5SDimitry Andric return InsertPos; 1600b57cec5SDimitry Andric } 1610b57cec5SDimitry Andric 1620b57cec5SDimitry Andric // Returns an iterator to the latest position possible within the MBB, 1630b57cec5SDimitry Andric // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 1640b57cec5SDimitry Andric // contains instructions that should go before the marker, and AfterSet contains 1650b57cec5SDimitry Andric // ones that should go after the marker. In this function, BeforeSet is only 1660b57cec5SDimitry Andric // used for sanity checking. 167e8d8bef9SDimitry Andric template <typename Container> 1680b57cec5SDimitry Andric static MachineBasicBlock::iterator 169e8d8bef9SDimitry Andric getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, 170e8d8bef9SDimitry Andric const Container &AfterSet) { 1710b57cec5SDimitry Andric auto InsertPos = MBB->begin(); 1720b57cec5SDimitry Andric while (InsertPos != MBB->end()) { 1730b57cec5SDimitry Andric if (AfterSet.count(&*InsertPos)) { 1740b57cec5SDimitry Andric #ifndef NDEBUG 1750b57cec5SDimitry Andric // Sanity check 1760b57cec5SDimitry Andric for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos) 1770b57cec5SDimitry Andric assert(!BeforeSet.count(&*Pos)); 1780b57cec5SDimitry Andric #endif 1790b57cec5SDimitry Andric break; 1800b57cec5SDimitry Andric } 1810b57cec5SDimitry Andric ++InsertPos; 1820b57cec5SDimitry Andric } 1830b57cec5SDimitry Andric return InsertPos; 1840b57cec5SDimitry Andric } 1850b57cec5SDimitry Andric 1860b57cec5SDimitry Andric void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin, 1870b57cec5SDimitry Andric MachineInstr *End) { 1880b57cec5SDimitry Andric BeginToEnd[Begin] = End; 1890b57cec5SDimitry Andric EndToBegin[End] = Begin; 1900b57cec5SDimitry Andric } 1910b57cec5SDimitry Andric 1920b57cec5SDimitry Andric void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin, 1930b57cec5SDimitry Andric MachineInstr *End, 1940b57cec5SDimitry Andric MachineBasicBlock *EHPad) { 1950b57cec5SDimitry Andric registerScope(Begin, End); 1960b57cec5SDimitry Andric TryToEHPad[Begin] = EHPad; 1970b57cec5SDimitry Andric EHPadToTry[EHPad] = Begin; 1980b57cec5SDimitry Andric } 1990b57cec5SDimitry Andric 2000b57cec5SDimitry Andric void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) { 2010b57cec5SDimitry Andric assert(BeginToEnd.count(Begin)); 2020b57cec5SDimitry Andric MachineInstr *End = BeginToEnd[Begin]; 2030b57cec5SDimitry Andric assert(EndToBegin.count(End)); 2040b57cec5SDimitry Andric BeginToEnd.erase(Begin); 2050b57cec5SDimitry Andric EndToBegin.erase(End); 2060b57cec5SDimitry Andric MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin); 2070b57cec5SDimitry Andric if (EHPad) { 2080b57cec5SDimitry Andric assert(EHPadToTry.count(EHPad)); 2090b57cec5SDimitry Andric TryToEHPad.erase(Begin); 2100b57cec5SDimitry Andric EHPadToTry.erase(EHPad); 2110b57cec5SDimitry Andric } 2120b57cec5SDimitry Andric } 2130b57cec5SDimitry Andric 2140b57cec5SDimitry Andric /// Insert a BLOCK marker for branches to MBB (if needed). 2150b57cec5SDimitry Andric // TODO Consider a more generalized way of handling block (and also loop and 2160b57cec5SDimitry Andric // try) signatures when we implement the multi-value proposal later. 2170b57cec5SDimitry Andric void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) { 2180b57cec5SDimitry Andric assert(!MBB.isEHPad()); 2190b57cec5SDimitry Andric MachineFunction &MF = *MBB.getParent(); 2200b57cec5SDimitry Andric auto &MDT = getAnalysis<MachineDominatorTree>(); 2210b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 2220b57cec5SDimitry Andric const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 2230b57cec5SDimitry Andric 2240b57cec5SDimitry Andric // First compute the nearest common dominator of all forward non-fallthrough 2250b57cec5SDimitry Andric // predecessors so that we minimize the time that the BLOCK is on the stack, 2260b57cec5SDimitry Andric // which reduces overall stack height. 2270b57cec5SDimitry Andric MachineBasicBlock *Header = nullptr; 2280b57cec5SDimitry Andric bool IsBranchedTo = false; 2290b57cec5SDimitry Andric int MBBNumber = MBB.getNumber(); 2300b57cec5SDimitry Andric for (MachineBasicBlock *Pred : MBB.predecessors()) { 2310b57cec5SDimitry Andric if (Pred->getNumber() < MBBNumber) { 2320b57cec5SDimitry Andric Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 233e8d8bef9SDimitry Andric if (explicitlyBranchesTo(Pred, &MBB)) 2340b57cec5SDimitry Andric IsBranchedTo = true; 2350b57cec5SDimitry Andric } 2360b57cec5SDimitry Andric } 2370b57cec5SDimitry Andric if (!Header) 2380b57cec5SDimitry Andric return; 2390b57cec5SDimitry Andric if (!IsBranchedTo) 2400b57cec5SDimitry Andric return; 2410b57cec5SDimitry Andric 2420b57cec5SDimitry Andric assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors"); 2430b57cec5SDimitry Andric MachineBasicBlock *LayoutPred = MBB.getPrevNode(); 2440b57cec5SDimitry Andric 2450b57cec5SDimitry Andric // If the nearest common dominator is inside a more deeply nested context, 2460b57cec5SDimitry Andric // walk out to the nearest scope which isn't more deeply nested. 2470b57cec5SDimitry Andric for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 2480b57cec5SDimitry Andric if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 2490b57cec5SDimitry Andric if (ScopeTop->getNumber() > Header->getNumber()) { 2500b57cec5SDimitry Andric // Skip over an intervening scope. 2510b57cec5SDimitry Andric I = std::next(ScopeTop->getIterator()); 2520b57cec5SDimitry Andric } else { 2530b57cec5SDimitry Andric // We found a scope level at an appropriate depth. 2540b57cec5SDimitry Andric Header = ScopeTop; 2550b57cec5SDimitry Andric break; 2560b57cec5SDimitry Andric } 2570b57cec5SDimitry Andric } 2580b57cec5SDimitry Andric } 2590b57cec5SDimitry Andric 2600b57cec5SDimitry Andric // Decide where in Header to put the BLOCK. 2610b57cec5SDimitry Andric 2620b57cec5SDimitry Andric // Instructions that should go before the BLOCK. 2630b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> BeforeSet; 2640b57cec5SDimitry Andric // Instructions that should go after the BLOCK. 2650b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> AfterSet; 2660b57cec5SDimitry Andric for (const auto &MI : *Header) { 2670b57cec5SDimitry Andric // If there is a previously placed LOOP marker and the bottom block of the 2680b57cec5SDimitry Andric // loop is above MBB, it should be after the BLOCK, because the loop is 2690b57cec5SDimitry Andric // nested in this BLOCK. Otherwise it should be before the BLOCK. 2700b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::LOOP) { 2710b57cec5SDimitry Andric auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); 2720b57cec5SDimitry Andric if (MBB.getNumber() > LoopBottom->getNumber()) 2730b57cec5SDimitry Andric AfterSet.insert(&MI); 2740b57cec5SDimitry Andric #ifndef NDEBUG 2750b57cec5SDimitry Andric else 2760b57cec5SDimitry Andric BeforeSet.insert(&MI); 2770b57cec5SDimitry Andric #endif 2780b57cec5SDimitry Andric } 2790b57cec5SDimitry Andric 2805ffd83dbSDimitry Andric // If there is a previously placed BLOCK/TRY marker and its corresponding 2815ffd83dbSDimitry Andric // END marker is before the current BLOCK's END marker, that should be 2825ffd83dbSDimitry Andric // placed after this BLOCK. Otherwise it should be placed before this BLOCK 2835ffd83dbSDimitry Andric // marker. 2840b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::BLOCK || 2855ffd83dbSDimitry Andric MI.getOpcode() == WebAssembly::TRY) { 2865ffd83dbSDimitry Andric if (BeginToEnd[&MI]->getParent()->getNumber() <= MBB.getNumber()) 2870b57cec5SDimitry Andric AfterSet.insert(&MI); 2885ffd83dbSDimitry Andric #ifndef NDEBUG 2895ffd83dbSDimitry Andric else 2905ffd83dbSDimitry Andric BeforeSet.insert(&MI); 2915ffd83dbSDimitry Andric #endif 2925ffd83dbSDimitry Andric } 2930b57cec5SDimitry Andric 2940b57cec5SDimitry Andric #ifndef NDEBUG 2950b57cec5SDimitry Andric // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK. 2960b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_BLOCK || 2970b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_LOOP || 2980b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_TRY) 2990b57cec5SDimitry Andric BeforeSet.insert(&MI); 3000b57cec5SDimitry Andric #endif 3010b57cec5SDimitry Andric 3020b57cec5SDimitry Andric // Terminators should go after the BLOCK. 3030b57cec5SDimitry Andric if (MI.isTerminator()) 3040b57cec5SDimitry Andric AfterSet.insert(&MI); 3050b57cec5SDimitry Andric } 3060b57cec5SDimitry Andric 3070b57cec5SDimitry Andric // Local expression tree should go after the BLOCK. 3080b57cec5SDimitry Andric for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; 3090b57cec5SDimitry Andric --I) { 3100b57cec5SDimitry Andric if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 3110b57cec5SDimitry Andric continue; 3120b57cec5SDimitry Andric if (WebAssembly::isChild(*std::prev(I), MFI)) 3130b57cec5SDimitry Andric AfterSet.insert(&*std::prev(I)); 3140b57cec5SDimitry Andric else 3150b57cec5SDimitry Andric break; 3160b57cec5SDimitry Andric } 3170b57cec5SDimitry Andric 3180b57cec5SDimitry Andric // Add the BLOCK. 3198bcb0991SDimitry Andric WebAssembly::BlockType ReturnType = WebAssembly::BlockType::Void; 3200b57cec5SDimitry Andric auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); 3210b57cec5SDimitry Andric MachineInstr *Begin = 3220b57cec5SDimitry Andric BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 3230b57cec5SDimitry Andric TII.get(WebAssembly::BLOCK)) 3240b57cec5SDimitry Andric .addImm(int64_t(ReturnType)); 3250b57cec5SDimitry Andric 3260b57cec5SDimitry Andric // Decide where in Header to put the END_BLOCK. 3270b57cec5SDimitry Andric BeforeSet.clear(); 3280b57cec5SDimitry Andric AfterSet.clear(); 3290b57cec5SDimitry Andric for (auto &MI : MBB) { 3300b57cec5SDimitry Andric #ifndef NDEBUG 3310b57cec5SDimitry Andric // END_BLOCK should precede existing LOOP and TRY markers. 3320b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::LOOP || 3330b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::TRY) 3340b57cec5SDimitry Andric AfterSet.insert(&MI); 3350b57cec5SDimitry Andric #endif 3360b57cec5SDimitry Andric 3370b57cec5SDimitry Andric // If there is a previously placed END_LOOP marker and the header of the 3380b57cec5SDimitry Andric // loop is above this block's header, the END_LOOP should be placed after 3390b57cec5SDimitry Andric // the BLOCK, because the loop contains this block. Otherwise the END_LOOP 3400b57cec5SDimitry Andric // should be placed before the BLOCK. The same for END_TRY. 3410b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_LOOP || 3420b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_TRY) { 3430b57cec5SDimitry Andric if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) 3440b57cec5SDimitry Andric BeforeSet.insert(&MI); 3450b57cec5SDimitry Andric #ifndef NDEBUG 3460b57cec5SDimitry Andric else 3470b57cec5SDimitry Andric AfterSet.insert(&MI); 3480b57cec5SDimitry Andric #endif 3490b57cec5SDimitry Andric } 3500b57cec5SDimitry Andric } 3510b57cec5SDimitry Andric 3520b57cec5SDimitry Andric // Mark the end of the block. 3530b57cec5SDimitry Andric InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); 3540b57cec5SDimitry Andric MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos), 3550b57cec5SDimitry Andric TII.get(WebAssembly::END_BLOCK)); 3560b57cec5SDimitry Andric registerScope(Begin, End); 3570b57cec5SDimitry Andric 3580b57cec5SDimitry Andric // Track the farthest-spanning scope that ends at this point. 359e8d8bef9SDimitry Andric updateScopeTops(Header, &MBB); 3600b57cec5SDimitry Andric } 3610b57cec5SDimitry Andric 3620b57cec5SDimitry Andric /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header). 3630b57cec5SDimitry Andric void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { 3640b57cec5SDimitry Andric MachineFunction &MF = *MBB.getParent(); 3650b57cec5SDimitry Andric const auto &MLI = getAnalysis<MachineLoopInfo>(); 366e8d8bef9SDimitry Andric const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); 367e8d8bef9SDimitry Andric SortRegionInfo SRI(MLI, WEI); 3680b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 3690b57cec5SDimitry Andric 3700b57cec5SDimitry Andric MachineLoop *Loop = MLI.getLoopFor(&MBB); 3710b57cec5SDimitry Andric if (!Loop || Loop->getHeader() != &MBB) 3720b57cec5SDimitry Andric return; 3730b57cec5SDimitry Andric 3740b57cec5SDimitry Andric // The operand of a LOOP is the first block after the loop. If the loop is the 3750b57cec5SDimitry Andric // bottom of the function, insert a dummy block at the end. 376e8d8bef9SDimitry Andric MachineBasicBlock *Bottom = SRI.getBottom(Loop); 3770b57cec5SDimitry Andric auto Iter = std::next(Bottom->getIterator()); 3780b57cec5SDimitry Andric if (Iter == MF.end()) { 3790b57cec5SDimitry Andric getAppendixBlock(MF); 3800b57cec5SDimitry Andric Iter = std::next(Bottom->getIterator()); 3810b57cec5SDimitry Andric } 3820b57cec5SDimitry Andric MachineBasicBlock *AfterLoop = &*Iter; 3830b57cec5SDimitry Andric 3840b57cec5SDimitry Andric // Decide where in Header to put the LOOP. 3850b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> BeforeSet; 3860b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> AfterSet; 3870b57cec5SDimitry Andric for (const auto &MI : MBB) { 3880b57cec5SDimitry Andric // LOOP marker should be after any existing loop that ends here. Otherwise 3890b57cec5SDimitry Andric // we assume the instruction belongs to the loop. 3900b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_LOOP) 3910b57cec5SDimitry Andric BeforeSet.insert(&MI); 3920b57cec5SDimitry Andric #ifndef NDEBUG 3930b57cec5SDimitry Andric else 3940b57cec5SDimitry Andric AfterSet.insert(&MI); 3950b57cec5SDimitry Andric #endif 3960b57cec5SDimitry Andric } 3970b57cec5SDimitry Andric 3980b57cec5SDimitry Andric // Mark the beginning of the loop. 3990b57cec5SDimitry Andric auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); 4000b57cec5SDimitry Andric MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos), 4010b57cec5SDimitry Andric TII.get(WebAssembly::LOOP)) 4028bcb0991SDimitry Andric .addImm(int64_t(WebAssembly::BlockType::Void)); 4030b57cec5SDimitry Andric 4040b57cec5SDimitry Andric // Decide where in Header to put the END_LOOP. 4050b57cec5SDimitry Andric BeforeSet.clear(); 4060b57cec5SDimitry Andric AfterSet.clear(); 4070b57cec5SDimitry Andric #ifndef NDEBUG 4080b57cec5SDimitry Andric for (const auto &MI : MBB) 4090b57cec5SDimitry Andric // Existing END_LOOP markers belong to parent loops of this loop 4100b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_LOOP) 4110b57cec5SDimitry Andric AfterSet.insert(&MI); 4120b57cec5SDimitry Andric #endif 4130b57cec5SDimitry Andric 4140b57cec5SDimitry Andric // Mark the end of the loop (using arbitrary debug location that branched to 4150b57cec5SDimitry Andric // the loop end as its location). 4160b57cec5SDimitry Andric InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet); 4170b57cec5SDimitry Andric DebugLoc EndDL = AfterLoop->pred_empty() 4180b57cec5SDimitry Andric ? DebugLoc() 4190b57cec5SDimitry Andric : (*AfterLoop->pred_rbegin())->findBranchDebugLoc(); 4200b57cec5SDimitry Andric MachineInstr *End = 4210b57cec5SDimitry Andric BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP)); 4220b57cec5SDimitry Andric registerScope(Begin, End); 4230b57cec5SDimitry Andric 4240b57cec5SDimitry Andric assert((!ScopeTops[AfterLoop->getNumber()] || 4250b57cec5SDimitry Andric ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) && 4260b57cec5SDimitry Andric "With block sorting the outermost loop for a block should be first."); 427e8d8bef9SDimitry Andric updateScopeTops(&MBB, AfterLoop); 4280b57cec5SDimitry Andric } 4290b57cec5SDimitry Andric 4300b57cec5SDimitry Andric void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) { 4310b57cec5SDimitry Andric assert(MBB.isEHPad()); 4320b57cec5SDimitry Andric MachineFunction &MF = *MBB.getParent(); 4330b57cec5SDimitry Andric auto &MDT = getAnalysis<MachineDominatorTree>(); 4340b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 435e8d8bef9SDimitry Andric const auto &MLI = getAnalysis<MachineLoopInfo>(); 4360b57cec5SDimitry Andric const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); 437e8d8bef9SDimitry Andric SortRegionInfo SRI(MLI, WEI); 4380b57cec5SDimitry Andric const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 4390b57cec5SDimitry Andric 4400b57cec5SDimitry Andric // Compute the nearest common dominator of all unwind predecessors 4410b57cec5SDimitry Andric MachineBasicBlock *Header = nullptr; 4420b57cec5SDimitry Andric int MBBNumber = MBB.getNumber(); 4430b57cec5SDimitry Andric for (auto *Pred : MBB.predecessors()) { 4440b57cec5SDimitry Andric if (Pred->getNumber() < MBBNumber) { 4450b57cec5SDimitry Andric Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 4460b57cec5SDimitry Andric assert(!explicitlyBranchesTo(Pred, &MBB) && 4470b57cec5SDimitry Andric "Explicit branch to an EH pad!"); 4480b57cec5SDimitry Andric } 4490b57cec5SDimitry Andric } 4500b57cec5SDimitry Andric if (!Header) 4510b57cec5SDimitry Andric return; 4520b57cec5SDimitry Andric 4530b57cec5SDimitry Andric // If this try is at the bottom of the function, insert a dummy block at the 4540b57cec5SDimitry Andric // end. 4550b57cec5SDimitry Andric WebAssemblyException *WE = WEI.getExceptionFor(&MBB); 4560b57cec5SDimitry Andric assert(WE); 457e8d8bef9SDimitry Andric MachineBasicBlock *Bottom = SRI.getBottom(WE); 4580b57cec5SDimitry Andric 4590b57cec5SDimitry Andric auto Iter = std::next(Bottom->getIterator()); 4600b57cec5SDimitry Andric if (Iter == MF.end()) { 4610b57cec5SDimitry Andric getAppendixBlock(MF); 4620b57cec5SDimitry Andric Iter = std::next(Bottom->getIterator()); 4630b57cec5SDimitry Andric } 4640b57cec5SDimitry Andric MachineBasicBlock *Cont = &*Iter; 4650b57cec5SDimitry Andric 4660b57cec5SDimitry Andric assert(Cont != &MF.front()); 4670b57cec5SDimitry Andric MachineBasicBlock *LayoutPred = Cont->getPrevNode(); 4680b57cec5SDimitry Andric 4690b57cec5SDimitry Andric // If the nearest common dominator is inside a more deeply nested context, 4700b57cec5SDimitry Andric // walk out to the nearest scope which isn't more deeply nested. 4710b57cec5SDimitry Andric for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 4720b57cec5SDimitry Andric if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 4730b57cec5SDimitry Andric if (ScopeTop->getNumber() > Header->getNumber()) { 4740b57cec5SDimitry Andric // Skip over an intervening scope. 4750b57cec5SDimitry Andric I = std::next(ScopeTop->getIterator()); 4760b57cec5SDimitry Andric } else { 4770b57cec5SDimitry Andric // We found a scope level at an appropriate depth. 4780b57cec5SDimitry Andric Header = ScopeTop; 4790b57cec5SDimitry Andric break; 4800b57cec5SDimitry Andric } 4810b57cec5SDimitry Andric } 4820b57cec5SDimitry Andric } 4830b57cec5SDimitry Andric 4840b57cec5SDimitry Andric // Decide where in Header to put the TRY. 4850b57cec5SDimitry Andric 4860b57cec5SDimitry Andric // Instructions that should go before the TRY. 4870b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> BeforeSet; 4880b57cec5SDimitry Andric // Instructions that should go after the TRY. 4890b57cec5SDimitry Andric SmallPtrSet<const MachineInstr *, 4> AfterSet; 4900b57cec5SDimitry Andric for (const auto &MI : *Header) { 4910b57cec5SDimitry Andric // If there is a previously placed LOOP marker and the bottom block of the 4920b57cec5SDimitry Andric // loop is above MBB, it should be after the TRY, because the loop is nested 4930b57cec5SDimitry Andric // in this TRY. Otherwise it should be before the TRY. 4940b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::LOOP) { 4950b57cec5SDimitry Andric auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); 4960b57cec5SDimitry Andric if (MBB.getNumber() > LoopBottom->getNumber()) 4970b57cec5SDimitry Andric AfterSet.insert(&MI); 4980b57cec5SDimitry Andric #ifndef NDEBUG 4990b57cec5SDimitry Andric else 5000b57cec5SDimitry Andric BeforeSet.insert(&MI); 5010b57cec5SDimitry Andric #endif 5020b57cec5SDimitry Andric } 5030b57cec5SDimitry Andric 5040b57cec5SDimitry Andric // All previously inserted BLOCK/TRY markers should be after the TRY because 5050b57cec5SDimitry Andric // they are all nested trys. 5060b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::BLOCK || 5070b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::TRY) 5080b57cec5SDimitry Andric AfterSet.insert(&MI); 5090b57cec5SDimitry Andric 5100b57cec5SDimitry Andric #ifndef NDEBUG 5110b57cec5SDimitry Andric // All END_(BLOCK/LOOP/TRY) markers should be before the TRY. 5120b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_BLOCK || 5130b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_LOOP || 5140b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::END_TRY) 5150b57cec5SDimitry Andric BeforeSet.insert(&MI); 5160b57cec5SDimitry Andric #endif 5170b57cec5SDimitry Andric 5180b57cec5SDimitry Andric // Terminators should go after the TRY. 5190b57cec5SDimitry Andric if (MI.isTerminator()) 5200b57cec5SDimitry Andric AfterSet.insert(&MI); 5210b57cec5SDimitry Andric } 5220b57cec5SDimitry Andric 5238bcb0991SDimitry Andric // If Header unwinds to MBB (= Header contains 'invoke'), the try block should 5248bcb0991SDimitry Andric // contain the call within it. So the call should go after the TRY. The 5258bcb0991SDimitry Andric // exception is when the header's terminator is a rethrow instruction, in 5268bcb0991SDimitry Andric // which case that instruction, not a call instruction before it, is gonna 5278bcb0991SDimitry Andric // throw. 5288bcb0991SDimitry Andric MachineInstr *ThrowingCall = nullptr; 5298bcb0991SDimitry Andric if (MBB.isPredecessor(Header)) { 5308bcb0991SDimitry Andric auto TermPos = Header->getFirstTerminator(); 5318bcb0991SDimitry Andric if (TermPos == Header->end() || 5328bcb0991SDimitry Andric TermPos->getOpcode() != WebAssembly::RETHROW) { 5338bcb0991SDimitry Andric for (auto &MI : reverse(*Header)) { 5348bcb0991SDimitry Andric if (MI.isCall()) { 5358bcb0991SDimitry Andric AfterSet.insert(&MI); 5368bcb0991SDimitry Andric ThrowingCall = &MI; 5378bcb0991SDimitry Andric // Possibly throwing calls are usually wrapped by EH_LABEL 5388bcb0991SDimitry Andric // instructions. We don't want to split them and the call. 5398bcb0991SDimitry Andric if (MI.getIterator() != Header->begin() && 5408bcb0991SDimitry Andric std::prev(MI.getIterator())->isEHLabel()) { 5418bcb0991SDimitry Andric AfterSet.insert(&*std::prev(MI.getIterator())); 5428bcb0991SDimitry Andric ThrowingCall = &*std::prev(MI.getIterator()); 5438bcb0991SDimitry Andric } 5448bcb0991SDimitry Andric break; 5458bcb0991SDimitry Andric } 5468bcb0991SDimitry Andric } 5478bcb0991SDimitry Andric } 5488bcb0991SDimitry Andric } 5498bcb0991SDimitry Andric 5500b57cec5SDimitry Andric // Local expression tree should go after the TRY. 5518bcb0991SDimitry Andric // For BLOCK placement, we start the search from the previous instruction of a 5528bcb0991SDimitry Andric // BB's terminator, but in TRY's case, we should start from the previous 5538bcb0991SDimitry Andric // instruction of a call that can throw, or a EH_LABEL that precedes the call, 5548bcb0991SDimitry Andric // because the return values of the call's previous instructions can be 5558bcb0991SDimitry Andric // stackified and consumed by the throwing call. 5568bcb0991SDimitry Andric auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall) 5578bcb0991SDimitry Andric : Header->getFirstTerminator(); 5588bcb0991SDimitry Andric for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) { 5590b57cec5SDimitry Andric if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 5600b57cec5SDimitry Andric continue; 5610b57cec5SDimitry Andric if (WebAssembly::isChild(*std::prev(I), MFI)) 5620b57cec5SDimitry Andric AfterSet.insert(&*std::prev(I)); 5630b57cec5SDimitry Andric else 5640b57cec5SDimitry Andric break; 5650b57cec5SDimitry Andric } 5660b57cec5SDimitry Andric 5670b57cec5SDimitry Andric // Add the TRY. 5680b57cec5SDimitry Andric auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); 5690b57cec5SDimitry Andric MachineInstr *Begin = 5700b57cec5SDimitry Andric BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 5710b57cec5SDimitry Andric TII.get(WebAssembly::TRY)) 5728bcb0991SDimitry Andric .addImm(int64_t(WebAssembly::BlockType::Void)); 5730b57cec5SDimitry Andric 5740b57cec5SDimitry Andric // Decide where in Header to put the END_TRY. 5750b57cec5SDimitry Andric BeforeSet.clear(); 5760b57cec5SDimitry Andric AfterSet.clear(); 5770b57cec5SDimitry Andric for (const auto &MI : *Cont) { 5780b57cec5SDimitry Andric #ifndef NDEBUG 5790b57cec5SDimitry Andric // END_TRY should precede existing LOOP and BLOCK markers. 5800b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::LOOP || 5810b57cec5SDimitry Andric MI.getOpcode() == WebAssembly::BLOCK) 5820b57cec5SDimitry Andric AfterSet.insert(&MI); 5830b57cec5SDimitry Andric 5840b57cec5SDimitry Andric // All END_TRY markers placed earlier belong to exceptions that contains 5850b57cec5SDimitry Andric // this one. 5860b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_TRY) 5870b57cec5SDimitry Andric AfterSet.insert(&MI); 5880b57cec5SDimitry Andric #endif 5890b57cec5SDimitry Andric 5900b57cec5SDimitry Andric // If there is a previously placed END_LOOP marker and its header is after 5910b57cec5SDimitry Andric // where TRY marker is, this loop is contained within the 'catch' part, so 5920b57cec5SDimitry Andric // the END_TRY marker should go after that. Otherwise, the whole try-catch 5930b57cec5SDimitry Andric // is contained within this loop, so the END_TRY should go before that. 5940b57cec5SDimitry Andric if (MI.getOpcode() == WebAssembly::END_LOOP) { 5950b57cec5SDimitry Andric // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they 5960b57cec5SDimitry Andric // are in the same BB, LOOP is always before TRY. 5970b57cec5SDimitry Andric if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber()) 5980b57cec5SDimitry Andric BeforeSet.insert(&MI); 5990b57cec5SDimitry Andric #ifndef NDEBUG 6000b57cec5SDimitry Andric else 6010b57cec5SDimitry Andric AfterSet.insert(&MI); 6020b57cec5SDimitry Andric #endif 6030b57cec5SDimitry Andric } 6040b57cec5SDimitry Andric 6050b57cec5SDimitry Andric // It is not possible for an END_BLOCK to be already in this block. 6060b57cec5SDimitry Andric } 6070b57cec5SDimitry Andric 6080b57cec5SDimitry Andric // Mark the end of the TRY. 6090b57cec5SDimitry Andric InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet); 6100b57cec5SDimitry Andric MachineInstr *End = 6110b57cec5SDimitry Andric BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(), 6120b57cec5SDimitry Andric TII.get(WebAssembly::END_TRY)); 6130b57cec5SDimitry Andric registerTryScope(Begin, End, &MBB); 6140b57cec5SDimitry Andric 6150b57cec5SDimitry Andric // Track the farthest-spanning scope that ends at this point. We create two 6160b57cec5SDimitry Andric // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB 6170b57cec5SDimitry Andric // with 'try'). We need to create 'catch' -> 'try' mapping here too because 6180b57cec5SDimitry Andric // markers should not span across 'catch'. For example, this should not 6190b57cec5SDimitry Andric // happen: 6200b57cec5SDimitry Andric // 6210b57cec5SDimitry Andric // try 6220b57cec5SDimitry Andric // block --| (X) 6230b57cec5SDimitry Andric // catch | 6240b57cec5SDimitry Andric // end_block --| 6250b57cec5SDimitry Andric // end_try 626e8d8bef9SDimitry Andric for (auto *End : {&MBB, Cont}) 627e8d8bef9SDimitry Andric updateScopeTops(Header, End); 6280b57cec5SDimitry Andric } 6290b57cec5SDimitry Andric 6300b57cec5SDimitry Andric void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) { 6310b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 6320b57cec5SDimitry Andric 6330b57cec5SDimitry Andric // When there is an unconditional branch right before a catch instruction and 6340b57cec5SDimitry Andric // it branches to the end of end_try marker, we don't need the branch, because 6350b57cec5SDimitry Andric // it there is no exception, the control flow transfers to that point anyway. 6360b57cec5SDimitry Andric // bb0: 6370b57cec5SDimitry Andric // try 6380b57cec5SDimitry Andric // ... 6390b57cec5SDimitry Andric // br bb2 <- Not necessary 640e8d8bef9SDimitry Andric // bb1 (ehpad): 6410b57cec5SDimitry Andric // catch 6420b57cec5SDimitry Andric // ... 643e8d8bef9SDimitry Andric // bb2: <- Continuation BB 6440b57cec5SDimitry Andric // end 645e8d8bef9SDimitry Andric // 646e8d8bef9SDimitry Andric // A more involved case: When the BB where 'end' is located is an another EH 647e8d8bef9SDimitry Andric // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example, 648e8d8bef9SDimitry Andric // bb0: 649e8d8bef9SDimitry Andric // try 650e8d8bef9SDimitry Andric // try 651e8d8bef9SDimitry Andric // ... 652e8d8bef9SDimitry Andric // br bb3 <- Not necessary 653e8d8bef9SDimitry Andric // bb1 (ehpad): 654e8d8bef9SDimitry Andric // catch 655e8d8bef9SDimitry Andric // bb2 (ehpad): 656e8d8bef9SDimitry Andric // end 657e8d8bef9SDimitry Andric // catch 658e8d8bef9SDimitry Andric // ... 659e8d8bef9SDimitry Andric // bb3: <- Continuation BB 660e8d8bef9SDimitry Andric // end 661e8d8bef9SDimitry Andric // 662e8d8bef9SDimitry Andric // When the EH pad at hand is bb1, its matching end_try is in bb2. But it is 663e8d8bef9SDimitry Andric // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the 664e8d8bef9SDimitry Andric // code can be deleted. This is why we run 'while' until 'Cont' is not an EH 665e8d8bef9SDimitry Andric // pad. 6660b57cec5SDimitry Andric for (auto &MBB : MF) { 6670b57cec5SDimitry Andric if (!MBB.isEHPad()) 6680b57cec5SDimitry Andric continue; 6690b57cec5SDimitry Andric 6700b57cec5SDimitry Andric MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 6710b57cec5SDimitry Andric SmallVector<MachineOperand, 4> Cond; 6720b57cec5SDimitry Andric MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode(); 673e8d8bef9SDimitry Andric 674e8d8bef9SDimitry Andric MachineBasicBlock *Cont = &MBB; 675e8d8bef9SDimitry Andric while (Cont->isEHPad()) { 676e8d8bef9SDimitry Andric MachineInstr *Try = EHPadToTry[Cont]; 677e8d8bef9SDimitry Andric MachineInstr *EndTry = BeginToEnd[Try]; 678e8d8bef9SDimitry Andric Cont = EndTry->getParent(); 679e8d8bef9SDimitry Andric } 680e8d8bef9SDimitry Andric 6810b57cec5SDimitry Andric bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond); 6825ffd83dbSDimitry Andric // This condition means either 6835ffd83dbSDimitry Andric // 1. This BB ends with a single unconditional branch whose destinaion is 6845ffd83dbSDimitry Andric // Cont. 6855ffd83dbSDimitry Andric // 2. This BB ends with a conditional branch followed by an unconditional 6865ffd83dbSDimitry Andric // branch, and the unconditional branch's destination is Cont. 6875ffd83dbSDimitry Andric // In both cases, we want to remove the last (= unconditional) branch. 6880b57cec5SDimitry Andric if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) || 6895ffd83dbSDimitry Andric (!Cond.empty() && FBB && FBB == Cont))) { 6905ffd83dbSDimitry Andric bool ErasedUncondBr = false; 6915ffd83dbSDimitry Andric (void)ErasedUncondBr; 6925ffd83dbSDimitry Andric for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin(); 6935ffd83dbSDimitry Andric I != E; --I) { 6945ffd83dbSDimitry Andric auto PrevI = std::prev(I); 6955ffd83dbSDimitry Andric if (PrevI->isTerminator()) { 6965ffd83dbSDimitry Andric assert(PrevI->getOpcode() == WebAssembly::BR); 6975ffd83dbSDimitry Andric PrevI->eraseFromParent(); 6985ffd83dbSDimitry Andric ErasedUncondBr = true; 6995ffd83dbSDimitry Andric break; 7005ffd83dbSDimitry Andric } 7015ffd83dbSDimitry Andric } 7025ffd83dbSDimitry Andric assert(ErasedUncondBr && "Unconditional branch not erased!"); 7035ffd83dbSDimitry Andric } 7040b57cec5SDimitry Andric } 7050b57cec5SDimitry Andric 7060b57cec5SDimitry Andric // When there are block / end_block markers that overlap with try / end_try 7070b57cec5SDimitry Andric // markers, and the block and try markers' return types are the same, the 7080b57cec5SDimitry Andric // block /end_block markers are not necessary, because try / end_try markers 7090b57cec5SDimitry Andric // also can serve as boundaries for branches. 7100b57cec5SDimitry Andric // block <- Not necessary 7110b57cec5SDimitry Andric // try 7120b57cec5SDimitry Andric // ... 7130b57cec5SDimitry Andric // catch 7140b57cec5SDimitry Andric // ... 7150b57cec5SDimitry Andric // end 7160b57cec5SDimitry Andric // end <- Not necessary 7170b57cec5SDimitry Andric SmallVector<MachineInstr *, 32> ToDelete; 7180b57cec5SDimitry Andric for (auto &MBB : MF) { 7190b57cec5SDimitry Andric for (auto &MI : MBB) { 7200b57cec5SDimitry Andric if (MI.getOpcode() != WebAssembly::TRY) 7210b57cec5SDimitry Andric continue; 7220b57cec5SDimitry Andric 7230b57cec5SDimitry Andric MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try]; 7240b57cec5SDimitry Andric MachineBasicBlock *TryBB = Try->getParent(); 7250b57cec5SDimitry Andric MachineBasicBlock *Cont = EndTry->getParent(); 7260b57cec5SDimitry Andric int64_t RetType = Try->getOperand(0).getImm(); 7270b57cec5SDimitry Andric for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator()); 7280b57cec5SDimitry Andric B != TryBB->begin() && E != Cont->end() && 7290b57cec5SDimitry Andric std::prev(B)->getOpcode() == WebAssembly::BLOCK && 7300b57cec5SDimitry Andric E->getOpcode() == WebAssembly::END_BLOCK && 7310b57cec5SDimitry Andric std::prev(B)->getOperand(0).getImm() == RetType; 7320b57cec5SDimitry Andric --B, ++E) { 7330b57cec5SDimitry Andric ToDelete.push_back(&*std::prev(B)); 7340b57cec5SDimitry Andric ToDelete.push_back(&*E); 7350b57cec5SDimitry Andric } 7360b57cec5SDimitry Andric } 7370b57cec5SDimitry Andric } 7380b57cec5SDimitry Andric for (auto *MI : ToDelete) { 7390b57cec5SDimitry Andric if (MI->getOpcode() == WebAssembly::BLOCK) 7400b57cec5SDimitry Andric unregisterScope(MI); 7410b57cec5SDimitry Andric MI->eraseFromParent(); 7420b57cec5SDimitry Andric } 7430b57cec5SDimitry Andric } 7440b57cec5SDimitry Andric 7455ffd83dbSDimitry Andric // Get the appropriate copy opcode for the given register class. 7465ffd83dbSDimitry Andric static unsigned getCopyOpcode(const TargetRegisterClass *RC) { 7475ffd83dbSDimitry Andric if (RC == &WebAssembly::I32RegClass) 7485ffd83dbSDimitry Andric return WebAssembly::COPY_I32; 7495ffd83dbSDimitry Andric if (RC == &WebAssembly::I64RegClass) 7505ffd83dbSDimitry Andric return WebAssembly::COPY_I64; 7515ffd83dbSDimitry Andric if (RC == &WebAssembly::F32RegClass) 7525ffd83dbSDimitry Andric return WebAssembly::COPY_F32; 7535ffd83dbSDimitry Andric if (RC == &WebAssembly::F64RegClass) 7545ffd83dbSDimitry Andric return WebAssembly::COPY_F64; 7555ffd83dbSDimitry Andric if (RC == &WebAssembly::V128RegClass) 7565ffd83dbSDimitry Andric return WebAssembly::COPY_V128; 757e8d8bef9SDimitry Andric if (RC == &WebAssembly::FUNCREFRegClass) 758e8d8bef9SDimitry Andric return WebAssembly::COPY_FUNCREF; 759e8d8bef9SDimitry Andric if (RC == &WebAssembly::EXTERNREFRegClass) 760e8d8bef9SDimitry Andric return WebAssembly::COPY_EXTERNREF; 7615ffd83dbSDimitry Andric llvm_unreachable("Unexpected register class"); 7625ffd83dbSDimitry Andric } 7635ffd83dbSDimitry Andric 7648bcb0991SDimitry Andric // When MBB is split into MBB and Split, we should unstackify defs in MBB that 7658bcb0991SDimitry Andric // have their uses in Split. 766e8d8bef9SDimitry Andric // FIXME This function will be used when fixing unwind mismatches, but the old 767e8d8bef9SDimitry Andric // version of that function was removed for the moment and the new version has 768e8d8bef9SDimitry Andric // not yet been added. So 'LLVM_ATTRIBUTE_UNUSED' is added to suppress the 769e8d8bef9SDimitry Andric // warning. Remove the attribute after the new functionality is added. 770e8d8bef9SDimitry Andric LLVM_ATTRIBUTE_UNUSED static void 771e8d8bef9SDimitry Andric unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, MachineBasicBlock &Split) { 772e8d8bef9SDimitry Andric MachineFunction &MF = *MBB.getParent(); 773e8d8bef9SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 774e8d8bef9SDimitry Andric auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 775e8d8bef9SDimitry Andric auto &MRI = MF.getRegInfo(); 776e8d8bef9SDimitry Andric 7778bcb0991SDimitry Andric for (auto &MI : Split) { 7788bcb0991SDimitry Andric for (auto &MO : MI.explicit_uses()) { 7798bcb0991SDimitry Andric if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg())) 7808bcb0991SDimitry Andric continue; 7818bcb0991SDimitry Andric if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg())) 7828bcb0991SDimitry Andric if (Def->getParent() == &MBB) 7838bcb0991SDimitry Andric MFI.unstackifyVReg(MO.getReg()); 7848bcb0991SDimitry Andric } 7858bcb0991SDimitry Andric } 7865ffd83dbSDimitry Andric 7875ffd83dbSDimitry Andric // In RegStackify, when a register definition is used multiple times, 7885ffd83dbSDimitry Andric // Reg = INST ... 7895ffd83dbSDimitry Andric // INST ..., Reg, ... 7905ffd83dbSDimitry Andric // INST ..., Reg, ... 7915ffd83dbSDimitry Andric // INST ..., Reg, ... 7925ffd83dbSDimitry Andric // 7935ffd83dbSDimitry Andric // we introduce a TEE, which has the following form: 7945ffd83dbSDimitry Andric // DefReg = INST ... 7955ffd83dbSDimitry Andric // TeeReg, Reg = TEE_... DefReg 7965ffd83dbSDimitry Andric // INST ..., TeeReg, ... 7975ffd83dbSDimitry Andric // INST ..., Reg, ... 7985ffd83dbSDimitry Andric // INST ..., Reg, ... 7995ffd83dbSDimitry Andric // with DefReg and TeeReg stackified but Reg not stackified. 8005ffd83dbSDimitry Andric // 8015ffd83dbSDimitry Andric // But the invariant that TeeReg should be stackified can be violated while we 8025ffd83dbSDimitry Andric // unstackify registers in the split BB above. In this case, we convert TEEs 8035ffd83dbSDimitry Andric // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals. 8045ffd83dbSDimitry Andric // DefReg = INST ... 8055ffd83dbSDimitry Andric // TeeReg = COPY DefReg 8065ffd83dbSDimitry Andric // Reg = COPY DefReg 8075ffd83dbSDimitry Andric // INST ..., TeeReg, ... 8085ffd83dbSDimitry Andric // INST ..., Reg, ... 8095ffd83dbSDimitry Andric // INST ..., Reg, ... 8105ffd83dbSDimitry Andric for (auto I = MBB.begin(), E = MBB.end(); I != E;) { 8115ffd83dbSDimitry Andric MachineInstr &MI = *I++; 8125ffd83dbSDimitry Andric if (!WebAssembly::isTee(MI.getOpcode())) 8135ffd83dbSDimitry Andric continue; 8145ffd83dbSDimitry Andric Register TeeReg = MI.getOperand(0).getReg(); 8155ffd83dbSDimitry Andric Register Reg = MI.getOperand(1).getReg(); 8165ffd83dbSDimitry Andric Register DefReg = MI.getOperand(2).getReg(); 8175ffd83dbSDimitry Andric if (!MFI.isVRegStackified(TeeReg)) { 8185ffd83dbSDimitry Andric // Now we are not using TEE anymore, so unstackify DefReg too 8195ffd83dbSDimitry Andric MFI.unstackifyVReg(DefReg); 8205ffd83dbSDimitry Andric unsigned CopyOpc = getCopyOpcode(MRI.getRegClass(DefReg)); 8215ffd83dbSDimitry Andric BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg) 8225ffd83dbSDimitry Andric .addReg(DefReg); 8235ffd83dbSDimitry Andric BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg); 8245ffd83dbSDimitry Andric MI.eraseFromParent(); 8255ffd83dbSDimitry Andric } 8265ffd83dbSDimitry Andric } 8278bcb0991SDimitry Andric } 8288bcb0991SDimitry Andric 8290b57cec5SDimitry Andric bool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) { 830e8d8bef9SDimitry Andric // TODO Implement this 8310b57cec5SDimitry Andric return false; 8320b57cec5SDimitry Andric } 8330b57cec5SDimitry Andric 8340b57cec5SDimitry Andric static unsigned 8350b57cec5SDimitry Andric getDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack, 8360b57cec5SDimitry Andric const MachineBasicBlock *MBB) { 8370b57cec5SDimitry Andric unsigned Depth = 0; 8380b57cec5SDimitry Andric for (auto X : reverse(Stack)) { 8390b57cec5SDimitry Andric if (X == MBB) 8400b57cec5SDimitry Andric break; 8410b57cec5SDimitry Andric ++Depth; 8420b57cec5SDimitry Andric } 8430b57cec5SDimitry Andric assert(Depth < Stack.size() && "Branch destination should be in scope"); 8440b57cec5SDimitry Andric return Depth; 8450b57cec5SDimitry Andric } 8460b57cec5SDimitry Andric 8470b57cec5SDimitry Andric /// In normal assembly languages, when the end of a function is unreachable, 8480b57cec5SDimitry Andric /// because the function ends in an infinite loop or a noreturn call or similar, 8490b57cec5SDimitry Andric /// it isn't necessary to worry about the function return type at the end of 8500b57cec5SDimitry Andric /// the function, because it's never reached. However, in WebAssembly, blocks 8510b57cec5SDimitry Andric /// that end at the function end need to have a return type signature that 8520b57cec5SDimitry Andric /// matches the function signature, even though it's unreachable. This function 8530b57cec5SDimitry Andric /// checks for such cases and fixes up the signatures. 8540b57cec5SDimitry Andric void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { 8550b57cec5SDimitry Andric const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 8560b57cec5SDimitry Andric 8570b57cec5SDimitry Andric if (MFI.getResults().empty()) 8580b57cec5SDimitry Andric return; 8590b57cec5SDimitry Andric 8608bcb0991SDimitry Andric // MCInstLower will add the proper types to multivalue signatures based on the 8618bcb0991SDimitry Andric // function return type 8628bcb0991SDimitry Andric WebAssembly::BlockType RetType = 8638bcb0991SDimitry Andric MFI.getResults().size() > 1 8648bcb0991SDimitry Andric ? WebAssembly::BlockType::Multivalue 8658bcb0991SDimitry Andric : WebAssembly::BlockType( 8668bcb0991SDimitry Andric WebAssembly::toValType(MFI.getResults().front())); 8670b57cec5SDimitry Andric 868e8d8bef9SDimitry Andric SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist; 869e8d8bef9SDimitry Andric Worklist.push_back(MF.rbegin()->rbegin()); 870e8d8bef9SDimitry Andric 871e8d8bef9SDimitry Andric auto Process = [&](MachineBasicBlock::reverse_iterator It) { 872e8d8bef9SDimitry Andric auto *MBB = It->getParent(); 873e8d8bef9SDimitry Andric while (It != MBB->rend()) { 874e8d8bef9SDimitry Andric MachineInstr &MI = *It++; 8750b57cec5SDimitry Andric if (MI.isPosition() || MI.isDebugInstr()) 8760b57cec5SDimitry Andric continue; 8778bcb0991SDimitry Andric switch (MI.getOpcode()) { 878e8d8bef9SDimitry Andric case WebAssembly::END_TRY: { 879e8d8bef9SDimitry Andric // If a 'try''s return type is fixed, both its try body and catch body 880e8d8bef9SDimitry Andric // should satisfy the return type, so we need to search 'end' 881e8d8bef9SDimitry Andric // instructions before its corresponding 'catch' too. 882e8d8bef9SDimitry Andric auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]); 883e8d8bef9SDimitry Andric assert(EHPad); 884e8d8bef9SDimitry Andric auto NextIt = 885e8d8bef9SDimitry Andric std::next(WebAssembly::findCatch(EHPad)->getReverseIterator()); 886e8d8bef9SDimitry Andric if (NextIt != EHPad->rend()) 887e8d8bef9SDimitry Andric Worklist.push_back(NextIt); 888e8d8bef9SDimitry Andric LLVM_FALLTHROUGH; 889e8d8bef9SDimitry Andric } 8908bcb0991SDimitry Andric case WebAssembly::END_BLOCK: 8918bcb0991SDimitry Andric case WebAssembly::END_LOOP: 8920b57cec5SDimitry Andric EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType)); 8930b57cec5SDimitry Andric continue; 8948bcb0991SDimitry Andric default: 895e8d8bef9SDimitry Andric // Something other than an `end`. We're done for this BB. 8960b57cec5SDimitry Andric return; 8970b57cec5SDimitry Andric } 8980b57cec5SDimitry Andric } 899e8d8bef9SDimitry Andric // We've reached the beginning of a BB. Continue the search in the previous 900e8d8bef9SDimitry Andric // BB. 901e8d8bef9SDimitry Andric Worklist.push_back(MBB->getPrevNode()->rbegin()); 902e8d8bef9SDimitry Andric }; 903e8d8bef9SDimitry Andric 904e8d8bef9SDimitry Andric while (!Worklist.empty()) 905e8d8bef9SDimitry Andric Process(Worklist.pop_back_val()); 9068bcb0991SDimitry Andric } 9070b57cec5SDimitry Andric 9080b57cec5SDimitry Andric // WebAssembly functions end with an end instruction, as if the function body 9090b57cec5SDimitry Andric // were a block. 9100b57cec5SDimitry Andric static void appendEndToFunction(MachineFunction &MF, 9110b57cec5SDimitry Andric const WebAssemblyInstrInfo &TII) { 9120b57cec5SDimitry Andric BuildMI(MF.back(), MF.back().end(), 9130b57cec5SDimitry Andric MF.back().findPrevDebugLoc(MF.back().end()), 9140b57cec5SDimitry Andric TII.get(WebAssembly::END_FUNCTION)); 9150b57cec5SDimitry Andric } 9160b57cec5SDimitry Andric 9170b57cec5SDimitry Andric /// Insert LOOP/TRY/BLOCK markers at appropriate places. 9180b57cec5SDimitry Andric void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { 9190b57cec5SDimitry Andric // We allocate one more than the number of blocks in the function to 9200b57cec5SDimitry Andric // accommodate for the possible fake block we may insert at the end. 9210b57cec5SDimitry Andric ScopeTops.resize(MF.getNumBlockIDs() + 1); 9220b57cec5SDimitry Andric // Place the LOOP for MBB if MBB is the header of a loop. 9230b57cec5SDimitry Andric for (auto &MBB : MF) 9240b57cec5SDimitry Andric placeLoopMarker(MBB); 9250b57cec5SDimitry Andric 9260b57cec5SDimitry Andric const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 9270b57cec5SDimitry Andric for (auto &MBB : MF) { 9280b57cec5SDimitry Andric if (MBB.isEHPad()) { 9290b57cec5SDimitry Andric // Place the TRY for MBB if MBB is the EH pad of an exception. 9300b57cec5SDimitry Andric if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 9310b57cec5SDimitry Andric MF.getFunction().hasPersonalityFn()) 9320b57cec5SDimitry Andric placeTryMarker(MBB); 9330b57cec5SDimitry Andric } else { 9340b57cec5SDimitry Andric // Place the BLOCK for MBB if MBB is branched to from above. 9350b57cec5SDimitry Andric placeBlockMarker(MBB); 9360b57cec5SDimitry Andric } 9370b57cec5SDimitry Andric } 9380b57cec5SDimitry Andric // Fix mismatches in unwind destinations induced by linearizing the code. 9398bcb0991SDimitry Andric if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 9408bcb0991SDimitry Andric MF.getFunction().hasPersonalityFn()) 9410b57cec5SDimitry Andric fixUnwindMismatches(MF); 9420b57cec5SDimitry Andric } 9430b57cec5SDimitry Andric 9440b57cec5SDimitry Andric void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { 9450b57cec5SDimitry Andric // Now rewrite references to basic blocks to be depth immediates. 9460b57cec5SDimitry Andric SmallVector<const MachineBasicBlock *, 8> Stack; 9470b57cec5SDimitry Andric for (auto &MBB : reverse(MF)) { 9480b57cec5SDimitry Andric for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) { 9490b57cec5SDimitry Andric MachineInstr &MI = *I; 9500b57cec5SDimitry Andric switch (MI.getOpcode()) { 9510b57cec5SDimitry Andric case WebAssembly::BLOCK: 9520b57cec5SDimitry Andric case WebAssembly::TRY: 9530b57cec5SDimitry Andric assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= 9540b57cec5SDimitry Andric MBB.getNumber() && 9550b57cec5SDimitry Andric "Block/try marker should be balanced"); 9560b57cec5SDimitry Andric Stack.pop_back(); 9570b57cec5SDimitry Andric break; 9580b57cec5SDimitry Andric 9590b57cec5SDimitry Andric case WebAssembly::LOOP: 9600b57cec5SDimitry Andric assert(Stack.back() == &MBB && "Loop top should be balanced"); 9610b57cec5SDimitry Andric Stack.pop_back(); 9620b57cec5SDimitry Andric break; 9630b57cec5SDimitry Andric 9640b57cec5SDimitry Andric case WebAssembly::END_BLOCK: 9650b57cec5SDimitry Andric case WebAssembly::END_TRY: 9660b57cec5SDimitry Andric Stack.push_back(&MBB); 9670b57cec5SDimitry Andric break; 9680b57cec5SDimitry Andric 9690b57cec5SDimitry Andric case WebAssembly::END_LOOP: 9700b57cec5SDimitry Andric Stack.push_back(EndToBegin[&MI]->getParent()); 9710b57cec5SDimitry Andric break; 9720b57cec5SDimitry Andric 9730b57cec5SDimitry Andric default: 9740b57cec5SDimitry Andric if (MI.isTerminator()) { 9750b57cec5SDimitry Andric // Rewrite MBB operands to be depth immediates. 9760b57cec5SDimitry Andric SmallVector<MachineOperand, 4> Ops(MI.operands()); 9770b57cec5SDimitry Andric while (MI.getNumOperands() > 0) 9780b57cec5SDimitry Andric MI.RemoveOperand(MI.getNumOperands() - 1); 9790b57cec5SDimitry Andric for (auto MO : Ops) { 9800b57cec5SDimitry Andric if (MO.isMBB()) 9810b57cec5SDimitry Andric MO = MachineOperand::CreateImm(getDepth(Stack, MO.getMBB())); 9820b57cec5SDimitry Andric MI.addOperand(MF, MO); 9830b57cec5SDimitry Andric } 9840b57cec5SDimitry Andric } 9850b57cec5SDimitry Andric break; 9860b57cec5SDimitry Andric } 9870b57cec5SDimitry Andric } 9880b57cec5SDimitry Andric } 9890b57cec5SDimitry Andric assert(Stack.empty() && "Control flow should be balanced"); 9900b57cec5SDimitry Andric } 9910b57cec5SDimitry Andric 9920b57cec5SDimitry Andric void WebAssemblyCFGStackify::releaseMemory() { 9930b57cec5SDimitry Andric ScopeTops.clear(); 9940b57cec5SDimitry Andric BeginToEnd.clear(); 9950b57cec5SDimitry Andric EndToBegin.clear(); 9960b57cec5SDimitry Andric TryToEHPad.clear(); 9970b57cec5SDimitry Andric EHPadToTry.clear(); 9980b57cec5SDimitry Andric AppendixBB = nullptr; 9990b57cec5SDimitry Andric } 10000b57cec5SDimitry Andric 10010b57cec5SDimitry Andric bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 10020b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n" 10030b57cec5SDimitry Andric "********** Function: " 10040b57cec5SDimitry Andric << MF.getName() << '\n'); 10050b57cec5SDimitry Andric const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 10060b57cec5SDimitry Andric 10070b57cec5SDimitry Andric releaseMemory(); 10080b57cec5SDimitry Andric 10090b57cec5SDimitry Andric // Liveness is not tracked for VALUE_STACK physreg. 10100b57cec5SDimitry Andric MF.getRegInfo().invalidateLiveness(); 10110b57cec5SDimitry Andric 10120b57cec5SDimitry Andric // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes. 10130b57cec5SDimitry Andric placeMarkers(MF); 10140b57cec5SDimitry Andric 10150b57cec5SDimitry Andric // Remove unnecessary instructions possibly introduced by try/end_trys. 10160b57cec5SDimitry Andric if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 10170b57cec5SDimitry Andric MF.getFunction().hasPersonalityFn()) 10180b57cec5SDimitry Andric removeUnnecessaryInstrs(MF); 10190b57cec5SDimitry Andric 10200b57cec5SDimitry Andric // Convert MBB operands in terminators to relative depth immediates. 10210b57cec5SDimitry Andric rewriteDepthImmediates(MF); 10220b57cec5SDimitry Andric 10230b57cec5SDimitry Andric // Fix up block/loop/try signatures at the end of the function to conform to 10240b57cec5SDimitry Andric // WebAssembly's rules. 10250b57cec5SDimitry Andric fixEndsAtEndOfFunction(MF); 10260b57cec5SDimitry Andric 10270b57cec5SDimitry Andric // Add an end instruction at the end of the function body. 10280b57cec5SDimitry Andric const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 10290b57cec5SDimitry Andric if (!MF.getSubtarget<WebAssemblySubtarget>() 10300b57cec5SDimitry Andric .getTargetTriple() 10310b57cec5SDimitry Andric .isOSBinFormatELF()) 10320b57cec5SDimitry Andric appendEndToFunction(MF, TII); 10330b57cec5SDimitry Andric 10340b57cec5SDimitry Andric MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified(); 10350b57cec5SDimitry Andric return true; 10360b57cec5SDimitry Andric } 1037