This is an archive of the discontinued LLVM Phabricator instance.

[AA] Cache (optionally) estimated PartialAlias offsets.
ClosedPublic

Authored by dfukalov on Dec 18 2020, 2:42 AM.

Details

Summary

For the cases of two clobbering loads and one loaded object is fully contained
in the second BasicAAResult::aliasGEP returns just PartialAlias that
is actually more common case of partial overlap, it doesn't say anything about
actual overlapping sizes.

AA users such as GVN and DSE have no functionality to estimate aliasing of GEPs
with non-constant offsets. The change stores estimated relative offsets so they
can be used further.

Diff Detail

Event Timeline

dfukalov created this revision.Dec 18 2020, 2:42 AM
dfukalov requested review of this revision.Dec 18 2020, 2:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 18 2020, 2:42 AM
bmahjour removed a subscriber: bmahjour.Dec 18 2020, 7:25 AM
nikic added inline comments.Dec 18 2020, 10:06 AM
llvm/lib/Analysis/AliasAnalysis.cpp
971

Why is it okay to treat the offset symmetrically? I'd expect the offset either be negative if swapped, or be not defined at all, depending on the contract of this function is supposed to be (probably needs a doc comment).

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1435

Why do you use a separate VisitedPhi flag, rather than checking !VisitedPhiBBs.empty(), as we do elsewhere?

This kind of flag breaks BatchAA, because it will leak across queries.

