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