[DAGcombine] Teach the combiner about -a = ~a + 1

[deadalnix]

Summary

This include variant for add, uaddo and addcarry. usubo and subcarry require the carry to be flipped to preserve semantic, but we chose to do the transform anyway in that case as to push the transform down the carry chain.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2199

Move this inside flipBoolean() ?

2262

full stop: // fold (uaddo (xor a, -1), 1) -> (usub 0, a) and flip carry.

[spatel]

We should have minimal dedicated tests for these patterns. Something like this:

; simple fold - no overflow intrinsic/node
define i32 @inc_not(i32 %a) {
  %nota = xor i32 %a, -1
  %r = add i32 %nota, 1
  ret i32 %r
}

%ov32 = type { i32, i1 }
declare %ov32 @llvm.uadd.with.overflow.i32(i32, i32)

define void @uaddo1_not(i32 %a, i32* %p0, i1* %p1) {
  %nota = xor i32 %a, -1
  %uaddo = call %ov32 @llvm.uadd.with.overflow.i32(i32 %nota, i32 1)
  %r0 = extractvalue %ov32 %uaddo, 0
  %r1 = extractvalue %ov32 %uaddo, 1
  store i32 %r0, i32* %p0
  store i1 %r1, i1* %p1
  ret void
}

; another test for addcarry

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2059–2061

Use llvm::isBitwiseNot()? I don't think we care about vectors in the motivating cases, but you could extend that to handle a vector constant if it matters.

On 2nd thought, do we need this? It's not necessary for the test shown here, and instcombine already does that transform. If the pattern is created here in the DAG, it should have its own test (ie, this could be an independent patch).

2263–2265

Same as above - use isBitwiseNot()?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2059–2061

You are correct that my motivation example doesn't require this. However, it seemed weird tome to to it for uaddo and addcarry, but not plain old add.

[deadalnix]

Use isBitwiseNot
Merge flipBooleanConstant into flipBoolean
Add more specific test cases.

[deadalnix]

Ping ?

[spatel]

LGTM.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitADD(SDNode *N) {
   if (SimplifyDemandedBits(SDValue(N, 0)))
     return SDValue(N, 0);
 
   // fold (a+b) -> (a|b) iff a and b share no bits.
   if ((!LegalOperations || TLI.isOperationLegal(ISD::OR, VT)) &&
       DAG.haveNoCommonBitsSet(N0, N1))
     return DAG.getNode(ISD::OR, DL, VT, N0, N1);
 
+  // fold (add (xor a, -1), 1) -> (sub 0, a)
+  if (isBitwiseNot(N0) && isOneConstantOrOneSplatConstant(N1))
+    return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT),
+                       N0.getOperand(0));
+
   if (SDValue Combined = visitADDLike(N0, N1, N))
     return Combined;
 
   if (SDValue Combined = visitADDLike(N1, N0, N))
     return Combined;
 
   return SDValue();
 }
SDValue DAGCombiner::visitADDC(SDNode *N) {
   // If it cannot overflow, transform into an add.
   if (DAG.computeOverflowKind(N0, N1) == SelectionDAG::OFK_Never)
     return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
                      DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
 
   return SDValue();
 }
 
+static SDValue flipBoolean(SDValue V, const SDLoc &DL, EVT VT,
+                           SelectionDAG &DAG, const TargetLowering &TLI) {
+  SDValue Cst;
+  switch(TLI.getBooleanContents(VT)) {
+    case TargetLowering::ZeroOrOneBooleanContent:
+    case TargetLowering::UndefinedBooleanContent:
+      Cst = DAG.getConstant(1, DL, VT);
+      break;
+    case TargetLowering::ZeroOrNegativeOneBooleanContent:
+      Cst = DAG.getConstant(-1, DL, VT);
+      break;
+    default:
+      llvm_unreachable("Unsupported boolean content");
+  }
+
+  return DAG.getNode(ISD::XOR, DL, VT, V, Cst);
+}
+
+static bool isBooleanFlip(SDValue V, EVT VT, const TargetLowering &TLI) {
+  if (V.getOpcode() != ISD::XOR) return false;
+  ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V.getOperand(1));
+  if (!Const) return false;
+
+  switch(TLI.getBooleanContents(VT)) {
+    case TargetLowering::ZeroOrOneBooleanContent:
+      return Const->isOne();
+    case TargetLowering::ZeroOrNegativeOneBooleanContent:
+      return Const->isAllOnesValue();
+    case TargetLowering::UndefinedBooleanContent:
+      return (Const->getAPIntValue() & 0x01) == 1;
+  }
+  llvm_unreachable("Unsupported boolean content");
+}
+
 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::visitUADDO(SDNode *N) {
   if (isNullConstant(N1))
     return CombineTo(N, N0, DAG.getConstant(0, DL, CarryVT));
 
   // If it cannot overflow, transform into an add.
   if (DAG.computeOverflowKind(N0, N1) == SelectionDAG::OFK_Never)
     return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
                      DAG.getConstant(0, DL, CarryVT));
 
+  // fold (uaddo (xor a, -1), 1) -> (usub 0, a) and flip carry.
+  if (isBitwiseNot(N0) && isOneConstantOrOneSplatConstant(N1)) {
+    SDValue Sub = DAG.getNode(ISD::USUBO, DL, N->getVTList(),
+                              DAG.getConstant(0, DL, VT),
+                              N0.getOperand(0));
+    return CombineTo(N, Sub,
+                     flipBoolean(Sub.getValue(1), DL, CarryVT, DAG, TLI));
+  }
+
   if (SDValue Combined = visitUADDOLike(N0, N1, N))
     return Combined;
 
   if (SDValue Combined = visitUADDOLike(N1, N0, N))
     return Combined;
 
   return SDValue();
 }
SDValue DAGCombiner::visitADDCARRY(SDNode *N) {
 
   // fold (addcarry x, y, false) -> (uaddo x, y)
   if (isNullConstant(CarryIn)) {
     if (!LegalOperations ||
         TLI.isOperationLegalOrCustom(ISD::UADDO, N->getValueType(0)))
       return DAG.getNode(ISD::UADDO, DL, N->getVTList(), N0, N1);
   }
 
+  EVT CarryVT = CarryIn.getValueType();
+
   // fold (addcarry 0, 0, X) -> (and (ext/trunc X), 1) and no carry.
   if (isNullConstant(N0) && isNullConstant(N1)) {
     EVT VT = N0.getValueType();
-    EVT CarryVT = CarryIn.getValueType();
     SDValue CarryExt = DAG.getBoolExtOrTrunc(CarryIn, DL, VT, CarryVT);
     AddToWorklist(CarryExt.getNode());
     return CombineTo(N, DAG.getNode(ISD::AND, DL, VT, CarryExt,
                                     DAG.getConstant(1, DL, VT)),
                      DAG.getConstant(0, DL, CarryVT));
   }
 
+  // fold (addcarry (xor a, -1), 0, !b) -> (subcarry 0, a, b) and flip carry.
+  if (isBitwiseNot(N0) && isNullConstant(N1) &&
+      isBooleanFlip(CarryIn, CarryVT, TLI)) {
+    SDValue Sub = DAG.getNode(ISD::SUBCARRY, DL, N->getVTList(),
+                              DAG.getConstant(0, DL, N0.getValueType()),
+                              N0.getOperand(0), CarryIn.getOperand(0));
+    return CombineTo(N, Sub,
+                     flipBoolean(Sub.getValue(1), DL, CarryVT, DAG, TLI));
+  }
+
   if (SDValue Combined = visitADDCARRYLike(N0, N1, CarryIn, N))
     return Combined;
 
   if (SDValue Combined = visitADDCARRYLike(N1, N0, CarryIn, N))
     return Combined;
 
   return SDValue();
 }

test/CodeGen/X86/add.ll

entry:
   %b = add i64 %aa, 128
   store i64 %b, i64* %a
   ret void
 }
 
 define i32 @inc_not(i32 %a) {
 ; X32-LABEL: inc_not:
 ; X32:       # %bb.0:
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X32-NEXT:    notl %eax
-; X32-NEXT:    incl %eax
+; X32-NEXT:    xorl %eax, %eax
+; X32-NEXT:    subl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    retl
 ;
 ; X64-LINUX-LABEL: inc_not:
 ; X64-LINUX:       # %bb.0:
-; X64-LINUX-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-LINUX-NEXT:    notl %edi
-; X64-LINUX-NEXT:    leal 1(%rdi), %eax
+; X64-LINUX-NEXT:    negl %edi
+; X64-LINUX-NEXT:    movl %edi, %eax
 ; X64-LINUX-NEXT:    retq
 ;
 ; X64-WIN32-LABEL: inc_not:
 ; X64-WIN32:       # %bb.0:
-; X64-WIN32-NEXT:    # kill: def $ecx killed $ecx def $rcx
-; X64-WIN32-NEXT:    notl %ecx
-; X64-WIN32-NEXT:    leal 1(%rcx), %eax
+; X64-WIN32-NEXT:    negl %ecx
+; X64-WIN32-NEXT:    movl %ecx, %eax
 ; X64-WIN32-NEXT:    retq
   %nota = xor i32 %a, -1
   %r = add i32 %nota, 1
   ret i32 %r
 }
 
 define void @uaddo1_not(i32 %a, i32* %p0, i1* %p1) {
 ; X32-LABEL: uaddo1_not:
 ; X32:       # %bb.0:
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X32-NEXT:    notl %edx
-; X32-NEXT:    addl $1, %edx
+; X32-NEXT:    xorl %edx, %edx
+; X32-NEXT:    subl {{[0-9]+}}(%esp), %edx
 ; X32-NEXT:    movl %edx, (%ecx)
-; X32-NEXT:    setb (%eax)
+; X32-NEXT:    setae (%eax)
 ; X32-NEXT:    retl
 ;
 ; X64-LINUX-LABEL: uaddo1_not:
 ; X64-LINUX:       # %bb.0:
-; X64-LINUX-NEXT:    notl %edi
-; X64-LINUX-NEXT:    addl $1, %edi
+; X64-LINUX-NEXT:    negl %edi
 ; X64-LINUX-NEXT:    movl %edi, (%rsi)
-; X64-LINUX-NEXT:    setb (%rdx)
+; X64-LINUX-NEXT:    setae (%rdx)
 ; X64-LINUX-NEXT:    retq
 ;
 ; X64-WIN32-LABEL: uaddo1_not:
 ; X64-WIN32:       # %bb.0:
-; X64-WIN32-NEXT:    notl %ecx
-; X64-WIN32-NEXT:    addl $1, %ecx
+; X64-WIN32-NEXT:    negl %ecx
 ; X64-WIN32-NEXT:    movl %ecx, (%rdx)
-; X64-WIN32-NEXT:    setb (%r8)
+; X64-WIN32-NEXT:    setae (%r8)
 ; X64-WIN32-NEXT:    retq
   %nota = xor i32 %a, -1
   %uaddo = call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %nota, i32 1)
   %r0 = extractvalue {i32, i1} %uaddo, 0
   %r1 = extractvalue {i32, i1} %uaddo, 1
   store i32 %r0, i32* %p0
   store i1 %r1, i1* %p1
   ret void
 }

