diff --git a/llvm/include/llvm/Analysis/CallGraphSCCPass.h b/llvm/include/llvm/Analysis/CallGraphSCCPass.h
--- a/llvm/include/llvm/Analysis/CallGraphSCCPass.h
+++ b/llvm/include/llvm/Analysis/CallGraphSCCPass.h
@@ -103,6 +103,10 @@
   /// Old node has been deleted, and New is to be used in its place.
   void ReplaceNode(CallGraphNode *Old, CallGraphNode *New);
 
+  /// DeleteNode - This informs the SCC and the pass manager that the specified
+  /// Old node has been deleted.
+  void DeleteNode(CallGraphNode *Old);
+
   using iterator = std::vector<CallGraphNode *>::const_iterator;
 
   iterator begin() const { return Nodes.begin(); }
diff --git a/llvm/lib/Analysis/CallGraphSCCPass.cpp b/llvm/lib/Analysis/CallGraphSCCPass.cpp
--- a/llvm/lib/Analysis/CallGraphSCCPass.cpp
+++ b/llvm/lib/Analysis/CallGraphSCCPass.cpp
@@ -562,6 +562,10 @@
   CGI->ReplaceNode(Old, New);
 }
 
+void CallGraphSCC::DeleteNode(CallGraphNode *Old) {
+  ReplaceNode(Old, /* New */ nullptr);
+}
+
 //===----------------------------------------------------------------------===//
 // CallGraphSCCPass Implementation
 //===----------------------------------------------------------------------===//
diff --git a/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp b/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
--- a/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
+++ b/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp
@@ -103,6 +103,10 @@
     DeadFunctionsInComdats.push_back(&DeadFn);
   else
     DeadFunctions.push_back(&DeadFn);
+
+  // For the old call graph we remove the function from the SCC right away.
+  if (CGSCC && !ReplacedFunctions.count(&DeadFn))
+    CGSCC->DeleteNode((*CG)[&DeadFn]);
 }
 
 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {