This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fold icmps comparing uadd_sat with a constant
ClosedPublic

Authored by 0xdc03 on Jul 5 2023, 10:43 PM.

Details

Summary

This patch is a continuation of D154206. It introduces a fold for the
operation "uadd_sat(X, C) pred C2" where "C" and "C2" are constants. The
fold is:

uadd_sat(X, C) pred C2
=> (X >= ~C) || ((X + C) pred C2) -> when (UINT_MAX pred C2) is true
=> (X < ~C)  && ((X + C) pred C2) -> when (UINT_MAX pred C2) is false

These expressions can generally be folded into a simpler expression. As
they can sometimes emit more than one instruction, they are limited to
cases where the "uadd_sat" has only one user.

Proofs: https://alive2.llvm.org/ce/z/wWeirP

Diff Detail

Event Timeline

0xdc03 created this revision.Jul 5 2023, 10:43 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 5 2023, 10:43 PM
0xdc03 requested review of this revision.Jul 5 2023, 10:43 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 5 2023, 10:43 PM
0xdc03 edited the summary of this revision. (Show Details)Jul 5 2023, 10:44 PM
0xdc03 updated this revision to Diff 537589.Jul 5 2023, 10:49 PM
  • Rebase on patch for tests: D154566
0xdc03 added inline comments.Jul 5 2023, 10:54 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3625

This expression can be simplified to:

LHSPred = (IntrinsicIsUAddSat XNOR SaturatingValueCheck) ? ICmpInst::ICMP_UGE : ICmpInst::ICMP_ULT;

i.e. (IntrinsicIsUAddSat == SaturatingValueCheck), however I feel that just looks ugly.

nikic added inline comments.Jul 6 2023, 12:27 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3632

In the end, what we're computing here is the range of values where the add/sub doesn't (or does) overflow. Can we express this in terms of makeExactNoWrapRegion() instead? That would also make it easier to extend this to signed intrinsics in the future, where the overflow condition is more complex.

0xdc03 updated this revision to Diff 537776.Jul 6 2023, 10:04 AM
  • Replace usage of makeExactICmpRegion with makeExactNoWrapRegion
0xdc03 marked an inline comment as done.Jul 6 2023, 10:05 AM
0xdc03 added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3632

Yup, this works quite well 😄

0xdc03 marked an inline comment as done.Jul 6 2023, 10:05 AM
0xdc03 updated this revision to Diff 537778.Jul 6 2023, 10:16 AM
  • Update to use SaturatingInst
nikic added inline comments.Jul 6 2023, 11:03 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3587

Directly accept SaturingInst (moving the cast to the caller)?

3622

Now that makeExactNoWrapRegion is used, I think we can combine both cases to something like this:

// Let Y = add/sub_sat(X, C) pred C2
//  => Y = (no_overflow ? sat_val : (X binop C)) pred C2
//  => Y = no_overflow ? (sat_val pred C2) : ((X binop C) pred C2)
//
// When (sat_val pred C2) is true, then
//    Y = no_overflow ? true : ((X binop C) pred C2)
// => Y = no_overflow || ((X binop C) pred C2)
// else
//    Y = no_overflow ? false : ((X binop C) pred C2)
// => Y = !no_overflow && ((X binop C) pred C2)

This is true for all saturating intrinsics and matches the implementation more closely. Extension to the signed case at this point would only involve determining the right sat_val.

It would also be possible to replace the last line with:

// => Y = !(no_overflow || !((X - C) pred C2))

Which might make the implementation a bit simpler because you only have two optional inverts, and can always use exactUnionWith. Not sure whether this is better or not.

0xdc03 updated this revision to Diff 538137.Jul 7 2023, 7:28 AM
  • Address reviewer comments
    • Generalize the formula
    • Redo the comments to be better
    • Make parameter a SaturatingInst
0xdc03 marked 2 inline comments as done.Jul 7 2023, 7:29 AM
0xdc03 added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3622

Okay, I have done this and cleaned up the formula, hopefully the code is better now.

nikic accepted this revision.Jul 7 2023, 1:16 PM

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3643

I feel like this comment is largely redundant with the one above...

3651

This variable is only used here -- check II->getBinaryOp() == Instruction::Add instead?

This revision is now accepted and ready to land.Jul 7 2023, 1:16 PM
0xdc03 updated this revision to Diff 538322.Jul 7 2023, 10:35 PM
  • Simplify comment
  • Remove IntrinsicIsAddition
0xdc03 marked 3 inline comments as done.Jul 7 2023, 10:36 PM
0xdc03 added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
3643

Sure, that was mainly for me to understand what I had done.

0xdc03 marked an inline comment as done.Jul 7 2023, 10:37 PM