[DAGCombiner] fold (addcarry (xor a, -1), b, c) -> (subcarry b, a, !c) and flip carry.

[deadalnix]

Summary

As per title. DAGCombiner only mathes the special case where b = 0, this patches extends the pattern to match any value of b.

Depends on D57302

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2413 ↗

(On Diff #190083)

NFC - this can be committed straight away?

2423 ↗

(On Diff #190083)

Drop unnecessary getNode() ?

[deadalnix]

Rebase, extract the NFC changes into a NFC patch and remove redundant getNode call.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2711 ↗

(On Diff #207821)

Are there any callers that use Force == false?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2711 ↗

(On Diff #207821)

I have to be honest here, that patch is from march and my memory isn't super fresh. Reading the code, this seems wrong and I'm surprised things work at all. When force is set to true, then extractBooleanFlip will ALWAYS flip the boolean, even if that means adding new ops. Clearly, this is not what is intended in the select case for instance. It's somewhat surprising that no test broke. I'll investigate further and see if I can come up with a test case for select.

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2711 ↗

(On Diff #207821)

After further investigation, it turns out that select use a boolean predicate, so Force cannot have any effect (1 is already recognized as a flip, 0 is a noop and a constant gets optimized away).

[deadalnix]

Add a comment explainign what extractBooleanFlip does.

By default, only flip the boolean if it is cheaper to compute.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2718 ↗

(On Diff #207909)

It's probably better for Force not to have a default value?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2718 ↗

(On Diff #207909)

I don't feel strongly either way so I'll remove the default value.

[deadalnix]

Remove default value for extractBooleanFlip's Force parameter.

[RKSimon]

LGTM - cheers

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

static SDValue flipBoolean(SDValue V, const SDLoc &DL,
   case TargetLowering::ZeroOrNegativeOneBooleanContent:
     Cst = DAG.getAllOnesConstant(DL, VT);
     break;
   }
 
   return DAG.getNode(ISD::XOR, DL, VT, V, Cst);
 }
 
-static SDValue extractBooleanFlip(SDValue V, const TargetLowering &TLI) {
+/**
+ * Flips a boolean if it is cheaper to compute. If the Force parameters is set,
+ * then the flip also occurs if computing the inverse is the same cost.
+ * This function returns an empty SDValue in case it cannot flip the boolean
+ * without increasing the cost of the computation. If you want to flip a boolean
+ * no matter what, use flipBoolean.
+ */
+static SDValue extractBooleanFlip(SDValue V, SelectionDAG &DAG,
+                                  const TargetLowering &TLI,
+                                  bool Force) {
+  if (Force && isa<ConstantSDNode>(V))
+    return flipBoolean(V, SDLoc(V), DAG, TLI);
+
   if (V.getOpcode() != ISD::XOR)
     return SDValue();
 
   ConstantSDNode *Const = isConstOrConstSplat(V.getOperand(1), false);
   if (!Const)
     return SDValue();
 
   EVT VT = V.getValueType();
 
   bool IsFlip = false;
   switch(TLI.getBooleanContents(VT)) {
     case TargetLowering::ZeroOrOneBooleanContent:
       IsFlip = Const->isOne();
       break;
     case TargetLowering::ZeroOrNegativeOneBooleanContent:
       IsFlip = Const->isAllOnesValue();
       break;
     case TargetLowering::UndefinedBooleanContent:
       IsFlip = (Const->getAPIntValue() & 0x01) == 1;
       break;
   }
 
   if (IsFlip)
     return V.getOperand(0);
+  if (Force)
+    return flipBoolean(V, SDLoc(V), DAG, TLI);
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDO(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   bool IsSigned = (ISD::SADDO == N->getOpcode());
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)) {
-    if (SDValue B = extractBooleanFlip(CarryIn, TLI)) {
-      SDValue Sub = DAG.getNode(ISD::SUBCARRY, DL, N->getVTList(),
-                                DAG.getConstant(0, DL, N0.getValueType()),
-                                N0.getOperand(0), B);
-      return CombineTo(N, Sub,
-                       flipBoolean(Sub.getValue(1), DL, DAG, TLI));
-    }
-  }
-
   if (SDValue Combined = visitADDCARRYLike(N0, N1, CarryIn, N))
     return Combined;
 
   if (SDValue Combined = visitADDCARRYLike(N1, N0, CarryIn, N))
     return Combined;
 
   return SDValue();
 }
if (Carry1.getOperand(1) == Carry0.getValue(0)) {
     return cancelDiamond(Carry1.getOperand(0), Carry0.getOperand(0));
   }
 
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDCARRYLike(SDValue N0, SDValue N1, SDValue CarryIn,
                                        SDNode *N) {
+  // fold (addcarry (xor a, -1), b, c) -> (subcarry b, a, !c) and flip carry.
+  if (isBitwiseNot(N0))
+    if (SDValue NotC = extractBooleanFlip(CarryIn, DAG, TLI, true)) {
+      SDLoc DL(N);
+      SDValue Sub = DAG.getNode(ISD::SUBCARRY, DL, N->getVTList(), N1,
+                                N0.getOperand(0), NotC);
+      return CombineTo(N, Sub,
+                       flipBoolean(Sub.getValue(1), DL, DAG, TLI));
+    }
+
   // Iff the flag result is dead:
   // (addcarry (add|uaddo X, Y), 0, Carry) -> (addcarry X, Y, Carry)
   // Don't do this if the Carry comes from the uaddo. It won't remove the uaddo
   // or the dependency between the instructions.
   if ((N0.getOpcode() == ISD::ADD ||
        (N0.getOpcode() == ISD::UADDO && N0.getResNo() == 0 &&
         N0.getValue(1) != CarryIn)) &&
       isNullConstant(N1) && !N->hasAnyUseOfValue(1))
if (N2->getOpcode() == ISD::SELECT && N2->hasOneUse()) {
         if (SDValue Combined = visitORLike(N0, N2_0, N))
           return DAG.getNode(ISD::SELECT, DL, N1.getValueType(), Combined, N1,
                              N2_2, Flags);
       }
     }
   }
 
   // select (not Cond), N1, N2 -> select Cond, N2, N1
-  if (SDValue F = extractBooleanFlip(N0, TLI)) {
+  if (SDValue F = extractBooleanFlip(N0, DAG, TLI, false)) {
     SDValue SelectOp = DAG.getSelect(DL, VT, F, N2, N1);
     SelectOp->setFlags(Flags);
     return SelectOp;
   }
 
   // Fold selects based on a setcc into other things, such as min/max/abs.
   if (N0.getOpcode() == ISD::SETCC) {
     SDValue Cond0 = N0.getOperand(0), Cond1 = N0.getOperand(1);
SDValue DAGCombiner::visitVSELECT(SDNode *N) {
   SDValue N2 = N->getOperand(2);
   EVT VT = N->getValueType(0);
   SDLoc DL(N);
 
   if (SDValue V = DAG.simplifySelect(N0, N1, N2))
     return V;
 
   // vselect (not Cond), N1, N2 -> vselect Cond, N2, N1
-  if (SDValue F = extractBooleanFlip(N0, TLI))
+  if (SDValue F = extractBooleanFlip(N0, DAG, TLI, false))
     return DAG.getSelect(DL, VT, F, N2, N1);
 
   // Canonicalize integer abs.
   // vselect (setg[te] X,  0),  X, -X ->
   // vselect (setgt    X, -1),  X, -X ->
   // vselect (setl[te] X,  0), -X,  X ->
   // Y = sra (X, size(X)-1); xor (add (X, Y), Y)
   if (N0.getOpcode() == ISD::SETCC) {

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

; CHECK-NEXT:    retq
   %2 = add i128 %1, 1
   ret i128 %2
 }
 
 define i128 @addcarry_to_subcarry(i64 %a, i64 %b) {
 ; CHECK-LABEL: addcarry_to_subcarry:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    cmpq %rsi, %rdi
 ; CHECK-NEXT:    notq %rsi
-; CHECK-NEXT:    movb $1, %cl
+; CHECK-NEXT:    setae %cl
 ; CHECK-NEXT:    addb $-1, %cl
-; CHECK-NEXT:    movq %rdi, %rcx
-; CHECK-NEXT:    adcq %rsi, %rcx
 ; CHECK-NEXT:    adcq $0, %rax
 ; CHECK-NEXT:    setb %cl
 ; CHECK-NEXT:    movzbl %cl, %edx
 ; CHECK-NEXT:    addq %rsi, %rax
 ; CHECK-NEXT:    adcq $0, %rdx
 ; CHECK-NEXT:    retq
   %notb = xor i64 %b, -1
   %notb128 = zext i64 %notb to i128
   %a128 = zext i64 %a to i128
   %sum1 = add i128 %a128, 1
   %sub1 = add i128 %sum1, %notb128
   %hi = lshr i128 %sub1, 64
   %sum2 = add i128 %hi, %a128
   %sub2 = add i128 %sum2, %notb128
   ret i128 %sub2
 }

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

entry:
   %30 = insertvalue [4 x i64] %29, i64 %26, 3
   %31 = insertvalue %S undef, [4 x i64] %30, 0
   ret %S %31
 }
 
 define %S @sub(%S* nocapture readonly %this, %S %arg.b) local_unnamed_addr {
 ; CHECK-LABEL: sub:
 ; CHECK:       # %bb.0: # %entry
-; CHECK-NEXT:    pushq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    .cfi_offset %rbx, -16
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    movq (%rsi), %r10
 ; CHECK-NEXT:    movq 8(%rsi), %rdi
-; CHECK-NEXT:    movq %r10, %r11
-; CHECK-NEXT:    subq %rdx, %r11
-; CHECK-NEXT:    notq %rdx
-; CHECK-NEXT:    movb $1, %bl
-; CHECK-NEXT:    addb $-1, %bl
-; CHECK-NEXT:    adcq %r10, %rdx
+; CHECK-NEXT:    subq %rdx, %r10
+; CHECK-NEXT:    setae %dl
+; CHECK-NEXT:    addb $-1, %dl
 ; CHECK-NEXT:    adcq $0, %rdi
 ; CHECK-NEXT:    setb %dl
-; CHECK-NEXT:    movzbl %dl, %edx
+; CHECK-NEXT:    movzbl %dl, %r11d
 ; CHECK-NEXT:    notq %rcx
 ; CHECK-NEXT:    addq %rdi, %rcx
-; CHECK-NEXT:    adcq 16(%rsi), %rdx
-; CHECK-NEXT:    setb %bl
-; CHECK-NEXT:    movzbl %bl, %edi
+; CHECK-NEXT:    adcq 16(%rsi), %r11
+; CHECK-NEXT:    setb %dl
+; CHECK-NEXT:    movzbl %dl, %edx
 ; CHECK-NEXT:    notq %r8
-; CHECK-NEXT:    addq %rdx, %r8
-; CHECK-NEXT:    adcq 24(%rsi), %rdi
+; CHECK-NEXT:    addq %r11, %r8
+; CHECK-NEXT:    adcq 24(%rsi), %rdx
 ; CHECK-NEXT:    notq %r9
-; CHECK-NEXT:    addq %rdi, %r9
-; CHECK-NEXT:    movq %r11, (%rax)
+; CHECK-NEXT:    addq %rdx, %r9
+; CHECK-NEXT:    movq %r10, (%rax)
 ; CHECK-NEXT:    movq %rcx, 8(%rax)
 ; CHECK-NEXT:    movq %r8, 16(%rax)
 ; CHECK-NEXT:    movq %r9, 24(%rax)
-; CHECK-NEXT:    popq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 8
 ; CHECK-NEXT:    retq
 entry:
   %0 = extractvalue %S %arg.b, 0
   %.elt6 = extractvalue [4 x i64] %0, 1
   %.elt8 = extractvalue [4 x i64] %0, 2
   %.elt10 = extractvalue [4 x i64] %0, 3
   %.elt = extractvalue [4 x i64] %0, 0
   %1 = getelementptr inbounds %S, %S* %this, i64 0, i32 0, i64 0