[DAGCombiner] Leverage add's commutativity

[deadalnix]

Summary

This avoid the need to duplicate all pattern and actually end up exposing some opportunity to optimize existing pattern that did not exists in both directions on an existing test case.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1795 ↗

(On Diff #87093)

Why not replace SDNode *LocReference by const SDLoc &DL?

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1795 ↗

(On Diff #87093)

I followed the pattern that is used for other visitFOOLike . Also having the node available maybe come up handy if other information are required in the future. I was some factorization could be done between this and visitADDC.

[RKSimon]

LGTM

[deadalnix]

Rebase

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

private:
     // Return Value:
     //   SDValue.getNode() == 0 - No change was made
     //   SDValue.getNode() == N - N was replaced, is dead and has been handled.
     //   otherwise              - N should be replaced by the returned Operand.
     //
     SDValue visitTokenFactor(SDNode *N);
     SDValue visitMERGE_VALUES(SDNode *N);
     SDValue visitADD(SDNode *N);
+    SDValue visitADDLike(SDValue N0, SDValue N1, SDNode *LocReference);
     SDValue visitSUB(SDNode *N);
     SDValue visitADDC(SDNode *N);
     SDValue visitSUBC(SDNode *N);
     SDValue visitADDE(SDNode *N);
     SDValue visitSUBE(SDNode *N);
     SDValue visitMUL(SDNode *N);
     SDValue useDivRem(SDNode *N);
     SDValue visitSDIV(SDNode *N);
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)) &&
       VT.isInteger() && DAG.haveNoCommonBitsSet(N0, N1))
     return DAG.getNode(ISD::OR, DL, VT, N0, N1);
 
+  if (SDValue Combined = visitADDLike(N0, N1, N))
+    return Combined;
+
+  if (SDValue Combined = visitADDLike(N1, N0, N))
+    return Combined;
+
+  return SDValue();
+}
+
+SDValue DAGCombiner::visitADDLike(SDValue N0, SDValue N1, SDNode *LocReference) {
+  EVT VT = N0.getValueType();
+  SDLoc DL(LocReference);
+
   // fold (add x, shl(0 - y, n)) -> sub(x, shl(y, n))
   if (N1.getOpcode() == ISD::SHL && N1.getOperand(0).getOpcode() == ISD::SUB &&
       isNullConstantOrNullSplatConstant(N1.getOperand(0).getOperand(0)))
     return DAG.getNode(ISD::SUB, DL, VT, N0,
                        DAG.getNode(ISD::SHL, DL, VT,
                                    N1.getOperand(0).getOperand(1),
                                    N1.getOperand(1)));
-  if (N0.getOpcode() == ISD::SHL && N0.getOperand(0).getOpcode() == ISD::SUB &&
-      isNullConstantOrNullSplatConstant(N0.getOperand(0).getOperand(0)))
-    return DAG.getNode(ISD::SUB, DL, VT, N1,
-                       DAG.getNode(ISD::SHL, DL, VT,
-                                   N0.getOperand(0).getOperand(1),
-                                   N0.getOperand(1)));
 
   if (N1.getOpcode() == ISD::AND) {
     SDValue AndOp0 = N1.getOperand(0);
     unsigned NumSignBits = DAG.ComputeNumSignBits(AndOp0);
     unsigned DestBits = VT.getScalarSizeInBits();
 
     // (add z, (and (sbbl x, x), 1)) -> (sub z, (sbbl x, x))
     // and similar xforms where the inner op is either ~0 or 0.

llvm/trunk/test/CodeGen/X86/adde-carry.ll

  ret void
 }
 
 define void @b(i32* nocapture %r, i64 %a, i64 %b, i32 %c) nounwind {
 ; CHECK-LABEL: b:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    addq %rdx, %rsi
 ; CHECK-NEXT:    sbbq %rax, %rax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    addl %ecx, %eax
-; CHECK-NEXT:    movl %eax, (%rdi)
+; CHECK-NEXT:    subl %eax, %ecx
+; CHECK-NEXT:    movl %ecx, (%rdi)
 ; CHECK-NEXT:    retq
 entry:
  %0 = zext i64 %a to i128
  %1 = zext i64 %b to i128
  %2 = zext i32 %c to i128
  %3 = add i128 %1, %0
  %4 = lshr i128 %3, 64
  %5 = add i128 %4, %2
  %6 = trunc i128 %5 to i32
  store i32 %6, i32* %r, align 4
  ret void
 }
 
 define void @c(i16* nocapture %r, i64 %a, i64 %b, i16 %c) nounwind {
 ; CHECK-LABEL: c:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    addq %rdx, %rsi
 ; CHECK-NEXT:    sbbq %rax, %rax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    addl %ecx, %eax
-; CHECK-NEXT:    movw %ax, (%rdi)
+; CHECK-NEXT:    subl %eax, %ecx
+; CHECK-NEXT:    movw %cx, (%rdi)
 ; CHECK-NEXT:    retq
 entry:
  %0 = zext i64 %a to i128
  %1 = zext i64 %b to i128
  %2 = zext i16 %c to i128
  %3 = add i128 %1, %0
  %4 = lshr i128 %3, 64
  %5 = add i128 %4, %2
  %6 = trunc i128 %5 to i16
  store i16 %6, i16* %r, align 4
  ret void
 }
 
 define void @d(i8* nocapture %r, i64 %a, i64 %b, i8 %c) nounwind {
 ; CHECK-LABEL: d:
 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    addq %rdx, %rsi
 ; CHECK-NEXT:    sbbq %rax, %rax
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    addl %ecx, %eax
-; CHECK-NEXT:    movb %al, (%rdi)
+; CHECK-NEXT:    subl %eax, %ecx
+; CHECK-NEXT:    movb %cl, (%rdi)
 ; CHECK-NEXT:    retq
 entry:
  %0 = zext i64 %a to i128
  %1 = zext i64 %b to i128
  %2 = zext i8 %c to i128
  %3 = add i128 %1, %0
  %4 = lshr i128 %3, 64
  %5 = add i128 %4, %2

 ; CHECK:       # BB#0: # %entry
 ; CHECK-NEXT:    movq %rdx, %rax
 ; CHECK-NEXT:    mulq %rsi
 ; CHECK-NEXT:    addq (%rdi), %rax
 ; CHECK-NEXT:    adcq $0, %rdx
 ; CHECK-NEXT:    movq %rax, (%rdi)
 ; CHECK-NEXT:    addq 8(%rdi), %rdx
 ; CHECK-NEXT:    sbbq %rax, %rax
-; CHECK-NEXT:    andl $1, %eax
 ; CHECK-NEXT:    movq %rdx, 8(%rdi)
-; CHECK-NEXT:    addl %eax, 16(%rdi)
+; CHECK-NEXT:    subl %eax, 16(%rdi)
 ; CHECK-NEXT:    retq
 entry:
   %0 = zext i64 %arg.a to i128
   %1 = zext i64 %arg.b to i128
   %2 = mul nuw i128 %1, %0
   %3 = getelementptr inbounds %accumulator, %accumulator* %this, i64 0, i32 0
   %4 = load i64, i64* %3, align 8
   %5 = zext i64 %4 to i128