Stream: git-wasmtime

Topic: wasmtime / PR #10468 `cranelift-frontend`: Propagate need...

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:13):

fitzgen opened PR #10468 from fitzgen:stack-map-var-to-val-during-finalization to bytecodealliance:main:

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.

<!--
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 (Mar 25 2025 at 17:13):

fitzgen requested alexcrichton for a review on PR #10468.

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:13):

fitzgen requested wasmtime-fuzz-reviewers for a review on PR #10468.

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:13):

fitzgen requested cfallin for a review on PR #10468.

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:13):

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

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:17):

bjorn3 submitted PR review.

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:17):

bjorn3 created PR review comment:

This is quadratic, right? O(#vars * #vals)

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:40):

fitzgen submitted PR review.

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:40):

fitzgen created PR review comment:

The values_for_var function is not O(vars * vals) but the loop calling values_for_vars in finalization is. I'm unsure which part of the code you are referring to with this comment.

And while that finalization loop is O(vars * vals) in the worse case where every variable is marked as needing a stack map and every value is associated with not just one but every single variable, I wouldn't really call that quadratic because vars and vals are two independent big-O variables. Similarly, I wouldn't really call an O(edges * vertices) graph algorithm quadratic.

Either way, I don't think it actually matters in this case. It shouldn't be possible to write a Wasm program that constructs that worst case input or anything like it. And it would be pretty difficult to accidentally generate this code with any typical cranelift_frontend usage (even in the face of translating untrusted code to CLIF). It would require using the cranelift_frontend API directly in a fairly malicious way to create that worst case.

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:56):

cfallin submitted PR review:

LGTM; this is simpler as well as fixing the issue, so thanks for revisiting!

Wasmtime GitHub notifications bot (Mar 25 2025 at 17:56):

cfallin created PR review comment:

Maybe one way of seeing this is that values are subordinate to variables: so we aren't taking a cross-product of all vars with all vals, but performing some work for each value, and we get to all the values by traversing the per-var bins of values.

Said more simply: this is linear in the size of the IR; but all of compilation is already at least linear in the size of the IR, so we aren't introducing any additional blowup here, I think.

Wasmtime GitHub notifications bot (Mar 25 2025 at 18:08):

bjorn3 submitted PR review.

Wasmtime GitHub notifications bot (Mar 25 2025 at 18:08):

bjorn3 created PR review comment:

When I saw the use of filter while quickly looking at it, for some reason I mistakenly thought each values_for_var call iterated over the full list of values in the function filtering just those applicable to the given variable. Reading it again, this is indeed not what happens.

Wasmtime GitHub notifications bot (Mar 25 2025 at 19:25):

fitzgen updated PR #10468.

Wasmtime GitHub notifications bot (Mar 25 2025 at 19:25):

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

Wasmtime GitHub notifications bot (Mar 25 2025 at 19:25):

fitzgen has enabled auto merge for PR #10468.

Wasmtime GitHub notifications bot (Mar 25 2025 at 20:02):

fitzgen merged PR #10468.

Last updated: Apr 18 2025 at 09:03 UTC