<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/66417>66417</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Missed optimization for n^2 euclidean division remainder operations on signed integers.
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          HypheX
      </td>
    </tr>
</table>

<pre>
    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.

<details>
<summary> Failed optimization </summary>

Rust:
```rs
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)"}
```
</details>

<details>
<summary> Example of what the optimization would look like </summary>

Rust:
```rs
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)"}
```
</details>

---

It is worth noting that the optimization is applied to unsigned integers just fine:
<details> 
<summary> With unsigned integers </summary>

Although, I'm not sure if this is `rustc` doing the optimization, or if LLVM is.
Rust:
```rs
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)"}
```
</details>
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsmE1v4zYTxz8NfRlIkEayJB98yObleRbItsV22y16MShpZHFDkQJf4ng_fUHJTuwkfcEWWPQQwKBJeuY_oxH1w1jcWrFVRGu2fMeWVwvuXa_N-v_7saffFrVu9-vPPSlouGy85E6oLbiegHwjRUtcQSvuhRVagaGBC9WSAd3BpNqCUI62ZCzDy-BmCIQFDoOwllrQoxOD-Mqd0CqGTz2d7YDttZct1AR8HKWgFrgFqdU2fIckptDazJqj3s2hMWbJFUsuDmN22ZLjQlqWXT9uWT8M3OxZdg03XMhnuQDLLhnePBmdCn701rHsqF4k88fYeWP0NXRTLRhWimUXIDJkuIIoxBIZAivfzaagYkPDZq4kwyqYHVTLq2fy81LK-0GYl8HnpeNmSw5a7rjke-0dsOwKGCJFA8suKBqxTFh2keE0hGV6vgyzIp-GSBwnXRWcUqwiVYVJcfQp8ujnFCuGeBbfGTFKOsZ-qIpNkUde3Sm9U5EUyj9EW-UfveaxpU4oAqW9aqmb65Qnm99_KOmBD6OkzNCQln2JTda15apOumXa4PKaYRWMj44MlypU2yvFB2o3vG0NMMySk7IzXJpYTAlaQ8McbPK7hENSEDY21cFKNMMIVrqjpYlFsE1ObO1ITWxJUuOO0tMCRHqUCi5BID1ODkoHEUOP-mdiz0_ENHLnjKi9I3u4uFDs8h0M3rrR6K0ha0HpzlCoqaHGGxtmdq-aqVY7oVpQWkn-dV-H-U5Iach5o2CgQZt9OL5a0VTMneN1uKWIo9E1Rdbx5i7cweyKIQolhaKI24FhyB_ngxA1o3-0eaiKqMin38-vhGEaTnU86NZLijvJt_ZwdtJwyzBNQr0YpumT58FHtKTcuTG-lE9OLEKBq4MeQ_zp_SXc0j3JkOfhruBpmPSZLz75fnS3ov7F0v9-_HTifZYknufGEI23roF7MhMw07jM4yRSYts7uQeGVZXmyLN0RYAJZlGyitIsUAHxz5Awk-oF4f4Z-q7nZytAc9dzNzH1jIO7CcBS6zuQ4o6-ExcBQAHDAtI3HH4XHG7mZ4Sr9gyG6Sts2iRvQHoD0jcCKYqi0-V7Fzq3nTauB6UPreVrGAr93aEDdBq8etZcwhdvHYQn5okFp-iD19j3Wbj-Fam_ItyFdL322z7U9j3DcghZg_Whq-3A9cKGTAP0QlVZkUCrj_3y6fUE_9C1dnB7--sHEDb-NoL6E4L6t87y36G0ybuKJ4hd1bV1Te0bSt9Q-h9D6aJdZ-0qW_EFrdNilZdpucpw0YfdqqyrVVU2dVrWZUHNssMqy6tVsqp4txDrEDNZpXlaLaslxl3SFdWyKatV3lJapCxPwr93GU_F12a7ENZ6WhdFnpYLyWuSdnpFgKhoB9OPIfPl1cKsg09U-61leSKFdfZJxQknaf3h5d996LQBxZbX-DevEkYyk4MFrZ6_VYgX3sh179xoA7rwhuHNVrje13GjB4Y3IY_DVzQa_YUax_Bmyt4yvJmu7o8AAAD__zY0xj8">