[PM] Teach the AAManager and AAResults layer (the worst offender for inter-analysis dependencies) to use the new invalidation infrastructure.

[chandlerc]

Summary

This teaches it to invalidate itself when any of the peer function
AA results that it uses become invalid. We do this by just tracking the
originating IDs. I've kept it in a somewhat clunky API since some users
of AAResults are outside the new PM right now. We can clean this API up
if/when those users go away.

Secondly, it uses the registration on the outer analysis manager proxy
to trigger deferred invalidation when a module analysis result becomes
invalid.

I've included test cases that specifically try to trigger use-after-free
in both of these cases and they would crash or hang pretty horribly for
me even without ASan. Now they work nicely.

The "InvalidateAnalysis" utility pass required some tweaking to be
useful in this context and it still is pretty garbage. I'd like to
switch it back to the previous implementation and teach the explicit
invalidate method on the AnalysisManager to take care of correctly
triggering indirect invalidation, but I wanted to go ahead and send this
out so folks could see how all of this stuff works together in practice.
And, you know, that it does actually work. =]

Depends on D27198.

[silvas]

This is just wiring up the new machinery from D27198. Looks good.

You may want to consider in a separate patch breaking the new PM tests into a new directory (instead of just a single main huge file in test/Other). Lit's test failure diagnostics tend to be better for separate files.

[jlebar]

include/llvm/Analysis/AliasAnalysis.h

206

A thought: It would be cool if our system allowed you to check somehow that this is specifically a function analysis, even if only in debug builds. (This relates back to e.g. https://reviews.llvm.org/D27198#inline-236718.)

[chandlerc]

include/llvm/Analysis/AliasAnalysis.h

206

Just wanted to mention I'm not ignoring this, and will be thinking about a clean way to introduce it without complicating things too much.

include/llvm/Analysis/AliasAnalysis.h

public:
   /// Register a specific AA result.
   template <typename AAResultT> void addAAResult(AAResultT &AAResult) {
     // FIXME: We should use a much lighter weight system than the usual
     // polymorphic pattern because we don't own AAResult. It should
     // ideally involve two pointers and no separate allocation.
     AAs.emplace_back(new Model<AAResultT>(AAResult, *this));
   }
 
+  /// Register a function analysis ID that the results aggregation depends on.
+  ///
+  /// This is used in the new pass manager to implement the invalidation logic
+  /// where we must invalidate the results aggregation if any of our component
+  /// analyses become invalid.
+  void addAADependencyID(AnalysisKey *ID) {
+    AADeps.push_back(ID);
+  }
+
+  /// Handle invalidation events in the new pass manager.
+  ///
+  /// The aggregation is invalidated if any of the underlying analyses is
+  /// invalidated.
+  bool invalidate(Function &F, const PreservedAnalyses &PA,
+                  FunctionAnalysisManager::Invalidator &Inv);
+
   //===--------------------------------------------------------------------===//
   /// \name Alias Queries
   /// @{
 
   /// The main low level interface to the alias analysis implementation.
   /// Returns an AliasResult indicating whether the two pointers are aliased to
   /// each other. This is the interface that must be implemented by specific
   /// alias analysis implementations.
private:
   class Concept;
   template <typename T> class Model;
 
   template <typename T> friend class AAResultBase;
 
   const TargetLibraryInfo &TLI;
 
   std::vector<std::unique_ptr<Concept>> AAs;
+
+  std::vector<AnalysisKey *> AADeps;
 };
 
 /// Temporary typedef for legacy code that uses a generic \c AliasAnalysis
 /// pointer or reference.
 typedef AAResults AliasAnalysis;
 
 /// A private abstract base class describing the concept of an individual alias
 /// analysis implementation.
