[X86] Improve (select carry C1+1 C1)

[kazu]

Summary

Without this patch:

return X < 4 ? 3 : 2;

return X < 9 ? 7 : 6;

are compiled as:

31 c0                   xor    %eax,%eax
83 ff 04                cmp    $0x4,%edi
0f 93 c0                setae  %al
83 f0 03                xor    $0x3,%eax

31 c0                   xor    %eax,%eax
83 ff 09                cmp    $0x9,%edi
0f 92 c0                setb   %al
83 c8 06                or     $0x6,%eax

respectively. With this patch, we generate:

31 c0                   xor    %eax,%eax
83 ff 04                cmp    $0x4,%edi
83 d0 02                adc    $0x2,%eax

31 c0                   xor    %eax,%eax
83 ff 04                cmp    $0x4,%edi
83 d0 02                adc    $0x2,%eax

respectively, saving 3 bytes while reducing the tree height.

This patch recognizes the equivalence of OR and ADD
(if bits do not overlap) and delegates to combineAddOrSubToADCOrSBB
for further processing. The same applies to the equivalence of XOR
and SUB.

[craig.topper]

llvm/lib/Target/X86/X86ISelLowering.cpp

50054

80 columns

[kazu]

Fixed formatting.

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

52553

This block of code is duplicated in CombineOr/CombineXor. Maybe add a helper?

static SDValue combineOrXorWithSETCC(SDNode *N, SDValue N0, SDValue N1) {
  // Delegate to combineAddOrSubToADCOrSBB if we have:
  //
  //   (xor/or (zero_extend (setcc)) imm)
  //
  // where imm has its LSB set, in which case the XOR is equivalent to SUB
  // with the operands swapped.
  SDLoc DL(N);
  if (N0.getOpcode() == ISD::ZERO_EXTEND && N0.hasOneUse() &&
      N0.getOperand(0).getOpcode() == X86ISD::SETCC) {
    if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1)) {
      bool N1COdd = N1C->getZExtValue() & 1;
      if (N->getOpcode() == ISD::OR ? !N1COdd : N1COdd) {
        if (SDValue R = combineAddOrSubToADCOrSBB(N->getOpcode() == ISD::XOR,
                                                  DL, VT, N1, N0, DAG))
          return R;
      }
    }
  }
}

llvm/test/CodeGen/X86/select_const.ll

548

Two things regarding the tests.

1. there should be some tests for the sbb case.
2. can you split this into two patches, one for adding the tests (w.o the code change to isellowering) and another with the isellowering changes so we can see the changes more easily.

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

49895

Instead of adding a forward declaration - could we not just move the 2 existing combineAddOrSubToADCOrSBB implementations up here as a NFC?

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

50051

Move hasOneUse() to the end of the checks - its a slow function and we should avoid it if we can.

