[NewPM][CGSCC] Handle newly added functions in updateCGAndAnalysisManagerForPass

[aeubanks]

Summary

This seems to fit the CGSCC updates model better than calling
addNewFunctionInto{Ref,}SCC() on newly created/outlined functions.
Now addNewFunctionInto{Ref,}SCC() are no longer necessary.

However, this doesn't work on newly outlined functions that aren't
referenced by the original function. e.g. if a() was outlined into b()
and c(), but c() is only referenced by b() and not by a(), this will
trigger an assert.

This also fixes an issue I was seeing with newly created functions not
having passes run on them.

Ran check-llvm with expensive checks.

[asbirlea]

The general comment (I mentioned this offline too), is that this is much closer to the direction I'd see the changes going. By this, I mean, the APIs removed here seemed unnecessary, and inlining their functionality at the callsite made more sense.
This seems the right approach for coroutines and outlining. I'm not clear for inlining at this point, Im working to understand the flow better there.

llvm/lib/Analysis/CGSCCPassManager.cpp

518

Remove braces.

519

I'm not clear how adding this call impacts the Inliner.

[aeubanks]

rebase
remove braces

[aeubanks]

llvm/lib/Analysis/CGSCCPassManager.cpp

519

It shouldn't affect the inliner. For a given inline, the inliner will remove an edge, and potentially add new call/ref edges (corresponding to any call/ref edges in the inlined function). All of those will already have nodes since they were further down the call graph.

