[WebAssembly] Fix catch unwind mismatches

[aheejin]

Summary

This fixes unwind destination mismatches caused by 'catch'es, which
occur when a foreign exception is not caught by the nearest catch and
the next outer catch is not the catch it should unwind to, or the next
unwind destination should be the caller instead. This kind of mismatches
didn't exist in the previous version of the spec, because in the
previous spec catch was effectively catch_all, catching all
exceptions.

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

905–906

What is an example of when the split position could be before catch?

1267–1373

1268

1321–1322

~Is this supposed to be a continue?~ Oh, I see it's just there in service of the else ifs below. I found this confusing when I first saw it (especially without braces). I think it would be clearer if structured a different way.

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

905–906

When fixing catch mismatches. When an inner try is included in a body of an outer try:

bb0:
  try
    try
      ...
bb1 (ehpad):
    catch ...
      ...
bb2: (ehpad)
    end_try
  catch ...
    ...

Suppose we need to wrap the inner try with try-delegate:

bb0:
  try
    try          ;; new inst
      try
        ...
bb1 (ehpad):
      catch ...
        ...
bb-pre: (ehpad)  ;; new BB
      end_try
bb-delegate:     ;; new BB
    delegate    ;; new inst
bb2 (ehpad):
  catch ...
    ...

The split pos is before the catch in bb2. Because catch's BB should be preserved, because that's what WasmEHFuncInfo remembers.

1321–1322

The reason this is not a continue is it needs to run the common code at the very bottom:

EHPadStack.push_back(EHPad);

I can add the braces. Do you have any other restructuring suggestions?

[aheejin]

• Address comments

[aheejin]

rebase

[tlively]

Sorry for dropping this for such a long time!

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

905–906

I see, I was thinking that catch would always be at the beginning of a BB, but I hadn't considered that various end markers may precede it.

1321–1322

No, this looks clear now. Thanks!

llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

 #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/CodeGen/WasmEHFuncInfo.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/Target/TargetMachine.h"
 using namespace llvm;
 using WebAssembly::SortRegionInfo;
 
 #define DEBUG_TYPE "wasm-cfg-stackify"
 
 STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found");
+STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found");
 
 namespace {
 class WebAssemblyCFGStackify final : public MachineFunctionPass {
   StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MachineDominatorTree>();
     AU.addRequired<MachineLoopInfo>();
void WebAssemblyCFGStackify::addTryDelegate(MachineInstr *RangeBegin,
   auto SplitPos = std::next(RangeEnd->getIterator());
   if (SplitPos == EndBB->end()) {
     // If the range's end instruction is at the end of the BB, insert the new
     // delegate BB after the current BB.
     MF.insert(std::next(EndBB->getIterator()), DelegateBB);
     EndBB->addSuccessor(DelegateBB);
 
   } else {
+    // When the split pos is in the middle of a BB, we split the BB into two and
+    // put the 'delegate' BB in between. We normally create a split BB and make
+    // it a successor of the original BB (PostSplit == true), but in case the BB
+    // is an EH pad and the split pos is before 'catch', we should preserve the
+    // BB's property, including that it is an EH pad, in the later part of the
+    // BB, where 'catch' is. In this case we set PostSplit to false.
+    bool PostSplit = true;
+    if (EndBB->isEHPad()) {
+      for (auto I = MachineBasicBlock::iterator(SplitPos), E = EndBB->end();
+           I != E; ++I) {
+        if (WebAssembly::isCatch(I->getOpcode())) {
+          PostSplit = false;
+          break;
+        }
+      }
+    }
+
+    MachineBasicBlock *PreBB = nullptr, *PostBB = nullptr;
+    if (PostSplit) {
       // If the range's end instruction is in the middle of the BB, we split the
       // BB into two and insert the delegate BB in between.
       // - Before:
       // bb:
       //   range_end
       //   other_insts
       //
       // - After:
       // pre_bb: (previous 'bb')
       //   range_end
       // delegate_bb: (new)
       //   delegate
       // post_bb: (new)
       //   other_insts
-    MachineBasicBlock *PreBB = EndBB;
-    MachineBasicBlock *PostBB = MF.CreateMachineBasicBlock();
+      PreBB = EndBB;
+      PostBB = MF.CreateMachineBasicBlock();
       MF.insert(std::next(PreBB->getIterator()), PostBB);
       MF.insert(std::next(PreBB->getIterator()), DelegateBB);
       PostBB->splice(PostBB->end(), PreBB, SplitPos, PreBB->end());
       PostBB->transferSuccessors(PreBB);
+    } else {
+      // - Before:
+      // ehpad:
+      //   range_end
+      //   catch
+      //   ...
+      //
+      // - After:
+      // pre_bb: (new)
+      //   range_end
+      // delegate_bb: (new)
+      //   delegate
+      // post_bb: (previous 'ehpad')
+      //   catch
+      //   ...
+      assert(EndBB->isEHPad());
+      PreBB = MF.CreateMachineBasicBlock();
+      PostBB = EndBB;
+      MF.insert(PostBB->getIterator(), PreBB);
+      MF.insert(PostBB->getIterator(), DelegateBB);
+      PreBB->splice(PreBB->end(), PostBB, PostBB->begin(), SplitPos);
+      // We don't need to transfer predecessors of the EH pad to 'PreBB',
+      // because an EH pad's predecessors are all through unwind edges and they
+      // should still unwind to the EH pad, not PreBB.
+    }
     unstackifyVRegsUsedInSplitBB(*PreBB, *PostBB);
     PreBB->addSuccessor(DelegateBB);
     PreBB->addSuccessor(PostBB);
   }
 
   // Add 'delegate' instruction in the delegate BB created above.
   MachineInstr *Delegate = BuildMI(DelegateBB, RangeEnd->getDebugLoc(),
                                    TII.get(WebAssembly::DELEGATE))
bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) {
   //   ...
   // end_try
   //
   // Now if bar() throws, it is going to end up ip in bb2, not bb3, where it
   // is supposed to end up. We solve this problem by wrapping the mismatching
   // call with an inner try-delegate that rethrows the exception to the right
   // 'catch'.
   //
-  //
   // try
   //   try
   //     call @foo
   //     try               ;; (new)
   //       call @bar
   //     delegate 1 (bb3)  ;; (new)
   //   catch               ;; ehpad (bb2)
   //     ...
for (auto Range : TryRanges) {
       addTryDelegate(RangeBegin, RangeEnd, UnwindDest);
     }
   }
 
   return true;
 }
 
 bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) {
-  // TODO implement
+  // There is another kind of unwind destination mismatches besides call unwind
+  // mismatches, which we will call "catch unwind mismatches". See this example
+  // after the marker placement:
+  // try
+  //   try
+  //     call @foo
+  //   catch __cpp_exception  ;; ehpad A (next unwind dest: caller)
+  //     ...
+  //   end_try
+  // catch_all                ;; ehpad B
+  //   ...
+  // end_try
+  //
+  // 'call @foo's unwind destination is the ehpad A. But suppose 'call @foo'
+  // throws a foreign exception that is not caught by ehpad A, and its next
+  // destination should be the caller. But after control flow linearization,
+  // another EH pad can be placed in between (e.g. ehpad B here), making the
+  // next unwind destination incorrect. In this case, the  foreign exception
+  // will instead go to ehpad B and will be caught there instead. In this
+  // example the correct next unwind destination is the caller, but it can be
+  // another outer catch in other cases.
+  //
+  // There is no specific 'call' or 'throw' instruction to wrap with a
+  // try-delegate, so we wrap the whole try-catch-end with a try-delegate and
+  // make it rethrow to the right destination, as in the example below:
+  // try
+  //   try                     ;; (new)
+  //     try
+  //       call @foo
+  //     catch __cpp_exception ;; ehpad A (next unwind dest: caller)
+  //       ...
+  //     end_try
+  //   delegate 1 (caller)     ;; (new)
+  // catch_all                 ;; ehpad B
+  //   ...
+  // end_try
+
+  const auto *EHInfo = MF.getWasmEHFuncInfo();
+  SmallVector<const MachineBasicBlock *, 8> EHPadStack;
+  // For EH pads that have catch unwind mismatches, a map of <EH pad, its
+  // correct unwind destination>.
+  DenseMap<MachineBasicBlock *, MachineBasicBlock *> EHPadToUnwindDest;
+
+  for (auto &MBB : reverse(MF)) {
+    for (auto &MI : reverse(MBB)) {
+      if (MI.getOpcode() == WebAssembly::TRY)
+        EHPadStack.pop_back();
+      else if (MI.getOpcode() == WebAssembly::DELEGATE)
+        EHPadStack.push_back(&MBB);
+      else if (WebAssembly::isCatch(MI.getOpcode())) {
+        auto *EHPad = &MBB;
+
+        // catch_all always catches an exception, so we don't need to do
+        // anything
+        if (MI.getOpcode() == WebAssembly::CATCH_ALL) {
+        }
+
+        // This can happen when the unwind dest was removed during the
+        // optimization, e.g. because it was unreachable.
+        else if (EHPadStack.empty() && EHInfo->hasEHPadUnwindDest(EHPad)) {
+          LLVM_DEBUG(dbgs() << "EHPad (" << EHPad->getName()
+                            << "'s unwind destination does not exist anymore"
+                            << "\n\n");
+        }
+
+        // The EHPad's next unwind destination is the caller, but we incorrectly
+        // unwind to another EH pad.
+        else if (!EHPadStack.empty() && !EHInfo->hasEHPadUnwindDest(EHPad)) {
+          EHPadToUnwindDest[EHPad] = getFakeCallerBlock(MF);
+          LLVM_DEBUG(dbgs()
+                     << "- Catch unwind mismatch:\nEHPad = " << EHPad->getName()
+                     << "  Original dest = caller  Current dest = "
+                     << EHPadStack.back()->getName() << "\n\n");
+        }
+
+        // The EHPad's next unwind destination is an EH pad, whereas we
+        // incorrectly unwind to another EH pad.
+        else if (!EHPadStack.empty() && EHInfo->hasEHPadUnwindDest(EHPad)) {
+          auto *UnwindDest = EHInfo->getEHPadUnwindDest(EHPad);
+          if (EHPadStack.back() != UnwindDest) {
+            EHPadToUnwindDest[EHPad] = UnwindDest;
+            LLVM_DEBUG(dbgs() << "- Catch unwind mismatch:\nEHPad = "
+                              << EHPad->getName() << "  Original dest = "
+                              << UnwindDest->getName() << "  Current dest = "
+                              << EHPadStack.back()->getName() << "\n\n");
+          }
+        }
+
+        EHPadStack.push_back(EHPad);
+      }
+    }
+  }
+
+  assert(EHPadStack.empty());
+  if (EHPadToUnwindDest.empty())
     return false;
+  NumCatchUnwindMismatches += EHPadToUnwindDest.size();
+
+  for (auto &P : EHPadToUnwindDest) {
+    MachineBasicBlock *EHPad = P.first;
+    MachineBasicBlock *UnwindDest = P.second;
+    MachineInstr *Try = EHPadToTry[EHPad];
+    MachineInstr *EndTry = BeginToEnd[Try];
+    addTryDelegate(Try, EndTry, UnwindDest);
+  }
+
+  return true;
 }
 
 void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) {
   // Renumber BBs and recalculate ScopeTop info because new BBs might have been
   // created and inserted during fixing unwind mismatches.
   MF.RenumberBlocks();
   ScopeTops.clear();
   ScopeTops.resize(MF.getNumBlockIDs());

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

try.cont:                                         ; preds = %catch.start, %loop
   br label %loop
 }
 
 ; Some of test cases below are hand-tweaked by deleting some library calls to
 ; simplify tests and changing the order of basic blocks to cause unwind
 ; destination mismatches. And we use -wasm-disable-ehpad-sort to create maximum
 ; number of mismatches in several tests below.
 
+; - Call unwind mismatch
 ; 'call bar''s original unwind destination was 'C0', but after control flow
 ; linearization, its unwind destination incorrectly becomes 'C1'. We fix this by
 ; wrapping the call with a nested try-delegate that targets 'C0'.
+; - Catch unwind mismatch
+; If 'call foo' throws a foreign exception, it will not be caught by C1, and
+; should be rethrown to the caller. But after control flow linearization, it
+; will instead unwind to C0, an incorrect next EH pad. We wrap the whole
+; try-catch with try-delegate that rethrows an exception to the caller to fix
+; this.
 
 ; NOSORT-LABEL: test5
 ; NOSORT: try
-; NOSORT:   try
-; NOSORT:     call  foo
+; --- try-delegate starts (catch unwind mismatch)
+; NOSORT    try
+; NOSORT:     try
+; NOSORT:       call  foo
 ; --- try-delegate starts (call unwind mismatch)
-; NOSORT:     try
-; NOSORT:       call  bar
-; NOSORT:     delegate    1     # label/catch{{[0-9]+}}: down to catch[[C0:[0-9]+]]
+; NOSORT:       try
+; NOSORT:         call  bar
+; NOSORT:       delegate    2     # label/catch{{[0-9]+}}: down to catch[[C0:[0-9]+]]
 ; --- try-delegate ends (call unwind mismatch)
-; NOSORT:   catch   {{.*}}      # catch[[C1:[0-9]+]]:
-; NOSORT:   end_try
-; NOSORT: catch   {{.*}}        # catch[[C0]]:
+; NOSORT:     catch   {{.*}}      # catch[[C1:[0-9]+]]:
+; NOSORT:     end_try
+; NOSORT:   delegate    1         # label/catch{{[0-9]+}}: to caller
+; --- try-delegate ends (catch unwind mismatch)
+; NOSORT: catch   {{.*}}          # catch[[C0]]:
 ; NOSORT: end_try
 ; NOSORT: return
 
 define void @test5() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 bb0:
   invoke void @foo()
           to label %bb1 unwind label %catch.dispatch0
 

 }
 
 ; The same as test5, but we have one more call 'call @foo' in bb1 which unwinds
 ; to the caller. IN this case bb1 has two call unwind mismatches: 'call @foo'
 ; unwinds to the caller and 'call @bar' unwinds to catch C0.
 
 ; NOSORT-LABEL: test7
 ; NOSORT: try
-; NOSORT:   try
-; NOSORT:     call  foo
+; --- try-delegate starts (catch unwind mismatch)
+; NOSORT    try
+; NOSORT:     try
+; NOSORT:       call  foo
 ; --- try-delegate starts (call unwind mismatch)
-; NOSORT:     try
-; NOSORT:       call  foo
-; NOSORT:     delegate    2     # label/catch{{[0-9]+}}: to caller
+; NOSORT:       try
+; NOSORT:         call  foo
+; NOSORT:       delegate    3     # label/catch{{[0-9]+}}: to caller
 ; --- try-delegate ends (call unwind mismatch)
 ; --- try-delegate starts (call unwind mismatch)
-; NOSORT:     try
-; NOSORT:       call  bar
-; NOSORT:     delegate    1     # label/catch{{[0-9]+}}: down to catch[[C0:[0-9]+]]
+; NOSORT:       try
+; NOSORT:         call  bar
+; NOSORT:       delegate    2     # label/catch{{[0-9]+}}: down to catch[[C0:[0-9]+]]
 ; --- try-delegate ends (call unwind mismatch)
