[DAG] Improve carry reconstruction in combineCarryDiamond.

[deadalnix]

Summary

The gain is usually suffiscient to go the extra mile and reconstruct a carry in some cases.

[deadalnix]

Fix SystemZ tests

[deadalnix]

llvm/test/CodeGen/SystemZ/int-uadd-01.ll

313–318 ↗

(On Diff #537474)

@uweigand Maybe you could advise on what's the right way forward here?

[uweigand]

Hi @deadalnix , it looks to me the test case exposes an actual bug. A simplified test would be this:

define i1 @f14(i32 %val0, i32 %val1, i32 %val2) {
  %t0 = call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %val0, i32 %val1)
  %add0 = extractvalue {i32, i1} %t0, 0
  %obit0 = extractvalue {i32, i1} %t0, 1
  %t1 = call {i32, i1} @llvm.uadd.with.overflow.i32(i32 %add0, i32 %val2)
  %add1 = extractvalue {i32, i1} %t1, 0
  %obit1 = extractvalue {i32, i1} %t1, 1

  %res = or i1 %obit0, %obit1
  ret i1 %res
}

declare {i32, i1} @llvm.uadd.with.overflow.i32(i32, i32) nounwind readnone

This gets initially expanded into:

t0: ch,glue = EntryToken
  t2: i32,ch = CopyFromReg t0, Register:i32 %0
  t4: i32,ch = CopyFromReg t0, Register:i32 %1
t7: i32,i1 = uaddo t2, t4
        t6: i32,ch = CopyFromReg t0, Register:i32 %2
      t8: i32,i1 = uaddo t7, t6
    t9: i1 = or t7:1, t8:1
  t10: i32 = any_extend t9

but after DAGCombine with your change this ends up as:

    t2: i32,ch = CopyFromReg t0, Register:i32 %0
    t4: i32,ch = CopyFromReg t0, Register:i32 %1
    t6: i32,ch = CopyFromReg t0, Register:i32 %2
  t14: i32,i1 = uaddo_carry t2, t4, t6
t10: i32 = any_extend t14:1

This looks wrong to me - the last operand of uaddo_carry is supposed to be a boolean flag indicating incoming carry, but here we're passing in one of the i32 inputs in full. Am I missing something here?

[deadalnix]

In D154533#4476409, @uweigand wrote:

Hi @deadalnix , it looks to me the test case exposes an actual bug. A simplified test would be this:
...

Good catch. The carry reconstruction is a bit too optimistic. I'll rework this.

[deadalnix]

Fix overly enthusiastic carry promotion.

[barannikov88]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3545

It does not look like this TODO was addressed, unless I'm misunderstanding it.

3551–3552

It is now an arbitrary boolean value, not necessarily a carry/borrow.
I don't know whether this is good or bad, although it looks like it was indended to match only carry/borrow-producing nodes.
If go that road I'd also consider replacing this call with more general bit tracking (ComputeNumSignBits et al.).

[deadalnix]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3545

Indeed. I did not think that really needed after this logic change so I removed the TODO.

[deadalnix]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3551–3552

In this case, we replace a complex web of instructions by just one add. Reconstructing a carry is worth it. The test cases that were changed bellow are good exemple of that, the carry is passed as an argument to the functions, so it is not possible to know if these are "real" carries or not, and it is nevertheless worth doing the transform.

[barannikov88]

In this case, we replace a complex web of instructions by just one add. Reconstructing a carry is worth it. The test cases that were changed bellow are good exemple of that, the carry is passed as an argument to the functions, so it is not possible to know if these are "real" carries or not, and it is nevertheless worth doing the transform.

I was thinking about cases like feeding uaddo by a setcc, but that does not seem to pay off. E.g.:

declare { i64, i1 } @llvm.usub.with.overflow.i64(i64, i64)

define { i64, i1 } @subcarry_fake_carry(i64 %a, i64 %b, i32 %x, i32 %y) {
    %t1 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %a, i64 %b)
    %partial = extractvalue { i64, i1 } %t1, 0
    %k1 = extractvalue { i64, i1 } %t1, 1

    %carryin = icmp eq i32 %x, %y
    %zcarryin = zext i1 %carryin to i64
    %s = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %partial, i64 %zcarryin)
    %k2 = extractvalue { i64, i1 } %s, 1

    %carryout = or i1 %k1, %k2

    %ret = insertvalue { i64, i1 } %s, i1 %carryout, 1
    ret { i64, i1 } %ret
}

$ llc test.ll -o - -x86-asm-syntax=intel
Before this patch:

mov     rax, rdi
sub     rax, rsi
setb    sil
xor     edi, edi
cmp     edx, ecx
sete    dil
sub     rax, rdi
setb    dl
or      dl, sil

with this patch:

mov     rax, rdi
cmp     edx, ecx
sete    cl
add     cl, -1
sbb     rax, rsi
setb    dl

With my suggestion:

mov     rax, rdi
xor     edi, edi
cmp     edx, ecx
sete    dil
add     rdi, -1
sbb     rax, rsi
setb    dl

[barannikov88]

Ok, this looks good to me as-is. There are things that can be improved e.g. taking into accout "boolean contents flavor" and the type of the boolean value (which appears to be i8 on x86), but they seem to be more or less independent of this change.
It's not exactly my area, so I'll let someone else take a look.

[deadalnix]

Tighten conditions and add a test case.

[deadalnix]

Rebase, ping?

[RKSimon]

LGTM

[chfast]

In D154533#4480255, @barannikov88 wrote:

In this case, we replace a complex web of instructions by just one add. Reconstructing a carry is worth it. The test cases that were changed bellow are good exemple of that, the carry is passed as an argument to the functions, so it is not possible to know if these are "real" carries or not, and it is nevertheless worth doing the transform.

I was thinking about cases like feeding uaddo by a setcc, but that does not seem to pay off. E.g.:

declare { i64, i1 } @llvm.usub.with.overflow.i64(i64, i64)

define { i64, i1 } @subcarry_fake_carry(i64 %a, i64 %b, i32 %x, i32 %y) {
    %t1 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %a, i64 %b)
    %partial = extractvalue { i64, i1 } %t1, 0
    %k1 = extractvalue { i64, i1 } %t1, 1

    %carryin = icmp eq i32 %x, %y
    %zcarryin = zext i1 %carryin to i64
    %s = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %partial, i64 %zcarryin)
    %k2 = extractvalue { i64, i1 } %s, 1

    %carryout = or i1 %k1, %k2

    %ret = insertvalue { i64, i1 } %s, i1 %carryout, 1
    ret { i64, i1 } %ret
}

It looks this test cases could be added to the repo.

[deadalnix]

In D154533#4525125, @chfast wrote:

It looks this test cases could be added to the repo.

It already is in subcarry.ll . I'll rebase and check everything's good with this, and if so land.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

SDValue DAGCombiner::visitADDSAT(SDNode *N) {
 
   // If it cannot overflow, transform into an add.
   if (DAG.computeOverflowForAdd(IsSigned, N0, N1) == SelectionDAG::OFK_Never)
     return DAG.getNode(ISD::ADD, DL, VT, N0, N1);
 
   return SDValue();
 }
 
-static SDValue getAsCarry(const TargetLowering &TLI, SDValue V) {
+static SDValue getAsCarry(const TargetLowering &TLI, SDValue V,
+                          bool ForceCarryReconstruction = false) {
   bool Masked = false;
 
   // First, peel away TRUNCATE/ZERO_EXTEND/AND nodes due to legalization.
   while (true) {
     if (V.getOpcode() == ISD::TRUNCATE || V.getOpcode() == ISD::ZERO_EXTEND) {
       V = V.getOperand(0);
       continue;
     }
 
     if (V.getOpcode() == ISD::AND && isOneConstant(V.getOperand(1))) {
+      if (ForceCarryReconstruction)
+        return V;
+
       Masked = true;
       V = V.getOperand(0);
       continue;
     }
 
+    if (ForceCarryReconstruction && V.getValueType() == MVT::i1)
+      return V;
+
     break;
   }
 
   // If this is not a carry, return.
   if (V.getResNo() != 1)
     return SDValue();
 
   if (V.getOpcode() != ISD::UADDO_CARRY && V.getOpcode() != ISD::USUBO_CARRY &&
static SDValue combineCarryDiamond(SelectionDAG &DAG, const TargetLowering &TLI,
   if (Opcode == ISD::USUBO && CarryInOperandNum != 1)
     return SDValue();
   SDValue CarryIn = Carry1.getOperand(CarryInOperandNum);
 
   unsigned NewOp = Opcode == ISD::UADDO ? ISD::UADDO_CARRY : ISD::USUBO_CARRY;
   if (!TLI.isOperationLegalOrCustom(NewOp, Carry0.getValue(0).getValueType()))
     return SDValue();
 
   // Verify that the carry/borrow in is plausibly a carry/borrow bit.
-  // TODO: make getAsCarry() aware of how partial carries are merged.
-  if (CarryIn.getOpcode() != ISD::ZERO_EXTEND)
-    return SDValue();
-  CarryIn = CarryIn.getOperand(0);
-  if (CarryIn.getValueType() != MVT::i1)
+  CarryIn = getAsCarry(TLI, CarryIn, true);
+  if (!CarryIn)
     return SDValue();
 
   SDLoc DL(N);
   SDValue Merged =
       DAG.getNode(NewOp, DL, Carry1->getVTList(), Carry0.getOperand(0),
                   Carry0.getOperand(1), CarryIn);
 
   // Please note that because we have proven that the result of the UADDO/USUBO

llvm/test/CodeGen/X86/addcarry.ll

; CHECK-NEXT:    retq
   %ret = insertvalue { i64, i1 } %sum, i1 %carryout, 1
   ret { i64, i1 } %ret
 }
 
 ; Check that we can reconstruct a carry if it is masked.
 define { i64, i1 } @addcarry_carry_and_1(i64 %a, i64 %b, i64 %carryin) nounwind {
 ; CHECK-LABEL: addcarry_carry_and_1:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movq %rdx, %rax
-; CHECK-NEXT:    addq %rsi, %rdi
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    andl $1, %eax
-; CHECK-NEXT:    addq %rdi, %rax
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    btl $0, %edx
+; CHECK-NEXT:    adcq %rsi, %rax
 ; CHECK-NEXT:    setb %dl
-; CHECK-NEXT:    orb %cl, %dl
 ; CHECK-NEXT:    retq
   %t1 = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %a, i64 %b)
   %partial = extractvalue { i64, i1 } %t1, 0
   %k1 = extractvalue { i64, i1 } %t1, 1
 
   %mcarryin = and i64 %carryin, 1
   %sum = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %partial, i64 %mcarryin)
   %k2 = extractvalue { i64, i1 } %sum, 1