[X86][BMI] Fold cmpeq/ne(or(X,Y),X) --> cmpeq/ne(and(~X,Y),0) (PR44136)

[RKSimon]

Summary

I've initially just enabled this for BMI which has the ANDN instruction for i32/i64 - the i16/i8 cases give an idea of what'd we get if we enabled it in all cases.

Additionally, the i16/i8 cases could be freely promoted to i32 (as the args are already zeroext) and we could then make use of ANDN + the free cmp0 there as well - this has come up in PR48768 and PR49028 so I'm going to look at this soon.

https://alive2.llvm.org/ce/z/QVWHP_
https://alive2.llvm.org/ce/z/pLngT-

Vector cases do not appear to benefit from this as we end up with having to generate the zero vector as well - this is one of the reasons I didn't try to tie this into hasAndNot/hasAndNotCompare.

[RKSimon]

Just noticed this works for cmpne as well - https://alive2.llvm.org/ce/z/pLngT- - I'll update the tests/patch

[RKSimon]

Added cmpne handling

[spatel]

llvm/lib/Target/X86/X86ISelLowering.cpp

48170

Is isOnlyUserOf() safer/better than hasOneUse() in this pattern (or in general)?

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

48170

Nice catch - its a force of habit from shuffle combining!

[RKSimon]

Fixed oneuse check

[spatel]

LGTM - unless there's a danger of reversal (infinite looping), it should be fine to remove the BMI predicate to make things uniform.
Every x86 has test, and I don't see any implementations where it would perform at lower perf than other basic ALU instructions, so that ensures we're no worse off using not+test.

[RKSimon]

In D100177#2679647, @spatel wrote:

LGTM - unless there's a danger of reversal (infinite looping), it should be fine to remove the BMI predicate to make things uniform.
Every x86 has test, and I don't see any implementations where it would perform at lower perf than other basic ALU instructions, so that ensures we're no worse off using not+test.

Cheers, I'll remove the BMI limit - the plan is to add the reverse fold in InstCombine (see PR44136) but there isn't an equivalent in DAG afaict.

llvm/lib/Target/X86/X86ISelLowering.cpp

