summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ir/subtypes.h36
-rw-r--r--src/ir/type-updating.cpp170
-rw-r--r--src/passes/GlobalTypeOptimization.cpp4
-rw-r--r--src/passes/TypeMerging.cpp33
-rw-r--r--src/tools/wasm-ctor-eval.cpp36
-rw-r--r--src/wasm-type-ordering.h66
6 files changed, 121 insertions, 224 deletions
diff --git a/src/ir/subtypes.h b/src/ir/subtypes.h
index 47ee51ac3..c69250043 100644
--- a/src/ir/subtypes.h
+++ b/src/ir/subtypes.h
@@ -18,7 +18,7 @@
#define wasm_ir_subtypes_h
#include "ir/module-utils.h"
-#include "support/old_topological_sort.h"
+#include "support/topological_sort.h"
#include "wasm.h"
namespace wasm {
@@ -79,29 +79,19 @@ struct SubTypes {
}
// A topological sort that visits subtypes first.
- auto getSubTypesFirstSort() const {
- struct SubTypesFirstSort : OldTopologicalSort<HeapType, SubTypesFirstSort> {
- const SubTypes& parent;
-
- SubTypesFirstSort(const SubTypes& parent) : parent(parent) {
- for (auto type : parent.types) {
- // The roots are types with no supertype.
- if (!type.getDeclaredSuperType()) {
- push(type);
- }
- }
- }
-
- void pushPredecessors(HeapType type) {
- // Things we need to process before each type are its subtypes. Once we
- // know their depth, we can easily compute our own.
- for (auto pred : parent.getImmediateSubTypes(type)) {
- push(pred);
- }
+ std::vector<HeapType> getSubTypesFirstSort() const {
+ std::vector<std::pair<HeapType, std::vector<HeapType>>> graph;
+ graph.reserve(types.size());
+ for (auto type : types) {
+ if (auto it = typeSubTypes.find(type); it != typeSubTypes.end()) {
+ graph.emplace_back(*it);
+ } else {
+ graph.emplace_back(type, std::vector<HeapType>{});
}
- };
-
- return SubTypesFirstSort(*this);
+ }
+ auto sorted = TopologicalSort::sortOf(graph.begin(), graph.end());
+ std::reverse(sorted.begin(), sorted.end());
+ return sorted;
}
// Computes the depth of children for each type. This is 0 if the type has no
diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index 467971989..dedbb6316 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -40,118 +40,72 @@ GlobalTypeRewriter::TypeMap GlobalTypeRewriter::rebuildTypes(
// world scenario, don't modify public types because we assume that they may
// be reflected on or used for linking. Figure out where each private type
// will be located in the builder.
- //
- // There are two code paths here: a new one that is used when there are type
- // indices to preserve and an old one that is used otherwise. The old code
- // path is kept around to avoid unnecessary changes to test outputs while we
- // incrementally add --preserve-type-order to tests that could benefit from
- // it. Once we are done adding --preserve-type-order to tests, we should
- // remove the old code path here since the new code path is strictly better.
- if (wasm.typeIndices.size()) {
- // New code path, currently used only with --preserve-type-order.
- auto typeInfo = ModuleUtils::collectHeapTypeInfo(
- wasm,
- ModuleUtils::TypeInclusion::UsedIRTypes,
- ModuleUtils::VisibilityHandling::FindVisibility);
-
- std::unordered_set<HeapType> additionalSet(additionalPrivateTypes.begin(),
- additionalPrivateTypes.end());
-
- std::vector<std::pair<HeapType, SmallVector<HeapType, 1>>>
- privateSupertypes;
- privateSupertypes.reserve(typeInfo.size());
- for (auto& [type, info] : typeInfo) {
- if (info.visibility != ModuleUtils::Visibility::Private &&
- !additionalSet.count(type)) {
- continue;
- }
- privateSupertypes.push_back({type, {}});
-
- if (auto super = getDeclaredSuperType(type)) {
- auto it = typeInfo.find(*super);
- // Record the supertype only if it is among the private types.
- if ((it != typeInfo.end() &&
- it->second.visibility == ModuleUtils::Visibility::Private) ||
- additionalSet.count(*super)) {
- privateSupertypes.back().second.push_back(*super);
- }
- }
- }
-
- // Topological sort to have subtypes first. This is the opposite of the
- // order we need, so the comparison is the opposite of what we ultimately
- // want.
- std::vector<HeapType> sorted;
- if (wasm.typeIndices.empty()) {
- sorted = TopologicalSort::sortOf(privateSupertypes.begin(),
- privateSupertypes.end());
- } else {
- sorted =
- TopologicalSort::minSortOf(privateSupertypes.begin(),
- privateSupertypes.end(),
- [&](Index a, Index b) {
- auto typeA = privateSupertypes[a].first;
- auto typeB = privateSupertypes[b].first;
- // Preserve type order.
- auto itA = wasm.typeIndices.find(typeA);
- auto itB = wasm.typeIndices.find(typeB);
- bool hasA = itA != wasm.typeIndices.end();
- bool hasB = itB != wasm.typeIndices.end();
- if (hasA != hasB) {
- // Types with preserved indices must be
- // sorted before (after in this reversed
- // comparison) types without indices to
- // maintain transitivity.
- return !hasA;
- }
- if (hasA && *itA != *itB) {
- return !(itA->second < itB->second);
- }
- // Break ties by the arbitrary order we
- // have collected the types in.
- return a > b;
- });
- }
- std::reverse(sorted.begin(), sorted.end());
- Index i = 0;
- for (auto type : sorted) {
- typeIndices[type] = i++;
+ auto typeInfo = ModuleUtils::collectHeapTypeInfo(
+ wasm,
+ ModuleUtils::TypeInclusion::UsedIRTypes,
+ ModuleUtils::VisibilityHandling::FindVisibility);
+
+ std::unordered_set<HeapType> additionalSet(additionalPrivateTypes.begin(),
+ additionalPrivateTypes.end());
+
+ std::vector<std::pair<HeapType, SmallVector<HeapType, 1>>> privateSupertypes;
+ privateSupertypes.reserve(typeInfo.size());
+ for (auto& [type, info] : typeInfo) {
+ if (info.visibility != ModuleUtils::Visibility::Private &&
+ !additionalSet.count(type)) {
+ continue;
}
- } else {
- // Old code path.
-
- auto privateTypes = ModuleUtils::getPrivateHeapTypes(wasm);
-
- if (!additionalPrivateTypes.empty()) {
- // Only add additional private types that are not already in the list.
- std::unordered_set<HeapType> privateTypesSet(privateTypes.begin(),
- privateTypes.end());
+ privateSupertypes.push_back({type, {}});
- for (auto t : additionalPrivateTypes) {
- if (!privateTypesSet.count(t)) {
- privateTypes.push_back(t);
- privateTypesSet.insert(t);
- }
+ if (auto super = getDeclaredSuperType(type)) {
+ auto it = typeInfo.find(*super);
+ // Record the supertype only if it is among the private types.
+ if ((it != typeInfo.end() &&
+ it->second.visibility == ModuleUtils::Visibility::Private) ||
+ additionalSet.count(*super)) {
+ privateSupertypes.back().second.push_back(*super);
}
}
+ }
- // Topological sort to have supertypes first, but we have to account for the
- // fact that we may be replacing the supertypes to get the order correct.
- struct SupertypesFirst
- : HeapTypeOrdering::SupertypesFirstBase<SupertypesFirst> {
- GlobalTypeRewriter& parent;
-
- SupertypesFirst(GlobalTypeRewriter& parent) : parent(parent) {}
- std::optional<HeapType> getDeclaredSuperType(HeapType type) {
- return parent.getDeclaredSuperType(type);
- }
- };
-
- SupertypesFirst sortedTypes(*this);
- Index i = 0;
- for (auto type : sortedTypes.sort(privateTypes)) {
- typeIndices[type] = i++;
- }
+ // Topological sort to have subtypes first. This is the opposite of the
+ // order we need, so the comparison is the opposite of what we ultimately
+ // want.
+ std::vector<HeapType> sorted;
+ if (wasm.typeIndices.empty()) {
+ sorted = TopologicalSort::sortOf(privateSupertypes.begin(),
+ privateSupertypes.end());
+ } else {
+ sorted =
+ TopologicalSort::minSortOf(privateSupertypes.begin(),
+ privateSupertypes.end(),
+ [&](Index a, Index b) {
+ auto typeA = privateSupertypes[a].first;
+ auto typeB = privateSupertypes[b].first;
+ // Preserve type order.
+ auto itA = wasm.typeIndices.find(typeA);
+ auto itB = wasm.typeIndices.find(typeB);
+ bool hasA = itA != wasm.typeIndices.end();
+ bool hasB = itB != wasm.typeIndices.end();
+ if (hasA != hasB) {
+ // Types with preserved indices must be
+ // sorted before (after in this reversed
+ // comparison) types without indices to
+ // maintain transitivity.
+ return !hasA;
+ }
+ if (hasA && *itA != *itB) {
+ return !(itA->second < itB->second);
+ }
+ // Break ties by the arbitrary order we
+ // have collected the types in.
+ return a > b;
+ });
+ }
+ std::reverse(sorted.begin(), sorted.end());
+ Index i = 0;
+ for (auto type : sorted) {
+ typeIndices[type] = i++;
}
if (typeIndices.size() == 0) {
@@ -168,7 +122,7 @@ GlobalTypeRewriter::TypeMap GlobalTypeRewriter::rebuildTypes(
typeBuilder.createRecGroup(0, typeBuilder.size());
// Create the temporary heap types.
- Index i = 0;
+ i = 0;
auto map = [&](HeapType type) -> HeapType {
if (auto it = typeIndices.find(type); it != typeIndices.end()) {
return typeBuilder[it->second];
diff --git a/src/passes/GlobalTypeOptimization.cpp b/src/passes/GlobalTypeOptimization.cpp
index eec8e206d..dac6fd7b6 100644
--- a/src/passes/GlobalTypeOptimization.cpp
+++ b/src/passes/GlobalTypeOptimization.cpp
@@ -171,8 +171,8 @@ struct GlobalTypeOptimization : public Pass {
// fields in a supertype is a constraint on what subtypes can do. That is,
// we decide for each supertype what the optimal order is, and consider that
// fixed, and then subtypes can decide how to sort fields that they append.
- HeapTypeOrdering::SupertypesFirst sorted;
- for (auto type : sorted.sort(propagator.subTypes.types)) {
+ for (auto type :
+ HeapTypeOrdering::supertypesFirst(propagator.subTypes.types)) {
if (!type.isStruct()) {
continue;
}
diff --git a/src/passes/TypeMerging.cpp b/src/passes/TypeMerging.cpp
index 1cac7732f..206addd2f 100644
--- a/src/passes/TypeMerging.cpp
+++ b/src/passes/TypeMerging.cpp
@@ -142,6 +142,17 @@ struct TypeMerging : public Pass {
return type;
}
+ std::vector<HeapType>
+ mergeableSupertypesFirst(const std::vector<HeapType>& types) {
+ return HeapTypeOrdering::supertypesFirst(
+ types, [&](HeapType type) -> std::optional<HeapType> {
+ if (auto super = type.getDeclaredSuperType()) {
+ return getMerged(*super);
+ }
+ return std::nullopt;
+ });
+ }
+
void run(Module* module_) override;
// We will do two different kinds of merging: First, we will merge types into
@@ -163,20 +174,6 @@ struct TypeMerging : public Pass {
void applyMerges();
};
-struct MergeableSupertypesFirst
- : HeapTypeOrdering::SupertypesFirstBase<MergeableSupertypesFirst> {
- TypeMerging& merging;
-
- MergeableSupertypesFirst(TypeMerging& merging) : merging(merging) {}
-
- std::optional<HeapType> getDeclaredSuperType(HeapType type) {
- if (auto super = type.getDeclaredSuperType()) {
- return merging.getMerged(*super);
- }
- return std::nullopt;
- }
-};
-
// Hash and equality-compare HeapTypes based on their top-level structure (i.e.
// "shape"), ignoring nontrivial heap type children that will not be
// differentiated between until we run the DFA partition refinement.
@@ -305,8 +302,7 @@ bool TypeMerging::merge(MergeKind kind) {
// For each type, either create a new partition or add to its supertype's
// partition.
- MergeableSupertypesFirst sortedTypes(*this);
- for (auto type : sortedTypes.sort(mergeable)) {
+ for (auto type : mergeableSupertypesFirst(mergeable)) {
// We need partitions for any public children of this type since those
// children will participate in the DFA we're creating.
for (auto child : getPublicChildren(type)) {
@@ -414,7 +410,7 @@ bool TypeMerging::merge(MergeKind kind) {
std::vector<HeapType> newMergeable;
bool merged = false;
for (const auto& partition : refinedPartitions) {
- auto target = *MergeableSupertypesFirst(*this).sort(partition).begin();
+ auto target = mergeableSupertypesFirst(partition).front();
newMergeable.push_back(target);
for (auto type : partition) {
if (type != target) {
@@ -452,8 +448,7 @@ TypeMerging::splitSupertypePartition(const std::vector<HeapType>& types) {
std::unordered_set<HeapType> includedTypes(types.begin(), types.end());
std::vector<std::vector<HeapType>> partitions;
std::unordered_map<HeapType, Index> partitionIndices;
- MergeableSupertypesFirst sortedTypes(*this);
- for (auto type : sortedTypes.sort(types)) {
+ for (auto type : mergeableSupertypesFirst(types)) {
auto super = type.getDeclaredSuperType();
if (super && includedTypes.count(*super)) {
// We must already have a partition for the supertype we can add to.
diff --git a/src/tools/wasm-ctor-eval.cpp b/src/tools/wasm-ctor-eval.cpp
index d74790b2a..464654d4f 100644
--- a/src/tools/wasm-ctor-eval.cpp
+++ b/src/tools/wasm-ctor-eval.cpp
@@ -36,9 +36,9 @@
#include "support/colors.h"
#include "support/file.h"
#include "support/insert_ordered.h"
-#include "support/old_topological_sort.h"
#include "support/small_set.h"
#include "support/string.h"
+#include "support/topological_sort.h"
#include "tool-options.h"
#include "wasm-builder.h"
#include "wasm-interpreter.h"
@@ -609,9 +609,9 @@ private:
Builder builder(*wasm);
// First, find what constraints we have on the ordering of the globals. We
- // will build up a map of each global to the globals it must be after.
- using MustBeAfter = InsertOrderedMap<Name, InsertOrderedSet<Name>>;
- MustBeAfter mustBeAfter;
+ // will build up a map of each global to the globals it must be before.
+ using MustBeBefore = InsertOrderedMap<Name, InsertOrderedSet<Name>>;
+ MustBeBefore mustBeBefore;
for (auto& global : wasm->globals) {
if (!global->init) {
@@ -672,31 +672,12 @@ private:
// Any global.gets that cannot be fixed up are constraints.
for (auto* get : scanner.unfixableGets) {
- mustBeAfter[global->name].insert(get->name);
+ mustBeBefore[global->name];
+ mustBeBefore[get->name].insert(global->name);
}
}
- if (!mustBeAfter.empty()) {
- // We found constraints that require reordering, so do so.
- struct MustBeAfterSort : OldTopologicalSort<Name, MustBeAfterSort> {
- MustBeAfter& mustBeAfter;
-
- MustBeAfterSort(MustBeAfter& mustBeAfter) : mustBeAfter(mustBeAfter) {
- for (auto& [global, _] : mustBeAfter) {
- push(global);
- }
- }
-
- void pushPredecessors(Name global) {
- auto iter = mustBeAfter.find(global);
- if (iter != mustBeAfter.end()) {
- for (auto other : iter->second) {
- push(other);
- }
- }
- }
- };
-
+ if (!mustBeBefore.empty()) {
auto oldGlobals = std::move(wasm->globals);
// After clearing the globals vector, clear the map as well.
wasm->updateMaps();
@@ -706,7 +687,8 @@ private:
globalIndexes[oldGlobals[i]->name] = i;
}
// Add the globals that had an important ordering, in the right order.
- for (auto global : MustBeAfterSort(mustBeAfter)) {
+ for (auto global :
+ TopologicalSort::sortOf(mustBeBefore.begin(), mustBeBefore.end())) {
wasm->addGlobal(std::move(oldGlobals[globalIndexes[global]]));
}
// Add all other globals after them.
diff --git a/src/wasm-type-ordering.h b/src/wasm-type-ordering.h
index 9ccf4c568..0f23b4953 100644
--- a/src/wasm-type-ordering.h
+++ b/src/wasm-type-ordering.h
@@ -20,58 +20,34 @@
#include <unordered_set>
#include "support/insert_ordered.h"
-#include "support/old_topological_sort.h"
+#include "support/topological_sort.h"
#include "wasm-type.h"
namespace wasm::HeapTypeOrdering {
-// Given a collection of types, iterate through it such that each type in the
-// collection is visited only after its immediate supertype in the collection is
-// visited.
-template<typename SupertypeProvider>
-struct SupertypesFirstBase
- : OldTopologicalSort<HeapType, SupertypesFirstBase<SupertypeProvider>> {
- // For each type in the input collection, whether it is a supertype. Used to
- // track membership in the input collection.
- InsertOrderedMap<HeapType, bool> typeSet;
-
- SupertypeProvider& self() { return *static_cast<SupertypeProvider*>(this); }
-
- template<typename T> SupertypeProvider& sort(const T& types) {
- for (auto type : types) {
- typeSet[type] = false;
- }
- // Find the supertypes that are in the collection.
- for (auto [type, _] : typeSet) {
- if (auto super = self().getDeclaredSuperType(type)) {
- if (auto it = typeSet.find(*super); it != typeSet.end()) {
- it->second = true;
- }
- }
- }
- // Types that are not supertypes of others are the roots.
- for (auto [type, isSuper] : typeSet) {
- if (!isSuper) {
- this->push(type);
- }
- }
- return self();
+// Given a collection of types, return a sequence of the types such that each
+// type in the sequence comes only after its immediate supertype in the
+// collection is visited.
+template<typename T>
+std::vector<HeapType> supertypesFirst(
+ const T& types,
+ std::function<std::optional<HeapType>(HeapType)> getSuper =
+ [](HeapType type) { return type.getDeclaredSuperType(); }) {
+
+ InsertOrderedMap<HeapType, std::vector<HeapType>> subtypes;
+ for (auto type : types) {
+ subtypes.insert({type, {}});
}
-
- void pushPredecessors(HeapType type) {
- // Do not visit types that weren't in the input collection.
- if (auto super = self().getDeclaredSuperType(type);
- super && typeSet.count(*super)) {
- this->push(*super);
+ // Find the supertypes that are in the collection.
+ for (auto [type, _] : subtypes) {
+ if (auto super = getSuper(type)) {
+ if (auto it = subtypes.find(*super); it != subtypes.end()) {
+ it->second.push_back(type);
+ }
}
}
-};
-
-struct SupertypesFirst : SupertypesFirstBase<SupertypesFirst> {
- std::optional<HeapType> getDeclaredSuperType(HeapType type) {
- return type.getDeclaredSuperType();
- }
-};
+ return TopologicalSort::sortOf(subtypes.begin(), subtypes.end());
+}
} // namespace wasm::HeapTypeOrdering
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-05 13:22:16 +0000