1 //===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
11 /// Implements a lazy call graph analysis and related passes for the new pass
12 /// manager.
13 ///
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'
17 /// instruction.
18 ///
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.
29 ///
30 /// To understand the specific rules and nature of this call graph analysis,
31 /// see the documentation of the \c LazyCallGraph below.
32 ///
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_range.h"
45 #include "llvm/IR/BasicBlock.h"
46 #include "llvm/IR/Function.h"
47 #include "llvm/IR/Module.h"
48 #include "llvm/Support/Allocator.h"
49 #include <iterator>
51 namespace llvm {
52 class ModuleAnalysisManager;
53 class PreservedAnalyses;
54 class raw_ostream;
56 /// \brief A lazily constructed view of the call graph of a module.
57 ///
58 /// With the edges of this graph, the motivating constraint that we are
59 /// attempting to maintain is that function-local optimization, CGSCC-local
60 /// optimizations, and optimizations transforming a pair of functions connected
61 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
62 /// DAG. That is, no optimizations will delete, remove, or add an edge such
63 /// that functions already visited in a bottom-up order of the SCC DAG are no
64 /// longer valid to have visited, or such that functions not yet visited in
65 /// a bottom-up order of the SCC DAG are not required to have already been
66 /// visited.
67 ///
68 /// Within this constraint, the desire is to minimize the merge points of the
69 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
70 /// in the SCC DAG, the more independence there is in optimizing within it.
71 /// There is a strong desire to enable parallelization of optimizations over
72 /// the call graph, and both limited fanout and merge points will (artificially
73 /// in some cases) limit the scaling of such an effort.
74 ///
75 /// To this end, graph represents both direct and any potential resolution to
76 /// an indirect call edge. Another way to think about it is that it represents
77 /// both the direct call edges and any direct call edges that might be formed
78 /// through static optimizations. Specifically, it considers taking the address
79 /// of a function to be an edge in the call graph because this might be
80 /// forwarded to become a direct call by some subsequent function-local
81 /// optimization. The result is that the graph closely follows the use-def
82 /// edges for functions. Walking "up" the graph can be done by looking at all
83 /// of the uses of a function.
84 ///
85 /// The roots of the call graph are the external functions and functions
86 /// escaped into global variables. Those functions can be called from outside
87 /// of the module or via unknowable means in the IR -- we may not be able to
88 /// form even a potential call edge from a function body which may dynamically
89 /// load the function and call it.
90 ///
91 /// This analysis still requires updates to remain valid after optimizations
92 /// which could potentially change the set of potential callees. The
93 /// constraints it operates under only make the traversal order remain valid.
94 ///
95 /// The entire analysis must be re-computed if full interprocedural
96 /// optimizations run at any point. For example, globalopt completely
97 /// invalidates the information in this analysis.
98 ///
99 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
100 /// it from the existing CallGraph. At some point, it is expected that this
101 /// will be the only call graph and it will be renamed accordingly.
102 class LazyCallGraph {
103 public:
104 class Node;
105 class SCC;
106 typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
107 typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;
109 /// \brief A lazy iterator used for both the entry nodes and child nodes.
110 ///
111 /// When this iterator is dereferenced, if not yet available, a function will
112 /// be scanned for "calls" or uses of functions and its child information
113 /// will be constructed. All of these results are accumulated and cached in
114 /// the graph.
115 class iterator : public std::iterator<std::bidirectional_iterator_tag, Node *,
116 ptrdiff_t, Node *, Node *> {
117 friend class LazyCallGraph;
118 friend class LazyCallGraph::Node;
119 typedef std::iterator<std::bidirectional_iterator_tag, Node *, ptrdiff_t,
120 Node *, Node *> BaseT;
122 /// \brief Nonce type to select the constructor for the end iterator.
123 struct IsAtEndT {};
125 LazyCallGraph *G;
126 NodeVectorImplT::iterator NI;
128 // Build the begin iterator for a node.
129 explicit iterator(LazyCallGraph &G, NodeVectorImplT &Nodes)
130 : G(&G), NI(Nodes.begin()) {}
132 // Build the end iterator for a node. This is selected purely by overload.
133 iterator(LazyCallGraph &G, NodeVectorImplT &Nodes, IsAtEndT /*Nonce*/)
134 : G(&G), NI(Nodes.end()) {}
136 public:
137 bool operator==(const iterator &Arg) const { return NI == Arg.NI; }
138 bool operator!=(const iterator &Arg) const { return !operator==(Arg); }
140 reference operator*() const {
141 if (NI->is<Node *>())
142 return NI->get<Node *>();
144 Function *F = NI->get<Function *>();
145 Node *ChildN = G->get(*F);
146 *NI = ChildN;
147 return ChildN;
148 }
149 pointer operator->() const { return operator*(); }
151 iterator &operator++() {
152 ++NI;
153 return *this;
154 }
155 iterator operator++(int) {
156 iterator prev = *this;
157 ++*this;
158 return prev;
159 }
161 iterator &operator--() {
162 --NI;
163 return *this;
164 }
165 iterator operator--(int) {
166 iterator next = *this;
167 --*this;
168 return next;
169 }
170 };
172 /// \brief A node in the call graph.
173 ///
174 /// This represents a single node. It's primary roles are to cache the list of
175 /// callees, de-duplicate and provide fast testing of whether a function is
176 /// a callee, and facilitate iteration of child nodes in the graph.
177 class Node {
178 friend class LazyCallGraph;
179 friend class LazyCallGraph::SCC;
181 LazyCallGraph *G;
182 Function &F;
184 // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
185 // stored directly within the node.
186 int DFSNumber;
187 int LowLink;
189 mutable NodeVectorT Callees;
190 DenseMap<Function *, size_t> CalleeIndexMap;
192 /// \brief Basic constructor implements the scanning of F into Callees and
193 /// CalleeIndexMap.
194 Node(LazyCallGraph &G, Function &F);
196 public:
197 typedef LazyCallGraph::iterator iterator;
199 Function &getFunction() const {
200 return F;
201 };
203 iterator begin() const { return iterator(*G, Callees); }
204 iterator end() const { return iterator(*G, Callees, iterator::IsAtEndT()); }
206 /// Equality is defined as address equality.
207 bool operator==(const Node &N) const { return this == &N; }
208 bool operator!=(const Node &N) const { return !operator==(N); }
209 };
211 /// \brief An SCC of the call graph.
212 ///
213 /// This represents a Strongly Connected Component of the call graph as
214 /// a collection of call graph nodes. While the order of nodes in the SCC is
215 /// stable, it is not any particular order.
216 class SCC {
217 friend class LazyCallGraph;
218 friend class LazyCallGraph::Node;
220 SmallSetVector<SCC *, 1> ParentSCCs;
221 SmallVector<Node *, 1> Nodes;
222 SmallPtrSet<Function *, 1> NodeSet;
224 SCC() {}
226 public:
227 typedef SmallVectorImpl<Node *>::const_iterator iterator;
229 iterator begin() const { return Nodes.begin(); }
230 iterator end() const { return Nodes.end(); }
231 };
233 /// \brief A post-order depth-first SCC iterator over the call graph.
234 ///
235 /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
236 /// the call graph, walking it lazily in depth-first post-order. That is, it
237 /// always visits SCCs for a callee prior to visiting the SCC for a caller
238 /// (when they are in different SCCs).
239 class postorder_scc_iterator
240 : public std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t, SCC *,
241 SCC *> {
242 friend class LazyCallGraph;
243 friend class LazyCallGraph::Node;
244 typedef std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t,
245 SCC *, SCC *> BaseT;
247 /// \brief Nonce type to select the constructor for the end iterator.
248 struct IsAtEndT {};
250 LazyCallGraph *G;
251 SCC *C;
253 // Build the begin iterator for a node.
254 postorder_scc_iterator(LazyCallGraph &G) : G(&G) {
255 C = G.getNextSCCInPostOrder();
256 }
258 // Build the end iterator for a node. This is selected purely by overload.
259 postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
260 : G(&G), C(nullptr) {}
262 public:
263 bool operator==(const postorder_scc_iterator &Arg) const {
264 return G == Arg.G && C == Arg.C;
265 }
266 bool operator!=(const postorder_scc_iterator &Arg) const {
267 return !operator==(Arg);
268 }
270 reference operator*() const { return C; }
271 pointer operator->() const { return operator*(); }
273 postorder_scc_iterator &operator++() {
274 C = G->getNextSCCInPostOrder();
275 return *this;
276 }
277 postorder_scc_iterator operator++(int) {
278 postorder_scc_iterator prev = *this;
279 ++*this;
280 return prev;
281 }
282 };
284 /// \brief Construct a graph for the given module.
285 ///
286 /// This sets up the graph and computes all of the entry points of the graph.
287 /// No function definitions are scanned until their nodes in the graph are
288 /// requested during traversal.
289 LazyCallGraph(Module &M);
291 LazyCallGraph(LazyCallGraph &&G);
292 LazyCallGraph &operator=(LazyCallGraph &&RHS);
294 iterator begin() { return iterator(*this, EntryNodes); }
295 iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
297 postorder_scc_iterator postorder_scc_begin() {
298 return postorder_scc_iterator(*this);
299 }
300 postorder_scc_iterator postorder_scc_end() {
301 return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
302 }
304 iterator_range<postorder_scc_iterator> postorder_sccs() {
305 return iterator_range<postorder_scc_iterator>(postorder_scc_begin(),
306 postorder_scc_end());
307 }
309 /// \brief Lookup a function in the graph which has already been scanned and
310 /// added.
311 Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
313 /// \brief Get a graph node for a given function, scanning it to populate the
314 /// graph data as necessary.
315 Node *get(Function &F) {
316 Node *&N = NodeMap[&F];
317 if (N)
318 return N;
320 return insertInto(F, N);
321 }
323 private:
324 /// \brief Allocator that holds all the call graph nodes.
325 SpecificBumpPtrAllocator<Node> BPA;
327 /// \brief Maps function->node for fast lookup.
328 DenseMap<const Function *, Node *> NodeMap;
330 /// \brief The entry nodes to the graph.
331 ///
332 /// These nodes are reachable through "external" means. Put another way, they
333 /// escape at the module scope.
334 NodeVectorT EntryNodes;
336 /// \brief Map of the entry nodes in the graph to their indices in
337 /// \c EntryNodes.
338 DenseMap<Function *, size_t> EntryIndexMap;
340 /// \brief Allocator that holds all the call graph SCCs.
341 SpecificBumpPtrAllocator<SCC> SCCBPA;
343 /// \brief Maps Function -> SCC for fast lookup.
344 DenseMap<const Function *, SCC *> SCCMap;
346 /// \brief The leaf SCCs of the graph.
347 ///
348 /// These are all of the SCCs which have no children.
349 SmallVector<SCC *, 4> LeafSCCs;
351 /// \brief Stack of nodes not-yet-processed into SCCs.
352 SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
354 /// \brief Set of entry nodes not-yet-processed into SCCs.
355 SmallSetVector<Function *, 4> SCCEntryNodes;
357 /// \brief Counter for the next DFS number to assign.
358 int NextDFSNumber;
360 /// \brief Helper to insert a new function, with an already looked-up entry in
361 /// the NodeMap.
362 Node *insertInto(Function &F, Node *&MappedN);
364 /// \brief Helper to update pointers back to the graph object during moves.
365 void updateGraphPtrs();
367 /// \brief Helper to form a new SCC out of the top of a DFSStack-like
368 /// structure.
369 SCC *formSCCFromDFSStack(
370 SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack);
372 /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
373 SCC *getNextSCCInPostOrder();
374 };
376 // Provide GraphTraits specializations for call graphs.
377 template <> struct GraphTraits<LazyCallGraph::Node *> {
378 typedef LazyCallGraph::Node NodeType;
379 typedef LazyCallGraph::iterator ChildIteratorType;
381 static NodeType *getEntryNode(NodeType *N) { return N; }
382 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
383 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
384 };
385 template <> struct GraphTraits<LazyCallGraph *> {
386 typedef LazyCallGraph::Node NodeType;
387 typedef LazyCallGraph::iterator ChildIteratorType;
389 static NodeType *getEntryNode(NodeType *N) { return N; }
390 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
391 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
392 };
394 /// \brief An analysis pass which computes the call graph for a module.
395 class LazyCallGraphAnalysis {
396 public:
397 /// \brief Inform generic clients of the result type.
398 typedef LazyCallGraph Result;
400 static void *ID() { return (void *)&PassID; }
402 /// \brief Compute the \c LazyCallGraph for a the module \c M.
403 ///
404 /// This just builds the set of entry points to the call graph. The rest is
405 /// built lazily as it is walked.
406 LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
408 private:
409 static char PassID;
410 };
412 /// \brief A pass which prints the call graph to a \c raw_ostream.
413 ///
414 /// This is primarily useful for testing the analysis.
415 class LazyCallGraphPrinterPass {
416 raw_ostream &OS;
418 public:
419 explicit LazyCallGraphPrinterPass(raw_ostream &OS);
421 PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
423 static StringRef name() { return "LazyCallGraphPrinterPass"; }
424 };
426 }
428 #endif