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_LAZYCALLGRAPH_H
36 #define LLVM_ANALYSIS_LAZYCALLGRAPH_H
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/IR/PassManager.h"
50 #include "llvm/Support/Allocator.h"
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
117 : public iterator_adaptor_base
<iterator
, NodeVectorImplT::iterator
,
118 std::forward_iterator_tag
, Node
> {
119 friend class LazyCallGraph
;
120 friend class LazyCallGraph::Node
;
123 NodeVectorImplT::iterator E
;
125 // Build the iterator for a specific position in a node list.
126 iterator(LazyCallGraph
&G
, NodeVectorImplT::iterator NI
,
127 NodeVectorImplT::iterator E
)
128 : iterator_adaptor_base(NI
), G(&G
), E(E
) {
129 while (I
!= E
&& I
->isNull())
136 using iterator_adaptor_base::operator++;
137 iterator
&operator++() {
140 } while (I
!= E
&& I
->isNull());
144 reference
operator*() const {
146 return *I
->get
<Node
*>();
148 Function
*F
= I
->get
<Function
*>();
149 Node
&ChildN
= G
->get(*F
);
155 /// \brief A node in the call graph.
157 /// This represents a single node. It's primary roles are to cache the list of
158 /// callees, de-duplicate and provide fast testing of whether a function is
159 /// a callee, and facilitate iteration of child nodes in the graph.
161 friend class LazyCallGraph
;
162 friend class LazyCallGraph::SCC
;
167 // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
168 // stored directly within the node.
172 mutable NodeVectorT Callees
;
173 DenseMap
<Function
*, size_t> CalleeIndexMap
;
175 /// \brief Basic constructor implements the scanning of F into Callees and
177 Node(LazyCallGraph
&G
, Function
&F
);
179 /// \brief Internal helper to insert a callee.
180 void insertEdgeInternal(Function
&Callee
);
182 /// \brief Internal helper to insert a callee.
183 void insertEdgeInternal(Node
&CalleeN
);
185 /// \brief Internal helper to remove a callee from this node.
186 void removeEdgeInternal(Function
&Callee
);
189 typedef LazyCallGraph::iterator iterator
;
191 Function
&getFunction() const {
195 iterator
begin() const {
196 return iterator(*G
, Callees
.begin(), Callees
.end());
198 iterator
end() const { return iterator(*G
, Callees
.end(), Callees
.end()); }
200 /// Equality is defined as address equality.
201 bool operator==(const Node
&N
) const { return this == &N
; }
202 bool operator!=(const Node
&N
) const { return !operator==(N
); }
205 /// \brief An SCC of the call graph.
207 /// This represents a Strongly Connected Component of the call graph as
208 /// a collection of call graph nodes. While the order of nodes in the SCC is
209 /// stable, it is not any particular order.
211 friend class LazyCallGraph
;
212 friend class LazyCallGraph::Node
;
215 SmallPtrSet
<SCC
*, 1> ParentSCCs
;
216 SmallVector
<Node
*, 1> Nodes
;
218 SCC(LazyCallGraph
&G
) : G(&G
) {}
220 void insert(Node
&N
);
223 internalDFS(SmallVectorImpl
<std::pair
<Node
*, Node::iterator
>> &DFSStack
,
224 SmallVectorImpl
<Node
*> &PendingSCCStack
, Node
*N
,
225 SmallVectorImpl
<SCC
*> &ResultSCCs
);
228 typedef SmallVectorImpl
<Node
*>::const_iterator iterator
;
229 typedef pointee_iterator
<SmallPtrSet
<SCC
*, 1>::const_iterator
> parent_iterator
;
231 iterator
begin() const { return Nodes
.begin(); }
232 iterator
end() const { return Nodes
.end(); }
234 parent_iterator
parent_begin() const { return ParentSCCs
.begin(); }
235 parent_iterator
parent_end() const { return ParentSCCs
.end(); }
237 iterator_range
<parent_iterator
> parents() const {
238 return iterator_range
<parent_iterator
>(parent_begin(), parent_end());
241 /// \brief Test if this SCC is a parent of \a C.
242 bool isParentOf(const SCC
&C
) const { return C
.isChildOf(*this); }
244 /// \brief Test if this SCC is an ancestor of \a C.
245 bool isAncestorOf(const SCC
&C
) const { return C
.isDescendantOf(*this); }
247 /// \brief Test if this SCC is a child of \a C.
248 bool isChildOf(const SCC
&C
) const {
249 return ParentSCCs
.count(const_cast<SCC
*>(&C
));
252 /// \brief Test if this SCC is a descendant of \a C.
253 bool isDescendantOf(const SCC
&C
) const;
255 /// \brief Short name useful for debugging or logging.
257 /// We use the name of the first function in the SCC to name the SCC for
258 /// the purposes of debugging and logging.
259 StringRef
getName() const { return (*begin())->getFunction().getName(); }
262 /// \name Mutation API
264 /// These methods provide the core API for updating the call graph in the
265 /// presence of a (potentially still in-flight) DFS-found SCCs.
267 /// Note that these methods sometimes have complex runtimes, so be careful
268 /// how you call them.
270 /// \brief Insert an edge from one node in this SCC to another in this SCC.
272 /// By the definition of an SCC, this does not change the nature or make-up
274 void insertIntraSCCEdge(Node
&CallerN
, Node
&CalleeN
);
276 /// \brief Insert an edge whose tail is in this SCC and head is in some
279 /// There must be an existing path from the caller to the callee. This
280 /// operation is inexpensive and does not change the set of SCCs in the
282 void insertOutgoingEdge(Node
&CallerN
, Node
&CalleeN
);
284 /// \brief Insert an edge whose tail is in a descendant SCC and head is in
287 /// There must be an existing path from the callee to the caller in this
288 /// case. NB! This is has the potential to be a very expensive function. It
289 /// inherently forms a cycle in the prior SCC DAG and we have to merge SCCs
290 /// to resolve that cycle. But finding all of the SCCs which participate in
291 /// the cycle can in the worst case require traversing every SCC in the
292 /// graph. Every attempt is made to avoid that, but passes must still
293 /// exercise caution calling this routine repeatedly.
295 /// FIXME: We could possibly optimize this quite a bit for cases where the
296 /// caller and callee are very nearby in the graph. See comments in the
297 /// implementation for details, but that use case might impact users.
298 SmallVector
<SCC
*, 1> insertIncomingEdge(Node
&CallerN
, Node
&CalleeN
);
300 /// \brief Remove an edge whose source is in this SCC and target is *not*.
302 /// This removes an inter-SCC edge. All inter-SCC edges originating from
303 /// this SCC have been fully explored by any in-flight DFS SCC formation,
304 /// so this is always safe to call once you have the source SCC.
306 /// This operation does not change the set of SCCs or the members of the
307 /// SCCs and so is very inexpensive. It may change the connectivity graph
308 /// of the SCCs though, so be careful calling this while iterating over
310 void removeInterSCCEdge(Node
&CallerN
, Node
&CalleeN
);
312 /// \brief Remove an edge which is entirely within this SCC.
314 /// Both the \a Caller and the \a Callee must be within this SCC. Removing
315 /// such an edge make break cycles that form this SCC and thus this
316 /// operation may change the SCC graph significantly. In particular, this
317 /// operation will re-form new SCCs based on the remaining connectivity of
318 /// the graph. The following invariants are guaranteed to hold after
319 /// calling this method:
321 /// 1) This SCC is still an SCC in the graph.
322 /// 2) This SCC will be the parent of any new SCCs. Thus, this SCC is
323 /// preserved as the root of any new SCC directed graph formed.
324 /// 3) No SCC other than this SCC has its member set changed (this is
325 /// inherent in the definition of removing such an edge).
326 /// 4) All of the parent links of the SCC graph will be updated to reflect
327 /// the new SCC structure.
328 /// 5) All SCCs formed out of this SCC, excluding this SCC, will be
329 /// returned in a vector.
330 /// 6) The order of the SCCs in the vector will be a valid postorder
331 /// traversal of the new SCCs.
333 /// These invariants are very important to ensure that we can build
334 /// optimization pipeliens on top of the CGSCC pass manager which
335 /// intelligently update the SCC graph without invalidating other parts of
338 /// The runtime complexity of this method is, in the worst case, O(V+E)
339 /// where V is the number of nodes in this SCC and E is the number of edges
340 /// leaving the nodes in this SCC. Note that E includes both edges within
341 /// this SCC and edges from this SCC to child SCCs. Some effort has been
342 /// made to minimize the overhead of common cases such as self-edges and
343 /// edge removals which result in a spanning tree with no more cycles.
344 SmallVector
<SCC
*, 1> removeIntraSCCEdge(Node
&CallerN
, Node
&CalleeN
);
349 /// \brief A post-order depth-first SCC iterator over the call graph.
351 /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
352 /// the call graph, walking it lazily in depth-first post-order. That is, it
353 /// always visits SCCs for a callee prior to visiting the SCC for a caller
354 /// (when they are in different SCCs).
355 class postorder_scc_iterator
356 : public iterator_facade_base
<postorder_scc_iterator
,
357 std::forward_iterator_tag
, SCC
> {
358 friend class LazyCallGraph
;
359 friend class LazyCallGraph::Node
;
361 /// \brief Nonce type to select the constructor for the end iterator.
367 // Build the begin iterator for a node.
368 postorder_scc_iterator(LazyCallGraph
&G
) : G(&G
) {
369 C
= G
.getNextSCCInPostOrder();
372 // Build the end iterator for a node. This is selected purely by overload.
373 postorder_scc_iterator(LazyCallGraph
&G
, IsAtEndT
/*Nonce*/)
374 : G(&G
), C(nullptr) {}
377 bool operator==(const postorder_scc_iterator
&Arg
) const {
378 return G
== Arg
.G
&& C
== Arg
.C
;
381 reference
operator*() const { return *C
; }
383 using iterator_facade_base::operator++;
384 postorder_scc_iterator
&operator++() {
385 C
= G
->getNextSCCInPostOrder();
390 /// \brief Construct a graph for the given module.
392 /// This sets up the graph and computes all of the entry points of the graph.
393 /// No function definitions are scanned until their nodes in the graph are
394 /// requested during traversal.
395 LazyCallGraph(Module
&M
);
397 LazyCallGraph(LazyCallGraph
&&G
);
398 LazyCallGraph
&operator=(LazyCallGraph
&&RHS
);
401 return iterator(*this, EntryNodes
.begin(), EntryNodes
.end());
403 iterator
end() { return iterator(*this, EntryNodes
.end(), EntryNodes
.end()); }
405 postorder_scc_iterator
postorder_scc_begin() {
406 return postorder_scc_iterator(*this);
408 postorder_scc_iterator
postorder_scc_end() {
409 return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
412 iterator_range
<postorder_scc_iterator
> postorder_sccs() {
413 return iterator_range
<postorder_scc_iterator
>(postorder_scc_begin(),
414 postorder_scc_end());
417 /// \brief Lookup a function in the graph which has already been scanned and
419 Node
*lookup(const Function
&F
) const { return NodeMap
.lookup(&F
); }
421 /// \brief Lookup a function's SCC in the graph.
423 /// \returns null if the function hasn't been assigned an SCC via the SCC
425 SCC
*lookupSCC(Node
&N
) const { return SCCMap
.lookup(&N
); }
427 /// \brief Get a graph node for a given function, scanning it to populate the
428 /// graph data as necessary.
429 Node
&get(Function
&F
) {
430 Node
*&N
= NodeMap
[&F
];
434 return insertInto(F
, N
);
438 /// \name Pre-SCC Mutation API
440 /// These methods are only valid to call prior to forming any SCCs for this
441 /// call graph. They can be used to update the core node-graph during
442 /// a node-based inorder traversal that precedes any SCC-based traversal.
444 /// Once you begin manipulating a call graph's SCCs, you must perform all
445 /// mutation of the graph via the SCC methods.
447 /// \brief Update the call graph after inserting a new edge.
448 void insertEdge(Node
&Caller
, Function
&Callee
);
450 /// \brief Update the call graph after inserting a new edge.
451 void insertEdge(Function
&Caller
, Function
&Callee
) {
452 return insertEdge(get(Caller
), Callee
);
455 /// \brief Update the call graph after deleting an edge.
456 void removeEdge(Node
&Caller
, Function
&Callee
);
458 /// \brief Update the call graph after deleting an edge.
459 void removeEdge(Function
&Caller
, Function
&Callee
) {
460 return removeEdge(get(Caller
), Callee
);
466 /// \brief Allocator that holds all the call graph nodes.
467 SpecificBumpPtrAllocator
<Node
> BPA
;
469 /// \brief Maps function->node for fast lookup.
470 DenseMap
<const Function
*, Node
*> NodeMap
;
472 /// \brief The entry nodes to the graph.
474 /// These nodes are reachable through "external" means. Put another way, they
475 /// escape at the module scope.
476 NodeVectorT EntryNodes
;
478 /// \brief Map of the entry nodes in the graph to their indices in
480 DenseMap
<Function
*, size_t> EntryIndexMap
;
482 /// \brief Allocator that holds all the call graph SCCs.
483 SpecificBumpPtrAllocator
<SCC
> SCCBPA
;
485 /// \brief Maps Function -> SCC for fast lookup.
486 DenseMap
<Node
*, SCC
*> SCCMap
;
488 /// \brief The leaf SCCs of the graph.
490 /// These are all of the SCCs which have no children.
491 SmallVector
<SCC
*, 4> LeafSCCs
;
493 /// \brief Stack of nodes in the DFS walk.
494 SmallVector
<std::pair
<Node
*, iterator
>, 4> DFSStack
;
496 /// \brief Set of entry nodes not-yet-processed into SCCs.
497 SmallVector
<Function
*, 4> SCCEntryNodes
;
499 /// \brief Stack of nodes the DFS has walked but not yet put into a SCC.
500 SmallVector
<Node
*, 4> PendingSCCStack
;
502 /// \brief Counter for the next DFS number to assign.
505 /// \brief Helper to insert a new function, with an already looked-up entry in
507 Node
&insertInto(Function
&F
, Node
*&MappedN
);
509 /// \brief Helper to update pointers back to the graph object during moves.
510 void updateGraphPtrs();
512 /// \brief Helper to form a new SCC out of the top of a DFSStack-like
514 SCC
*formSCC(Node
*RootN
, SmallVectorImpl
<Node
*> &NodeStack
);
516 /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
517 SCC
*getNextSCCInPostOrder();
520 // Provide GraphTraits specializations for call graphs.
521 template <> struct GraphTraits
<LazyCallGraph::Node
*> {
522 typedef LazyCallGraph::Node NodeType
;
523 typedef LazyCallGraph::iterator ChildIteratorType
;
525 static NodeType
*getEntryNode(NodeType
*N
) { return N
; }
526 static ChildIteratorType
child_begin(NodeType
*N
) { return N
->begin(); }
527 static ChildIteratorType
child_end(NodeType
*N
) { return N
->end(); }
529 template <> struct GraphTraits
<LazyCallGraph
*> {
530 typedef LazyCallGraph::Node NodeType
;
531 typedef LazyCallGraph::iterator ChildIteratorType
;
533 static NodeType
*getEntryNode(NodeType
*N
) { return N
; }
534 static ChildIteratorType
child_begin(NodeType
*N
) { return N
->begin(); }
535 static ChildIteratorType
child_end(NodeType
*N
) { return N
->end(); }
538 /// \brief An analysis pass which computes the call graph for a module.
539 class LazyCallGraphAnalysis
{
541 /// \brief Inform generic clients of the result type.
542 typedef LazyCallGraph Result
;
544 static void *ID() { return (void *)&PassID
; }
546 static StringRef
name() { return "Lazy CallGraph Analysis"; }
548 /// \brief Compute the \c LazyCallGraph for the module \c M.
550 /// This just builds the set of entry points to the call graph. The rest is
551 /// built lazily as it is walked.
552 LazyCallGraph
run(Module
&M
) { return LazyCallGraph(M
); }
558 /// \brief A pass which prints the call graph to a \c raw_ostream.
560 /// This is primarily useful for testing the analysis.
561 class LazyCallGraphPrinterPass
{
565 explicit LazyCallGraphPrinterPass(raw_ostream
&OS
);
567 PreservedAnalyses
run(Module
&M
, ModuleAnalysisManager
*AM
);
569 static StringRef
name() { return "LazyCallGraphPrinterPass"; }