[WebAssembly] CFG sort support for exception handling

[aheejin]

Summary

This patch extends CFGSort pass to support exception handling. Once it
places a loop header, it does not place blocks that are not dominated by
the loop header until all the loop blocks are sorted. This patch extends
the same algorithm to exception 'catch' part, using the information
calculated by WebAssemblyExceptionInfo class.

[aheejin]

• Delete debugging code

[aheejin]

• clang-tidy

[aheejin]

test fixes

[aheejin]

• clang-format

[aheejin]

• Use unique_ptr for containers and delete destructors
• Make wasm.get.exception/ehselector intrinsic take a token argument

[aheejin]

• rebase

[dschuff]

This change is really quite nice and minimal other than the renaming.

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

41

'SortUnit' to me implies that this is a thing that is being sorted, i.e. compared against other units, which isn't correct. What about if we called this a 'Region'?

204

Even when comparing backwards? I don't quite understand why this shouldn't just be the inverse of forward comparison.

[aheejin]

• SortUnit -> Region

[aheejin]

• More unit -> region

[aheejin]

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

204

For some reason I don't fully understand, for Ready list later BBs are selected first. But my intention here is no matter whether the list is Preferred (which uses CompareBlockNumbers) or Ready (which uses CompareBlockNumbersBackwards), whenever we have an EH pad ready, we want to pick it first.

So CompareBlockNumbersBackwards doesn't mean its results will be used in the reverse direction. Regardless of the comparison function, a BB indicated by the function as having higher priority is placed before when sorting.

[dschuff]

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

85

We could also assert that ML and WE aren't both set.

204

OK. This whole bit with the comparison functions still seems a little awkward to me though. At the very least there should be a comment here saying something about the usage or why it's not just the inverse of the above (especially since the name seems to imply that it is). Or maybe it just needs a better name?

Perhaps @sunfish knows why the queues sort in the opposite directions.

Or, stepping back, more, would it make more sense to just have separate queue (alongside Preferred and Ready) for EH pads? Preferred and Ready are basically 2 different priority classes, and we are now adding a third, but we are handling its prioritization differently from the other 2.

[sunfish]

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

14–16

This "and" should be "or".

70

Could you add a comment for this class that briefly describes its purpose? Do I understand correctly that this is essentially the SortUnit analog of what LoopInfo is for loops?

204

It was an early attempt at balancing two concerns: preserving the original code layout to the extent possible, while also keeping contiguous sequences contiguous. It worked on some simple testcases. It's probably not optimal.

[aheejin]

• Address comments
• Add +mattr=exception-handling flag

[aheejin]

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

70

Yes that's what it is. And I renamed them to Region and RegionInfo per @dschuff's suggestion.

85

They can be both set. In that case we return the smaller one.

204

@dschuff Let me clarify a bit. You can think of those two queue as just queue Alpha and queue Beta or something. Here they happen to be CompareBlockNumbersForward and CompareBlockNumbersBackward and they sound like they have some opposite relationship and thus confusing, but they are just different ways to pick a block. What I want is, I want to impose a universal rule of "pick an EH pad first whenever it is available" for all queues available. So why the queues sort in the opposite direction doesn't really matter. And also having a separate queue for EH pads wouldn't do what I want (I want impose a universal rule for all queues, as I said). If we make this as a separate queue, it is unclear how we should modify the logic itself to figure out when we should switch to this specific queue.

For comment-wise, I'm not sure what I should add more to what's already there. Should I add what I described here?

[aheejin]

@dschuff I added some more clarification to your questions. PTAL

[aheejin]

ping

[aheejin]

@dschuff ping

[dschuff]

LGTM With those changes.

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

204

Maybe the long comment about EH pad handling could go outside both comparators, and it could note that EH pads are selected first regardless of the block comparison order. I also actually think that changing the name to CompareBlockNumbersAndEHPad doesn't really make them more understandable, and I'd probably just leave the names the same (while keeping the comments).

255

Could also add one note here like 'EH blocks are picked first from both queues.'

[aheejin]

Address comments

lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

 //===-- WebAssemblyCFGSort.cpp - CFG Sorting ------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file implements a CFG sorting pass.
 ///
 /// This pass reorders the blocks in a function to put them into topological
-/// order, ignoring loop backedges, and without any loop being interrupted
-/// by a block not dominated by the loop header, with special care to keep the
-/// order as similar as possible to the original order.
+/// order, ignoring loop backedges, and without any loop and exception being
+/// interrupted by a block not dominated by the its header, with special care
+/// to keep the order as similar as possible to the original order.
 ///
 ////===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssembly.h"
+#include "WebAssemblyExceptionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyUtilities.h"
 #include "llvm/ADT/PriorityQueue.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "wasm-cfg-sort"
 
 namespace {
+
+// Wrapper for loops and exceptions
+class SortUnit {
+public:
+  virtual ~SortUnit() {}
+  virtual MachineBasicBlock *getHeader() const = 0;
+  virtual bool contains(const MachineBasicBlock *MBB) const = 0;
+  virtual unsigned getNumBlocks() const = 0;
+  typedef typename ArrayRef<MachineBasicBlock *>::const_iterator block_iterator;
+  virtual iterator_range<block_iterator> blocks() const = 0;
+  virtual bool isLoop() const = 0;
+};
+
+template <typename T> class ConcreteSortUnit : public SortUnit {
+  const T *Unit;
+
+public:
+  ConcreteSortUnit(const T *Unit) : Unit(Unit) {}
+  MachineBasicBlock *getHeader() const { return Unit->getHeader(); }
+  bool contains(const MachineBasicBlock *MBB) const {
+    return Unit->contains(MBB);
+  }
+  unsigned getNumBlocks() const { return Unit->getNumBlocks(); }
+  iterator_range<block_iterator> blocks() const { return Unit->blocks(); }
+  bool isLoop() const { return false; }
+};
+
+template <> bool ConcreteSortUnit<MachineLoop>::isLoop() const { return true; }
+
+class SortUnitInfo {
+  const MachineLoopInfo &MLI;
+  const WebAssemblyExceptionInfo &WEI;
+  std::vector<const SortUnit *> Units;
+  DenseMap<const MachineLoop *, const SortUnit *> LoopMap;
+  DenseMap<const WebAssemblyException *, const SortUnit *> ExceptionMap;
+
+public:
+  SortUnitInfo(const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI)
+      : MLI(MLI), WEI(WEI) {}
+  ~SortUnitInfo() {
+    for (const auto &KV : LoopMap)
+      delete KV.second;
+    for (const auto &KV : ExceptionMap)
+      delete KV.second;
+  }
+
+  // Returns a smallest loop or exception that contains MBB
+  const SortUnit *getSortUnitFor(const MachineBasicBlock *MBB) {
+    const auto *ML = MLI.getLoopFor(MBB);
+    const auto *WE = WEI.getExceptionFor(MBB);
+    if (!ML && !WE)
+      return nullptr;
+    if ((ML && !WE) || (ML && WE && ML->getNumBlocks() < WE->getNumBlocks())) {
+      // If the smallest unit containing MBB is a loop
+      if (LoopMap.count(ML))
+        return LoopMap[ML];
+      const SortUnit *SU = new ConcreteSortUnit<MachineLoop>(ML);
+      LoopMap[ML] = SU;
+      return SU;
+    } else {
+      // If the smallest unit containing MBB is an exception
+      if (ExceptionMap.count(WE))
+        return ExceptionMap[WE];
+      const SortUnit *SU = new ConcreteSortUnit<WebAssemblyException>(WE);
+      ExceptionMap[WE] = SU;
+      return SU;
+    }
+  }
+};
+
 class WebAssemblyCFGSort final : public MachineFunctionPass {
   StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<MachineDominatorTree>();
     AU.addPreserved<MachineDominatorTree>();
     AU.addRequired<MachineLoopInfo>();
     AU.addPreserved<MachineLoopInfo>();
+    AU.addRequired<WebAssemblyExceptionInfo>();
+    AU.addPreserved<WebAssemblyExceptionInfo>();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
 public:
   static char ID; // Pass identification, replacement for typeid
   WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
#endif
   assert((AnyBarrier || AllAnalyzable) &&
          "AnalyzeBranch needs to analyze any block with a fallthrough");
   if (AllAnalyzable)
     MBB->updateTerminator();
 }
 
 namespace {
 /// Sort blocks by their number.
-struct CompareBlockNumbers {
+struct CompareBlockNumbersAndEHPad {
   bool operator()(const MachineBasicBlock *A,
                   const MachineBasicBlock *B) const {
+    // When only one of the BBs is an EH pad, we give a higher priority to it,
+    // to prevent common mismatches between possibly throwing calls and ehpads
+    // they unwind to, as in the example below:
+    //
+    // bb0:
+    //   call @foo      // If this throws, unwind to bb2
+    // bb1:
+    //   call @bar      // If this throws, unwind to bb3
+    // bb2 (ehpad):
+    //   handler_bb2
+    // bb3 (ehpad):
+    //   handler_bb3
+    // continuing code
+    //
+    // Because this pass tries to preserve the original BB order, this order
+    // will not change. But this will result in this try-catch structure in
+    // CFGStackify, resulting in a mismatch:
+    // try
+    //   try
+    //     call @foo
+    //     call @bar    // This should unwind to bb3, not bb2!
+    //   catch
+    //     handler_bb2
+    //   end
+    // catch
+    //   handler_bb3
+    // end
+    // continuing code
+    //
+    // If we give a higher priority to an EH pad whenever it is ready in this
+    // example, when both bb1 and bb2 are ready, we would pick up bb2 first.
+    if (A->isEHPad() && !B->isEHPad())
+      return false;
+    if (!A->isEHPad() && B->isEHPad())
+      return true;
+
     return A->getNumber() > B->getNumber();
   }
 };
 /// Sort blocks by their number in the opposite order..
-struct CompareBlockNumbersBackwards {
+struct CompareBlockNumbersBackwardsAndEHPad {
   bool operator()(const MachineBasicBlock *A,
                   const MachineBasicBlock *B) const {
+    // We give a higher priority to an EH pad
+    if (A->isEHPad() && !B->isEHPad())
+      return false;
+    if (!A->isEHPad() && B->isEHPad())
+      return true;
+
     return A->getNumber() < B->getNumber();
   }
 };
-/// Bookkeeping for a loop to help ensure that we don't mix blocks not dominated
-/// by the loop header among the loop's blocks.
+/// Bookkeeping for a sort unit to help ensure that we don't mix blocks not
+/// dominated by the its header among its blocks.
 struct Entry {
-  const MachineLoop *Loop;
+  const SortUnit *Unit;
   unsigned NumBlocksLeft;
 
   /// List of blocks not dominated by Loop's header that are deferred until
   /// after all of Loop's blocks have been seen.
   std::vector<MachineBasicBlock *> Deferred;
 
-  explicit Entry(const MachineLoop *L)
-      : Loop(L), NumBlocksLeft(L->getNumBlocks()) {}
+  explicit Entry(const SortUnit *U)
+      : Unit(U), NumBlocksLeft(U->getNumBlocks()) {}
 };
 } // end anonymous namespace
 
-/// Sort the blocks, taking special care to make sure that loops are not
+/// Sort the blocks, taking special care to make sure that sort units are not
 /// interrupted by blocks not dominated by their header.
 /// TODO: There are many opportunities for improving the heuristics here.
 /// Explore them.
 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
+                       const WebAssemblyExceptionInfo &WEI,
                        const MachineDominatorTree &MDT) {
   // Prepare for a topological sort: Record the number of predecessors each
   // block has, ignoring loop backedges.
   MF.RenumberBlocks();
   SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
   for (MachineBasicBlock &MBB : MF) {
     unsigned N = MBB.pred_size();
     if (MachineLoop *L = MLI.getLoopFor(&MBB))
       if (L->getHeader() == &MBB)
         for (const MachineBasicBlock *Pred : MBB.predecessors())
           if (L->contains(Pred))
             --N;
     NumPredsLeft[MBB.getNumber()] = N;
   }
 
   // Topological sort the CFG, with additional constraints:
-  //  - Between a loop header and the last block in the loop, there can be
-  //    no blocks not dominated by the loop header.
+  //  - Between a sort unit header and the last block in the sort unit, there
+  //    can be no blocks not dominated by its header.
   //  - It's desirable to preserve the original block order when possible.
   // We use two ready lists; Preferred and Ready. Preferred has recently
   // processed successors, to help preserve block sequences from the original
   // order. Ready has the remaining ready blocks.
   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
-                CompareBlockNumbers>
+                CompareBlockNumbersAndEHPad>
       Preferred;
   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
-                CompareBlockNumbersBackwards>
+                CompareBlockNumbersBackwardsAndEHPad>
       Ready;
-  SmallVector<Entry, 4> Loops;
+
+  SortUnitInfo SUI(MLI, WEI);
+  SmallVector<Entry, 4> Entries;
   for (MachineBasicBlock *MBB = &MF.front();;) {
-    const MachineLoop *L = MLI.getLoopFor(MBB);
-    if (L) {
-      // If MBB is a loop header, add it to the active loop list. We can't put
-      // any blocks that it doesn't dominate until we see the end of the loop.
-      if (L->getHeader() == MBB)
-        Loops.push_back(Entry(L));
-      // For each active loop the block is in, decrement the count. If MBB is
-      // the last block in an active loop, take it off the list and pick up any
-      // blocks deferred because the header didn't dominate them.
-      for (Entry &E : Loops)
-        if (E.Loop->contains(MBB) && --E.NumBlocksLeft == 0)
+    const SortUnit *U = SUI.getSortUnitFor(MBB);
+    if (U) {
+      // If MBB is a sort unit header, add it to the active sort unit list. We
+      // can't put any blocks that it doesn't dominate until we see the end of
+      // the sort unit.
+      if (U->getHeader() == MBB)
+        Entries.push_back(Entry(U));
+      // For each active sort unit the block is in, decrement the count. If MBB
+      // is the last block in an active sort unit, take it off the list and pick
+      // up any blocks deferred because the header didn't dominate them.
+      for (Entry &E : Entries)
+        if (E.Unit->contains(MBB) && --E.NumBlocksLeft == 0)
           for (auto DeferredBlock : E.Deferred)
             Ready.push(DeferredBlock);
-      while (!Loops.empty() && Loops.back().NumBlocksLeft == 0)
-        Loops.pop_back();
+      while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)
+        Entries.pop_back();
     }
     // The main topological sort logic.
     for (MachineBasicBlock *Succ : MBB->successors()) {
       // Ignore backedges.
       if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
         if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
           continue;
       // Decrement the predecessor count. If it's now zero, it's ready.
       if (--NumPredsLeft[Succ->getNumber()] == 0)
         Preferred.push(Succ);
     }
     // Determine the block to follow MBB. First try to find a preferred block,
     // to preserve the original block order when possible.
     MachineBasicBlock *Next = nullptr;
     while (!Preferred.empty()) {
       Next = Preferred.top();
       Preferred.pop();
-      // If X isn't dominated by the top active loop header, defer it until that
-      // loop is done.
-      if (!Loops.empty() &&
-          !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
-        Loops.back().Deferred.push_back(Next);
+      // If X isn't dominated by the top active sort unit header, defer it until
+      // that unit is done.
+      if (!Entries.empty() &&
+          !MDT.dominates(Entries.back().Unit->getHeader(), Next)) {
+        Entries.back().Deferred.push_back(Next);
         Next = nullptr;
         continue;
       }
       // If Next was originally ordered before MBB, and it isn't because it was
       // loop-rotated above the header, it's not preferred.
       if (Next->getNumber() < MBB->getNumber() &&
-          (!L || !L->contains(Next) ||
-           L->getHeader()->getNumber() < Next->getNumber())) {
+          (!U || !U->contains(Next) ||
+           U->getHeader()->getNumber() < Next->getNumber())) {
         Ready.push(Next);
         Next = nullptr;
         continue;
       }
       break;
     }
     // If we didn't find a suitable block in the Preferred list, check the
     // general Ready list.
     if (!Next) {
       // If there are no more blocks to process, we're done.
       if (Ready.empty()) {
         MaybeUpdateTerminator(MBB);
         break;
       }
       for (;;) {
         Next = Ready.top();
         Ready.pop();
-        // If Next isn't dominated by the top active loop header, defer it until
-        // that loop is done.
-        if (!Loops.empty() &&
-            !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
-          Loops.back().Deferred.push_back(Next);
+        // If Next isn't dominated by the top active sort unit header, defer it
+        // until that unit is done.
+        if (!Entries.empty() &&
+            !MDT.dominates(Entries.back().Unit->getHeader(), Next)) {
+          Entries.back().Deferred.push_back(Next);
           continue;
         }
         break;
       }
     }
     // Move the next block into place and iterate.
     Next->moveAfter(MBB);
     MaybeUpdateTerminator(MBB);
     MBB = Next;
   }
-  assert(Loops.empty() && "Active loop list not finished");
+  assert(Entries.empty() && "Active sort unit list not finished");
   MF.RenumberBlocks();
 
 #ifndef NDEBUG
-  SmallSetVector<MachineLoop *, 8> OnStack;
+  SmallSetVector<const SortUnit *, 8> OnStack;
 
   // Insert a sentinel representing the degenerate loop that starts at the
   // function entry block and includes the entire function as a "loop" that
   // executes once.
   OnStack.insert(nullptr);
 
   for (auto &MBB : MF) {
     assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
+    const SortUnit *Unit = SUI.getSortUnitFor(&MBB);
 
-    MachineLoop *Loop = MLI.getLoopFor(&MBB);
-    if (Loop && &MBB == Loop->getHeader()) {
-      // Loop header. The loop predecessor should be sorted above, and the other
-      // predecessors should be backedges below.
+    if (Unit && &MBB == Unit->getHeader()) {
+      if (Unit->isLoop()) {
+        // Loop header. The loop predecessor should be sorted above, and the
+        // other predecessors should be backedges below.
         for (auto Pred : MBB.predecessors())
           assert(
-            (Pred->getNumber() < MBB.getNumber() || Loop->contains(Pred)) &&
-            "Loop header predecessors must be loop predecessors or backedges");
-      assert(OnStack.insert(Loop) && "Loops should be declared at most once.");
+              (Pred->getNumber() < MBB.getNumber() || Unit->contains(Pred)) &&
+              "Loop header predecessors must be loop predecessors or "
+              "backedges");
+      } else {
+        // Not a loop header. All predecessors should be sorted above.
+        for (auto Pred : MBB.predecessors())
+          assert(Pred->getNumber() < MBB.getNumber() &&
+                 "Non-loop-header predecessors should be topologically sorted");
+      }
+      assert(OnStack.insert(Unit) && "Units should be declared at most once.");
+
     } else {
       // Not a loop header. All predecessors should be sorted above.
       for (auto Pred : MBB.predecessors())
         assert(Pred->getNumber() < MBB.getNumber() &&
                "Non-loop-header predecessors should be topologically sorted");
-      assert(OnStack.count(MLI.getLoopFor(&MBB)) &&
-             "Blocks must be nested in their loops");
+      assert(OnStack.count(SUI.getSortUnitFor(&MBB)) &&
+             "Blocks must be nested in their units");
     }
-    while (OnStack.size() > 1 && &MBB == LoopBottom(OnStack.back()))
+    while (OnStack.size() > 1 && &MBB == getBottom(OnStack.back()))
       OnStack.pop_back();
   }
   assert(OnStack.pop_back_val() == nullptr &&
-         "The function entry block shouldn't actually be a loop header");
+         "The function entry block shouldn't actually be a unit header");
   assert(OnStack.empty() &&
          "Control flow stack pushes and pops should be balanced.");
 #endif
 }
 
 bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
   DEBUG(dbgs() << "********** CFG Sorting **********\n"
                   "********** Function: "
                << MF.getName() << '\n');
 
   const auto &MLI = getAnalysis<MachineLoopInfo>();
+  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
   auto &MDT = getAnalysis<MachineDominatorTree>();
   // Liveness is not tracked for VALUE_STACK physreg.
   MF.getRegInfo().invalidateLiveness();
 
-  // Sort the blocks, with contiguous loops.
-  SortBlocks(MF, MLI, MDT);
+  // Sort the blocks, with contiguous sort units.
+  SortBlocks(MF, MLI, WEI, MDT);
 
   return true;
 }

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
         break;
       }
     }
   }
 
   // Decide where in Header to put the BLOCK.
   MachineBasicBlock::iterator InsertPos;
   MachineLoop *HeaderLoop = MLI.getLoopFor(Header);
