contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp

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