[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, 79 insertions, 7 deletions

diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index 9bdf886b3..f526cebf3 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -37,6 +37,11 @@ Literal::Literal(Type type) : type(type) {
     assert(type != Type::unreachable && (!type.isRef() || type.isNullable()));
     if (type.isException()) {
       new (&exn) std::unique_ptr<ExceptionPackage>();
+    } else if (isGCData()) {
+      new (&gcData) std::shared_ptr<GCData>();
+    } else if (type.isRtt()) {
+      // Allocate a new RttSupers (with no data).
+      new (&rttSupers) auto(std::make_unique<RttSupers>());
     } else {
       memset(&v128, 0, 16);
     }
@@ -47,6 +52,19 @@ Literal::Literal(const uint8_t init[16]) : type(Type::v128) {
   memcpy(&v128, init, 16);
 }
 
+Literal::Literal(std::shared_ptr<GCData> gcData, Type type)
+  : gcData(gcData), type(type) {
+  // Null data is only allowed if nullable.
+  assert(gcData || type.isNullable());
+  // The type must be a proper type for GC data.
+  assert(isGCData());
+}
+
+Literal::Literal(std::unique_ptr<RttSupers>&& rttSupers, Type type)
+  : rttSupers(std::move(rttSupers)), type(type) {
+  assert(type.isRtt());
+}
+
 Literal::Literal(const Literal& other) : type(other.type) {
   if (type.isException()) {
     // Avoid calling the destructor on an uninitialized value
@@ -56,13 +74,12 @@ Literal::Literal(const Literal& other) : type(other.type) {
       new (&exn) std::unique_ptr<ExceptionPackage>();
     }
   } else if (other.isGCData()) {
-    // Avoid calling the destructor on an uninitialized value
-    new (&gcData) std::shared_ptr<Literals>(other.gcData);
+    new (&gcData) std::shared_ptr<GCData>(other.gcData);
   } else if (type.isFunction()) {
     func = other.func;
   } else if (type.isRtt()) {
-    // Nothing to do: Rtts help JITs optimize, but are not used in the
-    // interpreter yet, and they are opaque to the wasm itself.
+    // Allocate a new RttSupers with a copy of the other's data.
+    new (&rttSupers) auto(std::make_unique<RttSupers>(*other.rttSupers));
   } else {
     TODO_SINGLE_COMPOUND(type);
     switch (type.getBasic()) {
@@ -92,6 +109,21 @@ Literal::Literal(const Literal& other) : type(other.type) {
   }
 }
 
+Literal::~Literal() {
+  if (type.isException()) {
+    exn.~unique_ptr();
+  } else if (isGCData()) {
+    gcData.~shared_ptr();
+  } else if (type.isRtt()) {
+    rttSupers.~unique_ptr();
+  } else if (type.isFunction()) {
+    // Nothing special to do.
+  } else {
+    // Basic types need no special handling.
+    assert(type.isBasic());
+  }
+}
+
 Literal& Literal::operator=(const Literal& other) {
   if (this != &other) {
     this->~Literal();
@@ -168,6 +200,8 @@ Literal Literal::makeZero(Type type) {
     } else {
       return makeNull(type);
     }
+  } else if (type.isRtt()) {
+    return Literal(type);
   } else {
     return makeFromInt32(0, type);
   }
@@ -195,11 +229,16 @@ ExceptionPackage Literal::getExceptionPackage() const {
   return *exn;
 }
 
-std::shared_ptr<Literals> Literal::getGCData() const {
+std::shared_ptr<GCData> Literal::getGCData() const {
   assert(isGCData());
   return gcData;
 }
 
+const RttSupers& Literal::getRttSupers() const {
+  assert(type.isRtt());
+  return *rttSupers;
+}
+
 Literal Literal::castToF32() {
   assert(type == Type::i32);
   Literal ret(Type::f32);
@@ -333,7 +372,7 @@ bool Literal::operator==(const Literal& other) const {
   } else if (type.isRef()) {
     return compareRef();
   } else if (type.isRtt()) {
-    WASM_UNREACHABLE("TODO: rtt literals");
+    return *rttSupers == *other.rttSupers;
   }
   WASM_UNREACHABLE("unexpected type");
 }
@@ -442,10 +481,16 @@ std::ostream& operator<<(std::ostream& o, Literal literal) {
   } else if (literal.isGCData()) {
     auto data = literal.getGCData();
     if (data) {
-      o << "[ref " << *data << ']';
+      o << "[ref " << data->rtt << ' ' << data->values << ']';
     } else {
       o << "[ref null " << literal.type << ']';
     }
+  } else if (literal.type.isRtt()) {
+    o << "[rtt ";
+    for (Type super : literal.getRttSupers()) {
+      o << super << " :> ";
+    }
+    o << literal.type << ']';
   } else {
     TODO_SINGLE_COMPOUND(literal.type);
     switch (literal.type.getBasic()) {
@@ -2362,4 +2407,31 @@ Literal Literal::swizzleVec8x16(const Literal& other) const {
   return Literal(result);
 }
 
+bool Literal::isSubRtt(const Literal& other) const {
+  assert(type.isRtt() && other.type.isRtt());
+  // For this literal to be a sub-rtt of the other rtt, the supers must be a
+  // superset. That is, if other is a->b->c then we should be a->b->c as well
+  // with possibly ->d->.. added. The rttSupers array represents those chains,
+  // but only the supers, which means the last item in the chain is simply the
+  // type of the literal.
+  const auto& supers = getRttSupers();
+  const auto& otherSupers = other.getRttSupers();
+  if (otherSupers.size() > supers.size()) {
+    return false;
+  }
+  for (Index i = 0; i < otherSupers.size(); i++) {
+    if (supers[i] != otherSupers[i]) {
+      return false;
+    }
+  }
+  // If we have more supers than other, compare that extra super. Otherwise,
+  // we have the same amount of supers, and must be completely identical to
+  // other.
+  if (otherSupers.size() < supers.size()) {
+    return other.type == supers[otherSupers.size()];
+  } else {
+    return other.type == type;
+  }
+}
+
 } // namespace wasm