[NewPM] Fix a nasty bug with analysis invalidation in the new PM.

[chandlerc]

Summary

The issue here is that we actually allow CGSCC passes to mutate IR (and
therefore invalidate analyses) outside of the current SCC. At a minimum,
we need to support mutating parent and ancestor SCCs to support the
ArgumentPromotion pass which rewrites all calls to a function.

However, the analysis invalidation infrastructure is heavily based
around not needing to invalidate the same IR-unit at multiple levels.
With Loop passes for example, they don't invalidate other Loops. So we
need to customize how we handle CGSCC invalidation. Doing this without
gratuitously re-running analyses is even harder. I've avoided most of
these by using an out-of-band preserved set to accumulate the cross-SCC
invalidation, but it still isn't perfect in the case of re-visiting the
same SCC repeatedly *but* it coming off the worklist. Unclear how
important this use case really is, but I wanted to call it out.

Another wrinkle is that in order for this to successfully propagate to
function analyses, we have to make sure we have a proxy from the SCC to
the Function level. That requires pre-creating the necessary proxy.

The motivating test case now works cleanly and is added for
ArgumentPromotion.

[chandlerc]

Fix up the CHECK lines in my new test case.

[philip.pfaffe]

This makes complete sense to me. There is currently no way to invalidate an analysis for a specific IRUnit instance only, right? So not preserving an analysis cross-SCC will invalidate it for all?

[chandlerc]

In D59869#1444442, @philip.pfaffe wrote:

This makes complete sense to me. There is currently no way to invalidate an analysis for a specific IRUnit instance only, right? So not preserving an analysis cross-SCC will invalidate it for all?

Correct.

[philip.pfaffe]

Okay. Any plans to improve it? On the other hand, I'm not sure about the impact. We'll probably have to get some profile data first.

Anyways, this patch looks good!

[wmi]

Thanks for working on the patch which will fix several build failures found internally! I believe the patch is already after a lot of balancing, and here are just some questions out of curiousity.

In the patch, I saw two targets to achieve: T1. lazy invalidation. T2. maintain pass-manager driven invalidation scheme (mentioned in a comment). And I saw two compromises made, C1. If a SCC changes its IR and invalidate some analysis, the invalidated pass will be propagated not only to its SCC parent, but also to its grandparent and grandgrandparent ... or even SCC not being an ancestor on the call graph if only it is visited after the current SCC. C2. For CGSCC pass other than ArgumentPromotion, like inliner pass, even if it will not touch the IR other than the current SCC like what ArgumentPromotion does, it will still invalidate the analysis of other SCCs after this change.

lazy invalidation seems to be achieved using the UR.CrossSCCPA set, so the purpose of the compromises seems mainly to maintain passmanager driven invalidation scheme. From my understanding, the scheme means invalidation initiated by pass manager instead of single IR Unit, and pass manager can only invalidate the analysis of the IR managed by itself.

I am wondering for C1, Can we have multiple CrossSCCPA instead of one (like a map, every SCC has its own CrossSCCPA) so if only the current SCC hasn't made any change, it can propagate preservedall to its parent SCC. For relieving C2, it seems to require returning PreservedAnalysesCrossSCC instead of PreservedAnalyses for each SCC pass so each pass can set PreservedAnalysesCrossSCC accordingly. That seems not very easy with little churn.

[chandlerc]

In D59869#1445062, @philip.pfaffe wrote:

Anyways, this patch looks good!

Thanks, will land it momentarily, but I do want to dig into your questions and Wei's questions here.

Okay. Any plans to improve it? On the other hand, I'm not sure about the impact. We'll probably have to get some profile data first.

I don't see any really good ways of implementing this. See below, as I think Wei was also hitting on this, and I'll try to answer in a bit of detail.

But yes, if we find that this causes a serious drop in available cached results, we can investigate alternatives. My suspicion is that *this* won't be the real problem though, and so I'm not too worried.

In D59869#1445186, @wmi wrote:

Thanks for working on the patch which will fix several build failures found internally! I believe the patch is already after a lot of balancing, and here are just some questions out of curiousity.

In the patch, I saw two targets to achieve: T1. lazy invalidation. T2. maintain pass-manager driven invalidation scheme (mentioned in a comment). And I saw two compromises made, C1. If a SCC changes its IR and invalidate some analysis, the invalidated pass will be propagated not only to its SCC parent, but also to its grandparent and grandgrandparent ... or even SCC not being an ancestor on the call graph if only it is visited after the current SCC. C2. For CGSCC pass other than ArgumentPromotion, like inliner pass, even if it will not touch the IR other than the current SCC like what ArgumentPromotion does, it will still invalidate the analysis of other SCCs after this change.

lazy invalidation seems to be achieved using the UR.CrossSCCPA set, so the purpose of the compromises seems mainly to maintain passmanager driven invalidation scheme. From my understanding, the scheme means invalidation initiated by pass manager instead of single IR Unit, and pass manager can only invalidate the analysis of the IR managed by itself.

I am wondering for C1, Can we have multiple CrossSCCPA instead of one (like a map, every SCC has its own CrossSCCPA) so if only the current SCC hasn't made any change, it can propagate preservedall to its parent SCC.

This seems really appealing, and I thought a bunch about it. I hit some really difficult problems though and don't really see a way to make it work. That said, if you see something I'm missing, please say so. It would certainly be convenient.

So, first, let's think about how to do this while still being lazy -- that is, the pass itself doesn't *eagerly* invalidate anything. Also, I'll use ArgumentPromotion as an example (with the caller being mutated while processing the callee SCC).

What we could do is, as you suggest have a map. The next question is, what key would we put in the map? It turns out this is ... a really tricky question. Let's assume that the caller is in an SCC (that was the case we hit in the wild certainly). In that case, we could put the caller's SCC into the map as a key. This creates a bunch of new problems unfortunately. The inliner or another pass may merge this SCC with other SCCs or split it appart. We'll have to update the map every time, and it may be somewhat complex to do the update. But it is worse than that, the function in question may *move* between SCCs. So we'll also have to be able to think about that form of update. Maybe we can solve this, but it already started to look very unappealing to me in terms of complexity and cost. Then I started thinking about the case where the caller isn't in an SCC *at all* because we haven't built the callers part of the call graph yet! So we would also need a two-level map so that we can add invalidation into SCCs that we form in the future from functions that have not yet been visited.

Ultimately, storing enough information to do the invalidation for individual IR units seems definitely do-able, but not trivial. I think we'd need to have a decent amount of infrastructure to update everything and make sure it stayed in sync as the structure changes. This is a big reason why I didn't try harder to address the issue in this direction. We can go down the road if we end up in practice *needing* this kind of preservation, but it does seem quite difficult.

A different approach would be to invalidate things eagerly. This removes any need to track things, which is nice. But it forces each pass that mutates code outside of its SCC to know all the details of invalidation. It also will perform that invalidation at a surprising step when nothing else would naturally be operating on that unit of IR. It also removes the ability to coalesce multiple invalidation events into a single one. That also seemed quite a high cost.

So this is how I ended up with the compromise here. It seemed like a basically minimal burden to get the most important preservation while still keeping things correct.

For relieving C2, it seems to require returning PreservedAnalysesCrossSCC instead of PreservedAnalyses for each SCC pass so each pass can set PreservedAnalysesCrossSCC accordingly. That seems not very easy with little churn

This is an interestingly different compromise to tackle. I don't quite understand your suggestion (changing the return type of the pass seems like it would be fairly disruptive from an API / code perspective). But I think the idea here is very straight forward. The way I would do it is to have a synthetic "analysis" ID that can be preserved which symbolically represents preserving all other SCCs' analyses. Then, before updating the CrossSCCPA, we could check if that symbolic analysis is preserved. This would allow the inliner to mark in its pass PA.preserve<SomeSymbolicNameHere>() and avoid any extraneous invalidation.

I'm fine adding this if we want it, but it wasn't clear there was any realistic advantage. I don't really expect that many cached analysis results to exist for parent functions. It seemed like the case we found in the wild was much more of the edge case. But if you or any others are seeing more significant caching here, then yes, we should add some symbolic analysis so that we can preserve it.

It also has the nice effect of remaining conservatively correct -- a pass will have to explicitly think about the fact that it is not mutating other SCCs before setting this.

[wmi]

Thanks for the detailed answer for how to make the choices!

