clang/lib/Analysis/ReachableCode.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-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/StmtCXX.h"
  21 #include "clang/Analysis/AnalysisDeclContext.h"
  22 #include "clang/Analysis/CFG.h"
  23 #include "clang/Basic/Builtins.h"
  24 #include "clang/Basic/SourceManager.h"
  25 #include "clang/Lex/Preprocessor.h"
  26 #include "llvm/ADT/BitVector.h"
  27 #include "llvm/ADT/SmallVector.h"
  28 #include <optional>
  29
  30 using namespace clang;
  31
  32 //===----------------------------------------------------------------------===//
  33 // Core Reachability Analysis routines.
  34 //===----------------------------------------------------------------------===//
  35
  36 static 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
  43 static 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
  51 static 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
  63 static 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
  71 static 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
  86 static 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
 138 static 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.
 149 static 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 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()) {
 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 them
 162       // 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
 179 static 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.
 188 static 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 ==
 264               UO->getSubExpr()->IgnoreCasts()->getSourceRange())
 265         *SilenceableCondVal = UO->getSourceRange();
 266       return IsSubExprConfigValue;
 267     }
 268     default:
 269       return false;
 270   }
 271 }
 272
 273 static 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.
 295 static 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 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
 316 static unsigned scanFromBlock(const CFGBlock *Start,
 317                               llvm::BitVector &Reachable,
 318                               Preprocessor *PP,
 319                               bool IncludeSometimesUnreachableEdges) {
 320   unsigned count = 0;
 321
 322   // Prep work queue
 323   SmallVector<const CFGBlock*, 32> WL;
 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
 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
 382 static 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
 392 namespace {
 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
 425 void 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
 433 bool 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 static 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
 464 const 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
 472   CFGTerminator T = Block->getTerminator();
 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
 482 static 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
 491 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
 492                                      clang::reachable_code::Callback &CB) {
 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.
 510       for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
 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
 552 static SourceLocation GetUnreachableLoc(const Stmt *S,
 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: {
 578       const AbstractConditionalOperator *CO =
 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
 617 void DeadCodeScan::reportDeadCode(const CFGBlock *B,
 618                                   const Stmt *S,
 619                                   clang::reachable_code::Callback &CB) {
 620   // Classify the unreachable code found, or suppress it in some cases.
 621   reachable_code::UnreachableKind UK = reachable_code::UK_Other;
 622
 623   if (isa<BreakStmt>(S)) {
 624     UK = reachable_code::UK_Break;
 625   } else if (isTrivialDoWhile(B, S) || isBuiltinUnreachable(S) ||
 626              isBuiltinAssumeFalse(B, S, C)) {
 627     return;
 628   }
 629   else if (isDeadReturn(B, S)) {
 630     UK = reachable_code::UK_Return;
 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
 653       CB.HandleUnreachable(reachable_code::UK_Loop_Increment, Loc,
 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.
 662     CFGBlock::const_pred_iterator PI = B->pred_begin();
 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
 681 namespace clang { namespace reachable_code {
 682
 683 void Callback::anchor() { }
 684
 685 unsigned ScanReachableFromBlock(const CFGBlock *Start,
 686                                 llvm::BitVector &Reachable) {
 687   return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
 688 }
 689
 690 void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP,
 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