Clang Project

clang_source_code/include/clang/Analysis/CallGraph.h
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"
21#include "clang/AST/RecursiveASTVisitor.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
29namespace clang {
30
31class CallGraphNode;
32class Decl;
33class DeclContext;
34class 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.
41class 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
53public:
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.
73  CallGraphNode *getOrInsertNode(Decl *);
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
102  void addNodesForBlocks(DeclContext *D);
103
104  /// Part of recursive declaration visitation. We recursively visit all the
105  /// declarations to collect the root functions.
106  bool VisitFunctionDecl(FunctionDecl *FD) {
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.
121  bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
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
135private:
136  /// Add the given declaration to the call graph.
137  void addNodeForDecl(Decl *D, bool IsGlobal);
138
139  /// Allocate a new node in the graph.
140  CallGraphNode *allocateNewNode(Decl *);
141};
142
143class CallGraphNode {
144public:
145  using CallRecord = CallGraphNode *;
146
147private:
148  /// The function/method declaration.
149  Decl *FD;
150
151  /// The list of functions called from this node.
152  SmallVector<CallRecord, 5> CalledFunctions;
153
154public:
155  CallGraphNode(Decl *D) : FD(D) {}
156
157  using iterator = SmallVectorImpl<CallRecord>::iterator;
158  using const_iterator = SmallVectorImpl<CallRecord>::const_iterator;
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
169  void addCallee(CallGraphNode *N) {
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.
182namespace llvm {
183
184template <> struct GraphTraits<clang::CallGraphNode*> {
185  using NodeType = clang::CallGraphNode;
186  using NodeRef = clang::CallGraphNode *;
187  using ChildIteratorType = NodeType::iterator;
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
194template <> struct GraphTraits<const clang::CallGraphNode*> {
195  using NodeType = const clang::CallGraphNode;
196  using NodeRef = const clang::CallGraphNode *;
197  using ChildIteratorType = NodeType::const_iterator;
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
204template <> 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
219  static nodes_iterator nodes_begin(clang::CallGraph *CG) {
220    return nodes_iterator(CG->begin(), &CGGetValue);
221  }
222
223  static nodes_iterator nodes_end  (clang::CallGraph *CG) {
224    return nodes_iterator(CG->end(), &CGGetValue);
225  }
226
227  static unsigned size(clang::CallGraph *CG) { return CG->size(); }
228};
229
230template <> 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
245  static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
246    return nodes_iterator(CG->begin(), &CGGetValue);
247  }
248
249  static nodes_iterator nodes_end(const clang::CallGraph *CG) {
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
259
clang::CallGraph::FunctionMap
clang::CallGraph::Root
clang::CallGraph::addToCallGraph
clang::CallGraph::includeInGraph
clang::CallGraph::getNode
clang::CallGraph::getOrInsertNode
clang::CallGraph::begin
clang::CallGraph::end
clang::CallGraph::begin
clang::CallGraph::end
clang::CallGraph::size
clang::CallGraph::getRoot
clang::CallGraph::print
clang::CallGraph::dump
clang::CallGraph::viewGraph
clang::CallGraph::addNodesForBlocks
clang::CallGraph::VisitFunctionDecl
clang::CallGraph::VisitObjCMethodDecl
clang::CallGraph::TraverseStmt
clang::CallGraph::shouldWalkTypesOfTypeLocs
clang::CallGraph::shouldVisitTemplateInstantiations
clang::CallGraph::addNodeForDecl
clang::CallGraph::allocateNewNode
clang::CallGraphNode::FD
clang::CallGraphNode::CalledFunctions
clang::CallGraphNode::begin
clang::CallGraphNode::end
clang::CallGraphNode::begin
clang::CallGraphNode::end
clang::CallGraphNode::empty
clang::CallGraphNode::size
clang::CallGraphNode::addCallee
clang::CallGraphNode::getDecl
clang::CallGraphNode::print
clang::CallGraphNode::dump
llvm::GraphTraits::getEntryNode
llvm::GraphTraits::child_begin
llvm::GraphTraits::child_end
CodeThinker, Enjoy your reading code