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