Add new compound Signature, Struct and Array types (#3012)

Extends the `Type` hash-consing infrastructure to handle type-parameterized and constructed types introduced in the typed function references and GC proposals. This should be a non-functional change since the new types are not used anywhere yet. Recursive type construction and canonicalization is also left as future work.

Co-authored-by: Thomas Lively <tlively@google.com>

14 files changed, 587 insertions, 157 deletions

diff --git a/src/asmjs/asm_v_wasm.cpp b/src/asmjs/asm_v_wasm.cpp
index a6ffd4cc2..4a79d9caf 100644
--- a/src/asmjs/asm_v_wasm.cpp
+++ b/src/asmjs/asm_v_wasm.cpp
@@ -101,7 +101,7 @@ std::string getSig(Function* func) {
 }
 
 std::string getSig(Type results, Type params) {
-  assert(!results.isMulti());
+  assert(!results.isTuple());
   std::string sig;
   sig += getSig(results);
   for (const auto& param : params) {
diff --git a/src/ir/module-utils.h b/src/ir/module-utils.h
index 8f89c780f..375d9e245 100644
--- a/src/ir/module-utils.h
+++ b/src/ir/module-utils.h
@@ -409,7 +409,7 @@ collectSignatures(Module& wasm,
           counts[call->sig]++;
         } else if (Properties::isControlFlowStructure(curr)) {
           // TODO: Allow control flow to have input types as well
-          if (curr->type.isMulti()) {
+          if (curr->type.isTuple()) {
             counts[Signature(Type::none, curr->type)]++;
           }
         }
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index d03201f1a..f35f0d626 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -66,7 +66,7 @@ struct SExprType {
 
 static std::ostream& operator<<(std::ostream& o, const SExprType& localType) {
   Type type = localType.type;
-  if (type.isMulti()) {
+  if (type.isTuple()) {
     o << '(';
     auto sep = "";
     for (const auto& t : type) {
diff --git a/src/passes/RemoveUnusedBrs.cpp b/src/passes/RemoveUnusedBrs.cpp
index 9d4575bb7..2238e9e95 100644
--- a/src/passes/RemoveUnusedBrs.cpp
+++ b/src/passes/RemoveUnusedBrs.cpp
@@ -319,7 +319,7 @@ struct RemoveUnusedBrs : public WalkerPass<PostWalker<RemoveUnusedBrs>> {
             // be further optimizable, and if select does not branch we also
             // avoid one branch.
             // Multivalue selects are not supported
-            if (br->value && br->value->type.isMulti()) {
+            if (br->value && br->value->type.isTuple()) {
               return;
             }
             // If running the br's condition unconditionally is too expensive,
diff --git a/src/tools/fuzzing.h b/src/tools/fuzzing.h
index 23ea6bbec..b3c1212d4 100644
--- a/src/tools/fuzzing.h
+++ b/src/tools/fuzzing.h
@@ -306,7 +306,7 @@ private:
   double getDouble() { return Literal(get64()).reinterpretf64(); }
 
   Type getSubType(Type type) {
-    if (type.isMulti()) {
+    if (type.isTuple()) {
       std::vector<Type> types;
       for (const auto& t : type) {
         types.push_back(getSubType(t));
@@ -850,7 +850,7 @@ private:
 
   Expression* _makeConcrete(Type type) {
     bool canMakeControlFlow =
-      !type.isMulti() || wasm.features.has(FeatureSet::Multivalue);
+      !type.isTuple() || wasm.features.has(FeatureSet::Multivalue);
     using Self = TranslateToFuzzReader;
     FeatureOptions<Expression* (Self::*)(Type)> options;
     using WeightedOption = decltype(options)::WeightedOption;
@@ -886,7 +886,7 @@ private:
     if (type == Type::i32) {
       options.add(FeatureSet::ReferenceTypes, &Self::makeRefIsNull);
     }
-    if (type.isMulti()) {
+    if (type.isTuple()) {
       options.add(FeatureSet::Multivalue, &Self::makeTupleMake);
     }
     return (this->*pick(options))(type);
@@ -1265,7 +1265,7 @@ private:
 
   Expression* makeTupleMake(Type type) {
     assert(wasm.features.hasMultivalue());
-    assert(type.isMulti());
+    assert(type.isTuple());
     std::vector<Expression*> elements;
     for (const auto& t : type) {
       elements.push_back(make(t));
@@ -1765,7 +1765,7 @@ private:
       }
       return builder.makeRefNull();
     }
-    if (type.isMulti()) {
+    if (type.isTuple()) {
       std::vector<Expression*> operands;
       for (const auto& t : type) {
         operands.push_back(makeConst(t));
@@ -1783,7 +1783,7 @@ private:
   }
 
   Expression* makeUnary(Type type) {
-    assert(!type.isMulti());
+    assert(!type.isTuple());
     if (type == Type::unreachable) {
       if (auto* unary = makeUnary(getSingleConcreteType())->dynCast<Unary>()) {
         return builder.makeUnary(unary->op, make(Type::unreachable));
@@ -2004,7 +2004,7 @@ private:
   }
 
   Expression* makeBinary(Type type) {
-    assert(!type.isMulti());
+    assert(!type.isTuple());
     if (type == Type::unreachable) {
       if (auto* binary =
             makeBinary(getSingleConcreteType())->dynCast<Binary>()) {
diff --git a/src/tools/wasm-reduce.cpp b/src/tools/wasm-reduce.cpp
index e0491c0db..9c9978b63 100644
--- a/src/tools/wasm-reduce.cpp
+++ b/src/tools/wasm-reduce.cpp
@@ -1019,7 +1019,7 @@ struct Reducer
       RefNull* n = builder->makeRefNull();
       return tryToReplaceCurrent(n);
     }
-    if (curr->type.isMulti()) {
+    if (curr->type.isTuple()) {
       Expression* n =
         builder->makeConstantExpression(Literal::makeZero(curr->type));
       return tryToReplaceCurrent(n);
diff --git a/src/tools/wasm2c-wrapper.h b/src/tools/wasm2c-wrapper.h
index 91971c68b..6ea473d7a 100644
--- a/src/tools/wasm2c-wrapper.h
+++ b/src/tools/wasm2c-wrapper.h
@@ -164,7 +164,7 @@ int main(int argc, char** argv) {
     };
 
     ret += wasm2cSignature(result);
-    if (func->sig.params.isMulti()) {
+    if (func->sig.params.isTuple()) {
       for (const auto& param : func->sig.params) {
         ret += wasm2cSignature(param);
       }
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index 7cf8b4043..4e94da090 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -795,7 +795,7 @@ public:
   // minimal contents. as a replacement, this may reuse the
   // input node
   template<typename T> Expression* replaceWithIdenticalType(T* curr) {
-    if (curr->type.isMulti()) {
+    if (curr->type.isTuple()) {
       return makeConstantExpression(Literal::makeZero(curr->type));
     }
     Literal value;
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 3d025ad50..cee8dae03 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -26,21 +26,27 @@
 // Signature, Struct and Array types that will be single but not basic. To
 // prepare for this change, the following macro marks affected code locations.
 #define TODO_SINGLE_COMPOUND(type)                                             \
-  assert(!type.isMulti() && "Unexpected multi-value type");                    \
+  assert(!type.isTuple() && "Unexpected tuple type");                          \
   assert(!type.isCompound() && "TODO: handle compound types");
 
 namespace wasm {
 
+struct Tuple;
+struct Signature;
+struct Struct;
+struct Array;
+
+typedef std::vector<class Type> TypeList;
+
 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 `ValueType`
+  // comparison of the ids. For basic types the `id` is just the `BasicID`
   // 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.
   uintptr_t id;
-  void init(const std::vector<Type>&);
 
 public:
-  enum ValueType : uint32_t {
+  enum BasicID : uint32_t {
     none,
     unreachable,
     i32,
@@ -52,20 +58,31 @@ public:
     externref,
     nullref,
     exnref,
-    _last_value_type = exnref
+    _last_basic_id = exnref
   };
 
   Type() = default;
 
-  // ValueType can be implicitly upgraded to Type
-  constexpr Type(ValueType id) : id(id){};
+  // BasicID can be implicitly upgraded to Type
+  constexpr Type(BasicID id) : id(id){};
 
   // But converting raw uint32_t is more dangerous, so make it explicit
   explicit Type(uint64_t id) : id(id){};
 
-  // Construct from lists of elementary types
-  Type(std::initializer_list<Type> types);
-  explicit Type(const std::vector<Type>& types);
+  // Construct tuple from a list of single types
+  Type(std::initializer_list<Type>);
+
+  // Construct from tuple description
+  explicit Type(const Tuple&);
+
+  // Construct from signature description
+  explicit Type(const Signature, bool nullable);
+
+  // Construct from struct description
+  explicit Type(const Struct&, bool nullable);
+
+  // Construct from array description
+  explicit Type(const Array&, bool nullable);
 
   // Predicates
   //                 Compound Concrete
@@ -85,30 +102,22 @@ public:
   // │ nullref     ║ x │   │ x │ x │       │ │
   // │ exnref      ║ x │   │ x │ x │       │ │
   // ├─────────────╫───┼───┼───┼───┤───────┤ │
-  // │ Signature   ║   │ x │ x │ x │ f     │ │ ┐
-  // │ Struct      ║   │ x │ x │ x │       │ │ │ TODO (GC)
-  // │ Array       ║   │ x │ x │ x │       │ ┘ ┘
-  // │ Multi       ║   │ x │   │ x │       │
+  // │ Signature   ║   │ x │ x │ x │ f     │ │
+  // │ Struct      ║   │ x │ x │ x │       │ │
+  // │ Array       ║   │ x │ x │ x │       │ ┘
+  // │ Tuple       ║   │ x │   │ x │       │
   // └─────────────╨───┴───┴───┴───┴───────┘
-  constexpr bool isBasic() const { return id <= _last_value_type; }
-  constexpr bool isCompound() const { return id > _last_value_type; }
-  constexpr bool isSingle() const {
-    // TODO: Compound types Signature, Struct and Array are single
-    return id >= i32 && id <= _last_value_type;
-  }
-  constexpr bool isMulti() const {
-    // TODO: Compound types Signature, Struct and Array are not multi
-    return id > _last_value_type;
-  }
+  constexpr bool isBasic() const { return id <= _last_basic_id; }
+  constexpr bool isCompound() const { return id > _last_basic_id; }
   constexpr bool isConcrete() const { return id >= i32; }
   constexpr bool isInteger() const { return id == i32 || id == i64; }
   constexpr bool isFloat() const { return id == f32 || id == f64; }
   constexpr bool isVector() const { return id == v128; };
   constexpr bool isNumber() const { return id >= i32 && id <= v128; }
-  constexpr bool isRef() const {
-    // TODO: Compound types Signature, Struct and Array are ref
-    return id >= funcref && id <= exnref;
-  }
+  bool isTuple() const;
+  bool isSingle() const { return isConcrete() && !isTuple(); }
+  bool isRef() const;
+  bool isNullable() const;
 
 private:
   template<bool (Type::*pred)() const> bool hasPredicate() {
@@ -125,18 +134,18 @@ public:
   bool hasRef() { return hasPredicate<&Type::isRef>(); }
 
   constexpr uint64_t getID() const { return id; }
-  constexpr ValueType getBasic() const {
+  constexpr BasicID getBasic() const {
     assert(isBasic() && "Basic type expected");
-    return static_cast<ValueType>(id);
+    return static_cast<BasicID>(id);
   }
 
-  // (In)equality must be defined for both Type and ValueType because it is
+  // (In)equality must be defined for both Type and BasicID because it is
   // otherwise ambiguous whether to convert both this and other to int or
   // convert other to Type.
   bool operator==(const Type& other) const { return id == other.id; }
-  bool operator==(const ValueType& other) const { return id == other; }
+  bool operator==(const BasicID& otherId) const { return id == otherId; }
   bool operator!=(const Type& other) const { return id != other.id; }
-  bool operator!=(const ValueType& other) const { return id != other; }
+  bool operator!=(const BasicID& otherId) const { return id != otherId; }
 
   // Order types by some notion of simplicity
   bool operator<(const Type& other) const;
@@ -195,35 +204,13 @@ public:
       assert(parent == other.parent);
       return index - other.index;
     }
-    const value_type& operator*() const {
-      if (parent->isMulti()) {
-        return (*(std::vector<Type>*)parent->getID())[index];
-      } else {
-        // see TODO in Type::end()
-        assert(index == 0 && parent->id != Type::none && "Index out of bounds");
-        return *parent;
-      }
-    }
+    const value_type& operator*() const;
   };
 
   Iterator begin() const { return Iterator(this, 0); }
-  Iterator end() const {
-    if (isMulti()) {
-      return Iterator(this, (*(std::vector<Type>*)getID()).size());
-    } else {
-      // TODO: unreachable is special and expands to {unreachable} currently.
-      // see also: https://github.com/WebAssembly/binaryen/issues/3062
-      return Iterator(this, size_t(id != Type::none));
-    }
-  }
+  Iterator end() const;
   size_t size() const { return end() - begin(); }
-  const Type& operator[](size_t i) const {
-    if (isMulti()) {
-      return (*(std::vector<Type>*)getID())[i];
-    } else {
-      return *begin();
-    }
-  }
+  const Type& operator[](size_t i) const;
 };
 
 // Wrapper type for formatting types as "(param i32 i64 f32)"
@@ -240,6 +227,17 @@ struct ResultType {
   std::string toString() const;
 };
 
+struct Tuple {
+  TypeList types;
+  Tuple() : types() {}
+  Tuple(std::initializer_list<Type> types) : types(types) {}
+  Tuple(const TypeList& types) : types(types) {}
+  Tuple(TypeList&& types) : types(std::move(types)) {}
+  bool operator==(const Tuple& other) const { return types == other.types; }
+  bool operator!=(const Tuple& other) const { return !(*this == other); }
+  std::string toString() const;
+};
+
 struct Signature {
   Type params;
   Type results;
@@ -250,12 +248,69 @@ struct Signature {
   }
   bool operator!=(const Signature& other) const { return !(*this == other); }
   bool operator<(const Signature& other) const;
+  std::string toString() const;
+};
+
+struct Field {
+  Type type;
+  enum PackedType {
+    not_packed,
+    i8,
+    i16,
+  } packedType; // applicable iff type=i32
+  bool mutable_;
+
+  Field(Type type, bool mutable_ = false)
+    : type(type), packedType(not_packed), mutable_(mutable_) {}
+  Field(PackedType packedType, bool mutable_ = false)
+    : type(Type::i32), packedType(packedType), mutable_(mutable_) {}
+
+  constexpr bool isPacked() const {
+    if (packedType != not_packed) {
+      assert(type == Type::i32 && "unexpected type");
+      return true;
+    }
+    return false;
+  }
+
+  bool operator==(const Field& other) const {
+    return type == other.type && packedType == other.packedType &&
+           mutable_ == other.mutable_;
+  }
+  bool operator!=(const Field& other) const { return !(*this == other); }
+  std::string toString() const;
+};
+
+typedef std::vector<Field> FieldList;
+
+struct Struct {
+  FieldList fields;
+  Struct(const Struct& other) : fields(other.fields) {}
+  Struct(const FieldList& fields) : fields(fields) {}
+  Struct(FieldList&& fields) : fields(std::move(fields)) {}
+  bool operator==(const Struct& other) const { return fields == other.fields; }
+  bool operator!=(const Struct& other) const { return !(*this == other); }
+  std::string toString() const;
+};
+
+struct Array {
+  Field element;
+  Array(const Array& other) : element(other.element) {}
+  Array(const Field& element) : element(element) {}
+  Array(Field&& element) : element(std::move(element)) {}
+  bool operator==(const Array& other) const { return element == other.element; }
+  bool operator!=(const Array& other) const { return !(*this == other); }
+  std::string toString() const;
 };
 
-std::ostream& operator<<(std::ostream& os, Type t);
-std::ostream& operator<<(std::ostream& os, ParamType t);
-std::ostream& operator<<(std::ostream& os, ResultType t);
-std::ostream& operator<<(std::ostream& os, Signature t);
+std::ostream& operator<<(std::ostream&, Type);
+std::ostream& operator<<(std::ostream&, ParamType);
+std::ostream& operator<<(std::ostream&, ResultType);
+std::ostream& operator<<(std::ostream&, Tuple);
+std::ostream& operator<<(std::ostream&, Signature);
+std::ostream& operator<<(std::ostream&, Field);
+std::ostream& operator<<(std::ostream&, Struct);
+std::ostream& operator<<(std::ostream&, Array);
 
 } // namespace wasm
 
@@ -263,12 +318,27 @@ namespace std {
 
 template<> class hash<wasm::Type> {
 public:
-  size_t operator()(const wasm::Type& type) const;
+  size_t operator()(const wasm::Type&) const;
+};
+template<> class hash<wasm::Tuple> {
+public:
+  size_t operator()(const wasm::Tuple&) const;
 };
-
 template<> class hash<wasm::Signature> {
 public:
-  size_t operator()(const wasm::Signature& sig) const;
+  size_t operator()(const wasm::Signature&) const;
+};
+template<> class hash<wasm::Field> {
+public:
+  size_t operator()(const wasm::Field&) const;
+};
+template<> class hash<wasm::Struct> {
+public:
+  size_t operator()(const wasm::Struct&) const;
+};
+template<> class hash<wasm::Array> {
+public:
+  size_t operator()(const wasm::Array&) const;
 };
 
 } // namespace std
diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index 205d65b84..ffb007cf3 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -1435,8 +1435,7 @@ Literal Literal::shuffleV8x16(const Literal& other,
   return Literal(bytes);
 }
 
-template<Type::ValueType Ty, int Lanes>
-static Literal splat(const Literal& val) {
+template<Type::BasicID Ty, int Lanes> static Literal splat(const Literal& val) {
   assert(val.type == Ty);
   LaneArray<Lanes> lanes;
   lanes.fill(val);
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 0f7647b72..ae10687fb 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1793,7 +1793,7 @@ void WasmBinaryBuilder::skipUnreachableCode() {
 }
 
 void WasmBinaryBuilder::pushExpression(Expression* curr) {
-  if (curr->type.isMulti()) {
+  if (curr->type.isTuple()) {
     // Store tuple to local and push individual extracted values
     Builder builder(wasm);
     Index tuple = builder.addVar(currFunction, curr->type);
@@ -1822,7 +1822,7 @@ Expression* WasmBinaryBuilder::popExpression() {
   }
   // the stack is not empty, and we would not be going out of the current block
   auto ret = expressionStack.back();
-  assert(!ret->type.isMulti());
+  assert(!ret->type.isTuple());
   expressionStack.pop_back();
   return ret;
 }
@@ -1885,7 +1885,7 @@ Expression* WasmBinaryBuilder::popTuple(size_t numElems) {
 Expression* WasmBinaryBuilder::popTypedExpression(Type type) {
   if (type.isSingle()) {
     return popNonVoidExpression();
-  } else if (type.isMulti()) {
+  } else if (type.isTuple()) {
     return popTuple(type.size());
   } else {
     WASM_UNREACHABLE("Invalid popped type");
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index eedac4e95..88f90378c 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -23,7 +23,7 @@ namespace wasm {
 void BinaryInstWriter::emitResultType(Type type) {
   if (type == Type::unreachable) {
     o << binaryType(Type::none);
-  } else if (type.isMulti()) {
+  } else if (type.isTuple()) {
     o << S32LEB(parent.getTypeIndex(Signature(Type::none, type)));
   } else {
     o << binaryType(type);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 8e6903642..5247ebb6f 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -25,29 +25,215 @@
 #include "wasm-features.h"
 #include "wasm-type.h"
 
+namespace wasm {
+
+struct TypeInfo {
+  enum Kind { TupleKind, SignatureRefKind, StructRefKind, ArrayRefKind } kind;
+  struct SignatureRef {
+    Signature signature;
+    bool nullable;
+  };
+  struct StructRef {
+    Struct struct_;
+    bool nullable;
+  };
+  struct ArrayRef {
+    Array array;
+    bool nullable;
+  };
+  union {
+    Tuple tuple;
+    SignatureRef signatureRef;
+    StructRef structRef;
+    ArrayRef arrayRef;
+  };
+
+  TypeInfo(const Tuple& tuple) : kind(TupleKind), tuple(tuple) {}
+  TypeInfo(Tuple&& tuple) : kind(TupleKind), tuple(std::move(tuple)) {}
+  TypeInfo(const Signature& signature, bool nullable)
+    : kind(SignatureRefKind), signatureRef{signature, nullable} {}
+  TypeInfo(const Struct& struct_, bool nullable)
+    : kind(StructRefKind), structRef{struct_, nullable} {}
+  TypeInfo(const Array& array, bool nullable)
+    : kind(ArrayRefKind), arrayRef{array, nullable} {}
+  TypeInfo(const TypeInfo& other) {
+    kind = other.kind;
+    switch (kind) {
+      case TupleKind:
+        new (&tuple) auto(other.tuple);
+        return;
+      case SignatureRefKind:
+        new (&signatureRef) auto(other.signatureRef);
+        return;
+      case StructRefKind:
+        new (&structRef) auto(other.structRef);
+        return;
+      case ArrayRefKind:
+        new (&arrayRef) auto(other.arrayRef);
+        return;
+    }
+    WASM_UNREACHABLE("unexpected kind");
+  }
+  ~TypeInfo() {
+    switch (kind) {
+      case TupleKind: {
+        tuple.~Tuple();
+        return;
+      }
+      case SignatureRefKind: {
+        signatureRef.~SignatureRef();
+        return;
+      }
+      case StructRefKind: {
+        structRef.~StructRef();
+        return;
+      }
+      case ArrayRefKind: {
+        arrayRef.~ArrayRef();
+        return;
+      }
+    }
+    WASM_UNREACHABLE("unexpected kind");
+  }
+
+  constexpr bool isTuple() const { return kind == TupleKind; }
+  constexpr bool isSignatureRef() const { return kind == SignatureRefKind; }
+  constexpr bool isStructRef() const { return kind == StructRefKind; }
+  constexpr bool isArrayRef() const { return kind == ArrayRefKind; }
+
+  bool isNullable() const {
+    switch (kind) {
+      case TupleKind:
+        return false;
+      case SignatureRefKind:
+        return signatureRef.nullable;
+      case StructRefKind:
+        return structRef.nullable;
+      case ArrayRefKind:
+        return arrayRef.nullable;
+    }
+    WASM_UNREACHABLE("unexpected kind");
+  }
+
+  bool operator==(const TypeInfo& other) const {
+    if (kind != other.kind) {
+      return false;
+    }
+    switch (kind) {
+      case TupleKind:
+        return tuple == other.tuple;
+      case SignatureRefKind:
+        return signatureRef.nullable == other.signatureRef.nullable &&
+               signatureRef.signature == other.signatureRef.signature;
+      case StructRefKind:
+        return structRef.nullable == other.structRef.nullable &&
+               structRef.struct_ == other.structRef.struct_;
+      case ArrayRefKind:
+        return arrayRef.nullable == other.arrayRef.nullable &&
+               arrayRef.array == other.arrayRef.array;
+    }
+    WASM_UNREACHABLE("unexpected kind");
+  }
+  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;
+};
+
+std::ostream& operator<<(std::ostream&, TypeInfo);
+
+} // namespace wasm
+
 namespace std {
 
-template<> class hash<vector<wasm::Type>> {
+template<> class hash<wasm::TypeList> {
 public:
-  size_t operator()(const vector<wasm::Type>& types) const {
+  size_t operator()(const wasm::TypeList& types) const {
     auto digest = wasm::hash(types.size());
-    for (auto t : types) {
-      wasm::rehash(digest, t.getID());
+    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;
+  }
+};
+
+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.types);
+        return digest;
+      }
+      case wasm::TypeInfo::SignatureRefKind: {
+        wasm::rehash(digest, info.signatureRef.signature);
+        wasm::rehash(digest, info.signatureRef.nullable);
+        return digest;
+      }
+      case wasm::TypeInfo::StructRefKind: {
+        wasm::rehash(digest, info.structRef.struct_);
+        wasm::rehash(digest, info.structRef.nullable);
+        return digest;
+      }
+      case wasm::TypeInfo::ArrayRefKind: {
+        wasm::rehash(digest, info.arrayRef.array);
+        wasm::rehash(digest, info.arrayRef.nullable);
+        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.getID());
-  wasm::rehash(digest, sig.results.getID());
+  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_);
   return digest;
 }
 
+size_t hash<wasm::Struct>::operator()(const wasm::Struct& struct_) const {
+  auto digest = wasm::hash(0);
+  wasm::rehash(digest, struct_.fields);
+  return digest;
+}
+
+size_t hash<wasm::Array>::operator()(const wasm::Array& array) const {
+  return wasm::hash(array.element);
+}
+
 } // namespace std
 
 namespace wasm {
@@ -57,32 +243,58 @@ namespace {
 std::mutex mutex;
 
 // Track unique_ptrs for constructed types to avoid leaks
-std::vector<std::unique_ptr<std::vector<Type>>> constructedTypes;
-
-// Maps from type vectors to the canonical Type ID
-std::unordered_map<std::vector<Type>, uintptr_t> indices = {
-  {{}, Type::none},
-  {{Type::unreachable}, Type::unreachable},
-  {{Type::i32}, Type::i32},
-  {{Type::i64}, Type::i64},
-  {{Type::f32}, Type::f32},
-  {{Type::f64}, Type::f64},
-  {{Type::v128}, Type::v128},
-  {{Type::funcref}, Type::funcref},
-  {{Type::externref}, Type::externref},
-  {{Type::nullref}, Type::nullref},
-  {{Type::exnref}, Type::exnref},
+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 BasicID of the single type. As
+  // such, the following entries are solely placeholders to enable the lookup
+  // of lists of just one type to the BasicID 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({Type::externref}), Type::externref},
+  {TypeInfo({Type::nullref}), Type::nullref},
+  {TypeInfo({Type::exnref}), Type::exnref},
 };
 
 } // anonymous namespace
 
-void Type::init(const std::vector<Type>& types) {
+static uintptr_t canonicalize(const TypeInfo& info) {
+  std::lock_guard<std::mutex> lock(mutex);
+  auto indexIt = indices.find(info);
+  if (indexIt != indices.end()) {
+    return indexIt->second;
+  }
+  auto ptr = std::make_unique<TypeInfo>(info);
+  auto id = uintptr_t(ptr.get());
+  constructedTypes.push_back(std::move(ptr));
+  assert(id > Type::_last_basic_id);
+  indices[info] = id;
+  return id;
+}
+
+static TypeInfo* getTypeInfo(const Type& type) {
+  return (TypeInfo*)type.getID();
+}
+
+Type::Type(std::initializer_list<Type> types) : Type(Tuple(types)) {}
+
+Type::Type(const Tuple& tuple) {
+  auto& types = tuple.types;
 #ifndef NDEBUG
   for (Type t : types) {
-    assert(!t.isMulti() && t.isConcrete());
+    assert(t.isSingle());
   }
 #endif
-
   if (types.size() == 0) {
     id = none;
     return;
@@ -91,28 +303,62 @@ void Type::init(const std::vector<Type>& types) {
     *this = types[0];
     return;
   }
+  id = canonicalize(TypeInfo(tuple));
+}
 
-  // Add a new type if it hasn't been added concurrently
-  std::lock_guard<std::mutex> lock(mutex);
-  auto indexIt = indices.find(types);
-  if (indexIt != indices.end()) {
-    id = indexIt->second;
+Type::Type(const Signature signature, bool nullable) {
+  id = canonicalize(TypeInfo(signature, nullable));
+}
+
+Type::Type(const Struct& struct_, bool nullable) {
+#ifndef NDEBUG
+  for (Field f : struct_.fields) {
+    assert(f.type.isSingle());
+  }
+#endif
+  id = canonicalize(TypeInfo(struct_, nullable));
+}
+
+Type::Type(const Array& array, bool nullable) {
+  assert(array.element.type.isSingle());
+  id = canonicalize(TypeInfo(array, nullable));
+}
+
+bool Type::isTuple() const {
+  if (isBasic()) {
+    return false;
   } else {
-    auto vec = std::make_unique<std::vector<Type>>(types);
-    id = uintptr_t(vec.get());
-    constructedTypes.push_back(std::move(vec));
-    assert(id > _last_value_type);
-    indices[types] = id;
+    return getTypeInfo(*this)->isTuple();
   }
 }
 
-Type::Type(std::initializer_list<Type> types) { init(types); }
+bool Type::isRef() const {
+  if (isBasic()) {
+    return id >= funcref && id <= exnref;
+  } else {
+    switch (getTypeInfo(*this)->kind) {
+      case TypeInfo::TupleKind:
+        return false;
+      case TypeInfo::SignatureRefKind:
+      case TypeInfo::StructRefKind:
+      case TypeInfo::ArrayRefKind:
+        return true;
+    }
+    WASM_UNREACHABLE("unexpected kind");
+  }
+}
 
-Type::Type(const std::vector<Type>& types) { init(types); }
+bool Type::isNullable() const {
+  if (isBasic()) {
+    return id >= funcref && id <= exnref;
+  } else {
+    return getTypeInfo(*this)->isNullable();
+  }
+}
 
 bool Type::operator<(const Type& other) const {
-  return std::lexicographical_compare((*this).begin(),
-                                      (*this).end(),
+  return std::lexicographical_compare(begin(),
+                                      end(),
                                       other.begin(),
                                       other.end(),
                                       [](const Type& a, const Type& b) {
@@ -145,7 +391,7 @@ unsigned Type::getByteSize() const {
     WASM_UNREACHABLE("invalid type");
   };
 
-  if (isMulti()) {
+  if (isTuple()) {
     unsigned size = 0;
     for (const auto& t : *this) {
       size += getSingleByteSize(t);
@@ -156,8 +402,8 @@ unsigned Type::getByteSize() const {
 }
 
 Type Type::reinterpret() const {
-  auto singleType = *(*this).begin();
-  switch (singleType.getBasic()) {
+  assert(!isTuple() && "Unexpected tuple type");
+  switch ((*begin()).getBasic()) {
     case Type::i32:
       return f32;
     case Type::i64:
@@ -166,16 +412,9 @@ Type Type::reinterpret() const {
       return i32;
     case Type::f64:
       return i64;
-    case Type::v128:
-    case Type::funcref:
-    case Type::externref:
-    case Type::nullref:
-    case Type::exnref:
-    case Type::none:
-    case Type::unreachable:
+    default:
       WASM_UNREACHABLE("invalid type");
   }
-  WASM_UNREACHABLE("invalid type");
 }
 
 FeatureSet Type::getFeatures() const {
@@ -195,7 +434,7 @@ FeatureSet Type::getFeatures() const {
     }
   };
 
-  if (isMulti()) {
+  if (isTuple()) {
     FeatureSet feats = FeatureSet::Multivalue;
     for (const auto& t : *this) {
       feats |= getSingleFeatures(t);
@@ -229,7 +468,7 @@ bool Type::isSubType(Type left, Type right) {
       (right == Type::externref || left == Type::nullref)) {
     return true;
   }
-  if (left.isMulti() && right.isMulti()) {
+  if (left.isTuple() && right.isTuple()) {
     if (left.size() != right.size()) {
       return false;
     }
@@ -256,8 +495,8 @@ Type Type::getLeastUpperBound(Type a, Type b) {
   if (a.size() != b.size()) {
     return Type::none; // a poison value that must not be consumed
   }
-  if (a.isMulti()) {
-    std::vector<Type> types;
+  if (a.isTuple()) {
+    TypeList types;
     types.resize(a.size());
     for (size_t i = 0; i < types.size(); ++i) {
       types[i] = getLeastUpperBound(a[i], b[i]);
@@ -279,6 +518,35 @@ Type Type::getLeastUpperBound(Type a, Type b) {
   return Type::externref;
 }
 
+Type::Iterator Type::end() const {
+  if (isTuple()) {
+    return Iterator(this, getTypeInfo(*this)->tuple.types.size());
+  } else {
+    // TODO: unreachable is special and expands to {unreachable} currently.
+    // see also: https://github.com/WebAssembly/binaryen/issues/3062
+    return Iterator(this, size_t(id != Type::none));
+  }
+}
+
+const Type& Type::Iterator::operator*() const {
+  if (parent->isTuple()) {
+    return getTypeInfo(*parent)->tuple.types[index];
+  } else {
+    // TODO: see comment in Type::end()
+    assert(index == 0 && parent->id != Type::none && "Index out of bounds");
+    return *parent;
+  }
+}
+
+const Type& Type::operator[](size_t index) const {
+  if (isTuple()) {
+    return getTypeInfo(*this)->tuple.types[index];
+  } else {
+    assert(index == 0 && "Index out of bounds");
+    return *begin();
+  }
+}
+
 namespace {
 
 std::ostream&
@@ -305,6 +573,16 @@ std::string ParamType::toString() const { return genericToString(*this); }
 
 std::string ResultType::toString() const { return genericToString(*this); }
 
+std::string Tuple::toString() const { return genericToString(*this); }
+
+std::string Signature::toString() const { return genericToString(*this); }
+
+std::string Struct::toString() const { return genericToString(*this); }
+
+std::string Array::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;
@@ -316,16 +594,7 @@ bool Signature::operator<(const Signature& other) const {
 }
 
 std::ostream& operator<<(std::ostream& os, Type type) {
-  if (type.isMulti()) {
-    os << '(';
-    auto sep = "";
-    for (const auto& t : type) {
-      os << sep << t;
-      sep = ", ";
-    }
-    os << ')';
-  } else {
-    TODO_SINGLE_COMPOUND(type);
+  if (type.isBasic()) {
     switch (type.getBasic()) {
       case Type::none:
         os << "none";
@@ -361,6 +630,8 @@ std::ostream& operator<<(std::ostream& os, Type type) {
         os << "exnref";
         break;
     }
+  } else {
+    os << *getTypeInfo(type);
   }
   return os;
 }
@@ -373,8 +644,98 @@ std::ostream& operator<<(std::ostream& os, ResultType param) {
   return printPrefixedTypes(os, "result", param.type);
 }
 
+std::ostream& operator<<(std::ostream& os, Tuple tuple) {
+  auto& types = tuple.types;
+  auto size = types.size();
+  os << "(";
+  if (size) {
+    os << types[0];
+    for (size_t i = 1; i < size; ++i) {
+      os << " " << types[i];
+    }
+  }
+  return os << ")";
+}
+
 std::ostream& operator<<(std::ostream& os, Signature sig) {
-  return os << "Signature(" << sig.params << " => " << sig.results << ")";
+  os << "(func";
+  if (sig.params.getID() != Type::none) {
+    os << " ";
+    printPrefixedTypes(os, "param", sig.params);
+  }
+  if (sig.results.getID() != Type::none) {
+    os << " ";
+    printPrefixedTypes(os, "result", sig.results);
+  }
+  return os << ")";
+}
+
+std::ostream& operator<<(std::ostream& os, Field field) {
+  if (field.mutable_) {
+    os << "(mut ";
+  }
+  if (field.isPacked()) {
+    auto packedType = field.packedType;
+    if (packedType == Field::PackedType::i8) {
+      os << "i8";
+    } else if (packedType == Field::PackedType::i16) {
+      os << "i16";
+    } else {
+      WASM_UNREACHABLE("unexpected packed type");
+    }
+  } else {
+    os << field.type;
+  }
+  if (field.mutable_) {
+    os << ")";
+  }
+  return os;
+};
+
+std::ostream& operator<<(std::ostream& os, Struct struct_) {
+  os << "(struct";
+  if (struct_.fields.size()) {
+    os << " (field";
+    for (auto f : struct_.fields) {
+      os << " " << f;
+    }
+    os << ")";
+  }
+  return os << ")";
+}
+
+std::ostream& operator<<(std::ostream& os, Array array) {
+  return os << "(array " << array.element << ")";
+}
+
+std::ostream& operator<<(std::ostream& os, TypeInfo info) {
+  switch (info.kind) {
+    case TypeInfo::TupleKind: {
+      return os << info.tuple;
+    }
+    case TypeInfo::SignatureRefKind: {
+      os << "(ref ";
+      if (info.signatureRef.nullable) {
+        os << "null ";
+      }
+      return os << info.signatureRef.signature << ")";
+    }
+    case TypeInfo::StructRefKind: {
+      os << "(ref ";
+      if (info.structRef.nullable) {
+        os << "null ";
+      }
+      return os << info.structRef.struct_ << ")";
+    }
+    case TypeInfo::ArrayRefKind: {
+      os << "(ref ";
+      if (info.arrayRef.nullable) {
+        os << "null ";
+      }
+      return os << info.arrayRef.array << ")";
+    }
+  }
+  WASM_UNREACHABLE("unexpected kind");
 }
 
 } // namespace wasm
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 6e7ef3301..8410cc0b2 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -389,7 +389,7 @@ void FunctionValidator::noteLabelName(Name name) {
 
 void FunctionValidator::visitBlock(Block* curr) {
   if (!getModule()->features.hasMultivalue()) {
-    shouldBeTrue(!curr->type.isMulti(),
+    shouldBeTrue(!curr->type.isTuple(),
                  curr,
                  "Multivalue block type (multivalue is not enabled)");
   }
@@ -1773,11 +1773,11 @@ void FunctionValidator::visitSelect(Select* curr) {
                "select condition must be valid");
   if (curr->ifTrue->type != Type::unreachable) {
     shouldBeFalse(
-      curr->ifTrue->type.isMulti(), curr, "select value may not be a tuple");
+      curr->ifTrue->type.isTuple(), curr, "select value may not be a tuple");
   }
   if (curr->ifFalse->type != Type::unreachable) {
     shouldBeFalse(
-      curr->ifFalse->type.isMulti(), curr, "select value may not be a tuple");
+      curr->ifFalse->type.isTuple(), curr, "select value may not be a tuple");
   }
   if (curr->type != Type::unreachable) {
     shouldBeTrue(Type::isSubType(curr->ifTrue->type, curr->type),
@@ -1969,7 +1969,7 @@ void FunctionValidator::visitTupleExtract(TupleExtract* curr) {
 }
 
 void FunctionValidator::visitFunction(Function* curr) {
-  if (curr->sig.results.isMulti()) {
+  if (curr->sig.results.isTuple()) {
     shouldBeTrue(getModule()->features.hasMultivalue(),
                  curr->body,
                  "Multivalue function results (multivalue is not enabled)");
@@ -2137,7 +2137,7 @@ static void validateBinaryenIR(Module& wasm, ValidationInfo& info) {
 
 static void validateImports(Module& module, ValidationInfo& info) {
   ModuleUtils::iterImportedFunctions(module, [&](Function* curr) {
-    if (curr->sig.results.isMulti()) {
+    if (curr->sig.results.isTuple()) {
       info.shouldBeTrue(module.features.hasMultivalue(),
                         curr->name,
                         "Imported multivalue function "
@@ -2164,7 +2164,7 @@ static void validateImports(Module& module, ValidationInfo& info) {
         curr->mutable_, curr->name, "Imported global cannot be mutable");
     }
     info.shouldBeFalse(
-      curr->type.isMulti(), curr->name, "Imported global cannot be tuple");
+      curr->type.isTuple(), curr->name, "Imported global cannot be tuple");
   });
 }
 
@@ -2194,7 +2194,7 @@ static void validateExports(Module& module, ValidationInfo& info) {
             g->mutable_, g->name, "Exported global cannot be mutable");
         }
         info.shouldBeFalse(
-          g->type.isMulti(), g->name, "Exported global cannot be tuple");
+          g->type.isTuple(), g->name, "Exported global cannot be tuple");
       }
     }
   }
@@ -2347,7 +2347,7 @@ static void validateEvents(Module& module, ValidationInfo& info) {
                        Type(Type::none),
                        curr->name,
                        "Event type's result type should be none");
-    if (curr->sig.params.isMulti()) {
+    if (curr->sig.params.isTuple()) {
       info.shouldBeTrue(module.features.hasMultivalue(),
                         curr->name,
                         "Multivalue event type (multivalue is not enabled)");