if (N0.getOpcode() == ISD::ZERO_EXTEND &&
    N0.getOperand(0).getOpcode() == X86ISD::SETCC &&
    N0.hasOneUse()) {

52543

Move hasOneUse() to the end of the checks

[kazu]

Adjusted hasOneUsed.

Regenerated this patch relative to the pre-committed tests.

[kazu]

Regenerated a patch after moving up combineAddOrSubToADCOrSBB.

[kazu]

Thank you for all the feedback. Please take a look.

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

50105

assert((N->getOpcode() == ISD::OR || N->getOpcode() == ISD::XOR) && "Unexpected opcode");

50114

auto *N1C

[kazu]

Added an assert expecting XOR or OR.

Replaced ConstantSDNode* with auto*.

[kazu]

Please take a look. Thanks!

[kazu]

Please take a look. Thanks!

[goldstein.w.n]

llvm/lib/Target/X86/X86ISelLowering.cpp

50119

Do you need to check that N0 is getting zero-extended to the same VT as N1?

Also can you do sign-extend as well and swap sbb/adc?

[craig.topper]

llvm/lib/Target/X86/X86ISelLowering.cpp

50119

As long as N0 and N1 both are operands of the XOR/OR they should always have the same type. We don't allow mixed types on XOR/OR.

sign-extend wouldn't work because the X86ISD::SETCC node returns an i8 where bits 7:1 are 0. It corresponds to the SETcc instruction. So sign-extend would be sign extending bit 7 which isn't useful. It should have already been turned into zero-extend.

[kazu]

I think I've addressed all the feedback so far, but I am happy to address if there is more. Thanks!

[RKSimon]

LGTM with one minor

llvm/test/CodeGen/X86/select_const.ll

571–572

ugt3 ?

[kazu]

Fixed a typo in the test.

llvm/lib/Target/X86/X86ISelLowering.cpp

static SDValue foldMaskedMerge(SDNode *Node, SelectionDAG &DAG) {
   SDValue N00 = N0->getOperand(0);
   SDValue N01 = N0->getOperand(1);
   SDValue N10 = N1->getOperand(0);
   SDValue N11 = N1->getOperand(1);
   if (SDValue Result = foldMaskedMergeImpl(N00, N01, N10, N11, DL, DAG))
     return Result;
   if (SDValue Result = foldMaskedMergeImpl(N01, N00, N10, N11, DL, DAG))
     return Result;
   if (SDValue Result = foldMaskedMergeImpl(N10, N11, N00, N01, DL, DAG))
     return Result;
   if (SDValue Result = foldMaskedMergeImpl(N11, N10, N00, N01, DL, DAG))
     return Result;
   return SDValue();
 }
 
 /// If this is an add or subtract where one operand is produced by a cmp+setcc,
 /// then try to convert it to an ADC or SBB. This replaces TEST+SET+{ADD/SUB}
if ((IsSub && CC == X86::COND_NE && ConstantX->isZero()) ||
         (!IsSub && CC == X86::COND_E && ConstantX->isAllOnes())) {
       SDValue Zero = DAG.getConstant(0, DL, ZVT);
       SDVTList X86SubVTs = DAG.getVTList(ZVT, MVT::i32);
       SDValue Neg = DAG.getNode(X86ISD::SUB, DL, X86SubVTs, Zero, Z);
       return DAG.getNode(X86ISD::SETCC_CARRY, DL, VT,
                          DAG.getTargetConstant(X86::COND_B, DL, MVT::i8),
                          SDValue(Neg.getNode(), 1));
     }
 
     // cmp with 1 sets the carry flag when Z == 0, so create 0 or -1 using 'sbb'
     // with fake operands:
     //  0 - (Z == 0) --> sbb %eax, %eax, (cmp Z, 1)
     // -1 + (Z != 0) --> sbb %eax, %eax, (cmp Z, 1)
     if ((IsSub && CC == X86::COND_E && ConstantX->isZero()) ||
         (!IsSub && CC == X86::COND_NE && ConstantX->isAllOnes())) {
       SDValue One = DAG.getConstant(1, DL, ZVT);
       SDVTList X86SubVTs = DAG.getVTList(ZVT, MVT::i32);
       SDValue Cmp1 = DAG.getNode(X86ISD::SUB, DL, X86SubVTs, Z, One);
       return DAG.getNode(X86ISD::SETCC_CARRY, DL, VT,
                          DAG.getTargetConstant(X86::COND_B, DL, MVT::i8),
static SDValue combineAddOrSubToADCOrSBB(SDNode *N, SelectionDAG &DAG) {
   if (SDValue ADCOrSBB = combineAddOrSubToADCOrSBB(IsSub, DL, VT, X, Y, DAG))
     return ADCOrSBB;
 
   // Commute and try again (negate the result for subtracts).
   if (SDValue ADCOrSBB = combineAddOrSubToADCOrSBB(IsSub, DL, VT, Y, X, DAG)) {
     if (IsSub)
       ADCOrSBB =
           DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), ADCOrSBB);
     return ADCOrSBB;
   }
 
   return SDValue();
 }
 
+static SDValue combineOrXorWithSETCC(SDNode *N, SDValue N0, SDValue N1,
+                                     SelectionDAG &DAG) {
+  assert((N->getOpcode() == ISD::XOR || N->getOpcode() == ISD::OR) &&
+         "Unexpected opcode");
+
+  // Delegate to combineAddOrSubToADCOrSBB if we have:
+  //
+  //   (xor/or (zero_extend (setcc)) imm)
+  //
+  // where imm is odd if and only if we have xor, in which case the XOR/OR are
+  // equivalent to a SUB/ADD, respectively.
+  if (N0.getOpcode() == ISD::ZERO_EXTEND &&
+      N0.getOperand(0).getOpcode() == X86ISD::SETCC && N0.hasOneUse()) {
+    if (auto *N1C = dyn_cast<ConstantSDNode>(N1)) {
+      bool IsSub = N->getOpcode() == ISD::XOR;
+      bool N1COdd = N1C->getZExtValue() & 1;
+      if (IsSub ? N1COdd : !N1COdd) {
+        SDLoc DL(N);
+        EVT VT = N->getValueType(0);
+        if (SDValue R = combineAddOrSubToADCOrSBB(IsSub, DL, VT, N1, N0, DAG))
+          return R;
+      }
+    }
+  }
+
+  return SDValue();
+}
+
 static SDValue combineOr(SDNode *N, SelectionDAG &DAG,
                          TargetLowering::DAGCombinerInfo &DCI,
                          const X86Subtarget &Subtarget) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N->getValueType(0);
   SDLoc dl(N);
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
if (VT.isVector() && (VT.getScalarSizeInBits() % 8) == 0) {
     }
   }
 
   // We should fold "masked merge" patterns when `andn` is not available.
   if (!Subtarget.hasBMI() && VT.isScalarInteger() && VT != MVT::i1)
     if (SDValue R = foldMaskedMerge(N, DAG))
       return R;
 
