clang 18.0.0git
ReachableCode.cpp
Go to the documentation of this file.
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
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/StmtCXX.h"
22#include "clang/Analysis/CFG.h"
26#include "llvm/ADT/BitVector.h"
27#include "llvm/ADT/SmallVector.h"
28#include <optional>
29
30using namespace clang;
31
32//===----------------------------------------------------------------------===//
33// Core Reachability Analysis routines.
34//===----------------------------------------------------------------------===//
35
36static bool isEnumConstant(const Expr *Ex) {
37 const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex);
38 if (!DR)
39 return false;
40 return isa<EnumConstantDecl>(DR->getDecl());
41}
42
43static bool isTrivialExpression(const Expr *Ex) {
44 Ex = Ex->IgnoreParenCasts();
45 return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex) ||
46 isa<CXXBoolLiteralExpr>(Ex) || isa<ObjCBoolLiteralExpr>(Ex) ||
47 isa<CharacterLiteral>(Ex) ||
49}
50
51static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) {
52 // Check if the block ends with a do...while() and see if 'S' is the
53 // condition.
54 if (const Stmt *Term = B->getTerminatorStmt()) {
55 if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
56 const Expr *Cond = DS->getCond()->IgnoreParenCasts();
57 return Cond == S && isTrivialExpression(Cond);
58 }
59 }
60 return false;
61}
62
63static bool isBuiltinUnreachable(const Stmt *S) {
64 if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
65 if (const auto *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl()))
66 return FDecl->getIdentifier() &&
67 FDecl->getBuiltinID() == Builtin::BI__builtin_unreachable;
68 return false;
69}
70
71static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S,
72 ASTContext &C) {
73 if (B->empty()) {
74 // Happens if S is B's terminator and B contains nothing else
75 // (e.g. a CFGBlock containing only a goto).
76 return false;
77 }
78 if (std::optional<CFGStmt> CS = B->back().getAs<CFGStmt>()) {
79 if (const auto *CE = dyn_cast<CallExpr>(CS->getStmt())) {
80 return CE->getCallee()->IgnoreCasts() == S && CE->isBuiltinAssumeFalse(C);
81 }
82 }
83 return false;
84}
85
86static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
87 // Look to see if the current control flow ends with a 'return', and see if
88 // 'S' is a substatement. The 'return' may not be the last element in the
89 // block, or may be in a subsequent block because of destructors.
90 const CFGBlock *Current = B;
91 while (true) {
92 for (const CFGElement &CE : llvm::reverse(*Current)) {
93 if (std::optional<CFGStmt> CS = CE.getAs<CFGStmt>()) {
94 if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
95 if (RS == S)
96 return true;
97 if (const Expr *RE = RS->getRetValue()) {
98 RE = RE->IgnoreParenCasts();
99 if (RE == S)
100 return true;
101 ParentMap PM(const_cast<Expr *>(RE));
102 // If 'S' is in the ParentMap, it is a subexpression of
103 // the return statement.
104 return PM.getParent(S);
105 }
106 }
107 break;
108 }
109 }
110 // Note also that we are restricting the search for the return statement
111 // to stop at control-flow; only part of a return statement may be dead,
112 // without the whole return statement being dead.
113 if (Current->getTerminator().isTemporaryDtorsBranch()) {
114 // Temporary destructors have a predictable control flow, thus we want to
115 // look into the next block for the return statement.
116 // We look into the false branch, as we know the true branch only contains
117 // the call to the destructor.
118 assert(Current->succ_size() == 2);
119 Current = *(Current->succ_begin() + 1);
120 } else if (!Current->getTerminatorStmt() && Current->succ_size() == 1) {
121 // If there is only one successor, we're not dealing with outgoing control
122 // flow. Thus, look into the next block.
123 Current = *Current->succ_begin();
124 if (Current->pred_size() > 1) {
125 // If there is more than one predecessor, we're dealing with incoming
126 // control flow - if the return statement is in that block, it might
127 // well be reachable via a different control flow, thus it's not dead.
128 return false;
129 }
130 } else {
131 // We hit control flow or a dead end. Stop searching.
132 return false;
133 }
134 }
135 llvm_unreachable("Broke out of infinite loop.");
136}
137
139 assert(Loc.isMacroID());
141 do {
142 Last = Loc;
143 Loc = SM.getImmediateMacroCallerLoc(Loc);
144 } while (Loc.isMacroID());
145 return Last;
146}
147
148/// Returns true if the statement is expanded from a configuration macro.
150 Preprocessor &PP,
151 bool IgnoreYES_NO = false) {
152 // FIXME: This is not very precise. Here we just check to see if the
153 // value comes from a macro, but we can do much better. This is likely
154 // to be over conservative. This logic is factored into a separate function
155 // so that we can refine it later.
156 SourceLocation L = S->getBeginLoc();
157 if (L.isMacroID()) {
159 if (IgnoreYES_NO) {
160 // The Objective-C constant 'YES' and 'NO'
161 // are defined as macros. Do not treat them
162 // as configuration values.
164 StringRef MacroName = PP.getImmediateMacroName(TopL);
165 if (MacroName == "YES" || MacroName == "NO")
166 return false;
167 } else if (!PP.getLangOpts().CPlusPlus) {
168 // Do not treat C 'false' and 'true' macros as configuration values.
170 StringRef MacroName = PP.getImmediateMacroName(TopL);
171 if (MacroName == "false" || MacroName == "true")
172 return false;
173 }
174 return true;
175 }
176 return false;
177}
178
179static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP);
180
181/// Returns true if the statement represents a configuration value.
182///
183/// A configuration value is something usually determined at compile-time
184/// to conditionally always execute some branch. Such guards are for
185/// "sometimes unreachable" code. Such code is usually not interesting
186/// to report as unreachable, and may mask truly unreachable code within
187/// those blocks.
188static bool isConfigurationValue(const Stmt *S,
189 Preprocessor &PP,
190 SourceRange *SilenceableCondVal = nullptr,
191 bool IncludeIntegers = true,
192 bool WrappedInParens = false) {
193 if (!S)
194 return false;
195
196 if (const auto *Ex = dyn_cast<Expr>(S))
197 S = Ex->IgnoreImplicit();
198
199 if (const auto *Ex = dyn_cast<Expr>(S))
200 S = Ex->IgnoreCasts();
201
202 // Special case looking for the sigil '()' around an integer literal.
203 if (const ParenExpr *PE = dyn_cast<ParenExpr>(S))
204 if (!PE->getBeginLoc().isMacroID())
205 return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal,
206 IncludeIntegers, true);
207
208 if (const Expr *Ex = dyn_cast<Expr>(S))
209 S = Ex->IgnoreCasts();
210
211 bool IgnoreYES_NO = false;
212
213 switch (S->getStmtClass()) {
214 case Stmt::CallExprClass: {
215 const FunctionDecl *Callee =
216 dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
217 return Callee ? Callee->isConstexpr() : false;
218 }
219 case Stmt::DeclRefExprClass:
220 return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP);
221 case Stmt::ObjCBoolLiteralExprClass:
222 IgnoreYES_NO = true;
223 [[fallthrough]];
224 case Stmt::CXXBoolLiteralExprClass:
225 case Stmt::IntegerLiteralClass: {
226 const Expr *E = cast<Expr>(S);
227 if (IncludeIntegers) {
228 if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())
229 *SilenceableCondVal = E->getSourceRange();
230 return WrappedInParens ||
231 isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO);
232 }
233 return false;
234 }
235 case Stmt::MemberExprClass:
236 return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP);
237 case Stmt::UnaryExprOrTypeTraitExprClass:
238 return true;
239 case Stmt::BinaryOperatorClass: {
240 const BinaryOperator *B = cast<BinaryOperator>(S);
241 // Only include raw integers (not enums) as configuration
242 // values if they are used in a logical or comparison operator
243 // (not arithmetic).
244 IncludeIntegers &= (B->isLogicalOp() || B->isComparisonOp());
245 return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal,
246 IncludeIntegers) ||
247 isConfigurationValue(B->getRHS(), PP, SilenceableCondVal,
248 IncludeIntegers);
249 }
250 case Stmt::UnaryOperatorClass: {
251 const UnaryOperator *UO = cast<UnaryOperator>(S);
252 if (UO->getOpcode() != UO_LNot && UO->getOpcode() != UO_Minus)
253 return false;
254 bool SilenceableCondValNotSet =
255 SilenceableCondVal && SilenceableCondVal->getBegin().isInvalid();
256 bool IsSubExprConfigValue =
257 isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal,
258 IncludeIntegers, WrappedInParens);
259 // Update the silenceable condition value source range only if the range
260 // was set directly by the child expression.
261 if (SilenceableCondValNotSet &&
262 SilenceableCondVal->getBegin().isValid() &&
263 *SilenceableCondVal ==
265 *SilenceableCondVal = UO->getSourceRange();
266 return IsSubExprConfigValue;
267 }
268 default:
269 return false;
270 }
271}
272
273static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) {
274 if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D))
275 return isConfigurationValue(ED->getInitExpr(), PP);
276 if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
277 // As a heuristic, treat globals as configuration values. Note
278 // that we only will get here if Sema evaluated this
279 // condition to a constant expression, which means the global
280 // had to be declared in a way to be a truly constant value.
281 // We could generalize this to local variables, but it isn't
282 // clear if those truly represent configuration values that
283 // gate unreachable code.
284 if (!VD->hasLocalStorage())
285 return true;
286
287 // As a heuristic, locals that have been marked 'const' explicitly
288 // can be treated as configuration values as well.
289 return VD->getType().isLocalConstQualified();
290 }
291 return false;
292}
293
294/// Returns true if we should always explore all successors of a block.
296 Preprocessor &PP) {
297 if (const Stmt *Term = B->getTerminatorStmt()) {
298 if (isa<SwitchStmt>(Term))
299 return true;
300 // Specially handle '||' and '&&'.
301 if (isa<BinaryOperator>(Term)) {
302 return isConfigurationValue(Term, PP);
303 }
304 // Do not treat constexpr if statement successors as unreachable in warnings
305 // since the point of these statements is to determine branches at compile
306 // time.
307 if (const auto *IS = dyn_cast<IfStmt>(Term);
308 IS != nullptr && IS->isConstexpr())
309 return true;
310 }
311
312 const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
313 return isConfigurationValue(Cond, PP);
314}
315
316static unsigned scanFromBlock(const CFGBlock *Start,
317 llvm::BitVector &Reachable,
318 Preprocessor *PP,
319 bool IncludeSometimesUnreachableEdges) {
320 unsigned count = 0;
321
322 // Prep work queue
324
325 // The entry block may have already been marked reachable
326 // by the caller.
327 if (!Reachable[Start->getBlockID()]) {
328 ++count;
329 Reachable[Start->getBlockID()] = true;
330 }
331
332 WL.push_back(Start);
333
334 // Find the reachable blocks from 'Start'.
335 while (!WL.empty()) {
336 const CFGBlock *item = WL.pop_back_val();
337
338 // There are cases where we want to treat all successors as reachable.
339 // The idea is that some "sometimes unreachable" code is not interesting,
340 // and that we should forge ahead and explore those branches anyway.
341 // This allows us to potentially uncover some "always unreachable" code
342 // within the "sometimes unreachable" code.
343 // Look at the successors and mark then reachable.
344 std::optional<bool> TreatAllSuccessorsAsReachable;
345 if (!IncludeSometimesUnreachableEdges)
346 TreatAllSuccessorsAsReachable = false;
347
349 E = item->succ_end(); I != E; ++I) {
350 const CFGBlock *B = *I;
351 if (!B) do {
352 const CFGBlock *UB = I->getPossiblyUnreachableBlock();
353 if (!UB)
354 break;
355
356 if (!TreatAllSuccessorsAsReachable) {
357 assert(PP);
358 TreatAllSuccessorsAsReachable =
360 }
361
362 if (*TreatAllSuccessorsAsReachable) {
363 B = UB;
364 break;
365 }
366 }
367 while (false);
368
369 if (B) {
370 unsigned blockID = B->getBlockID();
371 if (!Reachable[blockID]) {
372 Reachable.set(blockID);
373 WL.push_back(B);
374 ++count;
375 }
376 }
377 }
378 }
379 return count;
380}
381
382static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
383 Preprocessor &PP,
384 llvm::BitVector &Reachable) {
385 return scanFromBlock(Start, Reachable, &PP, true);
386}
387
388//===----------------------------------------------------------------------===//
389// Dead Code Scanner.
390//===----------------------------------------------------------------------===//
391
392namespace {
393 class DeadCodeScan {
394 llvm::BitVector Visited;
395 llvm::BitVector &Reachable;
397 Preprocessor &PP;
398 ASTContext &C;
399
401 DeferredLocsTy;
402
403 DeferredLocsTy DeferredLocs;
404
405 public:
406 DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP, ASTContext &C)
407 : Visited(reachable.size()),
408 Reachable(reachable),
409 PP(PP), C(C) {}
410
411 void enqueue(const CFGBlock *block);
412 unsigned scanBackwards(const CFGBlock *Start,
414
415 bool isDeadCodeRoot(const CFGBlock *Block);
416
417 const Stmt *findDeadCode(const CFGBlock *Block);
418
419 void reportDeadCode(const CFGBlock *B,
420 const Stmt *S,
422 };
423}
424
425void DeadCodeScan::enqueue(const CFGBlock *block) {
426 unsigned blockID = block->getBlockID();
427 if (Reachable[blockID] || Visited[blockID])
428 return;
429 Visited[blockID] = true;
430 WorkList.push_back(block);
431}
432
433bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
434 bool isDeadRoot = true;
435
437 E = Block->pred_end(); I != E; ++I) {
438 if (const CFGBlock *PredBlock = *I) {
439 unsigned blockID = PredBlock->getBlockID();
440 if (Visited[blockID]) {
441 isDeadRoot = false;
442 continue;
443 }
444 if (!Reachable[blockID]) {
445 isDeadRoot = false;
446 Visited[blockID] = true;
447 WorkList.push_back(PredBlock);
448 continue;
449 }
450 }
451 }
452
453 return isDeadRoot;
454}
455
456static bool isValidDeadStmt(const Stmt *S) {
457 if (S->getBeginLoc().isInvalid())
458 return false;
459 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
460 return BO->getOpcode() != BO_Comma;
461 return true;
462}
463
464const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
465 for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
466 if (std::optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
467 const Stmt *S = CS->getStmt();
468 if (isValidDeadStmt(S))
469 return S;
470 }
471
473 if (T.isStmtBranch()) {
474 const Stmt *S = T.getStmt();
475 if (S && isValidDeadStmt(S))
476 return S;
477 }
478
479 return nullptr;
480}
481
482static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
483 const std::pair<const CFGBlock *, const Stmt *> *p2) {
484 if (p1->second->getBeginLoc() < p2->second->getBeginLoc())
485 return -1;
486 if (p2->second->getBeginLoc() < p1->second->getBeginLoc())
487 return 1;
488 return 0;
489}
490
491unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
493
494 unsigned count = 0;
495 enqueue(Start);
496
497 while (!WorkList.empty()) {
498 const CFGBlock *Block = WorkList.pop_back_val();
499
500 // It is possible that this block has been marked reachable after
501 // it was enqueued.
502 if (Reachable[Block->getBlockID()])
503 continue;
504
505 // Look for any dead code within the block.
506 const Stmt *S = findDeadCode(Block);
507
508 if (!S) {
509 // No dead code. Possibly an empty block. Look at dead predecessors.
511 E = Block->pred_end(); I != E; ++I) {
512 if (const CFGBlock *predBlock = *I)
513 enqueue(predBlock);
514 }
515 continue;
516 }
517
518 // Specially handle macro-expanded code.
519 if (S->getBeginLoc().isMacroID()) {
520 count += scanMaybeReachableFromBlock(Block, PP, Reachable);
521 continue;
522 }
523
524 if (isDeadCodeRoot(Block)) {
525 reportDeadCode(Block, S, CB);
526 count += scanMaybeReachableFromBlock(Block, PP, Reachable);
527 }
528 else {
529 // Record this statement as the possibly best location in a
530 // strongly-connected component of dead code for emitting a
531 // warning.
532 DeferredLocs.push_back(std::make_pair(Block, S));
533 }
534 }
535
536 // If we didn't find a dead root, then report the dead code with the
537 // earliest location.
538 if (!DeferredLocs.empty()) {
539 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
540 for (const auto &I : DeferredLocs) {
541 const CFGBlock *Block = I.first;
542 if (Reachable[Block->getBlockID()])
543 continue;
544 reportDeadCode(Block, I.second, CB);
545 count += scanMaybeReachableFromBlock(Block, PP, Reachable);
546 }
547 }
548
549 return count;
550}
551
553 SourceRange &R1,
554 SourceRange &R2) {
555 R1 = R2 = SourceRange();
556
557 if (const Expr *Ex = dyn_cast<Expr>(S))
558 S = Ex->IgnoreParenImpCasts();
559
560 switch (S->getStmtClass()) {
561 case Expr::BinaryOperatorClass: {
562 const BinaryOperator *BO = cast<BinaryOperator>(S);
563 return BO->getOperatorLoc();
564 }
565 case Expr::UnaryOperatorClass: {
566 const UnaryOperator *UO = cast<UnaryOperator>(S);
567 R1 = UO->getSubExpr()->getSourceRange();
568 return UO->getOperatorLoc();
569 }
570 case Expr::CompoundAssignOperatorClass: {
571 const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
572 R1 = CAO->getLHS()->getSourceRange();
573 R2 = CAO->getRHS()->getSourceRange();
574 return CAO->getOperatorLoc();
575 }
576 case Expr::BinaryConditionalOperatorClass:
577 case Expr::ConditionalOperatorClass: {
579 cast<AbstractConditionalOperator>(S);
580 return CO->getQuestionLoc();
581 }
582 case Expr::MemberExprClass: {
583 const MemberExpr *ME = cast<MemberExpr>(S);
584 R1 = ME->getSourceRange();
585 return ME->getMemberLoc();
586 }
587 case Expr::ArraySubscriptExprClass: {
588 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
589 R1 = ASE->getLHS()->getSourceRange();
590 R2 = ASE->getRHS()->getSourceRange();
591 return ASE->getRBracketLoc();
592 }
593 case Expr::CStyleCastExprClass: {
594 const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
595 R1 = CSC->getSubExpr()->getSourceRange();
596 return CSC->getLParenLoc();
597 }
598 case Expr::CXXFunctionalCastExprClass: {
599 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
600 R1 = CE->getSubExpr()->getSourceRange();
601 return CE->getBeginLoc();
602 }
603 case Stmt::CXXTryStmtClass: {
604 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
605 }
606 case Expr::ObjCBridgedCastExprClass: {
607 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
608 R1 = CSC->getSubExpr()->getSourceRange();
609 return CSC->getLParenLoc();
610 }
611 default: ;
612 }
613 R1 = S->getSourceRange();
614 return S->getBeginLoc();
615}
616
617void DeadCodeScan::reportDeadCode(const CFGBlock *B,
618 const Stmt *S,
620 // Classify the unreachable code found, or suppress it in some cases.
622
623 if (isa<BreakStmt>(S)) {
625 } else if (isTrivialDoWhile(B, S) || isBuiltinUnreachable(S) ||
626 isBuiltinAssumeFalse(B, S, C)) {
627 return;
628 }
629 else if (isDeadReturn(B, S)) {
631 }
632
633 const auto *AS = dyn_cast<AttributedStmt>(S);
634 bool HasFallThroughAttr =
635 AS && hasSpecificAttr<FallThroughAttr>(AS->getAttrs());
636
637 SourceRange SilenceableCondVal;
638
639 if (UK == reachable_code::UK_Other) {
640 // Check if the dead code is part of the "loop target" of
641 // a for/for-range loop. This is the block that contains
642 // the increment code.
643 if (const Stmt *LoopTarget = B->getLoopTarget()) {
644 SourceLocation Loc = LoopTarget->getBeginLoc();
645 SourceRange R1(Loc, Loc), R2;
646
647 if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
648 const Expr *Inc = FS->getInc();
649 Loc = Inc->getBeginLoc();
650 R2 = Inc->getSourceRange();
651 }
652
654 SourceRange(), SourceRange(Loc, Loc), R2,
655 HasFallThroughAttr);
656 return;
657 }
658
659 // Check if the dead block has a predecessor whose branch has
660 // a configuration value that *could* be modified to
661 // silence the warning.
663 if (PI != B->pred_end()) {
664 if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
665 const Stmt *TermCond =
666 PredBlock->getTerminatorCondition(/* strip parens */ false);
667 isConfigurationValue(TermCond, PP, &SilenceableCondVal);
668 }
669 }
670 }
671
672 SourceRange R1, R2;
673 SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
674 CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2, HasFallThroughAttr);
675}
676
677//===----------------------------------------------------------------------===//
678// Reachability APIs.
679//===----------------------------------------------------------------------===//
680
681namespace clang { namespace reachable_code {
682
683void Callback::anchor() { }
684
685unsigned ScanReachableFromBlock(const CFGBlock *Start,
686 llvm::BitVector &Reachable) {
687 return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
688}
689
691 Callback &CB) {
692
693 CFG *cfg = AC.getCFG();
694 if (!cfg)
695 return;
696
697 // Scan for reachable blocks from the entrance of the CFG.
698 // If there are no unreachable blocks, we're done.
699 llvm::BitVector reachable(cfg->getNumBlockIDs());
700 unsigned numReachable =
701 scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
702 if (numReachable == cfg->getNumBlockIDs())
703 return;
704
705 // If there aren't explicit EH edges, we should include the 'try' dispatch
706 // blocks as roots.
707 if (!AC.getCFGBuildOptions().AddEHEdges) {
708 for (const CFGBlock *B : cfg->try_blocks())
709 numReachable += scanMaybeReachableFromBlock(B, PP, reachable);
710 if (numReachable == cfg->getNumBlockIDs())
711 return;
712 }
713
714 // There are some unreachable blocks. We need to find the root blocks that
715 // contain code that should be considered unreachable.
716 for (const CFGBlock *block : *cfg) {
717 // A block may have been marked reachable during this loop.
718 if (reachable[block->getBlockID()])
719 continue;
720
721 DeadCodeScan DS(reachable, PP, AC.getASTContext());
722 numReachable += DS.scanBackwards(block, CB);
723
724 if (numReachable == cfg->getNumBlockIDs())
725 return;
726 }
727}
728
729}} // end namespace clang::reachable_code
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
#define SM(sm)
Definition: Cuda.cpp:80
Defines enum values for all the target-independent builtin functions.
Defines the clang::Expr interface and subclasses for C++ expressions.
const CFGBlock * Block
Definition: HTMLLogger.cpp:150
llvm::DenseSet< const void * > Visited
Definition: HTMLLogger.cpp:143
Defines the clang::Preprocessor interface.
static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM)
static bool isEnumConstant(const Expr *Ex)
static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B, Preprocessor &PP)
Returns true if we should always explore all successors of a block.
static int SrcCmp(const std::pair< const CFGBlock *, const Stmt * > *p1, const std::pair< const CFGBlock *, const Stmt * > *p2)
static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S)
static bool isExpandedFromConfigurationMacro(const Stmt *S, Preprocessor &PP, bool IgnoreYES_NO=false)
Returns true if the statement is expanded from a configuration macro.
static bool isValidDeadStmt(const Stmt *S)
static unsigned scanFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable, Preprocessor *PP, bool IncludeSometimesUnreachableEdges)
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP)
static bool isBuiltinUnreachable(const Stmt *S)
static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S, ASTContext &C)
static bool isDeadReturn(const CFGBlock *B, const Stmt *S)
static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start, Preprocessor &PP, llvm::BitVector &Reachable)
static SourceLocation GetUnreachableLoc(const Stmt *S, SourceRange &R1, SourceRange &R2)
static bool isTrivialExpression(const Expr *Ex)
Defines the SourceManager interface.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:182
AbstractConditionalOperator - An abstract base class for ConditionalOperator and BinaryConditionalOpe...
Definition: Expr.h:4135
SourceLocation getQuestionLoc() const
Definition: Expr.h:4162
AnalysisDeclContext contains the context data for the function, method or block under analysis.
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
Definition: Expr.h:2676
SourceLocation getRBracketLoc() const
Definition: Expr.h:2724
Expr * getLHS()
An array access can be written A[4] or 4[A] (both are equivalent).
Definition: Expr.h:2705
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3834
static bool isLogicalOp(Opcode Opc)
Definition: Expr.h:3966
Expr * getLHS() const
Definition: Expr.h:3883
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3933
SourceLocation getOperatorLoc() const
Definition: Expr.h:3875
Expr * getRHS() const
Definition: Expr.h:3885
Represents a single basic block in a source-level CFG.
Definition: CFG.h:604
pred_iterator pred_end()
Definition: CFG.h:966
succ_iterator succ_end()
Definition: CFG.h:984
ElementList::const_iterator const_iterator
Definition: CFG.h:894
CFGElement back() const
Definition: CFG.h:901
iterator begin()
Definition: CFG.h:903
bool empty() const
Definition: CFG.h:946
CFGTerminator getTerminator() const
Definition: CFG.h:1076
succ_iterator succ_begin()
Definition: CFG.h:983
Stmt * getTerminatorStmt()
Definition: CFG.h:1078
const Stmt * getLoopTarget() const
Definition: CFG.h:1095
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:952
pred_iterator pred_begin()
Definition: CFG.h:965
iterator end()
Definition: CFG.h:904
unsigned getBlockID() const
Definition: CFG.h:1102
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:6266
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:959
Represents a top-level expression in a basic block.
Definition: CFG.h:55
std::optional< T > getAs() const
Convert to the specified CFGElement type, returning std::nullopt if this CFGElement is not of the des...
Definition: CFG.h:109
Represents CFGBlock terminator statement.
Definition: CFG.h:531
Stmt * getStmt()
Definition: CFG.h:563
bool isStmtBranch() const
Definition: CFG.h:567
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1211
try_block_range try_blocks() const
Definition: CFG.h:1336
CFGBlock & getEntry()
Definition: CFG.h:1317
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1397
CStyleCastExpr - An explicit cast in C (C99 6.5.4) or a C-style cast in C++ (C++ [expr....
Definition: Expr.h:3765
SourceLocation getLParenLoc() const
Definition: Expr.h:3797
Represents an explicit C++ type conversion that uses "functional" notation (C++ [expr....
Definition: ExprCXX.h:1800
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: ExprCXX.cpp:877
Expr * getSubExpr()
Definition: Expr.h:3552
CompoundAssignOperator - For compound assignments (e.g.
Definition: Expr.h:4082
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1242
ValueDecl * getDecl()
Definition: Expr.h:1310
DoStmt - This represents a 'do/while' stmt.
Definition: Stmt.h:2546
An instance of this object exists for each enum constant that is defined.
Definition: Decl.h:3197
This represents one expression.
Definition: Expr.h:110
Expr * IgnoreParenCasts() LLVM_READONLY
Skip past any parentheses and casts which might surround this expression until reaching a fixed point...
Definition: Expr.cpp:3077
Expr * IgnoreCasts() LLVM_READONLY
Skip past any casts which might surround this expression until reaching a fixed point.
Definition: Expr.cpp:3056
ForStmt - This represents a 'for (init;cond;inc)' stmt.
Definition: Stmt.h:2602
Represents a function declaration or definition.
Definition: Decl.h:1919
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:3195
SourceLocation getMemberLoc() const
getMemberLoc - Return the location of the "member", in X->F, it is the location of 'F'.
Definition: Expr.h:3380
An Objective-C "bridged" cast expression, which casts between Objective-C pointers and C pointers,...
Definition: ExprObjC.h:1626
SourceLocation getLParenLoc() const
Definition: ExprObjC.h:1648
ParenExpr - This represents a parethesized expression, e.g.
Definition: Expr.h:2142
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:136
Engages in a tight little dance with the lexer to efficiently preprocess tokens.
Definition: Preprocessor.h:128
SourceManager & getSourceManager() const
StringRef getImmediateMacroName(SourceLocation Loc)
Retrieve the name of the immediate macro expansion.
const LangOptions & getLangOpts() const
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Definition: Stmt.h:2840
Encodes a location in the source.
This class handles loading and caching of source files into memory.
A trivial tuple used to represent a source range.
Stmt - This represents one statement.
Definition: Stmt.h:72
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:325
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2195
SourceLocation getOperatorLoc() const
getOperatorLoc - Return the location of the operator.
Definition: Expr.h:2244
Expr * getSubExpr() const
Definition: Expr.h:2240
Opcode getOpcode() const
Definition: Expr.h:2235
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:703
Represents a variable declaration or definition.
Definition: Decl.h:915
virtual void HandleUnreachable(UnreachableKind UK, SourceLocation L, SourceRange ConditionVal, SourceRange R1, SourceRange R2, bool HasFallThroughAttr)=0
bool Inc(InterpState &S, CodePtr OpPC)
1) Pops a pointer from the stack 2) Load the value from the pointer 3) Writes the value increased by ...
Definition: Interp.h:563
void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP, Callback &CB)
unsigned ScanReachableFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable)
ScanReachableFromBlock - Mark all blocks reachable from Start.
UnreachableKind
Classifications of unreachable code.
Definition: ReachableCode.h:40
@ C
Languages that the frontend can parse and compile.