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, TRY, and TRY_TABLE markers to mark the start
13/// of scopes, since scope boundaries serve as the labels for WebAssembly's
14/// control 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 "WebAssembly.h"
26#include "WebAssemblyExceptionInfo.h"
27#include "WebAssemblyMachineFunctionInfo.h"
28#include "WebAssemblySortRegion.h"
29#include "WebAssemblySubtarget.h"
30#include "WebAssemblyTargetMachine.h"
31#include "WebAssemblyUtilities.h"
32#include "llvm/ADT/MapVector.h"
33#include "llvm/ADT/Statistic.h"
34#include "llvm/BinaryFormat/Wasm.h"
35#include "llvm/CodeGen/MachineDominators.h"
36#include "llvm/CodeGen/MachineInstrBuilder.h"
37#include "llvm/CodeGen/MachineLoopInfo.h"
38#include "llvm/MC/MCAsmInfo.h"
39#include "llvm/Target/TargetMachine.h"
40using namespace llvm;
41using WebAssembly::SortRegionInfo;
42
43#define DEBUG_TYPE "wasm-cfg-stackify"
44
45STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found");
46STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found");
47
48namespace {
49class WebAssemblyCFGStackify final : public MachineFunctionPass {
50 MachineDominatorTree *MDT;
51
52 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
53
54 void getAnalysisUsage(AnalysisUsage &AU) const override {
55 AU.addRequired<MachineDominatorTreeWrapperPass>();
56 AU.addRequired<MachineLoopInfoWrapperPass>();
57 AU.addRequired<WebAssemblyExceptionInfo>();
58 MachineFunctionPass::getAnalysisUsage(AU);
59 }
60
61 bool runOnMachineFunction(MachineFunction &MF) override;
62
63 // For each block whose label represents the end of a scope, record the block
64 // which holds the beginning of the scope. This will allow us to quickly skip
65 // over scoped regions when walking blocks.
66 SmallVector<MachineBasicBlock *, 8> ScopeTops;
67 void updateScopeTops(MachineBasicBlock *Begin, MachineBasicBlock *End) {
68 int BeginNo = Begin->getNumber();
69 int EndNo = End->getNumber();
70 if (!ScopeTops[EndNo] || ScopeTops[EndNo]->getNumber() > BeginNo)
71 ScopeTops[EndNo] = Begin;
72 }
73
74 // Placing markers.
75 void placeMarkers(MachineFunction &MF);
76 void placeBlockMarker(MachineBasicBlock &MBB);
77 void placeLoopMarker(MachineBasicBlock &MBB);
78 void placeTryMarker(MachineBasicBlock &MBB);
79 void placeTryTableMarker(MachineBasicBlock &MBB);
80
81 // Unwind mismatch fixing for exception handling
82 // - Common functions
83 bool fixCallUnwindMismatches(MachineFunction &MF);
84 bool fixCatchUnwindMismatches(MachineFunction &MF);
85 void recalculateScopeTops(MachineFunction &MF);
86 // - Legacy EH
87 void addNestedTryDelegate(MachineInstr *RangeBegin, MachineInstr *RangeEnd,
88 MachineBasicBlock *UnwindDest);
89 void removeUnnecessaryInstrs(MachineFunction &MF);
90 // - Standard EH (exnref)
91 void addNestedTryTable(MachineInstr *RangeBegin, MachineInstr *RangeEnd,
92 MachineBasicBlock *UnwindDest);
93 MachineBasicBlock *getTrampolineBlock(MachineBasicBlock *UnwindDest);
94
95 // Wrap-up
96 using EndMarkerInfo =
97 std::pair<const MachineBasicBlock *, const MachineInstr *>;
98 unsigned getBranchDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,
99 const MachineBasicBlock *MBB);
100 unsigned getDelegateDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,
101 const MachineBasicBlock *MBB);
102 unsigned getRethrowDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,
103 const MachineBasicBlock *EHPadToRethrow);
104 void rewriteDepthImmediates(MachineFunction &MF);
105 void fixEndsAtEndOfFunction(MachineFunction &MF);
106 void cleanupFunctionData(MachineFunction &MF);
107
108 // For each BLOCK|LOOP|TRY|TRY_TABLE, the corresponding
109 // END_(BLOCK|LOOP|TRY|TRY_TABLE) or DELEGATE (in case of TRY).
110 DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd;
111 // For each END_(BLOCK|LOOP|TRY|TRY_TABLE) or DELEGATE, the corresponding
112 // BLOCK|LOOP|TRY|TRY_TABLE.
113 DenseMap<const MachineInstr *, MachineInstr *> EndToBegin;
114 // <TRY marker, EH pad> map
115 DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad;
116 // <EH pad, TRY marker> map
117 DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry;
118
119 DenseMap<const MachineBasicBlock *, MachineBasicBlock *>
120 UnwindDestToTrampoline;
121
122 // We need an appendix block to place 'end_loop' or 'end_try' marker when the
123 // loop / exception bottom block is the last block in a function
124 MachineBasicBlock *AppendixBB = nullptr;
125 MachineBasicBlock *getAppendixBlock(MachineFunction &MF) {
126 if (!AppendixBB) {
127 AppendixBB = MF.CreateMachineBasicBlock();
128 // Give it a fake predecessor so that AsmPrinter prints its label.
129 AppendixBB->addSuccessor(Succ: AppendixBB);
130 // If the caller trampoline BB exists, insert the appendix BB before it.
131 // Otherwise insert it at the end of the function.
132 if (CallerTrampolineBB)
133 MF.insert(MBBI: CallerTrampolineBB->getIterator(), MBB: AppendixBB);
134 else
135 MF.push_back(MBB: AppendixBB);
136 }
137 return AppendixBB;
138 }
139
140 // Create a caller-dedicated trampoline BB to be used for fixing unwind
141 // mismatches where the unwind destination is the caller.
142 MachineBasicBlock *CallerTrampolineBB = nullptr;
143 MachineBasicBlock *getCallerTrampolineBlock(MachineFunction &MF) {
144 if (!CallerTrampolineBB) {
145 CallerTrampolineBB = MF.CreateMachineBasicBlock();
146 MF.push_back(MBB: CallerTrampolineBB);
147 }
148 return CallerTrampolineBB;
149 }
150
151 // Before running rewriteDepthImmediates function, 'delegate' has a BB as its
152 // destination operand. getFakeCallerBlock() returns a fake BB that will be
153 // used for the operand when 'delegate' needs to rethrow to the caller. This
154 // will be rewritten as an immediate value that is the number of block depths
155 // + 1 in rewriteDepthImmediates, and this fake BB will be removed at the end
156 // of the pass.
157 MachineBasicBlock *FakeCallerBB = nullptr;
158 MachineBasicBlock *getFakeCallerBlock(MachineFunction &MF) {
159 if (!FakeCallerBB)
160 FakeCallerBB = MF.CreateMachineBasicBlock();
161 return FakeCallerBB;
162 }
163
164 // Helper functions to register / unregister scope information created by
165 // marker instructions.
166 void registerScope(MachineInstr *Begin, MachineInstr *End);
167 void registerTryScope(MachineInstr *Begin, MachineInstr *End,
168 MachineBasicBlock *EHPad);
169 void unregisterScope(MachineInstr *Begin);
170
171public:
172 static char ID; // Pass identification, replacement for typeid
173 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
174 ~WebAssemblyCFGStackify() override { releaseMemory(); }
175 void releaseMemory() override;
176};
177} // end anonymous namespace
178
179char WebAssemblyCFGStackify::ID = 0;
180INITIALIZE_PASS(
181 WebAssemblyCFGStackify, DEBUG_TYPE,
182 "Insert BLOCK/LOOP/TRY/TRY_TABLE markers for WebAssembly scopes", false,
183 false)
184
185FunctionPass *llvm::createWebAssemblyCFGStackify() {
186 return new WebAssemblyCFGStackify();
187}
188
189/// Test whether Pred has any terminators explicitly branching to MBB, as
190/// opposed to falling through. Note that it's possible (eg. in unoptimized
191/// code) for a branch instruction to both branch to a block and fallthrough
192/// to it, so we check the actual branch operands to see if there are any
193/// explicit mentions.
194static bool explicitlyBranchesTo(MachineBasicBlock *Pred,
195 MachineBasicBlock *MBB) {
196 for (MachineInstr &MI : Pred->terminators())
197 for (MachineOperand &MO : MI.explicit_operands())
198 if (MO.isMBB() && MO.getMBB() == MBB)
199 return true;
200 return false;
201}
202
203// Returns an iterator to the earliest position possible within the MBB,
204// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
205// contains instructions that should go before the marker, and AfterSet contains
206// ones that should go after the marker. In this function, AfterSet is only
207// used for validation checking.
208template <typename Container>
209static MachineBasicBlock::iterator
210getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet,
211 const Container &AfterSet) {
212 auto InsertPos = MBB->end();
213 while (InsertPos != MBB->begin()) {
214 if (BeforeSet.count(&*std::prev(x: InsertPos))) {
215#ifndef NDEBUG
216 // Validation check
217 for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
218 assert(!AfterSet.count(&*std::prev(Pos)));
219#endif
220 break;
221 }
222 --InsertPos;
223 }
224 return InsertPos;
225}
226
227// Returns an iterator to the latest position possible within the MBB,
228// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
229// contains instructions that should go before the marker, and AfterSet contains
230// ones that should go after the marker. In this function, BeforeSet is only
231// used for validation checking.
232template <typename Container>
233static MachineBasicBlock::iterator
234getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet,
235 const Container &AfterSet) {
236 auto InsertPos = MBB->begin();
237 while (InsertPos != MBB->end()) {
238 if (AfterSet.count(&*InsertPos)) {
239#ifndef NDEBUG
240 // Validation check
241 for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
242 assert(!BeforeSet.count(&*Pos));
243#endif
244 break;
245 }
246 ++InsertPos;
247 }
248 return InsertPos;
249}
250
251void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
252 MachineInstr *End) {
253 BeginToEnd[Begin] = End;
254 EndToBegin[End] = Begin;
255}
256
257// When 'End' is not an 'end_try' but a 'delegate', EHPad is nullptr.
258void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
259 MachineInstr *End,
260 MachineBasicBlock *EHPad) {
261 registerScope(Begin, End);
262 TryToEHPad[Begin] = EHPad;
263 EHPadToTry[EHPad] = Begin;
264}
265
266void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
267 assert(BeginToEnd.count(Begin));
268 MachineInstr *End = BeginToEnd[Begin];
269 assert(EndToBegin.count(End));
270 BeginToEnd.erase(Val: Begin);
271 EndToBegin.erase(Val: End);
272 MachineBasicBlock *EHPad = TryToEHPad.lookup(Val: Begin);
273 if (EHPad) {
274 assert(EHPadToTry.count(EHPad));
275 TryToEHPad.erase(Val: Begin);
276 EHPadToTry.erase(Val: EHPad);
277 }
278}
279
280/// Insert a BLOCK marker for branches to MBB (if needed).
281// TODO Consider a more generalized way of handling block (and also loop and
282// try) signatures when we implement the multi-value proposal later.
283void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
284 assert(!MBB.isEHPad());
285 MachineFunction &MF = *MBB.getParent();
286 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
287 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
288
289 // First compute the nearest common dominator of all forward non-fallthrough
290 // predecessors so that we minimize the time that the BLOCK is on the stack,
291 // which reduces overall stack height.
292 MachineBasicBlock *Header = nullptr;
293 bool IsBranchedTo = false;
294 int MBBNumber = MBB.getNumber();
295 for (MachineBasicBlock *Pred : MBB.predecessors()) {
296 if (Pred->getNumber() < MBBNumber) {
297 Header = Header ? MDT->findNearestCommonDominator(A: Header, B: Pred) : Pred;
298 if (explicitlyBranchesTo(Pred, MBB: &MBB))
299 IsBranchedTo = true;
300 }
301 }
302 if (!Header)
303 return;
304 if (!IsBranchedTo)
305 return;
306
307 assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
308 MachineBasicBlock *LayoutPred = MBB.getPrevNode();
309
310 // If the nearest common dominator is inside a more deeply nested context,
311 // walk out to the nearest scope which isn't more deeply nested.
312 for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
313 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
314 if (ScopeTop->getNumber() > Header->getNumber()) {
315 // Skip over an intervening scope.
316 I = std::next(x: ScopeTop->getIterator());
317 } else {
318 // We found a scope level at an appropriate depth.
319 Header = ScopeTop;
320 break;
321 }
322 }
323 }
324
325 // Decide where in MBB to put the BLOCK.
326
327 // Instructions that should go before the BLOCK.
328 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
329 // Instructions that should go after the BLOCK.
330 SmallPtrSet<const MachineInstr *, 4> AfterSet;
331 for (const auto &MI : *Header) {
332 // If there is a previously placed LOOP marker and the bottom block of the
333 // loop is above MBB, it should be after the BLOCK, because the loop is
334 // nested in this BLOCK. Otherwise it should be before the BLOCK.
335 if (MI.getOpcode() == WebAssembly::LOOP) {
336 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
337 if (MBB.getNumber() > LoopBottom->getNumber())
338 AfterSet.insert(Ptr: &MI);
339#ifndef NDEBUG
340 else
341 BeforeSet.insert(&MI);
342#endif
343 }
344
345 // If there is a previously placed BLOCK/TRY/TRY_TABLE marker and its
346 // corresponding END marker is before the current BLOCK's END marker, that
347 // should be placed after this BLOCK. Otherwise it should be placed before
348 // this BLOCK marker.
349 if (MI.getOpcode() == WebAssembly::BLOCK ||
350 MI.getOpcode() == WebAssembly::TRY ||
351 MI.getOpcode() == WebAssembly::TRY_TABLE) {
352 if (BeginToEnd[&MI]->getParent()->getNumber() <= MBB.getNumber())
353 AfterSet.insert(Ptr: &MI);
354#ifndef NDEBUG
355 else
356 BeforeSet.insert(&MI);
357#endif
358 }
359
360#ifndef NDEBUG
361 // All END_(BLOCK|LOOP|TRY|TRY_TABLE) markers should be before the BLOCK.
362 if (MI.getOpcode() == WebAssembly::END_BLOCK ||
363 MI.getOpcode() == WebAssembly::END_LOOP ||
364 MI.getOpcode() == WebAssembly::END_TRY ||
365 MI.getOpcode() == WebAssembly::END_TRY_TABLE)
366 BeforeSet.insert(&MI);
367#endif
368
369 // Terminators should go after the BLOCK.
370 if (MI.isTerminator())
371 AfterSet.insert(Ptr: &MI);
372 }
373
374 // Local expression tree should go after the BLOCK.
375 for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
376 --I) {
377 if (std::prev(x: I)->isDebugInstr() || std::prev(x: I)->isPosition())
378 continue;
379 if (WebAssembly::isChild(MI: *std::prev(x: I), MFI))
380 AfterSet.insert(Ptr: &*std::prev(x: I));
381 else
382 break;
383 }
384
385 // Add the BLOCK.
386 WebAssembly::BlockType ReturnType = WebAssembly::BlockType::Void;
387 auto InsertPos = getLatestInsertPos(MBB: Header, BeforeSet, AfterSet);
388 MachineInstr *Begin =
389 BuildMI(BB&: *Header, I: InsertPos, MIMD: Header->findDebugLoc(MBBI: InsertPos),
390 MCID: TII.get(Opcode: WebAssembly::BLOCK))
391 .addImm(Val: int64_t(ReturnType));
392
393 // Decide where in MBB to put the END_BLOCK.
394 BeforeSet.clear();
395 AfterSet.clear();
396 for (auto &MI : MBB) {
397#ifndef NDEBUG
398 // END_BLOCK should precede existing LOOP markers.
399 if (MI.getOpcode() == WebAssembly::LOOP)
400 AfterSet.insert(&MI);
401#endif
402
403 // If there is a previously placed END_LOOP marker and the header of the
404 // loop is above this block's header, the END_LOOP should be placed after
405 // the END_BLOCK, because the loop contains this block. Otherwise the
406 // END_LOOP should be placed before the END_BLOCK. The same for END_TRY.
407 //
408 // Note that while there can be existing END_TRYs, there can't be
409 // END_TRY_TABLEs; END_TRYs are placed when its corresponding EH pad is
410 // processed, so they are placed below MBB (EH pad) in placeTryMarker. But
411 // END_TRY_TABLE is placed like a END_BLOCK, so they can't be here already.
412 if (MI.getOpcode() == WebAssembly::END_LOOP ||
413 MI.getOpcode() == WebAssembly::END_TRY) {
414 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
415 BeforeSet.insert(Ptr: &MI);
416#ifndef NDEBUG
417 else
418 AfterSet.insert(&MI);
419#endif
420 }
421 }
422
423 // Mark the end of the block.
424 InsertPos = getEarliestInsertPos(MBB: &MBB, BeforeSet, AfterSet);
425 MachineInstr *End = BuildMI(BB&: MBB, I: InsertPos, MIMD: MBB.findPrevDebugLoc(MBBI: InsertPos),
426 MCID: TII.get(Opcode: WebAssembly::END_BLOCK));
427 registerScope(Begin, End);
428
429 // Track the farthest-spanning scope that ends at this point.
430 updateScopeTops(Begin: Header, End: &MBB);
431}
432
433/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
434void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
435 MachineFunction &MF = *MBB.getParent();
436 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
437 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
438 SortRegionInfo SRI(MLI, WEI);
439 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
440
441 MachineLoop *Loop = MLI.getLoopFor(BB: &MBB);
442 if (!Loop || Loop->getHeader() != &MBB)
443 return;
444
445 // The operand of a LOOP is the first block after the loop. If the loop is the
446 // bottom of the function, insert a dummy block at the end.
447 MachineBasicBlock *Bottom = SRI.getBottom(ML: Loop);
448 auto Iter = std::next(x: Bottom->getIterator());
449 if (Iter == MF.end()) {
450 getAppendixBlock(MF);
451 Iter = std::next(x: Bottom->getIterator());
452 }
453 MachineBasicBlock *AfterLoop = &*Iter;
454
455 // Decide where in Header to put the LOOP.
456 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
457 SmallPtrSet<const MachineInstr *, 4> AfterSet;
458 for (const auto &MI : MBB) {
459 // LOOP marker should be after any existing loop that ends here. Otherwise
460 // we assume the instruction belongs to the loop.
461 if (MI.getOpcode() == WebAssembly::END_LOOP)
462 BeforeSet.insert(Ptr: &MI);
463#ifndef NDEBUG
464 else
465 AfterSet.insert(&MI);
466#endif
467 }
468
469 // Mark the beginning of the loop.
470 auto InsertPos = getEarliestInsertPos(MBB: &MBB, BeforeSet, AfterSet);
471 MachineInstr *Begin = BuildMI(BB&: MBB, I: InsertPos, MIMD: MBB.findDebugLoc(MBBI: InsertPos),
472 MCID: TII.get(Opcode: WebAssembly::LOOP))
473 .addImm(Val: int64_t(WebAssembly::BlockType::Void));
474
475 // Decide where in MBB to put the END_LOOP.
476 BeforeSet.clear();
477 AfterSet.clear();
478#ifndef NDEBUG
479 for (const auto &MI : MBB)
480 // Existing END_LOOP markers belong to parent loops of this loop
481 if (MI.getOpcode() == WebAssembly::END_LOOP)
482 AfterSet.insert(&MI);
483#endif
484
485 // Mark the end of the loop (using arbitrary debug location that branched to
486 // the loop end as its location).
487 InsertPos = getEarliestInsertPos(MBB: AfterLoop, BeforeSet, AfterSet);
488 DebugLoc EndDL = AfterLoop->pred_empty()
489 ? DebugLoc()
490 : (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
491 MachineInstr *End =
492 BuildMI(BB&: *AfterLoop, I: InsertPos, MIMD: EndDL, MCID: TII.get(Opcode: WebAssembly::END_LOOP));
493 registerScope(Begin, End);
494
495 assert((!ScopeTops[AfterLoop->getNumber()] ||
496 ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
497 "With block sorting the outermost loop for a block should be first.");
498 updateScopeTops(Begin: &MBB, End: AfterLoop);
499}
500
501void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
502 assert(MBB.isEHPad());
503 MachineFunction &MF = *MBB.getParent();
504 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
505 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
506 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
507 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
508 SortRegionInfo SRI(MLI, WEI);
509 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
510
511 // Compute the nearest common dominator of all unwind predecessors
512 MachineBasicBlock *Header = nullptr;
513 int MBBNumber = MBB.getNumber();
514 for (auto *Pred : MBB.predecessors()) {
515 if (Pred->getNumber() < MBBNumber) {
516 Header = Header ? MDT.findNearestCommonDominator(A: Header, B: Pred) : Pred;
517 assert(!explicitlyBranchesTo(Pred, &MBB) &&
518 "Explicit branch to an EH pad!");
519 }
520 }
521 if (!Header)
522 return;
523
524 // If this try is at the bottom of the function, insert a dummy block at the
525 // end.
526 WebAssemblyException *WE = WEI.getExceptionFor(MBB: &MBB);
527 assert(WE);
528 MachineBasicBlock *Bottom = SRI.getBottom(WE);
529 auto Iter = std::next(x: Bottom->getIterator());
530 if (Iter == MF.end()) {
531 getAppendixBlock(MF);
532 Iter = std::next(x: Bottom->getIterator());
533 }
534 MachineBasicBlock *Cont = &*Iter;
535
536 // If the nearest common dominator is inside a more deeply nested context,
537 // walk out to the nearest scope which isn't more deeply nested.
538 for (MachineFunction::iterator I(Bottom), E(Header); I != E; --I) {
539 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
540 if (ScopeTop->getNumber() > Header->getNumber()) {
541 // Skip over an intervening scope.
542 I = std::next(x: ScopeTop->getIterator());
543 } else {
544 // We found a scope level at an appropriate depth.
545 Header = ScopeTop;
546 break;
547 }
548 }
549 }
550
551 // Decide where in Header to put the TRY.
552
553 // Instructions that should go before the TRY.
554 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
555 // Instructions that should go after the TRY.
556 SmallPtrSet<const MachineInstr *, 4> AfterSet;
557 for (const auto &MI : *Header) {
558 // If there is a previously placed LOOP marker and the bottom block of the
559 // loop is above MBB, it should be after the TRY, because the loop is nested
560 // in this TRY. Otherwise it should be before the TRY.
561 if (MI.getOpcode() == WebAssembly::LOOP) {
562 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
563 if (MBB.getNumber() > LoopBottom->getNumber())
564 AfterSet.insert(Ptr: &MI);
565#ifndef NDEBUG
566 else
567 BeforeSet.insert(&MI);
568#endif
569 }
570
571 // All previously inserted BLOCK/TRY markers should be after the TRY because
572 // they are all nested blocks/trys.
573 if (MI.getOpcode() == WebAssembly::BLOCK ||
574 MI.getOpcode() == WebAssembly::TRY)
575 AfterSet.insert(Ptr: &MI);
576
577#ifndef NDEBUG
578 // All END_(BLOCK/LOOP/TRY) markers should be before the TRY.
579 if (MI.getOpcode() == WebAssembly::END_BLOCK ||
580 MI.getOpcode() == WebAssembly::END_LOOP ||
581 MI.getOpcode() == WebAssembly::END_TRY)
582 BeforeSet.insert(&MI);
583#endif
584
585 // Terminators should go after the TRY.
586 if (MI.isTerminator())
587 AfterSet.insert(Ptr: &MI);
588 }
589
590 // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
591 // contain the call within it. So the call should go after the TRY. The
592 // exception is when the header's terminator is a rethrow instruction, in
593 // which case that instruction, not a call instruction before it, is gonna
594 // throw.
595 MachineInstr *ThrowingCall = nullptr;
596 if (MBB.isPredecessor(MBB: Header)) {
597 auto TermPos = Header->getFirstTerminator();
598 if (TermPos == Header->end() ||
599 TermPos->getOpcode() != WebAssembly::RETHROW) {
600 for (auto &MI : reverse(C&: *Header)) {
601 if (MI.isCall()) {
602 AfterSet.insert(Ptr: &MI);
603 ThrowingCall = &MI;
604 // Possibly throwing calls are usually wrapped by EH_LABEL
605 // instructions. We don't want to split them and the call.
606 if (MI.getIterator() != Header->begin() &&
607 std::prev(x: MI.getIterator())->isEHLabel()) {
608 AfterSet.insert(Ptr: &*std::prev(x: MI.getIterator()));
609 ThrowingCall = &*std::prev(x: MI.getIterator());
610 }
611 break;
612 }
613 }
614 }
615 }
616
617 // Local expression tree should go after the TRY.
618 // For BLOCK placement, we start the search from the previous instruction of a
619 // BB's terminator, but in TRY's case, we should start from the previous
620 // instruction of a call that can throw, or a EH_LABEL that precedes the call,
621 // because the return values of the call's previous instructions can be
622 // stackified and consumed by the throwing call.
623 auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall)
624 : Header->getFirstTerminator();
625 for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) {
626 if (std::prev(x: I)->isDebugInstr() || std::prev(x: I)->isPosition())
627 continue;
628 if (WebAssembly::isChild(MI: *std::prev(x: I), MFI))
629 AfterSet.insert(Ptr: &*std::prev(x: I));
630 else
631 break;
632 }
633
634 // Add the TRY.
635 auto InsertPos = getLatestInsertPos(MBB: Header, BeforeSet, AfterSet);
636 MachineInstr *Begin =
637 BuildMI(BB&: *Header, I: InsertPos, MIMD: Header->findDebugLoc(MBBI: InsertPos),
638 MCID: TII.get(Opcode: WebAssembly::TRY))
639 .addImm(Val: int64_t(WebAssembly::BlockType::Void));
640
641 // Decide where in Cont to put the END_TRY.
642 BeforeSet.clear();
643 AfterSet.clear();
644 for (const auto &MI : *Cont) {
645#ifndef NDEBUG
646 // END_TRY should precede existing LOOP markers.
647 if (MI.getOpcode() == WebAssembly::LOOP)
648 AfterSet.insert(&MI);
649
650 // All END_TRY markers placed earlier belong to exceptions that contains
651 // this one.
652 if (MI.getOpcode() == WebAssembly::END_TRY)
653 AfterSet.insert(&MI);
654#endif
655
656 // If there is a previously placed END_LOOP marker and its header is after
657 // where TRY marker is, this loop is contained within the 'catch' part, so
658 // the END_TRY marker should go after that. Otherwise, the whole try-catch
659 // is contained within this loop, so the END_TRY should go before that.
660 if (MI.getOpcode() == WebAssembly::END_LOOP) {
661 // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they
662 // are in the same BB, LOOP is always before TRY.
663 if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber())
664 BeforeSet.insert(Ptr: &MI);
665#ifndef NDEBUG
666 else
667 AfterSet.insert(&MI);
668#endif
669 }
670
671 // It is not possible for an END_BLOCK to be already in this block.
672 }
673
674 // Mark the end of the TRY.
675 InsertPos = getEarliestInsertPos(MBB: Cont, BeforeSet, AfterSet);
676 MachineInstr *End = BuildMI(BB&: *Cont, I: InsertPos, MIMD: Bottom->findBranchDebugLoc(),
677 MCID: TII.get(Opcode: WebAssembly::END_TRY));
678 registerTryScope(Begin, End, EHPad: &MBB);
679
680 // Track the farthest-spanning scope that ends at this point. We create two
681 // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB
682 // with 'try'). We need to create 'catch' -> 'try' mapping here too because
683 // markers should not span across 'catch'. For example, this should not
684 // happen:
685 //
686 // try
687 // block --| (X)
688 // catch |
689 // end_block --|
690 // end_try
691 for (auto *End : {&MBB, Cont})
692 updateScopeTops(Begin: Header, End);
693}
694
695void WebAssemblyCFGStackify::placeTryTableMarker(MachineBasicBlock &MBB) {
696 assert(MBB.isEHPad());
697 MachineFunction &MF = *MBB.getParent();
698 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
699 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
700 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
701 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
702 SortRegionInfo SRI(MLI, WEI);
703 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
704
705 // Compute the nearest common dominator of all unwind predecessors
706 MachineBasicBlock *Header = nullptr;
707 int MBBNumber = MBB.getNumber();
708 for (auto *Pred : MBB.predecessors()) {
709 if (Pred->getNumber() < MBBNumber) {
710 Header = Header ? MDT.findNearestCommonDominator(A: Header, B: Pred) : Pred;
711 assert(!explicitlyBranchesTo(Pred, &MBB) &&
712 "Explicit branch to an EH pad!");
713 }
714 }
715 if (!Header)
716 return;
717
718 // Unlike the end_try marker, we don't place an end marker at the end of
719 // exception bottom, i.e., at the end of the old 'catch' block. But we still
720 // consider the try-catch part as a scope when computing ScopeTops.
721 WebAssemblyException *WE = WEI.getExceptionFor(MBB: &MBB);
722 assert(WE);
723 MachineBasicBlock *Bottom = SRI.getBottom(WE);
724 auto Iter = std::next(x: Bottom->getIterator());
725 if (Iter == MF.end())
726 Iter--;
727 MachineBasicBlock *Cont = &*Iter;
728
729 // If the nearest common dominator is inside a more deeply nested context,
730 // walk out to the nearest scope which isn't more deeply nested.
731 for (MachineFunction::iterator I(Bottom), E(Header); I != E; --I) {
732 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
733 if (ScopeTop->getNumber() > Header->getNumber()) {
734 // Skip over an intervening scope.
735 I = std::next(x: ScopeTop->getIterator());
736 } else {
737 // We found a scope level at an appropriate depth.
738 Header = ScopeTop;
739 break;
740 }
741 }
742 }
743
744 // Decide where in Header to put the TRY_TABLE.
745
746 // Instructions that should go before the TRY_TABLE.
747 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
748 // Instructions that should go after the TRY_TABLE.
749 SmallPtrSet<const MachineInstr *, 4> AfterSet;
750 for (const auto &MI : *Header) {
751 // If there is a previously placed LOOP marker and the bottom block of the
752 // loop is above MBB, it should be after the TRY_TABLE, because the loop is
753 // nested in this TRY_TABLE. Otherwise it should be before the TRY_TABLE.
754 if (MI.getOpcode() == WebAssembly::LOOP) {
755 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
756 if (MBB.getNumber() > LoopBottom->getNumber())
757 AfterSet.insert(Ptr: &MI);
758#ifndef NDEBUG
759 else
760 BeforeSet.insert(&MI);
761#endif
762 }
763
764 // All previously inserted BLOCK/TRY_TABLE markers should be after the
765 // TRY_TABLE because they are all nested blocks/try_tables.
766 if (MI.getOpcode() == WebAssembly::BLOCK ||
767 MI.getOpcode() == WebAssembly::TRY_TABLE)
768 AfterSet.insert(Ptr: &MI);
769
770#ifndef NDEBUG
771 // All END_(BLOCK/LOOP/TRY_TABLE) markers should be before the TRY_TABLE.
772 if (MI.getOpcode() == WebAssembly::END_BLOCK ||
773 MI.getOpcode() == WebAssembly::END_LOOP ||
774 MI.getOpcode() == WebAssembly::END_TRY_TABLE)
775 BeforeSet.insert(&MI);
776#endif
777
778 // Terminators should go after the TRY_TABLE.
779 if (MI.isTerminator())
780 AfterSet.insert(Ptr: &MI);
781 }
782
783 // If Header unwinds to MBB (= Header contains 'invoke'), the try_table block
784 // should contain the call within it. So the call should go after the
785 // TRY_TABLE. The exception is when the header's terminator is a rethrow
786 // instruction, in which case that instruction, not a call instruction before
787 // it, is gonna throw.
788 MachineInstr *ThrowingCall = nullptr;
789 if (MBB.isPredecessor(MBB: Header)) {
790 auto TermPos = Header->getFirstTerminator();
791 if (TermPos == Header->end() ||
792 TermPos->getOpcode() != WebAssembly::RETHROW) {
793 for (auto &MI : reverse(C&: *Header)) {
794 if (MI.isCall()) {
795 AfterSet.insert(Ptr: &MI);
796 ThrowingCall = &MI;
797 // Possibly throwing calls are usually wrapped by EH_LABEL
798 // instructions. We don't want to split them and the call.
799 if (MI.getIterator() != Header->begin() &&
800 std::prev(x: MI.getIterator())->isEHLabel()) {
801 AfterSet.insert(Ptr: &*std::prev(x: MI.getIterator()));
802 ThrowingCall = &*std::prev(x: MI.getIterator());
803 }
804 break;
805 }
806 }
807 }
808 }
809
810 // Local expression tree should go after the TRY_TABLE.
811 // For BLOCK placement, we start the search from the previous instruction of a
812 // BB's terminator, but in TRY_TABLE's case, we should start from the previous
813 // instruction of a call that can throw, or a EH_LABEL that precedes the call,
814 // because the return values of the call's previous instructions can be
815 // stackified and consumed by the throwing call.
816 auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall)
817 : Header->getFirstTerminator();
818 for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) {
819 if (std::prev(x: I)->isDebugInstr() || std::prev(x: I)->isPosition())
820 continue;
821 if (WebAssembly::isChild(MI: *std::prev(x: I), MFI))
822 AfterSet.insert(Ptr: &*std::prev(x: I));
823 else
824 break;
825 }
826
827 // Add the TRY_TABLE and a BLOCK for the catch destination. We currently
828 // generate only one CATCH clause for a TRY_TABLE, so we need one BLOCK for
829 // its destination.
830 //
831 // Header:
832 // block
833 // try_table (catch ... $MBB)
834 // ...
835 //
836 // MBB:
837 // end_try_table
838 // end_block ;; destination of (catch ...)
839 // ... catch handler body ...
840 auto InsertPos = getLatestInsertPos(MBB: Header, BeforeSet, AfterSet);
841 MachineInstrBuilder BlockMIB =
842 BuildMI(BB&: *Header, I: InsertPos, MIMD: Header->findDebugLoc(MBBI: InsertPos),
843 MCID: TII.get(Opcode: WebAssembly::BLOCK));
844 auto *Block = BlockMIB.getInstr();
845 MachineInstrBuilder TryTableMIB =
846 BuildMI(BB&: *Header, I: InsertPos, MIMD: Header->findDebugLoc(MBBI: InsertPos),
847 MCID: TII.get(Opcode: WebAssembly::TRY_TABLE))
848 .addImm(Val: int64_t(WebAssembly::BlockType::Void))
849 .addImm(Val: 1); // # of catch clauses
850 auto *TryTable = TryTableMIB.getInstr();
851
852 // Add a CATCH_*** clause to the TRY_TABLE. These are pseudo instructions
853 // following the destination END_BLOCK to simulate block return values,
854 // because we currently don't support them.
855 const auto &TLI =
856 *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
857 WebAssembly::BlockType PtrTy =
858 TLI.getPointerTy(DL: MF.getDataLayout()) == MVT::i32
859 ? WebAssembly::BlockType::I32
860 : WebAssembly::BlockType::I64;
861 auto *Catch = WebAssembly::findCatch(EHPad: &MBB);
862 switch (Catch->getOpcode()) {
863 case WebAssembly::CATCH:
864 // CATCH's destination block's return type is the extracted value type,
865 // which is currently the thrown value's pointer type for all supported
866 // tags.
867 BlockMIB.addImm(Val: int64_t(PtrTy));
868 TryTableMIB.addImm(Val: wasm::WASM_OPCODE_CATCH);
869 for (const auto &Use : Catch->uses()) {
870 // The only use operand a CATCH can have is the tag symbol.
871 TryTableMIB.addExternalSymbol(FnName: Use.getSymbolName());
872 break;
873 }
874 TryTableMIB.addMBB(MBB: &MBB);
875 break;
876 case WebAssembly::CATCH_REF:
877 // CATCH_REF's destination block's return type is the extracted value type
878 // followed by an exnref, which is (i32, exnref) in our case. We assign the
879 // actual multiavlue signature in MCInstLower. MO_CATCH_BLOCK_SIG signals
880 // that this operand is used for catch_ref's multivalue destination.
881 BlockMIB.addImm(Val: int64_t(WebAssembly::BlockType::Multivalue));
882 Block->getOperand(i: 0).setTargetFlags(WebAssemblyII::MO_CATCH_BLOCK_SIG);
883 TryTableMIB.addImm(Val: wasm::WASM_OPCODE_CATCH_REF);
884 for (const auto &Use : Catch->uses()) {
885 TryTableMIB.addExternalSymbol(FnName: Use.getSymbolName());
886 break;
887 }
888 TryTableMIB.addMBB(MBB: &MBB);
889 break;
890 case WebAssembly::CATCH_ALL:
891 // CATCH_ALL's destination block's return type is void.
892 BlockMIB.addImm(Val: int64_t(WebAssembly::BlockType::Void));
893 TryTableMIB.addImm(Val: wasm::WASM_OPCODE_CATCH_ALL);
894 TryTableMIB.addMBB(MBB: &MBB);
895 break;
896 case WebAssembly::CATCH_ALL_REF:
897 // CATCH_ALL_REF's destination block's return type is exnref.
898 BlockMIB.addImm(Val: int64_t(WebAssembly::BlockType::Exnref));
899 TryTableMIB.addImm(Val: wasm::WASM_OPCODE_CATCH_ALL_REF);
900 TryTableMIB.addMBB(MBB: &MBB);
901 break;
902 }
903
904 // Decide where in MBB to put the END_TRY_TABLE, and the END_BLOCK for the
905 // CATCH destination.
906 BeforeSet.clear();
907 AfterSet.clear();
908 for (const auto &MI : MBB) {
909#ifndef NDEBUG
910 // END_TRY_TABLE should precede existing LOOP markers.
911 if (MI.getOpcode() == WebAssembly::LOOP)
912 AfterSet.insert(&MI);
913#endif
914
915 // If there is a previously placed END_LOOP marker and the header of the
916 // loop is above this try_table's header, the END_LOOP should be placed
917 // after the END_TRY_TABLE, because the loop contains this block. Otherwise
918 // the END_LOOP should be placed before the END_TRY_TABLE.
919 if (MI.getOpcode() == WebAssembly::END_LOOP) {
920 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
921 BeforeSet.insert(Ptr: &MI);
922#ifndef NDEBUG
923 else
924 AfterSet.insert(&MI);
925#endif
926 }
927
928#ifndef NDEBUG
929 // CATCH, CATCH_REF, CATCH_ALL, and CATCH_ALL_REF are pseudo-instructions
930 // that simulate the block return value, so they should be placed after the
931 // END_TRY_TABLE.
932 if (WebAssembly::isCatch(MI.getOpcode()))
933 AfterSet.insert(&MI);
934#endif
935 }
936
937 // Mark the end of the TRY_TABLE and the BLOCK.
938 InsertPos = getEarliestInsertPos(MBB: &MBB, BeforeSet, AfterSet);
939 MachineInstr *EndTryTable =
940 BuildMI(BB&: MBB, I: InsertPos, MIMD: MBB.findPrevDebugLoc(MBBI: InsertPos),
941 MCID: TII.get(Opcode: WebAssembly::END_TRY_TABLE));
942 registerTryScope(Begin: TryTable, End: EndTryTable, EHPad: &MBB);
943 MachineInstr *EndBlock =
944 BuildMI(BB&: MBB, I: InsertPos, MIMD: MBB.findPrevDebugLoc(MBBI: InsertPos),
945 MCID: TII.get(Opcode: WebAssembly::END_BLOCK));
946 registerScope(Begin: Block, End: EndBlock);
947
948 // Track the farthest-spanning scope that ends at this point.
949 // Unlike the end_try, even if we don't put a end marker at the end of catch
950 // block, we still have to create two mappings: (BB with 'end_try_table' -> BB
951 // with 'try_table') and (BB after the (conceptual) catch block -> BB with
952 // 'try_table').
953 //
954 // This is what can happen if we don't create the latter mapping:
955 //
956 // Suppoe in the legacy EH we have this code:
957 // try
958 // try
959 // code1
960 // catch (a)
961 // end_try
962 // code2
963 // catch (b)
964 // end_try
965 //
966 // If we don't create the latter mapping, try_table markers would be placed
967 // like this:
968 // try_table
969 // code1
970 // end_try_table (a)
971 // try_table
972 // code2
973 // end_try_table (b)
974 //
975 // This does not reflect the original structure, and more important problem
976 // is, in case 'code1' has an unwind mismatch and should unwind to
977 // 'end_try_table (b)' rather than 'end_try_table (a)', we don't have a way to
978 // make it jump after 'end_try_table (b)' without creating another block. So
979 // even if we don't place 'end_try' marker at the end of 'catch' block
980 // anymore, we create ScopeTops mapping the same way as the legacy exception,
981 // so the resulting code will look like:
982 // try_table
983 // try_table
984 // code1
985 // end_try_table (a)
986 // code2
987 // end_try_table (b)
988 for (auto *End : {&MBB, Cont})
989 updateScopeTops(Begin: Header, End);
990}
991
992void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
993 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
994
995 // When there is an unconditional branch right before a catch instruction and
996 // it branches to the end of end_try marker, we don't need the branch, because
997 // if there is no exception, the control flow transfers to that point anyway.
998 // bb0:
999 // try
1000 // ...
1001 // br bb2 <- Not necessary
1002 // bb1 (ehpad):
1003 // catch
1004 // ...
1005 // bb2: <- Continuation BB
1006 // end
1007 //
1008 // A more involved case: When the BB where 'end' is located is an another EH
1009 // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example,
1010 // bb0:
1011 // try
1012 // try
1013 // ...
1014 // br bb3 <- Not necessary
1015 // bb1 (ehpad):
1016 // catch
1017 // bb2 (ehpad):
1018 // end
1019 // catch
1020 // ...
1021 // bb3: <- Continuation BB
1022 // end
1023 //
1024 // When the EH pad at hand is bb1, its matching end_try is in bb2. But it is
1025 // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the
1026 // code can be deleted. This is why we run 'while' until 'Cont' is not an EH
1027 // pad.
1028 for (auto &MBB : MF) {
1029 if (!MBB.isEHPad())
1030 continue;
1031
1032 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1033 SmallVector<MachineOperand, 4> Cond;
1034 MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
1035
1036 MachineBasicBlock *Cont = &MBB;
1037 while (Cont->isEHPad()) {
1038 MachineInstr *Try = EHPadToTry[Cont];
1039 MachineInstr *EndTry = BeginToEnd[Try];
1040 // We started from an EH pad, so the end marker cannot be a delegate
1041 assert(EndTry->getOpcode() != WebAssembly::DELEGATE);
1042 Cont = EndTry->getParent();
1043 }
1044
1045 bool Analyzable = !TII.analyzeBranch(MBB&: *EHPadLayoutPred, TBB, FBB, Cond);
1046 // This condition means either
1047 // 1. This BB ends with a single unconditional branch whose destinaion is
1048 // Cont.
1049 // 2. This BB ends with a conditional branch followed by an unconditional
1050 // branch, and the unconditional branch's destination is Cont.
1051 // In both cases, we want to remove the last (= unconditional) branch.
1052 if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
1053 (!Cond.empty() && FBB && FBB == Cont))) {
1054 bool ErasedUncondBr = false;
1055 (void)ErasedUncondBr;
1056 for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin();
1057 I != E; --I) {
1058 auto PrevI = std::prev(x: I);
1059 if (PrevI->isTerminator()) {
1060 assert(PrevI->getOpcode() == WebAssembly::BR);
1061 PrevI->eraseFromParent();
1062 ErasedUncondBr = true;
1063 break;
1064 }
1065 }
1066 assert(ErasedUncondBr && "Unconditional branch not erased!");
1067 }
1068 }
1069
1070 // When there are block / end_block markers that overlap with try / end_try
1071 // markers, and the block and try markers' return types are the same, the
1072 // block /end_block markers are not necessary, because try / end_try markers
1073 // also can serve as boundaries for branches.
1074 // block <- Not necessary
1075 // try
1076 // ...
1077 // catch
1078 // ...
1079 // end
1080 // end <- Not necessary
1081 SmallVector<MachineInstr *, 32> ToDelete;
1082 for (auto &MBB : MF) {
1083 for (auto &MI : MBB) {
1084 if (MI.getOpcode() != WebAssembly::TRY)
1085 continue;
1086 MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
1087 if (EndTry->getOpcode() == WebAssembly::DELEGATE)
1088 continue;
1089
1090 MachineBasicBlock *TryBB = Try->getParent();
1091 MachineBasicBlock *Cont = EndTry->getParent();
1092 int64_t RetType = Try->getOperand(i: 0).getImm();
1093 for (auto B = Try->getIterator(), E = std::next(x: EndTry->getIterator());
1094 B != TryBB->begin() && E != Cont->end() &&
1095 std::prev(x: B)->getOpcode() == WebAssembly::BLOCK &&
1096 E->getOpcode() == WebAssembly::END_BLOCK &&
1097 std::prev(x: B)->getOperand(i: 0).getImm() == RetType;
1098 --B, ++E) {
1099 ToDelete.push_back(Elt: &*std::prev(x: B));
1100 ToDelete.push_back(Elt: &*E);
1101 }
1102 }
1103 }
1104 for (auto *MI : ToDelete) {
1105 if (MI->getOpcode() == WebAssembly::BLOCK)
1106 unregisterScope(Begin: MI);
1107 MI->eraseFromParent();
1108 }
1109}
1110
1111// When MBB is split into MBB and Split, we should unstackify defs in MBB that
1112// have their uses in Split.
1113static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB,
1114 MachineBasicBlock &Split) {
1115 MachineFunction &MF = *MBB.getParent();
1116 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1117 auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1118 auto &MRI = MF.getRegInfo();
1119
1120 for (auto &MI : Split) {
1121 for (auto &MO : MI.explicit_uses()) {
1122 if (!MO.isReg() || MO.getReg().isPhysical())
1123 continue;
1124 if (MachineInstr *Def = MRI.getUniqueVRegDef(Reg: MO.getReg()))
1125 if (Def->getParent() == &MBB)
1126 MFI.unstackifyVReg(VReg: MO.getReg());
1127 }
1128 }
1129
1130 // In RegStackify, when a register definition is used multiple times,
1131 // Reg = INST ...
1132 // INST ..., Reg, ...
1133 // INST ..., Reg, ...
1134 // INST ..., Reg, ...
1135 //
1136 // we introduce a TEE, which has the following form:
1137 // DefReg = INST ...
1138 // TeeReg, Reg = TEE_... DefReg
1139 // INST ..., TeeReg, ...
1140 // INST ..., Reg, ...
1141 // INST ..., Reg, ...
1142 // with DefReg and TeeReg stackified but Reg not stackified.
1143 //
1144 // But the invariant that TeeReg should be stackified can be violated while we
1145 // unstackify registers in the split BB above. In this case, we convert TEEs
1146 // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals.
1147 // DefReg = INST ...
1148 // TeeReg = COPY DefReg
1149 // Reg = COPY DefReg
1150 // INST ..., TeeReg, ...
1151 // INST ..., Reg, ...
1152 // INST ..., Reg, ...
1153 for (MachineInstr &MI : llvm::make_early_inc_range(Range&: MBB)) {
1154 if (!WebAssembly::isTee(Opc: MI.getOpcode()))
1155 continue;
1156 Register TeeReg = MI.getOperand(i: 0).getReg();
1157 Register Reg = MI.getOperand(i: 1).getReg();
1158 Register DefReg = MI.getOperand(i: 2).getReg();
1159 if (!MFI.isVRegStackified(VReg: TeeReg)) {
1160 // Now we are not using TEE anymore, so unstackify DefReg too
1161 MFI.unstackifyVReg(VReg: DefReg);
1162 unsigned CopyOpc =
1163 WebAssembly::getCopyOpcodeForRegClass(RC: MRI.getRegClass(Reg: DefReg));
1164 BuildMI(BB&: MBB, I: &MI, MIMD: MI.getDebugLoc(), MCID: TII.get(Opcode: CopyOpc), DestReg: TeeReg)
1165 .addReg(RegNo: DefReg);
1166 BuildMI(BB&: MBB, I: &MI, MIMD: MI.getDebugLoc(), MCID: TII.get(Opcode: CopyOpc), DestReg: Reg).addReg(RegNo: DefReg);
1167 MI.eraseFromParent();
1168 }
1169 }
1170}
1171
1172// Wrap the given range of instructions with a try-delegate that targets
1173// 'UnwindDest'. RangeBegin and RangeEnd are inclusive.
1174void WebAssemblyCFGStackify::addNestedTryDelegate(
1175 MachineInstr *RangeBegin, MachineInstr *RangeEnd,
1176 MachineBasicBlock *UnwindDest) {
1177 auto *BeginBB = RangeBegin->getParent();
1178 auto *EndBB = RangeEnd->getParent();
1179 MachineFunction &MF = *BeginBB->getParent();
1180 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1181 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1182
1183 // Local expression tree before the first call of this range should go
1184 // after the nested TRY.
1185 SmallPtrSet<const MachineInstr *, 4> AfterSet;
1186 AfterSet.insert(Ptr: RangeBegin);
1187 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();
1188 I != E; --I) {
1189 if (std::prev(x: I)->isDebugInstr() || std::prev(x: I)->isPosition())
1190 continue;
1191 if (WebAssembly::isChild(MI: *std::prev(x: I), MFI))
1192 AfterSet.insert(Ptr: &*std::prev(x: I));
1193 else
1194 break;
1195 }
1196
1197 // Create the nested try instruction.
1198 auto TryPos = getLatestInsertPos(
1199 MBB: BeginBB, BeforeSet: SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
1200 MachineInstr *Try = BuildMI(BB&: *BeginBB, I: TryPos, MIMD: RangeBegin->getDebugLoc(),
1201 MCID: TII.get(Opcode: WebAssembly::TRY))
1202 .addImm(Val: int64_t(WebAssembly::BlockType::Void));
1203
1204 // Create a BB to insert the 'delegate' instruction.
1205 MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock();
1206 // If the destination of 'delegate' is not the caller, adds the destination to
1207 // the BB's successors.
1208 if (UnwindDest != FakeCallerBB)
1209 DelegateBB->addSuccessor(Succ: UnwindDest);
1210
1211 auto SplitPos = std::next(x: RangeEnd->getIterator());
1212 if (SplitPos == EndBB->end()) {
1213 // If the range's end instruction is at the end of the BB, insert the new
1214 // delegate BB after the current BB.
1215 MF.insert(MBBI: std::next(x: EndBB->getIterator()), MBB: DelegateBB);
1216 EndBB->addSuccessor(Succ: DelegateBB);
1217
1218 } else {
1219 // When the split pos is in the middle of a BB, we split the BB into two and
1220 // put the 'delegate' BB in between. We normally create a split BB and make
1221 // it a successor of the original BB (CatchAfterSplit == false), but in case
1222 // the BB is an EH pad and there is a 'catch' after the split pos
1223 // (CatchAfterSplit == true), we should preserve the BB's property,
1224 // including that it is an EH pad, in the later part of the BB, where the
1225 // 'catch' is.
1226 bool CatchAfterSplit = false;
1227 if (EndBB->isEHPad()) {
1228 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
1229 I != E; ++I) {
1230 if (WebAssembly::isCatch(Opc: I->getOpcode())) {
1231 CatchAfterSplit = true;
1232 break;
1233 }
1234 }
1235 }
1236
1237 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
1238 if (!CatchAfterSplit) {
1239 // If the range's end instruction is in the middle of the BB, we split the
1240 // BB into two and insert the delegate BB in between.
1241 // - Before:
1242 // bb:
1243 // range_end
1244 // other_insts
1245 //
1246 // - After:
1247 // pre_bb: (previous 'bb')
1248 // range_end
1249 // delegate_bb: (new)
1250 // delegate
1251 // post_bb: (new)
1252 // other_insts
1253 PreBB = EndBB;
1254 PostBB = MF.CreateMachineBasicBlock();
1255 MF.insert(MBBI: std::next(x: PreBB->getIterator()), MBB: PostBB);
1256 MF.insert(MBBI: std::next(x: PreBB->getIterator()), MBB: DelegateBB);
1257 PostBB->splice(Where: PostBB->end(), Other: PreBB, From: SplitPos, To: PreBB->end());
1258 PostBB->transferSuccessors(FromMBB: PreBB);
1259 } else {
1260 // - Before:
1261 // ehpad:
1262 // range_end
1263 // catch
1264 // ...
1265 //
1266 // - After:
1267 // pre_bb: (new)
1268 // range_end
1269 // delegate_bb: (new)
1270 // delegate
1271 // post_bb: (previous 'ehpad')
1272 // catch
1273 // ...
1274 assert(EndBB->isEHPad());
1275 PreBB = MF.CreateMachineBasicBlock();
1276 PostBB = EndBB;
1277 MF.insert(MBBI: PostBB->getIterator(), MBB: PreBB);
1278 MF.insert(MBBI: PostBB->getIterator(), MBB: DelegateBB);
1279 PreBB->splice(Where: PreBB->end(), Other: PostBB, From: PostBB->begin(), To: SplitPos);
1280 // We don't need to transfer predecessors of the EH pad to 'PreBB',
1281 // because an EH pad's predecessors are all through unwind edges and they
1282 // should still unwind to the EH pad, not PreBB.
1283 }
1284 unstackifyVRegsUsedInSplitBB(MBB&: *PreBB, Split&: *PostBB);
1285 PreBB->addSuccessor(Succ: DelegateBB);
1286 PreBB->addSuccessor(Succ: PostBB);
1287 }
1288
1289 // Add a 'delegate' instruction in the delegate BB created above.
1290 MachineInstr *Delegate = BuildMI(BB: DelegateBB, MIMD: RangeEnd->getDebugLoc(),
1291 MCID: TII.get(Opcode: WebAssembly::DELEGATE))
1292 .addMBB(MBB: UnwindDest);
1293 registerTryScope(Begin: Try, End: Delegate, EHPad: nullptr);
1294}
1295
1296// Given an unwind destination, return a trampoline BB. A trampoline BB is a
1297// destination of a nested try_table inserted to fix an unwind mismatch. It
1298// contains an end_block, which is the target of the try_table, and a throw_ref,
1299// to rethrow the exception to the right try_table.
1300// try_table (catch ... )
1301// block exnref
1302// ...
1303// try_table (catch_all_ref N)
1304// some code
1305// end_try_table
1306// ...
1307// unreachable
1308// end_block ;; Trampoline BB
1309// throw_ref
1310// end_try_table
1311MachineBasicBlock *
1312WebAssemblyCFGStackify::getTrampolineBlock(MachineBasicBlock *UnwindDest) {
1313 // We need one trampoline BB per unwind destination, even though there are
1314 // multiple try_tables target the same unwind destination. If we have already
1315 // created one for the given UnwindDest, return it.
1316 auto It = UnwindDestToTrampoline.find(Val: UnwindDest);
1317 if (It != UnwindDestToTrampoline.end())
1318 return It->second;
1319
1320 auto &MF = *UnwindDest->getParent();
1321 auto &MRI = MF.getRegInfo();
1322 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1323
1324 MachineInstr *Block = nullptr;
1325 MachineBasicBlock *TrampolineBB = nullptr;
1326 DebugLoc EndDebugLoc;
1327
1328 if (UnwindDest == getFakeCallerBlock(MF)) {
1329 // If the unwind destination is the caller, create a caller-dedicated
1330 // trampoline BB at the end of the function and wrap the whole function with
1331 // a block.
1332 auto BeginPos = MF.begin()->begin();
1333 while (WebAssembly::isArgument(Opc: BeginPos->getOpcode()))
1334 BeginPos++;
1335 Block = BuildMI(BB&: *MF.begin(), I: BeginPos, MIMD: MF.begin()->begin()->getDebugLoc(),
1336 MCID: TII.get(Opcode: WebAssembly::BLOCK))
1337 .addImm(Val: int64_t(WebAssembly::BlockType::Exnref));
1338 TrampolineBB = getCallerTrampolineBlock(MF);
1339 MachineBasicBlock *PrevBB = &*std::prev(x: CallerTrampolineBB->getIterator());
1340 EndDebugLoc = PrevBB->findPrevDebugLoc(MBBI: PrevBB->end());
1341 } else {
1342 // If the unwind destination is another EH pad, create a trampoline BB for
1343 // the unwind dest and insert a block instruction right after the target
1344 // try_table.
1345 auto *TargetBeginTry = EHPadToTry[UnwindDest];
1346 auto *TargetEndTry = BeginToEnd[TargetBeginTry];
1347 auto *TargetBeginBB = TargetBeginTry->getParent();
1348 auto *TargetEndBB = TargetEndTry->getParent();
1349
1350 Block = BuildMI(BB&: *TargetBeginBB, I: std::next(x: TargetBeginTry->getIterator()),
1351 MIMD: TargetBeginTry->getDebugLoc(), MCID: TII.get(Opcode: WebAssembly::BLOCK))
1352 .addImm(Val: int64_t(WebAssembly::BlockType::Exnref));
1353 TrampolineBB = MF.CreateMachineBasicBlock();
1354 EndDebugLoc = TargetEndTry->getDebugLoc();
1355 MF.insert(MBBI: TargetEndBB->getIterator(), MBB: TrampolineBB);
1356 TrampolineBB->addSuccessor(Succ: UnwindDest);
1357 }
1358
1359 // Insert an end_block, catch_all_ref (pseudo instruction), and throw_ref
1360 // instructions in the trampoline BB.
1361 MachineInstr *EndBlock =
1362 BuildMI(BB: TrampolineBB, MIMD: EndDebugLoc, MCID: TII.get(Opcode: WebAssembly::END_BLOCK));
1363 auto ExnReg = MRI.createVirtualRegister(RegClass: &WebAssembly::EXNREFRegClass);
1364 BuildMI(BB: TrampolineBB, MIMD: EndDebugLoc, MCID: TII.get(Opcode: WebAssembly::CATCH_ALL_REF))
1365 .addDef(RegNo: ExnReg);
1366 BuildMI(BB: TrampolineBB, MIMD: EndDebugLoc, MCID: TII.get(Opcode: WebAssembly::THROW_REF))
1367 .addReg(RegNo: ExnReg);
1368
1369 // The trampoline BB's return type is exnref because it is a target of
1370 // catch_all_ref. But the body type of the block we just created is not. We
1371 // add an 'unreachable' right before the 'end_block' to make the code valid.
1372 MachineBasicBlock *TrampolineLayoutPred = TrampolineBB->getPrevNode();
1373 BuildMI(BB: TrampolineLayoutPred, MIMD: TrampolineLayoutPred->findBranchDebugLoc(),
1374 MCID: TII.get(Opcode: WebAssembly::UNREACHABLE));
1375
1376 registerScope(Begin: Block, End: EndBlock);
1377 UnwindDestToTrampoline[UnwindDest] = TrampolineBB;
1378 return TrampolineBB;
1379}
1380
1381// Wrap the given range of instructions with a try_table-end_try_table that
1382// targets 'UnwindDest'. RangeBegin and RangeEnd are inclusive.
1383void WebAssemblyCFGStackify::addNestedTryTable(MachineInstr *RangeBegin,
1384 MachineInstr *RangeEnd,
1385 MachineBasicBlock *UnwindDest) {
1386 auto *BeginBB = RangeBegin->getParent();
1387 auto *EndBB = RangeEnd->getParent();
1388
1389 MachineFunction &MF = *BeginBB->getParent();
1390 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1391 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1392
1393 // Get the trampoline BB that the new try_table will unwind to.
1394 auto *TrampolineBB = getTrampolineBlock(UnwindDest);
1395
1396 // Local expression tree before the first call of this range should go
1397 // after the nested TRY_TABLE.
1398 SmallPtrSet<const MachineInstr *, 4> AfterSet;
1399 AfterSet.insert(Ptr: RangeBegin);
1400 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();
1401 I != E; --I) {
1402 if (std::prev(x: I)->isDebugInstr() || std::prev(x: I)->isPosition())
1403 continue;
1404 if (WebAssembly::isChild(MI: *std::prev(x: I), MFI))
1405 AfterSet.insert(Ptr: &*std::prev(x: I));
1406 else
1407 break;
1408 }
1409
1410 // Create the nested try_table instruction.
1411 auto TryTablePos = getLatestInsertPos(
1412 MBB: BeginBB, BeforeSet: SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
1413 MachineInstr *TryTable =
1414 BuildMI(BB&: *BeginBB, I: TryTablePos, MIMD: RangeBegin->getDebugLoc(),
1415 MCID: TII.get(Opcode: WebAssembly::TRY_TABLE))
1416 .addImm(Val: int64_t(WebAssembly::BlockType::Void))
1417 .addImm(Val: 1) // # of catch clauses
1418 .addImm(Val: wasm::WASM_OPCODE_CATCH_ALL_REF)
1419 .addMBB(MBB: TrampolineBB);
1420
1421 // Create a BB to insert the 'end_try_table' instruction.
1422 MachineBasicBlock *EndTryTableBB = MF.CreateMachineBasicBlock();
1423 EndTryTableBB->addSuccessor(Succ: TrampolineBB);
1424
1425 auto SplitPos = std::next(x: RangeEnd->getIterator());
1426 if (SplitPos == EndBB->end()) {
1427 // If the range's end instruction is at the end of the BB, insert the new
1428 // end_try_table BB after the current BB.
1429 MF.insert(MBBI: std::next(x: EndBB->getIterator()), MBB: EndTryTableBB);
1430 EndBB->addSuccessor(Succ: EndTryTableBB);
1431
1432 } else {
1433 // When the split pos is in the middle of a BB, we split the BB into two and
1434 // put the 'end_try_table' BB in between. We normally create a split BB and
1435 // make it a successor of the original BB (CatchAfterSplit == false), but in
1436 // case the BB is an EH pad and there is a 'catch' after split pos
1437 // (CatchAfterSplit == true), we should preserve the BB's property,
1438 // including that it is an EH pad, in the later part of the BB, where the
1439 // 'catch' is.
1440 bool CatchAfterSplit = false;
1441 if (EndBB->isEHPad()) {
1442 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
1443 I != E; ++I) {
1444 if (WebAssembly::isCatch(Opc: I->getOpcode())) {
1445 CatchAfterSplit = true;
1446 break;
1447 }
1448 }
1449 }
1450
1451 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
1452 if (!CatchAfterSplit) {
1453 // If the range's end instruction is in the middle of the BB, we split the
1454 // BB into two and insert the end_try_table BB in between.
1455 // - Before:
1456 // bb:
1457 // range_end
1458 // other_insts
1459 //
1460 // - After:
1461 // pre_bb: (previous 'bb')
1462 // range_end
1463 // end_try_table_bb: (new)
1464 // end_try_table
1465 // post_bb: (new)
1466 // other_insts
1467 PreBB = EndBB;
1468 PostBB = MF.CreateMachineBasicBlock();
1469 MF.insert(MBBI: std::next(x: PreBB->getIterator()), MBB: PostBB);
1470 MF.insert(MBBI: std::next(x: PreBB->getIterator()), MBB: EndTryTableBB);
1471 PostBB->splice(Where: PostBB->end(), Other: PreBB, From: SplitPos, To: PreBB->end());
1472 PostBB->transferSuccessors(FromMBB: PreBB);
1473 } else {
1474 // - Before:
1475 // ehpad:
1476 // range_end
1477 // catch
1478 // ...
1479 //
1480 // - After:
1481 // pre_bb: (new)
1482 // range_end
1483 // end_try_table_bb: (new)
1484 // end_try_table
1485 // post_bb: (previous 'ehpad')
1486 // catch
1487 // ...
1488 assert(EndBB->isEHPad());
1489 PreBB = MF.CreateMachineBasicBlock();
1490 PostBB = EndBB;
1491 MF.insert(MBBI: PostBB->getIterator(), MBB: PreBB);
1492 MF.insert(MBBI: PostBB->getIterator(), MBB: EndTryTableBB);
1493 PreBB->splice(Where: PreBB->end(), Other: PostBB, From: PostBB->begin(), To: SplitPos);
1494 // We don't need to transfer predecessors of the EH pad to 'PreBB',
1495 // because an EH pad's predecessors are all through unwind edges and they
1496 // should still unwind to the EH pad, not PreBB.
1497 }
1498 unstackifyVRegsUsedInSplitBB(MBB&: *PreBB, Split&: *PostBB);
1499 PreBB->addSuccessor(Succ: EndTryTableBB);
1500 PreBB->addSuccessor(Succ: PostBB);
1501 }
1502
1503 // Add a 'end_try_table' instruction in the EndTryTable BB created above.
1504 MachineInstr *EndTryTable = BuildMI(BB: EndTryTableBB, MIMD: RangeEnd->getDebugLoc(),
1505 MCID: TII.get(Opcode: WebAssembly::END_TRY_TABLE));
1506 registerTryScope(Begin: TryTable, End: EndTryTable, EHPad: TrampolineBB);
1507}
1508
1509// In the standard (exnref) EH, we fix unwind mismatches by adding a new
1510// block~end_block inside of the unwind destination try_table~end_try_table:
1511// try_table ...
1512// block exnref ;; (new)
1513// ...
1514// try_table (catch_all_ref N) ;; (new) to trampoline BB
1515// code
1516// end_try_table ;; (new)
1517// ...
1518// end_block ;; (new) trampoline BB
1519// throw_ref ;; (new)
1520// end_try_table
1521//
1522// To do this, we will create a new BB that will contain the new 'end_block' and
1523// 'throw_ref' and insert it before the 'end_try_table' BB.
1524//
1525// But there are cases when there are 'end_loop'(s) before the 'end_try_table'
1526// in the same BB. (There can't be 'end_block' before 'end_try_table' in the
1527// same BB because EH pads can't be directly branched to.) Then after fixing
1528// unwind mismatches this will create the mismatching markers like below:
1529// bb0:
1530// try_table
1531// block exnref
1532// ...
1533// loop
1534// ...
1535// new_bb:
1536// end_block
1537// end_try_table_bb:
1538// end_loop
1539// end_try_table
1540//
1541// So if an end_try_table BB has an end_loop before the end_try_table, we split
1542// the BB with the end_loop as a separate BB before the end_try_table BB, so
1543// that after we fix the unwind mismatch, the code will be like:
1544// bb0:
1545// try_table
1546// block exnref
1547// ...
1548// loop
1549// ...
1550// end_loop_bb:
1551// end_loop
1552// new_bb:
1553// end_block
1554// end_try_table_bb:
1555// end_try_table
1556static void splitEndLoopBB(MachineBasicBlock *EndTryTableBB) {
1557 auto &MF = *EndTryTableBB->getParent();
1558 MachineInstr *EndTryTable = nullptr, *EndLoop = nullptr;
1559 for (auto &MI : reverse(C&: *EndTryTableBB)) {
1560 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE) {
1561 EndTryTable = &MI;
1562 continue;
1563 }
1564 if (EndTryTable && MI.getOpcode() == WebAssembly::END_LOOP) {
1565 EndLoop = &MI;
1566 break;
1567 }
1568 }
1569 if (!EndLoop)
1570 return;
1571
1572 auto *EndLoopBB = MF.CreateMachineBasicBlock();
1573 MF.insert(MBBI: EndTryTableBB->getIterator(), MBB: EndLoopBB);
1574 auto SplitPos = std::next(x: EndLoop->getIterator());
1575 EndLoopBB->splice(Where: EndLoopBB->end(), Other: EndTryTableBB, From: EndTryTableBB->begin(),
1576 To: SplitPos);
1577 EndLoopBB->addSuccessor(Succ: EndTryTableBB);
1578}
1579
1580// Print the BB name in the form of bb.NUMBER.ORIGINAL_NAME.
1581// e.g., bb.3.catch.start
1582[[maybe_unused]] static std::string getBBName(const MachineBasicBlock *MBB) {
1583 std::string Name = "bb.";
1584 Name += Twine(MBB->getNumber()).str();
1585 if (MBB->getBasicBlock()) {
1586 Name += ".";
1587 Name += MBB->getBasicBlock()->getName();
1588 }
1589 return Name;
1590}
1591
1592bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {
1593 // This function is used for both the legacy EH and the standard (exnref) EH,
1594 // and the reason we have unwind mismatches is the same for the both of them,
1595 // but the code examples in the comments are going to be different. To make
1596 // the description less confusing, we write the basically same comments twice,
1597 // once for the legacy EH and the standard EH.
1598 //
1599 // -- Legacy EH --------------------------------------------------------------
1600 //
1601 // Linearizing the control flow by placing TRY / END_TRY markers can create
1602 // mismatches in unwind destinations for throwing instructions, such as calls.
1603 //
1604 // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate'
1605 // instruction delegates an exception to an outer 'catch'. It can target not
1606 // only 'catch' but all block-like structures including another 'delegate',
1607 // but with slightly different semantics than branches. When it targets a
1608 // 'catch', it will delegate the exception to that catch. It is being
1609 // discussed how to define the semantics when 'delegate''s target is a non-try
1610 // block: it will either be a validation failure or it will target the next
1611 // outer try-catch. But anyway our LLVM backend currently does not generate
1612 // such code. The example below illustrates where the 'delegate' instruction
1613 // in the middle will delegate the exception to, depending on the value of N.
1614 // try
1615 // try
1616 // block
1617 // try
1618 // try
1619 // call @foo
1620 // delegate N ;; Where will this delegate to?
1621 // catch ;; N == 0
1622 // end
1623 // end ;; N == 1 (invalid; will not be generated)
1624 // delegate ;; N == 2
1625 // catch ;; N == 3
1626 // end
1627 // ;; N == 4 (to caller)
1628 //
1629 // 1. When an instruction may throw, but the EH pad it will unwind to can be
1630 // different from the original CFG.
1631 //
1632 // Example: we have the following CFG:
1633 // bb0:
1634 // call @foo ; if it throws, unwind to bb2
1635 // bb1:
1636 // call @bar ; if it throws, unwind to bb3
1637 // bb2 (ehpad):
1638 // catch
1639 // ...
1640 // bb3 (ehpad)
1641 // catch
1642 // ...
1643 //
1644 // And the CFG is sorted in this order. Then after placing TRY markers, it
1645 // will look like: (BB markers are omitted)
1646 // try
1647 // try
1648 // call @foo
1649 // call @bar ;; if it throws, unwind to bb3
1650 // catch ;; ehpad (bb2)
1651 // ...
1652 // end_try
1653 // catch ;; ehpad (bb3)
1654 // ...
1655 // end_try
1656 //
1657 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is
1658 // supposed to end up. We solve this problem by wrapping the mismatching call
1659 // with an inner try-delegate that rethrows the exception to the right
1660 // 'catch'.
1661 //
1662 // try
1663 // try
1664 // call @foo
1665 // try ;; (new)
1666 // call @bar
1667 // delegate 1 (bb3) ;; (new)
1668 // catch ;; ehpad (bb2)
1669 // ...
1670 // end_try
1671 // catch ;; ehpad (bb3)
1672 // ...
1673 // end_try
1674 //
1675 // ---
1676 // 2. The same as 1, but in this case an instruction unwinds to a caller
1677 // function and not another EH pad.
1678 //
1679 // Example: we have the following CFG:
1680 // bb0:
1681 // call @foo ; if it throws, unwind to bb2
1682 // bb1:
1683 // call @bar ; if it throws, unwind to caller
1684 // bb2 (ehpad):
1685 // catch
1686 // ...
1687 //
1688 // And the CFG is sorted in this order. Then after placing TRY markers, it
1689 // will look like:
1690 // try
1691 // call @foo
1692 // call @bar ;; if it throws, unwind to caller
1693 // catch ;; ehpad (bb2)
1694 // ...
1695 // end_try
1696 //
1697 // Now if bar() throws, it is going to end up in bb2, when it is supposed
1698 // throw up to the caller. We solve this problem in the same way, but in this
1699 // case 'delegate's immediate argument is the number of block depths + 1,
1700 // which means it rethrows to the caller.
1701 // try
1702 // call @foo
1703 // try ;; (new)
1704 // call @bar
1705 // delegate 1 (caller) ;; (new)
1706 // catch ;; ehpad (bb2)
1707 // ...
1708 // end_try
1709 //
1710 // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the
1711 // caller, it will take a fake BB generated by getFakeCallerBlock(), which
1712 // will be converted to a correct immediate argument later.
1713 //
1714 // In case there are multiple calls in a BB that may throw to the caller, they
1715 // can be wrapped together in one nested try-delegate scope. (In 1, this
1716 // couldn't happen, because may-throwing instruction there had an unwind
1717 // destination, i.e., it was an invoke before, and there could be only one
1718 // invoke within a BB.)
1719 //
1720 // -- Standard EH ------------------------------------------------------------
1721 //
1722 // Linearizing the control flow by placing TRY / END_TRY_TABLE markers can
1723 // create mismatches in unwind destinations for throwing instructions, such as
1724 // calls.
1725 //
1726 // We use the a nested 'try_table'~'end_try_table' instruction to fix the
1727 // unwind mismatches. try_table's catch clauses take an immediate argument
1728 // that specifics which block we should branch to.
1729 //
1730 // 1. When an instruction may throw, but the EH pad it will unwind to can be
1731 // different from the original CFG.
1732 //
1733 // Example: we have the following CFG:
1734 // bb0:
1735 // call @foo ; if it throws, unwind to bb2
1736 // bb1:
1737 // call @bar ; if it throws, unwind to bb3
1738 // bb2 (ehpad):
1739 // catch
1740 // ...
1741 // bb3 (ehpad)
1742 // catch
1743 // ...
1744 //
1745 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers
1746 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:
1747 // (BB markers are omitted)
1748 // block
1749 // try_table (catch ... 0)
1750 // block
1751 // try_table (catch ... 0)
1752 // call @foo
1753 // call @bar ;; if it throws, unwind to bb3
1754 // end_try_table
1755 // end_block ;; ehpad (bb2)
1756 // ...
1757 // end_try_table
1758 // end_block ;; ehpad (bb3)
1759 // ...
1760 //
1761 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is
1762 // supposed to end up. We solve this problem by wrapping the mismatching call
1763 // with an inner try_table~end_try_table that sends the exception to the the
1764 // 'trampoline' block, which rethrows, or 'bounces' it to the right
1765 // end_try_table:
1766 // block
1767 // try_table (catch ... 0)
1768 // block exnref ;; (new)
1769 // block
1770 // try_table (catch ... 0)
1771 // call @foo
1772 // try_table (catch_all_ref 2) ;; (new) to trampoline BB
1773 // call @bar
1774 // end_try_table ;; (new)
1775 // end_try_table
1776 // end_block ;; ehpad (bb2)
1777 // ...
1778 // end_block ;; (new) trampoline BB
1779 // throw_ref ;; (new)
1780 // end_try_table
1781 // end_block ;; ehpad (bb3)
1782 //
1783 // ---
1784 // 2. The same as 1, but in this case an instruction unwinds to a caller
1785 // function and not another EH pad.
1786 //
1787 // Example: we have the following CFG:
1788 // bb0:
1789 // call @foo ; if it throws, unwind to bb2
1790 // bb1:
1791 // call @bar ; if it throws, unwind to caller
1792 // bb2 (ehpad):
1793 // catch
1794 // ...
1795 //
1796 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers
1797 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:
1798 // block
1799 // try_table (catch ... 0)
1800 // call @foo
1801 // call @bar ;; if it throws, unwind to caller
1802 // end_try_table
1803 // end_block ;; ehpad (bb2)
1804 // ...
1805 //
1806 // Now if bar() throws, it is going to end up in bb2, when it is supposed
1807 // throw up to the caller. We solve this problem in the same way, but in this
1808 // case 'catch_all_ref's immediate argument is the number of block depths + 1,
1809 // which means it rethrows to the caller.
1810 // block exnref ;; (new)
1811 // block
1812 // try_table (catch ... 0)
1813 // call @foo
1814 // try_table (catch_all_ref 2) ;; (new) to trampoline BB
1815 // call @bar
1816 // end_try_table ;; (new)
1817 // end_try_table
1818 // end_block ;; ehpad (bb2)
1819 // ...
1820 // end_block ;; (new) caller trampoline BB
1821 // throw_ref ;; (new) throw to the caller
1822 //
1823 // Before rewriteDepthImmediates, try_table's catch clauses' argument is a
1824 // trampoline BB from which we throw_ref the exception to the right
1825 // end_try_table. In case of the caller, it will take a new caller-dedicated
1826 // trampoline BB generated by getCallerTrampolineBlock(), which throws the
1827 // exception to the caller.
1828 //
1829 // In case there are multiple calls in a BB that may throw to the caller, they
1830 // can be wrapped together in one nested try_table-end_try_table scope. (In 1,
1831 // this couldn't happen, because may-throwing instruction there had an unwind
1832 // destination, i.e., it was an invoke before, and there could be only one
1833 // invoke within a BB.)
1834
1835 SmallVector<const MachineBasicBlock *, 8> EHPadStack;
1836 // Range of intructions to be wrapped in a new nested try~delegate or
1837 // try_table~end_try_table. A range exists in a single BB and does not span
1838 // multiple BBs.
1839 using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1840 // In original CFG, <unwind destination BB, a vector of try/try_table ranges>
1841 MapVector<MachineBasicBlock *, SmallVector<TryRange, 4>>
1842 UnwindDestToTryRanges;
1843
1844 // Gather possibly throwing calls (i.e., previously invokes) whose current
1845 // unwind destination is not the same as the original CFG. (Case 1)
1846
1847 for (auto &MBB : reverse(C&: MF)) {
1848 bool SeenThrowableInstInBB = false;
1849 for (auto &MI : reverse(C&: MBB)) {
1850 if (WebAssembly::isTry(Opc: MI.getOpcode()))
1851 EHPadStack.pop_back();
1852 else if (MI.getOpcode() == WebAssembly::DELEGATE)
1853 EHPadStack.push_back(Elt: MI.getOperand(i: 0).getMBB());
1854 else if (WebAssembly::WasmUseLegacyEH &&
1855 WebAssembly::isCatch(Opc: MI.getOpcode()))
1856 EHPadStack.push_back(Elt: MI.getParent());
1857 else if (MI.getOpcode() == WebAssembly::END_TRY_TABLE)
1858 // In case of the legacy EH, 'catch' instruction is always an EH pad for
1859 // the 'try' body that precedes it. But in the standard EH, because
1860 // fixCatchUnwindMismatches runs before this, a new try_table's
1861 // trampoline BB will be separated from try_table ~ end_try_table body:
1862 //
1863 // bb0:
1864 // try_table (catch_all_ref %far_away_trampoline)
1865 // ...
1866 // end_try_table
1867 // ...
1868 // far_away_trampoline:
1869 // catch_all_ref
1870 // throw_ref
1871 //
1872 // And there can be multiple try_tables that target a single trampoline:
1873 //
1874 // bb0:
1875 // try_table (catch_all_ref %far_away_trampolinle_bb)
1876 // ...
1877 // end_try_table
1878 // ...
1879 // bb1:
1880 // try_table (catch_all_ref %far_away_trampolinle_bb)
1881 // ...
1882 // end_try_table
1883 // ...
1884 // far_away_trampoline:
1885 // catch_all_ref
1886 // throw_ref
1887 //
1888 // So we can't call WebAssembly::isCatch to add its parent EH pad to
1889 // EHPadStack. Now we add to EHPadStack at end_try_table marker, by
1890 // getting its matching try_table's destination. This works when the
1891 // destination EH pad is either a normal EH pad or a trampoline created
1892 // in fixCatchUnwindMismatches.
1893 //
1894 // Note that we don't need to distinguish this case in
1895 // fixCatchUnwindMismatches because it runs before
1896 // fixCallUnwindMismatches and there is no new try_tables and
1897 // trampolines when it runs.
1898 EHPadStack.push_back(Elt: TryToEHPad[EndToBegin[&MI]]);
1899
1900 // In this loop we only gather calls that have an EH pad to unwind. So
1901 // there will be at most 1 such call (= invoke) in a BB, so after we've
1902 // seen one, we can skip the rest of BB. Also if MBB has no EH pad
1903 // successor or MI does not throw, this is not an invoke.
1904 if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
1905 !WebAssembly::mayThrow(MI))
1906 continue;
1907 SeenThrowableInstInBB = true;
1908
1909 // If the EH pad on the stack top is where this instruction should unwind
1910 // next, we're good.
1911 MachineBasicBlock *UnwindDest = nullptr;
1912 for (auto *Succ : MBB.successors()) {
1913 // Even though semantically a BB can have multiple successors in case an
1914 // exception is not caught by a catchpad, the first unwind destination
1915 // should appear first in the successor list, based on the calculation
1916 // in findUnwindDestinations() in SelectionDAGBuilder.cpp.
1917 if (Succ->isEHPad()) {
1918 UnwindDest = Succ;
1919 break;
1920 }
1921 }
1922 if (EHPadStack.back() == UnwindDest)
1923 continue;
1924
1925 // Include EH_LABELs in the range before and after the invoke
1926 MachineInstr *RangeBegin = &MI, *RangeEnd = &MI;
1927 if (RangeBegin->getIterator() != MBB.begin() &&
1928 std::prev(x: RangeBegin->getIterator())->isEHLabel())
1929 RangeBegin = &*std::prev(x: RangeBegin->getIterator());
1930 if (std::next(x: RangeEnd->getIterator()) != MBB.end() &&
1931 std::next(x: RangeEnd->getIterator())->isEHLabel())
1932 RangeEnd = &*std::next(x: RangeEnd->getIterator());
1933
1934 // If not, record the range.
1935 UnwindDestToTryRanges[UnwindDest].push_back(
1936 Elt: TryRange(RangeBegin, RangeEnd));
1937 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << getBBName(&MBB)
1938 << "\nCall = " << MI
1939 << "\nOriginal dest = " << getBBName(UnwindDest)
1940 << " Current dest = " << getBBName(EHPadStack.back())
1941 << "\n\n");
1942 }
1943 }
1944
1945 assert(EHPadStack.empty());
1946
1947 // Gather possibly throwing calls that are supposed to unwind up to the caller
1948 // if they throw, but currently unwind to an incorrect destination. Unlike the
1949 // loop above, there can be multiple calls within a BB that unwind to the
1950 // caller, which we should group together in a range. (Case 2)
1951
1952 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
1953
1954 // Record the range.
1955 auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) {
1956 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1957 Elt: TryRange(RangeBegin, RangeEnd));
1958 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "
1959 << getBBName(RangeBegin->getParent())
1960 << "\nRange begin = " << *RangeBegin
1961 << "Range end = " << *RangeEnd
1962 << "\nOriginal dest = caller Current dest = "
1963 << getBBName(CurrentDest) << "\n\n");
1964 RangeBegin = RangeEnd = nullptr; // Reset range pointers
1965 };
1966
1967 for (auto &MBB : reverse(C&: MF)) {
1968 bool SeenThrowableInstInBB = false;
1969 for (auto &MI : reverse(C&: MBB)) {
1970 bool MayThrow = WebAssembly::mayThrow(MI);
1971
1972 // If MBB has an EH pad successor and this is the last instruction that
1973 // may throw, this instruction unwinds to the EH pad and not to the
1974 // caller.
1975 if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB)
1976 SeenThrowableInstInBB = true;
1977
1978 // We wrap up the current range when we see a marker even if we haven't
1979 // finished a BB.
1980 else if (RangeEnd && WebAssembly::isMarker(Opc: MI.getOpcode()))
1981 RecordCallerMismatchRange(EHPadStack.back());
1982
1983 // If EHPadStack is empty, that means it correctly unwinds to the caller
1984 // if it throws, so we're good. A delegate targeting FakeCallerBB also
1985 // correctly unwinds to the caller. If MI does not throw, we're good too.
1986 else if (EHPadStack.empty() || EHPadStack.back() == FakeCallerBB ||
1987 !MayThrow) {
1988 }
1989
1990 // We found an instruction that unwinds to the caller but currently has an
1991 // incorrect unwind destination. Create a new range or increment the
1992 // currently existing range.
1993 else {
1994 if (!RangeEnd)
1995 RangeBegin = RangeEnd = &MI;
1996 else
1997 RangeBegin = &MI;
1998 }
1999
2000 // Update EHPadStack.
2001 if (WebAssembly::isTry(Opc: MI.getOpcode()))
2002 EHPadStack.pop_back();
2003 else if (MI.getOpcode() == WebAssembly::DELEGATE)
2004 EHPadStack.push_back(Elt: MI.getOperand(i: 0).getMBB());
2005 else if (WebAssembly::WasmUseLegacyEH &&
2006 WebAssembly::isCatch(Opc: MI.getOpcode()))
2007 EHPadStack.push_back(Elt: MI.getParent());
2008 else if (!WebAssembly::WasmUseLegacyEH &&
2009 MI.getOpcode() == WebAssembly::END_TRY_TABLE)
2010 EHPadStack.push_back(Elt: TryToEHPad[EndToBegin[&MI]]);
2011 }
2012
2013 if (RangeEnd)
2014 RecordCallerMismatchRange(EHPadStack.back());
2015 }
2016
2017 assert(EHPadStack.empty());
2018
2019 // We don't have any unwind destination mismatches to resolve.
2020 if (UnwindDestToTryRanges.empty())
2021 return false;
2022
2023 // When end_loop is before end_try_table within the same BB in unwind
2024 // destinations, we should split the end_loop into another BB.
2025 if (!WebAssembly::WasmUseLegacyEH)
2026 for (auto &[UnwindDest, _] : UnwindDestToTryRanges) {
2027 auto It = EHPadToTry.find(Val: UnwindDest);
2028 // If UnwindDest is the fake caller block, it will not be in EHPadToTry
2029 // map
2030 if (It != EHPadToTry.end()) {
2031 auto *TryTable = It->second;
2032 auto *EndTryTable = BeginToEnd[TryTable];
2033 splitEndLoopBB(EndTryTableBB: EndTryTable->getParent());
2034 }
2035 }
2036
2037 // Now we fix the mismatches by wrapping calls with inner try-delegates.
2038 for (auto &P : UnwindDestToTryRanges) {
2039 NumCallUnwindMismatches += P.second.size();
2040 MachineBasicBlock *UnwindDest = P.first;
2041 auto &TryRanges = P.second;
2042
2043 for (auto Range : TryRanges) {
2044 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
2045 std::tie(args&: RangeBegin, args&: RangeEnd) = Range;
2046 auto *MBB = RangeBegin->getParent();
2047
2048 // If this BB has an EH pad successor, i.e., ends with an 'invoke', and if
2049 // the current range contains the invoke, now we are going to wrap the
2050 // invoke with try-delegate or try_table-end_try_table, making the
2051 // 'delegate' or 'end_try_table' BB the new successor instead, so remove
2052 // the EH pad succesor here. The BB may not have an EH pad successor if
2053 // calls in this BB throw to the caller.
2054 if (UnwindDest != getFakeCallerBlock(MF)) {
2055 MachineBasicBlock *EHPad = nullptr;
2056 for (auto *Succ : MBB->successors()) {
2057 if (Succ->isEHPad()) {
2058 EHPad = Succ;
2059 break;
2060 }
2061 }
2062 if (EHPad)
2063 MBB->removeSuccessor(Succ: EHPad);
2064 }
2065
2066 if (WebAssembly::WasmUseLegacyEH)
2067 addNestedTryDelegate(RangeBegin, RangeEnd, UnwindDest);
2068 else
2069 addNestedTryTable(RangeBegin, RangeEnd, UnwindDest);
2070 }
2071 }
2072
2073 return true;
2074}
2075
2076bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {
2077 // This function is used for both the legacy EH and the standard (exnref) EH,
2078 // and the reason we have unwind mismatches is the same for the both of them,
2079 // but the code examples in the comments are going to be different. To make
2080 // the description less confusing, we write the basically same comments twice,
2081 // once for the legacy EH and the standard EH.
2082 //
2083 // -- Legacy EH --------------------------------------------------------------
2084 //
2085 // There is another kind of unwind destination mismatches besides call unwind
2086 // mismatches, which we will call "catch unwind mismatches". See this example
2087 // after the marker placement:
2088 // try
2089 // try
2090 // call @foo
2091 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
2092 // ...
2093 // end_try
2094 // catch_all ;; ehpad B
2095 // ...
2096 // end_try
2097 //
2098 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
2099 // throws a foreign exception that is not caught by ehpad A, and its next
2100 // destination should be the caller. But after control flow linearization,
2101 // another EH pad can be placed in between (e.g. ehpad B here), making the
2102 // next unwind destination incorrect. In this case, the foreign exception will
2103 // instead go to ehpad B and will be caught there instead. In this example the
2104 // correct next unwind destination is the caller, but it can be another outer
2105 // catch in other cases.
2106 //
2107 // There is no specific 'call' or 'throw' instruction to wrap with a
2108 // try-delegate, so we wrap the whole try-catch-end with a try-delegate and
2109 // make it rethrow to the right destination, which is the caller in the
2110 // example below:
2111 // try
2112 // try ;; (new)
2113 // try
2114 // call @foo
2115 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
2116 // ...
2117 // end_try
2118 // delegate 1 (caller) ;; (new)
2119 // catch_all ;; ehpad B
2120 // ...
2121 // end_try
2122 //
2123 // The right destination may be another EH pad or the caller. (The example
2124 // here shows the case it is the caller.)
2125 //
2126 // -- Standard EH ------------------------------------------------------------
2127 //
2128 // There is another kind of unwind destination mismatches besides call unwind
2129 // mismatches, which we will call "catch unwind mismatches". See this example
2130 // after the marker placement:
2131 // block
2132 // try_table (catch_all_ref 0)
2133 // block
2134 // try_table (catch ... 0)
2135 // call @foo
2136 // end_try_table
2137 // end_block ;; ehpad A (next unwind dest: caller)
2138 // ...
2139 // end_try_table
2140 // end_block ;; ehpad B
2141 // ...
2142 //
2143 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
2144 // throws a foreign exception that is not caught by ehpad A, and its next
2145 // destination should be the caller. But after control flow linearization,
2146 // another EH pad can be placed in between (e.g. ehpad B here), making the
2147 // next unwind destination incorrect. In this case, the foreign exception will
2148 // instead go to ehpad B and will be caught there instead. In this example the
2149 // correct next unwind destination is the caller, but it can be another outer
2150 // catch in other cases.
2151 //
2152 // There is no specific 'call' or 'throw' instruction to wrap with an inner
2153 // try_table-end_try_table, so we wrap the whole try_table-end_try_table with
2154 // an inner try_table-end_try_table that sends the exception to a trampoline
2155 // BB. We rethrow the sent exception using a throw_ref to the right
2156 // destination, which is the caller in the example below:
2157 // block exnref
2158 // block
2159 // try_table (catch_all_ref 0)
2160 // try_table (catch_all_ref 2) ;; (new) to trampoline
2161 // block
2162 // try_table (catch ... 0)
2163 // call @foo
2164 // end_try_table
2165 // end_block ;; ehpad A (next unwind dest: caller)
2166 // end_try_table ;; (new)
2167 // ...
2168 // end_try_table
2169 // end_block ;; ehpad B
2170 // ...
2171 // end_block ;; (new) caller trampoline BB
2172 // throw_ref ;; (new) throw to the caller
2173 //
2174 // The right destination may be another EH pad or the caller. (The example
2175 // here shows the case it is the caller.)
2176
2177 // Returns whether the next unwind destination exists when an exception is not
2178 // caught by the given EHPad. It is guaranteed that the next successor of the
2179 // given EHPad's predecessor is the next unwind destination, due to the order
2180 // we add successors in findUnwindDestinations in SelectionDAGBuilder.
2181 auto HasUnwindDest = [&](const MachineBasicBlock *EHPad) {
2182 assert(!EHPad->pred_empty() && "EHPad has no predecessors");
2183 auto *InvokeBB = *EHPad->pred_begin();
2184 for (auto I = InvokeBB->succ_begin(), E = InvokeBB->succ_end(); I != E; ++I)
2185 if (*I == EHPad)
2186 return std::next(x: I) != E;
2187 llvm_unreachable("EHPad not found in its predecessor's successors");
2188 };
2189
2190 // Returns the next unwind destination when an exception is not caught by the
2191 // given EHPad. Returns nullptr when it doesn't exist.
2192 auto GetUnwindDest = [&](const MachineBasicBlock *EHPad) {
2193 assert(!EHPad->pred_empty() && "EHPad has no predecessors");
2194 auto *InvokeBB = *EHPad->pred_begin();
2195 for (auto I = InvokeBB->succ_begin(), E = InvokeBB->succ_end(); I != E;
2196 ++I) {
2197 if (*I == EHPad) {
2198 auto *Next = std::next(x: I);
2199 return Next == E ? nullptr : *Next;
2200 }
2201 }
2202 llvm_unreachable("EHPad not found in its predecessor's successors");
2203 };
2204
2205 SmallVector<const MachineBasicBlock *, 8> EHPadStack;
2206 // For EH pads that have catch unwind mismatches, a map of <EH pad, its
2207 // correct unwind destination>.
2208 MapVector<MachineBasicBlock *, MachineBasicBlock *> EHPadToUnwindDest;
2209
2210 for (auto &MBB : reverse(C&: MF)) {
2211 for (auto &MI : reverse(C&: MBB)) {
2212 if (WebAssembly::isTry(Opc: MI.getOpcode())) {
2213 EHPadStack.pop_back();
2214 } else if (MI.getOpcode() == WebAssembly::DELEGATE) {
2215 EHPadStack.push_back(Elt: &MBB);
2216 } else if (WebAssembly::isCatch(Opc: MI.getOpcode())) {
2217 auto *EHPad = &MBB;
2218
2219 // catch_all always catches an exception, so we don't need to do
2220 // anything
2221 if (WebAssembly::isCatchAll(Opc: MI.getOpcode())) {
2222 }
2223
2224 // This can happen when the unwind dest was removed during the
2225 // optimization, e.g. because it was unreachable.
2226 else if (EHPadStack.empty() && HasUnwindDest(EHPad)) {
2227 LLVM_DEBUG(dbgs() << "EHPad (" << getBBName(EHPad)
2228 << "'s unwind destination does not exist anymore"
2229 << "\n\n");
2230 }
2231
2232 // The EHPad's next unwind destination is the caller, but we incorrectly
2233 // unwind to another EH pad.
2234 else if (!EHPadStack.empty() && EHPadStack.back() != FakeCallerBB &&
2235 !HasUnwindDest(EHPad)) {
2236 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
2237 LLVM_DEBUG(dbgs()
2238 << "- Catch unwind mismatch:\nEHPad = " << getBBName(EHPad)
2239 << " Original dest = caller Current dest = "
2240 << getBBName(EHPadStack.back()) << "\n\n");
2241 }
2242
2243 // The EHPad's next unwind destination is an EH pad, whereas we
2244 // incorrectly unwind to another EH pad.
2245 else if (!EHPadStack.empty() && HasUnwindDest(EHPad)) {
2246 auto *UnwindDest = GetUnwindDest(EHPad);
2247 if (EHPadStack.back() != UnwindDest) {
2248 EHPadToUnwindDest[EHPad] = UnwindDest;
2249 LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "
2250 << getBBName(EHPad) << " Original dest = "
2251 << getBBName(UnwindDest) << " Current dest = "
2252 << getBBName(EHPadStack.back()) << "\n\n");
2253 }
2254 }
2255
2256 EHPadStack.push_back(Elt: EHPad);
2257 }
2258 }
2259 }
2260
2261 assert(EHPadStack.empty());
2262 if (EHPadToUnwindDest.empty())
2263 return false;
2264
2265 // When end_loop is before end_try_table within the same BB in unwind
2266 // destinations, we should split the end_loop into another BB.
2267 for (auto &[_, UnwindDest] : EHPadToUnwindDest) {
2268 auto It = EHPadToTry.find(Val: UnwindDest);
2269 // If UnwindDest is the fake caller block, it will not be in EHPadToTry map
2270 if (It != EHPadToTry.end()) {
2271 auto *TryTable = It->second;
2272 auto *EndTryTable = BeginToEnd[TryTable];
2273 splitEndLoopBB(EndTryTableBB: EndTryTable->getParent());
2274 }
2275 }
2276
2277 NumCatchUnwindMismatches += EHPadToUnwindDest.size();
2278 SmallPtrSet<MachineBasicBlock *, 4> NewEndTryBBs;
2279
2280 for (auto &[EHPad, UnwindDest] : EHPadToUnwindDest) {
2281 MachineInstr *Try = EHPadToTry[EHPad];
2282 MachineInstr *EndTry = BeginToEnd[Try];
2283 if (WebAssembly::WasmUseLegacyEH) {
2284 addNestedTryDelegate(RangeBegin: Try, RangeEnd: EndTry, UnwindDest);
2285 NewEndTryBBs.insert(Ptr: EndTry->getParent());
2286 } else {
2287 addNestedTryTable(RangeBegin: Try, RangeEnd: EndTry, UnwindDest);
2288 }
2289 }
2290
2291 if (!WebAssembly::WasmUseLegacyEH)
2292 return true;
2293
2294 // Adding a try-delegate wrapping an existing try-catch-end can make existing
2295 // branch destination BBs invalid. For example,
2296 //
2297 // - Before:
2298 // bb0:
2299 // block
2300 // br bb3
2301 // bb1:
2302 // try
2303 // ...
2304 // bb2: (ehpad)
2305 // catch
2306 // bb3:
2307 // end_try
2308 // end_block ;; 'br bb3' targets here
2309 //
2310 // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap
2311 // this with a try-delegate. Then this becomes:
2312 //
2313 // - After:
2314 // bb0:
2315 // block
2316 // br bb3 ;; invalid destination!
2317 // bb1:
2318 // try ;; (new instruction)
2319 // try
2320 // ...
2321 // bb2: (ehpad)
2322 // catch
2323 // bb3:
2324 // end_try ;; 'br bb3' still incorrectly targets here!
2325 // delegate_bb: ;; (new BB)
2326 // delegate ;; (new instruction)
2327 // split_bb: ;; (new BB)
2328 // end_block
2329 //
2330 // Now 'br bb3' incorrectly branches to an inner scope.
2331 //
2332 // As we can see in this case, when branches target a BB that has both
2333 // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we
2334 // have to remap existing branch destinations so that they target not the
2335 // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's
2336 // in between, so we try to find the next BB with 'end_block' instruction. In
2337 // this example, the 'br bb3' instruction should be remapped to 'br split_bb'.
2338 for (auto &MBB : MF) {
2339 for (auto &MI : MBB) {
2340 if (MI.isTerminator()) {
2341 for (auto &MO : MI.operands()) {
2342 if (MO.isMBB() && NewEndTryBBs.count(Ptr: MO.getMBB())) {
2343 auto *BrDest = MO.getMBB();
2344 bool FoundEndBlock = false;
2345 for (; std::next(x: BrDest->getIterator()) != MF.end();
2346 BrDest = BrDest->getNextNode()) {
2347 for (const auto &MI : *BrDest) {
2348 if (MI.getOpcode() == WebAssembly::END_BLOCK) {
2349 FoundEndBlock = true;
2350 break;
2351 }
2352 }
2353 if (FoundEndBlock)
2354 break;
2355 }
2356 assert(FoundEndBlock);
2357 MO.setMBB(BrDest);
2358 }
2359 }
2360 }
2361 }
2362 }
2363
2364 return true;
2365}
2366
2367void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {
2368 // Renumber BBs and recalculate ScopeTop info because new BBs might have been
2369 // created and inserted during fixing unwind mismatches.
2370 MF.RenumberBlocks();
2371 ScopeTops.clear();
2372 ScopeTops.resize(N: MF.getNumBlockIDs());
2373 for (auto &MBB : reverse(C&: MF)) {
2374 for (auto &MI : reverse(C&: MBB)) {
2375 if (ScopeTops[MBB.getNumber()])
2376 break;
2377 switch (MI.getOpcode()) {
2378 case WebAssembly::END_BLOCK:
2379 case WebAssembly::END_LOOP:
2380 case WebAssembly::END_TRY:
2381 case WebAssembly::END_TRY_TABLE:
2382 case WebAssembly::DELEGATE:
2383 updateScopeTops(Begin: EndToBegin[&MI]->getParent(), End: &MBB);
2384 break;
2385 case WebAssembly::CATCH_LEGACY:
2386 case WebAssembly::CATCH_ALL_LEGACY:
2387 updateScopeTops(Begin: EHPadToTry[&MBB]->getParent(), End: &MBB);
2388 break;
2389 }
2390 }
2391 }
2392}
2393
2394/// In normal assembly languages, when the end of a function is unreachable,
2395/// because the function ends in an infinite loop or a noreturn call or similar,
2396/// it isn't necessary to worry about the function return type at the end of
2397/// the function, because it's never reached. However, in WebAssembly, blocks
2398/// that end at the function end need to have a return type signature that
2399/// matches the function signature, even though it's unreachable. This function
2400/// checks for such cases and fixes up the signatures.
2401void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
2402 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
2403
2404 if (MFI.getResults().empty())
2405 return;
2406
2407 // MCInstLower will add the proper types to multivalue signatures based on the
2408 // function return type
2409 WebAssembly::BlockType RetType =
2410 MFI.getResults().size() > 1
2411 ? WebAssembly::BlockType::Multivalue
2412 : WebAssembly::BlockType(
2413 WebAssembly::toValType(Type: MFI.getResults().front()));
2414
2415 SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist;
2416 Worklist.push_back(Elt: MF.rbegin()->rbegin());
2417
2418 auto Process = [&](MachineBasicBlock::reverse_iterator It) {
2419 auto *MBB = It->getParent();
2420 while (It != MBB->rend()) {
2421 MachineInstr &MI = *It++;
2422 if (MI.isPosition() || MI.isDebugInstr())
2423 continue;
2424 switch (MI.getOpcode()) {
2425 case WebAssembly::END_TRY: {
2426 // If a 'try''s return type is fixed, both its try body and catch body
2427 // should satisfy the return type, so we need to search 'end'
2428 // instructions before its corresponding 'catch' too.
2429 auto *EHPad = TryToEHPad.lookup(Val: EndToBegin[&MI]);
2430 assert(EHPad);
2431 auto NextIt =
2432 std::next(x: WebAssembly::findCatch(EHPad)->getReverseIterator());
2433 if (NextIt != EHPad->rend())
2434 Worklist.push_back(Elt: NextIt);
2435 [[fallthrough]];
2436 }
2437 case WebAssembly::END_BLOCK:
2438 case WebAssembly::END_LOOP:
2439 case WebAssembly::END_TRY_TABLE:
2440 case WebAssembly::DELEGATE:
2441 EndToBegin[&MI]->getOperand(i: 0).setImm(int32_t(RetType));
2442 continue;
2443 default:
2444 // Something other than an `end`. We're done for this BB.
2445 return;
2446 }
2447 }
2448 // We've reached the beginning of a BB. Continue the search in the previous
2449 // BB.
2450 Worklist.push_back(Elt: MBB->getPrevNode()->rbegin());
2451 };
2452
2453 while (!Worklist.empty())
2454 Process(Worklist.pop_back_val());
2455}
2456
2457// WebAssembly functions end with an end instruction, as if the function body
2458// were a block.
2459static void appendEndToFunction(MachineFunction &MF,
2460 const WebAssemblyInstrInfo &TII) {
2461 BuildMI(BB&: MF.back(), I: MF.back().end(),
2462 MIMD: MF.back().findPrevDebugLoc(MBBI: MF.back().end()),
2463 MCID: TII.get(Opcode: WebAssembly::END_FUNCTION));
2464}
2465
2466// We added block~end_block and try_table~end_try_table markers in
2467// placeTryTableMarker. But When catch clause's destination has a return type,
2468// as in the case of catch with a concrete tag, catch_ref, and catch_all_ref.
2469// For example:
2470// block exnref
2471// try_table (catch_all_ref 0)
2472// ...
2473// end_try_table
2474// end_block
2475// ... use exnref ...
2476//
2477// This code is not valid because the block's body type is not exnref. So we add
2478// an unreachable after the 'end_try_table' to make the code valid here:
2479// block exnref
2480// try_table (catch_all_ref 0)
2481// ...
2482// end_try_table
2483// unreachable (new)
2484// end_block
2485//
2486// Because 'unreachable' is a terminator we also need to split the BB.
2487static void addUnreachableAfterTryTables(MachineFunction &MF,
2488 const WebAssemblyInstrInfo &TII) {
2489 std::vector<MachineInstr *> EndTryTables;
2490 for (auto &MBB : MF)
2491 for (auto &MI : MBB)
2492 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE)
2493 EndTryTables.push_back(x: &MI);
2494
2495 for (auto *EndTryTable : EndTryTables) {
2496 auto *MBB = EndTryTable->getParent();
2497 auto *NewEndTryTableBB = MF.CreateMachineBasicBlock();
2498 MF.insert(MBBI: MBB->getIterator(), MBB: NewEndTryTableBB);
2499 auto SplitPos = std::next(x: EndTryTable->getIterator());
2500 NewEndTryTableBB->splice(Where: NewEndTryTableBB->end(), Other: MBB, From: MBB->begin(),
2501 To: SplitPos);
2502 NewEndTryTableBB->addSuccessor(Succ: MBB);
2503 BuildMI(BB: NewEndTryTableBB, MIMD: EndTryTable->getDebugLoc(),
2504 MCID: TII.get(Opcode: WebAssembly::UNREACHABLE));
2505 }
2506}
2507
2508/// Insert BLOCK/LOOP/TRY/TRY_TABLE markers at appropriate places.
2509void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
2510 // We allocate one more than the number of blocks in the function to
2511 // accommodate for the possible fake block we may insert at the end.
2512 ScopeTops.resize(N: MF.getNumBlockIDs() + 1);
2513 // Place the LOOP for MBB if MBB is the header of a loop.
2514 for (auto &MBB : MF)
2515 placeLoopMarker(MBB);
2516
2517 const MCAsmInfo &MCAI = MF.getTarget().getMCAsmInfo();
2518 for (auto &MBB : MF) {
2519 if (MBB.isEHPad()) {
2520 // Place the TRY/TRY_TABLE for MBB if MBB is the EH pad of an exception.
2521 if (MCAI.getExceptionHandlingType() == ExceptionHandling::Wasm &&
2522 MF.getFunction().hasPersonalityFn()) {
2523 if (WebAssembly::WasmUseLegacyEH)
2524 placeTryMarker(MBB);
2525 else
2526 placeTryTableMarker(MBB);
2527 }
2528 } else {
2529 // Place the BLOCK for MBB if MBB is branched to from above.
2530 placeBlockMarker(MBB);
2531 }
2532 }
2533
2534 if (MCAI.getExceptionHandlingType() == ExceptionHandling::Wasm &&
2535 MF.getFunction().hasPersonalityFn()) {
2536 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
2537 // Add an 'unreachable' after 'end_try_table's.
2538 addUnreachableAfterTryTables(MF, TII);
2539 // Fix mismatches in unwind destinations induced by linearizing the code.
2540 // Run fixCatchUnwindMismatches() first so that fixCallUnwindMismatches()
2541 // will see and correct any new call/rethrow unwind mismatches introduced by
2542 // fixCatchUnwindMismatches().
2543 fixCatchUnwindMismatches(MF);
2544 fixCallUnwindMismatches(MF);
2545 // addUnreachableAfterTryTables and fixUnwindMismatches create new BBs, so
2546 // we need to recalculate ScopeTops.
2547 recalculateScopeTops(MF);
2548 }
2549}
2550
2551unsigned WebAssemblyCFGStackify::getBranchDepth(
2552 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
2553 unsigned Depth = 0;
2554 for (auto X : reverse(C: Stack)) {
2555 if (X.first == MBB)
2556 break;
2557 ++Depth;
2558 }
2559 assert(Depth < Stack.size() && "Branch destination should be in scope");
2560 return Depth;
2561}
2562
2563unsigned WebAssemblyCFGStackify::getDelegateDepth(
2564 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
2565 if (MBB == FakeCallerBB)
2566 return Stack.size();
2567 // Delegate's destination is either a catch or a another delegate BB. When the
2568 // destination is another delegate, we can compute the argument in the same
2569 // way as branches, because the target delegate BB only contains the single
2570 // delegate instruction.
2571 if (!MBB->isEHPad()) // Target is a delegate BB
2572 return getBranchDepth(Stack, MBB);
2573
2574 // When the delegate's destination is a catch BB, we need to use its
2575 // corresponding try's end_try BB because Stack contains each marker's end BB.
2576 // Also we need to check if the end marker instruction matches, because a
2577 // single BB can contain multiple end markers, like this:
2578 // bb:
2579 // END_BLOCK
2580 // END_TRY
2581 // END_BLOCK
2582 // END_TRY
2583 // ...
2584 //
2585 // In case of branches getting the immediate that targets any of these is
2586 // fine, but delegate has to exactly target the correct try.
2587 unsigned Depth = 0;
2588 const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];
2589 for (auto X : reverse(C: Stack)) {
2590 if (X.first == EndTry->getParent() && X.second == EndTry)
2591 break;
2592 ++Depth;
2593 }
2594 assert(Depth < Stack.size() && "Delegate destination should be in scope");
2595 return Depth;
2596}
2597
2598unsigned WebAssemblyCFGStackify::getRethrowDepth(
2599 const SmallVectorImpl<EndMarkerInfo> &Stack,
2600 const MachineBasicBlock *EHPadToRethrow) {
2601 unsigned Depth = 0;
2602 for (auto X : reverse(C: Stack)) {
2603 const MachineInstr *End = X.second;
2604 if (End->getOpcode() == WebAssembly::END_TRY) {
2605 auto *EHPad = TryToEHPad[EndToBegin[End]];
2606 if (EHPadToRethrow == EHPad)
2607 break;
2608 }
2609 ++Depth;
2610 }
2611 assert(Depth < Stack.size() && "Rethrow destination should be in scope");
2612 return Depth;
2613}
2614
2615void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
2616 // Now rewrite references to basic blocks to be depth immediates.
2617 SmallVector<EndMarkerInfo, 8> Stack;
2618
2619 auto RewriteOperands = [&](MachineInstr &MI) {
2620 // Rewrite MBB operands to be depth immediates.
2621 SmallVector<MachineOperand, 4> Ops(MI.operands());
2622 while (MI.getNumOperands() > 0)
2623 MI.removeOperand(OpNo: MI.getNumOperands() - 1);
2624 for (auto MO : Ops) {
2625 if (MO.isMBB()) {
2626 if (MI.getOpcode() == WebAssembly::DELEGATE)
2627 MO = MachineOperand::CreateImm(Val: getDelegateDepth(Stack, MBB: MO.getMBB()));
2628 else if (MI.getOpcode() == WebAssembly::RETHROW)
2629 MO = MachineOperand::CreateImm(Val: getRethrowDepth(Stack, EHPadToRethrow: MO.getMBB()));
2630 else
2631 MO = MachineOperand::CreateImm(Val: getBranchDepth(Stack, MBB: MO.getMBB()));
2632 }
2633 MI.addOperand(MF, Op: MO);
2634 }
2635 };
2636
2637 for (auto &MBB : reverse(C&: MF)) {
2638 for (MachineInstr &MI : llvm::reverse(C&: MBB)) {
2639 switch (MI.getOpcode()) {
2640 case WebAssembly::BLOCK:
2641 case WebAssembly::TRY:
2642 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2643 MBB.getNumber() &&
2644 "Block/try/try_table marker should be balanced");
2645 Stack.pop_back();
2646 break;
2647
2648 case WebAssembly::TRY_TABLE:
2649 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2650 MBB.getNumber() &&
2651 "Block/try/try_table marker should be balanced");
2652 Stack.pop_back();
2653 RewriteOperands(MI);
2654 break;
2655
2656 case WebAssembly::LOOP:
2657 assert(Stack.back().first == &MBB && "Loop top should be balanced");
2658 Stack.pop_back();
2659 break;
2660
2661 case WebAssembly::END_BLOCK:
2662 case WebAssembly::END_TRY:
2663 case WebAssembly::END_TRY_TABLE:
2664 Stack.push_back(Elt: std::make_pair(x: &MBB, y: &MI));
2665 break;
2666
2667 case WebAssembly::END_LOOP:
2668 Stack.push_back(Elt: std::make_pair(x: EndToBegin[&MI]->getParent(), y: &MI));
2669 break;
2670
2671 case WebAssembly::DELEGATE:
2672 RewriteOperands(MI);
2673 Stack.push_back(Elt: std::make_pair(x: &MBB, y: &MI));
2674 break;
2675
2676 default:
2677 if (MI.isTerminator())
2678 RewriteOperands(MI);
2679 break;
2680 }
2681 }
2682 }
2683 assert(Stack.empty() && "Control flow should be balanced");
2684}
2685
2686void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) {
2687 if (FakeCallerBB)
2688 MF.deleteMachineBasicBlock(MBB: FakeCallerBB);
2689 AppendixBB = FakeCallerBB = CallerTrampolineBB = nullptr;
2690}
2691
2692void WebAssemblyCFGStackify::releaseMemory() {
2693 ScopeTops.clear();
2694 BeginToEnd.clear();
2695 EndToBegin.clear();
2696 TryToEHPad.clear();
2697 EHPadToTry.clear();
2698 UnwindDestToTrampoline.clear();
2699}
2700
2701bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
2702 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
2703 "********** Function: "
2704 << MF.getName() << '\n');
2705 const MCAsmInfo &MCAI = MF.getTarget().getMCAsmInfo();
2706 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
2707
2708 releaseMemory();
2709
2710 // Liveness is not tracked for VALUE_STACK physreg.
2711 MF.getRegInfo().invalidateLiveness();
2712
2713 // Place the BLOCK/LOOP/TRY/TRY_TABLE markers to indicate the beginnings of
2714 // scopes.
2715 placeMarkers(MF);
2716
2717 // Remove unnecessary instructions possibly introduced by try/end_trys.
2718 if (MCAI.getExceptionHandlingType() == ExceptionHandling::Wasm &&
2719 MF.getFunction().hasPersonalityFn() && WebAssembly::WasmUseLegacyEH)
2720 removeUnnecessaryInstrs(MF);
2721
2722 // Convert MBB operands in terminators to relative depth immediates.
2723 rewriteDepthImmediates(MF);
2724
2725 // Fix up block/loop/try/try_table signatures at the end of the function to
2726 // conform to WebAssembly's rules.
2727 fixEndsAtEndOfFunction(MF);
2728
2729 // Add an end instruction at the end of the function body.
2730 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
2731 appendEndToFunction(MF, TII);
2732
2733 cleanupFunctionData(MF);
2734
2735 MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
2736 return true;
2737}
2738