1 //===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// Implements a lazy call graph analysis and related passes for the new pass
14 /// NB: This is *not* a traditional call graph! It is a graph which models both
15 /// the current calls and potential calls. As a consequence there are many
16 /// edges in this call graph that do not correspond to a 'call' or 'invoke'
19 /// The primary use cases of this graph analysis is to facilitate iterating
20 /// across the functions of a module in ways that ensure all callees are
21 /// visited prior to a caller (given any SCC constraints), or vice versa. As
22 /// such is it particularly well suited to organizing CGSCC optimizations such
23 /// as inlining, outlining, argument promotion, etc. That is its primary use
24 /// case and motivates the design. It may not be appropriate for other
25 /// purposes. The use graph of functions or some other conservative analysis of
26 /// call instructions may be interesting for optimizations and subsequent
27 /// analyses which don't work in the context of an overly specified
28 /// potential-call-edge graph.
30 /// To understand the specific rules and nature of this call graph analysis,
31 /// see the documentation of the \c LazyCallGraph below.
33 //===----------------------------------------------------------------------===//
35 #ifndef LLVM_ANALYSIS_LAZY_CALL_GRAPH
36 #define LLVM_ANALYSIS_LAZY_CALL_GRAPH
38 #include "llvm/ADT/DenseMap.h"
39 #include "llvm/ADT/PointerUnion.h"
40 #include "llvm/ADT/STLExtras.h"
41 #include "llvm/ADT/SetVector.h"
42 #include "llvm/ADT/SmallPtrSet.h"
43 #include "llvm/ADT/SmallVector.h"
44 #include "llvm/ADT/iterator.h"
45 #include "llvm/ADT/iterator_range.h"
46 #include "llvm/IR/BasicBlock.h"
47 #include "llvm/IR/Function.h"
48 #include "llvm/IR/Module.h"
49 #include "llvm/Support/Allocator.h"
53 class ModuleAnalysisManager;
54 class PreservedAnalyses;
57 /// \brief A lazily constructed view of the call graph of a module.
59 /// With the edges of this graph, the motivating constraint that we are
60 /// attempting to maintain is that function-local optimization, CGSCC-local
61 /// optimizations, and optimizations transforming a pair of functions connected
62 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
63 /// DAG. That is, no optimizations will delete, remove, or add an edge such
64 /// that functions already visited in a bottom-up order of the SCC DAG are no
65 /// longer valid to have visited, or such that functions not yet visited in
66 /// a bottom-up order of the SCC DAG are not required to have already been
69 /// Within this constraint, the desire is to minimize the merge points of the
70 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
71 /// in the SCC DAG, the more independence there is in optimizing within it.
72 /// There is a strong desire to enable parallelization of optimizations over
73 /// the call graph, and both limited fanout and merge points will (artificially
74 /// in some cases) limit the scaling of such an effort.
76 /// To this end, graph represents both direct and any potential resolution to
77 /// an indirect call edge. Another way to think about it is that it represents
78 /// both the direct call edges and any direct call edges that might be formed
79 /// through static optimizations. Specifically, it considers taking the address
80 /// of a function to be an edge in the call graph because this might be
81 /// forwarded to become a direct call by some subsequent function-local
82 /// optimization. The result is that the graph closely follows the use-def
83 /// edges for functions. Walking "up" the graph can be done by looking at all
84 /// of the uses of a function.
86 /// The roots of the call graph are the external functions and functions
87 /// escaped into global variables. Those functions can be called from outside
88 /// of the module or via unknowable means in the IR -- we may not be able to
89 /// form even a potential call edge from a function body which may dynamically
90 /// load the function and call it.
92 /// This analysis still requires updates to remain valid after optimizations
93 /// which could potentially change the set of potential callees. The
94 /// constraints it operates under only make the traversal order remain valid.
96 /// The entire analysis must be re-computed if full interprocedural
97 /// optimizations run at any point. For example, globalopt completely
98 /// invalidates the information in this analysis.
100 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
101 /// it from the existing CallGraph. At some point, it is expected that this
102 /// will be the only call graph and it will be renamed accordingly.
103 class LazyCallGraph {
107 typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
108 typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;
110 /// \brief A lazy iterator used for both the entry nodes and child nodes.
112 /// When this iterator is dereferenced, if not yet available, a function will
113 /// be scanned for "calls" or uses of functions and its child information
114 /// will be constructed. All of these results are accumulated and cached in
116 class iterator : public iterator_adaptor_base<
117 iterator, NodeVectorImplT::iterator, Node> {
118 friend class LazyCallGraph;
119 friend class LazyCallGraph::Node;
122 NodeVectorImplT::iterator NI;
124 // Build the iterator for a specific position in a node list.
125 iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI)
126 : iterator_adaptor_base(NI), G(&G) {}
131 reference operator*() const {
133 return *I->get<Node *>();
135 Function *F = I->get<Function *>();
136 Node &ChildN = G->get(*F);
142 /// \brief A node in the call graph.
144 /// This represents a single node. It's primary roles are to cache the list of
145 /// callees, de-duplicate and provide fast testing of whether a function is
146 /// a callee, and facilitate iteration of child nodes in the graph.
148 friend class LazyCallGraph;
149 friend class LazyCallGraph::SCC;
154 // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
155 // stored directly within the node.
159 mutable NodeVectorT Callees;
160 DenseMap<Function *, size_t> CalleeIndexMap;
162 /// \brief Basic constructor implements the scanning of F into Callees and
164 Node(LazyCallGraph &G, Function &F);
166 /// \brief Internal helper to remove a callee from this node.
167 void removeEdgeInternal(Function &Callee);
170 typedef LazyCallGraph::iterator iterator;
172 Function &getFunction() const {
176 iterator begin() const { return iterator(*G, Callees.begin()); }
177 iterator end() const { return iterator(*G, Callees.end()); }
179 /// Equality is defined as address equality.
180 bool operator==(const Node &N) const { return this == &N; }
181 bool operator!=(const Node &N) const { return !operator==(N); }
184 /// \brief An SCC of the call graph.
186 /// This represents a Strongly Connected Component of the call graph as
187 /// a collection of call graph nodes. While the order of nodes in the SCC is
188 /// stable, it is not any particular order.
190 friend class LazyCallGraph;
191 friend class LazyCallGraph::Node;
194 SmallPtrSet<SCC *, 1> ParentSCCs;
195 SmallVector<Node *, 1> Nodes;
197 SCC(LazyCallGraph &G) : G(&G) {}
199 void insert(Node &N);
202 internalDFS(SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
203 SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
204 SmallVectorImpl<SCC *> &ResultSCCs);
207 typedef SmallVectorImpl<Node *>::const_iterator iterator;
208 typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> parent_iterator;
210 iterator begin() const { return Nodes.begin(); }
211 iterator end() const { return Nodes.end(); }
213 parent_iterator parent_begin() const { return ParentSCCs.begin(); }
214 parent_iterator parent_end() const { return ParentSCCs.end(); }
216 iterator_range<parent_iterator> parents() const {
217 return iterator_range<parent_iterator>(parent_begin(), parent_end());
221 /// \name Mutation API
223 /// These methods provide the core API for updating the call graph in the
224 /// presence of a (potentially still in-flight) DFS-found SCCs.
226 /// Note that these methods sometimes have complex runtimes, so be careful
227 /// how you call them.
229 /// \brief Remove an edge whose source is in this SCC and target is *not*.
231 /// This removes an inter-SCC edge. All inter-SCC edges originating from
232 /// this SCC have been fully explored by any in-flight DFS SCC formation,
233 /// so this is always safe to call once you have the source SCC.
235 /// This operation does not change the set of SCCs or the members of the
236 /// SCCs and so is very inexpensive. It may change the connectivity graph
237 /// of the SCCs though, so be careful calling this while iterating over
239 void removeInterSCCEdge(Node &CallerN, Node &CalleeN);
241 /// \brief Remove an edge which is entirely within this SCC.
243 /// Both the \a Caller and the \a Callee must be within this SCC. Removing
244 /// such an edge make break cycles that form this SCC and thus this
245 /// operation may change the SCC graph significantly. In particular, this
246 /// operation will re-form new SCCs based on the remaining connectivity of
247 /// the graph. The following invariants are guaranteed to hold after
248 /// calling this method:
250 /// 1) This SCC is still an SCC in the graph.
251 /// 2) This SCC will be the parent of any new SCCs. Thus, this SCC is
252 /// preserved as the root of any new SCC directed graph formed.
253 /// 3) No SCC other than this SCC has its member set changed (this is
254 /// inherent in the definiton of removing such an edge).
255 /// 4) All of the parent links of the SCC graph will be updated to reflect
256 /// the new SCC structure.
257 /// 5) All SCCs formed out of this SCC, excluding this SCC, will be
258 /// returned in a vector.
259 /// 6) The order of the SCCs in the vector will be a valid postorder
260 /// traversal of the new SCCs.
262 /// These invariants are very important to ensure that we can build
263 /// optimization pipeliens on top of the CGSCC pass manager which
264 /// intelligently update the SCC graph without invalidating other parts of
267 /// The runtime complexity of this method is, in the worst case, O(V+E)
268 /// where V is the number of nodes in this SCC and E is the number of edges
269 /// leaving the nodes in this SCC. Note that E includes both edges within
270 /// this SCC and edges from this SCC to child SCCs. Some effort has been
271 /// made to minimize the overhead of common cases such as self-edges and
272 /// edge removals which result in a spanning tree with no more cycles.
273 SmallVector<SCC *, 1> removeIntraSCCEdge(Node &CallerN, Node &CalleeN);
278 /// \brief A post-order depth-first SCC iterator over the call graph.
280 /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
281 /// the call graph, walking it lazily in depth-first post-order. That is, it
282 /// always visits SCCs for a callee prior to visiting the SCC for a caller
283 /// (when they are in different SCCs).
284 class postorder_scc_iterator
285 : public iterator_facade_base<postorder_scc_iterator,
286 std::forward_iterator_tag, SCC> {
287 friend class LazyCallGraph;
288 friend class LazyCallGraph::Node;
290 /// \brief Nonce type to select the constructor for the end iterator.
296 // Build the begin iterator for a node.
297 postorder_scc_iterator(LazyCallGraph &G) : G(&G) {
298 C = G.getNextSCCInPostOrder();
301 // Build the end iterator for a node. This is selected purely by overload.
302 postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
303 : G(&G), C(nullptr) {}
306 bool operator==(const postorder_scc_iterator &Arg) const {
307 return G == Arg.G && C == Arg.C;
310 reference operator*() const { return *C; }
312 using iterator_facade_base::operator++;
313 postorder_scc_iterator &operator++() {
314 C = G->getNextSCCInPostOrder();
319 /// \brief Construct a graph for the given module.
321 /// This sets up the graph and computes all of the entry points of the graph.
322 /// No function definitions are scanned until their nodes in the graph are
323 /// requested during traversal.
324 LazyCallGraph(Module &M);
326 LazyCallGraph(LazyCallGraph &&G);
327 LazyCallGraph &operator=(LazyCallGraph &&RHS);
329 iterator begin() { return iterator(*this, EntryNodes.begin()); }
330 iterator end() { return iterator(*this, EntryNodes.end()); }
332 postorder_scc_iterator postorder_scc_begin() {
333 return postorder_scc_iterator(*this);
335 postorder_scc_iterator postorder_scc_end() {
336 return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
339 iterator_range<postorder_scc_iterator> postorder_sccs() {
340 return iterator_range<postorder_scc_iterator>(postorder_scc_begin(),
341 postorder_scc_end());
344 /// \brief Lookup a function in the graph which has already been scanned and
346 Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
348 /// \brief Lookup a function's SCC in the graph.
350 /// \returns null if the function hasn't been assigned an SCC via the SCC
352 SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
354 /// \brief Get a graph node for a given function, scanning it to populate the
355 /// graph data as necessary.
356 Node &get(Function &F) {
357 Node *&N = NodeMap[&F];
361 return insertInto(F, N);
365 /// \name Pre-SCC Mutation API
367 /// These methods are only valid to call prior to forming any SCCs for this
368 /// call graph. They can be used to update the core node-graph during
369 /// a node-based inorder traversal that precedes any SCC-based traversal.
371 /// Once you begin manipulating a call graph's SCCs, you must perform all
372 /// mutation of the graph via the SCC methods.
374 /// \brief Update the call graph after deleting an edge.
375 void removeEdge(Node &Caller, Function &Callee);
377 /// \brief Update the call graph after deleting an edge.
378 void removeEdge(Function &Caller, Function &Callee) {
379 return removeEdge(get(Caller), Callee);
385 /// \brief Allocator that holds all the call graph nodes.
386 SpecificBumpPtrAllocator<Node> BPA;
388 /// \brief Maps function->node for fast lookup.
389 DenseMap<const Function *, Node *> NodeMap;
391 /// \brief The entry nodes to the graph.
393 /// These nodes are reachable through "external" means. Put another way, they
394 /// escape at the module scope.
395 NodeVectorT EntryNodes;
397 /// \brief Map of the entry nodes in the graph to their indices in
399 DenseMap<Function *, size_t> EntryIndexMap;
401 /// \brief Allocator that holds all the call graph SCCs.
402 SpecificBumpPtrAllocator<SCC> SCCBPA;
404 /// \brief Maps Function -> SCC for fast lookup.
405 DenseMap<Node *, SCC *> SCCMap;
407 /// \brief The leaf SCCs of the graph.
409 /// These are all of the SCCs which have no children.
410 SmallVector<SCC *, 4> LeafSCCs;
412 /// \brief Stack of nodes in the DFS walk.
413 SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
415 /// \brief Set of entry nodes not-yet-processed into SCCs.
416 SmallVector<Function *, 4> SCCEntryNodes;
418 /// \brief Stack of nodes the DFS has walked but not yet put into a SCC.
419 SmallVector<Node *, 4> PendingSCCStack;
421 /// \brief Counter for the next DFS number to assign.
424 /// \brief Helper to insert a new function, with an already looked-up entry in
426 Node &insertInto(Function &F, Node *&MappedN);
428 /// \brief Helper to update pointers back to the graph object during moves.
429 void updateGraphPtrs();
431 /// \brief Helper to form a new SCC out of the top of a DFSStack-like
433 SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack);
435 /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
436 SCC *getNextSCCInPostOrder();
439 // Provide GraphTraits specializations for call graphs.
440 template <> struct GraphTraits<LazyCallGraph::Node *> {
441 typedef LazyCallGraph::Node NodeType;
442 typedef LazyCallGraph::iterator ChildIteratorType;
444 static NodeType *getEntryNode(NodeType *N) { return N; }
445 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
446 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
448 template <> struct GraphTraits<LazyCallGraph *> {
449 typedef LazyCallGraph::Node NodeType;
450 typedef LazyCallGraph::iterator ChildIteratorType;
452 static NodeType *getEntryNode(NodeType *N) { return N; }
453 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
454 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
457 /// \brief An analysis pass which computes the call graph for a module.
458 class LazyCallGraphAnalysis {
460 /// \brief Inform generic clients of the result type.
461 typedef LazyCallGraph Result;
463 static void *ID() { return (void *)&PassID; }
465 /// \brief Compute the \c LazyCallGraph for a the module \c M.
467 /// This just builds the set of entry points to the call graph. The rest is
468 /// built lazily as it is walked.
469 LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
475 /// \brief A pass which prints the call graph to a \c raw_ostream.
477 /// This is primarily useful for testing the analysis.
478 class LazyCallGraphPrinterPass {
482 explicit LazyCallGraphPrinterPass(raw_ostream &OS);
484 PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
486 static StringRef name() { return "LazyCallGraphPrinterPass"; }