diff options
44 files changed, 194 insertions, 1501 deletions
diff --git a/CHANGELOG.md b/CHANGELOG.md index 0072b18d0..1fe30bdff 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -16,7 +16,8 @@ Current Trunk ------------- - The isorecursive WasmGC type system (i.e. --hybrid) is now the default to - match the spec. + match the spec and the old default equirecursive (i.e. --structural) system + has been removed. v111 ---- diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp index e28b9fb77..e3d1505fa 100644 --- a/src/binaryen-c.cpp +++ b/src/binaryen-c.cpp @@ -408,9 +408,6 @@ BinaryenType BinaryenTypeFromHeapType(BinaryenHeapType heapType, // TypeSystem -BinaryenTypeSystem BinaryenTypeSystemEquirecursive() { - return static_cast<BinaryenTypeSystem>(TypeSystem::Equirecursive); -} BinaryenTypeSystem BinaryenTypeSystemNominal() { return static_cast<BinaryenTypeSystem>(TypeSystem::Nominal); } diff --git a/src/binaryen-c.h b/src/binaryen-c.h index 8da248f07..c9331d49d 100644 --- a/src/binaryen-c.h +++ b/src/binaryen-c.h @@ -192,7 +192,6 @@ BINARYEN_API BinaryenType BinaryenTypeFromHeapType(BinaryenHeapType heapType, typedef uint32_t BinaryenTypeSystem; -BINARYEN_API BinaryenTypeSystem BinaryenTypeSystemEquirecursive(void); BINARYEN_API BinaryenTypeSystem BinaryenTypeSystemNominal(void); BINARYEN_API BinaryenTypeSystem BinaryenTypeSystemIsorecursive(void); BINARYEN_API BinaryenTypeSystem BinaryenGetTypeSystem(void); diff --git a/src/ir/module-utils.cpp b/src/ir/module-utils.cpp index c10a45b15..22f07a2e8 100644 --- a/src/ir/module-utils.cpp +++ b/src/ir/module-utils.cpp @@ -214,24 +214,6 @@ IndexedHeapTypes getOptimizedIndexedHeapTypes(Module& wasm) { TypeSystem system = getTypeSystem(); Counts counts = getHeapTypeCounts(wasm); - if (system == TypeSystem::Equirecursive) { - // Sort by frequency and then original insertion order. - std::vector<std::pair<HeapType, size_t>> sorted(counts.begin(), - counts.end()); - std::stable_sort(sorted.begin(), sorted.end(), [&](auto a, auto b) { - return a.second > b.second; - }); - - // Collect the results. - IndexedHeapTypes indexedTypes; - for (Index i = 0; i < sorted.size(); ++i) { - indexedTypes.types.push_back(sorted[i].first); - } - - setIndices(indexedTypes); - return indexedTypes; - } - // Types have to be arranged into topologically ordered recursion groups. // Under isorecrsive typing, the topological sort has to take all referenced // rec groups into account but under nominal typing it only has to take @@ -285,9 +267,6 @@ IndexedHeapTypes getOptimizedIndexedHeapTypes(Module& wasm) { info.preds.insert(super->getRecGroup()); } break; - case TypeSystem::Equirecursive: - WASM_UNREACHABLE( - "Equirecursive types should already have been handled"); } } diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp index 0284101ed..7ed6bfde6 100644 --- a/src/ir/possible-contents.cpp +++ b/src/ir/possible-contents.cpp @@ -488,12 +488,6 @@ struct InfoCollector } } } - if (type.isRef() && getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive) { - // We need explicit supers in the SubTyping helper class. Without that, - // cannot handle refs, and consider them irrelevant. - return false; - } return true; } @@ -1582,11 +1576,8 @@ Flower::Flower(Module& wasm) : wasm(wasm) { std::cout << "struct phase\n"; #endif - if (getTypeSystem() == TypeSystem::Nominal || - getTypeSystem() == TypeSystem::Isorecursive) { - subTypes = std::make_unique<SubTypes>(wasm); - maxDepths = subTypes->getMaxDepths(); - } + subTypes = std::make_unique<SubTypes>(wasm); + maxDepths = subTypes->getMaxDepths(); #ifdef POSSIBLE_CONTENTS_DEBUG std::cout << "Link-targets phase\n"; diff --git a/src/ir/subtypes.h b/src/ir/subtypes.h index 198a69b7a..bc14c1d4f 100644 --- a/src/ir/subtypes.h +++ b/src/ir/subtypes.h @@ -29,10 +29,6 @@ namespace wasm { // This only scans user types, and not basic types like HeapType::eq. struct SubTypes { SubTypes(const std::vector<HeapType>& types) : types(types) { - if (getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive) { - Fatal() << "SubTypes requires explicit supers"; - } for (auto type : types) { note(type); } diff --git a/src/passes/ConstantFieldPropagation.cpp b/src/passes/ConstantFieldPropagation.cpp index 5048b978b..c5b95b15a 100644 --- a/src/passes/ConstantFieldPropagation.cpp +++ b/src/passes/ConstantFieldPropagation.cpp @@ -187,10 +187,6 @@ struct ConstantFieldPropagation : public Pass { if (!module->features.hasGC()) { return; } - if (getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive) { - Fatal() << "CFP requires nominal/isorecursive typing"; - } // Find and analyze all writes inside each function. PCVFunctionStructValuesMap functionNewInfos(*module), diff --git a/src/passes/GUFA.cpp b/src/passes/GUFA.cpp index 9774c1bb7..4250c76e9 100644 --- a/src/passes/GUFA.cpp +++ b/src/passes/GUFA.cpp @@ -110,13 +110,6 @@ struct GUFAOptimizer return; } - if (type.isRef() && (getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive)) { - // Without type info we can't analyze subtypes, so we cannot infer - // anything about refs. - return; - } - // Ok, this is an interesting location that we might optimize. See what the // oracle says is possible there. auto contents = getContents(curr); diff --git a/src/passes/GlobalRefining.cpp b/src/passes/GlobalRefining.cpp index f994d4082..0576e3285 100644 --- a/src/passes/GlobalRefining.cpp +++ b/src/passes/GlobalRefining.cpp @@ -38,10 +38,6 @@ struct GlobalRefining : public Pass { if (!module->features.hasGC()) { return; } - if (getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive) { - Fatal() << "GlobalRefining requires nominal/isorecursive typing"; - } // First, find all the global.sets. diff --git a/src/passes/GlobalStructInference.cpp b/src/passes/GlobalStructInference.cpp index 8bb4c0ba9..938350960 100644 --- a/src/passes/GlobalStructInference.cpp +++ b/src/passes/GlobalStructInference.cpp @@ -71,10 +71,6 @@ struct GlobalStructInference : public Pass { if (!module->features.hasGC()) { return; } - if (getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive) { - Fatal() << "GlobalStructInference requires nominal/isorecursive typing"; - } // First, find all the information we need. We need to know which struct // types are created in functions, because we will not be able to optimize diff --git a/src/passes/GlobalTypeOptimization.cpp b/src/passes/GlobalTypeOptimization.cpp index 95d8859e9..4f7ce7ac7 100644 --- a/src/passes/GlobalTypeOptimization.cpp +++ b/src/passes/GlobalTypeOptimization.cpp @@ -117,10 +117,6 @@ struct GlobalTypeOptimization : public Pass { if (!module->features.hasGC()) { return; } - if (getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive) { - Fatal() << "GlobalTypeOptimization requires nominal/isorecursive typing"; - } // Find and analyze struct operations inside each function. StructUtils::FunctionStructValuesMap<FieldInfo> functionNewInfos(*module), diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp index a92b0a16a..d9e54b054 100644 --- a/src/passes/Print.cpp +++ b/src/passes/Print.cpp @@ -3034,9 +3034,7 @@ struct PrintSExpression : public UnifiedExpressionVisitor<PrintSExpression> { o << '('; printMajor(o, "func "); printName(curr->name, o); - if (currModule && currModule->features.hasGC() && - (getTypeSystem() == TypeSystem::Nominal || - getTypeSystem() == TypeSystem::Isorecursive)) { + if (currModule && currModule->features.hasGC()) { o << " (type "; printHeapType(o, curr->type, currModule) << ')'; } diff --git a/src/passes/SignaturePruning.cpp b/src/passes/SignaturePruning.cpp index e6a7aa44e..3244ee103 100644 --- a/src/passes/SignaturePruning.cpp +++ b/src/passes/SignaturePruning.cpp @@ -52,10 +52,6 @@ struct SignaturePruning : public Pass { if (!module->features.hasGC()) { return; } - if (getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive) { - Fatal() << "SignaturePruning requires nominal/isorecursive typing"; - } if (!module->tables.empty()) { // When there are tables we must also take their types into account, which diff --git a/src/passes/SignatureRefining.cpp b/src/passes/SignatureRefining.cpp index 488e2c6cc..132079b76 100644 --- a/src/passes/SignatureRefining.cpp +++ b/src/passes/SignatureRefining.cpp @@ -54,10 +54,6 @@ struct SignatureRefining : public Pass { if (!module->features.hasGC()) { return; } - if (getTypeSystem() != TypeSystem::Nominal && - getTypeSystem() != TypeSystem::Isorecursive) { - Fatal() << "SignatureRefining requires nominal/hybrid typing"; - } if (!module->tables.empty()) { // When there are tables we must also take their types into account, which diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 9643b489e..9daf8e1d3 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -593,10 +593,7 @@ void PassRunner::addDefaultGlobalOptimizationPrePasses() { if (options.optimizeLevel >= 2) { addIfNoDWARFIssues("once-reduction"); } - if (wasm->features.hasGC() && - (getTypeSystem() == TypeSystem::Nominal || - getTypeSystem() == TypeSystem::Isorecursive) && - options.optimizeLevel >= 2) { + if (wasm->features.hasGC() && options.optimizeLevel >= 2) { addIfNoDWARFIssues("type-refining"); addIfNoDWARFIssues("signature-pruning"); addIfNoDWARFIssues("signature-refining"); diff --git a/src/tools/tool-options.h b/src/tools/tool-options.h index eb5212c84..0522b5538 100644 --- a/src/tools/tool-options.h +++ b/src/tools/tool-options.h @@ -148,15 +148,6 @@ struct ToolOptions : public Options { [](Options* o, const std::string& argument) { setTypeSystem(TypeSystem::Nominal); }) - .add("--structural", - "", - "Force all GC type definitions to be parsed as structural " - "(i.e. equirecursive). This is the default.", - ToolOptionsCategory, - Options::Arguments::Zero, - [](Options* o, const std::string& argument) { - setTypeSystem(TypeSystem::Equirecursive); - }) .add("--hybrid", "", "Force all GC type definitions to be parsed using the isorecursive " @@ -196,9 +187,7 @@ struct ToolOptions : public Options { void applyFeatures(Module& module) const { module.features.enable(enabledFeatures); module.features.disable(disabledFeatures); - // Non-default type systems only make sense with GC enabled. TODO: Error on - // non-GC equirecursive types as well once we make isorecursive the default - // if we don't remove equirecursive types entirely. + // Non-default type systems only make sense with GC enabled. if (!module.features.hasGC() && getTypeSystem() == TypeSystem::Nominal) { Fatal() << "Nominal typing is only allowed when GC is enabled"; } diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp index bbf4967e3..0e40e7a15 100644 --- a/src/tools/wasm-fuzz-types.cpp +++ b/src/tools/wasm-fuzz-types.cpp @@ -517,25 +517,17 @@ int main(int argc, const char* argv[]) { Options::Arguments::Zero, [&](Options*, const std::string& arg) { verbose = true; }); - TypeSystem system = TypeSystem::Nominal; + TypeSystem system = TypeSystem::Isorecursive; options.add( "--nominal", "", - "Use the nominal type system (default)", + "Use the nominal type system", WasmFuzzTypesOption, Options::Arguments::Zero, [&](Options*, const std::string& arg) { system = TypeSystem::Nominal; }); - options.add("--structural", - "", - "Use the equirecursive type system", - WasmFuzzTypesOption, - Options::Arguments::Zero, - [&](Options*, const std::string& arg) { - system = TypeSystem::Equirecursive; - }); options.add("--hybrid", "", - "Use the isorecursive hybrid type system", + "Use the isorecursive hybrid type system (default)", WasmFuzzTypesOption, Options::Arguments::Zero, [&](Options*, const std::string& arg) { diff --git a/src/tools/wasm-reduce.cpp b/src/tools/wasm-reduce.cpp index eec1e0874..d92e0a93c 100644 --- a/src/tools/wasm-reduce.cpp +++ b/src/tools/wasm-reduce.cpp @@ -1293,9 +1293,10 @@ int main(int argc, const char* argv[]) { } if (getTypeSystem() == TypeSystem::Nominal) { extraFlags += " --nominal"; - } - if (getTypeSystem() == TypeSystem::Isorecursive) { + } else if (getTypeSystem() == TypeSystem::Isorecursive) { extraFlags += " --hybrid"; + } else { + WASM_UNREACHABLE("unexpected type system"); } if (test.size() == 0) { diff --git a/src/wasm-type.h b/src/wasm-type.h index fa365b0e5..140fcf893 100644 --- a/src/wasm-type.h +++ b/src/wasm-type.h @@ -41,9 +41,8 @@ namespace wasm { enum class TypeSystem { - Equirecursive, - Nominal, Isorecursive, + Nominal, }; // This should only ever be called before any Types or HeapTypes have been diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp index 3cceaef46..c2a7dfff3 100644 --- a/src/wasm/wasm-binary.cpp +++ b/src/wasm/wasm-binary.cpp @@ -232,12 +232,9 @@ void WasmBinaryWriter::writeTypes() { // MVP types are structural and do not use recursion groups. TypeSystem typeSystem = getTypeSystem(); if (!wasm->features.hasGC()) { - typeSystem = TypeSystem::Equirecursive; + typeSystem = TypeSystem::Isorecursive; } switch (typeSystem) { - case TypeSystem::Equirecursive: - numGroups = indexedTypes.types.size(); - break; case TypeSystem::Nominal: numGroups = 1; break; @@ -2191,9 +2188,6 @@ void WasmBinaryBuilder::readTypes() { auto form = getS32LEB(); if (form == BinaryConsts::EncodedType::Rec) { uint32_t groupSize = getU32LEB(); - if (getTypeSystem() == TypeSystem::Equirecursive) { - throwError("Recursion groups not allowed with equirecursive typing"); - } if (groupSize == 0u) { // TODO: Support groups of size zero by shrinking the builder. throwError("Recursion groups of size zero not supported"); diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp index da40bb10e..284d6d7d6 100644 --- a/src/wasm/wasm-type.cpp +++ b/src/wasm/wasm-type.cpp @@ -151,9 +151,6 @@ struct HeapTypeInfo { // Helper for coinductively checking whether a pair of Types or HeapTypes are in // a subtype relation. struct SubTyper { - // Set of HeapTypes we are assuming are equivalent as long as we cannot prove - // otherwise. - std::unordered_set<std::pair<HeapType, HeapType>> seen; bool isSubType(Type a, Type b); bool isSubType(HeapType a, HeapType b); bool isSubType(const Tuple& a, const Tuple& b); @@ -164,36 +161,8 @@ struct SubTyper { }; // Helper for finding the equirecursive least upper bound of two types. -struct TypeBounder { - TypeBuilder builder; - // The indices in `builder` at which the LUB of each pair of HeapTypes are - // being constructed. - std::unordered_map<std::pair<HeapType, HeapType>, size_t> indices; - - bool hasLeastUpperBound(Type a, Type b); - Type getLeastUpperBound(Type a, Type b); - std::optional<HeapType> getLeastUpperBound(HeapType a, HeapType b); - -private: - // Return the LUB iff a LUB was found. The HeapType and Struct overloads are - // exceptional because they are infallible; HeapType::any is an upper bound of - // all HeapTypes and the empty struct is an upper bound of all struct types. - // Note that these methods can return temporary types, so they should never be - // used directly. - std::optional<Type> lub(Type a, Type b); - std::optional<HeapType> lub(HeapType a, HeapType b); - std::optional<Tuple> lub(const Tuple& a, const Tuple& b); - std::optional<Field> lub(const Field& a, const Field& b); - std::optional<Signature> lub(const Signature& a, const Signature& b); - Struct lub(const Struct& a, const Struct& b); - std::optional<Array> lub(const Array& a, const Array& b); -}; - // Helper for printing types. struct TypePrinter { - // Whether to print explicit supertypes. - bool printSupertypes; - // The stream we are printing to. std::ostream& os; @@ -204,8 +173,7 @@ struct TypePrinter { HeapTypeNameGenerator generator; TypePrinter(std::ostream& os, HeapTypeNameGenerator generator) - : printSupertypes(getTypeSystem() != TypeSystem::Equirecursive), os(os), - defaultGenerator(), generator(generator) {} + : os(os), defaultGenerator(), generator(generator) {} TypePrinter(std::ostream& os) : TypePrinter( os, [&](HeapType type) { return defaultGenerator->getNames(type); }) { @@ -213,7 +181,6 @@ struct TypePrinter { } void printHeapTypeName(HeapType type); - void printSupertypeOr(std::optional<HeapType> super, std::string other); std::ostream& print(Type type); std::ostream& print(HeapType type); @@ -227,54 +194,6 @@ struct TypePrinter { std::optional<HeapType> super = std::nullopt); }; -// Helper for hashing the shapes of TypeInfos and HeapTypeInfos. Keeps track of -// previously seen HeapTypes to avoid traversing them more than once. Infos -// referring to different type IDs but sharing a finite shape will compare and -// hash the same. -struct FiniteShapeHasher { - bool topLevelOnly; - size_t currDepth = 0; - size_t currStep = 0; - std::unordered_map<HeapType, size_t> seen; - - FiniteShapeHasher(bool topLevelOnly = false) : topLevelOnly(topLevelOnly) {} - - size_t hash(Type type); - size_t hash(HeapType heapType); - size_t hash(const TypeInfo& info); - size_t hash(const HeapTypeInfo& info); - size_t hash(const Tuple& tuple); - size_t hash(const Field& field); - size_t hash(const Signature& sig); - size_t hash(const Struct& struct_); - size_t hash(const Array& array); -}; - -// Helper for comparing the shapes of TypeInfos and HeapTypeInfos for equality. -// Like FiniteShapeHasher, keeps track of previously seen HeapTypes. Note that -// this does not test for coinductive equality of the infinite expansion of the -// type tree, but rather tests for equality of the finite shape of the graph. If -// FiniteShapeEquator reports that two type shapes are equal, FiniteShapeHasher -// should produce the same hash for them. -struct FiniteShapeEquator { - bool topLevelOnly; - size_t currDepth = 0; - size_t currStep = 0; - std::unordered_map<HeapType, size_t> seenA, seenB; - - FiniteShapeEquator(bool topLevelOnly = false) : topLevelOnly(topLevelOnly) {} - - bool eq(Type a, Type b); - bool eq(HeapType a, HeapType b); - bool eq(const TypeInfo& a, const TypeInfo& b); - bool eq(const HeapTypeInfo& a, const HeapTypeInfo& b); - bool eq(const Tuple& a, const Tuple& b); - bool eq(const Field& a, const Field& b); - bool eq(const Signature& a, const Signature& b); - bool eq(const Struct& a, const Struct& b); - bool eq(const Array& a, const Array& b); -}; - struct RecGroupHasher { // `group` may or may not be canonical, but any other recursion group it // reaches must be canonical. @@ -733,7 +652,7 @@ HeapTypeInfo& HeapTypeInfo::operator=(const HeapTypeInfo& other) { } bool HeapTypeInfo::operator==(const HeapTypeInfo& other) const { - return FiniteShapeEquator().eq(*this, other); + return this == &other; } template<typename Info> struct Store { @@ -1203,9 +1122,6 @@ std::vector<HeapType> Type::getHeapTypeChildren() { } bool Type::hasLeastUpperBound(Type a, Type b) { - if (getTypeSystem() == TypeSystem::Equirecursive) { - return TypeBounder().hasLeastUpperBound(a, b); - } return getLeastUpperBound(a, b) != Type::none; } @@ -1213,9 +1129,6 @@ Type Type::getLeastUpperBound(Type a, Type b) { if (a == b) { return a; } - if (getTypeSystem() == TypeSystem::Equirecursive) { - return TypeBounder().getLeastUpperBound(a, b); - } if (a == Type::unreachable) { return b; } @@ -1285,9 +1198,6 @@ HeapType::HeapType(Signature sig) { // signature to emulate structural behavior. new (this) HeapType(nominalSignatureCache.getType(sig)); return; - case TypeSystem::Equirecursive: - new (this) HeapType(globalHeapTypeStore.insert(sig)); - return; case TypeSystem::Isorecursive: new (this) HeapType( globalRecGroupStore.insert(std::make_unique<HeapTypeInfo>(sig))); @@ -1304,7 +1214,6 @@ HeapType::HeapType(const Struct& struct_) { #endif switch (getTypeSystem()) { case TypeSystem::Nominal: - case TypeSystem::Equirecursive: new (this) HeapType(globalHeapTypeStore.insert(struct_)); return; case TypeSystem::Isorecursive: @@ -1323,7 +1232,6 @@ HeapType::HeapType(Struct&& struct_) { #endif switch (getTypeSystem()) { case TypeSystem::Nominal: - case TypeSystem::Equirecursive: new (this) HeapType(globalHeapTypeStore.insert(std::move(struct_))); return; case TypeSystem::Isorecursive: @@ -1338,7 +1246,6 @@ HeapType::HeapType(Array array) { assert(!isTemp(array.element.type) && "Leaking temporary type!"); switch (getTypeSystem()) { case TypeSystem::Nominal: - case TypeSystem::Equirecursive: new (this) HeapType(globalHeapTypeStore.insert(array)); return; case TypeSystem::Isorecursive: @@ -1561,9 +1468,6 @@ std::optional<HeapType> HeapType::getLeastUpperBound(HeapType a, HeapType b) { if (b.isBottom()) { return a; } - if (getTypeSystem() == TypeSystem::Equirecursive) { - return TypeBounder().getLeastUpperBound(a, b); - } if (a.isBasic() || b.isBasic()) { return getBasicHeapTypeLUB(getBasicHeapSupertype(a), getBasicHeapSupertype(b)); @@ -1793,34 +1697,13 @@ bool SubTyper::isSubType(HeapType a, HeapType b) { // bottom types. return a == b.getBottom(); } - if (typeSystem == TypeSystem::Nominal || - typeSystem == TypeSystem::Isorecursive) { - // Subtyping must be declared in a nominal system, not derived from - // structure, so we will not recurse. TODO: optimize this search with some - // form of caching. - HeapTypeInfo* curr = getHeapTypeInfo(a); - while ((curr = curr->supertype)) { - if (curr == getHeapTypeInfo(b)) { - return true; - } + // Subtyping must be declared rather than derived from structure, so we will + // not recurse. TODO: optimize this search with some form of caching. + HeapTypeInfo* curr = getHeapTypeInfo(a); + while ((curr = curr->supertype)) { + if (curr == getHeapTypeInfo(b)) { + return true; } - return false; - } - // As we recurse, we will coinductively assume that a == b unless proven - // otherwise. - if (!seen.insert({a, b}).second) { - // We weren't able to disprove that a == b since we last saw them, so the - // relation holds coinductively. - return true; - } - if (a.isSignature() && b.isSignature()) { - return isSubType(a.getSignature(), b.getSignature()); - } - if (a.isArray() && b.isArray()) { - return isSubType(a.getArray(), b.getArray()); - } - if (a.isStruct() && b.isStruct()) { - return isSubType(a.getStruct(), b.getStruct()); } return false; } @@ -1870,212 +1753,6 @@ bool SubTyper::isSubType(const Array& a, const Array& b) { return isSubType(a.element, b.element); } -bool TypeBounder::hasLeastUpperBound(Type a, Type b) { return bool(lub(a, b)); } - -Type TypeBounder::getLeastUpperBound(Type a, Type b) { - auto tempLUB = lub(a, b); - if (!tempLUB) { - return Type::none; - } - if (!isTemp(*tempLUB)) { - // The LUB is already canonical, so we're done. - return *tempLUB; - } - // `tempLUB` is a temporary type owned by `builder`. Since TypeBuilder::build - // returns HeapTypes rather than Types, create a new HeapType definition meant - // only to get `tempLUB` canonicalized in a known location. The use of an - // Array is arbitrary; it might as well have been a Struct. - builder.grow(1); - builder[builder.size() - 1] = Array(Field(*tempLUB, Mutable)); - std::vector<HeapType> built = *builder.build(); - return built.back().getArray().element.type; -} - -std::optional<HeapType> TypeBounder::getLeastUpperBound(HeapType a, - HeapType b) { - auto maybeLub = lub(a, b); - if (!maybeLub) { - return std::nullopt; - } - HeapType l = *maybeLub; - if (!isTemp(l)) { - // The LUB is already canonical, so we're done. - return l; - } - // Find the index corresponding to the LUB. - size_t index = 0; - while (l != builder[index]) { - ++index; - } - // Canonicalize and return the LUB. - return (*builder.build())[index]; -} - -std::optional<Type> TypeBounder::lub(Type a, Type b) { - if (a == b) { - return a; - } - if (a == Type::unreachable) { - return b; - } - if (b == Type::unreachable) { - return a; - } - if (a.isTuple() && b.isTuple()) { - auto tuple = lub(a.getTuple(), b.getTuple()); - if (!tuple) { - return {}; - } - return builder.getTempTupleType(*tuple); - } else if (a.isRef() && b.isRef()) { - if (auto heapType = lub(a.getHeapType(), b.getHeapType())) { - auto nullability = - (a.isNullable() || b.isNullable()) ? Nullable : NonNullable; - return builder.getTempRefType(*heapType, nullability); - } - } - return {}; -} - -std::optional<HeapType> TypeBounder::lub(HeapType a, HeapType b) { - if (a == b) { - return a; - } - if (a.getBottom() != b.getBottom()) { - return {}; - } - if (a.isBottom()) { - return b; - } - if (b.isBottom()) { - return a; - } - - if (a.isBasic() || b.isBasic()) { - return getBasicHeapTypeLUB(getBasicHeapSupertype(a), - getBasicHeapSupertype(b)); - } - - HeapTypeInfo* infoA = getHeapTypeInfo(a); - HeapTypeInfo* infoB = getHeapTypeInfo(b); - - if (infoA->kind != infoB->kind) { - return getBasicHeapTypeLUB(getBasicHeapSupertype(a), - getBasicHeapSupertype(b)); - } - - assert(getTypeSystem() == TypeSystem::Equirecursive); - - // Allocate a new slot to construct the LUB of this pair if we have not - // already seen it before. Canonicalize the pair to have the element with the - // smaller ID first since order does not matter. - auto pair = - a.getID() < b.getID() ? std::make_pair(a, b) : std::make_pair(b, a); - size_t index = builder.size(); - auto result = indices.insert({pair, index}); - if (!result.second) { - // We've seen this pair before; stop recursing and do not allocate. - return builder[result.first->second]; - } - - builder.grow(1); - switch (infoA->kind) { - case HeapTypeInfo::BasicKind: - WASM_UNREACHABLE("unexpected kind"); - case HeapTypeInfo::SignatureKind: { - if (auto sig = lub(infoA->signature, infoB->signature)) { - return builder[index] = *sig; - } else { - return builder[index] = HeapType::func; - } - } - case HeapTypeInfo::StructKind: { - return builder[index] = lub(infoA->struct_, infoB->struct_); - } - case HeapTypeInfo::ArrayKind: { - if (auto array = lub(infoA->array, infoB->array)) { - return builder[index] = *array; - } else { - return builder[index] = HeapType::data; - } - } - } - WASM_UNREACHABLE("unexpected kind"); -} - -std::optional<Tuple> TypeBounder::lub(const Tuple& a, const Tuple& b) { - if (a.types.size() != b.types.size()) { - return {}; - } - Tuple result; - result.types.resize(a.types.size()); - for (size_t i = 0; i < a.types.size(); ++i) { - if (auto type = lub(a.types[i], b.types[i])) { - result.types[i] = *type; - } else { - return {}; - } - } - return result; -} - -std::optional<Field> TypeBounder::lub(const Field& a, const Field& b) { - if (a == b) { - return a; - } - // Mutable fields are invariant, so they would have had to be the same. - if (a.mutable_ == Mutable || b.mutable_ == Mutable) { - return {}; - } - // Packed types must match. - if (a.isPacked() != b.isPacked() || - (a.isPacked() && a.packedType != b.packedType)) { - return {}; - } - // Either the packed types match or the types aren't packed. - Type type; - if (auto type = lub(a.type, b.type)) { - Field result = a; - result.type = *type; - return result; - } else { - return {}; - } -} - -std::optional<Signature> TypeBounder::lub(const Signature& a, - const Signature& b) { - // TODO: Implement proper signature subtyping, covariant in results and - // contravariant in params, once V8 implements it. - if (a != b) { - return {}; - } else { - return a; - } -} - -Struct TypeBounder::lub(const Struct& a, const Struct& b) { - Struct result; - size_t numFields = std::min(a.fields.size(), b.fields.size()); - for (size_t i = 0; i < numFields; ++i) { - if (auto field = lub(a.fields[i], b.fields[i])) { - result.fields.push_back(*field); - } else { - // Stop at the common prefix and ignore the rest. - break; - } - } - return result; -} - -std::optional<Array> TypeBounder::lub(const Array& a, const Array& b) { - if (auto elem = lub(a.element, b.element)) { - return Array{*elem}; - } else { - return {}; - } -} - void TypePrinter::printHeapTypeName(HeapType type) { if (type.isBasic()) { print(type); @@ -2084,15 +1761,6 @@ void TypePrinter::printHeapTypeName(HeapType type) { os << '$' << generator(type).name; } -void TypePrinter::printSupertypeOr(std::optional<HeapType> super, - std::string other) { - if (super) { - printHeapTypeName(*super); - } else { - os << other; - } -} - std::ostream& TypePrinter::print(Type type) { if (type.isBasic()) { switch (type.getBasic()) { @@ -2270,7 +1938,7 @@ std::ostream& TypePrinter::print(const Signature& sig, }; os << "(func"; - if (printSupertypes) { + if (super) { os << "_subtype"; } if (sig.params.getID() != Type::none) { @@ -2281,9 +1949,9 @@ std::ostream& TypePrinter::print(const Signature& sig, os << ' '; printPrefixed("result", sig.results); } - if (printSupertypes) { + if (super) { os << ' '; - printSupertypeOr(super, "func"); + printHeapTypeName(*super); } return os << ')'; } @@ -2291,7 +1959,7 @@ std::ostream& TypePrinter::print(const Signature& sig, std::ostream& TypePrinter::print(const Struct& struct_, std::optional<HeapType> super) { os << "(struct"; - if (printSupertypes) { + if (super) { os << "_subtype"; } if (struct_.fields.size()) { @@ -2304,9 +1972,9 @@ std::ostream& TypePrinter::print(const Struct& struct_, if (struct_.fields.size()) { os << ')'; } - if (printSupertypes) { + if (super) { os << ' '; - printSupertypeOr(super, "data"); + printHeapTypeName(*super); } return os << ')'; } @@ -2314,230 +1982,18 @@ std::ostream& TypePrinter::print(const Struct& struct_, std::ostream& TypePrinter::print(const Array& array, std::optional<HeapType> super) { os << "(array"; - if (printSupertypes) { + if (super) { os << "_subtype"; } os << ' '; print(array.element); - if (printSupertypes) { + if (super) { os << ' '; - printSupertypeOr(super, "data"); + printHeapTypeName(*super); } return os << ')'; } -size_t FiniteShapeHasher::hash(Type type) { - size_t digest = wasm::hash(type.isBasic()); - if (type.isBasic()) { - rehash(digest, type.getID()); - } else { - hash_combine(digest, hash(*getTypeInfo(type))); - } - return digest; -} - -size_t FiniteShapeHasher::hash(HeapType heapType) { - size_t digest = wasm::hash(heapType.isBasic()); - if (heapType.isBasic()) { - rehash(digest, heapType.getID()); - return digest; - } - if (topLevelOnly && currDepth > 0) { - return digest; - } - auto it = seen.find(heapType); - rehash(digest, it != seen.end()); - if (it != seen.end()) { - rehash(digest, it->second); - return digest; - } - seen[heapType] = ++currStep; - ++currDepth; - hash_combine(digest, hash(*getHeapTypeInfo(heapType))); - --currDepth; - return digest; -} - -size_t FiniteShapeHasher::hash(const TypeInfo& info) { - 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.nullable); - hash_combine(digest, hash(info.ref.heapType)); - return digest; - } - WASM_UNREACHABLE("unexpected kind"); -} - -size_t FiniteShapeHasher::hash(const HeapTypeInfo& info) { - if (getTypeSystem() == TypeSystem::Nominal || - getTypeSystem() == TypeSystem::Isorecursive) { - return wasm::hash(uintptr_t(&info)); - } - // If the HeapTypeInfo is not finalized, then it is mutable and its shape - // might change in the future. In that case, fall back to pointer identity to - // keep the hash consistent until all the TypeBuilder's types are finalized. - size_t digest = wasm::hash(info.isFinalized); - if (!info.isFinalized) { - rehash(digest, uintptr_t(&info)); - return digest; - } - rehash(digest, info.kind); - switch (info.kind) { - case HeapTypeInfo::BasicKind: - WASM_UNREACHABLE("Basic HeapTypeInfo should have been canonicalized"); - case HeapTypeInfo::SignatureKind: - hash_combine(digest, hash(info.signature)); - return digest; - case HeapTypeInfo::StructKind: - hash_combine(digest, hash(info.struct_)); - return digest; - case HeapTypeInfo::ArrayKind: - hash_combine(digest, hash(info.array)); - return digest; - } - WASM_UNREACHABLE("unexpected kind"); -} - -size_t FiniteShapeHasher::hash(const Tuple& tuple) { - size_t digest = wasm::hash(tuple.types.size()); - for (auto type : tuple.types) { - hash_combine(digest, hash(type)); - } - return digest; -} - -size_t FiniteShapeHasher::hash(const Field& field) { - size_t digest = wasm::hash(field.packedType); - rehash(digest, field.mutable_); - hash_combine(digest, hash(field.type)); - return digest; -} - -size_t FiniteShapeHasher::hash(const Signature& sig) { - size_t digest = hash(sig.params); - hash_combine(digest, hash(sig.results)); - return digest; -} - -size_t FiniteShapeHasher::hash(const Struct& struct_) { - size_t digest = wasm::hash(struct_.fields.size()); - for (const auto& field : struct_.fields) { - hash_combine(digest, hash(field)); - } - return digest; -} - -size_t FiniteShapeHasher::hash(const Array& array) { - return hash(array.element); -} - -bool FiniteShapeEquator::eq(Type a, Type b) { - if (a.isBasic() != b.isBasic()) { - return false; - } else if (a.isBasic()) { - return a.getID() == b.getID(); - } else { - return eq(*getTypeInfo(a), *getTypeInfo(b)); - } -} - -bool FiniteShapeEquator::eq(HeapType a, HeapType b) { - if (a.isBasic() != b.isBasic()) { - return false; - } else if (a.isBasic()) { - return a.getID() == b.getID(); - } - if (topLevelOnly && currDepth > 0) { - return true; - } - auto itA = seenA.find(a); - auto itB = seenB.find(b); - if ((itA != seenA.end()) != (itB != seenB.end())) { - return false; - } else if (itA != seenA.end()) { - return itA->second == itB->second; - } - seenA[a] = seenB[b] = ++currStep; - ++currDepth; - bool ret = eq(*getHeapTypeInfo(a), *getHeapTypeInfo(b)); - --currDepth; - return ret; -} - -bool FiniteShapeEquator::eq(const TypeInfo& a, const TypeInfo& b) { - 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.nullable == b.ref.nullable && - eq(a.ref.heapType, b.ref.heapType); - } - WASM_UNREACHABLE("unexpected kind"); -} - -bool FiniteShapeEquator::eq(const HeapTypeInfo& a, const HeapTypeInfo& b) { - if (getTypeSystem() == TypeSystem::Nominal || - getTypeSystem() == TypeSystem::Isorecursive) { - return &a == &b; - } - if (a.isFinalized != b.isFinalized) { - return false; - } else if (!a.isFinalized) { - // See comment on corresponding FiniteShapeHasher method. - return &a == &b; - } - if (a.kind != b.kind) { - return false; - } - switch (a.kind) { - case HeapTypeInfo::BasicKind: - WASM_UNREACHABLE("Basic HeapTypeInfo should have been canonicalized"); - case HeapTypeInfo::SignatureKind: - return eq(a.signature, b.signature); - case HeapTypeInfo::StructKind: - return eq(a.struct_, b.struct_); - case HeapTypeInfo::ArrayKind: - return eq(a.array, b.array); - } - WASM_UNREACHABLE("unexpected kind"); -} - -bool FiniteShapeEquator::eq(const Tuple& a, const Tuple& b) { - return std::equal(a.types.begin(), - a.types.end(), - b.types.begin(), - b.types.end(), - [&](const Type& x, const Type& y) { return eq(x, y); }); -} - -bool FiniteShapeEquator::eq(const Field& a, const Field& b) { - return a.packedType == b.packedType && a.mutable_ == b.mutable_ && - eq(a.type, b.type); -} - -bool FiniteShapeEquator::eq(const Signature& a, const Signature& b) { - return eq(a.params, b.params) && eq(a.results, b.results); -} - -bool FiniteShapeEquator::eq(const Struct& a, const Struct& b) { - return std::equal(a.fields.begin(), - a.fields.end(), - b.fields.begin(), - b.fields.end(), - [&](const Field& x, const Field& y) { return eq(x, y); }); -} - -bool FiniteShapeEquator::eq(const Array& a, const Array& b) { - return eq(a.element, b.element); -} - size_t RecGroupHasher::operator()() const { size_t digest = wasm::hash(group.size()); for (auto type : group) { @@ -3125,480 +2581,6 @@ void CanonicalizationState::updateUses(ReplacementMap& replacements, } } -// A wrapper around a HeapType that provides equality and hashing based only on -// its top-level shape, up to but not including its closest HeapType -// descendants. This is the shape that determines the most fine-grained initial -// partitions for DFA minimization and also the shape that determines the -// "alphabet" for transitioning to the child HeapTypes in the DFA view of the -// type definition. -struct ShallowHeapType { - HeapType heapType; - - ShallowHeapType(HeapType heapType) : heapType(heapType) {} - bool operator==(const ShallowHeapType& other) const; -}; - -bool ShallowHeapType::operator==(const ShallowHeapType& other) const { - return FiniteShapeEquator(/*topLevelOnly=*/true) - .eq(this->heapType, other.heapType); -} - -} // anonymous namespace -} // namespace wasm - -namespace std { - -template<> class hash<wasm::ShallowHeapType> { -public: - size_t operator()(const wasm::ShallowHeapType& type) const { - return wasm::FiniteShapeHasher(/*topLevelOnly=*/true).hash(type.heapType); - } -}; - -} // namespace std - -namespace wasm { -namespace { - -// The Refined Partitions data structure used in Valmari-Lehtinen DFA -// minimization. The translation from terms used in the Valmari-Lehtinen paper -// to the more expanded terms used here is: -// -// Block => Set -// elems => elements -// loc => elementIndices -// sidx => setIndices -// first => beginnings -// end => endings -// mid => pivots -// -struct Partitions { - // The number of sets. - size_t sets = 0; - - // The partitioned elements. Elements in the same set are next to each other. - // Within each set, "marked" elements come first followed by "unmarked" - // elements. - std::vector<size_t> elements; - - // Maps elements to their indices in `elements`. - std::vector<size_t> elementIndices; - - // Maps elements to their sets, identified by an index. - std::vector<size_t> setIndices; - - // Maps sets to the indices of their first elements in `elements`. - std::vector<size_t> beginnings; - - // Maps sets to (one past) the indices of their ends in `elements`. - std::vector<size_t> endings; - - // Maps sets to the indices of their first unmarked elements in `elements`. - std::vector<size_t> pivots; - - Partitions() = default; - - // Allocate space up front so we never need to re-allocate. The actual - // contents of all the vectors will need to be externally initialized, - // though. - Partitions(size_t size) - : elements(size), elementIndices(size), setIndices(size), beginnings(size), - endings(size), pivots(size) {} - - struct Set { - using Iterator = std::vector<size_t>::iterator; - - Partitions& partitions; - size_t index; - - Set(Partitions& partitions, size_t index) - : partitions(partitions), index(index) {} - - Iterator begin() { - return partitions.elements.begin() + partitions.beginnings[index]; - } - Iterator end() { - return partitions.elements.begin() + partitions.endings[index]; - } - size_t size() { - return partitions.endings[index] - partitions.beginnings[index]; - } - - bool hasMarks() { - return partitions.pivots[index] != partitions.beginnings[index]; - } - - // Split the set between marked and unmarked elements if there are both - // marked and unmarked elements. Unmark all elements of this set regardless. - // Return the index of the new partition or 0 if there was no split. - size_t split(); - }; - - Set getSet(size_t index) { return {*this, index}; } - - // Returns the set containing an element, which can be iterated upon. The set - // may be invalidated by calls to `mark` or `Set::split`. - Set getSetForElem(size_t element) { return getSet(setIndices[element]); } - - void mark(size_t element) { - size_t index = elementIndices[element]; - size_t set = setIndices[element]; - size_t pivot = pivots[set]; - if (index >= pivot) { - // Move the pivot element into the location of the newly marked element. - elements[index] = elements[pivot]; - elementIndices[elements[index]] = index; - // Move the newly marked element into the pivot location. - elements[pivot] = element; - elementIndices[element] = pivot; - // Update the pivot index to mark the element. - ++pivots[set]; - } - } -}; - -size_t Partitions::Set::split() { - size_t begin = partitions.beginnings[index]; - size_t end = partitions.endings[index]; - size_t pivot = partitions.pivots[index]; - if (pivot == begin) { - // No elements marked, so there is nothing to do. - return 0; - } - if (pivot == end) { - // All elements were marked, so just unmark them. - partitions.pivots[index] = begin; - return 0; - } - // Create a new set covering the marked region. - size_t newIndex = partitions.sets++; - partitions.beginnings[newIndex] = begin; - partitions.pivots[newIndex] = begin; - partitions.endings[newIndex] = pivot; - for (size_t i = begin; i < pivot; ++i) { - partitions.setIndices[partitions.elements[i]] = newIndex; - } - // Update the old set. The end and pivot are already correct. - partitions.beginnings[index] = pivot; - return newIndex; -} - -// Uses Valmari and Lehtinen's partial DFA minimization algorithm to construct a -// minimal type definition graph from an input graph. See -// https://arxiv.org/pdf/0802.2826.pdf. -struct ShapeCanonicalizer { - // The results of shape canonicalization. - CanonicalizationState::ReplacementMap replacements; - - ShapeCanonicalizer(std::vector<HeapType>& roots); - -private: - // Maps state indices to their underlying HeapTypes and vice versa. - std::vector<HeapType> heapTypes; - std::unordered_map<HeapType, size_t> states; - - // A DFA transition into a state. - struct Transition { - size_t pred; - size_t label; - }; - - // The transitions arranged such that the transitions leading to state `q` are - // `transitions[transitionIndices[q] : transitionIndices[q+1]]`. - std::vector<Transition> transitions; - std::vector<size_t> transitionIndices; - - // The state partitions. - Partitions partitions; - - // The splitters, which are partitions of the input transitions. - Partitions splitters; - - void initialize(std::vector<HeapType>& roots); - void createReplacements(); - - // Return pointers to the non-basic HeapType children of `ht`, including - // BasicKind children. - std::vector<HeapType*> getChildren(HeapType ht); - -#if TRACE_CANONICALIZATION - void dumpPartitions() { - for (size_t set = 0; set < partitions.sets; ++set) { - std::cerr << "Partition " << set << '\n'; - std::cerr << "begin: " << partitions.beginnings[set] - << ", end: " << partitions.endings[set] - << ", pivot: " << partitions.pivots[set] << '\n'; - for (size_t index : partitions.getSet(set)) { - assert(partitions.setIndices[index] == set); - std::cerr << heapTypes[index] << '\n'; - } - std::cerr << '\n'; - } - } -#endif -}; - -ShapeCanonicalizer::ShapeCanonicalizer(std::vector<HeapType>& roots) { -#if TRACE_CANONICALIZATION - std::cerr << "Root HeapTypes:\n"; - for (auto root : roots) { - std::cerr << root << '\n'; - } - std::cerr << '\n'; -#endif - - initialize(roots); - -#if TRACE_CANONICALIZATION - std::cerr << "Initial partitions:\n"; - dumpPartitions(); -#endif - - // The list of splitter partitions that might be able to split states in some - // state partition. Starts out containing all splitter partitions. - std::vector<size_t> potentialSplitters; - potentialSplitters.reserve(splitters.sets); - for (size_t i = 0; i < splitters.sets; ++i) { - potentialSplitters.push_back(i); - } - - while (!potentialSplitters.empty()) { - size_t potentialSplitter = potentialSplitters.back(); - potentialSplitters.pop_back(); - - // The partitions that may be able to be split. - std::vector<size_t> markedPartitions; - - // Mark states that are predecessors via this splitter partition. - for (size_t transition : splitters.getSet(potentialSplitter)) { - size_t state = transitions[transition].pred; - auto partition = partitions.getSetForElem(state); - if (!partition.hasMarks()) { - markedPartitions.push_back(partition.index); - } - partitions.mark(state); - } - - // Try to split each partition with marked states. - for (size_t partition : markedPartitions) { - size_t newPartition = partitions.getSet(partition).split(); - if (!newPartition) { - // There was nothing to split. - continue; - } - - // We only want to keep using the smaller of the two split partitions. - if (partitions.getSet(newPartition).size() < - partitions.getSet(partition).size()) { - newPartition = partition; - } - - // The splitter partitions that may need to be split to match the new - // split of the state partitions. - std::vector<size_t> markedSplitters; - - // Mark transitions that lead to the newly split off states. - for (size_t state : partitions.getSet(newPartition)) { - for (size_t t = transitionIndices[state], - end = transitionIndices[state + 1]; - t < end; - ++t) { - auto splitter = splitters.getSetForElem(t); - if (!splitter.hasMarks()) { - markedSplitters.push_back(splitter.index); - } - splitters.mark(t); - } - } - - // Split the splitters and update `potentialSplitters`. - for (size_t splitter : markedSplitters) { - size_t newSplitter = splitters.getSet(splitter).split(); - if (newSplitter) { - potentialSplitters.push_back(newSplitter); - } - } - } - } - -#if TRACE_CANONICALIZATION - std::cerr << "Final partitions:\n"; - dumpPartitions(); -#endif - - createReplacements(); -} - -void ShapeCanonicalizer::initialize(std::vector<HeapType>& roots) { - struct Initializer : HeapTypeGraphWalker<Initializer> { - ShapeCanonicalizer& canonicalizer; - - // Maps shallow HeapType shapes to corresponding HeapType indices. - InsertOrderedMap<ShallowHeapType, std::vector<size_t>> initialPartitions; - - // Maps `dest` HeapType indices to their input transitions. - std::map<size_t, std::vector<Transition>> transitions; - size_t numTransitions = 0; - - Initializer(ShapeCanonicalizer& canonicalizer) - : canonicalizer(canonicalizer) {} - - size_t getIndex(HeapType type) { - // Allocate an index for the HeapType if it doesn't already have one. - auto inserted = - canonicalizer.states.insert({type, canonicalizer.states.size()}); - if (inserted.second) { - canonicalizer.heapTypes.push_back(type); - } - return inserted.first->second; - } - - void noteHeapType(HeapType type) { - size_t index = getIndex(type); - - // Allocate an initial partition for this HeapType's shallow shape if one - // does not already exist, then append the HeapType to the partition. - initialPartitions[ShallowHeapType(type)].push_back(index); - - // Traverse the non-basic children to collect graph edges, i.e. - // transitions in the DFA. - struct TransitionInitializer - : HeapTypeChildWalker<TransitionInitializer> { - Initializer& initializer; - size_t parent; - size_t label = 0; - TransitionInitializer(Initializer& initializer, size_t parent) - : initializer(initializer), parent(parent) {} - void noteChild(HeapType* childType) { - if (childType->isBasic()) { - return; - } - // Record the transition from parent to child. - size_t child = initializer.getIndex(*childType); - initializer.transitions[child].push_back({parent, label++}); - ++initializer.numTransitions; - } - }; - TransitionInitializer(*this, index).walkRoot(&type); - } - }; - - Initializer initializer(*this); - for (HeapType& root : roots) { - initializer.walkRoot(&root); - } - - // Now that we have initialized maps containing all the necessary data, use - // them to initialize the flattened vector-based data structures that we will - // use to efficiently run the minimization algorithm. - - // Initialize `partitions`. - partitions = Partitions(heapTypes.size()); - size_t elementIndex = 0; - for (auto pair : initializer.initialPartitions) { - size_t set = partitions.sets++; - partitions.beginnings[set] = elementIndex; - partitions.pivots[set] = elementIndex; - for (size_t elem : pair.second) { - partitions.elements[elementIndex] = elem; - partitions.elementIndices[elem] = elementIndex; - partitions.setIndices[elem] = set; - ++elementIndex; - } - partitions.endings[set] = elementIndex; - } - - // Initialize `transitions` and `transitionIndices`. - transitions.reserve(initializer.numTransitions); - transitionIndices.resize(heapTypes.size() + 1); - for (size_t dest = 0; dest < heapTypes.size(); ++dest) { - // Record the first index of transitions leading to `dest`. - transitionIndices[dest] = transitions.size(); - auto it = initializer.transitions.find(dest); - if (it != initializer.transitions.end()) { - transitions.insert( - transitions.end(), it->second.begin(), it->second.end()); - } - } - // Record one-past the end of the transitions leading to the final `dest`. - transitionIndices[heapTypes.size()] = transitions.size(); - - // Initialize `splitters`. The initial sets are partitioned by destination - // state partition and transition label. - splitters = Partitions(transitions.size()); - elementIndex = 0; - for (size_t statePartition = 0; statePartition < partitions.sets; - ++statePartition) { - // The in-transitions leading to states in the current partition, organized - // by transition label. - std::map<size_t, std::vector<size_t>> currTransitions; - for (size_t state : partitions.getSet(statePartition)) { - for (size_t transition = transitionIndices[state], - end = transitionIndices[state + 1]; - transition < end; - ++transition) { - currTransitions[transitions[transition].label].push_back(transition); - } - } - // Create a splitter partition for each in-transition label leading to the - // current state partition. - for (auto& pair : currTransitions) { - size_t set = splitters.sets++; - splitters.beginnings[set] = elementIndex; - splitters.pivots[set] = elementIndex; - for (size_t transition : pair.second) { - splitters.elements[elementIndex] = transition; - splitters.elementIndices[transition] = elementIndex; - splitters.setIndices[transition] = set; - ++elementIndex; - } - splitters.endings[set] = elementIndex; - } - } -} - -void ShapeCanonicalizer::createReplacements() { - // Create a single new HeapTypeInfo for each partition. Initialize each new - // HeapTypeInfo as a copy of a representative HeapTypeInfo from its partition, - // then patch all the children of the new HeapTypeInfos to refer to other new - // HeapTypeInfos rather than the original HeapTypeInfos. This newly formed - // graph will have a shape coinductively equivalent to the original graph's - // shape, but each type definition will be minimal and distinct. - // - // However, for partitions that already contain globally canonical types, find - // and use the corresponding HeapTypeInfo directly without copying. Since the - // partitions reachable from a globally canonical type will also contain a - // globally canonical type, no temporary types will end up being patched into - // the globally canonical types and we can skip patching the children of those - // types. - for (size_t p = 0; p < partitions.sets; ++p) { - auto partition = partitions.getSet(p); - auto it = std::find_if(partition.begin(), - partition.end(), - [this](size_t i) { return !isTemp(heapTypes[i]); }); - HeapType newType; - auto partitionIt = partition.begin(); - if (it != partition.end()) { - newType = heapTypes[*it]; - } else { - // We do not already know about a globally canonical type for this - // partition. Create a copy and a replacement that owns it. - HeapType oldType = heapTypes[*partitionIt++]; - const auto& representative = *getHeapTypeInfo(oldType); - auto info = std::make_unique<HeapTypeInfo>(representative); - info->isTemp = true; - newType = asHeapType(info); - replacements.insert({oldType, std::move(info)}); - } - // Create replacements for all the other types in the partition. - for (; partitionIt != partition.end(); ++partitionIt) { - if (partitionIt != it) { - replacements.insert({heapTypes[*partitionIt], newType}); - } - } - } -} - // Replaces temporary types and heap types in a type definition graph with their // globally canonical versions to prevent temporary types or heap type from // leaking into the global stores. @@ -3682,24 +2664,8 @@ void globallyCanonicalize(CanonicalizationState& state) { #endif } -void canonicalizeEquirecursive(CanonicalizationState& state) { - // Equirecursive types always have null supertypes and recursion groups. - for (auto& info : state.newInfos) { - info->recGroup = nullptr; - info->supertype = nullptr; - } - - // Canonicalize the shape of the type definition graph. - ShapeCanonicalizer minimized(state.results); - state.update(minimized.replacements); -} - std::optional<TypeBuilder::Error> validateSubtyping(const std::vector<HeapType>& types) { - if (getTypeSystem() == TypeSystem::Equirecursive) { - // Subtyping is not explicitly declared, so nothing to check. - return {}; - } for (size_t i = 0; i < types.size(); ++i) { HeapType type = types[i]; if (type.isBasic()) { @@ -3966,9 +2932,6 @@ TypeBuilder::BuildResult TypeBuilder::build() { #endif switch (typeSystem) { - case TypeSystem::Equirecursive: - canonicalizeEquirecursive(state); - break; case TypeSystem::Nominal: if (auto error = canonicalizeNominal(state)) { return {*error}; @@ -4091,7 +3054,7 @@ size_t hash<wasm::TypeInfo>::operator()(const wasm::TypeInfo& info) const { size_t hash<wasm::HeapTypeInfo>::operator()(const wasm::HeapTypeInfo& info) const { - return wasm::FiniteShapeHasher().hash(info); + return wasm::hash(uintptr_t(&info)); } } // namespace std diff --git a/test/example/c-api-kitchen-sink.c b/test/example/c-api-kitchen-sink.c index 8dd9260d5..d20c76100 100644 --- a/test/example/c-api-kitchen-sink.c +++ b/test/example/c-api-kitchen-sink.c @@ -2090,8 +2090,6 @@ void test_func_opt() { void test_typesystem() { BinaryenTypeSystem defaultTypeSystem = BinaryenGetTypeSystem(); assert(defaultTypeSystem == BinaryenTypeSystemIsorecursive()); - printf("BinaryenTypeSystemEquirecursive: %d\n", - BinaryenTypeSystemEquirecursive()); BinaryenSetTypeSystem(BinaryenTypeSystemNominal()); assert(BinaryenGetTypeSystem() == BinaryenTypeSystemNominal()); printf("BinaryenTypeSystemNominal: %d\n", BinaryenTypeSystemNominal()); diff --git a/test/example/c-api-kitchen-sink.txt b/test/example/c-api-kitchen-sink.txt index 857988419..c4dd09168 100644 --- a/test/example/c-api-kitchen-sink.txt +++ b/test/example/c-api-kitchen-sink.txt @@ -3028,9 +3028,8 @@ optimized: (i32.const 4) ) ) -BinaryenTypeSystemEquirecursive: 0 BinaryenTypeSystemNominal: 1 -BinaryenTypeSystemIsorecursive: 2 +BinaryenTypeSystemIsorecursive: 0 TypeBuilderErrorReasonSelfSupertype: 0 TypeBuilderErrorReasonInvalidSupertype: 1 TypeBuilderErrorReasonForwardSupertypeReference: 2 diff --git a/test/example/type-builder-nominal.txt b/test/example/type-builder-nominal.txt index 8d146cc1f..b542f212c 100644 --- a/test/example/type-builder-nominal.txt +++ b/test/example/type-builder-nominal.txt @@ -1,24 +1,24 @@ ;; Test TypeBuilder Before setting heap types: -$sig => (; temp ;) (func_subtype func) -$struct => (; temp ;) (func_subtype func) -$array => (; temp ;) (func_subtype func) +$sig => (; temp ;) (func) +$struct => (; temp ;) (func) +$array => (; temp ;) (func) (ref $sig) => (; temp ;) (ref $0) (ref $struct) => (; temp ;) (ref $1) (ref $array) => (; temp ;) (ref $2) (ref null $array) => (; temp ;) (ref null $2) After setting heap types: -$sig => (; temp ;) (func_subtype (param (; temp ;) (ref $1)) (result (; temp ;) (ref $2) i32) func) -$struct => (; temp ;) (struct_subtype (field (; temp ;) (ref null $2)) data) -$array => (; temp ;) (array_subtype (mut anyref) data) +$sig => (; temp ;) (func (param (; temp ;) (ref $1)) (result (; temp ;) (ref $2) i32)) +$struct => (; temp ;) (struct (field (; temp ;) (ref null $2))) +$array => (; temp ;) (array (mut anyref)) (ref $sig) => (; temp ;) (ref $0) (ref $struct) => (; temp ;) (ref $1) (ref $array) => (; temp ;) (ref $2) (ref null $array) => (; temp ;) (ref null $2) After building types: -$sig => (func_subtype (param (ref $1)) (result (ref $2) i32) func) -$struct => (struct_subtype (field (ref null $2)) data) -$array => (array_subtype (mut anyref) data) +$sig => (func (param (ref $1)) (result (ref $2) i32)) +$struct => (struct (field (ref null $2))) +$array => (array (mut anyref)) (ref $sig) => (ref $0) (ref $struct) => (ref $1) (ref $array) => (ref $2) @@ -27,49 +27,49 @@ $array => (array_subtype (mut anyref) data) ;; Test basic ;; Test canonical signatures ;; Test recursive types -(func_subtype (result (ref null $0)) func) +(func (result (ref null $0))) -(func_subtype (result (ref null $1)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $1))) +(func (result (ref null $0))) -(func_subtype (result (ref null $1)) func) -(func_subtype (result (ref null $2)) func) -(func_subtype (result (ref null $3)) func) -(func_subtype (result (ref null $4)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $1))) +(func (result (ref null $2))) +(func (result (ref null $3))) +(func (result (ref null $4))) +(func (result (ref null $0))) -(func_subtype (result (ref null $0) (ref null $2)) func) -(func_subtype (result (ref null $1) (ref null $3)) func) -(func_subtype func) -(func_subtype func) -(func_subtype (result (ref null $0)) func) -(func_subtype (result (ref null $1)) func) +(func (result (ref null $0) (ref null $2))) +(func (result (ref null $1) (ref null $3))) +(func) +(func) +(func (result (ref null $0))) +(func (result (ref null $1))) -(func_subtype (result (ref null $0)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $0))) +(func (result (ref null $0))) ;; Test subtyping ;; Test TypeBuilder Before setting heap types: -$sig => (; temp ;) (func_subtype func) -$struct => (; temp ;) (func_subtype func) -$array => (; temp ;) (func_subtype func) +$sig => (; temp ;) (func) +$struct => (; temp ;) (func) +$array => (; temp ;) (func) (ref $sig) => (; temp ;) (ref $0) (ref $struct) => (; temp ;) (ref $1) (ref $array) => (; temp ;) (ref $2) (ref null $array) => (; temp ;) (ref null $2) After setting heap types: -$sig => (; temp ;) (func_subtype (param (; temp ;) (ref $1)) (result (; temp ;) (ref $2) i32) func) -$struct => (; temp ;) (struct_subtype (field (; temp ;) (ref null $2)) data) -$array => (; temp ;) (array_subtype (mut anyref) data) +$sig => (; temp ;) (func (param (; temp ;) (ref $1)) (result (; temp ;) (ref $2) i32)) +$struct => (; temp ;) (struct (field (; temp ;) (ref null $2))) +$array => (; temp ;) (array (mut anyref)) (ref $sig) => (; temp ;) (ref $0) (ref $struct) => (; temp ;) (ref $1) (ref $array) => (; temp ;) (ref $2) (ref null $array) => (; temp ;) (ref null $2) After building types: -$sig => (func_subtype (param (ref $1)) (result (ref $2) i32) func) -$struct => (struct_subtype (field (ref null $2)) data) -$array => (array_subtype (mut anyref) data) +$sig => (func (param (ref $1)) (result (ref $2) i32)) +$struct => (struct (field (ref null $2))) +$array => (array (mut anyref)) (ref $sig) => (ref $0) (ref $struct) => (ref $1) (ref $array) => (ref $2) @@ -78,25 +78,25 @@ $array => (array_subtype (mut anyref) data) ;; Test basic ;; Test canonical signatures ;; Test recursive types -(func_subtype (result (ref null $0)) func) +(func (result (ref null $0))) -(func_subtype (result (ref null $1)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $1))) +(func (result (ref null $0))) -(func_subtype (result (ref null $1)) func) -(func_subtype (result (ref null $2)) func) -(func_subtype (result (ref null $3)) func) -(func_subtype (result (ref null $4)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $1))) +(func (result (ref null $2))) +(func (result (ref null $3))) +(func (result (ref null $4))) +(func (result (ref null $0))) -(func_subtype (result (ref null $0) (ref null $2)) func) -(func_subtype (result (ref null $1) (ref null $3)) func) -(func_subtype func) -(func_subtype func) -(func_subtype (result (ref null $0)) func) -(func_subtype (result (ref null $1)) func) +(func (result (ref null $0) (ref null $2))) +(func (result (ref null $1) (ref null $3))) +(func) +(func) +(func (result (ref null $0))) +(func (result (ref null $1))) -(func_subtype (result (ref null $0)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $0))) +(func (result (ref null $0))) ;; Test subtyping diff --git a/test/example/type-builder.txt b/test/example/type-builder.txt index af40fd5de..6d584e7be 100644 --- a/test/example/type-builder.txt +++ b/test/example/type-builder.txt @@ -1,54 +1,54 @@ ;; Test canonicalization ;; Test basic ;; Test recursive types -(func_subtype (result (ref null $0)) func) +(func (result (ref null $0))) -(func_subtype (result (ref null $1)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $1))) +(func (result (ref null $0))) -(func_subtype (result (ref null $1)) func) -(func_subtype (result (ref null $2)) func) -(func_subtype (result (ref null $3)) func) -(func_subtype (result (ref null $4)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $1))) +(func (result (ref null $2))) +(func (result (ref null $3))) +(func (result (ref null $4))) +(func (result (ref null $0))) -(func_subtype func) -(func_subtype func) -(func_subtype (result (ref null $0) (ref null $2)) func) -(func_subtype (result (ref null $0) (ref null $3)) func) -(func_subtype (result (ref null $2)) func) -(func_subtype (result (ref null $3)) func) +(func) +(func) +(func (result (ref null $0) (ref null $2))) +(func (result (ref null $0) (ref null $3))) +(func (result (ref null $2))) +(func (result (ref null $3))) -(func_subtype (result (ref null $0)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $0))) +(func (result (ref null $0))) any -(func_subtype (param anyref) (result (ref null $1)) func) +(func (param anyref) (result (ref null $1))) ;; Test canonicalization ;; Test basic ;; Test recursive types -(func_subtype (result (ref null $0)) func) +(func (result (ref null $0))) -(func_subtype (result (ref null $1)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $1))) +(func (result (ref null $0))) -(func_subtype (result (ref null $1)) func) -(func_subtype (result (ref null $2)) func) -(func_subtype (result (ref null $3)) func) -(func_subtype (result (ref null $4)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $1))) +(func (result (ref null $2))) +(func (result (ref null $3))) +(func (result (ref null $4))) +(func (result (ref null $0))) -(func_subtype func) -(func_subtype func) -(func_subtype (result (ref null $0) (ref null $2)) func) -(func_subtype (result (ref null $0) (ref null $3)) func) -(func_subtype (result (ref null $2)) func) -(func_subtype (result (ref null $3)) func) +(func) +(func) +(func (result (ref null $0) (ref null $2))) +(func (result (ref null $0) (ref null $3))) +(func (result (ref null $2))) +(func (result (ref null $3))) -(func_subtype (result (ref null $0)) func) -(func_subtype (result (ref null $0)) func) +(func (result (ref null $0))) +(func (result (ref null $0))) any -(func_subtype (param anyref) (result (ref null $1)) func) +(func (param anyref) (result (ref null $1))) diff --git a/test/example/typeinfo.txt b/test/example/typeinfo.txt index 67f9766d0..7015e6cfc 100644 --- a/test/example/typeinfo.txt +++ b/test/example/typeinfo.txt @@ -11,31 +11,31 @@ eqref i31 i31ref (ref i31) -(func_subtype func) -(struct_subtype data) -(array_subtype i32 data) +(func) +(struct) +(array i32) ;; Signature -(func_subtype func) +(func) (ref $func.0) (ref null $func.0) -(func_subtype (param i32) (result f64) func) +(func (param i32) (result f64)) (ref $func.0) (ref null $func.0) ;; Struct -(struct_subtype data) +(struct) (ref $struct.0) (ref null $struct.0) -(struct_subtype (field i32 i64 (mut f32) (mut f64)) data) +(struct (field i32 i64 (mut f32) (mut f64))) (ref $struct.0) (ref null $struct.0) ;; Array -(array_subtype i32 data) +(array i32) (ref $array.0) (ref null $array.0) -(array_subtype (mut i64) data) +(array (mut i64)) (ref $array.0) (ref null $array.0) @@ -46,33 +46,33 @@ none (i32 f64) ;; Signature of references (param/result) -(func_subtype (param (ref null $struct.0)) (result (ref $array.0)) func) +(func (param (ref null $struct.0)) (result (ref $array.0))) ;; Signature of references (params/results) -(func_subtype (param (ref null $struct.0) (ref $array.0)) (result (ref $struct.0) (ref null $array.1)) func) +(func (param (ref null $struct.0) (ref $array.0)) (result (ref $struct.0) (ref null $array.1))) ;; Struct of references -(struct_subtype (field (ref $func.0) (mut (ref $func.0)) (ref null $func.0) (mut (ref null $func.0))) data) +(struct (field (ref $func.0) (mut (ref $func.0)) (ref null $func.0) (mut (ref null $func.0)))) (ref $struct.0) (ref null $struct.0) -(struct_subtype (field (ref $struct.0) (mut (ref $struct.0)) (ref null $struct.0) (mut (ref null $struct.0))) data) +(struct (field (ref $struct.0) (mut (ref $struct.0)) (ref null $struct.0) (mut (ref null $struct.0)))) (ref $struct.0) (ref null $struct.0) -(struct_subtype (field (ref $array.0) (mut (ref $array.0)) (ref null $array.0) (mut (ref null $array.0))) data) +(struct (field (ref $array.0) (mut (ref $array.0)) (ref null $array.0) (mut (ref null $array.0)))) (ref $struct.0) (ref null $struct.0) -(struct_subtype (field (mut i32) (mut (ref null $func.0)) (mut (ref null $struct.0)) (mut (ref null $array.0))) data) +(struct (field (mut i32) (mut (ref null $func.0)) (mut (ref null $struct.0)) (mut (ref null $array.0)))) (ref $struct.0) (ref null $struct.0) ;; Array of references -(array_subtype (ref null $func.0) data) +(array (ref null $func.0)) (ref $array.0) (ref null $array.0) -(array_subtype (mut (ref null $struct.0)) data) +(array (mut (ref null $struct.0))) (ref $array.0) (ref null $array.0) -(array_subtype (ref null $array.0) data) +(array (ref null $array.0)) (ref $array.0) (ref null $array.0) @@ -81,7 +81,7 @@ none ((ref $func.0) (ref null $func.0) (ref $struct.0) (ref null $struct.0) (ref $array.0) (ref null $array.0)) ;; Recursive (not really) -(func_subtype (param (ref $func.0)) func) +(func (param (ref $func.0))) (ref $func.0) -(func_subtype (param (ref $array.0)) func) +(func (param (ref $array.0))) (ref $func.0) diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp index fcf0e1a5a..0dba0a10c 100644 --- a/test/gtest/type-builder.cpp +++ b/test/gtest/type-builder.cpp @@ -103,22 +103,22 @@ TEST_F(TypeTest, IndexedTypePrinter) { std::stringstream stream; stream << print(built[0]); - EXPECT_EQ(stream.str(), "(struct_subtype (field (ref null $array1)) data)"); + EXPECT_EQ(stream.str(), "(struct (field (ref null $array1)))"); stream.str(""); stream << print(built[1]); - EXPECT_EQ(stream.str(), "(struct_subtype (field (ref null $struct0)) data)"); + EXPECT_EQ(stream.str(), "(struct (field (ref null $struct0)))"); stream.str(""); stream << print(built[2]); - EXPECT_EQ(stream.str(), "(array_subtype (ref null $struct1) data)"); + EXPECT_EQ(stream.str(), "(array (ref null $struct1))"); stream.str(""); stream << print(built[3]); - EXPECT_EQ(stream.str(), "(array_subtype (ref null $array0) data)"); + EXPECT_EQ(stream.str(), "(array (ref null $array0))"); } -TEST_F(EquirecursiveTest, Basics) { +TEST_F(IsorecursiveTest, Basics) { // (type $sig (func (param (ref $struct)) (result (ref $array) i32))) // (type $struct (struct (field (ref null $array)))) // (type $array (array (mut anyref))) @@ -139,6 +139,8 @@ TEST_F(EquirecursiveTest, Basics) { builder[1] = struct_; builder[2] = array; + builder.createRecGroup(0, 3); + auto result = builder.build(); ASSERT_TRUE(result); std::vector<HeapType> built = *result; @@ -470,7 +472,7 @@ TEST_F(IsorecursiveTest, CanonicalizeTypesBeforeSubtyping) { EXPECT_TRUE(result); } -static void testCanonicalizeBasicTypes() { +TEST_F(IsorecursiveTest, CanonicalizeBasicTypes) { TypeBuilder builder(5); Type anyref = builder.getTempRefType(builder[0], Nullable); @@ -492,13 +494,6 @@ static void testCanonicalizeBasicTypes() { EXPECT_EQ(built[3], built[4]); } -TEST_F(EquirecursiveTest, CanonicalizeBasicTypes) { - testCanonicalizeBasicTypes(); -} -TEST_F(IsorecursiveTest, CanonicalizeBasicTypes) { - testCanonicalizeBasicTypes(); -} - TEST_F(IsorecursiveTest, TestHeapTypeRelations) { HeapType ext = HeapType::ext; HeapType func = HeapType::func; diff --git a/test/gtest/type-test.h b/test/gtest/type-test.h index fffcbd3dd..49c6381fa 100644 --- a/test/gtest/type-test.h +++ b/test/gtest/type-test.h @@ -33,7 +33,6 @@ protected: }; using TypeTest = TypeSystemTest<wasm::TypeSystem::Isorecursive>; -using EquirecursiveTest = TypeSystemTest<wasm::TypeSystem::Equirecursive>; using NominalTest = TypeSystemTest<wasm::TypeSystem::Nominal>; using IsorecursiveTest = TypeSystemTest<wasm::TypeSystem::Isorecursive>; diff --git a/test/lit/fuzz-types/isorecursive.test b/test/lit/fuzz-types/isorecursive.test index ccbb63d5e..4a1725c07 100644 --- a/test/lit/fuzz-types/isorecursive.test +++ b/test/lit/fuzz-types/isorecursive.test @@ -1,26 +1,26 @@ ;; RUN: wasm-fuzz-types --hybrid -v --seed=0 | filecheck %s ;; CHECK: (rec -;; CHECK-NEXT: (type $0 (array_subtype (mut i64) data)) -;; CHECK-NEXT: (type $1 (func_subtype (param i32 (ref eq) (ref null $3)) (result v128) func)) -;; CHECK-NEXT: (type $2 (array_subtype (mut v128) data)) +;; CHECK-NEXT: (type $0 (array (mut i64))) +;; CHECK-NEXT: (type $1 (func (param i32 (ref eq) (ref null $3)) (result v128))) +;; CHECK-NEXT: (type $2 (array (mut v128))) ;; CHECK-NEXT: (type $3 (array_subtype (mut i64) $0)) -;; CHECK-NEXT: (type $4 (array_subtype i32 data)) +;; CHECK-NEXT: (type $4 (array i32)) ;; CHECK-NEXT: (type $5 none) ;; CHECK-NEXT: (type $6 extern) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (rec ;; CHECK-NEXT: (type $7 (array_subtype (mut i64) $3)) -;; CHECK-NEXT: (type $8 (func_subtype (result v128) func)) +;; CHECK-NEXT: (type $8 (func (result v128))) ;; CHECK-NEXT: (type $9 (array_subtype (mut v128) $2)) ;; CHECK-NEXT: (type $10 none) ;; CHECK-NEXT: (type $11 none) ;; CHECK-NEXT: (type $12 (array_subtype (mut v128) $2)) -;; CHECK-NEXT: (type $13 (func_subtype (param f32 (ref none) (ref null $3)) (result eqref) func)) +;; CHECK-NEXT: (type $13 (func (param f32 (ref none) (ref null $3)) (result eqref))) ;; CHECK-NEXT: (type $14 (array_subtype (mut i64) $7)) -;; CHECK-NEXT: (type $15 (func_subtype (param (ref null $17) v128 (ref i31)) func)) -;; CHECK-NEXT: (type $16 (array_subtype i32 data)) -;; CHECK-NEXT: (type $17 (func_subtype (param (ref i31)) (result v128) func)) -;; CHECK-NEXT: (type $18 (func_subtype (param f32) func)) +;; CHECK-NEXT: (type $15 (func (param (ref null $17) v128 (ref i31)))) +;; CHECK-NEXT: (type $16 (array i32)) +;; CHECK-NEXT: (type $17 (func (param (ref i31)) (result v128))) +;; CHECK-NEXT: (type $18 (func (param f32))) ;; CHECK-NEXT: (type $19 (array_subtype (mut i64) $3)) ;; CHECK-NEXT: ) diff --git a/test/lit/fuzz-types/nominal.test b/test/lit/fuzz-types/nominal.test index bb84f6991..26802a4ba 100644 --- a/test/lit/fuzz-types/nominal.test +++ b/test/lit/fuzz-types/nominal.test @@ -1,22 +1,22 @@ ;; RUN: wasm-fuzz-types --nominal -v --seed=0 | filecheck %s -;; CHECK: (type $0 (array_subtype (mut (ref null $8)) data)) -;; CHECK-NEXT: (type $1 (func_subtype (param nullref) (result v128) func)) -;; CHECK-NEXT: (type $2 (struct_subtype (field (mut i64) (mut i8) (mut (ref $12)) (mut f32)) data)) +;; CHECK: (type $0 (array (mut (ref null $8)))) +;; CHECK-NEXT: (type $1 (func (param nullref) (result v128))) +;; CHECK-NEXT: (type $2 (struct (field (mut i64) (mut i8) (mut (ref $12)) (mut f32)))) ;; CHECK-NEXT: (type $3 (array_subtype (mut (ref null $8)) $0)) -;; CHECK-NEXT: (type $4 (array_subtype (mut i64) data)) +;; CHECK-NEXT: (type $4 (array (mut i64))) ;; CHECK-NEXT: (type $5 none) ;; CHECK-NEXT: (type $6 extern) ;; CHECK-NEXT: (type $7 (array_subtype (mut (ref null $8)) $3)) -;; CHECK-NEXT: (type $8 (func_subtype (result (ref $9)) func)) +;; CHECK-NEXT: (type $8 (func (result (ref $9)))) ;; CHECK-NEXT: (type $9 (struct_subtype (field (mut i64) (mut i8) (mut (ref $12)) (mut f32) i16) $2)) ;; CHECK-NEXT: (type $10 none) ;; CHECK-NEXT: (type $11 none) ;; CHECK-NEXT: (type $12 (struct_subtype (field (mut i64) (mut i8) (mut (ref $12)) (mut f32) (mut f32) (mut (ref $4))) $2)) -;; CHECK-NEXT: (type $13 (func_subtype (param dataref) func)) +;; CHECK-NEXT: (type $13 (func (param dataref))) ;; CHECK-NEXT: (type $14 (array_subtype (mut (ref null $8)) $7)) -;; CHECK-NEXT: (type $15 (func_subtype (param externref) func)) -;; CHECK-NEXT: (type $16 (array_subtype v128 data)) -;; CHECK-NEXT: (type $17 (func_subtype (result (ref extern)) func)) -;; CHECK-NEXT: (type $18 (func_subtype (param v128 i64) func)) +;; CHECK-NEXT: (type $15 (func (param externref))) +;; CHECK-NEXT: (type $16 (array v128)) +;; CHECK-NEXT: (type $17 (func (result (ref extern)))) +;; CHECK-NEXT: (type $18 (func (param v128 i64))) ;; CHECK-NEXT: (type $19 (array_subtype (mut (ref null $8)) $3)) diff --git a/test/lit/fuzz-types/structural.test b/test/lit/fuzz-types/structural.test deleted file mode 100644 index 3dcec3179..000000000 --- a/test/lit/fuzz-types/structural.test +++ /dev/null @@ -1,22 +0,0 @@ -;; RUN: wasm-fuzz-types --structural -v --seed=0 | filecheck %s - -;; CHECK: (type $0 (array (mut (ref null $8)))) -;; CHECK-NEXT: (type $1 (func (param nullref) (result v128))) -;; CHECK-NEXT: (type $2 (struct (field (mut i64) (mut i8) (mut (ref $12)) (mut f32)))) -;; CHECK-NEXT: (type $3 identical to $0) -;; CHECK-NEXT: (type $4 (array (mut i64))) -;; CHECK-NEXT: (type $5 none) -;; CHECK-NEXT: (type $6 extern) -;; CHECK-NEXT: (type $7 identical to $0) -;; CHECK-NEXT: (type $8 (func (result (ref $9)))) -;; CHECK-NEXT: (type $9 (struct (field (mut i64) (mut i8) (mut (ref $12)) (mut f32) i16))) -;; CHECK-NEXT: (type $10 none) -;; CHECK-NEXT: (type $11 none) -;; CHECK-NEXT: (type $12 (struct (field (mut i64) (mut i8) (mut (ref $12)) (mut f32) (mut f32) (mut (ref $4))))) -;; CHECK-NEXT: (type $13 (func (param dataref))) -;; CHECK-NEXT: (type $14 identical to $0) -;; CHECK-NEXT: (type $15 (func (param externref))) -;; CHECK-NEXT: (type $16 (array v128)) -;; CHECK-NEXT: (type $17 (func (result (ref extern)))) -;; CHECK-NEXT: (type $18 (func (param v128 i64))) -;; CHECK-NEXT: (type $19 identical to $0) diff --git a/test/lit/help/wasm-as.test b/test/lit/help/wasm-as.test index bbce25015..c94dab310 100644 --- a/test/lit/help/wasm-as.test +++ b/test/lit/help/wasm-as.test @@ -122,10 +122,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to be ;; CHECK-NEXT: parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to be -;; CHECK-NEXT: parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to be ;; CHECK-NEXT: parsed using the isorecursive hybrid type ;; CHECK-NEXT: system. diff --git a/test/lit/help/wasm-ctor-eval.test b/test/lit/help/wasm-ctor-eval.test index c20ccc8c8..9295fc9d1 100644 --- a/test/lit/help/wasm-ctor-eval.test +++ b/test/lit/help/wasm-ctor-eval.test @@ -126,10 +126,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to be ;; CHECK-NEXT: parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to be -;; CHECK-NEXT: parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to be ;; CHECK-NEXT: parsed using the isorecursive hybrid type ;; CHECK-NEXT: system. diff --git a/test/lit/help/wasm-dis.test b/test/lit/help/wasm-dis.test index f6baf0467..c0f0b6f38 100644 --- a/test/lit/help/wasm-dis.test +++ b/test/lit/help/wasm-dis.test @@ -115,10 +115,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to be ;; CHECK-NEXT: parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to be -;; CHECK-NEXT: parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to be ;; CHECK-NEXT: parsed using the isorecursive hybrid type ;; CHECK-NEXT: system. diff --git a/test/lit/help/wasm-emscripten-finalize.test b/test/lit/help/wasm-emscripten-finalize.test index 45d3a3eae..1600bb823 100644 --- a/test/lit/help/wasm-emscripten-finalize.test +++ b/test/lit/help/wasm-emscripten-finalize.test @@ -162,10 +162,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to be ;; CHECK-NEXT: parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to be -;; CHECK-NEXT: parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to be ;; CHECK-NEXT: parsed using the isorecursive hybrid type ;; CHECK-NEXT: system. diff --git a/test/lit/help/wasm-fuzz-types.test b/test/lit/help/wasm-fuzz-types.test index a282aa4a6..49e491358 100644 --- a/test/lit/help/wasm-fuzz-types.test +++ b/test/lit/help/wasm-fuzz-types.test @@ -9,23 +9,21 @@ ;; CHECK-NEXT: wasm-fuzz-types options: ;; CHECK-NEXT: ------------------------ ;; CHECK-NEXT: -;; CHECK-NEXT: --seed Run a single workload generated by the given seed +;; CHECK-NEXT: --seed Run a single workload generated by the given seed ;; CHECK-NEXT: -;; CHECK-NEXT: --verbose,-v Print extra information +;; CHECK-NEXT: --verbose,-v Print extra information ;; CHECK-NEXT: -;; CHECK-NEXT: --nominal Use the nominal type system (default) +;; CHECK-NEXT: --nominal Use the nominal type system ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Use the equirecursive type system -;; CHECK-NEXT: -;; CHECK-NEXT: --hybrid Use the isorecursive hybrid type system +;; CHECK-NEXT: --hybrid Use the isorecursive hybrid type system (default) ;; CHECK-NEXT: ;; CHECK-NEXT: ;; CHECK-NEXT: General options: ;; CHECK-NEXT: ---------------- ;; CHECK-NEXT: -;; CHECK-NEXT: --version Output version information and exit +;; CHECK-NEXT: --version Output version information and exit ;; CHECK-NEXT: -;; CHECK-NEXT: --help,-h Show this help message and exit +;; CHECK-NEXT: --help,-h Show this help message and exit ;; CHECK-NEXT: -;; CHECK-NEXT: --debug,-d Print debug information to stderr +;; CHECK-NEXT: --debug,-d Print debug information to stderr ;; CHECK-NEXT: diff --git a/test/lit/help/wasm-metadce.test b/test/lit/help/wasm-metadce.test index 10e67873a..a748d8198 100644 --- a/test/lit/help/wasm-metadce.test +++ b/test/lit/help/wasm-metadce.test @@ -163,10 +163,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to be ;; CHECK-NEXT: parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to be -;; CHECK-NEXT: parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to be ;; CHECK-NEXT: parsed using the isorecursive hybrid type ;; CHECK-NEXT: system. diff --git a/test/lit/help/wasm-opt.test b/test/lit/help/wasm-opt.test index bc3d710ac..bdc4b9cd8 100644 --- a/test/lit/help/wasm-opt.test +++ b/test/lit/help/wasm-opt.test @@ -661,11 +661,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to ;; CHECK-NEXT: be parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to -;; CHECK-NEXT: be parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the -;; CHECK-NEXT: default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to ;; CHECK-NEXT: be parsed using the isorecursive ;; CHECK-NEXT: hybrid type system. diff --git a/test/lit/help/wasm-reduce.test b/test/lit/help/wasm-reduce.test index 9b394a7f7..c640cf5f7 100644 --- a/test/lit/help/wasm-reduce.test +++ b/test/lit/help/wasm-reduce.test @@ -151,10 +151,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to be ;; CHECK-NEXT: parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to be -;; CHECK-NEXT: parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to be ;; CHECK-NEXT: parsed using the isorecursive hybrid type ;; CHECK-NEXT: system. diff --git a/test/lit/help/wasm-split.test b/test/lit/help/wasm-split.test index 8da75cca2..176ba1858 100644 --- a/test/lit/help/wasm-split.test +++ b/test/lit/help/wasm-split.test @@ -231,10 +231,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to be ;; CHECK-NEXT: parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to be -;; CHECK-NEXT: parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to be ;; CHECK-NEXT: parsed using the isorecursive hybrid type ;; CHECK-NEXT: system. diff --git a/test/lit/help/wasm2js.test b/test/lit/help/wasm2js.test index ce2748343..16c6c45fc 100644 --- a/test/lit/help/wasm2js.test +++ b/test/lit/help/wasm2js.test @@ -620,11 +620,6 @@ ;; CHECK-NEXT: --nominal Force all GC type definitions to ;; CHECK-NEXT: be parsed as nominal. ;; CHECK-NEXT: -;; CHECK-NEXT: --structural Force all GC type definitions to -;; CHECK-NEXT: be parsed as structural (i.e. -;; CHECK-NEXT: equirecursive). This is the -;; CHECK-NEXT: default. -;; CHECK-NEXT: ;; CHECK-NEXT: --hybrid Force all GC type definitions to ;; CHECK-NEXT: be parsed using the isorecursive ;; CHECK-NEXT: hybrid type system. diff --git a/test/lit/lub-bug-3843.wast b/test/lit/lub-bug-3843.wast deleted file mode 100644 index 8bf384c71..000000000 --- a/test/lit/lub-bug-3843.wast +++ /dev/null @@ -1,53 +0,0 @@ -;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited. -;; RUN: wasm-opt %s -all --precompute --structural -S -o - | filecheck %s -;; RUN: wasm-opt %s -all --precompute --nominal -S -o - | filecheck %s --check-prefix NOMNL - -;; Regression test for a bug (#3843) in which the LUB calculation done during -;; the refinalization of the select incorrectly produced a new type rather than -;; returning (ref null $A). - -(module - ;; CHECK: (type $A (struct (field (ref null $C)))) - ;; NOMNL: (type $A (struct (field (ref null $C)))) - (type $A (struct (field (ref null $C)))) - - ;; CHECK: (type $B (struct (field (ref null $D)))) - ;; NOMNL: (type $B (struct_subtype (field (ref null $D)) $A)) - (type $B (struct_subtype (field (ref null $D)) $A)) - - ;; CHECK: (type $C (struct (field (mut (ref $A))))) - - ;; CHECK: (type $D (struct (field (mut (ref $A))) (field (mut (ref $A))))) - ;; NOMNL: (type $C (struct (field (mut (ref $A))))) - - ;; NOMNL: (type $D (struct_subtype (field (mut (ref $A))) (field (mut (ref $A))) $C)) - (type $D (struct_subtype (field (mut (ref $A))) (field (mut (ref $A))) $C)) - - (type $C (struct (field (mut (ref $A))))) - - - ;; CHECK: (func $foo (param $a (ref null $A)) (param $b (ref null $B)) (result (ref null $A)) - ;; CHECK-NEXT: (select (result (ref null $A)) - ;; CHECK-NEXT: (local.get $a) - ;; CHECK-NEXT: (local.get $b) - ;; CHECK-NEXT: (i32.const 0) - ;; CHECK-NEXT: ) - ;; CHECK-NEXT: ) - ;; NOMNL: (func $foo (type $ref?|$A|_ref?|$B|_=>_ref?|$A|) (param $a (ref null $A)) (param $b (ref null $B)) (result (ref null $A)) - ;; NOMNL-NEXT: (select (result (ref null $A)) - ;; NOMNL-NEXT: (local.get $a) - ;; NOMNL-NEXT: (local.get $b) - ;; NOMNL-NEXT: (i32.const 0) - ;; NOMNL-NEXT: ) - ;; NOMNL-NEXT: ) - (func $foo (param $a (ref null $A)) (param $b (ref null $B)) (result (ref null $A)) - ;; the select should have type $A - (select (result (ref null $A)) - ;; one arm has type $A - (local.get $a) - ;; one arm has type $B (a subtype of $A) - (local.get $b) - (i32.const 0) - ) - ) -) diff --git a/test/lit/nominal-good.wast b/test/lit/nominal-good.wast index ec64b466c..76863d637 100644 --- a/test/lit/nominal-good.wast +++ b/test/lit/nominal-good.wast @@ -1,69 +1,51 @@ ;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited. -;; RUN: wasm-opt %s -all --nominal -S -o - | filecheck %s --check-prefix NOMINAL -;; RUN: wasm-opt %s -all --nominal --roundtrip -S -o - | filecheck %s --check-prefix NOMINAL -;; RUN: wasm-opt %s -all --hybrid -S -o - | filecheck %s --check-prefix NOMINAL -;; RUN: wasm-opt %s -all --hybrid --roundtrip -S -o - | filecheck %s --check-prefix NOMINAL -;; RUN: wasm-opt %s -all --structural -S -o - | filecheck %s --check-prefix EQUIREC -;; RUN: wasm-opt %s -all --structural --roundtrip -S -o - | filecheck %s --check-prefix EQUIREC +;; RUN: wasm-opt %s -all --nominal -S -o - | filecheck %s --check-prefix CHECK +;; RUN: wasm-opt %s -all --nominal --roundtrip -S -o - | filecheck %s +;; RUN: wasm-opt %s -all --hybrid -S -o - | filecheck %s --check-prefix CHECK +;; RUN: wasm-opt %s -all --hybrid --roundtrip -S -o - | filecheck %s -;; Note that --hybrid and --nominal have the same output, so they share the NOMINAL prefix. +;; Note that --hybrid and --nominal have the same output, so they share the CHECK prefix. (module - ;; NOMINAL: (type $super-struct (struct (field i32))) - ;; EQUIREC: (type $super-struct (struct (field i32))) + ;; CHECK: (type $super-struct (struct (field i32))) (type $super-struct (struct i32)) - ;; NOMINAL: (type $sub-struct (struct_subtype (field i32) (field i64) $super-struct)) - ;; EQUIREC: (type $sub-struct (struct (field i32) (field i64))) + ;; CHECK: (type $sub-struct (struct_subtype (field i32) (field i64) $super-struct)) (type $sub-struct (struct_subtype i32 i64 $super-struct)) - ;; NOMINAL: (type $super-array (array (ref $super-struct))) - ;; EQUIREC: (type $super-array (array (ref $super-struct))) + ;; CHECK: (type $super-array (array (ref $super-struct))) (type $super-array (array (ref $super-struct))) - ;; NOMINAL: (type $sub-array (array_subtype (ref $sub-struct) $super-array)) - ;; EQUIREC: (type $sub-array (array (ref $sub-struct))) + ;; CHECK: (type $sub-array (array_subtype (ref $sub-struct) $super-array)) (type $sub-array (array_subtype (ref $sub-struct) $super-array)) ;; TODO: signature types as well, once functions store their HeapTypes. - ;; NOMINAL: (func $make-super-struct (type $none_=>_ref|$super-struct|) (result (ref $super-struct)) - ;; NOMINAL-NEXT: (call $make-sub-struct) - ;; NOMINAL-NEXT: ) - ;; EQUIREC: (func $make-super-struct (result (ref $super-struct)) - ;; EQUIREC-NEXT: (call $make-sub-struct) - ;; EQUIREC-NEXT: ) + ;; CHECK: (func $make-super-struct (type $none_=>_ref|$super-struct|) (result (ref $super-struct)) + ;; CHECK-NEXT: (call $make-sub-struct) + ;; CHECK-NEXT: ) (func $make-super-struct (result (ref $super-struct)) (call $make-sub-struct) ) - ;; NOMINAL: (func $make-sub-struct (type $none_=>_ref|$sub-struct|) (result (ref $sub-struct)) - ;; NOMINAL-NEXT: (unreachable) - ;; NOMINAL-NEXT: ) - ;; EQUIREC: (func $make-sub-struct (result (ref $sub-struct)) - ;; EQUIREC-NEXT: (unreachable) - ;; EQUIREC-NEXT: ) + ;; CHECK: (func $make-sub-struct (type $none_=>_ref|$sub-struct|) (result (ref $sub-struct)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) (func $make-sub-struct (result (ref $sub-struct)) (unreachable) ) - ;; NOMINAL: (func $make-super-array (type $none_=>_ref|$super-array|) (result (ref $super-array)) - ;; NOMINAL-NEXT: (call $make-sub-array) - ;; NOMINAL-NEXT: ) - ;; EQUIREC: (func $make-super-array (result (ref $super-array)) - ;; EQUIREC-NEXT: (call $make-sub-array) - ;; EQUIREC-NEXT: ) + ;; CHECK: (func $make-super-array (type $none_=>_ref|$super-array|) (result (ref $super-array)) + ;; CHECK-NEXT: (call $make-sub-array) + ;; CHECK-NEXT: ) (func $make-super-array (result (ref $super-array)) (call $make-sub-array) ) - ;; NOMINAL: (func $make-sub-array (type $none_=>_ref|$sub-array|) (result (ref $sub-array)) - ;; NOMINAL-NEXT: (unreachable) - ;; NOMINAL-NEXT: ) - ;; EQUIREC: (func $make-sub-array (result (ref $sub-array)) - ;; EQUIREC-NEXT: (unreachable) - ;; EQUIREC-NEXT: ) + ;; CHECK: (func $make-sub-array (type $none_=>_ref|$sub-array|) (result (ref $sub-array)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) (func $make-sub-array (result (ref $sub-array)) (unreachable) ) diff --git a/test/lit/recursive-type-sort.wast b/test/lit/recursive-type-sort.wast deleted file mode 100644 index 3b241fd96..000000000 --- a/test/lit/recursive-type-sort.wast +++ /dev/null @@ -1,30 +0,0 @@ -;; Test that multiple recursive types are sorted and emitted properly. -;; Regression test for a bug in TypeComparator that made it fail to properly -;; implement the C++ Compare requirements. See #3648. - -;; RUN: wasm-opt %s -all --roundtrip --structural -S -o - | filecheck %s -;; RUN: wasm-opt %s -all --roundtrip --nominal -S -o - | filecheck %s - -;; Check that there's no crash. -;; CHECK: module - -(module - (type $a (func (param (ref null $b)))) - (type $b (struct (field (ref null $i)))) - (type $c (struct (field (ref null $l)))) - (type $d (func (param (ref null $b)))) - (type $e (func (result (ref null $g)))) - (type $f (func (result (ref null $c)))) - (type $g (struct (field (ref null $j)))) - (type $h (struct (field (ref null $k)))) - (type $i (struct (field (mut (ref null $a))))) - (type $j (struct (field (mut (ref null $a))) (field (mut (ref null $a))))) - (type $k (struct (field (mut (ref null $a))) (field (mut (ref null $a))) (field (mut (ref null $e))))) - (type $l (struct (field (mut (ref null $a))) (field (mut (ref null $d))) (field (mut (ref null $f))))) - - (func $foo - (local $1 (ref null $h)) - (local $2 (ref null $b)) - (local $3 (ref null $c)) - ) -) |