[WebAssembly] Make BR_TABLE non-duplicable

[tlively]

Summary

After their range checks were removed in 7f50c15be5c0, br_tables
started being duplicated into their predecessors by tail
folding. Unfortunately, when the br_tables were in loops this
transformation introduced bad irreducible control flow which was later
expanded into even more br_tables. This commit abuses the
isNotDuplicable property to prevent this irreducible control flow
from being introduced. This change saves a few dozen bytes of code
size and has a negligible affect on performance for most of the large
Emscripten benchmarks, but can improve performance significantly on
microbenchmarks of switches in loops.

[arsenm]

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

61

Does isConvergent accomplish the same thing here?

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

61

It would, but to be honest I'm still not sure what it means for an instruction to be convergent or not. I know convergent instructions can't get any new control flow dependencies, but I don't have a good sense of why that might be an important property and what kind of instructions would need it. Do you have a good intuitive explanation for that? If it makes more sense, I would be happy to use isConvergent rather than isNotDuplicable. I looked at the places they are used earlier and either seems fine for this instruction.

[aheejin]

LGTM either with isNotDuplicable or isConvergent, as long as it works. I'm not familiar with what isConvergent is used for either, so..

Just to confirm, this is separate from why final.c in https://bugs.chromium.org/p/v8/issues/detail?id=10606 is slow, right?

llvm/test/CodeGen/WebAssembly/indirectbr.ll

30

Were we duplicating br_table even for this simple example? Is that why the test result changed?

[tlively]

In D81628#2087315, @aheejin wrote:

LGTM either with isNotDuplicable or isConvergent, as long as it works. I'm not familiar with what isConvergent is used for either, so..

Just to confirm, this is separate from why final.c in https://bugs.chromium.org/p/v8/issues/detail?id=10606 is slow, right?

Right, if I'm reading that bug correctly, there is also a register allocation issue in V8 making switches in loops slow.

llvm/test/CodeGen/WebAssembly/indirectbr.ll

30

That's right 👍

[dschuff]

