diff options
| -rwxr-xr-x | scripts/fuzz_opt.py | 1 | ||||
| -rw-r--r-- | src/passes/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/passes/MinimizeRecGroups.cpp | 802 | ||||
| -rw-r--r-- | src/passes/pass.cpp | 3 | ||||
| -rw-r--r-- | src/passes/passes.h | 1 | ||||
| -rw-r--r-- | src/wasm/wasm-type-shape.cpp | 1 | ||||
| -rw-r--r-- | test/lit/help/wasm-metadce.test | 3 | ||||
| -rw-r--r-- | test/lit/help/wasm-opt.test | 3 | ||||
| -rw-r--r-- | test/lit/help/wasm2js.test | 3 | ||||
| -rw-r--r-- | test/lit/passes/minimize-rec-groups-brands.wast | 1378 | ||||
| -rw-r--r-- | test/lit/passes/minimize-rec-groups.wast | 486 |
11 files changed, 2682 insertions, 0 deletions
diff --git a/scripts/fuzz_opt.py b/scripts/fuzz_opt.py index 4087abed1..28426f773 100755 --- a/scripts/fuzz_opt.py +++ b/scripts/fuzz_opt.py @@ -1571,6 +1571,7 @@ opt_choices = [ ('--monomorphize', '--pass-arg=monomorphize-min-benefit@50'), ('--monomorphize', '--pass-arg=monomorphize-min-benefit@95'), ('--monomorphize-always',), + ('--minimize-rec-groups',), ('--no-stack-ir',), ('--once-reduction',), ("--optimize-casts",), diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt index 703b27e05..54f044057 100644 --- a/src/passes/CMakeLists.txt +++ b/src/passes/CMakeLists.txt @@ -67,6 +67,7 @@ set(passes_SOURCES MergeLocals.cpp Metrics.cpp MinifyImportsAndExports.cpp + MinimizeRecGroups.cpp Monomorphize.cpp MultiMemoryLowering.cpp NameList.cpp diff --git a/src/passes/MinimizeRecGroups.cpp b/src/passes/MinimizeRecGroups.cpp new file mode 100644 index 000000000..728cb306e --- /dev/null +++ b/src/passes/MinimizeRecGroups.cpp @@ -0,0 +1,802 @@ +/* + * Copyright 2024 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// Split types into minimal recursion groups by computing the strongly connected +// components of the type graph, which are the minimal sets of +// mutually-recursive types that must be in the same recursion group with each +// other for the type section to validate. +// +// We must additionally ensure that distinct types remain distinct, which would +// not be the case if we allowed two separate strongly connected components with +// the same shape to be rewritten to two copies of the same recursion group. +// Accidentally merging types would be incorrect because it would change the +// behavior of casts that would have previously been able to differentiate the +// types. +// +// When multiple strongly connected components have the same shape, first try to +// differentiate them by permuting their types, which keeps the sizes of the rec +// groups as small as possible. When there are more strongly connected +// components that are permutations of one another than there are distinct +// permutations, fall back to keeping the types distinct by adding distinct +// brand types to the recursion groups to ensure they have different shapes. +// +// There are several possible algorithmic design for detecting when to generate +// permutations and determining what permutations to generate. They trade off +// the amount of "wasted" work spent generating shapes that have already been +// used with the amount of work spent trying to avoid the wasted work and with +// the quality of the output. +// +// The simplest possible design that avoids all "wasted" work would be to +// canonicalize the shape of each group to eagerly detect isomorphisms and +// eagerly organize the groups into equivalence classes. This would allow us to +// avoid ever generating permutations of a group with shapes that have already +// been used. See `getCanonicalPermutation` below for details on how this works. +// However, this is not an ideal solution because canonicalization is an +// expensive operation and in the common case a group's shape will not conflict +// with any other group's shape, so canonicalization itself would be wasted +// work. +// +// The simplest possible design in the other direction is to never canonicalize +// and instead to lazily build up equivalences classes of isomorphic groups when +// shape conflicts are detected in practice. Conflicts are resolved by choosing +// the next permutation generated by the representative element of the +// equivalence class. This solution is not ideal because groups with high +// symmetry can have very many permutations that have the same shape, so many +// permutations might need to be generated before finding one that is distinct +// from previous permutations with respect to its shape. This work can be +// sidestepped by instead eagerly advancing the brand type, but that increases +// the code size of the output. +// +// The design chosen here is a hybrid of those two designs that is slightly more +// complicated, but gets the best of both worlds. We lazily detect equivalence +// classes of groups without eager shape canonicalization like in the second +// design, but we canonicalize the shape for any equivalence class that grows +// larger than one group like in the first design. This ensures that we don't +// spend time canonicalizing in the common case where there are no shape +// conflicts, but it also ensures that we don't waste time generating +// permutations with shapes that conflict with the shapes of previous groups. It +// also allows us to avoid compromising on the quality of the output. + +#include "ir/module-utils.h" +#include "ir/type-updating.h" +#include "pass.h" +#include "support/disjoint_sets.h" +#include "support/strongly_connected_components.h" +#include "support/topological_orders.h" +#include "wasm-type-shape.h" +#include "wasm.h" + +namespace wasm { + +namespace { + +// Compute the strongly connected components of the private types, being sure to +// only consider edges to other private types. +struct TypeSCCs + : SCCs<typename std::vector<HeapType>::const_iterator, TypeSCCs> { + std::unordered_set<HeapType> includedTypes; + TypeSCCs(const std::vector<HeapType>& types) + : SCCs(types.begin(), types.end()), + includedTypes(types.cbegin(), types.cend()) {} + void pushChildren(HeapType parent) { + for (auto child : parent.getReferencedHeapTypes()) { + if (includedTypes.count(child)) { + push(child); + } + } + } +}; + +// After all their permutations with distinct shapes have been used, different +// groups with the same shapes must be differentiated by adding in a "brand" +// type. Even with a brand mixed in, we might run out of permutations with +// distinct shapes, in which case we need a new brand type. This iterator +// provides an infinite sequence of possible brand types, prioritizing those +// with the most compact encoding. +struct BrandTypeIterator { + // See `initFieldOptions` for the 18 options. + static constexpr size_t optionCount = 18; + static std::array<Field, optionCount> fieldOptions; + static void initFieldOptions(); + + struct FieldInfo { + uint8_t index = 0; + bool immutable = false; + + operator Field() const { + auto field = fieldOptions[index]; + if (immutable) { + field.mutable_ = Immutable; + } + return field; + } + + bool advance() { + if (!immutable) { + immutable = true; + return true; + } + immutable = false; + index = (index + 1) % optionCount; + return index != 0; + } + }; + + bool useArray = false; + std::vector<FieldInfo> fields; + + HeapType operator*() const { + if (useArray) { + return Array(fields[0]); + } + return Struct(std::vector<Field>(fields.begin(), fields.end())); + } + + BrandTypeIterator& operator++() { + for (size_t i = fields.size(); i > 0; --i) { + if (fields[i - 1].advance()) { + return *this; + } + } + if (useArray) { + useArray = false; + return *this; + } + fields.emplace_back(); + useArray = fields.size() == 1; + return *this; + } +}; + +// Create an adjacency list with edges from supertype to subtypes. +std::vector<std::vector<size_t>> +createSubtypeGraph(const std::vector<HeapType>& types) { + std::unordered_map<HeapType, size_t> indices; + for (auto type : types) { + indices.insert({type, indices.size()}); + } + + std::vector<std::vector<size_t>> subtypeGraph(types.size()); + for (size_t i = 0; i < types.size(); ++i) { + if (auto super = types[i].getDeclaredSuperType()) { + if (auto it = indices.find(*super); it != indices.end()) { + subtypeGraph[it->second].push_back(i); + } + } + } + return subtypeGraph; +} + +struct RecGroupInfo; + +// As we iterate through the strongly connected components, we may find +// components that have the same shape. When we find such a collision, we merge +// the groups for the components into a single equivalence class where we track +// how we have disambiguated all such isomorphic groups. +struct GroupClassInfo { + // If the group has just a single type, record it so we can make sure the + // brand is not identical to it. + std::optional<HeapType> singletonType; + // If we have gone through all the permutations of this group with distinct + // shapes, we need to add a brand type to continue differentiating different + // groups in the class. + std::optional<BrandTypeIterator> brand; + // An adjacency list giving edges from supertypes to subtypes within the + // group, using indices into the (non-materialized) canonical shape of this + // group, offset by 1 iff there is a brand type. Used to ensure that we only + // find emit permutations that respect the constraint that supertypes must be + // ordered before subtypes. + std::vector<std::vector<size_t>> subtypeGraph; + // A generator of valid permutations of the components in this class. + TopologicalOrders orders; + + // Initialize `subtypeGraph` and `orders` based on the canonical ordering + // encoded by the group and permutation in `info`. + static std::vector<std::vector<size_t>> initSubtypeGraph(RecGroupInfo& info); + GroupClassInfo(RecGroupInfo& info); + + void advance() { + ++orders; + if (orders == orders.end()) { + advanceBrand(); + } + } + + void advanceBrand() { + if (brand) { + ++*brand; + } else { + brand.emplace(); + // Make room in the subtype graph for the brand type, which goes at the + // beginning of the canonical order. + subtypeGraph.insert(subtypeGraph.begin(), {{}}); + // Adjust indices. + for (size_t i = 1; i < subtypeGraph.size(); ++i) { + for (auto& edge : subtypeGraph[i]) { + ++edge; + } + } + } + // Make sure the brand is not the same as the real type. + if (singletonType && + RecGroupShape({**brand}) == RecGroupShape({*singletonType})) { + ++*brand; + } + // Start back at the initial permutation with the new brand. + orders.~TopologicalOrders(); + new (&orders) TopologicalOrders(subtypeGraph); + } + + // Permute the types in the given group to match the current configuration in + // this GroupClassInfo. + void permute(RecGroupInfo&); +}; + +// The information we keep for each produced rec group. +struct RecGroupInfo { + // The sequence of input types to be rewritten into this output group. + std::vector<HeapType> group; + // The permutation of the canonical shape for this group's class used to + // arrive at this group's shape. Used when we later find another strongly + // connected component with this shape to apply the inverse permutation and + // get that other component's types into the canonical shape before using a + // fresh permutation to re-shuffle them into their final shape. Only set for + // groups belonging to nontrivial equivalence classes. + std::vector<size_t> permutation; + // Does this group include a brand type that does not correspond to a type in + // the original module? + bool hasBrand = false; + // This group may be the representative group for its nontrivial equivalence + // class, in which case it holds the necessary extra information used to add + // new groups to the class. + std::optional<GroupClassInfo> classInfo; +}; + +std::vector<std::vector<size_t>> +GroupClassInfo::initSubtypeGraph(RecGroupInfo& info) { + assert(!info.classInfo); + assert(info.permutation.size() == info.group.size()); + + std::vector<HeapType> canonical(info.group.size()); + for (size_t i = 0; i < info.group.size(); ++i) { + canonical[info.permutation[i]] = info.group[i]; + } + + return createSubtypeGraph(canonical); +} + +GroupClassInfo::GroupClassInfo(RecGroupInfo& info) + : singletonType(info.group.size() == 1 + ? std::optional<HeapType>(info.group[0]) + : std::nullopt), + brand(std::nullopt), subtypeGraph(initSubtypeGraph(info)), + orders(subtypeGraph) {} + +void GroupClassInfo::permute(RecGroupInfo& info) { + assert(info.group.size() == info.permutation.size()); + bool insertingBrand = info.group.size() < subtypeGraph.size(); + // First, un-permute the group to get back to the canonical order, offset by 1 + // if we are newly inserting a brand. + std::vector<HeapType> canonical(info.group.size() + insertingBrand); + for (size_t i = 0; i < info.group.size(); ++i) { + canonical[info.permutation[i] + insertingBrand] = info.group[i]; + } + // Update the brand. + if (brand) { + canonical[0] = **brand; + } + if (insertingBrand) { + info.group.resize(info.group.size() + 1); + info.hasBrand = true; + } + // Finally, re-permute with the new permutation.. + info.permutation = *orders; + for (size_t i = 0; i < info.group.size(); ++i) { + info.group[i] = canonical[info.permutation[i]]; + } +} + +std::array<Field, BrandTypeIterator::optionCount> + BrandTypeIterator::fieldOptions = {{}}; + +void BrandTypeIterator::initFieldOptions() { + BrandTypeIterator::fieldOptions = {{ + Field(Field::i8, Mutable), + Field(Field::i16, Mutable), + Field(Type::i32, Mutable), + Field(Type::i64, Mutable), + Field(Type::f32, Mutable), + Field(Type::f64, Mutable), + Field(Type(HeapType::any, Nullable), Mutable), + Field(Type(HeapType::func, Nullable), Mutable), + Field(Type(HeapType::ext, Nullable), Mutable), + Field(Type(HeapType::none, Nullable), Mutable), + Field(Type(HeapType::nofunc, Nullable), Mutable), + Field(Type(HeapType::noext, Nullable), Mutable), + Field(Type(HeapType::any, NonNullable), Mutable), + Field(Type(HeapType::func, NonNullable), Mutable), + Field(Type(HeapType::ext, NonNullable), Mutable), + Field(Type(HeapType::none, NonNullable), Mutable), + Field(Type(HeapType::nofunc, NonNullable), Mutable), + Field(Type(HeapType::noext, NonNullable), Mutable), + }}; +} + +struct MinimizeRecGroups : Pass { + // The types we are optimizing and their indices in this list. + std::vector<HeapType> types; + + // A global ordering on all types, including public types. Used to define a + // total ordering on rec group shapes. + std::unordered_map<HeapType, size_t> typeIndices; + + // As we process strongly connected components, we will construct output + // recursion groups here. + std::vector<RecGroupInfo> groups; + + // For each shape of rec group we have created, its index in `groups`. + std::unordered_map<RecGroupShape, size_t> groupShapeIndices; + + // When we find that two groups are isomorphic to (i.e. permutations of) each + // other, we combine their equivalence classes and choose a new class + // representative to use to disambiguate the groups and any further groups + // that will join the class. + DisjointSets equivalenceClasses; + + // When we see a new group, we have to make sure its shape doesn't conflict + // with the shape of any existing group. If there is a conflict, we need to + // update the group's shape and try again. Maintain a stack of group indices + // whose shapes we need to check for uniqueness to avoid deep recursions. + std::vector<size_t> shapesToUpdate; + + void run(Module* module) override { + // There are no recursion groups to minimize if GC is not enabled. + if (!module->features.hasGC()) { + return; + } + + initBrandOptions(); + + types = ModuleUtils::getPrivateHeapTypes(*module); + for (auto type : ModuleUtils::collectHeapTypes(*module)) { + typeIndices.insert({type, typeIndices.size()}); + } + + // The number of types to optimize is an upper bound on the number of + // recursion groups we will emit. + groups.reserve(types.size()); + + // Compute the strongly connected components and ensure they form distinct + // recursion groups. + for (auto scc : TypeSCCs(types)) { + [[maybe_unused]] size_t index = equivalenceClasses.addSet(); + assert(index == groups.size()); + groups.emplace_back(); + + // The SCC is not necessarily topologically sorted to have the supertypes + // come first. Fix that. + std::vector<HeapType> sccTypes(scc.begin(), scc.end()); + auto deps = createSubtypeGraph(sccTypes); + auto permutation = *TopologicalOrders(deps).begin(); + groups.back().group.resize(sccTypes.size()); + for (size_t i = 0; i < sccTypes.size(); ++i) { + groups.back().group[i] = sccTypes[permutation[i]]; + } + assert(shapesToUpdate.empty()); + shapesToUpdate.push_back(index); + updateShapes(); + } + + rewriteTypes(*module); + } + + void initBrandOptions() { + // Initialize the field options for brand types lazily here to avoid + // depending on global constructor ordering. + [[maybe_unused]] static bool fieldsInitialized = []() { + BrandTypeIterator::initFieldOptions(); + return true; + }(); + } + + void updateShapes() { + while (!shapesToUpdate.empty()) { + auto index = shapesToUpdate.back(); + shapesToUpdate.pop_back(); + updateShape(index); + } + } + + void updateShape(size_t group) { + auto [it, inserted] = + groupShapeIndices.insert({RecGroupShape(groups[group].group), group}); + if (inserted) { + // This shape was unique. We're done. + return; + } + + // We have a conflict. There are five possibilities: + // + // 1. We are trying to insert the next permutation of an existing + // equivalence class and have found that... + // + // A. The next permutation has the same shape as some previous + // permutation in the same equivalence class. + // + // B. The next permutation has the same shape as some other group + // already in a different nontrivial equivalent class. + // + // C. The next permutation has the same shape as some other group + // not yet included in a nontrivial equivalence class. + // + // 2. We are inserting a new group not yet affiliated with a + // nontrivial equivalence class and have found that... + // + // A. It has the same shape as some group in an existing nontrivial + // equivalence class. + // + // B. It has the same shape as some other group also not yet affiliated + // with a nontrivial equivalence class, so we will form a new + // nontrivial equivalence class. + // + // These possibilities are handled in order below. + + size_t other = it->second; + + auto& groupInfo = groups[group]; + auto& otherInfo = groups[other]; + + size_t groupRep = equivalenceClasses.getRoot(group); + size_t otherRep = equivalenceClasses.getRoot(other); + + // Case 1A: We have found a permutation of this group that has the same + // shape as a previous permutation of this group. Skip the rest of the + // permutations, which will also have the same shapes as previous + // permutations. + if (groupRep == otherRep) { + assert(groups[groupRep].classInfo); + auto& classInfo = *groups[groupRep].classInfo; + + // Move to the next permutation after advancing the type brand to skip + // further repeated shapes. + classInfo.advanceBrand(); + classInfo.permute(groupInfo); + + shapesToUpdate.push_back(group); + return; + } + + // Case 1B: There is a shape conflict with a group from a different + // nontrivial equivalence class. Because we canonicalize the shapes whenever + // we first create a nontrivial equivalence class, this is usually not + // possible; two equivalence classes with groups of the same shape should + // actually be the same equivalence class. The exception is when there is a + // group in each class whose brand matches the base type of the other class. + // In this case we don't actually want to join the classes; we just want to + // advance the current group to the next permutation to resolve the + // conflict. + if (groups[groupRep].classInfo && groups[otherRep].classInfo) { + auto& classInfo = *groups[groupRep].classInfo; + classInfo.advance(); + classInfo.permute(groupInfo); + shapesToUpdate.push_back(group); + return; + } + + // Case 1C: The current group belongs to a nontrivial equivalence class and + // has the same shape as some other group unaffiliated with a nontrivial + // equivalence class. Bring that other group into our equivalence class and + // advance the current group to the next permutation to resolve the + // conflict. + if (groups[groupRep].classInfo) { + auto& classInfo = *groups[groupRep].classInfo; + + [[maybe_unused]] size_t unionRep = + equivalenceClasses.getUnion(groupRep, otherRep); + assert(groupRep == unionRep); + + // `other` must have the same permutation as `group` because they have the + // same shape. Advance `group` to the next permutation. + otherInfo.classInfo = std::nullopt; + otherInfo.permutation = groupInfo.permutation; + classInfo.advance(); + classInfo.permute(groupInfo); + + shapesToUpdate.push_back(group); + return; + } + + // Case 2A: The shape of the current group is already found in an existing + // nontrivial equivalence class. Join the class and advance to the next + // permutation to resolve the conflict. + if (groups[otherRep].classInfo) { + auto& classInfo = *groups[otherRep].classInfo; + + [[maybe_unused]] size_t unionRep = + equivalenceClasses.getUnion(otherRep, groupRep); + assert(otherRep == unionRep); + + // Since we matched shapes with `other`, unapplying its permutation gets + // us back to the canonical shape, from which we can apply a fresh + // permutation. + groupInfo.classInfo = std::nullopt; + groupInfo.permutation = otherInfo.permutation; + classInfo.advance(); + classInfo.permute(groupInfo); + + shapesToUpdate.push_back(group); + return; + } + + // Case 2B: We need to join two groups with matching shapes into a new + // nontrivial equivalence class. + assert(!groups[groupRep].classInfo && !groups[otherRep].classInfo); + assert(group == groupRep && other == otherRep); + + // We are canonicalizing and reinserting the shape for other, so remove it + // from the map under its current shape. + groupShapeIndices.erase(it); + + // Put the types for both groups into the canonical order. + auto permutation = getCanonicalPermutation(groupInfo.group); + groupInfo.permutation = otherInfo.permutation = std::move(permutation); + + // Set up `other` to be the representative element of the equivalence class. + otherInfo.classInfo.emplace(otherInfo); + auto& classInfo = *otherInfo.classInfo; + + // Update both groups to have the initial valid order. Their shapes still + // match. + classInfo.permute(otherInfo); + classInfo.permute(groupInfo); + + // Insert `other` with its new shape. It may end up being joined to another + // existing equivalence class, in which case its class info will be cleared + // and `group` will subsequently be added to that same existing class, or + // alternatively it may be inserted as the representative element of a new + // class to which `group` will subsequently be joined. + shapesToUpdate.push_back(group); + shapesToUpdate.push_back(other); + } + + std::vector<size_t> + getCanonicalPermutation(const std::vector<HeapType>& types) { + // The correctness of this part depends on some interesting properties of + // strongly connected graphs with ordered, directed edges. A permutation of + // the vertices in a graph is an isomorphism that produces an isomorphic + // graph. An automorphism is an isomorphism of a structure onto itself, so + // an automorphism of a graph is a permutation of the vertices that does not + // change the label-independent properties of a graph. Permutations can be + // described in terms of sets of cycles of elements. + // + // As an example, consider this strongly-connected recursion group: + // + // (rec + // (type $a1 (struct (field (ref $a2) (ref $b1)))) + // (type $a2 (struct (field (ref $a1) (ref $b2)))) + // (type $b1 (struct (field (ref $b2) (ref $a1)))) + // (type $b2 (struct (field (ref $b1) (ref $a2)))) + // ) + // + // This group has one nontrivial automorphism: ($a1 $a2) ($b1 $b2). Applying + // this automorphism gives this recursion group: + // + // (rec + // (type $a2 (struct (field (ref $a1) (ref $b2)))) + // (type $a1 (struct (field (ref $a2) (ref $b1)))) + // (type $b2 (struct (field (ref $b1) (ref $a2)))) + // (type $b1 (struct (field (ref $b2) (ref $a1)))) + // ) + // + // We can verify that the permutation was an automorphism by checking that + // the label-independent properties of these two rec groups are the same. + // Indeed, when we write the adjacency matrices with ordered edges for the + // two graphs, they both come out to this: + // + // 0: _ 0 1 _ + // 1: 0 _ _ 1 + // 2: 1 _ _ 0 + // 3: _ 1 0 _ + // + // In addition to having the same adjacency matrix, the two recursion groups + // have the same vertex colorings since all of their types have the same + // top-level structure. Since the label-independent properties of the + // recursion groups (i.e. all the properties except the intended type + // identity at each index) are the same, the permutation that takes one + // group to the other is an automorphism. These are precisely the + // permutations that do not change a recursion group's shape, so would not + // change type identity under WebAssembly's isorecursive type system. In + // other words, automorphisms cannot help us resolve shape conflicts, so we + // want to avoid generating them. + // + // Theorem 1: All cycles in an automorphism of a strongly-connected + // recursion group are the same size. + // + // Proof: By contradiction. Assume there are two cycles of different + // sizes. Because the group is strongly connected, there is a path from + // an element in the smaller of these cycles to an element in the + // larger. This path must contain an edge between two vertices in cycles + // of different sizes N and M such that N < M. Apply the automorphism N + // times. The source of this edge has been cycled back to its original + // index, but the destination is not yet back at its original index, so + // the edge's destination index is different from its original + // destination index and the permutation we applied was not an + // automorphism after all. + // + // Corollary 1.1: No nontrivial automorphism of an SCC may have a stationary + // element, since either all the cycles have size 1 and the automorphism is + // trivial or all the cycles have some other size and there are no + // stationary elements. + // + // Corollary 1.2: No two distinct permutations of an SCC with the same first + // element (e.g. both with some type $t as the first element) have the same + // shape, since no nontrivial automorphism can keep the first element + // stationary while mapping one permutation to the other. + // + // Find a canonical ordering of the types in this group. The ordering must + // be independent of the initial order of the types. To do so, consider the + // orderings given by visitation order on a tree search rooted at each type + // in the group. Since the group is strongly connected, a tree search from + // any of types will visit all types in the group, so it will generate a + // total and deterministic ordering of the types in the group. We can + // compare the shapes of each of these orderings to organize the root + // types and their generated orderings into ordered equivalence classes. + // These equivalence classes each correspond to a cycle in an automorphism + // of the graph because their elements are vertices that can all occupy the + // initial index of the graph without the graph structure changing. We can + // choose an arbitrary ordering from the least equivalence class as a + // canonical ordering because all orderings in that class describe the same + // label-independent graph. + // + // Compute the orderings generated by DFS on each type. + std::unordered_set<HeapType> typeSet(types.begin(), types.end()); + std::vector<std::vector<HeapType>> dfsOrders(types.size()); + for (size_t i = 0; i < types.size(); ++i) { + dfsOrders[i].reserve(types.size()); + std::vector<HeapType> workList; + workList.push_back(types[i]); + std::unordered_set<HeapType> seen; + while (!workList.empty()) { + auto curr = workList.back(); + workList.pop_back(); + if (!typeSet.count(curr)) { + continue; + } + if (seen.insert(curr).second) { + dfsOrders[i].push_back(curr); + auto children = curr.getReferencedHeapTypes(); + workList.insert(workList.end(), children.rbegin(), children.rend()); + } + } + assert(dfsOrders[i].size() == types.size()); + } + + // Organize the orderings into equivalence classes, mapping equivalent + // shapes to lists of automorphically equivalent root types. + std::map<ComparableRecGroupShape, std::vector<HeapType>> typeClasses; + for (const auto& order : dfsOrders) { + ComparableRecGroupShape shape(order, [this](HeapType a, HeapType b) { + return this->typeIndices.at(a) < this->typeIndices.at(b); + }); + typeClasses[shape].push_back(order[0]); + } + + // Choose the initial canonical ordering. + const auto& leastOrder = typeClasses.begin()->first.types; + + // We want our canonical ordering to have the additional property that it + // contains one type from each equivalence class before a second type of any + // equivalence class. Since our utility for enumerating the topological + // sorts of the canonical order keeps the initial element fixed as long as + // possible before moving to the next one, by Corollary 1.2 and because + // permutations that begin with types in different equivalence class cannot + // have the same shape (otherwise those initial types would be in the same + // equivalence class), this will maximize the number of distinct shapes the + // utility emits before starting to emit permutations that have the same + // shapes as previous permutations. Since all the type equivalence classes + // are the same size by Theorem 1, we can assemble the final order by + // striping across the equivalence classes. We determine the order of types + // taken from each equivalence class by sorting them by order of appearance + // in the least order, which ensures the final order remains independent of + // the initial order. + std::unordered_map<HeapType, size_t> indexInLeastOrder; + for (auto type : leastOrder) { + indexInLeastOrder.insert({type, indexInLeastOrder.size()}); + } + auto classSize = typeClasses.begin()->second.size(); + for (auto& [shape, members] : typeClasses) { + assert(members.size() == classSize); + std::sort(members.begin(), members.end(), [&](HeapType a, HeapType b) { + return indexInLeastOrder.at(a) < indexInLeastOrder.at(b); + }); + } + std::vector<HeapType> finalOrder; + finalOrder.reserve(types.size()); + for (size_t i = 0; i < classSize; ++i) { + for (auto& [shape, members] : typeClasses) { + finalOrder.push_back(members[i]); + } + } + + // Now what we actually want is the permutation that takes us from the final + // canonical order to the original order of the types. + std::unordered_map<HeapType, size_t> indexInFinalOrder; + for (auto type : finalOrder) { + indexInFinalOrder.insert({type, indexInFinalOrder.size()}); + } + std::vector<size_t> permutation; + permutation.reserve(types.size()); + for (auto type : types) { + permutation.push_back(indexInFinalOrder.at(type)); + } + return permutation; + } + + void rewriteTypes(Module& wasm) { + // Map types to indices in the builder. + std::unordered_map<HeapType, size_t> outputIndices; + size_t i = 0; + for (const auto& group : groups) { + for (size_t j = 0; j < group.group.size(); ++j) { + // Skip the brand if it exists. + if (!group.hasBrand || group.permutation[j] != 0) { + outputIndices.insert({group.group[j], i}); + } + ++i; + } + } + + // Build the types. + TypeBuilder builder(i); + i = 0; + for (const auto& group : groups) { + builder.createRecGroup(i, group.group.size()); + for (auto type : group.group) { + builder[i++].copy(type, [&](HeapType ht) -> HeapType { + if (auto it = outputIndices.find(ht); it != outputIndices.end()) { + return builder[it->second]; + } + return ht; + }); + } + } + auto built = builder.build(); + assert(built); + auto newTypes = *built; + + // Replace the types in the module. + std::unordered_map<HeapType, HeapType> oldToNew; + i = 0; + for (const auto& group : groups) { + for (size_t j = 0; j < group.group.size(); ++j) { + // Skip the brand again if it exists. + if (!group.hasBrand || group.permutation[j] != 0) { + oldToNew[group.group[j]] = newTypes[i]; + } + ++i; + } + } + GlobalTypeRewriter rewriter(wasm); + rewriter.mapTypes(oldToNew); + rewriter.mapTypeNames(oldToNew); + } +}; + +} // anonymous namespace + +Pass* createMinimizeRecGroupsPass() { return new MinimizeRecGroups(); } + +} // namespace wasm diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 3f84ee604..ccfc7b728 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -290,6 +290,9 @@ void PassRegistry::registerPasses() { "minifies both import and export names, and emits a mapping to " "the minified ones, and minifies the modules as well", createMinifyImportsAndExportsAndModulesPass); + registerPass("minimize-rec-groups", + "Split types into minimal recursion groups", + createMinimizeRecGroupsPass); registerPass("mod-asyncify-always-and-only-unwind", "apply the assumption that asyncify imports always unwind, " "and we never rewind", diff --git a/src/passes/passes.h b/src/passes/passes.h index bd3aabf9f..9fcb5f95f 100644 --- a/src/passes/passes.h +++ b/src/passes/passes.h @@ -88,6 +88,7 @@ Pass* createMinifiedPrinterPass(); Pass* createMinifyImportsPass(); Pass* createMinifyImportsAndExportsPass(); Pass* createMinifyImportsAndExportsAndModulesPass(); +Pass* createMinimizeRecGroupsPass(); Pass* createMetricsPass(); Pass* createMonomorphizePass(); Pass* createMonomorphizeAlwaysPass(); diff --git a/src/wasm/wasm-type-shape.cpp b/src/wasm/wasm-type-shape.cpp index 99398bb7b..b1f74d491 100644 --- a/src/wasm/wasm-type-shape.cpp +++ b/src/wasm/wasm-type-shape.cpp @@ -187,6 +187,7 @@ template<typename CompareTypes> struct RecGroupComparator { if (indexA != indexB) { return indexA < indexB ? LT : GT; } + return EQ; } // These types are external to the group, so fall back to the provided // comparator. diff --git a/test/lit/help/wasm-metadce.test b/test/lit/help/wasm-metadce.test index 8a2107ca7..c40f2e22b 100644 --- a/test/lit/help/wasm-metadce.test +++ b/test/lit/help/wasm-metadce.test @@ -269,6 +269,9 @@ ;; CHECK-NEXT: the minified ones, and minifies ;; CHECK-NEXT: the modules as well ;; CHECK-NEXT: +;; CHECK-NEXT: --minimize-rec-groups Split types into minimal +;; CHECK-NEXT: recursion groups +;; CHECK-NEXT: ;; CHECK-NEXT: --mod-asyncify-always-and-only-unwind apply the assumption that ;; CHECK-NEXT: asyncify imports always unwind, ;; CHECK-NEXT: and we never rewind diff --git a/test/lit/help/wasm-opt.test b/test/lit/help/wasm-opt.test index a48b8e303..a1df2640a 100644 --- a/test/lit/help/wasm-opt.test +++ b/test/lit/help/wasm-opt.test @@ -278,6 +278,9 @@ ;; CHECK-NEXT: the minified ones, and minifies ;; CHECK-NEXT: the modules as well ;; CHECK-NEXT: +;; CHECK-NEXT: --minimize-rec-groups Split types into minimal +;; CHECK-NEXT: recursion groups +;; CHECK-NEXT: ;; CHECK-NEXT: --mod-asyncify-always-and-only-unwind apply the assumption that ;; CHECK-NEXT: asyncify imports always unwind, ;; CHECK-NEXT: and we never rewind diff --git a/test/lit/help/wasm2js.test b/test/lit/help/wasm2js.test index 0b87ad0aa..beefdbbd7 100644 --- a/test/lit/help/wasm2js.test +++ b/test/lit/help/wasm2js.test @@ -232,6 +232,9 @@ ;; CHECK-NEXT: the minified ones, and minifies ;; CHECK-NEXT: the modules as well ;; CHECK-NEXT: +;; CHECK-NEXT: --minimize-rec-groups Split types into minimal +;; CHECK-NEXT: recursion groups +;; CHECK-NEXT: ;; CHECK-NEXT: --mod-asyncify-always-and-only-unwind apply the assumption that ;; CHECK-NEXT: asyncify imports always unwind, ;; CHECK-NEXT: and we never rewind diff --git a/test/lit/passes/minimize-rec-groups-brands.wast b/test/lit/passes/minimize-rec-groups-brands.wast new file mode 100644 index 000000000..861f88705 --- /dev/null +++ b/test/lit/passes/minimize-rec-groups-brands.wast @@ -0,0 +1,1378 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited. +;; RUN: wasm-opt %s -all --minimize-rec-groups -S -o - | filecheck %s + +;; Check that brands increment correctly once we get into structs with multiple +;; fields. This requires very many duplicate SCCs. + +(module + (rec + ;; CHECK: (type $0 (struct)) + (type $0 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $10 (struct)) + + ;; CHECK: (type $200 (array (mut i32))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $201 (array i32)) + + ;; CHECK: (type $11 (struct)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $12 (struct)) + + ;; CHECK: (type $204 (array i32)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $205 (array (mut i64))) + + ;; CHECK: (type $13 (struct)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $14 (struct)) + + ;; CHECK: (type $208 (array (mut i64))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $209 (array i64)) + + ;; CHECK: (type $15 (struct)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $16 (struct)) + + ;; CHECK: (type $212 (array i64)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $213 (array (mut f32))) + + ;; CHECK: (type $17 (struct)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $18 (struct)) + + ;; CHECK: (type $216 (array (mut f32))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $217 (array f32)) + + ;; CHECK: (type $19 (struct)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $219 (array (mut i8))) + + ;; CHECK: (type $1 (struct)) + (type $1 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $2 (struct)) + (type $2 (struct)) + ;; CHECK: (type $222 (array (mut i8))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $223 (array i8)) + + ;; CHECK: (type $3 (struct)) + (type $3 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $4 (struct)) + (type $4 (struct)) + ;; CHECK: (type $226 (array i8)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $227 (array (mut i16))) + + ;; CHECK: (type $5 (struct)) + (type $5 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $6 (struct)) + (type $6 (struct)) + ;; CHECK: (type $230 (array (mut i16))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $231 (array i16)) + + ;; CHECK: (type $7 (struct)) + (type $7 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $8 (struct)) + (type $8 (struct)) + ;; CHECK: (type $234 (array i16)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $235 (array (mut i32))) + + ;; CHECK: (type $9 (struct)) + (type $9 (struct)) + (type $10 (struct)) + (type $11 (struct)) + (type $12 (struct)) + (type $13 (struct)) + (type $14 (struct)) + (type $15 (struct)) + (type $16 (struct)) + (type $17 (struct)) + (type $18 (struct)) + (type $19 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $20 (struct)) + (type $20 (struct)) + ;; CHECK: (type $238 (array f32)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $239 (array (mut f64))) + + ;; CHECK: (type $21 (struct)) + (type $21 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $22 (struct)) + (type $22 (struct)) + ;; CHECK: (type $242 (array (mut f64))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $243 (array f64)) + + ;; CHECK: (type $23 (struct)) + (type $23 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $24 (struct)) + (type $24 (struct)) + ;; CHECK: (type $246 (array f64)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $247 (array (mut anyref))) + + ;; CHECK: (type $25 (struct)) + (type $25 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $26 (struct)) + (type $26 (struct)) + ;; CHECK: (type $250 (array (mut anyref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $251 (array anyref)) + + ;; CHECK: (type $27 (struct)) + (type $27 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $28 (struct)) + (type $28 (struct)) + ;; CHECK: (type $254 (array anyref)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $255 (array (mut funcref))) + + ;; CHECK: (type $29 (struct)) + (type $29 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $30 (struct)) + (type $30 (struct)) + ;; CHECK: (type $258 (array (mut funcref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $259 (array funcref)) + + ;; CHECK: (type $31 (struct)) + (type $31 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $32 (struct)) + (type $32 (struct)) + ;; CHECK: (type $262 (array funcref)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $263 (array (mut externref))) + + ;; CHECK: (type $33 (struct)) + (type $33 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $34 (struct)) + (type $34 (struct)) + ;; CHECK: (type $266 (array (mut externref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $267 (array externref)) + + ;; CHECK: (type $35 (struct)) + (type $35 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $36 (struct)) + (type $36 (struct)) + ;; CHECK: (type $270 (array externref)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $271 (array (mut nullref))) + + ;; CHECK: (type $37 (struct)) + (type $37 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $38 (struct)) + (type $38 (struct)) + ;; CHECK: (type $274 (array (mut nullref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $275 (array nullref)) + + ;; CHECK: (type $39 (struct)) + (type $39 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $40 (struct)) + (type $40 (struct)) + ;; CHECK: (type $278 (array nullref)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $279 (array (mut nullfuncref))) + + ;; CHECK: (type $41 (struct)) + (type $41 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $42 (struct)) + (type $42 (struct)) + ;; CHECK: (type $282 (array (mut nullfuncref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $283 (array nullfuncref)) + + ;; CHECK: (type $43 (struct)) + (type $43 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $44 (struct)) + (type $44 (struct)) + ;; CHECK: (type $286 (array nullfuncref)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $287 (array (mut nullexternref))) + + ;; CHECK: (type $45 (struct)) + (type $45 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $46 (struct)) + (type $46 (struct)) + ;; CHECK: (type $290 (array (mut nullexternref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $291 (array nullexternref)) + + ;; CHECK: (type $47 (struct)) + (type $47 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $48 (struct)) + (type $48 (struct)) + ;; CHECK: (type $294 (array nullexternref)) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $295 (array (mut (ref any)))) + + ;; CHECK: (type $49 (struct)) + (type $49 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $50 (struct)) + (type $50 (struct)) + ;; CHECK: (type $298 (array (mut (ref any)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $299 (array (ref any))) + + ;; CHECK: (type $51 (struct)) + (type $51 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $52 (struct)) + (type $52 (struct)) + ;; CHECK: (type $302 (array (ref any))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $303 (array (mut (ref func)))) + + ;; CHECK: (type $53 (struct)) + (type $53 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $54 (struct)) + (type $54 (struct)) + ;; CHECK: (type $306 (array (mut (ref func)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $307 (array (ref func))) + + ;; CHECK: (type $55 (struct)) + (type $55 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $56 (struct)) + (type $56 (struct)) + ;; CHECK: (type $310 (array (ref func))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $311 (array (mut (ref extern)))) + + ;; CHECK: (type $57 (struct)) + (type $57 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $58 (struct)) + (type $58 (struct)) + ;; CHECK: (type $314 (array (mut (ref extern)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $315 (array (ref extern))) + + ;; CHECK: (type $59 (struct)) + (type $59 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $60 (struct)) + (type $60 (struct)) + ;; CHECK: (type $318 (array (ref extern))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $319 (array (mut (ref none)))) + + ;; CHECK: (type $61 (struct)) + (type $61 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $62 (struct)) + (type $62 (struct)) + ;; CHECK: (type $322 (array (mut (ref none)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $323 (array (ref none))) + + ;; CHECK: (type $63 (struct)) + (type $63 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $64 (struct)) + (type $64 (struct)) + ;; CHECK: (type $326 (array (ref none))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $327 (array (mut (ref nofunc)))) + + ;; CHECK: (type $65 (struct)) + (type $65 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $66 (struct)) + (type $66 (struct)) + ;; CHECK: (type $330 (array (mut (ref nofunc)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $331 (array (ref nofunc))) + + ;; CHECK: (type $67 (struct)) + (type $67 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $68 (struct)) + (type $68 (struct)) + ;; CHECK: (type $334 (array (ref nofunc))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $335 (array (mut (ref noextern)))) + + ;; CHECK: (type $69 (struct)) + (type $69 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $70 (struct)) + (type $70 (struct)) + ;; CHECK: (type $338 (array (mut (ref noextern)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $339 (array (ref noextern))) + + ;; CHECK: (type $71 (struct)) + (type $71 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $72 (struct)) + (type $72 (struct)) + ;; CHECK: (type $342 (array (ref noextern))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $343 (struct (field (mut i8)))) + + ;; CHECK: (type $73 (struct)) + (type $73 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $74 (struct)) + (type $74 (struct)) + ;; CHECK: (type $346 (struct (field (mut i8)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $347 (struct (field i8))) + + ;; CHECK: (type $75 (struct)) + (type $75 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $76 (struct)) + (type $76 (struct)) + ;; CHECK: (type $350 (struct (field i8))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $351 (struct (field (mut i16)))) + + ;; CHECK: (type $77 (struct)) + (type $77 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $78 (struct)) + (type $78 (struct)) + ;; CHECK: (type $354 (struct (field (mut i16)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $355 (struct (field i16))) + + ;; CHECK: (type $79 (struct)) + (type $79 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $80 (struct)) + (type $80 (struct)) + ;; CHECK: (type $358 (struct (field i16))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $359 (struct (field (mut i32)))) + + ;; CHECK: (type $81 (struct)) + (type $81 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $82 (struct)) + (type $82 (struct)) + ;; CHECK: (type $362 (struct (field (mut i32)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $363 (struct (field i32))) + + ;; CHECK: (type $83 (struct)) + (type $83 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $84 (struct)) + (type $84 (struct)) + ;; CHECK: (type $366 (struct (field i32))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $367 (struct (field (mut i64)))) + + ;; CHECK: (type $85 (struct)) + (type $85 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $86 (struct)) + (type $86 (struct)) + ;; CHECK: (type $370 (struct (field (mut i64)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $371 (struct (field i64))) + + ;; CHECK: (type $87 (struct)) + (type $87 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $88 (struct)) + (type $88 (struct)) + ;; CHECK: (type $374 (struct (field i64))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $375 (struct (field (mut f32)))) + + ;; CHECK: (type $89 (struct)) + (type $89 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $90 (struct)) + (type $90 (struct)) + ;; CHECK: (type $378 (struct (field (mut f32)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $379 (struct (field f32))) + + ;; CHECK: (type $91 (struct)) + (type $91 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $92 (struct)) + (type $92 (struct)) + ;; CHECK: (type $382 (struct (field f32))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $383 (struct (field (mut f64)))) + + ;; CHECK: (type $93 (struct)) + (type $93 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $94 (struct)) + (type $94 (struct)) + ;; CHECK: (type $386 (struct (field (mut f64)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $387 (struct (field f64))) + + ;; CHECK: (type $95 (struct)) + (type $95 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $96 (struct)) + (type $96 (struct)) + ;; CHECK: (type $390 (struct (field f64))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $391 (struct (field (mut anyref)))) + + ;; CHECK: (type $97 (struct)) + (type $97 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $98 (struct)) + (type $98 (struct)) + ;; CHECK: (type $394 (struct (field (mut anyref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $395 (struct (field anyref))) + + ;; CHECK: (type $99 (struct)) + (type $99 (struct)) + (type $100 (struct)) + (type $101 (struct)) + (type $102 (struct)) + (type $103 (struct)) + (type $104 (struct)) + (type $105 (struct)) + (type $106 (struct)) + (type $107 (struct)) + (type $108 (struct)) + (type $109 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $110 (struct)) + (type $110 (struct)) + ;; CHECK: (type $398 (struct (field anyref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $399 (struct (field (mut funcref)))) + + ;; CHECK: (type $111 (struct)) + (type $111 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $112 (struct)) + (type $112 (struct)) + ;; CHECK: (type $402 (struct (field (mut funcref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $403 (struct (field funcref))) + + ;; CHECK: (type $113 (struct)) + (type $113 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $114 (struct)) + (type $114 (struct)) + ;; CHECK: (type $406 (struct (field funcref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $407 (struct (field (mut externref)))) + + ;; CHECK: (type $115 (struct)) + (type $115 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $116 (struct)) + (type $116 (struct)) + ;; CHECK: (type $410 (struct (field (mut externref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $411 (struct (field externref))) + + ;; CHECK: (type $117 (struct)) + (type $117 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $118 (struct)) + (type $118 (struct)) + ;; CHECK: (type $414 (struct (field externref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $415 (struct (field (mut nullref)))) + + ;; CHECK: (type $119 (struct)) + (type $119 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $120 (struct)) + (type $120 (struct)) + ;; CHECK: (type $418 (struct (field (mut nullref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $419 (struct (field nullref))) + + ;; CHECK: (type $121 (struct)) + (type $121 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $122 (struct)) + (type $122 (struct)) + ;; CHECK: (type $422 (struct (field nullref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $423 (struct (field (mut nullfuncref)))) + + ;; CHECK: (type $123 (struct)) + (type $123 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $124 (struct)) + (type $124 (struct)) + ;; CHECK: (type $426 (struct (field (mut nullfuncref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $427 (struct (field nullfuncref))) + + ;; CHECK: (type $125 (struct)) + (type $125 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $126 (struct)) + (type $126 (struct)) + ;; CHECK: (type $430 (struct (field nullfuncref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $431 (struct (field (mut nullexternref)))) + + ;; CHECK: (type $127 (struct)) + (type $127 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $128 (struct)) + (type $128 (struct)) + ;; CHECK: (type $434 (struct (field (mut nullexternref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $435 (struct (field nullexternref))) + + ;; CHECK: (type $129 (struct)) + (type $129 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $130 (struct)) + (type $130 (struct)) + ;; CHECK: (type $438 (struct (field nullexternref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $439 (struct (field (mut (ref any))))) + + ;; CHECK: (type $131 (struct)) + (type $131 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $132 (struct)) + (type $132 (struct)) + ;; CHECK: (type $442 (struct (field (mut (ref any))))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $443 (struct (field (ref any)))) + + ;; CHECK: (type $133 (struct)) + (type $133 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $134 (struct)) + (type $134 (struct)) + ;; CHECK: (type $446 (struct (field (ref any)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $447 (struct (field (mut (ref func))))) + + ;; CHECK: (type $135 (struct)) + (type $135 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $136 (struct)) + (type $136 (struct)) + ;; CHECK: (type $450 (struct (field (mut (ref func))))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $451 (struct (field (ref func)))) + + ;; CHECK: (type $137 (struct)) + (type $137 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $138 (struct)) + (type $138 (struct)) + ;; CHECK: (type $454 (struct (field (ref func)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $455 (struct (field (mut (ref extern))))) + + ;; CHECK: (type $139 (struct)) + (type $139 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $140 (struct)) + (type $140 (struct)) + ;; CHECK: (type $458 (struct (field (mut (ref extern))))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $459 (struct (field (ref extern)))) + + ;; CHECK: (type $141 (struct)) + (type $141 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $142 (struct)) + (type $142 (struct)) + ;; CHECK: (type $462 (struct (field (ref extern)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $463 (struct (field (mut (ref none))))) + + ;; CHECK: (type $143 (struct)) + (type $143 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $144 (struct)) + (type $144 (struct)) + ;; CHECK: (type $466 (struct (field (mut (ref none))))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $467 (struct (field (ref none)))) + + ;; CHECK: (type $145 (struct)) + (type $145 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $146 (struct)) + (type $146 (struct)) + ;; CHECK: (type $470 (struct (field (ref none)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $471 (struct (field (mut (ref nofunc))))) + + ;; CHECK: (type $147 (struct)) + (type $147 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $148 (struct)) + (type $148 (struct)) + ;; CHECK: (type $474 (struct (field (mut (ref nofunc))))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $475 (struct (field (ref nofunc)))) + + ;; CHECK: (type $149 (struct)) + (type $149 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $150 (struct)) + (type $150 (struct)) + ;; CHECK: (type $478 (struct (field (ref nofunc)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $479 (struct (field (mut (ref noextern))))) + + ;; CHECK: (type $151 (struct)) + (type $151 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $152 (struct)) + (type $152 (struct)) + ;; CHECK: (type $482 (struct (field (mut (ref noextern))))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $483 (struct (field (ref noextern)))) + + ;; CHECK: (type $153 (struct)) + (type $153 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $154 (struct)) + (type $154 (struct)) + ;; CHECK: (type $486 (struct (field (ref noextern)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $487 (struct (field (mut i8)) (field (mut i8)))) + + ;; CHECK: (type $155 (struct)) + (type $155 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $156 (struct)) + (type $156 (struct)) + ;; CHECK: (type $490 (struct (field (mut i8)) (field (mut i8)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $491 (struct (field (mut i8)) (field i8))) + + ;; CHECK: (type $157 (struct)) + (type $157 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $158 (struct)) + (type $158 (struct)) + ;; CHECK: (type $494 (struct (field (mut i8)) (field i8))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $495 (struct (field (mut i8)) (field (mut i16)))) + + ;; CHECK: (type $159 (struct)) + (type $159 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $160 (struct)) + (type $160 (struct)) + ;; CHECK: (type $498 (struct (field (mut i8)) (field (mut i16)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $499 (struct (field (mut i8)) (field i16))) + + ;; CHECK: (type $161 (struct)) + (type $161 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $162 (struct)) + (type $162 (struct)) + ;; CHECK: (type $502 (struct (field (mut i8)) (field i16))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $503 (struct (field (mut i8)) (field (mut i32)))) + + ;; CHECK: (type $163 (struct)) + (type $163 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $164 (struct)) + (type $164 (struct)) + ;; CHECK: (type $506 (struct (field (mut i8)) (field (mut i32)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $507 (struct (field (mut i8)) (field i32))) + + ;; CHECK: (type $165 (struct)) + (type $165 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $166 (struct)) + (type $166 (struct)) + ;; CHECK: (type $510 (struct (field (mut i8)) (field i32))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $511 (struct (field (mut i8)) (field (mut i64)))) + + ;; CHECK: (type $167 (struct)) + (type $167 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $168 (struct)) + (type $168 (struct)) + ;; CHECK: (type $514 (struct (field (mut i8)) (field (mut i64)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $515 (struct (field (mut i8)) (field i64))) + + ;; CHECK: (type $169 (struct)) + (type $169 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $170 (struct)) + (type $170 (struct)) + ;; CHECK: (type $518 (struct (field (mut i8)) (field i64))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $519 (struct (field (mut i8)) (field (mut f32)))) + + ;; CHECK: (type $171 (struct)) + (type $171 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $172 (struct)) + (type $172 (struct)) + ;; CHECK: (type $522 (struct (field (mut i8)) (field (mut f32)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $523 (struct (field (mut i8)) (field f32))) + + ;; CHECK: (type $173 (struct)) + (type $173 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $174 (struct)) + (type $174 (struct)) + ;; CHECK: (type $526 (struct (field (mut i8)) (field f32))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $527 (struct (field (mut i8)) (field (mut f64)))) + + ;; CHECK: (type $175 (struct)) + (type $175 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $176 (struct)) + (type $176 (struct)) + ;; CHECK: (type $530 (struct (field (mut i8)) (field (mut f64)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $531 (struct (field (mut i8)) (field f64))) + + ;; CHECK: (type $177 (struct)) + (type $177 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $178 (struct)) + (type $178 (struct)) + ;; CHECK: (type $534 (struct (field (mut i8)) (field f64))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $535 (struct (field (mut i8)) (field (mut anyref)))) + + ;; CHECK: (type $179 (struct)) + (type $179 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $180 (struct)) + (type $180 (struct)) + ;; CHECK: (type $538 (struct (field (mut i8)) (field (mut anyref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $539 (struct (field (mut i8)) (field anyref))) + + ;; CHECK: (type $181 (struct)) + (type $181 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $182 (struct)) + (type $182 (struct)) + ;; CHECK: (type $542 (struct (field (mut i8)) (field anyref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $543 (struct (field (mut i8)) (field (mut funcref)))) + + ;; CHECK: (type $183 (struct)) + (type $183 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $184 (struct)) + (type $184 (struct)) + ;; CHECK: (type $546 (struct (field (mut i8)) (field (mut funcref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $547 (struct (field (mut i8)) (field funcref))) + + ;; CHECK: (type $185 (struct)) + (type $185 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $186 (struct)) + (type $186 (struct)) + ;; CHECK: (type $550 (struct (field (mut i8)) (field funcref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $551 (struct (field (mut i8)) (field (mut externref)))) + + ;; CHECK: (type $187 (struct)) + (type $187 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $188 (struct)) + (type $188 (struct)) + ;; CHECK: (type $554 (struct (field (mut i8)) (field (mut externref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $555 (struct (field (mut i8)) (field externref))) + + ;; CHECK: (type $189 (struct)) + (type $189 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $190 (struct)) + (type $190 (struct)) + ;; CHECK: (type $558 (struct (field (mut i8)) (field externref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $559 (struct (field (mut i8)) (field (mut nullref)))) + + ;; CHECK: (type $191 (struct)) + (type $191 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $192 (struct)) + (type $192 (struct)) + ;; CHECK: (type $562 (struct (field (mut i8)) (field (mut nullref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $563 (struct (field (mut i8)) (field nullref))) + + ;; CHECK: (type $193 (struct)) + (type $193 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $194 (struct)) + (type $194 (struct)) + ;; CHECK: (type $566 (struct (field (mut i8)) (field nullref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $567 (struct (field (mut i8)) (field (mut nullfuncref)))) + + ;; CHECK: (type $195 (struct)) + (type $195 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $196 (struct)) + (type $196 (struct)) + ;; CHECK: (type $570 (struct (field (mut i8)) (field (mut nullfuncref)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $571 (struct (field (mut i8)) (field nullfuncref))) + + ;; CHECK: (type $197 (struct)) + (type $197 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $198 (struct)) + (type $198 (struct)) + ;; CHECK: (type $574 (struct (field (mut i8)) (field nullfuncref))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $575 (struct (field (mut i8)) (field (mut nullexternref)))) + + ;; CHECK: (type $199 (struct)) + (type $199 (struct)) + ) + + ;; CHECK: (global $0 (ref null $0) (ref.null none)) + (global $0 (ref null $0) (ref.null none)) + ;; CHECK: (global $1 (ref null $1) (ref.null none)) + (global $1 (ref null $1) (ref.null none)) + ;; CHECK: (global $2 (ref null $2) (ref.null none)) + (global $2 (ref null $2) (ref.null none)) + ;; CHECK: (global $3 (ref null $3) (ref.null none)) + (global $3 (ref null $3) (ref.null none)) + ;; CHECK: (global $4 (ref null $4) (ref.null none)) + (global $4 (ref null $4) (ref.null none)) + ;; CHECK: (global $5 (ref null $5) (ref.null none)) + (global $5 (ref null $5) (ref.null none)) + ;; CHECK: (global $6 (ref null $6) (ref.null none)) + (global $6 (ref null $6) (ref.null none)) + ;; CHECK: (global $7 (ref null $7) (ref.null none)) + (global $7 (ref null $7) (ref.null none)) + ;; CHECK: (global $8 (ref null $8) (ref.null none)) + (global $8 (ref null $8) (ref.null none)) + ;; CHECK: (global $9 (ref null $9) (ref.null none)) + (global $9 (ref null $9) (ref.null none)) + ;; CHECK: (global $10 (ref null $10) (ref.null none)) + (global $10 (ref null $10) (ref.null none)) + ;; CHECK: (global $11 (ref null $11) (ref.null none)) + (global $11 (ref null $11) (ref.null none)) + ;; CHECK: (global $12 (ref null $12) (ref.null none)) + (global $12 (ref null $12) (ref.null none)) + ;; CHECK: (global $13 (ref null $13) (ref.null none)) + (global $13 (ref null $13) (ref.null none)) + ;; CHECK: (global $14 (ref null $14) (ref.null none)) + (global $14 (ref null $14) (ref.null none)) + ;; CHECK: (global $15 (ref null $15) (ref.null none)) + (global $15 (ref null $15) (ref.null none)) + ;; CHECK: (global $16 (ref null $16) (ref.null none)) + (global $16 (ref null $16) (ref.null none)) + ;; CHECK: (global $17 (ref null $17) (ref.null none)) + (global $17 (ref null $17) (ref.null none)) + ;; CHECK: (global $18 (ref null $18) (ref.null none)) + (global $18 (ref null $18) (ref.null none)) + ;; CHECK: (global $19 (ref null $19) (ref.null none)) + (global $19 (ref null $19) (ref.null none)) + ;; CHECK: (global $20 (ref null $20) (ref.null none)) + (global $20 (ref null $20) (ref.null none)) + ;; CHECK: (global $21 (ref null $21) (ref.null none)) + (global $21 (ref null $21) (ref.null none)) + ;; CHECK: (global $22 (ref null $22) (ref.null none)) + (global $22 (ref null $22) (ref.null none)) + ;; CHECK: (global $23 (ref null $23) (ref.null none)) + (global $23 (ref null $23) (ref.null none)) + ;; CHECK: (global $24 (ref null $24) (ref.null none)) + (global $24 (ref null $24) (ref.null none)) + ;; CHECK: (global $25 (ref null $25) (ref.null none)) + (global $25 (ref null $25) (ref.null none)) + ;; CHECK: (global $26 (ref null $26) (ref.null none)) + (global $26 (ref null $26) (ref.null none)) + ;; CHECK: (global $27 (ref null $27) (ref.null none)) + (global $27 (ref null $27) (ref.null none)) + ;; CHECK: (global $28 (ref null $28) (ref.null none)) + (global $28 (ref null $28) (ref.null none)) + ;; CHECK: (global $29 (ref null $29) (ref.null none)) + (global $29 (ref null $29) (ref.null none)) + ;; CHECK: (global $30 (ref null $30) (ref.null none)) + (global $30 (ref null $30) (ref.null none)) + ;; CHECK: (global $31 (ref null $31) (ref.null none)) + (global $31 (ref null $31) (ref.null none)) + ;; CHECK: (global $32 (ref null $32) (ref.null none)) + (global $32 (ref null $32) (ref.null none)) + ;; CHECK: (global $33 (ref null $33) (ref.null none)) + (global $33 (ref null $33) (ref.null none)) + ;; CHECK: (global $34 (ref null $34) (ref.null none)) + (global $34 (ref null $34) (ref.null none)) + ;; CHECK: (global $35 (ref null $35) (ref.null none)) + (global $35 (ref null $35) (ref.null none)) + ;; CHECK: (global $36 (ref null $36) (ref.null none)) + (global $36 (ref null $36) (ref.null none)) + ;; CHECK: (global $37 (ref null $37) (ref.null none)) + (global $37 (ref null $37) (ref.null none)) + ;; CHECK: (global $38 (ref null $38) (ref.null none)) + (global $38 (ref null $38) (ref.null none)) + ;; CHECK: (global $39 (ref null $39) (ref.null none)) + (global $39 (ref null $39) (ref.null none)) + ;; CHECK: (global $40 (ref null $40) (ref.null none)) + (global $40 (ref null $40) (ref.null none)) + ;; CHECK: (global $41 (ref null $41) (ref.null none)) + (global $41 (ref null $41) (ref.null none)) + ;; CHECK: (global $42 (ref null $42) (ref.null none)) + (global $42 (ref null $42) (ref.null none)) + ;; CHECK: (global $43 (ref null $43) (ref.null none)) + (global $43 (ref null $43) (ref.null none)) + ;; CHECK: (global $44 (ref null $44) (ref.null none)) + (global $44 (ref null $44) (ref.null none)) + ;; CHECK: (global $45 (ref null $45) (ref.null none)) + (global $45 (ref null $45) (ref.null none)) + ;; CHECK: (global $46 (ref null $46) (ref.null none)) + (global $46 (ref null $46) (ref.null none)) + ;; CHECK: (global $47 (ref null $47) (ref.null none)) + (global $47 (ref null $47) (ref.null none)) + ;; CHECK: (global $48 (ref null $48) (ref.null none)) + (global $48 (ref null $48) (ref.null none)) + ;; CHECK: (global $49 (ref null $49) (ref.null none)) + (global $49 (ref null $49) (ref.null none)) + ;; CHECK: (global $50 (ref null $50) (ref.null none)) + (global $50 (ref null $50) (ref.null none)) + ;; CHECK: (global $51 (ref null $51) (ref.null none)) + (global $51 (ref null $51) (ref.null none)) + ;; CHECK: (global $52 (ref null $52) (ref.null none)) + (global $52 (ref null $52) (ref.null none)) + ;; CHECK: (global $53 (ref null $53) (ref.null none)) + (global $53 (ref null $53) (ref.null none)) + ;; CHECK: (global $54 (ref null $54) (ref.null none)) + (global $54 (ref null $54) (ref.null none)) + ;; CHECK: (global $55 (ref null $55) (ref.null none)) + (global $55 (ref null $55) (ref.null none)) + ;; CHECK: (global $56 (ref null $56) (ref.null none)) + (global $56 (ref null $56) (ref.null none)) + ;; CHECK: (global $57 (ref null $57) (ref.null none)) + (global $57 (ref null $57) (ref.null none)) + ;; CHECK: (global $58 (ref null $58) (ref.null none)) + (global $58 (ref null $58) (ref.null none)) + ;; CHECK: (global $59 (ref null $59) (ref.null none)) + (global $59 (ref null $59) (ref.null none)) + ;; CHECK: (global $60 (ref null $60) (ref.null none)) + (global $60 (ref null $60) (ref.null none)) + ;; CHECK: (global $61 (ref null $61) (ref.null none)) + (global $61 (ref null $61) (ref.null none)) + ;; CHECK: (global $62 (ref null $62) (ref.null none)) + (global $62 (ref null $62) (ref.null none)) + ;; CHECK: (global $63 (ref null $63) (ref.null none)) + (global $63 (ref null $63) (ref.null none)) + ;; CHECK: (global $64 (ref null $64) (ref.null none)) + (global $64 (ref null $64) (ref.null none)) + ;; CHECK: (global $65 (ref null $65) (ref.null none)) + (global $65 (ref null $65) (ref.null none)) + ;; CHECK: (global $66 (ref null $66) (ref.null none)) + (global $66 (ref null $66) (ref.null none)) + ;; CHECK: (global $67 (ref null $67) (ref.null none)) + (global $67 (ref null $67) (ref.null none)) + ;; CHECK: (global $68 (ref null $68) (ref.null none)) + (global $68 (ref null $68) (ref.null none)) + ;; CHECK: (global $69 (ref null $69) (ref.null none)) + (global $69 (ref null $69) (ref.null none)) + ;; CHECK: (global $70 (ref null $70) (ref.null none)) + (global $70 (ref null $70) (ref.null none)) + ;; CHECK: (global $71 (ref null $71) (ref.null none)) + (global $71 (ref null $71) (ref.null none)) + ;; CHECK: (global $72 (ref null $72) (ref.null none)) + (global $72 (ref null $72) (ref.null none)) + ;; CHECK: (global $73 (ref null $73) (ref.null none)) + (global $73 (ref null $73) (ref.null none)) + ;; CHECK: (global $74 (ref null $74) (ref.null none)) + (global $74 (ref null $74) (ref.null none)) + ;; CHECK: (global $75 (ref null $75) (ref.null none)) + (global $75 (ref null $75) (ref.null none)) + ;; CHECK: (global $76 (ref null $76) (ref.null none)) + (global $76 (ref null $76) (ref.null none)) + ;; CHECK: (global $77 (ref null $77) (ref.null none)) + (global $77 (ref null $77) (ref.null none)) + ;; CHECK: (global $78 (ref null $78) (ref.null none)) + (global $78 (ref null $78) (ref.null none)) + ;; CHECK: (global $79 (ref null $79) (ref.null none)) + (global $79 (ref null $79) (ref.null none)) + ;; CHECK: (global $80 (ref null $80) (ref.null none)) + (global $80 (ref null $80) (ref.null none)) + ;; CHECK: (global $81 (ref null $81) (ref.null none)) + (global $81 (ref null $81) (ref.null none)) + ;; CHECK: (global $82 (ref null $82) (ref.null none)) + (global $82 (ref null $82) (ref.null none)) + ;; CHECK: (global $83 (ref null $83) (ref.null none)) + (global $83 (ref null $83) (ref.null none)) + ;; CHECK: (global $84 (ref null $84) (ref.null none)) + (global $84 (ref null $84) (ref.null none)) + ;; CHECK: (global $85 (ref null $85) (ref.null none)) + (global $85 (ref null $85) (ref.null none)) + ;; CHECK: (global $86 (ref null $86) (ref.null none)) + (global $86 (ref null $86) (ref.null none)) + ;; CHECK: (global $87 (ref null $87) (ref.null none)) + (global $87 (ref null $87) (ref.null none)) + ;; CHECK: (global $88 (ref null $88) (ref.null none)) + (global $88 (ref null $88) (ref.null none)) + ;; CHECK: (global $89 (ref null $89) (ref.null none)) + (global $89 (ref null $89) (ref.null none)) + ;; CHECK: (global $90 (ref null $90) (ref.null none)) + (global $90 (ref null $90) (ref.null none)) + ;; CHECK: (global $91 (ref null $91) (ref.null none)) + (global $91 (ref null $91) (ref.null none)) + ;; CHECK: (global $92 (ref null $92) (ref.null none)) + (global $92 (ref null $92) (ref.null none)) + ;; CHECK: (global $93 (ref null $93) (ref.null none)) + (global $93 (ref null $93) (ref.null none)) + ;; CHECK: (global $94 (ref null $94) (ref.null none)) + (global $94 (ref null $94) (ref.null none)) + ;; CHECK: (global $95 (ref null $95) (ref.null none)) + (global $95 (ref null $95) (ref.null none)) + ;; CHECK: (global $96 (ref null $96) (ref.null none)) + (global $96 (ref null $96) (ref.null none)) + ;; CHECK: (global $97 (ref null $97) (ref.null none)) + (global $97 (ref null $97) (ref.null none)) + ;; CHECK: (global $98 (ref null $98) (ref.null none)) + (global $98 (ref null $98) (ref.null none)) + ;; CHECK: (global $99 (ref null $99) (ref.null none)) + (global $99 (ref null $99) (ref.null none)) + ;; CHECK: (global $100 (ref null $10) (ref.null none)) + (global $100 (ref null $10) (ref.null none)) + ;; CHECK: (global $101 (ref null $11) (ref.null none)) + (global $101 (ref null $11) (ref.null none)) + ;; CHECK: (global $102 (ref null $12) (ref.null none)) + (global $102 (ref null $12) (ref.null none)) + ;; CHECK: (global $103 (ref null $13) (ref.null none)) + (global $103 (ref null $13) (ref.null none)) + ;; CHECK: (global $104 (ref null $14) (ref.null none)) + (global $104 (ref null $14) (ref.null none)) + ;; CHECK: (global $105 (ref null $15) (ref.null none)) + (global $105 (ref null $15) (ref.null none)) + ;; CHECK: (global $106 (ref null $16) (ref.null none)) + (global $106 (ref null $16) (ref.null none)) + ;; CHECK: (global $107 (ref null $17) (ref.null none)) + (global $107 (ref null $17) (ref.null none)) + ;; CHECK: (global $108 (ref null $18) (ref.null none)) + (global $108 (ref null $18) (ref.null none)) + ;; CHECK: (global $109 (ref null $19) (ref.null none)) + (global $109 (ref null $19) (ref.null none)) + ;; CHECK: (global $110 (ref null $110) (ref.null none)) + (global $110 (ref null $110) (ref.null none)) + ;; CHECK: (global $111 (ref null $111) (ref.null none)) + (global $111 (ref null $111) (ref.null none)) + ;; CHECK: (global $112 (ref null $112) (ref.null none)) + (global $112 (ref null $112) (ref.null none)) + ;; CHECK: (global $113 (ref null $113) (ref.null none)) + (global $113 (ref null $113) (ref.null none)) + ;; CHECK: (global $114 (ref null $114) (ref.null none)) + (global $114 (ref null $114) (ref.null none)) + ;; CHECK: (global $115 (ref null $115) (ref.null none)) + (global $115 (ref null $115) (ref.null none)) + ;; CHECK: (global $116 (ref null $116) (ref.null none)) + (global $116 (ref null $116) (ref.null none)) + ;; CHECK: (global $117 (ref null $117) (ref.null none)) + (global $117 (ref null $117) (ref.null none)) + ;; CHECK: (global $118 (ref null $118) (ref.null none)) + (global $118 (ref null $118) (ref.null none)) + ;; CHECK: (global $119 (ref null $119) (ref.null none)) + (global $119 (ref null $119) (ref.null none)) + ;; CHECK: (global $120 (ref null $120) (ref.null none)) + (global $120 (ref null $120) (ref.null none)) + ;; CHECK: (global $121 (ref null $121) (ref.null none)) + (global $121 (ref null $121) (ref.null none)) + ;; CHECK: (global $122 (ref null $122) (ref.null none)) + (global $122 (ref null $122) (ref.null none)) + ;; CHECK: (global $123 (ref null $123) (ref.null none)) + (global $123 (ref null $123) (ref.null none)) + ;; CHECK: (global $124 (ref null $124) (ref.null none)) + (global $124 (ref null $124) (ref.null none)) + ;; CHECK: (global $125 (ref null $125) (ref.null none)) + (global $125 (ref null $125) (ref.null none)) + ;; CHECK: (global $126 (ref null $126) (ref.null none)) + (global $126 (ref null $126) (ref.null none)) + ;; CHECK: (global $127 (ref null $127) (ref.null none)) + (global $127 (ref null $127) (ref.null none)) + ;; CHECK: (global $128 (ref null $128) (ref.null none)) + (global $128 (ref null $128) (ref.null none)) + ;; CHECK: (global $129 (ref null $129) (ref.null none)) + (global $129 (ref null $129) (ref.null none)) + ;; CHECK: (global $130 (ref null $130) (ref.null none)) + (global $130 (ref null $130) (ref.null none)) + ;; CHECK: (global $131 (ref null $131) (ref.null none)) + (global $131 (ref null $131) (ref.null none)) + ;; CHECK: (global $132 (ref null $132) (ref.null none)) + (global $132 (ref null $132) (ref.null none)) + ;; CHECK: (global $133 (ref null $133) (ref.null none)) + (global $133 (ref null $133) (ref.null none)) + ;; CHECK: (global $134 (ref null $134) (ref.null none)) + (global $134 (ref null $134) (ref.null none)) + ;; CHECK: (global $135 (ref null $135) (ref.null none)) + (global $135 (ref null $135) (ref.null none)) + ;; CHECK: (global $136 (ref null $136) (ref.null none)) + (global $136 (ref null $136) (ref.null none)) + ;; CHECK: (global $137 (ref null $137) (ref.null none)) + (global $137 (ref null $137) (ref.null none)) + ;; CHECK: (global $138 (ref null $138) (ref.null none)) + (global $138 (ref null $138) (ref.null none)) + ;; CHECK: (global $139 (ref null $139) (ref.null none)) + (global $139 (ref null $139) (ref.null none)) + ;; CHECK: (global $140 (ref null $140) (ref.null none)) + (global $140 (ref null $140) (ref.null none)) + ;; CHECK: (global $141 (ref null $141) (ref.null none)) + (global $141 (ref null $141) (ref.null none)) + ;; CHECK: (global $142 (ref null $142) (ref.null none)) + (global $142 (ref null $142) (ref.null none)) + ;; CHECK: (global $143 (ref null $143) (ref.null none)) + (global $143 (ref null $143) (ref.null none)) + ;; CHECK: (global $144 (ref null $144) (ref.null none)) + (global $144 (ref null $144) (ref.null none)) + ;; CHECK: (global $145 (ref null $145) (ref.null none)) + (global $145 (ref null $145) (ref.null none)) + ;; CHECK: (global $146 (ref null $146) (ref.null none)) + (global $146 (ref null $146) (ref.null none)) + ;; CHECK: (global $147 (ref null $147) (ref.null none)) + (global $147 (ref null $147) (ref.null none)) + ;; CHECK: (global $148 (ref null $148) (ref.null none)) + (global $148 (ref null $148) (ref.null none)) + ;; CHECK: (global $149 (ref null $149) (ref.null none)) + (global $149 (ref null $149) (ref.null none)) + ;; CHECK: (global $150 (ref null $150) (ref.null none)) + (global $150 (ref null $150) (ref.null none)) + ;; CHECK: (global $151 (ref null $151) (ref.null none)) + (global $151 (ref null $151) (ref.null none)) + ;; CHECK: (global $152 (ref null $152) (ref.null none)) + (global $152 (ref null $152) (ref.null none)) + ;; CHECK: (global $153 (ref null $153) (ref.null none)) + (global $153 (ref null $153) (ref.null none)) + ;; CHECK: (global $154 (ref null $154) (ref.null none)) + (global $154 (ref null $154) (ref.null none)) + ;; CHECK: (global $155 (ref null $155) (ref.null none)) + (global $155 (ref null $155) (ref.null none)) + ;; CHECK: (global $156 (ref null $156) (ref.null none)) + (global $156 (ref null $156) (ref.null none)) + ;; CHECK: (global $157 (ref null $157) (ref.null none)) + (global $157 (ref null $157) (ref.null none)) + ;; CHECK: (global $158 (ref null $158) (ref.null none)) + (global $158 (ref null $158) (ref.null none)) + ;; CHECK: (global $159 (ref null $159) (ref.null none)) + (global $159 (ref null $159) (ref.null none)) + ;; CHECK: (global $160 (ref null $160) (ref.null none)) + (global $160 (ref null $160) (ref.null none)) + ;; CHECK: (global $161 (ref null $161) (ref.null none)) + (global $161 (ref null $161) (ref.null none)) + ;; CHECK: (global $162 (ref null $162) (ref.null none)) + (global $162 (ref null $162) (ref.null none)) + ;; CHECK: (global $163 (ref null $163) (ref.null none)) + (global $163 (ref null $163) (ref.null none)) + ;; CHECK: (global $164 (ref null $164) (ref.null none)) + (global $164 (ref null $164) (ref.null none)) + ;; CHECK: (global $165 (ref null $165) (ref.null none)) + (global $165 (ref null $165) (ref.null none)) + ;; CHECK: (global $166 (ref null $166) (ref.null none)) + (global $166 (ref null $166) (ref.null none)) + ;; CHECK: (global $167 (ref null $167) (ref.null none)) + (global $167 (ref null $167) (ref.null none)) + ;; CHECK: (global $168 (ref null $168) (ref.null none)) + (global $168 (ref null $168) (ref.null none)) + ;; CHECK: (global $169 (ref null $169) (ref.null none)) + (global $169 (ref null $169) (ref.null none)) + ;; CHECK: (global $170 (ref null $170) (ref.null none)) + (global $170 (ref null $170) (ref.null none)) + ;; CHECK: (global $171 (ref null $171) (ref.null none)) + (global $171 (ref null $171) (ref.null none)) + ;; CHECK: (global $172 (ref null $172) (ref.null none)) + (global $172 (ref null $172) (ref.null none)) + ;; CHECK: (global $173 (ref null $173) (ref.null none)) + (global $173 (ref null $173) (ref.null none)) + ;; CHECK: (global $174 (ref null $174) (ref.null none)) + (global $174 (ref null $174) (ref.null none)) + ;; CHECK: (global $175 (ref null $175) (ref.null none)) + (global $175 (ref null $175) (ref.null none)) + ;; CHECK: (global $176 (ref null $176) (ref.null none)) + (global $176 (ref null $176) (ref.null none)) + ;; CHECK: (global $177 (ref null $177) (ref.null none)) + (global $177 (ref null $177) (ref.null none)) + ;; CHECK: (global $178 (ref null $178) (ref.null none)) + (global $178 (ref null $178) (ref.null none)) + ;; CHECK: (global $179 (ref null $179) (ref.null none)) + (global $179 (ref null $179) (ref.null none)) + ;; CHECK: (global $180 (ref null $180) (ref.null none)) + (global $180 (ref null $180) (ref.null none)) + ;; CHECK: (global $181 (ref null $181) (ref.null none)) + (global $181 (ref null $181) (ref.null none)) + ;; CHECK: (global $182 (ref null $182) (ref.null none)) + (global $182 (ref null $182) (ref.null none)) + ;; CHECK: (global $183 (ref null $183) (ref.null none)) + (global $183 (ref null $183) (ref.null none)) + ;; CHECK: (global $184 (ref null $184) (ref.null none)) + (global $184 (ref null $184) (ref.null none)) + ;; CHECK: (global $185 (ref null $185) (ref.null none)) + (global $185 (ref null $185) (ref.null none)) + ;; CHECK: (global $186 (ref null $186) (ref.null none)) + (global $186 (ref null $186) (ref.null none)) + ;; CHECK: (global $187 (ref null $187) (ref.null none)) + (global $187 (ref null $187) (ref.null none)) + ;; CHECK: (global $188 (ref null $188) (ref.null none)) + (global $188 (ref null $188) (ref.null none)) + ;; CHECK: (global $189 (ref null $189) (ref.null none)) + (global $189 (ref null $189) (ref.null none)) + ;; CHECK: (global $190 (ref null $190) (ref.null none)) + (global $190 (ref null $190) (ref.null none)) + ;; CHECK: (global $191 (ref null $191) (ref.null none)) + (global $191 (ref null $191) (ref.null none)) + ;; CHECK: (global $192 (ref null $192) (ref.null none)) + (global $192 (ref null $192) (ref.null none)) + ;; CHECK: (global $193 (ref null $193) (ref.null none)) + (global $193 (ref null $193) (ref.null none)) + ;; CHECK: (global $194 (ref null $194) (ref.null none)) + (global $194 (ref null $194) (ref.null none)) + ;; CHECK: (global $195 (ref null $195) (ref.null none)) + (global $195 (ref null $195) (ref.null none)) + ;; CHECK: (global $196 (ref null $196) (ref.null none)) + (global $196 (ref null $196) (ref.null none)) + ;; CHECK: (global $197 (ref null $197) (ref.null none)) + (global $197 (ref null $197) (ref.null none)) + ;; CHECK: (global $198 (ref null $198) (ref.null none)) + (global $198 (ref null $198) (ref.null none)) + ;; CHECK: (global $199 (ref null $199) (ref.null none)) + (global $199 (ref null $199) (ref.null none)) +) diff --git a/test/lit/passes/minimize-rec-groups.wast b/test/lit/passes/minimize-rec-groups.wast new file mode 100644 index 000000000..b1c1b1467 --- /dev/null +++ b/test/lit/passes/minimize-rec-groups.wast @@ -0,0 +1,486 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py --all-items and should not be edited. +;; RUN: foreach %s %t wasm-opt -all --minimize-rec-groups -S -o - | filecheck %s + +;; A module with no heap types at all should be ok. +(module + ;; CHECK: (global $g i32 (i32.const 0)) + (global $g i32 (i32.const 0)) +) + +;; A module with a single heap type should be ok. +(module + ;; CHECK: (type $t (struct)) + (type $t (struct)) + ;; CHECK: (global $g (ref null $t) (ref.null none)) + (global $g (ref null $t) (ref.null none)) +) + +;; Split a rec group containing independent types +(module + (rec + ;; CHECK: (type $a (struct (field i32))) + (type $a (struct (field i32))) + ;; CHECK: (type $b (struct (field i64))) + (type $b (struct (field i64))) + ;; CHECK: (type $c (struct (field f32))) + (type $c (struct (field f32))) + ) + + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) + ;; CHECK: (global $b (ref null $b) (ref.null none)) + (global $b (ref null $b) (ref.null none)) + ;; CHECK: (global $c (ref null $c) (ref.null none)) + (global $c (ref null $c) (ref.null none)) +) + +;; Split a rec group containing types that depend on each other but belong to +;; different SCCs. +(module + (rec + ;; CHECK: (type $a (struct)) + (type $a (struct)) + ;; CHECK: (type $b (struct (field (ref $a)))) + (type $b (struct (field (ref $a)))) + ;; CHECK: (type $c (struct (field (ref $b)))) + (type $c (struct (field (ref $b)))) + ) + + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) + ;; CHECK: (global $b (ref null $b) (ref.null none)) + (global $b (ref null $b) (ref.null none)) + ;; CHECK: (global $c (ref null $c) (ref.null none)) + (global $c (ref null $c) (ref.null none)) +) + +;; Reverse the order of the previous case. The output should still be in a valid +;; order. +(module + (rec + ;; CHECK: (type $a (struct)) + + ;; CHECK: (type $b (struct (field (ref $a)))) + + ;; CHECK: (type $c (struct (field (ref $b)))) + (type $c (struct (field (ref $b)))) + (type $b (struct (field (ref $a)))) + (type $a (struct)) + ) + + ;; CHECK: (global $c (ref null $c) (ref.null none)) + (global $c (ref null $c) (ref.null none)) + ;; CHECK: (global $b (ref null $b) (ref.null none)) + (global $b (ref null $b) (ref.null none)) + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) +) + +;; Now all the types are in the same SCC. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $c (struct (field (ref $a)))) + + ;; CHECK: (type $b (struct (field (ref $c)))) + + ;; CHECK: (type $a (struct (field (ref $b)))) + (type $a (struct (field (ref $b)))) + (type $b (struct (field (ref $c)))) + (type $c (struct (field (ref $a)))) + ) + + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) +) + +;; Only two of the types are in the same SCC. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $b (struct (field (ref $a)))) + + ;; CHECK: (type $a (struct (field (ref $b)))) + (type $a (struct (field (ref $b)))) + (type $b (struct (field (ref $a)))) + ;; CHECK: (type $c (struct (field (ref $a)))) + (type $c (struct (field (ref $a)))) + ) + + ;; CHECK: (global $c (ref null $c) (ref.null none)) + (global $c (ref null $c) (ref.null none)) +) + +;; Same, but change which two are in the SCC. The output order should still be +;; valid. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $c (struct (field (ref $b)))) + + ;; CHECK: (type $b (struct (field (ref $c)))) + + ;; CHECK: (type $a (struct (field (ref $b)))) + (type $a (struct (field (ref $b)))) + (type $b (struct (field (ref $c)))) + (type $c (struct (field (ref $b)))) + ) + + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) +) + +;; Two types that are in conflicting SCCs should be disambiguated. In this case +;; there are no different permutations, so we use a brand. +(module + (rec + ;; CHECK: (type $a (func)) + (type $a (func)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $1 (struct)) + + ;; CHECK: (type $b (func)) + (type $b (func)) + ) + + ;; CHECK: (global $a (ref null $a) (ref.null nofunc)) + (global $a (ref null $a) (ref.null nofunc)) + ;; CHECK: (global $b (ref null $b) (ref.null nofunc)) + (global $b (ref null $b) (ref.null nofunc)) +) + +;; Same as above, but now the types match the initial brand, so we have to skip +;; to the next one. +(module + (rec + ;; CHECK: (type $a (struct)) + (type $a (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $1 (array (mut i8))) + + ;; CHECK: (type $b (struct)) + (type $b (struct)) + ) + + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) + ;; CHECK: (global $b (ref null $b) (ref.null none)) + (global $b (ref null $b) (ref.null none)) +) + +;; Now we have groups that match both the initial brand and the next one, so +;; adding the brand will cause a conflict. We will have to go to the next brand. +(module + (rec + ;; CHECK: (type $a1 (struct)) + (type $a1 (struct)) + ;; CHECK: (type $b1 (array (mut i8))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $2 (array (mut i8))) + + ;; CHECK: (type $a2 (struct)) + (type $a2 (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $a3 (struct)) + (type $a3 (struct)) + (type $b1 (array (mut i8))) + ;; CHECK: (type $5 (array (mut i8))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $6 (array i8)) + + ;; CHECK: (type $b2 (array (mut i8))) + (type $b2 (array (mut i8))) + ) + + ;; CHECK: (global $a1 (ref null $a1) (ref.null none)) + (global $a1 (ref null $a1) (ref.null none)) + ;; CHECK: (global $a2 (ref null $a2) (ref.null none)) + (global $a2 (ref null $a2) (ref.null none)) + ;; CHECK: (global $a3 (ref null $a3) (ref.null none)) + (global $a3 (ref null $a3) (ref.null none)) + ;; CHECK: (global $b1 (ref null $b1) (ref.null none)) + (global $b1 (ref null $b1) (ref.null none)) + ;; CHECK: (global $b2 (ref null $b2) (ref.null none)) + (global $b2 (ref null $b2) (ref.null none)) +) + +;; Now the types have more fields, including one referring to a previous SCC. +(module + (rec + ;; CHECK: (type $other (struct (field i32))) + (type $other (struct (field i32))) + ;; CHECK: (type $a (struct (field anyref) (field i32) (field (ref $other)))) + (type $a (struct (field anyref i32 (ref $other)))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $2 (struct)) + + ;; CHECK: (type $b (struct (field anyref) (field i32) (field (ref $other)))) + (type $b (struct (field anyref i32 (ref $other)))) + ) + + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) + ;; CHECK: (global $b (ref null $b) (ref.null none)) + (global $b (ref null $b) (ref.null none)) +) + +;; Now there is a third type and we can disambiguate it by using a different +;; permutation with the same brand. +(module + (rec + ;; CHECK: (type $a (struct)) + (type $a (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $1 (array (mut i8))) + + ;; CHECK: (type $b (struct)) + (type $b (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $c (struct)) + (type $c (struct)) + ) + + ;; CHECK: (type $4 (array (mut i8))) + + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) + ;; CHECK: (global $b (ref null $b) (ref.null none)) + (global $b (ref null $b) (ref.null none)) + ;; CHECK: (global $c (ref null $c) (ref.null none)) + (global $c (ref null $c) (ref.null none)) +) + +;; Adding a fourth type requires using yet another brand. +(module + (rec + ;; CHECK: (type $a (struct)) + (type $a (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $1 (array (mut i8))) + + ;; CHECK: (type $b (struct)) + (type $b (struct)) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $c (struct)) + (type $c (struct)) + ;; CHECK: (type $4 (array (mut i8))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $5 (array i8)) + + ;; CHECK: (type $d (struct)) + (type $d (struct)) + ) + + ;; CHECK: (global $a (ref null $a) (ref.null none)) + (global $a (ref null $a) (ref.null none)) + ;; CHECK: (global $b (ref null $b) (ref.null none)) + (global $b (ref null $b) (ref.null none)) + ;; CHECK: (global $c (ref null $c) (ref.null none)) + (global $c (ref null $c) (ref.null none)) + ;; CHECK: (global $d (ref null $d) (ref.null none)) + (global $d (ref null $d) (ref.null none)) +) + +;; After $a1 and $a2 are dismabiguated with a brand, $b1 and $b2 require no +;; further disambiguation. +(module + (rec + ;; CHECK: (type $a1 (struct)) + (type $a1 (struct)) + ;; CHECK: (type $b1 (struct (field (ref $a1)))) + + ;; CHECK: (rec + ;; CHECK-NEXT: (type $2 (array (mut i8))) + + ;; CHECK: (type $a2 (struct)) + (type $a2 (struct)) + (type $b1 (struct (field (ref $a1)))) + ;; CHECK: (type $b2 (struct (field (ref $a2)))) + (type $b2 (struct (field (ref $a2)))) + ) + + ;; CHECK: (global $b1 (ref null $b1) (ref.null none)) + (global $b1 (ref null $b1) (ref.null none)) + ;; CHECK: (global $b2 (ref null $b2) (ref.null none)) + (global $b2 (ref null $b2) (ref.null none)) +) + +;; Now we can disambiguate by permuting without a brand. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $b1 (struct (field (ref $a1)))) + + ;; CHECK: (type $a1 (struct (field (ref $b1)) (field i32))) + (type $a1 (struct (field (ref $b1) i32))) + (type $b1 (struct (field (ref $a1)))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $a2 (struct (field (ref $b2)) (field i32))) + (type $a2 (struct (field (ref $b2) i32))) + ;; CHECK: (type $b2 (struct (field (ref $a2)))) + (type $b2 (struct (field (ref $a2)))) + ) + + ;; CHECK: (global $a1 (ref null $a1) (ref.null none)) + (global $a1 (ref null $a1) (ref.null none)) + ;; CHECK: (global $a2 (ref null $a2) (ref.null none)) + (global $a2 (ref null $a2) (ref.null none)) +) + +;; But when we run out of permutations, we need a brand again. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $b1 (struct (field (ref $a1)))) + + ;; CHECK: (type $a1 (struct (field (ref $b1)) (field i32))) + (type $a1 (struct (field (ref $b1) i32))) + (type $b1 (struct (field (ref $a1)))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $a2 (struct (field (ref $b2)) (field i32))) + (type $a2 (struct (field (ref $b2) i32))) + ;; CHECK: (type $b2 (struct (field (ref $a2)))) + (type $b2 (struct (field (ref $a2)))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $4 (struct)) + + ;; CHECK: (type $b3 (struct (field (ref $a3)))) + + ;; CHECK: (type $a3 (struct (field (ref $b3)) (field i32))) + (type $a3 (struct (field (ref $b3) i32))) + (type $b3 (struct (field (ref $a3)))) + ) + + ;; CHECK: (global $a1 (ref null $a1) (ref.null none)) + (global $a1 (ref null $a1) (ref.null none)) + ;; CHECK: (global $a2 (ref null $a2) (ref.null none)) + (global $a2 (ref null $a2) (ref.null none)) + ;; CHECK: (global $a3 (ref null $a3) (ref.null none)) + (global $a3 (ref null $a3) (ref.null none)) +) + +;; Same as above, except the middle global now refers to $b2 instead of $a2, +;; changing the initial order of types in the middle SCC. We arrive at the same +;; result by a different path. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $b1 (struct (field (ref $a1)))) + + ;; CHECK: (type $a1 (struct (field (ref $b1)) (field i32))) + (type $a1 (struct (field (ref $b1) i32))) + (type $b1 (struct (field (ref $a1)))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $a2 (struct (field (ref $b2)) (field i32))) + (type $a2 (struct (field (ref $b2) i32))) + ;; CHECK: (type $b2 (struct (field (ref $a2)))) + (type $b2 (struct (field (ref $a2)))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $4 (struct)) + + ;; CHECK: (type $b3 (struct (field (ref $a3)))) + + ;; CHECK: (type $a3 (struct (field (ref $b3)) (field i32))) + (type $a3 (struct (field (ref $b3) i32))) + (type $b3 (struct (field (ref $a3)))) + ) + + ;; CHECK: (global $a1 (ref null $a1) (ref.null none)) + (global $a1 (ref null $a1) (ref.null none)) + ;; CHECK: (global $b2 (ref null $b2) (ref.null none)) + (global $b2 (ref null $b2) (ref.null none)) + ;; CHECK: (global $a3 (ref null $a3) (ref.null none)) + (global $a3 (ref null $a3) (ref.null none)) +) + +;; Now we can't differentiate by permutation because of automorphisms. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $b1 (struct (field (ref $a1)))) + + ;; CHECK: (type $a1 (struct (field (ref $b1)))) + (type $a1 (struct (field (ref $b1)))) + (type $b1 (struct (field (ref $a1)))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $2 (struct)) + + ;; CHECK: (type $b2 (struct (field (ref $a2)))) + + ;; CHECK: (type $a2 (struct (field (ref $b2)))) + (type $a2 (struct (field (ref $b2)))) + (type $b2 (struct (field (ref $a2)))) + ) + + ;; CHECK: (global $a1 (ref null $a1) (ref.null none)) + (global $a1 (ref null $a1) (ref.null none)) + ;; CHECK: (global $a2 (ref null $a2) (ref.null none)) + (global $a2 (ref null $a2) (ref.null none)) +) + +;; Now we can't differentiate by permutation because the subtyping constraint +;; admits only one ordering. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $a1 (sub (struct (field (ref $b1))))) + (type $a1 (sub (struct (field (ref $b1))))) + ;; CHECK: (type $b1 (sub $a1 (struct (field (ref $b1))))) + (type $b1 (sub $a1 (struct (field (ref $b1))))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $2 (struct)) + + ;; CHECK: (type $a2 (sub (struct (field (ref $b2))))) + (type $a2 (sub (struct (field (ref $b2))))) + ;; CHECK: (type $b2 (sub $a2 (struct (field (ref $b2))))) + (type $b2 (sub $a2 (struct (field (ref $b2))))) + ) + + ;; CHECK: (global $a1 (ref null $a1) (ref.null none)) + (global $a1 (ref null $a1) (ref.null none)) + ;; CHECK: (global $a2 (ref null $a2) (ref.null none)) + (global $a2 (ref null $a2) (ref.null none)) +) + + +;; Now there are only two possible orderings admitted by the subtyping +;; constraint. +(module + (rec + ;; CHECK: (rec + ;; CHECK-NEXT: (type $a1 (sub (struct (field (ref $b1))))) + (type $a1 (sub (struct (field (ref $b1))))) + ;; CHECK: (type $c1 (sub $a1 (struct (field (ref $b1))))) + + ;; CHECK: (type $b1 (sub $a1 (struct (field (ref $b1)) (field (ref $c1))))) + (type $b1 (sub $a1 (struct (field (ref $b1)) (ref $c1)))) + (type $c1 (sub $a1 (struct (field (ref $b1))))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $a2 (sub (struct (field (ref $b2))))) + (type $a2 (sub (struct (field (ref $b2))))) + ;; CHECK: (type $b2 (sub $a2 (struct (field (ref $b2)) (field (ref $c2))))) + (type $b2 (sub $a2 (struct (field (ref $b2)) (ref $c2)))) + ;; CHECK: (type $c2 (sub $a2 (struct (field (ref $b2))))) + (type $c2 (sub $a2 (struct (field (ref $b2))))) + ;; CHECK: (rec + ;; CHECK-NEXT: (type $6 (struct)) + + ;; CHECK: (type $a3 (sub (struct (field (ref $b3))))) + (type $a3 (sub (struct (field (ref $b3))))) + ;; CHECK: (type $c3 (sub $a3 (struct (field (ref $b3))))) + + ;; CHECK: (type $b3 (sub $a3 (struct (field (ref $b3)) (field (ref $c3))))) + (type $b3 (sub $a3 (struct (field (ref $b3)) (ref $c3)))) + (type $c3 (sub $a3 (struct (field (ref $b3))))) + ) + + ;; CHECK: (global $a1 (ref null $a1) (ref.null none)) + (global $a1 (ref null $a1) (ref.null none)) + ;; CHECK: (global $a2 (ref null $a2) (ref.null none)) + (global $a2 (ref null $a2) (ref.null none)) + ;; CHECK: (global $a3 (ref null $a3) (ref.null none)) + (global $a3 (ref null $a3) (ref.null none)) +) |