[DAGCombine] Combine composition of ADDC(ADDE)

[deadalnix]

Summary

fold (add X, (adde Y, 0, Carry)) -> (adde X, Y, Carry)
fold (addc X, (adde Y, 0, Carry)) -> (adde X, Y, Carry) when Y + 1 cannot overflow.
fold (adde (add|adc X, Y), 0, Carry) -> (adde X, Y, Carry) when carry isn't used.
fold (adde X, (adde 0, 0, Y:Carry), (adde Y, 0, Z):Carry) with Y = (addc A, B) into (adde X, 0, (adde A, B, Z):Carry)

Improves the situation for bug 31719

[deadalnix]

Rebase and use better test case.

[deadalnix]

Reabse and fix rebase conflict.
Some style improvement.

More generally, what should I do with that one ? Is it too big and I should split it is smaller pieces ?

[zvi]

Is it possible to break this patch to a patch for visitADD + 1 or 2 patches for visitADDE. It would make it easier to review the code and verify the tests give coverage.

[deadalnix]

I split the visitADD part away, the visitADDE patterns are not exposed without the visitADD ones, so they'll come in time :)

[aaboud]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1919

Is it worth checking that Carry != A:Carry, where A = add X, Y (or A = addc X, Y) ?

[deadalnix]

This is not relevent anymore.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
     VTSDNode *TN = cast<VTSDNode>(N1.getOperand(1));
     if (TN->getVT() == MVT::i1) {
       SDValue ZExt = DAG.getNode(ISD::AND, DL, VT, N1.getOperand(0),
                                  DAG.getConstant(1, DL, VT));
       return DAG.getNode(ISD::SUB, DL, VT, N0, ZExt);
     }
   }
 
