[DAG] Promote ADDCARRY / SUBCARRY

[rogfer01]

Summary

Add missing case that was not implemented yet.

[rogfer01]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

776–786

This looks like a lot like the "dual" of PromoteIntRes_Overflow but replacing the users of :1 (instead of :0). It generates correct code in Arm but I may be missing some subtlety here.

[efriedma]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

776–786

Yes, you're missing a very important piece here: the output carry bit is wrong. You have to check whether the addition would overflow in the narrow type, not just whether it would overflow in the promoted type.

What code is producing an ADDCARRY like this?

[rogfer01]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

776–786

Ah! Of course!

Thanks a lot Eli. This will need fixing.

A testcase (found by csmith)

unsigned a, b, e;
void fn1() {
  long d = (a + b < b) - e;
  short c = d + 1;
  if (c)
   for (;;)
   ;
}

[jgreenhalgh]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

776–786

I'm not sure this comment is correct. Because you're sign extending, you want to treat the narrow mode as a signed value, which means you only have 3 cases to consider:

1. Addition of two negative numbers - In two's compliment this will always set the carry flag. Sign extension would leave a 1 in the most significant bit for both widened input values, and so addition in the wider mode would also always set the carry flag.

2. Addition of two positive numbers - In two's compliment this can never set the carry flag in the narrow mode. Sign extension leave a 0 in the two most significant bits for both widened input values, and so addition in the wider mode would also never set the carry flag.

3. Addition of a positive number and a negative number - This will sometimes set the carry flag in the narrow mode. The insight here is that the negative number will propagate 1 to all widened bits when sign extended, without changing the bits of the two narrow values. If a carry would be generated from the narrow values, this would also propagate through the upper bits of the widened addition, and a carry would be generated. If no carry is generated from addition in the narrow mode, then no carry is generated in the wider mode.

[efriedma]

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

776–786

What code is producing an ADDCARRY like this?

I meant, what code in the ARM backend is producing an ISD::ADDCARRY node with an illegal type?

[rogfer01]

The generic combiner DAGCombiner::visitTRUNCATE does this

// (trunc adde(X, Y, Carry)) -> (adde trunc(X), trunc(Y), Carry)
// (trunc addcarry(X, Y, Carry)) -> (addcarry trunc(X), trunc(Y), Carry)
// When the adde's carry is not used.
if ((N0.getOpcode() == ISD::ADDE || N0.getOpcode() == ISD::ADDCARRY) &&
    N0.hasOneUse() && !N0.getNode()->hasAnyUseOfValue(1) &&
    (!LegalOperations || TLI.isOperationLegal(N0.getOpcode(), VT))) {
  SDLoc SL(N);
  auto X = DAG.getNode(ISD::TRUNCATE, SL, VT, N0.getOperand(0));
  auto Y = DAG.getNode(ISD::TRUNCATE, SL, VT, N0.getOperand(1));
  auto VTs = DAG.getVTList(VT, N0->getValueType(1));
  return DAG.getNode(N0.getOpcode(), SL, VTs, X, Y, N0.getOperand(2));
}

Here N0 is t22: i32,i1 = addcarry t12, Constant:i32<0>, t7:1 but VT is i16 and it is used in the VTs of the final getNode, but this happens before legalize types, this is, inside this

// Run the DAG combiner in pre-legalize mode.
{
  NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
                     GroupDescription, TimePassesIsEnabled);
  CurDAG->Combine(BeforeLegalizeTypes, AA, OptLevel);
}

so I think it is valid to create this node and what we are missing is a promotion for it so it finally becomes legal.

Does this make sense @efriedma ?

[efriedma]

I can't see how that DAGCombine transform is actually profitable if the type isn't legal... but I guess we might as well just fix the legalizer so we don't trip over it again.

[rogfer01]

We want to do here is to calculate the ADDCARRY / SUBCARRY with a wider type and then use that result to compute the carry/borrow. I think that by sign extension of the operands, the carry/borrow of wider operation should exactly be the same as in a narrower type:

• to generate carry in a case like ADDCARRY x, y at least one of them must have the most significant bit (n-1) set (if the most significant bit is not set the largest number we can represent is 2ⁿ⁻²-1, if we add it twice we get 2ⁿ⁻¹-2 which does not generate carry). This means that, in the case of carry, at least one of the operands will be all ones in its higher (after sign extension), these higher bits should have the effect of propagating the carry of the narrow operation to the carry of the wider operation.
• to generate a borrow in a case like SUBCARRY x, y we need x < y and this property should be preserved by sign extension.

@efriedma from your first comment above it looks like I'm plain wrong. Mind to shed some light on this? Thanks! :)

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

776–777

I think this is wrong and should be

SDValue LHS = SExtPromotedInteger(N->getOperand(0));
SDValue RHS = SExtPromotedInteger(N->getOperand(1));

because I pretend to use the extended bits (for the carry/borrow propagation) but then I get an apparently redundant (at least in this test case) sign extension from i16 to i32.

[efriedma]

Oh, I see. Yes, sign-extending should work: https://rise4fun.com/Alive/Ux9 . Please add a your explanation as a comment (and fix the code so it actually sign-extends).