This would only affect completely new functions being created (or potentially new calls to functions up the call graph, which would be a bug, not sure if that's caught by asserts or not).

[asbirlea]

llvm/lib/Analysis/CGSCCPassManager.cpp

519

Thank you for the clarification.

[lxfind]

@aeubanks, I was wondering if you are familiar with this but it seems that the SCC update after CoroSplit couldn't handle the case when there is recursion in the original coroutine, that is, the newly generated functions by CoroSplit will contain cycles (foo calling foo.resume which then calls foo). Do you have suggestions/thoughts on how to fix it?
For example, test like this will fail assertions:

; RUN: opt < %s --enable-new-pm --enable-coroutines -O3 -S
; Function Attrs: argmemonly nounwind readonly
declare token @llvm.coro.id(i32, i8* readnone, i8* nocapture readonly, i8*) #0

; Function Attrs: nounwind
declare i8* @llvm.coro.begin(token, i8* writeonly) #1

; Function Attrs: nounwind
declare token @llvm.coro.save(i8*) #1

; Function Attrs: nounwind
declare i8 @llvm.coro.suspend(token, i1) #1

define dso_local void @foo() align 2 personality i8* undef {
entry:
  %__promise = alloca i32, align 8
  %0 = bitcast i32* %__promise to i8*
  %1 = call token @llvm.coro.id(i32 16, i8* %0, i8* null, i8* null)
  %2 = call i8* @llvm.coro.begin(token %1, i8* null)
  br i1 undef, label %if.then154, label %init.suspend

init.suspend:                                     ; preds = %entry
  %save = call token @llvm.coro.save(i8* null)
  %3 = call i8 @llvm.coro.suspend(token %save, i1 false)
  %cond = icmp eq i8 %3, 0
  br i1 %cond, label %if.then154, label %invoke.cont163

if.then154:                                       ; preds = %init.suspend, %entry
  call void @foo()
  br label %invoke.cont163

invoke.cont163:                                   ; preds = %if.then154, %init.suspend
  ret void
}

attributes #0 = { argmemonly nounwind readonly }
attributes #1 = { nounwind }

llvm/lib/Transforms/Coroutines/CoroSplit.cpp

1491

Seems like the comments wasn't updated.

[aeubanks]

Yes I'm aware of the issue and https://reviews.llvm.org/D88714 is an attempt to fix that. I was going to ask exactly what sorts of transformations coroutines does. I'll make a post in llvm-dev.

[lxfind]

In D87798#2395800, @aeubanks wrote:

Yes I'm aware of the issue and https://reviews.llvm.org/D88714 is an attempt to fix that. I was going to ask exactly what sorts of transformations coroutines does. I'll make a post in llvm-dev.

Cool. Thanks!
Besides the problem caused by recursion, I also filed https://bugs.llvm.org/show_bug.cgi?id=48176 the other day which seems to be related too.

[lxfind]

In D87798#2395800, @aeubanks wrote:

Yes I'm aware of the issue and https://reviews.llvm.org/D88714 is an attempt to fix that. I was going to ask exactly what sorts of transformations coroutines does. I'll make a post in llvm-dev.

I just double checked, D88714 is going to fix https://bugs.llvm.org/show_bug.cgi?id=48176 but not the issue I mentioned above.
In the case of recursion, it will form cycles in the newly added functions, which the current SCC update cannot handle. The assertion will fail here:
https://github.com/llvm/llvm-project/blob/master/llvm/lib/Analysis/CGSCCPassManager.cpp#L409

llvm/include/llvm/Analysis/LazyCallGraph.h

#endif
   /// Test whether a function is a known and defined library function tracked by
   /// the call graph.
   ///
   /// Because these functions are known to LLVM they are specially modeled in
   /// the call graph and even when all IR-level references have been removed
   /// remain active and reachable.
   bool isLibFunction(Function &F) const { return LibFunctions.count(&F); }
 
+  /// Helper to initialize a new node created outside of creating SCCs and add
+  /// it to the NodeMap. e.g. when a function is outlined.
+  Node &initNode(Node &N, LazyCallGraph::SCC &C);
+
   ///@{
   /// \name Pre-SCC Mutation API
   ///
   /// These methods are only valid to call prior to forming any SCCs for this
   /// call graph. They can be used to update the core node-graph during
   /// a node-based inorder traversal that precedes any SCC-based traversal.
   ///
   /// Once you begin manipulating a call graph's SCCs, most mutation of the
#endif
   /// changes result from calling this routine other than potentially removing
   /// entry points into the call graph.
   ///
   /// If SCC formation has begun, this function must not be part of the current
   /// DFS in order to call this safely. Typically, the function will have been
   /// fully visited by the DFS prior to calling this routine.
   void removeDeadFunction(Function &F);
 
-  /// Introduce a node for the function \p NewF in the SCC \p C.
-  void addNewFunctionIntoSCC(Function &NewF, SCC &C);
-
-  /// Introduce a node for the function \p NewF, as a single node in a
-  /// new SCC, in the RefSCC \p RC.
-  void addNewFunctionIntoRefSCC(Function &NewF, RefSCC &RC);
-
   ///@}
 
   ///@{
   /// \name Static helpers for code doing updates to the call graph.
   ///
   /// 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.
private:
 
   /// Helper to insert a new function, with an already looked-up entry in
   /// the NodeMap.
   Node &insertInto(Function &F, Node *&MappedN);
 
   /// Helper to update pointers back to the graph object during moves.
   void updateGraphPtrs();
 
-  /// Helper to insert a new function, add it to the NodeMap, and populate its
-  /// node.
-  Node &createNode(Function &F);
-
-  /// Helper to add the given Node \p N to the SCCMap, mapped to the SCC \p C.
-  void addNodeToSCC(SCC &C, Node &N);
-
   /// Allocates an SCC and constructs it using the graph allocator.
   ///
   /// The arguments are forwarded to the constructor.
   template <typename... Ts> SCC *createSCC(Ts &&... Args) {
     return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...);
   }
 
   /// Allocates a RefSCC and constructs it using the graph allocator.

llvm/lib/Analysis/CGSCCPassManager.cpp

