lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

   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 "MCTargetDesc/WebAssemblyMCTargetDesc.h"
  25 #include "WebAssembly.h"
  26 #include "WebAssemblyExceptionInfo.h"
  27 #include "WebAssemblyMachineFunctionInfo.h"
  28 #include "WebAssemblySubtarget.h"
  29 #include "WebAssemblyUtilities.h"
  30 #include "llvm/CodeGen/MachineDominators.h"
  31 #include "llvm/CodeGen/MachineFunction.h"
  32 #include "llvm/CodeGen/MachineInstrBuilder.h"
  33 #include "llvm/CodeGen/MachineLoopInfo.h"
  34 #include "llvm/CodeGen/MachineRegisterInfo.h"
  35 #include "llvm/CodeGen/Passes.h"
  36 #include "llvm/CodeGen/WasmEHFuncInfo.h"
  37 #include "llvm/MC/MCAsmInfo.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/raw_ostream.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 {
  50     AU.addRequired<MachineDominatorTree>();
  51     AU.addRequired<MachineLoopInfo>();
  52     AU.addRequired<WebAssemblyExceptionInfo>();
  53     MachineFunctionPass::getAnalysisUsage(AU);
  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.
  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 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
  87   MachineBasicBlock *getBottom(const MachineInstr *Begin);
  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
  97 char WebAssemblyCFGStackify::ID = 0;
  98 INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,
  99                 "Insert BLOCK and LOOP markers for WebAssembly scopes", false,
 100                 false)
 101
 102 FunctionPass *llvm::createWebAssemblyCFGStackify() {
 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.
 111 static bool explicitlyBranchesTo(MachineBasicBlock *Pred,
 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.
 125 static MachineBasicBlock::iterator
 126 getEarliestInsertPos(MachineBasicBlock *MBB,
 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.
 149 static MachineBasicBlock::iterator
 150 getLatestInsertPos(MachineBasicBlock *MBB,
 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.
 184 MachineBasicBlock *
 185 WebAssemblyCFGStackify::getBottom(const MachineInstr *Begin) {
 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.
 261   SmallPtrSet<const MachineInstr *, 4> BeforeSet;
 262   // Instructions that should go after the BLOCK.
 263   SmallPtrSet<const MachineInstr *, 4> AfterSet;
 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
 317   WebAssembly::ExprType ReturnType = WebAssembly::ExprType::Void;
 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.
 382   MachineBasicBlock *Bottom = WebAssembly::getBottom(Loop);
 383   auto Iter = std::next(MachineFunction::iterator(Bottom));
 384   if (Iter == MF.end()) {
 385     MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
 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.
 394   SmallPtrSet<const MachineInstr *, 4> BeforeSet;
 395   SmallPtrSet<const MachineInstr *, 4> AfterSet;
 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);
 465   MachineBasicBlock *Bottom = WebAssembly::getBottom(WE);
 466
 467   auto Iter = std::next(MachineFunction::iterator(Bottom));
 468   if (Iter == MF.end()) {
 469     MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
 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.
 499   SmallPtrSet<const MachineInstr *, 4> BeforeSet;
 500   // Instructions that should go after the BLOCK.
 501   SmallPtrSet<const MachineInstr *, 4> AfterSet;
 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
 612 getDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack,
 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:
 661     RetType = WebAssembly::ExprType::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.
 687 static void appendEndToFunction(MachineFunction &MF,
 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();
 704   if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
 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.
 715   SmallVector<const MachineBasicBlock *, 8> Stack;
 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
 739       case WebAssembly::END_BLOCK:
 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.
 751           SmallVector<MachineOperand, 4> Ops(MI.operands());
 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.
 784   MF.getRegInfo().invalidateLiveness();
 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();
 798   if (!MF.getSubtarget<WebAssemblySubtarget>()
 799            .getTargetTriple()
 800            .isOSBinFormatELF())
 801     appendEndToFunction(MF, TII);
 802
 803   return true;
 804 }