This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Add transforms for `(or/and (icmp eq/ne X,0),(icmp eq/ne X,Pow2OrZero))`
AbandonedPublic

Authored by goldstein.w.n on Aug 7 2023, 10:50 AM.

Details

Reviewers
nikic
Allen
Summary

(or (icmp eq X, 0), (icmp eq X, Pow2OrZero))

--> `(icmp eq (and X, Pow2OrZero), X)`

(and (icmp ne X, 0), (icmp ne X, Pow2OrZero))

--> `(icmp ne (and X, Pow2OrZero), X)`

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

Diff Detail

Event Timeline

goldstein.w.n created this revision.Aug 7 2023, 10:50 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 7 2023, 10:50 AM
goldstein.w.n requested review of this revision.Aug 7 2023, 10:50 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 7 2023, 10:50 AM
Allen added inline comments.Aug 24 2023, 7:25 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
764

LHS and RHS are commutative . Do we need to consider it?

goldstein.w.n added inline comments.Aug 24 2023, 9:59 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
764

Above we swap LHS/RHS so that LHS is the comparison against zero: L757.

If you are refering to not using m_c_ICmp here then its also no issue b.c of canonicalization.

Allen added inline comments.Aug 24 2023, 7:33 PM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
743

nit: Pow2 -> Pow2OrZero

764

oh, I missed the swap, thanks.

nikic added a comment.Aug 25 2023, 3:24 AM

Not sure we should do this transform in IR. The original form seems to be a lot simpler to reason about than the new one -- e.g. if you have that as condition, it's obvious that %x can't be zero (as there's an explicit check for it). Afterwards, that would be fairly hard to determine.

Not sure we should do this transform in IR. The original form seems to be a lot simpler to reason about than the new one -- e.g. if you have that as condition, it's obvious that %x can't be zero (as there's an explicit check for it). Afterwards, that would be fairly hard to determine.

Really? We have a fair amount of logic for X & Y eq/ne ... and we do this fold already for constants (and similiar folds for non-constants).
Also since its an equivilency and only relies on Pow2OrZero being a pow2orzero, theres no information loss.

nikic added a comment.Aug 25 2023, 1:26 PM

Not sure we should do this transform in IR. The original form seems to be a lot simpler to reason about than the new one -- e.g. if you have that as condition, it's obvious that %x can't be zero (as there's an explicit check for it). Afterwards, that would be fairly hard to determine.

Really? We have a fair amount of logic for X & Y eq/ne ... and we do this fold already for constants (and similiar folds for non-constants).
Also since its an equivilency and only relies on Pow2OrZero being a pow2orzero, theres no information loss.

For constants this is turned into an X & ~C eq 0 or X & ~C ne 0 pattern. That is well understood due to the obvious KnownBits implications. X & Y == X not so much I think.

goldstein.w.n added a comment.EditedAug 25 2023, 2:18 PM

Not sure we should do this transform in IR. The original form seems to be a lot simpler to reason about than the new one -- e.g. if you have that as condition, it's obvious that %x can't be zero (as there's an explicit check for it). Afterwards, that would be fairly hard to determine.

Really? We have a fair amount of logic for X & Y eq/ne ... and we do this fold already for constants (and similiar folds for non-constants).
Also since its an equivilency and only relies on Pow2OrZero being a pow2orzero, theres no information loss.

For constants this is turned into an X & ~C eq 0 or X & ~C ne 0 pattern. That is well understood due to the obvious KnownBits implications. X & Y == X not so much I think.

How about if we get D145424, D145425, and D145426 in as well?
Otherwise I'll move to the DAG, but since we split branches in SelectionDAGLowering folds like this lose alot of there effectiveness.

Okay, let's give this a try.

llvm/test/Transforms/InstCombine/and-or-icmps.ll
3135

Please also add tests with logical and/or that don't fold (with pow2 on the right).

I thin kwe'd also missing a test where the comparison is not against zero but another constant.

goldstein.w.n marked 3 inline comments as done.

Rebase (ontop of a lot of new stuff and AndXX Support)

nikic accepted this revision.Aug 29 2023, 3:46 AM

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
751

out op?

This revision is now accepted and ready to land.Aug 29 2023, 3:46 AM
goldstein.w.n abandoned this revision.Sep 19 2023, 9:11 AM

Abandoning and resubmitting on GH