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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Missed optimization for `(x * z) % (y * z) == 0` => `x % y == 0`
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:instcombine,
            missed-optimization
      </td>
    </tr>

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

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

<pre>
    `(x * z) % (y * z) == 0` => `x % y == 0` when the multiplications/modulus do not overflow:

[alive](https://alive2.llvm.org/ce/z/ylAxft)
```llvm
define dso_local i1 @src1(i8 noundef %0, i8 noundef %1, i8 noundef %2) {
  %4 = mul nuw i8 %2, %0
  %5 = mul nuw i8 %2, %1
  %6 = urem i8 %4, %5
 %7 = icmp eq i8 %6, 0
  ret i1 %7
}

define dso_local i1 @tgt1(i8 noundef %0, i8 noundef %1, i8 noundef %2) {
  %4 = urem i8 %0, %1
  %5 = icmp eq i8 %4, 0
  ret i1 %5
}

define dso_local i1 @src2(i8 noundef %0, i8 noundef %1, i8 noundef %2) {
  %4 = icmp ne i8 %1, -1
 tail call void @llvm.assume(i1 %4)
  %5 = mul nsw i8 %2, %0
  %6 = mul nsw i8 %2, %1
  %7 = srem i8 %5, %6
  %8 = icmp eq i8 %7, 0
  ret i1 %8
}


define dso_local i1 @tgt2(i8 noundef %0, i8 noundef %1, i8 noundef %2) {
  %4 = srem i8 %0, %1
  %5 = icmp eq i8 %4, 0
  ret i1 %5
}

declare void @llvm.assume(i1 noundef)
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy0ld9u4joQxp9mcmOBnAnOn4tc0OZEOjo6z7BykgG868Rs7NDSp1_ZSVuqQlcrsRICNP5lPN-X0Yy0Vu0HohLEA4gqkpM7mLH8ryf5Qw1RY7pzCSkHzJ8Z4Ja9ABYMUDDA_HwRSSpIKsYh5fP_fxik_DmQ5w-nTwcamDsQ6yft1FGrVjplBgtY96ab9GRZZ9hgHDMnGnfaPEGyBV4Bf_0WD1KrE4GoAPODc0frCawB63CAa61P_dqMe8C6JcD6BbA-6-3zzgEWS5aUzx_PzqGOdmog1lnzTZtWaqZiBhtuxzYGzFXOBjMNHe28KA74yD6G4s8hDNZkD3N-5kMbb4bXzobpyeMz9jgnfefEF1x8waWBm0bqF2izQGKBAEUWGNX2R0Y_Fyz12NuFI7mgFkW22JNVl57fsMbt3d2tuZDCr-gVV7RsbmgRf6LFji3eW0soc6ClzPDk6lWMk0qzVmrNTkZ1voLQtdLaqSdfSLxIK653hf2qe9IvuEs3586w75aLBUovoPyK5dkNy_Orlv-uie5uvP37TdRqOdLtd7dU-XneRF2ZdEVSyIjKOONJnvMsTqNDmTUJyV2etWkiimJHsmkpbpom5p3I05xHqkSOSYxYII9jka6TNkmypCnSWHDZcYINp14q_Tb_ImXtRGWWilxEWjakbZjziGHqJVs1WNeavlEDAfoGAcReWUvdyhyd6tVLGM7-TFTRWPrHVs20t16yss6-X-WU02GL_DtY97jkFBX7P6Rjl-nYzozsnkslmkZdftwEe-UOU7NuTQ9YB7Xzz-o4mu_UOsA6mOP3TvDnVwAAAP__45vj6g">