[DAGCombiner] fold (add (add (xor a, -1), b), 1) -> (sub b, a)

[deadalnix]

Summary

This pattern is sometime created after legalization.

[lebedev.ri]

Looks sane https://rise4fun.com/Alive/Nfiz
But looks like it's missed in instcombine too?
https://godbolt.org/z/UdEwql

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2196–2197 ↗

(On Diff #189047)

Tests?

[RKSimon]

vector test?

[deadalnix]

It is interesting that instcombine doesn't do this. I would have expected it to be the case. Let me prepare a patch for it.

[deadalnix]

I made the patch for InstCombine: D58877

[spatel]

If this pattern can emerge during legalization, then yes, we want a DAG combine for it. There's also a question raised in the IR version of the patch (D58877) about a reassociated version of this pattern. We don't have a dedicated reassociation pass for SDAG, so DAGCombine is responsible for handling that pattern too. Do we already have it, or should it be added too (as a separate DAG patch)?

[deadalnix]

All the pattern I submit in DAGCombiner are extracted from actual code -in this case libraries doing cryptography). I never encountered the vector version of this but I'm happy to add test cases for them if this is of interest.

[deadalnix]

Rebase and regenerate tests introduced in rL355400

[RKSimon]

Please can you rebase after rL355699 ?

[deadalnix]

Update to reflect change in tests (the vector test had an incorrect constant in it).

[RKSimon]

LGTM

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitADD(SDNode *N) {
   if (SimplifyDemandedBits(SDValue(N, 0)))
     return SDValue(N, 0);
 
   // fold (a+b) -> (a|b) iff a and b share no bits.
   if ((!LegalOperations || TLI.isOperationLegal(ISD::OR, VT)) &&
       DAG.haveNoCommonBitsSet(N0, N1))
     return DAG.getNode(ISD::OR, DL, VT, N0, N1);
 
+  if (isOneOrOneSplat(N1)) {
     // fold (add (xor a, -1), 1) -> (sub 0, a)
-  if (isBitwiseNot(N0) && isOneOrOneSplat(N1))
+    if (isBitwiseNot(N0))
       return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT),
                          N0.getOperand(0));
 
+    // fold (add (add (xor a, -1), b), 1) -> (sub b, a)
+    if (N0.getOpcode() == ISD::ADD ||
+        N0.getOpcode() == ISD::UADDO ||
+        N0.getOpcode() == ISD::SADDO) {
+      SDValue A, Xor;
+
+      if (isBitwiseNot(N0.getOperand(0))) {
+        A = N0.getOperand(1);
+        Xor = N0.getOperand(0);
+      } else if (isBitwiseNot(N0.getOperand(1))) {
+        A = N0.getOperand(0);
+        Xor = N0.getOperand(1);
+      }
+
+      if (Xor)
+        return DAG.getNode(ISD::SUB, DL, VT, A, Xor.getOperand(0));
+    }
+  }
+
   if (SDValue Combined = visitADDLike(N0, N1, N))
     return Combined;
 
   if (SDValue Combined = visitADDLike(N1, N0, N))
     return Combined;
 
   return SDValue();
 }

llvm/trunk/test/CodeGen/X86/add.ll

; X64-WIN32-NEXT:    retq
   store i1 %r1, i1* %p1
   ret void
 }
 
 define i32 @add_to_sub(i32 %a, i32 %b) {
 ; X32-LABEL: add_to_sub:
 ; X32:       # %bb.0:
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    notl %ecx
-; X32-NEXT:    leal 1(%ecx,%eax), %eax
+; X32-NEXT:    subl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    retl
 ;
 ; X64-LINUX-LABEL: add_to_sub:
 ; X64-LINUX:       # %bb.0:
-; X64-LINUX-NEXT:    # kill: def $esi killed $esi def $rsi
-; X64-LINUX-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-LINUX-NEXT:    notl %edi
-; X64-LINUX-NEXT:    leal 1(%rdi,%rsi), %eax
+; X64-LINUX-NEXT:    movl %esi, %eax
+; X64-LINUX-NEXT:    subl %edi, %eax
 ; X64-LINUX-NEXT:    retq
 ;
 ; X64-WIN32-LABEL: add_to_sub:
 ; X64-WIN32:       # %bb.0:
-; X64-WIN32-NEXT:    # kill: def $edx killed $edx def $rdx
-; X64-WIN32-NEXT:    # kill: def $ecx killed $ecx def $rcx
-; X64-WIN32-NEXT:    notl %ecx
-; X64-WIN32-NEXT:    leal 1(%rcx,%rdx), %eax
+; X64-WIN32-NEXT:    movl %edx, %eax
+; X64-WIN32-NEXT:    subl %ecx, %eax
 ; X64-WIN32-NEXT:    retq
   %nota = xor i32 %a, -1
   %add = add i32 %nota, %b
   %r = add i32 %add, 1
   ret i32 %r
 }
 
 declare void @bar_i32(i32)

