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

    <tr>
        <th>Summary</th>
        <td>
            `mul nuw`+`lshr exact` should fold to a single multiplication (when the latter is a factor)
        </td>
    </tr>

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

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

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

<pre>
    Alive for the specific example, with opt+llc: <https://alive2.llvm.org/ce/z/7oofsh>
+label: llvm:optimizations 

I tried the following:
```llvm
define i64 @src(i64 noundef %0) {
start:
  %1 = mul nuw nsw i64 %0, 52
  %2 = lshr exact i64 %1, 2
  ret i64 %2
}
```

Since `52 = 4 * 13` I expected to see that fold down to just a single `mul`:
```llvm
define i64 @tgt(i64 noundef %0) {
start:
  %1 = mul nuw nsw i64 %0, 13
  ret i64 %1
}
```

But it doesn't -- the `mul` and `lshr` are left in the optimized IR, and aren't folded by the target either:
```asm
src:                                    # @src
        imul    rax, rdi, 52
        shr     rax, 2
        ret
```

Whereas the single-multiplication version ends up not even needing an `imul`:
```asm
tgt:                                    # @tgt
        lea     rax, [rdi + 2*rdi]
        lea     rax, [rdi + 4*rax]
        ret
```

So in general, `%1 = mul nuw %0, CONST1; %2 = lshr exact %1, CONST2` should simplify to a single `mul nuw` whenever `CONST1` is a multiple of `1 << CONST2`.

In fact, it looks like this already happens in `opt` if written with `div`: <https://alive2.llvm.org/ce/z/L-VouQ>
```llvm
  %1 = mul nuw i64 %0, 52
  %2 = udiv exact i64 %1, 4
=>
  %1 = mul nuw nsw i64 %0, 13
```

So that code path just needs to take into account places where the `udiv -> lshr` transformation had already happened.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJytVttu4zYQ_Rr6hbAhU_IlD3rwpQECFC3aFO0zLY4s7tKkQFL2Zr--M5Ts2E52mwAVFMsih3M5c-Y4O6deypXRR-C18zw2wEMLla51xeGbPLQGmNjwk44Nd21kYm1MxfIVZ_mmibEN-J2JR7wlORETY46HifN7XKnw6ON3_Fs4V4eG5b-wbMuyFTmROzDkhszxia71QX-XUTsb-GCWPp949BpUyqx2xriTtnsK2tvMs_5OftKSglpb4HpecFZkwVdMLOnFus7iHmdiljHxwNli3R8IUfp48cjJYIrlbfmhM9x2J27DqXeXTm74TFyZimRqQuMJryqeLadkeTH0cNkY1thie1fCddXP2lbAcXHwTydXfJrjCn_CQNiiSKA4HgAQGxkJHMWVO1la_dKFyCUPiJVJfrAWCvFh3OI-_u-4Yfpv4Zh-BI51h_YRq4NgmVhEPh4nQlwK49IqeqM-pFcP3ECNp2wyHPiFkD39SamQOdr0zgg53Nm9JFOsao_pATIe_FvAZBjwImYhgT9wMZGfqTjU31-agMLLy2-Uk1f6ll39Rcy6srrbRSR_gts_WALI0I914sIYY0bdGl2lWeNH8IGeYFXgXYvdxtKPYLkFUHgCkSJc9Y_4c4GDCPMpOOjATSkG5HWhbLZGRNB6jTWLFaEz2370REEncPX-xM_henbElz1Y8NIkj7h_z-ozmze___b815Tl63dV4KwAyUoQJUPjOpzQoFFTdf1CU3o3oOSeLE8NZoCNoeUhCq7qgPZD95DQNe1SZhu8X8NMbrTT8hqToTxweoxzXwM3-isJBnkzyA31whvZtoCqq1OnSeQpWs1PXseITEjaj2tKH3sKfEr7fx3_7bo_XrX_rfC8oxz_obYdpvKO2hZDiHx7CfcJVfoRI5K4Vk4BbyUCkZSVhiNQB6NENLWlXlYVCmXkrZEVBOqhh7NGpXzHmBQ_61P00gb8wT30U9hIddcOUJORKnP1kD_IUdTRQHlDEiT5IHc9EFcMSz8E1-y6G3nUdWJYSs5IbLHvuUVUcR4lftR5U942eI8c6HaTyh3wJbWuf4xb774AUexRh9BBwC-zYimKUVPOYDHNclnNCwDYgYLZshAqn86my51Q1WKU_gkIJY4tE8ICtoVc4Hcc25EuRSZEVmQP2SJfZNlkXuS7LJsvazmXooYMJQQOUpsL60a-TCntun3ATaNDDK-bMgS9x76lcOhfdrFxvgyVi_FQHUYpdply_xf1pZHt">