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

    <tr>
        <th>Summary</th>
        <td>
            [LoopInterchange] Incorrect exchange happens when the Levels of Dependence is less than the depth of the loop nest
        </td>
    </tr>

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

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

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

<pre>
    Input:
```c
#include <stdio.h>

float A[4][4];
float V[16];

void g(float *dst, float *src) {
  for (int j = 0; j < 4; j++)
    for (int i = 0; i < 4; i++)
      dst[i * 4 + j] = src[j * 4 + i] + A[i][j];
}

int main(void) {
  for (int i = 0; i < 16; i++) {
 A[i / 4][i % 4] = i;
    V[i] = i * i;
  }

  g(V, V);

  for (int i = 0; i < 16; i++)
    printf("V[%d]=%f\n", i, V[i]);
  return 0;
}
```

godbolt: https://godbolt.org/z/dq6Kad14a

The root cause is that the dependency matrix for the loops in `g` is `I I`, which is treated same as `= =` in legality check. An `I` dependence is used to fill a direction vector if its length is less than the depth of the loop nest.

https://github.com/llvm/llvm-project/blob/9f77c26ec641c7f0c353f74ee6ee072086e2f3d7/llvm/lib/Transforms/Scalar/LoopInterchange.cpp#L212-L214

In this case, since the alias check results in MayAlias, DependenceInfo skips the analysis and returns a default Dependence object, whose `Levels` is always 0.

https://github.com/llvm/llvm-project/blob/b712590ef4acfd9f0bea42aff695b22ca99ae5dd/llvm/lib/Analysis/DependenceAnalysis.cpp#L3605-L3609

A similar problem occurs when the dimension of arrays used in the target loops is less than the depth of the loop nest, such as in the following case

```c
float A[4][4][4];
float V[4];

void f() {
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
      for (int k = 0; k < 4; k++)
        V[i] += A[i][j][k];
}
```

godbolt: https://godbolt.org/z/Yss6oe3eb

In this case, exchanging the j- and k-loop fails because the IR structure is currently unsupported. However, it should be rejected by dependence reason, because that exchange changes the order of addition of float values.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJykVl2P6jYT_jXmZrQoTL7IBRewvOhF3d60Ryv10rEnxIuxU9vZPfTXV3Zg2a9K57QSIiSTx_PMM19w79XBEK1YuWHldsbH0Fu3OnI_Hvhd9zRrrTyv9mYYA8vXLFuzKps-It5grozQoyRg-b0PUtl5z_L_RVO27rTlAdas3BSs3F4v-ebV9MjKzaJ6fciy9bNVEg4Ml9MLDNfSB4b38HrvnWDYAKsjAqCzDhgulQnwBCzfQsbyTfp5D0X6yXCTPk16_x1C3RDqhlAfEQCRRLlR0T8UwDAeW24TOvIpN09vTCqZcJMiV1PkT7cg6-0UaiRw4sowXMao_yGoTxQX1XuOV9D6QnAHF7HjTZlu0hFqch-jebzwmp4n5q_WV3qQ0vAYtX-MUlwz9HPsLh4Hp0zoGC4ZYvTOsJRJkS3DsmPlvWGI0ZWa_F10u7oFcBRGZ5Knm4bXSpyIHaxsrY5VCn0Ig4_lijuGu4thbt2B4e4vhjv5Z_ULl4uCT8hvPYGzNoDgoydQHkLPA4SeQNJARpIRZzjx4NT3FH20aGsHD8oAq7IDq7IIY1W2h31khPfw0ivRp8Mc8UASPD8R8PRWVC0GH2EGNB24VuEMoidxnMM6HRrPuflPtEZPEoKFTmkNHKRyJIKyBp5JBOtAdaCCB03mEJJrTT4FY67BhB5s98ofDPkwn0T4oJkK_djOhT0x3Gn9fL3cDc4-kQgMd622LcNd09W1wIpEVSxE3WUiL_OuLogqoqzGbFkRdrms35yjIu6b48Z31p08w93vgmvuGO4erB32JpATPTcHmothYJg_4ALvHnBRTFT3MRzlQXBPUWmvoj4xKK4V95OM4MiPOqQU_crP62iJL29fFd2bzoI_qsFPWMP12SsP3MhLvfkoMnV81OENDmw7SRBzbD3FZD3QM2l_KQOuX_jZQ_YflW3rBZZNRl3BRSebLmuJF8i7rmrKFlHwpuFUSvlR2fUlEIa7G-nrw6uieZWVd_G7mUiuwauT0tzB4Gyr6QRWiNF5eOnpUj3qRMbHarMdcOdiiKkg1WQP3B0oXPvix2ovZW8UfWyLyzGd1dq-KHOY0pt92jlfb5Wvl0vxabdMQ-jHRu3X2-DnN847zPGGOd4wx8-Yt3MaNxH0cZ-Um-PHtfKvR-If3leWcmq_bjH6nhoypiUm6ekudcnxLmWy40p7aGkan9G-_w18cKMIo0uDS4zOkQn6DKPx4zBYF0jO4f_2hZ7JpcEfwPd21BJaAkexE0hCe347AR1xb018--aLhys3gukydbN1klyqVClVuFTtVBjPXI_k5zO5ymWTN3xGq0Vd1HmDyxJn_arktRRUctmglHVNbZFh0dTLTtaywmU5UyvMsMzKRbXIymKB80bIqsiKZSN5ibxGVmR04krPY19GkWfK-5FWiyLDfDnTvCXt0z8uREMvkKxxA5bbmVuladCOB8-KTCsf_O2YoIJOf9U-zMlYJHsjrIsL4SZIz4eBzJsensZUlGL7brH8SK_ORqdXPz3LUmhxFF1if17h3wEAAP__4hcctw">