[DAGCombine] More diamond carry pattern optimization.

[deadalnix]

Summary

This diff improve the capability of DAGCOmbine to generate linear carries propagation in presence of a diamond pattern. It is now able to match a large variety of different patterns rather than some hardcoded one.

Arguably, the codegen in test cases is not better, but this is to be expected. The goal of this transformation is more about canonicalisation than actual optimisation.

[deadalnix]

Fix NewY's type which was invalid in some circustances

[craig.topper]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2522 ↗

(On Diff #183760)

usualy->usually

2523 ↗

(On Diff #183760)

linarized->linearized

2567 ↗

(On Diff #183760)

fnd->find

[deadalnix]

Fix typos.
Rebase on top of D57367

[deadalnix]

Remove dependency on D57367 as now it show improvement on existing test cases.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2590 ↗

(On Diff #190035)

ddamoni ? paternq?

2670 ↗

(On Diff #190035)

Don't use auto

2675 ↗

(On Diff #190035)

Instead of 'DoIt' - would it be better to move this into a lambda and just call it in each of the cases above?

test/CodeGen/X86/subcarry.ll

107 ↗

(On Diff #190035)

Whats your plan to deal with this regression?

[deadalnix]

• rebase
• Fix types
• Remove unnecessary use of auto
• Use a lambda

[deadalnix]

test/CodeGen/X86/subcarry.ll

107 ↗

(On Diff #190035)

It may seems counter intuitive, but this is regression is maybe the main motivation behind that patch. The code previously had 2 carries propagation, and now it has one. This new form is not as good independently, but can be optimized.

See D57317 and D59208 for instance.

[deadalnix]

Rebase and ping.

[deadalnix]

Ping

[deadalnix]

Rebase and ping.

While I understand one may have doubts about this patch, it is absolutely key to push the quality of the canonicalisation of large interegers further. With a dual track for carry propapagtion, it is not possible to to do any better than we do now.

[deadalnix]

Rebase.

This is important to be able to make the carry propagation path canonical to be able to optimise large ineteger computation further. I would really appreciate if tis could move forward as this is gating a lot of work.

[deadalnix]

Rebase, ping?

[niravd]

Should we have the corresponding subcarry case folded in here as well?

Also, do we have a test case where we're adding/subtracting 3 or more multi-register numbers?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2779 ↗

(On Diff #202606)

nit: make the failing case here an else clause.

2812 ↗

(On Diff #202606)

Remove the else for consistency.

[deadalnix]

Do you have a test case where diamond carries are generated for subs ? I'm happy to look into this, but I have no test case.

[deadalnix]

Update logic as requested

[deadalnix]

rebase and ping!

[niravd]

LGTM

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (SDValue Combined = visitADDCARRYLike(N0, N1, CarryIn, N))
     return Combined;
 
   if (SDValue Combined = visitADDCARRYLike(N1, N0, CarryIn, N))
     return Combined;
 
   return SDValue();
 }
 
+/**
+ * If we are facing some sort of diamond carry propapagtion pattern try to
+ * break it up to generate something like:
+ *   (addcarry X, 0, (addcarry A, B, Z):Carry)
+ *
+ * The end result is usually an increase in operation required, but because the
+ * carry is now linearized, other tranforms can kick in and optimize the DAG.
+ *
+ * Patterns typically look something like
+ *            (uaddo A, B)
+ *             /       \
+ *          Carry      Sum
+ *            |          \
+ *            | (addcarry *, 0, Z)
+ *            |       /
+ *             \   Carry
+ *              |   /
+ * (addcarry X, *, *)
+ *
+ * But numerous variation exist. Our goal is to identify A, B, X and Z and
+ * produce a combine with a single path for carry propagation.
+ */
+static SDValue combineADDCARRYDiamond(DAGCombiner &Combiner, SelectionDAG &DAG,
+                                      SDValue X, SDValue Carry0, SDValue Carry1,
+                                      SDNode *N) {
+  if (Carry1.getResNo() != 1 || Carry0.getResNo() != 1)
+    return SDValue();
+  if (Carry1.getOpcode() != ISD::UADDO)
+    return SDValue();
+
+  SDValue Z;
+
+  /**
+   * First look for a suitable Z. It will present itself in the form of
+   * (addcarry Y, 0, Z) or its equivalent (uaddo Y, 1) for Z=true
+   */
+  if (Carry0.getOpcode() == ISD::ADDCARRY &&
+      isNullConstant(Carry0.getOperand(1))) {
+    Z = Carry0.getOperand(2);
+  } else if (Carry0.getOpcode() == ISD::UADDO &&
+             isOneConstant(Carry0.getOperand(1))) {
+    EVT VT = Combiner.getSetCCResultType(Carry0.getValueType());
+    Z = DAG.getConstant(1, SDLoc(Carry0.getOperand(1)), VT);
+  } else {
+    // We couldn't find a suitable Z.
+    return SDValue();
+  }
+
+
+  auto cancelDiamond = [&](SDValue A,SDValue B) {
+    SDLoc DL(N);
+    SDValue NewY = DAG.getNode(ISD::ADDCARRY, DL, Carry0->getVTList(), A, B, Z);
+    Combiner.AddToWorklist(NewY.getNode());
+    return DAG.getNode(ISD::ADDCARRY, DL, N->getVTList(), X,
+                       DAG.getConstant(0, DL, X.getValueType()),
+                       NewY.getValue(1));
+  };
+
+  /**
+   *      (uaddo A, B)
+   *           |
+   *          Sum
+   *           |
+   * (addcarry *, 0, Z)
+   */
+  if (Carry0.getOperand(0) == Carry1.getValue(0)) {
+    return cancelDiamond(Carry1.getOperand(0), Carry1.getOperand(1));
+  }
+
+  /**
+   * (addcarry A, 0, Z)
+   *         |
+   *        Sum
+   *         |
+   *  (uaddo *, B)
+   */
+  if (Carry1.getOperand(0) == Carry0.getValue(0)) {
+    return cancelDiamond(Carry0.getOperand(0), Carry1.getOperand(1));
+  }
+
+  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) {
   // 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 && N0.getResNo() == 0)) &&
       isNullConstant(N1) && !N->hasAnyUseOfValue(1))
     return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(),
                        N0.getOperand(0), N0.getOperand(1), CarryIn);
 
   /**
    * When one of the addcarry argument is itself a carry, we may be facing
    * a diamond carry propagation. In which case we try to transform the DAG
    * to ensure linear carry propagation if that is possible.
-   *
-   * We are trying to get:
-   *   (addcarry X, 0, (addcarry A, B, Z):Carry)
    */
   if (auto Y = getAsCarry(TLI, N1)) {
-    /**
-     *            (uaddo A, B)
-     *             /       \
-     *          Carry      Sum
-     *            |          \
-     *            | (addcarry *, 0, Z)
-     *            |       /
-     *             \   Carry
-     *              |   /
-     * (addcarry X, *, *)
-     */
-    if (Y.getOpcode() == ISD::UADDO &&
-        CarryIn.getResNo() == 1 &&
-        CarryIn.getOpcode() == ISD::ADDCARRY &&
-        isNullConstant(CarryIn.getOperand(1)) &&
-        CarryIn.getOperand(0) == Y.getValue(0)) {
-      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));
-    }
+    // Because both are carries, Y and Z can be swapped.
+    if (auto R = combineADDCARRYDiamond(*this, DAG, N0, Y, CarryIn, N))
+      return R;
+    if (auto R = combineADDCARRYDiamond(*this, DAG, N0, CarryIn, Y, N))
+      return R;
   }
 
   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,

llvm/test/CodeGen/X86/addcarry.ll

; CHECK-NEXT:    retq
   %1 = xor i128 %n, -1
   %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:    notq %rsi
-; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    movb $1, %cl
+; CHECK-NEXT:    addb $-1, %cl
 ; CHECK-NEXT:    movq %rdi, %rcx
-; CHECK-NEXT:    addq %rsi, %rcx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addq $1, %rcx
-; CHECK-NEXT:    adcq %rdi, %rax
+; 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/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:    xorl %edi, %edi
-; CHECK-NEXT:    addq (%rsi), %rdx
-; CHECK-NEXT:    setb %dil
-; CHECK-NEXT:    addq $1, %rdx
-; CHECK-NEXT:    adcq 8(%rsi), %rdi
-; CHECK-NEXT:    setb %r10b
-; CHECK-NEXT:    movzbl %r10b, %r10d
+; CHECK-NEXT:    movb $1, %bl
+; CHECK-NEXT:    addb $-1, %bl
+; CHECK-NEXT:    adcq %r10, %rdx
+; CHECK-NEXT:    adcq $0, %rdi
+; CHECK-NEXT:    setb %dl
+; CHECK-NEXT:    movzbl %dl, %edx
 ; CHECK-NEXT:    notq %rcx
 ; CHECK-NEXT:    addq %rdi, %rcx
-; CHECK-NEXT:    adcq 16(%rsi), %r10
-; CHECK-NEXT:    setb %dil
-; CHECK-NEXT:    movzbl %dil, %edi
+; CHECK-NEXT:    adcq 16(%rsi), %rdx
+; CHECK-NEXT:    setb %bl
+; CHECK-NEXT:    movzbl %bl, %edi
 ; CHECK-NEXT:    notq %r8
-; CHECK-NEXT:    addq %r10, %r8
+; CHECK-NEXT:    addq %rdx, %r8
 ; CHECK-NEXT:    adcq 24(%rsi), %rdi
 ; CHECK-NEXT:    notq %r9
 ; CHECK-NEXT:    addq %rdi, %r9
-; CHECK-NEXT:    movq %rdx, (%rax)
+; CHECK-NEXT:    movq %r11, (%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