CallGraph.h revision 263508
1258057Sbr//== CallGraph.h - AST-based Call graph ------------------------*- C++ -*--==// 2258057Sbr// 3258057Sbr// The LLVM Compiler Infrastructure 4258057Sbr// 5258057Sbr// This file is distributed under the University of Illinois Open Source 6258057Sbr// License. See LICENSE.TXT for details. 7258057Sbr// 8258057Sbr//===----------------------------------------------------------------------===// 9258057Sbr// 10258057Sbr// This file declares the AST-based CallGraph. 11258057Sbr// 12258057Sbr// A call graph for functions whose definitions/bodies are available in the 13258057Sbr// current translation unit. The graph has a "virtual" root node that contains 14258057Sbr// edges to all externally available functions. 15258057Sbr//===----------------------------------------------------------------------===// 16258057Sbr 17258057Sbr#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH 18258057Sbr#define LLVM_CLANG_ANALYSIS_CALLGRAPH 19258057Sbr 20258057Sbr#include "clang/AST/DeclBase.h" 21258057Sbr#include "clang/AST/RecursiveASTVisitor.h" 22258057Sbr#include "llvm/ADT/DenseMap.h" 23258057Sbr#include "llvm/ADT/GraphTraits.h" 24258057Sbr#include "llvm/ADT/SetVector.h" 25258057Sbr 26258057Sbrnamespace clang { 27258057Sbrclass CallGraphNode; 28258057Sbr 29258057Sbr/// \brief The AST-based call graph. 30258057Sbr/// 31258057Sbr/// The call graph extends itself with the given declarations by implementing 32258057Sbr/// the recursive AST visitor, which constructs the graph by visiting the given 33258057Sbr/// declarations. 34258057Sbrclass CallGraph : public RecursiveASTVisitor<CallGraph> { 35258057Sbr friend class CallGraphNode; 36258057Sbr 37258057Sbr typedef llvm::DenseMap<const Decl *, CallGraphNode *> FunctionMapTy; 38258057Sbr 39258057Sbr /// FunctionMap owns all CallGraphNodes. 40258057Sbr FunctionMapTy FunctionMap; 41258057Sbr 42258057Sbr /// This is a virtual root node that has edges to all the functions. 43258057Sbr CallGraphNode *Root; 44258057Sbr 45258057Sbrpublic: 46258057Sbr CallGraph(); 47258057Sbr ~CallGraph(); 48258057Sbr 49258057Sbr /// \brief Populate the call graph with the functions in the given 50258057Sbr /// declaration. 51258057Sbr /// 52258057Sbr /// Recursively walks the declaration to find all the dependent Decls as well. 53258057Sbr void addToCallGraph(Decl *D) { 54258057Sbr TraverseDecl(D); 55258057Sbr } 56258057Sbr 57258057Sbr /// \brief Determine if a declaration should be included in the graph. 58258057Sbr static bool includeInGraph(const Decl *D); 59258057Sbr 60258057Sbr /// \brief Lookup the node for the given declaration. 61258057Sbr CallGraphNode *getNode(const Decl *) const; 62258057Sbr 63258057Sbr /// \brief Lookup the node for the given declaration. If none found, insert 64258057Sbr /// one into the graph. 65258057Sbr CallGraphNode *getOrInsertNode(Decl *); 66258057Sbr 67258057Sbr /// Iterators through all the elements in the graph. Note, this gives 68258057Sbr /// non-deterministic order. 69258057Sbr typedef FunctionMapTy::iterator iterator; 70258057Sbr typedef FunctionMapTy::const_iterator const_iterator; 71258057Sbr iterator begin() { return FunctionMap.begin(); } 72258057Sbr iterator end() { return FunctionMap.end(); } 73258057Sbr const_iterator begin() const { return FunctionMap.begin(); } 74258057Sbr const_iterator end() const { return FunctionMap.end(); } 75258057Sbr 76258057Sbr /// \brief Get the number of nodes in the graph. 77261410Sian unsigned size() const { return FunctionMap.size(); } 78261410Sian 79261410Sian /// \ brief Get the virtual root of the graph, all the functions available 80258057Sbr /// externally are represented as callees of the node. 81258057Sbr CallGraphNode *getRoot() const { return Root; } 82258057Sbr 83258057Sbr /// Iterators through all the nodes of the graph that have no parent. These 84258057Sbr /// are the unreachable nodes, which are either unused or are due to us 85258057Sbr /// failing to add a call edge due to the analysis imprecision. 86258057Sbr typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator; 87258057Sbr typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator; 88258057Sbr 89258057Sbr void print(raw_ostream &os) const; 90258057Sbr void dump() const; 91258057Sbr void viewGraph() const; 92258057Sbr 93258057Sbr void addNodesForBlocks(DeclContext *D); 94258057Sbr 95258057Sbr /// Part of recursive declaration visitation. We recursively visit all the 96258057Sbr /// declarations to collect the root functions. 97258057Sbr bool VisitFunctionDecl(FunctionDecl *FD) { 98258057Sbr // We skip function template definitions, as their semantics is 99258057Sbr // only determined when they are instantiated. 100258057Sbr if (includeInGraph(FD)) { 101258057Sbr // Add all blocks declared inside this function to the graph. 102258057Sbr addNodesForBlocks(FD); 103258057Sbr // If this function has external linkage, anything could call it. 104258057Sbr // Note, we are not precise here. For example, the function could have 105258057Sbr // its address taken. 106258057Sbr addNodeForDecl(FD, FD->isGlobal()); 107258057Sbr } 108258057Sbr return true; 109258057Sbr } 110258057Sbr 111258057Sbr /// Part of recursive declaration visitation. 112258057Sbr bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 113258057Sbr if (includeInGraph(MD)) { 114258057Sbr addNodesForBlocks(MD); 115258057Sbr addNodeForDecl(MD, true); 116258057Sbr } 117258057Sbr return true; 118258057Sbr } 119258057Sbr 120258057Sbr // We are only collecting the declarations, so do not step into the bodies. 121258057Sbr bool TraverseStmt(Stmt *S) { return true; } 122258057Sbr 123258057Sbr bool shouldWalkTypesOfTypeLocs() const { return false; } 124258057Sbr 125258057Sbrprivate: 126 /// \brief Add the given declaration to the call graph. 127 void addNodeForDecl(Decl *D, bool IsGlobal); 128 129 /// \brief Allocate a new node in the graph. 130 CallGraphNode *allocateNewNode(Decl *); 131}; 132 133class CallGraphNode { 134public: 135 typedef CallGraphNode* CallRecord; 136 137private: 138 /// \brief The function/method declaration. 139 Decl *FD; 140 141 /// \brief The list of functions called from this node. 142 SmallVector<CallRecord, 5> CalledFunctions; 143 144public: 145 CallGraphNode(Decl *D) : FD(D) {} 146 147 typedef SmallVectorImpl<CallRecord>::iterator iterator; 148 typedef SmallVectorImpl<CallRecord>::const_iterator const_iterator; 149 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(); } 155 156 inline bool empty() const {return CalledFunctions.empty(); } 157 inline unsigned size() const {return CalledFunctions.size(); } 158 159 void addCallee(CallGraphNode *N, CallGraph *CG) { 160 CalledFunctions.push_back(N); 161 } 162 163 Decl *getDecl() const { return FD; } 164 165 void print(raw_ostream &os) const; 166 void dump() const; 167}; 168 169} // end clang namespace 170 171// Graph traits for iteration, viewing. 172namespace llvm { 173template <> 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)); 182 } 183 static inline ChildIteratorType child_end (NodeType *N) { 184 return map_iterator(N->end(), CGNDerefFun(CGNDeref)); 185 } 186 static clang::CallGraphNode *CGNDeref(CallRecordTy P) { 187 return P; 188 } 189}; 190 191template <> 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(); } 197}; 198 199template <> struct GraphTraits<clang::CallGraph*> 200 : public GraphTraits<clang::CallGraphNode*> { 201 202 static NodeType *getEntryNode(clang::CallGraph *CGN) { 203 return CGN->getRoot(); // Start at the external node! 204 } 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; 209 210 static nodes_iterator nodes_begin(clang::CallGraph *CG) { 211 return map_iterator(CG->begin(), DerefFun(CGdereference)); 212 } 213 static nodes_iterator nodes_end (clang::CallGraph *CG) { 214 return map_iterator(CG->end(), DerefFun(CGdereference)); 215 } 216 static clang::CallGraphNode &CGdereference(PairTy P) { 217 return *(P.second); 218 } 219 220 static unsigned size(clang::CallGraph *CG) { 221 return CG->size(); 222 } 223}; 224 225template <> struct GraphTraits<const clang::CallGraph*> : 226 public GraphTraits<const clang::CallGraphNode*> { 227 static NodeType *getEntryNode(const clang::CallGraph *CGN) { 228 return CGN->getRoot(); 229 } 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; 235 236 static nodes_iterator nodes_begin(const clang::CallGraph *CG) { 237 return map_iterator(CG->begin(), DerefFun(CGdereference)); 238 } 239 static nodes_iterator nodes_end(const clang::CallGraph *CG) { 240 return map_iterator(CG->end(), DerefFun(CGdereference)); 241 } 242 static clang::CallGraphNode &CGdereference(PairTy P) { 243 return *(P.second); 244 } 245 246 static unsigned size(const clang::CallGraph *CG) { 247 return CG->size(); 248 } 249}; 250 251} // end llvm namespace 252 253#endif 254