Stream: git-wasmtime

Topic: wasmtime / issue #5709 Legalize `b{and,or,xor}_not` into ...

Wasmtime GitHub notifications bot (Feb 04 2023 at 22:19):

alexcrichton commented on issue #5709:

Ok I've pushed up an alternate strategy of reaching my goal:

• Legalization has been added to "break apart" the band_not and other related instructions
• All backend lowerings for band_not and related instructions are moved up to pattern-matching

A single egraph-rule is retained for x^-1 being translated to ~x, which is enough to trigger wasm modules to use andn on x86_64, for example.

One shortcoming remaining, however, is that the backends currently only pattern match (band x (bnot y)), not (band (bnot y) x), for example. This means that if the order of the operands in the *.wat test I added are swapped then the andn instruction isn't generated. Is this something that should be fixed with an egraph rule? I thought I remembered reading there's a "move constants to the right" rule so should there similarly be a "move bnot to the right" rule? Or should the backends all have duplicate patterns for each order?

Wasmtime GitHub notifications bot (Feb 04 2023 at 23:01):

cfallin commented on issue #5709:

One shortcoming remaining, however, is that the backends currently only pattern match (band x (bnot y)), not (band (bnot y) x), for example. This means that if the order of the operands in the *.wat test I added are swapped then the andn instruction isn't generated. Is this something that should be fixed with an egraph rule? I thought I remembered reading there's a "move constants to the right" rule so should there similarly be a "move bnot to the right" rule?

That seems like a reasonable thing to try, yup!

Wasmtime GitHub notifications bot (Feb 05 2023 at 00:46):

alexcrichton commented on issue #5709:

Ok I've pushed up a commit which does that and it seems to work well for at least the small unit tests.

Wasmtime GitHub notifications bot (Feb 06 2023 at 16:23):

jameysharp commented on issue #5709:

I wouldn't expect a "move bnot to the right" egraph rule to work reliably for backend patterns. It correctly declares that they're equivalent expressions, but then during elaboration we pick one expression as our final choice to hand to the backend, and there's no guarantee we'll pick the one with bnot on the right, since the two alternatives have equal cost. I assume it's working now because elaboration happens to be picking the last-added option in the e-class in case of ties, or something like that.

I think the backends need to match both patterns instead. Which is annoying, since the patterns overlap; we have to give them different priorities.

I also think we need to work on helping ISLE understand commutative operators. It could generate every unique version of a rule with operands swapped, given a commutative flag on terms or something. We'd have to put some thought into how that interacts with overlap checking though.

Wasmtime GitHub notifications bot (Feb 06 2023 at 17:44):

alexcrichton commented on issue #5709:

Ok! I've removed the egraph bits for that and added more lowering rules

Wasmtime GitHub notifications bot (Feb 10 2023 at 15:23):

uweigand commented on issue #5709:

• I think the bxor_not instruction was buggy on s390x int that it was calculating (bnot (bxor x y)) instead of (bxor x (bnot y)).

Isn't this the same, given that bnot is XOR with -1, and XOR is associative?

Wasmtime GitHub notifications bot (Feb 10 2023 at 17:29):

alexcrichton commented on issue #5709:

Ah yes indeed!

Last updated: Dec 23 2024 at 12:05 UTC