diff --git a/llvm/include/llvm/Analysis/CGSCCPassManager.h b/llvm/include/llvm/Analysis/CGSCCPassManager.h --- a/llvm/include/llvm/Analysis/CGSCCPassManager.h +++ b/llvm/include/llvm/Analysis/CGSCCPassManager.h @@ -418,6 +418,16 @@ LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR); +/// Helper to update the call graph after running a CGSCC pass. +/// +/// CGSCC passes can only mutate the call graph in specific ways. This +/// routine provides a helper that updates the call graph in those ways +/// including returning whether any changes were made and populating a CG +/// update result struct for the overall CGSCC walk. +LazyCallGraph::SCC &updateCGAndAnalysisManagerForCGSCCPass( + LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, + CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR); + /// Adaptor that maps from a SCC to its functions. /// /// Designed to allow composition of a FunctionPass(Manager) and 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 @@ -423,9 +423,9 @@ return C; } -LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass( +static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass( LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, - CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) { + CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, bool FunctionPass) { using Node = LazyCallGraph::Node; using Edge = LazyCallGraph::Edge; using SCC = LazyCallGraph::SCC; @@ -443,6 +443,8 @@ SmallPtrSet RetainedEdges; SmallSetVector PromotedRefTargets; SmallSetVector DemotedCallTargets; + SmallSetVector NewCallEdges; + SmallSetVector NewRefEdges; // 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 @@ -453,18 +455,16 @@ if (Visited.insert(Callee).second && !Callee->isDeclaration()) { Node &CalleeN = *G.lookup(*Callee); Edge *E = N->lookup(CalleeN); - // FIXME: We should really handle adding new calls. While it will - // make downstream usage more complex, there is no fundamental - // limitation and it will allow passes within the CGSCC to be a bit - // more flexible in what transforms they can do. Until then, we - // verify that new calls haven't been introduced. - assert(E && "No function transformations should introduce *new* " - "call edges! Any new calls should be modeled as " - "promoted existing ref edges!"); + 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; (void)Inserted; assert(Inserted && "We should never visit a function twice."); - if (!E->isCall()) + if (!E) + NewCallEdges.insert(&CalleeN); + else if (!E->isCall()) PromotedRefTargets.insert(&CalleeN); } @@ -478,19 +478,40 @@ auto VisitRef = [&](Function &Referee) { Node &RefereeN = *G.lookup(Referee); Edge *E = N->lookup(RefereeN); - // FIXME: Similarly to new calls, we also currently preclude - // introducing new references. See above for details. - assert(E && "No function transformations should introduce *new* ref " - "edges! Any new ref edges would require IPO which " - "function passes aren't allowed to do!"); + 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; (void)Inserted; assert(Inserted && "We should never visit a function twice."); - if (E->isCall()) + if (!E) + NewRefEdges.insert(&RefereeN); + else if (E->isCall()) DemotedCallTargets.insert(&RefereeN); }; LazyCallGraph::visitReferences(Worklist, Visited, VisitRef); + // Handle new ref edges. + for (Node *RefTarget : NewRefEdges) { + SCC &TargetC = *G.lookupSCC(*RefTarget); + RefSCC &TargetRC = TargetC.getOuterRefSCC(); + // TODO: This only allows trivial edges to be added for now. + assert(RC == &TargetRC || + RC->isAncestorOf(TargetRC) && "New ref edge is not trivial!"); + RC->insertTrivialRefEdge(N, *RefTarget); + } + + // Handle new call edges. + for (Node *CallTarget : NewCallEdges) { + SCC &TargetC = *G.lookupSCC(*CallTarget); + RefSCC &TargetRC = TargetC.getOuterRefSCC(); + // TODO: This only allows trivial edges to be added for now. + assert(RC == &TargetRC || + RC->isAncestorOf(TargetRC) && "New call edge is not trivial!"); + RC->insertTrivialCallEdge(N, *CallTarget); + } + // Include synthetic reference edges to known, defined lib functions. for (auto *F : G.getLibFunctions()) // While the list of lib functions doesn't have repeats, don't re-visit @@ -707,3 +728,16 @@ return *C; } + +LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass( + LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, + CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) { + return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, + /* FunctionPass */ true); +} +LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForCGSCCPass( + LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, + CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) { + return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, + /* FunctionPass */ false); +} 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 @@ -1281,4 +1281,151 @@ // the graph, and then over the whole module. EXPECT_EQ(6 + 3 + 6 + 3 + 3 + 2 + 6, IndirectFunctionAnalysisRuns); } + +// The (negative) tests below check for assertions so we only run them if NDEBUG +// is not defined. +#ifndef NDEBUG + +struct LambdaSCCPassNoPreserve : public PassInfoMixin { + template + LambdaSCCPassNoPreserve(T &&Arg) : Func(std::forward(Arg)) {} + + PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, + LazyCallGraph &CG, CGSCCUpdateResult &UR) { + Func(C, AM, CG, UR); + return PreservedAnalyses::none(); + } + + std::function + Func; +}; + +TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses0) { + CGSCCPassManager CGPM(/*DebugLogging*/ true); + CGPM.addPass(LambdaSCCPassNoPreserve( + [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, + CGSCCUpdateResult &UR) { + if (C.getName() != "(h3, h1, h2)") + return; + + Function *FnX = M->getFunction("x"); + Function *FnH1 = M->getFunction("h1"); + Function *FnH2 = M->getFunction("h2"); + Function *FnH3 = M->getFunction("h3"); + ASSERT_NE(FnX, nullptr); + ASSERT_NE(FnH1, nullptr); + ASSERT_NE(FnH2, nullptr); + ASSERT_NE(FnH3, nullptr); + + // And insert a call to `h1`, `h2`, and `h3`. + Instruction *IP = &FnH2->getEntryBlock().front(); + (void)CallInst::Create(FnH1, {}, "", IP); + (void)CallInst::Create(FnH2, {}, "", IP); + (void)CallInst::Create(FnH3, {}, "", IP); + + auto &H2N = *llvm::find_if( + C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; }); + ASSERT_NO_FATAL_FAILURE( + updateCGAndAnalysisManagerForCGSCCPass(CG, C, H2N, AM, UR)); + })); + + ModulePassManager MPM(/*DebugLogging*/ true); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + MPM.run(*M, MAM); } + +TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses1) { + CGSCCPassManager CGPM(/*DebugLogging*/ true); + CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C, + CGSCCAnalysisManager &AM, + LazyCallGraph &CG, + CGSCCUpdateResult &UR) { + if (C.getName() != "(h3, h1, h2)") + return; + + Function *FnX = M->getFunction("x"); + Function *FnH1 = M->getFunction("h1"); + Function *FnH2 = M->getFunction("h2"); + Function *FnH3 = M->getFunction("h3"); + ASSERT_NE(FnX, nullptr); + ASSERT_NE(FnH1, nullptr); + ASSERT_NE(FnH2, nullptr); + ASSERT_NE(FnH3, nullptr); + + // And insert a call to `h1`, `h2`, and `h3`. + Instruction *IP = &FnH2->getEntryBlock().front(); + (void)CallInst::Create(FnH1, {}, "", IP); + (void)CallInst::Create(FnH2, {}, "", IP); + (void)CallInst::Create(FnH3, {}, "", IP); + + auto &H2N = *llvm::find_if( + C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; }); + ASSERT_DEATH(updateCGAndAnalysisManagerForFunctionPass(CG, C, H2N, AM, UR), + "Any new calls should be modeled as"); + })); + + ModulePassManager MPM(/*DebugLogging*/ true); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + MPM.run(*M, MAM); +} + +TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses2) { + CGSCCPassManager CGPM(/*DebugLogging*/ true); + CGPM.addPass(LambdaSCCPassNoPreserve( + [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, + CGSCCUpdateResult &UR) { + if (C.getName() != "(f)") + return; + + Function *FnF = M->getFunction("f"); + Function *FnH2 = M->getFunction("h2"); + ASSERT_NE(FnF, nullptr); + ASSERT_NE(FnH2, nullptr); + + // And insert a call to `h2` + Instruction *IP = &FnF->getEntryBlock().front(); + (void)CallInst::Create(FnH2, {}, "", IP); + + auto &FN = *llvm::find_if( + C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; }); + ASSERT_NO_FATAL_FAILURE( + updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR)); + })); + + ModulePassManager MPM(/*DebugLogging*/ true); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + MPM.run(*M, MAM); +} + +TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses3) { + CGSCCPassManager CGPM(/*DebugLogging*/ true); + CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C, + CGSCCAnalysisManager &AM, + LazyCallGraph &CG, + CGSCCUpdateResult &UR) { + if (C.getName() != "(f)") + return; + + Function *FnF = M->getFunction("f"); + Function *FnH2 = M->getFunction("h2"); + ASSERT_NE(FnF, nullptr); + ASSERT_NE(FnH2, nullptr); + + // And insert a call to `h2` + Instruction *IP = &FnF->getEntryBlock().front(); + (void)CallInst::Create(FnH2, {}, "", IP); + + auto &FN = *llvm::find_if( + C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; }); + ASSERT_DEATH(updateCGAndAnalysisManagerForFunctionPass(CG, C, FN, AM, UR), + "Any new calls should be modeled as"); + })); + + ModulePassManager MPM(/*DebugLogging*/ true); + MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM))); + MPM.run(*M, MAM); +} + +#endif +} // namespace