1//===- CallGraph.h - AST-based 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//
10// This file declares the AST-based CallGraph.
11//
12// A call graph for functions whose definitions/bodies are available in the
13// current translation unit. The graph has a "virtual" root node that contains
14// edges to all externally available functions.
15//
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH_H
19#define LLVM_CLANG_ANALYSIS_CALLGRAPH_H
20
21#include "clang/AST/Decl.h"
22#include "clang/AST/RecursiveASTVisitor.h"
23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/GraphTraits.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/ADT/SetVector.h"
27#include "llvm/ADT/SmallVector.h"
28#include <memory>
29
30namespace clang {
31
32class CallGraphNode;
33class Decl;
34class DeclContext;
35class Stmt;
36
37/// The AST-based call graph.
38///
39/// The call graph extends itself with the given declarations by implementing
40/// the recursive AST visitor, which constructs the graph by visiting the given
41/// declarations.
42class CallGraph : public RecursiveASTVisitor<CallGraph> {
43 friend class CallGraphNode;
44
45 using FunctionMapTy =
46 llvm::DenseMap<const Decl *, std::unique_ptr<CallGraphNode>>;
47
48 /// FunctionMap owns all CallGraphNodes.
49 FunctionMapTy FunctionMap;
50
51 /// This is a virtual root node that has edges to all the functions.
52 CallGraphNode *Root;
53
54public:
55 CallGraph();
56 ~CallGraph();
57
58 /// Populate the call graph with the functions in the given
59 /// declaration.
60 ///
61 /// Recursively walks the declaration to find all the dependent Decls as well.
62 void addToCallGraph(Decl *D) {
63 TraverseDecl(D);
64 }
65
66 /// Determine if a declaration should be included in the graph.
67 static bool includeInGraph(const Decl *D);
68
69 /// Lookup the node for the given declaration.
70 CallGraphNode *getNode(const Decl *) const;
71
72 /// Lookup the node for the given declaration. If none found, insert
73 /// one into the graph.
74 CallGraphNode *getOrInsertNode(Decl *);
75
76 using iterator = FunctionMapTy::iterator;
77 using const_iterator = FunctionMapTy::const_iterator;
78
79 /// Iterators through all the elements in the graph. Note, this gives
80 /// non-deterministic order.
81 iterator begin() { return FunctionMap.begin(); }
82 iterator end() { return FunctionMap.end(); }
83 const_iterator begin() const { return FunctionMap.begin(); }
84 const_iterator end() const { return FunctionMap.end(); }
85
86 /// Get the number of nodes in the graph.
87 unsigned size() const { return FunctionMap.size(); }
88
89 /// \ brief Get the virtual root of the graph, all the functions available
90 /// externally are represented as callees of the node.
91 CallGraphNode *getRoot() const { return Root; }
92
93 /// Iterators through all the nodes of the graph that have no parent. These
94 /// are the unreachable nodes, which are either unused or are due to us
95 /// failing to add a call edge due to the analysis imprecision.
96 using nodes_iterator = llvm::SetVector<CallGraphNode *>::iterator;
97 using const_nodes_iterator = llvm::SetVector<CallGraphNode *>::const_iterator;
98
99 void print(raw_ostream &os) const;
100 void dump() const;
101 void viewGraph() const;
102
103 void addNodesForBlocks(DeclContext *D);
104
105 /// Part of recursive declaration visitation. We recursively visit all the
106 /// declarations to collect the root functions.
107 bool VisitFunctionDecl(FunctionDecl *FD) {
108 // We skip function template definitions, as their semantics is
109 // only determined when they are instantiated.
110 if (includeInGraph(FD) && FD->isThisDeclarationADefinition()) {
111 // Add all blocks declared inside this function to the graph.
112 addNodesForBlocks(FD);
113 // If this function has external linkage, anything could call it.
114 // Note, we are not precise here. For example, the function could have
115 // its address taken.
116 addNodeForDecl(FD, FD->isGlobal());
117 }
118 return true;
119 }
120
121 /// Part of recursive declaration visitation.
122 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
123 if (includeInGraph(MD)) {
124 addNodesForBlocks(MD);
125 addNodeForDecl(MD, true);
126 }
127 return true;
128 }
129
130 // We are only collecting the declarations, so do not step into the bodies.
131 bool TraverseStmt(Stmt *S) { return true; }
132
133 bool shouldWalkTypesOfTypeLocs() const { return false; }
134
135private:
136 /// Add the given declaration to the call graph.
137 void addNodeForDecl(Decl *D, bool IsGlobal);
138
139 /// Allocate a new node in the graph.
140 CallGraphNode *allocateNewNode(Decl *);
141};
142
143class CallGraphNode {
144public:
145 using CallRecord = CallGraphNode *;
146
147private:
148 /// The function/method declaration.
149 Decl *FD;
150
151 /// The list of functions called from this node.
152 SmallVector<CallRecord, 5> CalledFunctions;
153
154public:
155 CallGraphNode(Decl *D) : FD(D) {}
156
157 using iterator = SmallVectorImpl<CallRecord>::iterator;
158 using const_iterator = SmallVectorImpl<CallRecord>::const_iterator;
159
160 /// Iterators through all the callees/children of the node.
161 iterator begin() { return CalledFunctions.begin(); }
162 iterator end() { return CalledFunctions.end(); }
163 const_iterator begin() const { return CalledFunctions.begin(); }
164 const_iterator end() const { return CalledFunctions.end(); }
165
166 bool empty() const { return CalledFunctions.empty(); }
167 unsigned size() const { return CalledFunctions.size(); }
168
169 void addCallee(CallGraphNode *N) {
170 CalledFunctions.push_back(N);
171 }
172
173 Decl *getDecl() const { return FD; }
174
175 void print(raw_ostream &os) const;
176 void dump() const;
177};
178
179} // namespace clang
180
181// Graph traits for iteration, viewing.
182namespace llvm {
183
184template <> struct GraphTraits<clang::CallGraphNode*> {
185 using NodeType = clang::CallGraphNode;
186 using NodeRef = clang::CallGraphNode *;
187 using ChildIteratorType = NodeType::iterator;
188
189 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
190 static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
191 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
192};
193
194template <> struct GraphTraits<const clang::CallGraphNode*> {
195 using NodeType = const clang::CallGraphNode;
196 using NodeRef = const clang::CallGraphNode *;
197 using ChildIteratorType = NodeType::const_iterator;
198
199 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
200 static ChildIteratorType child_begin(NodeType *N) { return N->begin();}
201 static ChildIteratorType child_end(NodeType *N) { return N->end(); }
202};
203
204template <> struct GraphTraits<clang::CallGraph*>
205 : public GraphTraits<clang::CallGraphNode*> {
206 static NodeType *getEntryNode(clang::CallGraph *CGN) {
207 return CGN->getRoot(); // Start at the external node!
208 }
209
210 static clang::CallGraphNode *
211 CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
212 return P.second.get();
213 }
214
215 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
216 using nodes_iterator =
217 mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>;
218
219 static nodes_iterator nodes_begin(clang::CallGraph *CG) {
220 return nodes_iterator(CG->begin(), &CGGetValue);
221 }
222
223 static nodes_iterator nodes_end (clang::CallGraph *CG) {
224 return nodes_iterator(CG->end(), &CGGetValue);
225 }
226
227 static unsigned size(clang::CallGraph *CG) { return CG->size(); }
228};
229
230template <> struct GraphTraits<const clang::CallGraph*> :
231 public GraphTraits<const clang::CallGraphNode*> {
232 static NodeType *getEntryNode(const clang::CallGraph *CGN) {
233 return CGN->getRoot();
234 }
235
236 static clang::CallGraphNode *
237 CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
238 return P.second.get();
239 }
240
241 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
242 using nodes_iterator =
243 mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>;
244
245 static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
246 return nodes_iterator(CG->begin(), &CGGetValue);
247 }
248
249 static nodes_iterator nodes_end(const clang::CallGraph *CG) {
250 return nodes_iterator(CG->end(), &CGGetValue);
251 }
252
253 static unsigned size(const clang::CallGraph *CG) { return CG->size(); }
254};
255
256} // namespace llvm
257
258#endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H
259