[X86] Make `(and/or (icmp eq/ne A,C0), (icmp eq/ne A,C1))` where `IsPow2(dif(C0,C1))` work for more patterns.

[goldstein.w.n]

Summary

(and/or (icmp eq/ne A,C0), (icmp eq/ne A,C1)) can be lowered to
(icmp eq/ne (and (sub A, (smin C0, C1)), (not (sub (smax C0, C1), (smin C0, C1)))), 0)
generically if (sub (smax C0, C1), (smin C0,C1)) is a power of 2.

This covers the existing case of (and/or (icmp eq/ne A, C_Pow2),(icmp eq/ne A, -C_Pow2))
as well as other cases.

Alive2 Links:
EQ: https://alive2.llvm.org/ce/z/mLJiUW
NE: https://alive2.llvm.org/ce/z/TKnzUr

[pengfei]

llvm/test/CodeGen/X86/icmp-pow2-dif.ll

310–311

Should the name be addand? Same for below.

[goldstein.w.n]

Rebase

[goldstein.w.n]

addadd -> addand

[goldstein.w.n]

Comment on intentional failures

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[RKSimon]

foobar?

[RKSimon]

LGTM

[goldstein.w.n]

In D144283#4149117, @RKSimon wrote:

foobar?

Was left from an earlier rebase. commit message has already been fixed.

[goldstein.w.n]

Rebase

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

static SDValue foldAndOrOfSETCC(SDNode *LogicOp, SelectionDAG &DAG) {
   ISD::CondCode CCL = cast<CondCodeSDNode>(LHS.getOperand(2))->get();
   ISD::CondCode CCR = cast<CondCodeSDNode>(RHS.getOperand(2))->get();
 
   SDValue LHS0 = LHS->getOperand(0);
   SDValue RHS0 = RHS->getOperand(0);
   SDValue LHS1 = LHS->getOperand(1);
   SDValue RHS1 = RHS->getOperand(1);
 
-  // TODO: We don't actually need a splat here, for vectors we just need
-  // LaneLHS[N] == -LaneRHS[N];
+  // TODO: We don't actually need a splat here, for vectors we just need the
+  // invariants to hold for each element.
   auto *LHS1C = isConstOrConstSplat(LHS1);
   auto *RHS1C = isConstOrConstSplat(RHS1);
 
   EVT VT = LogicOp->getValueType(0);
   EVT OpVT = LHS0.getValueType();
   SDLoc DL(LogicOp);
 
   if (CCL == CCR &&
       CCL == (LogicOp->getOpcode() == ISD::AND ? ISD::SETNE : ISD::SETEQ) &&
       LHS0 == RHS0 && LHS1C && RHS1C && OpVT.isInteger() && LHS.hasOneUse() &&
-      RHS.hasOneUse() && LHS1C->getAPIntValue() == (-RHS1C->getAPIntValue())) {
+      RHS.hasOneUse()) {
+    const APInt &APLhs = LHS1C->getAPIntValue();
+    const APInt &APRhs = RHS1C->getAPIntValue();
 
     // Preference is to use ISD::ABS or we already have an ISD::ABS (in which
     // case this is just a compare).
-    if (TargetPreference == AndOrSETCCFoldKind::ABS ||
-        DAG.doesNodeExist(ISD::ABS, DAG.getVTList(OpVT), {LHS0})) {
-      APInt C = LHS1C->getAPIntValue();
-      if (C.isNegative())
-        C = RHS1C->getAPIntValue();
+    if (APLhs == (-APRhs) &&
+        (TargetPreference == AndOrSETCCFoldKind::ABS ||
+         DAG.doesNodeExist(ISD::ABS, DAG.getVTList(OpVT), {LHS0}))) {
+      const APInt &C = APLhs.isNegative() ? APRhs : APLhs;
       // (icmp eq A, C) | (icmp eq A, -C)
       //    -> (icmp eq Abs(A), C)
       // (icmp ne A, C) & (icmp ne A, -C)
       //    -> (icmp ne Abs(A), C)
       SDValue AbsOp = DAG.getNode(ISD::ABS, DL, OpVT, LHS0);
       return DAG.getNode(ISD::SETCC, DL, VT, AbsOp,
                          DAG.getConstant(C, DL, OpVT), LHS.getOperand(2));
     } else if (TargetPreference == AndOrSETCCFoldKind::AddAnd) {
-      // With C as a power of 2 and C != 0 and C != INT_MIN:
-      //   (icmp eq A, C) | (icmp eq A, -C)
-      //        -> (icmp eq and(add(A, C), ~(C + C)), 0)
-      //   (icmp ne A, C) & (icmp ne A, -C)w
-      //        -> (icmp ne and(add(A, C), ~(C + C)), 0)
-      const ConstantSDNode *Pow2 = nullptr;
-      if (LHS1C->getAPIntValue().isPowerOf2())
-        Pow2 = LHS1C;
-      else if (RHS1C->getAPIntValue().isPowerOf2())
-        Pow2 = RHS1C;
-      // isPowerOf2 is only for non-zero powers of 2.
-      if (Pow2 != nullptr && !Pow2->getAPIntValue().isMinSignedValue()) {
-        const APInt &C = Pow2->getAPIntValue();
-        SDValue AddOp =
-            DAG.getNode(ISD::ADD, DL, OpVT, LHS0, DAG.getConstant(C, DL, OpVT));
+      // A == C0 | A == C1
+      //  IF IsPow2(smax(C0, C1)-smin(C0, C1))
+      //    -> ((A - smin(C0, C1)) & ~(smax(C0, C1)-smin(C0, C1))) == 0
+      // A != C0 & A != C1
+      //  IF IsPow2(smax(C0, C1)-smin(C0, C1))
+      //    -> ((A - smin(C0, C1)) & ~(smax(C0, C1)-smin(C0, C1))) != 0
+      const APInt &MaxC = APIntOps::smax(APRhs, APLhs);
+      const APInt &MinC = APIntOps::smin(APRhs, APLhs);
+      APInt Dif = MaxC - MinC;
+      if (!Dif.isZero() && Dif.isPowerOf2()) {
+        SDValue AddOp = DAG.getNode(ISD::ADD, DL, OpVT, LHS0,
+                                    DAG.getConstant(-MinC, DL, OpVT));
         SDValue AndOp = DAG.getNode(ISD::AND, DL, OpVT, AddOp,
-                                    DAG.getConstant(~(C + C), DL, OpVT));
+                                    DAG.getConstant(~Dif, DL, OpVT));
         return DAG.getNode(ISD::SETCC, DL, VT, AndOp,
                            DAG.getConstant(0, DL, OpVT), LHS.getOperand(2));
       }
     }
   }
 
   return SDValue();
 }

llvm/test/CodeGen/X86/icmp-pow2-dif.ll

 ; CHECK-NEXT:    testl $-1073741825, %edi # imm = 0xBFFFFFFF
 ; CHECK-NEXT:    setne %al
 ; CHECK-NEXT:    retq
   %cmp1 = icmp ne i32 %x, -1
   %cmp2 = icmp ne i32 %x, -1073741825
   %r = and i1 %cmp1, %cmp2
   ret i1 %r
 }
 
 define i1 @addand_ne_i16(i16 %x) nounwind {
 ; CHECK-LABEL: addand_ne_i16:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    cmpw $-3, %di
-; CHECK-NEXT:    setne %cl
-; CHECK-NEXT:    movzwl %di, %eax
-; CHECK-NEXT:    cmpl $16381, %eax # imm = 0x3FFD
+; CHECK-NEXT:    addl $3, %edi
+; CHECK-NEXT:    testl $49151, %edi # imm = 0xBFFF
 ; CHECK-NEXT:    setne %al
-; CHECK-NEXT:    andb %cl, %al
 ; CHECK-NEXT:    retq
   %cmp1 = icmp ne i16 %x, -3
   %cmp2 = icmp ne i16 %x, 16381
   %r = and i1 %cmp1, %cmp2
   ret i1 %r
 }
 
 ; Intentional negative test.
