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.
855 const auto &TLI =
856 *MF.getSubtarget<WebAssemblySubtarget>().getTargetLowering();
858 TLI.getPointerTy(MF.getDataLayout()) == MVT::i32
859 ? WebAssembly::BlockType::I32
860 : WebAssembly::BlockType::I64;
862 switch (Catch->getOpcode()) {
863 case WebAssembly::CATCH:
864 // CATCH's destination block's return type is the extracted value type,
865 // which is currently the thrown value's pointer type for all supported
866 // tags.
867 BlockMIB.addImm(int64_t(PtrTy));
868 TryTableMIB.addImm(wasm::WASM_OPCODE_CATCH);
869 for (const auto &Use : Catch->uses()) {
870 // The only use operand a CATCH can have is the tag symbol.
871 TryTableMIB.addExternalSymbol(Use.getSymbolName());
872 break;
873 }
874 TryTableMIB.addMBB(&MBB);
875 break;
876 case WebAssembly::CATCH_REF:
877 // CATCH_REF's destination block's return type is the extracted value type
878 // followed by an exnref, which is (i32, exnref) in our case. We assign the
879 // actual multiavlue signature in MCInstLower. MO_CATCH_BLOCK_SIG signals
880 // that this operand is used for catch_ref's multivalue destination.
881 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Multivalue));
882 Block->getOperand(0).setTargetFlags(WebAssemblyII::MO_CATCH_BLOCK_SIG);
884 for (const auto &Use : Catch->uses()) {
885 TryTableMIB.addExternalSymbol(Use.getSymbolName());
886 break;
887 }
888 TryTableMIB.addMBB(&MBB);
889 break;
890 case WebAssembly::CATCH_ALL:
891 // CATCH_ALL's destination block's return type is void.
892 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Void));
894 TryTableMIB.addMBB(&MBB);
895 break;
896 case WebAssembly::CATCH_ALL_REF:
897 // CATCH_ALL_REF's destination block's return type is exnref.
898 BlockMIB.addImm(int64_t(WebAssembly::BlockType::Exnref));
900 TryTableMIB.addMBB(&MBB);
901 break;
902 }
903
904 // Decide where in MBB to put the END_TRY_TABLE, and the END_BLOCK for the
905 // CATCH destination.
906 BeforeSet.clear();
907 AfterSet.clear();
908 for (const auto &MI : MBB) {
909#ifndef NDEBUG
910 // END_TRY_TABLE should precede existing LOOP markers.
911 if (MI.getOpcode() == WebAssembly::LOOP)
912 AfterSet.insert(&MI);
913#endif
914
915 // If there is a previously placed END_LOOP marker and the header of the
916 // loop is above this try_table's header, the END_LOOP should be placed
917 // after the END_TRY_TABLE, because the loop contains this block. Otherwise
918 // the END_LOOP should be placed before the END_TRY_TABLE.
919 if (MI.getOpcode() == WebAssembly::END_LOOP) {
920 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
921 BeforeSet.insert(&MI);
922#ifndef NDEBUG
923 else
924 AfterSet.insert(&MI);
925#endif
926 }
927
928#ifndef NDEBUG
929 // CATCH, CATCH_REF, CATCH_ALL, and CATCH_ALL_REF are pseudo-instructions
930 // that simulate the block return value, so they should be placed after the
931 // END_TRY_TABLE.
932 if (WebAssembly::isCatch(MI.getOpcode()))
933 AfterSet.insert(&MI);
934#endif
935 }
936
937 // Mark the end of the TRY_TABLE and the BLOCK.
938 InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
939 MachineInstr *EndTryTable =
940 BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
941 TII.get(WebAssembly::END_TRY_TABLE));
942 registerTryScope(TryTable, EndTryTable, &MBB);
943 MachineInstr *EndBlock =
944 BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
945 TII.get(WebAssembly::END_BLOCK));
946 registerScope(Block, EndBlock);
947
948 // Track the farthest-spanning scope that ends at this point.
949 // Unlike the end_try, even if we don't put a end marker at the end of catch
950 // block, we still have to create two mappings: (BB with 'end_try_table' -> BB
951 // with 'try_table') and (BB after the (conceptual) catch block -> BB with
952 // 'try_table').
953 //
954 // This is what can happen if we don't create the latter mapping:
955 //
956 // Suppoe in the legacy EH we have this code:
957 // try
958 // try
959 // code1
960 // catch (a)
961 // end_try
962 // code2
963 // catch (b)
964 // end_try
965 //
966 // If we don't create the latter mapping, try_table markers would be placed
967 // like this:
968 // try_table
969 // code1
970 // end_try_table (a)
971 // try_table
972 // code2
973 // end_try_table (b)
974 //
975 // This does not reflect the original structure, and more important problem
976 // is, in case 'code1' has an unwind mismatch and should unwind to
977 // 'end_try_table (b)' rather than 'end_try_table (a)', we don't have a way to
978 // make it jump after 'end_try_table (b)' without creating another block. So
979 // even if we don't place 'end_try' marker at the end of 'catch' block
980 // anymore, we create ScopeTops mapping the same way as the legacy exception,
981 // so the resulting code will look like:
982 // try_table
983 // try_table
984 // code1
985 // end_try_table (a)
986 // code2
987 // end_try_table (b)
988 for (auto *End : {&MBB, Cont})
989 updateScopeTops(Header, End);
990}
991
992void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
993 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
994
995 // When there is an unconditional branch right before a catch instruction and
996 // it branches to the end of end_try marker, we don't need the branch, because
997 // if there is no exception, the control flow transfers to that point anyway.
998 // bb0:
999 // try
1000 // ...
1001 // br bb2 <- Not necessary
1002 // bb1 (ehpad):
1003 // catch
1004 // ...
1005 // bb2: <- Continuation BB
1006 // end
1007 //
1008 // A more involved case: When the BB where 'end' is located is an another EH
1009 // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example,
1010 // bb0:
1011 // try
1012 // try
1013 // ...
1014 // br bb3 <- Not necessary
1015 // bb1 (ehpad):
1016 // catch
1017 // bb2 (ehpad):
1018 // end
1019 // catch
1020 // ...
1021 // bb3: <- Continuation BB
1022 // end
1023 //
1024 // When the EH pad at hand is bb1, its matching end_try is in bb2. But it is
1025 // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the
1026 // code can be deleted. This is why we run 'while' until 'Cont' is not an EH
1027 // pad.
1028 for (auto &MBB : MF) {
1029 if (!MBB.isEHPad())
1030 continue;
1031
1032 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1034 MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
1035
1036 MachineBasicBlock *Cont = &MBB;
1037 while (Cont->isEHPad()) {
1038 MachineInstr *Try = EHPadToTry[Cont];
1039 MachineInstr *EndTry = BeginToEnd[Try];
1040 // We started from an EH pad, so the end marker cannot be a delegate
1041 assert(EndTry->getOpcode() != WebAssembly::DELEGATE);
1042 Cont = EndTry->getParent();
1043 }
1044
1045 bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
1046 // This condition means either
1047 // 1. This BB ends with a single unconditional branch whose destinaion is
1048 // Cont.
1049 // 2. This BB ends with a conditional branch followed by an unconditional
1050 // branch, and the unconditional branch's destination is Cont.
1051 // In both cases, we want to remove the last (= unconditional) branch.
1052 if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
1053 (!Cond.empty() && FBB && FBB == Cont))) {
1054 bool ErasedUncondBr = false;
1055 (void)ErasedUncondBr;
1056 for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin();
1057 I != E; --I) {
1058 auto PrevI = std::prev(I);
1059 if (PrevI->isTerminator()) {
1060 assert(PrevI->getOpcode() == WebAssembly::BR);
1061 PrevI->eraseFromParent();
1062 ErasedUncondBr = true;
1063 break;
1064 }
1065 }
1066 assert(ErasedUncondBr && "Unconditional branch not erased!");
1067 }
1068 }
1069
1070 // When there are block / end_block markers that overlap with try / end_try
1071 // markers, and the block and try markers' return types are the same, the
1072 // block /end_block markers are not necessary, because try / end_try markers
1073 // also can serve as boundaries for branches.
1074 // block <- Not necessary
1075 // try
1076 // ...
1077 // catch
1078 // ...
1079 // end
1080 // end <- Not necessary
1082 for (auto &MBB : MF) {
1083 for (auto &MI : MBB) {
1084 if (MI.getOpcode() != WebAssembly::TRY)
1085 continue;
1086 MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
1087 if (EndTry->getOpcode() == WebAssembly::DELEGATE)
1088 continue;
1089
1090 MachineBasicBlock *TryBB = Try->getParent();
1091 MachineBasicBlock *Cont = EndTry->getParent();
1092 int64_t RetType = Try->getOperand(0).getImm();
1093 for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());
1094 B != TryBB->begin() && E != Cont->end() &&
1095 std::prev(B)->getOpcode() == WebAssembly::BLOCK &&
1096 E->getOpcode() == WebAssembly::END_BLOCK &&
1097 std::prev(B)->getOperand(0).getImm() == RetType;
1098 --B, ++E) {
1099 ToDelete.push_back(&*std::prev(B));
1100 ToDelete.push_back(&*E);
1101 }
1102 }
1103 }
1104 for (auto *MI : ToDelete) {
1105 if (MI->getOpcode() == WebAssembly::BLOCK)
1106 unregisterScope(MI);
1107 MI->eraseFromParent();
1108 }
1109}
1110
1111// When MBB is split into MBB and Split, we should unstackify defs in MBB that
1112// have their uses in Split.
1114 MachineBasicBlock &Split) {
1115 MachineFunction &MF = *MBB.getParent();
1116 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1117 auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1118 auto &MRI = MF.getRegInfo();
1119
1120 for (auto &MI : Split) {
1121 for (auto &MO : MI.explicit_uses()) {
1122 if (!MO.isReg() || MO.getReg().isPhysical())
1123 continue;
1124 if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg()))
1125 if (Def->getParent() == &MBB)
1126 MFI.unstackifyVReg(MO.getReg());
1127 }
1128 }
1129
1130 // In RegStackify, when a register definition is used multiple times,
1131 // Reg = INST ...
1132 // INST ..., Reg, ...
1133 // INST ..., Reg, ...
1134 // INST ..., Reg, ...
1135 //
1136 // we introduce a TEE, which has the following form:
1137 // DefReg = INST ...
1138 // TeeReg, Reg = TEE_... DefReg
1139 // INST ..., TeeReg, ...
1140 // INST ..., Reg, ...
1141 // INST ..., Reg, ...
1142 // with DefReg and TeeReg stackified but Reg not stackified.
1143 //
1144 // But the invariant that TeeReg should be stackified can be violated while we
1145 // unstackify registers in the split BB above. In this case, we convert TEEs
1146 // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals.
1147 // DefReg = INST ...
1148 // TeeReg = COPY DefReg
1149 // Reg = COPY DefReg
1150 // INST ..., TeeReg, ...
1151 // INST ..., Reg, ...
1152 // INST ..., Reg, ...
1154 if (!WebAssembly::isTee(MI.getOpcode()))
1155 continue;
1156 Register TeeReg = MI.getOperand(0).getReg();
1157 Register Reg = MI.getOperand(1).getReg();
1158 Register DefReg = MI.getOperand(2).getReg();
1159 if (!MFI.isVRegStackified(TeeReg)) {
1160 // Now we are not using TEE anymore, so unstackify DefReg too
1161 MFI.unstackifyVReg(DefReg);
1162 unsigned CopyOpc =
1163 WebAssembly::getCopyOpcodeForRegClass(MRI.getRegClass(DefReg));
1164 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg)
1165 .addReg(DefReg);
1166 BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg);
1167 MI.eraseFromParent();
1168 }
1169 }
1170}
1171
1172// Wrap the given range of instructions with a try-delegate that targets
1173// 'UnwindDest'. RangeBegin and RangeEnd are inclusive.
1174void WebAssemblyCFGStackify::addNestedTryDelegate(
1175 MachineInstr *RangeBegin, MachineInstr *RangeEnd,
1176 MachineBasicBlock *UnwindDest) {
1177 auto *BeginBB = RangeBegin->getParent();
1178 auto *EndBB = RangeEnd->getParent();
1179 MachineFunction &MF = *BeginBB->getParent();
1180 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1181 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1182
1183 // Local expression tree before the first call of this range should go
1184 // after the nested TRY.
1186 AfterSet.insert(RangeBegin);
1187 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();
1188 I != E; --I) {
1189 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
1190 continue;
1191 if (WebAssembly::isChild(*std::prev(I), MFI))
1192 AfterSet.insert(&*std::prev(I));
1193 else
1194 break;
1195 }
1196
1197 // Create the nested try instruction.
1198 auto TryPos = getLatestInsertPos(
1199 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
1200 MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(),
1201 TII.get(WebAssembly::TRY))
1202 .addImm(int64_t(WebAssembly::BlockType::Void));
1203
1204 // Create a BB to insert the 'delegate' instruction.
1205 MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock();
1206 // If the destination of 'delegate' is not the caller, adds the destination to
1207 // the BB's successors.
1208 if (UnwindDest != FakeCallerBB)
1209 DelegateBB->addSuccessor(UnwindDest);
1210
1211 auto SplitPos = std::next(RangeEnd->getIterator());
1212 if (SplitPos == EndBB->end()) {
1213 // If the range's end instruction is at the end of the BB, insert the new
1214 // delegate BB after the current BB.
1215 MF.insert(std::next(EndBB->getIterator()), DelegateBB);
1216 EndBB->addSuccessor(DelegateBB);
1217
1218 } else {
1219 // When the split pos is in the middle of a BB, we split the BB into two and
1220 // put the 'delegate' BB in between. We normally create a split BB and make
1221 // it a successor of the original BB (CatchAfterSplit == false), but in case
1222 // the BB is an EH pad and there is a 'catch' after the split pos
1223 // (CatchAfterSplit == true), we should preserve the BB's property,
1224 // including that it is an EH pad, in the later part of the BB, where the
1225 // 'catch' is.
1226 bool CatchAfterSplit = false;
1227 if (EndBB->isEHPad()) {
1228 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
1229 I != E; ++I) {
1230 if (WebAssembly::isCatch(I->getOpcode())) {
1231 CatchAfterSplit = true;
1232 break;
1233 }
1234 }
1235 }
1236
1237 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
1238 if (!CatchAfterSplit) {
1239 // If the range's end instruction is in the middle of the BB, we split the
1240 // BB into two and insert the delegate BB in between.
1241 // - Before:
1242 // bb:
1243 // range_end
1244 // other_insts
1245 //
1246 // - After:
1247 // pre_bb: (previous 'bb')
1248 // range_end
1249 // delegate_bb: (new)
1250 // delegate
1251 // post_bb: (new)
1252 // other_insts
1253 PreBB = EndBB;
1254 PostBB = MF.CreateMachineBasicBlock();
1255 MF.insert(std::next(PreBB->getIterator()), PostBB);
1256 MF.insert(std::next(PreBB->getIterator()), DelegateBB);
1257 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
1258 PostBB->transferSuccessors(PreBB);
1259 } else {
1260 // - Before:
1261 // ehpad:
1262 // range_end
1263 // catch
1264 // ...
1265 //
1266 // - After:
1267 // pre_bb: (new)
1268 // range_end
1269 // delegate_bb: (new)
1270 // delegate
1271 // post_bb: (previous 'ehpad')
1272 // catch
1273 // ...
1274 assert(EndBB->isEHPad());
1275 PreBB = MF.CreateMachineBasicBlock();
1276 PostBB = EndBB;
1277 MF.insert(PostBB->getIterator(), PreBB);
1278 MF.insert(PostBB->getIterator(), DelegateBB);
1279 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
1280 // We don't need to transfer predecessors of the EH pad to 'PreBB',
1281 // because an EH pad's predecessors are all through unwind edges and they
1282 // should still unwind to the EH pad, not PreBB.
1283 }
1284 unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);
1285 PreBB->addSuccessor(DelegateBB);
1286 PreBB->addSuccessor(PostBB);
1287 }
1288
1289 // Add a 'delegate' instruction in the delegate BB created above.
1290 MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(),
1291 TII.get(WebAssembly::DELEGATE))
1292 .addMBB(UnwindDest);
1293 registerTryScope(Try, Delegate, nullptr);
1294}
1295
1296// Given an unwind destination, return a trampoline BB. A trampoline BB is a
1297// destination of a nested try_table inserted to fix an unwind mismatch. It
1298// contains an end_block, which is the target of the try_table, and a throw_ref,
1299// to rethrow the exception to the right try_table.
1300// try_table (catch ... )
1301// block exnref
1302// ...
1303// try_table (catch_all_ref N)
1304// some code
1305// end_try_table
1306// ...
1307// unreachable
1308// end_block ;; Trampoline BB
1309// throw_ref
1310// end_try_table
1312WebAssemblyCFGStackify::getTrampolineBlock(MachineBasicBlock *UnwindDest) {
1313 // We need one trampoline BB per unwind destination, even though there are
1314 // multiple try_tables target the same unwind destination. If we have already
1315 // created one for the given UnwindDest, return it.
1316 auto It = UnwindDestToTrampoline.find(UnwindDest);
1317 if (It != UnwindDestToTrampoline.end())
1318 return It->second;
1319
1320 auto &MF = *UnwindDest->getParent();
1321 auto &MRI = MF.getRegInfo();
1322 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1323
1324 MachineInstr *Block = nullptr;
1325 MachineBasicBlock *TrampolineBB = nullptr;
1326 DebugLoc EndDebugLoc;
1327
1328 if (UnwindDest == getFakeCallerBlock(MF)) {
1329 // If the unwind destination is the caller, create a caller-dedicated
1330 // trampoline BB at the end of the function and wrap the whole function with
1331 // a block.
1332 auto BeginPos = MF.begin()->begin();
1333 while (WebAssembly::isArgument(BeginPos->getOpcode()))
1334 BeginPos++;
1335 Block = BuildMI(*MF.begin(), BeginPos, MF.begin()->begin()->getDebugLoc(),
1336 TII.get(WebAssembly::BLOCK))
1337 .addImm(int64_t(WebAssembly::BlockType::Exnref));
1338 TrampolineBB = getCallerTrampolineBlock(MF);
1339 MachineBasicBlock *PrevBB = &*std::prev(CallerTrampolineBB->getIterator());
1340 EndDebugLoc = PrevBB->findPrevDebugLoc(PrevBB->end());
1341 } else {
1342 // If the unwind destination is another EH pad, create a trampoline BB for
1343 // the unwind dest and insert a block instruction right after the target
1344 // try_table.
1345 auto *TargetBeginTry = EHPadToTry[UnwindDest];
1346 auto *TargetEndTry = BeginToEnd[TargetBeginTry];
1347 auto *TargetBeginBB = TargetBeginTry->getParent();
1348 auto *TargetEndBB = TargetEndTry->getParent();
1349
1350 Block = BuildMI(*TargetBeginBB, std::next(TargetBeginTry->getIterator()),
1351 TargetBeginTry->getDebugLoc(), TII.get(WebAssembly::BLOCK))
1352 .addImm(int64_t(WebAssembly::BlockType::Exnref));
1353 TrampolineBB = MF.CreateMachineBasicBlock();
1354 EndDebugLoc = TargetEndTry->getDebugLoc();
1355 MF.insert(TargetEndBB->getIterator(), TrampolineBB);
1356 TrampolineBB->addSuccessor(UnwindDest);
1357 }
1358
1359 // Insert an end_block, catch_all_ref (pseudo instruction), and throw_ref
1360 // instructions in the trampoline BB.
1361 MachineInstr *EndBlock =
1362 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::END_BLOCK));
1363 auto ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);
1364 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::CATCH_ALL_REF))
1365 .addDef(ExnReg);
1366 BuildMI(TrampolineBB, EndDebugLoc, TII.get(WebAssembly::THROW_REF))
1367 .addReg(ExnReg);
1368
1369 // The trampoline BB's return type is exnref because it is a target of
1370 // catch_all_ref. But the body type of the block we just created is not. We
1371 // add an 'unreachable' right before the 'end_block' to make the code valid.
1372 MachineBasicBlock *TrampolineLayoutPred = TrampolineBB->getPrevNode();
1373 BuildMI(TrampolineLayoutPred, TrampolineLayoutPred->findBranchDebugLoc(),
1374 TII.get(WebAssembly::UNREACHABLE));
1375
1376 registerScope(Block, EndBlock);
1377 UnwindDestToTrampoline[UnwindDest] = TrampolineBB;
1378 return TrampolineBB;
1379}
1380
1381// Wrap the given range of instructions with a try_table-end_try_table that
1382// targets 'UnwindDest'. RangeBegin and RangeEnd are inclusive.
1383void WebAssemblyCFGStackify::addNestedTryTable(MachineInstr *RangeBegin,
1384 MachineInstr *RangeEnd,
1385 MachineBasicBlock *UnwindDest) {
1386 auto *BeginBB = RangeBegin->getParent();
1387 auto *EndBB = RangeEnd->getParent();
1388
1389 MachineFunction &MF = *BeginBB->getParent();
1390 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1391 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1392
1393 // Get the trampoline BB that the new try_table will unwind to.
1394 auto *TrampolineBB = getTrampolineBlock(UnwindDest);
1395
1396 // Local expression tree before the first call of this range should go
1397 // after the nested TRY_TABLE.
1399 AfterSet.insert(RangeBegin);
1400 for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();
1401 I != E; --I) {
1402 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
1403 continue;
1404 if (WebAssembly::isChild(*std::prev(I), MFI))
1405 AfterSet.insert(&*std::prev(I));
1406 else
1407 break;
1408 }
1409
1410 // Create the nested try_table instruction.
1411 auto TryTablePos = getLatestInsertPos(
1412 BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
1413 MachineInstr *TryTable =
1414 BuildMI(*BeginBB, TryTablePos, RangeBegin->getDebugLoc(),
1415 TII.get(WebAssembly::TRY_TABLE))
1416 .addImm(int64_t(WebAssembly::BlockType::Void))
1417 .addImm(1) // # of catch clauses
1419 .addMBB(TrampolineBB);
1420
1421 // Create a BB to insert the 'end_try_table' instruction.
1422 MachineBasicBlock *EndTryTableBB = MF.CreateMachineBasicBlock();
1423 EndTryTableBB->addSuccessor(TrampolineBB);
1424
1425 auto SplitPos = std::next(RangeEnd->getIterator());
1426 if (SplitPos == EndBB->end()) {
1427 // If the range's end instruction is at the end of the BB, insert the new
1428 // end_try_table BB after the current BB.
1429 MF.insert(std::next(EndBB->getIterator()), EndTryTableBB);
1430 EndBB->addSuccessor(EndTryTableBB);
1431
1432 } else {
1433 // When the split pos is in the middle of a BB, we split the BB into two and
1434 // put the 'end_try_table' BB in between. We normally create a split BB and
1435 // make it a successor of the original BB (CatchAfterSplit == false), but in
1436 // case the BB is an EH pad and there is a 'catch' after split pos
1437 // (CatchAfterSplit == true), we should preserve the BB's property,
1438 // including that it is an EH pad, in the later part of the BB, where the
1439 // 'catch' is.
1440 bool CatchAfterSplit = false;
1441 if (EndBB->isEHPad()) {
1442 for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
1443 I != E; ++I) {
1444 if (WebAssembly::isCatch(I->getOpcode())) {
1445 CatchAfterSplit = true;
1446 break;
1447 }
1448 }
1449 }
1450
1451 MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
1452 if (!CatchAfterSplit) {
1453 // If the range's end instruction is in the middle of the BB, we split the
1454 // BB into two and insert the end_try_table BB in between.
1455 // - Before:
1456 // bb:
1457 // range_end
1458 // other_insts
1459 //
1460 // - After:
1461 // pre_bb: (previous 'bb')
1462 // range_end
1463 // end_try_table_bb: (new)
1464 // end_try_table
1465 // post_bb: (new)
1466 // other_insts
1467 PreBB = EndBB;
1468 PostBB = MF.CreateMachineBasicBlock();
1469 MF.insert(std::next(PreBB->getIterator()), PostBB);
1470 MF.insert(std::next(PreBB->getIterator()), EndTryTableBB);
1471 PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
1472 PostBB->transferSuccessors(PreBB);
1473 } else {
1474 // - Before:
1475 // ehpad:
1476 // range_end
1477 // catch
1478 // ...
1479 //
1480 // - After:
1481 // pre_bb: (new)
1482 // range_end
1483 // end_try_table_bb: (new)
1484 // end_try_table
1485 // post_bb: (previous 'ehpad')
1486 // catch
1487 // ...
1488 assert(EndBB->isEHPad());
1489 PreBB = MF.CreateMachineBasicBlock();
1490 PostBB = EndBB;
1491 MF.insert(PostBB->getIterator(), PreBB);
1492 MF.insert(PostBB->getIterator(), EndTryTableBB);
1493 PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
1494 // We don't need to transfer predecessors of the EH pad to 'PreBB',
1495 // because an EH pad's predecessors are all through unwind edges and they
1496 // should still unwind to the EH pad, not PreBB.
1497 }
1498 unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);
1499 PreBB->addSuccessor(EndTryTableBB);
1500 PreBB->addSuccessor(PostBB);
1501 }
1502
1503 // Add a 'end_try_table' instruction in the EndTryTable BB created above.
1504 MachineInstr *EndTryTable = BuildMI(EndTryTableBB, RangeEnd->getDebugLoc(),
1505 TII.get(WebAssembly::END_TRY_TABLE));
1506 registerTryScope(TryTable, EndTryTable, nullptr);
1507}
1508
1509// In the standard (exnref) EH, we fix unwind mismatches by adding a new
1510// block~end_block inside of the unwind destination try_table~end_try_table:
1511// try_table ...
1512// block exnref ;; (new)
1513// ...
1514// try_table (catch_all_ref N) ;; (new) to trampoline BB
1515// code
1516// end_try_table ;; (new)
1517// ...
1518// end_block ;; (new) trampoline BB
1519// throw_ref ;; (new)
1520// end_try_table
1521//
1522// To do this, we will create a new BB that will contain the new 'end_block' and
1523// 'throw_ref' and insert it before the 'end_try_table' BB.
1524//
1525// But there are cases when there are 'end_loop'(s) before the 'end_try_table'
1526// in the same BB. (There can't be 'end_block' before 'end_try_table' in the
1527// same BB because EH pads can't be directly branched to.) Then after fixing
1528// unwind mismatches this will create the mismatching markers like below:
1529// bb0:
1530// try_table
1531// block exnref
1532// ...
1533// loop
1534// ...
1535// new_bb:
1536// end_block
1537// end_try_table_bb:
1538// end_loop
1539// end_try_table
1540//
1541// So if an end_try_table BB has an end_loop before the end_try_table, we split
1542// the BB with the end_loop as a separate BB before the end_try_table BB, so
1543// that after we fix the unwind mismatch, the code will be like:
1544// bb0:
1545// try_table
1546// block exnref
1547// ...
1548// loop
1549// ...
1550// end_loop_bb:
1551// end_loop
1552// new_bb:
1553// end_block
1554// end_try_table_bb:
1555// end_try_table
1556static void splitEndLoopBB(MachineBasicBlock *EndTryTableBB) {
1557 auto &MF = *EndTryTableBB->getParent();
1558 MachineInstr *EndTryTable = nullptr, *EndLoop = nullptr;
1559 for (auto &MI : reverse(*EndTryTableBB)) {
1560 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE) {
1561 EndTryTable = &MI;
1562 continue;
1563 }
1564 if (EndTryTable && MI.getOpcode() == WebAssembly::END_LOOP) {
1565 EndLoop = &MI;
1566 break;
1567 }
1568 }
1569 if (!EndLoop)
1570 return;
1571
1572 auto *EndLoopBB = MF.CreateMachineBasicBlock();
1573 MF.insert(EndTryTableBB->getIterator(), EndLoopBB);
1574 auto SplitPos = std::next(EndLoop->getIterator());
1575 EndLoopBB->splice(EndLoopBB->end(), EndTryTableBB, EndTryTableBB->begin(),
1576 SplitPos);
1577 EndLoopBB->addSuccessor(EndTryTableBB);
1578}
1579
1580bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {
1581 // This function is used for both the legacy EH and the standard (exnref) EH,
1582 // and the reason we have unwind mismatches is the same for the both of them,
1583 // but the code examples in the comments are going to be different. To make
1584 // the description less confusing, we write the basically same comments twice,
1585 // once for the legacy EH and the standard EH.
1586 //
1587 // -- Legacy EH --------------------------------------------------------------
1588 //
1589 // Linearizing the control flow by placing TRY / END_TRY markers can create
1590 // mismatches in unwind destinations for throwing instructions, such as calls.
1591 //
1592 // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate'
1593 // instruction delegates an exception to an outer 'catch'. It can target not
1594 // only 'catch' but all block-like structures including another 'delegate',
1595 // but with slightly different semantics than branches. When it targets a
1596 // 'catch', it will delegate the exception to that catch. It is being
1597 // discussed how to define the semantics when 'delegate''s target is a non-try
1598 // block: it will either be a validation failure or it will target the next
1599 // outer try-catch. But anyway our LLVM backend currently does not generate
1600 // such code. The example below illustrates where the 'delegate' instruction
1601 // in the middle will delegate the exception to, depending on the value of N.
1602 // try
1603 // try
1604 // block
1605 // try
1606 // try
1607 // call @foo
1608 // delegate N ;; Where will this delegate to?
1609 // catch ;; N == 0
1610 // end
1611 // end ;; N == 1 (invalid; will not be generated)
1612 // delegate ;; N == 2
1613 // catch ;; N == 3
1614 // end
1615 // ;; N == 4 (to caller)
1616 //
1617 // 1. When an instruction may throw, but the EH pad it will unwind to can be
1618 // different from the original CFG.
1619 //
1620 // Example: we have the following CFG:
1621 // bb0:
1622 // call @foo ; if it throws, unwind to bb2
1623 // bb1:
1624 // call @bar ; if it throws, unwind to bb3
1625 // bb2 (ehpad):
1626 // catch
1627 // ...
1628 // bb3 (ehpad)
1629 // catch
1630 // ...
1631 //
1632 // And the CFG is sorted in this order. Then after placing TRY markers, it
1633 // will look like: (BB markers are omitted)
1634 // try
1635 // try
1636 // call @foo
1637 // call @bar ;; if it throws, unwind to bb3
1638 // catch ;; ehpad (bb2)
1639 // ...
1640 // end_try
1641 // catch ;; ehpad (bb3)
1642 // ...
1643 // end_try
1644 //
1645 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is
1646 // supposed to end up. We solve this problem by wrapping the mismatching call
1647 // with an inner try-delegate that rethrows the exception to the right
1648 // 'catch'.
1649 //
1650 // try
1651 // try
1652 // call @foo
1653 // try ;; (new)
1654 // call @bar
1655 // delegate 1 (bb3) ;; (new)
1656 // catch ;; ehpad (bb2)
1657 // ...
1658 // end_try
1659 // catch ;; ehpad (bb3)
1660 // ...
1661 // end_try
1662 //
1663 // ---
1664 // 2. The same as 1, but in this case an instruction unwinds to a caller
1665 // function and not another EH pad.
1666 //
1667 // Example: we have the following CFG:
1668 // bb0:
1669 // call @foo ; if it throws, unwind to bb2
1670 // bb1:
1671 // call @bar ; if it throws, unwind to caller
1672 // bb2 (ehpad):
1673 // catch
1674 // ...
1675 //
1676 // And the CFG is sorted in this order. Then after placing TRY markers, it
1677 // will look like:
1678 // try
1679 // call @foo
1680 // call @bar ;; if it throws, unwind to caller
1681 // catch ;; ehpad (bb2)
1682 // ...
1683 // end_try
1684 //
1685 // Now if bar() throws, it is going to end up in bb2, when it is supposed
1686 // throw up to the caller. We solve this problem in the same way, but in this
1687 // case 'delegate's immediate argument is the number of block depths + 1,
1688 // which means it rethrows to the caller.
1689 // try
1690 // call @foo
1691 // try ;; (new)
1692 // call @bar
1693 // delegate 1 (caller) ;; (new)
1694 // catch ;; ehpad (bb2)
1695 // ...
1696 // end_try
1697 //
1698 // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the
1699 // caller, it will take a fake BB generated by getFakeCallerBlock(), which
1700 // will be converted to a correct immediate argument later.
1701 //
1702 // In case there are multiple calls in a BB that may throw to the caller, they
1703 // can be wrapped together in one nested try-delegate scope. (In 1, this
1704 // couldn't happen, because may-throwing instruction there had an unwind
1705 // destination, i.e., it was an invoke before, and there could be only one
1706 // invoke within a BB.)
1707 //
1708 // -- Standard EH ------------------------------------------------------------
1709 //
1710 // Linearizing the control flow by placing TRY / END_TRY_TABLE markers can
1711 // create mismatches in unwind destinations for throwing instructions, such as
1712 // calls.
1713 //
1714 // We use the a nested 'try_table'~'end_try_table' instruction to fix the
1715 // unwind mismatches. try_table's catch clauses take an immediate argument
1716 // that specifics which block we should branch to.
1717 //
1718 // 1. When an instruction may throw, but the EH pad it will unwind to can be
1719 // different from the original CFG.
1720 //
1721 // Example: we have the following CFG:
1722 // bb0:
1723 // call @foo ; if it throws, unwind to bb2
1724 // bb1:
1725 // call @bar ; if it throws, unwind to bb3
1726 // bb2 (ehpad):
1727 // catch
1728 // ...
1729 // bb3 (ehpad)
1730 // catch
1731 // ...
1732 //
1733 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers
1734 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:
1735 // (BB markers are omitted)
1736 // block
1737 // try_table (catch ... 0)
1738 // block
1739 // try_table (catch ... 0)
1740 // call @foo
1741 // call @bar ;; if it throws, unwind to bb3
1742 // end_try_table
1743 // end_block ;; ehpad (bb2)
1744 // ...
1745 // end_try_table
1746 // end_block ;; ehpad (bb3)
1747 // ...
1748 //
1749 // Now if bar() throws, it is going to end up in bb2, not bb3, where it is
1750 // supposed to end up. We solve this problem by wrapping the mismatching call
1751 // with an inner try_table~end_try_table that sends the exception to the the
1752 // 'trampoline' block, which rethrows, or 'bounces' it to the right
1753 // end_try_table:
1754 // block
1755 // try_table (catch ... 0)
1756 // block exnref ;; (new)
1757 // block
1758 // try_table (catch ... 0)
1759 // call @foo
1760 // try_table (catch_all_ref 2) ;; (new) to trampoline BB
1761 // call @bar
1762 // end_try_table ;; (new)
1763 // end_try_table
1764 // end_block ;; ehpad (bb2)
1765 // ...
1766 // end_block ;; (new) trampoline BB
1767 // throw_ref ;; (new)
1768 // end_try_table
1769 // end_block ;; ehpad (bb3)
1770 //
1771 // ---
1772 // 2. The same as 1, but in this case an instruction unwinds to a caller
1773 // function and not another EH pad.
1774 //
1775 // Example: we have the following CFG:
1776 // bb0:
1777 // call @foo ; if it throws, unwind to bb2
1778 // bb1:
1779 // call @bar ; if it throws, unwind to caller
1780 // bb2 (ehpad):
1781 // catch
1782 // ...
1783 //
1784 // And the CFG is sorted in this order. Then after placing TRY_TABLE markers
1785 // (and BLOCK markers for the TRY_TABLE's destinations), it will look like:
1786 // block
1787 // try_table (catch ... 0)
1788 // call @foo
1789 // call @bar ;; if it throws, unwind to caller
1790 // end_try_table
1791 // end_block ;; ehpad (bb2)
1792 // ...
1793 //
1794 // Now if bar() throws, it is going to end up in bb2, when it is supposed
1795 // throw up to the caller. We solve this problem in the same way, but in this
1796 // case 'delegate's immediate argument is the number of block depths + 1,
1797 // which means it rethrows to the caller.
1798 // block exnref ;; (new)
1799 // block
1800 // try_table (catch ... 0)
1801 // call @foo
1802 // try_table (catch_all_ref 2) ;; (new) to trampoline BB
1803 // call @bar
1804 // end_try_table ;; (new)
1805 // end_try_table
1806 // end_block ;; ehpad (bb2)
1807 // ...
1808 // end_block ;; (new) caller trampoline BB
1809 // throw_ref ;; (new) throw to the caller
1810 //
1811 // Before rewriteDepthImmediates, try_table's catch clauses' argument is a
1812 // trampoline BB from which we throw_ref the exception to the right
1813 // end_try_table. In case of the caller, it will take a new caller-dedicated
1814 // trampoline BB generated by getCallerTrampolineBlock(), which throws the
1815 // exception to the caller.
1816 //
1817 // In case there are multiple calls in a BB that may throw to the caller, they
1818 // can be wrapped together in one nested try_table-end_try_table scope. (In 1,
1819 // this couldn't happen, because may-throwing instruction there had an unwind
1820 // destination, i.e., it was an invoke before, and there could be only one
1821 // invoke within a BB.)
1822
1824 // Range of intructions to be wrapped in a new nested try~delegate or
1825 // try_table~end_try_table. A range exists in a single BB and does not span
1826 // multiple BBs.
1827 using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1828 // In original CFG, <unwind destination BB, a vector of try/try_table ranges>
1830
1831 // Gather possibly throwing calls (i.e., previously invokes) whose current
1832 // unwind destination is not the same as the original CFG. (Case 1)
1833
1834 for (auto &MBB : reverse(MF)) {
1835 bool SeenThrowableInstInBB = false;
1836 for (auto &MI : reverse(MBB)) {
1837 if (WebAssembly::isTry(MI.getOpcode()))
1838 EHPadStack.pop_back();
1839 else if (WebAssembly::isCatch(MI.getOpcode()))
1840 EHPadStack.push_back(MI.getParent());
1841
1842 // In this loop we only gather calls that have an EH pad to unwind. So
1843 // there will be at most 1 such call (= invoke) in a BB, so after we've
1844 // seen one, we can skip the rest of BB. Also if MBB has no EH pad
1845 // successor or MI does not throw, this is not an invoke.
1846 if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
1848 continue;
1849 SeenThrowableInstInBB = true;
1850
1851 // If the EH pad on the stack top is where this instruction should unwind
1852 // next, we're good.
1853 MachineBasicBlock *UnwindDest = getFakeCallerBlock(MF);
1854 for (auto *Succ : MBB.successors()) {
1855 // Even though semantically a BB can have multiple successors in case an
1856 // exception is not caught by a catchpad, in our backend implementation
1857 // it is guaranteed that a BB can have at most one EH pad successor. For
1858 // details, refer to comments in findWasmUnwindDestinations function in
1859 // SelectionDAGBuilder.cpp.
1860 if (Succ->isEHPad()) {
1861 UnwindDest = Succ;
1862 break;
1863 }
1864 }
1865 if (EHPadStack.back() == UnwindDest)
1866 continue;
1867
1868 // Include EH_LABELs in the range before and after the invoke
1869 MachineInstr *RangeBegin = &MI, *RangeEnd = &MI;
1870 if (RangeBegin->getIterator() != MBB.begin() &&
1871 std::prev(RangeBegin->getIterator())->isEHLabel())
1872 RangeBegin = &*std::prev(RangeBegin->getIterator());
1873 if (std::next(RangeEnd->getIterator()) != MBB.end() &&
1874 std::next(RangeEnd->getIterator())->isEHLabel())
1875 RangeEnd = &*std::next(RangeEnd->getIterator());
1876
1877 // If not, record the range.
1878 UnwindDestToTryRanges[UnwindDest].push_back(
1879 TryRange(RangeBegin, RangeEnd));
1880 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName()
1881 << "\nCall = " << MI
1882 << "\nOriginal dest = " << UnwindDest->getName()
1883 << " Current dest = " << EHPadStack.back()->getName()
1884 << "\n\n");
1885 }
1886 }
1887
1888 assert(EHPadStack.empty());
1889
1890 // Gather possibly throwing calls that are supposed to unwind up to the caller
1891 // if they throw, but currently unwind to an incorrect destination. Unlike the
1892 // loop above, there can be multiple calls within a BB that unwind to the
1893 // caller, which we should group together in a range. (Case 2)
1894
1895 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
1896
1897 // Record the range.
1898 auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) {
1899 UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1900 TryRange(RangeBegin, RangeEnd));
1901 LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "
1902 << RangeBegin->getParent()->getName()
1903 << "\nRange begin = " << *RangeBegin
1904 << "Range end = " << *RangeEnd
1905 << "\nOriginal dest = caller Current dest = "
1906 << CurrentDest->getName() << "\n\n");
1907 RangeBegin = RangeEnd = nullptr; // Reset range pointers
1908 };
1909
1910 for (auto &MBB : reverse(MF)) {
1911 bool SeenThrowableInstInBB = false;
1912 for (auto &MI : reverse(MBB)) {
1913 bool MayThrow = WebAssembly::mayThrow(MI);
1914
1915 // If MBB has an EH pad successor and this is the last instruction that
1916 // may throw, this instruction unwinds to the EH pad and not to the
1917 // caller.
1918 if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB)
1919 SeenThrowableInstInBB = true;
1920
1921 // We wrap up the current range when we see a marker even if we haven't
1922 // finished a BB.
1923 else if (RangeEnd && WebAssembly::isMarker(MI.getOpcode()))
1924 RecordCallerMismatchRange(EHPadStack.back());
1925
1926 // If EHPadStack is empty, that means it correctly unwinds to the caller
1927 // if it throws, so we're good. If MI does not throw, we're good too.
1928 else if (EHPadStack.empty() || !MayThrow) {
1929 }
1930
1931 // We found an instruction that unwinds to the caller but currently has an
1932 // incorrect unwind destination. Create a new range or increment the
1933 // currently existing range.
1934 else {
1935 if (!RangeEnd)
1936 RangeBegin = RangeEnd = &MI;
1937 else
1938 RangeBegin = &MI;
1939 }
1940
1941 // Update EHPadStack.
1942 if (WebAssembly::isTry(MI.getOpcode()))
1943 EHPadStack.pop_back();
1944 else if (WebAssembly::isCatch(MI.getOpcode()))
1945 EHPadStack.push_back(MI.getParent());
1946 }
1947
1948 if (RangeEnd)
1949 RecordCallerMismatchRange(EHPadStack.back());
1950 }
1951
1952 assert(EHPadStack.empty());
1953
1954 // We don't have any unwind destination mismatches to resolve.
1955 if (UnwindDestToTryRanges.empty())
1956 return false;
1957
1958 // When end_loop is before end_try_table within the same BB in unwind
1959 // destinations, we should split the end_loop into another BB.
1961 for (auto &[UnwindDest, _] : UnwindDestToTryRanges) {
1962 auto It = EHPadToTry.find(UnwindDest);
1963 // If UnwindDest is the fake caller block, it will not be in EHPadToTry
1964 // map
1965 if (It != EHPadToTry.end()) {
1966 auto *TryTable = It->second;
1967 auto *EndTryTable = BeginToEnd[TryTable];
1968 splitEndLoopBB(EndTryTable->getParent());
1969 }
1970 }
1971
1972 // Now we fix the mismatches by wrapping calls with inner try-delegates.
1973 for (auto &P : UnwindDestToTryRanges) {
1974 NumCallUnwindMismatches += P.second.size();
1975 MachineBasicBlock *UnwindDest = P.first;
1976 auto &TryRanges = P.second;
1977
1978 for (auto Range : TryRanges) {
1979 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1980 std::tie(RangeBegin, RangeEnd) = Range;
1981 auto *MBB = RangeBegin->getParent();
1982
1983 // If this BB has an EH pad successor, i.e., ends with an 'invoke', and if
1984 // the current range contains the invoke, now we are going to wrap the
1985 // invoke with try-delegate or try_table-end_try_table, making the
1986 // 'delegate' or 'end_try_table' BB the new successor instead, so remove
1987 // the EH pad succesor here. The BB may not have an EH pad successor if
1988 // calls in this BB throw to the caller.
1989 if (UnwindDest != getFakeCallerBlock(MF)) {
1990 MachineBasicBlock *EHPad = nullptr;
1991 for (auto *Succ : MBB->successors()) {
1992 if (Succ->isEHPad()) {
1993 EHPad = Succ;
1994 break;
1995 }
1996 }
1997 if (EHPad)
1998 MBB->removeSuccessor(EHPad);
1999 }
2000
2002 addNestedTryDelegate(RangeBegin, RangeEnd, UnwindDest);
2003 else
2004 addNestedTryTable(RangeBegin, RangeEnd, UnwindDest);
2005 }
2006 }
2007
2008 return true;
2009}
2010
2011// Returns the single destination of try_table, if there is one. All try_table
2012// we generate in this pass has a single destination, i.e., a single catch
2013// clause.
2015 if (TryTable->getOperand(1).getImm() != 1)
2016 return nullptr;
2017 switch (TryTable->getOperand(2).getImm()) {
2020 return TryTable->getOperand(4).getMBB();
2023 return TryTable->getOperand(3).getMBB();
2024 default:
2025 llvm_unreachable("try_table: Invalid catch clause\n");
2026 }
2027}
2028
2029bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {
2030 // This function is used for both the legacy EH and the standard (exnref) EH,
2031 // and the reason we have unwind mismatches is the same for the both of them,
2032 // but the code examples in the comments are going to be different. To make
2033 // the description less confusing, we write the basically same comments twice,
2034 // once for the legacy EH and the standard EH.
2035 //
2036 // -- Legacy EH --------------------------------------------------------------
2037 //
2038 // There is another kind of unwind destination mismatches besides call unwind
2039 // mismatches, which we will call "catch unwind mismatches". See this example
2040 // after the marker placement:
2041 // try
2042 // try
2043 // call @foo
2044 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
2045 // ...
2046 // end_try
2047 // catch_all ;; ehpad B
2048 // ...
2049 // end_try
2050 //
2051 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
2052 // throws a foreign exception that is not caught by ehpad A, and its next
2053 // destination should be the caller. But after control flow linearization,
2054 // another EH pad can be placed in between (e.g. ehpad B here), making the
2055 // next unwind destination incorrect. In this case, the foreign exception will
2056 // instead go to ehpad B and will be caught there instead. In this example the
2057 // correct next unwind destination is the caller, but it can be another outer
2058 // catch in other cases.
2059 //
2060 // There is no specific 'call' or 'throw' instruction to wrap with a
2061 // try-delegate, so we wrap the whole try-catch-end with a try-delegate and
2062 // make it rethrow to the right destination, which is the caller in the
2063 // example below:
2064 // try
2065 // try ;; (new)
2066 // try
2067 // call @foo
2068 // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
2069 // ...
2070 // end_try
2071 // delegate 1 (caller) ;; (new)
2072 // catch_all ;; ehpad B
2073 // ...
2074 // end_try
2075 //
2076 // The right destination may be another EH pad or the caller. (The example
2077 // here shows the case it is the caller.)
2078 //
2079 // -- Standard EH ------------------------------------------------------------
2080 //
2081 // There is another kind of unwind destination mismatches besides call unwind
2082 // mismatches, which we will call "catch unwind mismatches". See this example
2083 // after the marker placement:
2084 // block
2085 // try_table (catch_all_ref 0)
2086 // block
2087 // try_table (catch ... 0)
2088 // call @foo
2089 // end_try_table
2090 // end_block ;; ehpad A (next unwind dest: caller)
2091 // ...
2092 // end_try_table
2093 // end_block ;; ehpad B
2094 // ...
2095 //
2096 // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
2097 // throws a foreign exception that is not caught by ehpad A, and its next
2098 // destination should be the caller. But after control flow linearization,
2099 // another EH pad can be placed in between (e.g. ehpad B here), making the
2100 // next unwind destination incorrect. In this case, the foreign exception will
2101 // instead go to ehpad B and will be caught there instead. In this example the
2102 // correct next unwind destination is the caller, but it can be another outer
2103 // catch in other cases.
2104 //
2105 // There is no specific 'call' or 'throw' instruction to wrap with an inner
2106 // try_table-end_try_table, so we wrap the whole try_table-end_try_table with
2107 // an inner try_table-end_try_table that sends the exception to a trampoline
2108 // BB. We rethrow the sent exception using a throw_ref to the right
2109 // destination, which is the caller in the example below:
2110 // block exnref
2111 // block
2112 // try_table (catch_all_ref 0)
2113 // try_table (catch_all_ref 2) ;; (new) to trampoline
2114 // block
2115 // try_table (catch ... 0)
2116 // call @foo
2117 // end_try_table
2118 // end_block ;; ehpad A (next unwind dest: caller)
2119 // end_try_table ;; (new)
2120 // ...
2121 // end_try_table
2122 // end_block ;; ehpad B
2123 // ...
2124 // end_block ;; (new) caller trampoline BB
2125 // throw_ref ;; (new) throw to the caller
2126 //
2127 // The right destination may be another EH pad or the caller. (The example
2128 // here shows the case it is the caller.)
2129
2130 const auto *EHInfo = MF.getWasmEHFuncInfo();
2131 assert(EHInfo);
2133 // For EH pads that have catch unwind mismatches, a map of <EH pad, its
2134 // correct unwind destination>.
2136
2137 for (auto &MBB : reverse(MF)) {
2138 for (auto &MI : reverse(MBB)) {
2139 if (MI.getOpcode() == WebAssembly::TRY)
2140 EHPadStack.pop_back();
2141 else if (MI.getOpcode() == WebAssembly::TRY_TABLE) {
2142 // We want to exclude try_tables created in fixCallUnwindMismatches.
2143 // Check if the try_table's unwind destination matches the EH pad stack
2144 // top. If it is created in fixCallUnwindMismatches, it wouldn't.
2145 if (getSingleUnwindDest(&MI) == EHPadStack.back())
2146 EHPadStack.pop_back();
2147 } else if (MI.getOpcode() == WebAssembly::DELEGATE)
2148 EHPadStack.push_back(&MBB);
2149 else if (WebAssembly::isCatch(MI.getOpcode())) {
2150 auto *EHPad = &MBB;
2151
2152 // If the BB has a catch pseudo instruction but is not marked as an EH
2153 // pad, it's a trampoline BB we created in fixCallUnwindMismatches. Skip
2154 // it.
2155 if (!EHPad->isEHPad())
2156 continue;
2157
2158 // catch_all always catches an exception, so we don't need to do
2159 // anything
2160 if (WebAssembly::isCatchAll(MI.getOpcode())) {
2161 }
2162
2163 // This can happen when the unwind dest was removed during the
2164 // optimization, e.g. because it was unreachable.
2165 else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
2166 LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName()
2167 << "'s unwind destination does not exist anymore"
2168 << "\n\n");
2169 }
2170
2171 // The EHPad's next unwind destination is the caller, but we incorrectly
2172 // unwind to another EH pad.
2173 else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) {
2174 EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
2176 << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()
2177 << " Original dest = caller Current dest = "
2178 << EHPadStack.back()->getName() << "\n\n");
2179 }
2180
2181 // The EHPad's next unwind destination is an EH pad, whereas we
2182 // incorrectly unwind to another EH pad.
2183 else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
2184 auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
2185 if (EHPadStack.back() != UnwindDest) {
2186 EHPadToUnwindDest[EHPad] = UnwindDest;
2187 LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "
2188 << EHPad->getName() << " Original dest = "
2189 << UnwindDest->getName() << " Current dest = "
2190 << EHPadStack.back()->getName() << "\n\n");
2191 }
2192 }
2193
2194 EHPadStack.push_back(EHPad);
2195 }
2196 }
2197 }
2198
2199 assert(EHPadStack.empty());
2200 if (EHPadToUnwindDest.empty())
2201 return false;
2202
2203 // When end_loop is before end_try_table within the same BB in unwind
2204 // destinations, we should split the end_loop into another BB.
2205 for (auto &[_, UnwindDest] : EHPadToUnwindDest) {
2206 auto It = EHPadToTry.find(UnwindDest);
2207 // If UnwindDest is the fake caller block, it will not be in EHPadToTry map
2208 if (It != EHPadToTry.end()) {
2209 auto *TryTable = It->second;
2210 auto *EndTryTable = BeginToEnd[TryTable];
2211 splitEndLoopBB(EndTryTable->getParent());
2212 }
2213 }
2214
2215 NumCatchUnwindMismatches += EHPadToUnwindDest.size();
2217
2218 for (auto &[EHPad, UnwindDest] : EHPadToUnwindDest) {
2219 MachineInstr *Try = EHPadToTry[EHPad];
2220 MachineInstr *EndTry = BeginToEnd[Try];
2222 addNestedTryDelegate(Try, EndTry, UnwindDest);
2223 NewEndTryBBs.insert(EndTry->getParent());
2224 } else {
2225 addNestedTryTable(Try, EndTry, UnwindDest);
2226 }
2227 }
2228
2230 return true;
2231
2232 // Adding a try-delegate wrapping an existing try-catch-end can make existing
2233 // branch destination BBs invalid. For example,
2234 //
2235 // - Before:
2236 // bb0:
2237 // block
2238 // br bb3
2239 // bb1:
2240 // try
2241 // ...
2242 // bb2: (ehpad)
2243 // catch
2244 // bb3:
2245 // end_try
2246 // end_block ;; 'br bb3' targets here
2247 //
2248 // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap
2249 // this with a try-delegate. Then this becomes:
2250 //
2251 // - After:
2252 // bb0:
2253 // block
2254 // br bb3 ;; invalid destination!
2255 // bb1:
2256 // try ;; (new instruction)
2257 // try
2258 // ...
2259 // bb2: (ehpad)
2260 // catch
2261 // bb3:
2262 // end_try ;; 'br bb3' still incorrectly targets here!
2263 // delegate_bb: ;; (new BB)
2264 // delegate ;; (new instruction)
2265 // split_bb: ;; (new BB)
2266 // end_block
2267 //
2268 // Now 'br bb3' incorrectly branches to an inner scope.
2269 //
2270 // As we can see in this case, when branches target a BB that has both
2271 // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we
2272 // have to remap existing branch destinations so that they target not the
2273 // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's
2274 // in between, so we try to find the next BB with 'end_block' instruction. In
2275 // this example, the 'br bb3' instruction should be remapped to 'br split_bb'.
2276 for (auto &MBB : MF) {
2277 for (auto &MI : MBB) {
2278 if (MI.isTerminator()) {
2279 for (auto &MO : MI.operands()) {
2280 if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) {
2281 auto *BrDest = MO.getMBB();
2282 bool FoundEndBlock = false;
2283 for (; std::next(BrDest->getIterator()) != MF.end();
2284 BrDest = BrDest->getNextNode()) {
2285 for (const auto &MI : *BrDest) {
2286 if (MI.getOpcode() == WebAssembly::END_BLOCK) {
2287 FoundEndBlock = true;
2288 break;
2289 }
2290 }
2291 if (FoundEndBlock)
2292 break;
2293 }
2294 assert(FoundEndBlock);
2295 MO.setMBB(BrDest);
2296 }
2297 }
2298 }
2299 }
2300 }
2301
2302 return true;
2303}
2304
2305void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {
2306 // Renumber BBs and recalculate ScopeTop info because new BBs might have been
2307 // created and inserted during fixing unwind mismatches.
2308 MF.RenumberBlocks();
2309 MDT->updateBlockNumbers();
2310 ScopeTops.clear();
2311 ScopeTops.resize(MF.getNumBlockIDs());
2312 for (auto &MBB : reverse(MF)) {
2313 for (auto &MI : reverse(MBB)) {
2314 if (ScopeTops[MBB.getNumber()])
2315 break;
2316 switch (MI.getOpcode()) {
2317 case WebAssembly::END_BLOCK:
2318 case WebAssembly::END_LOOP:
2319 case WebAssembly::END_TRY:
2320 case WebAssembly::END_TRY_TABLE:
2321 case WebAssembly::DELEGATE:
2322 updateScopeTops(EndToBegin[&MI]->getParent(), &MBB);
2323 break;
2324 case WebAssembly::CATCH_LEGACY:
2325 case WebAssembly::CATCH_ALL_LEGACY:
2326 updateScopeTops(EHPadToTry[&MBB]->getParent(), &MBB);
2327 break;
2328 }
2329 }
2330 }
2331}
2332
2333/// In normal assembly languages, when the end of a function is unreachable,
2334/// because the function ends in an infinite loop or a noreturn call or similar,
2335/// it isn't necessary to worry about the function return type at the end of
2336/// the function, because it's never reached. However, in WebAssembly, blocks
2337/// that end at the function end need to have a return type signature that
2338/// matches the function signature, even though it's unreachable. This function
2339/// checks for such cases and fixes up the signatures.
2340void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
2341 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
2342
2343 if (MFI.getResults().empty())
2344 return;
2345
2346 // MCInstLower will add the proper types to multivalue signatures based on the
2347 // function return type
2348 WebAssembly::BlockType RetType =
2349 MFI.getResults().size() > 1
2350 ? WebAssembly::BlockType::Multivalue
2352 WebAssembly::toValType(MFI.getResults().front()));
2353
2355 Worklist.push_back(MF.rbegin()->rbegin());
2356
2358 auto *MBB = It->getParent();
2359 while (It != MBB->rend()) {
2360 MachineInstr &MI = *It++;
2361 if (MI.isPosition() || MI.isDebugInstr())
2362 continue;
2363 switch (MI.getOpcode()) {
2364 case WebAssembly::END_TRY: {
2365 // If a 'try''s return type is fixed, both its try body and catch body
2366 // should satisfy the return type, so we need to search 'end'
2367 // instructions before its corresponding 'catch' too.
2368 auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]);
2369 assert(EHPad);
2370 auto NextIt =
2371 std::next(WebAssembly::findCatch(EHPad)->getReverseIterator());
2372 if (NextIt != EHPad->rend())
2373 Worklist.push_back(NextIt);
2374 [[fallthrough]];
2375 }
2376 case WebAssembly::END_BLOCK:
2377 case WebAssembly::END_LOOP:
2378 case WebAssembly::END_TRY_TABLE:
2379 case WebAssembly::DELEGATE:
2380 EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
2381 continue;
2382 default:
2383 // Something other than an `end`. We're done for this BB.
2384 return;
2385 }
2386 }
2387 // We've reached the beginning of a BB. Continue the search in the previous
2388 // BB.
2389 Worklist.push_back(MBB->getPrevNode()->rbegin());
2390 };
2391
2392 while (!Worklist.empty())
2393 Process(Worklist.pop_back_val());
2394}
2395
2396// WebAssembly functions end with an end instruction, as if the function body
2397// were a block.
2399 const WebAssemblyInstrInfo &TII) {
2400 BuildMI(MF.back(), MF.back().end(),
2401 MF.back().findPrevDebugLoc(MF.back().end()),
2402 TII.get(WebAssembly::END_FUNCTION));
2403}
2404
2405// We added block~end_block and try_table~end_try_table markers in
2406// placeTryTableMarker. But When catch clause's destination has a return type,
2407// as in the case of catch with a concrete tag, catch_ref, and catch_all_ref.
2408// For example:
2409// block exnref
2410// try_table (catch_all_ref 0)
2411// ...
2412// end_try_table
2413// end_block
2414// ... use exnref ...
2415//
2416// This code is not valid because the block's body type is not exnref. So we add
2417// an unreachable after the 'end_try_table' to make the code valid here:
2418// block exnref
2419// try_table (catch_all_ref 0)
2420// ...
2421// end_try_table
2422// unreachable (new)
2423// end_block
2424//
2425// Because 'unreachable' is a terminator we also need to split the BB.
2427 const WebAssemblyInstrInfo &TII) {
2428 std::vector<MachineInstr *> EndTryTables;
2429 for (auto &MBB : MF)
2430 for (auto &MI : MBB)
2431 if (MI.getOpcode() == WebAssembly::END_TRY_TABLE)
2432 EndTryTables.push_back(&MI);
2433
2434 for (auto *EndTryTable : EndTryTables) {
2435 auto *MBB = EndTryTable->getParent();
2436 auto *NewEndTryTableBB = MF.CreateMachineBasicBlock();
2437 MF.insert(MBB->getIterator(), NewEndTryTableBB);
2438 auto SplitPos = std::next(EndTryTable->getIterator());
2439 NewEndTryTableBB->splice(NewEndTryTableBB->end(), MBB, MBB->begin(),
2440 SplitPos);
2441 NewEndTryTableBB->addSuccessor(MBB);
2442 BuildMI(NewEndTryTableBB, EndTryTable->getDebugLoc(),
2443 TII.get(WebAssembly::UNREACHABLE));
2444 }
2445}
2446
2447/// Insert BLOCK/LOOP/TRY/TRY_TABLE markers at appropriate places.
2448void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
2449 // We allocate one more than the number of blocks in the function to
2450 // accommodate for the possible fake block we may insert at the end.
2451 ScopeTops.resize(MF.getNumBlockIDs() + 1);
2452 // Place the LOOP for MBB if MBB is the header of a loop.
2453 for (auto &MBB : MF)
2454 placeLoopMarker(MBB);
2455
2456 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
2457 for (auto &MBB : MF) {
2458 if (MBB.isEHPad()) {
2459 // Place the TRY/TRY_TABLE for MBB if MBB is the EH pad of an exception.
2460 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2461 MF.getFunction().hasPersonalityFn()) {
2463 placeTryMarker(MBB);
2464 else
2465 placeTryTableMarker(MBB);
2466 }
2467 } else {
2468 // Place the BLOCK for MBB if MBB is branched to from above.
2469 placeBlockMarker(MBB);
2470 }
2471 }
2472
2473 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2474 MF.getFunction().hasPersonalityFn()) {
2475 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
2476 // Add an 'unreachable' after 'end_try_table's.
2478 // Fix mismatches in unwind destinations induced by linearizing the code.
2479 fixCallUnwindMismatches(MF);
2480 fixCatchUnwindMismatches(MF);
2481 // addUnreachableAfterTryTables and fixUnwindMismatches create new BBs, so
2482 // we need to recalculate ScopeTops.
2483 recalculateScopeTops(MF);
2484 }
2485}
2486
2487unsigned WebAssemblyCFGStackify::getBranchDepth(
2489 unsigned Depth = 0;
2490 for (auto X : reverse(Stack)) {
2491 if (X.first == MBB)
2492 break;
2493 ++Depth;
2494 }
2495 assert(Depth < Stack.size() && "Branch destination should be in scope");
2496 return Depth;
2497}
2498
2499unsigned WebAssemblyCFGStackify::getDelegateDepth(
2501 if (MBB == FakeCallerBB)
2502 return Stack.size();
2503 // Delegate's destination is either a catch or a another delegate BB. When the
2504 // destination is another delegate, we can compute the argument in the same
2505 // way as branches, because the target delegate BB only contains the single
2506 // delegate instruction.
2507 if (!MBB->isEHPad()) // Target is a delegate BB
2508 return getBranchDepth(Stack, MBB);
2509
2510 // When the delegate's destination is a catch BB, we need to use its
2511 // corresponding try's end_try BB because Stack contains each marker's end BB.
2512 // Also we need to check if the end marker instruction matches, because a
2513 // single BB can contain multiple end markers, like this:
2514 // bb:
2515 // END_BLOCK
2516 // END_TRY
2517 // END_BLOCK
2518 // END_TRY
2519 // ...
2520 //
2521 // In case of branches getting the immediate that targets any of these is
2522 // fine, but delegate has to exactly target the correct try.
2523 unsigned Depth = 0;
2524 const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];
2525 for (auto X : reverse(Stack)) {
2526 if (X.first == EndTry->getParent() && X.second == EndTry)
2527 break;
2528 ++Depth;
2529 }
2530 assert(Depth < Stack.size() && "Delegate destination should be in scope");
2531 return Depth;
2532}
2533
2534unsigned WebAssemblyCFGStackify::getRethrowDepth(
2535 const SmallVectorImpl<EndMarkerInfo> &Stack,
2536 const MachineBasicBlock *EHPadToRethrow) {
2537 unsigned Depth = 0;
2538 for (auto X : reverse(Stack)) {
2539 const MachineInstr *End = X.second;
2540 if (End->getOpcode() == WebAssembly::END_TRY) {
2541 auto *EHPad = TryToEHPad[EndToBegin[End]];
2542 if (EHPadToRethrow == EHPad)
2543 break;
2544 }
2545 ++Depth;
2546 }
2547 assert(Depth < Stack.size() && "Rethrow destination should be in scope");
2548 return Depth;
2549}
2550
2551void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
2552 // Now rewrite references to basic blocks to be depth immediates.
2554
2555 auto RewriteOperands = [&](MachineInstr &MI) {
2556 // Rewrite MBB operands to be depth immediates.
2557 SmallVector<MachineOperand, 4> Ops(MI.operands());
2558 while (MI.getNumOperands() > 0)
2559 MI.removeOperand(MI.getNumOperands() - 1);
2560 for (auto MO : Ops) {
2561 if (MO.isMBB()) {
2562 if (MI.getOpcode() == WebAssembly::DELEGATE)
2563 MO = MachineOperand::CreateImm(getDelegateDepth(Stack, MO.getMBB()));
2564 else if (MI.getOpcode() == WebAssembly::RETHROW)
2565 MO = MachineOperand::CreateImm(getRethrowDepth(Stack, MO.getMBB()));
2566 else
2567 MO = MachineOperand::CreateImm(getBranchDepth(Stack, MO.getMBB()));
2568 }
2569 MI.addOperand(MF, MO);
2570 }
2571 };
2572
2573 for (auto &MBB : reverse(MF)) {
2574 for (MachineInstr &MI : llvm::reverse(MBB)) {
2575 switch (MI.getOpcode()) {
2576 case WebAssembly::BLOCK:
2577 case WebAssembly::TRY:
2578 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2579 MBB.getNumber() &&
2580 "Block/try/try_table marker should be balanced");
2581 Stack.pop_back();
2582 break;
2583
2584 case WebAssembly::TRY_TABLE:
2585 assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
2586 MBB.getNumber() &&
2587 "Block/try/try_table marker should be balanced");
2588 Stack.pop_back();
2589 RewriteOperands(MI);
2590 break;
2591
2592 case WebAssembly::LOOP:
2593 assert(Stack.back().first == &MBB && "Loop top should be balanced");
2594 Stack.pop_back();
2595 break;
2596
2597 case WebAssembly::END_BLOCK:
2598 case WebAssembly::END_TRY:
2599 case WebAssembly::END_TRY_TABLE:
2600 Stack.push_back(std::make_pair(&MBB, &MI));
2601 break;
2602
2603 case WebAssembly::END_LOOP:
2604 Stack.push_back(std::make_pair(EndToBegin[&MI]->getParent(), &MI));
2605 break;
2606
2607 case WebAssembly::DELEGATE:
2608 RewriteOperands(MI);
2609 Stack.push_back(std::make_pair(&MBB, &MI));
2610 break;
2611
2612 default:
2613 if (MI.isTerminator())
2614 RewriteOperands(MI);
2615 break;
2616 }
2617 }
2618 }
2619 assert(Stack.empty() && "Control flow should be balanced");
2620}
2621
2622void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) {
2623 if (FakeCallerBB)
2624 MF.deleteMachineBasicBlock(FakeCallerBB);
2625 AppendixBB = FakeCallerBB = CallerTrampolineBB = nullptr;
2626}
2627
2628void WebAssemblyCFGStackify::releaseMemory() {
2629 ScopeTops.clear();
2630 BeginToEnd.clear();
2631 EndToBegin.clear();
2632 TryToEHPad.clear();
2633 EHPadToTry.clear();
2634 UnwindDestToTrampoline.clear();
2635}
2636
2637bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
2638 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
2639 "********** Function: "
2640 << MF.getName() << '\n');
2641 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
2642 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
2643
2644 releaseMemory();
2645
2646 // Liveness is not tracked for VALUE_STACK physreg.
2648
2649 // Place the BLOCK/LOOP/TRY/TRY_TABLE markers to indicate the beginnings of
2650 // scopes.
2651 placeMarkers(MF);
2652
2653 // Remove unnecessary instructions possibly introduced by try/end_trys.
2654 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
2656 removeUnnecessaryInstrs(MF);
2657
2658 // Convert MBB operands in terminators to relative depth immediates.
2659 rewriteDepthImmediates(MF);
2660
2661 // Fix up block/loop/try/try_table signatures at the end of the function to
2662 // conform to WebAssembly's rules.
2663 fixEndsAtEndOfFunction(MF);
2664
2665 // Add an end instruction at the end of the function body.
2666 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
2668
2669 cleanupFunctionData(MF);
2670
2671 MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
2672 return true;
2673}
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 void addUnreachableAfterTryTables(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
static MachineBasicBlock::iterator getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, const Container &AfterSet)
static void splitEndLoopBB(MachineBasicBlock *EndTryTableBB)
static void appendEndToFunction(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
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:642
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.
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
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:71
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:577
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:349
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:501
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:587
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)
cl::opt< bool > WasmUseLegacyEH
MachineInstr * findCatch(MachineBasicBlock *EHPad)
Find a catch instruction from an EH pad.
bool isCatch(unsigned Opc)
bool isTee(unsigned Opc)
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()