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.

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

Implementing <= via 3-way comparison doesn't optimize down #59666

Closed
scottmcm opened this issue Dec 23, 2022 · 1 comment
Closed

Implementing <= via 3-way comparison doesn't optimize down #59666

scottmcm opened this issue Dec 23, 2022 · 1 comment

Comments

@scottmcm
Copy link

I ended up here from code doing essentially a spaceship operator, then comparing against zero: ((a > b) - (a < b)) <= 0.

That could optimize away: https://alive2.llvm.org/ce/z/_jFfvV

define i1 @src(i16 %0, i16 %1) noundef {
%start:
  %_8.i.i.i = icmp ult i16 %0, %1
  %_7.neg.i.i.i = sext i1 %_8.i.i.i to i8
  %_12.i.i.i = icmp ugt i16 %0, %1
  %_11.i.i.i = zext i1 %_12.i.i.i to i8
  %2 = add nsw i8 %_7.neg.i.i.i, %_11.i.i.i
  %3 = icmp slt i8 %2, 1
  ret i1 %3
}
=>
define i1 @tgt(i16 %0, i16 %1) noundef {
%start:
  %x = icmp ule i16 %0, %1
  ret i1 %x
}
Transformation seems to be correct!

But today it doesn't: https://llvm.godbolt.org/z/WerxaczEc


Original Rust repro: https://rust.godbolt.org/z/n6b5KWWhG

pub fn spaceship(x: i16, y: i16) -> i8 {
    (x > y) as i8 - (x < y) as i8
}

pub fn check_lt(x: i16, y: i16) -> bool {
    spaceship(x, y) < 0
}
pub fn check_le(x: i16, y: i16) -> bool {
    spaceship(x, y) <= 0
}
pub fn check_gt(x: i16, y: i16) -> bool {
    spaceship(x, y) > 0
}
pub fn check_ge(x: i16, y: i16) -> bool {
    spaceship(x, y) >= 0
}

Interestingly, check_lt and check_ge both optimize down to a single icmp, exactly as hoped. But neither check_le nor check_gt does.

@bcl5980
Copy link
Contributor

bcl5980 commented Feb 6, 2023

Candidate patch:
https://reviews.llvm.org/D143373

CarlosAlbertoEnciso pushed a commit to SNSystems/llvm-debuginfo-analyzer that referenced this issue Feb 15, 2023
For the pattern `(zext i1 X) + (sext i1 Y)`, the constant range is [-1, 1].
We can simplify the pattern by logical operations. Like:

```
    (zext i1 X) + (sext i1 Y) == -1 -->  ~X & Y
    (zext i1 X) + (sext i1 Y) == 0  --> ~(X ^ Y)
    (zext i1 X) + (sext i1 Y) == 1 --> X & ~Y
```
And other predicates can the combination of these results:

```
    (zext i1 X) + (sext i1 Y)) != -1 --> X | ~Y
    (zext i1 X) + (sext i1 Y)) s> -1 --> X | ~Y
    (zext i1 X) + (sext i1 Y)) u< -1 --> X | ~Y
    (zext i1 X) + (sext i1 Y)) s> 0 --> X & ~Y
    (zext i1 X) + (sext i1 Y)) s< 0 --> ~X & Y
    (zext i1 X) + (sext i1 Y)) != 1 --> ~X | Y
    (zext i1 X) + (sext i1 Y)) s< 1 --> ~X | Y
    (zext i1 X) + (sext i1 Y)) u> 1 --> ~X & Y
```

All alive proofs:
https://alive2.llvm.org/ce/z/KmgDpF
https://alive2.llvm.org/ce/z/fLwWa9
https://alive2.llvm.org/ce/z/ZKQn2P

Fix: llvm/llvm-project#59666

Reviewed By: spatel

Differential Revision: https://reviews.llvm.org/D143373
veselypeta pushed a commit to veselypeta/cherillvm that referenced this issue Aug 12, 2024
For the pattern `(zext i1 X) + (sext i1 Y)`, the constant range is [-1, 1].
We can simplify the pattern by logical operations. Like:

```
    (zext i1 X) + (sext i1 Y) == -1 -->  ~X & Y
    (zext i1 X) + (sext i1 Y) == 0  --> ~(X ^ Y)
    (zext i1 X) + (sext i1 Y) == 1 --> X & ~Y
```
And other predicates can the combination of these results:

```
    (zext i1 X) + (sext i1 Y)) != -1 --> X | ~Y
    (zext i1 X) + (sext i1 Y)) s> -1 --> X | ~Y
    (zext i1 X) + (sext i1 Y)) u< -1 --> X | ~Y
    (zext i1 X) + (sext i1 Y)) s> 0 --> X & ~Y
    (zext i1 X) + (sext i1 Y)) s< 0 --> ~X & Y
    (zext i1 X) + (sext i1 Y)) != 1 --> ~X | Y
    (zext i1 X) + (sext i1 Y)) s< 1 --> ~X | Y
    (zext i1 X) + (sext i1 Y)) u> 1 --> ~X & Y
```

All alive proofs:
https://alive2.llvm.org/ce/z/KmgDpF
https://alive2.llvm.org/ce/z/fLwWa9
https://alive2.llvm.org/ce/z/ZKQn2P

Fix: llvm/llvm-project#59666

Reviewed By: spatel

Differential Revision: https://reviews.llvm.org/D143373
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants