[PM] Extend the explicit 'invalidate' method API on analysis results to accept an Invalidator that allows them to invalidate themselves if their dependencies are in turn invalidated.

[chandlerc]

Summary

Rather than recording the dependency graph ahead of time when analysis
get results from other analyses, this simply lets each result trigger
the immediate invalidation of any analyses they actually depend on. They
do this in a way that has three nice properties:

1. They don't have to handle transitive dependencies because the infrastructure will recurse for them.
2. The invalidate methods are still called only once. We just dynamically discover the necessary topological ordering, everything is memoized nicely.
3. The infrastructure still provides a default implementation and can access it so that only analyses which have dependencies need to do anything custom.

To make this work at all, the invalidation logic also has to defer the
deletion of the result objects themselves so that they can remain alive
until we have collected the complete set of results to invalidate.

This also requires that we not do the (very questionable) thing where we
mark invalidated analyses as preserved. I originally thought this would
make sense, but it really seems confusing and impractical. The only
reason to do it was to avoid re-invalidating analyses endlessly when
crossing IR-unit boundaries between analysis managers. I've solved that
in the previous patch by just having an IR-unit set, and having pass
manager mark that entire set as preserved. This seems dramatically
simpler and more robust anyways. And as a consequence, we lose nothing
by removing the constant marking of invalidated analyses as preserved.

A unittest is added here that has exactly the dependency pattern we are
concerned with. It hit the use-after-free described by Sean in much
detail in the long thread about analysis invalidation before this
change, and even in an intermediate form of this change where we failed
to defer the deletion of the result objects.

There is an important problem with doing dependency invalidation that
*isn't* solved here: we don't *enforce* that results correctly
invalidate all the analyses whose results they depend on.

I actually looked at what it would take to do that, and it isn't as hard
as I had thought but the complexity it introduces seems very likely to
outweigh the benefit. The technique would be to provide a base class for
an analysis result that would be populated with other results, and
automatically provide the invalidate method which immediately does the
correct thing. This approach has some nice pros IMO:

• Handles the case we care about and nothing else: only *results* that depend on other analyses trigger extra invalidation.
• Localized to the result rather than centralized in the analysis manager.
• Ties the storage of the reference to another result to the triggering of the invalidation of that analysis.
• Still supports extending invalidation in customized ways.

But the down sides here are:

• Very heavy-weight meta-programming is needed to provide this base class.
• Requires a pretty awful API for accessing the dependencies.

Ultimately, I fear it will not pull its weight. But we can re-evaluate
this at any point if we start discovering consistent problems where the
invalidation and dependencies get out of sync. It will fit as a clean
layer on top of the facilities in this patch that we can add if and when
we need it.

Note that I'm not really thrilled with the names for these APIs... The
name "Invalidator" seems ok but not great. The method name "invalidate"
also. But I've not come up with any better naming patterns.

I'm working on the actual fixes to various analyses that need to use these, but
I want to try to get tests for each of them so we don't regress. And those
changes are seperable and obvious so once this goes in I should be able to roll
them out throughout LLVM.

[silvas]

This is a big improvement on the current state of things and can probably get rid of most if not all of the insufficient invalidation issues I was running into without a big refactor to pass stuff into the query path of a ton of analyses.

This is somewhat limited because it only works within a single IRUnit. So it won't cover cases like:

• AAManager (function analysis) can be holding a pointer to GlobalsAA (module analysis)
• LoopAccessAnalysis (loop analysis) holds pointers to various function analysis
• Loop analyses implicitly hold pointers to Loop objects owned by LoopAnalysis. (analogously for CGSCC analyses and LazyCallGraph)

Those will likely not be an issue when running a standard pipeline as long as we don't have any transformations that preserve the inner proxies. E.g. during standard pipelines, when we invalidate module analyses and thus GlobalsAA, as long as transformations don't preserve the module to function proxy, the proxy will clear out the inner analysis manager.

In other words, the approach in this patch depends on having the for-loop in PreservedAnalyses invalidate(IRUnitT &IR, PreservedAnalyses PA) iterate over all analysis results that may need to be invalidated; however, since it is only iterating over the analysis results cached on a single IRUnit, any cross-IRUnit dependencies will not be correctly handled. (the invalidation of the inner proxies will invalidate analysis results cached on any inner IRUnitT's, so the main concern here is analysis results that hold pointers to analyses cached on their outer IRUnitT's or the their same IRUnitT)

IIRC, LoopAccessAnalysis was the only analysis that had data-structure-dependencies on other analyses (it holds SCEV* and Loop*) and so the cross-IRUnit case is probably worth thinking about long-term, even though currently I think we'll get away with it LoopAccessAnalysis getting invalidated by the function to loop proxy during standard pipelines.

FYI I'll be on vacation for the next two weeks, so feel free to move forward with this if others are onboard with the idea. I think this is a nice improvement.

[chandlerc]

In D23738#521875, @silvas wrote:

This is a big improvement on the current state of things and can probably get rid of most if not all of the insufficient invalidation issues I was running into without a big refactor to pass stuff into the query path of a ton of analyses.

This is somewhat limited because it only works within a single IRUnit. So it won't cover cases like:

• AAManager (function analysis) can be holding a pointer to GlobalsAA (module analysis)

Yea, I'm working on a follow-up patch that should address this. It's less pretty, but the fact that it is so much less common makes me hesitant to engineer a more heavyweight solution.

• LoopAccessAnalysis (loop analysis) holds pointers to various function analysis

I'm specifically trying to end up with a solution that will work equally well here and for function analyses using module analyses.

I'll be looking at the loop stuff next though to help validate this or uncover any further issues.

• Loop analyses implicitly hold pointers to Loop objects owned by LoopAnalysis. (analogously for CGSCC analyses and LazyCallGraph)

Both of these I think will be handled by the proxies, but it is certainly something that needs to be dealt with.

[chandlerc]

Rebase and incorporate the changes to the CGSCC layer. No substantial changes
though.

[chandlerc]

Ping...

[chandlerc]

Ping and adding Justin explicitly as we talked about this at the last social...

[chandlerc]

Rebase and ping...

[chandlerc]

Rebase and ping...

[jlebar]

I am still trying to understand why we've designed it this way, but here are some comments on comments.

include/llvm/IR/PassManager.h

357

I can't figure out what "half of a bijection" is, and this phrase apparently appears nowhere on the internet other than in this file. Can we rephrase?

