| 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 ...
|