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 *, CallGraphNode *> FunctionMapTy;
39 /// FunctionMap owns all CallGraphNodes.
40 FunctionMapTy FunctionMap;
42 /// This is a virtual root node that has edges to all the functions.
49 /// \brief Populate the call graph with the functions in the given
52 /// Recursively walks the declaration to find all the dependent Decls as well.
53 void addToCallGraph(Decl *D) {
57 /// \brief Determine if a declaration should be included in the graph.
58 static bool includeInGraph(const Decl *D);
60 /// \brief Lookup the node for the given declaration.
61 CallGraphNode *getNode(const Decl *) const;
63 /// \brief Lookup the node for the given declaration. If none found, insert
64 /// one into the graph.
65 CallGraphNode *getOrInsertNode(Decl *);
67 /// Iterators through all the elements in the graph. Note, this gives
68 /// non-deterministic order.
69 typedef FunctionMapTy::iterator iterator;
70 typedef FunctionMapTy::const_iterator const_iterator;
71 iterator begin() { return FunctionMap.begin(); }
72 iterator end() { return FunctionMap.end(); }
73 const_iterator begin() const { return FunctionMap.begin(); }
74 const_iterator end() const { return FunctionMap.end(); }
76 /// \brief Get the number of nodes in the graph.
77 unsigned size() const { return FunctionMap.size(); }
79 /// \ brief Get the virtual root of the graph, all the functions available
80 /// externally are represented as callees of the node.
81 CallGraphNode *getRoot() const { return Root; }
83 /// Iterators through all the nodes of the graph that have no parent. These
84 /// are the unreachable nodes, which are either unused or are due to us
85 /// failing to add a call edge due to the analysis imprecision.
86 typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator;
87 typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator;
89 void print(raw_ostream &os) const;
91 void viewGraph() const;
93 void addNodesForBlocks(DeclContext *D);
95 /// Part of recursive declaration visitation. We recursively visit all the
96 /// declarations to collect the root functions.
97 bool VisitFunctionDecl(FunctionDecl *FD) {
98 // We skip function template definitions, as their semantics is
99 // only determined when they are instantiated.
100 if (includeInGraph(FD)) {
101 // Add all blocks declared inside this function to the graph.
102 addNodesForBlocks(FD);
103 // If this function has external linkage, anything could call it.
104 // Note, we are not precise here. For example, the function could have
105 // its address taken.
106 addNodeForDecl(FD, FD->isGlobal());
111 /// Part of recursive declaration visitation.
112 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
113 if (includeInGraph(MD)) {
114 addNodesForBlocks(MD);
115 addNodeForDecl(MD, true);
120 // We are only collecting the declarations, so do not step into the bodies.
121 bool TraverseStmt(Stmt *S) { return true; }
123 bool shouldWalkTypesOfTypeLocs() const { return false; }
126 /// \brief Add the given declaration to the call graph.
127 void addNodeForDecl(Decl *D, bool IsGlobal);
129 /// \brief Allocate a new node in the graph.
130 CallGraphNode *allocateNewNode(Decl *);
133 class CallGraphNode {
135 typedef CallGraphNode* CallRecord;
138 /// \brief The function/method declaration.
141 /// \brief The list of functions called from this node.
142 SmallVector<CallRecord, 5> CalledFunctions;
145 CallGraphNode(Decl *D) : FD(D) {}
147 typedef SmallVectorImpl<CallRecord>::iterator iterator;
148 typedef SmallVectorImpl<CallRecord>::const_iterator const_iterator;
150 /// Iterators through all the callees/children of the node.
151 inline iterator begin() { return CalledFunctions.begin(); }
152 inline iterator end() { return CalledFunctions.end(); }
153 inline const_iterator begin() const { return CalledFunctions.begin(); }
154 inline const_iterator end() const { return CalledFunctions.end(); }
156 inline bool empty() const {return CalledFunctions.empty(); }
157 inline unsigned size() const {return CalledFunctions.size(); }
159 void addCallee(CallGraphNode *N, CallGraph *CG) {
160 CalledFunctions.push_back(N);
163 Decl *getDecl() const { return FD; }
165 void print(raw_ostream &os) const;
169 } // end clang namespace
171 // Graph traits for iteration, viewing.
173 template <> struct GraphTraits<clang::CallGraphNode*> {
174 typedef clang::CallGraphNode NodeType;
175 typedef clang::CallGraphNode::CallRecord CallRecordTy;
176 typedef std::pointer_to_unary_function<CallRecordTy,
177 clang::CallGraphNode*> CGNDerefFun;
178 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
179 typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
180 static inline ChildIteratorType child_begin(NodeType *N) {
181 return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
183 static inline ChildIteratorType child_end (NodeType *N) {
184 return map_iterator(N->end(), CGNDerefFun(CGNDeref));
186 static clang::CallGraphNode *CGNDeref(CallRecordTy P) {
191 template <> struct GraphTraits<const clang::CallGraphNode*> {
192 typedef const clang::CallGraphNode NodeType;
193 typedef NodeType::const_iterator ChildIteratorType;
194 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
195 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
196 static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
199 template <> struct GraphTraits<clang::CallGraph*>
200 : public GraphTraits<clang::CallGraphNode*> {
202 static NodeType *getEntryNode(clang::CallGraph *CGN) {
203 return CGN->getRoot(); // Start at the external node!
205 typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
206 typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
207 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
208 typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator;
210 static nodes_iterator nodes_begin(clang::CallGraph *CG) {
211 return map_iterator(CG->begin(), DerefFun(CGdereference));
213 static nodes_iterator nodes_end (clang::CallGraph *CG) {
214 return map_iterator(CG->end(), DerefFun(CGdereference));
216 static clang::CallGraphNode &CGdereference(PairTy P) {
220 static unsigned size(clang::CallGraph *CG) {
225 template <> struct GraphTraits<const clang::CallGraph*> :
226 public GraphTraits<const clang::CallGraphNode*> {
227 static NodeType *getEntryNode(const clang::CallGraph *CGN) {
228 return CGN->getRoot();
230 typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
231 typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
232 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
233 typedef mapped_iterator<clang::CallGraph::const_iterator,
234 DerefFun> nodes_iterator;
236 static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
237 return map_iterator(CG->begin(), DerefFun(CGdereference));
239 static nodes_iterator nodes_end(const clang::CallGraph *CG) {
240 return map_iterator(CG->end(), DerefFun(CGdereference));
242 static clang::CallGraphNode &CGdereference(PairTy P) {
246 static unsigned size(const clang::CallGraph *CG) {
251 } // end llvm namespace