LLVM  10.0.0svn
WebAssemblyCFGStackify.cpp
Go to the documentation of this file.
1 //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file implements a CFG stacking pass.
11 ///
12 /// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes,
13 /// since scope boundaries serve as the labels for WebAssembly's control
14 /// transfers.
15 ///
16 /// This is sufficient to convert arbitrary CFGs into a form that works on
17 /// WebAssembly, provided that all loops are single-entry.
18 ///
19 /// In case we use exceptions, this pass also fixes mismatches in unwind
20 /// destinations created during transforming CFG into wasm structured format.
21 ///
22 //===----------------------------------------------------------------------===//
23 
24 #include "WebAssembly.h"
27 #include "WebAssemblySubtarget.h"
28 #include "WebAssemblyUtilities.h"
29 #include "llvm/ADT/Statistic.h"
32 #include "llvm/MC/MCAsmInfo.h"
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "wasm-cfg-stackify"
36 
37 STATISTIC(NumUnwindMismatches, "Number of EH pad unwind mismatches found");
38 
39 namespace {
40 class WebAssemblyCFGStackify final : public MachineFunctionPass {
41  StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
42 
43  void getAnalysisUsage(AnalysisUsage &AU) const override {
48  }
49 
50  bool runOnMachineFunction(MachineFunction &MF) override;
51 
52  // For each block whose label represents the end of a scope, record the block
53  // which holds the beginning of the scope. This will allow us to quickly skip
54  // over scoped regions when walking blocks.
56 
57  // Placing markers.
58  void placeMarkers(MachineFunction &MF);
59  void placeBlockMarker(MachineBasicBlock &MBB);
60  void placeLoopMarker(MachineBasicBlock &MBB);
61  void placeTryMarker(MachineBasicBlock &MBB);
62  void removeUnnecessaryInstrs(MachineFunction &MF);
63  bool fixUnwindMismatches(MachineFunction &MF);
64  void rewriteDepthImmediates(MachineFunction &MF);
65  void fixEndsAtEndOfFunction(MachineFunction &MF);
66 
67  // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY).
69  // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY.
71  // <TRY marker, EH pad> map
73  // <EH pad, TRY marker> map
75 
76  // There can be an appendix block at the end of each function, shared for:
77  // - creating a correct signature for fallthrough returns
78  // - target for rethrows that need to unwind to the caller, but are trapped
79  // inside another try/catch
80  MachineBasicBlock *AppendixBB = nullptr;
81  MachineBasicBlock *getAppendixBlock(MachineFunction &MF) {
82  if (!AppendixBB) {
83  AppendixBB = MF.CreateMachineBasicBlock();
84  // Give it a fake predecessor so that AsmPrinter prints its label.
85  AppendixBB->addSuccessor(AppendixBB);
86  MF.push_back(AppendixBB);
87  }
88  return AppendixBB;
89  }
90 
91  // Helper functions to register / unregister scope information created by
92  // marker instructions.
93  void registerScope(MachineInstr *Begin, MachineInstr *End);
94  void registerTryScope(MachineInstr *Begin, MachineInstr *End,
95  MachineBasicBlock *EHPad);
96  void unregisterScope(MachineInstr *Begin);
97 
98 public:
99  static char ID; // Pass identification, replacement for typeid
100  WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
101  ~WebAssemblyCFGStackify() override { releaseMemory(); }
102  void releaseMemory() override;
103 };
104 } // end anonymous namespace
105 
107 INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,
108  "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false,
109  false)
110 
112  return new WebAssemblyCFGStackify();
113 }
114 
115 /// Test whether Pred has any terminators explicitly branching to MBB, as
116 /// opposed to falling through. Note that it's possible (eg. in unoptimized
117 /// code) for a branch instruction to both branch to a block and fallthrough
118 /// to it, so we check the actual branch operands to see if there are any
119 /// explicit mentions.
121  MachineBasicBlock *MBB) {
122  for (MachineInstr &MI : Pred->terminators())
123  for (MachineOperand &MO : MI.explicit_operands())
124  if (MO.isMBB() && MO.getMBB() == MBB)
125  return true;
126  return false;
127 }
128 
129 // Returns an iterator to the earliest position possible within the MBB,
130 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
131 // contains instructions that should go before the marker, and AfterSet contains
132 // ones that should go after the marker. In this function, AfterSet is only
133 // used for sanity checking.
136  const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
137  const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
138  auto InsertPos = MBB->end();
139  while (InsertPos != MBB->begin()) {
140  if (BeforeSet.count(&*std::prev(InsertPos))) {
141 #ifndef NDEBUG
142  // Sanity check
143  for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
144  assert(!AfterSet.count(&*std::prev(Pos)));
145 #endif
146  break;
147  }
148  --InsertPos;
149  }
150  return InsertPos;
151 }
152 
153 // Returns an iterator to the latest position possible within the MBB,
154 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
155 // contains instructions that should go before the marker, and AfterSet contains
156 // ones that should go after the marker. In this function, BeforeSet is only
157 // used for sanity checking.
160  const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
161  const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
162  auto InsertPos = MBB->begin();
163  while (InsertPos != MBB->end()) {
164  if (AfterSet.count(&*InsertPos)) {
165 #ifndef NDEBUG
166  // Sanity check
167  for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
168  assert(!BeforeSet.count(&*Pos));
169 #endif
170  break;
171  }
172  ++InsertPos;
173  }
174  return InsertPos;
175 }
176 
177 void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
178  MachineInstr *End) {
179  BeginToEnd[Begin] = End;
180  EndToBegin[End] = Begin;
181 }
182 
183 void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
184  MachineInstr *End,
185  MachineBasicBlock *EHPad) {
186  registerScope(Begin, End);
187  TryToEHPad[Begin] = EHPad;
188  EHPadToTry[EHPad] = Begin;
189 }
190 
191 void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
192  assert(BeginToEnd.count(Begin));
193  MachineInstr *End = BeginToEnd[Begin];
194  assert(EndToBegin.count(End));
195  BeginToEnd.erase(Begin);
196  EndToBegin.erase(End);
197  MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
198  if (EHPad) {
199  assert(EHPadToTry.count(EHPad));
200  TryToEHPad.erase(Begin);
201  EHPadToTry.erase(EHPad);
202  }
203 }
204 
205 /// Insert a BLOCK marker for branches to MBB (if needed).
206 // TODO Consider a more generalized way of handling block (and also loop and
207 // try) signatures when we implement the multi-value proposal later.
208 void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
209  assert(!MBB.isEHPad());
210  MachineFunction &MF = *MBB.getParent();
211  auto &MDT = getAnalysis<MachineDominatorTree>();
212  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
213  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
214 
215  // First compute the nearest common dominator of all forward non-fallthrough
216  // predecessors so that we minimize the time that the BLOCK is on the stack,
217  // which reduces overall stack height.
218  MachineBasicBlock *Header = nullptr;
219  bool IsBranchedTo = false;
220  bool IsBrOnExn = false;
221  MachineInstr *BrOnExn = nullptr;
222  int MBBNumber = MBB.getNumber();
223  for (MachineBasicBlock *Pred : MBB.predecessors()) {
224  if (Pred->getNumber() < MBBNumber) {
225  Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
226  if (explicitlyBranchesTo(Pred, &MBB)) {
227  IsBranchedTo = true;
228  if (Pred->getFirstTerminator()->getOpcode() == WebAssembly::BR_ON_EXN) {
229  IsBrOnExn = true;
230  assert(!BrOnExn && "There should be only one br_on_exn per block");
231  BrOnExn = &*Pred->getFirstTerminator();
232  }
233  }
234  }
235  }
236  if (!Header)
237  return;
238  if (!IsBranchedTo)
239  return;
240 
241  assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
242  MachineBasicBlock *LayoutPred = MBB.getPrevNode();
243 
244  // If the nearest common dominator is inside a more deeply nested context,
245  // walk out to the nearest scope which isn't more deeply nested.
246  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
247  if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
248  if (ScopeTop->getNumber() > Header->getNumber()) {
249  // Skip over an intervening scope.
250  I = std::next(ScopeTop->getIterator());
251  } else {
252  // We found a scope level at an appropriate depth.
253  Header = ScopeTop;
254  break;
255  }
256  }
257  }
258 
259  // Decide where in Header to put the BLOCK.
260 
261  // Instructions that should go before the BLOCK.
263  // Instructions that should go after the BLOCK.
265  for (const auto &MI : *Header) {
266  // If there is a previously placed LOOP marker and the bottom block of the
267  // loop is above MBB, it should be after the BLOCK, because the loop is
268  // nested in this BLOCK. Otherwise it should be before the BLOCK.
269  if (MI.getOpcode() == WebAssembly::LOOP) {
270  auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
271  if (MBB.getNumber() > LoopBottom->getNumber())
272  AfterSet.insert(&MI);
273 #ifndef NDEBUG
274  else
275  BeforeSet.insert(&MI);
276 #endif
277  }
278 
279  // All previously inserted BLOCK/TRY markers should be after the BLOCK
280  // because they are all nested blocks.
281  if (MI.getOpcode() == WebAssembly::BLOCK ||
282  MI.getOpcode() == WebAssembly::TRY)
283  AfterSet.insert(&MI);
284 
285 #ifndef NDEBUG
286  // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK.
287  if (MI.getOpcode() == WebAssembly::END_BLOCK ||
288  MI.getOpcode() == WebAssembly::END_LOOP ||
289  MI.getOpcode() == WebAssembly::END_TRY)
290  BeforeSet.insert(&MI);
291 #endif
292 
293  // Terminators should go after the BLOCK.
294  if (MI.isTerminator())
295  AfterSet.insert(&MI);
296  }
297 
298  // Local expression tree should go after the BLOCK.
299  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
300  --I) {
301  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
302  continue;
303  if (WebAssembly::isChild(*std::prev(I), MFI))
304  AfterSet.insert(&*std::prev(I));
305  else
306  break;
307  }
308 
309  // Add the BLOCK.
310 
311  // 'br_on_exn' extracts exnref object and pushes variable number of values
312  // depending on its tag. For C++ exception, its a single i32 value, and the
313  // generated code will be in the form of:
314  // block i32
315  // br_on_exn 0, $__cpp_exception
316  // rethrow
317  // end_block
319  if (IsBrOnExn) {
320  const char *TagName = BrOnExn->getOperand(1).getSymbolName();
321  if (std::strcmp(TagName, "__cpp_exception") != 0)
322  llvm_unreachable("Only C++ exception is supported");
323  ReturnType = WebAssembly::BlockType::I32;
324  }
325 
326  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
327  MachineInstr *Begin =
328  BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
329  TII.get(WebAssembly::BLOCK))
330  .addImm(int64_t(ReturnType));
331 
332  // Decide where in Header to put the END_BLOCK.
333  BeforeSet.clear();
334  AfterSet.clear();
335  for (auto &MI : MBB) {
336 #ifndef NDEBUG
337  // END_BLOCK should precede existing LOOP and TRY markers.
338  if (MI.getOpcode() == WebAssembly::LOOP ||
339  MI.getOpcode() == WebAssembly::TRY)
340  AfterSet.insert(&MI);
341 #endif
342 
343  // If there is a previously placed END_LOOP marker and the header of the
344  // loop is above this block's header, the END_LOOP should be placed after
345  // the BLOCK, because the loop contains this block. Otherwise the END_LOOP
346  // should be placed before the BLOCK. The same for END_TRY.
347  if (MI.getOpcode() == WebAssembly::END_LOOP ||
348  MI.getOpcode() == WebAssembly::END_TRY) {
349  if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
350  BeforeSet.insert(&MI);
351 #ifndef NDEBUG
352  else
353  AfterSet.insert(&MI);
354 #endif
355  }
356  }
357 
358  // Mark the end of the block.
359  InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
360  MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
361  TII.get(WebAssembly::END_BLOCK));
362  registerScope(Begin, End);
363 
364  // Track the farthest-spanning scope that ends at this point.
365  int Number = MBB.getNumber();
366  if (!ScopeTops[Number] ||
367  ScopeTops[Number]->getNumber() > Header->getNumber())
368  ScopeTops[Number] = Header;
369 }
370 
371 /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
372 void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
373  MachineFunction &MF = *MBB.getParent();
374  const auto &MLI = getAnalysis<MachineLoopInfo>();
375  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
376 
377  MachineLoop *Loop = MLI.getLoopFor(&MBB);
378  if (!Loop || Loop->getHeader() != &MBB)
379  return;
380 
381  // The operand of a LOOP is the first block after the loop. If the loop is the
382  // bottom of the function, insert a dummy block at the end.
384  auto Iter = std::next(Bottom->getIterator());
385  if (Iter == MF.end()) {
386  getAppendixBlock(MF);
387  Iter = std::next(Bottom->getIterator());
388  }
389  MachineBasicBlock *AfterLoop = &*Iter;
390 
391  // Decide where in Header to put the LOOP.
394  for (const auto &MI : MBB) {
395  // LOOP marker should be after any existing loop that ends here. Otherwise
396  // we assume the instruction belongs to the loop.
397  if (MI.getOpcode() == WebAssembly::END_LOOP)
398  BeforeSet.insert(&MI);
399 #ifndef NDEBUG
400  else
401  AfterSet.insert(&MI);
402 #endif
403  }
404 
405  // Mark the beginning of the loop.
406  auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
407  MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),
408  TII.get(WebAssembly::LOOP))
409  .addImm(int64_t(WebAssembly::BlockType::Void));
410 
411  // Decide where in Header to put the END_LOOP.
412  BeforeSet.clear();
413  AfterSet.clear();
414 #ifndef NDEBUG
415  for (const auto &MI : MBB)
416  // Existing END_LOOP markers belong to parent loops of this loop
417  if (MI.getOpcode() == WebAssembly::END_LOOP)
418  AfterSet.insert(&MI);
419 #endif
420 
421  // Mark the end of the loop (using arbitrary debug location that branched to
422  // the loop end as its location).
423  InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet);
424  DebugLoc EndDL = AfterLoop->pred_empty()
425  ? DebugLoc()
426  : (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
427  MachineInstr *End =
428  BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP));
429  registerScope(Begin, End);
430 
431  assert((!ScopeTops[AfterLoop->getNumber()] ||
432  ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
433  "With block sorting the outermost loop for a block should be first.");
434  if (!ScopeTops[AfterLoop->getNumber()])
435  ScopeTops[AfterLoop->getNumber()] = &MBB;
436 }
437 
438 void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
439  assert(MBB.isEHPad());
440  MachineFunction &MF = *MBB.getParent();
441  auto &MDT = getAnalysis<MachineDominatorTree>();
442  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
443  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
444  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
445 
446  // Compute the nearest common dominator of all unwind predecessors
447  MachineBasicBlock *Header = nullptr;
448  int MBBNumber = MBB.getNumber();
449  for (auto *Pred : MBB.predecessors()) {
450  if (Pred->getNumber() < MBBNumber) {
451  Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
452  assert(!explicitlyBranchesTo(Pred, &MBB) &&
453  "Explicit branch to an EH pad!");
454  }
455  }
456  if (!Header)
457  return;
458 
459  // If this try is at the bottom of the function, insert a dummy block at the
460  // end.
461  WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
462  assert(WE);
464 
465  auto Iter = std::next(Bottom->getIterator());
466  if (Iter == MF.end()) {
467  getAppendixBlock(MF);
468  Iter = std::next(Bottom->getIterator());
469  }
470  MachineBasicBlock *Cont = &*Iter;
471 
472  assert(Cont != &MF.front());
473  MachineBasicBlock *LayoutPred = Cont->getPrevNode();
474 
475  // If the nearest common dominator is inside a more deeply nested context,
476  // walk out to the nearest scope which isn't more deeply nested.
477  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
478  if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
479  if (ScopeTop->getNumber() > Header->getNumber()) {
480  // Skip over an intervening scope.
481  I = std::next(ScopeTop->getIterator());
482  } else {
483  // We found a scope level at an appropriate depth.
484  Header = ScopeTop;
485  break;
486  }
487  }
488  }
489 
490  // Decide where in Header to put the TRY.
491 
492  // Instructions that should go before the TRY.
494  // Instructions that should go after the TRY.
496  for (const auto &MI : *Header) {
497  // If there is a previously placed LOOP marker and the bottom block of the
498  // loop is above MBB, it should be after the TRY, because the loop is nested
499  // in this TRY. Otherwise it should be before the TRY.
500  if (MI.getOpcode() == WebAssembly::LOOP) {
501  auto *LoopBottom = BeginToEnd[&MI]->getParent()->getPrevNode();
502  if (MBB.getNumber() > LoopBottom->getNumber())
503  AfterSet.insert(&MI);
504 #ifndef NDEBUG
505  else
506  BeforeSet.insert(&MI);
507 #endif
508  }
509 
510  // All previously inserted BLOCK/TRY markers should be after the TRY because
511  // they are all nested trys.
512  if (MI.getOpcode() == WebAssembly::BLOCK ||
513  MI.getOpcode() == WebAssembly::TRY)
514  AfterSet.insert(&MI);
515 
516 #ifndef NDEBUG
517  // All END_(BLOCK/LOOP/TRY) markers should be before the TRY.
518  if (MI.getOpcode() == WebAssembly::END_BLOCK ||
519  MI.getOpcode() == WebAssembly::END_LOOP ||
520  MI.getOpcode() == WebAssembly::END_TRY)
521  BeforeSet.insert(&MI);
522 #endif
523 
524  // Terminators should go after the TRY.
525  if (MI.isTerminator())
526  AfterSet.insert(&MI);
527  }
528 
529  // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
530  // contain the call within it. So the call should go after the TRY. The
531  // exception is when the header's terminator is a rethrow instruction, in
532  // which case that instruction, not a call instruction before it, is gonna
533  // throw.
534  MachineInstr *ThrowingCall = nullptr;
535  if (MBB.isPredecessor(Header)) {
536  auto TermPos = Header->getFirstTerminator();
537  if (TermPos == Header->end() ||
538  TermPos->getOpcode() != WebAssembly::RETHROW) {
539  for (auto &MI : reverse(*Header)) {
540  if (MI.isCall()) {
541  AfterSet.insert(&MI);
542  ThrowingCall = &MI;
543  // Possibly throwing calls are usually wrapped by EH_LABEL
544  // instructions. We don't want to split them and the call.
545  if (MI.getIterator() != Header->begin() &&
546  std::prev(MI.getIterator())->isEHLabel()) {
547  AfterSet.insert(&*std::prev(MI.getIterator()));
548  ThrowingCall = &*std::prev(MI.getIterator());
549  }
550  break;
551  }
552  }
553  }
554  }
555 
556  // Local expression tree should go after the TRY.
557  // For BLOCK placement, we start the search from the previous instruction of a
558  // BB's terminator, but in TRY's case, we should start from the previous
559  // instruction of a call that can throw, or a EH_LABEL that precedes the call,
560  // because the return values of the call's previous instructions can be
561  // stackified and consumed by the throwing call.
562  auto SearchStartPt = ThrowingCall ? MachineBasicBlock::iterator(ThrowingCall)
563  : Header->getFirstTerminator();
564  for (auto I = SearchStartPt, E = Header->begin(); I != E; --I) {
565  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
566  continue;
567  if (WebAssembly::isChild(*std::prev(I), MFI))
568  AfterSet.insert(&*std::prev(I));
569  else
570  break;
571  }
572 
573  // Add the TRY.
574  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
575  MachineInstr *Begin =
576  BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
577  TII.get(WebAssembly::TRY))
578  .addImm(int64_t(WebAssembly::BlockType::Void));
579 
580  // Decide where in Header to put the END_TRY.
581  BeforeSet.clear();
582  AfterSet.clear();
583  for (const auto &MI : *Cont) {
584 #ifndef NDEBUG
585  // END_TRY should precede existing LOOP and BLOCK markers.
586  if (MI.getOpcode() == WebAssembly::LOOP ||
587  MI.getOpcode() == WebAssembly::BLOCK)
588  AfterSet.insert(&MI);
589 
590  // All END_TRY markers placed earlier belong to exceptions that contains
591  // this one.
592  if (MI.getOpcode() == WebAssembly::END_TRY)
593  AfterSet.insert(&MI);
594 #endif
595 
596  // If there is a previously placed END_LOOP marker and its header is after
597  // where TRY marker is, this loop is contained within the 'catch' part, so
598  // the END_TRY marker should go after that. Otherwise, the whole try-catch
599  // is contained within this loop, so the END_TRY should go before that.
600  if (MI.getOpcode() == WebAssembly::END_LOOP) {
601  // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they
602  // are in the same BB, LOOP is always before TRY.
603  if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber())
604  BeforeSet.insert(&MI);
605 #ifndef NDEBUG
606  else
607  AfterSet.insert(&MI);
608 #endif
609  }
610 
611  // It is not possible for an END_BLOCK to be already in this block.
612  }
613 
614  // Mark the end of the TRY.
615  InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet);
616  MachineInstr *End =
617  BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(),
618  TII.get(WebAssembly::END_TRY));
619  registerTryScope(Begin, End, &MBB);
620 
621  // Track the farthest-spanning scope that ends at this point. We create two
622  // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB
623  // with 'try'). We need to create 'catch' -> 'try' mapping here too because
624  // markers should not span across 'catch'. For example, this should not
625  // happen:
626  //
627  // try
628  // block --| (X)
629  // catch |
630  // end_block --|
631  // end_try
632  for (int Number : {Cont->getNumber(), MBB.getNumber()}) {
633  if (!ScopeTops[Number] ||
634  ScopeTops[Number]->getNumber() > Header->getNumber())
635  ScopeTops[Number] = Header;
636  }
637 }
638 
639 void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
640  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
641 
642  // When there is an unconditional branch right before a catch instruction and
643  // it branches to the end of end_try marker, we don't need the branch, because
644  // it there is no exception, the control flow transfers to that point anyway.
645  // bb0:
646  // try
647  // ...
648  // br bb2 <- Not necessary
649  // bb1:
650  // catch
651  // ...
652  // bb2:
653  // end
654  for (auto &MBB : MF) {
655  if (!MBB.isEHPad())
656  continue;
657 
658  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
660  MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
661  MachineBasicBlock *Cont = BeginToEnd[EHPadToTry[&MBB]]->getParent();
662  bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
663  if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
664  (!Cond.empty() && FBB && FBB == Cont)))
665  TII.removeBranch(*EHPadLayoutPred);
666  }
667 
668  // When there are block / end_block markers that overlap with try / end_try
669  // markers, and the block and try markers' return types are the same, the
670  // block /end_block markers are not necessary, because try / end_try markers
671  // also can serve as boundaries for branches.
672  // block <- Not necessary
673  // try
674  // ...
675  // catch
676  // ...
677  // end
678  // end <- Not necessary
680  for (auto &MBB : MF) {
681  for (auto &MI : MBB) {
682  if (MI.getOpcode() != WebAssembly::TRY)
683  continue;
684 
685  MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
686  MachineBasicBlock *TryBB = Try->getParent();
687  MachineBasicBlock *Cont = EndTry->getParent();
688  int64_t RetType = Try->getOperand(0).getImm();
689  for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());
690  B != TryBB->begin() && E != Cont->end() &&
691  std::prev(B)->getOpcode() == WebAssembly::BLOCK &&
692  E->getOpcode() == WebAssembly::END_BLOCK &&
693  std::prev(B)->getOperand(0).getImm() == RetType;
694  --B, ++E) {
695  ToDelete.push_back(&*std::prev(B));
696  ToDelete.push_back(&*E);
697  }
698  }
699  }
700  for (auto *MI : ToDelete) {
701  if (MI->getOpcode() == WebAssembly::BLOCK)
702  unregisterScope(MI);
703  MI->eraseFromParent();
704  }
705 }
706 
707 // When MBB is split into MBB and Split, we should unstackify defs in MBB that
708 // have their uses in Split.
710  MachineBasicBlock &Split,
713  for (auto &MI : Split) {
714  for (auto &MO : MI.explicit_uses()) {
715  if (!MO.isReg() || Register::isPhysicalRegister(MO.getReg()))
716  continue;
717  if (MachineInstr *Def = MRI.getUniqueVRegDef(MO.getReg()))
718  if (Def->getParent() == &MBB)
719  MFI.unstackifyVReg(MO.getReg());
720  }
721  }
722 }
723 
724 bool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) {
725  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
726  auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
728 
729  // Linearizing the control flow by placing TRY / END_TRY markers can create
730  // mismatches in unwind destinations. There are two kinds of mismatches we
731  // try to solve here.
732 
733  // 1. When an instruction may throw, but the EH pad it will unwind to can be
734  // different from the original CFG.
735  //
736  // Example: we have the following CFG:
737  // bb0:
738  // call @foo (if it throws, unwind to bb2)
739  // bb1:
740  // call @bar (if it throws, unwind to bb3)
741  // bb2 (ehpad):
742  // catch
743  // ...
744  // bb3 (ehpad)
745  // catch
746  // handler body
747  //
748  // And the CFG is sorted in this order. Then after placing TRY markers, it
749  // will look like: (BB markers are omitted)
750  // try $label1
751  // try
752  // call @foo
753  // call @bar (if it throws, unwind to bb3)
754  // catch <- ehpad (bb2)
755  // ...
756  // end_try
757  // catch <- ehpad (bb3)
758  // handler body
759  // end_try
760  //
761  // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it
762  // is supposed to end up. We solve this problem by
763  // a. Split the target unwind EH pad (here bb3) so that the handler body is
764  // right after 'end_try', which means we extract the handler body out of
765  // the catch block. We do this because this handler body should be
766  // somewhere branch-eable from the inner scope.
767  // b. Wrap the call that has an incorrect unwind destination ('call @bar'
768  // here) with a nested try/catch/end_try scope, and within the new catch
769  // block, branches to the handler body.
770  // c. Place a branch after the newly inserted nested end_try so it can bypass
771  // the handler body, which is now outside of a catch block.
772  //
773  // The result will like as follows. (new: a) means this instruction is newly
774  // created in the process of doing 'a' above.
775  //
776  // block $label0 (new: placeBlockMarker)
777  // try $label1
778  // try
779  // call @foo
780  // try (new: b)
781  // call @bar
782  // catch (new: b)
783  // local.set n / drop (new: b)
784  // br $label1 (new: b)
785  // end_try (new: b)
786  // catch <- ehpad (bb2)
787  // end_try
788  // br $label0 (new: c)
789  // catch <- ehpad (bb3)
790  // end_try (hoisted: a)
791  // handler body
792  // end_block (new: placeBlockMarker)
793  //
794  // Note that the new wrapping block/end_block will be generated later in
795  // placeBlockMarker.
796  //
797  // TODO Currently local.set and local.gets are generated to move exnref value
798  // created by catches. That's because we don't support yielding values from a
799  // block in LLVM machine IR yet, even though it is supported by wasm. Delete
800  // unnecessary local.get/local.sets once yielding values from a block is
801  // supported. The full EH spec requires multi-value support to do this, but
802  // for C++ we don't yet need it because we only throw a single i32.
803  //
804  // ---
805  // 2. The same as 1, but in this case an instruction unwinds to a caller
806  // function and not another EH pad.
807  //
808  // Example: we have the following CFG:
809  // bb0:
810  // call @foo (if it throws, unwind to bb2)
811  // bb1:
812  // call @bar (if it throws, unwind to caller)
813  // bb2 (ehpad):
814  // catch
815  // ...
816  //
817  // And the CFG is sorted in this order. Then after placing TRY markers, it
818  // will look like:
819  // try
820  // call @foo
821  // call @bar (if it throws, unwind to caller)
822  // catch <- ehpad (bb2)
823  // ...
824  // end_try
825  //
826  // Now if bar() throws, it is going to end up ip in bb2, when it is supposed
827  // throw up to the caller.
828  // We solve this problem by
829  // a. Create a new 'appendix' BB at the end of the function and put a single
830  // 'rethrow' instruction (+ local.get) in there.
831  // b. Wrap the call that has an incorrect unwind destination ('call @bar'
832  // here) with a nested try/catch/end_try scope, and within the new catch
833  // block, branches to the new appendix block.
834  //
835  // block $label0 (new: placeBlockMarker)
836  // try
837  // call @foo
838  // try (new: b)
839  // call @bar
840  // catch (new: b)
841  // local.set n (new: b)
842  // br $label0 (new: b)
843  // end_try (new: b)
844  // catch <- ehpad (bb2)
845  // ...
846  // end_try
847  // ...
848  // end_block (new: placeBlockMarker)
849  // local.get n (new: a) <- appendix block
850  // rethrow (new: a)
851  //
852  // In case there are multiple calls in a BB that may throw to the caller, they
853  // can be wrapped together in one nested try scope. (In 1, this couldn't
854  // happen, because may-throwing instruction there had an unwind destination,
855  // i.e., it was an invoke before, and there could be only one invoke within a
856  // BB.)
857 
859  // Range of intructions to be wrapped in a new nested try/catch
860  using TryRange = std::pair<MachineInstr *, MachineInstr *>;
861  // In original CFG, <unwind destination BB, a vector of try ranges>
863  // In new CFG, <destination to branch to, a vector of try ranges>
865  // In new CFG, <destination to branch to, register containing exnref>
867 
868  // Gather possibly throwing calls (i.e., previously invokes) whose current
869  // unwind destination is not the same as the original CFG.
870  for (auto &MBB : reverse(MF)) {
871  bool SeenThrowableInstInBB = false;
872  for (auto &MI : reverse(MBB)) {
873  if (MI.getOpcode() == WebAssembly::TRY)
874  EHPadStack.pop_back();
875  else if (MI.getOpcode() == WebAssembly::CATCH)
876  EHPadStack.push_back(MI.getParent());
877 
878  // In this loop we only gather calls that have an EH pad to unwind. So
879  // there will be at most 1 such call (= invoke) in a BB, so after we've
880  // seen one, we can skip the rest of BB. Also if MBB has no EH pad
881  // successor or MI does not throw, this is not an invoke.
882  if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
884  continue;
885  SeenThrowableInstInBB = true;
886 
887  // If the EH pad on the stack top is where this instruction should unwind
888  // next, we're good.
889  MachineBasicBlock *UnwindDest = nullptr;
890  for (auto *Succ : MBB.successors()) {
891  if (Succ->isEHPad()) {
892  UnwindDest = Succ;
893  break;
894  }
895  }
896  if (EHPadStack.back() == UnwindDest)
897  continue;
898 
899  // If not, record the range.
900  UnwindDestToTryRanges[UnwindDest].push_back(TryRange(&MI, &MI));
901  }
902  }
903 
904  assert(EHPadStack.empty());
905 
906  // Gather possibly throwing calls that are supposed to unwind up to the caller
907  // if they throw, but currently unwind to an incorrect destination. Unlike the
908  // loop above, there can be multiple calls within a BB that unwind to the
909  // caller, which we should group together in a range.
910  bool NeedAppendixBlock = false;
911  for (auto &MBB : reverse(MF)) {
912  MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
913  for (auto &MI : reverse(MBB)) {
914  if (MI.getOpcode() == WebAssembly::TRY)
915  EHPadStack.pop_back();
916  else if (MI.getOpcode() == WebAssembly::CATCH)
917  EHPadStack.push_back(MI.getParent());
918 
919  // If MBB has an EH pad successor, this inst does not unwind to caller.
920  if (MBB.hasEHPadSuccessor())
921  continue;
922 
923  // We wrap up the current range when we see a marker even if we haven't
924  // finished a BB.
925  if (RangeEnd && WebAssembly::isMarker(MI.getOpcode())) {
926  NeedAppendixBlock = true;
927  // Record the range. nullptr here means the unwind destination is the
928  // caller.
929  UnwindDestToTryRanges[nullptr].push_back(
930  TryRange(RangeBegin, RangeEnd));
931  RangeBegin = RangeEnd = nullptr; // Reset range pointers
932  }
933 
934  // If EHPadStack is empty, that means it is correctly unwind to caller if
935  // it throws, so we're good. If MI does not throw, we're good too.
936  if (EHPadStack.empty() || !WebAssembly::mayThrow(MI))
937  continue;
938 
939  // We found an instruction that unwinds to the caller but currently has an
940  // incorrect unwind destination. Create a new range or increment the
941  // currently existing range.
942  if (!RangeEnd)
943  RangeBegin = RangeEnd = &MI;
944  else
945  RangeBegin = &MI;
946  }
947 
948  if (RangeEnd) {
949  NeedAppendixBlock = true;
950  // Record the range. nullptr here means the unwind destination is the
951  // caller.
952  UnwindDestToTryRanges[nullptr].push_back(TryRange(RangeBegin, RangeEnd));
953  RangeBegin = RangeEnd = nullptr; // Reset range pointers
954  }
955  }
956 
957  assert(EHPadStack.empty());
958  // We don't have any unwind destination mismatches to resolve.
959  if (UnwindDestToTryRanges.empty())
960  return false;
961 
962  // If we found instructions that should unwind to the caller but currently
963  // have incorrect unwind destination, we create an appendix block at the end
964  // of the function with a local.get and a rethrow instruction.
965  if (NeedAppendixBlock) {
966  auto *AppendixBB = getAppendixBlock(MF);
967  Register ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);
968  BuildMI(AppendixBB, DebugLoc(), TII.get(WebAssembly::RETHROW))
969  .addReg(ExnReg);
970  // These instruction ranges should branch to this appendix BB.
971  for (auto Range : UnwindDestToTryRanges[nullptr])
972  BrDestToTryRanges[AppendixBB].push_back(Range);
973  BrDestToExnReg[AppendixBB] = ExnReg;
974  }
975 
976  // We loop through unwind destination EH pads that are targeted from some
977  // inner scopes. Because these EH pads are destination of more than one scope
978  // now, we split them so that the handler body is after 'end_try'.
979  // - Before
980  // ehpad:
981  // catch
982  // local.set n / drop
983  // handler body
984  // ...
985  // cont:
986  // end_try
987  //
988  // - After
989  // ehpad:
990  // catch
991  // local.set n / drop
992  // brdest: (new)
993  // end_try (hoisted from 'cont' BB)
994  // handler body (taken from 'ehpad')
995  // ...
996  // cont:
997  for (auto &P : UnwindDestToTryRanges) {
998  NumUnwindMismatches += P.second.size();
999 
1000  // This means the destination is the appendix BB, which was separately
1001  // handled above.
1002  if (!P.first)
1003  continue;
1004 
1005  MachineBasicBlock *EHPad = P.first;
1006 
1007  // Find 'catch' and 'local.set' or 'drop' instruction that follows the
1008  // 'catch'. If -wasm-disable-explicit-locals is not set, 'catch' should be
1009  // always followed by either 'local.set' or a 'drop', because 'br_on_exn' is
1010  // generated after 'catch' in LateEHPrepare and we don't support blocks
1011  // taking values yet.
1012  MachineInstr *Catch = nullptr;
1013  unsigned ExnReg = 0;
1014  for (auto &MI : *EHPad) {
1015  switch (MI.getOpcode()) {
1016  case WebAssembly::CATCH:
1017  Catch = &MI;
1018  ExnReg = Catch->getOperand(0).getReg();
1019  break;
1020  }
1021  }
1022  assert(Catch && "EH pad does not have a catch");
1023  assert(ExnReg != 0 && "Invalid register");
1024 
1025  auto SplitPos = std::next(Catch->getIterator());
1026 
1027  // Create a new BB that's gonna be the destination for branches from the
1028  // inner mismatched scope.
1029  MachineInstr *BeginTry = EHPadToTry[EHPad];
1030  MachineInstr *EndTry = BeginToEnd[BeginTry];
1031  MachineBasicBlock *Cont = EndTry->getParent();
1032  auto *BrDest = MF.CreateMachineBasicBlock();
1033  MF.insert(std::next(EHPad->getIterator()), BrDest);
1034  // Hoist up the existing 'end_try'.
1035  BrDest->insert(BrDest->end(), EndTry->removeFromParent());
1036  // Take out the handler body from EH pad to the new branch destination BB.
1037  BrDest->splice(BrDest->end(), EHPad, SplitPos, EHPad->end());
1038  unstackifyVRegsUsedInSplitBB(*EHPad, *BrDest, MFI, MRI);
1039  // Fix predecessor-successor relationship.
1040  BrDest->transferSuccessors(EHPad);
1041  EHPad->addSuccessor(BrDest);
1042 
1043  // All try ranges that were supposed to unwind to this EH pad now have to
1044  // branch to this new branch dest BB.
1045  for (auto Range : UnwindDestToTryRanges[EHPad])
1046  BrDestToTryRanges[BrDest].push_back(Range);
1047  BrDestToExnReg[BrDest] = ExnReg;
1048 
1049  // In case we fall through to the continuation BB after the catch block, we
1050  // now have to add a branch to it.
1051  // - Before
1052  // try
1053  // ...
1054  // (falls through to 'cont')
1055  // catch
1056  // handler body
1057  // end
1058  // <-- cont
1059  //
1060  // - After
1061  // try
1062  // ...
1063  // br %cont (new)
1064  // catch
1065  // end
1066  // handler body
1067  // <-- cont
1068  MachineBasicBlock *EHPadLayoutPred = &*std::prev(EHPad->getIterator());
1069  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1071  bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
1072  if (Analyzable && !TBB && !FBB) {
1073  DebugLoc DL = EHPadLayoutPred->empty()
1074  ? DebugLoc()
1075  : EHPadLayoutPred->rbegin()->getDebugLoc();
1076  BuildMI(EHPadLayoutPred, DL, TII.get(WebAssembly::BR)).addMBB(Cont);
1077  }
1078  }
1079 
1080  // For possibly throwing calls whose unwind destinations are currently
1081  // incorrect because of CFG linearization, we wrap them with a nested
1082  // try/catch/end_try, and within the new catch block, we branch to the correct
1083  // handler.
1084  // - Before
1085  // mbb:
1086  // call @foo <- Unwind destination mismatch!
1087  // ehpad:
1088  // ...
1089  //
1090  // - After
1091  // mbb:
1092  // try (new)
1093  // call @foo
1094  // nested-ehpad: (new)
1095  // catch (new)
1096  // local.set n / drop (new)
1097  // br %brdest (new)
1098  // nested-end: (new)
1099  // end_try (new)
1100  // ehpad:
1101  // ...
1102  for (auto &P : BrDestToTryRanges) {
1103  MachineBasicBlock *BrDest = P.first;
1104  auto &TryRanges = P.second;
1105  unsigned ExnReg = BrDestToExnReg[BrDest];
1106 
1107  for (auto Range : TryRanges) {
1108  MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1109  std::tie(RangeBegin, RangeEnd) = Range;
1110  auto *MBB = RangeBegin->getParent();
1111 
1112  // Include possible EH_LABELs in the range
1113  if (RangeBegin->getIterator() != MBB->begin() &&
1114  std::prev(RangeBegin->getIterator())->isEHLabel())
1115  RangeBegin = &*std::prev(RangeBegin->getIterator());
1116  if (std::next(RangeEnd->getIterator()) != MBB->end() &&
1117  std::next(RangeEnd->getIterator())->isEHLabel())
1118  RangeEnd = &*std::next(RangeEnd->getIterator());
1119 
1120  MachineBasicBlock *EHPad = nullptr;
1121  for (auto *Succ : MBB->successors()) {
1122  if (Succ->isEHPad()) {
1123  EHPad = Succ;
1124  break;
1125  }
1126  }
1127 
1128  // Create the nested try instruction.
1129  MachineInstr *NestedTry =
1130  BuildMI(*MBB, *RangeBegin, RangeBegin->getDebugLoc(),
1131  TII.get(WebAssembly::TRY))
1132  .addImm(int64_t(WebAssembly::BlockType::Void));
1133 
1134  // Create the nested EH pad and fill instructions in.
1135  MachineBasicBlock *NestedEHPad = MF.CreateMachineBasicBlock();
1136  MF.insert(std::next(MBB->getIterator()), NestedEHPad);
1137  NestedEHPad->setIsEHPad();
1138  NestedEHPad->setIsEHScopeEntry();
1139  BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::CATCH),
1140  ExnReg);
1141  BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::BR))
1142  .addMBB(BrDest);
1143 
1144  // Create the nested continuation BB and end_try instruction.
1145  MachineBasicBlock *NestedCont = MF.CreateMachineBasicBlock();
1146  MF.insert(std::next(NestedEHPad->getIterator()), NestedCont);
1147  MachineInstr *NestedEndTry =
1148  BuildMI(*NestedCont, NestedCont->begin(), RangeEnd->getDebugLoc(),
1149  TII.get(WebAssembly::END_TRY));
1150  // In case MBB has more instructions after the try range, move them to the
1151  // new nested continuation BB.
1152  NestedCont->splice(NestedCont->end(), MBB,
1153  std::next(RangeEnd->getIterator()), MBB->end());
1154  unstackifyVRegsUsedInSplitBB(*MBB, *NestedCont, MFI, MRI);
1155  registerTryScope(NestedTry, NestedEndTry, NestedEHPad);
1156 
1157  // Fix predecessor-successor relationship.
1158  NestedCont->transferSuccessors(MBB);
1159  if (EHPad)
1160  NestedCont->removeSuccessor(EHPad);
1161  MBB->addSuccessor(NestedEHPad);
1162  MBB->addSuccessor(NestedCont);
1163  NestedEHPad->addSuccessor(BrDest);
1164  }
1165  }
1166 
1167  // Renumber BBs and recalculate ScopeTop info because new BBs might have been
1168  // created and inserted above.
1169  MF.RenumberBlocks();
1170  ScopeTops.clear();
1171  ScopeTops.resize(MF.getNumBlockIDs());
1172  for (auto &MBB : reverse(MF)) {
1173  for (auto &MI : reverse(MBB)) {
1174  if (ScopeTops[MBB.getNumber()])
1175  break;
1176  switch (MI.getOpcode()) {
1178  case WebAssembly::END_LOOP:
1179  case WebAssembly::END_TRY:
1180  ScopeTops[MBB.getNumber()] = EndToBegin[&MI]->getParent();
1181  break;
1182  case WebAssembly::CATCH:
1183  ScopeTops[MBB.getNumber()] = EHPadToTry[&MBB]->getParent();
1184  break;
1185  }
1186  }
1187  }
1188 
1189  // Recompute the dominator tree.
1190  getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF);
1191 
1192  // Place block markers for newly added branches.
1194  for (auto &P : BrDestToTryRanges)
1195  BrDests.push_back(P.first);
1196  llvm::sort(BrDests,
1197  [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
1198  auto ANum = A->getNumber();
1199  auto BNum = B->getNumber();
1200  return ANum < BNum;
1201  });
1202  for (auto *Dest : BrDests)
1203  placeBlockMarker(*Dest);
1204 
1205  return true;
1206 }
1207 
1208 static unsigned
1210  const MachineBasicBlock *MBB) {
1211  unsigned Depth = 0;
1212  for (auto X : reverse(Stack)) {
1213  if (X == MBB)
1214  break;
1215  ++Depth;
1216  }
1217  assert(Depth < Stack.size() && "Branch destination should be in scope");
1218  return Depth;
1219 }
1220 
1221 /// In normal assembly languages, when the end of a function is unreachable,
1222 /// because the function ends in an infinite loop or a noreturn call or similar,
1223 /// it isn't necessary to worry about the function return type at the end of
1224 /// the function, because it's never reached. However, in WebAssembly, blocks
1225 /// that end at the function end need to have a return type signature that
1226 /// matches the function signature, even though it's unreachable. This function
1227 /// checks for such cases and fixes up the signatures.
1228 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
1229  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1230 
1231  if (MFI.getResults().empty())
1232  return;
1233 
1234  // MCInstLower will add the proper types to multivalue signatures based on the
1235  // function return type
1236  WebAssembly::BlockType RetType =
1237  MFI.getResults().size() > 1
1240  WebAssembly::toValType(MFI.getResults().front()));
1241 
1242  for (MachineBasicBlock &MBB : reverse(MF)) {
1243  for (MachineInstr &MI : reverse(MBB)) {
1244  if (MI.isPosition() || MI.isDebugInstr())
1245  continue;
1246  switch (MI.getOpcode()) {
1248  case WebAssembly::END_LOOP:
1249  case WebAssembly::END_TRY:
1250  EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1251  continue;
1252  default:
1253  // Something other than an `end`. We're done.
1254  return;
1255  }
1256  }
1257  }
1258 }
1259 
1260 // WebAssembly functions end with an end instruction, as if the function body
1261 // were a block.
1263  const WebAssemblyInstrInfo &TII) {
1264  BuildMI(MF.back(), MF.back().end(),
1265  MF.back().findPrevDebugLoc(MF.back().end()),
1266  TII.get(WebAssembly::END_FUNCTION));
1267 }
1268 
1269 /// Insert LOOP/TRY/BLOCK markers at appropriate places.
1270 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
1271  // We allocate one more than the number of blocks in the function to
1272  // accommodate for the possible fake block we may insert at the end.
1273  ScopeTops.resize(MF.getNumBlockIDs() + 1);
1274  // Place the LOOP for MBB if MBB is the header of a loop.
1275  for (auto &MBB : MF)
1276  placeLoopMarker(MBB);
1277 
1278  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1279  for (auto &MBB : MF) {
1280  if (MBB.isEHPad()) {
1281  // Place the TRY for MBB if MBB is the EH pad of an exception.
1283  MF.getFunction().hasPersonalityFn())
1284  placeTryMarker(MBB);
1285  } else {
1286  // Place the BLOCK for MBB if MBB is branched to from above.
1287  placeBlockMarker(MBB);
1288  }
1289  }
1290  // Fix mismatches in unwind destinations induced by linearizing the code.
1292  MF.getFunction().hasPersonalityFn())
1293  fixUnwindMismatches(MF);
1294 }
1295 
1296 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
1297  // Now rewrite references to basic blocks to be depth immediates.
1299  for (auto &MBB : reverse(MF)) {
1300  for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) {
1301  MachineInstr &MI = *I;
1302  switch (MI.getOpcode()) {
1303  case WebAssembly::BLOCK:
1304  case WebAssembly::TRY:
1305  assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
1306  MBB.getNumber() &&
1307  "Block/try marker should be balanced");
1308  Stack.pop_back();
1309  break;
1310 
1311  case WebAssembly::LOOP:
1312  assert(Stack.back() == &MBB && "Loop top should be balanced");
1313  Stack.pop_back();
1314  break;
1315 
1317  case WebAssembly::END_TRY:
1318  Stack.push_back(&MBB);
1319  break;
1320 
1321  case WebAssembly::END_LOOP:
1322  Stack.push_back(EndToBegin[&MI]->getParent());
1323  break;
1324 
1325  default:
1326  if (MI.isTerminator()) {
1327  // Rewrite MBB operands to be depth immediates.
1329  while (MI.getNumOperands() > 0)
1330  MI.RemoveOperand(MI.getNumOperands() - 1);
1331  for (auto MO : Ops) {
1332  if (MO.isMBB())
1333  MO = MachineOperand::CreateImm(getDepth(Stack, MO.getMBB()));
1334  MI.addOperand(MF, MO);
1335  }
1336  }
1337  break;
1338  }
1339  }
1340  }
1341  assert(Stack.empty() && "Control flow should be balanced");
1342 }
1343 
1344 void WebAssemblyCFGStackify::releaseMemory() {
1345  ScopeTops.clear();
1346  BeginToEnd.clear();
1347  EndToBegin.clear();
1348  TryToEHPad.clear();
1349  EHPadToTry.clear();
1350  AppendixBB = nullptr;
1351 }
1352 
1353 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
1354  LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
1355  "********** Function: "
1356  << MF.getName() << '\n');
1357  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1358 
1359  releaseMemory();
1360 
1361  // Liveness is not tracked for VALUE_STACK physreg.
1363 
1364  // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
1365  placeMarkers(MF);
1366 
1367  // Remove unnecessary instructions possibly introduced by try/end_trys.
1368  if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
1370  removeUnnecessaryInstrs(MF);
1371 
1372  // Convert MBB operands in terminators to relative depth immediates.
1373  rewriteDepthImmediates(MF);
1374 
1375  // Fix up block/loop/try signatures at the end of the function to conform to
1376  // WebAssembly's rules.
1377  fixEndsAtEndOfFunction(MF);
1378 
1379  // Add an end instruction at the end of the function body.
1380  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1382  .getTargetTriple()
1383  .isOSBinFormatELF())
1384  appendEndToFunction(MF, TII);
1385 
1386  MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
1387  return true;
1388 }
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
DILocation * get() const
Get the underlying DILocation.
Definition: DebugLoc.cpp:21
static void appendEndToFunction(MachineFunction &MF, const WebAssemblyInstrInfo &TII)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them...
bool isMarker(unsigned Opc)
static bool explicitlyBranchesTo(MachineBasicBlock *Pred, MachineBasicBlock *MBB)
Test whether Pred has any terminators explicitly branching to MBB, as opposed to falling through...
bool isOSBinFormatELF() const
Tests whether the OS uses the ELF binary format.
Definition: Triple.h:623
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
bool mayThrow(const MachineInstr &MI)
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:385
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
void transferSuccessors(MachineBasicBlock *FromMBB)
Transfers all the successors from MBB to this machine basic block (i.e., copies all the successors Fr...
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:33
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:477
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end...
iterator_range< succ_iterator > successors()
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...
AnalysisUsage & addRequired()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:414
MachineBasicBlock iterator that automatically skips over MIs that are inside bundles (i...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:673
iterator_range< iterator > terminators()
static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB, MachineBasicBlock &Split, WebAssemblyFunctionInfo &MFI, MachineRegisterInfo &MRI)
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
const char * getSymbolName() const
BlockT * getHeader() const
Definition: LoopInfo.h:105
#define DEBUG_TYPE
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
DebugLoc findPrevDebugLoc(instr_iterator MBBI)
Find the previous valid DebugLoc preceding MBBI, skipping and DBG_VALUE instructions.
static MachineBasicBlock::iterator getEarliestInsertPos(MachineBasicBlock *MBB, const SmallPtrSet< const MachineInstr *, 4 > &BeforeSet, const SmallPtrSet< const MachineInstr *, 4 > &AfterSet)
bool hasPersonalityFn() const
Check whether this function has a personality function.
Definition: Function.h:732
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
This file implements WebAssemblyException information analysis.
reverse_iterator rend()
INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, "Insert BLOCK/LOOP/TRY markers for WebAssembly scopes", false, false) FunctionPass *llvm
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
wasm::ValType toValType(const MVT &Ty)
reverse_iterator rbegin()
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
WebAssembly Exception Handling.
This class is intended to be used as a base class for asm properties and features specific to the tar...
Definition: MCAsmInfo.h:56
This file contains the declaration of the WebAssembly-specific utility functions. ...
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
#define P(N)
MachineInstrBundleIterator< MachineInstr > iterator
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:658
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const Triple & getTargetTriple() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const MCAsmInfo * getMCAsmInfo() const
Return target specific asm information.
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:370
bool isPredecessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a predecessor of this block.
Represent the analysis usage information of a pass.
Ty * getInfo()
getInfo - Keep track of various per-function pieces of information for backends that would like to do...
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
iterator_range< pred_iterator > predecessors()
size_t size() const
Definition: SmallVector.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1095
This file declares the WebAssembly-specific subclass of TargetSubtarget.
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
void addOperand(MachineFunction &MF, const MachineOperand &Op)
Add the specified operand to the instruction.
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
static unsigned getDepth(const SmallVectorImpl< const MachineBasicBlock *> &Stack, const MachineBasicBlock *MBB)
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
int64_t getImm() const
MachineInstr * getUniqueVRegDef(unsigned Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:256
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:64
This class is derived from MachineFunctionInfo and contains private WebAssembly-specific information ...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB &#39;Other&#39; at the position From, and insert it into this MBB right before &#39;...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
static MachineOperand CreateImm(int64_t Val)
#define I(x, y, z)
Definition: MD5.cpp:58
BlockType
Used as immediate MachineOperands for block signatures.
This file declares WebAssembly-specific per-machine-function information.
const MachineBasicBlock & back() const
const std::vector< MVT > & getResults() const
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
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
MachineInstr * removeFromParent()
Unlink &#39;this&#39; from the containing basic block, and return it without deleting it. ...
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
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:185
FunctionPass * createWebAssemblyCFGStackify()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void insert(iterator MBBI, MachineBasicBlock *MBB)
static MachineBasicBlock::iterator getLatestInsertPos(MachineBasicBlock *MBB, const SmallPtrSet< const MachineInstr *, 4 > &BeforeSet, const SmallPtrSet< const MachineInstr *, 4 > &AfterSet)
MachineBasicBlock * getBottom(const T *Unit)
Return the "bottom" block of an entity, which can be either a MachineLoop or WebAssemblyException.
void push_back(MachineBasicBlock *MBB)
static const Function * getParent(const Value *V)
ExceptionHandling getExceptionHandlingType() const
Definition: MCAsmInfo.h:593
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
void RemoveOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
bool isChild(const MachineInstr &MI, const WebAssemblyFunctionInfo &MFI)
Test whether MI is a child of some other node in an expression tree.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
void resize(size_type N)
Definition: SmallVector.h:344