binaryen icon indicating copy to clipboard operation
binaryen copied to clipboard

Use getMaxBits in comparisons

Open kripken opened this issue 1 year ago • 4 comments

E.g.

(i32.lt_u
 (i32.ne
  (local.get $0)
  (i32.const 0)
 )
 (i32.const 128)
)
 =->
(i32.const 1)

i32.ne returns 0 or 1, so it is max 1 bit, and that is always less than 128.

Found by the superoptimizer https://github.com/WebAssembly/binaryen/pull/4994 (for comparison to other findings: rule #20, benefit 13760).

kripken avatar Sep 02 '22 19:09 kripken

generalize to:

u32(x)  < C      ->      1,    iff  maxBits(x) < maxBits(C)
u32(x) <= C      ->      1,    iff  maxBits(x) < maxBits(C)

MaxGraey avatar Sep 03 '22 05:09 MaxGraey

Also

x == C   =>   0   if maxBits(x) < bits(C)
x != C   =>   1   if maxBits(x) < bits(C)

(to be equal, the number of bits must be equal, so if that differs, the values must differ).

kripken avatar Sep 08 '22 22:09 kripken

Special case:

x == -1   =>   0   if maxBits(x) != bits(-1)

MaxGraey avatar Sep 09 '22 15:09 MaxGraey

This should be complete except for the last part in https://github.com/WebAssembly/binaryen/issues/5010#issuecomment-1242153149 That pattern is basically where the right side is -1 (or more generally a mask of lower bits), so we know more than just the min/max bits.

kripken avatar Sep 13 '22 17:09 kripken