/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/Analysis/ReachableCode.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- ReachableCode.cpp - Code Reachability Analysis --------------------===// |
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 implements a flow-sensitive, path-insensitive analysis of |
10 | | // determining reachable blocks within a CFG. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "clang/Analysis/Analyses/ReachableCode.h" |
15 | | #include "clang/AST/Expr.h" |
16 | | #include "clang/AST/ExprCXX.h" |
17 | | #include "clang/AST/ExprObjC.h" |
18 | | #include "clang/AST/ParentMap.h" |
19 | | #include "clang/AST/StmtCXX.h" |
20 | | #include "clang/Analysis/AnalysisDeclContext.h" |
21 | | #include "clang/Analysis/CFG.h" |
22 | | #include "clang/Basic/SourceManager.h" |
23 | | #include "clang/Lex/Preprocessor.h" |
24 | | #include "llvm/ADT/BitVector.h" |
25 | | #include "llvm/ADT/SmallVector.h" |
26 | | |
27 | | using namespace clang; |
28 | | |
29 | | //===----------------------------------------------------------------------===// |
30 | | // Core Reachability Analysis routines. |
31 | | //===----------------------------------------------------------------------===// |
32 | | |
33 | 0 | static bool isEnumConstant(const Expr *Ex) { |
34 | 0 | const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex); |
35 | 0 | if (!DR) |
36 | 0 | return false; |
37 | 0 | return isa<EnumConstantDecl>(DR->getDecl()); |
38 | 0 | } |
39 | | |
40 | 3 | static bool isTrivialExpression(const Expr *Ex) { |
41 | 3 | Ex = Ex->IgnoreParenCasts(); |
42 | 3 | return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex)0 || |
43 | 3 | isa<CXXBoolLiteralExpr>(Ex)0 || isa<ObjCBoolLiteralExpr>(Ex)0 || |
44 | 3 | isa<CharacterLiteral>(Ex)0 || |
45 | 3 | isEnumConstant(Ex)0 ; |
46 | 3 | } |
47 | | |
48 | 170 | static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) { |
49 | 170 | // Check if the block ends with a do...while() and see if 'S' is the |
50 | 170 | // condition. |
51 | 170 | if (const Stmt *Term = B->getTerminatorStmt()) { |
52 | 29 | if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) { |
53 | 5 | const Expr *Cond = DS->getCond()->IgnoreParenCasts(); |
54 | 5 | return Cond == S && isTrivialExpression(Cond)3 ; |
55 | 5 | } |
56 | 165 | } |
57 | 165 | return false; |
58 | 165 | } |
59 | | |
60 | 167 | static bool isBuiltinUnreachable(const Stmt *S) { |
61 | 167 | if (const auto *DRE = dyn_cast<DeclRefExpr>(S)) |
62 | 119 | if (const auto *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl())) |
63 | 103 | return FDecl->getIdentifier() && |
64 | 103 | FDecl->getBuiltinID() == Builtin::BI__builtin_unreachable; |
65 | 64 | return false; |
66 | 64 | } |
67 | | |
68 | | static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S, |
69 | 161 | ASTContext &C) { |
70 | 161 | if (B->empty()) { |
71 | 8 | // Happens if S is B's terminator and B contains nothing else |
72 | 8 | // (e.g. a CFGBlock containing only a goto). |
73 | 8 | return false; |
74 | 8 | } |
75 | 153 | if (Optional<CFGStmt> CS = B->back().getAs<CFGStmt>()) { |
76 | 152 | if (const auto *CE = dyn_cast<CallExpr>(CS->getStmt())) { |
77 | 90 | return CE->getCallee()->IgnoreCasts() == S && CE->isBuiltinAssumeFalse(C)83 ; |
78 | 90 | } |
79 | 63 | } |
80 | 63 | return false; |
81 | 63 | } |
82 | | |
83 | 153 | static bool isDeadReturn(const CFGBlock *B, const Stmt *S) { |
84 | 153 | // Look to see if the current control flow ends with a 'return', and see if |
85 | 153 | // 'S' is a substatement. The 'return' may not be the last element in the |
86 | 153 | // block, or may be in a subsequent block because of destructors. |
87 | 153 | const CFGBlock *Current = B; |
88 | 154 | while (true) { |
89 | 154 | for (CFGBlock::const_reverse_iterator I = Current->rbegin(), |
90 | 154 | E = Current->rend(); |
91 | 155 | I != E; ++I1 ) { |
92 | 146 | if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) { |
93 | 145 | if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) { |
94 | 34 | if (RS == S) |
95 | 5 | return true; |
96 | 29 | if (const Expr *RE = RS->getRetValue()) { |
97 | 29 | RE = RE->IgnoreParenCasts(); |
98 | 29 | if (RE == S) |
99 | 21 | return true; |
100 | 8 | ParentMap PM(const_cast<Expr *>(RE)); |
101 | 8 | // If 'S' is in the ParentMap, it is a subexpression of |
102 | 8 | // the return statement. |
103 | 8 | return PM.getParent(S); |
104 | 8 | } |
105 | 29 | } |
106 | 111 | break; |
107 | 111 | } |
108 | 146 | } |
109 | 154 | // Note also that we are restricting the search for the return statement |
110 | 154 | // to stop at control-flow; only part of a return statement may be dead, |
111 | 154 | // without the whole return statement being dead. |
112 | 154 | if (120 Current->getTerminator().isTemporaryDtorsBranch()120 ) { |
113 | 0 | // Temporary destructors have a predictable control flow, thus we want to |
114 | 0 | // look into the next block for the return statement. |
115 | 0 | // We look into the false branch, as we know the true branch only contains |
116 | 0 | // the call to the destructor. |
117 | 0 | assert(Current->succ_size() == 2); |
118 | 0 | Current = *(Current->succ_begin() + 1); |
119 | 120 | } else if (!Current->getTerminatorStmt() && Current->succ_size() == 194 ) { |
120 | 93 | // If there is only one successor, we're not dealing with outgoing control |
121 | 93 | // flow. Thus, look into the next block. |
122 | 93 | Current = *Current->succ_begin(); |
123 | 93 | if (Current->pred_size() > 1) { |
124 | 92 | // If there is more than one predecessor, we're dealing with incoming |
125 | 92 | // control flow - if the return statement is in that block, it might |
126 | 92 | // well be reachable via a different control flow, thus it's not dead. |
127 | 92 | return false; |
128 | 92 | } |
129 | 27 | } else { |
130 | 27 | // We hit control flow or a dead end. Stop searching. |
131 | 27 | return false; |
132 | 27 | } |
133 | 120 | } |
134 | 153 | llvm_unreachable0 ("Broke out of infinite loop."); |
135 | 153 | } |
136 | | |
137 | 29 | static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM) { |
138 | 29 | assert(Loc.isMacroID()); |
139 | 29 | SourceLocation Last; |
140 | 59 | while (Loc.isMacroID()) { |
141 | 30 | Last = Loc; |
142 | 30 | Loc = SM.getImmediateMacroCallerLoc(Loc); |
143 | 30 | } |
144 | 29 | return Last; |
145 | 29 | } |
146 | | |
147 | | /// Returns true if the statement is expanded from a configuration macro. |
148 | | static bool isExpandedFromConfigurationMacro(const Stmt *S, |
149 | | Preprocessor &PP, |
150 | 117 | bool IgnoreYES_NO = false) { |
151 | 117 | // FIXME: This is not very precise. Here we just check to see if the |
152 | 117 | // value comes from a macro, but we can do much better. This is likely |
153 | 117 | // to be over conservative. This logic is factored into a separate function |
154 | 117 | // so that we can refine it later. |
155 | 117 | SourceLocation L = S->getBeginLoc(); |
156 | 117 | if (L.isMacroID()) { |
157 | 29 | SourceManager &SM = PP.getSourceManager(); |
158 | 29 | if (IgnoreYES_NO) { |
159 | 9 | // The Objective-C constant 'YES' and 'NO' |
160 | 9 | // are defined as macros. Do not treat them |
161 | 9 | // as configuration values. |
162 | 9 | SourceLocation TopL = getTopMostMacro(L, SM); |
163 | 9 | StringRef MacroName = PP.getImmediateMacroName(TopL); |
164 | 9 | if (MacroName == "YES" || MacroName == "NO"4 ) |
165 | 8 | return false; |
166 | 20 | } else if (!PP.getLangOpts().CPlusPlus) { |
167 | 20 | // Do not treat C 'false' and 'true' macros as configuration values. |
168 | 20 | SourceLocation TopL = getTopMostMacro(L, SM); |
169 | 20 | StringRef MacroName = PP.getImmediateMacroName(TopL); |
170 | 20 | if (MacroName == "false" || MacroName == "true"16 ) |
171 | 8 | return false; |
172 | 13 | } |
173 | 13 | return true; |
174 | 13 | } |
175 | 88 | return false; |
176 | 88 | } |
177 | | |
178 | | static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP); |
179 | | |
180 | | /// Returns true if the statement represents a configuration value. |
181 | | /// |
182 | | /// A configuration value is something usually determined at compile-time |
183 | | /// to conditionally always execute some branch. Such guards are for |
184 | | /// "sometimes unreachable" code. Such code is usually not interesting |
185 | | /// to report as unreachable, and may mask truly unreachable code within |
186 | | /// those blocks. |
187 | | static bool isConfigurationValue(const Stmt *S, |
188 | | Preprocessor &PP, |
189 | | SourceRange *SilenceableCondVal = nullptr, |
190 | | bool IncludeIntegers = true, |
191 | 473 | bool WrappedInParens = false) { |
192 | 473 | if (!S) |
193 | 32 | return false; |
194 | 441 | |
195 | 441 | if (const auto *Ex = dyn_cast<Expr>(S)) |
196 | 441 | S = Ex->IgnoreImplicit(); |
197 | 441 | |
198 | 441 | if (const auto *Ex = dyn_cast<Expr>(S)) |
199 | 441 | S = Ex->IgnoreCasts(); |
200 | 441 | |
201 | 441 | // Special case looking for the sigil '()' around an integer literal. |
202 | 441 | if (const ParenExpr *PE = dyn_cast<ParenExpr>(S)) |
203 | 32 | if (!PE->getBeginLoc().isMacroID()) |
204 | 28 | return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal, |
205 | 28 | IncludeIntegers, true); |
206 | 413 | |
207 | 413 | if (const Expr *Ex = dyn_cast<Expr>(S)) |
208 | 413 | S = Ex->IgnoreCasts(); |
209 | 413 | |
210 | 413 | bool IgnoreYES_NO = false; |
211 | 413 | |
212 | 413 | switch (S->getStmtClass()) { |
213 | 413 | case Stmt::CallExprClass: { |
214 | 6 | const FunctionDecl *Callee = |
215 | 6 | dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl()); |
216 | 6 | return Callee ? Callee->isConstexpr() : false0 ; |
217 | 413 | } |
218 | 413 | case Stmt::DeclRefExprClass: |
219 | 61 | return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP); |
220 | 413 | case Stmt::ObjCBoolLiteralExprClass: |
221 | 13 | IgnoreYES_NO = true; |
222 | 13 | LLVM_FALLTHROUGH; |
223 | 161 | case Stmt::CXXBoolLiteralExprClass: |
224 | 161 | case Stmt::IntegerLiteralClass: { |
225 | 161 | const Expr *E = cast<Expr>(S); |
226 | 161 | if (IncludeIntegers) { |
227 | 141 | if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid()47 ) |
228 | 44 | *SilenceableCondVal = E->getSourceRange(); |
229 | 141 | return WrappedInParens || isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO)117 ; |
230 | 141 | } |
231 | 20 | return false; |
232 | 20 | } |
233 | 20 | case Stmt::MemberExprClass: |
234 | 19 | return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP); |
235 | 20 | case Stmt::UnaryExprOrTypeTraitExprClass: |
236 | 9 | return true; |
237 | 91 | case Stmt::BinaryOperatorClass: { |
238 | 91 | const BinaryOperator *B = cast<BinaryOperator>(S); |
239 | 91 | // Only include raw integers (not enums) as configuration |
240 | 91 | // values if they are used in a logical or comparison operator |
241 | 91 | // (not arithmetic). |
242 | 91 | IncludeIntegers &= (B->isLogicalOp() || B->isComparisonOp()53 ); |
243 | 91 | return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal, |
244 | 91 | IncludeIntegers) || |
245 | 91 | isConfigurationValue(B->getRHS(), PP, SilenceableCondVal, |
246 | 72 | IncludeIntegers); |
247 | 20 | } |
248 | 62 | case Stmt::UnaryOperatorClass: { |
249 | 62 | const UnaryOperator *UO = cast<UnaryOperator>(S); |
250 | 62 | if (UO->getOpcode() != UO_LNot) |
251 | 4 | return false; |
252 | 58 | bool SilenceableCondValNotSet = |
253 | 58 | SilenceableCondVal && SilenceableCondVal->getBegin().isInvalid()17 ; |
254 | 58 | bool IsSubExprConfigValue = |
255 | 58 | isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal, |
256 | 58 | IncludeIntegers, WrappedInParens); |
257 | 58 | // Update the silenceable condition value source range only if the range |
258 | 58 | // was set directly by the child expression. |
259 | 58 | if (SilenceableCondValNotSet && |
260 | 58 | SilenceableCondVal->getBegin().isValid()15 && |
261 | 58 | *SilenceableCondVal == |
262 | 13 | UO->getSubExpr()->IgnoreCasts()->getSourceRange()) |
263 | 11 | *SilenceableCondVal = UO->getSourceRange(); |
264 | 58 | return IsSubExprConfigValue; |
265 | 58 | } |
266 | 58 | default: |
267 | 4 | return false; |
268 | 413 | } |
269 | 413 | } |
270 | | |
271 | 80 | static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) { |
272 | 80 | if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D)) |
273 | 12 | return isConfigurationValue(ED->getInitExpr(), PP); |
274 | 68 | if (const VarDecl *VD = dyn_cast<VarDecl>(D)) { |
275 | 50 | // As a heuristic, treat globals as configuration values. Note |
276 | 50 | // that we only will get here if Sema evaluated this |
277 | 50 | // condition to a constant expression, which means the global |
278 | 50 | // had to be declared in a way to be a truly constant value. |
279 | 50 | // We could generalize this to local variables, but it isn't |
280 | 50 | // clear if those truly represent configuration values that |
281 | 50 | // gate unreachable code. |
282 | 50 | if (!VD->hasLocalStorage()) |
283 | 5 | return true; |
284 | 45 | |
285 | 45 | // As a heuristic, locals that have been marked 'const' explicitly |
286 | 45 | // can be treated as configuration values as well. |
287 | 45 | return VD->getType().isLocalConstQualified(); |
288 | 45 | } |
289 | 18 | return false; |
290 | 18 | } |
291 | | |
292 | | /// Returns true if we should always explore all successors of a block. |
293 | | static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B, |
294 | 131 | Preprocessor &PP) { |
295 | 131 | if (const Stmt *Term = B->getTerminatorStmt()) { |
296 | 131 | if (isa<SwitchStmt>(Term)) |
297 | 6 | return true; |
298 | 125 | // Specially handle '||' and '&&'. |
299 | 125 | if (isa<BinaryOperator>(Term)) { |
300 | 11 | return isConfigurationValue(Term, PP); |
301 | 11 | } |
302 | 114 | } |
303 | 114 | |
304 | 114 | const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false); |
305 | 114 | return isConfigurationValue(Cond, PP); |
306 | 114 | } |
307 | | |
308 | | static unsigned scanFromBlock(const CFGBlock *Start, |
309 | | llvm::BitVector &Reachable, |
310 | | Preprocessor *PP, |
311 | 234k | bool IncludeSometimesUnreachableEdges) { |
312 | 234k | unsigned count = 0; |
313 | 234k | |
314 | 234k | // Prep work queue |
315 | 234k | SmallVector<const CFGBlock*, 32> WL; |
316 | 234k | |
317 | 234k | // The entry block may have already been marked reachable |
318 | 234k | // by the caller. |
319 | 234k | if (!Reachable[Start->getBlockID()]) { |
320 | 234k | ++count; |
321 | 234k | Reachable[Start->getBlockID()] = true; |
322 | 234k | } |
323 | 234k | |
324 | 234k | WL.push_back(Start); |
325 | 234k | |
326 | 234k | // Find the reachable blocks from 'Start'. |
327 | 1.31M | while (!WL.empty()) { |
328 | 1.10M | const CFGBlock *item = WL.pop_back_val(); |
329 | 1.10M | |
330 | 1.10M | // There are cases where we want to treat all successors as reachable. |
331 | 1.10M | // The idea is that some "sometimes unreachable" code is not interesting, |
332 | 1.10M | // and that we should forge ahead and explore those branches anyway. |
333 | 1.10M | // This allows us to potentially uncover some "always unreachable" code |
334 | 1.10M | // within the "sometimes unreachable" code. |
335 | 1.10M | // Look at the successors and mark then reachable. |
336 | 1.10M | Optional<bool> TreatAllSuccessorsAsReachable; |
337 | 1.10M | if (!IncludeSometimesUnreachableEdges) |
338 | 1.10M | TreatAllSuccessorsAsReachable = false; |
339 | 1.10M | |
340 | 1.10M | for (CFGBlock::const_succ_iterator I = item->succ_begin(), |
341 | 2.24M | E = item->succ_end(); I != E; ++I1.13M ) { |
342 | 1.16M | const CFGBlock *B = *I; |
343 | 1.16M | if (!B) do 100k { |
344 | 100k | const CFGBlock *UB = I->getPossiblyUnreachableBlock(); |
345 | 100k | if (!UB) |
346 | 30.8k | break; |
347 | 69.8k | |
348 | 69.8k | if (!TreatAllSuccessorsAsReachable.hasValue()) { |
349 | 131 | assert(PP); |
350 | 131 | TreatAllSuccessorsAsReachable = |
351 | 131 | shouldTreatSuccessorsAsReachable(item, *PP); |
352 | 131 | } |
353 | 69.8k | |
354 | 69.8k | if (TreatAllSuccessorsAsReachable.getValue()) { |
355 | 60 | B = UB; |
356 | 60 | break; |
357 | 60 | } |
358 | 69.8k | } |
359 | 69.8k | while (false); |
360 | 1.16M | |
361 | 1.16M | if (1.13M B1.13M ) { |
362 | 1.06M | unsigned blockID = B->getBlockID(); |
363 | 1.06M | if (!Reachable[blockID]) { |
364 | 874k | Reachable.set(blockID); |
365 | 874k | WL.push_back(B); |
366 | 874k | ++count; |
367 | 874k | } |
368 | 1.06M | } |
369 | 1.13M | } |
370 | 1.10M | } |
371 | 234k | return count203k ; |
372 | 234k | } |
373 | | |
374 | | static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start, |
375 | | Preprocessor &PP, |
376 | 363 | llvm::BitVector &Reachable) { |
377 | 363 | return scanFromBlock(Start, Reachable, &PP, true); |
378 | 363 | } |
379 | | |
380 | | //===----------------------------------------------------------------------===// |
381 | | // Dead Code Scanner. |
382 | | //===----------------------------------------------------------------------===// |
383 | | |
384 | | namespace { |
385 | | class DeadCodeScan { |
386 | | llvm::BitVector Visited; |
387 | | llvm::BitVector &Reachable; |
388 | | SmallVector<const CFGBlock *, 10> WorkList; |
389 | | Preprocessor &PP; |
390 | | ASTContext &C; |
391 | | |
392 | | typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12> |
393 | | DeferredLocsTy; |
394 | | |
395 | | DeferredLocsTy DeferredLocs; |
396 | | |
397 | | public: |
398 | | DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP, ASTContext &C) |
399 | | : Visited(reachable.size()), |
400 | | Reachable(reachable), |
401 | 211 | PP(PP), C(C) {} |
402 | | |
403 | | void enqueue(const CFGBlock *block); |
404 | | unsigned scanBackwards(const CFGBlock *Start, |
405 | | clang::reachable_code::Callback &CB); |
406 | | |
407 | | bool isDeadCodeRoot(const CFGBlock *Block); |
408 | | |
409 | | const Stmt *findDeadCode(const CFGBlock *Block); |
410 | | |
411 | | void reportDeadCode(const CFGBlock *B, |
412 | | const Stmt *S, |
413 | | clang::reachable_code::Callback &CB); |
414 | | }; |
415 | | } |
416 | | |
417 | 216 | void DeadCodeScan::enqueue(const CFGBlock *block) { |
418 | 216 | unsigned blockID = block->getBlockID(); |
419 | 216 | if (Reachable[blockID] || Visited[blockID]) |
420 | 0 | return; |
421 | 216 | Visited[blockID] = true; |
422 | 216 | WorkList.push_back(block); |
423 | 216 | } |
424 | | |
425 | 208 | bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) { |
426 | 208 | bool isDeadRoot = true; |
427 | 208 | |
428 | 208 | for (CFGBlock::const_pred_iterator I = Block->pred_begin(), |
429 | 377 | E = Block->pred_end(); I != E; ++I169 ) { |
430 | 169 | if (const CFGBlock *PredBlock = *I) { |
431 | 41 | unsigned blockID = PredBlock->getBlockID(); |
432 | 41 | if (Visited[blockID]) { |
433 | 6 | isDeadRoot = false; |
434 | 6 | continue; |
435 | 6 | } |
436 | 35 | if (!Reachable[blockID]) { |
437 | 35 | isDeadRoot = false; |
438 | 35 | Visited[blockID] = true; |
439 | 35 | WorkList.push_back(PredBlock); |
440 | 35 | continue; |
441 | 35 | } |
442 | 35 | } |
443 | 169 | } |
444 | 208 | |
445 | 208 | return isDeadRoot; |
446 | 208 | } |
447 | | |
448 | 234 | static bool isValidDeadStmt(const Stmt *S) { |
449 | 234 | if (S->getBeginLoc().isInvalid()) |
450 | 0 | return false; |
451 | 234 | if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S)) |
452 | 20 | return BO->getOpcode() != BO_Comma; |
453 | 214 | return true; |
454 | 214 | } |
455 | | |
456 | 247 | const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) { |
457 | 271 | for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I24 ) |
458 | 210 | if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) { |
459 | 202 | const Stmt *S = CS->getStmt(); |
460 | 202 | if (isValidDeadStmt(S)) |
461 | 186 | return S; |
462 | 202 | } |
463 | 247 | |
464 | 247 | CFGTerminator T = Block->getTerminator(); |
465 | 61 | if (T.isStmtBranch()) { |
466 | 58 | const Stmt *S = T.getStmt(); |
467 | 58 | if (S && isValidDeadStmt(S)32 ) |
468 | 32 | return S; |
469 | 29 | } |
470 | 29 | |
471 | 29 | return nullptr; |
472 | 29 | } |
473 | | |
474 | | static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1, |
475 | 16 | const std::pair<const CFGBlock *, const Stmt *> *p2) { |
476 | 16 | if (p1->second->getBeginLoc() < p2->second->getBeginLoc()) |
477 | 6 | return -1; |
478 | 10 | if (p2->second->getBeginLoc() < p1->second->getBeginLoc()) |
479 | 10 | return 1; |
480 | 0 | return 0; |
481 | 0 | } |
482 | | |
483 | | unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, |
484 | 211 | clang::reachable_code::Callback &CB) { |
485 | 211 | |
486 | 211 | unsigned count = 0; |
487 | 211 | enqueue(Start); |
488 | 211 | |
489 | 462 | while (!WorkList.empty()) { |
490 | 251 | const CFGBlock *Block = WorkList.pop_back_val(); |
491 | 251 | |
492 | 251 | // It is possible that this block has been marked reachable after |
493 | 251 | // it was enqueued. |
494 | 251 | if (Reachable[Block->getBlockID()]) |
495 | 4 | continue; |
496 | 247 | |
497 | 247 | // Look for any dead code within the block. |
498 | 247 | const Stmt *S = findDeadCode(Block); |
499 | 247 | |
500 | 247 | if (!S) { |
501 | 29 | // No dead code. Possibly an empty block. Look at dead predecessors. |
502 | 29 | for (CFGBlock::const_pred_iterator I = Block->pred_begin(), |
503 | 50 | E = Block->pred_end(); I != E; ++I21 ) { |
504 | 21 | if (const CFGBlock *predBlock = *I) |
505 | 5 | enqueue(predBlock); |
506 | 21 | } |
507 | 29 | continue; |
508 | 29 | } |
509 | 218 | |
510 | 218 | // Specially handle macro-expanded code. |
511 | 218 | if (S->getBeginLoc().isMacroID()) { |
512 | 10 | count += scanMaybeReachableFromBlock(Block, PP, Reachable); |
513 | 10 | continue; |
514 | 10 | } |
515 | 208 | |
516 | 208 | if (isDeadCodeRoot(Block)) { |
517 | 179 | reportDeadCode(Block, S, CB); |
518 | 179 | count += scanMaybeReachableFromBlock(Block, PP, Reachable); |
519 | 179 | } |
520 | 29 | else { |
521 | 29 | // Record this statement as the possibly best location in a |
522 | 29 | // strongly-connected component of dead code for emitting a |
523 | 29 | // warning. |
524 | 29 | DeferredLocs.push_back(std::make_pair(Block, S)); |
525 | 29 | } |
526 | 208 | } |
527 | 211 | |
528 | 211 | // If we didn't find a dead root, then report the dead code with the |
529 | 211 | // earliest location. |
530 | 211 | if (!DeferredLocs.empty()) { |
531 | 15 | llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp); |
532 | 15 | for (DeferredLocsTy::iterator I = DeferredLocs.begin(), |
533 | 44 | E = DeferredLocs.end(); I != E; ++I29 ) { |
534 | 29 | const CFGBlock *Block = I->first; |
535 | 29 | if (Reachable[Block->getBlockID()]) |
536 | 22 | continue; |
537 | 7 | reportDeadCode(Block, I->second, CB); |
538 | 7 | count += scanMaybeReachableFromBlock(Block, PP, Reachable); |
539 | 7 | } |
540 | 15 | } |
541 | 211 | |
542 | 211 | return count; |
543 | 211 | } |
544 | | |
545 | | static SourceLocation GetUnreachableLoc(const Stmt *S, |
546 | | SourceRange &R1, |
547 | 166 | SourceRange &R2) { |
548 | 166 | R1 = R2 = SourceRange(); |
549 | 166 | |
550 | 166 | if (const Expr *Ex = dyn_cast<Expr>(S)) |
551 | 137 | S = Ex->IgnoreParenImpCasts(); |
552 | 166 | |
553 | 166 | switch (S->getStmtClass()) { |
554 | 166 | case Expr::BinaryOperatorClass: { |
555 | 2 | const BinaryOperator *BO = cast<BinaryOperator>(S); |
556 | 2 | return BO->getOperatorLoc(); |
557 | 166 | } |
558 | 166 | case Expr::UnaryOperatorClass: { |
559 | 3 | const UnaryOperator *UO = cast<UnaryOperator>(S); |
560 | 3 | R1 = UO->getSubExpr()->getSourceRange(); |
561 | 3 | return UO->getOperatorLoc(); |
562 | 166 | } |
563 | 166 | case Expr::CompoundAssignOperatorClass: { |
564 | 2 | const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); |
565 | 2 | R1 = CAO->getLHS()->getSourceRange(); |
566 | 2 | R2 = CAO->getRHS()->getSourceRange(); |
567 | 2 | return CAO->getOperatorLoc(); |
568 | 166 | } |
569 | 166 | case Expr::BinaryConditionalOperatorClass: |
570 | 2 | case Expr::ConditionalOperatorClass: { |
571 | 2 | const AbstractConditionalOperator *CO = |
572 | 2 | cast<AbstractConditionalOperator>(S); |
573 | 2 | return CO->getQuestionLoc(); |
574 | 2 | } |
575 | 2 | case Expr::MemberExprClass: { |
576 | 1 | const MemberExpr *ME = cast<MemberExpr>(S); |
577 | 1 | R1 = ME->getSourceRange(); |
578 | 1 | return ME->getMemberLoc(); |
579 | 2 | } |
580 | 2 | case Expr::ArraySubscriptExprClass: { |
581 | 2 | const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); |
582 | 2 | R1 = ASE->getLHS()->getSourceRange(); |
583 | 2 | R2 = ASE->getRHS()->getSourceRange(); |
584 | 2 | return ASE->getRBracketLoc(); |
585 | 2 | } |
586 | 2 | case Expr::CStyleCastExprClass: { |
587 | 2 | const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); |
588 | 2 | R1 = CSC->getSubExpr()->getSourceRange(); |
589 | 2 | return CSC->getLParenLoc(); |
590 | 2 | } |
591 | 2 | case Expr::CXXFunctionalCastExprClass: { |
592 | 0 | const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); |
593 | 0 | R1 = CE->getSubExpr()->getSourceRange(); |
594 | 0 | return CE->getBeginLoc(); |
595 | 2 | } |
596 | 2 | case Stmt::CXXTryStmtClass: { |
597 | 0 | return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); |
598 | 2 | } |
599 | 2 | case Expr::ObjCBridgedCastExprClass: { |
600 | 0 | const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); |
601 | 0 | R1 = CSC->getSubExpr()->getSourceRange(); |
602 | 0 | return CSC->getLParenLoc(); |
603 | 2 | } |
604 | 152 | default: ; |
605 | 166 | } |
606 | 166 | R1 = S->getSourceRange(); |
607 | 152 | return S->getBeginLoc(); |
608 | 166 | } |
609 | | |
610 | | void DeadCodeScan::reportDeadCode(const CFGBlock *B, |
611 | | const Stmt *S, |
612 | 186 | clang::reachable_code::Callback &CB) { |
613 | 186 | // Classify the unreachable code found, or suppress it in some cases. |
614 | 186 | reachable_code::UnreachableKind UK = reachable_code::UK_Other; |
615 | 186 | |
616 | 186 | if (isa<BreakStmt>(S)) { |
617 | 16 | UK = reachable_code::UK_Break; |
618 | 170 | } else if (isTrivialDoWhile(B, S) || isBuiltinUnreachable(S)167 || |
619 | 170 | isBuiltinAssumeFalse(B, S, C)161 ) { |
620 | 17 | return; |
621 | 17 | } |
622 | 153 | else if (isDeadReturn(B, S)) { |
623 | 32 | UK = reachable_code::UK_Return; |
624 | 32 | } |
625 | 186 | |
626 | 186 | SourceRange SilenceableCondVal; |
627 | 169 | |
628 | 169 | if (UK == reachable_code::UK_Other) { |
629 | 121 | // Check if the dead code is part of the "loop target" of |
630 | 121 | // a for/for-range loop. This is the block that contains |
631 | 121 | // the increment code. |
632 | 121 | if (const Stmt *LoopTarget = B->getLoopTarget()) { |
633 | 3 | SourceLocation Loc = LoopTarget->getBeginLoc(); |
634 | 3 | SourceRange R1(Loc, Loc), R2; |
635 | 3 | |
636 | 3 | if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) { |
637 | 2 | const Expr *Inc = FS->getInc(); |
638 | 2 | Loc = Inc->getBeginLoc(); |
639 | 2 | R2 = Inc->getSourceRange(); |
640 | 2 | } |
641 | 3 | |
642 | 3 | CB.HandleUnreachable(reachable_code::UK_Loop_Increment, |
643 | 3 | Loc, SourceRange(), SourceRange(Loc, Loc), R2); |
644 | 3 | return; |
645 | 3 | } |
646 | 118 | |
647 | 118 | // Check if the dead block has a predecessor whose branch has |
648 | 118 | // a configuration value that *could* be modified to |
649 | 118 | // silence the warning. |
650 | 118 | CFGBlock::const_pred_iterator PI = B->pred_begin(); |
651 | 118 | if (PI != B->pred_end()) { |
652 | 93 | if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) { |
653 | 87 | const Stmt *TermCond = |
654 | 87 | PredBlock->getTerminatorCondition(/* strip parens */ false); |
655 | 87 | isConfigurationValue(TermCond, PP, &SilenceableCondVal); |
656 | 87 | } |
657 | 93 | } |
658 | 118 | } |
659 | 169 | |
660 | 169 | SourceRange R1, R2; |
661 | 166 | SourceLocation Loc = GetUnreachableLoc(S, R1, R2); |
662 | 166 | CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2); |
663 | 166 | } |
664 | | |
665 | | //===----------------------------------------------------------------------===// |
666 | | // Reachability APIs. |
667 | | //===----------------------------------------------------------------------===// |
668 | | |
669 | | namespace clang { namespace reachable_code { |
670 | | |
671 | 0 | void Callback::anchor() { } |
672 | | |
673 | | unsigned ScanReachableFromBlock(const CFGBlock *Start, |
674 | 234k | llvm::BitVector &Reachable) { |
675 | 234k | return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false); |
676 | 234k | } |
677 | | |
678 | | void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP, |
679 | 155 | Callback &CB) { |
680 | 155 | |
681 | 155 | CFG *cfg = AC.getCFG(); |
682 | 155 | if (!cfg) |
683 | 0 | return; |
684 | 155 | |
685 | 155 | // Scan for reachable blocks from the entrance of the CFG. |
686 | 155 | // If there are no unreachable blocks, we're done. |
687 | 155 | llvm::BitVector reachable(cfg->getNumBlockIDs()); |
688 | 155 | unsigned numReachable = |
689 | 155 | scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable); |
690 | 155 | if (numReachable == cfg->getNumBlockIDs()) |
691 | 50 | return; |
692 | 105 | |
693 | 105 | // If there aren't explicit EH edges, we should include the 'try' dispatch |
694 | 105 | // blocks as roots. |
695 | 105 | if (!AC.getCFGBuildOptions().AddEHEdges) { |
696 | 105 | for (CFG::try_block_iterator I = cfg->try_blocks_begin(), |
697 | 117 | E = cfg->try_blocks_end() ; I != E; ++I12 ) { |
698 | 12 | numReachable += scanMaybeReachableFromBlock(*I, PP, reachable); |
699 | 12 | } |
700 | 105 | if (numReachable == cfg->getNumBlockIDs()) |
701 | 1 | return; |
702 | 104 | } |
703 | 104 | |
704 | 104 | // There are some unreachable blocks. We need to find the root blocks that |
705 | 104 | // contain code that should be considered unreachable. |
706 | 610 | for (CFG::iterator I = cfg->begin(), E = cfg->end(); 104 I != E; ++I506 ) { |
707 | 599 | const CFGBlock *block = *I; |
708 | 599 | // A block may have been marked reachable during this loop. |
709 | 599 | if (reachable[block->getBlockID()]) |
710 | 388 | continue; |
711 | 211 | |
712 | 211 | DeadCodeScan DS(reachable, PP, AC.getASTContext()); |
713 | 211 | numReachable += DS.scanBackwards(block, CB); |
714 | 211 | |
715 | 211 | if (numReachable == cfg->getNumBlockIDs()) |
716 | 93 | return; |
717 | 211 | } |
718 | 104 | } |
719 | | |
720 | | }} // end namespace clang::reachable_code |