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 42bd80231672a7418aa1a99d3dbbe1774205c88f74Anna Zaks /// This is a virtual root node that has edges to all the functions. 43196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CallGraphNode *Root; 44196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 45196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakspublic: 46196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CallGraph(); 47196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks ~CallGraph(); 48196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 496a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// \brief Populate the call graph with the functions in the given 506a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// declaration. 516a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// 526a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// Recursively walks the declaration to find all the dependent Decls as well. 536a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks void addToCallGraph(Decl *D) { 546a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks TraverseDecl(D); 556a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks } 56196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 576a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// \brief Determine if a declaration should be included in the graph. 586a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks static bool includeInGraph(const Decl *D); 59196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 60a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks /// \brief Lookup the node for the given declaration. 61a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks CallGraphNode *getNode(const Decl *) const; 62a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks 63196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \brief Lookup the node for the given declaration. If none found, insert 64196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// one into the graph. 656a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks CallGraphNode *getOrInsertNode(Decl *); 66196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 67196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// Iterators through all the elements in the graph. Note, this gives 68196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// non-deterministic order. 69196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef FunctionMapTy::iterator iterator; 70196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef FunctionMapTy::const_iterator const_iterator; 71196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks iterator begin() { return FunctionMap.begin(); } 72196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks iterator end() { return FunctionMap.end(); } 73196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks const_iterator begin() const { return FunctionMap.begin(); } 74196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks const_iterator end() const { return FunctionMap.end(); } 75196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 76196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \brief Get the number of nodes in the graph. 77196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks unsigned size() const { return FunctionMap.size(); } 78196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 79196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \ brief Get the virtual root of the graph, all the functions available 80196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// externally are represented as callees of the node. 81196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CallGraphNode *getRoot() const { return Root; } 82196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 83196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// Iterators through all the nodes of the graph that have no parent. These 84196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// are the unreachable nodes, which are either unused or are due to us 85196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// failing to add a call edge due to the analysis imprecision. 86196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator; 87196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator; 88196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 89196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void print(raw_ostream &os) const; 90196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void dump() const; 91196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void viewGraph() const; 926a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 934f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks void addNodesForBlocks(DeclContext *D); 944f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks 9524388333364be0ce9d04a07fa9895baeeff78bdaAnna Zaks /// Part of recursive declaration visitation. We recursively visit all the 964f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks /// declarations to collect the root functions. 976a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks bool VisitFunctionDecl(FunctionDecl *FD) { 986a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // We skip function template definitions, as their semantics is 996a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // only determined when they are instantiated. 1004f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks if (includeInGraph(FD)) { 1014f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks // Add all blocks declared inside this function to the graph. 1024f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks addNodesForBlocks(FD); 1036a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // If this function has external linkage, anything could call it. 1046a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // Note, we are not precise here. For example, the function could have 1056a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks // its address taken. 1066a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks addNodeForDecl(FD, FD->isGlobal()); 1074f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks } 1086a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks return true; 1096a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks } 1106a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 1116a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// Part of recursive declaration visitation. 1126a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks bool VisitObjCMethodDecl(ObjCMethodDecl *MD) { 1134f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks if (includeInGraph(MD)) { 1144f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks addNodesForBlocks(MD); 1156a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks addNodeForDecl(MD, true); 1164f858dfd42c89b67200dac0afc228a0baa323691Anna Zaks } 1176a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks return true; 1186a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks } 1196a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 12024388333364be0ce9d04a07fa9895baeeff78bdaAnna Zaks // We are only collecting the declarations, so do not step into the bodies. 12124388333364be0ce9d04a07fa9895baeeff78bdaAnna Zaks bool TraverseStmt(Stmt *S) { return true; } 12224388333364be0ce9d04a07fa9895baeeff78bdaAnna Zaks 123e2c9238d7b53fdfd99e724ce50de9197a23727faAnna Zaks bool shouldWalkTypesOfTypeLocs() const { return false; } 124e2c9238d7b53fdfd99e724ce50de9197a23727faAnna Zaks 1256a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaksprivate: 1266a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// \brief Add the given declaration to the call graph. 1276a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks void addNodeForDecl(Decl *D, bool IsGlobal); 1286a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks 1296a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks /// \brief Allocate a new node in the graph. 1306a86082f3a06a2dcceaaf63f78a0e52d64bcbaa3Anna Zaks CallGraphNode *allocateNewNode(Decl *); 131196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 132196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 133196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaksclass CallGraphNode { 134196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakspublic: 135196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef CallGraphNode* CallRecord; 136196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 137196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaksprivate: 138196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \brief The function/method declaration. 139196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks Decl *FD; 140196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 141196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// \brief The list of functions called from this node. 142cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko SmallVector<CallRecord, 5> CalledFunctions; 143196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 144196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakspublic: 145196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CallGraphNode(Decl *D) : FD(D) {} 146196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 14709d19efaa147762f84aed55efa7930bb3616a4e5Craig Topper typedef SmallVectorImpl<CallRecord>::iterator iterator; 14809d19efaa147762f84aed55efa7930bb3616a4e5Craig Topper typedef SmallVectorImpl<CallRecord>::const_iterator const_iterator; 149196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 150196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks /// Iterators through all the callees/children of the node. 151196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline iterator begin() { return CalledFunctions.begin(); } 152196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline iterator end() { return CalledFunctions.end(); } 153196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline const_iterator begin() const { return CalledFunctions.begin(); } 154196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline const_iterator end() const { return CalledFunctions.end(); } 155196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 156196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline bool empty() const {return CalledFunctions.empty(); } 157196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks inline unsigned size() const {return CalledFunctions.size(); } 158196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 159196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void addCallee(CallGraphNode *N, CallGraph *CG) { 160196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks CalledFunctions.push_back(N); 161196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 162196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 163196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks Decl *getDecl() const { return FD; } 164196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 165196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void print(raw_ostream &os) const; 166196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks void dump() const; 167196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 168196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 169196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks} // end clang namespace 170196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 171196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks// Graph traits for iteration, viewing. 172196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaksnamespace llvm { 173196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakstemplate <> struct GraphTraits<clang::CallGraphNode*> { 174196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef clang::CallGraphNode NodeType; 175196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef clang::CallGraphNode::CallRecord CallRecordTy; 176196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef std::pointer_to_unary_function<CallRecordTy, 177196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks clang::CallGraphNode*> CGNDerefFun; 178196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } 179196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; 180196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static inline ChildIteratorType child_begin(NodeType *N) { 181196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); 182196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 183196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static inline ChildIteratorType child_end (NodeType *N) { 184196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(N->end(), CGNDerefFun(CGNDeref)); 185196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 186196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static clang::CallGraphNode *CGNDeref(CallRecordTy P) { 187196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return P; 188196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 189196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 190196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 191196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakstemplate <> struct GraphTraits<const clang::CallGraphNode*> { 192196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef const clang::CallGraphNode NodeType; 193196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef NodeType::const_iterator ChildIteratorType; 194196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } 195196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} 196bd80231672a7418aa1a99d3dbbe1774205c88f74Anna Zaks static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } 197196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 198196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 199196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakstemplate <> struct GraphTraits<clang::CallGraph*> 200196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks : public GraphTraits<clang::CallGraphNode*> { 201196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 202196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static NodeType *getEntryNode(clang::CallGraph *CGN) { 203196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return CGN->getRoot(); // Start at the external node! 204196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 205a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; 206196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; 207196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 208196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator; 209196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 210196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static nodes_iterator nodes_begin(clang::CallGraph *CG) { 211196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(CG->begin(), DerefFun(CGdereference)); 212196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 213196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static nodes_iterator nodes_end (clang::CallGraph *CG) { 214196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(CG->end(), DerefFun(CGdereference)); 215196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 216196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static clang::CallGraphNode &CGdereference(PairTy P) { 217196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return *(P.second); 218196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 219196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 220196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static unsigned size(clang::CallGraph *CG) { 221196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return CG->size(); 222196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 223196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 224196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 225196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zakstemplate <> struct GraphTraits<const clang::CallGraph*> : 226196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks public GraphTraits<const clang::CallGraphNode*> { 227196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static NodeType *getEntryNode(const clang::CallGraph *CGN) { 228196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return CGN->getRoot(); 229196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 230a5d531f67de0cfeb56b843da15146f3b4cd75bd9Anna Zaks typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy; 231196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; 232196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 233196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks typedef mapped_iterator<clang::CallGraph::const_iterator, 234196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks DerefFun> nodes_iterator; 235196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 236196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static nodes_iterator nodes_begin(const clang::CallGraph *CG) { 237196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(CG->begin(), DerefFun(CGdereference)); 238196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 239196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static nodes_iterator nodes_end(const clang::CallGraph *CG) { 240196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return map_iterator(CG->end(), DerefFun(CGdereference)); 241196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 242196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static clang::CallGraphNode &CGdereference(PairTy P) { 243196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return *(P.second); 244196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 245196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 246196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks static unsigned size(const clang::CallGraph *CG) { 247196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks return CG->size(); 248196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks } 249196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks}; 250196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 251196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks} // end llvm namespace 252196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks 253196b8cfe9cfcc452eb2f83aa4ad330c2324f8c7dAnna Zaks#endif 254