[PM] Introduce the facilities for registering cross-IR-unit dependencies that require deferred invalidation.

[chandlerc]

Summary

This handles the other real-world invalidation scenario that we have
cases of: a function analysis which caches references to a module
analysis. We currently do this in the AA aggregation layer and might
well do this in other places as well.

Since this is relative rare, the technique is somewhat more cumbersome.
Analyses need to register themselves when accessing the outer analysis
manager's proxy. This proxy is already necessarily present to allow
access to the outer IR unit's analyses. By registering here we can track
and trigger invalidation when that outer analysis goes away.

To make this work we need to enhance the PreservedAnalyses
infrastructure to support a (slightly) more explicit model for "sets" of
analyses, and allow abandoning a single specific analyses even when
a set covering that analysis is preserved. That allows us to describe
the scenario of preserving all Function analyses *except* for the one
where deferred invalidation has triggered.

We also need to teach the invalidator API to support direct ID calls
instead of always going through a template to dispatch so that we can
just record the ID mapping.

I've introduced testing of all of this both for simple module<->function
cases as well as for more complex cases involving a CGSCC layer.

Much like the previous patch I've not tried to fully update the loop
pass management layer because that layer is due to be heavily reworked
to use similar techniques to the CGSCC to handle updates. As that
happens, we'll have a better testing basis for adding support like this.

Depends on D27197.

[silvas]

This makes sense given your current trajectory for the new PM. LGTM with a nit.

It is somewhat bothersome that so much ad-hoc open-coded stuff is needed, but that's inherent to the approach you're taking (trying to do things in terms of sets of analyses being exchanged by IRUnit specifc analysis managers orchestrated by the proxies, instead of directly tracking dependencies between the analysis result objects, which are the objects being cached that need to be correctly invalidated).

unittests/IR/PassManagerTest.cpp

431

nit: avoid the terminology "analysis pass". In the new PM analyses and transformations are separate concepts. The term "pass" doesn't help because it conflates the two (and many uses in the code use "pass" to really mean "transformation", so "analysis pass" is particularly confusing and old-PM'ish).

Hopefully some day we can rename things to be more consistent. Really the new "PM" has just two main things: an AnalysisCache class and a bunch of composable TransformationRunner's. There isn't a conflated concept of "pass" (which can be either a transformation or an analysis) like in the old PM.

[jlebar]

include/llvm/IR/PassManager.h

75

The changes here seem like a type-safety nightmare.

Could we require that these abstract sets inherit from some type? That would also help with the explanation, I think, by making "abstract sets that might be preserved" a concrete thing, namely types that inherit from FooType.

100

s/If not covered by the "all" set/If we're not already preserving all analyses (other than those in NotPreservedAnalysisIDs)/

(Problem is there's no direct object for "covered".)

106

and even if already explicitly marked as preserved.

113

Should this note appear above as well?

119

s/, that/

136

Nit, I would emphasize "*union*" and "*intersection*", rather than "*not*".

158

ibid.

179

Looks like this comment should be updated too?

235

s/ as/, as/

236

s/to be empty//

236

Actually, it's stronger than "should never contain the 'all' set" -- it should never contain *any* abstract sets of analyses.

506

/// Type-erased version of templated \c invalidate above.

?

Also, real bummer we have to copy-paste this.

675

It's not clear what this is contrasting with (without the diff available :).

956

deffered

988

s/datastructure/data structure/

1007

You don't want a version with inline storage?

lib/Analysis/CGSCCPassManager.cpp

103

Hm, now that I see it being used, I am even less thrilled about this API. It's not at all obvious what the second template argument means here, and it also seems super easy to forget to pass this the relevant arguments. In addition, if I ever add a new abstract set, I have to go and modify every preserved() call.

Would it be out of the question to encapsulate within (say) the CGSCCAnalysisManagerModuleProxy type the sets that cover it, so that we could continue to pass only one type to preserved<...>()?

114

Not sure this comment is helpful, although maybe some foreshadowing about what we're going to do with this information might help.

130

deffered

131

Run-on sentence

131

proxies

146

Split into two sentences.

lib/IR/PassManager.cpp

86

...wait, didn't I just read this function inCGSCCPassManager.cpp? :(

Probably not something to be fixed in this patch.

unittests/Analysis/CGSCCPassManagerTest.cpp

846

invalidate

894

chaches

unittests/IR/PassManagerTest.cpp

431

+1 to that in principle, although if we actually carry that out, we're going to have to do a big refactoring, so until then my personal preference would be that we should just say whatever is clear, rather than adding in the new terminology in places where "pass" would, in the current state, be more clear.

Not begging the specific question of what to say here.

[chandlerc]

Rebase and address most of the comments.

[chandlerc]

Responses to more comments below, thanks for the review!

lib/Analysis/CGSCCPassManager.cpp

103

I mean, I don't disagree with any of this, but I've not come up with a better alternative really.

I know there are going to be more sets than IR-unit derived ones such as CFG-preserving. =/ So bundling it inside the proxy doesn't seem like it'd be a great alternative... And it would still be quite hard to make work.

The key thing that needs to happen is that one layer needs to be able to introduce a preserved set for an IR unit, and then some other part of the code needs to subtract one analysis from that set, and then when we call 'invalidate' on *that* analysis it needs to not pay attention to the set.

Anyways, any better API ideas here are very, very welcome. =/

131

Yea, this is just a mess. Tried to improve, but complain more if it is still just not coming across well.

lib/IR/PassManager.cpp

86

You read a remarkably similar but subtly different function. =[ I'm not thrilled with this either, but factoring the code may be noisier than the duplication.

[chandlerc]

include/llvm/IR/PassManager.h

119

I'm so bad at commas... I hope this is better now...

506

Done and factored into a common routine. Came up with a nice way to have a single implementation that is fast when it can be fast but generic/type-erased when it needs to be.

675

Reworded to hopefully make this more clear.

unittests/IR/PassManagerTest.cpp

431

I don't actually think of it this way.

I think there is a common underlying idea of a pass, and there are two primary special cases: analysis passes and transformation passes.

I understand that many (most?) analysis passes tend to be trivial and we instead focus on the analysis result and caching it, but I don't want to neglect the fact that it is a pass that gets run over the IR. In that sense, the AnalysisManager *is* a `pass manager as well.

Anyways, I'm happy to spend some time debating this long term, but I'm not sure it's the right focus of this code review....

[jlebar]

lib/Analysis/CGSCCPassManager.cpp

103

Anyways, any better API ideas here are very, very welcome. =/

One idea was up earlier in the review:

Could we require that these abstract sets inherit from some type [or otherwise have some way to tell the difference between an analysis and a set of analyses]?

At least then PA could catch some incorrect uses of its API.

(I understand that is solving a different problem than the one I was originally commenting on here.)

In terms of this problem, are you saying that we can neither

a) have an abstract analysis set enumerate its passes, nor can we
b) have an analysis enumerate its abstract analysis sets,

because the only layer that knows about all of the relevant sets and passes does not declare the sets or the passes? If so this seems remarkably fragile, to the point that I would want to step back and consider whether the layering we've imposed is actually helpful -- that is, whether the design space is overconstrained.

TBH I am pretty concerned that nobody other than you and Sean is going to be smart enough to program this correctly. For example, writing

!PA.preserved<CGSCCAnalysisManagerModuleProxy, AllAnalysesOn<Module>>()

requires global knowledge of LLVM that the only analysis set that covers CGSCCAnalysisManagerModuleProxy is AllAnalysesOn<Module>. (Or it somehow requires even more arcane knowledge that AllAnalysesOn<Module> is the only set that we need to enumerate here.) If you get it wrong, things will mostly work, until they don't, so these are not going to be easy bugs to find.

My understanding is that a lot of the design complexity is motivated by a desire to allow outside-tree users to provide new kinds of PMs. That's a laudable goal, but on average I would expect out-of-tree users to have less knowledge of LLVM core than your average core developer, so such an API is really only useful if it's hard to screw up. If we can't make it hard for them to do the wrong thing, and if providing this loose-coupling mechanism adds substantial complexity to our internal design, I am personally not convinced we are making the right design tradeoffs.

