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

    <tr>
        <th>Summary</th>
        <td>
            Failure to optimize `udiv`/`urem` when non-constant divisor is known power of two
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            missed-optimization
      </td>
    </tr>

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

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

<pre>
    Strength reduction can be performed on `udiv`/`urem` if the divisor is known to be a power of two, due to dominating condition or assume:

Compiler explorer: https://godbolt.org/z/4ncnjsPTM
Alive proof: https://alive2.llvm.org/ce/z/3FJYeg
```rust

#![feature(core_intrinsics)]

use std::hint::assert_unchecked as assume;
use std::intrinsics::unchecked_div;
use std::intrinsics::unchecked_rem;

#[no_mangle]
pub fn src_udiv_if(x: u32, y: u32) -> u32 {
    if y.is_power_of_two() {
        unsafe { unchecked_div(x, y) }
    } else {
        0
 }
}

#[no_mangle]
pub fn tgt_udiv_if(x: u32, y: u32) -> u32 {
 if y.is_power_of_two() {
        x >> y.trailing_zeros()
    } else {
        0
    }
}

#[no_mangle]
pub fn src_udiv_assume(x: u32, y: u32) -> u32 {
    unsafe {
 assume(y.is_power_of_two());
        unchecked_div(x, y)
 }
}

#[no_mangle]
pub fn tgt_udiv_assume(x: u32, y: u32) -> u32 {
    unsafe {
        assume(y.is_power_of_two());
        x >> y.trailing_zeros()
    }
}

#[no_mangle]
pub fn src_urem_if(x: u32, y: u32) -> u32 {
    if y.is_power_of_two() {
        unsafe { unchecked_rem(x, y) }
    } else {
        0
 }
}

#[no_mangle]
pub fn tgt_urem_if(x: u32, y: u32) -> u32 {
 if y.is_power_of_two() {
        x & (y - 1)
    } else {
 0
    }
}

#[no_mangle]
pub fn src_urem_assume(x: u32, y: u32) -> u32 {
    unsafe {
        assume(y.is_power_of_two());
 unchecked_rem(x, y)
    }
}

#[no_mangle]
pub fn tgt_urem_assume(x: u32, y: u32) -> u32 {
    unsafe {
 assume(y.is_power_of_two());
        x & (y - 1)
    }
}
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzEVk2PqzYb_TVm8yiRsSEJCxYzN5fF-6pSpXbTFTLwAL4DNvJH5uPXVyZcMvdOp23SkQahxAafYx-fx-gIa2WnEHOS3pP0GAnvem3y_48oHqSKKt085785g6pzPRhsfO2kVlALBRXChKbVZsQGtAKyo76RJ7KjhBWhY3AkOwqyBdcjNPIkrTYgLTwo_ajA6UAhYNKPaEC34B41YV-g8RjeNXqUSjipOqi1auQ8rzYgrPUjEn5H6JHQ5feLHic5oAF8mgZt0BB-B71zkw0DWUFY0emm0oPbatMRVrwQViSqVt_sr7__cua4G-QJYTJat2_RIrxk22E4jQtDjQsNL_73B3bLanb0fBtv3esFEsYJi0l636Jw3iBhh1obLKVyRiora0tYRtLja4y3CNY1YQ38rpfKnVvCWjSu9KrusX7ABoRdN-X-L5Cvppj7K7AMbl0JCZ5-h1yUpfdKl6NQ3YCrhslX0Cqwpi5DWZSyJezwFHbWcxZ8fl7bGWwI_xraQPYLOQCEynneSlvOFVLqtpwr5BAAP4wLl1dWtBiew48Cw6TzbDPqeEGR_RFwsPiWiy7ddfil8W8ku87dJvkavU9A-NdA8bx1RshBqq58QaPtGXCNzPOgW5Su5i71d63BF9OWZyvPO_sQbv7G-Xfs_iAXP0rbct0i8Rqzb_bR4PgphzR8Uj7pkN4i-cpDynYQvIYNxP90LD_oPAZRn1mz7zr7n-Wtnn3m5-bvPf1Z1vc8EDU5bzKeiQjzeM9jnh4ymkZ93iaHHSb7ivIsqSgTcXao6J7yNEuqpDkkkcwZZUkcxzGLaZykW76rmn1F66xqecJaRhKKo5DDGk4iaa3HPI7T_W4fDaLCwc75jrFRWovNRk9OjvJFhExFGAvBz-QBvql8Z0lCB2mdvRA66QbMCyEHb-ZwthDgu6HvsUcFSqtNrZV1Qrm3-e917ou8GfKf8pp0va-2tR4JK8JKlr_NZPQ3rB1hxazTElYsUk85-zMAAP__EtAKeQ">