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.
Details
Details
Diff Detail
Diff Detail
- Repository
- rL LLVM
Event Timeline
Comment Actions
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.
| lib/Analysis/DependenceAnalysis.cpp | ||
|---|---|---|
| 629 ↗ | (On Diff #139279) |
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.
if (!isIdentifiedObject(AObj) || !isIdentifiedObject(BObj)) return true;
return AObj == BObj; |
| lib/Analysis/DependenceAnalysis.cpp | ||
|---|---|---|
| 629 ↗ | (On Diff #139279) | I agree with Hal's comment. Seems like the way to go. |
| 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: 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) |
| lib/Analysis/DependenceAnalysis.cpp | ||
|---|---|---|
| 629 ↗ | (On Diff #139279) |
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.
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). |
Comment Actions
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.
Comment Actions
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).
Comment Actions
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)
Comment Actions
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).
Comment Actions
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)