Index: include/llvm/Analysis/CGSCCPassManager.h
===================================================================
--- include/llvm/Analysis/CGSCCPassManager.h
+++ include/llvm/Analysis/CGSCCPassManager.h
@@ -26,53 +26,76 @@
 
 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;
+
+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;
 
-class CGInvalidationProxyAnalysis : public AnalysisInfoMixin<CGInvalidationProxyAnalysis> {
-public:
-  struct Result {
-    LazyCallGraph::UpdateResult UR;
-
-    bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA) {
-      // This isn't a traditional analysis pass, it is just a cache of
-      // information to convey between SCC passes and the adaptor walking SCCs.
-      return false;
-    }
-  };
-
-  Result run(LazyCallGraph::SCC &C, AnalysisManager<LazyCallGraph::SCC> &AM) {
-    return Result();
-  }
-
-private:
-  friend AnalysisInfoMixin<CGInvalidationProxyAnalysis>;
-  static char PassID;
+/// 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 rammifications 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 {
+  SmallSetVector<LazyCallGraph::RefSCC *, 1> &RCWorklist;
+  SmallSetVector<LazyCallGraph::SCC *, 1> &CWorklist;
+  SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs;
+  SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs;
+
+  LazyCallGraph::SCC *UpdatedC;
 };
 
 /// \brief The core module pass which does a post-order walk of the SCCs and
@@ -119,18 +142,20 @@
 
     // We keep worklists to allow us to push more work onto the pass manager as
     // the passes are run.
-    SmallVector<LazyCallGraph::RefSCC *, 1> RCWorklist;
-    SmallVector<LazyCallGraph::SCC *, 1> CWorklist;
+    SmallSetVector<LazyCallGraph::RefSCC *, 1> RCWorklist;
+    SmallSetVector<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};
+
     PreservedAnalyses PA = PreservedAnalyses::all();
     for (LazyCallGraph::RefSCC &InitialRC : CG.postorder_ref_sccs()) {
       assert(RCWorklist.empty() && "Should always start with an empty RefSCC worklist");
-      RCWorklist.push_back(&InitialRC);
+      RCWorklist.insert(&InitialRC);
 
       do {
         LazyCallGraph::RefSCC &RC = *RCWorklist.pop_back_val();
@@ -143,49 +168,31 @@
         // 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.push_back(&C);
+          CWorklist.insert(&C);
 
         do {
           LazyCallGraph::SCC &C = *CWorklist.pop_back_val();
           if (InvalidSCCSet.count(&C))
             continue;
 
-          // Before we run the pass over this SCC, clear the invalidation
-          // proxy so that we can collect any call graph invalidation
-          // information provided by the pass.
-          LazyCallGraph::UpdateResult &UR =
-              CGAM.getResult<CGInvalidationProxyAnalysis>(C).UR;
-          assert(UR.empty() &&
-                 "Didn't start with a clean invalidation result!");
+          PreservedAnalyses PassPA = Pass.run(C, CGAM, CG, UR);
 
-          PreservedAnalyses PassPA = Pass.run(C, CGAM);
+          // The pass may have mutated the call graph and so we need reference
+          // a potentially newly updated SCC.
+          LazyCallGraph::SCC &UpdatedC = *(UR.UpdatedC ? UR.UpdatedC : &C);
 
-          // 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.
-          PassPA = CGAM.invalidate(C, std::move(PassPA));
+          // 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(UpdatedC, 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));
 
-          // We also need to handle invalidated and newly added SCCs and
-          // RefSCCs.
-          for (auto *InvalidRC : UR.InvalidatedRefSCCs)
-            InvalidRefSCCSet.insert(InvalidRC);
-          for (auto *InvalidC : UR.InvalidatedSCCs) {
-            InvalidSCCSet.insert(InvalidC);
-            // FIXME: need to clear this SCC from the analysis manager.
-          }
-          // Note that we append in reverse order as the worklist is consumed
-          // from the end.
-          RCWorklist.append(UR.NewRefSCCs.rbegin(), UR.NewRefSCCs.rend());
-          CWorklist.append(UR.NewSCCs.rbegin(), UR.NewSCCs.rend());
-          UR.clear();
         } while (!CWorklist.empty());
-
       } while (!RCWorklist.empty());
     }
 
