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