WebAssemblyCFGStackify.cpp revision 344779
1292915Sdim//===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===// 2292915Sdim// 3292915Sdim// The LLVM Compiler Infrastructure 4292915Sdim// 5292915Sdim// This file is distributed under the University of Illinois Open Source 6292915Sdim// License. See LICENSE.TXT for details. 7292915Sdim// 8292915Sdim//===----------------------------------------------------------------------===// 9292915Sdim/// 10292915Sdim/// \file 11341825Sdim/// This file implements a CFG stacking pass. 12292915Sdim/// 13344779Sdim/// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes, 14344779Sdim/// since scope boundaries serve as the labels for WebAssembly's control 15344779Sdim/// transfers. 16292915Sdim/// 17292915Sdim/// This is sufficient to convert arbitrary CFGs into a form that works on 18292915Sdim/// WebAssembly, provided that all loops are single-entry. 19292915Sdim/// 20344779Sdim/// In case we use exceptions, this pass also fixes mismatches in unwind 21344779Sdim/// destinations created during transforming CFG into wasm structured format. 22344779Sdim/// 23292915Sdim//===----------------------------------------------------------------------===// 24292915Sdim 25321369Sdim#include "MCTargetDesc/WebAssemblyMCTargetDesc.h" 26292915Sdim#include "WebAssembly.h" 27344779Sdim#include "WebAssemblyExceptionInfo.h" 28309124Sdim#include "WebAssemblyMachineFunctionInfo.h" 29292915Sdim#include "WebAssemblySubtarget.h" 30314564Sdim#include "WebAssemblyUtilities.h" 31292915Sdim#include "llvm/CodeGen/MachineDominators.h" 32292915Sdim#include "llvm/CodeGen/MachineFunction.h" 33292915Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 34292915Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 35294024Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 36292915Sdim#include "llvm/CodeGen/Passes.h" 37344779Sdim#include "llvm/CodeGen/WasmEHFuncInfo.h" 38344779Sdim#include "llvm/MC/MCAsmInfo.h" 39292915Sdim#include "llvm/Support/Debug.h" 40292915Sdim#include "llvm/Support/raw_ostream.h" 41292915Sdimusing namespace llvm; 42292915Sdim 43292915Sdim#define DEBUG_TYPE "wasm-cfg-stackify" 44292915Sdim 45292915Sdimnamespace { 46292915Sdimclass WebAssemblyCFGStackify final : public MachineFunctionPass { 47314564Sdim StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } 48292915Sdim 49292915Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 50292915Sdim AU.addRequired<MachineDominatorTree>(); 51292915Sdim AU.addRequired<MachineLoopInfo>(); 52344779Sdim AU.addRequired<WebAssemblyExceptionInfo>(); 53292915Sdim MachineFunctionPass::getAnalysisUsage(AU); 54292915Sdim } 55292915Sdim 56292915Sdim bool runOnMachineFunction(MachineFunction &MF) override; 57292915Sdim 58344779Sdim // For each block whose label represents the end of a scope, record the block 59344779Sdim // which holds the beginning of the scope. This will allow us to quickly skip 60344779Sdim // over scoped regions when walking blocks. 61344779Sdim SmallVector<MachineBasicBlock *, 8> ScopeTops; 62344779Sdim 63344779Sdim void placeMarkers(MachineFunction &MF); 64344779Sdim void placeBlockMarker(MachineBasicBlock &MBB); 65344779Sdim void placeLoopMarker(MachineBasicBlock &MBB); 66344779Sdim void placeTryMarker(MachineBasicBlock &MBB); 67344779Sdim void rewriteDepthImmediates(MachineFunction &MF); 68344779Sdim void fixEndsAtEndOfFunction(MachineFunction &MF); 69344779Sdim 70344779Sdim // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY). 71344779Sdim DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd; 72344779Sdim // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY. 73344779Sdim DenseMap<const MachineInstr *, MachineInstr *> EndToBegin; 74344779Sdim // <TRY marker, EH pad> map 75344779Sdim DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad; 76344779Sdim // <EH pad, TRY marker> map 77344779Sdim DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry; 78344779Sdim // <LOOP|TRY marker, Loop/exception bottom BB> map 79344779Sdim DenseMap<const MachineInstr *, MachineBasicBlock *> BeginToBottom; 80344779Sdim 81344779Sdim // Helper functions to register scope information created by marker 82344779Sdim // instructions. 83344779Sdim void registerScope(MachineInstr *Begin, MachineInstr *End); 84344779Sdim void registerTryScope(MachineInstr *Begin, MachineInstr *End, 85344779Sdim MachineBasicBlock *EHPad); 86344779Sdim 87344779Sdim MachineBasicBlock *getBottom(const MachineInstr *Begin); 88344779Sdim 89292915Sdimpublic: 90292915Sdim static char ID; // Pass identification, replacement for typeid 91292915Sdim WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} 92344779Sdim ~WebAssemblyCFGStackify() override { releaseMemory(); } 93344779Sdim void releaseMemory() override; 94292915Sdim}; 95292915Sdim} // end anonymous namespace 96292915Sdim 97292915Sdimchar WebAssemblyCFGStackify::ID = 0; 98341825SdimINITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, 99344779Sdim "Insert BLOCK and LOOP markers for WebAssembly scopes", false, 100344779Sdim false) 101341825Sdim 102292915SdimFunctionPass *llvm::createWebAssemblyCFGStackify() { 103292915Sdim return new WebAssemblyCFGStackify(); 104292915Sdim} 105292915Sdim 106292915Sdim/// Test whether Pred has any terminators explicitly branching to MBB, as 107292915Sdim/// opposed to falling through. Note that it's possible (eg. in unoptimized 108292915Sdim/// code) for a branch instruction to both branch to a block and fallthrough 109292915Sdim/// to it, so we check the actual branch operands to see if there are any 110292915Sdim/// explicit mentions. 111294024Sdimstatic bool ExplicitlyBranchesTo(MachineBasicBlock *Pred, 112294024Sdim MachineBasicBlock *MBB) { 113292915Sdim for (MachineInstr &MI : Pred->terminators()) 114344779Sdim // Even if a rethrow takes a BB argument, it is not a branch 115344779Sdim if (!WebAssembly::isRethrow(MI)) 116344779Sdim for (MachineOperand &MO : MI.explicit_operands()) 117344779Sdim if (MO.isMBB() && MO.getMBB() == MBB) 118344779Sdim return true; 119292915Sdim return false; 120292915Sdim} 121292915Sdim 122344779Sdim// Returns an iterator to the earliest position possible within the MBB, 123344779Sdim// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 124344779Sdim// contains instructions that should go before the marker, and AfterSet contains 125344779Sdim// ones that should go after the marker. In this function, AfterSet is only 126344779Sdim// used for sanity checking. 127344779Sdimstatic MachineBasicBlock::iterator 128344779SdimGetEarliestInsertPos(MachineBasicBlock *MBB, 129344779Sdim const SmallPtrSet<const MachineInstr *, 4> &BeforeSet, 130344779Sdim const SmallPtrSet<const MachineInstr *, 4> &AfterSet) { 131344779Sdim auto InsertPos = MBB->end(); 132344779Sdim while (InsertPos != MBB->begin()) { 133344779Sdim if (BeforeSet.count(&*std::prev(InsertPos))) { 134344779Sdim#ifndef NDEBUG 135344779Sdim // Sanity check 136344779Sdim for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos) 137344779Sdim assert(!AfterSet.count(&*std::prev(Pos))); 138344779Sdim#endif 139344779Sdim break; 140344779Sdim } 141344779Sdim --InsertPos; 142344779Sdim } 143344779Sdim return InsertPos; 144344779Sdim} 145344779Sdim 146344779Sdim// Returns an iterator to the latest position possible within the MBB, 147344779Sdim// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 148344779Sdim// contains instructions that should go before the marker, and AfterSet contains 149344779Sdim// ones that should go after the marker. In this function, BeforeSet is only 150344779Sdim// used for sanity checking. 151344779Sdimstatic MachineBasicBlock::iterator 152344779SdimGetLatestInsertPos(MachineBasicBlock *MBB, 153344779Sdim const SmallPtrSet<const MachineInstr *, 4> &BeforeSet, 154344779Sdim const SmallPtrSet<const MachineInstr *, 4> &AfterSet) { 155344779Sdim auto InsertPos = MBB->begin(); 156344779Sdim while (InsertPos != MBB->end()) { 157344779Sdim if (AfterSet.count(&*InsertPos)) { 158344779Sdim#ifndef NDEBUG 159344779Sdim // Sanity check 160344779Sdim for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos) 161344779Sdim assert(!BeforeSet.count(&*Pos)); 162344779Sdim#endif 163344779Sdim break; 164344779Sdim } 165344779Sdim ++InsertPos; 166344779Sdim } 167344779Sdim return InsertPos; 168344779Sdim} 169344779Sdim 170344779Sdimvoid WebAssemblyCFGStackify::registerScope(MachineInstr *Begin, 171344779Sdim MachineInstr *End) { 172344779Sdim BeginToEnd[Begin] = End; 173344779Sdim EndToBegin[End] = Begin; 174344779Sdim} 175344779Sdim 176344779Sdimvoid WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin, 177344779Sdim MachineInstr *End, 178344779Sdim MachineBasicBlock *EHPad) { 179344779Sdim registerScope(Begin, End); 180344779Sdim TryToEHPad[Begin] = EHPad; 181344779Sdim EHPadToTry[EHPad] = Begin; 182344779Sdim} 183344779Sdim 184344779Sdim// Given a LOOP/TRY marker, returns its bottom BB. Use cached information if any 185344779Sdim// to prevent recomputation. 186344779SdimMachineBasicBlock * 187344779SdimWebAssemblyCFGStackify::getBottom(const MachineInstr *Begin) { 188344779Sdim const auto &MLI = getAnalysis<MachineLoopInfo>(); 189344779Sdim const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); 190344779Sdim if (BeginToBottom.count(Begin)) 191344779Sdim return BeginToBottom[Begin]; 192344779Sdim if (Begin->getOpcode() == WebAssembly::LOOP) { 193344779Sdim MachineLoop *L = MLI.getLoopFor(Begin->getParent()); 194344779Sdim assert(L); 195344779Sdim BeginToBottom[Begin] = WebAssembly::getBottom(L); 196344779Sdim } else if (Begin->getOpcode() == WebAssembly::TRY) { 197344779Sdim WebAssemblyException *WE = WEI.getExceptionFor(TryToEHPad[Begin]); 198344779Sdim assert(WE); 199344779Sdim BeginToBottom[Begin] = WebAssembly::getBottom(WE); 200344779Sdim } else 201344779Sdim assert(false); 202344779Sdim return BeginToBottom[Begin]; 203344779Sdim} 204344779Sdim 205292915Sdim/// Insert a BLOCK marker for branches to MBB (if needed). 206344779Sdimvoid WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) { 207344779Sdim // This should have been handled in placeTryMarker. 208344779Sdim if (MBB.isEHPad()) 209344779Sdim return; 210344779Sdim 211344779Sdim MachineFunction &MF = *MBB.getParent(); 212344779Sdim auto &MDT = getAnalysis<MachineDominatorTree>(); 213344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 214344779Sdim const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 215344779Sdim 216292915Sdim // First compute the nearest common dominator of all forward non-fallthrough 217292915Sdim // predecessors so that we minimize the time that the BLOCK is on the stack, 218292915Sdim // which reduces overall stack height. 219292915Sdim MachineBasicBlock *Header = nullptr; 220292915Sdim bool IsBranchedTo = false; 221292915Sdim int MBBNumber = MBB.getNumber(); 222344779Sdim for (MachineBasicBlock *Pred : MBB.predecessors()) { 223292915Sdim if (Pred->getNumber() < MBBNumber) { 224292915Sdim Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 225292915Sdim if (ExplicitlyBranchesTo(Pred, &MBB)) 226292915Sdim IsBranchedTo = true; 227292915Sdim } 228344779Sdim } 229292915Sdim if (!Header) 230292915Sdim return; 231292915Sdim if (!IsBranchedTo) 232292915Sdim return; 233292915Sdim 234292915Sdim assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors"); 235314564Sdim MachineBasicBlock *LayoutPred = &*std::prev(MachineFunction::iterator(&MBB)); 236292915Sdim 237292915Sdim // If the nearest common dominator is inside a more deeply nested context, 238292915Sdim // walk out to the nearest scope which isn't more deeply nested. 239292915Sdim for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 240292915Sdim if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 241292915Sdim if (ScopeTop->getNumber() > Header->getNumber()) { 242292915Sdim // Skip over an intervening scope. 243314564Sdim I = std::next(MachineFunction::iterator(ScopeTop)); 244292915Sdim } else { 245292915Sdim // We found a scope level at an appropriate depth. 246292915Sdim Header = ScopeTop; 247292915Sdim break; 248292915Sdim } 249292915Sdim } 250292915Sdim } 251292915Sdim 252292915Sdim // Decide where in Header to put the BLOCK. 253344779Sdim 254344779Sdim // Instructions that should go before the BLOCK. 255344779Sdim SmallPtrSet<const MachineInstr *, 4> BeforeSet; 256344779Sdim // Instructions that should go after the BLOCK. 257344779Sdim SmallPtrSet<const MachineInstr *, 4> AfterSet; 258344779Sdim for (const auto &MI : *Header) { 259344779Sdim // If there is a previously placed LOOP/TRY marker and the bottom block of 260344779Sdim // the loop/exception is above MBB, it should be after the BLOCK, because 261344779Sdim // the loop/exception is nested in this block. Otherwise it should be before 262344779Sdim // the BLOCK. 263344779Sdim if (MI.getOpcode() == WebAssembly::LOOP || 264344779Sdim MI.getOpcode() == WebAssembly::TRY) { 265344779Sdim if (MBB.getNumber() > getBottom(&MI)->getNumber()) 266344779Sdim AfterSet.insert(&MI); 267344779Sdim#ifndef NDEBUG 268344779Sdim else 269344779Sdim BeforeSet.insert(&MI); 270344779Sdim#endif 271344779Sdim } 272344779Sdim 273344779Sdim // All previously inserted BLOCK markers should be after the BLOCK because 274344779Sdim // they are all nested blocks. 275344779Sdim if (MI.getOpcode() == WebAssembly::BLOCK) 276344779Sdim AfterSet.insert(&MI); 277344779Sdim 278344779Sdim#ifndef NDEBUG 279344779Sdim // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK. 280344779Sdim if (MI.getOpcode() == WebAssembly::END_BLOCK || 281344779Sdim MI.getOpcode() == WebAssembly::END_LOOP || 282344779Sdim MI.getOpcode() == WebAssembly::END_TRY) 283344779Sdim BeforeSet.insert(&MI); 284344779Sdim#endif 285344779Sdim 286344779Sdim // Terminators should go after the BLOCK. 287344779Sdim if (MI.isTerminator()) 288344779Sdim AfterSet.insert(&MI); 289292915Sdim } 290292915Sdim 291344779Sdim // Local expression tree should go after the BLOCK. 292344779Sdim for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; 293344779Sdim --I) { 294344779Sdim if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 295344779Sdim continue; 296344779Sdim if (WebAssembly::isChild(*std::prev(I), MFI)) 297344779Sdim AfterSet.insert(&*std::prev(I)); 298344779Sdim else 299344779Sdim break; 300344779Sdim } 301344779Sdim 302292915Sdim // Add the BLOCK. 303344779Sdim auto InsertPos = GetLatestInsertPos(Header, BeforeSet, AfterSet); 304341825Sdim MachineInstr *Begin = 305341825Sdim BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 306341825Sdim TII.get(WebAssembly::BLOCK)) 307341825Sdim .addImm(int64_t(WebAssembly::ExprType::Void)); 308292915Sdim 309344779Sdim // Decide where in Header to put the END_BLOCK. 310344779Sdim BeforeSet.clear(); 311344779Sdim AfterSet.clear(); 312344779Sdim for (auto &MI : MBB) { 313344779Sdim#ifndef NDEBUG 314344779Sdim // END_BLOCK should precede existing LOOP and TRY markers. 315344779Sdim if (MI.getOpcode() == WebAssembly::LOOP || 316344779Sdim MI.getOpcode() == WebAssembly::TRY) 317344779Sdim AfterSet.insert(&MI); 318344779Sdim#endif 319344779Sdim 320344779Sdim // If there is a previously placed END_LOOP marker and the header of the 321344779Sdim // loop is above this block's header, the END_LOOP should be placed after 322344779Sdim // the BLOCK, because the loop contains this block. Otherwise the END_LOOP 323344779Sdim // should be placed before the BLOCK. The same for END_TRY. 324344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP || 325344779Sdim MI.getOpcode() == WebAssembly::END_TRY) { 326344779Sdim if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) 327344779Sdim BeforeSet.insert(&MI); 328344779Sdim#ifndef NDEBUG 329344779Sdim else 330344779Sdim AfterSet.insert(&MI); 331344779Sdim#endif 332344779Sdim } 333344779Sdim } 334344779Sdim 335294024Sdim // Mark the end of the block. 336344779Sdim InsertPos = GetEarliestInsertPos(&MBB, BeforeSet, AfterSet); 337341825Sdim MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos), 338314564Sdim TII.get(WebAssembly::END_BLOCK)); 339344779Sdim registerScope(Begin, End); 340294024Sdim 341292915Sdim // Track the farthest-spanning scope that ends at this point. 342292915Sdim int Number = MBB.getNumber(); 343292915Sdim if (!ScopeTops[Number] || 344292915Sdim ScopeTops[Number]->getNumber() > Header->getNumber()) 345292915Sdim ScopeTops[Number] = Header; 346292915Sdim} 347292915Sdim 348292915Sdim/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header). 349344779Sdimvoid WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { 350344779Sdim MachineFunction &MF = *MBB.getParent(); 351344779Sdim const auto &MLI = getAnalysis<MachineLoopInfo>(); 352344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 353344779Sdim 354292915Sdim MachineLoop *Loop = MLI.getLoopFor(&MBB); 355292915Sdim if (!Loop || Loop->getHeader() != &MBB) 356292915Sdim return; 357292915Sdim 358292915Sdim // The operand of a LOOP is the first block after the loop. If the loop is the 359292915Sdim // bottom of the function, insert a dummy block at the end. 360341825Sdim MachineBasicBlock *Bottom = WebAssembly::getBottom(Loop); 361314564Sdim auto Iter = std::next(MachineFunction::iterator(Bottom)); 362292915Sdim if (Iter == MF.end()) { 363292915Sdim MachineBasicBlock *Label = MF.CreateMachineBasicBlock(); 364292915Sdim // Give it a fake predecessor so that AsmPrinter prints its label. 365292915Sdim Label->addSuccessor(Label); 366292915Sdim MF.push_back(Label); 367314564Sdim Iter = std::next(MachineFunction::iterator(Bottom)); 368292915Sdim } 369292915Sdim MachineBasicBlock *AfterLoop = &*Iter; 370292915Sdim 371344779Sdim // Decide where in Header to put the LOOP. 372344779Sdim SmallPtrSet<const MachineInstr *, 4> BeforeSet; 373344779Sdim SmallPtrSet<const MachineInstr *, 4> AfterSet; 374344779Sdim for (const auto &MI : MBB) { 375344779Sdim // LOOP marker should be after any existing loop that ends here. Otherwise 376344779Sdim // we assume the instruction belongs to the loop. 377344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP) 378344779Sdim BeforeSet.insert(&MI); 379344779Sdim#ifndef NDEBUG 380344779Sdim else 381344779Sdim AfterSet.insert(&MI); 382344779Sdim#endif 383344779Sdim } 384344779Sdim 385344779Sdim // Mark the beginning of the loop. 386344779Sdim auto InsertPos = GetEarliestInsertPos(&MBB, BeforeSet, AfterSet); 387341825Sdim MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos), 388314564Sdim TII.get(WebAssembly::LOOP)) 389341825Sdim .addImm(int64_t(WebAssembly::ExprType::Void)); 390292915Sdim 391344779Sdim // Decide where in Header to put the END_LOOP. 392344779Sdim BeforeSet.clear(); 393344779Sdim AfterSet.clear(); 394344779Sdim#ifndef NDEBUG 395344779Sdim for (const auto &MI : MBB) 396344779Sdim // Existing END_LOOP markers belong to parent loops of this loop 397344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP) 398344779Sdim AfterSet.insert(&MI); 399344779Sdim#endif 400344779Sdim 401344779Sdim // Mark the end of the loop (using arbitrary debug location that branched to 402344779Sdim // the loop end as its location). 403344779Sdim InsertPos = GetEarliestInsertPos(AfterLoop, BeforeSet, AfterSet); 404341825Sdim DebugLoc EndDL = (*AfterLoop->pred_rbegin())->findBranchDebugLoc(); 405344779Sdim MachineInstr *End = 406344779Sdim BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP)); 407344779Sdim registerScope(Begin, End); 408294024Sdim 409292915Sdim assert((!ScopeTops[AfterLoop->getNumber()] || 410292915Sdim ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) && 411309124Sdim "With block sorting the outermost loop for a block should be first."); 412292915Sdim if (!ScopeTops[AfterLoop->getNumber()]) 413292915Sdim ScopeTops[AfterLoop->getNumber()] = &MBB; 414292915Sdim} 415292915Sdim 416344779Sdimvoid WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) { 417344779Sdim if (!MBB.isEHPad()) 418344779Sdim return; 419344779Sdim 420344779Sdim // catch_all terminate pad is grouped together with catch terminate pad and 421344779Sdim // does not need a separate TRY and END_TRY marker. 422344779Sdim if (WebAssembly::isCatchAllTerminatePad(MBB)) 423344779Sdim return; 424344779Sdim 425344779Sdim MachineFunction &MF = *MBB.getParent(); 426344779Sdim auto &MDT = getAnalysis<MachineDominatorTree>(); 427344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 428344779Sdim const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); 429344779Sdim const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 430344779Sdim 431344779Sdim // Compute the nearest common dominator of all unwind predecessors 432344779Sdim MachineBasicBlock *Header = nullptr; 433344779Sdim int MBBNumber = MBB.getNumber(); 434344779Sdim for (auto *Pred : MBB.predecessors()) { 435344779Sdim if (Pred->getNumber() < MBBNumber) { 436344779Sdim Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 437344779Sdim assert(!ExplicitlyBranchesTo(Pred, &MBB) && 438344779Sdim "Explicit branch to an EH pad!"); 439344779Sdim } 440344779Sdim } 441344779Sdim if (!Header) 442344779Sdim return; 443344779Sdim 444344779Sdim // If this try is at the bottom of the function, insert a dummy block at the 445344779Sdim // end. 446344779Sdim WebAssemblyException *WE = WEI.getExceptionFor(&MBB); 447344779Sdim assert(WE); 448344779Sdim MachineBasicBlock *Bottom = WebAssembly::getBottom(WE); 449344779Sdim 450344779Sdim auto Iter = std::next(MachineFunction::iterator(Bottom)); 451344779Sdim if (Iter == MF.end()) { 452344779Sdim MachineBasicBlock *Label = MF.CreateMachineBasicBlock(); 453344779Sdim // Give it a fake predecessor so that AsmPrinter prints its label. 454344779Sdim Label->addSuccessor(Label); 455344779Sdim MF.push_back(Label); 456344779Sdim Iter = std::next(MachineFunction::iterator(Bottom)); 457344779Sdim } 458344779Sdim MachineBasicBlock *AfterTry = &*Iter; 459344779Sdim 460344779Sdim assert(AfterTry != &MF.front()); 461344779Sdim MachineBasicBlock *LayoutPred = 462344779Sdim &*std::prev(MachineFunction::iterator(AfterTry)); 463344779Sdim 464344779Sdim // If the nearest common dominator is inside a more deeply nested context, 465344779Sdim // walk out to the nearest scope which isn't more deeply nested. 466344779Sdim for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 467344779Sdim if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 468344779Sdim if (ScopeTop->getNumber() > Header->getNumber()) { 469344779Sdim // Skip over an intervening scope. 470344779Sdim I = std::next(MachineFunction::iterator(ScopeTop)); 471344779Sdim } else { 472344779Sdim // We found a scope level at an appropriate depth. 473344779Sdim Header = ScopeTop; 474344779Sdim break; 475344779Sdim } 476344779Sdim } 477344779Sdim } 478344779Sdim 479344779Sdim // Decide where in Header to put the TRY. 480344779Sdim 481344779Sdim // Instructions that should go before the BLOCK. 482344779Sdim SmallPtrSet<const MachineInstr *, 4> BeforeSet; 483344779Sdim // Instructions that should go after the BLOCK. 484344779Sdim SmallPtrSet<const MachineInstr *, 4> AfterSet; 485344779Sdim for (const auto &MI : *Header) { 486344779Sdim // If there is a previously placed LOOP marker and the bottom block of 487344779Sdim // the loop is above MBB, the LOOP should be after the TRY, because the 488344779Sdim // loop is nested in this try. Otherwise it should be before the TRY. 489344779Sdim if (MI.getOpcode() == WebAssembly::LOOP) { 490344779Sdim if (MBB.getNumber() > Bottom->getNumber()) 491344779Sdim AfterSet.insert(&MI); 492344779Sdim#ifndef NDEBUG 493344779Sdim else 494344779Sdim BeforeSet.insert(&MI); 495344779Sdim#endif 496344779Sdim } 497344779Sdim 498344779Sdim // All previously inserted TRY markers should be after the TRY because they 499344779Sdim // are all nested trys. 500344779Sdim if (MI.getOpcode() == WebAssembly::TRY) 501344779Sdim AfterSet.insert(&MI); 502344779Sdim 503344779Sdim#ifndef NDEBUG 504344779Sdim // All END_(LOOP/TRY) markers should be before the TRY. 505344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP || 506344779Sdim MI.getOpcode() == WebAssembly::END_TRY) 507344779Sdim BeforeSet.insert(&MI); 508344779Sdim#endif 509344779Sdim 510344779Sdim // Terminators should go after the TRY. 511344779Sdim if (MI.isTerminator()) 512344779Sdim AfterSet.insert(&MI); 513344779Sdim } 514344779Sdim 515344779Sdim // Local expression tree should go after the TRY. 516344779Sdim for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; 517344779Sdim --I) { 518344779Sdim if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 519344779Sdim continue; 520344779Sdim if (WebAssembly::isChild(*std::prev(I), MFI)) 521344779Sdim AfterSet.insert(&*std::prev(I)); 522344779Sdim else 523344779Sdim break; 524344779Sdim } 525344779Sdim 526344779Sdim // If Header unwinds to MBB (= Header contains 'invoke'), the try block should 527344779Sdim // contain the call within it. So the call should go after the TRY. The 528344779Sdim // exception is when the header's terminator is a rethrow instruction, in 529344779Sdim // which case that instruction, not a call instruction before it, is gonna 530344779Sdim // throw. 531344779Sdim if (MBB.isPredecessor(Header)) { 532344779Sdim auto TermPos = Header->getFirstTerminator(); 533344779Sdim if (TermPos == Header->end() || !WebAssembly::isRethrow(*TermPos)) { 534344779Sdim for (const auto &MI : reverse(*Header)) { 535344779Sdim if (MI.isCall()) { 536344779Sdim AfterSet.insert(&MI); 537344779Sdim break; 538344779Sdim } 539344779Sdim } 540344779Sdim } 541344779Sdim } 542344779Sdim 543344779Sdim // Add the TRY. 544344779Sdim auto InsertPos = GetLatestInsertPos(Header, BeforeSet, AfterSet); 545344779Sdim MachineInstr *Begin = 546344779Sdim BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 547344779Sdim TII.get(WebAssembly::TRY)) 548344779Sdim .addImm(int64_t(WebAssembly::ExprType::Void)); 549344779Sdim 550344779Sdim // Decide where in Header to put the END_TRY. 551344779Sdim BeforeSet.clear(); 552344779Sdim AfterSet.clear(); 553344779Sdim for (const auto &MI : *AfterTry) { 554344779Sdim#ifndef NDEBUG 555344779Sdim // END_TRY should precede existing LOOP markers. 556344779Sdim if (MI.getOpcode() == WebAssembly::LOOP) 557344779Sdim AfterSet.insert(&MI); 558344779Sdim 559344779Sdim // All END_TRY markers placed earlier belong to exceptions that contains 560344779Sdim // this one. 561344779Sdim if (MI.getOpcode() == WebAssembly::END_TRY) 562344779Sdim AfterSet.insert(&MI); 563344779Sdim#endif 564344779Sdim 565344779Sdim // If there is a previously placed END_LOOP marker and its header is after 566344779Sdim // where TRY marker is, this loop is contained within the 'catch' part, so 567344779Sdim // the END_TRY marker should go after that. Otherwise, the whole try-catch 568344779Sdim // is contained within this loop, so the END_TRY should go before that. 569344779Sdim if (MI.getOpcode() == WebAssembly::END_LOOP) { 570344779Sdim if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) 571344779Sdim BeforeSet.insert(&MI); 572344779Sdim#ifndef NDEBUG 573344779Sdim else 574344779Sdim AfterSet.insert(&MI); 575344779Sdim#endif 576344779Sdim } 577344779Sdim } 578344779Sdim 579344779Sdim // Mark the end of the TRY. 580344779Sdim InsertPos = GetEarliestInsertPos(AfterTry, BeforeSet, AfterSet); 581344779Sdim MachineInstr *End = 582344779Sdim BuildMI(*AfterTry, InsertPos, Bottom->findBranchDebugLoc(), 583344779Sdim TII.get(WebAssembly::END_TRY)); 584344779Sdim registerTryScope(Begin, End, &MBB); 585344779Sdim 586344779Sdim // Track the farthest-spanning scope that ends at this point. 587344779Sdim int Number = AfterTry->getNumber(); 588344779Sdim if (!ScopeTops[Number] || 589344779Sdim ScopeTops[Number]->getNumber() > Header->getNumber()) 590344779Sdim ScopeTops[Number] = Header; 591344779Sdim} 592344779Sdim 593294024Sdimstatic unsigned 594294024SdimGetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack, 595294024Sdim const MachineBasicBlock *MBB) { 596294024Sdim unsigned Depth = 0; 597294024Sdim for (auto X : reverse(Stack)) { 598294024Sdim if (X == MBB) 599294024Sdim break; 600294024Sdim ++Depth; 601294024Sdim } 602294024Sdim assert(Depth < Stack.size() && "Branch destination should be in scope"); 603294024Sdim return Depth; 604294024Sdim} 605294024Sdim 606314564Sdim/// In normal assembly languages, when the end of a function is unreachable, 607314564Sdim/// because the function ends in an infinite loop or a noreturn call or similar, 608314564Sdim/// it isn't necessary to worry about the function return type at the end of 609314564Sdim/// the function, because it's never reached. However, in WebAssembly, blocks 610314564Sdim/// that end at the function end need to have a return type signature that 611314564Sdim/// matches the function signature, even though it's unreachable. This function 612314564Sdim/// checks for such cases and fixes up the signatures. 613344779Sdimvoid WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { 614344779Sdim const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 615314564Sdim assert(MFI.getResults().size() <= 1); 616314564Sdim 617314564Sdim if (MFI.getResults().empty()) 618314564Sdim return; 619314564Sdim 620314564Sdim WebAssembly::ExprType retType; 621314564Sdim switch (MFI.getResults().front().SimpleTy) { 622344779Sdim case MVT::i32: 623344779Sdim retType = WebAssembly::ExprType::I32; 624344779Sdim break; 625344779Sdim case MVT::i64: 626344779Sdim retType = WebAssembly::ExprType::I64; 627344779Sdim break; 628344779Sdim case MVT::f32: 629344779Sdim retType = WebAssembly::ExprType::F32; 630344779Sdim break; 631344779Sdim case MVT::f64: 632344779Sdim retType = WebAssembly::ExprType::F64; 633344779Sdim break; 634344779Sdim case MVT::v16i8: 635344779Sdim case MVT::v8i16: 636344779Sdim case MVT::v4i32: 637344779Sdim case MVT::v2i64: 638344779Sdim case MVT::v4f32: 639344779Sdim case MVT::v2f64: 640344779Sdim retType = WebAssembly::ExprType::V128; 641344779Sdim break; 642344779Sdim case MVT::ExceptRef: 643344779Sdim retType = WebAssembly::ExprType::ExceptRef; 644344779Sdim break; 645344779Sdim default: 646344779Sdim llvm_unreachable("unexpected return type"); 647314564Sdim } 648314564Sdim 649314564Sdim for (MachineBasicBlock &MBB : reverse(MF)) { 650314564Sdim for (MachineInstr &MI : reverse(MBB)) { 651341825Sdim if (MI.isPosition() || MI.isDebugInstr()) 652314564Sdim continue; 653314564Sdim if (MI.getOpcode() == WebAssembly::END_BLOCK) { 654344779Sdim EndToBegin[&MI]->getOperand(0).setImm(int32_t(retType)); 655314564Sdim continue; 656314564Sdim } 657314564Sdim if (MI.getOpcode() == WebAssembly::END_LOOP) { 658344779Sdim EndToBegin[&MI]->getOperand(0).setImm(int32_t(retType)); 659314564Sdim continue; 660314564Sdim } 661314564Sdim // Something other than an `end`. We're done. 662314564Sdim return; 663314564Sdim } 664314564Sdim } 665314564Sdim} 666314564Sdim 667321369Sdim// WebAssembly functions end with an end instruction, as if the function body 668321369Sdim// were a block. 669344779Sdimstatic void AppendEndToFunction(MachineFunction &MF, 670344779Sdim const WebAssemblyInstrInfo &TII) { 671341825Sdim BuildMI(MF.back(), MF.back().end(), 672341825Sdim MF.back().findPrevDebugLoc(MF.back().end()), 673321369Sdim TII.get(WebAssembly::END_FUNCTION)); 674321369Sdim} 675321369Sdim 676344779Sdim/// Insert LOOP/TRY/BLOCK markers at appropriate places. 677344779Sdimvoid WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { 678344779Sdim const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 679344779Sdim // We allocate one more than the number of blocks in the function to 680344779Sdim // accommodate for the possible fake block we may insert at the end. 681344779Sdim ScopeTops.resize(MF.getNumBlockIDs() + 1); 682344779Sdim // Place the LOOP for MBB if MBB is the header of a loop. 683344779Sdim for (auto &MBB : MF) 684344779Sdim placeLoopMarker(MBB); 685344779Sdim // Place the TRY for MBB if MBB is the EH pad of an exception. 686344779Sdim if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 687344779Sdim MF.getFunction().hasPersonalityFn()) 688344779Sdim for (auto &MBB : MF) 689344779Sdim placeTryMarker(MBB); 690344779Sdim // Place the BLOCK for MBB if MBB is branched to from above. 691344779Sdim for (auto &MBB : MF) 692344779Sdim placeBlockMarker(MBB); 693344779Sdim} 694292915Sdim 695344779Sdimvoid WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { 696344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 697294024Sdim // Now rewrite references to basic blocks to be depth immediates. 698344779Sdim // We need two stacks: one for normal scopes and the other for EH pad scopes. 699344779Sdim // EH pad stack is used to rewrite depths in rethrow instructions. 700294024Sdim SmallVector<const MachineBasicBlock *, 8> Stack; 701344779Sdim SmallVector<const MachineBasicBlock *, 8> EHPadStack; 702294024Sdim for (auto &MBB : reverse(MF)) { 703344779Sdim for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) { 704344779Sdim MachineInstr &MI = *I; 705294024Sdim switch (MI.getOpcode()) { 706294024Sdim case WebAssembly::BLOCK: 707344779Sdim assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= 708344779Sdim MBB.getNumber() && 709344779Sdim "Block/try should be balanced"); 710294024Sdim Stack.pop_back(); 711294024Sdim break; 712344779Sdim 713344779Sdim case WebAssembly::TRY: 714344779Sdim assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= 715344779Sdim MBB.getNumber() && 716344779Sdim "Block/try marker should be balanced"); 717344779Sdim Stack.pop_back(); 718344779Sdim EHPadStack.pop_back(); 719344779Sdim break; 720344779Sdim 721344779Sdim case WebAssembly::CATCH_I32: 722344779Sdim case WebAssembly::CATCH_I64: 723344779Sdim case WebAssembly::CATCH_ALL: 724344779Sdim // Currently the only case there are more than one catch for a try is 725344779Sdim // for catch terminate pad, in the form of 726344779Sdim // try 727344779Sdim // catch 728344779Sdim // call @__clang_call_terminate 729344779Sdim // unreachable 730344779Sdim // catch_all 731344779Sdim // call @std::terminate 732344779Sdim // unreachable 733344779Sdim // end 734344779Sdim // So we shouldn't push the current BB for the second catch_all block 735344779Sdim // here. 736344779Sdim if (!WebAssembly::isCatchAllTerminatePad(MBB)) 737344779Sdim EHPadStack.push_back(&MBB); 738344779Sdim break; 739344779Sdim 740294024Sdim case WebAssembly::LOOP: 741294024Sdim assert(Stack.back() == &MBB && "Loop top should be balanced"); 742294024Sdim Stack.pop_back(); 743294024Sdim break; 744344779Sdim 745294024Sdim case WebAssembly::END_BLOCK: 746344779Sdim case WebAssembly::END_TRY: 747294024Sdim Stack.push_back(&MBB); 748294024Sdim break; 749344779Sdim 750294024Sdim case WebAssembly::END_LOOP: 751344779Sdim Stack.push_back(EndToBegin[&MI]->getParent()); 752294024Sdim break; 753344779Sdim 754344779Sdim case WebAssembly::RETHROW: { 755344779Sdim // Rewrite MBB operands to be depth immediates. 756344779Sdim unsigned EHPadDepth = GetDepth(EHPadStack, MI.getOperand(0).getMBB()); 757344779Sdim MI.RemoveOperand(0); 758344779Sdim MI.addOperand(MF, MachineOperand::CreateImm(EHPadDepth)); 759344779Sdim break; 760344779Sdim } 761344779Sdim 762344779Sdim case WebAssembly::RETHROW_TO_CALLER: { 763344779Sdim MachineInstr *Rethrow = 764344779Sdim BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(WebAssembly::RETHROW)) 765344779Sdim .addImm(EHPadStack.size()); 766344779Sdim MI.eraseFromParent(); 767344779Sdim I = MachineBasicBlock::reverse_iterator(Rethrow); 768344779Sdim break; 769344779Sdim } 770344779Sdim 771294024Sdim default: 772294024Sdim if (MI.isTerminator()) { 773294024Sdim // Rewrite MBB operands to be depth immediates. 774294024Sdim SmallVector<MachineOperand, 4> Ops(MI.operands()); 775294024Sdim while (MI.getNumOperands() > 0) 776294024Sdim MI.RemoveOperand(MI.getNumOperands() - 1); 777294024Sdim for (auto MO : Ops) { 778294024Sdim if (MO.isMBB()) 779294024Sdim MO = MachineOperand::CreateImm(GetDepth(Stack, MO.getMBB())); 780294024Sdim MI.addOperand(MF, MO); 781294024Sdim } 782294024Sdim } 783294024Sdim break; 784294024Sdim } 785294024Sdim } 786294024Sdim } 787294024Sdim assert(Stack.empty() && "Control flow should be balanced"); 788344779Sdim} 789314564Sdim 790344779Sdimvoid WebAssemblyCFGStackify::releaseMemory() { 791344779Sdim ScopeTops.clear(); 792344779Sdim BeginToEnd.clear(); 793344779Sdim EndToBegin.clear(); 794344779Sdim TryToEHPad.clear(); 795344779Sdim EHPadToTry.clear(); 796344779Sdim BeginToBottom.clear(); 797292915Sdim} 798292915Sdim 799292915Sdimbool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 800341825Sdim LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n" 801341825Sdim "********** Function: " 802341825Sdim << MF.getName() << '\n'); 803292915Sdim 804344779Sdim releaseMemory(); 805344779Sdim 806314564Sdim // Liveness is not tracked for VALUE_STACK physreg. 807294024Sdim MF.getRegInfo().invalidateLiveness(); 808292915Sdim 809344779Sdim // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes. 810344779Sdim placeMarkers(MF); 811292915Sdim 812344779Sdim // Convert MBB operands in terminators to relative depth immediates. 813344779Sdim rewriteDepthImmediates(MF); 814344779Sdim 815344779Sdim // Fix up block/loop/try signatures at the end of the function to conform to 816344779Sdim // WebAssembly's rules. 817344779Sdim fixEndsAtEndOfFunction(MF); 818344779Sdim 819344779Sdim // Add an end instruction at the end of the function body. 820344779Sdim const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 821344779Sdim if (!MF.getSubtarget<WebAssemblySubtarget>() 822344779Sdim .getTargetTriple() 823344779Sdim .isOSBinFormatELF()) 824344779Sdim AppendEndToFunction(MF, TII); 825344779Sdim 826292915Sdim return true; 827292915Sdim} 828