valid BasicAA behavior?

Hi all,

I have this test case-

#define N 1000

extern double Ag[N];

extern double Bg[N];

void consume(double *A, double *B);

void swap_deps() {

double *A = Ag;

double *B = Bg;

for (int i = 0; i < 97; ++i) {

for (int j = 0; j < N; ++j) {

B[j] = A[j] + 1;

}

double *tmp = A;

A = B;

B = tmp;

}

consume(A, B);

}

BasicAA is returning ‘NoAlias’ when queried for phis created in the i-loop for A and B.

I was expecting it to return MayAlias since A and B are being swapped in the outer loop and so they access same locations in alternate iterations of the i-loop.

Is BasicAA returning the correct result in this case?

Thanks,

Pankaj

Perhaps BasicAA is telling that A and B don’t alias during one particular iteration of the loop even though they are swapped?

1: ; preds = %0, %35
%2 = phi double* [ getelementptr inbounds ([1000 x double], [1000 x double]* @Ag, i64 0, i64 0), %0 ], [ %4, %35 ]
%3 = phi i32 [ 0, %0 ], [ %36, %35 ]
%4 = phi double* [ getelementptr inbounds ([1000 x double], [1000 x double]* @Bg, i64 0, i64 0), %0 ], [ %2, %35 ]
br label %5

https://godbolt.org/z/vHJmL5

My understanding is that alias analysis returns results in the function scope, not in loop scope.

Since both the phis access both global arrays, that should results in BasicAA conservatively returning MayAlias.

I debugged this a little bit and narrowed it down to the section of the code in BasicAAResult::aliasPHI() which has this comment-

// Analyse the PHIs’ inputs under the assumption that the PHIs are

// NoAlias.

// If the PHIs are May/MustAlias there must be (recursively) an input

// operand from outside the PHIs’ cycle that is MayAlias/MustAlias or

// there must be an operation on the PHIs within the PHIs’ value cycle

// that causes a MayAlias.

// Pretend the phis do not alias.

It seems to be analyzing corresponding phi operands assuming the PHIs to be ‘Noalias’ to begin with.

IMHO, this setup does not work correctly for loop header phis.

BasicAA should return a result that is valid for the particular SSA values it is provided, valid at points in the control flow where it would be valid to use both SSA values simultaneously. In this example, the SSA values representing A and B always point to different memory, so NoAlias seems correct.

-Hal

Hi Hal,

In that case what is the best way to query whether there is a loop carried dependence between B[j] and A[j] at i-loop level?

We were operating under the assumption of ‘conservatively correct’ behavior of alias analysis in the function scope?

Thanks,

Pankaj

Hi, Pankaj,

You want a dependence analysis, there is a DependenceAnalysis (and also a new DDG).

-Hal

Isn’t DependenceAnalysis dependent on conservative behavior of alias analysis?

It invokes AliasAnalysis with unknown size.

I tried it on this case and it returns this-

$ opt -analyze -basicaa -da test.ll

Src: %0 = load double, double* %arrayidx, align 8, !tbaa !2 → Dst: store double %add, double* %arrayidx6, align 8, !tbaa !2

da analyze - none!

AliasAnalysis and dependence analysis answer different problems. AA check whether two memory ranges accessed at the same time (i.e. in the same iteration) do not overlap. DI checks when two accesses, not necessarily executed in the same iteration, do overlap.

DI makes use of AA in verifying that the base pointer (with unknown size), at the beginning of the loop, themselves do not overlap. If they are allowed to, reasoning over which iterations do access the same memory becomes … difficult. Note that it is possible to check at runtime whether to base pointer overlaps if the accessed range is known. LoopAccessAnalysis (for vectorization) does this.

For the original example, if the loop outer loops is unrolled by an even factor, the non-overlapping becomes more obvious in SSA.

Michael

All I am expecting from DA is a direction vector containing (*).

I think the main problem is that currently there is no exact way DA can query AliasAnalysis in a ‘conservatively correct’ manner.

Using UnknownSize seems to be an approximate solution (workaround).

IMHO, this particular piece of code in aliasPHI() does not work when conservative size is passed in to the aliasing query.

How do you guys feel about setting the initial cached result as MayAlias instead of NoAlias if the query is performed for UnknownSize?

If during alias query recursion we hit the same phi query again, we will return a conservative ‘MayAlias’ knowing that we have hit a cycle (loop).

The change will look something like this-

CacheIt->second = (PNSize == UnknownSize) ? MayAlias : NoAlias;

