[Exceptions] Finish interpreter + optimizer support for try_table. (#6814)

* Add interpreter support for exnref values.
* Fix optimization passes to support try_table.
* Enable the interpreter (but not in V8, see code) on exceptions.

15 files changed, 218 insertions, 29 deletions

diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index 0f78d37b7..c32d6efbf 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -128,7 +128,12 @@ void ReFinalize::visitTableFill(TableFill* curr) { curr->finalize(); }
 void ReFinalize::visitTableCopy(TableCopy* curr) { curr->finalize(); }
 void ReFinalize::visitTableInit(TableInit* curr) { curr->finalize(); }
 void ReFinalize::visitTry(Try* curr) { curr->finalize(); }
-void ReFinalize::visitTryTable(TryTable* curr) { curr->finalize(); }
+void ReFinalize::visitTryTable(TryTable* curr) {
+  curr->finalize();
+  for (size_t i = 0; i < curr->catchDests.size(); i++) {
+    updateBreakValueType(curr->catchDests[i], curr->sentTypes[i]);
+  }
+}
 void ReFinalize::visitThrow(Throw* curr) { curr->finalize(); }
 void ReFinalize::visitRethrow(Rethrow* curr) { curr->finalize(); }
 void ReFinalize::visitThrowRef(ThrowRef* curr) { curr->finalize(); }
diff --git a/src/ir/effects.h b/src/ir/effects.h
index fee8b3441..716624d64 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -431,6 +431,14 @@ private:
         self->pushTask(doStartTry, currp);
         return;
       }
+      if (auto* tryTable = curr->dynCast<TryTable>()) {
+        // We need to increment try depth before starting.
+        self->pushTask(doEndTryTable, currp);
+        self->pushTask(doVisitTryTable, currp);
+        self->pushTask(scan, &tryTable->body);
+        self->pushTask(doStartTryTable, currp);
+        return;
+      }
       PostWalker<InternalAnalyzer, OverriddenVisitor<InternalAnalyzer>>::scan(
         self, currp);
     }
@@ -472,6 +480,24 @@ private:
       self->parent.catchDepth--;
     }
 
