[DA] Correct size parameter from dependency analysis to AA

[dmgreen]

Summary

We were supplying the size to AA as DL.getTypeStoreSize(AObj->getType()),
which causes us to incorrectly presume noalias between loads/stores
with dependencies. I believe BasicAA was returning noalias because it
is undefined behaviour to access objects with a larger access than the
object size.

[dmgreen]

Rebase and simplify test.

It's possible that the size here should be the size of the thing that AObj points to, as opposed to unknown. I've added a number of reviewers who may know what they are talking about.

[dmgreen]

ping :)

[hfinkel]

lib/Analysis/DependenceAnalysis.cpp

629

It's possible that the size here should be the size of the thing that AObj points to, as opposed to unknown

There are two problems here, and I think that we can fix them both. What we're really trying to do here is to identify disjoint underlying objects.

• First, GetUnderlyingObject might not always return the underlying object (because it has a recursion-depth cutoff). Thus, we need to validate the fact that GetUnderlyingObject actually did return such a thing. So we really want to do:

if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj))
  return true;

• At that point, the sizes are essentially irrelevant. and we should pass MemoryLocation::UnknownSize as the size. However, at that point, since we have unique underlying objects, we can just compare them, so we can just do (there's no further value in calling into AA):

return AObj == BObj;

[nlopes]

lib/Analysis/DependenceAnalysis.cpp

629

I agree with Hal's comment. Seems like the way to go.

[dmgreen]

lib/Analysis/DependenceAnalysis.cpp

629

This sounds good. I like the simplification. I've updated things to something that may still be wrong.

As far as I understand, this is returning a tristate:
MustAlias - Do dependency analysis.
NoAlias - No dependence is possible.
MayAlias - Don't know anything - a confused dependence.

A lot of the tests use function arguments as input (as will real code). If AObj and BObj are the same argument, we are obviously mustalias, even if that isn't an identified object. So I think this is now still correct even if we hit the recursion limit, the mustalias will still be valid.

Also (and this might be something that doesn't come up very often) what if one argument has a noalias attribute, but another doesn't (or one is a alloca, the other an argument). We can still prove noalias there?

Also I was hoping to get TBAA working here. See D42382. As in - if the loads/stores of the Src and Dst are different types, we know there is no alias, so no dependency. Any ideas what the best bet there would be? Call alias on the Src and Dst? Work with the TBAA metadata somehow? (I'm not sure that's possible)

[hfinkel]

lib/Analysis/DependenceAnalysis.cpp

629

Also (and this might be something that doesn't come up very often) what if one argument has a noalias attribute, but another doesn't (or one is a alloca, the other an argument). We can still prove noalias there?

No, although you could add that as a special case (i.e., one value is an argument (or global value) and for the other isIdentifiedFunctionLocal returns true.

Also I was hoping to get TBAA working here.

Good point. This will require a slightly larger change, but seems worthwhile. You'll want to collect the AA metadata and then construct a memory location using that metadata but using MemoryLocation::UnknownSize, and then to an AA query using those memory locations (this will effectively check the underlying objects, but also make use of the metadata). I recommend that you change this function to accept to MemoryLocation references. Get these from the original accesses using MemoryLocation::get, and then inside this function form two new MemoryLocation objects, one from each original, MemoryLocation(LocA.Ptr, MemoryLocation::UnknownSize, LocA.AATags) (or something equivalent).

[dmgreen]

Thanks for the pointers. I've folded the tbaa changes into this patch as they are related. This now checks the alias on the original locations, on the assumption that if they don't alias for any reason then there is no dependency. Then falls back to underlying object.

[dmgreen]

Minus size...

[hfinkel]

In D42381#1061022, @dmgreen wrote:

Thanks for the pointers. I've folded the tbaa changes into this patch as they are related. This now checks the alias on the original locations, on the assumption that if they don't alias for any reason then there is no dependency. Then falls back to underlying object.

Does the fallback add anything? I think that the AA query should catch all relevant cases (i.e., you can just return the result of the AA query and be done).

[dmgreen]

Does the fallback add anything?

We need to detect things like this as mustalias (to find the flow dependence), not mayalias (confused):

for (int i = 0; i < n; i++) {
  A[i + 2] = i;
  ... = A[i];

Unless you mean just do the alias analysis like this:?

return AA->alias(GetUnderlyingObject(LocA.Ptr), MemoryLocation::UnknownSize, LocA.AATags, GetUnderlyingObject(LocB.Ptr), MemoryLocation::UnknownSize, LocB.AATags)

[hfinkel]

In D42381#1061379, @dmgreen wrote:

Does the fallback add anything?

We need to detect things like this as mustalias (to find the flow dependence), not mayalias (confused):

for (int i = 0; i < n; i++) {
  A[i + 2] = i;
  ... = A[i];

Unless you mean just do the alias analysis like this:?

return AA->alias(GetUnderlyingObject(LocA.Ptr), MemoryLocation::UnknownSize, LocA.AATags, GetUnderlyingObject(LocB.Ptr), MemoryLocation::UnknownSize, LocB.AATags)

Just do:

return AA->alias(LocA.Ptr, MemoryLocation::UnknownSize, LocA.AATags, LocB.Ptr, MemoryLocation::UnknownSize, LocB.AATags)

there's no need to call GetUnderlyingObject here explicitly. When you pass an unknown size, that's essentially what BasicAA is doing anyway (since it has no size information, AA can only look at the metadata and the underlying objects for aliasing information).

[dmgreen]

But in here:

for (int i = 0; i < n; i++) {
  A[i + 2] = i;
  ... = A[i];

the load and store are mayalias. We need the fact that the underlying obects are mustalias (otherwise a number of tests are failing in a way that looks like it's discovering less dependencies, more are confused)

[hfinkel]

In D42381#1061394, @dmgreen wrote:

But in here:

for (int i = 0; i < n; i++) {
  A[i + 2] = i;
  ... = A[i];

the load and store are mayalias. We need the fact that the underlying obects are mustalias (otherwise a number of tests are failing in a way that looks like it's discovering less dependencies, more are confused)

Ah, okay. LGTM.

lib/Analysis/DependenceAnalysis.cpp

void Dependence::dump(raw_ostream &OS) const {
   OS << "!\n";
 }
 
 static AliasResult underlyingObjectsAlias(AliasAnalysis *AA,
                                           const DataLayout &DL, const Value *A,
                                           const Value *B) {
   const Value *AObj = GetUnderlyingObject(A, DL);
   const Value *BObj = GetUnderlyingObject(B, DL);
-  return AA->alias(AObj, DL.getTypeStoreSize(AObj->getType()),
-                   BObj, DL.getTypeStoreSize(BObj->getType()));
+  return AA->alias(AObj, BObj);
 }
 
 
 // Returns true if the load or store can be analyzed. Atomic and volatile
 // operations have properties which this analysis does not understand.
 static
 bool isLoadOrStore(const Instruction *I) {
   if (const LoadInst *LI = dyn_cast<LoadInst>(I))

test/Analysis/DependenceAnalysis/AASize.ll

+; RUN: opt < %s -analyze -basicaa -da | FileCheck %s
+
+; CHECK-LABEL: test
+; CHECK: da analyze - none!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - none!
+; CHECK: da analyze - none!
+; CHECK: da analyze - confused!
+; CHECK: da analyze - none!
+
+@a = global i16 5, align 2
+@b = global i16* @a, align 4
+define void @test2() {
+entry:
+  %0 = load i16*, i16** @b, align 4
+  %1 = load i16, i16* %0, align 2
+  store i16 1, i16* @a, align 2
+  ret void
+}