[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.

25 files changed, 274 insertions, 110 deletions

diff --git a/scripts/fuzz_opt.py b/scripts/fuzz_opt.py
index 509c25e3e..7e6753700 100755
--- a/scripts/fuzz_opt.py
+++ b/scripts/fuzz_opt.py
@@ -213,6 +213,8 @@ def pick_initial_contents():
         '--disable-exception-handling',
         # has not been fuzzed in general yet
         '--disable-memory64',
+        # has not been fuzzed in general yet
+        '--disable-gc',
         # DWARF is incompatible with multivalue atm; it's more important to
         # fuzz multivalue since we aren't actually fuzzing DWARF here
         '--strip-dwarf',
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() {
diff --git a/test/heap-types.wast b/test/heap-types.wast
index 8e7655361..7e44e4fdb 100644
--- a/test/heap-types.wast
+++ b/test/heap-types.wast
@@ -1,5 +1,6 @@
 ;; Test that we can roundtrip struct and array types
 (module
+  ;; Structs
   (type $struct.A (struct
     i32
     (field f32)
@@ -15,9 +16,18 @@
     (field $named-mut (mut f32))
   ))
 
+  ;; Arrays
   (type $vector (array (mut f64)))
   (type $matrix (array (ref $vector)))
 
+  ;; RTT
+  (type $parent (struct))
+  (type $child (struct i32))
+  (type $grandchild (struct i32 i64))
+  (global $rttparent (rtt 0 $parent) (rtt.canon $parent))
+  (global $rttchild (rtt 1 $child) (rtt.sub $child (global.get $rttparent)))
+  (global $rttgrandchild (rtt 2 $grandchild) (rtt.sub $grandchild (global.get $rttchild)))
+
   (func "foo" (param $x (ref $struct.A)) (result (ref $struct.B))
     (local $tA (ref null $struct.A))
     (local $tB (ref null $struct.B))
@@ -78,4 +88,7 @@
     )
     (unreachable)
   )
+  ;; RTT types as parameters
+  (func $rtt-param-with-depth (param $rtt (rtt 1 $parent)))
+  (func $rtt-param-without-depth (param $rtt (rtt $parent)))
 )
diff --git a/test/heap-types.wast.from-wast b/test/heap-types.wast.from-wast
index ced28e941..6f3c20589 100644
--- a/test/heap-types.wast.from-wast
+++ b/test/heap-types.wast.from-wast
@@ -1,10 +1,22 @@
 (module
  (type ${i32_f32_f64} (struct (field i32) (field f32) (field f64)))
+ (type ${} (struct ))
  (type $[mut:f64] (array (mut f64)))
+ (type ${i32} (struct (field i32)))
+ (type ${i32_i64} (struct (field i32) (field i64)))
  (type ${mut:f32} (struct (field (mut f32))))
  (type ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|} (struct (field i8) (field (mut i16)) (field (ref null ${i32_f32_f64})) (field (mut (ref null ${i32_f32_f64})))))
+ (type $rtt_1_${}_=>_none (func (param (rtt 1 ${}))))
+ (type $rtt_${}_=>_none (func (param (rtt ${}))))
  (type $[ref?|[mut:f64]|] (array (ref null $[mut:f64])))
  (type $ref?|{i32_f32_f64}|_=>_ref?|{i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}| (func (param (ref null ${i32_f32_f64})) (result (ref null ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}))))
+ (global $rttparent (rtt 0 ${}) (rtt.canon ${}))
+ (global $rttchild (rtt 1 ${i32}) (rtt.sub ${i32}
+  (global.get $rttparent)
+ ))
+ (global $rttgrandchild (rtt 2 ${i32_i64}) (rtt.sub ${i32_i64}
+  (global.get $rttchild)
+ ))
  (export "foo" (func $0))
  (func $0 (param $x (ref null ${i32_f32_f64})) (result (ref null ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}))
   (local $tA (ref null ${i32_f32_f64}))
@@ -78,4 +90,10 @@
   )
   (unreachable)
  )
+ (func $rtt-param-with-depth (param $rtt (rtt 1 ${}))
+  (nop)
+ )
+ (func $rtt-param-without-depth (param $rtt (rtt ${}))
+  (nop)
+ )
 )
diff --git a/test/heap-types.wast.fromBinary b/test/heap-types.wast.fromBinary
index 2d8e7ff38..537096fe0 100644
--- a/test/heap-types.wast.fromBinary
+++ b/test/heap-types.wast.fromBinary
@@ -1,10 +1,22 @@
 (module
  (type ${i32_f32_f64} (struct (field i32) (field f32) (field f64)))
+ (type ${} (struct ))
  (type $[mut:f64] (array (mut f64)))
+ (type ${i32} (struct (field i32)))
+ (type ${i32_i64} (struct (field i32) (field i64)))
  (type ${mut:f32} (struct (field (mut f32))))
  (type ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|} (struct (field i8) (field (mut i16)) (field (ref null ${i32_f32_f64})) (field (mut (ref null ${i32_f32_f64})))))
+ (type $rtt_1_${}_=>_none (func (param (rtt 1 ${}))))
+ (type $rtt_${}_=>_none (func (param (rtt ${}))))
  (type $[ref?|[mut:f64]|] (array (ref null $[mut:f64])))
  (type $ref?|{i32_f32_f64}|_=>_ref?|{i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}| (func (param (ref null ${i32_f32_f64})) (result (ref null ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}))))
+ (global $rttparent (rtt 0 ${}) (rtt.canon ${}))
+ (global $rttchild (rtt 1 ${i32}) (rtt.sub ${i32}
+  (global.get $rttparent)
+ ))
+ (global $rttgrandchild (rtt 2 ${i32_i64}) (rtt.sub ${i32_i64}
+  (global.get $rttchild)
+ ))
  (export "foo" (func $0))
  (func $0 (param $x (ref null ${i32_f32_f64})) (result (ref null ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}))
   (local $tA (ref null ${i32_f32_f64}))
@@ -78,5 +90,11 @@
   )
   (unreachable)
  )
+ (func $rtt-param-with-depth (param $rtt (rtt 1 ${}))
+  (nop)
+ )
+ (func $rtt-param-without-depth (param $rtt (rtt ${}))
+  (nop)
+ )
 )
 
diff --git a/test/heap-types.wast.fromBinary.noDebugInfo b/test/heap-types.wast.fromBinary.noDebugInfo
index 753402c05..19e5f701d 100644
--- a/test/heap-types.wast.fromBinary.noDebugInfo
+++ b/test/heap-types.wast.fromBinary.noDebugInfo
@@ -1,10 +1,22 @@
 (module
  (type ${i32_f32_f64} (struct (field i32) (field f32) (field f64)))
+ (type ${} (struct ))
  (type $[mut:f64] (array (mut f64)))
+ (type ${i32} (struct (field i32)))
+ (type ${i32_i64} (struct (field i32) (field i64)))
  (type ${mut:f32} (struct (field (mut f32))))
  (type ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|} (struct (field i8) (field (mut i16)) (field (ref null ${i32_f32_f64})) (field (mut (ref null ${i32_f32_f64})))))
+ (type $rtt_1_${}_=>_none (func (param (rtt 1 ${}))))
+ (type $rtt_${}_=>_none (func (param (rtt ${}))))
  (type $[ref?|[mut:f64]|] (array (ref null $[mut:f64])))
  (type $ref?|{i32_f32_f64}|_=>_ref?|{i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}| (func (param (ref null ${i32_f32_f64})) (result (ref null ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}))))
+ (global $global$0 (rtt 0 ${}) (rtt.canon ${}))
+ (global $global$1 (rtt 1 ${i32}) (rtt.sub ${i32}
+  (global.get $global$0)
+ ))
+ (global $global$2 (rtt 2 ${i32_i64}) (rtt.sub ${i32_i64}
+  (global.get $global$1)
+ ))
  (export "foo" (func $0))
  (func $0 (param $0 (ref null ${i32_f32_f64})) (result (ref null ${i32_mut:i32_ref?|{i32_f32_f64}|_mut:ref?|{i32_f32_f64}|}))
   (local $1 (ref null ${i32_f32_f64}))
@@ -78,5 +90,11 @@
   )
   (unreachable)
  )
+ (func $1 (param $0 (rtt 1 ${}))
+  (nop)
+ )
+ (func $2 (param $0 (rtt ${}))
+  (nop)
+ )
 )
 
diff --git a/test/try-body-multiple-insts.wasm b/test/try-body-multiple-insts.wasm
deleted file mode 100644
index dd67f3e52..000000000
--- a/test/try-body-multiple-insts.wasm
+++ /dev/null
diff --git a/test/try-body-multiple-insts.wasm.fromBinary b/test/try-body-multiple-insts.wasm.fromBinary
deleted file mode 100644
index 179bb42ab..000000000
--- a/test/try-body-multiple-insts.wasm.fromBinary
+++ /dev/null
@@ -1,26 +0,0 @@
-(module
- (type $none_=>_none (func))
- (func $0
-  (nop)
- )
- (func $1
-  (nop)
- )
- (func $2
-  (local $0 exnref)
-  (try
-   (do
-    (call $0)
-    (call $1)
-   )
-   (catch
-    (drop
-     (pop exnref)
-    )
-    (call $0)
-    (call $1)
-   )
-  )
- )
-)
-