[DAGCombiner] convert and-of-seteq to bitwise logic+seteq (PR32401)

[spatel]

Summary

This is a generic combine to reduce icmp logic as discussed in:
https://bugs.llvm.org/show_bug.cgi?id=32401

I think these are all wins for targets in the affected tests, but a target could reverse this if it is not a win (or we can add a target hook to selectively disable this). A follow-up would allow us to canonicalize IR to the icmp form in instcombine.

I had initially enabled this for vectors too, but there were several regressions because of the scalar-limited constant matching in the combines above this one (and likely we're accidentally excluding vectors from folds that would reduce to those forms).

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3274

If you're going to do this, it would be nice to at least handle the inverse case: or(setne, setne). Not sure what other related cases are worth transforming.

test/CodeGen/ARM/and-setcc.ll

27 ↗

(On Diff #93419)

This isn't the shortest possible sequence; for example, gcc generates:

cmp     r0, r1
cmpeq   r2, r3
moveq   r0, #1
movne   r0, #0
bx      lr

Probably not worth worrying about, though.

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3274

Sure - I was planning to look at the related patterns in "visitORLike" as well as the vector cases as follow-ups. Would you prefer that I pull it together in one patch, or I can add another FIXME comment?

[efriedma]

Someone is inevitably going to request a target hook for this; the reason this transform looks good is that all the targets you have tests for require at least 3 instructions to lower seteq. If you have a one-instruction seteq operation, the seteq+seteq+and sequence is cheaper. (Not sure what targets have this for scalars, but a lot of targets have this for vectors, e.g. x86 pcmpeqd.)

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3274

It doesn't need to be in the same patch, as long as you don't forget about it.

[spatel]

Patch updated:

1. Add a target hook to selectively enable this transform.
2. Enable the hook for scalars on x86, PPC, and ARM.
3. Add the 'or' sibling fold (I did several NFC clean-up commits last week, so this could be added simply here).

[spatel]

test/CodeGen/PowerPC/setcc-logic.ll

454–456

I think this sequence is better than crand+isel, but another possibility:
https://bugs.llvm.org/show_bug.cgi?id=32520

[efriedma]

I'm not really familiar enough with PPC to comment on those changes. Otherwise LGTM.

[nemanjai]

I think the PPC changes look good.

test/CodeGen/PowerPC/setcc-logic.ll

454–456

This is in the pipeline:
https://reviews.llvm.org/D31240

include/llvm/Target/TargetLowering.h

public:
   /// into a single machine instruction of a form like:
   /// \code
   ///   cc = test %register, #mask
   /// \endcode
   virtual bool isMaskAndCmp0FoldingBeneficial(const Instruction &AndI) const {
     return false;
   }
 
+  /// Use bitwise logic to make pairs of compares more efficient. For example:
+  /// and (seteq A, B), (seteq C, D) --> seteq (or (xor A, B), (xor C, D)), 0
+  /// This should be true when it takes more than one instruction to lower
+  /// setcc (cmp+set on x86 scalar), when bitwise ops are faster than logic on
+  /// condition bits (crand on PowerPC), and/or when reducing cmp+br is a win.
+  virtual bool convertSetCCLogicToBitwiseLogic(EVT VT) const {
+    return false;
+  }
+
   /// Return the preferred operand type if the target has a quick way to compare
   /// integer values of the given size. Assume that any legal integer type can
   /// be compared efficiently. Targets may override this to allow illegal wide
   /// types to return a vector type if there is support to compare that type.
   virtual MVT hasFastEqualityCompare(unsigned NumBits) const {
     MVT VT = MVT::getIntegerVT(NumBits);
     return isTypeLegal(VT) ? VT : MVT::INVALID_SIMPLE_VALUE_TYPE;
   }

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (IsAnd && LL == RL && CC0 == CC1 && IsInteger && CC0 == ISD::SETNE &&
        (isAllOnesConstant(LR) && isNullConstant(RR)))) {
     SDValue One = DAG.getConstant(1, DL, OpVT);
     SDValue Two = DAG.getConstant(2, DL, OpVT);
     SDValue Add = DAG.getNode(ISD::ADD, SDLoc(N0), OpVT, LL, One);
     AddToWorklist(Add.getNode());
     return DAG.getSetCC(DL, VT, Add, Two, ISD::SETUGE);
   }
 
+  // Try more general transforms if the predicates match and the only user of
+  // the compares is the 'and' or 'or'.
+  if (IsInteger && TLI.convertSetCCLogicToBitwiseLogic(OpVT) && CC0 == CC1 &&
+      N0.hasOneUse() && N1.hasOneUse()) {
+    // and (seteq A, B), (seteq C, D) --> seteq (or (xor A, B), (xor C, D)), 0
+    // or  (setne A, B), (setne C, D) --> setne (or (xor A, B), (xor C, D)), 0
+    if ((IsAnd && CC1 == ISD::SETEQ) || (!IsAnd && CC1 == ISD::SETNE)) {
+      SDValue XorL = DAG.getNode(ISD::XOR, SDLoc(N0), OpVT, LL, LR);
+      SDValue XorR = DAG.getNode(ISD::XOR, SDLoc(N1), OpVT, RL, RR);
+      SDValue Or = DAG.getNode(ISD::OR, DL, OpVT, XorL, XorR);
+      SDValue Zero = DAG.getConstant(0, DL, OpVT);
+      return DAG.getSetCC(DL, VT, Or, Zero, CC1);
+    }
+  }
+
   // Canonicalize equivalent operands to LL == RL.
   if (LL == RR && LR == RL) {
     CC1 = ISD::getSetCCSwappedOperands(CC1);
     std::swap(RL, RR);
   }
 
   // (and (setcc X, Y, CC0), (setcc X, Y, CC1)) --> (setcc X, Y, NewCC)
   // (or  (setcc X, Y, CC0), (setcc X, Y, CC1)) --> (setcc X, Y, NewCC)
   if (LL == RL && LR == RR) {
     ISD::CondCode NewCC = IsAnd ? ISD::getSetCCAndOperation(CC0, CC1, IsInteger)

lib/Target/ARM/ARMISelLowering.h

public:
     bool canMergeStoresTo(EVT MemVT) const override {
       // Do not merge to larger than i32.
       return (MemVT.getSizeInBits() <= 32);
     }
 
     bool isCheapToSpeculateCttz() const override;
     bool isCheapToSpeculateCtlz() const override;
 
+    bool convertSetCCLogicToBitwiseLogic(EVT VT) const override {
+      return VT.isScalarInteger();
+    }
+
     bool supportSwiftError() const override {
       return true;
     }
 
     bool hasStandaloneRem(EVT VT) const override {
       return HasStandaloneRem;
     }
 

lib/Target/PowerPC/PPCISelLowering.h

public:
     bool isCtlzFast() const override {
       return true;
     }
 
     bool hasAndNotCompare(SDValue) const override {
       return true;
     }
 
+    bool convertSetCCLogicToBitwiseLogic(EVT VT) const override {
+      return VT.isScalarInteger();
+    }
+
     bool supportSplitCSR(MachineFunction *MF) const override {
       return
         MF->getFunction()->getCallingConv() == CallingConv::CXX_FAST_TLS &&
         MF->getFunction()->hasFnAttribute(Attribute::NoUnwind);
     }
 
     void initializeSplitCSR(MachineBasicBlock *Entry) const override;
 

lib/Target/X86/X86ISelLowering.h

bool isMultiStoresCheaperThanBitsMerge(EVT LTy, EVT HTy) const override {
       // such pair out until we get testcase to prove it is a win.
       return false;
     }
 
     bool isMaskAndCmp0FoldingBeneficial(const Instruction &AndI) const override;
 
     bool hasAndNotCompare(SDValue Y) const override;
 
+    bool convertSetCCLogicToBitwiseLogic(EVT VT) const override {
+      return VT.isScalarInteger();
+    }
+
     /// Vector-sized comparisons are fast using PCMPEQ + PMOVMSK or PTEST.
     MVT hasFastEqualityCompare(unsigned NumBits) const override;
 
     /// Return the value type to use for ISD::SETCC.
     EVT getSetCCResultType(const DataLayout &DL, LLVMContext &Context,
                            EVT VT) const override;
 
     /// Determine which of the bits specified in Mask are known to be either

test/CodeGen/ARM/setcc-logic.ll

; CHECK-NEXT:    bx lr
   ret i1 %and
 }
 
 ; PR32401 - https://bugs.llvm.org/show_bug.cgi?id=32401
 
 define zeroext i1 @and_eq(i32 %a, i32 %b, i32 %c, i32 %d) nounwind {
 ; CHECK-LABEL: and_eq:
 ; CHECK:       @ BB#0:
-; CHECK-NEXT:    cmp r2, r3
-; CHECK-NEXT:    mov r2, #0
-; CHECK-NEXT:    movweq r2, #1
-; CHECK-NEXT:    mov r12, #0
-; CHECK-NEXT:    cmp r0, r1
-; CHECK-NEXT:    movweq r12, #1
-; CHECK-NEXT:    and r0, r12, r2
+; CHECK-NEXT:    eor r2, r2, r3
+; CHECK-NEXT:    eor r0, r0, r1
+; CHECK-NEXT:    orrs r0, r0, r2
+; CHECK-NEXT:    mov r0, #0
+; CHECK-NEXT:    movweq r0, #1
 ; CHECK-NEXT:    bx lr
   %cmp1 = icmp eq i32 %a, %b
   %cmp2 = icmp eq i32 %c, %d
   %and = and i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 define zeroext i1 @or_ne(i32 %a, i32 %b, i32 %c, i32 %d) nounwind {
 ; CHECK-LABEL: or_ne:
 ; CHECK:       @ BB#0:
-; CHECK-NEXT:    cmp r2, r3
-; CHECK-NEXT:    mov r2, #0
-; CHECK-NEXT:    movwne r2, #1
-; CHECK-NEXT:    mov r12, #0
-; CHECK-NEXT:    cmp r0, r1
-; CHECK-NEXT:    movwne r12, #1
-; CHECK-NEXT:    orr r0, r12, r2
+; CHECK-NEXT:    eor r2, r2, r3
+; CHECK-NEXT:    eor r0, r0, r1
+; CHECK-NEXT:    orrs r0, r0, r2
+; CHECK-NEXT:    movwne r0, #1
 ; CHECK-NEXT:    bx lr
   %cmp1 = icmp ne i32 %a, %b
   %cmp2 = icmp ne i32 %c, %d
   %or = or i1 %cmp1, %cmp2
   ret i1 %or
 }
 
 define <4 x i1> @and_eq_vec(<4 x i32> %a, <4 x i32> %b, <4 x i32> %c, <4 x i32> %d) nounwind {

test/CodeGen/PowerPC/setcc-logic.ll

; CHECK-NEXT:    blr
   ret i1 %and
 }
 
 ; PR32401 - https://bugs.llvm.org/show_bug.cgi?id=32401
 
 define zeroext i1 @and_eq(i16 zeroext  %a, i16 zeroext %b, i16 zeroext %c, i16 zeroext %d) {
 ; CHECK-LABEL: and_eq:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    cmpw 0, 3, 4
-; CHECK-NEXT:    cmpw 1, 5, 6
-; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    crnand 20, 2, 6
-; CHECK-NEXT:    isel 3, 0, 3, 20
+; CHECK-NEXT:    xor 5, 5, 6
+; CHECK-NEXT:    xor 3, 3, 4
+; CHECK-NEXT:    or 3, 3, 5
+; CHECK-NEXT:    cntlzw 3, 3
+; CHECK-NEXT:    rlwinm 3, 3, 27, 31, 31
 ; CHECK-NEXT:    blr
   %cmp1 = icmp eq i16 %a, %b
   %cmp2 = icmp eq i16 %c, %d
   %and = and i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 define zeroext i1 @or_ne(i32 %a, i32 %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: or_ne:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    cmpw 0, 3, 4
-; CHECK-NEXT:    cmpw 1, 5, 6
-; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    crand 20, 6, 2
-; CHECK-NEXT:    isel 3, 0, 3, 20
+; CHECK-NEXT:    xor 5, 5, 6
+; CHECK-NEXT:    xor 3, 3, 4
+; CHECK-NEXT:    or 3, 3, 5
+; CHECK-NEXT:    cntlzw 3, 3
+; CHECK-NEXT:    nor 3, 3, 3
+; CHECK-NEXT:    rlwinm 3, 3, 27, 31, 31
 ; CHECK-NEXT:    blr
   %cmp1 = icmp ne i32 %a, %b
   %cmp2 = icmp ne i32 %c, %d
   %or = or i1 %cmp1, %cmp2
   ret i1 %or
 }
 
 ; This should not be transformed because vector compares + bitwise logic are faster.

test/CodeGen/X86/avx512-cmp.ll

entry:
   %0 = fcmp one double %x, %y
   %or = zext i1 %0 to i32
   ret i32 %or
 }
 
 define i32 @test8(i32 %a1, i32 %a2, i32 %a3) {
 ; ALL-LABEL: test8:
 ; ALL:       ## BB#0:
+; ALL-NEXT:    notl %edi
+; ALL-NEXT:    xorl $-2147483648, %esi ## imm = 0x80000000
 ; ALL-NEXT:    testl %edx, %edx
 ; ALL-NEXT:    movl $1, %eax
 ; ALL-NEXT:    cmovel %eax, %edx
-; ALL-NEXT:    cmpl $-2147483648, %esi ## imm = 0x80000000
-; ALL-NEXT:    cmovnel %edx, %eax
-; ALL-NEXT:    cmpl $-1, %edi
+; ALL-NEXT:    orl %edi, %esi
 ; ALL-NEXT:    cmovnel %edx, %eax
 ; ALL-NEXT:    retq
   %tmp1 = icmp eq i32 %a1, -1
   %tmp2 = icmp eq i32 %a2, -2147483648
   %tmp3 = and i1 %tmp1, %tmp2
   %tmp4 = icmp eq i32 %a3, 0
   %tmp5 = or i1 %tmp3, %tmp4
   %res = select i1 %tmp5, i32 1, i32 %a3

test/CodeGen/X86/setcc-logic.ll

; CHECK-NEXT:    retq
   ret i1 %and
 }
 
 ; PR32401 - https://bugs.llvm.org/show_bug.cgi?id=32401
 
 define zeroext i1 @and_eq(i8 %a, i8 %b, i8 %c, i8 %d) nounwind {
 ; CHECK-LABEL: and_eq:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    cmpb %sil, %dil
-; CHECK-NEXT:    sete %sil
-; CHECK-NEXT:    cmpb %cl, %dl
+; CHECK-NEXT:    xorl %esi, %edi
+; CHECK-NEXT:    xorl %ecx, %edx
+; CHECK-NEXT:    orb %dl, %dil
 ; CHECK-NEXT:    sete %al
-; CHECK-NEXT:    andb %sil, %al
 ; CHECK-NEXT:    retq
   %cmp1 = icmp eq i8 %a, %b
   %cmp2 = icmp eq i8 %c, %d
   %and = and i1 %cmp1, %cmp2
   ret i1 %and
 }
 
 define zeroext i1 @or_ne(i8 %a, i8 %b, i8 %c, i8 %d) nounwind {
 ; CHECK-LABEL: or_ne:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    cmpb %sil, %dil
-; CHECK-NEXT:    setne %sil
-; CHECK-NEXT:    cmpb %cl, %dl
+; CHECK-NEXT:    xorl %esi, %edi
+; CHECK-NEXT:    xorl %ecx, %edx
+; CHECK-NEXT:    orb %dl, %dil
 ; CHECK-NEXT:    setne %al
-; CHECK-NEXT:    orb %sil, %al
 ; CHECK-NEXT:    retq
   %cmp1 = icmp ne i8 %a, %b
   %cmp2 = icmp ne i8 %c, %d
   %or = or i1 %cmp1, %cmp2
   ret i1 %or
 }
 
 ; This should not be transformed because vector compares + bitwise logic are faster.