More performant codegen for logical expressions

[MaxGraey]

It seems logical expressions much better compile use blocks (1) like:

export function f3(x: number): number {
  do {
    if (x === 1) {
      break;
    }
    if (x === 2) {
      break;
    }
    return f3(x - 1) + f3(x - 2);
  } while (false);
  return 1;
}

instead (2):

export function f1(x: number): number {
  if (x === 1 || x === 2) {
    return 1;
  }
  return f1(x - 1) + f1(x - 2);
}

Chrome 80:

fib ver	time	notes
f64.f1	150ms	default with f64 ver (2)
f64.f2	139ms
f64.f3	124ms	wrapped by block f64 ver (1)
f64.f4	134ms
i32.i1	121ms	default with i32 ver (2)
i32.i3	112ms	wrapped by block i32 ver (1)
f64.js	190ms	javascript

Firefox 73

fib ver	time	notes
f64.f1	133ms	default with f64 ver (2)
f64.f2	143ms
f64.f3	127ms	wrapped by block f64 ver (1)
f64.f4	128ms
i32.i1	110ms	default with i32 ver (2)
i32.i3	101ms	wrapped by block i32 ver (1)
f64.js	117ms	javascript

Safari 13.0.4

fib ver	time	notes
f64.f1	130ms	default with f64 ver (2)
f64.f2	154ms
f64.f3	115ms	wrapped by block f64 ver (1)
f64.f4	117ms
i32.i1	97ms	default with i32 ver (2)
i32.i3	87ms	wrapped by block i32 ver (1)
f64.js	811ms	javascript

Codegen for (1):

(func $f3 (export "f3") (type $t0) (param $p0 f64) (result f64)
    block $B0
      get_local $p0
      f64.const 0x1p+0 (;=1;)
      f64.eq
      br_if $B0
      get_local $p0
      f64.const 0x1p+1 (;=2;)
      f64.eq
      br_if $B0
      get_local $p0
      f64.const 0x1p+0 (;=1;)
      f64.sub
      call $f3
      get_local $p0
      f64.const 0x1p+1 (;=2;)
      f64.sub
      call $f3
      f64.add
      return
    end
    f64.const 0x1p+0 (;=1;))

Codegen for (2):

(func $f1 (export "f1") (type $t0) (param $p0 f64) (result f64)
    i32.const 1
    get_local $p0
    f64.const 0x1p+1 (;=2;)
    f64.eq
    get_local $p0
    f64.const 0x1p+0 (;=1;)
    f64.eq
    select
    if $I0
      f64.const 0x1p+0 (;=1;)
      return
    end
    get_local $p0
    f64.const 0x1p+0 (;=1;)
    f64.sub
    call $f1
    get_local $p0
    f64.const 0x1p+1 (;=2;)
    f64.sub
    call $f1
    f64.add)

PS Other versions like:

export function f4(x: number): number {
  if (x == 1) {
    return 1;
  }
  if (x == 2) {
    return 1;
  }
  return f1(x - 1) + f1(x - 2);
}

and

export function f4(x: number): number {
  do {
    if (x == 1 || x == 2) { // or i32(x == 1) || i32(x == 2)
      break;
    }
    return f1(x - 1) + f1(x - 2);
  } while (false);
  return 1;
}

Also less efficient and approximately equal to f64.f1 or f64.f4.

[jtenner]

Do you guys need some help identifying places where we should change the std lib?

[jtenner]

also, I'm curious if this is faster?

if (i32(x == 1) | i32(x == 2)) break;

[MaxGraey]

also, I'm curious if this is faster?

Nope, not faster. Sometimes even slower, but it highly depends on logical expressions. And btw will need calc side effects and try preoptimize some expressions before wrap to block. It seems LLVM also prefer block-scoped variant.

[dcodeIO]

Current implementation tries to do both the bool (if (a && b)) and the value case (var c = a && b) as one, with the latter complicating matters a bit. Somewhat related to https://github.com/AssemblyScript/assemblyscript/issues/1136, in that the current value rules in logical expressions are weird anyway and need a rework.

[dcodeIO]

@MaxGraey Do you think that this can/should be solved on the Binaryen side? If not, there have been some changes to codegen here lately when exclusively interested in boolean values. Do you know if these did help?

[MaxGraey]

I don't know yet. Plz leave this open

[dcodeIO]

Sure, no problem :)