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_H
18#define LLVM_CLANG_ANALYSIS_CALLGRAPH_H
19
20#include "clang/AST/DeclBase.h"
21#include "clang/AST/RecursiveASTVisitor.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/GraphTraits.h"
24#include "llvm/ADT/SetVector.h"
25
26namespace clang {
27class CallGraphNode;
28
29/// \brief The AST-based call graph.
30///
31/// The call graph extends itself with the given declarations by implementing
32/// the recursive AST visitor, which constructs the graph by visiting the given
33/// declarations.
34class CallGraph : public RecursiveASTVisitor<CallGraph> {
35  friend class CallGraphNode;
36
37  typedef llvm::DenseMap<const Decl *, std::unique_ptr<CallGraphNode>>
38      FunctionMapTy;
39
40  /// FunctionMap owns all CallGraphNodes.
41  FunctionMapTy FunctionMap;
42
43  /// This is a virtual root node that has edges to all the functions.
44  CallGraphNode *Root;
45
46public:
47  CallGraph();
48  ~CallGraph();
49
50  /// \brief Populate the call graph with the functions in the given
51  /// declaration.
52  ///
53  /// Recursively walks the declaration to find all the dependent Decls as well.
54  void addToCallGraph(Decl *D) {
55    TraverseDecl(D);
56  }
57
58  /// \brief Determine if a declaration should be included in the graph.
59  static bool includeInGraph(const Decl *D);
60
61  /// \brief Lookup the node for the given declaration.
62  CallGraphNode *getNode(const Decl *) const;
63
64  /// \brief Lookup the node for the given declaration. If none found, insert
65  /// one into the graph.
66  CallGraphNode *getOrInsertNode(Decl *);
67
68  /// Iterators through all the elements in the graph. Note, this gives
69  /// non-deterministic order.
70  typedef FunctionMapTy::iterator iterator;
71  typedef FunctionMapTy::const_iterator const_iterator;
72  iterator begin() { return FunctionMap.begin(); }
73  iterator end()   { return FunctionMap.end();   }
74  const_iterator begin() const { return FunctionMap.begin(); }
75  const_iterator end()   const { return FunctionMap.end();   }
76
77  /// \brief Get the number of nodes in the graph.
78  unsigned size() const { return FunctionMap.size(); }
79
80  /// \ brief Get the virtual root of the graph, all the functions available
81  /// externally are represented as callees of the node.
82  CallGraphNode *getRoot() const { return Root; }
83
84  /// Iterators through all the nodes of the graph that have no parent. These
85  /// are the unreachable nodes, which are either unused or are due to us
86  /// failing to add a call edge due to the analysis imprecision.
87  typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator;
88  typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator;
89
90  void print(raw_ostream &os) const;
91  void dump() const;
92  void viewGraph() const;
93
94  void addNodesForBlocks(DeclContext *D);
95
96  /// Part of recursive declaration visitation. We recursively visit all the
97  /// declarations to collect the root functions.
98  bool VisitFunctionDecl(FunctionDecl *FD) {
99    // We skip function template definitions, as their semantics is
100    // only determined when they are instantiated.
101    if (includeInGraph(FD) && FD->isThisDeclarationADefinition()) {
102      // Add all blocks declared inside this function to the graph.
103      addNodesForBlocks(FD);
104      // If this function has external linkage, anything could call it.
105      // Note, we are not precise here. For example, the function could have
106      // its address taken.
107      addNodeForDecl(FD, FD->isGlobal());
108    }
109    return true;
110  }
111
112  /// Part of recursive declaration visitation.
113  bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
114    if (includeInGraph(MD)) {
115      addNodesForBlocks(MD);
116      addNodeForDecl(MD, true);
117    }
118    return true;
119  }
120
121  // We are only collecting the declarations, so do not step into the bodies.
122  bool TraverseStmt(Stmt *S) { return true; }
123
124  bool shouldWalkTypesOfTypeLocs() const { return false; }
125
126private:
127  /// \brief Add the given declaration to the call graph.
128  void addNodeForDecl(Decl *D, bool IsGlobal);
129
130  /// \brief Allocate a new node in the graph.
131  CallGraphNode *allocateNewNode(Decl *);
132};
133
134class CallGraphNode {
135public:
136  typedef CallGraphNode* CallRecord;
137
138private:
139  /// \brief The function/method declaration.
140  Decl *FD;
141
142  /// \brief The list of functions called from this node.
143  SmallVector<CallRecord, 5> CalledFunctions;
144
145public:
146  CallGraphNode(Decl *D) : FD(D) {}
147
148  typedef SmallVectorImpl<CallRecord>::iterator iterator;
149  typedef SmallVectorImpl<CallRecord>::const_iterator const_iterator;
150
151  /// Iterators through all the callees/children of the node.
152  inline iterator begin() { return CalledFunctions.begin(); }
153  inline iterator end()   { return CalledFunctions.end(); }
154  inline const_iterator begin() const { return CalledFunctions.begin(); }
155  inline const_iterator end()   const { return CalledFunctions.end();   }
156
157  inline bool empty() const {return CalledFunctions.empty(); }
158  inline unsigned size() const {return CalledFunctions.size(); }
159
160  void addCallee(CallGraphNode *N) {
161    CalledFunctions.push_back(N);
162  }
163
164  Decl *getDecl() const { return FD; }
165
166  void print(raw_ostream &os) const;
167  void dump() const;
168};
169
170} // end clang namespace
171
172// Graph traits for iteration, viewing.
173namespace llvm {
174template <> struct GraphTraits<clang::CallGraphNode*> {
175  typedef clang::CallGraphNode NodeType;
176  typedef clang::CallGraphNode *NodeRef;
177  typedef NodeType::iterator ChildIteratorType;
178
179  static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
180  static inline ChildIteratorType child_begin(NodeType *N) {
181    return N->begin();
182  }
183  static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
184};
185
186template <> struct GraphTraits<const clang::CallGraphNode*> {
187  typedef const clang::CallGraphNode NodeType;
188  typedef const clang::CallGraphNode *NodeRef;
189  typedef NodeType::const_iterator ChildIteratorType;
190
191  static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
192  static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
193  static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
194};
195
196template <> struct GraphTraits<clang::CallGraph*>
197  : public GraphTraits<clang::CallGraphNode*> {
198
199  static NodeType *getEntryNode(clang::CallGraph *CGN) {
200    return CGN->getRoot();  // Start at the external node!
201  }
202
203  static clang::CallGraphNode *
204  CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
205    return P.second.get();
206  }
207
208  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
209  typedef mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>
210      nodes_iterator;
211
212  static nodes_iterator nodes_begin(clang::CallGraph *CG) {
213    return nodes_iterator(CG->begin(), &CGGetValue);
214  }
215  static nodes_iterator nodes_end  (clang::CallGraph *CG) {
216    return nodes_iterator(CG->end(), &CGGetValue);
217  }
218
219  static unsigned size(clang::CallGraph *CG) {
220    return CG->size();
221  }
222};
223
224template <> struct GraphTraits<const clang::CallGraph*> :
225  public GraphTraits<const clang::CallGraphNode*> {
226  static NodeType *getEntryNode(const clang::CallGraph *CGN) {
227    return CGN->getRoot();
228  }
229
230  static clang::CallGraphNode *
231  CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
232    return P.second.get();
233  }
234
235  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
236  typedef mapped_iterator<clang::CallGraph::const_iterator,
237                          decltype(&CGGetValue)>
238      nodes_iterator;
239
240  static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
241    return nodes_iterator(CG->begin(), &CGGetValue);
242  }
243  static nodes_iterator nodes_end(const clang::CallGraph *CG) {
244    return nodes_iterator(CG->end(), &CGGetValue);
245  }
246  static unsigned size(const clang::CallGraph *CG) {
247    return CG->size();
248  }
249};
250
251} // end llvm namespace
252
253#endif
254