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