/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Analysis/CallGraph.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- CallGraph.cpp - AST-based Call graph -------------------------------===// |
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 defines the AST-based CallGraph. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "clang/Analysis/CallGraph.h" |
14 | | #include "clang/AST/Decl.h" |
15 | | #include "clang/AST/DeclBase.h" |
16 | | #include "clang/AST/DeclObjC.h" |
17 | | #include "clang/AST/Expr.h" |
18 | | #include "clang/AST/ExprObjC.h" |
19 | | #include "clang/AST/Stmt.h" |
20 | | #include "clang/AST/StmtVisitor.h" |
21 | | #include "clang/Basic/IdentifierTable.h" |
22 | | #include "clang/Basic/LLVM.h" |
23 | | #include "llvm/ADT/PostOrderIterator.h" |
24 | | #include "llvm/ADT/STLExtras.h" |
25 | | #include "llvm/ADT/Statistic.h" |
26 | | #include "llvm/Support/Casting.h" |
27 | | #include "llvm/Support/Compiler.h" |
28 | | #include "llvm/Support/DOTGraphTraits.h" |
29 | | #include "llvm/Support/GraphWriter.h" |
30 | | #include "llvm/Support/raw_ostream.h" |
31 | | #include <cassert> |
32 | | #include <memory> |
33 | | #include <string> |
34 | | |
35 | | using namespace clang; |
36 | | |
37 | | #define DEBUG_TYPE "CallGraph" |
38 | | |
39 | | STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); |
40 | | STATISTIC(NumBlockCallEdges, "Number of block call edges"); |
41 | | |
42 | | namespace { |
43 | | |
44 | | /// A helper class, which walks the AST and locates all the call sites in the |
45 | | /// given function body. |
46 | | class CGBuilder : public StmtVisitor<CGBuilder> { |
47 | | CallGraph *G; |
48 | | CallGraphNode *CallerNode; |
49 | | |
50 | | public: |
51 | 21.8k | CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} |
52 | | |
53 | 346k | void VisitStmt(Stmt *S) { VisitChildren(S); } |
54 | | |
55 | 37.3k | Decl *getDeclFromCall(CallExpr *CE) { |
56 | 37.3k | if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) |
57 | 37.0k | return CalleeDecl; |
58 | | |
59 | | // Simple detection of a call through a block. |
60 | 246 | Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); |
61 | 246 | if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) { |
62 | 77 | NumBlockCallEdges++; |
63 | 77 | return Block->getBlockDecl(); |
64 | 77 | } |
65 | | |
66 | 169 | return nullptr; |
67 | 169 | } |
68 | | |
69 | 49.7k | void addCalledDecl(Decl *D, Expr *CallExpr) { |
70 | 49.7k | if (G->includeCalleeInGraph(D)) { |
71 | 49.6k | CallGraphNode *CalleeNode = G->getOrInsertNode(D); |
72 | 49.6k | CallerNode->addCallee({CalleeNode, CallExpr}); |
73 | 49.6k | } |
74 | 49.7k | } |
75 | | |
76 | 37.3k | void VisitCallExpr(CallExpr *CE) { |
77 | 37.3k | if (Decl *D = getDeclFromCall(CE)) |
78 | 37.1k | addCalledDecl(D, CE); |
79 | 37.3k | VisitChildren(CE); |
80 | 37.3k | } |
81 | | |
82 | 218 | void VisitLambdaExpr(LambdaExpr *LE) { |
83 | 218 | if (FunctionTemplateDecl *FTD = LE->getDependentCallOperator()) |
84 | 2 | for (FunctionDecl *FD : FTD->specializations()) |
85 | 2 | G->VisitFunctionDecl(FD); |
86 | 216 | else if (CXXMethodDecl *MD = LE->getCallOperator()) |
87 | 216 | G->VisitFunctionDecl(MD); |
88 | 218 | } |
89 | | |
90 | 843 | void VisitCXXNewExpr(CXXNewExpr *E) { |
91 | 843 | if (FunctionDecl *FD = E->getOperatorNew()) |
92 | 843 | addCalledDecl(FD, E); |
93 | 843 | VisitChildren(E); |
94 | 843 | } |
95 | | |
96 | 12.0k | void VisitCXXConstructExpr(CXXConstructExpr *E) { |
97 | 12.0k | CXXConstructorDecl *Ctor = E->getConstructor(); |
98 | 12.0k | if (FunctionDecl *Def = Ctor->getDefinition()) |
99 | 11.1k | addCalledDecl(Def, E); |
100 | 12.0k | VisitChildren(E); |
101 | 12.0k | } |
102 | | |
103 | | // Include the evaluation of the default argument. |
104 | 1.73k | void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) { |
105 | 1.73k | Visit(E->getExpr()); |
106 | 1.73k | } |
107 | | |
108 | | // Include the evaluation of the default initializers in a class. |
109 | 113 | void VisitCXXDefaultInitExpr(CXXDefaultInitExpr *E) { |
110 | 113 | Visit(E->getExpr()); |
111 | 113 | } |
112 | | |
113 | | // Adds may-call edges for the ObjC message sends. |
114 | 2.91k | void VisitObjCMessageExpr(ObjCMessageExpr *ME) { |
115 | 2.91k | if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { |
116 | 2.47k | Selector Sel = ME->getSelector(); |
117 | | |
118 | | // Find the callee definition within the same translation unit. |
119 | 2.47k | Decl *D = nullptr; |
120 | 2.47k | if (ME->isInstanceMessage()) |
121 | 2.22k | D = IDecl->lookupPrivateMethod(Sel); |
122 | 248 | else |
123 | 248 | D = IDecl->lookupPrivateClassMethod(Sel); |
124 | 2.47k | if (D) { |
125 | 587 | addCalledDecl(D, ME); |
126 | 587 | NumObjCCallEdges++; |
127 | 587 | } |
128 | 2.47k | } |
129 | 2.91k | } |
130 | | |
131 | 396k | void VisitChildren(Stmt *S) { |
132 | 396k | for (Stmt *SubStmt : S->children()) |
133 | 375k | if (SubStmt) |
134 | 374k | this->Visit(SubStmt); |
135 | 396k | } |
136 | | }; |
137 | | |
138 | | } // namespace |
139 | | |
140 | 23.6k | void CallGraph::addNodesForBlocks(DeclContext *D) { |
141 | 23.6k | if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) |
142 | 358 | addNodeForDecl(BD, true); |
143 | | |
144 | 23.6k | for (auto *I : D->decls()) |
145 | 34.8k | if (auto *DC = dyn_cast<DeclContext>(I)) |
146 | 2.19k | addNodesForBlocks(DC); |
147 | 23.6k | } |
148 | | |
149 | 1.31k | CallGraph::CallGraph() { |
150 | 1.31k | Root = getOrInsertNode(nullptr); |
151 | 1.31k | } |
152 | | |
153 | 1.31k | CallGraph::~CallGraph() = default; |
154 | | |
155 | 85.2k | bool CallGraph::includeInGraph(const Decl *D) { |
156 | 85.2k | assert(D); |
157 | 85.2k | if (!D->hasBody()) |
158 | 45.7k | return false; |
159 | | |
160 | 39.5k | return includeCalleeInGraph(D); |
161 | 39.5k | } |
162 | | |
163 | 89.2k | bool CallGraph::includeCalleeInGraph(const Decl *D) { |
164 | 89.2k | if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { |
165 | | // We skip function template definitions, as their semantics is |
166 | | // only determined when they are instantiated. |
167 | 87.4k | if (FD->isDependentContext()) |
168 | 17.8k | return false; |
169 | | |
170 | 69.5k | IdentifierInfo *II = FD->getIdentifier(); |
171 | 69.5k | if (II && II->getName().startswith("__inline")49.8k ) |
172 | 6 | return false; |
173 | 71.3k | } |
174 | | |
175 | 71.3k | return true; |
176 | 71.3k | } |
177 | | |
178 | 21.8k | void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { |
179 | 21.8k | assert(D); |
180 | | |
181 | | // Allocate a new node, mark it as root, and process its calls. |
182 | 21.8k | CallGraphNode *Node = getOrInsertNode(D); |
183 | | |
184 | | // Process all the calls by this function as well. |
185 | 21.8k | CGBuilder builder(this, Node); |
186 | 21.8k | if (Stmt *Body = D->getBody()) |
187 | 21.8k | builder.Visit(Body); |
188 | | |
189 | | // Include C++ constructor member initializers. |
190 | 21.8k | if (auto constructor = dyn_cast<CXXConstructorDecl>(D)) { |
191 | 2.59k | for (CXXCtorInitializer *init : constructor->inits()) { |
192 | 2.59k | builder.Visit(init->getInit()); |
193 | 2.59k | } |
194 | 3.12k | } |
195 | 21.8k | } |
196 | | |
197 | 0 | CallGraphNode *CallGraph::getNode(const Decl *F) const { |
198 | 0 | FunctionMapTy::const_iterator I = FunctionMap.find(F); |
199 | 0 | if (I == FunctionMap.end()) return nullptr; |
200 | 0 | return I->second.get(); |
201 | 0 | } |
202 | | |
203 | 72.8k | CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { |
204 | 72.8k | if (F && !isa<ObjCMethodDecl>(F)71.5k ) |
205 | 69.7k | F = F->getCanonicalDecl(); |
206 | | |
207 | 72.8k | std::unique_ptr<CallGraphNode> &Node = FunctionMap[F]; |
208 | 72.8k | if (Node) |
209 | 45.1k | return Node.get(); |
210 | | |
211 | 27.7k | Node = std::make_unique<CallGraphNode>(F); |
212 | | // Make Root node a parent of all functions to make sure all are reachable. |
213 | 27.7k | if (F) |
214 | 26.3k | Root->addCallee({Node.get(), /*Call=*/nullptr}); |
215 | 27.7k | return Node.get(); |
216 | 27.7k | } |
217 | | |
218 | 2 | void CallGraph::print(raw_ostream &OS) const { |
219 | 2 | OS << " --- Call graph Dump --- \n"; |
220 | | |
221 | | // We are going to print the graph in reverse post order, partially, to make |
222 | | // sure the output is deterministic. |
223 | 2 | llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this); |
224 | 2 | for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator |
225 | 33 | I = RPOT.begin(), E = RPOT.end(); I != E; ++I31 ) { |
226 | 31 | const CallGraphNode *N = *I; |
227 | | |
228 | 31 | OS << " Function: "; |
229 | 31 | if (N == Root) |
230 | 2 | OS << "< root >"; |
231 | 29 | else |
232 | 29 | N->print(OS); |
233 | | |
234 | 31 | OS << " calls: "; |
235 | 31 | for (CallGraphNode::const_iterator CI = N->begin(), |
236 | 85 | CE = N->end(); CI != CE; ++CI54 ) { |
237 | 54 | assert(CI->Callee != Root && "No one can call the root node."); |
238 | 54 | CI->Callee->print(OS); |
239 | 54 | OS << " "; |
240 | 54 | } |
241 | 31 | OS << '\n'; |
242 | 31 | } |
243 | 2 | OS.flush(); |
244 | 2 | } |
245 | | |
246 | 2 | LLVM_DUMP_METHOD void CallGraph::dump() const { |
247 | 2 | print(llvm::errs()); |
248 | 2 | } |
249 | | |
250 | 0 | void CallGraph::viewGraph() const { |
251 | 0 | llvm::ViewGraph(this, "CallGraph"); |
252 | 0 | } |
253 | | |
254 | 83 | void CallGraphNode::print(raw_ostream &os) const { |
255 | 83 | if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD)) |
256 | 80 | return ND->printQualifiedName(os); |
257 | 3 | os << "< >"; |
258 | 3 | } |
259 | | |
260 | 0 | LLVM_DUMP_METHOD void CallGraphNode::dump() const { |
261 | 0 | print(llvm::errs()); |
262 | 0 | } |
263 | | |
264 | | namespace llvm { |
265 | | |
266 | | template <> |
267 | | struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { |
268 | 0 | DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} |
269 | | |
270 | | static std::string getNodeLabel(const CallGraphNode *Node, |
271 | 0 | const CallGraph *CG) { |
272 | 0 | if (CG->getRoot() == Node) { |
273 | 0 | return "< root >"; |
274 | 0 | } |
275 | 0 | if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl())) |
276 | 0 | return ND->getNameAsString(); |
277 | 0 | else |
278 | 0 | return "< >"; |
279 | 0 | } |
280 | | }; |
281 | | |
282 | | } // namespace llvm |