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 fold: umax(x *nuw 2, x + 1) => x == 0 ? 1 : x *nuw 2 #122388

Open
Kmeakin opened this issue Jan 9, 2025 · 5 comments · May be fixed by #123468
Open

[InstCombine] Missed fold: umax(x *nuw 2, x + 1) => x == 0 ? 1 : x *nuw 2 #122388

Kmeakin opened this issue Jan 9, 2025 · 5 comments · May be fixed by #123468
Assignees
@Ruhung
Labels
llvm:instcombine missed-optimization

Comments

@Kmeakin
Copy link
Contributor

Kmeakin commented Jan 9, 2025

https://godbolt.org/z/TEzxx8vbj

#[inline(never)]
pub unsafe fn src(x: usize) -> usize {
    std::cmp::max(x.unchecked_mul(2), x + 1)
}

#[inline(never)]
pub unsafe fn tgt(x: usize) -> usize {
    match x {
        0 => 1,
        _ => x.unchecked_mul(2),
    }
}

https://alive2.llvm.org/ce/z/ijq6ZJ

define noundef i64 @src(i64 noundef %x) {
  %x2 = shl nuw i64 %x, 1
  %x1 = add i64 %x, 1
  %max = tail call noundef i64 @llvm.umax.i64(i64 %x2, i64 %x1)
  ret i64 %max
}

define noundef range(i64 1, 0) i64 @tgt(i64 noundef %x) {
  %eq = icmp eq i64 %x, 0
  %x2 = shl nuw i64 %x, 1
  %max = select i1 %eq, i64 1, i64 %x2
  ret i64 %max
}
@Kmeakin
Copy link
Contributor Author

Kmeakin commented Jan 10, 2025

This also applies for saturating mul:

https://godbolt.org/z/WPKohs7hT

#[inline(never)]
pub unsafe fn src1(x: usize) -> usize {
    std::cmp::max(x.saturating_mul(2), x + 1)
}

#[inline(never)]
pub unsafe fn tgt1(x: usize) -> usize {
    match x {
        0 => 1,
        _ => x.saturating_mul(2),
    }
}
define noundef i64 @src(i64 noundef %x) {
  %_6.0 = shl nuw i64 %x, 1
  %_6.1.inv = icmp sgt i64 %x, -1
  %_2.sroa.0.0 = select i1 %_6.1.inv, i64 %_6.0, i64 -1
  %_3 = add i64 %x, 1
  %_0.sroa.0.0.sroa.speculated.i = tail call noundef i64 @llvm.umax.i64(i64 %_2.sroa.0.0, i64 %_3)
  ret i64 %_0.sroa.0.0.sroa.speculated.i
}

define noundef i64 @tgt(i64 noundef %x) unnamed_addr #0 {
  %z = icmp eq i64 %x, 0
  %_4.0 = shl nuw i64 %x, 1
  %_4.1.inv = icmp sgt i64 %x, -1
  %spec.select = select i1 %_4.1.inv, i64 %_4.0, i64 -1
  %_0.sroa.0.0 = select i1 %z, i64 1, i64 %spec.select
  ret i64 %_0.sroa.0.0
}

https://alive2.llvm.org/ce/z/AGAfbc

@nikic
Copy link
Contributor

nikic commented Jan 10, 2025

Where does this pattern occur?

@Kmeakin
Copy link
Contributor Author

Kmeakin commented Jan 10, 2025

Where does this pattern occur?

In the exponential growth calculation for Rust's Vec type: https://github.com/rust-lang/rust/blob/master/library/alloc/src/raw_vec.rs#L653

@dtcxzyw
Copy link
Member

dtcxzyw commented Jan 10, 2025

Another pattern x + umax(x, 1) exists in libstdc++: https://github.com/gcc-mirror/gcc/blob/86175a64f167e3b1701132fa1684d76230054c36/libstdc%2B%2B-v3/include/bits/stl_vector.h#L2105

@Ruhung
Copy link
Contributor

Ruhung commented Jan 11, 2025

Hi, I'm new to LLVM, and I'm interested in this issue. Could you assign it to me? Thank you. :)

@Ruhung Ruhung linked a pull request Jan 18, 2025 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Ruhung Ruhung

Labels
llvm:instcombine missed-optimization
Projects
None yet
Milestone
No milestone
4 participants
@nikic @dtcxzyw @Kmeakin @Ruhung