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 validation 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 // Validation 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 validation 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 // Validation 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 // When MBB is split into MBB and Split, we should unstackify defs in MBB that 785 // have their uses in Split. 786 static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, 787 MachineBasicBlock &Split) { 788 MachineFunction &MF = *MBB.getParent(); 789 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 790 auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 791 auto &MRI = MF.getRegInfo(); 792 793 for (auto &MI : Split) { 794 for (auto &MO : MI.explicit_uses()) { 795 if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg())) 796 continue; 797 if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg())) 798 if (Def->getParent() == &MBB) 799 MFI.unstackifyVReg(MO.getReg()); 800 } 801 } 802 803 // In RegStackify, when a register definition is used multiple times, 804 // Reg = INST ... 805 // INST ..., Reg, ... 806 // INST ..., Reg, ... 807 // INST ..., Reg, ... 808 // 809 // we introduce a TEE, which has the following form: 810 // DefReg = INST ... 811 // TeeReg, Reg = TEE_... DefReg 812 // INST ..., TeeReg, ... 813 // INST ..., Reg, ... 814 // INST ..., Reg, ... 815 // with DefReg and TeeReg stackified but Reg not stackified. 816 // 817 // But the invariant that TeeReg should be stackified can be violated while we 818 // unstackify registers in the split BB above. In this case, we convert TEEs 819 // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals. 820 // DefReg = INST ... 821 // TeeReg = COPY DefReg 822 // Reg = COPY DefReg 823 // INST ..., TeeReg, ... 824 // INST ..., Reg, ... 825 // INST ..., Reg, ... 826 for (MachineInstr &MI : llvm::make_early_inc_range(MBB)) { 827 if (!WebAssembly::isTee(MI.getOpcode())) 828 continue; 829 Register TeeReg = MI.getOperand(0).getReg(); 830 Register Reg = MI.getOperand(1).getReg(); 831 Register DefReg = MI.getOperand(2).getReg(); 832 if (!MFI.isVRegStackified(TeeReg)) { 833 // Now we are not using TEE anymore, so unstackify DefReg too 834 MFI.unstackifyVReg(DefReg); 835 unsigned CopyOpc = 836 WebAssembly::getCopyOpcodeForRegClass(MRI.getRegClass(DefReg)); 837 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg) 838 .addReg(DefReg); 839 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg); 840 MI.eraseFromParent(); 841 } 842 } 843 } 844 845 // Wrap the given range of instruction with try-delegate. RangeBegin and 846 // RangeEnd are inclusive. 847 void WebAssemblyCFGStackify::addTryDelegate(MachineInstr *RangeBegin, 848 MachineInstr *RangeEnd, 849 MachineBasicBlock *DelegateDest) { 850 auto *BeginBB = RangeBegin->getParent(); 851 auto *EndBB = RangeEnd->getParent(); 852 MachineFunction &MF = *BeginBB->getParent(); 853 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 854 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 855 856 // Local expression tree before the first call of this range should go 857 // after the nested TRY. 858 SmallPtrSet<const MachineInstr *, 4> AfterSet; 859 AfterSet.insert(RangeBegin); 860 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin(); 861 I != E; --I) { 862 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition()) 863 continue; 864 if (WebAssembly::isChild(*std::prev(I), MFI)) 865 AfterSet.insert(&*std::prev(I)); 866 else 867 break; 868 } 869 870 // Create the nested try instruction. 871 auto TryPos = getLatestInsertPos( 872 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet); 873 MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(), 874 TII.get(WebAssembly::TRY)) 875 .addImm(int64_t(WebAssembly::BlockType::Void)); 876 877 // Create a BB to insert the 'delegate' instruction. 878 MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock(); 879 // If the destination of 'delegate' is not the caller, adds the destination to 880 // the BB's successors. 881 if (DelegateDest != FakeCallerBB) 882 DelegateBB->addSuccessor(DelegateDest); 883 884 auto SplitPos = std::next(RangeEnd->getIterator()); 885 if (SplitPos == EndBB->end()) { 886 // If the range's end instruction is at the end of the BB, insert the new 887 // delegate BB after the current BB. 888 MF.insert(std::next(EndBB->getIterator()), DelegateBB); 889 EndBB->addSuccessor(DelegateBB); 890 891 } else { 892 // When the split pos is in the middle of a BB, we split the BB into two and 893 // put the 'delegate' BB in between. We normally create a split BB and make 894 // it a successor of the original BB (PostSplit == true), but in case the BB 895 // is an EH pad and the split pos is before 'catch', we should preserve the 896 // BB's property, including that it is an EH pad, in the later part of the 897 // BB, where 'catch' is. In this case we set PostSplit to false. 898 bool PostSplit = true; 899 if (EndBB->isEHPad()) { 900 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end(); 901 I != E; ++I) { 902 if (WebAssembly::isCatch(I->getOpcode())) { 903 PostSplit = false; 904 break; 905 } 906 } 907 } 908 909 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr; 910 if (PostSplit) { 911 // If the range's end instruction is in the middle of the BB, we split the 912 // BB into two and insert the delegate BB in between. 913 // - Before: 914 // bb: 915 // range_end 916 // other_insts 917 // 918 // - After: 919 // pre_bb: (previous 'bb') 920 // range_end 921 // delegate_bb: (new) 922 // delegate 923 // post_bb: (new) 924 // other_insts 925 PreBB = EndBB; 926 PostBB = MF.CreateMachineBasicBlock(); 927 MF.insert(std::next(PreBB->getIterator()), PostBB); 928 MF.insert(std::next(PreBB->getIterator()), DelegateBB); 929 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end()); 930 PostBB->transferSuccessors(PreBB); 931 } else { 932 // - Before: 933 // ehpad: 934 // range_end 935 // catch 936 // ... 937 // 938 // - After: 939 // pre_bb: (new) 940 // range_end 941 // delegate_bb: (new) 942 // delegate 943 // post_bb: (previous 'ehpad') 944 // catch 945 // ... 946 assert(EndBB->isEHPad()); 947 PreBB = MF.CreateMachineBasicBlock(); 948 PostBB = EndBB; 949 MF.insert(PostBB->getIterator(), PreBB); 950 MF.insert(PostBB->getIterator(), DelegateBB); 951 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos); 952 // We don't need to transfer predecessors of the EH pad to 'PreBB', 953 // because an EH pad's predecessors are all through unwind edges and they 954 // should still unwind to the EH pad, not PreBB. 955 } 956 unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB); 957 PreBB->addSuccessor(DelegateBB); 958 PreBB->addSuccessor(PostBB); 959 } 960 961 // Add 'delegate' instruction in the delegate BB created above. 962 MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(), 963 TII.get(WebAssembly::DELEGATE)) 964 .addMBB(DelegateDest); 965 registerTryScope(Try, Delegate, nullptr); 966 } 967 968 bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) { 969 // Linearizing the control flow by placing TRY / END_TRY markers can create 970 // mismatches in unwind destinations for throwing instructions, such as calls. 971 // 972 // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate' 973 // instruction delegates an exception to an outer 'catch'. It can target not 974 // only 'catch' but all block-like structures including another 'delegate', 975 // but with slightly different semantics than branches. When it targets a 976 // 'catch', it will delegate the exception to that catch. It is being 977 // discussed how to define the semantics when 'delegate''s target is a non-try 978 // block: it will either be a validation failure or it will target the next 979 // outer try-catch. But anyway our LLVM backend currently does not generate 980 // such code. The example below illustrates where the 'delegate' instruction 981 // in the middle will delegate the exception to, depending on the value of N. 982 // try 983 // try 984 // block 985 // try 986 // try 987 // call @foo 988 // delegate N ;; Where will this delegate to? 989 // catch ;; N == 0 990 // end 991 // end ;; N == 1 (invalid; will not be generated) 992 // delegate ;; N == 2 993 // catch ;; N == 3 994 // end 995 // ;; N == 4 (to caller) 996 997 // 1. When an instruction may throw, but the EH pad it will unwind to can be 998 // different from the original CFG. 999 // 1000 // Example: we have the following CFG: 1001 // bb0: 1002 // call @foo ; if it throws, unwind to bb2 1003 // bb1: 1004 // call @bar ; if it throws, unwind to bb3 1005 // bb2 (ehpad): 1006 // catch 1007 // ... 1008 // bb3 (ehpad) 1009 // catch 1010 // ... 1011 // 1012 // And the CFG is sorted in this order. Then after placing TRY markers, it 1013 // will look like: (BB markers are omitted) 1014 // try 1015 // try 1016 // call @foo 1017 // call @bar ;; if it throws, unwind to bb3 1018 // catch ;; ehpad (bb2) 1019 // ... 1020 // end_try 1021 // catch ;; ehpad (bb3) 1022 // ... 1023 // end_try 1024 // 1025 // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it 1026 // is supposed to end up. We solve this problem by wrapping the mismatching 1027 // call with an inner try-delegate that rethrows the exception to the right 1028 // 'catch'. 1029 // 1030 // try 1031 // try 1032 // call @foo 1033 // try ;; (new) 1034 // call @bar 1035 // delegate 1 (bb3) ;; (new) 1036 // catch ;; ehpad (bb2) 1037 // ... 1038 // end_try 1039 // catch ;; ehpad (bb3) 1040 // ... 1041 // end_try 1042 // 1043 // --- 1044 // 2. The same as 1, but in this case an instruction unwinds to a caller 1045 // function and not another EH pad. 1046 // 1047 // Example: we have the following CFG: 1048 // bb0: 1049 // call @foo ; if it throws, unwind to bb2 1050 // bb1: 1051 // call @bar ; if it throws, unwind to caller 1052 // bb2 (ehpad): 1053 // catch 1054 // ... 1055 // 1056 // And the CFG is sorted in this order. Then after placing TRY markers, it 1057 // will look like: 1058 // try 1059 // call @foo 1060 // call @bar ;; if it throws, unwind to caller 1061 // catch ;; ehpad (bb2) 1062 // ... 1063 // end_try 1064 // 1065 // Now if bar() throws, it is going to end up ip in bb2, when it is supposed 1066 // throw up to the caller. We solve this problem in the same way, but in this 1067 // case 'delegate's immediate argument is the number of block depths + 1, 1068 // which means it rethrows to the caller. 1069 // try 1070 // call @foo 1071 // try ;; (new) 1072 // call @bar 1073 // delegate 1 (caller) ;; (new) 1074 // catch ;; ehpad (bb2) 1075 // ... 1076 // end_try 1077 // 1078 // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the 1079 // caller, it will take a fake BB generated by getFakeCallerBlock(), which 1080 // will be converted to a correct immediate argument later. 1081 // 1082 // In case there are multiple calls in a BB that may throw to the caller, they 1083 // can be wrapped together in one nested try-delegate scope. (In 1, this 1084 // couldn't happen, because may-throwing instruction there had an unwind 1085 // destination, i.e., it was an invoke before, and there could be only one 1086 // invoke within a BB.) 1087 1088 SmallVector<const MachineBasicBlock *, 8> EHPadStack; 1089 // Range of intructions to be wrapped in a new nested try/catch. A range 1090 // exists in a single BB and does not span multiple BBs. 1091 using TryRange = std::pair<MachineInstr *, MachineInstr *>; 1092 // In original CFG, <unwind destination BB, a vector of try ranges> 1093 DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges; 1094 1095 // Gather possibly throwing calls (i.e., previously invokes) whose current 1096 // unwind destination is not the same as the original CFG. (Case 1) 1097 1098 for (auto &MBB : reverse(MF)) { 1099 bool SeenThrowableInstInBB = false; 1100 for (auto &MI : reverse(MBB)) { 1101 if (MI.getOpcode() == WebAssembly::TRY) 1102 EHPadStack.pop_back(); 1103 else if (WebAssembly::isCatch(MI.getOpcode())) 1104 EHPadStack.push_back(MI.getParent()); 1105 1106 // In this loop we only gather calls that have an EH pad to unwind. So 1107 // there will be at most 1 such call (= invoke) in a BB, so after we've 1108 // seen one, we can skip the rest of BB. Also if MBB has no EH pad 1109 // successor or MI does not throw, this is not an invoke. 1110 if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() || 1111 !WebAssembly::mayThrow(MI)) 1112 continue; 1113 SeenThrowableInstInBB = true; 1114 1115 // If the EH pad on the stack top is where this instruction should unwind 1116 // next, we're good. 1117 MachineBasicBlock *UnwindDest = getFakeCallerBlock(MF); 1118 for (auto *Succ : MBB.successors()) { 1119 // Even though semantically a BB can have multiple successors in case an 1120 // exception is not caught by a catchpad, in our backend implementation 1121 // it is guaranteed that a BB can have at most one EH pad successor. For 1122 // details, refer to comments in findWasmUnwindDestinations function in 1123 // SelectionDAGBuilder.cpp. 1124 if (Succ->isEHPad()) { 1125 UnwindDest = Succ; 1126 break; 1127 } 1128 } 1129 if (EHPadStack.back() == UnwindDest) 1130 continue; 1131 1132 // Include EH_LABELs in the range before and afer the invoke 1133 MachineInstr *RangeBegin = &MI, *RangeEnd = &MI; 1134 if (RangeBegin->getIterator() != MBB.begin() && 1135 std::prev(RangeBegin->getIterator())->isEHLabel()) 1136 RangeBegin = &*std::prev(RangeBegin->getIterator()); 1137 if (std::next(RangeEnd->getIterator()) != MBB.end() && 1138 std::next(RangeEnd->getIterator())->isEHLabel()) 1139 RangeEnd = &*std::next(RangeEnd->getIterator()); 1140 1141 // If not, record the range. 1142 UnwindDestToTryRanges[UnwindDest].push_back( 1143 TryRange(RangeBegin, RangeEnd)); 1144 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName() 1145 << "\nCall = " << MI 1146 << "\nOriginal dest = " << UnwindDest->getName() 1147 << " Current dest = " << EHPadStack.back()->getName() 1148 << "\n\n"); 1149 } 1150 } 1151 1152 assert(EHPadStack.empty()); 1153 1154 // Gather possibly throwing calls that are supposed to unwind up to the caller 1155 // if they throw, but currently unwind to an incorrect destination. Unlike the 1156 // loop above, there can be multiple calls within a BB that unwind to the 1157 // caller, which we should group together in a range. (Case 2) 1158 1159 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive 1160 1161 // Record the range. 1162 auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) { 1163 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back( 1164 TryRange(RangeBegin, RangeEnd)); 1165 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " 1166 << RangeBegin->getParent()->getName() 1167 << "\nRange begin = " << *RangeBegin 1168 << "Range end = " << *RangeEnd 1169 << "\nOriginal dest = caller Current dest = " 1170 << CurrentDest->getName() << "\n\n"); 1171 RangeBegin = RangeEnd = nullptr; // Reset range pointers 1172 }; 1173 1174 for (auto &MBB : reverse(MF)) { 1175 bool SeenThrowableInstInBB = false; 1176 for (auto &MI : reverse(MBB)) { 1177 bool MayThrow = WebAssembly::mayThrow(MI); 1178 1179 // If MBB has an EH pad successor and this is the last instruction that 1180 // may throw, this instruction unwinds to the EH pad and not to the 1181 // caller. 1182 if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB) 1183 SeenThrowableInstInBB = true; 1184 1185 // We wrap up the current range when we see a marker even if we haven't 1186 // finished a BB. 1187 else if (RangeEnd && WebAssembly::isMarker(MI.getOpcode())) 1188 RecordCallerMismatchRange(EHPadStack.back()); 1189 1190 // If EHPadStack is empty, that means it correctly unwinds to the caller 1191 // if it throws, so we're good. If MI does not throw, we're good too. 1192 else if (EHPadStack.empty() || !MayThrow) { 1193 } 1194 1195 // We found an instruction that unwinds to the caller but currently has an 1196 // incorrect unwind destination. Create a new range or increment the 1197 // currently existing range. 1198 else { 1199 if (!RangeEnd) 1200 RangeBegin = RangeEnd = &MI; 1201 else 1202 RangeBegin = &MI; 1203 } 1204 1205 // Update EHPadStack. 1206 if (MI.getOpcode() == WebAssembly::TRY) 1207 EHPadStack.pop_back(); 1208 else if (WebAssembly::isCatch(MI.getOpcode())) 1209 EHPadStack.push_back(MI.getParent()); 1210 } 1211 1212 if (RangeEnd) 1213 RecordCallerMismatchRange(EHPadStack.back()); 1214 } 1215 1216 assert(EHPadStack.empty()); 1217 1218 // We don't have any unwind destination mismatches to resolve. 1219 if (UnwindDestToTryRanges.empty()) 1220 return false; 1221 1222 // Now we fix the mismatches by wrapping calls with inner try-delegates. 1223 for (auto &P : UnwindDestToTryRanges) { 1224 NumCallUnwindMismatches += P.second.size(); 1225 MachineBasicBlock *UnwindDest = P.first; 1226 auto &TryRanges = P.second; 1227 1228 for (auto Range : TryRanges) { 1229 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; 1230 std::tie(RangeBegin, RangeEnd) = Range; 1231 auto *MBB = RangeBegin->getParent(); 1232 1233 // If this BB has an EH pad successor, i.e., ends with an 'invoke', now we 1234 // are going to wrap the invoke with try-delegate, making the 'delegate' 1235 // BB the new successor instead, so remove the EH pad succesor here. The 1236 // BB may not have an EH pad successor if calls in this BB throw to the 1237 // caller. 1238 MachineBasicBlock *EHPad = nullptr; 1239 for (auto *Succ : MBB->successors()) { 1240 if (Succ->isEHPad()) { 1241 EHPad = Succ; 1242 break; 1243 } 1244 } 1245 if (EHPad) 1246 MBB->removeSuccessor(EHPad); 1247 1248 addTryDelegate(RangeBegin, RangeEnd, UnwindDest); 1249 } 1250 } 1251 1252 return true; 1253 } 1254 1255 bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) { 1256 // There is another kind of unwind destination mismatches besides call unwind 1257 // mismatches, which we will call "catch unwind mismatches". See this example 1258 // after the marker placement: 1259 // try 1260 // try 1261 // call @foo 1262 // catch __cpp_exception ;; ehpad A (next unwind dest: caller) 1263 // ... 1264 // end_try 1265 // catch_all ;; ehpad B 1266 // ... 1267 // end_try 1268 // 1269 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo' 1270 // throws a foreign exception that is not caught by ehpad A, and its next 1271 // destination should be the caller. But after control flow linearization, 1272 // another EH pad can be placed in between (e.g. ehpad B here), making the 1273 // next unwind destination incorrect. In this case, the foreign exception 1274 // will instead go to ehpad B and will be caught there instead. In this 1275 // example the correct next unwind destination is the caller, but it can be 1276 // another outer catch in other cases. 1277 // 1278 // There is no specific 'call' or 'throw' instruction to wrap with a 1279 // try-delegate, so we wrap the whole try-catch-end with a try-delegate and 1280 // make it rethrow to the right destination, as in the example below: 1281 // try 1282 // try ;; (new) 1283 // try 1284 // call @foo 1285 // catch __cpp_exception ;; ehpad A (next unwind dest: caller) 1286 // ... 1287 // end_try 1288 // delegate 1 (caller) ;; (new) 1289 // catch_all ;; ehpad B 1290 // ... 1291 // end_try 1292 1293 const auto *EHInfo = MF.getWasmEHFuncInfo(); 1294 SmallVector<const MachineBasicBlock *, 8> EHPadStack; 1295 // For EH pads that have catch unwind mismatches, a map of <EH pad, its 1296 // correct unwind destination>. 1297 DenseMap<MachineBasicBlock *, MachineBasicBlock *> EHPadToUnwindDest; 1298 1299 for (auto &MBB : reverse(MF)) { 1300 for (auto &MI : reverse(MBB)) { 1301 if (MI.getOpcode() == WebAssembly::TRY) 1302 EHPadStack.pop_back(); 1303 else if (MI.getOpcode() == WebAssembly::DELEGATE) 1304 EHPadStack.push_back(&MBB); 1305 else if (WebAssembly::isCatch(MI.getOpcode())) { 1306 auto *EHPad = &MBB; 1307 1308 // catch_all always catches an exception, so we don't need to do 1309 // anything 1310 if (MI.getOpcode() == WebAssembly::CATCH_ALL) { 1311 } 1312 1313 // This can happen when the unwind dest was removed during the 1314 // optimization, e.g. because it was unreachable. 1315 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) { 1316 LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName() 1317 << "'s unwind destination does not exist anymore" 1318 << "\n\n"); 1319 } 1320 1321 // The EHPad's next unwind destination is the caller, but we incorrectly 1322 // unwind to another EH pad. 1323 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) { 1324 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF); 1325 LLVM_DEBUG(dbgs() 1326 << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName() 1327 << " Original dest = caller Current dest = " 1328 << EHPadStack.back()->getName() << "\n\n"); 1329 } 1330 1331 // The EHPad's next unwind destination is an EH pad, whereas we 1332 // incorrectly unwind to another EH pad. 1333 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) { 1334 auto *UnwindDest = EHInfo->getUnwindDest(EHPad); 1335 if (EHPadStack.back() != UnwindDest) { 1336 EHPadToUnwindDest[EHPad] = UnwindDest; 1337 LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = " 1338 << EHPad->getName() << " Original dest = " 1339 << UnwindDest->getName() << " Current dest = " 1340 << EHPadStack.back()->getName() << "\n\n"); 1341 } 1342 } 1343 1344 EHPadStack.push_back(EHPad); 1345 } 1346 } 1347 } 1348 1349 assert(EHPadStack.empty()); 1350 if (EHPadToUnwindDest.empty()) 1351 return false; 1352 NumCatchUnwindMismatches += EHPadToUnwindDest.size(); 1353 SmallPtrSet<MachineBasicBlock *, 4> NewEndTryBBs; 1354 1355 for (auto &P : EHPadToUnwindDest) { 1356 MachineBasicBlock *EHPad = P.first; 1357 MachineBasicBlock *UnwindDest = P.second; 1358 MachineInstr *Try = EHPadToTry[EHPad]; 1359 MachineInstr *EndTry = BeginToEnd[Try]; 1360 addTryDelegate(Try, EndTry, UnwindDest); 1361 NewEndTryBBs.insert(EndTry->getParent()); 1362 } 1363 1364 // Adding a try-delegate wrapping an existing try-catch-end can make existing 1365 // branch destination BBs invalid. For example, 1366 // 1367 // - Before: 1368 // bb0: 1369 // block 1370 // br bb3 1371 // bb1: 1372 // try 1373 // ... 1374 // bb2: (ehpad) 1375 // catch 1376 // bb3: 1377 // end_try 1378 // end_block ;; 'br bb3' targets here 1379 // 1380 // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap 1381 // this with a try-delegate. Then this becomes: 1382 // 1383 // - After: 1384 // bb0: 1385 // block 1386 // br bb3 ;; invalid destination! 1387 // bb1: 1388 // try ;; (new instruction) 1389 // try 1390 // ... 1391 // bb2: (ehpad) 1392 // catch 1393 // bb3: 1394 // end_try ;; 'br bb3' still incorrectly targets here! 1395 // delegate_bb: ;; (new BB) 1396 // delegate ;; (new instruction) 1397 // split_bb: ;; (new BB) 1398 // end_block 1399 // 1400 // Now 'br bb3' incorrectly branches to an inner scope. 1401 // 1402 // As we can see in this case, when branches target a BB that has both 1403 // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we 1404 // have to remap existing branch destinations so that they target not the 1405 // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's 1406 // in between, so we try to find the next BB with 'end_block' instruction. In 1407 // this example, the 'br bb3' instruction should be remapped to 'br split_bb'. 1408 for (auto &MBB : MF) { 1409 for (auto &MI : MBB) { 1410 if (MI.isTerminator()) { 1411 for (auto &MO : MI.operands()) { 1412 if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) { 1413 auto *BrDest = MO.getMBB(); 1414 bool FoundEndBlock = false; 1415 for (; std::next(BrDest->getIterator()) != MF.end(); 1416 BrDest = BrDest->getNextNode()) { 1417 for (const auto &MI : *BrDest) { 1418 if (MI.getOpcode() == WebAssembly::END_BLOCK) { 1419 FoundEndBlock = true; 1420 break; 1421 } 1422 } 1423 if (FoundEndBlock) 1424 break; 1425 } 1426 assert(FoundEndBlock); 1427 MO.setMBB(BrDest); 1428 } 1429 } 1430 } 1431 } 1432 } 1433 1434 return true; 1435 } 1436 1437 void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) { 1438 // Renumber BBs and recalculate ScopeTop info because new BBs might have been 1439 // created and inserted during fixing unwind mismatches. 1440 MF.RenumberBlocks(); 1441 ScopeTops.clear(); 1442 ScopeTops.resize(MF.getNumBlockIDs()); 1443 for (auto &MBB : reverse(MF)) { 1444 for (auto &MI : reverse(MBB)) { 1445 if (ScopeTops[MBB.getNumber()]) 1446 break; 1447 switch (MI.getOpcode()) { 1448 case WebAssembly::END_BLOCK: 1449 case WebAssembly::END_LOOP: 1450 case WebAssembly::END_TRY: 1451 case WebAssembly::DELEGATE: 1452 updateScopeTops(EndToBegin[&MI]->getParent(), &MBB); 1453 break; 1454 case WebAssembly::CATCH: 1455 case WebAssembly::CATCH_ALL: 1456 updateScopeTops(EHPadToTry[&MBB]->getParent(), &MBB); 1457 break; 1458 } 1459 } 1460 } 1461 } 1462 1463 /// In normal assembly languages, when the end of a function is unreachable, 1464 /// because the function ends in an infinite loop or a noreturn call or similar, 1465 /// it isn't necessary to worry about the function return type at the end of 1466 /// the function, because it's never reached. However, in WebAssembly, blocks 1467 /// that end at the function end need to have a return type signature that 1468 /// matches the function signature, even though it's unreachable. This function 1469 /// checks for such cases and fixes up the signatures. 1470 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { 1471 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 1472 1473 if (MFI.getResults().empty()) 1474 return; 1475 1476 // MCInstLower will add the proper types to multivalue signatures based on the 1477 // function return type 1478 WebAssembly::BlockType RetType = 1479 MFI.getResults().size() > 1 1480 ? WebAssembly::BlockType::Multivalue 1481 : WebAssembly::BlockType( 1482 WebAssembly::toValType(MFI.getResults().front())); 1483 1484 SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist; 1485 Worklist.push_back(MF.rbegin()->rbegin()); 1486 1487 auto Process = [&](MachineBasicBlock::reverse_iterator It) { 1488 auto *MBB = It->getParent(); 1489 while (It != MBB->rend()) { 1490 MachineInstr &MI = *It++; 1491 if (MI.isPosition() || MI.isDebugInstr()) 1492 continue; 1493 switch (MI.getOpcode()) { 1494 case WebAssembly::END_TRY: { 1495 // If a 'try''s return type is fixed, both its try body and catch body 1496 // should satisfy the return type, so we need to search 'end' 1497 // instructions before its corresponding 'catch' too. 1498 auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]); 1499 assert(EHPad); 1500 auto NextIt = 1501 std::next(WebAssembly::findCatch(EHPad)->getReverseIterator()); 1502 if (NextIt != EHPad->rend()) 1503 Worklist.push_back(NextIt); 1504 LLVM_FALLTHROUGH; 1505 } 1506 case WebAssembly::END_BLOCK: 1507 case WebAssembly::END_LOOP: 1508 case WebAssembly::DELEGATE: 1509 EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType)); 1510 continue; 1511 default: 1512 // Something other than an `end`. We're done for this BB. 1513 return; 1514 } 1515 } 1516 // We've reached the beginning of a BB. Continue the search in the previous 1517 // BB. 1518 Worklist.push_back(MBB->getPrevNode()->rbegin()); 1519 }; 1520 1521 while (!Worklist.empty()) 1522 Process(Worklist.pop_back_val()); 1523 } 1524 1525 // WebAssembly functions end with an end instruction, as if the function body 1526 // were a block. 1527 static void appendEndToFunction(MachineFunction &MF, 1528 const WebAssemblyInstrInfo &TII) { 1529 BuildMI(MF.back(), MF.back().end(), 1530 MF.back().findPrevDebugLoc(MF.back().end()), 1531 TII.get(WebAssembly::END_FUNCTION)); 1532 } 1533 1534 /// Insert LOOP/TRY/BLOCK markers at appropriate places. 1535 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { 1536 // We allocate one more than the number of blocks in the function to 1537 // accommodate for the possible fake block we may insert at the end. 1538 ScopeTops.resize(MF.getNumBlockIDs() + 1); 1539 // Place the LOOP for MBB if MBB is the header of a loop. 1540 for (auto &MBB : MF) 1541 placeLoopMarker(MBB); 1542 1543 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 1544 for (auto &MBB : MF) { 1545 if (MBB.isEHPad()) { 1546 // Place the TRY for MBB if MBB is the EH pad of an exception. 1547 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1548 MF.getFunction().hasPersonalityFn()) 1549 placeTryMarker(MBB); 1550 } else { 1551 // Place the BLOCK for MBB if MBB is branched to from above. 1552 placeBlockMarker(MBB); 1553 } 1554 } 1555 // Fix mismatches in unwind destinations induced by linearizing the code. 1556 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1557 MF.getFunction().hasPersonalityFn()) { 1558 bool Changed = fixCallUnwindMismatches(MF); 1559 Changed |= fixCatchUnwindMismatches(MF); 1560 if (Changed) 1561 recalculateScopeTops(MF); 1562 } 1563 } 1564 1565 unsigned WebAssemblyCFGStackify::getBranchDepth( 1566 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) { 1567 unsigned Depth = 0; 1568 for (auto X : reverse(Stack)) { 1569 if (X.first == MBB) 1570 break; 1571 ++Depth; 1572 } 1573 assert(Depth < Stack.size() && "Branch destination should be in scope"); 1574 return Depth; 1575 } 1576 1577 unsigned WebAssemblyCFGStackify::getDelegateDepth( 1578 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) { 1579 if (MBB == FakeCallerBB) 1580 return Stack.size(); 1581 // Delegate's destination is either a catch or a another delegate BB. When the 1582 // destination is another delegate, we can compute the argument in the same 1583 // way as branches, because the target delegate BB only contains the single 1584 // delegate instruction. 1585 if (!MBB->isEHPad()) // Target is a delegate BB 1586 return getBranchDepth(Stack, MBB); 1587 1588 // When the delegate's destination is a catch BB, we need to use its 1589 // corresponding try's end_try BB because Stack contains each marker's end BB. 1590 // Also we need to check if the end marker instruction matches, because a 1591 // single BB can contain multiple end markers, like this: 1592 // bb: 1593 // END_BLOCK 1594 // END_TRY 1595 // END_BLOCK 1596 // END_TRY 1597 // ... 1598 // 1599 // In case of branches getting the immediate that targets any of these is 1600 // fine, but delegate has to exactly target the correct try. 1601 unsigned Depth = 0; 1602 const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]]; 1603 for (auto X : reverse(Stack)) { 1604 if (X.first == EndTry->getParent() && X.second == EndTry) 1605 break; 1606 ++Depth; 1607 } 1608 assert(Depth < Stack.size() && "Delegate destination should be in scope"); 1609 return Depth; 1610 } 1611 1612 unsigned WebAssemblyCFGStackify::getRethrowDepth( 1613 const SmallVectorImpl<EndMarkerInfo> &Stack, 1614 const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack) { 1615 unsigned Depth = 0; 1616 // In our current implementation, rethrows always rethrow the exception caught 1617 // by the innermost enclosing catch. This means while traversing Stack in the 1618 // reverse direction, when we encounter END_TRY, we should check if the 1619 // END_TRY corresponds to the current innermost EH pad. For example: 1620 // try 1621 // ... 1622 // catch ;; (a) 1623 // try 1624 // rethrow 1 ;; (b) 1625 // catch ;; (c) 1626 // rethrow 0 ;; (d) 1627 // end ;; (e) 1628 // end ;; (f) 1629 // 1630 // When we are at 'rethrow' (d), while reversely traversing Stack the first 1631 // 'end' we encounter is the 'end' (e), which corresponds to the 'catch' (c). 1632 // And 'rethrow' (d) rethrows the exception caught by 'catch' (c), so we stop 1633 // there and the depth should be 0. But when we are at 'rethrow' (b), it 1634 // rethrows the exception caught by 'catch' (a), so when traversing Stack 1635 // reversely, we should skip the 'end' (e) and choose 'end' (f), which 1636 // corresponds to 'catch' (a). 1637 for (auto X : reverse(Stack)) { 1638 const MachineInstr *End = X.second; 1639 if (End->getOpcode() == WebAssembly::END_TRY) { 1640 auto *EHPad = TryToEHPad[EndToBegin[End]]; 1641 if (EHPadStack.back() == EHPad) 1642 break; 1643 } 1644 ++Depth; 1645 } 1646 assert(Depth < Stack.size() && "Rethrow destination should be in scope"); 1647 return Depth; 1648 } 1649 1650 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { 1651 // Now rewrite references to basic blocks to be depth immediates. 1652 SmallVector<EndMarkerInfo, 8> Stack; 1653 SmallVector<const MachineBasicBlock *, 8> EHPadStack; 1654 for (auto &MBB : reverse(MF)) { 1655 for (MachineInstr &MI : llvm::reverse(MBB)) { 1656 switch (MI.getOpcode()) { 1657 case WebAssembly::BLOCK: 1658 case WebAssembly::TRY: 1659 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <= 1660 MBB.getNumber() && 1661 "Block/try marker should be balanced"); 1662 Stack.pop_back(); 1663 break; 1664 1665 case WebAssembly::LOOP: 1666 assert(Stack.back().first == &MBB && "Loop top should be balanced"); 1667 Stack.pop_back(); 1668 break; 1669 1670 case WebAssembly::END_BLOCK: 1671 Stack.push_back(std::make_pair(&MBB, &MI)); 1672 break; 1673 1674 case WebAssembly::END_TRY: { 1675 // We handle DELEGATE in the default level, because DELEGATE has 1676 // immediate operands to rewrite. 1677 Stack.push_back(std::make_pair(&MBB, &MI)); 1678 auto *EHPad = TryToEHPad[EndToBegin[&MI]]; 1679 EHPadStack.push_back(EHPad); 1680 break; 1681 } 1682 1683 case WebAssembly::END_LOOP: 1684 Stack.push_back(std::make_pair(EndToBegin[&MI]->getParent(), &MI)); 1685 break; 1686 1687 case WebAssembly::CATCH: 1688 case WebAssembly::CATCH_ALL: 1689 EHPadStack.pop_back(); 1690 break; 1691 1692 case WebAssembly::RETHROW: 1693 MI.getOperand(0).setImm(getRethrowDepth(Stack, EHPadStack)); 1694 break; 1695 1696 default: 1697 if (MI.isTerminator()) { 1698 // Rewrite MBB operands to be depth immediates. 1699 SmallVector<MachineOperand, 4> Ops(MI.operands()); 1700 while (MI.getNumOperands() > 0) 1701 MI.removeOperand(MI.getNumOperands() - 1); 1702 for (auto MO : Ops) { 1703 if (MO.isMBB()) { 1704 if (MI.getOpcode() == WebAssembly::DELEGATE) 1705 MO = MachineOperand::CreateImm( 1706 getDelegateDepth(Stack, MO.getMBB())); 1707 else 1708 MO = MachineOperand::CreateImm( 1709 getBranchDepth(Stack, MO.getMBB())); 1710 } 1711 MI.addOperand(MF, MO); 1712 } 1713 } 1714 1715 if (MI.getOpcode() == WebAssembly::DELEGATE) 1716 Stack.push_back(std::make_pair(&MBB, &MI)); 1717 break; 1718 } 1719 } 1720 } 1721 assert(Stack.empty() && "Control flow should be balanced"); 1722 } 1723 1724 void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) { 1725 if (FakeCallerBB) 1726 MF.deleteMachineBasicBlock(FakeCallerBB); 1727 AppendixBB = FakeCallerBB = nullptr; 1728 } 1729 1730 void WebAssemblyCFGStackify::releaseMemory() { 1731 ScopeTops.clear(); 1732 BeginToEnd.clear(); 1733 EndToBegin.clear(); 1734 TryToEHPad.clear(); 1735 EHPadToTry.clear(); 1736 } 1737 1738 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 1739 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n" 1740 "********** Function: " 1741 << MF.getName() << '\n'); 1742 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo(); 1743 1744 releaseMemory(); 1745 1746 // Liveness is not tracked for VALUE_STACK physreg. 1747 MF.getRegInfo().invalidateLiveness(); 1748 1749 // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes. 1750 placeMarkers(MF); 1751 1752 // Remove unnecessary instructions possibly introduced by try/end_trys. 1753 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm && 1754 MF.getFunction().hasPersonalityFn()) 1755 removeUnnecessaryInstrs(MF); 1756 1757 // Convert MBB operands in terminators to relative depth immediates. 1758 rewriteDepthImmediates(MF); 1759 1760 // Fix up block/loop/try signatures at the end of the function to conform to 1761 // WebAssembly's rules. 1762 fixEndsAtEndOfFunction(MF); 1763 1764 // Add an end instruction at the end of the function body. 1765 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 1766 if (!MF.getSubtarget<WebAssemblySubtarget>() 1767 .getTargetTriple() 1768 .isOSBinFormatELF()) 1769 appendEndToFunction(MF, TII); 1770 1771 cleanupFunctionData(MF); 1772 1773 MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified(); 1774 return true; 1775 } 1776