diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/wasm-type.h | 188 | ||||
| -rw-r--r-- | src/wasm/wasm-binary.cpp | 64 | ||||
| -rw-r--r-- | src/wasm/wasm-s-parser.cpp | 12 | ||||
| -rw-r--r-- | src/wasm/wasm-type.cpp | 893 |
4 files changed, 633 insertions, 524 deletions
diff --git a/src/wasm-type.h b/src/wasm-type.h index 4d842cdca..0e159b3a9 100644 --- a/src/wasm-type.h +++ b/src/wasm-type.h @@ -32,11 +32,24 @@ namespace wasm { +// The types defined in this file. All of them are small and typically passed by +// value except for `Tuple` and `Struct`, which may own an unbounded amount of +// data. +class Type; +class HeapType; +struct Tuple; +struct Signature; +struct Field; +struct Struct; +struct Array; +struct Rtt; + 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. + // Since `Type` is really just a single integer, it should be passed by value. uintptr_t id; public: @@ -54,29 +67,30 @@ public: anyref, eqref, i31ref, - _last_basic_id = i31ref, }; + static constexpr BasicType _last_basic_type = i31ref; - Type() = default; + Type() : id(none) {} // BasicType can be implicitly upgraded to Type - constexpr Type(BasicType id) : id(id){}; + constexpr Type(BasicType id) : id(id) {} - // But converting raw uint32_t is more dangerous, so make it explicit - explicit Type(uint64_t id) : id(id){}; + // But converting raw uint64_t is more dangerous, so make it explicit + explicit Type(uint64_t id) : id(id) {} // Construct tuple from a list of single types Type(std::initializer_list<Type>); // Construct from tuple description - explicit Type(const struct Tuple&); + Type(const Tuple&); + Type(Tuple&&); // Construct from a heap type description. Also covers construction from // Signature, Struct or Array via implicit conversion to HeapType. - explicit Type(const struct HeapType&, bool nullable); + Type(HeapType, bool nullable); // Construct from rtt description - explicit Type(const struct Rtt&); + Type(Rtt); // Predicates // Compound Concrete @@ -102,8 +116,8 @@ public: // │ Tuple ║ │ x │ │ x │ │ // │ Rtt ║ │ x │ x │ x │ │ // └─────────────╨───┴───┴───┴───┴───────┘ - constexpr bool isBasic() const { return id <= _last_basic_id; } - constexpr bool isCompound() const { return id > _last_basic_id; } + constexpr bool isBasic() const { return id <= _last_basic_type; } + constexpr bool isCompound() const { return id > _last_basic_type; } 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; } @@ -143,9 +157,9 @@ public: // 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 BasicType& otherId) const { return id == otherId; } + bool operator==(const BasicType& other) const { return id == other; } bool operator!=(const Type& other) const { return id != other.id; } - bool operator!=(const BasicType& otherId) const { return id != otherId; } + bool operator!=(const BasicType& other) const { return id != other; } // Order types by some notion of simplicity bool operator<(const Type& other) const; @@ -161,7 +175,7 @@ public: FeatureSet getFeatures() const; // Gets the heap type corresponding to this type - const HeapType& getHeapType() const; + HeapType getHeapType() const; // Returns a number type based on its size in bytes and whether it is a float // type. @@ -254,17 +268,90 @@ struct ResultType { std::string toString() const; }; +class HeapType { + // Unlike `Type`, which represents the types of values on the WebAssembly + // stack, `HeapType` is used to describe the structures that reference types + // refer to. HeapTypes are canonicalized and interned exactly like Types and + // should also be passed by value. + uintptr_t id; + +public: + enum BasicHeapType : uint32_t { + func, + ext, + exn, + any, + eq, + i31, + }; + static constexpr BasicHeapType _last_basic_type = i31; + + // BasicHeapType can be implicitly upgraded to HeapType + constexpr HeapType(BasicHeapType id) : id(id) {} + + // But converting raw uint64_t is more dangerous, so make it explicit + explicit HeapType(uint64_t id) : id(id) {} + + HeapType(Signature signature); + HeapType(const Struct& struct_); + HeapType(Struct&& struct_); + HeapType(Array array); + + constexpr bool isBasic() const { return id <= _last_basic_type; } + constexpr bool isCompound() const { return id > _last_basic_type; } + bool isFunction() const; + bool isSignature() const; + bool isStruct() const; + bool isArray() const; + + Signature getSignature() const; + const Struct& getStruct() const; + Array getArray() const; + + constexpr uint64_t getID() const { return id; } + constexpr BasicHeapType getBasic() const { + assert(isBasic() && "Basic heap type expected"); + return static_cast<BasicHeapType>(id); + } + + // (In)equality must be defined for both HeapType and BasicHeapType because it + // is otherwise ambiguous whether to convert both this and other to int or + // convert other to HeapType. + bool operator==(const HeapType& other) const { return id == other.id; } + bool operator==(const BasicHeapType& other) const { return id == other; } + bool operator!=(const HeapType& other) const { return id != other.id; } + bool operator!=(const BasicHeapType& other) const { return id != other; } + + bool operator<(const HeapType& other) const; + std::string toString() const; +}; + typedef std::vector<Type> TypeList; +// Passed by reference rather than by value because it can own an unbounded +// amount of data. 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)) {} + Tuple(std::initializer_list<Type> types) : types(types) { validate(); } + Tuple(const TypeList& types) : types(types) { validate(); } + Tuple(TypeList&& types) : types(std::move(types)) { validate(); } bool operator==(const Tuple& other) const { return types == other.types; } bool operator!=(const Tuple& other) const { return !(*this == other); } + bool operator<(const Tuple& other) const { return types < other.types; } std::string toString() const; + + // Prevent accidental copies + Struct& operator=(const Struct&) = delete; + +private: + void validate() { +#ifndef NDEBUG + for (auto type : types) { + assert(type.isSingle()); + } +#endif + } }; struct Signature { @@ -316,6 +403,8 @@ struct Field { typedef std::vector<Field> FieldList; +// Passed by reference rather than by value because it can own an unbounded +// amount of data. struct Struct { FieldList fields; Struct(const Struct& other) : fields(other.fields) {} @@ -325,85 +414,30 @@ struct Struct { bool operator!=(const Struct& other) const { return !(*this == other); } bool operator<(const Struct& other) const { return fields < other.fields; } std::string toString() const; + + // Prevent accidental copies + Struct& operator=(const Struct&) = delete; }; struct Array { Field element; Array(const Array& other) : element(other.element) {} - Array(const Field& element) : element(element) {} - Array(Field&& element) : element(std::move(element)) {} + Array(Field element) : element(element) {} bool operator==(const Array& other) const { return element == other.element; } bool operator!=(const Array& other) const { return !(*this == other); } bool operator<(const Array& other) const { return element < other.element; } std::string toString() const; }; -struct HeapType { - enum Kind { - FuncKind, - ExternKind, - ExnKind, - AnyKind, - EqKind, - I31Kind, - _last_basic_kind = I31Kind, - SignatureKind, - StructKind, - ArrayKind, - } kind; - union { - Signature signature; - Struct struct_; - Array array; - }; - HeapType(Kind kind) : kind(kind) { assert(kind <= _last_basic_kind); } - HeapType(const Signature& signature) - : kind(SignatureKind), signature(signature) {} - HeapType(Signature&& signature) - : kind(SignatureKind), signature(std::move(signature)) {} - HeapType(const Struct& struct_) : kind(StructKind), struct_(struct_) {} - HeapType(Struct&& struct_) : kind(StructKind), struct_(std::move(struct_)) {} - HeapType(const Array& array) : kind(ArrayKind), array(array) {} - HeapType(Array&& array) : kind(ArrayKind), array(std::move(array)) {} - HeapType(const HeapType& other); - ~HeapType(); - - bool isBasic() const { return kind <= _last_basic_kind; } - bool isSignature() const { return kind == SignatureKind; } - Signature getSignature() const { - assert(isSignature() && "Not a signature"); - return signature; - } - bool isStruct() const { return kind == StructKind; } - const Struct& getStruct() const { - assert(isStruct() && "Not a struct"); - return struct_; - } - bool isArray() const { return kind == ArrayKind; } - const Array& getArray() const { - assert(isArray() && "Not an array"); - return array; - } - bool isException() const { return kind == ExnKind; } - - bool operator==(const HeapType& other) const; - bool operator!=(const HeapType& other) const { return !(*this == other); } - bool operator<(const HeapType& other) const; - HeapType& operator=(const HeapType& other); - std::string toString() const; -}; - struct Rtt { uint32_t depth; HeapType heapType; - Rtt(uint32_t depth, const HeapType& heapType) - : depth(depth), heapType(heapType) {} - Rtt(uint32_t depth, HeapType&& heapType) - : depth(depth), heapType(std::move(heapType)) {} + Rtt(uint32_t depth, HeapType heapType) : depth(depth), heapType(heapType) {} bool operator==(const Rtt& other) const { return depth == other.depth && heapType == other.heapType; } bool operator!=(const Rtt& other) const { return !(*this == other); } + bool operator<(const Rtt& other) const; std::string toString() const; }; 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 |