[WebAssembly] Add WebAssemblyLateEHPrepare pass

[aheejin]

Summary

Add WebAssemblyLateEHPrepare pass that does several small jobs for
exception handling. This runs before CFGSort, and is different from
WasmEHPrepare pass that runs before ISel, even though the names are
similar.

[aheejin]

fixes

[aheejin]

Removed a blank line

[aheejin]

rebase

[aheejin]

removed setIsEHFuncletEntry

[aheejin]

• Deleted successors of catch-all terminatepads

[aheejin]

• removed an unnecessary call from a test case

[aheejin]

• debug location fix

[aheejin]

@majnemer Continuing the discussion from D44134:

So the background was:
__clang_call_terminate is called within a cleanuppad. But cleanuppad does not give you an exception object, which __clang_call_terminate takes as an argument. So even if it is a cleanuppad, we added a wasm catch instruction there to catch an exception object. But this cleanuppad should be entered even when we catch a foreign (e.g. JavaScript) exception, which we have no exception object to deal with. So in that case we just directly all std::terminate.

So, when the clang-generated code is like

terminate:
  %exn = catch(0)
  call void @__clang_call_terminate(%exn)
  unreachable

processTerminatePads() appends one more terminatepad right after this terminatepad, like:

terminate-catchall:
  catch_all
  call @std::terminate
  unreachable

So the intention was, if we catch a C++ exception we go to terminate, and if we catch a foreign exception we end up in terminate-catchall. Here I also assumed that the terminatepad is a single BB, but as you noted, it may not be. But because this pass runs even before ExceptinInfo (D44134), this does not have the exception grouping information here.

Do you think I can merge the terminatepad into a single BB in this pass, so this duplication of terminatepad process will be easier? I can't think of a situation in which a terminatepad can have complicated control flows other than a few straight-line BBs. (Actually I can't even imagine what kind of llvm pass is gonna divide a single terminate into two or more, but we can't guarantee that can't happen, so..)

Also, the other thing is, I merge terminate pads if there are more than two of them in mergeTerminatePads() here. This is in principle violation of EH scope membership, but this happens after all MachineFunctionPasses and only remaining wasm passes after this are CFGSort and CFGStackify, so I guess it should be OK.

[aheejin]

• Make wasm.get.exception/ehselector intrinsic take a token argument

[aheejin]

• Rebased onto D44090
• Not this pass deletes the following unreachable instruction after adding a rethrow instruction.

[aheejin]

Planning two changes:

1. Handling of the terminate pad
2. Removing unreachable BB after rethrow

[aheejin]

• Added a method to ensure a terminate pad is a single BB
• Using WasmEHInfo, now this adds RETHROW or RETHROW_TO_CALLER instruction depending on its unwind destination
• Ensured a rethrow instruction is in the same BB with __cxa_rethrow() call and deleted all unreachable children
• In hoistCatches, added handling of a case when catch instruction is not in the EH pad BB anymore
• Now uses several utility functions in WebAssemblyUtilities.cpp
• Added helper functions
• Misc. improvements here and there

[aheejin]

• Delete an unreachable after rethrow

[dschuff]

lib/Target/WebAssembly/WebAssemblyExceptionPrepare.cpp

28

I didn't think about the confusing-ness of this name when we put it in originally; maybe we could call it 'WebAssemblyMachineEHPrepare' or 'WebAssemblyLateEHPrepare'

59

So a function can rethrow but not have a personality function?

110

'instruction is'

154

Would it make more sense to just have the rethrow inside of cxa_rethrow (at least if the destination is the caller)? It might save some on code size? I guess we would just have to put an 'unreachable' after the call and it wouldn't matter; or is there some other reason?

[aheejin]

• WebAssemblyExceptionPrepare -> WebAssemblyLateEHPrepare
• Typo fix

[aheejin]

lib/Target/WebAssembly/WebAssemblyExceptionPrepare.cpp

28

Hmm, not to be confused with WasmEHPrepare? Yeah, that makes sense.. I'll go with WebAssemblyLateEHPrepare because 'Machine' sounds like it has its same or similar counterpart in LLVM IR passes. (like, LoopInfo vs MachineLoopInfo)

59

