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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Missing optimization: fold `div(v, a) * b + rem(v, a)` to `div(v, a) * (b - a) + v`
        </td>
    </tr>

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

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

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

<pre>
    Alive2 proof: https://alive2.llvm.org/ce/z/7SnGmc

### Description:

```llvm
define i32 @src(i32 noundef %val) {
entry:
  %div = udiv i32 %val, 10
  %shl = shl i32 %div, 4
 %rem = urem i32 %val, 10
  %add = or disjoint i32 %shl, %rem
  ret i32 %add
}
```
can be folded to:
```llvm
define i32 @tgt(i32 noundef %val) {
entry:
  %div = udiv i32 %val, 10
  %reass.mul = mul nuw i32 %div, 6
  %i = add i32 %reass.mul, %val
  ret i32 %i
}
```
This is a simple example. `or disjoint` can be replaced with `add nsw nuw`, `shl 4` can be replaced with equivalent `mul 16`, and constants here can be replaced with other simple constants: https://alive2.llvm.org/ce/z/qmYLyJ
I don't replace constants with arguments because I haven't figure out completetly what condition is needed for this fold yet.

### Real-world motivation

This snippet of IR is derived from [linux/lib/bcd.c](https://github.com/torvalds/linux/blob/master/lib/bcd.c#L11C17-L11C17) (after O3 pipeline).
The example above is a reduced version. If you're interested in the original suboptimal IR and optimal IR, see also:https://godbolt.org/z/hra9qYbY7

**Let me know if you can confirm that it's an optimization opportunity, thanks.**
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy0VU1v4zYQ_TX0ZRBDor7sgw9JDBcptiiw7aE5UuLYml2KVEhKXu-vL0ayHSfdTdFDAcE0xTePwzePIxUCHSziRhQPotgu1BBb5zd_PbanRe30aXNvaEQJvXduL7J7aGPsg8juhdwJuVPT6tKYsVs6fxBy16CQu-9C7qo_7C9dI5KtSO7PvzKbH9hiaDz1kZxlqltMmcwPU86vNO7JIlAmQeRJ8I2QK55YN1iNexCyGJURcg2iephD0EZ_ujIDQzSNILItDPxn4jqHPUKa3OBCayYcj2eYppFh-RklZOGxm8n4zwdkSusJ5zxoCl8c2XiBh3aCz2SXEI_XdaX1WZFq-06aedooCzXC3hmNGqJ7FfLfJIyH-L9K6FGFsOyGWUge7XB8J2Z5g6cJx1qdMVeCs0K8yT8Voo_1-bOlABRAQaCuNwj4TfG4BFEmNwURZQJnLT32RjWo4UixZRjnZMOR82dezqZM2Bn5T6PwZaBRGbSRsXz4tDzHKquhcTZEZWOAFj3-mMLFFv0l62vAf7p8L93zp9OvsxBPoJ0VsoqXbW6SmPZT_jB0yNMaGzUEhCdo1Yhz0J4Og0dwQ4TGcUoRoznBsVX8wmriW8xCW0R24t55iKw9OxNOGJc_7gGfUZm7o_NGQ-cijWrqBjfQqYDBUt9jBLeHp8-8i0ZPI2_jXQeieDBkh29C7gzVQu7qRi8bUWyFXL3V6kCxHepl4zohd9H5URkdprA5vDaO4zsVIvp3dDL7lKaPaXU3D9M1kSu1j-jh9wx66tGQRSHXy0vmV7eBqt2Isw896oGLPKIP5OwSnvZwcoOQlUcgG9FjiKiBLMQWwXk6kFUGwlC7PlKnDGvALnqdsq8CIigTuAO8O7TTtTPxbA72RevV-uW5fq7e1oSfTxihQ_hq3RFoSmxyZ-PsnnwHketNUcgqgLJzBvR9Khq4vnc-DpbiifOJrbJfw3KmXehNptfZWi1wk1ZJluaFzKtFu5G4qvNMrXFfFlIWWbZq8lVVpVhXldLpekEbmcgslTJNqiJPqmVZq6RIFJbNGnOFucgT7BSZ6w1YUAgDbqoylauFUTWaMH3XpLR4hGlRSMmfOb_hmLt6OASRJ4ZCDK8skaKZPohPNsRH19Vc3GILv1EIZA9vzs63cjK6KJOpta2m9qZmk9xDDUI-ALf4mxVuHtH9LETIVQ13l_kDjKJMFoM3mw8cPbX6ebjrvfuCTRRyN52YXT4p8ncAAAD__xFFYu4">