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

    <tr>
        <th>Summary</th>
        <td>
            `reassociate` creates loop dependent variables and defeats `licm`
        </td>
    </tr>

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

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

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

<pre>
    I stumbled on a case where the reassociate pass is actively making the generated code worse.
In a nutshell, reassociate turns loop invariant computations into loop variant ones and licm is not able to hoist them back.

I haven't dug why, maybe reassociate is tweaked to form cse'able expressions / reduce the total number of instructions but the overall runtime is going to be worse in this case.

To reproduce:
```
opt -S -passes='reassociate' repro_reassoc_defeats_licm.ll -o -
```

Result:
Before reassociate we have:
- 2 loop invariant adds
- 1 loop variant shift
- 3 loop variant adds

After reassociate we have:
- 0 loop invariant adds
- 1 loop variant shift
- 5 loop variant adds (of which 1 is cse'able)

So accounting for `cse` (`-passes=reassociate,early-cse`), we would trade 2 loop invariant adds + 3 loop variant adds with 4 loop variant adds.

Before:
```
define void @reassoc_defeats_licm(i64 %inv1, i64 %inv2, i64 %inv3) {
bb:
 %inv4 = add nuw nsw i64 %inv1, %inv2
  %inv5 = add nuw nsw i64 %inv2, %inv3
  br label %bb214

bb214: ; preds = %bb214, %bb
  %iv1 = phi i64 [ %iv2, %bb214 ], [ 0, %bb ]
  %iv2 = phi i64 [ %iv2_plus_1, %bb214 ], [ 1, %bb ]
 %loop_dependent = shl nuw nsw i64 %iv1, 13
  %loop_dependent2 = add nsw i64 %inv4, %loop_dependent
  call void @keep_alive(i64 %loop_dependent2)
  %loop_dependent3 = add i64 %inv5, %loop_dependent
 call void @keep_alive(i64 %loop_dependent3)
  %iv2_plus_1 = add i64 %iv2, 1
  br label %bb214
}

declare void @keep_alive(i64)
```

After (with cse):
```
define void @reassoc_defeats_licm(i64 %inv1, i64 %inv2, i64 %inv3) {
bb:
  br label %bb214

bb214:                                            ; preds = %bb214, %bb
  %iv1 = phi i64 [ %iv2, %bb214 ], [ 0, %bb ]
  %iv2 = phi i64 [ %iv2_plus_1, %bb214 ], [ 1, %bb ]
  %loop_dependent = shl nuw nsw i64 %iv1, 13
  %inv4 = add i64 %loop_dependent, %inv2
 %loop_dependent2 = add i64 %inv4, %inv1
  call void @keep_alive(i64 %loop_dependent2)
  %loop_dependent3 = add i64 %inv4, %inv3
  call void @keep_alive(i64 %loop_dependent3)
  %iv2_plus_1 = add i64 %iv2, 1
  br label %bb214
}

declare void @keep_alive(i64)
```

[repro_reassoc_defeats_licm.ll.txt](https://github.com/llvm/llvm-project/files/10994658/repro_reassoc_defeats_licm.ll.txt)
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzcV02P4jgQ_TXmUgI5zgdw4DAMQprrzt6R41SItx07azsw_e9XdoCQge7e3pV2pWm1guwqv3p-9aGEOyePGnFD8i3JdzPe-8bYzZ_CKNOW6GelqV4338D5vi0VVmA0cBDcIZwbtAi-QbDInTNCco_QcedAOuDCyxOqV2j5i9TH6HdEjZZ7rECYCuFsrMMFoTtCv3wLsLr3rkGlCPs6wfS91Q6UMR1IfeJWcu1BmLbrPffSaAdSezM4XM1GowOuK1BStIGQNh54qRC8gcZI5wOlFkouXi4cLkyg4SfUhC09VP0Rzs1r4NPy13J6U-nAn5G_YBUga2NbEA4JW8Yo-KOz6FxkR9geLFa9GOTyxnMFum9LtGBqkNp524vhJmUfiYE5oeVKge21l22MdjRRSAPlRTuQGnwjXczH5BK_G7DYWRNikvSySQp6-Y9L03mYf4d5yBg6ku4IW97dj7DlgHG4bB4qrJF7dwiKLpSCuYH5U-Th-Ru6Xvlb9C3Wxk4VPGPU-uYyB_ZzlnlVuasxmWbYNbL2V1s6tY3HhueX2qP9IDb9p7Hzx9hA2MrUcG6kaCAJyRtLg7D1PbXvBrgQJqRZH0MZASlo8C5oQCEFHTM0Sc9X5Fa9zgfXAMq-hludTa8q8JZX-FxOIGz7TC84S99A9miYVNaQxrdqqsJaaoSTkRWQjD6rHMJWssiAsFzqUxJIj0s2XaaErYEstwN2Wd6iXuwZkHQXKILuz6DdGX5CvqIOhy7L_J1TbDyVXk-VFhQvUYX9smRJdi_HsJF-AZJuobMY5E13o-sAV5b3FE5J9OkaOUTOt8M2u3mzJGzv4jrfAr0Z4u49FHsD6tCp3h2StxCTZ4iE5SH3hwo71BVqH7Fdox6EGtRN0jsq05Ns1Hii71WQqfcVRoSBd62dF8TuwJU84VgxPwW5ddITBumNwRg9fy_6J4On0-Cj5A9xh7wmH5XTcndfVxUKxS2-SWgcIs9G7zDuCFvFlo6jZ_1_t-zf7KNP_P0CLffvem4yAp9W6eMQfKdVH9s0pvs_as7syej9lXqS5Nt3X6cW_oeP5bJqvO9caBy2J2x_lL7py4UwLWF7pU7Xn3lnzR8oPGH7Wip0hO0Tul5nRb4ibP9xKLaeVZu0WqdrPsNNUixX6zWjxWrWbKq8Tos8o5TyNBNUCJ4lZV0mebFOlqt0OZMbRllK06RIVllCVwuBqShSvkzTWlBKkWQUWy7VIjBdGHucSed63BRJlq9mUWsXPzkY03iGaCSMhS8Qu4m3K_ujIxlV0nk3onjpFW5IQe_fhAoKwiL3ePlGGHspvsWU6vIlcFEhvF_FqVbQWW_V5tNyR7ZB73ibvwIAAP__ay_vtA">