| 3c9305c0 | 17-Jul-2025 |
Nick Fitzgerald <[email protected]> |
Stratification of call graphs for parallel bottom-up inlining (#11269)
* Stratification of call graphs for parallel bottom-up inlining
This commit takes a call graph and constructs a strata, which
Stratification of call graphs for parallel bottom-up inlining (#11269)
* Stratification of call graphs for parallel bottom-up inlining
This commit takes a call graph and constructs a strata, which is essentially a
parallel execution plan. A strata consists of an ordered sequence of layers, and
a layer of an unordered set of functions. The `i`th layer must be processed
before the `i + 1`th layer, but functions within the same layer may be processed
in any order (and in parallel).
For example, when given the following tree-like call graph:
+---+ +---+ +---+
| a |-->| b |-->| c |
+---+ +---+ +---+
| |
| | +---+
| '---->| d |
| +---+
|
| +---+ +---+
'---->| e |-->| f |
+---+ +---+
|
| +---+
'---->| g |
+---+
then stratification will produce these layers:
[
{c, d, f, g},
{b, e},
{a},
]
Our goal in constructing the layers is to maximize potential parallelism at each
layer. Logically, we do this by finding the strongly-connected components of the
input call graph and peeling off all of the leaves of SCCs'
condensation (i.e. the DAG that the SCCs form; see the documentation for the
`StronglyConnectedComponents::evaporation` method for details). These leaves
become the strata's first layer. The layer's components are removed from the
condensation graph, and we repeat the process, so that the condensation's new
leaves become the strata's second layer, and etc... until the condensation graph
is empty and all components have been processed. In practice we don't actually
mutate the condensation graph or remove its nodes but instead count how many
unprocessed dependencies each component has, and a component is ready for
inclusion in a layer once its unprocessed-dependencies count reaches zero.
This commit also renames the entity type for strongly-connected components from
`Component` to `Scc`, as I felt the former was a bit ambiguous given Wasm
components.
The next PR will extend Wasmtime's compilation driver code to actually make use
of this new infrastructure.
* Address review feedback
show more ...
|
| bf9273a3 | 25-Mar-2025 |
Nick Fitzgerald <[email protected]> |
`cranelift-frontend`: Propagate needs-stack-map from variables to values during finalization (#10468)
* cranelift-frontend: Propagate needs-stack-map from variables to values during finalization
Ra
`cranelift-frontend`: Propagate needs-stack-map from variables to values during finalization (#10468)
* cranelift-frontend: Propagate needs-stack-map from variables to values during finalization
Rather than trying to propagate the needs-stack-map bit from variables to values
online, while we are building the IR and defining and using variables, wait
until the function is being finalized, and then propagate everything all at
once. This avoids potential repeated work and is easier to ensure that it is
complete and covers all values associated with a variable, since by the time we
are finalizing the function, we won't add any new values for a variable that we
will need to keep track of and propagate this information to.
This also means that we can remove the `params_added_to_blocks` vector from the
SSA side effects structure, since it was only used to online-update the
`stack_map_values` set.
* Initialize the env-logger in `#[wasmtime_test]`
* Fix needs-stack-map set iteration
For reasons I do not understand, the `EntitySet::keys` method includes keys that
are not in the set, and we have unit tests asserting this bizarre behavior. Very
perplexing. So I added a new method to iterate over just the elements of the
set.
show more ...
|