[WebAssembly] Fix getBottom for loops

[aheejin]

Summary

When it was first created, CFGSort only made sure BBs in each
MachineLoop are sorted together. After we added exception support,
CFGSort now also sorts BBs in each WebAssemblyException, which
represents a catch block, together, and
Region class was introduced to be a thin wrapper for both
MachineLoop and WebAssemblyException.

But how we compute those loops and exceptions is different.
MachineLoopInfo is constructed using the standard loop computation
algorithm in LLVM; the definition of loop is "a set of BBs that are
dominated by a loop header and have a path back to the loop header". So
even if some BBs are semantically contained by a loop in the original
program, or in other words dominated by a loop header, if they don't
have a path back to the loop header, they are not considered a part of
the loop. For example, if a BB is dominated by a loop header but
contains call abort() or rethrow, it wouldn't have a path back to
the header, so it is not included in the loop.

But WebAssemblyException is wasm-specific data structure, and its
algorithm is simple: a WebAssemblyException consists of an EH pad and
all BBs dominated by the EH pad. So this scenario is possible: (This is
also the situation in the newly added test in cfg-stackify-eh.ll)

Loop L: header, A, ehpad, latch
Exception E: ehpad, latch, B

(B contains abort(), so it does not have a path back to the loop
header, so it is not included in L.)

And it is sorted in this order:

header
A
ehpad
latch
B

And when CFGStackify places end_loop or end_try markers, it
previously used WebAssembly::getBottom(), which returns the latest BB
in the sorted order, and placed the marker there. So in this case the
marker placements will be like this:

loop
  header
  try
    A
  catch
    ehpad
    latch
end_loop         <-- misplaced!
    B
  end_try

in which nesting between the loop and the exception is not correct.
end_loop marker has to be placed after B, and also after end_try.

Maybe the fundamental way to solve this problem is to come up with our
own algorithm for computing loop region too, in which we include all BBs
dominated by a loop header in a loop. But this takes a lot more effort.
The only thing we need to fix is actually, getBottom(). If we make it
return the right BB, which means in case of a loop, the latest BB of the
loop itself and all exceptions contained in there, we are good.

This renames Region and RegionInfo to SortRegion and
SortRegionInfo and extracts them into their own file. And add
getBottom to SortRegionInfo class, from which it can access
WebAssemblyExceptionInfo, so that it can compute a correct bottom
block for loops.

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblySortRegion.cpp

48–66

Most of WebAssemblySortRegion.h and cpp was preexisting and only moved, except for this method.

[aheejin]

This comment was removed by aheejin.

[dschuff]

LGTM!

llvm/lib/Target/WebAssembly/CMakeLists.txt

add_llvm_target(WebAssemblyCodeGen
   WebAssemblyRegisterInfo.cpp
   WebAssemblyRegColoring.cpp
   WebAssemblyRegNumbering.cpp
   WebAssemblyRegStackify.cpp
   WebAssemblyReplacePhysRegs.cpp
   WebAssemblyRuntimeLibcallSignatures.cpp
   WebAssemblySelectionDAGInfo.cpp
   WebAssemblySetP2AlignOperands.cpp
+  WebAssemblySortRegion.cpp
   WebAssemblyMemIntrinsicResults.cpp
   WebAssemblySubtarget.cpp
   WebAssemblyTargetMachine.cpp
   WebAssemblyTargetObjectFile.cpp
   WebAssemblyTargetTransformInfo.cpp
   WebAssemblyUtilities.cpp
 
   DEPENDS
   intrinsics_gen
 )
 
 add_subdirectory(AsmParser)
 add_subdirectory(Disassembler)
 add_subdirectory(MCTargetDesc)
 add_subdirectory(TargetInfo)

llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

 /// 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 "WebAssemblySortRegion.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;
