[WebAssembly] Fix ExceptionInfo grouping again

[aheejin]

Summary

This is a case D97677 missed. When taking out remaining BBs that are
reachable from already-taken-out exceptions (because they are not
subexcptions but unwind destinations), I assumed the remaining BBs are
not EH pads, but they can be. For example,

try {
  try {
    throw 0;
  } catch (int) { // (a)
  }
} catch (int) {   // (b)
}
try {
  foo();
} catch (int) {   // (c)
}

In this code, (b) is the unwind destination of (a) so its exception is
taken out of (a)'s exception, But even though the next try-catch is not
inside the first two-level try-catches, because the first try always
throws, its continuation BB is unreachable and the whole rest of the
function is dominated by EH pad (a), including EH pad (c). So after we
take out of (b)'s exception out of (a)'s, we also need to take out (c)'s
exception out of (a)'s, because (c) is reachable from (b).

This adds one more step before what we did for remaining BBs in D97677;
it traverses EH pads first to take subexceptions out of their incorrect
parent exception. It's the same thing as D97677, but because we can do
this before we add BBs to exceptions' sets, we don't need to fix sets
and only need to fix parent exception pointers.

Other changes are variable name changes (I changed WE -> SrcWE,
UnwindWE -> DstWE for clarity), some comment changes, and a drive-by
fix in a bug in a LLVM_DEBUG print statement.

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

[dschuff]

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

1560

I don't see any CHECKs here. I guess the test is just to ensure there are no assert failures?

[dschuff]

LGTM assuming the test is what you intended.

[aheejin]

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

1560

Yes these regression tests are mostly to check they don't crash. Checking specific CFGStackify output is not very informative or not easy to verify by eyes. Maybe one more informative thing to dump or check is WebAssemblyExceptionInfo::dump().. Maybe we can dump that info and check that.

[dschuff]

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

1560

that sounds like it could be useful. One thing to watch out for on that, is that (IIRC) some dumping methods get compiled away in release builds. I'm not sure what the common practice is for using those in tests.

llvm/lib/Target/WebAssembly/WebAssemblyExceptionInfo.cpp