; SSE-NEXT:    retq
   %cmp2 = icmp ne <8 x i16> %x, <i16 16381, i16 16381, i16 16381, i16 16381, i16 16381, i16 16381, i16 16381, i16 16381>
   %r = and <8 x i1> %cmp1, %cmp2
   ret <8 x i1> %r
 }
 
 define i1 @addand_eq_i32(i32 %x) nounwind {
 ; CHECK-LABEL: addand_eq_i32:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    cmpl $-1, %edi
-; CHECK-NEXT:    sete %cl
-; CHECK-NEXT:    cmpl $7, %edi
+; CHECK-NEXT:    incl %edi
+; CHECK-NEXT:    testl $-9, %edi
 ; CHECK-NEXT:    sete %al
-; CHECK-NEXT:    orb %cl, %al
 ; CHECK-NEXT:    retq
   %cmp1 = icmp eq i32 %x, -1
   %cmp2 = icmp eq i32 %x, 7
   %r = or i1 %cmp1, %cmp2
   ret i1 %r
 }
 
 ; Intentional negative test.
; CHECK-NEXT:    retq
   %cmp2 = icmp eq i8 %x, -8
   %r = or i1 %cmp1, %cmp2
   ret i1 %r
 }
 
 define i1 @addand_ne_i8(i8 %x) nounwind {
 ; CHECK-LABEL: addand_ne_i8:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    cmpb $59, %dil
-; CHECK-NEXT:    setne %cl
-; CHECK-NEXT:    cmpb $-5, %dil
+; CHECK-NEXT:    addb $5, %dil
+; CHECK-NEXT:    testb $-65, %dil
 ; CHECK-NEXT:    setne %al
-; CHECK-NEXT:    andb %cl, %al
 ; CHECK-NEXT:    retq
   %cmp1 = icmp ne i8 %x, 59
   %cmp2 = icmp ne i8 %x, -5
   %r = and i1 %cmp1, %cmp2
   ret i1 %r
 }
 
 ; Intentional negative test.
; CHECK-NEXT:    retq
   %cmp2 = icmp ne i64 %x, -17
   %r = and i1 %cmp1, %cmp2
   ret i1 %r
 }
 
 define i1 @addand_eq_i64(i64 %x) nounwind {
 ; CHECK-LABEL: addand_eq_i64:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    cmpq $768, %rdi # imm = 0x300
-; CHECK-NEXT:    setne %cl
-; CHECK-NEXT:    cmpq $-256, %rdi
+; CHECK-NEXT:    addq $256, %rdi # imm = 0x100
+; CHECK-NEXT:    testq $-1025, %rdi # imm = 0xFBFF
 ; CHECK-NEXT:    setne %al
-; CHECK-NEXT:    andb %cl, %al
 ; CHECK-NEXT:    retq
   %cmp1 = icmp ne i64 %x, 768
   %cmp2 = icmp ne i64 %x, -256
   %r = and i1 %cmp1, %cmp2
   ret i1 %r
 }

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

; CHECK-NEXT:    retq
   %c = or <4 x i1> %a, %b
   ret <4 x i1> %c
 }
 
 define zeroext i1 @ne_neg1_and_ne_zero(i64 %x) nounwind {
 ; CHECK-LABEL: ne_neg1_and_ne_zero:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    incq %rdi
-; CHECK-NEXT:    cmpq $2, %rdi
-; CHECK-NEXT:    setae %al
+; CHECK-NEXT:    testq $-2, %rdi
+; CHECK-NEXT:    setne %al
 ; CHECK-NEXT:    retq
   %cmp1 = icmp ne i64 %x, -1
   %cmp2 = icmp ne i64 %x, 0
   %and = and i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 ; PR32401 - https://bugs.llvm.org/show_bug.cgi?id=32401