[WebAssembly] CFG stackify support for exception handling

[aheejin]

Summary

This adds support for exception handling to CFGStackify pass. This only
adds TRY / END_TRY markers and DOES NOT yet fix unwind mismatches that
can be created by the linearization of the CFG into the structural wasm
format. The mismatch fix will be added by following patches.

In detail, this patch

• Added support for TRY / END_TRY markers to support EH
• Changed many static functions into class member functions as they take too many arguments now
• Added several more bookeeping data structures
• Refactored routines that decide where to insert markers, because without refactoring this got too complicated as we added support for new kinds of markers (TRY/END_TRY).
• Rewrote rethrow instructions' BB arguments to relative depths in EH pad stack

[aheejin]

Ping

[aheejin]

Add markers to an existing test case

[dschuff]

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

126 ↗

(On Diff #160221)

I think this idea of BeforeSet and AfterSet makes sense given the symmetry, but it was unclear on the first reading that only the BeforeSet is actually used other than for debugging (despite the ifdef and comment below). So this comment could maybe just have an additional ", but is only used for sanity checking" at the end.

294 ↗

(On Diff #160221)

why is this only for debugging? edit: nevermind I figured it out. see comment abo.ve

307 ↗

(On Diff #160221)

I know LLVM style allows this complete lack of braces, but IMO using this many lines (control structures, etc) is just asking for bugs. Plus I find it difficult to read. Could we use the braces anyway in cases where the body is a nested expression?

539 ↗

(On Diff #160221)

Add braces here too.

670 ↗

(On Diff #160221)

Update comment.

[dschuff]

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

443 ↗

(On Diff #160221)

The fact that so many sections of this function are the same as or almost the same as placeBlockMarker kind of makes me wonder if we can do better about sharing the logic, although there are enough differences to make that challenging too. Probably worth thinking about, especially if we end up thinking of going toward a more explicit or IR-like representation of wasm control structures.

[aheejin]

• Address comments
• Add more braces

[aheejin]

lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

307 ↗

(On Diff #160221)

Yeah I used to place braces in this kind of cases too, but someone (not you) once told me to remove them in code review, and I guess that's when I started removing them :$ But I also think braces make code easy to read and less bug prone. Anyway I added the braces back.

443 ↗

(On Diff #160221)

Hmm. Yes. In the current structure I also find it difficult to share the logics. Further, when determining BeforeSet and AfterSet, there are even more differences, partly because marker kinds are different, but also partly try/end_try marker placement is done lastly so it has to make sure the placement makes sense with respect to all previously placed block/end_block/loop/end_loop markers.

[aheejin]

@sunfish Do you have any other concerns?

[sunfish]

This looks ok to land now.

llvm/trunk/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

 //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
 //
 //                     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 stacking pass.
 ///
-/// This pass inserts BLOCK and LOOP markers to mark the start of scopes, since
-/// scope boundaries serve as the labels for WebAssembly's control transfers.
+/// This pass inserts BLOCK, LOOP, and TRY markers to mark the start of scopes,
+/// since scope boundaries serve as the labels for WebAssembly's control
+/// transfers.
 ///
 /// This is sufficient to convert arbitrary CFGs into a form that works on
 /// WebAssembly, provided that all loops are single-entry.
 ///
+/// In case we use exceptions, this pass also fixes mismatches in unwind
+/// destinations created during transforming CFG into wasm structured format.
+///
 //===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssembly.h"
+#include "WebAssemblyExceptionInfo.h"
 #include "WebAssemblyMachineFunctionInfo.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyUtilities.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/WasmEHFuncInfo.h"
+#include "llvm/MC/MCAsmInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "wasm-cfg-stackify"
 
 namespace {
 class WebAssemblyCFGStackify final : public MachineFunctionPass {
   StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesCFG();
     AU.addRequired<MachineDominatorTree>();
-    AU.addPreserved<MachineDominatorTree>();
     AU.addRequired<MachineLoopInfo>();
-    AU.addPreserved<MachineLoopInfo>();
+    AU.addRequired<WebAssemblyExceptionInfo>();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
+  // For each block whose label represents the end of a scope, record the block
+  // which holds the beginning of the scope. This will allow us to quickly skip
+  // over scoped regions when walking blocks.
+  SmallVector<MachineBasicBlock *, 8> ScopeTops;
+
+  void placeMarkers(MachineFunction &MF);
+  void placeBlockMarker(MachineBasicBlock &MBB);
+  void placeLoopMarker(MachineBasicBlock &MBB);
+  void placeTryMarker(MachineBasicBlock &MBB);
+  void rewriteDepthImmediates(MachineFunction &MF);
+  void fixEndsAtEndOfFunction(MachineFunction &MF);
+
+  // For each BLOCK|LOOP|TRY, the corresponding END_(BLOCK|LOOP|TRY).
+  DenseMap<const MachineInstr *, MachineInstr *> BeginToEnd;
+  // For each END_(BLOCK|LOOP|TRY), the corresponding BLOCK|LOOP|TRY.
+  DenseMap<const MachineInstr *, MachineInstr *> EndToBegin;
+  // <TRY marker, EH pad> map
+  DenseMap<const MachineInstr *, MachineBasicBlock *> TryToEHPad;
+  // <EH pad, TRY marker> map
+  DenseMap<const MachineBasicBlock *, MachineInstr *> EHPadToTry;
+  // <LOOP|TRY marker, Loop/exception bottom BB> map
+  DenseMap<const MachineInstr *, MachineBasicBlock *> BeginToBottom;
+
+  // Helper functions to register / unregister scope information created by
+  // marker instructions.
+  void registerScope(MachineInstr *Begin, MachineInstr *End);
+  void registerTryScope(MachineInstr *Begin, MachineInstr *End,
+                        MachineBasicBlock *EHPad);
+  void unregisterScope(MachineInstr *Begin);
+
+  MachineBasicBlock *getBottom(const MachineInstr *Begin);
+
 public:
   static char ID; // Pass identification, replacement for typeid
   WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
+  ~WebAssemblyCFGStackify() override { releaseMemory(); }
+  void releaseMemory() override;
 };
 } // end anonymous namespace
 
 char WebAssemblyCFGStackify::ID = 0;
 INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE,
                 "Insert BLOCK and LOOP markers for WebAssembly scopes",
                 false, false)
 
 FunctionPass *llvm::createWebAssemblyCFGStackify() {
   return new WebAssemblyCFGStackify();
 }
 
 /// Test whether Pred has any terminators explicitly branching to MBB, as
 /// opposed to falling through. Note that it's possible (eg. in unoptimized
 /// code) for a branch instruction to both branch to a block and fallthrough
 /// to it, so we check the actual branch operands to see if there are any
 /// explicit mentions.
 static bool ExplicitlyBranchesTo(MachineBasicBlock *Pred,
                                  MachineBasicBlock *MBB) {
   for (MachineInstr &MI : Pred->terminators())
+    // Even if a rethrow takes a BB argument, it is not a branch
+    if (!WebAssembly::isRethrow(MI))
       for (MachineOperand &MO : MI.explicit_operands())
         if (MO.isMBB() && MO.getMBB() == MBB)
           return true;
   return false;
 }
 
+// Returns an iterator to the earliest position possible within the MBB,
+// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
+// contains instructions that should go before the marker, and AfterSet contains
+// ones that should go after the marker. In this function, AfterSet is only
+// used for sanity checking.
+static MachineBasicBlock::iterator
+GetEarliestInsertPos(MachineBasicBlock *MBB,
+                     const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
+                     const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
+  auto InsertPos = MBB->end();
+  while (InsertPos != MBB->begin()) {
+    if (BeforeSet.count(&*std::prev(InsertPos))) {
+#ifndef NDEBUG
+      // Sanity check
+      for (auto Pos = InsertPos, E = MBB->begin(); Pos != E; --Pos)
+        assert(!AfterSet.count(&*std::prev(Pos)));
+#endif
+      break;
+    }
+    --InsertPos;
+  }
+  return InsertPos;
+}
+
+// Returns an iterator to the latest position possible within the MBB,
+// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
+// contains instructions that should go before the marker, and AfterSet contains
+// ones that should go after the marker. In this function, BeforeSet is only
+// used for sanity checking.
+static MachineBasicBlock::iterator
+GetLatestInsertPos(MachineBasicBlock *MBB,
+                   const SmallPtrSet<const MachineInstr *, 4> &BeforeSet,
+                   const SmallPtrSet<const MachineInstr *, 4> &AfterSet) {
+  auto InsertPos = MBB->begin();
+  while (InsertPos != MBB->end()) {
+    if (AfterSet.count(&*InsertPos)) {
+#ifndef NDEBUG
+      // Sanity check
+      for (auto Pos = InsertPos, E = MBB->end(); Pos != E; ++Pos)
+        assert(!BeforeSet.count(&*Pos));
+#endif
+      break;
+    }
+    ++InsertPos;
+  }
+  return InsertPos;
+}
+
+void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
+                                           MachineInstr *End) {
+  BeginToEnd[Begin] = End;
+  EndToBegin[End] = Begin;
+}
+
+void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
+                                              MachineInstr *End,
+                                              MachineBasicBlock *EHPad) {
+  registerScope(Begin, End);
+  TryToEHPad[Begin] = EHPad;
+  EHPadToTry[EHPad] = Begin;
+}
+
+void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) {
+  assert(BeginToEnd.count(Begin));
+  MachineInstr *End = BeginToEnd[Begin];
+  assert(EndToBegin.count(End));
+  BeginToEnd.erase(Begin);
+  EndToBegin.erase(End);
+  MachineBasicBlock *EHPad = TryToEHPad.lookup(Begin);
+  if (EHPad) {
+    assert(EHPadToTry.count(EHPad));
+    TryToEHPad.erase(Begin);
+    EHPadToTry.erase(EHPad);
+  }
+  MachineBasicBlock *Bottom = BeginToBottom.lookup(Begin);
+  if (Bottom)
+    BeginToBottom.erase(Begin);
+}
+
+// Given a LOOP/TRY marker, returns its bottom BB. Use cached information if any
+// to prevent recomputation.
+MachineBasicBlock *
+WebAssemblyCFGStackify::getBottom(const MachineInstr *Begin) {
+  const auto &MLI = getAnalysis<MachineLoopInfo>();
+  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
+  if (BeginToBottom.count(Begin))
+    return BeginToBottom[Begin];
+  if (Begin->getOpcode() == WebAssembly::LOOP) {
+    MachineLoop *L = MLI.getLoopFor(Begin->getParent());
+    assert(L);
+    BeginToBottom[Begin] = WebAssembly::getBottom(L);
+  } else if (Begin->getOpcode() == WebAssembly::TRY) {
+    WebAssemblyException *WE = WEI.getExceptionFor(TryToEHPad[Begin]);
+    assert(WE);
+    BeginToBottom[Begin] = WebAssembly::getBottom(WE);
+  } else
+    assert(false);
+  return BeginToBottom[Begin];
+}
+
 /// Insert a BLOCK marker for branches to MBB (if needed).
-static void PlaceBlockMarker(
-    MachineBasicBlock &MBB, MachineFunction &MF,
-    SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
-    DenseMap<const MachineInstr *, MachineInstr *> &BlockTops,
-    DenseMap<const MachineInstr *, MachineInstr *> &LoopTops,
-    const WebAssemblyInstrInfo &TII,
-    const MachineLoopInfo &MLI,
-    MachineDominatorTree &MDT,
-    WebAssemblyFunctionInfo &MFI) {
+void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) {
+  // This should have been handled in placeTryMarker.
+  if (MBB.isEHPad())
+    return;
+
+  MachineFunction &MF = *MBB.getParent();
+  auto &MDT = getAnalysis<MachineDominatorTree>();
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
+
   // First compute the nearest common dominator of all forward non-fallthrough
   // predecessors so that we minimize the time that the BLOCK is on the stack,
   // which reduces overall stack height.
   MachineBasicBlock *Header = nullptr;
   bool IsBranchedTo = false;
   int MBBNumber = MBB.getNumber();
-  for (MachineBasicBlock *Pred : MBB.predecessors())
+  for (MachineBasicBlock *Pred : MBB.predecessors()) {
     if (Pred->getNumber() < MBBNumber) {
       Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
       if (ExplicitlyBranchesTo(Pred, &MBB))
         IsBranchedTo = true;
     }
+  }
   if (!Header)
     return;
   if (!IsBranchedTo)
     return;
 
   assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
   MachineBasicBlock *LayoutPred = &*std::prev(MachineFunction::iterator(&MBB));
 
   // If the nearest common dominator is inside a more deeply nested context,
   // walk out to the nearest scope which isn't more deeply nested.
   for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
     if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
       if (ScopeTop->getNumber() > Header->getNumber()) {
         // Skip over an intervening scope.
         I = std::next(MachineFunction::iterator(ScopeTop));
       } else {
         // We found a scope level at an appropriate depth.
         Header = ScopeTop;
         break;
       }
     }
   }
 
   // Decide where in Header to put the BLOCK.
-  MachineBasicBlock::iterator InsertPos;
-  MachineLoop *HeaderLoop = MLI.getLoopFor(Header);
-  if (HeaderLoop &&
-      MBB.getNumber() > WebAssembly::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
-    // beginning of the local expression tree and any nested BLOCKs.
-    InsertPos = Header->getFirstTerminator();
-    while (InsertPos != Header->begin() &&
-           WebAssembly::isChild(*std::prev(InsertPos), MFI) &&
-           std::prev(InsertPos)->getOpcode() != WebAssembly::LOOP &&
-           std::prev(InsertPos)->getOpcode() != WebAssembly::END_BLOCK &&
-           std::prev(InsertPos)->getOpcode() != WebAssembly::END_LOOP)
-      --InsertPos;
+
+  // Instructions that should go before the BLOCK.
+  SmallPtrSet<const MachineInstr *, 4> BeforeSet;
+  // Instructions that should go after the BLOCK.
+  SmallPtrSet<const MachineInstr *, 4> AfterSet;
+  for (const auto &MI : *Header) {
+    // If there is a previously placed LOOP/TRY marker and the bottom block of
+    // the loop/exception is above MBB, it should be after the BLOCK, because
+    // the loop/exception is nested in this block. Otherwise it should be before
+    // the BLOCK.
+    if (MI.getOpcode() == WebAssembly::LOOP ||
+        MI.getOpcode() == WebAssembly::TRY) {
+      if (MBB.getNumber() > getBottom(&MI)->getNumber())
+        AfterSet.insert(&MI);
+#ifndef NDEBUG
+      else
+        BeforeSet.insert(&MI);
+#endif
+    }
+
+    // All previously inserted BLOCK markers should be after the BLOCK because
+    // they are all nested blocks.
+    if (MI.getOpcode() == WebAssembly::BLOCK)
+      AfterSet.insert(&MI);
+
+#ifndef NDEBUG
+    // All END_(BLOCK|LOOP|TRY) markers should be before the BLOCK.
+    if (MI.getOpcode() == WebAssembly::END_BLOCK ||
+        MI.getOpcode() == WebAssembly::END_LOOP ||
+        MI.getOpcode() == WebAssembly::END_TRY)
+      BeforeSet.insert(&MI);
+#endif
+
+    // Terminators should go after the BLOCK.
+    if (MI.isTerminator())
+      AfterSet.insert(&MI);
+  }
+
+  // Local expression tree should go after the BLOCK.
+  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
+       --I) {
+    if (WebAssembly::isChild(*std::prev(I), MFI))
+      AfterSet.insert(&*std::prev(I));
+    else
+      break;
   }
 
   // Add the BLOCK.
+  auto InsertPos = GetLatestInsertPos(Header, BeforeSet, AfterSet);
   MachineInstr *Begin =
       BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
               TII.get(WebAssembly::BLOCK))
           .addImm(int64_t(WebAssembly::ExprType::Void));
 
+  // Decide where in Header to put the END_BLOCK.
+  BeforeSet.clear();
+  AfterSet.clear();
+  for (auto &MI : MBB) {
+#ifndef NDEBUG
+    // END_BLOCK should precede existing LOOP and TRY markers.
+    if (MI.getOpcode() == WebAssembly::LOOP ||
+        MI.getOpcode() == WebAssembly::TRY)
+      AfterSet.insert(&MI);
+#endif
+
+    // If there is a previously placed END_LOOP marker and the header of the
+    // loop is above this block's header, the END_LOOP should be placed after
+    // the BLOCK, because the loop contains this block. Otherwise the END_LOOP
+    // should be placed before the BLOCK. The same for END_TRY.
+    if (MI.getOpcode() == WebAssembly::END_LOOP ||
+        MI.getOpcode() == WebAssembly::END_TRY) {
+      if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
+        BeforeSet.insert(&MI);
+#ifndef NDEBUG
+      else
+        AfterSet.insert(&MI);
+#endif
+    }
+  }
+
   // Mark the end of the block.
-  InsertPos = MBB.begin();
-  while (InsertPos != MBB.end() &&
-         InsertPos->getOpcode() == WebAssembly::END_LOOP &&
-         LoopTops[&*InsertPos]->getParent()->getNumber() >= Header->getNumber())
-    ++InsertPos;
+  InsertPos = GetEarliestInsertPos(&MBB, BeforeSet, AfterSet);
   MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos),
                               TII.get(WebAssembly::END_BLOCK));
-  BlockTops[End] = Begin;
+  registerScope(Begin, End);
 
   // Track the farthest-spanning scope that ends at this point.
   int Number = MBB.getNumber();
   if (!ScopeTops[Number] ||
       ScopeTops[Number]->getNumber() > Header->getNumber())
     ScopeTops[Number] = Header;
 }
 
 /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
-static void PlaceLoopMarker(
-    MachineBasicBlock &MBB, MachineFunction &MF,
-    SmallVectorImpl<MachineBasicBlock *> &ScopeTops,
-    DenseMap<const MachineInstr *, MachineInstr *> &LoopTops,
-    const WebAssemblyInstrInfo &TII, const MachineLoopInfo &MLI) {
+void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
+  MachineFunction &MF = *MBB.getParent();
+  const auto &MLI = getAnalysis<MachineLoopInfo>();
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+
   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 = WebAssembly::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));
   }
   MachineBasicBlock *AfterLoop = &*Iter;
 
-  // Mark the beginning of the loop (after the end of any existing loop that
-  // ends here).
-  auto InsertPos = MBB.begin();
-  while (InsertPos != MBB.end() &&
-         InsertPos->getOpcode() == WebAssembly::END_LOOP)
-    ++InsertPos;
+  // Decide where in Header to put the LOOP.
+  SmallPtrSet<const MachineInstr *, 4> BeforeSet;
+  SmallPtrSet<const MachineInstr *, 4> AfterSet;
+  for (const auto &MI : MBB) {
+    // LOOP marker should be after any existing loop that ends here. Otherwise
+    // we assume the instruction belongs to the loop.
+    if (MI.getOpcode() == WebAssembly::END_LOOP)
+      BeforeSet.insert(&MI);
+#ifndef NDEBUG
+    else
+      AfterSet.insert(&MI);
+#endif
+  }
+
+  // Mark the beginning of the loop.
+  auto InsertPos = GetEarliestInsertPos(&MBB, BeforeSet, AfterSet);
   MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos),
                                 TII.get(WebAssembly::LOOP))
                             .addImm(int64_t(WebAssembly::ExprType::Void));
 
-  // Mark the end of the loop (using arbitrary debug location that branched
-  // to the loop end as its location).
+  // Decide where in Header to put the END_LOOP.
+  BeforeSet.clear();
+  AfterSet.clear();
+#ifndef NDEBUG
+  for (const auto &MI : MBB)
+    // Existing END_LOOP markers belong to parent loops of this loop
+    if (MI.getOpcode() == WebAssembly::END_LOOP)
+      AfterSet.insert(&MI);
+#endif
+
+  // Mark the end of the loop (using arbitrary debug location that branched to
+  // the loop end as its location).
+  InsertPos = GetEarliestInsertPos(AfterLoop, BeforeSet, AfterSet);
   DebugLoc EndDL = (*AfterLoop->pred_rbegin())->findBranchDebugLoc();
-  MachineInstr *End = BuildMI(*AfterLoop, AfterLoop->begin(), EndDL,
-                              TII.get(WebAssembly::END_LOOP));
-  LoopTops[End] = Begin;
+  MachineInstr *End =
+      BuildMI(*AfterLoop, InsertPos, EndDL, TII.get(WebAssembly::END_LOOP));
+  registerScope(Begin, End);
 
   assert((!ScopeTops[AfterLoop->getNumber()] ||
           ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) &&
          "With block sorting the outermost loop for a block should be first.");
   if (!ScopeTops[AfterLoop->getNumber()])
     ScopeTops[AfterLoop->getNumber()] = &MBB;
 }
 
