wasmtime / PR #5435 cranelift-isle: codegen from new IR · git-wasmtime

Stream: git-wasmtime

Topic: wasmtime / PR #5435 cranelift-isle: codegen from new IR

Wasmtime GitHub notifications bot (Dec 14 2022 at 02:48):

jameysharp opened PR #5435 from isle-codegen to main:

ISLE's existing code-generation strategy doesn't generate the most efficient matching order for rules. This PR completely replaces it.

With this PR applied, wasmtime compile retires 2% fewer instructions on the pulldown-cmark and spidermonkey benchmarks from Sightglass.

A dev build of cranelift-codegen from an empty target/ directory takes 2% less time. The build script, invoking ISLE, takes a little longer, but Rust can compile the generated code faster, so it balances out.

This PR is ready for review, but I'm expecting review to take a few rounds of back-and-forth while we figure out what comments I should have written.

Wasmtime GitHub notifications bot (Dec 14 2022 at 02:48):

jameysharp requested cfallin for a review on PR #5435.

Wasmtime GitHub notifications bot (Dec 14 2022 at 20:10):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Dec 14 2022 at 22:47):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Better name -- something like ReadyTracker?

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

I wonder if there's a better name here: maybe Item or Seq or something like that?

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Verify that equality constraints are processed in the right order, such that we always have one non-Matched input to trigger the evaluation? Consider e.g. a == b, c == d, b == c in order: after the first two, all four are Matched but we haven't yet processed b == c...

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Comment here to describe how many rules may reach this point: if not a multi-term, and if we've passed the overlap checker, then we should only have one rule if there is nothing to split on. But in a multi-term we may just be left with a bunch of rules to evaluate in priority order

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

A top-level doc comment describing the structure of the code would be helpful here!

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Can we define what order is here? Is it necessary to carry it separately from Ready or can it be integrated?

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

doc: indexed by binding ID

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Document order: on input, it contains indices of rules we need to order at this point in recursion tree?

Document recursion: does the recursive structure of the calls mirror the tree structure of output?

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Also: document that there is one ReadyTracker per block; they are created recursively

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Make note of binding-dependence-ID-order invariant allowing for a single pass propagation of transitive availability here

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Can we explicitly list all Binding kinds here so that adding a new one forces consideration of this property?

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

This is super-confusing and it seems maybe a different representation is in order: why should there ever be a test of source == source present? The explanation given seems to indicate that this triggers some other check; if so can we make that explicit?

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

changed here needs to consider whether set_ready above (line 225) updated the readiness of source as well

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Note here that the order is load-bearing, and why this order?

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Clarify invariant here and elsewhere: are the bindings named in Condition variants required to already be use_expr'd, or does the consumer of the Conditions do so?

Wasmtime GitHub notifications bot (Dec 15 2022 at 00:30):

cfallin created PR review comment:

Define what this means: produce a result (return or add to list of results)?

Wasmtime GitHub notifications bot (Dec 17 2022 at 01:31):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Dec 20 2022 at 01:17):

cfallin created PR review comment:

The name scrutinee is a little... archaic?... here -- perhaps something like emit_expr_for_constraint_eval()?

Wasmtime GitHub notifications bot (Dec 20 2022 at 01:17):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 20 2022 at 01:17):

cfallin created PR review comment:

Can we add a TODO here with the issue tracking a more full-featured integer type system in ISLE?

Wasmtime GitHub notifications bot (Dec 20 2022 at 01:17):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 21 2022 at 02:43):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Dec 21 2022 at 23:50):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Dec 22 2022 at 02:15):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Dec 22 2022 at 17:52):

cfallin created PR review comment:

A helper on equal might make this idiom a little clearer: it's basically asserting that x and y have overlapping equivalence classes (at least one element in common), right? Maybe something like self.equal.overlaps(x, y)?

Wasmtime GitHub notifications bot (Dec 22 2022 at 17:52):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 22 2022 at 17:52):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 22 2022 at 17:52):

