|
LLVM 20.0.0git
|
A lazily constructed view of the call graph of a module. More...
#include "llvm/Analysis/LazyCallGraph.h"
Classes | |
| class | Edge |
| A class used to represent edges in the call graph. More... | |
| class | EdgeSequence |
| The edge sequence object. More... | |
| class | Node |
| A node in the call graph. More... | |
| class | postorder_ref_scc_iterator |
| A post-order depth-first RefSCC iterator over the call graph. More... | |
| class | RefSCC |
| A RefSCC of the call graph. More... | |
| class | SCC |
| An SCC of the call graph. More... | |
Public Member Functions | |
| LazyCallGraph (Module &M, function_ref< TargetLibraryInfo &(Function &)> GetTLI) | |
| Construct a graph for the given module. | |
| LazyCallGraph (LazyCallGraph &&G) | |
| LazyCallGraph & | operator= (LazyCallGraph &&RHS) |
| void | verify () |
| Verify that every RefSCC is valid. | |
| bool | invalidate (Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &) |
| EdgeSequence::iterator | begin () |
| EdgeSequence::iterator | end () |
| void | buildRefSCCs () |
| postorder_ref_scc_iterator | postorder_ref_scc_begin () |
| postorder_ref_scc_iterator | postorder_ref_scc_end () |
| iterator_range< postorder_ref_scc_iterator > | postorder_ref_sccs () |
| Node * | lookup (const Function &F) const |
| Lookup a function in the graph which has already been scanned and added. | |
| SCC * | lookupSCC (Node &N) const |
| Lookup a function's SCC in the graph. | |
| RefSCC * | lookupRefSCC (Node &N) const |
| Lookup a function's RefSCC in the graph. | |
| Node & | get (Function &F) |
| Get a graph node for a given function, scanning it to populate the graph data as necessary. | |
| ArrayRef< Function * > | getLibFunctions () const |
| Get the sequence of known and defined library functions. | |
| bool | isLibFunction (Function &F) const |
| Test whether a function is a known and defined library function tracked by the call graph. | |
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 graph must be performed via a RefSCC method. There are some exceptions below. | |
| void | insertEdge (Node &SourceN, Node &TargetN, Edge::Kind EK) |
| Update the call graph after inserting a new edge. | |
| void | insertEdge (Function &Source, Function &Target, Edge::Kind EK) |
| Update the call graph after inserting a new edge. | |
| void | removeEdge (Node &SourceN, Node &TargetN) |
| Update the call graph after deleting an edge. | |
| void | removeEdge (Function &Source, Function &Target) |
| Update the call graph after deleting an edge. | |
General Mutation API | |
There are a very limited set of mutations allowed on the graph as a whole once SCCs have started to be formed. These routines have strict contracts but may be called at any point. | |
| void | removeDeadFunctions (ArrayRef< Function * > DeadFs) |
| Remove dead functions from the call graph. | |
| void | markDeadFunction (Function &F) |
| Mark a function as dead to be removed later by removeDeadFunctions(). | |
| void | addSplitFunction (Function &OriginalFunction, Function &NewFunction) |
| Add a new function split/outlined from an existing function. | |
| void | addSplitRefRecursiveFunctions (Function &OriginalFunction, ArrayRef< Function * > NewFunctions) |
| Add new ref-recursive functions split/outlined from an existing function. | |
Static Public Member Functions | |
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. | |
| static void | visitReferences (SmallVectorImpl< Constant * > &Worklist, SmallPtrSetImpl< Constant * > &Visited, function_ref< void(Function &)> Callback) |
Recursively visits the defined functions whose address is reachable from every constant in the Worklist. | |
A lazily constructed view of the call graph of a module.
With the edges of this graph, the motivating constraint that we are attempting to maintain is that function-local optimization, CGSCC-local optimizations, and optimizations transforming a pair of functions connected by an edge in the graph, do not invalidate a bottom-up traversal of the SCC DAG. That is, no optimizations will delete, remove, or add an edge such that functions already visited in a bottom-up order of the SCC DAG are no longer valid to have visited, or such that functions not yet visited in a bottom-up order of the SCC DAG are not required to have already been visited.
Within this constraint, the desire is to minimize the merge points of the SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points in the SCC DAG, the more independence there is in optimizing within it. There is a strong desire to enable parallelization of optimizations over the call graph, and both limited fanout and merge points will (artificially in some cases) limit the scaling of such an effort.
To this end, graph represents both direct and any potential resolution to an indirect call edge. Another way to think about it is that it represents both the direct call edges and any direct call edges that might be formed through static optimizations. Specifically, it considers taking the address of a function to be an edge in the call graph because this might be forwarded to become a direct call by some subsequent function-local optimization. The result is that the graph closely follows the use-def edges for functions. Walking "up" the graph can be done by looking at all of the uses of a function.
The roots of the call graph are the external functions and functions escaped into global variables. Those functions can be called from outside of the module or via unknowable means in the IR – we may not be able to form even a potential call edge from a function body which may dynamically load the function and call it.
This analysis still requires updates to remain valid after optimizations which could potentially change the set of potential callees. The constraints it operates under only make the traversal order remain valid.
The entire analysis must be re-computed if full interprocedural optimizations run at any point. For example, globalopt completely invalidates the information in this analysis.
FIXME: This class is named LazyCallGraph in a lame attempt to distinguish it from the existing CallGraph. At some point, it is expected that this will be the only call graph and it will be renamed accordingly.
Definition at line 108 of file LazyCallGraph.h.
| LazyCallGraph::LazyCallGraph | ( | Module & | M, |
| function_ref< TargetLibraryInfo &(Function &)> | GetTLI | ||
| ) |
Construct a graph for the given module.
This sets up the graph and computes all of the entry points of the graph. No function definitions are scanned until their nodes in the graph are requested during traversal.
Definition at line 156 of file LazyCallGraph.cpp.
References A, addEdge(), llvm::dbgs(), F, get(), llvm::SmallPtrSetImpl< PtrType >::insert(), isKnownLibFunction(), LLVM_DEBUG, llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::LazyCallGraph::Edge::Ref, and visitReferences().
| LazyCallGraph::LazyCallGraph | ( | LazyCallGraph && | G | ) |
Definition at line 209 of file LazyCallGraph.cpp.
Add a new function split/outlined from an existing function.
The new function may only reference other functions that the original function did.
The original function must reference (either directly or indirectly) the new function.
The new function may also reference the original function. It may end up in a parent SCC in the case that the original function's edge to the new function is a ref edge, and the edge back is a call edge.
Definition at line 1622 of file LazyCallGraph.cpp.
References assert(), llvm::LazyCallGraph::Edge::Call, get(), getEdgeKind(), I, lookup(), lookupRefSCC(), lookupSCC(), llvm::make_scope_exit(), and Size.
Referenced by llvm::CallGraphUpdater::registerOutlinedFunction(), and updateCallGraphAfterCoroutineSplit().
| void LazyCallGraph::addSplitRefRecursiveFunctions | ( | Function & | OriginalFunction, |
| ArrayRef< Function * > | NewFunctions | ||
| ) |
Add new ref-recursive functions split/outlined from an existing function.
The new functions may only reference other functions that the original function did. The new functions may reference (not call) the original function.
The original function must reference (not call) all new functions. All new functions must reference (not call) each other.
Definition at line 1701 of file LazyCallGraph.cpp.
References assert(), llvm::ArrayRef< T >::empty(), get(), getEdgeKind(), I, llvm::LazyCallGraph::Edge::isCall(), lookup(), llvm::LazyCallGraph::EdgeSequence::lookup(), lookupRefSCC(), llvm::make_scope_exit(), llvm::LazyCallGraph::Edge::Ref, Size, and verify().
Referenced by updateCallGraphAfterCoroutineSplit().
|
inline |
Definition at line 951 of file LazyCallGraph.h.
References llvm::LazyCallGraph::EdgeSequence::begin().
| void LazyCallGraph::buildRefSCCs | ( | ) |
Definition at line 1935 of file LazyCallGraph.cpp.
References assert(), llvm::LazyCallGraph::EdgeSequence::empty(), llvm::LazyCallGraph::Edge::getNode(), I, N, and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by llvm::buildTopDownFuncOrder(), deduceFunctionAttributeInRPO(), llvm::AMDGPUPerfHintAnalysis::run(), and llvm::ModuleToPostOrderCGSCCPassAdaptor::run().
|
inline |
Definition at line 952 of file LazyCallGraph.h.
References llvm::LazyCallGraph::EdgeSequence::end().
Get a graph node for a given function, scanning it to populate the graph data as necessary.
Definition at line 996 of file LazyCallGraph.h.
Referenced by addSplitFunction(), addSplitRefRecursiveFunctions(), llvm::CallGraphUpdater::finalize(), insertEdge(), LazyCallGraph(), llvm::MLInlineAdvisor::MLInlineAdvisor(), llvm::CallGraphUpdater::reanalyzeFunction(), removeEdge(), llvm::CallGraphUpdater::replaceFunctionWith(), and llvm::CoroSplitPass::run().
Get the sequence of known and defined library functions.
These functions, because they are known to LLVM, can have calls introduced out of thin air from arbitrary IR.
Definition at line 1008 of file LazyCallGraph.h.
|
inline |
Update the call graph after inserting a new edge.
Definition at line 1035 of file LazyCallGraph.h.
References get(), and insertEdge().
| void LazyCallGraph::insertEdge | ( | Node & | SourceN, |
| Node & | TargetN, | ||
| Edge::Kind | EK | ||
| ) |
Update the call graph after inserting a new edge.
Definition at line 1484 of file LazyCallGraph.cpp.
References assert().
Referenced by insertEdge().
| bool LazyCallGraph::invalidate | ( | Module & | , |
| const PreservedAnalyses & | PA, | ||
| ModuleAnalysisManager::Invalidator & | |||
| ) |
Definition at line 224 of file LazyCallGraph.cpp.
References llvm::PreservedAnalyses::getChecker().
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.
Definition at line 1018 of file LazyCallGraph.h.
References F.
Referenced by markDeadFunction().
Lookup a function in the graph which has already been scanned and added.
Definition at line 975 of file LazyCallGraph.h.
References F.
Referenced by addSplitFunction(), addSplitRefRecursiveFunctions(), llvm::MLInlineAdvisor::getInitialFunctionLevel(), llvm::MLInlineAdvisor::onSuccessfulInlining(), removeDeadFunctions(), and llvm::CoroAnnotationElidePass::run().
Lookup a function's RefSCC in the graph.
Definition at line 987 of file LazyCallGraph.h.
References llvm::CallingConv::C, lookupSCC(), and N.
Referenced by addSplitFunction(), addSplitRefRecursiveFunctions(), and removeDeadFunctions().
Lookup a function's SCC in the graph.
Definition at line 981 of file LazyCallGraph.h.
References N.
Referenced by addSplitFunction(), llvm::CallGraphUpdater::finalize(), lookupRefSCC(), llvm::CallGraphUpdater::reanalyzeFunction(), llvm::CGSCCToFunctionPassAdaptor::run(), llvm::CoroAnnotationElidePass::run(), and llvm::CoroSplitPass::run().
| void LazyCallGraph::markDeadFunction | ( | Function & | F | ) |
Mark a function as dead to be removed later by removeDeadFunctions().
The function body should have no incoming or outgoing call or ref edges. For example, a function with a single "unreachable" instruction.
Definition at line 1500 of file LazyCallGraph.cpp.
References assert(), F, isLibFunction(), N, and llvm::LazyCallGraph::Edge::Ref.
Referenced by llvm::CallGraphUpdater::finalize().
| LazyCallGraph & LazyCallGraph::operator= | ( | LazyCallGraph && | RHS | ) |
Definition at line 232 of file LazyCallGraph.cpp.
References G.
|
inline |
Definition at line 956 of file LazyCallGraph.h.
References assert(), and llvm::LazyCallGraph::EdgeSequence::empty().
Referenced by postorder_ref_sccs().
|
inline |
Definition at line 962 of file LazyCallGraph.h.
References assert(), and llvm::LazyCallGraph::EdgeSequence::empty().
Referenced by postorder_ref_sccs().
|
inline |
Definition at line 970 of file LazyCallGraph.h.
References llvm::make_range(), postorder_ref_scc_begin(), and postorder_ref_scc_end().
Referenced by llvm::buildTopDownFuncOrder(), deduceFunctionAttributeInRPO(), llvm::AMDGPUPerfHintAnalysis::run(), llvm::ModuleToPostOrderCGSCCPassAdaptor::run(), and verify().
Remove dead functions from the call graph.
These functions should have already been passed to markDeadFunction(). This is done as a batch to prevent compile time blowup as a result of handling a single function at a time.
Definition at line 1523 of file LazyCallGraph.cpp.
References assert(), llvm::LazyCallGraph::RefSCC::begin(), llvm::ArrayRef< T >::empty(), lookup(), lookupRefSCC(), N, llvm::SmallVectorTemplateBase< T, bool >::push_back(), and llvm::LazyCallGraph::RefSCC::size().
Referenced by llvm::ModuleToPostOrderCGSCCPassAdaptor::run().
Update the call graph after deleting an edge.
Definition at line 1043 of file LazyCallGraph.h.
References get(), and removeEdge().
Update the call graph after deleting an edge.
Definition at line 1491 of file LazyCallGraph.cpp.
References assert().
Referenced by removeEdge().
| void LazyCallGraph::verify | ( | ) |
Verify that every RefSCC is valid.
Definition at line 217 of file LazyCallGraph.cpp.
References postorder_ref_sccs().
Referenced by addSplitRefRecursiveFunctions(), llvm::LazyCallGraph::RefSCC::insertIncomingRefEdge(), llvm::LazyCallGraph::RefSCC::insertInternalRefEdge(), llvm::LazyCallGraph::RefSCC::insertOutgoingEdge(), llvm::LazyCallGraph::RefSCC::insertTrivialCallEdge(), llvm::LazyCallGraph::RefSCC::insertTrivialRefEdge(), llvm::LazyCallGraph::RefSCC::removeInternalRefEdges(), llvm::LazyCallGraph::RefSCC::removeOutgoingEdge(), llvm::LazyCallGraph::RefSCC::replaceNodeFunction(), llvm::ModuleToPostOrderCGSCCPassAdaptor::run(), llvm::LazyCallGraph::RefSCC::switchInternalEdgeToCall(), llvm::LazyCallGraph::RefSCC::switchInternalEdgeToRef(), llvm::LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(), llvm::LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(), and llvm::LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef().
|
static |
Recursively visits the defined functions whose address is reachable from every constant in the Worklist.
Doesn't recurse through any constants already in the Visited set, and updates that set with every constant visited.
For each defined function, calls Callback with that function.
Definition at line 1973 of file LazyCallGraph.cpp.
References llvm::CallingConv::C, llvm::SmallVectorBase< Size_T >::empty(), F, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().
Referenced by getEdgeKind(), LazyCallGraph(), and updateCGAndAnalysisManagerForPass().
1.9.6