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 *, std::unique_ptr<CallGraphNode>> 38 FunctionMapTy; 39 40 /// FunctionMap owns all CallGraphNodes. 41 FunctionMapTy FunctionMap; 42 43 /// This is a virtual root node that has edges to all the functions. 44 CallGraphNode *Root; 45 46public: 47 CallGraph(); 48 ~CallGraph(); 49 50 /// \brief Populate the call graph with the functions in the given 51 /// declaration. 52 /// 53 /// Recursively walks the declaration to find all the dependent Decls as well. 54 void addToCallGraph(Decl *D) { 55 TraverseDecl(D); 56 } 57 58 /// \brief Determine if a declaration should be included in the graph. 59 static bool includeInGraph(const Decl *D); 60 61 /// \brief Lookup the node for the given declaration. 62 CallGraphNode *getNode(const Decl *) const; 63 64 /// \brief Lookup the node for the given declaration. If none found, insert 65 /// one into the graph. 66 CallGraphNode *getOrInsertNode(Decl *); 67 68 /// Iterators through all the elements in the graph. Note, this gives 69 /// non-deterministic order. 70 typedef FunctionMapTy::iterator iterator; 71 typedef FunctionMapTy::const_iterator const_iterator; 72 iterator begin() { return FunctionMap.begin(); } 73 iterator end() { return FunctionMap.end(); } 74 const_iterator begin() const { return FunctionMap.begin(); } 75 const_iterator end() const { return FunctionMap.end(); } 76 77 /// \brief Get the number of nodes in the graph. 78 unsigned size() const { return FunctionMap.size(); } 79 80 /// \ brief Get the virtual root of the graph, all the functions available 81 /// externally are represented as callees of the node. 82 CallGraphNode *getRoot() const { return Root; } 83 84 /// Iterators through all the nodes of the graph that have no parent. These 85 /// are the unreachable nodes, which are either unused or are due to us 86 /// failing to add a call edge due to the analysis imprecision. 87 typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator; 88 typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator; 89 90 void print(raw_ostream &os) const; 91 void dump() const; 92 void viewGraph() const; 93 94 void addNodesForBlocks(DeclContext *D); 95 96 /// Part of recursive declaration visitation. We recursively visit all the 97 /// declarations to collect the root functions. 98 bool VisitFunctionDecl(FunctionDecl *FD) { 99 // We skip function template definitions, as their semantics is 100 // only determined when they are instantiated. 101 if (includeInGraph(FD) && FD->isThisDeclarationADefinition()) { 102 // Add all blocks declared inside this function to the graph. 103 addNodesForBlocks(FD); 104 // If this function has external linkage, anything could call it. 105 // Note, we are not precise here. For example, the function could have 106 // its address taken. 107 addNodeForDecl(FD, FD->isGlobal()); 108 } 109 return true; 110 } 111 112 /// Part of recursive declaration visitation. 113 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 114 if (includeInGraph(MD)) { 115 addNodesForBlocks(MD); 116 addNodeForDecl(MD, true); 117 } 118 return true; 119 } 120 121 // We are only collecting the declarations, so do not step into the bodies. 122 bool TraverseStmt(Stmt *S) { return true; } 123 124 bool shouldWalkTypesOfTypeLocs() const { return false; } 125 126private: 127 /// \brief Add the given declaration to the call graph. 128 void addNodeForDecl(Decl *D, bool IsGlobal); 129 130 /// \brief Allocate a new node in the graph. 131 CallGraphNode *allocateNewNode(Decl *); 132}; 133 134class CallGraphNode { 135public: 136 typedef CallGraphNode* CallRecord; 137 138private: 139 /// \brief The function/method declaration. 140 Decl *FD; 141 142 /// \brief The list of functions called from this node. 143 SmallVector<CallRecord, 5> CalledFunctions; 144 145public: 146 CallGraphNode(Decl *D) : FD(D) {} 147 148 typedef SmallVectorImpl<CallRecord>::iterator iterator; 149 typedef SmallVectorImpl<CallRecord>::const_iterator const_iterator; 150 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(); } 156 157 inline bool empty() const {return CalledFunctions.empty(); } 158 inline unsigned size() const {return CalledFunctions.size(); } 159 160 void addCallee(CallGraphNode *N) { 161 CalledFunctions.push_back(N); 162 } 163 164 Decl *getDecl() const { return FD; } 165 166 void print(raw_ostream &os) const; 167 void dump() const; 168}; 169 170} // end clang namespace 171 172// Graph traits for iteration, viewing. 173namespace llvm { 174template <> struct GraphTraits<clang::CallGraphNode*> { 175 typedef clang::CallGraphNode NodeType; 176 typedef clang::CallGraphNode *NodeRef; 177 typedef NodeType::iterator ChildIteratorType; 178 179 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } 180 static inline ChildIteratorType child_begin(NodeType *N) { 181 return N->begin(); 182 } 183 static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } 184}; 185 186template <> struct GraphTraits<const clang::CallGraphNode*> { 187 typedef const clang::CallGraphNode NodeType; 188 typedef const clang::CallGraphNode *NodeRef; 189 typedef NodeType::const_iterator ChildIteratorType; 190 191 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } 192 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 193 static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } 194}; 195 196template <> struct GraphTraits<clang::CallGraph*> 197 : public GraphTraits<clang::CallGraphNode*> { 198 199 static NodeType *getEntryNode(clang::CallGraph *CGN) { 200 return CGN->getRoot(); // Start at the external node! 201 } 202 203 static clang::CallGraphNode * 204 CGGetValue(clang::CallGraph::const_iterator::value_type &P) { 205 return P.second.get(); 206 } 207 208 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 209 typedef mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)> 210 nodes_iterator; 211 212 static nodes_iterator nodes_begin(clang::CallGraph *CG) { 213 return nodes_iterator(CG->begin(), &CGGetValue); 214 } 215 static nodes_iterator nodes_end (clang::CallGraph *CG) { 216 return nodes_iterator(CG->end(), &CGGetValue); 217 } 218 219 static unsigned size(clang::CallGraph *CG) { 220 return CG->size(); 221 } 222}; 223 224template <> struct GraphTraits<const clang::CallGraph*> : 225 public GraphTraits<const clang::CallGraphNode*> { 226 static NodeType *getEntryNode(const clang::CallGraph *CGN) { 227 return CGN->getRoot(); 228 } 229 230 static clang::CallGraphNode * 231 CGGetValue(clang::CallGraph::const_iterator::value_type &P) { 232 return P.second.get(); 233 } 234 235 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 236 typedef mapped_iterator<clang::CallGraph::const_iterator, 237 decltype(&CGGetValue)> 238 nodes_iterator; 239 240 static nodes_iterator nodes_begin(const clang::CallGraph *CG) { 241 return nodes_iterator(CG->begin(), &CGGetValue); 242 } 243 static nodes_iterator nodes_end(const clang::CallGraph *CG) { 244 return nodes_iterator(CG->end(), &CGGetValue); 245 } 246 static unsigned size(const clang::CallGraph *CG) { 247 return CG->size(); 248 } 249}; 250 251} // end llvm namespace 252 253#endif 254