Add interpreter support for EH (#2780)

This adds interpreter support for EH instructions. This adds
`ExceptionPackage` struct, which contains info of a thrown exception (an
event tag and thrown values), and the union in `Literal` can take a
`unique_ptr` to `ExceptionPackage`. We need a destructor, a copy
constructor, and an assignment operator for `Literal`, because the union
in `Literal` now has a member that cannot be trivially copied or
deleted.

7 files changed, 294 insertions, 41 deletions

diff --git a/src/literal.h b/src/literal.h
index 652f80bdc..b21f08995 100644
--- a/src/literal.h
+++ b/src/literal.h
@@ -30,6 +30,7 @@
 namespace wasm {
 
 class Literals;
+struct ExceptionPackage;
 
 class Literal {
   // store only integers, whose bits are deterministic. floats
@@ -39,6 +40,7 @@ class Literal {
     int64_t i64;
     uint8_t v128[16];
     Name func; // function name for funcref
+    std::unique_ptr<ExceptionPackage> exn;
   };
 
 public:
@@ -65,6 +67,15 @@ public:
   explicit Literal(const std::array<Literal, 4>&);
   explicit Literal(const std::array<Literal, 2>&);
   explicit Literal(Name func) : func(func), type(Type::funcref) {}
+  explicit Literal(std::unique_ptr<ExceptionPackage> exn)
+    : exn(std::move(exn)), type(Type::exnref) {}
+  Literal(const Literal& other);
+  Literal& operator=(const Literal& other);
+  ~Literal() {
+    if (type == Type::exnref) {
+      exn.~unique_ptr();
+    }
+  }
 
   bool isConcrete() const { return type != Type::none; }
   bool isNone() const { return type == Type::none; }
@@ -104,6 +115,9 @@ public:
 
   static Literal makeNullref() { return Literal(Type(Type::nullref)); }
   static Literal makeFuncref(Name func) { return Literal(func.c_str()); }
+  static Literal makeExnref(std::unique_ptr<ExceptionPackage> exn) {
+    return Literal(std::move(exn));
+  }
 
   Literal castToF32();
   Literal castToF64();
@@ -127,7 +141,14 @@ public:
     return bit_cast<double>(i64);
   }
   std::array<uint8_t, 16> getv128() const;
-  Name getFunc() const { return func; }
+  Name getFunc() const {
+    assert(type == Type::funcref);
+    return func;
+  }
+  const ExceptionPackage& getExceptionPackage() const {
+    assert(type == Type::exnref);
+    return *exn.get();
+  }
 
   // careful!
   int32_t* geti32Ptr() {
@@ -472,8 +493,16 @@ public:
   bool isConcrete() { return size() != 0; }
 };
 
+// A struct for a thrown exception, which includes a tag (event) and thrown
+// values
+struct ExceptionPackage {
+  Name event;
+  Literals values;
+};
+
 std::ostream& operator<<(std::ostream& o, wasm::Literal literal);
 std::ostream& operator<<(std::ostream& o, wasm::Literals literals);
+std::ostream& operator<<(std::ostream& o, const ExceptionPackage& exn);
 
 } // namespace wasm
 
diff --git a/src/shell-interface.h b/src/shell-interface.h
index a5293ac76..8c5793bfc 100644
--- a/src/shell-interface.h
+++ b/src/shell-interface.h
@@ -221,6 +221,8 @@ struct ShellExternalInterface : ModuleInstance::ExternalInterface {
     std::cout << "[trap " << why << "]\n";
     throw TrapException();
   }
+
+  void throwException(Literal exn) override { throw WasmException(exn); }
 };
 
 } // namespace wasm
diff --git a/src/tools/wasm-ctor-eval.cpp b/src/tools/wasm-ctor-eval.cpp
index ca0dafd8e..7ef52dd5f 100644
--- a/src/tools/wasm-ctor-eval.cpp
+++ b/src/tools/wasm-ctor-eval.cpp
@@ -291,6 +291,12 @@ struct CtorEvalExternalInterface : EvallingModuleInstance::ExternalInterface {
     throw FailToEvalException(std::string("trap: ") + why);
   }
 
