[WebAssembly] Exception handling: Switch to the new proposal

Summary:
This switches the EH implementation to the new proposal:
https://github.com/WebAssembly/exception-handling/blob/master/proposals/Exceptions.md
(The previous proposal was
 https://github.com/WebAssembly/exception-handling/blob/master/proposals/old/Exceptions.md)

- Instruction changes
  - Now we have one single `catch` instruction that returns a except_ref
    value
  - `throw` now can take variable number of operations
  - `rethrow` does not have 'depth' argument anymore
  - `br_on_exn` queries an except_ref to see if it matches the tag and
    branches to the given label if true.
  - `extract_exception` is a pseudo instruction that simulates popping
    values from wasm stack. This is to make `br_on_exn`, a very special
    instruction, work: `br_on_exn` puts values onto the stack only if it
    is taken, and the # of values can vay depending on the tag.

- Now there's only one `catch` per `try`, this patch removes all special
  handling for terminate pad with a call to `__clang_call_terminate`.
  Before it was the only case there are two catch clauses (a normal
  `catch` and `catch_all` per `try`).

- Make `rethrow` act as a terminator like `throw`. This splits BB after
  `rethrow` in WasmEHPrepare, and deletes an unnecessary `unreachable`
  after `rethrow` in LateEHPrepare.

- Now we stop at all catchpads (because we add wasm `catch` instruction
  that catches all exceptions), this creates new
  `findWasmUnwindDestinations` function in SelectionDAGBuilder.

- Now we use `br_on_exn` instrution to figure out if an except_ref
  matches the current tag or not, LateEHPrepare generates this sequence
  for catch pads:
```
  catch
  block i32
  br_on_exn $__cpp_exception
  end_block
  extract_exception
```

- Branch analysis for `br_on_exn` in WebAssemblyInstrInfo

- Other various misc. changes to switch to the new proposal.

Reviewers: dschuff

Subscribers: sbc100, jgravelle-google, sunfish, llvm-commits

Differential Revision: https://reviews.llvm.org/D57134

llvm-svn: 352598

1 files changed, 138 insertions, 227 deletions

diff --git a/llvm/lib/Target/WebAssembly/WebAssemblyLateEHPrepare.cpp b/llvm/lib/Target/WebAssembly/WebAssemblyLateEHPrepare.cpp
index caedd140a1c..030f09b8bf4 100644
--- a/llvm/lib/Target/WebAssembly/WebAssemblyLateEHPrepare.cpp
+++ b/llvm/lib/Target/WebAssembly/WebAssemblyLateEHPrepare.cpp
@@ -15,6 +15,7 @@
 #include "WebAssembly.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyUtilities.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/WasmEHFuncInfo.h"
 #include "llvm/MC/MCAsmInfo.h"
@@ -25,19 +26,14 @@ using namespace llvm;
 namespace {
 class WebAssemblyLateEHPrepare final : public MachineFunctionPass {
   StringRef getPassName() const override {
-    return "WebAssembly Prepare Exception";
+    return "WebAssembly Late Prepare Exception";
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
-
   bool removeUnnecessaryUnreachables(MachineFunction &MF);
   bool replaceFuncletReturns(MachineFunction &MF);
-  bool hoistCatches(MachineFunction &MF);
-  bool addCatchAlls(MachineFunction &MF);
-  bool addRethrows(MachineFunction &MF);
-  bool ensureSingleBBTermPads(MachineFunction &MF);
-  bool mergeTerminatePads(MachineFunction &MF);
-  bool addCatchAllTerminatePads(MachineFunction &MF);
+  bool addCatches(MachineFunction &MF);
+  bool addExceptionExtraction(MachineFunction &MF);
 
 public:
   static char ID; // Pass identification, replacement for typeid
@@ -112,15 +108,11 @@ bool WebAssemblyLateEHPrepare::runOnMachineFunction(MachineFunction &MF) {
 
   bool Changed = false;
   Changed |= removeUnnecessaryUnreachables(MF);
-  Changed |= addRethrows(MF);
   if (!MF.getFunction().hasPersonalityFn())
     return Changed;
   Changed |= replaceFuncletReturns(MF);
-  Changed |= hoistCatches(MF);
-  Changed |= addCatchAlls(MF);
-  Changed |= ensureSingleBBTermPads(MF);
-  Changed |= mergeTerminatePads(MF);
-  Changed |= addCatchAllTerminatePads(MF);
+  Changed |= addCatches(MF);
+  Changed |= addExceptionExtraction(MF);
   return Changed;
 }
 
@@ -129,7 +121,8 @@ bool WebAssemblyLateEHPrepare::removeUnnecessaryUnreachables(
   bool Changed = false;
   for (auto &MBB : MF) {
     for (auto &MI : MBB) {
-      if (!WebAssembly::isThrow(MI))
+      if (MI.getOpcode() != WebAssembly::THROW &&
+          MI.getOpcode() != WebAssembly::RETHROW)
         continue;
       Changed = true;
 
@@ -152,7 +145,6 @@ bool WebAssemblyLateEHPrepare::removeUnnecessaryUnreachables(
 bool WebAssemblyLateEHPrepare::replaceFuncletReturns(MachineFunction &MF) {
   bool Changed = false;
   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
-  auto *EHInfo = MF.getWasmEHFuncInfo();
 
   for (auto &MBB : MF) {
     auto Pos = MBB.getFirstTerminator();
@@ -173,13 +165,7 @@ bool WebAssemblyLateEHPrepare::replaceFuncletReturns(MachineFunction &MF) {
     }
     case WebAssembly::CLEANUPRET: {
       // Replace a cleanupret with a rethrow
-      if (EHInfo->hasThrowUnwindDest(&MBB))
-        BuildMI(MBB, TI, TI->getDebugLoc(), TII.get(WebAssembly::RETHROW))
-            .addMBB(EHInfo->getThrowUnwindDest(&MBB));
-      else
-        BuildMI(MBB, TI, TI->getDebugLoc(),
-                TII.get(WebAssembly::RETHROW_TO_CALLER));
-
+      BuildMI(MBB, TI, TI->getDebugLoc(), TII.get(WebAssembly::RETHROW));
       TI->eraseFromParent();
       Changed = true;
       break;
@@ -189,233 +175,158 @@ bool WebAssemblyLateEHPrepare::replaceFuncletReturns(MachineFunction &MF) {
   return Changed;
 }
 
-// Hoist catch instructions to the beginning of their matching EH pad BBs in
-// case,
-// (1) catch instruction is not the first instruction in EH pad.
-// ehpad:
-//   some_other_instruction
-//   ...
-//   %exn = catch 0
-// (2) catch instruction is in a non-EH pad BB. For example,
-// ehpad:
-//   br bb0
-// bb0:
-//   %exn = catch 0
-bool WebAssemblyLateEHPrepare::hoistCatches(MachineFunction &MF) {
-  bool Changed = false;
-  SmallVector<MachineInstr *, 16> Catches;
-  for (auto &MBB : MF)
-    for (auto &MI : MBB)
-      if (WebAssembly::isCatch(MI))
-        Catches.push_back(&MI);
-
-  for (auto *Catch : Catches) {
-    MachineBasicBlock *EHPad = getMatchingEHPad(Catch);
-    assert(EHPad && "No matching EH pad for catch");
-    if (EHPad->begin() == Catch)
-      continue;
-    Changed = true;
-    EHPad->insert(EHPad->begin(), Catch->removeFromParent());
-  }
-  return Changed;
-}
-
-// Add catch_all to beginning of cleanup pads.
-bool WebAssemblyLateEHPrepare::addCatchAlls(MachineFunction &MF) {
+// Add catch instruction to beginning of catchpads and cleanuppads.
+bool WebAssemblyLateEHPrepare::addCatches(MachineFunction &MF) {
   bool Changed = false;
   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
-
+  MachineRegisterInfo &MRI = MF.getRegInfo();
   for (auto &MBB : MF) {
-    if (!MBB.isEHPad())
-      continue;
-    // This runs after hoistCatches(), so we assume that if there is a catch,
-    // that should be the first instruction in an EH pad.
-    if (!WebAssembly::isCatch(*MBB.begin())) {
+    if (MBB.isEHPad()) {
       Changed = true;
+      unsigned DstReg =
+          MRI.createVirtualRegister(&WebAssembly::EXCEPT_REFRegClass);
       BuildMI(MBB, MBB.begin(), MBB.begin()->getDebugLoc(),
-              TII.get(WebAssembly::CATCH_ALL));
+              TII.get(WebAssembly::CATCH), DstReg);
     }
   }
   return Changed;
 }
 
-// Add a 'rethrow' instruction after __cxa_rethrow() call
-bool WebAssemblyLateEHPrepare::addRethrows(MachineFunction &MF) {
-  bool Changed = false;
+// Wasm uses 'br_on_exn' instruction to check the tag of an exception. It takes
+// except_ref type object returned by 'catch', and branches to the destination
+// if it matches a given tag. We currently use __cpp_exception symbol to
+// represent the tag for all C++ exceptions.
+//
+// block $l (result i32)
+//   ...
+//   ;; except_ref $e is on the stack at this point
+//   br_on_exn $l $e ;; branch to $l with $e's arguments
+//   ...
+// end
+// ;; Here we expect the extracted values are on top of the wasm value stack
+// ... Handle exception using values ...
+//
+// br_on_exn takes an except_ref object and branches if it matches the given
+// tag. There can be multiple br_on_exn instructions if we want to match for
+// another tag, but for now we only test for __cpp_exception tag, and if it does
+// not match, i.e., it is a foreign exception, we rethrow it.
+//
+// In the destination BB that's the target of br_on_exn, extracted exception
+// values (in C++'s case a single i32, which represents an exception pointer)
+// are placed on top of the wasm stack. Because we can't model wasm stack in
+// LLVM instruction, we use 'extract_exception' pseudo instruction to retrieve
+// it. The pseudo instruction will be deleted later.
+bool WebAssemblyLateEHPrepare::addExceptionExtraction(MachineFunction &MF) {
   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
   auto *EHInfo = MF.getWasmEHFuncInfo();
-
-  for (auto &MBB : MF)
+  SmallVector<MachineInstr *, 16> ExtractInstrs;
+  for (auto &MBB : MF) {
     for (auto &MI : MBB) {
-      // Check if it is a call to __cxa_rethrow()
-      if (!MI.isCall())
-        continue;
-      MachineOperand &CalleeOp = MI.getOperand(0);
-      if (!CalleeOp.isGlobal() ||
-          CalleeOp.getGlobal()->getName() != WebAssembly::CxaRethrowFn)
-        continue;
-
-      // Now we have __cxa_rethrow() call
-      Changed = true;
-      auto InsertPt = std::next(MachineBasicBlock::iterator(MI));
-      while (InsertPt != MBB.end() && InsertPt->isLabel()) // Skip EH_LABELs
-        ++InsertPt;
-      MachineInstr *Rethrow = nullptr;
-      if (EHInfo->hasThrowUnwindDest(&MBB))
-        Rethrow = BuildMI(MBB, InsertPt, MI.getDebugLoc(),
-                          TII.get(WebAssembly::RETHROW))
-                      .addMBB(EHInfo->getThrowUnwindDest(&MBB));
-      else
-        Rethrow = BuildMI(MBB, InsertPt, MI.getDebugLoc(),
-                          TII.get(WebAssembly::RETHROW_TO_CALLER));
-
-      // Because __cxa_rethrow does not return, the instruction after the
-      // rethrow should be an unreachable or a branch to another BB that should
-      // eventually lead to an unreachable. Delete it because rethrow itself is
-      // a terminator, and also delete non-EH pad successors if any.
-      MBB.erase(std::next(MachineBasicBlock::iterator(Rethrow)), MBB.end());
-      SmallVector<MachineBasicBlock *, 8> NonPadSuccessors;
-      for (auto *Succ : MBB.successors())
-        if (!Succ->isEHPad())
-          NonPadSuccessors.push_back(Succ);
-      for (auto *Succ : NonPadSuccessors)
-        MBB.removeSuccessor(Succ);
-      eraseDeadBBsAndChildren(NonPadSuccessors);
+      if (MI.getOpcode() == WebAssembly::EXTRACT_EXCEPTION_I32) {
+        if (MI.getOperand(0).isDead())
+          MI.eraseFromParent();
+        else
+          ExtractInstrs.push_back(&MI);
+      }
     }
-  return Changed;
-}
-
-// Terminate pads are an single-BB EH pad in the form of
-// termpad:
-//   %exn = catch 0
-//   call @__clang_call_terminate(%exn)
-//   unreachable
-// (There can be local.set and local.gets before the call if we didn't run
-// RegStackify)
-// But code transformations can change or add more control flow, so the call to
-// __clang_call_terminate() function may not be in the original EH pad anymore.
-// This ensures every terminate pad is a single BB in the form illustrated
-// above.
-bool WebAssemblyLateEHPrepare::ensureSingleBBTermPads(MachineFunction &MF) {
-  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  }
+  if (ExtractInstrs.empty())
+    return false;
 
-  // Find calls to __clang_call_terminate()
-  SmallVector<MachineInstr *, 8> ClangCallTerminateCalls;
-  for (auto &MBB : MF)
-    for (auto &MI : MBB)
+  // Find terminate pads.
+  SmallSet<MachineBasicBlock *, 8> TerminatePads;
+  for (auto &MBB : MF) {
+    for (auto &MI : MBB) {
       if (MI.isCall()) {
         const MachineOperand &CalleeOp = MI.getOperand(0);
         if (CalleeOp.isGlobal() && CalleeOp.getGlobal()->getName() ==
                                        WebAssembly::ClangCallTerminateFn)
-          ClangCallTerminateCalls.push_back(&MI);
+          TerminatePads.insert(getMatchingEHPad(&MI));
       }
-
-  bool Changed = false;
-  for (auto *Call : ClangCallTerminateCalls) {
-    MachineBasicBlock *EHPad = getMatchingEHPad(Call);
-    assert(EHPad && "No matching EH pad for catch");
-
-    // If it is already the form we want, skip it
-    if (Call->getParent() == EHPad &&
-        Call->getNextNode()->getOpcode() == WebAssembly::UNREACHABLE)
-      continue;
-
-    // In case the __clang_call_terminate() call is not in its matching EH pad,
-    // move the call to the end of EH pad and add an unreachable instruction
-    // after that. Delete all successors and their children if any, because here
-    // the program terminates.
-    Changed = true;
-    MachineInstr *Catch = &*EHPad->begin();
-    // This runs after hoistCatches(), so catch instruction should be at the top
-    assert(WebAssembly::isCatch(*Catch));
-    // Takes the result register of the catch instruction as argument. There may
-    // have been some other local.set/local.gets in between, but at this point
-    // we don't care.
-    Call->getOperand(1).setReg(Catch->getOperand(0).getReg());
-    auto InsertPos = std::next(MachineBasicBlock::iterator(Catch));
-    EHPad->insert(InsertPos, Call->removeFromParent());
-    BuildMI(*EHPad, InsertPos, Call->getDebugLoc(),
-            TII.get(WebAssembly::UNREACHABLE));
-    EHPad->erase(InsertPos, EHPad->end());
-    SmallVector<MachineBasicBlock *, 8> Succs(EHPad->succ_begin(),
-                                              EHPad->succ_end());
-    for (auto *Succ : Succs)
-      EHPad->removeSuccessor(Succ);
-    eraseDeadBBsAndChildren(Succs);
+    }
   }
-  return Changed;
-}
 
-// In case there are multiple terminate pads, merge them into one for code size.
-// This runs after ensureSingleBBTermPads() and assumes every terminate pad is a
-// single BB.
-// In principle this violates EH scope relationship because it can merge
-// multiple inner EH scopes, each of which is in different outer EH scope. But
-// getEHScopeMembership() function will not be called after this, so it is fine.
-bool WebAssemblyLateEHPrepare::mergeTerminatePads(MachineFunction &MF) {
-  SmallVector<MachineBasicBlock *, 8> TermPads;
-  for (auto &MBB : MF)
-    if (WebAssembly::isCatchTerminatePad(MBB))
-      TermPads.push_back(&MBB);
-  if (TermPads.empty())
-    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->eraseFromParent();
+  for (auto *Extract : ExtractInstrs) {
+    MachineBasicBlock *EHPad = getMatchingEHPad(Extract);
+    assert(EHPad && "No matching EH pad for extract_exception");
+    MachineInstr *Catch = &*EHPad->begin();
+    if (Catch->getNextNode() != Extract)
+      EHPad->insert(Catch->getNextNode(), Extract->removeFromParent());
+
+    // - Before:
+    // ehpad:
+    //   %exnref:except_ref = catch
+    //   %exn:i32 = extract_exception
+    //   ... use exn ...
+    //
+    // - After:
+    // ehpad:
+    //   %exnref:except_ref = catch
+    //   br_on_exn %thenbb, $__cpp_exception, %exnref
+    //   br %elsebb
+    // elsebb:
+    //   rethrow
+    // thenbb:
+    //   %exn:i32 = extract_exception
+    //   ... use exn ...
+    unsigned ExnRefReg = Catch->getOperand(0).getReg();
+    auto *ThenMBB = MF.CreateMachineBasicBlock();
+    auto *ElseMBB = MF.CreateMachineBasicBlock();
+    MF.insert(std::next(MachineFunction::iterator(EHPad)), ElseMBB);
+    MF.insert(std::next(MachineFunction::iterator(ElseMBB)), ThenMBB);
+    ThenMBB->splice(ThenMBB->end(), EHPad, Extract, EHPad->end());
+    ThenMBB->transferSuccessors(EHPad);
+    EHPad->addSuccessor(ThenMBB);
+    EHPad->addSuccessor(ElseMBB);
+
+    DebugLoc DL = Extract->getDebugLoc();
+    const char *CPPExnSymbol = MF.createExternalSymbolName("__cpp_exception");
+    BuildMI(EHPad, DL, TII.get(WebAssembly::BR_ON_EXN))
+        .addMBB(ThenMBB)
+        .addExternalSymbol(CPPExnSymbol, WebAssemblyII::MO_SYMBOL_EVENT)
+        .addReg(ExnRefReg);
+    BuildMI(EHPad, DL, TII.get(WebAssembly::BR)).addMBB(ElseMBB);
+
+    // When this is a terminate pad with __clang_call_terminate() call, we don't
+    // rethrow it anymore and call __clang_call_terminate() with a nullptr
+    // argument, which will call std::terminate().
+    //
+    // - Before:
+    // ehpad:
+    //   %exnref:except_ref = catch
+    //   %exn:i32 = extract_exception
+    //   call @__clang_call_terminate(%exn)
+    //   unreachable
+    //
+    // - After:
+    // ehpad:
+    //   %exnref:except_ref = catch
+    //   br_on_exn %thenbb, $__cpp_exception, %exnref
+    //   br %elsebb
+    // elsebb:
+    //   call @__clang_call_terminate(0)
+    //   unreachable
+    // thenbb:
+    //   %exn:i32 = extract_exception
+    //   call @__clang_call_terminate(%exn)
+    //   unreachable
+    if (TerminatePads.count(EHPad)) {
+      Function *ClangCallTerminateFn =
+          MF.getFunction().getParent()->getFunction(
+              WebAssembly::ClangCallTerminateFn);
+      assert(ClangCallTerminateFn &&
+             "There is no __clang_call_terminate() function");
+      BuildMI(ElseMBB, DL, TII.get(WebAssembly::CALL_VOID))
+          .addGlobalAddress(ClangCallTerminateFn)
+          .addImm(0);
+      BuildMI(ElseMBB, DL, TII.get(WebAssembly::UNREACHABLE));
+
+    } else {
+      BuildMI(ElseMBB, DL, TII.get(WebAssembly::RETHROW));
+      if (EHInfo->hasEHPadUnwindDest(EHPad))
+        EHInfo->setThrowUnwindDest(ElseMBB, EHInfo->getEHPadUnwindDest(EHPad));
+    }
   }
-  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
-// with the passed exception pointer and then std::terminate. This is the reason
-// that terminate pads are generated with not a catch_all but a catch
-// instruction in clang and earlier llvm passes. Here we append a terminate pad
-// with a catch_all after each existing terminate pad so we can also catch
-// foreign exceptions. For every terminate pad:
-//   %exn = catch 0
-//   call @__clang_call_terminate(%exn)
-//   unreachable
-// We append this BB right after that:
-//   catch_all
-//   call @std::terminate()
-//   unreachable
-bool WebAssemblyLateEHPrepare::addCatchAllTerminatePads(MachineFunction &MF) {
-  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
-  SmallVector<MachineBasicBlock *, 8> TermPads;
-  for (auto &MBB : MF)
-    if (WebAssembly::isCatchTerminatePad(MBB))
-      TermPads.push_back(&MBB);
-  if (TermPads.empty())
-    return false;
-
-  Function *StdTerminateFn =
-      MF.getFunction().getParent()->getFunction(WebAssembly::StdTerminateFn);
-  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));
-
-    // Actually this CatchAllTermPad (new terminate pad with a catch_all) is not
-    // a successor of an existing terminate pad. CatchAllTermPad should have all
-    // predecessors CatchTermPad has instead. This is a hack to force
-    // CatchAllTermPad be always sorted right after CatchTermPad; the correct
-    // predecessor-successor relationships will be restored in CFGStackify pass.
-    CatchTermPad->addSuccessor(CatchAllTermPad);
-  }
   return true;
 }