Optimize combined integer compare

[lexaknyazev]

Generic case

This function

export function foo(x: i32, a: i32, b: i32): boolean {
  return (x < a) || (x > b);
}

currently yields

  i32.const 1
  local.get $0
  local.get $2
  i32.gt_s
  local.get $0
  local.get $1
  i32.lt_s
  select

A better option with fewer instructions and a shorter stack would probably be:

  local.get $0
  local.get $2
  i32.gt_s
  local.get $0
  local.get $1
  i32.lt_s
  i32.or

Const bounds case

When bounds are const values, the compiler may exploit the integer wrapping to reduce the number of compare instructions.

Outer range check

export function bar(x: i32): boolean {
  return (x < 10) || (x > 100);
}

could be

  local.get $0
  i32.const 10
  i32.sub
  i32.const 90
  i32.gt_u

Inner range check

export function baz(x: i32): boolean {
  return (x > 10) && (x < 100);
}

could be

  local.get $0
  i32.const 11
  i32.sub
  i32.const 89
  i32.lt_u

[MaxGraey]

A better option with fewer instructions and a shorter stack would probably be:

  local.get $0
  local.get $2
  i32.gt_s
  local.get $0
  local.get $1
  i32.lt_s
  i32.or

This already in main branch and will be available in next AS version

[MaxGraey]

Regarding more optimal codegen for:

export function bar(x: i32): boolean {
  return (x < 10) || (x > 100);
}

This is also known and will be implemented in the future

[lexaknyazev]

Another related case:

export function foo(x: i32): boolean {
  return x - 10 > 100;
}

currently yields

  local.get $0
  i32.const 10
  i32.sub
  i32.const 100
  i32.gt_s

When x is signed, this could be reduced to

  local.get $0
  i32.const 110
  i32.gt_s

[MaxGraey]

Another related case:

Did you check with C++?
Such transform is danger. C++ do this, but AS and Rust for example avoid it.
We can't do this simplification due to overflow when x equal -0x80000000 for example:
-0x80000000 - 10 > 100 -> true
while:
-0x80000000 > 110 -> false

https://godbolt.org/z/Ke3Y9cajs

Same for similar unsigned comparisons. But instead [-0x7ffffff7 -0x80000000] danger overflow range will be [0, 9] for x;

In C/C++ integer overflow is UB by spec so they could do such danger things.

[lexaknyazev]

You're right, the WebAssembly semantics are more strict than C++, so my last example is incorrect. The initial suggestions are not affected, though.

[MaxGraey]

Usually such optimizations do not give significant acceleration. At the same time, they introduce undefined behaviors that WebAssembly tries to avoid. In our turn, we do the same. I don't see much sense in introducing some optional flag for such things either. I'm also not a fan of very loose fastMath mode in C/C++ (the one that ignores NaN at all). That mode is very dangerous and in most cases just breaks the application (or rather execution flow graph). Ignoring integer overflows also do this to some extent. But compared to fastMath, it doesn't even give a significant speedup and doesn't open up new possibilities for subsequent optimizations.

C++ do really dangerous things sometimes: https://twitter.com/jckarter/status/1428093469755527168?s=20

[MaxGraey]

However if we could approve that's x is always positive for example (it's possible in some cases) we could apply such simplification. For example:

export function foo(x: i32): bool {
  return (x & 0x7FFFFFFF) - 10 > 100
  // or (x >>> 1) - 10 > 100
}

could be transformed to:

local.get   $x
i32.const   0x7FFFFFFF
i32.and 
i32.const   110
i32.gt_u

[MaxGraey]

A better option with fewer instructions and a shorter stack would probably be:

  local.get $0
  local.get $2
  i32.gt_s
  local.get $0
  local.get $1
  i32.lt_s
  i32.or

This already in main branch and will be available in next AS version

@lexaknyazev should be already in v0.19.19. As well as extra early inline pass from here #2115