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::ExprType::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::ExprType::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  // Local expression tree should go after the TRY.
530  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
531  --I) {
532  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
533  continue;
534  if (WebAssembly::isChild(*std::prev(I), MFI))
535  AfterSet.insert(&*std::prev(I));
536  else
537  break;
538  }
539 
540  // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
541  // contain the call within it. So the call should go after the TRY. The
542  // exception is when the header's terminator is a rethrow instruction, in
543  // which case that instruction, not a call instruction before it, is gonna
544  // throw.
545  if (MBB.isPredecessor(Header)) {
546  auto TermPos = Header->getFirstTerminator();
547  if (TermPos == Header->end() ||
548  TermPos->getOpcode() != WebAssembly::RETHROW) {
549  for (const auto &MI : reverse(*Header)) {
550  if (MI.isCall()) {
551  AfterSet.insert(&MI);
552  // Possibly throwing calls are usually wrapped by EH_LABEL
553  // instructions. We don't want to split them and the call.
554  if (MI.getIterator() != Header->begin() &&
555  std::prev(MI.getIterator())->isEHLabel())
556  AfterSet.insert(&*std::prev(MI.getIterator()));
557  break;
558  }
559  }
560  }
561  }
562 
563  // Add the TRY.
564  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
565  MachineInstr *Begin =
566  BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
567  TII.get(WebAssembly::TRY))
568  .addImm(int64_t(WebAssembly::ExprType::Void));
569 
570  // Decide where in Header to put the END_TRY.
571  BeforeSet.clear();
572  AfterSet.clear();
573  for (const auto &MI : *Cont) {
574 #ifndef NDEBUG
575  // END_TRY should precede existing LOOP and BLOCK markers.
576  if (MI.getOpcode() == WebAssembly::LOOP ||
577  MI.getOpcode() == WebAssembly::BLOCK)
578  AfterSet.insert(&MI);
579 
580  // All END_TRY markers placed earlier belong to exceptions that contains
581  // this one.
582  if (MI.getOpcode() == WebAssembly::END_TRY)
583  AfterSet.insert(&MI);
584 #endif
585 
586  // If there is a previously placed END_LOOP marker and its header is after
587  // where TRY marker is, this loop is contained within the 'catch' part, so
588  // the END_TRY marker should go after that. Otherwise, the whole try-catch
589  // is contained within this loop, so the END_TRY should go before that.
590  if (MI.getOpcode() == WebAssembly::END_LOOP) {
591  // For a LOOP to be after TRY, LOOP's BB should be after TRY's BB; if they
592  // are in the same BB, LOOP is always before TRY.
593  if (EndToBegin[&MI]->getParent()->getNumber() > Header->getNumber())
594  BeforeSet.insert(&MI);
595 #ifndef NDEBUG
596  else
597  AfterSet.insert(&MI);
598 #endif
599  }
600 
601  // It is not possible for an END_BLOCK to be already in this block.
602  }
603 
604  // Mark the end of the TRY.
605  InsertPos = getEarliestInsertPos(Cont, BeforeSet, AfterSet);
606  MachineInstr *End =
607  BuildMI(*Cont, InsertPos, Bottom->findBranchDebugLoc(),
608  TII.get(WebAssembly::END_TRY));
609  registerTryScope(Begin, End, &MBB);
610 
611  // Track the farthest-spanning scope that ends at this point. We create two
612  // mappings: (BB with 'end_try' -> BB with 'try') and (BB with 'catch' -> BB
613  // with 'try'). We need to create 'catch' -> 'try' mapping here too because
614  // markers should not span across 'catch'. For example, this should not
615  // happen:
616  //
617  // try
618  // block --| (X)
619  // catch |
620  // end_block --|
621  // end_try
622  for (int Number : {Cont->getNumber(), MBB.getNumber()}) {
623  if (!ScopeTops[Number] ||
624  ScopeTops[Number]->getNumber() > Header->getNumber())
625  ScopeTops[Number] = Header;
626  }
627 }
628 
629 void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) {
630  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
631 
632  // When there is an unconditional branch right before a catch instruction and
633  // it branches to the end of end_try marker, we don't need the branch, because
634  // it there is no exception, the control flow transfers to that point anyway.
635  // bb0:
636  // try
637  // ...
638  // br bb2 <- Not necessary
639  // bb1:
640  // catch
641  // ...
642  // bb2:
643  // end
644  for (auto &MBB : MF) {
645  if (!MBB.isEHPad())
646  continue;
647 
648  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
650  MachineBasicBlock *EHPadLayoutPred = MBB.getPrevNode();
651  MachineBasicBlock *Cont = BeginToEnd[EHPadToTry[&MBB]]->getParent();
652  bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
653  if (Analyzable && ((Cond.empty() && TBB && TBB == Cont) ||
654  (!Cond.empty() && FBB && FBB == Cont)))
655  TII.removeBranch(*EHPadLayoutPred);
656  }
657 
658  // When there are block / end_block markers that overlap with try / end_try
659  // markers, and the block and try markers' return types are the same, the
660  // block /end_block markers are not necessary, because try / end_try markers
661  // also can serve as boundaries for branches.
662  // block <- Not necessary
663  // try
664  // ...
665  // catch
666  // ...
667  // end
668  // end <- Not necessary
670  for (auto &MBB : MF) {
671  for (auto &MI : MBB) {
672  if (MI.getOpcode() != WebAssembly::TRY)
673  continue;
674 
675  MachineInstr *Try = &MI, *EndTry = BeginToEnd[Try];
676  MachineBasicBlock *TryBB = Try->getParent();
677  MachineBasicBlock *Cont = EndTry->getParent();
678  int64_t RetType = Try->getOperand(0).getImm();
679  for (auto B = Try->getIterator(), E = std::next(EndTry->getIterator());
680  B != TryBB->begin() && E != Cont->end() &&
681  std::prev(B)->getOpcode() == WebAssembly::BLOCK &&
682  E->getOpcode() == WebAssembly::END_BLOCK &&
683  std::prev(B)->getOperand(0).getImm() == RetType;
684  --B, ++E) {
685  ToDelete.push_back(&*std::prev(B));
686  ToDelete.push_back(&*E);
687  }
688  }
689  }
690  for (auto *MI : ToDelete) {
691  if (MI->getOpcode() == WebAssembly::BLOCK)
692  unregisterScope(MI);
693  MI->eraseFromParent();
694  }
695 }
696 
697 bool WebAssemblyCFGStackify::fixUnwindMismatches(MachineFunction &MF) {
698  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
700 
701  // Linearizing the control flow by placing TRY / END_TRY markers can create
702  // mismatches in unwind destinations. There are two kinds of mismatches we
703  // try to solve here.
704 
705  // 1. When an instruction may throw, but the EH pad it will unwind to can be
706  // different from the original CFG.
707  //
708  // Example: we have the following CFG:
709  // bb0:
710  // call @foo (if it throws, unwind to bb2)
711  // bb1:
712  // call @bar (if it throws, unwind to bb3)
713  // bb2 (ehpad):
714  // catch
715  // ...
716  // bb3 (ehpad)
717  // catch
718  // handler body
719  //
720  // And the CFG is sorted in this order. Then after placing TRY markers, it
721  // will look like: (BB markers are omitted)
722  // try $label1
723  // try
724  // call @foo
725  // call @bar (if it throws, unwind to bb3)
726  // catch <- ehpad (bb2)
727  // ...
728  // end_try
729  // catch <- ehpad (bb3)
730  // handler body
731  // end_try
732  //
733  // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it
734  // is supposed to end up. We solve this problem by
735  // a. Split the target unwind EH pad (here bb3) so that the handler body is
736  // right after 'end_try', which means we extract the handler body out of
737  // the catch block. We do this because this handler body should be
738  // somewhere branch-eable from the inner scope.
739  // b. Wrap the call that has an incorrect unwind destination ('call @bar'
740  // here) with a nested try/catch/end_try scope, and within the new catch
741  // block, branches to the handler body.
742  // c. Place a branch after the newly inserted nested end_try so it can bypass
743  // the handler body, which is now outside of a catch block.
744  //
745  // The result will like as follows. (new: a) means this instruction is newly
746  // created in the process of doing 'a' above.
747  //
748  // block $label0 (new: placeBlockMarker)
749  // try $label1
750  // try
751  // call @foo
752  // try (new: b)
753  // call @bar
754  // catch (new: b)
755  // local.set n / drop (new: b)
756  // br $label1 (new: b)
757  // end_try (new: b)
758  // catch <- ehpad (bb2)
759  // end_try
760  // br $label0 (new: c)
761  // catch <- ehpad (bb3)
762  // end_try (hoisted: a)
763  // handler body
764  // end_block (new: placeBlockMarker)
765  //
766  // Note that the new wrapping block/end_block will be generated later in
767  // placeBlockMarker.
768  //
769  // TODO Currently local.set and local.gets are generated to move exnref value
770  // created by catches. That's because we don't support yielding values from a
771  // block in LLVM machine IR yet, even though it is supported by wasm. Delete
772  // unnecessary local.get/local.sets once yielding values from a block is
773  // supported. The full EH spec requires multi-value support to do this, but
774  // for C++ we don't yet need it because we only throw a single i32.
775  //
776  // ---
777  // 2. The same as 1, but in this case an instruction unwinds to a caller
778  // function and not another EH pad.
779  //
780  // Example: we have the following CFG:
781  // bb0:
782  // call @foo (if it throws, unwind to bb2)
783  // bb1:
784  // call @bar (if it throws, unwind to caller)
785  // bb2 (ehpad):
786  // catch
787  // ...
788  //
789  // And the CFG is sorted in this order. Then after placing TRY markers, it
790  // will look like:
791  // try
792  // call @foo
793  // call @bar (if it throws, unwind to caller)
794  // catch <- ehpad (bb2)
795  // ...
796  // end_try
797  //
798  // Now if bar() throws, it is going to end up ip in bb2, when it is supposed
799  // throw up to the caller.
800  // We solve this problem by
801  // a. Create a new 'appendix' BB at the end of the function and put a single
802  // 'rethrow' instruction (+ local.get) in there.
803  // b. Wrap the call that has an incorrect unwind destination ('call @bar'
804  // here) with a nested try/catch/end_try scope, and within the new catch
805  // block, branches to the new appendix block.
806  //
807  // block $label0 (new: placeBlockMarker)
808  // try
809  // call @foo
810  // try (new: b)
811  // call @bar
812  // catch (new: b)
813  // local.set n (new: b)
814  // br $label0 (new: b)
815  // end_try (new: b)
816  // catch <- ehpad (bb2)
817  // ...
818  // end_try
819  // ...
820  // end_block (new: placeBlockMarker)
821  // local.get n (new: a) <- appendix block
822  // rethrow (new: a)
823  //
824  // In case there are multiple calls in a BB that may throw to the caller, they
825  // can be wrapped together in one nested try scope. (In 1, this couldn't
826  // happen, because may-throwing instruction there had an unwind destination,
827  // i.e., it was an invoke before, and there could be only one invoke within a
828  // BB.)
829 
831  // Range of intructions to be wrapped in a new nested try/catch
832  using TryRange = std::pair<MachineInstr *, MachineInstr *>;
833  // In original CFG, <unwind destionation BB, a vector of try ranges>
835  // In new CFG, <destination to branch to, a vector of try ranges>
837  // In new CFG, <destination to branch to, register containing exnref>
839 
840  // Gather possibly throwing calls (i.e., previously invokes) whose current
841  // unwind destination is not the same as the original CFG.
842  for (auto &MBB : reverse(MF)) {
843  bool SeenThrowableInstInBB = false;
844  for (auto &MI : reverse(MBB)) {
845  if (MI.getOpcode() == WebAssembly::TRY)
846  EHPadStack.pop_back();
847  else if (MI.getOpcode() == WebAssembly::CATCH)
848  EHPadStack.push_back(MI.getParent());
849 
850  // In this loop we only gather calls that have an EH pad to unwind. So
851  // there will be at most 1 such call (= invoke) in a BB, so after we've
852  // seen one, we can skip the rest of BB. Also if MBB has no EH pad
853  // successor or MI does not throw, this is not an invoke.
854  if (SeenThrowableInstInBB || !MBB.hasEHPadSuccessor() ||
856  continue;
857  SeenThrowableInstInBB = true;
858 
859  // If the EH pad on the stack top is where this instruction should unwind
860  // next, we're good.
861  MachineBasicBlock *UnwindDest = nullptr;
862  for (auto *Succ : MBB.successors()) {
863  if (Succ->isEHPad()) {
864  UnwindDest = Succ;
865  break;
866  }
867  }
868  if (EHPadStack.back() == UnwindDest)
869  continue;
870 
871  // If not, record the range.
872  UnwindDestToTryRanges[UnwindDest].push_back(TryRange(&MI, &MI));
873  }
874  }
875 
876  assert(EHPadStack.empty());
877 
878  // Gather possibly throwing calls that are supposed to unwind up to the caller
879  // if they throw, but currently unwind to an incorrect destination. Unlike the
880  // loop above, there can be multiple calls within a BB that unwind to the
881  // caller, which we should group together in a range.
882  bool NeedAppendixBlock = false;
883  for (auto &MBB : reverse(MF)) {
884  MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr; // inclusive
885  for (auto &MI : reverse(MBB)) {
886  if (MI.getOpcode() == WebAssembly::TRY)
887  EHPadStack.pop_back();
888  else if (MI.getOpcode() == WebAssembly::CATCH)
889  EHPadStack.push_back(MI.getParent());
890 
891  // If MBB has an EH pad successor, this inst does not unwind to caller.
892  if (MBB.hasEHPadSuccessor())
893  continue;
894 
895  // We wrap up the current range when we see a marker even if we haven't
896  // finished a BB.
897  if (RangeEnd && WebAssembly::isMarker(MI.getOpcode())) {
898  NeedAppendixBlock = true;
899  // Record the range. nullptr here means the unwind destination is the
900  // caller.
901  UnwindDestToTryRanges[nullptr].push_back(
902  TryRange(RangeBegin, RangeEnd));
903  RangeBegin = RangeEnd = nullptr; // Reset range pointers
904  }
905 
906  // If EHPadStack is empty, that means it is correctly unwind to caller if
907  // it throws, so we're good. If MI does not throw, we're good too.
908  if (EHPadStack.empty() || !WebAssembly::mayThrow(MI))
909  continue;
910 
911  // We found an instruction that unwinds to the caller but currently has an
912  // incorrect unwind destination. Create a new range or increment the
913  // currently existing range.
914  if (!RangeEnd)
915  RangeBegin = RangeEnd = &MI;
916  else
917  RangeBegin = &MI;
918  }
919 
920  if (RangeEnd) {
921  NeedAppendixBlock = true;
922  // Record the range. nullptr here means the unwind destination is the
923  // caller.
924  UnwindDestToTryRanges[nullptr].push_back(TryRange(RangeBegin, RangeEnd));
925  RangeBegin = RangeEnd = nullptr; // Reset range pointers
926  }
927  }
928 
929  assert(EHPadStack.empty());
930  // We don't have any unwind destination mismatches to resolve.
931  if (UnwindDestToTryRanges.empty())
932  return false;
933 
934  // If we found instructions that should unwind to the caller but currently
935  // have incorrect unwind destination, we create an appendix block at the end
936  // of the function with a local.get and a rethrow instruction.
937  if (NeedAppendixBlock) {
938  auto *AppendixBB = getAppendixBlock(MF);
939  Register ExnReg = MRI.createVirtualRegister(&WebAssembly::EXNREFRegClass);
940  BuildMI(AppendixBB, DebugLoc(), TII.get(WebAssembly::RETHROW))
941  .addReg(ExnReg);
942  // These instruction ranges should branch to this appendix BB.
943  for (auto Range : UnwindDestToTryRanges[nullptr])
944  BrDestToTryRanges[AppendixBB].push_back(Range);
945  BrDestToExnReg[AppendixBB] = ExnReg;
946  }
947 
948  // We loop through unwind destination EH pads that are targeted from some
949  // inner scopes. Because these EH pads are destination of more than one scope
950  // now, we split them so that the handler body is after 'end_try'.
951  // - Before
952  // ehpad:
953  // catch
954  // local.set n / drop
955  // handler body
956  // ...
957  // cont:
958  // end_try
959  //
960  // - After
961  // ehpad:
962  // catch
963  // local.set n / drop
964  // brdest: (new)
965  // end_try (hoisted from 'cont' BB)
966  // handler body (taken from 'ehpad')
967  // ...
968  // cont:
969  for (auto &P : UnwindDestToTryRanges) {
970  NumUnwindMismatches++;
971 
972  // This means the destination is the appendix BB, which was separately
973  // handled above.
974  if (!P.first)
975  continue;
976 
977  MachineBasicBlock *EHPad = P.first;
978 
979  // Find 'catch' and 'local.set' or 'drop' instruction that follows the
980  // 'catch'. If -wasm-disable-explicit-locals is not set, 'catch' should be
981  // always followed by either 'local.set' or a 'drop', because 'br_on_exn' is
982  // generated after 'catch' in LateEHPrepare and we don't support blocks
983  // taking values yet.
984  MachineInstr *Catch = nullptr;
985  unsigned ExnReg = 0;
986  for (auto &MI : *EHPad) {
987  switch (MI.getOpcode()) {
988  case WebAssembly::CATCH:
989  Catch = &MI;
990  ExnReg = Catch->getOperand(0).getReg();
991  break;
992  }
993  }
994  assert(Catch && "EH pad does not have a catch");
995  assert(ExnReg != 0 && "Invalid register");
996 
997  auto SplitPos = std::next(Catch->getIterator());
998 
999  // Create a new BB that's gonna be the destination for branches from the
1000  // inner mismatched scope.
1001  MachineInstr *BeginTry = EHPadToTry[EHPad];
1002  MachineInstr *EndTry = BeginToEnd[BeginTry];
1003  MachineBasicBlock *Cont = EndTry->getParent();
1004  auto *BrDest = MF.CreateMachineBasicBlock();
1005  MF.insert(std::next(EHPad->getIterator()), BrDest);
1006  // Hoist up the existing 'end_try'.
1007  BrDest->insert(BrDest->end(), EndTry->removeFromParent());
1008  // Take out the handler body from EH pad to the new branch destination BB.
1009  BrDest->splice(BrDest->end(), EHPad, SplitPos, EHPad->end());
1010  // Fix predecessor-successor relationship.
1011  BrDest->transferSuccessors(EHPad);
1012  EHPad->addSuccessor(BrDest);
1013 
1014  // All try ranges that were supposed to unwind to this EH pad now have to
1015  // branch to this new branch dest BB.
1016  for (auto Range : UnwindDestToTryRanges[EHPad])
1017  BrDestToTryRanges[BrDest].push_back(Range);
1018  BrDestToExnReg[BrDest] = ExnReg;
1019 
1020  // In case we fall through to the continuation BB after the catch block, we
1021  // now have to add a branch to it.
1022  // - Before
1023  // try
1024  // ...
1025  // (falls through to 'cont')
1026  // catch
1027  // handler body
1028  // end
1029  // <-- cont
1030  //
1031  // - After
1032  // try
1033  // ...
1034  // br %cont (new)
1035  // catch
1036  // end
1037  // handler body
1038  // <-- cont
1039  MachineBasicBlock *EHPadLayoutPred = &*std::prev(EHPad->getIterator());
1040  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
1042  bool Analyzable = !TII.analyzeBranch(*EHPadLayoutPred, TBB, FBB, Cond);
1043  if (Analyzable && !TBB && !FBB) {
1044  DebugLoc DL = EHPadLayoutPred->empty()
1045  ? DebugLoc()
1046  : EHPadLayoutPred->rbegin()->getDebugLoc();
1047  BuildMI(EHPadLayoutPred, DL, TII.get(WebAssembly::BR)).addMBB(Cont);
1048  }
1049  }
1050 
1051  // For possibly throwing calls whose unwind destinations are currently
1052  // incorrect because of CFG linearization, we wrap them with a nested
1053  // try/catch/end_try, and within the new catch block, we branch to the correct
1054  // handler.
1055  // - Before
1056  // mbb:
1057  // call @foo <- Unwind destination mismatch!
1058  // ehpad:
1059  // ...
1060  //
1061  // - After
1062  // mbb:
1063  // try (new)
1064  // call @foo
1065  // nested-ehpad: (new)
1066  // catch (new)
1067  // local.set n / drop (new)
1068  // br %brdest (new)
1069  // nested-end: (new)
1070  // end_try (new)
1071  // ehpad:
1072  // ...
1073  for (auto &P : BrDestToTryRanges) {
1074  MachineBasicBlock *BrDest = P.first;
1075  auto &TryRanges = P.second;
1076  unsigned ExnReg = BrDestToExnReg[BrDest];
1077 
1078  for (auto Range : TryRanges) {
1079  MachineInstr *RangeBegin = nullptr, *RangeEnd = nullptr;
1080  std::tie(RangeBegin, RangeEnd) = Range;
1081  auto *MBB = RangeBegin->getParent();
1082 
1083  // Include possible EH_LABELs in the range
1084  if (RangeBegin->getIterator() != MBB->begin() &&
1085  std::prev(RangeBegin->getIterator())->isEHLabel())
1086  RangeBegin = &*std::prev(RangeBegin->getIterator());
1087  if (std::next(RangeEnd->getIterator()) != MBB->end() &&
1088  std::next(RangeEnd->getIterator())->isEHLabel())
1089  RangeEnd = &*std::next(RangeEnd->getIterator());
1090 
1091  MachineBasicBlock *EHPad = nullptr;
1092  for (auto *Succ : MBB->successors()) {
1093  if (Succ->isEHPad()) {
1094  EHPad = Succ;
1095  break;
1096  }
1097  }
1098 
1099  // Create the nested try instruction.
1100  MachineInstr *NestedTry =
1101  BuildMI(*MBB, *RangeBegin, RangeBegin->getDebugLoc(),
1102  TII.get(WebAssembly::TRY))
1103  .addImm(int64_t(WebAssembly::ExprType::Void));
1104 
1105  // Create the nested EH pad and fill instructions in.
1106  MachineBasicBlock *NestedEHPad = MF.CreateMachineBasicBlock();
1107  MF.insert(std::next(MBB->getIterator()), NestedEHPad);
1108  NestedEHPad->setIsEHPad();
1109  NestedEHPad->setIsEHScopeEntry();
1110  BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::CATCH),
1111  ExnReg);
1112  BuildMI(NestedEHPad, RangeEnd->getDebugLoc(), TII.get(WebAssembly::BR))
1113  .addMBB(BrDest);
1114 
1115  // Create the nested continuation BB and end_try instruction.
1116  MachineBasicBlock *NestedCont = MF.CreateMachineBasicBlock();
1117  MF.insert(std::next(NestedEHPad->getIterator()), NestedCont);
1118  MachineInstr *NestedEndTry =
1119  BuildMI(*NestedCont, NestedCont->begin(), RangeEnd->getDebugLoc(),
1120  TII.get(WebAssembly::END_TRY));
1121  // In case MBB has more instructions after the try range, move them to the
1122  // new nested continuation BB.
1123  NestedCont->splice(NestedCont->end(), MBB,
1124  std::next(RangeEnd->getIterator()), MBB->end());
1125  registerTryScope(NestedTry, NestedEndTry, NestedEHPad);
1126 
1127  // Fix predecessor-successor relationship.
1128  NestedCont->transferSuccessors(MBB);
1129  if (EHPad)
1130  NestedCont->removeSuccessor(EHPad);
1131  MBB->addSuccessor(NestedEHPad);
1132  MBB->addSuccessor(NestedCont);
1133  NestedEHPad->addSuccessor(BrDest);
1134  }
1135  }
1136 
1137  // Renumber BBs and recalculate ScopeTop info because new BBs might have been
1138  // created and inserted above.
1139  MF.RenumberBlocks();
1140  ScopeTops.clear();
1141  ScopeTops.resize(MF.getNumBlockIDs());
1142  for (auto &MBB : reverse(MF)) {
1143  for (auto &MI : reverse(MBB)) {
1144  if (ScopeTops[MBB.getNumber()])
1145  break;
1146  switch (MI.getOpcode()) {
1148  case WebAssembly::END_LOOP:
1149  case WebAssembly::END_TRY:
1150  ScopeTops[MBB.getNumber()] = EndToBegin[&MI]->getParent();
1151  break;
1152  case WebAssembly::CATCH:
1153  ScopeTops[MBB.getNumber()] = EHPadToTry[&MBB]->getParent();
1154  break;
1155  }
1156  }
1157  }
1158 
1159  // Recompute the dominator tree.
1160  getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF);
1161 
1162  // Place block markers for newly added branches.
1164  for (auto &P : BrDestToTryRanges)
1165  BrDests.push_back(P.first);
1166  llvm::sort(BrDests,
1167  [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
1168  auto ANum = A->getNumber();
1169  auto BNum = B->getNumber();
1170  return ANum < BNum;
1171  });
1172  for (auto *Dest : BrDests)
1173  placeBlockMarker(*Dest);
1174 
1175  return true;
1176 }
1177 
1178 static unsigned
1180  const MachineBasicBlock *MBB) {
1181  unsigned Depth = 0;
1182  for (auto X : reverse(Stack)) {
1183  if (X == MBB)
1184  break;
1185  ++Depth;
1186  }
1187  assert(Depth < Stack.size() && "Branch destination should be in scope");
1188  return Depth;
1189 }
1190 
1191 /// In normal assembly languages, when the end of a function is unreachable,
1192 /// because the function ends in an infinite loop or a noreturn call or similar,
1193 /// it isn't necessary to worry about the function return type at the end of
1194 /// the function, because it's never reached. However, in WebAssembly, blocks
1195 /// that end at the function end need to have a return type signature that
1196 /// matches the function signature, even though it's unreachable. This function
1197 /// checks for such cases and fixes up the signatures.
1198 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
1199  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
1200  assert(MFI.getResults().size() <= 1);
1201 
1202  if (MFI.getResults().empty())
1203  return;
1204 
1205  WebAssembly::ExprType RetType;
1206  switch (MFI.getResults().front().SimpleTy) {
1207  case MVT::i32:
1208  RetType = WebAssembly::ExprType::I32;
1209  break;
1210  case MVT::i64:
1211  RetType = WebAssembly::ExprType::I64;
1212  break;
1213  case MVT::f32:
1214  RetType = WebAssembly::ExprType::F32;
1215  break;
1216  case MVT::f64:
1217  RetType = WebAssembly::ExprType::F64;
1218  break;
1219  case MVT::v16i8:
1220  case MVT::v8i16:
1221  case MVT::v4i32:
1222  case MVT::v2i64:
1223  case MVT::v4f32:
1224  case MVT::v2f64:
1225  RetType = WebAssembly::ExprType::V128;
1226  break;
1227  case MVT::exnref:
1229  break;
1230  default:
1231  llvm_unreachable("unexpected return type");
1232  }
1233 
1234  for (MachineBasicBlock &MBB : reverse(MF)) {
1235  for (MachineInstr &MI : reverse(MBB)) {
1236  if (MI.isPosition() || MI.isDebugInstr())
1237  continue;
1238  if (MI.getOpcode() == WebAssembly::END_BLOCK) {
1239  EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1240  continue;
1241  }
1242  if (MI.getOpcode() == WebAssembly::END_LOOP) {
1243  EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
1244  continue;
1245  }
1246  // Something other than an `end`. We're done.
1247  return;
1248  }
1249  }
1250 }
1251 
1252 // WebAssembly functions end with an end instruction, as if the function body
1253 // were a block.
1255  const WebAssemblyInstrInfo &TII) {
1256  BuildMI(MF.back(), MF.back().end(),
1257  MF.back().findPrevDebugLoc(MF.back().end()),
1258  TII.get(WebAssembly::END_FUNCTION));
1259 }
1260 
1261 /// Insert LOOP/TRY/BLOCK markers at appropriate places.
1262 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
1263  // We allocate one more than the number of blocks in the function to
1264  // accommodate for the possible fake block we may insert at the end.
1265  ScopeTops.resize(MF.getNumBlockIDs() + 1);
1266  // Place the LOOP for MBB if MBB is the header of a loop.
1267  for (auto &MBB : MF)
1268  placeLoopMarker(MBB);
1269 
1270  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1271  for (auto &MBB : MF) {
1272  if (MBB.isEHPad()) {
1273  // Place the TRY for MBB if MBB is the EH pad of an exception.
1275  MF.getFunction().hasPersonalityFn())
1276  placeTryMarker(MBB);
1277  } else {
1278  // Place the BLOCK for MBB if MBB is branched to from above.
1279  placeBlockMarker(MBB);
1280  }
1281  }
1282  // Fix mismatches in unwind destinations induced by linearizing the code.
1283  fixUnwindMismatches(MF);
1284 }
1285 
1286 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
1287  // Now rewrite references to basic blocks to be depth immediates.
1289  for (auto &MBB : reverse(MF)) {
1290  for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) {
1291  MachineInstr &MI = *I;
1292  switch (MI.getOpcode()) {
1293  case WebAssembly::BLOCK:
1294  case WebAssembly::TRY:
1295  assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
1296  MBB.getNumber() &&
1297  "Block/try marker should be balanced");
1298  Stack.pop_back();
1299  break;
1300 
1301  case WebAssembly::LOOP:
1302  assert(Stack.back() == &MBB && "Loop top should be balanced");
1303  Stack.pop_back();
1304  break;
1305 
1307  case WebAssembly::END_TRY:
1308  Stack.push_back(&MBB);
1309  break;
1310 
1311  case WebAssembly::END_LOOP:
1312  Stack.push_back(EndToBegin[&MI]->getParent());
1313  break;
1314 
1315  default:
1316  if (MI.isTerminator()) {
1317  // Rewrite MBB operands to be depth immediates.
1319  while (MI.getNumOperands() > 0)
1320  MI.RemoveOperand(MI.getNumOperands() - 1);
1321  for (auto MO : Ops) {
1322  if (MO.isMBB())
1323  MO = MachineOperand::CreateImm(getDepth(Stack, MO.getMBB()));
1324  MI.addOperand(MF, MO);
1325  }
1326  }
1327  break;
1328  }
1329  }
1330  }
1331  assert(Stack.empty() && "Control flow should be balanced");
1332 }
1333 
1334 void WebAssemblyCFGStackify::releaseMemory() {
1335  ScopeTops.clear();
1336  BeginToEnd.clear();
1337  EndToBegin.clear();
1338  TryToEHPad.clear();
1339  EHPadToTry.clear();
1340  AppendixBB = nullptr;
1341 }
1342 
1343 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
1344  LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
1345  "********** Function: "
1346  << MF.getName() << '\n');
1347  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
1348 
1349  releaseMemory();
1350 
1351  // Liveness is not tracked for VALUE_STACK physreg.
1353 
1354  // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
1355  placeMarkers(MF);
1356 
1357  // Remove unnecessary instructions possibly introduced by try/end_trys.
1358  if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
1360  removeUnnecessaryInstrs(MF);
1361 
1362  // Convert MBB operands in terminators to relative depth immediates.
1363  rewriteDepthImmediates(MF);
1364 
1365  // Fix up block/loop/try signatures at the end of the function to conform to
1366  // WebAssembly's rules.
1367  fixEndsAtEndOfFunction(MF);
1368 
1369  // Add an end instruction at the end of the function body.
1370  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
1372  .getTargetTriple()
1373  .isOSBinFormatELF())
1374  appendEndToFunction(MF, TII);
1375 
1376  MF.getInfo<WebAssemblyFunctionInfo>()->setCFGStackified();
1377  return true;
1378 }
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...
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
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
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:667
iterator_range< iterator > terminators()
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:273
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.
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)
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:657
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:1107
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)
ExprType
This is used to indicate block signatures.
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
int64_t getImm() const
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
This file declares WebAssembly-specific per-machine-function information.
const MachineBasicBlock & back() 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:171
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:211
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:576
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