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 26 namespace clang { 27 class 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. 34 class 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 45 public: 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. addToCallGraph(Decl * D)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; begin()71 iterator begin() { return FunctionMap.begin(); } end()72 iterator end() { return FunctionMap.end(); } begin()73 const_iterator begin() const { return FunctionMap.begin(); } end()74 const_iterator end() const { return FunctionMap.end(); } 75 76 /// \brief Get the number of nodes in the graph. size()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. getRoot()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. VisitFunctionDecl(FunctionDecl * FD)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. VisitObjCMethodDecl(ObjCMethodDecl * MD)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. TraverseStmt(Stmt * S)121 bool TraverseStmt(Stmt *S) { return true; } 122 shouldWalkTypesOfTypeLocs()123 bool shouldWalkTypesOfTypeLocs() const { return false; } 124 125 private: 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 133 class CallGraphNode { 134 public: 135 typedef CallGraphNode* CallRecord; 136 137 private: 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 144 public: CallGraphNode(Decl * D)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. begin()151 inline iterator begin() { return CalledFunctions.begin(); } end()152 inline iterator end() { return CalledFunctions.end(); } begin()153 inline const_iterator begin() const { return CalledFunctions.begin(); } end()154 inline const_iterator end() const { return CalledFunctions.end(); } 155 empty()156 inline bool empty() const {return CalledFunctions.empty(); } size()157 inline unsigned size() const {return CalledFunctions.size(); } 158 addCallee(CallGraphNode * N,CallGraph * CG)159 void addCallee(CallGraphNode *N, CallGraph *CG) { 160 CalledFunctions.push_back(N); 161 } 162 getDecl()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. 172 namespace llvm { 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)); 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 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(); } 197 }; 198 199 template <> 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 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(); 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