[DAGCombine] (add/uaddo X, Carry) -> (addcarry X, 0, Carry)

[deadalnix]

Summary

This enables further transforms.

Depends on D32916

[deadalnix]

Rebase on changes from D32916 .

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1985

As was discussed on D32916, the carry is a boolean that will respect TargetLowering::BooleanContent so we can't just accept any extension - it has to match the bool type.

test/CodeGen/X86/add-of-carry.ll

16

This is annoying....

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1985

This just follow the chain to see if there is a carry generating ops at the end. This isn't generating anything, so I'm not sure what the problem is.

test/CodeGen/X86/add-of-carry.ll

16

I have a patch making this better. However, it has to be noted that this code is very unrepresentative from code in the field, as it essentially does a + b + carry(a, b) . This is fine to test this as it exercise edge cases, but if the tradeof is between that specific sample vs any actual sample code extracted from existing software (which I'm doing with this lagre int optimization serie) I'd rather go for the one that is actually used.

[deadalnix]

Ping ?

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1985

In this case, we're taking a boolean carry value and using it as an operand for a new ADDCARRY node that has the same boolean content requirement, so I think this part is ok.

Given that it's not clear from reading the code, please add a comment to explain the logic.

cc'ing @efriedma in case he sees a hole in that reasoning.

1987

Shouldn't this be: "If this is *not* a use of a carry bit, return." ?

2047

Just looking at that transform formula, it's not clear to me why it makes sense. We're turning a simple op into a more complicated op and creating a new constant operand.

Is it because there will always be a trunc/extend/mask op sitting between the carry and the add? Should we check or assert that?

In the first test case, we're going to eventually fold the addcarry with 0 operand with a uaddo. Would it make sense to have that fold directly?

I don't have a sense of how these folds work together, so if we do need this more general fold, we should have a comment to explain why it is generally good.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1985

"X + (sext Carry)" clearly produces a different result from "X + (zext carry)"; I can't see how it makes sense to ignore the difference.

[spatel]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1985

Ah, right. So yes, Simon's observation was correct. We need to match whatever this node is to the boolean content type.

So I think that's more reason to make specific folds for the actual patterns that are causing problems for this codegen.

[deadalnix]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1985

It has to match the bool type and this one is correct. But if the bool type isn't 1/0 the end result is different. We need to avoid matching SEXT and ANY_EXT here and validate that the flag is of the form 0/1 ot that a (and X, 1) is present along the way.

1987

Yes, you are correct. Fixing.

2047

In practice this is better. When taking the carry as an argument, it is necessary to materialize it, which takes a register and an instruction to copy the carry from the flag register to a general purpose register. On the other hand, when passing the carry down as carry, there are usually some predicated instruction that can be used.

In addition, there are various combine you can do on top of that form, for instance if X is (add A, B) you end up with (addcarry A, B, Carry) which is preferable.

[deadalnix]

Do not match sext and any_ext as this is invalid.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1985

and validate that the flag is of the form 0/1 ot that a (and X, 1) is present along the way.

I don't see any code in the current version to do this?

[deadalnix]

Check the kind of bool being generated as carry.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

1981

// First, peel away TRUNCATE/ZERO_EXTEND/AND nodes due to legalization.

2048

use SDValue not auto

2137

use SDValue not auto

[deadalnix]

Comments

[RKSimon]

LGTM

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (SDValue Combined = visitADDLike(N0, N1, N))
     return Combined;
 
   if (SDValue Combined = visitADDLike(N1, N0, N))
     return Combined;
 
   return SDValue();
 }
 
+static SDValue getAsCarry(SDValue V) {
+  // First, peel away truncation and and due to legalization.
+  while (V.getOpcode() == ISD::TRUNCATE ||
+         V.getOpcode() == ISD::ZERO_EXTEND ||
+         V.getOpcode() == ISD::SIGN_EXTEND ||
+         V.getOpcode() == ISD::ANY_EXTEND ||
+         (V.getOpcode() == ISD::AND && isOneConstant(V.getOperand(1))))
+      V = V.getOperand(0);
+
+  // If this is a carry, return.
+  if (V.getResNo() != 1)
+    return SDValue();
+
+  if (V.getOpcode() == ISD::ADDCARRY ||
+      V.getOpcode() == ISD::SUBCARRY ||
+      V.getOpcode() == ISD::UADDO ||
+      V.getOpcode() == ISD::USUBO)
+    return V;
+
+  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,
if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
     }
   }
 
   // (add X, (addcarry Y, 0, Carry)) -> (addcarry X, Y, Carry)
   if (N1.getOpcode() == ISD::ADDCARRY && isNullConstant(N1.getOperand(1)))
     return DAG.getNode(ISD::ADDCARRY, DL, N1->getVTList(),
                        N0, N1.getOperand(0), N1.getOperand(2));
 
+  // (add X, Carry) -> (addcarry X, 0, Carry)
+  if (auto Carry = getAsCarry(N1))
+    return DAG.getNode(ISD::ADDCARRY, DL,
+                       DAG.getVTList(VT, Carry.getValueType()), N0,
+                       DAG.getConstant(0, DL, VT), Carry);
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDC(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   SDLoc DL(N);
SDValue DAGCombiner::visitUADDOLike(SDValue N0, SDValue N1, SDNode *N) {
   if (N1.getOpcode() == ISD::ADDCARRY && isNullConstant(N1.getOperand(1))) {
     SDValue Y = N1.getOperand(0);
     SDValue One = DAG.getConstant(1, SDLoc(N), Y.getValueType());
     if (DAG.computeOverflowKind(Y, One) == SelectionDAG::OFK_Never)
       return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(), N0, Y,
                          N1.getOperand(2));
   }
 
+  // (uaddo X, Carry) -> (addcarry X, 0, Carry)
+  if (auto Carry = getAsCarry(N1))
+    return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(), N0,
+                       DAG.getConstant(0, SDLoc(N), N0.getValueType()), Carry);
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitADDE(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDValue CarryIn = N->getOperand(2);
 

test/CodeGen/X86/add-of-carry.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown-unknown | FileCheck %s
 
 ; These tests use adc/sbb in place of set+add/sub. Should this transform
 ; be enabled by micro-architecture rather than as part of generic lowering/isel?
 
 ; <rdar://problem/8449754>
 
 define i32 @test1(i32 %sum, i32 %x) nounwind readnone ssp {
 ; CHECK-LABEL: test1:
 ; CHECK:       # BB#0:
+; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; CHECK-NEXT:    addl {{[0-9]+}}(%esp), %eax
-; CHECK-NEXT:    adcl $0, %eax
+; CHECK-NEXT:    movl %eax, %edx
+; CHECK-NEXT:    addl %ecx, %edx
+; CHECK-NEXT:    adcl %ecx, %eax
 ; CHECK-NEXT:    retl
   %add4 = add i32 %x, %sum
   %cmp = icmp ult i32 %add4, %x
   %inc = zext i1 %cmp to i32
   %z.0 = add i32 %add4, %inc
   ret i32 %z.0
 }
 

test/CodeGen/X86/addcarry.ll

entry:
   %19 = trunc i128 %18 to i32
   store i32 %19, i32* %15, align 4
   ret void
 }
 
 define i64 @shiftadd(i64 %a, i64 %b, i64 %c, i64 %d) {
 ; CHECK-LABEL: shiftadd:
 ; CHECK:       # BB#0: # %entry
-; CHECK-NEXT:    leaq (%rdx,%rcx), %rax
 ; CHECK-NEXT:    addq %rsi, %rdi
-; CHECK-NEXT:    adcq $0, %rax
+; CHECK-NEXT:    adcq %rcx, %rdx
+; CHECK-NEXT:    movq %rdx, %rax
 ; CHECK-NEXT:    retq
 entry:
   %0 = zext i64 %a to i128
   %1 = zext i64 %b to i128
   %2 = add i128 %0, %1
   %3 = lshr i128 %2, 64
   %4 = trunc i128 %3 to i64
   %5 = add i64 %c, %d