Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: add a way to declare variables in rewrite rules #37423

Open
josharian opened this issue Feb 24, 2020 · 12 comments
Open

cmd/compile: add a way to declare variables in rewrite rules #37423

josharian opened this issue Feb 24, 2020 · 12 comments
Milestone

Comments

@josharian
Copy link
Contributor

@josharian josharian commented Feb 24, 2020

Consider this rewrite rule: (Div32F (Const32F [c]) (Const32F [d])) && !math.IsNaN(float64(auxTo32F(c) / auxTo32F(d))) -> (Const32F [auxFrom32F(auxTo32F(c) / auxTo32F(d))])

It'd be a lot easier to read and write (and compile) if we could declare a variable somewhere to hold the value auxTo32F(c) / auxTo32F(d). I run into this a fair amount.

Maybe we could let the condition section contain short variable declarations?

(Div32F (Const32F [c]) (Const32F [d])) && quo := auxTo32F(c) / auxTo32F(d) && !math.IsNaN(float64(quo)) -> (Const32F [auxFrom32F(quo)])

It looks a bit weird. Other ideas?

Kinda related: #30818

cc @mvdan @randall77

@gopherbot
Copy link

@gopherbot gopherbot commented Feb 25, 2020

Change https://golang.org/cl/220684 mentions this issue: cmd/compile: support := in rewrite rule conditions

@josharian
Copy link
Contributor Author

@josharian josharian commented Feb 25, 2020

I hacked up a CL to allow := in conditions, to see what it looked like, and for us to play with.

(Thanks, @mvdan, for your rulegen improvements. They make doing stuff like this so much easier.)

Having added a few := conditions to test my code, I still think it looks kinda weird...but it definitely is also kind of nice.

@josharian
Copy link
Contributor Author

@josharian josharian commented Feb 25, 2020

CL 220696 contains a demo showing what this would look like in a few real-life rules.

@mundaym
Copy link
Member

@mundaym mundaym commented Feb 25, 2020

This could potentially be really valuable in a CL like CL 173659 that uses helper types heavily (rot.FromAux(r) is repeated a lot). Though that particular example would probably be helped more by Keith's strongly typed aux field change (CL 190197). Speaking of which that CL would probably also help your example too.