@@ -210,9 +217,9 @@
 }
 
 extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager,
-                                                LazyCallGraph::SCC>;
+                                                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>;
@@ -220,6 +227,16 @@
 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);
+
 /// \brief Adaptor that maps from a SCC to its functions.
 ///
 /// Designed to allow composition of a FunctionPass(Manager) and
@@ -251,25 +268,48 @@
   }
 
   /// \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;
 
     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);
+      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
@@ -278,12 +318,8 @@
     // incrementally above.
     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 
-    // Do a full re-scan of the functions in this SCC in order to update the
-    // call graph based on any function-local changes made.
-    auto &CG = *AM.getCachedResult<LazyCallGraphAnalysis>(C);
-    LazyCallGraph::UpdateResult &UR =
-        AM.getCachedResult<CGInvalidationProxyAnalysis>(C)->UR;
-    CG.updateSCC(C, UR);
+    // We've also ensured that we updated the call graph along the way.
+    PA.preserve<LazyCallGraphAnalysis>();
 
     return PA;
   }
Index: include/llvm/Analysis/LazyCallGraph.h
===================================================================
--- include/llvm/Analysis/LazyCallGraph.h
+++ include/llvm/Analysis/LazyCallGraph.h
@@ -509,7 +509,8 @@
     /// 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);
+    iterator_range<iterator> switchInternalEdgeToRef(Node &SourceN,
+                                                     Node &TargetN);
 
     /// Make an existing outgoing ref edge into a call edge.
     ///
@@ -761,37 +762,31 @@
   ///@}
 
   ///@{
-  /// \name Generic SCC Update API
+  /// \name Static helpers for code doing updates to the call graph.
   ///
-  /// This provides generic top-level update APIs that operate after the RefSCC
-  /// traversal has started.
-
-  struct UpdateResult {
-    SmallVector<RefSCC *, 4> InvalidatedRefSCCs;
-    SmallVector<SCC *, 4> InvalidatedSCCs;
-    SmallVector<RefSCC *, 4> NewRefSCCs;
-    SmallVector<SCC *, 4> NewSCCs;
-
-    bool empty() const {
-      return InvalidatedRefSCCs.empty() && InvalidatedSCCs.empty() &&
-             NewRefSCCs.empty() && NewSCCs.empty();
+  /// 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));
     }
 
-    void clear() {
-      InvalidatedRefSCCs.clear();
-      InvalidatedSCCs.clear();
-      NewRefSCCs.clear();
-      NewSCCs.clear();
-    }
-  };
-
-  /// Do a full re-scan of an SCC and update the call graph based upon any
-  /// function-local changes made to that SCC.
-  ///
-  /// FIXME: describe accurately the full constraints on this routine!
-  void updateSCC(SCC &C, UpdateResult &UR);
-
-  ///@}
+    ///@}
+}
 
 private:
   typedef SmallVectorImpl<Node *>::reverse_iterator node_stack_iterator;
Index: include/llvm/IR/PassManager.h
===================================================================
--- include/llvm/IR/PassManager.h
+++ include/llvm/IR/PassManager.h
@@ -519,12 +519,35 @@
     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();
Index: include/llvm/Transforms/IPO/FunctionAttrs.h
===================================================================
--- include/llvm/Transforms/IPO/FunctionAttrs.h
+++ include/llvm/Transforms/IPO/FunctionAttrs.h
@@ -30,7 +30,8 @@
 /// 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
Index: lib/Analysis/CGSCCPassManager.cpp
===================================================================
--- lib/Analysis/CGSCCPassManager.cpp
+++ lib/Analysis/CGSCCPassManager.cpp
@@ -8,17 +8,213 @@
 //===----------------------------------------------------------------------===//
 
 #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>;
+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>;
 }
+
+namespace {
+/// Helper function for \c updatecGAndAnalysisManagerForFunctionPass that can't
+/// be a lambda because it would need to be a generic lambda.
+template <typename SCCRangeT>
+LazyCallGraph::SCC *processNewSCCRange(const SCCRangeT &NewSCCRange,
+                                       LazyCallGraph &G, LazyCallGraph::Node &N,
+                                       LazyCallGraph::SCC *C,
+                                       CGSCCAnalysisManager &AM,
+                                       CGSCCUpdateResult &UR) {
+  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);
+
+  SCC *OldC = C;
+
+  // 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);
+  }
+  return C;
+}
+}
+
+LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
+    LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
+    CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) {
+  typedef LazyCallGraph::Node Node;
+  typedef LazyCallGraph::Edge Edge;
+  typedef LazyCallGraph::SCC SCC;
+  typedef LazyCallGraph::RefSCC RefSCC;
+
+  SCC *C = &InitialC;
+  RefSCC *RC = &C->getOuterRefSCC();
+  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> PromotedCallTargets;
+  SmallSetVector<Function *, 4> DemotedRefTargets;
+  for (BasicBlock &BB : F)
+    for (Instruction &I : BB) {
+      if (auto CS = CallSite(&I))
+        if (Function *Callee = CS.getCalledFunction()) {
+          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())
+            PromotedCallTargets.insert(Callee);
+        }
+
+      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) {
+        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())
+          DemotedRefTargets.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.isCall() ? Edge::Call : Edge::Ref});
+  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);
+      continue;
+    }
+
+    if (IsCall)
+      C = processNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G, N, C,
+                             AM, UR);
+
+    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.
+      UR.RCWorklist.insert(NewRefSCCs.rbegin(), NewRefSCCs.rend());
+      RC = &C->getOuterRefSCC();
+      assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!");
+    }
+  }
+
+  // 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 : DemotedRefTargets) {
+    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);
+      continue;
+    }
+
+    // Otherwise we are switching an internal call edge to a ref edge. This
+    // may split up some SCCs.
+    C = processNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G, N, C, AM,
+                           UR);
+  }
+
+  // Now promote ref edges into call edges.
+  for (Function *CallTarget : PromotedCallTargets) {
+    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);
+      continue;
+    }
+
+    // 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.
+    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 valid 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);
+      }
+    }
+  }
+
+  // Record the current SCC for higher layers of the CGSCC pass
+  // manager now that all the updates have been applied.
+  UR.UpdatedC = C;
+
+  return *C;
+}
Index: lib/Analysis/LazyCallGraph.cpp
===================================================================
--- lib/Analysis/LazyCallGraph.cpp
+++ lib/Analysis/LazyCallGraph.cpp
@@ -40,24 +40,6 @@
   }
 }
 
-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));
-  }
-}
-
 LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F)
     : G(&G), F(F), DFSNumber(0), LowLink(0) {
   DEBUG(dbgs() << "  Adding functions called by '" << F.getName()
@@ -470,8 +452,8 @@
   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);
@@ -492,7 +474,7 @@
     // 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
@@ -659,6 +641,9 @@
   // 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,
@@ -1232,88 +1217,6 @@
   return SourceN.removeEdgeInternal(Target);
 }
 