SmallVector<void (*)(Function &F, FunctionAnalysisManager &AM,
                        AAResults &AAResults),
               4> ResultGetters;
 
   template <typename AnalysisT>
   static void getFunctionAAResultImpl(Function &F,
                                       FunctionAnalysisManager &AM,
                                       AAResults &AAResults) {
     AAResults.addAAResult(AM.template getResult<AnalysisT>(F));
+    AAResults.addAADependencyID(AnalysisT::ID());
   }
 
   template <typename AnalysisT>
   static void getModuleAAResultImpl(Function &F, FunctionAnalysisManager &AM,
                                     AAResults &AAResults) {
-    auto &MAM =
-        AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
-    if (auto *R = MAM.template getCachedResult<AnalysisT>(*F.getParent()))
+    auto &MAMProxy =
+        AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
+    auto &MAM = MAMProxy.getManager();
+    if (auto *R = MAM.template getCachedResult<AnalysisT>(*F.getParent())) {
       AAResults.addAAResult(*R);
+      MAMProxy
+          .template registerOuterAnalysisInvalidation<AnalysisT, AAManager>();
+    }
   }
 };
 
 /// A wrapper pass to provide the legacy pass manager access to a suitably
 /// prepared AAResults object.
 class AAResultsWrapperPass : public FunctionPass {
   std::unique_ptr<AAResults> AAR;
 

include/llvm/IR/PassManager.h

struct InvalidateAnalysisPass
   /// \brief Run this pass over some unit of IR.
   ///
   /// This pass can be run over any unit of IR and use any analysis manager
   /// provided they satisfy the basic API requirements. When this pass is
   /// created, these methods can be instantiated to satisfy whatever the
   /// context requires.
   template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
   PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&...) {
-    // We have to directly invalidate the analysis result as we can't
-    // enumerate all other analyses and use the preserved set to control it.
-    AM.template invalidate<AnalysisT>(Arg);
-
-    return PreservedAnalyses::all();
+    auto PA = PreservedAnalyses::all();
+    PA.abandon<AnalysisT>();
+    return PA;
   }
 };
 
 /// \brief A utility pass that does nothing but preserves no analyses.
 ///
 /// As a consequence fo not preserving any analyses, this pass will force all
 /// analysis passes to be re-run to produce fresh results if any are needed.
 struct InvalidateAllAnalysesPass : PassInfoMixin<InvalidateAllAnalysesPass> {

lib/Analysis/AliasAnalysis.cpp

 #include "llvm/Pass.h"
 using namespace llvm;
 
 /// Allow disabling BasicAA from the AA results. This is particularly useful
 /// when testing to isolate a single AA implementation.
 static cl::opt<bool> DisableBasicAA("disable-basicaa", cl::Hidden,
                                     cl::init(false));
 
-AAResults::AAResults(AAResults &&Arg) : TLI(Arg.TLI), AAs(std::move(Arg.AAs)) {
+AAResults::AAResults(AAResults &&Arg)
+    : TLI(Arg.TLI), AAs(std::move(Arg.AAs)), AADeps(std::move(Arg.AADeps)) {
   for (auto &AA : AAs)
     AA->setAAResults(this);
 }
 
 AAResults::~AAResults() {
 // FIXME; It would be nice to at least clear out the pointers back to this
 // aggregation here, but we end up with non-nesting lifetimes in the legacy
 // pass manager that prevent this from working. In the legacy pass manager
 // we'll end up with dangling references here in some cases.
 #if 0
   for (auto &AA : AAs)
     AA->setAAResults(nullptr);
 #endif
 }
 
+bool AAResults::invalidate(Function &F, const PreservedAnalyses &PA,
+                           FunctionAnalysisManager::Invalidator &Inv) {
+  if (PA.areAllPreserved())
+    return false; // Nothing to do, everything is still valid.
+
+  // Check if the AA manager itself has been invalidated.
+  if (!PA.preserved<AAManager, AllAnalysesOn<Function>>())
+    return true; // The manager needs to be blown away, clear everything.
+
+  // Check all of the dependencies registered.
+  for (AnalysisKey *ID : AADeps)
+    if (Inv.invalidate(ID, F, PA))
+      return true;
+
+  // Everything we depend on is still fine, so are we. Nothing to invalidate.
+  return false;
+}
+
 //===----------------------------------------------------------------------===//
 // Default chaining methods
 //===----------------------------------------------------------------------===//
 
 AliasResult AAResults::alias(const MemoryLocation &LocA,
                              const MemoryLocation &LocB) {
   for (const auto &AA : AAs) {
     auto Result = AA->alias(LocA, LocB);

test/Other/new-pass-manager.ll

 ; CHECK-FUNCTION-PASS-NEXT: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager -passes=print %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-MODULE-PRINT
 ; CHECK-MODULE-PRINT: Starting llvm::Module pass manager run
 ; CHECK-MODULE-PRINT: Running pass: VerifierPass
 ; CHECK-MODULE-PRINT: Running pass: PrintModulePass
 ; CHECK-MODULE-PRINT: ModuleID
-; CHECK-MODULE-PRINT: define void @foo(i1 %x)
+; CHECK-MODULE-PRINT: define void @foo(i1 %x, i8* %p1, i8* %p2)
 ; CHECK-MODULE-PRINT: Running pass: VerifierPass
 ; CHECK-MODULE-PRINT: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager -disable-verify -passes='print,verify' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-MODULE-VERIFY
 ; CHECK-MODULE-VERIFY: Starting llvm::Module pass manager run
 ; CHECK-MODULE-VERIFY: Running pass: PrintModulePass
 ; CHECK-MODULE-VERIFY: ModuleID
-; CHECK-MODULE-VERIFY: define void @foo(i1 %x)
+; CHECK-MODULE-VERIFY: define void @foo(i1 %x, i8* %p1, i8* %p2)
 ; CHECK-MODULE-VERIFY: Running pass: VerifierPass
 ; CHECK-MODULE-VERIFY: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager -passes='function(print)' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-FUNCTION-PRINT
 ; CHECK-FUNCTION-PRINT: Starting llvm::Module pass manager run
 ; CHECK-FUNCTION-PRINT: Running pass: VerifierPass
 ; CHECK-FUNCTION-PRINT: Running pass: ModuleToFunctionPassAdaptor
 ; CHECK-FUNCTION-PRINT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
 ; CHECK-FUNCTION-PRINT: Starting llvm::Function pass manager run
 ; CHECK-FUNCTION-PRINT: Running pass: PrintFunctionPass
 ; CHECK-FUNCTION-PRINT-NOT: ModuleID
-; CHECK-FUNCTION-PRINT: define void @foo(i1 %x)
+; CHECK-FUNCTION-PRINT: define void @foo(i1 %x, i8* %p1, i8* %p2)
 ; CHECK-FUNCTION-PRINT: Finished llvm::Function pass manager run
 ; CHECK-FUNCTION-PRINT: Running pass: VerifierPass
 ; CHECK-FUNCTION-PRINT: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager -disable-verify -passes='function(print,verify)' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-FUNCTION-VERIFY
 ; CHECK-FUNCTION-VERIFY: Starting llvm::Module pass manager run
 ; CHECK-FUNCTION-VERIFY: Starting llvm::Function pass manager run
 ; CHECK-FUNCTION-VERIFY: Running pass: PrintFunctionPass
 ; CHECK-FUNCTION-VERIFY-NOT: ModuleID
-; CHECK-FUNCTION-VERIFY: define void @foo(i1 %x)
+; CHECK-FUNCTION-VERIFY: define void @foo(i1 %x, i8* %p1, i8* %p2)
 ; CHECK-FUNCTION-VERIFY: Running pass: VerifierPass
 ; CHECK-FUNCTION-VERIFY: Finished llvm::Function pass manager run
 ; CHECK-FUNCTION-VERIFY: Finished llvm::Module pass manager run
 
 ; RUN: opt -S -o - -passes='no-op-module,no-op-module' %s \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-NOOP
-; CHECK-NOOP: define void @foo(i1 %x) {
+; CHECK-NOOP: define void @foo(i1 %x, i8* %p1, i8* %p2) {
 ; CHECK-NOOP: entry:
+; CHECK-NOOP:   store i8 42, i8* %p1
 ; CHECK-NOOP:   br i1 %x, label %loop, label %exit
 ; CHECK-NOOP: loop:
+; CHECK-NOOP:   %tmp1 = load i8, i8* %p2
 ; CHECK-NOOP:   br label %loop
 ; CHECK-NOOP: exit:
 ; CHECK-NOOP:   ret void
 ; CHECK-NOOP: }
 
 ; Round trip through bitcode.
 ; RUN: opt -f -o - -passes='no-op-module,no-op-module' %s \
 ; RUN:     | llvm-dis \

 ; RUN:     | FileCheck %s --check-prefix=CHECK-AA
 ; CHECK-AA: Starting llvm::Module pass manager run
 ; CHECK-AA: Running pass: RequireAnalysisPass
 ; CHECK-AA: Running analysis: AAManager
 ; CHECK-AA: Running analysis: BasicAA
 ; CHECK-AA: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \
+; RUN:     -passes='require<aa>,invalidate<basic-aa>,aa-eval' -aa-pipeline='basic-aa' \
+; RUN:     | FileCheck %s --check-prefix=CHECK-AA-FUNCTION-INVALIDATE
+; CHECK-AA-FUNCTION-INVALIDATE: Starting llvm::Function pass manager run
+; CHECK-AA-FUNCTION-INVALIDATE: Running pass: RequireAnalysisPass
+; CHECK-AA-FUNCTION-INVALIDATE: Running analysis: AAManager
+; CHECK-AA-FUNCTION-INVALIDATE: Running analysis: BasicAA
+; CHECK-AA-FUNCTION-INVALIDATE: Running pass: InvalidateAnalysisPass
+; CHECK-AA-FUNCTION-INVALIDATE: Invalidating analysis: BasicAA
+; CHECK-AA-FUNCTION-INVALIDATE: Invalidating analysis: AAManager
+; CHECK-AA-FUNCTION-INVALIDATE: Running pass: AAEvaluator
+; CHECK-AA-FUNCTION-INVALIDATE: Running analysis: AAManager
+; CHECK-AA-FUNCTION-INVALIDATE: Running analysis: BasicAA
+; CHECK-AA-FUNCTION-INVALIDATE: Finished llvm::Function pass manager run
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \
+; RUN:     -passes='require<globals-aa>,function(require<aa>),invalidate<globals-aa>,require<globals-aa>,function(aa-eval)' -aa-pipeline='globals-aa' \
+; RUN:     | FileCheck %s --check-prefix=CHECK-AA-MODULE-INVALIDATE
+; CHECK-AA-MODULE-INVALIDATE: Starting llvm::Module pass manager run
+; CHECK-AA-MODULE-INVALIDATE: Running pass: RequireAnalysisPass
+; CHECK-AA-MODULE-INVALIDATE: Running analysis: GlobalsAA
+; CHECK-AA-MODULE-INVALIDATE: Starting llvm::Function pass manager run
+; CHECK-AA-MODULE-INVALIDATE: Running pass: RequireAnalysisPass
+; CHECK-AA-MODULE-INVALIDATE: Running analysis: AAManager
+; CHECK-AA-MODULE-INVALIDATE: Finished llvm::Function pass manager run
+; CHECK-AA-MODULE-INVALIDATE: Running pass: InvalidateAnalysisPass
+; CHECK-AA-MODULE-INVALIDATE: Invalidating analysis: AAManager
+; CHECK-AA-MODULE-INVALIDATE: Invalidating analysis: GlobalsAA
+; CHECK-AA-MODULE-INVALIDATE: Running pass: RequireAnalysisPass
+; CHECK-AA-MODULE-INVALIDATE: Running analysis: GlobalsAA
+; CHECK-AA-MODULE-INVALIDATE: Starting llvm::Function pass manager run
+; CHECK-AA-MODULE-INVALIDATE: Running pass: AAEvaluator
+; CHECK-AA-MODULE-INVALIDATE: Running analysis: AAManager
+; CHECK-AA-MODULE-INVALIDATE: Finished llvm::Function pass manager run
+; CHECK-AA-MODULE-INVALIDATE: Finished llvm::Module pass manager run
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \
 ; RUN:     -passes='require<memdep>' \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-MEMDEP
 ; CHECK-MEMDEP: Starting llvm::Module pass manager run
 ; CHECK-MEMDEP: Running pass: RequireAnalysisPass
 ; CHECK-MEMDEP: Running analysis: MemoryDependenceAnalysis
 ; CHECK-MEMDEP: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \

 ; CHECK-REPEAT-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running pass: NoOpLoopPass
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Finished llvm::Function pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Finished llvm::Module pass manager run
 
-define void @foo(i1 %x) {
+define void @foo(i1 %x, i8* %p1, i8* %p2) {
 entry:
+  store i8 42, i8* %p1
   br i1 %x, label %loop, label %exit
 
 loop:
+  %tmp1 = load i8, i8* %p2
   br label %loop
 
 exit:
   ret void
 }
 
 declare void @bar()