Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[InstCombine] Missed optimization for icmp ult <power-of-2> & mask check #54856

Closed
erikdesjardins opened this issue Apr 12, 2022 · 5 comments
Closed

[InstCombine] Missed optimization for icmp ult <power-of-2> & mask check #54856

erikdesjardins opened this issue Apr 12, 2022 · 5 comments
Assignees
@jmciver
Labels
confirmed Verified by a second party llvm:instcombine missed-optimization

Comments

@erikdesjardins
Copy link
Member 

define i1 @src(i32 %arg) {
  %a = icmp ult i32 %arg, C1
  %b = and i32 %arg, C2
  %c = icmp ne i32 %b, C2
  %r = and i1 %a, %c
  ret i1 %r
}

is equivalent to:

define i1 @tgt(i32 %arg) {
  %r = icmp ult i32, %arg, C2
  ret i1 %r
}

where C1 is a power of 2, and C2 is a contiguous mask of bits starting 1 bit "below" C1.

For example:

If C1 is       00100000

then C2 can be 00010000
            or 00011000
            or 00011100, etc.

and can not be 00010100
            or 00111000, etc.

This is already optimized if C2 is also a power of 2, but not if it has more than one set bit: https://godbolt.org/z/3a6WbKabr

Alive2 proof: https://alive2.llvm.org/ce/z/3Se4bm
@erikdesjardins erikdesjardins mentioned this issue Apr 12, 2022
Merged
@jmciver
Copy link
Contributor

jmciver commented Apr 19, 2022 •
edited
Loading

I am interested in working on this issue. I have started looking into a solution.

@RKSimon RKSimon added llvm:optimizations confirmed Verified by a second party labels Apr 19, 2022
@jmciver
Copy link
Contributor

jmciver commented May 3, 2022

I am still working on a solution.

@jmciver
Copy link
Contributor

jmciver commented May 11, 2022

Apologies, I was not aware that pushes to my forked repository would cause notifications on this ticket.

I am currently developing associated test cases for the solution.

@jmciver
Copy link
Contributor

jmciver commented May 17, 2022

Phabricator differential: https://reviews.llvm.org/D125717

jmciver added a commit that referenced this issue Jun 9, 2023
@jmciver
[InstCombine][NFC] Add tests pre-implementation of issue #54856
ea868d5 
Provide both positive and negative testing using scalar and vector values for
issue #54856.

Reviewed By: goldstein.w.n

Differential Revision: https://reviews.llvm.org/D143044
jmciver added a commit that referenced this issue Jun 9, 2023
@jmciver
[InstCombine] Optimize and of icmps with power-of-2 and contiguous masks
1001f90 
Add an instance combine optimization for expressions of the form:

(%arg u< C1) & ((%arg & C2) != C2) -> %arg u< C2

Where C1 is a power-of-2 and C2 is a contiguous mask starting 1 bit below
C1. This commit resolves GitHub missed-optimization issue #54856.

Validation of scalar tests:
  - https://alive2.llvm.org/ce/z/JfKjiU
  - https://alive2.llvm.org/ce/z/AruHY_
  - https://alive2.llvm.org/ce/z/JAiR6t
  - https://alive2.llvm.org/ce/z/S2X2e5
  - https://alive2.llvm.org/ce/z/4cycdE
  - https://alive2.llvm.org/ce/z/NcDiLP

Validation of vector tests:
  - https://alive2.llvm.org/ce/z/ABY6tE
  - https://alive2.llvm.org/ce/z/BTJi3s
  - https://alive2.llvm.org/ce/z/3BKWpu
  - https://alive2.llvm.org/ce/z/RrAbkj
  - https://alive2.llvm.org/ce/z/nM6fsN

Reviewed By: goldstein.w.n

Differential Revision: https://reviews.llvm.org/D125717
@erikdesjardins
Copy link
Member Author

Fixed in 1001f90

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jmciver jmciver

Labels
confirmed Verified by a second party llvm:instcombine missed-optimization
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@fhahn @RKSimon @jmciver @erikdesjardins @EugeneZelenko