-  if (HeaderLoop && MBB.getNumber() > LoopBottom(HeaderLoop)->getNumber()) {
+  if (HeaderLoop && MBB.getNumber() > getBottom(HeaderLoop)->getNumber()) {
     // Header is the header of a loop that does not lexically contain MBB, so
     // the BLOCK needs to be above the LOOP, after any END constructs.
     InsertPos = Header->begin();
     while (InsertPos->getOpcode() == WebAssembly::END_BLOCK ||
            InsertPos->getOpcode() == WebAssembly::END_LOOP)
       ++InsertPos;
   } else {
     // Otherwise, insert the BLOCK as late in Header as we can, but before the
static void PlaceLoopMarker(
     DenseMap<const MachineInstr *, MachineInstr *> &LoopTops,
     const WebAssemblyInstrInfo &TII, const MachineLoopInfo &MLI) {
   MachineLoop *Loop = MLI.getLoopFor(&MBB);
   if (!Loop || Loop->getHeader() != &MBB)
     return;
 
   // The operand of a LOOP is the first block after the loop. If the loop is the
   // bottom of the function, insert a dummy block at the end.
-  MachineBasicBlock *Bottom = LoopBottom(Loop);
+  MachineBasicBlock *Bottom = getBottom(Loop);
   auto Iter = std::next(MachineFunction::iterator(Bottom));
   if (Iter == MF.end()) {
     MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
     // Give it a fake predecessor so that AsmPrinter prints its label.
     Label->addSuccessor(Label);
     MF.push_back(Label);
     Iter = std::next(MachineFunction::iterator(Bottom));
   }

lib/Target/WebAssembly/WebAssemblyUtilities.h

 /// This file contains the declaration of the WebAssembly-specific
 /// utility functions.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYUTILITIES_H
 #define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYUTILITIES_H
 
+#include "llvm/CodeGen/MachineBasicBlock.h"
+
 namespace llvm {
 
-class MachineBasicBlock;
-class MachineInstr;
-class MachineLoop;
 class WebAssemblyFunctionInfo;
 
 namespace WebAssembly {
 
 bool isArgument(const MachineInstr &MI);
 bool isCopy(const MachineInstr &MI);
 bool isTee(const MachineInstr &MI);
 bool isChild(const MachineInstr &MI, const WebAssemblyFunctionInfo &MFI);
 bool isCallIndirect(const MachineInstr &MI);
 
 } // end namespace WebAssembly
 
-/// Return the "bottom" block of a loop. This differs from
-/// MachineLoop::getBottomBlock in that it works even if the loop is
+/// Return the "bottom" block of an entity, which can be either a loop or an
+/// exception, or something else. This differs from
+/// MachineLoop::getBottomBlock in that it works even if the entity is
 /// discontiguous.
-MachineBasicBlock *LoopBottom(const MachineLoop *Loop);
+template <typename T>
+MachineBasicBlock *getBottom(const T *Unit) {
+  MachineBasicBlock *Bottom = Unit->getHeader();
+  for (MachineBasicBlock *MBB : Unit->blocks())
+    if (MBB->getNumber() > Bottom->getNumber())
+      Bottom = MBB;
+  return Bottom;
+}
 
 } // end namespace llvm
 
 #endif

lib/Target/WebAssembly/WebAssemblyUtilities.cpp

bool WebAssembly::isCallIndirect(const MachineInstr &MI) {
   case WebAssembly::CALL_INDIRECT_v8i16:
   case WebAssembly::CALL_INDIRECT_v4i32:
   case WebAssembly::CALL_INDIRECT_v4f32:
     return true;
   default:
     return false;
   }
 }
-
-MachineBasicBlock *llvm::LoopBottom(const MachineLoop *Loop) {
-  MachineBasicBlock *Bottom = Loop->getHeader();
-  for (MachineBasicBlock *MBB : Loop->blocks())
-    if (MBB->getNumber() > Bottom->getNumber())
-      Bottom = MBB;
-  return Bottom;
-}

test/CodeGen/WebAssembly/cfg-stackify-eh.ll

+; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -disable-wasm-explicit-locals -disable-block-placement -verify-machineinstrs -fast-isel=false -machine-sink-split-probability-threshold=0 -cgp-freq-ratio-to-skip-merge=1000 -exception-model=wasm | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+@_ZTIi = external constant i8*
+@_ZTId = external constant i8*
+
+; Simple test case with two catch clauses
+
+; CHECK-LABEL: test0
+; CHECK:   call      foo@FUNCTION
+; CHECK: .LBB0_1:
+; CHECK:   i32.catch
+; CHECK:   i32.call  $drop=, _Unwind_CallPersonality@FUNCTION
+; CHECK:   i32.call  $drop=, __cxa_begin_catch@FUNCTION
+; CHECK:   call      bar@FUNCTION
+; CHECK:   call      __cxa_end_catch@FUNCTION
+; CHECK: .LBB0_3:
+; CHECK:   i32.call  $drop=, __cxa_begin_catch@FUNCTION
+; CHECK:   call      __cxa_end_catch@FUNCTION
+; CHECK: .LBB0_5:
+; CHECK:   call      __cxa_rethrow@FUNCTION
+; CHECK:   unreachable
+; CHECK: .LBB0_6:
+; CHECK:   return
+define void @test0() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  invoke void @foo()
+          to label %try.cont unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %entry
+  %0 = catchswitch within none [label %catch.start] unwind to caller
+
+catch.start:                                      ; preds = %catch.dispatch
+  %1 = catchpad within %0 [i8* bitcast (i8** @_ZTIi to i8*), i8* bitcast (i8** @_ZTId to i8*)]
+  %2 = call i8* @llvm.wasm.get.exception()
+  %3 = call i32 @llvm.wasm.get.ehselector()
+  %4 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %3, %4
+  br i1 %matches, label %catch2, label %catch.fallthrough
+
+catch2:                                           ; preds = %catch.start
+  %5 = call i8* @__cxa_begin_catch(i8* %2) [ "funclet"(token %1) ]
+  %6 = bitcast i8* %5 to i32*
+  %7 = load i32, i32* %6, align 4
+  call void @bar() [ "funclet"(token %1) ]
+  call void @__cxa_end_catch() [ "funclet"(token %1) ]
+  catchret from %1 to label %try.cont
+
+catch.fallthrough:                                ; preds = %catch.start
+  %8 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTId to i8*))
+  %matches1 = icmp eq i32 %3, %8
+  br i1 %matches1, label %catch, label %rethrow
+
+catch:                                            ; preds = %catch.fallthrough
+  %9 = call i8* @__cxa_begin_catch(i8* %2) [ "funclet"(token %1) ]
+  %10 = bitcast i8* %9 to double*
+  %11 = load double, double* %10, align 8
+  call void @__cxa_end_catch() [ "funclet"(token %1) ]
+  catchret from %1 to label %try.cont
+
+rethrow:                                          ; preds = %catch.fallthrough
+  call void @__cxa_rethrow() [ "funclet"(token %1) ]
+  unreachable
+
+try.cont:                                         ; preds = %entry, %catch, %catch2
+  ret void
+}
+
+; Nested try-catches within a catch
+
+; CHECK-LABEL: test1
+; CHECK:   call      foo@FUNCTION
+; CHECK: .LBB1_1:
+; CHECK:   i32.catch     $0=, 0
+; CHECK:   i32.call  $drop=, _Unwind_CallPersonality@FUNCTION, $0
+; CHECK:   i32.call  $drop=, __cxa_begin_catch@FUNCTION, $0
+; CHECK:   call      foo@FUNCTION
+; CHECK: .LBB1_3:
+; CHECK:   i32.catch     $0=, 0
+; CHECK:   i32.call  $drop=, _Unwind_CallPersonality@FUNCTION, $0
+; CHECK:   i32.call  $drop=, __cxa_begin_catch@FUNCTION, $0
+; CHECK:   call      foo@FUNCTION
+; CHECK: .LBB1_5:
+; CHECK:   call      __cxa_end_catch@FUNCTION
+; CHECK:   rethrow
+; CHECK: .LBB1_6:
+; CHECK:   call      __cxa_rethrow@FUNCTION
+; CHECK:   unreachable
+; CHECK: .LBB1_8:
+; CHECK:   call      __cxa_end_catch@FUNCTION
+; CHECK: .LBB1_9:
+; CHECK:   call      __cxa_end_catch@FUNCTION
+; CHECK:   rethrow   0
+; CHECK: .LBB1_10:
+; CHECK:   call      __cxa_rethrow@FUNCTION
+; CHECK:   unreachable
+; CHECK: .LBB1_11:
+; CHECK:   call      __cxa_end_catch@FUNCTION
+; CHECK: .LBB1_12:
+; CHECK:   return
+define hidden void @test1() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  invoke void @foo()
+          to label %try.cont11 unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %entry
+  %0 = catchswitch within none [label %catch.start] unwind to caller
+
+catch.start:                                      ; preds = %catch.dispatch
+  %1 = catchpad within %0 [i8* bitcast (i8** @_ZTIi to i8*)]
+  %2 = call i8* @llvm.wasm.get.exception()
+  %3 = call i32 @llvm.wasm.get.ehselector()
+  %4 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %3, %4
+  br i1 %matches, label %catch, label %rethrow
+
+catch:                                            ; preds = %catch.start
+  %5 = call i8* @__cxa_begin_catch(i8* %2) [ "funclet"(token %1) ]
+  %6 = bitcast i8* %5 to i32*
+  %7 = load i32, i32* %6, align 4
+  invoke void @foo() [ "funclet"(token %1) ]
+          to label %try.cont unwind label %catch.dispatch2
+
+catch.dispatch2:                                  ; preds = %catch
+  %8 = catchswitch within %1 [label %catch.start3] unwind label %ehcleanup9
+
+catch.start3:                                     ; preds = %catch.dispatch2
+  %9 = catchpad within %8 [i8* bitcast (i8** @_ZTIi to i8*)]
+  %10 = call i8* @llvm.wasm.get.exception()
+  %11 = call i32 @llvm.wasm.get.ehselector()
+  %12 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches4 = icmp eq i32 %11, %12
+  br i1 %matches4, label %catch6, label %rethrow5
+
+catch6:                                           ; preds = %catch.start3
+  %13 = call i8* @__cxa_begin_catch(i8* %10) [ "funclet"(token %9) ]
+  %14 = bitcast i8* %13 to i32*
+  %15 = load i32, i32* %14, align 4
+  invoke void @foo() [ "funclet"(token %9) ]
+          to label %invoke.cont8 unwind label %ehcleanup
+
+invoke.cont8:                                     ; preds = %catch6
+  call void @__cxa_end_catch() [ "funclet"(token %9) ]
+  catchret from %9 to label %try.cont
+
+rethrow5:                                         ; preds = %catch.start3
+  invoke void @__cxa_rethrow() [ "funclet"(token %9) ]
+          to label %unreachable unwind label %ehcleanup9
+
+try.cont:                                         ; preds = %catch, %invoke.cont8
+  call void @__cxa_end_catch() [ "funclet"(token %1) ]
+  catchret from %1 to label %try.cont11
+
+rethrow:                                          ; preds = %catch.start
+  call void @__cxa_rethrow() [ "funclet"(token %1) ]
+  unreachable
+
+try.cont11:                                       ; preds = %entry, %try.cont
+  ret void
+
+ehcleanup:                                        ; preds = %catch6
+  %16 = cleanuppad within %9 []
+  call void @__cxa_end_catch() [ "funclet"(token %16) ]
+  cleanupret from %16 unwind label %ehcleanup9
+
+ehcleanup9:                                       ; preds = %ehcleanup, %rethrow5, %catch.dispatch2
+  %17 = cleanuppad within %1 []
+  call void @__cxa_end_catch() [ "funclet"(token %17) ]
+  cleanupret from %17 unwind to caller
+
+unreachable:                                      ; preds = %rethrow5
+  unreachable
+}
+
+; Nested loop within a catch clause
+
+; CHECK-LABEL: test2
+; CHECK:   call      foo@FUNCTION
+; CHECK: .LBB2_1:
+; CHECK:   i32.catch
+; CHECK:   i32.call  $drop=, __cxa_begin_catch@FUNCTION
+; CHECK: .LBB2_2:
+; CHECK:   call      foo@FUNCTION
+; CHECK: .LBB2_4:
+; CHECK:   call      __cxa_end_catch@FUNCTION
+; CHECK: .LBB2_5:
+; CHECK:   i32.catch
+; CHECK:   call      __clang_call_terminate@FUNCTION
+; CHECK:   unreachable
+; CHECK: .LBB2_6:
+; CHECK:   rethrow
+; CHECK: .LBB2_7:
+; CHECK:   call      __cxa_end_catch@FUNCTION
+; CHECK: .LBB2_8:
+; CHECK: .LBB2_9:
+; CHECK:   return
+define void @test2() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  invoke void @foo()
+          to label %try.cont unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %entry
+  %0 = catchswitch within none [label %catch.start] unwind to caller
+
+catch.start:                                      ; preds = %catch.dispatch
+  %1 = catchpad within %0 [i8* null]
+  %2 = call i8* @llvm.wasm.get.exception()
+  %3 = call i32 @llvm.wasm.get.ehselector()
+  %4 = call i8* @__cxa_begin_catch(i8* %2) [ "funclet"(token %1) ]
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %catch.start
+  %i.0 = phi i32 [ 0, %catch.start ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, 50
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  invoke void @foo() [ "funclet"(token %1) ]
+          to label %for.inc unwind label %ehcleanup
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  call void @__cxa_end_catch() [ "funclet"(token %1) ]
+  catchret from %1 to label %try.cont
+
+try.cont:                                         ; preds = %for.end, %entry
+  ret void
+
+ehcleanup:                                        ; preds = %for.body
+  %5 = cleanuppad within %1 []
+  invoke void @__cxa_end_catch() [ "funclet"(token %5) ]
+          to label %invoke.cont2 unwind label %terminate
+
+invoke.cont2:                                     ; preds = %ehcleanup
+  cleanupret from %5 unwind to caller
+
+terminate:                                        ; preds = %ehcleanup
+  %6 = cleanuppad within %5 []
+  %7 = call i8* @llvm.wasm.get.exception()
+  call void @__clang_call_terminate(i8* %7) [ "funclet"(token %6) ]
+  unreachable
+}
+
+declare void @foo()
+declare void @bar()
+declare i32 @__gxx_wasm_personality_v0(...)
+declare i8* @llvm.wasm.get.exception()
+declare i32 @llvm.wasm.get.ehselector()
+declare i32 @llvm.eh.typeid.for(i8*)
+declare i8* @__cxa_begin_catch(i8*)
+declare void @__cxa_end_catch()
+declare void @__cxa_rethrow()
+declare void @__clang_call_terminate(i8*)

test/CodeGen/WebAssembly/exception.ll

rethrow:                                          ; preds = %catch.start
   unreachable
 
 try.cont:                                         ; preds = %entry, %catch
   ret void
 }
 
 ; CHECK-LABEL: test_cleanup:
 ; CHECK:   call      foo@FUNCTION
-; CHECK:   return
 ; CHECK:   i32.call  $push20=, _ZN7CleanupD1Ev@FUNCTION
 ; CHECK:   rethrow   0
+; CHECK:   return
 define void @test_cleanup() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %c = alloca %struct.Cleanup, align 1
   invoke void @foo()
           to label %invoke.cont unwind label %ehcleanup
 
 invoke.cont:                                      ; preds = %entry
   %call = call %struct.Cleanup* @_ZN7CleanupD1Ev(%struct.Cleanup* %c)