[InstCombine] Combine lshr of add -> (a + b < a)

[Pierre-vh]

Summary

Tries to perform

(lshr (add (zext X), (zext Y)), K)
->  (icmp ult (add X, Y), X)
where
  - The add's operands are zexts from a K-bits integer to a bigger type.
  - The add is only used by the shr, or by iK (or narrower) truncates.
  - The lshr type has more than 2 bits (other types are boolean math).
  - K > 1

This seems to be a pattern that just comes from OpenCL front-ends, so adding DAG/GISel combines doesn't seem to be worth the complexity.

Original patch D107552 by @abinavpp - adapted to use (a + b < a) instead of uaddo following discussion on the review.
See this issue https://github.com/RadeonOpenCompute/ROCm/issues/488

[spatel]

Coincidence I think - I just filed a bug for this pattern:
https://github.com/llvm/llvm-project/issues/59232

What do you think about producing the sequence with 'not' + 'icmp' instead of the uadd + extract?

[foad]

What do you think about producing the sequence with 'not' + 'icmp' instead of the uadd + extract?

The point about using uadd.with.overflow is that it also gives you the truncated 32 bit result of the add.

[spatel]

In D138814#3953729, @foad wrote:

What do you think about producing the sequence with 'not' + 'icmp' instead of the uadd + extract?

The point about using uadd.with.overflow is that it also gives you the truncated 32 bit result of the add.

If we're not using that value (as shown in the first two tests), then do we still we want to canonicalize to an overflow intrinsic? That implies that we also need to transform the "not+icmp" pattern into "uadd+extract" to be consistent.

[foad]

In D138814#3953742, @spatel wrote:

In D138814#3953729, @foad wrote:

What do you think about producing the sequence with 'not' + 'icmp' instead of the uadd + extract?

The point about using uadd.with.overflow is that it also gives you the truncated 32 bit result of the add.

If we're not using that value (as shown in the first two tests), then do we still we want to canonicalize to an overflow intrinsic? That implies that we also need to transform the "not+icmp" pattern into "uadd+extract" to be consistent.

Oh, I see. In that case I guess the "not" form is reasonable. Hopefully value range tracking understands it.

[spatel]

In D138814#3953839, @foad wrote:

In D138814#3953742, @spatel wrote:

In D138814#3953729, @foad wrote:

What do you think about producing the sequence with 'not' + 'icmp' instead of the uadd + extract?

The point about using uadd.with.overflow is that it also gives you the truncated 32 bit result of the add.

If we're not using that value (as shown in the first two tests), then do we still we want to canonicalize to an overflow intrinsic? That implies that we also need to transform the "not+icmp" pattern into "uadd+extract" to be consistent.

Oh, I see. In that case I guess the "not" form is reasonable. Hopefully value range tracking understands it.

Right - I don't know which form is going to get us to the ideal final output (might be different for different patterns).
In the earlier version(s) of this patch (is there a functional diff here from D107552?), there were questions about how it would interact with SCEV and/or vectorization.

If we're focusing on the overflow-only/minimal pattern, then I think we should structure the matching as a known-bits/demanded-bits problem. Ie, instead of zexts, we might have and masks. Instead of a shift at the end, that might also be a mask op.

[chfast]

In D138814#3953742, @spatel wrote:

In D138814#3953729, @foad wrote:

What do you think about producing the sequence with 'not' + 'icmp' instead of the uadd + extract?

The point about using uadd.with.overflow is that it also gives you the truncated 32 bit result of the add.

If we're not using that value (as shown in the first two tests), then do we still we want to canonicalize to an overflow intrinsic? That implies that we also need to transform the "not+icmp" pattern into "uadd+extract" to be consistent.

Well, some time ago we added a change that changes usubo without math usage into icmp https://reviews.llvm.org/rG926e7312b2f20f2f7b0a3d5ddbd29da5625507f3. Here this is not so simple as you need two instructions but I wander what direction do we want to go. Previously there were concerns about forming intrinsic before CodeGenPrepare.

[Pierre-vh]

Use known bits instead of zext

[foad]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

916

This is incorrect in the i2/i1 case: https://alive2.llvm.org/ce/z/ga8CDx

Using sext if the original shift was ashr will fix it.

[Pierre-vh]

Support i2/i1 case with SExt

[lebedev.ri]

Nice! This is the proper place for it.
I'm not sure i understand why you can't just zext the overflow bit
and RAUW all the original users with that?

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

864

Is it not sufficient to just check that the width is 2x the shift amount?
Do we need the power-of-two check?

880–891

This is rather unusual in InstCombine.
Would it not be sufficient to just zext the result?

917–918

mul i16 255, 2 is i16 510, which is non-negative,
so the signbit of the original result is never set.
IOW, just zero-extend.

[foad]

Looks OK to me techincally but I will leave it to an InstCombine maintainer to approve.

I don't think there is any requirement for the wider type to be exactly double the narrower type.

[Pierre-vh]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

864

I don't think the power of 2 check is really needed - I inherited it from the original patch. I will remove it

880–891

I think the original intent was to only to do the transform when it appears beneficial, but if we're fine with doing it all the time as a canonical form then we can indeed just zext + RAUW. What do you think?

917–918

Is it normal that Alive2 reports the transformation as incorrect for i2 then (see @foad's comment above) ?
Maybe we just need to SExt if it's i2 + ashr?

[Pierre-vh]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

880–891

Now that I think about it again, I don't think the transform would be valid if we don't look for the truncs?
We would be replacing the .add - which may have <32 leading zeroes (if overflow), with a zext of the uaddo, which will always have 32 leading zeroes or more

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

880–891

Ah yes, you look at truncs of the wide add.
It wouldn't be illegal to just leave it be.

I think what you want here, is:

if(!Op0.hasOneUse()) {
  for (User *Usr : Op0->users()) {
    if (Usr == &I)
      continue;

    TruncInst *Trunc = dyn_cast<TruncInst>(Usr);
    if (!Trunc || Trunc->getType()->getScalarSizeInBits() > HalfWidth)
      return nullptr;
  }
}

and then just

if(!Op0.hasOneUse()) {
   Value*WideOV = Builder.CreateZExt(Overflow);
   replaceInstUsesWith(Op0, WideOV);
}

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

917–918

Ok, good point, please add that as a comment.

[Pierre-vh]

Comments

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

880–891

Indeed that works too, but I think you meant CreateZExt(UAdd) instead of the Overflow bit?

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

911–912

Right, not an overflow bit. Probably adjust the name too.

[Pierre-vh]

Comment

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

853

I think it would be nicer to hoist the match and rename the variable.

Value *Add = I.getOperand(0);
Value *X = nullptr, *Y = nullptr;
if (!match(Add, m_Add(m_Value(X), m_Value(Y))))
  return nullptr;

[spatel]

In D138814#3959942, @foad wrote:

I don't think there is any requirement for the wider type to be exactly double the narrower type.

That's correct:
https://alive2.llvm.org/ce/z/iLVIgn

So this patch/tests are too narrow as-is. It should be checking something like "if we only demand the top N bits of an add, and the add operands are known zero in those top N bits, then fold the add into an overflow check."

Also, canonicalizing to the add intrinsic if we're not using the add part of the result seems like the wrong direction. I can't tell from the larger test what we're expecting to happen. Please pre-commit the baseline tests, so we can see the diffs.

[Pierre-vh]

In D138814#3960221, @spatel wrote:

In D138814#3959942, @foad wrote:

I don't think there is any requirement for the wider type to be exactly double the narrower type.

That's correct:
https://alive2.llvm.org/ce/z/iLVIgn

So this patch/tests are too narrow as-is. It should be checking something like "if we only demand the top N bits of an add, and the add operands are known zero in those top N bits, then fold the add into an overflow check."

Also, canonicalizing to the add intrinsic if we're not using the add part of the result seems like the wrong direction. I can't tell from the larger test what we're expecting to happen. Please pre-commit the baseline tests, so we can see the diffs.

Will update the combine & add a base test diff.

Do you mean we shouldn't do the combine if the Add has only one use?

[Pierre-vh]

Rebase on D139011

[Pierre-vh]

Since I relaxed the rules on the combine, another test changed.
Not sure if the new conditions are correct, what do you think?

[spatel]

In D138814#3960260, @Pierre-vh wrote:

In D138814#3960221, @spatel wrote:

In D138814#3959942, @foad wrote:

I don't think there is any requirement for the wider type to be exactly double the narrower type.

That's correct:
https://alive2.llvm.org/ce/z/iLVIgn

So this patch/tests are too narrow as-is. It should be checking something like "if we only demand the top N bits of an add, and the add operands are known zero in those top N bits, then fold the add into an overflow check."

Also, canonicalizing to the add intrinsic if we're not using the add part of the result seems like the wrong direction. I can't tell from the larger test what we're expecting to happen. Please pre-commit the baseline tests, so we can see the diffs.

Will update the combine & add a base test diff.

Do you mean we shouldn't do the combine if the Add has only one use?

I think it's the inverse - if the add has only one use, then fold to "not+icmp+zext":
https://github.com/llvm/llvm-project/issues/59232

If the add has >1 use, then I'm not sure what we want to happen. In the general form, we have something like this:
https://alive2.llvm.org/ce/z/sW5BME
...so what other pieces of the pattern need to be there to justify creating the add intrinsic? We're in target-independent InstCombine here, so we don't usually want to end up with more instructions than we started with.

[Pierre-vh]

In D138814#3960318, @spatel wrote:

In D138814#3960260, @Pierre-vh wrote:

In D138814#3960221, @spatel wrote:

In D138814#3959942, @foad wrote:

I don't think there is any requirement for the wider type to be exactly double the narrower type.

That's correct:
https://alive2.llvm.org/ce/z/iLVIgn

So this patch/tests are too narrow as-is. It should be checking something like "if we only demand the top N bits of an add, and the add operands are known zero in those top N bits, then fold the add into an overflow check."

Also, canonicalizing to the add intrinsic if we're not using the add part of the result seems like the wrong direction. I can't tell from the larger test what we're expecting to happen. Please pre-commit the baseline tests, so we can see the diffs.

Will update the combine & add a base test diff.

Do you mean we shouldn't do the combine if the Add has only one use?

I think it's the inverse - if the add has only one use, then fold to "not+icmp+zext":
https://github.com/llvm/llvm-project/issues/59232

If the add has >1 use, then I'm not sure what we want to happen. In the general form, we have something like this:
https://alive2.llvm.org/ce/z/sW5BME
...so what other pieces of the pattern need to be there to justify creating the add intrinsic? We're in target-independent InstCombine here, so we don't usually want to end up with more instructions than we started with.

I personally think we can create the add intrinsic if the add has more than one user, and the users are either the a/lshr or truncs (like we check now). I
In the end I'm not sure, to me it looks beneficial but I'll leave the final decision to people with more experience (cc @foad / @arsenm what do you think?)

[spatel]

There's a potentially missing/difficult optimization in the larger example. It boils down to this:
https://alive2.llvm.org/ce/z/qpCq-X

Ie, should we replace a value (the trunc) with a narrow math op that produces the identical value directly? That might be good because it removes a use of the wide add and increases parallelism, but it might be bad because it creates an independent math op that could impede analysis and be more expensive than a trunc in codegen. That's the problem shown in issue #59217 - with a mul, it's pretty clear that we don't want to create more math.

Given that there's no clear answer (and no way to invert the transform that I'm aware of), the direction of this patch is ok with me.

llvm/test/Transforms/InstCombine/shift-add.ll

437–439

This is an awkward way to check if 2 bools are set.
We're missing the reduction of boolean math to logic either way:
https://alive2.llvm.org/ce/z/4dBQhx

599

For anything but the i1/i2 case, we should convert the ashr to lshr (as happened here and the next test)?
So we could just bail out of the transform if the type doesn't have at least 3 bits (ignore the possibility of ashr).

[Pierre-vh]

Comments

llvm/test/Transforms/InstCombine/shift-add.ll

437–439

I removed support for types <3 bits; should I leave the test case in?

599

Ah I didn't know that, I'll simplify the combine to only check lshr then. Thanks!

[lebedev.ri]

Thanks.

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

847–848

880

Is there test coverage when the shift amt isn't the half of the original width?

902–905

alive2 proof please?

[Pierre-vh]

• Add new tests (rebased)
• Fix the combine to check for the EXACT amount of leading zeroes to ensure the transform is correct. Otherwise, if there's too little/too many leading zeroes it could mean that the shift was checking something other than the OV bit, I think.

[Pierre-vh]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

880

lshr_16_to_64_add_zext_basic?
I also added a couple of test cases where the shift amount is lower/higher than what's desired.

902–905

At this stage, the add is only used by either ShAmt-sized truncs, or the shift.
We're removing the shift, and for the truncs, they will cancel out.
https://alive2.llvm.org/ce/z/TWQp29

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

869–871

What we want to know here, is whether both X and Y can be NUW-truncated to ShAmt-wide types.
This is award because we are tiptoeing around adding new QoL helper functions.
We already have this: (ValueTracking.h/cpp)

/// Get the upper bound on bit size for this Value \p Op as a signed integer.
/// i.e.  x == sext(trunc(x to MaxSignificantBits) to bitwidth(x)).
/// Similar to the APInt::getSignificantBits function.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL,
                                   unsigned Depth = 0,
                                   AssumptionCache *AC = nullptr,
                                   const Instruction *CxtI = nullptr,
                                   const DominatorTree *DT = nullptr);

but that is for sign bits, while we want zero bits.
Can you just add an unsigned variant of it next to it, and use it here?

902–905

Right, i'm being slow. This is correct.

908

I think we should just emit it all next to the original add,
there isn't much point in sinking the final zext.

[Pierre-vh]

Comments

[nikic]

FWIW our historical stance has always been that uadd.with.overflow is non-canonical, and the canonical pattern is a + b < a (for non-constant b). uadd.with.overflow generally has worse optimization support, which is why we only form it during CGP for backend purposes.

[Pierre-vh]

In D138814#3973599, @nikic wrote:

FWIW our historical stance has always been that uadd.with.overflow is non-canonical, and the canonical pattern is a + b < a (for non-constant b). uadd.with.overflow generally has worse optimization support, which is why we only form it during CGP for backend purposes.

Interesting, not sure what other reviewers think?
Maybe adding a TII hook so targets can enable/disable the combine is a good idea? e.g. something like allowUAddoCanonicalForm?

[spatel]

In D138814#3980701, @Pierre-vh wrote:

In D138814#3973599, @nikic wrote:

FWIW our historical stance has always been that uadd.with.overflow is non-canonical, and the canonical pattern is a + b < a (for non-constant b). uadd.with.overflow generally has worse optimization support, which is why we only form it during CGP for backend purposes.

Interesting, not sure what other reviewers think?
Maybe adding a TII hook so targets can enable/disable the combine is a good idea? e.g. something like allowUAddoCanonicalForm?

We don't want TTI/TLI hooks in InstCombine because it's supposed to be early/target-independent transforms only (although it has folds gated by the data-layout that are almost the same thing as using TTI).

We decided that there is a legitimate need for target-dependent canonicalization though, so that's now possible in AggressiveInstCombine. So moving this patch to that pass and gating the transform on a target hook seems like a non-controversial way forward.

Currently, CodeGenPrepare uses this hook:
https://github.com/llvm/llvm-project/blob/1fe65d866c5285261b7766f2d3930ae975b878ff/llvm/include/llvm/CodeGen/TargetLowering.h#L3086

If we're using that as an early predicate, then I think it should be moved to TargetTransformInfo. I don't see any uses outside of CGP currently.

[arsenm]

In D138814#3981276, @spatel wrote:

In D138814#3980701, @Pierre-vh wrote:

In D138814#3973599, @nikic wrote:

FWIW our historical stance has always been that uadd.with.overflow is non-canonical, and the canonical pattern is a + b < a (for non-constant b). uadd.with.overflow generally has worse optimization support, which is why we only form it during CGP for backend purposes.

Interesting, not sure what other reviewers think?
Maybe adding a TII hook so targets can enable/disable the combine is a good idea? e.g. something like allowUAddoCanonicalForm?

We don't want TTI/TLI hooks in InstCombine because it's supposed to be early/target-independent transforms only (although it has folds gated by the data-layout that are almost the same thing as using TTI).

We decided that there is a legitimate need for target-dependent canonicalization though, so that's now possible in AggressiveInstCombine. So moving this patch to that pass and gating the transform on a target hook seems like a non-controversial way forward.

Currently, CodeGenPrepare uses this hook:
https://github.com/llvm/llvm-project/blob/1fe65d866c5285261b7766f2d3930ae975b878ff/llvm/include/llvm/CodeGen/TargetLowering.h#L3086