357

Comma before "and" -- new independent clause.

361

An IRUnitT is not necessarily a function pointer, nor a pointer to an llvm::Function, right?

364

same here wrt "function pointer"

365

This comment in particular, but also the one above, just sort of spells out in English what the type is. It's definitely helpful to tell me what "void*" is, but you could write that as

std::pair</* AnalysisID */ void*, IRUnit *>

or even

using AnalysisID = void*;
std::pair<AnalysisID, IRUnit *>

Once we've made the code clearer in this way, perhaps we could use the comments to say something about what these types are for.

373–424

comma before "to"

377

Rephrase beginning at "and" -- bad parallelism.

378

Nit, we don't really pass the API per se. "We pass in an Invalidator", perhaps?

380

Rephrase starting with "rather than". I think this is important, because it's kind of the motivation for the whole design, but I don't grok what you're trying to get across.

395

"look up" is still the verb form. I am losing this fight, but I have at least a few more years before the space is gone forever. (The space makes the written form of the verb match the spoken form, which has two accented syllables -- the spoken noun form has only one accented syllable -- "LOOKup TAble", versus "LOOK UP 'TAble' in the dictionary".)

570

Kind of runs on -- split into two sentences?

Track whether each pass's result is invalidated.  Memoize the results using the IsResultInvalidated map.

575

type-erased

575

s/where/whereas/

575

s/but/and

576

again s/where/whereas/ (or "while") would help, I think.

Or maybe just

This is basically the same thing as Invalidator::invalidate, but we can't call it here because we're operating on the type-erased result.  Moreover if we instead called invalidate() directly, it would do an unnecessary lookup in ResultsList.

Or maybe even leave out that second sentence, because it's a premature optimization. :)

584

s/invalidator/Invalidator/?

594

No need to set up a contrast, I think. Maybe simply

Now erase the results that were invalidated.

604

(I don't know why we have both a list and a map when we have things like MapVector, but...okay, let's assume there's a good reason for this. :)

include/llvm/IR/PassManagerInternal.h

110

Based on this comment I have no idea what I am supposed to do with the InvalidatorT object.

lib/Analysis/CGSCCPassManager.cpp

74

Invaliadtion

(I wonder how hard it would be to make a good C++ spellchecker. You could imagine a tool that spellchecks only comments, and doesn't flag tokens that appear elsewhere in the code (outside comments)... Catching these typos doesn't seem like a good job for hoomans.)

((Now I'm thinking about using whatever tech Chrome's online spellchecker -- which is hauntingly accurate -- uses, not just to catch typos in comments, but also bugs in code...))

77

I don't understand this comment, particularly "with a set".

unittests/IR/PassManagerTest.cpp

392

s/analyses/analysis/

393

Kind of a run-on sentence, maybe split?

426

Can this constructor just take an std::function instead? That would mean you have to spell out the type of the std::function twice, but I think it would be more explicit.

450

Nit, missing period.

458

The "for one function invalidate" form is awkward for me. Maybe this would be easier to read as a bulleted list:

Next, invalidate
  - the indirect analysis for g(),
  - the underlying analysis for h(), and
  - both analyses for f().

It might also make sense to rejigger the code so that we can change the comment to read "f()", "g()", and "h()".

469

comma before "forcing"

479

ecah

483

sp, indiract

is invalidated

484

Not sure "total" is helpful.

488

Again not sure the second "total" helps.

[jlebar]

include/llvm/IR/PassManager.h

591

WRT the names:

I agree "invalidate" isn't a great name, because

if (!my_pass->invalidate(...)) {
  // my_pass was not invalidated!
}

checkIfInvalidated? onIRChange? notifyIRChanged? I like the first one because the bool return value sort of makes sense.

This would also change the comment above -- we're not really "trying" to invalidate the result. More informing it that something has changed, and giving it the option to mark itself as invalid.

I still don't really understand what we're supposed to do inside the invalidate function, so I'm not sure about the Invalidator class name. The only example I have is

bool TestIndirectFunctionAnalysis::invalidate(Function &F, const PreservedAnalyses &PA,
                FunctionAnalysisManager::Invalidator &Inv) {
  return !PA.preserved<TestIndirectFunctionAnalysis>() ||
         Inv.invalidate<TestFunctionAnalysis>(F, PA);
}

It naively seems to me that it would be better to structure things so that we never run this function if PA.preserved<TestIndirectFunctionAnalysis>(). The Invalidator could ensure this. Then our function could be

bool checkIfInvalidated(...) {
  return Inv.checkIfInvalidated<Dep1>() || Inv.checkIfInvalidated<Dep2>();
}

which actually makes sense to me. I think ideally Inv.checkIfInvalidated would take zero parameters, since it's just boilerplate, but maybe it should still take the Function/Module/whatever. We'd at least be able to get rid of the PreservedAnalyses argument, I think?

[silvas]

include/llvm/IR/PassManager.h

591

Currently, the invalidate method is a way to opt out of being invalidated (e.g. for TTI which knows it only depends on the target).

However, this cannot trigger invalidation of additional analysis result objects, which is what is needed when one analysis result holds pointers to another analysis results in order to avoid use-after free errors[1]. Hence the addition of the extra invalidation machinery in this patch. (this patch is by no means a comprehensive solution; I mentioned some problem areas in the initial comment in this review).

The Invalidator that is added in this patch basically provides a constrained interface to the analysis result list so that analysis result objects can transitively find and check whether any analysis result objects that they hold a pointer to have been invalidated. This allows invalidation to propagate from dependencies to dependents and trigger additional invalidation, avoiding use-after-free. (for layering reasons, analyses cannot know what will depend on them, but only what they depend on, so to do this with object recursion requires this process to be top-down dependent-to-dependency relying on memoization, rather than bottom-up dependency-to-dependent with a direct traversal)

Also, unfortunately, it is not entirely practical to avoid calling the invalidate method when PA.preserved<FooAnalysis>() is true. The difficulty again occurs when analysis result objects for FooAnalysis hold pointers to other analysis result objects. In that case, transformation passes would have to call PA.preserve<BarAnalysis>() for every analysis that FooAnalysis result objects transitively hold a pointer to (otherwise there would be a dangling pointer / use-after-free error when the BarAnalysis result object is invalidated due to not being in the "preserved" set). There is actually an additional difficulty due to AliasAnalysis, which depends on a dynamic (but fixed for a given pass pipeline invocation) set of type-erased analyses; hence there is no static set of PA.preserve<...>() calls which is necessarily correct.

I don't think that the PreservedAnalyses argument can be eliminated, because the !PA.preserved<FooAnalysis>() check is essentially the base-case of the object recursion facilitated by the Invalidator. I.e. it determines the roots from which invalidation must be propagated from dependency to dependent (although for layering reasons the object recursion goes from dependent to dependency, with memoization to keep the complexity under control).

[1] This is actually pervasive. Running any non-trivial pipeline on any non-trivial piece of code will currently trigger numerous use-after free errors with the new pass manager.

[chandlerc]

Whew, finally through this. Thanks so much Justin for the review. Responses to a few issues inline, and an updated patch on its way.

include/llvm/IR/PassManager.h

361

Just a stale comment.

365

True, the comment here is just trying to explain the type itself. The members below that use them I think have more helpful comments?

I could try to clean up the type names with aliases and remove the comments if you like. But maybe in a follow-up patch? It seems orthogonal to what this is trying to do.

I've cleaned up the comments very minorly here, but not in any way that substantively addresses this.

380

I've tried to clarify this. Keep complaining until it makes sense though.

576

I like your wording much better than mine. Stolen.

And I still want to document that we're dodging a map lookup -- if we go back, the author should be aware of this even if it is worth the tradeoff.

591

First and foremost, I'm down with renaming this, but I'd really like that to be a separate patch. It'll be a ton of boring changes that I don't want to try and juggle in this commit.

Second, regarding the preserved analysis argument and the IR unit argument: I think they both have good reasons to exist.

1. Transformations may want to preserve an entire set of analyses, and analyses should query in the preserved analyses to see if a set that covers them has been preserved even if the individual analyses has not been.
2. Analyses may want to check trivial information about the IR to determine from first principles that they have been preserved.

And as Sean points out, this is really just about adding the first of several pieces of infrastructure necessary to make invalidation reliable.

I'd like to brainstorm different names for this outside the review though to see if there is a clearly superior alternative.

include/llvm/IR/PassManagerInternal.h

110

Yea, I failed to update this. Fixed.

lib/Analysis/CGSCCPassManager.cpp

77

Tried better words.

unittests/IR/PassManagerTest.cpp

458

Not sure what rejiggering you had in mind here, but the comment seems sane now?

[chandlerc]

Update with fixes to Justin's comments.

[chandlerc]

Rebase now that we're using more clear types for the static key which is used
to compute an analysis ID.

[chandlerc]

Rebase, especially picking up some more underlying refactorings and
improvements that simplify this patch.

[jlebar]

This looks good to me!

include/llvm/IR/PassManager.h

357

Is "pass ID" still the right way to describe the first element of the pair?

385

Should we comment what this returns? It's not obvious to me from the name, and the body is nontrivial.

591

I think I understand why you want the three args; thanks Sean and Chandler for the explanation.

I'd like to brainstorm different names for this outside the review though to see if there is a clearly superior alternative.

sgtm. What is the right venue for this discussion? We can seed it with my comment from above.

include/llvm/IR/PassManagerInternal.h

106

s/analises/analyses'/?

unittests/IR/PassManagerTest.cpp

458

Yes, seems sane now.

[chandlerc]

Thanks so much! Submitting with suggested changes and getting the next patch in my queue ready for review.

include/llvm/IR/PassManager.h

357

switched to 'analysis ID' which seems more clear.

385

Yea, this was just completely missing documentation. Added. Happy to tweak and/or improve in follow-up commits.

591

I'll chat with you and maybe others on IRC first to get some ideas, and then I'll send a dedicated patch to do this.

include/llvm/Analysis/CFLAndersAliasAnalysis.h

 
 public:
   explicit CFLAndersAAResult(const TargetLibraryInfo &);
   CFLAndersAAResult(CFLAndersAAResult &&);
   ~CFLAndersAAResult();
 
   /// Handle invalidation events from the new pass manager.
   /// By definition, this result is stateless and so remains valid.
-  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &) {
+    return false;
+  }
   /// Evict the given function from cache
   void evict(const Function &Fn);
 
   /// \brief Get the alias summary for the given function
   /// Return nullptr if the summary is not found or not available
   const cflaa::AliasSummary *getAliasSummary(const Function &);
 
   AliasResult query(const MemoryLocation &, const MemoryLocation &);

include/llvm/Analysis/CFLSteensAliasAnalysis.h

 public:
   explicit CFLSteensAAResult(const TargetLibraryInfo &);
   CFLSteensAAResult(CFLSteensAAResult &&Arg);
   ~CFLSteensAAResult();
 
   /// Handle invalidation events from the new pass manager.
   ///
   /// By definition, this result is stateless and so remains valid.
-  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &) {
+    return false;
+  }
 
   /// \brief Inserts the given Function into the cache.
   void scan(Function *Fn);
 
   void evict(Function *Fn);
 
   /// \brief Ensures that the given function is available in the cache.
   /// Returns the appropriate entry from the cache.

include/llvm/Analysis/CGSCCPassManager.h

 #include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 struct CGSCCUpdateResult;
 
+/// Extern template declaration for the analysis set for this IR unit.
+extern template class AllAnalysesOn<LazyCallGraph::SCC>;
+
 extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
 /// \brief The CGSCC analysis manager.
 ///
 /// See the documentation for the AnalysisManager template for detail
 /// documentation. This typedef serves as a convenient way to refer to this
 /// construct in the adaptors and proxies used to integrate this into the larger
 /// pass manager infrastructure.
 typedef AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>

include/llvm/Analysis/ObjCARCAliasAnalysis.h

 public:
   explicit ObjCARCAAResult(const DataLayout &DL) : AAResultBase(), DL(DL) {}
   ObjCARCAAResult(ObjCARCAAResult &&Arg)
       : AAResultBase(std::move(Arg)), DL(Arg.DL) {}
 
   /// Handle invalidation events from the new pass manager.
   ///
   /// By definition, this result is stateless and so remains valid.
-  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &) {
+    return false;
+  }
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
 
   using AAResultBase::getModRefBehavior;
   FunctionModRefBehavior getModRefBehavior(const Function *F);
 
   using AAResultBase::getModRefInfo;

