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

    <tr>
        <th>Summary</th>
        <td>
            [LoopInterchange] Interchange potentially breaks the program correctness
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          kasuga-fj
      </td>
    </tr>
</table>

<pre>
    In the following program, LoopInterchange incorrectly interchanges the innermost two loops.

```c
#define N 4
int a[N*N][N*N][N*N];
void f() {
  for (int i = 0; i < N; i++)
    for (int j = 1; j < 2*N; j++)
      for (int k = 1; k < 2*N; k++)
        a[2*i][k+1][j-1] -= a[i+N-1][k][j];
}
```

See also: https://godbolt.org/z/rfev9drn7 

Note that the current LoopInterchange interchanges these loops twice, therefore the order returns to the original one. So this case works fine.

The problem here is that the LoopInterchange regards `Dependence::DVEntry::LE` as '<'. As a result, the direction vector becomes `[< < >]`. Swapping the innermost loops changes this to `[< > <]`, which passes the legality check. In fact, we must also consider the direction vector such as `[= < >]`.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJx0VE2v6ygM_TVkYzUipOnHIov2tpWu9NTNHc2eECehJRABadX59SNI3vS2c59EFIN8DvaxDXdOthqxJMWeFIeEj74ztrxyN7Z80VySytSP8lOD7xAao5S5S93CYE1reU_YB_wyZvjUHq3ouG4RpBbGWhRePUA-z11kkFqj7Y3z4O8GlDGDSwndhbWi0xJhw_IaG6kRzrAkdCe1B06K_Zmw3ZkUhz-Y-Z7Q3c3IGhrCNoRtgazDEUBjLBC2CTwSSH4ASvJ9ND_gHE3C9nFto_8L4hIRWXC7RASLF4btO-oFd33irq-46_9xEBMMHnLKKvhkk3lZBAMWgS54hWDPi-y33-TznwBkffiu5yTvFyJw5QzJd9B5PziS7wg7EXZqTV0Z5VNjW8JO_xB2sg3etrXVa5iwZ-MRfMd9LKEYrUXtf6j7a60dTvUFf5cCQ6f4Di02xmLkMbZGCxb9aLUDb-ZD2UrNFRiNKXyFQ-lAcIdwN_bqIDTF3DF_dRj6sFLYQ2AG6Z5RvkdnseW2dkBW9IAD6hq1wKBBvjv8fdTePqbNryNZUeAOCFuT_IOwdQo7BxwsulH5OQ2oZehwaTTcUHhjoUJheoz8YZLyD5i-YyjLiqbwdefDEEbndQwmiZ6yySjFd5ZjYJpYwu33TooOBu7cPFIKW66kf4DoUFxT-NTQcBEjvSP0o_Ox8CCMdjJI_mP8bhRdTHu--fAWf1KXeb3NtzzBMlvn62JJt0WRdOVyU4gKi6JhLKtpLbJmmWXrFTZY5XSzyRJZMsoKmjGW0awoinS1ZDTDVb4ptllOBSNLij2XKlXq1oc2TKRzI5YZy7eMJopXqNzv98mWwWtRja0jS6qk8-6J89Kr-JK9VT8Mz_dmGIxH7SVX6gGVRX6dlJwfNZjfL43OJaNV5du8SN-NVSpMT9gpXD3_FoM1FwzCn2L8jrDTnMKtZP8GAAD__6MwpY0">