void WebAssemblyExceptionInfo::recalculate(
   // 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();
-  DenseMap<WebAssemblyException *, WebAssemblyException *> UnwindWEMap;
+  SmallVector<std::pair<WebAssemblyException *, WebAssemblyException *>>
+      UnwindWEVec;
   for (auto *DomNode : depth_first(&MDT)) {
     MachineBasicBlock *EHPad = DomNode->getBlock();
     if (!EHPad->isEHPad())
       continue;
     if (!EHInfo->hasUnwindDest(EHPad))
       continue;
     auto *UnwindDest = EHInfo->getUnwindDest(EHPad);
-    auto *WE = getExceptionFor(EHPad);
-    auto *UnwindWE = getExceptionFor(UnwindDest);
-    if (WE->contains(UnwindWE)) {
-      UnwindWEMap[WE] = UnwindWE;
-      LLVM_DEBUG(dbgs() << "ExceptionInfo fix: " << WE->getEHPad()->getNumber()
-                        << "." << WE->getEHPad()->getName()
+    auto *SrcWE = getExceptionFor(EHPad);
+    auto *DstWE = getExceptionFor(UnwindDest);
+    if (SrcWE->contains(DstWE)) {
+      UnwindWEVec.push_back(std::make_pair(SrcWE, DstWE));
+      LLVM_DEBUG(dbgs() << "Unwind destination ExceptionInfo fix:\n  "
+                        << DstWE->getEHPad()->getNumber() << "."
+                        << DstWE->getEHPad()->getName()
                         << "'s exception is taken out of "
-                        << UnwindWE->getEHPad()->getNumber() << "."
-                        << UnwindWE->getEHPad()->getName() << "'s exception\n");
-      if (WE->getParentException())
-        UnwindWE->setParentException(WE->getParentException());
-      else
-        UnwindWE->setParentException(nullptr);
-    }
+                        << SrcWE->getEHPad()->getNumber() << "."
+                        << SrcWE->getEHPad()->getName() << "'s exception\n");
+      DstWE->setParentException(SrcWE->getParentException());
     }
-
-  // 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
+  // to Exception A and were not a part of this '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;
+  //
+  // 1. First, we take out remaining incorrect subexceptions. This part is
+  // easier, because we haven't added BBs to exceptions yet, we only need to
+  // change parent exception pointer.
+  for (auto *DomNode : depth_first(&MDT)) {
+    MachineBasicBlock *EHPad = DomNode->getBlock();
+    if (!EHPad->isEHPad())
+      continue;
+    auto *WE = getExceptionFor(EHPad);
 
-    for (auto *MBB : WE->getBlocksSet()) {
+    // For each source EHPad -> unwind destination EHPad
+    for (auto &P : UnwindWEVec) {
+      auto *SrcWE = P.first;
+      auto *DstWE = P.second;
+      // If WE (the current EH pad's exception) is still contained in SrcWE but
+      // reachable from DstWE that was taken out of SrcWE above, we have to take
+      // out WE out of SrcWE too.
+      if (WE != SrcWE && SrcWE->contains(WE) && !DstWE->contains(WE) &&
+          isReachableAmongDominated(DstWE->getEHPad(), EHPad, SrcWE->getEHPad(),
+                                    MDT)) {
+        LLVM_DEBUG(dbgs() << "Remaining reachable ExceptionInfo fix:\n  "
+                          << WE->getEHPad()->getNumber() << "."
+                          << WE->getEHPad()->getName()
+                          << "'s exception is taken out of "
+                          << SrcWE->getEHPad()->getNumber() << "."
+                          << SrcWE->getEHPad()->getName() << "'s exception\n");
+        WE->setParentException(SrcWE->getParentException());
+      }
+    }
+  }
+
+  // Add BBs to exceptions' block set. This is a preparation to take out
+  // remaining incorect BBs from exceptions, because we need to iterate over BBs
+  // for each exception.
+  for (auto *DomNode : post_order(&MDT)) {
+    MachineBasicBlock *MBB = DomNode->getBlock();
+    WebAssemblyException *WE = getExceptionFor(MBB);
+    for (; WE; WE = WE->getParentException())
+      WE->addToBlocksSet(MBB);
+  }
+
+  // 2. We take out remaining individual BBs out. Now we have added BBs to each
+  // exceptions' BlockSet, when we take a BB out of an exception, we need to fix
+  // those sets too.
+  for (auto &P : UnwindWEVec) {
+    auto *SrcWE = P.first;
+    auto *DstWE = P.second;
+
+    for (auto *MBB : SrcWE->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?");
+        assert(!isReachableAmongDominated(DstWE->getEHPad(), MBB,
+                                          SrcWE->getEHPad(), MDT) &&
+               "We already handled EH pads above");
         continue;
       }
-      if (isReachableAmongDominated(UnwindWE->getEHPad(), MBB, WE->getEHPad(),
+      if (isReachableAmongDominated(DstWE->getEHPad(), MBB, SrcWE->getEHPad(),
                                     MDT)) {
         LLVM_DEBUG(dbgs() << "Remainder BB: " << MBB->getNumber() << "."
-                          << MBB->getName() << " is ");
+                          << MBB->getName() << " is\n");
         WebAssemblyException *InnerWE = getExceptionFor(MBB);
-        while (InnerWE != WE) {
+        while (InnerWE != SrcWE) {
           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()
+        SrcWE->removeFromBlocksSet(MBB);
+        LLVM_DEBUG(dbgs() << "  removed from " << SrcWE->getEHPad()->getNumber()
+                          << "." << SrcWE->getEHPad()->getName()
                           << "'s exception\n");
-        changeExceptionFor(MBB, WE->getParentException());
-        if (WE->getParentException())
-          WE->getParentException()->addToBlocksSet(MBB);
+        changeExceptionFor(MBB, SrcWE->getParentException());
+        if (SrcWE->getParentException())
+          SrcWE->getParentException()->addToBlocksSet(MBB);
       }
     }
   }
 
   // Add BBs to exceptions' block vector
   for (auto DomNode : post_order(&MDT)) {
     MachineBasicBlock *MBB = DomNode->getBlock();
     WebAssemblyException *WE = getExceptionFor(MBB);

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

 
 try.cont18:                                       ; preds = %catch, %catch7, %catch15, %invoke.cont1
   ret void
 
 unreachable:                                      ; preds = %rethrow, %rethrow6
   unreachable
 }
 
+; void test25() {
+;   try {
+;     try {
+;       throw 0;
+;     } catch (int) { // (a)
+;     }
+;   } catch (int) {   // (b)
+;   }
+;   try {
+;     foo();
+;   } catch (int) {   // (c)
+;   }
+; }
+;
+; Regression test for an ExceptionInfo grouping bug. Because the first (inner)
+; try always throws, both EH pads (b) (catch.start2) and (c) (catch.start10) are
+; dominated by EH pad (a) (catch.start), even though they are not semantically
+; contained in (a)'s exception. Because (a)'s unwind destination is (b), (b)'s
+; exception is taken out of (a)'s. But because (c) is reachable from (b), we
+; should make sure to take out (c)'s exception out of (a)'s exception too.
+define void @test25() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  %exception = call i8* @__cxa_allocate_exception(i32 4) #1
+  %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) #3
+          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*)) #1
+  %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) #1 [ "funclet"(token %2) ]
+  %7 = bitcast i8* %6 to i32*
+  %8 = load i32, i32* %7, align 4
+  call void @__cxa_end_catch() #1 [ "funclet"(token %2) ]
+  catchret from %2 to label %try.cont8
+
+rethrow:                                          ; preds = %catch.start
+  invoke void @llvm.wasm.rethrow() #3 [ "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*)) #1
+  %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) #1 [ "funclet"(token %10) ]
+  %15 = bitcast i8* %14 to i32*
+  %16 = load i32, i32* %15, align 4
+  call void @__cxa_end_catch() #1 [ "funclet"(token %10) ]
+  catchret from %10 to label %try.cont8
+
+rethrow4:                                         ; preds = %catch.start2
+  call void @llvm.wasm.rethrow() #3 [ "funclet"(token %10) ]
+  unreachable
+
+try.cont8:                                        ; preds = %catch, %catch5
+  invoke void @foo()
+          to label %try.cont16 unwind label %catch.dispatch9
+
+catch.dispatch9:                                  ; preds = %try.cont8
+  %17 = catchswitch within none [label %catch.start10] unwind to caller
+
+catch.start10:                                    ; preds = %catch.dispatch9
+  %18 = catchpad within %17 [i8* bitcast (i8** @_ZTIi to i8*)]
+  %19 = call i8* @llvm.wasm.get.exception(token %18)
+  %20 = call i32 @llvm.wasm.get.ehselector(token %18)
+  %21 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*)) #1
+  %matches11 = icmp eq i32 %20, %21
+  br i1 %matches11, label %catch13, label %rethrow12
+
+catch13:                                          ; preds = %catch.start10
+  %22 = call i8* @__cxa_begin_catch(i8* %19) #1 [ "funclet"(token %18) ]
+  %23 = bitcast i8* %22 to i32*
+  %24 = load i32, i32* %23, align 4
+  call void @__cxa_end_catch() #1 [ "funclet"(token %18) ]
+  catchret from %18 to label %try.cont16
+
+rethrow12:                                        ; preds = %catch.start10
+  call void @llvm.wasm.rethrow() #3 [ "funclet"(token %18) ]
+  unreachable
+
+try.cont16:                                       ; preds = %try.cont8, %catch13
+  ret void
+
+unreachable:                                      ; preds = %rethrow, %entry
+  unreachable
+}
+
 ; Check if the unwind destination mismatch stats are correct
 ; 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)