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 "MCTargetDesc/WebAssemblyMCTargetDesc.h"
25#include "Utils/WebAssemblyTypeUtilities.h"
26#include "WebAssembly.h"
27#include "WebAssemblyExceptionInfo.h"
28#include "WebAssemblyMachineFunctionInfo.h"
29#include "WebAssemblySortRegion.h"
30#include "WebAssemblySubtarget.h"
31#include "WebAssemblyUtilities.h"
32#include "llvm/ADT/Statistic.h"
33#include "llvm/BinaryFormat/Wasm.h"
34#include "llvm/CodeGen/MachineDominators.h"
35#include "llvm/CodeGen/MachineInstrBuilder.h"
36#include "llvm/CodeGen/MachineLoopInfo.h"
37#include "llvm/CodeGen/WasmEHFuncInfo.h"
38#include "llvm/MC/MCAsmInfo.h"
39#include "llvm/Target/TargetMachine.h"
40using namespace llvm;
41using WebAssembly::SortRegionInfo;
42
43#define DEBUG_TYPE "wasm-cfg-stackify"
44
45STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found");
46STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found");
47
48namespace {
49class WebAssemblyCFGStackify final : public MachineFunctionPass {
50 MachineDominatorTree *MDT;
51
52 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
53
54 void getAnalysisUsage(AnalysisUsage &AU) const override {
55 AU.addRequired<MachineDominatorTreeWrapperPass>();
56 AU.addRequired<MachineLoopInfoWrapperPass>();
57 AU.addRequired<WebAssemblyExceptionInfo>();
58 MachineFunctionPass::getAnalysisUsage(AU);
59 }
60
61 bool runOnMachineFunction(MachineFunction &MF) override;
62
63 // For each block whose label represents the end of a scope, record the 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: nullptr);
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
1580bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {
1581 // This function is used for both the legacy EH and the standard (exnref) EH,
1582 // and the reason we have unwind mismatches is the same for the both of them,
1583 // but the code examples in the comments are going to be different. To make
1584 // the description less confusing, we write the basically same comments twice,
1585 // once for the legacy EH and the standard EH.
1586 //
1587 // -- Legacy EH --------------------------------------------------------------
1588 //
1589 // Linearizing the control flow by placing TRY / END_TRY markers can create
1590 // mismatches in unwind destinations for throwing instructions, such as calls.
1591 //
1592 // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate'
1593 // instruction delegates an exception to an outer 'catch'. It can target not
1594 // only 'catch' but all block-like structures including another 'delegate',
1595 // but with slightly different semantics than branches. When it targets a
1596 // 'catch', it will delegate the exception to that catch. It is being
1597 // discussed how to define the semantics when 'delegate''s target is a non-try
1598 // block: it will either be a validation failure or it will target the next
1599 // outer try-catch. But anyway our LLVM backend currently does not generate
1600 // such code. The example below illustrates where the 'delegate' instruction
1601 // in the middle will delegate the exception to, depending on the value of N.
1602 // try
1603 // try
1604 // block
1605 // try
1606 // try
1607 // call @foo
1608 // delegate N ;; Where will this delegate to?
1609 // catch ;; N == 0
1610 // end
1611 // end ;; N == 1 (invalid; will not be generated)
1612 // delegate ;; N == 2
1613 // catch ;; N == 3
1614 // end
1615 // ;; N == 4 (to caller)
1616 //
1617 // 1. When an instruction may throw, but the EH pad it will unwind to can be
1618 // different from the original CFG.
1619 //
1620 // Example: we have the following CFG:
1621 // bb0:
1622 // call @foo ; if it throws, unwind to bb2
1623 // bb1:
1624 // call @bar ; if it throws, unwind to bb3
1625 // bb2 (ehpad):
1626 // catch
1627 // ...
1628 // bb3 (ehpad)
1629 // catch
1630 // ...
1631 //
1632 // And the CFG is sorted in this order. Then after placing TRY markers, it
1633 // will look like: (BB markers are omitted)
1634 // try
1635 // try
1636 // call @foo
1637 // call @bar ;; if it throws, unwind to bb3
1638 // catch ;; ehpad (bb2)
1639 // ...
1640 // end_try
1641 // catch ;; ehpad (bb3)
1642 // ...
1643 // end_try
1644 //
1645 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is
1646 // supposed to end up. We solve this problem by wrapping the mismatching call
1647 // with an inner try-delegate that rethrows the exception to the right
1648 // 'catch'.
1649 //
1650 // try
1651 // try
1652 // call @foo
1653 // try ;; (new)
1654 // call @bar
1655 // delegate 1 (bb3) ;; (new)
1656 // catch ;; ehpad (bb2)
1657 // ...
1658 // end_try
1659 // catch ;; ehpad (bb3)
1660 // ...
1661 // end_try
1662 //
1663 // ---
1664 // 2. The same as 1, but in this case an instruction unwinds to a caller
1665 // function and not another EH pad.
1666 //
1667 // Example: we have the following CFG:
1668 // bb0:
1669 // call @foo ; if it throws, unwind to bb2
1670 // bb1:
1671 // call @bar ; if it throws, unwind to caller
1672 // bb2 (ehpad):
1673 // catch
1674 // ...
1675 //
1676 // And the CFG is sorted in this order. Then after placing TRY markers, it
1677 // will look like:
1678 // try
1679 // call @foo
1680 // call @bar ;; if it throws, unwind to caller
1681 // catch ;; ehpad (bb2)
1682 // ...
1683 // end_try
1684 //
1685 // Now if bar() throws, it is going to end up in bb2, when it is supposed
1686 // throw up to the caller. We solve this problem in the same way, but in this
1687 // case 'delegate's immediate argument is the number of block depths + 1,
1688 // which means it rethrows to the caller.
1689 // try
1690 // call @foo
1691 // try ;; (new)
1692 // call @bar
1693 // delegate 1 (caller) ;; (new)
1694 // catch ;; ehpad (bb2)
1695 // ...
1696 // end_try
1697 //
1698 // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the
1699 // caller, it will take a fake BB generated by getFakeCallerBlock(), which
1700 // will be converted to a correct immediate argument later.
1701 //
1702 // In case there are multiple calls in a BB that may throw to the caller, they
1703 // can be wrapped together in one nested try-delegate scope. (In 1, this
1704 // couldn't happen, because may-throwing instruction there had an unwind
1705 // destination, i.e., it was an invoke before, and there could be only one
1706 // invoke within a BB.)
1707 //
1708 // -- Standard EH ------------------------------------------------------------
1709 //
1710 // Linearizing the control flow by placing TRY / END_TRY_TABLE markers can
1711 // create mismatches in unwind destinations for throwing instructions, such as
1712 // calls.
1713 //
1714 // We use the a nested 'try_table'~'end_try_table' instruction to fix the
1715 // unwind mismatches. try_table's catch clauses take an immediate argument
1716 // that specifics which block we should branch to.
1717 //
1718 // 1. When an instruction may throw, but the EH pad it will unwind to can be
1719 // different from the original CFG.
1720 //
1721 // Example: we have the following CFG:
1722 // bb0:
1723 // call @foo ; if it throws, unwind to bb2
1724 // bb1:
1725 // call @bar ; if it throws, unwind to bb3
1726 // bb2 (ehpad):
1727 // catch
1728 // ...
1729 // bb3 (ehpad)
1730 // catch
1731 // ...
1732 //
1733 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers
1734 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:
1735 // (BB markers are omitted)
1736 // block
1737 // try_table (catch ... 0)
1738 // block
1739 // try_table (catch ... 0)
1740 // call @foo
1741 // call @bar ;; if it throws, unwind to bb3
1742 // end_try_table
1743 // end_block ;; ehpad (bb2)
1744 // ...
1745 // end_try_table
1746 // end_block ;; ehpad (bb3)
1747 // ...
1748 //
1749 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is
1750 // supposed to end up. We solve this problem by wrapping the mismatching call
1751 // with an inner try_table~end_try_table that sends the exception to the the
1752 // 'trampoline' block, which rethrows, or 'bounces' it to the right
1753 // end_try_table:
1754 // block
1755 // try_table (catch ... 0)
1756 // block exnref ;; (new)
1757 // block
1758 // try_table (catch ... 0)
1759 // call @foo
1760 // try_table (catch_all_ref 2) ;; (new) to trampoline BB
1761 // call @bar
1762 // end_try_table ;; (new)
1763 // end_try_table
1764 // end_block ;; ehpad (bb2)
1765 // ...
1766 // end_block ;; (new) trampoline BB
1767 // throw_ref ;; (new)
1768 // end_try_table
1769 // end_block ;; ehpad (bb3)
1770 //
1771 // ---
1772 // 2. The same as 1, but in this case an instruction unwinds to a caller
1773 // function and not another EH pad.
1774 //
1775 // Example: we have the following CFG:
1776 // bb0:
1777 // call @foo ; if it throws, unwind to bb2
1778 // bb1:
1779 // call @bar ; if it throws, unwind to caller
1780 // bb2 (ehpad):
1781 // catch
1782 // ...
1783 //
1784 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers
1785 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:
1786 // block
1787 // try_table (catch ... 0)
1788 // call @foo
1789 // call @bar ;; if it throws, unwind to caller
1790 // end_try_table
1791 // end_block ;; ehpad (bb2)
1792 // ...
1793 //
1794 // Now if bar() throws, it is going to end up in bb2, when it is supposed
1795 // throw up to the caller. We solve this problem in the same way, but in this
1796 // case 'delegate's immediate argument is the number of block depths + 1,
1797 // which means it rethrows to the caller.
1798 // block exnref ;; (new)
1799 // block
1800 // try_table (catch ... 0)
1801 // call @foo
1802 // try_table (catch_all_ref 2) ;; (new) to trampoline BB
1803 // call @bar
1804 // end_try_table ;; (new)
1805 // end_try_table
1806 // end_block ;; ehpad (bb2)
1807 // ...
1808 // end_block ;; (new) caller trampoline BB
1809 // throw_ref ;; (new) throw to the caller
1810 //
1811 // Before rewriteDepthImmediates, try_table's catch clauses' argument is a
1812 // trampoline BB from which we throw_ref the exception to the right
1813 // end_try_table. In case of the caller, it will take a new caller-dedicated
1814 // trampoline BB generated by getCallerTrampolineBlock(), which throws the
1815 // exception to the caller.
1816 //
1817 // In case there are multiple calls in a BB that may throw to the caller, they
1818 // can be wrapped together in one nested try_table-end_try_table scope. (In 1,
1819 // this couldn't happen, because may-throwing instruction there had an unwind
1820 // destination, i.e., it was an invoke before, and there could be only one
1821 // invoke within a BB.)
1822
1823 SmallVector<const MachineBasicBlock *, 8> EHPadStack;
1824 // Range of intructions to be wrapped in a new nested try~delegate or
1825 // try_table~end_try_table. A range exists in a single BB and does not span
1826 // multiple BBs.
1827 using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1828 // In original CFG, <unwind destination BB, a vector of try/try_table ranges>
1829 DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges;
1830
1831 // Gather possibly throwing calls (i.e., previously invokes) whose current
1832 // unwind destination is not the same as the original CFG. (Case 1)
1833
1834 for (auto &MBB : reverse(C&: MF)) {
1835 bool SeenThrowableInstInBB = false;
1836 for (auto &MI : reverse(C&: MBB)) {
1837 if (WebAssembly::isTry(Opc: MI.getOpcode()))
1838 EHPadStack.pop_back();
1839 else if (WebAssembly::isCatch(Opc: MI.getOpcode()))
1840 EHPadStack.push_back(Elt: MI.getParent());
1841
1842 // In this loop we only gather calls that have an EH pad to unwind. So
1843 // there will be at most 1 such call (= invoke) in a BB, so after we've
1844 // seen one, we can skip the rest of BB. Also if MBB has no EH pad
1845 // successor or MI does not throw, this is not an invoke.
1846 if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
1847 !WebAssembly::mayThrow(MI))
1848 continue;
1849 SeenThrowableInstInBB = true;
1850
1851 // If the EH pad on the stack top is where this instruction should unwind
1852 // next, we're good.
1853 MachineBasicBlock *UnwindDest = nullptr;
1854 for (auto *Succ : MBB.successors()) {
1855 // Even though semantically a BB can have multiple successors in case an
1856 // exception is not caught by a catchpad, the first unwind destination
1857 // should appear first in the successor list, based on the calculation
1858 // in findUnwindDestinations() in SelectionDAGBuilder.cpp.
1859 if (Succ->isEHPad()) {
1860 UnwindDest = Succ;
1861 break;
1862 }
1863 }
1864 if (EHPadStack.back() == UnwindDest)
1865 continue;
1866
1867 // Include EH_LABELs in the range before and after the invoke
1868 MachineInstr *RangeBegin = &MI, *RangeEnd = &MI;
1869 if (RangeBegin->getIterator() != MBB.begin() &&
1870 std::prev(x: RangeBegin->getIterator())->isEHLabel())
1871 RangeBegin = &*std::prev(x: RangeBegin->getIterator());
1872 if (std::next(x: RangeEnd->getIterator()) != MBB.end() &&
1873 std::next(x: RangeEnd->getIterator())->isEHLabel())
1874 RangeEnd = &*std::next(x: RangeEnd->getIterator());
1875
1876 // If not, record the range.
1877 UnwindDestToTryRanges[UnwindDest].push_back(
1878 Elt: TryRange(RangeBegin, RangeEnd));
1879 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName()
1880 << "\nCall = " << MI
1881 << "\nOriginal dest = " << UnwindDest->getName()
1882 << " Current dest = " << EHPadStack.back()->getName()
1883 << "\n\n");
1884 }
1885 }
1886
1887 assert(EHPadStack.empty());
1888
1889 // Gather possibly throwing calls that are supposed to unwind up to the caller
1890 // if they throw, but currently unwind to an incorrect destination. Unlike the
1891 // loop above, there can be multiple calls within a BB that unwind to the
1892 // caller, which we should group together in a range. (Case 2)
1893
1894 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
1895
1896 // Record the range.
1897 auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) {
1898 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1899 Elt: TryRange(RangeBegin, RangeEnd));
1900 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "
1901 << RangeBegin->getParent()->getName()
1902 << "\nRange begin = " << *RangeBegin
1903 << "Range end = " << *RangeEnd
1904 << "\nOriginal dest = caller Current dest = "
1905 << CurrentDest->getName() << "\n\n");
1906 RangeBegin = RangeEnd = nullptr; // Reset range pointers
1907 };
1908
1909 for (auto &MBB : reverse(C&: MF)) {
1910 bool SeenThrowableInstInBB = false;
1911 for (auto &MI : reverse(C&: MBB)) {
1912 bool MayThrow = WebAssembly::mayThrow(MI);
1913
1914 // If MBB has an EH pad successor and this is the last instruction that
1915 // may throw, this instruction unwinds to the EH pad and not to the
1916 // caller.
1917 if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB)
1918 SeenThrowableInstInBB = true;
1919
1920 // We wrap up the current range when we see a marker even if we haven't
1921 // finished a BB.
1922 else if (RangeEnd && WebAssembly::isMarker(Opc: MI.getOpcode()))
1923 RecordCallerMismatchRange(EHPadStack.back());
1924
1925 // If EHPadStack is empty, that means it correctly unwinds to the caller
1926 // if it throws, so we're good. If MI does not throw, we're good too.
1927 else if (EHPadStack.empty() || !MayThrow) {
1928 }
1929
1930 // We found an instruction that unwinds to the caller but currently has an
1931 // incorrect unwind destination. Create a new range or increment the
1932 // currently existing range.
1933 else {
1934 if (!RangeEnd)
1935 RangeBegin = RangeEnd = &MI;
1936 else
1937 RangeBegin = &MI;
1938 }
1939
1940 // Update EHPadStack.
1941 if (WebAssembly::isTry(Opc: MI.getOpcode()))
1942 EHPadStack.pop_back();
1943 else if (WebAssembly::isCatch(Opc: MI.getOpcode()))
1944 EHPadStack.push_back(Elt: MI.getParent());
1945 }
1946
1947 if (RangeEnd)
1948 RecordCallerMismatchRange(EHPadStack.back());
1949 }
1950
1951 assert(EHPadStack.empty());
1952
1953 // We don't have any unwind destination mismatches to resolve.
1954 if (UnwindDestToTryRanges.empty())
1955 return false;
1956
1957 // When end_loop is before end_try_table within the same BB in unwind
1958 // destinations, we should split the end_loop into another BB.
1959 if (!WebAssembly::WasmUseLegacyEH)
1960 for (auto &[UnwindDest, _] : UnwindDestToTryRanges) {
1961 auto It = EHPadToTry.find(Val: UnwindDest);
1962 // If UnwindDest is the fake caller block, it will not be in EHPadToTry
1963 // map
1964 if (It != EHPadToTry.end()) {
1965 auto *TryTable = It->second;
1966 auto *EndTryTable = BeginToEnd[TryTable];
1967 splitEndLoopBB(EndTryTableBB: EndTryTable->getParent());
1968 }
1969 }
1970
1971 // Now we fix the mismatches by wrapping calls with inner try-delegates.
1972 for (auto &P : UnwindDestToTryRanges) {
1973 NumCallUnwindMismatches += P.second.size();
1974 MachineBasicBlock *UnwindDest = P.first;
1975 auto &TryRanges = P.second;
1976
1977 for (auto Range : TryRanges) {
1978 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1979 std::tie(args&: RangeBegin, args&: RangeEnd) = Range;
1980 auto *MBB = RangeBegin->getParent();
1981
1982 // If this BB has an EH pad successor, i.e., ends with an 'invoke', and if
1983 // the current range contains the invoke, now we are going to wrap the
1984 // invoke with try-delegate or try_table-end_try_table, making the
1985 // 'delegate' or 'end_try_table' BB the new successor instead, so remove
1986 // the EH pad succesor here. The BB may not have an EH pad successor if
1987 // calls in this BB throw to the caller.
1988 if (UnwindDest != getFakeCallerBlock(MF)) {
1989 MachineBasicBlock *EHPad = nullptr;
1990 for (auto *Succ : MBB->successors()) {
1991 if (Succ->isEHPad()) {
1992 EHPad = Succ;
1993 break;
1994 }
1995 }
1996 if (EHPad)
1997 MBB->removeSuccessor(Succ: EHPad);
1998 }
1999
2000 if (WebAssembly::WasmUseLegacyEH)
2001 addNestedTryDelegate(RangeBegin, RangeEnd, UnwindDest);
2002 else
2003 addNestedTryTable(RangeBegin, RangeEnd, UnwindDest);
2004 }
2005 }
2006
2007 return true;
2008}
2009
2010// Returns the single destination of try_table, if there is one. All try_table
2011// we generate in this pass has a single destination, i.e., a single catch
2012// clause.
2013static MachineBasicBlock *getSingleUnwindDest(const MachineInstr *TryTable) {
2014 if (TryTable->getOperand(i: 1).getImm() != 1)
2015 return nullptr;
2016 switch (TryTable->getOperand(i: 2).getImm()) {
2017 case wasm::WASM_OPCODE_CATCH:
2018 case wasm::WASM_OPCODE_CATCH_REF:
2019 return TryTable->getOperand(i: 4).getMBB();
2020 case wasm::WASM_OPCODE_CATCH_ALL:
2021 case wasm::WASM_OPCODE_CATCH_ALL_REF:
2022 return TryTable->getOperand(i: 3).getMBB();
2023 default:
2024 llvm_unreachable("try_table: Invalid catch clause\n");
2025 }
2026}
2027
2028bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {
2029 // This function is used for both the legacy EH and the standard (exnref) EH,
2030 // and the reason we have unwind mismatches is the same for the both of them,
2031 // but the code examples in the comments are going to be different. To make
2032 // the description less confusing, we write the basically same comments twice,
2033 // once for the legacy EH and the standard EH.
2034 //
2035 // -- Legacy EH --------------------------------------------------------------
2036 //
2037 // There is another kind of unwind destination mismatches besides call unwind
2038 // mismatches, which we will call "catch unwind mismatches". See this example
2039 // after the marker placement:
2040 // try
2041 // try
2042 // call @foo
2043 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
2044 // ...
2045 // end_try
2046 // catch_all ;; ehpad B
2047 // ...
2048 // end_try
2049 //
2050 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
2051 // throws a foreign exception that is not caught by ehpad A, and its next
2052 // destination should be the caller. But after control flow linearization,
2053 // another EH pad can be placed in between (e.g. ehpad B here), making the
2054 // next unwind destination incorrect. In this case, the foreign exception will
2055 // instead go to ehpad B and will be caught there instead. In this example the
2056 // correct next unwind destination is the caller, but it can be another outer
2057 // catch in other cases.
2058 //
2059 // There is no specific 'call' or 'throw' instruction to wrap with a
2060 // try-delegate, so we wrap the whole try-catch-end with a try-delegate and
2061 // make it rethrow to the right destination, which is the caller in the
2062 // example below:
2063 // try
2064 // try ;; (new)
2065 // try
2066 // call @foo
2067 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
2068 // ...
2069 // end_try
2070 // delegate 1 (caller) ;; (new)
2071 // catch_all ;; ehpad B
2072 // ...
2073 // end_try
2074 //
2075 // The right destination may be another EH pad or the caller. (The example
2076 // here shows the case it is the caller.)
2077 //
2078 // -- Standard EH ------------------------------------------------------------
2079 //
2080 // There is another kind of unwind destination mismatches besides call unwind
2081 // mismatches, which we will call "catch unwind mismatches". See this example
2082 // after the marker placement:
2083 // block
2084 // try_table (catch_all_ref 0)
2085 // block
2086 // try_table (catch ... 0)
2087 // call @foo
2088 // end_try_table
2089 // end_block ;; ehpad A (next unwind dest: caller)
2090 // ...
2091 // end_try_table
2092 // end_block ;; ehpad B
2093 // ...
2094 //
2095 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
2096 // throws a foreign exception that is not caught by ehpad A, and its next
2097 // destination should be the caller. But after control flow linearization,
2098 // another EH pad can be placed in between (e.g. ehpad B here), making the
2099 // next unwind destination incorrect. In this case, the foreign exception will
2100 // instead go to ehpad B and will be caught there instead. In this example the
2101 // correct next unwind destination is the caller, but it can be another outer
2102 // catch in other cases.
2103 //
2104 // There is no specific 'call' or 'throw' instruction to wrap with an inner
2105 // try_table-end_try_table, so we wrap the whole try_table-end_try_table with
2106 // an inner try_table-end_try_table that sends the exception to a trampoline
2107 // BB. We rethrow the sent exception using a throw_ref to the right
2108 // destination, which is the caller in the example below:
2109 // block exnref
2110 // block
2111 // try_table (catch_all_ref 0)
2112 // try_table (catch_all_ref 2) ;; (new) to trampoline
2113 // block
2114 // try_table (catch ... 0)
2115 // call @foo
2116 // end_try_table
2117 // end_block ;; ehpad A (next unwind dest: caller)
2118 // end_try_table ;; (new)
2119 // ...
2120 // end_try_table
2121 // end_block ;; ehpad B
2122 // ...
2123 // end_block ;; (new) caller trampoline BB
2124 // throw_ref ;; (new) throw to the caller
2125 //
2126 // The right destination may be another EH pad or the caller. (The example
2127 // here shows the case it is the caller.)
2128
2129 const auto *EHInfo = MF.getWasmEHFuncInfo();
2130 assert(EHInfo);
2131 SmallVector<const MachineBasicBlock *, 8> EHPadStack;
2132 // For EH pads that have catch unwind mismatches, a map of <EH pad, its
2133 // correct unwind destination>.
2134 DenseMap<MachineBasicBlock *, MachineBasicBlock *> EHPadToUnwindDest;
2135
2136 for (auto &MBB : reverse(C&: MF)) {
2137 for (auto &MI : reverse(C&: MBB)) {
2138 if (MI.getOpcode() == WebAssembly::TRY)
2139 EHPadStack.pop_back();
2140 else if (MI.getOpcode() == WebAssembly::TRY_TABLE) {
2141 // We want to exclude try_tables created in fixCallUnwindMismatches.
2142 // Check if the try_table's unwind destination matches the EH pad stack
2143 // top. If it is created in fixCallUnwindMismatches, it wouldn't.
2144 if (getSingleUnwindDest(TryTable: &MI) == EHPadStack.back())
2145 EHPadStack.pop_back();
2146 } else if (MI.getOpcode() == WebAssembly::DELEGATE)
2147 EHPadStack.push_back(Elt: &MBB);
2148 else if (WebAssembly::isCatch(Opc: MI.getOpcode())) {
2149 auto *EHPad = &MBB;
2150
2151 // If the BB has a catch pseudo instruction but is not marked as an EH
2152 // pad, it's a trampoline BB we created in fixCallUnwindMismatches. Skip
2153 // it.
2154 if (!EHPad->isEHPad())
2155 continue;
2156
2157 // catch_all always catches an exception, so we don't need to do
2158 // anything
2159 if (WebAssembly::isCatchAll(Opc: MI.getOpcode())) {
2160 }
2161
2162 // This can happen when the unwind dest was removed during the
2163 // optimization, e.g. because it was unreachable.
2164 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(MBB: EHPad)) {
2165 LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName()
2166 << "'s unwind destination does not exist anymore"
2167 << "\n\n");
2168 }
2169
2170 // The EHPad's next unwind destination is the caller, but we incorrectly
2171 // unwind to another EH pad.
2172 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(MBB: EHPad)) {
2173 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
2174 LLVM_DEBUG(dbgs()
2175 << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()
2176 << " Original dest = caller Current dest = "
2177 << EHPadStack.back()->getName() << "\n\n");
2178 }
2179
2180 // The EHPad's next unwind destination is an EH pad, whereas we
2181 // incorrectly unwind to another EH pad.
2182 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(MBB: EHPad)) {
2183 auto *UnwindDest = EHInfo->getUnwindDest(MBB: EHPad);
2184 if (EHPadStack.back() != UnwindDest) {
2185 EHPadToUnwindDest[EHPad] = UnwindDest;
2186 LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "
2187 << EHPad->getName() << " Original dest = "
2188 << UnwindDest->getName() << " Current dest = "
2189 << EHPadStack.back()->getName() << "\n\n");
2190 }
2191 }
2192
2193 EHPadStack.push_back(Elt: EHPad);
2194 }
2195 }
2196 }
2197
2198 assert(EHPadStack.empty());
2199 if (EHPadToUnwindDest.empty())
2200 return false;
2201
2202 // When end_loop is before end_try_table within the same BB in unwind
2203 // destinations, we should split the end_loop into another BB.
2204 for (auto &[_, UnwindDest] : EHPadToUnwindDest) {
2205 auto It = EHPadToTry.find(Val: UnwindDest);
2206 // If UnwindDest is the fake caller block, it will not be in EHPadToTry map
2207 if (It != EHPadToTry.end()) {
2208 auto *TryTable = It->second;
2209 auto *EndTryTable = BeginToEnd[TryTable];
2210 splitEndLoopBB(EndTryTableBB: EndTryTable->getParent());
2211 }
2212 }
2213
2214 NumCatchUnwindMismatches += EHPadToUnwindDest.size();
2215 SmallPtrSet<MachineBasicBlock *, 4> NewEndTryBBs;
2216
2217 for (auto &[EHPad, UnwindDest] : EHPadToUnwindDest) {
2218 MachineInstr *Try = EHPadToTry[EHPad];
2219 MachineInstr *EndTry = BeginToEnd[Try];
2220 if (WebAssembly::WasmUseLegacyEH) {
2221 addNestedTryDelegate(RangeBegin: Try, RangeEnd: EndTry, UnwindDest);
2222 NewEndTryBBs.insert(Ptr: EndTry->getParent());
2223 } else {
2224 addNestedTryTable(RangeBegin: Try, RangeEnd: EndTry, UnwindDest);
2225 }
2226 }
2227
2228 if (!WebAssembly::WasmUseLegacyEH)
2229 return true;
2230
2231 // Adding a try-delegate wrapping an existing try-catch-end can make existing
2232 // branch destination BBs invalid. For example,
2233 //
2234 // - Before:
2235 // bb0:
2236 // block
2237 // br bb3
2238 // bb1:
2239 // try
2240 // ...
2241 // bb2: (ehpad)
2242 // catch
2243 // bb3:
2244 // end_try
2245 // end_block ;; 'br bb3' targets here
2246 //
2247 // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap
2248 // this with a try-delegate. Then this becomes:
2249 //
2250 // - After:
2251 // bb0:
2252 // block
2253 // br bb3 ;; invalid destination!
2254 // bb1:
2255 // try ;; (new instruction)
2256 // try
2257 // ...
2258 // bb2: (ehpad)
2259 // catch
2260 // bb3:
2261 // end_try ;; 'br bb3' still incorrectly targets here!
2262 // delegate_bb: ;; (new BB)
2263 // delegate ;; (new instruction)
2264 // split_bb: ;; (new BB)
2265 // end_block
2266 //
2267 // Now 'br bb3' incorrectly branches to an inner scope.
2268 //
2269 // As we can see in this case, when branches target a BB that has both
2270 // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we
2271 // have to remap existing branch destinations so that they target not the
2272 // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's
2273 // in between, so we try to find the next BB with 'end_block' instruction. In
2274 // this example, the 'br bb3' instruction should be remapped to 'br split_bb'.
2275 for (auto &MBB : MF) {
2276 for (auto &MI : MBB) {
2277 if (MI.isTerminator()) {
2278 for (auto &MO : MI.operands()) {
2279 if (MO.isMBB() && NewEndTryBBs.count(Ptr: MO.getMBB())) {
2280 auto *BrDest = MO.getMBB();
2281 bool FoundEndBlock = false;
2282 for (; std::next(x: BrDest->getIterator()) != MF.end();
2283 BrDest = BrDest->getNextNode()) {
2284 for (const auto &MI : *BrDest) {
2285 if (MI.getOpcode() == WebAssembly::END_BLOCK) {
2286 FoundEndBlock = true;
2287 break;
2288 }
2289 }
2290 if (FoundEndBlock)
2291 break;
2292 }
2293 assert(FoundEndBlock);
2294 MO.setMBB(BrDest);
2295 }
2296 }
2297 }
2298 }
2299 }
2300
2301 return true;
2302}
2303
2304void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {
2305 // Renumber BBs and recalculate ScopeTop info because new BBs might have been
2306 // created and inserted during fixing unwind mismatches.
2307 MF.RenumberBlocks();
2308 MDT->updateBlockNumbers();
2309 ScopeTops.clear();
2310 ScopeTops.resize(N: MF.getNumBlockIDs());
2311 for (auto &MBB : reverse(C&: MF)) {
2312 for (auto &MI : reverse(C&: MBB)) {
2313 if (ScopeTops[MBB.getNumber()])
2314 break;
2315 switch (MI.getOpcode()) {
2316 case WebAssembly::END_BLOCK:
2317 case WebAssembly::END_LOOP:
2318 case WebAssembly::END_TRY:
2319 case WebAssembly::END_TRY_TABLE:
2320 case WebAssembly::DELEGATE:
2321 updateScopeTops(Begin: EndToBegin[&MI]->getParent(), End: &MBB);
2322 break;
2323 case WebAssembly::CATCH_LEGACY:
2324 case WebAssembly::CATCH_ALL_LEGACY:
2325 updateScopeTops(Begin: EHPadToTry[&MBB]->getParent(), End: &MBB);
2326 break;
2327 }
2328 }
2329 }
2330}
2331
2332/// In normal assembly languages, when the end of a function is unreachable,
2333/// because the function ends in an infinite loop or a noreturn call or similar,
2334/// it isn't necessary to worry about the function return type at the end of
2335/// the function, because it's never reached. However, in WebAssembly, blocks
2336/// that end at the function end need to have a return type signature that
2337/// matches the function signature, even though it's unreachable. This function
2338/// checks for such cases and fixes up the signatures.
2339void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
2340 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
2341
2342 if (MFI.getResults().empty())
2343 return;
2344
2345 // MCInstLower will add the proper types to multivalue signatures based on the
2346 // function return type
2347 WebAssembly::BlockType RetType =
2348 MFI.getResults().size() > 1
2349 ? WebAssembly::BlockType::Multivalue
2350 : WebAssembly::BlockType(
2351 WebAssembly::toValType(Type: MFI.getResults().front()));
2352
2353 SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist;
2354 Worklist.push_back(Elt: MF.rbegin()->rbegin());
2355
2356 auto Process = [&](MachineBasicBlock::reverse_iterator It) {
2357 auto *MBB = It->getParent();
2358 while (It != MBB->rend()) {
2359 MachineInstr &MI = *It++;
2360 if (MI.isPosition() || MI.isDebugInstr())
2361 continue;
2362 switch (MI.getOpcode()) {
2363 case WebAssembly::END_TRY: {
2364 // If a 'try''s return type is fixed, both its try body and catch body
2365 // should satisfy the return type, so we need to search 'end'
2366 // instructions before its corresponding 'catch' too.
2367 auto *EHPad = TryToEHPad.lookup(Val: EndToBegin[&MI]);
2368 assert(EHPad);
2369 auto NextIt =
2370 std::next(x: WebAssembly::findCatch(EHPad)->getReverseIterator());
2371 if (NextIt != EHPad->rend())
2372 Worklist.push_back(Elt: NextIt);
2373 [[fallthrough]];
2374 }
2375 case WebAssembly::END_BLOCK:
2376 case WebAssembly::END_LOOP:
2377 case WebAssembly::END_TRY_TABLE:
2378 case WebAssembly::DELEGATE:
2379 EndToBegin[&MI]->getOperand(i: 0).setImm(int32_t(RetType));
2380 continue;
2381 default:
2382 // Something other than an `end`. We're done for this BB.
2383 return;
2384 }
2385 }
2386 // We've reached the beginning of a BB. Continue the search in the previous
2387 // BB.
2388 Worklist.push_back(Elt: MBB->getPrevNode()->rbegin());
2389 };
2390
2391 while (!Worklist.empty())
2392 Process(Worklist.pop_back_val());
2393}
2394
2395// WebAssembly functions end with an end instruction, as if the function body
2396// were a block.
2397static void appendEndToFunction(MachineFunction &MF,
2398 const WebAssemblyInstrInfo &TII) {
2399 BuildMI(BB&: MF.back(), I: MF.back().end(),
2400 MIMD: MF.back().findPrevDebugLoc(MBBI: MF.back().end()),
2401 MCID: TII.get(Opcode: WebAssembly::END_FUNCTION));
2402}
2403
2404// We added block~end_block and try_table~end_try_table markers in
2405// placeTryTableMarker. But When catch clause's destination has a return type,
2406// as in the case of catch with a concrete tag, catch_ref, and catch_all_ref.
2407// For example:
2408// block exnref
2409// try_table (catch_all_ref 0)
2410// ...
2411// end_try_table
2412// end_block
2413// ... use exnref ...
2414//
2415// This code is not valid because the block's body type is not exnref. So we add
2416// an unreachable after the 'end_try_table' to make the code valid here:
2417// block exnref
2418// try_table (catch_all_ref 0)
2419// ...
2420// end_try_table
2421// unreachable (new)
2422// end_block
2423//
2424// Because 'unreachable' is a terminator we also need to split the BB.
2425static void addUnreachableAfterTryTables(MachineFunction &MF,
2426 const WebAssemblyInstrInfo &TII) {
2427 std::vector<MachineInstr *> EndTryTables;
2428 for (auto &MBB : MF)
2429 for (auto &MI : MBB)
2430 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE)
2431 EndTryTables.push_back(x: &MI);
2432
2433 for (auto *EndTryTable : EndTryTables) {
2434 auto *MBB = EndTryTable->getParent();
2435 auto *NewEndTryTableBB = MF.CreateMachineBasicBlock();
2436 MF.insert(MBBI: MBB->getIterator(), MBB: NewEndTryTableBB);
2437 auto SplitPos = std::next(x: EndTryTable->getIterator());
2438 NewEndTryTableBB->splice(Where: NewEndTryTableBB->end(), Other: MBB, From: MBB->begin(),
2439 To: SplitPos);
2440 NewEndTryTableBB->addSuccessor(Succ: MBB);
2441 BuildMI(BB: NewEndTryTableBB, MIMD: EndTryTable->getDebugLoc(),
2442 MCID: TII.get(Opcode: WebAssembly::UNREACHABLE));
2443 }
2444}
2445
2446/// Insert BLOCK/LOOP/TRY/TRY_TABLE markers at appropriate places.
2447void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
2448 // We allocate one more than the number of blocks in the function to
2449 // accommodate for the possible fake block we may insert at the end.
2450 ScopeTops.resize(N: MF.getNumBlockIDs() + 1);
2451 // Place the LOOP for MBB if MBB is the header of a loop.
2452 for (auto &MBB : MF)
2453 placeLoopMarker(MBB);
2454
2455 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
2456 for (auto &MBB : MF) {
2457 if (MBB.isEHPad()) {
2458 // Place the TRY/TRY_TABLE for MBB if MBB is the EH pad of an exception.
2459 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2460 MF.getFunction().hasPersonalityFn()) {
2461 if (WebAssembly::WasmUseLegacyEH)
2462 placeTryMarker(MBB);
2463 else
2464 placeTryTableMarker(MBB);
2465 }
2466 } else {
2467 // Place the BLOCK for MBB if MBB is branched to from above.
2468 placeBlockMarker(MBB);
2469 }
2470 }
2471
2472 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2473 MF.getFunction().hasPersonalityFn()) {
2474 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
2475 // Add an 'unreachable' after 'end_try_table's.
2476 addUnreachableAfterTryTables(MF, TII);
2477 // Fix mismatches in unwind destinations induced by linearizing the code.
2478 fixCallUnwindMismatches(MF);
2479 fixCatchUnwindMismatches(MF);
2480 // addUnreachableAfterTryTables and fixUnwindMismatches create new BBs, so
2481 // we need to recalculate ScopeTops.
2482 recalculateScopeTops(MF);
2483 }
2484}
2485
2486unsigned WebAssemblyCFGStackify::getBranchDepth(
2487 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
2488 unsigned Depth = 0;
2489 for (auto X : reverse(C: Stack)) {
2490 if (X.first == MBB)
2491 break;
2492 ++Depth;
2493 }
2494 assert(Depth < Stack.size() && "Branch destination should be in scope");
2495 return Depth;
2496}
2497
2498unsigned WebAssemblyCFGStackify::getDelegateDepth(
2499 const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
2500 if (MBB == FakeCallerBB)
2501 return Stack.size();
2502 // Delegate's destination is either a catch or a another delegate BB. When the
2503 // destination is another delegate, we can compute the argument in the same
2504 // way as branches, because the target delegate BB only contains the single
2505 // delegate instruction.
2506 if (!MBB->isEHPad()) // Target is a delegate BB
2507 return getBranchDepth(Stack, MBB);
2508
2509 // When the delegate's destination is a catch BB, we need to use its
2510 // corresponding try's end_try BB because Stack contains each marker's end BB.
2511 // Also we need to check if the end marker instruction matches, because a
2512 // single BB can contain multiple end markers, like this:
2513 // bb:
2514 // END_BLOCK
2515 // END_TRY
2516 // END_BLOCK
2517 // END_TRY
2518 // ...
2519 //
2520 // In case of branches getting the immediate that targets any of these is
2521 // fine, but delegate has to exactly target the correct try.
2522 unsigned Depth = 0;
2523 const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];
2524 for (auto X : reverse(C: Stack)) {
2525 if (X.first == EndTry->getParent() && X.second == EndTry)
2526 break;
2527 ++Depth;
2528 }
2529 assert(Depth < Stack.size() && "Delegate destination should be in scope");
2530 return Depth;
2531}
2532
2533unsigned WebAssemblyCFGStackify::getRethrowDepth(
2534 const SmallVectorImpl<EndMarkerInfo> &Stack,
2535 const MachineBasicBlock *EHPadToRethrow) {
2536 unsigned Depth = 0;
2537 for (auto X : reverse(C: Stack)) {
2538 const MachineInstr *End = X.second;
2539 if (End->getOpcode() == WebAssembly::END_TRY) {
2540 auto *EHPad = TryToEHPad[EndToBegin[End]];
2541 if (EHPadToRethrow == EHPad)
2542 break;
2543 }
2544 ++Depth;
2545 }
2546 assert(Depth < Stack.size() && "Rethrow destination should be in scope");
2547 return Depth;
2548}
2549
2550void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
2551 // Now rewrite references to basic blocks to be depth immediates.
2552 SmallVector<EndMarkerInfo, 8> Stack;
2553
2554 auto RewriteOperands = [&](MachineInstr &MI) {
2555 // Rewrite MBB operands to be depth immediates.
2556 SmallVector<MachineOperand, 4> Ops(MI.operands());
2557 while (MI.getNumOperands() > 0)
2558 MI.removeOperand(OpNo: MI.getNumOperands() - 1);
2559 for (auto MO : Ops) {
2560 if (MO.isMBB()) {
2561 if (MI.getOpcode() == WebAssembly::DELEGATE)
2562 MO = MachineOperand::CreateImm(Val: getDelegateDepth(Stack, MBB: MO.getMBB()));
2563 else if (MI.getOpcode() == WebAssembly::RETHROW)
2564 MO = MachineOperand::CreateImm(Val: getRethrowDepth(Stack, EHPadToRethrow: MO.getMBB()));
2565 else
2566 MO = MachineOperand::CreateImm(Val: getBranchDepth(Stack, MBB: MO.getMBB()));
2567 }
2568 MI.addOperand(MF, Op: MO);
2569 }
2570 };
2571
2572 for (auto &MBB : reverse(C&: MF)) {
2573 for (MachineInstr &MI : llvm::reverse(C&: MBB)) {
2574 switch (MI.getOpcode()) {
2575 case WebAssembly::BLOCK:
2576 case WebAssembly::TRY:
2577 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2578 MBB.getNumber() &&
2579 "Block/try/try_table marker should be balanced");
2580 Stack.pop_back();
2581 break;
2582
2583 case WebAssembly::TRY_TABLE:
2584 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2585 MBB.getNumber() &&
2586 "Block/try/try_table marker should be balanced");
2587 Stack.pop_back();
2588 RewriteOperands(MI);
2589 break;
2590
2591 case WebAssembly::LOOP:
2592 assert(Stack.back().first == &MBB && "Loop top should be balanced");
2593 Stack.pop_back();
2594 break;
2595
2596 case WebAssembly::END_BLOCK:
2597 case WebAssembly::END_TRY:
2598 case WebAssembly::END_TRY_TABLE:
2599 Stack.push_back(Elt: std::make_pair(x: &MBB, y: &MI));
2600 break;
2601
2602 case WebAssembly::END_LOOP:
2603 Stack.push_back(Elt: std::make_pair(x: EndToBegin[&MI]->getParent(), y: &MI));
2604 break;
2605
2606 case WebAssembly::DELEGATE:
2607 RewriteOperands(MI);
2608 Stack.push_back(Elt: std::make_pair(x: &MBB, y: &MI));
2609 break;
2610
2611 default:
2612 if (MI.isTerminator())
2613 RewriteOperands(MI);
2614 break;
2615 }
2616 }
2617 }
2618 assert(Stack.empty() && "Control flow should be balanced");
2619}
2620
2621void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) {
2622 if (FakeCallerBB)
2623 MF.deleteMachineBasicBlock(MBB: FakeCallerBB);
2624 AppendixBB = FakeCallerBB = CallerTrampolineBB = nullptr;
2625}
2626
2627void WebAssemblyCFGStackify::releaseMemory() {
2628 ScopeTops.clear();
2629 BeginToEnd.clear();
2630 EndToBegin.clear();
2631 TryToEHPad.clear();
2632 EHPadToTry.clear();
2633 UnwindDestToTrampoline.clear();
2634}
2635
2636bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
2637 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
2638 "********** Function: "
2639 << MF.getName() << '\n');
2640 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
2641 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
2642
2643 releaseMemory();
2644
2645 // Liveness is not tracked for VALUE_STACK physreg.
2646 MF.getRegInfo().invalidateLiveness();
2647
2648 // Place the BLOCK/LOOP/TRY/TRY_TABLE markers to indicate the beginnings of
2649 // scopes.
2650 placeMarkers(MF);
2651
2652 // Remove unnecessary instructions possibly introduced by try/end_trys.
2653 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2654 MF.getFunction().hasPersonalityFn() && WebAssembly::WasmUseLegacyEH)
2655 removeUnnecessaryInstrs(MF);
2656
2657 // Convert MBB operands in terminators to relative depth immediates.
2658 rewriteDepthImmediates(MF);
2659
2660 // Fix up block/loop/try/try_table signatures at the end of the function to
2661 // conform to WebAssembly's rules.
2662 fixEndsAtEndOfFunction(MF);
2663
2664 // Add an end instruction at the end of the function body.
2665 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
2666 appendEndToFunction(MF, TII);
2667
2668 cleanupFunctionData(MF);
2669
2670 MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
2671 return true;
2672}
2673