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 validation 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  // Validation 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 validation 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  // Validation 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, ...
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  case WebAssembly::DELEGATE:
1527  EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1528  continue;
1529  default:
1530  // Something other than an `end`. We're done for this BB.
1531  return;
1532  }
1533  }
1534  // We've reached the beginning of a BB. Continue the search in the previous
1535  // BB.
1536  Worklist.push_back(MBB->getPrevNode()->rbegin());
1537  };
1538 
1539  while (!Worklist.empty())
1540  Process(Worklist.pop_back_val());
1541 }
1542 
1543 // WebAssembly functions end with an end instruction, as if the function body
1544 // were a block.
1546  const WebAssemblyInstrInfo &TII) {
1547  BuildMI(MF.back(), MF.back().end(),
1548  MF.back().findPrevDebugLoc(MF.back().end()),
1549  TII.get(WebAssembly::END_FUNCTION));
1550 }
1551 
1552 /// Insert LOOP/TRY/BLOCK markers at appropriate places.
1553 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
1554  // We allocate one more than the number of blocks in the function to
1555  // accommodate for the possible fake block we may insert at the end.
1556  ScopeTops.resize(MF.getNumBlockIDs() + 1);
1557  // Place the LOOP for MBB if MBB is the header of a loop.
1558  for (auto &MBB : MF)
1559  placeLoopMarker(MBB);
1560 
1561  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1562  for (auto &MBB : MF) {
1563  if (MBB.isEHPad()) {
1564  // Place the TRY for MBB if MBB is the EH pad of an exception.
1566  MF.getFunction().hasPersonalityFn())
1567  placeTryMarker(MBB);
1568  } else {
1569  // Place the BLOCK for MBB if MBB is branched to from above.
1570  placeBlockMarker(MBB);
1571  }
1572  }
1573  // Fix mismatches in unwind destinations induced by linearizing the code.
1575  MF.getFunction().hasPersonalityFn()) {
1576  bool Changed = fixCallUnwindMismatches(MF);
1577  Changed |= fixCatchUnwindMismatches(MF);
1578  if (Changed)
1579  recalculateScopeTops(MF);
1580  }
1581 }
1582 
1583 unsigned WebAssemblyCFGStackify::getBranchDepth(
1584  const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
1585  unsigned Depth = 0;
1586  for (auto X : reverse(Stack)) {
1587  if (X.first == MBB)
1588  break;
1589  ++Depth;
1590  }
1591  assert(Depth < Stack.size() && "Branch destination should be in scope");
1592  return Depth;
1593 }
1594 
1595 unsigned WebAssemblyCFGStackify::getDelegateDepth(
1596  const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
1597  if (MBB == FakeCallerBB)
1598  return Stack.size();
1599  // Delegate's destination is either a catch or a another delegate BB. When the
1600  // destination is another delegate, we can compute the argument in the same
1601  // way as branches, because the target delegate BB only contains the single
1602  // delegate instruction.
1603  if (!MBB->isEHPad()) // Target is a delegate BB
1604  return getBranchDepth(Stack, MBB);
1605 
1606  // When the delegate's destination is a catch BB, we need to use its
1607  // corresponding try's end_try BB because Stack contains each marker's end BB.
1608  // Also we need to check if the end marker instruction matches, because a
1609  // single BB can contain multiple end markers, like this:
1610  // bb:
1611  // END_BLOCK
1612  // END_TRY
1613  // END_BLOCK
1614  // END_TRY
1615  // ...
1616  //
1617  // In case of branches getting the immediate that targets any of these is
1618  // fine, but delegate has to exactly target the correct try.
1619  unsigned Depth = 0;
1620  const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];
1621  for (auto X : reverse(Stack)) {
1622  if (X.first == EndTry->getParent() && X.second == EndTry)
1623  break;
1624  ++Depth;
1625  }
1626  assert(Depth < Stack.size() && "Delegate destination should be in scope");
1627  return Depth;
1628 }
1629 
1630 unsigned WebAssemblyCFGStackify::getRethrowDepth(
1631  const SmallVectorImpl<EndMarkerInfo> &Stack,
1632  const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack) {
1633  unsigned Depth = 0;
1634  // In our current implementation, rethrows always rethrow the exception caught
1635  // by the innermost enclosing catch. This means while traversing Stack in the
1636  // reverse direction, when we encounter END_TRY, we should check if the
1637  // END_TRY corresponds to the current innermost EH pad. For example:
1638  // try
1639  // ...
1640  // catch ;; (a)
1641  // try
1642  // rethrow 1 ;; (b)
1643  // catch ;; (c)
1644  // rethrow 0 ;; (d)
1645  // end ;; (e)
1646  // end ;; (f)
1647  //
1648  // When we are at 'rethrow' (d), while reversely traversing Stack the first
1649  // 'end' we encounter is the 'end' (e), which corresponds to the 'catch' (c).
1650  // And 'rethrow' (d) rethrows the exception caught by 'catch' (c), so we stop
1651  // there and the depth should be 0. But when we are at 'rethrow' (b), it
1652  // rethrows the exception caught by 'catch' (a), so when traversing Stack
1653  // reversely, we should skip the 'end' (e) and choose 'end' (f), which
1654  // corresponds to 'catch' (a).
1655  for (auto X : reverse(Stack)) {
1656  const MachineInstr *End = X.second;
1657  if (End->getOpcode() == WebAssembly::END_TRY) {
1658  auto *EHPad = TryToEHPad[EndToBegin[End]];
1659  if (EHPadStack.back() == EHPad)
1660  break;
1661  }
1662  ++Depth;
1663  }
1664  assert(Depth < Stack.size() && "Rethrow destination should be in scope");
1665  return Depth;
1666 }
1667 
1668 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
1669  // Now rewrite references to basic blocks to be depth immediates.
1672  for (auto &MBB : reverse(MF)) {
1673  for (MachineInstr &MI : llvm::reverse(MBB)) {
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:84
WebAssemblySortRegion.h
This file implements regions used in CFGSort and CFGStackify.
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
llvm::MachineInstrBuilder::addImm
const MachineInstrBuilder & addImm(int64_t Val) const
Add a new immediate operand.
Definition: MachineInstrBuilder.h:131
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
Reg
unsigned Reg
Definition: MachineSink.cpp:1558
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:389
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:818
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:409
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:830
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:761
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:1375
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:359
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:835
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:750
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:828
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:644
llvm::Triple::isOSBinFormatELF
bool isOSBinFormatELF() const
Tests whether the OS uses the ELF binary format.
Definition: Triple.h:635
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:732
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:821
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:775
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
llvm::AMDGPUISD::LOOP
@ LOOP
Definition: AMDGPUISelLowering.h:359
llvm::MachineFunction::getWasmEHFuncInfo
const WasmEHFuncInfo * getWasmEHFuncInfo() const
getWasmEHFuncInfo - Return information about how the current function uses Wasm exception handling.
Definition: MachineFunction.h:672
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:1393
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:634
llvm::MachineFunction::push_back
void push_back(MachineBasicBlock *MBB)
Definition: MachineFunction.h:833
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::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:593
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:415
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:542
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:234
llvm::TargetMachine::getMCAsmInfo
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
Definition: TargetMachine.h:208
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:422
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: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:950
llvm::MachineBasicBlock::hasEHPadSuccessor
bool hasEHPadSuccessor() const
Definition: MachineBasicBlock.cpp:282
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:1414
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:870
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:286
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:908
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:600
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:630
llvm::MachineBasicBlock::removeSuccessor
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:788
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:46
appendEndToFunction
static void appendEndToFunction(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
Definition: WebAssemblyCFGStackify.cpp:1545
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:313
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:295
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