[fedor.sergeev]

Pushed this through our java-based fuzzer, no problems found so far
(though our use of SCC-based passes is very limited).

[wenlei]

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

832–835 ↗

(On Diff #192549)

@chandlerc, was it intentional to have overlap/redundancy between UR.UpdatedC and CWorklist?

Asking because we ran into a pathological case where that redundancy and the one extra pass over a SCC caused significant compile time increase (by couple hours), when we switch a service to use new pass manager. There was no SCC mutation between the last two runs, and we run over that same SCC twice only because of the redundancy. (The one extra last run over it caused its size to grow exponentially, and that slowed down downstream passes)

I tried to tweak this to avoid that redundancy between the two - that resolved the compile time regression from newpm, and all llvm tests passed too (except the analysis counts for CGSCCPassManagerTest needs update, which is expected I think). But wanted to check if that's a sensible approach..

[wenlei]

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

832–835 ↗

(On Diff #192549)

Here's an attempt/rfc to address this FIXME and the compile time issue we saw with new pass manager: D80589

llvm/include/llvm/Analysis/CGSCCPassManager.h

struct CGSCCUpdateResult {
   /// 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;
 
+  /// Preserved analyses across SCCs.
+  ///
+  /// We specifically want to allow CGSCC passes to mutate ancestor IR
+  /// (changing both the CG structure and the function IR itself). However,
+  /// this means we need to take special care to correctly mark what analyses
+  /// are preserved *across* SCCs. We have to track this out-of-band here
+  /// because within the main `PassManeger` infrastructure we need to mark
+  /// everything within an SCC as preserved in order to avoid repeatedly
+  /// invalidating the same analyses as we unnest pass managers and adaptors.
+  /// So we track the cross-SCC version of the preserved analyses here from any
+  /// code that does direct invalidation of SCC analyses, and then use it
+  /// whenever we move forward in the post-order walk of SCCs before running
+  /// passes over the new SCC.
+  PreservedAnalyses CrossSCCPA;
+
   /// A hacky area where the inliner can retain history about inlining
   /// decisions that mutated the call graph's SCC structure in order to avoid
   /// infinite inlining. See the comments in the inliner's CG update logic.
   ///
   /// FIXME: Keeping this here seems like a big layering issue, we should look
   /// for a better technique.
   SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
       &InlinedInternalEdges;
public:
 
   ModuleToPostOrderCGSCCPassAdaptor &
   operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   /// Runs the CGSCC pass across every SCC in the module.
-  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;
-
-    SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
-        InlinedInternalEdges;
-
-    CGSCCUpdateResult UR = {RCWorklist,          CWorklist, InvalidRefSCCSet,
-                            InvalidSCCSet,       nullptr,   nullptr,
-                            InlinedInternalEdges};
-
-    // Request PassInstrumentation from analysis manager, will use it to run
-    // instrumenting callbacks for the passes later.
-    PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
-
-    PreservedAnalyses PA = PreservedAnalyses::all();
-    CG.buildRefSCCs();
-    for (auto RCI = CG.postorder_ref_scc_begin(),
-              RCE = CG.postorder_ref_scc_end();
-         RCI != RCE;) {
-      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.
-      //
-      // We also eagerly increment the iterator to the next position because
-      // the CGSCC passes below may delete the current RefSCC.
-      RCWorklist.insert(&*RCI++);
-
-      do {
-        LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
-        if (InvalidRefSCCSet.count(RC)) {
-          LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
-          continue;
-        }
-
-        assert(CWorklist.empty() &&
-               "Should always start with an empty SCC worklist");
-
-        LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
-                          << "\n");
-
-        // Push the initial SCCs in reverse post-order as we'll pop off the
-        // back and so see this in post-order.
-        for (LazyCallGraph::SCC &C : llvm::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)) {
-            LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
-            continue;
-          }
-          if (&C->getOuterRefSCC() != RC) {
-            LLVM_DEBUG(dbgs()
-                       << "Skipping an SCC that is now part of some other "
-                          "RefSCC...\n");
-            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;
-
-            // Check the PassInstrumentation's BeforePass callbacks before
-            // running the pass, skip its execution completely if asked to
-            // (callback returns false).
-            if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
-              continue;
-
-            PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
-
-            if (UR.InvalidatedSCCs.count(C))
-              PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
-            else
-              PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
-
-            // Update the SCC and RefSCC if necessary.
-            C = UR.UpdatedC ? UR.UpdatedC : C;
-            RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
-
-            // If the CGSCC pass wasn't able to provide a valid updated SCC,
-            // the current SCC may simply need to be skipped if invalid.
-            if (UR.InvalidatedSCCs.count(C)) {
-              LLVM_DEBUG(dbgs()
-                         << "Skipping invalidated root or island SCC!\n");
-              break;
-            }
-            // Check that we didn't miss any update scenario.
-            assert(C->begin() != C->end() && "Cannot have an empty SCC!");
-
-            // 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.
-            CGAM.invalidate(*C, 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.
-            if (UR.UpdatedC)
-              LLVM_DEBUG(dbgs()
-                         << "Re-running SCC passes after a refinement of the "
-                            "current SCC: "
-                         << *UR.UpdatedC << "\n");
-
-            // Note that both `C` and `RC` may at this point refer to deleted,
-            // invalid SCC and RefSCCs respectively. But we will short circuit
-            // the processing when we check them in the loop above.
-          } while (UR.UpdatedC);
-        } while (!CWorklist.empty());
-
-        // We only need to keep internal inlined edge information within
-        // a RefSCC, clear it to save on space and let the next time we visit
-        // any of these functions have a fresh start.
-        InlinedInternalEdges.clear();
-      } while (!RCWorklist.empty());
-    }
-
-    // By definition we preserve the call garph, all SCC analyses, and the
-    // analysis proxies by handling them above and in any nested pass managers.
-    PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
-    PA.preserve<LazyCallGraphAnalysis>();
-    PA.preserve<CGSCCAnalysisManagerModuleProxy>();
-    PA.preserve<FunctionAnalysisManagerModuleProxy>();
-    return PA;
-  }
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
 private:
   CGSCCPassT Pass;
 };
 
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename CGSCCPassT>

 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename PassT>
 DevirtSCCRepeatedPass<PassT> createDevirtSCCRepeatedPass(PassT Pass,
                                                          int MaxIterations) {
   return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations);
 }
 
+// Out-of-line implementation details for templates below this point.
+
+template <typename CGSCCPassT>
+PreservedAnalyses
+ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>::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;
+
+  SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
+      InlinedInternalEdges;
+
+  CGSCCUpdateResult UR = {
+      RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
+      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges};
+
+  // Request PassInstrumentation from analysis manager, will use it to run
+  // instrumenting callbacks for the passes later.
+  PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
+
+  PreservedAnalyses PA = PreservedAnalyses::all();
+  CG.buildRefSCCs();
+  for (auto RCI = CG.postorder_ref_scc_begin(),
+            RCE = CG.postorder_ref_scc_end();
+       RCI != RCE;) {
+    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.
+    //
+    // We also eagerly increment the iterator to the next position because
+    // the CGSCC passes below may delete the current RefSCC.
+    RCWorklist.insert(&*RCI++);
+
+    do {
+      LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
+      if (InvalidRefSCCSet.count(RC)) {
+        LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
+        continue;
+      }
+
+      assert(CWorklist.empty() &&
+             "Should always start with an empty SCC worklist");
+
+      LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
+                        << "\n");
+
+      // Push the initial SCCs in reverse post-order as we'll pop off the
+      // back and so see this in post-order.
+      for (LazyCallGraph::SCC &C : llvm::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)) {
+          LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
+          continue;
+        }
+        if (&C->getOuterRefSCC() != RC) {
+          LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
+                               "RefSCC...\n");
+          continue;
+        }
+
+        // Ensure we can proxy analysis updates from from the CGSCC analysis
+        // manager into the Function analysis manager by getting a proxy here.
+        // FIXME: This seems like a bit of a hack. We should find a cleaner
+        // or more costructive way to ensure this happens.
+        (void)CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG);
+
+        // Each time we visit a new SCC pulled off the worklist,
+        // a transformation of a child SCC may have also modified this parent
+        // and invalidated analyses. So we invalidate using the update record's
+        // cross-SCC preserved set. This preserved set is intersected by any
+        // CGSCC pass that handles invalidation (primarily pass managers) prior
+        // to marking its SCC as preserved. That lets us track everything that
+        // might need invalidation across SCCs without excessive invalidations
+        // on a single SCC.
+        //
+        // This essentially allows SCC passes to freely invalidate analyses
+        // of any ancestor SCC. If this becomes detrimental to successfully
+        // caching analyses, we could force each SCC pass to manually
+        // invalidate the analyses for any SCCs other than themselves which
+        // are mutated. However, that seems to lose the robustness of the
+        // pass-manager driven invalidation scheme.
+        //
+        // FIXME: This is redundant in one case -- the top of the worklist may
+        // *also* be the same SCC we just ran over (and invalidated for). In
+        // that case, we'll end up doing a redundant invalidation here as
+        // a consequence.
+        CGAM.invalidate(*C, UR.CrossSCCPA);
+
+        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;
+
+          // Check the PassInstrumentation's BeforePass callbacks before
+          // running the pass, skip its execution completely if asked to
+          // (callback returns false).
+          if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
+            continue;
+
+          PreservedAnalyses PassPA = Pass.run(*C, CGAM, CG, UR);
+
+          if (UR.InvalidatedSCCs.count(C))
+            PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
+          else
+            PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
+
+          // Update the SCC and RefSCC if necessary.
+          C = UR.UpdatedC ? UR.UpdatedC : C;
+          RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
+
+          // If the CGSCC pass wasn't able to provide a valid updated SCC,
+          // the current SCC may simply need to be skipped if invalid.
+          if (UR.InvalidatedSCCs.count(C)) {
+            LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
+            break;
+          }
+          // Check that we didn't miss any update scenario.
+          assert(C->begin() != C->end() && "Cannot have an empty SCC!");
+
+          // 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.
+          CGAM.invalidate(*C, PassPA);
+
+          // Then intersect the preserved set so that invalidation of module
+          // analyses will eventually occur when the module pass completes.
+          // Also intersect with the cross-SCC preserved set to capture any
+          // cross-SCC invalidation.
+          UR.CrossSCCPA.intersect(PassPA);
+          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.
+          if (UR.UpdatedC)
+            LLVM_DEBUG(dbgs()
+                       << "Re-running SCC passes after a refinement of the "
+                          "current SCC: "
+                       << *UR.UpdatedC << "\n");
+
+          // Note that both `C` and `RC` may at this point refer to deleted,
+          // invalid SCC and RefSCCs respectively. But we will short circuit
+          // the processing when we check them in the loop above.
+        } while (UR.UpdatedC);
+      } while (!CWorklist.empty());
+
+      // We only need to keep internal inlined edge information within
+      // a RefSCC, clear it to save on space and let the next time we visit
+      // any of these functions have a fresh start.
+      InlinedInternalEdges.clear();
+    } while (!RCWorklist.empty());
+  }
+
+  // By definition we preserve the call garph, all SCC analyses, and the
+  // analysis proxies by handling them above and in any nested pass managers.
+  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
+  PA.preserve<LazyCallGraphAnalysis>();
+  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+  PA.preserve<FunctionAnalysisManagerModuleProxy>();
+  return PA;
+}
+
 // Clear out the debug logging macro.
 #undef DEBUG_TYPE
 
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H

