1 //== CallGraph.h - AST-based 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 //===----------------------------------------------------------------------===//
10 // This file declares the AST-based CallGraph.
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 //===----------------------------------------------------------------------===//
17 #ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH_H
18 #define LLVM_CLANG_ANALYSIS_CALLGRAPH_H
20 #include "clang/AST/DeclBase.h"
21 #include "clang/AST/RecursiveASTVisitor.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/GraphTraits.h"
24 #include "llvm/ADT/SetVector.h"
29 /// \brief The AST-based call graph.
31 /// The call graph extends itself with the given declarations by implementing
32 /// the recursive AST visitor, which constructs the graph by visiting the given
34 class CallGraph : public RecursiveASTVisitor<CallGraph> {
35 friend class CallGraphNode;
37 typedef llvm::DenseMap<const Decl *, std::unique_ptr<CallGraphNode>>
40 /// FunctionMap owns all CallGraphNodes.
41 FunctionMapTy FunctionMap;
43 /// This is a virtual root node that has edges to all the functions.
50 /// \brief Populate the call graph with the functions in the given
53 /// Recursively walks the declaration to find all the dependent Decls as well.
54 void addToCallGraph(Decl *D) {
58 /// \brief Determine if a declaration should be included in the graph.
59 static bool includeInGraph(const Decl *D);
61 /// \brief Lookup the node for the given declaration.
62 CallGraphNode *getNode(const Decl *) const;
64 /// \brief Lookup the node for the given declaration. If none found, insert
65 /// one into the graph.
66 CallGraphNode *getOrInsertNode(Decl *);
68 /// Iterators through all the elements in the graph. Note, this gives
69 /// non-deterministic order.
70 typedef FunctionMapTy::iterator iterator;
71 typedef FunctionMapTy::const_iterator const_iterator;
72 iterator begin() { return FunctionMap.begin(); }
73 iterator end() { return FunctionMap.end(); }
74 const_iterator begin() const { return FunctionMap.begin(); }
75 const_iterator end() const { return FunctionMap.end(); }
77 /// \brief Get the number of nodes in the graph.
78 unsigned size() const { return FunctionMap.size(); }
80 /// \ brief Get the virtual root of the graph, all the functions available
81 /// externally are represented as callees of the node.
82 CallGraphNode *getRoot() const { return Root; }
84 /// Iterators through all the nodes of the graph that have no parent. These
85 /// are the unreachable nodes, which are either unused or are due to us
86 /// failing to add a call edge due to the analysis imprecision.
87 typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator;
88 typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator;
90 void print(raw_ostream &os) const;
92 void viewGraph() const;
94 void addNodesForBlocks(DeclContext *D);
96 /// Part of recursive declaration visitation. We recursively visit all the
97 /// declarations to collect the root functions.
98 bool VisitFunctionDecl(FunctionDecl *FD) {
99 // We skip function template definitions, as their semantics is
100 // only determined when they are instantiated.
101 if (includeInGraph(FD)) {
102 // Add all blocks declared inside this function to the graph.
103 addNodesForBlocks(FD);
104 // If this function has external linkage, anything could call it.
105 // Note, we are not precise here. For example, the function could have
106 // its address taken.
107 addNodeForDecl(FD, FD->isGlobal());
112 /// Part of recursive declaration visitation.
113 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
114 if (includeInGraph(MD)) {
115 addNodesForBlocks(MD);
116 addNodeForDecl(MD, true);
121 // We are only collecting the declarations, so do not step into the bodies.
122 bool TraverseStmt(Stmt *S) { return true; }
124 bool shouldWalkTypesOfTypeLocs() const { return false; }
127 /// \brief Add the given declaration to the call graph.
128 void addNodeForDecl(Decl *D, bool IsGlobal);
130 /// \brief Allocate a new node in the graph.
131 CallGraphNode *allocateNewNode(Decl *);
134 class CallGraphNode {
136 typedef CallGraphNode* CallRecord;
139 /// \brief The function/method declaration.
142 /// \brief The list of functions called from this node.
143 SmallVector<CallRecord, 5> CalledFunctions;
146 CallGraphNode(Decl *D) : FD(D) {}
148 typedef SmallVectorImpl<CallRecord>::iterator iterator;
149 typedef SmallVectorImpl<CallRecord>::const_iterator const_iterator;
151 /// Iterators through all the callees/children of the node.
152 inline iterator begin() { return CalledFunctions.begin(); }
153 inline iterator end() { return CalledFunctions.end(); }
154 inline const_iterator begin() const { return CalledFunctions.begin(); }
155 inline const_iterator end() const { return CalledFunctions.end(); }
157 inline bool empty() const {return CalledFunctions.empty(); }
158 inline unsigned size() const {return CalledFunctions.size(); }
160 void addCallee(CallGraphNode *N) {
161 CalledFunctions.push_back(N);
164 Decl *getDecl() const { return FD; }
166 void print(raw_ostream &os) const;
170 } // end clang namespace
172 // Graph traits for iteration, viewing.
174 template <> struct GraphTraits<clang::CallGraphNode*> {
175 typedef clang::CallGraphNode NodeType;
176 typedef clang::CallGraphNode *NodeRef;
177 typedef NodeType::iterator ChildIteratorType;
179 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
180 static inline ChildIteratorType child_begin(NodeType *N) {
183 static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
186 template <> struct GraphTraits<const clang::CallGraphNode*> {
187 typedef const clang::CallGraphNode NodeType;
188 typedef const clang::CallGraphNode *NodeRef;
189 typedef NodeType::const_iterator ChildIteratorType;
191 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
192 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
193 static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
196 template <> struct GraphTraits<clang::CallGraph*>
197 : public GraphTraits<clang::CallGraphNode*> {
199 static NodeType *getEntryNode(clang::CallGraph *CGN) {
200 return CGN->getRoot(); // Start at the external node!
203 static clang::CallGraphNode *
204 CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
205 return P.second.get();
208 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
209 typedef mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>
212 static nodes_iterator nodes_begin(clang::CallGraph *CG) {
213 return nodes_iterator(CG->begin(), &CGGetValue);
215 static nodes_iterator nodes_end (clang::CallGraph *CG) {
216 return nodes_iterator(CG->end(), &CGGetValue);
219 static unsigned size(clang::CallGraph *CG) {
224 template <> struct GraphTraits<const clang::CallGraph*> :
225 public GraphTraits<const clang::CallGraphNode*> {
226 static NodeType *getEntryNode(const clang::CallGraph *CGN) {
227 return CGN->getRoot();
230 static clang::CallGraphNode *
231 CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
232 return P.second.get();
235 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
236 typedef mapped_iterator<clang::CallGraph::const_iterator,
237 decltype(&CGGetValue)>
240 static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
241 return nodes_iterator(CG->begin(), &CGGetValue);
243 static nodes_iterator nodes_end(const clang::CallGraph *CG) {
244 return nodes_iterator(CG->end(), &CGGetValue);
246 static unsigned size(const clang::CallGraph *CG) {
251 } // end llvm namespace