[WebAssembly] Fold xor by inverting branch target

[samparker]

Summary

I noticed this pattern appearing when running the bullet physics engine on node. Folding away the xor looks beneficial for different architectures and runtimes, speedups:

Benchmark	Macbook m1 (node)	Macbook m1 (wasmtime)	Ryzen 3 (node)
Bullet	1.4%	0.5%	1%
Adobe	2.4%	0.8%	2.3%

I have performed this transformation directly in v8 too and the numbers correlate.

[samparker]

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

33

Ah, I've remembered that I thought I should check that the incoming I32 is indeed a boolean value.

[kripken]

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

33

Yes, this seems like a valid pattern for any boolean value, not just one flowing into a br? That is,

bool(x) ^ 1 => !bool(x)

or in wasm

(i32.xor X (i32.const 1)) => (i32.eqz X)

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

33

Is there a good way to check for boolean values from tablegen patterns?

[craig.topper]

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

33

You'd need to use a PatFrag to call computeKnownBits I think.

[samparker]

Thanks all. I've added a PatLeaf to detect a boolean, but I wasn't sure how to write a negative test using LLVM IR considering that the branch always takes an i1. Any ideas?

[craig.topper]

In D99171#2646847, @samparker wrote:

Thanks all. I've added a PatLeaf to detect a boolean, but I wasn't sure how to write a negative test using LLVM IR considering that the branch always takes an i1. Any ideas?

If you're starting from brcond, I don't think you need the check. I think the input to brcond should agree with the what the target has defined for getBooleanContents. I assume that's ZeroOrOne for WebAssembly. If you were to generalize this for xors not being used by a brcond you would need a check.

[tlively]

@samparker Can you add tests that do explicit xors in the IR to show that it is not folded out where it shouldn't be?

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

29–31

This looks generally useful; Can you move it to WebAssemblyInstrInfo.td and add a TODO about using it in more places?

33

@craig.topper, by

If you're starting from brcond, I don't think you need the check.

Do you mean that we shouldn't need to use bool_node here?

[samparker]

Can you add tests that do explicit xors in the IR to show that it is not folded out where it shouldn't be?

Well this is what I mean, that I don't think this is possible. Writing a test in IR, the br has to take an i1, though this is expanded to i32 during codegen. I could write some IR tests with xors, but they should all be valid. AFAIK, I'd need a way of writing a test input in selection dag form to write a negative test. I have missed some FP conditions in the existing tests, so I'm going to add those.

[samparker]

• Moved PatLeaf to top-level file.
• Added tests for missing FP conditions.
• Added switch tests.

[tlively]

Looks good, thanks! Do you need me to land this for you?

[samparker]

Cheers! And no thanks - I've had commit access for a few years.

[sbc100]

llvm/test/CodeGen/WebAssembly/comparisons-f32.ll

304

Probably cleaner not to include C++ name mangling here. Maybe just call1?

[samparker]

llvm/test/CodeGen/WebAssembly/comparisons-f32.ll

304

Done: f1313b3b249a

llvm/lib/Target/WebAssembly/WebAssemblyInstrControl.td

 defm BR_UNLESS : I<(outs), (ins bb_op:$dst, I32:$cond),
                    (outs), (ins bb_op:$dst), []>;
 let isBarrier = 1 in
 defm BR   : NRI<(outs), (ins bb_op:$dst),
                 [(br bb:$dst)],
                 "br      \t$dst", 0x0c>;
 } // isBranch = 1, isTerminator = 1, hasCtrlDep = 1
 
 def : Pat<(brcond (i32 (setne I32:$cond, 0)), bb:$dst),
           (BR_IF bb_op:$dst, I32:$cond)>;
 def : Pat<(brcond (i32 (seteq I32:$cond, 0)), bb:$dst),
           (BR_UNLESS bb_op:$dst, I32:$cond)>;
+def : Pat<(brcond (i32 (xor bool_node:$cond, (i32 1))), bb:$dst),
+          (BR_UNLESS bb_op:$dst, I32:$cond)>;
 
 // A list of branch targets enclosed in {} and separated by comma.
 // 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";

llvm/lib/Target/WebAssembly/WebAssemblyInstrInfo.td

