class LazyCallGraph

Declaration

class LazyCallGraph { /* full declaration omitted */ };

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.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:110

Member Variables

private SpecificBumpPtrAllocator< llvm::LazyCallGraph::Node> BPA: Allocator that holds all the call graph nodes.
private DenseMap<const llvm::Function*, llvm::LazyCallGraph::Node*> NodeMap: Maps function->node for fast lookup.
private llvm::LazyCallGraph::EdgeSequence EntryEdges: These edges are from "external" sources. Put another way, they escape at the module scope.
private SpecificBumpPtrAllocator<llvm::LazyCallGraph::SCC> SCCBPA: Allocator that holds all the call graph SCCs.
private DenseMap<llvm::LazyCallGraph::Node*, llvm::LazyCallGraph::SCC*> SCCMap: Maps Function -> SCC for fast lookup.
private SpecificBumpPtrAllocator< llvm::LazyCallGraph::RefSCC> RefSCCBPA: Allocator that holds all the call graph RefSCCs.
private SmallVector<llvm::LazyCallGraph::RefSCC*, 16> PostOrderRefSCCs: This list is lazily formed the first time we walk the graph.
private DenseMap<llvm::LazyCallGraph::RefSCC*, int> RefSCCIndices: A map from RefSCC to the index for it in the postorder sequence of RefSCCs.
private SmallSetVector<llvm::Function*, 4> LibFunctions: Defined functions that are also known library functions which the optimizer can reason about and therefore might introduce calls to out of thin air.

Method Overview

public LazyCallGraph(llvm::LazyCallGraph && G)
public LazyCallGraph(llvm::Module & M, function_ref<llvm::TargetLibraryInfo &(llvm::Function &)> GetTLI)
public void addSplitFunction(llvm::Function & OriginalFunction, llvm::Function & NewFunction)
public void addSplitRefRecursiveFunctions(llvm::Function & OriginalFunction, ArrayRef<llvm::Function *> NewFunctions)
public EdgeSequence::iterator begin()
private template <typename RootsT, typename GetBeginT, typename GetEndT, typename GetNodeT, typename FormSCCCallbackT>static void buildGenericSCCs(RootsT && Roots, GetBeginT && GetBegin, GetEndT && GetEnd, GetNodeT && GetNode, FormSCCCallbackT && FormSCC)
public void buildRefSCCs()
private void buildSCCs(llvm::LazyCallGraph::RefSCC & RC, llvm::LazyCallGraph::node_stack_range Nodes)
private template <typename... Ts>llvm::LazyCallGraph::RefSCC * createRefSCC(Ts &&... Args)
private template <typename... Ts>llvm::LazyCallGraph::SCC * createSCC(Ts &&... Args)
public EdgeSequence::iterator end()
public llvm::LazyCallGraph::Node & get(llvm::Function & F)
public ArrayRef<llvm::Function *> getLibFunctions() const
private int getRefSCCIndex(llvm::LazyCallGraph::RefSCC & RC)
private llvm::LazyCallGraph::Node & initNode(llvm::Function & F)
public void insertEdge(llvm::LazyCallGraph::Node & SourceN, llvm::LazyCallGraph::Node & TargetN, Edge::Kind EK)
public void insertEdge(llvm::Function & Source, llvm::Function & Target, Edge::Kind EK)
private llvm::LazyCallGraph::Node & insertInto(llvm::Function & F, llvm::LazyCallGraph::Node *& MappedN)
public bool invalidate(llvm::Module &, const llvm::PreservedAnalyses & PA, ModuleAnalysisManager::Invalidator &)
public bool isLibFunction(llvm::Function & F) const
public llvm::LazyCallGraph::Node * lookup(const llvm::Function & F) const
public llvm::LazyCallGraph::RefSCC * lookupRefSCC(llvm::LazyCallGraph::Node & N) const
public llvm::LazyCallGraph::SCC * lookupSCC(llvm::LazyCallGraph::Node & N) const
public llvm::LazyCallGraph::postorder_ref_scc_iterator postorder_ref_scc_begin()
public llvm::LazyCallGraph::postorder_ref_scc_iterator postorder_ref_scc_end()
public iterator_range<llvm::LazyCallGraph::postorder_ref_scc_iterator> postorder_ref_sccs()
public void removeDeadFunction(llvm::Function & F)
public void removeEdge(llvm::Function & Source, llvm::Function & Target)
public void removeEdge(llvm::LazyCallGraph::Node & SourceN, llvm::LazyCallGraph::Node & TargetN)
private void updateGraphPtrs()
public static void visitReferences(SmallVectorImpl<llvm::Constant *> & Worklist, SmallPtrSetImpl<llvm::Constant *> & Visited, function_ref<void (llvm::Function &)> Callback)

Methods

¶LazyCallGraph(llvm::LazyCallGraph&& G)

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:935

Parameters

llvm::LazyCallGraph&& G

¶LazyCallGraph(
    llvm::Module& M,
    function_ref<llvm::TargetLibraryInfo&(
        llvm::Function&)> GetTLI)

Description

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.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:932

Parameters

llvm::Module& M
function_ref<llvm::TargetLibraryInfo&( llvm::Function&)> GetTLI

¶void addSplitFunction(
    llvm::Function& OriginalFunction,
    llvm::Function& NewFunction)

Description

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.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1070

Parameters

llvm::Function& OriginalFunction
llvm::Function& NewFunction

¶void addSplitRefRecursiveFunctions(
    llvm::Function& OriginalFunction,
    ArrayRef<llvm::Function*> NewFunctions)

Description

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.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1080

Parameters

llvm::Function& OriginalFunction
ArrayRef<llvm::Function*> NewFunctions

¶EdgeSequence::iterator begin()

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:941

¶template <typename RootsT,
          typename GetBeginT,
          typename GetEndT,
          typename GetNodeT,
          typename FormSCCCallbackT>
static void buildGenericSCCs(
    RootsT&& Roots,
    GetBeginT&& GetBegin,
    GetEndT&& GetEnd,
    GetNodeT&& GetNode,
    FormSCCCallbackT&& FormSCC)

Description

Common logic for building SCCs from a sequence of roots. This is a very generic implementation of the depth-first walk and SCC formation algorithm. It uses a generic sequence of roots and generic callbacks for each step. This is designed to be used to implement both the RefSCC formation and SCC formation with shared logic. Currently this is a relatively naive implementation of Tarjan's DFS algorithm to form the SCCs. FIXME: We should consider newer variants such as Nuutila.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1183

Templates

RootsT
GetBeginT
GetEndT
GetNodeT
FormSCCCallbackT

Parameters

RootsT&& Roots
GetBeginT&& GetBegin
GetEndT&& GetEnd
GetNodeT&& GetNode
FormSCCCallbackT&& FormSCC

¶void buildRefSCCs()

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:944

¶void buildSCCs(
    llvm::LazyCallGraph::RefSCC& RC,
    llvm::LazyCallGraph::node_stack_range Nodes)

Description

Build the SCCs for a RefSCC out of a list of nodes.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1188

Parameters

llvm::LazyCallGraph::RefSCC& RC
llvm::LazyCallGraph::node_stack_range Nodes

¶template <typename... Ts>
llvm::LazyCallGraph::RefSCC* createRefSCC(
    Ts&&... Args)

Description

Allocates a RefSCC and constructs it using the graph allocator. The arguments are forwarded to the constructor.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1166

Templates

Ts

Parameters

Ts&&... Args

¶template <typename... Ts>
llvm::LazyCallGraph::SCC* createSCC(Ts&&... Args)

Description

Allocates an SCC and constructs it using the graph allocator. The arguments are forwarded to the constructor.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1159

Templates

Ts

Parameters

Ts&&... Args

¶EdgeSequence::iterator end()

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:942

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

Description

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

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:986

Parameters

llvm::Function& F

¶ArrayRef<llvm::Function*> getLibFunctions() const

Description

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.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:998

¶int getRefSCCIndex(
    llvm::LazyCallGraph::RefSCC& RC)

Description

Get the index of a RefSCC within the postorder traversal. Requires that this RefSCC is a valid one in the (perhaps partial) postorder traversed part of the graph.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1194

Parameters

llvm::LazyCallGraph::RefSCC& RC

¶llvm::LazyCallGraph::Node& initNode(
    llvm::Function& F)

Description

Helper to initialize a new node created outside of creating SCCs and add it to the NodeMap if necessary. For example, useful when a function is split.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1151

Parameters

llvm::Function& F

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

Description

Update the call graph after inserting a new edge.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1022

Parameters

llvm::LazyCallGraph::Node& SourceN
llvm::LazyCallGraph::Node& TargetN
Edge::Kind EK

¶void insertEdge(llvm::Function& Source,
                llvm::Function& Target,
                Edge::Kind EK)

Description

Update the call graph after inserting a new edge.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1025

Parameters

llvm::Function& Source
llvm::Function& Target
Edge::Kind EK

¶llvm::LazyCallGraph::Node& insertInto(
    llvm::Function& F,
    llvm::LazyCallGraph::Node*& MappedN)

Description

Helper to insert a new function, with an already looked-up entry in the NodeMap.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1146

Parameters

llvm::Function& F
llvm::LazyCallGraph::Node*& MappedN

¶bool invalidate(
    llvm::Module&,
    const llvm::PreservedAnalyses& PA,
    ModuleAnalysisManager::Invalidator&)

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:938

Parameters

llvm::Module&
const llvm::PreservedAnalyses& PA
ModuleAnalysisManager::Invalidator&

¶bool isLibFunction(llvm::Function& F) const

Description

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.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1008

Parameters

llvm::Function& F

¶llvm::LazyCallGraph::Node* lookup(
    const llvm::Function& F) const

Description

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

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:965

Parameters

const llvm::Function& F

¶llvm::LazyCallGraph::RefSCC* lookupRefSCC(
    llvm::LazyCallGraph::Node& N) const

Description

Lookup a function's RefSCC in the graph.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:977

Parameters

llvm::LazyCallGraph::Node& N

Returns

null if the function hasn't been assigned a RefSCC via the RefSCC iterator walk.

¶llvm::LazyCallGraph::SCC* lookupSCC(
    llvm::LazyCallGraph::Node& N) const

Description

Lookup a function's SCC in the graph.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:971

Parameters

llvm::LazyCallGraph::Node& N

Returns

null if the function hasn't been assigned an SCC via the RefSCC iterator walk.

¶llvm::LazyCallGraph::postorder_ref_scc_iterator
postorder_ref_scc_begin()

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:946

¶llvm::LazyCallGraph::postorder_ref_scc_iterator
postorder_ref_scc_end()

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:952

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

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:960

¶void removeDeadFunction(llvm::Function& F)

Description

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.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1057

Parameters

llvm::Function& F

¶void removeEdge(llvm::Function& Source,
                llvm::Function& Target)

Description

Update the call graph after deleting an edge.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1033

Parameters

llvm::Function& Source
llvm::Function& Target

¶void removeEdge(
    llvm::LazyCallGraph::Node& SourceN,
    llvm::LazyCallGraph::Node& TargetN)

Description

Update the call graph after deleting an edge.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1030

Parameters

llvm::LazyCallGraph::Node& SourceN
llvm::LazyCallGraph::Node& TargetN

¶void updateGraphPtrs()

Description

Helper to update pointers back to the graph object during moves.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1154

¶static void visitReferences(
    SmallVectorImpl<llvm::Constant*>& Worklist,
    SmallPtrSetImpl<llvm::Constant*>& Visited,
    function_ref<void(llvm::Function&)> Callback)

Description

Recursively visits the defined functions whose address is reachable from every constant in the \p Worklist. Doesn't recurse through any constants already in the \p Visited set, and updates that set with every constant visited. For each defined function, calls \p Callback with that function.

Declared at: llvm/include/llvm/Analysis/LazyCallGraph.h:1099

Parameters

SmallVectorImpl<llvm::Constant*>& Worklist
SmallPtrSetImpl<llvm::Constant*>& Visited
function_ref<void(llvm::Function&)> Callback

class LazyCallGraph

Declaration

Description

Member Variables

Method Overview

Methods

¶LazyCallGraph(llvm::LazyCallGraph&& G)

Parameters

¶LazyCallGraph( llvm::Module& M, function_ref<llvm::TargetLibraryInfo&( llvm::Function&)> GetTLI)

Description

Parameters

¶void addSplitFunction( llvm::Function& OriginalFunction, llvm::Function& NewFunction)

Description

Parameters

¶void addSplitRefRecursiveFunctions( llvm::Function& OriginalFunction, ArrayRef<llvm::Function*> NewFunctions)

Description

Parameters

¶EdgeSequence::iterator begin()

¶template <typename RootsT, typename GetBeginT, typename GetEndT, typename GetNodeT, typename FormSCCCallbackT> static void buildGenericSCCs( RootsT&& Roots, GetBeginT&& GetBegin, GetEndT&& GetEnd, GetNodeT&& GetNode, FormSCCCallbackT&& FormSCC)

Description

Templates

Parameters

¶void buildRefSCCs()

¶void buildSCCs( llvm::LazyCallGraph::RefSCC& RC, llvm::LazyCallGraph::node_stack_range Nodes)

Description

Parameters

¶template <typename... Ts> llvm::LazyCallGraph::RefSCC* createRefSCC( Ts&&... Args)

Description

Templates

Parameters

¶template <typename... Ts> llvm::LazyCallGraph::SCC* createSCC(Ts&&... Args)

Description

Templates

Parameters

¶EdgeSequence::iterator end()

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

Description

Parameters

¶ArrayRef<llvm::Function*> getLibFunctions() const

Description

¶int getRefSCCIndex( llvm::LazyCallGraph::RefSCC& RC)

Description

Parameters

¶llvm::LazyCallGraph::Node& initNode( llvm::Function& F)

Description

Parameters

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

Description

Parameters

¶void insertEdge(llvm::Function& Source, llvm::Function& Target, Edge::Kind EK)

Description

Parameters

¶llvm::LazyCallGraph::Node& insertInto( llvm::Function& F, llvm::LazyCallGraph::Node*& MappedN)

Description

Parameters

¶bool invalidate( llvm::Module&, const llvm::PreservedAnalyses& PA, ModuleAnalysisManager::Invalidator&)

Parameters

¶bool isLibFunction(llvm::Function& F) const

Description

Parameters

¶llvm::LazyCallGraph::Node* lookup( const llvm::Function& F) const

Description

Parameters

¶llvm::LazyCallGraph::RefSCC* lookupRefSCC( llvm::LazyCallGraph::Node& N) const

Description

Parameters

Returns

¶llvm::LazyCallGraph::SCC* lookupSCC( llvm::LazyCallGraph::Node& N) const

Description

Parameters

Returns

¶llvm::LazyCallGraph::postorder_ref_scc_iterator postorder_ref_scc_begin()

¶llvm::LazyCallGraph::postorder_ref_scc_iterator postorder_ref_scc_end()

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

¶void removeDeadFunction(llvm::Function& F)

Description

Parameters

¶void removeEdge(llvm::Function& Source, llvm::Function& Target)

Description

Parameters

¶`LazyCallGraph(llvm::LazyCallGraph&& G)`

¶`LazyCallGraph( llvm::Module& M, function_ref<llvm::TargetLibraryInfo&( llvm::Function&)> GetTLI)`

¶`void addSplitFunction( llvm::Function& OriginalFunction, llvm::Function& NewFunction)`

¶`void addSplitRefRecursiveFunctions( llvm::Function& OriginalFunction, ArrayRef<llvm::Function*> NewFunctions)`

¶`EdgeSequence::iterator begin()`

¶`template <typename RootsT, typename GetBeginT, typename GetEndT, typename GetNodeT, typename FormSCCCallbackT> static void buildGenericSCCs( RootsT&& Roots, GetBeginT&& GetBegin, GetEndT&& GetEnd, GetNodeT&& GetNode, FormSCCCallbackT&& FormSCC)`

¶`void buildRefSCCs()`

¶`void buildSCCs( llvm::LazyCallGraph::RefSCC& RC, llvm::LazyCallGraph::node_stack_range Nodes)`

¶`template <typename... Ts> llvm::LazyCallGraph::RefSCC* createRefSCC( Ts&&... Args)`

¶`template <typename... Ts> llvm::LazyCallGraph::SCC* createSCC(Ts&&... Args)`

¶`EdgeSequence::iterator end()`

¶`llvm::LazyCallGraph::Node& get(llvm::Function& F)`

¶`ArrayRef<llvm::Function*> getLibFunctions() const`

¶`int getRefSCCIndex( llvm::LazyCallGraph::RefSCC& RC)`

¶`llvm::LazyCallGraph::Node& initNode( llvm::Function& F)`

¶`void insertEdge( llvm::LazyCallGraph::Node& SourceN, llvm::LazyCallGraph::Node& TargetN, Edge::Kind EK)`

¶`void insertEdge(llvm::Function& Source, llvm::Function& Target, Edge::Kind EK)`

¶`llvm::LazyCallGraph::Node& insertInto( llvm::Function& F, llvm::LazyCallGraph::Node*& MappedN)`

¶`bool invalidate( llvm::Module&, const llvm::PreservedAnalyses& PA, ModuleAnalysisManager::Invalidator&)`

¶`bool isLibFunction(llvm::Function& F) const`

¶`llvm::LazyCallGraph::Node* lookup( const llvm::Function& F) const`

¶`llvm::LazyCallGraph::RefSCC* lookupRefSCC( llvm::LazyCallGraph::Node& N) const`

¶`llvm::LazyCallGraph::SCC* lookupSCC( llvm::LazyCallGraph::Node& N) const`

¶`llvm::LazyCallGraph::postorder_ref_scc_iterator postorder_ref_scc_begin()`

¶`llvm::LazyCallGraph::postorder_ref_scc_iterator postorder_ref_scc_end()`

¶`iterator_range<llvm::LazyCallGraph:: postorder_ref_scc_iterator> postorder_ref_sccs()`

¶`void removeDeadFunction(llvm::Function& F)`

¶`void removeEdge(llvm::Function& Source, llvm::Function& Target)`

¶`void removeEdge( llvm::LazyCallGraph::Node& SourceN, llvm::LazyCallGraph::Node& TargetN)`

¶`void updateGraphPtrs()`

¶`static void visitReferences( SmallVectorImpl<llvm::Constant>& Worklist, SmallPtrSetImpl<llvm::Constant>& Visited, function_ref<void(llvm::Function&)> Callback)`