Stream: git-wasmtime

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

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

alexcrichton edited PR #5709 from wasm-bandnot to main:

I was curious to see the effect of #5701 on the compilation of spidermonkey.wasm and much to my dismay I saw that the andn instruction was never generated. It turns out, however, that WebAssembly does not have a "bnot" equivalent instruction for i32 or i64, nor a "band_not" instruction. To trigger the optimization added there I added a few egraph simplification rules to pattern match xor against -1 to bnot and then take a sequence of ands/nots and turn that into a single band_not instruction.

I'm not so certain that this is the best way to do this, however. There's a lot of optimization rules around just bnot and just band, but most of them don't mention the fused form of band_not (or other forms like bor_not). I tried adding a simple "band_not is equivalent to (band (bnot))" rule but it ended up not generating the band_not instruction. It seems like the best way forward might be to remove the fused instructions from clif entirely, instead pattern matching in backends for those that support fused instructions. If that's the way to go I'm happy to remove the band_not fusing in algebraic.isle and can push on that later.

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

alexcrichton edited PR #5709 from wasm-bandnot to main:

I was curious to see the effect of #5701 on the compilation of spidermonkey.wasm and much to my dismay I saw that the andn instruction was never generated. It turns out, however, that WebAssembly does not have a "bnot" equivalent instruction for i32 or i64, nor a "band_not" instruction. To trigger the optimization added there I added a few egraph simplification rules to pattern match xor against -1 to bnot.

I then additionally noticed that the lowering added in #5701 was for the clif band_not instruction, but this was never actually used by wasm. Additionally egraphs didn't fuse band-of-bnot into one instruction, so the lowering still never fired. To address this issue I've added legalizations now from band_not into band-of-bnot in addition to bor_not and bxor_not. This involved updating all backends with fused lowerings to do more pattern-matching on the top-level operation instead of matching on b*_not since those now never reach the backends.

After all this I've added a *.wat test to assert that bnot shows up and at least for x86_64 the specialized lowering of band_not is triggered.

Along the way I noticed a few things:

• I cleaned up some riscv64 bits where band_not unconditionally used gen_andn but internally gen_andn tested for codegen features. Instead the lowering of (band ... (bnot ..)) now explicitly tests for codegen features and falls back to normal rules if the feature for andn isn't available.
• 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)). The tests got updated as a result. I'm not so certain that the remaining lowerings are correct since the instructions are called NotXor32, for example, but I haven't tested.

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

alexcrichton updated PR #5709 from wasm-bandnot to main.

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

alexcrichton updated PR #5709 from wasm-bandnot to main.

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

alexcrichton updated PR #5709 from wasm-bandnot to main.

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

alexcrichton updated PR #5709 from wasm-bandnot to main.

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

alexcrichton updated PR #5709 from wasm-bandnot to main.

Wasmtime GitHub notifications bot (Feb 06 2023 at 18:24):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Feb 06 2023 at 18:24):

jameysharp submitted PR review.

Wasmtime GitHub notifications bot (Feb 06 2023 at 18:24):

jameysharp created PR review comment:

Tiny whitespace fix:

(rule 9 (lower (has_type ty @ (multi_lane _bits _lane) (band (bnot y) x)))

Wasmtime GitHub notifications bot (Feb 06 2023 at 18:57):

alexcrichton updated PR #5709 from wasm-bandnot to main.

Wasmtime GitHub notifications bot (Feb 06 2023 at 19:53):

alexcrichton merged PR #5709.

Last updated: Dec 06 2025 at 06:05 UTC