+void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
+  if (!MBB.isEHPad())
+    return;
+
+  // catch_all terminate pad is grouped together with catch terminate pad and
+  // does not need a separate TRY and END_TRY marker.
+  if (WebAssembly::isCatchAllTerminatePad(MBB))
+    return;
+
+  MachineFunction &MF = *MBB.getParent();
+  auto &MDT = getAnalysis<MachineDominatorTree>();
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
+  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
+
+  // Compute the nearest common dominator of all unwind predecessors
+  MachineBasicBlock *Header = nullptr;
+  int MBBNumber = MBB.getNumber();
+  for (auto *Pred : MBB.predecessors()) {
+    if (Pred->getNumber() < MBBNumber) {
+      Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
+      assert(!ExplicitlyBranchesTo(Pred, &MBB) &&
+             "Explicit branch to an EH pad!");
+    }
+  }
+  if (!Header)
+    return;
+
+  // If this try is at the bottom of the function, insert a dummy block at the
+  // end.
+  WebAssemblyException *WE = WEI.getExceptionFor(&MBB);
+  assert(WE);
+  MachineBasicBlock *Bottom = WebAssembly::getBottom(WE);
+
+  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));
+  }
+  MachineBasicBlock *AfterTry = &*Iter;
+
+  assert(AfterTry != &MF.front());
+  MachineBasicBlock *LayoutPred =
+      &*std::prev(MachineFunction::iterator(AfterTry));
+
+  // If the nearest common dominator is inside a more deeply nested context,
+  // walk out to the nearest scope which isn't more deeply nested.
+  for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) {
+    if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) {
+      if (ScopeTop->getNumber() > Header->getNumber()) {
+        // Skip over an intervening scope.
+        I = std::next(MachineFunction::iterator(ScopeTop));
+      } else {
+        // We found a scope level at an appropriate depth.
+        Header = ScopeTop;
+        break;
+      }
+    }
+  }
+
+  // Decide where in Header to put the TRY.
+
+  // Instructions that should go before the BLOCK.
+  SmallPtrSet<const MachineInstr *, 4> BeforeSet;
+  // Instructions that should go after the BLOCK.
+  SmallPtrSet<const MachineInstr *, 4> AfterSet;
+  for (const auto &MI : *Header) {
+    // If there is a previously placed LOOP marker and the bottom block of
+    // the loop is above MBB, the LOOP should be after the TRY, because the
+    // loop is nested in this try. Otherwise it should be before the TRY.
+    if (MI.getOpcode() == WebAssembly::LOOP) {
+      if (MBB.getNumber() > Bottom->getNumber())
+        AfterSet.insert(&MI);
+#ifndef NDEBUG
+      else
+        BeforeSet.insert(&MI);
+#endif
+    }
+
+    // All previously inserted TRY markers should be after the TRY because they
+    // are all nested trys.
+    if (MI.getOpcode() == WebAssembly::TRY)
+      AfterSet.insert(&MI);
+
+#ifndef NDEBUG
+    // All END_(LOOP/TRY) markers should be before the TRY.
+    if (MI.getOpcode() == WebAssembly::END_LOOP ||
+        MI.getOpcode() == WebAssembly::END_TRY)
+      BeforeSet.insert(&MI);
+#endif
+
+    // Terminators should go after the TRY.
+    if (MI.isTerminator())
+      AfterSet.insert(&MI);
+  }
+
+  // Local expression tree should go after the TRY.
+  for (auto I = Header->getFirstTerminator(), E = Header->begin(); I != E;
+       --I) {
+    if (WebAssembly::isChild(*std::prev(I), MFI))
+      AfterSet.insert(&*std::prev(I));
+    else
+      break;
+  }
+
+  // If Header unwinds to MBB (= Header contains 'invoke'), the try block should
+  // contain the call within it. So the call should go after the TRY. The
+  // exception is when the header's terminator is a rethrow instruction, in
+  // which case that instruction, not a call instruction before it, is gonna
+  // throw.
+  if (MBB.isPredecessor(Header)) {
+    auto TermPos = Header->getFirstTerminator();
+    if (TermPos == Header->end() || !WebAssembly::isRethrow(*TermPos)) {
+      for (const auto &MI : reverse(*Header)) {
+        if (MI.isCall()) {
+          AfterSet.insert(&MI);
+          break;
+        }
+      }
+    }
+  }
+
+  // Add the TRY.
+  auto InsertPos = GetLatestInsertPos(Header, BeforeSet, AfterSet);
+  MachineInstr *Begin =
+      BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos),
+              TII.get(WebAssembly::TRY))
+          .addImm(int64_t(WebAssembly::ExprType::Void));
+
+  // Decide where in Header to put the END_TRY.
+  BeforeSet.clear();
+  AfterSet.clear();
+  for (const auto &MI : *AfterTry) {
+#ifndef NDEBUG
+    // END_TRY should precede existing LOOP markers.
+    if (MI.getOpcode() == WebAssembly::LOOP)
+      AfterSet.insert(&MI);
+
+    // All END_TRY markers placed earlier belong to exceptions that contains
+    // this one.
+    if (MI.getOpcode() == WebAssembly::END_TRY)
+      AfterSet.insert(&MI);
+#endif
+
+    // If there is a previously placed END_LOOP marker and its header is after
+    // where TRY marker is, this loop is contained within the 'catch' part, so
+    // the END_TRY marker should go after that. Otherwise, the whole try-catch
+    // is contained within this loop, so the END_TRY should go before that.
+    if (MI.getOpcode() == WebAssembly::END_LOOP) {
+      if (EndToBegin[&MI]->getParent()->getNumber() >= Header->getNumber())
+        BeforeSet.insert(&MI);
+#ifndef NDEBUG
+      else
+        AfterSet.insert(&MI);
+#endif
+    }
+  }
+
+  // Mark the end of the TRY.
+  InsertPos = GetEarliestInsertPos(AfterTry, BeforeSet, AfterSet);
+  MachineInstr *End =
+      BuildMI(*AfterTry, InsertPos, Bottom->findBranchDebugLoc(),
+              TII.get(WebAssembly::END_TRY));
+  registerTryScope(Begin, End, &MBB);
+
+  // Track the farthest-spanning scope that ends at this point.
+  int Number = AfterTry->getNumber();
+  if (!ScopeTops[Number] ||
+      ScopeTops[Number]->getNumber() > Header->getNumber())
+    ScopeTops[Number] = Header;
+}
+
 static unsigned
 GetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack,
          const MachineBasicBlock *MBB) {
   unsigned Depth = 0;
   for (auto X : reverse(Stack)) {
     if (X == MBB)
       break;
     ++Depth;
   }
   assert(Depth < Stack.size() && "Branch destination should be in scope");
   return Depth;
 }
 
 /// In normal assembly languages, when the end of a function is unreachable,
 /// because the function ends in an infinite loop or a noreturn call or similar,
 /// it isn't necessary to worry about the function return type at the end of
 /// the function, because it's never reached. However, in WebAssembly, blocks
 /// that end at the function end need to have a return type signature that
 /// matches the function signature, even though it's unreachable. This function
 /// checks for such cases and fixes up the signatures.
-static void FixEndsAtEndOfFunction(
-    MachineFunction &MF,
-    const WebAssemblyFunctionInfo &MFI,
-    DenseMap<const MachineInstr *, MachineInstr *> &BlockTops,
-    DenseMap<const MachineInstr *, MachineInstr *> &LoopTops) {
+void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
+  const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
   assert(MFI.getResults().size() <= 1);
 
   if (MFI.getResults().empty())
     return;
 
   WebAssembly::ExprType retType;
   switch (MFI.getResults().front().SimpleTy) {
   case MVT::i32: retType = WebAssembly::ExprType::I32; break;
void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
   default: llvm_unreachable("unexpected return type");
   }
 
   for (MachineBasicBlock &MBB : reverse(MF)) {
     for (MachineInstr &MI : reverse(MBB)) {
       if (MI.isPosition() || MI.isDebugInstr())
         continue;
       if (MI.getOpcode() == WebAssembly::END_BLOCK) {
-        BlockTops[&MI]->getOperand(0).setImm(int32_t(retType));
+        EndToBegin[&MI]->getOperand(0).setImm(int32_t(retType));
         continue;
       }
       if (MI.getOpcode() == WebAssembly::END_LOOP) {
-        LoopTops[&MI]->getOperand(0).setImm(int32_t(retType));
+        EndToBegin[&MI]->getOperand(0).setImm(int32_t(retType));
         continue;
       }
       // Something other than an `end`. We're done.
       return;
     }
   }
 }
 
 // WebAssembly functions end with an end instruction, as if the function body
 // were a block.
 static void AppendEndToFunction(
     MachineFunction &MF,
     const WebAssemblyInstrInfo &TII) {
   BuildMI(MF.back(), MF.back().end(),
           MF.back().findPrevDebugLoc(MF.back().end()),
           TII.get(WebAssembly::END_FUNCTION));
 }
 
