diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp
--- a/llvm/lib/Analysis/LazyCallGraph.cpp
+++ b/llvm/lib/Analysis/LazyCallGraph.cpp
@@ -1595,8 +1595,6 @@
 }
 
 LazyCallGraph::Node &LazyCallGraph::createNode(Function &F) {
-  assert(!lookup(F) && "node already exists");
-
   Node &N = get(F);
   NodeMap[&F] = &N;
   N.DFSNumber = N.LowLink = -1;
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
@@ -1735,29 +1735,58 @@
           if (!Call || Call->getCalledFunction()->getName() != "f")
             continue;
 
+          // "Demote" the 'f -> f' call edge to a ref edge.
+          // 1. Erase the call edge from 'f' to 'f'.
+          Call->eraseFromParent();
+          // 2. Insert a ref edge from 'f' to 'f'.
+          auto *FFRef = CastInst::CreatePointerCast(
+              &F, Type::getInt8PtrTy(F.getContext()), "f.ref",
+              &*F.begin()->begin());
+
           // Create a new function 'g'.
           auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
                                      F.getAddressSpace(), "g", F.getParent());
           BasicBlock::Create(F.getParent()->getContext(), "entry", G);
+          // Add 'f -> g' ref edge.
+          (void)CastInst::CreatePointerCast(G,
+                                            Type::getInt8PtrTy(F.getContext()),
+                                            "g.ref", FFRef->getNextNode());
           // Instruct the LazyCallGraph to create a new node for 'g', as the
           // single node in a new SCC, into the call graph. As a result
           // the call graph is composed of a single RefSCC with two SCCs:
           // [(f), (g)].
           CG.addNewFunctionIntoRefSCC(*G, C.getOuterRefSCC());
 
-          // "Demote" the 'f -> f' call egde to a ref edge.
-          // 1. Erase the call edge from 'f' to 'f'.
-          Call->eraseFromParent();
-          // 2. Insert a ref edge from 'f' to 'f'.
-          (void)CastInst::CreatePointerCast(&F,
+          // Create mutually recursive functions (ref only) 'h1' and 'h2'.
+          auto *H1 = Function::Create(F.getFunctionType(), F.getLinkage(),
+                                      F.getAddressSpace(), "h1", F.getParent());
+          auto *H2 = Function::Create(F.getFunctionType(), F.getLinkage(),
+                                      F.getAddressSpace(), "h2", F.getParent());
+          BasicBlock *H1BB =
+              BasicBlock::Create(F.getParent()->getContext(), "entry", H1);
+          BasicBlock *H2BB =
+              BasicBlock::Create(F.getParent()->getContext(), "entry", H2);
+          (void)CastInst::CreatePointerCast(
+              H2, Type::getInt8PtrTy(F.getContext()), "h2.ref", H1BB);
+          (void)ReturnInst::Create(H1->getContext(), H1BB);
+          (void)CastInst::CreatePointerCast(
+              H1, Type::getInt8PtrTy(F.getContext()), "h1.ref", H2BB);
+          (void)ReturnInst::Create(H2->getContext(), H2BB);
+
+          // Add 'f -> h1' ref edge.
+          (void)CastInst::CreatePointerCast(H1,
                                             Type::getInt8PtrTy(F.getContext()),
-                                            "f.ref", &*F.begin()->begin());
+                                            "h.ref", FFRef->getNextNode());
+
+          CG.addNewFunctionIntoRefSCC(*H1, C.getOuterRefSCC());
+          CG.addNewFunctionIntoRefSCC(*H2, C.getOuterRefSCC());
 
+          F.getParent()->dump();
           ASSERT_NO_FATAL_FAILURE(
               updateCGAndAnalysisManagerForCGSCCPass(CG, C, N, AM, UR, FAM))
               << "Updating the call graph with a demoted, self-referential "
-                 "call edge 'f -> f', and a newly inserted ref edge 'f -> g', "
-                 "caused a fatal failure";
+                 "call edge 'f -> f', a newly inserted ref edge 'f -> g', and "
+                 "mutually recursive h1 <-> h2 caused a fatal failure";
         }
       }));