static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
   // demoted edges.
   SmallVector<Constant *, 16> Worklist;
   SmallPtrSet<Constant *, 16> Visited;
   SmallPtrSet<Node *, 16> RetainedEdges;
   SmallSetVector<Node *, 4> PromotedRefTargets;
   SmallSetVector<Node *, 4> DemotedCallTargets;
   SmallSetVector<Node *, 4> NewCallEdges;
   SmallSetVector<Node *, 4> NewRefEdges;
+  SmallSetVector<Node *, 4> NewNodes;
 
   // First walk the function and handle all called functions. We do this first
   // because if there is a single call edge, whether there are ref edges is
   // irrelevant.
   for (Instruction &I : instructions(F))
     if (auto *CB = dyn_cast<CallBase>(&I))
       if (Function *Callee = CB->getCalledFunction())
         if (Visited.insert(Callee).second && !Callee->isDeclaration()) {
-          Node &CalleeN = *G.lookup(*Callee);
-          Edge *E = N->lookup(CalleeN);
+          Node *CalleeN = G.lookup(*Callee);
+          if (!CalleeN) {
+            CalleeN = &G.get(*Callee);
+            NewNodes.insert(CalleeN);
+          }
+          Edge *E = N->lookup(*CalleeN);
           assert((E || !FunctionPass) &&
                  "No function transformations should introduce *new* "
                  "call edges! Any new calls should be modeled as "
                  "promoted existing ref edges!");
-          bool Inserted = RetainedEdges.insert(&CalleeN).second;
+          bool Inserted = RetainedEdges.insert(CalleeN).second;
           (void)Inserted;
           assert(Inserted && "We should never visit a function twice.");
           if (!E)
-            NewCallEdges.insert(&CalleeN);
+            NewCallEdges.insert(CalleeN);
           else if (!E->isCall())
-            PromotedRefTargets.insert(&CalleeN);
+            PromotedRefTargets.insert(CalleeN);
         }
 
   // Now walk all references.
   for (Instruction &I : instructions(F))
     for (Value *Op : I.operand_values())
       if (auto *C = dyn_cast<Constant>(Op))
         if (Visited.insert(C).second)
           Worklist.push_back(C);
 
   auto VisitRef = [&](Function &Referee) {
-    Node &RefereeN = *G.lookup(Referee);
-    Edge *E = N->lookup(RefereeN);
+    Node *RefereeN = G.lookup(Referee);
+    if (!RefereeN) {
+      RefereeN = &G.get(Referee);
+      NewNodes.insert(RefereeN);
+    }
+    Edge *E = N->lookup(*RefereeN);
     assert((E || !FunctionPass) &&
            "No function transformations should introduce *new* ref "
            "edges! Any new ref edges would require IPO which "
            "function passes aren't allowed to do!");
-    bool Inserted = RetainedEdges.insert(&RefereeN).second;
+    bool Inserted = RetainedEdges.insert(RefereeN).second;
     (void)Inserted;
     assert(Inserted && "We should never visit a function twice.");
     if (!E)
-      NewRefEdges.insert(&RefereeN);
+      NewRefEdges.insert(RefereeN);
     else if (E->isCall())
-      DemotedCallTargets.insert(&RefereeN);
+      DemotedCallTargets.insert(RefereeN);
   };
   LazyCallGraph::visitReferences(Worklist, Visited, VisitRef);
 
