LLVM  16.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 // When MBB is split into MBB and Split, we should unstackify defs in MBB that
785 // have their uses in Split.
787  MachineBasicBlock &Split) {
788  MachineFunction &MF = *MBB.getParent();
789  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
790  auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
791  auto &MRI = MF.getRegInfo();
792 
793  for (auto &MI : Split) {
794  for (auto &MO : MI.explicit_uses()) {
795  if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg()))
796  continue;
797  if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg()))
798  if (Def->getParent() == &MBB)
799  MFI.unstackifyVReg(MO.getReg());
800  }
801  }
802 
803  // In RegStackify, when a register definition is used multiple times,
804  // Reg = INST ...
805  // INST ..., Reg, ...
806  // INST ..., Reg, ...
807  // INST ..., Reg, ...
808  //
809  // we introduce a TEE, which has the following form:
810  // DefReg = INST ...
811  // TeeReg, Reg = TEE_... DefReg
812  // INST ..., TeeReg, ...
813  // INST ..., Reg, ...
814  // INST ..., Reg, ...
815  // with DefReg and TeeReg stackified but Reg not stackified.
816  //
817  // But the invariant that TeeReg should be stackified can be violated while we
818  // unstackify registers in the split BB above. In this case, we convert TEEs
819  // into two COPYs. This COPY will be eventually eliminated in ExplicitLocals.
820  // DefReg = INST ...
821  // TeeReg = COPY DefReg
822  // Reg = COPY DefReg
823  // INST ..., TeeReg, ...
824  // INST ..., Reg, ...
825  // INST ..., Reg, ...
827  if (!WebAssembly::isTee(MI.getOpcode()))
828  continue;
829  Register TeeReg = MI.getOperand(0).getReg();
830  Register Reg = MI.getOperand(1).getReg();
831  Register DefReg = MI.getOperand(2).getReg();
832  if (!MFI.isVRegStackified(TeeReg)) {
833  // Now we are not using TEE anymore, so unstackify DefReg too
834  MFI.unstackifyVReg(DefReg);
835  unsigned CopyOpc =
837  BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), TeeReg)
838  .addReg(DefReg);
839  BuildMI(MBB, &MI, MI.getDebugLoc(), TII.get(CopyOpc), Reg).addReg(DefReg);
840  MI.eraseFromParent();
841  }
842  }
843 }
844 
845 // Wrap the given range of instruction with try-delegate. RangeBegin and
846 // RangeEnd are inclusive.
847 void WebAssemblyCFGStackify::addTryDelegate(MachineInstr *RangeBegin,
848  MachineInstr *RangeEnd,
849  MachineBasicBlock *DelegateDest) {
850  auto *BeginBB = RangeBegin->getParent();
851  auto *EndBB = RangeEnd->getParent();
852  MachineFunction &MF = *BeginBB->getParent();
853  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
854  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
855 
856  // Local expression tree before the first call of this range should go
857  // after the nested TRY.
859  AfterSet.insert(RangeBegin);
860  for (auto I = MachineBasicBlock::iterator(RangeBegin), E = BeginBB->begin();
861  I != E; --I) {
862  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
863  continue;
864  if (WebAssembly::isChild(*std::prev(I), MFI))
865  AfterSet.insert(&*std::prev(I));
866  else
867  break;
868  }
869 
870  // Create the nested try instruction.
871  auto TryPos = getLatestInsertPos(
872  BeginBB, SmallPtrSet<const MachineInstr *, 4>(), AfterSet);
873  MachineInstr *Try = BuildMI(*BeginBB, TryPos, RangeBegin->getDebugLoc(),
874  TII.get(WebAssembly::TRY))
876 
877  // Create a BB to insert the 'delegate' instruction.
878  MachineBasicBlock *DelegateBB = MF.CreateMachineBasicBlock();
879  // If the destination of 'delegate' is not the caller, adds the destination to
880  // the BB's successors.
881  if (DelegateDest != FakeCallerBB)
882  DelegateBB->addSuccessor(DelegateDest);
883 
884  auto SplitPos = std::next(RangeEnd->getIterator());
885  if (SplitPos == EndBB->end()) {
886  // If the range's end instruction is at the end of the BB, insert the new
887  // delegate BB after the current BB.
888  MF.insert(std::next(EndBB->getIterator()), DelegateBB);
889  EndBB->addSuccessor(DelegateBB);
890 
891  } else {
892  // When the split pos is in the middle of a BB, we split the BB into two and
893  // put the 'delegate' BB in between. We normally create a split BB and make
894  // it a successor of the original BB (PostSplit == true), but in case the BB
895  // is an EH pad and the split pos is before 'catch', we should preserve the
896  // BB's property, including that it is an EH pad, in the later part of the
897  // BB, where 'catch' is. In this case we set PostSplit to false.
898  bool PostSplit = true;
899  if (EndBB->isEHPad()) {
900  for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
901  I != E; ++I) {
902  if (WebAssembly::isCatch(I->getOpcode())) {
903  PostSplit = false;
904  break;
905  }
906  }
907  }
908 
909  MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
910  if (PostSplit) {
911  // If the range's end instruction is in the middle of the BB, we split the
912  // BB into two and insert the delegate BB in between.
913  // - Before:
914  // bb:
915  // range_end
916  // other_insts
917  //
918  // - After:
919  // pre_bb: (previous 'bb')
920  // range_end
921  // delegate_bb: (new)
922  // delegate
923  // post_bb: (new)
924  // other_insts
925  PreBB = EndBB;
926  PostBB = MF.CreateMachineBasicBlock();
927  MF.insert(std::next(PreBB->getIterator()), PostBB);
928  MF.insert(std::next(PreBB->getIterator()), DelegateBB);
929  PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
930  PostBB->transferSuccessors(PreBB);
931  } else {
932  // - Before:
933  // ehpad:
934  // range_end
935  // catch
936  // ...
937  //
938  // - After:
939  // pre_bb: (new)
940  // range_end
941  // delegate_bb: (new)
942  // delegate
943  // post_bb: (previous 'ehpad')
944  // catch
945  // ...
946  assert(EndBB->isEHPad());
947  PreBB = MF.CreateMachineBasicBlock();
948  PostBB = EndBB;
949  MF.insert(PostBB->getIterator(), PreBB);
950  MF.insert(PostBB->getIterator(), DelegateBB);
951  PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
952  // We don't need to transfer predecessors of the EH pad to 'PreBB',
953  // because an EH pad's predecessors are all through unwind edges and they
954  // should still unwind to the EH pad, not PreBB.
955  }
956  unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);
957  PreBB->addSuccessor(DelegateBB);
958  PreBB->addSuccessor(PostBB);
959  }
960 
961  // Add 'delegate' instruction in the delegate BB created above.
962  MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(),
964  .addMBB(DelegateDest);
965  registerTryScope(Try, Delegate, nullptr);
966 }
967 
968 bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {
969  // Linearizing the control flow by placing TRY / END_TRY markers can create
970  // mismatches in unwind destinations for throwing instructions, such as calls.
971  //
972  // We use the 'delegate' instruction to fix the unwind mismatches. 'delegate'
973  // instruction delegates an exception to an outer 'catch'. It can target not
974  // only 'catch' but all block-like structures including another 'delegate',
975  // but with slightly different semantics than branches. When it targets a
976  // 'catch', it will delegate the exception to that catch. It is being
977  // discussed how to define the semantics when 'delegate''s target is a non-try
978  // block: it will either be a validation failure or it will target the next
979  // outer try-catch. But anyway our LLVM backend currently does not generate
980  // such code. The example below illustrates where the 'delegate' instruction
981  // in the middle will delegate the exception to, depending on the value of N.
982  // try
983  // try
984  // block
985  // try
986  // try
987  // call @foo
988  // delegate N ;; Where will this delegate to?
989  // catch ;; N == 0
990  // end
991  // end ;; N == 1 (invalid; will not be generated)
992  // delegate ;; N == 2
993  // catch ;; N == 3
994  // end
995  // ;; N == 4 (to caller)
996 
997  // 1. When an instruction may throw, but the EH pad it will unwind to can be
998  // different from the original CFG.
999  //
1000  // Example: we have the following CFG:
1001  // bb0:
1002  // call @foo ; if it throws, unwind to bb2
1003  // bb1:
1004  // call @bar ; if it throws, unwind to bb3
1005  // bb2 (ehpad):
1006  // catch
1007  // ...
1008  // bb3 (ehpad)
1009  // catch
1010  // ...
1011  //
1012  // And the CFG is sorted in this order. Then after placing TRY markers, it
1013  // will look like: (BB markers are omitted)
1014  // try
1015  // try
1016  // call @foo
1017  // call @bar ;; if it throws, unwind to bb3
1018  // catch ;; ehpad (bb2)
1019  // ...
1020  // end_try
1021  // catch ;; ehpad (bb3)
1022  // ...
1023  // end_try
1024  //
1025  // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it
1026  // is supposed to end up. We solve this problem by wrapping the mismatching
1027  // call with an inner try-delegate that rethrows the exception to the right
1028  // 'catch'.
1029  //
1030  // try
1031  // try
1032  // call @foo
1033  // try ;; (new)
1034  // call @bar
1035  // delegate 1 (bb3) ;; (new)
1036  // catch ;; ehpad (bb2)
1037  // ...
1038  // end_try
1039  // catch ;; ehpad (bb3)
1040  // ...
1041  // end_try
1042  //
1043  // ---
1044  // 2. The same as 1, but in this case an instruction unwinds to a caller
1045  // function and not another EH pad.
1046  //
1047  // Example: we have the following CFG:
1048  // bb0:
1049  // call @foo ; if it throws, unwind to bb2
1050  // bb1:
1051  // call @bar ; if it throws, unwind to caller
1052  // bb2 (ehpad):
1053  // catch
1054  // ...
1055  //
1056  // And the CFG is sorted in this order. Then after placing TRY markers, it
1057  // will look like:
1058  // try
1059  // call @foo
1060  // call @bar ;; if it throws, unwind to caller
1061  // catch ;; ehpad (bb2)
1062  // ...
1063  // end_try
1064  //
1065  // Now if bar() throws, it is going to end up ip in bb2, when it is supposed
1066  // throw up to the caller. We solve this problem in the same way, but in this
1067  // case 'delegate's immediate argument is the number of block depths + 1,
1068  // which means it rethrows to the caller.
1069  // try
1070  // call @foo
1071  // try ;; (new)
1072  // call @bar
1073  // delegate 1 (caller) ;; (new)
1074  // catch ;; ehpad (bb2)
1075  // ...
1076  // end_try
1077  //
1078  // Before rewriteDepthImmediates, delegate's argument is a BB. In case of the
1079  // caller, it will take a fake BB generated by getFakeCallerBlock(), which
1080  // will be converted to a correct immediate argument later.
1081  //
1082  // In case there are multiple calls in a BB that may throw to the caller, they
1083  // can be wrapped together in one nested try-delegate scope. (In 1, this
1084  // couldn't happen, because may-throwing instruction there had an unwind
1085  // destination, i.e., it was an invoke before, and there could be only one
1086  // invoke within a BB.)
1087 
1089  // Range of intructions to be wrapped in a new nested try/catch. A range
1090  // exists in a single BB and does not span multiple BBs.
1091  using TryRange = std::pair<MachineInstr *, MachineInstr *>;
1092  // In original CFG, <unwind destination BB, a vector of try ranges>
1094 
1095  // Gather possibly throwing calls (i.e., previously invokes) whose current
1096  // unwind destination is not the same as the original CFG. (Case 1)
1097 
1098  for (auto &MBB : reverse(MF)) {
1099  bool SeenThrowableInstInBB = false;
1100  for (auto &MI : reverse(MBB)) {
1101  if (MI.getOpcode() == WebAssembly::TRY)
1102  EHPadStack.pop_back();
1103  else if (WebAssembly::isCatch(MI.getOpcode()))
1104  EHPadStack.push_back(MI.getParent());
1105 
1106  // In this loop we only gather calls that have an EH pad to unwind. So
1107  // there will be at most 1 such call (= invoke) in a BB, so after we've
1108  // seen one, we can skip the rest of BB. Also if MBB has no EH pad
1109  // successor or MI does not throw, this is not an invoke.
1110  if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
1112  continue;
1113  SeenThrowableInstInBB = true;
1114 
1115  // If the EH pad on the stack top is where this instruction should unwind
1116  // next, we're good.
1117  MachineBasicBlock *UnwindDest = getFakeCallerBlock(MF);
1118  for (auto *Succ : MBB.successors()) {
1119  // Even though semantically a BB can have multiple successors in case an
1120  // exception is not caught by a catchpad, in our backend implementation
1121  // it is guaranteed that a BB can have at most one EH pad successor. For
1122  // details, refer to comments in findWasmUnwindDestinations function in
1123  // SelectionDAGBuilder.cpp.
1124  if (Succ->isEHPad()) {
1125  UnwindDest = Succ;
1126  break;
1127  }
1128  }
1129  if (EHPadStack.back() == UnwindDest)
1130  continue;
1131 
1132  // Include EH_LABELs in the range before and afer the invoke
1133  MachineInstr *RangeBegin = &MI, *RangeEnd = &MI;
1134  if (RangeBegin->getIterator() != MBB.begin() &&
1135  std::prev(RangeBegin->getIterator())->isEHLabel())
1136  RangeBegin = &*std::prev(RangeBegin->getIterator());
1137  if (std::next(RangeEnd->getIterator()) != MBB.end() &&
1138  std::next(RangeEnd->getIterator())->isEHLabel())
1139  RangeEnd = &*std::next(RangeEnd->getIterator());
1140 
1141  // If not, record the range.
1142  UnwindDestToTryRanges[UnwindDest].push_back(
1143  TryRange(RangeBegin, RangeEnd));
1144  LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = " << MBB.getName()
1145  << "\nCall = " << MI
1146  << "\nOriginal dest = " << UnwindDest->getName()
1147  << " Current dest = " << EHPadStack.back()->getName()
1148  << "\n\n");
1149  }
1150  }
1151 
1152  assert(EHPadStack.empty());
1153 
1154  // Gather possibly throwing calls that are supposed to unwind up to the caller
1155  // if they throw, but currently unwind to an incorrect destination. Unlike the
1156  // loop above, there can be multiple calls within a BB that unwind to the
1157  // caller, which we should group together in a range. (Case 2)
1158 
1159  MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
1160 
1161  // Record the range.
1162  auto RecordCallerMismatchRange = [&](const MachineBasicBlock *CurrentDest) {
1163  UnwindDestToTryRanges[getFakeCallerBlock(MF)].push_back(
1164  TryRange(RangeBegin, RangeEnd));
1165  LLVM_DEBUG(dbgs() << "- Call unwind mismatch: MBB = "
1166  << RangeBegin->getParent()->getName()
1167  << "\nRange begin = " << *RangeBegin
1168  << "Range end = " << *RangeEnd
1169  << "\nOriginal dest = caller Current dest = "
1170  << CurrentDest->getName() << "\n\n");
1171  RangeBegin = RangeEnd = nullptr; // Reset range pointers
1172  };
1173 
1174  for (auto &MBB : reverse(MF)) {
1175  bool SeenThrowableInstInBB = false;
1176  for (auto &MI : reverse(MBB)) {
1177  bool MayThrow = WebAssembly::mayThrow(MI);
1178 
1179  // If MBB has an EH pad successor and this is the last instruction that
1180  // may throw, this instruction unwinds to the EH pad and not to the
1181  // caller.
1182  if (MBB.hasEHPadSuccessor() && MayThrow && !SeenThrowableInstInBB)
1183  SeenThrowableInstInBB = true;
1184 
1185  // We wrap up the current range when we see a marker even if we haven't
1186  // finished a BB.
1187  else if (RangeEnd && WebAssembly::isMarker(MI.getOpcode()))
1188  RecordCallerMismatchRange(EHPadStack.back());
1189 
1190  // If EHPadStack is empty, that means it correctly unwinds to the caller
1191  // if it throws, so we're good. If MI does not throw, we're good too.
1192  else if (EHPadStack.empty() || !MayThrow) {
1193  }
1194 
1195  // We found an instruction that unwinds to the caller but currently has an
1196  // incorrect unwind destination. Create a new range or increment the
1197  // currently existing range.
1198  else {
1199  if (!RangeEnd)
1200  RangeBegin = RangeEnd = &MI;
1201  else
1202  RangeBegin = &MI;
1203  }
1204 
1205  // Update EHPadStack.
1206  if (MI.getOpcode() == WebAssembly::TRY)
1207  EHPadStack.pop_back();
1208  else if (WebAssembly::isCatch(MI.getOpcode()))
1209  EHPadStack.push_back(MI.getParent());
1210  }
1211 
1212  if (RangeEnd)
1213  RecordCallerMismatchRange(EHPadStack.back());
1214  }
1215 
1216  assert(EHPadStack.empty());
1217 
1218  // We don't have any unwind destination mismatches to resolve.
1219  if (UnwindDestToTryRanges.empty())
1220  return false;
1221 
1222  // Now we fix the mismatches by wrapping calls with inner try-delegates.
1223  for (auto &P : UnwindDestToTryRanges) {
1224  NumCallUnwindMismatches += P.second.size();
1225  MachineBasicBlock *UnwindDest = P.first;
1226  auto &TryRanges = P.second;
1227 
1228  for (auto Range : TryRanges) {
1229  MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1230  std::tie(RangeBegin, RangeEnd) = Range;
1231  auto *MBB = RangeBegin->getParent();
1232 
1233  // If this BB has an EH pad successor, i.e., ends with an 'invoke', now we
1234  // are going to wrap the invoke with try-delegate, making the 'delegate'
1235  // BB the new successor instead, so remove the EH pad succesor here. The
1236  // BB may not have an EH pad successor if calls in this BB throw to the
1237  // caller.
1238  MachineBasicBlock *EHPad = nullptr;
1239  for (auto *Succ : MBB->successors()) {
1240  if (Succ->isEHPad()) {
1241  EHPad = Succ;
1242  break;
1243  }
1244  }
1245  if (EHPad)
1246  MBB->removeSuccessor(EHPad);
1247 
1248  addTryDelegate(RangeBegin, RangeEnd, UnwindDest);
1249  }
1250  }
1251 
1252  return true;
1253 }
1254 
1255 bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {
1256  // There is another kind of unwind destination mismatches besides call unwind
1257  // mismatches, which we will call "catch unwind mismatches". See this example
1258  // after the marker placement:
1259  // try
1260  // try
1261  // call @foo
1262  // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
1263  // ...
1264  // end_try
1265  // catch_all ;; ehpad B
1266  // ...
1267  // end_try
1268  //
1269  // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
1270  // throws a foreign exception that is not caught by ehpad A, and its next
1271  // destination should be the caller. But after control flow linearization,
1272  // another EH pad can be placed in between (e.g. ehpad B here), making the
1273  // next unwind destination incorrect. In this case, the foreign exception
1274  // will instead go to ehpad B and will be caught there instead. In this
1275  // example the correct next unwind destination is the caller, but it can be
1276  // another outer catch in other cases.
1277  //
1278  // There is no specific 'call' or 'throw' instruction to wrap with a
1279  // try-delegate, so we wrap the whole try-catch-end with a try-delegate and
1280  // make it rethrow to the right destination, as in the example below:
1281  // try
1282  // try ;; (new)
1283  // try
1284  // call @foo
1285  // catch __cpp_exception ;; ehpad A (next unwind dest: caller)
1286  // ...
1287  // end_try
1288  // delegate 1 (caller) ;; (new)
1289  // catch_all ;; ehpad B
1290  // ...
1291  // end_try
1292 
1293  const auto *EHInfo = MF.getWasmEHFuncInfo();
1295  // For EH pads that have catch unwind mismatches, a map of <EH pad, its
1296  // correct unwind destination>.
1298 
1299  for (auto &MBB : reverse(MF)) {
1300  for (auto &MI : reverse(MBB)) {
1301  if (MI.getOpcode() == WebAssembly::TRY)
1302  EHPadStack.pop_back();
1303  else if (MI.getOpcode() == WebAssembly::DELEGATE)
1304  EHPadStack.push_back(&MBB);
1305  else if (WebAssembly::isCatch(MI.getOpcode())) {
1306  auto *EHPad = &MBB;
1307 
1308  // catch_all always catches an exception, so we don't need to do
1309  // anything
1310  if (MI.getOpcode() == WebAssembly::CATCH_ALL) {
1311  }
1312 
1313  // This can happen when the unwind dest was removed during the
1314  // optimization, e.g. because it was unreachable.
1315  else if (EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
1316  LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName()
1317  << "'s unwind destination does not exist anymore"
1318  << "\n\n");
1319  }
1320 
1321  // The EHPad's next unwind destination is the caller, but we incorrectly
1322  // unwind to another EH pad.
1323  else if (!EHPadStack.empty() && !EHInfo->hasUnwindDest(EHPad)) {
1324  EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
1325  LLVM_DEBUG(dbgs()
1326  << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()
1327  << " Original dest = caller Current dest = "
1328  << EHPadStack.back()->getName() << "\n\n");
1329  }
1330 
1331  // The EHPad's next unwind destination is an EH pad, whereas we
1332  // incorrectly unwind to another EH pad.
1333  else if (!EHPadStack.empty() && EHInfo->hasUnwindDest(EHPad)) {
1334  auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
1335  if (EHPadStack.back() != UnwindDest) {
1336  EHPadToUnwindDest[EHPad] = UnwindDest;
1337  LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "
1338  << EHPad->getName() << " Original dest = "
1339  << UnwindDest->getName() << " Current dest = "
1340  << EHPadStack.back()->getName() << "\n\n");
1341  }
1342  }
1343 
1344  EHPadStack.push_back(EHPad);
1345  }
1346  }
1347  }
1348 
1349  assert(EHPadStack.empty());
1350  if (EHPadToUnwindDest.empty())
1351  return false;
1352  NumCatchUnwindMismatches += EHPadToUnwindDest.size();
1354 
1355  for (auto &P : EHPadToUnwindDest) {
1356  MachineBasicBlock *EHPad = P.first;
1357  MachineBasicBlock *UnwindDest = P.second;
1358  MachineInstr *Try = EHPadToTry[EHPad];
1359  MachineInstr *EndTry = BeginToEnd[Try];
1360  addTryDelegate(Try, EndTry, UnwindDest);
1361  NewEndTryBBs.insert(EndTry->getParent());
1362  }
1363 
1364  // Adding a try-delegate wrapping an existing try-catch-end can make existing
1365  // branch destination BBs invalid. For example,
1366  //
1367  // - Before:
1368  // bb0:
1369  // block
1370  // br bb3
1371  // bb1:
1372  // try
1373  // ...
1374  // bb2: (ehpad)
1375  // catch
1376  // bb3:
1377  // end_try
1378  // end_block ;; 'br bb3' targets here
1379  //
1380  // Suppose this try-catch-end has a catch unwind mismatch, so we need to wrap
1381  // this with a try-delegate. Then this becomes:
1382  //
1383  // - After:
1384  // bb0:
1385  // block
1386  // br bb3 ;; invalid destination!
1387  // bb1:
1388  // try ;; (new instruction)
1389  // try
1390  // ...
1391  // bb2: (ehpad)
1392  // catch
1393  // bb3:
1394  // end_try ;; 'br bb3' still incorrectly targets here!
1395  // delegate_bb: ;; (new BB)
1396  // delegate ;; (new instruction)
1397  // split_bb: ;; (new BB)
1398  // end_block
1399  //
1400  // Now 'br bb3' incorrectly branches to an inner scope.
1401  //
1402  // As we can see in this case, when branches target a BB that has both
1403  // 'end_try' and 'end_block' and the BB is split to insert a 'delegate', we
1404  // have to remap existing branch destinations so that they target not the
1405  // 'end_try' BB but the new 'end_block' BB. There can be multiple 'delegate's
1406  // in between, so we try to find the next BB with 'end_block' instruction. In
1407  // this example, the 'br bb3' instruction should be remapped to 'br split_bb'.
1408  for (auto &MBB : MF) {
1409  for (auto &MI : MBB) {
1410  if (MI.isTerminator()) {
1411  for (auto &MO : MI.operands()) {
1412  if (MO.isMBB() && NewEndTryBBs.count(MO.getMBB())) {
1413  auto *BrDest = MO.getMBB();
1414  bool FoundEndBlock = false;
1415  for (; std::next(BrDest->getIterator()) != MF.end();
1416  BrDest = BrDest->getNextNode()) {
1417  for (const auto &MI : *BrDest) {
1418  if (MI.getOpcode() == WebAssembly::END_BLOCK) {
1419  FoundEndBlock = true;
1420  break;
1421  }
1422  }
1423  if (FoundEndBlock)
1424  break;
1425  }
1426  assert(FoundEndBlock);
1427  MO.setMBB(BrDest);
1428  }
1429  }
1430  }
1431  }
1432  }
1433 
1434  return true;
1435 }
1436 
1437 void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {
1438  // Renumber BBs and recalculate ScopeTop info because new BBs might have been
1439  // created and inserted during fixing unwind mismatches.
1440  MF.RenumberBlocks();
1441  ScopeTops.clear();
1442  ScopeTops.resize(MF.getNumBlockIDs());
1443  for (auto &MBB : reverse(MF)) {
1444  for (auto &MI : reverse(MBB)) {
1445  if (ScopeTops[MBB.getNumber()])
1446  break;
1447  switch (MI.getOpcode()) {
1449  case WebAssembly::END_LOOP:
1450  case WebAssembly::END_TRY:
1451  case WebAssembly::DELEGATE:
1452  updateScopeTops(EndToBegin[&MI]->getParent(), &MBB);
1453  break;
1454  case WebAssembly::CATCH:
1455  case WebAssembly::CATCH_ALL:
1456  updateScopeTops(EHPadToTry[&MBB]->getParent(), &MBB);
1457  break;
1458  }
1459  }
1460  }
1461 }
1462 
1463 /// In normal assembly languages, when the end of a function is unreachable,
1464 /// because the function ends in an infinite loop or a noreturn call or similar,
1465 /// it isn't necessary to worry about the function return type at the end of
1466 /// the function, because it's never reached. However, in WebAssembly, blocks
1467 /// that end at the function end need to have a return type signature that
1468 /// matches the function signature, even though it's unreachable. This function
1469 /// checks for such cases and fixes up the signatures.
1470 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
1471  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1472 
1473  if (MFI.getResults().empty())
1474  return;
1475 
1476  // MCInstLower will add the proper types to multivalue signatures based on the
1477  // function return type
1478  WebAssembly::BlockType RetType =
1479  MFI.getResults().size() > 1
1482  WebAssembly::toValType(MFI.getResults().front()));
1483 
1485  Worklist.push_back(MF.rbegin()->rbegin());
1486 
1488  auto *MBB = It->getParent();
1489  while (It != MBB->rend()) {
1490  MachineInstr &MI = *It++;
1491  if (MI.isPosition() || MI.isDebugInstr())
1492  continue;
1493  switch (MI.getOpcode()) {
1494  case WebAssembly::END_TRY: {
1495  // If a 'try''s return type is fixed, both its try body and catch body
1496  // should satisfy the return type, so we need to search 'end'
1497  // instructions before its corresponding 'catch' too.
1498  auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]);
1499  assert(EHPad);
1500  auto NextIt =
1501  std::next(WebAssembly::findCatch(EHPad)->getReverseIterator());
1502  if (NextIt != EHPad->rend())
1503  Worklist.push_back(NextIt);
1504  [[fallthrough]];
1505  }
1507  case WebAssembly::END_LOOP:
1508  case WebAssembly::DELEGATE:
1509  EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1510  continue;
1511  default:
1512  // Something other than an `end`. We're done for this BB.
1513  return;
1514  }
1515  }
1516  // We've reached the beginning of a BB. Continue the search in the previous
1517  // BB.
1518  Worklist.push_back(MBB->getPrevNode()->rbegin());
1519  };
1520 
1521  while (!Worklist.empty())
1522  Process(Worklist.pop_back_val());
1523 }
1524 
1525 // WebAssembly functions end with an end instruction, as if the function body
1526 // were a block.
1528  const WebAssemblyInstrInfo &TII) {
1529  BuildMI(MF.back(), MF.back().end(),
1530  MF.back().findPrevDebugLoc(MF.back().end()),
1531  TII.get(WebAssembly::END_FUNCTION));
1532 }
1533 
1534 /// Insert LOOP/TRY/BLOCK markers at appropriate places.
1535 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
1536  // We allocate one more than the number of blocks in the function to
1537  // accommodate for the possible fake block we may insert at the end.
1538  ScopeTops.resize(MF.getNumBlockIDs() + 1);
1539  // Place the LOOP for MBB if MBB is the header of a loop.
1540  for (auto &MBB : MF)
1541  placeLoopMarker(MBB);
1542 
1543  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1544  for (auto &MBB : MF) {
1545  if (MBB.isEHPad()) {
1546  // Place the TRY for MBB if MBB is the EH pad of an exception.
1548  MF.getFunction().hasPersonalityFn())
1549  placeTryMarker(MBB);
1550  } else {
1551  // Place the BLOCK for MBB if MBB is branched to from above.
1552  placeBlockMarker(MBB);
1553  }
1554  }
1555  // Fix mismatches in unwind destinations induced by linearizing the code.
1557  MF.getFunction().hasPersonalityFn()) {
1558  bool Changed = fixCallUnwindMismatches(MF);
1559  Changed |= fixCatchUnwindMismatches(MF);
1560  if (Changed)
1561  recalculateScopeTops(MF);
1562  }
1563 }
1564 
1565 unsigned WebAssemblyCFGStackify::getBranchDepth(
1566  const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
1567  unsigned Depth = 0;
1568  for (auto X : reverse(Stack)) {
1569  if (X.first == MBB)
1570  break;
1571  ++Depth;
1572  }
1573  assert(Depth < Stack.size() && "Branch destination should be in scope");
1574  return Depth;
1575 }
1576 
1577 unsigned WebAssemblyCFGStackify::getDelegateDepth(
1578  const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) {
1579  if (MBB == FakeCallerBB)
1580  return Stack.size();
1581  // Delegate's destination is either a catch or a another delegate BB. When the
1582  // destination is another delegate, we can compute the argument in the same
1583  // way as branches, because the target delegate BB only contains the single
1584  // delegate instruction.
1585  if (!MBB->isEHPad()) // Target is a delegate BB
1586  return getBranchDepth(Stack, MBB);
1587 
1588  // When the delegate's destination is a catch BB, we need to use its
1589  // corresponding try's end_try BB because Stack contains each marker's end BB.
1590  // Also we need to check if the end marker instruction matches, because a
1591  // single BB can contain multiple end markers, like this:
1592  // bb:
1593  // END_BLOCK
1594  // END_TRY
1595  // END_BLOCK
1596  // END_TRY
1597  // ...
1598  //
1599  // In case of branches getting the immediate that targets any of these is
1600  // fine, but delegate has to exactly target the correct try.
1601  unsigned Depth = 0;
1602  const MachineInstr *EndTry = BeginToEnd[EHPadToTry[MBB]];
1603  for (auto X : reverse(Stack)) {
1604  if (X.first == EndTry->getParent() && X.second == EndTry)
1605  break;
1606  ++Depth;
1607  }
1608  assert(Depth < Stack.size() && "Delegate destination should be in scope");
1609  return Depth;
1610 }
1611 
1612 unsigned WebAssemblyCFGStackify::getRethrowDepth(
1613  const SmallVectorImpl<EndMarkerInfo> &Stack,
1614  const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack) {
1615  unsigned Depth = 0;
1616  // In our current implementation, rethrows always rethrow the exception caught
1617  // by the innermost enclosing catch. This means while traversing Stack in the
1618  // reverse direction, when we encounter END_TRY, we should check if the
1619  // END_TRY corresponds to the current innermost EH pad. For example:
1620  // try
1621  // ...
1622  // catch ;; (a)
1623  // try
1624  // rethrow 1 ;; (b)
1625  // catch ;; (c)
1626  // rethrow 0 ;; (d)
1627  // end ;; (e)
1628  // end ;; (f)
1629  //
1630  // When we are at 'rethrow' (d), while reversely traversing Stack the first
1631  // 'end' we encounter is the 'end' (e), which corresponds to the 'catch' (c).
1632  // And 'rethrow' (d) rethrows the exception caught by 'catch' (c), so we stop
1633  // there and the depth should be 0. But when we are at 'rethrow' (b), it
1634  // rethrows the exception caught by 'catch' (a), so when traversing Stack
1635  // reversely, we should skip the 'end' (e) and choose 'end' (f), which
1636  // corresponds to 'catch' (a).
1637  for (auto X : reverse(Stack)) {
1638  const MachineInstr *End = X.second;
1639  if (End->getOpcode() == WebAssembly::END_TRY) {
1640  auto *EHPad = TryToEHPad[EndToBegin[End]];
1641  if (EHPadStack.back() == EHPad)
1642  break;
1643  }
1644  ++Depth;
1645  }
1646  assert(Depth < Stack.size() && "Rethrow destination should be in scope");
1647  return Depth;
1648 }
1649 
1650 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
1651  // Now rewrite references to basic blocks to be depth immediates.
1654  for (auto &MBB : reverse(MF)) {
1655  for (MachineInstr &MI : llvm::reverse(MBB)) {
1656  switch (MI.getOpcode()) {
1657  case WebAssembly::BLOCK:
1658  case WebAssembly::TRY:
1659  assert(ScopeTops[Stack.back().first->getNumber()]->getNumber() <=
1660  MBB.getNumber() &&
1661  "Block/try marker should be balanced");
1662  Stack.pop_back();
1663  break;
1664 
1665  case WebAssembly::LOOP:
1666  assert(Stack.back().first == &MBB && "Loop top should be balanced");
1667  Stack.pop_back();
1668  break;
1669 
1671  Stack.push_back(std::make_pair(&MBB, &MI));
1672  break;
1673 
1674  case WebAssembly::END_TRY: {
1675  // We handle DELEGATE in the default level, because DELEGATE has
1676  // immediate operands to rewrite.
1677  Stack.push_back(std::make_pair(&MBB, &MI));
1678  auto *EHPad = TryToEHPad[EndToBegin[&MI]];
1679  EHPadStack.push_back(EHPad);
1680  break;
1681  }
1682 
1683  case WebAssembly::END_LOOP:
1684  Stack.push_back(std::make_pair(EndToBegin[&MI]->getParent(), &MI));
1685  break;
1686 
1687  case WebAssembly::CATCH:
1688  case WebAssembly::CATCH_ALL:
1689  EHPadStack.pop_back();
1690  break;
1691 
1692  case WebAssembly::RETHROW:
1693  MI.getOperand(0).setImm(getRethrowDepth(Stack, EHPadStack));
1694  break;
1695 
1696  default:
1697  if (MI.isTerminator()) {
1698  // Rewrite MBB operands to be depth immediates.
1699  SmallVector<MachineOperand, 4> Ops(MI.operands());
1700  while (MI.getNumOperands() > 0)
1701  MI.removeOperand(MI.getNumOperands() - 1);
1702  for (auto MO : Ops) {
1703  if (MO.isMBB()) {
1704  if (MI.getOpcode() == WebAssembly::DELEGATE)
1706  getDelegateDepth(Stack, MO.getMBB()));
1707  else
1709  getBranchDepth(Stack, MO.getMBB()));
1710  }
1711  MI.addOperand(MF, MO);
1712  }
1713  }
1714 
1715  if (MI.getOpcode() == WebAssembly::DELEGATE)
1716  Stack.push_back(std::make_pair(&MBB, &MI));
1717  break;
1718  }
1719  }
1720  }
1721  assert(Stack.empty() && "Control flow should be balanced");
1722 }
1723 
1724 void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) {
1725  if (FakeCallerBB)
1726  MF.deleteMachineBasicBlock(FakeCallerBB);
1727  AppendixBB = FakeCallerBB = nullptr;
1728 }
1729 
1730 void WebAssemblyCFGStackify::releaseMemory() {
1731  ScopeTops.clear();
1732  BeginToEnd.clear();
1733  EndToBegin.clear();
1734  TryToEHPad.clear();
1735  EHPadToTry.clear();
1736 }
1737 
1738 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
1739  LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
1740  "********** Function: "
1741  << MF.getName() << '\n');
1742  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1743 
1744  releaseMemory();
1745 
1746  // Liveness is not tracked for VALUE_STACK physreg.
1748 
1749  // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
1750  placeMarkers(MF);
1751 
1752  // Remove unnecessary instructions possibly introduced by try/end_trys.
1755  removeUnnecessaryInstrs(MF);
1756 
1757  // Convert MBB operands in terminators to relative depth immediates.
1758  rewriteDepthImmediates(MF);
1759 
1760  // Fix up block/loop/try signatures at the end of the function to conform to
1761  // WebAssembly's rules.
1762  fixEndsAtEndOfFunction(MF);
1763 
1764  // Add an end instruction at the end of the function body.
1765  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1767  .getTargetTriple()
1768  .isOSBinFormatELF())
1769  appendEndToFunction(MF, TII);
1770 
1771  cleanupFunctionData(MF);
1772 
1773  MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
1774  return true;
1775 }
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:53
llvm::WebAssemblySubtarget::getTargetTriple
const Triple & getTargetTriple() const
Definition: WebAssemblySubtarget.h:85
WebAssemblySortRegion.h
This file implements regions used in CFGSort and CFGStackify.
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
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: AddressRanges.h:18
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
WebAssembly.h
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::WebAssembly::isCatch
bool isCatch(unsigned Opc)
Definition: WebAssemblyMCTargetDesc.h:407
llvm::WebAssembly::findCatch
MachineInstr * findCatch(MachineBasicBlock *EHPad)
Find a catch instruction from an EH pad.
Definition: WebAssemblyUtilities.cpp:170
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
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:433
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:329
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:856
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
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:407
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:64
llvm::MachineFunction::back
const MachineBasicBlock & back() const
Definition: MachineFunction.h:868
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:799
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:1388
DEBUG_TYPE
#define DEBUG_TYPE
Definition: WebAssemblyCFGStackify.cpp:41
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
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:873
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:450
llvm::WebAssembly::isMarker
bool isMarker(unsigned Opc)
Definition: WebAssemblyMCTargetDesc.h:387
llvm::MachineBasicBlock::terminators
iterator_range< iterator > terminators()
Definition: MachineBasicBlock.h:325
llvm::WebAssemblyException
Definition: WebAssemblyExceptionInfo.h:41
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
llvm::WebAssembly::BlockType::Void
@ Void
llvm::sys::Process
A collection of legacy interfaces for querying information about the current executing process.
Definition: Process.h:43
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:762
llvm::MachineFunction::front
const MachineBasicBlock & front() const
Definition: MachineFunction.h:866
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
llvm::Triple::isOSBinFormatELF
bool isOSBinFormatELF() const
Tests whether the OS uses the ELF binary format.
Definition: Triple.h:673
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:782
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineOperand::getImm
int64_t getImm() const
Definition: MachineOperand.h:546
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:755
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
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::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::bitc::END_BLOCK
@ END_BLOCK
Definition: BitCodeEnums.h:45
TBB
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
Definition: RISCVRedundantCopyElimination.cpp:76
llvm::WebAssembly::toValType
wasm::ValType toValType(MVT Type)
Definition: WebAssemblyTypeUtilities.cpp:125
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineFunction::deleteMachineBasicBlock
void deleteMachineBasicBlock(MachineBasicBlock *MBB)
DeleteMachineBasicBlock - Delete the given MachineBasicBlock.
Definition: MachineFunction.cpp:445
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:48
llvm::MachineFunction::rbegin
reverse_iterator rbegin()
Definition: MachineFunction.h:859
WebAssemblyTypeUtilities.h
llvm::MachineBasicBlock::rend
reverse_iterator rend()
Definition: MachineBasicBlock.h:315
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:759
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:642
llvm::AMDGPUISD::LOOP
@ LOOP
Definition: AMDGPUISelLowering.h:363
llvm::MachineFunction::getWasmEHFuncInfo
const WasmEHFuncInfo * getWasmEHFuncInfo() const
getWasmEHFuncInfo - Return information about how the current function uses Wasm exception handling.
Definition: MachineFunction.h:695
llvm::WebAssembly::getCopyOpcodeForRegClass
unsigned getCopyOpcodeForRegClass(const TargetRegisterClass *RC)
Returns the appropriate copy opcode for the given register class.
Definition: WebAssemblyUtilities.cpp:183
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
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:1406
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::MachineFunction::push_back
void push_back(MachineBasicBlock *MBB)
Definition: MachineFunction.h:871
llvm::MachineInstr::getDebugLoc
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:445
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
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:110
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::DenseMap
Definition: DenseMap.h:714
llvm::WebAssemblyExceptionInfo
Definition: WebAssemblyExceptionInfo.h:122
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:716
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:439
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:567
llvm::ilist_node_with_parent::getPrevNode
NodeTy * getPrevNode()
Definition: ilist_node.h:275
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:261
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:386
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::empty
bool empty() const
Definition: DenseMap.h:98
llvm::MachineBasicBlock::pred_empty
bool pred_empty() const
Definition: MachineBasicBlock.h:368
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:383
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:257
llvm::TargetMachine::getMCAsmInfo
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
Definition: TargetMachine.h:205
llvm::WebAssemblyFunctionInfo::getResults
const std::vector< MVT > & getResults() const
Definition: WebAssemblyMachineFunctionInfo.h:83
llvm::SmallPtrSetImplBase::clear
void clear()
Definition: SmallPtrSet.h:95
llvm::MachineBasicBlock::iterator
MachineInstrBundleIterator< MachineInstr > iterator
Definition: MachineBasicBlock.h:269
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1115
MCAsmInfo.h
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
llvm::logicalview::LVAttributeKind::Range
@ Range
llvm::MachineBasicBlock::isEHPad
bool isEHPad() const
Returns true if the block is a landing pad.
Definition: MachineBasicBlock.h:576
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::MachineBasicBlock::rbegin
reverse_iterator rbegin()
Definition: MachineBasicBlock.h:309
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:1009
llvm::MachineBasicBlock::hasEHPadSuccessor
bool hasEHPadSuccessor() const
Definition: MachineBasicBlock.cpp:280
llvm::MachineInstr::getOpcode
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:516
llvm::MachineBasicBlock::findBranchDebugLoc
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
Definition: MachineBasicBlock.cpp:1427
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:804
llvm::MachineRegisterInfo::invalidateLiveness
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
Definition: MachineRegisterInfo.h:205
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
unstackifyVRegsUsedInSplitBB
static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, MachineBasicBlock &Split)
Definition: WebAssemblyCFGStackify.cpp:786
llvm::WebAssemblySubtarget
Definition: WebAssemblySubtarget.h:35
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
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:920
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:623
DELEGATE
#define DELEGATE(CLASS_TO_VISIT)
Definition: InstVisitor.h:27
llvm::MachineFunction::getTarget
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
Definition: MachineFunction.h:653
llvm::MachineBasicBlock::removeSuccessor
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:800
llvm::ISD::BR
@ BR
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:982
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:105
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:99
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::MCAsmInfo::getExceptionHandlingType
ExceptionHandling getExceptionHandlingType() const
Definition: MCAsmInfo.h:777
llvm::BuildMI
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
Definition: MachineInstrBuilder.h:357
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
MachineInstrBuilder.h
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::WebAssembly::BlockType
BlockType
Used as immediate MachineOperands for block signatures.
Definition: WebAssemblyTypeUtilities.h:31
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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:51
appendEndToFunction
static void appendEndToFunction(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
Definition: WebAssemblyCFGStackify.cpp:1527
llvm::MachineInstrBundleIterator< MachineInstr >
WebAssemblyExceptionInfo.h
This file implements WebAssemblyException information analysis.
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:311
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
llvm::MachineFunction::RenumberBlocks
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
Definition: MachineFunction.cpp:319
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:365
llvm::WebAssembly::SortRegionInfo
Definition: WebAssemblySortRegion.h:61