[ARM] Use ADDCARRY / SUBCARRY

[rogfer01]

Summary

This is a preparatory step for D34515

This patch:

• makes nodes ISD::ADDCARRY and ISD::SUBCARRY legal for i32
• lowering is done by first converting the boolean value into the carry flag using (_, C) ← (ARMISD::ADDC R, -1) and converted back to an integer value using (R, _) ← (ARMISD::ADDE 0, 0, C). An ARMISD::ADDE between the two operations does the actual addition.
• for subtraction, given that ISD::SUBCARRY second result is actually a borrow, we need to invert the value of the second operand and result before and after using ARMISD::SUBE. We need to invert the carry result of ARMISD::SUBE to preserve the semantics.
• given that the generic combiner may lower ISD::ADDCARRY and ISD::SUBCARRYinto ISD::UADDO and ISD::USUBO we need to update their lowering as well otherwise i64 operations now would require branches. This implies updating the corresponding test for unsigned.
• add new combiner to remove the redundant conversions from/to carry flags to/from boolean values (ARMISD::ADDC (ARMISD::ADDE 0, 0, C), -1) → C

[rogfer01]

lib/Target/ARM/ARMISelLowering.cpp

7438–7442

This is usually combined into (ARMISD::SUBC Carry, 1) so I think that I can save a few combiners that have to take into account this node before being combined.

Does this sound sensible?

[deadalnix]

lib/Target/ARM/ARMISelLowering.cpp

4007

Usual style is more like

case Foo: {
  ...
}

test/CodeGen/ARM/intrinsics-overflow.ll

14

CHECK

[rogfer01]

ChangeLog:

• clang-format LowerUnsignedALUO
• fix FileCheck test

[deadalnix]

I see nothing obviously wrong with this patch. It'd be better if someone with more ARM experience than I do could review it.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

9993

ARMISD::SUBC return two values. The flags register will be the same, but the returned value might not.

10027

What is this combine trying to do? X is an arbitrary i32; the numeric result of ADDE is either 0 or 1.

12808–12809

Is this true?

test/CodeGen/ARM/intrinsics-overflow.ll

14

Could you change this test to also show what happens in Thumb1 mode?

[rogfer01]

ChangeLog:

• Fix combiners so they preserve the arity of the result.
• Remove bogus combiner.
• Add new tests for {u,s}{add,sub} overflow for Thumb and Thumb2

[rogfer01]

Hi @efriedma, thanks for the review. I have updated with your suggestions.

Still pending to resolve is the change I did in ARMTargetLowering::computeKnownBitsForTargetNode, can you clarify your comment?

Thanks!

lib/Target/ARM/ARMISelLowering.cpp

10027

My brain must have shorted when I wrote this. I will remove it because not only is wrong, apparently it has no effect.

12808–12809

Maybe I do not understand what this function computes.

The result of the first operand (Op.getResNo() == 0) should be either 0 or 1 in the given nodes so all bits are zero but the lowermost one.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

7451

Typo "ARMISDD".

7461

Typo "ARMISDD".

12808–12809

I was asking specifically about the comment "These nodes' second result is a boolean". (I know it isn't new, but we should fix it while we're here.)

[efriedma]

You should be able to test ARM+Thumb1+Thumb2 in the same file. See, for example, test/CodeGen/ARM/arm-position-independence-jump-table.ll.

[rogfer01]

ChangeLog:

• Use a single file for the new tests instead of scattering them in two files.
• Fix a bug introduced when ARMTargetLowering::computeKnownBitsForTargetNode was updated.

[rogfer01]

Hi @efriedma, thanks again for the comments. I have updated the diff with your suggestions.

Please find a comment for the ARMTargetLowering::computeKnownBitsForTargetNode, I think it is now OK but I will appreciate some more insight.

Kind regards,
Roger

[rogfer01]

lib/Target/ARM/ARMISelLowering.cpp

12808–12809

My understanding is that ISD::ADDE/ISD::SUBE and (the now deprecated) ISD::ADDC/ISD::SUBC are immediately lowered into ARMISD::ADDE and ARMISD::ADDC respectively so I think that for the second result nothing has changed. The extra check for the first is because the extra hops that we do now when lowering ADDCARRY / SUBCARRY.

That said, you were right to point me at this part of code because I introduced a bug here, which I fixed in this update.

Sadly I'm not sure how can I test that these bits are correctly accounted for this second operand (for the first operand is easy and already caght by the regression testsuite: not knowing it will introduce spurious and operations to make sure only 1 bit is used).

I find difficult to generate an ARMISD::ADDE (using IR) where some combiner wants to check the outcome of the second operand, even more now that the patch legalizes ADDCARRY / SUBCARRY and we do some extra hops to get in and out the carry flag itself. It would be a bit worrying that this were wrong at this point because it'd mean I cannot do exactly that.

It could well be that I'm missing something obvious here.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

12808–12809

The second result of ARMISD::SUBE isn't a boolean; it's a copy of CPSR.

[rogfer01]

ChangeLog:

• Remove incorrect computation of known bits for an operand that contains a copy of the CPSR and not a boolean.

[rogfer01]

Thanks again @efriedma.

From your comment I think that we should remove this case as it was wrong already. Let me know if I understood you correctly.

Regards,
Roger

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

4011

Oops, I should have spotted the issue here earlier.

The value produced by sbc is a+~b+C. So (ARMISD::SUBE i32 1, i32 0) is computing 1+-1+C==C. The value you actually need to produce here is 1-C.

In practice, this means we're generating wrong code for the usub_overflow testcase.

[rogfer01]

ChangeLog:

• Correctly handle the second operand of ISD::SUBCARRY. We need to invert its value (i.e. 1-x) before passing it to ARMISD::SUBE, also the result of ARMISD::SUBE has to be inverted again to match what ISD::SUBCARRY means.
• Fix USUBO lowering as a consequence of the above.
• Add a combiner for (SUBC 1, (SUBC 1, X)) → X
• Compute the known bits of (SUBC 1, (ADDE 0, 0, C)) (1 bit) to avoid spurious and instructions.
• Update the tests for usub_builtin_overflow with the correct code generation.
• Remove combiners that became pointless after the changes above.

