Conversation
The binary writer already takes care to order rec groups to minimize the size taken to encode type indices throughout the module, but it cannot order types within a rec group because that would change their identity. MinimizeRecGroups can be used to split the type section into small recursion groups that can be ordered by the binary writer, but that pass does not optimize the order of types within a rec group. Furthermore, if the minimal early rec groups are large, all the extra types taking up valuable index space can cause a large code size overhead. To get the best possible outcome, add a TypeOrdering pass that creates a single large rec group, giving the types the most possible flexibility to be moved around, and orders the types within it. As we do in ReorderGlobals, try multiple tolological sorts with different factors for adjusting weights based on successor types, then choose the best ordering. Refactoring so that ReorderGlobals and ReorderTypes can share more code is left as future work. To avoid reimplementing all of the GlobalTypeRewriter utility, which already rewrites all the private types into a single rec group, factor out just the part that sorts the types and make it overrideable in subclasses.
src/ir/type-updating.h
Outdated
|
|
||
| // Given the predecessor graph of the types to be rebuilt, return a list of | ||
| // the types in the order in which they will be rebuilt. Users can override | ||
| // this to inject placeholders for extra types ore use custom logic to sort |
There was a problem hiding this comment.
| // this to inject placeholders for extra types ore use custom logic to sort | |
| // this to inject placeholders for extra types or use custom logic to sort |
src/passes/ReorderTypes.cpp
Outdated
| // contribution from successors, then pick the best result. | ||
| static constexpr float minFactor = 0.0; | ||
| static constexpr float maxFactor = 1.0; | ||
| static constexpr Index buckets = 21; |
There was a problem hiding this comment.
Perhaps explain what "bucket" is?
There was a problem hiding this comment.
I renamed buckets to numFactors, which is hopefully more self-explanatory.
src/passes/ReorderTypes.cpp
Outdated
|
|
||
| // Accumulate weights. Start with the use counts for each type, then add the | ||
| // adjusted weight for each successor to the weights of its predecessors. | ||
| std::vector<float> weights(numTypes * buckets); |
There was a problem hiding this comment.
My guess is that each bucket is an entirely separate sorting attempt. If so, why store all of them in the same vector? I would expect either
- Iteration over attempts, not storing them all in memory at once, or
std::vector<std::vector<..>>if they do need to be in memory at once for some reason I'm missing.
There was a problem hiding this comment.
Good idea. I've refactored it to do one sort at a time and not keep all the weights in memory.
src/passes/ReorderTypes.cpp
Outdated
| std::vector<Index> bestSort; | ||
| Index bestCost = 0; | ||
| for (Index i = 0; i < buckets; ++i) { | ||
| auto curr = TopologicalSort::minSort(succs, [&](Index a, Index b) { |
There was a problem hiding this comment.
Is this guaranteed to be deterministic when there are ties?
There was a problem hiding this comment.
Yes, the traversal order on the graph is deterministic and the topological sort utility does not introduce any non-determinism.
There was a problem hiding this comment.
It would be good to also add a test file with the non-testing variant, just for some coverage. Maybe just with something minimal there.
kripken
left a comment
There was a problem hiding this comment.
Might also be good to have a test with enough types for the LEB size to matter, so we cover the "7" in the source. Not urgent, and I guess it would be covered well enough if we refactor to use the same sorting as in ReorderGlobals (as that one is heavily tested).
|
The fuzzer hits a V8 failure: 😄 We can either skip this file, or add that error to |
|
Should we document this on the GC optimizer cookbook? https://github.com/WebAssembly/binaryen/wiki/GC-Optimization-Guidebook |
|
Sure, I've just added a section on "Type Reordering and Rec Group Minimization." |
|
Thanks! |
The binary writer already takes care to order rec groups to minimize the
size taken to encode type indices throughout the module, but it cannot
order types within a rec group because that would change their identity.
MinimizeRecGroups can be used to split the type section into small
recursion groups that can be ordered by the binary writer, but that pass
does not optimize the order of types within a rec group. Furthermore, if
the minimal early rec groups are large, all the extra types taking up
valuable index space can cause a large code size overhead.
To get the best possible outcome, add a TypeOrdering pass that creates a
single large rec group, giving the types the most possible flexibility
to be moved around, and orders the types within it. As we do in
ReorderGlobals, try multiple tolological sorts with different factors
for adjusting weights based on successor types, then choose the best
ordering. Refactoring so that ReorderGlobals and ReorderTypes can share
more code is left as future work.
To avoid reimplementing all of the GlobalTypeRewriter utility, which
already rewrites all the private types into a single rec group, factor
out just the part that sorts the types and make it overrideable in
subclasses.