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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Missed optimization : fold rol pattern `(a * b) >> (BW - c) | (a * (b << c))` to `fshl(a * b, a * b, c)`
        </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>
          XChy
      </td>
    </tr>
</table>

<pre>
    Alive2 proof: https://alive2.llvm.org/ce/z/E4PcTZ (use i8 to speed up SMT)

### Motivating example 

A concrete example (generalized proof is in Alive2 link):
```llvm
define i64 @src(i64 %a) {
entry:
  %mul100.i = mul i64 %a, -8663945395140668459
  %shl.i.i = mul i64 %a, 1118853283428214698
  %shr.i.i = lshr i64 %mul100.i, 63
 %or.i.i = or disjoint i64 %shr.i.i, %shl.i.i
  ret i64 %or.i.i
}
```
can be folded to:
```llvm
define i64 @tgt(i64 %a) {
entry:
  %reass.mul.i = mul i64 %a, -8663945395140668459
 %or.i.i = call i64 @llvm.fshl.i64(i64 %reass.mul.i, i64 %reass.mul.i, i64 1)
  ret i64 %or.i.i
}
```

### Real-world motivation

This snippet of IR is derived from [jemalloc/hash.h@hash](https://github.com/jemalloc/jemalloc/blob/92aa52c0625d35ca1c30e7fc913d7c92c9518f9e/include/jemalloc/internal/hash.h#L306) (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/G8YzPMYvY

**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/eJyUVU2P2zYQ_TX0ZWBDGkqydPDBa8dFgCwapAHa9EZRI4sJRQok5XT31xeU_LlAii5A2KQ4b-bxcWYovFdHQ7Rh-RPL9wsxhs66zV-77mVR2-Zls9XqRAiDs7ZlfAtdCINnfMvwwPAgpt2V1qd-Zd2R4UESw8Mrw8OH7LP8-jcwLEdPoEoIFvxA1MA4wB_PXxlWLNmzZHv-RT4PeLZBnURQ5gj0j-gHTXBvuAVpjXQU6LaN5ZEMOaHVKzUzV1AelIEzfa3MjxiQX6IVyTwi8_lTQ60yBKrIgGWJd5JhOS0wFwwrYOun2ZBMcC9XTxAN-lGnSbJSwPge-lHDDbiDZVkUvMpyXuVplhRFmeXVHdZ3eqV-AU3TtCxzjiXPsMQ0K6ryAemuSO07d4Fe2EQPBT8DGOb2Zm4dNMp_t8qEC-rsLYJurC7RHF3tZi9nGdf7N3rOSykM1ASt1Q01EOz_1z0cwzt0dyS8X_Wjfr_0j3pIofWFwpTM7SRAkd3I3MWKrn_9Nb1m9rt1e1sKX0jo5U_rdAP9uSqsuTf92ikP3qhhoAC2hY9fYt435NSJGmid7YHlT9-pF1pbyfDQCd-tOpYlccLyPcPysaKPKnRjvZK2Z3i4A95Na21rhocKhchRJgXmDc-lSCVPaN3KKuXNWlYoqzwt2yr2A2WkHht6dKNMIGeEvrFC_oknxXTpWIo2kIPfOQxqIK0MMaxWl1Pfal_U9kTx0AIcNaOkBk7kvLJmBR9beLEjw7UjmKKRD9TEthA6AuvUURmhwY-1HYLqhY76CdPAbRkv1ROB0D5m8RutbFNbHc6dLza938pvr5-fv52-Pd5nHJ8oQE_ww9ifoCZiEMtEWtMq10PoRAAVGK49CDMzUK_ThYMdBuvCaFR4iXxCJ8wPv5rdLpoNbypeiQVt0nWaJlmRFbjoNklGOYqsqEWR1EIgCVG32GCdVHUu0nShNphglnBM0zJLE1xRkSLmslqnayrqumJZQr1Q-treF8r7kTZlka7ThRY1aT-9G4hTOfOtMj5I29fTbSHDHUPslffULO8PFPfy_cJtImxZj0cfy0754G-hggp6epU-Gh92Z5_5Hp4nd4_6xHcp9hpwVsMgQswriEWFpQCGW6innOIfGP8QU-vpT1iCnJvLDq5WDMsaGN8xvpt24yiS-G6xIokN4d7fDu6mcjZdjE5v_qOcJpXmv-Xg7HeSIdZBFNUzPEy6_hsAAP__tG4zjQ">