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

    <tr>
        <th>Summary</th>
        <td>
            [LoopInterchange] Can only replace phis iff the uses are in the loop nest exit
        </td>
    </tr>

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

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

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

<pre>
    For the reproducers, see also: https://godbolt.org/z/3W6eMxsMh

For this input:

```
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128-Fn32"
target triple = "aarch64-unknown-linux-gnu"

define void @_Z1fisPi() {
entry:
 br label %for.body

for.cond.for.cond.cleanup_crit_edge.split.loopexit:
 ret void

for.body:
  %.us-phi495254 = phi i16 [ %.sroa.speculated, %for.cond1.for.cond.cleanup2_crit_edge.split ], [ 0, %entry ]
  br label %for.body3

for.cond1.for.cond.cleanup2_crit_edge.split:
  br i1 false, label %for.body, label %for.cond.for.cond.cleanup_crit_edge.split.loopexit

for.body3:
  %m.047 = phi i32 [ 0, %for.body ], [ %add20, %for.cond.cleanup15.split ]
  %0 = phi i16 [ %.us-phi495254, %for.body ], [ %.sroa.speculated, %for.cond.cleanup15.split ]
  br label %for.body16

for.cond.cleanup15.split:
  %.sroa.speculated = tail call i16 @llvm.umax.i16(i16 %0, i16 0)
  %add20 = add i32 %m.047, 1
  br i1 true, label %for.cond1.for.cond.cleanup2_crit_edge.split, label %for.body3

for.body16:
  br i1 false, label %for.body16, label %for.cond.cleanup15.split

; uselistorder directives
  uselistorder i16 %.sroa.speculated, { 1, 0 }
}

declare i16 @llvm.umax.i16(i16, i16) #0

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }
```

Compile with:

```
-S -passes=loop-interchange --disable-output -loop-interchange-profitabilities=ignore
```

to run into this assert:

```
opt: /root/llvm-project/llvm/lib/Transforms/Scalar/LoopInterchange.cpp:1711: void moveLCSSAPhis(llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::Loop*, llvm::LoopInfo*): Assertion `all_of(P.users(), [OuterHeader, OuterExit, IncI, InnerHeader](User *U) { return (cast<PHINode>(U)->getParent() == OuterHeader && IncI->getParent() == InnerHeader) || cast<PHINode>(U)->getParent() == OuterExit; }) && "Can only replace phis iff the uses are in the loop nest exit or " "the incoming value is defined in the inner header (it will " "dominate all loop blocks after interchanging)"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -S -passes=loop-interchange --disable-output -loop-interchange-profitabilities=ignore <source>
1.      Running pass "function(loop(loop-interchange))" on module "<source>"
2.      Running pass "loop(loop-interchange)" on function "_Z1fisPi"
```

The stack trace:

```
 #0 0x0000aaaaae8e9074 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /llvm-project/llvm/lib/Support/Unix/Signals.inc:834:11
 #1 0x0000aaaaae8e9594 PrintStackTraceSignalHandler(void*) /llvm-project/llvm/lib/Support/Unix/Signals.inc:918:1
 #2 0x0000aaaaae8e7634 llvm::sys::RunSignalHandlers() /llvm-project/llvm/lib/Support/Signals.cpp:104:5
 #3 0x0000aaaaae8e9d5c SignalHandler(int, siginfo_t*, void*) /llvm-project/llvm/lib/Support/Unix/Signals.inc:426:38
 #4 0x0000fffff7fb09d0 (linux-vdso.so.1+0x9d0)
 #5 0x0000fffff7a1f200 __pthread_kill_implementation ./nptl/pthread_kill.c:44:76
 #6 0x0000fffff79da67c gsignal ./signal/../sysdeps/posix/raise.c:27:6
 #7 0x0000fffff79c7130 abort ./stdlib/abort.c:81:7
 #8 0x0000fffff79d3fd0 __assert_fail_base ./assert/assert.c:89:7
 #9 0x0000fffff79d4040 __assert_perror_fail ./assert/assert-perr.c:31:1
