[DAGCombiner] Propagate carry flag for 3+ additions

[chfast]

Summary

This is an attempt to more aggressively optimize additions with carry flag propagation. So far DAG Combiner is able to optimize it mostly for two additions.
This change makes it work for 3 additions.

The goal is to have it working for at lest 4 additions, so this is not finished yet. But I'm sending it at this point to possibly get comments in case the direction where this is going is work.

[deadalnix]

Can you please explain a bit more what this is doing? This seems interesting, but I'm not quite sure the pattern is correct.

[deadalnix]

Also while I'm at it, first sorry for taking so long to review, I missed that patch. Second, if I understand properly, getting node to be processed in the right order actually can collapse arbitrary long addition chains, but it's not clear how to get there, there is a bit of a wack a mole problem that start poping up every time.

[chfast]

Thanks for comments @deadalnix, but please review D70079. I'm closing this one as being the duplicate of the mentioned PR.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitOR(SDNode *N) {
 
   // See if this is some rotate idiom.
   if (SDValue Rot = MatchRotate(N0, N1, SDLoc(N)))
     return Rot;
 
   if (SDValue Load = MatchLoadCombine(N))
     return Load;
 
+  // TODO(chfast): Move to visitORCommutative()
+  // TODO(chfast): Generalize for other opcodes.
+
+  if (auto Carry0 = getAsCarry(TLI, N0)) {
+    if (Carry0.getOpcode() == ISD::UADDO && Carry0.hasOneUse()) {
+      if (auto Carry1 = getAsCarry(TLI, N1)) {
+        if (Carry1.getOpcode() == Carry0.getOpcode() && Carry1.hasOneUse()) {
+          if (auto Carry2 = getAsCarry(TLI, Carry1.getOperand(1))) {
+            if (Carry2.getOpcode() == Carry0.getOpcode() &&
+                Carry2.hasOneUse()) {
+              if (TLI.isOperationLegalOrCustom(ISD::ADDCARRY,
+                                               Carry1->getValueType(0))) {
+                // TODO: The ADDCARRY node should replace the Carry1 node,
+                //       but this happens in other place in the DAG combiner.
+                auto AddcarryN =
+                    DAG.getNode(ISD::ADDCARRY, SDLoc{N0}, N0->getVTList(),
+                                N0->getOperand(0), N0->getOperand(1), Carry2);
+                return CombineTo(N, AddcarryN.getValue(1));
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+
   // Simplify the operands using demanded-bits information.
   if (SimplifyDemandedBits(SDValue(N, 0)))
     return SDValue(N, 0);
 
   // If OR can be rewritten into ADD, try combines based on ADD.
   if ((!LegalOperations || TLI.isOperationLegal(ISD::ADD, VT)) &&
       DAG.haveNoCommonBitsSet(N0, N1))
     if (SDValue Combined = visitADDLike(N))

llvm/test/CodeGen/X86/addcarry.ll

 }
 
 
 %uint128 = type { i64, i64 }
 
 define zeroext i1 @uaddo128(i64 %0, i64 %1, i64 %2, i64 %3, %uint128* nocapture %4) nounwind {
 ; CHECK-LABEL: uaddo128:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    addq %rcx, %rsi
-; CHECK-NEXT:    setb %cl
 ; CHECK-NEXT:    addq %rdx, %rdi
-; CHECK-NEXT:    adcq $0, %rsi
+; CHECK-NEXT:    adcq %rcx, %rsi
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %cl, %al
 ; CHECK-NEXT:    movq %rsi, (%r8)
 ; CHECK-NEXT:    movq %rdi, 8(%r8)
 ; CHECK-NEXT:    retq
   %6 = add i64 %2, %0
   %7 = icmp ult i64 %6, %0
   %8 = add i64 %3, %1
   %9 = icmp ult i64 %8, %1
   %10 = zext i1 %7 to i64

 
 
 %uint192 = type { i64, i64, i64 }
 
 define void @add192(%uint192* sret %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5, i64 %6) nounwind {
 ; CHECK-LABEL: add192:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    addq %r9, %rdx
-; CHECK-NEXT:    setb %dil
 ; CHECK-NEXT:    addq %r8, %rsi
-; CHECK-NEXT:    adcq $0, %rdx
-; CHECK-NEXT:    setb %r8b
-; CHECK-NEXT:    orb %dil, %r8b
-; CHECK-NEXT:    addq {{[0-9]+}}(%rsp), %rcx
-; CHECK-NEXT:    movzbl %r8b, %edi
-; CHECK-NEXT:    addq %rcx, %rdi
-; CHECK-NEXT:    movq %rdi, (%rax)
-; CHECK-NEXT:    movq %rdx, 8(%rax)
-; CHECK-NEXT:    movq %rsi, 16(%rax)
+; CHECK-NEXT:    adcq %r9, %rdx
+; CHECK-NEXT:    adcq {{[0-9]+}}(%rsp), %rcx
+; CHECK-NEXT:    movq %rcx, (%rdi)
+; CHECK-NEXT:    movq %rdx, 8(%rdi)
+; CHECK-NEXT:    movq %rsi, 16(%rdi)
 ; CHECK-NEXT:    retq
   %8 = add i64 %4, %1
   %9 = icmp ult i64 %8, %1
   %10 = add i64 %5, %2
   %11 = icmp ult i64 %10, %2
   %12 = zext i1 %9 to i64
   %13 = add i64 %10, %12
   %14 = icmp ult i64 %13, %10