[rogfer01]

ChangeLog

• Sign extend operands as we will want to use the higher bits (they could be rubbish in the previous diff). Add a comment.

[rogfer01]

test/CodeGen/ARM/addsubcarry-promotion.ll

15

This is made redundant by the tst below (as it will mask the higher 16 bits) but I presume this has to be fixed elsewhere.

[efriedma]

LGTM

test/CodeGen/ARM/addsubcarry-promotion.ll

15

Yes. (Maybe in SimplifyDemandedBits.)

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp

SDValue DAGTypeLegalizer::PromoteIntRes_UADDSUBO(SDNode *N, unsigned ResNo) {
   ReplaceValueWith(SDValue(N, 1), Ofl);
 
   return Res;
 }
 
 SDValue DAGTypeLegalizer::PromoteIntRes_ADDSUBCARRY(SDNode *N, unsigned ResNo) {
   if (ResNo == 1)
     return PromoteIntRes_Overflow(N);
-  llvm_unreachable("Not implemented");
+
+  // We need to sign-extend the operands so the carry value computed by the
+  // wide operation will be equivalent to the carry value computed by the
+  // narrow operation.
+  // An ADDCARRY can generate carry only if any of the operands has its
+  // most significant bit set. Sign extension propagates the most significant
+  // bit into the higher bits which means the extra bit that the narrow
+  // addition would need (i.e. the carry) will be propagated through the higher
+  // bits of the wide addition.
+  // A SUBCARRY can generate borrow only if LHS < RHS and this property will be
+  // preserved by sign extension.
+  SDValue LHS = SExtPromotedInteger(N->getOperand(0));
+  SDValue RHS = SExtPromotedInteger(N->getOperand(1));
+
+  EVT ValueVTs[] = {LHS.getValueType(), N->getValueType(1)};
+
+  // Do the arithmetic in the wide type.
+  SDValue Res = DAG.getNode(N->getOpcode(), SDLoc(N), DAG.getVTList(ValueVTs),
+                            LHS, RHS, N->getOperand(2));
+
+  // Update the users of the original carry/borrow value.
+  ReplaceValueWith(SDValue(N, 1), Res.getValue(1));
+
+  return SDValue(Res.getNode(), 0);
 }
 
 SDValue DAGTypeLegalizer::PromoteIntRes_XMULO(SDNode *N, unsigned ResNo) {
   // Promote the overflow bit trivially.
   if (ResNo == 1)
     return PromoteIntRes_Overflow(N);
 
   SDValue LHS = N->getOperand(0), RHS = N->getOperand(1);

test/CodeGen/ARM/addsubcarry-promotion.ll

+; RUN: llc -O2 -mtriple armv7a < %s | FileCheck --check-prefix=ARM %s
+
+; RUN: llc -O2 -mtriple thumbv6m < %s | FileCheck --check-prefix=THUMB1 %s
+; RUN: llc -O2 -mtriple thumbv8m.base < %s | FileCheck --check-prefix=THUMB1 %s
+
+; RUN: llc -O2 -mtriple thumbv7a < %s | FileCheck --check-prefix=THUMB %s
+; RUN: llc -O2 -mtriple thumbv8m.main < %s | FileCheck --check-prefix=THUMB %s
+
+define void @fn1(i32 %a, i32 %b, i32 %c) local_unnamed_addr #0 {
+entry:
+
+; ARM: rsb  r2, r2, #1
+; ARM: adds r0, r1, r0
+; ARM: movw r1, #65535
+; ARM: sxth r2, r2
+; ARM: adc  r0, r2, #0
+; ARM: tst  r0, r1
+; ARM: bxeq lr
+; ARM: .LBB0_1:
+; ARM: b  .LBB0_1
+
+; THUMB1: movs  r3, #1
+; THUMB1: subs  r2, r3, r2
+; THUMB1: sxth  r2, r2
+; THUMB1: movs  r3, #0
+; THUMB1: adds  r0, r1, r0
+; THUMB1: adcs  r3, r2
+; THUMB1: lsls  r0, r3, #16
+; THUMB1: beq .LBB0_2
+; THUMB1: .LBB0_1:
+; THUMB1: b .LBB0_1
+
+; THUMB: rsb.w  r2, r2, #1
+; THUMB: adds r0, r0, r1
+; THUMB: sxth r2, r2
+; THUMB: adc  r0, r2, #0
+; THUMB: lsls r0, r0, #16
+; THUMB: it eq
+; THUMB: bxeq lr
+; THUMB: .LBB0_1:
+; THUMB: b  .LBB0_1
+
+  %add = add i32 %b, %a
+  %cmp = icmp ult i32 %add, %b
+  %conv = zext i1 %cmp to i32
+  %sub = sub i32 1, %c
+  %add1 = add i32 %sub, %conv
+  %conv2 = trunc i32 %add1 to i16
+  %tobool = icmp eq i16 %conv2, 0
+  br i1 %tobool, label %if.end, label %for.cond.preheader
+
+for.cond.preheader:                               ; preds = %entry
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond.preheader, %for.cond
+  br label %for.cond
+
+if.end:                                           ; preds = %entry
+  ret void
+}