/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 | 23.9k | CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} |
52 | | |
53 | 412k | void VisitStmt(Stmt *S) { VisitChildren(S); } |
54 | | |
55 | 45.1k | Decl *getDeclFromCall(CallExpr *CE) { |
56 | 45.1k | if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) |
57 | 44.8k | return CalleeDecl; |
58 | | |
59 | | // Simple detection of a call through a block. |
60 | 256 | Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); |
61 | 256 | if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) { |
62 | 77 | NumBlockCallEdges++; |
63 | 77 | return Block->getBlockDecl(); |
64 | 77 | } |
65 | | |
66 | 179 | return nullptr; |
67 | 256 | } |
68 | | |
69 | 58.0k | void addCalledDecl(Decl *D, Expr *CallExpr) { |
70 | 58.0k | if (G->includeCalleeInGraph(D)) { |
71 | 58.0k | CallGraphNode *CalleeNode = G->getOrInsertNode(D); |
72 | 58.0k | CallerNode->addCallee({CalleeNode, CallExpr}); |
73 | 58.0k | } |
74 | 58.0k | } |
75 | | |
76 | 45.1k | void VisitCallExpr(CallExpr *CE) { |
77 | 45.1k | if (Decl *D = getDeclFromCall(CE)) |
78 | 44.9k | addCalledDecl(D, CE); |
79 | 45.1k | VisitChildren(CE); |
80 | 45.1k | } |
81 | | |
82 | 260 | void VisitLambdaExpr(LambdaExpr *LE) { |
83 | 260 | if (FunctionTemplateDecl *FTD = LE->getDependentCallOperator()) |
84 | 22 | for (FunctionDecl *FD : FTD->specializations()) |
85 | 22 | G->VisitFunctionDecl(FD); |
86 | 238 | else if (CXXMethodDecl *MD = LE->getCallOperator()) |
87 | 238 | G->VisitFunctionDecl(MD); |
88 | 260 | } |
89 | | |
90 | 954 | void VisitCXXNewExpr(CXXNewExpr *E) { |
91 | 954 | if (FunctionDecl *FD = E->getOperatorNew()) |
92 | 954 | addCalledDecl(FD, E); |
93 | 954 | VisitChildren(E); |
94 | 954 | } |
95 | | |
96 | 12.4k | void VisitCXXConstructExpr(CXXConstructExpr *E) { |
97 | 12.4k | CXXConstructorDecl *Ctor = E->getConstructor(); |
98 | 12.4k | if (FunctionDecl *Def = Ctor->getDefinition()) |
99 | 11.5k | addCalledDecl(Def, E); |
100 | 12.4k | VisitChildren(E); |
101 | 12.4k | } |
102 | | |
103 | | // Include the evaluation of the default argument. |
104 | 1.77k | void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) { |
105 | 1.77k | Visit(E->getExpr()); |
106 | 1.77k | } |
107 | | |
108 | | // Include the evaluation of the default initializers in a class. |
109 | 120 | void VisitCXXDefaultInitExpr(CXXDefaultInitExpr *E) { |
110 | 120 | Visit(E->getExpr()); |
111 | 120 | } |
112 | | |
113 | | // Adds may-call edges for the ObjC message sends. |
114 | 2.95k | void VisitObjCMessageExpr(ObjCMessageExpr *ME) { |
115 | 2.95k | if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { |
116 | 2.50k | Selector Sel = ME->getSelector(); |
117 | | |
118 | | // Find the callee definition within the same translation unit. |
119 | 2.50k | Decl *D = nullptr; |
120 | 2.50k | if (ME->isInstanceMessage()) |
121 | 2.25k | D = IDecl->lookupPrivateMethod(Sel); |
122 | 248 | else |
123 | 248 | D = IDecl->lookupPrivateClassMethod(Sel); |
124 | 2.50k | if (D) { |
125 | 617 | addCalledDecl(D, ME); |
126 | 617 | NumObjCCallEdges++; |
127 | 617 | } |
128 | 2.50k | } |
129 | 2.95k | } |
130 | | |
131 | 471k | void VisitChildren(Stmt *S) { |
132 | 471k | for (Stmt *SubStmt : S->children()) |
133 | 448k | if (SubStmt) |
134 | 447k | this->Visit(SubStmt); |
135 | 471k | } |
136 | | }; |
137 | | |
138 | | } // namespace |
139 | | |
140 | 26.1k | void CallGraph::addNodesForBlocks(DeclContext *D) { |
141 | 26.1k | if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) |
142 | 365 | addNodeForDecl(BD, true); |
143 | | |
144 | 26.1k | for (auto *I : D->decls()) |
145 | 39.8k | if (auto *DC = dyn_cast<DeclContext>(I)) |
146 | 2.54k | addNodesForBlocks(DC); |
147 | 26.1k | } |
148 | | |
149 | 1.68k | CallGraph::CallGraph() { |
150 | 1.68k | Root = getOrInsertNode(nullptr); |
151 | 1.68k | } |
152 | | |
153 | 1.68k | CallGraph::~CallGraph() = default; |
154 | | |
155 | 100k | bool CallGraph::includeInGraph(const Decl *D) { |
156 | 100k | assert(D); |
157 | 100k | if (!D->hasBody()) |
158 | 56.2k | return false; |
159 | | |
160 | 44.4k | return includeCalleeInGraph(D); |
161 | 100k | } |
162 | | |
163 | 102k | bool CallGraph::includeCalleeInGraph(const Decl *D) { |
164 | 102k | 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 | 100k | if (FD->isDependentContext()) |
168 | 20.6k | return false; |
169 | | |
170 | 80.0k | IdentifierInfo *II = FD->getIdentifier(); |
171 | 80.0k | if (II && II->getName().startswith("__inline")59.2k ) |
172 | 12 | return false; |
173 | 80.0k | } |
174 | | |
175 | 81.8k | return true; |
176 | 102k | } |
177 | | |
178 | 23.9k | void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { |
179 | 23.9k | assert(D); |
180 | | |
181 | | // Allocate a new node, mark it as root, and process its calls. |
182 | 0 | CallGraphNode *Node = getOrInsertNode(D); |
183 | | |
184 | | // Process all the calls by this function as well. |
185 | 23.9k | CGBuilder builder(this, Node); |
186 | 23.9k | if (Stmt *Body = D->getBody()) |
187 | 23.9k | builder.Visit(Body); |
188 | | |
189 | | // Include C++ constructor member initializers. |
190 | 23.9k | if (auto constructor = dyn_cast<CXXConstructorDecl>(D)) { |
191 | 3.22k | for (CXXCtorInitializer *init : constructor->inits()) { |
192 | 2.69k | builder.Visit(init->getInit()); |
193 | 2.69k | } |
194 | 3.22k | } |
195 | 23.9k | } |
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 | 83.7k | CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { |
204 | 83.7k | if (F && !isa<ObjCMethodDecl>(F)82.0k ) |
205 | 80.2k | F = F->getCanonicalDecl(); |
206 | | |
207 | 83.7k | std::unique_ptr<CallGraphNode> &Node = FunctionMap[F]; |
208 | 83.7k | if (Node) |
209 | 52.1k | return Node.get(); |
210 | | |
211 | 31.5k | Node = std::make_unique<CallGraphNode>(F); |
212 | | // Make Root node a parent of all functions to make sure all are reachable. |
213 | 31.5k | if (F) |
214 | 29.8k | Root->addCallee({Node.get(), /*Call=*/nullptr}); |
215 | 31.5k | return Node.get(); |
216 | 83.7k | } |
217 | | |
218 | 3 | void CallGraph::print(raw_ostream &OS) const { |
219 | 3 | 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 | 3 | llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this); |
224 | 3 | for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator |
225 | 37 | I = RPOT.begin(), E = RPOT.end(); I != E; ++I34 ) { |
226 | 34 | const CallGraphNode *N = *I; |
227 | | |
228 | 34 | OS << " Function: "; |
229 | 34 | if (N == Root) |
230 | 3 | OS << "< root >"; |
231 | 31 | else |
232 | 31 | N->print(OS); |
233 | | |
234 | 34 | OS << " calls: "; |
235 | 34 | for (CallGraphNode::const_iterator CI = N->begin(), |
236 | 91 | CE = N->end(); CI != CE; ++CI57 ) { |
237 | 57 | assert(CI->Callee != Root && "No one can call the root node."); |
238 | 0 | CI->Callee->print(OS); |
239 | 57 | OS << " "; |
240 | 57 | } |
241 | 34 | OS << '\n'; |
242 | 34 | } |
243 | 3 | OS.flush(); |
244 | 3 | } |
245 | | |
246 | 3 | LLVM_DUMP_METHOD void CallGraph::dump() const { |
247 | 3 | print(llvm::errs()); |
248 | 3 | } |
249 | | |
250 | 0 | void CallGraph::viewGraph() const { |
251 | 0 | llvm::ViewGraph(this, "CallGraph"); |
252 | 0 | } |
253 | | |
254 | 88 | void CallGraphNode::print(raw_ostream &os) const { |
255 | 88 | if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD)) |
256 | 85 | 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 |