1234287Sdim//== CallGraph.h - AST-based Call graph ------------------------*- C++ -*--==// 2234287Sdim// 3234287Sdim// The LLVM Compiler Infrastructure 4234287Sdim// 5234287Sdim// This file is distributed under the University of Illinois Open Source 6234287Sdim// License. See LICENSE.TXT for details. 7234287Sdim// 8234287Sdim//===----------------------------------------------------------------------===// 9234287Sdim// 10234287Sdim// This file declares the AST-based CallGraph. 11234287Sdim// 12234287Sdim// A call graph for functions whose definitions/bodies are available in the 13234287Sdim// current translation unit. The graph has a "virtual" root node that contains 14234287Sdim// edges to all externally available functions. 15234287Sdim//===----------------------------------------------------------------------===// 16234287Sdim 17234287Sdim#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH 18234287Sdim#define LLVM_CLANG_ANALYSIS_CALLGRAPH 19234287Sdim 20234287Sdim#include "clang/AST/DeclBase.h" 21234287Sdim#include "clang/AST/RecursiveASTVisitor.h" 22234287Sdim#include "llvm/ADT/DenseMap.h" 23234287Sdim#include "llvm/ADT/GraphTraits.h" 24234287Sdim#include "llvm/ADT/SetVector.h" 25234287Sdim 26234287Sdimnamespace clang { 27234287Sdimclass CallGraphNode; 28234287Sdim 29239462Sdim/// \brief The AST-based call graph. 30234287Sdim/// 31234287Sdim/// The call graph extends itself with the given declarations by implementing 32234287Sdim/// the recursive AST visitor, which constructs the graph by visiting the given 33234287Sdim/// declarations. 34234287Sdimclass CallGraph : public RecursiveASTVisitor<CallGraph> { 35234287Sdim friend class CallGraphNode; 36234287Sdim 37234287Sdim typedef llvm::DenseMap<const Decl *, CallGraphNode *> FunctionMapTy; 38234287Sdim 39234287Sdim /// FunctionMap owns all CallGraphNodes. 40234287Sdim FunctionMapTy FunctionMap; 41234287Sdim 42249423Sdim /// This is a virtual root node that has edges to all the functions. 43234287Sdim CallGraphNode *Root; 44234287Sdim 45234287Sdimpublic: 46234287Sdim CallGraph(); 47234287Sdim ~CallGraph(); 48234287Sdim 49234287Sdim /// \brief Populate the call graph with the functions in the given 50234287Sdim /// declaration. 51234287Sdim /// 52234287Sdim /// Recursively walks the declaration to find all the dependent Decls as well. 53234287Sdim void addToCallGraph(Decl *D) { 54234287Sdim TraverseDecl(D); 55234287Sdim } 56234287Sdim 57234287Sdim /// \brief Determine if a declaration should be included in the graph. 58234287Sdim static bool includeInGraph(const Decl *D); 59234287Sdim 60234287Sdim /// \brief Lookup the node for the given declaration. 61234287Sdim CallGraphNode *getNode(const Decl *) const; 62234287Sdim 63234287Sdim /// \brief Lookup the node for the given declaration. If none found, insert 64234287Sdim /// one into the graph. 65234287Sdim CallGraphNode *getOrInsertNode(Decl *); 66234287Sdim 67234287Sdim /// Iterators through all the elements in the graph. Note, this gives 68234287Sdim /// non-deterministic order. 69234287Sdim typedef FunctionMapTy::iterator iterator; 70234287Sdim typedef FunctionMapTy::const_iterator const_iterator; 71234287Sdim iterator begin() { return FunctionMap.begin(); } 72234287Sdim iterator end() { return FunctionMap.end(); } 73234287Sdim const_iterator begin() const { return FunctionMap.begin(); } 74234287Sdim const_iterator end() const { return FunctionMap.end(); } 75234287Sdim 76234287Sdim /// \brief Get the number of nodes in the graph. 77234287Sdim unsigned size() const { return FunctionMap.size(); } 78234287Sdim 79234287Sdim /// \ brief Get the virtual root of the graph, all the functions available 80234287Sdim /// externally are represented as callees of the node. 81234287Sdim CallGraphNode *getRoot() const { return Root; } 82234287Sdim 83234287Sdim /// Iterators through all the nodes of the graph that have no parent. These 84234287Sdim /// are the unreachable nodes, which are either unused or are due to us 85234287Sdim /// failing to add a call edge due to the analysis imprecision. 86234287Sdim typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator; 87234287Sdim typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator; 88234287Sdim 89234287Sdim void print(raw_ostream &os) const; 90234287Sdim void dump() const; 91234287Sdim void viewGraph() const; 92234287Sdim 93249423Sdim void addNodesForBlocks(DeclContext *D); 94249423Sdim 95239462Sdim /// Part of recursive declaration visitation. We recursively visit all the 96249423Sdim /// declarations to collect the root functions. 97234287Sdim bool VisitFunctionDecl(FunctionDecl *FD) { 98234287Sdim // We skip function template definitions, as their semantics is 99234287Sdim // only determined when they are instantiated. 100249423Sdim if (includeInGraph(FD)) { 101249423Sdim // Add all blocks declared inside this function to the graph. 102249423Sdim addNodesForBlocks(FD); 103234287Sdim // If this function has external linkage, anything could call it. 104234287Sdim // Note, we are not precise here. For example, the function could have 105234287Sdim // its address taken. 106234287Sdim addNodeForDecl(FD, FD->isGlobal()); 107249423Sdim } 108234287Sdim return true; 109234287Sdim } 110234287Sdim 111234287Sdim /// Part of recursive declaration visitation. 112234287Sdim bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 113249423Sdim if (includeInGraph(MD)) { 114249423Sdim addNodesForBlocks(MD); 115234287Sdim addNodeForDecl(MD, true); 116249423Sdim } 117234287Sdim return true; 118234287Sdim } 119234287Sdim 120239462Sdim // We are only collecting the declarations, so do not step into the bodies. 121239462Sdim bool TraverseStmt(Stmt *S) { return true; } 122239462Sdim 123239462Sdim bool shouldWalkTypesOfTypeLocs() const { return false; } 124239462Sdim 125234287Sdimprivate: 126234287Sdim /// \brief Add the given declaration to the call graph. 127234287Sdim void addNodeForDecl(Decl *D, bool IsGlobal); 128234287Sdim 129234287Sdim /// \brief Allocate a new node in the graph. 130234287Sdim CallGraphNode *allocateNewNode(Decl *); 131234287Sdim}; 132234287Sdim 133234287Sdimclass CallGraphNode { 134234287Sdimpublic: 135234287Sdim typedef CallGraphNode* CallRecord; 136234287Sdim 137234287Sdimprivate: 138234287Sdim /// \brief The function/method declaration. 139234287Sdim Decl *FD; 140234287Sdim 141234287Sdim /// \brief The list of functions called from this node. 142249423Sdim SmallVector<CallRecord, 5> CalledFunctions; 143234287Sdim 144234287Sdimpublic: 145234287Sdim CallGraphNode(Decl *D) : FD(D) {} 146234287Sdim 147249423Sdim typedef SmallVector<CallRecord, 5>::iterator iterator; 148249423Sdim typedef SmallVector<CallRecord, 5>::const_iterator const_iterator; 149234287Sdim 150234287Sdim /// Iterators through all the callees/children of the node. 151234287Sdim inline iterator begin() { return CalledFunctions.begin(); } 152234287Sdim inline iterator end() { return CalledFunctions.end(); } 153234287Sdim inline const_iterator begin() const { return CalledFunctions.begin(); } 154234287Sdim inline const_iterator end() const { return CalledFunctions.end(); } 155234287Sdim 156234287Sdim inline bool empty() const {return CalledFunctions.empty(); } 157234287Sdim inline unsigned size() const {return CalledFunctions.size(); } 158234287Sdim 159234287Sdim void addCallee(CallGraphNode *N, CallGraph *CG) { 160234287Sdim CalledFunctions.push_back(N); 161234287Sdim } 162234287Sdim 163234287Sdim Decl *getDecl() const { return FD; } 164234287Sdim 165234287Sdim void print(raw_ostream &os) const; 166234287Sdim void dump() const; 167234287Sdim}; 168234287Sdim 169234287Sdim} // end clang namespace 170234287Sdim 171234287Sdim// Graph traits for iteration, viewing. 172234287Sdimnamespace llvm { 173234287Sdimtemplate <> struct GraphTraits<clang::CallGraphNode*> { 174234287Sdim typedef clang::CallGraphNode NodeType; 175234287Sdim typedef clang::CallGraphNode::CallRecord CallRecordTy; 176234287Sdim typedef std::pointer_to_unary_function<CallRecordTy, 177234287Sdim clang::CallGraphNode*> CGNDerefFun; 178234287Sdim static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } 179234287Sdim typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; 180234287Sdim static inline ChildIteratorType child_begin(NodeType *N) { 181234287Sdim return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); 182234287Sdim } 183234287Sdim static inline ChildIteratorType child_end (NodeType *N) { 184234287Sdim return map_iterator(N->end(), CGNDerefFun(CGNDeref)); 185234287Sdim } 186234287Sdim static clang::CallGraphNode *CGNDeref(CallRecordTy P) { 187234287Sdim return P; 188234287Sdim } 189234287Sdim}; 190234287Sdim 191234287Sdimtemplate <> struct GraphTraits<const clang::CallGraphNode*> { 192234287Sdim typedef const clang::CallGraphNode NodeType; 193234287Sdim typedef NodeType::const_iterator ChildIteratorType; 194234287Sdim static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } 195234287Sdim static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 196249423Sdim static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } 197234287Sdim}; 198234287Sdim 199234287Sdimtemplate <> struct GraphTraits<clang::CallGraph*> 200234287Sdim : public GraphTraits<clang::CallGraphNode*> { 201234287Sdim 202234287Sdim static NodeType *getEntryNode(clang::CallGraph *CGN) { 203234287Sdim return CGN->getRoot(); // Start at the external node! 204234287Sdim } 205234287Sdim typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; 206234287Sdim typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; 207234287Sdim // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 208234287Sdim typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator; 209234287Sdim 210234287Sdim static nodes_iterator nodes_begin(clang::CallGraph *CG) { 211234287Sdim return map_iterator(CG->begin(), DerefFun(CGdereference)); 212234287Sdim } 213234287Sdim static nodes_iterator nodes_end (clang::CallGraph *CG) { 214234287Sdim return map_iterator(CG->end(), DerefFun(CGdereference)); 215234287Sdim } 216234287Sdim static clang::CallGraphNode &CGdereference(PairTy P) { 217234287Sdim return *(P.second); 218234287Sdim } 219234287Sdim 220234287Sdim static unsigned size(clang::CallGraph *CG) { 221234287Sdim return CG->size(); 222234287Sdim } 223234287Sdim}; 224234287Sdim 225234287Sdimtemplate <> struct GraphTraits<const clang::CallGraph*> : 226234287Sdim public GraphTraits<const clang::CallGraphNode*> { 227234287Sdim static NodeType *getEntryNode(const clang::CallGraph *CGN) { 228234287Sdim return CGN->getRoot(); 229234287Sdim } 230234287Sdim typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; 231234287Sdim typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; 232234287Sdim // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 233234287Sdim typedef mapped_iterator<clang::CallGraph::const_iterator, 234234287Sdim DerefFun> nodes_iterator; 235234287Sdim 236234287Sdim static nodes_iterator nodes_begin(const clang::CallGraph *CG) { 237234287Sdim return map_iterator(CG->begin(), DerefFun(CGdereference)); 238234287Sdim } 239234287Sdim static nodes_iterator nodes_end(const clang::CallGraph *CG) { 240234287Sdim return map_iterator(CG->end(), DerefFun(CGdereference)); 241234287Sdim } 242234287Sdim static clang::CallGraphNode &CGdereference(PairTy P) { 243234287Sdim return *(P.second); 244234287Sdim } 245234287Sdim 246234287Sdim static unsigned size(const clang::CallGraph *CG) { 247234287Sdim return CG->size(); 248234287Sdim } 249234287Sdim}; 250234287Sdim 251234287Sdim} // end llvm namespace 252234287Sdim 253234287Sdim#endif 254