[EH] Support CFGWalker for new EH spec (#6235)

This adds support `CFGWalker` for the new EH instructions (`try_table`
and `throw_ref`). `CFGWalker` is used by many different passes, but in
the same vein as #3494, this adds tests for `RedundantSetElimination`
pass. `rse-eh.wast` file is created from translated and simplified
version of `rse-eh-old.wast`, but many tests were removed because we
don't have special `catch` block or `delegate` anymore.

3 files changed, 413 insertions, 29 deletions

diff --git a/scripts/fuzz_opt.py b/scripts/fuzz_opt.py
index 27b278703..f839984c2 100755
--- a/scripts/fuzz_opt.py
+++ b/scripts/fuzz_opt.py
@@ -319,6 +319,7 @@ INITIAL_CONTENTS_IGNORE = [
     # New EH implementation is in progress
     'exception-handling.wast',
     'translate-eh-old-to-new.wast',
+    'rse-eh.wast',
 ]
 
 
diff --git a/src/cfg/cfg-traversal.h b/src/cfg/cfg-traversal.h
index e72195cc3..9c68ae863 100644
--- a/src/cfg/cfg-traversal.h
+++ b/src/cfg/cfg-traversal.h
@@ -99,7 +99,7 @@ struct CFGWalker : public PostWalker<SubType, VisitorType> {
   // that can reach catch blocks (each item is assumed to be able to reach any
   // of the catches, although that could be improved perhaps).
   std::vector<std::vector<BasicBlock*>> throwingInstsStack;
-  // stack of 'Try' expressions corresponding to throwingInstsStack.
+  // stack of 'Try'/'TryTable' expressions corresponding to throwingInstsStack.
   std::vector<Expression*> tryStack;
   // A stack for each try, where each entry is a list of blocks, one for each
   // catch, used during processing. We start by assigning the start blocks to
@@ -254,11 +254,11 @@ struct CFGWalker : public PostWalker<SubType, VisitorType> {
   }
 
   static void doEndThrowingInst(SubType* self, Expression** currp) {
-    // If the innermost try does not have a catch_all clause, an exception
-    // thrown can be caught by any of its outer catch block. And if that outer
-    // try-catch also does not have a catch_all, this continues until we
-    // encounter a try-catch_all. Create a link to all those possible catch
-    // unwind destinations.
+    // If the innermost try/try_table does not have a catch_all clause, an
+    // exception thrown can be caught by any of its outer catch block. And if
+    // that outer try/try_table also does not have a catch_all, this continues
+    // until we encounter a try/try_table-catch_all. Create a link to all those
+    // possible catch unwind destinations.
     // TODO This can be more precise for `throw`s if we compare tag types and
     // create links to outer catch BBs only when the exception is not caught.
     // TODO This can also be more precise if we analyze the structure of nested
@@ -281,36 +281,47 @@ struct CFGWalker : public PostWalker<SubType, VisitorType> {
     // end
     assert(self->tryStack.size() == self->throwingInstsStack.size());
     for (int i = self->throwingInstsStack.size() - 1; i >= 0;) {
-      auto* tryy = self->tryStack[i]->template cast<Try>();
-      if (tryy->isDelegate()) {
-        // If this delegates to the caller, there is no possibility that this
-        // instruction can throw to outer catches.
-        if (tryy->delegateTarget == DELEGATE_CALLER_TARGET) {
-          break;
-        }
-        // If this delegates to an outer try, we skip catches between this try
-        // and the target try.
-        [[maybe_unused]] bool found = false;
-        for (int j = i - 1; j >= 0; j--) {
-          if (self->tryStack[j]->template cast<Try>()->name ==
-              tryy->delegateTarget) {
-            i = j;
-            found = true;
+      if (auto* tryy = self->tryStack[i]->template dynCast<Try>()) {
+        if (tryy->isDelegate()) {
+          // If this delegates to the caller, there is no possibility that this
+          // instruction can throw to outer catches.
+          if (tryy->delegateTarget == DELEGATE_CALLER_TARGET) {
             break;
           }
+          // If this delegates to an outer try, we skip catches between this try
+          // and the target try.
+          [[maybe_unused]] bool found = false;
+          for (int j = i - 1; j >= 0; j--) {
+            if (self->tryStack[j]->template cast<Try>()->name ==
+                tryy->delegateTarget) {
+              i = j;
+              found = true;
+              break;
+            }
+          }
+          assert(found);
+          continue;
         }
-        assert(found);
-        continue;
       }
 
       // Exception thrown. Note outselves so that we will create a link to each
-      // catch within the try when we get there.
+      // catch within the try / each destination block within the try_table when
+      // we get there.
       self->throwingInstsStack[i].push_back(self->currBasicBlock);
 
-      // If this try has catch_all, there is no possibility that this
-      // instruction can throw to outer catches. Stop here.
-      if (tryy->hasCatchAll()) {
-        break;
+      if (auto* tryy = self->tryStack[i]->template dynCast<Try>()) {
+        // If this try has catch_all, there is no possibility that this
+        // instruction can throw to outer catches. Stop here.
+        if (tryy->hasCatchAll()) {
+          break;
+        }
+      } else if (auto* tryTable =
+                   self->tryStack[i]->template dynCast<TryTable>()) {
+        if (tryTable->hasCatchAll()) {
+          break;
+        }
+      } else {
+        WASM_UNREACHABLE("invalid throwingInstsStack item");
       }
       i--;
     }
@@ -411,6 +422,28 @@ struct CFGWalker : public PostWalker<SubType, VisitorType> {
     self->startUnreachableBlock();
   }
 
+  static void doStartTryTable(SubType* self, Expression** currp) {
+    auto* curr = (*currp)->cast<TryTable>();
+    self->throwingInstsStack.emplace_back();
+    self->tryStack.push_back(curr);
+  }
+
+  static void doEndTryTable(SubType* self, Expression** currp) {
+    auto* curr = (*currp)->cast<TryTable>();
+
+    auto catchTargets = BranchUtils::getUniqueTargets(curr);
+    // Add catch destinations to the targets.
+    for (auto target : catchTargets) {
+      auto& preds = self->throwingInstsStack.back();
+      for (auto* pred : preds) {
+        self->branches[target].push_back(pred);
+      }
+    }
+
+    self->throwingInstsStack.pop_back();
+    self->tryStack.pop_back();
+  }
+
   static bool isReturnCall(Expression* curr) {
     switch (curr->_id) {
       case Expression::Id::CallId:
@@ -478,8 +511,13 @@ struct CFGWalker : public PostWalker<SubType, VisitorType> {
         self->pushTask(SubType::doStartTry, currp);
         return; // don't do anything else
       }
+      case Expression::Id::TryTableId: {
+        self->pushTask(SubType::doEndTryTable, currp);
+        break;
+      }
       case Expression::Id::ThrowId:
-      case Expression::Id::RethrowId: {
+      case Expression::Id::RethrowId:
+      case Expression::Id::ThrowRefId: {
         self->pushTask(SubType::doEndThrow, currp);
         break;
       }
@@ -499,6 +537,10 @@ struct CFGWalker : public PostWalker<SubType, VisitorType> {
         self->pushTask(SubType::doStartLoop, currp);
         break;
       }
+      case Expression::Id::TryTableId: {
+        self->pushTask(SubType::doStartTryTable, currp);
+        break;
+      }
       default: {}
     }
   }
diff --git a/test/lit/passes/rse-eh.wast b/test/lit/passes/rse-eh.wast
new file mode 100644
index 000000000..0e0ee2980
--- /dev/null
+++ b/test/lit/passes/rse-eh.wast
@@ -0,0 +1,341 @@
+;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited.
+;; RUN: wasm-opt %s --rse -all -S -o - | filecheck %s
+
+(module
+  ;; CHECK:      (type $0 (func))
+
+  ;; CHECK:      (type $1 (func (result i32 exnref)))
+
+  ;; CHECK:      (type $2 (func (param i32)))
+
+  ;; CHECK:      (tag $e-i32 (param i32))
+  (tag $e-i32 (param i32))
+  ;; CHECK:      (tag $e-empty)
+  (tag $e-empty)
+
+  ;; CHECK:      (func $foo (type $0)
+  ;; CHECK-NEXT:  (nop)
+  ;; CHECK-NEXT: )
+  (func $foo)
+
+  ;; CHECK:      (func $try_table1 (type $0)
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (block $outer
+  ;; CHECK-NEXT:   (block $catch_all
+  ;; CHECK-NEXT:    (try_table (catch_all $catch_all)
+  ;; CHECK-NEXT:     (nop)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (br $outer)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:   (local.set $x
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $x
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $try_table1
+    (local $x i32)
+    (block $outer
+      (block $catch_all
+        (try_table (catch_all $catch_all)
+        )
+        (br $outer)
+      )
+      (local.set $x (i32.const 1))
+    )
+    ;; try_table will not throw. So this should NOT be dropped
+    (local.set $x (i32.const 1))
+  )
+
+  ;; CHECK:      (func $try_table2 (type $0)
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (block $catch_all
+  ;; CHECK-NEXT:   (try_table (catch_all $catch_all)
+  ;; CHECK-NEXT:    (throw $e-i32
+  ;; CHECK-NEXT:     (i32.const 0)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (local.set $x
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $x
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $try_table2
+    (local $x i32)
+    (block $catch_all
+      (try_table (catch_all $catch_all)
+        (throw $e-i32 (i32.const 0))
+        (local.set $x (i32.const 1))
+      )
+    )
+    ;; local.set is after 'throw' so it will not run. This should NOT be
+    ;; dropped.
+    (local.set $x (i32.const 1))
+  )
+
+  ;; CHECK:      (func $try_table3 (type $0)
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (block $outer
+  ;; CHECK-NEXT:   (block $catch_all
+  ;; CHECK-NEXT:    (try_table (catch_all $catch_all)
+  ;; CHECK-NEXT:     (call $foo)
+  ;; CHECK-NEXT:     (local.set $x
+  ;; CHECK-NEXT:      (i32.const 1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (br $outer)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $x
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $try_table3
+    (local $x i32)
+    (block $outer
+      (block $catch_all
+        (try_table (catch_all $catch_all)
+          (call $foo)
+          (local.set $x (i32.const 1))
+        )
+        (br $outer)
+      )
+    )
+    ;; (call $foo) may throw and the local.set may not run, so this should NOT
+    ;; be dropped
+    (local.set $x (i32.const 1))
+  )
+
+  ;; CHECK:      (func $try_table4 (type $0)
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (block $outer
+  ;; CHECK-NEXT:   (block $catch_all
+  ;; CHECK-NEXT:    (try_table (catch_all $catch_all)
+  ;; CHECK-NEXT:     (local.set $x
+  ;; CHECK-NEXT:      (i32.const 1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (call $foo)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (br $outer)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $try_table4
+    (local $x i32)
+    (block $outer
+      (block $catch_all
+        (try_table (catch_all $catch_all)
+          (local.set $x (i32.const 1))
+          (call $foo)
+        )
+        (br $outer)
+      )
+    )
+    ;; Even if (call $foo) throws, local.set runs before it, so this should be
+    ;; dropped
+    (local.set $x (i32.const 1))
+  )
+
+  ;; CHECK:      (func $nested-try_table1 (type $0)
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (local $exn exnref)
+  ;; CHECK-NEXT:  (block $catch_all0
+  ;; CHECK-NEXT:   (try_table (catch_all $catch_all0)
+  ;; CHECK-NEXT:    (local.set $exn
+  ;; CHECK-NEXT:     (block $catch_all_ref1 (result exnref)
+  ;; CHECK-NEXT:      (try_table (catch_all_ref $catch_all_ref1)
+  ;; CHECK-NEXT:       (throw $e-i32
+  ;; CHECK-NEXT:        (i32.const 0)
+  ;; CHECK-NEXT:       )
+  ;; CHECK-NEXT:      )
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (local.set $x
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (throw_ref
+  ;; CHECK-NEXT:     (local.get $exn)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $nested-try_table1
+    (local $x i32)
+    (local $exn exnref)
+    (block $catch_all0
+      (try_table (catch_all $catch_all0)
+        (local.set $exn
+          (block $catch_all_ref1 (result exnref)
+            (try_table (catch_all_ref $catch_all_ref1)
+              (throw $e-i32 (i32.const 0))
+            )
+          )
+        )
+        (local.set $x (i32.const 1))
+        (throw_ref (local.get $exn))
+      )
+    )
+    ;; The exception is caught by the inner catch_all_ref, which runs the
+    ;; local.set, so this should be dropped
+    (local.set $x (i32.const 1))
+  )
+
+  ;; CHECK:      (func $nested-try_table2 (type $0)
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (local $exn exnref)
+  ;; CHECK-NEXT:  (local $pair (i32 exnref))
+  ;; CHECK-NEXT:  (block $catch_all0
+  ;; CHECK-NEXT:   (try_table (catch_all $catch_all0)
+  ;; CHECK-NEXT:    (local.set $pair
+  ;; CHECK-NEXT:     (block $catch1 (type $1) (result i32 exnref)
+  ;; CHECK-NEXT:      (try_table (catch_ref $e-i32 $catch1)
+  ;; CHECK-NEXT:       (throw $e-i32
+  ;; CHECK-NEXT:        (i32.const 0)
+  ;; CHECK-NEXT:       )
+  ;; CHECK-NEXT:      )
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (local.set $exn
+  ;; CHECK-NEXT:     (tuple.extract 2 1
+  ;; CHECK-NEXT:      (local.get $pair)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (local.set $x
+  ;; CHECK-NEXT:     (i32.const 1)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:    (throw_ref
+  ;; CHECK-NEXT:     (local.get $exn)
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $x
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $nested-try_table2
+    (local $x i32)
+    (local $exn exnref)
+    (local $pair (i32 exnref))
+    (block $catch_all0
+      (try_table (catch_all $catch_all0)
+        (local.set $pair
+          (block $catch1 (result i32 exnref)
+            (try_table (catch_ref $e-i32 $catch1)
+              (throw $e-i32 (i32.const 0))
+            )
+          )
+        )
+        (local.set $exn
+          (tuple.extract 2 1 (local.get $pair))
+        )
+        (local.set $x (i32.const 1))
+        (throw_ref (local.get $exn))
+      )
+    )
+    ;; Unlike nested-try_table1, the exception may not be caught by the inner
+    ;; catch, so the local.set may not run. So this should NOT be dropped.
+    ;; TODO This actually can be removed if we analyze tags in CFGWalker,
+    ;; because we throw an i32 and catch an i32 too in the inner try_table. Add
+    ;; this to the analysis.
+    (local.set $x (i32.const 1))
+  )
+
+  ;; CHECK:      (func $nested-try_table3 (type $0)
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (local $exn exnref)
+  ;; CHECK-NEXT:  (local $pair (i32 exnref))
+  ;; CHECK-NEXT:  (block $catch_all0
+  ;; CHECK-NEXT:   (try_table (catch_all $catch_all0)
+  ;; CHECK-NEXT:    (block $outer1
+  ;; CHECK-NEXT:     (local.set $pair
+  ;; CHECK-NEXT:      (block $catch1 (type $1) (result i32 exnref)
+  ;; CHECK-NEXT:       (try_table (catch_ref $e-i32 $catch1)
+  ;; CHECK-NEXT:        (call $foo)
+  ;; CHECK-NEXT:       )
+  ;; CHECK-NEXT:       (br $outer1)
+  ;; CHECK-NEXT:      )
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (local.set $exn
+  ;; CHECK-NEXT:      (tuple.extract 2 1
+  ;; CHECK-NEXT:       (local.get $pair)
+  ;; CHECK-NEXT:      )
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (local.set $x
+  ;; CHECK-NEXT:      (i32.const 1)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:     (throw_ref
+  ;; CHECK-NEXT:      (local.get $exn)
+  ;; CHECK-NEXT:     )
+  ;; CHECK-NEXT:    )
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (local.set $x
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $nested-try_table3
+    (local $x i32)
+    (local $exn exnref)
+    (local $pair (i32 exnref))
+    (block $catch_all0
+      (try_table (catch_all $catch_all0)
+        (block $outer1
+          (local.set $pair
+            (block $catch1 (result i32 exnref)
+              (try_table (catch_ref $e-i32 $catch1)
+                (call $foo)
+              )
+              (br $outer1)
+            )
+          )
+          (local.set $exn
+            (tuple.extract 2 1 (local.get $pair))
+          )
+          (local.set $x (i32.const 1))
+          (throw_ref (local.get $exn))
+        )
+      )
+    )
+    ;; Unlike nested-try_table1, the exception may not be caught by the inner
+    ;; catch, so the local.set may not run. So this should NOT be dropped.
+    ;; Unlike nested-try_table2, In this case we don't know what (call $foo)
+    ;; will throw, so we can't drop this even if we analyze tags.
+    (local.set $x (i32.const 1))
+  )
+
+  ;; CHECK:      (func $catchless-try_table (type $0)
+  ;; CHECK-NEXT:  (local $x i32)
+  ;; CHECK-NEXT:  (try_table
+  ;; CHECK-NEXT:   (call $foo)
+  ;; CHECK-NEXT:   (local.set $x
+  ;; CHECK-NEXT:    (i32.const 1)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (i32.const 1)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $catchless-try_table
+    (local $x i32)
+    (try_table
+      (call $foo)
+      (local.set $x (i32.const 1))
+    )
+    ;; The only way we end up here is when (call $foo) does not throw, because
+    ;; if (call $foo) throws, it will throw to the caller because it is within
+    ;; a catchless try_table. In that case the local.set after (call $foo) would
+    ;; have run before this, so this can be dropped.
+    (local.set $x (i32.const 1))
+  )
+)