test/CodeGen/X86/addcarry.ll

entry:
   %34 = insertvalue [4 x i64] %33, i64 %30, 3
   %35 = insertvalue %S undef, [4 x i64] %34, 0
   ret %S %35
 }
 
 define i128 @addcarry1_not(i128 %n) {
 ; CHECK-LABEL: addcarry1_not:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    notq %rsi
-; CHECK-NEXT:    notq %rdi
-; CHECK-NEXT:    addq $1, %rdi
-; CHECK-NEXT:    adcq $0, %rsi
+; CHECK-NEXT:    xorl %edx, %edx
+; CHECK-NEXT:    negq %rdi
+; CHECK-NEXT:    sbbq %rsi, %rdx
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    movq %rsi, %rdx
 ; CHECK-NEXT:    retq
   %1 = xor i128 %n, -1
   %2 = add i128 %1, 1
   ret i128 %2
 }

test/CodeGen/X86/subcarry.ll

entry:
   ret i256 %0
 }
 
 %S = type { [4 x i64] }
 
 define %S @negate(%S* nocapture readonly %this) {
 ; CHECK-LABEL: negate:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    movq (%rsi), %rax
-; CHECK-NEXT:    movq 8(%rsi), %rcx
-; CHECK-NEXT:    notq %rax
-; CHECK-NEXT:    addq $1, %rax
-; CHECK-NEXT:    notq %rcx
-; CHECK-NEXT:    adcq $0, %rcx
-; CHECK-NEXT:    movq 16(%rsi), %rdx
-; CHECK-NEXT:    notq %rdx
-; CHECK-NEXT:    adcq $0, %rdx
-; CHECK-NEXT:    movq 24(%rsi), %rsi
-; CHECK-NEXT:    notq %rsi
-; CHECK-NEXT:    adcq $0, %rsi
-; CHECK-NEXT:    movq %rax, (%rdi)
-; CHECK-NEXT:    movq %rcx, 8(%rdi)
-; CHECK-NEXT:    movq %rdx, 16(%rdi)
-; CHECK-NEXT:    movq %rsi, 24(%rdi)
+; CHECK-NEXT:    xorl %r8d, %r8d
+; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    subq (%rsi), %rcx
+; CHECK-NEXT:    movl $0, %edx
+; CHECK-NEXT:    sbbq 8(%rsi), %rdx
+; CHECK-NEXT:    movl $0, %eax
+; CHECK-NEXT:    sbbq 16(%rsi), %rax
+; CHECK-NEXT:    sbbq 24(%rsi), %r8
+; CHECK-NEXT:    movq %rcx, (%rdi)
+; CHECK-NEXT:    movq %rdx, 8(%rdi)
+; CHECK-NEXT:    movq %rax, 16(%rdi)
+; CHECK-NEXT:    movq %r8, 24(%rdi)
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    retq
 entry:
   %0 = getelementptr inbounds %S, %S* %this, i64 0, i32 0, i64 0
   %1 = load i64, i64* %0, align 8
   %2 = xor i64 %1, -1
   %3 = zext i64 %2 to i128
   %4 = add nuw nsw i128 %3, 1