Stream: git-wasmtime

Topic: wasmtime / PR #11269 Stratification of call graphs for pa...

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:17):

fitzgen opened PR #11269 from fitzgen:stratification to bytecodealliance:main:

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 ith layer must be processed before the i + 1th 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.

<!--
Please make sure you include the following information:

• If this work has been discussed elsewhere, please include a link to that
  conversation. If it was discussed in an issue, just mention "issue #...".

• Explain why this change is needed. If the details are in an issue already,
  this can be brief.

Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.html

Please ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:17):

fitzgen requested abrown for a review on PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:17):

fitzgen requested wasmtime-compiler-reviewers for a review on PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:17):

fitzgen requested pchickey for a review on PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:17):

fitzgen requested wasmtime-core-reviewers for a review on PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:17):

fitzgen requested cfallin for a review on PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:17):

fitzgen requested wasmtime-core-reviewers for a review on PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:17):

fitzgen requested wasmtime-compiler-reviewers for a review on PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:21):

fitzgen updated PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:40):

cfallin submitted PR review:

This looks great! Very happy to see this coming together. The dependency-based scheduling into layers looks exactly like I'd expect.

One thought below on a potential abstraction opportunity but otherwise LGTM

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:40):

cfallin created PR review comment:

We should clarify the scope and soundness/completeness of the call graph here -- in particular, with respect to imports and indirect calls (one could pick any of several set-points to get e.g. an overapproximation that's sound, or an underapproximation that gives partial but exact answers, and I think inlining wants the latter)

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:40):

cfallin created PR review comment:

Idle thought -- we have this idiom a lot (list-of-lists stored in a flattened manner, with ranges in another list). It might be nice to build an abstraction around it -- something like

let mut elems = edge_elems.start_range();
elems.extend_from_slice(...); // or elems.push or whatever
edges[caller] = elems.finish();

not necessarily in this PR but as a cleanup at some point.

We do have Ranges which optimizes for the case that we build the ranges themselves in-order so we can store only one end of the range (and use previous-end as start); here we're processing callers in arbitrary order.

Wasmtime GitHub notifications bot (Jul 17 2025 at 19:40):

cfallin created PR review comment:

(Actually, on reading further down and seeing more instances of this pattern -- I suspect it might be a nice cleanup in this PR!)

Wasmtime GitHub notifications bot (Jul 17 2025 at 21:15):

fitzgen updated PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 21:15):

fitzgen has enabled auto merge for PR #11269.

Wasmtime GitHub notifications bot (Jul 17 2025 at 21:53):

fitzgen merged PR #11269.

Last updated: Dec 06 2025 at 07:03 UTC