diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/wasm-type.h | 210 | ||||
| -rw-r--r-- | src/wasm/wasm-type.cpp | 364 |
2 files changed, 139 insertions, 435 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 |