[WebAssembly] Remove unreachable EH pads

[aheejin]

Summary

This removes unreachable EH pads in LateEHPrepare. This is not for
optimization but for preparation for CFGStackify. In CFGStackify, we
determine where to place try marker by computing the nearest common
dominator of all predecessors of an EH pad, but when an EH pad does not
have a predecessor, it becomes tricky. We can insert an empty dummy BB
before the EH pad and place the try there, but removing unreachable EH
pads is simpler.

This moves an existing exception label test from eh-label.mir to
exception.mir and adds a new test there.

This also adds some comments to existing methods.

[tlively]

llvm/test/CodeGen/WebAssembly/exception.mir

62

Can you add a ; CHECK for one of the other BB labels to demonstrate that this removed BB is different from other BBs?

[dschuff]

llvm/lib/Target/WebAssembly/WebAssemblyLateEHPrepare.cpp

98

This could be SmallPtrSet, I guess it's smaller?

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyLateEHPrepare.cpp

98

Done. Also changed one more usage of SmallSet in this pass to SmallPtrSet.

llvm/lib/Target/WebAssembly/WebAssemblyLateEHPrepare.cpp

 /// \brief Does various transformations for exception handling.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
 #include "WebAssembly.h"
 #include "WebAssemblySubtarget.h"
 #include "WebAssemblyUtilities.h"
-#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/WasmEHFuncInfo.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetMachine.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "wasm-late-eh-prepare"
 
 namespace {
 class WebAssemblyLateEHPrepare final : public MachineFunctionPass {
   StringRef getPassName() const override {
     return "WebAssembly Late Prepare Exception";
   }
 
   bool runOnMachineFunction(MachineFunction &MF) override;
+  bool removeUnreachableEHPads(MachineFunction &MF);
   void recordCatchRetBBs(MachineFunction &MF);
   bool hoistCatches(MachineFunction &MF);
   bool addCatchAlls(MachineFunction &MF);
   bool replaceFuncletReturns(MachineFunction &MF);
   bool removeUnnecessaryUnreachables(MachineFunction &MF);
   bool restoreStackPointer(MachineFunction &MF);
 
   MachineBasicBlock *getMatchingEHPad(MachineInstr *MI);
-  SmallSet<MachineBasicBlock *, 8> CatchRetBBs;
+  SmallPtrSet<MachineBasicBlock *, 8> CatchRetBBs;
 
 public:
   static char ID; // Pass identification, replacement for typeid
   WebAssemblyLateEHPrepare() : MachineFunctionPass(ID) {}
 };
 } // end anonymous namespace
 
 char WebAssemblyLateEHPrepare::ID = 0;
WebAssemblyLateEHPrepare::getMatchingEHPad(MachineInstr *MI) {
   return EHPad;
 }
 
 // Erase the specified BBs if the BB does not have any remaining predecessors,
 // and also all its dead children.
 template <typename Container>
 static void eraseDeadBBsAndChildren(const Container &MBBs) {
   SmallVector<MachineBasicBlock *, 8> WL(MBBs.begin(), MBBs.end());
+  SmallPtrSet<MachineBasicBlock *, 8> Deleted;
   while (!WL.empty()) {
     MachineBasicBlock *MBB = WL.pop_back_val();
-    if (!MBB->pred_empty())
+    if (Deleted.count(MBB) || !MBB->pred_empty())
       continue;
     SmallVector<MachineBasicBlock *, 4> Succs(MBB->successors());
     WL.append(MBB->succ_begin(), MBB->succ_end());
     for (auto *Succ : Succs)
       MBB->removeSuccessor(Succ);
+    // To prevent deleting the same BB multiple times, which can happen when
+    // 'MBBs' contain both a parent and a child
+    Deleted.insert(MBB);
     MBB->eraseFromParent();
   }
 }
 
 bool WebAssemblyLateEHPrepare::runOnMachineFunction(MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "********** Late EH Prepare **********\n"
                        "********** Function: "
                     << MF.getName() << '\n');
 
   if (MF.getTarget().getMCAsmInfo()->getExceptionHandlingType() !=
       ExceptionHandling::Wasm)
     return false;
 
   bool Changed = false;
   if (MF.getFunction().hasPersonalityFn()) {
+    Changed |= removeUnreachableEHPads(MF);
     recordCatchRetBBs(MF);
     Changed |= hoistCatches(MF);
     Changed |= addCatchAlls(MF);
     Changed |= replaceFuncletReturns(MF);
   }
   Changed |= removeUnnecessaryUnreachables(MF);
   if (MF.getFunction().hasPersonalityFn())
     Changed |= restoreStackPointer(MF);
   return Changed;
 }
 
