[llvm-dev] valid BasicAA behavior?

[Michael Kruse via llvm-dev]

Am Mi., 18. März 2020 um 18:15 Uhr schrieb Chawla, Pankaj
<pankaj.chawla at intel.com>:
>
> >> 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