Missed optimization for .rem_euclid(2^n) on signed integer types.

[LFS6502]

When calling .rem_euclid(n) on a signed integer type, it fails to apply the optimization for powers of 2, where it should do a bitwise AND operation instead.

Missed optimization

pub fn rem(n: i32) -> i32 {
    n.rem_euclid(2)
}

example::rem:
        mov     eax, edi
        shr     eax, 31
        add     eax, edi
        and     eax, -2
        sub     edi, eax
        mov     eax, 1
        cmovns  eax, edi
        ret

How it should be optimized

pub fn rem(n: i32) -> i32 {
    n & 1
}

example::rem:
        mov     eax, edi
        and     eax, 1
        ret

Testing the optimization:

n = 2

?play

let mut passed = true;
for i in (std::i16::MIN..=std::i16::MAX) {
    if (i&1) != (i.rem_euclid(2)) {
        passed = false;
        break
    }
}
println!("{passed}");

true

n = 1

?play

let mut passed = true;
for i in (std::i16::MIN..=std::i16::MAX) {
    if (i&0) != (i.rem_euclid(1)) {
        passed = false;
        break
    }
}
println!("{passed}");

true

n = 4

?play

let mut passed = true;
for i in (std::i16::MIN..=std::i16::MAX) {
    if (i&3) != (i.rem_euclid(4)) {
        passed = false;
        break
    }
}
println!("{passed}");

true

---

Curiously, the optimization is applied to unsigned integers just fine

pub fn rem(n: u32) -> u32 {
    n.rem_euclid(2) 
}

example::rem:
        mov     eax, edi
        and     eax, 1
        ret

[nikic]

If you are going to file an upstream issue yourself, please do link back to it so other people don't do duplicate work: llvm/llvm-project#66417

Anyway, this issue should already be fixed in LLVM 18.

[fmease]

As an aside, the title should be 2^n (powers of two) instead of n^2 (squares).

[LFS6502]

As an aside, the title should be 2^n (powers of two) instead of n^2 (squares).

Thanks, wow, had a brainfart there.

[nikic]

Confirmed fixed by #120055, needs codegen test. Godbolt: https://rust.godbolt.org/z/cf3Ej1Mq3

[LFS6502]

Fixed in 1.78.0 (Updated to LLVM 18)