include/llvm/Analysis/ScopedNoAliasAA.h

 /// A simple AA result which uses scoped-noalias metadata to answer queries.
 class ScopedNoAliasAAResult : public AAResultBase<ScopedNoAliasAAResult> {
   friend AAResultBase<ScopedNoAliasAAResult>;
 
 public:
   /// Handle invalidation events from the new pass manager.
   ///
   /// By definition, this result is stateless and so remains valid.
-  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &) {
+    return false;
+  }
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
 
 private:
   bool mayAliasInScopes(const MDNode *Scopes, const MDNode *NoAlias) const;
 };

include/llvm/Analysis/TargetLibraryInfo.h

if (Impl->ShouldExtI32Return)
       return Signed ? Attribute::SExt : Attribute::ZExt;
     return Attribute::None;
   }
 
   /// Handle invalidation from the pass manager.
   ///
   /// If we try to invalidate this info, just return false. It cannot become
   /// invalid even if the module or function changes.
-  bool invalidate(Module &, const PreservedAnalyses &) { return false; }
-  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
+  bool invalidate(Module &, const PreservedAnalyses &,
+                  ModuleAnalysisManager::Invalidator &) {
+    return false;
+  }
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &) {
+    return false;
+  }
 };
 
 /// Analysis pass providing the \c TargetLibraryInfo.
 ///
 /// Note that this pass's result cannot be invalidated, it is immutable for the
 /// life of the module.
 class TargetLibraryAnalysis : public AnalysisInfoMixin<TargetLibraryAnalysis> {
 public:

include/llvm/Analysis/TargetTransformInfo.h

public:
   // out-of-line.
   ~TargetTransformInfo();
 
   /// \brief Handle the invalidation of this information.
   ///
   /// When used as a result of \c TargetIRAnalysis this method will be called
   /// when the function this was computed for changes. When it returns false,
   /// the information is preserved across those changes.
-  bool invalidate(Function &, const PreservedAnalyses &) {
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &) {
     // FIXME: We should probably in some way ensure that the subtarget
     // information for a function hasn't changed.
     return false;
   }
 
   /// \name Generic Target Information
   /// @{
 

include/llvm/Analysis/TypeBasedAliasAnalysis.h

 /// A simple AA result that uses TBAA metadata to answer queries.
 class TypeBasedAAResult : public AAResultBase<TypeBasedAAResult> {
   friend AAResultBase<TypeBasedAAResult>;
 
 public:
   /// Handle invalidation events from the new pass manager.
   ///
   /// By definition, this result is stateless and so remains valid.
-  bool invalidate(Function &, const PreservedAnalyses &) { return false; }
+  bool invalidate(Function &, const PreservedAnalyses &,
+                  FunctionAnalysisManager::Invalidator &) {
+    return false;
+  }
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal);
   FunctionModRefBehavior getModRefBehavior(ImmutableCallSite CS);
   FunctionModRefBehavior getModRefBehavior(const Function *F);
   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);
   ModRefInfo getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2);
 

include/llvm/IR/PassManager.h

 
 /// \brief A generic analysis pass manager with lazy running and caching of
 /// results.
 ///
 /// This analysis manager can be used for any IR unit where the address of the
 /// IR unit sufficies as its identity. It manages the cache for a unit of IR via
 /// the address of each unit of IR cached.
 template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager {
-  typedef detail::AnalysisResultConcept<IRUnitT> ResultConceptT;
-  typedef detail::AnalysisPassConcept<IRUnitT, ExtraArgTs...> PassConceptT;
+public:
+  class Invalidator;
+
+private:
+  // Now that we've defined our invalidator, we can build types for the concept
+  // types.
+  typedef detail::AnalysisResultConcept<IRUnitT, PreservedAnalyses, Invalidator>
+      ResultConceptT;
+  typedef detail::AnalysisPassConcept<IRUnitT, PreservedAnalyses, Invalidator,
+                                      ExtraArgTs...>
+      PassConceptT;
+
+  /// \brief List of function analysis pass IDs and associated concept pointers.
+  ///
+  /// Requires iterators to be valid across appending new entries and arbitrary
+  /// erases. Provides the pass ID to enable finding iterators to a given entry
+  /// in maps below, and provides the storage for the actual result concept.
+  typedef std::list<std::pair<AnalysisKey *, std::unique_ptr<ResultConceptT>>>
+      AnalysisResultListT;
+
+  /// \brief Map type from IRUnitT pointer to our custom list type.
+  typedef DenseMap<IRUnitT *, AnalysisResultListT> AnalysisResultListMapT;
+
+  /// \brief Map type from a pair of analysis ID and IRUnitT pointer to an
+  /// iterator into a particular result list which is where the actual result
+  /// is stored.
+  typedef DenseMap<std::pair<AnalysisKey *, IRUnitT *>,
+                   typename AnalysisResultListT::iterator>
+      AnalysisResultMapT;
 
 public:
-  // Most public APIs are inherited from the CRTP base class.
+  /// API to communicate dependencies between analyses during invalidation.
+  ///
+  /// When an analysis result embeds handles to other analysis results, it
+  /// needs to be invalidated both when its own information isn't preserved and
+  /// if any of those embedded analysis results end up invalidated. We pass in
+  /// an \c Invalidator object from the analysis manager in order to let the
+  /// analysis results themselves define the dependency graph on the fly. This
+  /// avoids building an explicit data structure representation of the
+  /// dependencies between analysis results.
+  class Invalidator {
+  public:
+    template <typename PassT>
+    bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
+      AnalysisKey *ID = PassT::ID();
+      SmallDenseMap<AnalysisKey *, bool, 8>::iterator IMapI;
+      bool Inserted;
+      std::tie(IMapI, Inserted) = IsResultInvalidated.insert({ID, false});
+
+      // If we've already visited this pass, return true if it was invalidated
+      // and false otherwise.
+      if (!Inserted)
+        return IMapI->second;
+
+      // Otherwise look up the result object.
+      auto RI = Results.find({ID, &IR});
+      assert(RI != Results.end() &&
+             "Trying to invalidate a dependent result that isn't in the "
+             "manager's cache is always an error, likely due to a stale result "
+             "handle!");
+
+      typedef detail::AnalysisResultModel<IRUnitT, PassT,
+                                          typename PassT::Result,
+                                          PreservedAnalyses, Invalidator>
+          ResultModelT;
+      auto &ResultModel = static_cast<ResultModelT &>(*RI->second->second);
+
+      // Mark in the map whether the result should be invalidated and return
+      // that.
+      IMapI->second = ResultModel.invalidate(IR, PA, *this);
+      return IMapI->second;
+    }
+
+  private:
+    friend class AnalysisManager;
+
+    Invalidator(SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated,
+                const AnalysisResultMapT &Results)
+        : IsResultInvalidated(IsResultInvalidated), Results(Results) {}
+
+    SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated;
+    const AnalysisResultMapT &Results;
+  };
 
   /// \brief Construct an empty analysis manager.
   ///
   /// A flag can be passed to indicate that the manager should perform debug
   /// logging.
   AnalysisManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {}
   AnalysisManager(AnalysisManager &&) = default;
   AnalysisManager &operator=(AnalysisManager &&) = default;
