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

[Kmeakin]

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]

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]

Where does this pattern occur?

[Kmeakin]

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]

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]

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