[PM] WIP: Introduce basic update capabilities to the new PM's CGSCC pass manager, including both plumbing and logic to handle function pass updates.

[chandlerc]

Summary

There are three fundamentally tied changes here:

1. Plumbing *some* mechanism for updating the CGSCC pass manager as the CG changes while passes are running.
2. Changing the CGSCC pass manager infrastructure to have support for the underlying graph to mutate mid-pass run.
3. Actually updating the CG after function passes run.

I can separate them if necessary, but I think its really useful to have
them together as the needs of #3 drove #2, and that in turn drove #1.

The plumbing technique is to extend the "run" method signature with
extra arguments. We provide the call graph that intrinsically is
available as it is the basis of the pass manager's IR units, and an
output parameter that records the results of updating the call graph
during an SCC passes's run. Note that "...UpdateResult" isn't a *great*
name here... suggestions very welcome.

I tried a pretty frustrating number of different data structures and such
for the innards of the update result. Every other one failed for one
reason or another. Sometimes I just couldn't keep the layers of
complexity right in my head. The thing that really worked was to just
directly provide access to the underlying structures used to walk the
call graph so that their updates could be informed by the *particular*
nature of the change to the graph.

The technique for how to make the pass management infrastructure cope
with mutating graphs was also something that took a really, really large
number of iterations to get to a place where I was happy. Here are some
of the considerations that drove the design:

• We operate at three levels within the infrastructure: RefSCC, SCC, and Node. In each case, we are working bottom up and so we want to continue to iterate on the "lowest" node as the graph changes. Look at how we iterate over nodes in an SCC running function passes as those function passes mutate the CG. We continue to iterate on the "lowest" SCC, which is the one that continues to contain the function just processed.

• The call graph structure re-uses SCCs (and RefSCCs) during mutation events for the *highest* entry in the resulting new subgraph, not the lowest. This means that it is necessary to continually update the current SCC or RefSCC as it shifts. This is really surprising and subtle, and took a long time for me to work out. I actually tried changing the call graph to provide the opposite behavior, and it breaks *EVERYTHING*. The graph update algorithms are really deeply tied to this particualr pattern.

• When SCCs or RefSCCs are split apart and refined and we continually re-pin our processing to the bottom one in the subgraph, we need to enqueue the newly formed SCCs and RefSCCs for subsequent processing. Queuing them presents a few challenges:
  1. SCCs and RefSCCs use wildly different iteration strategies at a high level. We end up needing to converge them on worklist approaches that can be extended in order to be able to handle the mutations.
  2. The order of the enqueuing need to remain bottom-up post-order so that we don't get surprising order of visitation for things like the inliner.
  3. We need the worklists to have set semantics so we don't duplicate things endlessly. We don't need a *persistent* set though because we always keep processing the bottom node!!!! This is super, super surprising to me and took a long time to convince myself this is correct, but I'm pretty sure it is... Once we sink down to the bottom node, we can't re-split out the same node in any way, and the postorder of the current queue is fixed and unchanging.
  4. We need to make sure that the "current" SCC or RefSCC actually gets enqueued here such that we re-visit it because we continue processing a *new*, *bottom* SCC/RefSCC.

• We also need the ability to *skip* SCCs and RefSCCs that get merged into a larger component. We even need the ability to skip *nodes* from an SCC that are no longer part of that SCC.

This led to the design you see in the patch which uses SetVector-based
worklists. The RefSCC worklist is always empty until an update occurs
and is just used to handle those RefSCCs created by updates as the
others don't even exist yet and are formed on-demand during the
bottom-up walk. The SCC worklist is pre-populated from the RefSCC, and
we push new SCCs onto it and blacklist existing SCCs on it to get the
desired processing.

We then *directly* update these when updating the call graph as I was
never able to find a satisfactory abstraction around the update
strategy.

Finally, we need to compute the updates for function passes. This is
mostly used as an initial customer of all the update mechanisms to drive
their design to at least cover some real set of use cases. There are
a bunch of interesting things that came out of doing this:

• It is really nice to do this a function at a time because that function is likely hot in the cache. This means we want even the function pass adaptor to support online updates to the call graph!

• To update the call graph after arbitrary function pass mutations is quite hard. We have to build a fairly comprehensive set of data structures and then process them. Fortunately, some of this code is related to the code for building the cal graph in the first place. Unfortunately, very little of it makes any sense to share because the nature of what we're doing is so very different. I've factored out the one part that made sense at least.

• We need to transfer these updates into the various structures for the CGSCC pass manager. Once those were more sanely worked out, this became relatively easier. But some of those needs necessitated changes to the LazyCallGraph interface to make it significantly easier to extract the changed SCCs from an update operation.

• We also need to update the CGSCC analysis manager as the shape of the graph changes. When an SCC is merged away we need to clear analyses associated with it from the analysis manager which we didn't have support for in the analysis manager infrsatructure. New SCCs are easy! But then we have the case that the original SCC has its shape changed but remains in the call graph. There we need to *invalidate* the analyses associated with it.

• We also need to invalidate analyses after we *finish* processing an SCC. But the analyses we need to invalidate here are *only those for the newly updated SCC*!!! Because we only continue processing the bottom SCC, if we split SCCs apart the original one gets invalidated once when its shape changes and is not processed farther so its analyses will be correct. It is the bottom SCC which continues being processed and needs to have the "normal" invalidation done based on the preserved analyses set.

All of this is mostly background and context for the changes here. This
is still very much a WIP! I know there are bugs here (tests fail) and
I still need to actively test the core functionality here. I'll be
working on that next. Don't stress too much if things look like bugs or
something looks like it has a basic functionality error. Mostly looking
for feedback on the design, layering, and approach. I'll update ASAP
with fixes and tests.

Depends on http://reviews.llvm.org/D21462

[silvas]

Some initial comments.

You've described a lot of implementation details (and implementation), but haven't described the final intended visitation behavior you are trying to implement (or why). For starters, what's wrong with the old PM CGSCC visitation order that requires doing something fundamentally different in the new PM?

The general idea is clearly to maintain a bottom-up visitation behavior, but since this patch doesn't implement edge addition (which represents devirtualization and so is pretty important) the intended behavior there is unclear. I've put a very specific question about this inline.

lib/Analysis/CGSCCPassManager.cpp

90 ↗

(On Diff #61073)

What is the plan here? If I'm running cgscc(foo-cgscc-pass,function(gvn),bar-cgscc-pass) and gvn devirtualizes a call which increases the size of the SCC, what do we do after finishing the function pass manager? Do we:

1. start back at the beginning with foo-cgscc-pass running on the now-larger SCC?

or

2. continue on to bar-cgscc-pass running on the now-larger SCC?

or

3. something else?

[silvas]

Adding subscribers from the recent "Intended behavior of CGSCC pass manager." thread.

[chandlerc]

Rebase and fix a fundamental bug in the callgraph update due to incorrectly
tracking edges demoted to references. Also clean up the patch itself to avoid
some weird diff churn that was present in the previous patch (sorry about
that).

Responses to questions and more comprehensive testing still coming...

[davidxl]

Chandler, thanks for the tremendous effort for trying to make this work. At this moment, I only have very high level comments, so please bear with me.

Can we have a design document describing the underlying algorithm with formal proof (traversing with mutation)? Given the level of complexity involved and the fact there is no prior literature we can refer to, it is important we get it right.

Besides it is also more important to understand what problem the added complexity is trying to solve, why those problems are important to be solved (evidence of missing opportunities in real apps), and why they can not be solved in other ways? The same questions have been raised in Sean's email thread, and there are some interesting discussions there, so may be you can also chime in there?

As far as I can tell, for the new PM transition, the consensus is to make the transition NFC initially, which will greatly lower the bar for the new PM to become the default. If your plan is to make new PM transition depending on this update support in CGSCC pass to be ready, we need to understand why.

thanks,

David

[sanjoy]

lib/Analysis/CGSCCPassManager.cpp

170 ↗

(On Diff #61741)

Doesn't this also hold if the target SCC is not this SCC?

[chandlerc]

Digging into some of these comments, will get David's in the next email...

In D21464#460784, @silvas wrote:

Some initial comments.

You've described a lot of implementation details (and implementation), but haven't described the final intended visitation behavior you are trying to implement (or why). For starters, what's wrong with the old PM CGSCC visitation order that requires doing something fundamentally different in the new PM?

I'll post an update to the patch that adds a much more detailed comment to the header to try and describe what this is trying to achieve at a high level, etc. It includes some of the why, but it doesn't going into very specific details. I'm happy to do so here and add the details you or others find sufficient relevant and not too brittle to go there.

To summarize what is wrong with the old visit order: it misses specific optimization opportunities, and makes it harder to reason about the call graph updates in a principled way. The latter becomes more important when there might be cached analyses attached to the call graph nodes. Consider if we wanted to lift some of the things in FunctionAttrs into an *analysis* over an SCC rather than an attribute. Now it is essential that update to the graph structure invalidate the right set of analyses.

As an example of the kind of missed optimizations, I'm going to add a test case where we successfully deduce readnone with the new pass manager but can't (no matter how many iterations we make) deduce it with the old one. This is because we don't refine the SCC graph structure, and do principled visitation to that graph structure. The examples in the test case are somewhat contrived in order to make good test cases, but they hopefully represent the general pattern that I'm worried about here: we are using the set of functions in the SCC to reason about it as an SCC but not actually updating that set of functions when the code changes.

The general idea is clearly to maintain a bottom-up visitation behavior, but since this patch doesn't implement edge addition (which represents devirtualization and so is pretty important) the intended behavior there is unclear.

So, this *does* implement ref -> call promotion which is what I would expect devirtualization to look like in all cases. See below for details on your question.

The other case is for "out-of-thin-air" call (or ref) insertion such as instrumentation passes might do. Currently this isn't supported but could be added in the future.

lib/Analysis/CGSCCPassManager.cpp

90 ↗

(On Diff #61741)

(in case reading this against the current patch, this originally was attached to the FIXME regarding handling adding new calls)

As i somewhat alluded to above, what you describe should be handled by a ref edge turning into a call edge, and the update mechanism should be able to handle that well.

I've added a test case that exercises this with GVN and function-attrs. There is currently a case missed in the new pass manager because we don't have the up-to-four iteration whenever an indirect call turns into a direct call heuristic that the old pass manager has. I'm happy to add that, but I'd like to add it in a follow-up patch. I've marked where in the test case this is missed, and I've demonstrated that in theory this update mechanism is sufficient to handle it by explicitly running function-attrs again and it correctly catches the refinement.

The direct answer to your question is #2: it continues running on the now-larger SCC, detects that we switch from one SCC to another at some point, and re-runs on that SCC to make sure that the refined graph is observed.

170 ↗

(On Diff #61741)

Yes, and inside the implementation of switchInternalEdgeToRef, it early exits with an empty range when we hit that scenario.

I can lift that distinction up into this code if you think that would be helpful, the somewhat arbitrary split was that these methods are on a RefSCC, and so it is the RefSCC-easy case that callers have to handle.

[chandlerc]

In D21464#466098, @davidxl wrote:

Chandler, thanks for the tremendous effort for trying to make this work. At this moment, I only have very high level comments, so please bear with me.

Can we have a design document describing the underlying algorithm with formal proof (traversing with mutation)? Given the level of complexity involved and the fact there is no prior literature we can refer to, it is important we get it right.

I've added an overview to the top of the file that I hope answers a lot of the high level questions.

I don't have a formal proof of this, nor do I really know what you would want to prove here. What's the concern? I am working on building up a set of test cases that I think exercise the kinds of updates. I've not finished with that yet, but so far it seems to be hitting lots of the different aspects of this code.

Besides it is also more important to understand what problem the added complexity is trying to solve, why those problems are important to be solved (evidence of missing opportunities in real apps), and why they can not be solved in other ways?

See my response to Sean and my comments in the updated patch (coming shortly) for some of the details here.

I view this much more about getting the call graph management into a principled state with a path that supports the different goals. The new pass manager's requirement of *identity* for things to support analysis caching was a key element that drove the development of the LCG in the beginning. Without that kind of identity, it becomes extremely hard to reason about a caching approach to analyses. I can't claim its impossible to get something to work, but I tried and was unable to see a clear and clean path that made sense to me, so I worked on building up the infrastructure necessary to have identity.

Once you have identity, you need to be very careful with updates because it makes it easy to transform a "benign" relaxation of the model (the old PM's approach of folding more nodes into the current SCC) into a correctness bug. As a consequence I've tried to take a very principled approach to the call graph update where we can verify and check that the graph structure has a particular shape and structure.

Ultimately, I think this is the right way to design the call graph portion of the pass manager because I think other designs will inevitably run up against the limitations that their relaxed model imposes. In fact, I'd like to generalize and make more principled even the idea of the "reference graph" because I think it hasn't gone far enough yet, but that's for a future iteration.

The same questions have been raised in Sean's email thread, and there are some interesting discussions there, so may be you can also chime in there?

That email thread happened when I didn't have time to read it as it went, and after skimming it I was unable to really understand what open questions there were.

This *has* actually been discussed before, if you look at the discussions that led to the LazyCallGraph design. I don't know that we have a complete record of the discussion, but I've tried to capture the sentiment that folks were left with in terms of what direction the design should go in the comment I added to the top of the file.

None of that is to say that we shouldn't revisit the design decisions if they are wrong of course! I just don't want to give the impression that there was *no* discussion about this. We should still try to figure out if there is a problem with this approach or a better approach that we should take.

As far as I can tell, for the new PM transition, the consensus is to make the transition NFC initially, which will greatly lower the bar for the new PM to become the default. If your plan is to make new PM transition depending on this update support in CGSCC pass to be ready, we need to understand why.

I don't actually agree with this. This has come up several times on several different threads with myself, Hal, Philip and numerous others.

I think it would be *nice* if we could make the transition NFC, but I personally do not believe that is reasonable given the degree of difference between the designs. To me, it is very fundamental that when you have a caching analysis layer that understands the SCC organizational unit of IR, you need a different strategy for handling updates and iteration. Trying to force things to look exactly the same will, IMO, cause the design of the new pass manager to be worse.

That said, we do have to have a way to migrate. My plan has been to simply make the new approach superior in terms of benchmark numbers, and at least not a significant regression in terms of compile time. Given the power of a more call graph aware refinement-driven iteration order, and the compile time savings of caching analysis, I think both of these will be reasonably attainable. However, if we try, and they prove very difficult, I think we will still be able to layer a constraint on top of the current design that more precisely mimics the old behavior in order to ease migration. I don't think it will come to this, and I also think that if it does, having what we think is the principled design (but which needs more work to address regressions) underneath will ensure that the compatibility mode sits cleanly on top and doesn't twist the core in an unfortunate direction.

[chandlerc]

Major update that includes several fixes to correctly respect the call graph
updates as well as the first round of test cases that exercise the update
logic. 'cgscc-iterate-function-mutation.ll' is perhaps especially interesting
because it demonstrates a fundamental property that the old pass manager cannot
handle in its current form and that the new pass manager handles cleanly.

This also adds a lot of asserts and debug logging that helped me debug and fix
many issues.

Still working on more test cases, should be able to move this out of 'WIP'
status really soon though.

[silvas]

lib/Analysis/CGSCCPassManager.cpp

90 ↗

(On Diff #61741)

As i somewhat alluded to above, what you describe should be handled by a ref edge turning into a call edge, and the update mechanism should be able to handle that well.

Please add test cases exhibiting this.

The direct answer to your question is #2: it continues running on the now-larger SCC, detects that we switch from one SCC to another at some point, and re-runs on that SCC to make sure that the refined graph is observed.

Okay, please add a test case for that. Also add a test case demonstrating that we don't go quadratic on a graph like http://reviews.llvm.org/F2110388

digraph "foo bar" {
  rankdir=LR
  A -> B; B -> A [style=dashed,label="ref"];
  B -> C; C -> B [style=dashed,label="ref"];
  C -> D; D -> C [style=dashed,label="ref"];
  D -> E; E -> D [style=dashed,label="ref"];
}

where function passes manage to devirtualize all the ref edges.

[sanjoy]

include/llvm/Analysis/CGSCCPassManager.h

77 ↗

(On Diff #62157)

Can you clarify here what happens when there isn't a well defined "bottom"? I.e.

A -> B -> C -> A
A -> C

becomes

A -> B
A -> C

[chandlerc]

lib/Analysis/CGSCCPassManager.cpp

327 ↗

(On Diff #62157)

As i somewhat alluded to above, what you describe should be handled by a ref edge turning into a call edge, and the update mechanism should be able to handle that well.

Please add test cases exhibiting this.

Er, the next sentence in what I wrote was:

I've added a test case that exercises this with GVN and function-attrs.

I think the updated patch has this test case in it. It is cgscc-observe-devirt.ll

The direct answer to your question is #2: it continues running on the now-larger SCC, detects that we switch from one SCC to another at some point, and re-runs on that SCC to make sure that the refined graph is observed.

Okay, please add a test case for that.

This is the same thing, and covered by the same test case. I was just trying to make sure I directly answer your question as well...

Also add a test case demonstrating that we don't go quadratic on a graph like http://reviews.llvm.org/F2110388 where function passes manage to devirtualize all the ref edges.

I'm not really sure what you want here... In general it is very hard to have a test case in the regression test suite that demonstrates a lack of quadratic behavior -- it typically requires an unacceptably large test case even when the behavior is linear.

There are also a bunch of things that might "go quadratic" in this case. There are FIXMEs in the code for some of these things that I would like to address, but probably don't belong conflated into this patch...

Based on the example you post, I think I've figured out that you are trying to point out a case where we will run the SCC pass manager over the function E as many times as we successfully devirtualize edges somewhere in the SCC containing E in a way that brings a new node into that SCC. If I've understood this correctly, then I agree, and that's a nice find. I think it is unlikely to be a problem in practice, but it is definitely something we would need fixed to finish deploying this, probably with just a cap to limit things as a very large SCC formed in this way seems unlikely to be a practical concern to optimize heavily. Given that, I'm inclined to make a FIXME or note about this rather than trying to address it within this patch as that seems like it would bottleneck things.

Did I understand correctly? Does that approach make sense?

[chandlerc]

Update to resolve some issues, add more tests, and make the tests actually
exercise more logic and exercise it more effectively.

[chandlerc]

include/llvm/Analysis/CGSCCPassManager.h

77 ↗

(On Diff #62319)

Sanjoy helped me better understand his concern here, and I've added a 'test3_*' collection of functions to cgscc-observe-devirt.ll that model this. The key is that a scalar transform introduces a post-order constraint not previously present, and if we don't visit in order, we will fail to observe the refined context.

In that test case, if we fail to visit these in order, we will fail to deduce readonly for b1, b2, and b3. Before the most recent update, we failed that test. To fix this, we just have to use the *other* effect of switching a ref to a call edge -- the postorder list within the RefSCC may be updated and we need to adjust our visit order to reflect this (as well as revisit the current SCC which may now have refined context for what it calls). I've added this logic (using a worklist that can have the order adjusted which i separated into D21866) and now we correctly handle this case.

Thanks for bringing it up Sanjoy!

[chandlerc]

Add some more test cases (that already worked), asserts (that caught a bug
where we visit things too often), and the necessary plumbing to correctly
filter these extra visits.

At this point, I think the implementation is getting pretty good. I don't have
a lot of significant ideas of what else to test; Sanjoy's example really hit
the large remaining area that needs to be handled correctly.

I'm going to start working on the next layers (the devirt iteration driver and
the inliner).

[silvas]

Some initial comments.

include/llvm/Analysis/CGSCCPassManager.h

169 ↗

(On Diff #62329)

Please add specific documentation about how this CGSCCUpdateResult is used by CGSCC passes to communicate the modifications. One possibility for "documentation" may be to add unit tests covering basic patterns like how to update them when removing a function, how to update them when replacing a function, how to update them when adding edges, etc.

But I would also expect at least some basic comments on each member explaining under what scenarios it needs to be used and how.

388 ↗

(On Diff #62329)

This is error prone passing in both C and CG. For a given C there is only one valid CG and this signature gives the false impression that there are two degrees of freedom here. You already have the relevant back pointers to fetch the CG as needed so just use that.

[chandlerc]

Rebase, clean up the description a bit, and add some much belated comments to the update API.

[chandlerc]

FWIW, I think a lot of the issues here are at least much better understood. I've got a patch out that solves the most pressing of the invalidation problems within the framework of this design. I've got a devirtualization iteration utility posted. I've ported the inliner, and will mail that shortly -- i mostly was trying to test it a bit more heavily before sending it out, but I think that's counter-productive at this point.

There were a couple of specific comments on this patch outstanding that I've tried to address. Sorry for the delay there.

There are still several invalidation problems that need to be fixed. But I've started fixing them, and have the beginnings of patches, but I'm having a lot of trouble testing the fixes effectively. I'd like to do a fairly substantial refactoring of the unit tests, but I'd really rather do that *after* this lands so that I don't have to refactor the unittests twice essentially (all of the APIs will change with this patch).

Hoping this patch is in a state where folks can review again. I know the algorithms are pretty long, and there may even be bugs there that we'll have to fix as more testing lines up, but so far the testing of this particular part of the change seems to be working out fairly well -- I have way more bugs I need to fix in invalidation than in the graph update so far. =D

include/llvm/Analysis/CGSCCPassManager.h

169 ↗

(On Diff #62329)

Yea, I had forgotten to do this for a long time because I kept changing what the members of this were. I never went back and documented them once things settled into a final form. Sorry about that.

388 ↗

(On Diff #62329)

Unfortunately, there aren't a lot of great alternatives.

This replaces an already error prone pattern where the pass would immediately grab the analysis by calling 'getCachedResult' and asserting that it got a non-null pointer back. By passing in a reference to the deeply fundamental analyses I think it makes it more clear to the caller that these analyses have to be provided.

We could package all of these arguments inside a struct (possibly with an up-pointer in the SCC, but possibly with some other struct that bundles them). But I'm not sure that will really be a net improvement. I expect that functions which give this parameter a name at all would want to unpack any such struct immediately.

It is perhaps a bit weird that this API is really designed to optimize for implementor, but in a sense it is. This API gets implemented for each pass, but called in only a very few places.

Still, I'll definitely add some comments here to help make it very clear what the expected relationship is between the arguments.

[sanjoy]

Looks good overall, some minor comments inline. Feel free to push after fixing (or address them post-commit).

include/llvm/Analysis/CGSCCPassManager.h

42 ↗

(On Diff #68945)

It wasn't clear what you meant by "denormalized indirect references".

160 ↗

(On Diff #68945)

s/rammifications/ramifications/

292 ↗

(On Diff #68945)

Why do you do this nested scheme instead of queueing all of CG.postorder_ref_sccs() into RCWorklist? The answer is probably worth a comment.

437 ↗

(On Diff #68945)

Shouldn't this be "across every function in the SCC."?

include/llvm/Analysis/LazyCallGraph.h

585 ↗

(On Diff #68945)

Document what you're returning? Especially your assumption that the first node in the returned range is the SCC containing the source node.

Might be worth it to add a unit test for this new behavior (no need to block this patch on that though).

lib/Analysis/CGSCCPassManager.cpp

47 ↗

(On Diff #68945)

Range for?

86 ↗

(On Diff #68945)

I understand this this is a local utility, but I still think it will be helpful to add one or two lines about what it does (or use a more descriptive verb than "process").

92 ↗

(On Diff #68945)

Not sure if the default for DebugLogging adds any value.

111 ↗

(On Diff #68945)

This confused me for a moment -- how about calling the return value NextC?

145 ↗

(On Diff #68945)

I found these names a little off, I'd have called them PromotedRefTargets and DemotedCallTargets instead, since they're ref targets that were promoted and call targets that were demoted respectively.

199 ↗

(On Diff #68945)

Might be worth adding a Edge::getKind helper to use here.

240 ↗

(On Diff #68945)

In processNewSCCRange you assume that the SCC containing N will be the first one in the post-order, but you don't assume the corresponding fact for RefSCC s here. Why do we have this asymmetry?

244 ↗

(On Diff #68945)

s/Enqueing/Enqueuing/

307 ↗

(On Diff #68945)

I'd s/valid/precise/ here (I can't imagine a real-world analyses that would be _incorrect_ after splitting out SCCs).

328 ↗

(On Diff #68945)

s/Enqueing/Enqueuing/

329 ↗

(On Diff #68945)

Enqueue

[chandlerc]

Thanks so much Sanjoy! I've tried to essentially address all of these (with a couple of exceptions where I'd like further guidance on how to best address them in follow-up commits below).

Landing now, and will be preparing some follow-up patches and the next significant chunk of functionality for review.

include/llvm/Analysis/CGSCCPassManager.h

42 ↗

(On Diff #68945)

Sure, I've spelled this out better in the comment, just let me know if it still isn't sufficietnly clear.

292 ↗

(On Diff #68945)

Commented. For easy discovery, the crux is that CG.postorder_ref_sccs() is lazy, and we want to be as lazy as we can be. The worklist exists for when we discover new RefSCCs during transformations.

include/llvm/Analysis/LazyCallGraph.h

585 ↗

(On Diff #68945)

Gah, thought I had done that. Thanks for spotting it.

Documentation updated, and yea I'll get this covered by a unit test. (It *is* covered by the pass manager tests as well, but a unit test would be really good here.)

lib/Analysis/CGSCCPassManager.cpp

86 ↗

(On Diff #68945)

Indeed, i've already written code that wanted to use it again. I've both tried to give it a better name and improved the comments.

92 ↗

(On Diff #68945)

I don't think it does either. I'd really like to move all of the logging to use DEBUG and the DEBUG_PASS infrastructure. But I didn't want to do that in this change and the code already has the DebugLogging threaded through really pervasively.

111 ↗

(On Diff #68945)

Hmm, but it's not the next C... its the "current" C. Or the component containing N.

Let's keep chatting to see if there is a better name, and I'll fix this up with whatever we come up with.

145 ↗

(On Diff #68945)

Agreed.

240 ↗

(On Diff #68945)

My memory is because of the nature of how we split SCCs vs. how we split RefSCCs. For the former we use the existing postorder sequence to constrain the precise returned order. For the RefSCCs, while the order is deterministic, it isn't predictable in the same way, and so we might have sibling RefSCCs and the node might end up in any particular one.

I think this would be worth fixing so that we can make a symmetric assumption. It may even already happen to be true. But I would want to spend some considerable time re-examining the RefSCC splitting algorithm to ensure this is by design and actually something we can guarantee. And we'd need a bunch of testing for it.

So, maybe this just needs a FIXME or a comment. What do you think? Where would you put them?

[sanjoy]

Replied to comments.

lib/Analysis/CGSCCPassManager.cpp

92 ↗

(On Diff #68945)

I meant passing in false for the default value of DebugLogging. Looks like you explicitly pass in DebugLogging for both the places that call processNewSCCRange so the default isn't needed.

111 ↗

(On Diff #68945)

I was reading this as a "transition function" that returns the new state of the algorithm (so it returns the "next" state).

Passing in LazyCallGraph::SCC *&C and updating C in place is fine too, in which case I'll read the function as "destructively modify these variables to reflect that we have a set of new SCC s".

However, this is not a big deal, and using C is fine here.

240 ↗

(On Diff #68945)

A comment noting that this was intentional when written and not an oversight will be great.

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

 //===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// This header provides classes for managing passes over SCCs of the call
 /// graph. These passes form an important component of LLVM's interprocedural
 /// optimizations. Because they operate on the SCCs of the call graph, and they
-/// traverse the graph in post order, they can effectively do pair-wise
-/// interprocedural optimizations for all call edges in the program. At each
-/// call site edge, the callee has already been optimized as much as is
-/// possible. This in turn allows very accurate analysis of it for IPO.
+/// traverse the graph in post-order, they can effectively do pair-wise
+/// interprocedural optimizations for all call edges in the program while
+/// incrementally refining it and improving the context of these pair-wise
+/// optimizations. At each call site edge, the callee has already been
+/// optimized as much as is possible. This in turn allows very accurate
+/// analysis of it for IPO.
+///
+/// A secondary more general goal is to be able to isolate optimization on
+/// unrelated parts of the IR module. This is useful to ensure our
+/// optimizations are principled and don't miss oportunities where refinement
+/// of one part of the module influence transformations in another part of the
+/// module. But this is also useful if we want to parallelize the optimizations
+/// across common large module graph shapes which tend to be very wide and have
+/// large regions of unrelated cliques.
+///
+/// To satisfy these goals, we use the LazyCallGraph which provides two graphs
+/// nested inside each other (and built lazily from the bottom-up): the call
+/// graph proper, and a reference graph. The reference graph is super set of
+/// the call graph and is a conservative approximation of what could through
+/// scalar or CGSCC transforms *become* the call graph. Using this allows us to
+/// ensure we optimize functions prior to them being introduced into the call
+/// graph by devirtualization or other technique, and thus ensures that
+/// subsequent pair-wise interprocedural optimizations observe the optimized
+/// form of these functions. The (potentially transitive) reference
+/// reachability used by the reference graph is a conservative approximation
+/// that still allows us to have independent regions of the graph.
+///
+/// FIXME: There is one major drawback of the reference graph: in its naive
+/// form it is quadratic because it contains a distinct edge for each
+/// (potentially indirect) reference, even if are all through some common
+/// global table of function pointers. This can be fixed in a number of ways
+/// that essentially preserve enough of the normalization. While it isn't
+/// expected to completely preclude the usability of this, it will need to be
+/// addressed.
+///
+///
+/// All of these issues are made substantially more complex in the face of
+/// mutations to the call graph while optimization passes are being run. When
+/// mutations to the call graph occur we want to achieve two different things:
+///
+/// - We need to update the call graph in-flight and invalidate analyses
+///   cached on entities in the graph. Because of the cache-based analysis
+///   design of the pass manager, it is essential to have stable identities for
+///   the elements of the IR that passes traverse, and to invalidate any
+///   analyses cached on these elements as the mutations take place.
+///
+/// - We want to preserve the incremental and post-order traversal of the
+///   graph even as it is refined and mutated. This means we want optimization
+///   to observe the most refined form of the call graph and to do so in
+///   post-order.
+///
+/// To address this, the CGSCC manager uses both worklists that can be expanded
+/// by passes which transform the IR, and provides invalidation tests to skip
+/// entries that become dead. This extra data is provided to every SCC pass so
+/// that it can carefully update the manager's traversal as the call graph
+/// mutates.
+///
+/// We also provide support for running function passes within the CGSCC walk,
+/// and there we provide automatic update of the call graph including of the
+/// pass manager to reflect call graph changes that fall out naturally as part
+/// of scalar transformations.
+///
+/// The patterns used to ensure the goals of post-order visitation of the fully
+/// refined graph:
+///
+/// 1) Sink toward the "bottom" as the graph is refined. This means that any
+///    iteration continues in some valid post-order sequence after the mutation
+///    has altered the structure.
+///
+/// 2) Enqueue in post-order, including the current entity. If the current
+///    entity's shape changes, it and everything after it in post-order needs
+///    to be visited to observe that shape.
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 
+#include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
-extern template class PassManager<LazyCallGraph::SCC>;
-/// \brief The CGSCC pass manager.
-///
-/// See the documentation for the PassManager template for details. It runs
-/// a sequency of SCC passes over each SCC that the manager is run over. This
-/// typedef serves as a convenient way to refer to this construct.
-typedef PassManager<LazyCallGraph::SCC> CGSCCPassManager;
+struct CGSCCUpdateResult;
 
-extern template class AnalysisManager<LazyCallGraph::SCC>;
+extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
 /// \brief The CGSCC analysis manager.
 ///
 /// See the documentation for the AnalysisManager template for detail
 /// documentation. This typedef serves as a convenient way to refer to this
 /// construct in the adaptors and proxies used to integrate this into the larger
 /// pass manager infrastructure.
-typedef AnalysisManager<LazyCallGraph::SCC> CGSCCAnalysisManager;
+typedef AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>
+    CGSCCAnalysisManager;
+
+// Explicit specialization and instantiation declarations for the pass manager.
+// See the comments on the definition of the specialization for details on how
+// it differs from the primary template.
+template <>
+PreservedAnalyses
+PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
+            CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
+                                      CGSCCAnalysisManager &AM,
+                                      LazyCallGraph &G, CGSCCUpdateResult &UR);
+extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
+                                  LazyCallGraph &, CGSCCUpdateResult &>;
+
+/// \brief The CGSCC pass manager.
+///
+/// See the documentation for the PassManager template for details. It runs
+/// a sequency of SCC passes over each SCC that the manager is run over. This
+/// typedef serves as a convenient way to refer to this construct.
+typedef PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
+                    CGSCCUpdateResult &>
+    CGSCCPassManager;
+
+/// An explicit specialization of the require analysis template pass.
+template <typename AnalysisT>
+struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager,
+                           LazyCallGraph &, CGSCCUpdateResult &>
+    : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC,
+                                        CGSCCAnalysisManager, LazyCallGraph &,
+                                        CGSCCUpdateResult &>> {
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &) {
+    (void)AM.template getResult<AnalysisT>(C, CG);
+    return PreservedAnalyses::all();
+  }
+};
 
 extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
 /// A proxy from a \c CGSCCAnalysisManager to a \c Module.
 typedef InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>
     CGSCCAnalysisManagerModuleProxy;
 
-extern template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
-                                                LazyCallGraph::SCC>;
+extern template class OuterAnalysisManagerProxy<
+    ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
 /// A proxy from a \c ModuleAnalysisManager to an \c SCC.
-typedef OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC>
+typedef OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC,
+                                  LazyCallGraph &>
     ModuleAnalysisManagerCGSCCProxy;
 
+/// Support structure for SCC passes to communicate updates the call graph back
+/// to the CGSCC pass manager infrsatructure.
+///
+/// The CGSCC pass manager runs SCC passes which are allowed to update the call
+/// graph and SCC structures. This means the structure the pass manager works
+/// on is mutating underneath it. In order to support that, there needs to be
+/// careful communication about the precise nature and ramifications of these
+/// updates to the pass management infrastructure.
+///
+/// All SCC passes will have to accept a reference to the management layer's
+/// update result struct and use it to reflect the results of any CG updates
+/// performed.
+///
+/// Passes which do not change the call graph structure in any way can just
+/// ignore this argument to their run method.
+struct CGSCCUpdateResult {
+  /// Worklist of the RefSCCs queued for processing.
+  ///
+  /// When a pass refines the graph and creates new RefSCCs or causes them to
+  /// have a different shape or set of component SCCs it should add the RefSCCs
+  /// to this worklist so that we visit them in the refined form.
+  ///
+  /// This worklist is in reverse post-order, as we pop off the back in order
+  /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add
+  /// them in reverse post-order.
+  SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist;
+
+  /// Worklist of the SCCs queued for processing.
+  ///
+  /// When a pass refines the graph and creates new SCCs or causes them to have
+  /// a different shape or set of component functions it should add the SCCs to
+  /// this worklist so that we visit them in the refined form.
+  ///
+  /// Note that if the SCCs are part of a RefSCC that is added to the \c
+  /// RCWorklist, they don't need to be added here as visiting the RefSCC will
+  /// be sufficient to re-visit the SCCs within it.
+  ///
+  /// This worklist is in reverse post-order, as we pop off the back in order
+  /// to observe SCCs in post-order. When adding SCCs, clients should add them
+  /// in reverse post-order.
+  SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist;
+
+  /// The set of invalidated RefSCCs which should be skipped if they are found
+  /// in \c RCWorklist.
+  ///
+  /// This is used to quickly prune out RefSCCs when they get deleted and
+  /// happen to already be on the worklist. We use this primarily to avoid
+  /// scanning the list and removing entries from it.
+  SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs;
+
+  /// The set of invalidated SCCs which should be skipped if they are found
+  /// in \c CWorklist.
+  ///
+  /// This is used to quickly prune out SCCs when they get deleted and happen
+  /// to already be on the worklist. We use this primarily to avoid scanning
+  /// the list and removing entries from it.
+  SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;
+
+  /// If non-null, the updated current \c RefSCC being processed.
+  ///
+  /// This is set when a graph refinement takes place an the "current" point in
+  /// the graph moves "down" or earlier in the post-order walk. This will often
+  /// cause the "current" RefSCC to be a newly created RefSCC object and the
+  /// old one to be added to the above worklist. When that happens, this
+  /// pointer is non-null and can be used to continue processing the "top" of
+  /// the post-order walk.
+  LazyCallGraph::RefSCC *UpdatedRC;
+
+  /// If non-null, the updated current \c SCC being processed.
+  ///
+  /// This is set when a graph refinement takes place an the "current" point in
+  /// the graph moves "down" or earlier in the post-order walk. This will often
+  /// cause the "current" SCC to be a newly created SCC object and the old one
+  /// to be added to the above worklist. When that happens, this pointer is
+  /// non-null and can be used to continue processing the "top" of the
+  /// post-order walk.
+  LazyCallGraph::SCC *UpdatedC;
+};
+
 /// \brief The core module pass which does a post-order walk of the SCCs and
 /// runs a CGSCC pass over each one.
 ///
 /// Designed to allow composition of a CGSCCPass(Manager) and
 /// a ModulePassManager. Note that this pass must be run with a module analysis
 /// manager as it uses the LazyCallGraph analysis. It will also run the
 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
 /// pass over the module to enable a \c FunctionAnalysisManager to be used
public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     // Setup the CGSCC analysis manager from its proxy.
     CGSCCAnalysisManager &CGAM =
         AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
 
     // Get the call graph for this module.
     LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
 
+    // We keep worklists to allow us to push more work onto the pass manager as
+    // the passes are run.
+    SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
+    SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
+
+    // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
+    // iterating off the worklists.
+    SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
+    SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
+
+    CGSCCUpdateResult UR = {RCWorklist,    CWorklist, InvalidRefSCCSet,
+                            InvalidSCCSet, nullptr,   nullptr};
+
     PreservedAnalyses PA = PreservedAnalyses::all();
-    for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) {
-      if (DebugLogging)
-        dbgs() << "Running an SCC pass across the RefSCC: " << RC << "\n";
+    for (LazyCallGraph::RefSCC &InitialRC : CG.postorder_ref_sccs()) {
+      assert(RCWorklist.empty() &&
+             "Should always start with an empty RefSCC worklist");
+      // The postorder_ref_sccs range we are walking is lazily constructed, so
+      // we only push the first one onto the worklist. The worklist allows us
+      // to capture *new* RefSCCs created during transformations.
+      //
+      // We really want to form RefSCCs lazily because that makes them cheaper
+      // to update as the program is simplified and allows us to have greater
+      // cache locality as forming a RefSCC touches all the parts of all the
+      // functions within that RefSCC.
+      RCWorklist.insert(&InitialRC);
+
+      do {
+        LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
+        if (InvalidRefSCCSet.count(RC))
+          continue;
+
+        assert(CWorklist.empty() &&
+               "Should always start with an empty SCC worklist");
 
-      for (LazyCallGraph::SCC &C : RC) {
-        PreservedAnalyses PassPA = Pass.run(C, CGAM);
+        if (DebugLogging)
+          dbgs() << "Running an SCC pass across the RefSCC: " << *RC << "\n";
 
-        // We know that the CGSCC pass couldn't have invalidated any other
-        // SCC's analyses (that's the contract of a CGSCC pass), so
-        // directly handle the CGSCC analysis manager's invalidation here. We
-        // also update the preserved set of analyses to reflect that invalidated
-        // analyses are now safe to preserve.
-        // FIXME: This isn't quite correct. We need to handle the case where the
-        // pass updated the CG, particularly some child of the current SCC, and
-        // invalidate its analyses.
-        PassPA = CGAM.invalidate(C, std::move(PassPA));
+        // Push the initial SCCs in reverse post-order as we'll pop off the the
+        // back and so see this in post-order.
+        for (LazyCallGraph::SCC &C : reverse(*RC))
+          CWorklist.insert(&C);
+
+        do {
+          LazyCallGraph::SCC *C = CWorklist.pop_back_val();
+          // Due to call graph mutations, we may have invalid SCCs or SCCs from
+          // other RefSCCs in the worklist. The invalid ones are dead and the
+          // other RefSCCs should be queued above, so we just need to skip both
+          // scenarios here.
+          if (InvalidSCCSet.count(C) || &C->getOuterRefSCC() != RC)
+            continue;
+
+          do {
+            // Check that we didn't miss any update scenario.
+            assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
+            assert(C->begin() != C->end() && "Cannot have an empty SCC!");
+            assert(&C->getOuterRefSCC() == RC &&
+                   "Processing an SCC in a different RefSCC!");
+
+            UR.UpdatedRC = nullptr;
+            UR.UpdatedC = nullptr;
+            PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
+
+            // We handle invalidating the CGSCC analysis manager's information
+            // for the (potentially updated) SCC here. Note that any other SCCs
+            // whose structure has changed should have been invalidated by
+            // whatever was updating the call graph. This SCC gets invalidated
+            // late as it contains the nodes that were actively being
+            // processed.
+            PassPA = CGAM.invalidate(*(UR.UpdatedC ? UR.UpdatedC : C),
+                                     std::move(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));
-      }
+
+            // The pass may have restructured the call graph and refined the
+            // current SCC and/or RefSCC. We need to update our current SCC and
+            // RefSCC pointers to follow these. Also, when the current SCC is
+            // refined, re-run the SCC pass over the newly refined SCC in order
+            // to observe the most precise SCC model available. This inherently
+            // cannot cycle excessively as it only happens when we split SCCs
+            // apart, at most converging on a DAG of single nodes.
+            // FIXME: If we ever start having RefSCC passes, we'll want to
+            // iterate there too.
+            RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
+            C = UR.UpdatedC ? UR.UpdatedC : C;
+            if (DebugLogging && UR.UpdatedC)
+              dbgs() << "Re-running SCC passes after a refinement of the "
+                        "current SCC: "
+                     << *UR.UpdatedC << "\n";
+          } while (UR.UpdatedC);
+
+        } while (!CWorklist.empty());
+      } while (!RCWorklist.empty());
     }
 
     // By definition we preserve the proxy. This precludes *any* invalidation
     // of CGSCC analyses by the proxy, but that's OK because we've taken
     // care to invalidate analyses in the CGSCC analysis manager
     // incrementally above.
     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
     return PA;
   }
 
 private:
   CGSCCPassT Pass;
   bool DebugLogging;
 };
 
 /// \brief A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename CGSCCPassT>
 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass, bool DebugLogging = false) {
   return ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass), DebugLogging);
 }
 
-extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
-                                                LazyCallGraph::SCC>;
+extern template class InnerAnalysisManagerProxy<
+    FunctionAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
 /// A proxy from a \c FunctionAnalysisManager to an \c SCC.
-typedef InnerAnalysisManagerProxy<FunctionAnalysisManager, LazyCallGraph::SCC>
+typedef InnerAnalysisManagerProxy<FunctionAnalysisManager, LazyCallGraph::SCC,
+                                  LazyCallGraph &>
     FunctionAnalysisManagerCGSCCProxy;
 
 extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
 /// A proxy from a \c CGSCCAnalysisManager to a \c Function.
 typedef OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>
     CGSCCAnalysisManagerFunctionProxy;
 
+/// Helper to update the call graph after running a function pass.
+///
+/// Function passes can only mutate the call graph in specific ways. This
+/// routine provides a helper that updates the call graph in those ways
+/// including returning whether any changes were made and populating a CG
+/// update result struct for the overall CGSCC walk.
+LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass(
+    LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N,
+    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, bool DebugLogging = false);
+
 /// \brief Adaptor that maps from a SCC to its functions.
 ///
 /// Designed to allow composition of a FunctionPass(Manager) and
 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
 /// to a \c CGSCCAnalysisManager it will run the
 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
 /// within this run safely.
friend void swap(CGSCCToFunctionPassAdaptor &LHS,
     swap(LHS.DebugLogging, RHS.DebugLogging);
   }
   CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   /// \brief Runs the function pass across every function in the module.
-  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM) {
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     // Setup the function analysis manager from its proxy.
     FunctionAnalysisManager &FAM =
-        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
+        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
+
+    SmallVector<LazyCallGraph::Node *, 4> Nodes;
+    for (LazyCallGraph::Node &N : C)
+      Nodes.push_back(&N);
+
+    // The SCC may get split while we are optimizing functions due to deleting
+    // edges. If this happens, the current SCC can shift, so keep track of
+    // a pointer we can overwrite.
+    LazyCallGraph::SCC *CurrentC = &C;
 
     if (DebugLogging)
       dbgs() << "Running function passes across an SCC: " << C << "\n";
 
     PreservedAnalyses PA = PreservedAnalyses::all();
-    for (LazyCallGraph::Node &N : C) {
-      PreservedAnalyses PassPA = Pass.run(N.getFunction(), FAM);
+    for (LazyCallGraph::Node *N : Nodes) {
+      // Skip nodes from other SCCs. These may have been split out during
+      // processing. We'll eventually visit those SCCs and pick up the nodes
+      // there.
+      if (CG.lookupSCC(*N) != CurrentC)
+        continue;
+
+      PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
 
       // We know that the function pass couldn't have invalidated any other
       // function's analyses (that's the contract of a function pass), so
       // directly handle the function analysis manager's invalidation here.
       // Also, update the preserved analyses to reflect that once invalidated
       // these can again be preserved.
-      PassPA = FAM.invalidate(N.getFunction(), std::move(PassPA));
+      PassPA = FAM.invalidate(N->getFunction(), std::move(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));
+
+      // Update the call graph based on this function pass. This may also
+      // update the current SCC to point to a smaller, more refined SCC.
+      CurrentC = &updateCGAndAnalysisManagerForFunctionPass(
+          CG, *CurrentC, *N, AM, UR, DebugLogging);
+      assert(CG.lookupSCC(*N) == CurrentC &&
+             "Current SCC not updated to the SCC containing the current node!");
     }
 
     // By definition we preserve the proxy. 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.
-    // FIXME: We need to update the call graph here to account for any deleted
-    // edges!
     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+
+    // We've also ensured that we updated the call graph along the way.
+    PA.preserve<LazyCallGraphAnalysis>();
+
     return PA;
   }
 
 private:
   FunctionPassT Pass;
   bool DebugLogging;
 };
 

llvm/trunk/include/llvm/Analysis/LazyCallGraph.h

public:
     explicit Edge(Node &N, Kind K);
 
     /// Test whether the edge is null.
     ///
     /// This happens when an edge has been deleted. We leave the edge objects
     /// around but clear them.
     operator bool() const;
 
+    /// Returnss the \c Kind of the edge.
+    Kind getKind() const;
+
     /// Test whether the edge represents a direct call to a function.
     ///
     /// This requires that the edge is not null.
     bool isCall() const;
 
     /// Get the function referenced by this edge.
     ///
     /// This requires that the edge is not null, but will succeed whether we
public:
 
     const Edge &operator[](int i) const { return Edges[i]; }
     const Edge &operator[](Function &F) const {
       assert(EdgeIndexMap.find(&F) != EdgeIndexMap.end() && "No such edge!");
       return Edges[EdgeIndexMap.find(&F)->second];
     }
     const Edge &operator[](Node &N) const { return (*this)[N.getFunction()]; }
 
+    const Edge *lookup(Function &F) const {
+      auto EI = EdgeIndexMap.find(&F);
+      return EI != EdgeIndexMap.end() ? &Edges[EI->second] : nullptr;
+    }
+
     call_edge_iterator call_begin() const {
       return call_edge_iterator(Edges.begin(), Edges.end());
     }
     call_edge_iterator call_end() const {
       return call_edge_iterator(Edges.end(), Edges.end());
     }
 
     iterator_range<call_edge_iterator> calls() const {
public:
     /// Make an existing internal call edge into a ref edge.
     ///
     /// If SourceN and TargetN are part of a single SCC, it may be split up due
     /// to breaking a cycle in the call edges that formed it. If that happens,
     /// then this routine will insert new SCCs into the postorder list *before*
     /// the SCC of TargetN (previously the SCC of both). This preserves
     /// postorder as the TargetN can reach all of the other nodes by definition
     /// of previously being in a single SCC formed by the cycle from SourceN to
-    /// TargetN. The newly added nodes are added *immediately* and contiguously
-    /// prior to the TargetN SCC and so they may be iterated starting from
-    /// there.
-    void switchInternalEdgeToRef(Node &SourceN, Node &TargetN);
+    /// TargetN.
+    ///
+    /// The newly added SCCs are added *immediately* and contiguously
+    /// prior to the TargetN SCC and return the range covering the new SCCs in
+    /// the RefSCC's postorder sequence. You can directly iterate the returned
+    /// range to observe all of the new SCCs in postorder.
+    iterator_range<iterator> switchInternalEdgeToRef(Node &SourceN,
+                                                     Node &TargetN);
 
     /// Make an existing outgoing ref edge into a call edge.
     ///
     /// Note that this is trivial as there are no cyclic impacts and there
     /// remains a reference edge.
     void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN);
 
     /// Make an existing outgoing call edge into a ref edge.
#endif
 
   /// Update the call graph after deleting an edge.
   void removeEdge(Function &Caller, Function &Callee) {
     return removeEdge(get(Caller), Callee);
   }
 
   ///@}
 
+  ///@{
+  /// \name Static helpers for code doing updates to the call graph.
+  ///
+  /// These helpers are used to implement parts of the call graph but are also
+  /// useful to code doing updates or otherwise wanting to walk the IR in the
+  /// same patterns as when we build the call graph.
+
+  template <typename CallbackT>
+  static void visitReferences(SmallVectorImpl<Constant *> &Worklist,
+                              SmallPtrSetImpl<Constant *> &Visited,
+                              CallbackT Callback) {
+    while (!Worklist.empty()) {
+      Constant *C = Worklist.pop_back_val();
+
+      if (Function *F = dyn_cast<Function>(C)) {
+        Callback(*F);
+        continue;
+      }
+
+      for (Value *Op : C->operand_values())
+        if (Visited.insert(cast<Constant>(Op)).second)
+          Worklist.push_back(cast<Constant>(Op));
+    }
+
+    ///@}
+  }
+
 private:
   typedef SmallVectorImpl<Node *>::reverse_iterator node_stack_iterator;
   typedef iterator_range<node_stack_iterator> node_stack_range;
 
   /// Allocator that holds all the call graph nodes.
   SpecificBumpPtrAllocator<Node> BPA;
 
   /// Maps function->node for fast lookup.

 inline LazyCallGraph::Edge::Edge() : Value() {}
 inline LazyCallGraph::Edge::Edge(Function &F, Kind K) : Value(&F, K) {}
 inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {}
 
 inline LazyCallGraph::Edge::operator bool() const {
   return !Value.getPointer().isNull();
 }
 
+inline LazyCallGraph::Edge::Kind LazyCallGraph::Edge::getKind() const {
+  assert(*this && "Queried a null edge!");
+  return Value.getInt();
+}
+
 inline bool LazyCallGraph::Edge::isCall() const {
   assert(*this && "Queried a null edge!");
-  return Value.getInt() == Call;
+  return getKind() == Call;
 }
 
 inline Function &LazyCallGraph::Edge::getFunction() const {
   assert(*this && "Queried a null edge!");
   auto P = Value.getPointer();
   if (auto *F = P.dyn_cast<Function *>())
     return *F;
 

llvm/trunk/include/llvm/IR/PassManager.h

public:
   /// \brief Returns true if the analysis manager has an empty results cache.
   bool empty() const {
     assert(AnalysisResults.empty() == AnalysisResultLists.empty() &&
            "The storage and index of analysis results disagree on how many "
            "there are!");
     return AnalysisResults.empty();
   }
 
+  /// \brief Clear any results for a single unit of IR.
+  ///
+  /// This doesn't invalidate but directly clears the results. It is useful
+  /// when the IR is being removed and we want to clear out all the memory
+  /// pinned for it.
+  void clear(IRUnitT &IR) {
+    if (DebugLogging)
+      dbgs() << "Clearing all analysis results for: " << IR.getName() << "\n";
+
+    // Clear all the invalidated results associated specifically with this
+    // function.
+    SmallVector<void *, 8> InvalidatedPassIDs;
+    auto ResultsListI = AnalysisResultLists.find(&IR);
+    if (ResultsListI == AnalysisResultLists.end())
+      return;
+    // Clear the map pointing into the results list.
+    for (auto &PassIDAndResult : ResultsListI->second)
+      AnalysisResults.erase(std::make_pair(PassIDAndResult.first, &IR));
+
+    // And actually destroy and erase the results associated with this IR.
+    AnalysisResultLists.erase(ResultsListI);
+  }
+
   /// \brief Clear the analysis result cache.
   ///
   /// This routine allows cleaning up when the set of IR units itself has
   /// potentially changed, and thus we can't even look up a a result and
-  /// invalidate it directly. Notably, this does *not* call invalidate functions
-  /// as there is nothing to be done for them.
+  /// invalidate it directly. Notably, this does *not* call invalidate
+  /// functions as there is nothing to be done for them.
   void clear() {
     AnalysisResults.clear();
     AnalysisResultLists.clear();
   }
 
   /// \brief Get the result of an analysis pass for this module.
   ///
   /// If there is not a valid cached result in the manager already, this will

llvm/trunk/include/llvm/Transforms/IPO/FunctionAttrs.h

 /// By operating in post-order, this pass computes precise attributes for
 /// called functions prior to processsing their callers. This "bottom-up"
 /// approach allows powerful interprocedural inference of function attributes
 /// like memory access patterns, etc. It can discover functions that do not
 /// access memory, or only read memory, and give them the readnone/readonly
 /// attribute. It also discovers function arguments that are not captured by
 /// the function and marks them with the nocapture attribute.
 struct PostOrderFunctionAttrsPass : PassInfoMixin<PostOrderFunctionAttrsPass> {
-  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM);
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &UR);
 };
 
 /// Create a legacy pass manager instance of a pass to compute function attrs
 /// in post-order.
 Pass *createPostOrderFunctionAttrsLegacyPass();
 
 /// A pass to do RPO deduction and propagation of function attributes.
 ///

llvm/trunk/lib/Analysis/CGSCCPassManager.cpp

 //===- CGSCCPassManager.cpp - Managing & running CGSCC passes -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/IR/CallSite.h"
 
 using namespace llvm;
 
-// Explicit instantiations for the core proxy templates.
 namespace llvm {
-template class PassManager<LazyCallGraph::SCC>;
-template class AnalysisManager<LazyCallGraph::SCC>;
+
+// Explicit instantiations for the core proxy templates.
+template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
+template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
+                           LazyCallGraph &, CGSCCUpdateResult &>;
 template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
 template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
-                                         LazyCallGraph::SCC>;
+                                         LazyCallGraph::SCC, LazyCallGraph &>;
 template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
-                                         LazyCallGraph::SCC>;
+                                         LazyCallGraph::SCC, LazyCallGraph &>;
 template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
+
+/// Explicitly specialize the pass manager run method to handle call graph
+/// updates.
+template <>
+PreservedAnalyses
+PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
+            CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
+                                      CGSCCAnalysisManager &AM,
+                                      LazyCallGraph &G, CGSCCUpdateResult &UR) {
+  PreservedAnalyses PA = PreservedAnalyses::all();
+
+  if (DebugLogging)
+    dbgs() << "Starting CGSCC pass manager run.\n";
+
+  // The SCC may be refined while we are running passes over it, so set up
+  // a pointer that we can update.
+  LazyCallGraph::SCC *C = &InitialC;
+
+  for (auto &Pass : Passes) {
+    if (DebugLogging)
+      dbgs() << "Running pass: " << Pass->name() << " on " << *C << "\n";
+
+    PreservedAnalyses PassPA = Pass->run(*C, AM, G, UR);
+
+    // Update the SCC if necessary.
+    C = UR.UpdatedC ? UR.UpdatedC : C;
+
+    // Check that we didn't miss any update scenario.
+    assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
+    assert(C->begin() != C->end() && "Cannot have an empty SCC!");
+
+    // Update the analysis manager as each pass runs and potentially
+    // invalidates analyses. We also update the preserved set of analyses
+    // based on what analyses we have already handled the invalidation for
+    // here and don't need to invalidate when finished.
+    PassPA = AM.invalidate(*C, std::move(PassPA));
+
+    // Finally, we intersect the final preserved analyses to compute the
+    // aggregate preserved set for this pass manager.
+    PA.intersect(std::move(PassPA));
+
+    // FIXME: Historically, the pass managers all called the LLVM context's
+    // yield function here. We don't have a generic way to acquire the
+    // context and it isn't yet clear what the right pattern is for yielding
+    // in the new pass manager so it is currently omitted.
+    // ...getContext().yield();
+  }
+
+  if (DebugLogging)
+    dbgs() << "Finished CGSCC pass manager run.\n";
+
+  return PA;
+}
+
+} // End llvm namespace
+
+namespace {
+/// Helper function to update both the \c CGSCCAnalysisManager \p AM and the \c
+/// CGSCCPassManager's \c CGSCCUpdateResult \p UR based on a range of newly
+/// added SCCs.
+///
+/// The range of new SCCs must be in postorder already. The SCC they were split
+/// out of must be provided as \p C. The current node being mutated and
+/// triggering updates must be passed as \p N.
+///
+/// This function returns the SCC containing \p N. This will be either \p C if
+/// no new SCCs have been split out, or it will be the new SCC containing \p N.
+template <typename SCCRangeT>
+LazyCallGraph::SCC *
+incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
+                       LazyCallGraph::Node &N, LazyCallGraph::SCC *C,
+                       CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
+                       bool DebugLogging = false) {
+  typedef LazyCallGraph::SCC SCC;
+
+  if (NewSCCRange.begin() == NewSCCRange.end())
+    return C;
+
+  // Invalidate the analyses of the current SCC and add it to the worklist since
+  // it has changed its shape.
+  AM.invalidate(*C, PreservedAnalyses::none());
+  UR.CWorklist.insert(C);
+  if (DebugLogging)
+    dbgs() << "Enqueuing the existing SCC in the worklist:" << *C << "\n";
+
+  SCC *OldC = C;
+  (void)OldC;
+
+  // Update the current SCC. Note that if we have new SCCs, this must actually
+  // change the SCC.
+  assert(C != &*NewSCCRange.begin() &&
+         "Cannot insert new SCCs without changing current SCC!");
+  C = &*NewSCCRange.begin();
+  assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
+
+  for (SCC &NewC :
+       reverse(make_range(std::next(NewSCCRange.begin()), NewSCCRange.end()))) {
+    assert(C != &NewC && "No need to re-visit the current SCC!");
+    assert(OldC != &NewC && "Already handled the original SCC!");
+    UR.CWorklist.insert(&NewC);
+    if (DebugLogging)
+      dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n";
+  }
+  return C;
+}
+}
+
+LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
+    LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
+    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, bool DebugLogging) {
+  typedef LazyCallGraph::Node Node;
+  typedef LazyCallGraph::Edge Edge;
+  typedef LazyCallGraph::SCC SCC;
+  typedef LazyCallGraph::RefSCC RefSCC;
+
+  RefSCC &InitialRC = InitialC.getOuterRefSCC();
+  SCC *C = &InitialC;
+  RefSCC *RC = &InitialRC;
+  Function &F = N.getFunction();
+
+  // Walk the function body and build up the set of retained, promoted, and
+  // demoted edges.
+  SmallVector<Constant *, 16> Worklist;
+  SmallPtrSet<Constant *, 16> Visited;
+  SmallPtrSet<Function *, 16> RetainedEdges;
+  SmallSetVector<Function *, 4> PromotedRefTargets;
+  SmallSetVector<Function *, 4> DemotedCallTargets;
+  // First walk the function and handle all called functions. We do this first
+  // because if there is a single call edge, whether there are ref edges is
+  // irrelevant.
+  for (BasicBlock &BB : F)
+    for (Instruction &I : BB)
+      if (auto CS = CallSite(&I))
+        if (Function *Callee = CS.getCalledFunction())
+          if (Visited.insert(Callee).second && !Callee->isDeclaration()) {
+            const Edge *E = N.lookup(*Callee);
+            // FIXME: We should really handle adding new calls. While it will
+            // make downstream usage more complex, there is no fundamental
+            // limitation and it will allow passes within the CGSCC to be a bit
+            // more flexible in what transforms they can do. Until then, we
+            // verify that new calls haven't been introduced.
+            assert(E && "No function transformations should introduce *new* "
+                        "call edges! Any new calls should be modeled as "
+                        "promoted existing ref edges!");
+            RetainedEdges.insert(Callee);
+            if (!E->isCall())
+              PromotedRefTargets.insert(Callee);
+          }
+
+  // Now walk all references.
+  for (BasicBlock &BB : F)
+    for (Instruction &I : BB) {
+      for (Value *Op : I.operand_values())
+        if (Constant *C = dyn_cast<Constant>(Op))
+          if (Visited.insert(C).second)
+            Worklist.push_back(C);
+
+      LazyCallGraph::visitReferences(Worklist, Visited, [&](Function &Referee) {
+        // Skip declarations.
+        if (Referee.isDeclaration())
+          return;
+
+        const Edge *E = N.lookup(Referee);
+        // FIXME: Similarly to new calls, we also currently preclude
+        // introducing new references. See above for details.
+        assert(E && "No function transformations should introduce *new* ref "
+                    "edges! Any new ref edges would require IPO which "
+                    "function passes aren't allowed to do!");
+        RetainedEdges.insert(&Referee);
+        if (E->isCall())
+          DemotedCallTargets.insert(&Referee);
+      });
+    }
+
+  // First remove all of the edges that are no longer present in this function.
+  // We have to build a list of dead targets first and then remove them as the
+  // data structures will all be invalidated by removing them.
+  SmallVector<PointerIntPair<Node *, 1, Edge::Kind>, 4> DeadTargets;
+  for (Edge &E : N)
+    if (!RetainedEdges.count(&E.getFunction()))
+      DeadTargets.push_back({E.getNode(), E.getKind()});
+  for (auto DeadTarget : DeadTargets) {
+    Node &TargetN = *DeadTarget.getPointer();
+    bool IsCall = DeadTarget.getInt() == Edge::Call;
+    SCC &TargetC = *G.lookupSCC(TargetN);
+    RefSCC &TargetRC = TargetC.getOuterRefSCC();
+
+    if (&TargetRC != RC) {
+      RC->removeOutgoingEdge(N, TargetN);
+      if (DebugLogging)
+        dbgs() << "Deleting outgoing edge from '" << N << "' to '" << TargetN
+               << "'\n";
+      continue;
+    }
+    if (DebugLogging)
+      dbgs() << "Deleting internal " << (IsCall ? "call" : "ref")
+             << " edge from '" << N << "' to '" << TargetN << "'\n";
+
+    if (IsCall)
+      C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G, N,
+                                 C, AM, UR, DebugLogging);
+
+    auto NewRefSCCs = RC->removeInternalRefEdge(N, TargetN);
+    if (!NewRefSCCs.empty()) {
+      // Note that we don't bother to invalidate analyses as ref-edge
+      // connectivity is not really observable in any way and is intended
+      // exclusively to be used for ordering of transforms rather than for
+      // analysis conclusions.
+
+      // The RC worklist is in reverse postorder, so we first enqueue the
+      // current RefSCC as it will remain the parent of all split RefSCCs, then
+      // we enqueue the new ones in RPO except for the one which contains the
+      // source node as that is the "bottom" we will continue processing in the
+      // bottom-up walk.
+      UR.RCWorklist.insert(RC);
+      if (DebugLogging)
+        dbgs() << "Enqueuing the existing RefSCC in the update worklist: "
+               << *RC << "\n";
+      // Update the RC to the "bottom".
+      assert(G.lookupSCC(N) == C && "Changed the SCC when splitting RefSCCs!");
+      RC = &C->getOuterRefSCC();
+      assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!");
+      for (RefSCC *NewRC : reverse(NewRefSCCs))
+        if (NewRC != RC) {
+          UR.RCWorklist.insert(NewRC);
+          if (DebugLogging)
+            dbgs() << "Enqueuing a new RefSCC in the update worklist: "
+                   << *NewRC << "\n";
+        }
+    }
+  }
+
+  // Next demote all the call edges that are now ref edges. This helps make
+  // the SCCs small which should minimize the work below as we don't want to
+  // form cycles that this would break.
+  for (Function *RefTarget : DemotedCallTargets) {
+    Node &TargetN = *G.lookup(*RefTarget);
+    SCC &TargetC = *G.lookupSCC(TargetN);
+    RefSCC &TargetRC = TargetC.getOuterRefSCC();
+
+    // The easy case is when the target RefSCC is not this RefSCC. This is
+    // only supported when the target RefSCC is a child of this RefSCC.
+    if (&TargetRC != RC) {
+      assert(RC->isAncestorOf(TargetRC) &&
+             "Cannot potentially form RefSCC cycles here!");
+      RC->switchOutgoingEdgeToRef(N, TargetN);
+      if (DebugLogging)
+        dbgs() << "Switch outgoing call edge to a ref edge from '" << N
+               << "' to '" << TargetN << "'\n";
+      continue;
+    }
+
+    // Otherwise we are switching an internal call edge to a ref edge. This
+    // may split up some SCCs.
+    C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G, N, C,
+                               AM, UR, DebugLogging);
+  }
+
+  // Now promote ref edges into call edges.
+  for (Function *CallTarget : PromotedRefTargets) {
+    Node &TargetN = *G.lookup(*CallTarget);
+    SCC &TargetC = *G.lookupSCC(TargetN);
+    RefSCC &TargetRC = TargetC.getOuterRefSCC();
+
+    // The easy case is when the target RefSCC is not this RefSCC. This is
+    // only supported when the target RefSCC is a child of this RefSCC.
+    if (&TargetRC != RC) {
+      assert(RC->isAncestorOf(TargetRC) &&
+             "Cannot potentially form RefSCC cycles here!");
+      RC->switchOutgoingEdgeToCall(N, TargetN);
+      if (DebugLogging)
+        dbgs() << "Switch outgoing ref edge to a call edge from '" << N
+               << "' to '" << TargetN << "'\n";
+      continue;
+    }
+    if (DebugLogging)
+      dbgs() << "Switch an internal ref edge to a call edge from '" << N
+             << "' to '" << TargetN << "'\n";
+
+    // Otherwise we are switching an internal ref edge to a call edge. This
+    // may merge away some SCCs, and we add those to the UpdateResult. We also
+    // need to make sure to update the worklist in the event SCCs have moved
+    // before the current one in the post-order sequence.
+    auto InitialSCCIndex = RC->find(*C) - RC->begin();
+    auto InvalidatedSCCs = RC->switchInternalEdgeToCall(N, TargetN);
+    if (!InvalidatedSCCs.empty()) {
+      C = &TargetC;
+      assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
+
+      // Any analyses cached for this SCC are no longer precise as the shape
+      // has changed by introducing this cycle.
+      AM.invalidate(*C, PreservedAnalyses::none());
+
+      for (SCC *InvalidatedC : InvalidatedSCCs) {
+        assert(InvalidatedC != C && "Cannot invalidate the current SCC!");
+        UR.InvalidatedSCCs.insert(InvalidatedC);
+
+        // Also clear any cached analyses for the SCCs that are dead. This
+        // isn't really necessary for correctness but can release memory.
+        AM.clear(*InvalidatedC);
+      }
+    }
+    auto NewSCCIndex = RC->find(*C) - RC->begin();
+    if (InitialSCCIndex < NewSCCIndex) {
+      // Put our current SCC back onto the worklist as we'll visit other SCCs
+      // that are now definitively ordered prior to the current one in the
+      // post-order sequence, and may end up observing more precise context to
+      // optimize the current SCC.
+      UR.CWorklist.insert(C);
+      if (DebugLogging)
+        dbgs() << "Enqueuing the existing SCC in the worklist: " << *C << "\n";
+      // Enqueue in reverse order as we pop off the back of the worklist.
+      for (SCC &MovedC : reverse(make_range(RC->begin() + InitialSCCIndex,
+                                            RC->begin() + NewSCCIndex))) {
+        UR.CWorklist.insert(&MovedC);
+        if (DebugLogging)
+          dbgs() << "Enqueuing a newly earlier in post-order SCC: " << MovedC
+                 << "\n";
+      }
+    }
+  }
+
+  assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");
+  assert(!UR.InvalidatedRefSCCs.count(RC) && "Invalidated the current RefSCC!");
+  assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");
+
+  // Record the current RefSCC and SCC for higher layers of the CGSCC pass
+  // manager now that all the updates have been applied.
+  if (RC != &InitialRC)
+    UR.UpdatedRC = RC;
+  if (C != &InitialC)
+    UR.UpdatedC = C;
+
+  return *C;
 }

llvm/trunk/lib/Analysis/LazyCallGraph.cpp

static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,
   // safety of optimizing a direct call edge.
   if (!F.isDeclaration() &&
       EdgeIndexMap.insert({&F, Edges.size()}).second) {
     DEBUG(dbgs() << "    Added callable function: " << F.getName() << "\n");
     Edges.emplace_back(LazyCallGraph::Edge(F, EK));
   }
 }
 
-static void findReferences(SmallVectorImpl<Constant *> &Worklist,
-                           SmallPtrSetImpl<Constant *> &Visited,
-                           SmallVectorImpl<LazyCallGraph::Edge> &Edges,
-                           DenseMap<Function *, int> &EdgeIndexMap) {
-  while (!Worklist.empty()) {
-    Constant *C = Worklist.pop_back_val();
-
-    if (Function *F = dyn_cast<Function>(C)) {
-      addEdge(Edges, EdgeIndexMap, *F, LazyCallGraph::Edge::Ref);
-      continue;
-    }
-
-    for (Value *Op : C->operand_values())
-      if (Visited.insert(cast<Constant>(Op)).second)
-        Worklist.push_back(cast<Constant>(Op));
-  }
-}
-
 LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F)
     : G(&G), F(F), DFSNumber(0), LowLink(0) {
   DEBUG(dbgs() << "  Adding functions called by '" << F.getName()
                << "' to the graph.\n");
 
   SmallVector<Constant *, 16> Worklist;
   SmallPtrSet<Function *, 4> Callees;
   SmallPtrSet<Constant *, 16> Visited;
for (Instruction &I : BB) {
         if (Constant *C = dyn_cast<Constant>(Op))
           if (Visited.insert(C).second)
             Worklist.push_back(C);
     }
 
   // We've collected all the constant (and thus potentially function or
   // function containing) operands to all of the instructions in the function.
   // Process them (recursively) collecting every function found.
-  findReferences(Worklist, Visited, Edges, EdgeIndexMap);
+  visitReferences(Worklist, Visited, [&](Function &F) {
+    addEdge(Edges, EdgeIndexMap, F, LazyCallGraph::Edge::Ref);
+  });
 }
 
 void LazyCallGraph::Node::insertEdgeInternal(Function &Target, Edge::Kind EK) {
   if (Node *N = G->lookup(Target))
     return insertEdgeInternal(*N, EK);
 
   EdgeIndexMap.insert({&Target, Edges.size()});
   Edges.emplace_back(Target, EK);
LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) {
   SmallPtrSet<Constant *, 16> Visited;
   for (GlobalVariable &GV : M.globals())
     if (GV.hasInitializer())
       if (Visited.insert(GV.getInitializer()).second)
         Worklist.push_back(GV.getInitializer());
 
   DEBUG(dbgs() << "  Adding functions referenced by global initializers to the "
                   "entry set.\n");
-  findReferences(Worklist, Visited, EntryEdges, EntryIndexMap);
+  visitReferences(Worklist, Visited, [&](Function &F) {
+    addEdge(EntryEdges, EntryIndexMap, F, LazyCallGraph::Edge::Ref);
+  });
 
   for (const Edge &E : EntryEdges)
     RefSCCEntryNodes.push_back(&E.getFunction());
 }
 
 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
     : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
       EntryEdges(std::move(G.EntryEdges)),

 }
 
 #ifndef NDEBUG
 void LazyCallGraph::RefSCC::verify() {
   assert(G && "Can't have a null graph!");
   assert(!SCCs.empty() && "Can't have an empty SCC!");
 
   // Verify basic properties of the SCCs.
+  SmallPtrSet<SCC *, 4> SCCSet;
   for (SCC *C : SCCs) {
     assert(C && "Can't have a null SCC!");
     C->verify();
     assert(&C->getOuterRefSCC() == this &&
            "SCC doesn't think it is inside this RefSCC!");
+    bool Inserted = SCCSet.insert(C).second;
+    assert(Inserted && "Found a duplicate SCC!");
   }
 
   // Check that our indices map correctly.
   for (auto &SCCIndexPair : SCCIndices) {
     SCC *C = SCCIndexPair.first;
     int i = SCCIndexPair.second;
     assert(C && "Can't have a null SCC in the indices!");
+    assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
     assert(SCCs[i] == C && "Index doesn't point to SCC!");
   }
 
   // Check that the SCCs are in fact in post-order.
   for (int i = 0, Size = SCCs.size(); i < Size; ++i) {
     SCC &SourceSCC = *SCCs[i];
     for (Node &N : SourceSCC)
       for (Edge &E : N) {

 
 #ifndef NDEBUG
   // And we're done! Verify in debug builds that the RefSCC is coherent.
   verify();
 #endif
   return DeletedSCCs;
 }
 
-void LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN,
-                                                    Node &TargetN) {
+iterator_range<LazyCallGraph::RefSCC::iterator>
+LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) {
   assert(SourceN[TargetN].isCall() && "Must start with a call edge!");
 
   SCC &SourceSCC = *G->lookupSCC(SourceN);
   SCC &TargetSCC = *G->lookupSCC(TargetN);
 
   assert(&SourceSCC.getOuterRefSCC() == this &&
          "Source must be in this RefSCC.");
   assert(&TargetSCC.getOuterRefSCC() == this &&
          "Target must be in this RefSCC.");
 
   // Set the edge kind.
   SourceN.setEdgeKind(TargetN.getFunction(), Edge::Ref);
 
   // If this call edge is just connecting two separate SCCs within this RefSCC,
   // there is nothing to do.
   if (&SourceSCC != &TargetSCC) {
 #ifndef NDEBUG
     // Check that the RefSCC is still valid.
     verify();
 #endif
-    return;
+    return make_range(SCCs.end(), SCCs.end());
   }
 
   // Otherwise we are removing a call edge from a single SCC. This may break
   // the cycle. In order to compute the new set of SCCs, we need to do a small
   // DFS over the nodes within the SCC to form any sub-cycles that remain as
   // distinct SCCs and compute a postorder over the resulting SCCs.
   //
   // However, we specially handle the target node. The target node is known to
#endif
   // old SCC from the mapping.
   for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
     SCCIndices[SCCs[Idx]] = Idx;
 
 #ifndef NDEBUG
   // We're done. Check the validity on our way out.
   verify();
 #endif
+
+  return make_range(SCCs.begin() + OldIdx,
+                    SCCs.begin() + OldIdx + NewSCCs.size());
 }
 
 void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,
                                                      Node &TargetN) {
   assert(!SourceN[TargetN].isCall() && "Must start with a ref edge!");
 
   assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
   assert(G->lookupRefSCC(TargetN) != this &&
#endif
 
   // Now erase all but the root's SCCs.
   SCCs.erase(remove_if(SCCs,
                        [&](SCC *C) {
                          return PostOrderMapping.lookup(&*C->begin()) !=
                                 RootPostOrderNumber;
                        }),
              SCCs.end());
+  SCCIndices.clear();
+  for (int i = 0, Size = SCCs.size(); i < Size; ++i)
+    SCCIndices[SCCs[i]] = i;
 
 #ifndef NDEBUG
   // Now we need to reconnect the current (root) SCC to the graph. We do this
   // manually because we can special case our leaf handling and detect errors.
   bool IsLeaf = true;
 #endif
   for (SCC *C : SCCs)
     for (Node &N : *C) {

llvm/trunk/lib/Passes/PassBuilder.cpp

 public:
   struct Result {};
   Result run(Module &, ModuleAnalysisManager &) { return Result(); }
   static StringRef name() { return "NoOpModuleAnalysis"; }
 };
 
 /// \brief No-op CGSCC pass which does nothing.
 struct NoOpCGSCCPass {
-  PreservedAnalyses run(LazyCallGraph::SCC &C,
-                        CGSCCAnalysisManager &) {
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &,
+                        LazyCallGraph &, CGSCCUpdateResult &UR) {
     return PreservedAnalyses::all();
   }
   static StringRef name() { return "NoOpCGSCCPass"; }
 };
 
 /// \brief No-op CGSCC analysis.
 class NoOpCGSCCAnalysis : public AnalysisInfoMixin<NoOpCGSCCAnalysis> {
   friend AnalysisInfoMixin<NoOpCGSCCAnalysis>;
   static char PassID;
 
 public:
   struct Result {};
-  Result run(LazyCallGraph::SCC &, CGSCCAnalysisManager &) {
+  Result run(LazyCallGraph::SCC &, CGSCCAnalysisManager &, LazyCallGraph &G) {
     return Result();
   }
   static StringRef name() { return "NoOpCGSCCAnalysis"; }
 };
 
 /// \brief No-op function pass which does nothing.
 struct NoOpFunctionPass {
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &) {
#define CGSCC_PASS(NAME, CREATE_PASS)                                          \
   if (Name == NAME) {                                                          \
     CGPM.addPass(CREATE_PASS);                                                 \
     return true;                                                               \
   }
 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)                                      \
   if (Name == "require<" NAME ">") {                                           \
     CGPM.addPass(RequireAnalysisPass<                                          \
                  std::remove_reference<decltype(CREATE_PASS)>::type,           \
-                 LazyCallGraph::SCC>());                                       \
+                 LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,    \
+                 CGSCCUpdateResult &>());                                      \
     return true;                                                               \
   }                                                                            \
   if (Name == "invalidate<" NAME ">") {                                        \
     CGPM.addPass(InvalidateAnalysisPass<                                       \
                  std::remove_reference<decltype(CREATE_PASS)>::type>());       \
     return true;                                                               \
   }
 #include "PassRegistry.def"

llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp

static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
 
   // Every call was to a non-recursive function other than this function, and
   // we have no indirect recursion as the SCC size is one. This function cannot
   // recurse.
   return setDoesNotRecurse(*F);
 }
 
 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
-                                                  CGSCCAnalysisManager &AM) {
+                                                  CGSCCAnalysisManager &AM,
+                                                  LazyCallGraph &CG,
+                                                  CGSCCUpdateResult &) {
   FunctionAnalysisManager &FAM =
-      AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
+      AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 
   // We pass a lambda into functions to wire them up to the analysis manager
   // for getting function analyses.
   auto AARGetter = [&](Function &F) -> AAResults & {
     return FAM.getResult<AAManager>(F);
   };
 
   // Fill SCCNodes with the elements of the SCC. Also track whether there are

llvm/trunk/test/Other/cgscc-iterate-function-mutation.ll

+; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs,function(simplify-cfg))' -S < %s | FileCheck %s
+
+declare void @readnone() readnone
+declare void @unknown()
+declare void @reference_function_pointer(void()*) readnone
+
+; The @test1_* set of functions checks that when we mutate functions with
+; simplify-cfg to delete call edges and this ends up splitting both the SCCs
+; and the RefSCCs that those functions are in, we re-run the CGSCC passes to
+; observe the refined call graph structure.
+
+; CHECK: define void @test1_a() {
+define void @test1_a() {
+  call void @test1_b1()
+  call void @test1_b2()
+  call void @test1_b3()
+  call void @test1_b4()
+  ret void
+}
+
+; CHECK: define void @test1_b1() #0 {
+define void @test1_b1() {
+  call void @readnone()
+  ret void
+}
+
+; CHECK: define void @test1_b2() #0 {
+define void @test1_b2() {
+  call void @readnone()
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test1_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: define void @test1_b3() {
+define void @test1_b3() {
+  call void @unknown()
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test1_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: define void @test1_b4() #0 {
+define void @test1_b4() {
+  call void @readnone()
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test1_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+
+; The @test2_* set of functions provide similar checks to @test1_* but only
+; splitting the SCCs while leaving the RefSCC intact. This is accomplished by
+; having dummy ref edges to the root function.
+
+; CHECK: define void @test2_a() {
+define void @test2_a() {
+  call void @test2_b1()
+  call void @test2_b2()
+  call void @test2_b3()
+  call void @test2_b4()
+  ret void
+}
+
+; CHECK: define void @test2_b1() #0 {
+define void @test2_b1() {
+  call void @readnone()
+  ret void
+}
+
+; CHECK: define void @test2_b2() #0 {
+define void @test2_b2() {
+  call void @reference_function_pointer(void()* @test2_a)
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test2_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: define void @test2_b3() {
+define void @test2_b3() {
+  call void @reference_function_pointer(void()* @test2_a)
+  call void @unknown()
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test2_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: define void @test2_b4() #0 {
+define void @test2_b4() {
+  call void @reference_function_pointer(void()* @test2_a)
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test2_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+
+; The @test3_* set of functions are the same challenge as @test1_* but with
+; multiple layers that have to be traversed in the correct order instead of
+; a single node.
+
+; CHECK: define void @test3_a() {
+define void @test3_a() {
+  call void @test3_b11()
+  call void @test3_b21()
+  call void @test3_b31()
+  call void @test3_b41()
+  ret void
+}
+
+; CHECK: define void @test3_b11() #0 {
+define void @test3_b11() {
+  call void @test3_b12()
+  ret void
+}
+
+; CHECK: define void @test3_b12() #0 {
+define void @test3_b12() {
+  call void @test3_b13()
+  ret void
+}
+
+; CHECK: define void @test3_b13() #0 {
+define void @test3_b13() {
+  call void @readnone()
+  ret void
+}
+
+; CHECK: define void @test3_b21() #0 {
+define void @test3_b21() {
+  call void @test3_b22()
+  ret void
+}
+
+; CHECK: define void @test3_b22() #0 {
+define void @test3_b22() {
+  call void @test3_b23()
+  ret void
+}
+
+; CHECK: define void @test3_b23() #0 {
+define void @test3_b23() {
+  call void @readnone()
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test3_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: define void @test3_b31() {
+define void @test3_b31() {
+  call void @test3_b32()
+  ret void
+}
+
+; CHECK: define void @test3_b32() {
+define void @test3_b32() {
+  call void @test3_b33()
+  ret void
+}
+
+; CHECK: define void @test3_b33() {
+define void @test3_b33() {
+  call void @unknown()
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test3_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: define void @test3_b41() #0 {
+define void @test3_b41() {
+  call void @test3_b42()
+  ret void
+}
+
+; CHECK: define void @test3_b42() #0 {
+define void @test3_b42() {
+  call void @test3_b43()
+  ret void
+}
+
+; CHECK: define void @test3_b43() #0 {
+define void @test3_b43() {
+  call void @readnone()
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test3_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+
+; The @test4_* functions exercise the same core challenge as the @test2_*
+; functions, but again include long chains instead of single nodes and ensure
+; we traverse the chains in the correct order.
+
+; CHECK: define void @test4_a() {
+define void @test4_a() {
+  call void @test4_b11()
+  call void @test4_b21()
+  call void @test4_b31()
+  call void @test4_b41()
+  ret void
+}
+
+; CHECK: define void @test4_b11() #0 {
+define void @test4_b11() {
+  call void @test4_b12()
+  ret void
+}
+
+; CHECK: define void @test4_b12() #0 {
+define void @test4_b12() {
+  call void @test4_b13()
+  ret void
+}
+
+; CHECK: define void @test4_b13() #0 {
+define void @test4_b13() {
+  call void @readnone()
+  ret void
+}
+
+; CHECK: define void @test4_b21() #0 {
+define void @test4_b21() {
+  call void @test4_b22()
+  ret void
+}
+
+; CHECK: define void @test4_b22() #0 {
+define void @test4_b22() {
+  call void @test4_b23()
+  ret void
+}
+
+; CHECK: define void @test4_b23() #0 {
+define void @test4_b23() {
+  call void @reference_function_pointer(void()* @test4_a)
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test4_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: define void @test4_b31() {
+define void @test4_b31() {
+  call void @test4_b32()
+  ret void
+}
+
+; CHECK: define void @test4_b32() {
+define void @test4_b32() {
+  call void @test4_b33()
+  ret void
+}
+
+; CHECK: define void @test4_b33() {
+define void @test4_b33() {
+  call void @reference_function_pointer(void()* @test4_a)
+  call void @unknown()
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test4_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: define void @test4_b41() #0 {
+define void @test4_b41() {
+  call void @test4_b42()
+  ret void
+}
+
+; CHECK: define void @test4_b42() #0 {
+define void @test4_b42() {
+  call void @test4_b43()
+  ret void
+}
+
+; CHECK: define void @test4_b43() #0 {
+define void @test4_b43() {
+  call void @reference_function_pointer(void()* @test4_a)
+  br i1 false, label %dead, label %exit
+
+dead:
+  call void @test4_a()
+  br label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: attributes #0 = { readnone }

llvm/trunk/test/Other/cgscc-observe-devirt.ll

+; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs)' -S < %s | FileCheck %s --check-prefix=BEFORE
+; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs,function(gvn))' -S < %s | FileCheck %s --check-prefix=AFTER
+;
+; Also check that adding an extra CGSCC pass after the function update but
+; without requiring the outer manager to iterate doesn't break any invariant.
+; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs,function(gvn),function-attrs)' -S < %s | FileCheck %s --check-prefix=AFTER2
+
+declare void @readnone() readnone
+declare void @unknown()
+
+; The @test1_* functions check that when we refine an indirect call to a direct
+; call, even if it doesn't change the call graph structure, we revisit the SCC
+; passes to reflect the more precise information.
+; FIXME: Currently, this isn't implemented in the new pass manager and so we
+; only get this with AFTER2, not with AFTER.
+
+; BEFORE: define void @test1_a() {
+; AFTER: define void @test1_a() {
+; AFTER2: define void @test1_a() {
+define void @test1_a() {
+  %fptr = alloca void()*
+  store void()* @unknown, void()** %fptr
+  %f = load void()*, void()** %fptr
+  call void %f()
+  ret void
+}
+
+; BEFORE: define void @test1_b() {
+; AFTER: define void @test1_b() {
+; AFTER2: define void @test1_b() #0 {
+define void @test1_b() {
+  %fptr = alloca void()*
+  store void()* @readnone, void()** %fptr
+  %f = load void()*, void()** %fptr
+  call void %f()
+  ret void
+}
+
+; The @test2_* checks that if we refine an indirect call to a direct call and
+; in the process change the very structure of the call graph we also revisit
+; that component of the graph and do so in an up-to-date fashion.
+
+; BEFORE: define void @test2_a1() {
+; AFTER: define void @test2_a1() {
+; AFTER2: define void @test2_a1() {
+define void @test2_a1() {
+  %fptr = alloca void()*
+  store void()* @test2_b2, void()** %fptr
+  store void()* @test2_b1, void()** %fptr
+  %f = load void()*, void()** %fptr
+  call void %f()
+  ret void
+}
+
+; BEFORE: define void @test2_b1() {
+; AFTER: define void @test2_b1() {
+; AFTER2: define void @test2_b1() {
+define void @test2_b1() {
+  call void @unknown()
+  call void @test2_a1()
+  ret void
+}
+
+; BEFORE: define void @test2_a2() {
+; AFTER: define void @test2_a2() #0 {
+; AFTER2: define void @test2_a2() #0 {
+define void @test2_a2() {
+  %fptr = alloca void()*
+  store void()* @test2_b1, void()** %fptr
+  store void()* @test2_b2, void()** %fptr
+  %f = load void()*, void()** %fptr
+  call void %f()
+  ret void
+}
+
+; BEFORE: define void @test2_b2() {
+; AFTER: define void @test2_b2() #0 {
+; AFTER2: define void @test2_b2() #0 {
+define void @test2_b2() {
+  call void @readnone()
+  call void @test2_a2()
+  ret void
+}
+
+
+; The @test3_* set of functions exercise a case where running function passes
+; introduces a new post-order relationship that was not present originally and
+; makes sure we walk across the SCCs in that order.
+
+; CHECK: define void @test3_a() {
+define void @test3_a() {
+  call void @test3_b1()
+  call void @test3_b2()
+  call void @test3_b3()
+  call void @unknown()
+  ret void
+}
+
+; CHECK: define void @test3_b1() #0 {
+define void @test3_b1() {
+  %fptr = alloca void()*
+  store void()* @test3_a, void()** %fptr
+  store void()* @readnone, void()** %fptr
+  %f = load void()*, void()** %fptr
+  call void %f()
+  ret void
+}
+
+; CHECK: define void @test3_b2() #0 {
+define void @test3_b2() {
+  %fptr = alloca void()*
+  store void()* @test3_a, void()** %fptr
+  store void()* @test3_b2, void()** %fptr
+  store void()* @test3_b3, void()** %fptr
+  store void()* @test3_b1, void()** %fptr
+  %f = load void()*, void()** %fptr
+  call void %f()
+  ret void
+}
+
+; CHECK: define void @test3_b3() #0 {
+define void @test3_b3() {
+  %fptr = alloca void()*
+  store void()* @test3_a, void()** %fptr
+  store void()* @test3_b2, void()** %fptr
+  store void()* @test3_b3, void()** %fptr
+  store void()* @test3_b1, void()** %fptr
+  %f = load void()*, void()** %fptr
+  call void %f()
+  ret void
+}
+
+; CHECK: attributes #0 = { readnone }

llvm/trunk/test/Other/new-pass-manager.ll

 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes='cgscc(no-op-cgscc)' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-CGSCC-PASS
 ; CHECK-CGSCC-PASS: Starting llvm::Module pass manager run
 ; CHECK-CGSCC-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor
 ; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
 ; CHECK-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-CGSCC-PASS-NEXT: Running an SCC pass across the RefSCC: [(foo)]
-; CHECK-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
-; CHECK-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run
+; CHECK-CGSCC-PASS-NEXT: Finished CGSCC pass manager run
 ; CHECK-CGSCC-PASS-NEXT: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes=no-op-function %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-FUNCTION-PASS
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes='function(no-op-function)' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-FUNCTION-PASS

 ; CHECK-NO-VERIFY: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager \
 ; RUN:     -passes='require<no-op-module>,cgscc(require<no-op-cgscc>,function(require<no-op-function>))' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-ANALYSES
 ; CHECK-ANALYSES: Starting llvm::Module pass manager run
 ; CHECK-ANALYSES: Running pass: RequireAnalysisPass
 ; CHECK-ANALYSES: Running analysis: NoOpModuleAnalysis
-; CHECK-ANALYSES: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-ANALYSES: Starting CGSCC pass manager run
 ; CHECK-ANALYSES: Running pass: RequireAnalysisPass
 ; CHECK-ANALYSES: Running analysis: NoOpCGSCCAnalysis
 ; CHECK-ANALYSES: Starting llvm::Function pass manager run
 ; CHECK-ANALYSES: Running pass: RequireAnalysisPass
 ; CHECK-ANALYSES: Running analysis: NoOpFunctionAnalysis
 
 ; Make sure no-op passes that preserve all analyses don't even try to do any
 ; analysis invalidation.

 ; RUN:     -passes='require<no-op-module>,module(require<no-op-module>,cgscc(require<no-op-cgscc>,function(require<no-op-function>,invalidate<all>,require<no-op-function>),require<no-op-cgscc>),require<no-op-module>),require<no-op-module>' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-INVALIDATE-ALL-CG
 ; CHECK-INVALIDATE-ALL-CG: Starting llvm::Module pass manager run
 ; CHECK-INVALIDATE-ALL-CG: Running pass: RequireAnalysisPass
 ; CHECK-INVALIDATE-ALL-CG: Running analysis: NoOpModuleAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Starting llvm::Module pass manager run
 ; CHECK-INVALIDATE-ALL-CG: Running pass: RequireAnalysisPass
 ; CHECK-INVALIDATE-ALL-CG-NOT: Running analysis: NoOpModuleAnalysis
-; CHECK-INVALIDATE-ALL-CG: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-INVALIDATE-ALL-CG: Starting CGSCC pass manager run
 ; CHECK-INVALIDATE-ALL-CG: Running pass: RequireAnalysisPass
 ; CHECK-INVALIDATE-ALL-CG: Running analysis: NoOpCGSCCAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Starting llvm::Function pass manager run
 ; CHECK-INVALIDATE-ALL-CG: Running pass: RequireAnalysisPass
 ; CHECK-INVALIDATE-ALL-CG: Running analysis: NoOpFunctionAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Running pass: InvalidateAllAnalysesPass
 ; CHECK-INVALIDATE-ALL-CG: Invalidating analysis: NoOpFunctionAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Running pass: RequireAnalysisPass
 ; CHECK-INVALIDATE-ALL-CG: Running analysis: NoOpFunctionAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Finished llvm::Function pass manager run
 ; CHECK-INVALIDATE-ALL-CG-NOT: Running analysis: NoOpFunctionAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Invalidating analysis: NoOpCGSCCAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Running pass: RequireAnalysisPass
 ; CHECK-INVALIDATE-ALL-CG: Running analysis: NoOpCGSCCAnalysis
-; CHECK-INVALIDATE-ALL-CG: Finished llvm::LazyCallGraph::SCC pass manager run
+; CHECK-INVALIDATE-ALL-CG: Finished CGSCC pass manager run
 ; CHECK-INVALIDATE-ALL-CG-NOT: Invalidating analysis: NoOpCGSCCAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Invalidating analysis: NoOpModuleAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Running pass: RequireAnalysisPass
 ; CHECK-INVALIDATE-ALL-CG: Running analysis: NoOpModuleAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Finished llvm::Module pass manager run
 ; CHECK-INVALIDATE-ALL-CG-NOT: Invalidating analysis: NoOpModuleAnalysis
 ; CHECK-INVALIDATE-ALL-CG: Running pass: RequireAnalysisPass
 ; CHECK-INVALIDATE-ALL-CG-NOT: Running analysis: NoOpModuleAnalysis

 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes='cgscc(repeat<3>(no-op-cgscc))' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-REPEAT-CGSCC-PASS
 ; CHECK-REPEAT-CGSCC-PASS: Starting llvm::Module pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running an SCC pass across the RefSCC: [(foo)]
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: RepeatedPass
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished CGSCC pass manager run
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished CGSCC pass manager run
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run
-; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished CGSCC pass manager run
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes='function(repeat<3>(no-op-function))' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-REPEAT-FUNCTION-PASS
 ; CHECK-REPEAT-FUNCTION-PASS: Starting llvm::Module pass manager run
 ; CHECK-REPEAT-FUNCTION-PASS-NEXT: Running pass: ModuleToFunctionPassAdaptor
 ; CHECK-REPEAT-FUNCTION-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>

llvm/trunk/test/Other/pass-pipeline-parsing.ll

 ; RUN:     | FileCheck %s --check-prefix=CHECK-UNBALANCED10
 ; CHECK-UNBALANCED10: unable to parse pass pipeline description
 
 ; RUN: opt -disable-output -debug-pass-manager \
 ; RUN:     -passes=no-op-cgscc,no-op-cgscc %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-TWO-NOOP-CG
 ; CHECK-TWO-NOOP-CG: Starting llvm::Module pass manager run
 ; CHECK-TWO-NOOP-CG: Running pass: ModuleToPostOrderCGSCCPassAdaptor
-; CHECK-TWO-NOOP-CG: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-TWO-NOOP-CG: Starting CGSCC pass manager run
 ; CHECK-TWO-NOOP-CG: Running pass: NoOpCGSCCPass
 ; CHECK-TWO-NOOP-CG: Running pass: NoOpCGSCCPass
-; CHECK-TWO-NOOP-CG: Finished llvm::LazyCallGraph::SCC pass manager run
+; CHECK-TWO-NOOP-CG: Finished CGSCC pass manager run
 ; CHECK-TWO-NOOP-CG: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager \
 ; RUN:     -passes='module(function(no-op-function),cgscc(no-op-cgscc,function(no-op-function),no-op-cgscc),function(no-op-function))' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-NESTED-MP-CG-FP
 ; CHECK-NESTED-MP-CG-FP: Starting llvm::Module pass manager run
 ; CHECK-NESTED-MP-CG-FP: Starting llvm::Module pass manager run
 ; CHECK-NESTED-MP-CG-FP: Running pass: ModuleToFunctionPassAdaptor
 ; CHECK-NESTED-MP-CG-FP: Starting llvm::Function pass manager run
 ; CHECK-NESTED-MP-CG-FP: Running pass: NoOpFunctionPass
 ; CHECK-NESTED-MP-CG-FP: Finished llvm::Function pass manager run
 ; CHECK-NESTED-MP-CG-FP: Running pass: ModuleToPostOrderCGSCCPassAdaptor
-; CHECK-NESTED-MP-CG-FP: Starting llvm::LazyCallGraph::SCC pass manager run
+; CHECK-NESTED-MP-CG-FP: Starting CGSCC pass manager run
 ; CHECK-NESTED-MP-CG-FP: Running pass: NoOpCGSCCPass
 ; CHECK-NESTED-MP-CG-FP: Running pass: CGSCCToFunctionPassAdaptor
 ; CHECK-NESTED-MP-CG-FP: Starting llvm::Function pass manager run
 ; CHECK-NESTED-MP-CG-FP: Running pass: NoOpFunctionPass
 ; CHECK-NESTED-MP-CG-FP: Finished llvm::Function pass manager run
 ; CHECK-NESTED-MP-CG-FP: Running pass: NoOpCGSCCPass
-; CHECK-NESTED-MP-CG-FP: Finished llvm::LazyCallGraph::SCC pass manager run
+; CHECK-NESTED-MP-CG-FP: Finished CGSCC pass manager run
 ; CHECK-NESTED-MP-CG-FP: Running pass: ModuleToFunctionPassAdaptor
 ; CHECK-NESTED-MP-CG-FP: Starting llvm::Function pass manager run
 ; CHECK-NESTED-MP-CG-FP: Running pass: NoOpFunctionPass
 ; CHECK-NESTED-MP-CG-FP: Finished llvm::Function pass manager run
 ; CHECK-NESTED-MP-CG-FP: Finished llvm::Module pass manager run
 ; CHECK-NESTED-MP-CG-FP: Finished llvm::Module pass manager run
 
 ; RUN: opt -disable-output -debug-pass-manager \

llvm/trunk/unittests/Analysis/CGSCCPassManagerTest.cpp

struct Result {
     int FunctionCount;
   };
 
   static void *ID() { return (void *)&PassID; }
   static StringRef name() { return "TestSCCAnalysis"; }
 
   TestSCCAnalysis(int &Runs) : Runs(Runs) {}
 
-  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM) {
+  Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &) {
     ++Runs;
     return Result(C.size());
   }
 
 private:
   static char PassID;
 
   int &Runs;
struct TestSCCPass {
   TestSCCPass(int &RunCount, int &AnalyzedInstrCount,
               int &AnalyzedSCCFunctionCount, int &AnalyzedModuleFunctionCount,
               bool OnlyUseCachedResults = false)
       : RunCount(RunCount), AnalyzedInstrCount(AnalyzedInstrCount),
         AnalyzedSCCFunctionCount(AnalyzedSCCFunctionCount),
         AnalyzedModuleFunctionCount(AnalyzedModuleFunctionCount),
         OnlyUseCachedResults(OnlyUseCachedResults) {}
 
-  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM) {
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
     ++RunCount;
 
     const ModuleAnalysisManager &MAM =
-        AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C).getManager();
+        AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager();
     FunctionAnalysisManager &FAM =
-        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
+        AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
     if (TestModuleAnalysis::Result *TMA =
             MAM.getCachedResult<TestModuleAnalysis>(
                 *C.begin()->getFunction().getParent()))
       AnalyzedModuleFunctionCount += TMA->FunctionCount;
 
     if (OnlyUseCachedResults) {
       // Hack to force the use of the cached interface.
       if (TestSCCAnalysis::Result *AR = AM.getCachedResult<TestSCCAnalysis>(C))
         AnalyzedSCCFunctionCount += AR->FunctionCount;
       for (LazyCallGraph::Node &N : C)
         if (TestFunctionAnalysis::Result *FAR =
                 FAM.getCachedResult<TestFunctionAnalysis>(N.getFunction()))
           AnalyzedInstrCount += FAR->InstructionCount;
     } else {
       // Typical path just runs the analysis as needed.
-      TestSCCAnalysis::Result &AR = AM.getResult<TestSCCAnalysis>(C);
+      TestSCCAnalysis::Result &AR = AM.getResult<TestSCCAnalysis>(C, CG);
       AnalyzedSCCFunctionCount += AR.FunctionCount;
       for (LazyCallGraph::Node &N : C) {
         TestFunctionAnalysis::Result &FAR =
             FAM.getResult<TestFunctionAnalysis>(N.getFunction());
         AnalyzedInstrCount += FAR.InstructionCount;
 
         // Just ensure we get the immutable results.
         (void)FAM.getResult<TestImmutableFunctionAnalysis>(N.getFunction());