-/// Insert LOOP and BLOCK markers at appropriate places.
-static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
-                         const WebAssemblyInstrInfo &TII,
-                         MachineDominatorTree &MDT,
-                         WebAssemblyFunctionInfo &MFI) {
-  // For each block whose label represents the end of a scope, record the block
-  // which holds the beginning of the scope. This will allow us to quickly skip
-  // over scoped regions when walking blocks. We allocate one more than the
-  // number of blocks in the function to accommodate for the possible fake block
-  // we may insert at the end.
-  SmallVector<MachineBasicBlock *, 8> ScopeTops(MF.getNumBlockIDs() + 1);
-
-  // For each LOOP_END, the corresponding LOOP.
-  DenseMap<const MachineInstr *, MachineInstr *> LoopTops;
-
-  // For each END_BLOCK, the corresponding BLOCK.
-  DenseMap<const MachineInstr *, MachineInstr *> BlockTops;
-
-  for (auto &MBB : MF) {
-    // Place the LOOP for MBB if MBB is the header of a loop.
-    PlaceLoopMarker(MBB, MF, ScopeTops, LoopTops, TII, MLI);
-
-    // Place the BLOCK for MBB if MBB is branched to from above.
-    PlaceBlockMarker(MBB, MF, ScopeTops, BlockTops, LoopTops, TII, MLI, MDT, MFI);
-  }
+/// Insert LOOP/TRY/BLOCK markers at appropriate places.
+void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) {
+  const MCAsmInfo *MCAI = MF.getTarget().getMCAsmInfo();
+  // We allocate one more than the number of blocks in the function to
+  // accommodate for the possible fake block we may insert at the end.
+  ScopeTops.resize(MF.getNumBlockIDs() + 1);
+  for (auto &MBB : MF)
+    placeLoopMarker(MBB);
+  // Place the TRY for MBB if MBB is the EH pad of an exception.
+  if (MCAI->getExceptionHandlingType() == ExceptionHandling::Wasm &&
+      MF.getFunction().hasPersonalityFn())
+    for (auto &MBB : MF)
+      placeTryMarker(MBB);
+  for (auto &MBB : MF)
+    placeBlockMarker(MBB);
 
+void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) {
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
   // Now rewrite references to basic blocks to be depth immediates.
+  // We need two stacks: one for normal scopes and the other for EH pad scopes.
+  // EH pad stack is used to rewrite depths in rethrow instructions.
   SmallVector<const MachineBasicBlock *, 8> Stack;
+  SmallVector<const MachineBasicBlock *, 8> EHPadStack;
   for (auto &MBB : reverse(MF)) {
-    for (auto &MI : reverse(MBB)) {
+    for (auto I = MBB.rbegin(), E = MBB.rend(); I != E; ++I) {
+      MachineInstr &MI = *I;
       switch (MI.getOpcode()) {
       case WebAssembly::BLOCK:
-        assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= MBB.getNumber() &&
-               "Block should be balanced");
+        assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
+                   MBB.getNumber() &&
+               "Block/try should be balanced");
         Stack.pop_back();
         break;
+
+      case WebAssembly::TRY:
+        assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <=
+                   MBB.getNumber() &&
+               "Block/try marker should be balanced");
+        Stack.pop_back();
+        EHPadStack.pop_back();
+        break;
+
+      case WebAssembly::CATCH_I32:
+      case WebAssembly::CATCH_I64:
+      case WebAssembly::CATCH_ALL:
+        EHPadStack.push_back(&MBB);
+        break;
+
       case WebAssembly::LOOP:
         assert(Stack.back() == &MBB && "Loop top should be balanced");
         Stack.pop_back();
         break;
+
       case WebAssembly::END_BLOCK:
+      case WebAssembly::END_TRY:
         Stack.push_back(&MBB);
         break;
+
       case WebAssembly::END_LOOP:
-        Stack.push_back(LoopTops[&MI]->getParent());
+        Stack.push_back(EndToBegin[&MI]->getParent());
+        break;
+
+      case WebAssembly::RETHROW: {
+        // Rewrite MBB operands to be depth immediates.
+        unsigned EHPadDepth = GetDepth(EHPadStack, MI.getOperand(0).getMBB());
+        MI.RemoveOperand(0);
+        MI.addOperand(MF, MachineOperand::CreateImm(EHPadDepth));
+        break;
+      }
+
+      case WebAssembly::RETHROW_TO_CALLER: {
+        MachineInstr *Rethrow =
+            BuildMI(MBB, MI, MI.getDebugLoc(), TII.get(WebAssembly::RETHROW))
+                .addImm(Stack.size());
+        MI.eraseFromParent();
+        I = MachineBasicBlock::reverse_iterator(Rethrow);
         break;
+      }
+
       default:
         if (MI.isTerminator()) {
           // Rewrite MBB operands to be depth immediates.
           SmallVector<MachineOperand, 4> Ops(MI.operands());
           while (MI.getNumOperands() > 0)
             MI.RemoveOperand(MI.getNumOperands() - 1);
           for (auto MO : Ops) {
             if (MO.isMBB())
               MO = MachineOperand::CreateImm(GetDepth(Stack, MO.getMBB()));
             MI.addOperand(MF, MO);
           }
         }
         break;
       }
     }
   }
   assert(Stack.empty() && "Control flow should be balanced");
+}
 
-  // Fix up block/loop signatures at the end of the function to conform to
-  // WebAssembly's rules.
-  FixEndsAtEndOfFunction(MF, MFI, BlockTops, LoopTops);
-
-  // Add an end instruction at the end of the function body.
-  AppendEndToFunction(MF, TII);
+void WebAssemblyCFGStackify::releaseMemory() {
+  ScopeTops.clear();
+  BeginToEnd.clear();
+  EndToBegin.clear();
+  TryToEHPad.clear();
+  EHPadToTry.clear();
+  BeginToBottom.clear();
 }
 
 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "********** CFG Stackifying **********\n"
                        "********** Function: "
                     << MF.getName() << '\n');
 
-  const auto &MLI = getAnalysis<MachineLoopInfo>();
-  auto &MDT = getAnalysis<MachineDominatorTree>();
+  releaseMemory();
+
   // Liveness is not tracked for VALUE_STACK physreg.
-  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
-  WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
   MF.getRegInfo().invalidateLiveness();
 
-  // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
-  PlaceMarkers(MF, MLI, TII, MDT, MFI);
+  // Place the BLOCK/LOOP/TRY markers to indicate the beginnings of scopes.
+  placeMarkers(MF);
+
+  // Convert MBB operands in terminators to relative depth immediates.
+  rewriteDepthImmediates(MF);
+
+  // Fix up block/loop/try signatures at the end of the function to conform to
+  // WebAssembly's rules.
+  fixEndsAtEndOfFunction(MF);
+
+  // Add an end instruction at the end of the function body.
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  if (!MF.getSubtarget<WebAssemblySubtarget>()
+           .getTargetTriple()
+           .isOSBinFormatELF())
+    AppendEndToFunction(MF, TII);
 
   return true;
 }

llvm/trunk/test/CodeGen/WebAssembly/cfg-stackify-eh.mir

