Page MenuHomePhabricator

[DAG] Promote ADDCARRY / SUBCARRY
ClosedPublic

Authored by rogfer01 on Oct 16 2017, 12:46 AM.

Diff Detail

Repository
rL LLVM

Event Timeline

rogfer01 created this revision.Oct 16 2017, 12:46 AM
rogfer01 added inline comments.Oct 16 2017, 12:49 AM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
777–787 ↗(On Diff #119112)

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 added inline comments.Oct 16 2017, 12:15 PM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
777–787 ↗(On Diff #119112)

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 added inline comments.Oct 16 2017, 11:30 PM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
777–787 ↗(On Diff #119112)

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 added inline comments.
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
777–787 ↗(On Diff #119112)

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.
  1. 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.
  1. 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 added inline comments.Oct 17 2017, 11:16 AM
lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
777–787 ↗(On Diff #119112)

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?

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 edited edge metadata.Dec 8 2017, 11:11 AM

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.

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
777–778 ↗(On Diff #119112)

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.

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 updated this revision to Diff 126513.Dec 12 2017, 1:41 AM

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 added inline comments.Dec 12 2017, 1:43 AM
test/CodeGen/ARM/addsubcarry-promotion.ll
15 ↗(On Diff #126513)

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 accepted this revision.Dec 12 2017, 2:12 PM

LGTM

test/CodeGen/ARM/addsubcarry-promotion.ll
15 ↗(On Diff #126513)

Yes. (Maybe in SimplifyDemandedBits.)

This revision is now accepted and ready to land.Dec 12 2017, 2:12 PM
This revision was automatically updated to reflect the committed changes.