Line data Source code
1 : //===- CallGraph.h - Build 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 : /// This file provides interfaces used to build and manipulate a call graph,
12 : /// which is a very useful tool for interprocedural optimization.
13 : ///
14 : /// Every function in a module is represented as a node in the call graph. The
15 : /// callgraph node keeps track of which functions are called by the function
16 : /// corresponding to the node.
17 : ///
18 : /// A call graph may contain nodes where the function that they correspond to
19 : /// is null. These 'external' nodes are used to represent control flow that is
20 : /// not represented (or analyzable) in the module. In particular, this
21 : /// analysis builds one external node such that:
22 : /// 1. All functions in the module without internal linkage will have edges
23 : /// from this external node, indicating that they could be called by
24 : /// functions outside of the module.
25 : /// 2. All functions whose address is used for something more than a direct
26 : /// call, for example being stored into a memory location will also have
27 : /// an edge from this external node. Since they may be called by an
28 : /// unknown caller later, they must be tracked as such.
29 : ///
30 : /// There is a second external node added for calls that leave this module.
31 : /// Functions have a call edge to the external node iff:
32 : /// 1. The function is external, reflecting the fact that they could call
33 : /// anything without internal linkage or that has its address taken.
34 : /// 2. The function contains an indirect function call.
35 : ///
36 : /// As an extension in the future, there may be multiple nodes with a null
37 : /// function. These will be used when we can prove (through pointer analysis)
38 : /// that an indirect call site can call only a specific set of functions.
39 : ///
40 : /// Because of these properties, the CallGraph captures a conservative superset
41 : /// of all of the caller-callee relationships, which is useful for
42 : /// transformations.
43 : ///
44 : //===----------------------------------------------------------------------===//
45 :
46 : #ifndef LLVM_ANALYSIS_CALLGRAPH_H
47 : #define LLVM_ANALYSIS_CALLGRAPH_H
48 :
49 : #include "llvm/ADT/GraphTraits.h"
50 : #include "llvm/ADT/STLExtras.h"
51 : #include "llvm/IR/CallSite.h"
52 : #include "llvm/IR/Function.h"
53 : #include "llvm/IR/Intrinsics.h"
54 : #include "llvm/IR/PassManager.h"
55 : #include "llvm/IR/ValueHandle.h"
56 : #include "llvm/Pass.h"
57 : #include <cassert>
58 : #include <map>
59 : #include <memory>
60 : #include <utility>
61 : #include <vector>
62 :
63 : namespace llvm {
64 :
65 : class CallGraphNode;
66 : class Module;
67 : class raw_ostream;
68 :
69 : /// The basic data container for the call graph of a \c Module of IR.
70 : ///
71 : /// This class exposes both the interface to the call graph for a module of IR.
72 : ///
73 : /// The core call graph itself can also be updated to reflect changes to the IR.
74 : class CallGraph {
75 : Module &M;
76 :
77 : using FunctionMapTy =
78 : std::map<const Function *, std::unique_ptr<CallGraphNode>>;
79 :
80 : /// A map from \c Function* to \c CallGraphNode*.
81 : FunctionMapTy FunctionMap;
82 :
83 : /// This node has edges to all external functions and those internal
84 : /// functions that have their address taken.
85 : CallGraphNode *ExternalCallingNode;
86 :
87 : /// This node has edges to it from all functions making indirect calls
88 : /// or calling an external function.
89 : std::unique_ptr<CallGraphNode> CallsExternalNode;
90 :
91 : /// Replace the function represented by this node by another.
92 : ///
93 : /// This does not rescan the body of the function, so it is suitable when
94 : /// splicing the body of one function to another while also updating all
95 : /// callers from the old function to the new.
96 : void spliceFunction(const Function *From, const Function *To);
97 :
98 : /// Add a function to the call graph, and link the node to all of the
99 : /// functions that it calls.
100 : void addToCallGraph(Function *F);
101 :
102 : public:
103 : explicit CallGraph(Module &M);
104 : CallGraph(CallGraph &&Arg);
105 : ~CallGraph();
106 :
107 : void print(raw_ostream &OS) const;
108 : void dump() const;
109 :
110 : using iterator = FunctionMapTy::iterator;
111 : using const_iterator = FunctionMapTy::const_iterator;
112 :
113 : /// Returns the module the call graph corresponds to.
114 0 : Module &getModule() const { return M; }
115 :
116 : inline iterator begin() { return FunctionMap.begin(); }
117 : inline iterator end() { return FunctionMap.end(); }
118 : inline const_iterator begin() const { return FunctionMap.begin(); }
119 : inline const_iterator end() const { return FunctionMap.end(); }
120 :
121 : /// Returns the call graph node for the provided function.
122 : inline const CallGraphNode *operator[](const Function *F) const {
123 : const_iterator I = FunctionMap.find(F);
124 : assert(I != FunctionMap.end() && "Function not in callgraph!");
125 : return I->second.get();
126 : }
127 :
128 : /// Returns the call graph node for the provided function.
129 : inline CallGraphNode *operator[](const Function *F) {
130 : const_iterator I = FunctionMap.find(F);
131 : assert(I != FunctionMap.end() && "Function not in callgraph!");
132 : return I->second.get();
133 : }
134 :
135 : /// Returns the \c CallGraphNode which is used to represent
136 : /// undetermined calls into the callgraph.
137 0 : CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; }
138 :
139 : CallGraphNode *getCallsExternalNode() const {
140 : return CallsExternalNode.get();
141 : }
142 :
143 : //===---------------------------------------------------------------------
144 : // Functions to keep a call graph up to date with a function that has been
145 : // modified.
146 : //
147 :
148 : /// Unlink the function from this module, returning it.
149 : ///
150 : /// Because this removes the function from the module, the call graph node is
151 : /// destroyed. This is only valid if the function does not call any other
152 : /// functions (ie, there are no edges in it's CGN). The easiest way to do
153 : /// this is to dropAllReferences before calling this.
154 : Function *removeFunctionFromModule(CallGraphNode *CGN);
155 :
156 : /// Similar to operator[], but this will insert a new CallGraphNode for
157 : /// \c F if one does not already exist.
158 : CallGraphNode *getOrInsertFunction(const Function *F);
159 : };
160 :
161 : /// A node in the call graph for a module.
162 : ///
163 : /// Typically represents a function in the call graph. There are also special
164 : /// "null" nodes used to represent theoretical entries in the call graph.
165 : class CallGraphNode {
166 : public:
167 : /// A pair of the calling instruction (a call or invoke)
168 : /// and the call graph node being called.
169 : using CallRecord = std::pair<WeakTrackingVH, CallGraphNode *>;
170 :
171 : public:
172 : using CalledFunctionsVector = std::vector<CallRecord>;
173 :
174 : /// Creates a node for the specified function.
175 2182736 : inline CallGraphNode(Function *F) : F(F) {}
176 :
177 : CallGraphNode(const CallGraphNode &) = delete;
178 : CallGraphNode &operator=(const CallGraphNode &) = delete;
179 :
180 1091330 : ~CallGraphNode() {
181 : assert(NumReferences == 0 && "Node deleted while references remain");
182 : }
183 :
184 : using iterator = std::vector<CallRecord>::iterator;
185 : using const_iterator = std::vector<CallRecord>::const_iterator;
186 :
187 : /// Returns the function that this call graph node represents.
188 0 : Function *getFunction() const { return F; }
189 :
190 : inline iterator begin() { return CalledFunctions.begin(); }
191 : inline iterator end() { return CalledFunctions.end(); }
192 38 : inline const_iterator begin() const { return CalledFunctions.begin(); }
193 79 : inline const_iterator end() const { return CalledFunctions.end(); }
194 : inline bool empty() const { return CalledFunctions.empty(); }
195 : inline unsigned size() const { return (unsigned)CalledFunctions.size(); }
196 :
197 : /// Returns the number of other CallGraphNodes in this CallGraph that
198 : /// reference this node in their callee list.
199 0 : unsigned getNumReferences() const { return NumReferences; }
200 :
201 : /// Returns the i'th called function.
202 : CallGraphNode *operator[](unsigned i) const {
203 : assert(i < CalledFunctions.size() && "Invalid index");
204 : return CalledFunctions[i].second;
205 : }
206 :
207 : /// Print out this call graph node.
208 : void dump() const;
209 : void print(raw_ostream &OS) const;
210 :
211 : //===---------------------------------------------------------------------
212 : // Methods to keep a call graph up to date with a function that has been
213 : // modified
214 : //
215 :
216 : /// Removes all edges from this CallGraphNode to any functions it
217 : /// calls.
218 : void removeAllCalledFunctions() {
219 33374 : while (!CalledFunctions.empty()) {
220 11999 : CalledFunctions.back().second->DropRef();
221 11999 : CalledFunctions.pop_back();
222 : }
223 : }
224 :
225 : /// Moves all the callee information from N to this node.
226 : void stealCalledFunctionsFrom(CallGraphNode *N) {
227 : assert(CalledFunctions.empty() &&
228 : "Cannot steal callsite information if I already have some");
229 : std::swap(CalledFunctions, N->CalledFunctions);
230 : }
231 :
232 : /// Adds a function to the list of functions called by this one.
233 : void addCalledFunction(CallSite CS, CallGraphNode *M) {
234 : assert(!CS.getInstruction() || !CS.getCalledFunction() ||
235 : !CS.getCalledFunction()->isIntrinsic() ||
236 : !Intrinsic::isLeaf(CS.getCalledFunction()->getIntrinsicID()));
237 7266693 : CalledFunctions.emplace_back(CS.getInstruction(), M);
238 4190017 : M->AddRef();
239 : }
240 :
241 5379 : void removeCallEdge(iterator I) {
242 5379 : I->second->DropRef();
243 : *I = CalledFunctions.back();
244 5379 : CalledFunctions.pop_back();
245 5379 : }
246 :
247 : /// Removes the edge in the node for the specified call site.
248 : ///
249 : /// Note that this method takes linear time, so it should be used sparingly.
250 : void removeCallEdgeFor(CallSite CS);
251 :
252 : /// Removes all call edges from this node to the specified callee
253 : /// function.
254 : ///
255 : /// This takes more time to execute than removeCallEdgeTo, so it should not
256 : /// be used unless necessary.
257 : void removeAnyCallEdgeTo(CallGraphNode *Callee);
258 :
259 : /// Removes one edge associated with a null callsite from this node to
260 : /// the specified callee function.
261 : void removeOneAbstractEdgeTo(CallGraphNode *Callee);
262 :
263 : /// Replaces the edge in the node for the specified call site with a
264 : /// new one.
265 : ///
266 : /// Note that this method takes linear time, so it should be used sparingly.
267 : void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode);
268 :
269 : private:
270 : friend class CallGraph;
271 :
272 : Function *F;
273 :
274 : std::vector<CallRecord> CalledFunctions;
275 :
276 : /// The number of times that this CallGraphNode occurs in the
277 : /// CalledFunctions array of this or other CallGraphNodes.
278 : unsigned NumReferences = 0;
279 :
280 1922088 : void DropRef() { --NumReferences; }
281 4190186 : void AddRef() { ++NumReferences; }
282 :
283 : /// A special function that should only be used by the CallGraph class.
284 23921 : void allReferencesDropped() { NumReferences = 0; }
285 : };
286 :
287 : /// An analysis pass to compute the \c CallGraph for a \c Module.
288 : ///
289 : /// This class implements the concept of an analysis pass used by the \c
290 : /// ModuleAnalysisManager to run an analysis over a module and cache the
291 : /// resulting data.
292 : class CallGraphAnalysis : public AnalysisInfoMixin<CallGraphAnalysis> {
293 : friend AnalysisInfoMixin<CallGraphAnalysis>;
294 :
295 : static AnalysisKey Key;
296 :
297 : public:
298 : /// A formulaic type to inform clients of the result type.
299 : using Result = CallGraph;
300 :
301 : /// Compute the \c CallGraph for the module \c M.
302 : ///
303 : /// The real work here is done in the \c CallGraph constructor.
304 129 : CallGraph run(Module &M, ModuleAnalysisManager &) { return CallGraph(M); }
305 : };
306 :
307 : /// Printer pass for the \c CallGraphAnalysis results.
308 : class CallGraphPrinterPass : public PassInfoMixin<CallGraphPrinterPass> {
309 : raw_ostream &OS;
310 :
311 : public:
312 1 : explicit CallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
313 :
314 : PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
315 : };
316 :
317 : /// The \c ModulePass which wraps up a \c CallGraph and the logic to
318 : /// build it.
319 : ///
320 : /// This class exposes both the interface to the call graph container and the
321 : /// module pass which runs over a module of IR and produces the call graph. The
322 : /// call graph interface is entirelly a wrapper around a \c CallGraph object
323 : /// which is stored internally for each module.
324 47548 : class CallGraphWrapperPass : public ModulePass {
325 : std::unique_ptr<CallGraph> G;
326 :
327 : public:
328 : static char ID; // Class identification, replacement for typeinfo
329 :
330 : CallGraphWrapperPass();
331 : ~CallGraphWrapperPass() override;
332 :
333 : /// The internal \c CallGraph around which the rest of this interface
334 : /// is wrapped.
335 : const CallGraph &getCallGraph() const { return *G; }
336 : CallGraph &getCallGraph() { return *G; }
337 :
338 : using iterator = CallGraph::iterator;
339 : using const_iterator = CallGraph::const_iterator;
340 :
341 : /// Returns the module the call graph corresponds to.
342 : Module &getModule() const { return G->getModule(); }
343 :
344 : inline iterator begin() { return G->begin(); }
345 : inline iterator end() { return G->end(); }
346 : inline const_iterator begin() const { return G->begin(); }
347 : inline const_iterator end() const { return G->end(); }
348 :
349 : /// Returns the call graph node for the provided function.
350 : inline const CallGraphNode *operator[](const Function *F) const {
351 : return (*G)[F];
352 : }
353 :
354 : /// Returns the call graph node for the provided function.
355 : inline CallGraphNode *operator[](const Function *F) { return (*G)[F]; }
356 :
357 : /// Returns the \c CallGraphNode which is used to represent
358 : /// undetermined calls into the callgraph.
359 : CallGraphNode *getExternalCallingNode() const {
360 : return G->getExternalCallingNode();
361 : }
362 :
363 : CallGraphNode *getCallsExternalNode() const {
364 : return G->getCallsExternalNode();
365 : }
366 :
367 : //===---------------------------------------------------------------------
368 : // Functions to keep a call graph up to date with a function that has been
369 : // modified.
370 : //
371 :
372 : /// Unlink the function from this module, returning it.
373 : ///
374 : /// Because this removes the function from the module, the call graph node is
375 : /// destroyed. This is only valid if the function does not call any other
376 : /// functions (ie, there are no edges in it's CGN). The easiest way to do
377 : /// this is to dropAllReferences before calling this.
378 : Function *removeFunctionFromModule(CallGraphNode *CGN) {
379 : return G->removeFunctionFromModule(CGN);
380 : }
381 :
382 : /// Similar to operator[], but this will insert a new CallGraphNode for
383 : /// \c F if one does not already exist.
384 : CallGraphNode *getOrInsertFunction(const Function *F) {
385 : return G->getOrInsertFunction(F);
386 : }
387 :
388 : //===---------------------------------------------------------------------
389 : // Implementation of the ModulePass interface needed here.
390 : //
391 :
392 : void getAnalysisUsage(AnalysisUsage &AU) const override;
393 : bool runOnModule(Module &M) override;
394 : void releaseMemory() override;
395 :
396 : void print(raw_ostream &o, const Module *) const override;
397 : void dump() const;
398 : };
399 :
400 : //===----------------------------------------------------------------------===//
401 : // GraphTraits specializations for call graphs so that they can be treated as
402 : // graphs by the generic graph algorithms.
403 : //
404 :
405 : // Provide graph traits for tranversing call graphs using standard graph
406 : // traversals.
407 : template <> struct GraphTraits<CallGraphNode *> {
408 : using NodeRef = CallGraphNode *;
409 : using CGNPairTy = CallGraphNode::CallRecord;
410 :
411 : static NodeRef getEntryNode(CallGraphNode *CGN) { return CGN; }
412 4724773 : static CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; }
413 :
414 : using ChildIteratorType =
415 : mapped_iterator<CallGraphNode::iterator, decltype(&CGNGetValue)>;
416 :
417 : static ChildIteratorType child_begin(NodeRef N) {
418 : return ChildIteratorType(N->begin(), &CGNGetValue);
419 : }
420 :
421 : static ChildIteratorType child_end(NodeRef N) {
422 : return ChildIteratorType(N->end(), &CGNGetValue);
423 : }
424 : };
425 :
426 : template <> struct GraphTraits<const CallGraphNode *> {
427 : using NodeRef = const CallGraphNode *;
428 : using CGNPairTy = CallGraphNode::CallRecord;
429 : using EdgeRef = const CallGraphNode::CallRecord &;
430 :
431 : static NodeRef getEntryNode(const CallGraphNode *CGN) { return CGN; }
432 22 : static const CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; }
433 :
434 : using ChildIteratorType =
435 : mapped_iterator<CallGraphNode::const_iterator, decltype(&CGNGetValue)>;
436 : using ChildEdgeIteratorType = CallGraphNode::const_iterator;
437 :
438 : static ChildIteratorType child_begin(NodeRef N) {
439 : return ChildIteratorType(N->begin(), &CGNGetValue);
440 : }
441 :
442 : static ChildIteratorType child_end(NodeRef N) {
443 : return ChildIteratorType(N->end(), &CGNGetValue);
444 : }
445 :
446 : static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
447 : return N->begin();
448 : }
449 : static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
450 :
451 0 : static NodeRef edge_dest(EdgeRef E) { return E.second; }
452 : };
453 :
454 : template <>
455 : struct GraphTraits<CallGraph *> : public GraphTraits<CallGraphNode *> {
456 : using PairTy =
457 : std::pair<const Function *const, std::unique_ptr<CallGraphNode>>;
458 :
459 : static NodeRef getEntryNode(CallGraph *CGN) {
460 27414 : return CGN->getExternalCallingNode(); // Start at the external node!
461 : }
462 :
463 0 : static CallGraphNode *CGGetValuePtr(const PairTy &P) {
464 0 : return P.second.get();
465 : }
466 :
467 : // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
468 : using nodes_iterator =
469 : mapped_iterator<CallGraph::iterator, decltype(&CGGetValuePtr)>;
470 :
471 : static nodes_iterator nodes_begin(CallGraph *CG) {
472 : return nodes_iterator(CG->begin(), &CGGetValuePtr);
473 : }
474 :
475 : static nodes_iterator nodes_end(CallGraph *CG) {
476 : return nodes_iterator(CG->end(), &CGGetValuePtr);
477 : }
478 : };
479 :
480 : template <>
481 : struct GraphTraits<const CallGraph *> : public GraphTraits<
482 : const CallGraphNode *> {
483 : using PairTy =
484 : std::pair<const Function *const, std::unique_ptr<CallGraphNode>>;
485 :
486 : static NodeRef getEntryNode(const CallGraph *CGN) {
487 3 : return CGN->getExternalCallingNode(); // Start at the external node!
488 : }
489 :
490 0 : static const CallGraphNode *CGGetValuePtr(const PairTy &P) {
491 0 : return P.second.get();
492 : }
493 :
494 : // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
495 : using nodes_iterator =
496 : mapped_iterator<CallGraph::const_iterator, decltype(&CGGetValuePtr)>;
497 :
498 : static nodes_iterator nodes_begin(const CallGraph *CG) {
499 : return nodes_iterator(CG->begin(), &CGGetValuePtr);
500 : }
501 :
502 : static nodes_iterator nodes_end(const CallGraph *CG) {
503 : return nodes_iterator(CG->end(), &CGGetValuePtr);
504 : }
505 : };
506 :
507 : } // end namespace llvm
508 :
509 : #endif // LLVM_ANALYSIS_CALLGRAPH_H
|
