This is an archive of the discontinued LLVM Phabricator instance.

[DA] Correct size parameter from dependency analysis to AA
ClosedPublic

Authored by dmgreen on Jan 22 2018, 9:28 AM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

dmgreen created this revision.Jan 22 2018, 9:28 AM
dmgreen updated this revision to Diff 139279.Mar 21 2018, 5:49 AM

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.

hfinkel added inline comments.Apr 4 2018, 2:55 PM
lib/Analysis/DependenceAnalysis.cpp
629 ↗(On Diff #139279)

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 added a subscriber: nlopes.Apr 5 2018, 2:59 AM
nlopes added inline comments.
lib/Analysis/DependenceAnalysis.cpp
629 ↗(On Diff #139279)

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

dmgreen updated this revision to Diff 141139.Apr 5 2018, 5:56 AM
dmgreen added inline comments.
lib/Analysis/DependenceAnalysis.cpp
629 ↗(On Diff #139279)

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 added inline comments.Apr 6 2018, 5:19 AM
lib/Analysis/DependenceAnalysis.cpp
629 ↗(On Diff #139279)

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 updated this revision to Diff 141548.Apr 8 2018, 9:48 AM

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 updated this revision to Diff 141558.Apr 8 2018, 10:48 AM

Minus size...

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).

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)

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).

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 accepted this revision.Apr 9 2018, 4:08 AM

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.

This revision is now accepted and ready to land.Apr 9 2018, 4:08 AM
This revision was automatically updated to reflect the committed changes.