summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/passes/MinimizeRecGroups.cpp70
-rw-r--r--src/passes/ReorderGlobals.cpp12
-rw-r--r--src/support/topological_orders.h66
3 files changed, 76 insertions, 72 deletions
diff --git a/src/passes/MinimizeRecGroups.cpp b/src/passes/MinimizeRecGroups.cpp
index 728cb306e..3a61e1e0b 100644
--- a/src/passes/MinimizeRecGroups.cpp
+++ b/src/passes/MinimizeRecGroups.cpp
@@ -108,7 +108,7 @@ struct TypeSCCs
// with the most compact encoding.
struct BrandTypeIterator {
// See `initFieldOptions` for the 18 options.
- static constexpr size_t optionCount = 18;
+ static constexpr Index optionCount = 18;
static std::array<Field, optionCount> fieldOptions;
static void initFieldOptions();
@@ -146,7 +146,7 @@ struct BrandTypeIterator {
}
BrandTypeIterator& operator++() {
- for (size_t i = fields.size(); i > 0; --i) {
+ for (Index i = fields.size(); i > 0; --i) {
if (fields[i - 1].advance()) {
return *this;
}
@@ -162,15 +162,15 @@ struct BrandTypeIterator {
};
// Create an adjacency list with edges from supertype to subtypes.
-std::vector<std::vector<size_t>>
+std::vector<std::vector<Index>>
createSubtypeGraph(const std::vector<HeapType>& types) {
- std::unordered_map<HeapType, size_t> indices;
+ std::unordered_map<HeapType, Index> 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) {
+ std::vector<std::vector<Index>> subtypeGraph(types.size());
+ for (Index 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);
@@ -199,13 +199,13 @@ struct GroupClassInfo {
// 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;
+ std::vector<std::vector<Index>> 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);
+ static std::vector<std::vector<Index>> initSubtypeGraph(RecGroupInfo& info);
GroupClassInfo(RecGroupInfo& info);
void advance() {
@@ -224,7 +224,7 @@ struct GroupClassInfo {
// beginning of the canonical order.
subtypeGraph.insert(subtypeGraph.begin(), {{}});
// Adjust indices.
- for (size_t i = 1; i < subtypeGraph.size(); ++i) {
+ for (Index i = 1; i < subtypeGraph.size(); ++i) {
for (auto& edge : subtypeGraph[i]) {
++edge;
}
@@ -255,7 +255,7 @@ struct RecGroupInfo {
// 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;
+ std::vector<Index> permutation;
// Does this group include a brand type that does not correspond to a type in
// the original module?
bool hasBrand = false;
@@ -265,13 +265,13 @@ struct RecGroupInfo {
std::optional<GroupClassInfo> classInfo;
};
-std::vector<std::vector<size_t>>
+std::vector<std::vector<Index>>
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) {
+ for (Index i = 0; i < info.group.size(); ++i) {
canonical[info.permutation[i]] = info.group[i];
}
@@ -291,7 +291,7 @@ void GroupClassInfo::permute(RecGroupInfo& info) {
// 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) {
+ for (Index i = 0; i < info.group.size(); ++i) {
canonical[info.permutation[i] + insertingBrand] = info.group[i];
}
// Update the brand.
@@ -304,7 +304,7 @@ void GroupClassInfo::permute(RecGroupInfo& info) {
}
// Finally, re-permute with the new permutation..
info.permutation = *orders;
- for (size_t i = 0; i < info.group.size(); ++i) {
+ for (Index i = 0; i < info.group.size(); ++i) {
info.group[i] = canonical[info.permutation[i]];
}
}
@@ -341,14 +341,14 @@ struct MinimizeRecGroups : Pass {
// 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;
+ std::unordered_map<HeapType, Index> 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;
+ std::unordered_map<RecGroupShape, Index> 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
@@ -360,7 +360,7 @@ struct MinimizeRecGroups : Pass {
// 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;
+ std::vector<Index> shapesToUpdate;
void run(Module* module) override {
// There are no recursion groups to minimize if GC is not enabled.
@@ -382,7 +382,7 @@ struct MinimizeRecGroups : Pass {
// Compute the strongly connected components and ensure they form distinct
// recursion groups.
for (auto scc : TypeSCCs(types)) {
- [[maybe_unused]] size_t index = equivalenceClasses.addSet();
+ [[maybe_unused]] Index index = equivalenceClasses.addSet();
assert(index == groups.size());
groups.emplace_back();
@@ -392,7 +392,7 @@ struct MinimizeRecGroups : Pass {
auto deps = createSubtypeGraph(sccTypes);
auto permutation = *TopologicalOrders(deps).begin();
groups.back().group.resize(sccTypes.size());
- for (size_t i = 0; i < sccTypes.size(); ++i) {
+ for (Index i = 0; i < sccTypes.size(); ++i) {
groups.back().group[i] = sccTypes[permutation[i]];
}
assert(shapesToUpdate.empty());
@@ -420,7 +420,7 @@ struct MinimizeRecGroups : Pass {
}
}
- void updateShape(size_t group) {
+ void updateShape(Index group) {
auto [it, inserted] =
groupShapeIndices.insert({RecGroupShape(groups[group].group), group});
if (inserted) {
@@ -454,13 +454,13 @@ struct MinimizeRecGroups : Pass {
//
// These possibilities are handled in order below.
- size_t other = it->second;
+ Index other = it->second;
auto& groupInfo = groups[group];
auto& otherInfo = groups[other];
- size_t groupRep = equivalenceClasses.getRoot(group);
- size_t otherRep = equivalenceClasses.getRoot(other);
+ Index groupRep = equivalenceClasses.getRoot(group);
+ Index 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
@@ -504,7 +504,7 @@ struct MinimizeRecGroups : Pass {
if (groups[groupRep].classInfo) {
auto& classInfo = *groups[groupRep].classInfo;
- [[maybe_unused]] size_t unionRep =
+ [[maybe_unused]] Index unionRep =
equivalenceClasses.getUnion(groupRep, otherRep);
assert(groupRep == unionRep);
@@ -525,7 +525,7 @@ struct MinimizeRecGroups : Pass {
if (groups[otherRep].classInfo) {
auto& classInfo = *groups[otherRep].classInfo;
- [[maybe_unused]] size_t unionRep =
+ [[maybe_unused]] Index unionRep =
equivalenceClasses.getUnion(otherRep, groupRep);
assert(otherRep == unionRep);
@@ -572,7 +572,7 @@ struct MinimizeRecGroups : Pass {
shapesToUpdate.push_back(other);
}
- std::vector<size_t>
+ std::vector<Index>
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
@@ -664,7 +664,7 @@ struct MinimizeRecGroups : Pass {
// 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) {
+ for (Index i = 0; i < types.size(); ++i) {
dfsOrders[i].reserve(types.size());
std::vector<HeapType> workList;
workList.push_back(types[i]);
@@ -712,7 +712,7 @@ struct MinimizeRecGroups : Pass {
// 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;
+ std::unordered_map<HeapType, Index> indexInLeastOrder;
for (auto type : leastOrder) {
indexInLeastOrder.insert({type, indexInLeastOrder.size()});
}
@@ -725,7 +725,7 @@ struct MinimizeRecGroups : Pass {
}
std::vector<HeapType> finalOrder;
finalOrder.reserve(types.size());
- for (size_t i = 0; i < classSize; ++i) {
+ for (Index i = 0; i < classSize; ++i) {
for (auto& [shape, members] : typeClasses) {
finalOrder.push_back(members[i]);
}
@@ -733,11 +733,11 @@ struct MinimizeRecGroups : Pass {
// 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;
+ std::unordered_map<HeapType, Index> indexInFinalOrder;
for (auto type : finalOrder) {
indexInFinalOrder.insert({type, indexInFinalOrder.size()});
}
- std::vector<size_t> permutation;
+ std::vector<Index> permutation;
permutation.reserve(types.size());
for (auto type : types) {
permutation.push_back(indexInFinalOrder.at(type));
@@ -747,10 +747,10 @@ struct MinimizeRecGroups : Pass {
void rewriteTypes(Module& wasm) {
// Map types to indices in the builder.
- std::unordered_map<HeapType, size_t> outputIndices;
- size_t i = 0;
+ std::unordered_map<HeapType, Index> outputIndices;
+ Index i = 0;
for (const auto& group : groups) {
- for (size_t j = 0; j < group.group.size(); ++j) {
+ for (Index 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});
@@ -781,7 +781,7 @@ struct MinimizeRecGroups : Pass {
std::unordered_map<HeapType, HeapType> oldToNew;
i = 0;
for (const auto& group : groups) {
- for (size_t j = 0; j < group.group.size(); ++j) {
+ for (Index 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];
diff --git a/src/passes/ReorderGlobals.cpp b/src/passes/ReorderGlobals.cpp
index c5432f006..af0b9572a 100644
--- a/src/passes/ReorderGlobals.cpp
+++ b/src/passes/ReorderGlobals.cpp
@@ -77,7 +77,7 @@ struct ReorderGlobals : public Pass {
// use the index of the global in the original ordering to identify each
// global. A different ordering is then a vector of old indices, saying where
// each element comes from, which is logically a mapping between indices.
- using IndexIndexMap = std::vector<size_t>;
+ using IndexIndexMap = std::vector<Index>;
// We will also track counts of uses for each global. We use floating-point
// values here since while the initial counts are integers, we will be
@@ -126,7 +126,7 @@ struct ReorderGlobals : public Pass {
// (global $b i32 (global.get $a)) ;; $b depends on $a; $a must be first
//
// To do so we construct a map from each global to those that depends on it.
- std::vector<std::unordered_set<size_t>> dependentSets(globals.size());
+ std::vector<std::unordered_set<Index>> dependentSets(globals.size());
for (Index i = 0; i < globals.size(); i++) {
auto& global = globals[i];
if (!global->imported()) {
@@ -138,7 +138,7 @@ struct ReorderGlobals : public Pass {
}
TopologicalSort::Graph deps;
deps.reserve(globals.size());
- for (size_t i = 0; i < globals.size(); ++i) {
+ for (Index i = 0; i < globals.size(); ++i) {
deps.emplace_back(dependentSets[i].begin(), dependentSets[i].end());
}
@@ -241,7 +241,7 @@ struct ReorderGlobals : public Pass {
// Now use that optimal order to create an ordered graph that includes the
// dependencies. The final order will be the minimum topological sort of
// this graph.
- return TopologicalSort::minSort(deps, [&](size_t a, size_t b) {
+ return TopologicalSort::minSort(deps, [&](Index a, Index b) {
// Imports always go first. The binary writer takes care of this itself
// anyhow, but it is better to do it here in the IR so we can actually
// see what the final layout will be.
@@ -287,8 +287,8 @@ struct ReorderGlobals : public Pass {
// Track the size in bits and the next index at which the size increases. At
// the first iteration we'll compute the size of the LEB for index 0, and so
// forth.
- size_t sizeInBits = 0;
- size_t nextSizeIncrease = 0;
+ Index sizeInBits = 0;
+ Index nextSizeIncrease = 0;
for (Index i = 0; i < indices.size(); i++) {
if (i == nextSizeIncrease) {
sizeInBits++;
diff --git a/src/support/topological_orders.h b/src/support/topological_orders.h
index 925ad1117..bc6609ae0 100644
--- a/src/support/topological_orders.h
+++ b/src/support/topological_orders.h
@@ -27,22 +27,27 @@
#include <variant>
#include <vector>
+#include "support/index.h"
+
namespace wasm {
namespace TopologicalSort {
-// An adjacency list containing edges from vertices to their successors.
-using Graph = std::vector<std::vector<size_t>>;
+// An adjacency list containing edges from vertices to their successors. Uses
+// `Index` because we are primarily sorting elements of Wasm modules. If we ever
+// need to sort signficantly larger objects, we might need to switch to
+// `size_t` or make this a template parameter.
+using Graph = std::vector<std::vector<Index>>;
// Return a topological sort of the vertices in the given adjacency graph.
-inline std::vector<size_t> sort(const Graph& graph);
+inline std::vector<Index> sort(const Graph& graph);
// A utility that finds a topological sort of a graph with arbitrary element
// types. The provided iterators must be to pairs of elements and collections of
// their children.
template<typename It> decltype(auto) sortOf(It begin, It end) {
using T = std::remove_cv_t<typename It::value_type::first_type>;
- std::unordered_map<T, size_t> indices;
+ std::unordered_map<T, Index> indices;
std::vector<T> elements;
// Assign indices to each element.
for (auto it = begin; it != end; ++it) {
@@ -71,8 +76,8 @@ template<typename It> decltype(auto) sortOf(It begin, It end) {
// Return the topological sort of the vertices in the given adjacency graph that
// is lexicographically minimal with respect to the provided comparator on
// vertex indices. Implemented using a min-heap internally.
-template<typename F = std::less<size_t>>
-std::vector<size_t> minSort(const Graph& graph, F cmp = std::less<size_t>{});
+template<typename F = std::less<Index>>
+std::vector<Index> minSort(const Graph& graph, F cmp = std::less<Index>{});
} // namespace TopologicalSort
@@ -88,10 +93,10 @@ using TopologicalOrders = TopologicalOrdersImpl<std::monostate>;
// detail of `minSort`.
template<typename Cmp> struct TopologicalOrdersImpl {
using Graph = TopologicalSort::Graph;
- using value_type = const std::vector<size_t>;
+ using value_type = const std::vector<Index>;
using difference_type = std::ptrdiff_t;
- using reference = const std::vector<size_t>&;
- using pointer = const std::vector<size_t>*;
+ using reference = const std::vector<Index>&;
+ using pointer = const std::vector<Index>*;
using iterator_category = std::input_iterator_tag;
// Takes an adjacency list, where the list for each vertex is a sorted list of
@@ -108,8 +113,8 @@ template<typename Cmp> struct TopologicalOrdersImpl {
bool operator!=(const TopologicalOrdersImpl& other) const {
return !(*this == other);
}
- const std::vector<size_t>& operator*() const { return buf; }
- const std::vector<size_t>* operator->() const { return &buf; }
+ const std::vector<Index>& operator*() const { return buf; }
+ const std::vector<Index>* operator->() const { return &buf; }
TopologicalOrdersImpl& operator++() {
// Find the last selector that can be advanced, popping any that cannot.
std::optional<Selector> next;
@@ -149,7 +154,7 @@ private:
selectors.reserve(graph.size());
selectors.push_back({0, 0, 0});
auto& first = selectors.back();
- for (size_t i = 0; i < graph.size(); ++i) {
+ for (Index i = 0; i < graph.size(); ++i) {
if (indegrees[i] == 0) {
if constexpr (useMinHeap) {
pushChoice(i);
@@ -172,14 +177,14 @@ private:
// The current in-degrees for each vertex. When a vertex is appended to our
// permutation, the in-degrees of its children are decremented and those that
// go to zero become available for the next selection.
- std::vector<size_t> indegrees;
+ std::vector<Index> indegrees;
// The buffer in which we are constructing a permutation. It contains a
// sequence of selected vertices followed by a sequence of possible choices
// for the next vertex.
- std::vector<size_t> buf;
+ std::vector<Index> buf;
// When we are finding a minimal topological order, store the possible
// choices in this separate min-heap instead of directly in `buf`.
- std::vector<size_t> choiceHeap;
+ std::vector<Index> choiceHeap;
// When we are finding a minimal topological order, use this function to
// compare possible choices. Empty iff we are not finding a minimal
// topological order.
@@ -192,11 +197,11 @@ private:
struct Selector {
// The start index of the sequence of available choices. Also the index
// where we place the current choice.
- size_t start;
+ Index start;
// The number of choices we have.
- size_t count;
+ Index count;
// The index of the current choice in the original order.
- size_t index;
+ Index index;
// Select the next available vertex, decrement in-degrees, and update the
// sequence of available vertices. Return the Selector for the next vertex.
@@ -246,7 +251,7 @@ private:
// we leave everything how we found it so the previous selector can make
// its next selection without observing anything having changed in the
// meantime.
- for (size_t i = 1; i < count; ++i) {
+ for (Index i = 1; i < count; ++i) {
ctx.buf[start + i - 1] = ctx.buf[start + i];
}
ctx.buf[start + count - 1] = unselected;
@@ -259,16 +264,16 @@ private:
}
};
- void pushChoice(size_t choice) {
+ void pushChoice(Index choice) {
choiceHeap.push_back(choice);
- std::push_heap(choiceHeap.begin(),
- choiceHeap.end(),
- [&](size_t a, size_t b) { return cmp(b, a); });
+ std::push_heap(choiceHeap.begin(), choiceHeap.end(), [&](Index a, Index b) {
+ return cmp(b, a);
+ });
}
- size_t popChoice() {
- std::pop_heap(choiceHeap.begin(),
- choiceHeap.end(),
- [&](size_t a, size_t b) { return cmp(b, a); });
+ Index popChoice() {
+ std::pop_heap(choiceHeap.begin(), choiceHeap.end(), [&](Index a, Index b) {
+ return cmp(b, a);
+ });
auto choice = choiceHeap.back();
choiceHeap.pop_back();
return choice;
@@ -278,17 +283,16 @@ private:
// Empty if we've already seen every possible ordering.
std::vector<Selector> selectors;
- friend std::vector<size_t> TopologicalSort::minSort<Cmp>(const Graph&, Cmp);
+ friend std::vector<Index> TopologicalSort::minSort<Cmp>(const Graph&, Cmp);
};
namespace TopologicalSort {
-std::vector<size_t> sort(const Graph& graph) {
+std::vector<Index> sort(const Graph& graph) {
return *TopologicalOrders(graph);
}
-template<typename Cmp>
-std::vector<size_t> minSort(const Graph& graph, Cmp cmp) {
+template<typename Cmp> std::vector<Index> minSort(const Graph& graph, Cmp cmp) {
return *TopologicalOrdersImpl<Cmp>(graph, cmp);
}
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-10 02:28:07 +0000