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