Binaryen: optimizer not using select in a situation if-return

[MaxGraey]

Successful example case:

export function foo(a: bool): i32 {
  if (a) return 1;
  else return 2;
}

optimized output:

(func $foo (export "foo") (type $t0) (param $p0 i32) (result i32)
  i32.const 1
  i32.const 2
  get_local $p0
  select
)

Unsuccessful example case:

export function foo(a: bool): i32 {
  if (a) return 1;
  return 2;
}

optimized output:

(func $foo (export "foo") (type $t0) (param $p0 i32) (result i32)
  get_local $p0
  if $I0
    i32.const 1
    return
  end
  i32.const 2
)

[kripken]

Yeah, it might make sense to special-case this. But we do handle it with --flatten --rereloop -Os, which results in

 (func $0 (; 0 ;) (; has Stack IR ;) (type $0) (param $0 i32) (result i32)
  (select
   (i32.const 1)
   (i32.const 2)
   (local.get $0)
  )
 )

[MaxGraey]

Hmm, this also happened with one level up for shrinkage. Like -O3s. Is it make sense using this also for -O3? I guess select in this case also faster than if-return

[binji]

I guess select in this case also faster than if-return

I tested this out in v8 using the baseline compiler (liftoff) and the optimizing compiler (turbofan) with the following source:

(func (export "select") (param i32) (result i32)
  i32.const 1
  i32.const 2
  local.get 0
  select
)

(func (export "if") (param i32) (result i32)
  local.get 0
  if
    i32.const 1
    return
  end
  i32.const 2
)

(func (export "ifelse") (param i32) (result i32)
  local.get 0
  if (result i32)
    i32.const 1
  else
    i32.const 2
  end
)

(func (export "brif") (param i32) (result i32)
  i32.const 1
  local.get 0
  br_if 0
  drop
  i32.const 2
)

Liftoff generates the following (with the function prologue and epilogue removed for easier reading)

select:
0xa42f72d3f25    25  b902000000     movl rcx,0x2
0xa42f72d3f2a    2a  ba01000000     movl rdx,0x1
0xa42f72d3f2f    2f  85c0           testl rax,rax
0xa42f72d3f31    31  0f8405000000   jz 0xa42f72d3f3c  <+0x3c>
0xa42f72d3f37    37  e902000000     jmp 0xa42f72d3f3e  <+0x3e>
0xa42f72d3f3c    3c  8bd1           movl rdx,rcx
0xa42f72d3f3e    3e  8bc2           movl rax,rdx

if:
0xa42f72d3e65    25  85c0           testl rax,rax
0xa42f72d3e67    27  0f8431000000   jz 0xa42f72d3e9e  <+0x5e>
0xa42f72d3e6d    2d  b801000000     movl rax,0x1
...duplicated epilogue...
0xa42f72d3e9d    5d  c3             retl
0xa42f72d3e9e    5e  b802000000     movl rax,0x2

ifelse:
0xa42f72d3dc5    25  85c0           testl rax,rax
0xa42f72d3dc7    27  0f840a000000   jz 0xa42f72d3dd7  <+0x37>
0xa42f72d3dcd    2d  b901000000     movl rcx,0x1
0xa42f72d3dd2    32  e905000000     jmp 0xa42f72d3ddc  <+0x3c>
0xa42f72d3dd7    37  b902000000     movl rcx,0x2
0xa42f72d3ddc    3c  8bc1           movl rax,rcx

brif:
0xa42f72d3d05    25  85c0           testl rax,rax
0xa42f72d3d07    27  0f8431000000   jz 0xa42f72d3d3e  <+0x5e>
0xa42f72d3d0d    2d  b801000000     movl rax,0x1
...duplicated epilogue...
0xa42f72d3d3d    5d  c3             retl
0xa42f72d3d3e    5e  b802000000     movl rax,0x2

Turbofan generates the following:

select:
0xa42f72d4067     7  83f800         cmpl rax,0x0
0xa42f72d406a     a  0f850a000000   jnz 0xa42f72d407a  <+0x1a>
0xa42f72d4070    10  bb02000000     movl rbx,0x2
0xa42f72d4075    15  e905000000     jmp 0xa42f72d407f  <+0x1f>
0xa42f72d407a    1a  bb01000000     movl rbx,0x1

if:
0xa42f72d4027     7  83f800         cmpl rax,0x0
0xa42f72d402a     a  0f850a000000   jnz 0xa42f72d403a  <+0x1a>
0xa42f72d4030    10  b802000000     movl rax,0x2
...duplicated epilogue...
0xa42f72d4039    19  c3             retl
0xa42f72d403a    1a  b801000000     movl rax,0x1
0xa42f72d403f    1f  ebf4           jmp 0xa42f72d4035  <+0x15>

ifelse:
0xa42f72d3fe7     7  83f800         cmpl rax,0x0
0xa42f72d3fea     a  0f850a000000   jnz 0xa42f72d3ffa  <+0x1a>
0xa42f72d3ff0    10  bb02000000     movl rbx,0x2
0xa42f72d3ff5    15  e905000000     jmp 0xa42f72d3fff  <+0x1f>
0xa42f72d3ffa    1a  bb01000000     movl rbx,0x1

brif:
0xa42f72d3fa7     7  83f800         cmpl rax,0x0
0xa42f72d3faa     a  0f850a000000   jnz 0xa42f72d3fba  <+0x1a>
0xa42f72d3fb0    10  b802000000     movl rax,0x2
...duplicated epilogue...
0xa42f72d3fb9    19  c3             retl
0xa42f72d3fba    1a  b801000000     movl rax,0x1
0xa42f72d3fbf    1f  ebf4           jmp 0xa42f72d3fb5  <+0x15>

In both cases the early return generates more code, but the generated code is nearly identical and likely to have no effect on performance.

[MaxGraey]

@binji thanks for info!
Firefox more sensitive in this case:

select:

wasm-function[0]:
  sub rsp, 8                            ; 0x000000 48 83 ec 08
  mov eax, 1                            ; 0x000004 b8 01 00 00 00
  mov ecx, 2                            ; 0x000009 b9 02 00 00 00
  test edi, edi                         ; 0x00000e 85 ff
  cmove eax, ecx                        ; 0x000010 0f 44 c1
  nop                                   ; 0x000013 66 90
  add rsp, 8                            ; 0x000015 48 83 c4 08
  ret                                   ; 0x000019 c3

if-else:

wasm-function[1]:
 0x000000:                              ; 0x000000 from: [0x000006, 0x000011]
  sub rsp, 8                            ; 0x000000 48 83 ec 08
  test edi, edi                         ; 0x000004 85 ff
  je 0x16                               ; 0x000006 0f 84 0a 00 00 00
 0x00000c:                              
  mov eax, 1                            ; 0x00000c b8 01 00 00 00
  jmp 0x1b                              ; 0x000011 e9 05 00 00 00
 0x000016:                              
  mov eax, 2                            ; 0x000016 b8 02 00 00 00
  nop                                   ; 0x00001b 66 90
  add rsp, 8                            ; 0x00001d 48 83 c4 08
  ret                                   ; 0x000021 c3

[kripken]

Interesting data about the speed!

Given that data, and that the select version is smaller in the binary, I think it makes sense we emit it.

Is it make sense using this also for -O3?

Yes, it works in both -O3 and -Os, try --flatten --rereloop -O3.

[MaxGraey]

Currently AS using binaryen's -O4 which already include flatten and local-cse but without --rereloop which unnecessary for AS because it use binaryen as code/loop generator. But this not helps

[MaxGraey]

@binji Regards turbofan and liftoff always legalize select via branches. It seems this will be change sooner or later:
https://bugs.chromium.org/p/v8/issues/detail?id=10740&q=component%3AWebAssembly&can=2&colspec=ID%20Type%20Status%20Priority%20Owner%20Summary%20HW%20OS%20Component%20Stars%20Modified