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 CG-SCC pass. +/// +/// CG-SCC 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/include/llvm/Analysis/CallGraph.h b/llvm/include/llvm/Analysis/CallGraph.h --- a/llvm/include/llvm/Analysis/CallGraph.h +++ b/llvm/include/llvm/Analysis/CallGraph.h @@ -61,6 +61,7 @@ namespace llvm { +class CallGraphUpdater; class CallGraphNode; class Module; class raw_ostream; @@ -71,6 +72,8 @@ /// /// The core call graph itself can also be updated to reflect changes to the IR. class CallGraph { + friend class CallGraphUpdater; + Module &M; using FunctionMapTy = diff --git a/llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h b/llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Utils/CallGraphUpdater.h @@ -0,0 +1,54 @@ +//===- CallGraphUpdater.h - A (lazy) call graph update helper ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file provides interfaces used to manipulate a call graph, regardless +/// if it is a "old style" CallGraph or an "new style" LazyCallGraph. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_UTILS_GENERIC_CALL_GRAPH_H +#define LLVM_ANALYSIS_UTILS_GENERIC_CALL_GRAPH_H + +#include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/CallGraph.h" +#include "llvm/Analysis/LazyCallGraph.h" + +namespace llvm { + +/// Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph. This +/// simplifies the interface and the call sites, e.g., new and old pass manager +/// passes can share the same code. +class CallGraphUpdater { + CallGraph *const CG = nullptr; + LazyCallGraph *const LCG = nullptr; + CGSCCAnalysisManager *AM = nullptr; + CGSCCUpdateResult *UR = nullptr; + +public: + CallGraphUpdater() {} + CallGraphUpdater(CallGraph &CG) : CG(&CG) {} + CallGraphUpdater(LazyCallGraph &LCG, CGSCCAnalysisManager &AM, + CGSCCUpdateResult &UR) + : LCG(&LCG), AM(&AM), UR(&UR) {} + + void removeFunction(Function &Fn); + + /// After an CG-SCC pass changes a function in ways that affect the call + /// graph, this method can be called to update it. + void reanalyzeFunction(Function &Fn); + + /// If a new function was created by outlining, this method can be called + /// to update the call graph for the new function. Note that the old one + /// still needs to be re-analyzed or manually updated. + void registerOutlinedFunction(Function &NewFn); +}; + +} // end namespace llvm + +#endif // LLVM_ANALYSIS_UTILS_GENERIC_CALL_GRAPH_H 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,15 +478,16 @@ 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); @@ -603,6 +604,26 @@ C, AM, UR); } + // Handle new ref edges. + for (Node *CallTarget : NewRefEdges) { + 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->insertTrivialRefEdge(N, *CallTarget); + } + + // 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); + } + // Now promote ref edges into call edges. for (Node *CallTarget : PromotedRefTargets) { SCC &TargetC = *G.lookupSCC(*CallTarget); @@ -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/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -6,6 +6,7 @@ BuildLibCalls.cpp BypassSlowDivision.cpp CallPromotionUtils.cpp + CallGraphUpdater.cpp CanonicalizeAliases.cpp CloneFunction.cpp CloneModule.cpp diff --git a/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp b/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Utils/CallGraphUpdater.cpp @@ -0,0 +1,47 @@ +//===- CallGraphUpdater.cpp - A (lazy) call graph update helper -----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file provides interfaces used to manipulate a call graph, regardless +/// if it is a "old style" CallGraph or an "new style" LazyCallGraph. +/// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Utils/CallGraphUpdater.h" + +using namespace llvm; + +void CallGraphUpdater::reanalyzeFunction(Function &Fn) { + if (CG) { + CallGraphNode *OldCGN = (*CG)[&Fn]; + CG->getExternalCallingNode()->removeAnyCallEdgeTo(OldCGN); + OldCGN->removeAllCalledFunctions(); + CG->addToCallGraph(&Fn); + } else if (LCG) { + LazyCallGraph::Node &N = LCG->get(Fn); + LazyCallGraph::SCC *C = LCG->lookupSCC(N); + updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR); + } +} + +void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) { + if (CG) { + CG->addToCallGraph(&NewFn); + } else if (LCG) { + LazyCallGraph::Node &CCNode = LCG->get(NewFn); + CCNode.populate(); + } +} + +void CallGraphUpdater::removeFunction(Function &Fn) { + if (CG) { + CG->removeFunctionFromModule((*CG)[&Fn]); + } else if (LCG) { + // TODO + } +}