LLVM  6.0.0svn
Classes | Public Member Functions | List of all members
llvm::LazyCallGraph Class Reference

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, TargetLibraryInfo &TLI)
 Construct a graph for the given module. More...
 
 LazyCallGraph (LazyCallGraph &&G)
 
LazyCallGraphoperator= (LazyCallGraph &&RHS)
 
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_iteratorpostorder_ref_sccs ()
 
Nodelookup (const Function &F) const
 Lookup a function in the graph which has already been scanned and added. More...
 
SCClookupSCC (Node &N) const
 Lookup a function's SCC in the graph. More...
 
RefSCClookupRefSCC (Node &N) const
 Lookup a function's RefSCC in the graph. More...
 
Nodeget (Function &F)
 Get a graph node for a given function, scanning it to populate the graph data as necessary. More...
 
ArrayRef< Function * > getLibFunctions () const
 Get the sequence of known and defined library functions. More...
 
bool isLibFunction (Function &F) const
 Test whether a function is a known and defined library function tracked by the call graph. More...
 
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. More...
 
void insertEdge (Function &Source, Function &Target, Edge::Kind EK)
 Update the call graph after inserting a new edge. More...
 
void removeEdge (Node &SourceN, Node &TargetN)
 Update the call graph after deleting an edge. More...
 
void removeEdge (Function &Source, Function &Target)
 Update the call graph after deleting an edge. More...
 
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 removeDeadFunction (Function &F)
 Remove a dead function from the call graph (typically to delete it). More...
 

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.

template<typename CallbackT >
static void visitReferences (SmallVectorImpl< Constant *> &Worklist, SmallPtrSetImpl< Constant *> &Visited, CallbackT Callback)
 Recursively visits the defined functions whose address is reachable from every constant in the Worklist. More...
 

Detailed Description

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 112 of file LazyCallGraph.h.

Constructor & Destructor Documentation

◆ LazyCallGraph() [1/2]

LazyCallGraph::LazyCallGraph ( Module M,
TargetLibraryInfo TLI 
)

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 153 of file LazyCallGraph.cpp.

References addEdge(), llvm::dbgs(), DEBUG, F(), llvm::Module::getModuleIdentifier(), llvm::SmallPtrSetImpl< PtrType >::insert(), isKnownLibFunction(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::LazyCallGraph::Edge::Ref, second, and visitReferences().

Referenced by llvm::LazyCallGraph::postorder_ref_scc_iterator::operator++(), and llvm::LazyCallGraphAnalysis::run().

◆ LazyCallGraph() [2/2]

LazyCallGraph::LazyCallGraph ( LazyCallGraph &&  G)

Definition at line 191 of file LazyCallGraph.cpp.

Member Function Documentation

◆ begin()

EdgeSequence::iterator llvm::LazyCallGraph::begin ( )
inline

Definition at line 939 of file LazyCallGraph.h.

◆ buildRefSCCs()

void LazyCallGraph::buildRefSCCs ( )

◆ end()

EdgeSequence::iterator llvm::LazyCallGraph::end ( )
inline

Definition at line 940 of file LazyCallGraph.h.

References buildRefSCCs().

◆ get()

Node& llvm::LazyCallGraph::get ( Function F)
inline

Get a graph node for a given function, scanning it to populate the graph data as necessary.

Definition at line 984 of file LazyCallGraph.h.

References F(), and N.

Referenced by llvm::LazyCallGraphPrinterPass::run(), and llvm::LazyCallGraphDOTPrinterPass::run().

◆ getLibFunctions()

ArrayRef<Function *> llvm::LazyCallGraph::getLibFunctions ( ) const
inline

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 996 of file LazyCallGraph.h.

Referenced by llvm::updateCGAndAnalysisManagerForFunctionPass().

◆ insertEdge() [1/2]

void LazyCallGraph::insertEdge ( Node SourceN,
Node TargetN,
Edge::Kind  EK 
)

Update the call graph after inserting a new edge.

Definition at line 1462 of file LazyCallGraph.cpp.

References assert().

Referenced by insertEdge(), and isLibFunction().

◆ insertEdge() [2/2]

void llvm::LazyCallGraph::insertEdge ( Function Source,
Function Target,
Edge::Kind  EK 
)
inline

Update the call graph after inserting a new edge.

Definition at line 1023 of file LazyCallGraph.h.

References insertEdge(), and removeEdge().

◆ isLibFunction()

bool llvm::LazyCallGraph::isLibFunction ( Function F) const
inline

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 1006 of file LazyCallGraph.h.

References insertEdge().

Referenced by removeDeadFunction(), and llvm::InlinerPass::run().

◆ lookup()

Node* llvm::LazyCallGraph::lookup ( const Function F) const
inline

Lookup a function in the graph which has already been scanned and added.

Definition at line 963 of file LazyCallGraph.h.

Referenced by llvm::InlinerPass::run(), and llvm::updateCGAndAnalysisManagerForFunctionPass().

◆ lookupRefSCC()

RefSCC* llvm::LazyCallGraph::lookupRefSCC ( Node N) const
inline

◆ lookupSCC()

SCC* llvm::LazyCallGraph::lookupSCC ( Node N) const
inline

◆ operator=()

LazyCallGraph & LazyCallGraph::operator= ( LazyCallGraph &&  RHS)

◆ postorder_ref_scc_begin()

postorder_ref_scc_iterator llvm::LazyCallGraph::postorder_ref_scc_begin ( )
inline

◆ postorder_ref_scc_end()

postorder_ref_scc_iterator llvm::LazyCallGraph::postorder_ref_scc_end ( )
inline

◆ postorder_ref_sccs()

iterator_range<postorder_ref_scc_iterator> llvm::LazyCallGraph::postorder_ref_sccs ( )
inline

◆ removeDeadFunction()

void LazyCallGraph::removeDeadFunction ( Function F)

Remove a dead function from the call graph (typically to delete it).

Note that the function must have an empty use list, and the call graph must be up-to-date prior to calling this. That means it is by itself in a maximal SCC which is by itself in a maximal RefSCC, etc. No structural changes result from calling this routine other than potentially removing entry points into the call graph.

If SCC formation has begun, this function must not be part of the current DFS in order to call this safely. Typically, the function will have been fully visited by the DFS prior to calling this routine.

Definition at line 1478 of file LazyCallGraph.cpp.

References assert(), C, llvm::LazyCallGraph::EdgeSequence::call_begin(), llvm::LazyCallGraph::EdgeSequence::call_end(), E, llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorImpl< T >::erase(), F(), llvm::find_if(), I, isLibFunction(), llvm::make_range(), N, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SmallVectorTemplateCommon< T >::rbegin(), llvm::reverse(), llvm::AMDGPU::HSAMD::Kernel::Arg::Key::Size, llvm::LazyCallGraph::RefSCC::size(), and llvm::Value::use_empty().

Referenced by removeEdge(), and llvm::InlinerPass::run().

◆ removeEdge() [1/2]

void LazyCallGraph::removeEdge ( Node SourceN,
Node TargetN 
)

Update the call graph after deleting an edge.

Definition at line 1469 of file LazyCallGraph.cpp.

References assert().

Referenced by insertEdge(), and removeEdge().

◆ removeEdge() [2/2]

void llvm::LazyCallGraph::removeEdge ( Function Source,
Function Target 
)
inline

Update the call graph after deleting an edge.

Definition at line 1031 of file LazyCallGraph.h.

References F(), removeDeadFunction(), and removeEdge().

◆ visitReferences()

template<typename CallbackT >
static void llvm::LazyCallGraph::visitReferences ( SmallVectorImpl< Constant *> &  Worklist,
SmallPtrSetImpl< Constant *> &  Visited,
CallbackT  Callback 
)
inlinestatic

The documentation for this class was generated from the following files: