[GC] Fully implement RTT semantics (#3441)

This adds info to RTT literals so that they can represent the chain of
rtt.canon/sub commands that generated them, and it adds an internal
RTT for each GC allocation (array or struct).

The approach taken is to simply store the full chain of rtt.sub types
that led to each literal. This is not efficient, but it is simple and seems
sufficient for the semantics described in the GC MVP doc - specifically,
only the types matter, in that repeated executions of rtt.canon/sub
on the same inputs yield equal outputs.

This PR fixes a bunch of minor issues regarding that, enough to allow testing
of the optimization and execution of ref.test/cast.

1 files changed, 42 insertions, 13 deletions

diff --git a/src/literal.h b/src/literal.h
index 8a1829d10..bf8937533 100644
--- a/src/literal.h
+++ b/src/literal.h
@@ -31,6 +31,10 @@ namespace wasm {
 
 class Literals;
 struct ExceptionPackage;
+struct GCData;
+// Subclass the vector type so that this is not easily confused with a vector of
+// types (which could be confusing on the Literal constructor).
+struct RttSupers : std::vector<Type> {};
 
 class Literal {
   // store only integers, whose bits are deterministic. floats
@@ -47,7 +51,20 @@ class Literal {
     // we store the referred data as a Literals object (which is natural for an
     // Array, and for a Struct, is just the fields in order). The type is used
     // to indicate whether this is a Struct or an Array, and of what type.
-    std::shared_ptr<Literals> gcData;
+    std::shared_ptr<GCData> gcData;
+    // RTT values are "structural" in that the MVP doc says that multiple
+    // invocations of ref.canon return things that are observably identical, and
+    // the same is true for ref.sub. That is, what matters is the types; there
+    // is no unique identifier created in each ref.canon/sub. To track the
+    // types, we maintain a simple vector of the supertypes. Thus, an rtt.canon
+    // of type A will have an empty vector; an rtt.sub of type B of that initial
+    // canon would have a vector of size 1 containing A; a subsequent rtt.sub
+    // would have A, B, and so forth.
+    // (This encoding is very inefficient and not at all what a production VM
+    // would do, but it is simple.)
+    // The unique_ptr here is to avoid increasing the size of the union as well
+    // as the Literal class itself.
+    std::unique_ptr<RttSupers> rttSupers;
     // TODO: Literals of type `externref` can only be `null` currently but we
     // will need to represent extern values eventually, to
     // 1) run the spec tests and fuzzer with reference types enabled and
@@ -79,18 +96,11 @@ public:
   explicit Literal(Name func, Type type) : func(func), type(type) {}
   explicit Literal(std::unique_ptr<ExceptionPackage>&& exn)
     : exn(std::move(exn)), type(Type::exnref) {}
-  explicit Literal(std::shared_ptr<Literals> gcData, Type type)
-    : gcData(gcData), type(type) {}
+  explicit Literal(std::shared_ptr<GCData> gcData, Type type);
+  explicit Literal(std::unique_ptr<RttSupers>&& rttSupers, Type type);
   Literal(const Literal& other);
   Literal& operator=(const Literal& other);
-  ~Literal() {
-    if (type.isException()) {
-      exn.~unique_ptr();
-    }
-    if (type.isStruct() || type.isArray()) {
-      gcData.~shared_ptr();
-    }
-  }
+  ~Literal();
 
   bool isConcrete() const { return type != Type::none; }
   bool isNone() const { return type == Type::none; }
@@ -290,7 +300,8 @@ public:
     return func;
   }
   ExceptionPackage getExceptionPackage() const;
-  std::shared_ptr<Literals> getGCData() const;
+  std::shared_ptr<GCData> getGCData() const;
+  const RttSupers& getRttSupers() const;
 
   // careful!
   int32_t* geti32Ptr() {
@@ -629,6 +640,11 @@ public:
   Literal widenHighUToVecI32x4() const;
   Literal swizzleVec8x16(const Literal& other) const;
 
+  // Checks if an RTT value is a sub-rtt of another, that is, whether GC data
+  // with this object's RTT can be successfuly cast using the other RTT
+  // according to the wasm rules for that.
+  bool isSubRtt(const Literal& other) const;
+
 private:
   Literal addSatSI8(const Literal& other) const;
   Literal addSatUI8(const Literal& other) const;
@@ -686,6 +702,14 @@ 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);
 
+// A GC Struct or Array is a set of values with a run-time type saying what it
+// is.
+struct GCData {
+  Literal rtt;
+  Literals values;
+  GCData(Literal rtt, Literals values) : rtt(rtt), values(values) {}
+};
+
 } // namespace wasm
 
 namespace std {
@@ -748,7 +772,12 @@ template<> struct hash<wasm::Literal> {
     } else if (a.type.isRef()) {
       return hashRef();
     } else if (a.type.isRtt()) {
-      WASM_UNREACHABLE("TODO: rtt literals");
+      const auto& supers = a.getRttSupers();
+      wasm::rehash(digest, supers.size());
+      for (auto super : supers) {
+        wasm::rehash(digest, super.getID());
+      }
+      return digest;
     }
     WASM_UNREACHABLE("unexpected type");
   }