This is an archive of the discontinued LLVM Phabricator instance.

Require chained analyses in BasicAA and AAResults to be transitive
ClosedPublic

Authored by bjope on Jan 5 2021, 4:09 PM.

Details

Summary

This patch fixes a bug that could result in miscompiles (at least
in an OOT target). The problem could be seen by adding checks that
the DominatorTree used in BasicAliasAnalysis and ValueTracking was
valid (e.g. by adding DT->verify() call before every DT dereference
and then running all tests in test/CodeGen).

Problem was that the LegacyPassManager calculated "last user"
incorrectly for passes such as the DominatorTree when not telling
the pass manager that there was a transitive dependency between
the different analyses. And then it could happen that an incorrect
dominator tree was used when doing alias analysis (which was a pretty
serious bug as the alias analysis result could be invalid).

Diff Detail

Event Timeline

bjope created this revision.Jan 5 2021, 4:09 PM
bjope requested review of this revision.Jan 5 2021, 4:09 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 5 2021, 4:09 PM
bjope added a subscriber: uabelho.
bcain added a subscriber: bcain.Jan 5 2021, 9:04 PM
foad added a subscriber: foad.Jan 6 2021, 6:35 AM
foad added inline comments.
llvm/lib/Analysis/AliasAnalysis.cpp
886

I think this makes sense because a BasicAAResult object can be added to the AAResults object. But what about all the other kinds of AA object that can (optionally) be added? E.g. if we add a SCEVAAResult, doesn't that mean that this pass needs to "transitively require if available" SCEVAAWrapperPass?

887

This makes sense to me, given that the AAResults object has a reference to TLI.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
1878–1880

This makes sense to me, given that the BasicAAResult object has references or pointers to TLI and AC and DT. I wonder how we have got away with it for so long?

llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp
168

Did you try the alternative fix of preserving more stuff instead of less? I.e. preseve everything that is transitively required by AAResultsWrapperPass? Is that hard to do?

llvm/lib/Transforms/Scalar/GVNHoist.cpp
550

Ditto.

bjope added inline comments.Jan 6 2021, 10:08 AM
llvm/lib/Analysis/AliasAnalysis.cpp
886

Right. I don't really now how it works for addUsedIfAvailable (there is no addUsedIfAvailableTransitive). We have the same thing in BasicAliasAnalysis that uses PhiValuesWrapperPass if available.

I'm also a bit unsure about if we should do something with getAAResultsAnalysisUsage at the end of this file as well. That one does not even mention that it require BasicAA, even though createLegacyPMAAResults may add a BasicAA depending on DisableBasicAA.

llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp
168

I don't know if for example DominatorTree is preserved here (I imagined that someone has decided to require but not preserve DominatorTreeWrapperPass here in the past). It felt more safe (a more defensive bugfix) to drop preservation of AAResults.

llvm/lib/Transforms/Scalar/GVNHoist.cpp
550

I did try some different solutions here, but never really figured out exactly what was needed to avoid the assert in setLastUser (also knowing that those transitive analyses actually are preserved).
The solution of not preserving AAResults was inspired by the change above for HexagonLoopIdiomRecognition, but it also matches what it looks like in GVN and NewGVN etc.

Ka-Ka added a subscriber: Ka-Ka.Jan 6 2021, 11:26 PM
markus added a subscriber: markus.Jan 7 2021, 1:11 AM
bjope added inline comments.Jan 7 2021, 5:48 AM
llvm/lib/Analysis/AliasAnalysis.cpp
886

The RequiredTransitive set is only used in one place afaict. Not sure, but maybe we can remove addRequiredTransitive completely and treat all nested required analyses as being requested transitively in setLastUser instead. I don't understand why one would need to choose between addRequired and addRequiredTransitive if one need to use the latter as soon as there are chained analyses (or if there is a use case when it would be wrong/bad to use addRequiredTransitive instead of addRequired.

I think that the above might be worth investigating in a follow-up to this more prioritized bugfix.

Another thing I noticed is that the PreservedSet, RequiredSet etc. are implemented using vectors, and when doing getPreservedSet one could end up getting a vector with duplicates (not really a set). So verifyPreservedAnalysis could end up verifying the same analysis several times. Kind of stupid and a waste of time afaict. This is also something that I see as a candidate for a follow-up commit.

bjope added a reviewer: foad.Jan 9 2021, 4:27 PM
nikic added inline comments.Jan 10 2021, 2:14 AM
llvm/lib/Transforms/Scalar/GVNHoist.cpp
550

As this already preserves DT, possibly this only needs an explicit AU.addPreserved<BasicAAWrapperPass>?

nikic accepted this revision.Jan 10 2021, 2:21 AM

LGTM. I'm not an expert on the pass manager, but after looking into it a bit this seems like the right direction. I don't think not preserving AAResults in HexagonLoopIdiomRecognition/GVNHoist is much of a problem. Preserving AAResults is generally not important (this "analysis" is essentially free) and these are non-default passes anyway.

There is a small compile-time impact, but nothing particularly problematic: https://llvm-compile-time-tracker.com/compare.php?from=3b953e368f2971d4d7632633c0506dbeb8e365b9&to=86074d0a6c35d194feea62e87b0bef7cd8c75ad3&stat=instructions

This revision is now accepted and ready to land.Jan 10 2021, 2:21 AM
bjope added inline comments.Jan 11 2021, 1:48 AM
llvm/lib/Transforms/Scalar/GVNHoist.cpp
550

Yes, adding AU.addPreserved<BasicAAWrapperPass> seem to work as well. However, my intention is to land this as is. The NPM version does not preserve AAResults nor BasicAA so it makes the implementation a bit more equal between the two pass manager implementations.