+  for (Node *NewNode : NewNodes)
+    G.initNode(*NewNode, *C);
+
   // Handle new ref edges.
   for (Node *RefTarget : NewRefEdges) {
     SCC &TargetC = *G.lookupSCC(*RefTarget);
     RefSCC &TargetRC = TargetC.getOuterRefSCC();
     (void)TargetRC;
     // TODO: This only allows trivial edges to be added for now.
     assert((RC == &TargetRC ||
            RC->isAncestorOf(TargetRC)) && "New ref edge is not trivial!");

llvm/lib/Analysis/LazyCallGraph.cpp

void LazyCallGraph::removeDeadFunction(Function &F) {
   C.clear();
   RC.clear();
   RC.G = nullptr;
 
   // Nothing to delete as all the objects are allocated in stable bump pointer
   // allocators.
 }
 
-void LazyCallGraph::addNewFunctionIntoSCC(Function &NewF, SCC &C) {
-  addNodeToSCC(C, createNode(NewF));
-}
-
-void LazyCallGraph::addNewFunctionIntoRefSCC(Function &NewF, RefSCC &RC) {
-  Node &N = createNode(NewF);
-
-  auto *C = createSCC(RC, SmallVector<Node *, 1>());
-  addNodeToSCC(*C, N);
-
-  auto Index = RC.SCCIndices.size();
-  RC.SCCIndices[C] = Index;
-  RC.SCCs.push_back(C);
-}
-
 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
   return *new (MappedN = BPA.Allocate()) Node(*this, F);
 }
 
 void LazyCallGraph::updateGraphPtrs() {
   // Walk the node map to update their graph pointers. While this iterates in
   // an unstable order, the order has no effect so it remains correct.
   for (auto &FunctionNodePair : NodeMap)
     FunctionNodePair.second->G = this;
 
   for (auto *RC : PostOrderRefSCCs)
     RC->G = this;
 }
 
-LazyCallGraph::Node &LazyCallGraph::createNode(Function &F) {
-  Node &N = get(F);
-  NodeMap[&F] = &N;
+LazyCallGraph::Node &LazyCallGraph::initNode(Node &N, LazyCallGraph::SCC &C) {
+  NodeMap[&N.getFunction()] = &N;
   N.DFSNumber = N.LowLink = -1;
   N.populate();
-  return N;
-}
-
-void LazyCallGraph::addNodeToSCC(LazyCallGraph::SCC &C, Node &N) {
   C.Nodes.push_back(&N);
   SCCMap[&N] = &C;
+  return N;
 }
 
 template <typename RootsT, typename GetBeginT, typename GetEndT,
           typename GetNodeT, typename FormSCCCallbackT>
 void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
                                      GetEndT &&GetEnd, GetNodeT &&GetNode,
                                      FormSCCCallbackT &&FormSCC) {
   using EdgeItT = decltype(GetBegin(std::declval<Node &>()));

llvm/lib/Transforms/Coroutines/CoroSplit.cpp

static void updateCallGraphAfterCoroutineSplit(
   for (llvm::CoroEndInst *End : Shape.CoroEnds) {
     auto &Context = End->getContext();
     End->replaceAllUsesWith(ConstantInt::getFalse(Context));
     End->eraseFromParent();
   }
 
   postSplitCleanup(N.getFunction());
 
-  // To insert the newly created coroutine funclets 'f.resume', 'f.destroy', and
-  // 'f.cleanup' into the same SCC as the coroutine 'f' they were outlined from,
-  // we make use of the CallGraphUpdater class, which can modify the internal
-  // state of the LazyCallGraph.
-  for (Function *Clone : Clones)
-    CG.addNewFunctionIntoRefSCC(*Clone, C.getOuterRefSCC());
-
   // We've inserted instructions into coroutine 'f' that reference the three new
   // coroutine funclets. We must now update the call graph so that reference
   // edges between 'f' and its funclets are added to it. LazyCallGraph only
   // allows CGSCC passes to insert "trivial" reference edges. We've ensured
   // above, by inserting the funclets into the same SCC as the corutine, that
   // the edges are trivial.
   //
   // N.B.: If we didn't update the call graph here, a CGSCCToFunctionPassAdaptor
   // later in this CGSCC pass pipeline may be run, triggering a call graph
   // update of its own. Function passes run by the adaptor are not permitted to
   // add new edges of any kind to the graph, and the new edges inserted by this
   // pass would be misattributed to that unrelated function pass.
   updateCGAndAnalysisManagerForCGSCCPass(CG, C, N, AM, UR, FAM);

llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

if (CG) {
     LazyCallGraph::SCC *C = LCG->lookupSCC(N);
     updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
   }
 }
 
 void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) {
   if (CG)
     CG->addToCallGraph(&NewFn);
-  else if (LCG)
-    LCG->addNewFunctionIntoSCC(NewFn, *SCC);
 }
 
 void CallGraphUpdater::removeFunction(Function &DeadFn) {
   DeadFn.deleteBody();
   DeadFn.setLinkage(GlobalValue::ExternalLinkage);
   if (DeadFn.hasComdat())
     DeadFunctionsInComdats.push_back(&DeadFn);
   else

llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

CGPM.addPass(LambdaSCCPassNoPreserve(
           // 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);
           // 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,
                                             Type::getInt8PtrTy(F.getContext()),
                                             "f.ref", &*F.begin()->begin());
CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
     auto &FAM =
         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 
     for (auto &N : C) {
       auto &F = N.getFunction();
       if (F.getName() != "f")
         continue;
 
+      // Create mutually recursive functions (call) 'g1' and 'g2'.
+      auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
+                                  F.getAddressSpace(), "g1", F.getParent());
+      auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
+                                  F.getAddressSpace(), "g2", F.getParent());
+      BasicBlock *G1BB =
+          BasicBlock::Create(F.getParent()->getContext(), "entry", G1);
+      BasicBlock *G2BB =
+          BasicBlock::Create(F.getParent()->getContext(), "entry", G2);
+      (void)CallInst::Create(G1, {}, "", G1BB);
+      (void)ReturnInst::Create(G1->getContext(), G1BB);
+      (void)CallInst::Create(G2, {}, "", G1BB);
+      (void)ReturnInst::Create(G2->getContext(), G2BB);
+
+      // Add 'f -> g1' call edge.
+      (void)CallInst::Create(G1, {}, "", &F.getEntryBlock().front());
+      // Add 'f -> g2' call edge.
+      (void)CallInst::Create(G2, {}, "", &F.getEntryBlock().front());
+
       // 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()),
-                                        "h.ref", &F.getEntryBlock().front());
-
-      CG.addNewFunctionIntoRefSCC(*H1, C.getOuterRefSCC());
-      CG.addNewFunctionIntoRefSCC(*H2, C.getOuterRefSCC());
+                                        "h1.ref", &F.getEntryBlock().front());
+      // Add 'f -> h2' ref edge.
+      (void)CastInst::CreatePointerCast(H2, Type::getInt8PtrTy(F.getContext()),
+                                        "h2.ref", &F.getEntryBlock().front());
 
       ASSERT_NO_FATAL_FAILURE(
           updateCGAndAnalysisManagerForCGSCCPass(CG, C, N, AM, UR, FAM))
