CallGraph.h revision 6d42f4d8b8a176336a8c49ec3cf5f7fb6545ccfd
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 18#define LLVM_CLANG_ANALYSIS_CALLGRAPH 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 global functions - 43 /// 'main' or functions accessible from other translation units. 44 CallGraphNode *Root; 45 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; 50 51public: 52 CallGraph(); 53 ~CallGraph(); 54 55 /// \brief Populate the call graph with the functions in the given 56 /// declaration. 57 /// 58 /// Recursively walks the declaration to find all the dependent Decls as well. 59 void addToCallGraph(Decl *D) { 60 TraverseDecl(D); 61 } 62 63 /// \brief Determine if a declaration should be included in the graph. 64 static bool includeInGraph(const Decl *D); 65 66 /// \brief Lookup the node for the given declaration. 67 CallGraphNode *getNode(const Decl *) const; 68 69 /// \brief Lookup the node for the given declaration. If none found, insert 70 /// one into the graph. 71 CallGraphNode *getOrInsertNode(Decl *); 72 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(); } 81 82 /// \brief Get the number of nodes in the graph. 83 unsigned size() const { return FunctionMap.size(); } 84 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; } 88 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(); } 96 const_nodes_iterator 97 parentless_begin() const { return ParentlessNodes.begin(); } 98 const_nodes_iterator 99 parentless_end() const { return ParentlessNodes.end(); } 100 101 void print(raw_ostream &os) const; 102 void dump() const; 103 void viewGraph() const; 104 105 void addNodesForBlocks(DeclContext *D); 106 107 /// Part of recursive declaration visitation. We recursively visit all the 108 /// declarations to collect the root functions. 109 bool VisitFunctionDecl(FunctionDecl *FD) { 110 // We skip function template definitions, as their semantics is 111 // only determined when they are instantiated. 112 if (includeInGraph(FD)) { 113 // Add all blocks declared inside this function to the graph. 114 addNodesForBlocks(FD); 115 // If this function has external linkage, anything could call it. 116 // Note, we are not precise here. For example, the function could have 117 // its address taken. 118 addNodeForDecl(FD, FD->isGlobal()); 119 } 120 return true; 121 } 122 123 /// Part of recursive declaration visitation. 124 bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 125 if (includeInGraph(MD)) { 126 addNodesForBlocks(MD); 127 addNodeForDecl(MD, true); 128 } 129 return true; 130 } 131 132 // We are only collecting the declarations, so do not step into the bodies. 133 bool TraverseStmt(Stmt *S) { return true; } 134 135 bool shouldWalkTypesOfTypeLocs() const { return false; } 136 137private: 138 /// \brief Add the given declaration to the call graph. 139 void addNodeForDecl(Decl *D, bool IsGlobal); 140 141 /// \brief Allocate a new node in the graph. 142 CallGraphNode *allocateNewNode(Decl *); 143}; 144 145class CallGraphNode { 146public: 147 typedef CallGraphNode* CallRecord; 148 149private: 150 /// \brief The function/method declaration. 151 Decl *FD; 152 153 /// \brief The list of functions called from this node. 154 llvm::SmallVector<CallRecord, 5> CalledFunctions; 155 156public: 157 CallGraphNode(Decl *D) : FD(D) {} 158 159 typedef llvm::SmallVector<CallRecord, 5>::iterator iterator; 160 typedef llvm::SmallVector<CallRecord, 5>::const_iterator const_iterator; 161 162 /// Iterators through all the callees/children of the node. 163 inline iterator begin() { return CalledFunctions.begin(); } 164 inline iterator end() { return CalledFunctions.end(); } 165 inline const_iterator begin() const { return CalledFunctions.begin(); } 166 inline const_iterator end() const { return CalledFunctions.end(); } 167 168 inline bool empty() const {return CalledFunctions.empty(); } 169 inline unsigned size() const {return CalledFunctions.size(); } 170 171 void addCallee(CallGraphNode *N, CallGraph *CG) { 172 CalledFunctions.push_back(N); 173 CG->ParentlessNodes.remove(N); 174 } 175 176 Decl *getDecl() const { return FD; } 177 178 void print(raw_ostream &os) const; 179 void dump() const; 180}; 181 182} // end clang namespace 183 184// Graph traits for iteration, viewing. 185namespace llvm { 186template <> struct GraphTraits<clang::CallGraphNode*> { 187 typedef clang::CallGraphNode NodeType; 188 typedef clang::CallGraphNode::CallRecord CallRecordTy; 189 typedef std::pointer_to_unary_function<CallRecordTy, 190 clang::CallGraphNode*> CGNDerefFun; 191 static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } 192 typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; 193 static inline ChildIteratorType child_begin(NodeType *N) { 194 return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); 195 } 196 static inline ChildIteratorType child_end (NodeType *N) { 197 return map_iterator(N->end(), CGNDerefFun(CGNDeref)); 198 } 199 static clang::CallGraphNode *CGNDeref(CallRecordTy P) { 200 return P; 201 } 202}; 203 204template <> struct GraphTraits<const clang::CallGraphNode*> { 205 typedef const clang::CallGraphNode NodeType; 206 typedef NodeType::const_iterator ChildIteratorType; 207 static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } 208 static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 209 static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 210}; 211 212template <> struct GraphTraits<clang::CallGraph*> 213 : public GraphTraits<clang::CallGraphNode*> { 214 215 static NodeType *getEntryNode(clang::CallGraph *CGN) { 216 return CGN->getRoot(); // Start at the external node! 217 } 218 typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; 219 typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; 220 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 221 typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator; 222 223 static nodes_iterator nodes_begin(clang::CallGraph *CG) { 224 return map_iterator(CG->begin(), DerefFun(CGdereference)); 225 } 226 static nodes_iterator nodes_end (clang::CallGraph *CG) { 227 return map_iterator(CG->end(), DerefFun(CGdereference)); 228 } 229 static clang::CallGraphNode &CGdereference(PairTy P) { 230 return *(P.second); 231 } 232 233 static unsigned size(clang::CallGraph *CG) { 234 return CG->size(); 235 } 236}; 237 238template <> struct GraphTraits<const clang::CallGraph*> : 239 public GraphTraits<const clang::CallGraphNode*> { 240 static NodeType *getEntryNode(const clang::CallGraph *CGN) { 241 return CGN->getRoot(); 242 } 243 typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; 244 typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; 245 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 246 typedef mapped_iterator<clang::CallGraph::const_iterator, 247 DerefFun> nodes_iterator; 248 249 static nodes_iterator nodes_begin(const clang::CallGraph *CG) { 250 return map_iterator(CG->begin(), DerefFun(CGdereference)); 251 } 252 static nodes_iterator nodes_end(const clang::CallGraph *CG) { 253 return map_iterator(CG->end(), DerefFun(CGdereference)); 254 } 255 static clang::CallGraphNode &CGdereference(PairTy P) { 256 return *(P.second); 257 } 258 259 static unsigned size(const clang::CallGraph *CG) { 260 return CG->size(); 261 } 262}; 263 264} // end llvm namespace 265 266#endif 267