[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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

and even if already explicitly marked as preserved.

113 ↗

(On Diff #79533)

Should this note appear above as well?

119 ↗

(On Diff #79533)

s/, that/

136 ↗

(On Diff #79533)

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

158 ↗

(On Diff #79533)

ibid.

179 ↗

(On Diff #79533)

Looks like this comment should be updated too?

235 ↗

(On Diff #79533)

s/ as/, as/

236 ↗

(On Diff #79533)

s/to be empty//

236 ↗

(On Diff #79533)

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

506 ↗

(On Diff #79533)

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

?

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

675 ↗

(On Diff #79533)

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

956 ↗

(On Diff #79533)

deffered

988 ↗

(On Diff #79533)

s/datastructure/data structure/

1007 ↗

(On Diff #79533)

You don't want a version with inline storage?

lib/Analysis/CGSCCPassManager.cpp

103 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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

130 ↗

(On Diff #79533)

deffered

131 ↗

(On Diff #79533)

Run-on sentence

131 ↗

(On Diff #79533)

proxies

146 ↗

(On Diff #79533)

Split into two sentences.

lib/IR/PassManager.cpp

86 ↗

(On Diff #79533)

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

Probably not something to be fixed in this patch.

unittests/Analysis/CGSCCPassManagerTest.cpp

846 ↗

(On Diff #79533)

invalidate

894 ↗

(On Diff #79533)

chaches

unittests/IR/PassManagerTest.cpp

431 ↗

(On Diff #79533)

+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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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

506 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

Reworded to hopefully make this more clear.

unittests/IR/PassManagerTest.cpp

431 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #80994)

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 ↗

(On Diff #80994)

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

244 ↗

(On Diff #80994)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #79533)

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 ↗

(On Diff #80994)

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 ↗

(On Diff #80994)

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?

244 ↗

(On Diff #80994)

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

104 ↗

(On Diff #81363)

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

113 ↗

(On Diff #81363)

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

104 ↗

(On Diff #81363)

Doh! Good catch....

113 ↗

(On Diff #81363)

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

675 ↗

(On Diff #79533)

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

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

?

72 ↗

(On Diff #81507)

te

73 ↗

(On Diff #81507)

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

86 ↗

(On Diff #81507)

to indicate that they preserve

87 ↗

(On Diff #81507)

set off "such as its CFG" with parens

90 ↗

(On Diff #81507)

", which"

94 ↗

(On Diff #81507)

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.

95 ↗

(On Diff #81507)

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

96 ↗

(On Diff #81507)

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

101 ↗

(On Diff #81507)

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.

113 ↗

(On Diff #81507)

Not sure this para is necessary with the rewrite above.

117 ↗

(On Diff #81507)

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.

133 ↗

(On Diff #81507)

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.

157 ↗

(On Diff #81507)

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

164 ↗

(On Diff #81507)

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

176 ↗

(On Diff #81507)

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.

190 ↗

(On Diff #81507)

Nit, "not-preserved".

227 ↗

(On Diff #81507)

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.

253 ↗

(On Diff #81507)

s/in turn//

253 ↗

(On Diff #81507)

overal

254 ↗

(On Diff #81507)

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.

262 ↗

(On Diff #81507)

Same comments here.

268 ↗

(On Diff #81507)

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

270 ↗

(On Diff #81507)

Suggest something like

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

280 ↗

(On Diff #81507)

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

288 ↗

(On Diff #81507)

ibid.

297 ↗

(On Diff #81507)

Suggest

The analyses and analysis sets that are preserved.

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

300 ↗

(On Diff #81507)

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

307 ↗

(On Diff #81507)

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.

560 ↗

(On Diff #81507)

", 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.

562 ↗

(On Diff #81507)

s/needed/needs/?

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

570 ↗

(On Diff #81507)

implemente

573 ↗

(On Diff #81507)

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

lib/Analysis/CGSCCPassManager.cpp

117 ↗

(On Diff #81507)

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

828 ↗

(On Diff #81507)

", 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

675 ↗

(On Diff #79533)

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.

133 ↗

(On Diff #81507)

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

157 ↗

(On Diff #81507)

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

164 ↗

(On Diff #81507)

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

227 ↗

(On Diff #81507)

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

297 ↗

(On Diff #81507)

Took a slightly different approach but same spirit.

560 ↗

(On Diff #81507)

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.

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

133 ↗

(On Diff #81507)

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.

157 ↗

(On Diff #81507)

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.

164 ↗

(On Diff #81507)

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

560 ↗

(On Diff #81507)

Heh, okay. Sorry that wasn't helpful.

219 ↗

(On Diff #81724)

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.

271 ↗

(On Diff #81724)

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

278 ↗

(On Diff #81724)

ibid

560 ↗

(On Diff #81724)

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.

[chandlerc]

Update with even better comments thanks to Justin!

include/llvm/IR/PassManager.h

133 ↗

(On Diff #81507)

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

157 ↗

(On Diff #81507)

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.

llvm/trunk/include/llvm/Analysis/CGSCCPassManager.h

for (auto RCI = CG.postorder_ref_scc_begin(),
           } while (UR.UpdatedC);
 
         } while (!CWorklist.empty());
       } while (!RCWorklist.empty());
     }
 
     // By definition we preserve the call garph, all SCC analyses, and the
     // analysis proxies by handling them above and in any nested pass managers.
+    PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
     PA.preserve<LazyCallGraphAnalysis>();
-    PA.preserve<AllAnalysesOn<LazyCallGraph::SCC>>();
     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
     PA.preserve<FunctionAnalysisManagerModuleProxy>();
     return PA;
   }
 
 private:
   CGSCCPassT Pass;
   bool DebugLogging;
for (LazyCallGraph::Node *N : Nodes) {
       assert(CG.lookupSCC(*N) == CurrentC &&
              "Current SCC not updated to the SCC containing the current node!");
     }
 
     // By definition we preserve the proxy. And we preserve all analyses on
     // Functions. This precludes *any* invalidation of function analyses by the
     // proxy, but that's OK because we've taken care to invalidate analyses in
     // the function analysis manager incrementally above.
-    PA.preserve<AllAnalysesOn<Function>>();
+    PA.preserveSet<AllAnalysesOn<Function>>();
     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 
     // We've also ensured that we updated the call graph along the way.
     PA.preserve<LazyCallGraphAnalysis>();
 
     return PA;
   }
 

llvm/trunk/include/llvm/Analysis/LoopPassManager.h

while (!WorkList.empty()) {
       WorkList.insert(WorkList.end(), L->begin(), L->end());
       Loops.push_back(L);
     }
 
     // Now pop each element off of the stack to visit the loops in reverse
     // post-order.
     for (auto *L : reverse(Loops)) {
       PreservedAnalyses PassPA = Pass.run(*L, LAM);
-      assert(PassPA.preserved(getLoopPassPreservedAnalyses()) &&
-             "Loop passes must preserve all relevant analyses");
+      // FIXME: We should verify the set of analyses relevant to Loop passes
+      // are preserved.
 
       // We know that the loop pass couldn't have invalidated any other loop's
       // analyses (that's the contract of a loop pass), so directly handle the
       // loop analysis manager's invalidation here.
       LAM.invalidate(*L, PassPA);
 
       // Then intersect the preserved set so that invalidation of module
       // analyses will eventually occur when the module pass completes.
       PA.intersect(std::move(PassPA));
     }
 
     // By definition we preserve the proxy. We also preserve all analyses on
     // Loops. This precludes *any* invalidation of loop analyses by the proxy,
     // but that's OK because we've taken care to invalidate analyses in the
     // loop analysis manager incrementally above.
-    PA.preserve<AllAnalysesOn<Loop>>();
+    PA.preserveSet<AllAnalysesOn<Loop>>();
     PA.preserve<LoopAnalysisManagerFunctionProxy>();
     return PA;
   }
 
 private:
   LoopPassT Pass;
 };
 

llvm/trunk/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>
 #include <memory>
 #include <vector>
 
 namespace llvm {
 
 /// A special type used by analysis passes to provide an address that
 /// identifies that particular analysis pass type.
 ///
 /// Analysis passes should have a static data member of this type and derive
 /// from the \c AnalysisInfoMixin to get a static ID method used to identify
 /// the analysis in the pass management infrastructure.
 struct alignas(8) AnalysisKey {};
 
-/// \brief An abstract set of preserved analyses following a transformation pass
-/// run.
+/// A special type used to provide an address that identifies a set of related
+/// analyses.
+///
+/// These sets are primarily used below to mark sets of analyses as preserved.
+/// An example would be analyses depending only on the CFG of a function.
+/// A transformation can mark that it is preserving the CFG of a function and
+/// then analyses can check for this rather than each transform having to fully
+/// enumerate every analysis preserved.
+struct alignas(8) AnalysisSetKey {};
+
+/// Class for tracking what analyses are preserved after a transformation pass
+/// runs over some unit of IR.
+///
+/// Transformation passes build and return these objects when run over the IR
+/// to communicate which analyses remain valid afterward. For most passes this
+/// is fairly simple: if they don't change anything all analyses are preserved,
+/// otherwise only a short list of analyses that have been explicitly updated
+/// are preserved.
+///
+/// This class also provides the ability to mark abstract *sets* of analyses as
+/// preserved. These sets allow passes to indicate that they preserve broad
+/// aspects of the IR (such as its CFG) and analyses to opt in to that being
+/// sufficient without the passes having to fully enumerate such analyses.
 ///
-/// 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.
+/// Finally, this class can represent "abandoning" an analysis, which marks it
+/// as not-preserved even if it would be covered by some abstract set of
+/// analyses.
 ///
-/// There is also an explicit all state which can be used (for example) when
-/// the IR is not mutated at all.
+/// 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.
+///
+/// ```
+///   auto PAC = PA.getChecker<MyAnalysisType>();
+///   if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() ||
+///       (PAC.preservedSet<AnalysisSetA>() &&
+///        PAC.preservedSet<AnalysisSetB>())) {
+///     // The analysis has been successfully preserved ...
+///   }
+/// ```
 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);
+    PA.PreservedIDs.insert(&AllAnalysesKey);
     return PA;
   }
 
-  /// \brief Mark a particular pass as preserved, adding it to the set.
-  template <typename PassT> void preserve() { preserve(PassT::ID()); }
+  /// Mark an analysis as preserved.
+  template <typename AnalysisT> void preserve() { preserve(AnalysisT::ID()); }
 
-  /// \brief Mark an abstract ID as preserved, adding it to the set.
+  /// Mark an analysis as preserved using its ID.
   void preserve(AnalysisKey *ID) {
+    // Clear this ID from the explicit not-preserved set if present.
+    NotPreservedAnalysisIDs.erase(ID);
+
+    // If we're not already preserving all analyses (other than those in
+    // NotPreservedAnalysisIDs).
     if (!areAllPreserved())
-      PreservedAnalysisIDs.insert(ID);
+      PreservedIDs.insert(ID);
+  }
+
+  /// Mark an analysis set as preserved.
+  template <typename AnalysisSetT> void preserveSet() {
+    preserveSet(AnalysisSetT::ID());
+  }
+
+  /// Mark an analysis set as preserved using its ID.
+  void preserveSet(AnalysisSetKey *ID) {
+    // If we're not already in the saturated 'all' state, add this set.
+    if (!areAllPreserved())
+      PreservedIDs.insert(ID);
+  }
+
+  /// Mark an analysis as abandoned.
+  ///
+  /// An abandoned analysis is not preserved, even if it is nominally covered
+  /// by some other set or was previously explicitly marked as preserved.
+  ///
+  /// Note that you can only abandon a specific analysis, not a *set* of
+  /// analyses.
+  template <typename AnalysisT> void abandon() { abandon(AnalysisT::ID()); }
+
+  /// Mark an analysis as abandoned using its ID.
+  ///
+  /// An abandoned analysis is not preserved, even if it is nominally covered
+  /// by some other set or was previously explicitly marked as preserved.
+  ///
+  /// Note that you can only abandon a specific analysis, not a *set* of
+  /// analyses.
+  void abandon(AnalysisKey *ID) {
+    PreservedIDs.erase(ID);
+    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;
     }
-    for (auto ID : PreservedAnalysisIDs)
-      if (!Arg.PreservedAnalysisIDs.count(ID))
-        PreservedAnalysisIDs.erase(ID);
+    // The intersection requires the *union* of the explicitly not-preserved
+    // IDs and the *intersection* of the preserved IDs.
+    for (auto ID : Arg.NotPreservedAnalysisIDs) {
+      PreservedIDs.erase(ID);
+      NotPreservedAnalysisIDs.insert(ID);
+    }
+    for (auto ID : PreservedIDs)
+      if (!Arg.PreservedIDs.count(ID))
+        PreservedIDs.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;
     }
-    for (auto ID : PreservedAnalysisIDs)
-      if (!Arg.PreservedAnalysisIDs.count(ID))
-        PreservedAnalysisIDs.erase(ID);
+    // The intersection requires the *union* of the explicitly not-preserved
+    // IDs and the *intersection* of the preserved IDs.
+    for (auto ID : Arg.NotPreservedAnalysisIDs) {
+      PreservedIDs.erase(ID);
+      NotPreservedAnalysisIDs.insert(ID);
+    }
+    for (auto ID : PreservedIDs)
+      if (!Arg.PreservedIDs.count(ID))
+        PreservedIDs.erase(ID);
+  }
+
+  /// A checker object that makes it easy to query for whether an analysis or
+  /// some set covering it is preserved.
+  class PreservedAnalysisChecker {
+    friend class PreservedAnalyses;
+
+    const PreservedAnalyses &PA;
+    AnalysisKey *const ID;
+    const bool IsAbandoned;
+
+    /// A PreservedAnalysisChecker is tied to a particular Analysis because
+    /// `preserved()` and `preservedSet()` both return false if the Analysis
+    /// was abandoned.
+    PreservedAnalysisChecker(const PreservedAnalyses &PA, AnalysisKey *ID)
+        : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(ID)) {}
+
+  public:
+    /// Returns true if the checker's analysis was not abandoned and the
+    /// analysis is either is explicitly preserved or all analyses are
+    /// preserved.
+    bool preserved() {
+      return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) ||
+                              PA.PreservedIDs.count(ID));
     }
 
-  /// \brief Query whether a pass is marked as preserved by this set.
-  template <typename PassT> bool preserved() const {
-    return preserved(PassT::ID());
+    /// Returns true if the checker's analysis was not abandoned and either the
+    /// provided set type is either explicitly preserved or all analyses are
+    /// preserved.
+    template <typename AnalysisSetT> bool preservedSet() {
+      AnalysisSetKey *SetID = AnalysisSetT::ID();
+      return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) ||
+                              PA.PreservedIDs.count(SetID));
     }
+  };
 
-  /// \brief 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);
+  /// Build a checker for this `PreservedAnalyses` and the specified analysis
+  /// type.
+  ///
+  /// You can use the returned object to query whether an analysis was
+  /// preserved. See the example in the comment on `PreservedAnalysis`.
+  template <typename AnalysisT> PreservedAnalysisChecker getChecker() const {
+    return PreservedAnalysisChecker(*this, AnalysisT::ID());
   }
 
-  /// \brief Query whether all of the analyses in the set are preserved.
-  bool preserved(const PreservedAnalyses& Arg) {
-    if (Arg.areAllPreserved())
-      return areAllPreserved();
-    for (auto ID : Arg.PreservedAnalysisIDs)
-      if (!preserved(ID))
-        return false;
-    return true;
+  /// Build a checker for this `PreservedAnalyses` and the specified analysis
+  /// ID.
+  ///
+  /// You can use the returned object to query whether an analysis was
+  /// preserved. See the example in the comment on `PreservedAnalysis`.
+  PreservedAnalysisChecker getChecker(AnalysisKey *ID) const {
+    return PreservedAnalysisChecker(*this, ID);
   }
 
-  /// \brief Test whether all passes are preserved.
+  /// Test whether all analyses are preserved (and none are abandoned).
   ///
-  /// This is used primarily to optimize for the case of no changes which will
-  /// common in many scenarios.
+  /// This lets analyses optimize for the common case where a transformation
+  /// made no changes to the IR.
   bool areAllPreserved() const {
-    return PreservedAnalysisIDs.count(&AllAnalysesKey);
+    return NotPreservedAnalysisIDs.empty() &&
+           PreservedIDs.count(&AllAnalysesKey);
+  }
+
+  /// Directly test whether a set of analyses is preserved.
+  ///
+  /// This is only true when no analyses have been explicitly abandoned.
+  template <typename AnalysisSetT> bool allAnalysesInSetPreserved() const {
+    return allAnalysesInSetPreserved(AnalysisSetT::ID());
+  }
+
+  /// Directly test whether a set of analyses is preserved.
+  ///
+  /// This is only true when no analyses have been explicitly abandoned.
+  bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const {
+    return NotPreservedAnalysisIDs.empty() &&
+           (PreservedIDs.count(&AllAnalysesKey) || PreservedIDs.count(SetID));
   }
 
 private:
-  // A special key used to indicate all analyses.
-  static AnalysisKey AllAnalysesKey;
+  /// A special key used to indicate all analyses.
+  static AnalysisSetKey AllAnalysesKey;
 
-  SmallPtrSet<AnalysisKey *, 2> PreservedAnalysisIDs;
+  /// The IDs of analyses and analysis sets that are preserved.
+  SmallPtrSet<void *, 2> PreservedIDs;
+
+  /// The IDs of explicitly not-preserved analyses.
+  ///
+  /// If an analysis in this set is covered by a set in `PreservedIDs`, we
+  /// consider it not-preserved. That is, `NotPreservedAnalysisIDs` always
+  /// "wins" over analysis sets in `PreservedIDs`.
+  ///
+  /// Also, a given ID should never occur both here and in `PreservedIDs`.
+  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.
 ///

 /// invalidation events.
 ///
 /// Note that you must provide an explicit instantiation declaration and
 /// definition for this template in order to get the correct behavior on
 /// Windows. Otherwise, the address of SetKey will not be stable.
 template <typename IRUnitT>
 class AllAnalysesOn {
 public:
-  static AnalysisKey *ID() { return &SetKey; }
+  static AnalysisSetKey *ID() { return &SetKey; }
 
 private:
-  static AnalysisKey SetKey;
+  static AnalysisSetKey SetKey;
 };
 
-template <typename IRUnitT> AnalysisKey AllAnalysesOn<IRUnitT>::SetKey;
+template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey;
 
 extern template class AllAnalysesOn<Module>;
 extern template class AllAnalysesOn<Function>;
 
 /// \brief Manages a sequence of passes over units of IR.
 ///
 /// A pass manager contains a sequence of passes to run over units of IR. It is
 /// itself a valid pass over that unit of IR, and when over some given IR will
for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
       // in the new pass manager so it is currently omitted.
       //IR.getContext().yield();
     }
 
     // Invaliadtion was handled after each pass in the above loop for the
     // current unit of IR. 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<IRUnitT>>();
+    PA.preserveSet<AllAnalysesOn<IRUnitT>>();
 
     if (DebugLogging)
       dbgs() << "Finished " << getTypeName<IRUnitT>() << " pass manager run.\n";
 
     return PA;
   }
 
   template <typename PassT> void addPass(PassT Pass) {
public:
     /// trigger the corresponding result's \c invalidate method to be called.
     /// Subsequent calls will use a cache of the results of that initial call.
     /// It is an error to form cyclic dependencies between analysis results.
     ///
     /// This returns true if the given analysis pass's result is invalid and
     /// any dependecies on it will become invalid as a result.
     template <typename PassT>
     bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
-      AnalysisKey *ID = PassT::ID();
+      typedef detail::AnalysisResultModel<IRUnitT, PassT,
+                                          typename PassT::Result,
+                                          PreservedAnalyses, Invalidator>
+          ResultModelT;
+      return invalidateImpl<ResultModelT>(PassT::ID(), IR, PA);
+    }
 
+    /// A type-erased variant of the above invalidate method with the same core
+    /// API other than passing an analysis ID rather than an analysis type
+    /// parameter.
+    ///
+    /// This is sadly less efficient than the above routine, which leverages
+    /// the type parameter to avoid the type erasure overhead.
+    bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) {
+      return invalidateImpl<>(ID, IR, PA);
+    }
+
+  private:
+    friend class AnalysisManager;
+
+    template <typename ResultT = ResultConceptT>
+    bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR,
+                        const PreservedAnalyses &PA) {
       // If we've already visited this pass, return true if it was invalidated
       // and false otherwise.
       auto IMapI = IsResultInvalidated.find(ID);
       if (IMapI != IsResultInvalidated.end())
         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);
+      auto &Result = static_cast<ResultT &>(*RI->second->second);
 
       // Insert into the map whether the result should be invalidated and
       // return that. Note that we cannot re-use IMapI and must do a fresh
       // insert here as calling the invalidate routine could (recursively)
       // insert things into the map making any iterator or reference invalid.
       bool Inserted;
-      std::tie(IMapI, Inserted) = IsResultInvalidated.insert(
-          {ID, ResultModel.invalidate(IR, PA, *this)});
+      std::tie(IMapI, Inserted) =
+          IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)});
       (void)Inserted;
       assert(Inserted && "Should not have already inserted this ID, likely "
                          "indicates a dependency cycle!");
       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;
   };
 
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're done if all analyses on this IR unit are preserved.
+    if (PA.allAnalysesInSetPreserved<AllAnalysesOn<IRUnitT>>())
       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 deferred 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
+      // data structure 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 SmallDenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2> &
+    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.
+    SmallDenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2>
+        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...> &,
for (Function &F : M) {
       // analyses will eventually occur when the module pass completes.
       PA.intersect(std::move(PassPA));
     }
 
     // By definition we preserve the proxy. We also preserve all analyses on
     // Function units. This precludes *any* invalidation of function analyses
     // by the proxy, but that's OK because we've taken care to invalidate
     // analyses in the function analysis manager incrementally above.
-    PA.preserve<AllAnalysesOn<Function>>();
+    PA.preserveSet<AllAnalysesOn<Function>>();
     PA.preserve<FunctionAnalysisManagerModuleProxy>();
     return PA;
   }
 
 private:
   FunctionPassT Pass;
 };
 

llvm/trunk/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());
+    auto PAC = PA.template getChecker<PassT>();
+    return !PAC.preserved() &&
+           !PAC.template preservedSet<AllAnalysesOn<IRUnitT>>();
   }
 
   ResultT Result;
 };
 
 /// \brief Specialization of \c AnalysisResultModel which delegates invalidate
 /// handling to \c ResultT.
 template <typename IRUnitT, typename PassT, typename ResultT,

llvm/trunk/lib/Analysis/CGSCCPassManager.cpp

for (auto &Pass : Passes) {
     // 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>>();
+  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
 
   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 it's unavailable we conservatively clear the
-  // entire SCC layer as well rather than trying to do invaliadtion ourselves.
-  if (!PA.preserved<CGSCCAnalysisManagerModuleProxy>() ||
+  // entire SCC layer as well rather than trying to do invalidation ourselves.
+  auto PAC = PA.getChecker<CGSCCAnalysisManagerModuleProxy>();
+  if (!(PAC.preserved() || PAC.preservedSet<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. This isn't strictly necessary because we cheat
     // above, but is still useful.
     return true;
   }
 
+  // Directly check if the relevant set is preserved so we can short circuit
+  // invalidating SCCs below.
+  bool AreSCCAnalysesPreserved =
+      PA.allAnalysesInSetPreserved<AllAnalysesOn<LazyCallGraph::SCC>>();
+
   // Ok, we have a graph, so we can propagate the invalidation down into it.
   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 adjusted based on
+      // module-level analysis invalidation triggering deferred invalidation
+      // 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. 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);
+    }
 
   // Return false to indicate that this result is still a valid proxy.
   return false;
 }
 
 template <>
 CGSCCAnalysisManagerModuleProxy::Result
 CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM) {

llvm/trunk/lib/Analysis/LoopPassManager.cpp

 template <>
 bool LoopAnalysisManagerFunctionProxy::Result::invalidate(
     Function &F, const PreservedAnalyses &PA,
     FunctionAnalysisManager::Invalidator &Inv) {
   // If this proxy isn't marked as preserved, the set of Function objects in
   // the module may have changed. We therefore can't call
   // InnerAM->invalidate(), because any pointers to Functions it has may be
   // stale.
-  if (!PA.preserved(LoopAnalysisManagerFunctionProxy::ID()))
+  auto PAC = PA.getChecker<LoopAnalysisManagerFunctionProxy>();
+  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Loop>>())
     InnerAM->clear();
 
   // FIXME: Proper suppor for invalidation isn't yet implemented for the LPM.
 
   // Return false to indicate that this result is still a valid proxy.
   return false;
 }
 }

llvm/trunk/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())) {
+  auto PAC = PA.getChecker<FunctionAnalysisManagerModuleProxy>();
+  if (!PAC.preserved() && !PAC.preservedSet<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.allAnalysesInSetPreserved<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;
+AnalysisSetKey PreservedAnalyses::AllAnalysesKey;

llvm/trunk/unittests/Analysis/CGSCCPassManagerTest.cpp

TEST_F(CGSCCPassManagerTest,
   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
   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 invalidate 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) {
+      auto PAC = PA.getChecker<TestIndirectSCCAnalysis>();
+      return !(PAC.preserved() ||
+               PAC.preservedSet<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 caches 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) {
+      auto PAC = PA.getChecker<TestDoublyIndirectSCCAnalysis>();
+      return !(PAC.preserved() ||
+               PAC.preservedSet<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) {
+      auto PAC = PA.getChecker<TestIndirectFunctionAnalysis>();
+      return !(PAC.preserved() ||
+               PAC.preservedSet<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);
+}
 }

llvm/trunk/unittests/IR/PassManagerTest.cpp

PassManagerTest()
                            "define void @g() {\n"
                            "  ret void\n"
                            "}\n"
                            "define void @h() {\n"
                            "  ret void\n"
                            "}\n")) {}
 };
 
-TEST_F(PassManagerTest, BasicPreservedAnalyses) {
+TEST(PreservedAnalysesTest, Basic) {
   PreservedAnalyses PA1 = PreservedAnalyses();
-  EXPECT_FALSE(PA1.preserved<TestFunctionAnalysis>());
-  EXPECT_FALSE(PA1.preserved<TestModuleAnalysis>());
-  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>());
+  {
+    auto PAC = PA1.getChecker<TestFunctionAnalysis>();
+    EXPECT_FALSE(PAC.preserved());
+    EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Function>>());
+  }
+  {
+    auto PAC = PA1.getChecker<TestModuleAnalysis>();
+    EXPECT_FALSE(PAC.preserved());
+    EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Module>>());
+  }
+  auto PA2 = PreservedAnalyses::none();
+  {
+    auto PAC = PA2.getChecker<TestFunctionAnalysis>();
+    EXPECT_FALSE(PAC.preserved());
+    EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Function>>());
+  }
+  auto PA3 = PreservedAnalyses::all();
+  {
+    auto PAC = PA3.getChecker<TestFunctionAnalysis>();
+    EXPECT_TRUE(PAC.preserved());
+    EXPECT_TRUE(PAC.preservedSet<AllAnalysesOn<Function>>());
+  }
   PreservedAnalyses PA4 = PA1;
-  EXPECT_FALSE(PA4.preserved<TestFunctionAnalysis>());
-  EXPECT_FALSE(PA4.preserved<TestModuleAnalysis>());
+  {
+    auto PAC = PA4.getChecker<TestFunctionAnalysis>();
+    EXPECT_FALSE(PAC.preserved());
+    EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Function>>());
+  }
   PA4 = PA3;
-  EXPECT_TRUE(PA4.preserved<TestFunctionAnalysis>());
-  EXPECT_TRUE(PA4.preserved<TestModuleAnalysis>());
+  {
+    auto PAC = PA4.getChecker<TestFunctionAnalysis>();
+    EXPECT_TRUE(PAC.preserved());
+    EXPECT_TRUE(PAC.preservedSet<AllAnalysesOn<Function>>());
+  }
   PA4 = std::move(PA2);
-  EXPECT_FALSE(PA4.preserved<TestFunctionAnalysis>());
-  EXPECT_FALSE(PA4.preserved<TestModuleAnalysis>());
-  PA4.preserve<TestFunctionAnalysis>();
-  EXPECT_TRUE(PA4.preserved<TestFunctionAnalysis>());
-  EXPECT_FALSE(PA4.preserved<TestModuleAnalysis>());
-  PA1.preserve<TestModuleAnalysis>();
-  EXPECT_FALSE(PA1.preserved<TestFunctionAnalysis>());
-  EXPECT_TRUE(PA1.preserved<TestModuleAnalysis>());
+  {
+    auto PAC = PA4.getChecker<TestFunctionAnalysis>();
+    EXPECT_FALSE(PAC.preserved());
+    EXPECT_FALSE(PAC.preservedSet<AllAnalysesOn<Function>>());
+  }
+}
+
+TEST(PreservedAnalysesTest, Preserve) {
+  auto PA = PreservedAnalyses::none();
+  PA.preserve<TestFunctionAnalysis>();
+  EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(PA.getChecker<TestModuleAnalysis>().preserved());
+  PA.preserve<TestModuleAnalysis>();
+  EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>().preserved());
+
+  // Redundant calls are fine.
+  PA.preserve<TestFunctionAnalysis>();
+  EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>().preserved());
+}
+
+TEST(PreservedAnalysesTest, PreserveSets) {
+  auto PA = PreservedAnalyses::none();
+  PA.preserveSet<AllAnalysesOn<Function>>();
+  EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>()
+                  .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(PA.getChecker<TestModuleAnalysis>()
+                   .preservedSet<AllAnalysesOn<Module>>());
+  PA.preserveSet<AllAnalysesOn<Module>>();
+  EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>()
+                  .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+
+  // Mixing is fine.
+  PA.preserve<TestFunctionAnalysis>();
+  EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>()
+                  .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+
+  // Redundant calls are fine.
+  PA.preserveSet<AllAnalysesOn<Module>>();
+  EXPECT_TRUE(PA.getChecker<TestFunctionAnalysis>()
+                  .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_TRUE(PA.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+}
+
+TEST(PreservedAnalysisTest, Intersect) {
+  // Setup the initial sets.
+  auto PA1 = PreservedAnalyses::none();
   PA1.preserve<TestFunctionAnalysis>();
-  EXPECT_TRUE(PA1.preserved<TestFunctionAnalysis>());
-  EXPECT_TRUE(PA1.preserved<TestModuleAnalysis>());
-  PA1.intersect(PA4);
-  EXPECT_TRUE(PA1.preserved<TestFunctionAnalysis>());
-  EXPECT_FALSE(PA1.preserved<TestModuleAnalysis>());
+  PA1.preserveSet<AllAnalysesOn<Module>>();
+  auto PA2 = PreservedAnalyses::none();
+  PA2.preserve<TestFunctionAnalysis>();
+  PA2.preserveSet<AllAnalysesOn<Function>>();
+  PA2.preserve<TestModuleAnalysis>();
+  PA2.preserveSet<AllAnalysesOn<Module>>();
+  auto PA3 = PreservedAnalyses::none();
+  PA3.preserve<TestModuleAnalysis>();
+  PA3.preserveSet<AllAnalysesOn<Function>>();
+
+  // Self intersection is a no-op.
+  auto Intersected = PA1;
+  Intersected.intersect(PA1);
+  EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+
+  // Intersecting with all is a no-op.
+  Intersected.intersect(PreservedAnalyses::all());
+  EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+
+  // Intersecting a narrow set with a more broad set is the narrow set.
+  Intersected.intersect(PA2);
+  EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+
+  // Intersecting a broad set with a more narrow set is the narrow set.
+  Intersected = PA2;
+  Intersected.intersect(PA1);
+  EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+
+  // Intersecting with empty clears.
+  Intersected.intersect(PreservedAnalyses::none());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>()
+                   .preservedSet<AllAnalysesOn<Module>>());
+
+  // Intersecting non-overlapping clears.
+  Intersected = PA1;
+  Intersected.intersect(PA3);
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>()
+                   .preservedSet<AllAnalysesOn<Module>>());
+
+  // Intersecting with moves works in when there is storage on both sides.
+  Intersected = PA1;
+  auto Tmp = PA2;
+  Intersected.intersect(std::move(Tmp));
+  EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+
+  // Intersecting with move works for incoming all and existing all.
+  auto Tmp2 = PreservedAnalyses::all();
+  Intersected.intersect(std::move(Tmp2));
+  EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+  Intersected = PreservedAnalyses::all();
+  auto Tmp3 = PA1;
+  Intersected.intersect(std::move(Tmp3));
+  EXPECT_TRUE(Intersected.getChecker<TestFunctionAnalysis>().preserved());
+  EXPECT_FALSE(Intersected.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(Intersected.getChecker<TestModuleAnalysis>().preserved());
+  EXPECT_TRUE(Intersected.getChecker<TestModuleAnalysis>()
+                  .preservedSet<AllAnalysesOn<Module>>());
+}
+
+TEST(PreservedAnalysisTest, Abandon) {
+  auto PA = PreservedAnalyses::none();
+
+  // We can abandon things after they are preserved.
+  PA.preserve<TestFunctionAnalysis>();
+  PA.abandon<TestFunctionAnalysis>();
+  EXPECT_FALSE(PA.getChecker<TestFunctionAnalysis>().preserved());
+
+  // Repeated is fine, and abandoning if they were never preserved is fine.
+  PA.abandon<TestFunctionAnalysis>();
+  EXPECT_FALSE(PA.getChecker<TestFunctionAnalysis>().preserved());
+  PA.abandon<TestModuleAnalysis>();
+  EXPECT_FALSE(PA.getChecker<TestModuleAnalysis>().preserved());
+
+  // Even if the sets are preserved, the abandoned analyses' checker won't
+  // return true for those sets.
+  PA.preserveSet<AllAnalysesOn<Function>>();
+  PA.preserveSet<AllAnalysesOn<Module>>();
+  EXPECT_FALSE(PA.getChecker<TestFunctionAnalysis>()
+                   .preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_FALSE(PA.getChecker<TestModuleAnalysis>()
+                   .preservedSet<AllAnalysesOn<Module>>());
+
+  // But an arbitrary (opaque) analysis will still observe the sets as
+  // preserved. This also checks that we can use an explicit ID rather than
+  // a type.
+  AnalysisKey FakeKey, *FakeID = &FakeKey;
+  EXPECT_TRUE(PA.getChecker(FakeID).preservedSet<AllAnalysesOn<Function>>());
+  EXPECT_TRUE(PA.getChecker(FakeID).preservedSet<AllAnalysesOn<Module>>());
 }
 
 TEST_F(PassManagerTest, Basic) {
   FunctionAnalysisManager FAM(/*DebugLogging*/ true);
   int FunctionAnalysisRuns = 0;
   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 
   ModuleAnalysisManager MAM(/*DebugLogging*/ true);

 }
 
 /// 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>() ||
+      auto PAC = PA.getChecker<TestIndirectFunctionAnalysis>();
+      return !(PAC.preserved() ||
+               PAC.preservedSet<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) {
+      auto PAC = PA.getChecker<TestDoublyIndirectFunctionAnalysis>();
+      return !(PAC.preserved() ||
+               PAC.preservedSet<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);
 }
 }