[WebAssembly] Emit br_table for most switch instructions

[aheejin]

Summary

Always convert switches to br_tables unless there is only one case,
which is equivalent to a simple branch. This reduces code size for wasm,
and we defer possible jump table optimizations to the VM.
Addresses PR41502.

[aheejin]

test/CodeGen/WebAssembly/cfg-stackify.ll

649

@sunfish There are some CHECK-NOTs that I don't know how to preserve here, given that the structure has completely changed. Any ideas? Or do you think it's OK not preserving these?

[sunfish]

The theory here is that br_table represents the performance characteristics of a jump table, while br_if represents the performance characteristics of a branch. In hardware, a small switch with 3 cases is often more efficient with a couple of conditional branches than a jump table.

[aheejin]

• v8 -> VM

[kripken]

I'm in favor of this. There are a bunch of tradeoffs that VMs can make, and this lets them make their own choices, by emitting the higher-level construct, which is also smaller in size in the wasm.

[dschuff]

llvm/trunk/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

277 ↗

(On Diff #196330)

Might be worth putting a TODO in here or somewhere to investigate using if/else instead once we have support for that?

[aheejin]

llvm/trunk/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

277 ↗

(On Diff #196330)

In PR41502, @kripken said using if/else generates bigger code too. If we are doing this for code size, do we need that TODO?

lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

if (Subtarget->hasBulkMemory()) {
     // Use memory.copy and friends over multiple loads and stores
     MaxStoresPerMemcpy = 1;
     MaxStoresPerMemcpyOptSize = 1;
     MaxStoresPerMemmove = 1;
     MaxStoresPerMemmoveOptSize = 1;
     MaxStoresPerMemset = 1;
     MaxStoresPerMemsetOptSize = 1;
   }
+
+  // Always convert switches to br_tables unless there is only one case, which
+  // is equivalent to a simple branch. This reduces code size for wasm, and we
+  // defer possible jump table optimizations to v8.
+  setMinimumJumpTableEntries(2);
 }
 
 TargetLowering::AtomicExpansionKind
 WebAssemblyTargetLowering::shouldExpandAtomicRMWInIR(AtomicRMWInst *AI) const {
   // We have wasm instructions for these
   switch (AI->getOperation()) {
   case AtomicRMWInst::Add:
   case AtomicRMWInst::Sub:

test/CodeGen/WebAssembly/cfg-stackify.ll

 }
 
 ; Test switch lowering and block placement.
 
 ; CHECK-LABEL: test4:
 ; CHECK-NEXT: .functype test4 (i32) -> (){{$}}
 ; CHECK:      block   {{$}}
 ; CHECK-NEXT: block   {{$}}
-; CHECK:      br_if       0, $pop{{[0-9]+}}{{$}}
-; CHECK:      br_if       1, $pop{{[0-9]+}}{{$}}
-; CHECK:      br          1{{$}}
-; CHECK-NEXT: .LBB{{[0-9]+}}_3:
-; CHECK-NEXT: end_block{{$}}
-; CHECK-NEXT: block   {{$}}
-; CHECK:      br_if 0, $pop{{[0-9]+}}{{$}}
-; CHECK:      br_if 1, $pop{{[0-9]+}}{{$}}
-; CHECK-NEXT: .LBB{{[0-9]+}}_5:
+; CHECK:      br_if     0, $pop{{[0-9]+}}{{$}}
+; CHECK:      br        1{{$}}
+; CHECK-NEXT: .LBB{{[0-9]+}}_2:
 ; CHECK-NEXT: end_block{{$}}
-; CHECK-NEXT: return{{$}}
-; CHECK-NEXT: .LBB{{[0-9]+}}_6:
+; CHECK-NEXT: br_table   $0, 0, 0, 0, 0, 0, 0{{$}}
+; CHECK-NEXT: .LBB{{[0-9]+}}_3:
 ; CHECK-NEXT: end_block{{$}}
 ; CHECK-NEXT: return{{$}}
 define void @test4(i32 %t) {
 entry:
   switch i32 %t, label %default [
     i32 0, label %bb2
     i32 2, label %bb2
     i32 4, label %bb1

 }
 
 ; Test an interesting case involving nested loops sharing a loop bottom,
 ; and loop exits to a block with unreachable.
 
 ; CHECK-LABEL: test10:
 ; CHECK:       .LBB{{[0-9]+}}_1:
 ; CHECK-NEXT:  loop    {{$}}
-; CHECK-NOT:   block
-; CHECK:       br_if    0, {{[^,]+}}{{$}}
+; CHECK:       br_if     0, {{[^,]+}}{{$}}
 ; CHECK:       .LBB{{[0-9]+}}_3:
 ; CHECK-NEXT:  block   {{$}}
 ; CHECK-NEXT:  loop    {{$}}
-; CHECK-NOT:   block
 ; CHECK:       .LBB{{[0-9]+}}_4:
 ; CHECK-NEXT:  loop    {{$}}
-; CHECK-NOT:   block
-; CHECK:       br_if    0, {{[^,]+}}{{$}}
+; CHECK:       br_if     0, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  end_loop{{$}}
-; CHECK:       br_if    1, {{[^,]+}}{{$}}
-; CHECK-NOT:   block
-; CHECK:       br_if    0, {{[^,]+}}{{$}}
+; CHECK-NEXT:  block   {{$}}
+; CHECK:       br_if     0, {{[^,]+}}{{$}}
+; CHECK:       br        3{{$}}
+; CHECK-NEXT:  .LBB{{[0-9]+}}_7:
+; CHECK-NEXT:  end_block{{$}}
+; CHECK:       block   {{$}}
+; CHECK-NEXT:  br_table   $0, 0, 3, 1, 2, 0
+; CHECK-NEXT:  .LBB{{[0-9]+}}_8:
+; CHECK-NEXT:  end_block{{$}}
 ; CHECK-NEXT:  end_loop{{$}}
-; CHECK-NOT:   block
-; CHECK:       br_if    1, {{[^,]+}}{{$}}
 ; CHECK-NEXT:  return{{$}}
 ; CHECK-NEXT:  .LBB{{[0-9]+}}_9:
 ; CHECK-NEXT:  end_block{{$}}
-; CHECK-NOT:   block
-; CHECK:       br       0{{$}}
+; CHECK:       br        0{{$}}
 ; CHECK-NEXT:  .LBB{{[0-9]+}}_10:
+; CHECK-NEXT:  end_loop{{$}}
 define void @test10() {
 bb0:
   br label %bb1
 
 bb1:
   %tmp = phi i32 [ 2, %bb0 ], [ 3, %bb3 ]
   %tmp3 = phi i32 [ undef, %bb0 ], [ %tmp11, %bb3 ]
   %tmp4 = icmp eq i32 %tmp3, 0
bb7:
   ret void
 bb8:
   store volatile i32 8, i32* null
   ret void
 }
 
 ; CHECK-LABEL: test12:
 ; CHECK:       .LBB{{[0-9]+}}_1:
-; CHECK-NEXT:  block   {{$}}
 ; CHECK-NEXT:  loop    {{$}}
-; CHECK-NOT:   block
-; CHECK:       block   {{$}}
+; CHECK-NEXT:  block   {{$}}
+; CHECK-NEXT:  block   {{$}}
 ; CHECK-NEXT:  block   {{$}}
-; CHECK:       br_if       0, {{[^,]+}}{{$}}
-; CHECK-NOT:   block
-; CHECK:       br_if       1, {{[^,]+}}{{$}}
-; CHECK-NOT:   block
-; CHECK:       br_if       1, {{[^,]+}}{{$}}
-; CHECK-NEXT:  br          3{{$}}
+; CHECK:       br_if     0, {{[^,]+}}{{$}}
+; CHECK:       br_if     2, {{[^,]+}}{{$}}
+; CHECK:       br_if     1, {{[^,]+}}{{$}}
+; CHECK-NEXT:  br        2{{$}}
 ; CHECK-NEXT:  .LBB{{[0-9]+}}_4:
 ; CHECK-NEXT:  end_block{{$}}
-; CHECK-NOT:   block
-; CHECK:       br_if       0, {{[^,]+}}{{$}}
-; CHECK-NOT:   block
-; CHECK:       br_if       2, {{[^,]+}}{{$}}
+; CHECK-NEXT:  br_table   $2, 1, 0, 0, 0, 1, 1{{$}}
+; CHECK-NEXT:  .LBB{{[0-9]+}}_5:
+; CHECK-NEXT:  end_block{{$}}
+; CHECK-NEXT:  return{{$}}
 ; CHECK-NEXT:  .LBB{{[0-9]+}}_6:
 ; CHECK-NEXT:  end_block{{$}}
-; CHECK-NOT:   block
-; CHECK:       br          0{{$}}
+; CHECK:       br        0{{$}}
 ; CHECK-NEXT:  .LBB{{[0-9]+}}_7:
 ; CHECK-NEXT:  end_loop{{$}}
-; CHECK-NEXT:  end_block{{$}}
-; CHECK-NEXT:  return{{$}}
 define void @test12(i8* %arg) {
 bb:
   br label %bb1
 
 bb1:
   %tmp = phi i32 [ 0, %bb ], [ %tmp5, %bb4 ]
   %tmp2 = getelementptr i8, i8* %arg, i32 %tmp
   %tmp3 = load i8, i8* %tmp2