diff options
| -rw-r--r-- | src/ir/type-updating.cpp | 2 | ||||
| -rw-r--r-- | src/ir/type-updating.h | 7 | ||||
| -rw-r--r-- | src/passes/TypeMerging.cpp | 468 | ||||
| -rw-r--r-- | test/lit/passes/type-merging-tnh.wast | 6 | ||||
| -rw-r--r-- | test/lit/passes/type-merging.wast | 350 |
5 files changed, 614 insertions, 219 deletions
diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp index 00f313a2a..67ec4a5c0 100644 --- a/src/ir/type-updating.cpp +++ b/src/ir/type-updating.cpp @@ -89,7 +89,7 @@ void GlobalTypeRewriter::update() { } // Apply a super, if there is one - if (auto super = type.getSuperType()) { + if (auto super = getSuperType(type)) { if (auto it = typeIndices.find(*super); it != typeIndices.end()) { assert(it->second < i); typeBuilder[i].subTypeOf(typeBuilder[it->second]); diff --git a/src/ir/type-updating.h b/src/ir/type-updating.h index 5cd8eef47..e1b5e42a9 100644 --- a/src/ir/type-updating.h +++ b/src/ir/type-updating.h @@ -357,6 +357,13 @@ public: virtual void modifyArray(HeapType oldType, Array& array) {} virtual void modifySignature(HeapType oldType, Signature& sig) {} + // Subclasses can override this method to modify supertypes. The new + // supertype, if any, must be a supertype (or the same as) the original + // supertype. + virtual std::optional<HeapType> getSuperType(HeapType oldType) { + return oldType.getSuperType(); + } + // Map an old type to a temp type. This can be called from the above hooks, // so that they can use a proper temp type of the TypeBuilder while modifying // things. diff --git a/src/passes/TypeMerging.cpp b/src/passes/TypeMerging.cpp index aa9fcca67..365a6c213 100644 --- a/src/passes/TypeMerging.cpp +++ b/src/passes/TypeMerging.cpp @@ -39,23 +39,33 @@ #include "ir/module-utils.h" #include "ir/type-updating.h" #include "pass.h" +#include "support/dfa_minimization.h" #include "support/small_set.h" +#include "support/topological_sort.h" #include "wasm-builder.h" +#include "wasm-type-ordering.h" #include "wasm.h" +#define TYPE_MERGING_DEBUG 0 + +#if TYPE_MERGING_DEBUG +#include "wasm-type-printing.h" +#endif + namespace wasm { namespace { -// We need to find all the types that have references to them, such as casts, -// as such types must be preserved - even if they are identical to other types, -// they are nominally distinguishable. +// We need to find all types that are distinguished from their supertypes by +// some kind of cast instruction. Merging these types with their supertypes +// would be an observable change. In contrast, types that are never used in +// casts are never distinguished from their supertypes. // Most functions do no casts, or perhaps cast |this| and perhaps a few others. -using ReferredTypes = SmallUnorderedSet<HeapType, 5>; +using CastTypes = SmallUnorderedSet<HeapType, 5>; struct CastFinder : public PostWalker<CastFinder> { - ReferredTypes referredTypes; + CastTypes castTypes; // If traps never happen, then ref.cast and call_indirect can never // differentiate between types since they always succeed. Take advantage of @@ -68,7 +78,7 @@ struct CastFinder : public PostWalker<CastFinder> { template<typename T> void visitCast(T* curr) { if (auto type = curr->getCastType(); type != Type::unreachable) { - referredTypes.insert(type.getHeapType()); + castTypes.insert(type.getHeapType()); } } @@ -88,188 +98,352 @@ struct CastFinder : public PostWalker<CastFinder> { void visitCallIndirect(CallIndirect* curr) { if (!trapsNeverHappen) { - referredTypes.insert(curr->heapType); + castTypes.insert(curr->heapType); } } }; +// We are going to treat the type graph as a partitioned DFA where each type is +// a state with transitions to its children. We will partition the DFA states so +// that types that may be mergeable will be in the same partition and types that +// we know are not mergeable will be in different partitions. Then we will +// refine the partitions so that types that turn out to not be mergeable will be +// split out into separate partitions. struct TypeMerging : public Pass { + using TypeUpdates = std::unordered_map<HeapType, HeapType>; + // Only modifies types. bool requiresNonNullableLocalFixups() override { return false; } Module* module; - // The types we can merge. We map each such type to merge with the type we - // want to merge it with. - using TypeUpdates = std::unordered_map<HeapType, HeapType>; - TypeUpdates merges; + std::unordered_set<HeapType> privateTypes; + CastTypes castTypes; - void run(Module* module_) override { - module = module_; + void run(Module* module_) override; - if (!module->features.hasGC()) { - return; - } + CastTypes findCastTypes(); + std::vector<HeapType> getPublicChildren(HeapType type); + DFA::State<HeapType> makeDFAState(HeapType type); + void applyMerges(const TypeUpdates& merges); - if (!getPassOptions().closedWorld) { - Fatal() << "TypeMerging requires --closed-world"; - } + bool mayBeMergeable(HeapType sub, HeapType super); + bool mayBeMergeable(const Struct& a, const Struct& b); + bool mayBeMergeable(Array a, Array b); + bool mayBeMergeable(Signature a, Signature b); + bool mayBeMergeable(Field a, Field b); + bool mayBeMergeable(Type a, Type b); + bool mayBeMergeable(const Tuple& a, const Tuple& b); +}; - // First, find all the cast types. +void TypeMerging::run(Module* module_) { + module = module_; - ModuleUtils::ParallelFunctionAnalysis<ReferredTypes> analysis( - *module, [&](Function* func, ReferredTypes& referredTypes) { - if (func->imported()) { - return; - } + if (!module->features.hasGC()) { + return; + } - CastFinder finder(getPassOptions()); - finder.walk(func->body); - referredTypes = std::move(finder.referredTypes); - }); - - // Also find cast types in the module scope (not possible in the current - // spec, but do it to be future-proof). - CastFinder moduleFinder(getPassOptions()); - moduleFinder.walkModuleCode(module); - - // Accumulate all the referredTypes. - auto& allReferredTypes = moduleFinder.referredTypes; - for (auto& [k, referredTypes] : analysis.map) { - for (auto type : referredTypes) { - allReferredTypes.insert(type); + if (!getPassOptions().closedWorld) { + Fatal() << "TypeMerging requires --closed-world"; + } + + // First, find all the cast types and private types. We will need these to + // determine whether types are eligible to be merged. + auto privates = ModuleUtils::getPrivateHeapTypes(*module); + privateTypes = std::unordered_set<HeapType>(privates.begin(), privates.end()); + castTypes = findCastTypes(); + + // Initial partitions are formed by grouping types with their structurally + // similar supertypes. Starting with the topmost types and working down the + // subtype trees, add each type to its supertype's partition if they are + // structurally compatible. + + // A list of partitions with stable iterators. + using Partition = std::vector<DFA::State<HeapType>>; + using Partitions = std::list<Partition>; + Partitions partitions; + + // Map each type to its partition in the list. + std::unordered_map<HeapType, Partitions::iterator> typePartitions; + +#if TYPE_MERGING_DEBUG + auto dumpPartitions = [&]() { + using Fallback = IndexedTypeNameGenerator<DefaultTypeNameGenerator>; + Fallback printPrivate(privates, "private."); + ModuleTypeNameGenerator<Fallback> print(*module, printPrivate); + size_t i = 0; + for (auto& partition : partitions) { + std::cerr << i++ << ": " << print(partition[0].val) << "\n"; + for (size_t j = 1; j < partition.size(); ++j) { + std::cerr << " " << print(partition[j].val) << "\n"; } + std::cerr << "\n"; + } + }; +#endif // TYPE_MERGING_DEBUG + + // Ensure the type has a partition and return a reference to it. + auto ensurePartition = [&](HeapType type) { + auto [it, inserted] = typePartitions.insert({type, partitions.end()}); + if (inserted) { + it->second = partitions.insert(partitions.end(), {makeDFAState(type)}); } + return it->second; + }; + + // For each type, either create a new partition or add to its supertype's + // partition. + for (auto type : HeapTypeOrdering::SupertypesFirst(privates)) { + // We need partitions for any public children of this type since those + // children will participate in the DFA we're creating. + for (auto child : getPublicChildren(type)) { + ensurePartition(child); + } + auto super = type.getSuperType(); + if (!super || !mayBeMergeable(type, *super)) { + // Create a new partition containing just this type. + ensurePartition(type); + continue; + } + // The current type and its supertype have the same top-level structure, so + // merge the current type's partition into its supertype's partition. First, + // find the supertype's partition. The supertype's partition may not exist + // yet if the supertype is public since we don't visit public types in this + // loop. In that case we can create a new partition for the supertype + // because merging private types into public supertypes is fine. (In + // contrast, merging public types into their supertypes is not fine.) + auto it = ensurePartition(*super); + it->push_back(makeDFAState(type)); + typePartitions[type] = it; + } - // Find all the heap types. - std::vector<HeapType> types = ModuleUtils::collectHeapTypes(*module); - - // TODO: There may be more opportunities after this loop. Imagine that we - // decide to merge A and B into C, and there are types X and Y that - // contain a nested reference to A and B respectively, then after A - // and B become identical so do X and Y. The recursive case is not - // trivial, however, and needs more thought. - for (auto type : types) { - if (allReferredTypes.count(type)) { - // This has a cast, so it is distinguishable nominally. - continue; - } +#if TYPE_MERGING_DEBUG + std::cerr << "Initial partitions:\n"; + dumpPartitions(); +#endif - auto super = type.getSuperType(); - if (!super) { - // This has no supertype, so there is nothing to merge it into. - continue; - } + // Construct and refine the partitioned DFA. + std::vector<Partition> dfa(std::make_move_iterator(partitions.begin()), + std::make_move_iterator(partitions.end())); + auto refinedPartitions = DFA::refinePartitions(dfa); - if (type.isStruct()) { - auto& fields = type.getStruct().fields; - auto& superFields = super->getStruct().fields; - if (fields == superFields) { - // We can merge! This is identical structurally to the super, and also - // not distinguishable nominally. - merges[type] = *super; - } - } else if (type.isArray()) { - auto element = type.getArray().element; - auto superElement = super->getArray().element; - if (element == superElement) { - merges[type] = *super; - } - } - } + // The types we can merge mapped to the type we are merging them into. + TypeUpdates merges; - if (merges.empty()) { - return; + // Merge each refined partition into a single type. + for (const auto& partition : refinedPartitions) { + for (size_t i = 1; i < partition.size(); ++i) { + merges[partition[i]] = partition[0]; } + } - // We found things to optimize! Rewrite types in the module to apply those - // changes. + applyMerges(merges); +} - // First, close over the map, so if X can be merged into Y and Y into Z then - // we map X into Z. - for (auto type : types) { - if (!merges.count(type)) { - continue; +CastTypes TypeMerging::findCastTypes() { + ModuleUtils::ParallelFunctionAnalysis<CastTypes> analysis( + *module, [&](Function* func, CastTypes& castTypes) { + if (func->imported()) { + return; } - auto newType = merges[type]; - while (merges.count(newType)) { - newType = merges[newType]; - } - // Apply the findings to all intermediate types as well, to avoid - // duplicate work in later iterations. That is, all the types we saw in - // the above loop will all get merged into newType. - auto curr = type; - while (1) { - auto iter = merges.find(curr); - if (iter == merges.end()) { - break; - } - auto& currMerge = iter->second; - curr = currMerge; - currMerge = newType; - } + CastFinder finder(getPassOptions()); + finder.walk(func->body); + castTypes = std::move(finder.castTypes); + }); + + // Also find cast types in the module scope (not possible in the current + // spec, but do it to be future-proof). + CastFinder moduleFinder(getPassOptions()); + moduleFinder.walkModuleCode(module); + + // Accumulate all the castTypes. + auto& allCastTypes = moduleFinder.castTypes; + for (auto& [k, castTypes] : analysis.map) { + for (auto type : castTypes) { + allCastTypes.insert(type); + } + } + return allCastTypes; +} + +std::vector<HeapType> TypeMerging::getPublicChildren(HeapType type) { + std::vector<HeapType> publicChildren; + for (auto child : type.getHeapTypeChildren()) { + if (!child.isBasic() && !privateTypes.count(child)) { + publicChildren.push_back(child); + } + } + return publicChildren; +} + +DFA::State<HeapType> TypeMerging::makeDFAState(HeapType type) { + std::vector<HeapType> succs; + for (auto child : type.getHeapTypeChildren()) { + // Both private and public heap type children participate in the DFA and are + // eligible to be successors. + if (!child.isBasic()) { + succs.push_back(child); } + } + return {type, std::move(succs)}; +} + +void TypeMerging::applyMerges(const TypeUpdates& merges) { + if (merges.empty()) { + return; + } - // Apply the merges. + // We found things to optimize! Rewrite types in the module to apply those + // changes. - class TypeInternalsUpdater : public GlobalTypeRewriter { - const TypeUpdates& merges; + class TypeInternalsUpdater : public GlobalTypeRewriter { + const TypeUpdates& merges; - std::unordered_map<HeapType, Signature> newSignatures; + std::unordered_map<HeapType, Signature> newSignatures; - public: - TypeInternalsUpdater(Module& wasm, const TypeUpdates& merges) - : GlobalTypeRewriter(wasm), merges(merges) { + public: + TypeInternalsUpdater(Module& wasm, const TypeUpdates& merges) + : GlobalTypeRewriter(wasm), merges(merges) { - // Map the types of expressions (curr->type, etc.) to their merged - // types. - mapTypes(merges); + // Map the types of expressions (curr->type, etc.) to their merged + // types. + mapTypes(merges); - // Update the internals of types (struct fields, signatures, etc.) to - // refer to the merged types. - update(); + // Update the internals of types (struct fields, signatures, etc.) to + // refer to the merged types. + update(); + } + + Type getNewType(Type type) { + if (!type.isRef()) { + return type; + } + auto heapType = type.getHeapType(); + auto iter = merges.find(heapType); + if (iter != merges.end()) { + return getTempType(Type(iter->second, type.getNullability())); } + return getTempType(type); + } - Type getNewType(Type type) { - if (!type.isRef()) { - return type; - } - auto heapType = type.getHeapType(); - auto iter = merges.find(heapType); - if (iter != merges.end()) { - return getTempType(Type(iter->second, type.getNullability())); - } - return getTempType(type); + void modifyStruct(HeapType oldType, Struct& struct_) override { + auto& oldFields = oldType.getStruct().fields; + for (Index i = 0; i < oldFields.size(); i++) { + auto& oldField = oldFields[i]; + auto& newField = struct_.fields[i]; + newField.type = getNewType(oldField.type); } + } + void modifyArray(HeapType oldType, Array& array) override { + array.element.type = getNewType(oldType.getArray().element.type); + } + void modifySignature(HeapType oldSignatureType, Signature& sig) override { + auto getUpdatedTypeList = [&](Type type) { + std::vector<Type> vec; + for (auto t : type) { + vec.push_back(getNewType(t)); + } + return getTempTupleType(vec); + }; - void modifyStruct(HeapType oldType, Struct& struct_) override { - auto& oldFields = oldType.getStruct().fields; - for (Index i = 0; i < oldFields.size(); i++) { - auto& oldField = oldFields[i]; - auto& newField = struct_.fields[i]; - newField.type = getNewType(oldField.type); + auto oldSig = oldSignatureType.getSignature(); + sig.params = getUpdatedTypeList(oldSig.params); + sig.results = getUpdatedTypeList(oldSig.results); + } + std::optional<HeapType> getSuperType(HeapType oldType) override { + auto super = oldType.getSuperType(); + if (super) { + if (auto it = merges.find(*super); it != merges.end()) { + return it->second; } } - void modifyArray(HeapType oldType, Array& array) override { - array.element.type = getNewType(oldType.getArray().element.type); - } - void modifySignature(HeapType oldSignatureType, Signature& sig) override { - auto getUpdatedTypeList = [&](Type type) { - std::vector<Type> vec; - for (auto t : type) { - vec.push_back(getNewType(t)); - } - return getTempTupleType(vec); - }; - - auto oldSig = oldSignatureType.getSignature(); - sig.params = getUpdatedTypeList(oldSig.params); - sig.results = getUpdatedTypeList(oldSig.results); - } - } rewriter(*module, merges); + return super; + } + } rewriter(*module, merges); +} + +bool TypeMerging::mayBeMergeable(HeapType sub, HeapType super) { + // If the type is distinguishable from its supertype or public, we cannot + // merge it. + if (castTypes.count(sub) || !privateTypes.count(sub)) { + return false; } -}; + // Check whether `sub` and `super` have the same top-level structure, + // including the position and identity of any children that are not included + // as transitions in the DFA, i.e. any children that are not nontrivial + // references. + if (sub.isStruct() && super.isStruct()) { + return mayBeMergeable(sub.getStruct(), super.getStruct()); + } + if (sub.isArray() && super.isArray()) { + return mayBeMergeable(sub.getArray(), super.getArray()); + } + if (sub.isSignature() && super.isSignature()) { + return mayBeMergeable(sub.getSignature(), super.getSignature()); + } + return false; +} + +bool TypeMerging::mayBeMergeable(const Struct& a, const Struct& b) { + if (a.fields.size() != b.fields.size()) { + return false; + } + for (size_t i = 0; i < a.fields.size(); ++i) { + if (!mayBeMergeable(a.fields[i], b.fields[i])) { + return false; + } + } + return true; +} + +bool TypeMerging::mayBeMergeable(Array a, Array b) { + return mayBeMergeable(a.element, b.element); +} + +bool TypeMerging::mayBeMergeable(Signature a, Signature b) { + return mayBeMergeable(a.params, b.params) && + mayBeMergeable(a.results, b.results); +} + +bool TypeMerging::mayBeMergeable(Field a, Field b) { + return a.packedType == b.packedType && mayBeMergeable(a.type, b.type); +} + +bool TypeMerging::mayBeMergeable(Type a, Type b) { + if (a == b) { + return true; + } + if (a.isTuple() && b.isTuple()) { + return mayBeMergeable(a.getTuple(), b.getTuple()); + } + // The only thing allowed to differ is the non-basic heap type child, since we + // don't know before running the DFA partition refinement whether different + // heap type children will end up being merged. Children that won't be merged + // will end up being differentiated by the partition refinement. + if (!a.isRef() || !b.isRef()) { + return false; + } + if (a.getHeapType().isBasic() || b.getHeapType().isBasic()) { + return false; + } + if (a.getNullability() != b.getNullability()) { + return false; + } + return true; +} + +bool TypeMerging::mayBeMergeable(const Tuple& a, const Tuple& b) { + if (a.types.size() != b.types.size()) { + return false; + } + for (size_t i = 0; i < a.types.size(); ++i) { + if (!mayBeMergeable(a.types[i], b.types[i])) { + return false; + } + } + return true; +} } // anonymous namespace diff --git a/test/lit/passes/type-merging-tnh.wast b/test/lit/passes/type-merging-tnh.wast index 5099760de..fefdb00e3 100644 --- a/test/lit/passes/type-merging-tnh.wast +++ b/test/lit/passes/type-merging-tnh.wast @@ -88,12 +88,10 @@ ) ) -;; call_indirect should not inhibit merging if traps never happen, but we -;; haven't implemented function type merging yet TODO. +;; call_indirect should not inhibit merging if traps never happen. (module ;; CHECK: (type $A (func)) (type $A (func)) - ;; CHECK: (type $B (func_subtype $A)) (type $B (func_subtype $A)) (table 1 1 (ref null $A)) @@ -101,7 +99,7 @@ ;; CHECK: (table $0 1 1 (ref null $A)) ;; CHECK: (func $test (type $A) - ;; CHECK-NEXT: (call_indirect $0 (type $B) + ;; CHECK-NEXT: (call_indirect $0 (type $A) ;; CHECK-NEXT: (i32.const 0) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) diff --git a/test/lit/passes/type-merging.wast b/test/lit/passes/type-merging.wast index b4b84f94a..578d84ebb 100644 --- a/test/lit/passes/type-merging.wast +++ b/test/lit/passes/type-merging.wast @@ -1,30 +1,41 @@ ;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited. -;; RUN: foreach %s %t wasm-opt --nominal --closed-world --type-merging -all -S -o - | filecheck %s +;; RUN: foreach %s %t wasm-opt --hybrid --closed-world --type-merging --remove-unused-types -all -S -o - | filecheck %s (module - ;; CHECK: (type $A (struct (field i32))) - (type $A (struct_subtype (field i32) data)) - (type $B (struct_subtype (field i32) $A)) - ;; CHECK: (type $D (struct_subtype (field i32) $A)) - - ;; CHECK: (type $none_=>_none (func)) + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (struct (field anyref))) + (type $A (struct_subtype (field anyref) data)) + (type $B (struct_subtype (field anyref) $A)) + ;; CHECK: (type $F (struct_subtype (field anyref) $A)) + + ;; CHECK: (type $E (struct_subtype (field eqref) $A)) + + ;; CHECK: (type $D (struct_subtype (field (ref any)) $A)) + + ;; CHECK: (type $C (struct_subtype (field anyref) (field f64) $A)) + (type $C (struct_subtype (field anyref) (field f64) $A)) + (type $D (struct_subtype (field (ref any)) $A)) + (type $E (struct_subtype (field eqref) $A)) + (type $F (struct_subtype (field anyref) $A)) + ) - ;; CHECK: (type $C (struct_subtype (field i32) (field f64) $A)) - (type $C (struct_subtype (field i32) (field f64) $A)) - (type $D (struct_subtype (field i32) $A)) + ;; CHECK: (type $none_=>_none (func)) ;; CHECK: (func $foo (type $none_=>_none) ;; CHECK-NEXT: (local $a (ref null $A)) ;; CHECK-NEXT: (local $b (ref null $A)) ;; CHECK-NEXT: (local $c (ref null $C)) ;; CHECK-NEXT: (local $d (ref null $D)) + ;; CHECK-NEXT: (local $e (ref null $E)) + ;; CHECK-NEXT: (local $f (ref null $F)) ;; CHECK-NEXT: (drop ;; CHECK-NEXT: (ref.cast null $A ;; CHECK-NEXT: (local.get $a) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) ;; CHECK-NEXT: (drop - ;; CHECK-NEXT: (ref.cast null $D + ;; CHECK-NEXT: (ref.cast null $F ;; CHECK-NEXT: (local.get $a) ;; CHECK-NEXT: ) ;; CHECK-NEXT: ) @@ -36,8 +47,12 @@ (local $b (ref null $B)) ;; $C cannot because it adds a field. (local $c (ref null $C)) - ;; $D cannot because it has a cast. + ;; $D cannot because it refines a field's nullability. (local $d (ref null $D)) + ;; $E cannot because it refines a field's heap type. + (local $e (ref null $E)) + ;; $F cannot because it has a cast. + (local $f (ref null $F)) ;; A cast of $A has no effect. (drop @@ -45,9 +60,9 @@ (local.get $a) ) ) - ;; A cast of $D prevents it from being merged. + ;; A cast of $F prevents it from being merged. (drop - (ref.cast null $D + (ref.cast null $F (local.get $a) ) ) @@ -56,17 +71,18 @@ ;; Multiple levels of merging. (module - ;; CHECK: (type $A (struct (field i32))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (struct (field i32))) (type $A (struct_subtype (field i32) data)) (type $B (struct_subtype (field i32) $A)) (type $C (struct_subtype (field i32) $B)) - ;; CHECK: (type $D (struct_subtype (field i32) (field f64) $A)) + ;; CHECK: (type $D (struct_subtype (field i32) (field f64) $A)) (type $D (struct_subtype (field i32) (field f64) $A)) (type $E (struct_subtype (field i32) (field f64) $D)) (type $F (struct_subtype (field i32) (field f64) $E)) (type $G (struct_subtype (field i32) (field f64) $F)) - ;; CHECK: (type $none_=>_none (func)) + ;; CHECK: (type $none_=>_none (func)) ;; CHECK: (func $foo (type $none_=>_none) ;; CHECK-NEXT: (local $a (ref null $A)) @@ -99,19 +115,18 @@ ;; in which we have two "merge points" that things get merged into. The results ;; should remain the same as before, everything merged into either $A or $D. (module - ;; CHECK: (type $A (struct (field i32))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (struct (field i32))) (type $A (struct_subtype (field i32) data)) - ;; CHECK: (type $B (struct_subtype (field i32) $A)) (type $B (struct_subtype (field i32) $A)) - ;; CHECK: (type $C (struct_subtype (field i32) $B)) (type $C (struct_subtype (field i32) $B)) - ;; CHECK: (type $D (struct_subtype (field i32) (field f64) $C)) + ;; CHECK: (type $D (struct_subtype (field i32) (field f64) $A)) (type $D (struct_subtype (field i32) (field f64) $C)) ;; this line changed (type $E (struct_subtype (field i32) (field f64) $D)) (type $F (struct_subtype (field i32) (field f64) $E)) (type $G (struct_subtype (field i32) (field f64) $F)) - ;; CHECK: (type $none_=>_none (func)) + ;; CHECK: (type $none_=>_none (func)) ;; CHECK: (func $foo (type $none_=>_none) ;; CHECK-NEXT: (local $a (ref null $A)) @@ -135,13 +150,17 @@ ) (module - ;; CHECK: (type $A (struct (field (ref null $A)))) - (type $A (struct_subtype (field (ref null $A)) data)) - (type $B (struct_subtype (field (ref null $A)) $A)) - ;; CHECK: (type $none_=>_none (func)) - - ;; CHECK: (type $C (struct_subtype (field (ref null $A)) $A)) - (type $C (struct_subtype (field (ref null $B)) $A)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $X (struct )) + (type $X (struct)) + (type $Y (struct_subtype $X)) + ;; CHECK: (type $A (struct (field (ref null $X)))) + (type $A (struct (field (ref null $X)))) + (type $B (struct_subtype (field (ref null $Y)) $A)) + ;; CHECK: (type $C (struct_subtype (field (ref $X)) $A)) + (type $C (struct_subtype (field (ref $Y)) $A)) + + ;; CHECK: (type $none_=>_none (func)) ;; CHECK: (func $foo (type $none_=>_none) ;; CHECK-NEXT: (local $a (ref null $A)) @@ -150,24 +169,136 @@ ;; CHECK-NEXT: (nop) ;; CHECK-NEXT: ) (func $foo - ;; $A will remain the same. + ;; B can be merged into A even though it refines A's field because that + ;; refinement will no longer happen after X and Y are also merged. + (local $a (ref null $A)) + (local $b (ref null $B)) + ;; C cannot be merged because it refines the field's nullability. + (local $c (ref null $C)) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (struct (field (ref null $A)))) + (type $A (struct (ref null $A))) + (type $B (struct_subtype (ref null $B) $A)) + + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (func $foo (type $none_=>_none) + ;; CHECK-NEXT: (local $a (ref null $A)) + ;; CHECK-NEXT: (local $b (ref null $A)) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $foo + ;; A recursive subtype can be merged even though its field is a refinement + ;; as well. + (local $a (ref null $A)) + (local $b (ref null $B)) + ) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $X (struct (field (ref null $A)) (field f32))) + + ;; CHECK: (type $A (struct (field (ref null $X)) (field i32))) + (type $A (struct (ref null $X) i32)) + (type $B (struct_subtype (ref null $Y) i32 $A)) + (type $X (struct (ref null $A) f32)) + (type $Y (struct_subtype (ref null $B) f32 $X)) + ) + + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (func $foo (type $none_=>_none) + ;; CHECK-NEXT: (local $a (ref null $A)) + ;; CHECK-NEXT: (local $b (ref null $A)) + ;; CHECK-NEXT: (local $x (ref null $X)) + ;; CHECK-NEXT: (local $y (ref null $X)) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $foo + ;; Two mutually referential chains, A->B and X->Y, can be merged into a pair + ;; of mutually referential types. + (local $a (ref null $A)) + (local $b (ref null $B)) + (local $x (ref null $X)) + (local $y (ref null $Y)) + ) +) + +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $X (struct (field (ref null $A)))) + + ;; CHECK: (type $A (struct (field (ref null $X)))) + (type $A (struct (ref null $X))) + (type $B (struct_subtype (ref null $Y) $A)) + (type $X (struct (ref null $A))) + (type $Y (struct_subtype (ref null $B) $X)) + ) + + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (func $foo (type $none_=>_none) + ;; CHECK-NEXT: (local $a (ref null $A)) + ;; CHECK-NEXT: (local $b (ref null $A)) + ;; CHECK-NEXT: (local $x (ref null $X)) + ;; CHECK-NEXT: (local $y (ref null $X)) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $foo + ;; As above, but now the A->B and X->Y chains are not differentiated by the + ;; i32 and f32, so all four types can be merged into a single type. + ;; TODO: This is not yet implemented. Merge the top level types. + (local $a (ref null $A)) + (local $b (ref null $B)) + (local $x (ref null $X)) + (local $y (ref null $Y)) + ) +) + +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $X (struct (field anyref))) + (type $X (struct anyref)) + ;; CHECK: (type $Y (struct_subtype (field eqref) $X)) + (type $Y (struct_subtype eqref $X)) + ;; CHECK: (type $A (struct (field (ref null $X)))) + (type $A (struct (ref null $X))) + ;; CHECK: (type $B (struct_subtype (field (ref null $Y)) $A)) + (type $B (struct_subtype (ref null $Y) $A)) + (type $C (struct_subtype (ref null $Y) $A)) + + ;; CHECK: (type $none_=>_none (func)) + + ;; CHECK: (func $foo (type $none_=>_none) + ;; CHECK-NEXT: (local $a (ref null $A)) + ;; CHECK-NEXT: (local $b (ref null $B)) + ;; CHECK-NEXT: (local $c (ref null $B)) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $foo + ;; B and C cannot be merged into A because they refine A's field, but B and + ;; C can still be merged with each other even though they are siblings. (local $a (ref null $A)) - ;; $B can be merged into $A. (local $b (ref null $B)) - ;; $C refines the field, so it cannot be merged. However, separately, in - ;; the type definition of $C, its field of type $B should become $A. That - ;; is, $B should no longer be used anywhere. (local $c (ref null $C)) ) ) ;; Check that we refinalize properly. (module - ;; CHECK: (type $A (struct )) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (struct )) (type $A (struct)) (type $B (struct_subtype $A)) - ;; CHECK: (type $none_=>_ref?|$A| (func (result (ref null $A)))) + ;; CHECK: (type $none_=>_ref?|$A| (func (result (ref null $A)))) ;; CHECK: (func $returner (type $none_=>_ref?|$A|) (result (ref null $A)) ;; CHECK-NEXT: (local $local (ref null $A)) @@ -189,24 +320,29 @@ ;; into $D. While doing so we must update the fields and the expressions that ;; they appear in, and not error. (module - ;; CHECK: (type $C (struct (field (mut i32)))) - - ;; CHECK: (type $D (struct_subtype (field (mut i32)) (field (mut i32)) $C)) - - ;; CHECK: (type $I (array (mut (ref null $C)))) - (type $I (array (mut (ref null $C)))) - (type $C (struct (field (mut i32)))) - (type $D (struct_subtype (field (mut i32)) (field (mut i32)) $C)) - (type $E (struct_subtype (field (mut i32)) (field (mut i32)) $D)) - (type $F (struct_subtype (field (mut i32)) (field (mut i32)) $E)) - (type $D$to-merge (struct_subtype (field (mut i32)) (field (mut i32)) $F)) - ;; CHECK: (type $G (func (param (ref $C)) (result (ref $D)))) - (type $G (func (param (ref $C)) (result (ref $D)))) - ;; CHECK: (type $H (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $D))) $D)) - (type $H (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) $D)) - ;; CHECK: (type $A (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $D))) (field (mut i64)) (field (mut (ref null $I))) $H)) - (type $A (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) (field (mut i64)) (field (mut (ref null $I))) $H)) - (type $A$to-merge (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) (field (mut i64)) (field (mut (ref null $I))) $A)) + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $C (struct (field (mut i32)))) + + ;; CHECK: (type $D (struct_subtype (field (mut i32)) (field (mut i32)) $C)) + + ;; CHECK: (type $H (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $D))) $D)) + + ;; CHECK: (type $A (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $D))) (field (mut i64)) (field (mut (ref null $I))) $H)) + + ;; CHECK: (type $I (array (mut (ref null $C)))) + (type $I (array (mut (ref null $C)))) + (type $C (struct (field (mut i32)))) + (type $D (struct_subtype (field (mut i32)) (field (mut i32)) $C)) + (type $E (struct_subtype (field (mut i32)) (field (mut i32)) $D)) + (type $F (struct_subtype (field (mut i32)) (field (mut i32)) $E)) + (type $D$to-merge (struct_subtype (field (mut i32)) (field (mut i32)) $F)) + ;; CHECK: (type $G (func (param (ref $C)) (result (ref $D)))) + (type $G (func (param (ref $C)) (result (ref $D)))) + (type $H (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) $D)) + (type $A (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) (field (mut i64)) (field (mut (ref null $I))) $H)) + (type $A$to-merge (struct_subtype (field (mut i32)) (field (mut i32)) (field (mut (ref null $E))) (field (mut i64)) (field (mut (ref null $I))) $A)) + ) ;; CHECK: (global $global$0 (ref $D) (struct.new $D ;; CHECK-NEXT: (i32.const 1705) @@ -238,18 +374,21 @@ ;; Arrays (module - ;; CHECK: (type $none_=>_none (func)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $refarray (array anyref)) - ;; CHECK: (type $intarray (array (mut i32))) + ;; CHECK: (type $sub-refarray-nn (array_subtype (ref any) $refarray)) + + ;; CHECK: (type $intarray (array (mut i32))) (type $intarray (array (mut i32))) (type $sub-intarray (array_subtype (mut i32) $intarray)) - ;; CHECK: (type $refarray (array anyref)) (type $refarray (array (ref null any))) (type $sub-refarray (array_subtype (ref null any) $refarray)) - ;; CHECK: (type $sub-refarray-nn (array_subtype (ref any) $refarray)) (type $sub-refarray-nn (array_subtype (ref any) $refarray)) + ;; CHECK: (type $none_=>_none (func)) + ;; CHECK: (func $foo (type $none_=>_none) ;; CHECK-NEXT: (local $a (ref null $intarray)) ;; CHECK-NEXT: (local $b (ref null $intarray)) @@ -277,15 +416,90 @@ ) ) -;; Check that a ref.test inhibits merging (ref.cast is already checked above). +;; Function types (module - ;; CHECK: (type $ref|$A|_=>_i32 (func (param (ref $A)) (result i32))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $func (func (param eqref))) + (type $func (func (param eqref))) + (type $sub-func (func_subtype (param eqref) $func)) + ;; CHECK: (type $sub-func-refined (func_subtype (param anyref) $func)) + (type $sub-func-refined (func_subtype (param anyref) $func)) + + ;; CHECK: (type $none_=>_none (func)) - ;; CHECK: (type $A (struct )) + ;; CHECK: (func $foo (type $none_=>_none) + ;; CHECK-NEXT: (local $a (ref null $func)) + ;; CHECK-NEXT: (local $b (ref null $func)) + ;; CHECK-NEXT: (local $c (ref null $sub-func-refined)) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: ) + (func $foo + ;; $func will remain the same. + (local $a (ref null $func)) + ;; $sub-func will be merged into $func. + (local $b (ref null $sub-func)) + ;; $sub-func-refined will not be merged into $func because it refines a result. + (local $c (ref null $sub-func-refined)) + ) +) + +;; Check that public types are not merged. +(module + ;; CHECK: (type $A (func)) + (type $A (func)) ;; public + ;; CHECK: (type $B (func_subtype $A)) + (type $B (func_subtype $A)) ;; public + (type $C (func_subtype $B)) ;; private + + ;; CHECK: (type $ref|$A|_ref|$B|_ref|$B|_=>_none (func (param (ref $A) (ref $B) (ref $B)))) + + ;; CHECK: (export "foo" (func $foo)) + (export "foo" (func $foo)) + ;; CHECK: (export "bar" (func $bar)) + (export "bar" (func $bar)) + + ;; A stays the same. + ;; CHECK: (func $foo (type $A) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $foo (type $A) + (unreachable) + ) + + ;; B is not merged because it is public. + ;; CHECK: (func $bar (type $B) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $bar (type $B) + (unreachable) + ) + + ;; C can be merged into B because it is private. + ;; CHECK: (func $baz (type $B) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $baz (type $C) + (unreachable) + ) + + ;; CHECK: (func $quux (type $ref|$A|_ref|$B|_ref|$B|_=>_none) (param $0 (ref $A)) (param $1 (ref $B)) (param $2 (ref $B)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $quux (param (ref $A) (ref $B) (ref $C)) + (unreachable) + ) +) + +;; Check that a ref.test inhibits merging (ref.cast is already checked above). +(module + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (struct )) (type $A (struct)) - ;; CHECK: (type $B (struct_subtype $A)) + ;; CHECK: (type $B (struct_subtype $A)) (type $B (struct_subtype $A)) + ;; CHECK: (type $ref|$A|_=>_i32 (func (param (ref $A)) (result i32))) + ;; CHECK: (func $test (type $ref|$A|_=>_i32) (param $a (ref $A)) (result i32) ;; CHECK-NEXT: (ref.test $B ;; CHECK-NEXT: (local.get $a) @@ -300,12 +514,13 @@ ;; Check that a br_on_cast inhibits merging. (module - ;; CHECK: (type $A (struct )) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (struct )) (type $A (struct)) - ;; CHECK: (type $B (struct_subtype $A)) + ;; CHECK: (type $B (struct_subtype $A)) (type $B (struct_subtype $A)) - ;; CHECK: (type $ref|$A|_=>_ref|$B| (func (param (ref $A)) (result (ref $B)))) + ;; CHECK: (type $ref|$A|_=>_ref|$B| (func (param (ref $A)) (result (ref $B)))) ;; CHECK: (func $test (type $ref|$A|_=>_ref|$B|) (param $a (ref $A)) (result (ref $B)) ;; CHECK-NEXT: (block $__binaryen_fake_return (result (ref $B)) @@ -346,9 +561,10 @@ ;; Check that a call_indirect inhibits merging. (module - ;; CHECK: (type $A (func)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $A (func)) (type $A (func)) - ;; CHECK: (type $B (func_subtype $A)) + ;; CHECK: (type $B (func_subtype $A)) (type $B (func_subtype $A)) (table 1 1 (ref null $A)) |