clang  6.0.0svn
ReachableCode.cpp
Go to the documentation of this file.
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 
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"
22 #include "clang/Analysis/CFG.h"
24 #include "clang/Lex/Preprocessor.h"
25 #include "llvm/ADT/BitVector.h"
26 #include "llvm/ADT/SmallVector.h"
27 
28 using namespace clang;
29 
30 //===----------------------------------------------------------------------===//
31 // Core Reachability Analysis routines.
32 //===----------------------------------------------------------------------===//
33 
34 static bool isEnumConstant(const Expr *Ex) {
35  const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex);
36  if (!DR)
37  return false;
38  return isa<EnumConstantDecl>(DR->getDecl());
39 }
40 
41 static bool isTrivialExpression(const Expr *Ex) {
42  Ex = Ex->IgnoreParenCasts();
43  return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex) ||
44  isa<CXXBoolLiteralExpr>(Ex) || isa<ObjCBoolLiteralExpr>(Ex) ||
45  isa<CharacterLiteral>(Ex) ||
46  isEnumConstant(Ex);
47 }
48 
49 static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) {
50  // Check if the block ends with a do...while() and see if 'S' is the
51  // condition.
52  if (const Stmt *Term = B->getTerminator()) {
53  if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
54  const Expr *Cond = DS->getCond()->IgnoreParenCasts();
55  return Cond == S && isTrivialExpression(Cond);
56  }
57  }
58  return false;
59 }
60 
61 static bool isBuiltinUnreachable(const Stmt *S) {
62  if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
63  if (const auto *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl()))
64  return FDecl->getIdentifier() &&
65  FDecl->getBuiltinID() == Builtin::BI__builtin_unreachable;
66  return false;
67 }
68 
69 static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
70  // Look to see if the current control flow ends with a 'return', and see if
71  // 'S' is a substatement. The 'return' may not be the last element in the
72  // block, or may be in a subsequent block because of destructors.
73  const CFGBlock *Current = B;
74  while (true) {
75  for (CFGBlock::const_reverse_iterator I = Current->rbegin(),
76  E = Current->rend();
77  I != E; ++I) {
78  if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
79  if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
80  if (RS == S)
81  return true;
82  if (const Expr *RE = RS->getRetValue()) {
83  RE = RE->IgnoreParenCasts();
84  if (RE == S)
85  return true;
86  ParentMap PM(const_cast<Expr *>(RE));
87  // If 'S' is in the ParentMap, it is a subexpression of
88  // the return statement.
89  return PM.getParent(S);
90  }
91  }
92  break;
93  }
94  }
95  // Note also that we are restricting the search for the return statement
96  // to stop at control-flow; only part of a return statement may be dead,
97  // without the whole return statement being dead.
98  if (Current->getTerminator().isTemporaryDtorsBranch()) {
99  // Temporary destructors have a predictable control flow, thus we want to
100  // look into the next block for the return statement.
101  // We look into the false branch, as we know the true branch only contains
102  // the call to the destructor.
103  assert(Current->succ_size() == 2);
104  Current = *(Current->succ_begin() + 1);
105  } else if (!Current->getTerminator() && Current->succ_size() == 1) {
106  // If there is only one successor, we're not dealing with outgoing control
107  // flow. Thus, look into the next block.
108  Current = *Current->succ_begin();
109  if (Current->pred_size() > 1) {
110  // If there is more than one predecessor, we're dealing with incoming
111  // control flow - if the return statement is in that block, it might
112  // well be reachable via a different control flow, thus it's not dead.
113  return false;
114  }
115  } else {
116  // We hit control flow or a dead end. Stop searching.
117  return false;
118  }
119  }
120  llvm_unreachable("Broke out of infinite loop.");
121 }
122 
124  assert(Loc.isMacroID());
126  while (Loc.isMacroID()) {
127  Last = Loc;
128  Loc = SM.getImmediateMacroCallerLoc(Loc);
129  }
130  return Last;
131 }
132 
133 /// Returns true if the statement is expanded from a configuration macro.
135  Preprocessor &PP,
136  bool IgnoreYES_NO = false) {
137  // FIXME: This is not very precise. Here we just check to see if the
138  // value comes from a macro, but we can do much better. This is likely
139  // to be over conservative. This logic is factored into a separate function
140  // so that we can refine it later.
141  SourceLocation L = S->getLocStart();
142  if (L.isMacroID()) {
144  if (IgnoreYES_NO) {
145  // The Objective-C constant 'YES' and 'NO'
146  // are defined as macros. Do not treat them
147  // as configuration values.
148  SourceLocation TopL = getTopMostMacro(L, SM);
149  StringRef MacroName = PP.getImmediateMacroName(TopL);
150  if (MacroName == "YES" || MacroName == "NO")
151  return false;
152  } else if (!PP.getLangOpts().CPlusPlus) {
153  // Do not treat C 'false' and 'true' macros as configuration values.
154  SourceLocation TopL = getTopMostMacro(L, SM);
155  StringRef MacroName = PP.getImmediateMacroName(TopL);
156  if (MacroName == "false" || MacroName == "true")
157  return false;
158  }
159  return true;
160  }
161  return false;
162 }
163 
164 static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP);
165 
166 /// Returns true if the statement represents a configuration value.
167 ///
168 /// A configuration value is something usually determined at compile-time
169 /// to conditionally always execute some branch. Such guards are for
170 /// "sometimes unreachable" code. Such code is usually not interesting
171 /// to report as unreachable, and may mask truly unreachable code within
172 /// those blocks.
173 static bool isConfigurationValue(const Stmt *S,
174  Preprocessor &PP,
175  SourceRange *SilenceableCondVal = nullptr,
176  bool IncludeIntegers = true,
177  bool WrappedInParens = false) {
178  if (!S)
179  return false;
180 
181  S = S->IgnoreImplicit();
182 
183  if (const Expr *Ex = dyn_cast<Expr>(S))
184  S = Ex->IgnoreCasts();
185 
186  // Special case looking for the sigil '()' around an integer literal.
187  if (const ParenExpr *PE = dyn_cast<ParenExpr>(S))
188  if (!PE->getLocStart().isMacroID())
189  return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal,
190  IncludeIntegers, true);
191 
192  if (const Expr *Ex = dyn_cast<Expr>(S))
193  S = Ex->IgnoreCasts();
194 
195  bool IgnoreYES_NO = false;
196 
197  switch (S->getStmtClass()) {
198  case Stmt::CallExprClass: {
199  const FunctionDecl *Callee =
200  dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
201  return Callee ? Callee->isConstexpr() : false;
202  }
203  case Stmt::DeclRefExprClass:
204  return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP);
205  case Stmt::ObjCBoolLiteralExprClass:
206  IgnoreYES_NO = true;
207  // Fallthrough.
208  case Stmt::CXXBoolLiteralExprClass:
209  case Stmt::IntegerLiteralClass: {
210  const Expr *E = cast<Expr>(S);
211  if (IncludeIntegers) {
212  if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())
213  *SilenceableCondVal = E->getSourceRange();
214  return WrappedInParens || isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO);
215  }
216  return false;
217  }
218  case Stmt::MemberExprClass:
219  return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP);
220  case Stmt::UnaryExprOrTypeTraitExprClass:
221  return true;
222  case Stmt::BinaryOperatorClass: {
223  const BinaryOperator *B = cast<BinaryOperator>(S);
224  // Only include raw integers (not enums) as configuration
225  // values if they are used in a logical or comparison operator
226  // (not arithmetic).
227  IncludeIntegers &= (B->isLogicalOp() || B->isComparisonOp());
228  return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal,
229  IncludeIntegers) ||
230  isConfigurationValue(B->getRHS(), PP, SilenceableCondVal,
231  IncludeIntegers);
232  }
233  case Stmt::UnaryOperatorClass: {
234  const UnaryOperator *UO = cast<UnaryOperator>(S);
235  if (UO->getOpcode() != UO_LNot)
236  return false;
237  bool SilenceableCondValNotSet =
238  SilenceableCondVal && SilenceableCondVal->getBegin().isInvalid();
239  bool IsSubExprConfigValue =
240  isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal,
241  IncludeIntegers, WrappedInParens);
242  // Update the silenceable condition value source range only if the range
243  // was set directly by the child expression.
244  if (SilenceableCondValNotSet &&
245  SilenceableCondVal->getBegin().isValid() &&
246  *SilenceableCondVal ==
248  *SilenceableCondVal = UO->getSourceRange();
249  return IsSubExprConfigValue;
250  }
251  default:
252  return false;
253  }
254 }
255 
256 static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) {
257  if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D))
258  return isConfigurationValue(ED->getInitExpr(), PP);
259  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
260  // As a heuristic, treat globals as configuration values. Note
261  // that we only will get here if Sema evaluated this
262  // condition to a constant expression, which means the global
263  // had to be declared in a way to be a truly constant value.
264  // We could generalize this to local variables, but it isn't
265  // clear if those truly represent configuration values that
266  // gate unreachable code.
267  if (!VD->hasLocalStorage())
268  return true;
269 
270  // As a heuristic, locals that have been marked 'const' explicitly
271  // can be treated as configuration values as well.
272  return VD->getType().isLocalConstQualified();
273  }
274  return false;
275 }
276 
277 /// Returns true if we should always explore all successors of a block.
279  Preprocessor &PP) {
280  if (const Stmt *Term = B->getTerminator()) {
281  if (isa<SwitchStmt>(Term))
282  return true;
283  // Specially handle '||' and '&&'.
284  if (isa<BinaryOperator>(Term)) {
285  return isConfigurationValue(Term, PP);
286  }
287  }
288 
289  const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
290  return isConfigurationValue(Cond, PP);
291 }
292 
293 static unsigned scanFromBlock(const CFGBlock *Start,
294  llvm::BitVector &Reachable,
295  Preprocessor *PP,
296  bool IncludeSometimesUnreachableEdges) {
297  unsigned count = 0;
298 
299  // Prep work queue
301 
302  // The entry block may have already been marked reachable
303  // by the caller.
304  if (!Reachable[Start->getBlockID()]) {
305  ++count;
306  Reachable[Start->getBlockID()] = true;
307  }
308 
309  WL.push_back(Start);
310 
311  // Find the reachable blocks from 'Start'.
312  while (!WL.empty()) {
313  const CFGBlock *item = WL.pop_back_val();
314 
315  // There are cases where we want to treat all successors as reachable.
316  // The idea is that some "sometimes unreachable" code is not interesting,
317  // and that we should forge ahead and explore those branches anyway.
318  // This allows us to potentially uncover some "always unreachable" code
319  // within the "sometimes unreachable" code.
320  // Look at the successors and mark then reachable.
321  Optional<bool> TreatAllSuccessorsAsReachable;
322  if (!IncludeSometimesUnreachableEdges)
323  TreatAllSuccessorsAsReachable = false;
324 
325  for (CFGBlock::const_succ_iterator I = item->succ_begin(),
326  E = item->succ_end(); I != E; ++I) {
327  const CFGBlock *B = *I;
328  if (!B) do {
329  const CFGBlock *UB = I->getPossiblyUnreachableBlock();
330  if (!UB)
331  break;
332 
333  if (!TreatAllSuccessorsAsReachable.hasValue()) {
334  assert(PP);
335  TreatAllSuccessorsAsReachable =
337  }
338 
339  if (TreatAllSuccessorsAsReachable.getValue()) {
340  B = UB;
341  break;
342  }
343  }
344  while (false);
345 
346  if (B) {
347  unsigned blockID = B->getBlockID();
348  if (!Reachable[blockID]) {
349  Reachable.set(blockID);
350  WL.push_back(B);
351  ++count;
352  }
353  }
354  }
355  }
356  return count;
357 }
358 
359 static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
360  Preprocessor &PP,
361  llvm::BitVector &Reachable) {
362  return scanFromBlock(Start, Reachable, &PP, true);
363 }
364 
365 //===----------------------------------------------------------------------===//
366 // Dead Code Scanner.
367 //===----------------------------------------------------------------------===//
368 
369 namespace {
370  class DeadCodeScan {
371  llvm::BitVector Visited;
372  llvm::BitVector &Reachable;
374  Preprocessor &PP;
375 
377  DeferredLocsTy;
378 
379  DeferredLocsTy DeferredLocs;
380 
381  public:
382  DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP)
383  : Visited(reachable.size()),
384  Reachable(reachable),
385  PP(PP) {}
386 
387  void enqueue(const CFGBlock *block);
388  unsigned scanBackwards(const CFGBlock *Start,
390 
391  bool isDeadCodeRoot(const CFGBlock *Block);
392 
393  const Stmt *findDeadCode(const CFGBlock *Block);
394 
395  void reportDeadCode(const CFGBlock *B,
396  const Stmt *S,
398  };
399 }
400 
401 void DeadCodeScan::enqueue(const CFGBlock *block) {
402  unsigned blockID = block->getBlockID();
403  if (Reachable[blockID] || Visited[blockID])
404  return;
405  Visited[blockID] = true;
406  WorkList.push_back(block);
407 }
408 
409 bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
410  bool isDeadRoot = true;
411 
412  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
413  E = Block->pred_end(); I != E; ++I) {
414  if (const CFGBlock *PredBlock = *I) {
415  unsigned blockID = PredBlock->getBlockID();
416  if (Visited[blockID]) {
417  isDeadRoot = false;
418  continue;
419  }
420  if (!Reachable[blockID]) {
421  isDeadRoot = false;
422  Visited[blockID] = true;
423  WorkList.push_back(PredBlock);
424  continue;
425  }
426  }
427  }
428 
429  return isDeadRoot;
430 }
431 
432 static bool isValidDeadStmt(const Stmt *S) {
433  if (S->getLocStart().isInvalid())
434  return false;
435  if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
436  return BO->getOpcode() != BO_Comma;
437  return true;
438 }
439 
440 const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
441  for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
442  if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
443  const Stmt *S = CS->getStmt();
444  if (isValidDeadStmt(S))
445  return S;
446  }
447 
448  if (CFGTerminator T = Block->getTerminator()) {
449  if (!T.isTemporaryDtorsBranch()) {
450  const Stmt *S = T.getStmt();
451  if (isValidDeadStmt(S))
452  return S;
453  }
454  }
455 
456  return nullptr;
457 }
458 
459 static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
460  const std::pair<const CFGBlock *, const Stmt *> *p2) {
461  if (p1->second->getLocStart() < p2->second->getLocStart())
462  return -1;
463  if (p2->second->getLocStart() < p1->second->getLocStart())
464  return 1;
465  return 0;
466 }
467 
468 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
470 
471  unsigned count = 0;
472  enqueue(Start);
473 
474  while (!WorkList.empty()) {
475  const CFGBlock *Block = WorkList.pop_back_val();
476 
477  // It is possible that this block has been marked reachable after
478  // it was enqueued.
479  if (Reachable[Block->getBlockID()])
480  continue;
481 
482  // Look for any dead code within the block.
483  const Stmt *S = findDeadCode(Block);
484 
485  if (!S) {
486  // No dead code. Possibly an empty block. Look at dead predecessors.
487  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
488  E = Block->pred_end(); I != E; ++I) {
489  if (const CFGBlock *predBlock = *I)
490  enqueue(predBlock);
491  }
492  continue;
493  }
494 
495  // Specially handle macro-expanded code.
496  if (S->getLocStart().isMacroID()) {
497  count += scanMaybeReachableFromBlock(Block, PP, Reachable);
498  continue;
499  }
500 
501  if (isDeadCodeRoot(Block)) {
502  reportDeadCode(Block, S, CB);
503  count += scanMaybeReachableFromBlock(Block, PP, Reachable);
504  }
505  else {
506  // Record this statement as the possibly best location in a
507  // strongly-connected component of dead code for emitting a
508  // warning.
509  DeferredLocs.push_back(std::make_pair(Block, S));
510  }
511  }
512 
513  // If we didn't find a dead root, then report the dead code with the
514  // earliest location.
515  if (!DeferredLocs.empty()) {
516  llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
517  for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
518  E = DeferredLocs.end(); I != E; ++I) {
519  const CFGBlock *Block = I->first;
520  if (Reachable[Block->getBlockID()])
521  continue;
522  reportDeadCode(Block, I->second, CB);
523  count += scanMaybeReachableFromBlock(Block, PP, Reachable);
524  }
525  }
526 
527  return count;
528 }
529 
531  SourceRange &R1,
532  SourceRange &R2) {
533  R1 = R2 = SourceRange();
534 
535  if (const Expr *Ex = dyn_cast<Expr>(S))
536  S = Ex->IgnoreParenImpCasts();
537 
538  switch (S->getStmtClass()) {
539  case Expr::BinaryOperatorClass: {
540  const BinaryOperator *BO = cast<BinaryOperator>(S);
541  return BO->getOperatorLoc();
542  }
543  case Expr::UnaryOperatorClass: {
544  const UnaryOperator *UO = cast<UnaryOperator>(S);
545  R1 = UO->getSubExpr()->getSourceRange();
546  return UO->getOperatorLoc();
547  }
548  case Expr::CompoundAssignOperatorClass: {
549  const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
550  R1 = CAO->getLHS()->getSourceRange();
551  R2 = CAO->getRHS()->getSourceRange();
552  return CAO->getOperatorLoc();
553  }
554  case Expr::BinaryConditionalOperatorClass:
555  case Expr::ConditionalOperatorClass: {
556  const AbstractConditionalOperator *CO =
557  cast<AbstractConditionalOperator>(S);
558  return CO->getQuestionLoc();
559  }
560  case Expr::MemberExprClass: {
561  const MemberExpr *ME = cast<MemberExpr>(S);
562  R1 = ME->getSourceRange();
563  return ME->getMemberLoc();
564  }
565  case Expr::ArraySubscriptExprClass: {
566  const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
567  R1 = ASE->getLHS()->getSourceRange();
568  R2 = ASE->getRHS()->getSourceRange();
569  return ASE->getRBracketLoc();
570  }
571  case Expr::CStyleCastExprClass: {
572  const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
573  R1 = CSC->getSubExpr()->getSourceRange();
574  return CSC->getLParenLoc();
575  }
576  case Expr::CXXFunctionalCastExprClass: {
577  const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
578  R1 = CE->getSubExpr()->getSourceRange();
579  return CE->getLocStart();
580  }
581  case Stmt::CXXTryStmtClass: {
582  return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
583  }
584  case Expr::ObjCBridgedCastExprClass: {
585  const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
586  R1 = CSC->getSubExpr()->getSourceRange();
587  return CSC->getLParenLoc();
588  }
589  default: ;
590  }
591  R1 = S->getSourceRange();
592  return S->getLocStart();
593 }
594 
595 void DeadCodeScan::reportDeadCode(const CFGBlock *B,
596  const Stmt *S,
598  // Classify the unreachable code found, or suppress it in some cases.
600 
601  if (isa<BreakStmt>(S)) {
603  } else if (isTrivialDoWhile(B, S) || isBuiltinUnreachable(S)) {
604  return;
605  }
606  else if (isDeadReturn(B, S)) {
608  }
609 
610  SourceRange SilenceableCondVal;
611 
612  if (UK == reachable_code::UK_Other) {
613  // Check if the dead code is part of the "loop target" of
614  // a for/for-range loop. This is the block that contains
615  // the increment code.
616  if (const Stmt *LoopTarget = B->getLoopTarget()) {
617  SourceLocation Loc = LoopTarget->getLocStart();
618  SourceRange R1(Loc, Loc), R2;
619 
620  if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
621  const Expr *Inc = FS->getInc();
622  Loc = Inc->getLocStart();
623  R2 = Inc->getSourceRange();
624  }
625 
627  Loc, SourceRange(), SourceRange(Loc, Loc), R2);
628  return;
629  }
630 
631  // Check if the dead block has a predecessor whose branch has
632  // a configuration value that *could* be modified to
633  // silence the warning.
635  if (PI != B->pred_end()) {
636  if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
637  const Stmt *TermCond =
638  PredBlock->getTerminatorCondition(/* strip parens */ false);
639  isConfigurationValue(TermCond, PP, &SilenceableCondVal);
640  }
641  }
642  }
643 
644  SourceRange R1, R2;
645  SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
646  CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2);
647 }
648 
649 //===----------------------------------------------------------------------===//
650 // Reachability APIs.
651 //===----------------------------------------------------------------------===//
652 
653 namespace clang { namespace reachable_code {
654 
655 void Callback::anchor() { }
656 
657 unsigned ScanReachableFromBlock(const CFGBlock *Start,
658  llvm::BitVector &Reachable) {
659  return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
660 }
661 
663  Callback &CB) {
664 
665  CFG *cfg = AC.getCFG();
666  if (!cfg)
667  return;
668 
669  // Scan for reachable blocks from the entrance of the CFG.
670  // If there are no unreachable blocks, we're done.
671  llvm::BitVector reachable(cfg->getNumBlockIDs());
672  unsigned numReachable =
673  scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
674  if (numReachable == cfg->getNumBlockIDs())
675  return;
676 
677  // If there aren't explicit EH edges, we should include the 'try' dispatch
678  // blocks as roots.
679  if (!AC.getCFGBuildOptions().AddEHEdges) {
681  E = cfg->try_blocks_end() ; I != E; ++I) {
682  numReachable += scanMaybeReachableFromBlock(*I, PP, reachable);
683  }
684  if (numReachable == cfg->getNumBlockIDs())
685  return;
686  }
687 
688  // There are some unreachable blocks. We need to find the root blocks that
689  // contain code that should be considered unreachable.
690  for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
691  const CFGBlock *block = *I;
692  // A block may have been marked reachable during this loop.
693  if (reachable[block->getBlockID()])
694  continue;
695 
696  DeadCodeScan DS(reachable, PP);
697  numReachable += DS.scanBackwards(block, CB);
698 
699  if (numReachable == cfg->getNumBlockIDs())
700  return;
701  }
702 }
703 
704 }} // end namespace clang::reachable_code
An instance of this class is created to represent a function declaration or definition.
Definition: Decl.h:1697
static bool isBuiltinUnreachable(const Stmt *S)
pred_iterator pred_end()
Definition: CFG.h:607
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:593
static bool isValidDeadStmt(const Stmt *S)
virtual void HandleUnreachable(UnreachableKind UK, SourceLocation L, SourceRange ConditionVal, SourceRange R1, SourceRange R2)=0
succ_iterator succ_begin()
Definition: CFG.h:624
Stmt - This represents one statement.
Definition: Stmt.h:66
CFGBlock & getEntry()
Definition: CFG.h:921
EnumConstantDecl - An instance of this object exists for each enum constant that is defined...
Definition: Decl.h:2661
Defines the SourceManager interface.
bool isConstexpr() const
Whether this is a (C++11) constexpr function or constexpr constructor.
Definition: Decl.h:2036
static bool isEnumConstant(const Expr *Ex)
unsigned getBlockID() const
Definition: CFG.h:729
static int SrcCmp(const std::pair< const CFGBlock *, const Stmt *> *p1, const std::pair< const CFGBlock *, const Stmt *> *p2)
ParenExpr - This represents a parethesized expression, e.g.
Definition: Expr.h:1665
const Stmt * getLoopTarget() const
Definition: CFG.h:722
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:122
iterator begin()
Definition: CFG.h:576
SourceLocation getLParenLoc() const
Definition: Expr.h:2948
Stmt * IgnoreImplicit()
Skip past any implicit AST nodes which might surround this statement, such as ExprWithCleanups or Imp...
Definition: Stmt.cpp:112
SourceLocation getLocStart() const LLVM_READONLY
Definition: ExprCXX.cpp:695
unsigned succ_size() const
Definition: CFG.h:642
SourceLocation getImmediateMacroCallerLoc(SourceLocation Loc) const
Gets the location of the immediate macro caller, one level up the stack toward the initial macro type...
VarDecl - An instance of this class is created to represent a variable declaration or definition...
Definition: Decl.h:806
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP)
Defines the clang::Expr interface and subclasses for C++ expressions.
std::vector< const CFGBlock * >::const_iterator try_block_iterator
Definition: CFG.h:929
AnalysisDeclContext contains the context data for the function or method under analysis.
Expr * getSubExpr()
Definition: Expr.h:2761
SourceLocation getQuestionLoc() const
Definition: Expr.h:3258
const LangOptions & getLangOpts() const
Definition: Preprocessor.h:815
iterator end()
Definition: CFG.h:907
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:600
ForStmt - This represents a &#39;for (init;cond;inc)&#39; stmt.
Definition: Stmt.h:1203
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:2985
CFGBlockListTy::iterator iterator
Definition: CFG.h:898
Expr * IgnoreParenCasts() LLVM_READONLY
IgnoreParenCasts - Ignore parentheses and casts.
Definition: Expr.cpp:2465
static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start, Preprocessor &PP, llvm::BitVector &Reachable)
SourceLocation getOperatorLoc() const
getOperatorLoc - Return the location of the operator.
Definition: Expr.h:1748
reverse_iterator rend()
Definition: CFG.h:582
static bool isDeadReturn(const CFGBlock *B, const Stmt *S)
static bool isTrivialExpression(const Expr *Ex)
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:422
static SourceLocation GetUnreachableLoc(const Stmt *S, SourceRange &R1, SourceRange &R2)
ValueDecl - Represent the declaration of a variable (in which case it is an lvalue) a function (in wh...
Definition: Decl.h:627
Expr - This represents one expression.
Definition: Expr.h:106
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:4898
CFG - Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:834
const FunctionProtoType * T
Defines the clang::Preprocessor interface.
ElementList::const_iterator const_iterator
Definition: CFG.h:569
bool isTemporaryDtorsBranch() const
Definition: CFG.h:383
void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP, Callback &CB)
unsigned ScanReachableFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable)
ScanReachableFromBlock - Mark all blocks reachable from Start.
ReturnStmt - This represents a return, optionally of an expression: return; return 4;...
Definition: Stmt.h:1413
SourceLocation getRBracketLoc() const
Definition: Expr.h:2183
UnaryOperator - This represents the unary-expression&#39;s (except sizeof and alignof), the postinc/postdec operators from postfix-expression, and various extensions.
Definition: Expr.h:1717
SourceLocation getMemberLoc() const
getMemberLoc - Return the location of the "member", in X->F, it is the location of &#39;F&#39;...
Definition: Expr.h:2587
ValueDecl * getDecl()
Definition: Expr.h:1041
CStyleCastExpr - An explicit cast in C (C99 6.5.4) or a C-style cast in C++ (C++ [expr.cast]), which uses the syntax (Type)expr.
Definition: Expr.h:2922
Expr * getLHS()
An array access can be written A[4] or 4[A] (both are equivalent).
Definition: Expr.h:2154
const SourceManager & SM
Definition: Format.cpp:1337
reverse_iterator rbegin()
Definition: CFG.h:581
DoStmt - This represents a &#39;do/while&#39; stmt.
Definition: Stmt.h:1154
try_block_iterator try_blocks_begin() const
Definition: CFG.h:931
SourceManager & getSourceManager() const
Definition: Preprocessor.h:819
static bool isExpandedFromConfigurationMacro(const Stmt *S, Preprocessor &PP, bool IgnoreYES_NO=false)
Returns true if the statement is expanded from a configuration macro.
Expr * IgnoreCasts() LLVM_READONLY
Ignore casts. Strip off any CastExprs, returning their operand.
Definition: Expr.cpp:2487
CFGTerminator getTerminator()
Definition: CFG.h:713
Encodes a location in the source.
SourceLocation getOperatorLoc() const
Definition: Expr.h:3023
Expr * getSubExpr() const
Definition: Expr.h:1744
static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM)
unsigned getNumBlockIDs() const
getNumBlockIDs - Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:998
iterator begin()
Definition: CFG.h:906
static bool isLogicalOp(Opcode Opc)
Definition: Expr.h:3105
succ_iterator succ_end()
Definition: CFG.h:625
Expr * getLHS() const
Definition: Expr.h:3029
CompoundAssignOperator - For compound assignments (e.g.
Definition: Expr.h:3191
An Objective-C "bridged" cast expression, which casts between Objective-C pointers and C pointers...
Definition: ExprObjC.h:1572
pred_iterator pred_begin()
Definition: CFG.h:606
Dataflow Directional Tag Classes.
CFG::BuildOptions & getCFGBuildOptions()
Return the build options used to construct the CFG.
unsigned pred_size() const
Definition: CFG.h:645
StmtClass getStmtClass() const
Definition: Stmt.h:378
static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B, Preprocessor &PP)
Returns true if we should always explore all successors of a block.
SourceLocation getLParenLoc() const
Definition: ExprObjC.h:1596
bool isMacroID() const
UnreachableKind
Classifications of unreachable code.
Definition: ReachableCode.h:41
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
Definition: Expr.h:2121
try_block_iterator try_blocks_end() const
Definition: CFG.h:935
AbstractConditionalOperator - An abstract base class for ConditionalOperator and BinaryConditionalOpe...
Definition: Expr.h:3227
static unsigned scanFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable, Preprocessor *PP, bool IncludeSometimesUnreachableEdges)
Opcode getOpcode() const
Definition: Expr.h:1741
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:2387
Represents an explicit C++ type conversion that uses "functional" notation (C++ [expr.type.conv]).
Definition: ExprCXX.h:1471
CFGElement - Represents a top-level expression in a basic block.
Definition: CFG.h:54
CFGTerminator - Represents CFGBlock terminator statement.
Definition: CFG.h:372
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:265
StringRef getImmediateMacroName(SourceLocation Loc)
Retrieve the name of the immediate macro expansion.
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:956
Expr * getRHS() const
Definition: Expr.h:3031
static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S)
A trivial tuple used to represent a source range.
iterator end()
Definition: CFG.h:577
SourceLocation getLocStart() const LLVM_READONLY
Definition: Stmt.cpp:277
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3075
This class handles loading and caching of source files into memory.
Engages in a tight little dance with the lexer to efficiently preprocess tokens.
Definition: Preprocessor.h:127