Stream: git-wasmtime

Topic: wasmtime / PR #3560 Add ISLE reference documentation.


view this post on Zulip Wasmtime GitHub notifications bot (Nov 24 2021 at 00:47):

cfallin opened PR #3560 from isle-docs to main:

Markdown rendered

This documentation provides details for all of the ISLE language
features, and detailed rationale for why many of them are designed in
the way that they are. It is hopefully both a reasonable tutorial and
reference for someone looking to understand the DSL.

Note that this documentation is separate from and orthogonal to the
work to document the Cranelift bindings and integration work that
@fitzgen has covered well in #3556. This document can link to that one
and vice-versa once they are both in-tree.

In addition to @fitzgen I'm picking a few folks for reviewers who would
likely be consumers of this doc; please do let me know if there are holes
or not-clear parts anywhere!

<!--

Please ensure that the following steps are all taken care of before submitting
the PR.

Please ensure all communication adheres to the code of conduct.
-->

view this post on Zulip Wasmtime GitHub notifications bot (Nov 24 2021 at 00:47):

cfallin requested abrown for a review on PR #3560.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 24 2021 at 00:47):

cfallin requested alexcrichton for a review on PR #3560.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 24 2021 at 00:47):

cfallin requested fitzgen for a review on PR #3560.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 24 2021 at 03:32):

cfallin updated PR #3560 from isle-docs to main.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

nit: the point about "until no more rules are applicable" isn't necessarily a characteristic of term rewriting systems in general (many systems have rules that can apply an infinite number of times, like a -> -(-a). I'd suggest leaving that part out or replacing with something like "until the term meets some application-specific end condition".

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Could add here that programs don't need to consider the complex tree when changing a single rule, since it is auto-generated by the ISLE compiler.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

I might add here that term rewriting allows a nice separation between specifying when rules are possible and when they are profitable/desired (since not all term rewriting systems choose to apply more specific rules first).

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

nit: closing paren

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Can all ISLE terms/expressions operate on either CLIF or the machine dependent IR? That is, can we think of rules are operating on the language that is the union of the input and output languages? Or does something prevent compiler writers from adding a term that rewrites a machine dependent IR term back into a higher level term?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Give example?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

And boolean constants, as below?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

This is cool!

Does this mean (A 1 _) -> ... and (A 2 _) -> ... would share the function created for (A ...)?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Are wildcards the same as symbolic variables here? Sorry if this if a CLIF distinction I'm just unaware of!

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Again, this is system/application specific.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Maybe just me, but I don't follow the sentence starting with "Here...". Does here mean in the previous generic instruction selection example, or in ISEL?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Can wildcards be used as constructions if they are nested? I.e. (A (_ 1 x))?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Could be fun here to add a footnote that some systems (e.g., equality graphs in theorem proving) support applying multiple rules "at once" and only choosing the best one after exploring many possible results. Sadly, I'm not sure that there are any more general-audience-friendly write-ups of this: https://cseweb.ucsd.edu/~lerner/papers/popl09.html

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Could call out here that symbolic is more special than the other primitives, since it's not a construct in the language itself (I assume?)

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

nit: the (extern ...) syntax was not introduced above but is here in the "summary", I would leave the syntax for the next section

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

nit: around

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Maybe name this as the "context trait" here to make the rest of this section more clear?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

This is a bit confusing since before in the general parts "constructor" was also used for LHS. I'm also not seeing yet how this works with the heuristic of precedence for more-specific rules (though maybe that's coming)

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

nit: spell out instruction selection

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Does the system error if two rules with identical priorities both apply? Or fall back to the previous heuristic? What if both rules complete the match?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Why usually and not always?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

In this case, backtracking is impossible, correct? So nodes can only be used in backtracking if they are not enum destructors?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Questions/comments at this point:

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

This post is about a specific tool but a little more general-audience-friendly: https://blog.sigplan.org/2021/04/06/equality-saturation-with-egg/

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

Would this be disallowed if the middle range were [0, 1]? Where in the system would a failure happen if this were attempted?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

A range because child nodes can differ in priority?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 28 2021 at 21:57):

avanhatt created PR review comment:

This also will make testing/fuzzing much easier, presumably :D

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 00:57):

avanhatt edited PR review comment.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 00:58):

avanhatt edited PR review comment.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 18:20):

abrown submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 18:20):

abrown created PR review comment:

  interface) of sorts to allow interaction with Rust code, and

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 18:20):

abrown created PR review comment:

Is this right?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 18:20):

abrown submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

"backtracking" is a little strange to see here to me, because we specifically don't do any backtracking

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

Elsewhere (and at the top of this document) we've defined it as "instruction selection lowering expressions"

This document will describe ISLE (Instruction Selection Lowering

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

These last two bullet points are indented one space deeper than the earlier bullet points, fwiw.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

  interface) of sorts to allow interacting with Rust code, and

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

omg I've been writing footnotes by hand in markdown for years, I had no idea that (at least for github markdown) this existed

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

This file should probably belong in cranelift/isle/docs/reference.md or something next to the other ISLE-specific documentation that is in the isle README.md (and could probably be split out into multiple .md files)

