[LoopInterchange] incorrect handling of scalar dependencies and dependence vectors starting with ">"

[bmahjour]

The following example shows a miscompile:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

__attribute__((noinline))
void foo(int n, int m, float aa[1024][128], float bb[1024][128], float cc[1024][128]) {
#ifndef MYINTERCHANGE
  for (int j = 1; j < 128; j++)  {
    for (int i = 1; i < 1024; i++)    {
      aa[1][j-1] += bb[i][j];
      cc[i][j] = aa[1][j];
    }
  }
#else
  for (int i = 1; i < 1024; i++)  {
    for (int j = 1; j < 128; j++)    {
      aa[1][j-1] += bb[i][j];
      cc[i][j] = aa[1][j];
    }
  }

#endif
}

__attribute__((noinline))
void init(int n, int m, float aa[restrict][m]) {
  for (int i = 0; i < n; i++)  {
    for (int j = 0; j < m; j++)    {
      aa[i][j] = i*j;
    }
  }
}

__attribute__((noinline))
void print(int n, int m, float aa[restrict][m]) {
  for (int i = 0; i < n; i++)  {
    for (int j = 0; j < m; j++)    {
      printf("[%d,%d]=%f\n", i, j, aa[i][j]);
    }
  }
}

#define N 1024
#define M 128

int main() {
  float *f1, *f2, *f3;
  f1 = (float *) malloc (N * M * sizeof(float));
  f2 = (float *) malloc (N * M * sizeof(float));
  f3 = (float *) malloc (N * M * sizeof(float));
  memset(f3, 0, N*M*sizeof(float));
  init(N,M, (float (*)[])f1);
  init(N,M, (float (*)[])f2);
  foo(N,M, (float (*)[])f1, (float (*)[])f2, (float (*)[])f3);
  print(N,M,(float (*)[])f3);
}

> clang  bad-interchange.c -O3 -o bad -mllvm -enable-loopinterchange
> clang  bad-interchange.c -O3 -o good
> good > 1.txt && bad > 2.txt
> diff 1.txt 2.txt | head
258,383c258,383
< [2,1]=1.000000
< [2,2]=2.000000

[bmahjour]

The problem is that S dependencies should be treated as if having loop carried dependency in all directions and they don't!
There is also a problem in how the legality analysis handles dependency vectors that have a ">" in their left-most non-'=' position. A slightly modified version of the above test case is treated illegal (which is good) but for the wrong reason:

  for (int j = 1; j < 128; j++)  {
    for (int i = 1; i < 1024; i++)    {
      cc[i][j] = aa[1][j];
      aa[1][j-1] += bb[i][j];
    }
  }

it starts with an row of [-1 S] and then permutes it to [S -1]. It treats the S as if it was a = and only concludes the interchange is illegal because now the left-most non-'=' is >'. What should really be the reason to stop interchange is the presence of Sin the left-most position not the>` in the second position.

In such cases it should reverse all directions within that row, since a dependence whose sink happens before its source is meaningless.

[bmahjour]

I suspect the following might be related to the mishandling of scalar dependencies:

• [LoopInterchange] Interchange breaks program correctness #46867
• [LoopInterchange] Loops should not interchanged due to dependencies #47259
• [LoopInterchange] Loops should not interchanged due to control flow #47401