+  // (add X, (adde Y, 0, Carry)) -> (adde X, Y, Carry)
+  if (N1.getOpcode() == ISD::ADDE &&
+      N1->hasOneUse() &&
+      isNullConstant(N1.getOperand(1)))
+    return DAG.getNode(ISD::ADDE, DL, DAG.getVTList(VT, MVT::Glue),
+                       N0, N1->getOperand(0), N1->getOperand(2));
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDC(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
 
if (LHSZero.getBoolValue()) {
     // If all possibly-set bits on the LHS are clear on the RHS, return an OR.
     // If all possibly-set bits on the RHS are clear on the LHS, return an OR.
     if ((RHSZero & ~LHSZero) == ~LHSZero || (LHSZero & ~RHSZero) == ~RHSZero)
       return CombineTo(N, DAG.getNode(ISD::OR, SDLoc(N), VT, N0, N1),
                        DAG.getNode(ISD::CARRY_FALSE,
                                    SDLoc(N), MVT::Glue));
   }
 
+  // (addc X, (adde Y, 0, Carry)) -> (adde X, Y, Carry)
+  // if Y + 1 cannot overflow.
+  if (N1.getOpcode() == ISD::ADDE &&
+      N1->hasOneUse() &&
+      isNullConstant(N1.getOperand(1))) {
+    APInt YZero, YOne;
+    DAG.computeKnownBits(N1.getOperand(0), YZero, YOne);
+    if (YZero.getBoolValue())
+      return DAG.getNode(ISD::ADDE, SDLoc(N), N->getVTList(), N0,
+                         N1->getOperand(0), N1->getOperand(2));
+  }
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDE(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDValue CarryIn = N->getOperand(2);
+  auto VTL = N->getVTList();
+  SDLoc DL(N);
 
   // canonicalize constant to RHS
   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
   if (N0C && !N1C)
-    return DAG.getNode(ISD::ADDE, SDLoc(N), N->getVTList(),
-                       N1, N0, CarryIn);
+    return DAG.getNode(ISD::ADDE, DL, VTL, N1, N0, CarryIn);
 
   // fold (adde x, y, false) -> (addc x, y)
   if (CarryIn.getOpcode() == ISD::CARRY_FALSE)
-    return DAG.getNode(ISD::ADDC, SDLoc(N), N->getVTList(), N0, N1);
+    return DAG.getNode(ISD::ADDC, DL, VTL, N0, N1);
+
+  // If the flag result is dead, we can do transform that invalidate it.
+  if (!N->hasAnyUseOfValue(1)) {
+    // (adde (add|addc X, Y), 0, Carry) -> (adde X, Y, Carry)
+    if ((N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::ADDC) &&
+        isNullConstant(N1))
+      return DAG.getNode(ISD::ADDE, DL, VTL,
+                         N0->getOperand(0), N0->getOperand(1), CarryIn);
+  }
+
+  // This is a convoluted pattern, but it is actually common
+  // when legalizing big int additions.
+  // (adde X, (adde 0, 0, Y:Carry), (adde Y, 0, Z):Carry)
+  //   -> (adde X, 0, (adde A, B, Z):Carry)
+  // With Y = (addc A, B)
+  if (N1.getOpcode() == ISD::ADDE &&
+      isNullConstant(N1.getOperand(0)) &&
+      isNullConstant(N1.getOperand(1)) &&
+      CarryIn.getOpcode() == ISD::ADDE &&
+      isNullConstant(CarryIn.getOperand(1))) {
+    auto Y = CarryIn.getOperand(0);
+    if (Y.getOpcode() == ISD::ADDC &&
+        N1.getOperand(2).getNode() == Y.getNode()) {
+      auto NewY = DAG.getNode(ISD::ADDE, DL, VTL,
+                              Y.getOperand(0), Y.getOperand(1),
+                              CarryIn.getOperand(2));
+      AddToWorklist(NewY.getNode());
+      return DAG.getNode(ISD::ADDE, DL, VTL, N0,
+                         DAG.getConstant(0, DL, N0.getValueType()),
+                         NewY.getValue(1));
+    }
+  }
 
   return SDValue();
 }
 
 // Since it may not be valid to emit a fold to zero for vector initializers
 // check if we can before folding.
 static SDValue tryFoldToZero(const SDLoc &DL, const TargetLowering &TLI, EVT VT,
                              SelectionDAG &DAG, bool LegalOperations,

test/CodeGen/X86/adde-carry.ll

 }
 
 %scalar = type { [4 x i64] }
 
 define %scalar @pr31719(%scalar* nocapture readonly %this, %scalar %arg.b) {
 ; CHECK-LABEL: pr31719:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    addq (%rsi), %rdx
-; CHECK-NEXT:    sbbq %r10, %r10
-; CHECK-NEXT:    andl $1, %r10d
-; CHECK-NEXT:    addq 8(%rsi), %rcx
-; CHECK-NEXT:    sbbq %r11, %r11
-; CHECK-NEXT:    andl $1, %r11d
-; CHECK-NEXT:    addq %r10, %rcx
-; CHECK-NEXT:    adcq $0, %r11
-; CHECK-NEXT:    addq 16(%rsi), %r8
-; CHECK-NEXT:    sbbq %rax, %rax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    addq %r11, %r8
-; CHECK-NEXT:    adcq $0, %rax
-; CHECK-NEXT:    addq 24(%rsi), %r9
-; CHECK-NEXT:    addq %rax, %r9
+; CHECK-NEXT:    adcq 8(%rsi), %rcx
+; CHECK-NEXT:    adcq 16(%rsi), %r8
+; CHECK-NEXT:    adcq 24(%rsi), %r9
 ; CHECK-NEXT:    movq %rdx, (%rdi)
 ; CHECK-NEXT:    movq %rcx, 8(%rdi)
 ; CHECK-NEXT:    movq %r8, 16(%rdi)
 ; CHECK-NEXT:    movq %r9, 24(%rdi)
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    retq
 entry:
   %0 = extractvalue %scalar %arg.b, 0