[GC] Add basic RTT support (#3432)

This adds rtt.canon and rtt.sub together with RTT type support
that is necessary for them. Together this lets us test roundtripping the
instructions and types.

Also fixes a missing traversal over globals in collectHeapTypes,
which the example from the GC docs requires, as the RTTs are in
globals there.

This does not yet add full interpreter support and other things. It
disables initial contents on GC in the fuzzer, to avoid the fuzzer
breaking.

Renames the binary ID for exnref, which is being removed from
the spec, and which overlaps with the binary ID for rtt.

18 files changed, 205 insertions, 84 deletions

diff --git a/src/ir/cost.h b/src/ir/cost.h
index 268ac41b3..a006146d3 100644
--- a/src/ir/cost.h
+++ b/src/ir/cost.h
@@ -563,8 +563,14 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, Index> {
   Index visitRefTest(RefTest* curr) { WASM_UNREACHABLE("TODO: GC"); }
   Index visitRefCast(RefCast* curr) { WASM_UNREACHABLE("TODO: GC"); }
   Index visitBrOnCast(BrOnCast* curr) { WASM_UNREACHABLE("TODO: GC"); }
-  Index visitRttCanon(RttCanon* curr) { WASM_UNREACHABLE("TODO: GC"); }
-  Index visitRttSub(RttSub* curr) { WASM_UNREACHABLE("TODO: GC"); }
+  Index visitRttCanon(RttCanon* curr) {
+    // TODO: investigate actual RTT costs in VMs
+    return 1;
+  }
+  Index visitRttSub(RttSub* curr) {
+    // TODO: investigate actual RTT costs in VMs
+    return 2 + visit(curr->parent);
+  }
   Index visitStructNew(StructNew* curr) { WASM_UNREACHABLE("TODO: GC"); }
   Index visitStructGet(StructGet* curr) {
     return 1 + nullCheckCost(curr->ref) + visit(curr->ref);
diff --git a/src/ir/effects.h b/src/ir/effects.h
index d5b917d8b..39d0d265a 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -554,10 +554,8 @@ private:
     void visitBrOnCast(BrOnCast* curr) {
       WASM_UNREACHABLE("TODO (gc): br_on_cast");
     }
-    void visitRttCanon(RttCanon* curr) {
-      WASM_UNREACHABLE("TODO (gc): rtt.canon");
-    }
-    void visitRttSub(RttSub* curr) { WASM_UNREACHABLE("TODO (gc): rtt.sub"); }
+    void visitRttCanon(RttCanon* curr) {}
+    void visitRttSub(RttSub* curr) {}
     void visitStructNew(StructNew* curr) {
       WASM_UNREACHABLE("TODO (gc): struct.new");
     }
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 2e93aa677..0095fb407 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -404,7 +404,9 @@ inline void collectHeapTypes(Module& wasm,
                              std::vector<HeapType>& types,
                              std::unordered_map<HeapType, Index>& typeIndices) {
   struct Counts : public std::unordered_map<HeapType, size_t> {
-    bool isRelevant(Type type) { return !type.isBasic() && type.isRef(); }
+    bool isRelevant(Type type) {
+      return !type.isBasic() && (type.isRef() || type.isRtt());
+    }
     void note(HeapType type) { (*this)[type]++; }
     void maybeNote(Type type) {
       if (isRelevant(type)) {
@@ -429,6 +431,8 @@ inline void collectHeapTypes(Module& wasm,
           counts.note(call->sig);
         } else if (curr->is<RefNull>()) {
           counts.maybeNote(curr->type);
+        } else if (curr->is<RttCanon>() || curr->is<RttSub>()) {
+          counts.note(curr->type.getRtt().heapType);
         } else if (auto* get = curr->dynCast<StructGet>()) {
           counts.maybeNote(get->ref->type);
         } else if (auto* set = curr->dynCast<StructSet>()) {
@@ -463,6 +467,9 @@ inline void collectHeapTypes(Module& wasm,
   for (auto& curr : wasm.events) {
     counts.note(curr->sig);
   }
+  for (auto& curr : wasm.globals) {
+    counts.maybeNote(curr->type);
+  }
   for (auto& pair : analysis.map) {
     Counts& functionCounts = pair.second;
     for (auto& innerPair : functionCounts) {
diff --git a/src/ir/properties.h b/src/ir/properties.h
index b86032ba0..485a37e22 100644
--- a/src/ir/properties.h
+++ b/src/ir/properties.h
@@ -82,7 +82,8 @@ inline bool isNamedControlFlow(Expression* curr) {
 
 inline bool isSingleConstantExpression(const Expression* curr) {
   return curr->is<Const>() || curr->is<RefNull>() || curr->is<RefFunc>() ||
-         (curr->is<I31New>() && curr->cast<I31New>()->value->is<Const>());
+         (curr->is<I31New>() && curr->cast<I31New>()->value->is<Const>()) ||
+         curr->is<RttCanon>() || curr->is<RttSub>();
 }
 
 inline bool isConstantExpression(const Expression* curr) {
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index d7691fe07..2edd069d9 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -57,29 +57,6 @@ static std::ostream& printLocal(Index index, Function* func, std::ostream& o) {
   return printName(name, o);
 }
 
-// Unlike the default format, tuple types in s-expressions should not have
-// commas.
-struct SExprType {
-  Type type;
-  SExprType(Type type) : type(type){};
-};
-
-static std::ostream& operator<<(std::ostream& o, const SExprType& localType) {
-  Type type = localType.type;
-  if (type.isTuple()) {
-    o << '(';
-    auto sep = "";
-    for (const auto& t : type) {
-      o << sep << t;
-      sep = " ";
-    }
-    o << ')';
-  } else {
-    o << type;
-  }
-  return o;
-}
-
 // Wrapper for printing a type when we try to print the type name as much as
 // possible. For example, for a signature we will print the signature's name,
 // not its contents.
@@ -88,11 +65,6 @@ struct TypeName {
   TypeName(Type type) : type(type) {}
 };
 
-struct ResultTypeName {
-  Type type;
-  ResultTypeName(Type type) : type(type) {}
-};
-
 static void
 printHeapTypeName(std::ostream& os, HeapType type, bool first = true);
 
@@ -101,6 +73,15 @@ static void printTypeName(std::ostream& os, Type type) {
     os << type;
     return;
   }
+  if (type.isRtt()) {
+    auto rtt = type.getRtt();
+    os << "rtt_";
+    if (rtt.hasDepth()) {
+      os << rtt.depth << '_';
+    }
+    printHeapTypeName(os, rtt.heapType);
+    return;
+  }
   if (type.isTuple()) {
     auto sep = "";
     for (auto t : type) {
@@ -108,7 +89,9 @@ static void printTypeName(std::ostream& os, Type type) {
       sep = "_";
       printTypeName(os, t);
     }
-  } else if (type.isRef()) {
+    return;
+  }
+  if (type.isRef()) {
     os << "ref";
     if (type.isNullable()) {
       os << "?";
@@ -116,9 +99,9 @@ static void printTypeName(std::ostream& os, Type type) {
     os << "|";
     printHeapTypeName(os, type.getHeapType(), false);
     os << "|";
-  } else {
-    WASM_UNREACHABLE("unsupported print type");
+    return;
   }
+  WASM_UNREACHABLE("unsupported print type");
 }
 
 static void printHeapTypeName(std::ostream& os, HeapType type, bool first) {
@@ -164,6 +147,37 @@ static void printHeapTypeName(std::ostream& os, HeapType type, bool first) {
   }
 }
 
+// Unlike the default format, tuple types in s-expressions should not have
+// commas.
+struct SExprType {
+  Type type;
+  SExprType(Type type) : type(type){};
+};
+
+static std::ostream& operator<<(std::ostream& o, const SExprType& localType) {
+  Type type = localType.type;
+  if (type.isTuple()) {
+    o << '(';
+    auto sep = "";
+    for (const auto& t : type) {
+      o << sep << t;
+      sep = " ";
+    }
+    o << ')';
+  } else if (type.isRtt()) {
+    auto rtt = type.getRtt();
+    o << "(rtt ";
+    if (rtt.hasDepth()) {
+      o << rtt.depth << ' ';
+    }
+    printHeapTypeName(o, rtt.heapType);
+    o << ')';
+  } else {
+    printTypeName(o, localType.type);
+  }
+  return o;
+}
+
 std::ostream& operator<<(std::ostream& os, TypeName typeName) {
   auto type = typeName.type;
   if (type.isRef() && !type.isBasic()) {
@@ -178,6 +192,13 @@ std::ostream& operator<<(std::ostream& os, TypeName typeName) {
   return os << SExprType(typeName.type);
 }
 
+// TODO: try to simplify or even remove this, as we may be able to do the same
+//       things with SExprType
+struct ResultTypeName {
+  Type type;
+  ResultTypeName(Type type) : type(type) {}
+};
+
 std::ostream& operator<<(std::ostream& os, ResultTypeName typeName) {
   auto type = typeName.type;
   os << "(result ";
@@ -1673,12 +1694,12 @@ struct PrintExpressionContents
     WASM_UNREACHABLE("TODO (gc): br_on_cast");
   }
   void visitRttCanon(RttCanon* curr) {
-    printMedium(o, "rtt.canon");
-    WASM_UNREACHABLE("TODO (gc): rtt.canon");
+    printMedium(o, "rtt.canon ");
+    printHeapTypeName(o, curr->type.getRtt().heapType);
   }
   void visitRttSub(RttSub* curr) {
-    printMedium(o, "rtt.sub");
-    WASM_UNREACHABLE("TODO (gc): rtt.sub");
+    printMedium(o, "rtt.sub ");
+    printHeapTypeName(o, curr->type.getRtt().heapType);
   }
   void visitStructNew(StructNew* curr) {
     WASM_UNREACHABLE("TODO (gc): struct.new");
@@ -2358,12 +2379,14 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
   void visitRttCanon(RttCanon* curr) {
     o << '(';
     PrintExpressionContents(currFunction, o).visit(curr);
-    WASM_UNREACHABLE("TODO (gc): rtt.canon");
+    o << ')';
   }
   void visitRttSub(RttSub* curr) {
     o << '(';
     PrintExpressionContents(currFunction, o).visit(curr);
-    WASM_UNREACHABLE("TODO (gc): rtt.sub");
+    incIndent();
+    printFullLine(curr->parent);
+    decIndent();
   }
   void visitStructNew(StructNew* curr) {
     o << '(';
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 4c4789b69..8b5988602 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -354,8 +354,12 @@ enum EncodedType {
   nonnullable = -0x15, // 0x6b
   // integer reference type
   i31ref = -0x16, // 0x6a
-  // exception reference type
-  exnref = -0x18, // 0x68
+  // run-time type info type, with depth index n
+  rtt_n = -0x17, // 0x69
+  // run-time type info type, without depth index n
+  rtt = -0x18, // 0x68
+  // exception reference type TODO remove; the code for now is incorrect
+  exnref = -0x19, // 0x67
   // func_type form
   Func = -0x20,   // 0x60
   Struct = -0x21, // 0x5f
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index 5bc238878..5cca8d959 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -709,15 +709,21 @@ public:
     ret->finalize();
     return ret;
   }
-  RttCanon* makeRttCanon() {
+  RttCanon* makeRttCanon(HeapType heapType) {
     auto* ret = wasm.allocator.alloc<RttCanon>();
-    WASM_UNREACHABLE("TODO (gc): rtt.canon");
+    ret->type = Type(Rtt(0, heapType));
     ret->finalize();
     return ret;
   }
-  RttSub* makeRttSub() {
+  RttSub* makeRttSub(HeapType heapType, Expression* parent) {
     auto* ret = wasm.allocator.alloc<RttSub>();
-    WASM_UNREACHABLE("TODO (gc): rtt.sub");
+    ret->parent = parent;
+    auto parentRtt = parent->type.getRtt();
+    if (parentRtt.hasDepth()) {
+      ret->type = Type(Rtt(parentRtt.depth + 1, heapType));
+    } else {
+      ret->type = Type(Rtt(heapType));
+    }
     ret->finalize();
     return ret;
   }
diff --git a/src/wasm-delegations-fields.h b/src/wasm-delegations-fields.h
index 44ac20b89..4e23a6530 100644
--- a/src/wasm-delegations-fields.h
+++ b/src/wasm-delegations-fields.h
@@ -577,13 +577,12 @@ switch (DELEGATE_ID) {
   }
   case Expression::Id::RttCanonId: {
     DELEGATE_START(RttCanon);
-    WASM_UNREACHABLE("TODO (gc): rtt.canon");
     DELEGATE_END(RttCanon);
     break;
   }
   case Expression::Id::RttSubId: {
     DELEGATE_START(RttSub);
-    WASM_UNREACHABLE("TODO (gc): rtt.sub");
+    DELEGATE_FIELD_CHILD(RttSub, parent);
     DELEGATE_END(RttSub);
     break;
   }
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index a22bb6e54..65a4417c8 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1388,13 +1388,13 @@ public:
     NOTE_ENTER("BrOnCast");
     WASM_UNREACHABLE("TODO (gc): br_on_cast");
   }
-  Flow visitRttCanon(RttCanon* curr) {
-    NOTE_ENTER("RttCanon");
-    WASM_UNREACHABLE("TODO (gc): rtt.canon");
-  }
+  Flow visitRttCanon(RttCanon* curr) { return Literal(curr->type); }
   Flow visitRttSub(RttSub* curr) {
-    NOTE_ENTER("RttSub");
-    WASM_UNREACHABLE("TODO (gc): rtt.sub");
+    Flow parent = this->visit(curr->parent);
+    if (parent.breaking()) {
+      return parent;
+    }
+    return Literal(curr->type);
   }
   Flow visitStructNew(StructNew* curr) {
     NOTE_ENTER("StructNew");
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 0e159b3a9..f600f2e79 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -177,6 +177,8 @@ public:
   // Gets the heap type corresponding to this type
   HeapType getHeapType() const;
 
+  const struct Rtt& getRtt() const;
+
   // Returns a number type based on its size in bytes and whether it is a float
   // type.
   static Type get(unsigned byteSize, bool float_);
@@ -430,14 +432,20 @@ struct Array {
 };
 
 struct Rtt {
+  enum {
+    // An Rtt can have no depth specified
+    NoDepth = -1
+  };
   uint32_t depth;
   HeapType heapType;
+  Rtt(HeapType heapType) : depth(NoDepth), heapType(heapType) {}
   Rtt(uint32_t depth, HeapType heapType) : depth(depth), heapType(heapType) {}
   bool operator==(const Rtt& other) const {
     return depth == other.depth && heapType == other.heapType;
   }
   bool operator!=(const Rtt& other) const { return !(*this == other); }
   bool operator<(const Rtt& other) const;
+  bool hasDepth() { return depth != uint32_t(NoDepth); }
   std::string toString() const;
 };
 
diff --git a/src/wasm.h b/src/wasm.h
index c1b5b4bdf..c1936cb46 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -1331,14 +1331,16 @@ class RttCanon : public SpecificExpression<Expression::RttCanonId> {
 public:
   RttCanon(MixedArena& allocator) {}
 
-  void finalize() { WASM_UNREACHABLE("TODO (gc): rtt.canon"); }
+  void finalize();
 };
 
 class RttSub : public SpecificExpression<Expression::RttSubId> {
 public:
   RttSub(MixedArena& allocator) {}
 
-  void finalize() { WASM_UNREACHABLE("TODO (gc): rtt.sub"); }
+  Expression* parent;
+
+  void finalize();
 };
 
 class StructNew : public SpecificExpression<Expression::StructNewId> {
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index b7cf5084e..c19efa225 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -60,6 +60,9 @@ Literal::Literal(const Literal& other) : type(other.type) {
     new (&gcData) std::shared_ptr<Literals>(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.
   } else {
     TODO_SINGLE_COMPOUND(type);
     switch (type.getBasic()) {
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 25c1eea8c..20edab3cf 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -982,6 +982,17 @@ void WasmBinaryWriter::writeType(Type type) {
     writeHeapType(type.getHeapType());
     return;
   }
+  if (type.isRtt()) {
+    auto rtt = type.getRtt();
+    if (rtt.hasDepth()) {
+      o << S32LEB(BinaryConsts::EncodedType::rtt_n);
+      o << U32LEB(rtt.depth);
+    } else {
+      o << S32LEB(BinaryConsts::EncodedType::rtt);
+    }
+    writeHeapType(rtt.heapType);
+    return;
+  }
   int ret = 0;
   TODO_SINGLE_COMPOUND(type);
   switch (type.getBasic()) {
@@ -1382,6 +1393,14 @@ Type WasmBinaryBuilder::getType(int initial) {
       return Type(getHeapType(), /* nullable = */ true);
     case BinaryConsts::EncodedType::i31ref:
       return Type::i31ref;
+    case BinaryConsts::EncodedType::rtt_n: {
+      auto depth = getU32LEB();
+      auto heapType = getHeapType();
+      return Type(Rtt(depth, heapType));
+    }
+    case BinaryConsts::EncodedType::rtt: {
+      return Type(Rtt(getHeapType()));
+    }
     default:
       throwError("invalid wasm type: " + std::to_string(initial));
   }
@@ -5575,10 +5594,8 @@ bool WasmBinaryBuilder::maybeVisitRttCanon(Expression*& out, uint32_t code) {
   if (code != BinaryConsts::RttCanon) {
     return false;
   }
-  auto* curr = allocator.alloc<RttCanon>();
-  WASM_UNREACHABLE("TODO (gc): rtt.canon");
-  curr->finalize();
-  out = curr;
+  auto heapType = getHeapType();
+  out = Builder(wasm).makeRttCanon(heapType);
   return true;
 }
 
@@ -5586,10 +5603,11 @@ bool WasmBinaryBuilder::maybeVisitRttSub(Expression*& out, uint32_t code) {
   if (code != BinaryConsts::RttSub) {
     return false;
   }
-  auto* curr = allocator.alloc<RttSub>();
-  WASM_UNREACHABLE("TODO (gc): rtt.sub");
-  curr->finalize();
-  out = curr;
+  // FIXME: the binary format may also have an extra heap type and index that
+  //        are not needed
+  auto heapType = getHeapType();
+  auto* parent = popNonVoidExpression();
+  out = Builder(wasm).makeRttSub(heapType, parent);
   return true;
 }
 
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 21104d0fe..63b6e34bd 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -50,7 +50,7 @@ int unhex(char c) {
 namespace wasm {
 
 static Name STRUCT("struct"), FIELD("field"), ARRAY("array"), I8("i8"),
-  I16("i16");
+  I16("i16"), RTT("rtt");
 
 static Address getAddress(const Element* s) { return atoll(s->c_str()); }
 
@@ -940,6 +940,18 @@ Type SExpressionWasmBuilder::elementToType(Element& s) {
     }
     return Type(parseHeapType(*s[i]), nullable);
   }
+  if (elementStartsWith(s, RTT)) {
+    // It's an RTT, something like (rtt N $typename) or just (rtt $typename)
+    // if there is no depth.
+    if (s[1]->dollared()) {
+      auto heapType = parseHeapType(*s[1]);
+      return Type(Rtt(heapType));
+    } else {
+      auto depth = atoi(s[1]->str().c_str());
+      auto heapType = parseHeapType(*s[2]);
+      return Type(Rtt(depth, heapType));
+    }
+  }
   // It's a tuple.
   std::vector<Type> types;
   for (size_t i = 0; i < s.size(); ++i) {
@@ -2102,17 +2114,13 @@ Expression* SExpressionWasmBuilder::makeBrOnCast(Element& s) {
 }
 
 Expression* SExpressionWasmBuilder::makeRttCanon(Element& s) {
-  auto ret = allocator.alloc<RttCanon>();
-  WASM_UNREACHABLE("TODO (gc): rtt.canon");
-  ret->finalize();
-  return ret;
+  return Builder(wasm).makeRttCanon(parseHeapType(*s[1]));
 }
 
 Expression* SExpressionWasmBuilder::makeRttSub(Element& s) {
-  auto ret = allocator.alloc<RttSub>();
-  WASM_UNREACHABLE("TODO (gc): rtt.sub");
-  ret->finalize();
-  return ret;
+  auto heapType = parseHeapType(*s[1]);
+  auto parent = parseExpression(*s[2]);
+  return Builder(wasm).makeRttSub(heapType, parent);
 }
 
 Expression* SExpressionWasmBuilder::makeStructNew(Element& s, bool default_) {
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index 9d0d04b6d..cca351b6f 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -1897,12 +1897,14 @@ void BinaryInstWriter::visitBrOnCast(BrOnCast* curr) {
 
 void BinaryInstWriter::visitRttCanon(RttCanon* curr) {
   o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::RttCanon);
-  WASM_UNREACHABLE("TODO (gc): rtt.canon");
+  parent.writeHeapType(curr->type.getRtt().heapType);
 }
 
 void BinaryInstWriter::visitRttSub(RttSub* curr) {
   o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::RttSub);
-  WASM_UNREACHABLE("TODO (gc): rtt.sub");
+  // FIXME: the binary format may also have an extra heap type and index that
+  //        are not needed
+  parent.writeHeapType(curr->type.getRtt().heapType);
 }
 
 void BinaryInstWriter::visitStructNew(StructNew* curr) {
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 48b37a864..013dadcf4 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -463,6 +463,8 @@ FeatureSet Type::getFeatures() const {
       if (heapType.isStruct() || heapType.isArray()) {
         return FeatureSet::ReferenceTypes | FeatureSet::GC;
       }
+    } else if (t.isRtt()) {
+      return FeatureSet::ReferenceTypes | FeatureSet::GC;
     }
     TODO_SINGLE_COMPOUND(t);
     switch (t.getBasic()) {
@@ -529,6 +531,15 @@ HeapType Type::getHeapType() const {
     }
     WASM_UNREACHABLE("Unexpected type");
   }
+  if (isRtt()) {
+    return getRtt().heapType;
+  }
+  WASM_UNREACHABLE("unexpected type");
+}
+
+const Rtt& Type::getRtt() const {
+  assert(isRtt());
+  return getTypeInfo(*this)->rtt;
 }
 
 Type Type::get(unsigned byteSize, bool float_) {
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index b2e208d53..c6e22899c 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -2211,13 +2211,27 @@ void FunctionValidator::visitBrOnCast(BrOnCast* curr) {
 void FunctionValidator::visitRttCanon(RttCanon* curr) {
   shouldBeTrue(
     getModule()->features.hasGC(), curr, "rtt.canon requires gc to be enabled");
-  WASM_UNREACHABLE("TODO (gc): rtt.canon");
+  shouldBeTrue(curr->type.isRtt(), curr, "rtt.canon must have RTT type");
+  auto rtt = curr->type.getRtt();
+  shouldBeEqual(rtt.depth, Index(0), curr, "rtt.canon has a depth of 0");
 }
 
 void FunctionValidator::visitRttSub(RttSub* curr) {
   shouldBeTrue(
     getModule()->features.hasGC(), curr, "rtt.sub requires gc to be enabled");
-  WASM_UNREACHABLE("TODO (gc): rtt.sub");
+  shouldBeTrue(curr->type.isRtt(), curr, "rtt.sub must have RTT type");
+  if (curr->parent->type != Type::unreachable) {
+    shouldBeTrue(
+      curr->parent->type.isRtt(), curr, "rtt.sub parent must have RTT type");
+    auto parentRtt = curr->parent->type.getRtt();
+    auto rtt = curr->type.getRtt();
+    if (rtt.hasDepth() && parentRtt.hasDepth()) {
+      shouldBeEqual(rtt.depth,
+                    parentRtt.depth + 1,
+                    curr,
+                    "rtt.canon has a depth of 1 over the parent");
+    }
+  }
 }
 
 void FunctionValidator::visitStructNew(StructNew* curr) {
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index c15042721..1e8bf93ae 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -1080,8 +1080,19 @@ void CallRef::finalize(Type type_) {
 // TODO (gc): ref.test
 // TODO (gc): ref.cast
 // TODO (gc): br_on_cast
-// TODO (gc): rtt.canon
-// TODO (gc): rtt.sub
+
+void RttCanon::finalize() {
+  // Nothing to do - the type must have been set already during construction.
+}
+
+void RttSub::finalize() {
+  if (parent->type == Type::unreachable) {
+    type = Type::unreachable;
+  }
+  // Else nothing to do - the type must have been set already during
+  // construction.
+}
+
 // TODO (gc): struct.new
 
 void StructGet::finalize() {