Intern HeapTypes and clean up types code (#3428)

Interns HeapTypes using the same patterns and utilities already used to intern
Types. This allows HeapTypes to efficiently be compared for equality and hashed,
which may be important for very large struct types in the future. This change
also has the benefit of increasing symmetry between the APIs of Type and
HeapType, which will make the developer experience more consistent. Finally,
this change will make TypeBuilder (#3418) much simpler because it will no longer
have to introduce TypeInfo variants to refer to HeapTypes indirectly.

3 files changed, 522 insertions, 447 deletions

diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index e70dc4a29..25c1eea8c 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1034,29 +1034,29 @@ void WasmBinaryWriter::writeHeapType(HeapType type) {
     return;
   }
   int ret = 0;
-  switch (type.kind) {
-    case HeapType::FuncKind:
-      ret = BinaryConsts::EncodedHeapType::func;
-      break;
-    case HeapType::ExternKind:
-      ret = BinaryConsts::EncodedHeapType::extern_;
-      break;
-    case HeapType::ExnKind:
-      ret = BinaryConsts::EncodedHeapType::exn;
-      break;
-    case HeapType::AnyKind:
-      ret = BinaryConsts::EncodedHeapType::any;
-      break;
-    case HeapType::EqKind:
-      ret = BinaryConsts::EncodedHeapType::eq;
-      break;
-    case HeapType::I31Kind:
-      ret = BinaryConsts::EncodedHeapType::i31;
-      break;
-    case HeapType::SignatureKind:
-    case HeapType::StructKind:
-    case HeapType::ArrayKind:
-      WASM_UNREACHABLE("TODO: compound GC types");
+  if (type.isBasic()) {
+    switch (type.getBasic()) {
+      case HeapType::func:
+        ret = BinaryConsts::EncodedHeapType::func;
+        break;
+      case HeapType::ext:
+        ret = BinaryConsts::EncodedHeapType::extern_;
+        break;
+      case HeapType::exn:
+        ret = BinaryConsts::EncodedHeapType::exn;
+        break;
+      case HeapType::any:
+        ret = BinaryConsts::EncodedHeapType::any;
+        break;
+      case HeapType::eq:
+        ret = BinaryConsts::EncodedHeapType::eq;
+        break;
+      case HeapType::i31:
+        ret = BinaryConsts::EncodedHeapType::i31;
+        break;
+    }
+  } else {
+    WASM_UNREACHABLE("TODO: compound GC types");
   }
   o << S64LEB(ret); // TODO: Actually s33
 }
@@ -1401,17 +1401,17 @@ HeapType WasmBinaryBuilder::getHeapType() {
   }
   switch (type) {
     case BinaryConsts::EncodedHeapType::func:
-      return HeapType::FuncKind;
+      return HeapType::func;
     case BinaryConsts::EncodedHeapType::extern_:
-      return HeapType::ExternKind;
+      return HeapType::ext;
     case BinaryConsts::EncodedHeapType::exn:
-      return HeapType::ExnKind;
+      return HeapType::exn;
     case BinaryConsts::EncodedHeapType::any:
-      return HeapType::AnyKind;
+      return HeapType::any;
     case BinaryConsts::EncodedHeapType::eq:
-      return HeapType::EqKind;
+      return HeapType::eq;
     case BinaryConsts::EncodedHeapType::i31:
-      return HeapType::I31Kind;
+      return HeapType::i31;
     default:
       throwError("invalid wasm heap type: " + std::to_string(type));
   }
@@ -5630,7 +5630,8 @@ bool WasmBinaryBuilder::maybeVisitStructGet(Expression*& out, uint32_t code) {
     default:
       return false;
   }
-  auto type = getHeapType();
+  // This type annotation is unused. Beware it needing to be used in the future!
+  getHeapType();
   curr->index = getU32LEB();
   curr->ref = popNonVoidExpression();
   curr->finalize();
@@ -5643,7 +5644,8 @@ bool WasmBinaryBuilder::maybeVisitStructSet(Expression*& out, uint32_t code) {
     return false;
   }
   auto* curr = allocator.alloc<StructSet>();
-  auto type = getHeapType();
+  // This type annotation is unused. Beware it needing to be used in the future!
+  getHeapType();
   curr->index = getU32LEB();
   curr->ref = popNonVoidExpression();
   curr->value = popNonVoidExpression();
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 37592fcd5..21104d0fe 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -879,32 +879,32 @@ HeapType SExpressionWasmBuilder::stringToHeapType(const char* str,
                                                   bool prefix) {
   if (str[0] == 'a') {
     if (str[1] == 'n' && str[2] == 'y' && (prefix || str[3] == 0)) {
-      return HeapType::AnyKind;
+      return HeapType::any;
     }
   }
   if (str[0] == 'e') {
     if (str[1] == 'q' && (prefix || str[2] == 0)) {
-      return HeapType::EqKind;
+      return HeapType::eq;
     }
     if (str[1] == 'x') {
       if (str[2] == 'n' && (prefix || str[3] == 0)) {
-        return HeapType::ExnKind;
+        return HeapType::exn;
       }
       if (str[2] == 't' && str[3] == 'e' && str[4] == 'r' && str[5] == 'n' &&
           (prefix || str[6] == 0)) {
-        return HeapType::ExternKind;
+        return HeapType::ext;
       }
     }
   }
   if (str[0] == 'i') {
     if (str[1] == '3' && str[2] == '1' && (prefix || str[3] == 0)) {
-      return HeapType::I31Kind;
+      return HeapType::i31;
     }
   }
   if (str[0] == 'f') {
     if (str[1] == 'u' && str[2] == 'n' && str[3] == 'c' &&
         (prefix || str[4] == 0)) {
-      return HeapType::FuncKind;
+      return HeapType::func;
     }
   }
   throw ParseException(std::string("invalid wasm heap type: ") + str);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 22a7c9888..48b37a864 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -27,7 +27,10 @@
 
 namespace wasm {
 
+namespace {
+
 struct TypeInfo {
+  using type_t = Type;
   enum Kind {
     TupleKind,
     RefKind,
@@ -45,44 +48,11 @@ struct TypeInfo {
 
   TypeInfo(const Tuple& tuple) : kind(TupleKind), tuple(tuple) {}
   TypeInfo(Tuple&& tuple) : kind(TupleKind), tuple(std::move(tuple)) {}
-  TypeInfo(const HeapType& heapType, bool nullable)
+  TypeInfo(HeapType heapType, bool nullable)
     : kind(RefKind), ref{heapType, nullable} {}
-  TypeInfo(HeapType&& heapType, bool nullable)
-    : kind(RefKind), ref{std::move(heapType), nullable} {}
-  TypeInfo(const Rtt& rtt) : kind(RttKind), rtt(rtt) {}
-  TypeInfo(Rtt&& rtt) : kind(RttKind), rtt(std::move(rtt)) {}
-  TypeInfo(const TypeInfo& other) {
-    kind = other.kind;
-    switch (kind) {
-      case TupleKind:
-        new (&tuple) auto(other.tuple);
-        return;
-      case RefKind:
-        new (&ref) auto(other.ref);
-        return;
-      case RttKind:
-        new (&rtt) auto(other.rtt);
-        return;
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
-  ~TypeInfo() {
-    switch (kind) {
-      case TupleKind: {
-        tuple.~Tuple();
-        return;
-      }
-      case RefKind: {
-        ref.~Ref();
-        return;
-      }
-      case RttKind: {
-        rtt.~Rtt();
-        return;
-      }
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
+  TypeInfo(Rtt rtt) : kind(RttKind), rtt(rtt) {}
+  TypeInfo(const TypeInfo& other);
+  ~TypeInfo();
 
   constexpr bool isTuple() const { return kind == TupleKind; }
   constexpr bool isRef() const { return kind == RefKind; }
@@ -90,257 +60,272 @@ struct TypeInfo {
 
   bool isNullable() const { return kind == RefKind && ref.nullable; }
 
-  bool operator==(const TypeInfo& other) const {
-    if (kind != other.kind) {
-      return false;
-    }
-    switch (kind) {
-      case TupleKind:
-        return tuple == other.tuple;
-      case RefKind:
-        return ref.heapType == other.ref.heapType &&
-               ref.nullable == other.ref.nullable;
-      case RttKind:
-        return rtt == other.rtt;
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
+  bool operator==(const TypeInfo& other) const;
   bool operator!=(const TypeInfo& other) const { return !(*this == other); }
-  TypeInfo& operator=(const TypeInfo& other) {
-    if (&other != this) {
-      this->~TypeInfo();
-      new (this) auto(other);
-    }
-    return *this;
-  }
-
-  std::string toString() const;
+  bool operator<(const TypeInfo& other) const;
 };
 
-std::ostream& operator<<(std::ostream&, TypeInfo);
+struct HeapTypeInfo {
+  using type_t = HeapType;
+  enum Kind {
+    SignatureKind,
+    StructKind,
+    ArrayKind,
+  } kind;
+  union {
+    Signature signature;
+    Struct struct_;
+    Array array;
+  };
+
+  HeapTypeInfo(Signature sig) : kind(SignatureKind), signature(sig) {}
+  HeapTypeInfo(const Struct& struct_) : kind(StructKind), struct_(struct_) {}
+  HeapTypeInfo(Struct&& struct_)
+    : kind(StructKind), struct_(std::move(struct_)) {}
+  HeapTypeInfo(Array array) : kind(ArrayKind), array(array) {}
+  HeapTypeInfo(const HeapTypeInfo& other);
+  ~HeapTypeInfo();
+
+  constexpr bool isSignature() const { return kind == SignatureKind; }
+  constexpr bool isStruct() const { return kind == StructKind; }
+  constexpr bool isArray() const { return kind == ArrayKind; }
+
+  bool operator==(const HeapTypeInfo& other) const;
+  bool operator!=(const HeapTypeInfo& other) const { return !(*this == other); }
+  bool operator<(const HeapTypeInfo& other) const;
+};
 
+} // anonymous namespace
 } // namespace wasm
 
 namespace std {
 
-template<> class hash<wasm::TypeList> {
+template<> class hash<wasm::TypeInfo> {
 public:
-  size_t operator()(const wasm::TypeList& types) const {
-    auto digest = wasm::hash(types.size());
-    for (auto type : types) {
-      wasm::rehash(digest, type);
-    }
-    return digest;
-  }
+  size_t operator()(const wasm::TypeInfo&) const;
 };
 
-template<> class hash<wasm::FieldList> {
+template<> class hash<wasm::HeapTypeInfo> {
 public:
-  size_t operator()(const wasm::FieldList& fields) const {
-    auto digest = wasm::hash(fields.size());
-    for (auto field : fields) {
-      wasm::rehash(digest, field);
-    }
-    return digest;
-  }
+  size_t operator()(const wasm::HeapTypeInfo&) const;
 };
 
-template<> class hash<wasm::TypeInfo> {
-public:
-  size_t operator()(const wasm::TypeInfo& info) const {
-    auto digest = wasm::hash(info.kind);
-    switch (info.kind) {
-      case wasm::TypeInfo::TupleKind: {
-        wasm::rehash(digest, info.tuple);
-        return digest;
-      }
-      case wasm::TypeInfo::RefKind: {
-        wasm::rehash(digest, info.ref.heapType);
-        wasm::rehash(digest, info.ref.nullable);
-        return digest;
-      }
-      case wasm::TypeInfo::RttKind: {
-        wasm::rehash(digest, info.rtt);
-        return digest;
-      }
-    }
-    WASM_UNREACHABLE("unexpected kind");
-  }
-};
+} // namespace std
 
-size_t hash<wasm::Type>::operator()(const wasm::Type& type) const {
-  return wasm::hash(type.getID());
-}
+namespace wasm {
+namespace {
 
-size_t hash<wasm::Tuple>::operator()(const wasm::Tuple& tuple) const {
-  return wasm::hash(tuple.types);
-}
+TypeInfo* getTypeInfo(Type type) { return (TypeInfo*)type.getID(); }
+HeapTypeInfo* getHeapTypeInfo(HeapType ht) { return (HeapTypeInfo*)ht.getID(); }
 
-size_t hash<wasm::Signature>::operator()(const wasm::Signature& sig) const {
-  auto digest = wasm::hash(sig.params);
-  wasm::rehash(digest, sig.results);
-  return digest;
+TypeInfo::TypeInfo(const TypeInfo& other) {
+  kind = other.kind;
+  switch (kind) {
+    case TupleKind:
+      new (&tuple) auto(other.tuple);
+      return;
+    case RefKind:
+      new (&ref) auto(other.ref);
+      return;
+    case RttKind:
+      new (&rtt) auto(other.rtt);
+      return;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::Field>::operator()(const wasm::Field& field) const {
-  auto digest = wasm::hash(field.type);
-  wasm::rehash(digest, field.packedType);
-  wasm::rehash(digest, field.mutable_);
-  // Note that the name is not hashed here - it is pure metadata for printing
-  // purposes only.
-  return digest;
+TypeInfo::~TypeInfo() {
+  switch (kind) {
+    case TupleKind:
+      tuple.~Tuple();
+      return;
+    case RefKind:
+      ref.~Ref();
+      return;
+    case RttKind:
+      rtt.~Rtt();
+      return;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::Struct>::operator()(const wasm::Struct& struct_) const {
-  return wasm::hash(struct_.fields);
+bool TypeInfo::operator==(const TypeInfo& other) const {
+  if (kind != other.kind) {
+    return false;
+  }
+  switch (kind) {
+    case TupleKind:
+      return tuple == other.tuple;
+    case RefKind:
+      return ref.heapType == other.ref.heapType &&
+             ref.nullable == other.ref.nullable;
+    case RttKind:
+      return rtt == other.rtt;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::Array>::operator()(const wasm::Array& array) const {
-  return wasm::hash(array.element);
+bool TypeInfo::operator<(const TypeInfo& other) const {
+  if (kind != other.kind) {
+    return kind < other.kind;
+  }
+  switch (kind) {
+    case TupleKind:
+      return tuple < other.tuple;
+    case RefKind:
+      if (ref.nullable != other.ref.nullable) {
+        return ref.nullable < other.ref.nullable;
+      }
+      return ref.heapType < other.ref.heapType;
+    case RttKind:
+      return rtt < other.rtt;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::HeapType>::operator()(const wasm::HeapType& heapType) const {
-  auto digest = wasm::hash(heapType.kind);
-  switch (heapType.kind) {
-    case wasm::HeapType::FuncKind:
-    case wasm::HeapType::ExternKind:
-    case wasm::HeapType::AnyKind:
-    case wasm::HeapType::EqKind:
-    case wasm::HeapType::I31Kind:
-    case wasm::HeapType::ExnKind:
-      return digest;
-    case wasm::HeapType::SignatureKind:
-      wasm::rehash(digest, heapType.signature);
-      return digest;
-    case wasm::HeapType::StructKind:
-      wasm::rehash(digest, heapType.struct_);
-      return digest;
-    case wasm::HeapType::ArrayKind:
-      wasm::rehash(digest, heapType.array);
-      return digest;
+HeapTypeInfo::HeapTypeInfo(const HeapTypeInfo& other) {
+  kind = other.kind;
+  switch (kind) {
+    case SignatureKind:
+      new (&signature) auto(other.signature);
+      return;
+    case StructKind:
+      new (&struct_) auto(other.struct_);
+      return;
+    case ArrayKind:
+      new (&array) auto(other.array);
+      return;
   }
   WASM_UNREACHABLE("unexpected kind");
 }
 
-size_t hash<wasm::Rtt>::operator()(const wasm::Rtt& rtt) const {
-  auto digest = wasm::hash(rtt.depth);
-  wasm::rehash(digest, rtt.heapType);
-  return digest;
+HeapTypeInfo::~HeapTypeInfo() {
+  switch (kind) {
+    case SignatureKind:
+      signature.~Signature();
+      return;
+    case StructKind:
+      struct_.~Struct();
+      return;
+    case ArrayKind:
+      array.~Array();
+      return;
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
-} // namespace std
-
-namespace wasm {
+bool HeapTypeInfo::operator==(const HeapTypeInfo& other) const {
+  if (kind != other.kind) {
+    return false;
+  }
+  switch (kind) {
+    case SignatureKind:
+      return signature == other.signature;
+    case StructKind:
+      return struct_ == other.struct_;
+    case ArrayKind:
+      return array == other.array;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
 
-namespace {
+bool HeapTypeInfo::operator<(const HeapTypeInfo& other) const {
+  if (kind != other.kind) {
+    return kind < other.kind;
+  }
+  switch (kind) {
+    case SignatureKind:
+      return signature < other.signature;
+    case StructKind:
+      return struct_ < other.struct_;
+    case ArrayKind:
+      return array < other.array;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
 
-struct TypeStore {
+template<typename Info> struct Store {
   std::mutex mutex;
 
-  // Track unique_ptrs for constructed types to avoid leaks
-  std::vector<std::unique_ptr<TypeInfo>> constructedTypes;
-
-  // Maps from constructed types to the canonical Type ID.
-  std::unordered_map<TypeInfo, uintptr_t> indices = {
-    // If a Type is constructed from a list of types, the list of types becomes
-    // implicitly converted to a TypeInfo before canonicalizing its id. This is
-    // also the case if a list of just one type is provided, even though such a
-    // list of types will be canonicalized to the BasicType of the single type.
-    // As such, the following entries are solely placeholders to enable the
-    // lookup of lists of just one type to the BasicType of the single type.
-    {TypeInfo(Tuple()), Type::none},
-    {TypeInfo({Type::unreachable}), Type::unreachable},
-    {TypeInfo({Type::i32}), Type::i32},
-    {TypeInfo({Type::i64}), Type::i64},
-    {TypeInfo({Type::f32}), Type::f32},
-    {TypeInfo({Type::f64}), Type::f64},
-    {TypeInfo({Type::v128}), Type::v128},
-    {TypeInfo({Type::funcref}), Type::funcref},
-    {TypeInfo(HeapType(HeapType::FuncKind), true), Type::funcref},
-    {TypeInfo({Type::externref}), Type::externref},
-    {TypeInfo(HeapType(HeapType::ExternKind), true), Type::externref},
-    {TypeInfo({Type::exnref}), Type::exnref},
-    {TypeInfo(HeapType(HeapType::ExnKind), true), Type::exnref},
-    {TypeInfo({Type::anyref}), Type::anyref},
-    {TypeInfo(HeapType(HeapType::AnyKind), true), Type::anyref},
-    {TypeInfo({Type::eqref}), Type::eqref},
-    {TypeInfo(HeapType(HeapType::EqKind), true), Type::eqref},
-    {TypeInfo({Type::i31ref}), Type::i31ref},
-    {TypeInfo(HeapType(HeapType::I31Kind), false), Type::i31ref},
-  };
+  // Track unique_ptrs for constructed types to avoid leaks.
+  std::vector<std::unique_ptr<Info>> constructedTypes;
 
-  uintptr_t canonicalize(const TypeInfo& info) {
+  // Maps from constructed types to their canonical Type IDs.
+  std::unordered_map<Info, uintptr_t> typeIDs;
+
+  typename Info::type_t canonicalize(const Info& info) {
     std::lock_guard<std::mutex> lock(mutex);
-    auto indexIt = indices.find(info);
-    if (indexIt != indices.end()) {
-      return indexIt->second;
+    auto indexIt = typeIDs.find(info);
+    if (indexIt != typeIDs.end()) {
+      return typename Info::type_t(indexIt->second);
     }
-    auto ptr = std::make_unique<TypeInfo>(info);
+    auto ptr = std::make_unique<Info>(info);
     auto id = uintptr_t(ptr.get());
     constructedTypes.push_back(std::move(ptr));
-    assert(id > Type::_last_basic_id);
-    indices[info] = id;
-    return id;
+    assert(id > Info::type_t::_last_basic_type);
+    typeIDs[info] = id;
+    return typename Info::type_t(id);
   }
+};
 
-  Type makeType(const Tuple& tuple) {
-    auto& types = tuple.types;
-#ifndef NDEBUG
-    for (Type t : types) {
-      assert(t.isSingle());
-    }
-#endif
-    if (types.size() == 0) {
-      return Type::none;
-    }
-    if (types.size() == 1) {
-      return types[0];
+struct TypeStore : Store<TypeInfo> {
+  Type canonicalize(TypeInfo info) {
+    if (info.isTuple()) {
+      if (info.tuple.types.size() == 0) {
+        return Type::none;
+      }
+      if (info.tuple.types.size() == 1) {
+        return info.tuple.types[0];
+      }
     }
-    return Type(canonicalize(TypeInfo(tuple)));
-  }
-
-  Type makeType(const HeapType& heapType, bool nullable) {
-#ifndef NDEBUG
-    switch (heapType.kind) {
-      case HeapType::FuncKind:
-      case HeapType::ExternKind:
-      case HeapType::AnyKind:
-      case HeapType::EqKind:
-      case HeapType::I31Kind:
-      case HeapType::ExnKind:
-      case HeapType::SignatureKind:
-        break;
-      case HeapType::StructKind:
-        for (Field f : heapType.struct_.fields) {
-          assert(f.type.isSingle());
+    if (info.isRef() && info.ref.heapType.isBasic()) {
+      if (info.ref.nullable) {
+        switch (info.ref.heapType.getBasic()) {
+          case HeapType::func:
+            return Type::funcref;
+          case HeapType::ext:
+            return Type::externref;
+          case HeapType::exn:
+            return Type::exnref;
+          case HeapType::any:
+            return Type::anyref;
+          case HeapType::eq:
+            return Type::eqref;
+          case HeapType::i31:
+            break;
         }
-        break;
-      case HeapType::ArrayKind:
-        assert(heapType.array.element.type.isSingle());
-        break;
+      } else {
+        if (info.ref.heapType == HeapType::i31) {
+          return Type::i31ref;
+        }
+      }
     }
-#endif
-    return Type(canonicalize(TypeInfo(heapType, nullable)));
+    return Store<TypeInfo>::canonicalize(info);
   }
-
-  Type makeType(const Rtt& rtt) { return Type(canonicalize(TypeInfo(rtt))); }
 };
 
-TypeStore globalTypeStore;
+using HeapTypeStore = Store<HeapTypeInfo>;
 
-TypeInfo* getTypeInfo(const Type& type) { return (TypeInfo*)type.getID(); }
+TypeStore globalTypeStore;
+HeapTypeStore globalHeapTypeStore;
 
 } // anonymous namespace
 
 Type::Type(std::initializer_list<Type> types) : Type(Tuple(types)) {}
 
-Type::Type(const Tuple& tuple) { *this = globalTypeStore.makeType(tuple); }
+Type::Type(const Tuple& tuple) {
+  new (this) Type(globalTypeStore.canonicalize(tuple));
+}
 
-Type::Type(const HeapType& heapType, bool nullable) {
-  *this = globalTypeStore.makeType(heapType, nullable);
+Type::Type(Tuple&& tuple) {
+  new (this) Type(globalTypeStore.canonicalize(std::move(tuple)));
 }
 
-Type::Type(const Rtt& rtt) { *this = globalTypeStore.makeType(rtt); }
+Type::Type(HeapType heapType, bool nullable) {
+  new (this) Type(globalTypeStore.canonicalize(TypeInfo(heapType, nullable)));
+}
+
+Type::Type(Rtt rtt) { new (this) Type(globalTypeStore.canonicalize(rtt)); }
 
 bool Type::isTuple() const {
   if (isBasic()) {
@@ -363,7 +348,7 @@ bool Type::isFunction() const {
     return id == funcref;
   } else {
     auto* info = getTypeInfo(*this);
-    return info->isRef() && info->ref.heapType.isSignature();
+    return info->isRef() && info->ref.heapType.isFunction();
   }
 }
 
@@ -372,7 +357,7 @@ bool Type::isException() const {
     return id == exnref;
   } else {
     auto* info = getTypeInfo(*this);
-    return info->isRef() && info->ref.heapType.isException();
+    return info->isRef() && info->ref.heapType == HeapType::exn;
   }
 }
 
@@ -397,25 +382,20 @@ bool Type::isStruct() const { return isRef() && getHeapType().isStruct(); }
 bool Type::isArray() const { return isRef() && getHeapType().isArray(); }
 
 bool Type::operator<(const Type& other) const {
-  auto comp = [](const Type& a, const Type& b) {
-    if (a.isBasic() && b.isBasic()) {
-      return a.getBasic() < b.getBasic();
-    }
-    if (a.isBasic()) {
-      return true;
-    }
-    if (b.isBasic()) {
-      return false;
-    }
-    // Both are compound.
-    if (a.isNullable() != b.isNullable()) {
-      return a.isNullable();
-    }
-    return a.getHeapType() < b.getHeapType();
-  };
-  return std::lexicographical_compare(
-    begin(), end(), other.begin(), other.end(), comp);
-}
+  if (*this == other) {
+    return false;
+  }
+  if (isBasic() && other.isBasic()) {
+    return getBasic() < other.getBasic();
+  }
+  if (isBasic()) {
+    return true;
+  }
+  if (other.isBasic()) {
+    return false;
+  }
+  return *getTypeInfo(*this) < *getTypeInfo(other);
+};
 
 unsigned Type::getByteSize() const {
   // TODO: alignment?
@@ -512,39 +492,43 @@ FeatureSet Type::getFeatures() const {
   return getSingleFeatures(*this);
 }
 
-// getHeapType() returns a const HeapType&, so we need a canonical object to
-// return for the basic types, so that we don't create a temporary copy on each
-// call.
-namespace statics {
-static HeapType funcHeapType(HeapType::FuncKind),
-  externHeapType(HeapType::ExternKind), exnHeapType(HeapType::ExnKind),
-  anyHeapType(HeapType::AnyKind), eqHeapType(HeapType::EqKind),
-  i31HeapType(HeapType::I31Kind);
-}
-
-const HeapType& Type::getHeapType() const {
-  if (isRef()) {
-    if (isCompound()) {
-      return getTypeInfo(*this)->ref.heapType;
-    }
+HeapType Type::getHeapType() const {
+  if (isBasic()) {
     switch (getBasic()) {
-      case funcref:
-        return statics::funcHeapType;
-      case externref:
-        return statics::externHeapType;
-      case exnref:
-        return statics::exnHeapType;
-      case anyref:
-        return statics::anyHeapType;
-      case eqref:
-        return statics::eqHeapType;
-      case i31ref:
-        return statics::i31HeapType;
-      default:
+      case Type::none:
+      case Type::unreachable:
+      case Type::i32:
+      case Type::i64:
+      case Type::f32:
+      case Type::f64:
+      case Type::v128:
         break;
+      case Type::funcref:
+        return HeapType::func;
+      case Type::externref:
+        return HeapType::ext;
+      case Type::exnref:
+        return HeapType::exn;
+      case Type::anyref:
+        return HeapType::any;
+      case Type::eqref:
+        return HeapType::eq;
+      case Type::i31ref:
+        return HeapType::i31;
     }
+    WASM_UNREACHABLE("Unexpected type");
+  } else {
+    auto* info = getTypeInfo(*this);
+    switch (info->kind) {
+      case TypeInfo::TupleKind:
+        break;
+      case TypeInfo::RefKind:
+        return info->ref.heapType;
+      case TypeInfo::RttKind:
+        return info->rtt.heapType;
+    }
+    WASM_UNREACHABLE("Unexpected type");
   }
-  WASM_UNREACHABLE("unexpected type");
 }
 
 Type Type::get(unsigned byteSize, bool float_) {
@@ -672,93 +656,90 @@ const Type& Type::operator[](size_t index) const {
   }
 }
 
-HeapType::HeapType(const HeapType& other) : kind(other.kind) {
-  switch (kind) {
-    case FuncKind:
-    case ExternKind:
-    case AnyKind:
-    case EqKind:
-    case I31Kind:
-    case ExnKind:
-      return;
-    case SignatureKind:
-      new (&signature) auto(other.signature);
-      return;
-    case StructKind:
-      new (&struct_) auto(other.struct_);
-      return;
-    case ArrayKind:
-      new (&array) auto(other.array);
-      return;
-  }
-  WASM_UNREACHABLE("unexpected kind");
+HeapType::HeapType(Signature signature) {
+  new (this) HeapType(globalHeapTypeStore.canonicalize(signature));
 }
 
-HeapType::~HeapType() {
-  switch (kind) {
-    case FuncKind:
-    case ExternKind:
-    case AnyKind:
-    case EqKind:
-    case I31Kind:
-    case ExnKind:
-      return;
-    case SignatureKind:
-      signature.~Signature();
-      return;
-    case StructKind:
-      struct_.~Struct();
-      return;
-    case ArrayKind:
-      array.~Array();
-      return;
+HeapType::HeapType(const Struct& struct_) {
+  new (this) HeapType(globalHeapTypeStore.canonicalize(struct_));
+}
+
+HeapType::HeapType(Struct&& struct_) {
+  new (this) HeapType(globalHeapTypeStore.canonicalize(std::move(struct_)));
+}
+
+HeapType::HeapType(Array array) {
+  new (this) HeapType(globalHeapTypeStore.canonicalize(array));
+}
+
+bool HeapType::isFunction() const {
+  if (isBasic()) {
+    return id == func;
+  } else {
+    return getHeapTypeInfo(*this)->isSignature();
   }
 }
 
-bool HeapType::operator==(const HeapType& other) const {
-  if (kind != other.kind) {
+bool HeapType::isSignature() const {
+  if (isBasic()) {
     return false;
+  } else {
+    return getHeapTypeInfo(*this)->isSignature();
   }
-  switch (kind) {
-    case FuncKind:
-    case ExternKind:
-    case AnyKind:
-    case EqKind:
-    case I31Kind:
-    case ExnKind:
-      return true;
-    case SignatureKind:
-      return signature == other.signature;
-    case StructKind:
-      return struct_ == other.struct_;
-    case ArrayKind:
-      return array == other.array;
+}
+
+bool HeapType::isStruct() const {
+  if (isBasic()) {
+    return false;
+  } else {
+    return getHeapTypeInfo(*this)->isStruct();
   }
-  WASM_UNREACHABLE("unexpected kind");
 }
 
 bool HeapType::operator<(const HeapType& other) const {
-  if (kind != other.kind) {
-    return kind < other.kind;
+  if (*this == other) {
+    return false;
+  }
+  if (isBasic() && other.isBasic()) {
+    return getBasic() < other.getBasic();
   }
-  if (isSignature()) {
-    return getSignature() < other.getSignature();
+  if (isBasic()) {
+    return true;
   }
-  if (isStruct()) {
-    return getStruct() < other.getStruct();
+  if (other.isBasic()) {
+    return false;
   }
-  if (isArray()) {
-    return getArray() < other.getArray();
+  return *getHeapTypeInfo(*this) < *getHeapTypeInfo(other);
+}
+
+bool HeapType::isArray() const {
+  if (isBasic()) {
+    return false;
+  } else {
+    return getHeapTypeInfo(*this)->isArray();
   }
-  WASM_UNREACHABLE("unimplemented type comparison");
 }
 
-HeapType& HeapType::operator=(const HeapType& other) {
-  if (&other != this) {
-    this->~HeapType();
-    new (this) auto(other);
+Signature HeapType::getSignature() const {
+  assert(isSignature());
+  return getHeapTypeInfo(*this)->signature;
+}
+
+const Struct& HeapType::getStruct() const {
+  assert(isStruct());
+  return getHeapTypeInfo(*this)->struct_;
+}
+
+Array HeapType::getArray() const {
+  assert(isArray());
+  return getHeapTypeInfo(*this)->array;
+}
+
+bool Signature::operator<(const Signature& other) const {
+  if (results != other.results) {
+    return results < other.results;
   }
-  return *this;
+  return params < other.params;
 }
 
 bool Field::operator<(const Field& other) const {
@@ -771,6 +752,13 @@ bool Field::operator<(const Field& other) const {
   return type < other.type;
 }
 
+bool Rtt::operator<(const Rtt& other) const {
+  if (depth != other.depth) {
+    return depth < other.depth;
+  }
+  return heapType < other.heapType;
+}
+
 namespace {
 
 std::ostream&
@@ -809,65 +797,41 @@ std::string HeapType::toString() const { return genericToString(*this); }
 
 std::string Rtt::toString() const { return genericToString(*this); }
 
-std::string TypeInfo::toString() const { return genericToString(*this); }
-
-bool Signature::operator<(const Signature& other) const {
-  if (results < other.results) {
-    return true;
-  } else if (other.results < results) {
-    return false;
-  } else {
-    return params < other.params;
-  }
-}
+std::ostream& operator<<(std::ostream&, TypeInfo);
+std::ostream& operator<<(std::ostream&, HeapTypeInfo);
 
 std::ostream& operator<<(std::ostream& os, Type type) {
   if (type.isBasic()) {
     switch (type.getBasic()) {
       case Type::none:
-        os << "none";
-        break;
+        return os << "none";
       case Type::unreachable:
-        os << "unreachable";
-        break;
+        return os << "unreachable";
       case Type::i32:
-        os << "i32";
-        break;
+        return os << "i32";
       case Type::i64:
-        os << "i64";
-        break;
+        return os << "i64";
       case Type::f32:
-        os << "f32";
-        break;
+        return os << "f32";
       case Type::f64:
-        os << "f64";
-        break;
+        return os << "f64";
       case Type::v128:
-        os << "v128";
-        break;
+        return os << "v128";
       case Type::funcref:
-        os << "funcref";
-        break;
+        return os << "funcref";
       case Type::externref:
-        os << "externref";
-        break;
+        return os << "externref";
       case Type::exnref:
-        os << "exnref";
-        break;
+        return os << "exnref";
       case Type::anyref:
-        os << "anyref";
-        break;
+        return os << "anyref";
       case Type::eqref:
-        os << "eqref";
-        break;
+        return os << "eqref";
       case Type::i31ref:
-        os << "i31ref";
-        break;
+        return os << "i31ref";
     }
-  } else {
-    os << *getTypeInfo(type);
   }
-  return os;
+  return os << *getTypeInfo(type);
 }
 
 std::ostream& operator<<(std::ostream& os, ParamType param) {
@@ -943,27 +907,23 @@ std::ostream& operator<<(std::ostream& os, Array array) {
 }
 
 std::ostream& operator<<(std::ostream& os, HeapType heapType) {
-  switch (heapType.kind) {
-    case wasm::HeapType::FuncKind:
-      return os << "func";
-    case wasm::HeapType::ExternKind:
-      return os << "extern";
-    case wasm::HeapType::AnyKind:
-      return os << "any";
-    case wasm::HeapType::EqKind:
-      return os << "eq";
-    case wasm::HeapType::I31Kind:
-      return os << "i31";
-    case wasm::HeapType::ExnKind:
-      return os << "exn";
-    case wasm::HeapType::SignatureKind:
-      return os << heapType.signature;
-    case wasm::HeapType::StructKind:
-      return os << heapType.struct_;
-    case wasm::HeapType::ArrayKind:
-      return os << heapType.array;
+  if (heapType.isBasic()) {
+    switch (heapType.getBasic()) {
+      case HeapType::func:
+        return os << "func";
+      case HeapType::ext:
+        return os << "extern";
+      case HeapType::exn:
+        return os << "exn";
+      case HeapType::any:
+        return os << "any";
+      case HeapType::eq:
+        return os << "eq";
+      case HeapType::i31:
+        return os << "i31";
+    }
   }
-  WASM_UNREACHABLE("unexpected kind");
+  return os << *getHeapTypeInfo(heapType);
 }
 
 std::ostream& operator<<(std::ostream& os, Rtt rtt) {
@@ -989,4 +949,117 @@ std::ostream& operator<<(std::ostream& os, TypeInfo info) {
   WASM_UNREACHABLE("unexpected kind");
 }
 
+std::ostream& operator<<(std::ostream& os, HeapTypeInfo info) {
+  switch (info.kind) {
+    case HeapTypeInfo::SignatureKind:
+      return os << info.signature;
+    case HeapTypeInfo::StructKind:
+      return os << info.struct_;
+    case HeapTypeInfo::ArrayKind:
+      return os << info.array;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
 } // namespace wasm
+
+namespace std {
+
+template<> class hash<wasm::TypeList> {
+public:
+  size_t operator()(const wasm::TypeList& types) const {
+    auto digest = wasm::hash(types.size());
+    for (auto type : types) {
+      wasm::rehash(digest, type);
+    }
+    return digest;
+  }
+};
+
+template<> class hash<wasm::FieldList> {
+public:
+  size_t operator()(const wasm::FieldList& fields) const {
+    auto digest = wasm::hash(fields.size());
+    for (auto field : fields) {
+      wasm::rehash(digest, field);
+    }
+    return digest;
+  }
+};
+
+size_t hash<wasm::TypeInfo>::operator()(const wasm::TypeInfo& info) const {
+  auto digest = wasm::hash(info.kind);
+  switch (info.kind) {
+    case wasm::TypeInfo::TupleKind:
+      wasm::rehash(digest, info.tuple);
+      return digest;
+    case wasm::TypeInfo::RefKind:
+      wasm::rehash(digest, info.ref.heapType);
+      wasm::rehash(digest, info.ref.nullable);
+      return digest;
+    case wasm::TypeInfo::RttKind:
+      wasm::rehash(digest, info.rtt);
+      return digest;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
+size_t hash<wasm::HeapTypeInfo>::
+operator()(const wasm::HeapTypeInfo& info) const {
+  auto digest = wasm::hash(info.kind);
+  switch (info.kind) {
+    case wasm::HeapTypeInfo::SignatureKind:
+      wasm::rehash(digest, info.signature);
+      return digest;
+    case wasm::HeapTypeInfo::StructKind:
+      wasm::rehash(digest, info.struct_);
+      return digest;
+    case wasm::HeapTypeInfo::ArrayKind:
+      wasm::rehash(digest, info.array);
+      return digest;
+  }
+  WASM_UNREACHABLE("unexpected kind");
+}
+
+size_t hash<wasm::Type>::operator()(const wasm::Type& type) const {
+  return wasm::hash(type.getID());
+}
+
+size_t hash<wasm::Tuple>::operator()(const wasm::Tuple& tuple) const {
+  return wasm::hash(tuple.types);
+}
+
+size_t hash<wasm::Signature>::operator()(const wasm::Signature& sig) const {
+  auto digest = wasm::hash(sig.params);
+  wasm::rehash(digest, sig.results);
+  return digest;
+}
+
+size_t hash<wasm::Field>::operator()(const wasm::Field& field) const {
+  auto digest = wasm::hash(field.type);
+  wasm::rehash(digest, field.packedType);
+  wasm::rehash(digest, field.mutable_);
+  // Note that the name is not hashed here - it is pure metadata for printing
+  // purposes only.
+  return digest;
+}
+
+size_t hash<wasm::Struct>::operator()(const wasm::Struct& struct_) const {
+  return wasm::hash(struct_.fields);
+}
+
+size_t hash<wasm::Array>::operator()(const wasm::Array& array) const {
+  return wasm::hash(array.element);
+}
+
+size_t hash<wasm::HeapType>::operator()(const wasm::HeapType& heapType) const {
+  return wasm::hash(heapType.getID());
+}
+
+size_t hash<wasm::Rtt>::operator()(const wasm::Rtt& rtt) const {
+  auto digest = wasm::hash(rtt.depth);
+  wasm::rehash(digest, rtt.heapType);
+  return digest;
+}
+
+} // namespace std