optimise LSBit mask (followed by branch) to use `ctz`

[ggreif]

I have code snippets like

i32.const 1
i32.and
i32.eqz
br_if 1 (;@1;)

which could be optimised to

i32.ctz
br_if 1 (;@1;)

Similar analogous transformations:

• i32.const 1; i32.and; i32.eqz; if to i32.ctz; if
• i32.const 1; i32.and; if to i32.ctz; if (with legs swapped)
• i32.const 2_147_483_648; i32.and; if to i32.clz; if (with legs swapped)
• i32.const 31; i32.shr_u; if to i32.clz; if (with legs swapped)
• possibly 64-bit variants (but here probably instructions for truncation need to be added)
• what about signedness testing? (cmp against 0 --> clz)

[ggreif]

PR #8562 implements the two main patterns from the description:

• i32.const 1; i32.and; if T E → i32.ctz; if E T (via visitIf)
• i32.const 1; i32.and; i32.eqz; br_if → i32.ctz; br_if (via optimizeBoolean, also covers if and select)

The analogous MSB patterns (i32.const 2_147_483_648; i32.and; if and i32.const 31; i32.shr_u; if) and the 64-bit variants remain for future work.

[MaxGraey]

That's really strange. What runtime are you using? Since this applies to Motoko, it must be wasmtime or wasmer. I think better to open a pull request there asking why the first pattern is optimized less efficiently than bool(i32.ctz(x)) by the runtime.

There are many runtimes that cannot optimize i32.ctz in bool context, which will lead to performance degradation due to counting bits itself is significantly more expensive than a couple of bitwise operations + set flags. It’s also worth noting that wasm does not allow UBs, so an additional check for non-zero values is performed.

[MaxGraey]

For example wasmtime v22 (very outdated due to latest v43) generate tzcnt instruction which is definitely suboptimal:
https://godbolt.org/z/jGhn74b5x

[ggreif]

Good morning @MaxGraey! Motoko targets the IC, and its native language is Wasm. So all cycle cost accounting is based on the number and difficulty of those instructions. Clearly const 1, and is a two-instruction (3 bytes, 0x41 0x01 0x71) sequence, while this PR optimises it to one (0x68). So it is a win. But indeed The machine layer uses wasmtime, and there is some concern how that executes. But being a peephole-optimiser itself, it can choose to expand i32.ctz; if to whatever it thinks is the most efficient for the target architecture. If it fails to do that, I consider that a bug in wasmtime and not a shortcoming of this PR.