Stream: cranelift

Topic: ISLE and e-matching optimizations

Maja Kądziołka (Mar 03 2023 at 18:44):

I'm pondering how matching rules like these gets implemented:

;; `or(and(x, y), not(y)) == or(x, not(y))`
(rule (simplify (bor ty
                     (band ty x y)
                     z @ (bnot ty y)))
      (bor ty x z))

Currently, if I understand correctly, this does the following

• if we're simplifying a bor node, iterate over the first argument's e-class, looking for band nodes
• for each band node, bind x and y and iterate over the e-class of z, looking for bnot nodes
• for each bnot node, check whether y matches what we bound before

Instead, once we know y (and ty, for that matter), we could lookup bnot ty y in the e-graph's hashcons and check whether it's in the same e-class as z (rejecting the match if bnot ty y is not represented in the e-graph).

I agree that for this one rule this might seem like a micro-optimization, but I'm looking to use ISLE for another application, where a matching strategy like this would make a big difference. Unfortunately it seems to me like this is quite hard to reconcile with the current semantics of ISLE...

Maja Kądziołka (Mar 03 2023 at 20:45):

I suppose this might be expressible with lots of manual if let, but that's just painful...

Chris Fallin (Mar 05 2023 at 02:20):

Hi @Maja Kądziołka -- it is indeed true that the current way that we have chosen to bind ISLE to the egraphs framework does a step-by-step exhaustive search, as you've described.

I don't think that this is an inescapable aspect of the design though; first of all, one needs to separate ISLE (the language) from "Cranelift bindings in ISLE" (i.e., the external extractors and constructors we've defined). ISLE-the-language is fairly low-level in its matching strategy, in that it will freely evaluate external extractors and try to match LHSes in sequence, subject to merging of rules.

I suspect one might be able to define a sort of "DSLeDSL" (DSL embedded in DSL) where the LHS extractors return a lazily-evaluated "Match of bor at this enode" value of sorts, and other etors when given this as a starting point, build upon it. Then you basically have an AST describing a query. There are some plumbing details there around how to yield bound variables properly that would need more thought.

There may be other ways too. I guess I would reflect back to you: we've built ISLE to fit our needs; what changes do you think it needs to fit yours? If you're willing to build such changes, e.g. as a set of primitive features needed to build up to your solution, or an alternate search mode, or something like that, we'd love to talk more!

Maja Kądziołka (Mar 05 2023 at 02:35):

As far as the DSLeDSL goes, it is certainly an elegant idea on paper. I'll certainly give it some thought, though I'm not sure whether that won't defeat the purpose of ISLE...

Ultimately to give ISLE the capability of making use of the e-graph fully, you'd need to give it the option to call a constructor within the pattern, when all the variables are known. Of course, when a relevant annotation is present that tells it that this is reasonable to do for this constructor.

It would probably also be nice to make the distinction between "I need this node, create it if necessary" and "i need a reference to the existing copy of this node, if any".

It kinda feels like a third concept, next to constructors and extractors, but also kinda not really? Definitely seems like a big enough change that you wouldn't want to carry it upstream without a use case in cranelift ifself...

Maja Kądziołka (Mar 05 2023 at 02:47):

(there is at least one rule in cranelift that could benefit from this, but I'd be surprised if this was considered a satisfactory justification)

Jamey Sharp (Mar 06 2023 at 22:59):

I've been idly considering what it would look like to make ISLE generate bottom-up matchers, in the style of https://en.wikipedia.org/wiki/Rete_algorithm: because we know we call the ISLE-generated code for instructions in dominator-tree order, ISLE could build its own tables for matching subtrees, and ensure that every call only needs to look at the root of an expression tree. That's a time-space trade-off: it makes matching ~linear in the number of instructions regardless of the complexity of the patterns, but it uses more memory to store the intermediate matches.

I think your suggestion is interesting because it hadn't occurred to me that doing lookups in the egraph's GVN map is sort of a middle-ground position that re-uses data we're already storing anyway. It still requires exhaustive search over eclasses sometimes, but it sounds like a nice optimization when it applies.

To get ISLE to do this you'd need to find extractor calls where all operands are equality constraints. I think that's a pattern that's pretty easy to find in the intermediate data structures ISLE uses. I'm less sure how we'd want to express an alternate codegen strategy for this case in the ISLE source language, but it's an interesting idea.

Last updated: Nov 22 2024 at 17:03 UTC