[LoopInterchange] Incorrect exchange happens when the Levels of Dependence is less than the depth of the loop nest

[kasuga-fj]

Input:

#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.

llvm-project/llvm/lib/Transforms/Scalar/LoopInterchange.cpp

Lines 212 to 214 in 9f77c26

	while (Dep.size() != Level) {
	Dep.push_back('I');
	}

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.

llvm-project/llvm/lib/Analysis/DependenceAnalysis.cpp

Lines 3605 to 3609 in b712590

	case AliasResult::MayAlias:
	case AliasResult::PartialAlias:
	// cannot analyse objects if we don't understand their aliasing.
	LLVM_DEBUG(dbgs() << "can't analyze may or partial alias\n");
	return std::make_unique<Dependence>(Src, Dst);

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

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.

For safety, I think I dependencies should be replaced with *

[kasuga-fj]

cc: @sjoerdmeijer
This should also be fixed before #124911. I think I'll submit a PR by the end of the month.