if (CC == ISD::SETNE || CC == ISD::SETEQ) {
 
     if (VT == MVT::i1 && isNullConstant(RHS)) {
       SDValue X86CC;
       if (SDValue V =
               MatchVectorAllZeroTest(LHS, CC, DL, Subtarget, DAG, X86CC))
         return DAG.getNode(ISD::TRUNCATE, DL, VT,
                            DAG.getNode(X86ISD::SETCC, DL, MVT::i8, X86CC, V));
     }
+
+    // cmpeq(or(X,Y),X) --> cmpeq(and(~X,Y),0)
+    // cmpne(or(X,Y),X) --> cmpne(and(~X,Y),0)
+    if (OpVT.isScalarInteger() && Subtarget.hasBMI()) {
+      auto MatchOrCmpEq = [&](SDValue N0, SDValue N1) {
+        if (N0.getOpcode() == ISD::OR && N0->hasOneUse()) {
+          if (N0.getOperand(0) == N1)
+            return DAG.getNode(ISD::AND, DL, OpVT, DAG.getNOT(DL, N1, OpVT),
+                               N0.getOperand(1));
+          if (N0.getOperand(1) == N1)
+            return DAG.getNode(ISD::AND, DL, OpVT, DAG.getNOT(DL, N1, OpVT),
+                               N0.getOperand(0));
+        }
+        return SDValue();
+      };
+      if (SDValue AndN = MatchOrCmpEq(LHS, RHS))
+        return DAG.getSetCC(DL, VT, AndN, DAG.getConstant(0, DL, OpVT), CC);
+      if (SDValue AndN = MatchOrCmpEq(RHS, LHS))
+        return DAG.getSetCC(DL, VT, AndN, DAG.getConstant(0, DL, OpVT), CC);
+    }
   }
 
   if (VT.isVector() && VT.getVectorElementType() == MVT::i1 &&
       (CC == ISD::SETNE || CC == ISD::SETEQ || ISD::isSignedIntSetCC(CC))) {
     // Using temporaries to avoid messing up operand ordering for later
     // transformations if this doesn't work.
     SDValue Op0 = LHS;
     SDValue Op1 = RHS;

llvm/test/CodeGen/X86/setcc-logic.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
-; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s
-; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+bmi | FileCheck %s
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown | FileCheck %s --check-prefixes=CHECK,NOBMI
+; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+bmi | FileCheck %s --check-prefixes=CHECK,BMI
 
 define zeroext i1 @all_bits_clear(i32 %P, i32 %Q) nounwind {
 ; CHECK-LABEL: all_bits_clear:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    orl %esi, %edi
 ; CHECK-NEXT:    sete %al
 ; CHECK-NEXT:    retq
   %a = icmp eq i32 %P, 0

 ; CHECK-NEXT:    orb %cl, %al
 ; CHECK-NEXT:    retq
   %a = icmp eq i32 %x, 43
   %b = icmp eq i32 %y, 45
   %r = or i1 %a, %b
   ret i1 %r
 }
 
-; TODO: PR44136 - fold cmpeq(or(X,Y),X) --> cmpeq(and(~X,Y),0)
+; PR44136 - fold cmpeq(or(X,Y),X) --> cmpeq(and(~X,Y),0)
 
 define i1 @or_cmp_eq_i64(i64 %x, i64 %y) {
-; CHECK-LABEL: or_cmp_eq_i64:
-; CHECK:       # %bb.0:
-; CHECK-NEXT:    orq %rdi, %rsi
-; CHECK-NEXT:    cmpq %rdi, %rsi
-; CHECK-NEXT:    sete %al
-; CHECK-NEXT:    retq
+; NOBMI-LABEL: or_cmp_eq_i64:
+; NOBMI:       # %bb.0:
+; NOBMI-NEXT:    orq %rdi, %rsi
+; NOBMI-NEXT:    cmpq %rdi, %rsi
+; NOBMI-NEXT:    sete %al
+; NOBMI-NEXT:    retq
+;
+; BMI-LABEL: or_cmp_eq_i64:
+; BMI:       # %bb.0:
+; BMI-NEXT:    andnq %rsi, %rdi, %rax
+; BMI-NEXT:    sete %al
+; BMI-NEXT:    retq
   %o = or i64 %x, %y
   %c = icmp eq i64 %o, %x
   ret i1 %c
 }
 
 define i1 @or_cmp_ne_i32(i32 %x, i32 %y) {
-; CHECK-LABEL: or_cmp_ne_i32:
-; CHECK:       # %bb.0:
-; CHECK-NEXT:    orl %esi, %edi
-; CHECK-NEXT:    cmpl %esi, %edi
-; CHECK-NEXT:    setne %al
-; CHECK-NEXT:    retq
+; NOBMI-LABEL: or_cmp_ne_i32:
+; NOBMI:       # %bb.0:
+; NOBMI-NEXT:    orl %esi, %edi
+; NOBMI-NEXT:    cmpl %esi, %edi
+; NOBMI-NEXT:    setne %al
+; NOBMI-NEXT:    retq
+;
+; BMI-LABEL: or_cmp_ne_i32:
+; BMI:       # %bb.0:
+; BMI-NEXT:    andnl %edi, %esi, %eax
+; BMI-NEXT:    setne %al
+; BMI-NEXT:    retq
   %o = or i32 %x, %y
   %c = icmp ne i32 %o, %y
   ret i1 %c
 }
 
 define i1 @or_cmp_eq_i16(i16 zeroext %x, i16 zeroext %y) {
-; CHECK-LABEL: or_cmp_eq_i16:
-; CHECK:       # %bb.0:
-; CHECK-NEXT:    orl %edi, %esi
-; CHECK-NEXT:    cmpw %si, %di
-; CHECK-NEXT:    sete %al
-; CHECK-NEXT:    retq
+; NOBMI-LABEL: or_cmp_eq_i16:
+; NOBMI:       # %bb.0:
+; NOBMI-NEXT:    orl %edi, %esi
+; NOBMI-NEXT:    cmpw %si, %di
+; NOBMI-NEXT:    sete %al
+; NOBMI-NEXT:    retq
+;
+; BMI-LABEL: or_cmp_eq_i16:
+; BMI:       # %bb.0:
+; BMI-NEXT:    notl %edi
+; BMI-NEXT:    testw %si, %di
+; BMI-NEXT:    sete %al
+; BMI-NEXT:    retq
   %o = or i16 %x, %y
   %c = icmp eq i16 %x, %o
   ret i1 %c
 }
 
 define i1 @or_cmp_ne_i8(i8 zeroext %x, i8 zeroext %y) {
-; CHECK-LABEL: or_cmp_ne_i8:
-; CHECK:       # %bb.0:
-; CHECK-NEXT:    orl %esi, %edi
-; CHECK-NEXT:    cmpb %dil, %sil
-; CHECK-NEXT:    setne %al
-; CHECK-NEXT:    retq
+; NOBMI-LABEL: or_cmp_ne_i8:
+; NOBMI:       # %bb.0:
+; NOBMI-NEXT:    orl %esi, %edi
+; NOBMI-NEXT:    cmpb %dil, %sil
+; NOBMI-NEXT:    setne %al
+; NOBMI-NEXT:    retq
+;
+; BMI-LABEL: or_cmp_ne_i8:
+; BMI:       # %bb.0:
+; BMI-NEXT:    notb %sil
+; BMI-NEXT:    testb %dil, %sil
+; BMI-NEXT:    setne %al
+; BMI-NEXT:    retq
   %o = or i8 %x, %y
   %c = icmp ne i8 %y, %o
   ret i1 %c
 }
 
 ; Don't fold vectors.
 define <4 x i32> @or_cmp_eq_v4i32(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: or_cmp_eq_v4i32: