[X86] combineCarryThroughADD - recognise X86ISD::ADD(AND(X,1),-1) pattern can be folded to X86ISD::BT

[RKSimon]

Summary

As mentioned on D122482, if we've generated a masked overflow test see if we can fold it to X86ISD::BT to feed a X86ISD::ADC/SBB

[RKSimon]

cleanup type legalization for BT nodes

[RKSimon]

rebase

[RKSimon]

rebase

[craig.topper]

LGTM

llvm/lib/Target/X86/X86ISelLowering.cpp

 }
 
 // When legalizing carry, we create carries via add X, -1
 // If that comes from an actual carry, via setcc, we use the
 // carry directly.
 static SDValue combineCarryThroughADD(SDValue EFLAGS, SelectionDAG &DAG) {
   if (EFLAGS.getOpcode() == X86ISD::ADD) {
     if (isAllOnesConstant(EFLAGS.getOperand(1))) {
+      bool FoundAndLSB = false;
       SDValue Carry = EFLAGS.getOperand(0);
       while (Carry.getOpcode() == ISD::TRUNCATE ||
              Carry.getOpcode() == ISD::ZERO_EXTEND ||
              (Carry.getOpcode() == ISD::AND &&
-              isOneConstant(Carry.getOperand(1))))
+              isOneConstant(Carry.getOperand(1)))) {
+        FoundAndLSB |= Carry.getOpcode() == ISD::AND;
         Carry = Carry.getOperand(0);
+      }
       if (Carry.getOpcode() == X86ISD::SETCC ||
           Carry.getOpcode() == X86ISD::SETCC_CARRY) {
         // TODO: Merge this code with equivalent in combineAddOrSubToADCOrSBB?
         uint64_t CarryCC = Carry.getConstantOperandVal(0);
         SDValue CarryOp1 = Carry.getOperand(1);
         if (CarryCC == X86::COND_B)
           return CarryOp1;
         if (CarryCC == X86::COND_A) {
if (isAllOnesConstant(EFLAGS.getOperand(1))) {
           }
         }
         // If this is a check of the z flag of an add with 1, switch to the
         // C flag.
         if (CarryCC == X86::COND_E &&
             CarryOp1.getOpcode() == X86ISD::ADD &&
             isOneConstant(CarryOp1.getOperand(1)))
           return CarryOp1;
+      } else if (FoundAndLSB) {
+        SDLoc DL(Carry);
+        SDValue BitNo = DAG.getConstant(0, DL, Carry.getValueType());
+        if (Carry.getOpcode() == ISD::SRL) {
+          BitNo = Carry.getOperand(1);
+          Carry = Carry.getOperand(0);
+        }
+        if (Carry.getScalarValueSizeInBits() < 32)
+          Carry = DAG.getNode(ISD::ANY_EXTEND, DL, MVT::i32, Carry);
+        EVT CarryVT = Carry.getValueType();
+        if (DAG.getTargetLoweringInfo().isTypeLegal(CarryVT)) {
+          if (CarryVT != BitNo.getValueType())
+            BitNo = DAG.getNode(ISD::ANY_EXTEND, DL, CarryVT, BitNo);
+          return DAG.getNode(X86ISD::BT, DL, MVT::i32, Carry, BitNo);
+        }
       }
     }
   }
 
   return SDValue();
 }
 
 /// If we are inverting an PTEST/TESTP operand, attempt to adjust the CC

llvm/test/CodeGen/X86/addcarry.ll

 }
 
 ; Here %carryin is considered as valid carry flag for combining into ADDCARRY
 ; although %carryin does not come from any carry-producing instruction.
 define { i64, i1 } @addcarry_fake_carry(i64 %a, i64 %b, i1 %carryin) {
 ; CHECK-LABEL: addcarry_fake_carry:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    andb $1, %dl
-; CHECK-NEXT:    addb $-1, %dl
+; CHECK-NEXT:    btl $0, %edx
 ; CHECK-NEXT:    adcq %rsi, %rax
 ; CHECK-NEXT:    setb %dl
 ; CHECK-NEXT:    retq
     %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a, i64 %b)
     %partial = extractvalue { i64, i1 } %t1, 0
     %k1 = extractvalue { i64, i1 } %t1, 1
 
     %zcarryin = zext i1 %carryin to i64

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

; X64-NEXT:    retq
   %6 = extractvalue { i8, i32 } %4, 0
   %7 = icmp eq i8 %6, 0
   %8 = add i32 %3, %1
   %9 = or i32 %5, %8
   %10 = select i1 %7, i32 0, i32 %9
   ret i32 %10
 }
 
-; FIXME: Fail to convert add+lshr+and to BT
 define i32 @adc_merge_constants(i32 %a0) nounwind {
 ; X86-LABEL: adc_merge_constants:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    shrl $11, %ecx
-; X86-NEXT:    andb $1, %cl
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:    addb $-1, %cl
+; X86-NEXT:    btl $11, {{[0-9]+}}(%esp)
 ; X86-NEXT:    adcl $54, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: adc_merge_constants:
 ; X64:       # %bb.0:
-; X64-NEXT:    shrl $11, %edi
-; X64-NEXT:    andb $1, %dil
 ; X64-NEXT:    xorl %eax, %eax
-; X64-NEXT:    addb $-1, %dil
+; X64-NEXT:    btl $11, %edi
 ; X64-NEXT:    adcl $54, %eax
 ; X64-NEXT:    retq
   %bit = lshr i32 %a0, 11
   %mask = and i32 %bit, 1
   %isz = trunc i32 %mask to i8
   %adc = tail call { i8, i32 } @llvm.x86.addcarry.32(i8 %isz, i32 55, i32 -1)
   %sum = extractvalue { i8, i32 } %adc, 1
   ret i32 %sum
 }
 
 declare { i8, i32 } @llvm.x86.addcarry.32(i8, i32, i32)

llvm/test/CodeGen/X86/subcarry.ll

 }
 
 ; Here %carryin is considered as valid carry flag for combining into ADDCARRY
 ; although %carryin does not come from any carry-producing instruction.
 define { i64, i1 } @subcarry_fake_carry(i64 %a, i64 %b, i1 %carryin) {
 ; CHECK-LABEL: subcarry_fake_carry:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    andb $1, %dl
-; CHECK-NEXT:    addb $-1, %dl
+; CHECK-NEXT:    btl $0, %edx
 ; CHECK-NEXT:    sbbq %rsi, %rax
 ; CHECK-NEXT:    setb %dl
 ; CHECK-NEXT:    retq
     %t1 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %a, i64 %b)
     %partial = extractvalue { i64, i1 } %t1, 0
     %k1 = extractvalue { i64, i1 } %t1, 1
 
     %zcarryin = zext i1 %carryin to i64