summaryrefslogtreecommitdiff
path: root/src/ir
diff options
context:
space:
mode:
Diffstat (limited to 'src/ir')
-rw-r--r--src/ir/subtypes.h36
-rw-r--r--src/ir/type-updating.cpp170
2 files changed, 75 insertions, 131 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];
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-12 21:12:51 +0000