def HeapType : Operand<i32> {
   let PrintMethod = "printWebAssemblyHeapTypeOperand";
 }
 
 let OperandType = "OPERAND_TYPEINDEX" in
 def TypeIndex : Operand<i32>;
 
 } // OperandNamespace = "WebAssembly"
 
+// TODO: Find more places to use this.
+def bool_node : PatLeaf<(i32 I32:$cond), [{
+  return CurDAG->computeKnownBits(SDValue(N, 0)).countMinLeadingZeros() == 31;
+}]>;
+
 //===----------------------------------------------------------------------===//
 // WebAssembly Register to Stack instruction mapping
 //===----------------------------------------------------------------------===//
 
 class StackRel;
 def getStackOpcode : InstrMapping {
   let FilterClass = "StackRel";
   let RowFields = ["BaseName"];

llvm/test/CodeGen/WebAssembly/comparisons-f32.ll

 ; CHECK-NEXT: i32.const $push[[C0:[0-9]+]]=, 1
 ; CHECK-NEXT: i32.xor $push[[NUM2:[0-9]+]]=, $pop[[NUM0]], $pop[[C0]]{{$}}
 ; CHECK-NEXT: return $pop[[NUM2]]{{$}}
 define i32 @uge_f32(float %x, float %y) {
   %a = fcmp uge float %x, %y
   %b = zext i1 %a to i32
   ret i32 %b
 }
+
+; CHECK-LABEL: olt_f32_branch
+; CHECK:      local.get $push[[L4:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L3:[0-9]+]]=, 1
+; CHECK-NEXT: f32.lt    $push[[NUM0:[0-9]+]]=, $pop[[L4]], $pop[[L3]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @olt_f32_branch(float %a, float %b) {
+entry:
+  %cmp = fcmp olt float %a, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ole_f32_branch
+; CHECK:      local.get $push[[L4:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L3:[0-9]+]]=, 1
+; CHECK-NEXT: f32.le    $push[[NUM0:[0-9]+]]=, $pop[[L4]], $pop[[L3]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ole_f32_branch(float %a, float %b) {
+entry:
+  %cmp = fcmp ole float %a, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ugt_f32_branch
+; CHECK:      local.get $push[[L4:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L3:[0-9]+]]=, 1
+; CHECK-NEXT: f32.le    $push[[NUM0:[0-9]+]]=, $pop[[L4]], $pop[[L3]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ugt_f32_branch(float %a, float %b) {
+entry:
+  %cmp = fcmp ugt float %a, %b
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ogt_f32_branch
+; CHECK:      local.get $push[[L4:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L3:[0-9]+]]=, 1
+; CHECK-NEXT: f32.gt    $push[[NUM0:[0-9]+]]=, $pop[[L4]], $pop[[L3]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ogt_f32_branch(float %a, float %b) {
+entry:
+  %cmp = fcmp ogt float %a, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ult_f32_branch
+; CHECK:      local.get $push[[L4:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L3:[0-9]+]]=, 1
+; CHECK-NEXT: f32.ge    $push[[NUM0:[0-9]+]]=, $pop[[L4]], $pop[[L3]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ult_f32_branch(float %a, float %b) {
+entry:
+  %cmp = fcmp ult float %a, %b
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ule_f32_branch
+; CHECK:      local.get $push[[L4:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L3:[0-9]+]]=, 1
+; CHECK-NEXT: f32.ge    $push[[NUM0:[0-9]+]]=, $pop[[L4]], $pop[[L3]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ule_f32_branch(float %a, float %b) {
+entry:
+  %cmp = fcmp ult float %a, %b
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: xor_zext_switch
+; CHECK:      i32.const $push[[L1:[0-9]+]]=, 0
+; CHECK-NEXT: br_if     0, $pop[[L1]]
+; CHECK-NEXT: block
+; CHECK-NEXT: block
+; CHECK-NEXT: local.get $push[[L3:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L2:[0-9]+]]=, 1
+; CHECK-NEXT: f32.ge    $push[[L0:[0-9]+]]=, $pop[[L3]], $pop[[L2]]
+; CHECK-NEXT: br_table  $pop[[L0]], 0, 1, 0
+define void @xor_zext_switch(float %a, float %b) {
+entry:
+  %cmp = fcmp ult float %a, %b
+  %zext = zext i1 %cmp to i32
+  %xor = xor i32 %zext, 1
+  switch i32 %xor, label %exit [
+    i32 0, label %sw.bb.1
+    i32 1, label %sw.bb.2
+  ]
+
+sw.bb.1:
+  tail call void @foo1()
+  br label %exit
+
+sw.bb.2:
+  tail call void @foo2()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: xor_add_switch
+; CHECK:      local.get $push[[L8:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L7:[0-9]+]]=, 1
+; CHECK-NEXT: f32.ge    $push[[L1:[0-9]+]]=, $pop[[L8]], $pop[[L7]]
+; CHECK-NEXT: i32.const $push[[L2:[0-9]+]]=, 1
+; CHECK-NEXT: i32.xor   $push[[L3:[0-9]+]]=, $pop[[L1]], $pop[[L2]]
+; CHECK-NEXT: i32.const $push[[L6:[0-9]+]]=, 1
+; CHECK-NEXT: i32.add   $push[[L4:[0-9]+]]=, $pop[[L3]], $pop[[L6]]
+; CHECK-NEXT: i32.const $push[[L5:[0-9]+]]=, 1
+; CHECK-NEXT: i32.xor   $push[[L0:[0-9]+]]=, $pop[[L4]], $pop[[L5]]
+; CHECK-NEXT: br_table  $pop[[L0]], 0, 1, 2, 3
+define void @xor_add_switch(float %a, float %b) {
+entry:
+  %cmp = fcmp ult float %a, %b
+  %zext = zext i1 %cmp to i32
+  %add = add nsw nuw i32 %zext, 1
+  %xor = xor i32 %add, 1
+  switch i32 %xor, label %exit [
+    i32 0, label %sw.bb.1
+    i32 1, label %sw.bb.2
+    i32 2, label %sw.bb.3
+  ]
+
+sw.bb.1:
+  tail call void @foo1()
+  br label %exit
+
+sw.bb.2:
+  tail call void @foo2()
+  br label %exit
+
+sw.bb.3:
+  tail call void @foo3()
+  br label %exit
+
+exit:
+  ret void
+}
+
+declare void @foo1()
+declare void @foo2()
+declare void @foo3()
+declare void @_Z5call1v()

llvm/test/CodeGen/WebAssembly/comparisons-f64.ll

 ; CHECK-NEXT: i32.const $push[[C0:[0-9]+]]=, 1
 ; CHECK-NEXT: i32.xor $push[[NUM2:[0-9]+]]=, $pop[[NUM0]], $pop[[C0]]{{$}}
 ; CHECK-NEXT: return $pop[[NUM2]]{{$}}
 define i32 @uge_f64(double %x, double %y) {
   %a = fcmp uge double %x, %y
   %b = zext i1 %a to i32
   ret i32 %b
 }
+
+; CHECK-LABEL: olt_f64_branch:
+; CHECK:      local.get $push[[L0:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L1:[0-9]+]]=, 1
+; CHECK-NEXT: f64.lt    $push[[NUM0:[0-9]+]]=, $pop[[L0]], $pop[[L1]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @olt_f64_branch(double %a, double %b) {
+entry:
+  %cmp = fcmp olt double %a, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ole_f64_branch:
+; CHECK:      local.get $push[[L0:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L1:[0-9]+]]=, 1
+; CHECK-NEXT: f64.le    $push[[NUM0:[0-9]+]]=, $pop[[L0]], $pop[[L1]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ole_f64_branch(double %a, double %b) {
+entry:
+  %cmp = fcmp ole double %a, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ugt_f64_branch:
+; CHECK:      local.get $push[[L0:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L1:[0-9]+]]=, 1
+; CHECK-NEXT: f64.le    $push[[NUM0:[0-9]+]]=, $pop[[L0]], $pop[[L1]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ugt_f64_branch(double %a, double %b) {
+entry:
+  %cmp = fcmp ugt double %a, %b
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ogt_f64_branch:
+; CHECK:      local.get $push[[L0:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L1:[0-9]+]]=, 1
+; CHECK-NEXT: f64.gt    $push[[NUM0:[0-9]+]]=, $pop[[L0]], $pop[[L1]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ogt_f64_branch(double %a, double %b) {
+entry:
+  %cmp = fcmp ogt double %a, %b
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ult_f64_branch:
+; CHECK:      local.get $push[[L0:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L1:[0-9]+]]=, 1
+; CHECK-NEXT: f64.ge    $push[[NUM0:[0-9]+]]=, $pop[[L0]], $pop[[L1]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ult_f64_branch(double %a, double %b) {
+entry:
+  %cmp = fcmp ult double %a, %b
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: ule_f64_branch:
+; CHECK:      local.get $push[[L0:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L1:[0-9]+]]=, 1
+; CHECK-NEXT: f64.gt    $push[[NUM0:[0-9]+]]=, $pop[[L0]], $pop[[L1]]
+; CHECK-NEXT: i32.eqz   $push[[NUM3:[0-9]+]]=, $pop[[NUM0]]
+; CHECK-NEXT: br_if     0, $pop[[NUM3]]
+; CHECK-NEXT: call  _Z5call1v
+define void @ule_f64_branch(double %a, double %b) {
+entry:
+  %cmp = fcmp ule double %a, %b
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:
+  tail call void @_Z5call1v()
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; CHECK-LABEL: xor_zext_switch
+; CHECK:      i32.const $push[[L1:[0-9]+]]=, 0
+; CHECK-NEXT: br_if     0, $pop[[L1]]
+; CHECK-NEXT: block
+; CHECK-NEXT: block
+; CHECK-NEXT: local.get $push[[L3:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L2:[0-9]+]]=, 1
+; CHECK-NEXT: f64.ge    $push[[L0:[0-9]+]]=, $pop[[L3]], $pop[[L2]]
+; CHECK-NEXT: br_table  $pop[[L0]], 0, 1, 0
+define void @xor_zext_switch(double %a, double %b) {
+entry:
+  %cmp = fcmp ult double %a, %b
+  %zext = zext i1 %cmp to i32
+  %xor = xor i32 %zext, 1
+  switch i32 %xor, label %exit [
+    i32 0, label %sw.bb.1
+    i32 1, label %sw.bb.2
+  ]
+
+sw.bb.1:
+  tail call void @foo1()
+  br label %exit
+
+sw.bb.2:
+  tail call void @foo2()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: xor_add_switch
+; CHECK:      local.get $push[[L8:[0-9]+]]=, 0
+; CHECK-NEXT: local.get $push[[L7:[0-9]+]]=, 1
+; CHECK-NEXT: f64.ge    $push[[L1:[0-9]+]]=, $pop[[L8]], $pop[[L7]]
+; CHECK-NEXT: i32.const $push[[L2:[0-9]+]]=, 1
+; CHECK-NEXT: i32.xor   $push[[L3:[0-9]+]]=, $pop[[L1]], $pop[[L2]]
+; CHECK-NEXT: i32.const $push[[L6:[0-9]+]]=, 1
+; CHECK-NEXT: i32.add   $push[[L4:[0-9]+]]=, $pop[[L3]], $pop[[L6]]
+; CHECK-NEXT: i32.const $push[[L5:[0-9]+]]=, 1
+; CHECK-NEXT: i32.xor   $push[[L0:[0-9]+]]=, $pop[[L4]], $pop[[L5]]
+; CHECK-NEXT: br_table  $pop[[L0]], 0, 1, 2, 3
+define void @xor_add_switch(double %a, double %b) {
+entry:
+  %cmp = fcmp ult double %a, %b
+  %zext = zext i1 %cmp to i32
+  %add = add nsw nuw i32 %zext, 1
+  %xor = xor i32 %add, 1
+  switch i32 %xor, label %exit [
+    i32 0, label %sw.bb.1
+    i32 1, label %sw.bb.2
+    i32 2, label %sw.bb.3
+  ]
+
+sw.bb.1:
+  tail call void @foo1()
+  br label %exit
+
+sw.bb.2:
+  tail call void @foo2()
+  br label %exit
+
+sw.bb.3:
+  tail call void @foo3()
+  br label %exit
+
+exit:
+  ret void
+}
+
+declare void @foo1()
+declare void @foo2()
+declare void @foo3()
+declare void @_Z5call1v()