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