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/SmallPtrSet.h"
42 #include "llvm/ADT/SmallVector.h"
43 #include "llvm/IR/BasicBlock.h"
44 #include "llvm/IR/Function.h"
45 #include "llvm/IR/Module.h"
46 #include "llvm/Support/Allocator.h"
50 class ModuleAnalysisManager;
51 class PreservedAnalyses;
54 /// \brief A lazily constructed view of the call graph of a module.
56 /// With the edges of this graph, the motivating constraint that we are
57 /// attempting to maintain is that function-local optimization, CGSCC-local
58 /// optimizations, and optimizations transforming a pair of functions connected
59 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
60 /// DAG. That is, no optimizations will delete, remove, or add an edge such
61 /// that functions already visited in a bottom-up order of the SCC DAG are no
62 /// longer valid to have visited, or such that functions not yet visited in
63 /// a bottom-up order of the SCC DAG are not required to have already been
66 /// Within this constraint, the desire is to minimize the merge points of the
67 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
68 /// in the SCC DAG, the more independence there is in optimizing within it.
69 /// There is a strong desire to enable parallelization of optimizations over
70 /// the call graph, and both limited fanout and merge points will (artificially
71 /// in some cases) limit the scaling of such an effort.
73 /// To this end, graph represents both direct and any potential resolution to
74 /// an indirect call edge. Another way to think about it is that it represents
75 /// both the direct call edges and any direct call edges that might be formed
76 /// through static optimizations. Specifically, it considers taking the address
77 /// of a function to be an edge in the call graph because this might be
78 /// forwarded to become a direct call by some subsequent function-local
79 /// optimization. The result is that the graph closely follows the use-def
80 /// edges for functions. Walking "up" the graph can be done by looking at all
81 /// of the uses of a function.
83 /// The roots of the call graph are the external functions and functions
84 /// escaped into global variables. Those functions can be called from outside
85 /// of the module or via unknowable means in the IR -- we may not be able to
86 /// form even a potential call edge from a function body which may dynamically
87 /// load the function and call it.
89 /// This analysis still requires updates to remain valid after optimizations
90 /// which could potentially change the set of potential callees. The
91 /// constraints it operates under only make the traversal order remain valid.
93 /// The entire analysis must be re-computed if full interprocedural
94 /// optimizations run at any point. For example, globalopt completely
95 /// invalidates the information in this analysis.
97 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
98 /// it from the existing CallGraph. At some point, it is expected that this
99 /// will be the only call graph and it will be renamed accordingly.
100 class LazyCallGraph {
103 typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
104 typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;
106 /// \brief A lazy iterator used for both the entry nodes and child nodes.
108 /// When this iterator is dereferenced, if not yet available, a function will
109 /// be scanned for "calls" or uses of functions and its child information
110 /// will be constructed. All of these results are accumulated and cached in
112 class iterator : public std::iterator<std::bidirectional_iterator_tag, Node *,
113 ptrdiff_t, Node *, Node *> {
114 friend class LazyCallGraph;
115 friend class LazyCallGraph::Node;
116 typedef std::iterator<std::bidirectional_iterator_tag, Node *, ptrdiff_t,
117 Node *, Node *> BaseT;
119 /// \brief Nonce type to select the constructor for the end iterator.
123 NodeVectorImplT::iterator NI;
125 // Build the begin iterator for a node.
126 explicit iterator(LazyCallGraph &G, NodeVectorImplT &Nodes)
127 : G(G), NI(Nodes.begin()) {}
129 // Build the end iterator for a node. This is selected purely by overload.
130 iterator(LazyCallGraph &G, NodeVectorImplT &Nodes, IsAtEndT /*Nonce*/)
131 : G(G), NI(Nodes.end()) {}
134 iterator(const iterator &Arg) : G(Arg.G), NI(Arg.NI) {}
135 iterator(iterator &&Arg) : G(Arg.G), NI(std::move(Arg.NI)) {}
136 iterator &operator=(iterator Arg) {
137 std::swap(Arg, *this);
141 bool operator==(const iterator &Arg) { return NI == Arg.NI; }
142 bool operator!=(const iterator &Arg) { return !operator==(Arg); }
144 reference operator*() const {
145 if (NI->is<Node *>())
146 return NI->get<Node *>();
148 Function *F = NI->get<Function *>();
149 Node *ChildN = G.get(*F);
153 pointer operator->() const { return operator*(); }
155 iterator &operator++() {
159 iterator operator++(int) {
160 iterator prev = *this;
165 iterator &operator--() {
169 iterator operator--(int) {
170 iterator next = *this;
176 /// \brief Construct a graph for the given module.
178 /// This sets up the graph and computes all of the entry points of the graph.
179 /// No function definitions are scanned until their nodes in the graph are
180 /// requested during traversal.
181 LazyCallGraph(Module &M);
183 /// \brief Copy constructor.
185 /// This does a deep copy of the graph. It does no verification that the
186 /// graph remains valid for the module. It is also relatively expensive.
187 LazyCallGraph(const LazyCallGraph &G);
189 /// \brief Move constructor.
191 /// This is a deep move. It leaves G in an undefined but destroyable state.
192 /// Any other operation on G is likely to fail.
193 LazyCallGraph(LazyCallGraph &&G);
195 /// \brief Copy and move assignment.
196 LazyCallGraph &operator=(LazyCallGraph RHS) {
197 std::swap(*this, RHS);
201 iterator begin() { return iterator(*this, EntryNodes); }
202 iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
204 /// \brief Lookup a function in the graph which has already been scanned and
206 Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
208 /// \brief Get a graph node for a given function, scanning it to populate the
209 /// graph data as necessary.
210 Node *get(Function &F) {
211 Node *&N = NodeMap[&F];
215 return insertInto(F, N);
221 /// \brief Allocator that holds all the call graph nodes.
222 SpecificBumpPtrAllocator<Node> BPA;
224 /// \brief Maps function->node for fast lookup.
225 DenseMap<const Function *, Node *> NodeMap;
227 /// \brief The entry nodes to the graph.
229 /// These nodes are reachable through "external" means. Put another way, they
230 /// escape at the module scope.
231 NodeVectorT EntryNodes;
233 /// \brief Set of the entry nodes to the graph.
234 SmallPtrSet<Function *, 4> EntryNodeSet;
236 /// \brief Helper to insert a new function, with an already looked-up entry in
238 Node *insertInto(Function &F, Node *&MappedN);
240 /// \brief Helper to copy a node from another graph into this one.
241 Node *copyInto(const Node &OtherN);
243 /// \brief Helper to move a node from another graph into this one.
244 Node *moveInto(Node &&OtherN);
247 /// \brief A node in the call graph.
249 /// This represents a single node. It's primary roles are to cache the list of
250 /// callees, de-duplicate and provide fast testing of whether a function is
251 /// a callee, and facilitate iteration of child nodes in the graph.
252 class LazyCallGraph::Node {
253 friend class LazyCallGraph;
257 mutable NodeVectorT Callees;
258 SmallPtrSet<Function *, 4> CalleeSet;
260 /// \brief Basic constructor implements the scanning of F into Callees and
262 Node(LazyCallGraph &G, Function &F);
264 /// \brief Constructor used when copying a node from one graph to another.
265 Node(LazyCallGraph &G, const Node &OtherN);
267 /// \brief Constructor used when moving a node from one graph to another.
268 Node(LazyCallGraph &G, Node &&OtherN);
271 typedef LazyCallGraph::iterator iterator;
273 Function &getFunction() const {
277 iterator begin() const { return iterator(G, Callees); }
278 iterator end() const { return iterator(G, Callees, iterator::IsAtEndT()); }
280 /// Equality is defined as address equality.
281 bool operator==(const Node &N) const { return this == &N; }
282 bool operator!=(const Node &N) const { return !operator==(N); }
285 // Provide GraphTraits specializations for call graphs.
286 template <> struct GraphTraits<LazyCallGraph::Node *> {
287 typedef LazyCallGraph::Node NodeType;
288 typedef LazyCallGraph::iterator ChildIteratorType;
290 static NodeType *getEntryNode(NodeType *N) { return N; }
291 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
292 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
294 template <> struct GraphTraits<LazyCallGraph *> {
295 typedef LazyCallGraph::Node NodeType;
296 typedef LazyCallGraph::iterator ChildIteratorType;
298 static NodeType *getEntryNode(NodeType *N) { return N; }
299 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
300 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
303 /// \brief An analysis pass which computes the call graph for a module.
304 class LazyCallGraphAnalysis {
306 /// \brief Inform generic clients of the result type.
307 typedef LazyCallGraph Result;
309 static void *ID() { return (void *)&PassID; }
311 /// \brief Compute the \c LazyCallGraph for a the module \c M.
313 /// This just builds the set of entry points to the call graph. The rest is
314 /// built lazily as it is walked.
315 LazyCallGraph run(Module *M) { return LazyCallGraph(*M); }
321 /// \brief A pass which prints the call graph to a \c raw_ostream.
323 /// This is primarily useful for testing the analysis.
324 class LazyCallGraphPrinterPass {
328 explicit LazyCallGraphPrinterPass(raw_ostream &OS);
330 PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM);
332 static StringRef name() { return "LazyCallGraphPrinterPass"; }