LLVM  13.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, 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 //===----------------------------------------------------------------------===//
23 
24 #include "WebAssembly.h"
27 #include "WebAssemblySortRegion.h"
28 #include "WebAssemblySubtarget.h"
29 #include "WebAssemblyUtilities.h"
30 #include "llvm/ADT/Statistic.h"
35 #include "llvm/MC/MCAsmInfo.h"
37 using namespace llvm;
39 
40 #define DEBUG_TYPE "wasm-cfg-stackify"
41 
42 STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found");
43 STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found");
44 
45 namespace {
46 class WebAssemblyCFGStackify final : public MachineFunctionPass {
47  StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
48 
49  void getAnalysisUsage(AnalysisUsage &AU) const override {
54  }
55 
56  bool runOnMachineFunction(MachineFunction &MF) override;
57 
58  // For each block whose label represents the end of a scope, record the block
59  // which holds the beginning of the scope. This will allow us to quickly skip
60  // over scoped regions when walking blocks.
62  void updateScopeTops(MachineBasicBlock *Begin, MachineBasicBlock *End) {
63  int EndNo = End->getNumber();
64  if (!ScopeTops[EndNo] || ScopeTops[EndNo]->getNumber() > Begin->getNumber())
65  ScopeTops[EndNo] = Begin;
66  }
67 
68  // Placing markers.
69  void placeMarkers(MachineFunction &MF);
70  void placeBlockMarker(MachineBasicBlock &MBB);
71  void placeLoopMarker(MachineBasicBlock &MBB);
72  void placeTryMarker(MachineBasicBlock &MBB);
73 
74  // Exception handling related functions
75  bool fixCallUnwindMismatches(MachineFunction &MF);
76  bool fixCatchUnwindMismatches(MachineFunction &MF);
77  void addTryDelegate(MachineInstr *RangeBegin, MachineInstr *RangeEnd,
78  MachineBasicBlock *DelegateDest);
79  void recalculateScopeTops(MachineFunction &MF);
80  void removeUnnecessaryInstrs(MachineFunction &MF);
81 
82  // Wrap-up
83  using EndMarkerInfo =
84  std::pair<const MachineBasicBlock *, const MachineInstr *>;
85  unsigned getBranchDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,
86  const MachineBasicBlock *MBB);
87  unsigned getDelegateDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,
88  const MachineBasicBlock *MBB);
89  unsigned
90  getRethrowDepth(const SmallVectorImpl<EndMarkerInfo> &Stack,
92  void rewriteDepthImmediates(MachineFunction &MF);
93  void fixEndsAtEndOfFunction(MachineFunction &MF);
94  void cleanupFunctionData(MachineFunction &MF);
95 
96  // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY) or DELEGATE
97  // (in case of TRY).
99  // For each END_(BLOCK|LOOP|TRY) or DELEGATE, the corresponding
100  // BLOCK|LOOP|TRY.
102  // <TRY marker, EH pad> map
104  // <EH pad, TRY marker> map
106 
107  // We need an appendix block to place 'end_loop' or 'end_try' marker when the
108  // loop / exception bottom block is the last block in a function
109  MachineBasicBlock *AppendixBB = nullptr;
110  MachineBasicBlock *getAppendixBlock(MachineFunction &MF) {
111  if (!AppendixBB) {
112  AppendixBB = MF.CreateMachineBasicBlock();
113  // Give it a fake predecessor so that AsmPrinter prints its label.
114  AppendixBB->addSuccessor(AppendixBB);
115  MF.push_back(AppendixBB);
116  }
117  return AppendixBB;
118  }
119 
120  // Before running rewriteDepthImmediates function, 'delegate' has a BB as its
121  // destination operand. getFakeCallerBlock() returns a fake BB that will be
122  // used for the operand when 'delegate' needs to rethrow to the caller. This
123  // will be rewritten as an immediate value that is the number of block depths
124  // + 1 in rewriteDepthImmediates, and this fake BB will be removed at the end
125  // of the pass.
126  MachineBasicBlock *FakeCallerBB = nullptr;
127  MachineBasicBlock *getFakeCallerBlock(MachineFunction &MF) {
128  if (!FakeCallerBB)
129  FakeCallerBB = MF.CreateMachineBasicBlock();
130  return FakeCallerBB;
131  }
132 
133  // Helper functions to register / unregister scope information created by
134  // marker instructions.
135  void registerScope(MachineInstr *Begin, MachineInstr *End);
136  void registerTryScope(MachineInstr *Begin, MachineInstr *End,
137  MachineBasicBlock *EHPad);
138  void unregisterScope(MachineInstr *Begin);
139 
140 public:
141  static char ID; // Pass identification, replacement for typeid
142  WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
143  ~WebAssemblyCFGStackify() override { releaseMemory(); }
144  void releaseMemory() override;
145 };
146 } // end anonymous namespace
147 
149 INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,
150  "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false,
151  false)
152 
154  return new WebAssemblyCFGStackify();
155 }
156 
157 /// Test whether Pred has any terminators explicitly branching to MBB, as
158 /// opposed to falling through. Note that it's possible (eg. in unoptimized
159 /// code) for a branch instruction to both branch to a block and fallthrough
160 /// to it, so we check the actual branch operands to see if there are any
161 /// explicit mentions.
164  for (MachineInstr &MI : Pred->terminators())
165  for (MachineOperand &MO : MI.explicit_operands())
166  if (MO.isMBB() && MO.getMBB() == MBB)
167  return true;
168  return false;
169 }
170 
171 // Returns an iterator to the earliest position possible within the MBB,
172 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
173 // contains instructions that should go before the marker, and AfterSet contains
174 // ones that should go after the marker. In this function, AfterSet is only
175 // used for sanity checking.
176 template <typename Container>
178 getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet,
179  const Container &AfterSet) {
180  auto InsertPos = MBB->end();
181  while (InsertPos != MBB->begin()) {
182  if (BeforeSet.count(&*std::prev(InsertPos))) {
183 #ifndef NDEBUG
184  // Sanity check
185  for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
186  assert(!AfterSet.count(&*std::prev(Pos)));
187 #endif
188  break;
189  }
190  --InsertPos;
191  }
192  return InsertPos;
193 }
194 
195 // Returns an iterator to the latest position possible within the MBB,
196 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
197 // contains instructions that should go before the marker, and AfterSet contains
198 // ones that should go after the marker. In this function, BeforeSet is only
199 // used for sanity checking.
200 template <typename Container>
202 getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet,
203  const Container &AfterSet) {
204  auto InsertPos = MBB->begin();
205  while (InsertPos != MBB->end()) {
206  if (AfterSet.count(&*InsertPos)) {
207 #ifndef NDEBUG
208  // Sanity check
209  for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
210  assert(!BeforeSet.count(&*Pos));
211 #endif
212  break;
213  }
214  ++InsertPos;
215  }
216  return InsertPos;
217 }
218 
219 void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
220  MachineInstr *End) {
221  BeginToEnd[Begin] = End;
222  EndToBegin[End] = Begin;
223 }
224 
225 // When 'End' is not an 'end_try' but 'delegate, EHPad is nullptr.
226 void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
227  MachineInstr *End,
228  MachineBasicBlock *EHPad) {
229  registerScope(Begin, End);
230  TryToEHPad[Begin] = EHPad;
231  EHPadToTry[EHPad] = Begin;
232 }
233 
234 void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
235  assert(BeginToEnd.count(Begin));
236  MachineInstr *End = BeginToEnd[Begin];
237  assert(EndToBegin.count(End));
238  BeginToEnd.erase(Begin);
239  EndToBegin.erase(End);
240  MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
241  if (EHPad) {
242  assert(EHPadToTry.count(EHPad));
243  TryToEHPad.erase(Begin);
244  EHPadToTry.erase(EHPad);
245  }
246 }
247 
248 /// Insert a BLOCK marker for branches to MBB (if needed).
249 // TODO Consider a more generalized way of handling block (and also loop and
250 // try) signatures when we implement the multi-value proposal later.
251 void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
252  assert(!MBB.isEHPad());
253  MachineFunction &MF = *MBB.getParent();
254  auto &MDT = getAnalysis<MachineDominatorTree>();
255  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
256  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
257 
258  // First compute the nearest common dominator of all forward non-fallthrough
259  // predecessors so that we minimize the time that the BLOCK is on the stack,
260  // which reduces overall stack height.
261  MachineBasicBlock *Header = nullptr;
262  bool IsBranchedTo = false;
263  int MBBNumber = MBB.getNumber();
264  for (MachineBasicBlock *Pred : MBB.predecessors()) {
265  if (Pred->getNumber() < MBBNumber) {
266  Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
267  if (explicitlyBranchesTo(Pred, &MBB))
268  IsBranchedTo = true;
269  }
270  }
271  if (!Header)
272  return;
273  if (!IsBranchedTo)
274  return;
275 
276  assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
277  MachineBasicBlock *LayoutPred = MBB.getPrevNode();
278 
279  // If the nearest common dominator is inside a more deeply nested context,
280  // walk out to the nearest scope which isn't more deeply nested.
281  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
282  if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
283  if (ScopeTop->getNumber() > Header->getNumber()) {
284  // Skip over an intervening scope.
285  I = std::next(ScopeTop->getIterator());
286  } else {
287  // We found a scope level at an appropriate depth.
288  Header = ScopeTop;
289  break;
290  }
291  }
292  }
293 
294  // Decide where in Header to put the BLOCK.
295 
296  // Instructions that should go before the BLOCK.
298  // Instructions that should go after the BLOCK.
300  for (const auto &MI : *Header) {
301  // If there is a previously placed LOOP marker and the bottom block of the
302  // loop is above MBB, it should be after the BLOCK, because the loop is
303  // nested in this BLOCK. Otherwise it should be before the BLOCK.
304  if (MI.getOpcode() == WebAssembly::LOOP) {
305  auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
306  if (MBB.getNumber() > LoopBottom->getNumber())
307  AfterSet.insert(&MI);
308 #ifndef NDEBUG
309  else
310  BeforeSet.insert(&MI);
311 #endif
312  }
313 
314  // If there is a previously placed BLOCK/TRY marker and its corresponding
315  // END marker is before the current BLOCK's END marker, that should be
316  // placed after this BLOCK. Otherwise it should be placed before this BLOCK
317  // marker.
318  if (MI.getOpcode() == WebAssembly::BLOCK ||
319  MI.getOpcode() == WebAssembly::TRY) {
320  if (BeginToEnd[&MI]->getParent()->getNumber() <= MBB.getNumber())
321  AfterSet.insert(&MI);
322 #ifndef NDEBUG
323  else
324  BeforeSet.insert(&MI);
325 #endif
326  }
327 
328 #ifndef NDEBUG
329  // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK.
330  if (MI.getOpcode() == WebAssembly::END_BLOCK ||
331  MI.getOpcode() == WebAssembly::END_LOOP ||
332  MI.getOpcode() == WebAssembly::END_TRY)
333  BeforeSet.insert(&MI);
334 #endif
335 
336  // Terminators should go after the BLOCK.
337  if (MI.isTerminator())
338  AfterSet.insert(&MI);
339  }
340 
341  // Local expression tree should go after the BLOCK.
342  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
343  --I) {
344  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
345  continue;
346  if (WebAssembly::isChild(*std::prev(I), MFI))
347  AfterSet.insert(&*std::prev(I));
348  else
349  break;
350  }
351 
352  // Add the BLOCK.
354  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
355  MachineInstr *Begin =
356  BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
357  TII.get(WebAssembly::BLOCK))
358  .addImm(int64_t(ReturnType));
359 
360  // Decide where in Header to put the END_BLOCK.
361  BeforeSet.clear();
362  AfterSet.clear();
363  for (auto &MI : MBB) {
364 #ifndef NDEBUG
365  // END_BLOCK should precede existing LOOP and TRY markers.
366  if (MI.getOpcode() == WebAssembly::LOOP ||
367  MI.getOpcode() == WebAssembly::TRY)
368  AfterSet.insert(&MI);
369 #endif
370 
371  // If there is a previously placed END_LOOP marker and the header of the
372  // loop is above this block's header, the END_LOOP should be placed after
373  // the BLOCK, because the loop contains this block. Otherwise the END_LOOP
374  // should be placed before the BLOCK. The same for END_TRY.
375  if (MI.getOpcode() == WebAssembly::END_LOOP ||
376  MI.getOpcode() == WebAssembly::END_TRY) {
377  if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
378  BeforeSet.insert(&MI);
379 #ifndef NDEBUG
380  else
381  AfterSet.insert(&MI);
382 #endif
383  }
384  }
385 
386  // Mark the end of the block.
387  InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
388  MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
390  registerScope(Begin, End);
391 
392  // Track the farthest-spanning scope that ends at this point.
393  updateScopeTops(Header, &MBB);
394 }
395 
396 /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
397 void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
398  MachineFunction &MF = *MBB.getParent();
399  const auto &MLI = getAnalysis<MachineLoopInfo>();
400  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
401  SortRegionInfo SRI(MLI, WEI);
402  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
403 
404  MachineLoop *Loop = MLI.getLoopFor(&MBB);
405  if (!Loop || Loop->getHeader() != &MBB)
406  return;
407 
408  // The operand of a LOOP is the first block after the loop. If the loop is the
409  // bottom of the function, insert a dummy block at the end.
410  MachineBasicBlock *Bottom = SRI.getBottom(Loop);
411  auto Iter = std::next(Bottom->getIterator());
412  if (Iter == MF.end()) {
413  getAppendixBlock(MF);
414  Iter = std::next(Bottom->getIterator());
415  }
416  MachineBasicBlock *AfterLoop = &*Iter;
417 
418  // Decide where in Header to put the LOOP.
421  for (const auto &MI : MBB) {
422  // LOOP marker should be after any existing loop that ends here. Otherwise
423  // we assume the instruction belongs to the loop.
424  if (MI.getOpcode() == WebAssembly::END_LOOP)
425  BeforeSet.insert(&MI);
426 #ifndef NDEBUG
427  else
428  AfterSet.insert(&MI);
429 #endif
430  }
431 
432  // Mark the beginning of the loop.
433  auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
434  MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),
435  TII.get(WebAssembly::LOOP))
437 
438  // Decide where in Header to put the END_LOOP.
439  BeforeSet.clear();
440  AfterSet.clear();
441 #ifndef NDEBUG
442  for (const auto &MI : MBB)
443  // Existing END_LOOP markers belong to parent loops of this loop
444  if (MI.getOpcode() == WebAssembly::END_LOOP)
445  AfterSet.insert(&MI);
446 #endif
447 
448  // Mark the end of the loop (using arbitrary debug location that branched to
449  // the loop end as its location).
450  InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet);
451  DebugLoc EndDL = AfterLoop->pred_empty()
452  ? DebugLoc()
453  : (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
454  MachineInstr *End =
455  BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP));
456  registerScope(Begin, End);
457 
458  assert((!ScopeTops[AfterLoop->getNumber()] ||
459  ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
460  "With block sorting the outermost loop for a block should be first.");
461  updateScopeTops(&MBB, AfterLoop);
462 }
463 
464 void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
465  assert(MBB.isEHPad());
466  MachineFunction &MF = *MBB.getParent();
467  auto &MDT = getAnalysis<MachineDominatorTree>();
468  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
469  const auto &MLI = getAnalysis<MachineLoopInfo>();
470  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
471  SortRegionInfo SRI(MLI, WEI);
472  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
473 
474  // Compute the nearest common dominator of all unwind predecessors
475  MachineBasicBlock *Header = nullptr;
476  int MBBNumber = MBB.getNumber();
477  for (auto *Pred : MBB.predecessors()) {
478  if (Pred->getNumber() < MBBNumber) {
479  Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
480  assert(!explicitlyBranchesTo(Pred, &MBB) &&
481  "Explicit branch to an EH pad!");
482  }
483  }
484  if (!Header)
485  return;
486 
487  // If this try is at the bottom of the function, insert a dummy block at the
488  // end.
489  WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
490  assert(WE);
491  MachineBasicBlock *Bottom = SRI.getBottom(WE);
492 
493  auto Iter = std::next(Bottom->getIterator());
494  if (Iter == MF.end()) {
495  getAppendixBlock(MF);
496  Iter = std::next(Bottom->getIterator());
497  }
498  MachineBasicBlock *Cont = &*Iter;
499 
500  assert(Cont != &MF.front());
501  MachineBasicBlock *LayoutPred = Cont->getPrevNode();
502 
503  // If the nearest common dominator is inside a more deeply nested context,
504  // walk out to the nearest scope which isn't more deeply nested.
505  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
506  if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
507  if (ScopeTop->getNumber() > Header->getNumber()) {
508  // Skip over an intervening scope.
509  I = std::next(ScopeTop->getIterator());
510  } else {
511  // We found a scope level at an appropriate depth.
512  Header = ScopeTop;
513  break;
514  }
515  }
516  }
517 
518  // Decide where in Header to put the TRY.
519 
520  // Instructions that should go before the TRY.
522  // Instructions that should go after the TRY.
524  for (const auto &MI : *Header) {
525  // If there is a previously placed LOOP marker and the bottom block of the
526  // loop is above MBB, it should be after the TRY, because the loop is nested
527  // in this TRY. Otherwise it should be before the TRY.
528  if (MI.getOpcode() == WebAssembly::LOOP) {
529  auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
530  if (MBB.getNumber() > LoopBottom->getNumber())
531  AfterSet.insert(&MI);
532 #ifndef NDEBUG
533  else
534  BeforeSet.insert(&MI);
535 #endif
536  }
537 
538  // All previously inserted BLOCK/TRY markers should be after the TRY because
539  // they are all nested trys.
540  if (MI.getOpcode() == WebAssembly::BLOCK ||
541  MI.getOpcode() == WebAssembly::TRY)
542  AfterSet.insert(&MI);
543 
544 #ifndef NDEBUG
545  // All END_(BLOCK/LOOP/TRY) markers should be before the TRY.
546  if (MI.getOpcode() == WebAssembly::END_BLOCK ||
547  MI.getOpcode() == WebAssembly::END_LOOP ||
548  MI.getOpcode() == WebAssembly::END_TRY)
549  BeforeSet.insert(&MI);
550 #endif
551 
552  // Terminators should go after the TRY.
553  if (MI.isTerminator())
554  AfterSet.insert(&MI);
555  }
556 
557  // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
558  // contain the call within it. So the call should go after the TRY. The
559  // exception is when the header's terminator is a rethrow instruction, in
560  // which case that instruction, not a call instruction before it, is gonna
561  // throw.
562  MachineInstr *ThrowingCall = nullptr;
563  if (MBB.isPredecessor(Header)) {
564  auto TermPos = Header->getFirstTerminator();
565  if (TermPos == Header->end() ||
566  TermPos->getOpcode() != WebAssembly::RETHROW) {
567  for (auto &MI : reverse(*Header)) {
568  if (MI.isCall()) {
569  AfterSet.insert(&MI);
570  ThrowingCall = &MI;
571  // Possibly throwing calls are usually wrapped by EH_LABEL
572  // instructions. We don't want to split them and the call.
573  if (MI.getIterator() != Header->begin() &&
574  std::prev(MI.getIterator())->isEHLabel()) {
575  AfterSet.insert(&*std::prev(MI.getIterator()));
576  ThrowingCall = &*std::prev(MI.getIterator());
577  }
578  break;
579  }
580  }
581  }
582  }
583 
584  // Local expression tree should go after the TRY.
585  // For BLOCK placement, we start the search from the previous instruction of a
586  // BB's terminator, but in TRY's case, we should start from the previous
587  // instruction of a call that can throw, or a EH_LABEL that precedes the call,
588  // because the return values of the call's previous instructions can be
589  // stackified and consumed by the throwing call.
590  auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall)
591  : Header->getFirstTerminator();
592  for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) {
593  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
594  continue;
595  if (WebAssembly::isChild(*std::prev(I), MFI))
596  AfterSet.insert(&*std::prev(I));
597  else
598  break;
599  }
600 
601  // Add the TRY.
602  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
603  MachineInstr *Begin =
604  BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
605  TII.get(WebAssembly::TRY))
607 
608  // Decide where in Header to put the END_TRY.
609  BeforeSet.clear();
610  AfterSet.clear();
611  for (const auto &MI : *Cont) {
612 #ifndef NDEBUG
613  // END_TRY should precede existing LOOP and BLOCK markers.
614  if (MI.getOpcode() == WebAssembly::LOOP ||
615  MI.getOpcode() == WebAssembly::BLOCK)
616  AfterSet.insert(&MI);
617 
618  // All END_TRY markers placed earlier belong to exceptions that contains
619  // this one.
620  if (MI.getOpcode() == WebAssembly::END_TRY)
621  AfterSet.insert(&MI);
622 #endif
623 
624  // If there is a previously placed END_LOOP marker and its header is after
625  // where TRY marker is, this loop is contained within the 'catch' part, so
626  // the END_TRY marker should go after that. Otherwise, the whole try-catch
627  // is contained within this loop, so the END_TRY should go before that.
628  if (MI.getOpcode() == WebAssembly::END_LOOP) {
629  // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they
630  // are in the same BB, LOOP is always before TRY.
631  if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber())
632  BeforeSet.insert(&MI);
633 #ifndef NDEBUG
634  else
635  AfterSet.insert(&MI);
636 #endif
637  }
638 
639  // It is not possible for an END_BLOCK to be already in this block.
640  }
641 
642  // Mark the end of the TRY.
643  InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet);
644  MachineInstr *End =
645  BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(),
646  TII.get(WebAssembly::END_TRY));
647  registerTryScope(Begin, End, &MBB);
648 
649  // Track the farthest-spanning scope that ends at this point. We create two
650  // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB
651  // with 'try'). We need to create 'catch' -> 'try' mapping here too because
652  // markers should not span across 'catch'. For example, this should not
653  // happen:
654  //
655  // try
656  // block --| (X)
657  // catch |
658  // end_block --|
659  // end_try
660  for (auto *End : {&MBB, Cont})
661  updateScopeTops(Header, End);
662 }
663 
664 void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
665  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
666 
667  // When there is an unconditional branch right before a catch instruction and
668  // it branches to the end of end_try marker, we don't need the branch, because
669  // it there is no exception, the control flow transfers to that point anyway.
670  // bb0:
671  // try
672  // ...
673  // br bb2 <- Not necessary
674  // bb1 (ehpad):
675  // catch
676  // ...
677  // bb2: <- Continuation BB
678  // end
679  //
680  // A more involved case: When the BB where 'end' is located is an another EH
681  // pad, the Cont (= continuation) BB is that EH pad's 'end' BB. For example,
682  // bb0:
683  // try
684  // try
685  // ...
686  // br bb3 <- Not necessary
687  // bb1 (ehpad):
688  // catch
689  // bb2 (ehpad):
690  // end
691  // catch
692  // ...
693  // bb3: <- Continuation BB
694  // end
695  //
696  // When the EH pad at hand is bb1, its matching end_try is in bb2. But it is
697  // another EH pad, so bb0's continuation BB becomes bb3. So 'br bb3' in the
698  // code can be deleted. This is why we run 'while' until 'Cont' is not an EH
699  // pad.
700  for (auto &MBB : MF) {
701  if (!MBB.isEHPad())
702  continue;
703 
704  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
706  MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
707 
708  MachineBasicBlock *Cont = &MBB;
709  while (Cont->isEHPad()) {
710  MachineInstr *Try = EHPadToTry[Cont];
711  MachineInstr *EndTry = BeginToEnd[Try];
712  // We started from an EH pad, so the end marker cannot be a delegate
713  assert(EndTry->getOpcode() != WebAssembly::DELEGATE);
714  Cont = EndTry->getParent();
715  }
716 
717  bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
718  // This condition means either
719  // 1. This BB ends with a single unconditional branch whose destinaion is
720  // Cont.
721  // 2. This BB ends with a conditional branch followed by an unconditional
722  // branch, and the unconditional branch's destination is Cont.
723  // In both cases, we want to remove the last (= unconditional) branch.
724  if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
725  (!Cond.empty() && FBB && FBB == Cont))) {
726  bool ErasedUncondBr = false;
727  (void)ErasedUncondBr;
728  for (auto I = EHPadLayoutPred->end(), E = EHPadLayoutPred->begin();
729  I != E; --I) {
730  auto PrevI = std::prev(I);
731  if (PrevI->isTerminator()) {
732  assert(PrevI->getOpcode() == WebAssembly::BR);
733  PrevI->eraseFromParent();
734  ErasedUncondBr = true;
735  break;
736  }
737  }
738  assert(ErasedUncondBr && "Unconditional branch not erased!");
739  }
740  }
741 
742  // When there are block / end_block markers that overlap with try / end_try
743  // markers, and the block and try markers' return types are the same, the
744  // block /end_block markers are not necessary, because try / end_try markers
745  // also can serve as boundaries for branches.
746  // block <- Not necessary
747  // try
748  // ...
749  // catch
750  // ...
751  // end
752  // end <- Not necessary
754  for (auto &MBB : MF) {
755  for (auto &MI : MBB) {
756  if (MI.getOpcode() != WebAssembly::TRY)
757  continue;
758  MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
759  if (EndTry->getOpcode() == WebAssembly::DELEGATE)
760  continue;
761 
762  MachineBasicBlock *TryBB = Try->getParent();
763  MachineBasicBlock *Cont = EndTry->getParent();
764  int64_t RetType = Try->getOperand(0).getImm();
765  for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());
766  B != TryBB->begin() && E != Cont->end() &&
767  std::prev(B)->getOpcode() == WebAssembly::BLOCK &&
768  E->getOpcode() == WebAssembly::END_BLOCK &&
769  std::prev(B)->getOperand(0).getImm() == RetType;
770  --B, ++E) {
771  ToDelete.push_back(&*std::prev(B));
772  ToDelete.push_back(&*E);
773  }
774  }
775  }
776  for (auto *MI : ToDelete) {
777  if (MI->getOpcode() == WebAssembly::BLOCK)
778  unregisterScope(MI);
779  MI->eraseFromParent();
780  }
781 }
782 
783 // Get the appropriate copy opcode for the given register class.
784 static unsigned getCopyOpcode(const TargetRegisterClass *RC) {
785  if (RC == &WebAssembly::I32RegClass)
786  return WebAssembly::COPY_I32;
787  if (RC == &WebAssembly::I64RegClass)
788  return WebAssembly::COPY_I64;
789  if (RC == &WebAssembly::F32RegClass)
790  return WebAssembly::COPY_F32;
791  if (RC == &WebAssembly::F64RegClass)
792  return WebAssembly::COPY_F64;
793  if (RC == &WebAssembly::V128RegClass)
794  return WebAssembly::COPY_V128;
795  if (RC == &WebAssembly::FUNCREFRegClass)
796  return WebAssembly::COPY_FUNCREF;
797  if (RC == &WebAssembly::EXTERNREFRegClass)
798  return WebAssembly::COPY_EXTERNREF;
799  llvm_unreachable("Unexpected register class");
800 }
801 
802 // When MBB is split into MBB and Split, we should unstackify defs in MBB that
803 // have their uses in Split.
805  MachineBasicBlock &Split) {
806  MachineFunction &MF = *MBB.getParent();
807  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
808  auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
809  auto &MRI = MF.getRegInfo();
810 
811  for (auto &MI : Split) {
812  for (auto &MO : MI.explicit_uses()) {
813  if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg()))
814  continue;
815  if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg()))
816  if (Def->getParent() == &MBB)
817  MFI.unstackifyVReg(MO.getReg());
818  }
819  }
820 
821  // In RegStackify, when a register definition is used multiple times,
822  // Reg = INST ...
823  // INST ..., Reg, ...
824  // INST ..., Reg, ...
825  // INST ..., Reg, ...
826  //
827  // we introduce a TEE, which has the following form:
828  // DefReg = INST ...
829  // TeeReg, Reg = TEE_... DefReg
830  // INST ..., TeeReg, ...
831  // INST ..., Reg, ...
832  // INST ..., Reg, ...
833  // with DefReg and TeeReg stackified but Reg not stackified.
834  //
835  // But the invariant that TeeReg should be stackified can be violated while we
836  // unstackify registers in the split BB above. In this case, we convert TEEs
837  // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals.
838  // DefReg = INST ...
839  // TeeReg = COPY DefReg
840  // Reg = COPY DefReg
841  // INST ..., TeeReg, ...
842  // INST ..., Reg, ...
843  // INST ..., Reg, ...
844  for (auto I = MBB.begin(), E = MBB.end(); I != E;) {
845  MachineInstr &MI = *I++;
846  if (!WebAssembly::isTee(MI.getOpcode()))
847  continue;
848  Register TeeReg = MI.getOperand(0).getReg();
849  Register Reg = MI.getOperand(1).getReg();
850  Register DefReg = MI.getOperand(2).getReg();
851  if (!MFI.isVRegStackified(TeeReg)) {
852  // Now we are not using TEE anymore, so unstackify DefReg too
853  MFI.unstackifyVReg(DefReg);
854  unsigned CopyOpc = getCopyOpcode(MRI.getRegClass(DefReg));
855  BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg)
856  .addReg(DefReg);
857  BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg);
858  MI.eraseFromParent();
859  }
860  }
861 }
862 
863 // Wrap the given range of instruction with try-delegate. RangeBegin and
864 // RangeEnd are inclusive.
865 void WebAssemblyCFGStackify::addTryDelegate(MachineInstr *RangeBegin,
866  MachineInstr *RangeEnd,
867  MachineBasicBlock *DelegateDest) {
868  auto *BeginBB = RangeBegin->getParent();
869  auto *EndBB = RangeEnd->getParent();
870  MachineFunction &MF = *BeginBB->getParent();
871  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
872  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
873 
874  // Local expression tree before the first call of this range should go
875  // after the nested TRY.
877  AfterSet.insert(RangeBegin);
878  for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();
879  I != E; --I) {
880  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
881  continue;
882  if (WebAssembly::isChild(*std::prev(I), MFI))
883  AfterSet.insert(&*std::prev(I));
884  else
885  break;
886  }
887 
888  // Create the nested try instruction.
889  auto TryPos = getLatestInsertPos(
890  BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
891  MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(),
892  TII.get(WebAssembly::TRY))
894 
895  // Create a BB to insert the 'delegate' instruction.
896  MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock();
897  // If the destination of 'delegate' is not the caller, adds the destination to
898  // the BB's successors.
899  if (DelegateDest != FakeCallerBB)
900  DelegateBB->addSuccessor(DelegateDest);
901 
902  auto SplitPos = std::next(RangeEnd->getIterator());
903  if (SplitPos == EndBB->end()) {
904  // If the range's end instruction is at the end of the BB, insert the new
905  // delegate BB after the current BB.
906  MF.insert(std::next(EndBB->getIterator()), DelegateBB);
907  EndBB->addSuccessor(DelegateBB);
908 
909  } else {
910  // When the split pos is in the middle of a BB, we split the BB into two and
911  // put the 'delegate' BB in between. We normally create a split BB and make
912  // it a successor of the original BB (PostSplit == true), but in case the BB
913  // is an EH pad and the split pos is before 'catch', we should preserve the
914  // BB's property, including that it is an EH pad, in the later part of the
915  // BB, where 'catch' is. In this case we set PostSplit to false.
916  bool PostSplit = true;
917  if (EndBB->isEHPad()) {
918  for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
919  I != E; ++I) {
920  if (WebAssembly::isCatch(I->getOpcode())) {
921  PostSplit = false;
922  break;
923  }
924  }
925  }
926 
927  MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
928  if (PostSplit) {
929  // If the range's end instruction is in the middle of the BB, we split the
930  // BB into two and insert the delegate BB in between.
931  // - Before:
932  // bb:
933  // range_end
934  // other_insts
935  //
936  // - After:
937  // pre_bb: (previous 'bb')
938  // range_end
939  // delegate_bb: (new)
940  // delegate
941  // post_bb: (new)
942  // other_insts
943  PreBB = EndBB;
944  PostBB = MF.CreateMachineBasicBlock();
945  MF.insert(std::next(PreBB->getIterator()), PostBB);
946  MF.insert(std::next(PreBB->getIterator()), DelegateBB);
947  PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
948  PostBB->transferSuccessors(PreBB);
949  } else {
950  // - Before:
951  // ehpad:
952  // range_end
953  // catch
954  // ...
955  //
956  // - After:
957  // pre_bb: (new)
958  // range_end
959  // delegate_bb: (new)
960  // delegate
961  // post_bb: (previous 'ehpad')
962  // catch
963  // ...
964  assert(EndBB->isEHPad());
965  PreBB = MF.CreateMachineBasicBlock();
966  PostBB = EndBB;
967  MF.insert(PostBB->getIterator(), PreBB);
968  MF.insert(PostBB->getIterator(), DelegateBB);
969  PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
970  // We don't need to transfer predecessors of the EH pad to 'PreBB',
971  // because an EH pad's predecessors are all through unwind edges and they
972  // should still unwind to the EH pad, not PreBB.
973  }
974  unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);
975  PreBB->addSuccessor(DelegateBB);
976  PreBB->addSuccessor(PostBB);
977  }
978 
979  // Add 'delegate' instruction in the delegate BB created above.
980  MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(),
982  .addMBB(DelegateDest);
983  registerTryScope(Try, Delegate, nullptr);
984 }
985 
986 bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {
987  // Linearizing the control flow by placing TRY / END_TRY markers can create
988  // mismatches in unwind destinations for throwing instructions, such as calls.
989  //
990  // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate'
991  // instruction delegates an exception to an outer 'catch'. It can target not
992  // only 'catch' but all block-like structures including another 'delegate',
993  // but with slightly different semantics than branches. When it targets a
994  // 'catch', it will delegate the exception to that catch. It is being
995  // discussed how to define the semantics when 'delegate''s target is a non-try
996  // block: it will either be a validation failure or it will target the next
997  // outer try-catch. But anyway our LLVM backend currently does not generate
998  // such code. The example below illustrates where the 'delegate' instruction
999  // in the middle will delegate the exception to, depending on the value of N.
1000  // try
1001  // try
1002  // block
1003  // try
1004  // try
1005  // call @foo
1006  // delegate N ;; Where will this delegate to?
1007  // catch ;; N == 0
1008  // end
1009  // end ;; N == 1 (invalid; will not be generated)
1010  // delegate ;; N == 2
1011  // catch ;; N == 3
1012  // end
1013  // ;; N == 4 (to caller)
1014 
1015  // 1. When an instruction may throw, but the EH pad it will unwind to can be
1016  // different from the original CFG.
1017  //
1018  // Example: we have the following CFG:
1019  // bb0:
1020  // call @foo ; if it throws, unwind to bb2
1021  // bb1:
1022  // call @bar ; if it throws, unwind to bb3
1023  // bb2 (ehpad):
1024  // catch
1025  // ...
1026  // bb3 (ehpad)
1027  // catch
1028  // ...
1029  //
1030  // And the CFG is sorted in this order. Then after placing TRY markers, it
1031  // will look like: (BB markers are omitted)
1032  // try
1033  // try
1034  // call @foo
1035  // call @bar ;; if it throws, unwind to bb3
1036  // catch ;; ehpad (bb2)
1037  // ...
1038  // end_try
1039  // catch ;; ehpad (bb3)
1040  // ...
1041  // end_try
1042  //
1043  // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it
1044  // is supposed to end up. We solve this problem by wrapping the mismatching
1045  // call with an inner try-delegate that rethrows the exception to the right
1046  // 'catch'.
1047  //
1048  // try
1049  // try
1050  // call @foo
1051  // try ;; (new)
1052  // call @bar
1053  // delegate 1 (bb3) ;; (new)
1054  // catch ;; ehpad (bb2)
1055  // ...
1056  // end_try
1057  // catch ;; ehpad (bb3)
1058  // ...
1059  // end_try
1060  //
1061  // ---
1062  // 2. The same as 1, but in this case an instruction unwinds to a caller
1063  // function and not another EH pad.
1064  //
1065  // Example: we have the following CFG:
1066  // bb0:
1067  // call @foo ; if it throws, unwind to bb2
1068  // bb1:
1069  // call @bar ; if it throws, unwind to caller
1070  // bb2 (ehpad):
1071  // catch
1072  // ...
1073  //
1074  // And the CFG is sorted in this order. Then after placing TRY markers, it
1075  // will look like:
1076  // try
1077  // call @foo
1078  // call @bar ;; if it throws, unwind to caller
1079  // catch ;; ehpad (bb2)
1080  // ...
1081  // end_try
1082  //
1083  // Now if bar() throws, it is going to end up ip in bb2, when it is supposed
1084  // throw up to the caller. We solve this problem in the same way, but in this
1085  // case 'delegate's immediate argument is the number of block depths + 1,
1086  // which means it rethrows to the caller.
1087  // try
1088  // call @foo
1089  // try ;; (new)
1090  // call @bar
1091  // delegate 1 (caller) ;; (new)
1092  // catch ;; ehpad (bb2)
1093  // ...
1094  // end_try
1095  //
1096  // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the
1097  // caller, it will take a fake BB generated by getFakeCallerBlock(), which
1098  // will be converted to a correct immediate argument later.
1099  //
1100  // In case there are multiple calls in a BB that may throw to the caller, they
1101  // can be wrapped together in one nested try-delegate scope. (In 1, this
1102  // couldn't happen, because may-throwing instruction there had an unwind
1103  // destination, i.e., it was an invoke before, and there could be only one
1104  // invoke within a BB.)
1105 
1107  // Range of intructions to be wrapped in a new nested try/catch. A range
1108  // exists in a single BB and does not span multiple BBs.
1109  using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1110  // In original CFG, <unwind destination BB, a vector of try ranges>
1112 
1113  // Gather possibly throwing calls (i.e., previously invokes) whose current
1114  // unwind destination is not the same as the original CFG. (Case 1)
1115 
1116  for (auto &MBB : reverse(MF)) {
1117  bool SeenThrowableInstInBB = false;
1118  for (auto &MI : reverse(MBB)) {
1119  if (MI.getOpcode() == WebAssembly::TRY)
1120  EHPadStack.pop_back();
1121  else if (WebAssembly::isCatch(MI.getOpcode()))
1122  EHPadStack.push_back(MI.getParent());
1123 
1124  // In this loop we only gather calls that have an EH pad to unwind. So
1125  // there will be at most 1 such call (= invoke) in a BB, so after we've
1126  // seen one, we can skip the rest of BB. Also if MBB has no EH pad
1127  // successor or MI does not throw, this is not an invoke.
1128  if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
1130  continue;
1131  SeenThrowableInstInBB = true;
1132 
1133  // If the EH pad on the stack top is where this instruction should unwind
1134  // next, we're good.
1135  MachineBasicBlock *UnwindDest = getFakeCallerBlock(MF);
1136  for (auto *Succ : MBB.successors()) {
1137  // Even though semantically a BB can have multiple successors in case an
1138  // exception is not caught by a catchpad, in our backend implementation
1139  // it is guaranteed that a BB can have at most one EH pad successor. For
1140  // details, refer to comments in findWasmUnwindDestinations function in
1141  // SelectionDAGBuilder.cpp.
1142  if (Succ->isEHPad()) {
1143  UnwindDest = Succ;
1144  break;
1145  }
1146  }
1147  if (EHPadStack.back() == UnwindDest)
1148  continue;
1149 
1150  // Include EH_LABELs in the range before and afer the invoke
1151  MachineInstr *RangeBegin = &MI, *RangeEnd = &MI;
1152  if (RangeBegin->getIterator() != MBB.begin() &&
1153  std::prev(RangeBegin->getIterator())->isEHLabel())
1154  RangeBegin = &*std::prev(RangeBegin->getIterator());
1155  if (std::next(RangeEnd->getIterator()) != MBB.end() &&
1156  std::next(RangeEnd->getIterator())->isEHLabel())
1157  RangeEnd = &*std::next(RangeEnd->getIterator());
1158 
1159  // If not, record the range.
1160  UnwindDestToTryRanges[UnwindDest].push_back(
1161  TryRange(RangeBegin, RangeEnd));
1162  LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName()
1163  << "\nCall = " << MI
1164  << "\nOriginal dest = " << UnwindDest->getName()
1165  << " Current dest = " << EHPadStack.back()->getName()
1166  << "\n\n");
1167  }
1168  }
1169 
1170  assert(EHPadStack.empty());
1171 
1172  // Gather possibly throwing calls that are supposed to unwind up to the caller
1173  // if they throw, but currently unwind to an incorrect destination. Unlike the
1174  // loop above, there can be multiple calls within a BB that unwind to the
1175  // caller, which we should group together in a range. (Case 2)
1176 
1177  MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
1178 
1179  // Record the range.
1180  auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) {
1181  UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1182  TryRange(RangeBegin, RangeEnd));
1183  LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "
1184  << RangeBegin->getParent()->getName()
1185  << "\nRange begin = " << *RangeBegin
1186  << "Range end = " << *RangeEnd
1187  << "\nOriginal dest = caller Current dest = "
1188  << CurrentDest->getName() << "\n\n");
1189  RangeBegin = RangeEnd = nullptr; // Reset range pointers
1190  };
1191 
1192  for (auto &MBB : reverse(MF)) {
1193  bool SeenThrowableInstInBB = false;
1194  for (auto &MI : reverse(MBB)) {
1195  bool MayThrow = WebAssembly::mayThrow(MI);
1196 
1197  // If MBB has an EH pad successor and this is the last instruction that
1198  // may throw, this instruction unwinds to the EH pad and not to the
1199  // caller.
1200  if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB)
1201  SeenThrowableInstInBB = true;
1202 
1203  // We wrap up the current range when we see a marker even if we haven't
1204  // finished a BB.
1205  else if (RangeEnd && WebAssembly::isMarker(MI.getOpcode()))
1206  RecordCallerMismatchRange(EHPadStack.back());
1207 
1208  // If EHPadStack is empty, that means it correctly unwinds to the caller
1209  // if it throws, so we're good. If MI does not throw, we're good too.
1210  else if (EHPadStack.empty() || !MayThrow) {
1211  }
1212 
1213  // We found an instruction that unwinds to the caller but currently has an
1214  // incorrect unwind destination. Create a new range or increment the
1215  // currently existing range.
1216  else {
1217  if (!RangeEnd)
1218  RangeBegin = RangeEnd = &MI;
1219  else
1220  RangeBegin = &MI;
1221  }
1222 
1223  // Update EHPadStack.
1224  if (MI.getOpcode() == WebAssembly::TRY)
1225  EHPadStack.pop_back();
1226  else if (WebAssembly::isCatch(MI.getOpcode()))
1227  EHPadStack.push_back(MI.getParent());
1228  }
1229 
1230  if (RangeEnd)
1231  RecordCallerMismatchRange(EHPadStack.back());
1232  }
1233 
1234  assert(EHPadStack.empty());
1235 
1236  // We don't have any unwind destination mismatches to resolve.
1237  if (UnwindDestToTryRanges.empty())
1238  return false;
1239 
1240  // Now we fix the mismatches by wrapping calls with inner try-delegates.
1241  for (auto &P : UnwindDestToTryRanges) {
1242  NumCallUnwindMismatches += P.second.size();
1243  MachineBasicBlock *UnwindDest = P.first;
1244  auto &TryRanges = P.second;
1245 
1246  for (auto Range : TryRanges) {
1247  MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1248  std::tie(RangeBegin, RangeEnd) = Range;
1249  auto *MBB = RangeBegin->getParent();
1250 
1251  // If this BB has an EH pad successor, i.e., ends with an 'invoke', now we
1252  // are going to wrap the invoke with try-delegate, making the 'delegate'
1253  // BB the new successor instead, so remove the EH pad succesor here. The
1254  // BB may not have an EH pad successor if calls in this BB throw to the
1255  // caller.
1256  MachineBasicBlock *EHPad = nullptr;
1257  for (auto *Succ : MBB->successors()) {
1258  if (Succ->isEHPad()) {
1259  EHPad = Succ;
1260  break;
1261  }
1262  }
1263  if (EHPad)
1264  MBB->removeSuccessor(EHPad);
1265 
1266  addTryDelegate(RangeBegin, RangeEnd, UnwindDest);
1267  }
1268  }
1269 
1270  return true;
1271 }
1272 
1273 bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {
1274  // There is another kind of unwind destination mismatches besides call unwind
1275  // mismatches, which we will call "catch unwind mismatches". See this example
1276  // after the marker placement:
1277  // try
1278  // try
1279  // call @foo
1280  // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
1281  // ...
1282  // end_try
1283  // catch_all ;; ehpad B
1284  // ...
1285  // end_try
1286  //
1287  // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
1288  // throws a foreign exception that is not caught by ehpad A, and its next
1289  // destination should be the caller. But after control flow linearization,
1290  // another EH pad can be placed in between (e.g. ehpad B here), making the
1291  // next unwind destination incorrect. In this case, the foreign exception
1292  // will instead go to ehpad B and will be caught there instead. In this
1293  // example the correct next unwind destination is the caller, but it can be
1294  // another outer catch in other cases.
1295  //
1296  // There is no specific 'call' or 'throw' instruction to wrap with a
1297  // try-delegate, so we wrap the whole try-catch-end with a try-delegate and
1298  // make it rethrow to the right destination, as in the example below:
1299  // try
1300  // try ;; (new)
1301  // try
1302  // call @foo
1303  // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
1304  // ...
1305  // end_try
1306  // delegate 1 (caller) ;; (new)
1307  // catch_all ;; ehpad B
1308  // ...
1309  // end_try
1310 
1311  const auto *EHInfo = MF.getWasmEHFuncInfo();
1313  // For EH pads that have catch unwind mismatches, a map of <EH pad, its
1314  // correct unwind destination>.
1316 
1317  for (auto &MBB : reverse(MF)) {
1318  for (auto &MI : reverse(MBB)) {
1319  if (MI.getOpcode() == WebAssembly::TRY)
1320  EHPadStack.pop_back();
1321  else if (MI.getOpcode() == WebAssembly::DELEGATE)
1322  EHPadStack.push_back(&MBB);
1323  else if (WebAssembly::isCatch(MI.getOpcode())) {
1324  auto *EHPad = &MBB;
1325 
1326  // catch_all always catches an exception, so we don't need to do
1327  // anything
1328  if (MI.getOpcode() == WebAssembly::CATCH_ALL) {
1329  }
1330 
1331  // This can happen when the unwind dest was removed during the
1332  // optimization, e.g. because it was unreachable.
1333  else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
1334  LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName()
1335  << "'s unwind destination does not exist anymore"
1336  << "\n\n");
1337  }
1338 
1339  // The EHPad's next unwind destination is the caller, but we incorrectly
1340  // unwind to another EH pad.
1341  else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) {
1342  EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
1343  LLVM_DEBUG(dbgs()
1344  << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()
1345  << " Original dest = caller Current dest = "
1346  << EHPadStack.back()->getName() << "\n\n");
1347  }
1348 
1349  // The EHPad's next unwind destination is an EH pad, whereas we
1350  // incorrectly unwind to another EH pad.
1351  else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
1352  auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
1353  if (EHPadStack.back() != UnwindDest) {
1354  EHPadToUnwindDest[EHPad] = UnwindDest;
1355  LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "
1356  << EHPad->getName() << " Original dest = "
1357  << UnwindDest->getName() << " Current dest = "
1358  << EHPadStack.back()->getName() << "\n\n");
1359  }
1360  }
1361 
1362  EHPadStack.push_back(EHPad);
1363  }
1364  }
1365  }
1366 
1367  assert(EHPadStack.empty());
1368  if (EHPadToUnwindDest.empty())
1369  return false;
1370  NumCatchUnwindMismatches += EHPadToUnwindDest.size();
1372 
1373  for (auto &P : EHPadToUnwindDest) {
1374  MachineBasicBlock *EHPad = P.first;
1375  MachineBasicBlock *UnwindDest = P.second;
1376  MachineInstr *Try = EHPadToTry[EHPad];
1377  MachineInstr *EndTry = BeginToEnd[Try];
1378  addTryDelegate(Try, EndTry, UnwindDest);
1379  NewEndTryBBs.insert(EndTry->getParent());
1380  }
1381 
1382  // Adding a try-delegate wrapping an existing try-catch-end can make existing
1383  // branch destination BBs invalid. For example,
1384  //
1385  // - Before:
1386  // bb0:
1387  // block
1388  // br bb3
1389  // bb1:
1390  // try
1391  // ...
1392  // bb2: (ehpad)
1393  // catch
1394  // bb3:
1395  // end_try
1396  // end_block ;; 'br bb3' targets here
1397  //
1398  // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap
1399  // this with a try-delegate. Then this becomes:
1400  //
1401  // - After:
1402  // bb0:
1403  // block
1404  // br bb3 ;; invalid destination!
1405  // bb1:
1406  // try ;; (new instruction)
1407  // try
1408  // ...
1409  // bb2: (ehpad)
1410  // catch
1411  // bb3:
1412  // end_try ;; 'br bb3' still incorrectly targets here!
1413  // delegate_bb: ;; (new BB)
1414  // delegate ;; (new instruction)
1415  // split_bb: ;; (new BB)
1416  // end_block
1417  //
1418  // Now 'br bb3' incorrectly branches to an inner scope.
1419  //
1420  // As we can see in this case, when branches target a BB that has both
1421  // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we
1422  // have to remap existing branch destinations so that they target not the
1423  // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's
1424  // in between, so we try to find the next BB with 'end_block' instruction. In
1425  // this example, the 'br bb3' instruction should be remapped to 'br split_bb'.
1426  for (auto &MBB : MF) {
1427  for (auto &MI : MBB) {
1428  if (MI.isTerminator()) {
1429  for (auto &MO : MI.operands()) {
1430  if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) {
1431  auto *BrDest = MO.getMBB();
1432  bool FoundEndBlock = false;
1433  for (; std::next(BrDest->getIterator()) != MF.end();
1434  BrDest = BrDest->getNextNode()) {
1435  for (const auto &MI : *BrDest) {
1436  if (MI.getOpcode() == WebAssembly::END_BLOCK) {
1437  FoundEndBlock = true;
1438  break;
1439  }
1440  }
1441  if (FoundEndBlock)
1442  break;
1443  }
1444  assert(FoundEndBlock);
1445  MO.setMBB(BrDest);
1446  }
1447  }
1448  }
1449  }
1450  }
1451 
1452  return true;
1453 }
1454 
1455 void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {
1456  // Renumber BBs and recalculate ScopeTop info because new BBs might have been
1457  // created and inserted during fixing unwind mismatches.
1458  MF.RenumberBlocks();
1459  ScopeTops.clear();
1460  ScopeTops.resize(MF.getNumBlockIDs());
1461  for (auto &MBB : reverse(MF)) {
1462  for (auto &MI : reverse(MBB)) {
1463  if (ScopeTops[MBB.getNumber()])
1464  break;
1465  switch (MI.getOpcode()) {
1467  case WebAssembly::END_LOOP:
1468  case WebAssembly::END_TRY:
1469  case WebAssembly::DELEGATE:
1470  updateScopeTops(EndToBegin[&MI]->getParent(), &MBB);
1471  break;
1472  case WebAssembly::CATCH:
1473  case WebAssembly::CATCH_ALL:
1474  updateScopeTops(EHPadToTry[&MBB]->getParent(), &MBB);
1475  break;
1476  }
1477  }
1478  }
1479 }
1480 
1481 /// In normal assembly languages, when the end of a function is unreachable,
1482 /// because the function ends in an infinite loop or a noreturn call or similar,
1483 /// it isn't necessary to worry about the function return type at the end of
1484 /// the function, because it's never reached. However, in WebAssembly, blocks
1485 /// that end at the function end need to have a return type signature that
1486 /// matches the function signature, even though it's unreachable. This function
1487 /// checks for such cases and fixes up the signatures.
1488 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
1489  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1490 
1491  if (MFI.getResults().empty())
1492  return;
1493 
1494  // MCInstLower will add the proper types to multivalue signatures based on the
1495  // function return type
1496  WebAssembly::BlockType RetType =
1497  MFI.getResults().size() > 1
1500  WebAssembly::toValType(MFI.getResults().front()));
1501 
1503  Worklist.push_back(MF.rbegin()->rbegin());
1504 
1506  auto *MBB = It->getParent();
1507  while (It != MBB->rend()) {
1508  MachineInstr &MI = *It++;
1509  if (MI.isPosition() || MI.isDebugInstr())
1510  continue;
1511  switch (MI.getOpcode()) {
1512  case WebAssembly::END_TRY: {
1513  // If a 'try''s return type is fixed, both its try body and catch body
1514  // should satisfy the return type, so we need to search 'end'
1515  // instructions before its corresponding 'catch' too.
1516  auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]);
1517  assert(EHPad);
1518  auto NextIt =
1519  std::next(WebAssembly::findCatch(EHPad)->getReverseIterator());
1520  if (NextIt != EHPad->rend())
1521  Worklist.push_back(NextIt);
1523  }
1525  case WebAssembly::END_LOOP:
1526  EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1527  continue;
1528  default:
1529  // Something other than an `end`. We're done for this BB.
1530  return;
1531  }
1532  }
1533  // We've reached the beginning of a BB. Continue the search in the previous
1534  // BB.
1535  Worklist.push_back(MBB->getPrevNode()->rbegin());
1536  };
1537 
1538  while (!Worklist.empty())
1539  Process(Worklist.pop_back_val());
1540 }
1541 
1542 // WebAssembly functions end with an end instruction, as if the function body
1543 // were a block.
1545  const WebAssemblyInstrInfo &TII) {
1546  BuildMI(MF.back(), MF.back().end(),
1547  MF.back().findPrevDebugLoc(MF.back().end()),
1548  TII.get(WebAssembly::END_FUNCTION));
1549 }
1550 
1551 /// Insert LOOP/TRY/BLOCK markers at appropriate places.
1552 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
1553  // We allocate one more than the number of blocks in the function to
1554  // accommodate for the possible fake block we may insert at the end.
1555  ScopeTops.resize(MF.getNumBlockIDs() + 1);
1556  // Place the LOOP for MBB if MBB is the header of a loop.
1557  for (auto &MBB : MF)
1558  placeLoopMarker(MBB);
1559 
1560  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1561  for (auto &MBB : MF) {
1562  if (MBB.isEHPad()) {
1563  // Place the TRY for MBB if MBB is the EH pad of an exception.
1565  MF.getFunction().hasPersonalityFn())
1566  placeTryMarker(MBB);
1567  } else {
1568  // Place the BLOCK for MBB if MBB is branched to from above.
1569  placeBlockMarker(MBB);
1570  }
1571  }
1572  // Fix mismatches in unwind destinations induced by linearizing the code.
1574  MF.getFunction().hasPersonalityFn()) {
1575  bool Changed = fixCallUnwindMismatches(MF);
1576  Changed |= fixCatchUnwindMismatches(MF);
1577  if (Changed)
1578  recalculateScopeTops(MF);
1579  }
1580 }
1581 
1582 unsigned WebAssemblyCFGStackify::getBranchDepth(
1583  const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
1584  unsigned Depth = 0;
1585  for (auto X : reverse(Stack)) {
1586  if (X.first == MBB)
1587  break;
1588  ++Depth;
1589  }
1590  assert(Depth < Stack.size() && "Branch destination should be in scope");
1591  return Depth;
1592 }
1593 
1594 unsigned WebAssemblyCFGStackify::getDelegateDepth(
1595  const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
1596  if (MBB == FakeCallerBB)
1597  return Stack.size();
1598  // Delegate's destination is either a catch or a another delegate BB. When the
1599  // destination is another delegate, we can compute the argument in the same
1600  // way as branches, because the target delegate BB only contains the single
1601  // delegate instruction.
1602  if (!MBB->isEHPad()) // Target is a delegate BB
1603  return getBranchDepth(Stack, MBB);
1604 
1605  // When the delegate's destination is a catch BB, we need to use its
1606  // corresponding try's end_try BB because Stack contains each marker's end BB.
1607  // Also we need to check if the end marker instruction matches, because a
1608  // single BB can contain multiple end markers, like this:
1609  // bb:
1610  // END_BLOCK
1611  // END_TRY
1612  // END_BLOCK
1613  // END_TRY
1614  // ...
1615  //
1616  // In case of branches getting the immediate that targets any of these is
1617  // fine, but delegate has to exactly target the correct try.
1618  unsigned Depth = 0;
1619  const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];
1620  for (auto X : reverse(Stack)) {
1621  if (X.first == EndTry->getParent() && X.second == EndTry)
1622  break;
1623  ++Depth;
1624  }
1625  assert(Depth < Stack.size() && "Delegate destination should be in scope");
1626  return Depth;
1627 }
1628 
1629 unsigned WebAssemblyCFGStackify::getRethrowDepth(
1630  const SmallVectorImpl<EndMarkerInfo> &Stack,
1631  const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack) {
1632  unsigned Depth = 0;
1633  // In our current implementation, rethrows always rethrow the exception caught
1634  // by the innermost enclosing catch. This means while traversing Stack in the
1635  // reverse direction, when we encounter END_TRY, we should check if the
1636  // END_TRY corresponds to the current innermost EH pad. For example:
1637  // try
1638  // ...
1639  // catch ;; (a)
1640  // try
1641  // rethrow 1 ;; (b)
1642  // catch ;; (c)
1643  // rethrow 0 ;; (d)
1644  // end ;; (e)
1645  // end ;; (f)
1646  //
1647  // When we are at 'rethrow' (d), while reversely traversing Stack the first
1648  // 'end' we encounter is the 'end' (e), which corresponds to the 'catch' (c).
1649  // And 'rethrow' (d) rethrows the exception caught by 'catch' (c), so we stop
1650  // there and the depth should be 0. But when we are at 'rethrow' (b), it
1651  // rethrows the exception caught by 'catch' (a), so when traversing Stack
1652  // reversely, we should skip the 'end' (e) and choose 'end' (f), which
1653  // corresponds to 'catch' (a).
1654  for (auto X : reverse(Stack)) {
1655  const MachineInstr *End = X.second;
1656  if (End->getOpcode() == WebAssembly::END_TRY) {
1657  auto *EHPad = TryToEHPad[EndToBegin[End]];
1658  if (EHPadStack.back() == EHPad)
1659  break;
1660  }
1661  ++Depth;
1662  }
1663  assert(Depth < Stack.size() && "Rethrow destination should be in scope");
1664  return Depth;
1665 }
1666 
1667 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
1668  // Now rewrite references to basic blocks to be depth immediates.
1671  for (auto &MBB : reverse(MF)) {
1672  for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) {
1673  MachineInstr &MI = *I;
1674  switch (MI.getOpcode()) {
1675  case WebAssembly::BLOCK:
1676  case WebAssembly::TRY:
1677  assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
1678  MBB.getNumber() &&
1679  "Block/try marker should be balanced");
1680  Stack.pop_back();
1681  break;
1682 
1683  case WebAssembly::LOOP:
1684  assert(Stack.back().first == &MBB && "Loop top should be balanced");
1685  Stack.pop_back();
1686  break;
1687 
1689  Stack.push_back(std::make_pair(&MBB, &MI));
1690  break;
1691 
1692  case WebAssembly::END_TRY: {
1693  // We handle DELEGATE in the default level, because DELEGATE has
1694  // immediate operands to rewrite.
1695  Stack.push_back(std::make_pair(&MBB, &MI));
1696  auto *EHPad = TryToEHPad[EndToBegin[&MI]];
1697  EHPadStack.push_back(EHPad);
1698  break;
1699  }
1700 
1701  case WebAssembly::END_LOOP:
1702  Stack.push_back(std::make_pair(EndToBegin[&MI]->getParent(), &MI));
1703  break;
1704 
1705  case WebAssembly::CATCH:
1706  case WebAssembly::CATCH_ALL:
1707  EHPadStack.pop_back();
1708  break;
1709 
1710  case WebAssembly::RETHROW:
1711  MI.getOperand(0).setImm(getRethrowDepth(Stack, EHPadStack));
1712  break;
1713 
1714  default:
1715  if (MI.isTerminator()) {
1716  // Rewrite MBB operands to be depth immediates.
1717  SmallVector<MachineOperand, 4> Ops(MI.operands());
1718  while (MI.getNumOperands() > 0)
1719  MI.RemoveOperand(MI.getNumOperands() - 1);
1720  for (auto MO : Ops) {
1721  if (MO.isMBB()) {
1722  if (MI.getOpcode() == WebAssembly::DELEGATE)
1724  getDelegateDepth(Stack, MO.getMBB()));
1725  else
1727  getBranchDepth(Stack, MO.getMBB()));
1728  }
1729  MI.addOperand(MF, MO);
1730  }
1731  }
1732 
1733  if (MI.getOpcode() == WebAssembly::DELEGATE)
1734  Stack.push_back(std::make_pair(&MBB, &MI));
1735  break;
1736  }
1737  }
1738  }
1739  assert(Stack.empty() && "Control flow should be balanced");
1740 }
1741 
1742 void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) {
1743  if (FakeCallerBB)
1744  MF.DeleteMachineBasicBlock(FakeCallerBB);
1745  AppendixBB = FakeCallerBB = nullptr;
1746 }
1747 
1748 void WebAssemblyCFGStackify::releaseMemory() {
1749  ScopeTops.clear();
1750  BeginToEnd.clear();
1751  EndToBegin.clear();
1752  TryToEHPad.clear();
1753  EHPadToTry.clear();
1754 }
1755 
1756 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
1757  LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
1758  "********** Function: "
1759  << MF.getName() << '\n');
1760  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1761 
1762  releaseMemory();
1763 
1764  // Liveness is not tracked for VALUE_STACK physreg.
1766 
1767  // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
1768  placeMarkers(MF);
1769 
1770  // Remove unnecessary instructions possibly introduced by try/end_trys.
1773  removeUnnecessaryInstrs(MF);
1774 
1775  // Convert MBB operands in terminators to relative depth immediates.
1776  rewriteDepthImmediates(MF);
1777 
1778  // Fix up block/loop/try signatures at the end of the function to conform to
1779  // WebAssembly's rules.
1780  fixEndsAtEndOfFunction(MF);
1781 
1782  // Add an end instruction at the end of the function body.
1783  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1785  .getTargetTriple()
1786  .isOSBinFormatELF())
1787  appendEndToFunction(MF, TII);
1788 
1789  cleanupFunctionData(MF);
1790 
1791  MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
1792  return true;
1793 }
llvm::WebAssembly::isChild
bool isChild(const MachineInstr &MI, const WebAssemblyFunctionInfo &MFI)
Test whether MI is a child of some other node in an expression tree.
Definition: WebAssemblyUtilities.cpp:28
llvm::WebAssemblySubtarget::getTargetTriple
const Triple & getTargetTriple() const
Definition: WebAssemblySubtarget.h:83
WebAssemblySortRegion.h
This file implements regions used in CFGSort and CFGStackify.
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:132
llvm
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
WebAssembly.h
llvm::WebAssembly::isCatch
bool isCatch(unsigned Opc)
Definition: WebAssemblyMCTargetDesc.h:434
llvm::WebAssembly::findCatch
MachineInstr * findCatch(MachineBasicBlock *EHPad)
Find a catch instruction from an EH pad.
Definition: WebAssemblyUtilities.cpp:120
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
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:197
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::HexagonInstrInfo::analyzeBranch
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....
Definition: HexagonInstrInfo.cpp:391
llvm::MCAsmInfo
This class is intended to be used as a base class for asm properties and features specific to the tar...
Definition: MCAsmInfo.h:56
llvm::WebAssembly::isTee
bool isTee(unsigned Opc)
Definition: WebAssemblyMCTargetDesc.h:356
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:739
llvm::MachineRegisterInfo::getUniqueVRegDef
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
Definition: MachineRegisterInfo.cpp:411
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::WebAssembly::mayThrow
bool mayThrow(const MachineInstr &MI)
Definition: WebAssemblyUtilities.cpp:39
llvm::MachineFunction::back
const MachineBasicBlock & back() const
Definition: MachineFunction.h:751
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
getLatestInsertPos
static MachineBasicBlock::iterator getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, const Container &AfterSet)
Definition: WebAssemblyCFGStackify.cpp:202
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:682
llvm::MachineBasicBlock::findDebugLoc
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions.
Definition: MachineBasicBlock.cpp:1396
DEBUG_TYPE
#define DEBUG_TYPE
Definition: WebAssemblyCFGStackify.cpp:40
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:34
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:338
explicitlyBranchesTo
static bool explicitlyBranchesTo(MachineBasicBlock *Pred, MachineBasicBlock *MBB)
Test whether Pred has any terminators explicitly branching to MBB, as opposed to falling through.
Definition: WebAssemblyCFGStackify.cpp:162
llvm::MachineFunction::insert
void insert(iterator MBBI, MachineBasicBlock *MBB)
Definition: MachineFunction.h:756
llvm::createWebAssemblyCFGStackify
FunctionPass * createWebAssemblyCFGStackify()
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
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:145
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::WebAssembly::isMarker
bool isMarker(unsigned Opc)
Definition: WebAssemblyMCTargetDesc.h:414
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::MachineBasicBlock::terminators
iterator_range< iterator > terminators()
Definition: MachineBasicBlock.h:288
llvm::WebAssemblyException
Definition: WebAssemblyExceptionInfo.h:42
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::WebAssembly::BlockType::Void
@ Void
llvm::sys::Process
A collection of legacy interfaces for querying information about the current executing process.
Definition: Process.h:44
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
getEarliestInsertPos
static MachineBasicBlock::iterator getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet, const Container &AfterSet)
Definition: WebAssemblyCFGStackify.cpp:178
llvm::MachineBasicBlock::addSuccessor
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:743
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:749
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:565
llvm::Triple::isOSBinFormatELF
bool isOSBinFormatELF() const
Tests whether the OS uses the ELF binary format.
Definition: Triple.h:632
MachineLoopInfo.h
TargetMachine.h
llvm::MachineInstrBuilder::addMBB
const MachineInstrBuilder & addMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0) const
Definition: MachineInstrBuilder.h:147
llvm::MachineOperand::CreateImm
static MachineOperand CreateImm(int64_t Val)
Definition: MachineOperand.h:770
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:534
llvm::MachineFunction::getInfo
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
Definition: MachineFunction.h:653
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:488
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::bitc::END_BLOCK
@ END_BLOCK
Definition: BitCodes.h:47
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineFunction::rbegin
reverse_iterator rbegin()
Definition: MachineFunction.h:742
llvm::MachineBasicBlock::rend
reverse_iterator rend()
Definition: MachineBasicBlock.h:278
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::ExceptionHandling::Wasm
@ Wasm
WebAssembly Exception Handling.
llvm::Function::hasPersonalityFn
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:820
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
llvm::AMDGPUISD::LOOP
@ LOOP
Definition: AMDGPUISelLowering.h:350
llvm::MachineFunction::getWasmEHFuncInfo
const WasmEHFuncInfo * getWasmEHFuncInfo() const
getWasmEHFuncInfo - Return information about how the current function uses Wasm exception handling.
Definition: MachineFunction.h:593
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
WebAssemblyUtilities.h
llvm::MachineBasicBlock::findPrevDebugLoc
DebugLoc findPrevDebugLoc(instr_iterator MBBI)
Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE instructions.
Definition: MachineBasicBlock.cpp:1414
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:555
llvm::MachineFunction::push_back
void push_back(MachineBasicBlock *MBB)
Definition: MachineFunction.h:754
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:418
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::DenseMap
Definition: DenseMap.h:714
llvm::WebAssemblyExceptionInfo
Definition: WebAssemblyExceptionInfo.h:123
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::WebAssembly::toValType
wasm::ValType toValType(const MVT &Ty)
Definition: WebAssemblyMCTargetDesc.cpp:133
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:414
llvm::WebAssembly::BlockType::Multivalue
@ Multivalue
llvm::pdb::PDB_MemoryType::Stack
@ Stack
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:522
llvm::ilist_node_with_parent::getPrevNode
NodeTy * getPrevNode()
Definition: ilist_node.h:274
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::WebAssemblyFunctionInfo
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
Definition: WebAssemblyMachineFunctionInfo.h:33
llvm::MachineInstrBuilder::addReg
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Definition: MachineInstrBuilder.h:98
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:349
llvm::MachineBasicBlock::pred_empty
bool pred_empty() const
Definition: MachineBasicBlock.h:331
WebAssemblyMachineFunctionInfo.h
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::ARM::WinEH::ReturnType
ReturnType
Definition: ARMWinEH.h:25
INITIALIZE_PASS
INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false, false) FunctionPass *llvm
Definition: WebAssemblyCFGStackify.cpp:149
llvm::MachineFunction
Definition: MachineFunction.h:227
llvm::TargetMachine::getMCAsmInfo
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
Definition: TargetMachine.h:202
llvm::WebAssemblyFunctionInfo::getResults
const std::vector< MVT > & getResults() const
Definition: WebAssemblyMachineFunctionInfo.h:85
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:94
llvm::MachineBasicBlock::iterator
MachineInstrBundleIterator< MachineInstr > iterator
Definition: MachineBasicBlock.h:233
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:965
MCAsmInfo.h
llvm::MachineFunction::DeleteMachineBasicBlock
void DeleteMachineBasicBlock(MachineBasicBlock *MBB)
DeleteMachineBasicBlock - Delete the given MachineBasicBlock.
Definition: MachineFunction.cpp:421
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:355
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:435
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::MachineBasicBlock::rbegin
reverse_iterator rbegin()
Definition: MachineBasicBlock.h:272
llvm::MachineBasicBlock::splice
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 '...
Definition: MachineBasicBlock.h:859
llvm::MachineBasicBlock::hasEHPadSuccessor
bool hasEHPadSuccessor() const
Definition: MachineBasicBlock.cpp:280
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:478
llvm::MachineBasicBlock::findBranchDebugLoc
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
Definition: MachineBasicBlock.cpp:1435
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:759
llvm::MachineRegisterInfo::invalidateLiveness
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
Definition: MachineRegisterInfo.h:207
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
unstackifyVRegsUsedInSplitBB
static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, MachineBasicBlock &Split)
Definition: WebAssemblyCFGStackify.cpp:804
llvm::WebAssemblySubtarget
Definition: WebAssemblySubtarget.h:35
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:281
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineBasicBlock::isPredecessor
bool isPredecessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a predecessor of this block.
Definition: MachineBasicBlock.cpp:927
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
LLVM_NODISCARD bool empty() const
Definition: DenseMap.h:97
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::WebAssemblyInstrInfo
Definition: WebAssemblyInstrInfo.h:38
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:521
DELEGATE
#define DELEGATE(CLASS_TO_VISIT)
Definition: InstVisitor.h:28
llvm::MachineFunction::getTarget
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
Definition: MachineFunction.h:551
llvm::MachineBasicBlock::removeSuccessor
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:781
getCopyOpcode
static unsigned getCopyOpcode(const TargetRegisterClass *RC)
Definition: WebAssemblyCFGStackify.cpp:784
llvm::ISD::BR
@ BR
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:922
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
WasmEHFuncInfo.h
WebAssemblySubtarget.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::size
unsigned size() const
Definition: DenseMap.h:100
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::MCAsmInfo::getExceptionHandlingType
ExceptionHandling getExceptionHandlingType() const
Definition: MCAsmInfo.h:672
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
MachineInstrBuilder.h
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:329
llvm::WebAssembly::BlockType
BlockType
Used as immediate MachineOperands for block signatures.
Definition: WebAssemblyMCTargetDesc.h:133
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
appendEndToFunction
static void appendEndToFunction(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
Definition: WebAssemblyCFGStackify.cpp:1544
llvm::MachineInstrBundleIterator< MachineInstr >
WebAssemblyExceptionInfo.h
This file implements WebAssemblyException information analysis.
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:311
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::MachineFunction::RenumberBlocks
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
Definition: MachineFunction.cpp:294
MachineDominators.h
llvm::SmallPtrSetImpl::insert
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::WebAssembly::SortRegionInfo
Definition: WebAssemblySortRegion.h:61