+  void throwException(Literal exn) override {
+    std::stringstream ss;
+    ss << "exception thrown: " << exn;
+    throw FailToEvalException(ss.str());
+  }
+
 private:
   // TODO: handle unaligned too, see shell-interface
 
diff --git a/src/tools/wasm-shell.cpp b/src/tools/wasm-shell.cpp
index 301da6cac..1430c1891 100644
--- a/src/tools/wasm-shell.cpp
+++ b/src/tools/wasm-shell.cpp
@@ -209,6 +209,9 @@ static void run_asserts(Name moduleName,
         result = operation.operate();
       } catch (const TrapException&) {
         trapped = true;
+      } catch (const WasmException& e) {
+        std::cout << "[exception thrown: " << e.exn << "]" << std::endl;
+        trapped = true;
       }
       if (id == ASSERT_RETURN) {
         assert(!trapped);
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 0124055ad..2841dc432 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -40,6 +40,11 @@
 
 namespace wasm {
 
+struct WasmException {
+  WasmException(Literal exn) : exn(exn) {}
+  Literal exn;
+};
+
 using namespace cashew;
 
 // Utilities
@@ -81,7 +86,7 @@ public:
     }
   }
 
-  friend std::ostream& operator<<(std::ostream& o, Flow& flow) {
+  friend std::ostream& operator<<(std::ostream& o, const Flow& flow) {
     o << "(flow " << (flow.breakTo.is() ? flow.breakTo.str : "-") << " : {";
     for (size_t i = 0; i < flow.values.size(); ++i) {
       if (i > 0) {
@@ -1228,11 +1233,7 @@ public:
     NOTE_NAME(curr->func);
     return Literal::makeFuncref(curr->func);
   }
-  Flow visitTry(Try* curr) {
-    NOTE_ENTER("Try");
-    // FIXME This currently only executes 'try' part. Correctly implement this.
-    return visit(curr->body);
-  }
+  Flow visitTry(Try* curr) { WASM_UNREACHABLE("unimp"); }
   Flow visitThrow(Throw* curr) {
     NOTE_ENTER("Throw");
     LiteralList arguments;
@@ -1241,8 +1242,12 @@ public:
       return flow;
     }
     NOTE_EVAL1(curr->event);
-    // FIXME This currently traps. Correctly implement throw.
-    trap("throw");
+    auto exn = std::make_unique<ExceptionPackage>();
+    exn->event = curr->event;
+    for (auto item : arguments) {
+      exn->values.push_back(item);
+    }
+    throwException(Literal(std::move(exn)));
     WASM_UNREACHABLE("throw");
   }
   Flow visitRethrow(Rethrow* curr) {
@@ -1254,13 +1259,14 @@ public:
     if (flow.getType() == Type::nullref) {
       trap("rethrow: argument is null");
     }
-    // FIXME This currently traps. Correctly implement rethrow.
-    trap("rethrow");
+    throwException(flow.getSingleValue());
     WASM_UNREACHABLE("rethrow");
   }
   Flow visitBrOnExn(BrOnExn* curr) { WASM_UNREACHABLE("unimp"); }
 
   virtual void trap(const char* why) { WASM_UNREACHABLE("unimp"); }
+
+  virtual void throwException(Literal exn) { WASM_UNREACHABLE("unimp"); }
 };
 
 // Execute a suspected constant expression (precompute and C-API).
@@ -1496,12 +1502,20 @@ public:
     NOTE_ENTER("Pop");
     return Flow(NONCONSTANT_FLOW);
   }
+  Flow visitTry(Try* curr) {
+    NOTE_ENTER("Try");
+    return Flow(NONCONSTANT_FLOW);
+  }
   Flow visitBrOnExn(BrOnExn* curr) {
     NOTE_ENTER("BrOnExn");
     return Flow(NONCONSTANT_FLOW);
   }
 
   void trap(const char* why) override { throw NonconstantException(); }
+
+  virtual void throwException(Literal exn) override {
+    throw NonconstantException();
+  }
 };
 
 // Execute an initializer expression of a global, data or element segment.
