contrib/llvm-project/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/SourceManager.h"
  23 #include "clang/Lex/Preprocessor.h"
  24 #include "llvm/ADT/BitVector.h"
  25 #include "llvm/ADT/SmallVector.h"
  26
  27 using namespace clang;
  28
  29 //===----------------------------------------------------------------------===//
  30 // Core Reachability Analysis routines.
  31 //===----------------------------------------------------------------------===//
  32
  33 static bool isEnumConstant(const Expr *Ex) {
  34   const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex);
  35   if (!DR)
  36     return false;
  37   return isa<EnumConstantDecl>(DR->getDecl());
  38 }
  39
  40 static bool isTrivialExpression(const Expr *Ex) {
  41   Ex = Ex->IgnoreParenCasts();
  42   return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex) ||
  43          isa<CXXBoolLiteralExpr>(Ex) || isa<ObjCBoolLiteralExpr>(Ex) ||
  44          isa<CharacterLiteral>(Ex) ||
  45          isEnumConstant(Ex);
  46 }
  47
  48 static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) {
  49   // Check if the block ends with a do...while() and see if 'S' is the
  50   // condition.
  51   if (const Stmt *Term = B->getTerminatorStmt()) {
  52     if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
  53       const Expr *Cond = DS->getCond()->IgnoreParenCasts();
  54       return Cond == S && isTrivialExpression(Cond);
  55     }
  56   }
  57   return false;
  58 }
  59
  60 static bool isBuiltinUnreachable(const Stmt *S) {
  61   if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
  62     if (const auto *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl()))
  63       return FDecl->getIdentifier() &&
  64              FDecl->getBuiltinID() == Builtin::BI__builtin_unreachable;
  65   return false;
  66 }
  67
  68 static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S,
  69                                  ASTContext &C) {
  70   if (B->empty())  {
  71     // Happens if S is B's terminator and B contains nothing else
  72     // (e.g. a CFGBlock containing only a goto).
  73     return false;
  74   }
  75   if (Optional<CFGStmt> CS = B->back().getAs<CFGStmt>()) {
  76     if (const auto *CE = dyn_cast<CallExpr>(CS->getStmt())) {
  77       return CE->getCallee()->IgnoreCasts() == S && CE->isBuiltinAssumeFalse(C);
  78     }
  79   }
  80   return false;
  81 }
  82
  83 static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
  84   // Look to see if the current control flow ends with a 'return', and see if
  85   // 'S' is a substatement. The 'return' may not be the last element in the
  86   // block, or may be in a subsequent block because of destructors.
  87   const CFGBlock *Current = B;
  88   while (true) {
  89     for (CFGBlock::const_reverse_iterator I = Current->rbegin(),
  90                                           E = Current->rend();
  91          I != E; ++I) {
  92       if (Optional<CFGStmt> CS = I->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   while (Loc.isMacroID()) {
 141     Last = Loc;
 142     Loc = SM.getImmediateMacroCallerLoc(Loc);
 143   }
 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       LLVM_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 || isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO);
 230       }
 231       return false;
 232     }
 233     case Stmt::MemberExprClass:
 234       return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP);
 235     case Stmt::UnaryExprOrTypeTraitExprClass:
 236       return true;
 237     case Stmt::BinaryOperatorClass: {
 238       const BinaryOperator *B = cast<BinaryOperator>(S);
 239       // Only include raw integers (not enums) as configuration
 240       // values if they are used in a logical or comparison operator
 241       // (not arithmetic).
 242       IncludeIntegers &= (B->isLogicalOp() || B->isComparisonOp());
 243       return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal,
 244                                   IncludeIntegers) ||
 245              isConfigurationValue(B->getRHS(), PP, SilenceableCondVal,
 246                                   IncludeIntegers);
 247     }
 248     case Stmt::UnaryOperatorClass: {
 249       const UnaryOperator *UO = cast<UnaryOperator>(S);
 250       if (UO->getOpcode() != UO_LNot)
 251         return false;
 252       bool SilenceableCondValNotSet =
 253           SilenceableCondVal && SilenceableCondVal->getBegin().isInvalid();
 254       bool IsSubExprConfigValue =
 255           isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal,
 256                                IncludeIntegers, WrappedInParens);
 257       // Update the silenceable condition value source range only if the range
 258       // was set directly by the child expression.
 259       if (SilenceableCondValNotSet &&
 260           SilenceableCondVal->getBegin().isValid() &&
 261           *SilenceableCondVal ==
 262               UO->getSubExpr()->IgnoreCasts()->getSourceRange())
 263         *SilenceableCondVal = UO->getSourceRange();
 264       return IsSubExprConfigValue;
 265     }
 266     default:
 267       return false;
 268   }
 269 }
 270
 271 static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) {
 272   if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D))
 273     return isConfigurationValue(ED->getInitExpr(), PP);
 274   if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
 275     // As a heuristic, treat globals as configuration values.  Note
 276     // that we only will get here if Sema evaluated this
 277     // condition to a constant expression, which means the global
 278     // had to be declared in a way to be a truly constant value.
 279     // We could generalize this to local variables, but it isn't
 280     // clear if those truly represent configuration values that
 281     // gate unreachable code.
 282     if (!VD->hasLocalStorage())
 283       return true;
 284
 285     // As a heuristic, locals that have been marked 'const' explicitly
 286     // can be treated as configuration values as well.
 287     return VD->getType().isLocalConstQualified();
 288   }
 289   return false;
 290 }
 291
 292 /// Returns true if we should always explore all successors of a block.
 293 static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B,
 294                                              Preprocessor &PP) {
 295   if (const Stmt *Term = B->getTerminatorStmt()) {
 296     if (isa<SwitchStmt>(Term))
 297       return true;
 298     // Specially handle '||' and '&&'.
 299     if (isa<BinaryOperator>(Term)) {
 300       return isConfigurationValue(Term, PP);
 301     }
 302   }
 303
 304   const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
 305   return isConfigurationValue(Cond, PP);
 306 }
 307
 308 static unsigned scanFromBlock(const CFGBlock *Start,
 309                               llvm::BitVector &Reachable,
 310                               Preprocessor *PP,
 311                               bool IncludeSometimesUnreachableEdges) {
 312   unsigned count = 0;
 313
 314   // Prep work queue
 315   SmallVector<const CFGBlock*, 32> WL;
 316
 317   // The entry block may have already been marked reachable
 318   // by the caller.
 319   if (!Reachable[Start->getBlockID()]) {
 320     ++count;
 321     Reachable[Start->getBlockID()] = true;
 322   }
 323
 324   WL.push_back(Start);
 325
 326   // Find the reachable blocks from 'Start'.
 327   while (!WL.empty()) {
 328     const CFGBlock *item = WL.pop_back_val();
 329
 330     // There are cases where we want to treat all successors as reachable.
 331     // The idea is that some "sometimes unreachable" code is not interesting,
 332     // and that we should forge ahead and explore those branches anyway.
 333     // This allows us to potentially uncover some "always unreachable" code
 334     // within the "sometimes unreachable" code.
 335     // Look at the successors and mark then reachable.
 336     Optional<bool> TreatAllSuccessorsAsReachable;
 337     if (!IncludeSometimesUnreachableEdges)
 338       TreatAllSuccessorsAsReachable = false;
 339
 340     for (CFGBlock::const_succ_iterator I = item->succ_begin(),
 341          E = item->succ_end(); I != E; ++I) {
 342       const CFGBlock *B = *I;
 343       if (!B) do {
 344         const CFGBlock *UB = I->getPossiblyUnreachableBlock();
 345         if (!UB)
 346           break;
 347
 348         if (!TreatAllSuccessorsAsReachable.hasValue()) {
 349           assert(PP);
 350           TreatAllSuccessorsAsReachable =
 351             shouldTreatSuccessorsAsReachable(item, *PP);
 352         }
 353
 354         if (TreatAllSuccessorsAsReachable.getValue()) {
 355           B = UB;
 356           break;
 357         }
 358       }
 359       while (false);
 360
 361       if (B) {
 362         unsigned blockID = B->getBlockID();
 363         if (!Reachable[blockID]) {
 364           Reachable.set(blockID);
 365           WL.push_back(B);
 366           ++count;
 367         }
 368       }
 369     }
 370   }
 371   return count;
 372 }
 373
 374 static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
 375                                             Preprocessor &PP,
 376                                             llvm::BitVector &Reachable) {
 377   return scanFromBlock(Start, Reachable, &PP, true);
 378 }
 379
 380 //===----------------------------------------------------------------------===//
 381 // Dead Code Scanner.
 382 //===----------------------------------------------------------------------===//
 383
 384 namespace {
 385   class DeadCodeScan {
 386     llvm::BitVector Visited;
 387     llvm::BitVector &Reachable;
 388     SmallVector<const CFGBlock *, 10> WorkList;
 389     Preprocessor &PP;
 390     ASTContext &C;
 391
 392     typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
 393     DeferredLocsTy;
 394
 395     DeferredLocsTy DeferredLocs;
 396
 397   public:
 398     DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP, ASTContext &C)
 399     : Visited(reachable.size()),
 400       Reachable(reachable),
 401       PP(PP), C(C) {}
 402
 403     void enqueue(const CFGBlock *block);
 404     unsigned scanBackwards(const CFGBlock *Start,
 405     clang::reachable_code::Callback &CB);
 406
 407     bool isDeadCodeRoot(const CFGBlock *Block);
 408
 409     const Stmt *findDeadCode(const CFGBlock *Block);
 410
 411     void reportDeadCode(const CFGBlock *B,
 412                         const Stmt *S,
 413                         clang::reachable_code::Callback &CB);
 414   };
 415 }
 416
 417 void DeadCodeScan::enqueue(const CFGBlock *block) {
 418   unsigned blockID = block->getBlockID();
 419   if (Reachable[blockID] || Visited[blockID])
 420     return;
 421   Visited[blockID] = true;
 422   WorkList.push_back(block);
 423 }
 424
 425 bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
 426   bool isDeadRoot = true;
 427
 428   for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
 429        E = Block->pred_end(); I != E; ++I) {
 430     if (const CFGBlock *PredBlock = *I) {
 431       unsigned blockID = PredBlock->getBlockID();
 432       if (Visited[blockID]) {
 433         isDeadRoot = false;
 434         continue;
 435       }
 436       if (!Reachable[blockID]) {
 437         isDeadRoot = false;
 438         Visited[blockID] = true;
 439         WorkList.push_back(PredBlock);
 440         continue;
 441       }
 442     }
 443   }
 444
 445   return isDeadRoot;
 446 }
 447
 448 static bool isValidDeadStmt(const Stmt *S) {
 449   if (S->getBeginLoc().isInvalid())
 450     return false;
 451   if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
 452     return BO->getOpcode() != BO_Comma;
 453   return true;
 454 }
 455
 456 const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
 457   for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
 458     if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
 459       const Stmt *S = CS->getStmt();
 460       if (isValidDeadStmt(S))
 461         return S;
 462     }
 463
 464   CFGTerminator T = Block->getTerminator();
 465   if (T.isStmtBranch()) {
 466     const Stmt *S = T.getStmt();
 467     if (S && isValidDeadStmt(S))
 468       return S;
 469   }
 470
 471   return nullptr;
 472 }
 473
 474 static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
 475                   const std::pair<const CFGBlock *, const Stmt *> *p2) {
 476   if (p1->second->getBeginLoc() < p2->second->getBeginLoc())
 477     return -1;
 478   if (p2->second->getBeginLoc() < p1->second->getBeginLoc())
 479     return 1;
 480   return 0;
 481 }
 482
 483 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
 484                                      clang::reachable_code::Callback &CB) {
 485
 486   unsigned count = 0;
 487   enqueue(Start);
 488
 489   while (!WorkList.empty()) {
 490     const CFGBlock *Block = WorkList.pop_back_val();
 491
 492     // It is possible that this block has been marked reachable after
 493     // it was enqueued.
 494     if (Reachable[Block->getBlockID()])
 495       continue;
 496
 497     // Look for any dead code within the block.
 498     const Stmt *S = findDeadCode(Block);
 499
 500     if (!S) {
 501       // No dead code.  Possibly an empty block.  Look at dead predecessors.
 502       for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
 503            E = Block->pred_end(); I != E; ++I) {
 504         if (const CFGBlock *predBlock = *I)
 505           enqueue(predBlock);
 506       }
 507       continue;
 508     }
 509
 510     // Specially handle macro-expanded code.
 511     if (S->getBeginLoc().isMacroID()) {
 512       count += scanMaybeReachableFromBlock(Block, PP, Reachable);
 513       continue;
 514     }
 515
 516     if (isDeadCodeRoot(Block)) {
 517       reportDeadCode(Block, S, CB);
 518       count += scanMaybeReachableFromBlock(Block, PP, Reachable);
 519     }
 520     else {
 521       // Record this statement as the possibly best location in a
 522       // strongly-connected component of dead code for emitting a
 523       // warning.
 524       DeferredLocs.push_back(std::make_pair(Block, S));
 525     }
 526   }
 527
 528   // If we didn't find a dead root, then report the dead code with the
 529   // earliest location.
 530   if (!DeferredLocs.empty()) {
 531     llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
 532     for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
 533          E = DeferredLocs.end(); I != E; ++I) {
 534       const CFGBlock *Block = I->first;
 535       if (Reachable[Block->getBlockID()])
 536         continue;
 537       reportDeadCode(Block, I->second, CB);
 538       count += scanMaybeReachableFromBlock(Block, PP, Reachable);
 539     }
 540   }
 541
 542   return count;
 543 }
 544
 545 static SourceLocation GetUnreachableLoc(const Stmt *S,
 546                                         SourceRange &R1,
 547                                         SourceRange &R2) {
 548   R1 = R2 = SourceRange();
 549
 550   if (const Expr *Ex = dyn_cast<Expr>(S))
 551     S = Ex->IgnoreParenImpCasts();
 552
 553   switch (S->getStmtClass()) {
 554     case Expr::BinaryOperatorClass: {
 555       const BinaryOperator *BO = cast<BinaryOperator>(S);
 556       return BO->getOperatorLoc();
 557     }
 558     case Expr::UnaryOperatorClass: {
 559       const UnaryOperator *UO = cast<UnaryOperator>(S);
 560       R1 = UO->getSubExpr()->getSourceRange();
 561       return UO->getOperatorLoc();
 562     }
 563     case Expr::CompoundAssignOperatorClass: {
 564       const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
 565       R1 = CAO->getLHS()->getSourceRange();
 566       R2 = CAO->getRHS()->getSourceRange();
 567       return CAO->getOperatorLoc();
 568     }
 569     case Expr::BinaryConditionalOperatorClass:
 570     case Expr::ConditionalOperatorClass: {
 571       const AbstractConditionalOperator *CO =
 572       cast<AbstractConditionalOperator>(S);
 573       return CO->getQuestionLoc();
 574     }
 575     case Expr::MemberExprClass: {
 576       const MemberExpr *ME = cast<MemberExpr>(S);
 577       R1 = ME->getSourceRange();
 578       return ME->getMemberLoc();
 579     }
 580     case Expr::ArraySubscriptExprClass: {
 581       const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
 582       R1 = ASE->getLHS()->getSourceRange();
 583       R2 = ASE->getRHS()->getSourceRange();
 584       return ASE->getRBracketLoc();
 585     }
 586     case Expr::CStyleCastExprClass: {
 587       const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
 588       R1 = CSC->getSubExpr()->getSourceRange();
 589       return CSC->getLParenLoc();
 590     }
 591     case Expr::CXXFunctionalCastExprClass: {
 592       const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
 593       R1 = CE->getSubExpr()->getSourceRange();
 594       return CE->getBeginLoc();
 595     }
 596     case Stmt::CXXTryStmtClass: {
 597       return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
 598     }
 599     case Expr::ObjCBridgedCastExprClass: {
 600       const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
 601       R1 = CSC->getSubExpr()->getSourceRange();
 602       return CSC->getLParenLoc();
 603     }
 604     default: ;
 605   }
 606   R1 = S->getSourceRange();
 607   return S->getBeginLoc();
 608 }
 609
 610 void DeadCodeScan::reportDeadCode(const CFGBlock *B,
 611                                   const Stmt *S,
 612                                   clang::reachable_code::Callback &CB) {
 613   // Classify the unreachable code found, or suppress it in some cases.
 614   reachable_code::UnreachableKind UK = reachable_code::UK_Other;
 615
 616   if (isa<BreakStmt>(S)) {
 617     UK = reachable_code::UK_Break;
 618   } else if (isTrivialDoWhile(B, S) || isBuiltinUnreachable(S) ||
 619              isBuiltinAssumeFalse(B, S, C)) {
 620     return;
 621   }
 622   else if (isDeadReturn(B, S)) {
 623     UK = reachable_code::UK_Return;
 624   }
 625
 626   SourceRange SilenceableCondVal;
 627
 628   if (UK == reachable_code::UK_Other) {
 629     // Check if the dead code is part of the "loop target" of
 630     // a for/for-range loop.  This is the block that contains
 631     // the increment code.
 632     if (const Stmt *LoopTarget = B->getLoopTarget()) {
 633       SourceLocation Loc = LoopTarget->getBeginLoc();
 634       SourceRange R1(Loc, Loc), R2;
 635
 636       if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
 637         const Expr *Inc = FS->getInc();
 638         Loc = Inc->getBeginLoc();
 639         R2 = Inc->getSourceRange();
 640       }
 641
 642       CB.HandleUnreachable(reachable_code::UK_Loop_Increment,
 643                            Loc, SourceRange(), SourceRange(Loc, Loc), R2);
 644       return;
 645     }
 646
 647     // Check if the dead block has a predecessor whose branch has
 648     // a configuration value that *could* be modified to
 649     // silence the warning.
 650     CFGBlock::const_pred_iterator PI = B->pred_begin();
 651     if (PI != B->pred_end()) {
 652       if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
 653         const Stmt *TermCond =
 654             PredBlock->getTerminatorCondition(/* strip parens */ false);
 655         isConfigurationValue(TermCond, PP, &SilenceableCondVal);
 656       }
 657     }
 658   }
 659
 660   SourceRange R1, R2;
 661   SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
 662   CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2);
 663 }
 664
 665 //===----------------------------------------------------------------------===//
 666 // Reachability APIs.
 667 //===----------------------------------------------------------------------===//
 668
 669 namespace clang { namespace reachable_code {
 670
 671 void Callback::anchor() { }
 672
 673 unsigned ScanReachableFromBlock(const CFGBlock *Start,
 674                                 llvm::BitVector &Reachable) {
 675   return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
 676 }
 677
 678 void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP,
 679                          Callback &CB) {
 680
 681   CFG *cfg = AC.getCFG();
 682   if (!cfg)
 683     return;
 684
 685   // Scan for reachable blocks from the entrance of the CFG.
 686   // If there are no unreachable blocks, we're done.
 687   llvm::BitVector reachable(cfg->getNumBlockIDs());
 688   unsigned numReachable =
 689     scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
 690   if (numReachable == cfg->getNumBlockIDs())
 691     return;
 692
 693   // If there aren't explicit EH edges, we should include the 'try' dispatch
 694   // blocks as roots.
 695   if (!AC.getCFGBuildOptions().AddEHEdges) {
 696     for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
 697          E = cfg->try_blocks_end() ; I != E; ++I) {
 698       numReachable += scanMaybeReachableFromBlock(*I, PP, reachable);
 699     }
 700     if (numReachable == cfg->getNumBlockIDs())
 701       return;
 702   }
 703
 704   // There are some unreachable blocks.  We need to find the root blocks that
 705   // contain code that should be considered unreachable.
 706   for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
 707     const CFGBlock *block = *I;
 708     // A block may have been marked reachable during this loop.
 709     if (reachable[block->getBlockID()])
 710       continue;
 711
 712     DeadCodeScan DS(reachable, PP, AC.getASTContext());
 713     numReachable += DS.scanBackwards(block, CB);
 714
 715     if (numReachable == cfg->getNumBlockIDs())
 716       return;
 717   }
 718 }
 719
 720 }} // end namespace clang::reachable_code