[rogfer01]

Hi @efriedma, thanks for the review, please find the updated changes. I was wrongly handling ISD::SUBCARRY because its operand is a borrow while ARMISD::SUBE expects a carry.

lib/Target/ARM/ARMISelLowering.cpp

4011

Thanks Eli, this was a serious bug. Sorry for that. I used the obvious approach instead.

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

4014

Could you use ISD::SUB here, rather than ARMISD::SUBC?

[rogfer01]

ChangeLog:

• Use ISD::SUB instead of ARMISD::SUBC when inverting the borrow / carry.
• Due to the above, remove now unnecessary target-specific combiner.

[rogfer01]

Hi @efriedma thanks for your suggestion, this way I can avoid one target-specific combiner which I have now removed.

Regards,
Roger

[efriedma]

lib/Target/ARM/ARMISelLowering.cpp

7478

Maybe you could refactor this to share a little more code for ADDCARRY/SUBCARRY?

9996

Do we still need the code for SUBC here?

12828

Do we still need the code for SUBC here?

[rogfer01]

ChangeLog:

• Remove unnecessary combiner for ARMISD::SUBC
• Refactor a bit the conversion carry to/from boolean

[efriedma]

LGTM, with minor comments.

Please make sure to update the commit message to account for the changes during the review.

lib/Target/ARM/ARMISelLowering.cpp

7461

Weird indentation (maybe try clang-format?)

[rogfer01]

ChangeLog:

• clang-format fixes

[rogfer01]

I plan to submit this tomorrow morning (BST time).

[rogfer01]

Reopening: this is causing PR34045.

[rogfer01]

ChangeLog:

• Fix problem in S/UMLAL combiner that caused PR34045.
• New bugpoint-reduced test based on the reproducer of PR34045.

[rogfer01]

lib/Target/ARM/ARMISelLowering.cpp

9880–9883

This fixes the problem in PR34045.

I wonder if AddeNode + LowAdd might have the same problem but I don't think it can happen.

The rest of boringssl has built correctly using -mthumb, though.

[efriedma]

LGTM

lib/Target/ARM/ARMISelLowering.cpp

9880–9883

I wonder if AddeNode + LowAdd might have the same problem but I don't think it can happen.

loAdd is a predecessor of AddcNode, which is a predecessor of AddeNode, so I don't think you can run into problems there. (It's possible for loAdd to use the result of the UMUL_LOHI, but you don't end up with a cycle in that case, just a redundant multiply.)

I guess this issue only shows up with your patch because it's impossible to create a DAG like that without ADDCARRY transforms?

[rogfer01]

Thanks for the review Eli!

lib/Target/ARM/ARMISelLowering.cpp

9880–9883

I think so. Before the ADDCARRY transforms the DAG is slightly simpler at the point this combiner kicks in.

[rogfer01]

We're still hitting PR34045. I also plan integrate the fix in D37690 to ease reverting if needed.

[rogfer01]

ChangeLog:

• fix for the second instance of PR34045
• also integrates the changes to fix PR34564, fall-out of the original change, that was reverted as well

[rogfer01]

In the second instance of PR34045 what happens is that ADDC is exactly HiAdd, not just a predecessor of the latter.

That said, let me first check I can build Chrome for ARM with this change. It is not a matter of bothering Google folks :)

[efriedma]

Makes sense.

[rogfer01]

Ok, Chrome for Linux Arm took a bit to build with a debug compiler but finished successfully.

That said tomorrow I'm on holidays tomorrow until Tuesday so I will commit this then (I want to monitor this change as it has proved more disruptive than expected).

[manojgupta]

Roger, We are seeing a fail in ChromeOS with the CL r313618. I'll try to send a test case soon.

[rogfer01]

This is causing PR35103, so reopening after the revert, so I can investigate what is going wrong there.

[rogfer01]

Hi @efriedma ,

I'm trying to understand what went wrong in the following input

define i32 @foo(i32 %var1, i32 %var2, i32 %var3, i32 %var4, i32 %var5) local_unnamed_addr #0 {
entry:
  %conv1 = zext i32 %var3 to i64
  %conv2 = zext i32 %var1 to i64
  %add3 = add nuw nsw i64 %conv1, %conv2
  %shr = lshr i64 %add3, 32
  %conv5 = trunc i64 %shr to i32
  %conv7 = and i64 %add3, 4294967295
  %add10 = add nuw nsw i64 %conv7, %conv2
  %shr12 = lshr i64 %add10, 32
  %conv13 = trunc i64 %shr12 to i32
  %add14 = add nuw nsw i32 %conv13, %conv5
  %conv16 = zext i32 %var4 to i64
  %conv18 = zext i32 %var2 to i64
  %add19 = add nuw nsw i64 %conv16, %conv18
  %shr21 = lshr i64 %add19, 32
  %conv24 = zext i32 %var5 to i64
  %add25 = add nuw nsw i64 %shr21, %conv24
  %shr28 = lshr i64 %add25, 32
  %conv29 = trunc i64 %shr28 to i32
  %add30 = add nuw nsw i32 %add14, %conv29
  ret i32 %add30
}

which (with ADDCARRY / SUBCARRY nodes enabled) generates the following selection using

./bin/llc -mtriple armv8 -O3 -o - bad.ll

SelectionDAG has 28 nodes:
  t0: ch = EntryToken
  t2: i32,ch = CopyFromReg t0, Register:i32 %vreg0
    t6: i32,ch = CopyFromReg t0, Register:i32 %vreg2
  t75: i32,i32 = ADDSrr t6, t2, TargetConstant:i32<14>, Register:i32 %noreg
          t58: i32 = MOVi TargetConstant:i32<0>, TargetConstant:i32<14>, Register:i32 %noreg, Register:i32 %noreg
            t69: i32,i32 = ADDSrr t75, t2, TargetConstant:i32<14>, Register:i32 %noreg
          t84: ch,glue = CopyToReg t0, Register:i32 %CPSR, t69:1
        t70: i32,i32 = ADCri t58, TargetConstant:i32<0>, TargetConstant:i32<14>, Register:i32 %noreg, Register:i32 %noreg, t84:1
        t83: ch,glue = CopyToReg t0, Register:i32 %CPSR, t75:1
      t66: i32,i32 = ADCri t70, TargetConstant:i32<0>, TargetConstant:i32<14>, Register:i32 %noreg, Register:i32 %noreg, t83:1
      t47: i32,ch = LDRi12<Mem:LD4[FixedStack-1](align=8)> TargetFrameIndex:i32<-1>, TargetConstant:i32<0>, TargetConstant:i32<14>, Register:i32 %noreg, t0
          t8: i32,ch = CopyFromReg t0, Register:i32 %vreg3
          t4: i32,ch = CopyFromReg t0, Register:i32 %vreg1
        t72: i32,i32 = ADDSrr t8, t4, TargetConstant:i32<14>, Register:i32 %noreg
      t81: ch,glue = CopyToReg t0, Register:i32 %CPSR, t72:1
    t62: i32,i32 = ADCrr t66, t47, TargetConstant:i32<14>, Register:i32 %noreg, Register:i32 %noreg, t81:1
  t35: ch,glue = CopyToReg t0, Register:i32 %R0, t62
  t36: ch = BX_RET TargetConstant:i32<14>, Register:i32 %noreg, Register:i32 %R0, t35, t35:1

Where t75 second value is consumed by t83 CopyToReg which is glued to t66 ADCri. Similarly t69 second value is consumed by t84 CopytoReg which is glued to t70. I think this is not constraining enough the schedule which decides to do

BB#0: derived from LLVM BB %entry
    Live Ins: %R0 %R1 %R2 %R3
	%vreg3<def> = COPY %R3; GPR:%vreg3
	%vreg2<def> = COPY %R2; GPR:%vreg2
	%vreg1<def> = COPY %R1; GPR:%vreg1
	%vreg0<def> = COPY %R0; GPR:%vreg0
	%vreg4<def> = MOVi 0, pred:14, pred:%noreg, opt:%noreg; GPR:%vreg4
	%vreg5<def> = ADDrr %vreg2, %vreg0, pred:14, pred:%noreg, opt:%CPSR<def>; GPR:%vreg5,%vreg2,%vreg0
	%vreg6<def> = ADDrr %vreg5<kill>, %vreg0, pred:14, pred:%noreg, opt:%CPSR<def>; GPR:%vreg6,%vreg5,%vreg0
	%vreg7<def> = ADCri %vreg4<kill>, 0, pred:14, pred:%noreg, opt:%noreg, %CPSR<imp-use>; GPR:%vreg7,%vreg4
  ...

This is, the CPSR computed in %vreg5 is clobbered by the CPSR computed in %vreg6.

Looks like (after we have lowered addcarry/subcarry into ARMISD::ADDC/ARMISD::ADDE and removed the redundant nodes to make sure the carry flag is correctly propagated) we have ended with something that cannot be scheduled sensibly without storing the carry flag somewhere. Given that it is found inside CPSR this will mean MRS / MSR which will move more bits than the ones I need from/to the flags.

Before addcarry/subcarry, the code can be scheduled without having to preserve the flags anywhere so I must be missing something very obvious here. Perhaps the combiners we do in the ARMISelLowering have to be more conservative?

Kind regards,

[rogfer01]

Uploaded

dag.foo-6bb493.dot5 KBDownload

DAG after isel.

[efriedma]

The DAG scheduler, my least favorite part of SelectionDAG. :(

There's supposed to be code that ensures we don't end up with a schedule like that (by either changing the schedule, or introducing an cross-class copy). See ScheduleDAGRRList::DelayForLiveRegsBottomUp and ScheduleDAGRRList::PickNodeToScheduleBottomUp. It's possible there's a bug somewhere in the handling of optional defs, since they're only used on ARM.

[rogfer01]

Thanks a lot for the pointer Eli! :-)

[rogfer01]

Hmm, scheduling is correct. I was all wrong, the legalized DAG is already wrong.

typedef unsigned int mp_digit;
typedef unsigned long long mp_word;

int
foo(mp_digit vreg0, mp_digit vreg1, mp_digit vreg2, mp_digit vreg3, mp_digit vreg4)
{
    mp_digit carry = 0;

    mp_word w1 = ((mp_word)0) + (vreg2) + (vreg0);
    mp_digit vreg2_2 = (mp_digit)(w1);
    mp_digit carry2 = (mp_digit)((w1) >> (8 * sizeof(mp_digit)));

    // int r8_1 = carry2;

    mp_word w2 = ((mp_word)0) + (vreg2_2) + (vreg0);
    mp_digit carry4 = (mp_digit)((w2) >> (8 * sizeof(mp_digit)));

    // int r8_2 = rb8_1 + carry4;
    int r8_2 = carry2 + carry4;

    mp_word w3 = ((mp_word)0) + (vreg3) + (vreg1);
    mp_digit carry6 = (mp_digit)((w3) >> (8 * sizeof(mp_digit)));

    mp_word w4 = ((mp_word)carry6) + (vreg4) + (0);
    mp_digit carry7 = (mp_digit)((w4) >> (8 * sizeof(mp_digit)));

    int r8_3 = r8_2 + carry7;

    return r8_3;
}

Two steps of the combiner

. I believe node t57 in the right is wrong.

[rogfer01]

A combiner kicks in for t33 because it is of the form (add, X, (addcarry Y, 0, C) and then it becomes (addcarry X, Y, C) which looks correct but I think it interacts badly with the nodes t24, t44 and t42 (which also have similar forms).

If my reading is correct, after this combination the final carry7 is not computed.

@deadalnix can you take a look at the screenshot above to check if my findings make sense?

[rogfer01]

We believe there is a problem here as the generic combiner presumes we're going to use the first result (0) but actually the code is using the second (1)

diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 5387a7ed73e3a3f22931f981578859f3c0b08e90..5ec4cdeaa272988ca0a97b35b993b507dddd10b6 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -2150,7 +2150,8 @@ SDValue DAGCombiner::visitADDLike(SDValue N0, SDValue N1, SDNode *LocReference)
   }
 
   // (add X, (addcarry Y, 0, Carry)) -> (addcarry X, Y, Carry)