Another syntax idea might be to borrow the from if statements a little bit (if quo := auxTo32F(c) / auxTo32F(d); quo == quo {) to make the boolean evaluation more explicit:

(Div32F (Const32F [c]) (Const32F [d]))
     && quo := auxTo32F(c) / auxTo32F(d); quo == quo
     -> (Const32F [auxFrom32F(quo)])
@mvdan
Copy link
Member

@mvdan mvdan commented Feb 25, 2020

&& quo := auxTo32F(c) / auxTo32F(d) &&

I'm not a big fan of this because the syntax seems ambiguous. One might read && foo := bar && baz as && (foo := bar) && baz, or as && foo := (bar && baz).

Though I'm not a fan of parentheses for this use case. I like @mundaym's suggestion to reuse semicolons a little better.

Here's another idea; don't try to fit this straight into the rule, as we could end with complex syntax all in one single "expression". We don't want to have a full language, but we could add a couple more elements to it, like:

with quo := auxTo32F(c) / auxTo32F(d) {
    (Div32F (Const32F [c]) (Const32F [d]))
        && quo == quo
        -> (Const32F [auxFrom32F(quo)])
    // other rules that use "quo" too
}

We could also allow many such scoped definitions, like with foo := x; bar := y { ... }. They would be like if stmt; expr { ... }, but without the expression.

The reason I make this suggestion is because I think it would keep the code readable, and allow us to reuse definitions across multiple related rules without having to mess with global variables or macros.

@cagedmantis cagedmantis added this to the Backlog milestone Feb 27, 2020
@josharian
Copy link
Contributor Author

@josharian josharian commented Feb 27, 2020

I'm not a big fan of this because the syntax seems ambiguous.

Yeah, that's a bummer. We're not exactly using a bulletproof parser for this (as I discovered recently when I wrote something like && noteRule("x -> y")), but still. We could insist on parens to get the && foo := (bar && baz) interpretation.

suggestion to reuse semicolons a little better.

I like the semicolon idea (and it could then subsume #30818 by allowing any statement), but there's one weird case, the last cond/stmt before the arrow.

Instead of

(Foo [c]) && c != 0 && z := c+1 -> (Bar [z])

you'd have to write

(Foo [c]) && c != 0 && z := c+1; -> (Bar [z])

Here's another idea; don't try to fit this straight into the rule

I think it'd be better to be inline, because it makes scoping obvious, and gives more control over order of evaluation (for both semantics and performance).

@ALTree
Copy link
Member

@ALTree ALTree commented Feb 28, 2020

The fundamental issue here is that we started with a LISP-like parenthesized prefix notation for the rules, but then tried to bolt on more syntax that departed from the S-expressions ways of writing things.

I think adding even more may be a mistake. If anything, I would move back to a more regular (and easier to write a parser for!) LISP-like prefix notation.

I understand that many people don't like the LISP fully-parenthesized notation, but this weird mix of prefix/infix is starting to show its limitations.

@josharian
Copy link
Contributor Author

@josharian josharian commented Mar 1, 2020

If anything, I would move back to a more regular (and easier to write a parser for!) LISP-like prefix notation.

Do you have a concrete suggestion that we can discuss? That often helps.

I am sympathetic to this, but I'm not sure I agree. I don't actually care that the parser isn't bulletproof; I care that the DSL is easy to use, read, and reason about. The rewrite rules are very much a shop built jig.

@ALTree
Copy link
Member

@ALTree ALTree commented Mar 2, 2020

Do you have a concrete suggestion that we can discuss?

Rules are in the form:

LHS -> RHS

where LHS and RHS are S-expressions. Someone would actually suggest that the whole expression should be an S-expr:

(-> LHS RHS )

but maybe it's not necessary. Keeping pattern-arrow-replacement (in this order) may be clearer.

This rule is already in the LHS -> RHS form:

(Mod8 x y) -> (Select1 (DIVW  (SignExt8to16 x) (SignExt8to16 y)))

No Go-like calls. It's (clobber x y z), not clobber(x,y,z). To tell apart patterns to match and Go functions to call (for the result, or for side effects), you'll have to quote one or the other, e.g. (#clobber x y z)

No mix of infix && and S-expressions. This:

(ADCQ x (MOVQconst [c]) carry) && is32Bit(c)

becomes

(and
  (ADCQ x (MOVQconst [c]) carry)
  (#is32Bit c))

If you don't like that and is the top-level operator, you could make up something like match:

(match 
  (Load <t> ptr mem)
  (#is32BitInt t)) 
-> (MOVLload ptr mem)

What to introduce variable declaration? No need to come up with new syntax. Your example above:

(match
  (Foo [c])
  (!= c 0)
  (let z (+ c 1)))
-> (Bar [z])

Allowing side-effects expressions in the RHS (proposed in #30818)? Call it progn or anything else you like, and write:

-> (progn
     (#clobber l)
     (ADDQload x [off] {sym} ptr mem))

progn evaluates to the last of its args, and all the others are just called for side effects.

The ( | | ) syntax is not a S-expr so it'll need to be changed, maybe by introducing some special marker other than (:

(Mod[64|32|16] x y) -> (Select1 (DIV[Q|L|W] x y))

I am sympathetic to this, but I'm not sure I agree. I don't actually care that the parser isn't bulletproof; I care that the DSL is easy to use, read, and reason about.

You don't have to like any of this, obviously. I'm just throwing out this idea because it seems possible to me that in some (near, or maybe far) future we'll start to realize that the rules syntax is getting too hairy to handle, and if it ever becomes clear that what was build is too hard to extend with new syntax, you may want to reconsider the whole approach, and turn to something that is simpler, and more regular.

S-expr && gofunctioncall( ) seemed simple enough, but now you want to introduce variables declaration and it seemed to me (reading the discussion above) that you may be starting to realize that that is harder than it looks. Yet, I don't know if we are at the breaking point (or if we will ever get there), so it's possible that going back to a more strict approach based on s-expr will never be actually necessary.

@josharian
Copy link
Contributor Author

@josharian josharian commented Apr 18, 2020

Another possible syntax for this would be to use backticks to indicate that a statement is meant to be inserted directly inline:

(Foo [c]) && c != 0 && `z := c+1` -> (Bar [z])

That solves the ambiguity problem, and doesn't have the weird trailing semicolon issue.

@mvdan
Copy link
Member

@mvdan mvdan commented Apr 18, 2020

This last idea is pretty hacky but I like it. We could limit its power by only allowing declarations initially, and perhaps expand it to any single statement later. It would complicate the rules language for sure, but it's not really meant to be used directly by anyone other than rulegen anyway.

@nightlyone
Copy link
Contributor

@nightlyone nightlyone commented Apr 18, 2020

Another approach could be to CSE the expressions instead of giving an expression a symbol as the author of a rule.

That will help the generated code but keep the human written code a little repetitive. But the repetitions actually help readability in the examples shown, since one doesn't have to juggle so many symbols.

The small helper functions the Go team introduces all time are pretty good at keeping the rules small and understandable.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants
You can’t perform that action at this time.