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 @@ -1009,6 +1009,10 @@ /// 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 /// @@ -1058,13 +1062,6 @@ /// 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); - ///@} ///@{ @@ -1171,13 +1168,6 @@ /// 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. diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp --- a/llvm/lib/Analysis/CGSCCPassManager.cpp +++ b/llvm/lib/Analysis/CGSCCPassManager.cpp @@ -459,6 +459,7 @@ SmallSetVector DemotedCallTargets; SmallSetVector NewCallEdges; SmallSetVector NewRefEdges; + SmallSetVector 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 @@ -467,19 +468,23 @@ if (auto *CB = dyn_cast(&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. @@ -490,22 +495,29 @@ 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); 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 @@ -1565,21 +1565,6 @@ // 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()); - 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); } @@ -1594,17 +1579,13 @@ 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 addToCallGraph(&NewFn); - else if (LCG) - LCG->addNewFunctionIntoSCC(NewFn, *SCC); } void CallGraphUpdater::removeFunction(Function &DeadFn) { 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 @@ -1743,7 +1743,6 @@ // 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'. @@ -1785,6 +1784,25 @@ 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()); @@ -1803,16 +1821,15 @@ // 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"; } })); diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp --- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp +++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp @@ -451,47 +451,6 @@ EXPECT_EQ(0, std::distance(B->begin(), B->end())); } -TEST(LazyCallGraphTest, BasicGraphMutationOutlining) { - LLVMContext Context; - std::unique_ptr 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 M = parseAssembly(Context, DiamondOfTriangles); @@ -2211,46 +2170,4 @@ 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 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()); -} }