[WebAssembly] Fix more ExceptionInfo grouping bugs

[aheejin]

Summary

This fixes two bugs in WebAssemblyExceptionInfo grouping, created by
D97247. These two bugs are not easy to split into two different CLs,
because tests that fail for one also tend to fail for the other.

• In D97247, when fixing ExceptionInfo grouping by taking out the unwind destination' exception from the unwind src's exception, we just iterated the BBs in the function order, but this was incorrect; this changes it to dominator tree preorder. Please refer to the comments in the code for the reason and an example.

• After this subexception-taking-out fix, there still can be remaining BBs we have to take out. When Exception B is taken out of Exception A (because EHPad B is the unwind destination of EHPad A), there can still be BBs within Exception A that are reachable from Exception B, which also should be taken out. Please refer to the comments in the code for more detailed explanation on why this can happen. To make this possible, this splits WebAssemblyException::addBlock into two parts: adding to a set and adding to a vector. We need to iterate on BBs within a WebAssemblyException to fix this, so we add BBs to sets first. But we add BBs to vectors later after we fix all incorrectness because deleting BBs from vectors is expensive. I considered removing the vector from WebAssemblyException, but it was not easy because this class has to maintain a similar interface with MachineLoop to be wrapped into a single interface SortRegion, which is used in CFGSort.

Other misc. drive-by fixes:

• Make WebAssemblyExceptionInfo do not even run when wasm EH is not used or the function doesn't have any EH pads, not to waste time
• Add LLVM_DEBUG lines for easy debugging
• Fix preds comments in cfg-stackify-eh.ll
• Fix __cxa_throw's signature in cfg-stackify-eh.ll

Fixes https://github.com/emscripten-core/emscripten/issues/13554.

[aheejin]

clang-tidy fix

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp

163

167

207

I expected to see code copying the contents of the block set to the block vector, but I don't see that. Do the set and the vector have different contents, or am I missing something else?

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.h

48

If we expect there to be few blocks, then perhaps the cost of deleting them from the vector wouldn't be too bad? Alternatively, we could also "remove" blocks by replacing them in the vector with nullptr, then compact the vector and remove the nullptrs just once at the end. That might be more complicated then just adding this set, though.

[aheejin]

Address comments

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp

207

We can do it that way. We are just using a map from BB to exception (look at getExceptionFor below, in line 210) to do that now.

So previously the code was

for (auto DomNode : post_order(&MDT)) {
  MachineBasicBlock *MBB = DomNode->getBlock();
  WebAssemblyException *WE = getExceptionFor(MBB);
  for (; WE; WE = WE->getParentException())
    WE->addBlock(MBB);
}

And addBlock was doing this:

Blocks.push_back(MBB);
BlockSet.insert(MBB);

Now we are doing the same thing in two steps.

for (auto DomNode : post_order(&MDT)) {
  MachineBasicBlock *MBB = DomNode->getBlock();
  WebAssemblyException *WE = getExceptionFor(MBB);
  for (; WE; WE = WE->getParentException())
    WE->addToBlockSet(MBB);
}

...
... Fix incorrect mappings ...
...

for (auto DomNode : post_order(&MDT)) {
  MachineBasicBlock *MBB = DomNode->getBlock();
  WebAssemblyException *WE = getExceptionFor(MBB);
  for (; WE; WE = WE->getParentException())
    WE->addToBlockVector(MBB);
}

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.h

48

The number of blocks varies greatly. There are many exceptions with fewer than 8 BBs so I set it to 8, but it does not mean I think that will be the median. There are functions dozens of BBs are within the catch part, and removing a block from those vectors will be expensive. Also when we remove a BB from, say, Exception A, it can involve multiple removal, because the BB's innermost containing exception might not be Exception A. If Exception A > B > C and BB belongs to C and we want to remove BB from Exception A, we have to remove BB form all A, B, and C's vectors.

Yes, I think removing things by setting them to nullptr and compressing the vector later is OK too. I just think the set is more convenient for now.. MachineLoop also keeps both a set and vector, even though it doesn't mean we should do the same. (I couldn't remove the vector because SortRegion was expecting some unified interface on it, but I think we can remove the set without affecting SortRegion, but yeah, it's just convenient to keep it..)

