CallGraph.h revision a5d531f67de0cfeb56b843da15146f3b4cd75bd9 
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 "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/GraphTraits.h"
23#include "llvm/ADT/SetVector.h"
24
25namespace clang {
26class CallGraphNode;
27
28class CallGraph {
29  friend class CallGraphNode;
30  typedef llvm::DenseMap<const Decl *, CallGraphNode *> FunctionMapTy;
31
32  /// FunctionMap owns all CallGraphNodes.
33  FunctionMapTy FunctionMap;
34
35  /// This is a virtual root node that has edges to all the global functions -
36  /// 'main' or functions accessible from other translation units.
37  CallGraphNode *Root;
38
39  /// The list of nodes that have no parent. These are unreachable from Root.
40  /// Declarations can get to this list due to impressions in the graph, for
41  /// example, we do not track functions whose addresses were taken.
42  llvm::SetVector<CallGraphNode *> ParentlessNodes;
43
44public:
45  CallGraph();
46  ~CallGraph();
47
48  /// \brief Add the given declaration to the call graph.
49  void addToCallGraph(Decl *D, bool IsGlobal);
50
51  /// \brief Populate the call graph with the functions in the given DeclContext.
52  void addToCallGraph(DeclContext *DC);
53
54  /// \brief Lookup the node for the given declaration.
55  CallGraphNode *getNode(const Decl *) const;
56
57  /// \brief Lookup the node for the given declaration. If none found, insert
58  /// one into the graph.
59  CallGraphNode *getOrInsertFunction(Decl *);
60
61  /// Iterators through all the elements in the graph. Note, this gives
62  /// non-deterministic order.
63  typedef FunctionMapTy::iterator iterator;
64  typedef FunctionMapTy::const_iterator const_iterator;
65  iterator begin() { return FunctionMap.begin(); }
66  iterator end()   { return FunctionMap.end();   }
67  const_iterator begin() const { return FunctionMap.begin(); }
68  const_iterator end()   const { return FunctionMap.end();   }
69
70  /// \brief Get the number of nodes in the graph.
71  unsigned size() const { return FunctionMap.size(); }
72
73  /// \ brief Get the virtual root of the graph, all the functions available
74  /// externally are represented as callees of the node.
75  CallGraphNode *getRoot() const { return Root; }
76
77  /// Iterators through all the nodes of the graph that have no parent. These
78  /// are the unreachable nodes, which are either unused or are due to us
79  /// failing to add a call edge due to the analysis imprecision.
80  typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator;
81  typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator;
82  nodes_iterator parentless_begin() { return ParentlessNodes.begin(); }
83  nodes_iterator parentless_end() { return ParentlessNodes.end(); }
84  const_nodes_iterator
85    parentless_begin() const { return ParentlessNodes.begin(); }
86  const_nodes_iterator
87    parentless_end() const { return ParentlessNodes.end(); }
88
89  void print(raw_ostream &os) const;
90  void dump() const;
91  void viewGraph() const;
92};
93
94class CallGraphNode {
95public:
96  typedef CallGraphNode* CallRecord;
97
98private:
99  /// \brief The function/method declaration.
100  Decl *FD;
101
102  /// \brief The list of functions called from this node.
103  // Small vector might be more efficient since we are only tracking functions
104  // whose definition is in the current TU.
105  llvm::SmallVector<CallRecord, 5> CalledFunctions;
106
107public:
108  CallGraphNode(Decl *D) : FD(D) {}
109
110  typedef llvm::SmallVector<CallRecord, 5>::iterator iterator;
111  typedef llvm::SmallVector<CallRecord, 5>::const_iterator const_iterator;
112
113  /// Iterators through all the callees/children of the node.
114  inline iterator begin() { return CalledFunctions.begin(); }
115  inline iterator end()   { return CalledFunctions.end(); }
116  inline const_iterator begin() const { return CalledFunctions.begin(); }
117  inline const_iterator end()   const { return CalledFunctions.end();   }
118
119  inline bool empty() const {return CalledFunctions.empty(); }
120  inline unsigned size() const {return CalledFunctions.size(); }
121
122  void addCallee(CallGraphNode *N, CallGraph *CG) {
123    CalledFunctions.push_back(N);
124    CG->ParentlessNodes.remove(N);
125  }
126
127  Decl *getDecl() const { return FD; }
128
129  StringRef getName() const;
130
131  void print(raw_ostream &os) const;
132  void dump() const;
133};
134
135} // end clang namespace
136
137// Graph traits for iteration, viewing.
138namespace llvm {
139template <> struct GraphTraits<clang::CallGraphNode*> {
140  typedef clang::CallGraphNode NodeType;
141  typedef clang::CallGraphNode::CallRecord CallRecordTy;
142  typedef std::pointer_to_unary_function<CallRecordTy,
143                                         clang::CallGraphNode*> CGNDerefFun;
144  static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
145  typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
146  static inline ChildIteratorType child_begin(NodeType *N) {
147    return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
148  }
149  static inline ChildIteratorType child_end  (NodeType *N) {
150    return map_iterator(N->end(), CGNDerefFun(CGNDeref));
151  }
152  static clang::CallGraphNode *CGNDeref(CallRecordTy P) {
153    return P;
154  }
155};
156
157template <> struct GraphTraits<const clang::CallGraphNode*> {
158  typedef const clang::CallGraphNode NodeType;
159  typedef NodeType::const_iterator ChildIteratorType;
160  static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
161  static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
162  static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
163};
164
165template <> struct GraphTraits<clang::CallGraph*>
166  : public GraphTraits<clang::CallGraphNode*> {
167
168  static NodeType *getEntryNode(clang::CallGraph *CGN) {
169    return CGN->getRoot();  // Start at the external node!
170  }
171  typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
172  typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
173  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
174  typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator;
175
176  static nodes_iterator nodes_begin(clang::CallGraph *CG) {
177    return map_iterator(CG->begin(), DerefFun(CGdereference));
178  }
179  static nodes_iterator nodes_end  (clang::CallGraph *CG) {
180    return map_iterator(CG->end(), DerefFun(CGdereference));
181  }
182  static clang::CallGraphNode &CGdereference(PairTy P) {
183    return *(P.second);
184  }
185
186  static unsigned size(clang::CallGraph *CG) {
187    return CG->size();
188  }
189};
190
191template <> struct GraphTraits<const clang::CallGraph*> :
192  public GraphTraits<const clang::CallGraphNode*> {
193  static NodeType *getEntryNode(const clang::CallGraph *CGN) {
194    return CGN->getRoot();
195  }
196  typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
197  typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
198  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
199  typedef mapped_iterator<clang::CallGraph::const_iterator,
200                          DerefFun> nodes_iterator;
201
202  static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
203    return map_iterator(CG->begin(), DerefFun(CGdereference));
204  }
205  static nodes_iterator nodes_end(const clang::CallGraph *CG) {
206    return map_iterator(CG->end(), DerefFun(CGdereference));
207  }
208  static clang::CallGraphNode &CGdereference(PairTy P) {
209    return *(P.second);
210  }
211
212  static unsigned size(const clang::CallGraph *CG) {
213    return CG->size();
214  }
215};
216
217} // end llvm namespace
218
219#endif
220