clang  6.0.0svn
CallGraph.h
Go to the documentation of this file.
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"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/GraphTraits.h"
24 #include "llvm/ADT/SetVector.h"
25 
26 namespace clang {
27 class 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.
34 class 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 
46 public:
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.
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 
95 
96  /// Part of recursive declaration visitation. We recursively visit all the
97  /// declarations to collect the root functions.
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.
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 
126 private:
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 
135 public:
137 
138 private:
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 
145 public:
146  CallGraphNode(Decl *D) : FD(D) {}
147 
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 
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.
173 namespace llvm {
174 template <> struct GraphTraits<clang::CallGraphNode*> {
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 
186 template <> struct GraphTraits<const clang::CallGraphNode*> {
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 
196 template <> 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)>
211 
213  return nodes_iterator(CG->begin(), &CGGetValue);
214  }
216  return nodes_iterator(CG->end(), &CGGetValue);
217  }
218 
219  static unsigned size(clang::CallGraph *CG) {
220  return CG->size();
221  }
222 };
223 
224 template <> 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)>
239 
241  return nodes_iterator(CG->begin(), &CGGetValue);
242  }
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
The AST-based call graph.
Definition: CallGraph.h:34
FunctionDecl - An instance of this class is created to represent a function declaration or definition...
Definition: Decl.h:1631
void dump() const
Definition: CallGraph.cpp:190
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:26
Stmt - This represents one statement.
Definition: Stmt.h:60
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:81
StringRef P
const_iterator begin() const
Definition: CallGraph.h:74
ObjCMethodDecl - Represents an instance or class method declaration.
Definition: DeclObjC.h:113
CallGraphNode * getOrInsertNode(Decl *)
Lookup the node for the given declaration.
Definition: CallGraph.cpp:147
static ChildIteratorType child_end(NodeType *N)
Definition: CallGraph.h:193
void addCallee(CallGraphNode *N)
Definition: CallGraph.h:160
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument&#39;s dynamic ty...
static unsigned size(const clang::CallGraph *CG)
Definition: CallGraph.h:246
static NodeType * getEntryNode(const clang::CallGraph *CGN)
Definition: CallGraph.h:226
bool shouldWalkTypesOfTypeLocs() const
Definition: CallGraph.h:124
static nodes_iterator nodes_begin(clang::CallGraph *CG)
Definition: CallGraph.h:212
const_iterator begin() const
Definition: CallGraph.h:154
llvm::SetVector< CallGraphNode * >::iterator nodes_iterator
Iterators through all the nodes of the graph that have no parent.
Definition: CallGraph.h:87
void addNodesForBlocks(DeclContext *D)
Definition: CallGraph.cpp:95
CallGraphNode * CallRecord
Definition: CallGraph.h:136
mapped_iterator< clang::CallGraph::const_iterator, decltype(&CGGetValue)> nodes_iterator
Definition: CallGraph.h:238
static NodeType * getEntryNode(const clang::CallGraphNode *CGN)
Definition: CallGraph.h:191
static nodes_iterator nodes_begin(const clang::CallGraph *CG)
Definition: CallGraph.h:240
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
Decl * getDecl() const
Definition: CallGraph.h:164
CallGraphNode(Decl *D)
Definition: CallGraph.h:146
friend class CallGraphNode
Definition: CallGraph.h:35
SmallVectorImpl< CallRecord >::const_iterator const_iterator
Definition: CallGraph.h:149
mapped_iterator< clang::CallGraph::iterator, decltype(&CGGetValue)> nodes_iterator
Definition: CallGraph.h:210
bool isThisDeclarationADefinition() const
Returns whether this specific declaration of the function is also a definition that does not contain ...
Definition: Decl.h:1887
static clang::CallGraphNode * CGGetValue(clang::CallGraph::const_iterator::value_type &P)
Definition: CallGraph.h:231
static ChildIteratorType child_end(NodeType *N)
Definition: CallGraph.h:183
void print(raw_ostream &os) const
Definition: CallGraph.cpp:162
static ChildIteratorType child_begin(NodeType *N)
Definition: CallGraph.h:192
bool VisitFunctionDecl(FunctionDecl *FD)
Part of recursive declaration visitation.
Definition: CallGraph.h:98
unsigned size() const
Definition: CallGraph.h:158
static nodes_iterator nodes_end(clang::CallGraph *CG)
Definition: CallGraph.h:215
FunctionMapTy::iterator iterator
Iterators through all the elements in the graph.
Definition: CallGraph.h:70
bool TraverseStmt(Stmt *S)
Definition: CallGraph.h:122
static ChildIteratorType child_begin(NodeType *N)
Definition: CallGraph.h:180
static bool includeInGraph(const Decl *D)
Determine if a declaration should be included in the graph.
Definition: CallGraph.cpp:110
const_iterator end() const
Definition: CallGraph.h:75
static nodes_iterator nodes_end(const clang::CallGraph *CG)
Definition: CallGraph.h:243
void viewGraph() const
Definition: CallGraph.cpp:194
llvm::SetVector< CallGraphNode * >::const_iterator const_nodes_iterator
Definition: CallGraph.h:88
Dataflow Directional Tag Classes.
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1224
static NodeType * getEntryNode(clang::CallGraphNode *CGN)
Definition: CallGraph.h:179
CallGraphNode * getNode(const Decl *) const
Lookup the node for the given declaration.
Definition: CallGraph.cpp:141
CallGraphNode * getRoot() const
\ brief Get the virtual root of the graph, all the functions available externally are represented as ...
Definition: CallGraph.h:82
static NodeType * getEntryNode(clang::CallGraph *CGN)
Definition: CallGraph.h:199
iterator begin()
Iterators through all the callees/children of the node.
Definition: CallGraph.h:152
static clang::CallGraphNode * CGGetValue(clang::CallGraph::const_iterator::value_type &P)
Definition: CallGraph.h:204
static unsigned size(clang::CallGraph *CG)
Definition: CallGraph.h:219
const_iterator end() const
Definition: CallGraph.h:155
SmallVectorImpl< CallRecord >::iterator iterator
Definition: CallGraph.h:148
void addToCallGraph(Decl *D)
Populate the call graph with the functions in the given declaration.
Definition: CallGraph.h:54
iterator end()
Definition: CallGraph.h:73
unsigned size() const
Get the number of nodes in the graph.
Definition: CallGraph.h:78
bool empty() const
Definition: CallGraph.h:157
bool VisitObjCMethodDecl(ObjCMethodDecl *MD)
Part of recursive declaration visitation.
Definition: CallGraph.h:113
FunctionMapTy::const_iterator const_iterator
Definition: CallGraph.h:71
iterator begin()
Definition: CallGraph.h:72
bool isGlobal() const
Determines whether this is a global function.
Definition: Decl.cpp:2765