2673 lines · cpp
1//===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8///9/// \file10/// This file implements a CFG stacking pass.11///12/// This pass inserts BLOCK, LOOP, TRY, and TRY_TABLE markers to mark the start13/// of scopes, since scope boundaries serve as the labels for WebAssembly's14/// control transfers.15///16/// This is sufficient to convert arbitrary CFGs into a form that works on17/// WebAssembly, provided that all loops are single-entry.18///19/// In case we use exceptions, this pass also fixes mismatches in unwind20/// destinations created during transforming CFG into wasm structured format.21///22//===----------------------------------------------------------------------===//23 24#include "Utils/WebAssemblyTypeUtilities.h"25#include "WebAssembly.h"26#include "WebAssemblyExceptionInfo.h"27#include "WebAssemblyMachineFunctionInfo.h"28#include "WebAssemblySortRegion.h"29#include "WebAssemblySubtarget.h"30#include "WebAssemblyTargetMachine.h"31#include "WebAssemblyUtilities.h"32#include "llvm/ADT/Statistic.h"33#include "llvm/BinaryFormat/Wasm.h"34#include "llvm/CodeGen/MachineDominators.h"35#include "llvm/CodeGen/MachineInstrBuilder.h"36#include "llvm/CodeGen/MachineLoopInfo.h"37#include "llvm/CodeGen/WasmEHFuncInfo.h"38#include "llvm/MC/MCAsmInfo.h"39#include "llvm/Target/TargetMachine.h"40using namespace llvm;41using WebAssembly::SortRegionInfo;42 43#define DEBUG_TYPE "wasm-cfg-stackify"44 45STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found");46STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found");47 48namespace {49class WebAssemblyCFGStackify final : public MachineFunctionPass {50 MachineDominatorTree *MDT;51 52 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }53 54 void getAnalysisUsage(AnalysisUsage &AU) const override {55 AU.addRequired<MachineDominatorTreeWrapperPass>();56 AU.addRequired<MachineLoopInfoWrapperPass>();57 AU.addRequired<WebAssemblyExceptionInfo>();58 MachineFunctionPass::getAnalysisUsage(AU);59 }60 61 bool runOnMachineFunction(MachineFunction &MF) override;62 63 // For each block whose label represents the end of a scope, record the block64 // which holds the beginning of the scope. This will allow us to quickly skip65 // over scoped regions when walking blocks.66 SmallVector<MachineBasicBlock *, 8> ScopeTops;67 void updateScopeTops(MachineBasicBlock *Begin, MachineBasicBlock *End) {68 int BeginNo = Begin->getNumber();69 int EndNo = End->getNumber();70 if (!ScopeTops[EndNo] || ScopeTops[EndNo]->getNumber() > BeginNo)71 ScopeTops[EndNo] = Begin;72 }73 74 // Placing markers.75 void placeMarkers(MachineFunction &MF);76 void placeBlockMarker(MachineBasicBlock &MBB);77 void placeLoopMarker(MachineBasicBlock &MBB);78 void placeTryMarker(MachineBasicBlock &MBB);79 void placeTryTableMarker(MachineBasicBlock &MBB);80 81 // Unwind mismatch fixing for exception handling82 // - Common functions83 bool fixCallUnwindMismatches(MachineFunction &MF);84 bool fixCatchUnwindMismatches(MachineFunction &MF);85 void recalculateScopeTops(MachineFunction &MF);86 // - Legacy EH87 void addNestedTryDelegate(MachineInstr *RangeBegin, MachineInstr *RangeEnd,88 MachineBasicBlock *UnwindDest);89 void removeUnnecessaryInstrs(MachineFunction &MF);90 // - Standard EH (exnref)91 void addNestedTryTable(MachineInstr *RangeBegin, MachineInstr *RangeEnd,92 MachineBasicBlock *UnwindDest);93 MachineBasicBlock *getTrampolineBlock(MachineBasicBlock *UnwindDest);94 95 // Wrap-up96 using EndMarkerInfo =97 std::pair<const MachineBasicBlock *, const MachineInstr *>;98 unsigned getBranchDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,99 const MachineBasicBlock *MBB);100 unsigned getDelegateDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,101 const MachineBasicBlock *MBB);102 unsigned getRethrowDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,103 const MachineBasicBlock *EHPadToRethrow);104 void rewriteDepthImmediates(MachineFunction &MF);105 void fixEndsAtEndOfFunction(MachineFunction &MF);106 void cleanupFunctionData(MachineFunction &MF);107 108 // For each BLOCK|LOOP|TRY|TRY_TABLE, the corresponding109 // END_(BLOCK|LOOP|TRY|TRY_TABLE) or DELEGATE (in case of TRY).110 DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd;111 // For each END_(BLOCK|LOOP|TRY|TRY_TABLE) or DELEGATE, the corresponding112 // BLOCK|LOOP|TRY|TRY_TABLE.113 DenseMap<const MachineInstr *, MachineInstr *> EndToBegin;114 // <TRY marker, EH pad> map115 DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad;116 // <EH pad, TRY marker> map117 DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry;118 119 DenseMap<const MachineBasicBlock *, MachineBasicBlock *>120 UnwindDestToTrampoline;121 122 // We need an appendix block to place 'end_loop' or 'end_try' marker when the123 // loop / exception bottom block is the last block in a function124 MachineBasicBlock *AppendixBB = nullptr;125 MachineBasicBlock *getAppendixBlock(MachineFunction &MF) {126 if (!AppendixBB) {127 AppendixBB = MF.CreateMachineBasicBlock();128 // Give it a fake predecessor so that AsmPrinter prints its label.129 AppendixBB->addSuccessor(AppendixBB);130 // If the caller trampoline BB exists, insert the appendix BB before it.131 // Otherwise insert it at the end of the function.132 if (CallerTrampolineBB)133 MF.insert(CallerTrampolineBB->getIterator(), AppendixBB);134 else135 MF.push_back(AppendixBB);136 }137 return AppendixBB;138 }139 140 // Create a caller-dedicated trampoline BB to be used for fixing unwind141 // mismatches where the unwind destination is the caller.142 MachineBasicBlock *CallerTrampolineBB = nullptr;143 MachineBasicBlock *getCallerTrampolineBlock(MachineFunction &MF) {144 if (!CallerTrampolineBB) {145 CallerTrampolineBB = MF.CreateMachineBasicBlock();146 MF.push_back(CallerTrampolineBB);147 }148 return CallerTrampolineBB;149 }150 151 // Before running rewriteDepthImmediates function, 'delegate' has a BB as its152 // destination operand. getFakeCallerBlock() returns a fake BB that will be153 // used for the operand when 'delegate' needs to rethrow to the caller. This154 // will be rewritten as an immediate value that is the number of block depths155 // + 1 in rewriteDepthImmediates, and this fake BB will be removed at the end156 // of the pass.157 MachineBasicBlock *FakeCallerBB = nullptr;158 MachineBasicBlock *getFakeCallerBlock(MachineFunction &MF) {159 if (!FakeCallerBB)160 FakeCallerBB = MF.CreateMachineBasicBlock();161 return FakeCallerBB;162 }163 164 // Helper functions to register / unregister scope information created by165 // marker instructions.166 void registerScope(MachineInstr *Begin, MachineInstr *End);167 void registerTryScope(MachineInstr *Begin, MachineInstr *End,168 MachineBasicBlock *EHPad);169 void unregisterScope(MachineInstr *Begin);170 171public:172 static char ID; // Pass identification, replacement for typeid173 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}174 ~WebAssemblyCFGStackify() override { releaseMemory(); }175 void releaseMemory() override;176};177} // end anonymous namespace178 179char WebAssemblyCFGStackify::ID = 0;180INITIALIZE_PASS(181 WebAssemblyCFGStackify, DEBUG_TYPE,182 "Insert BLOCK/LOOP/TRY/TRY_TABLE markers for WebAssembly scopes", false,183 false)184 185FunctionPass *llvm::createWebAssemblyCFGStackify() {186 return new WebAssemblyCFGStackify();187}188 189/// Test whether Pred has any terminators explicitly branching to MBB, as190/// opposed to falling through. Note that it's possible (eg. in unoptimized191/// code) for a branch instruction to both branch to a block and fallthrough192/// to it, so we check the actual branch operands to see if there are any193/// explicit mentions.194static bool explicitlyBranchesTo(MachineBasicBlock *Pred,195 MachineBasicBlock *MBB) {196 for (MachineInstr &MI : Pred->terminators())197 for (MachineOperand &MO : MI.explicit_operands())198 if (MO.isMBB() && MO.getMBB() == MBB)199 return true;200 return false;201}202 203// Returns an iterator to the earliest position possible within the MBB,204// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet205// contains instructions that should go before the marker, and AfterSet contains206// ones that should go after the marker. In this function, AfterSet is only207// used for validation checking.208template <typename Container>209static MachineBasicBlock::iterator210getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet,211 const Container &AfterSet) {212 auto InsertPos = MBB->end();213 while (InsertPos != MBB->begin()) {214 if (BeforeSet.count(&*std::prev(InsertPos))) {215#ifndef NDEBUG216 // Validation check217 for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)218 assert(!AfterSet.count(&*std::prev(Pos)));219#endif220 break;221 }222 --InsertPos;223 }224 return InsertPos;225}226 227// Returns an iterator to the latest position possible within the MBB,228// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet229// contains instructions that should go before the marker, and AfterSet contains230// ones that should go after the marker. In this function, BeforeSet is only231// used for validation checking.232template <typename Container>233static MachineBasicBlock::iterator234getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet,235 const Container &AfterSet) {236 auto InsertPos = MBB->begin();237 while (InsertPos != MBB->end()) {238 if (AfterSet.count(&*InsertPos)) {239#ifndef NDEBUG240 // Validation check241 for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)242 assert(!BeforeSet.count(&*Pos));243#endif244 break;245 }246 ++InsertPos;247 }248 return InsertPos;249}250 251void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,252 MachineInstr *End) {253 BeginToEnd[Begin] = End;254 EndToBegin[End] = Begin;255}256 257// When 'End' is not an 'end_try' but a 'delegate', EHPad is nullptr.258void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,259 MachineInstr *End,260 MachineBasicBlock *EHPad) {261 registerScope(Begin, End);262 TryToEHPad[Begin] = EHPad;263 EHPadToTry[EHPad] = Begin;264}265 266void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {267 assert(BeginToEnd.count(Begin));268 MachineInstr *End = BeginToEnd[Begin];269 assert(EndToBegin.count(End));270 BeginToEnd.erase(Begin);271 EndToBegin.erase(End);272 MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);273 if (EHPad) {274 assert(EHPadToTry.count(EHPad));275 TryToEHPad.erase(Begin);276 EHPadToTry.erase(EHPad);277 }278}279 280/// Insert a BLOCK marker for branches to MBB (if needed).281// TODO Consider a more generalized way of handling block (and also loop and282// try) signatures when we implement the multi-value proposal later.283void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {284 assert(!MBB.isEHPad());285 MachineFunction &MF = *MBB.getParent();286 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();287 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();288 289 // First compute the nearest common dominator of all forward non-fallthrough290 // predecessors so that we minimize the time that the BLOCK is on the stack,291 // which reduces overall stack height.292 MachineBasicBlock *Header = nullptr;293 bool IsBranchedTo = false;294 int MBBNumber = MBB.getNumber();295 for (MachineBasicBlock *Pred : MBB.predecessors()) {296 if (Pred->getNumber() < MBBNumber) {297 Header = Header ? MDT->findNearestCommonDominator(Header, Pred) : Pred;298 if (explicitlyBranchesTo(Pred, &MBB))299 IsBranchedTo = true;300 }301 }302 if (!Header)303 return;304 if (!IsBranchedTo)305 return;306 307 assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");308 MachineBasicBlock *LayoutPred = MBB.getPrevNode();309 310 // If the nearest common dominator is inside a more deeply nested context,311 // walk out to the nearest scope which isn't more deeply nested.312 for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {313 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {314 if (ScopeTop->getNumber() > Header->getNumber()) {315 // Skip over an intervening scope.316 I = std::next(ScopeTop->getIterator());317 } else {318 // We found a scope level at an appropriate depth.319 Header = ScopeTop;320 break;321 }322 }323 }324 325 // Decide where in MBB to put the BLOCK.326 327 // Instructions that should go before the BLOCK.328 SmallPtrSet<const MachineInstr *, 4> BeforeSet;329 // Instructions that should go after the BLOCK.330 SmallPtrSet<const MachineInstr *, 4> AfterSet;331 for (const auto &MI : *Header) {332 // If there is a previously placed LOOP marker and the bottom block of the333 // loop is above MBB, it should be after the BLOCK, because the loop is334 // nested in this BLOCK. Otherwise it should be before the BLOCK.335 if (MI.getOpcode() == WebAssembly::LOOP) {336 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();337 if (MBB.getNumber() > LoopBottom->getNumber())338 AfterSet.insert(&MI);339#ifndef NDEBUG340 else341 BeforeSet.insert(&MI);342#endif343 }344 345 // If there is a previously placed BLOCK/TRY/TRY_TABLE marker and its346 // corresponding END marker is before the current BLOCK's END marker, that347 // should be placed after this BLOCK. Otherwise it should be placed before348 // this BLOCK marker.349 if (MI.getOpcode() == WebAssembly::BLOCK ||350 MI.getOpcode() == WebAssembly::TRY ||351 MI.getOpcode() == WebAssembly::TRY_TABLE) {352 if (BeginToEnd[&MI]->getParent()->getNumber() <= MBB.getNumber())353 AfterSet.insert(&MI);354#ifndef NDEBUG355 else356 BeforeSet.insert(&MI);357#endif358 }359 360#ifndef NDEBUG361 // All END_(BLOCK|LOOP|TRY|TRY_TABLE) markers should be before the BLOCK.362 if (MI.getOpcode() == WebAssembly::END_BLOCK ||363 MI.getOpcode() == WebAssembly::END_LOOP ||364 MI.getOpcode() == WebAssembly::END_TRY ||365 MI.getOpcode() == WebAssembly::END_TRY_TABLE)366 BeforeSet.insert(&MI);367#endif368 369 // Terminators should go after the BLOCK.370 if (MI.isTerminator())371 AfterSet.insert(&MI);372 }373 374 // Local expression tree should go after the BLOCK.375 for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;376 --I) {377 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())378 continue;379 if (WebAssembly::isChild(*std::prev(I), MFI))380 AfterSet.insert(&*std::prev(I));381 else382 break;383 }384 385 // Add the BLOCK.386 WebAssembly::BlockType ReturnType = WebAssembly::BlockType::Void;387 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);388 MachineInstr *Begin =389 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),390 TII.get(WebAssembly::BLOCK))391 .addImm(int64_t(ReturnType));392 393 // Decide where in MBB to put the END_BLOCK.394 BeforeSet.clear();395 AfterSet.clear();396 for (auto &MI : MBB) {397#ifndef NDEBUG398 // END_BLOCK should precede existing LOOP markers.399 if (MI.getOpcode() == WebAssembly::LOOP)400 AfterSet.insert(&MI);401#endif402 403 // If there is a previously placed END_LOOP marker and the header of the404 // loop is above this block's header, the END_LOOP should be placed after405 // the END_BLOCK, because the loop contains this block. Otherwise the406 // END_LOOP should be placed before the END_BLOCK. The same for END_TRY.407 //408 // Note that while there can be existing END_TRYs, there can't be409 // END_TRY_TABLEs; END_TRYs are placed when its corresponding EH pad is410 // processed, so they are placed below MBB (EH pad) in placeTryMarker. But411 // END_TRY_TABLE is placed like a END_BLOCK, so they can't be here already.412 if (MI.getOpcode() == WebAssembly::END_LOOP ||413 MI.getOpcode() == WebAssembly::END_TRY) {414 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())415 BeforeSet.insert(&MI);416#ifndef NDEBUG417 else418 AfterSet.insert(&MI);419#endif420 }421 }422 423 // Mark the end of the block.424 InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);425 MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),426 TII.get(WebAssembly::END_BLOCK));427 registerScope(Begin, End);428 429 // Track the farthest-spanning scope that ends at this point.430 updateScopeTops(Header, &MBB);431}432 433/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).434void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {435 MachineFunction &MF = *MBB.getParent();436 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();437 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();438 SortRegionInfo SRI(MLI, WEI);439 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();440 441 MachineLoop *Loop = MLI.getLoopFor(&MBB);442 if (!Loop || Loop->getHeader() != &MBB)443 return;444 445 // The operand of a LOOP is the first block after the loop. If the loop is the446 // bottom of the function, insert a dummy block at the end.447 MachineBasicBlock *Bottom = SRI.getBottom(Loop);448 auto Iter = std::next(Bottom->getIterator());449 if (Iter == MF.end()) {450 getAppendixBlock(MF);451 Iter = std::next(Bottom->getIterator());452 }453 MachineBasicBlock *AfterLoop = &*Iter;454 455 // Decide where in Header to put the LOOP.456 SmallPtrSet<const MachineInstr *, 4> BeforeSet;457 SmallPtrSet<const MachineInstr *, 4> AfterSet;458 for (const auto &MI : MBB) {459 // LOOP marker should be after any existing loop that ends here. Otherwise460 // we assume the instruction belongs to the loop.461 if (MI.getOpcode() == WebAssembly::END_LOOP)462 BeforeSet.insert(&MI);463#ifndef NDEBUG464 else465 AfterSet.insert(&MI);466#endif467 }468 469 // Mark the beginning of the loop.470 auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);471 MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),472 TII.get(WebAssembly::LOOP))473 .addImm(int64_t(WebAssembly::BlockType::Void));474 475 // Decide where in MBB to put the END_LOOP.476 BeforeSet.clear();477 AfterSet.clear();478#ifndef NDEBUG479 for (const auto &MI : MBB)480 // Existing END_LOOP markers belong to parent loops of this loop481 if (MI.getOpcode() == WebAssembly::END_LOOP)482 AfterSet.insert(&MI);483#endif484 485 // Mark the end of the loop (using arbitrary debug location that branched to486 // the loop end as its location).487 InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet);488 DebugLoc EndDL = AfterLoop->pred_empty()489 ? DebugLoc()490 : (*AfterLoop->pred_rbegin())->findBranchDebugLoc();491 MachineInstr *End =492 BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP));493 registerScope(Begin, End);494 495 assert((!ScopeTops[AfterLoop->getNumber()] ||496 ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&497 "With block sorting the outermost loop for a block should be first.");498 updateScopeTops(&MBB, AfterLoop);499}500 501void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {502 assert(MBB.isEHPad());503 MachineFunction &MF = *MBB.getParent();504 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();505 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();506 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();507 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();508 SortRegionInfo SRI(MLI, WEI);509 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();510 511 // Compute the nearest common dominator of all unwind predecessors512 MachineBasicBlock *Header = nullptr;513 int MBBNumber = MBB.getNumber();514 for (auto *Pred : MBB.predecessors()) {515 if (Pred->getNumber() < MBBNumber) {516 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;517 assert(!explicitlyBranchesTo(Pred, &MBB) &&518 "Explicit branch to an EH pad!");519 }520 }521 if (!Header)522 return;523 524 // If this try is at the bottom of the function, insert a dummy block at the525 // end.526 WebAssemblyException *WE = WEI.getExceptionFor(&MBB);527 assert(WE);528 MachineBasicBlock *Bottom = SRI.getBottom(WE);529 auto Iter = std::next(Bottom->getIterator());530 if (Iter == MF.end()) {531 getAppendixBlock(MF);532 Iter = std::next(Bottom->getIterator());533 }534 MachineBasicBlock *Cont = &*Iter;535 536 // If the nearest common dominator is inside a more deeply nested context,537 // walk out to the nearest scope which isn't more deeply nested.538 for (MachineFunction::iterator I(Bottom), E(Header); I != E; --I) {539 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {540 if (ScopeTop->getNumber() > Header->getNumber()) {541 // Skip over an intervening scope.542 I = std::next(ScopeTop->getIterator());543 } else {544 // We found a scope level at an appropriate depth.545 Header = ScopeTop;546 break;547 }548 }549 }550 551 // Decide where in Header to put the TRY.552 553 // Instructions that should go before the TRY.554 SmallPtrSet<const MachineInstr *, 4> BeforeSet;555 // Instructions that should go after the TRY.556 SmallPtrSet<const MachineInstr *, 4> AfterSet;557 for (const auto &MI : *Header) {558 // If there is a previously placed LOOP marker and the bottom block of the559 // loop is above MBB, it should be after the TRY, because the loop is nested560 // in this TRY. Otherwise it should be before the TRY.561 if (MI.getOpcode() == WebAssembly::LOOP) {562 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();563 if (MBB.getNumber() > LoopBottom->getNumber())564 AfterSet.insert(&MI);565#ifndef NDEBUG566 else567 BeforeSet.insert(&MI);568#endif569 }570 571 // All previously inserted BLOCK/TRY markers should be after the TRY because572 // they are all nested blocks/trys.573 if (MI.getOpcode() == WebAssembly::BLOCK ||574 MI.getOpcode() == WebAssembly::TRY)575 AfterSet.insert(&MI);576 577#ifndef NDEBUG578 // All END_(BLOCK/LOOP/TRY) markers should be before the TRY.579 if (MI.getOpcode() == WebAssembly::END_BLOCK ||580 MI.getOpcode() == WebAssembly::END_LOOP ||581 MI.getOpcode() == WebAssembly::END_TRY)582 BeforeSet.insert(&MI);583#endif584 585 // Terminators should go after the TRY.586 if (MI.isTerminator())587 AfterSet.insert(&MI);588 }589 590 // If Header unwinds to MBB (= Header contains 'invoke'), the try block should591 // contain the call within it. So the call should go after the TRY. The592 // exception is when the header's terminator is a rethrow instruction, in593 // which case that instruction, not a call instruction before it, is gonna594 // throw.595 MachineInstr *ThrowingCall = nullptr;596 if (MBB.isPredecessor(Header)) {597 auto TermPos = Header->getFirstTerminator();598 if (TermPos == Header->end() ||599 TermPos->getOpcode() != WebAssembly::RETHROW) {600 for (auto &MI : reverse(*Header)) {601 if (MI.isCall()) {602 AfterSet.insert(&MI);603 ThrowingCall = &MI;604 // Possibly throwing calls are usually wrapped by EH_LABEL605 // instructions. We don't want to split them and the call.606 if (MI.getIterator() != Header->begin() &&607 std::prev(MI.getIterator())->isEHLabel()) {608 AfterSet.insert(&*std::prev(MI.getIterator()));609 ThrowingCall = &*std::prev(MI.getIterator());610 }611 break;612 }613 }614 }615 }616 617 // Local expression tree should go after the TRY.618 // For BLOCK placement, we start the search from the previous instruction of a619 // BB's terminator, but in TRY's case, we should start from the previous620 // instruction of a call that can throw, or a EH_LABEL that precedes the call,621 // because the return values of the call's previous instructions can be622 // stackified and consumed by the throwing call.623 auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall)624 : Header->getFirstTerminator();625 for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) {626 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())627 continue;628 if (WebAssembly::isChild(*std::prev(I), MFI))629 AfterSet.insert(&*std::prev(I));630 else631 break;632 }633 634 // Add the TRY.635 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);636 MachineInstr *Begin =637 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),638 TII.get(WebAssembly::TRY))639 .addImm(int64_t(WebAssembly::BlockType::Void));640 641 // Decide where in Cont to put the END_TRY.642 BeforeSet.clear();643 AfterSet.clear();644 for (const auto &MI : *Cont) {645#ifndef NDEBUG646 // END_TRY should precede existing LOOP markers.647 if (MI.getOpcode() == WebAssembly::LOOP)648 AfterSet.insert(&MI);649 650 // All END_TRY markers placed earlier belong to exceptions that contains651 // this one.652 if (MI.getOpcode() == WebAssembly::END_TRY)653 AfterSet.insert(&MI);654#endif655 656 // If there is a previously placed END_LOOP marker and its header is after657 // where TRY marker is, this loop is contained within the 'catch' part, so658 // the END_TRY marker should go after that. Otherwise, the whole try-catch659 // is contained within this loop, so the END_TRY should go before that.660 if (MI.getOpcode() == WebAssembly::END_LOOP) {661 // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they662 // are in the same BB, LOOP is always before TRY.663 if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber())664 BeforeSet.insert(&MI);665#ifndef NDEBUG666 else667 AfterSet.insert(&MI);668#endif669 }670 671 // It is not possible for an END_BLOCK to be already in this block.672 }673 674 // Mark the end of the TRY.675 InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet);676 MachineInstr *End = BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(),677 TII.get(WebAssembly::END_TRY));678 registerTryScope(Begin, End, &MBB);679 680 // Track the farthest-spanning scope that ends at this point. We create two681 // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB682 // with 'try'). We need to create 'catch' -> 'try' mapping here too because683 // markers should not span across 'catch'. For example, this should not684 // happen:685 //686 // try687 // block --| (X)688 // catch |689 // end_block --|690 // end_try691 for (auto *End : {&MBB, Cont})692 updateScopeTops(Header, End);693}694 695void WebAssemblyCFGStackify::placeTryTableMarker(MachineBasicBlock &MBB) {696 assert(MBB.isEHPad());697 MachineFunction &MF = *MBB.getParent();698 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();699 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();700 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();701 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();702 SortRegionInfo SRI(MLI, WEI);703 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();704 705 // Compute the nearest common dominator of all unwind predecessors706 MachineBasicBlock *Header = nullptr;707 int MBBNumber = MBB.getNumber();708 for (auto *Pred : MBB.predecessors()) {709 if (Pred->getNumber() < MBBNumber) {710 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;711 assert(!explicitlyBranchesTo(Pred, &MBB) &&712 "Explicit branch to an EH pad!");713 }714 }715 if (!Header)716 return;717 718 // Unlike the end_try marker, we don't place an end marker at the end of719 // exception bottom, i.e., at the end of the old 'catch' block. But we still720 // consider the try-catch part as a scope when computing ScopeTops.721 WebAssemblyException *WE = WEI.getExceptionFor(&MBB);722 assert(WE);723 MachineBasicBlock *Bottom = SRI.getBottom(WE);724 auto Iter = std::next(Bottom->getIterator());725 if (Iter == MF.end())726 Iter--;727 MachineBasicBlock *Cont = &*Iter;728 729 // If the nearest common dominator is inside a more deeply nested context,730 // walk out to the nearest scope which isn't more deeply nested.731 for (MachineFunction::iterator I(Bottom), E(Header); I != E; --I) {732 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {733 if (ScopeTop->getNumber() > Header->getNumber()) {734 // Skip over an intervening scope.735 I = std::next(ScopeTop->getIterator());736 } else {737 // We found a scope level at an appropriate depth.738 Header = ScopeTop;739 break;740 }741 }742 }743 744 // Decide where in Header to put the TRY_TABLE.745 746 // Instructions that should go before the TRY_TABLE.747 SmallPtrSet<const MachineInstr *, 4> BeforeSet;748 // Instructions that should go after the TRY_TABLE.749 SmallPtrSet<const MachineInstr *, 4> AfterSet;750 for (const auto &MI : *Header) {751 // If there is a previously placed LOOP marker and the bottom block of the752 // loop is above MBB, it should be after the TRY_TABLE, because the loop is753 // nested in this TRY_TABLE. Otherwise it should be before the TRY_TABLE.754 if (MI.getOpcode() == WebAssembly::LOOP) {755 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();756 if (MBB.getNumber() > LoopBottom->getNumber())757 AfterSet.insert(&MI);758#ifndef NDEBUG759 else760 BeforeSet.insert(&MI);761#endif762 }763 764 // All previously inserted BLOCK/TRY_TABLE markers should be after the765 // TRY_TABLE because they are all nested blocks/try_tables.766 if (MI.getOpcode() == WebAssembly::BLOCK ||767 MI.getOpcode() == WebAssembly::TRY_TABLE)768 AfterSet.insert(&MI);769 770#ifndef NDEBUG771 // All END_(BLOCK/LOOP/TRY_TABLE) markers should be before the TRY_TABLE.772 if (MI.getOpcode() == WebAssembly::END_BLOCK ||773 MI.getOpcode() == WebAssembly::END_LOOP ||774 MI.getOpcode() == WebAssembly::END_TRY_TABLE)775 BeforeSet.insert(&MI);776#endif777 778 // Terminators should go after the TRY_TABLE.779 if (MI.isTerminator())780 AfterSet.insert(&MI);781 }782 783 // If Header unwinds to MBB (= Header contains 'invoke'), the try_table block784 // should contain the call within it. So the call should go after the785 // TRY_TABLE. The exception is when the header's terminator is a rethrow786 // instruction, in which case that instruction, not a call instruction before787 // it, is gonna throw.788 MachineInstr *ThrowingCall = nullptr;789 if (MBB.isPredecessor(Header)) {790 auto TermPos = Header->getFirstTerminator();791 if (TermPos == Header->end() ||792 TermPos->getOpcode() != WebAssembly::RETHROW) {793 for (auto &MI : reverse(*Header)) {794 if (MI.isCall()) {795 AfterSet.insert(&MI);796 ThrowingCall = &MI;797 // Possibly throwing calls are usually wrapped by EH_LABEL798 // instructions. We don't want to split them and the call.799 if (MI.getIterator() != Header->begin() &&800 std::prev(MI.getIterator())->isEHLabel()) {801 AfterSet.insert(&*std::prev(MI.getIterator()));802 ThrowingCall = &*std::prev(MI.getIterator());803 }804 break;805 }806 }807 }808 }809 810 // Local expression tree should go after the TRY_TABLE.811 // For BLOCK placement, we start the search from the previous instruction of a812 // BB's terminator, but in TRY_TABLE's case, we should start from the previous813 // instruction of a call that can throw, or a EH_LABEL that precedes the call,814 // because the return values of the call's previous instructions can be815 // stackified and consumed by the throwing call.816 auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall)817 : Header->getFirstTerminator();818 for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) {819 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())820 continue;821 if (WebAssembly::isChild(*std::prev(I), MFI))822 AfterSet.insert(&*std::prev(I));823 else824 break;825 }826 827 // Add the TRY_TABLE and a BLOCK for the catch destination. We currently828 // generate only one CATCH clause for a TRY_TABLE, so we need one BLOCK for829 // its destination.830 //831 // Header:832 // block833 // try_table (catch ... $MBB)834 // ...835 //836 // MBB:837 // end_try_table838 // end_block ;; destination of (catch ...)839 // ... catch handler body ...840 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);841 MachineInstrBuilder BlockMIB =842 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),843 TII.get(WebAssembly::BLOCK));844 auto *Block = BlockMIB.getInstr();845 MachineInstrBuilder TryTableMIB =846 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),847 TII.get(WebAssembly::TRY_TABLE))848 .addImm(int64_t(WebAssembly::BlockType::Void))849 .addImm(1); // # of catch clauses850 auto *TryTable = TryTableMIB.getInstr();851 852 // Add a CATCH_*** clause to the TRY_TABLE. These are pseudo instructions853 // following the destination END_BLOCK to simulate block return values,854 // because we currently don't support them.855 const auto &TLI =856 *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();857 WebAssembly::BlockType PtrTy =858 TLI.getPointerTy(MF.getDataLayout()) == MVT::i32859 ? WebAssembly::BlockType::I32860 : WebAssembly::BlockType::I64;861 auto *Catch = WebAssembly::findCatch(&MBB);862 switch (Catch->getOpcode()) {863 case WebAssembly::CATCH:864 // CATCH's destination block's return type is the extracted value type,865 // which is currently the thrown value's pointer type for all supported866 // tags.867 BlockMIB.addImm(int64_t(PtrTy));868 TryTableMIB.addImm(wasm::WASM_OPCODE_CATCH);869 for (const auto &Use : Catch->uses()) {870 // The only use operand a CATCH can have is the tag symbol.871 TryTableMIB.addExternalSymbol(Use.getSymbolName());872 break;873 }874 TryTableMIB.addMBB(&MBB);875 break;876 case WebAssembly::CATCH_REF:877 // CATCH_REF's destination block's return type is the extracted value type878 // followed by an exnref, which is (i32, exnref) in our case. We assign the879 // actual multiavlue signature in MCInstLower. MO_CATCH_BLOCK_SIG signals880 // that this operand is used for catch_ref's multivalue destination.881 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Multivalue));882 Block->getOperand(0).setTargetFlags(WebAssemblyII::MO_CATCH_BLOCK_SIG);883 TryTableMIB.addImm(wasm::WASM_OPCODE_CATCH_REF);884 for (const auto &Use : Catch->uses()) {885 TryTableMIB.addExternalSymbol(Use.getSymbolName());886 break;887 }888 TryTableMIB.addMBB(&MBB);889 break;890 case WebAssembly::CATCH_ALL:891 // CATCH_ALL's destination block's return type is void.892 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Void));893 TryTableMIB.addImm(wasm::WASM_OPCODE_CATCH_ALL);894 TryTableMIB.addMBB(&MBB);895 break;896 case WebAssembly::CATCH_ALL_REF:897 // CATCH_ALL_REF's destination block's return type is exnref.898 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Exnref));899 TryTableMIB.addImm(wasm::WASM_OPCODE_CATCH_ALL_REF);900 TryTableMIB.addMBB(&MBB);901 break;902 }903 904 // Decide where in MBB to put the END_TRY_TABLE, and the END_BLOCK for the905 // CATCH destination.906 BeforeSet.clear();907 AfterSet.clear();908 for (const auto &MI : MBB) {909#ifndef NDEBUG910 // END_TRY_TABLE should precede existing LOOP markers.911 if (MI.getOpcode() == WebAssembly::LOOP)912 AfterSet.insert(&MI);913#endif914 915 // If there is a previously placed END_LOOP marker and the header of the916 // loop is above this try_table's header, the END_LOOP should be placed917 // after the END_TRY_TABLE, because the loop contains this block. Otherwise918 // the END_LOOP should be placed before the END_TRY_TABLE.919 if (MI.getOpcode() == WebAssembly::END_LOOP) {920 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())921 BeforeSet.insert(&MI);922#ifndef NDEBUG923 else924 AfterSet.insert(&MI);925#endif926 }927 928#ifndef NDEBUG929 // CATCH, CATCH_REF, CATCH_ALL, and CATCH_ALL_REF are pseudo-instructions930 // that simulate the block return value, so they should be placed after the931 // END_TRY_TABLE.932 if (WebAssembly::isCatch(MI.getOpcode()))933 AfterSet.insert(&MI);934#endif935 }936 937 // Mark the end of the TRY_TABLE and the BLOCK.938 InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);939 MachineInstr *EndTryTable =940 BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),941 TII.get(WebAssembly::END_TRY_TABLE));942 registerTryScope(TryTable, EndTryTable, &MBB);943 MachineInstr *EndBlock =944 BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),945 TII.get(WebAssembly::END_BLOCK));946 registerScope(Block, EndBlock);947 948 // Track the farthest-spanning scope that ends at this point.949 // Unlike the end_try, even if we don't put a end marker at the end of catch950 // block, we still have to create two mappings: (BB with 'end_try_table' -> BB951 // with 'try_table') and (BB after the (conceptual) catch block -> BB with952 // 'try_table').953 //954 // This is what can happen if we don't create the latter mapping:955 //956 // Suppoe in the legacy EH we have this code:957 // try958 // try959 // code1960 // catch (a)961 // end_try962 // code2963 // catch (b)964 // end_try965 //966 // If we don't create the latter mapping, try_table markers would be placed967 // like this:968 // try_table969 // code1970 // end_try_table (a)971 // try_table972 // code2973 // end_try_table (b)974 //975 // This does not reflect the original structure, and more important problem976 // is, in case 'code1' has an unwind mismatch and should unwind to977 // 'end_try_table (b)' rather than 'end_try_table (a)', we don't have a way to978 // make it jump after 'end_try_table (b)' without creating another block. So979 // even if we don't place 'end_try' marker at the end of 'catch' block980 // anymore, we create ScopeTops mapping the same way as the legacy exception,981 // so the resulting code will look like:982 // try_table983 // try_table984 // code1985 // end_try_table (a)986 // code2987 // end_try_table (b)988 for (auto *End : {&MBB, Cont})989 updateScopeTops(Header, End);990}991 992void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {993 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();994 995 // When there is an unconditional branch right before a catch instruction and996 // it branches to the end of end_try marker, we don't need the branch, because997 // if there is no exception, the control flow transfers to that point anyway.998 // bb0:999 // try1000 // ...1001 // br bb2 <- Not necessary1002 // bb1 (ehpad):1003 // catch1004 // ...1005 // bb2: <- Continuation BB1006 // end1007 //1008 // A more involved case: When the BB where 'end' is located is an another EH1009 // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example,1010 // bb0:1011 // try1012 // try1013 // ...1014 // br bb3 <- Not necessary1015 // bb1 (ehpad):1016 // catch1017 // bb2 (ehpad):1018 // end1019 // catch1020 // ...1021 // bb3: <- Continuation BB1022 // end1023 //1024 // When the EH pad at hand is bb1, its matching end_try is in bb2. But it is1025 // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the1026 // code can be deleted. This is why we run 'while' until 'Cont' is not an EH1027 // pad.1028 for (auto &MBB : MF) {1029 if (!MBB.isEHPad())1030 continue;1031 1032 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;1033 SmallVector<MachineOperand, 4> Cond;1034 MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();1035 1036 MachineBasicBlock *Cont = &MBB;1037 while (Cont->isEHPad()) {1038 MachineInstr *Try = EHPadToTry[Cont];1039 MachineInstr *EndTry = BeginToEnd[Try];1040 // We started from an EH pad, so the end marker cannot be a delegate1041 assert(EndTry->getOpcode() != WebAssembly::DELEGATE);1042 Cont = EndTry->getParent();1043 }1044 1045 bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);1046 // This condition means either1047 // 1. This BB ends with a single unconditional branch whose destinaion is1048 // Cont.1049 // 2. This BB ends with a conditional branch followed by an unconditional1050 // branch, and the unconditional branch's destination is Cont.1051 // In both cases, we want to remove the last (= unconditional) branch.1052 if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||1053 (!Cond.empty() && FBB && FBB == Cont))) {1054 bool ErasedUncondBr = false;1055 (void)ErasedUncondBr;1056 for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin();1057 I != E; --I) {1058 auto PrevI = std::prev(I);1059 if (PrevI->isTerminator()) {1060 assert(PrevI->getOpcode() == WebAssembly::BR);1061 PrevI->eraseFromParent();1062 ErasedUncondBr = true;1063 break;1064 }1065 }1066 assert(ErasedUncondBr && "Unconditional branch not erased!");1067 }1068 }1069 1070 // When there are block / end_block markers that overlap with try / end_try1071 // markers, and the block and try markers' return types are the same, the1072 // block /end_block markers are not necessary, because try / end_try markers1073 // also can serve as boundaries for branches.1074 // block <- Not necessary1075 // try1076 // ...1077 // catch1078 // ...1079 // end1080 // end <- Not necessary1081 SmallVector<MachineInstr *, 32> ToDelete;1082 for (auto &MBB : MF) {1083 for (auto &MI : MBB) {1084 if (MI.getOpcode() != WebAssembly::TRY)1085 continue;1086 MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];1087 if (EndTry->getOpcode() == WebAssembly::DELEGATE)1088 continue;1089 1090 MachineBasicBlock *TryBB = Try->getParent();1091 MachineBasicBlock *Cont = EndTry->getParent();1092 int64_t RetType = Try->getOperand(0).getImm();1093 for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());1094 B != TryBB->begin() && E != Cont->end() &&1095 std::prev(B)->getOpcode() == WebAssembly::BLOCK &&1096 E->getOpcode() == WebAssembly::END_BLOCK &&1097 std::prev(B)->getOperand(0).getImm() == RetType;1098 --B, ++E) {1099 ToDelete.push_back(&*std::prev(B));1100 ToDelete.push_back(&*E);1101 }1102 }1103 }1104 for (auto *MI : ToDelete) {1105 if (MI->getOpcode() == WebAssembly::BLOCK)1106 unregisterScope(MI);1107 MI->eraseFromParent();1108 }1109}1110 1111// When MBB is split into MBB and Split, we should unstackify defs in MBB that1112// have their uses in Split.1113static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB,1114 MachineBasicBlock &Split) {1115 MachineFunction &MF = *MBB.getParent();1116 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();1117 auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();1118 auto &MRI = MF.getRegInfo();1119 1120 for (auto &MI : Split) {1121 for (auto &MO : MI.explicit_uses()) {1122 if (!MO.isReg() || MO.getReg().isPhysical())1123 continue;1124 if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg()))1125 if (Def->getParent() == &MBB)1126 MFI.unstackifyVReg(MO.getReg());1127 }1128 }1129 1130 // In RegStackify, when a register definition is used multiple times,1131 // Reg = INST ...1132 // INST ..., Reg, ...1133 // INST ..., Reg, ...1134 // INST ..., Reg, ...1135 //1136 // we introduce a TEE, which has the following form:1137 // DefReg = INST ...1138 // TeeReg, Reg = TEE_... DefReg1139 // INST ..., TeeReg, ...1140 // INST ..., Reg, ...1141 // INST ..., Reg, ...1142 // with DefReg and TeeReg stackified but Reg not stackified.1143 //1144 // But the invariant that TeeReg should be stackified can be violated while we1145 // unstackify registers in the split BB above. In this case, we convert TEEs1146 // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals.1147 // DefReg = INST ...1148 // TeeReg = COPY DefReg1149 // Reg = COPY DefReg1150 // INST ..., TeeReg, ...1151 // INST ..., Reg, ...1152 // INST ..., Reg, ...1153 for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) {1154 if (!WebAssembly::isTee(MI.getOpcode()))1155 continue;1156 Register TeeReg = MI.getOperand(0).getReg();1157 Register Reg = MI.getOperand(1).getReg();1158 Register DefReg = MI.getOperand(2).getReg();1159 if (!MFI.isVRegStackified(TeeReg)) {1160 // Now we are not using TEE anymore, so unstackify DefReg too1161 MFI.unstackifyVReg(DefReg);1162 unsigned CopyOpc =1163 WebAssembly::getCopyOpcodeForRegClass(MRI.getRegClass(DefReg));1164 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg)1165 .addReg(DefReg);1166 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg);1167 MI.eraseFromParent();1168 }1169 }1170}1171 1172// Wrap the given range of instructions with a try-delegate that targets1173// 'UnwindDest'. RangeBegin and RangeEnd are inclusive.1174void WebAssemblyCFGStackify::addNestedTryDelegate(1175 MachineInstr *RangeBegin, MachineInstr *RangeEnd,1176 MachineBasicBlock *UnwindDest) {1177 auto *BeginBB = RangeBegin->getParent();1178 auto *EndBB = RangeEnd->getParent();1179 MachineFunction &MF = *BeginBB->getParent();1180 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();1181 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();1182 1183 // Local expression tree before the first call of this range should go1184 // after the nested TRY.1185 SmallPtrSet<const MachineInstr *, 4> AfterSet;1186 AfterSet.insert(RangeBegin);1187 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();1188 I != E; --I) {1189 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())1190 continue;1191 if (WebAssembly::isChild(*std::prev(I), MFI))1192 AfterSet.insert(&*std::prev(I));1193 else1194 break;1195 }1196 1197 // Create the nested try instruction.1198 auto TryPos = getLatestInsertPos(1199 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);1200 MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(),1201 TII.get(WebAssembly::TRY))1202 .addImm(int64_t(WebAssembly::BlockType::Void));1203 1204 // Create a BB to insert the 'delegate' instruction.1205 MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock();1206 // If the destination of 'delegate' is not the caller, adds the destination to1207 // the BB's successors.1208 if (UnwindDest != FakeCallerBB)1209 DelegateBB->addSuccessor(UnwindDest);1210 1211 auto SplitPos = std::next(RangeEnd->getIterator());1212 if (SplitPos == EndBB->end()) {1213 // If the range's end instruction is at the end of the BB, insert the new1214 // delegate BB after the current BB.1215 MF.insert(std::next(EndBB->getIterator()), DelegateBB);1216 EndBB->addSuccessor(DelegateBB);1217 1218 } else {1219 // When the split pos is in the middle of a BB, we split the BB into two and1220 // put the 'delegate' BB in between. We normally create a split BB and make1221 // it a successor of the original BB (CatchAfterSplit == false), but in case1222 // the BB is an EH pad and there is a 'catch' after the split pos1223 // (CatchAfterSplit == true), we should preserve the BB's property,1224 // including that it is an EH pad, in the later part of the BB, where the1225 // 'catch' is.1226 bool CatchAfterSplit = false;1227 if (EndBB->isEHPad()) {1228 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();1229 I != E; ++I) {1230 if (WebAssembly::isCatch(I->getOpcode())) {1231 CatchAfterSplit = true;1232 break;1233 }1234 }1235 }1236 1237 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;1238 if (!CatchAfterSplit) {1239 // If the range's end instruction is in the middle of the BB, we split the1240 // BB into two and insert the delegate BB in between.1241 // - Before:1242 // bb:1243 // range_end1244 // other_insts1245 //1246 // - After:1247 // pre_bb: (previous 'bb')1248 // range_end1249 // delegate_bb: (new)1250 // delegate1251 // post_bb: (new)1252 // other_insts1253 PreBB = EndBB;1254 PostBB = MF.CreateMachineBasicBlock();1255 MF.insert(std::next(PreBB->getIterator()), PostBB);1256 MF.insert(std::next(PreBB->getIterator()), DelegateBB);1257 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());1258 PostBB->transferSuccessors(PreBB);1259 } else {1260 // - Before:1261 // ehpad:1262 // range_end1263 // catch1264 // ...1265 //1266 // - After:1267 // pre_bb: (new)1268 // range_end1269 // delegate_bb: (new)1270 // delegate1271 // post_bb: (previous 'ehpad')1272 // catch1273 // ...1274 assert(EndBB->isEHPad());1275 PreBB = MF.CreateMachineBasicBlock();1276 PostBB = EndBB;1277 MF.insert(PostBB->getIterator(), PreBB);1278 MF.insert(PostBB->getIterator(), DelegateBB);1279 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);1280 // We don't need to transfer predecessors of the EH pad to 'PreBB',1281 // because an EH pad's predecessors are all through unwind edges and they1282 // should still unwind to the EH pad, not PreBB.1283 }1284 unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);1285 PreBB->addSuccessor(DelegateBB);1286 PreBB->addSuccessor(PostBB);1287 }1288 1289 // Add a 'delegate' instruction in the delegate BB created above.1290 MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(),1291 TII.get(WebAssembly::DELEGATE))1292 .addMBB(UnwindDest);1293 registerTryScope(Try, Delegate, nullptr);1294}1295 1296// Given an unwind destination, return a trampoline BB. A trampoline BB is a1297// destination of a nested try_table inserted to fix an unwind mismatch. It1298// contains an end_block, which is the target of the try_table, and a throw_ref,1299// to rethrow the exception to the right try_table.1300// try_table (catch ... )1301// block exnref1302// ...1303// try_table (catch_all_ref N)1304// some code1305// end_try_table1306// ...1307// unreachable1308// end_block ;; Trampoline BB1309// throw_ref1310// end_try_table1311MachineBasicBlock *1312WebAssemblyCFGStackify::getTrampolineBlock(MachineBasicBlock *UnwindDest) {1313 // We need one trampoline BB per unwind destination, even though there are1314 // multiple try_tables target the same unwind destination. If we have already1315 // created one for the given UnwindDest, return it.1316 auto It = UnwindDestToTrampoline.find(UnwindDest);1317 if (It != UnwindDestToTrampoline.end())1318 return It->second;1319 1320 auto &MF = *UnwindDest->getParent();1321 auto &MRI = MF.getRegInfo();1322 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();1323 1324 MachineInstr *Block = nullptr;1325 MachineBasicBlock *TrampolineBB = nullptr;1326 DebugLoc EndDebugLoc;1327 1328 if (UnwindDest == getFakeCallerBlock(MF)) {1329 // If the unwind destination is the caller, create a caller-dedicated1330 // trampoline BB at the end of the function and wrap the whole function with1331 // a block.1332 auto BeginPos = MF.begin()->begin();1333 while (WebAssembly::isArgument(BeginPos->getOpcode()))1334 BeginPos++;1335 Block = BuildMI(*MF.begin(), BeginPos, MF.begin()->begin()->getDebugLoc(),1336 TII.get(WebAssembly::BLOCK))1337 .addImm(int64_t(WebAssembly::BlockType::Exnref));1338 TrampolineBB = getCallerTrampolineBlock(MF);1339 MachineBasicBlock *PrevBB = &*std::prev(CallerTrampolineBB->getIterator());1340 EndDebugLoc = PrevBB->findPrevDebugLoc(PrevBB->end());1341 } else {1342 // If the unwind destination is another EH pad, create a trampoline BB for1343 // the unwind dest and insert a block instruction right after the target1344 // try_table.1345 auto *TargetBeginTry = EHPadToTry[UnwindDest];1346 auto *TargetEndTry = BeginToEnd[TargetBeginTry];1347 auto *TargetBeginBB = TargetBeginTry->getParent();1348 auto *TargetEndBB = TargetEndTry->getParent();1349 1350 Block = BuildMI(*TargetBeginBB, std::next(TargetBeginTry->getIterator()),1351 TargetBeginTry->getDebugLoc(), TII.get(WebAssembly::BLOCK))1352 .addImm(int64_t(WebAssembly::BlockType::Exnref));1353 TrampolineBB = MF.CreateMachineBasicBlock();1354 EndDebugLoc = TargetEndTry->getDebugLoc();1355 MF.insert(TargetEndBB->getIterator(), TrampolineBB);1356 TrampolineBB->addSuccessor(UnwindDest);1357 }1358 1359 // Insert an end_block, catch_all_ref (pseudo instruction), and throw_ref1360 // instructions in the trampoline BB.1361 MachineInstr *EndBlock =1362 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::END_BLOCK));1363 auto ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);1364 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::CATCH_ALL_REF))1365 .addDef(ExnReg);1366 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::THROW_REF))1367 .addReg(ExnReg);1368 1369 // The trampoline BB's return type is exnref because it is a target of1370 // catch_all_ref. But the body type of the block we just created is not. We1371 // add an 'unreachable' right before the 'end_block' to make the code valid.1372 MachineBasicBlock *TrampolineLayoutPred = TrampolineBB->getPrevNode();1373 BuildMI(TrampolineLayoutPred, TrampolineLayoutPred->findBranchDebugLoc(),1374 TII.get(WebAssembly::UNREACHABLE));1375 1376 registerScope(Block, EndBlock);1377 UnwindDestToTrampoline[UnwindDest] = TrampolineBB;1378 return TrampolineBB;1379}1380 1381// Wrap the given range of instructions with a try_table-end_try_table that1382// targets 'UnwindDest'. RangeBegin and RangeEnd are inclusive.1383void WebAssemblyCFGStackify::addNestedTryTable(MachineInstr *RangeBegin,1384 MachineInstr *RangeEnd,1385 MachineBasicBlock *UnwindDest) {1386 auto *BeginBB = RangeBegin->getParent();1387 auto *EndBB = RangeEnd->getParent();1388 1389 MachineFunction &MF = *BeginBB->getParent();1390 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();1391 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();1392 1393 // Get the trampoline BB that the new try_table will unwind to.1394 auto *TrampolineBB = getTrampolineBlock(UnwindDest);1395 1396 // Local expression tree before the first call of this range should go1397 // after the nested TRY_TABLE.1398 SmallPtrSet<const MachineInstr *, 4> AfterSet;1399 AfterSet.insert(RangeBegin);1400 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();1401 I != E; --I) {1402 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())1403 continue;1404 if (WebAssembly::isChild(*std::prev(I), MFI))1405 AfterSet.insert(&*std::prev(I));1406 else1407 break;1408 }1409 1410 // Create the nested try_table instruction.1411 auto TryTablePos = getLatestInsertPos(1412 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);1413 MachineInstr *TryTable =1414 BuildMI(*BeginBB, TryTablePos, RangeBegin->getDebugLoc(),1415 TII.get(WebAssembly::TRY_TABLE))1416 .addImm(int64_t(WebAssembly::BlockType::Void))1417 .addImm(1) // # of catch clauses1418 .addImm(wasm::WASM_OPCODE_CATCH_ALL_REF)1419 .addMBB(TrampolineBB);1420 1421 // Create a BB to insert the 'end_try_table' instruction.1422 MachineBasicBlock *EndTryTableBB = MF.CreateMachineBasicBlock();1423 EndTryTableBB->addSuccessor(TrampolineBB);1424 1425 auto SplitPos = std::next(RangeEnd->getIterator());1426 if (SplitPos == EndBB->end()) {1427 // If the range's end instruction is at the end of the BB, insert the new1428 // end_try_table BB after the current BB.1429 MF.insert(std::next(EndBB->getIterator()), EndTryTableBB);1430 EndBB->addSuccessor(EndTryTableBB);1431 1432 } else {1433 // When the split pos is in the middle of a BB, we split the BB into two and1434 // put the 'end_try_table' BB in between. We normally create a split BB and1435 // make it a successor of the original BB (CatchAfterSplit == false), but in1436 // case the BB is an EH pad and there is a 'catch' after split pos1437 // (CatchAfterSplit == true), we should preserve the BB's property,1438 // including that it is an EH pad, in the later part of the BB, where the1439 // 'catch' is.1440 bool CatchAfterSplit = false;1441 if (EndBB->isEHPad()) {1442 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();1443 I != E; ++I) {1444 if (WebAssembly::isCatch(I->getOpcode())) {1445 CatchAfterSplit = true;1446 break;1447 }1448 }1449 }1450 1451 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;1452 if (!CatchAfterSplit) {1453 // If the range's end instruction is in the middle of the BB, we split the1454 // BB into two and insert the end_try_table BB in between.1455 // - Before:1456 // bb:1457 // range_end1458 // other_insts1459 //1460 // - After:1461 // pre_bb: (previous 'bb')1462 // range_end1463 // end_try_table_bb: (new)1464 // end_try_table1465 // post_bb: (new)1466 // other_insts1467 PreBB = EndBB;1468 PostBB = MF.CreateMachineBasicBlock();1469 MF.insert(std::next(PreBB->getIterator()), PostBB);1470 MF.insert(std::next(PreBB->getIterator()), EndTryTableBB);1471 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());1472 PostBB->transferSuccessors(PreBB);1473 } else {1474 // - Before:1475 // ehpad:1476 // range_end1477 // catch1478 // ...1479 //1480 // - After:1481 // pre_bb: (new)1482 // range_end1483 // end_try_table_bb: (new)1484 // end_try_table1485 // post_bb: (previous 'ehpad')1486 // catch1487 // ...1488 assert(EndBB->isEHPad());1489 PreBB = MF.CreateMachineBasicBlock();1490 PostBB = EndBB;1491 MF.insert(PostBB->getIterator(), PreBB);1492 MF.insert(PostBB->getIterator(), EndTryTableBB);1493 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);1494 // We don't need to transfer predecessors of the EH pad to 'PreBB',1495 // because an EH pad's predecessors are all through unwind edges and they1496 // should still unwind to the EH pad, not PreBB.1497 }1498 unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);1499 PreBB->addSuccessor(EndTryTableBB);1500 PreBB->addSuccessor(PostBB);1501 }1502 1503 // Add a 'end_try_table' instruction in the EndTryTable BB created above.1504 MachineInstr *EndTryTable = BuildMI(EndTryTableBB, RangeEnd->getDebugLoc(),1505 TII.get(WebAssembly::END_TRY_TABLE));1506 registerTryScope(TryTable, EndTryTable, nullptr);1507}1508 1509// In the standard (exnref) EH, we fix unwind mismatches by adding a new1510// block~end_block inside of the unwind destination try_table~end_try_table:1511// try_table ...1512// block exnref ;; (new)1513// ...1514// try_table (catch_all_ref N) ;; (new) to trampoline BB1515// code1516// end_try_table ;; (new)1517// ...1518// end_block ;; (new) trampoline BB1519// throw_ref ;; (new)1520// end_try_table1521//1522// To do this, we will create a new BB that will contain the new 'end_block' and1523// 'throw_ref' and insert it before the 'end_try_table' BB.1524//1525// But there are cases when there are 'end_loop'(s) before the 'end_try_table'1526// in the same BB. (There can't be 'end_block' before 'end_try_table' in the1527// same BB because EH pads can't be directly branched to.) Then after fixing1528// unwind mismatches this will create the mismatching markers like below:1529// bb0:1530// try_table1531// block exnref1532// ...1533// loop1534// ...1535// new_bb:1536// end_block1537// end_try_table_bb:1538// end_loop1539// end_try_table1540//1541// So if an end_try_table BB has an end_loop before the end_try_table, we split1542// the BB with the end_loop as a separate BB before the end_try_table BB, so1543// that after we fix the unwind mismatch, the code will be like:1544// bb0:1545// try_table1546// block exnref1547// ...1548// loop1549// ...1550// end_loop_bb:1551// end_loop1552// new_bb:1553// end_block1554// end_try_table_bb:1555// end_try_table1556static void splitEndLoopBB(MachineBasicBlock *EndTryTableBB) {1557 auto &MF = *EndTryTableBB->getParent();1558 MachineInstr *EndTryTable = nullptr, *EndLoop = nullptr;1559 for (auto &MI : reverse(*EndTryTableBB)) {1560 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE) {1561 EndTryTable = &MI;1562 continue;1563 }1564 if (EndTryTable && MI.getOpcode() == WebAssembly::END_LOOP) {1565 EndLoop = &MI;1566 break;1567 }1568 }1569 if (!EndLoop)1570 return;1571 1572 auto *EndLoopBB = MF.CreateMachineBasicBlock();1573 MF.insert(EndTryTableBB->getIterator(), EndLoopBB);1574 auto SplitPos = std::next(EndLoop->getIterator());1575 EndLoopBB->splice(EndLoopBB->end(), EndTryTableBB, EndTryTableBB->begin(),1576 SplitPos);1577 EndLoopBB->addSuccessor(EndTryTableBB);1578}1579 1580bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {1581 // This function is used for both the legacy EH and the standard (exnref) EH,1582 // and the reason we have unwind mismatches is the same for the both of them,1583 // but the code examples in the comments are going to be different. To make1584 // the description less confusing, we write the basically same comments twice,1585 // once for the legacy EH and the standard EH.1586 //1587 // -- Legacy EH --------------------------------------------------------------1588 //1589 // Linearizing the control flow by placing TRY / END_TRY markers can create1590 // mismatches in unwind destinations for throwing instructions, such as calls.1591 //1592 // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate'1593 // instruction delegates an exception to an outer 'catch'. It can target not1594 // only 'catch' but all block-like structures including another 'delegate',1595 // but with slightly different semantics than branches. When it targets a1596 // 'catch', it will delegate the exception to that catch. It is being1597 // discussed how to define the semantics when 'delegate''s target is a non-try1598 // block: it will either be a validation failure or it will target the next1599 // outer try-catch. But anyway our LLVM backend currently does not generate1600 // such code. The example below illustrates where the 'delegate' instruction1601 // in the middle will delegate the exception to, depending on the value of N.1602 // try1603 // try1604 // block1605 // try1606 // try1607 // call @foo1608 // delegate N ;; Where will this delegate to?1609 // catch ;; N == 01610 // end1611 // end ;; N == 1 (invalid; will not be generated)1612 // delegate ;; N == 21613 // catch ;; N == 31614 // end1615 // ;; N == 4 (to caller)1616 //1617 // 1. When an instruction may throw, but the EH pad it will unwind to can be1618 // different from the original CFG.1619 //1620 // Example: we have the following CFG:1621 // bb0:1622 // call @foo ; if it throws, unwind to bb21623 // bb1:1624 // call @bar ; if it throws, unwind to bb31625 // bb2 (ehpad):1626 // catch1627 // ...1628 // bb3 (ehpad)1629 // catch1630 // ...1631 //1632 // And the CFG is sorted in this order. Then after placing TRY markers, it1633 // will look like: (BB markers are omitted)1634 // try1635 // try1636 // call @foo1637 // call @bar ;; if it throws, unwind to bb31638 // catch ;; ehpad (bb2)1639 // ...1640 // end_try1641 // catch ;; ehpad (bb3)1642 // ...1643 // end_try1644 //1645 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is1646 // supposed to end up. We solve this problem by wrapping the mismatching call1647 // with an inner try-delegate that rethrows the exception to the right1648 // 'catch'.1649 //1650 // try1651 // try1652 // call @foo1653 // try ;; (new)1654 // call @bar1655 // delegate 1 (bb3) ;; (new)1656 // catch ;; ehpad (bb2)1657 // ...1658 // end_try1659 // catch ;; ehpad (bb3)1660 // ...1661 // end_try1662 //1663 // ---1664 // 2. The same as 1, but in this case an instruction unwinds to a caller1665 // function and not another EH pad.1666 //1667 // Example: we have the following CFG:1668 // bb0:1669 // call @foo ; if it throws, unwind to bb21670 // bb1:1671 // call @bar ; if it throws, unwind to caller1672 // bb2 (ehpad):1673 // catch1674 // ...1675 //1676 // And the CFG is sorted in this order. Then after placing TRY markers, it1677 // will look like:1678 // try1679 // call @foo1680 // call @bar ;; if it throws, unwind to caller1681 // catch ;; ehpad (bb2)1682 // ...1683 // end_try1684 //1685 // Now if bar() throws, it is going to end up in bb2, when it is supposed1686 // throw up to the caller. We solve this problem in the same way, but in this1687 // case 'delegate's immediate argument is the number of block depths + 1,1688 // which means it rethrows to the caller.1689 // try1690 // call @foo1691 // try ;; (new)1692 // call @bar1693 // delegate 1 (caller) ;; (new)1694 // catch ;; ehpad (bb2)1695 // ...1696 // end_try1697 //1698 // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the1699 // caller, it will take a fake BB generated by getFakeCallerBlock(), which1700 // will be converted to a correct immediate argument later.1701 //1702 // In case there are multiple calls in a BB that may throw to the caller, they1703 // can be wrapped together in one nested try-delegate scope. (In 1, this1704 // couldn't happen, because may-throwing instruction there had an unwind1705 // destination, i.e., it was an invoke before, and there could be only one1706 // invoke within a BB.)1707 //1708 // -- Standard EH ------------------------------------------------------------1709 //1710 // Linearizing the control flow by placing TRY / END_TRY_TABLE markers can1711 // create mismatches in unwind destinations for throwing instructions, such as1712 // calls.1713 //1714 // We use the a nested 'try_table'~'end_try_table' instruction to fix the1715 // unwind mismatches. try_table's catch clauses take an immediate argument1716 // that specifics which block we should branch to.1717 //1718 // 1. When an instruction may throw, but the EH pad it will unwind to can be1719 // different from the original CFG.1720 //1721 // Example: we have the following CFG:1722 // bb0:1723 // call @foo ; if it throws, unwind to bb21724 // bb1:1725 // call @bar ; if it throws, unwind to bb31726 // bb2 (ehpad):1727 // catch1728 // ...1729 // bb3 (ehpad)1730 // catch1731 // ...1732 //1733 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers1734 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:1735 // (BB markers are omitted)1736 // block1737 // try_table (catch ... 0)1738 // block1739 // try_table (catch ... 0)1740 // call @foo1741 // call @bar ;; if it throws, unwind to bb31742 // end_try_table1743 // end_block ;; ehpad (bb2)1744 // ...1745 // end_try_table1746 // end_block ;; ehpad (bb3)1747 // ...1748 //1749 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is1750 // supposed to end up. We solve this problem by wrapping the mismatching call1751 // with an inner try_table~end_try_table that sends the exception to the the1752 // 'trampoline' block, which rethrows, or 'bounces' it to the right1753 // end_try_table:1754 // block1755 // try_table (catch ... 0)1756 // block exnref ;; (new)1757 // block1758 // try_table (catch ... 0)1759 // call @foo1760 // try_table (catch_all_ref 2) ;; (new) to trampoline BB1761 // call @bar1762 // end_try_table ;; (new)1763 // end_try_table1764 // end_block ;; ehpad (bb2)1765 // ...1766 // end_block ;; (new) trampoline BB1767 // throw_ref ;; (new)1768 // end_try_table1769 // end_block ;; ehpad (bb3)1770 //1771 // ---1772 // 2. The same as 1, but in this case an instruction unwinds to a caller1773 // function and not another EH pad.1774 //1775 // Example: we have the following CFG:1776 // bb0:1777 // call @foo ; if it throws, unwind to bb21778 // bb1:1779 // call @bar ; if it throws, unwind to caller1780 // bb2 (ehpad):1781 // catch1782 // ...1783 //1784 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers1785 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:1786 // block1787 // try_table (catch ... 0)1788 // call @foo1789 // call @bar ;; if it throws, unwind to caller1790 // end_try_table1791 // end_block ;; ehpad (bb2)1792 // ...1793 //1794 // Now if bar() throws, it is going to end up in bb2, when it is supposed1795 // throw up to the caller. We solve this problem in the same way, but in this1796 // case 'delegate's immediate argument is the number of block depths + 1,1797 // which means it rethrows to the caller.1798 // block exnref ;; (new)1799 // block1800 // try_table (catch ... 0)1801 // call @foo1802 // try_table (catch_all_ref 2) ;; (new) to trampoline BB1803 // call @bar1804 // end_try_table ;; (new)1805 // end_try_table1806 // end_block ;; ehpad (bb2)1807 // ...1808 // end_block ;; (new) caller trampoline BB1809 // throw_ref ;; (new) throw to the caller1810 //1811 // Before rewriteDepthImmediates, try_table's catch clauses' argument is a1812 // trampoline BB from which we throw_ref the exception to the right1813 // end_try_table. In case of the caller, it will take a new caller-dedicated1814 // trampoline BB generated by getCallerTrampolineBlock(), which throws the1815 // exception to the caller.1816 //1817 // In case there are multiple calls in a BB that may throw to the caller, they1818 // can be wrapped together in one nested try_table-end_try_table scope. (In 1,1819 // this couldn't happen, because may-throwing instruction there had an unwind1820 // destination, i.e., it was an invoke before, and there could be only one1821 // invoke within a BB.)1822 1823 SmallVector<const MachineBasicBlock *, 8> EHPadStack;1824 // Range of intructions to be wrapped in a new nested try~delegate or1825 // try_table~end_try_table. A range exists in a single BB and does not span1826 // multiple BBs.1827 using TryRange = std::pair<MachineInstr *, MachineInstr *>;1828 // In original CFG, <unwind destination BB, a vector of try/try_table ranges>1829 DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges;1830 1831 // Gather possibly throwing calls (i.e., previously invokes) whose current1832 // unwind destination is not the same as the original CFG. (Case 1)1833 1834 for (auto &MBB : reverse(MF)) {1835 bool SeenThrowableInstInBB = false;1836 for (auto &MI : reverse(MBB)) {1837 if (WebAssembly::isTry(MI.getOpcode()))1838 EHPadStack.pop_back();1839 else if (WebAssembly::isCatch(MI.getOpcode()))1840 EHPadStack.push_back(MI.getParent());1841 1842 // In this loop we only gather calls that have an EH pad to unwind. So1843 // there will be at most 1 such call (= invoke) in a BB, so after we've1844 // seen one, we can skip the rest of BB. Also if MBB has no EH pad1845 // successor or MI does not throw, this is not an invoke.1846 if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||1847 !WebAssembly::mayThrow(MI))1848 continue;1849 SeenThrowableInstInBB = true;1850 1851 // If the EH pad on the stack top is where this instruction should unwind1852 // next, we're good.1853 MachineBasicBlock *UnwindDest = nullptr;1854 for (auto *Succ : MBB.successors()) {1855 // Even though semantically a BB can have multiple successors in case an1856 // exception is not caught by a catchpad, the first unwind destination1857 // should appear first in the successor list, based on the calculation1858 // in findUnwindDestinations() in SelectionDAGBuilder.cpp.1859 if (Succ->isEHPad()) {1860 UnwindDest = Succ;1861 break;1862 }1863 }1864 if (EHPadStack.back() == UnwindDest)1865 continue;1866 1867 // Include EH_LABELs in the range before and after the invoke1868 MachineInstr *RangeBegin = &MI, *RangeEnd = &MI;1869 if (RangeBegin->getIterator() != MBB.begin() &&1870 std::prev(RangeBegin->getIterator())->isEHLabel())1871 RangeBegin = &*std::prev(RangeBegin->getIterator());1872 if (std::next(RangeEnd->getIterator()) != MBB.end() &&1873 std::next(RangeEnd->getIterator())->isEHLabel())1874 RangeEnd = &*std::next(RangeEnd->getIterator());1875 1876 // If not, record the range.1877 UnwindDestToTryRanges[UnwindDest].push_back(1878 TryRange(RangeBegin, RangeEnd));1879 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName()1880 << "\nCall = " << MI1881 << "\nOriginal dest = " << UnwindDest->getName()1882 << " Current dest = " << EHPadStack.back()->getName()1883 << "\n\n");1884 }1885 }1886 1887 assert(EHPadStack.empty());1888 1889 // Gather possibly throwing calls that are supposed to unwind up to the caller1890 // if they throw, but currently unwind to an incorrect destination. Unlike the1891 // loop above, there can be multiple calls within a BB that unwind to the1892 // caller, which we should group together in a range. (Case 2)1893 1894 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive1895 1896 // Record the range.1897 auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) {1898 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(1899 TryRange(RangeBegin, RangeEnd));1900 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "1901 << RangeBegin->getParent()->getName()1902 << "\nRange begin = " << *RangeBegin1903 << "Range end = " << *RangeEnd1904 << "\nOriginal dest = caller Current dest = "1905 << CurrentDest->getName() << "\n\n");1906 RangeBegin = RangeEnd = nullptr; // Reset range pointers1907 };1908 1909 for (auto &MBB : reverse(MF)) {1910 bool SeenThrowableInstInBB = false;1911 for (auto &MI : reverse(MBB)) {1912 bool MayThrow = WebAssembly::mayThrow(MI);1913 1914 // If MBB has an EH pad successor and this is the last instruction that1915 // may throw, this instruction unwinds to the EH pad and not to the1916 // caller.1917 if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB)1918 SeenThrowableInstInBB = true;1919 1920 // We wrap up the current range when we see a marker even if we haven't1921 // finished a BB.1922 else if (RangeEnd && WebAssembly::isMarker(MI.getOpcode()))1923 RecordCallerMismatchRange(EHPadStack.back());1924 1925 // If EHPadStack is empty, that means it correctly unwinds to the caller1926 // if it throws, so we're good. If MI does not throw, we're good too.1927 else if (EHPadStack.empty() || !MayThrow) {1928 }1929 1930 // We found an instruction that unwinds to the caller but currently has an1931 // incorrect unwind destination. Create a new range or increment the1932 // currently existing range.1933 else {1934 if (!RangeEnd)1935 RangeBegin = RangeEnd = &MI;1936 else1937 RangeBegin = &MI;1938 }1939 1940 // Update EHPadStack.1941 if (WebAssembly::isTry(MI.getOpcode()))1942 EHPadStack.pop_back();1943 else if (WebAssembly::isCatch(MI.getOpcode()))1944 EHPadStack.push_back(MI.getParent());1945 }1946 1947 if (RangeEnd)1948 RecordCallerMismatchRange(EHPadStack.back());1949 }1950 1951 assert(EHPadStack.empty());1952 1953 // We don't have any unwind destination mismatches to resolve.1954 if (UnwindDestToTryRanges.empty())1955 return false;1956 1957 // When end_loop is before end_try_table within the same BB in unwind1958 // destinations, we should split the end_loop into another BB.1959 if (!WebAssembly::WasmUseLegacyEH)1960 for (auto &[UnwindDest, _] : UnwindDestToTryRanges) {1961 auto It = EHPadToTry.find(UnwindDest);1962 // If UnwindDest is the fake caller block, it will not be in EHPadToTry1963 // map1964 if (It != EHPadToTry.end()) {1965 auto *TryTable = It->second;1966 auto *EndTryTable = BeginToEnd[TryTable];1967 splitEndLoopBB(EndTryTable->getParent());1968 }1969 }1970 1971 // Now we fix the mismatches by wrapping calls with inner try-delegates.1972 for (auto &P : UnwindDestToTryRanges) {1973 NumCallUnwindMismatches += P.second.size();1974 MachineBasicBlock *UnwindDest = P.first;1975 auto &TryRanges = P.second;1976 1977 for (auto Range : TryRanges) {1978 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;1979 std::tie(RangeBegin, RangeEnd) = Range;1980 auto *MBB = RangeBegin->getParent();1981 1982 // If this BB has an EH pad successor, i.e., ends with an 'invoke', and if1983 // the current range contains the invoke, now we are going to wrap the1984 // invoke with try-delegate or try_table-end_try_table, making the1985 // 'delegate' or 'end_try_table' BB the new successor instead, so remove1986 // the EH pad succesor here. The BB may not have an EH pad successor if1987 // calls in this BB throw to the caller.1988 if (UnwindDest != getFakeCallerBlock(MF)) {1989 MachineBasicBlock *EHPad = nullptr;1990 for (auto *Succ : MBB->successors()) {1991 if (Succ->isEHPad()) {1992 EHPad = Succ;1993 break;1994 }1995 }1996 if (EHPad)1997 MBB->removeSuccessor(EHPad);1998 }1999 2000 if (WebAssembly::WasmUseLegacyEH)2001 addNestedTryDelegate(RangeBegin, RangeEnd, UnwindDest);2002 else2003 addNestedTryTable(RangeBegin, RangeEnd, UnwindDest);2004 }2005 }2006 2007 return true;2008}2009 2010// Returns the single destination of try_table, if there is one. All try_table2011// we generate in this pass has a single destination, i.e., a single catch2012// clause.2013static MachineBasicBlock *getSingleUnwindDest(const MachineInstr *TryTable) {2014 if (TryTable->getOperand(1).getImm() != 1)2015 return nullptr;2016 switch (TryTable->getOperand(2).getImm()) {2017 case wasm::WASM_OPCODE_CATCH:2018 case wasm::WASM_OPCODE_CATCH_REF:2019 return TryTable->getOperand(4).getMBB();2020 case wasm::WASM_OPCODE_CATCH_ALL:2021 case wasm::WASM_OPCODE_CATCH_ALL_REF:2022 return TryTable->getOperand(3).getMBB();2023 default:2024 llvm_unreachable("try_table: Invalid catch clause\n");2025 }2026}2027 2028bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {2029 // This function is used for both the legacy EH and the standard (exnref) EH,2030 // and the reason we have unwind mismatches is the same for the both of them,2031 // but the code examples in the comments are going to be different. To make2032 // the description less confusing, we write the basically same comments twice,2033 // once for the legacy EH and the standard EH.2034 //2035 // -- Legacy EH --------------------------------------------------------------2036 //2037 // There is another kind of unwind destination mismatches besides call unwind2038 // mismatches, which we will call "catch unwind mismatches". See this example2039 // after the marker placement:2040 // try2041 // try2042 // call @foo2043 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)2044 // ...2045 // end_try2046 // catch_all ;; ehpad B2047 // ...2048 // end_try2049 //2050 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'2051 // throws a foreign exception that is not caught by ehpad A, and its next2052 // destination should be the caller. But after control flow linearization,2053 // another EH pad can be placed in between (e.g. ehpad B here), making the2054 // next unwind destination incorrect. In this case, the foreign exception will2055 // instead go to ehpad B and will be caught there instead. In this example the2056 // correct next unwind destination is the caller, but it can be another outer2057 // catch in other cases.2058 //2059 // There is no specific 'call' or 'throw' instruction to wrap with a2060 // try-delegate, so we wrap the whole try-catch-end with a try-delegate and2061 // make it rethrow to the right destination, which is the caller in the2062 // example below:2063 // try2064 // try ;; (new)2065 // try2066 // call @foo2067 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)2068 // ...2069 // end_try2070 // delegate 1 (caller) ;; (new)2071 // catch_all ;; ehpad B2072 // ...2073 // end_try2074 //2075 // The right destination may be another EH pad or the caller. (The example2076 // here shows the case it is the caller.)2077 //2078 // -- Standard EH ------------------------------------------------------------2079 //2080 // There is another kind of unwind destination mismatches besides call unwind2081 // mismatches, which we will call "catch unwind mismatches". See this example2082 // after the marker placement:2083 // block2084 // try_table (catch_all_ref 0)2085 // block2086 // try_table (catch ... 0)2087 // call @foo2088 // end_try_table2089 // end_block ;; ehpad A (next unwind dest: caller)2090 // ...2091 // end_try_table2092 // end_block ;; ehpad B2093 // ...2094 //2095 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'2096 // throws a foreign exception that is not caught by ehpad A, and its next2097 // destination should be the caller. But after control flow linearization,2098 // another EH pad can be placed in between (e.g. ehpad B here), making the2099 // next unwind destination incorrect. In this case, the foreign exception will2100 // instead go to ehpad B and will be caught there instead. In this example the2101 // correct next unwind destination is the caller, but it can be another outer2102 // catch in other cases.2103 //2104 // There is no specific 'call' or 'throw' instruction to wrap with an inner2105 // try_table-end_try_table, so we wrap the whole try_table-end_try_table with2106 // an inner try_table-end_try_table that sends the exception to a trampoline2107 // BB. We rethrow the sent exception using a throw_ref to the right2108 // destination, which is the caller in the example below:2109 // block exnref2110 // block2111 // try_table (catch_all_ref 0)2112 // try_table (catch_all_ref 2) ;; (new) to trampoline2113 // block2114 // try_table (catch ... 0)2115 // call @foo2116 // end_try_table2117 // end_block ;; ehpad A (next unwind dest: caller)2118 // end_try_table ;; (new)2119 // ...2120 // end_try_table2121 // end_block ;; ehpad B2122 // ...2123 // end_block ;; (new) caller trampoline BB2124 // throw_ref ;; (new) throw to the caller2125 //2126 // The right destination may be another EH pad or the caller. (The example2127 // here shows the case it is the caller.)2128 2129 const auto *EHInfo = MF.getWasmEHFuncInfo();2130 assert(EHInfo);2131 SmallVector<const MachineBasicBlock *, 8> EHPadStack;2132 // For EH pads that have catch unwind mismatches, a map of <EH pad, its2133 // correct unwind destination>.2134 DenseMap<MachineBasicBlock *, MachineBasicBlock *> EHPadToUnwindDest;2135 2136 for (auto &MBB : reverse(MF)) {2137 for (auto &MI : reverse(MBB)) {2138 if (MI.getOpcode() == WebAssembly::TRY)2139 EHPadStack.pop_back();2140 else if (MI.getOpcode() == WebAssembly::TRY_TABLE) {2141 // We want to exclude try_tables created in fixCallUnwindMismatches.2142 // Check if the try_table's unwind destination matches the EH pad stack2143 // top. If it is created in fixCallUnwindMismatches, it wouldn't.2144 if (getSingleUnwindDest(&MI) == EHPadStack.back())2145 EHPadStack.pop_back();2146 } else if (MI.getOpcode() == WebAssembly::DELEGATE)2147 EHPadStack.push_back(&MBB);2148 else if (WebAssembly::isCatch(MI.getOpcode())) {2149 auto *EHPad = &MBB;2150 2151 // If the BB has a catch pseudo instruction but is not marked as an EH2152 // pad, it's a trampoline BB we created in fixCallUnwindMismatches. Skip2153 // it.2154 if (!EHPad->isEHPad())2155 continue;2156 2157 // catch_all always catches an exception, so we don't need to do2158 // anything2159 if (WebAssembly::isCatchAll(MI.getOpcode())) {2160 }2161 2162 // This can happen when the unwind dest was removed during the2163 // optimization, e.g. because it was unreachable.2164 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {2165 LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName()2166 << "'s unwind destination does not exist anymore"2167 << "\n\n");2168 }2169 2170 // The EHPad's next unwind destination is the caller, but we incorrectly2171 // unwind to another EH pad.2172 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) {2173 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);2174 LLVM_DEBUG(dbgs()2175 << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()2176 << " Original dest = caller Current dest = "2177 << EHPadStack.back()->getName() << "\n\n");2178 }2179 2180 // The EHPad's next unwind destination is an EH pad, whereas we2181 // incorrectly unwind to another EH pad.2182 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {2183 auto *UnwindDest = EHInfo->getUnwindDest(EHPad);2184 if (EHPadStack.back() != UnwindDest) {2185 EHPadToUnwindDest[EHPad] = UnwindDest;2186 LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "2187 << EHPad->getName() << " Original dest = "2188 << UnwindDest->getName() << " Current dest = "2189 << EHPadStack.back()->getName() << "\n\n");2190 }2191 }2192 2193 EHPadStack.push_back(EHPad);2194 }2195 }2196 }2197 2198 assert(EHPadStack.empty());2199 if (EHPadToUnwindDest.empty())2200 return false;2201 2202 // When end_loop is before end_try_table within the same BB in unwind2203 // destinations, we should split the end_loop into another BB.2204 for (auto &[_, UnwindDest] : EHPadToUnwindDest) {2205 auto It = EHPadToTry.find(UnwindDest);2206 // If UnwindDest is the fake caller block, it will not be in EHPadToTry map2207 if (It != EHPadToTry.end()) {2208 auto *TryTable = It->second;2209 auto *EndTryTable = BeginToEnd[TryTable];2210 splitEndLoopBB(EndTryTable->getParent());2211 }2212 }2213 2214 NumCatchUnwindMismatches += EHPadToUnwindDest.size();2215 SmallPtrSet<MachineBasicBlock *, 4> NewEndTryBBs;2216 2217 for (auto &[EHPad, UnwindDest] : EHPadToUnwindDest) {2218 MachineInstr *Try = EHPadToTry[EHPad];2219 MachineInstr *EndTry = BeginToEnd[Try];2220 if (WebAssembly::WasmUseLegacyEH) {2221 addNestedTryDelegate(Try, EndTry, UnwindDest);2222 NewEndTryBBs.insert(EndTry->getParent());2223 } else {2224 addNestedTryTable(Try, EndTry, UnwindDest);2225 }2226 }2227 2228 if (!WebAssembly::WasmUseLegacyEH)2229 return true;2230 2231 // Adding a try-delegate wrapping an existing try-catch-end can make existing2232 // branch destination BBs invalid. For example,2233 //2234 // - Before:2235 // bb0:2236 // block2237 // br bb32238 // bb1:2239 // try2240 // ...2241 // bb2: (ehpad)2242 // catch2243 // bb3:2244 // end_try2245 // end_block ;; 'br bb3' targets here2246 //2247 // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap2248 // this with a try-delegate. Then this becomes:2249 //2250 // - After:2251 // bb0:2252 // block2253 // br bb3 ;; invalid destination!2254 // bb1:2255 // try ;; (new instruction)2256 // try2257 // ...2258 // bb2: (ehpad)2259 // catch2260 // bb3:2261 // end_try ;; 'br bb3' still incorrectly targets here!2262 // delegate_bb: ;; (new BB)2263 // delegate ;; (new instruction)2264 // split_bb: ;; (new BB)2265 // end_block2266 //2267 // Now 'br bb3' incorrectly branches to an inner scope.2268 //2269 // As we can see in this case, when branches target a BB that has both2270 // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we2271 // have to remap existing branch destinations so that they target not the2272 // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's2273 // in between, so we try to find the next BB with 'end_block' instruction. In2274 // this example, the 'br bb3' instruction should be remapped to 'br split_bb'.2275 for (auto &MBB : MF) {2276 for (auto &MI : MBB) {2277 if (MI.isTerminator()) {2278 for (auto &MO : MI.operands()) {2279 if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) {2280 auto *BrDest = MO.getMBB();2281 bool FoundEndBlock = false;2282 for (; std::next(BrDest->getIterator()) != MF.end();2283 BrDest = BrDest->getNextNode()) {2284 for (const auto &MI : *BrDest) {2285 if (MI.getOpcode() == WebAssembly::END_BLOCK) {2286 FoundEndBlock = true;2287 break;2288 }2289 }2290 if (FoundEndBlock)2291 break;2292 }2293 assert(FoundEndBlock);2294 MO.setMBB(BrDest);2295 }2296 }2297 }2298 }2299 }2300 2301 return true;2302}2303 2304void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {2305 // Renumber BBs and recalculate ScopeTop info because new BBs might have been2306 // created and inserted during fixing unwind mismatches.2307 MF.RenumberBlocks();2308 MDT->updateBlockNumbers();2309 ScopeTops.clear();2310 ScopeTops.resize(MF.getNumBlockIDs());2311 for (auto &MBB : reverse(MF)) {2312 for (auto &MI : reverse(MBB)) {2313 if (ScopeTops[MBB.getNumber()])2314 break;2315 switch (MI.getOpcode()) {2316 case WebAssembly::END_BLOCK:2317 case WebAssembly::END_LOOP:2318 case WebAssembly::END_TRY:2319 case WebAssembly::END_TRY_TABLE:2320 case WebAssembly::DELEGATE:2321 updateScopeTops(EndToBegin[&MI]->getParent(), &MBB);2322 break;2323 case WebAssembly::CATCH_LEGACY:2324 case WebAssembly::CATCH_ALL_LEGACY:2325 updateScopeTops(EHPadToTry[&MBB]->getParent(), &MBB);2326 break;2327 }2328 }2329 }2330}2331 2332/// In normal assembly languages, when the end of a function is unreachable,2333/// because the function ends in an infinite loop or a noreturn call or similar,2334/// it isn't necessary to worry about the function return type at the end of2335/// the function, because it's never reached. However, in WebAssembly, blocks2336/// that end at the function end need to have a return type signature that2337/// matches the function signature, even though it's unreachable. This function2338/// checks for such cases and fixes up the signatures.2339void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {2340 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();2341 2342 if (MFI.getResults().empty())2343 return;2344 2345 // MCInstLower will add the proper types to multivalue signatures based on the2346 // function return type2347 WebAssembly::BlockType RetType =2348 MFI.getResults().size() > 12349 ? WebAssembly::BlockType::Multivalue2350 : WebAssembly::BlockType(2351 WebAssembly::toValType(MFI.getResults().front()));2352 2353 SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist;2354 Worklist.push_back(MF.rbegin()->rbegin());2355 2356 auto Process = [&](MachineBasicBlock::reverse_iterator It) {2357 auto *MBB = It->getParent();2358 while (It != MBB->rend()) {2359 MachineInstr &MI = *It++;2360 if (MI.isPosition() || MI.isDebugInstr())2361 continue;2362 switch (MI.getOpcode()) {2363 case WebAssembly::END_TRY: {2364 // If a 'try''s return type is fixed, both its try body and catch body2365 // should satisfy the return type, so we need to search 'end'2366 // instructions before its corresponding 'catch' too.2367 auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]);2368 assert(EHPad);2369 auto NextIt =2370 std::next(WebAssembly::findCatch(EHPad)->getReverseIterator());2371 if (NextIt != EHPad->rend())2372 Worklist.push_back(NextIt);2373 [[fallthrough]];2374 }2375 case WebAssembly::END_BLOCK:2376 case WebAssembly::END_LOOP:2377 case WebAssembly::END_TRY_TABLE:2378 case WebAssembly::DELEGATE:2379 EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));2380 continue;2381 default:2382 // Something other than an `end`. We're done for this BB.2383 return;2384 }2385 }2386 // We've reached the beginning of a BB. Continue the search in the previous2387 // BB.2388 Worklist.push_back(MBB->getPrevNode()->rbegin());2389 };2390 2391 while (!Worklist.empty())2392 Process(Worklist.pop_back_val());2393}2394 2395// WebAssembly functions end with an end instruction, as if the function body2396// were a block.2397static void appendEndToFunction(MachineFunction &MF,2398 const WebAssemblyInstrInfo &TII) {2399 BuildMI(MF.back(), MF.back().end(),2400 MF.back().findPrevDebugLoc(MF.back().end()),2401 TII.get(WebAssembly::END_FUNCTION));2402}2403 2404// We added block~end_block and try_table~end_try_table markers in2405// placeTryTableMarker. But When catch clause's destination has a return type,2406// as in the case of catch with a concrete tag, catch_ref, and catch_all_ref.2407// For example:2408// block exnref2409// try_table (catch_all_ref 0)2410// ...2411// end_try_table2412// end_block2413// ... use exnref ...2414//2415// This code is not valid because the block's body type is not exnref. So we add2416// an unreachable after the 'end_try_table' to make the code valid here:2417// block exnref2418// try_table (catch_all_ref 0)2419// ...2420// end_try_table2421// unreachable (new)2422// end_block2423//2424// Because 'unreachable' is a terminator we also need to split the BB.2425static void addUnreachableAfterTryTables(MachineFunction &MF,2426 const WebAssemblyInstrInfo &TII) {2427 std::vector<MachineInstr *> EndTryTables;2428 for (auto &MBB : MF)2429 for (auto &MI : MBB)2430 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE)2431 EndTryTables.push_back(&MI);2432 2433 for (auto *EndTryTable : EndTryTables) {2434 auto *MBB = EndTryTable->getParent();2435 auto *NewEndTryTableBB = MF.CreateMachineBasicBlock();2436 MF.insert(MBB->getIterator(), NewEndTryTableBB);2437 auto SplitPos = std::next(EndTryTable->getIterator());2438 NewEndTryTableBB->splice(NewEndTryTableBB->end(), MBB, MBB->begin(),2439 SplitPos);2440 NewEndTryTableBB->addSuccessor(MBB);2441 BuildMI(NewEndTryTableBB, EndTryTable->getDebugLoc(),2442 TII.get(WebAssembly::UNREACHABLE));2443 }2444}2445 2446/// Insert BLOCK/LOOP/TRY/TRY_TABLE markers at appropriate places.2447void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {2448 // We allocate one more than the number of blocks in the function to2449 // accommodate for the possible fake block we may insert at the end.2450 ScopeTops.resize(MF.getNumBlockIDs() + 1);2451 // Place the LOOP for MBB if MBB is the header of a loop.2452 for (auto &MBB : MF)2453 placeLoopMarker(MBB);2454 2455 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();2456 for (auto &MBB : MF) {2457 if (MBB.isEHPad()) {2458 // Place the TRY/TRY_TABLE for MBB if MBB is the EH pad of an exception.2459 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&2460 MF.getFunction().hasPersonalityFn()) {2461 if (WebAssembly::WasmUseLegacyEH)2462 placeTryMarker(MBB);2463 else2464 placeTryTableMarker(MBB);2465 }2466 } else {2467 // Place the BLOCK for MBB if MBB is branched to from above.2468 placeBlockMarker(MBB);2469 }2470 }2471 2472 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&2473 MF.getFunction().hasPersonalityFn()) {2474 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();2475 // Add an 'unreachable' after 'end_try_table's.2476 addUnreachableAfterTryTables(MF, TII);2477 // Fix mismatches in unwind destinations induced by linearizing the code.2478 fixCallUnwindMismatches(MF);2479 fixCatchUnwindMismatches(MF);2480 // addUnreachableAfterTryTables and fixUnwindMismatches create new BBs, so2481 // we need to recalculate ScopeTops.2482 recalculateScopeTops(MF);2483 }2484}2485 2486unsigned WebAssemblyCFGStackify::getBranchDepth(2487 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {2488 unsigned Depth = 0;2489 for (auto X : reverse(Stack)) {2490 if (X.first == MBB)2491 break;2492 ++Depth;2493 }2494 assert(Depth < Stack.size() && "Branch destination should be in scope");2495 return Depth;2496}2497 2498unsigned WebAssemblyCFGStackify::getDelegateDepth(2499 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {2500 if (MBB == FakeCallerBB)2501 return Stack.size();2502 // Delegate's destination is either a catch or a another delegate BB. When the2503 // destination is another delegate, we can compute the argument in the same2504 // way as branches, because the target delegate BB only contains the single2505 // delegate instruction.2506 if (!MBB->isEHPad()) // Target is a delegate BB2507 return getBranchDepth(Stack, MBB);2508 2509 // When the delegate's destination is a catch BB, we need to use its2510 // corresponding try's end_try BB because Stack contains each marker's end BB.2511 // Also we need to check if the end marker instruction matches, because a2512 // single BB can contain multiple end markers, like this:2513 // bb:2514 // END_BLOCK2515 // END_TRY2516 // END_BLOCK2517 // END_TRY2518 // ...2519 //2520 // In case of branches getting the immediate that targets any of these is2521 // fine, but delegate has to exactly target the correct try.2522 unsigned Depth = 0;2523 const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];2524 for (auto X : reverse(Stack)) {2525 if (X.first == EndTry->getParent() && X.second == EndTry)2526 break;2527 ++Depth;2528 }2529 assert(Depth < Stack.size() && "Delegate destination should be in scope");2530 return Depth;2531}2532 2533unsigned WebAssemblyCFGStackify::getRethrowDepth(2534 const SmallVectorImpl<EndMarkerInfo> &Stack,2535 const MachineBasicBlock *EHPadToRethrow) {2536 unsigned Depth = 0;2537 for (auto X : reverse(Stack)) {2538 const MachineInstr *End = X.second;2539 if (End->getOpcode() == WebAssembly::END_TRY) {2540 auto *EHPad = TryToEHPad[EndToBegin[End]];2541 if (EHPadToRethrow == EHPad)2542 break;2543 }2544 ++Depth;2545 }2546 assert(Depth < Stack.size() && "Rethrow destination should be in scope");2547 return Depth;2548}2549 2550void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {2551 // Now rewrite references to basic blocks to be depth immediates.2552 SmallVector<EndMarkerInfo, 8> Stack;2553 2554 auto RewriteOperands = [&](MachineInstr &MI) {2555 // Rewrite MBB operands to be depth immediates.2556 SmallVector<MachineOperand, 4> Ops(MI.operands());2557 while (MI.getNumOperands() > 0)2558 MI.removeOperand(MI.getNumOperands() - 1);2559 for (auto MO : Ops) {2560 if (MO.isMBB()) {2561 if (MI.getOpcode() == WebAssembly::DELEGATE)2562 MO = MachineOperand::CreateImm(getDelegateDepth(Stack, MO.getMBB()));2563 else if (MI.getOpcode() == WebAssembly::RETHROW)2564 MO = MachineOperand::CreateImm(getRethrowDepth(Stack, MO.getMBB()));2565 else2566 MO = MachineOperand::CreateImm(getBranchDepth(Stack, MO.getMBB()));2567 }2568 MI.addOperand(MF, MO);2569 }2570 };2571 2572 for (auto &MBB : reverse(MF)) {2573 for (MachineInstr &MI : llvm::reverse(MBB)) {2574 switch (MI.getOpcode()) {2575 case WebAssembly::BLOCK:2576 case WebAssembly::TRY:2577 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=2578 MBB.getNumber() &&2579 "Block/try/try_table marker should be balanced");2580 Stack.pop_back();2581 break;2582 2583 case WebAssembly::TRY_TABLE:2584 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=2585 MBB.getNumber() &&2586 "Block/try/try_table marker should be balanced");2587 Stack.pop_back();2588 RewriteOperands(MI);2589 break;2590 2591 case WebAssembly::LOOP:2592 assert(Stack.back().first == &MBB && "Loop top should be balanced");2593 Stack.pop_back();2594 break;2595 2596 case WebAssembly::END_BLOCK:2597 case WebAssembly::END_TRY:2598 case WebAssembly::END_TRY_TABLE:2599 Stack.push_back(std::make_pair(&MBB, &MI));2600 break;2601 2602 case WebAssembly::END_LOOP:2603 Stack.push_back(std::make_pair(EndToBegin[&MI]->getParent(), &MI));2604 break;2605 2606 case WebAssembly::DELEGATE:2607 RewriteOperands(MI);2608 Stack.push_back(std::make_pair(&MBB, &MI));2609 break;2610 2611 default:2612 if (MI.isTerminator())2613 RewriteOperands(MI);2614 break;2615 }2616 }2617 }2618 assert(Stack.empty() && "Control flow should be balanced");2619}2620 2621void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) {2622 if (FakeCallerBB)2623 MF.deleteMachineBasicBlock(FakeCallerBB);2624 AppendixBB = FakeCallerBB = CallerTrampolineBB = nullptr;2625}2626 2627void WebAssemblyCFGStackify::releaseMemory() {2628 ScopeTops.clear();2629 BeginToEnd.clear();2630 EndToBegin.clear();2631 TryToEHPad.clear();2632 EHPadToTry.clear();2633 UnwindDestToTrampoline.clear();2634}2635 2636bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {2637 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"2638 "********** Function: "2639 << MF.getName() << '\n');2640 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();2641 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();2642 2643 releaseMemory();2644 2645 // Liveness is not tracked for VALUE_STACK physreg.2646 MF.getRegInfo().invalidateLiveness();2647 2648 // Place the BLOCK/LOOP/TRY/TRY_TABLE markers to indicate the beginnings of2649 // scopes.2650 placeMarkers(MF);2651 2652 // Remove unnecessary instructions possibly introduced by try/end_trys.2653 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&2654 MF.getFunction().hasPersonalityFn() && WebAssembly::WasmUseLegacyEH)2655 removeUnnecessaryInstrs(MF);2656 2657 // Convert MBB operands in terminators to relative depth immediates.2658 rewriteDepthImmediates(MF);2659 2660 // Fix up block/loop/try/try_table signatures at the end of the function to2661 // conform to WebAssembly's rules.2662 fixEndsAtEndOfFunction(MF);2663 2664 // Add an end instruction at the end of the function body.2665 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();2666 appendEndToFunction(MF, TII);2667 2668 cleanupFunctionData(MF);2669 2670 MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();2671 return true;2672}2673