-void LazyCallGraph::updateSCC(SCC &C, UpdateResult &UR) {
-  RefSCC &RC = C.getOuterRefSCC();
-  SmallVector<Constant *, 16> Worklist;
-  SmallSetVector<Function *, 4> NewCallTargets;
-  SmallSetVector<Function *, 4> PromotedCallTargets;
-  SmallSetVector<Function *, 4> NewRefTargets;
-  SmallSetVector<Function *, 4> DemotedRefTargets;
-  SmallPtrSet<Constant *, 16> Visited;
-
-  for (Node &N : C) {
-    Function &F = N.getFunction();
-
-    for (BasicBlock &BB : F)
-      for (Instruction &I : BB) {
-        if (auto CS = CallSite(&I))
-          if (Function *Callee = CS.getCalledFunction()) {
-            const Edge *E = N.lookup(*Callee);
-            if (!E)
-              NewCallTargets.insert(Callee);
-            else if (!E->isCall())
-              PromotedCallTargets.insert(Callee);
-          }
-
-        for (Value *Op : I.operand_values())
-          if (Constant *C = dyn_cast<Constant>(Op))
-            if (Visited.insert(C).second)
-              Worklist.push_back(C);
-
-        visitReferences(Worklist, Visited, [&](Function &Referee) {
-          const Edge *E = N.lookup(Referee);
-          if (!E)
-            NewRefTargets.insert(&Referee);
-          else if (E->isCall())
-            DemotedRefTargets.insert(&Referee);
-        });
-      }
-
-    for (Function *CallTarget : NewCallTargets) {
-      Node &TargetN = *lookup(*CallTarget);
-      SCC &TargetC = *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.insertOutgoingEdge(N, TargetN, Edge::Call);
-        continue;
-      }
-
-      // Otherwise we need to first insert a ref edge, and then convert it to
-      // a call edge. This may merge some SCCs, and we add those to the
-      // UpdateResult.
-      RC.insertInternalRefEdge(N, TargetN);
-
-      auto InvalidatedSCCs = RC.switchInternalEdgeToCall(N, TargetN);
-      UR.InvalidatedSCCs.append(InvalidatedSCCs.begin(), InvalidatedSCCs.end());
-    }
-
-    for (Function *CallTarget : PromotedCallTargets) {
-      Node &TargetN = *lookup(*CallTarget);
-      SCC &TargetC = *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);
-        continue;
-      }
-
-      // Otherwise we are switching an internal ref edgo to a call edge. This
-      // may merge some SCCs, and we add those to the UpdateResult.
-      auto InvalidatedSCCs = RC.switchInternalEdgeToCall(N, TargetN);
-      UR.InvalidatedSCCs.append(InvalidatedSCCs.begin(), InvalidatedSCCs.end());
-    }
-  }
-}
-
 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
   return *new (MappedN = BPA.Allocate()) Node(*this, F);
 }
Index: lib/Passes/PassBuilder.cpp
===================================================================
--- lib/Passes/PassBuilder.cpp
+++ lib/Passes/PassBuilder.cpp
@@ -125,7 +125,8 @@
 /// \brief No-op CGSCC pass which does nothing.
 struct NoOpCGSCCPass {
   PreservedAnalyses run(LazyCallGraph::SCC &C,
-                        AnalysisManager<LazyCallGraph::SCC> &) {
+                        CGSCCAnalysisManager &, LazyCallGraph &,
+                        CGSCCUpdateResult &UR) {
     return PreservedAnalyses::all();
   }
   static StringRef name() { return "NoOpCGSCCPass"; }
@@ -138,7 +139,7 @@
 
 public:
   struct Result {};
-  Result run(LazyCallGraph::SCC &, AnalysisManager<LazyCallGraph::SCC> &) {
+  Result run(LazyCallGraph::SCC &, CGSCCAnalysisManager &, LazyCallGraph &G) {
     return Result();
   }
   static StringRef name() { return "NoOpCGSCCAnalysis"; }
@@ -358,7 +359,8 @@
   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 ">") {                                        \
Index: lib/Transforms/IPO/FunctionAttrs.cpp
===================================================================
--- lib/Transforms/IPO/FunctionAttrs.cpp
+++ lib/Transforms/IPO/FunctionAttrs.cpp
@@ -991,12 +991,14 @@
 }
 
 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
-                                                  CGSCCAnalysisManager &AM) {
+                                                  CGSCCAnalysisManager &AM,
+                                                  LazyCallGraph &CG,
+                                                  CGSCCUpdateResult &) {
   Module &M = *C.begin()->getFunction().getParent();
   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();
 
   // FIXME: Need some way to make it more reasonable to assume that this is
   // always cached.
Index: unittests/Analysis/CGSCCPassManagerTest.cpp
===================================================================
--- unittests/Analysis/CGSCCPassManagerTest.cpp
+++ unittests/Analysis/CGSCCPassManagerTest.cpp
@@ -59,7 +59,7 @@
 
   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());
   }
@@ -149,13 +149,14 @@
         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()))
@@ -171,7 +172,7 @@
           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 =