-; NOSORT:   catch   {{.*}}      # catch[[C1:[0-9]+]]:
-; NOSORT:   end_try
+; NOSORT:     catch   {{.*}}      # catch[[C1:[0-9]+]]:
+; NOSORT:     end_try
+; NOSORT:   delegate    1         # label/catch{{[0-9]+}}: to caller
+; --- try-delegate ends (catch unwind mismatch)
 ; NOSORT: catch   {{.*}}        # catch[[C0]]:
 ; NOSORT: end_try
 ; NOSORT: return
 
 define void @test7() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 bb0:
   invoke void @foo()
           to label %bb1 unwind label %catch.dispatch0
catch.start0:                                     ; preds = %catch.dispatch0
   %2 = call i8* @llvm.wasm.get.exception(token %1)
   %3 = call i32 @llvm.wasm.get.ehselector(token %1)
   catchret from %1 to label %try.cont
 
 try.cont:                                         ; preds = %catch.start0
   ret void
 }
 
-; When we have both kinds of EH pad unwind mismatches:
+; We have two call unwind unwind mismatches:
 ; - A may-throw instruction unwinds to an incorrect EH pad after linearizing the
 ;   CFG, when it is supposed to unwind to another EH pad.
 ; - A may-throw instruction unwinds to an incorrect EH pad after linearizing the
 ;   CFG, when it is supposed to unwind to the caller.
+; We also have a catch unwind mismatch: If an exception is not caught by the
+; first catch because it is a non-C++ exception, it shouldn't unwind to the next
+; catch, but it should unwind to the caller.
 
 ; NOSORT-LABEL: test10
 ; NOSORT: try
-; NOSORT:   try
-; NOSORT:     call  foo
+; --- try-delegate starts (catch unwind mismatch)
+; NOSORT:   try
+; NOSORT:     try
+; NOSORT:       call  foo
 ; --- try-delegate starts (call unwind mismatch)
-; NOSORT:     try
-; NOSORT:       call  bar
-; NOSORT:     delegate    1            # label/catch{{[0-9]+}}: down to catch[[C0:[0-9]+]]
+; NOSORT:       try
+; NOSORT:         call  bar
+; NOSORT:       delegate    2            # label/catch{{[0-9]+}}: down to catch[[C0:[0-9]+]]
 ; --- try-delegate ends (call unwind mismatch)
-; NOSORT:   catch
-; NOSORT:     call  {{.*}} __cxa_begin_catch
+; NOSORT:     catch
+; NOSORT:       call  {{.*}} __cxa_begin_catch
 ; --- try-delegate starts (call unwind mismatch)
-; NOSORT:     try
-; NOSORT:       call  __cxa_end_catch
-; NOSORT:     delegate    1            # label/catch{{[0-9]+}}: to caller
+; NOSORT:       try
+; NOSORT:         call  __cxa_end_catch
+; NOSORT:       delegate    2            # label/catch{{[0-9]+}}: to caller
 ; --- try-delegate ends (call unwind mismatch)
-; NOSORT:   end_try
-; NOSORT: catch  {{.*}}                # catch[[C0]]:
+; NOSORT:     end_try
+; NOSORT:   delegate    1                # label/catch{{[0-9]+}}: to caller
+; --- try-delegate ends (catch unwind mismatch)
+; NOSORT: catch  {{.*}}                  # catch[[C0]]:
 ; NOSORT:   call  {{.*}} __cxa_begin_catch
 ; NOSORT:   call  __cxa_end_catch
 ; NOSORT: end_try
 ; NOSORT: return
 
 define void @test10() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 bb0:
   invoke void @foo()

 ehcleanup:                                        ; preds = %if.then
   %0 = cleanuppad within none []
   %call3 = call %class.Object* @_ZN6ObjectD2Ev(%class.Object* %t) #4 [ "funclet"(token %0) ]
   cleanupret from %0 unwind to caller
 }
 
 ; Check if the unwind destination mismatch stats are correct
 ; NOSORT: 18 wasm-cfg-stackify    - Number of call unwind mismatches found
+; NOSORT:  3 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