This is an archive of the discontinued LLVM Phabricator instance.

[AA] Pass AAResults through AAQueryInfo
ClosedPublic

Authored by nikic on Jan 9 2021, 1:14 PM.

Details

Summary

Currently, AAResultBase (from which alias analysis passes inherit) stores a reference back to the AAResults aggregation it is part of, so it can perform recursive alias analysis queries via getBestAAResults. This has the implicit assumption that an AAResult can only be part of a single AAResults aggregation. At least under the legacy pass manager, this doesn't seem to actually be the case. This appears to be mostly harmless in practice, but caused quite a bit of confusion for me, and could be dangerous depending on the lifetimes of the objects involved (one could be left with dangling AAResults references).

Instead of storing a reference inside AAResult, this instead passes in the used AAResults aggregation as part of the query. AAQueryInfo offers a convenient way to do this nowadays. Code doing recursive queries just needs to use AAQI.AAR instead of getBestAAResults().

Diff Detail

Event Timeline

nikic created this revision.Jan 9 2021, 1:14 PM
nikic requested review of this revision.Jan 9 2021, 1:14 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 9 2021, 1:14 PM
nikic added inline comments.Jan 9 2021, 1:15 PM
llvm/lib/Analysis/BasicAliasAnalysis.cpp
764

This is the only place using getBestAAResults() and not having access to AAQueryInfo yet. If the general approach here is okay, I'll thread through AAQI to this method in a separate commit.

Do you have an idea if there is overhead of adding the AAR object to each query (each query info object)? (vs the setAAResults being done once for all the AAs available).

Details/nits:

  • clang-format
  • if approved, this change would need to go in together with the patch threading AAQI to getModRefBehavior.
llvm/include/llvm/Analysis/AliasAnalysis.h
482

Add comment this stands for Aggregated Alias Result?

Do you have an idea if there is overhead of adding the AAR object to each query (each query info object)? (vs the setAAResults being done once for all the AAs available).

It looks like adding AAR to the query doesn't have noticeable overhead: https://llvm-compile-time-tracker.com/compare.php?from=6ee44ee7c3cee47cb070ccb961359df8de252f36&to=9787880b8fe7ed5f62f15eaeed561a6ce09fdfd6&stat=instructions

There is however a small cost to passing AAQI through getModRefBehavior: https://llvm-compile-time-tracker.com/compare.php?from=33be50daa9ce1074c3b423a4ab27c70c0722113a&to=6ee44ee7c3cee47cb070ccb961359df8de252f36&stat=instructions

dfukalov added inline comments.
llvm/include/llvm/Analysis/AliasAnalysis.h
922–925

Am I right AAResults &AA member is not needed anymore?

nikic updated this revision to Diff 463193.Sep 27 2022, 5:19 AM
nikic added a reviewer: reames.

Rebase. I made an error in my previous compile-time test, it turns out that this change has no significant impact after all.

The original motivation for this patch mostly went away, but I still think that doing this is a good idea. Our current AA infrastructure is really complicated, with some convoluted layering of 7 different classes (AAResults, BatchAAResults, AAQueryInfo, AAResults::Concept, AAResults::Model, AAResultBase and AAResultsProxy).

This patch removes the AAResultsProxy part of the equation. An immediate followup would be to make AAResultBase non-CRTP (this patch leaves behind an unused template argument). Possible followups on top of that would be:

  • Make AAResultBase virtual itself and drop the AAResults::Concept and AAResults::Model indirections. I gave this a try but it turned out to be not entirely straightforward due to some NewPM interaction, but should be principally possible now.
  • Make methods that take AAQueryInfo member methods of AAQueryInfo. This should prevent accidentally not passing on AAQI. With this BatchAAResults would reduce down to AAQueryInfo, we could just make it an alias.
Herald added a project: Restricted Project. · View Herald TranscriptSep 27 2022, 5:19 AM

FWIW, (and drive by) this looks like a more reasonable design.

asbirlea accepted this revision.Oct 5 2022, 9:53 AM

Rebase. I made an error in my previous compile-time test, it turns out that this change has no significant impact after all.

The original motivation for this patch mostly went away, but I still think that doing this is a good idea. Our current AA infrastructure is really complicated, with some convoluted layering of 7 different classes (AAResults, BatchAAResults, AAQueryInfo, AAResults::Concept, AAResults::Model, AAResultBase and AAResultsProxy).

This patch removes the AAResultsProxy part of the equation. An immediate followup would be to make AAResultBase non-CRTP (this patch leaves behind an unused template argument). Possible followups on top of that would be:

  • Make AAResultBase virtual itself and drop the AAResults::Concept and AAResults::Model indirections. I gave this a try but it turned out to be not entirely straightforward due to some NewPM interaction, but should be principally possible now.
  • Make methods that take AAQueryInfo member methods of AAQueryInfo. This should prevent accidentally not passing on AAQI. With this BatchAAResults would reduce down to AAQueryInfo, we could just make it an alias.

The current design is much better IMO than what we had before.

If you make private the AAR inside AAQI and expose methods only, then instead of calling:

AAQI.AAR.alias(MemoryLocation::getBeforeOrAfter(*CI),
                         MemoryLocation::getBeforeOrAfter(Object), AAQI);

you'd call:

AAQI.alias(MemoryLocation::getBeforeOrAfter(*CI),
                   MemoryLocation::getBeforeOrAfter(Object), <OptionalNewAAQI>);

I think this is what you meant with "prevent accidentally not passing on AAQI". It's not a huge cleanup though, since there still needs to be an AAQI param for the recursive phi case when a new one's needed.


Is this comment outdated, or did we still have a case where the AAR could be null?

/// A pointer to the AAResults object that this AAResult is
/// aggregated within. May be null if not aggregated.
This revision is now accepted and ready to land.Oct 5 2022, 9:53 AM
nikic added a comment.Oct 5 2022, 12:45 PM

If you make private the AAR inside AAQI and expose methods only, then instead of calling:

AAQI.AAR.alias(MemoryLocation::getBeforeOrAfter(*CI),
                         MemoryLocation::getBeforeOrAfter(Object), AAQI);

you'd call:

AAQI.alias(MemoryLocation::getBeforeOrAfter(*CI),
                   MemoryLocation::getBeforeOrAfter(Object), <OptionalNewAAQI>);

I think this is what you meant with "prevent accidentally not passing on AAQI". It's not a huge cleanup though, since there still needs to be an AAQI param for the recursive phi case when a new one's needed.

Yes, that's basically what I had in mind. I don't think the OptionalNewAAQI argument is necessary though, you'd just call it on the new AAQueryInfo instance. The call in https://github.com/llvm/llvm-project/blob/5f7f4846e826f97c7f298fe419c958398d5a0386/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L1449-L1450 would become UseAAQI->alias(MemoryLocation(...), MemoryLocation(...)).

Is this comment outdated, or did we still have a case where the AAR could be null?

/// A pointer to the AAResults object that this AAResult is
/// aggregated within. May be null if not aggregated.

It can be null if you construct a single AA provider by hand, but not as part of normal usage via the pass manager.

This revision was landed with ongoing or failed builds.Oct 6 2022, 1:10 AM
This revision was automatically updated to reflect the committed changes.