Removing trailing zeros of a NonZero

[leonardo-m]

If a u8 or u64 is non zero, then removing all its trailing zeros should still always produce a non zero value. It seems LLVM isn't able to see that:

use std::num::NonZero;

#[inline(never)]
pub fn remove_trailing_zeros(x: NonZero<u8>) -> NonZero<u8> {
    NonZero::new(x.get() >> x.trailing_zeros()).unwrap()
}

fn main() {
    for i in 1_u8 ..= 255 {
        let nzi = NonZero::new(i).unwrap();
        println!("{:?}", remove_trailing_zeros(nzi));
    }
}

rustc 1.87.0-nightly (6650252 2025-03-11) generates:

remove_trailing_zeros:
        tzcnt   rax, rdi
        shrx    rax, rdi, rax
        test    rax, rax
        je      .LBB0_2
        ret
.LBB0_2:
        push    rax
        lea     rdi, [rip + .Lanon.3bf69852bd0f87f34a431b46baed8d35.1]
        call    qword ptr [rip + core::option::unwrap_failed::h2026bc009ac871c4@GOTPCREL]

I'd like rustc to remove the unwrap_failed test, or perhaps better to add NonZero::remove_trailing_zeros methods.

[saethlin]

alive2 says optimizing out the check is valid: https://alive2.llvm.org/ce/z/iEL2Bb

[scottmcm]

It seems LLVM isn't able to see that:

Have you filed a bug asking them to handle that case?

I don't think rust adding new APIs for "remove trailing zeros" and "remove leading zeros" and ... is a sustainable model.

[leonardo-m]

Have you filed a bug asking them to handle that case?

Not yet. (LLVM devs are quite good about similar things).

I don't think rust adding new APIs for "remove trailing zeros" and "remove leading zeros" and ... is a sustainable model.

Yes, I understand. But I don't know what "remove leading zeros" could be used for. (Most things I've asked in ten years of Rust and its std lib have being added. Perhaps some bigger entity will ask for this function too).

[workingjubilee]

@leonardo-m It's very difficult to keep track of random API requests on the rust issue tracker anymore, because we are well into the 6-digit issues now, and we have changed the process for adding such things, so it is increasingly unlikely that any such requests you make will be acted on.

[nikic]

Upstream issue: llvm/llvm-project#131444

[leonardo-m]

For future persons that find this issue I think it could be useful to add an use case:

use std::num::NonZero;

fn jacobi_u64(mut a: u64, mut nzm: NonZero<u64>) -> i32 {
    let mut t = 1;
    a %= nzm;

    while let Some(nza) = NonZero::new(a) {
        let nt = nza.trailing_zeros();
        // Safety: removing all the trailing zeros of a
        // non zero value always produce a non zero value.
        let mut nza = unsafe { NonZero::new_unchecked(nza.get() >> nt) };

        if ((nzm.get() & 0b_111) == 0b_011 || (nzm.get() & 0b_111) == 0b_101)
            && (nt & 0b_1) == 0b_1 {
            t = -t;
        }
        (nza, nzm) = (nzm, nza);
        if (nza.get() & 0b_11) == 0b_11 && (nzm.get() & 0b_11) == 0b_11 {
            t = -t;
        }
        a = nza.get() % nzm;
    }

    if nzm.get() == 1 { t } else { 0 }
}

(https://en.wikipedia.org/wiki/Legendre_symbol ).