773 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements a flow-sensitive, path-insensitive analysis of10// 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/DynamicRecursiveASTVisitor.h"17#include "clang/AST/Expr.h"18#include "clang/AST/ExprCXX.h"19#include "clang/AST/ExprObjC.h"20#include "clang/AST/ParentMap.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 <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) ||48 isEnumConstant(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 the53 // 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 else75 // (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 if88 // 'S' is a substatement. The 'return' may not be the last element in the89 // 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 of103 // 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 statement111 // 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 to115 // look into the next block for the return statement.116 // We look into the false branch, as we know the true branch only contains117 // 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 control122 // 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 incoming126 // control flow - if the return statement is in that block, it might127 // 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 138static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM) {139 assert(Loc.isMacroID());140 SourceLocation Last;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.149static bool isExpandedFromConfigurationMacro(const Stmt *S,150 Preprocessor &PP,151 bool IgnoreYES_NO = false) {152 // FIXME: This is not very precise. Here we just check to see if the153 // value comes from a macro, but we can do much better. This is likely154 // to be over conservative. This logic is factored into a separate function155 // so that we can refine it later.156 SourceLocation L = S->getBeginLoc();157 if (L.isMacroID()) {158 SourceManager &SM = PP.getSourceManager();159 if (IgnoreYES_NO) {160 // The Objective-C constant 'YES' and 'NO'161 // are defined as macros. Do not treat them162 // as configuration values.163 SourceLocation TopL = getTopMostMacro(L, SM);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.169 SourceLocation TopL = getTopMostMacro(L, SM);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-time184/// to conditionally always execute some branch. Such guards are for185/// "sometimes unreachable" code. Such code is usually not interesting186/// to report as unreachable, and may mask truly unreachable code within187/// 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 configuration242 // values if they are used in a logical or comparison operator243 // (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 range260 // was set directly by the child expression.261 if (SilenceableCondValNotSet &&262 SilenceableCondVal->getBegin().isValid() &&263 *SilenceableCondVal ==264 UO->getSubExpr()->IgnoreCasts()->getSourceRange())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. Note278 // that we only will get here if Sema evaluated this279 // condition to a constant expression, which means the global280 // had to be declared in a way to be a truly constant value.281 // We could generalize this to local variables, but it isn't282 // clear if those truly represent configuration values that283 // gate unreachable code.284 if (!VD->hasLocalStorage())285 return true;286 287 // As a heuristic, locals that have been marked 'const' explicitly288 // 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.295static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B,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 warnings305 // since the point of these statements is to determine branches at compile306 // 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 queue323 SmallVector<const CFGBlock*, 32> WL;324 325 // The entry block may have already been marked reachable326 // 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" code342 // 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 348 for (CFGBlock::const_succ_iterator I = item->succ_begin(),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 =359 shouldTreatSuccessorsAsReachable(item, *PP);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;396 SmallVector<const CFGBlock *, 10> WorkList;397 Preprocessor &PP;398 ASTContext &C;399 400 typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>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,413 clang::reachable_code::Callback &CB);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,421 clang::reachable_code::Callback &CB);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 436 for (CFGBlock::const_pred_iterator I = Block->pred_begin(),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 456// Check if the given `DeadStmt` is a coroutine statement and is a substmt of457// the coroutine statement. `Block` is the CFGBlock containing the `DeadStmt`.458static bool isInCoroutineStmt(const Stmt *DeadStmt, const CFGBlock *Block) {459 // The coroutine statement, co_return, co_await, or co_yield.460 const Stmt *CoroStmt = nullptr;461 // Find the first coroutine statement after the DeadStmt in the block.462 bool AfterDeadStmt = false;463 for (const CFGElement &Elem : *Block)464 if (std::optional<CFGStmt> CS = Elem.getAs<CFGStmt>()) {465 const Stmt *S = CS->getStmt();466 if (S == DeadStmt)467 AfterDeadStmt = true;468 if (AfterDeadStmt &&469 // For simplicity, we only check simple coroutine statements.470 (llvm::isa<CoreturnStmt>(S) || llvm::isa<CoroutineSuspendExpr>(S))) {471 CoroStmt = S;472 break;473 }474 }475 if (!CoroStmt)476 return false;477 struct Checker : DynamicRecursiveASTVisitor {478 const Stmt *DeadStmt;479 bool CoroutineSubStmt = false;480 Checker(const Stmt *S) : DeadStmt(S) {481 // Statements captured in the CFG can be implicit.482 ShouldVisitImplicitCode = true;483 }484 485 bool VisitStmt(Stmt *S) override {486 if (S == DeadStmt)487 CoroutineSubStmt = true;488 return true;489 }490 };491 Checker checker(DeadStmt);492 checker.TraverseStmt(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>(S))500 return BO->getOpcode() != BO_Comma;501 // Coroutine statements are never considered dead statements, because removing502 // them may change the function semantic if it is the only coroutine statement503 // of the coroutine.504 return !isInCoroutineStmt(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(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 after544 // 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(predBlock);557 }558 continue;559 }560 561 // Specially handle macro-expanded code.562 if (S->getBeginLoc().isMacroID()) {563 count += scanMaybeReachableFromBlock(Block, PP, Reachable);564 continue;565 }566 567 if (isDeadCodeRoot(Block)) {568 reportDeadCode(Block, S, CB);569 count += scanMaybeReachableFromBlock(Block, PP, Reachable);570 }571 else {572 // Record this statement as the possibly best location in a573 // strongly-connected component of dead code for emitting a574 // warning.575 DeferredLocs.push_back(std::make_pair(Block, S));576 }577 }578 579 // If we didn't find a dead root, then report the dead code with the580 // earliest location.581 if (!DeferredLocs.empty()) {582 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);583 for (const auto &I : DeferredLocs) {584 const CFGBlock *Block = I.first;585 if (Reachable[Block->getBlockID()])586 continue;587 reportDeadCode(Block, I.second, CB);588 count += scanMaybeReachableFromBlock(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>(S))601 S = Ex->IgnoreParenImpCasts();602 603 switch (S->getStmtClass()) {604 case Expr::BinaryOperatorClass: {605 const BinaryOperator *BO = cast<BinaryOperator>(S);606 return BO->getOperatorLoc();607 }608 case Expr::UnaryOperatorClass: {609 const UnaryOperator *UO = cast<UnaryOperator>(S);610 R1 = UO->getSubExpr()->getSourceRange();611 return UO->getOperatorLoc();612 }613 case Expr::CompoundAssignOperatorClass: {614 const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(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>(S);623 return CO->getQuestionLoc();624 }625 case Expr::MemberExprClass: {626 const MemberExpr *ME = cast<MemberExpr>(S);627 R1 = ME->getSourceRange();628 return ME->getMemberLoc();629 }630 case Expr::ArraySubscriptExprClass: {631 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(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>(S);638 R1 = CSC->getSubExpr()->getSourceRange();639 return CSC->getLParenLoc();640 }641 case Expr::CXXFunctionalCastExprClass: {642 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);643 R1 = CE->getSubExpr()->getSourceRange();644 return CE->getBeginLoc();645 }646 case Stmt::CXXTryStmtClass: {647 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();648 }649 case Expr::ObjCBridgedCastExprClass: {650 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(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>(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>(S);677 bool HasFallThroughAttr =678 AS && hasSpecificAttr<FallThroughAttr>(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" of684 // a for/for-range loop. This is the block that contains685 // 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>(LoopTarget)) {691 const Expr *Inc = FS->getInc();692 Loc = Inc->getBeginLoc();693 R2 = Inc->getSourceRange();694 }695 696 CB.HandleUnreachable(reachable_code::UK_Loop_Increment, Loc,697 SourceRange(), SourceRange(Loc, Loc), R2,698 HasFallThroughAttr);699 return;700 }701 702 // Check if the dead block has a predecessor whose branch has703 // a configuration value that *could* be modified to704 // 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 */ false);710 isConfigurationValue(TermCond, PP, &SilenceableCondVal);711 }712 }713 }714 715 SourceRange R1, R2;716 SourceLocation Loc = GetUnreachableLoc(S, R1, R2);717 CB.HandleUnreachable(UK, Loc, 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* */ nullptr, 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(&cfg->getEntry(), PP, reachable);745 if (numReachable == cfg->getNumBlockIDs())746 return;747 748 // If there aren't explicit EH edges, we should include the 'try' dispatch749 // blocks as roots.750 if (!AC.getCFGBuildOptions().AddEHEdges) {751 for (const CFGBlock *B : cfg->try_blocks())752 numReachable += scanMaybeReachableFromBlock(B, PP, reachable);753 if (numReachable == cfg->getNumBlockIDs())754 return;755 }756 757 // There are some unreachable blocks. We need to find the root blocks that758 // 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(block, CB);766 767 if (numReachable == cfg->getNumBlockIDs())768 return;769 }770}771 772}} // end namespace clang::reachable_code773