[DAGCombiner] fold or (xor x, y),? patterns

[bcl5980]

Summary

or (xor x, y), x --> or x, y
or (xor x, y), y --> or x, y
or (xor x, y), (and x, y) --> or x, y
or (xor x, y), (or x, y) --> or x, y

[foad]

Does instcombine do this at the IR level? Is there a need to do it in selectiondag too?

[bcl5980]

In D138401#3940326, @foad wrote:

Does instcombine do this at the IR level? Is there a need to do it in selectiondag too?

Yeah, instsimplify do this. But I find some corner cases in selectiondag can trigger this code because of some logical op generated by SelectionDAG itself. So, I add all similar code in this change.

[RKSimon]

llvm/test/CodeGen/X86/combine-sra-load.ll

99

This test probably needs adjusting so the multiple uses of %shift remains.

[foad]

In D138401#3940345, @bcl5980 wrote:

In D138401#3940326, @foad wrote:

Does instcombine do this at the IR level? Is there a need to do it in selectiondag too?

Yeah, instsimplify do this. But I find some corner cases in selectiondag can trigger this code because of some logical op generated by SelectionDAG itself. So, I add all similar code in this change.

Can you add a test that shows that happening?

[bcl5980]

add a test to amdgpu for or (xor x, y), x --> or x, y
adjust test sra_to_sextload_multiple_sra_uses

[bcl5980]

In D138401#3940984, @foad wrote:

In D138401#3940345, @bcl5980 wrote:

In D138401#3940326, @foad wrote:

Does instcombine do this at the IR level? Is there a need to do it in selectiondag too?

Yeah, instsimplify do this. But I find some corner cases in selectiondag can trigger this code because of some logical op generated by SelectionDAG itself. So, I add all similar code in this change.

Can you add a test that shows that happening?

If you think the test is OK I can precommit the test.

[foad]

In D138401#3942877, @bcl5980 wrote:

In D138401#3940984, @foad wrote:

In D138401#3940345, @bcl5980 wrote:

In D138401#3940326, @foad wrote:

Does instcombine do this at the IR level? Is there a need to do it in selectiondag too?

Yeah, instsimplify do this. But I find some corner cases in selectiondag can trigger this code because of some logical op generated by SelectionDAG itself. So, I add all similar code in this change.

Can you add a test that shows that happening?

If you think the test is OK I can precommit the test.

Yes, please do.

[bcl5980]

rebase code

[foad]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7001–7002

Should we also handle the commuted forms of the OR?
or x, (xor x, y)
or (x and/or y), (xor x, y)

[bcl5980]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

7001–7002

We already handle these case. This code is in the function visitORCommutative. It will call twice with (N0, N1) and (N1, N0).

[foad]

LGTM, thanks.

Please consider adding a similar combine for GlobalISel.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (getBitwiseNotOperand(N01, N00,
       return DAG.getNode(ISD::OR, SDLoc(N), VT, N00, N1);
 
     // fold (or (and (xor Y, -1), X), Y) -> (or X, Y)
     if (getBitwiseNotOperand(N00, N01,
                              /* AllowUndefs */ false) == N1)
       return DAG.getNode(ISD::OR, SDLoc(N), VT, N01, N1);
   }
 
+  if (N0.getOpcode() == ISD::XOR) {
+    // fold or (xor x, y), x --> or x, y
+    //      or (xor x, y), (x and/or y) --> or x, y
+    SDValue N00 = N0.getOperand(0);
+    SDValue N01 = N0.getOperand(1);
+    if (N00 == N1)
+      return DAG.getNode(ISD::OR, SDLoc(N), VT, N01, N1);
+    if (N01 == N1)
+      return DAG.getNode(ISD::OR, SDLoc(N), VT, N00, N1);
+
+    if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
+      SDValue N10 = N1.getOperand(0);
+      SDValue N11 = N1.getOperand(1);
+      if (N00 == N10 && N01 == N11 || N00 == N11 && N01 == N10)
+        return DAG.getNode(ISD::OR, SDLoc(N), VT, N00, N01);
+    }
+  }
+
   if (SDValue R = foldLogicOfShifts(N, N0, N1, DAG))
     return R;
 
   auto peekThroughZext = [](SDValue V) {
     if (V->getOpcode() == ISD::ZERO_EXTEND)
       return V->getOperand(0);
     return V;
   };

