[DAGCombiner] Add SADDO/SSUBO combine support

[RKSimon]

Summary

Basic constant handling folds, for both scalars and vectors

[spatel]

I think we'd do better by making a helper for the common code rather than duplicating. These things tend to diverge because someone will come along later and add a fold for 1 opcode but forget to add the corresponding fold for its sibling. This might've already happened because we allow vectors for the signed ops, but not the unsigned ops...or that's the planned follow-up?

[RKSimon]

In D58967#1418826, @spatel wrote:

I think we'd do better by making a helper for the common code rather than duplicating. These things tend to diverge because someone will come along later and add a fold for 1 opcode but forget to add the corresponding fold for its sibling. This might've already happened because we allow vectors for the signed ops, but not the unsigned ops...or that's the planned follow-up?

I'm happy to fold this into a generalized version of visitUADDO/visitUSUBO once D58965 has landed.

[spatel]

Ah, I'm getting the order of the patches mixed up. Are we missing tests for when the flag result is unused, or is that already covered elsewhere?

[RKSimon]

In D58967#1418877, @spatel wrote:

Ah, I'm getting the order of the patches mixed up. Are we missing tests for when the flag result is unused, or is that already covered elsewhere?

On scalars we do have some tests that cover this. For vectors I haven't thought of a good way to test this yet as expansion strips it away if its not used.

[spatel]

Code/tests look correct, so LGTM. Please do refactor to reduce duplication once the other patches are committed.

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue visitTokenFactor(SDNode *N);
     SDValue visitMERGE_VALUES(SDNode *N);
     SDValue visitADD(SDNode *N);
     SDValue visitADDLike(SDValue N0, SDValue N1, SDNode *LocReference);
     SDValue visitSUB(SDNode *N);
     SDValue visitADDSAT(SDNode *N);
     SDValue visitSUBSAT(SDNode *N);
     SDValue visitADDC(SDNode *N);
+    SDValue visitSADDO(SDNode *N);
     SDValue visitUADDO(SDNode *N);
     SDValue visitUADDOLike(SDValue N0, SDValue N1, SDNode *N);
     SDValue visitSUBC(SDNode *N);
+    SDValue visitSSUBO(SDNode *N);
     SDValue visitUSUBO(SDNode *N);
     SDValue visitADDE(SDNode *N);
     SDValue visitADDCARRY(SDNode *N);
     SDValue visitADDCARRYLike(SDValue N0, SDValue N1, SDValue CarryIn, SDNode *N);
     SDValue visitSUBE(SDNode *N);
     SDValue visitSUBCARRY(SDNode *N);
     SDValue visitMUL(SDNode *N);
     SDValue useDivRem(SDNode *N);
SDValue DAGCombiner::visit(SDNode *N) {
   case ISD::MERGE_VALUES:       return visitMERGE_VALUES(N);
   case ISD::ADD:                return visitADD(N);
   case ISD::SUB:                return visitSUB(N);
   case ISD::SADDSAT:
   case ISD::UADDSAT:            return visitADDSAT(N);
   case ISD::SSUBSAT:
   case ISD::USUBSAT:            return visitSUBSAT(N);
   case ISD::ADDC:               return visitADDC(N);
+  case ISD::SADDO:              return visitSADDO(N);
   case ISD::UADDO:              return visitUADDO(N);
   case ISD::SUBC:               return visitSUBC(N);
+  case ISD::SSUBO:              return visitSSUBO(N);
   case ISD::USUBO:              return visitUSUBO(N);
   case ISD::ADDE:               return visitADDE(N);
   case ISD::ADDCARRY:           return visitADDCARRY(N);
   case ISD::SUBE:               return visitSUBE(N);
   case ISD::SUBCARRY:           return visitSUBCARRY(N);
   case ISD::MUL:                return visitMUL(N);
   case ISD::SDIV:               return visitSDIV(N);
   case ISD::UDIV:               return visitUDIV(N);
switch(TLI.getBooleanContents(VT)) {
     case TargetLowering::ZeroOrNegativeOneBooleanContent:
       return Const->isAllOnesValue();
     case TargetLowering::UndefinedBooleanContent:
       return (Const->getAPIntValue() & 0x01) == 1;
   }
   llvm_unreachable("Unsupported boolean content");
 }
 
