[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);