public:
   /// If there is not a valid cached result in the manager already, this will
   /// re-run the analysis to produce a valid result.
   template <typename PassT>
   typename PassT::Result &getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs) {
     assert(AnalysisPasses.count(PassT::ID()) &&
            "This analysis pass was not registered prior to being queried");
     ResultConceptT &ResultConcept =
         getResultImpl(PassT::ID(), IR, ExtraArgs...);
-    typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
+    typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
+                                        PreservedAnalyses, Invalidator>
         ResultModelT;
     return static_cast<ResultModelT &>(ResultConcept).Result;
   }
 
   /// \brief Get the cached result of an analysis pass for this module.
   ///
   /// This method never runs the analysis.
   ///
   /// \returns null if there is no cached result.
   template <typename PassT>
   typename PassT::Result *getCachedResult(IRUnitT &IR) const {
     assert(AnalysisPasses.count(PassT::ID()) &&
            "This analysis pass was not registered prior to being queried");
 
     ResultConceptT *ResultConcept = getCachedResultImpl(PassT::ID(), IR);
     if (!ResultConcept)
       return nullptr;
 
-    typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
+    typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
+                                        PreservedAnalyses, Invalidator>
         ResultModelT;
     return &static_cast<ResultModelT *>(ResultConcept)->Result;
   }
 
   /// \brief Register an analysis pass with the manager.
   ///
   /// The argument is a callable whose result is a pass. This allows passing in
   /// a lambda to construct the pass.
   ///
   /// The pass type registered is the result type of calling the argument. If
   /// that pass has already been registered, then the argument will not be
   /// called and this function will return false. Otherwise, the pass type
   /// becomes registered, with the instance provided by calling the argument
   /// once, and this function returns true.
   ///
   /// While this returns whether or not the pass type was already registered,
   /// there in't an independent way to query that as that would be prone to
   /// risky use when *querying* the analysis manager. Instead, the only
   /// supported use case is avoiding duplicate registry of an analysis. This
   /// interface also lends itself to minimizing the number of times we have to
   /// do lookups for analyses or construct complex passes only to throw them
   /// away.
   template <typename PassBuilderT> bool registerPass(PassBuilderT PassBuilder) {
     typedef decltype(PassBuilder()) PassT;
-    typedef detail::AnalysisPassModel<IRUnitT, PassT, ExtraArgTs...> PassModelT;
+    typedef detail::AnalysisPassModel<IRUnitT, PassT, PreservedAnalyses,
+                                      Invalidator, ExtraArgTs...>
+        PassModelT;
 
     auto &PassPtr = AnalysisPasses[PassT::ID()];
     if (PassPtr)
       // Already registered this pass type!
       return false;
 
     // Construct a new model around the instance returned by the builder.
     PassPtr.reset(new PassModelT(PassBuilder()));
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
     // Short circuit for common cases of all analyses being preserved.
     if (PA.areAllPreserved() || PA.preserved<AllAnalysesOn<IRUnitT>>())
       return;
 
     if (DebugLogging)
       dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName()
              << "\n";
 
-    // Clear all the invalidated results associated specifically with this
-    // function.
-    SmallVector<AnalysisKey *, 8> InvalidatedIDs;
+    // Track whether each pass's result is invalidated. Memoize the results
+    // using the IsResultInvalidated map.
+    SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;
+    Invalidator Inv(IsResultInvalidated, AnalysisResults);
     AnalysisResultListT &ResultsList = AnalysisResultLists[&IR];
-    for (typename AnalysisResultListT::iterator I = ResultsList.begin(),
-                                                E = ResultsList.end();
-         I != E;) {
+    for (auto &AnalysisResultPair : ResultsList) {
+      // This is basically the same thing as Invalidator::invalidate, but we
+      // can't call it here because we're operating on the type-erased result.
+      // Moreover if we instead called invalidate() directly, it would do an
+      // unnecessary lookup in ResultsList.
+      AnalysisKey *ID = AnalysisResultPair.first;
+      auto &Result = *AnalysisResultPair.second;
+
+      SmallDenseMap<AnalysisKey *, bool, 8>::iterator IMapI;
+      bool Inserted;
+      std::tie(IMapI, Inserted) = IsResultInvalidated.insert({ID, false});
+      if (!Inserted)
+        // This result was already handled via the Invalidator.
+        continue;
+
+      // Try to invalidate the result, giving it the Invalidator so it can
+      // recursively query for any dependencies it has and record the result.
+      IMapI->second = Result.invalidate(IR, PA, Inv);
+    }
+
+    // Now erase the results that were marked above as invalidated.
+    for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) {
       AnalysisKey *ID = I->first;
+      if (!IsResultInvalidated.lookup(ID)) {
+        ++I;
+        continue;
+      }
 
-      // Pass the invalidation down to the pass itself to see if it thinks it is
-      // necessary. The analysis pass can return false if no action on the part
-      // of the analysis manager is required for this invalidation event.
-      if (I->second->invalidate(IR, PA)) {
-        if (DebugLogging)
-          dbgs() << "Invalidating analysis: " << this->lookupPass(ID).name()
-                 << "\n";
 
-        InvalidatedIDs.push_back(I->first);
-        I = ResultsList.erase(I);
-      } else {
-        ++I;
-      }
+      AnalysisResults.erase({ID, &IR});
     }
-    while (!InvalidatedIDs.empty())
-      AnalysisResults.erase(std::make_pair(InvalidatedIDs.pop_back_val(), &IR));
     if (ResultsList.empty())
       AnalysisResultLists.erase(&IR);
 
     return;
   }
 
 private:
   /// \brief Lookup a registered analysis pass.
