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