[NFC] Encode reference types with bit packing (#7142)

Value types were previously represented internally as either enum values
for "basic," i.e. non-reference, non-tuple types or pointers to
`TypeInfo` structs encoding either references or tuples. Update the
representation of reference types to use one bit to encode nullability
and the rest of the bits to encode the referenced heap type. This allows
canonical reference types to be created with a single logical or rather
than by taking a lock on a global type store and doing a hash map lookup
to canonicalize.

This change is a massive performance improvement and dramatically
improves how performance scales with threads because the removed lock
was highly contended. Even with a single core, the performance of an O3
optimization pipeline on a WasmGC module improves by 6%. With 8 cores,
the improvement increases to 29% and with all 128 threads on my machine,
the improvement reaches 46%.

The full new encoding of types is as follows:

 - If the type ID is within the range of the basic types, the type is
   the corresponding basic type.

 - Otherwise, if bit 0 is set, the type is a tuple and the rest of the
   bits are a canonical pointer to the tuple.

 - Otherwise, the type is a reference type. Bit 1 determines the
   nullability and the rest of the bits encode the heap type.

Also update the encodings of basic heap types so they no longer use the
low two bits to avoid conflicts with the use of those bits in the
encoding of types.

4 files changed, 150 insertions, 454 deletions

diff --git a/src/wasm-type.h b/src/wasm-type.h
index d26ba324f..b48a10713 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -96,26 +96,27 @@ class HeapType {
   uintptr_t id;
 
 public:
-  // Bit zero indicates whether the type is `shared`, so we need to leave it
-  // free.
+  // Bits 0 and 1 are used by the Type representation, so need to be left free.
+  // Bit 2 determines whether the basic heap type is shared (1) or unshared (0).
   enum BasicHeapType : uint32_t {
-    ext = 0 << 1,
-    func = 1 << 1,
-    cont = 2 << 1,
-    any = 3 << 1,
-    eq = 4 << 1,
-    i31 = 5 << 1,
-    struct_ = 6 << 1,
-    array = 7 << 1,
-    exn = 8 << 1,
-    string = 9 << 1,
-    none = 10 << 1,
-    noext = 11 << 1,
-    nofunc = 12 << 1,
-    nocont = 13 << 1,
-    noexn = 14 << 1,
+    ext = 1 << 3,
+    func = 2 << 3,
+    cont = 3 << 3,
+    any = 4 << 3,
+    eq = 5 << 3,
+    i31 = 6 << 3,
+    struct_ = 7 << 3,
+    array = 8 << 3,
+    exn = 9 << 3,
+    string = 10 << 3,
+    none = 11 << 3,
+    noext = 12 << 3,
+    nofunc = 13 << 3,
+    nocont = 14 << 3,
+    noexn = 15 << 3,
   };
-  static constexpr BasicHeapType _last_basic_type = BasicHeapType(noexn + 1);
+  static constexpr BasicHeapType _last_basic_type =
+    BasicHeapType(noexn + (1 << 2));
 
   // BasicHeapType can be implicitly upgraded to HeapType
   constexpr HeapType(BasicHeapType id) : id(id) {}
@@ -213,7 +214,7 @@ public:
   // Get the shared or unshared version of this basic heap type.
   constexpr BasicHeapType getBasic(Shareability share) const {
     assert(isBasic());
-    return BasicHeapType(share == Shared ? (id | 1) : (id & ~1));
+    return BasicHeapType(share == Shared ? (id | 4) : (id & ~4));
   }
 
   // (In)equality must be defined for both HeapType and BasicHeapType because it
@@ -261,49 +262,15 @@ public:
   std::string toString() const;
 };
 
-// Internal only.
-struct TypeInfo {
-  using type_t = Type;
-  // Used in assertions to ensure that temporary types don't leak into the
-  // global store.
-  bool isTemp = false;
-  enum Kind {
-    TupleKind,
-    RefKind,
-  } kind;
-  struct Ref {
-    HeapType heapType;
-    Nullability nullability;
-  };
-  union {
-    Tuple tuple;
-    Ref ref;
-  };
-
-  TypeInfo(const Tuple& tuple);
-  TypeInfo(Tuple&& tuple) : kind(TupleKind), tuple(std::move(tuple)) {}
-  TypeInfo(HeapType heapType, Nullability nullable)
-    : kind(RefKind), ref{heapType, nullable} {}
-  TypeInfo(const TypeInfo& other);
-  ~TypeInfo();
-
-  constexpr bool isTuple() const { return kind == TupleKind; }
-  constexpr bool isRef() const { return kind == RefKind; }
-
-  // If this TypeInfo represents a Type that can be represented more simply,
-  // return that simpler Type. For example, this handles eliminating singleton
-  // tuple types.
-  std::optional<Type> getCanonical() const;
-
-  bool operator==(const TypeInfo& other) const;
-  bool operator!=(const TypeInfo& other) const { return !(*this == other); }
-};
-
 class Type {
   // The `id` uniquely represents each type, so type equality is just a
-  // comparison of the ids. For basic types the `id` is just the `BasicType`
-  // enum value below, and for constructed types the `id` is the address of the
-  // canonical representation of the type, making lookups cheap for all types.
+  // comparison of the ids. The basic types are packed at the bottom of the
+  // expressible range, and after that tuple types are distinguished by having
+  // bit 0 set. When that bit is masked off, they are pointers to the underlying
+  // vectors of types. Otherwise, the type is a reference type, and is
+  // represented as a heap type with bit 1 set iff the reference type is
+  // nullable.
+  //
   // Since `Type` is really just a single integer, it should be passed by value.
   // This is a uintptr_t rather than a TypeID (uint64_t) to save memory on
   // 32-bit platforms.
@@ -311,13 +278,13 @@ class Type {
 
 public:
   enum BasicType : uint32_t {
-    none,
-    unreachable,
-    i32,
-    i64,
-    f32,
-    f64,
-    v128,
+    none = 0,
+    unreachable = 1,
+    i32 = 2,
+    i64 = 3,
+    f32 = 4,
+    f64 = 5,
+    v128 = 6,
   };
   static constexpr BasicType _last_basic_type = v128;
 
@@ -338,7 +305,8 @@ public:
 
   // Construct from a heap type description. Also covers construction from
   // Signature, Struct or Array via implicit conversion to HeapType.
-  Type(HeapType, Nullability nullable);
+  Type(HeapType heapType, Nullability nullable)
+    : Type(heapType.getID() | (nullable == Nullable ? 2 : 0)) {}
 
   // Predicates
   //                 Compound Concrete
@@ -376,74 +344,37 @@ public:
   // Tuples, refs, etc. are quickly handled using isBasic(), leaving the non-
   // basic case for the underlying implementation.
 
-  bool isTuple() const {
-    if (isBasic()) {
-      return false;
-    } else {
-      return getTypeInfo(*this)->isTuple();
-    }
-  }
-
-  bool isRef() const {
-    if (isBasic()) {
-      return false;
-    } else {
-      return getTypeInfo(*this)->isRef();
-    }
-  }
-
-  bool isFunction() const {
-    if (isBasic()) {
-      return false;
-    } else {
-      auto* info = getTypeInfo(*this);
-      return info->isRef() && info->ref.heapType.isFunction();
-    }
-  }
-
-  bool isData() const {
-    if (isBasic()) {
-      return false;
-    } else {
-      auto* info = getTypeInfo(*this);
-      return info->isRef() && info->ref.heapType.isData();
-    }
-  }
-
-  // Checks whether a type is a reference and is nullable. This returns false
-  // for a value that is not a reference, that is, for which nullability is
-  // irrelevant.
-  bool isNullable() const {
-    if (isRef()) {
-      return getTypeInfo(*this)->ref.nullability == Nullable;
-    } else {
-      return false;
-    }
+  // TODO: Experiment with leaving bit 0 free in basic types.
+  bool isTuple() const { return !isBasic() && (id & 1); }
+  const Tuple& getTuple() const {
+    assert(isTuple());
+    return *(Tuple*)(id & ~1);
   }
 
-  // Checks whether a type is a reference and is non-nullable. This returns
-  // false for a value that is not a reference, that is, for which nullability
-  // is irrelevant. (For that reason, this is only the negation of isNullable()
-  // on references, but both return false on non-references.)
-  bool isNonNullable() const {
-    if (isRef()) {
-      return getTypeInfo(*this)->ref.nullability == NonNullable;
-    } else {
-      return false;
-    }
+  bool isRef() const { return !isBasic() && !(id & 1); }
+  bool isNullable() const { return isRef() && (id & 2); }
+  bool isNonNullable() const { return isRef() && !(id & 2); }
+  HeapType getHeapType() const {
+    assert(isRef());
+    return HeapType(id & ~2);
   }
 
+  bool isFunction() const { return isRef() && getHeapType().isFunction(); }
   bool isSignature() const { return isRef() && getHeapType().isSignature(); }
+  bool isData() const { return isRef() && getHeapType().isData(); }
 
   // Whether this type is only inhabited by null values.
-  bool isNull() const;
-  bool isStruct() const;
-  bool isArray() const;
-  bool isExn() const;
-  bool isString() const;
+  bool isNull() const { return isRef() && getHeapType().isBottom(); }
+  bool isStruct() const { return isRef() && getHeapType().isStruct(); }
+  bool isArray() const { return isRef() && getHeapType().isArray(); }
+  bool isExn() const { return isRef() && getHeapType().isExn(); }
+  bool isString() const { return isRef() && getHeapType().isString(); }
   bool isDefaultable() const;
 
-  Nullability getNullability() const;
+  // TODO: Allow this only for reference types.
+  Nullability getNullability() const {
+    return isNullable() ? Nullable : NonNullable;
+  }
 
 private:
   template<bool (Type::*pred)() const> bool hasPredicate() {
@@ -489,20 +420,6 @@ public:
   // Returns the feature set required to use this type.
   FeatureSet getFeatures() const;
 
-  // Returns the tuple, assuming that this is a tuple type. Note that it is
-  // normally simpler to use operator[] and size() on the Type directly.
-  HeapType getHeapType() const {
-    assert(isRef());
-    return getTypeInfo(*this)->ref.heapType;
-  }
-
-  // Gets the heap type corresponding to this type, assuming that it is a
-  // reference type.
-  const Tuple& getTuple() const {
-    assert(isTuple());
-    return getTypeInfo(*this)->tuple;
-  }
-
   // Returns a number type based on its size in bytes and whether it is a float
   // type.
   static Type get(unsigned byteSize, bool float_);
@@ -565,7 +482,9 @@ public:
 
   std::string toString() const;
 
-  size_t size() const;
+  size_t size() const {
+    return isTuple() ? getTuple().size() : size_t(id != Type::none);
+  }
 
   struct Iterator : ParentIndexIterator<const Type*, Iterator> {
     using value_type = Type;
@@ -583,15 +502,8 @@ public:
     return std::make_reverse_iterator(begin());
   }
   const Type& operator[](size_t i) const { return *Iterator{{this, i}}; }
-
-  static TypeInfo* getTypeInfo(Type type) {
-    assert(!type.isBasic());
-    return (TypeInfo*)type.getID();
-  }
 };
 
-inline bool Type::isNull() const { return isRef() && getHeapType().isBottom(); }
-
 namespace HeapTypes {
 
 constexpr HeapType ext = HeapType::ext;
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 51b77c3ab..a6ed68770 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -143,7 +143,6 @@ struct RecGroupHasher {
   size_t topLevelHash(HeapType type) const;
   size_t hash(Type type) const;
   size_t hash(HeapType type) const;
-  size_t hash(const TypeInfo& info) const;
   size_t hash(const HeapTypeInfo& info) const;
   size_t hash(const Tuple& tuple) const;
   size_t hash(const Field& field) const;
@@ -170,7 +169,6 @@ struct RecGroupEquator {
   bool topLevelEq(HeapType a, HeapType b) const;
   bool eq(Type a, Type b) const;
   bool eq(HeapType a, HeapType b) const;
-  bool eq(const TypeInfo& a, const TypeInfo& b) const;
   bool eq(const HeapTypeInfo& a, const HeapTypeInfo& b) const;
   bool eq(const Tuple& a, const Tuple& b) const;
   bool eq(const Field& a, const Field& b) const;
@@ -204,11 +202,6 @@ public:
   }
 };
 
-template<> class hash<wasm::TypeInfo> {
-public:
-  size_t operator()(const wasm::TypeInfo& info) const;
-};
-
 template<typename T> class hash<reference_wrapper<const T>> {
 public:
   size_t operator()(const reference_wrapper<const T>& ref) const {
@@ -238,17 +231,6 @@ HeapType asHeapType(std::unique_ptr<HeapTypeInfo>& info) {
   return HeapType(uintptr_t(info.get()));
 }
 
-Type markTemp(Type type) {
-  if (!type.isBasic()) {
-    Type::getTypeInfo(type)->isTemp = true;
-  }
-  return type;
-}
-
-bool isTemp(Type type) {
-  return !type.isBasic() && Type::getTypeInfo(type)->isTemp;
-}
-
 bool isTemp(HeapType type) {
   return !type.isBasic() && getHeapTypeInfo(type)->isTemp;
 }
@@ -350,35 +332,7 @@ private:
   }
 };
 
-// A type graph walker base class that still does no useful work, but at least
-// knows to scan each HeapType and Type only once.
-template<typename Self> struct TypeGraphWalker : TypeGraphWalkerBase<Self> {
-  // Override these.
-  void noteType(Type type) {}
-  void noteHeapType(HeapType ht) {}
-
-  void scanType(Type* type) {
-    if (scannedTypes.insert(*type).second) {
-      static_cast<Self*>(this)->noteType(*type);
-      TypeGraphWalkerBase<Self>::scanType(type);
-    }
-  }
-  void scanHeapType(HeapType* ht) {
-    if (scannedHeapTypes.insert(*ht).second) {
-      static_cast<Self*>(this)->noteHeapType(*ht);
-      TypeGraphWalkerBase<Self>::scanHeapType(ht);
-    }
-  }
-
-private:
-  std::unordered_set<HeapType> scannedHeapTypes;
-  std::unordered_set<Type> scannedTypes;
-};
-
-// A type graph walker base class that still does no useful work, but at least
-// knows to scan each HeapType and Type only once.
-// A type graph walker that calls `noteChild` on each each direct HeapType child
-// of the root.
+// A type graph walker that scans each each direct HeapType child of the root.
 template<typename Self> struct HeapTypeChildWalker : TypeGraphWalkerBase<Self> {
   void scanType(Type* type) {
     isTopLevel = false;
@@ -496,59 +450,6 @@ std::optional<HeapType> getBasicHeapTypeLUB(HeapType::BasicHeapType a,
 
 } // anonymous namespace
 
-TypeInfo::TypeInfo(const Tuple& tuple) : kind(TupleKind), tuple(tuple) {}
-
-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;
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
-TypeInfo::~TypeInfo() {
-  switch (kind) {
-    case TupleKind:
-      tuple.~Tuple();
-      return;
-    case RefKind:
-      ref.~Ref();
-      return;
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
-std::optional<Type> TypeInfo::getCanonical() const {
-  if (isTuple()) {
-    if (tuple.size() == 0) {
-      return Type::none;
-    }
-    if (tuple.size() == 1) {
-      return tuple[0];
-    }
-  }
-  return {};
-}
-
-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.nullability == other.ref.nullability &&
-             ref.heapType == other.ref.heapType;
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
 HeapTypeInfo::~HeapTypeInfo() {
   switch (kind) {
     case HeapTypeKind::Func:
@@ -571,82 +472,75 @@ HeapTypeInfo::~HeapTypeInfo() {
 
 namespace {
 
-struct TypeStore {
+struct TupleStore {
   std::recursive_mutex mutex;
 
-  // Track unique_ptrs for constructed types to avoid leaks.
-  std::vector<std::unique_ptr<TypeInfo>> constructedTypes;
+  // Track unique_ptrs for constructed tuples to avoid leaks.
+  std::vector<std::unique_ptr<Tuple>> constructedTuples;
 
-  // Maps from constructed types to their canonical Type IDs.
-  std::unordered_map<std::reference_wrapper<const TypeInfo>, uintptr_t> typeIDs;
+  // Maps from constructed tuples to their canonical Type IDs.
+  std::unordered_map<std::reference_wrapper<const Tuple>, uintptr_t> typeIDs;
 
-#ifndef NDEBUG
-  bool isGlobalStore();
-#endif
-
-  Type insert(const TypeInfo& info) { return doInsert(info); }
-  Type insert(std::unique_ptr<TypeInfo>&& info) { return doInsert(info); }
-  bool hasCanonical(const TypeInfo& info, Type& canonical);
+  Type insert(const Tuple& info) { return doInsert(info); }
+  Type insert(std::unique_ptr<Tuple>&& info) { return doInsert(info); }
+  bool hasCanonical(const Tuple& info, Tuple& canonical);
 
   void clear() {
     typeIDs.clear();
-    constructedTypes.clear();
+    constructedTuples.clear();
   }
 
 private:
-  template<typename Ref> Type doInsert(Ref& infoRef) {
-    const TypeInfo& info = [&]() {
-      if constexpr (std::is_same_v<Ref, const TypeInfo>) {
-        return infoRef;
-      } else if constexpr (std::is_same_v<Ref, std::unique_ptr<TypeInfo>>) {
-        infoRef->isTemp = false;
-        return *infoRef;
+  template<typename Ref> Type doInsert(Ref& tupleRef) {
+    const Tuple& tuple = [&]() {
+      if constexpr (std::is_same_v<Ref, const Tuple>) {
+        return tupleRef;
+      } else if constexpr (std::is_same_v<Ref, std::unique_ptr<Tuple>>) {
+        return *tupleRef;
       }
     }();
 
-    auto getPtr = [&]() -> std::unique_ptr<TypeInfo> {
-      if constexpr (std::is_same_v<Ref, const TypeInfo>) {
-        return std::make_unique<TypeInfo>(infoRef);
-      } else if constexpr (std::is_same_v<Ref, std::unique_ptr<TypeInfo>>) {
-        return std::move(infoRef);
+    auto getPtr = [&]() -> std::unique_ptr<Tuple> {
+      if constexpr (std::is_same_v<Ref, const Tuple>) {
+        return std::make_unique<Tuple>(tupleRef);
+      } else if constexpr (std::is_same_v<Ref, std::unique_ptr<Tuple>>) {
+        return std::move(tupleRef);
       }
     };
 
     auto insertNew = [&]() {
-      assert((!isGlobalStore() || !info.isTemp) && "Leaking temporary type!");
       auto ptr = getPtr();
-      TypeID id = uintptr_t(ptr.get());
+      TypeID id = uintptr_t(ptr.get()) | 1;
       assert(id > Type::_last_basic_type);
       typeIDs.insert({*ptr, id});
-      constructedTypes.emplace_back(std::move(ptr));
+      constructedTuples.emplace_back(std::move(ptr));
       return Type(id);
     };
 
     // Turn e.g. singleton tuple into non-tuple.
-    if (auto canonical = info.getCanonical()) {
-      return *canonical;
+    if (tuple.size() == 0) {
+      return Type::none;
+    }
+    if (tuple.size() == 1) {
+      return tuple[0];
     }
 
     std::lock_guard<std::recursive_mutex> lock(mutex);
-    // Check whether we already have a type for this structural Info.
-    auto indexIt = typeIDs.find(std::cref(info));
+    // Check whether we already have a type for this tuple.
+    auto indexIt = typeIDs.find(std::cref(tuple));
     if (indexIt != typeIDs.end()) {
       return Type(indexIt->second);
     }
-    // We do not have a type for this Info already. Create one.
+    // We do not have a type for this tuple already. Create one.
     return insertNew();
   }
 };
 
-static TypeStore globalTypeStore;
+static TupleStore globalTupleStore;
 
 static std::vector<std::unique_ptr<HeapTypeInfo>> globalHeapTypeStore;
 static std::recursive_mutex globalHeapTypeStoreMutex;
 
-#ifndef NDEBUG
-bool TypeStore::isGlobalStore() { return this == &globalTypeStore; }
-#endif
-
 // Keep track of the constructed recursion groups.
 struct RecGroupStore {
   std::mutex mutex;
@@ -708,7 +602,7 @@ void validateTuple(const Tuple& tuple) {
 } // anonymous namespace
 
 void destroyAllTypesForTestingPurposesOnly() {
-  globalTypeStore.clear();
+  globalTupleStore.clear();
   globalHeapTypeStore.clear();
   globalRecGroupStore.clear();
 }
@@ -717,36 +611,13 @@ Type::Type(std::initializer_list<Type> types) : Type(Tuple(types)) {}
 
 Type::Type(const Tuple& tuple) {
   validateTuple(tuple);
-#ifndef NDEBUG
-  for (auto type : tuple) {
-    assert(!isTemp(type) && "Leaking temporary type!");
-  }
-#endif
-  new (this) Type(globalTypeStore.insert(tuple));
+  new (this) Type(globalTupleStore.insert(tuple));
 }
 
 Type::Type(Tuple&& tuple) {
-#ifndef NDEBUG
-  for (auto type : tuple) {
-    assert(!isTemp(type) && "Leaking temporary type!");
-  }
-#endif
-  new (this) Type(globalTypeStore.insert(std::move(tuple)));
-}
-
-Type::Type(HeapType heapType, Nullability nullable) {
-  assert(!isTemp(heapType) && "Leaking temporary type!");
-  new (this) Type(globalTypeStore.insert(TypeInfo(heapType, nullable)));
+  new (this) Type(globalTupleStore.insert(std::move(tuple)));
 }
 
-bool Type::isStruct() const { return isRef() && getHeapType().isStruct(); }
-
-bool Type::isArray() const { return isRef() && getHeapType().isArray(); }
-
-bool Type::isExn() const { return isRef() && getHeapType().isExn(); }
-
-bool Type::isString() const { return isRef() && getHeapType().isString(); }
-
 bool Type::isDefaultable() const {
   // A variable can get a default value if its type is concrete (unreachable
   // and none have no values, hence no default), and if it's a reference, it
@@ -762,10 +633,6 @@ bool Type::isDefaultable() const {
   return isConcrete() && !isNonNullable();
 }
 
-Nullability Type::getNullability() const {
-  return isNullable() ? Nullable : NonNullable;
-}
-
 unsigned Type::getByteSize() const {
   // TODO: alignment?
   auto getSingleByteSize = [](Type t) {
@@ -958,61 +825,36 @@ Type Type::getGreatestLowerBound(Type a, Type b) {
   return Type(heapType, nullability);
 }
 
-size_t Type::size() const {
-  if (isTuple()) {
-    return getTypeInfo(*this)->tuple.size();
-  } else {
-    // TODO: unreachable is special and expands to {unreachable} currently.
-    // see also: https://github.com/WebAssembly/binaryen/issues/3062
-    return size_t(id != Type::none);
-  }
-}
-
 const Type& Type::Iterator::operator*() const {
   if (parent->isTuple()) {
-    return getTypeInfo(*parent)->tuple[index];
+    return parent->getTuple()[index];
   } else {
-    // TODO: see comment in Type::size()
-    assert(index == 0 && parent->id != Type::none && "Index out of bounds");
+    assert(index == 0 && *parent != Type::none && "Index out of bounds");
     return *parent;
   }
 }
 
 HeapType::HeapType(Signature sig) {
-  assert(!isTemp(sig.params) && "Leaking temporary type!");
-  assert(!isTemp(sig.results) && "Leaking temporary type!");
   new (this)
     HeapType(globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(sig)));
 }
 
 HeapType::HeapType(Continuation continuation) {
-  assert(!isTemp(continuation.type) && "Leaking temporary type!");
   new (this) HeapType(
     globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(continuation)));
 }
 
 HeapType::HeapType(const Struct& struct_) {
-#ifndef NDEBUG
-  for (const auto& field : struct_.fields) {
-    assert(!isTemp(field.type) && "Leaking temporary type!");
-  }
-#endif
   new (this) HeapType(
     globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(struct_)));
 }
 
 HeapType::HeapType(Struct&& struct_) {
-#ifndef NDEBUG
-  for (const auto& field : struct_.fields) {
-    assert(!isTemp(field.type) && "Leaking temporary type!");
-  }
-#endif
   new (this) HeapType(globalRecGroupStore.insert(
     std::make_unique<HeapTypeInfo>(std::move(struct_))));
 }
 
 HeapType::HeapType(Array array) {
-  assert(!isTemp(array.element.type) && "Leaking temporary type!");
   new (this)
     HeapType(globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(array)));
 }
@@ -1059,7 +901,7 @@ bool HeapType::isOpen() const {
 
 Shareability HeapType::getShared() const {
   if (isBasic()) {
-    return (id & 1) != 0 ? Shared : Unshared;
+    return (id & 4) != 0 ? Shared : Unshared;
   } else {
     return getHeapTypeInfo(*this)->share;
   }
@@ -1764,9 +1606,6 @@ std::ostream& TypePrinter::print(Type type) {
 #if TRACE_CANONICALIZATION
   os << "(;" << ((type.getID() >> 4) % 1000) << ";) ";
 #endif
-  if (isTemp(type)) {
-    os << "(; temp ;) ";
-  }
   if (type.isTuple()) {
     print(type.getTuple());
   } else if (type.isRef()) {
@@ -2029,9 +1868,16 @@ size_t RecGroupHasher::hash(Type type) const {
   size_t digest = wasm::hash(type.isBasic());
   if (type.isBasic()) {
     wasm::rehash(digest, type.getID());
-  } else {
-    hash_combine(digest, hash(*Type::getTypeInfo(type)));
+    return digest;
   }
+  wasm::rehash(digest, type.isTuple());
+  if (type.isTuple()) {
+    hash_combine(digest, hash(type.getTuple()));
+    return digest;
+  }
+  assert(type.isRef());
+  rehash(digest, type.getNullability());
+  rehash(digest, hash(type.getHeapType()));
   return digest;
 }
 
@@ -2053,20 +1899,6 @@ size_t RecGroupHasher::hash(HeapType type) const {
   return digest;
 }
 
-size_t RecGroupHasher::hash(const TypeInfo& info) const {
-  size_t digest = wasm::hash(info.kind);
-  switch (info.kind) {
-    case TypeInfo::TupleKind:
-      hash_combine(digest, hash(info.tuple));
-      return digest;
-    case TypeInfo::RefKind:
-      rehash(digest, info.ref.nullability);
-      hash_combine(digest, hash(info.ref.heapType));
-      return digest;
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
 size_t RecGroupHasher::hash(const HeapTypeInfo& info) const {
   size_t digest = wasm::hash(bool(info.supertype));
   if (info.supertype) {
@@ -2162,7 +1994,14 @@ bool RecGroupEquator::eq(Type a, Type b) const {
   if (a.isBasic() || b.isBasic()) {
     return a == b;
   }
-  return eq(*Type::getTypeInfo(a), *Type::getTypeInfo(b));
+  if (a.isTuple() && b.isTuple()) {
+    return eq(a.getTuple(), b.getTuple());
+  }
+  if (a.isRef() && b.isRef()) {
+    return a.getNullability() == b.getNullability() &&
+           eq(a.getHeapType(), b.getHeapType());
+  }
+  return false;
 }
 
 bool RecGroupEquator::eq(HeapType a, HeapType b) const {
@@ -2184,20 +2023,6 @@ bool RecGroupEquator::eq(HeapType a, HeapType b) const {
   return (selfRefA && selfRefB) || (!selfRefA && !selfRefB && groupA == groupB);
 }
 
-bool RecGroupEquator::eq(const TypeInfo& a, const TypeInfo& b) const {
-  if (a.kind != b.kind) {
-    return false;
-  }
-  switch (a.kind) {
-    case TypeInfo::TupleKind:
-      return eq(a.tuple, b.tuple);
-    case TypeInfo::RefKind:
-      return a.ref.nullability == b.ref.nullability &&
-             eq(a.ref.heapType, b.ref.heapType);
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
 bool RecGroupEquator::eq(const HeapTypeInfo& a, const HeapTypeInfo& b) const {
   if (bool(a.supertype) != bool(b.supertype)) {
     return false;
@@ -2268,9 +2093,9 @@ bool RecGroupEquator::eq(const Array& a, const Array& b) const {
 } // anonymous namespace
 
 struct TypeBuilder::Impl {
-  // Store of temporary Types. Types that need to be canonicalized will be
-  // copied into the global TypeStore.
-  TypeStore typeStore;
+  // Store of temporary tuples. Tuples that need to be canonicalized will be
+  // copied into the global TupleStore.
+  TupleStore tupleStore;
 
   // Store of temporary recursion groups, which will be moved to the global
   // collection of recursion groups as part of building.
@@ -2361,17 +2186,11 @@ HeapType TypeBuilder::getTempHeapType(size_t i) {
 }
 
 Type TypeBuilder::getTempTupleType(const Tuple& tuple) {
-  Type ret = impl->typeStore.insert(tuple);
-  if (tuple.size() > 1) {
-    return markTemp(ret);
-  } else {
-    // No new tuple was created, so the result might not be temporary.
-    return ret;
-  }
+  return impl->tupleStore.insert(tuple);
 }
 
 Type TypeBuilder::getTempRefType(HeapType type, Nullability nullable) {
-  return markTemp(impl->typeStore.insert(TypeInfo(type, nullable)));
+  return Type(type, nullable);
 }
 
 void TypeBuilder::setSubType(size_t i, std::optional<HeapType> super) {
@@ -2490,8 +2309,7 @@ void updateReferencedHeapTypes(
   std::unique_ptr<HeapTypeInfo>& info,
   const std::unordered_map<HeapType, HeapType>& canonicalized) {
   // Update the reference types that refer to canonicalized heap types to be
-  // their canonical versions. Update the Types rather than the HeapTypes so
-  // that the validation of supertypes sees canonical types.
+  // their canonical versions.
   struct ChildUpdater : TypeGraphWalkerBase<ChildUpdater> {
     const std::unordered_map<HeapType, HeapType>& canonicalized;
     bool isTopLevel = true;
@@ -2505,8 +2323,6 @@ void updateReferencedHeapTypes(
         auto ht = type->getHeapType();
         if (auto it = canonicalized.find(ht); it != canonicalized.end()) {
           *type = Type(it->second, type->getNullability());
-        } else if (isTemp(*type) && !isTemp(ht)) {
-          *type = Type(ht, type->getNullability());
         }
       } else if (type->isTuple()) {
         TypeGraphWalkerBase<ChildUpdater>::scanType(type);
@@ -2603,39 +2419,29 @@ buildRecGroup(std::unique_ptr<RecGroupInfo>&& groupInfo,
 
   std::vector<HeapType> results(group.begin(), group.end());
 
-  // We need to make the Types canonical as well, but right now there is no way
-  // to move them to their global store, so we have to create new types and
-  // replace the old ones. TODO simplify this.
-  struct Locations : TypeGraphWalker<Locations> {
-    std::unordered_map<Type, std::unordered_set<Type*>> types;
+  // We need to make the tuples canonical as well, but right now there is no way
+  // to move them to their global store, so we have to create new tuples and
+  // replace the old ones.
+  struct TupleUpdater : TypeGraphWalkerBase<TupleUpdater> {
+    bool isTopLevel = true;
+    void scanHeapType(HeapType* type) {
+      // Only scan top-level heap types. Heap type children will either be
+      // scanned separately or are already canonical.
+      if (isTopLevel) {
+        TypeGraphWalkerBase<TupleUpdater>::scanHeapType(type);
+        isTopLevel = false;
+      }
+    }
     void scanType(Type* type) {
-      if (isTemp(*type)) {
-        types[*type].insert(type);
+      if (type->isTuple()) {
+        *type = globalTupleStore.insert(type->getTuple());
       }
-      TypeGraphWalker<Locations>::scanType(type);
     }
   };
 
-  Locations locations;
   for (auto& type : results) {
-    locations.walkRoot(&type);
-  }
-
-  // Canonicalize non-tuple Types (which never directly refer to other Types)
-  // before tuple Types to avoid canonicalizing a tuple that still contains
-  // non-canonical Types.
-  auto canonicalizeTypes = [&](bool tuples) {
-    for (auto& [original, uses] : locations.types) {
-      if (original.isTuple() == tuples) {
-        Type canonical = globalTypeStore.insert(*Type::getTypeInfo(original));
-        for (Type* use : uses) {
-          *use = canonical;
-        }
-      }
-    }
-  };
-  canonicalizeTypes(false);
-  canonicalizeTypes(true);
+    TupleUpdater().walkRoot(&type);
+  }
 
   return {results};
 }
@@ -2795,18 +2601,4 @@ size_t hash<wasm::RecGroup>::operator()(const wasm::RecGroup& group) const {
   return wasm::hash(group.getID());
 }
 
-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.nullability);
-      wasm::rehash(digest, info.ref.heapType);
-      return digest;
-  }
-  WASM_UNREACHABLE("unexpected kind");
-}
-
 } // namespace std
diff --git a/test/example/c-api-kitchen-sink.txt b/test/example/c-api-kitchen-sink.txt
index d3e6a6767..032d15db4 100644
--- a/test/example/c-api-kitchen-sink.txt
+++ b/test/example/c-api-kitchen-sink.txt
@@ -20,17 +20,17 @@ BinaryenTypeAuto: -1
 BinaryenPackedTypeNotPacked: 0
 BinaryenPackedTypeInt8: 1
 BinaryenPackedTypeInt16: 2
-BinaryenHeapTypeExt: 0
-BinaryenHeapTypeFunc: 2
-BinaryenHeapTypeAny: 6
-BinaryenHeapTypeEq: 8
-BinaryenHeapTypeI31: 10
-BinaryenHeapTypeStruct: 12
-BinaryenHeapTypeArray: 14
-BinaryenHeapTypeString: 18
-BinaryenHeapTypeNone: 20
-BinaryenHeapTypeNoext: 22
-BinaryenHeapTypeNofunc: 24
+BinaryenHeapTypeExt: 8
+BinaryenHeapTypeFunc: 16
+BinaryenHeapTypeAny: 32
+BinaryenHeapTypeEq: 40
+BinaryenHeapTypeI31: 48
+BinaryenHeapTypeStruct: 56
+BinaryenHeapTypeArray: 64
+BinaryenHeapTypeString: 80
+BinaryenHeapTypeNone: 88
+BinaryenHeapTypeNoext: 96
+BinaryenHeapTypeNofunc: 104
 BinaryenFeatureMVP: 0
 BinaryenFeatureAtomics: 1
 BinaryenFeatureBulkMemory: 16
diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp
index 97943551f..514df0c59 100644
--- a/test/gtest/type-builder.cpp
+++ b/test/gtest/type-builder.cpp
@@ -164,7 +164,6 @@ TEST_F(TypeTest, Basics) {
   TypeBuilder builder(3);
   ASSERT_EQ(builder.size(), size_t{3});
 
-  Type refSig = builder.getTempRefType(builder[0], NonNullable);
   Type refStruct = builder.getTempRefType(builder[1], NonNullable);
   Type refArray = builder.getTempRefType(builder[2], NonNullable);
   Type refNullArray = builder.getTempRefType(builder[2], Nullable);
@@ -191,7 +190,6 @@ TEST_F(TypeTest, Basics) {
   ASSERT_TRUE(built[2].isArray());
 
   // The built types should have the correct structure.
-  Type newRefSig = Type(built[0], NonNullable);
   Type newRefStruct = Type(built[1], NonNullable);
   Type newRefArray = Type(built[2], NonNullable);
   Type newRefNullArray = Type(built[2], Nullable);
@@ -200,12 +198,6 @@ TEST_F(TypeTest, Basics) {
             Signature(newRefStruct, {newRefArray, Type::i32}));
   EXPECT_EQ(built[1].getStruct(), Struct({Field(newRefNullArray, Immutable)}));
   EXPECT_EQ(built[2].getArray(), Array(Field(refNullAny, Mutable)));
-
-  // The built types should be different from the temporary types.
-  EXPECT_NE(newRefSig, refSig);
-  EXPECT_NE(newRefStruct, refStruct);
-  EXPECT_NE(newRefArray, refArray);
-  EXPECT_NE(newRefNullArray, refNullArray);
 }
 
 TEST_F(TypeTest, DirectSelfSupertype) {