[SelectionDAG] Combine U{ADD,SUB}O diamonds into {ADD,SUB}CARRY

[davezarzycki]

Summary

Convert (uaddo (uaddo x, y), carryIn) into addcarry x, y, carryIn if-and-only-if the carry flags of the first two uaddo are merged via OR or XOR.

Work remaining: match ADD, etc.

[davezarzycki]

Can somebody CC the right System Z experts? A couple of their tests fail after this change.

[RKSimon]

@davezarzycki Please can you give more detail on the SystemZ breakages?

[davezarzycki]

With all the targets enabled, only System Z fails. It looks like somebody just needs to update the assembly.

FAIL: LLVM :: CodeGen/SystemZ/int-uadd-03.ll (15196 of 34316)
******************** TEST 'LLVM :: CodeGen/SystemZ/int-uadd-03.ll' FAILED ********************
Script:
--
: 'RUN: at line 3';   /home/dave/b/l/t/bin/llc < /home/dave/s/l/llvm/test/CodeGen/SystemZ/int-uadd-03.ll -mtriple=s390x-linux-gnu | /home/dave/b/l/t/bin/FileCheck /home/dave/s/l/llvm/test/CodeGen/SystemZ/int-uadd-03.ll
--
Exit Code: 1

Command Output (stderr):
--
/home/dave/s/l/llvm/test/CodeGen/SystemZ/int-uadd-03.ll:202:10: error: CHECK: expected string not found in input
; CHECK: algf %r2, 160(%r15)
         ^
<stdin>:207:2: note: scanning from here
 llgfr %r1, %r13
 ^
<stdin>:239:2: note: possible intended match here
 algf %r1, 160(%r15) # 4-byte Folded Reload
 ^

--

********************
FAIL: LLVM :: CodeGen/SystemZ/int-usub-03.ll (15237 of 34316)
******************** TEST 'LLVM :: CodeGen/SystemZ/int-usub-03.ll' FAILED ********************
Script:
--
: 'RUN: at line 3';   /home/dave/b/l/t/bin/llc < /home/dave/s/l/llvm/test/CodeGen/SystemZ/int-usub-03.ll -mtriple=s390x-linux-gnu | /home/dave/b/l/t/bin/FileCheck /home/dave/s/l/llvm/test/CodeGen/SystemZ/int-usub-03.ll
--
Exit Code: 1

Command Output (stderr):
--
/home/dave/s/l/llvm/test/CodeGen/SystemZ/int-usub-03.ll:210:10: error: CHECK: expected string not found in input
; CHECK: slgf %r2, 160(%r15)
         ^
<stdin>:215:2: note: scanning from here
 lgr %r3, %r2
 ^
<stdin>:251:2: note: possible intended match here
 slgf %r1, 160(%r15) # 4-byte Folded Reload
 ^

--

********************

Testing Time: 34.33s
********************
Failing Tests (2):
    LLVM :: CodeGen/SystemZ/int-uadd-03.ll
    LLVM :: CodeGen/SystemZ/int-usub-03.ll

  Expected Passes    : 33723
  Expected Failures  : 150
  Unsupported Tests  : 441
  Unexpected Failures: 2

[RKSimon]

Why can't you include the updated systemz tests in this patch?

[uweigand]

It looks like the check is a bit too strict, something like the following should fix the problem:

diff --git a/llvm/test/CodeGen/SystemZ/int-uadd-03.ll b/llvm/test/CodeGen/SystemZ/int-uadd-03.ll
index d57f8a84411..b7b9883ecc9 100644
--- a/llvm/test/CodeGen/SystemZ/int-uadd-03.ll
+++ b/llvm/test/CodeGen/SystemZ/int-uadd-03.ll
@@ -199,7 +199,7 @@ define zeroext i1 @f10(i64 %src, i64 %index, i64 %a, i64 *%res) {
 define zeroext i1 @f11(i32 *%ptr0) {
 ; CHECK-LABEL: f11:
 ; CHECK: brasl %r14, foo@PLT
-; CHECK: algf %r2, 160(%r15)
+; CHECK: algf {{%r[0-9]+}}, 160(%r15)
 ; CHECK: br %r14
   %ptr1 = getelementptr i32, i32 *%ptr0, i64 2
   %ptr2 = getelementptr i32, i32 *%ptr0, i64 4
diff --git a/llvm/test/CodeGen/SystemZ/int-usub-03.ll b/llvm/test/CodeGen/SystemZ/int-usub-03.ll
index 4e5f99fcee2..5e0a947772c 100644
--- a/llvm/test/CodeGen/SystemZ/int-usub-03.ll
+++ b/llvm/test/CodeGen/SystemZ/int-usub-03.ll
@@ -207,7 +207,7 @@ define zeroext i1 @f10(i64 %src, i64 %index, i64 %a, i64 *%res) {
 define zeroext i1 @f11(i32 *%ptr0) {
 ; CHECK-LABEL: f11:
 ; CHECK: brasl %r14, foo@PLT
-; CHECK: slgf %r2, 160(%r15)
+; CHECK: slgf {{%r[0-9]+}}, 160(%r15)
 ; CHECK: br %r14
   %ptr1 = getelementptr i32, i32 *%ptr0, i64 2
   %ptr2 = getelementptr i32, i32 *%ptr0, i64 4
}

[davezarzycki]

1. Merged the minor System Z fixes into the prerequisite patch: https://reviews.llvm.org/D70077
2. Added a paranoia check to ensure that the carry in value is i1.

[RKSimon]

@davezarzycki Please can you rebase?

[davezarzycki]

Rebased with regenerated tests.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2825

We handle OR and XOR here but I don't see anything that treats them differently.

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2825

That's because it doesn't matter in this scenario. Either (uaddo A, B) overflows, or (uaddo *, In) overflows, but they cannot both overflow. I can add a comment about this if you want.

[RKSimon]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2825

yes please - your diagram doesn't mention xor at all

[davezarzycki]

Added commentary about how it's impossible for both carry bits in the diamond to be set at the same time.

[spatel]

(added potential reviewers based on carry/overflow experience)

[davezarzycki]

Thank you @spatel for adding more reviewers. Questions I have as a non-expert of LLVM design:

1. Why is UADDO/USUBO an intrinsic but ADDCARRY/SUBCARRY is not? This is unfortunate given that clang and perhaps other languages have addcarry/subcarry intrinsics.
2. Is the diamond being updated correctly? Or does it work by accident?
3. Is there a good example of how to break a diamond when updating the DAG?

[chfast]

Oh sh*i, this is the same thing I'm doing in https://reviews.llvm.org/D70012.

At least I can add my tests to the pool :)

[spatel]

In D70079#1745241, @davezarzycki wrote:

1. Why is UADDO/USUBO an intrinsic but ADDCARRY/SUBCARRY is not? This is unfortunate given that clang and perhaps other languages have addcarry/subcarry intrinsics.

I don't know the full history, but my guess is that the *.with.overflow intrinsics were assumed to be good enough to hold the patterns together through IR optimization, and the backend could relatively easily map those to DAG nodes. If that's not correct, then we could make a case for adding to, extending, or replacing the current set of intrinsics.

That does lead to questions I was already wondering about:

1. Can we do this transform in IR (instcombine)?
2. There are tests with intrinsics and tests with "raw" IR - are we missing IR transforms that should canonicalize to 1 form or the other?

[davezarzycki]

In D70079#1745594, @spatel wrote:

In D70079#1745241, @davezarzycki wrote:

1. Why is UADDO/USUBO an intrinsic but ADDCARRY/SUBCARRY is not? This is unfortunate given that clang and perhaps other languages have addcarry/subcarry intrinsics.

I don't know the full history, but my guess is that the *.with.overflow intrinsics were assumed to be good enough to hold the patterns together through IR optimization, and the backend could relatively easily map those to DAG nodes. If that's not correct, then we could make a case for adding to, extending, or replacing the current set of intrinsics.

That does lead to questions I was already wondering about:

1. Can we do this transform in IR (instcombine)?
2. There are tests with intrinsics and tests with "raw" IR - are we missing IR transforms that should canonicalize to 1 form or the other?

As the first question and according to the SCM history (r234638 / b6c5914308132acc9289335ed6a92b31f9484631):

This change moves creating calls to llvm.uadd.with.overflow from InstCombine to CodeGenPrep. Combining overflow check patterns into calls to the said intrinsic in InstCombine inhibits optimization because it introduces an intrinsic call that not all other transforms and analyses understand.

As to the second question, the tests with intrinsics was generated via clang's __builtin_addc/subc. The tests without intrinsics were generated via pure C and hence more potential solutions exist that can be matched.

[EDIT] – I should add that CodeGenPrep doesn't match all eligible cases where llvm.uadd.with.overflow is possible, which hurts this proposed optimization.

[davezarzycki]

Hi everybody. Feedback is still appreciated. What's blocking this change from being committed?

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2844–2849

I find this confusing.
Which one of Carry0 and Carry1 is the first one?
Can this be simplified to something like

// ???
if (Carry1.getOperand(0) != Carry0.getValue(0))
  std::swap(Carry0, Carry1);
if (Carry1.getOperand(0) != Carry0.getValue(0))
  return SDValue();

This would be more idiomatic..

2854–2856

Do we care what Carry0.getOperand(1) is, what produces it?

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2844–2849

Sure. I can refactor that. I guess the comment wasn't clear enough. The code wants the UADDO (or USUBO) that does the primary arithmetic to be Carry0. I.e. the node at the top of the ASCII art. The UADDO (or USUBO) that does the carry/borrow in is Carry1. I.e. the node in the middle of the ASCII art.

2854–2856

We want that operand to be a carry bit (or at least plausibly so), so that we don't create bogus addcarry/subcarry nodes.

[davezarzycki]

1. Check TLI.isOperationLegalOrCustom().
2. Handle AND being used to merge flags.
3. More source comments.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2821–2822

Since you've drawn the original graph, also showing the result might be good?

2844–2849

Please mark done comments as done.

2848

Ah, so the numbering is from bottom to top, i expected the other way around.

2855–2857

s/ISDOp/NewOp/

2863–2867

There's getAsCarry() should it be used here, or are we okay with some other i1?
(can we have some other i1 by now?)

2873–2876

This could use a few comments

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2848

I've swapped the ordering to match your expectations.

2863–2867

That function is non-recursive, so it doesn't work. In other words, it doesn't know how to handle carry flags being merged. I can change that if people are okay with that.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2848

(It's just that i think this ordering is more prevalent, i've practically not seen the opposite ordering in the codebase)

2863–2867

No real opinion from me here.

2875

I'm not following this bit, why do we do this only for ISD::AND?

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2875

As the comment above tries to explain, we can prove in this diamond UADDO/USUBO scenario that it is impossible for both UADDO/USUBO nodes to overflow at the same time. Either one does, or the other, therefore using AND to merge the carry flags will always return zero.

[chfast]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2850

Have you seen the getAsCarry() helper? It might help simplifying matching here.

2856

The ADDCARRY rather replaces UADDO so you should use the debug location of the Carry1 node.

2875

I think you should use CombineTo() here to bump stats counters, produce some debug logs, updated worklist and delete replaced nodes.

It can be something like:

CombineTo(Carry1.getNode(), Merged.getValue(0), undef);
return CombineTo(N, Merged.getValue(1));

Both Carry1 and N should be deleted by CombineTo().

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2850

As mentioned elsewhere in this thread, getAsCarry() would need to be updated in order to be used here. In particular, it would need become aware of this proposed optimization because the carry flag might not have been merged yet.

2856

The ADDCARRY replaces three operations. Why is one node better than another for the debug location?

2875

Okay. I'll look into that.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2856

I'd say the current debuginfo is correct.

2875

As the comment above tries to explain, we can prove in this diamond UADDO/USUBO scenario that it is impossible for both UADDO/USUBO nodes to overflow at the same time. Either one does, or the other, therefore using AND to merge the carry flags will always return zero.

Yes, but that wasn't the question i was asking.
My question was - what happens with uses of Carry1.getValue(0) if we have non-AND?
Since you don't replace, they will still use old nodes,
which means the old instruction chain will stay?
I think this may missing more tests.

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2875

There is a test for the zero case. See bogus_add_U320_without_i128_and in addcarry.ll.

In any case, I'll switch to CombineTo

[davezarzycki]

Switch to DAGCombiner::CombineTo

[davezarzycki]

With the exception of some debate among the reviewers about what the right debug location should be, I think I've addressed all actionable comments so far.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2875

FWIW the previous version (no CombineTo(), only a singled RAUW call) looked more better to me,
but maybe i'm missing the point as to why that was wrong.

2876–2877

I'm sorry, i still don't understand why this is being done only in ISD::AND case.
Please explain that in a new comment in the code.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2876–2877

To be specific, i don't understand why this isn't:

DAG.ReplaceAllUsesOfValueWith(Carry1.getValue(0), Merged.getValue(0)); // debatable, but done always
if (N->getOpcode() == ISD::AND) // Both carrys can't overflow at the same time
  return DAG.getConstant(0, DL, MVT::i1);
return Merged.getValue(1);

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2876–2877

That also works. I'll switch to that.

Why in your mind is the first line of your suggestion "debatable"?

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2876–2877

Because i do not understand why currently Combiner.CombineTo() is used,
maybe using DAG.ReplaceAllUsesOfValueWith() would be incorrect there.

[chfast]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2875

To my understanding CombineTo() is a rich version of RAUW. It does RAUW, but also can add new nodes to the DAG Combiner worklist, updates DAG combiner stats, prints debug logs about which nodes has been combined into which, handles removed nodes.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2875

I would think simply returning the new value would be enough,
and whatever code called us will do all the same anyway?

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2876–2877

I tried this:

-  Combiner.CombineTo(Carry1.getNode(), Merged.getValue(0),
-                     DAG.getUNDEF(Merged.getValue(1).getValueType()));
+  DAG.ReplaceAllUsesOfValueWith(Carry1.getValue(0), Merged.getValue(0));
   if (N->getOpcode() == ISD::AND)
-    return Combiner.CombineTo(N, DAG.getConstant(0, DL, MVT::i1));
-  return Combiner.CombineTo(N, Merged.getValue(1));
+    return DAG.getConstant(0, DL, MVT::i1);
+  return Merged.getValue(1);

And it also worked. Who is responsible for this code and decide which approach is preferable?

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2876–2877

Ping. @RKSimon @spatel @craig.topper – As the top three committers to DAGCombiner.cpp in the last two years, do you have any preference about DAG.ReplaceAllUsesOfValueWith(…) versus Combiner.CombineTo(…)? Otherwise I believe that all feedback has been addressed to date. What's blocking approval? Thanks! :-)

[craig.topper]

Why does Carry1's result 0 not get replaced for the xor/or case?

[davezarzycki]

Unless I'm misunderstanding you, I think the many rounds of review feedback are clouding the code review. Lines 2874 and 2875 replace Carry1's result 0 in all cases (OR, XOR, and AND).

[craig.topper]

In D70079#1752986, @davezarzycki wrote:

Unless I'm misunderstanding you, I think the many rounds of review feedback are clouding the code review. Lines 2874 and 2875 replace Carry1's result 0 in all cases (OR, XOR, and AND).

Doesn't line 2873 return if the opcode is not ISD::AND?

[davezarzycki]

In D70079#1752991, @craig.topper wrote:

In D70079#1752986, @davezarzycki wrote:

Unless I'm misunderstanding you, I think the many rounds of review feedback are clouding the code review. Lines 2874 and 2875 replace Carry1's result 0 in all cases (OR, XOR, and AND).

Doesn't line 2873 return if the opcode is not ISD::AND?

Ah. Oops. I paused on uploading new patches while @chfast and @lebedev.ri were debating whether DAG.ReplaceAllUsesOfValueWith(…) or Combiner.CombineTo(…) was better. (Do you have a preference?) I'll update the patch now with the former.

[davezarzycki]

Update the patch now that the DAG RAUW versus Combiner discussion has settled down. I personally like the former because it's simpler, but I do like the arguments in favor of the DAGCombiner. Either way, I'll defer to a code owner.

[lebedev.ri]

Almost LG to me, but apparently i have more comments.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2812

Wait, In is some third carry-in bit, right? This diagram doesn't really make that obvious.

2820

Out = (addcarry A, B, In).carry

2837–2840

Why can Carry0.getValue(0) only be in Carry1.getOperand(0), but not in Carry1.getOperand(1)?
I think there is no such restriction at least for add.

2846–2848

We are replacing and/or/xor node, and we only create a single replacement node,
so i don't think we need any one-use checks here?

2849

I think it will be helpful to

SDValue CarryBit = Carry1.getOperand(1);

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2812

No. There is one carry in bit in this graph: In. There are two carry out bits being merged in a way that implies an addcarry or subcarry is possible. I can try to make this more obvious.

2820

Sure. In the next patch.

2837–2840

Sure. I'll make it more robust in the next patch. For whatever it may be worth, this is the order output by CodeGenPrepare when creates implicit UADDO/USUBO nodes. It's also happens to be the order that clang generates via its addc/subc builtins.

2846–2848

I was trying to be conservative. After some thought, I think dropping the one-use tests is harmless. I'll remove them from the next patch.

2849

Sure. In the next patch.

[davezarzycki]

1. Prettier ASCII art.
2. Add robustness against the carry in bit swapping positions during optimization passes.
3. Dropped use-once checks on the first uaddo/usubo node.

[davezarzycki]

This patch fixes a bug introduced during the last round of feedback. By making the patch robust against the optimizer swapping operands to UADDO, the patch started tolerating the carry in bit being on the lefthand side of USUBO. That is wrong, and it's now fixed.

[lebedev.ri]

With latest update i think this is basically LG, last few non-functional comments.
But please wait a bit for @deadalnix / @craig.topper / @RKSimon.

In D70079#1753410, @davezarzycki wrote:

This patch fixes a bug introduced during the last round of feedback. By making the patch robust against the optimizer swapping operands to UADDO, the patch started tolerating the carry in bit being on the lefthand side of USUBO. That is wrong, and it's now fixed.

Thank you! I was just figuring out if that bug *wasn't* there.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2815

Since you are drawing add, you could swap it's operands, and thus CarryIn wouldn't have to intercept PartialCarryOutX. Just a thought, not sure it matters.

2861–2864

if (CarryIn.getOpcode() != ISD::ZERO_EXTEND)
  return SDValue();
CarryIn = CarryIn.getOperand(0);
if (CarryIn.getValueType() != MVT::i1)
  return SDValue();

It's better than seeing CarryIn.getOperand(0) later and going "wait what why we use first operand from CarryIn instruction?"

2869

CarryIn);

[lebedev.ri]

test/CodeGen/X86/addcarry.ll

623

Please precommit all tests first.

[davezarzycki]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2815

I'd really rather not. The current diagram matches the UADDO/USUBO generated by CodeGenPrepare from plain IR. It also matches the UADDO/USUBO that clang emits as a part of its builtin addc/subc intrinsics. Also, if one substitutes usubo for uaddo, the diagram still holds true, whereas if the add operands were swapped, the diagram would be wrong for usubo.

2861–2864

Sure. I'll change that before committing.

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2815

Sure, that was only an observation.

[davezarzycki]

test/CodeGen/X86/addcarry.ll

623

Oh, whoops. I missed this feedback once I saw the "ready to land" status change. Sorry. At least all of the other tests were pre-committed.

[davezarzycki]

257acbf6aee983227a3976d10d0086f3600f2bee

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2831

Just make it a member function?

2839–2840

Very last note, i think it would be best to also

if (N->getOpcode() != ISD::AND && N->getOpcode() != ISD::OR && N->getOpcode() != ISD::XOR)
  return SDValue();

(or maybe that should be an assert)

[lebedev.ri]

In D70079#1753459, @davezarzycki wrote:

257acbf6aee983227a3976d10d0086f3600f2bee

There was this line:

In D70079#1753422, @lebedev.ri wrote:

But please wait a bit for @deadalnix / @craig.topper / @RKSimon.

[davezarzycki]

In D70079#1753468, @lebedev.ri wrote:

In D70079#1753459, @davezarzycki wrote:

257acbf6aee983227a3976d10d0086f3600f2bee

There was this line:

In D70079#1753422, @lebedev.ri wrote:

But please wait a bit for @deadalnix / @craig.topper / @RKSimon.

Oh, sorry, I missed that there was a comment above the quoted text in addition to below it. I'm happy to revert this if somebody wants, or fix things in a followup patch.

[deadalnix]

I'm a bit late to the party, but this is nothing short of amazing. Congratulations!

[chfast]

I have found one case not covered by this case: in case of subtraction when we only care about the final carry bit (the difference is discarded) the first subtraction will be to compare. So here we may want to also search for cmp. I did a prototype by duplicating this code and modifying in for the cmp case only it this works. But I'm not sure if mixing it all here will be good idea. Anyway, I wanted to reach out about it and maybe fix the TODO from this patch in the mean time.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2864

Do you remember this TODO here? I'd like to fix it if you can provide more details about it.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

static SDValue combineADDCARRYDiamond(DAGCombiner &Combiner, SelectionDAG &DAG,
 
   if (Carry1.getOperand(1) == Carry0.getValue(0)) {
     return cancelDiamond(Carry1.getOperand(0), Carry0.getOperand(0));
   }
 
   return SDValue();
 }
 
+// If we are facing some sort of diamond carry/borrow in/out pattern try to
+// match patterns like:
+//
+//          (uaddo A, B)            CarryIn
+//            |  \                     |
+//            |   \                    |
+//    PartialSum   PartialCarryOutX   /
+//            |        |             /
+//            |    ____|____________/
+//            |   /    |
+//     (uaddo *, *)    \________
+//       |  \                   \
+//       |   \                   |
+//       |    PartialCarryOutY   |
+//       |        \              |
+//       |         \            /
+//   AddCarrySum    |    ______/
+//                  |   /
+//   CarryOut = (or *, *)
+//
+// And generate ADDCARRY (or SUBCARRY) with two result values:
+//
+//    {AddCarrySum, CarryOut} = (addcarry A, B, CarryIn)
+//
+// Our goal is to identify A, B, and CarryIn and produce ADDCARRY/SUBCARRY with
+// a single path for carry/borrow out propagation:
+static SDValue combineCarryDiamond(DAGCombiner &Combiner, SelectionDAG &DAG,
+                                   const TargetLowering &TLI, SDValue Carry0,
+                                   SDValue Carry1, SDNode *N) {
+  if (Carry0.getResNo() != 1 || Carry1.getResNo() != 1)
+    return SDValue();
+  unsigned Opcode = Carry0.getOpcode();
+  if (Opcode != Carry1.getOpcode())
+    return SDValue();
+  if (Opcode != ISD::UADDO && Opcode != ISD::USUBO)
+    return SDValue();
+
+  // Canonicalize the add/sub of A and B as Carry0 and the add/sub of the
+  // carry/borrow in as Carry1. (The top and middle uaddo nodes respectively in
+  // the above ASCII art.)
+  if (Carry1.getOperand(0) != Carry0.getValue(0) &&
+      Carry1.getOperand(1) != Carry0.getValue(0))
+    std::swap(Carry0, Carry1);
+  if (Carry1.getOperand(0) != Carry0.getValue(0) &&
+      Carry1.getOperand(1) != Carry0.getValue(0))
+    return SDValue();
+
+  // The carry in value must be on the righthand side for subtraction.
+  unsigned CarryInOperandNum =
+      Carry1.getOperand(0) == Carry0.getValue(0) ? 1 : 0;
+  if (Opcode == ISD::USUBO && CarryInOperandNum != 1)
+    return SDValue();
+  SDValue CarryIn = Carry1.getOperand(CarryInOperandNum);
+
+  unsigned NewOp = Opcode == ISD::UADDO ? ISD::ADDCARRY : ISD::SUBCARRY;
+  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();
+  if (CarryIn.getOperand(0).getValueType() != MVT::i1)
+    return SDValue();
+
+  SDLoc DL(N);
+  SDValue Merged =
+      DAG.getNode(NewOp, DL, Carry1->getVTList(), Carry0.getOperand(0),
+                  Carry0.getOperand(1), CarryIn.getOperand(0));
+
+  // Please note that because we have proven that the result of the UADDO/USUBO
+  // of A and B feeds into the UADDO/USUBO that does the carry/borrow in, we can
+  // therefore prove that if the first UADDO/USUBO overflows, the second
+  // UADDO/USUBO cannot. For example consider 8-bit numbers where 0xFF is the
+  // maximum value.
+  //
+  //   0xFF + 0xFF == 0xFE with carry but 0xFE + 1 does not carry
+  //   0x00 - 0xFF == 1 with a carry/borrow but 1 - 1 == 0 (no carry/borrow)
+  //
+  // This is important because it means that OR and XOR can be used to merge
+  // carry flags; and that AND can return a constant zero.
+  //
+  // TODO: match other operations that can merge flags (ADD, etc)
+  DAG.ReplaceAllUsesOfValueWith(Carry1.getValue(0), Merged.getValue(0));
+  if (N->getOpcode() == ISD::AND)
+    return DAG.getConstant(0, DL, MVT::i1);
+  return Merged.getValue(1);
+}
+
 SDValue DAGCombiner::visitADDCARRYLike(SDValue N0, SDValue N1, SDValue CarryIn,
                                        SDNode *N) {
   // fold (addcarry (xor a, -1), b, c) -> (subcarry b, a, !c) and flip carry.
   if (isBitwiseNot(N0))
     if (SDValue NotC = extractBooleanFlip(CarryIn, DAG, TLI, true)) {
       SDLoc DL(N);
       SDValue Sub = DAG.getNode(ISD::SUBCARRY, DL, N->getVTList(), N1,
                                 N0.getOperand(0), NotC);
SDValue DAGCombiner::visitAND(SDNode *N) {
   if (SDValue RAND = reassociateOps(ISD::AND, SDLoc(N), N0, N1, N->getFlags()))
     return RAND;
 
   // Try to convert a constant mask AND into a shuffle clear mask.
   if (VT.isVector())
     if (SDValue Shuffle = XformToShuffleWithZero(N))
       return Shuffle;
 
+  if (SDValue Combined = combineCarryDiamond(*this, DAG, TLI, N0, N1, N))
+    return Combined;
+
   // fold (and (or x, C), D) -> D if (C & D) == D
   auto MatchSubset = [](ConstantSDNode *LHS, ConstantSDNode *RHS) {
     return RHS->getAPIntValue().isSubsetOf(LHS->getAPIntValue());
   };
   if (N0.getOpcode() == ISD::OR &&
       ISD::matchBinaryPredicate(N0.getOperand(1), N1, MatchSubset))
     return N1;
   // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits.
SDValue DAGCombiner::visitOR(SDNode *N) {
 
   // fold (or x, c) -> c iff (x & ~c) == 0
   if (N1C && DAG.MaskedValueIsZero(N0, ~N1C->getAPIntValue()))
     return N1;
 
   if (SDValue Combined = visitORLike(N0, N1, N))
     return Combined;
 
+  if (SDValue Combined = combineCarryDiamond(*this, DAG, TLI, N0, N1, N))
+    return Combined;
+
   // Recognize halfword bswaps as (bswap + rotl 16) or (bswap + shl 16)
   if (SDValue BSwap = MatchBSwapHWord(N, N0, N1))
     return BSwap;
   if (SDValue BSwap = MatchBSwapHWordLow(N, N0, N1))
     return BSwap;
 
   // reassociate or
   if (SDValue ROR = reassociateOps(ISD::OR, SDLoc(N), N0, N1, N->getFlags()))
SDValue DAGCombiner::visitXOR(SDNode *N) {
   // Unfold  ((x ^ y) & m) ^ y  into  (x & m) | (y & ~m)  if profitable
   if (SDValue MM = unfoldMaskedMerge(N))
     return MM;
 
   // Simplify the expression using non-local knowledge.
   if (SimplifyDemandedBits(SDValue(N, 0)))
     return SDValue(N, 0);
 
+  if (SDValue Combined = combineCarryDiamond(*this, DAG, TLI, N0, N1, N))
+    return Combined;
+
   return SDValue();
 }
 
 /// If we have a shift-by-constant of a bitwise logic op that itself has a
 /// shift-by-constant operand with identical opcode, we may be able to convert
 /// that into 2 independent shifts followed by the logic op. This is a
 /// throughput improvement.
 static SDValue combineShiftOfShiftedLogic(SDNode *Shift, SelectionDAG &DAG) {

test/CodeGen/X86/addcarry.ll

; CHECK-NEXT:    retq
   %46 = zext i1 %45 to i32
   %47 = add nuw nsw i32 %46, %44
   ret i32 %47
 }
 
 define i32 @add_U320_without_i128_or(%struct.U320* nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) {
 ; CHECK-LABEL: add_U320_without_i128_or:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    pushq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    .cfi_offset %rbx, -16
-; CHECK-NEXT:    addq 8(%rdi), %rdx
-; CHECK-NEXT:    setb %r10b
 ; CHECK-NEXT:    addq %rsi, (%rdi)
-; CHECK-NEXT:    adcq $0, %rdx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addq 16(%rdi), %rcx
-; CHECK-NEXT:    setb %r11b
-; CHECK-NEXT:    orb %r10b, %al
-; CHECK-NEXT:    movzbl %al, %ebx
-; CHECK-NEXT:    addq %rcx, %rbx
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    addq 24(%rdi), %r8
-; CHECK-NEXT:    setb %r10b
-; CHECK-NEXT:    orb %r11b, %cl
-; CHECK-NEXT:    movzbl %cl, %esi
-; CHECK-NEXT:    addq %r8, %rsi
+; CHECK-NEXT:    adcq %rdx, 8(%rdi)
+; CHECK-NEXT:    adcq %rcx, 16(%rdi)
+; CHECK-NEXT:    adcq %r8, 24(%rdi)
+; CHECK-NEXT:    adcq %r9, 32(%rdi)
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addq 32(%rdi), %r9
-; CHECK-NEXT:    setb %r8b
-; CHECK-NEXT:    orb %r10b, %al
 ; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    addq %r9, %rax
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    movq %rdx, 8(%rdi)
-; CHECK-NEXT:    movq %rbx, 16(%rdi)
-; CHECK-NEXT:    movq %rsi, 24(%rdi)
-; CHECK-NEXT:    movq %rax, 32(%rdi)
-; CHECK-NEXT:    orb %r8b, %cl
-; CHECK-NEXT:    movzbl %cl, %eax
-; CHECK-NEXT:    popq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 8
 ; CHECK-NEXT:    retq
   %7 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 0
   %8 = load i64, i64* %7, align 8
   %9 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 1
   %10 = load i64, i64* %9, align 8
   %11 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 2
   %12 = load i64, i64* %11, align 8
   %13 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 3
; CHECK-NEXT:    retq
   %42 = or i1 %40, %41
   %43 = zext i1 %42 to i32
   ret i32 %43
 }
 
 define i32 @add_U320_without_i128_xor(%struct.U320* nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) {
 ; CHECK-LABEL: add_U320_without_i128_xor:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    pushq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    .cfi_offset %rbx, -16
-; CHECK-NEXT:    addq 8(%rdi), %rdx
-; CHECK-NEXT:    setb %r10b
 ; CHECK-NEXT:    addq %rsi, (%rdi)
-; CHECK-NEXT:    adcq $0, %rdx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addq 16(%rdi), %rcx
-; CHECK-NEXT:    setb %r11b
-; CHECK-NEXT:    xorb %r10b, %al
-; CHECK-NEXT:    movzbl %al, %ebx
-; CHECK-NEXT:    addq %rcx, %rbx
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    addq 24(%rdi), %r8
-; CHECK-NEXT:    setb %r10b
-; CHECK-NEXT:    xorb %r11b, %cl
-; CHECK-NEXT:    movzbl %cl, %esi
-; CHECK-NEXT:    addq %r8, %rsi
+; CHECK-NEXT:    adcq %rdx, 8(%rdi)
+; CHECK-NEXT:    adcq %rcx, 16(%rdi)
+; CHECK-NEXT:    adcq %r8, 24(%rdi)
+; CHECK-NEXT:    adcq %r9, 32(%rdi)
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addq 32(%rdi), %r9
-; CHECK-NEXT:    setb %r8b
-; CHECK-NEXT:    xorb %r10b, %al
 ; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    addq %r9, %rax
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    movq %rdx, 8(%rdi)
-; CHECK-NEXT:    movq %rbx, 16(%rdi)
-; CHECK-NEXT:    movq %rsi, 24(%rdi)
-; CHECK-NEXT:    movq %rax, 32(%rdi)
-; CHECK-NEXT:    xorb %r8b, %cl
-; CHECK-NEXT:    movzbl %cl, %eax
-; CHECK-NEXT:    popq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 8
 ; CHECK-NEXT:    retq
   %7 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 0
   %8 = load i64, i64* %7, align 8
   %9 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 1
   %10 = load i64, i64* %9, align 8
   %11 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 2
   %12 = load i64, i64* %11, align 8
   %13 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 3
; CHECK-NEXT:    retq
   store i64 %39, i64* %15, align 8
   %40 = icmp ult i64 %34, %16
   %41 = icmp ult i64 %39, %34
   %42 = xor i1 %40, %41
   %43 = zext i1 %42 to i32
   ret i32 %43
 }
 
+; Either the primary addition can overflow or the addition of the carry, but
+; they cannot both overflow.
+define i32 @bogus_add_U320_without_i128_and(%struct.U320* nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) {
+; CHECK-LABEL: bogus_add_U320_without_i128_and:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    addq %rsi, (%rdi)
+; CHECK-NEXT:    adcq %rdx, 8(%rdi)
+; CHECK-NEXT:    addq %rcx, 16(%rdi)
+; CHECK-NEXT:    addq %r8, 24(%rdi)
+; CHECK-NEXT:    addq %r9, 32(%rdi)
+; CHECK-NEXT:    xorl %eax, %eax
+; CHECK-NEXT:    retq
+  %7 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 0
+  %8 = load i64, i64* %7, align 8
+  %9 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 1
+  %10 = load i64, i64* %9, align 8
+  %11 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 2
+  %12 = load i64, i64* %11, align 8
+  %13 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 3
+  %14 = load i64, i64* %13, align 8
+  %15 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 4
+  %16 = load i64, i64* %15, align 8
+  %17 = add i64 %8, %1
+  %18 = add i64 %10, %2
+  %19 = icmp ult i64 %17, %1
+  %20 = zext i1 %19 to i64
+  %21 = add i64 %18, %20
+  %22 = add i64 %12, %3
+  %23 = icmp ult i64 %18, %10
+  %24 = icmp ult i64 %21, %18
+  %25 = and i1 %23, %24
+  %26 = zext i1 %25 to i64
+  %27 = add i64 %22, %26
+  %28 = add i64 %14, %4
+  %29 = icmp ult i64 %22, %12
+  %30 = icmp ult i64 %27, %22
+  %31 = and i1 %29, %30
+  %32 = zext i1 %31 to i64
+  %33 = add i64 %28, %32
+  %34 = add i64 %16, %5
+  %35 = icmp ult i64 %28, %14
+  %36 = icmp ult i64 %33, %28
+  %37 = and i1 %35, %36
+  %38 = zext i1 %37 to i64
+  %39 = add i64 %34, %38
+  store i64 %17, i64* %7, align 8
+  store i64 %21, i64* %9, align 8
+  store i64 %27, i64* %11, align 8
+  store i64 %33, i64* %13, align 8
+  store i64 %39, i64* %15, align 8
+  %40 = icmp ult i64 %34, %16
+  %41 = icmp ult i64 %39, %34
+  %42 = and i1 %40, %41
+  %43 = zext i1 %42 to i32
+  ret i32 %43
+}
+
 define void @add_U320_without_i128_or_no_ret(%struct.U320* nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) {
 ; CHECK-LABEL: add_U320_without_i128_or_no_ret:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    addq 8(%rdi), %rdx
-; CHECK-NEXT:    setb %r10b
 ; CHECK-NEXT:    addq %rsi, (%rdi)
-; CHECK-NEXT:    adcq $0, %rdx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addq 16(%rdi), %rcx
-; CHECK-NEXT:    setb %r11b
-; CHECK-NEXT:    orb %r10b, %al
-; CHECK-NEXT:    movzbl %al, %esi
-; CHECK-NEXT:    addq %rcx, %rsi
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    addq 24(%rdi), %r8
-; CHECK-NEXT:    setb %r10b
-; CHECK-NEXT:    orb %r11b, %cl
-; CHECK-NEXT:    movzbl %cl, %ecx
-; CHECK-NEXT:    addq %r8, %rcx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addq 32(%rdi), %r9
-; CHECK-NEXT:    orb %r10b, %al
-; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    addq %r9, %rax
-; CHECK-NEXT:    movq %rdx, 8(%rdi)
-; CHECK-NEXT:    movq %rsi, 16(%rdi)
-; CHECK-NEXT:    movq %rcx, 24(%rdi)
-; CHECK-NEXT:    movq %rax, 32(%rdi)
+; CHECK-NEXT:    adcq %rdx, 8(%rdi)
+; CHECK-NEXT:    adcq %rcx, 16(%rdi)
+; CHECK-NEXT:    adcq %r8, 24(%rdi)
+; CHECK-NEXT:    adcq %r9, 32(%rdi)
 ; CHECK-NEXT:    retq
   %7 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 0
   %8 = load i64, i64* %7, align 8
   %9 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 1
   %10 = load i64, i64* %9, align 8
   %11 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 2
   %12 = load i64, i64* %11, align 8
   %13 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 3
; CHECK-NEXT:    retq
   store i64 %33, i64* %13, align 8
   store i64 %39, i64* %15, align 8
   ret void
 }
 
 define i32 @add_U320_uaddo(%struct.U320* nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) {
 ; CHECK-LABEL: add_U320_uaddo:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    addq 8(%rdi), %rdx
-; CHECK-NEXT:    setb %r10b
 ; CHECK-NEXT:    addq %rsi, (%rdi)
-; CHECK-NEXT:    adcq $0, %rdx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %r10b, %al
-; CHECK-NEXT:    movzbl %al, %esi
-; CHECK-NEXT:    addq 16(%rdi), %rcx
-; CHECK-NEXT:    setb %r10b
-; CHECK-NEXT:    addq %rsi, %rcx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %r10b, %al
-; CHECK-NEXT:    movzbl %al, %esi
-; CHECK-NEXT:    addq 24(%rdi), %r8
-; CHECK-NEXT:    setb %r10b
-; CHECK-NEXT:    addq %rsi, %r8
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %r10b, %al
-; CHECK-NEXT:    movzbl %al, %esi
-; CHECK-NEXT:    addq 32(%rdi), %r9
-; CHECK-NEXT:    setb %r10b
-; CHECK-NEXT:    addq %rsi, %r9
+; CHECK-NEXT:    adcq %rdx, 8(%rdi)
+; CHECK-NEXT:    adcq %rcx, 16(%rdi)
+; CHECK-NEXT:    adcq %r8, 24(%rdi)
+; CHECK-NEXT:    adcq %r9, 32(%rdi)
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %r10b, %al
-; CHECK-NEXT:    movq %rdx, 8(%rdi)
-; CHECK-NEXT:    movq %rcx, 16(%rdi)
-; CHECK-NEXT:    movq %r8, 24(%rdi)
-; CHECK-NEXT:    movq %r9, 32(%rdi)
 ; CHECK-NEXT:    movzbl %al, %eax
 ; CHECK-NEXT:    retq
   %7 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 0
   %8 = load i64, i64* %7, align 8
   %9 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 1
   %10 = load i64, i64* %9, align 8
   %11 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 2
   %12 = load i64, i64* %11, align 8

 
 %struct.U192 = type { [3 x i64] }
 
 define void @PR39464(%struct.U192* noalias nocapture sret %0, %struct.U192* nocapture readonly dereferenceable(24) %1, %struct.U192* nocapture readonly dereferenceable(24) %2) {
 ; CHECK-LABEL: PR39464:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    movq (%rsi), %rcx
-; CHECK-NEXT:    movq (%rdx), %r8
-; CHECK-NEXT:    leaq (%rcx,%r8), %rdi
-; CHECK-NEXT:    movq %rdi, (%rax)
-; CHECK-NEXT:    movq 8(%rsi), %rdi
-; CHECK-NEXT:    addq 8(%rdx), %rdi
-; CHECK-NEXT:    setb %r9b
-; CHECK-NEXT:    addq %r8, %rcx
-; CHECK-NEXT:    adcq $0, %rdi
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %r9b, %cl
-; CHECK-NEXT:    movzbl %cl, %ecx
-; CHECK-NEXT:    movq %rdi, 8(%rax)
-; CHECK-NEXT:    movq 16(%rsi), %rsi
-; CHECK-NEXT:    addq 16(%rdx), %rsi
-; CHECK-NEXT:    addq %rcx, %rsi
-; CHECK-NEXT:    movq %rsi, 16(%rax)
+; CHECK-NEXT:    addq (%rdx), %rcx
+; CHECK-NEXT:    movq %rcx, (%rdi)
+; CHECK-NEXT:    movq 8(%rsi), %rcx
+; CHECK-NEXT:    adcq 8(%rdx), %rcx
+; CHECK-NEXT:    movq %rcx, 8(%rdi)
+; CHECK-NEXT:    movq 16(%rsi), %rcx
+; CHECK-NEXT:    adcq 16(%rdx), %rcx
+; CHECK-NEXT:    movq %rcx, 16(%rdi)
 ; CHECK-NEXT:    retq
   %4 = getelementptr inbounds %struct.U192, %struct.U192* %1, i64 0, i32 0, i64 0
   %5 = load i64, i64* %4, align 8
   %6 = getelementptr inbounds %struct.U192, %struct.U192* %2, i64 0, i32 0, i64 0
   %7 = load i64, i64* %6, align 8
   %8 = tail call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 %5, i64 %7)
   %9 = extractvalue { i64, i1 } %8, 1
   %10 = extractvalue { i64, i1 } %8, 0

 }
 
 
 %uint128 = type { i64, i64 }
 
 define zeroext i1 @uaddo_U128_without_i128_or(i64 %0, i64 %1, i64 %2, i64 %3, %uint128* nocapture %4) nounwind {
 ; CHECK-LABEL: uaddo_U128_without_i128_or:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    addq %rcx, %rsi
-; CHECK-NEXT:    setb %cl
 ; CHECK-NEXT:    addq %rdx, %rdi
-; CHECK-NEXT:    adcq $0, %rsi
+; CHECK-NEXT:    adcq %rcx, %rsi
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %cl, %al
 ; CHECK-NEXT:    movq %rsi, (%r8)
 ; CHECK-NEXT:    movq %rdi, 8(%r8)
 ; CHECK-NEXT:    retq
   %6 = add i64 %2, %0
   %7 = icmp ult i64 %6, %0
   %8 = add i64 %3, %1
   %9 = icmp ult i64 %8, %1
   %10 = zext i1 %7 to i64

 
 
 %uint192 = type { i64, i64, i64 }
 
 define void @add_U192_without_i128_or(%uint192* sret %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5, i64 %6) nounwind {
 ; CHECK-LABEL: add_U192_without_i128_or:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    addq %r9, %rdx
-; CHECK-NEXT:    setb %dil
 ; CHECK-NEXT:    addq %r8, %rsi
-; CHECK-NEXT:    adcq $0, %rdx
-; CHECK-NEXT:    setb %r8b
-; CHECK-NEXT:    orb %dil, %r8b
-; CHECK-NEXT:    addq {{[0-9]+}}(%rsp), %rcx
-; CHECK-NEXT:    movzbl %r8b, %edi
-; CHECK-NEXT:    addq %rcx, %rdi
-; CHECK-NEXT:    movq %rdi, (%rax)
-; CHECK-NEXT:    movq %rdx, 8(%rax)
-; CHECK-NEXT:    movq %rsi, 16(%rax)
+; CHECK-NEXT:    adcq %r9, %rdx
+; CHECK-NEXT:    adcq {{[0-9]+}}(%rsp), %rcx
+; CHECK-NEXT:    movq %rcx, (%rdi)
+; CHECK-NEXT:    movq %rdx, 8(%rdi)
+; CHECK-NEXT:    movq %rsi, 16(%rdi)
 ; CHECK-NEXT:    retq
   %8 = add i64 %4, %1
   %9 = icmp ult i64 %8, %1
   %10 = add i64 %5, %2
   %11 = icmp ult i64 %10, %2
   %12 = zext i1 %9 to i64
   %13 = add i64 %10, %12
   %14 = icmp ult i64 %13, %10

 %uint256 = type { %uint128, %uint128 }
 
 ; Classic unrolled 256-bit addition implementation using i64 as the word type.
 ; It starts by adding least significant words and propagates carry to additions of the higher words.
 define void @add_U256_without_i128_or_by_i64_words(%uint256* sret %0, %uint256* %1, %uint256* %2) nounwind {
 ; CHECK-LABEL: add_U256_without_i128_or_by_i64_words:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    movq (%rdx), %r9
-; CHECK-NEXT:    movq 8(%rdx), %r10
-; CHECK-NEXT:    addq 8(%rsi), %r10
-; CHECK-NEXT:    setb %r8b
-; CHECK-NEXT:    addq (%rsi), %r9
-; CHECK-NEXT:    adcq $0, %r10
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %r8b, %cl
-; CHECK-NEXT:    movq 16(%rdx), %rdi
-; CHECK-NEXT:    addq 16(%rsi), %rdi
-; CHECK-NEXT:    setb %r8b
-; CHECK-NEXT:    movzbl %cl, %r11d
-; CHECK-NEXT:    addq %rdi, %r11
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %r8b, %cl
+; CHECK-NEXT:    movq (%rdx), %r8
+; CHECK-NEXT:    movq 8(%rdx), %rdi
+; CHECK-NEXT:    addq (%rsi), %r8
+; CHECK-NEXT:    adcq 8(%rsi), %rdi
+; CHECK-NEXT:    movq 16(%rdx), %rcx
+; CHECK-NEXT:    adcq 16(%rsi), %rcx
 ; CHECK-NEXT:    movq 24(%rdx), %rdx
-; CHECK-NEXT:    addq 24(%rsi), %rdx
-; CHECK-NEXT:    movzbl %cl, %ecx
-; CHECK-NEXT:    addq %rdx, %rcx
-; CHECK-NEXT:    movq %rcx, (%rax)
-; CHECK-NEXT:    movq %r11, 8(%rax)
-; CHECK-NEXT:    movq %r10, 16(%rax)
-; CHECK-NEXT:    movq %r9, 24(%rax)
+; CHECK-NEXT:    adcq 24(%rsi), %rdx
+; CHECK-NEXT:    movq %rdx, (%rax)
+; CHECK-NEXT:    movq %rcx, 8(%rax)
+; CHECK-NEXT:    movq %rdi, 16(%rax)
+; CHECK-NEXT:    movq %r8, 24(%rax)
 ; CHECK-NEXT:    retq
   %4 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 0
   %5 = load i64, i64* %4, align 8
   %6 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 0
   %7 = load i64, i64* %6, align 8
   %8 = add i64 %7, %5
   %9 = icmp ult i64 %8, %5
   %10 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 1

 }
 
 ; The 256-bit addition implementation using two inlined uaddo procedures for U128 type { i64, i64 }.
 ; This is similar to how LLVM legalize types in CodeGen.
 define void @add_U256_without_i128_or_recursive(%uint256* sret %0, %uint256* %1, %uint256* %2) nounwind {
 ; CHECK-LABEL: add_U256_without_i128_or_recursive:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    movq (%rdx), %r9
+; CHECK-NEXT:    movq (%rdx), %r8
 ; CHECK-NEXT:    movq 8(%rdx), %rdi
-; CHECK-NEXT:    addq 8(%rsi), %rdi
-; CHECK-NEXT:    setb %r8b
-; CHECK-NEXT:    addq (%rsi), %r9
-; CHECK-NEXT:    adcq $0, %rdi
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %r8b, %cl
-; CHECK-NEXT:    movq 16(%rdx), %r8
-; CHECK-NEXT:    movq 24(%rdx), %r10
-; CHECK-NEXT:    xorl %edx, %edx
-; CHECK-NEXT:    addq 16(%rsi), %r8
-; CHECK-NEXT:    setb %dl
-; CHECK-NEXT:    addq 24(%rsi), %r10
-; CHECK-NEXT:    movzbl %cl, %ecx
-; CHECK-NEXT:    addq %r8, %rcx
-; CHECK-NEXT:    adcq %r10, %rdx
-; CHECK-NEXT:    movq %r9, (%rax)
+; CHECK-NEXT:    addq (%rsi), %r8
+; CHECK-NEXT:    adcq 8(%rsi), %rdi
+; CHECK-NEXT:    movq 16(%rdx), %rcx
+; CHECK-NEXT:    movq 24(%rdx), %rdx
+; CHECK-NEXT:    adcq 16(%rsi), %rcx
+; CHECK-NEXT:    adcq 24(%rsi), %rdx
+; CHECK-NEXT:    movq %r8, (%rax)
 ; CHECK-NEXT:    movq %rdi, 8(%rax)
 ; CHECK-NEXT:    movq %rcx, 16(%rax)
 ; CHECK-NEXT:    movq %rdx, 24(%rax)
 ; CHECK-NEXT:    retq
   %4 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 0
   %5 = load i64, i64* %4, align 8
   %6 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 1
   %7 = load i64, i64* %6, align 8

test/CodeGen/X86/subcarry.ll

; CHECK-NEXT:    retq
   ret i64 %res
 }
 
 %struct.U320 = type { [5 x i64] }
 
 define i32 @sub_U320_without_i128_or(%struct.U320* nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) {
 ; CHECK-LABEL: sub_U320_without_i128_or:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    pushq %r14
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    pushq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 24
-; CHECK-NEXT:    .cfi_offset %rbx, -24
-; CHECK-NEXT:    .cfi_offset %r14, -16
-; CHECK-NEXT:    movq 8(%rdi), %r14
-; CHECK-NEXT:    movq 16(%rdi), %r10
-; CHECK-NEXT:    movq 24(%rdi), %r11
-; CHECK-NEXT:    movq 32(%rdi), %rbx
-; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    subq %rsi, (%rdi)
+; CHECK-NEXT:    sbbq %rdx, 8(%rdi)
+; CHECK-NEXT:    sbbq %rcx, 16(%rdi)
+; CHECK-NEXT:    sbbq %r8, 24(%rdi)
+; CHECK-NEXT:    sbbq %r9, 32(%rdi)
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    subq %rdx, %r14
-; CHECK-NEXT:    setb %dl
-; CHECK-NEXT:    subq %rax, %r14
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    subq %rcx, %r10
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %dl, %al
-; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    subq %rax, %r10
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    subq %r8, %r11
-; CHECK-NEXT:    setb %dl
-; CHECK-NEXT:    orb %cl, %al
-; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    subq %rax, %r11
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    subq %r9, %rbx
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %dl, %al
-; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    subq %rax, %rbx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    movq %r14, 8(%rdi)
-; CHECK-NEXT:    movq %r10, 16(%rdi)
-; CHECK-NEXT:    movq %r11, 24(%rdi)
-; CHECK-NEXT:    movq %rbx, 32(%rdi)
-; CHECK-NEXT:    orb %cl, %al
 ; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    popq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    popq %r14
-; CHECK-NEXT:    .cfi_def_cfa_offset 8
 ; CHECK-NEXT:    retq
   %7 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 0
   %8 = load i64, i64* %7, align 8
   %9 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 1
   %10 = load i64, i64* %9, align 8
   %11 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 2
   %12 = load i64, i64* %11, align 8
   %13 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 3
; CHECK-NEXT:    retq
   %42 = or i1 %40, %41
   %43 = zext i1 %42 to i32
   ret i32 %43
 }
 
 define i32 @sub_U320_usubo(%struct.U320* nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) {
 ; CHECK-LABEL: sub_U320_usubo:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    pushq %r14
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    pushq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 24
-; CHECK-NEXT:    .cfi_offset %rbx, -24
-; CHECK-NEXT:    .cfi_offset %r14, -16
-; CHECK-NEXT:    movq 8(%rdi), %r14
-; CHECK-NEXT:    movq 16(%rdi), %r10
-; CHECK-NEXT:    movq 24(%rdi), %r11
-; CHECK-NEXT:    movq 32(%rdi), %rbx
-; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    subq %rsi, (%rdi)
+; CHECK-NEXT:    sbbq %rdx, 8(%rdi)
+; CHECK-NEXT:    sbbq %rcx, 16(%rdi)
+; CHECK-NEXT:    sbbq %r8, 24(%rdi)
+; CHECK-NEXT:    sbbq %r9, 32(%rdi)
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    subq %rdx, %r14
-; CHECK-NEXT:    setb %dl
-; CHECK-NEXT:    subq %rax, %r14
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %dl, %al
 ; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    subq %rcx, %r10
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    subq %rax, %r10
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %cl, %al
-; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    subq %r8, %r11
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    subq %rax, %r11
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %cl, %al
-; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    subq %r9, %rbx
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    subq %rax, %rbx
-; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    orb %cl, %al
-; CHECK-NEXT:    movq %r14, 8(%rdi)
-; CHECK-NEXT:    movq %r10, 16(%rdi)
-; CHECK-NEXT:    movq %r11, 24(%rdi)
-; CHECK-NEXT:    movq %rbx, 32(%rdi)
-; CHECK-NEXT:    movzbl %al, %eax
-; CHECK-NEXT:    popq %rbx
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    popq %r14
-; CHECK-NEXT:    .cfi_def_cfa_offset 8
 ; CHECK-NEXT:    retq
   %7 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 0
   %8 = load i64, i64* %7, align 8
   %9 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 1
   %10 = load i64, i64* %9, align 8
   %11 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 2
   %12 = load i64, i64* %11, align 8
   %13 = getelementptr inbounds %struct.U320, %struct.U320* %0, i64 0, i32 0, i64 3

 
 %struct.U192 = type { [3 x i64] }
 
 define void @PR39464(%struct.U192* noalias nocapture sret %0, %struct.U192* nocapture readonly dereferenceable(24) %1, %struct.U192* nocapture readonly dereferenceable(24) %2) {
 ; CHECK-LABEL: PR39464:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
 ; CHECK-NEXT:    movq (%rsi), %rcx
-; CHECK-NEXT:    xorl %r9d, %r9d
 ; CHECK-NEXT:    subq (%rdx), %rcx
-; CHECK-NEXT:    setb %r9b
 ; CHECK-NEXT:    movq %rcx, (%rdi)
-; CHECK-NEXT:    movq 8(%rsi), %rdi
-; CHECK-NEXT:    subq 8(%rdx), %rdi
-; CHECK-NEXT:    setb %r8b
-; CHECK-NEXT:    subq %r9, %rdi
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %r8b, %cl
-; CHECK-NEXT:    movzbl %cl, %ecx
-; CHECK-NEXT:    movq %rdi, 8(%rax)
-; CHECK-NEXT:    movq 16(%rsi), %rsi
-; CHECK-NEXT:    subq 16(%rdx), %rsi
-; CHECK-NEXT:    subq %rcx, %rsi
-; CHECK-NEXT:    movq %rsi, 16(%rax)
+; CHECK-NEXT:    movq 8(%rsi), %rcx
+; CHECK-NEXT:    sbbq 8(%rdx), %rcx
+; CHECK-NEXT:    movq %rcx, 8(%rdi)
+; CHECK-NEXT:    movq 16(%rsi), %rcx
+; CHECK-NEXT:    sbbq 16(%rdx), %rcx
+; CHECK-NEXT:    movq %rcx, 16(%rdi)
 ; CHECK-NEXT:    retq
   %4 = getelementptr inbounds %struct.U192, %struct.U192* %1, i64 0, i32 0, i64 0
   %5 = load i64, i64* %4, align 8
   %6 = getelementptr inbounds %struct.U192, %struct.U192* %2, i64 0, i32 0, i64 0
   %7 = load i64, i64* %6, align 8
   %8 = tail call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %5, i64 %7)
   %9 = extractvalue { i64, i1 } %8, 1
   %10 = extractvalue { i64, i1 } %8, 0

 %uint256 = type { %uint128, %uint128 }
 
 ; The 256-bit subtraction implementation using two inlined usubo procedures for U128 type { i64, i64 }.
 ; This is similar to how LLVM legalize types in CodeGen.
 define void @sub_U256_without_i128_or_recursive(%uint256* sret %0, %uint256* %1, %uint256* %2) nounwind {
 ; CHECK-LABEL: sub_U256_without_i128_or_recursive:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rdi, %rax
-; CHECK-NEXT:    movq (%rsi), %r8
+; CHECK-NEXT:    movq (%rsi), %r9
 ; CHECK-NEXT:    movq 8(%rsi), %r10
-; CHECK-NEXT:    xorl %ecx, %ecx
-; CHECK-NEXT:    subq (%rdx), %r8
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    subq 8(%rdx), %r10
-; CHECK-NEXT:    setb %r9b
-; CHECK-NEXT:    subq %rcx, %r10
-; CHECK-NEXT:    setb %cl
-; CHECK-NEXT:    orb %r9b, %cl
-; CHECK-NEXT:    movq 16(%rsi), %rdi
+; CHECK-NEXT:    subq (%rdx), %r9
+; CHECK-NEXT:    sbbq 8(%rdx), %r10
+; CHECK-NEXT:    setb %r8b
+; CHECK-NEXT:    movq 16(%rsi), %rcx
 ; CHECK-NEXT:    movq 24(%rsi), %rsi
-; CHECK-NEXT:    xorl %r9d, %r9d
-; CHECK-NEXT:    subq 16(%rdx), %rdi
-; CHECK-NEXT:    setb %r9b
+; CHECK-NEXT:    xorl %edi, %edi
+; CHECK-NEXT:    subq 16(%rdx), %rcx
+; CHECK-NEXT:    setb %dil
 ; CHECK-NEXT:    subq 24(%rdx), %rsi
-; CHECK-NEXT:    movzbl %cl, %ecx
-; CHECK-NEXT:    subq %rcx, %rdi
-; CHECK-NEXT:    sbbq %r9, %rsi
-; CHECK-NEXT:    movq %r8, (%rax)
+; CHECK-NEXT:    movzbl %r8b, %edx
+; CHECK-NEXT:    subq %rdx, %rcx
+; CHECK-NEXT:    sbbq %rdi, %rsi
+; CHECK-NEXT:    movq %r9, (%rax)
 ; CHECK-NEXT:    movq %r10, 8(%rax)
-; CHECK-NEXT:    movq %rdi, 16(%rax)
+; CHECK-NEXT:    movq %rcx, 16(%rax)
 ; CHECK-NEXT:    movq %rsi, 24(%rax)
 ; CHECK-NEXT:    retq
   %4 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 0
   %5 = load i64, i64* %4, align 8
   %6 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 1
   %7 = load i64, i64* %6, align 8
   %8 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 0
   %9 = load i64, i64* %8, align 8