-// Record which BB ends with 'CATCHRET' instruction, because this will be
-// replaced with BRs later. This set of 'CATCHRET' BBs is necessary in
-// 'getMatchingEHPad' function.
+// Remove unreachable EH pads and its children. If they remain, CFG
+// stackification can be tricky.
+bool WebAssemblyLateEHPrepare::removeUnreachableEHPads(MachineFunction &MF) {
+  SmallVector<MachineBasicBlock *, 4> ToDelete;
+  for (auto &MBB : MF)
+    if (MBB.isEHPad() && MBB.pred_empty())
+      ToDelete.push_back(&MBB);
+  eraseDeadBBsAndChildren(ToDelete);
+  return !ToDelete.empty();
+}
+
+// Record which BB ends with catchret instruction, because this will be replaced
+// with 'br's later. This set of catchret BBs is necessary in 'getMatchingEHPad'
+// function.
 void WebAssemblyLateEHPrepare::recordCatchRetBBs(MachineFunction &MF) {
   CatchRetBBs.clear();
   for (auto &MBB : MF) {
     auto Pos = MBB.getFirstTerminator();
     if (Pos == MBB.end())
       continue;
     MachineInstr *TI = &*Pos;
     if (TI->getOpcode() == WebAssembly::CATCHRET)
if (InsertPos == MBB.end() ||
       Changed = true;
       BuildMI(MBB, InsertPos, InsertPos->getDebugLoc(),
               TII.get(WebAssembly::CATCH_ALL));
     }
   }
   return Changed;
 }
 
+// Replace pseudo-instructions catchret and cleanupret with br and rethrow
+// respectively.
 bool WebAssemblyLateEHPrepare::replaceFuncletReturns(MachineFunction &MF) {
   bool Changed = false;
   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
 
   for (auto &MBB : MF) {
     auto Pos = MBB.getFirstTerminator();
     if (Pos == MBB.end())
       continue;
case WebAssembly::CLEANUPRET: {
       Changed = true;
       break;
     }
     }
   }
   return Changed;
 }
 
+// Remove unnecessary unreachables after a throw or rethrow.
 bool WebAssemblyLateEHPrepare::removeUnnecessaryUnreachables(
     MachineFunction &MF) {
   bool Changed = false;
   for (auto &MBB : MF) {
     for (auto &MI : MBB) {
       if (MI.getOpcode() != WebAssembly::THROW &&
           MI.getOpcode() != WebAssembly::RETHROW)
         continue;

llvm/test/CodeGen/WebAssembly/exception.mir

 # RUN: llc -mtriple=wasm32-unknown-unknown -exception-model=wasm -mattr=+exception-handling -run-pass wasm-late-eh-prepare -run-pass wasm-cfg-stackify %s -o - | FileCheck %s
 
-# This tests 'try' and 'catch' instructions are correctly placed with respect to
-# EH_LABEL instructions.
 --- |
   target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
   target triple = "wasm32-unknown-unknown"
 
   declare i32 @__gxx_wasm_personality_v0(...)
   declare void @foo()
   define void @eh_label_test() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
     ret void
   }
+  define void @unreachable_ehpad_test() personality i8* bitcast (i32 (...)* @__gxx_wasm_personality_v0 to i8*) {
+    ret void
+  }
 ...
 
 ---
-# CHECK-LABEL: eh_label_test
+# This tests 'try' and 'catch' instructions are correctly placed with respect to
+# EH_LABEL instructions.
+# CHECK-LABEL: name: eh_label_test
 name: eh_label_test
 liveins:
   - { reg: '$arguments' }
 body: |
   bb.0:
     ; TRY should be before EH_LABEL wrappers of throwing calls
     ; CHECK:      TRY
     ; CHECK-NEXT: EH_LABEL
; predecessors: %bb.0
     ; CHECK-NEXT: CATCH_ALL
     EH_LABEL <mcsymbol .Ltmp2>
     CATCHRET %bb.2, %bb.0, implicit-def dead $arguments
 
   bb.2:
   ; predecessors: %bb.0, %bb.1
     RETURN implicit-def dead $arguments
 ...
+---
+# Unreachable EH pads should be removed by LateEHPrepare.
+# CHECK-LABEL: name: unreachable_ehpad_test
+name: unreachable_ehpad_test
+liveins:
+  - { reg: '$arguments' }
+body: |
+  ; CHECK: bb.0
+  bb.0:
+    successors: %bb.2
+    BR %bb.2, implicit-def dead $arguments
+
+  ; This EH pad is unreachable, so it should be removed by LateEHPrepare
+  ; CHECK-NOT: bb.1 (landing-pad)
+  bb.1 (landing-pad):
+    successors: %bb.2
+    EH_LABEL <mcsymbol .Ltmp2>
+    CATCHRET %bb.2, %bb.0, implicit-def dead $arguments
+
+  ; CHECK: bb.2
+  bb.2:
+  ; predecessors: %bb.0, %bb.1
+    RETURN implicit-def dead $arguments
+...