CallGraph.h revision e2c9238d7b53fdfd99e724ce50de9197a23727fa
1196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks//== CallGraph.h - AST-based Call graph ------------------------*- C++ -*--==// 2196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// 3196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// The LLVM Compiler Infrastructure 4196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// 5196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// This file is distributed under the University of Illinois Open Source 6196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// License. See LICENSE.TXT for details. 7196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// 8196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks//===----------------------------------------------------------------------===// 9196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// 10196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// This file declares the AST-based CallGraph. 11196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// 12196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// A call graph for functions whose definitions/bodies are available in the 13196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// current translation unit. The graph has a "virtual" root node that contains 14196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// edges to all externally available functions. 15196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks//===----------------------------------------------------------------------===// 16196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 17196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH 18196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks#define LLVM_CLANG_ANALYSIS_CALLGRAPH 19196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 20196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks#include "clang/AST/DeclBase.h" 216a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks#include "clang/AST/RecursiveASTVisitor.h" 22196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks#include "llvm/ADT/DenseMap.h" 23196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks#include "llvm/ADT/GraphTraits.h" 24196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks#include "llvm/ADT/SetVector.h" 25196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 26196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaksnamespace clang { 27196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaksclass CallGraphNode; 28196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 2941c2bcff88a23a046ee8d71451bc03717a4248f6Chandler Carruth/// \brief The AST-based call graph. 306a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks/// 316a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks/// The call graph extends itself with the given declarations by implementing 326a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks/// the recursive AST visitor, which constructs the graph by visiting the given 336a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks/// declarations. 346a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaksclass CallGraph : public RecursiveASTVisitor<CallGraph> { 35196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks friend class CallGraphNode; 366a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 37a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks typedef llvm::DenseMap<const Decl *, CallGraphNode *> FunctionMapTy; 38196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 39196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// FunctionMap owns all CallGraphNodes. 40196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks FunctionMapTy FunctionMap; 41196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 42196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// This is a virtual root node that has edges to all the global functions - 43196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// 'main' or functions accessible from other translation units. 44196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CallGraphNode *Root; 45196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 46196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// The list of nodes that have no parent. These are unreachable from Root. 47196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// Declarations can get to this list due to impressions in the graph, for 48196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// example, we do not track functions whose addresses were taken. 49196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks llvm::SetVector<CallGraphNode *> ParentlessNodes; 50196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 51196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakspublic: 52196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CallGraph(); 53196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks ~CallGraph(); 54196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 556a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// \brief Populate the call graph with the functions in the given 566a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// declaration. 576a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// 586a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// Recursively walks the declaration to find all the dependent Decls as well. 596a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks void addToCallGraph(Decl *D) { 606a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks TraverseDecl(D); 616a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks } 62196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 636a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// \brief Determine if a declaration should be included in the graph. 646a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks static bool includeInGraph(const Decl *D); 65196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 66a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks /// \brief Lookup the node for the given declaration. 67a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks CallGraphNode *getNode(const Decl *) const; 68a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks 69196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \brief Lookup the node for the given declaration. If none found, insert 70196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// one into the graph. 716a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks CallGraphNode *getOrInsertNode(Decl *); 72196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 73196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// Iterators through all the elements in the graph. Note, this gives 74196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// non-deterministic order. 75196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef FunctionMapTy::iterator iterator; 76196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef FunctionMapTy::const_iterator const_iterator; 77196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks iterator begin() { return FunctionMap.begin(); } 78196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks iterator end() { return FunctionMap.end(); } 79196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks const_iterator begin() const { return FunctionMap.begin(); } 80196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks const_iterator end() const { return FunctionMap.end(); } 81196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 82196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \brief Get the number of nodes in the graph. 83196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks unsigned size() const { return FunctionMap.size(); } 84196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 85196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \ brief Get the virtual root of the graph, all the functions available 86196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// externally are represented as callees of the node. 87196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CallGraphNode *getRoot() const { return Root; } 88196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 89196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// Iterators through all the nodes of the graph that have no parent. These 90196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// are the unreachable nodes, which are either unused or are due to us 91196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// failing to add a call edge due to the analysis imprecision. 92196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator; 93196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator; 94196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks nodes_iterator parentless_begin() { return ParentlessNodes.begin(); } 95196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks nodes_iterator parentless_end() { return ParentlessNodes.end(); } 96196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks const_nodes_iterator 97196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks parentless_begin() const { return ParentlessNodes.begin(); } 98196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks const_nodes_iterator 99196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks parentless_end() const { return ParentlessNodes.end(); } 100196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 101196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void print(raw_ostream &os) const; 102196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void dump() const; 103196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void viewGraph() const; 1046a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 1056a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// Part of recursive declaration visitation. 1066a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks bool VisitFunctionDecl(FunctionDecl *FD) { 1076a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // We skip function template definitions, as their semantics is 1086a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // only determined when they are instantiated. 1096a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks if (includeInGraph(FD)) 1106a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // If this function has external linkage, anything could call it. 1116a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // Note, we are not precise here. For example, the function could have 1126a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // its address taken. 1136a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks addNodeForDecl(FD, FD->isGlobal()); 1146a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks return true; 1156a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks } 1166a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 1176a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// Part of recursive declaration visitation. 1186a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 1196a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks if (includeInGraph(MD)) 1206a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks addNodeForDecl(MD, true); 1216a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks return true; 1226a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks } 1236a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 124e2c9238d7b53fdfd99e724ce50de9197a23727faAnna Zaks bool shouldWalkTypesOfTypeLocs() const { return false; } 125e2c9238d7b53fdfd99e724ce50de9197a23727faAnna Zaks 1266a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaksprivate: 1276a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// \brief Add the given declaration to the call graph. 1286a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks void addNodeForDecl(Decl *D, bool IsGlobal); 1296a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 1306a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// \brief Allocate a new node in the graph. 1316a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks CallGraphNode *allocateNewNode(Decl *); 132196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 133196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 134196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaksclass CallGraphNode { 135196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakspublic: 136196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef CallGraphNode* CallRecord; 137196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 138196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaksprivate: 139196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \brief The function/method declaration. 140196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks Decl *FD; 141196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 142196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \brief The list of functions called from this node. 143196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks // Small vector might be more efficient since we are only tracking functions 144196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks // whose definition is in the current TU. 145196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks llvm::SmallVector<CallRecord, 5> CalledFunctions; 146196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 147196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakspublic: 148196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CallGraphNode(Decl *D) : FD(D) {} 149196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 150196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef llvm::SmallVector<CallRecord, 5>::iterator iterator; 151196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef llvm::SmallVector<CallRecord, 5>::const_iterator const_iterator; 152196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 153196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// Iterators through all the callees/children of the node. 154196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline iterator begin() { return CalledFunctions.begin(); } 155196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline iterator end() { return CalledFunctions.end(); } 156196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline const_iterator begin() const { return CalledFunctions.begin(); } 157196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline const_iterator end() const { return CalledFunctions.end(); } 158196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 159196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline bool empty() const {return CalledFunctions.empty(); } 160196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline unsigned size() const {return CalledFunctions.size(); } 161196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 162196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void addCallee(CallGraphNode *N, CallGraph *CG) { 163196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CalledFunctions.push_back(N); 164196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CG->ParentlessNodes.remove(N); 165196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 166196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 167196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks Decl *getDecl() const { return FD; } 168196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 169196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks StringRef getName() const; 170196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 171196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void print(raw_ostream &os) const; 172196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void dump() const; 173196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 174196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 175196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks} // end clang namespace 176196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 177196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// Graph traits for iteration, viewing. 178196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaksnamespace llvm { 179196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakstemplate <> struct GraphTraits<clang::CallGraphNode*> { 180196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef clang::CallGraphNode NodeType; 181196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef clang::CallGraphNode::CallRecord CallRecordTy; 182196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef std::pointer_to_unary_function<CallRecordTy, 183196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks clang::CallGraphNode*> CGNDerefFun; 184196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } 185196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; 186196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static inline ChildIteratorType child_begin(NodeType *N) { 187196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); 188196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 189196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static inline ChildIteratorType child_end (NodeType *N) { 190196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(N->end(), CGNDerefFun(CGNDeref)); 191196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 192196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static clang::CallGraphNode *CGNDeref(CallRecordTy P) { 193196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return P; 194196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 195196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 196196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 197196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakstemplate <> struct GraphTraits<const clang::CallGraphNode*> { 198196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef const clang::CallGraphNode NodeType; 199196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef NodeType::const_iterator ChildIteratorType; 200196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } 201196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 202196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } 203196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 204196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 205196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakstemplate <> struct GraphTraits<clang::CallGraph*> 206196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks : public GraphTraits<clang::CallGraphNode*> { 207196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 208196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static NodeType *getEntryNode(clang::CallGraph *CGN) { 209196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return CGN->getRoot(); // Start at the external node! 210196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 211a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; 212196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; 213196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 214196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator; 215196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 216196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static nodes_iterator nodes_begin(clang::CallGraph *CG) { 217196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(CG->begin(), DerefFun(CGdereference)); 218196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 219196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static nodes_iterator nodes_end (clang::CallGraph *CG) { 220196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(CG->end(), DerefFun(CGdereference)); 221196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 222196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static clang::CallGraphNode &CGdereference(PairTy P) { 223196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return *(P.second); 224196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 225196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 226196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static unsigned size(clang::CallGraph *CG) { 227196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return CG->size(); 228196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 229196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 230196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 231196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakstemplate <> struct GraphTraits<const clang::CallGraph*> : 232196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks public GraphTraits<const clang::CallGraphNode*> { 233196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static NodeType *getEntryNode(const clang::CallGraph *CGN) { 234196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return CGN->getRoot(); 235196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 236a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; 237196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; 238196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 239196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef mapped_iterator<clang::CallGraph::const_iterator, 240196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks DerefFun> nodes_iterator; 241196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 242196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static nodes_iterator nodes_begin(const clang::CallGraph *CG) { 243196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(CG->begin(), DerefFun(CGdereference)); 244196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 245196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static nodes_iterator nodes_end(const clang::CallGraph *CG) { 246196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(CG->end(), DerefFun(CGdereference)); 247196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 248196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static clang::CallGraphNode &CGdereference(PairTy P) { 249196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return *(P.second); 250196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 251196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 252196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static unsigned size(const clang::CallGraph *CG) { 253196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return CG->size(); 254196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 255196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 256196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 257196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks} // end llvm namespace 258196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 259196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks#endif 260