A function has its associated personality function when it has an EH pad (landingpad or catchpad/cleanuppad). Functions that call __cxa_rethrow() can rethrow to the caller, in which case the function doesn't have an EH pad. I didn't want to run all the functions below needlessly in that case.

154

That is the spec question. The current implementation is based on the first proposal, in which rethrow can only be placed within a catch block. We can change this later if that is shown to save code size.

I'll do some experiments on that once I'm able to run things end-to-end, but I actually doubt if that would be saving much, because we can save one rethrow instruction if we put that within a function, but that also means we have to pass a first-class exception argument to __cxa_rethrow(), and to put that argument on the wasm stack we have to consume one more instruction anyway. And also, if we use first-class exception objects, now every catch clause has to have that if_except ~ else ~ end instruction sequence too, which also contributes to the code size.

Anyway, I'm not saying I'm against it though. I'm saying just the current implementation is based on the first proposal :$

[dschuff]

OK, the pass looks good; don't know if @majnemer has any more feedback on this or D44134?

[aheejin]

@majnemer Do you think the problem we discussed in this CL and D44134 have been resolved?
The comment that started the discussion is here. So basically I tried to ensure a terminatepad is a single BB in this prepare pass.

lib/Target/WebAssembly/WebAssemblyExceptionPrepare.cpp

 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssembly.h"
 #include "WebAssemblySubtarget.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "wasm-exception-prepare"
 
+static const char *const ClangCallTerminate = "__clang_call_terminate";
+static const char *const CxaRethrow = "__cxa_rethrow";
+static const char *const StdTerminate = "_ZSt9terminatev";
+
 namespace {
 class WebAssemblyExceptionPrepare final : public MachineFunctionPass {
   StringRef getPassName() const override {
     return "WebAssembly Prepare Exception";
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   bool replaceFuncletReturns(MachineFunction &MF);
+  bool hoistCatches(MachineFunction &MF);
+  bool addCatchAlls(MachineFunction &MF);
+  bool addRethrows(MachineFunction &MF);
+  bool mergeTerminatePads(MachineFunction &MF);
+  bool processTerminatePads(MachineFunction &MF);
 
 public:
   static char ID; // Pass identification, replacement for typeid
   WebAssemblyExceptionPrepare() : MachineFunctionPass(ID) {}
 };
 } // end anonymous namespace
 
 char WebAssemblyExceptionPrepare::ID = 0;
 INITIALIZE_PASS(WebAssemblyExceptionPrepare, DEBUG_TYPE,
                 "WebAssembly Exception Preparation", false, false)
 
 FunctionPass *llvm::createWebAssemblyExceptionPrepare() {
   return new WebAssemblyExceptionPrepare();
 }
 
 bool WebAssemblyExceptionPrepare::runOnMachineFunction(MachineFunction &MF) {
   bool Changed = false;
+  Changed |= addRethrows(MF);
   if (!MF.getFunction().hasPersonalityFn())
-    return false;
+    return Changed;
   Changed |= replaceFuncletReturns(MF);
-  // TODO More transformations will be added
+  Changed |= hoistCatches(MF);
+  Changed |= addCatchAlls(MF);
+  Changed |= mergeTerminatePads(MF);
+  Changed |= processTerminatePads(MF);
   return Changed;
 }
 
 bool WebAssemblyExceptionPrepare::replaceFuncletReturns(MachineFunction &MF) {
   bool Changed = false;
   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 
   for (auto &MBB : MF) {
case WebAssembly::CLEANUPRET: {
       TI->eraseFromParent();
       Changed = true;
       break;
     }
     }
   }
   return Changed;
 }