llvm/lib/Analysis/CGSCCPassManager.cpp

for (auto &Pass : Passes) {
 
     // FIXME: Historically, the pass managers all called the LLVM context's
     // yield function here. We don't have a generic way to acquire the
     // context and it isn't yet clear what the right pattern is for yielding
     // in the new pass manager so it is currently omitted.
     // ...getContext().yield();
   }
 
+  // Before we mark all of *this* SCC's analyses as preserved below, intersect
+  // this with the cross-SCC preserved analysis set. This is used to allow
+  // CGSCC passes to mutate ancestor SCCs and still trigger proper invalidation
+  // for them.
+  UR.CrossSCCPA.intersect(PA);
+
   // Invalidation was handled after each pass in the above loop for the current
   // SCC. Therefore, the remaining analysis results in the AnalysisManager are
   // preserved. We mark this with a set so that we don't need to inspect each
   // one individually.
   PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
 
   if (DebugLogging)
     dbgs() << "Finished CGSCC pass manager run.\n";

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

 ; 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<{{.*(CGSCCAnalysisManager|AnalysisManager<.*LazyCallGraph::SCC.*>).*}},{{.*}}Module>
 ; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*(FunctionAnalysisManager|AnalysisManager<.*Function.*>).*}},{{.*}}Module>
 ; CHECK-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-CGSCC-PASS-NEXT: Running analysis: TargetLibraryAnalysis
+; CHECK-CGSCC-PASS-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-CGSCC-PASS-NEXT: Running analysis: PassInstrumentationAnalysis
+; CHECK-CGSCC-PASS-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph::SCC{{.*}}>
 ; CHECK-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
 ; 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:     -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<{{.*(CGSCCAnalysisManager|AnalysisManager<.*LazyCallGraph::SCC.*>).*}},{{.*}}Module>
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*(FunctionAnalysisManager|AnalysisManager<.*Function.*>).*}},{{.*}}Module>
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: TargetLibraryAnalysis
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: PassInstrumentationAnalysis
+; CHECK-REPEAT-CGSCC-PASS-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph::SCC{{.*}}>
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: RepeatedPass
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Starting CGSCC pass manager run
 ; CHECK-REPEAT-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
 ; 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 CGSCC pass manager run

llvm/test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}GlobalsAA
 ; CHECK-O-NEXT: Running analysis: GlobalsAA
 ; CHECK-O-NEXT: Running analysis: CallGraphAnalysis
 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}ProfileSummaryAnalysis
 ; CHECK-O-NEXT: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}LazyCallGraph{{.*}}>
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
+; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running analysis: PassInstrumentationAnalysis
+; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph::SCC{{.*}}>
 ; CHECK-O-NEXT: Starting CGSCC pass manager run.
 ; CHECK-O-NEXT: Running pass: InlinerPass
-; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph{{.*}}>
-; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running pass: PostOrderFunctionAttrsPass
 ; CHECK-O3-NEXT: Running pass: ArgumentPromotionPass
 ; CHECK-O-NEXT: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-O-NEXT: Running pass: SpeculativeExecutionPass

llvm/test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}GlobalsAA
 ; CHECK-O-NEXT: Running analysis: GlobalsAA
 ; CHECK-O-NEXT: Running analysis: CallGraphAnalysis
 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}ProfileSummaryAnalysis
 ; CHECK-PRELINK-O-NEXT: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}LazyCallGraph{{.*}}>
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
+; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running analysis: PassInstrumentationAnalysis
+; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph::SCC{{.*}}>
 ; CHECK-O-NEXT: Starting CGSCC pass manager run.
 ; CHECK-O-NEXT: Running pass: InlinerPass
-; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph{{.*}}>
-; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running pass: PostOrderFunctionAttrsPass
 ; CHECK-O3-NEXT: Running pass: ArgumentPromotionPass
 ; CHECK-O-NEXT: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-O-NEXT: Running pass: SpeculativeExecutionPass

llvm/test/Transforms/ArgumentPromotion/invalidation.ll

