1292915Sdim//===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===// 2292915Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6292915Sdim// 7292915Sdim//===----------------------------------------------------------------------===// 8292915Sdim/// 9292915Sdim/// \file 10341825Sdim/// This file implements a CFG stacking pass. 11292915Sdim/// 12344779Sdim/// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes, 13344779Sdim/// since scope boundaries serve as the labels for WebAssembly's control 14344779Sdim/// transfers. 15292915Sdim/// 16292915Sdim/// This is sufficient to convert arbitrary CFGs into a form that works on 17292915Sdim/// WebAssembly, provided that all loops are single-entry. 18292915Sdim/// 19344779Sdim/// In case we use exceptions, this pass also fixes mismatches in unwind 20344779Sdim/// destinations created during transforming CFG into wasm structured format. 21344779Sdim/// 22292915Sdim//===----------------------------------------------------------------------===// 23292915Sdim 24292915Sdim#include "WebAssembly.h" 25344779Sdim#include "WebAssemblyExceptionInfo.h" 26309124Sdim#include "WebAssemblyMachineFunctionInfo.h" 27292915Sdim#include "WebAssemblySubtarget.h" 28314564Sdim#include "WebAssemblyUtilities.h" 29353358Sdim#include "llvm/ADT/Statistic.h" 30292915Sdim#include "llvm/CodeGen/MachineDominators.h" 31292915Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 32360784Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 33344779Sdim#include "llvm/MC/MCAsmInfo.h" 34292915Sdimusing namespace llvm; 35292915Sdim 36292915Sdim#define DEBUG_TYPE "wasm-cfg-stackify" 37292915Sdim 38353358SdimSTATISTIC(NumUnwindMismatches, "Number of EH pad unwind mismatches found"); 39353358Sdim 40292915Sdimnamespace { 41292915Sdimclass WebAssemblyCFGStackify final : public MachineFunctionPass { 42314564Sdim StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } 43292915Sdim 44292915Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 45292915Sdim AU.addRequired<MachineDominatorTree>(); 46292915Sdim AU.addRequired<MachineLoopInfo>(); 47344779Sdim AU.addRequired<WebAssemblyExceptionInfo>(); 48292915Sdim MachineFunctionPass::getAnalysisUsage(AU); 49292915Sdim } 50292915Sdim 51292915Sdim bool runOnMachineFunction(MachineFunction &MF) override; 52292915Sdim 53344779Sdim // For each block whose label represents the end of a scope, record the block 54344779Sdim // which holds the beginning of the scope. This will allow us to quickly skip 55344779Sdim // over scoped regions when walking blocks. 56344779Sdim SmallVector<MachineBasicBlock *, 8> ScopeTops; 57344779Sdim 58353358Sdim // Placing markers. 59344779Sdim void placeMarkers(MachineFunction &MF); 60344779Sdim void placeBlockMarker(MachineBasicBlock &MBB); 61344779Sdim void placeLoopMarker(MachineBasicBlock &MBB); 62344779Sdim void placeTryMarker(MachineBasicBlock &MBB); 63353358Sdim void removeUnnecessaryInstrs(MachineFunction &MF); 64353358Sdim bool fixUnwindMismatches(MachineFunction &MF); 65344779Sdim void rewriteDepthImmediates(MachineFunction &MF); 66344779Sdim void fixEndsAtEndOfFunction(MachineFunction &MF); 67344779Sdim 68344779Sdim // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY). 69344779Sdim DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd; 70344779Sdim // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY. 71344779Sdim DenseMap<const MachineInstr *, MachineInstr *> EndToBegin; 72344779Sdim // <TRY marker, EH pad> map 73344779Sdim DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad; 74344779Sdim // <EH pad, TRY marker> map 75344779Sdim DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry; 76344779Sdim 77353358Sdim // There can be an appendix block at the end of each function, shared for: 78353358Sdim // - creating a correct signature for fallthrough returns 79353358Sdim // - target for rethrows that need to unwind to the caller, but are trapped 80353358Sdim // inside another try/catch 81353358Sdim MachineBasicBlock *AppendixBB = nullptr; 82353358Sdim MachineBasicBlock *getAppendixBlock(MachineFunction &MF) { 83353358Sdim if (!AppendixBB) { 84353358Sdim AppendixBB = MF.CreateMachineBasicBlock(); 85353358Sdim // Give it a fake predecessor so that AsmPrinter prints its label. 86353358Sdim AppendixBB->addSuccessor(AppendixBB); 87353358Sdim MF.push_back(AppendixBB); 88353358Sdim } 89353358Sdim return AppendixBB; 90353358Sdim } 91353358Sdim 92353358Sdim // Helper functions to register / unregister scope information created by 93353358Sdim // marker instructions. 94344779Sdim void registerScope(MachineInstr *Begin, MachineInstr *End); 95344779Sdim void registerTryScope(MachineInstr *Begin, MachineInstr *End, 96344779Sdim MachineBasicBlock *EHPad); 97353358Sdim void unregisterScope(MachineInstr *Begin); 98344779Sdim 99292915Sdimpublic: 100292915Sdim static char ID; // Pass identification, replacement for typeid 101292915Sdim WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} 102344779Sdim ~WebAssemblyCFGStackify() override { releaseMemory(); } 103344779Sdim void releaseMemory() override; 104292915Sdim}; 105292915Sdim} // end anonymous namespace 106292915Sdim 107292915Sdimchar WebAssemblyCFGStackify::ID = 0; 108341825SdimINITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, 109353358Sdim "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false, 110344779Sdim false) 111341825Sdim 112292915SdimFunctionPass *llvm::createWebAssemblyCFGStackify() { 113292915Sdim return new WebAssemblyCFGStackify(); 114292915Sdim} 115292915Sdim 116292915Sdim/// Test whether Pred has any terminators explicitly branching to MBB, as 117292915Sdim/// opposed to falling through. Note that it's possible (eg. in unoptimized 118292915Sdim/// code) for a branch instruction to both branch to a block and fallthrough 119292915Sdim/// to it, so we check the actual branch operands to see if there are any 120292915Sdim/// explicit mentions. 121353358Sdimstatic bool explicitlyBranchesTo(MachineBasicBlock *Pred, 122294024Sdim MachineBasicBlock *MBB) { 123292915Sdim for (MachineInstr &MI : Pred->terminators()) 124353358Sdim for (MachineOperand &MO : MI.explicit_operands()) 125353358Sdim if (MO.isMBB() && MO.getMBB() == MBB) 126353358Sdim return true; 127292915Sdim return false; 128292915Sdim} 129292915Sdim 130344779Sdim// Returns an iterator to the earliest position possible within the MBB, 131344779Sdim// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 132344779Sdim// contains instructions that should go before the marker, and AfterSet contains 133344779Sdim// ones that should go after the marker. In this function, AfterSet is only 134344779Sdim// used for sanity checking. 135344779Sdimstatic MachineBasicBlock::iterator 136353358SdimgetEarliestInsertPos(MachineBasicBlock *MBB, 137344779Sdim const SmallPtrSet<const MachineInstr *, 4> &BeforeSet, 138344779Sdim const SmallPtrSet<const MachineInstr *, 4> &AfterSet) { 139344779Sdim auto InsertPos = MBB->end(); 140344779Sdim while (InsertPos != MBB->begin()) { 141344779Sdim if (BeforeSet.count(&*std::prev(InsertPos))) { 142344779Sdim#ifndef NDEBUG 143344779Sdim // Sanity check 144344779Sdim for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos) 145344779Sdim assert(!AfterSet.count(&*std::prev(Pos))); 146344779Sdim#endif 147344779Sdim break; 148344779Sdim } 149344779Sdim --InsertPos; 150344779Sdim } 151344779Sdim return InsertPos; 152344779Sdim} 153344779Sdim 154344779Sdim// Returns an iterator to the latest position possible within the MBB, 155344779Sdim// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 156344779Sdim// contains instructions that should go before the marker, and AfterSet contains 157344779Sdim// ones that should go after the marker. In this function, BeforeSet is only 158344779Sdim// used for sanity checking. 159344779Sdimstatic MachineBasicBlock::iterator 160353358SdimgetLatestInsertPos(MachineBasicBlock *MBB, 161344779Sdim const SmallPtrSet<const MachineInstr *, 4> &BeforeSet, 162344779Sdim const SmallPtrSet<const MachineInstr *, 4> &AfterSet) { 163344779Sdim auto InsertPos = MBB->begin(); 164344779Sdim while (InsertPos != MBB->end()) { 165344779Sdim if (AfterSet.count(&*InsertPos)) { 166344779Sdim#ifndef NDEBUG 167344779Sdim // Sanity check 168344779Sdim for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos) 169344779Sdim assert(!BeforeSet.count(&*Pos)); 170344779Sdim#endif 171344779Sdim break; 172344779Sdim } 173344779Sdim ++InsertPos; 174344779Sdim } 175344779Sdim return InsertPos; 176344779Sdim} 177344779Sdim 178344779Sdimvoid WebAssemblyCFGStackify::registerScope(MachineInstr *Begin, 179344779Sdim MachineInstr *End) { 180344779Sdim BeginToEnd[Begin] = End; 181344779Sdim EndToBegin[End] = Begin; 182344779Sdim} 183344779Sdim 184344779Sdimvoid WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin, 185344779Sdim MachineInstr *End, 186344779Sdim MachineBasicBlock *EHPad) { 187344779Sdim registerScope(Begin, End); 188344779Sdim TryToEHPad[Begin] = EHPad; 189344779Sdim EHPadToTry[EHPad] = Begin; 190344779Sdim} 191344779Sdim 192353358Sdimvoid WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) { 193353358Sdim assert(BeginToEnd.count(Begin)); 194353358Sdim MachineInstr *End = BeginToEnd[Begin]; 195353358Sdim assert(EndToBegin.count(End)); 196353358Sdim BeginToEnd.erase(Begin); 197353358Sdim EndToBegin.erase(End); 198353358Sdim MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin); 199353358Sdim if (EHPad) { 200353358Sdim assert(EHPadToTry.count(EHPad)); 201353358Sdim TryToEHPad.erase(Begin); 202353358Sdim EHPadToTry.erase(EHPad); 203353358Sdim } 204344779Sdim} 205344779Sdim 206292915Sdim/// Insert a BLOCK marker for branches to MBB (if needed). 207353358Sdim// TODO Consider a more generalized way of handling block (and also loop and 208353358Sdim// try) signatures when we implement the multi-value proposal later. 209344779Sdimvoid WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) { 210353358Sdim assert(!MBB.isEHPad()); 211344779Sdim MachineFunction &MF = *MBB.getParent(); 212344779Sdim auto &MDT = getAnalysis<MachineDominatorTree>(); 213344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 214344779Sdim const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 215344779Sdim 216292915Sdim // First compute the nearest common dominator of all forward non-fallthrough 217292915Sdim // predecessors so that we minimize the time that the BLOCK is on the stack, 218292915Sdim // which reduces overall stack height. 219292915Sdim MachineBasicBlock *Header = nullptr; 220292915Sdim bool IsBranchedTo = false; 221353358Sdim bool IsBrOnExn = false; 222353358Sdim MachineInstr *BrOnExn = nullptr; 223292915Sdim int MBBNumber = MBB.getNumber(); 224344779Sdim for (MachineBasicBlock *Pred : MBB.predecessors()) { 225292915Sdim if (Pred->getNumber() < MBBNumber) { 226292915Sdim Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 227353358Sdim if (explicitlyBranchesTo(Pred, &MBB)) { 228292915Sdim IsBranchedTo = true; 229353358Sdim if (Pred->getFirstTerminator()->getOpcode() == WebAssembly::BR_ON_EXN) { 230353358Sdim IsBrOnExn = true; 231353358Sdim assert(!BrOnExn && "There should be only one br_on_exn per block"); 232353358Sdim BrOnExn = &*Pred->getFirstTerminator(); 233353358Sdim } 234353358Sdim } 235292915Sdim } 236344779Sdim } 237292915Sdim if (!Header) 238292915Sdim return; 239292915Sdim if (!IsBranchedTo) 240292915Sdim return; 241292915Sdim 242292915Sdim assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors"); 243353358Sdim MachineBasicBlock *LayoutPred = MBB.getPrevNode(); 244292915Sdim 245292915Sdim // If the nearest common dominator is inside a more deeply nested context, 246292915Sdim // walk out to the nearest scope which isn't more deeply nested. 247292915Sdim for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 248292915Sdim if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 249292915Sdim if (ScopeTop->getNumber() > Header->getNumber()) { 250292915Sdim // Skip over an intervening scope. 251353358Sdim I = std::next(ScopeTop->getIterator()); 252292915Sdim } else { 253292915Sdim // We found a scope level at an appropriate depth. 254292915Sdim Header = ScopeTop; 255292915Sdim break; 256292915Sdim } 257292915Sdim } 258292915Sdim } 259292915Sdim 260292915Sdim // Decide where in Header to put the BLOCK. 261344779Sdim 262344779Sdim // Instructions that should go before the BLOCK. 263344779Sdim SmallPtrSet<const MachineInstr *, 4> BeforeSet; 264344779Sdim // Instructions that should go after the BLOCK. 265344779Sdim SmallPtrSet<const MachineInstr *, 4> AfterSet; 266344779Sdim for (const auto &MI : *Header) { 267353358Sdim // If there is a previously placed LOOP marker and the bottom block of the 268353358Sdim // loop is above MBB, it should be after the BLOCK, because the loop is 269353358Sdim // nested in this BLOCK. Otherwise it should be before the BLOCK. 270353358Sdim if (MI.getOpcode() == WebAssembly::LOOP) { 271353358Sdim auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); 272353358Sdim if (MBB.getNumber() > LoopBottom->getNumber()) 273344779Sdim AfterSet.insert(&MI); 274344779Sdim#ifndef NDEBUG 275344779Sdim else 276344779Sdim BeforeSet.insert(&MI); 277344779Sdim#endif 278344779Sdim } 279344779Sdim 280353358Sdim // All previously inserted BLOCK/TRY markers should be after the BLOCK 281353358Sdim // because they are all nested blocks. 282353358Sdim if (MI.getOpcode() == WebAssembly::BLOCK || 283353358Sdim MI.getOpcode() == WebAssembly::TRY) 284344779Sdim AfterSet.insert(&MI); 285344779Sdim 286344779Sdim#ifndef NDEBUG 287344779Sdim // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK. 288344779Sdim if (MI.getOpcode() == WebAssembly::END_BLOCK || 289344779Sdim MI.getOpcode() == WebAssembly::END_LOOP || 290344779Sdim MI.getOpcode() == WebAssembly::END_TRY) 291344779Sdim BeforeSet.insert(&MI); 292344779Sdim#endif 293344779Sdim 294344779Sdim // Terminators should go after the BLOCK. 295344779Sdim if (MI.isTerminator()) 296344779Sdim AfterSet.insert(&MI); 297292915Sdim } 298292915Sdim 299344779Sdim // Local expression tree should go after the BLOCK. 300344779Sdim for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; 301344779Sdim --I) { 302344779Sdim if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 303344779Sdim continue; 304344779Sdim if (WebAssembly::isChild(*std::prev(I), MFI)) 305344779Sdim AfterSet.insert(&*std::prev(I)); 306344779Sdim else 307344779Sdim break; 308344779Sdim } 309344779Sdim 310292915Sdim // Add the BLOCK. 311353358Sdim 312353358Sdim // 'br_on_exn' extracts exnref object and pushes variable number of values 313353358Sdim // depending on its tag. For C++ exception, its a single i32 value, and the 314353358Sdim // generated code will be in the form of: 315353358Sdim // block i32 316353358Sdim // br_on_exn 0, $__cpp_exception 317353358Sdim // rethrow 318353358Sdim // end_block 319360784Sdim WebAssembly::BlockType ReturnType = WebAssembly::BlockType::Void; 320353358Sdim if (IsBrOnExn) { 321353358Sdim const char *TagName = BrOnExn->getOperand(1).getSymbolName(); 322353358Sdim if (std::strcmp(TagName, "__cpp_exception") != 0) 323353358Sdim llvm_unreachable("Only C++ exception is supported"); 324360784Sdim ReturnType = WebAssembly::BlockType::I32; 325353358Sdim } 326353358Sdim 327353358Sdim auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); 328341825Sdim MachineInstr *Begin = 329341825Sdim BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 330341825Sdim TII.get(WebAssembly::BLOCK)) 331353358Sdim .addImm(int64_t(ReturnType)); 332292915Sdim 333344779Sdim // Decide where in Header to put the END_BLOCK. 334344779Sdim BeforeSet.clear(); 335344779Sdim AfterSet.clear(); 336344779Sdim for (auto &MI : MBB) { 337344779Sdim#ifndef NDEBUG 338344779Sdim // END_BLOCK should precede existing LOOP and TRY markers. 339344779Sdim if (MI.getOpcode() == WebAssembly::LOOP || 340344779Sdim MI.getOpcode() == WebAssembly::TRY) 341344779Sdim AfterSet.insert(&MI); 342344779Sdim#endif 343344779Sdim 344344779Sdim // If there is a previously placed END_LOOP marker and the header of the 345344779Sdim // loop is above this block's header, the END_LOOP should be placed after 346344779Sdim // the BLOCK, because the loop contains this block. Otherwise the END_LOOP 347344779Sdim // should be placed before the BLOCK. The same for END_TRY. 348344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP || 349344779Sdim MI.getOpcode() == WebAssembly::END_TRY) { 350344779Sdim if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) 351344779Sdim BeforeSet.insert(&MI); 352344779Sdim#ifndef NDEBUG 353344779Sdim else 354344779Sdim AfterSet.insert(&MI); 355344779Sdim#endif 356344779Sdim } 357344779Sdim } 358344779Sdim 359294024Sdim // Mark the end of the block. 360353358Sdim InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); 361341825Sdim MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos), 362314564Sdim TII.get(WebAssembly::END_BLOCK)); 363344779Sdim registerScope(Begin, End); 364294024Sdim 365292915Sdim // Track the farthest-spanning scope that ends at this point. 366292915Sdim int Number = MBB.getNumber(); 367292915Sdim if (!ScopeTops[Number] || 368292915Sdim ScopeTops[Number]->getNumber() > Header->getNumber()) 369292915Sdim ScopeTops[Number] = Header; 370292915Sdim} 371292915Sdim 372292915Sdim/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header). 373344779Sdimvoid WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { 374344779Sdim MachineFunction &MF = *MBB.getParent(); 375344779Sdim const auto &MLI = getAnalysis<MachineLoopInfo>(); 376344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 377344779Sdim 378292915Sdim MachineLoop *Loop = MLI.getLoopFor(&MBB); 379292915Sdim if (!Loop || Loop->getHeader() != &MBB) 380292915Sdim return; 381292915Sdim 382292915Sdim // The operand of a LOOP is the first block after the loop. If the loop is the 383292915Sdim // bottom of the function, insert a dummy block at the end. 384341825Sdim MachineBasicBlock *Bottom = WebAssembly::getBottom(Loop); 385353358Sdim auto Iter = std::next(Bottom->getIterator()); 386292915Sdim if (Iter == MF.end()) { 387353358Sdim getAppendixBlock(MF); 388353358Sdim Iter = std::next(Bottom->getIterator()); 389292915Sdim } 390292915Sdim MachineBasicBlock *AfterLoop = &*Iter; 391292915Sdim 392344779Sdim // Decide where in Header to put the LOOP. 393344779Sdim SmallPtrSet<const MachineInstr *, 4> BeforeSet; 394344779Sdim SmallPtrSet<const MachineInstr *, 4> AfterSet; 395344779Sdim for (const auto &MI : MBB) { 396344779Sdim // LOOP marker should be after any existing loop that ends here. Otherwise 397344779Sdim // we assume the instruction belongs to the loop. 398344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP) 399344779Sdim BeforeSet.insert(&MI); 400344779Sdim#ifndef NDEBUG 401344779Sdim else 402344779Sdim AfterSet.insert(&MI); 403344779Sdim#endif 404344779Sdim } 405344779Sdim 406344779Sdim // Mark the beginning of the loop. 407353358Sdim auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); 408341825Sdim MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos), 409314564Sdim TII.get(WebAssembly::LOOP)) 410360784Sdim .addImm(int64_t(WebAssembly::BlockType::Void)); 411292915Sdim 412344779Sdim // Decide where in Header to put the END_LOOP. 413344779Sdim BeforeSet.clear(); 414344779Sdim AfterSet.clear(); 415344779Sdim#ifndef NDEBUG 416344779Sdim for (const auto &MI : MBB) 417344779Sdim // Existing END_LOOP markers belong to parent loops of this loop 418344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP) 419344779Sdim AfterSet.insert(&MI); 420344779Sdim#endif 421344779Sdim 422344779Sdim // Mark the end of the loop (using arbitrary debug location that branched to 423344779Sdim // the loop end as its location). 424353358Sdim InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet); 425353358Sdim DebugLoc EndDL = AfterLoop->pred_empty() 426353358Sdim ? DebugLoc() 427353358Sdim : (*AfterLoop->pred_rbegin())->findBranchDebugLoc(); 428344779Sdim MachineInstr *End = 429344779Sdim BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP)); 430344779Sdim registerScope(Begin, End); 431294024Sdim 432292915Sdim assert((!ScopeTops[AfterLoop->getNumber()] || 433292915Sdim ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) && 434309124Sdim "With block sorting the outermost loop for a block should be first."); 435292915Sdim if (!ScopeTops[AfterLoop->getNumber()]) 436292915Sdim ScopeTops[AfterLoop->getNumber()] = &MBB; 437292915Sdim} 438292915Sdim 439344779Sdimvoid WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) { 440353358Sdim assert(MBB.isEHPad()); 441344779Sdim MachineFunction &MF = *MBB.getParent(); 442344779Sdim auto &MDT = getAnalysis<MachineDominatorTree>(); 443344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 444344779Sdim const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); 445344779Sdim const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 446344779Sdim 447344779Sdim // Compute the nearest common dominator of all unwind predecessors 448344779Sdim MachineBasicBlock *Header = nullptr; 449344779Sdim int MBBNumber = MBB.getNumber(); 450344779Sdim for (auto *Pred : MBB.predecessors()) { 451344779Sdim if (Pred->getNumber() < MBBNumber) { 452344779Sdim Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 453353358Sdim assert(!explicitlyBranchesTo(Pred, &MBB) && 454344779Sdim "Explicit branch to an EH pad!"); 455344779Sdim } 456344779Sdim } 457344779Sdim if (!Header) 458344779Sdim return; 459344779Sdim 460344779Sdim // If this try is at the bottom of the function, insert a dummy block at the 461344779Sdim // end. 462344779Sdim WebAssemblyException *WE = WEI.getExceptionFor(&MBB); 463344779Sdim assert(WE); 464344779Sdim MachineBasicBlock *Bottom = WebAssembly::getBottom(WE); 465344779Sdim 466353358Sdim auto Iter = std::next(Bottom->getIterator()); 467344779Sdim if (Iter == MF.end()) { 468353358Sdim getAppendixBlock(MF); 469353358Sdim Iter = std::next(Bottom->getIterator()); 470344779Sdim } 471353358Sdim MachineBasicBlock *Cont = &*Iter; 472344779Sdim 473353358Sdim assert(Cont != &MF.front()); 474353358Sdim MachineBasicBlock *LayoutPred = Cont->getPrevNode(); 475344779Sdim 476344779Sdim // If the nearest common dominator is inside a more deeply nested context, 477344779Sdim // walk out to the nearest scope which isn't more deeply nested. 478344779Sdim for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 479344779Sdim if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 480344779Sdim if (ScopeTop->getNumber() > Header->getNumber()) { 481344779Sdim // Skip over an intervening scope. 482353358Sdim I = std::next(ScopeTop->getIterator()); 483344779Sdim } else { 484344779Sdim // We found a scope level at an appropriate depth. 485344779Sdim Header = ScopeTop; 486344779Sdim break; 487344779Sdim } 488344779Sdim } 489344779Sdim } 490344779Sdim 491344779Sdim // Decide where in Header to put the TRY. 492344779Sdim 493353358Sdim // Instructions that should go before the TRY. 494344779Sdim SmallPtrSet<const MachineInstr *, 4> BeforeSet; 495353358Sdim // Instructions that should go after the TRY. 496344779Sdim SmallPtrSet<const MachineInstr *, 4> AfterSet; 497344779Sdim for (const auto &MI : *Header) { 498353358Sdim // If there is a previously placed LOOP marker and the bottom block of the 499353358Sdim // loop is above MBB, it should be after the TRY, because the loop is nested 500353358Sdim // in this TRY. Otherwise it should be before the TRY. 501344779Sdim if (MI.getOpcode() == WebAssembly::LOOP) { 502353358Sdim auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); 503353358Sdim if (MBB.getNumber() > LoopBottom->getNumber()) 504344779Sdim AfterSet.insert(&MI); 505344779Sdim#ifndef NDEBUG 506344779Sdim else 507344779Sdim BeforeSet.insert(&MI); 508344779Sdim#endif 509344779Sdim } 510344779Sdim 511353358Sdim // All previously inserted BLOCK/TRY markers should be after the TRY because 512353358Sdim // they are all nested trys. 513353358Sdim if (MI.getOpcode() == WebAssembly::BLOCK || 514353358Sdim MI.getOpcode() == WebAssembly::TRY) 515344779Sdim AfterSet.insert(&MI); 516344779Sdim 517344779Sdim#ifndef NDEBUG 518353358Sdim // All END_(BLOCK/LOOP/TRY) markers should be before the TRY. 519353358Sdim if (MI.getOpcode() == WebAssembly::END_BLOCK || 520353358Sdim MI.getOpcode() == WebAssembly::END_LOOP || 521344779Sdim MI.getOpcode() == WebAssembly::END_TRY) 522344779Sdim BeforeSet.insert(&MI); 523344779Sdim#endif 524344779Sdim 525344779Sdim // Terminators should go after the TRY. 526344779Sdim if (MI.isTerminator()) 527344779Sdim AfterSet.insert(&MI); 528344779Sdim } 529344779Sdim 530344779Sdim // If Header unwinds to MBB (= Header contains 'invoke'), the try block should 531344779Sdim // contain the call within it. So the call should go after the TRY. The 532344779Sdim // exception is when the header's terminator is a rethrow instruction, in 533344779Sdim // which case that instruction, not a call instruction before it, is gonna 534344779Sdim // throw. 535360784Sdim MachineInstr *ThrowingCall = nullptr; 536344779Sdim if (MBB.isPredecessor(Header)) { 537344779Sdim auto TermPos = Header->getFirstTerminator(); 538353358Sdim if (TermPos == Header->end() || 539353358Sdim TermPos->getOpcode() != WebAssembly::RETHROW) { 540360784Sdim for (auto &MI : reverse(*Header)) { 541344779Sdim if (MI.isCall()) { 542344779Sdim AfterSet.insert(&MI); 543360784Sdim ThrowingCall = &MI; 544353358Sdim // Possibly throwing calls are usually wrapped by EH_LABEL 545353358Sdim // instructions. We don't want to split them and the call. 546353358Sdim if (MI.getIterator() != Header->begin() && 547360784Sdim std::prev(MI.getIterator())->isEHLabel()) { 548353358Sdim AfterSet.insert(&*std::prev(MI.getIterator())); 549360784Sdim ThrowingCall = &*std::prev(MI.getIterator()); 550360784Sdim } 551344779Sdim break; 552344779Sdim } 553344779Sdim } 554344779Sdim } 555344779Sdim } 556344779Sdim 557360784Sdim // Local expression tree should go after the TRY. 558360784Sdim // For BLOCK placement, we start the search from the previous instruction of a 559360784Sdim // BB's terminator, but in TRY's case, we should start from the previous 560360784Sdim // instruction of a call that can throw, or a EH_LABEL that precedes the call, 561360784Sdim // because the return values of the call's previous instructions can be 562360784Sdim // stackified and consumed by the throwing call. 563360784Sdim auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall) 564360784Sdim : Header->getFirstTerminator(); 565360784Sdim for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) { 566360784Sdim if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 567360784Sdim continue; 568360784Sdim if (WebAssembly::isChild(*std::prev(I), MFI)) 569360784Sdim AfterSet.insert(&*std::prev(I)); 570360784Sdim else 571360784Sdim break; 572360784Sdim } 573360784Sdim 574344779Sdim // Add the TRY. 575353358Sdim auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); 576344779Sdim MachineInstr *Begin = 577344779Sdim BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 578344779Sdim TII.get(WebAssembly::TRY)) 579360784Sdim .addImm(int64_t(WebAssembly::BlockType::Void)); 580344779Sdim 581344779Sdim // Decide where in Header to put the END_TRY. 582344779Sdim BeforeSet.clear(); 583344779Sdim AfterSet.clear(); 584353358Sdim for (const auto &MI : *Cont) { 585344779Sdim#ifndef NDEBUG 586353358Sdim // END_TRY should precede existing LOOP and BLOCK markers. 587353358Sdim if (MI.getOpcode() == WebAssembly::LOOP || 588353358Sdim MI.getOpcode() == WebAssembly::BLOCK) 589344779Sdim AfterSet.insert(&MI); 590344779Sdim 591344779Sdim // All END_TRY markers placed earlier belong to exceptions that contains 592344779Sdim // this one. 593344779Sdim if (MI.getOpcode() == WebAssembly::END_TRY) 594344779Sdim AfterSet.insert(&MI); 595344779Sdim#endif 596344779Sdim 597344779Sdim // If there is a previously placed END_LOOP marker and its header is after 598344779Sdim // where TRY marker is, this loop is contained within the 'catch' part, so 599344779Sdim // the END_TRY marker should go after that. Otherwise, the whole try-catch 600344779Sdim // is contained within this loop, so the END_TRY should go before that. 601344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP) { 602353358Sdim // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they 603353358Sdim // are in the same BB, LOOP is always before TRY. 604353358Sdim if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber()) 605344779Sdim BeforeSet.insert(&MI); 606344779Sdim#ifndef NDEBUG 607344779Sdim else 608344779Sdim AfterSet.insert(&MI); 609344779Sdim#endif 610344779Sdim } 611353358Sdim 612353358Sdim // It is not possible for an END_BLOCK to be already in this block. 613344779Sdim } 614344779Sdim 615344779Sdim // Mark the end of the TRY. 616353358Sdim InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet); 617344779Sdim MachineInstr *End = 618353358Sdim BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(), 619344779Sdim TII.get(WebAssembly::END_TRY)); 620344779Sdim registerTryScope(Begin, End, &MBB); 621344779Sdim 622353358Sdim // Track the farthest-spanning scope that ends at this point. We create two 623353358Sdim // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB 624353358Sdim // with 'try'). We need to create 'catch' -> 'try' mapping here too because 625353358Sdim // markers should not span across 'catch'. For example, this should not 626353358Sdim // happen: 627353358Sdim // 628353358Sdim // try 629353358Sdim // block --| (X) 630353358Sdim // catch | 631353358Sdim // end_block --| 632353358Sdim // end_try 633353358Sdim for (int Number : {Cont->getNumber(), MBB.getNumber()}) { 634353358Sdim if (!ScopeTops[Number] || 635353358Sdim ScopeTops[Number]->getNumber() > Header->getNumber()) 636353358Sdim ScopeTops[Number] = Header; 637353358Sdim } 638344779Sdim} 639344779Sdim 640353358Sdimvoid WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) { 641353358Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 642353358Sdim 643353358Sdim // When there is an unconditional branch right before a catch instruction and 644353358Sdim // it branches to the end of end_try marker, we don't need the branch, because 645353358Sdim // it there is no exception, the control flow transfers to that point anyway. 646353358Sdim // bb0: 647353358Sdim // try 648353358Sdim // ... 649353358Sdim // br bb2 <- Not necessary 650353358Sdim // bb1: 651353358Sdim // catch 652353358Sdim // ... 653353358Sdim // bb2: 654353358Sdim // end 655353358Sdim for (auto &MBB : MF) { 656353358Sdim if (!MBB.isEHPad()) 657353358Sdim continue; 658353358Sdim 659353358Sdim MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 660353358Sdim SmallVector<MachineOperand, 4> Cond; 661353358Sdim MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode(); 662353358Sdim MachineBasicBlock *Cont = BeginToEnd[EHPadToTry[&MBB]]->getParent(); 663353358Sdim bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond); 664353358Sdim if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) || 665353358Sdim (!Cond.empty() && FBB && FBB == Cont))) 666353358Sdim TII.removeBranch(*EHPadLayoutPred); 667353358Sdim } 668353358Sdim 669353358Sdim // When there are block / end_block markers that overlap with try / end_try 670353358Sdim // markers, and the block and try markers' return types are the same, the 671353358Sdim // block /end_block markers are not necessary, because try / end_try markers 672353358Sdim // also can serve as boundaries for branches. 673353358Sdim // block <- Not necessary 674353358Sdim // try 675353358Sdim // ... 676353358Sdim // catch 677353358Sdim // ... 678353358Sdim // end 679353358Sdim // end <- Not necessary 680353358Sdim SmallVector<MachineInstr *, 32> ToDelete; 681353358Sdim for (auto &MBB : MF) { 682353358Sdim for (auto &MI : MBB) { 683353358Sdim if (MI.getOpcode() != WebAssembly::TRY) 684353358Sdim continue; 685353358Sdim 686353358Sdim MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try]; 687353358Sdim MachineBasicBlock *TryBB = Try->getParent(); 688353358Sdim MachineBasicBlock *Cont = EndTry->getParent(); 689353358Sdim int64_t RetType = Try->getOperand(0).getImm(); 690353358Sdim for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator()); 691353358Sdim B != TryBB->begin() && E != Cont->end() && 692353358Sdim std::prev(B)->getOpcode() == WebAssembly::BLOCK && 693353358Sdim E->getOpcode() == WebAssembly::END_BLOCK && 694353358Sdim std::prev(B)->getOperand(0).getImm() == RetType; 695353358Sdim --B, ++E) { 696353358Sdim ToDelete.push_back(&*std::prev(B)); 697353358Sdim ToDelete.push_back(&*E); 698353358Sdim } 699353358Sdim } 700353358Sdim } 701353358Sdim for (auto *MI : ToDelete) { 702353358Sdim if (MI->getOpcode() == WebAssembly::BLOCK) 703353358Sdim unregisterScope(MI); 704353358Sdim MI->eraseFromParent(); 705353358Sdim } 706353358Sdim} 707353358Sdim 708360784Sdim// When MBB is split into MBB and Split, we should unstackify defs in MBB that 709360784Sdim// have their uses in Split. 710360784Sdimstatic void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, 711360784Sdim MachineBasicBlock &Split, 712360784Sdim WebAssemblyFunctionInfo &MFI, 713360784Sdim MachineRegisterInfo &MRI) { 714360784Sdim for (auto &MI : Split) { 715360784Sdim for (auto &MO : MI.explicit_uses()) { 716360784Sdim if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg())) 717360784Sdim continue; 718360784Sdim if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg())) 719360784Sdim if (Def->getParent() == &MBB) 720360784Sdim MFI.unstackifyVReg(MO.getReg()); 721360784Sdim } 722360784Sdim } 723360784Sdim} 724360784Sdim 725353358Sdimbool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) { 726353358Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 727360784Sdim auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 728353358Sdim MachineRegisterInfo &MRI = MF.getRegInfo(); 729353358Sdim 730353358Sdim // Linearizing the control flow by placing TRY / END_TRY markers can create 731353358Sdim // mismatches in unwind destinations. There are two kinds of mismatches we 732353358Sdim // try to solve here. 733353358Sdim 734353358Sdim // 1. When an instruction may throw, but the EH pad it will unwind to can be 735353358Sdim // different from the original CFG. 736353358Sdim // 737353358Sdim // Example: we have the following CFG: 738353358Sdim // bb0: 739353358Sdim // call @foo (if it throws, unwind to bb2) 740353358Sdim // bb1: 741353358Sdim // call @bar (if it throws, unwind to bb3) 742353358Sdim // bb2 (ehpad): 743353358Sdim // catch 744353358Sdim // ... 745353358Sdim // bb3 (ehpad) 746353358Sdim // catch 747353358Sdim // handler body 748353358Sdim // 749353358Sdim // And the CFG is sorted in this order. Then after placing TRY markers, it 750353358Sdim // will look like: (BB markers are omitted) 751353358Sdim // try $label1 752353358Sdim // try 753353358Sdim // call @foo 754353358Sdim // call @bar (if it throws, unwind to bb3) 755353358Sdim // catch <- ehpad (bb2) 756353358Sdim // ... 757353358Sdim // end_try 758353358Sdim // catch <- ehpad (bb3) 759353358Sdim // handler body 760353358Sdim // end_try 761353358Sdim // 762353358Sdim // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it 763353358Sdim // is supposed to end up. We solve this problem by 764353358Sdim // a. Split the target unwind EH pad (here bb3) so that the handler body is 765353358Sdim // right after 'end_try', which means we extract the handler body out of 766353358Sdim // the catch block. We do this because this handler body should be 767353358Sdim // somewhere branch-eable from the inner scope. 768353358Sdim // b. Wrap the call that has an incorrect unwind destination ('call @bar' 769353358Sdim // here) with a nested try/catch/end_try scope, and within the new catch 770353358Sdim // block, branches to the handler body. 771353358Sdim // c. Place a branch after the newly inserted nested end_try so it can bypass 772353358Sdim // the handler body, which is now outside of a catch block. 773353358Sdim // 774353358Sdim // The result will like as follows. (new: a) means this instruction is newly 775353358Sdim // created in the process of doing 'a' above. 776353358Sdim // 777353358Sdim // block $label0 (new: placeBlockMarker) 778353358Sdim // try $label1 779353358Sdim // try 780353358Sdim // call @foo 781353358Sdim // try (new: b) 782353358Sdim // call @bar 783353358Sdim // catch (new: b) 784353358Sdim // local.set n / drop (new: b) 785353358Sdim // br $label1 (new: b) 786353358Sdim // end_try (new: b) 787353358Sdim // catch <- ehpad (bb2) 788353358Sdim // end_try 789353358Sdim // br $label0 (new: c) 790353358Sdim // catch <- ehpad (bb3) 791353358Sdim // end_try (hoisted: a) 792353358Sdim // handler body 793353358Sdim // end_block (new: placeBlockMarker) 794353358Sdim // 795353358Sdim // Note that the new wrapping block/end_block will be generated later in 796353358Sdim // placeBlockMarker. 797353358Sdim // 798353358Sdim // TODO Currently local.set and local.gets are generated to move exnref value 799353358Sdim // created by catches. That's because we don't support yielding values from a 800353358Sdim // block in LLVM machine IR yet, even though it is supported by wasm. Delete 801353358Sdim // unnecessary local.get/local.sets once yielding values from a block is 802353358Sdim // supported. The full EH spec requires multi-value support to do this, but 803353358Sdim // for C++ we don't yet need it because we only throw a single i32. 804353358Sdim // 805353358Sdim // --- 806353358Sdim // 2. The same as 1, but in this case an instruction unwinds to a caller 807353358Sdim // function and not another EH pad. 808353358Sdim // 809353358Sdim // Example: we have the following CFG: 810353358Sdim // bb0: 811353358Sdim // call @foo (if it throws, unwind to bb2) 812353358Sdim // bb1: 813353358Sdim // call @bar (if it throws, unwind to caller) 814353358Sdim // bb2 (ehpad): 815353358Sdim // catch 816353358Sdim // ... 817353358Sdim // 818353358Sdim // And the CFG is sorted in this order. Then after placing TRY markers, it 819353358Sdim // will look like: 820353358Sdim // try 821353358Sdim // call @foo 822353358Sdim // call @bar (if it throws, unwind to caller) 823353358Sdim // catch <- ehpad (bb2) 824353358Sdim // ... 825353358Sdim // end_try 826353358Sdim // 827353358Sdim // Now if bar() throws, it is going to end up ip in bb2, when it is supposed 828353358Sdim // throw up to the caller. 829353358Sdim // We solve this problem by 830353358Sdim // a. Create a new 'appendix' BB at the end of the function and put a single 831353358Sdim // 'rethrow' instruction (+ local.get) in there. 832353358Sdim // b. Wrap the call that has an incorrect unwind destination ('call @bar' 833353358Sdim // here) with a nested try/catch/end_try scope, and within the new catch 834353358Sdim // block, branches to the new appendix block. 835353358Sdim // 836353358Sdim // block $label0 (new: placeBlockMarker) 837353358Sdim // try 838353358Sdim // call @foo 839353358Sdim // try (new: b) 840353358Sdim // call @bar 841353358Sdim // catch (new: b) 842353358Sdim // local.set n (new: b) 843353358Sdim // br $label0 (new: b) 844353358Sdim // end_try (new: b) 845353358Sdim // catch <- ehpad (bb2) 846353358Sdim // ... 847353358Sdim // end_try 848353358Sdim // ... 849353358Sdim // end_block (new: placeBlockMarker) 850353358Sdim // local.get n (new: a) <- appendix block 851353358Sdim // rethrow (new: a) 852353358Sdim // 853353358Sdim // In case there are multiple calls in a BB that may throw to the caller, they 854353358Sdim // can be wrapped together in one nested try scope. (In 1, this couldn't 855353358Sdim // happen, because may-throwing instruction there had an unwind destination, 856353358Sdim // i.e., it was an invoke before, and there could be only one invoke within a 857353358Sdim // BB.) 858353358Sdim 859353358Sdim SmallVector<const MachineBasicBlock *, 8> EHPadStack; 860353358Sdim // Range of intructions to be wrapped in a new nested try/catch 861353358Sdim using TryRange = std::pair<MachineInstr *, MachineInstr *>; 862360784Sdim // In original CFG, <unwind destination BB, a vector of try ranges> 863353358Sdim DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges; 864353358Sdim // In new CFG, <destination to branch to, a vector of try ranges> 865353358Sdim DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> BrDestToTryRanges; 866353358Sdim // In new CFG, <destination to branch to, register containing exnref> 867353358Sdim DenseMap<MachineBasicBlock *, unsigned> BrDestToExnReg; 868353358Sdim 869353358Sdim // Gather possibly throwing calls (i.e., previously invokes) whose current 870353358Sdim // unwind destination is not the same as the original CFG. 871353358Sdim for (auto &MBB : reverse(MF)) { 872353358Sdim bool SeenThrowableInstInBB = false; 873353358Sdim for (auto &MI : reverse(MBB)) { 874353358Sdim if (MI.getOpcode() == WebAssembly::TRY) 875353358Sdim EHPadStack.pop_back(); 876353358Sdim else if (MI.getOpcode() == WebAssembly::CATCH) 877353358Sdim EHPadStack.push_back(MI.getParent()); 878353358Sdim 879353358Sdim // In this loop we only gather calls that have an EH pad to unwind. So 880353358Sdim // there will be at most 1 such call (= invoke) in a BB, so after we've 881353358Sdim // seen one, we can skip the rest of BB. Also if MBB has no EH pad 882353358Sdim // successor or MI does not throw, this is not an invoke. 883353358Sdim if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() || 884353358Sdim !WebAssembly::mayThrow(MI)) 885353358Sdim continue; 886353358Sdim SeenThrowableInstInBB = true; 887353358Sdim 888353358Sdim // If the EH pad on the stack top is where this instruction should unwind 889353358Sdim // next, we're good. 890353358Sdim MachineBasicBlock *UnwindDest = nullptr; 891353358Sdim for (auto *Succ : MBB.successors()) { 892353358Sdim if (Succ->isEHPad()) { 893353358Sdim UnwindDest = Succ; 894353358Sdim break; 895353358Sdim } 896353358Sdim } 897353358Sdim if (EHPadStack.back() == UnwindDest) 898353358Sdim continue; 899353358Sdim 900353358Sdim // If not, record the range. 901353358Sdim UnwindDestToTryRanges[UnwindDest].push_back(TryRange(&MI, &MI)); 902353358Sdim } 903353358Sdim } 904353358Sdim 905353358Sdim assert(EHPadStack.empty()); 906353358Sdim 907353358Sdim // Gather possibly throwing calls that are supposed to unwind up to the caller 908353358Sdim // if they throw, but currently unwind to an incorrect destination. Unlike the 909353358Sdim // loop above, there can be multiple calls within a BB that unwind to the 910353358Sdim // caller, which we should group together in a range. 911353358Sdim bool NeedAppendixBlock = false; 912353358Sdim for (auto &MBB : reverse(MF)) { 913353358Sdim MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive 914353358Sdim for (auto &MI : reverse(MBB)) { 915353358Sdim if (MI.getOpcode() == WebAssembly::TRY) 916353358Sdim EHPadStack.pop_back(); 917353358Sdim else if (MI.getOpcode() == WebAssembly::CATCH) 918353358Sdim EHPadStack.push_back(MI.getParent()); 919353358Sdim 920353358Sdim // If MBB has an EH pad successor, this inst does not unwind to caller. 921353358Sdim if (MBB.hasEHPadSuccessor()) 922353358Sdim continue; 923353358Sdim 924353358Sdim // We wrap up the current range when we see a marker even if we haven't 925353358Sdim // finished a BB. 926353358Sdim if (RangeEnd && WebAssembly::isMarker(MI.getOpcode())) { 927353358Sdim NeedAppendixBlock = true; 928353358Sdim // Record the range. nullptr here means the unwind destination is the 929353358Sdim // caller. 930353358Sdim UnwindDestToTryRanges[nullptr].push_back( 931353358Sdim TryRange(RangeBegin, RangeEnd)); 932353358Sdim RangeBegin = RangeEnd = nullptr; // Reset range pointers 933353358Sdim } 934353358Sdim 935353358Sdim // If EHPadStack is empty, that means it is correctly unwind to caller if 936353358Sdim // it throws, so we're good. If MI does not throw, we're good too. 937353358Sdim if (EHPadStack.empty() || !WebAssembly::mayThrow(MI)) 938353358Sdim continue; 939353358Sdim 940353358Sdim // We found an instruction that unwinds to the caller but currently has an 941353358Sdim // incorrect unwind destination. Create a new range or increment the 942353358Sdim // currently existing range. 943353358Sdim if (!RangeEnd) 944353358Sdim RangeBegin = RangeEnd = &MI; 945353358Sdim else 946353358Sdim RangeBegin = &MI; 947353358Sdim } 948353358Sdim 949353358Sdim if (RangeEnd) { 950353358Sdim NeedAppendixBlock = true; 951353358Sdim // Record the range. nullptr here means the unwind destination is the 952353358Sdim // caller. 953353358Sdim UnwindDestToTryRanges[nullptr].push_back(TryRange(RangeBegin, RangeEnd)); 954353358Sdim RangeBegin = RangeEnd = nullptr; // Reset range pointers 955353358Sdim } 956353358Sdim } 957353358Sdim 958353358Sdim assert(EHPadStack.empty()); 959353358Sdim // We don't have any unwind destination mismatches to resolve. 960353358Sdim if (UnwindDestToTryRanges.empty()) 961353358Sdim return false; 962353358Sdim 963353358Sdim // If we found instructions that should unwind to the caller but currently 964353358Sdim // have incorrect unwind destination, we create an appendix block at the end 965353358Sdim // of the function with a local.get and a rethrow instruction. 966353358Sdim if (NeedAppendixBlock) { 967353358Sdim auto *AppendixBB = getAppendixBlock(MF); 968360784Sdim Register ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass); 969353358Sdim BuildMI(AppendixBB, DebugLoc(), TII.get(WebAssembly::RETHROW)) 970353358Sdim .addReg(ExnReg); 971353358Sdim // These instruction ranges should branch to this appendix BB. 972353358Sdim for (auto Range : UnwindDestToTryRanges[nullptr]) 973353358Sdim BrDestToTryRanges[AppendixBB].push_back(Range); 974353358Sdim BrDestToExnReg[AppendixBB] = ExnReg; 975353358Sdim } 976353358Sdim 977353358Sdim // We loop through unwind destination EH pads that are targeted from some 978353358Sdim // inner scopes. Because these EH pads are destination of more than one scope 979353358Sdim // now, we split them so that the handler body is after 'end_try'. 980353358Sdim // - Before 981353358Sdim // ehpad: 982353358Sdim // catch 983353358Sdim // local.set n / drop 984353358Sdim // handler body 985353358Sdim // ... 986353358Sdim // cont: 987353358Sdim // end_try 988353358Sdim // 989353358Sdim // - After 990353358Sdim // ehpad: 991353358Sdim // catch 992353358Sdim // local.set n / drop 993353358Sdim // brdest: (new) 994353358Sdim // end_try (hoisted from 'cont' BB) 995353358Sdim // handler body (taken from 'ehpad') 996353358Sdim // ... 997353358Sdim // cont: 998353358Sdim for (auto &P : UnwindDestToTryRanges) { 999360784Sdim NumUnwindMismatches += P.second.size(); 1000353358Sdim 1001353358Sdim // This means the destination is the appendix BB, which was separately 1002353358Sdim // handled above. 1003353358Sdim if (!P.first) 1004353358Sdim continue; 1005353358Sdim 1006353358Sdim MachineBasicBlock *EHPad = P.first; 1007353358Sdim 1008353358Sdim // Find 'catch' and 'local.set' or 'drop' instruction that follows the 1009353358Sdim // 'catch'. If -wasm-disable-explicit-locals is not set, 'catch' should be 1010353358Sdim // always followed by either 'local.set' or a 'drop', because 'br_on_exn' is 1011353358Sdim // generated after 'catch' in LateEHPrepare and we don't support blocks 1012353358Sdim // taking values yet. 1013353358Sdim MachineInstr *Catch = nullptr; 1014353358Sdim unsigned ExnReg = 0; 1015353358Sdim for (auto &MI : *EHPad) { 1016353358Sdim switch (MI.getOpcode()) { 1017353358Sdim case WebAssembly::CATCH: 1018353358Sdim Catch = &MI; 1019353358Sdim ExnReg = Catch->getOperand(0).getReg(); 1020353358Sdim break; 1021353358Sdim } 1022353358Sdim } 1023353358Sdim assert(Catch && "EH pad does not have a catch"); 1024353358Sdim assert(ExnReg != 0 && "Invalid register"); 1025353358Sdim 1026353358Sdim auto SplitPos = std::next(Catch->getIterator()); 1027353358Sdim 1028353358Sdim // Create a new BB that's gonna be the destination for branches from the 1029353358Sdim // inner mismatched scope. 1030353358Sdim MachineInstr *BeginTry = EHPadToTry[EHPad]; 1031353358Sdim MachineInstr *EndTry = BeginToEnd[BeginTry]; 1032353358Sdim MachineBasicBlock *Cont = EndTry->getParent(); 1033353358Sdim auto *BrDest = MF.CreateMachineBasicBlock(); 1034353358Sdim MF.insert(std::next(EHPad->getIterator()), BrDest); 1035353358Sdim // Hoist up the existing 'end_try'. 1036353358Sdim BrDest->insert(BrDest->end(), EndTry->removeFromParent()); 1037353358Sdim // Take out the handler body from EH pad to the new branch destination BB. 1038353358Sdim BrDest->splice(BrDest->end(), EHPad, SplitPos, EHPad->end()); 1039360784Sdim unstackifyVRegsUsedInSplitBB(*EHPad, *BrDest, MFI, MRI); 1040353358Sdim // Fix predecessor-successor relationship. 1041353358Sdim BrDest->transferSuccessors(EHPad); 1042353358Sdim EHPad->addSuccessor(BrDest); 1043353358Sdim 1044353358Sdim // All try ranges that were supposed to unwind to this EH pad now have to 1045353358Sdim // branch to this new branch dest BB. 1046353358Sdim for (auto Range : UnwindDestToTryRanges[EHPad]) 1047353358Sdim BrDestToTryRanges[BrDest].push_back(Range); 1048353358Sdim BrDestToExnReg[BrDest] = ExnReg; 1049353358Sdim 1050353358Sdim // In case we fall through to the continuation BB after the catch block, we 1051353358Sdim // now have to add a branch to it. 1052353358Sdim // - Before 1053353358Sdim // try 1054353358Sdim // ... 1055353358Sdim // (falls through to 'cont') 1056353358Sdim // catch 1057353358Sdim // handler body 1058353358Sdim // end 1059353358Sdim // <-- cont 1060353358Sdim // 1061353358Sdim // - After 1062353358Sdim // try 1063353358Sdim // ... 1064353358Sdim // br %cont (new) 1065353358Sdim // catch 1066353358Sdim // end 1067353358Sdim // handler body 1068353358Sdim // <-- cont 1069353358Sdim MachineBasicBlock *EHPadLayoutPred = &*std::prev(EHPad->getIterator()); 1070353358Sdim MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 1071353358Sdim SmallVector<MachineOperand, 4> Cond; 1072353358Sdim bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond); 1073353358Sdim if (Analyzable && !TBB && !FBB) { 1074353358Sdim DebugLoc DL = EHPadLayoutPred->empty() 1075353358Sdim ? DebugLoc() 1076353358Sdim : EHPadLayoutPred->rbegin()->getDebugLoc(); 1077353358Sdim BuildMI(EHPadLayoutPred, DL, TII.get(WebAssembly::BR)).addMBB(Cont); 1078353358Sdim } 1079353358Sdim } 1080353358Sdim 1081353358Sdim // For possibly throwing calls whose unwind destinations are currently 1082353358Sdim // incorrect because of CFG linearization, we wrap them with a nested 1083353358Sdim // try/catch/end_try, and within the new catch block, we branch to the correct 1084353358Sdim // handler. 1085353358Sdim // - Before 1086353358Sdim // mbb: 1087353358Sdim // call @foo <- Unwind destination mismatch! 1088353358Sdim // ehpad: 1089353358Sdim // ... 1090353358Sdim // 1091353358Sdim // - After 1092353358Sdim // mbb: 1093353358Sdim // try (new) 1094353358Sdim // call @foo 1095353358Sdim // nested-ehpad: (new) 1096353358Sdim // catch (new) 1097353358Sdim // local.set n / drop (new) 1098353358Sdim // br %brdest (new) 1099353358Sdim // nested-end: (new) 1100353358Sdim // end_try (new) 1101353358Sdim // ehpad: 1102353358Sdim // ... 1103353358Sdim for (auto &P : BrDestToTryRanges) { 1104353358Sdim MachineBasicBlock *BrDest = P.first; 1105353358Sdim auto &TryRanges = P.second; 1106353358Sdim unsigned ExnReg = BrDestToExnReg[BrDest]; 1107353358Sdim 1108353358Sdim for (auto Range : TryRanges) { 1109353358Sdim MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; 1110353358Sdim std::tie(RangeBegin, RangeEnd) = Range; 1111353358Sdim auto *MBB = RangeBegin->getParent(); 1112353358Sdim 1113353358Sdim // Include possible EH_LABELs in the range 1114353358Sdim if (RangeBegin->getIterator() != MBB->begin() && 1115353358Sdim std::prev(RangeBegin->getIterator())->isEHLabel()) 1116353358Sdim RangeBegin = &*std::prev(RangeBegin->getIterator()); 1117353358Sdim if (std::next(RangeEnd->getIterator()) != MBB->end() && 1118353358Sdim std::next(RangeEnd->getIterator())->isEHLabel()) 1119353358Sdim RangeEnd = &*std::next(RangeEnd->getIterator()); 1120353358Sdim 1121353358Sdim MachineBasicBlock *EHPad = nullptr; 1122353358Sdim for (auto *Succ : MBB->successors()) { 1123353358Sdim if (Succ->isEHPad()) { 1124353358Sdim EHPad = Succ; 1125353358Sdim break; 1126353358Sdim } 1127353358Sdim } 1128353358Sdim 1129353358Sdim // Create the nested try instruction. 1130353358Sdim MachineInstr *NestedTry = 1131353358Sdim BuildMI(*MBB, *RangeBegin, RangeBegin->getDebugLoc(), 1132353358Sdim TII.get(WebAssembly::TRY)) 1133360784Sdim .addImm(int64_t(WebAssembly::BlockType::Void)); 1134353358Sdim 1135353358Sdim // Create the nested EH pad and fill instructions in. 1136353358Sdim MachineBasicBlock *NestedEHPad = MF.CreateMachineBasicBlock(); 1137353358Sdim MF.insert(std::next(MBB->getIterator()), NestedEHPad); 1138353358Sdim NestedEHPad->setIsEHPad(); 1139353358Sdim NestedEHPad->setIsEHScopeEntry(); 1140353358Sdim BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::CATCH), 1141353358Sdim ExnReg); 1142353358Sdim BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::BR)) 1143353358Sdim .addMBB(BrDest); 1144353358Sdim 1145353358Sdim // Create the nested continuation BB and end_try instruction. 1146353358Sdim MachineBasicBlock *NestedCont = MF.CreateMachineBasicBlock(); 1147353358Sdim MF.insert(std::next(NestedEHPad->getIterator()), NestedCont); 1148353358Sdim MachineInstr *NestedEndTry = 1149353358Sdim BuildMI(*NestedCont, NestedCont->begin(), RangeEnd->getDebugLoc(), 1150353358Sdim TII.get(WebAssembly::END_TRY)); 1151353358Sdim // In case MBB has more instructions after the try range, move them to the 1152353358Sdim // new nested continuation BB. 1153353358Sdim NestedCont->splice(NestedCont->end(), MBB, 1154353358Sdim std::next(RangeEnd->getIterator()), MBB->end()); 1155360784Sdim unstackifyVRegsUsedInSplitBB(*MBB, *NestedCont, MFI, MRI); 1156353358Sdim registerTryScope(NestedTry, NestedEndTry, NestedEHPad); 1157353358Sdim 1158353358Sdim // Fix predecessor-successor relationship. 1159353358Sdim NestedCont->transferSuccessors(MBB); 1160353358Sdim if (EHPad) 1161353358Sdim NestedCont->removeSuccessor(EHPad); 1162353358Sdim MBB->addSuccessor(NestedEHPad); 1163353358Sdim MBB->addSuccessor(NestedCont); 1164353358Sdim NestedEHPad->addSuccessor(BrDest); 1165353358Sdim } 1166353358Sdim } 1167353358Sdim 1168353358Sdim // Renumber BBs and recalculate ScopeTop info because new BBs might have been 1169353358Sdim // created and inserted above. 1170353358Sdim MF.RenumberBlocks(); 1171353358Sdim ScopeTops.clear(); 1172353358Sdim ScopeTops.resize(MF.getNumBlockIDs()); 1173353358Sdim for (auto &MBB : reverse(MF)) { 1174353358Sdim for (auto &MI : reverse(MBB)) { 1175353358Sdim if (ScopeTops[MBB.getNumber()]) 1176353358Sdim break; 1177353358Sdim switch (MI.getOpcode()) { 1178353358Sdim case WebAssembly::END_BLOCK: 1179353358Sdim case WebAssembly::END_LOOP: 1180353358Sdim case WebAssembly::END_TRY: 1181353358Sdim ScopeTops[MBB.getNumber()] = EndToBegin[&MI]->getParent(); 1182353358Sdim break; 1183353358Sdim case WebAssembly::CATCH: 1184353358Sdim ScopeTops[MBB.getNumber()] = EHPadToTry[&MBB]->getParent(); 1185353358Sdim break; 1186353358Sdim } 1187353358Sdim } 1188353358Sdim } 1189353358Sdim 1190353358Sdim // Recompute the dominator tree. 1191353358Sdim getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF); 1192353358Sdim 1193353358Sdim // Place block markers for newly added branches. 1194353358Sdim SmallVector <MachineBasicBlock *, 8> BrDests; 1195353358Sdim for (auto &P : BrDestToTryRanges) 1196353358Sdim BrDests.push_back(P.first); 1197353358Sdim llvm::sort(BrDests, 1198353358Sdim [&](const MachineBasicBlock *A, const MachineBasicBlock *B) { 1199353358Sdim auto ANum = A->getNumber(); 1200353358Sdim auto BNum = B->getNumber(); 1201353358Sdim return ANum < BNum; 1202353358Sdim }); 1203353358Sdim for (auto *Dest : BrDests) 1204353358Sdim placeBlockMarker(*Dest); 1205353358Sdim 1206353358Sdim return true; 1207353358Sdim} 1208353358Sdim 1209294024Sdimstatic unsigned 1210353358SdimgetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack, 1211294024Sdim const MachineBasicBlock *MBB) { 1212294024Sdim unsigned Depth = 0; 1213294024Sdim for (auto X : reverse(Stack)) { 1214294024Sdim if (X == MBB) 1215294024Sdim break; 1216294024Sdim ++Depth; 1217294024Sdim } 1218294024Sdim assert(Depth < Stack.size() && "Branch destination should be in scope"); 1219294024Sdim return Depth; 1220294024Sdim} 1221294024Sdim 1222314564Sdim/// In normal assembly languages, when the end of a function is unreachable, 1223314564Sdim/// because the function ends in an infinite loop or a noreturn call or similar, 1224314564Sdim/// it isn't necessary to worry about the function return type at the end of 1225314564Sdim/// the function, because it's never reached. However, in WebAssembly, blocks 1226314564Sdim/// that end at the function end need to have a return type signature that 1227314564Sdim/// matches the function signature, even though it's unreachable. This function 1228314564Sdim/// checks for such cases and fixes up the signatures. 1229344779Sdimvoid WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { 1230344779Sdim const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 1231314564Sdim 1232314564Sdim if (MFI.getResults().empty()) 1233314564Sdim return; 1234314564Sdim 1235360784Sdim // MCInstLower will add the proper types to multivalue signatures based on the 1236360784Sdim // function return type 1237360784Sdim WebAssembly::BlockType RetType = 1238360784Sdim MFI.getResults().size() > 1 1239360784Sdim ? WebAssembly::BlockType::Multivalue 1240360784Sdim : WebAssembly::BlockType( 1241360784Sdim WebAssembly::toValType(MFI.getResults().front())); 1242314564Sdim 1243314564Sdim for (MachineBasicBlock &MBB : reverse(MF)) { 1244314564Sdim for (MachineInstr &MI : reverse(MBB)) { 1245341825Sdim if (MI.isPosition() || MI.isDebugInstr()) 1246314564Sdim continue; 1247360784Sdim switch (MI.getOpcode()) { 1248360784Sdim case WebAssembly::END_BLOCK: 1249360784Sdim case WebAssembly::END_LOOP: 1250360784Sdim case WebAssembly::END_TRY: 1251353358Sdim EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType)); 1252314564Sdim continue; 1253360784Sdim default: 1254360784Sdim // Something other than an `end`. We're done. 1255360784Sdim return; 1256314564Sdim } 1257314564Sdim } 1258314564Sdim } 1259314564Sdim} 1260314564Sdim 1261321369Sdim// WebAssembly functions end with an end instruction, as if the function body 1262321369Sdim// were a block. 1263353358Sdimstatic void appendEndToFunction(MachineFunction &MF, 1264344779Sdim const WebAssemblyInstrInfo &TII) { 1265341825Sdim BuildMI(MF.back(), MF.back().end(), 1266341825Sdim MF.back().findPrevDebugLoc(MF.back().end()), 1267321369Sdim TII.get(WebAssembly::END_FUNCTION)); 1268321369Sdim} 1269321369Sdim 1270344779Sdim/// Insert LOOP/TRY/BLOCK markers at appropriate places. 1271344779Sdimvoid WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { 1272344779Sdim // We allocate one more than the number of blocks in the function to 1273344779Sdim // accommodate for the possible fake block we may insert at the end. 1274344779Sdim ScopeTops.resize(MF.getNumBlockIDs() + 1); 1275344779Sdim // Place the LOOP for MBB if MBB is the header of a loop. 1276344779Sdim for (auto &MBB : MF) 1277344779Sdim placeLoopMarker(MBB); 1278353358Sdim 1279353358Sdim const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 1280353358Sdim for (auto &MBB : MF) { 1281353358Sdim if (MBB.isEHPad()) { 1282353358Sdim // Place the TRY for MBB if MBB is the EH pad of an exception. 1283353358Sdim if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1284353358Sdim MF.getFunction().hasPersonalityFn()) 1285353358Sdim placeTryMarker(MBB); 1286353358Sdim } else { 1287353358Sdim // Place the BLOCK for MBB if MBB is branched to from above. 1288353358Sdim placeBlockMarker(MBB); 1289353358Sdim } 1290353358Sdim } 1291353358Sdim // Fix mismatches in unwind destinations induced by linearizing the code. 1292360784Sdim if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1293360784Sdim MF.getFunction().hasPersonalityFn()) 1294360784Sdim fixUnwindMismatches(MF); 1295344779Sdim} 1296292915Sdim 1297344779Sdimvoid WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { 1298294024Sdim // Now rewrite references to basic blocks to be depth immediates. 1299294024Sdim SmallVector<const MachineBasicBlock *, 8> Stack; 1300294024Sdim for (auto &MBB : reverse(MF)) { 1301344779Sdim for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) { 1302344779Sdim MachineInstr &MI = *I; 1303294024Sdim switch (MI.getOpcode()) { 1304294024Sdim case WebAssembly::BLOCK: 1305344779Sdim case WebAssembly::TRY: 1306344779Sdim assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= 1307344779Sdim MBB.getNumber() && 1308344779Sdim "Block/try marker should be balanced"); 1309344779Sdim Stack.pop_back(); 1310344779Sdim break; 1311344779Sdim 1312294024Sdim case WebAssembly::LOOP: 1313294024Sdim assert(Stack.back() == &MBB && "Loop top should be balanced"); 1314294024Sdim Stack.pop_back(); 1315294024Sdim break; 1316344779Sdim 1317294024Sdim case WebAssembly::END_BLOCK: 1318344779Sdim case WebAssembly::END_TRY: 1319294024Sdim Stack.push_back(&MBB); 1320294024Sdim break; 1321344779Sdim 1322294024Sdim case WebAssembly::END_LOOP: 1323344779Sdim Stack.push_back(EndToBegin[&MI]->getParent()); 1324294024Sdim break; 1325344779Sdim 1326294024Sdim default: 1327294024Sdim if (MI.isTerminator()) { 1328294024Sdim // Rewrite MBB operands to be depth immediates. 1329294024Sdim SmallVector<MachineOperand, 4> Ops(MI.operands()); 1330294024Sdim while (MI.getNumOperands() > 0) 1331294024Sdim MI.RemoveOperand(MI.getNumOperands() - 1); 1332294024Sdim for (auto MO : Ops) { 1333294024Sdim if (MO.isMBB()) 1334353358Sdim MO = MachineOperand::CreateImm(getDepth(Stack, MO.getMBB())); 1335294024Sdim MI.addOperand(MF, MO); 1336294024Sdim } 1337294024Sdim } 1338294024Sdim break; 1339294024Sdim } 1340294024Sdim } 1341294024Sdim } 1342294024Sdim assert(Stack.empty() && "Control flow should be balanced"); 1343344779Sdim} 1344314564Sdim 1345344779Sdimvoid WebAssemblyCFGStackify::releaseMemory() { 1346344779Sdim ScopeTops.clear(); 1347344779Sdim BeginToEnd.clear(); 1348344779Sdim EndToBegin.clear(); 1349344779Sdim TryToEHPad.clear(); 1350344779Sdim EHPadToTry.clear(); 1351353358Sdim AppendixBB = nullptr; 1352292915Sdim} 1353292915Sdim 1354292915Sdimbool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 1355341825Sdim LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n" 1356341825Sdim "********** Function: " 1357341825Sdim << MF.getName() << '\n'); 1358353358Sdim const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 1359292915Sdim 1360344779Sdim releaseMemory(); 1361344779Sdim 1362314564Sdim // Liveness is not tracked for VALUE_STACK physreg. 1363294024Sdim MF.getRegInfo().invalidateLiveness(); 1364292915Sdim 1365344779Sdim // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes. 1366344779Sdim placeMarkers(MF); 1367292915Sdim 1368353358Sdim // Remove unnecessary instructions possibly introduced by try/end_trys. 1369353358Sdim if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1370353358Sdim MF.getFunction().hasPersonalityFn()) 1371353358Sdim removeUnnecessaryInstrs(MF); 1372353358Sdim 1373344779Sdim // Convert MBB operands in terminators to relative depth immediates. 1374344779Sdim rewriteDepthImmediates(MF); 1375344779Sdim 1376344779Sdim // Fix up block/loop/try signatures at the end of the function to conform to 1377344779Sdim // WebAssembly's rules. 1378344779Sdim fixEndsAtEndOfFunction(MF); 1379344779Sdim 1380344779Sdim // Add an end instruction at the end of the function body. 1381344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 1382344779Sdim if (!MF.getSubtarget<WebAssemblySubtarget>() 1383344779Sdim .getTargetTriple() 1384344779Sdim .isOSBinFormatELF()) 1385353358Sdim appendEndToFunction(MF, TII); 1386344779Sdim 1387353358Sdim MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified(); 1388292915Sdim return true; 1389292915Sdim} 1390