Stream: git-wasmtime

Topic: wasmtime / PR #5709 Add egraph rules to generate `bnot` a...

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

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

I was curious to see the effect of #5703 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 01:07):

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 01:48):

jameysharp submitted PR review.

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

jameysharp submitted PR review.

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

jameysharp created PR review comment:

These rules are unlikely to match for any type smaller than I64 because we've been... somewhat... consistent about zeroing the unused bits in iconst instructions. If we fix #3059 then these rules would never match for anything but I64.

With the recently-merged #5706, you can write these this way instead:

(rule (simplify (bxor ty (iconst ty k) x))
 (if-let -1 (i64_sextend_imm64 ty k))
 (subsume (bnot ty x)))
(rule (simplify (bxor ty x (iconst ty k)))
 (if-let -1 (i64_sextend_imm64 ty k))
 (subsume (bnot ty x)))

The other thing to note though is I think these rules shouldn't use subsume. If both operands to bxor are constants, then we'd prefer to apply the constant folding rules instead of emitting a bnot instruction. If multiple rules use subsume, we don't specify which rule will win; it currently depends on details of how ISLE does codegen that are difficult to predict.

But I don't know yet what advice to give about when to use subsume. Struggling with that question led me to file #5704 today.

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

jameysharp created PR review comment:

Similarly, I don't think these rules should use subsume either.

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

jameysharp submitted PR review.

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

jameysharp created PR review comment:

To be clear, these rules do match for smaller types in the filetests in this PR because the CLIF text parser is one of the places where we have not been consistent about zeroing the high bits.

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

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

Last updated: Nov 22 2024 at 16:03 UTC