[X86] Attempt to fold EFLAGS into X86ISD::ADD/SUB ops

[RKSimon]

Summary

We already use combineAddOrSubToADCOrSBB to fold extended EFLAGS results into ISD::ADD/SUB ops as X86ISD::ADC/SBB carry ops.

This patch extends this to also fold EFLAGS results with X86ISD::ADD/SUB ops

[chfast]

Looks very nice, thanks.

[craig.topper]

llvm/lib/Target/X86/X86ISelLowering.cpp

52615

Since the ADD/SUB that is being replaced has flag users that might use the carry flag. Do all of the combines in combineAddOrSubToADCOrSBB produce the same value for the carry flag as the original ADD/SUB.

I'm not sure this one does

-1 + SETAE --> -1 + (!CF) --> CF ? -1 : 0 --> SBB %eax, %eax

But I admit I'm having a hard time thinking about it.

[RKSimon]

I can initially limit this to cases that create SBB $0, %REG patterns if you think it safer?

[RKSimon]

Restrict ADC/SBB folds to cases where the second op will be zero.

[craig.topper]

LGTM

llvm/lib/Target/X86/X86ISelLowering.cpp

 }
 
 /// 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}
 /// with CMP+{ADC, SBB}.
 /// Also try (ADD/SUB)+(AND(SRL,1)) bit extraction pattern with BT+{ADC, SBB}.
 static SDValue combineAddOrSubToADCOrSBB(bool IsSub, const SDLoc &DL, EVT VT,
                                          SDValue X, SDValue Y,
-                                         SelectionDAG &DAG) {
+                                         SelectionDAG &DAG,
+                                         bool ZeroSecondOpOnly = false) {
   if (!DAG.getTargetLoweringInfo().isTypeLegal(VT))
     return SDValue();
 
   // Look through a one-use zext.
   if (Y.getOpcode() == ISD::ZERO_EXTEND && Y.hasOneUse())
     Y = Y.getOperand(0);
 
   X86::CondCode CC;
   SDValue EFLAGS;
   if (Y.getOpcode() == X86ISD::SETCC && Y.hasOneUse()) {
     CC = (X86::CondCode)Y.getConstantOperandVal(0);
     EFLAGS = Y.getOperand(1);
   } else if (Y.getOpcode() == ISD::AND && isOneConstant(Y.getOperand(1)) &&
              Y.hasOneUse()) {
     EFLAGS = LowerAndToBT(Y, ISD::SETNE, DL, DAG, CC);
   }
 
   if (!EFLAGS)
     return SDValue();
 
   // If X is -1 or 0, then we have an opportunity to avoid constants required in
   // the general case below.
   auto *ConstantX = dyn_cast<ConstantSDNode>(X);
-  if (ConstantX) {
+  if (ConstantX && !ZeroSecondOpOnly) {
     if ((!IsSub && CC == X86::COND_AE && ConstantX->isAllOnes()) ||
         (IsSub && CC == X86::COND_B && ConstantX->isZero())) {
       // This is a complicated way to get -1 or 0 from the carry flag:
       // -1 + SETAE --> -1 + (!CF) --> CF ? -1 : 0 --> SBB %eax, %eax
       //  0 - SETB  -->  0 -  (CF) --> CF ? -1 : 0 --> SBB %eax, %eax
       return DAG.getNode(X86ISD::SETCC_CARRY, DL, VT,
                          DAG.getTargetConstant(X86::COND_B, DL, MVT::i8),
                          EFLAGS);
static SDValue combineAddOrSubToADCOrSBB(bool IsSub, const SDLoc &DL, EVT VT,
   if (CC == X86::COND_B) {
     // X + SETB Z --> adc X, 0
     // X - SETB Z --> sbb X, 0
     return DAG.getNode(IsSub ? X86ISD::SBB : X86ISD::ADC, DL,
                        DAG.getVTList(VT, MVT::i32), X,
                        DAG.getConstant(0, DL, VT), EFLAGS);
   }
 
+  if (ZeroSecondOpOnly)
+    return SDValue();
+
   if (CC == X86::COND_A) {
     // Try to convert COND_A into COND_B in an attempt to facilitate
     // materializing "setb reg".
     //
     // Do not flip "e > c", where "c" is a constant, because Cmp instruction
     // cannot take an immediate as its first operand.
     //
     if (EFLAGS.getOpcode() == X86ISD::SUB && EFLAGS.getNode()->hasOneUse() &&
static SDValue combineX86AddSub(SDNode *N, SelectionDAG &DAG,
                                 TargetLowering::DAGCombinerInfo &DCI) {
   assert((X86ISD::ADD == N->getOpcode() || X86ISD::SUB == N->getOpcode()) &&
          "Expected X86ISD::ADD or X86ISD::SUB");
 
   SDLoc DL(N);
   SDValue LHS = N->getOperand(0);
   SDValue RHS = N->getOperand(1);
   MVT VT = LHS.getSimpleValueType();
-  unsigned GenericOpc = X86ISD::ADD == N->getOpcode() ? ISD::ADD : ISD::SUB;
+  bool IsSub = X86ISD::SUB == N->getOpcode();
+  unsigned GenericOpc = IsSub ? ISD::SUB : ISD::ADD;
 
   // If we don't use the flag result, simplify back to a generic ADD/SUB.
   if (!N->hasAnyUseOfValue(1)) {
     SDValue Res = DAG.getNode(GenericOpc, DL, VT, LHS, RHS);
     return DAG.getMergeValues({Res, DAG.getConstant(0, DL, MVT::i32)}, DL);
   }
 
   // Fold any similar generic ADD/SUB opcodes to reuse this node.
   auto MatchGeneric = [&](SDValue N0, SDValue N1, bool Negate) {
     SDValue Ops[] = {N0, N1};
     SDVTList VTs = DAG.getVTList(N->getValueType(0));
     if (SDNode *GenericAddSub = DAG.getNodeIfExists(GenericOpc, VTs, Ops)) {
       SDValue Op(N, 0);
       if (Negate)
         Op = DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), Op);
       DCI.CombineTo(GenericAddSub, Op);
     }
   };
   MatchGeneric(LHS, RHS, false);
   MatchGeneric(RHS, LHS, X86ISD::SUB == N->getOpcode());
 
-  return SDValue();
+  // TODO: Can we drop the ZeroSecondOpOnly limit? This is to guarantee that the
+  // EFLAGS result doesn't change.
+  return combineAddOrSubToADCOrSBB(IsSub, DL, VT, LHS, RHS, DAG,
+                                   /*ZeroSecondOpOnly*/ true);
 }
 
 static SDValue combineSBB(SDNode *N, SelectionDAG &DAG) {
   SDValue LHS = N->getOperand(0);
   SDValue RHS = N->getOperand(1);
   SDValue BorrowIn = N->getOperand(2);
 
   if (SDValue Flags = combineCarryThroughADD(BorrowIn, DAG)) {

llvm/test/CodeGen/X86/add-sub-bool.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown | FileCheck %s --check-prefixes=X86
-; RUN: llc < %s -mtriple=x86_64-unknown | FileCheck %s --check-prefixes=X64,NOTBM
-; RUN: llc < %s -mtriple=x86_64-unknown -mattr=+tbm | FileCheck %s --check-prefixes=X64,TBM
+; RUN: llc < %s -mtriple=x86_64-unknown | FileCheck %s --check-prefixes=X64
+; RUN: llc < %s -mtriple=x86_64-unknown -mattr=+tbm | FileCheck %s --check-prefixes=X64
 
 ; PR35908 - Fold ADD/SUB and bit extracts into ADC/SBB+BT
 ;
 ; int test_add_add(int x, int y, int z) { return ((x + y) + bool(z & (1 << 30))); }
 ; int test_add_sub(int x, int y, int z) { return ((x - y) + bool(z & (1 << 30))); }
 ; int test_sub_add(int x, int y, int z) { return ((x + y) - bool(z & (1 << 30))); }
 ; int test_sub_sub(int x, int y, int z) { return (x - (y - bool(z & (1 << 30)))); }
 
; X64-NEXT:    retq
   %mask = and i24 %shift, 1
   %add1 = add i24 %add, %mask
   ret i24 %add1
 }
 
 define i128 @test_i128_add_add_idx(i128 %x, i128 %y, i128 %z) nounwind {
 ; X86-LABEL: test_i128_add_add_idx:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %ebx
 ; X86-NEXT:    pushl %edi
 ; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
-; X86-NEXT:    addl {{[0-9]+}}(%esp), %ebx
+; X86-NEXT:    addl {{[0-9]+}}(%esp), %esi
 ; X86-NEXT:    adcl {{[0-9]+}}(%esp), %edi
-; X86-NEXT:    adcl {{[0-9]+}}(%esp), %esi
+; X86-NEXT:    adcl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    adcl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    shrl $5, %edx
-; X86-NEXT:    andl $1, %edx
-; X86-NEXT:    addl %ebx, %edx
-; X86-NEXT:    adcl $0, %edi
+; X86-NEXT:    btl $5, {{[0-9]+}}(%esp)
 ; X86-NEXT:    adcl $0, %esi
+; X86-NEXT:    adcl $0, %edi
+; X86-NEXT:    adcl $0, %edx
 ; X86-NEXT:    adcl $0, %ecx
-; X86-NEXT:    movl %edx, (%eax)
 ; X86-NEXT:    movl %edi, 4(%eax)
-; X86-NEXT:    movl %esi, 8(%eax)
+; X86-NEXT:    movl %esi, (%eax)
+; X86-NEXT:    movl %edx, 8(%eax)
 ; X86-NEXT:    movl %ecx, 12(%eax)
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    popl %edi
-; X86-NEXT:    popl %ebx
 ; X86-NEXT:    retl $4
 ;
-; NOTBM-LABEL: test_i128_add_add_idx:
-; NOTBM:       # %bb.0:
-; NOTBM-NEXT:    movq %r9, %rax
-; NOTBM-NEXT:    addq %rdx, %rdi
-; NOTBM-NEXT:    adcq %rcx, %rsi
-; NOTBM-NEXT:    shrl $5, %eax
-; NOTBM-NEXT:    andl $1, %eax
-; NOTBM-NEXT:    addq %rdi, %rax
-; NOTBM-NEXT:    adcq $0, %rsi
-; NOTBM-NEXT:    movq %rsi, %rdx
-; NOTBM-NEXT:    retq
-;
-; TBM-LABEL: test_i128_add_add_idx:
-; TBM:       # %bb.0:
-; TBM-NEXT:    addq %rdx, %rdi
-; TBM-NEXT:    adcq %rcx, %rsi
-; TBM-NEXT:    bextrl $261, %r9d, %eax # imm = 0x105
-; TBM-NEXT:    addq %rdi, %rax
-; TBM-NEXT:    adcq $0, %rsi
-; TBM-NEXT:    movq %rsi, %rdx
-; TBM-NEXT:    retq
+; X64-LABEL: test_i128_add_add_idx:
+; X64:       # %bb.0:
+; X64-NEXT:    movq %rdi, %rax
+; X64-NEXT:    addq %rdx, %rax
+; X64-NEXT:    adcq %rcx, %rsi
+; X64-NEXT:    btl $5, %r9d
+; X64-NEXT:    adcq $0, %rax
+; X64-NEXT:    adcq $0, %rsi
+; X64-NEXT:    movq %rsi, %rdx
+; X64-NEXT:    retq
   %add = add i128 %y, %x
   %shift = lshr i128 %z, 69
   %mask = and i128 %shift, 1
   %add1 = add i128 %add, %mask
   ret i128 %add1
 }
 
 define i32 @test_i32_add_sub_idx(i32 %x, i32 %y, i32 %z) nounwind {

llvm/test/CodeGen/X86/addcarry.ll

; CHECK-NEXT:    retq
     ret { i64, i1 } %ret
 }
 
 ; negative test for combineCarryDiamond(): uaddo mixed with usubo
 define { i64, i64, i1 } @addcarry_mixed_2x64(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 ; CHECK-LABEL: addcarry_mixed_2x64:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    xorl %edi, %edi
-; CHECK-NEXT:    addq %rdx, %rax
-; CHECK-NEXT:    setb %dil
 ; CHECK-NEXT:    addq %rcx, %rsi
-; CHECK-NEXT:    setb %dl
-; CHECK-NEXT:    subq %rdi, %rsi
+; CHECK-NEXT:    setb %dil
+; CHECK-NEXT:    addq %rdx, %rax
+; CHECK-NEXT:    sbbq $0, %rsi
 ; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %dl, %cl
+; CHECK-NEXT:    orb %dil, %cl
 ; CHECK-NEXT:    movq %rsi, %rdx
 ; CHECK-NEXT:    retq
   %t0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
   %s0 = extractvalue { i64, i1 } %t0, 0
   %k0 = extractvalue { i64, i1 } %t0, 1
 
   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
   %s1 = extractvalue { i64, i1 } %t1, 0

llvm/test/CodeGen/X86/combine-sbb.ll

 
 declare  { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32)
 
 %WideUInt64 = type { i64, i64 }
 
 define void @PR25858_i64(%WideUInt64* sret(%WideUInt64), %WideUInt64*, %WideUInt64*) nounwind {
 ; X86-LABEL: PR25858_i64:
 ; X86:       # %bb.0: # %top
-; X86-NEXT:    pushl %ebp
 ; X86-NEXT:    pushl %ebx
 ; X86-NEXT:    pushl %edi
 ; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %esi
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %ebx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
-; X86-NEXT:    movl (%edi), %ecx
-; X86-NEXT:    movl 4(%edi), %edx
-; X86-NEXT:    subl (%esi), %ecx
-; X86-NEXT:    sbbl 4(%esi), %edx
-; X86-NEXT:    setb %bl
-; X86-NEXT:    movl 12(%edi), %ebp
+; X86-NEXT:    movl (%edi), %edx
+; X86-NEXT:    movl 4(%edi), %esi
+; X86-NEXT:    movl 12(%edi), %ecx
 ; X86-NEXT:    movl 8(%edi), %edi
-; X86-NEXT:    subl 8(%esi), %edi
-; X86-NEXT:    sbbl 12(%esi), %ebp
-; X86-NEXT:    movzbl %bl, %esi
-; X86-NEXT:    subl %esi, %edi
-; X86-NEXT:    sbbl $0, %ebp
-; X86-NEXT:    movl %ecx, (%eax)
-; X86-NEXT:    movl %edx, 4(%eax)
+; X86-NEXT:    subl 8(%ebx), %edi
+; X86-NEXT:    sbbl 12(%ebx), %ecx
+; X86-NEXT:    subl (%ebx), %edx
+; X86-NEXT:    sbbl 4(%ebx), %esi
+; X86-NEXT:    sbbl $0, %edi
+; X86-NEXT:    sbbl $0, %ecx
+; X86-NEXT:    movl %edx, (%eax)
+; X86-NEXT:    movl %esi, 4(%eax)
 ; X86-NEXT:    movl %edi, 8(%eax)
-; X86-NEXT:    movl %ebp, 12(%eax)
+; X86-NEXT:    movl %ecx, 12(%eax)
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    popl %edi
 ; X86-NEXT:    popl %ebx
-; X86-NEXT:    popl %ebp
 ; X86-NEXT:    retl $4
 ;
 ; X64-LABEL: PR25858_i64:
 ; X64:       # %bb.0: # %top
 ; X64-NEXT:    movq %rdi, %rax
 ; X64-NEXT:    movq (%rsi), %rcx
 ; X64-NEXT:    movq 8(%rsi), %rsi
 ; X64-NEXT:    subq (%rdx), %rcx

llvm/test/CodeGen/X86/subcarry.ll

; CHECK-NEXT:    retq
   ret { i64, i64, i1 } %r
 }
 
 ; basic test for combineCarryDiamond() with add operands reversed
 define { i64, i64, i1 } @subcarry_2x64_add_reversed(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 ; CHECK-LABEL: subcarry_2x64_add_reversed:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    xorl %edi, %edi
+; CHECK-NEXT:    movq %rsi, %rdi
+; CHECK-NEXT:    subq %rcx, %rdi
 ; CHECK-NEXT:    subq %rdx, %rax
-; CHECK-NEXT:    setb %dil
-; CHECK-NEXT:    movq %rsi, %rdx
-; CHECK-NEXT:    subq %rcx, %rdx
-; CHECK-NEXT:    subq %rdi, %rdx
-; CHECK-NEXT:    setb %dil
+; CHECK-NEXT:    sbbq $0, %rdi
+; CHECK-NEXT:    setb %r8b
 ; CHECK-NEXT:    cmpq %rcx, %rsi
-; CHECK-NEXT:    adcb $0, %dil
-; CHECK-NEXT:    movl %edi, %ecx
+; CHECK-NEXT:    adcb $0, %r8b
+; CHECK-NEXT:    movq %rdi, %rdx
+; CHECK-NEXT:    movl %r8d, %ecx
 ; CHECK-NEXT:    retq
   %t0 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %x0, i64 %y0)
   %s0 = extractvalue { i64, i1 } %t0, 0
   %k0 = extractvalue { i64, i1 } %t0, 1
 
   %t1 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %x1, i64 %y1)
   %s1 = extractvalue { i64, i1 } %t1, 0
   %k1 = extractvalue { i64, i1 } %t1, 1

 %uint256 = type { %uint128, %uint128 }
 
 ; The 256-bit subtraction implementation using two inlined usubo procedures for U128 type { i64, i64 }.
 ; This is similar to how LLVM legalize types in CodeGen.
 define void @sub_U256_without_i128_or_recursive(%uint256* sret(%uint256) %0, %uint256* %1, %uint256* %2) nounwind {
 ; CHECK-LABEL: sub_U256_without_i128_or_recursive:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    movq (%rsi), %r9
-; CHECK-NEXT:    movq 8(%rsi), %r10
-; CHECK-NEXT:    subq (%rdx), %r9
-; CHECK-NEXT:    sbbq 8(%rdx), %r10
-; CHECK-NEXT:    setb %r8b
+; CHECK-NEXT:    movq (%rsi), %r8
+; CHECK-NEXT:    movq 8(%rsi), %r9
 ; CHECK-NEXT:    movq 16(%rsi), %rcx
 ; CHECK-NEXT:    movq 24(%rsi), %rsi
 ; CHECK-NEXT:    xorl %edi, %edi
 ; CHECK-NEXT:    subq 16(%rdx), %rcx
 ; CHECK-NEXT:    setb %dil
 ; CHECK-NEXT:    subq 24(%rdx), %rsi
-; CHECK-NEXT:    movzbl %r8b, %edx
-; CHECK-NEXT:    subq %rdx, %rcx
+; CHECK-NEXT:    subq (%rdx), %r8
+; CHECK-NEXT:    sbbq 8(%rdx), %r9
+; CHECK-NEXT:    sbbq $0, %rcx
 ; CHECK-NEXT:    sbbq %rdi, %rsi
-; CHECK-NEXT:    movq %r9, (%rax)
-; CHECK-NEXT:    movq %r10, 8(%rax)
+; CHECK-NEXT:    movq %r8, (%rax)
+; CHECK-NEXT:    movq %r9, 8(%rax)
 ; CHECK-NEXT:    movq %rcx, 16(%rax)
 ; CHECK-NEXT:    movq %rsi, 24(%rax)
 ; CHECK-NEXT:    retq
   %4 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 0
   %5 = load i64, i64* %4, align 8
   %6 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 1
   %7 = load i64, i64* %6, align 8
   %8 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 0
; CHECK-NEXT:    retq
   %41 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 1, i32 1
   store i64 %37, i64* %41, align 8
   ret void
 }
 
 define i1 @subcarry_ult_2x64(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 ; CHECK-LABEL: subcarry_ult_2x64:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    cmpq %rdx, %rdi
-; CHECK-NEXT:    setb %al
 ; CHECK-NEXT:    subq %rcx, %rsi
 ; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    cmpq %rax, %rsi
+; CHECK-NEXT:    cmpq %rdx, %rdi
+; CHECK-NEXT:    sbbq $0, %rsi
 ; CHECK-NEXT:    setb %al
 ; CHECK-NEXT:    orb %cl, %al
 ; CHECK-NEXT:    retq
   %b0 = icmp ult i64 %x0, %y0
   %d1 = sub i64 %x1, %y1
   %b10 = icmp ult i64 %x1, %y1
   %b0z = zext i1 %b0 to i64
   %b11 = icmp ult i64 %d1, %b0z
   %b1 = or i1 %b10, %b11
   ret i1 %b1
 }