From 013774530898476debd4d65525f1c7ba942cabee Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Mon, 30 Dec 2019 17:02:09 -0600 Subject: [PATCH] [PM][CGSCC] Add a helper to update the call graph from SCC passes With this patch new trivial edges can be added to an SCC in a CGSCC pass via the updateCGAndAnalysisManagerForCGSCCPass method. It shares almost all the code with the existing updateCGAndAnalysisManagerForFunctionPass method but it implements the first step towards the TODOs. This was initially part of D70927. Reviewed By: JonChesterfield Differential Revision: https://reviews.llvm.org/D72025 --- llvm/include/llvm/Analysis/CGSCCPassManager.h | 10 ++ llvm/lib/Analysis/CGSCCPassManager.cpp | 70 ++++++++--- llvm/unittests/Analysis/CGSCCPassManagerTest.cpp | 147 +++++++++++++++++++++++ 3 files changed, 210 insertions(+), 17 deletions(-) diff --git a/llvm/include/llvm/Analysis/CGSCCPassManager.h b/llvm/include/llvm/Analysis/CGSCCPassManager.h index 933f221..3e14a84 100644 --- a/llvm/include/llvm/Analysis/CGSCCPassManager.h +++ b/llvm/include/llvm/Analysis/CGSCCPassManager.h @@ -418,6 +418,16 @@ LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass( 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 index a0b3f83..311aa65 100644 --- a/llvm/lib/Analysis/CGSCCPassManager.cpp +++ b/llvm/lib/Analysis/CGSCCPassManager.cpp @@ -423,9 +423,9 @@ incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G, 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 @@ LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass( 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 @@ LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass( 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,42 @@ LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass( 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(); + (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!"); + RC->insertTrivialRefEdge(N, *RefTarget); + } + + // Handle new call edges. + for (Node *CallTarget : NewCallEdges) { + SCC &TargetC = *G.lookupSCC(*CallTarget); + RefSCC &TargetRC = TargetC.getOuterRefSCC(); + (void)TargetRC; + // 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 +730,16 @@ LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass( 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 index e6ad625..89ee4f1 100644 --- a/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp +++ b/llvm/unittests/Analysis/CGSCCPassManagerTest.cpp @@ -1303,4 +1303,151 @@ TEST_F(CGSCCPassManagerTest, TestAnalysisInvalidationCGSCCUpdate) { // 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 -- 2.7.4