Stream: git-wasmtime

Topic: wasmtime / PR #8935 ISLE: Make block codegen non-recursive

Wasmtime GitHub notifications bot (Jul 10 2024 at 21:31):

jameysharp requested wasmtime-compiler-reviewers for a review on PR #8935.

Wasmtime GitHub notifications bot (Jul 10 2024 at 21:31):

jameysharp requested fitzgen for a review on PR #8935.

Wasmtime GitHub notifications bot (Jul 10 2024 at 21:31):

jameysharp opened PR #8935 from jameysharp:isle-no-recursion to bytecodealliance:main:

In #8919 we learned that Codegen::emit_block can overrun the stack when generating Rust source for deeply-nested blocks. Stack usage can be worse than one might expect because ISLE is called from a build script, and those are always built in debug mode.

This commit avoids the problem by using an explicit heap-allocated stack instead of recursion.

I recommend turning on the "ignore whitespace" option in your diff tool of choice when reviewing this commit.

The amount of stack space that this recursive function uses is affected by the version of rustc used to compile it, and the amount of stack space available depends on the host platform. As a result, this was only observed on Windows with a recent nightly version of rustc, but it could eventually affect other platforms or compiler versions, especially as ISLE rules grow in complexity.

Note that there are several other places in ISLE which recurse over the user-provided rules. This commit does not change those, but they could also become a problem in the future.

Wasmtime GitHub notifications bot (Jul 10 2024 at 22:31):

fitzgen submitted PR review:

Broadly LGTM, but the details of the stack's management is a little obscured IMO, so I have some suggestions below. If you feel strongly that I am off base here, however, I can be convinced otherwise. Let me know!

Wasmtime GitHub notifications bot (Jul 10 2024 at 22:31):

fitzgen created PR review comment:

Can this method take these things as arguments, instead of popping them? IIUC, that would allow the while let loop to do ctx.stack.pop() instead of ctx.stack.last_mut() which would make reasoning about control flow and termination much more straightforward, IMO, since it would all be localized within the same function.

Wasmtime GitHub notifications bot (Jul 10 2024 at 22:31):

fitzgen created PR review comment:

I can't seem to find anything that pops the Nested::Arms entries from the stack -- does that ever happen? If not, is that a bug? I would assume it is?

Wasmtime GitHub notifications bot (Jul 10 2024 at 22:31):

fitzgen submitted PR review:

Broadly LGTM, but the details of the stack's management is a little obscured IMO, so I have some suggestions below. If you feel strongly that I am off base here, however, I can be convinced otherwise. Let me know!

Wasmtime GitHub notifications bot (Jul 10 2024 at 22:31):

fitzgen created PR review comment:

Similarly, soft preference for having begin_nested (or begin_block, and removing begin_nested) return the stack entry and having callers do something like

let entry = ctx.begin_nested()?;
ctx.stack.push(entry);

For the same reasons, I think this would make it a little easier to understand what's happening here.

Wasmtime GitHub notifications bot (Jul 10 2024 at 22:31):

fitzgen created PR review comment:

D'oh it is the else { ctx.end_nested() } that does the pop.

This kinda highlights what I was talking about w.r.t. following control and reasoning about termination, though.

I see that it is a little tricky though because of how we are pumping this iterator and only actually popping this stack entry once the iterator is exhausted. It is, of course, possible to pop the iterator and then push it back on if it is not empty (would require a peekable iterator) and this would be fine. But it might be more natural or "simpler" (depending on your taste) to instead push a separate stack entry for each item in the iterator. This latter approach doesn't require any extra is-it-done-or-not wrangling, which is kind of nice. It does use probably mean more entries pushed onto the stack and therefore potentially a larger heap allocation, but I don't think that matters at all here.

Wasmtime GitHub notifications bot (Jul 10 2024 at 23:44):

github-actions[bot] commented on PR #8935:

Subscribe to Label Action

cc @cfallin, @fitzgen

<details>
This issue or pull request has been labeled: "cranelift", "isle"

Thus the following users have been cc'd because of the following labels:

• cfallin: isle
• fitzgen: isle

To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.

Learn more.
</details>

Wasmtime GitHub notifications bot (Jul 11 2024 at 07:40):

jameysharp updated PR #8935.

Wasmtime GitHub notifications bot (Jul 11 2024 at 07:55):

jameysharp commented on PR #8935:

I've now made the stack local to emit_block, and also used pop instead of last. I don't think the result can be honestly said to be clear, but I agree that it's less unclear than it was before :sweat_smile:

It's actually important to have some special treatment of the end of a list of cases or match-arms: we need to print some stuff and reset some state about what's still in scope. So if I take your suggestion of pushing each case/arm individually onto the stack, I also would need to push something like Nested::EndBlock { last_line, scope } first, which is certainly possible but is a fair bit more complexity each time stuff gets pushed onto the stack. Since that happens in more places (five) than calls to end_block (two), I feel like that's overall worse. But I'm still open to suggestions, and also may think differently about this after I get some sleep.

Wasmtime GitHub notifications bot (Jul 11 2024 at 16:38):

fitzgen submitted PR review:

I like this version a lot better, thank you!

Wasmtime GitHub notifications bot (Jul 11 2024 at 16:54):

fitzgen merged PR #8935.

Last updated: Dec 23 2024 at 12:05 UTC