+
+// Hoist catch instructions to the beginning of the BBs
+bool WebAssemblyExceptionPrepare::hoistCatches(MachineFunction &MF) {
+  bool Changed = false;
+
+  for (auto &MBB : MF) {
+    if (!MBB.isEHPad())
+      continue;
+    assert(!MBB.empty() && "EH pad is empty");
+
+    auto InsertPt = MBB.begin();
+    while (InsertPt->isLabel())
+      InsertPt++;
+    MachineInstr *Catch = nullptr;
+    for (auto &MI : llvm::make_range(std::next(InsertPt), MBB.end()))
+      if (MI.getOpcode() == WebAssembly::CATCH_I32 ||
+          MI.getOpcode() == WebAssembly::CATCH_I64) {
+        Catch = &MI;
+        Changed = true;
+        break;
+      }
+    if (Catch)
+      MBB.insert(InsertPt, Catch->removeFromParent());
+  }
+  return Changed;
+}
+
+// Add catch_all to beginning of cleanup pads
+bool WebAssemblyExceptionPrepare::addCatchAlls(MachineFunction &MF) {
+  bool Changed = false;
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+
+  for (auto &MBB : MF) {
+    if (!MBB.isEHPad())
+      continue;
+    bool HasCatch = false;
+    for (auto &MI : MBB)
+      if (MI.getOpcode() == WebAssembly::CATCH_I32 ||
+          MI.getOpcode() == WebAssembly::CATCH_I64) {
+        HasCatch = true;
+        break;
+      }
+
+    if (!HasCatch) {
+      Changed = true;
+      BuildMI(MBB, MBB.begin(), MBB.begin()->getDebugLoc(),
+              TII.get(WebAssembly::CATCH_ALL));
+    }
+  }
+  return Changed;
+}
+
+// Add a 'rethrow' instruction after __cxa_rethrow() call
+bool WebAssemblyExceptionPrepare::addRethrows(MachineFunction &MF) {
+  bool Changed = false;
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  for (auto &MBB : MF)
+    for (auto &MI : MBB) {
+      if (!MI.isCall())
+        continue;
+      MachineOperand &CalleeOp = MI.getOperand(0);
+      if (CalleeOp.isGlobal() &&
+          CalleeOp.getGlobal()->getName() == CxaRethrow) {
+        auto InsertPt = std::next(MachineBasicBlock::iterator(MI));
+        while (InsertPt != MBB.end() && InsertPt->isLabel())
+          InsertPt++;
+        MachineInstr *Rethrow = BuildMI(MBB, InsertPt, MI.getDebugLoc(),
+                                        TII.get(WebAssembly::RETHROW))
+                                    .addImm(0);
+
+        // If the next instruction is an unreachable, delete it because rethrow
+        // itself is a terminator.
+        auto NextPt = std::next(MachineBasicBlock::iterator(Rethrow));
+        if (NextPt != MBB.end() &&
+            NextPt->getOpcode() == WebAssembly::UNREACHABLE)
+          NextPt->eraseFromParent();
+
+        Changed = true;
+        break;
+      }
+    }
+  return Changed;
+}
+
+// Merge multiple terminate pads into one for code size.
+bool WebAssemblyExceptionPrepare::mergeTerminatePads(MachineFunction &MF) {
+  std::vector<MachineBasicBlock *> TermPads;
+
+  for (auto &MBB : MF) {
+    if (!MBB.isEHPad())
+      continue;
+    for (auto &MI : MBB) {
+      if (!MI.isCall())
+        continue;
+      MachineOperand &CalleeOp = MI.getOperand(0);
+      if (CalleeOp.isGlobal() &&
+          CalleeOp.getGlobal()->getName() == ClangCallTerminate) {
+        TermPads.push_back(&MBB);
+        break;
+      }
+    }
+  }
+  if (TermPads.size() <= 1)
+    return false;
+
+  MachineBasicBlock *UniqueTermPad = TermPads.front();
+  for (auto *TermPad :
+       llvm::make_range(std::next(TermPads.begin()), TermPads.end())) {
+    SmallVector<MachineBasicBlock *, 2> Preds(TermPad->pred_begin(),
+                                              TermPad->pred_end());
+    for (auto *Pred : Preds)
+      Pred->replaceSuccessor(TermPad, UniqueTermPad);
+    TermPad->removeFromParent();
+  }
+  return true;
+}
+
+// Terminate pads are cleanup pads, so they should start with a 'catch_all'
+// instruction. But in the Itanium model, when we have a C++ exception object,
+// we pass them to __clang_call_terminate function, which calls __cxa_end_catch
+// and then std::terminate. This is the reason that terminate pads are generated
+// with not catch_all but a catch instruction in the earlier passes. Here we add
+// catch_all BB after that so we can also catch foreign exceptions.
+// For every terminate pad:
+//   exn = catch <c++ tag>
+//   call @__clang_call_terminate(exn);
+//   unreachable
+// We append this BB right after that:
+//   catch_all
+//   call @std::terminate
+//   unreachable
+bool WebAssemblyExceptionPrepare::processTerminatePads(MachineFunction &MF) {
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  std::vector<MachineBasicBlock *> TermPads;
+
+  for (auto &MBB : MF) {
+    if (!MBB.isEHPad())
+      continue;
+    for (auto &MI : MBB) {
+      if (!MI.isCall())
+        continue;
+      MachineOperand &CalleeOp = MI.getOperand(0);
+      if (CalleeOp.isGlobal() &&
+          CalleeOp.getGlobal()->getName() == ClangCallTerminate) {
+        TermPads.push_back(&MBB);
+        break;
+      }
+    }
+  }
+  if (TermPads.empty())
+    return false;
+
+  Function *StdTerminateFn =
+      MF.getFunction().getParent()->getFunction(StdTerminate);
+  assert(StdTerminateFn && "There is no std::terminate() function");
+  for (auto *CatchTermPad : TermPads) {
+    DebugLoc DL = CatchTermPad->findDebugLoc(CatchTermPad->begin());
+    auto *CatchAllTermPad = MF.CreateMachineBasicBlock();
+    MF.insert(std::next(MachineFunction::iterator(CatchTermPad)),
+              CatchAllTermPad);
+    CatchAllTermPad->setIsEHPad();
+    BuildMI(CatchAllTermPad, DL, TII.get(WebAssembly::CATCH_ALL));
+    BuildMI(CatchAllTermPad, DL, TII.get(WebAssembly::CALL_VOID))
+        .addGlobalAddress(StdTerminateFn);
+    BuildMI(CatchAllTermPad, DL, TII.get(WebAssembly::UNREACHABLE));
+    CatchTermPad->addSuccessor(CatchAllTermPad);
+  }
+  return true;
+}

test/CodeGen/WebAssembly/exception.ll

 ; CHECK-LABEL: test_throw:
 ; CHECK-NEXT: i32.const $push0=, 0
 ; CHECK-NEXT: throw 0, $pop0
 define void @test_throw() {
   call void @llvm.wasm.throw(i32 0, i8* null)
   ret void
 }
 
-; CHECK-LABEL: test_catch:
+; CHECK-LABEL: test_catch_rethrow:
 ; CHECK:   call      foo@FUNCTION
 ; CHECK:   i32.catch     $push{{.+}}=, 0
 ; CHECK-DAG:   i32.store  __wasm_lpad_context
 ; CHECK-DAG:   i32.store  __wasm_lpad_context+4
 ; CHECK:   i32.call  $push{{.+}}=, _Unwind_CallPersonality@FUNCTION
 ; CHECK:   i32.call  $push{{.+}}=, __cxa_begin_catch@FUNCTION
 ; CHECK:   call      __cxa_end_catch@FUNCTION
 ; CHECK:   call      __cxa_rethrow@FUNCTION
-define void @test_catch() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+; CHECK-NEXT:   rethrow
+define void @test_catch_rethrow() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   invoke void @foo()
           to label %try.cont unwind label %catch.dispatch
 
 catch.dispatch:                                   ; preds = %entry
   %0 = catchswitch within none [label %catch.start] unwind to caller
 
 catch.start:                                      ; preds = %catch.dispatch

 
 try.cont:                                         ; preds = %entry, %catch
   ret void
 }
 
 ; CHECK-LABEL: test_cleanup:
 ; CHECK:   call      foo@FUNCTION
 ; CHECK:   return
+; CHECK:   catch_all
 ; CHECK:   i32.call  $push20=, _ZN7CleanupD1Ev@FUNCTION
 ; CHECK:   rethrow   0
 define void @test_cleanup() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
 entry:
   %c = alloca %struct.Cleanup, align 1
   invoke void @foo()
           to label %invoke.cont unwind label %ehcleanup
 
 invoke.cont:                                      ; preds = %entry
   %call = call %struct.Cleanup* @_ZN7CleanupD1Ev(%struct.Cleanup* %c)
   ret void
 
 ehcleanup:                                        ; preds = %entry
   %0 = cleanuppad within none []
   %call1 = call %struct.Cleanup* @_ZN7CleanupD1Ev(%struct.Cleanup* %c) [ "funclet"(token %0) ]
   cleanupret from %0 unwind to caller
 }
 
+; - Tests multple terminate pads are merged into one
+; - Tests a catch_all terminate pad is created after a catch terminate pad
+
+; CHECK-LABEL: test_terminatepad
+; CHECK:  i32.catch
+; CHECK:  call      __clang_call_terminate@FUNCTION
+; CHECK:  unreachable
+; CHECK:  catch_all
+; CHECK:  call      _ZSt9terminatev@FUNCTION
+; CHECK-NOT:  call      __clang_call_terminate@FUNCTION
+define hidden i32 @test_terminatepad() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+entry:
+  %c = alloca %struct.Cleanup, align 1
+  %c1 = alloca %struct.Cleanup, align 1
+  invoke void @foo()
+          to label %invoke.cont unwind label %ehcleanup
+
+invoke.cont:                                      ; preds = %entry
+  %call = invoke %struct.Cleanup* @_ZN7CleanupD1Ev(%struct.Cleanup* %c1)
+          to label %try.cont unwind label %catch.dispatch
+
+ehcleanup:                                        ; preds = %entry
+  %0 = cleanuppad within none []
+  %call4 = invoke %struct.Cleanup* @_ZN7CleanupD1Ev(%struct.Cleanup* %c1) [ "funclet"(token %0) ]
+          to label %invoke.cont3 unwind label %terminate
+
+invoke.cont3:                                     ; preds = %ehcleanup
+  cleanupret from %0 unwind label %catch.dispatch
+
+catch.dispatch:                                   ; preds = %invoke.cont3, %invoke.cont
+  %1 = catchswitch within none [label %catch.start] unwind label %ehcleanup7
+
+catch.start:                                      ; preds = %catch.dispatch
+  %2 = catchpad within %1 [i8* null]
+  %3 = call i8* @llvm.wasm.get.exception(token %2)
+  %4 = call i32 @llvm.wasm.get.ehselector(token %2)
+  %5 = call i8* @__cxa_begin_catch(i8* %3) [ "funclet"(token %2) ]
+  invoke void @__cxa_end_catch() [ "funclet"(token %2) ]
+          to label %invoke.cont5 unwind label %ehcleanup7
+
+invoke.cont5:                                     ; preds = %catch.start
+  catchret from %2 to label %try.cont
+
+try.cont:                                         ; preds = %invoke.cont5, %invoke.cont
+  %call6 = call %struct.Cleanup* @_ZN7CleanupD1Ev(%struct.Cleanup* %c)
+  ret i32 0
+
+ehcleanup7:                                       ; preds = %catch.start, %catch.dispatch
+  %6 = cleanuppad within none []
+  %call9 = invoke %struct.Cleanup* @_ZN7CleanupD1Ev(%struct.Cleanup* %c) [ "funclet"(token %6) ]
+          to label %invoke.cont8 unwind label %terminate10
+
+invoke.cont8:                                     ; preds = %ehcleanup7
+  cleanupret from %6 unwind to caller
+
+terminate:                                        ; preds = %ehcleanup
+  %7 = cleanuppad within %0 []
+  %8 = call i8* @llvm.wasm.get.exception(token %7)
+  call void @__clang_call_terminate(i8* %8) [ "funclet"(token %7) ]
+  unreachable
+
+terminate10:                                      ; preds = %ehcleanup7
+  %9 = cleanuppad within %6 []
+  %10 = call i8* @llvm.wasm.get.exception(token %9)
+  call void @__clang_call_terminate(i8* %10) [ "funclet"(token %9) ]
+  unreachable
+}
+
 declare void @foo()
-declare void @func(i32)
 declare i32 @__gxx_wasm_personality_v0(...)
 declare i8* @llvm.wasm.get.exception(token)
 declare i32 @llvm.wasm.get.ehselector(token)
 declare i32 @llvm.eh.typeid.for(i8*)
 declare i8* @__cxa_begin_catch(i8*)
 declare void @__cxa_end_catch()
 declare void @__cxa_rethrow()
 declare void @__clang_call_terminate(i8*)
+declare void @_ZSt9terminatev()
 declare %struct.Cleanup* @_ZN7CleanupD1Ev(%struct.Cleanup* returned)