[DAGCombine] Deduplicate addcarry node using commutativity.

[deadalnix]

Summary

The first two parameters of addcarry are commutative. We may face a situation where both variant are present in the DAG, in which case we benefit from using just one.

Depends on D57302 and D33587

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2527 ↗

(On Diff #183811)

We already do this in DAGCombiner::combine for plain commutative binops, is it worth generalizing that code?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2527 ↗

(On Diff #183811)

The problem is that this is not a binary operation so it doesn't fit in the existing machinery. If this end up being common enough, we can generalize.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2527 ↗

(On Diff #183811)

OK - please add a TODO suggesting this. Should the ConstantSDNode handling be done here as well?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2527 ↗

(On Diff #183811)

You mean moving a constant argument on RHS when it is on RHS ?

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2527 ↗

(On Diff #183811)

yes

[deadalnix]

Add a comment about existing commutative ops deduplication logic.

[RKSimon]

LGTM

[RKSimon]

@deadalnix Can this go in now or would you prefer to wait for D33587?

[deadalnix]

@RKSimon This can go now, but has no effect in isolation in any of the test cases I have, mainly because DAGCombine is fairly powerless when faced with addcarry as most of the work involve 'deep' patterns. Do you think I should land anyways ?

[RKSimon]

In D57317#1390578, @deadalnix wrote:

@RKSimon This can go now, but has no effect in isolation in any of the test cases I have, mainly because DAGCombine is fairly powerless when faced with addcarry as most of the work involve 'deep' patterns. Do you think I should land anyways ?

Unless you can add test coverage now I think this will have to wait.

[RKSimon]

@deadalnix What is the state of this patch now?

[deadalnix]

Rebased on top of D64174 , which expose many instances of this pattern.

[deadalnix]

Update for the monorepo

[RKSimon]

@deadalnix Is this likely to be committed anytime soon ?

[deadalnix]

@RKSimon It is good to go, the main problem here is that I don't have a test case for it in isolation, and I have been struggling to get the pieces in where this really shines (mostly related to process the DAG topologically).

[chfast]

I added tests for this change.
https://reviews.llvm.org/rGe399c5877801
https://github.com/llvm/llvm-project/commit/e399c58778017388a818cabd1b13fcb88b79a432

Please rebase.

[chfast]

Rebased.

[RKSimon]

Thanks @chfast!

[chfast]

Is it fine I commit this?

[RKSimon]

In D57317#3829385, @chfast wrote:

Is it fine I commit this?

Sure, but please make sure you tag it by Amaury Séchet <[e-mail]>

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitADDCARRY(SDNode *N) {
   }
 
   if (SDValue Combined = visitADDCARRYLike(N0, N1, CarryIn, N))
     return Combined;
 
   if (SDValue Combined = visitADDCARRYLike(N1, N0, CarryIn, N))
     return Combined;
 
+  // We want to avoid useless duplication.
+  // TODO: This is done automatically for binary operations. As ADDCARRY is
+  // not a binary operation, this is not really possible to leverage this
+  // existing mechanism for it. However, if more operations require the same
+  // deduplication logic, then it may be worth generalize.
+  SDValue Ops[] = {N1, N0, CarryIn};
+  SDNode *CSENode =
+      DAG.getNodeIfExists(ISD::ADDCARRY, N->getVTList(), Ops, N->getFlags());
+  if (CSENode)
+    return SDValue(CSENode, 0);
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitSADDO_CARRY(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDValue CarryIn = N->getOperand(2);
   SDLoc DL(N);

llvm/test/CodeGen/X86/addcarry.ll

; CHECK-NEXT:    retq
   %z = zext i1 %k to i32
   %r = add i32 %s, %z
   ret i32 %r
 }
 
 define { i64, i64 } @addcarry_commutative_1(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 ; CHECK-LABEL: addcarry_commutative_1:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    addq %rdx, %rax
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    adcq %rcx, %rax
 ; CHECK-NEXT:    addq %rdx, %rdi
-; CHECK-NEXT:    adcq %rcx, %rsi
-; CHECK-NEXT:    movq %rsi, %rdx
+; CHECK-NEXT:    adcq %rcx, %rax
+; CHECK-NEXT:    movq %rax, %rdx
 ; CHECK-NEXT:    retq
   %z0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
   %k0 = extractvalue { i64, i1 } %z0, 1
   %k0z = zext i1 %k0 to i64
 
   %t1s = add i64 %x1, %y1
   %z1s = add i64 %t1s, %k0z
 
   ; same as the above, but args swapped
   %a1s = add i64 %y1, %x1
   %b1s = add i64 %a1s, %k0z
 
   %r0 = insertvalue { i64, i64 } poison, i64 %z1s, 0
   %r1 = insertvalue { i64, i64 } %r0, i64 %b1s, 1
   ret { i64, i64 } %r1
 }
 
 define { i64, i64 } @addcarry_commutative_2(i64 %x0, i64 %x1, i64 %y0, i64 %y1) nounwind {
 ; CHECK-LABEL: addcarry_commutative_2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    addq %rdx, %rax
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    adcq %rcx, %rax
 ; CHECK-NEXT:    addq %rdx, %rdi
-; CHECK-NEXT:    adcq %rcx, %rsi
-; CHECK-NEXT:    movq %rsi, %rdx
+; CHECK-NEXT:    adcq %rcx, %rax
+; CHECK-NEXT:    movq %rax, %rdx
 ; CHECK-NEXT:    retq
   %z0 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x0, i64 %y0)
   %k0 = extractvalue { i64, i1 } %z0, 1
   %k0z = zext i1 %k0 to i64
 
   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %x1, i64 %y1)
   %t1s = extractvalue { i64, i1 } %t1, 0
   %z1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %t1s, i64 %k0z)