llvm/test/CodeGen/AMDGPU/xor3-i1-const.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -march=amdgcn -mcpu=bonaire -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
 
 ; This test used to crash
 define amdgpu_ps float @xor3_i1_const(float inreg %arg1, i32 inreg %arg2) {
 ; GCN-LABEL: xor3_i1_const:
 ; GCN:       ; %bb.0: ; %main_body
-; GCN-NEXT:    s_mov_b32 m0, s1
-; GCN-NEXT:    v_mov_b32_e32 v1, 0x42640000
-; GCN-NEXT:    v_cmp_nlt_f32_e64 s[2:3], s0, 0
-; GCN-NEXT:    v_interp_p2_f32 v0, v0, attr0.x
-; GCN-NEXT:    v_cmp_nlt_f32_e32 vcc, s0, v1
-; GCN-NEXT:    v_cmp_gt_f32_e64 s[0:1], 0, v0
-; GCN-NEXT:    s_or_b64 s[2:3], s[2:3], vcc
-; GCN-NEXT:    s_and_b64 s[0:1], s[0:1], s[2:3]
-; GCN-NEXT:    s_xor_b64 s[2:3], s[2:3], s[0:1]
-; GCN-NEXT:    s_or_b64 s[0:1], s[2:3], s[0:1]
-; GCN-NEXT:    v_cndmask_b32_e64 v0, 0, 1.0, s[0:1]
+; GCN-NEXT:    v_mov_b32_e32 v0, 0x42640000
+; GCN-NEXT:    v_cmp_lt_f32_e64 s[2:3], s0, 0
+; GCN-NEXT:    v_cmp_lt_f32_e32 vcc, s0, v0
+; GCN-NEXT:    s_and_b64 s[0:1], s[2:3], vcc
+; GCN-NEXT:    v_cndmask_b32_e64 v0, 1.0, 0, s[0:1]
 ; GCN-NEXT:    ; return to shader part epilog
 main_body:
   %tmp26 = fcmp nsz olt float %arg1, 0.000000e+00
   %tmp28 = call nsz float @llvm.amdgcn.interp.p2(float undef, float undef, i32 0, i32 0, i32 %arg2)
   %tmp29 = fcmp nsz olt float %arg1, 5.700000e+01
   %tmp31 = fcmp nsz olt float %tmp28, 0.000000e+00
   %.demorgan = and i1 %tmp26, %tmp29
   %tmp34 = xor i1 %.demorgan, true

llvm/test/CodeGen/X86/avx512-mask-op.ll

; X86-NEXT:    retl
   store i8 %ret, ptr %ptr, align 4
   ret void
 }
 
 define i16 @mand16(i16 %x, i16 %y) {
 ; CHECK-LABEL: mand16:
 ; CHECK:       ## %bb.0:
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    andl %esi, %eax
-; CHECK-NEXT:    xorl %esi, %edi
-; CHECK-NEXT:    orl %edi, %eax
+; CHECK-NEXT:    orl %esi, %eax
 ; CHECK-NEXT:    ## kill: def $ax killed $ax killed $eax
 ; CHECK-NEXT:    retq
 ;
 ; X86-LABEL: mand16:
 ; X86:       ## %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl %eax, %edx
-; X86-NEXT:    andl %ecx, %edx
-; X86-NEXT:    xorl %ecx, %eax
-; X86-NEXT:    orl %edx, %eax
-; X86-NEXT:    ## kill: def $ax killed $ax killed $eax
+; X86-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
+; X86-NEXT:    orw {{[0-9]+}}(%esp), %ax
 ; X86-NEXT:    retl
   %ma = bitcast i16 %x to <16 x i1>
   %mb = bitcast i16 %y to <16 x i1>
   %mc = and <16 x i1> %ma, %mb
   %md = xor <16 x i1> %ma, %mb
   %me = or <16 x i1> %mc, %md
   %ret = bitcast <16 x i1> %me to i16
   ret i16 %ret
 }
 
 define i16 @mand16_mem(ptr %x, ptr %y) {
 ; KNL-LABEL: mand16_mem:
 ; KNL:       ## %bb.0:
 ; KNL-NEXT:    kmovw (%rdi), %k0
 ; KNL-NEXT:    kmovw (%rsi), %k1
-; KNL-NEXT:    kandw %k1, %k0, %k2
-; KNL-NEXT:    kxorw %k1, %k0, %k0
-; KNL-NEXT:    korw %k0, %k2, %k0
+; KNL-NEXT:    korw %k1, %k0, %k0
 ; KNL-NEXT:    kmovw %k0, %eax
 ; KNL-NEXT:    ## kill: def $ax killed $ax killed $eax
 ; KNL-NEXT:    retq
 ;
 ; SKX-LABEL: mand16_mem:
 ; SKX:       ## %bb.0:
 ; SKX-NEXT:    kmovw (%rdi), %k0
 ; SKX-NEXT:    kmovw (%rsi), %k1
-; SKX-NEXT:    kandw %k1, %k0, %k2
-; SKX-NEXT:    kxorw %k1, %k0, %k0
-; SKX-NEXT:    korw %k0, %k2, %k0
+; SKX-NEXT:    korw %k1, %k0, %k0
 ; SKX-NEXT:    kmovd %k0, %eax
 ; SKX-NEXT:    ## kill: def $ax killed $ax killed $eax
 ; SKX-NEXT:    retq
 ;
 ; AVX512BW-LABEL: mand16_mem:
 ; AVX512BW:       ## %bb.0:
 ; AVX512BW-NEXT:    kmovw (%rdi), %k0
 ; AVX512BW-NEXT:    kmovw (%rsi), %k1
-; AVX512BW-NEXT:    kandw %k1, %k0, %k2
-; AVX512BW-NEXT:    kxorw %k1, %k0, %k0
-; AVX512BW-NEXT:    korw %k0, %k2, %k0
+; AVX512BW-NEXT:    korw %k1, %k0, %k0
 ; AVX512BW-NEXT:    kmovd %k0, %eax
 ; AVX512BW-NEXT:    ## kill: def $ax killed $ax killed $eax
 ; AVX512BW-NEXT:    retq
 ;
 ; AVX512DQ-LABEL: mand16_mem:
 ; AVX512DQ:       ## %bb.0:
 ; AVX512DQ-NEXT:    kmovw (%rdi), %k0
 ; AVX512DQ-NEXT:    kmovw (%rsi), %k1
-; AVX512DQ-NEXT:    kandw %k1, %k0, %k2
-; AVX512DQ-NEXT:    kxorw %k1, %k0, %k0
-; AVX512DQ-NEXT:    korw %k0, %k2, %k0
+; AVX512DQ-NEXT:    korw %k1, %k0, %k0
 ; AVX512DQ-NEXT:    kmovw %k0, %eax
 ; AVX512DQ-NEXT:    ## kill: def $ax killed $ax killed $eax
 ; AVX512DQ-NEXT:    retq
 ;
 ; X86-LABEL: mand16_mem:
 ; X86:       ## %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    kmovw (%ecx), %k0
 ; X86-NEXT:    kmovw (%eax), %k1
-; X86-NEXT:    kandw %k1, %k0, %k2
-; X86-NEXT:    kxorw %k1, %k0, %k0
-; X86-NEXT:    korw %k0, %k2, %k0
+; X86-NEXT:    korw %k1, %k0, %k0
 ; X86-NEXT:    kmovd %k0, %eax
 ; X86-NEXT:    ## kill: def $ax killed $ax killed $eax
 ; X86-NEXT:    retl
   %ma = load <16 x i1>, ptr %x
   %mb = load <16 x i1>, ptr %y
   %mc = and <16 x i1> %ma, %mb
   %md = xor <16 x i1> %ma, %mb
   %me = or <16 x i1> %mc, %md

llvm/test/CodeGen/X86/avx512bw-mask-op.ll

; CHECK-NEXT:    retq
   store i64 %ret, ptr %ptr, align 4
   ret void
 }
 
 define i32 @mand32(i32 %x, i32 %y) {
 ; CHECK-LABEL: mand32:
 ; CHECK:       ## %bb.0:
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    andl %esi, %eax
-; CHECK-NEXT:    xorl %esi, %edi
-; CHECK-NEXT:    orl %edi, %eax
+; CHECK-NEXT:    orl %esi, %eax
 ; CHECK-NEXT:    retq
   %ma = bitcast i32 %x to <32 x i1>
   %mb = bitcast i32 %y to <32 x i1>
   %mc = and <32 x i1> %ma, %mb
   %md = xor <32 x i1> %ma, %mb
   %me = or <32 x i1> %mc, %md
   %ret = bitcast <32 x i1> %me to i32
   ret i32 %ret
 }
 
 define i32 @mand32_mem(ptr %x, ptr %y) {
 ; CHECK-LABEL: mand32_mem:
 ; CHECK:       ## %bb.0:
 ; CHECK-NEXT:    kmovd (%rdi), %k0
 ; CHECK-NEXT:    kmovd (%rsi), %k1
-; CHECK-NEXT:    kandd %k1, %k0, %k2
-; CHECK-NEXT:    kxord %k1, %k0, %k0
-; CHECK-NEXT:    kord %k0, %k2, %k0
+; CHECK-NEXT:    kord %k1, %k0, %k0
 ; CHECK-NEXT:    kmovd %k0, %eax
 ; CHECK-NEXT:    retq
   %ma = load <32 x i1>, ptr %x
   %mb = load <32 x i1>, ptr %y
   %mc = and <32 x i1> %ma, %mb
   %md = xor <32 x i1> %ma, %mb
   %me = or <32 x i1> %mc, %md
   %ret = bitcast <32 x i1> %me to i32
   ret i32 %ret
 }
 
 define i64 @mand64(i64 %x, i64 %y) {
 ; CHECK-LABEL: mand64:
 ; CHECK:       ## %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    andq %rsi, %rax
-; CHECK-NEXT:    xorq %rsi, %rdi
-; CHECK-NEXT:    orq %rdi, %rax
+; CHECK-NEXT:    orq %rsi, %rax
 ; CHECK-NEXT:    retq
   %ma = bitcast i64 %x to <64 x i1>
   %mb = bitcast i64 %y to <64 x i1>
   %mc = and <64 x i1> %ma, %mb
   %md = xor <64 x i1> %ma, %mb
   %me = or <64 x i1> %mc, %md
   %ret = bitcast <64 x i1> %me to i64
   ret i64 %ret
 }
 
 define i64 @mand64_mem(ptr %x, ptr %y) {
 ; CHECK-LABEL: mand64_mem:
 ; CHECK:       ## %bb.0:
 ; CHECK-NEXT:    kmovq (%rdi), %k0
 ; CHECK-NEXT:    kmovq (%rsi), %k1
-; CHECK-NEXT:    kandq %k1, %k0, %k2
-; CHECK-NEXT:    kxorq %k1, %k0, %k0
-; CHECK-NEXT:    korq %k0, %k2, %k0
+; CHECK-NEXT:    korq %k1, %k0, %k0
 ; CHECK-NEXT:    kmovq %k0, %rax
 ; CHECK-NEXT:    retq
   %ma = load <64 x i1>, ptr %x
   %mb = load <64 x i1>, ptr %y
   %mc = and <64 x i1> %ma, %mb
   %md = xor <64 x i1> %ma, %mb
   %me = or <64 x i1> %mc, %md
   %ret = bitcast <64 x i1> %me to i64

llvm/test/CodeGen/X86/avx512dq-mask-op.ll

; CHECK-NEXT:    retq
   store i8 %ret, ptr %ptr, align 4
   ret void
 }
 
 define i8 @mand8(i8 %x, i8 %y) {
 ; CHECK-LABEL: mand8:
 ; CHECK:       ## %bb.0:
 ; CHECK-NEXT:    movl %edi, %eax
-; CHECK-NEXT:    andb %sil, %al
-; CHECK-NEXT:    xorb %sil, %dil
-; CHECK-NEXT:    orb %dil, %al
+; CHECK-NEXT:    orl %esi, %eax
+; CHECK-NEXT:    ## kill: def $al killed $al killed $eax
 ; CHECK-NEXT:    retq
   %ma = bitcast i8 %x to <8 x i1>
   %mb = bitcast i8 %y to <8 x i1>
   %mc = and <8 x i1> %ma, %mb
   %md = xor <8 x i1> %ma, %mb
   %me = or <8 x i1> %mc, %md
   %ret = bitcast <8 x i1> %me to i8
   ret i8 %ret
 }
 
 define i8 @mand8_mem(ptr %x, ptr %y) {
 ; CHECK-LABEL: mand8_mem:
 ; CHECK:       ## %bb.0:
 ; CHECK-NEXT:    kmovb (%rdi), %k0
 ; CHECK-NEXT:    kmovb (%rsi), %k1
-; CHECK-NEXT:    kandb %k1, %k0, %k2
-; CHECK-NEXT:    kxorb %k1, %k0, %k0
-; CHECK-NEXT:    korb %k0, %k2, %k0
+; CHECK-NEXT:    korb %k1, %k0, %k0
 ; CHECK-NEXT:    kmovd %k0, %eax
 ; CHECK-NEXT:    ## kill: def $al killed $al killed $eax
 ; CHECK-NEXT:    retq
   %ma = load <8 x i1>, ptr %x
   %mb = load <8 x i1>, ptr %y
   %mc = and <8 x i1> %ma, %mb
   %md = xor <8 x i1> %ma, %mb
   %me = or <8 x i1> %mc, %md
   %ret = bitcast <8 x i1> %me to i8
   ret i8 %ret
 }

llvm/test/CodeGen/X86/combine-sra-load.ll

; CHECK-NEXT:    retq
   %shift = ashr i32 %sext, 16
   ret i32 %shift
 }
 
 ; Fold even if SRA has multiple uses.
 define i32 @sra_to_sextload_multiple_sra_uses(ptr %p) {
 ; CHECK-LABEL: sra_to_sextload_multiple_sra_uses:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movswl 2(%rdi), %ecx
-; CHECK-NEXT:    movl %ecx, %eax
-; CHECK-NEXT:    xorl $6, %eax
-; CHECK-NEXT:    orl %ecx, %eax
+; CHECK-NEXT:    movswl 2(%rdi), %eax
+; CHECK-NEXT:    orl $6, %eax
 ; CHECK-NEXT:    retq
   %load = load i32, ptr %p
   %shift = ashr i32 %load, 16
   %use1 = xor i32 %shift, 6
   %use2 = or i32 %shift, %use1
   ret i32 %use2
 }