If we're using that as an early predicate, then I think it should be moved to TargetTransformInfo. I don't see any uses outside of CGP currently.

I'm more inclined to do this in CGP than AggressiveInstCombine if the shift is the preferred canonical form

[arsenm]

In D138814#3981278, @arsenm wrote:

In D138814#3981276, @spatel wrote:

In D138814#3980701, @Pierre-vh wrote:

In D138814#3973599, @nikic wrote:

FWIW our historical stance has always been that uadd.with.overflow is non-canonical, and the canonical pattern is a + b < a (for non-constant b). uadd.with.overflow generally has worse optimization support, which is why we only form it during CGP for backend purposes.

Interesting, not sure what other reviewers think?
Maybe adding a TII hook so targets can enable/disable the combine is a good idea? e.g. something like allowUAddoCanonicalForm?

We don't want TTI/TLI hooks in InstCombine because it's supposed to be early/target-independent transforms only (although it has folds gated by the data-layout that are almost the same thing as using TTI).

We decided that there is a legitimate need for target-dependent canonicalization though, so that's now possible in AggressiveInstCombine. So moving this patch to that pass and gating the transform on a target hook seems like a non-controversial way forward.

Currently, CodeGenPrepare uses this hook:
https://github.com/llvm/llvm-project/blob/1fe65d866c5285261b7766f2d3930ae975b878ff/llvm/include/llvm/CodeGen/TargetLowering.h#L3086

If we're using that as an early predicate, then I think it should be moved to TargetTransformInfo. I don't see any uses outside of CGP currently.

I'm more inclined to do this in CGP than AggressiveInstCombine if the shift is the preferred canonical form

Rather, if we can produce the add and compare as a more canonical form and match that in the backend, that would be better

[nikic]

In D138814#3980701, @Pierre-vh wrote:

In D138814#3973599, @nikic wrote:

FWIW our historical stance has always been that uadd.with.overflow is non-canonical, and the canonical pattern is a + b < a (for non-constant b). uadd.with.overflow generally has worse optimization support, which is why we only form it during CGP for backend purposes.

Interesting, not sure what other reviewers think?
Maybe adding a TII hook so targets can enable/disable the combine is a good idea? e.g. something like allowUAddoCanonicalForm?

I don't think there's any need for target dependence here. You just need to produce a + b < a instead of extract(uaddo(a, b), 1). The uaddo will be formed by the backend.

[spatel]

In D138814#3981279, @arsenm wrote:

Rather, if we can produce the add and compare as a more canonical form and match that in the backend, that would be better

Agreed - if we're just creating add+icmp rather than the intrinsic, then that seems fine to do here.

[Pierre-vh]

By a + b < a do you mean that the combine would:

• Still reduce the add to the smaller type
• Replace the overflow bit (lshr) with icmp lt (add a, b), a?

Does the backend already transform that to uaddo or will that need a separate patch in the target's CGP?

[arsenm]

In D138814#3981324, @Pierre-vh wrote:

By a + b < a do you mean that the combine would:

• Still reduce the add to the smaller type
• Replace the overflow bit (lshr) with icmp lt (add a, b), a?

Does the backend already transform that to uaddo or will that need a separate patch in the target's CGP?

Looks like no: https://godbolt.org/z/nTrzqxeo9

[nikic]

In D138814#3981336, @arsenm wrote:

In D138814#3981324, @Pierre-vh wrote:

By a + b < a do you mean that the combine would:

• Still reduce the add to the smaller type
• Replace the overflow bit (lshr) with icmp lt (add a, b), a?

Does the backend already transform that to uaddo or will that need a separate patch in the target's CGP?

Looks like no: https://godbolt.org/z/nTrzqxeo9

You are using slt rather than ult.

[Pierre-vh]

Change to (a + b < a); don't combine if ShAmt == 1.

Seems like CGP does the conversion to uaddo; or at least in AMDGPU's case codegen is the same for uaddo/(a + b < a): https://godbolt.org/z/zfnorbvzr

We seem to have more bitwise operations now, is it expected to see the add folded into other operations? (xor/and)
Should I restrict the combine to ShAmt > 2?

[Pierre-vh]

Rebase + ping

[nikic]

llvm/test/Transforms/InstCombine/pr34349.ll

17 ↗

(On Diff #486186)

This case doesn't look like a profitable transform. Do I understand correctly that the actual motivating case here is the case where the inputs are zext, and then this was later generalized based on reviewer feedback to use known bits instead?

For the zext case, this looks like an obviously desirable transform, but for the general case (where the truncs may not fold away) this is less clearly beneficial. I would personally restrict this to just zext unless we have specific motivation otherwise. (But I'm also not going to fight this if reviewers disagree.)

[Pierre-vh]

llvm/test/Transforms/InstCombine/pr34349.ll

17 ↗

(On Diff #486186)

I indeed did it using known bits after a comment from @spatel:

In the earlier version(s) of this patch (is there a functional diff here from D107552?), there were questions about how it would interact with SCEV and/or vectorization.

If we're focusing on the overflow-only/minimal pattern, then I think we should structure the matching as a known-bits/demanded-bits problem. Ie, instead of zexts, we might have and masks. Instead of a shift at the end, that might also be a mask op.

For me it's fine to do it with just zext but then I'm afraid we'd miss some profitable cases

[spatel]

llvm/test/Transforms/InstCombine/pr34349.ll

17 ↗

(On Diff #486186)

If we can get all of the motivating cases by matching zext directly, we can do that as a first step to reduce risk. Then, we can do the more general transform if needed as a second step.

IIUC, this means we could split off the ValueTracking part of the patch to an independent patch (add unit tests if there are no callers currently).

Also, please commit the baseline tests to main as a preliminary patch (D139011), so we can see current diffs (the bool math test diffs should be eliminated after 71df24dd39177ecfc440a0 ?)

[Pierre-vh]

Rebased tests for proper diff

Before I remove the known bits part and replace it with zext matching I would like @arsenm/@foad to give their opinions too

[arsenm]

In D138814#4031097, @Pierre-vh wrote:

Rebased tests for proper diff

Before I remove the known bits part and replace it with zext matching I would like @arsenm/@foad to give their opinions too

I think splitting the known bits part as a second step makes sense. The general case multiplies your potential bug surface so I think it's usually better to do this in 2 steps

[Pierre-vh]

Remove knownbits, use zext matching

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

866

We should put m_OneUse() limits on the m_ZExt matches. Also, add a test where the zexts have extra use(s).

That should avoid the +2 instruction count regression in the next patch. We are still potentially increasing instruction count with this transform, but the trade-off seems more reasonable if we can eliminate more of the intermediate instructions.

[Pierre-vh]

Add m_OneUse to m_ZExt in match

[spatel]

LGTM

[foad]

In D138814#3973599, @nikic wrote:

FWIW our historical stance has always been that uadd.with.overflow is non-canonical, and the canonical pattern is a + b < a (for non-constant b). uadd.with.overflow generally has worse optimization support, which is why we only form it during CGP for backend purposes.

What's the historical stance on sadd.with.overflow?

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

848

Likewise I don't think you need this line and the "boolean math" comment belongs on the "K > 1" line.

860

I don't think you need this check since you check below that K != 1 and it matches the width of X and Y, and the shift type must be strictly wider than that. But I guess it's harmless.

[nikic]

In D138814#4039101, @foad wrote:

In D138814#3973599, @nikic wrote:

FWIW our historical stance has always been that uadd.with.overflow is non-canonical, and the canonical pattern is a + b < a (for non-constant b). uadd.with.overflow generally has worse optimization support, which is why we only form it during CGP for backend purposes.

What's the historical stance on sadd.with.overflow?

sadd.with.overflow (and generally, all signed overflow intrinsics) are considered canonical, and we do produce them in InstCombine.

[Pierre-vh]

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

848

Will address in D141129

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
                           bool IsLogicalSelect = false);
 
   Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
                                        Instruction *CxtI, bool IsAnd,
                                        bool IsLogical = false);
   Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
   Value *getSelectCondition(Value *A, Value *B);
 
+  Instruction *foldXShrToOverflow(BinaryOperator &I);
   Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
   Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
   Instruction *foldFPSignBitOps(BinaryOperator &I);
   Instruction *foldFDivConstantDivisor(BinaryOperator &I);
 
   // Optimize one of these forms:
   //   and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
   //   or i1 Op, SI  / select i1 Op, i1 true, i1 SI  (if IsAnd = false)

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal &&
       Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift, NewRHS);
       return SelectInst::Create(Cond, NewShift, NewOp);
     }
   }
 
   return nullptr;
 }
 
+// Tries to perform
+//    (Xshr (add X, Y), K)
+//      -> (llvm.uadd.with.overflow (trunc X), (trunc Y)).overflow
+//    where
+//      - Xshr can be ashr or lshr
+//      - Only the K leading bits of X and Y can be non-zero.
+//      - The add is only used by the shr, or by iK truncates.
+Instruction *InstCombinerImpl::foldXShrToOverflow(BinaryOperator &I) {
+  assert(I.getOpcode() == Instruction::AShr ||
+         I.getOpcode() == Instruction::LShr);
+
+  const bool IsAShr = (I.getOpcode() == Instruction::AShr);
+  Value *Add = I.getOperand(0);
+  Value *ShiftAmt = I.getOperand(1);
+  Type *Ty = I.getType();
+
+  const APInt *ShAmtAPInt = nullptr;
+  Value *X = nullptr, *Y = nullptr;
+  if (!match(ShiftAmt, m_APInt(ShAmtAPInt)) ||
+      !match(Add, m_Add(m_Value(X), m_Value(Y))))
+    return nullptr;
+
+  const unsigned ShAmt = ShAmtAPInt->getZExtValue();
+  const unsigned BitWidth = Ty->getScalarSizeInBits();
+  const unsigned DesiredLeadingZeroes = BitWidth - ShAmt;
+
+  if (computeKnownBits(X, 0, &I).countMinLeadingZeros() <
+          DesiredLeadingZeroes ||
+      computeKnownBits(Y, 0, &I).countMinLeadingZeros() < DesiredLeadingZeroes)
+    return nullptr;
+
+  // Make sure that `Add` is only used by `I` and `ShAmt`-truncates.
+  if (!Add->hasOneUse()) {
+    for (User *U : Add->users()) {
+      if (U == &I)
+        continue;
+
+      TruncInst *Trunc = dyn_cast<TruncInst>(U);
+      if (!Trunc || Trunc->getType()->getScalarSizeInBits() > ShAmt)
+        return nullptr;
+    }
+  }
+
+  // Insert at Add so that the newly created `UAdd` will dominate it's users
+  // (i.e. `Add`'s users).
+  Instruction *AddInst = cast<Instruction>(Add);
+  BasicBlock::iterator RestoreInsPt = Builder.GetInsertPoint();
+  Builder.SetInsertPoint(AddInst);
+
+  Type *OpTy = Builder.getIntNTy(ShAmt);
+  X = Builder.CreateTrunc(X, OpTy);
+  Y = Builder.CreateTrunc(Y, OpTy);
+
+  Value *UAddOverflow = Builder.CreateBinaryIntrinsic(
+      Intrinsic::uadd_with_overflow, X, Y, /* FMFSource */ nullptr, "uaddo");
+  Value *UAdd = Builder.CreateExtractValue(UAddOverflow, 0,
+                                           UAddOverflow->getName() + ".add");
+  Value *Overflow = Builder.CreateExtractValue(
+      UAddOverflow, 1, UAddOverflow->getName() + ".overflow");
+
+  // Replace the uses of the original add with a zext of the
+  // uaddo's result.
+  if (!Add->hasOneUse())
+    replaceInstUsesWith(*AddInst, Builder.CreateZExt(UAdd, Ty));
+
+  Builder.SetInsertPoint(&(*RestoreInsPt));
+
+  // Replace the use of `Add` by `I` with `Overflow`.
+  //
+  // Note that for the transformation to be correct in the ashr i2 case,
+  // we need to use SExt instead of ZExt.
+  if (IsAShr && BitWidth == 2)
+    return new SExtInst(Overflow, Ty);
+  return new ZExtInst(Overflow, Ty);
+}
+
 Instruction *InstCombinerImpl::visitShl(BinaryOperator &I) {
   const SimplifyQuery Q = SQ.getWithInstruction(&I);
 
   if (Value *V = simplifyShlInst(I.getOperand(0), I.getOperand(1),
                                  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), Q))
     return replaceInstUsesWith(I, V);
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) {
   // Transform  (x << y) >> y  to  x & (-1 >> y)
   Value *X;
   if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))))) {
     Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
     Value *Mask = Builder.CreateLShr(AllOnes, Op1);
     return BinaryOperator::CreateAnd(Mask, X);
   }
 
+  if (Instruction *Overflow = foldXShrToOverflow(I))
+    return Overflow;
+
   return nullptr;
 }
 
 Instruction *
 InstCombinerImpl::foldVariableSignZeroExtensionOfVariableHighBitExtract(
     BinaryOperator &OldAShr) {
   assert(OldAShr.getOpcode() == Instruction::AShr &&
          "Must be called with arithmetic right-shift instruction only.");
Instruction *InstCombinerImpl::visitAShr(BinaryOperator &I) {
   // ashr (xor %x, -1), %y  -->  xor (ashr %x, %y), -1
   if (match(Op0, m_OneUse(m_Not(m_Value(X))))) {
     // Note that we must drop 'exact'-ness of the shift!
     // Note that we can't keep undef's in -1 vector constant!
     auto *NewAShr = Builder.CreateAShr(X, Op1, Op0->getName() + ".not");
     return BinaryOperator::CreateNot(NewAShr);
   }
 
+  if (Instruction *Overflow = foldXShrToOverflow(I))
+    return Overflow;
+
   return nullptr;
 }

llvm/test/Transforms/InstCombine/shift-add.ll

 ;
   %a = add i4 %x, 8
   %r = shl nsw i4 2, %a
   ret i4 %r
 }
 
 define i2 @lshr_2_add_zext_basic(i1 %a, i1 %b) {
 ; CHECK-LABEL: @lshr_2_add_zext_basic(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i1 [[A:%.*]] to i2
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i1 [[B:%.*]] to i2
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw i2 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i2 [[ADD]], 1
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i1, i1 } @llvm.uadd.with.overflow.i1(i1 [[A:%.*]], i1 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i1, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i2
 ; CHECK-NEXT:    ret i2 [[LSHR]]
 ;
   %zext.a = zext i1 %a to i2
   %zext.b = zext i1 %b to i2
   %add = add i2 %zext.a, %zext.b
   %lshr = lshr i2 %add, 1
   ret i2 %lshr
 }
 
 define i2 @ashr_2_add_zext_basic(i1 %a, i1 %b) {
 ; CHECK-LABEL: @ashr_2_add_zext_basic(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i1 [[A:%.*]] to i2
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i1 [[B:%.*]] to i2
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw i2 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[LSHR:%.*]] = ashr i2 [[ADD]], 1
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i1, i1 } @llvm.uadd.with.overflow.i1(i1 [[A:%.*]], i1 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i1, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[LSHR:%.*]] = sext i1 [[UADDO_OVERFLOW]] to i2
 ; CHECK-NEXT:    ret i2 [[LSHR]]
 ;
   %zext.a = zext i1 %a to i2
   %zext.b = zext i1 %b to i2
   %add = add i2 %zext.a, %zext.b
   %lshr = ashr i2 %add, 1
   ret i2 %lshr
 }
 
 define i32 @lshr_16_add_zext_basic(i16 %a, i16 %b) {
 ; CHECK-LABEL: @lshr_16_add_zext_basic(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i16 [[A:%.*]] to i32
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i16 [[B:%.*]] to i32
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ADD]], 16
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 [[A:%.*]], i16 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i16, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i32
 ; CHECK-NEXT:    ret i32 [[LSHR]]
 ;
   %zext.a = zext i16 %a to i32
   %zext.b = zext i16 %b to i32
   %add = add i32 %zext.a, %zext.b
   %lshr = lshr i32 %add, 16
   ret i32 %lshr
 }
 
 ; This should combine as we have 16 leading zeroes.
 
 define i32 @lshr_16_add_known_16_leading_zeroes(i32 %a, i32 %b) {
 ; CHECK-LABEL: @lshr_16_add_known_16_leading_zeroes(
-; CHECK-NEXT:    [[A16:%.*]] = and i32 [[A:%.*]], 65535
-; CHECK-NEXT:    [[B16:%.*]] = and i32 [[B:%.*]], 65535
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[A16]], [[B16]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ADD]], 16
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[A:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc i32 [[B:%.*]] to i16
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 [[TMP1]], i16 [[TMP2]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i16, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i32
 ; CHECK-NEXT:    ret i32 [[LSHR]]
 ;
   %a16 = and i32 %a, 65535 ; 0x65535
   %b16 = and i32 %b, 65535 ; 0x65535
   %add = add i32 %a16, %b16
   %lshr = lshr i32 %add, 16
   ret i32 %lshr
 }
;
   %b16 = and i32 %b, 65535 ; 0x65535
   %add = add i32 %a16, %b16
   %lshr = lshr i32 %add, 16
   ret i32 %lshr
 }
 
 define i64 @lshr_32_add_zext_basic(i32 %a, i32 %b) {
 ; CHECK-LABEL: @lshr_32_add_zext_basic(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i32 [[A:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i32 [[B:%.*]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i64 [[ADD]], 32
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[A:%.*]], i32 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i64
 ; CHECK-NEXT:    ret i64 [[LSHR]]
 ;
   %zext.a = zext i32 %a to i64
   %zext.b = zext i32 %b to i64
   %add = add i64 %zext.a, %zext.b
   %lshr = lshr i64 %add, 32
   ret i64 %lshr
 }
 
 define i64 @lshr_16_to_64_add_zext_basic(i16 %a, i16 %b) {
 ; CHECK-LABEL: @lshr_16_to_64_add_zext_basic(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i16 [[A:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i64 [[ADD]], 16
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 [[A:%.*]], i16 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i16, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i64
 ; CHECK-NEXT:    ret i64 [[LSHR]]
 ;
   %zext.a = zext i16 %a to i64
   %zext.b = zext i16 %b to i64
   %add = add i64 %zext.a, %zext.b
   %lshr = lshr i64 %add, 16
   ret i64 %lshr
 }
 
 ; This should combine as we have 32 leading zeroes.
 
 define i64 @lshr_32_add_known_32_leading_zeroes(i64 %a, i64 %b) {
 ; CHECK-LABEL: @lshr_32_add_known_32_leading_zeroes(
-; CHECK-NEXT:    [[A32:%.*]] = and i64 [[A:%.*]], 4294967295
-; CHECK-NEXT:    [[B32:%.*]] = and i64 [[B:%.*]], 4294967295
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[A32]], [[B32]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i64 [[ADD]], 32
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[A:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[B:%.*]] to i32
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[TMP1]], i32 [[TMP2]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i64
 ; CHECK-NEXT:    ret i64 [[LSHR]]
 ;
   %a32 = and i64 %a, 4294967295 ; 0xFFFFFFFF
   %b32 = and i64 %b, 4294967295 ; 0xFFFFFFFF
   %add = add i64 %a32, %b32
   %lshr = lshr i64 %add, 32
   ret i64 %lshr
 }
;
   %b32 = and i64 %b, 4294967295 ; 0xFFFFFFFF
   %add = add i64 %a32, %b32
   %lshr = lshr i64 %add, 32
   ret i64 %lshr
 }
 
 define i32 @ashr_16_add_zext_basic(i16 %a, i16 %b) {
 ; CHECK-LABEL: @ashr_16_add_zext_basic(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i16 [[A:%.*]] to i32
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i16 [[B:%.*]] to i32
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ADD]], 16
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 [[A:%.*]], i16 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i16, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i32
 ; CHECK-NEXT:    ret i32 [[LSHR]]
 ;
   %zext.a = zext i16 %a to i32
   %zext.b = zext i16 %b to i32
   %add = add i32 %zext.a, %zext.b
   %lshr = lshr i32 %add, 16
   ret i32 %lshr
 }
 
 define i64 @ashr_32_add_zext_basic(i32 %a, i32 %b) {
 ; CHECK-LABEL: @ashr_32_add_zext_basic(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i32 [[A:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i32 [[B:%.*]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[ADD]], 32
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[A:%.*]], i32 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i64
 ; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %zext.a = zext i32 %a to i64
   %zext.b = zext i32 %b to i64
   %add = add i64 %zext.a, %zext.b
   %lshr = ashr i64 %add, 32
   ret i64 %lshr
 }
 
 define i64 @ashr_16_to_64_add_zext_basic(i16 %a, i16 %b) {
 ; CHECK-LABEL: @ashr_16_to_64_add_zext_basic(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i16 [[A:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i16 [[B:%.*]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[ADD]], 16
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 [[A:%.*]], i16 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i16, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i64
 ; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %zext.a = zext i16 %a to i64
   %zext.b = zext i16 %b to i64
   %add = add i64 %zext.a, %zext.b
   %lshr = ashr i64 %add, 16
   ret i64 %lshr
 }
 
 define i32 @lshr_32_add_zext_trunc(i32 %a, i32 %b) {
 ; CHECK-LABEL: @lshr_32_add_zext_trunc(
-; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i32 [[A:%.*]] to i64
-; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i32 [[B:%.*]] to i64
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[ZEXT_A]], [[ZEXT_B]]
-; CHECK-NEXT:    [[TRUNC_ADD:%.*]] = trunc i64 [[ADD]] to i32
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i64 [[ADD]], 32
-; CHECK-NEXT:    [[TRUNC_SHR:%.*]] = trunc i64 [[SHR]] to i32
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[TRUNC_ADD]], [[TRUNC_SHR]]
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[A:%.*]], i32 [[B:%.*]])
+; CHECK-NEXT:    [[UADDO_ADD:%.*]] = extractvalue { i32, i1 } [[UADDO]], 0
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[TRUNC_SHR:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i32
+; CHECK-NEXT:    [[RET:%.*]] = add i32 [[UADDO_ADD]], [[TRUNC_SHR]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %zext.a = zext i32 %a to i64
   %zext.b = zext i32 %b to i64
   %add = add i64 %zext.a, %zext.b
   %trunc.add = trunc i64 %add to i32
   %shr = lshr i64 %add, 32
   %trunc.shr = trunc i64 %shr to i32
   %ret = add i32 %trunc.add, %trunc.shr
   ret i32 %ret
 }
 
 define <3 x i32> @add3_i96(<3 x i32> %0, <3 x i32> %1) {
 ; CHECK-LABEL: @add3_i96(
 ; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <3 x i32> [[TMP0:%.*]], i64 0
-; CHECK-NEXT:    [[TMP4:%.*]] = zext i32 [[TMP3]] to i64
-; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <3 x i32> [[TMP1:%.*]], i64 0
+; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <3 x i32> [[TMP1:%.*]], i64 0
+; CHECK-NEXT:    [[UADDO:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[TMP4]], i32 [[TMP3]])
+; CHECK-NEXT:    [[UADDO_ADD:%.*]] = extractvalue { i32, i1 } [[UADDO]], 0
+; CHECK-NEXT:    [[UADDO_OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UADDO]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <3 x i32> [[TMP0]], i64 1
 ; CHECK-NEXT:    [[TMP6:%.*]] = zext i32 [[TMP5]] to i64
-; CHECK-NEXT:    [[TMP7:%.*]] = add nuw nsw i64 [[TMP6]], [[TMP4]]
-; CHECK-NEXT:    [[TMP8:%.*]] = extractelement <3 x i32> [[TMP0]], i64 1
-; CHECK-NEXT:    [[TMP9:%.*]] = zext i32 [[TMP8]] to i64
-; CHECK-NEXT:    [[TMP10:%.*]] = extractelement <3 x i32> [[TMP1]], i64 1
-; CHECK-NEXT:    [[TMP11:%.*]] = zext i32 [[TMP10]] to i64
-; CHECK-NEXT:    [[TMP12:%.*]] = add nuw nsw i64 [[TMP11]], [[TMP9]]
-; CHECK-NEXT:    [[TMP13:%.*]] = lshr i64 [[TMP7]], 32
-; CHECK-NEXT:    [[TMP14:%.*]] = add nuw nsw i64 [[TMP12]], [[TMP13]]
-; CHECK-NEXT:    [[TMP15:%.*]] = extractelement <3 x i32> [[TMP0]], i64 2
-; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <3 x i32> [[TMP1]], i64 2
-; CHECK-NEXT:    [[TMP17:%.*]] = add i32 [[TMP16]], [[TMP15]]
-; CHECK-NEXT:    [[TMP18:%.*]] = lshr i64 [[TMP14]], 32
-; CHECK-NEXT:    [[TMP19:%.*]] = trunc i64 [[TMP18]] to i32
-; CHECK-NEXT:    [[TMP20:%.*]] = add i32 [[TMP17]], [[TMP19]]
-; CHECK-NEXT:    [[TMP21:%.*]] = trunc i64 [[TMP7]] to i32
-; CHECK-NEXT:    [[TMP22:%.*]] = insertelement <3 x i32> undef, i32 [[TMP21]], i64 0
-; CHECK-NEXT:    [[TMP23:%.*]] = trunc i64 [[TMP14]] to i32
-; CHECK-NEXT:    [[TMP24:%.*]] = insertelement <3 x i32> [[TMP22]], i32 [[TMP23]], i64 1
-; CHECK-NEXT:    [[TMP25:%.*]] = insertelement <3 x i32> [[TMP24]], i32 [[TMP20]], i64 2
-; CHECK-NEXT:    ret <3 x i32> [[TMP25]]
+; CHECK-NEXT:    [[TMP7:%.*]] = extractelement <3 x i32> [[TMP1]], i64 1
+; CHECK-NEXT:    [[TMP8:%.*]] = zext i32 [[TMP7]] to i64
+; CHECK-NEXT:    [[TMP9:%.*]] = add nuw nsw i64 [[TMP8]], [[TMP6]]
+; CHECK-NEXT:    [[TMP10:%.*]] = zext i1 [[UADDO_OVERFLOW]] to i64
+; CHECK-NEXT:    [[TMP11:%.*]] = add nuw nsw i64 [[TMP9]], [[TMP10]]
+; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <3 x i32> [[TMP0]], i64 2
+; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <3 x i32> [[TMP1]], i64 2
+; CHECK-NEXT:    [[TMP14:%.*]] = add i32 [[TMP13]], [[TMP12]]
+; CHECK-NEXT:    [[TMP15:%.*]] = lshr i64 [[TMP11]], 32
+; CHECK-NEXT:    [[TMP16:%.*]] = trunc i64 [[TMP15]] to i32
+; CHECK-NEXT:    [[TMP17:%.*]] = add i32 [[TMP14]], [[TMP16]]
+; CHECK-NEXT:    [[TMP18:%.*]] = insertelement <3 x i32> undef, i32 [[UADDO_ADD]], i64 0
+; CHECK-NEXT:    [[TMP19:%.*]] = trunc i64 [[TMP11]] to i32
+; CHECK-NEXT:    [[TMP20:%.*]] = insertelement <3 x i32> [[TMP18]], i32 [[TMP19]], i64 1
+; CHECK-NEXT:    [[TMP21:%.*]] = insertelement <3 x i32> [[TMP20]], i32 [[TMP17]], i64 2
+; CHECK-NEXT:    ret <3 x i32> [[TMP21]]
 ;
   %3 = extractelement <3 x i32> %0, i64 0
   %4 = zext i32 %3 to i64
   %5 = extractelement <3 x i32> %1, i64 0
   %6 = zext i32 %5 to i64
   %7 = add nuw nsw i64 %6, %4
   %8 = extractelement <3 x i32> %0, i64 1
   %9 = zext i32 %8 to i64