private:
   }
 
   /// \brief Map type from module analysis pass ID to pass concept pointer.
   typedef DenseMap<AnalysisKey *, std::unique_ptr<PassConceptT>> AnalysisPassMapT;
 
   /// \brief Collection of module analysis passes, indexed by ID.
   AnalysisPassMapT AnalysisPasses;
 
-  /// \brief List of function analysis pass IDs and associated concept pointers.
-  ///
-  /// Requires iterators to be valid across appending new entries and arbitrary
-  /// erases. Provides both the pass ID and concept pointer such that it is
-  /// half of a bijection and provides storage for the actual result concept.
-  typedef std::list<std::pair<
-      AnalysisKey *, std::unique_ptr<detail::AnalysisResultConcept<IRUnitT>>>>
-      AnalysisResultListT;
-
-  /// \brief Map type from function pointer to our custom list type.
-  typedef DenseMap<IRUnitT *, AnalysisResultListT> AnalysisResultListMapT;
-
   /// \brief Map from function to a list of function analysis results.
   ///
   /// Provides linear time removal of all analysis results for a function and
   /// the ultimate storage for a particular cached analysis result.
   AnalysisResultListMapT AnalysisResultLists;
 
-  /// \brief Map type from a pair of analysis ID and function pointer to an
-  /// iterator into a particular result list.
-  typedef DenseMap<std::pair<AnalysisKey *, IRUnitT *>,
-                   typename AnalysisResultListT::iterator>
-      AnalysisResultMapT;
-
   /// \brief Map from an analysis ID and function to a particular cached
   /// analysis result.
   AnalysisResultMapT AnalysisResults;
 
   /// \brief A flag indicating whether debug logging is enabled.
   bool DebugLogging;
 };
 
public:
     /// If this analysis itself is preserved, then we assume that the set of \c
     /// Function objects in the \c Module hasn't changed and thus we don't need
     /// to invalidate *all* cached data associated with a \c Function* in the \c
     /// FunctionAnalysisManager.
     ///
     /// Regardless of whether this analysis is marked as preserved, all of the
     /// analyses in the \c FunctionAnalysisManager are potentially invalidated
     /// based on the set of preserved analyses.