llvm/lib/Analysis/CaptureTracking.cpp
417 ↗(On Diff #312734)

This looks unrelated, land separately?

dfukalov updated this revision to Diff 313082.Dec 21 2020, 4:34 AM

Rebased, change reworked as requested.

dfukalov marked 2 inline comments as done.Dec 21 2020, 4:41 AM
dfukalov added inline comments.
llvm/lib/Analysis/AliasAnalysis.cpp
971

My thought was to mark "undefined" offset as -1 and store pointers in pairs in "positive offset" order. It was based on GVN ability to use positive offset only for clobbering.
But you're right, it is more effective to store pointers pairs in cache in the same way as it is implemented for AliasCache.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1435

Thanks, good catch, missed this leak.

dfukalov marked 2 inline comments as done.Dec 28 2020, 12:49 AM

Ping...

Ping. I'm going to submit the change on Friday if no objections are observed.

This should probably be split up into BasicAA (+unit test), MemoryDependenceAnalysis(?), and GVN patches.

fhahn added a comment.Jan 18 2021, 1:52 AM

IIUC this is similar to the handling of partial overwrites in DSE (https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp#L548)?

If so, could we just generalize the helper there, rather than threading this through the different caches from BasicAA to GVN? Yes, we have to do some extra work in GVN, but there would be no need to maintain a cached value not used by other clients, it will work with any AA implementations returning partial alias & there will be no extra work when moving away from MemDepAnalysis.

IIUC this is similar to the handling of partial overwrites in DSE (https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp#L548)?

If so, could we just generalize the helper there, rather than threading this through the different caches from BasicAA to GVN? Yes, we have to do some extra work in GVN, but there would be no need to maintain a cached value not used by other clients, it will work with any AA implementations returning partial alias & there will be no extra work when moving away from MemDepAnalysis.

GVN has similar partial aliased memory objects functionality in https://github.com/llvm/llvm-project/blob/master/llvm/lib/Transforms/Utils/VNCoercion.cpp but it has the same issue: they use GetPointerBaseWithConstantOffset() and give up in a case when GEP offset is not constant (please refer the trivial test case in the patch). But BasicAA has an ability to go further and prove partial alias plus estimate overlapping offsets. It seems all these operations (including PHIs processing) should not be re-applied in an AA user.

The issue was masked for different targets because usually vector types are splitted before GVN so it's just see MustAlias parts of vectors and successfully eliminate them.
Actually current DSE fails with the same pattern of stores, I planned to fix it after the patch.

I'm going to split the change by Roman request and update the description to clarify these circumstances.

dfukalov updated this revision to Diff 317702.Jan 19 2021, 2:49 PM

AA part of the splitted patch.

dfukalov edited the summary of this revision. (Show Details)Jan 19 2021, 2:53 PM
dfukalov retitled this revision from [GVN][BasicAA] Enable clobbering in GVN. to [AA] Store and return estimated PartialAlias offsets..
asbirlea requested changes to this revision.Jan 21 2021, 4:22 PM

Adding this only seems to make sense when using BatchAA.
Could we restrict populating this cache? e.g. extend AAQueryInfo constructor to take bool BatchMode = false, and set it to true for BatchAA. Then update the get/set methods to first check this (check in the setter and assert in the getter).

llvm/include/llvm/Analysis/AliasAnalysis.h
370

Document (add comments) what this cache stores, and its purpose.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1173

referenced

This revision now requires changes to proceed.Jan 21 2021, 4:22 PM
dfukalov updated this revision to Diff 318578.Jan 22 2021, 10:47 AM

Comments addressed.

dfukalov marked 2 inline comments as done.Jan 22 2021, 10:49 AM
dfukalov added inline comments.
llvm/lib/Analysis/BasicAliasAnalysis.cpp
1173

Thanks!

Thanks! Diff looks reasonable to me, but I'd like to see the use case changes as well. Could you (re-)upload a concrete use case as dependent patch?
One reason I have in mind is we may want to concretely enable this caching solely for a particular BatchAA instance, i.e. pass true to BatchAA and change the meaning in AAQI from BatchMode to CacheOffsets (and, same as now, only allow BatchAA to set this bool). Then only pass true at the BatchAA callsites where it will be used.

llvm/include/llvm/Analysis/AliasAnalysis.h
350

complicated

389

only

nikic added inline comments.Jan 23 2021, 1:31 AM
llvm/lib/Analysis/BasicAliasAnalysis.cpp
1175

I'm not sure this code is the right place to perform these access size checks. Consider the case where BatchAA is queried for the same pointers with different location sizes in a row. The first query is such that they are PartialAlias and the LocationSize fits into the larger access. The second one is also PartialAlias, but does not fit. In this case, the getClobberOffset() API will still return a result though, and a caller may incorrectly assume that the access is nested based on this check, even though it isn't.

dfukalov updated this revision to Diff 319634.Jan 27 2021, 11:21 AM
dfukalov marked an inline comment as done.

Added memory sizes to map key, BatchAA can be created without caching.

dfukalov marked 3 inline comments as done.Jan 27 2021, 11:30 AM

... Could you (re-)upload a concrete use case as dependent patch?

I've just created D95543 with the test for upcoming changes in GVN. It is actually the same code as one used in unit test in this patch.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1175

Thanks for good point! Added sizes to cache key, updated test to check that offset is returned only for exact the same set of two pointers and two sizes.

dfukalov retitled this revision from [AA] Store and return estimated PartialAlias offsets. to [AA] Cache (optionally) estimated PartialAlias offsets..Jan 27 2021, 11:32 AM
dfukalov marked an inline comment as done.Feb 3 2021, 3:08 AM

Gentle ping...

@asbirlea, @nikic, would you please take a look at the updated patch?

nikic accepted this revision.Mar 1 2021, 2:28 PM

I think the proper solution here would be to change AliasResult into a class that carries both the type of the result and an offset for PartialAlias (probably of reduced width), rather than making this information available via a cache side channel.

That would be a larger change though, and I'm okay with doing this in the meantime to make some progress.

llvm/include/llvm/Analysis/AliasAnalysis.h
399

nit: Unnecessary braces.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1153

No need to use pointer for LocationSize, the type is okay to copy.

1155

nit: Off.isNegative()

1168

nit: auto -> uint64_t. Type is not obvious from context.

llvm/unittests/Analysis/AliasAnalysisTest.cpp
323

Wrong test :)

dfukalov updated this revision to Diff 327454.Mar 2 2021, 7:39 AM

Rebased, addressed comments.

This revision was not accepted when it landed; it landed in state Needs Review.Mar 2 2021, 8:04 AM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
dfukalov marked 5 inline comments as done.