I also thought about removing the vector and using sets only within SortRegion but it was tricky due to some constness difference; MachineLoop's vector contains MachineBasicBlock* but its set contains const MachineBasicBlock*...

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp

207

I see, thanks. Either way is fine with me.

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.h

48

I agree that using a set seems reasonable, especially given the precedent in MachineBasicBlock. Thanks for the info!

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.h

 // An exception catch part is defined as a BB with catch instruction and all
 // other BBs dominated by this BB.
 class WebAssemblyException {
   MachineBasicBlock *EHPad = nullptr;
 
   WebAssemblyException *ParentException = nullptr;
   std::vector<std::unique_ptr<WebAssemblyException>> SubExceptions;
   std::vector<MachineBasicBlock *> Blocks;
-  SmallPtrSet<const MachineBasicBlock *, 8> BlockSet;
+  SmallPtrSet<MachineBasicBlock *, 8> BlockSet;
 
 public:
   WebAssemblyException(MachineBasicBlock *EHPad) : EHPad(EHPad) {}
   WebAssemblyException(const WebAssemblyException &) = delete;
   const WebAssemblyException &operator=(const WebAssemblyException &) = delete;
 
   MachineBasicBlock *getEHPad() const { return EHPad; }
   MachineBasicBlock *getHeader() const { return EHPad; }
   WebAssemblyException *getParentException() const { return ParentException; }
   void setParentException(WebAssemblyException *WE) { ParentException = WE; }
 
   bool contains(const WebAssemblyException *WE) const {
     if (WE == this)
       return true;
     if (!WE)
       return false;
     return contains(WE->getParentException());
   }
   bool contains(const MachineBasicBlock *MBB) const {
     return BlockSet.count(MBB);
   }
 
+  void addToBlocksSet(MachineBasicBlock *MBB) { BlockSet.insert(MBB); }
+  void removeFromBlocksSet(MachineBasicBlock *MBB) { BlockSet.erase(MBB); }
+  void addToBlocksVector(MachineBasicBlock *MBB) { Blocks.push_back(MBB); }
   void addBlock(MachineBasicBlock *MBB) {
     Blocks.push_back(MBB);
     BlockSet.insert(MBB);
   }
   ArrayRef<MachineBasicBlock *> getBlocks() const { return Blocks; }
   using block_iterator = typename ArrayRef<MachineBasicBlock *>::const_iterator;
   block_iterator block_begin() const { return getBlocks().begin(); }
   block_iterator block_end() const { return getBlocks().end(); }
   inline iterator_range<block_iterator> blocks() const {
     return make_range(block_begin(), block_end());
   }
   unsigned getNumBlocks() const { return Blocks.size(); }
   std::vector<MachineBasicBlock *> &getBlocksVector() { return Blocks; }
+  SmallPtrSetImpl<MachineBasicBlock *> &getBlocksSet() { return BlockSet; }
 
-  const std::vector<std::unique_ptr<WebAssemblyException>> &getSubExceptions() const {
+  const std::vector<std::unique_ptr<WebAssemblyException>> &
+  getSubExceptions() const {
     return SubExceptions;
   }
   std::vector<std::unique_ptr<WebAssemblyException>> &getSubExceptions() {
     return SubExceptions;
   }
   void addSubException(std::unique_ptr<WebAssemblyException> E) {
     SubExceptions.push_back(std::move(E));
   }
public:
   bool empty() const { return TopLevelExceptions.empty(); }
 
   // Return the innermost exception that MBB lives in. If the block is not in an
   // exception, null is returned.
   WebAssemblyException *getExceptionFor(const MachineBasicBlock *MBB) const {
     return BBMap.lookup(MBB);
   }
 
-  void changeExceptionFor(MachineBasicBlock *MBB, WebAssemblyException *WE) {
+  void changeExceptionFor(const MachineBasicBlock *MBB,
+                          WebAssemblyException *WE) {
     if (!WE) {
       BBMap.erase(MBB);
       return;
     }
     BBMap[MBB] = WE;
   }
 
   void addTopLevelException(std::unique_ptr<WebAssemblyException> WE) {

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp

 #include "WebAssemblyExceptionInfo.h"
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssemblyUtilities.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/CodeGen/MachineDominanceFrontier.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/WasmEHFuncInfo.h"
 #include "llvm/InitializePasses.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/Target/TargetMachine.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "wasm-exception-info"
 
 char WebAssemblyExceptionInfo::ID = 0;
 
 INITIALIZE_PASS_BEGIN(WebAssemblyExceptionInfo, DEBUG_TYPE,
                       "WebAssembly Exception Information", true, true)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
 INITIALIZE_PASS_END(WebAssemblyExceptionInfo, DEBUG_TYPE,
                     "WebAssembly Exception Information", true, true)
 
 bool WebAssemblyExceptionInfo::runOnMachineFunction(MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "********** Exception Info Calculation **********\n"
                        "********** Function: "
                     << MF.getName() << '\n');
   releaseMemory();
+  if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() !=
+          ExceptionHandling::Wasm ||
+      !MF.getFunction().hasPersonalityFn())
+    return false;
   auto &MDT = getAnalysis<MachineDominatorTree>();
   auto &MDF = getAnalysis<MachineDominanceFrontier>();
   recalculate(MF, MDT, MDF);
+  LLVM_DEBUG(dump());
+  return false;
+}
+
+// Check if Dst is reachable from Src using BFS. Search only within BBs
+// dominated by Header.
+static bool isReachableAmongDominated(const MachineBasicBlock *Src,
+                                      const MachineBasicBlock *Dst,
+                                      const MachineBasicBlock *Header,
+                                      const MachineDominatorTree &MDT) {
+  assert(MDT.dominates(Header, Dst));
+  SmallVector<const MachineBasicBlock *, 8> WL;
+  SmallPtrSet<const MachineBasicBlock *, 8> Visited;
+  WL.push_back(Src);
+
+  while (!WL.empty()) {
+    const auto *MBB = WL.pop_back_val();
+    if (MBB == Dst)
+      return true;
+    Visited.insert(MBB);
+    for (auto *Succ : MBB->successors())
+      if (!Visited.count(Succ) && MDT.dominates(Header, Succ))
+        WL.push_back(Succ);
+  }
   return false;
 }
 
 void WebAssemblyExceptionInfo::recalculate(
     MachineFunction &MF, MachineDominatorTree &MDT,
     const MachineDominanceFrontier &MDF) {
   // Postorder traversal of the dominator tree.
   SmallVector<std::unique_ptr<WebAssemblyException>, 8> Exceptions;
void WebAssemblyExceptionInfo::recalculate(
   // by an EH pad. But in case the EH pad's unwind destination does not have any
   // children outside of the exception, that unwind destination ends up also
   // being dominated by the EH pad and included in the exception, which is not
   // semantically correct, because it unwinds/rethrows into an inner scope.
   //
   // Here we extract those unwind destinations from their (incorrect) parent
   // exception. Note that the unwind destinations may not be an immediate
   // children of the parent exception, so we have to traverse the parent chain.
+  //
+  // We should traverse BBs in the preorder of the dominator tree, because
+  // otherwise the result can be incorrect. For example, when there are three
+  // exceptions A, B, and C and A > B > C (> is subexception relationship here),
+  // and A's unwind destination is B and B's is C. When we visit B before A, we
+  // end up extracting C only out of B but not out of A.
   const auto *EHInfo = MF.getWasmEHFuncInfo();
-  for (auto &MBB : MF) {
-    if (!MBB.isEHPad())
+  DenseMap<WebAssemblyException *, WebAssemblyException *> UnwindWEMap;
+  for (auto *DomNode : depth_first(&MDT)) {
+    MachineBasicBlock *EHPad = DomNode->getBlock();
+    if (!EHPad->isEHPad())
       continue;
-    auto *EHPad = &MBB;
     if (!EHInfo->hasUnwindDest(EHPad))
       continue;
     auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
     auto *WE = getExceptionFor(EHPad);
-    auto *UnwindDestWE = getExceptionFor(UnwindDest);
-    if (WE->contains(UnwindDestWE)) {
+    auto *UnwindWE = getExceptionFor(UnwindDest);
+    if (WE->contains(UnwindWE)) {
+      UnwindWEMap[WE] = UnwindWE;
+      LLVM_DEBUG(dbgs() << "ExceptionInfo fix: " << WE->getEHPad()->getNumber()
+                        << "." << WE->getEHPad()->getName()
+                        << "'s exception is taken out of "
+                        << UnwindWE->getEHPad()->getNumber() << "."
+                        << UnwindWE->getEHPad()->getName() << "'s exception\n");
       if (WE->getParentException())
-        UnwindDestWE->setParentException(WE->getParentException());
+        UnwindWE->setParentException(WE->getParentException());
       else
-        UnwindDestWE->setParentException(nullptr);
+        UnwindWE->setParentException(nullptr);
+    }
+  }
+
+  // Add BBs to exceptions' block set first
+  for (auto *DomNode : post_order(&MDT)) {
+    MachineBasicBlock *MBB = DomNode->getBlock();
+    WebAssemblyException *WE = getExceptionFor(MBB);
+    for (; WE; WE = WE->getParentException())
+      WE->addToBlocksSet(MBB);
+  }
+
+  // After fixing subexception relationship between unwind destinations above,
+  // there can still be remaining discrepancies.
+  //
+  // For example, suppose Exception A is dominated by EHPad A and Exception B is
+  // dominated by EHPad B. EHPad A's unwind destination is EHPad B, but because
+  // EHPad B is dominated by EHPad A, the initial grouping makes Exception B a
+  // subexception of Exception A, and we fix it by taking Exception B out of
+  // Exception A above. But there can still be remaining BBs within Exception A
+  // that are reachable from Exception B. These BBs semantically don't belong
+  // to Exception A and were not a part of 'catch' clause or cleanup code in the
+  // original code, but they just happened to be grouped within Exception A
+  // because they were dominated by EHPad A. We fix this case by taking those
+  // BBs out of the incorrect exception and all its subexceptions that it
+  // belongs to.
+  for (auto &KV : UnwindWEMap) {
+    WebAssemblyException *WE = KV.first;
+    WebAssemblyException *UnwindWE = KV.second;
+
+    for (auto *MBB : WE->getBlocksSet()) {
+      if (MBB->isEHPad()) {
+        // If this assertion is triggered, it would be a violation of scoping
+        // rules in ll files, because this means an instruction in an outer
+        // scope tries to unwind to an EH pad in an inner scope.
+        assert(!isReachableAmongDominated(UnwindWE->getEHPad(), MBB,
+                                          WE->getEHPad(), MDT) &&
+               "Outer scope unwinds to inner scope. Bug in scope rules?");
+        continue;
+      }
+      if (isReachableAmongDominated(UnwindWE->getEHPad(), MBB, WE->getEHPad(),
+                                    MDT)) {
+        LLVM_DEBUG(dbgs() << "Remainder BB: " << MBB->getNumber() << "."
+                          << MBB->getName() << " is ");
+        WebAssemblyException *InnerWE = getExceptionFor(MBB);
+        while (InnerWE != WE) {
+          LLVM_DEBUG(dbgs()
+                     << "  removed from " << InnerWE->getEHPad()->getNumber()
+                     << "." << InnerWE->getEHPad()->getName()
+                     << "'s exception\n");
+          InnerWE->removeFromBlocksSet(MBB);
+          InnerWE = InnerWE->getParentException();
+        }
+        WE->removeFromBlocksSet(MBB);
+        LLVM_DEBUG(dbgs() << "  removed from " << WE->getEHPad()->getNumber()
+                          << "." << WE->getEHPad()->getName()
+                          << "'s exception\n");
+        changeExceptionFor(MBB, WE->getParentException());
+        if (WE->getParentException())
+          WE->getParentException()->addToBlocksSet(MBB);
+      }
     }
   }
 
-  // Add BBs to exceptions
+  // Add BBs to exceptions' block vector
   for (auto DomNode : post_order(&MDT)) {
     MachineBasicBlock *MBB = DomNode->getBlock();
     WebAssemblyException *WE = getExceptionFor(MBB);
     for (; WE; WE = WE->getParentException())
-      WE->addBlock(MBB);
+      WE->addToBlocksVector(MBB);
   }
 
   SmallVector<WebAssemblyException*, 8> ExceptionPointers;
   ExceptionPointers.reserve(Exceptions.size());
 
   // Add subexceptions to exceptions
   for (auto &WE : Exceptions) {
     ExceptionPointers.push_back(WE.get());

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

 ;           <- (b) The br destination should be remapped to here
 ;
 ; The test was reduced by bugpoint and should not crash in CFGStackify.
 define void @test21() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   br i1 undef, label %if.then, label %if.end12
 
 if.then:                                          ; preds = %entry
-  invoke void @__cxa_throw() #1
+  invoke void @__cxa_throw(i8* null, i8* null, i8* null) #1
           to label %unreachable unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %if.then
   %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(token %1)
   %3 = call i32 @llvm.wasm.get.ehselector(token %1)
   catchret from %1 to label %catchret.dest
 
 catchret.dest:                                    ; preds = %catch.start
   invoke void @foo()
           to label %invoke.cont unwind label %catch.dispatch4
 
 invoke.cont:                                      ; preds = %catchret.dest
-  invoke void @__cxa_throw() #1
+  invoke void @__cxa_throw(i8* null, i8* null, i8* null) #1
           to label %unreachable unwind label %catch.dispatch4
 
 catch.dispatch4:                                  ; preds = %invoke.cont, %catchret.dest
   %4 = catchswitch within none [label %catch.start5] unwind to caller
 
 catch.start5:                                     ; preds = %catch.dispatch4
   %5 = catchpad within %4 [i8* bitcast (i8** @_ZTIi to i8*)]
   %6 = call i8* @llvm.wasm.get.exception(token %5)

 
 invoke.cont14:                                    ; preds = %if.end12
   br label %try.cont23
 
 ehcleanup:                                        ; preds = %try.cont23, %rethrow19, %catch.dispatch16
   %12 = cleanuppad within none []
   cleanupret from %12 unwind to caller
 
-unreachable:                                      ; preds = %if.then, %invoke.cont, %rethrow19
+unreachable:                                      ; preds = %rethrow19, %invoke.cont, %if.then
   unreachable
 }
 
 ; Regression test for WasmEHFuncInfo's reverse mapping bug. 'UnwindDestToSrc'
 ; should return a vector and not a single BB, which was incorrect.
 ; This was reduced by bugpoint and should not crash in CFGStackify.
 define void @test22() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   invoke void @foo()
           to label %invoke.cont unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %entry
   %0 = catchswitch within none [label %catch.start] unwind label %ehcleanup22
 
 catch.start:                                      ; preds = %catch.dispatch
   %1 = catchpad within %0 [i8* bitcast (i8** @_ZTIi to i8*)]
   %2 = call i8* @llvm.wasm.get.exception(token %1)
   %3 = call i32 @llvm.wasm.get.ehselector(token %1)
-  invoke void @__cxa_throw() #1 [ "funclet"(token %1) ]
+  invoke void @__cxa_throw(i8* null, i8* null, i8* null) #1 [ "funclet"(token %1) ]
           to label %unreachable unwind label %catch.dispatch2
 
 catch.dispatch2:                                  ; preds = %catch.start
   %4 = catchswitch within %1 [label %catch.start3] unwind label %ehcleanup
 
 catch.start3:                                     ; preds = %catch.dispatch2
   %5 = catchpad within %4 [i8* bitcast (i8** @_ZTIi to i8*)]
   %6 = call i8* @llvm.wasm.get.exception(token %5)
   %7 = call i32 @llvm.wasm.get.ehselector(token %5)
   catchret from %5 to label %try.cont
 
 try.cont:                                         ; preds = %catch.start3
   invoke void @foo() [ "funclet"(token %1) ]
           to label %invoke.cont8 unwind label %ehcleanup
 
 invoke.cont8:                                     ; preds = %try.cont
-  invoke void @__cxa_throw() #1 [ "funclet"(token %1) ]
+  invoke void @__cxa_throw(i8* null, i8* null, i8* null) #1 [ "funclet"(token %1) ]
           to label %unreachable unwind label %catch.dispatch11
 
 catch.dispatch11:                                 ; preds = %invoke.cont8
   %8 = catchswitch within %1 [label %catch.start12] unwind label %ehcleanup
 
 catch.start12:                                    ; preds = %catch.dispatch11
   %9 = catchpad within %8 [i8* bitcast (i8** @_ZTIi to i8*)]
   %10 = call i8* @llvm.wasm.get.exception(token %9)
   %11 = call i32 @llvm.wasm.get.ehselector(token %9)
   unreachable
 
 invoke.cont:                                      ; preds = %entry
   unreachable
 
-ehcleanup:                                        ; preds = %try.cont, %catch.dispatch11, %catch.dispatch2
+ehcleanup:                                        ; preds = %catch.dispatch11, %try.cont, %catch.dispatch2
   %12 = cleanuppad within %1 []
   cleanupret from %12 unwind label %ehcleanup22
 
 ehcleanup22:                                      ; preds = %ehcleanup, %catch.dispatch
   %13 = cleanuppad within none []
   cleanupret from %13 unwind to caller
 
-unreachable:                                      ; preds = %catch.start, %invoke.cont8
+unreachable:                                      ; preds = %invoke.cont8, %catch.start
+  unreachable
+}
+
+; void test23() {
+;   try {
+;     try {
+;       throw 0;
+;     } catch (int) {
+;     }
+;   } catch (int) {
+;   }
+; }
+;
+; Regression test for a WebAssemblyException grouping bug. After catchswitches
+; are removed, EH pad catch.start2 is dominated by catch.start, but because
+; catch.start2 is the unwind destination of catch.start, it should not be
+; included in catch.start's exception. Also, after we take catch.start2's
+; exception out of catch.start's exception, we have to take out try.cont8 out of
+; catch.start's exception, because it has a predecessor in catch.start2.
+define void @test23() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  %exception = call i8* @__cxa_allocate_exception(i32 4) #0
+  %0 = bitcast i8* %exception to i32*
+  store i32 0, i32* %0, align 16
+  invoke void @__cxa_throw(i8* %exception, i8* bitcast (i8** @_ZTIi to i8*), i8* null) #1
+          to label %unreachable unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %entry
+  %1 = catchswitch within none [label %catch.start] unwind label %catch.dispatch1
+
+catch.start:                                      ; preds = %catch.dispatch
+  %2 = catchpad within %1 [i8* bitcast (i8** @_ZTIi to i8*)]
+  %3 = call i8* @llvm.wasm.get.exception(token %2)
+  %4 = call i32 @llvm.wasm.get.ehselector(token %2)
+  %5 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) #0
+  %matches = icmp eq i32 %4, %5
+  br i1 %matches, label %catch, label %rethrow
+
+catch:                                            ; preds = %catch.start
+  %6 = call i8* @__cxa_begin_catch(i8* %3) #0 [ "funclet"(token %2) ]
+  %7 = bitcast i8* %6 to i32*
+  %8 = load i32, i32* %7, align 4
+  call void @__cxa_end_catch() #0 [ "funclet"(token %2) ]
+  catchret from %2 to label %catchret.dest
+
+catchret.dest:                                    ; preds = %catch
+  br label %try.cont
+
+rethrow:                                          ; preds = %catch.start
+  invoke void @llvm.wasm.rethrow() #1 [ "funclet"(token %2) ]
+          to label %unreachable unwind label %catch.dispatch1
+
+catch.dispatch1:                                  ; preds = %rethrow, %catch.dispatch
+  %9 = catchswitch within none [label %catch.start2] unwind to caller
+
+catch.start2:                                     ; preds = %catch.dispatch1
+  %10 = catchpad within %9 [i8* bitcast (i8** @_ZTIi to i8*)]
+  %11 = call i8* @llvm.wasm.get.exception(token %10)
+  %12 = call i32 @llvm.wasm.get.ehselector(token %10)
+  %13 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) #0
+  %matches3 = icmp eq i32 %12, %13
+  br i1 %matches3, label %catch5, label %rethrow4
+
+catch5:                                           ; preds = %catch.start2
+  %14 = call i8* @__cxa_begin_catch(i8* %11) #0 [ "funclet"(token %10) ]
+  %15 = bitcast i8* %14 to i32*
+  %16 = load i32, i32* %15, align 4
+  call void @__cxa_end_catch() #0 [ "funclet"(token %10) ]
+  catchret from %10 to label %catchret.dest7
+
+catchret.dest7:                                   ; preds = %catch5
+  br label %try.cont8
+
+rethrow4:                                         ; preds = %catch.start2
+  call void @llvm.wasm.rethrow() #1 [ "funclet"(token %10) ]
+  unreachable
+
+try.cont8:                                        ; preds = %try.cont, %catchret.dest7
+  ret void
+
+try.cont:                                         ; preds = %catchret.dest
+  br label %try.cont8
+
+unreachable:                                      ; preds = %rethrow, %entry
+  unreachable
+}
+
+; Test for WebAssemblyException grouping. This test is hand-modified to generate
+; this structure:
+; catch.start dominates catch.start4 and catch.start4 dominates catch.start12,
+; so the after dominator-based grouping, we end up with:
+; catch.start's exception > catch4.start's exception > catch12.start's exception
+; (> here represents subexception relationship)
+;
+; But the unwind destination chain is catch.start -> catch.start4 ->
+; catch.start12. So all these subexception relationship should be deconstructed.
+; We have to make sure to take out catch.start4's exception out of catch.start's
+; exception first, before taking out catch.start12's exception out of
+; catch.start4's exception; otherwise we end up with an incorrect relationship
+; of catch.start's exception > catch.start12's exception.
+define void @test24() personality i8* bitcast (i32 (...)*
+@__gxx_wasm_personality_v0 to i8*) {
+entry:
+  invoke void @foo()
+          to label %invoke.cont unwind label %catch.dispatch
+
+invoke.cont:                                      ; preds = %entry
+  invoke void @foo()
+          to label %invoke.cont1 unwind label %catch.dispatch
+
+invoke.cont1:                                     ; preds = %invoke.cont
+  invoke void @foo()
+          to label %try.cont18 unwind label %catch.dispatch
+
+catch.dispatch11:                                 ; preds = %rethrow6, %catch.dispatch3
+  %0 = catchswitch within none [label %catch.start12] unwind to caller
+
+catch.start12:                                    ; preds = %catch.dispatch11
+  %1 = catchpad within %0 [i8* bitcast (i8** @_ZTIi to i8*)]
+  %2 = call i8* @llvm.wasm.get.exception(token %1)
+  %3 = call i32 @llvm.wasm.get.ehselector(token %1)
+  %4 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) #0
+  %matches13 = icmp eq i32 %3, %4
+  br i1 %matches13, label %catch15, label %rethrow14
+
+catch15:                                          ; preds = %catch.start12
+  %5 = call i8* @__cxa_begin_catch(i8* %2) #0 [ "funclet"(token %1) ]
+  %6 = bitcast i8* %5 to i32*
+  %7 = load i32, i32* %6, align 4
+  call void @__cxa_end_catch() #0 [ "funclet"(token %1) ]
+  catchret from %1 to label %try.cont18
+
+rethrow14:                                        ; preds = %catch.start12
+  call void @llvm.wasm.rethrow() #1 [ "funclet"(token %1) ]
+  unreachable
+
+catch.dispatch3:                                  ; preds = %rethrow, %catch.dispatch
+  %8 = catchswitch within none [label %catch.start4] unwind label %catch.dispatch11
+
+catch.start4:                                     ; preds = %catch.dispatch3
+  %9 = catchpad within %8 [i8* bitcast (i8** @_ZTIi to i8*)]
+  %10 = call i8* @llvm.wasm.get.exception(token %9)
+  %11 = call i32 @llvm.wasm.get.ehselector(token %9)
+  %12 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) #0
+  %matches5 = icmp eq i32 %11, %12
+  br i1 %matches5, label %catch7, label %rethrow6
+
+catch7:                                           ; preds = %catch.start4
+  %13 = call i8* @__cxa_begin_catch(i8* %10) #0 [ "funclet"(token %9) ]
+  %14 = bitcast i8* %13 to i32*
+  %15 = load i32, i32* %14, align 4
+  call void @__cxa_end_catch() #0 [ "funclet"(token %9) ]
+  catchret from %9 to label %try.cont18
+
+rethrow6:                                         ; preds = %catch.start4
+  invoke void @llvm.wasm.rethrow() #1 [ "funclet"(token %9) ]
+          to label %unreachable unwind label %catch.dispatch11
+
+catch.dispatch:                                   ; preds = %invoke.cont1, %invoke.cont, %entry
+  %16 = catchswitch within none [label %catch.start] unwind label %catch.dispatch3
+
+catch.start:                                      ; preds = %catch.dispatch
+  %17 = catchpad within %16 [i8* bitcast (i8** @_ZTIi to i8*)]
+  %18 = call i8* @llvm.wasm.get.exception(token %17)
+  %19 = call i32 @llvm.wasm.get.ehselector(token %17)
+  %20 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) #0
+  %matches = icmp eq i32 %19, %20
+  br i1 %matches, label %catch, label %rethrow
+
+catch:                                            ; preds = %catch.start
+  %21 = call i8* @__cxa_begin_catch(i8* %18) #0 [ "funclet"(token %17) ]
+  %22 = bitcast i8* %21 to i32*
+  %23 = load i32, i32* %22, align 4
+  call void @__cxa_end_catch() #0 [ "funclet"(token %17) ]
+  catchret from %17 to label %try.cont18
+
+rethrow:                                          ; preds = %catch.start
+  invoke void @llvm.wasm.rethrow() #1 [ "funclet"(token %17) ]
+          to label %unreachable unwind label %catch.dispatch3
+
+try.cont18:                                       ; preds = %catch, %catch7, %catch15, %invoke.cont1
+  ret void
+
+unreachable:                                      ; preds = %rethrow, %rethrow6
   unreachable
 }
 
 ; Check if the unwind destination mismatch stats are correct
-; NOSORT: 20 wasm-cfg-stackify    - Number of call unwind mismatches found
+; NOSORT: 23 wasm-cfg-stackify    - Number of call unwind mismatches found
 ; NOSORT:  4 wasm-cfg-stackify    - Number of catch unwind mismatches found
 
 declare void @foo()
 declare void @bar()
 declare i32 @baz()
 declare i32 @qux(i32)
 declare void @quux(i32)
 declare void @fun(i32)

 ; Function Attrs: nounwind
 declare %class.MyClass* @_ZN7MyClassC2ERKS_(%class.MyClass* returned, %class.MyClass* dereferenceable(4)) #0
 
 declare i32 @__gxx_wasm_personality_v0(...)
 ; Function Attrs: nounwind
 declare i8* @llvm.wasm.get.exception(token) #0
 ; Function Attrs: nounwind
 declare i32 @llvm.wasm.get.ehselector(token) #0
+declare i8* @__cxa_allocate_exception(i32) #0
 ; Function Attrs: noreturn
-declare void @__cxa_throw() #1
+declare void @__cxa_throw(i8*, i8*, i8*) #1
 ; Function Attrs: noreturn
 declare void @llvm.wasm.rethrow() #1
 ; Function Attrs: nounwind
 declare i32 @llvm.eh.typeid.for(i8*) #0
 
 declare i8* @__cxa_begin_catch(i8*)
 declare void @__cxa_end_catch()
 declare i8* @__cxa_get_exception_ptr(i8*)