Not sure if there is a better solution.

Thanks,

Pankaj

Be careful with a known bug in DA + pointer swapping:

http://lists.llvm.org/pipermail/llvm-dev/2019-May/132725.html
https://bugs.llvm.org/show_bug.cgi?id=42143

Thanks for the hint. Indeed there seems to be confusion between
aliasing of the elements accessed in one itertation and aliasing
between the underlaying arrays.

Michael

All I am expecting from DA is a direction vector containing (*).

There seems to be a bug in DI, see Felipe's answer.

I think the main problem is that currently there is no exact way DA can query AliasAnalysis in a ‘conservatively correct’ manner.

Using UnknownSize seems to be an approximate solution (workaround).

Passing an unknown size is conservatively correct. That is, it must be
correct for any possible size.

Yes, we could be better if we know all the array elements that are
accessed. Unfortunately it is also difficult, e.g. because the access
range depends on `n`, ie is non-constant. The AA interface doesn't
even allow querying for non-constant sizes.

How do you guys feel about setting the initial cached result as MayAlias instead of NoAlias if the query is performed for UnknownSize?

If during alias query recursion we hit the same phi query again, we will return a conservative ‘MayAlias’ knowing that we have hit a cycle (loop).

Since aliasPHI looks for any incoming value contradicting the NoAlias
assumption, it would be equivalant to always return MayAlias.

Michael

Hi Michael,

There seems to be a bug in DI, see Felipe's answer.

Maybe I missed something. There seems to be no resolution to the problem. How can DA fix this without help from alias analysis?

Since aliasPHI looks for any incoming value contradicting the NoAlias assumption, it would be equivalant to always return MayAlias.

I pasted the code snippet below with some extra comments.
The merge is still happening with NoAlias. Only the cached query is set to MayAlias to detect the cycle during recursion.

     AliasResult Alias = NoAlias;
      AliasResult OrigAliasResult;
      {
        // Limited lifetime iterator invalidated by the aliasCheck call below.
        auto CacheIt = AAQI.AliasCache.find(Locs);
        assert((CacheIt != AAQI.AliasCache.end()) &&
               "There must exist an entry for the phi node");
        OrigAliasResult = CacheIt->second;
        CacheIt->second = NoAlias; // modify this to PNSize == MemoryLocation::UnknownSize ? MayAlias : NoAlias
      }

      for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
        AliasResult ThisAlias =
            aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
                       PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
                       V2Size, V2AAInfo, AAQI);
        Alias = MergeAliasResults(ThisAlias, Alias); //Merge happens with NoAlias
        if (Alias == MayAlias)
          break;
      }

I accept that this is a workaround but this could help DA for with this problem. A good solution might be to add an explicit interface to alias analysis which is conservatively correct for DA.

-Pankaj

As far

>> There seems to be a bug in DI, see Felipe's answer.
Maybe I missed something. There seems to be no resolution to the problem. How can DA fix this without help from alias analysis?

DependenceInfo is not using the AA interface correctly. Either DI has
to be fixed, or another method added to AA that gives additional
guarantees. Please see the bug report for details.

>> Since aliasPHI looks for any incoming value contradicting the NoAlias assumption, it would be equivalant to always return MayAlias.
I pasted the code snippet below with some extra comments.

As far as the AA interface specification is concerned, the NoAlias
result is correct. Such a patch would be a pessimization without
giving any additional guarantees.

Michael

DependenceInfo is not using the AA interface correctly. Either DI has to be fixed, or another method added to AA that gives additional guarantees. Please see the bug report for details.

Thanks for updating the bug report but GetUnderlyingObject() doesn't help in this case. The underlying object of the phi is phi itself. I don't think any amount of change on the client side will help because AA interface doesn't give the guarantee DI needs.

As far as the AA interface specification is concerned, the NoAlias result is correct. Such a patch would be a pessimization without giving any additional guarantees.

Ok, fair point.
So the only option left is to introduce a new AA interface which does provide the guarantees needed by DI, correct?

-Pankaj

>> DependenceInfo is not using the AA interface correctly. Either DI has to be fixed, or another method added to AA that gives additional guarantees. Please see the bug report for details.

Thanks for updating the bug report but GetUnderlyingObject() doesn't help in this case. The underlying object of the phi is phi itself. I don't think any amount of change on the client side will help because AA interface doesn't give the guarantee DI needs.