unittests/IR/PassManagerTest.cpp

431

I'm not sure it's the right focus of this code review....

I tend to lose state on anything I'm not working on in a week. If you start the discussion in the forum of your choosing Monday, great. If you start a thread in two or three weeks, you will probably still have state, but I may not, and then I will either decide I no longer care, or have to come back and page all this back in. Either way is not fun.

In fact I now vaguely recall that we had an outstanding question from a previous patch that we said we'd discuss outside the review. Maybe we did come back and it's been resolved? I am sort of a goldfish.

Because I've now been thinking about it, let me just say what I have in mind so we can capture it somewhere. I hope that's OK.

the AnalysisManager *is* a `pass manager as well.

I would ask a slightly different question. Instead of "is AM technically a PM?", I'd ask, "is it *useful* to an engineer of average skill to think of AM as a PM, and to think of Analyses as Passes?"

One can even have comments on AM explaining this technicality if it's useful to understand when thinking about the PM/AM framework. But then, is this happenstance of abstraction *so fundamental* that we should also use it everywhere else? Maybe I haven't fully understood the code because I don't grok that an analysis is just a monoid in the category of endofunctors^W^W^W^W^W^Wpass. :)

Personally I think "pass" is a useful word because "optimization pass" was a term I knew before I started working on compilers. But like Sean I am not sure it helps me more than it hurts to think of analyses as the same sort of thing.

[silvas]

A couple suggestions to make this patch more understadable.

include/llvm/IR/PassManager.h

75

The comment on this class needs to be beefed up in response to this patch. The original idea behind PreservedAnalyses was that it was a whitelist of analyses to preserve, so that invalidation was conservatively correct. The addition of NotPreservedAnalysisIDs breaks with this approach and adds a layer of complexity that isn't adequately addressed by the current comment.

109

This restriction seems like it stems from an implementation detail. Some implementation-level comment should explain its origin.

235

This restriction about no sets in NotPreservedAnalysisIDs needs to be explained better in the comments here. More generally, there is a clear asymmetry between the PreservedAnalysisIDs and NotPreservedAnalysisIDs that needs to be explained (not just the "rules", but *why* the rules are there). Maybe that is appropriate for the class comment?

lib/Analysis/CGSCCPassManager.cpp

103

In terms of this problem, are you saying that we can neither

a) have an abstract analysis set enumerate its passes, nor can we
b) have an analysis enumerate its abstract analysis sets,

b) is possible. It's just somewhat inconvenient right now because that information is hidden in the invalidate method which is on the analysis result object instead of the analysis itself.

TBH I am pretty concerned that nobody other than you and Sean is going to be smart enough to program this correctly.

For the record, I'm not convinced that I would be able to program this correctly. I don't like the approach that Chandler is taking here for precisely this reason. Explicitly tracking dependencies between analysis results so that there is a clear single point of truth in the analysis manager for the primitive operation "I need to invalidate analysis result X, invalidate all analysis results that depend on it" makes all of this so much easier.

If you haven't read it yet and want to understand the problem of analysis result invalidation better, I highly recommend reading (or at least skimming) the thread "[PM] I think that the new PM needs to learn about inter-analysis dependencies...": https://groups.google.com/d/topic/llvm-dev/4m_Lv3Rfylg/discussion
Especially this post: https://groups.google.com/d/msg/llvm-dev/4m_Lv3Rfylg/ss-UZ0wQDQAJ

[chandlerc]

FYI, working on one API improvement idea and on addressing the tactical comments from Sean that are spot on here, but wanted to reply to the two discussion threads...

lib/Analysis/CGSCCPassManager.cpp

103

Justin wrote:

In terms of this problem, are you saying that we can neither

a) have an abstract analysis set enumerate its passes, nor can we
b) have an analysis enumerate its abstract analysis sets,

I believe that we have (b) -> the analysis enumerates these in its result's invalidate routine.

The problem is that the API for doing this isn't good. I have some ideas about improving the API after thinking more on it. One thing that I did experiment with and continue to dislike is trying to do this *declaratively*. Every version of that I've come up with has been, IMO, much harder to understand.

TBH I am pretty concerned that nobody other than you and Sean is going to be smart enough to program this correctly.

I don't think this is about smarts. =] I think this is largely a problem of documentation and API design. I think your review is helping both of those.

I also think it is important to understand how rarely this complexity will come up. Most analyses will simply:

1. Use the default invalidation logic which works out of the box, or
2. Simply declare that they are never invalidated because they are fundamentally immutable or self-updating, or
3. Implement an invalidate routine that checks a few common sets like 'CFG' in addition to themselves.

Everything else is relatively rare. The next most common case are analyses which embed references to other analyses in their results. Some of these are because it was easy rather than because it was the right design. But some will need to use the Invalidator logic provided in the previous review.

Most of the facilities I'm adding in this patch to be very rarely used. That doesn't mean it gets a free pass of course, it still needs to be clearly documented and have examples that show how to use it and not be easy to misuse in subtle ways.

The facility I am most concerned about (and I called it out, and you called it out) is just letting an analysis result check an additional set or two. That is currently too confusing, agreed, and I'd like a better API for that. I'm experimenting with the idea you suggested Justin and I think it might help, but I can't yet be certain. I'll update the patch if/when I get something interesting.

I also don't think we should strive for perfection in a single patch if there aren't terribly good ideas yet.

Regarding the meta point Sean, I continue to think that unifying the analysis management is the wrong design. I think it creates serious issues when expressing analyses on IR units defined by analyses, which is functionality that I very much want in the design.

unittests/IR/PassManagerTest.cpp

431

Totally good to capture it. =] I'm hoping to discuss this more with you on Monday though and we can kick off some ideas on the list and/or IRC. I wasn't planning on waiting weeks and weeks.

[chandlerc]

Substantial rework of the documentation and API for the PreservedAnalyses
interface.

[chandlerc]

Ok, two significant changes here:

1. I've made the sets use a distinct key type from the analyses so they are clearly independent things. I've also separated the APIs dealing with them so that things are more explicit.

2. Justin and I sat down together to try to at least remove the "magical" aspect of the query API on PreservedAnalyses. The result is a very different API. It is a bit more heavyweight, but now the set relationships can be explicit logical relation ships of ||s and &&s rather than a list of things. This seems both more expressive and also more readable. It seemed to make the code implementing the invalidate method somewhat more comprehensible to Justin at least. But I'd like general feedback on this API design.

As Sean had suggested (thanks!) and then amplified by #2, I've rewritten the high level documentation for PreservedAnalyses and I've written much more comprehensive unit testing. It now clearly needs to live in a separate file IMO, but I want to do that code movement as a follow-up patch if that's OK.

I also spent some time trying to understand why elements of this are confusing, especially at first. I think Justin had a great insight here that the names of the critical component--the proxy analyses--give the reader no good anchor to what each one *is*. Once that is established, understanding the code becomes much easier.

The current plan is to rename the proxies from 'FunctionAnalysisManagerModuleProxy' to 'ProxyModuleAnalysis<FunctionAnalysisManager>'. This does two things that seem to help. One is that it puts 'ModuleAnalysis' early and contiguous in the name anchoring the reader that this is a module analysis first and foremost. The second is that it sinks the thing being proxied into a clearly subordinate position. This too seems like it should be its own patch.

A final thought is that there is currently some duplication of code between the two ProxyModuleAnalysis results' invalidate implementation that it turns out I *can* nicely factor out. I'm happy to do that in this patch or a follow-up, whatever folks prefer. I just wanted to update the patch now that the API rework is in place.

Some further replies below...

include/llvm/IR/PassManager.h

75

I've written new documentation that tries to do this. It may not be good or enough. Let me know how this does and what else I can do here.

109

It actually is more of an interface and semantic simplification in my mind... What does it mean to abandon a set? Does that abandon even explicitly preserved analyses? I would assume so (that's how analysis abandonment works), but instead we might just remove the set. Spelling that out will be necessary.

Also, supporting abandonment of sets makes the API for querying even more constrained, and the complexity of the interface was one thing that was raised as an unfortunate complexity in this patch.

With the new PreservedAnalyses API the code is simpler but we now can't express abandoned analysis sets reasonably at the interface level if they actually preclude individual analysis preservation.

I'm not sure what documentation would help here though... thoughts?

235

See above... in some ways the asymmetry is worse (we have it at the typesystem level). But I'm not sure how best to document this. Suggestions would really be helpful here. The why is both "we don't need it, so why add it?" coupled with the fact that adding support for it introduces non-trivial complexity to the API.

Like I said, I'm very happy to add documentation that you think would help in light of the new API, just need to know what and where.

[silvas]

A couple nits. Overall, this is looking a lot better. It's awesome that you sat down with Justin to hash this out.

include/llvm/IR/PassManager.h

99

This example is a bit confusing. Where is PAC used?

108

What is "name"? Do you mean "analysis" or "analysis key" or something?

[chandlerc]

Address thinkos in the comment spotted by Sean.

[chandlerc]

include/llvm/IR/PassManager.h

99

Doh! Good catch....

108

Yea, I have no idea. I meant what you said - "analysis".

[jlebar]

This looks good to me, and I'm basically ready to approve the patch, but there are a few new non-comment questions buried in here that I'd like to get resolved first.

include/llvm/IR/PassManager.h

74

te

75

I know what you mean, but the "rather than" part doesn't make sense -- *analyses* would never have to enumerate every analysis that's preserved. That's the job of the *transformations*.

81

to indicate that they preserve

82

set off "such as its CFG" with parens

85

", which"

89

First sentence could be clarified / simplified:

Given a PreservedAnalyses object built up by a transformation, an analysis will typically want to figure out whether it is preserved.

90

s/are expected to typically be part of sets/are usually covered by one or more sets/

91

"can" suggests that they have an option, but it's kind of the only choice.

94

Maybe

Mark a particular analysis as preserved, given a pointer to its AnalysisKey.

or something. The current way of distinguishing between this and the one above -- "a particular analysis" versus "an abstract analysis ID" -- is not facile.

Same below.

96

Suggest simplifying this whole para. Just introduce the idea and give the example.

Given a PreservedAnalyses object, an analysis will typically want to figure out whether it is preserved. In the example below, MyAnalysisType is preserved if it's not abandoned, and (a) it's explicitly marked as preserved, (b), the set AllAnalysesOn<MyIRUnit> is preserved, or (c) both AnalysisSetA and AnalysisSetB are preserved.

108

Not sure this para is necessary with the rewrite above.

112

Would suggest making this active, like the suggestion above:

You can also ask a PreservedAnalyses object whether all analyses in a particular set are preserved. If *any* analyses have been abandoned, this *always* returns false, because PreservedAnalyses does not have a priori knowledge of which analyses are in which sets.

Alternatively, maybe this isn't necessary to include in this comment at all; it's kind of an edge case, and we don't have to enumerate the whole API here.

118

"if it's covered" "was previously marked as preserved".

125

Again here, we are still marking the analysis -- not an ID -- as abandoned. The difference is in what we're *given*, not really what we *do*.

137

I am not sure either of these comments in the body are necessary, personally. They seem to repeat the code and the function-level comment.

143

Nit, "not-preserved".

180

Perhaps this sentence should live on the constructor:

We take an AnalysisKey in our constructor because we need to know ...

I think maybe you had this comment here because you wanted to clarify what preserved and preservedSet return without writing repetitive comments? I think it's probably worth having brief comments there:

/// Returns true if our analysis was not abandoned and (a) the analysis was explicitly preserved, or (b) all analyses were preserved.

/// Returns true if our analysis was not abandoned and (a) the set was explicitly preserved, or (b) all analyses were preserved.

189

s/in turn//

189

overal

190

The prep phrase starting with "for" doesn't make much sense. Maybe say:

You can use this object to query whether an analysis was preserved. See the example in the comment on PreservedAnalysis.

212

Same comments here.

212

Suggest being explicit "preserved (and none are abandoned)."

214

Suggest something like

This lets analyses optimize for the common case where a transformation made no changes to the IR.

224

Suggest deleting starting with "and" -- it confuses more than it helps.

229–237

Suggest

The analyses and analysis sets that are preserved.

Invariant: A given AnalysisKey is never in both PreservedIDs set and NotPreservedAnalysisIDs.

232

ibid.

232

I think this is pretty obvious, not sure it's necessary to say.

239

Now can remove

and should not include any synthetic set IDs such as the "all" ID.

because type-safety. Suggest rewriting para to

An analysis cannot be in both PreservedIDs and NotPreservedAnalysisIDs. If an analysis is covered by a set in PreservedIDs but is in NotPreservedAnalysisIDs, we consider it not-preserved. That is, NotPreservedAnalysisIDs always "wins" over analysis sets in PreservedIDs.

486

", which" and then start a new sentence at "but".

There is a rule for the comma here: If you have a "which/that/who" phrase that is not "narrowing", you almost always offset the phrase with commas. A "narrowing" "which/that/who" phrase restricts the meaning of the phrase before: "My coworker who uses ed is out sick." (No commas, I have more than one coworker.) If the phrase is not narrowing, it gets a comma: "My dad, who is a programmer, lives in CA." (Commas; I have only one dad.)

Like everything in English, it depends, but this one is relatively safe.

488

s/needed/needs/?

Although, is the caller really erasing the types itself? Maybe you can just delete starting with "but".

496

implemente

499

Not sure we need the sentence starting with "This implementation" -- it seems pretty clear.

675

With your latest change to the PA interface, can we revert this change and instead do

if (PA.areAllPreserved() || PA.allAnalysesOnSetPreserved<AllAnalysesOn<IRUnitT>>())

?

lib/Analysis/CGSCCPassManager.cpp

115

Suggest s/without.*//

lib/Analysis/LoopPassManager.cpp

37 ↗

(On Diff #81507)

You don't want to check an AllAnalysesOn here too?

unittests/Analysis/CGSCCPassManagerTest.cpp

845

", and" (comma separates independent clauses)

[chandlerc]

Update with fixes for Justin's round of comments.

[chandlerc]

Patch updated with fixes, see responses below.

include/llvm/IR/PassManager.h

94

How about "an analysis type" vs. "an analysis ID"?

118

No, the *set* isn't even temporal. An abandoned analysis is subtracted from all sets at query time.

125

Does clear terms (type vs. ID) help here? Or do you really want the verb moved around?

180

Done but with slightly different wording. See what you think.

229–237

Took a slightly different approach but same spirit.

486

My problem is not that I'm not familiar with the rule about narrowing vs. non-narrowing, it is two-fold:

1. When writing, I cannot keep both these rules and what I am trying to say in my head.

2. When writing and reading my own text, I often end up with a very different interpretation of what it means to be a narrowing phrase. I think I read restrictions of meaning into things that English says aren't actually narrowing phrases.

Sorry. =/ I've been failing at this aspect of writing for over 15 years I fear.

675

We can. It will never fire though because we instead do this test before walking all the IR units so that if we have 10million functions we don't query the PA 10 million times for this...

But we already query it for the all preserved.... so it seems silly in retrospect.

And what's more, the all query should really be handled in the allAnalysesOnSetPreserved, making this quite nice now.

We can keep the optimization in the callers that do this in a tight loop.

lib/Analysis/LoopPassManager.cpp

37 ↗

(On Diff #81507)

I can, I just wasn't bothering because this isn't really tested or updated at all yet. I just made it compile and behave exactly as it did before.

[jlebar]

include/llvm/IR/PassManager.h

94

If all I had were the comments and function signatures, I think I might still find this confusing -- is marking the analysis ID as preserved somehow different than marking a type as preserved? Given the implementation of the first function, it's pretty clear to me, though, so I think it's probably fine if you want to do it this way.

118

Mark an analysis type as abandoned, removing it from the preserved set even if covered by some other set or previously explicitly marked as preserved.

vs.

Mark an analysis type as abandoned, removing it from the preserved set even if it's covered by some other set or was previously explicitly marked as preserved.

To me, these two sentences have no semantic difference -- the first one is just eliding some verbs. It sounds like these two mean something different to you?

Based on these comments, I think maybe you want to get across that abandoning an analysis undoes explicit preservation, but that "implicit" preservation via a set does not undo abandonment. If that's it, how about:

Mark an analysis type as abandoned. An abandoned analysis is not part of the preserved set, even if it is nominally covered by some other set or was previously explicitly marked as preserved.

possibly s/is not part/will not be part/
possibly s/is not part/is not considered part/

If you think that's still not clear, maybe we just need an example; that would make it unambiguous. This a tricky but important API.

125

I'm fine with the "analysis ID" change; see above for the verb issue.

187

Kind of runs on with "in order to skip them". I'd set it off in parens, but maybe it's just not necessary:

Both \c preserved() and \c preservedSet() need to check whether the analysis was abandoned, so we take the analysis ID here and cache whether it was abandoned.

Or if you want to reveal fewer implementation details:

A PreservedAnalysisChecker is tied to a particular Analysis because \c preserved() and \c preservedSet() both return false if the Analysis was abandoned.

223

have been (or "no analysis has been" if you like)

230

ibid

483

Now that I see this -- do we need this comment at all? It's abundantly clear that this is a helper, and it's a private function.

486

Heh, okay. Sorry that wasn't helpful.

[chandlerc]

Update with even better comments thanks to Justin!

include/llvm/IR/PassManager.h

94

Ah, I think I see a better way of wording this. Try now?

118

I like your second wording attempt. That really gets at the heart of it I think. I'm happy to add an example if it helps though.

[chandlerc]

FYI (in case it is confusing) Justin marked this as LGTM already and I've addressed all the comments, so I'm going to land it to unblock further testing.

When Justin is back from vacation, I'll still circle back around with him to make sure the comments are in a state he's happy with.

include/llvm/IR/PassManager.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_PASSMANAGER_H
 #define LLVM_IR_PASSMANAGER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManagerInternal.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/TypeName.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/type_traits.h"
 #include <list>

 /// \brief An abstract set of preserved analyses following a transformation pass
 /// run.
 ///
 /// When a transformation pass is run, it can return a set of analyses whose
 /// results were preserved by that transformation. The default set is "none",
 /// and preserving analyses must be done explicitly.
 ///
 /// There is also an explicit all state which can be used (for example) when
 /// the IR is not mutated at all.
 class PreservedAnalyses {
 public:
   /// \brief Convenience factory function for the empty preserved set.
   static PreservedAnalyses none() { return PreservedAnalyses(); }
 
   /// \brief Construct a special preserved set that preserves all passes.
   static PreservedAnalyses all() {
     PreservedAnalyses PA;
     PA.PreservedAnalysisIDs.insert(&AllAnalysesKey);
     return PA;
   }
 
-  /// \brief Mark a particular pass as preserved, adding it to the set.
+  /// Mark a particular analysis or analysis set as preserved.
+  ///
+  /// Both specific analysis passes and abstract analysis sets can be
+  /// preserved. See the query API below to understand how sets and analyses
+  /// interact.
   template <typename PassT> void preserve() { preserve(PassT::ID()); }
 
-  /// \brief Mark an abstract ID as preserved, adding it to the set.
+  /// Mark an abstract ID as preserved, adding it to the set.
   void preserve(AnalysisKey *ID) {
+    // Clear this ID from the explicit not-preserved set if present.
+    NotPreservedAnalysisIDs.erase(ID);
+
+    // If not covered by the "all" set, add this to the explicitly preserved
+    // set.
     if (!areAllPreserved())
       PreservedAnalysisIDs.insert(ID);
   }
 
+  /// Mark a particular pass as abandoned, removing it from the preserved set
+  /// even if covered by some other set.
+  template <typename PassT> void abandon() { abandon(PassT::ID()); }
+
+  /// Mark a particular analysis ID as abandoned, removing it from the
+  /// preserved set even if covered by some other set.
+  ///
+  /// Note that you can only abandon a specific analysis, not a *set* of
+  /// analyses.
+  void abandon(AnalysisKey *ID) {
+    // Clear this ID from the preserved set if present.
+    PreservedAnalysisIDs.erase(ID);
+
+    // And add it to the explicitly not-preserved set so that even if there is
+    // some general set being preserved that won't cause this particular
+    // analysis to be preserved.
+    NotPreservedAnalysisIDs.insert(ID);
+  }
+
   /// \brief Intersect this set with another in place.
   ///
   /// This is a mutating operation on this preserved set, removing all
   /// preserved passes which are not also preserved in the argument.
   void intersect(const PreservedAnalyses &Arg) {
     if (Arg.areAllPreserved())
       return;
     if (areAllPreserved()) {
-      PreservedAnalysisIDs = Arg.PreservedAnalysisIDs;
+      *this = Arg;
       return;
     }
+    // The intersection requires the union of the explicitly *not* preserved
+    // IDs and the intersection of the preserved IDs.
+    for (auto ID : Arg.NotPreservedAnalysisIDs) {
+      PreservedAnalysisIDs.erase(ID);
+      NotPreservedAnalysisIDs.insert(ID);
+    }
     for (auto ID : PreservedAnalysisIDs)
       if (!Arg.PreservedAnalysisIDs.count(ID))
         PreservedAnalysisIDs.erase(ID);
   }
 
   /// \brief Intersect this set with a temporary other set in place.
   ///
   /// This is a mutating operation on this preserved set, removing all
   /// preserved passes which are not also preserved in the argument.
   void intersect(PreservedAnalyses &&Arg) {
     if (Arg.areAllPreserved())
       return;
     if (areAllPreserved()) {
-      PreservedAnalysisIDs = std::move(Arg.PreservedAnalysisIDs);
+      *this = std::move(Arg);
       return;
     }
+    // The intersection requires the union of the explicitly *not* preserved
+    // IDs and the intersection of the preserved IDs.
+    for (auto ID : Arg.NotPreservedAnalysisIDs) {
+      PreservedAnalysisIDs.erase(ID);
+      NotPreservedAnalysisIDs.insert(ID);
+    }
     for (auto ID : PreservedAnalysisIDs)
       if (!Arg.PreservedAnalysisIDs.count(ID))
         PreservedAnalysisIDs.erase(ID);
   }
 
-  /// \brief Query whether a pass is marked as preserved by this set.
-  template <typename PassT> bool preserved() const {
-    return preserved(PassT::ID());
+  /// Query whether a particular analysis or one of the sets covering this
+  /// analysis is marked as preserved by this set.
+  ///
+  /// The list of sets following the analysis may be empty or may contain, for
+  /// example, a set abstractly representing all analyses on a particular unit
+  /// of IR or all analysis which rely only on the CFG being preserved, etc.
+  template <typename AnalysisT, typename... SetTs> bool preserved() const {
+    return preserved(AnalysisT::ID(), {SetTs::ID()...});
   }
 
-  /// \brief Query whether an abstract pass ID is marked as preserved by this
+  /// Query whether an abstract pass ID is marked as preserved by this
   /// set.
-  bool preserved(AnalysisKey *ID) const {
-    return PreservedAnalysisIDs.count(&AllAnalysesKey) ||
-           PreservedAnalysisIDs.count(ID);
+  bool preserved(AnalysisKey *ID,
+                 std::initializer_list<AnalysisKey *> SetIDs = {}) const {
+#ifndef NDEBUG
+    for (auto SetID : SetIDs)
+      assert(!NotPreservedAnalysisIDs.count(SetID) &&
+             "Either an analysis ID was provided as an abstract set ID, or a "
+             "set ID was abandoned.");
+#endif
+    if (NotPreservedAnalysisIDs.count(ID))
+      return false;
+    if (PreservedAnalysisIDs.count(ID))
+      return true;
+    if (PreservedAnalysisIDs.count(&AllAnalysesKey))
+      return true;
+    for (auto SetID : SetIDs)
+      if (PreservedAnalysisIDs.count(SetID))
+        return true;
+
+    // Neither the analysis nor any covering set was preserved.
+    return false;
   }
 
-  /// \brief Query whether all of the analyses in the set are preserved.
+  /// Query whether all of the analyses in the set are preserved.
   bool preserved(PreservedAnalyses Arg) {
     if (Arg.areAllPreserved())
       return areAllPreserved();
     for (auto ID : Arg.PreservedAnalysisIDs)
       if (!preserved(ID))
         return false;
     return true;
   }
 
-  /// \brief Test whether all passes are preserved.
+  /// Test whether all passes are preserved.
   ///
   /// This is used primarily to optimize for the case of no changes which will
   /// common in many scenarios.
   bool areAllPreserved() const {
-    return PreservedAnalysisIDs.count(&AllAnalysesKey);
+    return NotPreservedAnalysisIDs.empty() &&
+           PreservedAnalysisIDs.count(&AllAnalysesKey);
   }
 
 private:
-  // A special key used to indicate all analyses.
+  /// A special key used to indicate all analyses.
   static AnalysisKey AllAnalysesKey;
 
+  /// The set of preserved analyses.
+  ///
+  /// Unless covered directly or via some set here, analyses are assumed to not
+  /// be preserved.
   SmallPtrSet<AnalysisKey *, 2> PreservedAnalysisIDs;
+
+  /// The set of explicitly not-preserved analyses.
+  ///
+  /// This can override a set which is preserved above and make a specific
+  /// analysis not preserved. It always wins over the above set and should not
+  /// include the "all" set as that would be better done by clearing both sets
+  /// to be empty.
+  SmallPtrSet<AnalysisKey *, 2> NotPreservedAnalysisIDs;
 };
 
 // Forward declare the analysis manager template.
 template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager;
 
 /// A CRTP mix-in to automatically provide informational APIs needed for
 /// passes.
 ///
 /// This provides some boiler plate for types that are passes.
 template <typename DerivedT> struct PassInfoMixin {
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;
     }
 
+    bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) {
+      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!");
+      ResultConceptT &Result = *RI->second->second;
+
+      // Mark in the map whether the result should be invalidated and return
+      // that.
+      IMapI->second = Result.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;
template <typename PassT> void invalidate(IRUnitT &IR) {
     invalidateImpl(PassT::ID(), IR);
   }
 
   /// \brief Invalidate analyses cached for an IR unit.
   ///
   /// Walk through all of the analyses pertaining to this unit of IR and
   /// invalidate them unless they are preserved by the PreservedAnalyses set.
   void invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
-    // Short circuit for common cases of all analyses being preserved.
-    if (PA.areAllPreserved() || PA.preserved<AllAnalysesOn<IRUnitT>>())
+    // We can only use one short circuit because even if another set is
+    // preserved there might be abandoned analyses within that set which still
+    // require the full invalidation run.
+    if (PA.areAllPreserved())
       return;
 
     if (DebugLogging)
       dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName()
              << "\n";
 
     // Track whether each pass's result is invalidated. Memoize the results
     // using the IsResultInvalidated map.

 /// manager.
 ///
 /// This primarily provides an accessor to a parent module analysis manager to
 /// function passes. Only the const interface of the module analysis manager is
 /// provided to indicate that once inside of a function analysis pass you
 /// cannot request a module analysis to actually run. Instead, the user must
 /// rely on the \c getCachedResult API.
 ///
-/// This proxy *doesn't* manage the invalidation in any way. That is handled by
-/// the recursive return path of each layer of the pass manager and the
-/// returned PreservedAnalysis set.
+/// The invalidation provided by this proxy involves tracking when an
+/// invalidation event in the outer analysis manager needs to trigger an
+/// invalidation of a particular analysis on this IR unit.
+///
+/// Because outer analyses aren't invalidated while these IR units are being
+/// precessed, we have to register and handle these as deffered invalidation
+/// events.
 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs>
 class OuterAnalysisManagerProxy
     : public AnalysisInfoMixin<
           OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT>> {
 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 &,
         typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &) {
       return false;
     }
 
+    /// Register a deferred invalidation event for when the outer analysis
+    /// manager processes its invalidations.
+    template <typename OuterAnalysisT, typename InvalidatedAnalysisT>
+    void registerOuterAnalysisInvalidation() {
+      AnalysisKey *OuterID = OuterAnalysisT::ID();
+      AnalysisKey *InvalidatedID = InvalidatedAnalysisT::ID();
+
+      auto &InvalidatedIDList = OuterAnalysisInvalidationMap[OuterID];
+      // Note, this is a linear scan. If we end up with large numbers of
+      // analyses that all trigger invalidation on the same outer analysis,
+      // this entire system should be changed to some other deterministic
+      // datastructure such as a setvector of a pair of pointers.
+      auto InvalidatedIt = std::find(InvalidatedIDList.begin(),
+                                     InvalidatedIDList.end(), InvalidatedID);
+      if (InvalidatedIt == InvalidatedIDList.end())
+        InvalidatedIDList.push_back(InvalidatedID);
+    }
+
+    /// Access the map from outer analyses to deferred invalidation requiring
+    /// analyses.
+    const DenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>> &
+    getOuterInvalidations() const {
+      return OuterAnalysisInvalidationMap;
+    }
+
   private:
     const AnalysisManagerT *AM;
+
+    /// A map from an outer analysis ID to the set of this IR-unit's analyses
+    /// which need to be invalidated.
+    DenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>>
+        OuterAnalysisInvalidationMap;
   };
 
   OuterAnalysisManagerProxy(const AnalysisManagerT &AM) : AM(&AM) {}
 
   /// \brief Run the analysis pass and create our proxy result object.
   /// Nothing to see here, it just forwards the \c AM reference into the
   /// result.
   Result run(IRUnitT &, AnalysisManager<IRUnitT, ExtraArgTs...> &,

include/llvm/IR/PassManagerInternal.h

 
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include <memory>
 #include <utility>
 
 namespace llvm {
 
+template <typename IRUnitT> class AllAnalysesOn;
 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
struct AnalysisResultModel<IRUnitT, PassT, ResultT, PreservedAnalysesT,
 
   /// \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,
                   InvalidatorT &) override {
-    return !PA.preserved(PassT::ID());
+    return !PA.template preserved<PassT, AllAnalysesOn<IRUnitT>>();
   }
 
   ResultT Result;
 };
 
 /// \brief Specialization of \c AnalysisResultModel which delegates invalidate
 /// handling to \c ResultT.
 template <typename IRUnitT, typename PassT, typename ResultT,

lib/Analysis/CGSCCPassManager.cpp

if (DebugLogging)
     dbgs() << "Finished CGSCC pass manager run.\n";
 
   return PA;
 }
 
 bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
     Module &M, const PreservedAnalyses &PA,
     ModuleAnalysisManager::Invalidator &Inv) {
+  // If literally everything is preserved, we're done.
+  if (PA.areAllPreserved())
+    return false; // This is still a valid proxy.
+
   // If this proxy or the call graph is going to be invalidated, we also need
   // to clear all the keys coming from that analysis.
   //
   // We also directly invalidate the FAM's module proxy if necessary and if
   // that proxy isn't preserved we can't preserve this proxy either. We rely on
   // it to handle module -> function analysis invalidation in the face of
   // structural changes and so if unavailable we conservatively clear the
   // entire SCC layer as well rather than trying to do invaliadtion ourselves.
-  if (!PA.preserved<CGSCCAnalysisManagerModuleProxy>() ||
+  if (!PA.preserved<CGSCCAnalysisManagerModuleProxy, AllAnalysesOn<Module>>() ||
       Inv.invalidate<LazyCallGraphAnalysis>(M, PA) ||
       Inv.invalidate<FunctionAnalysisManagerModuleProxy>(M, PA)) {
     InnerAM->clear();
 
     // And the proxy itself should be marked as invalid so that we can observe
     // the new call graph if and when created. This isn't strictly necessary
     // because we cheat above, but is still useful.
     return true;
   }
 
+  // Directly check if the relevant set is preserved.
+  bool AreSCCAnalysesPreserved =
+      PA.preserved<AllAnalysesOn<LazyCallGraph::SCC>>();
+
   // Ok, we have a graph so we can propagate the invalidation down into it.
   // Note that we do this even if the call graph is about to become invalid so
   // that we trigger any secondary invalidation within the cached results for
   // this inner analysis manager before we remove those results entirely. As an
   // example, we want to first propagate the invalidation to any function
   // analysis results that could be cached via a CGSCC proxy before we remove
   // that proxy.
   for (auto &RC : G->postorder_ref_sccs())
-    for (auto &C : RC)
+    for (auto &C : RC) {
+      Optional<PreservedAnalyses> InnerPA;
+
+      // Check to see whether the preserved set needs to be pruned based on
+      // module-level analysis invalidation that triggers deffered invalidation
+      // registered with the outer analysis manager proxy for this SCC.
+      if (auto *OuterProxy =
+              InnerAM->getCachedResult<ModuleAnalysisManagerCGSCCProxy>(C))
+        for (const auto &OuterInvalidationPair :
+             OuterProxy->getOuterInvalidations()) {
+          AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
+          const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
+          if (Inv.invalidate(OuterAnalysisID, M, PA)) {
+            if (!InnerPA)
+              InnerPA = PA;
+            for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
+              InnerPA->abandon(InnerAnalysisID);
+          }
+        }
+
+      // Check if we needed a custom PA set, and if so we'll need to run the
+      // inner invalidation.
+      if (InnerPA) {
+        InnerAM->invalidate(C, *InnerPA);
+        continue;
+      }
+
+      // Otherwise we only need to do invalidation if the original PA set didn't
+      // preserve all SCC analyses.
+      if (!AreSCCAnalysesPreserved)
         InnerAM->invalidate(C, PA);
+    }
 
   // Otherwise false to indicate that this result is still a valid proxy.
   return false;
 }
 
 template <>
 CGSCCAnalysisManagerModuleProxy::Result
 CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM) {

lib/IR/PassManager.cpp

 template class AnalysisManager<Function>;
 template class InnerAnalysisManagerProxy<FunctionAnalysisManager, Module>;
 template class OuterAnalysisManagerProxy<ModuleAnalysisManager, Function>;
 
 template <>
 bool FunctionAnalysisManagerModuleProxy::Result::invalidate(
     Module &M, const PreservedAnalyses &PA,
     ModuleAnalysisManager::Invalidator &Inv) {
+  // If literally everything is preserved, we're done.
+  if (PA.areAllPreserved())
+    return false; // This is still a valid proxy.
+
   // If this proxy isn't marked as preserved, then even if the result remains
   // valid, the key itself may no longer be valid, so we clear everything.
   //
   // Note that in order to preserve this proxy, a module pass must ensure that
   // the FAM has been completely updated to handle the deletion of functions.
   // Specifically, any FAM-cached results for those functions need to have been
   // forcibly cleared. When preserved, this proxy will only invalidate results
   // cached on functions *still in the module* at the end of the module pass.
-  if (!PA.preserved(FunctionAnalysisManagerModuleProxy::ID())) {
+  if (!PA.preserved<FunctionAnalysisManagerModuleProxy,
+                    AllAnalysesOn<Module>>()) {
     InnerAM->clear();
     return true;
   }
 
-  // Otherwise propagate the invalidation event to all the remaining IR units.
-  for (Function &F : M)
+  // Directly check if the relevant set is preserved.
+  bool AreFunctionAnalysesPreserved = PA.preserved<AllAnalysesOn<Function>>();
+
+  // Now walk all the functions to see if any inner analysis invalidation is
+  // necessary.
+  for (Function &F : M) {
+    Optional<PreservedAnalyses> FunctionPA;
+
+    // Check to see whether the preserved set needs to be pruned based on
+    // module-level analysis invalidation that triggers deferred invalidation
+    // registered with the outer analysis manager proxy for this function.
+    if (auto *OuterProxy =
+            InnerAM->getCachedResult<ModuleAnalysisManagerFunctionProxy>(F))
+      for (const auto &OuterInvalidationPair :
+           OuterProxy->getOuterInvalidations()) {
+        AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
+        const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
+        if (Inv.invalidate(OuterAnalysisID, M, PA)) {
+          if (!FunctionPA)
+            FunctionPA = PA;
+          for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
+            FunctionPA->abandon(InnerAnalysisID);
+        }
+      }
+
+    // Check if we needed a custom PA set, and if so we'll need to run the
+    // inner invalidation.
+    if (FunctionPA) {
+      InnerAM->invalidate(F, *FunctionPA);
+      continue;
+    }
+
+    // Otherwise we only need to do invalidation if the original PA set didn't
+    // preserve all function analyses.
+    if (!AreFunctionAnalysesPreserved)
       InnerAM->invalidate(F, PA);
+  }
 
   // Return false to indicate that this result is still a valid proxy.
   return false;
 }
 }
 
 AnalysisKey PreservedAnalyses::AllAnalysesKey;

unittests/Analysis/CGSCCPassManagerTest.cpp

// manage to invalidate everything.
     CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
     MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 
     MPM.run(*M, MAM);
     // Two runs and 6 functions.
     EXPECT_EQ(2 * 6, FunctionAnalysisRuns);
   }
 }
+
+/// A test CGSCC-level 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.
+///
+/// FIXME: Currently this doesn't also depend on a function analysis and if it
+/// did we would fail to invalidated it correctly.
+struct TestIndirectSCCAnalysis
+    : public AnalysisInfoMixin<TestIndirectSCCAnalysis> {
+  struct Result {
+    Result(TestSCCAnalysis::Result &SCCDep, TestModuleAnalysis::Result &MDep)
+        : SCCDep(SCCDep), MDep(MDep) {}
+    TestSCCAnalysis::Result &SCCDep;
+    TestModuleAnalysis::Result &MDep;
+
+    bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
+                    CGSCCAnalysisManager::Invalidator &Inv) {
+      return !PA.preserved<TestIndirectSCCAnalysis,
+                           AllAnalysesOn<LazyCallGraph::SCC>>() ||
+             Inv.invalidate<TestSCCAnalysis>(C, PA);
+    }
+  };
+
+  TestIndirectSCCAnalysis(int &Runs) : Runs(Runs) {}
+
+  /// Run the analysis pass over the function and return a result.
+  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+             LazyCallGraph &CG) {
+    ++Runs;
+    auto &SCCDep = AM.getResult<TestSCCAnalysis>(C, CG);
+
+    auto &ModuleProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
+    const ModuleAnalysisManager &MAM = ModuleProxy.getManager();
+    // For the test, we insist that the module analysis starts off in the
+    // cache.
+    auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(
+        *C.begin()->getFunction().getParent());
+    // Register the dependency as module analysis dependencies have to be
+    // pre-registered on the proxy.
+    ModuleProxy.registerOuterAnalysisInvalidation<TestModuleAnalysis,
+                                                  TestIndirectSCCAnalysis>();
+
+    return Result(SCCDep, MDep);
+  }
+
+private:
+  friend AnalysisInfoMixin<TestIndirectSCCAnalysis>;
+  static AnalysisKey Key;
+
+  int &Runs;
+};
+
+AnalysisKey TestIndirectSCCAnalysis::Key;
+
+/// A test analysis pass which chaches in its result the result from the above
+/// indirect analysis pass.
+///
+/// This allows us to ensure that whenever an analysis pass is invalidated due
+/// to dependencies (especially dependencies across IR units that trigger
+/// asynchronous invalidation) we correctly detect that this may in turn cause
+/// other analysis to be invalidated.
+struct TestDoublyIndirectSCCAnalysis
+    : public AnalysisInfoMixin<TestDoublyIndirectSCCAnalysis> {
+  struct Result {
+    Result(TestIndirectSCCAnalysis::Result &IDep) : IDep(IDep) {}
+    TestIndirectSCCAnalysis::Result &IDep;
+
+    bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
+                    CGSCCAnalysisManager::Invalidator &Inv) {
+      return !PA.preserved<TestDoublyIndirectSCCAnalysis,
+                           AllAnalysesOn<LazyCallGraph::SCC>>() ||
+             Inv.invalidate<TestIndirectSCCAnalysis>(C, PA);
+    }
+  };
+
+  TestDoublyIndirectSCCAnalysis(int &Runs) : Runs(Runs) {}
+
+  /// Run the analysis pass over the function and return a result.
+  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+             LazyCallGraph &CG) {
+    ++Runs;
+    auto &IDep = AM.getResult<TestIndirectSCCAnalysis>(C, CG);
+    return Result(IDep);
+  }
+
+private:
+  friend AnalysisInfoMixin<TestDoublyIndirectSCCAnalysis>;
+  static AnalysisKey Key;
+
+  int &Runs;
+};
+
+AnalysisKey TestDoublyIndirectSCCAnalysis::Key;
+
+/// A test analysis pass which caches results from three different IR unit
+/// layers and requires intermediate layers to correctly propagate the entire
+/// distance.
+struct TestIndirectFunctionAnalysis
+    : public AnalysisInfoMixin<TestIndirectFunctionAnalysis> {
+  struct Result {
+    Result(TestFunctionAnalysis::Result &FDep, TestModuleAnalysis::Result &MDep,
+           TestSCCAnalysis::Result &SCCDep)
+        : FDep(FDep), MDep(MDep), SCCDep(SCCDep) {}
+    TestFunctionAnalysis::Result &FDep;
+    TestModuleAnalysis::Result &MDep;
+    TestSCCAnalysis::Result &SCCDep;
+
+    bool invalidate(Function &F, const PreservedAnalyses &PA,
+                    FunctionAnalysisManager::Invalidator &Inv) {
+      return !PA.preserved<TestIndirectFunctionAnalysis,
+                           AllAnalysesOn<Function>>() ||
+             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;
+    auto &FDep = AM.getResult<TestFunctionAnalysis>(F);
+
+    auto &ModuleProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
+    const ModuleAnalysisManager &MAM = ModuleProxy.getManager();
+    // For the test, we insist that the module analysis starts off in the
+    // cache.
+    auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(*F.getParent());
+    // Register the dependency as module analysis dependencies have to be
+    // pre-registered on the proxy.
+    ModuleProxy.registerOuterAnalysisInvalidation<
+        TestModuleAnalysis, TestIndirectFunctionAnalysis>();
+
+    // For thet test we assume this is run inside a CGSCC pass manager.
+    const LazyCallGraph &CG =
+        *MAM.getCachedResult<LazyCallGraphAnalysis>(*F.getParent());
+    auto &CGSCCProxy = AM.getResult<CGSCCAnalysisManagerFunctionProxy>(F);
+    const CGSCCAnalysisManager &CGAM = CGSCCProxy.getManager();
+    // For the test, we insist that the CGSCC analysis starts off in the cache.
+    auto &SCCDep =
+        *CGAM.getCachedResult<TestSCCAnalysis>(*CG.lookupSCC(*CG.lookup(F)));
+    // Register the dependency as CGSCC analysis dependencies have to be
+    // pre-registered on the proxy.
+    CGSCCProxy.registerOuterAnalysisInvalidation<
+        TestSCCAnalysis, TestIndirectFunctionAnalysis>();
+
+    return Result(FDep, MDep, SCCDep);
+  }
+
+private:
+  friend AnalysisInfoMixin<TestIndirectFunctionAnalysis>;
+  static AnalysisKey Key;
+
+  int &Runs;
+};
+
+AnalysisKey TestIndirectFunctionAnalysis::Key;
+
+TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
+  int ModuleAnalysisRuns = 0;
+  MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
+
+  int SCCAnalysisRuns = 0, IndirectSCCAnalysisRuns = 0,
+      DoublyIndirectSCCAnalysisRuns = 0;
+  CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
+  CGAM.registerPass(
+      [&] { return TestIndirectSCCAnalysis(IndirectSCCAnalysisRuns); });
+  CGAM.registerPass([&] {
+    return TestDoublyIndirectSCCAnalysis(DoublyIndirectSCCAnalysisRuns);
+  });
+
+  int FunctionAnalysisRuns = 0, IndirectFunctionAnalysisRuns = 0;
+  FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
+  FAM.registerPass([&] {
+    return TestIndirectFunctionAnalysis(IndirectFunctionAnalysisRuns);
+  });
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+
+  int FunctionCount = 0;
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  // First just use the analysis to get the function count and preserve
+  // everything.
+  CGPM.addPass(
+      LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &) {
+        auto &DoublyIndirectResult =
+            AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
+        auto &IndirectResult = DoublyIndirectResult.IDep;
+        FunctionCount += IndirectResult.SCCDep.FunctionCount;
+        return PreservedAnalyses::all();
+      }));
+  // Next, invalidate
+  //   - both analyses for the (f) and (x) SCCs,
+  //   - just the underlying (indirect) analysis for (g) SCC, and
+  //   - just the direct analysis for (h1,h2,h3) SCC.
+  CGPM.addPass(
+      LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &) {
+        auto &DoublyIndirectResult =
+            AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
+        auto &IndirectResult = DoublyIndirectResult.IDep;
+        FunctionCount += IndirectResult.SCCDep.FunctionCount;
+        auto PA = PreservedAnalyses::none();
+        if (C.getName() == "(g)")
+          PA.preserve<TestSCCAnalysis>();
+        else if (C.getName() == "(h3, h1, h2)")
+          PA.preserve<TestIndirectSCCAnalysis>();
+        return PA;
+      }));
+  // Finally, use the analysis again on each function, forcing re-computation
+  // for all of them.
+  CGPM.addPass(
+      LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &) {
+        auto &DoublyIndirectResult =
+            AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
+        auto &IndirectResult = DoublyIndirectResult.IDep;
+        FunctionCount += IndirectResult.SCCDep.FunctionCount;
+        return PreservedAnalyses::all();
+      }));
+
+  // Create a second CGSCC pass manager. This will cause the module-level
+  // invalidation to occur, which will force yet another invalidation of the
+  // indirect SCC-level analysis as the module analysis it depends on gets
+  // invalidated.
+  CGSCCPassManager CGPM2(/*DebugLogging*/ true);
+  CGPM2.addPass(
+      LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &) {
+        auto &DoublyIndirectResult =
+            AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
+        auto &IndirectResult = DoublyIndirectResult.IDep;
+        FunctionCount += IndirectResult.SCCDep.FunctionCount;
+        return PreservedAnalyses::all();
+      }));
+
+  // Add a requires pass to populate the module analysis and then our function
+  // pass pipeline.
+  MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  // Now require the module analysis again (it will have been invalidated once)
+  // and then use it again from a function pass manager.
+  MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
+  MPM.run(*M, MAM);
+
+  // There are generally two possible runs for each of the four SCCs. But
+  // for one SCC, we only invalidate the indirect analysis so the base one
+  // only gets run seven times.
+  EXPECT_EQ(7, SCCAnalysisRuns);
+  // The module analysis pass should be run twice here.
+  EXPECT_EQ(2, ModuleAnalysisRuns);
+  // The indirect analysis is invalidated (either directly or indirectly) three
+  // times for each of four SCCs.
+  EXPECT_EQ(3 * 4, IndirectSCCAnalysisRuns);
+  EXPECT_EQ(3 * 4, DoublyIndirectSCCAnalysisRuns);
+
+  // Four passes count each of six functions once (via SCCs).
+  EXPECT_EQ(4 * 6, FunctionCount);
+}
 }

unittests/IR/PassManagerTest.cpp

PassManagerTest()
                            "define void @h() {\n"
                            "  ret void\n"
                            "}\n")) {}
 };
 
 TEST_F(PassManagerTest, BasicPreservedAnalyses) {
   PreservedAnalyses PA1 = PreservedAnalyses();
   EXPECT_FALSE(PA1.preserved<TestFunctionAnalysis>());
+  EXPECT_FALSE(
+      (PA1.preserved<TestFunctionAnalysis, AllAnalysesOn<Function>>()));
   EXPECT_FALSE(PA1.preserved<TestModuleAnalysis>());
+  EXPECT_FALSE((PA1.preserved<TestModuleAnalysis, AllAnalysesOn<Module>>()));
   PreservedAnalyses PA2 = PreservedAnalyses::none();
   EXPECT_FALSE(PA2.preserved<TestFunctionAnalysis>());
   EXPECT_FALSE(PA2.preserved<TestModuleAnalysis>());
   PreservedAnalyses PA3 = PreservedAnalyses::all();
   EXPECT_TRUE(PA3.preserved<TestFunctionAnalysis>());
   EXPECT_TRUE(PA3.preserved<TestModuleAnalysis>());
   PreservedAnalyses PA4 = PA1;
   EXPECT_FALSE(PA4.preserved<TestFunctionAnalysis>());

 }
 
 /// 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;
+    Result(TestFunctionAnalysis::Result &FDep, TestModuleAnalysis::Result &MDep)
+        : FDep(FDep), MDep(MDep) {}
+    TestFunctionAnalysis::Result &FDep;
+    TestModuleAnalysis::Result &MDep;
 
     bool invalidate(Function &F, const PreservedAnalyses &PA,
                     FunctionAnalysisManager::Invalidator &Inv) {
-      return !PA.preserved<TestIndirectFunctionAnalysis>() ||
+      return !PA.preserved<TestIndirectFunctionAnalysis,
+                           AllAnalysesOn<Function>>() ||
              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));
+    auto &FDep = AM.getResult<TestFunctionAnalysis>(F);
+    auto &Proxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
+    const ModuleAnalysisManager &MAM = Proxy.getManager();
+    // For the test, we insist that the module analysis starts off in the
+    // cache.
+    auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(*F.getParent());
+    // And register the dependency as module analysis dependencies have to be
+    // pre-registered on the proxy.
+    Proxy.registerOuterAnalysisInvalidation<TestModuleAnalysis,
+                                            TestIndirectFunctionAnalysis>();
+    return Result(FDep, MDep);
   }
 
 private:
   friend AnalysisInfoMixin<TestIndirectFunctionAnalysis>;
   static AnalysisKey Key;
 
   int &Runs;
 };
 
 AnalysisKey TestIndirectFunctionAnalysis::Key;
 
+/// A test analysis pass which chaches in its result the result from the above
+/// indirect analysis pass.
+///
+/// This allows us to ensure that whenever an analysis pass is invalidated due
+/// to dependencies (especially dependencies across IR units that trigger
+/// asynchronous invalidation) we correctly detect that this may in turn cause
+/// other analysis to be invalidated.
+struct TestDoublyIndirectFunctionAnalysis
+    : public AnalysisInfoMixin<TestDoublyIndirectFunctionAnalysis> {
+  struct Result {
+    Result(TestIndirectFunctionAnalysis::Result &IDep) : IDep(IDep) {}
+    TestIndirectFunctionAnalysis::Result &IDep;
+
+    bool invalidate(Function &F, const PreservedAnalyses &PA,
+                    FunctionAnalysisManager::Invalidator &Inv) {
+      return !PA.preserved<TestDoublyIndirectFunctionAnalysis,
+                           AllAnalysesOn<Function>>() ||
+             Inv.invalidate<TestIndirectFunctionAnalysis>(F, PA);
+    }
+  };
+
+  TestDoublyIndirectFunctionAnalysis(int &Runs) : Runs(Runs) {}
+
+  /// Run the analysis pass over the function and return a result.
+  Result run(Function &F, FunctionAnalysisManager &AM) {
+    ++Runs;
+    auto &IDep = AM.getResult<TestIndirectFunctionAnalysis>(F);
+    return Result(IDep);
+  }
+
+private:
+  friend AnalysisInfoMixin<TestDoublyIndirectFunctionAnalysis>;
+  static AnalysisKey Key;
+
+  int &Runs;
+};
+
+AnalysisKey TestDoublyIndirectFunctionAnalysis::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); });
+  int FunctionAnalysisRuns = 0, ModuleAnalysisRuns = 0,
+      IndirectAnalysisRuns = 0, DoublyIndirectAnalysisRuns = 0;
+  FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
   FAM.registerPass(
       [&] { return TestIndirectFunctionAnalysis(IndirectAnalysisRuns); });
+  FAM.registerPass([&] {
+    return TestDoublyIndirectFunctionAnalysis(DoublyIndirectAnalysisRuns);
+  });
 
   ModuleAnalysisManager MAM(/*DebugLogging*/ true);
+  MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
   MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
   FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
 
-  int InstrCount = 0;
+  int InstrCount = 0, FunctionCount = 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;
+    auto &DoublyIndirectResult =
+        AM.getResult<TestDoublyIndirectFunctionAnalysis>(F);
+    auto &IndirectResult = DoublyIndirectResult.IDep;
+    InstrCount += IndirectResult.FDep.InstructionCount;
+    FunctionCount += IndirectResult.MDep.FunctionCount;
     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 &DoublyIndirectResult =
+        AM.getResult<TestDoublyIndirectFunctionAnalysis>(F);
+    auto &IndirectResult = DoublyIndirectResult.IDep;
+    InstrCount += IndirectResult.FDep.InstructionCount;
+    FunctionCount += IndirectResult.MDep.FunctionCount;
     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;
+    auto &DoublyIndirectResult =
+        AM.getResult<TestDoublyIndirectFunctionAnalysis>(F);
+    auto &IndirectResult = DoublyIndirectResult.IDep;
+    InstrCount += IndirectResult.FDep.InstructionCount;
+    FunctionCount += IndirectResult.MDep.FunctionCount;
     return PreservedAnalyses::all();
   }));
+
+  // Create a second function pass manager. This will cause the module-level
+  // invalidation to occur, which will force yet another invalidation of the
+  // indirect function-level analysis as the module analysis it depends on gets
+  // invalidated.
+  FunctionPassManager FPM2(/*DebugLogging*/ true);
+  FPM2.addPass(LambdaPass([&](Function &F, FunctionAnalysisManager &AM) {
+    auto &DoublyIndirectResult =
+        AM.getResult<TestDoublyIndirectFunctionAnalysis>(F);
+    auto &IndirectResult = DoublyIndirectResult.IDep;
+    InstrCount += IndirectResult.FDep.InstructionCount;
+    FunctionCount += IndirectResult.MDep.FunctionCount;
+    return PreservedAnalyses::all();
+  }));
+
+  // Add a requires pass to populate the module analysis and then our function
+  // pass pipeline.
+  MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
+  // Now require the module analysis again (it will have been invalidated once)
+  // and then use it again from a function pass manager.
+  MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
+  MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM2)));
   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);
+  EXPECT_EQ(5, FunctionAnalysisRuns);
+  // The module analysis pass should be run twice here.
+  EXPECT_EQ(2, ModuleAnalysisRuns);
   // The indirect analysis is invalidated for each function (either directly or
   // indirectly) and run twice for each.
-  EXPECT_EQ(6, IndirectAnalysisRuns);
+  EXPECT_EQ(9, IndirectAnalysisRuns);
+  EXPECT_EQ(9, DoublyIndirectAnalysisRuns);
 
-  // There are five instructions in the module and we add the count three
+  // There are five instructions in the module and we add the count four
   // times.
-  EXPECT_EQ(5 * 3, InstrCount);
+  EXPECT_EQ(5 * 4, InstrCount);
+
+  // There are three functions and we count them four times for each of the
+  // three functions.
+  EXPECT_EQ(3 * 4 * 3, FunctionCount);
 }
 }