LCOV - code coverage report
Current view: top level - lib/Target/WebAssembly - WebAssemblyCFGStackify.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 240 260 92.3 %
Date: 2018-10-20 13:21:21 Functions: 21 23 91.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : ///
      10             : /// \file
      11             : /// This file implements a CFG stacking pass.
      12             : ///
      13             : /// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes,
      14             : /// since scope boundaries serve as the labels for WebAssembly's control
      15             : /// transfers.
      16             : ///
      17             : /// This is sufficient to convert arbitrary CFGs into a form that works on
      18             : /// WebAssembly, provided that all loops are single-entry.
      19             : ///
      20             : /// In case we use exceptions, this pass also fixes mismatches in unwind
      21             : /// destinations created during transforming CFG into wasm structured format.
      22             : ///
      23             : //===----------------------------------------------------------------------===//
      24             : 
      25             : #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
      26             : #include "WebAssembly.h"
      27             : #include "WebAssemblyExceptionInfo.h"
      28             : #include "WebAssemblyMachineFunctionInfo.h"
      29             : #include "WebAssemblySubtarget.h"
      30             : #include "WebAssemblyUtilities.h"
      31             : #include "llvm/CodeGen/MachineDominators.h"
      32             : #include "llvm/CodeGen/MachineFunction.h"
      33             : #include "llvm/CodeGen/MachineInstrBuilder.h"
      34             : #include "llvm/CodeGen/MachineLoopInfo.h"
      35             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      36             : #include "llvm/CodeGen/Passes.h"
      37             : #include "llvm/CodeGen/WasmEHFuncInfo.h"
      38             : #include "llvm/MC/MCAsmInfo.h"
      39             : #include "llvm/Support/Debug.h"
      40             : #include "llvm/Support/raw_ostream.h"
      41             : using namespace llvm;
      42             : 
      43             : #define DEBUG_TYPE "wasm-cfg-stackify"
      44             : 
      45             : namespace {
      46             : class WebAssemblyCFGStackify final : public MachineFunctionPass {
      47         306 :   StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
      48             : 
      49         306 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      50             :     AU.addRequired<MachineDominatorTree>();
      51             :     AU.addRequired<MachineLoopInfo>();
      52             :     AU.addRequired<WebAssemblyExceptionInfo>();
      53         306 :     MachineFunctionPass::getAnalysisUsage(AU);
      54         306 :   }
      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.
      61             :   SmallVector<MachineBasicBlock *, 8> ScopeTops;
      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).
      71             :   DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd;
      72             :   // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY.
      73             :   DenseMap<const MachineInstr *, MachineInstr *> EndToBegin;
      74             :   // <TRY marker, EH pad> map
      75             :   DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad;
      76             :   // <EH pad, TRY marker> map
      77             :   DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry;
      78             :   // <LOOP|TRY marker, Loop/exception bottom BB> map
      79             :   DenseMap<const MachineInstr *, MachineBasicBlock *> BeginToBottom;
      80             : 
      81             :   // Helper functions to register / unregister scope information created by
      82             :   // marker instructions.
      83             :   void registerScope(MachineInstr *Begin, MachineInstr *End);
      84             :   void registerTryScope(MachineInstr *Begin, MachineInstr *End,
      85             :                         MachineBasicBlock *EHPad);
      86             :   void unregisterScope(MachineInstr *Begin);
      87             : 
      88             :   MachineBasicBlock *getBottom(const MachineInstr *Begin);
      89             : 
      90             : public:
      91             :   static char ID; // Pass identification, replacement for typeid
      92         306 :   WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
      93         903 :   ~WebAssemblyCFGStackify() override { releaseMemory(); }
      94             :   void releaseMemory() override;
      95             : };
      96             : } // end anonymous namespace
      97             : 
      98             : char WebAssemblyCFGStackify::ID = 0;
      99      199030 : INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,
     100             :                 "Insert BLOCK and LOOP markers for WebAssembly scopes", false,
     101             :                 false)
     102             : 
     103         305 : FunctionPass *llvm::createWebAssemblyCFGStackify() {
     104         305 :   return new WebAssemblyCFGStackify();
     105             : }
     106             : 
     107             : /// Test whether Pred has any terminators explicitly branching to MBB, as
     108             : /// opposed to falling through. Note that it's possible (eg. in unoptimized
     109             : /// code) for a branch instruction to both branch to a block and fallthrough
     110             : /// to it, so we check the actual branch operands to see if there are any
     111             : /// explicit mentions.
     112         655 : static bool ExplicitlyBranchesTo(MachineBasicBlock *Pred,
     113             :                                  MachineBasicBlock *MBB) {
     114         909 :   for (MachineInstr &MI : Pred->terminators())
     115             :     // Even if a rethrow takes a BB argument, it is not a branch
     116         526 :     if (!WebAssembly::isRethrow(MI))
     117        1247 :       for (MachineOperand &MO : MI.explicit_operands())
     118         993 :         if (MO.isMBB() && MO.getMBB() == MBB)
     119             :           return true;
     120             :   return false;
     121             : }
     122             : 
     123             : // Returns an iterator to the earliest position possible within the MBB,
     124             : // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
     125             : // contains instructions that should go before the marker, and AfterSet contains
     126             : // ones that should go after the marker. In this function, AfterSet is only
     127             : // used for sanity checking.
     128             : static MachineBasicBlock::iterator
     129           0 : GetEarliestInsertPos(MachineBasicBlock *MBB,
     130             :                      const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
     131             :                      const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
     132           0 :   auto InsertPos = MBB->end();
     133           0 :   while (InsertPos != MBB->begin()) {
     134           0 :     if (BeforeSet.count(&*std::prev(InsertPos))) {
     135             : #ifndef NDEBUG
     136             :       // Sanity check
     137             :       for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
     138             :         assert(!AfterSet.count(&*std::prev(Pos)));
     139             : #endif
     140             :       break;
     141             :     }
     142             :     --InsertPos;
     143             :   }
     144           0 :   return InsertPos;
     145             : }
     146             : 
     147             : // Returns an iterator to the latest position possible within the MBB,
     148             : // satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
     149             : // contains instructions that should go before the marker, and AfterSet contains
     150             : // ones that should go after the marker. In this function, BeforeSet is only
     151             : // used for sanity checking.
     152             : static MachineBasicBlock::iterator
     153           0 : GetLatestInsertPos(MachineBasicBlock *MBB,
     154             :                    const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
     155             :                    const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
     156             :   auto InsertPos = MBB->begin();
     157           0 :   while (InsertPos != MBB->end()) {
     158           0 :     if (AfterSet.count(&*InsertPos)) {
     159             : #ifndef NDEBUG
     160             :       // Sanity check
     161             :       for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
     162             :         assert(!BeforeSet.count(&*Pos));
     163             : #endif
     164             :       break;
     165             :     }
     166             :     ++InsertPos;
     167             :   }
     168           0 :   return InsertPos;
     169             : }
     170             : 
     171         346 : void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
     172             :                                            MachineInstr *End) {
     173         346 :   BeginToEnd[Begin] = End;
     174         346 :   EndToBegin[End] = Begin;
     175         346 : }
     176             : 
     177          23 : void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
     178             :                                               MachineInstr *End,
     179             :                                               MachineBasicBlock *EHPad) {
     180          23 :   registerScope(Begin, End);
     181          23 :   TryToEHPad[Begin] = EHPad;
     182          23 :   EHPadToTry[EHPad] = Begin;
     183          23 : }
     184             : 
     185             : void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
     186             :   assert(BeginToEnd.count(Begin));
     187             :   MachineInstr *End = BeginToEnd[Begin];
     188             :   assert(EndToBegin.count(End));
     189             :   BeginToEnd.erase(Begin);
     190             :   EndToBegin.erase(End);
     191             :   MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
     192             :   if (EHPad) {
     193             :     assert(EHPadToTry.count(EHPad));
     194             :     TryToEHPad.erase(Begin);
     195             :     EHPadToTry.erase(EHPad);
     196             :   }
     197             :   MachineBasicBlock *Bottom = BeginToBottom.lookup(Begin);
     198             :   if (Bottom)
     199             :     BeginToBottom.erase(Begin);
     200             : }
     201             : 
     202             : // Given a LOOP/TRY marker, returns its bottom BB. Use cached information if any
     203             : // to prevent recomputation.
     204             : MachineBasicBlock *
     205          77 : WebAssemblyCFGStackify::getBottom(const MachineInstr *Begin) {
     206          77 :   const auto &MLI = getAnalysis<MachineLoopInfo>();
     207          77 :   const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
     208         104 :   if (BeginToBottom.count(Begin))
     209          27 :     return BeginToBottom[Begin];
     210         100 :   if (Begin->getOpcode() == WebAssembly::LOOP) {
     211          34 :     MachineLoop *L = MLI.getLoopFor(Begin->getParent());
     212             :     assert(L);
     213          34 :     BeginToBottom[Begin] = WebAssembly::getBottom(L);
     214          16 :   } else if (Begin->getOpcode() == WebAssembly::TRY) {
     215          16 :     WebAssemblyException *WE = WEI.getExceptionFor(TryToEHPad[Begin]);
     216             :     assert(WE);
     217          16 :     BeginToBottom[Begin] = WebAssembly::getBottom(WE);
     218             :   } else
     219             :     assert(false);
     220          50 :   return BeginToBottom[Begin];
     221             : }
     222             : 
     223             : /// Insert a BLOCK marker for branches to MBB (if needed).
     224        3576 : void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
     225             :   // This should have been handled in placeTryMarker.
     226        3576 :   if (MBB.isEHPad())
     227        3336 :     return;
     228             : 
     229        3551 :   MachineFunction &MF = *MBB.getParent();
     230        3551 :   auto &MDT = getAnalysis<MachineDominatorTree>();
     231        3551 :   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
     232             :   const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
     233             : 
     234             :   // First compute the nearest common dominator of all forward non-fallthrough
     235             :   // predecessors so that we minimize the time that the BLOCK is on the stack,
     236             :   // which reduces overall stack height.
     237             :   MachineBasicBlock *Header = nullptr;
     238             :   bool IsBranchedTo = false;
     239        3551 :   int MBBNumber = MBB.getNumber();
     240        4325 :   for (MachineBasicBlock *Pred : MBB.predecessors()) {
     241         774 :     if (Pred->getNumber() < MBBNumber) {
     242         655 :       Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
     243         655 :       if (ExplicitlyBranchesTo(Pred, &MBB))
     244             :         IsBranchedTo = true;
     245             :     }
     246             :   }
     247        3551 :   if (!Header)
     248             :     return;
     249         552 :   if (!IsBranchedTo)
     250             :     return;
     251             : 
     252             :   assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
     253             :   MachineBasicBlock *LayoutPred = &*std::prev(MachineFunction::iterator(&MBB));
     254             : 
     255             :   // If the nearest common dominator is inside a more deeply nested context,
     256             :   // walk out to the nearest scope which isn't more deeply nested.
     257         485 :   for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
     258         652 :     if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
     259         116 :       if (ScopeTop->getNumber() > Header->getNumber()) {
     260             :         // Skip over an intervening scope.
     261             :         I = std::next(MachineFunction::iterator(ScopeTop));
     262             :       } else {
     263             :         // We found a scope level at an appropriate depth.
     264             :         Header = ScopeTop;
     265             :         break;
     266             :       }
     267             :     }
     268             :   }
     269             : 
     270             :   // Decide where in Header to put the BLOCK.
     271             : 
     272             :   // Instructions that should go before the BLOCK.
     273             :   SmallPtrSet<const MachineInstr *, 4> BeforeSet;
     274             :   // Instructions that should go after the BLOCK.
     275             :   SmallPtrSet<const MachineInstr *, 4> AfterSet;
     276        1875 :   for (const auto &MI : *Header) {
     277             :     // If there is a previously placed LOOP/TRY marker and the bottom block of
     278             :     // the loop/exception is above MBB, it should be after the BLOCK, because
     279             :     // the loop/exception is nested in this block. Otherwise it should be before
     280             :     // the BLOCK.
     281        3270 :     if (MI.getOpcode() == WebAssembly::LOOP ||
     282             :         MI.getOpcode() == WebAssembly::TRY) {
     283          77 :       if (MBB.getNumber() > getBottom(&MI)->getNumber())
     284          38 :         AfterSet.insert(&MI);
     285             : #ifndef NDEBUG
     286             :       else
     287             :         BeforeSet.insert(&MI);
     288             : #endif
     289             :     }
     290             : 
     291             :     // All previously inserted BLOCK markers should be after the BLOCK because
     292             :     // they are all nested blocks.
     293        3270 :     if (MI.getOpcode() == WebAssembly::BLOCK)
     294         135 :       AfterSet.insert(&MI);
     295             : 
     296             : #ifndef NDEBUG
     297             :     // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK.
     298             :     if (MI.getOpcode() == WebAssembly::END_BLOCK ||
     299             :         MI.getOpcode() == WebAssembly::END_LOOP ||
     300             :         MI.getOpcode() == WebAssembly::END_TRY)
     301             :       BeforeSet.insert(&MI);
     302             : #endif
     303             : 
     304             :     // Terminators should go after the BLOCK.
     305        1635 :     if (MI.isTerminator())
     306         238 :       AfterSet.insert(&MI);
     307             :   }
     308             : 
     309             :   // Local expression tree should go after the BLOCK.
     310         979 :   for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
     311             :        --I) {
     312        1397 :     if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
     313          15 :       continue;
     314         686 :     if (WebAssembly::isChild(*std::prev(I), MFI))
     315         484 :       AfterSet.insert(&*std::prev(I));
     316             :     else
     317             :       break;
     318             :   }
     319             : 
     320             :   // Add the BLOCK.
     321         240 :   auto InsertPos = GetLatestInsertPos(Header, BeforeSet, AfterSet);
     322             :   MachineInstr *Begin =
     323         240 :       BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
     324         240 :               TII.get(WebAssembly::BLOCK))
     325             :           .addImm(int64_t(WebAssembly::ExprType::Void));
     326             : 
     327             :   // Decide where in Header to put the END_BLOCK.
     328         240 :   BeforeSet.clear();
     329         240 :   AfterSet.clear();
     330         999 :   for (auto &MI : MBB) {
     331             : #ifndef NDEBUG
     332             :     // END_BLOCK should precede existing LOOP and TRY markers.
     333             :     if (MI.getOpcode() == WebAssembly::LOOP ||
     334             :         MI.getOpcode() == WebAssembly::TRY)
     335             :       AfterSet.insert(&MI);
     336             : #endif
     337             : 
     338             :     // If there is a previously placed END_LOOP marker and the header of the
     339             :     // loop is above this block's header, the END_LOOP should be placed after
     340             :     // the BLOCK, because the loop contains this block. Otherwise the END_LOOP
     341             :     // should be placed before the BLOCK. The same for END_TRY.
     342        1518 :     if (MI.getOpcode() == WebAssembly::END_LOOP ||
     343             :         MI.getOpcode() == WebAssembly::END_TRY) {
     344          46 :       if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
     345          45 :         BeforeSet.insert(&MI);
     346             : #ifndef NDEBUG
     347             :       else
     348             :         AfterSet.insert(&MI);
     349             : #endif
     350             :     }
     351             :   }
     352             : 
     353             :   // Mark the end of the block.
     354         240 :   InsertPos = GetEarliestInsertPos(&MBB, BeforeSet, AfterSet);
     355         480 :   MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
     356         240 :                               TII.get(WebAssembly::END_BLOCK));
     357         240 :   registerScope(Begin, End);
     358             : 
     359             :   // Track the farthest-spanning scope that ends at this point.
     360         240 :   int Number = MBB.getNumber();
     361         480 :   if (!ScopeTops[Number] ||
     362          43 :       ScopeTops[Number]->getNumber() > Header->getNumber())
     363         215 :     ScopeTops[Number] = Header;
     364             : }
     365             : 
     366             : /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
     367        3576 : void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
     368        3576 :   MachineFunction &MF = *MBB.getParent();
     369        3576 :   const auto &MLI = getAnalysis<MachineLoopInfo>();
     370        3576 :   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
     371             : 
     372             :   MachineLoop *Loop = MLI.getLoopFor(&MBB);
     373         168 :   if (!Loop || Loop->getHeader() != &MBB)
     374        3493 :     return;
     375             : 
     376             :   // The operand of a LOOP is the first block after the loop. If the loop is the
     377             :   // bottom of the function, insert a dummy block at the end.
     378             :   MachineBasicBlock *Bottom = WebAssembly::getBottom(Loop);
     379             :   auto Iter = std::next(MachineFunction::iterator(Bottom));
     380          83 :   if (Iter == MF.end()) {
     381          12 :     MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
     382             :     // Give it a fake predecessor so that AsmPrinter prints its label.
     383          12 :     Label->addSuccessor(Label);
     384             :     MF.push_back(Label);
     385             :     Iter = std::next(MachineFunction::iterator(Bottom));
     386             :   }
     387             :   MachineBasicBlock *AfterLoop = &*Iter;
     388             : 
     389             :   // Decide where in Header to put the LOOP.
     390             :   SmallPtrSet<const MachineInstr *, 4> BeforeSet;
     391             :   SmallPtrSet<const MachineInstr *, 4> AfterSet;
     392         615 :   for (const auto &MI : MBB) {
     393             :     // LOOP marker should be after any existing loop that ends here. Otherwise
     394             :     // we assume the instruction belongs to the loop.
     395        1064 :     if (MI.getOpcode() == WebAssembly::END_LOOP)
     396           0 :       BeforeSet.insert(&MI);
     397             : #ifndef NDEBUG
     398             :     else
     399             :       AfterSet.insert(&MI);
     400             : #endif
     401             :   }
     402             : 
     403             :   // Mark the beginning of the loop.
     404          83 :   auto InsertPos = GetEarliestInsertPos(&MBB, BeforeSet, AfterSet);
     405          83 :   MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),
     406          83 :                                 TII.get(WebAssembly::LOOP))
     407             :                             .addImm(int64_t(WebAssembly::ExprType::Void));
     408             : 
     409             :   // Decide where in Header to put the END_LOOP.
     410          83 :   BeforeSet.clear();
     411          83 :   AfterSet.clear();
     412             : #ifndef NDEBUG
     413             :   for (const auto &MI : MBB)
     414             :     // Existing END_LOOP markers belong to parent loops of this loop
     415             :     if (MI.getOpcode() == WebAssembly::END_LOOP)
     416             :       AfterSet.insert(&MI);
     417             : #endif
     418             : 
     419             :   // Mark the end of the loop (using arbitrary debug location that branched to
     420             :   // the loop end as its location).
     421          83 :   InsertPos = GetEarliestInsertPos(AfterLoop, BeforeSet, AfterSet);
     422          83 :   DebugLoc EndDL = (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
     423             :   MachineInstr *End =
     424         166 :       BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP));
     425          83 :   registerScope(Begin, End);
     426             : 
     427             :   assert((!ScopeTops[AfterLoop->getNumber()] ||
     428             :           ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
     429             :          "With block sorting the outermost loop for a block should be first.");
     430         166 :   if (!ScopeTops[AfterLoop->getNumber()])
     431          81 :     ScopeTops[AfterLoop->getNumber()] = &MBB;
     432             : }
     433             : 
     434          82 : void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
     435          82 :   if (!MBB.isEHPad())
     436          59 :     return;
     437             : 
     438             :   // catch_all terminate pad is grouped together with catch terminate pad and
     439             :   // does not need a separate TRY and END_TRY marker.
     440          25 :   if (WebAssembly::isCatchAllTerminatePad(MBB))
     441             :     return;
     442             : 
     443          23 :   MachineFunction &MF = *MBB.getParent();
     444          23 :   auto &MDT = getAnalysis<MachineDominatorTree>();
     445          23 :   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
     446          23 :   const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
     447             :   const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
     448             : 
     449             :   // Compute the nearest common dominator of all unwind predecessors
     450             :   MachineBasicBlock *Header = nullptr;
     451          23 :   int MBBNumber = MBB.getNumber();
     452          53 :   for (auto *Pred : MBB.predecessors()) {
     453          30 :     if (Pred->getNumber() < MBBNumber) {
     454          30 :       Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
     455             :       assert(!ExplicitlyBranchesTo(Pred, &MBB) &&
     456             :              "Explicit branch to an EH pad!");
     457             :     }
     458             :   }
     459          23 :   if (!Header)
     460             :     return;
     461             : 
     462             :   // If this try is at the bottom of the function, insert a dummy block at the
     463             :   // end.
     464             :   WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
     465             :   assert(WE);
     466             :   MachineBasicBlock *Bottom = WebAssembly::getBottom(WE);
     467             : 
     468             :   auto Iter = std::next(MachineFunction::iterator(Bottom));
     469          23 :   if (Iter == MF.end()) {
     470           0 :     MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
     471             :     // Give it a fake predecessor so that AsmPrinter prints its label.
     472           0 :     Label->addSuccessor(Label);
     473             :     MF.push_back(Label);
     474             :     Iter = std::next(MachineFunction::iterator(Bottom));
     475             :   }
     476             :   MachineBasicBlock *AfterTry = &*Iter;
     477             : 
     478             :   assert(AfterTry != &MF.front());
     479             :   MachineBasicBlock *LayoutPred =
     480             :       &*std::prev(MachineFunction::iterator(AfterTry));
     481             : 
     482             :   // If the nearest common dominator is inside a more deeply nested context,
     483             :   // walk out to the nearest scope which isn't more deeply nested.
     484          92 :   for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
     485         148 :     if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
     486           6 :       if (ScopeTop->getNumber() > Header->getNumber()) {
     487             :         // Skip over an intervening scope.
     488             :         I = std::next(MachineFunction::iterator(ScopeTop));
     489             :       } else {
     490             :         // We found a scope level at an appropriate depth.
     491             :         Header = ScopeTop;
     492             :         break;
     493             :       }
     494             :     }
     495             :   }
     496             : 
     497             :   // Decide where in Header to put the TRY.
     498             : 
     499             :   // Instructions that should go before the BLOCK.
     500             :   SmallPtrSet<const MachineInstr *, 4> BeforeSet;
     501             :   // Instructions that should go after the BLOCK.
     502             :   SmallPtrSet<const MachineInstr *, 4> AfterSet;
     503         167 :   for (const auto &MI : *Header) {
     504             :     // If there is a previously placed LOOP marker and the bottom block of
     505             :     // the loop is above MBB, the LOOP should be after the TRY, because the
     506             :     // loop is nested in this try. Otherwise it should be before the TRY.
     507         288 :     if (MI.getOpcode() == WebAssembly::LOOP) {
     508           1 :       if (MBB.getNumber() > Bottom->getNumber())
     509           0 :         AfterSet.insert(&MI);
     510             : #ifndef NDEBUG
     511             :       else
     512             :         BeforeSet.insert(&MI);
     513             : #endif
     514             :     }
     515             : 
     516             :     // All previously inserted TRY markers should be after the TRY because they
     517             :     // are all nested trys.
     518         288 :     if (MI.getOpcode() == WebAssembly::TRY)
     519           8 :       AfterSet.insert(&MI);
     520             : 
     521             : #ifndef NDEBUG
     522             :     // All END_(LOOP/TRY) markers should be before the TRY.
     523             :     if (MI.getOpcode() == WebAssembly::END_LOOP ||
     524             :         MI.getOpcode() == WebAssembly::END_TRY)
     525             :       BeforeSet.insert(&MI);
     526             : #endif
     527             : 
     528             :     // Terminators should go after the TRY.
     529         144 :     if (MI.isTerminator())
     530          23 :       AfterSet.insert(&MI);
     531             :   }
     532             : 
     533             :   // Local expression tree should go after the TRY.
     534          63 :   for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
     535             :        --I) {
     536          80 :     if (std::prev(I)->isDebugInstr() || std::prev(I)->isPosition())
     537          17 :       continue;
     538          23 :     if (WebAssembly::isChild(*std::prev(I), MFI))
     539           0 :       AfterSet.insert(&*std::prev(I));
     540             :     else
     541             :       break;
     542             :   }
     543             : 
     544             :   // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
     545             :   // contain the call within it. So the call should go after the TRY. The
     546             :   // exception is when the header's terminator is a rethrow instruction, in
     547             :   // which case that instruction, not a call instruction before it, is gonna
     548             :   // throw.
     549          23 :   if (MBB.isPredecessor(Header)) {
     550          20 :     auto TermPos = Header->getFirstTerminator();
     551          20 :     if (TermPos == Header->end() || !WebAssembly::isRethrow(*TermPos)) {
     552          54 :       for (const auto &MI : reverse(*Header)) {
     553          54 :         if (MI.isCall()) {
     554          20 :           AfterSet.insert(&MI);
     555          20 :           break;
     556             :         }
     557             :       }
     558             :     }
     559             :   }
     560             : 
     561             :   // Add the TRY.
     562          23 :   auto InsertPos = GetLatestInsertPos(Header, BeforeSet, AfterSet);
     563             :   MachineInstr *Begin =
     564          23 :       BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
     565          23 :               TII.get(WebAssembly::TRY))
     566             :           .addImm(int64_t(WebAssembly::ExprType::Void));
     567             : 
     568             :   // Decide where in Header to put the END_TRY.
     569          23 :   BeforeSet.clear();
     570          23 :   AfterSet.clear();
     571         108 :   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         170 :     if (MI.getOpcode() == WebAssembly::END_LOOP) {
     588           1 :       if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
     589           1 :         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          23 :   InsertPos = GetEarliestInsertPos(AfterTry, BeforeSet, AfterSet);
     599             :   MachineInstr *End =
     600          23 :       BuildMI(*AfterTry, InsertPos, Bottom->findBranchDebugLoc(),
     601          23 :               TII.get(WebAssembly::END_TRY));
     602          23 :   registerTryScope(Begin, End, &MBB);
     603             : 
     604             :   // Track the farthest-spanning scope that ends at this point.
     605          23 :   int Number = AfterTry->getNumber();
     606          46 :   if (!ScopeTops[Number] ||
     607           1 :       ScopeTops[Number]->getNumber() > Header->getNumber())
     608          23 :     ScopeTops[Number] = Header;
     609             : }
     610             : 
     611             : static unsigned
     612             : GetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack,
     613             :          const MachineBasicBlock *MBB) {
     614             :   unsigned Depth = 0;
     615         697 :   for (auto X : reverse(Stack)) {
     616         697 :     if (X == MBB)
     617             :       break;
     618         270 :     ++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        2987 : void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
     632             :   const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
     633             :   assert(MFI.getResults().size() <= 1);
     634             : 
     635        2987 :   if (MFI.getResults().empty())
     636             :     return;
     637             : 
     638             :   WebAssembly::ExprType retType;
     639        1890 :   switch (MFI.getResults().front().SimpleTy) {
     640             :   case MVT::i32:
     641             :     retType = WebAssembly::ExprType::I32;
     642             :     break;
     643         215 :   case MVT::i64:
     644             :     retType = WebAssembly::ExprType::I64;
     645         215 :     break;
     646          59 :   case MVT::f32:
     647             :     retType = WebAssembly::ExprType::F32;
     648          59 :     break;
     649          55 :   case MVT::f64:
     650             :     retType = WebAssembly::ExprType::F64;
     651          55 :     break;
     652         782 :   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         782 :     break;
     660           0 :   case MVT::ExceptRef:
     661             :     retType = WebAssembly::ExprType::ExceptRef;
     662           0 :     break;
     663           0 :   default:
     664           0 :     llvm_unreachable("unexpected return type");
     665             :   }
     666             : 
     667        1896 :   for (MachineBasicBlock &MBB : reverse(MF)) {
     668        1902 :     for (MachineInstr &MI : reverse(MBB)) {
     669             :       if (MI.isPosition() || MI.isDebugInstr())
     670             :         continue;
     671        1896 :       if (MI.getOpcode() == WebAssembly::END_BLOCK) {
     672           0 :         EndToBegin[&MI]->getOperand(0).setImm(int32_t(retType));
     673           0 :         continue;
     674             :       }
     675        1896 :       if (MI.getOpcode() == WebAssembly::END_LOOP) {
     676           6 :         EndToBegin[&MI]->getOperand(0).setImm(int32_t(retType));
     677           6 :         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.
     687        2987 : static void AppendEndToFunction(MachineFunction &MF,
     688             :                                 const WebAssemblyInstrInfo &TII) {
     689             :   BuildMI(MF.back(), MF.back().end(),
     690        2987 :           MF.back().findPrevDebugLoc(MF.back().end()),
     691        2987 :           TII.get(WebAssembly::END_FUNCTION));
     692        2987 : }
     693             : 
     694             : /// Insert LOOP/TRY/BLOCK markers at appropriate places.
     695        2987 : void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
     696        2987 :   const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
     697             :   // We allocate one more than the number of blocks in the function to
     698             :   // accommodate for the possible fake block we may insert at the end.
     699        5974 :   ScopeTops.resize(MF.getNumBlockIDs() + 1);
     700             :   // Place the LOOP for MBB if MBB is the header of a loop.
     701        6563 :   for (auto &MBB : MF)
     702        3576 :     placeLoopMarker(MBB);
     703             :   // Place the TRY for MBB if MBB is the EH pad of an exception.
     704        2987 :   if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
     705          13 :       MF.getFunction().hasPersonalityFn())
     706          94 :     for (auto &MBB : MF)
     707          82 :       placeTryMarker(MBB);
     708             :   // Place the BLOCK for MBB if MBB is branched to from above.
     709        6563 :   for (auto &MBB : MF)
     710        3576 :     placeBlockMarker(MBB);
     711        2987 : }
     712             : 
     713        2987 : void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
     714        2987 :   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
     715             :   // Now rewrite references to basic blocks to be depth immediates.
     716             :   // We need two stacks: one for normal scopes and the other for EH pad scopes.
     717             :   // EH pad stack is used to rewrite depths in rethrow instructions.
     718             :   SmallVector<const MachineBasicBlock *, 8> Stack;
     719             :   SmallVector<const MachineBasicBlock *, 8> EHPadStack;
     720        6563 :   for (auto &MBB : reverse(MF)) {
     721       32407 :     for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) {
     722             :       MachineInstr &MI = *I;
     723       57662 :       switch (MI.getOpcode()) {
     724             :       case WebAssembly::BLOCK:
     725             :         assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
     726             :                    MBB.getNumber() &&
     727             :                "Block/try should be balanced");
     728             :         Stack.pop_back();
     729             :         break;
     730             : 
     731             :       case WebAssembly::TRY:
     732             :         assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
     733             :                    MBB.getNumber() &&
     734             :                "Block/try marker should be balanced");
     735             :         Stack.pop_back();
     736             :         EHPadStack.pop_back();
     737             :         break;
     738             : 
     739          25 :       case WebAssembly::CATCH_I32:
     740             :       case WebAssembly::CATCH_I64:
     741             :       case WebAssembly::CATCH_ALL:
     742          25 :         EHPadStack.push_back(&MBB);
     743          25 :         break;
     744             : 
     745             :       case WebAssembly::LOOP:
     746             :         assert(Stack.back() == &MBB && "Loop top should be balanced");
     747             :         Stack.pop_back();
     748             :         break;
     749             : 
     750         263 :       case WebAssembly::END_BLOCK:
     751             :       case WebAssembly::END_TRY:
     752         263 :         Stack.push_back(&MBB);
     753         263 :         break;
     754             : 
     755          83 :       case WebAssembly::END_LOOP:
     756          83 :         Stack.push_back(EndToBegin[&MI]->getParent());
     757          83 :         break;
     758             : 
     759           4 :       case WebAssembly::RETHROW: {
     760             :         // Rewrite MBB operands to be depth immediates.
     761           4 :         unsigned EHPadDepth = GetDepth(EHPadStack, MI.getOperand(0).getMBB());
     762           4 :         MI.RemoveOperand(0);
     763           8 :         MI.addOperand(MF, MachineOperand::CreateImm(EHPadDepth));
     764           4 :         break;
     765             :       }
     766             : 
     767          11 :       case WebAssembly::RETHROW_TO_CALLER: {
     768             :         MachineInstr *Rethrow =
     769          22 :             BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(WebAssembly::RETHROW))
     770          11 :                 .addImm(Stack.size());
     771          11 :         MI.eraseFromParent();
     772             :         I = MachineBasicBlock::reverse_iterator(Rethrow);
     773          11 :         break;
     774             :       }
     775             : 
     776             :       default:
     777       28099 :         if (MI.isTerminator()) {
     778             :           // Rewrite MBB operands to be depth immediates.
     779             :           SmallVector<MachineOperand, 4> Ops(MI.operands());
     780       13179 :           while (MI.getNumOperands() > 0)
     781        9732 :             MI.RemoveOperand(MI.getNumOperands() - 1);
     782       13179 :           for (auto MO : Ops) {
     783        9732 :             if (MO.isMBB())
     784         846 :               MO = MachineOperand::CreateImm(GetDepth(Stack, MO.getMBB()));
     785        9732 :             MI.addOperand(MF, MO);
     786             :           }
     787             :         }
     788             :         break;
     789             :       }
     790             :     }
     791             :   }
     792             :   assert(Stack.empty() && "Control flow should be balanced");
     793        2987 : }
     794             : 
     795        6275 : void WebAssemblyCFGStackify::releaseMemory() {
     796             :   ScopeTops.clear();
     797        6275 :   BeginToEnd.clear();
     798        6275 :   EndToBegin.clear();
     799        6275 :   TryToEHPad.clear();
     800        6275 :   EHPadToTry.clear();
     801        6275 :   BeginToBottom.clear();
     802        6275 : }
     803             : 
     804        2987 : bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
     805             :   LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
     806             :                        "********** Function: "
     807             :                     << MF.getName() << '\n');
     808             : 
     809        2987 :   releaseMemory();
     810             : 
     811             :   // Liveness is not tracked for VALUE_STACK physreg.
     812        2987 :   MF.getRegInfo().invalidateLiveness();
     813             : 
     814             :   // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
     815        2987 :   placeMarkers(MF);
     816             : 
     817             :   // Convert MBB operands in terminators to relative depth immediates.
     818        2987 :   rewriteDepthImmediates(MF);
     819             : 
     820             :   // Fix up block/loop/try signatures at the end of the function to conform to
     821             :   // WebAssembly's rules.
     822        2987 :   fixEndsAtEndOfFunction(MF);
     823             : 
     824             :   // Add an end instruction at the end of the function body.
     825        2987 :   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
     826        2987 :   if (!MF.getSubtarget<WebAssemblySubtarget>()
     827             :            .getTargetTriple()
     828             :            .isOSBinFormatELF())
     829        2987 :     AppendEndToFunction(MF, TII);
     830             : 
     831        2987 :   return true;
     832             : }

Generated by: LCOV version 1.13