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