LLVM 20.0.0git
WebAssemblyCFGStackify.cpp
Go to the documentation of this file.
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
26#include "WebAssembly.h"
32#include "llvm/ADT/Statistic.h"
38#include "llvm/MC/MCAsmInfo.h"
40using namespace llvm;
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 {
51
52 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
53
54 void getAnalysisUsage(AnalysisUsage &AU) const override {
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.
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).
111 // For each END_(BLOCK|LOOP|TRY|TRY_TABLE) or DELEGATE, the corresponding
112 // BLOCK|LOOP|TRY|TRY_TABLE.
114 // <TRY marker, EH pad> map
116 // <EH pad, TRY marker> map
118
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(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(CallerTrampolineBB->getIterator(), AppendixBB);
134 else
135 MF.push_back(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(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;
181 WebAssemblyCFGStackify, DEBUG_TYPE,
182 "Insert BLOCK/LOOP/TRY/TRY_TABLE markers for WebAssembly scopes", false,
183 false)
184
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.
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>
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(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>
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,
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(Begin);
271 EndToBegin.erase(End);
272 MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
273 if (EHPad) {
274 assert(EHPadToTry.count(EHPad));
275 TryToEHPad.erase(Begin);
276 EHPadToTry.erase(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());
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(Header, Pred) : Pred;
298 if (explicitlyBranchesTo(Pred, &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(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.
329 // Instructions that should go after the BLOCK.
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(&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(&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(&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(I)->isDebugInstr() || std::prev(I)->isPosition())
378 continue;
379 if (WebAssembly::isChild(*std::prev(I), MFI))
380 AfterSet.insert(&*std::prev(I));
381 else
382 break;
383 }
384
385 // Add the BLOCK.
386 WebAssembly::BlockType ReturnType = WebAssembly::BlockType::Void;
387 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
388 MachineInstr *Begin =
389 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
390 TII.get(WebAssembly::BLOCK))
391 .addImm(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(&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, BeforeSet, AfterSet);
425 MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
426 TII.get(WebAssembly::END_BLOCK));
427 registerScope(Begin, End);
428
429 // Track the farthest-spanning scope that ends at this point.
430 updateScopeTops(Header, &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) {
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(&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(Loop);
448 auto Iter = std::next(Bottom->getIterator());
449 if (Iter == MF.end()) {
450 getAppendixBlock(MF);
451 Iter = std::next(Bottom->getIterator());
452 }
453 MachineBasicBlock *AfterLoop = &*Iter;
454
455 // Decide where in Header to put the LOOP.
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(&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, BeforeSet, AfterSet);
471 MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),
472 TII.get(WebAssembly::LOOP))
473 .addImm(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(AfterLoop, BeforeSet, AfterSet);
488 DebugLoc EndDL = AfterLoop->pred_empty()
489 ? DebugLoc()
490 : (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
492 BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(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(&MBB, AfterLoop);
499}
500
501void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
502 assert(MBB.isEHPad());
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(Header, Pred) : Pred;
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);
527 assert(WE);
528 MachineBasicBlock *Bottom = SRI.getBottom(WE);
529 auto Iter = std::next(Bottom->getIterator());
530 if (Iter == MF.end()) {
531 getAppendixBlock(MF);
532 Iter = std::next(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(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.
555 // Instructions that should go after the TRY.
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(&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(&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(&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(Header)) {
597 auto TermPos = Header->getFirstTerminator();
598 if (TermPos == Header->end() ||
599 TermPos->getOpcode() != WebAssembly::RETHROW) {
600 for (auto &MI : reverse(*Header)) {
601 if (MI.isCall()) {
602 AfterSet.insert(&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(MI.getIterator())->isEHLabel()) {
608 AfterSet.insert(&*std::prev(MI.getIterator()));
609 ThrowingCall = &*std::prev(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(I)->isDebugInstr() || std::prev(I)->isPosition())
627 continue;
628 if (WebAssembly::isChild(*std::prev(I), MFI))
629 AfterSet.insert(&*std::prev(I));
630 else
631 break;
632 }
633
634 // Add the TRY.
635 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
636 MachineInstr *Begin =
637 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
638 TII.get(WebAssembly::TRY))
639 .addImm(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(&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(Cont, BeforeSet, AfterSet);
676 MachineInstr *End = BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(),
677 TII.get(WebAssembly::END_TRY));
678 registerTryScope(Begin, End, &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(Header, End);
693}
694
695void WebAssemblyCFGStackify::placeTryTableMarker(MachineBasicBlock &MBB) {
696 assert(MBB.isEHPad());
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(Header, Pred) : Pred;
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);
722 assert(WE);
723 MachineBasicBlock *Bottom = SRI.getBottom(WE);
724 auto Iter = std::next(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(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.
748 // Instructions that should go after the TRY_TABLE.
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(&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(&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(&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(Header)) {
790 auto TermPos = Header->getFirstTerminator();
791 if (TermPos == Header->end() ||
792 TermPos->getOpcode() != WebAssembly::RETHROW) {
793 for (auto &MI : reverse(*Header)) {
794 if (MI.isCall()) {
795 AfterSet.insert(&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(MI.getIterator())->isEHLabel()) {
801 AfterSet.insert(&*std::prev(MI.getIterator()));
802 ThrowingCall = &*std::prev(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(I)->isDebugInstr() || std::prev(I)->isPosition())
820 continue;
821 if (WebAssembly::isChild(*std::prev(I), MFI))
822 AfterSet.insert(&*std::prev(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(Header, BeforeSet, AfterSet);
841 MachineInstrBuilder BlockMIB =
842 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
843 TII.get(WebAssembly::BLOCK));
844 auto *Block = BlockMIB.getInstr();
845 MachineInstrBuilder TryTableMIB =
846 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
847 TII.get(WebAssembly::TRY_TABLE))
848 .addImm(int64_t(WebAssembly::BlockType::Void))
849 .addImm(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.
856 switch (Catch->getOpcode()) {
857 case WebAssembly::CATCH:
858 // CATCH's destination block's return type is the extracted value type,
859 // which is currently i32 for all supported tags.
860 BlockMIB.addImm(int64_t(WebAssembly::BlockType::I32));
861 TryTableMIB.addImm(wasm::WASM_OPCODE_CATCH);
862 for (const auto &Use : Catch->uses()) {
863 // The only use operand a CATCH can have is the tag symbol.
864 TryTableMIB.addExternalSymbol(Use.getSymbolName());
865 break;
866 }
867 TryTableMIB.addMBB(&MBB);
868 break;
869 case WebAssembly::CATCH_REF:
870 // CATCH_REF's destination block's return type is the extracted value type
871 // followed by an exnref, which is (i32, exnref) in our case. We assign the
872 // actual multiavlue signature in MCInstLower. MO_CATCH_BLOCK_SIG signals
873 // that this operand is used for catch_ref's multivalue destination.
874 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Multivalue));
875 Block->getOperand(0).setTargetFlags(WebAssemblyII::MO_CATCH_BLOCK_SIG);
877 for (const auto &Use : Catch->uses()) {
878 TryTableMIB.addExternalSymbol(Use.getSymbolName());
879 break;
880 }
881 TryTableMIB.addMBB(&MBB);
882 break;
883 case WebAssembly::CATCH_ALL:
884 // CATCH_ALL's destination block's return type is void.
885 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Void));
887 TryTableMIB.addMBB(&MBB);
888 break;
889 case WebAssembly::CATCH_ALL_REF:
890 // CATCH_ALL_REF's destination block's return type is exnref.
891 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Exnref));
893 TryTableMIB.addMBB(&MBB);
894 break;
895 }
896
897 // Decide where in MBB to put the END_TRY_TABLE, and the END_BLOCK for the
898 // CATCH destination.
899 BeforeSet.clear();
900 AfterSet.clear();
901 for (const auto &MI : MBB) {
902#ifndef NDEBUG
903 // END_TRY_TABLE should precede existing LOOP markers.
904 if (MI.getOpcode() == WebAssembly::LOOP)
905 AfterSet.insert(&MI);
906#endif
907
908 // If there is a previously placed END_LOOP marker and the header of the
909 // loop is above this try_table's header, the END_LOOP should be placed
910 // after the END_TRY_TABLE, because the loop contains this block. Otherwise
911 // the END_LOOP should be placed before the END_TRY_TABLE.
912 if (MI.getOpcode() == WebAssembly::END_LOOP) {
913 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
914 BeforeSet.insert(&MI);
915#ifndef NDEBUG
916 else
917 AfterSet.insert(&MI);
918#endif
919 }
920
921#ifndef NDEBUG
922 // CATCH, CATCH_REF, CATCH_ALL, and CATCH_ALL_REF are pseudo-instructions
923 // that simulate the block return value, so they should be placed after the
924 // END_TRY_TABLE.
925 if (WebAssembly::isCatch(MI.getOpcode()))
926 AfterSet.insert(&MI);
927#endif
928 }
929
930 // Mark the end of the TRY_TABLE and the BLOCK.
931 InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
932 MachineInstr *EndTryTable =
933 BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
934 TII.get(WebAssembly::END_TRY_TABLE));
935 registerTryScope(TryTable, EndTryTable, &MBB);
936 MachineInstr *EndBlock =
937 BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
938 TII.get(WebAssembly::END_BLOCK));
939 registerScope(Block, EndBlock);
940
941 // Track the farthest-spanning scope that ends at this point.
942 // Unlike the end_try, even if we don't put a end marker at the end of catch
943 // block, we still have to create two mappings: (BB with 'end_try_table' -> BB
944 // with 'try_table') and (BB after the (conceptual) catch block -> BB with
945 // 'try_table').
946 //
947 // This is what can happen if we don't create the latter mapping:
948 //
949 // Suppoe in the legacy EH we have this code:
950 // try
951 // try
952 // code1
953 // catch (a)
954 // end_try
955 // code2
956 // catch (b)
957 // end_try
958 //
959 // If we don't create the latter mapping, try_table markers would be placed
960 // like this:
961 // try_table
962 // code1
963 // end_try_table (a)
964 // try_table
965 // code2
966 // end_try_table (b)
967 //
968 // This does not reflect the original structure, and more important problem
969 // is, in case 'code1' has an unwind mismatch and should unwind to
970 // 'end_try_table (b)' rather than 'end_try_table (a)', we don't have a way to
971 // make it jump after 'end_try_table (b)' without creating another block. So
972 // even if we don't place 'end_try' marker at the end of 'catch' block
973 // anymore, we create ScopeTops mapping the same way as the legacy exception,
974 // so the resulting code will look like:
975 // try_table
976 // try_table
977 // code1
978 // end_try_table (a)
979 // code2
980 // end_try_table (b)
981 for (auto *End : {&MBB, Cont})
982 updateScopeTops(Header, End);
983}
984
985void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
986 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
987
988 // When there is an unconditional branch right before a catch instruction and
989 // it branches to the end of end_try marker, we don't need the branch, because
990 // if there is no exception, the control flow transfers to that point anyway.
991 // bb0:
992 // try
993 // ...
994 // br bb2 <- Not necessary
995 // bb1 (ehpad):
996 // catch
997 // ...
998 // bb2: <- Continuation BB
999 // end
1000 //
1001 // A more involved case: When the BB where 'end' is located is an another EH
1002 // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example,
1003 // bb0:
1004 // try
1005 // try
1006 // ...
1007 // br bb3 <- Not necessary
1008 // bb1 (ehpad):
1009 // catch
1010 // bb2 (ehpad):
1011 // end
1012 // catch
1013 // ...
1014 // bb3: <- Continuation BB
1015 // end
1016 //
1017 // When the EH pad at hand is bb1, its matching end_try is in bb2. But it is
1018 // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the
1019 // code can be deleted. This is why we run 'while' until 'Cont' is not an EH
1020 // pad.
1021 for (auto &MBB : MF) {
1022 if (!MBB.isEHPad())
1023 continue;
1024
1025 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1027 MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
1028
1029 MachineBasicBlock *Cont = &MBB;
1030 while (Cont->isEHPad()) {
1031 MachineInstr *Try = EHPadToTry[Cont];
1032 MachineInstr *EndTry = BeginToEnd[Try];
1033 // We started from an EH pad, so the end marker cannot be a delegate
1034 assert(EndTry->getOpcode() != WebAssembly::DELEGATE);
1035 Cont = EndTry->getParent();
1036 }
1037
1038 bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
1039 // This condition means either
1040 // 1. This BB ends with a single unconditional branch whose destinaion is
1041 // Cont.
1042 // 2. This BB ends with a conditional branch followed by an unconditional
1043 // branch, and the unconditional branch's destination is Cont.
1044 // In both cases, we want to remove the last (= unconditional) branch.
1045 if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
1046 (!Cond.empty() && FBB && FBB == Cont))) {
1047 bool ErasedUncondBr = false;
1048 (void)ErasedUncondBr;
1049 for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin();
1050 I != E; --I) {
1051 auto PrevI = std::prev(I);
1052 if (PrevI->isTerminator()) {
1053 assert(PrevI->getOpcode() == WebAssembly::BR);
1054 PrevI->eraseFromParent();
1055 ErasedUncondBr = true;
1056 break;
1057 }
1058 }
1059 assert(ErasedUncondBr && "Unconditional branch not erased!");
1060 }
1061 }
1062
1063 // When there are block / end_block markers that overlap with try / end_try
1064 // markers, and the block and try markers' return types are the same, the
1065 // block /end_block markers are not necessary, because try / end_try markers
1066 // also can serve as boundaries for branches.
1067 // block <- Not necessary
1068 // try
1069 // ...
1070 // catch
1071 // ...
1072 // end
1073 // end <- Not necessary
1075 for (auto &MBB : MF) {
1076 for (auto &MI : MBB) {
1077 if (MI.getOpcode() != WebAssembly::TRY)
1078 continue;
1079 MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
1080 if (EndTry->getOpcode() == WebAssembly::DELEGATE)
1081 continue;
1082
1083 MachineBasicBlock *TryBB = Try->getParent();
1084 MachineBasicBlock *Cont = EndTry->getParent();
1085 int64_t RetType = Try->getOperand(0).getImm();
1086 for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());
1087 B != TryBB->begin() && E != Cont->end() &&
1088 std::prev(B)->getOpcode() == WebAssembly::BLOCK &&
1089 E->getOpcode() == WebAssembly::END_BLOCK &&
1090 std::prev(B)->getOperand(0).getImm() == RetType;
1091 --B, ++E) {
1092 ToDelete.push_back(&*std::prev(B));
1093 ToDelete.push_back(&*E);
1094 }
1095 }
1096 }
1097 for (auto *MI : ToDelete) {
1098 if (MI->getOpcode() == WebAssembly::BLOCK)
1099 unregisterScope(MI);
1100 MI->eraseFromParent();
1101 }
1102}
1103
1104// When MBB is split into MBB and Split, we should unstackify defs in MBB that
1105// have their uses in Split.
1107 MachineBasicBlock &Split) {
1108 MachineFunction &MF = *MBB.getParent();
1109 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1110 auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1111 auto &MRI = MF.getRegInfo();
1112
1113 for (auto &MI : Split) {
1114 for (auto &MO : MI.explicit_uses()) {
1115 if (!MO.isReg() || MO.getReg().isPhysical())
1116 continue;
1117 if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg()))
1118 if (Def->getParent() == &MBB)
1119 MFI.unstackifyVReg(MO.getReg());
1120 }
1121 }
1122
1123 // In RegStackify, when a register definition is used multiple times,
1124 // Reg = INST ...
1125 // INST ..., Reg, ...
1126 // INST ..., Reg, ...
1127 // INST ..., Reg, ...
1128 //
1129 // we introduce a TEE, which has the following form:
1130 // DefReg = INST ...
1131 // TeeReg, Reg = TEE_... DefReg
1132 // INST ..., TeeReg, ...
1133 // INST ..., Reg, ...
1134 // INST ..., Reg, ...
1135 // with DefReg and TeeReg stackified but Reg not stackified.
1136 //
1137 // But the invariant that TeeReg should be stackified can be violated while we
1138 // unstackify registers in the split BB above. In this case, we convert TEEs
1139 // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals.
1140 // DefReg = INST ...
1141 // TeeReg = COPY DefReg
1142 // Reg = COPY DefReg
1143 // INST ..., TeeReg, ...
1144 // INST ..., Reg, ...
1145 // INST ..., Reg, ...
1147 if (!WebAssembly::isTee(MI.getOpcode()))
1148 continue;
1149 Register TeeReg = MI.getOperand(0).getReg();
1150 Register Reg = MI.getOperand(1).getReg();
1151 Register DefReg = MI.getOperand(2).getReg();
1152 if (!MFI.isVRegStackified(TeeReg)) {
1153 // Now we are not using TEE anymore, so unstackify DefReg too
1154 MFI.unstackifyVReg(DefReg);
1155 unsigned CopyOpc =
1156 WebAssembly::getCopyOpcodeForRegClass(MRI.getRegClass(DefReg));
1157 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg)
1158 .addReg(DefReg);
1159 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg);
1160 MI.eraseFromParent();
1161 }
1162 }
1163}
1164
1165// Wrap the given range of instructions with a try-delegate that targets
1166// 'UnwindDest'. RangeBegin and RangeEnd are inclusive.
1167void WebAssemblyCFGStackify::addNestedTryDelegate(
1168 MachineInstr *RangeBegin, MachineInstr *RangeEnd,
1169 MachineBasicBlock *UnwindDest) {
1170 auto *BeginBB = RangeBegin->getParent();
1171 auto *EndBB = RangeEnd->getParent();
1172 MachineFunction &MF = *BeginBB->getParent();
1173 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1174 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1175
1176 // Local expression tree before the first call of this range should go
1177 // after the nested TRY.
1179 AfterSet.insert(RangeBegin);
1180 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();
1181 I != E; --I) {
1182 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
1183 continue;
1184 if (WebAssembly::isChild(*std::prev(I), MFI))
1185 AfterSet.insert(&*std::prev(I));
1186 else
1187 break;
1188 }
1189
1190 // Create the nested try instruction.
1191 auto TryPos = getLatestInsertPos(
1192 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
1193 MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(),
1194 TII.get(WebAssembly::TRY))
1195 .addImm(int64_t(WebAssembly::BlockType::Void));
1196
1197 // Create a BB to insert the 'delegate' instruction.
1198 MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock();
1199 // If the destination of 'delegate' is not the caller, adds the destination to
1200 // the BB's successors.
1201 if (UnwindDest != FakeCallerBB)
1202 DelegateBB->addSuccessor(UnwindDest);
1203
1204 auto SplitPos = std::next(RangeEnd->getIterator());
1205 if (SplitPos == EndBB->end()) {
1206 // If the range's end instruction is at the end of the BB, insert the new
1207 // delegate BB after the current BB.
1208 MF.insert(std::next(EndBB->getIterator()), DelegateBB);
1209 EndBB->addSuccessor(DelegateBB);
1210
1211 } else {
1212 // When the split pos is in the middle of a BB, we split the BB into two and
1213 // put the 'delegate' BB in between. We normally create a split BB and make
1214 // it a successor of the original BB (CatchAfterSplit == false), but in case
1215 // the BB is an EH pad and there is a 'catch' after the split pos
1216 // (CatchAfterSplit == true), we should preserve the BB's property,
1217 // including that it is an EH pad, in the later part of the BB, where the
1218 // 'catch' is.
1219 bool CatchAfterSplit = false;
1220 if (EndBB->isEHPad()) {
1221 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
1222 I != E; ++I) {
1223 if (WebAssembly::isCatch(I->getOpcode())) {
1224 CatchAfterSplit = true;
1225 break;
1226 }
1227 }
1228 }
1229
1230 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
1231 if (!CatchAfterSplit) {
1232 // If the range's end instruction is in the middle of the BB, we split the
1233 // BB into two and insert the delegate BB in between.
1234 // - Before:
1235 // bb:
1236 // range_end
1237 // other_insts
1238 //
1239 // - After:
1240 // pre_bb: (previous 'bb')
1241 // range_end
1242 // delegate_bb: (new)
1243 // delegate
1244 // post_bb: (new)
1245 // other_insts
1246 PreBB = EndBB;
1247 PostBB = MF.CreateMachineBasicBlock();
1248 MF.insert(std::next(PreBB->getIterator()), PostBB);
1249 MF.insert(std::next(PreBB->getIterator()), DelegateBB);
1250 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
1251 PostBB->transferSuccessors(PreBB);
1252 } else {
1253 // - Before:
1254 // ehpad:
1255 // range_end
1256 // catch
1257 // ...
1258 //
1259 // - After:
1260 // pre_bb: (new)
1261 // range_end
1262 // delegate_bb: (new)
1263 // delegate
1264 // post_bb: (previous 'ehpad')
1265 // catch
1266 // ...
1267 assert(EndBB->isEHPad());
1268 PreBB = MF.CreateMachineBasicBlock();
1269 PostBB = EndBB;
1270 MF.insert(PostBB->getIterator(), PreBB);
1271 MF.insert(PostBB->getIterator(), DelegateBB);
1272 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
1273 // We don't need to transfer predecessors of the EH pad to 'PreBB',
1274 // because an EH pad's predecessors are all through unwind edges and they
1275 // should still unwind to the EH pad, not PreBB.
1276 }
1277 unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);
1278 PreBB->addSuccessor(DelegateBB);
1279 PreBB->addSuccessor(PostBB);
1280 }
1281
1282 // Add a 'delegate' instruction in the delegate BB created above.
1283 MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(),
1284 TII.get(WebAssembly::DELEGATE))
1285 .addMBB(UnwindDest);
1286 registerTryScope(Try, Delegate, nullptr);
1287}
1288
1289// Given an unwind destination, return a trampoline BB. A trampoline BB is a
1290// destination of a nested try_table inserted to fix an unwind mismatch. It
1291// contains an end_block, which is the target of the try_table, and a throw_ref,
1292// to rethrow the exception to the right try_table.
1293// try_table (catch ... )
1294// block exnref
1295// ...
1296// try_table (catch_all_ref N)
1297// some code
1298// end_try_table
1299// ...
1300// end_block ;; Trampoline BB
1301// throw_ref
1302// end_try_table
1304WebAssemblyCFGStackify::getTrampolineBlock(MachineBasicBlock *UnwindDest) {
1305 // We need one trampoline BB per unwind destination, even though there are
1306 // multiple try_tables target the same unwind destination. If we have already
1307 // created one for the given UnwindDest, return it.
1308 auto It = UnwindDestToTrampoline.find(UnwindDest);
1309 if (It != UnwindDestToTrampoline.end())
1310 return It->second;
1311
1312 auto &MF = *UnwindDest->getParent();
1313 auto &MRI = MF.getRegInfo();
1314 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1315
1316 MachineInstr *Block = nullptr;
1317 MachineBasicBlock *TrampolineBB = nullptr;
1318 DebugLoc EndDebugLoc;
1319
1320 if (UnwindDest == getFakeCallerBlock(MF)) {
1321 // If the unwind destination is the caller, create a caller-dedicated
1322 // trampoline BB at the end of the function and wrap the whole function with
1323 // a block.
1324 auto BeginPos = MF.begin()->begin();
1325 while (WebAssembly::isArgument(BeginPos->getOpcode()))
1326 BeginPos++;
1327 Block = BuildMI(*MF.begin(), BeginPos, MF.begin()->begin()->getDebugLoc(),
1328 TII.get(WebAssembly::BLOCK))
1329 .addImm(int64_t(WebAssembly::BlockType::Exnref));
1330 TrampolineBB = getCallerTrampolineBlock(MF);
1331 MachineBasicBlock *PrevBB = &*std::prev(CallerTrampolineBB->getIterator());
1332 EndDebugLoc = PrevBB->findPrevDebugLoc(PrevBB->end());
1333 } else {
1334 // If the unwind destination is another EH pad, create a trampoline BB for
1335 // the unwind dest and insert a block instruction right after the target
1336 // try_table.
1337 auto *TargetBeginTry = EHPadToTry[UnwindDest];
1338 auto *TargetEndTry = BeginToEnd[TargetBeginTry];
1339 auto *TargetBeginBB = TargetBeginTry->getParent();
1340 auto *TargetEndBB = TargetEndTry->getParent();
1341
1342 Block = BuildMI(*TargetBeginBB, std::next(TargetBeginTry->getIterator()),
1343 TargetBeginTry->getDebugLoc(), TII.get(WebAssembly::BLOCK))
1344 .addImm(int64_t(WebAssembly::BlockType::Exnref));
1345 TrampolineBB = MF.CreateMachineBasicBlock();
1346 EndDebugLoc = TargetEndTry->getDebugLoc();
1347 MF.insert(TargetEndBB->getIterator(), TrampolineBB);
1348 TrampolineBB->addSuccessor(UnwindDest);
1349 }
1350
1351 // Insert an end_block, catch_all_ref (pseudo instruction), and throw_ref
1352 // instructions in the trampoline BB.
1353 MachineInstr *EndBlock =
1354 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::END_BLOCK));
1355 auto ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);
1356 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::CATCH_ALL_REF))
1357 .addDef(ExnReg);
1358 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::THROW_REF))
1359 .addReg(ExnReg);
1360
1361 registerScope(Block, EndBlock);
1362 UnwindDestToTrampoline[UnwindDest] = TrampolineBB;
1363 return TrampolineBB;
1364}
1365
1366// Wrap the given range of instructions with a try_table-end_try_table that
1367// targets 'UnwindDest'. RangeBegin and RangeEnd are inclusive.
1368void WebAssemblyCFGStackify::addNestedTryTable(MachineInstr *RangeBegin,
1369 MachineInstr *RangeEnd,
1370 MachineBasicBlock *UnwindDest) {
1371 auto *BeginBB = RangeBegin->getParent();
1372 auto *EndBB = RangeEnd->getParent();
1373
1374 MachineFunction &MF = *BeginBB->getParent();
1375 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1376 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1377
1378 // Get the trampoline BB that the new try_table will unwind to.
1379 auto *TrampolineBB = getTrampolineBlock(UnwindDest);
1380
1381 // Local expression tree before the first call of this range should go
1382 // after the nested TRY_TABLE.
1384 AfterSet.insert(RangeBegin);
1385 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();
1386 I != E; --I) {
1387 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
1388 continue;
1389 if (WebAssembly::isChild(*std::prev(I), MFI))
1390 AfterSet.insert(&*std::prev(I));
1391 else
1392 break;
1393 }
1394
1395 // Create the nested try_table instruction.
1396 auto TryTablePos = getLatestInsertPos(
1397 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
1398 MachineInstr *TryTable =
1399 BuildMI(*BeginBB, TryTablePos, RangeBegin->getDebugLoc(),
1400 TII.get(WebAssembly::TRY_TABLE))
1401 .addImm(int64_t(WebAssembly::BlockType::Void))
1402 .addImm(1) // # of catch clauses
1404 .addMBB(TrampolineBB);
1405
1406 // Create a BB to insert the 'end_try_table' instruction.
1407 MachineBasicBlock *EndTryTableBB = MF.CreateMachineBasicBlock();
1408 EndTryTableBB->addSuccessor(TrampolineBB);
1409
1410 auto SplitPos = std::next(RangeEnd->getIterator());
1411 if (SplitPos == EndBB->end()) {
1412 // If the range's end instruction is at the end of the BB, insert the new
1413 // end_try_table BB after the current BB.
1414 MF.insert(std::next(EndBB->getIterator()), EndTryTableBB);
1415 EndBB->addSuccessor(EndTryTableBB);
1416
1417 } else {
1418 // When the split pos is in the middle of a BB, we split the BB into two and
1419 // put the 'end_try_table' BB in between. We normally create a split BB and
1420 // make it a successor of the original BB (CatchAfterSplit == false), but in
1421 // case the BB is an EH pad and there is a 'catch' after split pos
1422 // (CatchAfterSplit == true), we should preserve the BB's property,
1423 // including that it is an EH pad, in the later part of the BB, where the
1424 // 'catch' is.
1425 bool CatchAfterSplit = false;
1426 if (EndBB->isEHPad()) {
1427 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
1428 I != E; ++I) {
1429 if (WebAssembly::isCatch(I->getOpcode())) {
1430 CatchAfterSplit = true;
1431 break;
1432 }
1433 }
1434 }
1435
1436 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
1437 if (!CatchAfterSplit) {
1438 // If the range's end instruction is in the middle of the BB, we split the
1439 // BB into two and insert the end_try_table BB in between.
1440 // - Before:
1441 // bb:
1442 // range_end
1443 // other_insts
1444 //
1445 // - After:
1446 // pre_bb: (previous 'bb')
1447 // range_end
1448 // end_try_table_bb: (new)
1449 // end_try_table
1450 // post_bb: (new)
1451 // other_insts
1452 PreBB = EndBB;
1453 PostBB = MF.CreateMachineBasicBlock();
1454 MF.insert(std::next(PreBB->getIterator()), PostBB);
1455 MF.insert(std::next(PreBB->getIterator()), EndTryTableBB);
1456 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
1457 PostBB->transferSuccessors(PreBB);
1458 } else {
1459 // - Before:
1460 // ehpad:
1461 // range_end
1462 // catch
1463 // ...
1464 //
1465 // - After:
1466 // pre_bb: (new)
1467 // range_end
1468 // end_try_table: (new)
1469 // end_try_table
1470 // post_bb: (previous 'ehpad')
1471 // catch
1472 // ...
1473 assert(EndBB->isEHPad());
1474 PreBB = MF.CreateMachineBasicBlock();
1475 PostBB = EndBB;
1476 MF.insert(PostBB->getIterator(), PreBB);
1477 MF.insert(PostBB->getIterator(), EndTryTableBB);
1478 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
1479 // We don't need to transfer predecessors of the EH pad to 'PreBB',
1480 // because an EH pad's predecessors are all through unwind edges and they
1481 // should still unwind to the EH pad, not PreBB.
1482 }
1483 unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);
1484 PreBB->addSuccessor(EndTryTableBB);
1485 PreBB->addSuccessor(PostBB);
1486 }
1487
1488 // Add a 'end_try_table' instruction in the EndTryTable BB created above.
1489 MachineInstr *EndTryTable = BuildMI(EndTryTableBB, RangeEnd->getDebugLoc(),
1490 TII.get(WebAssembly::END_TRY_TABLE));
1491 registerTryScope(TryTable, EndTryTable, nullptr);
1492}
1493
1494// In the standard (exnref) EH, we fix unwind mismatches by adding a new
1495// block~end_block inside of the unwind destination try_table~end_try_table:
1496// try_table ...
1497// block exnref ;; (new)
1498// ...
1499// try_table (catch_all_ref N) ;; (new) to trampoline BB
1500// code
1501// end_try_table ;; (new)
1502// ...
1503// end_block ;; (new) trampoline BB
1504// throw_ref ;; (new)
1505// end_try_table
1506//
1507// To do this, we will create a new BB that will contain the new 'end_block' and
1508// 'throw_ref' and insert it before the 'end_try_table' BB.
1509//
1510// But there are cases when there are 'end_loop'(s) before the 'end_try_table'
1511// in the same BB. (There can't be 'end_block' before 'end_try_table' in the
1512// same BB because EH pads can't be directly branched to.) Then after fixing
1513// unwind mismatches this will create the mismatching markers like below:
1514// bb0:
1515// try_table
1516// block exnref
1517// ...
1518// loop
1519// ...
1520// new_bb:
1521// end_block
1522// end_try_table_bb:
1523// end_loop
1524// end_try_table
1525//
1526// So if the unwind dest BB has a end_loop before an end_try_table, we split the
1527// BB with the end_loop as a separate BB before the end_try_table BB, so that
1528// after we fix the unwind mismatch, the code will be like:
1529// bb0:
1530// try_table
1531// block exnref
1532// ...
1533// loop
1534// ...
1535// end_loop_bb:
1536// end_loop
1537// new_bb:
1538// end_block
1539// end_try_table_bb:
1540// end_try_table
1541static void splitEndLoopBB(MachineBasicBlock *UnwindDest) {
1542 auto &MF = *UnwindDest->getParent();
1543 MachineInstr *EndTryTable = nullptr, *EndLoop = nullptr;
1544 for (auto &MI : reverse(*UnwindDest)) {
1545 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE) {
1546 EndTryTable = &MI;
1547 continue;
1548 }
1549 if (EndTryTable && MI.getOpcode() == WebAssembly::END_LOOP) {
1550 EndLoop = &MI;
1551 break;
1552 }
1553 }
1554 if (!EndLoop)
1555 return;
1556
1557 auto *EndLoopBB = MF.CreateMachineBasicBlock();
1558 MF.insert(UnwindDest->getIterator(), EndLoopBB);
1559 auto SplitPos = std::next(EndLoop->getIterator());
1560 EndLoopBB->splice(EndLoopBB->end(), UnwindDest, UnwindDest->begin(),
1561 SplitPos);
1562 EndLoopBB->addSuccessor(UnwindDest);
1563}
1564
1565bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {
1566 // This function is used for both the legacy EH and the standard (exnref) EH,
1567 // and the reason we have unwind mismatches is the same for the both of them,
1568 // but the code examples in the comments are going to be different. To make
1569 // the description less confusing, we write the basically same comments twice,
1570 // once for the legacy EH and the standard EH.
1571 //
1572 // -- Legacy EH --------------------------------------------------------------
1573 //
1574 // Linearizing the control flow by placing TRY / END_TRY markers can create
1575 // mismatches in unwind destinations for throwing instructions, such as calls.
1576 //
1577 // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate'
1578 // instruction delegates an exception to an outer 'catch'. It can target not
1579 // only 'catch' but all block-like structures including another 'delegate',
1580 // but with slightly different semantics than branches. When it targets a
1581 // 'catch', it will delegate the exception to that catch. It is being
1582 // discussed how to define the semantics when 'delegate''s target is a non-try
1583 // block: it will either be a validation failure or it will target the next
1584 // outer try-catch. But anyway our LLVM backend currently does not generate
1585 // such code. The example below illustrates where the 'delegate' instruction
1586 // in the middle will delegate the exception to, depending on the value of N.
1587 // try
1588 // try
1589 // block
1590 // try
1591 // try
1592 // call @foo
1593 // delegate N ;; Where will this delegate to?
1594 // catch ;; N == 0
1595 // end
1596 // end ;; N == 1 (invalid; will not be generated)
1597 // delegate ;; N == 2
1598 // catch ;; N == 3
1599 // end
1600 // ;; N == 4 (to caller)
1601 //
1602 // 1. When an instruction may throw, but the EH pad it will unwind to can be
1603 // different from the original CFG.
1604 //
1605 // Example: we have the following CFG:
1606 // bb0:
1607 // call @foo ; if it throws, unwind to bb2
1608 // bb1:
1609 // call @bar ; if it throws, unwind to bb3
1610 // bb2 (ehpad):
1611 // catch
1612 // ...
1613 // bb3 (ehpad)
1614 // catch
1615 // ...
1616 //
1617 // And the CFG is sorted in this order. Then after placing TRY markers, it
1618 // will look like: (BB markers are omitted)
1619 // try
1620 // try
1621 // call @foo
1622 // call @bar ;; if it throws, unwind to bb3
1623 // catch ;; ehpad (bb2)
1624 // ...
1625 // end_try
1626 // catch ;; ehpad (bb3)
1627 // ...
1628 // end_try
1629 //
1630 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is
1631 // supposed to end up. We solve this problem by wrapping the mismatching call
1632 // with an inner try-delegate that rethrows the exception to the right
1633 // 'catch'.
1634 //
1635 // try
1636 // try
1637 // call @foo
1638 // try ;; (new)
1639 // call @bar
1640 // delegate 1 (bb3) ;; (new)
1641 // catch ;; ehpad (bb2)
1642 // ...
1643 // end_try
1644 // catch ;; ehpad (bb3)
1645 // ...
1646 // end_try
1647 //
1648 // ---
1649 // 2. The same as 1, but in this case an instruction unwinds to a caller
1650 // function and not another EH pad.
1651 //
1652 // Example: we have the following CFG:
1653 // bb0:
1654 // call @foo ; if it throws, unwind to bb2
1655 // bb1:
1656 // call @bar ; if it throws, unwind to caller
1657 // bb2 (ehpad):
1658 // catch
1659 // ...
1660 //
1661 // And the CFG is sorted in this order. Then after placing TRY markers, it
1662 // will look like:
1663 // try
1664 // call @foo
1665 // call @bar ;; if it throws, unwind to caller
1666 // catch ;; ehpad (bb2)
1667 // ...
1668 // end_try
1669 //
1670 // Now if bar() throws, it is going to end up in bb2, when it is supposed
1671 // throw up to the caller. We solve this problem in the same way, but in this
1672 // case 'delegate's immediate argument is the number of block depths + 1,
1673 // which means it rethrows to the caller.
1674 // try
1675 // call @foo
1676 // try ;; (new)
1677 // call @bar
1678 // delegate 1 (caller) ;; (new)
1679 // catch ;; ehpad (bb2)
1680 // ...
1681 // end_try
1682 //
1683 // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the
1684 // caller, it will take a fake BB generated by getFakeCallerBlock(), which
1685 // will be converted to a correct immediate argument later.
1686 //
1687 // In case there are multiple calls in a BB that may throw to the caller, they
1688 // can be wrapped together in one nested try-delegate scope. (In 1, this
1689 // couldn't happen, because may-throwing instruction there had an unwind
1690 // destination, i.e., it was an invoke before, and there could be only one
1691 // invoke within a BB.)
1692 //
1693 // -- Standard EH ------------------------------------------------------------
1694 //
1695 // Linearizing the control flow by placing TRY / END_TRY_TABLE markers can
1696 // create mismatches in unwind destinations for throwing instructions, such as
1697 // calls.
1698 //
1699 // We use the a nested 'try_table'~'end_try_table' instruction to fix the
1700 // unwind mismatches. try_table's catch clauses take an immediate argument
1701 // that specifics which block we should branch to.
1702 //
1703 // 1. When an instruction may throw, but the EH pad it will unwind to can be
1704 // different from the original CFG.
1705 //
1706 // Example: we have the following CFG:
1707 // bb0:
1708 // call @foo ; if it throws, unwind to bb2
1709 // bb1:
1710 // call @bar ; if it throws, unwind to bb3
1711 // bb2 (ehpad):
1712 // catch
1713 // ...
1714 // bb3 (ehpad)
1715 // catch
1716 // ...
1717 //
1718 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers
1719 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:
1720 // (BB markers are omitted)
1721 // block
1722 // try_table (catch ... 0)
1723 // block
1724 // try_table (catch ... 0)
1725 // call @foo
1726 // call @bar ;; if it throws, unwind to bb3
1727 // end_try_table
1728 // end_block ;; ehpad (bb2)
1729 // ...
1730 // end_try_table
1731 // end_block ;; ehpad (bb3)
1732 // ...
1733 //
1734 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is
1735 // supposed to end up. We solve this problem by wrapping the mismatching call
1736 // with an inner try_table~end_try_table that sends the exception to the the
1737 // 'trampoline' block, which rethrows, or 'bounces' it to the right
1738 // end_try_table:
1739 // block
1740 // try_table (catch ... 0)
1741 // block exnref ;; (new)
1742 // block
1743 // try_table (catch ... 0)
1744 // call @foo
1745 // try_table (catch_all_ref 2) ;; (new) to trampoline BB
1746 // call @bar
1747 // end_try_table ;; (new)
1748 // end_try_table
1749 // end_block ;; ehpad (bb2)
1750 // ...
1751 // end_block ;; (new) trampoline BB
1752 // throw_ref ;; (new)
1753 // end_try_table
1754 // end_block ;; ehpad (bb3)
1755 //
1756 // ---
1757 // 2. The same as 1, but in this case an instruction unwinds to a caller
1758 // function and not another EH pad.
1759 //
1760 // Example: we have the following CFG:
1761 // bb0:
1762 // call @foo ; if it throws, unwind to bb2
1763 // bb1:
1764 // call @bar ; if it throws, unwind to caller
1765 // bb2 (ehpad):
1766 // catch
1767 // ...
1768 //
1769 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers
1770 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:
1771 // block
1772 // try_table (catch ... 0)
1773 // call @foo
1774 // call @bar ;; if it throws, unwind to caller
1775 // end_try_table
1776 // end_block ;; ehpad (bb2)
1777 // ...
1778 //
1779 // Now if bar() throws, it is going to end up in bb2, when it is supposed
1780 // throw up to the caller. We solve this problem in the same way, but in this
1781 // case 'delegate's immediate argument is the number of block depths + 1,
1782 // which means it rethrows to the caller.
1783 // block exnref ;; (new)
1784 // block
1785 // try_table (catch ... 0)
1786 // call @foo
1787 // try_table (catch_all_ref 2) ;; (new) to trampoline BB
1788 // call @bar
1789 // end_try_table ;; (new)
1790 // end_try_table
1791 // end_block ;; ehpad (bb2)
1792 // ...
1793 // end_block ;; (new) caller trampoline BB
1794 // throw_ref ;; (new) throw to the caller
1795 //
1796 // Before rewriteDepthImmediates, try_table's catch clauses' argument is a
1797 // trampoline BB from which we throw_ref the exception to the right
1798 // end_try_table. In case of the caller, it will take a new caller-dedicated
1799 // trampoline BB generated by getCallerTrampolineBlock(), which throws the
1800 // exception to the caller.
1801 //
1802 // In case there are multiple calls in a BB that may throw to the caller, they
1803 // can be wrapped together in one nested try_table-end_try_table scope. (In 1,
1804 // this couldn't happen, because may-throwing instruction there had an unwind
1805 // destination, i.e., it was an invoke before, and there could be only one
1806 // invoke within a BB.)
1807
1809 // Range of intructions to be wrapped in a new nested try~delegate or
1810 // try_table~end_try_table. A range exists in a single BB and does not span
1811 // multiple BBs.
1812 using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1813 // In original CFG, <unwind destination BB, a vector of try/try_table ranges>
1815
1816 // Gather possibly throwing calls (i.e., previously invokes) whose current
1817 // unwind destination is not the same as the original CFG. (Case 1)
1818
1819 for (auto &MBB : reverse(MF)) {
1820 bool SeenThrowableInstInBB = false;
1821 for (auto &MI : reverse(MBB)) {
1822 if (WebAssembly::isTry(MI.getOpcode()))
1823 EHPadStack.pop_back();
1824 else if (WebAssembly::isCatch(MI.getOpcode()))
1825 EHPadStack.push_back(MI.getParent());
1826
1827 // In this loop we only gather calls that have an EH pad to unwind. So
1828 // there will be at most 1 such call (= invoke) in a BB, so after we've
1829 // seen one, we can skip the rest of BB. Also if MBB has no EH pad
1830 // successor or MI does not throw, this is not an invoke.
1831 if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
1833 continue;
1834 SeenThrowableInstInBB = true;
1835
1836 // If the EH pad on the stack top is where this instruction should unwind
1837 // next, we're good.
1838 MachineBasicBlock *UnwindDest = getFakeCallerBlock(MF);
1839 for (auto *Succ : MBB.successors()) {
1840 // Even though semantically a BB can have multiple successors in case an
1841 // exception is not caught by a catchpad, in our backend implementation
1842 // it is guaranteed that a BB can have at most one EH pad successor. For
1843 // details, refer to comments in findWasmUnwindDestinations function in
1844 // SelectionDAGBuilder.cpp.
1845 if (Succ->isEHPad()) {
1846 UnwindDest = Succ;
1847 break;
1848 }
1849 }
1850 if (EHPadStack.back() == UnwindDest)
1851 continue;
1852
1853 // Include EH_LABELs in the range before and after the invoke
1854 MachineInstr *RangeBegin = &MI, *RangeEnd = &MI;
1855 if (RangeBegin->getIterator() != MBB.begin() &&
1856 std::prev(RangeBegin->getIterator())->isEHLabel())
1857 RangeBegin = &*std::prev(RangeBegin->getIterator());
1858 if (std::next(RangeEnd->getIterator()) != MBB.end() &&
1859 std::next(RangeEnd->getIterator())->isEHLabel())
1860 RangeEnd = &*std::next(RangeEnd->getIterator());
1861
1862 // If not, record the range.
1863 UnwindDestToTryRanges[UnwindDest].push_back(
1864 TryRange(RangeBegin, RangeEnd));
1865 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName()
1866 << "\nCall = " << MI
1867 << "\nOriginal dest = " << UnwindDest->getName()
1868 << " Current dest = " << EHPadStack.back()->getName()
1869 << "\n\n");
1870 }
1871 }
1872
1873 assert(EHPadStack.empty());
1874
1875 // Gather possibly throwing calls that are supposed to unwind up to the caller
1876 // if they throw, but currently unwind to an incorrect destination. Unlike the
1877 // loop above, there can be multiple calls within a BB that unwind to the
1878 // caller, which we should group together in a range. (Case 2)
1879
1880 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
1881
1882 // Record the range.
1883 auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) {
1884 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1885 TryRange(RangeBegin, RangeEnd));
1886 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "
1887 << RangeBegin->getParent()->getName()
1888 << "\nRange begin = " << *RangeBegin
1889 << "Range end = " << *RangeEnd
1890 << "\nOriginal dest = caller Current dest = "
1891 << CurrentDest->getName() << "\n\n");
1892 RangeBegin = RangeEnd = nullptr; // Reset range pointers
1893 };
1894
1895 for (auto &MBB : reverse(MF)) {
1896 bool SeenThrowableInstInBB = false;
1897 for (auto &MI : reverse(MBB)) {
1898 bool MayThrow = WebAssembly::mayThrow(MI);
1899
1900 // If MBB has an EH pad successor and this is the last instruction that
1901 // may throw, this instruction unwinds to the EH pad and not to the
1902 // caller.
1903 if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB)
1904 SeenThrowableInstInBB = true;
1905
1906 // We wrap up the current range when we see a marker even if we haven't
1907 // finished a BB.
1908 else if (RangeEnd && WebAssembly::isMarker(MI.getOpcode()))
1909 RecordCallerMismatchRange(EHPadStack.back());
1910
1911 // If EHPadStack is empty, that means it correctly unwinds to the caller
1912 // if it throws, so we're good. If MI does not throw, we're good too.
1913 else if (EHPadStack.empty() || !MayThrow) {
1914 }
1915
1916 // We found an instruction that unwinds to the caller but currently has an
1917 // incorrect unwind destination. Create a new range or increment the
1918 // currently existing range.
1919 else {
1920 if (!RangeEnd)
1921 RangeBegin = RangeEnd = &MI;
1922 else
1923 RangeBegin = &MI;
1924 }
1925
1926 // Update EHPadStack.
1927 if (WebAssembly::isTry(MI.getOpcode()))
1928 EHPadStack.pop_back();
1929 else if (WebAssembly::isCatch(MI.getOpcode()))
1930 EHPadStack.push_back(MI.getParent());
1931 }
1932
1933 if (RangeEnd)
1934 RecordCallerMismatchRange(EHPadStack.back());
1935 }
1936
1937 assert(EHPadStack.empty());
1938
1939 // We don't have any unwind destination mismatches to resolve.
1940 if (UnwindDestToTryRanges.empty())
1941 return false;
1942
1943 // When end_loop is before end_try_table within the same BB in unwind
1944 // destinations, we should split the end_loop into another BB.
1946 for (auto &[UnwindDest, _] : UnwindDestToTryRanges)
1947 splitEndLoopBB(UnwindDest);
1948
1949 // Now we fix the mismatches by wrapping calls with inner try-delegates.
1950 for (auto &P : UnwindDestToTryRanges) {
1951 NumCallUnwindMismatches += P.second.size();
1952 MachineBasicBlock *UnwindDest = P.first;
1953 auto &TryRanges = P.second;
1954
1955 for (auto Range : TryRanges) {
1956 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1957 std::tie(RangeBegin, RangeEnd) = Range;
1958 auto *MBB = RangeBegin->getParent();
1959
1960 // If this BB has an EH pad successor, i.e., ends with an 'invoke', and if
1961 // the current range contains the invoke, now we are going to wrap the
1962 // invoke with try-delegate or try_table-end_try_table, making the
1963 // 'delegate' or 'end_try_table' BB the new successor instead, so remove
1964 // the EH pad succesor here. The BB may not have an EH pad successor if
1965 // calls in this BB throw to the caller.
1966 if (UnwindDest != getFakeCallerBlock(MF)) {
1967 MachineBasicBlock *EHPad = nullptr;
1968 for (auto *Succ : MBB->successors()) {
1969 if (Succ->isEHPad()) {
1970 EHPad = Succ;
1971 break;
1972 }
1973 }
1974 if (EHPad)
1975 MBB->removeSuccessor(EHPad);
1976 }
1977
1979 addNestedTryTable(RangeBegin, RangeEnd, UnwindDest);
1980 else
1981 addNestedTryDelegate(RangeBegin, RangeEnd, UnwindDest);
1982 }
1983 }
1984
1985 return true;
1986}
1987
1988// Returns the single destination of try_table, if there is one. All try_table
1989// we generate in this pass has a single destination, i.e., a single catch
1990// clause.
1992 if (TryTable->getOperand(1).getImm() != 1)
1993 return nullptr;
1994 switch (TryTable->getOperand(2).getImm()) {
1997 return TryTable->getOperand(4).getMBB();
2000 return TryTable->getOperand(3).getMBB();
2001 default:
2002 llvm_unreachable("try_table: Invalid catch clause\n");
2003 }
2004}
2005
2006bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {
2007 // This function is used for both the legacy EH and the standard (exnref) EH,
2008 // and the reason we have unwind mismatches is the same for the both of them,
2009 // but the code examples in the comments are going to be different. To make
2010 // the description less confusing, we write the basically same comments twice,
2011 // once for the legacy EH and the standard EH.
2012 //
2013 // -- Legacy EH --------------------------------------------------------------
2014 //
2015 // There is another kind of unwind destination mismatches besides call unwind
2016 // mismatches, which we will call "catch unwind mismatches". See this example
2017 // after the marker placement:
2018 // try
2019 // try
2020 // call @foo
2021 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
2022 // ...
2023 // end_try
2024 // catch_all ;; ehpad B
2025 // ...
2026 // end_try
2027 //
2028 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
2029 // throws a foreign exception that is not caught by ehpad A, and its next
2030 // destination should be the caller. But after control flow linearization,
2031 // another EH pad can be placed in between (e.g. ehpad B here), making the
2032 // next unwind destination incorrect. In this case, the foreign exception will
2033 // instead go to ehpad B and will be caught there instead. In this example the
2034 // correct next unwind destination is the caller, but it can be another outer
2035 // catch in other cases.
2036 //
2037 // There is no specific 'call' or 'throw' instruction to wrap with a
2038 // try-delegate, so we wrap the whole try-catch-end with a try-delegate and
2039 // make it rethrow to the right destination, which is the caller in the
2040 // example below:
2041 // try
2042 // try ;; (new)
2043 // try
2044 // call @foo
2045 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
2046 // ...
2047 // end_try
2048 // delegate 1 (caller) ;; (new)
2049 // catch_all ;; ehpad B
2050 // ...
2051 // end_try
2052 //
2053 // The right destination may be another EH pad or the caller. (The example
2054 // here shows the case it is the caller.)
2055 //
2056 // -- Standard EH ------------------------------------------------------------
2057 //
2058 // There is another kind of unwind destination mismatches besides call unwind
2059 // mismatches, which we will call "catch unwind mismatches". See this example
2060 // after the marker placement:
2061 // block
2062 // try_table (catch_all_ref 0)
2063 // block
2064 // try_table (catch ... 0)
2065 // call @foo
2066 // end_try_table
2067 // end_block ;; ehpad A (next unwind dest: caller)
2068 // ...
2069 // end_try_table
2070 // end_block ;; ehpad B
2071 // ...
2072 //
2073 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
2074 // throws a foreign exception that is not caught by ehpad A, and its next
2075 // destination should be the caller. But after control flow linearization,
2076 // another EH pad can be placed in between (e.g. ehpad B here), making the
2077 // next unwind destination incorrect. In this case, the foreign exception will
2078 // instead go to ehpad B and will be caught there instead. In this example the
2079 // correct next unwind destination is the caller, but it can be another outer
2080 // catch in other cases.
2081 //
2082 // There is no specific 'call' or 'throw' instruction to wrap with an inner
2083 // try_table-end_try_table, so we wrap the whole try_table-end_try_table with
2084 // an inner try_table-end_try_table that sends the exception to a trampoline
2085 // BB. We rethrow the sent exception using a throw_ref to the right
2086 // destination, which is the caller in the example below:
2087 // block exnref
2088 // block
2089 // try_table (catch_all_ref 0)
2090 // try_table (catch_all_ref 2) ;; (new) to trampoline
2091 // block
2092 // try_table (catch ... 0)
2093 // call @foo
2094 // end_try_table
2095 // end_block ;; ehpad A (next unwind dest: caller)
2096 // end_try_table ;; (new)
2097 // ...
2098 // end_try_table
2099 // end_block ;; ehpad B
2100 // ...
2101 // end_block ;; (new) caller trampoline BB
2102 // throw_ref ;; (new) throw to the caller
2103 //
2104 // The right destination may be another EH pad or the caller. (The example
2105 // here shows the case it is the caller.)
2106
2107 const auto *EHInfo = MF.getWasmEHFuncInfo();
2108 assert(EHInfo);
2110 // For EH pads that have catch unwind mismatches, a map of <EH pad, its
2111 // correct unwind destination>.
2113
2114 for (auto &MBB : reverse(MF)) {
2115 for (auto &MI : reverse(MBB)) {
2116 if (MI.getOpcode() == WebAssembly::TRY)
2117 EHPadStack.pop_back();
2118 else if (MI.getOpcode() == WebAssembly::TRY_TABLE) {
2119 // We want to exclude try_tables created in fixCallUnwindMismatches.
2120 // Check if the try_table's unwind destination matches the EH pad stack
2121 // top. If it is created in fixCallUnwindMismatches, it wouldn't.
2122 if (getSingleUnwindDest(&MI) == EHPadStack.back())
2123 EHPadStack.pop_back();
2124 } else if (MI.getOpcode() == WebAssembly::DELEGATE)
2125 EHPadStack.push_back(&MBB);
2126 else if (WebAssembly::isCatch(MI.getOpcode())) {
2127 auto *EHPad = &MBB;
2128
2129 // If the BB has a catch pseudo instruction but is not marked as an EH
2130 // pad, it's a trampoline BB we created in fixCallUnwindMismatches. Skip
2131 // it.
2132 if (!EHPad->isEHPad())
2133 continue;
2134
2135 // catch_all always catches an exception, so we don't need to do
2136 // anything
2137 if (WebAssembly::isCatchAll(MI.getOpcode())) {
2138 }
2139
2140 // This can happen when the unwind dest was removed during the
2141 // optimization, e.g. because it was unreachable.
2142 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
2143 LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName()
2144 << "'s unwind destination does not exist anymore"
2145 << "\n\n");
2146 }
2147
2148 // The EHPad's next unwind destination is the caller, but we incorrectly
2149 // unwind to another EH pad.
2150 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) {
2151 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
2153 << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()
2154 << " Original dest = caller Current dest = "
2155 << EHPadStack.back()->getName() << "\n\n");
2156 }
2157
2158 // The EHPad's next unwind destination is an EH pad, whereas we
2159 // incorrectly unwind to another EH pad.
2160 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
2161 auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
2162 if (EHPadStack.back() != UnwindDest) {
2163 EHPadToUnwindDest[EHPad] = UnwindDest;
2164 LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "
2165 << EHPad->getName() << " Original dest = "
2166 << UnwindDest->getName() << " Current dest = "
2167 << EHPadStack.back()->getName() << "\n\n");
2168 }
2169 }
2170
2171 EHPadStack.push_back(EHPad);
2172 }
2173 }
2174 }
2175
2176 assert(EHPadStack.empty());
2177 if (EHPadToUnwindDest.empty())
2178 return false;
2179
2180 // When end_loop is before end_try_table within the same BB in unwind
2181 // destinations, we should split the end_loop into another BB.
2182 for (auto &[_, UnwindDest] : EHPadToUnwindDest)
2183 splitEndLoopBB(UnwindDest);
2184
2185 NumCatchUnwindMismatches += EHPadToUnwindDest.size();
2187
2188 for (auto &[EHPad, UnwindDest] : EHPadToUnwindDest) {
2189 MachineInstr *Try = EHPadToTry[EHPad];
2190 MachineInstr *EndTry = BeginToEnd[Try];
2192 addNestedTryTable(Try, EndTry, UnwindDest);
2193 } else {
2194 addNestedTryDelegate(Try, EndTry, UnwindDest);
2195 NewEndTryBBs.insert(EndTry->getParent());
2196 }
2197 }
2198
2200 return true;
2201
2202 // Adding a try-delegate wrapping an existing try-catch-end can make existing
2203 // branch destination BBs invalid. For example,
2204 //
2205 // - Before:
2206 // bb0:
2207 // block
2208 // br bb3
2209 // bb1:
2210 // try
2211 // ...
2212 // bb2: (ehpad)
2213 // catch
2214 // bb3:
2215 // end_try
2216 // end_block ;; 'br bb3' targets here
2217 //
2218 // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap
2219 // this with a try-delegate. Then this becomes:
2220 //
2221 // - After:
2222 // bb0:
2223 // block
2224 // br bb3 ;; invalid destination!
2225 // bb1:
2226 // try ;; (new instruction)
2227 // try
2228 // ...
2229 // bb2: (ehpad)
2230 // catch
2231 // bb3:
2232 // end_try ;; 'br bb3' still incorrectly targets here!
2233 // delegate_bb: ;; (new BB)
2234 // delegate ;; (new instruction)
2235 // split_bb: ;; (new BB)
2236 // end_block
2237 //
2238 // Now 'br bb3' incorrectly branches to an inner scope.
2239 //
2240 // As we can see in this case, when branches target a BB that has both
2241 // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we
2242 // have to remap existing branch destinations so that they target not the
2243 // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's
2244 // in between, so we try to find the next BB with 'end_block' instruction. In
2245 // this example, the 'br bb3' instruction should be remapped to 'br split_bb'.
2246 for (auto &MBB : MF) {
2247 for (auto &MI : MBB) {
2248 if (MI.isTerminator()) {
2249 for (auto &MO : MI.operands()) {
2250 if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) {
2251 auto *BrDest = MO.getMBB();
2252 bool FoundEndBlock = false;
2253 for (; std::next(BrDest->getIterator()) != MF.end();
2254 BrDest = BrDest->getNextNode()) {
2255 for (const auto &MI : *BrDest) {
2256 if (MI.getOpcode() == WebAssembly::END_BLOCK) {
2257 FoundEndBlock = true;
2258 break;
2259 }
2260 }
2261 if (FoundEndBlock)
2262 break;
2263 }
2264 assert(FoundEndBlock);
2265 MO.setMBB(BrDest);
2266 }
2267 }
2268 }
2269 }
2270 }
2271
2272 return true;
2273}
2274
2275void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {
2276 // Renumber BBs and recalculate ScopeTop info because new BBs might have been
2277 // created and inserted during fixing unwind mismatches.
2278 MF.RenumberBlocks();
2279 MDT->updateBlockNumbers();
2280 ScopeTops.clear();
2281 ScopeTops.resize(MF.getNumBlockIDs());
2282 for (auto &MBB : reverse(MF)) {
2283 for (auto &MI : reverse(MBB)) {
2284 if (ScopeTops[MBB.getNumber()])
2285 break;
2286 switch (MI.getOpcode()) {
2287 case WebAssembly::END_BLOCK:
2288 case WebAssembly::END_LOOP:
2289 case WebAssembly::END_TRY:
2290 case WebAssembly::END_TRY_TABLE:
2291 case WebAssembly::DELEGATE:
2292 updateScopeTops(EndToBegin[&MI]->getParent(), &MBB);
2293 break;
2294 case WebAssembly::CATCH_LEGACY:
2295 case WebAssembly::CATCH_ALL_LEGACY:
2296 updateScopeTops(EHPadToTry[&MBB]->getParent(), &MBB);
2297 break;
2298 }
2299 }
2300 }
2301}
2302
2303/// In normal assembly languages, when the end of a function is unreachable,
2304/// because the function ends in an infinite loop or a noreturn call or similar,
2305/// it isn't necessary to worry about the function return type at the end of
2306/// the function, because it's never reached. However, in WebAssembly, blocks
2307/// that end at the function end need to have a return type signature that
2308/// matches the function signature, even though it's unreachable. This function
2309/// checks for such cases and fixes up the signatures.
2310void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
2311 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
2312
2313 if (MFI.getResults().empty())
2314 return;
2315
2316 // MCInstLower will add the proper types to multivalue signatures based on the
2317 // function return type
2318 WebAssembly::BlockType RetType =
2319 MFI.getResults().size() > 1
2320 ? WebAssembly::BlockType::Multivalue
2322 WebAssembly::toValType(MFI.getResults().front()));
2323
2325 Worklist.push_back(MF.rbegin()->rbegin());
2326
2328 auto *MBB = It->getParent();
2329 while (It != MBB->rend()) {
2330 MachineInstr &MI = *It++;
2331 if (MI.isPosition() || MI.isDebugInstr())
2332 continue;
2333 switch (MI.getOpcode()) {
2334 case WebAssembly::END_TRY: {
2335 // If a 'try''s return type is fixed, both its try body and catch body
2336 // should satisfy the return type, so we need to search 'end'
2337 // instructions before its corresponding 'catch' too.
2338 auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]);
2339 assert(EHPad);
2340 auto NextIt =
2341 std::next(WebAssembly::findCatch(EHPad)->getReverseIterator());
2342 if (NextIt != EHPad->rend())
2343 Worklist.push_back(NextIt);
2344 [[fallthrough]];
2345 }
2346 case WebAssembly::END_BLOCK:
2347 case WebAssembly::END_LOOP:
2348 case WebAssembly::END_TRY_TABLE:
2349 case WebAssembly::DELEGATE:
2350 EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
2351 continue;
2352 default:
2353 // Something other than an `end`. We're done for this BB.
2354 return;
2355 }
2356 }
2357 // We've reached the beginning of a BB. Continue the search in the previous
2358 // BB.
2359 Worklist.push_back(MBB->getPrevNode()->rbegin());
2360 };
2361
2362 while (!Worklist.empty())
2363 Process(Worklist.pop_back_val());
2364}
2365
2366// WebAssembly functions end with an end instruction, as if the function body
2367// were a block.
2369 const WebAssemblyInstrInfo &TII) {
2370 BuildMI(MF.back(), MF.back().end(),
2371 MF.back().findPrevDebugLoc(MF.back().end()),
2372 TII.get(WebAssembly::END_FUNCTION));
2373}
2374
2375/// Insert BLOCK/LOOP/TRY/TRY_TABLE markers at appropriate places.
2376void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
2377 // We allocate one more than the number of blocks in the function to
2378 // accommodate for the possible fake block we may insert at the end.
2379 ScopeTops.resize(MF.getNumBlockIDs() + 1);
2380 // Place the LOOP for MBB if MBB is the header of a loop.
2381 for (auto &MBB : MF)
2382 placeLoopMarker(MBB);
2383
2384 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
2385 for (auto &MBB : MF) {
2386 if (MBB.isEHPad()) {
2387 // Place the TRY/TRY_TABLE for MBB if MBB is the EH pad of an exception.
2388 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2389 MF.getFunction().hasPersonalityFn()) {
2391 placeTryTableMarker(MBB);
2392 else
2393 placeTryMarker(MBB);
2394 }
2395 } else {
2396 // Place the BLOCK for MBB if MBB is branched to from above.
2397 placeBlockMarker(MBB);
2398 }
2399 }
2400
2401 // Fix mismatches in unwind destinations induced by linearizing the code.
2402 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2403 MF.getFunction().hasPersonalityFn()) {
2404 bool MismatchFixed = fixCallUnwindMismatches(MF);
2405 MismatchFixed |= fixCatchUnwindMismatches(MF);
2406 if (MismatchFixed)
2407 recalculateScopeTops(MF);
2408 }
2409}
2410
2411unsigned WebAssemblyCFGStackify::getBranchDepth(
2413 unsigned Depth = 0;
2414 for (auto X : reverse(Stack)) {
2415 if (X.first == MBB)
2416 break;
2417 ++Depth;
2418 }
2419 assert(Depth < Stack.size() && "Branch destination should be in scope");
2420 return Depth;
2421}
2422
2423unsigned WebAssemblyCFGStackify::getDelegateDepth(
2425 if (MBB == FakeCallerBB)
2426 return Stack.size();
2427 // Delegate's destination is either a catch or a another delegate BB. When the
2428 // destination is another delegate, we can compute the argument in the same
2429 // way as branches, because the target delegate BB only contains the single
2430 // delegate instruction.
2431 if (!MBB->isEHPad()) // Target is a delegate BB
2432 return getBranchDepth(Stack, MBB);
2433
2434 // When the delegate's destination is a catch BB, we need to use its
2435 // corresponding try's end_try BB because Stack contains each marker's end BB.
2436 // Also we need to check if the end marker instruction matches, because a
2437 // single BB can contain multiple end markers, like this:
2438 // bb:
2439 // END_BLOCK
2440 // END_TRY
2441 // END_BLOCK
2442 // END_TRY
2443 // ...
2444 //
2445 // In case of branches getting the immediate that targets any of these is
2446 // fine, but delegate has to exactly target the correct try.
2447 unsigned Depth = 0;
2448 const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];
2449 for (auto X : reverse(Stack)) {
2450 if (X.first == EndTry->getParent() && X.second == EndTry)
2451 break;
2452 ++Depth;
2453 }
2454 assert(Depth < Stack.size() && "Delegate destination should be in scope");
2455 return Depth;
2456}
2457
2458unsigned WebAssemblyCFGStackify::getRethrowDepth(
2459 const SmallVectorImpl<EndMarkerInfo> &Stack,
2460 const MachineBasicBlock *EHPadToRethrow) {
2461 unsigned Depth = 0;
2462 for (auto X : reverse(Stack)) {
2463 const MachineInstr *End = X.second;
2464 if (End->getOpcode() == WebAssembly::END_TRY) {
2465 auto *EHPad = TryToEHPad[EndToBegin[End]];
2466 if (EHPadToRethrow == EHPad)
2467 break;
2468 }
2469 ++Depth;
2470 }
2471 assert(Depth < Stack.size() && "Rethrow destination should be in scope");
2472 return Depth;
2473}
2474
2475void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
2476 // Now rewrite references to basic blocks to be depth immediates.
2478
2479 auto RewriteOperands = [&](MachineInstr &MI) {
2480 // Rewrite MBB operands to be depth immediates.
2481 SmallVector<MachineOperand, 4> Ops(MI.operands());
2482 while (MI.getNumOperands() > 0)
2483 MI.removeOperand(MI.getNumOperands() - 1);
2484 for (auto MO : Ops) {
2485 if (MO.isMBB()) {
2486 if (MI.getOpcode() == WebAssembly::DELEGATE)
2487 MO = MachineOperand::CreateImm(getDelegateDepth(Stack, MO.getMBB()));
2488 else if (MI.getOpcode() == WebAssembly::RETHROW)
2489 MO = MachineOperand::CreateImm(getRethrowDepth(Stack, MO.getMBB()));
2490 else
2491 MO = MachineOperand::CreateImm(getBranchDepth(Stack, MO.getMBB()));
2492 }
2493 MI.addOperand(MF, MO);
2494 }
2495 };
2496
2497 for (auto &MBB : reverse(MF)) {
2498 for (MachineInstr &MI : llvm::reverse(MBB)) {
2499 switch (MI.getOpcode()) {
2500 case WebAssembly::BLOCK:
2501 case WebAssembly::TRY:
2502 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2503 MBB.getNumber() &&
2504 "Block/try/try_table marker should be balanced");
2505 Stack.pop_back();
2506 break;
2507
2508 case WebAssembly::TRY_TABLE:
2509 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2510 MBB.getNumber() &&
2511 "Block/try/try_table marker should be balanced");
2512 Stack.pop_back();
2513 RewriteOperands(MI);
2514 break;
2515
2516 case WebAssembly::LOOP:
2517 assert(Stack.back().first == &MBB && "Loop top should be balanced");
2518 Stack.pop_back();
2519 break;
2520
2521 case WebAssembly::END_BLOCK:
2522 case WebAssembly::END_TRY:
2523 case WebAssembly::END_TRY_TABLE:
2524 Stack.push_back(std::make_pair(&MBB, &MI));
2525 break;
2526
2527 case WebAssembly::END_LOOP:
2528 Stack.push_back(std::make_pair(EndToBegin[&MI]->getParent(), &MI));
2529 break;
2530
2531 case WebAssembly::DELEGATE:
2532 RewriteOperands(MI);
2533 Stack.push_back(std::make_pair(&MBB, &MI));
2534 break;
2535
2536 default:
2537 if (MI.isTerminator())
2538 RewriteOperands(MI);
2539 break;
2540 }
2541 }
2542 }
2543 assert(Stack.empty() && "Control flow should be balanced");
2544}
2545
2546void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) {
2547 if (FakeCallerBB)
2548 MF.deleteMachineBasicBlock(FakeCallerBB);
2549 AppendixBB = FakeCallerBB = CallerTrampolineBB = nullptr;
2550}
2551
2552void WebAssemblyCFGStackify::releaseMemory() {
2553 ScopeTops.clear();
2554 BeginToEnd.clear();
2555 EndToBegin.clear();
2556 TryToEHPad.clear();
2557 EHPadToTry.clear();
2558 UnwindDestToTrampoline.clear();
2559}
2560
2561bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
2562 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
2563 "********** Function: "
2564 << MF.getName() << '\n');
2565 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
2566 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
2567
2568 releaseMemory();
2569
2570 // Liveness is not tracked for VALUE_STACK physreg.
2572
2573 // Place the BLOCK/LOOP/TRY/TRY_TABLE markers to indicate the beginnings of
2574 // scopes.
2575 placeMarkers(MF);
2576
2577 // Remove unnecessary instructions possibly introduced by try/end_trys.
2578 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2580 removeUnnecessaryInstrs(MF);
2581
2582 // Convert MBB operands in terminators to relative depth immediates.
2583 rewriteDepthImmediates(MF);
2584
2585 // Fix up block/loop/try/try_table signatures at the end of the function to
2586 // conform to WebAssembly's rules.
2587 fixEndsAtEndOfFunction(MF);
2588
2589 // Add an end instruction at the end of the function body.
2590 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
2592
2593 cleanupFunctionData(MF);
2594
2595 MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
2596 return true;
2597}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DEBUG(...)
Definition: Debug.h:106
bool End
Definition: ELF_riscv.cpp:480
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
const HexagonInstrInfo * TII
#define _
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
#define P(N)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:166
static bool explicitlyBranchesTo(MachineBasicBlock *Pred, MachineBasicBlock *MBB)
Test whether Pred has any terminators explicitly branching to MBB, as opposed to falling through.
static MachineBasicBlock::iterator getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, const Container &AfterSet)
static void appendEndToFunction(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
static void splitEndLoopBB(MachineBasicBlock *UnwindDest)
static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, MachineBasicBlock &Split)
static MachineBasicBlock * getSingleUnwindDest(const MachineInstr *TryTable)
static MachineBasicBlock::iterator getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, const Container &AfterSet)
#define DEBUG_TYPE
This file implements WebAssemblyException information analysis.
This file provides WebAssembly-specific target descriptions.
This file declares WebAssembly-specific per-machine-function information.
This file implements regions used in CFGSort and CFGStackify.
This file declares the WebAssembly-specific subclass of TargetSubtarget.
This file contains the declaration of the WebAssembly-specific type parsing utility functions.
This file contains the declaration of the WebAssembly-specific utility functions.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
A debug info location.
Definition: DebugLoc.h:33
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:194
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:156
bool erase(const KeyT &Val)
Definition: DenseMap.h:321
bool empty() const
Definition: DenseMap.h:98
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:152
iterator end()
Definition: DenseMap.h:84
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:905
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
BlockT * getHeader() const
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:39
This class is intended to be used as a base class for asm properties and features specific to the tar...
Definition: MCAsmInfo.h:56
ExceptionHandling getExceptionHandlingType() const
Definition: MCAsmInfo.h:740
bool isEHPad() const
Returns true if the block is a landing pad.
reverse_iterator rend()
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
bool isPredecessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a predecessor of this block.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any debug instructions.
DebugLoc findPrevDebugLoc(instr_iterator MBBI)
Find the previous valid DebugLoc preceding MBBI, skipping any debug instructions.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< iterator > terminators()
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
iterator_range< succ_iterator > successors()
reverse_iterator rbegin()
iterator_range< pred_iterator > predecessors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
MachineInstrBundleIterator< MachineInstr > iterator
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
void push_back(MachineBasicBlock *MBB)
reverse_iterator rbegin()
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
void deleteMachineBasicBlock(MachineBasicBlock *MBB)
DeleteMachineBasicBlock - Delete the given MachineBasicBlock.
Function & getFunction()
Return the LLVM function that this machine code represents.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
const MachineBasicBlock & back() const
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
const WasmEHFuncInfo * getWasmEHFuncInfo() const
getWasmEHFuncInfo - Return information about how the current function uses Wasm exception handling.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineBasicBlock & front() const
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *BB=nullptr, std::optional< UniqueBBID > BBID=std::nullopt)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
void insert(iterator MBBI, MachineBasicBlock *MBB)
const TargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
const MachineInstrBuilder & addExternalSymbol(const char *FnName, unsigned TargetFlags=0) const
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
MachineInstr * getInstr() const
If conversion operators fail, use this method to get the MachineInstr explicitly.
const MachineInstrBuilder & addDef(Register RegNo, unsigned Flags=0, unsigned SubReg=0) const
Add a virtual register definition operand.
Representation of each machine instruction.
Definition: MachineInstr.h:69
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:575
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:347
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:499
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:585
MachineOperand class - Representation of each machine instruction operand.
int64_t getImm() const
MachineBasicBlock * getMBB() const
static MachineOperand CreateImm(int64_t Val)
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
virtual void releaseMemory()
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: Pass.cpp:102
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:452
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:384
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:519
bool empty() const
Definition: SmallVector.h:81
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
void resize(size_type N)
Definition: SmallVector.h:638
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
const std::vector< MVT > & getResults() const
self_iterator getIterator()
Definition: ilist_node.h:132
A collection of legacy interfaces for querying information about the current executing process.
Definition: Process.h:43
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
bool isChild(const MachineInstr &MI, const WebAssemblyFunctionInfo &MFI)
Test whether MI is a child of some other node in an expression tree.
bool isArgument(unsigned Opc)
bool isTry(unsigned Opc)
bool isCatchAll(unsigned Opc)
bool isMarker(unsigned Opc)
unsigned getCopyOpcodeForRegClass(const TargetRegisterClass *RC)
Returns the appropriate copy opcode for the given register class.
wasm::ValType toValType(MVT Type)
MachineInstr * findCatch(MachineBasicBlock *EHPad)
Find a catch instruction from an EH pad.
bool isCatch(unsigned Opc)
bool isTee(unsigned Opc)
cl::opt< bool > WasmEnableExnref
BlockType
Used as immediate MachineOperands for block signatures.
bool mayThrow(const MachineInstr &MI)
@ WASM_OPCODE_CATCH_ALL_REF
Definition: Wasm.h:152
@ WASM_OPCODE_CATCH
Definition: Wasm.h:149
@ WASM_OPCODE_CATCH_ALL
Definition: Wasm.h:151
@ WASM_OPCODE_CATCH_REF
Definition: Wasm.h:150
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:657
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:420
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createWebAssemblyCFGStackify()