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
29using namespace clang;
30
31//===----------------------------------------------------------------------===//
32// Core Reachability Analysis routines.
33//===----------------------------------------------------------------------===//
34
35static 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
42static 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
50static 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
62static 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
70static 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
85static 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
137static 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.
148static 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
178static 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.
187static 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
272static 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.
294static 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
315static 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
381static 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
391namespace {
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
424void 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
432bool 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
455static 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
463const 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
481static 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
490unsigned 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
551static 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
616void 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
675namespace clang { namespace reachable_code {
676
677void Callback::anchor() { }
678
679unsigned ScanReachableFromBlock(const CFGBlock *Start,
680                                llvm::BitVector &Reachable) {
681  return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
682}
683
684void 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
724