+; Check that when argument promotion changes a function in some parent node of
+; the call graph, any analyses that happened to be cached for that function are
+; actually invalidated. We are using `demanded-bits` here because when printed
+; it will end up caching a value for every instruction, making it easy to
+; detect the instruction-level changes that will fail here. With improper
+; invalidation this will crash in the second printer as it tries to reuse
+; now-invalid demanded bits.
+;
+; RUN: opt < %s -passes='function(print<demanded-bits>),cgscc(argpromotion,function(print<demanded-bits>))' -S | FileCheck %s
+
+@G = constant i32 0
+
+define internal i32 @a(i32* %x) {
+; CHECK-LABEL: define internal i32 @a(
+entry:
+  %v = load i32, i32* %x
+  ret i32 %v
+; CHECK: ret i32
+}
+
+define i32 @b() {
+; CHECK-LABEL: define i32 @b()
+entry:
+  %v = call i32 @a(i32* @G)
+  ret i32 %v
+}
+
+define i32 @c() {
+; CHECK-LABEL: define i32 @c()
+entry:
+  %v1 = call i32 @a(i32* @G)
+  %v2 = call i32 @b()
+  %result = add i32 %v1, %v2
+  ret i32 %result
+}
+

llvm/test/Transforms/Inline/cgscc-incremental-invalidate.ll

 ; Test for a subtle bug when computing analyses during inlining and mutating
 ; the SCC structure. Without care, this can fail to invalidate analyses.
 ;
 ; RUN: opt < %s -passes='cgscc(inline,function(verify<domtree>))' -debug-pass-manager -S 2>&1 | FileCheck %s
 
 ; First we check that the passes run in the way we expect. Otherwise this test
 ; may stop testing anything.
 ;
 ; CHECK-LABEL: Starting llvm::Module pass manager run.
 ; CHECK: Running pass: InlinerPass on (test1_f, test1_g, test1_h)
-; CHECK: Running analysis: FunctionAnalysisManagerCGSCCProxy on (test1_f, test1_g, test1_h)
 ; CHECK: Running analysis: DominatorTreeAnalysis on test1_f
 ; CHECK: Running analysis: DominatorTreeAnalysis on test1_g
 ; CHECK: Invalidating all non-preserved analyses for: (test1_f)
 ; CHECK: Invalidating all non-preserved analyses for: test1_f
 ; CHECK: Invalidating analysis: DominatorTreeAnalysis on test1_f
 ; CHECK: Invalidating analysis: LoopAnalysis on test1_f
 ; CHECK: Invalidating analysis: BranchProbabilityAnalysis on test1_f
 ; CHECK: Invalidating analysis: BlockFrequencyAnalysis on test1_f

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

TEST_F(CGSCCPassManagerTest, TestAnalysisInvalidationCGSCCUpdate) {
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM3)));
   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM4)));
   MPM.run(*M, MAM);
 
   // We run over four SCCs the first time. But then we split an SCC into three.
-  // And then we merge those three back into one.
-  EXPECT_EQ(4 + 3 + 1, SCCAnalysisRuns);
+  // And then we merge those three back into one. However, this also
+  // invalidates all three SCCs further down in the PO walk.
+  EXPECT_EQ(4 + 3 + 1 + 3, SCCAnalysisRuns);
   // The module analysis pass should be run three times.
   EXPECT_EQ(3, ModuleAnalysisRuns);
   // We run over four SCCs the first time. Then over the two new ones. Then the
   // entire module is invalidated causing a full run over all seven. Then we
-  // fold three SCCs back to one, and then run over the whole module again.
-  EXPECT_EQ(4 + 2 + 7 + 1 + 4, IndirectSCCAnalysisRuns);
-  EXPECT_EQ(4 + 2 + 7 + 1 + 4, DoublyIndirectSCCAnalysisRuns);
+  // fold three SCCs back to one, re-compute for it and the two SCCs above it
+  // in the graph, and then run over the whole module again.
+  EXPECT_EQ(4 + 2 + 7 + 1 + 3 + 4, IndirectSCCAnalysisRuns);
+  EXPECT_EQ(4 + 2 + 7 + 1 + 3 + 4, DoublyIndirectSCCAnalysisRuns);
 
   // First we run over all six functions. Then we re-run it over three when we
   // split their SCCs. Then we re-run over the whole module. Then we re-run
-  // over three functions merged back into a single SCC, and then over the
-  // whole module again.
-  EXPECT_EQ(6 + 3 + 6 + 3 + 6, FunctionAnalysisRuns);
+  // over three functions merged back into a single SCC, then those three
+  // functions again, the two functions in SCCs above it in the graph, and then
+  // over the whole module again.
+  EXPECT_EQ(6 + 3 + 6 + 3 + 3 + 2 + 6, FunctionAnalysisRuns);
 
   // Re run the function analysis over the entire module, and then re-run it
   // over the `(h3, h1, h2)` SCC due to invalidation. Then we re-run it over
   // the entire module, then the three functions merged back into a single SCC,
-  // and then over the whole module.
-  EXPECT_EQ(6 + 3 + 6 + 3 + 6, IndirectFunctionAnalysisRuns);
+  // those three functions again, then the two functions in SCCs above it in
+  // the graph, and then over the whole module.
+  EXPECT_EQ(6 + 3 + 6 + 3 + 3 + 2 + 6, IndirectFunctionAnalysisRuns);
 }
 }