This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Generalize foldICmpWithMinMax
ClosedPublic

Authored by dtcxzyw on Jul 25 2023, 6:51 AM.

Details

Summary

This patch generalizes the fold of icmp pred min/max(X, Y), Z to address the issue https://github.com/llvm/llvm-project/issues/62898.

For example, we can fold smin(X, Y) < Z into X < Z when Y > Z is implied by constant folds/invariants/dom conditions.

Alive2 (with --disable-undef-input due to the limitation of --smt-to=10000): https://alive2.llvm.org/ce/z/rB7qLc
You can run the standalone translation validation tool alive-tv locally to verify these transformations.

alive-tv transforms.ll --smt-to=600000 --exit-on-error

Diff Detail

Unit TestsFailed

Event Timeline

dtcxzyw created this revision.Jul 25 2023, 6:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 25 2023, 6:51 AM
dtcxzyw requested review of this revision.Jul 25 2023, 6:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 25 2023, 6:51 AM
xbolva00 added inline comments.
llvm/test/Transforms/InstCombine/smax-icmp.ll
67

Some comments need updates

goldstein.w.n added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4982

AsOptional doens't seem like a very useful name. Maybe IsCondKnownTrue or something might be better.

4987

See: m_c_MaxOrMin in PatternMatch. This can be:

if(!match(Val, m_c_MaxOrMin(X, Y)))
return false;
MinMaxIntrinsic = cast<Intrinsic>(Val)->getIntrinsicID();
return true;
4988

This needs a header comment to explain its purpose.

5006

Two things about these comments.

  1. They should reference the predicate they are folding for. I.e it looks like the top comment is regarding icmp eq and the bottom one is regarding icmp ne but thats not clear anywhere.
  1. Can they be a bit more explicit that the second/third columns are the resulting fold (i.e add table column names).
dtcxzyw added inline comments.Aug 24 2023, 10:24 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4987

m_c_MaxOrMin doesn't always match a MinMaxIntrinsic. It also matches the pattern (x pred y) ? x : y.

goldstein.w.n added inline comments.Aug 24 2023, 10:31 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4987

Ah, my mistake keep as is.

nikic added inline comments.Aug 24 2023, 11:26 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4987

But why not dyn_cast<MinMaxIntrinsic>? The select pattern is non-canonical and as such not relevant for InstCombine.

dtcxzyw updated this revision to Diff 553508.Aug 25 2023, 8:58 AM
dtcxzyw added a reviewer: goldstein.w.n.
  • Rebase
  • Address feedback
dtcxzyw marked 7 inline comments as done.Aug 25 2023, 8:59 AM
goldstein.w.n added inline comments.Aug 25 2023, 1:13 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5003

Think you mean Y == Z here?

5005

Think you mean Y != Z

5007

same thing and likewise below.

5044

Same issue with the fact column as above.

5045

Note on the comments. These are large blocks that are easy to get lost in.

I would suggest reformatting as follows.

  1. Format as:

Expr Fact Result. The expression is really what allows us to match the comment to a predicate / the codes you are transforming.

  1. Split the comments so instead of giant blocks, put the relevenat Expr below each case in the switch statemnt i.e
case SLT:
case ULT:
// Expr Fact Result where expr is LT variant.
case SLE:
case ULE:
// Expr Fact Result where expr is LE variant.
...

Likewise for the eq/ne cases.

dtcxzyw marked 4 inline comments as done.Aug 26 2023, 6:53 AM
dtcxzyw added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5003

It is X == Z. It just checks the value of CmpXZ and then folds the expr.

dtcxzyw updated this revision to Diff 553736.Aug 26 2023, 8:16 AM
dtcxzyw marked an inline comment as done.
  • Rebase
  • Update comments
dtcxzyw marked an inline comment as done.Aug 26 2023, 8:16 AM
goldstein.w.n added inline comments.Aug 28 2023, 10:55 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5004

Still missing fact for different transforms?

dtcxzyw marked an inline comment as done.Aug 28 2023, 6:18 PM
dtcxzyw added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5001

The fact is here.

Still missing fact for different transforms?

goldstein.w.n added inline comments.Aug 28 2023, 7:25 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5004

Shouldn't there be a factor for Y == Z?

dtcxzyw marked an inline comment as done.Aug 28 2023, 7:44 PM
dtcxzyw added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5004

I am sure that the fact to check is X == Z. https://alive2.llvm.org/ce/z/73Ta9S

CmpYZ is optional. When CmpXZ is unavailable and CmpYZ has a value, X and Y will get swapped.

Think mostly looks good.

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

nit: Braces because so many lines (or move comments to before the if). Also you need need the else in the two blocks b.c return in if

dtcxzyw updated this revision to Diff 554267.Aug 29 2023, 4:55 AM
dtcxzyw marked an inline comment as done.
  • Rebase
  • Address comments
dtcxzyw marked an inline comment as done.Aug 29 2023, 4:55 AM
nikic added inline comments.Aug 29 2023, 7:41 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4976

You can use MinMaxIntrinsic::isSigned(MinMaxIntrinsic).

Or maybe cleaner, you can pass in in the MinMaxIntrinsic and then do things like II->isSigned().

5031

Please add some vector tests. This looks like it will break with vector icmp.

dtcxzyw updated this revision to Diff 554398.Aug 29 2023, 9:46 AM
  • Rebase
  • Add some vector tests
  • Handle vector icmp
dtcxzyw marked 2 inline comments as done.Aug 29 2023, 9:50 AM
dtcxzyw added inline comments.
llvm/test/Transforms/InstCombine/smin-icmp.ll
447–448

Seems like simplifyICmpInst cannot infer X != Z with the fact X < Z. I will address this in a separate patch.
Alive2: https://alive2.llvm.org/ce/z/aaYERr

goldstein.w.n added inline comments.Aug 29 2023, 12:33 PM
llvm/test/Transforms/InstCombine/smin-icmp.ll
961

These belong with the test patch.

dtcxzyw marked an inline comment as done.Sep 9 2023, 12:25 AM
This revision is now accepted and ready to land.Sep 9 2023, 11:09 PM

@goldstein.w.n Could you please take a look at the test part D156227?

This revision was automatically updated to reflect the committed changes.
nikic added inline comments.Sep 15 2023, 11:47 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5032–5033
dtcxzyw marked an inline comment as done.Sep 16 2023, 2:44 AM
dtcxzyw added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5032–5033
dtcxzyw marked an inline comment as done.Sep 18 2023, 11:26 PM
This revision is now accepted and ready to land.Sep 24 2023, 6:48 PM