+  if (SDValue R = combineOrXorWithSETCC(N, N0, N1, DAG))
+    return R;
+
   return SDValue();
 }
 
 /// Try to turn tests against the signbit in the form of:
 ///   XOR(TRUNCATE(SRL(X, size(X)-1)), 1)
 /// into:
 ///   SETGT(X, -1)
 static SDValue foldXorTruncShiftIntoCmp(SDNode *N, SelectionDAG &DAG) {
static SDValue combineFneg(SDNode *N, SelectionDAG &DAG,
   SDLoc DL(N);
 
   // Let legalize expand this if it isn't a legal type yet.
   if (!TLI.isTypeLegal(VT))
     return SDValue();
 
   // If we're negating a FMUL node on a target with FMA, then we can avoid the
   // use of a constant by performing (-0 - A*B) instead.
   // FIXME: Check rounding control flags as well once it becomes available.
   if (Arg.getOpcode() == ISD::FMUL && (SVT == MVT::f32 || SVT == MVT::f64) &&
       Arg->getFlags().hasNoSignedZeros() && Subtarget.hasAnyFMA()) {
     SDValue Zero = DAG.getConstantFP(0.0, DL, VT);
     SDValue NewNode = DAG.getNode(X86ISD::FNMSUB, DL, VT, Arg.getOperand(0),
                                   Arg.getOperand(1), Zero);
     return DAG.getBitcast(OrigVT, NewNode);
   }
 
   bool CodeSize = DAG.getMachineFunction().getFunction().hasOptSize();
   bool LegalOperations = !DCI.isBeforeLegalizeOps();
   if (SDValue NegArg =
           TLI.getNegatedExpression(Arg, DAG, LegalOperations, CodeSize))
     return DAG.getBitcast(OrigVT, NegArg);
 
   return SDValue();
 }
 
 SDValue X86TargetLowering::getNegatedExpression(SDValue Op, SelectionDAG &DAG,
if (SDValue R = combineXorSubCTLZ(N, DAG, Subtarget))
     return R;
 
   if (DCI.isBeforeLegalizeOps())
     return SDValue();
 
   if (SDValue SetCC = foldXor1SetCC(N, DAG))
     return SetCC;
 
+  if (SDValue R = combineOrXorWithSETCC(N, N0, N1, DAG))
+    return R;
+
   if (SDValue RV = foldXorTruncShiftIntoCmp(N, DAG))
     return RV;
 
   // Fold not(iX bitcast(vXi1)) -> (iX bitcast(not(vec))) for legal boolvecs.
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
   if (llvm::isAllOnesConstant(N1) && N0.getOpcode() == ISD::BITCAST &&
       N0.getOperand(0).getValueType().isVector() &&
       N0.getOperand(0).getValueType().getVectorElementType() == MVT::i1 &&

llvm/test/CodeGen/X86/select_const.ll

; CHECK-NEXT:    retq
   %f = select i1 undef, float 4.0, float %x
   ret float %f
 }
 
 define i32 @select_eq0_3_2(i32 %X) {
 ; CHECK-LABEL: select_eq0_3_2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    testl %edi, %edi
-; CHECK-NEXT:    sete %al
-; CHECK-NEXT:    orl $2, %eax
+; CHECK-NEXT:    cmpl $1, %edi
+; CHECK-NEXT:    adcl $2, %eax
 ; CHECK-NEXT:    retq
   %cmp = icmp eq i32 %X, 0
   %sel = select i1 %cmp, i32 3, i32 2
   ret i32 %sel
 }
 
 define i32 @select_ugt3_2_3(i32 %X) {
 ; CHECK-LABEL: select_ugt3_2_3:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl $4, %edi
-; CHECK-NEXT:    setae %al
-; CHECK-NEXT:    xorl $3, %eax
+; CHECK-NEXT:    adcl $2, %eax
 ; CHECK-NEXT:    retq
   %cmp = icmp ugt i32 %X, 3
   %sel = select i1 %cmp, i32 2, i32 3
   ret i32 %sel
 }
 
 define i32 @select_ult9_7_6(i32 %X) {
 ; CHECK-LABEL: select_ult9_7_6:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl $9, %edi
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orl $6, %eax
+; CHECK-NEXT:    adcl $6, %eax
 ; CHECK-NEXT:    retq
   %cmp = icmp ult i32 %X, 9
   %sel = select i1 %cmp, i32 7, i32 6
   ret i32 %sel
 }
 
 define i32 @select_ult2_2_3(i32 %X) {
 ; CHECK-LABEL: select_ult2_2_3:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl $2, %edi
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    xorl $3, %eax
+; CHECK-NEXT:    movl $3, %eax
+; CHECK-NEXT:    sbbl $0, %eax
 ; CHECK-NEXT:    retq
   %cmp = icmp ult i32 %X, 2
   %cond = select i1 %cmp, i32 2, i32 3
   ret i32 %cond
 }
 
-define i32 @select_ugt2_3_2(i32 %X) {
-; CHECK-LABEL: select_ugt2_3_2:
+define i32 @select_ugt3_3_2(i32 %X) {
+; CHECK-LABEL: select_ugt3_3_2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    cmpl $4, %edi
-; CHECK-NEXT:    setae %al
-; CHECK-NEXT:    orl $2, %eax
+; CHECK-NEXT:    movl $2, %eax
+; CHECK-NEXT:    sbbl $-1, %eax
 ; CHECK-NEXT:    retq
   %cmp.inv = icmp ugt i32 %X, 3
   %cond = select i1 %cmp.inv, i32 3, i32 2
   ret i32 %cond
 }