-  if (N1.getOpcode() == ISD::ADDCARRY && isNullConstant(N1.getOperand(1)))
+  if (N1.getOpcode() == ISD::ADDCARRY && isNullConstant(N1.getOperand(1)) &&
+      N1.getResNo() == 0)
     return DAG.getNode(ISD::ADDCARRY, DL, N1->getVTList(),
                        N0, N1.getOperand(0), N1.getOperand(2));
 
-- 

@efriedma, @deadalnix is our diagnostic correct?

(Kudos to @avieira who did an amazing job chasing this)

[efriedma]

Yes, that looks correct.

[rogfer01]

• Fix combiner with addcarry that causes PR35103
• Add regression test

[efriedma]

LGTM

[deadalnix]

Congrats !

[efriedma]

Just filed https://bugs.llvm.org//show_bug.cgi?id=35836 .

lib/Target/ARM/ARMISelLowering.h

SDValue LowerToTLSGeneralDynamicModel(GlobalAddressSDNode *GA,
                                             SelectionDAG &DAG) const;
     SDValue LowerToTLSExecModels(GlobalAddressSDNode *GA,
                                  SelectionDAG &DAG,
                                  TLSModel::Model model) const;
     SDValue LowerGlobalTLSAddressDarwin(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerGlobalTLSAddressWindows(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerGLOBAL_OFFSET_TABLE(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerBR_JT(SDValue Op, SelectionDAG &DAG) const;
-    SDValue LowerXALUO(SDValue Op, SelectionDAG &DAG) const;
+    SDValue LowerSignedALUO(SDValue Op, SelectionDAG &DAG) const;
+    SDValue LowerUnsignedALUO(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSELECT(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSELECT_CC(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerBR_CC(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerFCOPYSIGN(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerRETURNADDR(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerFRAMEADDR(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerShiftRightParts(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerShiftLeftParts(SDValue Op, SelectionDAG &DAG) const;

lib/Target/ARM/ARMISelLowering.cpp

if (!Subtarget->isThumb1Only()) {
     setIndexedStoreAction(ISD::POST_INC, MVT::i32,  Legal);
   }
 
   setOperationAction(ISD::SADDO, MVT::i32, Custom);
   setOperationAction(ISD::UADDO, MVT::i32, Custom);
   setOperationAction(ISD::SSUBO, MVT::i32, Custom);
   setOperationAction(ISD::USUBO, MVT::i32, Custom);
 
+  setOperationAction(ISD::ADDCARRY, MVT::i32, Custom);
+  setOperationAction(ISD::SUBCARRY, MVT::i32, Custom);
+
   // i64 operation support.
   setOperationAction(ISD::MUL,     MVT::i64, Expand);
   setOperationAction(ISD::MULHU,   MVT::i32, Expand);
   if (Subtarget->isThumb1Only()) {
     setOperationAction(ISD::UMUL_LOHI, MVT::i32, Expand);
     setOperationAction(ISD::SMUL_LOHI, MVT::i32, Expand);
   }
   if (Subtarget->isThumb1Only() || !Subtarget->hasV6Ops()
case ISD::USUBO:
     OverflowCmp = DAG.getNode(ARMISD::CMP, dl, MVT::Glue, LHS, RHS);
     break;
   } // switch (...)
 
   return std::make_pair(Value, OverflowCmp);
 }
 
 SDValue
-ARMTargetLowering::LowerXALUO(SDValue Op, SelectionDAG &DAG) const {
+ARMTargetLowering::LowerSignedALUO(SDValue Op, SelectionDAG &DAG) const {
   // Let legalize expand this if it isn't a legal type yet.
   if (!DAG.getTargetLoweringInfo().isTypeLegal(Op.getValueType()))
     return SDValue();
 
   SDValue Value, OverflowCmp;
   SDValue ARMcc;
   std::tie(Value, OverflowCmp) = getARMXALUOOp(Op, DAG, ARMcc);
   SDValue CCR = DAG.getRegister(ARM::CPSR, MVT::i32);
   SDLoc dl(Op);
   // We use 0 and 1 as false and true values.
   SDValue TVal = DAG.getConstant(1, dl, MVT::i32);
   SDValue FVal = DAG.getConstant(0, dl, MVT::i32);
   EVT VT = Op.getValueType();
 
   SDValue Overflow = DAG.getNode(ARMISD::CMOV, dl, VT, TVal, FVal,
                                  ARMcc, CCR, OverflowCmp);
 
   SDVTList VTs = DAG.getVTList(Op.getValueType(), MVT::i32);
   return DAG.getNode(ISD::MERGE_VALUES, dl, VTs, Value, Overflow);
 }
 
+SDValue ARMTargetLowering::LowerUnsignedALUO(SDValue Op,
+                                             SelectionDAG &DAG) const {
+  // Let legalize expand this if it isn't a legal type yet.
+  if (!DAG.getTargetLoweringInfo().isTypeLegal(Op.getValueType()))
+    return SDValue();
+
+  SDValue LHS = Op.getOperand(0);
+  SDValue RHS = Op.getOperand(1);
+  SDLoc dl(Op);
+
+  SDVTList VTs = DAG.getVTList(Op.getValueType(), MVT::i32);
+  SDValue Value;
+  SDValue Overflow;
+  switch (Op.getOpcode()) {
+  default:
+    llvm_unreachable("Unknown overflow instruction!");
+  case ISD::UADDO:
+    Value = DAG.getNode(ARMISD::ADDC, dl, VTs, LHS, RHS);
+    // Convert the carry flag into a boolean value doing
+    // (ARMISD::ADDE 0, 0, Carry)
+    Overflow =
+        DAG.getNode(ARMISD::ADDE, dl, VTs, DAG.getConstant(0, dl, MVT::i32),
+                    DAG.getConstant(0, dl, MVT::i32), Value.getValue(1));
+    break;
+  case ISD::USUBO: {
+    Value = DAG.getNode(ARMISD::SUBC, dl, VTs, LHS, RHS);
+    // Convert the carry flag into a boolean value doing
+    // (ARMISD::ADDE 0, 0, Carry)
+    Overflow =
+        DAG.getNode(ARMISD::ADDE, dl, VTs, DAG.getConstant(0, dl, MVT::i32),
+                    DAG.getConstant(0, dl, MVT::i32), Value.getValue(1));
+    // ARMISD::SUBC returns 0 when we have to borrow, so make it an overflow
+    // value. We do this doing (sub 1, C)
+    Overflow = DAG.getNode(ISD::SUB, dl, VTs,
+                           DAG.getConstant(1, dl, MVT::i32), Overflow);
+    break;
+  }
+  }
+
+  return DAG.getNode(ISD::MERGE_VALUES, dl, VTs, Value, Overflow);
+}
+
 SDValue ARMTargetLowering::LowerSELECT(SDValue Op, SelectionDAG &DAG) const {
   SDValue Cond = Op.getOperand(0);
   SDValue SelectTrue = Op.getOperand(1);
   SDValue SelectFalse = Op.getOperand(2);
   SDLoc dl(Op);
   unsigned Opc = Cond.getOpcode();
 
   if (Cond.getResNo() == 1 &&
static SDValue LowerADDC_ADDE_SUBC_SUBE(SDValue Op, SelectionDAG &DAG) {
 
   if (!ExtraOp)
     return DAG.getNode(Opc, SDLoc(Op), VTs, Op.getOperand(0),
                        Op.getOperand(1));
   return DAG.getNode(Opc, SDLoc(Op), VTs, Op.getOperand(0),
                      Op.getOperand(1), Op.getOperand(2));
 }
 
+static SDValue LowerADDSUBCARRY(SDValue Op, SelectionDAG &DAG) {
+  SDNode *N = Op.getNode();
+  EVT VT = N->getValueType(0);
+  SDVTList VTs = DAG.getVTList(VT, MVT::i32);
+
+  SDValue Carry = Op.getOperand(2);
+  EVT CarryVT = Carry.getValueType();
+
+  SDLoc DL(Op);
+
+  APInt NegOne = APInt::getAllOnesValue(CarryVT.getScalarSizeInBits());
+
+  SDValue Result;
+  if (Op.getOpcode() == ISD::ADDCARRY) {
+    // This converts the boolean value carry into the carry flag by doing
+    // ARMISD::ADDC Carry, ~0
+    Carry = DAG.getNode(ARMISD::ADDC, DL, DAG.getVTList(CarryVT, MVT::i32),
+                        Carry, DAG.getConstant(NegOne, DL, CarryVT));
+
+    // Do the addition proper using the carry flag we wanted.
+    Result = DAG.getNode(ARMISD::ADDE, DL, VTs, Op.getOperand(0),
+                              Op.getOperand(1), Carry.getValue(1));
+
+    // Now convert the carry flag into a boolean value. We do this
+    // using ARMISD:ADDE 0, 0, Carry
+    Carry = DAG.getNode(ARMISD::ADDE, DL, VTs, DAG.getConstant(0, DL, MVT::i32),
+                        DAG.getConstant(0, DL, MVT::i32), Result.getValue(1));
+
+  } else {
+      // ARMISD::SUBE expects a carry not a borrow like ISD::SUBCARRY so we
+      // have to invert the carry first.
+      Carry = DAG.getNode(ISD::SUB, DL, VTs, DAG.getConstant(1, DL, MVT::i32),
+              Carry);
+      // This converts the boolean value carry into the carry flag by doing
+      // ARMISD::ADDC Carry, ~0
+      Carry = DAG.getNode(ARMISD::ADDC, DL, DAG.getVTList(CarryVT, MVT::i32),
+                          Carry, DAG.getConstant(NegOne, DL, CarryVT));
+
+      // Do the subtraction proper using the carry flag we wanted.
+      Result = DAG.getNode(ARMISD::SUBE, DL, VTs, Op.getOperand(0),
+              Op.getOperand(1), Carry.getValue(1));
+
+      // Now convert the carry flag into a boolean value. We do this
+      // using ARMISD:ADDE 0, 0, Carry
+      Carry = DAG.getNode(ARMISD::ADDE, DL, VTs, DAG.getConstant(0, DL, MVT::i32),
+              DAG.getConstant(0, DL, MVT::i32), Result.getValue(1));
+      // But the carry returned by ARMISD::SUBE is not a borrow as expected
+      // by ISD::SUBCARRY, so compute 1 - C.
+      Carry = DAG.getNode(ISD::SUB, DL, VTs, DAG.getConstant(1, DL, MVT::i32),
+              Carry);
+  }
+
+  // Return both values.
+  return DAG.getNode(ISD::MERGE_VALUES, DL, N->getVTList(), Result, Carry);
+}
+
 SDValue ARMTargetLowering::LowerFSINCOS(SDValue Op, SelectionDAG &DAG) const {
   assert(Subtarget->isTargetDarwin());
 
   // For iOS, we want to call an alternative entry point: __sincos_stret,
   // return values are passed via sret.
   SDLoc dl(Op);
   SDValue Arg = Op.getOperand(0);
   EVT ArgVT = Arg.getValueType();
SDValue ARMTargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const {
   case ISD::UDIV:
     if (Subtarget->isTargetWindows() && !Op.getValueType().isVector())
       return LowerDIV_Windows(Op, DAG, /* Signed */ false);
     return LowerUDIV(Op, DAG);
   case ISD::ADDC:
   case ISD::ADDE:
   case ISD::SUBC:
   case ISD::SUBE:          return LowerADDC_ADDE_SUBC_SUBE(Op, DAG);
+  case ISD::ADDCARRY:
+  case ISD::SUBCARRY:      return LowerADDSUBCARRY(Op, DAG);
   case ISD::SADDO:
-  case ISD::UADDO:
   case ISD::SSUBO:
+    return LowerSignedALUO(Op, DAG);
+  case ISD::UADDO:
   case ISD::USUBO:
-    return LowerXALUO(Op, DAG);
+    return LowerUnsignedALUO(Op, DAG);
   case ISD::ATOMIC_LOAD:
   case ISD::ATOMIC_STORE:  return LowerAtomicLoadStore(Op, DAG);
   case ISD::FSINCOS:       return LowerFSINCOS(Op, DAG);
   case ISD::SDIVREM:
   case ISD::UDIVREM:       return LowerDivRem(Op, DAG);
   case ISD::DYNAMIC_STACKALLOC:
     if (Subtarget->getTargetTriple().isWindowsItaniumEnvironment())
       return LowerDYNAMIC_STACKALLOC(Op, DAG);
static SDValue AddCombineTo64bitMLAL(SDNode *AddeNode,
   if (AddcOp1 == MULOp.getValue(0)) {
     LoMul = &AddcOp1;
     LowAdd = &AddcOp0;
   }
 
   if (!LoMul)
     return SDValue();
 
   // Create the merged node.
   SelectionDAG &DAG = DCI.DAG;
 
   // Build operand list.
   SmallVector<SDValue, 8> Ops;
   Ops.push_back(LoMul->getOperand(0));
   Ops.push_back(LoMul->getOperand(1));
   Ops.push_back(*LowAdd);
   Ops.push_back(*HiAdd);
 
   SDValue MLALNode =  DAG.getNode(FinalOpc, SDLoc(AddcNode),
                                  DAG.getVTList(MVT::i32, MVT::i32), Ops);
if ((AddcNode->getOpcode() == ARMISD::ADDC) &&
     return DAG.getNode(ARMISD::UMAAL, SDLoc(N),
                        DAG.getVTList(MVT::i32, MVT::i32),
                        {N->getOperand(0), N->getOperand(1),
                         AddcNode->getOperand(0), AddcNode->getOperand(1)});
   else
     return SDValue();
 }
 
-static SDValue PerformAddcSubcCombine(SDNode *N, SelectionDAG &DAG,
+static SDValue PerformAddcSubcCombine(SDNode *N,
+                                      TargetLowering::DAGCombinerInfo &DCI,
                                       const ARMSubtarget *Subtarget) {
+  SelectionDAG &DAG(DCI.DAG);
+
+  if (N->getOpcode() == ARMISD::SUBC) {
+    // (SUBC (ADDE 0, 0, C), 1) -> C
+    SDValue LHS = N->getOperand(0);
+    SDValue RHS = N->getOperand(1);
+    if (LHS->getOpcode() == ARMISD::ADDE &&
+        isNullConstant(LHS->getOperand(0)) &&
+        isNullConstant(LHS->getOperand(1)) && isOneConstant(RHS)) {
+      return DCI.CombineTo(N, SDValue(N, 0), LHS->getOperand(2));
+    }
+  }
+
+  if (N->getOpcode() == ARMISD::ADDC) {
+    // (ADDC (ADDE 0, 0, C), -1) -> C
+    SDValue LHS = N->getOperand(0);
+    SDValue RHS = N->getOperand(1);
+    if (LHS->getOpcode() == ARMISD::ADDE &&
+        isNullConstant(LHS->getOperand(0)) &&
+        isNullConstant(LHS->getOperand(1)) && isAllOnesConstant(RHS)) {
+      return DCI.CombineTo(N, SDValue(N, 0), LHS->getOperand(2));
+    }
+  }
+
   if (Subtarget->isThumb1Only()) {
     SDValue RHS = N->getOperand(1);
     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHS)) {
       int32_t imm = C->getSExtValue();
       if (imm < 0 && imm > INT_MIN) {
         SDLoc DL(N);
         RHS = DAG.getConstant(-imm, DL, MVT::i32);
         unsigned Opcode = (N->getOpcode() == ARMISD::ADDC) ? ARMISD::SUBC
                                                            : ARMISD::ADDC;
         return DAG.getNode(Opcode, DL, N->getVTList(), N->getOperand(0), RHS);
       }
     }
   }
   return SDValue();
 }
 
 static SDValue PerformAddeSubeCombine(SDNode *N, SelectionDAG &DAG,
                                       const ARMSubtarget *Subtarget) {
   if (Subtarget->isThumb1Only()) {
     SDValue RHS = N->getOperand(1);
     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(RHS)) {
       int64_t imm = C->getSExtValue();
       if (imm < 0) {
         SDLoc DL(N);
 
         // The with-carry-in form matches bitwise not instead of the negation.
         // Effectively, the inverse interpretation of the carry flag already
if (VT == MVT::i32 &&
       }
       return DAG.getNode(Opc, SDLoc(N), VT, Vec, Lane);
     }
   }
 
   return SDValue();
 }
 
+static const APInt *isPowerOf2Constant(SDValue V) {
+  ConstantSDNode *C = dyn_cast<ConstantSDNode>(V);
+  if (!C)
+    return nullptr;
+  const APInt *CV = &C->getAPIntValue();
+  return CV->isPowerOf2() ? CV : nullptr;
+}
+
 SDValue ARMTargetLowering::PerformCMOVToBFICombine(SDNode *CMOV, SelectionDAG &DAG) const {
   // If we have a CMOV, OR and AND combination such as:
   //   if (x & CN)
   //     y |= CM;
   //
   // And:
   //   * CN is a single bit;
   //   * All bits covered by CM are known zero in y
SDValue ARMTargetLowering::PerformCMOVToBFICombine(SDNode *CMOV, SelectionDAG &DAG) const {
   // The compare must be against zero.
   if (!isNullConstant(CmpZ->getOperand(1)))
     return SDValue();
 
   assert(CmpZ->getOpcode() == ARMISD::CMPZ);
   SDValue And = CmpZ->getOperand(0);
   if (And->getOpcode() != ISD::AND)
     return SDValue();
-  ConstantSDNode *AndC = dyn_cast<ConstantSDNode>(And->getOperand(1));
-  if (!AndC || !AndC->getAPIntValue().isPowerOf2())
+  const APInt *AndC = isPowerOf2Constant(And->getOperand(1));
+  if (!AndC)
     return SDValue();
   SDValue X = And->getOperand(0);
 
   if (CC == ARMCC::EQ) {
     // We're performing an "equal to zero" compare. Swap the operands so we
     // canonicalize on a "not equal to zero" compare.
     std::swap(Op0, Op1);
   } else {
SDValue ARMTargetLowering::PerformCMOVToBFICombine(SDNode *CMOV, SelectionDAG &DAG) const {
   DAG.computeKnownBits(Y, Known);
   if ((OrCI & Known.Zero) != OrCI)
     return SDValue();
 
   // OK, we can do the combine.
   SDValue V = Y;
   SDLoc dl(X);
   EVT VT = X.getValueType();
-  unsigned BitInX = AndC->getAPIntValue().logBase2();
+  unsigned BitInX = AndC->logBase2();
 
   if (BitInX != 0) {
     // We must shift X first.
     X = DAG.getNode(ISD::SRL, dl, VT, X,
                     DAG.getConstant(BitInX, dl, VT));
   }
 
   for (unsigned BitInY = 0, NumActiveBits = OrCI.getActiveBits();
SDValue ARMTargetLowering::PerformDAGCombine(SDNode *N,
   case ARMISD::UMLAL:   return PerformUMLALCombine(N, DCI.DAG, Subtarget);
   case ISD::ADD:        return PerformADDCombine(N, DCI, Subtarget);
   case ISD::SUB:        return PerformSUBCombine(N, DCI);
   case ISD::MUL:        return PerformMULCombine(N, DCI, Subtarget);
   case ISD::OR:         return PerformORCombine(N, DCI, Subtarget);
   case ISD::XOR:        return PerformXORCombine(N, DCI, Subtarget);
   case ISD::AND:        return PerformANDCombine(N, DCI, Subtarget);
   case ARMISD::ADDC:
-  case ARMISD::SUBC:    return PerformAddcSubcCombine(N, DCI.DAG, Subtarget);
+  case ARMISD::SUBC:    return PerformAddcSubcCombine(N, DCI, Subtarget);
   case ARMISD::SUBE:    return PerformAddeSubeCombine(N, DCI.DAG, Subtarget);
   case ARMISD::BFI:     return PerformBFICombine(N, DCI);
   case ARMISD::VMOVRRD: return PerformVMOVRRDCombine(N, DCI, Subtarget);
   case ARMISD::VMOVDRR: return PerformVMOVDRRCombine(N, DCI.DAG);
   case ISD::STORE:      return PerformSTORECombine(N, DCI);
   case ISD::BUILD_VECTOR: return PerformBUILD_VECTORCombine(N, DCI, Subtarget);
   case ISD::INSERT_VECTOR_ELT: return PerformInsertEltCombine(N, DCI);
   case ISD::VECTOR_SHUFFLE: return PerformVECTOR_SHUFFLECombine(N, DCI.DAG);
void ARMTargetLowering::computeKnownBitsForTargetNode(const SDValue Op,
                                                       unsigned Depth) const {
   unsigned BitWidth = Known.getBitWidth();
   Known.resetAll();
   switch (Op.getOpcode()) {
   default: break;
   case ARMISD::ADDC:
   case ARMISD::ADDE:
   case ARMISD::SUBC:
   case ARMISD::SUBE:
-    // These nodes' second result is a boolean
-    if (Op.getResNo() == 0)
-      break;
+    // Special cases when we convert a carry to a boolean.
+    if (Op.getResNo() == 0) {
+      SDValue LHS = Op.getOperand(0);
+      SDValue RHS = Op.getOperand(1);
+      // (ADDE 0, 0, C) will give us a single bit.
+      if (Op->getOpcode() == ARMISD::ADDE && isNullConstant(LHS) &&
+          isNullConstant(RHS)) {
+        Known.Zero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
+        return;
+      }
+      // SUBC (1, ADDE(0, 0, C)) gives us a single bit.
+      // FIXME: This can be probably generalized in that if the RHS just
+      // gives 1 bit, 1 - RHS will also give us 1 bit.
+      if (Op->getOpcode() == ARMISD::SUBC && isOneConstant(LHS) &&
+          RHS->getOpcode() == ARMISD::ADDE &&
+          isNullConstant(RHS->getOperand(0)) &&
+          isNullConstant(RHS->getOperand(1))) {
         Known.Zero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
+        return;
+      }
+    }
     break;
   case ARMISD::CMOV: {
     // Bits are known zero/one if known on the LHS and RHS.
     DAG.computeKnownBits(Op.getOperand(0), Known, Depth+1);
     if (Known.isUnknown())
       return;
 
     KnownBits KnownRHS;

test/CodeGen/ARM/intrinsics-overflow.ll

-; RUN: llc < %s -mtriple=arm-linux -mcpu=generic | FileCheck %s
+; RUN: llc < %s -mtriple=arm-linux -mcpu=generic -verify-machineinstrs | FileCheck %s --check-prefix=CHECK --check-prefix=ARM
+; RUN: llc < %s -mtriple=thumbv6m-eabi -verify-machineinstrs | FileCheck %s --check-prefix=CHECK --check-prefix=THUMBV6
+; RUN: llc < %s -mtriple=thumbv7-eabi -verify-machineinstrs | FileCheck %s --check-prefix=CHECK --check-prefix=THUMBV7
 
 define i32 @uadd_overflow(i32 %a, i32 %b) #0 {
   %sadd = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %a, i32 %b)
   %1 = extractvalue { i32, i1 } %sadd, 1
   %2 = zext i1 %1 to i32
   ret i32 %2
 
   ; CHECK-LABEL: uadd_overflow:
-  ; CHECK: add r[[R2:[0-9]+]], r[[R0:[0-9]+]], r[[R1:[0-9]+]]
-  ; CHECK: mov r[[R1]], #1
-  ; CHECK: cmp r[[R2]], r[[R0]]
-  ; CHECK: movhs r[[R1]], #0
+
+  ; ARM: adds r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
+  ; ARM: mov r[[R2:[0-9]+]], #0
+  ; ARM: adc r[[R0]], r[[R2]], #0
+
+  ; THUMBV6: movs    r[[R2:[0-9]+]], #0
+  ; THUMBV6: adds    r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
+  ; THUMBV6: adcs    r[[R2]], r[[R2]]
+  ; THUMBV6: mov     r[[R0]], r[[R2]]
+
+  ; THUMBV7: adds  r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
+  ; THUMBV7: mov.w r[[R2:[0-9]+]], #0
+  ; THUMBV7: adc   r[[R0]], r[[R2]], #0
 }
 
 
 define i32 @sadd_overflow(i32 %a, i32 %b) #0 {
   %sadd = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %a, i32 %b)
   %1 = extractvalue { i32, i1 } %sadd, 1
   %2 = zext i1 %1 to i32
   ret i32 %2
 
   ; CHECK-LABEL: sadd_overflow:
-  ; CHECK: add r[[R2:[0-9]+]], r[[R0:[0-9]+]], r[[R1:[0-9]+]]
-  ; CHECK: mov r[[R1]], #1
-  ; CHECK: cmp r[[R2]], r[[R0]]
-  ; CHECK: movvc r[[R1]], #0
+
+  ; ARM: add r[[R2:[0-9]+]], r[[R0:[0-9]+]], r[[R1:[0-9]+]]
+  ; ARM: mov r[[R1]], #1
+  ; ARM: cmp r[[R2]], r[[R0]]
+  ; ARM: movvc r[[R1]], #0
+
+  ; THUMBV6: mov  r[[R2:[0-9]+]], r[[R0:[0-9]+]]
+  ; THUMBV6: adds r[[R3:[0-9]+]], r[[R2]], r[[R1:[0-9]+]]
+  ; THUMBV6: movs r[[R0]], #0
+  ; THUMBV6: movs r[[R1]], #1
+  ; THUMBV6: cmp  r[[R3]], r[[R2]]
+  ; THUMBV6: bvc  .L[[LABEL:.*]]
+  ; THUMBV6: mov  r[[R0]], r[[R1]]
+  ; THUMBV6: .L[[LABEL]]:
+
+  ; THUMBV7: movs  r[[R1]], #1
+  ; THUMBV7: cmp   r[[R2]], r[[R0]]
+  ; THUMBV7: it    vc
+  ; THUMBV7: movvc r[[R1]], #0
+  ; THUMBV7: mov   r[[R0]], r[[R1]]
 }
 
 define i32 @usub_overflow(i32 %a, i32 %b) #0 {
   %sadd = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %a, i32 %b)
   %1 = extractvalue { i32, i1 } %sadd, 1
   %2 = zext i1 %1 to i32
   ret i32 %2
 
   ; CHECK-LABEL: usub_overflow:
-  ; CHECK: mov r[[R2]], #1
-  ; CHECK: cmp r[[R0]], r[[R1]]
-  ; CHECK: movhs r[[R2]], #0
+
+  ; ARM: subs    r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
+  ; ARM: mov     r[[R2:[0-9]+]], #0
+  ; ARM: adc     r[[R0]], r[[R2]], #0
+  ; ARM: rsb     r[[R0]], r[[R0]], #1
+
+  ; THUMBV6: movs    r[[R2:[0-9]+]], #0
+  ; THUMBV6: subs    r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
+  ; THUMBV6: adcs    r[[R2]], r[[R2]]
+  ; THUMBV6: movs    r[[R0]], #1
+  ; THUMBV6: subs    r[[R0]], r[[R0]], r[[R2]]
+
+  ; THUMBV7: subs    r[[R0:[0-9]+]], r[[R0]], r[[R1:[0-9]+]]
+  ; THUMBV7: mov.w   r[[R2:[0-9]+]], #0
+  ; THUMBV7: adc     r[[R0]], r[[R2]], #0
+  ; THUMBV7: rsb.w   r[[R0]], r[[R0]], #1
+
+  ; We should know that the overflow is just 1 bit,
+  ; no need to clear any other bit
+  ; CHECK-NOT: and
 }
 
 define i32 @ssub_overflow(i32 %a, i32 %b) #0 {
   %sadd = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %a, i32 %b)
   %1 = extractvalue { i32, i1 } %sadd, 1
   %2 = zext i1 %1 to i32
   ret i32 %2
 
   ; CHECK-LABEL: ssub_overflow:
-  ; CHECK: mov r[[R2]], #1
-  ; CHECK: cmp r[[R0]], r[[R1]]
-  ; CHECK: movvc r[[R2]], #0
+
+  ; ARM: mov r[[R2]], #1
+  ; ARM: cmp r[[R0]], r[[R1]]
+  ; ARM: movvc r[[R2]], #0
+
+  ; THUMBV6: movs    r[[R0]], #0
+  ; THUMBV6: movs    r[[R3:[0-9]+]], #1
+  ; THUMBV6: cmp     r[[R2]], r[[R1:[0-9]+]]
+  ; THUMBV6: bvc     .L[[LABEL:.*]]
+  ; THUMBV6: mov     r[[R0]], r[[R3]]
+  ; THUMBV6: .L[[LABEL]]:
+
+  ; THUMBV7: movs  r[[R2:[0-9]+]], #1
+  ; THUMBV7: cmp   r[[R0:[0-9]+]], r[[R1:[0-9]+]]
+  ; THUMBV7: it    vc
+  ; THUMBV7: movvc r[[R2]], #0
+  ; THUMBV7: mov   r[[R0]], r[[R2]]
 }
 
 declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32) #1
 declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) #2
 declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32) #3
 declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32) #4