[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

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

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2527

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

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

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2527

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

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2527

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]>

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.
+  SDValue Ops[] = {N1, N0, CarryIn};
+  SDNode *CSENode = DAG.getNodeIfExists(ISD::ADDCARRY, N->getVTList(), Ops,
+                                        N->getFlags());
+  if (CSENode)
+    return SDValue(CSENode, 0);
+
   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)
  *

test/CodeGen/X86/addcarry.ll

 
 %S = type { [4 x i64] }
 
 define %S @readd(%S* nocapture readonly %this, %S %arg.b) {
 ; CHECK-LABEL: readd:
 ; CHECK:       # %bb.0: # %entry
 ; 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:    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 %rdx, (%rax)
-; CHECK-NEXT:    movq %r11, 8(%rax)
-; CHECK-NEXT:    movq %rdi, 16(%rax)
-; CHECK-NEXT:    movq %rcx, 24(%rax)
+; CHECK-NEXT:    adcq 8(%rsi), %rcx
+; CHECK-NEXT:    adcq 16(%rsi), %r8
+; CHECK-NEXT:    adcq 24(%rsi), %r9
+; CHECK-NEXT:    movq %rdx, (%rdi)
+; CHECK-NEXT:    movq %rcx, 8(%rdi)
+; CHECK-NEXT:    movq %r8, 16(%rdi)
+; CHECK-NEXT:    movq %r9, 24(%rdi)
 ; 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:    movq (%rsi), %rdi
-; CHECK-NEXT:    movq 8(%rsi), %r10
+; CHECK-NEXT:    notq %rdx
+; CHECK-NEXT:    leaq 1(%rdi,%rdx), %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:    adcq %rdi, %rdx
 ; CHECK-NEXT:    notq %rcx
-; 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:    adcq 8(%rsi), %rcx
 ; CHECK-NEXT:    notq %r8
-; 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:    adcq 16(%rsi), %r8
 ; CHECK-NEXT:    notq %r9
 ; 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 %r10, (%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