Missed optimization for 2^n euclidean division remainder operations on signed integers.

[LFS6502]

When calculating the euclidean division remainder of signed integers, there is a missed optimization. The optimization should be applied as long as the divisor is a power of 2.

Missed optimization

Rust:

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

llvmir:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define noundef i32 @_ZN7example3rem17h72c3fd79b0f51c25E(i32 noundef %n) unnamed_addr #0 {
  %r.i = srem i32 %n, 2
  %_8.i = icmp slt i32 %r.i, 0
  %spec.select.i = select i1 %_8.i, i32 1, i32 %r.i
  ret i32 %spec.select.i
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind nonlazybind willreturn memory(none) uwtable "probe-stack"="inline-asm" "target-cpu"="x86-64" }

!llvm.module.flags = !{!0, !1}
!llvm.ident = !{!2}

!0 = !{i32 8, !"PIC Level", i32 2}
!1 = !{i32 2, !"RtLibUseGOT", i32 1}
!2 = !{!"rustc version 1.74.0-nightly (8142a319e 2023-09-13)"}

Example of what the optimization should look like

Rust:

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

llvmir:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define noundef i32 @_ZN7example3rem17h72c3fd79b0f51c25E(i32 noundef %n) unnamed_addr #0 {
  %_0 = and i32 %n, 1
  ret i32 %_0
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind nonlazybind willreturn memory(none) uwtable "probe-stack"="inline-asm" "target-cpu"="x86-64" }

!llvm.module.flags = !{!0, !1}
!llvm.ident = !{!2}

!0 = !{i32 8, !"PIC Level", i32 2}
!1 = !{i32 2, !"RtLibUseGOT", i32 1}
!2 = !{!"rustc version 1.74.0-nightly (8142a319e 2023-09-13)"}

---

It is worth noting that the optimization is applied to unsigned integers just fine:

With unsigned integers

Although, I'm not sure if this is rustc doing the optimization, or if LLVM is.
Rust:

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

llvmir:

target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define noundef i32 @_ZN7example3rem17hc4f8a022f8fdbbedE(i32 noundef %n) unnamed_addr #0 {
  %_0 = and i32 %n, 1
  ret i32 %_0
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind nonlazybind willreturn memory(none) uwtable "probe-stack"="inline-asm" "target-cpu"="x86-64" }

!llvm.module.flags = !{!0, !1}
!llvm.ident = !{!2}

!0 = !{i32 8, !"PIC Level", i32 2}
!1 = !{i32 2, !"RtLibUseGOT", i32 1}
!2 = !{!"rustc version 1.74.0-nightly (8142a319e 2023-09-13)"}

[nikic]

The general pattern is already handled since LLVM 18: https://llvm.godbolt.org/z/zfGjbGns9

We do fail to handle the specific form (where one select arm has been replaced by constant 1) though: https://alive2.llvm.org/ce/z/gmJ3XL

[antoniofrighetto]

Thanks for reporting, landed a possible fix in ce5b88b. Feel free to reopen should it be incomplete.