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