+// TODO: merge this with DAGCombiner::visitUADDO
+SDValue DAGCombiner::visitSADDO(SDNode *N) {
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+  EVT VT = N0.getValueType();
+  EVT CarryVT = N->getValueType(1);
+  SDLoc DL(N);
+
+  // If the flag result is dead, turn this into an ADD.
+  if (!N->hasAnyUseOfValue(1))
+    return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
+                     DAG.getUNDEF(CarryVT));
+
+  // canonicalize constant to RHS.
+  if (DAG.isConstantIntBuildVectorOrConstantInt(N0) &&
+      !DAG.isConstantIntBuildVectorOrConstantInt(N1))
+    return DAG.getNode(ISD::SADDO, DL, N->getVTList(), N1, N0);
+
+  // fold (saddo x, 0) -> x + no carry out
+  if (isNullOrNullSplat(N1))
+    return CombineTo(N, N0, DAG.getConstant(0, DL, CarryVT));
+
+  return SDValue();
+}
+
 SDValue DAGCombiner::visitUADDO(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   if (VT.isVector())
     return SDValue();
 
   EVT CarryVT = N->getValueType(1);
SDValue DAGCombiner::visitSUBC(SDNode *N) {
   // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1) + no borrow
   if (isAllOnesConstant(N0))
     return CombineTo(N, DAG.getNode(ISD::XOR, DL, VT, N1, N0),
                      DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
 
   return SDValue();
 }
 
+// TODO: merge this with DAGCombiner::visitUSUBO
+SDValue DAGCombiner::visitSSUBO(SDNode *N) {
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+  EVT VT = N0.getValueType();
+  EVT CarryVT = N->getValueType(1);
+  SDLoc DL(N);
+
+  // If the flag result is dead, turn this into an SUB.
+  if (!N->hasAnyUseOfValue(1))
+    return CombineTo(N, DAG.getNode(ISD::SUB, DL, VT, N0, N1),
+                     DAG.getUNDEF(CarryVT));
+
+  // fold (ssubo x, x) -> 0 + no borrow
+  if (N0 == N1)
+    return CombineTo(N, DAG.getConstant(0, DL, VT),
+                     DAG.getConstant(0, DL, CarryVT));
+
+  // fold (ssubo x, 0) -> x + no borrow
+  if (isNullOrNullSplat(N1))
+    return CombineTo(N, N0, DAG.getConstant(0, DL, CarryVT));
+
+  return SDValue();
+}
+
 SDValue DAGCombiner::visitUSUBO(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   if (VT.isVector())
     return SDValue();
 
   EVT CarryVT = N->getValueType(1);

llvm/trunk/test/CodeGen/X86/combine-addo.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+sse4.1 | FileCheck %s --check-prefix=SSE
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx2 | FileCheck %s --check-prefix=AVX
 
 declare {i32, i1} @llvm.sadd.with.overflow.i32(i32, i32) nounwind readnone
 declare {i32, i1} @llvm.uadd.with.overflow.i32(i32, i32) nounwind readnone
 
 declare {<4 x i32>, <4 x i1>} @llvm.sadd.with.overflow.v4i32(<4 x i32>, <4 x i32>) nounwind readnone
 declare {<4 x i32>, <4 x i1>} @llvm.uadd.with.overflow.v4i32(<4 x i32>, <4 x i32>) nounwind readnone
 
 ; fold (sadd x, 0) -> x
 define i32 @combine_sadd_zero(i32 %a0, i32 %a1) {
 ; SSE-LABEL: combine_sadd_zero:
 ; SSE:       # %bb.0:
 ; SSE-NEXT:    movl %edi, %eax
-; SSE-NEXT:    addl $0, %eax
-; SSE-NEXT:    cmovol %esi, %eax
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_sadd_zero:
 ; AVX:       # %bb.0:
 ; AVX-NEXT:    movl %edi, %eax
-; AVX-NEXT:    addl $0, %eax
-; AVX-NEXT:    cmovol %esi, %eax
 ; AVX-NEXT:    retq
   %1 = call {i32, i1} @llvm.sadd.with.overflow.i32(i32 %a0, i32 zeroinitializer)
   %2 = extractvalue {i32, i1} %1, 0
   %3 = extractvalue {i32, i1} %1, 1
   %4 = select i1 %3, i32 %a1, i32 %2
   ret i32 %4
 }
 
 define <4 x i32> @combine_vec_sadd_zero(<4 x i32> %a0, <4 x i32> %a1) {
 ; SSE-LABEL: combine_vec_sadd_zero:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    movdqa %xmm0, %xmm2
-; SSE-NEXT:    pxor %xmm0, %xmm0
-; SSE-NEXT:    pcmpgtd %xmm2, %xmm0
-; SSE-NEXT:    pcmpeqd %xmm3, %xmm3
-; SSE-NEXT:    pxor %xmm3, %xmm0
-; SSE-NEXT:    pcmpeqd %xmm0, %xmm3
-; SSE-NEXT:    pcmpeqd %xmm0, %xmm0
-; SSE-NEXT:    pandn %xmm3, %xmm0
-; SSE-NEXT:    blendvps %xmm0, %xmm1, %xmm2
-; SSE-NEXT:    movaps %xmm2, %xmm0
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_vec_sadd_zero:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vpxor %xmm2, %xmm2, %xmm2
-; AVX-NEXT:    vpcmpgtd %xmm0, %xmm2, %xmm2
-; AVX-NEXT:    vpcmpeqd %xmm3, %xmm3, %xmm3
-; AVX-NEXT:    vpxor %xmm3, %xmm2, %xmm2
-; AVX-NEXT:    vpcmpeqd %xmm3, %xmm2, %xmm3
-; AVX-NEXT:    vpcmpeqd %xmm2, %xmm2, %xmm2
-; AVX-NEXT:    vpandn %xmm3, %xmm2, %xmm2
-; AVX-NEXT:    vblendvps %xmm2, %xmm1, %xmm0, %xmm0
 ; AVX-NEXT:    retq
   %1 = call {<4 x i32>, <4 x i1>} @llvm.sadd.with.overflow.v4i32(<4 x i32> %a0, <4 x i32> zeroinitializer)
   %2 = extractvalue {<4 x i32>, <4 x i1>} %1, 0
   %3 = extractvalue {<4 x i32>, <4 x i1>} %1, 1
   %4 = select <4 x i1> %3, <4 x i32> %a1, <4 x i32> %2
   ret <4 x i32> %4
 }
 

llvm/trunk/test/CodeGen/X86/combine-subo.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+sse4.1 | FileCheck %s --check-prefix=SSE
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+avx2 | FileCheck %s --check-prefix=AVX
 
 declare {i32, i1} @llvm.ssub.with.overflow.i32(i32, i32) nounwind readnone
 declare {i32, i1} @llvm.usub.with.overflow.i32(i32, i32) nounwind readnone
 
 declare {<4 x i32>, <4 x i1>} @llvm.ssub.with.overflow.v4i32(<4 x i32>, <4 x i32>) nounwind readnone
 declare {<4 x i32>, <4 x i1>} @llvm.usub.with.overflow.v4i32(<4 x i32>, <4 x i32>) nounwind readnone
 
 ; fold (ssub x, 0) -> x
 define i32 @combine_ssub_zero(i32 %a0, i32 %a1) {
 ; SSE-LABEL: combine_ssub_zero:
 ; SSE:       # %bb.0:
 ; SSE-NEXT:    movl %edi, %eax
-; SSE-NEXT:    subl $0, %eax
-; SSE-NEXT:    cmovol %esi, %eax
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_ssub_zero:
 ; AVX:       # %bb.0:
 ; AVX-NEXT:    movl %edi, %eax
-; AVX-NEXT:    subl $0, %eax
-; AVX-NEXT:    cmovol %esi, %eax
 ; AVX-NEXT:    retq
   %1 = call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a0, i32 zeroinitializer)
   %2 = extractvalue {i32, i1} %1, 0
   %3 = extractvalue {i32, i1} %1, 1
   %4 = select i1 %3, i32 %a1, i32 %2
   ret i32 %4
 }
 
 define <4 x i32> @combine_vec_ssub_zero(<4 x i32> %a0, <4 x i32> %a1) {
 ; SSE-LABEL: combine_vec_ssub_zero:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    movdqa %xmm0, %xmm2
-; SSE-NEXT:    pxor %xmm3, %xmm3
-; SSE-NEXT:    pcmpgtd %xmm0, %xmm3
-; SSE-NEXT:    pcmpeqd %xmm4, %xmm4
-; SSE-NEXT:    pxor %xmm4, %xmm3
-; SSE-NEXT:    movdqa %xmm3, %xmm0
-; SSE-NEXT:    pcmpeqd %xmm4, %xmm0
-; SSE-NEXT:    pcmpeqd %xmm3, %xmm3
-; SSE-NEXT:    pxor %xmm4, %xmm3
-; SSE-NEXT:    pandn %xmm3, %xmm0
-; SSE-NEXT:    blendvps %xmm0, %xmm1, %xmm2
-; SSE-NEXT:    movaps %xmm2, %xmm0
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_vec_ssub_zero:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vpxor %xmm2, %xmm2, %xmm2
-; AVX-NEXT:    vpcmpgtd %xmm0, %xmm2, %xmm2
-; AVX-NEXT:    vpcmpeqd %xmm3, %xmm3, %xmm3
-; AVX-NEXT:    vpxor %xmm3, %xmm2, %xmm2
-; AVX-NEXT:    vpcmpeqd %xmm3, %xmm2, %xmm4
-; AVX-NEXT:    vpcmpeqd %xmm2, %xmm2, %xmm2
-; AVX-NEXT:    vpxor %xmm3, %xmm2, %xmm2
-; AVX-NEXT:    vpandn %xmm2, %xmm4, %xmm2
-; AVX-NEXT:    vblendvps %xmm2, %xmm1, %xmm0, %xmm0
 ; AVX-NEXT:    retq
   %1 = call {<4 x i32>, <4 x i1>} @llvm.ssub.with.overflow.v4i32(<4 x i32> %a0, <4 x i32> zeroinitializer)
   %2 = extractvalue {<4 x i32>, <4 x i1>} %1, 0
   %3 = extractvalue {<4 x i32>, <4 x i1>} %1, 1
   %4 = select <4 x i1> %3, <4 x i32> %a1, <4 x i32> %2
   ret <4 x i32> %4
 }
 
; AVX-NEXT:    retq
   %4 = select <4 x i1> %3, <4 x i32> %a1, <4 x i32> %2
   ret <4 x i32> %4
 }
 
 ; fold (ssub x, x) -> 0
 define i32 @combine_ssub_self(i32 %a0, i32 %a1) {
 ; SSE-LABEL: combine_ssub_self:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    movl %edi, %eax
-; SSE-NEXT:    subl %edi, %eax
-; SSE-NEXT:    cmovol %esi, %eax
+; SSE-NEXT:    xorl %eax, %eax
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_ssub_self:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    movl %edi, %eax
-; AVX-NEXT:    subl %edi, %eax
-; AVX-NEXT:    cmovol %esi, %eax
+; AVX-NEXT:    xorl %eax, %eax
 ; AVX-NEXT:    retq
   %1 = call {i32, i1} @llvm.ssub.with.overflow.i32(i32 %a0, i32 %a0)
   %2 = extractvalue {i32, i1} %1, 0
   %3 = extractvalue {i32, i1} %1, 1
   %4 = select i1 %3, i32 %a1, i32 %2
   ret i32 %4
 }
 
 define <4 x i32> @combine_vec_ssub_self(<4 x i32> %a0, <4 x i32> %a1) {
 ; SSE-LABEL: combine_vec_ssub_self:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    psubd %xmm0, %xmm0
+; SSE-NEXT:    xorps %xmm0, %xmm0
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_vec_ssub_self:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vpsubd %xmm0, %xmm0, %xmm0
+; AVX-NEXT:    vxorps %xmm0, %xmm0, %xmm0
 ; AVX-NEXT:    retq
   %1 = call {<4 x i32>, <4 x i1>} @llvm.ssub.with.overflow.v4i32(<4 x i32> %a0, <4 x i32> %a0)
   %2 = extractvalue {<4 x i32>, <4 x i1>} %1, 0
   %3 = extractvalue {<4 x i32>, <4 x i1>} %1, 1
   %4 = select <4 x i1> %3, <4 x i32> %a1, <4 x i32> %2
   ret <4 x i32> %4
 }
 

llvm/trunk/test/CodeGen/X86/xaluo.ll

; FAST-NEXT:    retq
   %t = call {i64, i1} @llvm.sadd.with.overflow.i64(i64 %v1, i64 1)
   %val = extractvalue {i64, i1} %t, 0
   %obit = extractvalue {i64, i1} %t, 1
   store i64 %val, i64* %res
   ret i1 %obit
 }
 
 ; SADDO reg, imm | imm, reg
-; FIXME: DAG doesn't optimize immediates on the LHS.
 define zeroext i1 @saddoi64imm1(i64 %v1, i64* %res) {
 ; SDAG-LABEL: saddoi64imm1:
 ; SDAG:       ## %bb.0:
-; SDAG-NEXT:    movl $2, %ecx
-; SDAG-NEXT:    addq %rdi, %rcx
+; SDAG-NEXT:    addq $2, %rdi
 ; SDAG-NEXT:    seto %al
-; SDAG-NEXT:    movq %rcx, (%rsi)
+; SDAG-NEXT:    movq %rdi, (%rsi)
 ; SDAG-NEXT:    retq
 ;
 ; FAST-LABEL: saddoi64imm1:
 ; FAST:       ## %bb.0:
 ; FAST-NEXT:    addq $2, %rdi
 ; FAST-NEXT:    seto %al
 ; FAST-NEXT:    movq %rdi, (%rsi)
 ; FAST-NEXT:    andb $1, %al