+    static void doStartTryTable(InternalAnalyzer* self, Expression** currp) {
+      auto* curr = (*currp)->cast<TryTable>();
+      // We only count 'try_table's with a 'catch_all' because instructions
+      // within a 'try_table' without a 'catch_all' can still throw outside of
+      // the try.
+      if (curr->hasCatchAll()) {
+        self->parent.tryDepth++;
+      }
+    }
+
+    static void doEndTryTable(InternalAnalyzer* self, Expression** currp) {
+      auto* curr = (*currp)->cast<TryTable>();
+      if (curr->hasCatchAll()) {
+        assert(self->parent.tryDepth > 0 && "try depth cannot be negative");
+        self->parent.tryDepth--;
+      }
+    }
+
     void visitBlock(Block* curr) {
       if (curr->name.is()) {
         parent.breakTargets.erase(curr->name); // these were internal breaks
diff --git a/src/ir/linear-execution.h b/src/ir/linear-execution.h
index c6593bd64..e8b1923aa 100644
--- a/src/ir/linear-execution.h
+++ b/src/ir/linear-execution.h
@@ -171,6 +171,12 @@ struct LinearExecutionWalker : public PostWalker<SubType, VisitorType> {
         self->pushTask(SubType::scan, &curr->cast<Try>()->body);
         break;
       }
+      case Expression::Id::TryTableId: {
+        self->pushTask(SubType::doVisitTryTable, currp);
+        self->pushTask(SubType::doNoteNonLinear, currp);
+        self->pushTask(SubType::scan, &curr->cast<TryTable>()->body);
+        break;
+      }
       case Expression::Id::ThrowId: {
         self->pushTask(SubType::doVisitThrow, currp);
         self->pushTask(SubType::doNoteNonLinear, currp);
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp
index e7454c7c6..e5e6cf659 100644
--- a/src/ir/possible-contents.cpp
+++ b/src/ir/possible-contents.cpp
@@ -1135,8 +1135,38 @@ struct InfoCollector
     }
   }
   void visitTryTable(TryTable* curr) {
-    // TODO: optimize when possible
-    addRoot(curr);
+    receiveChildValue(curr->body, curr);
+
+    // Connect caught tags with their branch targets, and materialize non-null
+    // exnref values.
+    auto numTags = curr->catchTags.size();
+    for (Index tagIndex = 0; tagIndex < numTags; tagIndex++) {
+      auto tag = curr->catchTags[tagIndex];
+      auto target = curr->catchDests[tagIndex];
+
+      Index exnrefIndex = 0;
+      if (tag.is()) {
+        auto params = getModule()->getTag(tag)->sig.params;
+
+        for (Index i = 0; i < params.size(); i++) {
+          if (isRelevant(params[i])) {
+            info.links.push_back(
+              {TagLocation{tag, i},
+               BreakTargetLocation{getFunction(), target, i}});
+          }
+        }
+
+        exnrefIndex = params.size();
+      }
+
+      if (curr->catchRefs[tagIndex]) {
+        auto location = CaughtExnRefLocation{};
+        addRoot(location,
+                PossibleContents::fromType(Type(HeapType::exn, NonNullable)));
+        info.links.push_back(
+          {location, BreakTargetLocation{getFunction(), target, exnrefIndex}});
+      }
+    }
   }
   void visitThrow(Throw* curr) {
     auto& operands = curr->operands;
diff --git a/src/ir/possible-contents.h b/src/ir/possible-contents.h
index 5ec4f758f..7b88483cf 100644
--- a/src/ir/possible-contents.h
+++ b/src/ir/possible-contents.h
@@ -473,6 +473,15 @@ struct TagLocation {
   }
 };
 
+// The location of an exnref materialized by a catch_ref or catch_all_ref clause
+// of a try_table. No data is stored here. exnrefs contain a tag and a payload
+// at run-time, as well as potential metadata such as stack traces, but we don't
+// track that. So this is the same as NullLocation in a way: we just need *a*
+// source of contents for places that receive an exnref.
+struct CaughtExnRefLocation {
+  bool operator==(const CaughtExnRefLocation& other) const { return true; }
+};
+
 // A null value. This is used as the location of the default value of a var in a
 // function, a null written to a struct field in struct.new_with_default, etc.
 struct NullLocation {
@@ -520,6 +529,7 @@ using Location = std::variant<ExpressionLocation,
                               SignatureResultLocation,
                               DataLocation,
                               TagLocation,
+                              CaughtExnRefLocation,
                               NullLocation,
                               ConeReadLocation>;
 
@@ -608,6 +618,12 @@ template<> struct hash<wasm::TagLocation> {
   }
 };
 
+template<> struct hash<wasm::CaughtExnRefLocation> {
+  size_t operator()(const wasm::CaughtExnRefLocation& loc) const {
+    return std::hash<const char*>()("caught-exnref-location");
+  }
+};
+
 template<> struct hash<wasm::NullLocation> {
   size_t operator()(const wasm::NullLocation& loc) const {
     return std::hash<wasm::Type>{}(loc.type);
diff --git a/src/literal.h b/src/literal.h
index d247b0c84..dd6247d00 100644
--- a/src/literal.h
+++ b/src/literal.h
@@ -32,6 +32,7 @@ namespace wasm {
 
 class Literals;
 struct GCData;
+struct ExnData;
 
 class Literal {
   // store only integers, whose bits are deterministic. floats
@@ -44,6 +45,7 @@ class Literal {
     int64_t i64;
     uint8_t v128[16];
     // funcref function name. `isNull()` indicates a `null` value.
+    // TODO: handle cross-module calls using something other than a Name here.
     Name func;
     // A reference to GC data, either a Struct or an Array. For both of those we
     // store the referred data as a Literals object (which is natural for an
@@ -56,6 +58,8 @@ class Literal {
     // reference as its sole value even though internal i31 references do not
     // have a gcData.
     std::shared_ptr<GCData> gcData;
+    // A reference to Exn data.
+    std::shared_ptr<ExnData> exnData;
   };
 
 public:
@@ -85,6 +89,7 @@ public:
     assert(type.isSignature());
   }
   explicit Literal(std::shared_ptr<GCData> gcData, HeapType type);
+  explicit Literal(std::shared_ptr<ExnData> exnData);
   explicit Literal(std::string_view string);
   Literal(const Literal& other);
   Literal& operator=(const Literal& other);
@@ -96,6 +101,7 @@ public:
   // Whether this is GC data, that is, something stored on the heap (aside from
   // a null or i31). This includes structs, arrays, and also strings.
   bool isData() const { return type.isData(); }
+  bool isExn() const { return type.isExn(); }
   bool isString() const { return type.isString(); }
 
   bool isNull() const { return type.isNull(); }
@@ -303,6 +309,7 @@ public:
     return func;
   }
   std::shared_ptr<GCData> getGCData() const;
+  std::shared_ptr<ExnData> getExnData() const;
 
   // careful!
   int32_t* geti32Ptr() {
@@ -742,6 +749,18 @@ struct GCData {
   GCData(HeapType type, Literals values) : type(type), values(values) {}
 };
 
+// The data of a (ref exn) literal.
+struct ExnData {
+  // The tag of this exn data.
+  // TODO: handle cross-module calls using something other than a Name here.
+  Name tag;
+
+  // The payload of this exn data.
+  Literals payload;
+
+  ExnData(Name tag, Literals payload) : tag(tag), payload(payload) {}
+};
+
 } // namespace wasm
 
 namespace std {
diff --git a/src/passes/CodeFolding.cpp b/src/passes/CodeFolding.cpp
index dc2301f9c..2d17f6d31 100644
--- a/src/passes/CodeFolding.cpp
+++ b/src/passes/CodeFolding.cpp
@@ -343,15 +343,18 @@ private:
         if (effects.danglingPop) {
           return false;
         }
-        // When an expression can throw and it is within a try scope, taking it
-        // out of the try scope changes the program's behavior, because the
-        // expression that would otherwise have been caught by the try now
-        // throws up to the next try scope or even up to the caller. We restrict
-        // the move if 'outOf' contains a 'try' anywhere in it. This is a
-        // conservative approximation because there can be cases that 'try' is
-        // within the expression that may throw so it is safe to take the
-        // expression out.
-        if (effects.throws() && !FindAll<Try>(outOf).list.empty()) {
+        // When an expression can throw and it is within a try/try_table scope,
+        // taking it out of the try/try_table scope changes the program's
+        // behavior, because the expression that would otherwise have been
+        // caught by the try/try_table now throws up to the next try/try_table
+        // scope or even up to the caller. We restrict the move if 'outOf'
+        // contains a 'try' or 'try_table' anywhere in it. This is a
+        // conservative approximation because there can be cases that
+        // 'try'/'try_table' is within the expression that may throw so it is
+        // safe to take the expression out.
+        // TODO: optimize this check to avoid two FindAlls.
+        if (effects.throws() &&
+            (FindAll<Try>(outOf).has() || FindAll<TryTable>(outOf).has())) {
           return false;
         }
       }
diff --git a/src/passes/DeadCodeElimination.cpp b/src/passes/DeadCodeElimination.cpp
index 996133ad5..f8acde7b0 100644
--- a/src/passes/DeadCodeElimination.cpp
+++ b/src/passes/DeadCodeElimination.cpp
@@ -185,6 +185,12 @@ struct DeadCodeElimination
           tryy->body->type == Type::unreachable && allCatchesUnreachable) {
         typeUpdater.changeType(tryy, Type::unreachable);
       }
+    } else if (auto* tryTable = curr->dynCast<TryTable>()) {
+      // try_table can finish normally only if its body finishes normally.
+      if (tryTable->type != Type::unreachable &&
+          tryTable->body->type == Type::unreachable) {
+        typeUpdater.changeType(tryTable, Type::unreachable);
+      }
     } else {
       WASM_UNREACHABLE("unimplemented DCE control flow structure");
     }
diff --git a/src/passes/SimplifyLocals.cpp b/src/passes/SimplifyLocals.cpp
index 28b13980b..eca503ad4 100644
--- a/src/passes/SimplifyLocals.cpp
+++ b/src/passes/SimplifyLocals.cpp
@@ -321,9 +321,9 @@ struct SimplifyLocals
            Expression** currp) {
     Expression* curr = *currp;
 
-    // Certain expressions cannot be sinked into 'try', and so at the start of
-    // 'try' we forget about them.
-    if (curr->is<Try>()) {
+    // Certain expressions cannot be sinked into 'try'/'try_table', and so at
+    // the start of 'try'/'try_table' we forget about them.
+    if (curr->is<Try>() || curr->is<TryTable>()) {
       std::vector<Index> invalidated;
       for (auto& [index, info] : self->sinkables) {
         // Expressions that may throw cannot be moved into a try (which might
diff --git a/src/passes/Vacuum.cpp b/src/passes/Vacuum.cpp
index 4a4963291..0e49f19c8 100644
--- a/src/passes/Vacuum.cpp
+++ b/src/passes/Vacuum.cpp
@@ -87,7 +87,7 @@ struct Vacuum : public WalkerPass<ExpressionStackWalker<Vacuum>> {
       // Some instructions have special handling in visit*, and we should do
       // nothing for them here.
       if (curr->is<Drop>() || curr->is<Block>() || curr->is<If>() ||
-          curr->is<Loop>() || curr->is<Try>()) {
+          curr->is<Loop>() || curr->is<Try>() || curr->is<TryTable>()) {
         return curr;
       }
       // Check if this expression itself has side effects, ignoring children.
@@ -435,6 +435,15 @@ struct Vacuum : public WalkerPass<ExpressionStackWalker<Vacuum>> {
     }
   }
 
+  void visitTryTable(TryTable* curr) {
+    // If try_table's body does not throw, the whole try_table can be replaced
+    // with the try_table's body.
+    if (!EffectAnalyzer(getPassOptions(), *getModule(), curr->body).throws()) {
+      replaceCurrent(curr->body);
+      return;
+    }
+  }
+
   void visitFunction(Function* curr) {
     auto* optimized =
       optimize(curr->body, curr->getResults() != Type::none, true);
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 644a141a2..1bf135c40 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -47,8 +47,7 @@
 namespace wasm {
 
 struct WasmException {
-  Name tag;
-  Literals values;
+  Literal exn;
 };
 std::ostream& operator<<(std::ostream& o, const WasmException& exn);
 
@@ -204,6 +203,15 @@ protected:
     return Literal(allocation, type.getHeapType());
   }
 
+  // Same as makeGCData but for ExnData.
+  Literal makeExnData(Name tag, const Literals& payload) {
+    auto allocation = std::make_shared<ExnData>(tag, payload);
+#if __has_feature(leak_sanitizer) || __has_feature(address_sanitizer)
+    __lsan_ignore_object(allocation.get());
+#endif
+    return Literal(allocation);
+  }
+
 public:
   // Indicates no limit of maxDepth or maxLoopIterations.
   static const Index NO_LIMIT = 0;
@@ -1428,16 +1436,25 @@ public:
       return flow;
     }
     NOTE_EVAL1(curr->tag);
-    WasmException exn;
-    exn.tag = curr->tag;
-    for (auto item : arguments) {
-      exn.values.push_back(item);
-    }
-    throwException(exn);
+    throwException(WasmException{makeExnData(curr->tag, arguments)});
     WASM_UNREACHABLE("throw");
   }
   Flow visitRethrow(Rethrow* curr) { WASM_UNREACHABLE("unimp"); }
-  Flow visitThrowRef(ThrowRef* curr) { WASM_UNREACHABLE("unimp"); }
+  Flow visitThrowRef(ThrowRef* curr) {
+    NOTE_ENTER("ThrowRef");
+    Flow flow = visit(curr->exnref);
+    if (flow.breaking()) {
+      return flow;
+    }
+    const auto& exnref = flow.getSingleValue();
+    NOTE_EVAL1(exnref);
+    if (exnref.isNull()) {
+      trap("null ref");
+    }
+    assert(exnref.isExn());
+    throwException(WasmException{exnref});
+    WASM_UNREACHABLE("throw");
+  }
   Flow visitRefI31(RefI31* curr) {
     NOTE_ENTER("RefI31");
     Flow flow = visit(curr->value);
@@ -2455,6 +2472,10 @@ public:
     NOTE_ENTER("Try");
     return Flow(NONCONSTANT_FLOW);
   }
+  Flow visitTryTable(TryTable* curr) {
+    NOTE_ENTER("TryTable");
+    return Flow(NONCONSTANT_FLOW);
+  }
   Flow visitRethrow(Rethrow* curr) {
     NOTE_ENTER("Rethrow");
     return Flow(NONCONSTANT_FLOW);
@@ -4103,9 +4124,10 @@ public:
         return ret;
       };
 
+      auto exnData = e.exn.getExnData();
       for (size_t i = 0; i < curr->catchTags.size(); i++) {
-        if (curr->catchTags[i] == e.tag) {
-          multiValues.push_back(e.values);
+        if (curr->catchTags[i] == exnData->tag) {
+          multiValues.push_back(exnData->payload);
           return processCatchBody(curr->catchBodies[i]);
         }
       }
@@ -4119,6 +4141,32 @@ public:
       throw;
     }
   }
+  Flow visitTryTable(TryTable* curr) {
+    NOTE_ENTER("TryTable");
+    try {
+      return self()->visit(curr->body);
+    } catch (const WasmException& e) {
+      auto exnData = e.exn.getExnData();
+      for (size_t i = 0; i < curr->catchTags.size(); i++) {
+        auto catchTag = curr->catchTags[i];
+        if (!catchTag.is() || catchTag == exnData->tag) {
+          Flow ret;
+          ret.breakTo = curr->catchDests[i];
+          if (catchTag.is()) {
+            for (auto item : exnData->payload) {
+              ret.values.push_back(item);
+            }
+          }
+          if (curr->catchRefs[i]) {
+            ret.values.push_back(e.exn);
+          }
+          return ret;
+        }
+      }
+      // This exception is not caught by this try_table. Rethrow it.
+      throw;
+    }
+  }
   Flow visitRethrow(Rethrow* curr) {
     for (int i = exceptionStack.size() - 1; i >= 0; i--) {
       if (exceptionStack[i].second == curr->target) {
diff --git a/src/wasm-type.h b/src/wasm-type.h
index ff1358a12..03c4f8e77 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -170,6 +170,7 @@ public:
   bool isSignature() const;
   bool isStruct() const;
   bool isArray() const;
+  bool isExn() const;
   bool isString() const;
   bool isDefaultable() const;
 
@@ -388,6 +389,7 @@ public:
   bool isContinuation() const { return getKind() == HeapTypeKind::Cont; }
   bool isStruct() const { return getKind() == HeapTypeKind::Struct; }
   bool isArray() const { return getKind() == HeapTypeKind::Array; }
+  bool isExn() const { return isMaybeShared(HeapType::exn); }
   bool isString() const { return isMaybeShared(HeapType::string); }
   bool isBottom() const;
   bool isOpen() const;
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index 9d659f753..650318be3 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -80,6 +80,12 @@ Literal::Literal(std::shared_ptr<GCData> gcData, HeapType type)
          (type.isBottom() && !gcData));
 }
 
+Literal::Literal(std::shared_ptr<ExnData> exnData)
+  : exnData(exnData), type(HeapType::exn, NonNullable) {
+  // The data must not be null.
+  assert(exnData);
+}
+
 Literal::Literal(std::string_view string)
   : gcData(nullptr), type(Type(HeapType::string, NonNullable)) {
   // TODO: we could in theory internalize strings
@@ -133,6 +139,9 @@ Literal::Literal(const Literal& other) : type(other.type) {
     case HeapType::i31:
       i32 = other.i32;
       return;
+    case HeapType::exn:
+      new (&exnData) std::shared_ptr<ExnData>(other.exnData);
+      return;
     case HeapType::ext:
       WASM_UNREACHABLE("handled above with isData()");
     case HeapType::none:
@@ -147,7 +156,6 @@ Literal::Literal(const Literal& other) : type(other.type) {
     case HeapType::cont:
     case HeapType::struct_:
     case HeapType::array:
-    case HeapType::exn:
       WASM_UNREACHABLE("invalid type");
     case HeapType::string:
       WASM_UNREACHABLE("TODO: string literals");
@@ -161,6 +169,8 @@ Literal::~Literal() {
   }
   if (isNull() || isData() || type.getHeapType().isMaybeShared(HeapType::ext)) {
     gcData.~shared_ptr();
+  } else if (isExn()) {
+    exnData.~shared_ptr();
   }
 }
 
@@ -328,6 +338,12 @@ std::shared_ptr<GCData> Literal::getGCData() const {
   return gcData;
 }
 
+std::shared_ptr<ExnData> Literal::getExnData() const {
+  assert(isExn());
+  assert(exnData);
+  return exnData;
+}
+
 Literal Literal::castToF32() {
   assert(type == Type::i32);
   Literal ret(Type::f32);
diff --git a/src/wasm/wasm-interpreter.cpp b/src/wasm/wasm-interpreter.cpp
index b49eeef4b..cd6c232b5 100644
--- a/src/wasm/wasm-interpreter.cpp
+++ b/src/wasm/wasm-interpreter.cpp
@@ -20,7 +20,8 @@ void Indenter::print() {
 #endif // WASM_INTERPRETER_DEBUG
 
 std::ostream& operator<<(std::ostream& o, const WasmException& exn) {
-  return o << exn.tag << " " << exn.values;
+  auto exnData = exn.exn.getExnData();
+  return o << exnData->tag << " " << exnData->payload;
 }
 
 } // namespace wasm
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 84ae51521..1730f1b85 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -814,6 +814,8 @@ bool Type::isStruct() const { return isRef() && getHeapType().isStruct(); }
 
 bool Type::isArray() const { return isRef() && getHeapType().isArray(); }
 
+bool Type::isExn() const { return isRef() && getHeapType().isExn(); }
+
 bool Type::isString() const { return isRef() && getHeapType().isString(); }
 
 bool Type::isDefaultable() const {