-    bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
+    bool invalidate(
+        IRUnitT &IR, const PreservedAnalyses &PA,
+        typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &) {
       // If this proxy isn't marked as preserved, then we can't even invalidate
       // individual function analyses, there may be an invalid set of Function
       // objects in the cache making it impossible to incrementally preserve
       // them. Just clear the entire manager.
       if (!PA.preserved(InnerAnalysisManagerProxy::ID()))
         AM->clear();
 
       // Return false to indicate that this result is still a valid proxy.
public:
   /// \brief Result proxy object for \c OuterAnalysisManagerProxy.
   class Result {
   public:
     explicit Result(const AnalysisManagerT &AM) : AM(&AM) {}
 
     const AnalysisManagerT &getManager() const { return *AM; }
 
     /// \brief Handle invalidation by ignoring it, this pass is immutable.
-    bool invalidate(IRUnitT &, const PreservedAnalyses &) { return false; }
+    bool invalidate(
+        IRUnitT &, const PreservedAnalyses &,
+        typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &) {
+      return false;
+    }
 
   private:
     const AnalysisManagerT *AM;
   };
 
   OuterAnalysisManagerProxy(const AnalysisManagerT &AM) : AM(&AM) {}
 
   /// \brief Run the analysis pass and create our proxy result object.

include/llvm/IR/PassManagerInternal.h

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include <memory>
 #include <utility>
 
 namespace llvm {
 
 template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager;
+class Invalidator;
 class PreservedAnalyses;
 
 /// \brief Implementation details of the pass manager interfaces.
 namespace detail {
 
 /// \brief Template for the abstract base class used to dispatch
 /// polymorphically over pass objects.
 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
struct PassModel : PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...> {
 
   PassT Pass;
 };
 
 /// \brief Abstract concept of an analysis result.
 ///
 /// This concept is parameterized over the IR unit that this result pertains
 /// to.
-template <typename IRUnitT> struct AnalysisResultConcept {
+template <typename IRUnitT, typename PreservedAnalysesT, typename InvalidatorT>
+struct AnalysisResultConcept {
   virtual ~AnalysisResultConcept() = default;
 
   /// \brief Method to try and mark a result as invalid.
   ///
   /// When the outer analysis manager detects a change in some underlying
   /// unit of the IR, it will call this method on all of the results cached.
   ///
-  /// This method also receives a set of preserved analyses which can be used
-  /// to avoid invalidation because the pass which changed the underlying IR
-  /// took care to update or preserve the analysis result in some way.
+  /// \p PA is a set of preserved analyses which can be used to avoid
+  /// invalidation because the pass which changed the underlying IR took care
+  /// to update or preserve the analysis result in some way.
+  ///
+  /// \p Inv is typically a \c AnalysisManager::Invalidator object that can be
+  /// used by a particular analysis result to discover if other analyises
+  /// results are also invalidated in the event that this result depends on
+  /// them. See the documentation in the \c AnalysisManager for more details.
   ///
   /// \returns true if the result is indeed invalid (the default).
-  virtual bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) = 0;
+  virtual bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA,
+                          InvalidatorT &Inv) = 0;
 };
 
 /// \brief SFINAE metafunction for computing whether \c ResultT provides an
 /// \c invalidate member function.
 template <typename IRUnitT, typename ResultT> class ResultHasInvalidateMethod {
   typedef char EnabledType;
   struct DisabledType {
     char a, b;

 
 /// \brief Wrapper to model the analysis result concept.
 ///
 /// By default, this will implement the invalidate method with a trivial
 /// implementation so that the actual analysis result doesn't need to provide
 /// an invalidation handler. It is only selected when the invalidation handler
 /// is not part of the ResultT's interface.
 template <typename IRUnitT, typename PassT, typename ResultT,
-          typename PreservedAnalysesT = PreservedAnalyses,
+          typename PreservedAnalysesT, typename InvalidatorT,
           bool HasInvalidateHandler =
               ResultHasInvalidateMethod<IRUnitT, ResultT>::Value>
 struct AnalysisResultModel;
 
 /// \brief Specialization of \c AnalysisResultModel which provides the default
 /// invalidate functionality.
 template <typename IRUnitT, typename PassT, typename ResultT,
-          typename PreservedAnalysesT>
-struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT, false>
-    : AnalysisResultConcept<IRUnitT> {
+          typename PreservedAnalysesT, typename InvalidatorT>
+struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT,
+                           InvalidatorT, false>
+    : AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT> {
   explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
   // We have to explicitly define all the special member functions because MSVC
   // refuses to generate them.
   AnalysisResultModel(const AnalysisResultModel &Arg) : Result(Arg.Result) {}
   AnalysisResultModel(AnalysisResultModel &&Arg)
       : Result(std::move(Arg.Result)) {}
 
   friend void swap(AnalysisResultModel &LHS, AnalysisResultModel &RHS) {
     using std::swap;
     swap(LHS.Result, RHS.Result);
   }
 
   AnalysisResultModel &operator=(AnalysisResultModel RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   /// \brief The model bases invalidation solely on being in the preserved set.
   //
   // FIXME: We should actually use two different concepts for analysis results
   // rather than two different models, and avoid the indirect function call for
   // ones that use the trivial behavior.
-  bool invalidate(IRUnitT &, const PreservedAnalysesT &PA) override {
+  bool invalidate(IRUnitT &, const PreservedAnalysesT &PA,
+                  InvalidatorT &) override {
     return !PA.preserved(PassT::ID());
   }
 
   ResultT Result;
 };
 
 /// \brief Specialization of \c AnalysisResultModel which delegates invalidate
 /// handling to \c ResultT.
 template <typename IRUnitT, typename PassT, typename ResultT,
-          typename PreservedAnalysesT>
-struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT, true>
-    : AnalysisResultConcept<IRUnitT> {
+          typename PreservedAnalysesT, typename InvalidatorT>
+struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT,
+                           InvalidatorT, true>
+    : AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT> {
   explicit AnalysisResultModel(ResultT Result) : Result(std::move(Result)) {}
   // We have to explicitly define all the special member functions because MSVC
   // refuses to generate them.
   AnalysisResultModel(const AnalysisResultModel &Arg) : Result(Arg.Result) {}
   AnalysisResultModel(AnalysisResultModel &&Arg)
       : Result(std::move(Arg.Result)) {}
 
   friend void swap(AnalysisResultModel &LHS, AnalysisResultModel &RHS) {
     using std::swap;
     swap(LHS.Result, RHS.Result);
   }
 
   AnalysisResultModel &operator=(AnalysisResultModel RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   /// \brief The model delegates to the \c ResultT method.
-  bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA) override {
-    return Result.invalidate(IR, PA);
+  bool invalidate(IRUnitT &IR, const PreservedAnalysesT &PA,
+                  InvalidatorT &Inv) override {
+    return Result.invalidate(IR, PA, Inv);
   }
 
   ResultT Result;
 };
 
 /// \brief Abstract concept of an analysis pass.
 ///
 /// This concept is parameterized over the IR unit that it can run over and
 /// produce an analysis result.
-template <typename IRUnitT, typename... ExtraArgTs> struct AnalysisPassConcept {
+template <typename IRUnitT, typename PreservedAnalysesT, typename InvalidatorT,
+          typename... ExtraArgTs>
+struct AnalysisPassConcept {
   virtual ~AnalysisPassConcept() = default;
 
   /// \brief Method to run this analysis over a unit of IR.
   /// \returns A unique_ptr to the analysis result object to be queried by
   /// users.
-  virtual std::unique_ptr<AnalysisResultConcept<IRUnitT>>
+  virtual std::unique_ptr<
+      AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT>>
   run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
       ExtraArgTs... ExtraArgs) = 0;
 
   /// \brief Polymorphic method to access the name of a pass.
   virtual StringRef name() = 0;
 };
 
 /// \brief Wrapper to model the analysis pass concept.
 ///
 /// Can wrap any type which implements a suitable \c run method. The method
 /// must accept an \c IRUnitT& and an \c AnalysisManager<IRUnitT>& as arguments
 /// and produce an object which can be wrapped in a \c AnalysisResultModel.
-template <typename IRUnitT, typename PassT, typename... ExtraArgTs>
-struct AnalysisPassModel : AnalysisPassConcept<IRUnitT, ExtraArgTs...> {
+template <typename IRUnitT, typename PassT, typename PreservedAnalysesT,
+          typename InvalidatorT, typename... ExtraArgTs>
+struct AnalysisPassModel : AnalysisPassConcept<IRUnitT, PreservedAnalysesT,
+                                               InvalidatorT, ExtraArgTs...> {
   explicit AnalysisPassModel(PassT Pass) : Pass(std::move(Pass)) {}
   // We have to explicitly define all the special member functions because MSVC
   // refuses to generate them.
   AnalysisPassModel(const AnalysisPassModel &Arg) : Pass(Arg.Pass) {}
   AnalysisPassModel(AnalysisPassModel &&Arg) : Pass(std::move(Arg.Pass)) {}
 
   friend void swap(AnalysisPassModel &LHS, AnalysisPassModel &RHS) {
     using std::swap;
     swap(LHS.Pass, RHS.Pass);
   }
 
   AnalysisPassModel &operator=(AnalysisPassModel RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   // FIXME: Replace PassT::Result with type traits when we use C++11.
-  typedef AnalysisResultModel<IRUnitT, PassT, typename PassT::Result>
+  typedef AnalysisResultModel<IRUnitT, PassT, typename PassT::Result,
+                              PreservedAnalysesT, InvalidatorT>
       ResultModelT;
 
   /// \brief The model delegates to the \c PassT::run method.
   ///
   /// The return is wrapped in an \c AnalysisResultModel.
-  std::unique_ptr<AnalysisResultConcept<IRUnitT>>
+  std::unique_ptr<
+      AnalysisResultConcept<IRUnitT, PreservedAnalysesT, InvalidatorT>>
   run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM,
       ExtraArgTs... ExtraArgs) override {
     return make_unique<ResultModelT>(Pass.run(IR, AM, ExtraArgs...));
   }
 
   /// \brief The model delegates to a static \c PassT::name method.
   ///
   /// The returned string ref must point to constant immutable data!

lib/Analysis/CGSCCPassManager.cpp

 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/IR/CallSite.h"
 
 using namespace llvm;
 
 namespace llvm {
 
 // Explicit instantiations for the core proxy templates.
+template class AllAnalysesOn<LazyCallGraph::SCC>;
 template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
 template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
                            LazyCallGraph &, CGSCCUpdateResult &>;
 template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
 template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
                                          LazyCallGraph::SCC>;
 template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
                                          LazyCallGraph::SCC>;
for (auto &Pass : Passes) {
 
     // FIXME: Historically, the pass managers all called the LLVM context's
     // yield function here. We don't have a generic way to acquire the
     // context and it isn't yet clear what the right pattern is for yielding
     // in the new pass manager so it is currently omitted.
     // ...getContext().yield();
   }
 
   // Invaliadtion was handled after each pass in the above loop for the current
   // SCC. Therefore, the remaining analysis results in the AnalysisManager are
   // preserved. We mark this with a set so that we don't need to inspect each
   // one individually.
   PA.preserve<AllAnalysesOn<LazyCallGraph::SCC>>();
 
   if (DebugLogging)
     dbgs() << "Finished CGSCC pass manager run.\n";
 
   return PA;
 }
 

unittests/Analysis/CGSCCPassManagerTest.cpp

 };
 
 AnalysisKey TestFunctionAnalysis::Key;
 
 class TestImmutableFunctionAnalysis
     : public AnalysisInfoMixin<TestImmutableFunctionAnalysis> {
 public:
   struct Result {
-    bool invalidate(Function &, const PreservedAnalyses &) { return false; }
+    bool invalidate(Function &, const PreservedAnalyses &,
+                    FunctionAnalysisManager::Invalidator &) {
+      return false;
+    }
   };
 
   TestImmutableFunctionAnalysis(int &Runs) : Runs(Runs) {}
 
   Result run(Function &F, FunctionAnalysisManager &AM) {
     ++Runs;
     return Result();
   }

unittests/IR/PassManagerTest.cpp

TEST_F(PassManagerTest, CustomizedPassManagerArgs) {
 
   // Run this over every function with the input of 42.
   for (Function &F : *M)
     PM.run(F, AM, 42, Result);
 
   // And ensure that we accumulated the correct result.
   EXPECT_EQ(42 * (int)M->size(), Result);
 }
+
+/// A test analysis pass which caches in its result another analysis pass and
+/// uses it to serve queries. This requires the result to invalidate itself
+/// when its dependency is invalidated.
+struct TestIndirectFunctionAnalysis
+    : public AnalysisInfoMixin<TestIndirectFunctionAnalysis> {
+  struct Result {
+    Result(TestFunctionAnalysis::Result &Dep) : Dep(Dep) {}
+    TestFunctionAnalysis::Result &Dep;
+
+    bool invalidate(Function &F, const PreservedAnalyses &PA,
+                    FunctionAnalysisManager::Invalidator &Inv) {
+      return !PA.preserved<TestIndirectFunctionAnalysis>() ||
+             Inv.invalidate<TestFunctionAnalysis>(F, PA);
+    }
+  };
+
+  TestIndirectFunctionAnalysis(int &Runs) : Runs(Runs) {}
+
+  /// Run the analysis pass over the function and return a result.
+  Result run(Function &F, FunctionAnalysisManager &AM) {
+    ++Runs;
+    return Result(AM.getResult<TestFunctionAnalysis>(F));
+  }
+
+private:
+  friend AnalysisInfoMixin<TestIndirectFunctionAnalysis>;
+  static AnalysisKey Key;
+
+  int &Runs;
+};
+
+AnalysisKey TestIndirectFunctionAnalysis::Key;
+
+struct LambdaPass : public PassInfoMixin<LambdaPass> {
+  using FuncT = std::function<PreservedAnalyses(Function &, FunctionAnalysisManager &)>;
+
+  LambdaPass(FuncT Func) : Func(std::move(Func)) {}
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
+    return Func(F, AM);
+  }
+
+  FuncT Func;
+};
+
+TEST_F(PassManagerTest, IndirectAnalysisInvalidation) {
+  FunctionAnalysisManager FAM(/*DebugLogging*/ true);
+  int AnalysisRuns = 0, IndirectAnalysisRuns = 0;
+  FAM.registerPass([&] { return TestFunctionAnalysis(AnalysisRuns); });
+  FAM.registerPass(
+      [&] { return TestIndirectFunctionAnalysis(IndirectAnalysisRuns); });
+
+  ModuleAnalysisManager MAM(/*DebugLogging*/ true);
+  MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
+  FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
+
+  int InstrCount = 0;
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  FunctionPassManager FPM(/*DebugLogging*/ true);
+  // First just use the analysis to get the instruction count, and preserve
+  // everything.
+  FPM.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) {
+    InstrCount +=
+        AM.getResult<TestIndirectFunctionAnalysis>(F).Dep.InstructionCount;
+    return PreservedAnalyses::all();
+  }));
+  // Next, invalidate
+  //   - both analyses for "f",
+  //   - just the underlying (indirect) analysis for "g", and
+  //   - just the direct analysis for "h".
+  FPM.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) {
+    InstrCount +=
+        AM.getResult<TestIndirectFunctionAnalysis>(F).Dep.InstructionCount;
+    auto PA = PreservedAnalyses::none();
+    if (F.getName() == "g")
+      PA.preserve<TestFunctionAnalysis>();
+    else if (F.getName() == "h")
+      PA.preserve<TestIndirectFunctionAnalysis>();
+    return PA;
+  }));
+  // Finally, use the analysis again on each function, forcing re-computation
+  // for all of them.
+  FPM.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) {
+    InstrCount +=
+        AM.getResult<TestIndirectFunctionAnalysis>(F).Dep.InstructionCount;
+    return PreservedAnalyses::all();
+  }));
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  MPM.run(*M, MAM);
+
+  // There are generally two possible runs for each of the three functions. But
+  // for one function, we only invalidate the indirect analysis so the base one
+  // only gets run five times.
+  EXPECT_EQ(5, AnalysisRuns);
+  // The indirect analysis is invalidated for each function (either directly or
+  // indirectly) and run twice for each.
+  EXPECT_EQ(6, IndirectAnalysisRuns);
+
+  // There are five instructions in the module and we add the count three
+  // times.
+  EXPECT_EQ(5 * 3, InstrCount);
+}
 }