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

    <tr>
        <th>Summary</th>
        <td>
            [LoopInterchange][DependenceAnalysis] Miscompilation on loops with anti-dependencies
        </td>
    </tr>

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

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

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

<pre>
    Consider this simple function:
``` c
void anti(int *A, int x, unsigned N, unsigned M) {
  for (unsigned m = 0; m < M; ++m)
    for (unsigned i = 0U; i < N - 1; ++i) {
      A[i] = A[i + 1] + x;
    }
}
```
LoopInterchange currently kicks in on this loop and turns it into:
``` c
void anti(int *A, int x, unsigned N, unsigned M) {
  for (unsigned i = 0U; i < N - 1; ++i)
    for (unsigned m = 0; m < M; ++m) {
      A[i] = A[i + 1] + x;
 }
}
```
Which is apparently wrong.

To further illustrate the problem, one can run the function with this `main` function:
``` c
int main(int argc, char **argv) {
  int A[5] = {1, 2, 3, 4, 5};
  anti(A, argc + 2, 5, 3);

  for (unsigned i = 0U; i < 5; ++i) {
 printf(" %d", A[i]);
  }
  printf("\n");

  return 0;
}
```
The `-O0` program prints out " 13 14 11 8 5" while the incorrectly interchanged program prints " 5 6 7 8 5", hence the miscompile.

-----

The culprit of this problem comes from DependenceAnalysis, which provides a direction vector (between `A[i]` & `A[i + 1]`) of "[S <]" in this case, but I think it really should yield "[S >]" because we have an anti-dependency here. LoopInterchange should be able to stop doing any optimization when it sees "[S >]" as it violates the legality.

CC @sjoerdmeijer @Meinersbur @bmahjour 
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy8Vk1v4zYT_jX0ZZBAoiTLPvjgjzfAAm-2h27RM0WNrUkoUiApe91fXwxlO3F2t7tAgQoBQ1LzQT7PMyOrEOhgEVei2ohqN1Nj7Jxf9aFz-vWkjjhrXHtebZ0N1KKH2FGAQP1gEPaj1ZGcFcVaZDuRrcU8m_5ATxtHRy0oG0nIBdkIQq7XQm6B5195MtqUvoXPd6tnIZcg6s0UBWDvPAi5uL3vQRQ7yESxSdMtPPNUyI2Qm17I5dXvW0-aPP9ge0qun-EB8jd3-pCan7WoNiSqXfJNCzaGPG3JDXwVxTt7Ue8ucNwmV1ym5f-dGz7ZiF53yh4Q9Og92mjO8Er6NQBZcHZC2jg3gLItxNHbABQZOvffA_5LsP0Y9Z_x9S8A_ynaf3akO6AAahjUBeeTd_bweDFP4xcH-9HHDj2QMWOIXkWE2CEM3jUGe4bLWQStLPjRplfXAoATxW4iTMyzXpFlSn5eHsxKsp7IUv6gOY3uFMO3FnKt_OH4AR-2ZEiqKz6i3uTsJnkoeCh5qBiQN11eRJHUwIkSjnIynPyWN-tfV0H1w8IZPNm4F3IhpAQhq1bIlO1K7ft872oG7hxFtbXJ79uzeeSSSJr6Z_6_dMisPPyWkB-8O3jVT1kCuJFrREJeQF5CnsOC4ZBw6shM9JPVznvULBt6K9r2YyT2qmAO9SUE37VDq6coPQXt-oEM3qnugZ87GXbcDszgKYLbT5K6CBC06zHA3rsedjigbTn62ipzDhQ43SkpffDuSC0GUNASH5wFekQdJzIbjCdEy5DcqJhnIOT8tnWrNcZQLvkgiYvN78x54k5yk0qn0yogJ2_GCJ94y75ym_KojDlD6NxoWjgTmvZdkP9dgjSo1RgQTgidOiIom3T60F7vd4YOPT7Cx5Z5idsgqIaJchCiG6B1ZA-g7BncEKmnv9RUnh1aPlRADN85hUqN9UjOqIgh8WXwoAzF8x1b2y2IMgsvDn3bI72g5_UzkkUfmjGtml51L270MGtXRbsslmqGq7wu8qpczJf1rFvpom6zupG50nu1n8_rLK9lJjOt54tlsS9ntJKZLPM8L7O8LKv6schVta-XZdtkssyKTJQZ9orMozHH_tH5w4xCGHGV5_O8LGdGNWhC-qBLafEE6W269m7mV-z00IyHIMrMUIjhLUykaNIvgQ9wM07V5juiq3bwfFX2BLWz6ZsVppZ4TyZhmI3erLoYh8BdUT4J-XSg2I3No3a9kE98lMu_h8G7F9RRyKd0gSDk0-WGx5X8OwAA__8esYLz">