-          << "Updating the call graph with a demoted, self-referential "
-             "call edge 'f -> f', a newly inserted ref edge 'f -> g', and "
-             "mutually recursive h1 <-> h2 caused a fatal failure";
+          << "Updating the call graph with mutually recursive g1 <-> g2, h1 "
+             "<-> h2 caused a fatal failure";
     }
   }));
 
   ModulePassManager MPM(/*DebugLogging*/ true);
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
   MPM.run(*M, MAM);
 }
 
 #endif
 } // namespace

llvm/unittests/Analysis/LazyCallGraphTest.cpp

TEST(LazyCallGraphTest, BasicGraphMutation) {
 
   CG.removeEdge(C, C);
   EXPECT_EQ(0, std::distance(C->begin(), C->end()));
 
   CG.removeEdge(B, C);
   EXPECT_EQ(0, std::distance(B->begin(), B->end()));
 }
 
-TEST(LazyCallGraphTest, BasicGraphMutationOutlining) {
-  LLVMContext Context;
-  std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
-                                                     "entry:\n"
-                                                     "  call void @b()\n"
-                                                     "  call void @c()\n"
-                                                     "  ret void\n"
-                                                     "}\n"
-                                                     "define void @b() {\n"
-                                                     "entry:\n"
-                                                     "  ret void\n"
-                                                     "}\n"
-                                                     "define void @c() {\n"
-                                                     "entry:\n"
-                                                     "  ret void\n"
-                                                     "}\n");
-  LazyCallGraph CG = buildCG(*M);
-
-  LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
-  LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
-  LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c"));
-  A.populate();
-  B.populate();
-  C.populate();
-  CG.buildRefSCCs();
-
-  // Add a new function that is called from @b and verify it is in the same SCC.
-  Function &BFn = B.getFunction();
-  Function *NewFn =
-      Function::Create(BFn.getFunctionType(), BFn.getLinkage(), "NewFn", *M);
-  auto IP = BFn.getEntryBlock().getFirstInsertionPt();
-  CallInst::Create(NewFn, "", &*IP);
-  CG.addNewFunctionIntoSCC(*NewFn, *CG.lookupSCC(B));
-
-  EXPECT_EQ(CG.lookupSCC(A)->size(), 1);
-  EXPECT_EQ(CG.lookupSCC(B)->size(), 2);
-  EXPECT_EQ(CG.lookupSCC(C)->size(), 1);
-  EXPECT_EQ(CG.lookupSCC(*CG.lookup(*NewFn))->size(), 2);
-  EXPECT_EQ(CG.lookupSCC(*CG.lookup(*NewFn))->size(), CG.lookupSCC(B)->size());
-}
-
 TEST(LazyCallGraphTest, InnerSCCFormation) {
   LLVMContext Context;
   std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
   LazyCallGraph CG = buildCG(*M);
 
   // Now mutate the graph to connect every node into a single RefSCC to ensure
   // that our inner SCC formation handles the rest.
   LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1"));
TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) {
 
   // The only observable change should be that the RefSCC is gone from the
   // postorder sequence.
   I = CG.postorder_ref_scc_begin();
   EXPECT_EQ(&RC1, &*I++);
   EXPECT_EQ(&RC2, &*I++);
   EXPECT_EQ(CG.postorder_ref_scc_end(), I);
 }
