diff --git a/llvm/include/llvm/Analysis/CallGraph.h b/llvm/include/llvm/Analysis/CallGraph.h
--- a/llvm/include/llvm/Analysis/CallGraph.h
+++ b/llvm/include/llvm/Analysis/CallGraph.h
@@ -61,6 +61,7 @@
 
 namespace llvm {
 
+class CallGraphUpdater;
 class CallGraphNode;
 class Module;
 class raw_ostream;
@@ -71,6 +72,8 @@
 ///
 /// The core call graph itself can also be updated to reflect changes to the IR.
 class CallGraph {
+  friend class CallGraphUpdater;
+
   Module &M;
 
   using FunctionMapTy =
diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h
--- a/llvm/include/llvm/Analysis/LazyCallGraph.h
+++ b/llvm/include/llvm/Analysis/LazyCallGraph.h
@@ -110,6 +110,8 @@
 /// it from the existing CallGraph. At some point, it is expected that this
 /// will be the only call graph and it will be renamed accordingly.
 class LazyCallGraph {
+  friend class CallGraphUpdater;
+
 public:
   class Node;
   class EdgeSequence;
@@ -327,6 +329,7 @@
   class Node {
     friend class LazyCallGraph;
     friend class LazyCallGraph::RefSCC;
+    friend class CallGraphUpdater;
 
   public:
     LazyCallGraph &getGraph() const { return *G; }
@@ -431,6 +434,7 @@
   class SCC {
     friend class LazyCallGraph;
     friend class LazyCallGraph::Node;
+    friend class CallGraphUpdater;
 
     RefSCC *OuterRefSCC;
     SmallVector<Node *, 1> Nodes;
diff --git a/llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h b/llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h
new file mode 100644
--- /dev/null
+++ b/llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h
@@ -0,0 +1,56 @@
+//===- CallGraphUpdater.h - A (lazy) call graph update helper ---*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file provides interfaces used to manipulate a call graph, regardless
+/// if it is a "old style" CallGraph or an "new style" LazyCallGraph.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_UTILS_GENERIC_CALL_GRAPH_H
+#define LLVM_ANALYSIS_UTILS_GENERIC_CALL_GRAPH_H
+
+#include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/LazyCallGraph.h"
+
+namespace llvm {
+
+/// Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph. This
+/// simplifies the interface and the call sites, e.g., new and old pass manager
+/// passes can share the same code.
+class CallGraphUpdater {
+  CallGraph *const CG = nullptr;
+  LazyCallGraph *const LCG = nullptr;
+  CGSCCAnalysisManager *AM = nullptr;
+  CGSCCUpdateResult *UR = nullptr;
+
+public:
+  CallGraphUpdater() {}
+  CallGraphUpdater(CallGraph &CG) : CG(&CG) {}
+  CallGraphUpdater(LazyCallGraph &LCG, CGSCCAnalysisManager &AM,
+                   CGSCCUpdateResult &UR)
+      : LCG(&LCG), AM(&AM), UR(&UR) {}
+
+  /// Remove \p Fn from the call graph.
+  void removeFunction(Function &Fn);
+
+  /// After an CG-SCC pass changes a function in ways that affect the call
+  /// graph, this method can be called to update it.
+  void reanalyzeFunction(Function &Fn);
+
+  /// If a new function was created by outlining, this method can be called
+  /// to update the call graph for the new function. Note that the old one
+  /// still needs to be re-analyzed or manually updated.
+  void registerOutlinedFunction(Function &NewFn,
+                                LazyCallGraph::SCC *SCC = nullptr);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_UTILS_GENERIC_CALL_GRAPH_H
diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt
--- a/llvm/lib/Transforms/Utils/CMakeLists.txt
+++ b/llvm/lib/Transforms/Utils/CMakeLists.txt
@@ -6,6 +6,7 @@
   BuildLibCalls.cpp
   BypassSlowDivision.cpp
   CallPromotionUtils.cpp
+  CallGraphUpdater.cpp
   CanonicalizeAliases.cpp
   CloneFunction.cpp
   CloneModule.cpp
diff --git a/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp b/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
new file mode 100644
--- /dev/null
+++ b/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
@@ -0,0 +1,53 @@
+//===- CallGraphUpdater.cpp - A (lazy) call graph update helper -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file provides interfaces used to manipulate a call graph, regardless
+/// if it is a "old style" CallGraph or an "new style" LazyCallGraph.
+///
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/CallGraphUpdater.h"
+
+using namespace llvm;
+
+void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
+  if (CG) {
+    CallGraphNode *OldCGN = (*CG)[&Fn];
+    CG->getExternalCallingNode()->removeAnyCallEdgeTo(OldCGN);
+    OldCGN->removeAllCalledFunctions();
+    CG->addToCallGraph(&Fn);
+  } else if (LCG) {
+    LazyCallGraph::Node &N = LCG->get(Fn);
+    LazyCallGraph::SCC *C = LCG->lookupSCC(N);
+    updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR);
+  }
+}
+
+void CallGraphUpdater::registerOutlinedFunction(Function &NewFn,
+                                                LazyCallGraph::SCC *SCC) {
+  if (CG) {
+    CG->addToCallGraph(&NewFn);
+  } else if (LCG) {
+    LazyCallGraph::Node &CGNode = LCG->get(NewFn);
+    CGNode.DFSNumber = CGNode.LowLink = -1;
+    CGNode.populate();
+    SCC->Nodes.push_back(&CGNode);
+    LCG->SCCMap[&CGNode] = SCC;
+    LCG->NodeMap[&NewFn] = &CGNode;
+  }
+}
+
+void CallGraphUpdater::removeFunction(Function &Fn) {
+  if (CG) {
+    CG->removeFunctionFromModule((*CG)[&Fn]);
+  } else if (LCG) {
+    llvm_unreachable("CallGraphUpdater::removeFunction not implemented for the "
+                     "lazy call graph yet.");
+  }
+}
diff --git a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
--- a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
+++ b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp
@@ -16,6 +16,7 @@
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/SourceMgr.h"
+#include "llvm/Transforms/Utils/CallGraphUpdater.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
@@ -1425,5 +1426,139 @@
   MPM.run(*M, MAM);
 }
 
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses4) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(f)")
+          return;
+
+
+        Function *FnF = M->getFunction("f");
+        Function *FnewF = Function::Create(FnF->getFunctionType(),
+                                           FnF->getLinkage(), "newF", *M);
+        BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
+        ReturnInst::Create(FnewF->getContext(), BB);
+
+        // Use the CallGraphUpdater to update the call graph for the new
+        // function.
+        CallGraphUpdater CGU(CG, AM, UR);
+        CGU.registerOutlinedFunction(*FnewF, &C);
+
+        // And insert a call to `newF`
+        Instruction *IP = &FnF->getEntryBlock().front();
+        (void)CallInst::Create(FnewF, {}, "", IP);
+
+        auto &FN = *llvm::find_if(
+            C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
+
+        ASSERT_NO_FATAL_FAILURE(
+            updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses5) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
+                                           CGSCCAnalysisManager &AM,
+                                           LazyCallGraph &CG,
+                                           CGSCCUpdateResult &UR) {
+    if (C.getName() != "(f)")
+      return;
+
+    Function *FnF = M->getFunction("f");
+    Function *FnewF =
+        Function::Create(FnF->getFunctionType(), FnF->getLinkage(), "newF", *M);
+    BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
+    ReturnInst::Create(FnewF->getContext(), BB);
+
+    // Use the CallGraphUpdater to update the call graph for the new
+    // function.
+    CallGraphUpdater CGU(CG, AM, UR);
+    CGU.registerOutlinedFunction(*FnewF, &C);
+
+    // And insert a call to `newF`
+    Instruction *IP = &FnF->getEntryBlock().front();
+    (void)CallInst::Create(FnewF, {}, "", IP);
+
+    auto &FN = *llvm::find_if(
+        C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
+
+    ASSERT_DEATH(updateCGAndAnalysisManagerForFunctionPass(CG, C, FN, AM, UR),
+                 "Any new calls should be modeled as");
+  }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses6) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(h3, h1, h2)")
+          return;
+
+        Function *FnX = M->getFunction("x");
+        Function *FnH1 = M->getFunction("h1");
+        Function *FnH2 = M->getFunction("h2");
+        Function *FnH3 = M->getFunction("h3");
+        ASSERT_NE(FnX, nullptr);
+        ASSERT_NE(FnH1, nullptr);
+        ASSERT_NE(FnH2, nullptr);
+        ASSERT_NE(FnH3, nullptr);
+
+        // And insert a call to `h1`, `h2`, and `h3`.
+        Instruction *IP = &FnH2->getEntryBlock().front();
+        (void)CallInst::Create(FnH1, {}, "", IP);
+        (void)CallInst::Create(FnH2, {}, "", IP);
+        (void)CallInst::Create(FnH3, {}, "", IP);
+
+        // Use the CallGraphUpdater to update the call graph for the new
+        // function.
+        CallGraphUpdater CGU(CG, AM, UR);
+        ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnH2));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
+TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses7) {
+  CGSCCPassManager CGPM(/*DebugLogging*/ true);
+  CGPM.addPass(LambdaSCCPassNoPreserve(
+      [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+          CGSCCUpdateResult &UR) {
+        if (C.getName() != "(f)")
+          return;
+
+        Function *FnF = M->getFunction("f");
+        Function *FnH2 = M->getFunction("h2");
+        ASSERT_NE(FnF, nullptr);
+        ASSERT_NE(FnH2, nullptr);
+
+        // And insert a call to `h2`
+        Instruction *IP = &FnF->getEntryBlock().front();
+        (void)CallInst::Create(FnH2, {}, "", IP);
+
+        // Use the CallGraphUpdater to update the call graph for the new
+        // function.
+        CallGraphUpdater CGU(CG, AM, UR);
+        ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnF));
+      }));
+
+  ModulePassManager MPM(/*DebugLogging*/ true);
+  MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+  MPM.run(*M, MAM);
+}
+
 #endif
 } // namespace
diff --git a/llvm/unittests/Analysis/CMakeLists.txt b/llvm/unittests/Analysis/CMakeLists.txt
--- a/llvm/unittests/Analysis/CMakeLists.txt
+++ b/llvm/unittests/Analysis/CMakeLists.txt
@@ -3,6 +3,7 @@
   AsmParser
   Core
   Support
+  TransformUtils
   )
 
 add_llvm_unittest(AnalysisTests