LLVM  9.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 
25 #include "WebAssembly.h"
28 #include "WebAssemblySubtarget.h"
29 #include "WebAssemblyUtilities.h"
35 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/MC/MCAsmInfo.h"
38 #include "llvm/Support/Debug.h"
40 #include <cstring>
41 using namespace llvm;
42 
43 #define DEBUG_TYPE "wasm-cfg-stackify"
44 
45 namespace {
46 class WebAssemblyCFGStackify final : public MachineFunctionPass {
47  StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
48 
49  void getAnalysisUsage(AnalysisUsage &AU) const override {
54  }
55 
56  bool runOnMachineFunction(MachineFunction &MF) override;
57 
58  // For each block whose label represents the end of a scope, record the block
59  // which holds the beginning of the scope. This will allow us to quickly skip
60  // over scoped regions when walking blocks.
62 
63  void placeMarkers(MachineFunction &MF);
64  void placeBlockMarker(MachineBasicBlock &MBB);
65  void placeLoopMarker(MachineBasicBlock &MBB);
66  void placeTryMarker(MachineBasicBlock &MBB);
67  void rewriteDepthImmediates(MachineFunction &MF);
68  void fixEndsAtEndOfFunction(MachineFunction &MF);
69 
70  // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY).
72  // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY.
74  // <TRY marker, EH pad> map
76  // <EH pad, TRY marker> map
78  // <LOOP|TRY marker, Loop/exception bottom BB> map
80 
81  // Helper functions to register scope information created by marker
82  // instructions.
83  void registerScope(MachineInstr *Begin, MachineInstr *End);
84  void registerTryScope(MachineInstr *Begin, MachineInstr *End,
85  MachineBasicBlock *EHPad);
86 
88 
89 public:
90  static char ID; // Pass identification, replacement for typeid
91  WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
92  ~WebAssemblyCFGStackify() override { releaseMemory(); }
93  void releaseMemory() override;
94 };
95 } // end anonymous namespace
96 
98 INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,
99  "Insert BLOCK and LOOP markers for WebAssembly scopes", false,
100  false)
101 
103  return new WebAssemblyCFGStackify();
104 }
105 
106 /// Test whether Pred has any terminators explicitly branching to MBB, as
107 /// opposed to falling through. Note that it's possible (eg. in unoptimized
108 /// code) for a branch instruction to both branch to a block and fallthrough
109 /// to it, so we check the actual branch operands to see if there are any
110 /// explicit mentions.
112  MachineBasicBlock *MBB) {
113  for (MachineInstr &MI : Pred->terminators())
114  for (MachineOperand &MO : MI.explicit_operands())
115  if (MO.isMBB() && MO.getMBB() == MBB)
116  return true;
117  return false;
118 }
119 
120 // Returns an iterator to the earliest position possible within the MBB,
121 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
122 // contains instructions that should go before the marker, and AfterSet contains
123 // ones that should go after the marker. In this function, AfterSet is only
124 // used for sanity checking.
127  const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
128  const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
129  auto InsertPos = MBB->end();
130  while (InsertPos != MBB->begin()) {
131  if (BeforeSet.count(&*std::prev(InsertPos))) {
132 #ifndef NDEBUG
133  // Sanity check
134  for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
135  assert(!AfterSet.count(&*std::prev(Pos)));
136 #endif
137  break;
138  }
139  --InsertPos;
140  }
141  return InsertPos;
142 }
143 
144 // Returns an iterator to the latest position possible within the MBB,
145 // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
146 // contains instructions that should go before the marker, and AfterSet contains
147 // ones that should go after the marker. In this function, BeforeSet is only
148 // used for sanity checking.
151  const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
152  const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
153  auto InsertPos = MBB->begin();
154  while (InsertPos != MBB->end()) {
155  if (AfterSet.count(&*InsertPos)) {
156 #ifndef NDEBUG
157  // Sanity check
158  for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
159  assert(!BeforeSet.count(&*Pos));
160 #endif
161  break;
162  }
163  ++InsertPos;
164  }
165  return InsertPos;
166 }
167 
168 void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
169  MachineInstr *End) {
170  BeginToEnd[Begin] = End;
171  EndToBegin[End] = Begin;
172 }
173 
174 void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
175  MachineInstr *End,
176  MachineBasicBlock *EHPad) {
177  registerScope(Begin, End);
178  TryToEHPad[Begin] = EHPad;
179  EHPadToTry[EHPad] = Begin;
180 }
181 
182 // Given a LOOP/TRY marker, returns its bottom BB. Use cached information if any
183 // to prevent recomputation.
186  const auto &MLI = getAnalysis<MachineLoopInfo>();
187  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
188  if (BeginToBottom.count(Begin))
189  return BeginToBottom[Begin];
190  if (Begin->getOpcode() == WebAssembly::LOOP) {
191  MachineLoop *L = MLI.getLoopFor(Begin->getParent());
192  assert(L);
193  BeginToBottom[Begin] = WebAssembly::getBottom(L);
194  } else if (Begin->getOpcode() == WebAssembly::TRY) {
195  WebAssemblyException *WE = WEI.getExceptionFor(TryToEHPad[Begin]);
196  assert(WE);
197  BeginToBottom[Begin] = WebAssembly::getBottom(WE);
198  } else
199  assert(false);
200  return BeginToBottom[Begin];
201 }
202 
203 /// Insert a BLOCK marker for branches to MBB (if needed).
204 void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
205  // This should have been handled in placeTryMarker.
206  if (MBB.isEHPad())
207  return;
208 
209  MachineFunction &MF = *MBB.getParent();
210  auto &MDT = getAnalysis<MachineDominatorTree>();
211  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
212  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
213 
214  // First compute the nearest common dominator of all forward non-fallthrough
215  // predecessors so that we minimize the time that the BLOCK is on the stack,
216  // which reduces overall stack height.
217  MachineBasicBlock *Header = nullptr;
218  bool IsBranchedTo = false;
219  bool IsBrOnExn = false;
220  MachineInstr *BrOnExn = nullptr;
221  int MBBNumber = MBB.getNumber();
222  for (MachineBasicBlock *Pred : MBB.predecessors()) {
223  if (Pred->getNumber() < MBBNumber) {
224  Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
225  if (explicitlyBranchesTo(Pred, &MBB)) {
226  IsBranchedTo = true;
227  if (Pred->getFirstTerminator()->getOpcode() == WebAssembly::BR_ON_EXN) {
228  IsBrOnExn = true;
229  assert(!BrOnExn && "There should be only one br_on_exn per block");
230  BrOnExn = &*Pred->getFirstTerminator();
231  }
232  }
233  }
234  }
235  if (!Header)
236  return;
237  if (!IsBranchedTo)
238  return;
239 
240  assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
241  MachineBasicBlock *LayoutPred = &*std::prev(MachineFunction::iterator(&MBB));
242 
243  // If the nearest common dominator is inside a more deeply nested context,
244  // walk out to the nearest scope which isn't more deeply nested.
245  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
246  if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
247  if (ScopeTop->getNumber() > Header->getNumber()) {
248  // Skip over an intervening scope.
249  I = std::next(MachineFunction::iterator(ScopeTop));
250  } else {
251  // We found a scope level at an appropriate depth.
252  Header = ScopeTop;
253  break;
254  }
255  }
256  }
257 
258  // Decide where in Header to put the BLOCK.
259 
260  // Instructions that should go before the BLOCK.
262  // Instructions that should go after the BLOCK.
264  for (const auto &MI : *Header) {
265  // If there is a previously placed LOOP/TRY marker and the bottom block of
266  // the loop/exception is above MBB, it should be after the BLOCK, because
267  // the loop/exception is nested in this block. Otherwise it should be before
268  // the BLOCK.
269  if (MI.getOpcode() == WebAssembly::LOOP ||
270  MI.getOpcode() == WebAssembly::TRY) {
271  if (MBB.getNumber() > getBottom(&MI)->getNumber())
272  AfterSet.insert(&MI);
273 #ifndef NDEBUG
274  else
275  BeforeSet.insert(&MI);
276 #endif
277  }
278 
279  // All previously inserted BLOCK markers should be after the BLOCK because
280  // they are all nested blocks.
281  if (MI.getOpcode() == WebAssembly::BLOCK)
282  AfterSet.insert(&MI);
283 
284 #ifndef NDEBUG
285  // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK.
286  if (MI.getOpcode() == WebAssembly::END_BLOCK ||
287  MI.getOpcode() == WebAssembly::END_LOOP ||
288  MI.getOpcode() == WebAssembly::END_TRY)
289  BeforeSet.insert(&MI);
290 #endif
291 
292  // Terminators should go after the BLOCK.
293  if (MI.isTerminator())
294  AfterSet.insert(&MI);
295  }
296 
297  // Local expression tree should go after the BLOCK.
298  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
299  --I) {
300  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
301  continue;
302  if (WebAssembly::isChild(*std::prev(I), MFI))
303  AfterSet.insert(&*std::prev(I));
304  else
305  break;
306  }
307 
308  // Add the BLOCK.
309 
310  // 'br_on_exn' extracts except_ref object and pushes variable number of values
311  // depending on its tag. For C++ exception, its a single i32 value, and the
312  // generated code will be in the form of:
313  // block i32
314  // br_on_exn 0, $__cpp_exception
315  // rethrow
316  // end_block
318  if (IsBrOnExn) {
319  const char *TagName = BrOnExn->getOperand(1).getSymbolName();
320  if (std::strcmp(TagName, "__cpp_exception") != 0)
321  llvm_unreachable("Only C++ exception is supported");
322  ReturnType = WebAssembly::ExprType::I32;
323  }
324 
325  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
326  MachineInstr *Begin =
327  BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
328  TII.get(WebAssembly::BLOCK))
329  .addImm(int64_t(ReturnType));
330 
331  // Decide where in Header to put the END_BLOCK.
332  BeforeSet.clear();
333  AfterSet.clear();
334  for (auto &MI : MBB) {
335 #ifndef NDEBUG
336  // END_BLOCK should precede existing LOOP and TRY markers.
337  if (MI.getOpcode() == WebAssembly::LOOP ||
338  MI.getOpcode() == WebAssembly::TRY)
339  AfterSet.insert(&MI);
340 #endif
341 
342  // If there is a previously placed END_LOOP marker and the header of the
343  // loop is above this block's header, the END_LOOP should be placed after
344  // the BLOCK, because the loop contains this block. Otherwise the END_LOOP
345  // should be placed before the BLOCK. The same for END_TRY.
346  if (MI.getOpcode() == WebAssembly::END_LOOP ||
347  MI.getOpcode() == WebAssembly::END_TRY) {
348  if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
349  BeforeSet.insert(&MI);
350 #ifndef NDEBUG
351  else
352  AfterSet.insert(&MI);
353 #endif
354  }
355  }
356 
357  // Mark the end of the block.
358  InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
359  MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
360  TII.get(WebAssembly::END_BLOCK));
361  registerScope(Begin, End);
362 
363  // Track the farthest-spanning scope that ends at this point.
364  int Number = MBB.getNumber();
365  if (!ScopeTops[Number] ||
366  ScopeTops[Number]->getNumber() > Header->getNumber())
367  ScopeTops[Number] = Header;
368 }
369 
370 /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
371 void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
372  MachineFunction &MF = *MBB.getParent();
373  const auto &MLI = getAnalysis<MachineLoopInfo>();
374  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
375 
376  MachineLoop *Loop = MLI.getLoopFor(&MBB);
377  if (!Loop || Loop->getHeader() != &MBB)
378  return;
379 
380  // The operand of a LOOP is the first block after the loop. If the loop is the
381  // bottom of the function, insert a dummy block at the end.
383  auto Iter = std::next(MachineFunction::iterator(Bottom));
384  if (Iter == MF.end()) {
386  // Give it a fake predecessor so that AsmPrinter prints its label.
387  Label->addSuccessor(Label);
388  MF.push_back(Label);
389  Iter = std::next(MachineFunction::iterator(Bottom));
390  }
391  MachineBasicBlock *AfterLoop = &*Iter;
392 
393  // Decide where in Header to put the LOOP.
396  for (const auto &MI : MBB) {
397  // LOOP marker should be after any existing loop that ends here. Otherwise
398  // we assume the instruction belongs to the loop.
399  if (MI.getOpcode() == WebAssembly::END_LOOP)
400  BeforeSet.insert(&MI);
401 #ifndef NDEBUG
402  else
403  AfterSet.insert(&MI);
404 #endif
405  }
406 
407  // Mark the beginning of the loop.
408  auto InsertPos = getEarliestInsertPos(&MBB, BeforeSet, AfterSet);
409  MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),
410  TII.get(WebAssembly::LOOP))
411  .addImm(int64_t(WebAssembly::ExprType::Void));
412 
413  // Decide where in Header to put the END_LOOP.
414  BeforeSet.clear();
415  AfterSet.clear();
416 #ifndef NDEBUG
417  for (const auto &MI : MBB)
418  // Existing END_LOOP markers belong to parent loops of this loop
419  if (MI.getOpcode() == WebAssembly::END_LOOP)
420  AfterSet.insert(&MI);
421 #endif
422 
423  // Mark the end of the loop (using arbitrary debug location that branched to
424  // the loop end as its location).
425  InsertPos = getEarliestInsertPos(AfterLoop, BeforeSet, AfterSet);
426  DebugLoc EndDL = (*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  if (!MBB.isEHPad())
440  return;
441 
442  MachineFunction &MF = *MBB.getParent();
443  auto &MDT = getAnalysis<MachineDominatorTree>();
444  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
445  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
446  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
447 
448  // Compute the nearest common dominator of all unwind predecessors
449  MachineBasicBlock *Header = nullptr;
450  int MBBNumber = MBB.getNumber();
451  for (auto *Pred : MBB.predecessors()) {
452  if (Pred->getNumber() < MBBNumber) {
453  Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
454  assert(!explicitlyBranchesTo(Pred, &MBB) &&
455  "Explicit branch to an EH pad!");
456  }
457  }
458  if (!Header)
459  return;
460 
461  // If this try is at the bottom of the function, insert a dummy block at the
462  // end.
463  WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
464  assert(WE);
466 
467  auto Iter = std::next(MachineFunction::iterator(Bottom));
468  if (Iter == MF.end()) {
470  // Give it a fake predecessor so that AsmPrinter prints its label.
471  Label->addSuccessor(Label);
472  MF.push_back(Label);
473  Iter = std::next(MachineFunction::iterator(Bottom));
474  }
475  MachineBasicBlock *AfterTry = &*Iter;
476 
477  assert(AfterTry != &MF.front());
478  MachineBasicBlock *LayoutPred =
479  &*std::prev(MachineFunction::iterator(AfterTry));
480 
481  // If the nearest common dominator is inside a more deeply nested context,
482  // walk out to the nearest scope which isn't more deeply nested.
483  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
484  if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
485  if (ScopeTop->getNumber() > Header->getNumber()) {
486  // Skip over an intervening scope.
487  I = std::next(MachineFunction::iterator(ScopeTop));
488  } else {
489  // We found a scope level at an appropriate depth.
490  Header = ScopeTop;
491  break;
492  }
493  }
494  }
495 
496  // Decide where in Header to put the TRY.
497 
498  // Instructions that should go before the BLOCK.
500  // Instructions that should go after the BLOCK.
502  for (const auto &MI : *Header) {
503  // If there is a previously placed LOOP marker and the bottom block of
504  // the loop is above MBB, the LOOP should be after the TRY, because the
505  // loop is nested in this try. Otherwise it should be before the TRY.
506  if (MI.getOpcode() == WebAssembly::LOOP) {
507  if (MBB.getNumber() > Bottom->getNumber())
508  AfterSet.insert(&MI);
509 #ifndef NDEBUG
510  else
511  BeforeSet.insert(&MI);
512 #endif
513  }
514 
515  // All previously inserted TRY markers should be after the TRY because they
516  // are all nested trys.
517  if (MI.getOpcode() == WebAssembly::TRY)
518  AfterSet.insert(&MI);
519 
520 #ifndef NDEBUG
521  // All END_(LOOP/TRY) markers should be before the TRY.
522  if (MI.getOpcode() == WebAssembly::END_LOOP ||
523  MI.getOpcode() == WebAssembly::END_TRY)
524  BeforeSet.insert(&MI);
525 #endif
526 
527  // Terminators should go after the TRY.
528  if (MI.isTerminator())
529  AfterSet.insert(&MI);
530  }
531 
532  // Local expression tree should go after the TRY.
533  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
534  --I) {
535  if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
536  continue;
537  if (WebAssembly::isChild(*std::prev(I), MFI))
538  AfterSet.insert(&*std::prev(I));
539  else
540  break;
541  }
542 
543  // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
544  // contain the call within it. So the call should go after the TRY. The
545  // exception is when the header's terminator is a rethrow instruction, in
546  // which case that instruction, not a call instruction before it, is gonna
547  // throw.
548  if (MBB.isPredecessor(Header)) {
549  auto TermPos = Header->getFirstTerminator();
550  if (TermPos == Header->end() ||
551  TermPos->getOpcode() != WebAssembly::RETHROW) {
552  for (const auto &MI : reverse(*Header)) {
553  if (MI.isCall()) {
554  AfterSet.insert(&MI);
555  break;
556  }
557  }
558  }
559  }
560 
561  // Add the TRY.
562  auto InsertPos = getLatestInsertPos(Header, BeforeSet, AfterSet);
563  MachineInstr *Begin =
564  BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
565  TII.get(WebAssembly::TRY))
566  .addImm(int64_t(WebAssembly::ExprType::Void));
567 
568  // Decide where in Header to put the END_TRY.
569  BeforeSet.clear();
570  AfterSet.clear();
571  for (const auto &MI : *AfterTry) {
572 #ifndef NDEBUG
573  // END_TRY should precede existing LOOP markers.
574  if (MI.getOpcode() == WebAssembly::LOOP)
575  AfterSet.insert(&MI);
576 
577  // All END_TRY markers placed earlier belong to exceptions that contains
578  // this one.
579  if (MI.getOpcode() == WebAssembly::END_TRY)
580  AfterSet.insert(&MI);
581 #endif
582 
583  // If there is a previously placed END_LOOP marker and its header is after
584  // where TRY marker is, this loop is contained within the 'catch' part, so
585  // the END_TRY marker should go after that. Otherwise, the whole try-catch
586  // is contained within this loop, so the END_TRY should go before that.
587  if (MI.getOpcode() == WebAssembly::END_LOOP) {
588  if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
589  BeforeSet.insert(&MI);
590 #ifndef NDEBUG
591  else
592  AfterSet.insert(&MI);
593 #endif
594  }
595  }
596 
597  // Mark the end of the TRY.
598  InsertPos = getEarliestInsertPos(AfterTry, BeforeSet, AfterSet);
599  MachineInstr *End =
600  BuildMI(*AfterTry, InsertPos, Bottom->findBranchDebugLoc(),
601  TII.get(WebAssembly::END_TRY));
602  registerTryScope(Begin, End, &MBB);
603 
604  // Track the farthest-spanning scope that ends at this point.
605  int Number = AfterTry->getNumber();
606  if (!ScopeTops[Number] ||
607  ScopeTops[Number]->getNumber() > Header->getNumber())
608  ScopeTops[Number] = Header;
609 }
610 
611 static unsigned
613  const MachineBasicBlock *MBB) {
614  unsigned Depth = 0;
615  for (auto X : reverse(Stack)) {
616  if (X == MBB)
617  break;
618  ++Depth;
619  }
620  assert(Depth < Stack.size() && "Branch destination should be in scope");
621  return Depth;
622 }
623 
624 /// In normal assembly languages, when the end of a function is unreachable,
625 /// because the function ends in an infinite loop or a noreturn call or similar,
626 /// it isn't necessary to worry about the function return type at the end of
627 /// the function, because it's never reached. However, in WebAssembly, blocks
628 /// that end at the function end need to have a return type signature that
629 /// matches the function signature, even though it's unreachable. This function
630 /// checks for such cases and fixes up the signatures.
631 void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
632  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
633  assert(MFI.getResults().size() <= 1);
634 
635  if (MFI.getResults().empty())
636  return;
637 
638  WebAssembly::ExprType RetType;
639  switch (MFI.getResults().front().SimpleTy) {
640  case MVT::i32:
641  RetType = WebAssembly::ExprType::I32;
642  break;
643  case MVT::i64:
644  RetType = WebAssembly::ExprType::I64;
645  break;
646  case MVT::f32:
647  RetType = WebAssembly::ExprType::F32;
648  break;
649  case MVT::f64:
650  RetType = WebAssembly::ExprType::F64;
651  break;
652  case MVT::v16i8:
653  case MVT::v8i16:
654  case MVT::v4i32:
655  case MVT::v2i64:
656  case MVT::v4f32:
657  case MVT::v2f64:
658  RetType = WebAssembly::ExprType::V128;
659  break;
660  case MVT::ExceptRef:
662  break;
663  default:
664  llvm_unreachable("unexpected return type");
665  }
666 
667  for (MachineBasicBlock &MBB : reverse(MF)) {
668  for (MachineInstr &MI : reverse(MBB)) {
669  if (MI.isPosition() || MI.isDebugInstr())
670  continue;
671  if (MI.getOpcode() == WebAssembly::END_BLOCK) {
672  EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
673  continue;
674  }
675  if (MI.getOpcode() == WebAssembly::END_LOOP) {
676  EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
677  continue;
678  }
679  // Something other than an `end`. We're done.
680  return;
681  }
682  }
683 }
684 
685 // WebAssembly functions end with an end instruction, as if the function body
686 // were a block.
688  const WebAssemblyInstrInfo &TII) {
689  BuildMI(MF.back(), MF.back().end(),
690  MF.back().findPrevDebugLoc(MF.back().end()),
691  TII.get(WebAssembly::END_FUNCTION));
692 }
693 
694 /// Insert LOOP/TRY/BLOCK markers at appropriate places.
695 void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
696  // We allocate one more than the number of blocks in the function to
697  // accommodate for the possible fake block we may insert at the end.
698  ScopeTops.resize(MF.getNumBlockIDs() + 1);
699  // Place the LOOP for MBB if MBB is the header of a loop.
700  for (auto &MBB : MF)
701  placeLoopMarker(MBB);
702  // Place the TRY for MBB if MBB is the EH pad of an exception.
703  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
705  MF.getFunction().hasPersonalityFn())
706  for (auto &MBB : MF)
707  placeTryMarker(MBB);
708  // Place the BLOCK for MBB if MBB is branched to from above.
709  for (auto &MBB : MF)
710  placeBlockMarker(MBB);
711 }
712 
713 void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
714  // Now rewrite references to basic blocks to be depth immediates.
716  for (auto &MBB : reverse(MF)) {
717  for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) {
718  MachineInstr &MI = *I;
719  switch (MI.getOpcode()) {
720  case WebAssembly::BLOCK:
721  assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
722  MBB.getNumber() &&
723  "Block/try should be balanced");
724  Stack.pop_back();
725  break;
726 
727  case WebAssembly::TRY:
728  assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
729  MBB.getNumber() &&
730  "Block/try marker should be balanced");
731  Stack.pop_back();
732  break;
733 
734  case WebAssembly::LOOP:
735  assert(Stack.back() == &MBB && "Loop top should be balanced");
736  Stack.pop_back();
737  break;
738 
740  case WebAssembly::END_TRY:
741  Stack.push_back(&MBB);
742  break;
743 
744  case WebAssembly::END_LOOP:
745  Stack.push_back(EndToBegin[&MI]->getParent());
746  break;
747 
748  default:
749  if (MI.isTerminator()) {
750  // Rewrite MBB operands to be depth immediates.
752  while (MI.getNumOperands() > 0)
753  MI.RemoveOperand(MI.getNumOperands() - 1);
754  for (auto MO : Ops) {
755  if (MO.isMBB())
756  MO = MachineOperand::CreateImm(getDepth(Stack, MO.getMBB()));
757  MI.addOperand(MF, MO);
758  }
759  }
760  break;
761  }
762  }
763  }
764  assert(Stack.empty() && "Control flow should be balanced");
765 }
766 
767 void WebAssemblyCFGStackify::releaseMemory() {
768  ScopeTops.clear();
769  BeginToEnd.clear();
770  EndToBegin.clear();
771  TryToEHPad.clear();
772  EHPadToTry.clear();
773  BeginToBottom.clear();
774 }
775 
776 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
777  LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
778  "********** Function: "
779  << MF.getName() << '\n');
780 
781  releaseMemory();
782 
783  // Liveness is not tracked for VALUE_STACK physreg.
785 
786  // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
787  placeMarkers(MF);
788 
789  // Convert MBB operands in terminators to relative depth immediates.
790  rewriteDepthImmediates(MF);
791 
792  // Fix up block/loop/try signatures at the end of the function to conform to
793  // WebAssembly's rules.
794  fixEndsAtEndOfFunction(MF);
795 
796  // Add an end instruction at the end of the function body.
797  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
799  .getTargetTriple()
800  .isOSBinFormatELF())
802 
803  return true;
804 }
pred_reverse_iterator pred_rbegin()
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
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:602
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
A debug info location.
Definition: DebugLoc.h:33
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:458
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end...
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:411
INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, "Insert BLOCK and LOOP markers for WebAssembly scopes", false, false) FunctionPass *llvm
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:648
iterator_range< iterator > terminators()
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
const char * getSymbolName() const
BlockT * getHeader() const
Definition: LoopInfo.h:99
#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:266
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)
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()
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.
Windows 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:55
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.
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")
This file provides WebAssembly-specific target descriptions.
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
iterator_range< pred_iterator > predecessors()
const MachineBasicBlock & front() const
size_t size() const
Definition: SmallVector.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
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:839
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
DebugLoc findBranchDebugLoc()
Find and return the merged DebugLoc of the branch instructions of the block.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:253
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.
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:464
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
FunctionPass * createWebAssemblyCFGStackify()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:569
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...
#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:413
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...