(discussed with @tlively offline). The root issue is that the br_table gets duplicated outside the wasm block that encloses the branch targets. That's what causes the irreducible control flow in this case. Because the target-independent passes that do the duplication can't reason about those wasm blocks (since we haven't done the analysis that places them until later in the pass pipeline) it probably just makes sense to use noduplicate, which is a stronger limitation than convergent.

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

 // Used by br_table only.
 def BrListAsmOperand : AsmOperandClass { let Name = "BrList"; }
 let OperandNamespace = "WebAssembly", OperandType = "OPERAND_BRLIST" in
 def brlist : Operand<i32> {
   let ParserMatchClass = BrListAsmOperand;
   let PrintMethod = "printBrList";
 }
 
-// TODO: SelectionDAG's lowering insists on using a pointer as the index for
-// jump tables, so in practice we don't ever use BR_TABLE_I64 in wasm32 mode
-// currently.
-let isTerminator = 1, hasCtrlDep = 1, isBarrier = 1 in {
+// Duplicating a BR_TABLE is almost never a good idea. In particular, it can
+// lead to some nasty irreducibility due to tail merging when the br_table is in
+// a loop.
+let isTerminator = 1, hasCtrlDep = 1, isBarrier = 1, isNotDuplicable = 1 in {
+
 defm BR_TABLE_I32 : I<(outs), (ins I32:$index, variable_ops),
                       (outs), (ins brlist:$brl),
                       [(WebAssemblybr_table I32:$index)],
                       "br_table \t$index", "br_table \t$brl",
                       0x0e>;
+// TODO: SelectionDAG's lowering insists on using a pointer as the index for
+// jump tables, so in practice we don't ever use BR_TABLE_I64 in wasm32 mode
+// currently.
 defm BR_TABLE_I64 : I<(outs), (ins I64:$index, variable_ops),
                       (outs), (ins brlist:$brl),
                       [(WebAssemblybr_table I64:$index)],
                       "br_table \t$index", "br_table \t$brl",
                       0x0e>;
-} // isTerminator = 1, hasCtrlDep = 1, isBarrier = 1
+} // isTerminator = 1, hasCtrlDep = 1, isBarrier = 1, isNotDuplicable = 1
 
 // This is technically a control-flow instruction, since all it affects is the
 // IP.
 defm NOP : NRI<(outs), (ins), [], "nop", 0x01>;
 
 // Placemarkers to indicate the start or end of a block or loop scope.
 // These use/clobber VALUE_STACK to prevent them from being moved into the
 // middle of an expression tree.

llvm/test/CodeGen/WebAssembly/indirectbr.ll

 ; RUN: llc < %s -asm-verbose=false -disable-wasm-fallthrough-return-opt -wasm-disable-explicit-locals -wasm-keep-registers | FileCheck %s
 
 ; This tests that indirectbr instructions are lowered to switches. Currently we
 ; just re-use the IndirectBrExpand Pass; it has its own IR-level test.
 ; So this test just ensures that the pass gets run and we can lower indirectbr
 
 target triple = "wasm32"
 
 @test1.targets = constant [4 x i8*] [i8* blockaddress(@test1, %bb0),
                                      i8* blockaddress(@test1, %bb1),
                                      i8* blockaddress(@test1, %bb2),
                                      i8* blockaddress(@test1, %bb3)]
 
 ; Just check the barest skeleton of the structure
 ; CHECK-LABEL: test1:
-; CHECK: block
-; CHECK: block
-; CHECK: block
-; CHECK: block
 ; CHECK: i32.load
 ; CHECK: i32.load
-; CHECK: i32.const
-; CHECK: i32.add $push[[DEST:.+]]=
-; CHECK: br_table $pop[[DEST]]
-; CHECK: end_block
-; CHECK: end_block
-; CHECK: end_block
-; CHECK: end_block
 ; CHECK: loop
 ; CHECK: block
 ; CHECK: block
 ; CHECK: block
 ; CHECK: block
-; CHECK: br_table ${{[^,]+}}, 0, 1, 2, 2
-; CHECK: end_block
-; CHECK: end_block
-; CHECK: end_block
-; CHECK: block
-; CHECK: block
-; CHECK: block
 ; CHECK: br_table ${{[^,]+}}, 1, 2, 0
 ; CHECK: end_block
 ; CHECK: end_block
 ; CHECK: end_block
+; CHECK: end_block
+; CHECK: br
 ; CHECK: end_loop
+; CHECK: end_function
 ; CHECK: test1.targets:
 ; CHECK-NEXT: .int32
 ; CHECK-NEXT: .int32
 ; CHECK-NEXT: .int32
 ; CHECK-NEXT: .int32
 
 define void @test1(i32* readonly %p, i32* %sink) #0 {
 

llvm/test/CodeGen/WebAssembly/switch-in-loop.ll

+; RUN: llc < %s -asm-verbose=false -verify-machineinstrs | FileCheck %s
+
+;; Test that a small but nontrivial switch in a loop (like in a
+;; bytecode interpreter) lowers reasonably without any irreducible
+;; control flow being introduced.
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32"
+
+declare void @a(i32*)
+declare void @b(i32*)
+
+; CHECK-LABEL: switch_in_loop:
+; CHECK-NEXT: .functype switch_in_loop (i32, i32) -> (i32)
+; CHECK:    global.get __stack_pointer
+; CHECK:    global.set __stack_pointer
+; CHECK:    block
+; CHECK:    br_if 0
+; CHECK: .LBB0_2:
+; CHECK:    loop
+; CHECK:    block
+; CHECK:    block
+; CHECK:    block
+; CHECK:    br_table {0, 1, 2}
+; CHECK: .LBB0_3:
+; CHECK:    end_block
+; CHECK:    call a
+; CHECK:    br 1
+; CHECK: .LBB0_4:
+; CHECK:    end_block
+; CHECK:    call b
+; CHECK: .LBB0_5:
+; CHECK:    end_block
+; CHECK:    br_if 0
+; CHECK:    end_loop
+; CHECK: .LBB0_7:
+; CHECK:    end_block
+; CHECK:    global.set __stack_pointer
+; CHECK:    end_function
+define i32 @switch_in_loop(i32* %ops, i32 %len) {
+entry:
+  %res = alloca i32
+  %0 = bitcast i32* %res to i8*
+  store i32 0, i32* %res
+  %cmp6 = icmp sgt i32 %len, 0
+  br i1 %cmp6, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup.loopexit:                        ; preds = %sw.epilog
+  %.pre = load i32, i32* %res
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  %1 = phi i32 [ %.pre, %for.cond.cleanup.loopexit ], [ 0, %entry ]
+  ret i32 %1
+
+for.body:                                         ; preds = %entry, %sw.epilog
+  %i.07 = phi i32 [ %inc, %sw.epilog ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %ops, i32 %i.07
+  %2 = load i32, i32* %arrayidx
+  switch i32 %2, label %sw.epilog [
+    i32 0, label %sw.bb
+    i32 1, label %sw.bb1
+  ]
+
+sw.bb:                                            ; preds = %for.body
+  call void @a(i32* nonnull %res)
+  br label %sw.epilog
+
+sw.bb1:                                           ; preds = %for.body
+  call void @b(i32* nonnull %res)
+  br label %sw.epilog
+
+sw.epilog:                                        ; preds = %for.body, %sw.bb1, %sw.bb
+  %inc = add nuw nsw i32 %i.07, 1
+  %exitcond = icmp eq i32 %inc, %len
+  br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body
+}