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