clang  14.0.0git
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 "llvm/ADT/iterator_range.h"
28 #include <memory>
29 
30 namespace clang {
31 
32 class CallGraphNode;
33 class Decl;
34 class DeclContext;
35 class Stmt;
36 
37 /// 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  /// 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  /// Determine if a declaration should be included in the graph.
67  static bool includeInGraph(const Decl *D);
68 
69  /// Determine if a declaration should be included in the graph for the
70  /// purposes of being a callee. This is similar to includeInGraph except
71  /// it permits declarations, not just definitions.
72  static bool includeCalleeInGraph(const Decl *D);
73 
74  /// Lookup the node for the given declaration.
75  CallGraphNode *getNode(const Decl *) const;
76 
77  /// Lookup the node for the given declaration. If none found, insert
78  /// one into the graph.
80 
81  using iterator = FunctionMapTy::iterator;
82  using const_iterator = FunctionMapTy::const_iterator;
83 
84  /// Iterators through all the elements in the graph. Note, this gives
85  /// non-deterministic order.
86  iterator begin() { return FunctionMap.begin(); }
87  iterator end() { return FunctionMap.end(); }
88  const_iterator begin() const { return FunctionMap.begin(); }
89  const_iterator end() const { return FunctionMap.end(); }
90 
91  /// Get the number of nodes in the graph.
92  unsigned size() const { return FunctionMap.size(); }
93 
94  /// Get the virtual root of the graph, all the functions available externally
95  /// are represented as callees of the node.
96  CallGraphNode *getRoot() const { return Root; }
97 
98  /// Iterators through all the nodes of the graph that have no parent. These
99  /// are the unreachable nodes, which are either unused or are due to us
100  /// failing to add a call edge due to the analysis imprecision.
101  using nodes_iterator = llvm::SetVector<CallGraphNode *>::iterator;
102  using const_nodes_iterator = llvm::SetVector<CallGraphNode *>::const_iterator;
103 
104  void print(raw_ostream &os) const;
105  void dump() const;
106  void viewGraph() const;
107 
109 
110  /// Part of recursive declaration visitation. We recursively visit all the
111  /// declarations to collect the root functions.
113  // We skip function template definitions, as their semantics is
114  // only determined when they are instantiated.
115  if (includeInGraph(FD) && FD->isThisDeclarationADefinition()) {
116  // Add all blocks declared inside this function to the graph.
117  addNodesForBlocks(FD);
118  // If this function has external linkage, anything could call it.
119  // Note, we are not precise here. For example, the function could have
120  // its address taken.
121  addNodeForDecl(FD, FD->isGlobal());
122  }
123  return true;
124  }
125 
126  /// Part of recursive declaration visitation.
128  if (includeInGraph(MD)) {
129  addNodesForBlocks(MD);
130  addNodeForDecl(MD, true);
131  }
132  return true;
133  }
134 
135  // We are only collecting the declarations, so do not step into the bodies.
136  bool TraverseStmt(Stmt *S) { return true; }
137 
138  bool shouldWalkTypesOfTypeLocs() const { return false; }
139  bool shouldVisitTemplateInstantiations() const { return true; }
140  bool shouldVisitImplicitCode() const { return true; }
141 
142 private:
143  /// Add the given declaration to the call graph.
144  void addNodeForDecl(Decl *D, bool IsGlobal);
145 };
146 
148 public:
149  struct CallRecord {
152 
153  CallRecord() = default;
154 
155  CallRecord(CallGraphNode *Callee_, Expr *CallExpr_)
156  : Callee(Callee_), CallExpr(CallExpr_) {}
157 
158  // The call destination is the only important data here,
159  // allow to transparently unwrap into it.
160  operator CallGraphNode *() const { return Callee; }
161  };
162 
163 private:
164  /// The function/method declaration.
165  Decl *FD;
166 
167  /// The list of functions called from this node.
168  SmallVector<CallRecord, 5> CalledFunctions;
169 
170 public:
171  CallGraphNode(Decl *D) : FD(D) {}
172 
175 
176  /// Iterators through all the callees/children of the node.
177  iterator begin() { return CalledFunctions.begin(); }
178  iterator end() { return CalledFunctions.end(); }
179  const_iterator begin() const { return CalledFunctions.begin(); }
180  const_iterator end() const { return CalledFunctions.end(); }
181 
182  /// Iterator access to callees/children of the node.
183  llvm::iterator_range<iterator> callees() {
184  return llvm::make_range(begin(), end());
185  }
186  llvm::iterator_range<const_iterator> callees() const {
187  return llvm::make_range(begin(), end());
188  }
189 
190  bool empty() const { return CalledFunctions.empty(); }
191  unsigned size() const { return CalledFunctions.size(); }
192 
193  void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); }
194 
195  Decl *getDecl() const { return FD; }
196 
198  return getDecl()->getAsFunction()->getDefinition();
199  }
200 
201  void print(raw_ostream &os) const;
202  void dump() const;
203 };
204 
205 // NOTE: we are comparing based on the callee only. So different call records
206 // (with different call expressions) to the same callee will compare equal!
207 inline bool operator==(const CallGraphNode::CallRecord &LHS,
208  const CallGraphNode::CallRecord &RHS) {
209  return LHS.Callee == RHS.Callee;
210 }
211 
212 } // namespace clang
213 
214 namespace llvm {
215 
216 // Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
217 template <> struct DenseMapInfo<clang::CallGraphNode::CallRecord> {
222  }
223 
228  }
229 
230  static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) {
231  // NOTE: we are comparing based on the callee only.
232  // Different call records with the same callee will compare equal!
234  }
235 
238  return LHS == RHS;
239  }
240 };
241 
242 // Graph traits for iteration, viewing.
243 template <> struct GraphTraits<clang::CallGraphNode*> {
247 
248  static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
249  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
250  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
251 };
252 
253 template <> struct GraphTraits<const clang::CallGraphNode*> {
255  using NodeRef = const clang::CallGraphNode *;
257 
258  static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
259  static ChildIteratorType child_begin(NodeType *N) { return N->begin();}
260  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
261 };
262 
263 template <> struct GraphTraits<clang::CallGraph*>
264  : public GraphTraits<clang::CallGraphNode*> {
266  return CGN->getRoot(); // Start at the external node!
267  }
268 
269  static clang::CallGraphNode *
270  CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
271  return P.second.get();
272  }
273 
274  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
275  using nodes_iterator =
276  mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>;
277 
279  return nodes_iterator(CG->begin(), &CGGetValue);
280  }
281 
283  return nodes_iterator(CG->end(), &CGGetValue);
284  }
285 
286  static unsigned size(clang::CallGraph *CG) { return CG->size(); }
287 };
288 
289 template <> struct GraphTraits<const clang::CallGraph*> :
290  public GraphTraits<const clang::CallGraphNode*> {
291  static NodeType *getEntryNode(const clang::CallGraph *CGN) {
292  return CGN->getRoot();
293  }
294 
295  static clang::CallGraphNode *
296  CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
297  return P.second.get();
298  }
299 
300  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
301  using nodes_iterator =
302  mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>;
303 
305  return nodes_iterator(CG->begin(), &CGGetValue);
306  }
307 
309  return nodes_iterator(CG->end(), &CGGetValue);
310  }
311 
312  static unsigned size(const clang::CallGraph *CG) { return CG->size(); }
313 };
314 
315 } // namespace llvm
316 
317 #endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H
llvm::DenseMapInfo< clang::CallGraphNode::CallRecord >::getHashValue
static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val)
Definition: CallGraph.h:230
clang::CallGraph::~CallGraph
~CallGraph()
llvm
Definition: Dominators.h:30
llvm::GraphTraits< const clang::CallGraph * >::CGGetValue
static clang::CallGraphNode * CGGetValue(clang::CallGraph::const_iterator::value_type &P)
Definition: CallGraph.h:296
clang::CallGraph::dump
void dump() const
Definition: CallGraph.cpp:246
clang::CallGraphNode::const_iterator
SmallVectorImpl< CallRecord >::const_iterator const_iterator
Definition: CallGraph.h:174
clang::DeclContext
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1347
clang::Decl::getAsFunction
FunctionDecl * getAsFunction() LLVM_READONLY
Returns the function itself, or the templated function if this is a function template.
Definition: DeclBase.cpp:218
clang::CallGraphNode::CallRecord::CallRecord
CallRecord()=default
llvm::SmallVector
Definition: LLVM.h:38
clang::CallGraphNode::CallRecord::Callee
CallGraphNode * Callee
Definition: CallGraph.h:150
clang::CallGraph::const_nodes_iterator
llvm::SetVector< CallGraphNode * >::const_iterator const_nodes_iterator
Definition: CallGraph.h:102
clang::CallGraph::getRoot
CallGraphNode * getRoot() const
Get the virtual root of the graph, all the functions available externally are represented as callees ...
Definition: CallGraph.h:96
clang::CallGraphNode::begin
const_iterator begin() const
Definition: CallGraph.h:179
clang::CallGraph::const_iterator
FunctionMapTy::const_iterator const_iterator
Definition: CallGraph.h:82
llvm::GraphTraits< const clang::CallGraphNode * >::child_end
static ChildIteratorType child_end(NodeType *N)
Definition: CallGraph.h:260
llvm::DenseMapInfo< clang::CallGraphNode::CallRecord >::getEmptyKey
static clang::CallGraphNode::CallRecord getEmptyKey()
Definition: CallGraph.h:218
clang::CallGraph::shouldWalkTypesOfTypeLocs
bool shouldWalkTypesOfTypeLocs() const
Definition: CallGraph.h:138
llvm::GraphTraits< clang::CallGraphNode * >::getEntryNode
static NodeType * getEntryNode(clang::CallGraphNode *CGN)
Definition: CallGraph.h:248
clang::CallGraphNode::addCallee
void addCallee(CallRecord Call)
Definition: CallGraph.h:193
clang::CallGraph::shouldVisitImplicitCode
bool shouldVisitImplicitCode() const
Definition: CallGraph.h:140
Decl.h
clang::FunctionDecl::getDefinition
FunctionDecl * getDefinition()
Get the definition for this declaration.
Definition: Decl.h:2119
clang::CodeGen::AlignmentSource::Decl
@ Decl
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
llvm::DenseMapInfo
Definition: TypeOrdering.h:37
clang::CallGraph::size
unsigned size() const
Get the number of nodes in the graph.
Definition: CallGraph.h:92
clang::CallGraph::nodes_iterator
llvm::SetVector< CallGraphNode * >::iterator nodes_iterator
Iterators through all the nodes of the graph that have no parent.
Definition: CallGraph.h:101
clang::CallGraph::begin
iterator begin()
Iterators through all the elements in the graph.
Definition: CallGraph.h:86
llvm::GraphTraits< const clang::CallGraph * >::nodes_end
static nodes_iterator nodes_end(const clang::CallGraph *CG)
Definition: CallGraph.h:308
llvm::GraphTraits< clang::CallGraph * >::size
static unsigned size(clang::CallGraph *CG)
Definition: CallGraph.h:286
clang::CallGraphNode
Definition: CallGraph.h:147
clang::CallGraphNode::getDefinition
FunctionDecl * getDefinition() const
Definition: CallGraph.h:197
clang::CallGraphNode::end
iterator end()
Definition: CallGraph.h:178
clang::FunctionDecl::isThisDeclarationADefinition
bool isThisDeclarationADefinition() const
Returns whether this specific declaration of the function is also a definition that does not contain ...
Definition: Decl.h:2151
clang::CallGraphNode::CallGraphNode
CallGraphNode(Decl *D)
Definition: CallGraph.h:171
clang::RecursiveASTVisitor
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
Definition: RecursiveASTVisitor.h:164
clang::CallGraphNode::callees
llvm::iterator_range< const_iterator > callees() const
Definition: CallGraph.h:186
llvm::GraphTraits< clang::CallGraph * >::getEntryNode
static NodeType * getEntryNode(clang::CallGraph *CGN)
Definition: CallGraph.h:265
llvm::GraphTraits< const clang::CallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeType *N)
Definition: CallGraph.h:259
llvm::GraphTraits< clang::CallGraph * >::nodes_end
static nodes_iterator nodes_end(clang::CallGraph *CG)
Definition: CallGraph.h:282
clang::CallGraphNode::CallRecord::CallExpr
Expr * CallExpr
Definition: CallGraph.h:151
clang::CallGraph::includeCalleeInGraph
static bool includeCalleeInGraph(const Decl *D)
Determine if a declaration should be included in the graph for the purposes of being a callee.
Definition: CallGraph.cpp:163
llvm::GraphTraits< const clang::CallGraphNode * >::getEntryNode
static NodeType * getEntryNode(const clang::CallGraphNode *CGN)
Definition: CallGraph.h:258
clang::CallGraph::print
void print(raw_ostream &os) const
Definition: CallGraph.cpp:218
clang::CallGraph::shouldVisitTemplateInstantiations
bool shouldVisitTemplateInstantiations() const
Definition: CallGraph.h:139
clang::CallGraph::end
iterator end()
Definition: CallGraph.h:87
clang::FunctionDecl::isGlobal
bool isGlobal() const
Determines whether this is a global function.
Definition: Decl.cpp:3214
llvm::GraphTraits< clang::CallGraph * >::nodes_iterator
mapped_iterator< clang::CallGraph::iterator, decltype(&CGGetValue)> nodes_iterator
Definition: CallGraph.h:276
clang::CallGraphNode::begin
iterator begin()
Iterators through all the callees/children of the node.
Definition: CallGraph.h:177
clang::CallGraphNode::iterator
SmallVectorImpl< CallRecord >::iterator iterator
Definition: CallGraph.h:173
llvm::GraphTraits< const clang::CallGraph * >::getEntryNode
static NodeType * getEntryNode(const clang::CallGraph *CGN)
Definition: CallGraph.h:291
clang::CallGraphNode::getDecl
Decl * getDecl() const
Definition: CallGraph.h:195
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
GraphTraits
clang::CallGraph::VisitObjCMethodDecl
bool VisitObjCMethodDecl(ObjCMethodDecl *MD)
Part of recursive declaration visitation.
Definition: CallGraph.h:127
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
clang::CallGraphNode::size
unsigned size() const
Definition: CallGraph.h:191
llvm::GraphTraits< const clang::CallGraph * >::nodes_iterator
mapped_iterator< clang::CallGraph::const_iterator, decltype(&CGGetValue)> nodes_iterator
Definition: CallGraph.h:302
clang::CallGraph::end
const_iterator end() const
Definition: CallGraph.h:89
clang::CallGraph::begin
const_iterator begin() const
Definition: CallGraph.h:88
clang::CallGraphNode::CallRecord::CallRecord
CallRecord(CallGraphNode *Callee_, Expr *CallExpr_)
Definition: CallGraph.h:155
clang::CallGraph::TraverseStmt
bool TraverseStmt(Stmt *S)
Definition: CallGraph.h:136
clang::CallGraph::includeInGraph
static bool includeInGraph(const Decl *D)
Determine if a declaration should be included in the graph.
Definition: CallGraph.cpp:155
llvm::GraphTraits< clang::CallGraphNode * >::child_begin
static ChildIteratorType child_begin(NodeType *N)
Definition: CallGraph.h:249
clang::ObjCMethodDecl
ObjCMethodDecl - Represents an instance or class method declaration.
Definition: DeclObjC.h:139
clang::CallGraph::iterator
FunctionMapTy::iterator iterator
Definition: CallGraph.h:81
clang::CallGraph::addToCallGraph
void addToCallGraph(Decl *D)
Populate the call graph with the functions in the given declaration.
Definition: CallGraph.h:62
llvm::GraphTraits< const clang::CallGraphNode * >::ChildIteratorType
NodeType::const_iterator ChildIteratorType
Definition: CallGraph.h:256
clang::CallGraph::VisitFunctionDecl
bool VisitFunctionDecl(FunctionDecl *FD)
Part of recursive declaration visitation.
Definition: CallGraph.h:112
llvm::GraphTraits< const clang::CallGraph * >::size
static unsigned size(const clang::CallGraph *CG)
Definition: CallGraph.h:312
clang
Definition: CalledOnceCheck.h:17
RecursiveASTVisitor.h
clang::CallGraph::addNodesForBlocks
void addNodesForBlocks(DeclContext *D)
Definition: CallGraph.cpp:140
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:68
clang::CallGraph::getOrInsertNode
CallGraphNode * getOrInsertNode(Decl *)
Lookup the node for the given declaration.
Definition: CallGraph.cpp:203
llvm::GraphTraits< clang::CallGraph * >::nodes_begin
static nodes_iterator nodes_begin(clang::CallGraph *CG)
Definition: CallGraph.h:278
clang::RecursiveASTVisitor< CallGraph >::TraverseDecl
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
Definition: RecursiveASTVisitor.h:655
llvm::DenseMapInfo< clang::CallGraphNode::CallRecord >::getTombstoneKey
static clang::CallGraphNode::CallRecord getTombstoneKey()
Definition: CallGraph.h:224
clang::CallGraphNode::print
void print(raw_ostream &os) const
Definition: CallGraph.cpp:254
clang::CallGraphNode::end
const_iterator end() const
Definition: CallGraph.h:180
llvm::GraphTraits< clang::CallGraphNode * >::child_end
static ChildIteratorType child_end(NodeType *N)
Definition: CallGraph.h:250
clang::CallGraph::CallGraph
CallGraph()
Definition: CallGraph.cpp:149
llvm::DenseMapInfo< clang::CallGraphNode::CallRecord >::isEqual
static bool isEqual(const clang::CallGraphNode::CallRecord &LHS, const clang::CallGraphNode::CallRecord &RHS)
Definition: CallGraph.h:236
clang::CallGraph::getNode
CallGraphNode * getNode(const Decl *) const
Lookup the node for the given declaration.
Definition: CallGraph.cpp:197
llvm::SmallVectorImpl
Definition: LLVM.h:39
llvm::GraphTraits< clang::CallGraph * >::CGGetValue
static clang::CallGraphNode * CGGetValue(clang::CallGraph::const_iterator::value_type &P)
Definition: CallGraph.h:270
llvm::GraphTraits< clang::CallGraphNode * >::ChildIteratorType
NodeType::iterator ChildIteratorType
Definition: CallGraph.h:246
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::CallGraphNode::empty
bool empty() const
Definition: CallGraph.h:190
clang::CallGraph::viewGraph
void viewGraph() const
Definition: CallGraph.cpp:250
clang::CallGraphNode::CallRecord
Definition: CallGraph.h:149
clang::CallGraphNode::callees
llvm::iterator_range< iterator > callees()
Iterator access to callees/children of the node.
Definition: CallGraph.h:183
clang::FunctionDecl
Represents a function declaration or definition.
Definition: Decl.h:1856
clang::CallExpr
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2795
clang::operator==
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
Definition: CallGraph.h:207
llvm::GraphTraits< const clang::CallGraph * >::nodes_begin
static nodes_iterator nodes_begin(const clang::CallGraph *CG)
Definition: CallGraph.h:304
clang::CallGraph
The AST-based call graph.
Definition: CallGraph.h:42
clang::CallGraphNode::dump
void dump() const
Definition: CallGraph.cpp:260