+# RUN: llc -mtriple=wasm32-unknown-unknown -exception-model=wasm -run-pass wasm-cfg-stackify %s -o - | FileCheck %s
+
+--- |
+  target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+  target triple = "wasm32-unknown-unknown"
+
+  @__wasm_lpad_context = external global { i32, i8*, i32 }
+
+  declare void @may_throw()
+  ; Function Attrs: nounwind
+  declare void @dont_throw() #0
+  declare i8* @__cxa_begin_catch(i8*)
+  declare void @__cxa_end_catch()
+  declare void @__cxa_rethrow()
+  ; Function Attrs: nounwind
+  declare i32 @__gxx_wasm_personality_v0(...)
+  declare i32 @_Unwind_CallPersonality(i8*) #0
+
+  define void @test0() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+    unreachable
+  }
+  define void @test1() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+    unreachable
+  }
+  define void @test2() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+    unreachable
+  }
+  define void @test3() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+    unreachable
+  }
+
+  attributes #0 = { nounwind }
+
+---
+# Simplest try-catch
+# try {
+#   may_throw();
+# } catch (...) {
+# }
+name: test0
+# CHECK-LABEL: name: test0
+liveins:
+  - { reg: '$arguments', reg: '$value_stack' }
+body: |
+  bb.0:
+    successors: %bb.2, %bb.1
+
+    CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    BR %bb.2, implicit-def $arguments
+  ; CHECK-LABEL: bb.0:
+    ; CHECK: TRY
+    ; CHECK-NEXT: CALL_VOID @may_throw
+
+  bb.1 (landing-pad):
+  ; predecessors: %bb.0
+    successors: %bb.2
+
+    %2:i32 = CATCH_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %3:i32 = CALL_I32 @__cxa_begin_catch, %2:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def $value_stack, implicit $value_stack
+    DROP_I32 killed %3:i32, implicit-def $arguments
+    CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+
+  bb.2:
+  ; predecessors: %bb.0, %bb.1
+
+    RETURN_VOID implicit-def dead $arguments
+  ; CHECK-LABEL: bb.2:
+    ; CHECK-NEXT: END_TRY
+    ; CHECK: RETURN_VOID
+...
+---
+
+# Nested try-catch inside another catch
+#  try {
+#    may_throw();
+#  } catch (int n) {
+#    try {
+#      may_throw();
+#    } catch (int n) {
+#    }
+#  }
+name: test1
+# CHECK-LABEL: name: test1
+liveins:
+  - { reg: '$arguments', reg: '$value_stack' }
+body: |
+  bb.0:
+    successors: %bb.9, %bb.1
+
+    CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    BR %bb.9, implicit-def $arguments
+  ; CHECK-LABEL: bb.0:
+    ; CHECK: TRY
+    ; CHECK-NEXT: CALL_VOID @may_throw
+
+  bb.1 (landing-pad):
+  ; predecessors: %bb.0
+    successors: %bb.2, %bb.7
+
+    %30:i32 = CATCH_I32 0, implicit-def dead $arguments
+    SET_LOCAL_I32 0, %30:i32, implicit-def $arguments
+    %16:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %27:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    STORE_I32 2, @__wasm_lpad_context + 4, %16:i32, %27:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (store 4 into `i8** getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 1)`)
+    %26:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %25:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    STORE_I32 2, @__wasm_lpad_context, %26:i32, %25:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (store 4 into `i32* getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 0)`)
+    %32:i32 = GET_LOCAL_I32 0, implicit-def $arguments
+    %31:i32 = CALL_I32 @_Unwind_CallPersonality, %32:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    DROP_I32 killed %31:i32, implicit-def $arguments
+    %24:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %17:i32 = LOAD_I32 2, @__wasm_lpad_context + 8, %24:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (dereferenceable load 4 from `i32* getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 2)`)
+    %18:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %19:i32 = NE_I32 %17:i32, %18:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    BR_IF %bb.7, %19:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack
+
+  bb.2:
+  ; predecessors: %bb.1
+    successors: %bb.8, %bb.3, %bb.6
+
+    %34:i32 = GET_LOCAL_I32 0, implicit-def $arguments
+    %33:i32 = CALL_I32 @__cxa_begin_catch, %34:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    DROP_I32 killed %33:i32, implicit-def $arguments
+    CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    BR %bb.8, implicit-def $arguments
+  ; CHECK-LABEL: bb.2:
+    ; CHECK: DROP_I32
+    ; CHECK-NEXT: TRY
+    ; CHECK-NEXT: TRY
+    ; CHECK-NEXT: CALL_VOID @may_throw
+
+  bb.3 (landing-pad):
+  ; predecessors: %bb.2
+    successors: %bb.4, %bb.5
+
+    %35:i32 = CATCH_I32 0, implicit-def dead $arguments
+    SET_LOCAL_I32 0, %35:i32, implicit-def $arguments
+    %21:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %20:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    STORE_I32 2, @__wasm_lpad_context, %21:i32, %20:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (store 4 into `i32* getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 0)`)
+    %37:i32 = GET_LOCAL_I32 0, implicit-def $arguments
+    %36:i32 = CALL_I32 @_Unwind_CallPersonality, %37:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    DROP_I32 killed %36:i32, implicit-def $arguments
+    %29:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %22:i32 = LOAD_I32 2, @__wasm_lpad_context + 8, %29:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack :: (dereferenceable load 4 from `i32* getelementptr inbounds ({ i32, i8*, i32 }, { i32, i8*, i32 }* @__wasm_lpad_context, i32 0, i32 2)`)
+    %28:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %23:i32 = NE_I32 %22:i32, %28:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    BR_IF %bb.5, %23:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack
+
+  bb.4:
+  ; predecessors: %bb.3
+    successors: %bb.8
+
+    %39:i32 = GET_LOCAL_I32 0, implicit-def $arguments
+    %38:i32 = CALL_I32 @__cxa_begin_catch, %39:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    DROP_I32 killed %38:i32, implicit-def $arguments
+    CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    BR %bb.8, implicit-def $arguments
+
+  bb.5:
+  ; predecessors: %bb.3
+    successors: %bb.6
+
+    CALL_VOID @__cxa_rethrow, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    RETHROW %bb.6, implicit-def $arguments
+
+  bb.6 (landing-pad):
+  ; predecessors: %bb.2, %bb.5
+
+    CATCH_ALL implicit-def $arguments
+    CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    RETHROW_TO_CALLER implicit-def $arguments
+  ; CHECK-LABEL: bb.6 (landing-pad):
+    ; CHECK-NEXT: END_TRY
+
+  bb.7:
+  ; predecessors: %bb.1
+
+    CALL_VOID @__cxa_rethrow, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    RETHROW_TO_CALLER implicit-def $arguments
+  ; CHECK-LABEL: bb.7:
+    ; CHECK-NEXT: END_TRY
+    ; CHECK: RETHROW 3
+
+  bb.8:
+  ; predecessors: %bb.2, %bb.4
+    successors: %bb.9
+
+    CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+
+  bb.9:
+  ; predecessors: %bb.0, %bb.8
+
+    RETURN_VOID implicit-def dead $arguments
+  ; CHECK-LABEL: bb.9:
+    ; CHECK-NEXT: END_TRY
+...
+---
+
+# A loop within a try.
+#  try {
+#    for (int i = 0; i < n; ++i)
+#      may_throw();
+#  } catch (...) {
+#  }
+name: test2
+# CHECK-LABEL: name: test2
+liveins:
+  - { reg: '$arguments', reg: '$value_stack' }
+body: |
+  bb.0:
+    successors: %bb.1, %bb.4
+
+    %18:i32 = CONST_I32 0, implicit-def dead $arguments
+    SET_LOCAL_I32 1, %18:i32, implicit-def $arguments
+    %14:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %19:i32 = GET_LOCAL_I32 0, implicit-def $arguments
+    %9:i32 = GE_S_I32 %14:i32, %19:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    BR_IF %bb.4, %9:i32, implicit-def $arguments
+
+  bb.1:
+  ; predecessors: %bb.0, %bb.3
+    successors: %bb.3, %bb.2
+
+    CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    BR %bb.3, implicit-def $arguments
+  ; CHECK-LABEL: bb.1:
+    ; CHECK: LOOP
+    ; CHECK: TRY
+    ; CHECK-NEXT: CALL_VOID @may_throw
+
+  bb.2 (landing-pad):
+  ; predecessors: %bb.1
+    successors: %bb.4
+
+    %11:i32 = CATCH_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %22:i32 = CALL_I32 @__cxa_begin_catch, %11:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def $value_stack, implicit $value_stack
+    DROP_I32 killed %22:i32, implicit-def $arguments
+    CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    BR %bb.4, implicit-def $arguments
+
+  bb.3:
+  ; predecessors: %bb.1
+    successors: %bb.1, %bb.4
+
+    %20:i32 = GET_LOCAL_I32 1, implicit-def $arguments
+    %17:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %16:i32 = ADD_I32 %20:i32, %17:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %15:i32 = TEE_LOCAL_I32 1, %16:i32, implicit-def $arguments
+    %21:i32 = GET_LOCAL_I32 0, implicit-def $arguments
+    %10:i32 = GE_S_I32 %15:i32, %21:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    BR_UNLESS %bb.1, %10:i32, implicit-def $arguments
+  ; CHECK-LABEL: bb.3:
+    ; CHECK: END_TRY
+
+  bb.4:
+  ; predecessors: %bb.2, %bb.0, %bb.3
+
+    RETURN_VOID implicit-def dead $arguments
+...
+---
+
+# A loop within a catch
+#  try {
+#    may_throw();
+#  } catch (...) {
+#    for (int i = 0; i < n; ++i)
+#      dont_throw();
+#  }
+name: test3
+# CHECK-LABEL: name: test3
+liveins:
+  - { reg: '$arguments', reg: '$value_stack' }
+body: |
+  bb.0:
+    successors: %bb.4, %bb.1
+
+    CALL_VOID @may_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    BR %bb.4, implicit-def $arguments
+  ; CHECK-LABEL: bb.0:
+    ; CHECK: TRY
+    ; CHECK-NEXT: CALL_VOID @may_throw
+
+  bb.1 (landing-pad):
+  ; predecessors: %bb.0
+    successors: %bb.2, %bb.3
+
+    %9:i32 = CATCH_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %18:i32 = CALL_I32 @__cxa_begin_catch, %9:i32, implicit-def dead $arguments, implicit $sp32, implicit $sp64, implicit-def $value_stack, implicit $value_stack
+    DROP_I32 killed %18:i32, implicit-def $arguments
+    %19:i32 = CONST_I32 0, implicit-def dead $arguments
+    SET_LOCAL_I32 1, %19:i32, implicit-def $arguments
+    %14:i32 = CONST_I32 0, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %20:i32 = GET_LOCAL_I32 0, implicit-def $arguments
+    %10:i32 = GE_S_I32 %14:i32, %20:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    BR_IF %bb.3, %10:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack
+
+  bb.2:
+  ; predecessors: %bb.1, %bb.2
+    successors: %bb.2, %bb.3
+
+    CALL_VOID @dont_throw, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+    %21:i32 = GET_LOCAL_I32 1, implicit-def $arguments
+    %17:i32 = CONST_I32 1, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %16:i32 = ADD_I32 %21:i32, %17:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    %15:i32 = TEE_LOCAL_I32 1, %16:i32, implicit-def $arguments
+    %22:i32 = GET_LOCAL_I32 0, implicit-def $arguments
+    %11:i32 = GE_S_I32 %15:i32, %22:i32, implicit-def dead $arguments, implicit-def $value_stack, implicit $value_stack
+    BR_UNLESS %bb.2, %11:i32, implicit-def $arguments, implicit-def $value_stack, implicit $value_stack
+
+  bb.3:
+  ; predecessors: %bb.1, %bb.2
+    successors: %bb.4
+
+    CALL_VOID @__cxa_end_catch, implicit-def dead $arguments, implicit $sp32, implicit $sp64
+
+  bb.4:
+  ; predecessors: %bb.0, %bb.3
+
+    RETURN_VOID implicit-def dead $arguments
+  ; CHECK-LABEL: bb.4:
+    ; CHECK: END_TRY

