Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
kasuga-fj opened this issue May 16, 2025 · 1 comment · May be fixed by #140709

Comments

@kasuga-fj
Copy link
Contributor

kasuga-fj commented May 16, 2025

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.

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.

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
Copy link
Contributor Author

kasuga-fj commented May 16, 2025

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

kasuga-fj added a commit to kasuga-fj/llvm-project that referenced this issue May 20, 2025
LoopInterchange pads the end of the direction vector with `I` when the
Levels value of a Dependence object is less than the depth of the loop
nest. However, `I` dependencies were treated the same as `=` in
subsequent processes, which is incorrect. For example,
DependenceAnalysis currently returns a default Dependence object when
AliasAnalysis results in MayAlias. In such a case, the direction vector
should be like `[* * ... *]`. However, because the Levels value of
default Dependence object is 0, therefore LoopInterchange generated a
direction vector like `[I I ... I]`, leading to unsafe interchanges.
This patch fixes the issue by replacing `I` with `*`. As far as I
understand, this change doesn't prevent any legal interchanges that were
applied before this patch.

Fixes llvm#140238
@kasuga-fj kasuga-fj linked a pull request May 20, 2025 that will close this issue
kasuga-fj added a commit to kasuga-fj/llvm-project that referenced this issue May 20, 2025
LoopInterchange pads the end of the direction vector with `I` when the
Levels value of a Dependence object is less than the depth of the loop
nest. However, `I` dependencies were treated the same as `=` in
subsequent processes, which is incorrect. For example,
DependenceAnalysis currently returns a default Dependence object when
AliasAnalysis results in MayAlias. In such a case, the direction vector
should be like `[* * ... *]`. However, because the Levels value of
default Dependence object is 0, therefore LoopInterchange generated a
direction vector like `[I I ... I]`, leading to unsafe interchanges.
This patch fixes the issue by replacing `I` with `*`. As far as I
understand, this change doesn't prevent any legal interchanges that were
applied before this patch.

Fixes llvm#140238
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants