[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

2543

usualy->usually

2544

linarized->linearized

2588

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

2539

ddamoni ? paternq?

2619

Don't use auto

2624

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

103

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

103

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

2582

nit: make the failing case here an else clause.

2615

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

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 ddamoni carry propapagtion patternq 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 A = Carry1.getOperand(0);
+  SDValue B = Carry1.getOperand(1);
+  SDValue Y = Carry0.getOperand(0);
+
+  SDValue Z;
+  bool DoIt = false;
+
+  /**
+   * 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);
+  }
+
+  // We couldn't find a suitable Z.
+  if (!Z) return SDValue();
+
+  /**
+   *      (uaddo A, B)
+   *           |
+   *          Sum
+   *           |
+   * (addcarry *, 0, Z)
+   */
+  if (Y == Carry1.getValue(0)) {
+    DoIt = true;
+  }
+
+  /**
+   * (addcarry A, 0, Z)
+   *         |
+   *        Sum
+   *         |
+   *  (uaddo *, B)
+   */
+  if (Carry1.getOperand(0) == Carry0.getValue(0)) {
+    A = Y;
+    DoIt = true;
+  } else if (Carry1.getOperand(1) == Carry0.getValue(0)) {
+    B = Y;
+    DoIt = true;
+  }
+
+  if (DoIt) {
+    SDLoc DL(N);
+    auto 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));
+  }
+
+  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);
 
+  DeepPatternNodes.insert(N);
+
   /**
    * 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,

test/CodeGen/X86/addcarry.ll

entry:
   ret i64 %6
 }
 
 %S = type { [4 x i64] }
 
 define %S @readd(%S* nocapture readonly %this, %S %arg.b) {
 ; CHECK-LABEL: readd:
 ; 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:    addq (%rsi), %rdx
-; CHECK-NEXT:    movq 8(%rsi), %r11
-; CHECK-NEXT:    adcq $0, %r11
-; CHECK-NEXT:    setb %r10b
-; CHECK-NEXT:    movzbl %r10b, %edi
-; CHECK-NEXT:    addq %rcx, %r11
-; CHECK-NEXT:    adcq 16(%rsi), %rdi
+; CHECK-NEXT:    movq (%rsi), %r10
+; CHECK-NEXT:    movq %rdx, %rdi
+; CHECK-NEXT:    addq %r10, %rdi
+; CHECK-NEXT:    movq 8(%rsi), %rdi
+; CHECK-NEXT:    movq 16(%rsi), %r11
+; CHECK-NEXT:    movq %rcx, %rbx
+; CHECK-NEXT:    adcq %rdi, %rbx
+; CHECK-NEXT:    addq %r10, %rdx
+; CHECK-NEXT:    adcq %rdi, %rcx
 ; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    movzbl %cl, %ecx
-; CHECK-NEXT:    addq %r8, %rdi
-; CHECK-NEXT:    adcq 24(%rsi), %rcx
-; CHECK-NEXT:    addq %r9, %rcx
+; CHECK-NEXT:    movq %r8, %rdi
+; CHECK-NEXT:    adcq %r11, %rdi
+; CHECK-NEXT:    addb $255, %cl
+; CHECK-NEXT:    adcq %r11, %r8
+; CHECK-NEXT:    adcq 24(%rsi), %r9
 ; CHECK-NEXT:    movq %rdx, (%rax)
-; CHECK-NEXT:    movq %r11, 8(%rax)
+; CHECK-NEXT:    movq %rbx, 8(%rax)
 ; CHECK-NEXT:    movq %rdi, 16(%rax)
-; CHECK-NEXT:    movq %rcx, 24(%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

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:    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:    movq (%rsi), %rdi
+; CHECK-NEXT:    movq 8(%rsi), %r10
+; CHECK-NEXT:    movb $1, %r11b
+; CHECK-NEXT:    addb $-1, %r11b
+; CHECK-NEXT:    leaq 1(%rdi,%rdx), %r11
+; CHECK-NEXT:    adcq %rdx, %rdi
 ; 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:    setb %dl
+; CHECK-NEXT:    movq %rcx, %rdi
+; CHECK-NEXT:    adcq %r10, %rdi
+; CHECK-NEXT:    movq 16(%rsi), %rbx
+; CHECK-NEXT:    addb $255, %dl
+; CHECK-NEXT:    adcq %r10, %rcx
 ; CHECK-NEXT:    notq %r8
-; CHECK-NEXT:    addq %r10, %r8
-; CHECK-NEXT:    adcq 24(%rsi), %rdi
+; CHECK-NEXT:    setb %cl
+; CHECK-NEXT:    movq %r8, %rdx
+; CHECK-NEXT:    adcq %rbx, %rdx
+; CHECK-NEXT:    addb $255, %cl
+; CHECK-NEXT:    adcq %rbx, %r8
 ; CHECK-NEXT:    notq %r9
-; CHECK-NEXT:    addq %rdi, %r9
-; CHECK-NEXT:    movq %rdx, (%rax)
-; CHECK-NEXT:    movq %rcx, 8(%rax)
-; CHECK-NEXT:    movq %r8, 16(%rax)
+; CHECK-NEXT:    adcq 24(%rsi), %r9
+; CHECK-NEXT:    movq %r11, (%rax)
+; CHECK-NEXT:    movq %rdi, 8(%rax)
+; CHECK-NEXT:    movq %rdx, 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