llvm/trunk/test/CodeGen/WebAssembly/exception.ll

 ; CHECK-NEXT: i32.const $push0=, 0
 ; CHECK-NEXT: throw 0, $pop0
 define void @test_throw() {
   call void @llvm.wasm.throw(i32 0, i8* null)
   ret void
 }
 
 ; CHECK-LABEL: test_catch_rethrow:
+; CHECK:   try
 ; CHECK:   call      foo@FUNCTION
 ; CHECK:   i32.catch     $push{{.+}}=, 0
 ; CHECK-DAG:   i32.store  __wasm_lpad_context
 ; CHECK-DAG:   i32.store  __wasm_lpad_context+4
 ; CHECK:   i32.call  $push{{.+}}=, _Unwind_CallPersonality@FUNCTION
 ; CHECK:   i32.call  $push{{.+}}=, __cxa_begin_catch@FUNCTION
 ; CHECK:   call      __cxa_end_catch@FUNCTION
 ; CHECK:   call      __cxa_rethrow@FUNCTION
 ; CHECK-NEXT:   rethrow
+; CHECK:   end_try
 define void @test_catch_rethrow() 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
 
rethrow:                                          ; preds = %catch.start
   call void @__cxa_rethrow() [ "funclet"(token %1) ]
   unreachable
 
 try.cont:                                         ; preds = %entry, %catch
   ret void
 }
 
 ; CHECK-LABEL: test_cleanup:
+; CHECK:   try
 ; CHECK:   call      foo@FUNCTION
 ; CHECK:   catch_all
 ; CHECK:   i32.call  $push{{.+}}=, _ZN7CleanupD1Ev@FUNCTION
 ; CHECK:   rethrow
+; CHECK:   end_try
 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)