cfallin created PR review comment:

This version of the logic is really close to complete, I think; the main thing that's still a bit unsatisfying to me is the dual use of HasControlFlow::Equal(x, y) as a sort of sentinel for "check anything related to x (and normally inserted as Equal(x, x) but the second tuple field is ignored here) and as an actual pair to emit a check for below. Could we instead have two variants on HasControlFlow for the two cases, something like EqualityInvolving(x) and Equal(x, y)? Then we can insert the former as a candidate elsewhere, and we can panic if we see it when converting to ControlFlow. (Alternately, two different enums, one for the domain of each stage of processing; but I'm fine with keeping the union of the domains in one enum for expediency here if you want.)

Wasmtime GitHub notifications bot (Dec 22 2022 at 17:52):

cfallin created PR review comment:

Could we have a bit more on the comment above describing why we are asserting something about equality-check candidates in particular below?

Wasmtime GitHub notifications bot (Dec 22 2022 at 17:52):

cfallin created PR review comment:

Is this just a reverse sort...? Could we use Reverse if so (sort_unstable_by_key(|x| Reverse(*x)) or somesuch)?

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:41):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:41):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:41):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:41):

jameysharp created PR review comment:

Nope, I can't add to the comment to explain why I did that, because I shouldn't have done that. :laughing:

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:41):

jameysharp created PR review comment:

Good idea. I'm adding a DisjointSets::in_same_set helper and using it the three places that I had some variant of this idiom.

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:41):

jameysharp created PR review comment:

It is just a reverse sort, yes. by_key is annoying for types that aren't Copy, and I didn't want to make Candidate be Copy because I'd rather have the compiler tell me if I tried to copy it somewhere I didn't intend to. Using by instead lets me operate on borrows.

If it helps, I could write it as x.cmp(y).reverse(). I didn't do that because we run this from a build script, so it's built in debug mode, which means these calls aren't inlined and have a non-trivial cost. But I haven't measured, so that might just be premature optimization.

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:41):

jameysharp created PR review comment:

I'm still hesitant to stop (mis-)using HasControlFlow::Equal in this way because every alternative I've considered so far feels worse to me. But I've at least changed it so that this quirk is entirely contained within best_control_flow, and I've improved the comments there about it. Now anywhere outside that function, the Equal variant only appears with two different binding sites. And I'm still thinking about whether I can improve this further.

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:44):

cfallin created PR review comment:

Also now that I look at it again: is it meant to be x.zip(y), that is, find if there's an overlap but only if the identical element is at the same position in both sequences, or is it meant instead to be an all-pairs check?

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:44):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:45):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 22 2022 at 23:45):

cfallin created PR review comment:

Fair enough; just a comment "note that x and y are reversed below, to sort in reverse" is probably enough then, IMHO.

Wasmtime GitHub notifications bot (Dec 23 2022 at 01:18):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Dec 23 2022 at 01:18):

jameysharp created PR review comment:

I _think_ I've confused you because I used Option::zip, not Iterator::zip. The Iterator for Option returns zero or one results for None or Some, respectively, so the two are equivalent, but it might be easier to think of this as more like a logical-and.

So this says, if DisjointSets::find returns Some(representative) of a set for both lookups, and the representative is the same for both, then return true.

Wasmtime GitHub notifications bot (Dec 23 2022 at 01:25):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Dec 23 2022 at 01:25):

cfallin created PR review comment:

Ah! Right, I had somehow thought this was an iteration over the whole equivalence class. That makes much more sense, thanks.

Wasmtime GitHub notifications bot (Dec 23 2022 at 01:26):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Dec 23 2022 at 01:26):

jameysharp created PR review comment:

Sure thing! I've added that comment locally now. I don't feel like making CI run again for a comment change so I'll push it after building the translation verifier we talked about.

Wasmtime GitHub notifications bot (Jan 12 2023 at 23:22):

elliottt submitted PR review.

Wasmtime GitHub notifications bot (Jan 12 2023 at 23:22):

