This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Add transforms for `(icmp upred (or X, Y), X)`
ClosedPublic

Authored by goldstein.w.n on Feb 22 2023, 5:20 PM.

Details

Summary

We can simplify ule/ugt -> eq/ne and we can remove the Or in some
cases of eq/ne.

icmp (X | Y) u<= X --> (X | Y) == X

icmp (X | Y) u> X --> (X | Y) != X

icmp (X | Y) eq/ne X

Diff Detail

Event Timeline

goldstein.w.n created this revision.Feb 22 2023, 5:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 22 2023, 5:20 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
goldstein.w.n requested review of this revision.Feb 22 2023, 5:20 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 22 2023, 5:20 PM

Split into two patch + helper

goldstein.w.n retitled this revision from [InstCombine] Add transforms for `(icmp (xor X, Y), X)` to [InstCombine] Add transforms for `(icmp upred (or X, Y), X)`.Mar 3 2023, 4:01 PM
goldstein.w.n edited the summary of this revision. (Show Details)
goldstein.w.n edited the summary of this revision. (Show Details)

Rebase

Swap operands so op0 is always or for cleaner logic

nikic added inline comments.May 28 2023, 3:56 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4127–4133

I'm somewhat skeptical about this fold. I can see where you're coming from here, in terms of picking a canonical form between and/or for this pattern, but the fact that we need the undef limitation here (so the canonicalization will be fairly unreliable) and that and/or are generally always handled in conjugate patterns (i.e. we shouldn't have cases where one optimizes better than the other) makes this fold not very compelling to me.

The more obvious canonicalization choice would be X & ~Y == 0, but that adds an extra instruction. We do canonicalize this for the case where Y is a constant, but don't do it even if Y is freely invertable (https://llvm.godbolt.org/z/7MWefMbP9).

goldstein.w.n added inline comments.May 28 2023, 9:04 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4127–4133

I'm somewhat skeptical about this fold. I can see where you're coming from here, in terms of picking a canonical form between and/or for this pattern, but the fact that we need the undef limitation here (so the canonicalization will be fairly unreliable) and that and/or are generally always handled in conjugate patterns (i.e. we shouldn't have cases where one optimizes better than the other) makes this fold not very compelling to me.

Agreed that is a limitation, but seems to me be better than nothing no?

The more obvious canonicalization choice would be X & ~Y == 0, but that adds an extra instruction. We do canonicalize this for the case where Y is a constant, but don't do it even if Y is freely invertable (https://llvm.godbolt.org/z/7MWefMbP9).

Although if Y is constant then it will be no undef so it will reach X & Y == Y -> X & ~Y == 0 either way.

goldstein.w.n added inline comments.May 28 2023, 9:12 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4127–4133

I'm somewhat skeptical about this fold. I can see where you're coming from here, in terms of picking a canonical form between and/or for this pattern, but the fact that we need the undef limitation here (so the canonicalization will be fairly unreliable) and that and/or are generally always handled in conjugate patterns (i.e. we shouldn't have cases where one optimizes better than the other) makes this fold not very compelling to me.

Agreed that is a limitation, but seems to me be better than nothing no?

The more obvious canonicalization choice would be X & ~Y == 0, but that adds an extra instruction. We do canonicalize this for the case where Y is a constant, but don't do it even if Y is freely invertable (https://llvm.godbolt.org/z/7MWefMbP9).

Although if Y is constant then it will be no undef so it will reach X & Y == Y -> X & ~Y == 0 either way.

4127–4133

I'm somewhat skeptical about this fold. I can see where you're coming from here, in terms of picking a canonical form between and/or for this pattern, but the fact that we need the undef limitation here (so the canonicalization will be fairly unreliable) and that and/or are generally always handled in conjugate patterns (i.e. we shouldn't have cases where one optimizes better than the other) makes this fold not very compelling to me.

Agreed that is a limitation, but seems to me be better than nothing no?

The more obvious canonicalization choice would be X & ~Y == 0, but that adds an extra instruction. We do canonicalize this for the case where Y is a constant, but don't do it even if Y is freely invertable (https://llvm.godbolt.org/z/7MWefMbP9).

Although if Y is constant then it will be no undef so it will reach X & Y == Y -> X & ~Y == 0 either way.

I'm wrong about this. Okay ill update to make only for constants and do the ~Y version.

goldstein.w.n added inline comments.May 28 2023, 9:12 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4127–4133

Added X & ~Y versions. Kept noundef version. It generally the norm for functions signitures so think it likely still has value. LMK, however, if you want me to remove it.

Add X & ~Y == 0 transform

nikic added inline comments.Aug 12 2023, 1:01 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4128–4130

No need to spell out one-use in comments.

4140

As said previously, I don't think this canonicalization makes sense. Please drop it so we can land the rest of this patch.

goldstein.w.n marked 2 inline comments as done.Aug 12 2023, 2:58 PM

Cleanup comment + remove noundef fold

nikic added inline comments.Aug 13 2023, 12:24 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4120

Rebase mistake?

nikic added inline comments.Aug 13 2023, 12:33 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4149

The proofs in the patch description need an update.

Worth noting that there is also a similar fold for the case where X is freely invertible: https://alive2.llvm.org/ce/z/cpPV_W

This case might actually be the more common one, because it covers (X | C) == X.

goldstein.w.n added inline comments.Aug 13 2023, 8:21 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4120

Ah, yeah that should be with the following patch. Will update.

goldstein.w.n edited the summary of this revision. (Show Details)Aug 13 2023, 10:55 AM
goldstein.w.n edited the summary of this revision. (Show Details)
goldstein.w.n marked 2 inline comments as done.Aug 13 2023, 11:01 AM

Add another freely invertible fold

foad added a subscriber: foad.Aug 14 2023, 2:01 AM

We can simplify ule/ugt -> eq/ne and we can remove the xor in some
cases of eq/ne.

What does "the xor" refer to? Description needs updating?

foad added inline comments.Aug 14 2023, 2:08 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4116

"else if" to avoid doing the match twice if we swapped?

4124

No "else" after "return"

4137

The comments say "X" but the code says "A". Can you change one or the other so they match?

nikic added inline comments.Aug 14 2023, 2:52 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4130

You can replace this with isFreeToInvert(Op1, Op1->hasOneUse()). This will also handle some additional cases if the operand only has one use.

goldstein.w.n edited the summary of this revision. (Show Details)Aug 14 2023, 8:40 AM

We can simplify ule/ugt -> eq/ne and we can remove the xor in some
cases of eq/ne.

What does "the xor" refer to? Description needs updating?

Mistype, fixed.

goldstein.w.n marked 4 inline comments as done.Aug 14 2023, 8:45 AM

Fix up some nits

nikic accepted this revision.Aug 15 2023, 3:00 AM

LGTM

This revision is now accepted and ready to land.Aug 15 2023, 3:00 AM
This revision was landed with ongoing or failed builds.Aug 16 2023, 12:00 AM
This revision was automatically updated to reflect the committed changes.