+using WebAssembly::SortRegion;
+using WebAssembly::SortRegionInfo;
 
 #define DEBUG_TYPE "wasm-cfg-sort"
 
 // Option to disable EH pad first sorting. Only for testing unwind destination
 // mismatches in CFGStackify.
 static cl::opt<bool> WasmDisableEHPadSort(
     "wasm-disable-ehpad-sort", cl::ReallyHidden,
     cl::desc(
         "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),
     cl::init(false));
 
 namespace {
 
-// Wrapper for loops and exceptions
-class Region {
-public:
-  virtual ~Region() = default;
-  virtual MachineBasicBlock *getHeader() const = 0;
-  virtual bool contains(const MachineBasicBlock *MBB) const = 0;
-  virtual unsigned getNumBlocks() const = 0;
-  using block_iterator = typename ArrayRef<MachineBasicBlock *>::const_iterator;
-  virtual iterator_range<block_iterator> blocks() const = 0;
-  virtual bool isLoop() const = 0;
-};
-
-template <typename T> class ConcreteRegion : public Region {
-  const T *Region;
-
-public:
-  ConcreteRegion(const T *Region) : Region(Region) {}
-  MachineBasicBlock *getHeader() const override { return Region->getHeader(); }
-  bool contains(const MachineBasicBlock *MBB) const override {
-    return Region->contains(MBB);
-  }
-  unsigned getNumBlocks() const override { return Region->getNumBlocks(); }
-  iterator_range<block_iterator> blocks() const override {
-    return Region->blocks();
-  }
-  bool isLoop() const override { return false; }
-};
-
-template <> bool ConcreteRegion<MachineLoop>::isLoop() const { return true; }
-
-// This class has information of nested Regions; this is analogous to what
-// LoopInfo is for loops.
-class RegionInfo {
-  const MachineLoopInfo &MLI;
-  const WebAssemblyExceptionInfo &WEI;
-  DenseMap<const MachineLoop *, std::unique_ptr<Region>> LoopMap;
-  DenseMap<const WebAssemblyException *, std::unique_ptr<Region>> ExceptionMap;
-
-public:
-  RegionInfo(const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI)
-      : MLI(MLI), WEI(WEI) {}
-
-  // Returns a smallest loop or exception that contains MBB
-  const Region *getRegionFor(const MachineBasicBlock *MBB) {
-    const auto *ML = MLI.getLoopFor(MBB);
-    const auto *WE = WEI.getExceptionFor(MBB);
-    if (!ML && !WE)
-      return nullptr;
-    // We determine subregion relationship by domination of their headers, i.e.,
-    // if region A's header dominates region B's header, B is a subregion of A.
-    // WebAssemblyException contains BBs in all its subregions (loops or
-    // exceptions), but MachineLoop may not, because MachineLoop does not contain
-    // BBs that don't have a path to its header even if they are dominated by
-    // its header. So here we should use WE->contains(ML->getHeader()), but not
-    // ML->contains(WE->getHeader()).
-    if ((ML && !WE) || (ML && WE && WE->contains(ML->getHeader()))) {
-      // If the smallest region containing MBB is a loop
-      if (LoopMap.count(ML))
-        return LoopMap[ML].get();
-      LoopMap[ML] = std::make_unique<ConcreteRegion<MachineLoop>>(ML);
-      return LoopMap[ML].get();
-    } else {
-      // If the smallest region containing MBB is an exception
-      if (ExceptionMap.count(WE))
-        return ExceptionMap[WE].get();
-      ExceptionMap[WE] =
-          std::make_unique<ConcreteRegion<WebAssemblyException>>(WE);
-      return ExceptionMap[WE].get();
-    }
-  }
-};
-
 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>();
bool operator()(const MachineBasicBlock *A,
     }
 
     return A->getNumber() < B->getNumber();
   }
 };
 /// Bookkeeping for a region to help ensure that we don't mix blocks not
 /// dominated by the its header among its blocks.
 struct Entry {
-  const Region *TheRegion;
+  const SortRegion *TheRegion;
   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 class Region *R)
+  explicit Entry(const SortRegion *R)
       : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}
 };
 } // end anonymous namespace
 
 /// Sort the blocks, taking special care to make sure that regions 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,
   // from both queues.
   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
                 CompareBlockNumbers>
       Preferred;
   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
                 CompareBlockNumbersBackwards>
       Ready;
 
-  RegionInfo RI(MLI, WEI);
+  SortRegionInfo SRI(MLI, WEI);
   SmallVector<Entry, 4> Entries;
   for (MachineBasicBlock *MBB = &MF.front();;) {
-    const Region *R = RI.getRegionFor(MBB);
+    const SortRegion *R = SRI.getRegionFor(MBB);
     if (R) {
       // If MBB is a region header, add it to the active region list. We can't
       // put any blocks that it doesn't dominate until we see the end of the
       // region.
       if (R->getHeader() == MBB)
         Entries.push_back(Entry(R));
       // For each active region the block is in, decrement the count. If MBB is
       // the last block in an active region, take it off the list and pick up
for (MachineBasicBlock *MBB = &MF.front();;) {
     Next->moveAfter(MBB);
     maybeUpdateTerminator(MBB);
     MBB = Next;
   }
   assert(Entries.empty() && "Active sort region list not finished");
   MF.RenumberBlocks();
 
 #ifndef NDEBUG
-  SmallSetVector<const Region *, 8> OnStack;
+  SmallSetVector<const SortRegion *, 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 Region *Region = RI.getRegionFor(&MBB);
+    const SortRegion *Region = SRI.getRegionFor(&MBB);
 
     if (Region && &MBB == Region->getHeader()) {
       // Region header.
       if (Region->isLoop()) {
         // Loop header. The loop predecessor should be sorted above, and the
         // other predecessors should be backedges below.
         for (auto Pred : MBB.predecessors())
           assert(
if (Region && &MBB == Region->getHeader()) {
       assert(OnStack.insert(Region) &&
              "Regions should be declared at most once.");
 
     } else {
       // Not a region 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(RI.getRegionFor(&MBB)) &&
+      assert(OnStack.count(SRI.getRegionFor(&MBB)) &&
              "Blocks must be nested in their regions");
     }
-    while (OnStack.size() > 1 && &MBB == WebAssembly::getBottom(OnStack.back()))
+    while (OnStack.size() > 1 && &MBB == SRI.getBottom(OnStack.back()))
       OnStack.pop_back();
   }
   assert(OnStack.pop_back_val() == nullptr &&
          "The function entry block shouldn't actually be a region header");
   assert(OnStack.empty() &&
          "Control flow stack pushes and pops should be balanced.");
 #endif
 }

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

 /// In case we use exceptions, this pass also fixes mismatches in unwind
 /// destinations created during transforming CFG into wasm structured format.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "WebAssembly.h"
 #include "WebAssemblyExceptionInfo.h"
 #include "WebAssemblyMachineFunctionInfo.h"
+#include "WebAssemblySortRegion.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyUtilities.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/Target/TargetMachine.h"
 using namespace llvm;
+using WebAssembly::SortRegionInfo;
 
 #define DEBUG_TYPE "wasm-cfg-stackify"
 
 STATISTIC(NumUnwindMismatches, "Number of EH pad unwind mismatches found");
 
 namespace {
 class WebAssemblyCFGStackify final : public MachineFunctionPass {
   StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
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).
 void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) {
   MachineFunction &MF = *MBB.getParent();
   const auto &MLI = getAnalysis<MachineLoopInfo>();
+  const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
+  SortRegionInfo SRI(MLI, WEI);
   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);
+  MachineBasicBlock *Bottom = SRI.getBottom(Loop);
   auto Iter = std::next(Bottom->getIterator());
   if (Iter == MF.end()) {
     getAppendixBlock(MF);
     Iter = std::next(Bottom->getIterator());
   }
   MachineBasicBlock *AfterLoop = &*Iter;
 
   // Decide where in Header to put the LOOP.
if (!ScopeTops[AfterLoop->getNumber()])
     ScopeTops[AfterLoop->getNumber()] = &MBB;
 }
 
 void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) {
   assert(MBB.isEHPad());
   MachineFunction &MF = *MBB.getParent();
   auto &MDT = getAnalysis<MachineDominatorTree>();
   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  const auto &MLI = getAnalysis<MachineLoopInfo>();
   const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
+  SortRegionInfo SRI(MLI, WEI);
   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);
+  MachineBasicBlock *Bottom = SRI.getBottom(WE);
 
   auto Iter = std::next(Bottom->getIterator());
   if (Iter == MF.end()) {
     getAppendixBlock(MF);
     Iter = std::next(Bottom->getIterator());
   }
   MachineBasicBlock *Cont = &*Iter;
 

llvm/lib/Target/WebAssembly/WebAssemblySortRegion.h

+//===-- WebAssemblySortRegion.h - WebAssembly Sort SortRegion ----*- C++-*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This file implements regions used in CFGSort and CFGStackify.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYSORTREGION_H
+#define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYSORTREGION_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/iterator_range.h"
+
+namespace llvm {
+
+class MachineBasicBlock;
+class MachineLoop;
+class MachineLoopInfo;
+class WebAssemblyException;
+class WebAssemblyExceptionInfo;
+
+namespace WebAssembly {
+
+// Wrapper for loops and exceptions
+class SortRegion {
+public:
+  virtual ~SortRegion() = default;
+  virtual MachineBasicBlock *getHeader() const = 0;
+  virtual bool contains(const MachineBasicBlock *MBB) const = 0;
+  virtual unsigned getNumBlocks() const = 0;
+  using block_iterator = typename ArrayRef<MachineBasicBlock *>::const_iterator;
+  virtual iterator_range<block_iterator> blocks() const = 0;
+  virtual bool isLoop() const = 0;
+};
+
+template <typename T> class ConcreteSortRegion : public SortRegion {
+  const T *Unit;
+
+public:
+  ConcreteSortRegion(const T *Unit) : Unit(Unit) {}
+  MachineBasicBlock *getHeader() const override { return Unit->getHeader(); }
+  bool contains(const MachineBasicBlock *MBB) const override {
+    return Unit->contains(MBB);
+  }
+  unsigned getNumBlocks() const override { return Unit->getNumBlocks(); }
+  iterator_range<block_iterator> blocks() const override {
+    return Unit->blocks();
+  }
+  bool isLoop() const override { return false; }
+};
+
+// This class has information of nested SortRegions; this is analogous to what
+// LoopInfo is for loops.
+class SortRegionInfo {
+  friend class ConcreteSortRegion<MachineLoopInfo>;
+  friend class ConcreteSortRegion<WebAssemblyException>;
+
+  const MachineLoopInfo &MLI;
+  const WebAssemblyExceptionInfo &WEI;
+  DenseMap<const MachineLoop *, std::unique_ptr<SortRegion>> LoopMap;
+  DenseMap<const WebAssemblyException *, std::unique_ptr<SortRegion>>
+      ExceptionMap;
+
+public:
+  SortRegionInfo(const MachineLoopInfo &MLI,
+                 const WebAssemblyExceptionInfo &WEI)
+      : MLI(MLI), WEI(WEI) {}
+
+  // Returns a smallest loop or exception that contains MBB
+  const SortRegion *getRegionFor(const MachineBasicBlock *MBB);
+
+  // Return the "bottom" block among all blocks dominated by the region
+  // (MachineLoop or WebAssemblyException) header. This works when the entity is
+  // discontiguous.
+  MachineBasicBlock *getBottom(const SortRegion *R);
+  MachineBasicBlock *getBottom(const MachineLoop *ML);
+  MachineBasicBlock *getBottom(const WebAssemblyException *WE);
+};
+
+} // end namespace WebAssembly
+
+} // end namespace llvm
+
+#endif

llvm/lib/Target/WebAssembly/WebAssemblySortRegion.cpp

+#include "WebAssemblySortRegion.h"
+#include "WebAssemblyExceptionInfo.h"
+#include "llvm/CodeGen/MachineLoopInfo.h"
+
+using namespace llvm;
+using namespace WebAssembly;
+
+template <> bool ConcreteSortRegion<MachineLoop>::isLoop() const {
+  return true;
+}
+
+const SortRegion *SortRegionInfo::getRegionFor(const MachineBasicBlock *MBB) {
+  const auto *ML = MLI.getLoopFor(MBB);
+  const auto *WE = WEI.getExceptionFor(MBB);
+  if (!ML && !WE)
+    return nullptr;
+  // We determine subregion relationship by domination of their headers, i.e.,
+  // if region A's header dominates region B's header, B is a subregion of A.
+  // WebAssemblyException contains BBs in all its subregions (loops or
+  // exceptions), but MachineLoop may not, because MachineLoop does not
+  // contain BBs that don't have a path to its header even if they are
+  // dominated by its header. So here we should use
+  // WE->contains(ML->getHeader()), but not ML->contains(WE->getHeader()).
+  if ((ML && !WE) || (ML && WE && WE->contains(ML->getHeader()))) {
+    // If the smallest region containing MBB is a loop
+    if (LoopMap.count(ML))
+      return LoopMap[ML].get();
+    LoopMap[ML] = std::make_unique<ConcreteSortRegion<MachineLoop>>(ML);
+    return LoopMap[ML].get();
+  } else {
+    // If the smallest region containing MBB is an exception
+    if (ExceptionMap.count(WE))
+      return ExceptionMap[WE].get();
+    ExceptionMap[WE] =
+        std::make_unique<ConcreteSortRegion<WebAssemblyException>>(WE);
+    return ExceptionMap[WE].get();
+  }
+}
+
+MachineBasicBlock *SortRegionInfo::getBottom(const SortRegion *R) {
+  if (R->isLoop())
+    return getBottom(MLI.getLoopFor(R->getHeader()));
+  else
+    return getBottom(WEI.getExceptionFor(R->getHeader()));
+}
+
+MachineBasicBlock *SortRegionInfo::getBottom(const MachineLoop *ML) {
+  MachineBasicBlock *Bottom = ML->getHeader();
+  for (MachineBasicBlock *MBB : ML->blocks()) {
+    if (MBB->getNumber() > Bottom->getNumber())
+      Bottom = MBB;
+    // MachineLoop does not contain all BBs dominated by its header. BBs that
+    // don't have a path back to the loop header aren't included. But for the
+    // purpose of CFG sorting and stackification, we need a bottom BB among all
+    // BBs that are dominated by the loop header. So we check if there is any
+    // WebAssemblyException contained in this loop, and computes the most bottom
+    // BB of them all.
+    if (MBB->isEHPad()) {
+      MachineBasicBlock *ExBottom = getBottom(WEI.getExceptionFor(MBB));
+      if (ExBottom->getNumber() > Bottom->getNumber())
+        Bottom = ExBottom;
+    }
+  }
+  return Bottom;
+}
+
+MachineBasicBlock *SortRegionInfo::getBottom(const WebAssemblyException *WE) {
+  MachineBasicBlock *Bottom = WE->getHeader();
+  for (MachineBasicBlock *MBB : WE->blocks())
+    if (MBB->getNumber() > Bottom->getNumber())
+      Bottom = MBB;
+  return Bottom;
+}

llvm/lib/Target/WebAssembly/WebAssemblyUtilities.h

 /// utility functions.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYUTILITIES_H
 #define LLVM_LIB_TARGET_WEBASSEMBLY_WEBASSEMBLYUTILITIES_H
 
 #include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineFunction.h"
 
 namespace llvm {
 
 class WebAssemblyFunctionInfo;
 
 namespace WebAssembly {
 
 bool isChild(const MachineInstr &MI, const WebAssemblyFunctionInfo &MFI);
 bool mayThrow(const MachineInstr &MI);
 
 // Exception-related function names
 extern const char *const ClangCallTerminateFn;
 extern const char *const CxaBeginCatchFn;
 extern const char *const CxaRethrowFn;
 extern const char *const StdTerminateFn;
 extern const char *const PersonalityWrapperFn;
 
-/// Return the "bottom" block of an entity, which can be either a MachineLoop or
-/// WebAssemblyException. This differs from MachineLoop::getBottomBlock in that
-/// it works even if the entity is discontiguous.
-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;
-}
-
 /// Returns the operand number of a callee, assuming the argument is a call
 /// instruction.
 const MachineOperand &getCalleeOp(const MachineInstr &MI);
 
 } // end namespace WebAssembly
 
 } // end namespace llvm
 
 #endif

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

catch.start:                                      ; preds = %catch.dispatch
   %4 = call i8* @__cxa_begin_catch(i8* %2) #2 [ "funclet"(token %1) ]
   call void @__cxa_end_catch() [ "funclet"(token %1) ]
   catchret from %1 to label %try.cont
 
 try.cont:                                         ; preds = %catch.start, %for.end
   ret void
 }
 
+; Here an exception is semantically contained in a loop. 'ehcleanup' BB belongs
+; to the exception, but does not belong to the loop (because it does not have a
+; path back to the loop header), and is placed after the loop latch block
+; 'invoke.cont' intentionally. This tests if 'end_loop' marker is placed
+; correctly not right after 'invoke.cont' part but after 'ehcleanup' part,
+; NOSORT-LABEL: test18
+; NOSORT: loop
+; NOSORT: try
+; NOSORT: end_try
+; NOSORT: end_loop
+define void @test18(i32 %n) personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  br label %while.cond
+
+while.cond:                                       ; preds = %invoke.cont, %entry
+  %n.addr.0 = phi i32 [ %n, %entry ], [ %dec, %invoke.cont ]
+  %tobool = icmp ne i32 %n.addr.0, 0
+  br i1 %tobool, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  %dec = add nsw i32 %n.addr.0, -1
+  invoke void @foo()
+          to label %while.end unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %while.body
+  %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(token %1)
+  %3 = call i32 @llvm.wasm.get.ehselector(token %1)
+  %4 = call i8* @__cxa_begin_catch(i8* %2) [ "funclet"(token %1) ]
+  invoke void @__cxa_end_catch() [ "funclet"(token %1) ]
+          to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %catch.start
+  catchret from %1 to label %while.cond
+
+ehcleanup:                                        ; preds = %catch.start
+  %5 = cleanuppad within %1 []
+  %6 = call i8* @llvm.wasm.get.exception(token %5)
+  call void @__clang_call_terminate(i8* %6) [ "funclet"(token %5) ]
+  unreachable
+
+while.end:                                        ; preds = %while.body, %while.cond
+  ret void
+}
+
 ; Check if the unwind destination mismatch stats are correct
 ; NOSORT-STAT: 17 wasm-cfg-stackify    - Number of EH pad unwind mismatches found
 
 declare void @foo()
 declare void @bar()
 declare i32 @baz()
 declare i32 @qux(i32)
 declare void @quux(i32)