-
-TEST(LazyCallGraphTest, AddNewFunctionIntoRefSCC) {
-  LLVMContext Context;
-  // Build and populate a graph composed of a single, self-referential node.
-  std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
-                                                     "entry:\n"
-                                                     "  call void @f()\n"
-                                                     "  ret void\n"
-                                                     "}\n");
-  LazyCallGraph CG = buildCG(*M);
-  CG.buildRefSCCs();
-
-  // At this point 'f' is in the call graph.
-  auto &F = lookupFunction(*M, "f");
-  LazyCallGraph::Node *FN = CG.lookup(F);
-  EXPECT_NE(FN, nullptr);
-
-  // And it has an SCC, of course.
-  auto *FSCC = CG.lookupSCC(*FN);
-  EXPECT_NE(FSCC, nullptr);
-
-  // Now, 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);
-
-  // Instruct the LazyCallGraph to create a new node for 'g', within the same
-  // RefSCC as 'f', but in a separate SCC.
-  CG.addNewFunctionIntoRefSCC(*G, FSCC->getOuterRefSCC());
-
-  // 'g' should now be in the call graph.
-  LazyCallGraph::Node *GN = CG.lookup(*G);
-  EXPECT_NE(GN, nullptr);
-  // 'g' should have an SCC, composed of the singular node 'g'.
-  // ('f' should not be included in the 'g' SCC.)
-  LazyCallGraph::SCC *GSCC = CG.lookupSCC(*GN);
-  EXPECT_NE(GSCC, nullptr);
-  EXPECT_EQ(GSCC->size(), 1);
-  EXPECT_NE(GSCC, FSCC);
-  // 'g' and 'f' should be part of the same RefSCC.
-  EXPECT_EQ(&GSCC->getOuterRefSCC(), &FSCC->getOuterRefSCC());
-}
 }