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
18 #define LLVM_CLANG_ANALYSIS_CALLGRAPH
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 /// \class 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 global functions -
43 /// 'main' or functions accessible from other translation units.
46 /// The list of nodes that have no parent. These are unreachable from Root.
47 /// Declarations can get to this list due to impressions in the graph, for
48 /// example, we do not track functions whose addresses were taken.
49 llvm::SetVector<CallGraphNode *> ParentlessNodes;
55 /// \brief Populate the call graph with the functions in the given
58 /// Recursively walks the declaration to find all the dependent Decls as well.
59 void addToCallGraph(Decl *D) {
63 /// \brief Determine if a declaration should be included in the graph.
64 static bool includeInGraph(const Decl *D);
66 /// \brief Lookup the node for the given declaration.
67 CallGraphNode *getNode(const Decl *) const;
69 /// \brief Lookup the node for the given declaration. If none found, insert
70 /// one into the graph.
71 CallGraphNode *getOrInsertNode(Decl *);
73 /// Iterators through all the elements in the graph. Note, this gives
74 /// non-deterministic order.
75 typedef FunctionMapTy::iterator iterator;
76 typedef FunctionMapTy::const_iterator const_iterator;
77 iterator begin() { return FunctionMap.begin(); }
78 iterator end() { return FunctionMap.end(); }
79 const_iterator begin() const { return FunctionMap.begin(); }
80 const_iterator end() const { return FunctionMap.end(); }
82 /// \brief Get the number of nodes in the graph.
83 unsigned size() const { return FunctionMap.size(); }
85 /// \ brief Get the virtual root of the graph, all the functions available
86 /// externally are represented as callees of the node.
87 CallGraphNode *getRoot() const { return Root; }
89 /// Iterators through all the nodes of the graph that have no parent. These
90 /// are the unreachable nodes, which are either unused or are due to us
91 /// failing to add a call edge due to the analysis imprecision.
92 typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator;
93 typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator;
94 nodes_iterator parentless_begin() { return ParentlessNodes.begin(); }
95 nodes_iterator parentless_end() { return ParentlessNodes.end(); }
97 parentless_begin() const { return ParentlessNodes.begin(); }
99 parentless_end() const { return ParentlessNodes.end(); }
101 void print(raw_ostream &os) const;
103 void viewGraph() const;
105 /// Part of recursive declaration visitation.
106 bool VisitFunctionDecl(FunctionDecl *FD) {
107 // We skip function template definitions, as their semantics is
108 // only determined when they are instantiated.
109 if (includeInGraph(FD))
110 // If this function has external linkage, anything could call it.
111 // Note, we are not precise here. For example, the function could have
112 // its address taken.
113 addNodeForDecl(FD, FD->isGlobal());
117 /// Part of recursive declaration visitation.
118 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
119 if (includeInGraph(MD))
120 addNodeForDecl(MD, true);
125 /// \brief Add the given declaration to the call graph.
126 void addNodeForDecl(Decl *D, bool IsGlobal);
128 /// \brief Allocate a new node in the graph.
129 CallGraphNode *allocateNewNode(Decl *);
132 class CallGraphNode {
134 typedef CallGraphNode* CallRecord;
137 /// \brief The function/method declaration.
140 /// \brief The list of functions called from this node.
141 // Small vector might be more efficient since we are only tracking functions
142 // whose definition is in the current TU.
143 llvm::SmallVector<CallRecord, 5> CalledFunctions;
146 CallGraphNode(Decl *D) : FD(D) {}
148 typedef llvm::SmallVector<CallRecord, 5>::iterator iterator;
149 typedef llvm::SmallVector<CallRecord, 5>::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, CallGraph *CG) {
161 CalledFunctions.push_back(N);
162 CG->ParentlessNodes.remove(N);
165 Decl *getDecl() const { return FD; }
167 StringRef getName() const;
169 void print(raw_ostream &os) const;
173 } // end clang namespace
175 // Graph traits for iteration, viewing.
177 template <> struct GraphTraits<clang::CallGraphNode*> {
178 typedef clang::CallGraphNode NodeType;
179 typedef clang::CallGraphNode::CallRecord CallRecordTy;
180 typedef std::pointer_to_unary_function<CallRecordTy,
181 clang::CallGraphNode*> CGNDerefFun;
182 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
183 typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
184 static inline ChildIteratorType child_begin(NodeType *N) {
185 return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
187 static inline ChildIteratorType child_end (NodeType *N) {
188 return map_iterator(N->end(), CGNDerefFun(CGNDeref));
190 static clang::CallGraphNode *CGNDeref(CallRecordTy P) {
195 template <> struct GraphTraits<const clang::CallGraphNode*> {
196 typedef const clang::CallGraphNode NodeType;
197 typedef NodeType::const_iterator ChildIteratorType;
198 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
199 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
200 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); }
203 template <> struct GraphTraits<clang::CallGraph*>
204 : public GraphTraits<clang::CallGraphNode*> {
206 static NodeType *getEntryNode(clang::CallGraph *CGN) {
207 return CGN->getRoot(); // Start at the external node!
209 typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
210 typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
211 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
212 typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator;
214 static nodes_iterator nodes_begin(clang::CallGraph *CG) {
215 return map_iterator(CG->begin(), DerefFun(CGdereference));
217 static nodes_iterator nodes_end (clang::CallGraph *CG) {
218 return map_iterator(CG->end(), DerefFun(CGdereference));
220 static clang::CallGraphNode &CGdereference(PairTy P) {
224 static unsigned size(clang::CallGraph *CG) {
229 template <> struct GraphTraits<const clang::CallGraph*> :
230 public GraphTraits<const clang::CallGraphNode*> {
231 static NodeType *getEntryNode(const clang::CallGraph *CGN) {
232 return CGN->getRoot();
234 typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
235 typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
236 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
237 typedef mapped_iterator<clang::CallGraph::const_iterator,
238 DerefFun> nodes_iterator;
240 static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
241 return map_iterator(CG->begin(), DerefFun(CGdereference));
243 static nodes_iterator nodes_end(const clang::CallGraph *CG) {
244 return map_iterator(CG->end(), DerefFun(CGdereference));
246 static clang::CallGraphNode &CGdereference(PairTy P) {
250 static unsigned size(const clang::CallGraph *CG) {
255 } // end llvm namespace