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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file implements a CFG stacking pass. 11 /// 12 /// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes, 13 /// since scope boundaries serve as the labels for WebAssembly's control 14 /// transfers. 15 /// 16 /// This is sufficient to convert arbitrary CFGs into a form that works on 17 /// WebAssembly, provided that all loops are single-entry. 18 /// 19 /// In case we use exceptions, this pass also fixes mismatches in unwind 20 /// destinations created during transforming CFG into wasm structured format. 21 /// 22 //===----------------------------------------------------------------------===// 23 24 #include "Utils/WebAssemblyTypeUtilities.h" 25 #include "Utils/WebAssemblyUtilities.h" 26 #include "WebAssembly.h" 27 #include "WebAssemblyExceptionInfo.h" 28 #include "WebAssemblyMachineFunctionInfo.h" 29 #include "WebAssemblySortRegion.h" 30 #include "WebAssemblySubtarget.h" 31 #include "llvm/ADT/Statistic.h" 32 #include "llvm/CodeGen/MachineDominators.h" 33 #include "llvm/CodeGen/MachineInstrBuilder.h" 34 #include "llvm/CodeGen/MachineLoopInfo.h" 35 #include "llvm/CodeGen/WasmEHFuncInfo.h" 36 #include "llvm/MC/MCAsmInfo.h" 37 #include "llvm/Target/TargetMachine.h" 38 using namespace llvm; 39 using WebAssembly::SortRegionInfo; 40 41 #define DEBUG_TYPE "wasm-cfg-stackify" 42 43 STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found"); 44 STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found"); 45 46 namespace { 47 class WebAssemblyCFGStackify final : public MachineFunctionPass { 48 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } 49 50 void getAnalysisUsage(AnalysisUsage &AU) const override { 51 AU.addRequired<MachineDominatorTree>(); 52 AU.addRequired<MachineLoopInfo>(); 53 AU.addRequired<WebAssemblyExceptionInfo>(); 54 MachineFunctionPass::getAnalysisUsage(AU); 55 } 56 57 bool runOnMachineFunction(MachineFunction &MF) override; 58 59 // For each block whose label represents the end of a scope, record the block 60 // which holds the beginning of the scope. This will allow us to quickly skip 61 // over scoped regions when walking blocks. 62 SmallVector<MachineBasicBlock *, 8> ScopeTops; 63 void updateScopeTops(MachineBasicBlock *Begin, MachineBasicBlock *End) { 64 int EndNo = End->getNumber(); 65 if (!ScopeTops[EndNo] || ScopeTops[EndNo]->getNumber() > Begin->getNumber()) 66 ScopeTops[EndNo] = Begin; 67 } 68 69 // Placing markers. 70 void placeMarkers(MachineFunction &MF); 71 void placeBlockMarker(MachineBasicBlock &MBB); 72 void placeLoopMarker(MachineBasicBlock &MBB); 73 void placeTryMarker(MachineBasicBlock &MBB); 74 75 // Exception handling related functions 76 bool fixCallUnwindMismatches(MachineFunction &MF); 77 bool fixCatchUnwindMismatches(MachineFunction &MF); 78 void addTryDelegate(MachineInstr *RangeBegin, MachineInstr *RangeEnd, 79 MachineBasicBlock *DelegateDest); 80 void recalculateScopeTops(MachineFunction &MF); 81 void removeUnnecessaryInstrs(MachineFunction &MF); 82 83 // Wrap-up 84 using EndMarkerInfo = 85 std::pair<const MachineBasicBlock *, const MachineInstr *>; 86 unsigned getBranchDepth(const SmallVectorImpl<EndMarkerInfo> &Stack, 87 const MachineBasicBlock *MBB); 88 unsigned getDelegateDepth(const SmallVectorImpl<EndMarkerInfo> &Stack, 89 const MachineBasicBlock *MBB); 90 unsigned 91 getRethrowDepth(const SmallVectorImpl<EndMarkerInfo> &Stack, 92 const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack); 93 void rewriteDepthImmediates(MachineFunction &MF); 94 void fixEndsAtEndOfFunction(MachineFunction &MF); 95 void cleanupFunctionData(MachineFunction &MF); 96 97 // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY) or DELEGATE 98 // (in case of TRY). 99 DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd; 100 // For each END_(BLOCK|LOOP|TRY) or DELEGATE, the corresponding 101 // BLOCK|LOOP|TRY. 102 DenseMap<const MachineInstr *, MachineInstr *> EndToBegin; 103 // <TRY marker, EH pad> map 104 DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad; 105 // <EH pad, TRY marker> map 106 DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry; 107 108 // We need an appendix block to place 'end_loop' or 'end_try' marker when the 109 // loop / exception bottom block is the last block in a function 110 MachineBasicBlock *AppendixBB = nullptr; 111 MachineBasicBlock *getAppendixBlock(MachineFunction &MF) { 112 if (!AppendixBB) { 113 AppendixBB = MF.CreateMachineBasicBlock(); 114 // Give it a fake predecessor so that AsmPrinter prints its label. 115 AppendixBB->addSuccessor(AppendixBB); 116 MF.push_back(AppendixBB); 117 } 118 return AppendixBB; 119 } 120 121 // Before running rewriteDepthImmediates function, 'delegate' has a BB as its 122 // destination operand. getFakeCallerBlock() returns a fake BB that will be 123 // used for the operand when 'delegate' needs to rethrow to the caller. This 124 // will be rewritten as an immediate value that is the number of block depths 125 // + 1 in rewriteDepthImmediates, and this fake BB will be removed at the end 126 // of the pass. 127 MachineBasicBlock *FakeCallerBB = nullptr; 128 MachineBasicBlock *getFakeCallerBlock(MachineFunction &MF) { 129 if (!FakeCallerBB) 130 FakeCallerBB = MF.CreateMachineBasicBlock(); 131 return FakeCallerBB; 132 } 133 134 // Helper functions to register / unregister scope information created by 135 // marker instructions. 136 void registerScope(MachineInstr *Begin, MachineInstr *End); 137 void registerTryScope(MachineInstr *Begin, MachineInstr *End, 138 MachineBasicBlock *EHPad); 139 void unregisterScope(MachineInstr *Begin); 140 141 public: 142 static char ID; // Pass identification, replacement for typeid 143 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} 144 ~WebAssemblyCFGStackify() override { releaseMemory(); } 145 void releaseMemory() override; 146 }; 147 } // end anonymous namespace 148 149 char WebAssemblyCFGStackify::ID = 0; 150 INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, 151 "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false, 152 false) 153 154 FunctionPass *llvm::createWebAssemblyCFGStackify() { 155 return new WebAssemblyCFGStackify(); 156 } 157 158 /// Test whether Pred has any terminators explicitly branching to MBB, as 159 /// opposed to falling through. Note that it's possible (eg. in unoptimized 160 /// code) for a branch instruction to both branch to a block and fallthrough 161 /// to it, so we check the actual branch operands to see if there are any 162 /// explicit mentions. 163 static bool explicitlyBranchesTo(MachineBasicBlock *Pred, 164 MachineBasicBlock *MBB) { 165 for (MachineInstr &MI : Pred->terminators()) 166 for (MachineOperand &MO : MI.explicit_operands()) 167 if (MO.isMBB() && MO.getMBB() == MBB) 168 return true; 169 return false; 170 } 171 172 // Returns an iterator to the earliest position possible within the MBB, 173 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 174 // contains instructions that should go before the marker, and AfterSet contains 175 // ones that should go after the marker. In this function, AfterSet is only 176 // used for sanity checking. 177 template <typename Container> 178 static MachineBasicBlock::iterator 179 getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, 180 const Container &AfterSet) { 181 auto InsertPos = MBB->end(); 182 while (InsertPos != MBB->begin()) { 183 if (BeforeSet.count(&*std::prev(InsertPos))) { 184 #ifndef NDEBUG 185 // Sanity check 186 for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos) 187 assert(!AfterSet.count(&*std::prev(Pos))); 188 #endif 189 break; 190 } 191 --InsertPos; 192 } 193 return InsertPos; 194 } 195 196 // Returns an iterator to the latest position possible within the MBB, 197 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet 198 // contains instructions that should go before the marker, and AfterSet contains 199 // ones that should go after the marker. In this function, BeforeSet is only 200 // used for sanity checking. 201 template <typename Container> 202 static MachineBasicBlock::iterator 203 getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, 204 const Container &AfterSet) { 205 auto InsertPos = MBB->begin(); 206 while (InsertPos != MBB->end()) { 207 if (AfterSet.count(&*InsertPos)) { 208 #ifndef NDEBUG 209 // Sanity check 210 for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos) 211 assert(!BeforeSet.count(&*Pos)); 212 #endif 213 break; 214 } 215 ++InsertPos; 216 } 217 return InsertPos; 218 } 219 220 void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin, 221 MachineInstr *End) { 222 BeginToEnd[Begin] = End; 223 EndToBegin[End] = Begin; 224 } 225 226 // When 'End' is not an 'end_try' but 'delegate, EHPad is nullptr. 227 void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin, 228 MachineInstr *End, 229 MachineBasicBlock *EHPad) { 230 registerScope(Begin, End); 231 TryToEHPad[Begin] = EHPad; 232 EHPadToTry[EHPad] = Begin; 233 } 234 235 void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) { 236 assert(BeginToEnd.count(Begin)); 237 MachineInstr *End = BeginToEnd[Begin]; 238 assert(EndToBegin.count(End)); 239 BeginToEnd.erase(Begin); 240 EndToBegin.erase(End); 241 MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin); 242 if (EHPad) { 243 assert(EHPadToTry.count(EHPad)); 244 TryToEHPad.erase(Begin); 245 EHPadToTry.erase(EHPad); 246 } 247 } 248 249 /// Insert a BLOCK marker for branches to MBB (if needed). 250 // TODO Consider a more generalized way of handling block (and also loop and 251 // try) signatures when we implement the multi-value proposal later. 252 void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) { 253 assert(!MBB.isEHPad()); 254 MachineFunction &MF = *MBB.getParent(); 255 auto &MDT = getAnalysis<MachineDominatorTree>(); 256 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 257 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 258 259 // First compute the nearest common dominator of all forward non-fallthrough 260 // predecessors so that we minimize the time that the BLOCK is on the stack, 261 // which reduces overall stack height. 262 MachineBasicBlock *Header = nullptr; 263 bool IsBranchedTo = false; 264 int MBBNumber = MBB.getNumber(); 265 for (MachineBasicBlock *Pred : MBB.predecessors()) { 266 if (Pred->getNumber() < MBBNumber) { 267 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 268 if (explicitlyBranchesTo(Pred, &MBB)) 269 IsBranchedTo = true; 270 } 271 } 272 if (!Header) 273 return; 274 if (!IsBranchedTo) 275 return; 276 277 assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors"); 278 MachineBasicBlock *LayoutPred = MBB.getPrevNode(); 279 280 // If the nearest common dominator is inside a more deeply nested context, 281 // walk out to the nearest scope which isn't more deeply nested. 282 for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 283 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 284 if (ScopeTop->getNumber() > Header->getNumber()) { 285 // Skip over an intervening scope. 286 I = std::next(ScopeTop->getIterator()); 287 } else { 288 // We found a scope level at an appropriate depth. 289 Header = ScopeTop; 290 break; 291 } 292 } 293 } 294 295 // Decide where in Header to put the BLOCK. 296 297 // Instructions that should go before the BLOCK. 298 SmallPtrSet<const MachineInstr *, 4> BeforeSet; 299 // Instructions that should go after the BLOCK. 300 SmallPtrSet<const MachineInstr *, 4> AfterSet; 301 for (const auto &MI : *Header) { 302 // If there is a previously placed LOOP marker and the bottom block of the 303 // loop is above MBB, it should be after the BLOCK, because the loop is 304 // nested in this BLOCK. Otherwise it should be before the BLOCK. 305 if (MI.getOpcode() == WebAssembly::LOOP) { 306 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); 307 if (MBB.getNumber() > LoopBottom->getNumber()) 308 AfterSet.insert(&MI); 309 #ifndef NDEBUG 310 else 311 BeforeSet.insert(&MI); 312 #endif 313 } 314 315 // If there is a previously placed BLOCK/TRY marker and its corresponding 316 // END marker is before the current BLOCK's END marker, that should be 317 // placed after this BLOCK. Otherwise it should be placed before this BLOCK 318 // marker. 319 if (MI.getOpcode() == WebAssembly::BLOCK || 320 MI.getOpcode() == WebAssembly::TRY) { 321 if (BeginToEnd[&MI]->getParent()->getNumber() <= MBB.getNumber()) 322 AfterSet.insert(&MI); 323 #ifndef NDEBUG 324 else 325 BeforeSet.insert(&MI); 326 #endif 327 } 328 329 #ifndef NDEBUG 330 // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK. 331 if (MI.getOpcode() == WebAssembly::END_BLOCK || 332 MI.getOpcode() == WebAssembly::END_LOOP || 333 MI.getOpcode() == WebAssembly::END_TRY) 334 BeforeSet.insert(&MI); 335 #endif 336 337 // Terminators should go after the BLOCK. 338 if (MI.isTerminator()) 339 AfterSet.insert(&MI); 340 } 341 342 // Local expression tree should go after the BLOCK. 343 for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E; 344 --I) { 345 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 346 continue; 347 if (WebAssembly::isChild(*std::prev(I), MFI)) 348 AfterSet.insert(&*std::prev(I)); 349 else 350 break; 351 } 352 353 // Add the BLOCK. 354 WebAssembly::BlockType ReturnType = WebAssembly::BlockType::Void; 355 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); 356 MachineInstr *Begin = 357 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 358 TII.get(WebAssembly::BLOCK)) 359 .addImm(int64_t(ReturnType)); 360 361 // Decide where in Header to put the END_BLOCK. 362 BeforeSet.clear(); 363 AfterSet.clear(); 364 for (auto &MI : MBB) { 365 #ifndef NDEBUG 366 // END_BLOCK should precede existing LOOP and TRY markers. 367 if (MI.getOpcode() == WebAssembly::LOOP || 368 MI.getOpcode() == WebAssembly::TRY) 369 AfterSet.insert(&MI); 370 #endif 371 372 // If there is a previously placed END_LOOP marker and the header of the 373 // loop is above this block's header, the END_LOOP should be placed after 374 // the BLOCK, because the loop contains this block. Otherwise the END_LOOP 375 // should be placed before the BLOCK. The same for END_TRY. 376 if (MI.getOpcode() == WebAssembly::END_LOOP || 377 MI.getOpcode() == WebAssembly::END_TRY) { 378 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber()) 379 BeforeSet.insert(&MI); 380 #ifndef NDEBUG 381 else 382 AfterSet.insert(&MI); 383 #endif 384 } 385 } 386 387 // Mark the end of the block. 388 InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); 389 MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos), 390 TII.get(WebAssembly::END_BLOCK)); 391 registerScope(Begin, End); 392 393 // Track the farthest-spanning scope that ends at this point. 394 updateScopeTops(Header, &MBB); 395 } 396 397 /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header). 398 void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { 399 MachineFunction &MF = *MBB.getParent(); 400 const auto &MLI = getAnalysis<MachineLoopInfo>(); 401 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); 402 SortRegionInfo SRI(MLI, WEI); 403 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 404 405 MachineLoop *Loop = MLI.getLoopFor(&MBB); 406 if (!Loop || Loop->getHeader() != &MBB) 407 return; 408 409 // The operand of a LOOP is the first block after the loop. If the loop is the 410 // bottom of the function, insert a dummy block at the end. 411 MachineBasicBlock *Bottom = SRI.getBottom(Loop); 412 auto Iter = std::next(Bottom->getIterator()); 413 if (Iter == MF.end()) { 414 getAppendixBlock(MF); 415 Iter = std::next(Bottom->getIterator()); 416 } 417 MachineBasicBlock *AfterLoop = &*Iter; 418 419 // Decide where in Header to put the LOOP. 420 SmallPtrSet<const MachineInstr *, 4> BeforeSet; 421 SmallPtrSet<const MachineInstr *, 4> AfterSet; 422 for (const auto &MI : MBB) { 423 // LOOP marker should be after any existing loop that ends here. Otherwise 424 // we assume the instruction belongs to the loop. 425 if (MI.getOpcode() == WebAssembly::END_LOOP) 426 BeforeSet.insert(&MI); 427 #ifndef NDEBUG 428 else 429 AfterSet.insert(&MI); 430 #endif 431 } 432 433 // Mark the beginning of the loop. 434 auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet); 435 MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos), 436 TII.get(WebAssembly::LOOP)) 437 .addImm(int64_t(WebAssembly::BlockType::Void)); 438 439 // Decide where in Header to put the END_LOOP. 440 BeforeSet.clear(); 441 AfterSet.clear(); 442 #ifndef NDEBUG 443 for (const auto &MI : MBB) 444 // Existing END_LOOP markers belong to parent loops of this loop 445 if (MI.getOpcode() == WebAssembly::END_LOOP) 446 AfterSet.insert(&MI); 447 #endif 448 449 // Mark the end of the loop (using arbitrary debug location that branched to 450 // the loop end as its location). 451 InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet); 452 DebugLoc EndDL = AfterLoop->pred_empty() 453 ? DebugLoc() 454 : (*AfterLoop->pred_rbegin())->findBranchDebugLoc(); 455 MachineInstr *End = 456 BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP)); 457 registerScope(Begin, End); 458 459 assert((!ScopeTops[AfterLoop->getNumber()] || 460 ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) && 461 "With block sorting the outermost loop for a block should be first."); 462 updateScopeTops(&MBB, AfterLoop); 463 } 464 465 void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) { 466 assert(MBB.isEHPad()); 467 MachineFunction &MF = *MBB.getParent(); 468 auto &MDT = getAnalysis<MachineDominatorTree>(); 469 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 470 const auto &MLI = getAnalysis<MachineLoopInfo>(); 471 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>(); 472 SortRegionInfo SRI(MLI, WEI); 473 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 474 475 // Compute the nearest common dominator of all unwind predecessors 476 MachineBasicBlock *Header = nullptr; 477 int MBBNumber = MBB.getNumber(); 478 for (auto *Pred : MBB.predecessors()) { 479 if (Pred->getNumber() < MBBNumber) { 480 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 481 assert(!explicitlyBranchesTo(Pred, &MBB) && 482 "Explicit branch to an EH pad!"); 483 } 484 } 485 if (!Header) 486 return; 487 488 // If this try is at the bottom of the function, insert a dummy block at the 489 // end. 490 WebAssemblyException *WE = WEI.getExceptionFor(&MBB); 491 assert(WE); 492 MachineBasicBlock *Bottom = SRI.getBottom(WE); 493 494 auto Iter = std::next(Bottom->getIterator()); 495 if (Iter == MF.end()) { 496 getAppendixBlock(MF); 497 Iter = std::next(Bottom->getIterator()); 498 } 499 MachineBasicBlock *Cont = &*Iter; 500 501 assert(Cont != &MF.front()); 502 MachineBasicBlock *LayoutPred = Cont->getPrevNode(); 503 504 // If the nearest common dominator is inside a more deeply nested context, 505 // walk out to the nearest scope which isn't more deeply nested. 506 for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 507 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 508 if (ScopeTop->getNumber() > Header->getNumber()) { 509 // Skip over an intervening scope. 510 I = std::next(ScopeTop->getIterator()); 511 } else { 512 // We found a scope level at an appropriate depth. 513 Header = ScopeTop; 514 break; 515 } 516 } 517 } 518 519 // Decide where in Header to put the TRY. 520 521 // Instructions that should go before the TRY. 522 SmallPtrSet<const MachineInstr *, 4> BeforeSet; 523 // Instructions that should go after the TRY. 524 SmallPtrSet<const MachineInstr *, 4> AfterSet; 525 for (const auto &MI : *Header) { 526 // If there is a previously placed LOOP marker and the bottom block of the 527 // loop is above MBB, it should be after the TRY, because the loop is nested 528 // in this TRY. Otherwise it should be before the TRY. 529 if (MI.getOpcode() == WebAssembly::LOOP) { 530 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode(); 531 if (MBB.getNumber() > LoopBottom->getNumber()) 532 AfterSet.insert(&MI); 533 #ifndef NDEBUG 534 else 535 BeforeSet.insert(&MI); 536 #endif 537 } 538 539 // All previously inserted BLOCK/TRY markers should be after the TRY because 540 // they are all nested trys. 541 if (MI.getOpcode() == WebAssembly::BLOCK || 542 MI.getOpcode() == WebAssembly::TRY) 543 AfterSet.insert(&MI); 544 545 #ifndef NDEBUG 546 // All END_(BLOCK/LOOP/TRY) markers should be before the TRY. 547 if (MI.getOpcode() == WebAssembly::END_BLOCK || 548 MI.getOpcode() == WebAssembly::END_LOOP || 549 MI.getOpcode() == WebAssembly::END_TRY) 550 BeforeSet.insert(&MI); 551 #endif 552 553 // Terminators should go after the TRY. 554 if (MI.isTerminator()) 555 AfterSet.insert(&MI); 556 } 557 558 // If Header unwinds to MBB (= Header contains 'invoke'), the try block should 559 // contain the call within it. So the call should go after the TRY. The 560 // exception is when the header's terminator is a rethrow instruction, in 561 // which case that instruction, not a call instruction before it, is gonna 562 // throw. 563 MachineInstr *ThrowingCall = nullptr; 564 if (MBB.isPredecessor(Header)) { 565 auto TermPos = Header->getFirstTerminator(); 566 if (TermPos == Header->end() || 567 TermPos->getOpcode() != WebAssembly::RETHROW) { 568 for (auto &MI : reverse(*Header)) { 569 if (MI.isCall()) { 570 AfterSet.insert(&MI); 571 ThrowingCall = &MI; 572 // Possibly throwing calls are usually wrapped by EH_LABEL 573 // instructions. We don't want to split them and the call. 574 if (MI.getIterator() != Header->begin() && 575 std::prev(MI.getIterator())->isEHLabel()) { 576 AfterSet.insert(&*std::prev(MI.getIterator())); 577 ThrowingCall = &*std::prev(MI.getIterator()); 578 } 579 break; 580 } 581 } 582 } 583 } 584 585 // Local expression tree should go after the TRY. 586 // For BLOCK placement, we start the search from the previous instruction of a 587 // BB's terminator, but in TRY's case, we should start from the previous 588 // instruction of a call that can throw, or a EH_LABEL that precedes the call, 589 // because the return values of the call's previous instructions can be 590 // stackified and consumed by the throwing call. 591 auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall) 592 : Header->getFirstTerminator(); 593 for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) { 594 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 595 continue; 596 if (WebAssembly::isChild(*std::prev(I), MFI)) 597 AfterSet.insert(&*std::prev(I)); 598 else 599 break; 600 } 601 602 // Add the TRY. 603 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet); 604 MachineInstr *Begin = 605 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 606 TII.get(WebAssembly::TRY)) 607 .addImm(int64_t(WebAssembly::BlockType::Void)); 608 609 // Decide where in Header to put the END_TRY. 610 BeforeSet.clear(); 611 AfterSet.clear(); 612 for (const auto &MI : *Cont) { 613 #ifndef NDEBUG 614 // END_TRY should precede existing LOOP and BLOCK markers. 615 if (MI.getOpcode() == WebAssembly::LOOP || 616 MI.getOpcode() == WebAssembly::BLOCK) 617 AfterSet.insert(&MI); 618 619 // All END_TRY markers placed earlier belong to exceptions that contains 620 // this one. 621 if (MI.getOpcode() == WebAssembly::END_TRY) 622 AfterSet.insert(&MI); 623 #endif 624 625 // If there is a previously placed END_LOOP marker and its header is after 626 // where TRY marker is, this loop is contained within the 'catch' part, so 627 // the END_TRY marker should go after that. Otherwise, the whole try-catch 628 // is contained within this loop, so the END_TRY should go before that. 629 if (MI.getOpcode() == WebAssembly::END_LOOP) { 630 // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they 631 // are in the same BB, LOOP is always before TRY. 632 if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber()) 633 BeforeSet.insert(&MI); 634 #ifndef NDEBUG 635 else 636 AfterSet.insert(&MI); 637 #endif 638 } 639 640 // It is not possible for an END_BLOCK to be already in this block. 641 } 642 643 // Mark the end of the TRY. 644 InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet); 645 MachineInstr *End = 646 BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(), 647 TII.get(WebAssembly::END_TRY)); 648 registerTryScope(Begin, End, &MBB); 649 650 // Track the farthest-spanning scope that ends at this point. We create two 651 // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB 652 // with 'try'). We need to create 'catch' -> 'try' mapping here too because 653 // markers should not span across 'catch'. For example, this should not 654 // happen: 655 // 656 // try 657 // block --| (X) 658 // catch | 659 // end_block --| 660 // end_try 661 for (auto *End : {&MBB, Cont}) 662 updateScopeTops(Header, End); 663 } 664 665 void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) { 666 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 667 668 // When there is an unconditional branch right before a catch instruction and 669 // it branches to the end of end_try marker, we don't need the branch, because 670 // it there is no exception, the control flow transfers to that point anyway. 671 // bb0: 672 // try 673 // ... 674 // br bb2 <- Not necessary 675 // bb1 (ehpad): 676 // catch 677 // ... 678 // bb2: <- Continuation BB 679 // end 680 // 681 // A more involved case: When the BB where 'end' is located is an another EH 682 // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example, 683 // bb0: 684 // try 685 // try 686 // ... 687 // br bb3 <- Not necessary 688 // bb1 (ehpad): 689 // catch 690 // bb2 (ehpad): 691 // end 692 // catch 693 // ... 694 // bb3: <- Continuation BB 695 // end 696 // 697 // When the EH pad at hand is bb1, its matching end_try is in bb2. But it is 698 // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the 699 // code can be deleted. This is why we run 'while' until 'Cont' is not an EH 700 // pad. 701 for (auto &MBB : MF) { 702 if (!MBB.isEHPad()) 703 continue; 704 705 MachineBasicBlock *TBB = nullptr, *FBB = nullptr; 706 SmallVector<MachineOperand, 4> Cond; 707 MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode(); 708 709 MachineBasicBlock *Cont = &MBB; 710 while (Cont->isEHPad()) { 711 MachineInstr *Try = EHPadToTry[Cont]; 712 MachineInstr *EndTry = BeginToEnd[Try]; 713 // We started from an EH pad, so the end marker cannot be a delegate 714 assert(EndTry->getOpcode() != WebAssembly::DELEGATE); 715 Cont = EndTry->getParent(); 716 } 717 718 bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond); 719 // This condition means either 720 // 1. This BB ends with a single unconditional branch whose destinaion is 721 // Cont. 722 // 2. This BB ends with a conditional branch followed by an unconditional 723 // branch, and the unconditional branch's destination is Cont. 724 // In both cases, we want to remove the last (= unconditional) branch. 725 if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) || 726 (!Cond.empty() && FBB && FBB == Cont))) { 727 bool ErasedUncondBr = false; 728 (void)ErasedUncondBr; 729 for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin(); 730 I != E; --I) { 731 auto PrevI = std::prev(I); 732 if (PrevI->isTerminator()) { 733 assert(PrevI->getOpcode() == WebAssembly::BR); 734 PrevI->eraseFromParent(); 735 ErasedUncondBr = true; 736 break; 737 } 738 } 739 assert(ErasedUncondBr && "Unconditional branch not erased!"); 740 } 741 } 742 743 // When there are block / end_block markers that overlap with try / end_try 744 // markers, and the block and try markers' return types are the same, the 745 // block /end_block markers are not necessary, because try / end_try markers 746 // also can serve as boundaries for branches. 747 // block <- Not necessary 748 // try 749 // ... 750 // catch 751 // ... 752 // end 753 // end <- Not necessary 754 SmallVector<MachineInstr *, 32> ToDelete; 755 for (auto &MBB : MF) { 756 for (auto &MI : MBB) { 757 if (MI.getOpcode() != WebAssembly::TRY) 758 continue; 759 MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try]; 760 if (EndTry->getOpcode() == WebAssembly::DELEGATE) 761 continue; 762 763 MachineBasicBlock *TryBB = Try->getParent(); 764 MachineBasicBlock *Cont = EndTry->getParent(); 765 int64_t RetType = Try->getOperand(0).getImm(); 766 for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator()); 767 B != TryBB->begin() && E != Cont->end() && 768 std::prev(B)->getOpcode() == WebAssembly::BLOCK && 769 E->getOpcode() == WebAssembly::END_BLOCK && 770 std::prev(B)->getOperand(0).getImm() == RetType; 771 --B, ++E) { 772 ToDelete.push_back(&*std::prev(B)); 773 ToDelete.push_back(&*E); 774 } 775 } 776 } 777 for (auto *MI : ToDelete) { 778 if (MI->getOpcode() == WebAssembly::BLOCK) 779 unregisterScope(MI); 780 MI->eraseFromParent(); 781 } 782 } 783 784 // Get the appropriate copy opcode for the given register class. 785 static unsigned getCopyOpcode(const TargetRegisterClass *RC) { 786 if (RC == &WebAssembly::I32RegClass) 787 return WebAssembly::COPY_I32; 788 if (RC == &WebAssembly::I64RegClass) 789 return WebAssembly::COPY_I64; 790 if (RC == &WebAssembly::F32RegClass) 791 return WebAssembly::COPY_F32; 792 if (RC == &WebAssembly::F64RegClass) 793 return WebAssembly::COPY_F64; 794 if (RC == &WebAssembly::V128RegClass) 795 return WebAssembly::COPY_V128; 796 if (RC == &WebAssembly::FUNCREFRegClass) 797 return WebAssembly::COPY_FUNCREF; 798 if (RC == &WebAssembly::EXTERNREFRegClass) 799 return WebAssembly::COPY_EXTERNREF; 800 llvm_unreachable("Unexpected register class"); 801 } 802 803 // When MBB is split into MBB and Split, we should unstackify defs in MBB that 804 // have their uses in Split. 805 static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, 806 MachineBasicBlock &Split) { 807 MachineFunction &MF = *MBB.getParent(); 808 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 809 auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 810 auto &MRI = MF.getRegInfo(); 811 812 for (auto &MI : Split) { 813 for (auto &MO : MI.explicit_uses()) { 814 if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg())) 815 continue; 816 if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg())) 817 if (Def->getParent() == &MBB) 818 MFI.unstackifyVReg(MO.getReg()); 819 } 820 } 821 822 // In RegStackify, when a register definition is used multiple times, 823 // Reg = INST ... 824 // INST ..., Reg, ... 825 // INST ..., Reg, ... 826 // INST ..., Reg, ... 827 // 828 // we introduce a TEE, which has the following form: 829 // DefReg = INST ... 830 // TeeReg, Reg = TEE_... DefReg 831 // INST ..., TeeReg, ... 832 // INST ..., Reg, ... 833 // INST ..., Reg, ... 834 // with DefReg and TeeReg stackified but Reg not stackified. 835 // 836 // But the invariant that TeeReg should be stackified can be violated while we 837 // unstackify registers in the split BB above. In this case, we convert TEEs 838 // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals. 839 // DefReg = INST ... 840 // TeeReg = COPY DefReg 841 // Reg = COPY DefReg 842 // INST ..., TeeReg, ... 843 // INST ..., Reg, ... 844 // INST ..., Reg, ... 845 for (auto I = MBB.begin(), E = MBB.end(); I != E;) { 846 MachineInstr &MI = *I++; 847 if (!WebAssembly::isTee(MI.getOpcode())) 848 continue; 849 Register TeeReg = MI.getOperand(0).getReg(); 850 Register Reg = MI.getOperand(1).getReg(); 851 Register DefReg = MI.getOperand(2).getReg(); 852 if (!MFI.isVRegStackified(TeeReg)) { 853 // Now we are not using TEE anymore, so unstackify DefReg too 854 MFI.unstackifyVReg(DefReg); 855 unsigned CopyOpc = getCopyOpcode(MRI.getRegClass(DefReg)); 856 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg) 857 .addReg(DefReg); 858 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg); 859 MI.eraseFromParent(); 860 } 861 } 862 } 863 864 // Wrap the given range of instruction with try-delegate. RangeBegin and 865 // RangeEnd are inclusive. 866 void WebAssemblyCFGStackify::addTryDelegate(MachineInstr *RangeBegin, 867 MachineInstr *RangeEnd, 868 MachineBasicBlock *DelegateDest) { 869 auto *BeginBB = RangeBegin->getParent(); 870 auto *EndBB = RangeEnd->getParent(); 871 MachineFunction &MF = *BeginBB->getParent(); 872 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 873 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 874 875 // Local expression tree before the first call of this range should go 876 // after the nested TRY. 877 SmallPtrSet<const MachineInstr *, 4> AfterSet; 878 AfterSet.insert(RangeBegin); 879 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin(); 880 I != E; --I) { 881 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 882 continue; 883 if (WebAssembly::isChild(*std::prev(I), MFI)) 884 AfterSet.insert(&*std::prev(I)); 885 else 886 break; 887 } 888 889 // Create the nested try instruction. 890 auto TryPos = getLatestInsertPos( 891 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet); 892 MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(), 893 TII.get(WebAssembly::TRY)) 894 .addImm(int64_t(WebAssembly::BlockType::Void)); 895 896 // Create a BB to insert the 'delegate' instruction. 897 MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock(); 898 // If the destination of 'delegate' is not the caller, adds the destination to 899 // the BB's successors. 900 if (DelegateDest != FakeCallerBB) 901 DelegateBB->addSuccessor(DelegateDest); 902 903 auto SplitPos = std::next(RangeEnd->getIterator()); 904 if (SplitPos == EndBB->end()) { 905 // If the range's end instruction is at the end of the BB, insert the new 906 // delegate BB after the current BB. 907 MF.insert(std::next(EndBB->getIterator()), DelegateBB); 908 EndBB->addSuccessor(DelegateBB); 909 910 } else { 911 // When the split pos is in the middle of a BB, we split the BB into two and 912 // put the 'delegate' BB in between. We normally create a split BB and make 913 // it a successor of the original BB (PostSplit == true), but in case the BB 914 // is an EH pad and the split pos is before 'catch', we should preserve the 915 // BB's property, including that it is an EH pad, in the later part of the 916 // BB, where 'catch' is. In this case we set PostSplit to false. 917 bool PostSplit = true; 918 if (EndBB->isEHPad()) { 919 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end(); 920 I != E; ++I) { 921 if (WebAssembly::isCatch(I->getOpcode())) { 922 PostSplit = false; 923 break; 924 } 925 } 926 } 927 928 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr; 929 if (PostSplit) { 930 // If the range's end instruction is in the middle of the BB, we split the 931 // BB into two and insert the delegate BB in between. 932 // - Before: 933 // bb: 934 // range_end 935 // other_insts 936 // 937 // - After: 938 // pre_bb: (previous 'bb') 939 // range_end 940 // delegate_bb: (new) 941 // delegate 942 // post_bb: (new) 943 // other_insts 944 PreBB = EndBB; 945 PostBB = MF.CreateMachineBasicBlock(); 946 MF.insert(std::next(PreBB->getIterator()), PostBB); 947 MF.insert(std::next(PreBB->getIterator()), DelegateBB); 948 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end()); 949 PostBB->transferSuccessors(PreBB); 950 } else { 951 // - Before: 952 // ehpad: 953 // range_end 954 // catch 955 // ... 956 // 957 // - After: 958 // pre_bb: (new) 959 // range_end 960 // delegate_bb: (new) 961 // delegate 962 // post_bb: (previous 'ehpad') 963 // catch 964 // ... 965 assert(EndBB->isEHPad()); 966 PreBB = MF.CreateMachineBasicBlock(); 967 PostBB = EndBB; 968 MF.insert(PostBB->getIterator(), PreBB); 969 MF.insert(PostBB->getIterator(), DelegateBB); 970 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos); 971 // We don't need to transfer predecessors of the EH pad to 'PreBB', 972 // because an EH pad's predecessors are all through unwind edges and they 973 // should still unwind to the EH pad, not PreBB. 974 } 975 unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB); 976 PreBB->addSuccessor(DelegateBB); 977 PreBB->addSuccessor(PostBB); 978 } 979 980 // Add 'delegate' instruction in the delegate BB created above. 981 MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(), 982 TII.get(WebAssembly::DELEGATE)) 983 .addMBB(DelegateDest); 984 registerTryScope(Try, Delegate, nullptr); 985 } 986 987 bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) { 988 // Linearizing the control flow by placing TRY / END_TRY markers can create 989 // mismatches in unwind destinations for throwing instructions, such as calls. 990 // 991 // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate' 992 // instruction delegates an exception to an outer 'catch'. It can target not 993 // only 'catch' but all block-like structures including another 'delegate', 994 // but with slightly different semantics than branches. When it targets a 995 // 'catch', it will delegate the exception to that catch. It is being 996 // discussed how to define the semantics when 'delegate''s target is a non-try 997 // block: it will either be a validation failure or it will target the next 998 // outer try-catch. But anyway our LLVM backend currently does not generate 999 // such code. The example below illustrates where the 'delegate' instruction 1000 // in the middle will delegate the exception to, depending on the value of N. 1001 // try 1002 // try 1003 // block 1004 // try 1005 // try 1006 // call @foo 1007 // delegate N ;; Where will this delegate to? 1008 // catch ;; N == 0 1009 // end 1010 // end ;; N == 1 (invalid; will not be generated) 1011 // delegate ;; N == 2 1012 // catch ;; N == 3 1013 // end 1014 // ;; N == 4 (to caller) 1015 1016 // 1. When an instruction may throw, but the EH pad it will unwind to can be 1017 // different from the original CFG. 1018 // 1019 // Example: we have the following CFG: 1020 // bb0: 1021 // call @foo ; if it throws, unwind to bb2 1022 // bb1: 1023 // call @bar ; if it throws, unwind to bb3 1024 // bb2 (ehpad): 1025 // catch 1026 // ... 1027 // bb3 (ehpad) 1028 // catch 1029 // ... 1030 // 1031 // And the CFG is sorted in this order. Then after placing TRY markers, it 1032 // will look like: (BB markers are omitted) 1033 // try 1034 // try 1035 // call @foo 1036 // call @bar ;; if it throws, unwind to bb3 1037 // catch ;; ehpad (bb2) 1038 // ... 1039 // end_try 1040 // catch ;; ehpad (bb3) 1041 // ... 1042 // end_try 1043 // 1044 // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it 1045 // is supposed to end up. We solve this problem by wrapping the mismatching 1046 // call with an inner try-delegate that rethrows the exception to the right 1047 // 'catch'. 1048 // 1049 // try 1050 // try 1051 // call @foo 1052 // try ;; (new) 1053 // call @bar 1054 // delegate 1 (bb3) ;; (new) 1055 // catch ;; ehpad (bb2) 1056 // ... 1057 // end_try 1058 // catch ;; ehpad (bb3) 1059 // ... 1060 // end_try 1061 // 1062 // --- 1063 // 2. The same as 1, but in this case an instruction unwinds to a caller 1064 // function and not another EH pad. 1065 // 1066 // Example: we have the following CFG: 1067 // bb0: 1068 // call @foo ; if it throws, unwind to bb2 1069 // bb1: 1070 // call @bar ; if it throws, unwind to caller 1071 // bb2 (ehpad): 1072 // catch 1073 // ... 1074 // 1075 // And the CFG is sorted in this order. Then after placing TRY markers, it 1076 // will look like: 1077 // try 1078 // call @foo 1079 // call @bar ;; if it throws, unwind to caller 1080 // catch ;; ehpad (bb2) 1081 // ... 1082 // end_try 1083 // 1084 // Now if bar() throws, it is going to end up ip in bb2, when it is supposed 1085 // throw up to the caller. We solve this problem in the same way, but in this 1086 // case 'delegate's immediate argument is the number of block depths + 1, 1087 // which means it rethrows to the caller. 1088 // try 1089 // call @foo 1090 // try ;; (new) 1091 // call @bar 1092 // delegate 1 (caller) ;; (new) 1093 // catch ;; ehpad (bb2) 1094 // ... 1095 // end_try 1096 // 1097 // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the 1098 // caller, it will take a fake BB generated by getFakeCallerBlock(), which 1099 // will be converted to a correct immediate argument later. 1100 // 1101 // In case there are multiple calls in a BB that may throw to the caller, they 1102 // can be wrapped together in one nested try-delegate scope. (In 1, this 1103 // couldn't happen, because may-throwing instruction there had an unwind 1104 // destination, i.e., it was an invoke before, and there could be only one 1105 // invoke within a BB.) 1106 1107 SmallVector<const MachineBasicBlock *, 8> EHPadStack; 1108 // Range of intructions to be wrapped in a new nested try/catch. A range 1109 // exists in a single BB and does not span multiple BBs. 1110 using TryRange = std::pair<MachineInstr *, MachineInstr *>; 1111 // In original CFG, <unwind destination BB, a vector of try ranges> 1112 DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges; 1113 1114 // Gather possibly throwing calls (i.e., previously invokes) whose current 1115 // unwind destination is not the same as the original CFG. (Case 1) 1116 1117 for (auto &MBB : reverse(MF)) { 1118 bool SeenThrowableInstInBB = false; 1119 for (auto &MI : reverse(MBB)) { 1120 if (MI.getOpcode() == WebAssembly::TRY) 1121 EHPadStack.pop_back(); 1122 else if (WebAssembly::isCatch(MI.getOpcode())) 1123 EHPadStack.push_back(MI.getParent()); 1124 1125 // In this loop we only gather calls that have an EH pad to unwind. So 1126 // there will be at most 1 such call (= invoke) in a BB, so after we've 1127 // seen one, we can skip the rest of BB. Also if MBB has no EH pad 1128 // successor or MI does not throw, this is not an invoke. 1129 if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() || 1130 !WebAssembly::mayThrow(MI)) 1131 continue; 1132 SeenThrowableInstInBB = true; 1133 1134 // If the EH pad on the stack top is where this instruction should unwind 1135 // next, we're good. 1136 MachineBasicBlock *UnwindDest = getFakeCallerBlock(MF); 1137 for (auto *Succ : MBB.successors()) { 1138 // Even though semantically a BB can have multiple successors in case an 1139 // exception is not caught by a catchpad, in our backend implementation 1140 // it is guaranteed that a BB can have at most one EH pad successor. For 1141 // details, refer to comments in findWasmUnwindDestinations function in 1142 // SelectionDAGBuilder.cpp. 1143 if (Succ->isEHPad()) { 1144 UnwindDest = Succ; 1145 break; 1146 } 1147 } 1148 if (EHPadStack.back() == UnwindDest) 1149 continue; 1150 1151 // Include EH_LABELs in the range before and afer the invoke 1152 MachineInstr *RangeBegin = &MI, *RangeEnd = &MI; 1153 if (RangeBegin->getIterator() != MBB.begin() && 1154 std::prev(RangeBegin->getIterator())->isEHLabel()) 1155 RangeBegin = &*std::prev(RangeBegin->getIterator()); 1156 if (std::next(RangeEnd->getIterator()) != MBB.end() && 1157 std::next(RangeEnd->getIterator())->isEHLabel()) 1158 RangeEnd = &*std::next(RangeEnd->getIterator()); 1159 1160 // If not, record the range. 1161 UnwindDestToTryRanges[UnwindDest].push_back( 1162 TryRange(RangeBegin, RangeEnd)); 1163 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName() 1164 << "\nCall = " << MI 1165 << "\nOriginal dest = " << UnwindDest->getName() 1166 << " Current dest = " << EHPadStack.back()->getName() 1167 << "\n\n"); 1168 } 1169 } 1170 1171 assert(EHPadStack.empty()); 1172 1173 // Gather possibly throwing calls that are supposed to unwind up to the caller 1174 // if they throw, but currently unwind to an incorrect destination. Unlike the 1175 // loop above, there can be multiple calls within a BB that unwind to the 1176 // caller, which we should group together in a range. (Case 2) 1177 1178 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive 1179 1180 // Record the range. 1181 auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) { 1182 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back( 1183 TryRange(RangeBegin, RangeEnd)); 1184 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " 1185 << RangeBegin->getParent()->getName() 1186 << "\nRange begin = " << *RangeBegin 1187 << "Range end = " << *RangeEnd 1188 << "\nOriginal dest = caller Current dest = " 1189 << CurrentDest->getName() << "\n\n"); 1190 RangeBegin = RangeEnd = nullptr; // Reset range pointers 1191 }; 1192 1193 for (auto &MBB : reverse(MF)) { 1194 bool SeenThrowableInstInBB = false; 1195 for (auto &MI : reverse(MBB)) { 1196 bool MayThrow = WebAssembly::mayThrow(MI); 1197 1198 // If MBB has an EH pad successor and this is the last instruction that 1199 // may throw, this instruction unwinds to the EH pad and not to the 1200 // caller. 1201 if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB) 1202 SeenThrowableInstInBB = true; 1203 1204 // We wrap up the current range when we see a marker even if we haven't 1205 // finished a BB. 1206 else if (RangeEnd && WebAssembly::isMarker(MI.getOpcode())) 1207 RecordCallerMismatchRange(EHPadStack.back()); 1208 1209 // If EHPadStack is empty, that means it correctly unwinds to the caller 1210 // if it throws, so we're good. If MI does not throw, we're good too. 1211 else if (EHPadStack.empty() || !MayThrow) { 1212 } 1213 1214 // We found an instruction that unwinds to the caller but currently has an 1215 // incorrect unwind destination. Create a new range or increment the 1216 // currently existing range. 1217 else { 1218 if (!RangeEnd) 1219 RangeBegin = RangeEnd = &MI; 1220 else 1221 RangeBegin = &MI; 1222 } 1223 1224 // Update EHPadStack. 1225 if (MI.getOpcode() == WebAssembly::TRY) 1226 EHPadStack.pop_back(); 1227 else if (WebAssembly::isCatch(MI.getOpcode())) 1228 EHPadStack.push_back(MI.getParent()); 1229 } 1230 1231 if (RangeEnd) 1232 RecordCallerMismatchRange(EHPadStack.back()); 1233 } 1234 1235 assert(EHPadStack.empty()); 1236 1237 // We don't have any unwind destination mismatches to resolve. 1238 if (UnwindDestToTryRanges.empty()) 1239 return false; 1240 1241 // Now we fix the mismatches by wrapping calls with inner try-delegates. 1242 for (auto &P : UnwindDestToTryRanges) { 1243 NumCallUnwindMismatches += P.second.size(); 1244 MachineBasicBlock *UnwindDest = P.first; 1245 auto &TryRanges = P.second; 1246 1247 for (auto Range : TryRanges) { 1248 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; 1249 std::tie(RangeBegin, RangeEnd) = Range; 1250 auto *MBB = RangeBegin->getParent(); 1251 1252 // If this BB has an EH pad successor, i.e., ends with an 'invoke', now we 1253 // are going to wrap the invoke with try-delegate, making the 'delegate' 1254 // BB the new successor instead, so remove the EH pad succesor here. The 1255 // BB may not have an EH pad successor if calls in this BB throw to the 1256 // caller. 1257 MachineBasicBlock *EHPad = nullptr; 1258 for (auto *Succ : MBB->successors()) { 1259 if (Succ->isEHPad()) { 1260 EHPad = Succ; 1261 break; 1262 } 1263 } 1264 if (EHPad) 1265 MBB->removeSuccessor(EHPad); 1266 1267 addTryDelegate(RangeBegin, RangeEnd, UnwindDest); 1268 } 1269 } 1270 1271 return true; 1272 } 1273 1274 bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) { 1275 // There is another kind of unwind destination mismatches besides call unwind 1276 // mismatches, which we will call "catch unwind mismatches". See this example 1277 // after the marker placement: 1278 // try 1279 // try 1280 // call @foo 1281 // catch __cpp_exception ;; ehpad A (next unwind dest: caller) 1282 // ... 1283 // end_try 1284 // catch_all ;; ehpad B 1285 // ... 1286 // end_try 1287 // 1288 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo' 1289 // throws a foreign exception that is not caught by ehpad A, and its next 1290 // destination should be the caller. But after control flow linearization, 1291 // another EH pad can be placed in between (e.g. ehpad B here), making the 1292 // next unwind destination incorrect. In this case, the foreign exception 1293 // will instead go to ehpad B and will be caught there instead. In this 1294 // example the correct next unwind destination is the caller, but it can be 1295 // another outer catch in other cases. 1296 // 1297 // There is no specific 'call' or 'throw' instruction to wrap with a 1298 // try-delegate, so we wrap the whole try-catch-end with a try-delegate and 1299 // make it rethrow to the right destination, as in the example below: 1300 // try 1301 // try ;; (new) 1302 // try 1303 // call @foo 1304 // catch __cpp_exception ;; ehpad A (next unwind dest: caller) 1305 // ... 1306 // end_try 1307 // delegate 1 (caller) ;; (new) 1308 // catch_all ;; ehpad B 1309 // ... 1310 // end_try 1311 1312 const auto *EHInfo = MF.getWasmEHFuncInfo(); 1313 SmallVector<const MachineBasicBlock *, 8> EHPadStack; 1314 // For EH pads that have catch unwind mismatches, a map of <EH pad, its 1315 // correct unwind destination>. 1316 DenseMap<MachineBasicBlock *, MachineBasicBlock *> EHPadToUnwindDest; 1317 1318 for (auto &MBB : reverse(MF)) { 1319 for (auto &MI : reverse(MBB)) { 1320 if (MI.getOpcode() == WebAssembly::TRY) 1321 EHPadStack.pop_back(); 1322 else if (MI.getOpcode() == WebAssembly::DELEGATE) 1323 EHPadStack.push_back(&MBB); 1324 else if (WebAssembly::isCatch(MI.getOpcode())) { 1325 auto *EHPad = &MBB; 1326 1327 // catch_all always catches an exception, so we don't need to do 1328 // anything 1329 if (MI.getOpcode() == WebAssembly::CATCH_ALL) { 1330 } 1331 1332 // This can happen when the unwind dest was removed during the 1333 // optimization, e.g. because it was unreachable. 1334 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) { 1335 LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName() 1336 << "'s unwind destination does not exist anymore" 1337 << "\n\n"); 1338 } 1339 1340 // The EHPad's next unwind destination is the caller, but we incorrectly 1341 // unwind to another EH pad. 1342 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) { 1343 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF); 1344 LLVM_DEBUG(dbgs() 1345 << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName() 1346 << " Original dest = caller Current dest = " 1347 << EHPadStack.back()->getName() << "\n\n"); 1348 } 1349 1350 // The EHPad's next unwind destination is an EH pad, whereas we 1351 // incorrectly unwind to another EH pad. 1352 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) { 1353 auto *UnwindDest = EHInfo->getUnwindDest(EHPad); 1354 if (EHPadStack.back() != UnwindDest) { 1355 EHPadToUnwindDest[EHPad] = UnwindDest; 1356 LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = " 1357 << EHPad->getName() << " Original dest = " 1358 << UnwindDest->getName() << " Current dest = " 1359 << EHPadStack.back()->getName() << "\n\n"); 1360 } 1361 } 1362 1363 EHPadStack.push_back(EHPad); 1364 } 1365 } 1366 } 1367 1368 assert(EHPadStack.empty()); 1369 if (EHPadToUnwindDest.empty()) 1370 return false; 1371 NumCatchUnwindMismatches += EHPadToUnwindDest.size(); 1372 SmallPtrSet<MachineBasicBlock *, 4> NewEndTryBBs; 1373 1374 for (auto &P : EHPadToUnwindDest) { 1375 MachineBasicBlock *EHPad = P.first; 1376 MachineBasicBlock *UnwindDest = P.second; 1377 MachineInstr *Try = EHPadToTry[EHPad]; 1378 MachineInstr *EndTry = BeginToEnd[Try]; 1379 addTryDelegate(Try, EndTry, UnwindDest); 1380 NewEndTryBBs.insert(EndTry->getParent()); 1381 } 1382 1383 // Adding a try-delegate wrapping an existing try-catch-end can make existing 1384 // branch destination BBs invalid. For example, 1385 // 1386 // - Before: 1387 // bb0: 1388 // block 1389 // br bb3 1390 // bb1: 1391 // try 1392 // ... 1393 // bb2: (ehpad) 1394 // catch 1395 // bb3: 1396 // end_try 1397 // end_block ;; 'br bb3' targets here 1398 // 1399 // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap 1400 // this with a try-delegate. Then this becomes: 1401 // 1402 // - After: 1403 // bb0: 1404 // block 1405 // br bb3 ;; invalid destination! 1406 // bb1: 1407 // try ;; (new instruction) 1408 // try 1409 // ... 1410 // bb2: (ehpad) 1411 // catch 1412 // bb3: 1413 // end_try ;; 'br bb3' still incorrectly targets here! 1414 // delegate_bb: ;; (new BB) 1415 // delegate ;; (new instruction) 1416 // split_bb: ;; (new BB) 1417 // end_block 1418 // 1419 // Now 'br bb3' incorrectly branches to an inner scope. 1420 // 1421 // As we can see in this case, when branches target a BB that has both 1422 // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we 1423 // have to remap existing branch destinations so that they target not the 1424 // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's 1425 // in between, so we try to find the next BB with 'end_block' instruction. In 1426 // this example, the 'br bb3' instruction should be remapped to 'br split_bb'. 1427 for (auto &MBB : MF) { 1428 for (auto &MI : MBB) { 1429 if (MI.isTerminator()) { 1430 for (auto &MO : MI.operands()) { 1431 if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) { 1432 auto *BrDest = MO.getMBB(); 1433 bool FoundEndBlock = false; 1434 for (; std::next(BrDest->getIterator()) != MF.end(); 1435 BrDest = BrDest->getNextNode()) { 1436 for (const auto &MI : *BrDest) { 1437 if (MI.getOpcode() == WebAssembly::END_BLOCK) { 1438 FoundEndBlock = true; 1439 break; 1440 } 1441 } 1442 if (FoundEndBlock) 1443 break; 1444 } 1445 assert(FoundEndBlock); 1446 MO.setMBB(BrDest); 1447 } 1448 } 1449 } 1450 } 1451 } 1452 1453 return true; 1454 } 1455 1456 void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) { 1457 // Renumber BBs and recalculate ScopeTop info because new BBs might have been 1458 // created and inserted during fixing unwind mismatches. 1459 MF.RenumberBlocks(); 1460 ScopeTops.clear(); 1461 ScopeTops.resize(MF.getNumBlockIDs()); 1462 for (auto &MBB : reverse(MF)) { 1463 for (auto &MI : reverse(MBB)) { 1464 if (ScopeTops[MBB.getNumber()]) 1465 break; 1466 switch (MI.getOpcode()) { 1467 case WebAssembly::END_BLOCK: 1468 case WebAssembly::END_LOOP: 1469 case WebAssembly::END_TRY: 1470 case WebAssembly::DELEGATE: 1471 updateScopeTops(EndToBegin[&MI]->getParent(), &MBB); 1472 break; 1473 case WebAssembly::CATCH: 1474 case WebAssembly::CATCH_ALL: 1475 updateScopeTops(EHPadToTry[&MBB]->getParent(), &MBB); 1476 break; 1477 } 1478 } 1479 } 1480 } 1481 1482 /// In normal assembly languages, when the end of a function is unreachable, 1483 /// because the function ends in an infinite loop or a noreturn call or similar, 1484 /// it isn't necessary to worry about the function return type at the end of 1485 /// the function, because it's never reached. However, in WebAssembly, blocks 1486 /// that end at the function end need to have a return type signature that 1487 /// matches the function signature, even though it's unreachable. This function 1488 /// checks for such cases and fixes up the signatures. 1489 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { 1490 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 1491 1492 if (MFI.getResults().empty()) 1493 return; 1494 1495 // MCInstLower will add the proper types to multivalue signatures based on the 1496 // function return type 1497 WebAssembly::BlockType RetType = 1498 MFI.getResults().size() > 1 1499 ? WebAssembly::BlockType::Multivalue 1500 : WebAssembly::BlockType( 1501 WebAssembly::toValType(MFI.getResults().front())); 1502 1503 SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist; 1504 Worklist.push_back(MF.rbegin()->rbegin()); 1505 1506 auto Process = [&](MachineBasicBlock::reverse_iterator It) { 1507 auto *MBB = It->getParent(); 1508 while (It != MBB->rend()) { 1509 MachineInstr &MI = *It++; 1510 if (MI.isPosition() || MI.isDebugInstr()) 1511 continue; 1512 switch (MI.getOpcode()) { 1513 case WebAssembly::END_TRY: { 1514 // If a 'try''s return type is fixed, both its try body and catch body 1515 // should satisfy the return type, so we need to search 'end' 1516 // instructions before its corresponding 'catch' too. 1517 auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]); 1518 assert(EHPad); 1519 auto NextIt = 1520 std::next(WebAssembly::findCatch(EHPad)->getReverseIterator()); 1521 if (NextIt != EHPad->rend()) 1522 Worklist.push_back(NextIt); 1523 LLVM_FALLTHROUGH; 1524 } 1525 case WebAssembly::END_BLOCK: 1526 case WebAssembly::END_LOOP: 1527 case WebAssembly::DELEGATE: 1528 EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType)); 1529 continue; 1530 default: 1531 // Something other than an `end`. We're done for this BB. 1532 return; 1533 } 1534 } 1535 // We've reached the beginning of a BB. Continue the search in the previous 1536 // BB. 1537 Worklist.push_back(MBB->getPrevNode()->rbegin()); 1538 }; 1539 1540 while (!Worklist.empty()) 1541 Process(Worklist.pop_back_val()); 1542 } 1543 1544 // WebAssembly functions end with an end instruction, as if the function body 1545 // were a block. 1546 static void appendEndToFunction(MachineFunction &MF, 1547 const WebAssemblyInstrInfo &TII) { 1548 BuildMI(MF.back(), MF.back().end(), 1549 MF.back().findPrevDebugLoc(MF.back().end()), 1550 TII.get(WebAssembly::END_FUNCTION)); 1551 } 1552 1553 /// Insert LOOP/TRY/BLOCK markers at appropriate places. 1554 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { 1555 // We allocate one more than the number of blocks in the function to 1556 // accommodate for the possible fake block we may insert at the end. 1557 ScopeTops.resize(MF.getNumBlockIDs() + 1); 1558 // Place the LOOP for MBB if MBB is the header of a loop. 1559 for (auto &MBB : MF) 1560 placeLoopMarker(MBB); 1561 1562 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 1563 for (auto &MBB : MF) { 1564 if (MBB.isEHPad()) { 1565 // Place the TRY for MBB if MBB is the EH pad of an exception. 1566 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1567 MF.getFunction().hasPersonalityFn()) 1568 placeTryMarker(MBB); 1569 } else { 1570 // Place the BLOCK for MBB if MBB is branched to from above. 1571 placeBlockMarker(MBB); 1572 } 1573 } 1574 // Fix mismatches in unwind destinations induced by linearizing the code. 1575 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1576 MF.getFunction().hasPersonalityFn()) { 1577 bool Changed = fixCallUnwindMismatches(MF); 1578 Changed |= fixCatchUnwindMismatches(MF); 1579 if (Changed) 1580 recalculateScopeTops(MF); 1581 } 1582 } 1583 1584 unsigned WebAssemblyCFGStackify::getBranchDepth( 1585 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) { 1586 unsigned Depth = 0; 1587 for (auto X : reverse(Stack)) { 1588 if (X.first == MBB) 1589 break; 1590 ++Depth; 1591 } 1592 assert(Depth < Stack.size() && "Branch destination should be in scope"); 1593 return Depth; 1594 } 1595 1596 unsigned WebAssemblyCFGStackify::getDelegateDepth( 1597 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) { 1598 if (MBB == FakeCallerBB) 1599 return Stack.size(); 1600 // Delegate's destination is either a catch or a another delegate BB. When the 1601 // destination is another delegate, we can compute the argument in the same 1602 // way as branches, because the target delegate BB only contains the single 1603 // delegate instruction. 1604 if (!MBB->isEHPad()) // Target is a delegate BB 1605 return getBranchDepth(Stack, MBB); 1606 1607 // When the delegate's destination is a catch BB, we need to use its 1608 // corresponding try's end_try BB because Stack contains each marker's end BB. 1609 // Also we need to check if the end marker instruction matches, because a 1610 // single BB can contain multiple end markers, like this: 1611 // bb: 1612 // END_BLOCK 1613 // END_TRY 1614 // END_BLOCK 1615 // END_TRY 1616 // ... 1617 // 1618 // In case of branches getting the immediate that targets any of these is 1619 // fine, but delegate has to exactly target the correct try. 1620 unsigned Depth = 0; 1621 const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]]; 1622 for (auto X : reverse(Stack)) { 1623 if (X.first == EndTry->getParent() && X.second == EndTry) 1624 break; 1625 ++Depth; 1626 } 1627 assert(Depth < Stack.size() && "Delegate destination should be in scope"); 1628 return Depth; 1629 } 1630 1631 unsigned WebAssemblyCFGStackify::getRethrowDepth( 1632 const SmallVectorImpl<EndMarkerInfo> &Stack, 1633 const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack) { 1634 unsigned Depth = 0; 1635 // In our current implementation, rethrows always rethrow the exception caught 1636 // by the innermost enclosing catch. This means while traversing Stack in the 1637 // reverse direction, when we encounter END_TRY, we should check if the 1638 // END_TRY corresponds to the current innermost EH pad. For example: 1639 // try 1640 // ... 1641 // catch ;; (a) 1642 // try 1643 // rethrow 1 ;; (b) 1644 // catch ;; (c) 1645 // rethrow 0 ;; (d) 1646 // end ;; (e) 1647 // end ;; (f) 1648 // 1649 // When we are at 'rethrow' (d), while reversely traversing Stack the first 1650 // 'end' we encounter is the 'end' (e), which corresponds to the 'catch' (c). 1651 // And 'rethrow' (d) rethrows the exception caught by 'catch' (c), so we stop 1652 // there and the depth should be 0. But when we are at 'rethrow' (b), it 1653 // rethrows the exception caught by 'catch' (a), so when traversing Stack 1654 // reversely, we should skip the 'end' (e) and choose 'end' (f), which 1655 // corresponds to 'catch' (a). 1656 for (auto X : reverse(Stack)) { 1657 const MachineInstr *End = X.second; 1658 if (End->getOpcode() == WebAssembly::END_TRY) { 1659 auto *EHPad = TryToEHPad[EndToBegin[End]]; 1660 if (EHPadStack.back() == EHPad) 1661 break; 1662 } 1663 ++Depth; 1664 } 1665 assert(Depth < Stack.size() && "Rethrow destination should be in scope"); 1666 return Depth; 1667 } 1668 1669 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { 1670 // Now rewrite references to basic blocks to be depth immediates. 1671 SmallVector<EndMarkerInfo, 8> Stack; 1672 SmallVector<const MachineBasicBlock *, 8> EHPadStack; 1673 for (auto &MBB : reverse(MF)) { 1674 for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) { 1675 MachineInstr &MI = *I; 1676 switch (MI.getOpcode()) { 1677 case WebAssembly::BLOCK: 1678 case WebAssembly::TRY: 1679 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <= 1680 MBB.getNumber() && 1681 "Block/try marker should be balanced"); 1682 Stack.pop_back(); 1683 break; 1684 1685 case WebAssembly::LOOP: 1686 assert(Stack.back().first == &MBB && "Loop top should be balanced"); 1687 Stack.pop_back(); 1688 break; 1689 1690 case WebAssembly::END_BLOCK: 1691 Stack.push_back(std::make_pair(&MBB, &MI)); 1692 break; 1693 1694 case WebAssembly::END_TRY: { 1695 // We handle DELEGATE in the default level, because DELEGATE has 1696 // immediate operands to rewrite. 1697 Stack.push_back(std::make_pair(&MBB, &MI)); 1698 auto *EHPad = TryToEHPad[EndToBegin[&MI]]; 1699 EHPadStack.push_back(EHPad); 1700 break; 1701 } 1702 1703 case WebAssembly::END_LOOP: 1704 Stack.push_back(std::make_pair(EndToBegin[&MI]->getParent(), &MI)); 1705 break; 1706 1707 case WebAssembly::CATCH: 1708 case WebAssembly::CATCH_ALL: 1709 EHPadStack.pop_back(); 1710 break; 1711 1712 case WebAssembly::RETHROW: 1713 MI.getOperand(0).setImm(getRethrowDepth(Stack, EHPadStack)); 1714 break; 1715 1716 default: 1717 if (MI.isTerminator()) { 1718 // Rewrite MBB operands to be depth immediates. 1719 SmallVector<MachineOperand, 4> Ops(MI.operands()); 1720 while (MI.getNumOperands() > 0) 1721 MI.RemoveOperand(MI.getNumOperands() - 1); 1722 for (auto MO : Ops) { 1723 if (MO.isMBB()) { 1724 if (MI.getOpcode() == WebAssembly::DELEGATE) 1725 MO = MachineOperand::CreateImm( 1726 getDelegateDepth(Stack, MO.getMBB())); 1727 else 1728 MO = MachineOperand::CreateImm( 1729 getBranchDepth(Stack, MO.getMBB())); 1730 } 1731 MI.addOperand(MF, MO); 1732 } 1733 } 1734 1735 if (MI.getOpcode() == WebAssembly::DELEGATE) 1736 Stack.push_back(std::make_pair(&MBB, &MI)); 1737 break; 1738 } 1739 } 1740 } 1741 assert(Stack.empty() && "Control flow should be balanced"); 1742 } 1743 1744 void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) { 1745 if (FakeCallerBB) 1746 MF.DeleteMachineBasicBlock(FakeCallerBB); 1747 AppendixBB = FakeCallerBB = nullptr; 1748 } 1749 1750 void WebAssemblyCFGStackify::releaseMemory() { 1751 ScopeTops.clear(); 1752 BeginToEnd.clear(); 1753 EndToBegin.clear(); 1754 TryToEHPad.clear(); 1755 EHPadToTry.clear(); 1756 } 1757 1758 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 1759 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n" 1760 "********** Function: " 1761 << MF.getName() << '\n'); 1762 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 1763 1764 releaseMemory(); 1765 1766 // Liveness is not tracked for VALUE_STACK physreg. 1767 MF.getRegInfo().invalidateLiveness(); 1768 1769 // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes. 1770 placeMarkers(MF); 1771 1772 // Remove unnecessary instructions possibly introduced by try/end_trys. 1773 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1774 MF.getFunction().hasPersonalityFn()) 1775 removeUnnecessaryInstrs(MF); 1776 1777 // Convert MBB operands in terminators to relative depth immediates. 1778 rewriteDepthImmediates(MF); 1779 1780 // Fix up block/loop/try signatures at the end of the function to conform to 1781 // WebAssembly's rules. 1782 fixEndsAtEndOfFunction(MF); 1783 1784 // Add an end instruction at the end of the function body. 1785 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 1786 if (!MF.getSubtarget<WebAssemblySubtarget>() 1787 .getTargetTriple() 1788 .isOSBinFormatELF()) 1789 appendEndToFunction(MF, TII); 1790 1791 cleanupFunctionData(MF); 1792 1793 MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified(); 1794 return true; 1795 } 1796