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#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH_H 18#define LLVM_CLANG_ANALYSIS_CALLGRAPH_H 19 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" 25 26namespace clang { 27class CallGraphNode; 28 29/// \brief The AST-based call graph. 30/// 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 33/// declarations. 34class CallGraph : public RecursiveASTVisitor<CallGraph> { 35 friend class CallGraphNode; 36 37 typedef llvm::DenseMap<const Decl *, CallGraphNode *> FunctionMapTy; 38 39 /// FunctionMap owns all CallGraphNodes. 40 FunctionMapTy FunctionMap; 41 42 /// This is a virtual root node that has edges to all the functions. 43 CallGraphNode *Root; 44 45public: 46 CallGraph(); 47 ~CallGraph(); 48 49 /// \brief Populate the call graph with the functions in the given 50 /// declaration. 51 /// 52 /// Recursively walks the declaration to find all the dependent Decls as well. 53 void addToCallGraph(Decl *D) { 54 TraverseDecl(D); 55 } 56 57 /// \brief Determine if a declaration should be included in the graph. 58 static bool includeInGraph(const Decl *D); 59 60 /// \brief Lookup the node for the given declaration. 61 CallGraphNode *getNode(const Decl *) const; 62 63 /// \brief Lookup the node for the given declaration. If none found, insert 64 /// one into the graph. 65 CallGraphNode *getOrInsertNode(Decl *); 66 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(); } 75 76 /// \brief Get the number of nodes in the graph. 77 unsigned size() const { return FunctionMap.size(); } 78 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; } 82 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; 88 89 void print(raw_ostream &os) const; 90 void dump() const; 91 void viewGraph() const; 92 93 void addNodesForBlocks(DeclContext *D); 94 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()); 107 } 108 return true; 109 } 110 111 /// Part of recursive declaration visitation. 112 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 113 if (includeInGraph(MD)) { 114 addNodesForBlocks(MD); 115 addNodeForDecl(MD, true); 116 } 117 return true; 118 } 119 120 // We are only collecting the declarations, so do not step into the bodies. 121 bool TraverseStmt(Stmt *S) { return true; } 122 123 bool shouldWalkTypesOfTypeLocs() const { return false; } 124 125private: 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