llvm/trunk/test/CodeGen/X86/combine-add.ll

 ; AVX-NEXT:    vpaddd %xmm1, %xmm0, %xmm0
 ; AVX-NEXT:    retq
   %1 = shl <4 x i32> %a0, <i32 31, i32 31, i32 31, i32 31>
   %2 = ashr <4 x i32> %1, <i32 31, i32 31, i32 31, i32 31>
   %3 = add <4 x i32> %2, %a1
   ret <4 x i32> %3
 }
 
-; TODO: (add (add (xor a, -1), b), 1) -> (sub b, a)
+; (add (add (xor a, -1), b), 1) -> (sub b, a)
 define i32 @combine_add_add_not(i32 %a, i32 %b) {
 ; SSE-LABEL: combine_add_add_not:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    # kill: def $esi killed $esi def $rsi
-; SSE-NEXT:    # kill: def $edi killed $edi def $rdi
-; SSE-NEXT:    notl %edi
-; SSE-NEXT:    leal 1(%rdi,%rsi), %eax
+; SSE-NEXT:    movl %esi, %eax
+; SSE-NEXT:    subl %edi, %eax
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_add_add_not:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    # kill: def $esi killed $esi def $rsi
-; AVX-NEXT:    # kill: def $edi killed $edi def $rdi
-; AVX-NEXT:    notl %edi
-; AVX-NEXT:    leal 1(%rdi,%rsi), %eax
+; AVX-NEXT:    movl %esi, %eax
+; AVX-NEXT:    subl %edi, %eax
 ; AVX-NEXT:    retq
   %nota = xor i32 %a, -1
   %add = add i32 %nota, %b
   %r = add i32 %add, 1
   ret i32 %r
 }
 
 define <4 x i32> @combine_vec_add_add_not(<4 x i32> %a, <4 x i32> %b) {
 ; SSE-LABEL: combine_vec_add_add_not:
 ; SSE:       # %bb.0:
-; SSE-NEXT:    pcmpeqd %xmm2, %xmm2
-; SSE-NEXT:    pxor %xmm2, %xmm0
-; SSE-NEXT:    paddd %xmm1, %xmm0
-; SSE-NEXT:    psubd %xmm2, %xmm0
+; SSE-NEXT:    psubd %xmm0, %xmm1
+; SSE-NEXT:    movdqa %xmm1, %xmm0
 ; SSE-NEXT:    retq
 ;
 ; AVX-LABEL: combine_vec_add_add_not:
 ; AVX:       # %bb.0:
-; AVX-NEXT:    vpcmpeqd %xmm2, %xmm2, %xmm2
-; AVX-NEXT:    vpxor %xmm2, %xmm0, %xmm0
-; AVX-NEXT:    vpaddd %xmm1, %xmm0, %xmm0
-; AVX-NEXT:    vpsubd %xmm2, %xmm0, %xmm0
+; AVX-NEXT:    vpsubd %xmm0, %xmm1, %xmm0
 ; AVX-NEXT:    retq
   %nota = xor <4 x i32> %a, <i32 -1, i32 -1, i32 -1, i32 -1>
   %add = add <4 x i32> %nota, %b
   %r = add <4 x i32> %add, <i32 1, i32 1, i32 1, i32 1>
   ret <4 x i32> %r
 }