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