Stream: git-wasmtime

Topic: wasmtime / PR #11239 Implement Tarjan's strongly-connecte...

Wasmtime GitHub notifications bot (Jul 15 2025 at 01:12):

fitzgen opened PR #11239 from fitzgen:tarjan-scc to bytecodealliance:main:

This commit implements [Tarjan's algorithm] for finding strongly-connected components.

This algorithm takes O(V+E) time and uses O(V+E) space.

Tarjan's algorithm is usually presented as a recursive algorithm, but we do not trust the input and cannot recurse over it for fear of blowing the stack. Therefore, this implementation is iterative.

This will be used to do bottom-up inlining in Wasmtime's compilation orchestration.

[Tarjan's algorithm]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

<!--
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 15 2025 at 01:12):

fitzgen requested alexcrichton for a review on PR #11239.

Wasmtime GitHub notifications bot (Jul 15 2025 at 01:12):

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

Wasmtime GitHub notifications bot (Jul 15 2025 at 01:12):

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

Wasmtime GitHub notifications bot (Jul 15 2025 at 01:13):

fitzgen updated PR #11239.

Wasmtime GitHub notifications bot (Jul 15 2025 at 12:43):

fitzgen updated PR #11239.

Wasmtime GitHub notifications bot (Jul 15 2025 at 14:22):

alexcrichton commented on PR #11239:

I'm feeling a bit overwhelmed recently so I'm going to re-roll review.

Wasmtime GitHub notifications bot (Jul 15 2025 at 14:23):

alexcrichton requested abrown for a review on PR #11239.

Wasmtime GitHub notifications bot (Jul 15 2025 at 14:23):

alexcrichton requested wasmtime-compiler-reviewers for a review on PR #11239.

Wasmtime GitHub notifications bot (Jul 15 2025 at 15:55):

cfallin commented on PR #11239:

(I'm happy to cover this one as a "core compiler algorithms PR" unless you really want it, Andrew!)

Wasmtime GitHub notifications bot (Jul 15 2025 at 16:14):

abrown commented on PR #11239:

Go for it!

Wasmtime GitHub notifications bot (Jul 15 2025 at 16:34):

cfallin created PR review comment:

Just a little optimization thing but perhaps we could use a length hint (perhaps from Iterator::size_hint) to pre-allocate using with_capacity?

Wasmtime GitHub notifications bot (Jul 15 2025 at 16:34):

cfallin created PR review comment:

Can we reuse self.nodes(component) here and below?

Wasmtime GitHub notifications bot (Jul 15 2025 at 16:34):

cfallin submitted PR review:

Very nice! A few thoughts below but overall LGTM.

Wasmtime GitHub notifications bot (Jul 15 2025 at 16:34):

cfallin created PR review comment:

This is a neat iterator chain but I wonder if it would be clearer in imperative style in this case (vs. the chaining and nested if-expression returning an option) -- something like:

for successor in successors(node) {
  self.stack.push(DfsEvent::AfterEdge(node, successor));
  if !seen(successor) {
    self.stack.push(DfsEvent::Pre(successor));
  }
}

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

fitzgen created PR review comment:

That technically implies an extra bounds check unless LLVM optimizes it away, but I can factor out the range conversion and indexing bits into a shared helper.

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

fitzgen submitted PR review.

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

cfallin submitted PR review.

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

cfallin created PR review comment:

Ah, good point! Not a huge deal, just noticed the duplication.

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

fitzgen submitted PR review.

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

fitzgen created PR review comment:

Yeah this is a reflection of how it was originally written and then modified as I found and fixed bugs. Should have moved it over to pushes already.

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

fitzgen updated PR #11239.

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

fitzgen has enabled auto merge for PR #11239.

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

fitzgen merged PR #11239.

Last updated: Dec 06 2025 at 07:03 UTC