[x86] fix assert with horizontal math + broadcast of vector (PR43402)
[llvm-core.git] / lib / Target / WebAssembly / WebAssemblyCFGStackify.cpp
blob6c38dead9ae09e884027a1ab4d7b82baabad1a78
1 //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file implements a CFG stacking pass.
11 ///
12 /// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes,
13 /// since scope boundaries serve as the labels for WebAssembly's control
14 /// transfers.
15 ///
16 /// This is sufficient to convert arbitrary CFGs into a form that works on
17 /// WebAssembly, provided that all loops are single-entry.
18 ///
19 /// In case we use exceptions, this pass also fixes mismatches in unwind
20 /// destinations created during transforming CFG into wasm structured format.
21 ///
22 //===----------------------------------------------------------------------===//
24 #include "WebAssembly.h"
25 #include "WebAssemblyExceptionInfo.h"
26 #include "WebAssemblyMachineFunctionInfo.h"
27 #include "WebAssemblySubtarget.h"
28 #include "WebAssemblyUtilities.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/CodeGen/MachineDominators.h"
31 #include "llvm/CodeGen/MachineInstrBuilder.h"
32 #include "llvm/MC/MCAsmInfo.h"
33 using namespace llvm;
35 #define DEBUG_TYPE "wasm-cfg-stackify"
37 STATISTIC(NumUnwindMismatches, "Number of EH pad unwind mismatches found");
39 namespace {
40 class WebAssemblyCFGStackify final : public MachineFunctionPass {
41 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
43 void getAnalysisUsage(AnalysisUsage &AU) const override {
44 AU.addRequired<MachineDominatorTree>();
45 AU.addRequired<MachineLoopInfo>();
46 AU.addRequired<WebAssemblyExceptionInfo>();
47 MachineFunctionPass::getAnalysisUsage(AU);
50 bool runOnMachineFunction(MachineFunction &MF) override;
52 // For each block whose label represents the end of a scope, record the block
53 // which holds the beginning of the scope. This will allow us to quickly skip
54 // over scoped regions when walking blocks.
55 SmallVector<MachineBasicBlock *, 8> ScopeTops;
57 // Placing markers.
58 void placeMarkers(MachineFunction &MF);
59 void placeBlockMarker(MachineBasicBlock &MBB);
60 void placeLoopMarker(MachineBasicBlock &MBB);
61 void placeTryMarker(MachineBasicBlock &MBB);
62 void removeUnnecessaryInstrs(MachineFunction &MF);
63 bool fixUnwindMismatches(MachineFunction &MF);
64 void rewriteDepthImmediates(MachineFunction &MF);
65 void fixEndsAtEndOfFunction(MachineFunction &MF);
67 // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY).
68 DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd;
69 // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY.
70 DenseMap<const MachineInstr *, MachineInstr *> EndToBegin;
71 // <TRY marker, EH pad> map
72 DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad;
73 // <EH pad, TRY marker> map
74 DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry;
76 // There can be an appendix block at the end of each function, shared for:
77 // - creating a correct signature for fallthrough returns
78 // - target for rethrows that need to unwind to the caller, but are trapped
79 // inside another try/catch
80 MachineBasicBlock *AppendixBB = nullptr;
81 MachineBasicBlock *getAppendixBlock(MachineFunction &MF) {
82 if (!AppendixBB) {
83 AppendixBB = MF.CreateMachineBasicBlock();
84 // Give it a fake predecessor so that AsmPrinter prints its label.
85 AppendixBB->addSuccessor(AppendixBB);
86 MF.push_back(AppendixBB);
88 return AppendixBB;
91 // Helper functions to register / unregister scope information created by
92 // marker instructions.
93 void registerScope(MachineInstr *Begin, MachineInstr *End);
94 void registerTryScope(MachineInstr *Begin, MachineInstr *End,
95 MachineBasicBlock *EHPad);
96 void unregisterScope(MachineInstr *Begin);
98 public:
99 static char ID; // Pass identification, replacement for typeid
100 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
101 ~WebAssemblyCFGStackify() override { releaseMemory(); }
102 void releaseMemory() override;
104 } // end anonymous namespace
106 char WebAssemblyCFGStackify::ID = 0;
107 INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,
108 "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false,
109 false)
111 FunctionPass *llvm::createWebAssemblyCFGStackify() {
112 return new WebAssemblyCFGStackify();
115 /// Test whether Pred has any terminators explicitly branching to MBB, as
116 /// opposed to falling through. Note that it's possible (eg. in unoptimized
117 /// code) for a branch instruction to both branch to a block and fallthrough
118 /// to it, so we check the actual branch operands to see if there are any
119 /// explicit mentions.
120 static bool explicitlyBranchesTo(MachineBasicBlock *Pred,
121 MachineBasicBlock *MBB) {
122 for (MachineInstr &MI : Pred->terminators())
123 for (MachineOperand &MO : MI.explicit_operands())
124 if (MO.isMBB() && MO.getMBB() == MBB)
125 return true;
126 return false;
129 // Returns an iterator to the earliest position possible within the MBB,
130 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
131 // contains instructions that should go before the marker, and AfterSet contains
132 // ones that should go after the marker. In this function, AfterSet is only
133 // used for sanity checking.
134 static MachineBasicBlock::iterator
135 getEarliestInsertPos(MachineBasicBlock *MBB,
136 const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
137 const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
138 auto InsertPos = MBB->end();
139 while (InsertPos != MBB->begin()) {
140 if (BeforeSet.count(&*std::prev(InsertPos))) {
141 #ifndef NDEBUG
142 // Sanity check
143 for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
144 assert(!AfterSet.count(&*std::prev(Pos)));
145 #endif
146 break;
148 --InsertPos;
150 return InsertPos;
153 // Returns an iterator to the latest position possible within the MBB,
154 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
155 // contains instructions that should go before the marker, and AfterSet contains
156 // ones that should go after the marker. In this function, BeforeSet is only
157 // used for sanity checking.
158 static MachineBasicBlock::iterator
159 getLatestInsertPos(MachineBasicBlock *MBB,
160 const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
161 const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
162 auto InsertPos = MBB->begin();
163 while (InsertPos != MBB->end()) {
164 if (AfterSet.count(&*InsertPos)) {
165 #ifndef NDEBUG
166 // Sanity check
167 for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
168 assert(!BeforeSet.count(&*Pos));
169 #endif
170 break;
172 ++InsertPos;
174 return InsertPos;
177 void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
178 MachineInstr *End) {
179 BeginToEnd[Begin] = End;
180 EndToBegin[End] = Begin;
183 void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
184 MachineInstr *End,
185 MachineBasicBlock *EHPad) {
186 registerScope(Begin, End);
187 TryToEHPad[Begin] = EHPad;
188 EHPadToTry[EHPad] = Begin;
191 void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
192 assert(BeginToEnd.count(Begin));
193 MachineInstr *End = BeginToEnd[Begin];
194 assert(EndToBegin.count(End));
195 BeginToEnd.erase(Begin);
196 EndToBegin.erase(End);
197 MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
198 if (EHPad) {
199 assert(EHPadToTry.count(EHPad));
200 TryToEHPad.erase(Begin);
201 EHPadToTry.erase(EHPad);
205 /// Insert a BLOCK marker for branches to MBB (if needed).
206 // TODO Consider a more generalized way of handling block (and also loop and
207 // try) signatures when we implement the multi-value proposal later.
208 void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
209 assert(!MBB.isEHPad());
210 MachineFunction &MF = *MBB.getParent();
211 auto &MDT = getAnalysis<MachineDominatorTree>();
212 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
213 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
215 // First compute the nearest common dominator of all forward non-fallthrough
216 // predecessors so that we minimize the time that the BLOCK is on the stack,
217 // which reduces overall stack height.
218 MachineBasicBlock *Header = nullptr;
219 bool IsBranchedTo = false;
220 bool IsBrOnExn = false;
221 MachineInstr *BrOnExn = nullptr;
222 int MBBNumber = MBB.getNumber();
223 for (MachineBasicBlock *Pred : MBB.predecessors()) {
224 if (Pred->getNumber() < MBBNumber) {
225 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
226 if (explicitlyBranchesTo(Pred, &MBB)) {
227 IsBranchedTo = true;
228 if (Pred->getFirstTerminator()->getOpcode() == WebAssembly::BR_ON_EXN) {
229 IsBrOnExn = true;
230 assert(!BrOnExn && "There should be only one br_on_exn per block");
231 BrOnExn = &*Pred->getFirstTerminator();
236 if (!Header)
237 return;
238 if (!IsBranchedTo)
239 return;
241 assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
242 MachineBasicBlock *LayoutPred = MBB.getPrevNode();
244 // If the nearest common dominator is inside a more deeply nested context,
245 // walk out to the nearest scope which isn't more deeply nested.
246 for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
247 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
248 if (ScopeTop->getNumber() > Header->getNumber()) {
249 // Skip over an intervening scope.
250 I = std::next(ScopeTop->getIterator());
251 } else {
252 // We found a scope level at an appropriate depth.
253 Header = ScopeTop;
254 break;
259 // Decide where in Header to put the BLOCK.
261 // Instructions that should go before the BLOCK.
262 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
263 // Instructions that should go after the BLOCK.
264 SmallPtrSet<const MachineInstr *, 4> AfterSet;
265 for (const auto &MI : *Header) {
266 // If there is a previously placed LOOP marker and the bottom block of the
267 // loop is above MBB, it should be after the BLOCK, because the loop is
268 // nested in this BLOCK. Otherwise it should be before the BLOCK.
269 if (MI.getOpcode() == WebAssembly::LOOP) {
270 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
271 if (MBB.getNumber() > LoopBottom->getNumber())
272 AfterSet.insert(&MI);
273 #ifndef NDEBUG
274 else
275 BeforeSet.insert(&MI);
276 #endif
279 // All previously inserted BLOCK/TRY markers should be after the BLOCK
280 // because they are all nested blocks.
281 if (MI.getOpcode() == WebAssembly::BLOCK ||
282 MI.getOpcode() == WebAssembly::TRY)
283 AfterSet.insert(&MI);
285 #ifndef NDEBUG
286 // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK.
287 if (MI.getOpcode() == WebAssembly::END_BLOCK ||
288 MI.getOpcode() == WebAssembly::END_LOOP ||
289 MI.getOpcode() == WebAssembly::END_TRY)
290 BeforeSet.insert(&MI);
291 #endif
293 // Terminators should go after the BLOCK.
294 if (MI.isTerminator())
295 AfterSet.insert(&MI);
298 // Local expression tree should go after the BLOCK.
299 for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
300 --I) {
301 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
302 continue;
303 if (WebAssembly::isChild(*std::prev(I), MFI))
304 AfterSet.insert(&*std::prev(I));
305 else
306 break;
309 // Add the BLOCK.
311 // 'br_on_exn' extracts exnref object and pushes variable number of values
312 // depending on its tag. For C++ exception, its a single i32 value, and the
313 // generated code will be in the form of:
314 // block i32
315 // br_on_exn 0, $__cpp_exception
316 // rethrow
317 // end_block
318 WebAssembly::ExprType ReturnType = WebAssembly::ExprType::Void;
319 if (IsBrOnExn) {
320 const char *TagName = BrOnExn->getOperand(1).getSymbolName();
321 if (std::strcmp(TagName, "__cpp_exception") != 0)
322 llvm_unreachable("Only C++ exception is supported");
323 ReturnType = WebAssembly::ExprType::I32;
326 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
327 MachineInstr *Begin =
328 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
329 TII.get(WebAssembly::BLOCK))
330 .addImm(int64_t(ReturnType));
332 // Decide where in Header to put the END_BLOCK.
333 BeforeSet.clear();
334 AfterSet.clear();
335 for (auto &MI : MBB) {
336 #ifndef NDEBUG
337 // END_BLOCK should precede existing LOOP and TRY markers.
338 if (MI.getOpcode() == WebAssembly::LOOP ||
339 MI.getOpcode() == WebAssembly::TRY)
340 AfterSet.insert(&MI);
341 #endif
343 // If there is a previously placed END_LOOP marker and the header of the
344 // loop is above this block's header, the END_LOOP should be placed after
345 // the BLOCK, because the loop contains this block. Otherwise the END_LOOP
346 // should be placed before the BLOCK. The same for END_TRY.
347 if (MI.getOpcode() == WebAssembly::END_LOOP ||
348 MI.getOpcode() == WebAssembly::END_TRY) {
349 if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
350 BeforeSet.insert(&MI);
351 #ifndef NDEBUG
352 else
353 AfterSet.insert(&MI);
354 #endif
358 // Mark the end of the block.
359 InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
360 MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
361 TII.get(WebAssembly::END_BLOCK));
362 registerScope(Begin, End);
364 // Track the farthest-spanning scope that ends at this point.
365 int Number = MBB.getNumber();
366 if (!ScopeTops[Number] ||
367 ScopeTops[Number]->getNumber() > Header->getNumber())
368 ScopeTops[Number] = Header;
371 /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
372 void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
373 MachineFunction &MF = *MBB.getParent();
374 const auto &MLI = getAnalysis<MachineLoopInfo>();
375 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
377 MachineLoop *Loop = MLI.getLoopFor(&MBB);
378 if (!Loop || Loop->getHeader() != &MBB)
379 return;
381 // The operand of a LOOP is the first block after the loop. If the loop is the
382 // bottom of the function, insert a dummy block at the end.
383 MachineBasicBlock *Bottom = WebAssembly::getBottom(Loop);
384 auto Iter = std::next(Bottom->getIterator());
385 if (Iter == MF.end()) {
386 getAppendixBlock(MF);
387 Iter = std::next(Bottom->getIterator());
389 MachineBasicBlock *AfterLoop = &*Iter;
391 // Decide where in Header to put the LOOP.
392 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
393 SmallPtrSet<const MachineInstr *, 4> AfterSet;
394 for (const auto &MI : MBB) {
395 // LOOP marker should be after any existing loop that ends here. Otherwise
396 // we assume the instruction belongs to the loop.
397 if (MI.getOpcode() == WebAssembly::END_LOOP)
398 BeforeSet.insert(&MI);
399 #ifndef NDEBUG
400 else
401 AfterSet.insert(&MI);
402 #endif
405 // Mark the beginning of the loop.
406 auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
407 MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),
408 TII.get(WebAssembly::LOOP))
409 .addImm(int64_t(WebAssembly::ExprType::Void));
411 // Decide where in Header to put the END_LOOP.
412 BeforeSet.clear();
413 AfterSet.clear();
414 #ifndef NDEBUG
415 for (const auto &MI : MBB)
416 // Existing END_LOOP markers belong to parent loops of this loop
417 if (MI.getOpcode() == WebAssembly::END_LOOP)
418 AfterSet.insert(&MI);
419 #endif
421 // Mark the end of the loop (using arbitrary debug location that branched to
422 // the loop end as its location).
423 InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet);
424 DebugLoc EndDL = AfterLoop->pred_empty()
425 ? DebugLoc()
426 : (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
427 MachineInstr *End =
428 BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP));
429 registerScope(Begin, End);
431 assert((!ScopeTops[AfterLoop->getNumber()] ||
432 ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
433 "With block sorting the outermost loop for a block should be first.");
434 if (!ScopeTops[AfterLoop->getNumber()])
435 ScopeTops[AfterLoop->getNumber()] = &MBB;
438 void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
439 assert(MBB.isEHPad());
440 MachineFunction &MF = *MBB.getParent();
441 auto &MDT = getAnalysis<MachineDominatorTree>();
442 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
443 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
444 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
446 // Compute the nearest common dominator of all unwind predecessors
447 MachineBasicBlock *Header = nullptr;
448 int MBBNumber = MBB.getNumber();
449 for (auto *Pred : MBB.predecessors()) {
450 if (Pred->getNumber() < MBBNumber) {
451 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
452 assert(!explicitlyBranchesTo(Pred, &MBB) &&
453 "Explicit branch to an EH pad!");
456 if (!Header)
457 return;
459 // If this try is at the bottom of the function, insert a dummy block at the
460 // end.
461 WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
462 assert(WE);
463 MachineBasicBlock *Bottom = WebAssembly::getBottom(WE);
465 auto Iter = std::next(Bottom->getIterator());
466 if (Iter == MF.end()) {
467 getAppendixBlock(MF);
468 Iter = std::next(Bottom->getIterator());
470 MachineBasicBlock *Cont = &*Iter;
472 assert(Cont != &MF.front());
473 MachineBasicBlock *LayoutPred = Cont->getPrevNode();
475 // If the nearest common dominator is inside a more deeply nested context,
476 // walk out to the nearest scope which isn't more deeply nested.
477 for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
478 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
479 if (ScopeTop->getNumber() > Header->getNumber()) {
480 // Skip over an intervening scope.
481 I = std::next(ScopeTop->getIterator());
482 } else {
483 // We found a scope level at an appropriate depth.
484 Header = ScopeTop;
485 break;
490 // Decide where in Header to put the TRY.
492 // Instructions that should go before the TRY.
493 SmallPtrSet<const MachineInstr *, 4> BeforeSet;
494 // Instructions that should go after the TRY.
495 SmallPtrSet<const MachineInstr *, 4> AfterSet;
496 for (const auto &MI : *Header) {
497 // If there is a previously placed LOOP marker and the bottom block of the
498 // loop is above MBB, it should be after the TRY, because the loop is nested
499 // in this TRY. Otherwise it should be before the TRY.
500 if (MI.getOpcode() == WebAssembly::LOOP) {
501 auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
502 if (MBB.getNumber() > LoopBottom->getNumber())
503 AfterSet.insert(&MI);
504 #ifndef NDEBUG
505 else
506 BeforeSet.insert(&MI);
507 #endif
510 // All previously inserted BLOCK/TRY markers should be after the TRY because
511 // they are all nested trys.
512 if (MI.getOpcode() == WebAssembly::BLOCK ||
513 MI.getOpcode() == WebAssembly::TRY)
514 AfterSet.insert(&MI);
516 #ifndef NDEBUG
517 // All END_(BLOCK/LOOP/TRY) markers should be before the TRY.
518 if (MI.getOpcode() == WebAssembly::END_BLOCK ||
519 MI.getOpcode() == WebAssembly::END_LOOP ||
520 MI.getOpcode() == WebAssembly::END_TRY)
521 BeforeSet.insert(&MI);
522 #endif
524 // Terminators should go after the TRY.
525 if (MI.isTerminator())
526 AfterSet.insert(&MI);
529 // Local expression tree should go after the TRY.
530 for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
531 --I) {
532 if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
533 continue;
534 if (WebAssembly::isChild(*std::prev(I), MFI))
535 AfterSet.insert(&*std::prev(I));
536 else
537 break;
540 // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
541 // contain the call within it. So the call should go after the TRY. The
542 // exception is when the header's terminator is a rethrow instruction, in
543 // which case that instruction, not a call instruction before it, is gonna
544 // throw.
545 if (MBB.isPredecessor(Header)) {
546 auto TermPos = Header->getFirstTerminator();
547 if (TermPos == Header->end() ||
548 TermPos->getOpcode() != WebAssembly::RETHROW) {
549 for (const auto &MI : reverse(*Header)) {
550 if (MI.isCall()) {
551 AfterSet.insert(&MI);
552 // Possibly throwing calls are usually wrapped by EH_LABEL
553 // instructions. We don't want to split them and the call.
554 if (MI.getIterator() != Header->begin() &&
555 std::prev(MI.getIterator())->isEHLabel())
556 AfterSet.insert(&*std::prev(MI.getIterator()));
557 break;
563 // Add the TRY.
564 auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
565 MachineInstr *Begin =
566 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
567 TII.get(WebAssembly::TRY))
568 .addImm(int64_t(WebAssembly::ExprType::Void));
570 // Decide where in Header to put the END_TRY.
571 BeforeSet.clear();
572 AfterSet.clear();
573 for (const auto &MI : *Cont) {
574 #ifndef NDEBUG
575 // END_TRY should precede existing LOOP and BLOCK markers.
576 if (MI.getOpcode() == WebAssembly::LOOP ||
577 MI.getOpcode() == WebAssembly::BLOCK)
578 AfterSet.insert(&MI);
580 // All END_TRY markers placed earlier belong to exceptions that contains
581 // this one.
582 if (MI.getOpcode() == WebAssembly::END_TRY)
583 AfterSet.insert(&MI);
584 #endif
586 // If there is a previously placed END_LOOP marker and its header is after
587 // where TRY marker is, this loop is contained within the 'catch' part, so
588 // the END_TRY marker should go after that. Otherwise, the whole try-catch
589 // is contained within this loop, so the END_TRY should go before that.
590 if (MI.getOpcode() == WebAssembly::END_LOOP) {
591 // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they
592 // are in the same BB, LOOP is always before TRY.
593 if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber())
594 BeforeSet.insert(&MI);
595 #ifndef NDEBUG
596 else
597 AfterSet.insert(&MI);
598 #endif
601 // It is not possible for an END_BLOCK to be already in this block.
604 // Mark the end of the TRY.
605 InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet);
606 MachineInstr *End =
607 BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(),
608 TII.get(WebAssembly::END_TRY));
609 registerTryScope(Begin, End, &MBB);
611 // Track the farthest-spanning scope that ends at this point. We create two
612 // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB
613 // with 'try'). We need to create 'catch' -> 'try' mapping here too because
614 // markers should not span across 'catch'. For example, this should not
615 // happen:
617 // try
618 // block --| (X)
619 // catch |
620 // end_block --|
621 // end_try
622 for (int Number : {Cont->getNumber(), MBB.getNumber()}) {
623 if (!ScopeTops[Number] ||
624 ScopeTops[Number]->getNumber() > Header->getNumber())
625 ScopeTops[Number] = Header;
629 void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
630 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
632 // When there is an unconditional branch right before a catch instruction and
633 // it branches to the end of end_try marker, we don't need the branch, because
634 // it there is no exception, the control flow transfers to that point anyway.
635 // bb0:
636 // try
637 // ...
638 // br bb2 <- Not necessary
639 // bb1:
640 // catch
641 // ...
642 // bb2:
643 // end
644 for (auto &MBB : MF) {
645 if (!MBB.isEHPad())
646 continue;
648 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
649 SmallVector<MachineOperand, 4> Cond;
650 MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
651 MachineBasicBlock *Cont = BeginToEnd[EHPadToTry[&MBB]]->getParent();
652 bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
653 if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
654 (!Cond.empty() && FBB && FBB == Cont)))
655 TII.removeBranch(*EHPadLayoutPred);
658 // When there are block / end_block markers that overlap with try / end_try
659 // markers, and the block and try markers' return types are the same, the
660 // block /end_block markers are not necessary, because try / end_try markers
661 // also can serve as boundaries for branches.
662 // block <- Not necessary
663 // try
664 // ...
665 // catch
666 // ...
667 // end
668 // end <- Not necessary
669 SmallVector<MachineInstr *, 32> ToDelete;
670 for (auto &MBB : MF) {
671 for (auto &MI : MBB) {
672 if (MI.getOpcode() != WebAssembly::TRY)
673 continue;
675 MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
676 MachineBasicBlock *TryBB = Try->getParent();
677 MachineBasicBlock *Cont = EndTry->getParent();
678 int64_t RetType = Try->getOperand(0).getImm();
679 for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());
680 B != TryBB->begin() && E != Cont->end() &&
681 std::prev(B)->getOpcode() == WebAssembly::BLOCK &&
682 E->getOpcode() == WebAssembly::END_BLOCK &&
683 std::prev(B)->getOperand(0).getImm() == RetType;
684 --B, ++E) {
685 ToDelete.push_back(&*std::prev(B));
686 ToDelete.push_back(&*E);
690 for (auto *MI : ToDelete) {
691 if (MI->getOpcode() == WebAssembly::BLOCK)
692 unregisterScope(MI);
693 MI->eraseFromParent();
697 bool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) {
698 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
699 MachineRegisterInfo &MRI = MF.getRegInfo();
701 // Linearizing the control flow by placing TRY / END_TRY markers can create
702 // mismatches in unwind destinations. There are two kinds of mismatches we
703 // try to solve here.
705 // 1. When an instruction may throw, but the EH pad it will unwind to can be
706 // different from the original CFG.
708 // Example: we have the following CFG:
709 // bb0:
710 // call @foo (if it throws, unwind to bb2)
711 // bb1:
712 // call @bar (if it throws, unwind to bb3)
713 // bb2 (ehpad):
714 // catch
715 // ...
716 // bb3 (ehpad)
717 // catch
718 // handler body
720 // And the CFG is sorted in this order. Then after placing TRY markers, it
721 // will look like: (BB markers are omitted)
722 // try $label1
723 // try
724 // call @foo
725 // call @bar (if it throws, unwind to bb3)
726 // catch <- ehpad (bb2)
727 // ...
728 // end_try
729 // catch <- ehpad (bb3)
730 // handler body
731 // end_try
733 // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it
734 // is supposed to end up. We solve this problem by
735 // a. Split the target unwind EH pad (here bb3) so that the handler body is
736 // right after 'end_try', which means we extract the handler body out of
737 // the catch block. We do this because this handler body should be
738 // somewhere branch-eable from the inner scope.
739 // b. Wrap the call that has an incorrect unwind destination ('call @bar'
740 // here) with a nested try/catch/end_try scope, and within the new catch
741 // block, branches to the handler body.
742 // c. Place a branch after the newly inserted nested end_try so it can bypass
743 // the handler body, which is now outside of a catch block.
745 // The result will like as follows. (new: a) means this instruction is newly
746 // created in the process of doing 'a' above.
748 // block $label0 (new: placeBlockMarker)
749 // try $label1
750 // try
751 // call @foo
752 // try (new: b)
753 // call @bar
754 // catch (new: b)
755 // local.set n / drop (new: b)
756 // br $label1 (new: b)
757 // end_try (new: b)
758 // catch <- ehpad (bb2)
759 // end_try
760 // br $label0 (new: c)
761 // catch <- ehpad (bb3)
762 // end_try (hoisted: a)
763 // handler body
764 // end_block (new: placeBlockMarker)
766 // Note that the new wrapping block/end_block will be generated later in
767 // placeBlockMarker.
769 // TODO Currently local.set and local.gets are generated to move exnref value
770 // created by catches. That's because we don't support yielding values from a
771 // block in LLVM machine IR yet, even though it is supported by wasm. Delete
772 // unnecessary local.get/local.sets once yielding values from a block is
773 // supported. The full EH spec requires multi-value support to do this, but
774 // for C++ we don't yet need it because we only throw a single i32.
776 // ---
777 // 2. The same as 1, but in this case an instruction unwinds to a caller
778 // function and not another EH pad.
780 // Example: we have the following CFG:
781 // bb0:
782 // call @foo (if it throws, unwind to bb2)
783 // bb1:
784 // call @bar (if it throws, unwind to caller)
785 // bb2 (ehpad):
786 // catch
787 // ...
789 // And the CFG is sorted in this order. Then after placing TRY markers, it
790 // will look like:
791 // try
792 // call @foo
793 // call @bar (if it throws, unwind to caller)
794 // catch <- ehpad (bb2)
795 // ...
796 // end_try
798 // Now if bar() throws, it is going to end up ip in bb2, when it is supposed
799 // throw up to the caller.
800 // We solve this problem by
801 // a. Create a new 'appendix' BB at the end of the function and put a single
802 // 'rethrow' instruction (+ local.get) in there.
803 // b. Wrap the call that has an incorrect unwind destination ('call @bar'
804 // here) with a nested try/catch/end_try scope, and within the new catch
805 // block, branches to the new appendix block.
807 // block $label0 (new: placeBlockMarker)
808 // try
809 // call @foo
810 // try (new: b)
811 // call @bar
812 // catch (new: b)
813 // local.set n (new: b)
814 // br $label0 (new: b)
815 // end_try (new: b)
816 // catch <- ehpad (bb2)
817 // ...
818 // end_try
819 // ...
820 // end_block (new: placeBlockMarker)
821 // local.get n (new: a) <- appendix block
822 // rethrow (new: a)
824 // In case there are multiple calls in a BB that may throw to the caller, they
825 // can be wrapped together in one nested try scope. (In 1, this couldn't
826 // happen, because may-throwing instruction there had an unwind destination,
827 // i.e., it was an invoke before, and there could be only one invoke within a
828 // BB.)
830 SmallVector<const MachineBasicBlock *, 8> EHPadStack;
831 // Range of intructions to be wrapped in a new nested try/catch
832 using TryRange = std::pair<MachineInstr *, MachineInstr *>;
833 // In original CFG, <unwind destionation BB, a vector of try ranges>
834 DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> UnwindDestToTryRanges;
835 // In new CFG, <destination to branch to, a vector of try ranges>
836 DenseMap<MachineBasicBlock *, SmallVector<TryRange, 4>> BrDestToTryRanges;
837 // In new CFG, <destination to branch to, register containing exnref>
838 DenseMap<MachineBasicBlock *, unsigned> BrDestToExnReg;
840 // Gather possibly throwing calls (i.e., previously invokes) whose current
841 // unwind destination is not the same as the original CFG.
842 for (auto &MBB : reverse(MF)) {
843 bool SeenThrowableInstInBB = false;
844 for (auto &MI : reverse(MBB)) {
845 if (MI.getOpcode() == WebAssembly::TRY)
846 EHPadStack.pop_back();
847 else if (MI.getOpcode() == WebAssembly::CATCH)
848 EHPadStack.push_back(MI.getParent());
850 // In this loop we only gather calls that have an EH pad to unwind. So
851 // there will be at most 1 such call (= invoke) in a BB, so after we've
852 // seen one, we can skip the rest of BB. Also if MBB has no EH pad
853 // successor or MI does not throw, this is not an invoke.
854 if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
855 !WebAssembly::mayThrow(MI))
856 continue;
857 SeenThrowableInstInBB = true;
859 // If the EH pad on the stack top is where this instruction should unwind
860 // next, we're good.
861 MachineBasicBlock *UnwindDest = nullptr;
862 for (auto *Succ : MBB.successors()) {
863 if (Succ->isEHPad()) {
864 UnwindDest = Succ;
865 break;
868 if (EHPadStack.back() == UnwindDest)
869 continue;
871 // If not, record the range.
872 UnwindDestToTryRanges[UnwindDest].push_back(TryRange(&MI, &MI));
876 assert(EHPadStack.empty());
878 // Gather possibly throwing calls that are supposed to unwind up to the caller
879 // if they throw, but currently unwind to an incorrect destination. Unlike the
880 // loop above, there can be multiple calls within a BB that unwind to the
881 // caller, which we should group together in a range.
882 bool NeedAppendixBlock = false;
883 for (auto &MBB : reverse(MF)) {
884 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
885 for (auto &MI : reverse(MBB)) {
886 if (MI.getOpcode() == WebAssembly::TRY)
887 EHPadStack.pop_back();
888 else if (MI.getOpcode() == WebAssembly::CATCH)
889 EHPadStack.push_back(MI.getParent());
891 // If MBB has an EH pad successor, this inst does not unwind to caller.
892 if (MBB.hasEHPadSuccessor())
893 continue;
895 // We wrap up the current range when we see a marker even if we haven't
896 // finished a BB.
897 if (RangeEnd && WebAssembly::isMarker(MI.getOpcode())) {
898 NeedAppendixBlock = true;
899 // Record the range. nullptr here means the unwind destination is the
900 // caller.
901 UnwindDestToTryRanges[nullptr].push_back(
902 TryRange(RangeBegin, RangeEnd));
903 RangeBegin = RangeEnd = nullptr; // Reset range pointers
906 // If EHPadStack is empty, that means it is correctly unwind to caller if
907 // it throws, so we're good. If MI does not throw, we're good too.
908 if (EHPadStack.empty() || !WebAssembly::mayThrow(MI))
909 continue;
911 // We found an instruction that unwinds to the caller but currently has an
912 // incorrect unwind destination. Create a new range or increment the
913 // currently existing range.
914 if (!RangeEnd)
915 RangeBegin = RangeEnd = &MI;
916 else
917 RangeBegin = &MI;
920 if (RangeEnd) {
921 NeedAppendixBlock = true;
922 // Record the range. nullptr here means the unwind destination is the
923 // caller.
924 UnwindDestToTryRanges[nullptr].push_back(TryRange(RangeBegin, RangeEnd));
925 RangeBegin = RangeEnd = nullptr; // Reset range pointers
929 assert(EHPadStack.empty());
930 // We don't have any unwind destination mismatches to resolve.
931 if (UnwindDestToTryRanges.empty())
932 return false;
934 // If we found instructions that should unwind to the caller but currently
935 // have incorrect unwind destination, we create an appendix block at the end
936 // of the function with a local.get and a rethrow instruction.
937 if (NeedAppendixBlock) {
938 auto *AppendixBB = getAppendixBlock(MF);
939 Register ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);
940 BuildMI(AppendixBB, DebugLoc(), TII.get(WebAssembly::RETHROW))
941 .addReg(ExnReg);
942 // These instruction ranges should branch to this appendix BB.
943 for (auto Range : UnwindDestToTryRanges[nullptr])
944 BrDestToTryRanges[AppendixBB].push_back(Range);
945 BrDestToExnReg[AppendixBB] = ExnReg;
948 // We loop through unwind destination EH pads that are targeted from some
949 // inner scopes. Because these EH pads are destination of more than one scope
950 // now, we split them so that the handler body is after 'end_try'.
951 // - Before
952 // ehpad:
953 // catch
954 // local.set n / drop
955 // handler body
956 // ...
957 // cont:
958 // end_try
960 // - After
961 // ehpad:
962 // catch
963 // local.set n / drop
964 // brdest: (new)
965 // end_try (hoisted from 'cont' BB)
966 // handler body (taken from 'ehpad')
967 // ...
968 // cont:
969 for (auto &P : UnwindDestToTryRanges) {
970 NumUnwindMismatches++;
972 // This means the destination is the appendix BB, which was separately
973 // handled above.
974 if (!P.first)
975 continue;
977 MachineBasicBlock *EHPad = P.first;
979 // Find 'catch' and 'local.set' or 'drop' instruction that follows the
980 // 'catch'. If -wasm-disable-explicit-locals is not set, 'catch' should be
981 // always followed by either 'local.set' or a 'drop', because 'br_on_exn' is
982 // generated after 'catch' in LateEHPrepare and we don't support blocks
983 // taking values yet.
984 MachineInstr *Catch = nullptr;
985 unsigned ExnReg = 0;
986 for (auto &MI : *EHPad) {
987 switch (MI.getOpcode()) {
988 case WebAssembly::CATCH:
989 Catch = &MI;
990 ExnReg = Catch->getOperand(0).getReg();
991 break;
994 assert(Catch && "EH pad does not have a catch");
995 assert(ExnReg != 0 && "Invalid register");
997 auto SplitPos = std::next(Catch->getIterator());
999 // Create a new BB that's gonna be the destination for branches from the
1000 // inner mismatched scope.
1001 MachineInstr *BeginTry = EHPadToTry[EHPad];
1002 MachineInstr *EndTry = BeginToEnd[BeginTry];
1003 MachineBasicBlock *Cont = EndTry->getParent();
1004 auto *BrDest = MF.CreateMachineBasicBlock();
1005 MF.insert(std::next(EHPad->getIterator()), BrDest);
1006 // Hoist up the existing 'end_try'.
1007 BrDest->insert(BrDest->end(), EndTry->removeFromParent());
1008 // Take out the handler body from EH pad to the new branch destination BB.
1009 BrDest->splice(BrDest->end(), EHPad, SplitPos, EHPad->end());
1010 // Fix predecessor-successor relationship.
1011 BrDest->transferSuccessors(EHPad);
1012 EHPad->addSuccessor(BrDest);
1014 // All try ranges that were supposed to unwind to this EH pad now have to
1015 // branch to this new branch dest BB.
1016 for (auto Range : UnwindDestToTryRanges[EHPad])
1017 BrDestToTryRanges[BrDest].push_back(Range);
1018 BrDestToExnReg[BrDest] = ExnReg;
1020 // In case we fall through to the continuation BB after the catch block, we
1021 // now have to add a branch to it.
1022 // - Before
1023 // try
1024 // ...
1025 // (falls through to 'cont')
1026 // catch
1027 // handler body
1028 // end
1029 // <-- cont
1031 // - After
1032 // try
1033 // ...
1034 // br %cont (new)
1035 // catch
1036 // end
1037 // handler body
1038 // <-- cont
1039 MachineBasicBlock *EHPadLayoutPred = &*std::prev(EHPad->getIterator());
1040 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1041 SmallVector<MachineOperand, 4> Cond;
1042 bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
1043 if (Analyzable && !TBB && !FBB) {
1044 DebugLoc DL = EHPadLayoutPred->empty()
1045 ? DebugLoc()
1046 : EHPadLayoutPred->rbegin()->getDebugLoc();
1047 BuildMI(EHPadLayoutPred, DL, TII.get(WebAssembly::BR)).addMBB(Cont);
1051 // For possibly throwing calls whose unwind destinations are currently
1052 // incorrect because of CFG linearization, we wrap them with a nested
1053 // try/catch/end_try, and within the new catch block, we branch to the correct
1054 // handler.
1055 // - Before
1056 // mbb:
1057 // call @foo <- Unwind destination mismatch!
1058 // ehpad:
1059 // ...
1061 // - After
1062 // mbb:
1063 // try (new)
1064 // call @foo
1065 // nested-ehpad: (new)
1066 // catch (new)
1067 // local.set n / drop (new)
1068 // br %brdest (new)
1069 // nested-end: (new)
1070 // end_try (new)
1071 // ehpad:
1072 // ...
1073 for (auto &P : BrDestToTryRanges) {
1074 MachineBasicBlock *BrDest = P.first;
1075 auto &TryRanges = P.second;
1076 unsigned ExnReg = BrDestToExnReg[BrDest];
1078 for (auto Range : TryRanges) {
1079 MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1080 std::tie(RangeBegin, RangeEnd) = Range;
1081 auto *MBB = RangeBegin->getParent();
1083 // Include possible EH_LABELs in the range
1084 if (RangeBegin->getIterator() != MBB->begin() &&
1085 std::prev(RangeBegin->getIterator())->isEHLabel())
1086 RangeBegin = &*std::prev(RangeBegin->getIterator());
1087 if (std::next(RangeEnd->getIterator()) != MBB->end() &&
1088 std::next(RangeEnd->getIterator())->isEHLabel())
1089 RangeEnd = &*std::next(RangeEnd->getIterator());
1091 MachineBasicBlock *EHPad = nullptr;
1092 for (auto *Succ : MBB->successors()) {
1093 if (Succ->isEHPad()) {
1094 EHPad = Succ;
1095 break;
1099 // Create the nested try instruction.
1100 MachineInstr *NestedTry =
1101 BuildMI(*MBB, *RangeBegin, RangeBegin->getDebugLoc(),
1102 TII.get(WebAssembly::TRY))
1103 .addImm(int64_t(WebAssembly::ExprType::Void));
1105 // Create the nested EH pad and fill instructions in.
1106 MachineBasicBlock *NestedEHPad = MF.CreateMachineBasicBlock();
1107 MF.insert(std::next(MBB->getIterator()), NestedEHPad);
1108 NestedEHPad->setIsEHPad();
1109 NestedEHPad->setIsEHScopeEntry();
1110 BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::CATCH),
1111 ExnReg);
1112 BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::BR))
1113 .addMBB(BrDest);
1115 // Create the nested continuation BB and end_try instruction.
1116 MachineBasicBlock *NestedCont = MF.CreateMachineBasicBlock();
1117 MF.insert(std::next(NestedEHPad->getIterator()), NestedCont);
1118 MachineInstr *NestedEndTry =
1119 BuildMI(*NestedCont, NestedCont->begin(), RangeEnd->getDebugLoc(),
1120 TII.get(WebAssembly::END_TRY));
1121 // In case MBB has more instructions after the try range, move them to the
1122 // new nested continuation BB.
1123 NestedCont->splice(NestedCont->end(), MBB,
1124 std::next(RangeEnd->getIterator()), MBB->end());
1125 registerTryScope(NestedTry, NestedEndTry, NestedEHPad);
1127 // Fix predecessor-successor relationship.
1128 NestedCont->transferSuccessors(MBB);
1129 if (EHPad)
1130 NestedCont->removeSuccessor(EHPad);
1131 MBB->addSuccessor(NestedEHPad);
1132 MBB->addSuccessor(NestedCont);
1133 NestedEHPad->addSuccessor(BrDest);
1137 // Renumber BBs and recalculate ScopeTop info because new BBs might have been
1138 // created and inserted above.
1139 MF.RenumberBlocks();
1140 ScopeTops.clear();
1141 ScopeTops.resize(MF.getNumBlockIDs());
1142 for (auto &MBB : reverse(MF)) {
1143 for (auto &MI : reverse(MBB)) {
1144 if (ScopeTops[MBB.getNumber()])
1145 break;
1146 switch (MI.getOpcode()) {
1147 case WebAssembly::END_BLOCK:
1148 case WebAssembly::END_LOOP:
1149 case WebAssembly::END_TRY:
1150 ScopeTops[MBB.getNumber()] = EndToBegin[&MI]->getParent();
1151 break;
1152 case WebAssembly::CATCH:
1153 ScopeTops[MBB.getNumber()] = EHPadToTry[&MBB]->getParent();
1154 break;
1159 // Recompute the dominator tree.
1160 getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF);
1162 // Place block markers for newly added branches.
1163 SmallVector <MachineBasicBlock *, 8> BrDests;
1164 for (auto &P : BrDestToTryRanges)
1165 BrDests.push_back(P.first);
1166 llvm::sort(BrDests,
1167 [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
1168 auto ANum = A->getNumber();
1169 auto BNum = B->getNumber();
1170 return ANum < BNum;
1172 for (auto *Dest : BrDests)
1173 placeBlockMarker(*Dest);
1175 return true;
1178 static unsigned
1179 getDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack,
1180 const MachineBasicBlock *MBB) {
1181 unsigned Depth = 0;
1182 for (auto X : reverse(Stack)) {
1183 if (X == MBB)
1184 break;
1185 ++Depth;
1187 assert(Depth < Stack.size() && "Branch destination should be in scope");
1188 return Depth;
1191 /// In normal assembly languages, when the end of a function is unreachable,
1192 /// because the function ends in an infinite loop or a noreturn call or similar,
1193 /// it isn't necessary to worry about the function return type at the end of
1194 /// the function, because it's never reached. However, in WebAssembly, blocks
1195 /// that end at the function end need to have a return type signature that
1196 /// matches the function signature, even though it's unreachable. This function
1197 /// checks for such cases and fixes up the signatures.
1198 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
1199 const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1200 assert(MFI.getResults().size() <= 1);
1202 if (MFI.getResults().empty())
1203 return;
1205 WebAssembly::ExprType RetType;
1206 switch (MFI.getResults().front().SimpleTy) {
1207 case MVT::i32:
1208 RetType = WebAssembly::ExprType::I32;
1209 break;
1210 case MVT::i64:
1211 RetType = WebAssembly::ExprType::I64;
1212 break;
1213 case MVT::f32:
1214 RetType = WebAssembly::ExprType::F32;
1215 break;
1216 case MVT::f64:
1217 RetType = WebAssembly::ExprType::F64;
1218 break;
1219 case MVT::v16i8:
1220 case MVT::v8i16:
1221 case MVT::v4i32:
1222 case MVT::v2i64:
1223 case MVT::v4f32:
1224 case MVT::v2f64:
1225 RetType = WebAssembly::ExprType::V128;
1226 break;
1227 case MVT::exnref:
1228 RetType = WebAssembly::ExprType::Exnref;
1229 break;
1230 default:
1231 llvm_unreachable("unexpected return type");
1234 for (MachineBasicBlock &MBB : reverse(MF)) {
1235 for (MachineInstr &MI : reverse(MBB)) {
1236 if (MI.isPosition() || MI.isDebugInstr())
1237 continue;
1238 if (MI.getOpcode() == WebAssembly::END_BLOCK) {
1239 EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1240 continue;
1242 if (MI.getOpcode() == WebAssembly::END_LOOP) {
1243 EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1244 continue;
1246 // Something other than an `end`. We're done.
1247 return;
1252 // WebAssembly functions end with an end instruction, as if the function body
1253 // were a block.
1254 static void appendEndToFunction(MachineFunction &MF,
1255 const WebAssemblyInstrInfo &TII) {
1256 BuildMI(MF.back(), MF.back().end(),
1257 MF.back().findPrevDebugLoc(MF.back().end()),
1258 TII.get(WebAssembly::END_FUNCTION));
1261 /// Insert LOOP/TRY/BLOCK markers at appropriate places.
1262 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
1263 // We allocate one more than the number of blocks in the function to
1264 // accommodate for the possible fake block we may insert at the end.
1265 ScopeTops.resize(MF.getNumBlockIDs() + 1);
1266 // Place the LOOP for MBB if MBB is the header of a loop.
1267 for (auto &MBB : MF)
1268 placeLoopMarker(MBB);
1270 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1271 for (auto &MBB : MF) {
1272 if (MBB.isEHPad()) {
1273 // Place the TRY for MBB if MBB is the EH pad of an exception.
1274 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
1275 MF.getFunction().hasPersonalityFn())
1276 placeTryMarker(MBB);
1277 } else {
1278 // Place the BLOCK for MBB if MBB is branched to from above.
1279 placeBlockMarker(MBB);
1282 // Fix mismatches in unwind destinations induced by linearizing the code.
1283 fixUnwindMismatches(MF);
1286 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
1287 // Now rewrite references to basic blocks to be depth immediates.
1288 SmallVector<const MachineBasicBlock *, 8> Stack;
1289 for (auto &MBB : reverse(MF)) {
1290 for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) {
1291 MachineInstr &MI = *I;
1292 switch (MI.getOpcode()) {
1293 case WebAssembly::BLOCK:
1294 case WebAssembly::TRY:
1295 assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
1296 MBB.getNumber() &&
1297 "Block/try marker should be balanced");
1298 Stack.pop_back();
1299 break;
1301 case WebAssembly::LOOP:
1302 assert(Stack.back() == &MBB && "Loop top should be balanced");
1303 Stack.pop_back();
1304 break;
1306 case WebAssembly::END_BLOCK:
1307 case WebAssembly::END_TRY:
1308 Stack.push_back(&MBB);
1309 break;
1311 case WebAssembly::END_LOOP:
1312 Stack.push_back(EndToBegin[&MI]->getParent());
1313 break;
1315 default:
1316 if (MI.isTerminator()) {
1317 // Rewrite MBB operands to be depth immediates.
1318 SmallVector<MachineOperand, 4> Ops(MI.operands());
1319 while (MI.getNumOperands() > 0)
1320 MI.RemoveOperand(MI.getNumOperands() - 1);
1321 for (auto MO : Ops) {
1322 if (MO.isMBB())
1323 MO = MachineOperand::CreateImm(getDepth(Stack, MO.getMBB()));
1324 MI.addOperand(MF, MO);
1327 break;
1331 assert(Stack.empty() && "Control flow should be balanced");
1334 void WebAssemblyCFGStackify::releaseMemory() {
1335 ScopeTops.clear();
1336 BeginToEnd.clear();
1337 EndToBegin.clear();
1338 TryToEHPad.clear();
1339 EHPadToTry.clear();
1340 AppendixBB = nullptr;
1343 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
1344 LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
1345 "********** Function: "
1346 << MF.getName() << '\n');
1347 const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1349 releaseMemory();
1351 // Liveness is not tracked for VALUE_STACK physreg.
1352 MF.getRegInfo().invalidateLiveness();
1354 // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
1355 placeMarkers(MF);
1357 // Remove unnecessary instructions possibly introduced by try/end_trys.
1358 if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
1359 MF.getFunction().hasPersonalityFn())
1360 removeUnnecessaryInstrs(MF);
1362 // Convert MBB operands in terminators to relative depth immediates.
1363 rewriteDepthImmediates(MF);
1365 // Fix up block/loop/try signatures at the end of the function to conform to
1366 // WebAssembly's rules.
1367 fixEndsAtEndOfFunction(MF);
1369 // Add an end instruction at the end of the function body.
1370 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1371 if (!MF.getSubtarget<WebAssemblySubtarget>()
1372 .getTargetTriple()
1373 .isOSBinFormatELF())
1374 appendEndToFunction(MF, TII);
1376 MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
1377 return true;