e.g. we don't have the ISLE compiler implementation docs under cranelift/docs/* and I don't think it would make sense to move them there

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

  the term is exactly equal to this constant.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

Does this section have any information that isn't present in that comment?

This level of implementation detail seems better reserved for code comments (as linked to here) or implementation overviews (as in the README), not language reference.

I think this section can probably be removed.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:22):

fitzgen created PR review comment:

I personally feel like there is way more background here than necessary and it will overwhelm people who just want to learn the semantics of ISLE so they can hack on Cranelift's instruction selection.

Like everything about Turing completeness seems like an aside that, while interesting, is mostly irrelevant.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:32):

fitzgen submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:32):

fitzgen created PR review comment:

Err actually this may have been a github rendering artifact

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:32):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:32):

cfallin created PR review comment:

We do actually, depending on how you look at it! Specifically one can see the decision-trie traversal as a depth-first attempt at finding a path to a leaf node, where we backtrack up the tree when a match op fails. In the generated Rust this manifests as a control-flow edge that falls out of the if match_condition { ... } without returning a Some(result). The "explicit backtracking stack pop" step that one would see in an FSM-like implementation implicitly happens because (i) PC encodes a path through match ops, and we effectively truncate that path by falling through, and (ii) local let-bindings go out of scope, backing up our state.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:36):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:36):

cfallin created PR review comment:

Apparently the syntax even allows symbolic footnote names (though I tend to just do numbers so it reads ok as plain text too)! And GitHub's markdown renderer recently started to support actually rendering them; it didn't last time I wrote an RFC :-)

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:43):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:43):

cfallin created PR review comment:

Maybe, but that's IMHO there is value in introducing the philosophy behind the approach and the language as well; I'm thinking a bit broader than just folks who want to hack on Cranelift, and this is meant to be reference documentation more than a tutorial. E.g. someone might not realize that it's possible to solve a problem in a certain way by recursing through term-rewrites, unless one is already familiar with the general field; one might not understand how term-rewriting came about and what it can be used for. I want to be helpful to that sort of newcomer who may not be as well-read in the field :-)

Said another way, somewhere we should do a deep-dive with all the details and thinking behind ISLE; this is meant to be that deep-dive, more than a quickstart.

There is definitely room for a "learn just enough about the DSL to be proficient at instruction lowering rules" tutorial to exist, though; or I guess it already sort of does, in the docs (README's tutorial at least) that you've written?

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 19:43):

cfallin edited PR review comment.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 20:48):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 29 2021 at 20:48):

cfallin created PR review comment:

Thinking about this a bit more -- I can probably wrap the whole TRS section in a "This section provides background on the general term-rewriting-system concept; please feel free to skip ahead if you just want details on ISLE" goto; that gives the context and background for those who want it without making it a necessary prerequisite.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:41):

cfallin updated PR #3560 from isle-docs to main.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:44):

cfallin updated PR #3560 from isle-docs to main.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:45):

cfallin updated PR #3560 from isle-docs to main.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:46):

cfallin created PR review comment:

Ah, OK, I was following your PR's lead (cranelift/docs/isle-integration.md) but I've moved both this and the ISLE-Cranelift integration doc into cranelift/isle/docs/. (Also renamed isle-integration.md to cranelift-integration.md since it's now within the ISLE tree.) This is nicer, agreed!

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:46):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:46):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:46):

cfallin created PR review comment:

Computer architect muscle memory! Fixed.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:47):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:47):

cfallin created PR review comment:

Yes, I think so, but I agree it's pretty terse, so I expanded it with an explanation :-)

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:47):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:47):

cfallin created PR review comment:

Done as above, added a reader-goto around the section "if you just want details...".

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:50):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:50):

cfallin created PR review comment:

Good point, the description of the algorithm itself is probably better left to the single canonical place in the source; removed that. I left the high-level description of the trie and added a note ("We describe this data structure below with the intent to provide an understanding of how the DSL compiler...") as I think it's useful to have this mental model whenever questions of how the generated code will work come up.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:50):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:50):

cfallin created PR review comment:

Yes, that's a good point! Updated as suggested.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:50):

cfallin created PR review comment:

Added this point, thanks.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:51):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:51):

cfallin created PR review comment:

Updated (removed "symbolic" here and clarified elsewhere) -- sorry for the confusion here. "Symbolic" in this context just meant an externally-defined, imported symbolic name for a particular concrete value; e.g. $MYVALUE for a u32. It's not actually a different type of primitive so I removed its mention here.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:52):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:52):

cfallin created PR review comment:

Just a pattern-matching operator, not anything CLIF-specific!

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:52):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:52):

cfallin created PR review comment:

Thanks, I added a footnote on this!

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:53):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:53):

cfallin created PR review comment:

Yes, exactly; all of the logic to rewrite (A ...) is invoked from one function entry point.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:53):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:53):

cfallin created PR review comment:

Done.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:54):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:54):

cfallin created PR review comment:

No, a constructor form has to have a concrete constructor name; no polymorphism in that dimension. Added clarification, thanks.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:54):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:54):

cfallin created PR review comment:

Clarified, thanks.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:56):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:56):

cfallin created PR review comment:

My mistake, it actually is always, in this context; I was thinking of constructor signatures in general, as they are infallible when imported (Rust code called from the RHS is not allowed to fail/backtrack). In this context we're only discussing internal constructors, so that doesn't apply; updated.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:56):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:56):

cfallin created PR review comment:

Done.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:58):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:58):

cfallin created PR review comment:

Indeed! No concrete plans yet to independently test the generated code but possibly we could come up with an alternate implementation of the input side (the extractors), maybe even inventing the operand tree as we go (carry the arbitrary::Unstructured in the context object and then generate things on demand). cc @fitzgen for possible fuzzing opportunity :-)

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:59):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 19:59):

cfallin created PR review comment:

Updated, thanks.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:02):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:02):

cfallin created PR review comment:

ISLE itself is agnostic to the underlying IR, it just knows about extractors and constructors and various types that the user defines; so one could have (decl compile_to_machine1 (CLIF) MachInst1) and (decl compile_to_machine2 (CLIF) MachInst2) and (decl optimize (CLIF) CLIF) and define rules for each. At least with the first two, we have a type-level guarantee that lowering goes in the proper direction. The latter could have convergence issues but we could limit the number of passes rather than chase a fixpoint indefinitely. Later in the doc ("A Note on Heterogeneous Types") touches on this distinction from other TRS-based instruction selector systems; hopefully that clarifies a bit more!

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:03):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:03):

cfallin created PR review comment:

There will be an error if two rules have exactly the same LHS pattern, but not otherwise; the more-specific-first heuristic breaks the tie.

I added some text about this and about how it's implementation-defined (i.e. the heuristic could change, and rules shouldn't rely on it for correctness, unlike priorities which have specifically-defined semantics).

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:03):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:03):

cfallin created PR review comment:

Updated language here to talk about "terms" instead, thanks for pointing this out!

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:04):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:04):

cfallin created PR review comment:

Yes, exactly. I ended up removing these few paragraphs because the code also has a similar block comment describing the trie building, but the idea is that it captures the range so that we can allow subtrees to merge as long as there is no intermediate-priority rule that has to be tried before part of the subtree and after another part.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:10):

cfallin created PR review comment:

I created #3574 to record this.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:10):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:15):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:15):

cfallin created PR review comment:

Backtracking (up the decision trie) is still possible if no match arm matches; e.g. one can have

match value {
    Value::A { ref x, ref y } => { ... return Some(...); }
    Value::B { ref z } => { ... return Some(...); }
    _ => {}
}
None

We always add the _ => {} catch-all, as we don't do exhaustiveness checking on the match arms. (We silence the unreachable-code warning so that rustc, which does do this, doesn't complain!)

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:16):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:16):

cfallin created PR review comment:

Yes, we would avoid building a trie like that, but it wouldn't cause a failure, but rather a tree-split. The block comment in trie.rs covers this a bit better than this summary here (which I removed in favor of just pointing to the block comment).

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:27):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:27):

cfallin created PR review comment:

show how this decision trie algorithm handles the more-and-less specific rule examples from the beginning

There's a bit more discussion in the block comment that's referenced now, but as far as the more-specific-first ordering, it's a bit subtle. IMHO the best way may not be to try to get the programmer to predict the current algorithm but just to make it a more explicit and well-defined ordering. I created #3575 for this.

brief reference that instruction selection is in general NP-complete

Added a note that collapsing the rule patterns to a fast-dispatch match is not guaranteed, and that worst-case complexity per rewrite is equivalent to a sequential attempt at each rule in turn. The way that we integrate ISLE into our lowering/isel framework I think takes care of the weighted set cover kind of NP-completeness that one generally has when doing isel over the dataflow graph (we do greedy matching) but the complexity is certainly still something to be aware of.

What should engineers consider when adding new ISLE rules? [interaction between ISLE and traditional isel, other details]

@fitzgen's doc I think covers this pretty well, hopefully! If not then we can definitely add more pointers/tips as we encounter/come up with them.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:40):

fitzgen submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 20:40):

fitzgen created PR review comment:

Wait, but the isle-integration.md stuff is Cranelift-specific, so it does make sense to be inside cranelift/docs.

Where as this documentation is just about ISLE and not any specific embedding, so it makes sense it should be under cranelift/isle/docs so it is a part of the ISLE crate/package.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 21:21):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 21:21):

cfallin created PR review comment:

Ah, two different perspectives I guess. I had figured putting all ISLE-related documentation in one place made sense, otherwise a newcomer who just knows "ISLE is an isel thing" and goes looking for its documentation might miss some of it. I don't care too much either way though, so I'm happy to move it back.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 21:25):

cfallin updated PR #3560 from isle-docs to main.

view this post on Zulip Wasmtime GitHub notifications bot (Nov 30 2021 at 22:10):

cfallin merged PR #3560.


Last updated: Nov 22 2024 at 17:03 UTC