A lazily constructed view of the call graph of a module. More...

#include <LazyCallGraph.h>

Classes
class	iterator
	A lazy iterator used for both the entry nodes and child nodes. More...
class	Node
	A node in the call graph. More...
class	postorder_scc_iterator
	A post-order depth-first SCC iterator over the call graph. More...
class	SCC
	An SCC of the call graph. More...
Public Types
typedef SmallVector < PointerUnion< Function , Node >, 4 >	NodeVectorT
typedef SmallVectorImpl < PointerUnion< Function , Node > >	NodeVectorImplT
Public Member Functions
	LazyCallGraph (Module &M)
	Construct a graph for the given module.
	LazyCallGraph (LazyCallGraph &&G)
LazyCallGraph &	operator= (LazyCallGraph &&RHS)
iterator	begin ()
iterator	end ()
postorder_scc_iterator	postorder_scc_begin ()
postorder_scc_iterator	postorder_scc_end ()
iterator_range < postorder_scc_iterator >	postorder_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.
Node &	get (Function &F)
	Get a graph node for a given function, scanning it to populate the graph data as necessary.
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, you must perform all mutation of the graph via the SCC methods.
void	insertEdge (Node &Caller, Function &Callee)
	Update the call graph after inserting a new edge.
void	insertEdge (Function &Caller, Function &Callee)
	Update the call graph after inserting a new edge.
void	removeEdge (Node &Caller, Function &Callee)
	Update the call graph after deleting an edge.
void	removeEdge (Function &Caller, Function &Callee)
	Update the call graph after deleting an edge.

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

Member Typedef Documentation

typedef SmallVectorImpl<PointerUnion<Function *, Node *> > llvm::LazyCallGraph::NodeVectorImplT

Definition at line 108 of file LazyCallGraph.h.

typedef SmallVector<PointerUnion<Function *, Node *>, 4> llvm::LazyCallGraph::NodeVectorT

Definition at line 106 of file LazyCallGraph.h.

Constructor & Destructor Documentation

LazyCallGraph::LazyCallGraph ( Module & M )

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

References llvm::dbgs(), DEBUG, findCallees(), llvm::LazyCallGraph::Node::getFunction(), llvm::Module::getModuleIdentifier(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), and llvm::SmallVectorTemplateCommon< T, typename >::size().