For a meaningful analysis, the underling object must be the same in
the analysis' scop. In case of DependenceInfo, this translates into
loop-invariance of the base base pointer. I don't think we can get any
meaningful dependence when the base pointer changes between loop
iterations. In your case, it's done by a PHINode, but it could also be
loaded from memory each iteration (and some metadata indicates that
two loaded pointers does not alias IN THE SAME ITERATION).

DI tries to approximate this:

switch (underlyingObjectsAlias(AA, F->getParent()->getDataLayout(),
                                 MemoryLocation::get(Dst),
                                 MemoryLocation::get(Src))) {
  case MayAlias:
  case 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);
  case NoAlias:
    // If the objects noalias, they are distinct, accesses are independent.
    LLVM_DEBUG(dbgs() << "no alias\n");
    return nullptr;
  case MustAlias:
    break; // The underlying objects alias; test accesses for dependence.
  }

Unfortunately, this does not verify that the base pointer is
invariant. It ensures aliasing within one iterations, but it it is
obviously wrong to conclude that pointers from different iterations
also do/do not alias.

I haven't looked at all of DependenceInfo, so there might be some
other place where the invariance is checked. One problem we had to
face for ensuring correctness of Polly was to ensure the the
loop-invariance of base pointers. A typical pattern is the following:

  for (int i = 0; i < S->size; ++i) {
     S->Data[i] = S->Data[i-1];
     do_something(S, ...);
  }

This looks like a simple flow dependence [i -> i+1]; The IR generated
by clang re-loads the pointer S->Data again in ever iteration, but
do_something might actually change the value of S->Data when called.
That is, we cannot analyze the dependency in this loop unless the load
of S->Data is hoisted out of the loop (e.g. by LICM). Polly has
mechisms to either infer conditions under which S->Data is
loop-invariant or to bail out if it cannot.

>> As far as the AA interface specification is concerned, the NoAlias result is correct. Such a patch would be a pessimization without giving any additional guarantees.

Ok, fair point.
So the only option left is to introduce a new AA interface which does provide the guarantees needed by DI, correct?

Either AA or DI must ensure the invariance of underlying objects. IMHO
it would make more sense if DI did it. AA is typically control-flow
agnostics and loop-invariance out of its scope.

Michael

Hi Michael,

Thank you for the thoughtful reply and discussion!

I don't think we can get any meaningful dependence when the base pointer changes between loop iterations. In your case, it's done by a PHINode, but it could also be loaded from memory each iteration (and some metadata indicates that two loaded pointers does not alias IN THE SAME ITERATION).

for (int i = 0; i < S->size; ++i) {
   S->Data[i] = S->Data[i-1];
   do_something(S, ...);
}

The loop invariance issue caused by PHIs is fundamentally different than the one caused my memory accesses. The latter is much easier for DI to deal with. AA will return MayAlias in this case which is the conservatively correct answer. After that it is up to DI to form a conservative direction vector by checking whether the pointer is loop invariant.

Either AA or DI must ensure the invariance of underlying objects. IMHO it would make more sense if DI did it. AA is typically control-flow agnostics and loop-invariance out of its scope.

Most of AA is control-flow agnostic but BasicAA is not. In fact, in the pointer swapping case aliasPHI() is refining the result based on control flow by querying corresponding PHI operands.

Here's an example where the base ptr PHIs are not loop-invariant but the NoAlias result returned by BasicAA for p[i] and q[i] is still valid for DI-

int A[100];
int B[100];
int C[100];
int D[100];

void foo() {

  int i, *p, *q;
  for(i=0; i<50; i++) {
    if (i > 5) {
      p = A;
      q = C;
    }
    else {
      p = B;
      q = D;
    }
    p[i] = q[i];
  }
}

The basic problem is that in some cases BasicAA is not returning the conservatively correct answer for purposes of dependence analysis.
Not all control-flow based analysis is bad, just the one which doesn't correctly take into account loops/cycles in the CFG.

For correctness, what we want is a more conservative cousin of BasicAA which DI can rely upon. The workaround for UnknownSize I proposed was for precisely this reason.
All analysis which care about 'loop-carried' analysis pass in UnknownSize to alias analysis.

Having said that, a separate alias interface which has conservatively correct behavior in the presence of loops/cycles would be a much better solution.

-Pankaj

To recap:

1. The result returned by BasicAA is correct in respect to the
AliasAnalysis specification.
2. We agree that the result return by DependenceInfo is incorrect,
including a pre-existing bug report.

I am puzzled how you conclude that we should fix BasicAA.

However, you are free to upload a patch to Phabricator so we get
experience about the consequences of your proposed change.

Michael