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