[DependenceAnalysis] assumes base pointer invariance.

[Meinersbur]

Consider these 3 functionally equivalent functions:

void foo(int n, double * restrict A, double * restrict B) {
  double *ptr1 = A;
  double *ptr2 = B;
  for (int i = 1; i < n; ++i) {
      ptr1[i] = ptr2[i-1];

      double *tmp = ptr1;
      ptr1 = ptr2;
      ptr2 = tmp;
  }
}

void bar(int n, double * restrict A, double * restrict B) {
  for (int i = 1; i < n; ++i) {
      double *ptr1 = i&2 ? A : B; 
      double *ptr2 = i&2 ? B : A;

      ptr1[i] = ptr2[i-1];
  }
}

void xyzzy(int n, double * restrict A, double * restrict B) {
  for (int i = 1; i < n; ++i) {
     if (i&1) 
      A[i] = B[i-1];
    else 
      B[i] = A[i-1];
  }
}

Compile with:

$ clang -O3 da.c -emit-llvm -Xclang -disable-llvm-passes -S -c -o da.ll
$ opt da.ll -basic-aa -mem2reg -instcombine -loop-simplify -loop-rotate -da -analyze -enable-new-pm=0

The -da result for foo is:

Src:  %0 = load double, double* %arrayidx, align 8, !tbaa !4 --> Dst:  store double %0, double* %arrayidx2, align 8, !tbaa !4
  da analyze - none!

which is wrong, because for even values of i, ptr2[i-1] reads the value written in the previous iteration. That is, there is a flow dependence.

The result is none because AliasAnalysis returns NoAlias for %ptr1 and %ptr2, which is correct in the sense that in the same iteration, one of them points to %A (which is noalias) and the other to %B (which is also noalias), ie. those two never alias.

DependenceAnalysis analyses dependencies across iterations and therefore will compare memory accesses from different iterations. I.e. %ptr1 is equal to %ptr2 from the previous iteration.

I think the problem here is that DependenceAnalysis makes two wrong assumptions that combined leads to wrongs results:

1. AliasAnalysis's results are valid across phi nodes
2. The base pointer is invariant in all loops

DependenceAnalysis on bar seems pessimistically correct, on xyzzy the correct flow/anti dependences are detected.

[llvmbot]

@llvm/issue-subscribers-bug

[Meinersbur]

Possible duplicate: #41488

It discusses extending the query interface for AliasAnalysis. However, I think it is more fundamental to check the loop-invariances of the base pointer. If base pointers varies between iterations, a DependencyAnalysis only taking subscripts into account cannot be correct. An extended cross-iteration AliasAnalysis could never return MustAlias in this case anyway, since the pointer will have different values in different iterations and only at most one of those could be MustAlias with another pointer (constant or the specific value of another varying pointer).

[sebpop]

Memory SSA is way too heavy to maintain in loop passes.
I will post a patch to fix this with SCEV analysis.