Require chained analyses in BasicAA and AAResults to be transitive

[bjope]

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

[foad]

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]

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.

[bjope]

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.

[nikic]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

550

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

[nikic]

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

[bjope]

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.

llvm/lib/Analysis/AliasAnalysis.cpp

 //==- AliasAnalysis.cpp - Generic Alias Analysis Interface Implementation --==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
if (WrapperPass->CB)
       WrapperPass->CB(*this, F, *AAR);
 
   // Analyses don't mutate the IR, so return false.
   return false;
 }
 
 void AAResultsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
-  AU.addRequired<BasicAAWrapperPass>();
-  AU.addRequired<TargetLibraryInfoWrapperPass>();
+  AU.addRequiredTransitive<BasicAAWrapperPass>();
+  AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
 
   // We also need to mark all the alias analysis passes we will potentially
   // probe in runOnFunction as used here to ensure the legacy pass manager
   // preserves them. This hard coding of lists of alias analyses is specific to
   // the legacy pass manager.
   AU.addUsedIfAvailable<ScopedNoAliasAAWrapperPass>();
   AU.addUsedIfAvailable<TypeBasedAAWrapperPass>();
   AU.addUsedIfAvailable<objcarc::ObjCARCAAWrapperPass>();

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 //===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F,
                                  LIWP ? &LIWP->getLoopInfo() : nullptr,
                                  PVWP ? &PVWP->getResult() : nullptr));
 
   return false;
 }
 
 void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
-  AU.addRequired<AssumptionCacheTracker>();
-  AU.addRequired<DominatorTreeWrapperPass>();
-  AU.addRequired<TargetLibraryInfoWrapperPass>();
+  AU.addRequiredTransitive<AssumptionCacheTracker>();
+  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
+  AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
   AU.addUsedIfAvailable<PhiValuesWrapperPass>();
 }
 
 BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) {
   return BasicAAResult(
       F.getParent()->getDataLayout(), F,
       P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F),
       P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
 }

llvm/lib/Target/Hexagon/HexagonLoopIdiomRecognition.cpp

 //===- HexagonLoopIdiomRecognition.cpp ------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
StringRef getPassName() const override {
     return "Recognize Hexagon-specific loop idioms";
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addRequiredID(LoopSimplifyID);
     AU.addRequiredID(LCSSAID);
     AU.addRequired<AAResultsWrapperPass>();
-    AU.addPreserved<AAResultsWrapperPass>();
     AU.addRequired<ScalarEvolutionWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addPreserved<TargetLibraryInfoWrapperPass>();
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 };

llvm/lib/Transforms/Scalar/GVNHoist.cpp

 //===- GVNHoist.cpp - Hoist scalar and load expressions -------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<PostDominatorTreeWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<MemorySSAWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
-    AU.addPreserved<AAResultsWrapperPass>();
   }
 };
 
 bool GVNHoist::run(Function &F) {
   NumFuncArgs = F.arg_size();
   VN.setDomTree(DT);
   VN.setAliasAnalysis(AA);
   VN.setMemDep(MD);