elliottt created PR review comment:

Is it worth stating here that the returned index will always be <= partition_point?

Wasmtime GitHub notifications bot (Jan 12 2023 at 23:32):

elliottt submitted PR review.

Wasmtime GitHub notifications bot (Jan 12 2023 at 23:32):

elliottt created PR review comment:

    /// Construct a candidate where the sort key is not set. The score will

Wasmtime GitHub notifications bot (Jan 12 2023 at 23:41):

elliottt submitted PR review.

Wasmtime GitHub notifications bot (Jan 12 2023 at 23:41):

elliottt created PR review comment:

There are more references to fields named score as sort key, so maybe this isn't a big deal :)

Wasmtime GitHub notifications bot (Jan 13 2023 at 00:12):

elliottt submitted PR review.

Wasmtime GitHub notifications bot (Jan 13 2023 at 00:12):

elliottt created PR review comment:

Is this because that would generate dead code?

Wasmtime GitHub notifications bot (Jan 13 2023 at 00:31):

elliottt submitted PR review.

Wasmtime GitHub notifications bot (Jan 13 2023 at 00:31):

elliottt created PR review comment:

What do you think about introducing a function on HasControlFlow called something like any_equiv_class that constructs the Equal(source, source) case? Something like:
impl HasControlFlow {
  fn any_equivalence_class(source: BindingId) -> Self {
    Self::Equal(source, source)
  }
}
It might help when seeing uses where the args are the same.

Wasmtime GitHub notifications bot (Jan 13 2023 at 00:44):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Jan 13 2023 at 00:44):

jameysharp created PR review comment:

Good question. No, I was concerned about the codegen going into an infinite loop of trying to match the same binding site repeatedly. The first time, it would reduce the partition to only those rules that all have the same pattern for that binding site. Matching the same binding site again within that partition won't move any rules out of the partition and it won't make any more binding sites available, so we'd come back to the same evaluation point without making any progress.

The other argument for this is that there's never anything to be gained from matching a binding site when you're in an evaluation path where you already know exactly what pattern that binding site matches. But the full justification for that is a little complicated because you have to reason about both fall-through cases and equality constraints. It's probably worth writing that argument out in some more detail, but the thought of doing so is making me tired :sweat_smile:

Wasmtime GitHub notifications bot (Jan 13 2023 at 00:55):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Jan 13 2023 at 00:55):

jameysharp created PR review comment:

Or maybe it means I should make changes in more places than this for consistency :sweat_smile:

I was hoping the doc comment for Score describing it as "A sort key ..." would be clear enough about the two terms being interchangeable. But then, if they're interchangeable, then why not pick one and stick with it?

Wasmtime GitHub notifications bot (Jan 13 2023 at 01:21):

elliottt submitted PR review.

Wasmtime GitHub notifications bot (Jan 13 2023 at 01:21):

elliottt created PR review comment:

Maybe emit_source to mirror the name from the Match constructor?

Wasmtime GitHub notifications bot (Jan 13 2023 at 02:49):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Jan 13 2023 at 02:50):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Jan 13 2023 at 02:50):

jameysharp created PR review comment:

Since both you and Chris found the Equal(x, x) pattern confusing, I've implemented an alternative. What do you think of 2bb7988?

Wasmtime GitHub notifications bot (Jan 13 2023 at 02:56):

jameysharp updated PR #5435 from isle-codegen to main.

Wasmtime GitHub notifications bot (Jan 13 2023 at 02:57):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Jan 13 2023 at 02:57):

jameysharp created PR review comment:

I like "scrutinee", and it's what the Rust reference calls that part of a match expression—but Trevor's suggestion is compelling enough I've taken it. Thanks!

Wasmtime GitHub notifications bot (Jan 20 2023 at 22:11):

cfallin submitted PR review.

Wasmtime GitHub notifications bot (Jan 23 2023 at 20:27):

jameysharp merged PR #5435.

Last updated: Dec 23 2024 at 12:05 UTC