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