ISLE: rewrite operation on `select` to `select` on operation

[Kmeakin]

trafficstars

Rewrites operations on select to select on operations (eg ineg(select(cond, x, y)) => select(cond, ineg(x), ineg(y)). This transform is not obviously beneficial by itself, but it may expose more opportunities for other rewrite rules to trigger.

I'm not sure I put the extractor/constructor definitions for unop/binop/ternop in the correct places. Let me know if I should move them somewhere else.

[jameysharp]

If you don't mind, @abrown, I'd like to take this one.

There's definitely something worth doing along these lines, and I really like that you got unop/binop/ternop to work completely generically.

I have two high-level concerns at the moment:

1. The cost model shouldn't be picking a three-instruction implementation when it has a two-instruction version available unless the duplicated instructions have zero cost, which these don't. So I don't understand why the new tests in this PR are passing, and I'm worried this might be highlighting a bug in the egraph pass generally.
2. I'd guess that we'd do better by checking if both branches of select have the same instruction and pulling it outside, rather than by pushing instructions inside.

[Kmeakin]

2. I'd guess that we'd do better by checking if both branches of select have the same instruction and pulling it outside, rather than by pushing instructions inside.

I'm not sure what you mean by this. We already rewrite select(cond, x, x) => x. Could you give an example of what you have in mind?

[jameysharp]

I mean rules like this:

(rule (simplify (select _ cond (unop ty op x @ (value_type ity)) (unop ty op y @ (value_type ity))))
      (unop ty op (select ity cond x y))

So it's not that the "true" and "false" branches are the same value, but that they're produced by applying the same operation to different values. This extends to instructions with more operands, where all but one of the operands is the same in both branches.

For instructions with two or three operands, we could also write rules that try to split into multiple selects, but I haven't decided whether that's a good idea. It would look like this (some type-checks omitted for clarity):

(rule (simplify (select _ cond (binop ty op a b) (binop ty op c d)))
      (binop ty op (select ty cond a c) (select ty cond b d)))

(rule (simplify (select _ cond (ternop ty op a b c) (ternop ty op d e f)))
      (ternop ty op (select ty cond a d) (select ty cond b e) (select ty cond c f)))

Together with the existing (select ty cond x x) rule, these rules cover the cases where some operands are the same in both branches. I like the idea of writing exactly one rule for each of unop, binop, and ternop. It's not clear to me though whether these rules will pull their weight in general.

[Kmeakin]

The cost model shouldn't be picking a three-instruction implementation when it has a two-instruction version available unless the duplicated instructions have zero cost, which these don't. So I don't understand why the new tests in this PR are passing, and I'm worried this might be highlighting a bug in the egraph pass generally.

Different forms seem to be preferred depending on the order the instructions appear in (see transpose_unop_both_1 and transpose_unop_both_2). Could it be related to https://github.com/bytecodealliance/wasmtime/issues/6126?

[jameysharp]

I don't think this is the same issue as #6126.

Hmmm. I wonder if the types specified for the newly-constructed instructions are wrong?

For example, in transpose_unop_select, it's producing v12 = ineg v3, but that instruction should have trivially unified with v4 = ineg v3 through the GVN map. The only thing that I think could be different about the two instructions is their controlling type.

I'm not sure how to run the CLIF verifier after the egraph pass but I think we should turn that on for filetests if it isn't on already.

@cfallin, could you take a think at the output in the filetests in this PR?

[cfallin]

@cfallin, could you take a think at the output in the filetests in this PR?

I'm not sure what's going on, to be honest -- I stared at the examples for a while but nothing jumps out at me as a possible reason. All of the outputs are correct, at least. It's hard to say more without looking at a debug trace-log.

[github-actions[bot]]

Subscribe to Label Action

cc @cfallin, @fitzgen

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 .github/subscribe-to-label.json configuration file.

Learn more.