[DAGCombine] Combine composition of ADDC(ADDE)

[zvi]

Summary

fold (addc X, (adde Y, 0, Carry)) -> (adde X, Y, Carry)

One step towards improving pr31719

[zvi]

test/CodeGen/X86/mul-i1024.ll

4383 ↗

(On Diff #86241)

FWIW, this file is 11 lines shorter

test/CodeGen/X86/mul-i512.ll

5 ↗

(On Diff #86241)

FWIW, this file is 8 lines shorter

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

Is that important to check this has only one use ? I'd assume that having (adde Y, 0, Carry) + (adde X, Y, Carry) is still preferable to (addc X, (adde Y, 0, Carry)) as it break dependencies between instructions.

[zvi]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

That's a fair point, but here I am following the practice that is common in the DAG Combiner. If you search for "hasOneUse" or "isOnlyUserOf" you can see the conservative approach of avoiding increase in instruction count.
If you can provide a benchmark that can show this case is an exception, we can discuss the trade-off with data to guide us - and better do it in a follow-up patch.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

Are there any situations where the inner ADDE's carry flag will be used by something else?

[zvi]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

The carry's type is glue, so by definition it can have a single user, right?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

If you search for "hasOneUse" or "isOnlyUserOf" you can see the conservative approach of avoiding increase in instruction count.

I don't think this is a valid concern in that case. If the instruction has more than one use, you get 2 instructions before and 2 after. So I don't think this apply in that case.

However, I'm not sure about the glue. It may indeed be the case that it is expected that a glue is used only once (that would make sense). In which case maybe a adding comment is a good thing because if it is not obvious to us now, it won't be to some dude reading this in a few month without context.

[zvi]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

You can see for yourself the results of your suggestion by applying this patch and running 'make check-llvm'.
At least the tests 'mul-i1024.ll' and 'mul-i512.ll' will be affected by this change. You will see the instruction count will increase. Not saying this is necessarily undesirable, but it requires additional work of convincing ourselves that the larger code is faster.

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

Alright, I think this is moot anyway. I'm not sure this transformation is valid if Y may be all ones. adde would generate a carry, but the addc would not, after the transformation, it would generate a carry.

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

I suggest something like:

// (addc X, (adde Y, 0, Carry)) -> (adde X, Y, Carry) if Y + 1 cannot overflow.
if (N1.getOpcode() == ISD::ADDE &&
    N->isOnlyUserOf(N1.getValue(0).getNode()) &&
    isNullConstant(N1.getOperand(1))) {
  APInt YZero, YOne;
  DAG.computeKnownBits(N1.getOperand(0), YZero, YOne);
  if (YZero)
    return DAG.getNode(ISD::ADDE, SDLoc(N), N->getVTList(), N0,
                       N1->getOperand(0), N1->getOperand(2));
}

[zvi]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

Sorry, it would have been clearer if i wrote: ".. by applying this patch only without the condtion of '&&

N->isOnlyUserOf(N1.getValue(0).getNode())'

1872

Good catch. Thanks

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1872

For what it's worth, in the meantime, I did https://reviews.llvm.org/D29443 which solve the whole thing. This pattern is part of the solution.

[deadalnix]

Shall we close this one in favor of D29443 ?

[zvi]

Following @deadalnix's suggestion for special case where Y is all ones. Thanks!

[zvi]

In D29268#666957, @deadalnix wrote:

Shall we close this one in favor of D29443 ?

I don't mind abandoning this patch in favor of D29443, but if possible, i think you should break D29443 into several patches. I'm saying this because D29443 adds several new combines and it would be easier to review each combine in a separate patch with tests that show its goodness.
So it may turn out that after breaking D29443, this patch will end-up as the initial patch in a sequence. Does this make sense?

[deadalnix]

I actually posted in that diff asking if I should do this, so yes, it does make sense.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

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 &&
+      N->isOnlyUserOf(N1.getValue(0).getNode()) &&
+      isNullConstant(N1.getOperand(1))) {
+    APInt YZero, YOne;
+    DAG.computeKnownBits(N1.getOperand(0), YZero, YOne);
+    if (YZero != 0)
+      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);
 

test/CodeGen/X86/adde-carry.ll

  store i64 %8, i64* %t, align 8
  ret void
 }
 
 define i64 @pr31719(i64 %.elt, i64 %.elt24, i64 %t1) {
 ; CHECK-LABEL: pr31719:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    addq %rdx, %rdi
-; CHECK-NEXT:    sbbq %rax, %rax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    addq %rsi, %rax
+; CHECK-NEXT:    adcq $0, %rsi
 ; CHECK-NEXT:    sbbq %rax, %rax
 ; CHECK-NEXT:    andl $1, %eax
 ; CHECK-NEXT:    retq
 entry:
   %t2 = zext i64 %t1 to i128
   %t3 = zext i64 %.elt to i128
   %t4 = add nuw nsw i128 %t2, %t3
   %t5 = lshr i128 %t4, 64
   %t6 = zext i64 %.elt24 to i128
   %t7 = add nuw nsw i128 0, %t6
   %t8 = add nuw nsw i128 %t7, %t5
   %t9 = lshr i128 %t8, 64
   %t10 = add nuw nsw i128 0, %t9
   %t11 = trunc i128 %t10 to i64
   ret i64 %t11
 }