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
@@ -138,6 +138,10 @@
     return CallsExternalNode.get();
   }
 
+  /// Old node has been deleted, and New is to be used in its place, update the
+  /// ExternalCallingNode.
+  void ReplaceExternalCallEdge(CallGraphNode *Old, CallGraphNode *New);
+
   //===---------------------------------------------------------------------
   // Functions to keep a call graph up to date with a function that has been
   // modified.
diff --git a/llvm/lib/Analysis/CallGraph.cpp b/llvm/lib/Analysis/CallGraph.cpp
--- a/llvm/lib/Analysis/CallGraph.cpp
+++ b/llvm/lib/Analysis/CallGraph.cpp
@@ -127,6 +127,16 @@
 LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); }
 #endif
 
+void CallGraph::ReplaceExternalCallEdge(CallGraphNode *Old,
+                                        CallGraphNode *New) {
+  for (auto &CR : ExternalCallingNode->CalledFunctions)
+    if (CR.second == Old) {
+      CR.second->DropRef();
+      CR.second = New;
+      CR.second->AddRef();
+    }
+}
+
 // removeFunctionFromModule - Unlink the function from this module, returning
 // it.  Because this removes the function from the module, the call graph node
 // is destroyed.  This is only valid if the function does not call any other
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
@@ -117,10 +117,10 @@
   ReplacedFunctions.insert(&OldFn);
   if (CG) {
     // Update the call graph for the newly promoted function.
-    // CG->spliceFunction(&OldFn, &NewFn);
     CallGraphNode *OldCGN = (*CG)[&OldFn];
     CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
     NewCGN->stealCalledFunctionsFrom(OldCGN);
+    CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
 
     // And update the SCC we're iterating as well.
     CGSCC->ReplaceNode(OldCGN, NewCGN);
diff --git a/llvm/unittests/IR/LegacyPassManagerTest.cpp b/llvm/unittests/IR/LegacyPassManagerTest.cpp
--- a/llvm/unittests/IR/LegacyPassManagerTest.cpp
+++ b/llvm/unittests/IR/LegacyPassManagerTest.cpp
@@ -467,7 +467,7 @@
 
       Function* func_test3 = Function::Create(
         /*Type=*/FuncTy_0,
-        /*Linkage=*/GlobalValue::ExternalLinkage,
+        /*Linkage=*/GlobalValue::InternalLinkage,
         /*Name=*/"test3", mod);
       func_test3->setCallingConv(CallingConv::C);
       AttributeList func_test3_PAL;
@@ -571,6 +571,9 @@
             BasicBlock::Create(Context, "return", func_test4, nullptr);
 
         // Block entry (label_entry_11)
+        auto *AI = new AllocaInst(func_test3->getType(), 0, "func3ptr",
+                                  label_entry_11);
+        new StoreInst(func_test3, AI, label_entry_11);
         BranchInst::Create(label_bb, label_entry_11);
 
         // Block bb (label_bb)
@@ -589,6 +592,8 @@
       unsigned NumSCCs = 0;
       unsigned NumFns = 0;
       bool SetupWorked = true;
+      unsigned NumExtCalledBefore = 0;
+      unsigned NumExtCalledAfter = 0;
 
       CallGraphUpdater CGU;
 
@@ -600,6 +605,10 @@
 
         CGPass::run();
 
+        CallGraph &CG = const_cast<CallGraph &>(SCMM.getCallGraph());
+        CallGraphNode *ExtCallingNode = CG.getExternalCallingNode();
+        NumExtCalledBefore = ExtCallingNode->size();
+
         if (SCMM.size() <= 1)
           return false;
 
@@ -610,6 +619,7 @@
         Function *Test2aF = M->getFunction("test2a");
         Function *Test2bF = M->getFunction("test2b");
         Function *Test3F = M->getFunction("test3");
+
         auto InSCC = [&](Function *Fn) {
           return llvm::any_of(SCMM, [Fn](CallGraphNode *CGN) {
             return CGN->getFunction() == Fn;
@@ -624,16 +634,41 @@
         if (!CI || CI->getCalledFunction() != Test2aF)
           return SetupWorked = false;
 
-        CI->setCalledFunction(Test3F);
+        // Create a replica of test3 and just move the blocks there.
+        Function *Test3FRepl = Function::Create(
+            /*Type=*/Test3F->getFunctionType(),
+            /*Linkage=*/GlobalValue::InternalLinkage,
+            /*Name=*/"test3repl", Test3F->getParent());
+        while (!Test3F->empty()) {
+          BasicBlock &BB = Test3F->front();
+          BB.removeFromParent();
+          BB.insertInto(Test3FRepl);
+        }
+
+        CGU.initialize(CG, SCMM);
 
-        CGU.initialize(const_cast<CallGraph &>(SCMM.getCallGraph()), SCMM);
+        // Replace test3 with the replica. This is legal as it is actually
+        // internal and the "capturing use" is not really capturing anything.
+        CGU.replaceFunctionWith(*Test3F, *Test3FRepl);
+        Test3F->replaceAllUsesWith(Test3FRepl);
+
+        // Rewrite the call in test1 to point to the replica of 3 not test2.
+        CI->setCalledFunction(Test3FRepl);
+
+        // Delete test2a and test2b and reanalyze 1 as we changed calls inside.
         CGU.removeFunction(*Test2aF);
         CGU.removeFunction(*Test2bF);
         CGU.reanalyzeFunction(*Test1F);
+
         return true;
       }
 
-      bool doFinalization(CallGraph &CG) override { return CGU.finalize(); }
+      bool doFinalization(CallGraph &CG) override {
+        CGU.finalize();
+        // We removed test2 and replaced the internal test3.
+        NumExtCalledAfter = CG.getExternalCallingNode()->size();
+        return true;
+      }
     };
 
     TEST(PassManager, CallGraphUpdater0) {
@@ -652,6 +687,8 @@
       ASSERT_EQ(P->NumSCCs, 3U);
       ASSERT_EQ(P->NumFns, 5U);
       ASSERT_EQ(M->getFunctionList().size(), 3U);
+      ASSERT_EQ(P->NumExtCalledBefore, /* test1, 2a, 2b, 3, 4 */ 5U);
+      ASSERT_EQ(P->NumExtCalledAfter, /* test1, 3repl, 4 */ 3U);
     }
   }
 }