@@ -1548,6 +1562,7 @@ public:
                                SubType& instance) = 0;
     virtual void growMemory(Address oldSize, Address newSize) = 0;
     virtual void trap(const char* why) = 0;
+    virtual void throwException(Literal exnref) = 0;
 
     // the default impls for load and store switch on the sizes. you can either
     // customize load/store, or the sub-functions which they call
@@ -2378,6 +2393,15 @@ private:
       }
       return {};
     }
+    Flow visitTry(Try* curr) {
+      NOTE_ENTER("Try");
+      try {
+        return this->visit(curr->body);
+      } catch (const WasmException& e) {
+        instance.multiValues.push_back(e.exn);
+        return this->visit(curr->catchBody);
+      }
+    }
     Flow visitBrOnExn(BrOnExn* curr) {
       NOTE_ENTER("BrOnExn");
       Flow flow = this->visit(curr->exnref);
@@ -2387,13 +2411,12 @@ private:
       if (flow.getType() == Type::nullref) {
         trap("br_on_exn: argument is null");
       }
-      // Currently we don't have a way to tell if the given expression matches
-      // the given event tag. Assume any exnref matches for now and always
-      // extracts a zero or null value of the given event type.
-      // FIXME Correctly implement event matching and extraction.
-      Type eventType = instance.wasm.getEvent(curr->event)->sig.params;
-      flow.values =
-        eventType == Type::none ? Literals() : Literal::makeZero(eventType);
+      const ExceptionPackage& ex = flow.getSingleValue().getExceptionPackage();
+      if (curr->event != ex.event) { // Not taken
+        return flow;
+      }
+      // Taken
+      flow.values = ex.values;
       flow.breakTo = curr->name;
       return flow;
     }
@@ -2418,6 +2441,10 @@ private:
       instance.externalInterface->trap(why);
     }
 
+    void throwException(Literal exn) override {
+      instance.externalInterface->throwException(exn);
+    }
+
     // Given a value, wrap it to a smaller given number of bytes.
     Literal wrapToSmallerSize(Literal value, Index bytes) {
       if (value.type == Type::i32) {
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index b740ae520..33e53ca48 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -33,6 +33,39 @@ Literal::Literal(const uint8_t init[16]) : type(Type::v128) {
   memcpy(&v128, init, 16);
 }
 
+Literal::Literal(const Literal& other) { *this = other; }
+
+Literal& Literal::operator=(const Literal& other) {
+  type = other.type;
+  assert(!type.isMulti());
+  switch (type.getSingle()) {
+    case Type::i32:
+    case Type::f32:
+      i32 = other.i32;
+      break;
+    case Type::i64:
+    case Type::f64:
+      i64 = other.i64;
+      break;
+    case Type::v128:
+      memcpy(&v128, other.v128, 16);
+      break;
+    case Type::funcref:
+      func = other.func;
+      break;
+    case Type::exnref:
+      new (&exn) auto(std::make_unique<ExceptionPackage>(*other.exn));
+      break;
+    case Type::none:
+    case Type::nullref:
+      break;
+    case Type::anyref:
+    case Type::unreachable:
+      WASM_UNREACHABLE("unexpected type");
+  }
+  return *this;
+}
+
 template<typename LaneT, int Lanes>
 static void extractBytes(uint8_t (&dest)[16], const LaneArray<Lanes>& lanes) {
   std::array<uint8_t, 16> bytes;
@@ -310,8 +343,10 @@ std::ostream& operator<<(std::ostream& o, Literal literal) {
     case Type::nullref:
       o << "nullref";
       break;
-    case Type::anyref:
     case Type::exnref:
+      o << "exnref(" << literal.getExceptionPackage() << ")";
+      break;
+    case Type::anyref:
     case Type::unreachable:
       WASM_UNREACHABLE("invalid type");
   }
@@ -334,6 +369,10 @@ std::ostream& operator<<(std::ostream& o, wasm::Literals literals) {
   }
 }
 
+std::ostream& operator<<(std::ostream& o, const ExceptionPackage& exn) {
+  return o << exn.event << " " << exn.values;
+}
+
 Literal Literal::countLeadingZeroes() const {
   if (type == Type::i32) {
     return Literal((int32_t)CountLeadingZeroes(i32));
diff --git a/test/spec/exception-handling.wast b/test/spec/exception-handling.wast
index 6e0ca9055..d8ae48631 100644
--- a/test/spec/exception-handling.wast
+++ b/test/spec/exception-handling.wast
@@ -1,39 +1,186 @@
 (module
-  (event $e0 (attr 0) (param i32))
-  (event $e1 (attr 0) (param i32 f32))
+  (event $e-v (attr 0))
+  (event $e-i32 (attr 0) (param i32))
+  (event $e-i32-f32 (attr 0) (param i32 f32))
 
-  (func (export "throw_test")
-    (throw $e0 (i32.const 0))
+  (func $throw_single_value (export "throw_single_value")
+    (throw $e-i32 (i32.const 5))
   )
 
-  (func (export "rethrow_test")
+  (func (export "throw_multiple_values")
+    (throw $e-i32-f32 (i32.const 3) (f32.const 3.5))
+  )
+
+  (func (export "rethrow_nullref")
     (rethrow (ref.null))
   )
 
-  (func (export "try_test") (result i32)
+  (func (export "try_nothrow") (result i32)
     (try (result i32)
       (i32.const 3)
       (catch
         (drop (exnref.pop))
+        (i32.const 0)
+      )
+    )
+  )
+
+  (func (export "try_throw_catch") (result i32)
+    (try (result i32)
+      (throw $e-i32 (i32.const 5))
+      (catch
+        (drop (exnref.pop))
         (i32.const 3)
       )
     )
   )
 
-  (func (export "br_on_exn_test") (result i32)
+  (func (export "try_call_catch") (result i32)
+    (try (result i32)
+      (block
+        (call $throw_single_value)
+        (unreachable)
+      )
+      (catch
+        (drop (exnref.pop))
+        (i32.const 3)
+      )
+    )
+  )
+
+  (func (export "try_throw_rethrow")
+    (try
+      (throw $e-i32 (i32.const 5))
+      (catch
+        (rethrow (exnref.pop))
+      )
+    )
+  )
+
+  (func $try_call_rethrow (export "try_call_rethrow")
+    (try
+      (call $throw_single_value)
+      (catch
+        (rethrow (exnref.pop))
+      )
+    )
+  )
+
+  (func (export "br_on_exn_nullref") (result i32)
     (block $l0 (result i32)
       (drop
-        (br_on_exn $l0 $e0 (ref.null))
+        (br_on_exn $l0 $e-i32 (ref.null))
       )
       (i32.const 0)
     )
   )
+
+  (func (export "br_on_exn_match_no_value") (local $exn exnref)
+    (try
+      (throw $e-v)
+      (catch
+        (local.set $exn (exnref.pop))
+        (block $l0
+          (rethrow
+            (br_on_exn $l0 $e-v (local.get $exn))
+          )
+        )
+      )
+    )
+  )
+
+  (func (export "br_on_exn_match_single_value") (result i32) (local $exn exnref)
+    (try (result i32)
+      (throw $e-i32 (i32.const 5))
+      (catch
+        (local.set $exn (exnref.pop))
+        (block $l0 (result i32)
+          (rethrow
+            (br_on_exn $l0 $e-i32 (local.get $exn))
+          )
+        )
+      )
+    )
+  )
+
+  (func (export "br_on_exn_match_multiple_values") (result i32 f32)
+        (local $exn exnref)
+    (try (result i32 f32)
+      (throw $e-i32-f32 (i32.const 3) (f32.const 3.5))
+      (catch
+        (local.set $exn (exnref.pop))
+        (block $l0 (result i32 f32)
+          (rethrow
+            (br_on_exn $l0 $e-i32-f32 (local.get $exn))
+          )
+        )
+      )
+    )
+  )
+
+  (func (export "br_on_exn_dont_match") (local $exn exnref)
+    (try
+      (throw $e-i32 (i32.const 5))
+      (catch
+        (local.set $exn (exnref.pop))
+        (block $l0
+          (rethrow
+            (br_on_exn $l0 $e-v (local.get $exn))
+          )
+        )
+      )
+    )
+  )
+
+  (func (export "call_br_on_exn") (result i32) (local $exn exnref)
+    (try (result i32)
+      (block
+        (call $throw_single_value)
+        (unreachable)
+      )
+      (catch
+        (local.set $exn (exnref.pop))
+        (block $l0 (result i32)
+          (rethrow
+            (br_on_exn $l0 $e-i32 (local.get $exn))
+          )
+        )
+      )
+    )
+  )
+
+  (func (export "call_rethrow_br_on_exn") (result i32) (local $exn exnref)
+    (try (result i32)
+      (block
+        (call $try_call_rethrow)
+        (unreachable)
+      )
+      (catch
+        (local.set $exn (exnref.pop))
+        (block $l0 (result i32)
+          (rethrow
+            (br_on_exn $l0 $e-i32 (local.get $exn))
+          )
+        )
+      )
+    )
+  )
 )
 
-(assert_trap (invoke "throw_test"))
-(assert_trap (invoke "rethrow_test"))
-(assert_return (invoke "try_test") (i32.const 3))
-(assert_trap (invoke "br_on_exn_test"))
+(assert_trap (invoke "throw_single_value"))
+(assert_trap (invoke "throw_multiple_values"))
+(assert_trap (invoke "rethrow_nullref"))
+(assert_return (invoke "try_nothrow") (i32.const 3))
+(assert_return (invoke "try_throw_catch") (i32.const 3))
+(assert_return (invoke "try_call_catch") (i32.const 3))
+(assert_trap (invoke "try_throw_rethrow"))
+(assert_trap (invoke "try_call_rethrow"))
+(assert_trap (invoke "br_on_exn_nullref"))
+(assert_return (invoke "br_on_exn_match_no_value"))
+(assert_return (invoke "br_on_exn_match_single_value") (i32.const 5))
+(assert_return (invoke "br_on_exn_match_multiple_values") (tuple.make (i32.const 3) (f32.const 3.5)))
+(assert_trap (invoke "br_on_exn_dont_match"))
+(assert_return (invoke "call_rethrow_br_on_exn") (i32.const 5))
 
 (assert_invalid
   (module
@@ -61,9 +208,9 @@
 
 (assert_invalid
   (module
-    (event $e0 (attr 0) (param i32))
+    (event $e-i32 (attr 0) (param i32))
     (func $f0
-      (throw $e0 (f32.const 0))
+      (throw $e-i32 (f32.const 0))
     )
   )
   "event param types must match"
@@ -71,9 +218,9 @@
 
 (assert_invalid
   (module
-    (event $e0 (attr 0) (param i32 f32))
+    (event $e-i32 (attr 0) (param i32 f32))
     (func $f0
-      (throw $e0 (f32.const 0))
+      (throw $e-i32 (f32.const 0))
     )
   )
   "event's param numbers must match"
@@ -90,11 +237,11 @@
 
 (assert_invalid
   (module
-    (event $e0 (attr 0) (param i32))
+    (event $e-i32 (attr 0) (param i32))
     (func $f0 (result i32)
       (block $l0 (result i32)
         (drop
-          (br_on_exn $l0 $e0 (i32.const 0))
+          (br_on_exn $l0 $e-i32 (i32.const 0))
         )
         (i32.const 0)
       )
@@ -105,11 +252,11 @@
 
 (assert_invalid
   (module
-    (event $e0 (attr 0) (param i32))
+    (event $e-i32 (attr 0) (param i32))
     (func $f0 (result i32) (local $0 exnref)
       (block $l0 (result i32)
         (i32.eqz
-          (br_on_exn $l0 $e0 (local.get $0))
+          (br_on_exn $l0 $e-i32 (local.get $0))
         )
       )
     )
@@ -119,11 +266,11 @@
 
 (assert_invalid
   (module
-    (event $e0 (attr 0) (param i32))
+    (event $e-i32 (attr 0) (param i32))
     (func $f0 (result f32) (local $0 exnref)
       (block $l0 (result f32)
         (drop
-          (br_on_exn $l0 $e0 (local.get $0))
+          (br_on_exn $l0 $e-i32 (local.get $0))
         )
         (f32.const 0)
       )