#10 0x0000aaaab0fc0e24 moveLCSSAPhis(llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::BasicBlock*, llvm::Loop*, llvm::LoopInfo*) /llvm-project/llvm/lib/Transforms/Scalar/LoopInterchange.cpp:1639:5
#11 0x0000aaaab0fc0094 (anonymous namespace)::LoopInterchangeTransform::adjustLoopBranches() /llvm-project/llvm/lib/Transforms/Scalar/LoopInterchange.cpp:1808:3
#12 0x0000aaaab0fbfa70 (anonymous namespace)::LoopInterchangeTransform::adjustLoopLinks() /llvm-project/llvm/lib/Transforms/Scalar/LoopInterchange.cpp:1856:18
#13 0x0000aaaab0fb91f4 (anonymous namespace)::LoopInterchangeTransform::transform() /llvm-project/llvm/lib/Transforms/Scalar/LoopInterchange.cpp:1542:18
```
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzcWF1v2zjW_jXMDSGBoixLuvCFnNSYAp33DSYtFtgbgxIpmw1FCvxIk_31i0PJia16O-20Ayw2CGxRJM95ztfDQzPn5EELsUHFFhV3Nyz4o7Eb99kIywchPwt70xr-stkZi_1RYCtGa3johHWI3mInBGbKGZQ3-Oj96FDeILpDdHcwvDXKp8YeEN39C9Fd_o-1-P3Z_X5EpEGkmSRKh6Ueg4d98TVak_mfNJ7Zg_CYM88UezHBY5TfYUSpSAaUNyIZaUlQ3uQ0fsAwuxzC03oVPxJZobyppimZrVHexA8YvS7JKCzIaJXofNqbPMBoB0NK3zB5K0clTngYs91xvUqCftTmi06U1OE5Oegw7UGk4aKXWuAnIzlGK7L_Z9ZLdy8RrRCtMSq3iDRCe_syOQK3FivWCoURLXpjUwjCJAlGndE8fX3olGA6jPvOSr8X_CBSNyrpU2XMKJ7l7FtshY_638REodMk6EmDS8ajXNUFLVbRtPEosczWGBXbuMBZw1I3ii4o5gWHDJjxAZDsK0h0iQmj4i7uKraYzNuj2XECcFwzPL-0_Dv0nKxqLZYZ7plyArR97dLlyx_07IUr8zNfDilZlW8-zOmFyacd5-5AtGCcU7Jw6glDVpx5cFZCrgbpPIrf1vcn8fyPqq_FKFsv0nOx-TzPFmqjFZ5JhTum1GTLiij1NKRhYM8pFCut4mtaRP_AM0G0PkmMjotiGOeTt-cQwOrsLBW8DV9nwvcm1bUMyi9zIFLKd6UeGHUt-ZZ-m1gx3-LghJLOG8uFxVxa0Xn5JFxUdjE3e-pqdMstzuCBYFRCMOdPIKhOMSu-4f3Z8ZGvaE6mbcx7K9vghYsvJ0Ist1gbiGXLukesTW-FwNq4F91hbYL-IjXHJ2CsVQJ_kUpZ4YPVeBCDsS-IVtpoMZHj3eJcQKS5NcMo40Z_vHp2JA84GZlzwqH8Duo1kdoL2x2ZPgicJFw60JyY4MfgcbJckozW9NKzVirpZZQiD9pY8TUWb7ANGkvtzXSigVp7_UgzI7zHiO6sMR7RHTgadH0W3WkIX7JFdPfRMu16YweH6O6hY4pZRHcfjBnfvwFNu3GEM6vM4OybTpjBPIkPtw8Pzf1ROkSrKDVvUN5smZPdVpnuEdEmJuB_2xSYd_Xle92bOFGDnU30sTQaozVhSu1Nj2h1nwYXWxM4Vmem-__ghf1NMC4svInDd89TOb_X3fvpW7-uAYqsPjlhMaLNp_l4xnN2Ilp1zHmU397_9v7_DBcofwfLEa0TlL87CH_PrND-dLDnd1ARZxAwomtE11HzN3acA4oIblF5i_-q6mhuvo2lFMs3QkCU3jKNjVYv0Ncp1gk4TByWfR-bveCEw5EUdBxDjWAtnMdw-GEDxgDVUpiUujOD1Af8xFQQWDo89Tz8tFuCSfh48kIlfSz7kwwOu5mHflJNmlrID4dZ74HUXjNe6kMMLkW0xD2TSvAUkeb-w7vm4R12oR2kxwy34QBWGeuxN8vmVPpjaNPODGcld1mI0rkgoO4w02BCpwIX0Y7OMnfEQG3esk6A7gcPRMfDME5FT1JE6ntrDpYNmNlDGIT2bi58oAC66yYCs4l4HpWxEOZdp5g-JOyU2S7xNuhHRHet1NNGnBgQwcYRxpG6UoeB6_4uusMov3Um2C6mG2kyMO2PoDWEGjRC7PqgO0AMVBPLt1rKjxGDoGGj8WB4gOaZ0gvhsVem1-R_S2iUeAIAi996a_o1V388CuxitGLwrnL0dJKRZ0IIYfAnKlGTcnXGR-7FTQ_3Vmofw_8xyjvnWsu-7I3zVrAhVtwtJPFUf9-k_YcwQtoiuvuk5TO8kAfNlEul7uAKk8NtJctmpNkSaVGv8ALWJOA3prmCRKviNSBS6U9iqbN4X5qh0AWUcp1fddofQV8gcifK-l4sJxDz0UfAIcUMIl_6gxcdXjogBuIWO3mQujd7Px84v8wvKxqvltWMaTVj6uGv7FtScwIUON0Tn7gzqTNphuiWPNf81NkimhcXG1nWU0Lwfj_6oxWM7x-lUns5jEoAwbBYASmiOz16hejufFkaYYGjyvUsfH0hvOZsXXb44KIhUcz0iOgujaMXx8UIlDgaF222TDoRBdMSLsuz3PJSbldmOcGsBSaOcjyffBhfxe0VtC7lvL1awMp7DjZPtLgHwt-3zIkoa-60Tg-TsPpMWL0QtiKrM2GjsNbYKPOauATmo8w8m9McCu6cG1rSd0TQ1f96y_Vn9fBDreo6r-eCBXdmS3eSegXFwbTRL4MJDms2CDdGeq3Pwb0KftU-zTL-OTgPa7aW6e4ovpNgfsiIisTfkmYj6KURbc9K8quM-CD1499iQRF_BKtmE_KFCXXW_2Qc_Ovw14MvVvQV_OnsvuGbnNd5zW7EJiuLnFRrUpY3x02Wt6QvqpZlGSE5bdf9qiJ8RdZr3tZ1Rm_khhJakJJmpKJZVqY5JSwvWy5IUZQ9a9GKiIFJlcaLsbGHm9ggbrJVXZbrm3iNd_FXVEq1-ILjLHQgxd2N3USr23BwcLOWzrs3MV56FX9-XdiJijv8M935TbBq89e73tmupw39dwAAAP__3d3cAw">