[DAGCombine] Refactor common addcarry pattern.

[deadalnix]

Summary

This pattern is no very useful per se, but it exposes optimization for toehr patterns that wouldn't kick in otherwize. It's very common and worth optimizing for.

[deadalnix]

Rebase

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2169

This comment really isn't any use to explain what is happening here - it needs a much better explanation.

AFAICT you are saying that if (A+B) overflows then the carry can only occur in the second operand, else if (A+B) doesn't overflow it might occur in the third (carry) operand after the additional add? Can carries ever occur in both? e.g. Is addcarry/uaddo supposed to accept for i1/i2 types?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2169

That is the idea. If A + B overflows, then Y + [0 or 1] cannot overflow. As a result, you can combine the two carries into one by doing A + B + [0 or 1]. This holds true even for types like i1, however, addcarry are generated by the legalization code, so you shouldn't get i1 in there anyway.

This transform a diamond pattern into the carry chain into a linear carry chain, and then other existing optimizations can kick in.

[deadalnix]

Change the comment to explain the transform with some ASCII art.

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2175

I like the ascii art!

I'm still not very familiar with the carry ops, so I would've kept the formulas from the previous rev in here too. This is complicated enough that I think it's justified to have both.

But I have a question about this node: (addcarry 0, 0, *)
Can that be simplified to a cast instruction from bool to the VT of the addcarry?
If yes, if we add that simplification, will it break this pattern matching?

[filcab]

You should probably also mention the PR number on the commit message.
Does this trigger often, btw?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2188

Shouldn't we allow both (addcarry *, 0, Z) and (addcarry 0, *, Z)?
Same for the final one, we could have X+0(+C) or 0+X(+C), no?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2175

I think you are correct. Let me do a patch with (addcarry 0, 0, X) to (extend/trunc X) and see where this goes.

2188

The method is called with argument in both order already. See line 2146 onward.

[filcab]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2188

Should take care of the final addcarry, yes. But it's still missing the one above (*+0+Z), no?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2175

So i played a bit with it, and as it turns out, it makes some things worse, other better. I still think this is useful, we just need to add a few patterns to get things back to normal after the fact, like promoting uaddo into addcarry when one of the parameter actually comes from a carry.

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2188

Constants are canonicalized on the RHS so it's fine.

[deadalnix]

Rebase on top of D32925

[deadalnix]

Doing some refactoring to help the introduction of further diamond pattern simplification.

[deadalnix]

Ping !

[RKSimon]

@filcab suggested adding the PR number on the commit message title as well.

LGTM - couple of minors.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2185

Worth checking/asserting that CarryIn.getResNo() == 1 ?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2185

Sounds like a good idea. i don't think we generate such a code ever, but better safe than sorry.

[deadalnix]

Check result count.

[RKSimon]

Thanks, LGTM

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitADDCARRYLike(SDValue N0, SDValue N1, SDValue CarryIn,
                                        SDNode *N) {
   // Iff the flag result is dead:
   // (addcarry (add|uaddo X, Y), 0, Carry) -> (addcarry X, Y, Carry)
   if ((N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::UADDO) &&
       isNullConstant(N1) && !N->hasAnyUseOfValue(1))
     return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(),
                        N0.getOperand(0), N0.getOperand(1), CarryIn);
 
+  /**
+   * Sometime, after legalization, we get a 'diamond' carry chain. Because
+   * the carry cannot propagate through both path at once, it is possible to
+   * restructure the chain so that it becomes linear. After which, other
+   * combine can kick in to optimize it.
+   *
+   * The pattern:
+   *                  (uaddo A, B)
+   *                    /       \
+   *                 Carry      Sum
+   *                  /           \
+   * (addcarry 0, 0, *)  (addcarry *, 0, Z)
+   *                 \        /
+   *                 Sum   Carry
+   *                   \    /
+   *       (addcarry X, *, *)
+   *
+   * is tranformed into
+   *   (addcarry X, 0, (addcarry A, B, Z):Carry)
+   */
+  if (N1.getOpcode() == ISD::ADDCARRY &&
+      isNullConstant(N1.getOperand(0)) &&
+      isNullConstant(N1.getOperand(1)) &&
+      CarryIn.getOpcode() == ISD::ADDCARRY &&
+      isNullConstant(CarryIn.getOperand(1))) {
+    auto Y = CarryIn.getOperand(0);
+    if (Y.getOpcode() == ISD::UADDO &&
+        N1.getOperand(2).getNode() == Y.getNode()) {
+      auto NewY = DAG.getNode(ISD::ADDCARRY, SDLoc(N), Y->getVTList(),
+                              Y.getOperand(0), Y.getOperand(1),
+                              CarryIn.getOperand(2));
+      AddToWorklist(NewY.getNode());
+      return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(), N0,
+                         DAG.getConstant(0, SDLoc(N), 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,
                              bool LegalTypes) {

test/CodeGen/X86/addcarry.ll

  ret void
 }
 
 %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 8(%rsi), %rcx
-; CHECK-NEXT:    sbbq %r10, %r10
-; CHECK-NEXT:    andl $1, %r10d
-; CHECK-NEXT:    addq 16(%rsi), %r8
-; CHECK-NEXT:    sbbq %rax, %rax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    addq 24(%rsi), %r9
 ; CHECK-NEXT:    addq (%rsi), %rdx
-; CHECK-NEXT:    adcq $0, %rcx
-; CHECK-NEXT:    adcq %r8, %r10
-; CHECK-NEXT:    adcq %r9, %rax
+; 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 %r10, 16(%rdi)
-; CHECK-NEXT:    movq %rax, 24(%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
   %.elt = extractvalue [4 x i64] %0, 0
   %.elt24 = extractvalue [4 x i64] %0, 1
   %.elt26 = extractvalue [4 x i64] %0, 2
   %.elt28 = extractvalue [4 x i64] %0, 3