clang  16.0.0git
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"
22 #include "clang/Basic/Builtins.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->getTerminatorStmt()) {
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 isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S,
70  ASTContext &C) {
71  if (B->empty()) {
72  // Happens if S is B's terminator and B contains nothing else
73  // (e.g. a CFGBlock containing only a goto).
74  return false;
75  }
76  if (Optional<CFGStmt> CS = B->back().getAs<CFGStmt>()) {
77  if (const auto *CE = dyn_cast<CallExpr>(CS->getStmt())) {
78  return CE->getCallee()->IgnoreCasts() == S && CE->isBuiltinAssumeFalse(C);
79  }
80  }
81  return false;
82 }
83 
84 static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
85  // Look to see if the current control flow ends with a 'return', and see if
86  // 'S' is a substatement. The 'return' may not be the last element in the
87  // block, or may be in a subsequent block because of destructors.
88  const CFGBlock *Current = B;
89  while (true) {
90  for (const CFGElement &CE : llvm::reverse(*Current)) {
91  if (Optional<CFGStmt> CS = CE.getAs<CFGStmt>()) {
92  if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
93  if (RS == S)
94  return true;
95  if (const Expr *RE = RS->getRetValue()) {
96  RE = RE->IgnoreParenCasts();
97  if (RE == S)
98  return true;
99  ParentMap PM(const_cast<Expr *>(RE));
100  // If 'S' is in the ParentMap, it is a subexpression of
101  // the return statement.
102  return PM.getParent(S);
103  }
104  }
105  break;
106  }
107  }
108  // Note also that we are restricting the search for the return statement
109  // to stop at control-flow; only part of a return statement may be dead,
110  // without the whole return statement being dead.
111  if (Current->getTerminator().isTemporaryDtorsBranch()) {
112  // Temporary destructors have a predictable control flow, thus we want to
113  // look into the next block for the return statement.
114  // We look into the false branch, as we know the true branch only contains
115  // the call to the destructor.
116  assert(Current->succ_size() == 2);
117  Current = *(Current->succ_begin() + 1);
118  } else if (!Current->getTerminatorStmt() && Current->succ_size() == 1) {
119  // If there is only one successor, we're not dealing with outgoing control
120  // flow. Thus, look into the next block.
121  Current = *Current->succ_begin();
122  if (Current->pred_size() > 1) {
123  // If there is more than one predecessor, we're dealing with incoming
124  // control flow - if the return statement is in that block, it might
125  // well be reachable via a different control flow, thus it's not dead.
126  return false;
127  }
128  } else {
129  // We hit control flow or a dead end. Stop searching.
130  return false;
131  }
132  }
133  llvm_unreachable("Broke out of infinite loop.");
134 }
135 
137  assert(Loc.isMacroID());
139  do {
140  Last = Loc;
141  Loc = SM.getImmediateMacroCallerLoc(Loc);
142  } while (Loc.isMacroID());
143  return Last;
144 }
145 
146 /// Returns true if the statement is expanded from a configuration macro.
148  Preprocessor &PP,
149  bool IgnoreYES_NO = false) {
150  // FIXME: This is not very precise. Here we just check to see if the
151  // value comes from a macro, but we can do much better. This is likely
152  // to be over conservative. This logic is factored into a separate function
153  // so that we can refine it later.
154  SourceLocation L = S->getBeginLoc();
155  if (L.isMacroID()) {
157  if (IgnoreYES_NO) {
158  // The Objective-C constant 'YES' and 'NO'
159  // are defined as macros. Do not treat them
160  // as configuration values.
161  SourceLocation TopL = getTopMostMacro(L, SM);
162  StringRef MacroName = PP.getImmediateMacroName(TopL);
163  if (MacroName == "YES" || MacroName == "NO")
164  return false;
165  } else if (!PP.getLangOpts().CPlusPlus) {
166  // Do not treat C 'false' and 'true' macros as configuration values.
167  SourceLocation TopL = getTopMostMacro(L, SM);
168  StringRef MacroName = PP.getImmediateMacroName(TopL);
169  if (MacroName == "false" || MacroName == "true")
170  return false;
171  }
172  return true;
173  }
174  return false;
175 }
176 
177 static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP);
178 
179 /// Returns true if the statement represents a configuration value.
180 ///
181 /// A configuration value is something usually determined at compile-time
182 /// to conditionally always execute some branch. Such guards are for
183 /// "sometimes unreachable" code. Such code is usually not interesting
184 /// to report as unreachable, and may mask truly unreachable code within
185 /// those blocks.
186 static bool isConfigurationValue(const Stmt *S,
187  Preprocessor &PP,
188  SourceRange *SilenceableCondVal = nullptr,
189  bool IncludeIntegers = true,
190  bool WrappedInParens = false) {
191  if (!S)
192  return false;
193 
194  if (const auto *Ex = dyn_cast<Expr>(S))
195  S = Ex->IgnoreImplicit();
196 
197  if (const auto *Ex = dyn_cast<Expr>(S))
198  S = Ex->IgnoreCasts();
199 
200  // Special case looking for the sigil '()' around an integer literal.
201  if (const ParenExpr *PE = dyn_cast<ParenExpr>(S))
202  if (!PE->getBeginLoc().isMacroID())
203  return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal,
204  IncludeIntegers, true);
205 
206  if (const Expr *Ex = dyn_cast<Expr>(S))
207  S = Ex->IgnoreCasts();
208 
209  bool IgnoreYES_NO = false;
210 
211  switch (S->getStmtClass()) {
212  case Stmt::CallExprClass: {
213  const FunctionDecl *Callee =
214  dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
215  return Callee ? Callee->isConstexpr() : false;
216  }
217  case Stmt::DeclRefExprClass:
218  return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP);
219  case Stmt::ObjCBoolLiteralExprClass:
220  IgnoreYES_NO = true;
221  [[fallthrough]];
222  case Stmt::CXXBoolLiteralExprClass:
223  case Stmt::IntegerLiteralClass: {
224  const Expr *E = cast<Expr>(S);
225  if (IncludeIntegers) {
226  if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())
227  *SilenceableCondVal = E->getSourceRange();
228  return WrappedInParens ||
229  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  // Do not treat constexpr if statement successors as unreachable in warnings
303  // since the point of these statements is to determine branches at compile
304  // time.
305  if (const auto *IS = dyn_cast<IfStmt>(Term);
306  IS != nullptr && IS->isConstexpr())
307  return true;
308  }
309 
310  const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
311  return isConfigurationValue(Cond, PP);
312 }
313 
314 static unsigned scanFromBlock(const CFGBlock *Start,
315  llvm::BitVector &Reachable,
316  Preprocessor *PP,
317  bool IncludeSometimesUnreachableEdges) {
318  unsigned count = 0;
319 
320  // Prep work queue
322 
323  // The entry block may have already been marked reachable
324  // by the caller.
325  if (!Reachable[Start->getBlockID()]) {
326  ++count;
327  Reachable[Start->getBlockID()] = true;
328  }
329 
330  WL.push_back(Start);
331 
332  // Find the reachable blocks from 'Start'.
333  while (!WL.empty()) {
334  const CFGBlock *item = WL.pop_back_val();
335 
336  // There are cases where we want to treat all successors as reachable.
337  // The idea is that some "sometimes unreachable" code is not interesting,
338  // and that we should forge ahead and explore those branches anyway.
339  // This allows us to potentially uncover some "always unreachable" code
340  // within the "sometimes unreachable" code.
341  // Look at the successors and mark then reachable.
342  Optional<bool> TreatAllSuccessorsAsReachable;
343  if (!IncludeSometimesUnreachableEdges)
344  TreatAllSuccessorsAsReachable = false;
345 
346  for (CFGBlock::const_succ_iterator I = item->succ_begin(),
347  E = item->succ_end(); I != E; ++I) {
348  const CFGBlock *B = *I;
349  if (!B) do {
350  const CFGBlock *UB = I->getPossiblyUnreachableBlock();
351  if (!UB)
352  break;
353 
354  if (!TreatAllSuccessorsAsReachable) {
355  assert(PP);
356  TreatAllSuccessorsAsReachable =
358  }
359 
360  if (*TreatAllSuccessorsAsReachable) {
361  B = UB;
362  break;
363  }
364  }
365  while (false);
366 
367  if (B) {
368  unsigned blockID = B->getBlockID();
369  if (!Reachable[blockID]) {
370  Reachable.set(blockID);
371  WL.push_back(B);
372  ++count;
373  }
374  }
375  }
376  }
377  return count;
378 }
379 
380 static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
381  Preprocessor &PP,
382  llvm::BitVector &Reachable) {
383  return scanFromBlock(Start, Reachable, &PP, true);
384 }
385 
386 //===----------------------------------------------------------------------===//
387 // Dead Code Scanner.
388 //===----------------------------------------------------------------------===//
389 
390 namespace {
391  class DeadCodeScan {
392  llvm::BitVector Visited;
393  llvm::BitVector &Reachable;
395  Preprocessor &PP;
396  ASTContext &C;
397 
399  DeferredLocsTy;
400 
401  DeferredLocsTy DeferredLocs;
402 
403  public:
404  DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP, ASTContext &C)
405  : Visited(reachable.size()),
406  Reachable(reachable),
407  PP(PP), C(C) {}
408 
409  void enqueue(const CFGBlock *block);
410  unsigned scanBackwards(const CFGBlock *Start,
412 
413  bool isDeadCodeRoot(const CFGBlock *Block);
414 
415  const Stmt *findDeadCode(const CFGBlock *Block);
416 
417  void reportDeadCode(const CFGBlock *B,
418  const Stmt *S,
420  };
421 }
422 
423 void DeadCodeScan::enqueue(const CFGBlock *block) {
424  unsigned blockID = block->getBlockID();
425  if (Reachable[blockID] || Visited[blockID])
426  return;
427  Visited[blockID] = true;
428  WorkList.push_back(block);
429 }
430 
431 bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
432  bool isDeadRoot = true;
433 
434  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
435  E = Block->pred_end(); I != E; ++I) {
436  if (const CFGBlock *PredBlock = *I) {
437  unsigned blockID = PredBlock->getBlockID();
438  if (Visited[blockID]) {
439  isDeadRoot = false;
440  continue;
441  }
442  if (!Reachable[blockID]) {
443  isDeadRoot = false;
444  Visited[blockID] = true;
445  WorkList.push_back(PredBlock);
446  continue;
447  }
448  }
449  }
450 
451  return isDeadRoot;
452 }
453 
454 static bool isValidDeadStmt(const Stmt *S) {
455  if (S->getBeginLoc().isInvalid())
456  return false;
457  if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
458  return BO->getOpcode() != BO_Comma;
459  return true;
460 }
461 
462 const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
463  for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
464  if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
465  const Stmt *S = CS->getStmt();
466  if (isValidDeadStmt(S))
467  return S;
468  }
469 
470  CFGTerminator T = Block->getTerminator();
471  if (T.isStmtBranch()) {
472  const Stmt *S = T.getStmt();
473  if (S && isValidDeadStmt(S))
474  return S;
475  }
476 
477  return nullptr;
478 }
479 
480 static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
481  const std::pair<const CFGBlock *, const Stmt *> *p2) {
482  if (p1->second->getBeginLoc() < p2->second->getBeginLoc())
483  return -1;
484  if (p2->second->getBeginLoc() < p1->second->getBeginLoc())
485  return 1;
486  return 0;
487 }
488 
489 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
491 
492  unsigned count = 0;
493  enqueue(Start);
494 
495  while (!WorkList.empty()) {
496  const CFGBlock *Block = WorkList.pop_back_val();
497 
498  // It is possible that this block has been marked reachable after
499  // it was enqueued.
500  if (Reachable[Block->getBlockID()])
501  continue;
502 
503  // Look for any dead code within the block.
504  const Stmt *S = findDeadCode(Block);
505 
506  if (!S) {
507  // No dead code. Possibly an empty block. Look at dead predecessors.
508  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
509  E = Block->pred_end(); I != E; ++I) {
510  if (const CFGBlock *predBlock = *I)
511  enqueue(predBlock);
512  }
513  continue;
514  }
515 
516  // Specially handle macro-expanded code.
517  if (S->getBeginLoc().isMacroID()) {
518  count += scanMaybeReachableFromBlock(Block, PP, Reachable);
519  continue;
520  }
521 
522  if (isDeadCodeRoot(Block)) {
523  reportDeadCode(Block, S, CB);
524  count += scanMaybeReachableFromBlock(Block, PP, Reachable);
525  }
526  else {
527  // Record this statement as the possibly best location in a
528  // strongly-connected component of dead code for emitting a
529  // warning.
530  DeferredLocs.push_back(std::make_pair(Block, S));
531  }
532  }
533 
534  // If we didn't find a dead root, then report the dead code with the
535  // earliest location.
536  if (!DeferredLocs.empty()) {
537  llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
538  for (const auto &I : DeferredLocs) {
539  const CFGBlock *Block = I.first;
540  if (Reachable[Block->getBlockID()])
541  continue;
542  reportDeadCode(Block, I.second, CB);
543  count += scanMaybeReachableFromBlock(Block, PP, Reachable);
544  }
545  }
546 
547  return count;
548 }
549 
551  SourceRange &R1,
552  SourceRange &R2) {
553  R1 = R2 = SourceRange();
554 
555  if (const Expr *Ex = dyn_cast<Expr>(S))
556  S = Ex->IgnoreParenImpCasts();
557 
558  switch (S->getStmtClass()) {
559  case Expr::BinaryOperatorClass: {
560  const BinaryOperator *BO = cast<BinaryOperator>(S);
561  return BO->getOperatorLoc();
562  }
563  case Expr::UnaryOperatorClass: {
564  const UnaryOperator *UO = cast<UnaryOperator>(S);
565  R1 = UO->getSubExpr()->getSourceRange();
566  return UO->getOperatorLoc();
567  }
568  case Expr::CompoundAssignOperatorClass: {
569  const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
570  R1 = CAO->getLHS()->getSourceRange();
571  R2 = CAO->getRHS()->getSourceRange();
572  return CAO->getOperatorLoc();
573  }
574  case Expr::BinaryConditionalOperatorClass:
575  case Expr::ConditionalOperatorClass: {
576  const AbstractConditionalOperator *CO =
577  cast<AbstractConditionalOperator>(S);
578  return CO->getQuestionLoc();
579  }
580  case Expr::MemberExprClass: {
581  const MemberExpr *ME = cast<MemberExpr>(S);
582  R1 = ME->getSourceRange();
583  return ME->getMemberLoc();
584  }
585  case Expr::ArraySubscriptExprClass: {
586  const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
587  R1 = ASE->getLHS()->getSourceRange();
588  R2 = ASE->getRHS()->getSourceRange();
589  return ASE->getRBracketLoc();
590  }
591  case Expr::CStyleCastExprClass: {
592  const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
593  R1 = CSC->getSubExpr()->getSourceRange();
594  return CSC->getLParenLoc();
595  }
596  case Expr::CXXFunctionalCastExprClass: {
597  const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
598  R1 = CE->getSubExpr()->getSourceRange();
599  return CE->getBeginLoc();
600  }
601  case Stmt::CXXTryStmtClass: {
602  return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
603  }
604  case Expr::ObjCBridgedCastExprClass: {
605  const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
606  R1 = CSC->getSubExpr()->getSourceRange();
607  return CSC->getLParenLoc();
608  }
609  default: ;
610  }
611  R1 = S->getSourceRange();
612  return S->getBeginLoc();
613 }
614 
615 void DeadCodeScan::reportDeadCode(const CFGBlock *B,
616  const Stmt *S,
618  // Classify the unreachable code found, or suppress it in some cases.
620 
621  if (isa<BreakStmt>(S)) {
623  } else if (isTrivialDoWhile(B, S) || isBuiltinUnreachable(S) ||
624  isBuiltinAssumeFalse(B, S, C)) {
625  return;
626  }
627  else if (isDeadReturn(B, S)) {
629  }
630 
631  SourceRange SilenceableCondVal;
632 
633  if (UK == reachable_code::UK_Other) {
634  // Check if the dead code is part of the "loop target" of
635  // a for/for-range loop. This is the block that contains
636  // the increment code.
637  if (const Stmt *LoopTarget = B->getLoopTarget()) {
638  SourceLocation Loc = LoopTarget->getBeginLoc();
639  SourceRange R1(Loc, Loc), R2;
640 
641  if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
642  const Expr *Inc = FS->getInc();
643  Loc = Inc->getBeginLoc();
644  R2 = Inc->getSourceRange();
645  }
646 
648  Loc, SourceRange(), SourceRange(Loc, Loc), R2);
649  return;
650  }
651 
652  // Check if the dead block has a predecessor whose branch has
653  // a configuration value that *could* be modified to
654  // silence the warning.
656  if (PI != B->pred_end()) {
657  if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
658  const Stmt *TermCond =
659  PredBlock->getTerminatorCondition(/* strip parens */ false);
660  isConfigurationValue(TermCond, PP, &SilenceableCondVal);
661  }
662  }
663  }
664 
665  SourceRange R1, R2;
666  SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
667  CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2);
668 }
669 
670 //===----------------------------------------------------------------------===//
671 // Reachability APIs.
672 //===----------------------------------------------------------------------===//
673 
674 namespace clang { namespace reachable_code {
675 
676 void Callback::anchor() { }
677 
678 unsigned ScanReachableFromBlock(const CFGBlock *Start,
679  llvm::BitVector &Reachable) {
680  return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
681 }
682 
684  Callback &CB) {
685 
686  CFG *cfg = AC.getCFG();
687  if (!cfg)
688  return;
689 
690  // Scan for reachable blocks from the entrance of the CFG.
691  // If there are no unreachable blocks, we're done.
692  llvm::BitVector reachable(cfg->getNumBlockIDs());
693  unsigned numReachable =
694  scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
695  if (numReachable == cfg->getNumBlockIDs())
696  return;
697 
698  // If there aren't explicit EH edges, we should include the 'try' dispatch
699  // blocks as roots.
700  if (!AC.getCFGBuildOptions().AddEHEdges) {
701  for (const CFGBlock *B : cfg->try_blocks())
702  numReachable += scanMaybeReachableFromBlock(B, PP, reachable);
703  if (numReachable == cfg->getNumBlockIDs())
704  return;
705  }
706 
707  // There are some unreachable blocks. We need to find the root blocks that
708  // contain code that should be considered unreachable.
709  for (const CFGBlock *block : *cfg) {
710  // A block may have been marked reachable during this loop.
711  if (reachable[block->getBlockID()])
712  continue;
713 
714  DeadCodeScan DS(reachable, PP, AC.getASTContext());
715  numReachable += DS.scanBackwards(block, CB);
716 
717  if (numReachable == cfg->getNumBlockIDs())
718  return;
719  }
720 }
721 
722 }} // end namespace clang::reachable_code
clang::CFGTerminator::isStmtBranch
bool isStmtBranch() const
Definition: CFG.h:541
Builtins.h
clang::AnalysisDeclContext::getASTContext
ASTContext & getASTContext() const
Definition: AnalysisDeclContext.h:104
clang::reachable_code::FindUnreachableCode
void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP, Callback &CB)
Definition: ReachableCode.cpp:683
clang::CFGBlock::getLoopTarget
const Stmt * getLoopTarget() const
Definition: CFG.h:1069
clang::SourceRange
A trivial tuple used to represent a source range.
Definition: SourceLocation.h:210
isExpandedFromConfigurationMacro
static bool isExpandedFromConfigurationMacro(const Stmt *S, Preprocessor &PP, bool IgnoreYES_NO=false)
Returns true if the statement is expanded from a configuration macro.
Definition: ReachableCode.cpp:147
clang::CFGBlock::empty
bool empty() const
Definition: CFG.h:920
shouldTreatSuccessorsAsReachable
static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B, Preprocessor &PP)
Returns true if we should always explore all successors of a block.
Definition: ReachableCode.cpp:293
clang::BinaryOperator::isComparisonOp
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3911
clang::CXXFunctionalCastExpr::getBeginLoc
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: ExprCXX.cpp:868
clang::CFG::getNumBlockIDs
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition: CFG.h:1413
clang::CFGBlock::succ_begin
succ_iterator succ_begin()
Definition: CFG.h:957
AnalysisDeclContext.h
llvm::SmallVector
Definition: LLVM.h:38
clang::CFG::BuildOptions::AddEHEdges
bool AddEHEdges
Definition: CFG.h:1242
clang::SourceLocation
Encodes a location in the source.
Definition: SourceLocation.h:86
clang::AbstractConditionalOperator
AbstractConditionalOperator - An abstract base class for ConditionalOperator and BinaryConditionalOpe...
Definition: Expr.h:4112
clang::CastExpr::getSubExpr
Expr * getSubExpr()
Definition: Expr.h:3530
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1076
clang::reachable_code::UK_Loop_Increment
@ UK_Loop_Increment
Definition: ReachableCode.h:43
clang::Stmt::getSourceRange
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:324
clang::ObjCBridgedCastExpr
An Objective-C "bridged" cast expression, which casts between Objective-C pointers and C pointers,...
Definition: ExprObjC.h:1625
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:56
clang::AnalysisDeclContext
AnalysisDeclContext contains the context data for the function, method or block under analysis.
Definition: AnalysisDeclContext.h:72
llvm::Optional
Definition: LLVM.h:40
clang::UnaryOperator
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2172
SourceManager.h
clang::CFGBlock::const_succ_iterator
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:933
clang::CFG
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1227
clang::reachable_code::UnreachableKind
UnreachableKind
Classifications of unreachable code.
Definition: ReachableCode.h:40
clang::SourceManager
This class handles loading and caching of source files into memory.
Definition: SourceManager.h:636
clang::CStyleCastExpr::getLParenLoc
SourceLocation getLParenLoc() const
Definition: Expr.h:3775
clang::Preprocessor::getLangOpts
const LangOptions & getLangOpts() const
Definition: Preprocessor.h:1065
Preprocessor.h
clang::Preprocessor::getImmediateMacroName
StringRef getImmediateMacroName(SourceLocation Loc)
Retrieve the name of the immediate macro expansion.
Definition: Preprocessor.h:1990
clang::CFGTerminator::getStmt
Stmt * getStmt()
Definition: CFG.h:537
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:578
scanFromBlock
static unsigned scanFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable, Preprocessor *PP, bool IncludeSometimesUnreachableEdges)
Definition: ReachableCode.cpp:314
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3812
isValidDeadStmt
static bool isValidDeadStmt(const Stmt *S)
Definition: ReachableCode.cpp:454
SrcCmp
static int SrcCmp(const std::pair< const CFGBlock *, const Stmt * > *p1, const std::pair< const CFGBlock *, const Stmt * > *p2)
Definition: ReachableCode.cpp:480
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:209
clang::interp::Inc
bool Inc(InterpState &S, CodePtr OpPC)
1) Pops a pointer from the stack 2) Load the value from the pointer 3) Writes the value increased by ...
Definition: Interp.h:357
ReachableCode.h
clang::ForStmt
ForStmt - This represents a 'for (init;cond;inc)' stmt.
Definition: Stmt.h:2570
clang::DeclRefExpr::getDecl
ValueDecl * getDecl()
Definition: Expr.h:1304
clang::CFGBlock::const_iterator
ElementList::const_iterator const_iterator
Definition: CFG.h:868
Expr.h
clang::VarDecl
Represents a variable declaration or definition.
Definition: Decl.h:906
clang::MemberExpr::getMemberLoc
SourceLocation getMemberLoc() const
getMemberLoc - Return the location of the "member", in X->F, it is the location of 'F'.
Definition: Expr.h:3358
clang::EnumConstantDecl
An instance of this object exists for each enum constant that is defined.
Definition: Decl.h:3145
ExprObjC.h
ExprCXX.h
clang::CFGBlock::getTerminatorCondition
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:6252
clang::CFGTerminator
Represents CFGBlock terminator statement.
Definition: CFG.h:505
clang::ArraySubscriptExpr::getLHS
Expr * getLHS()
An array access can be written A[4] or 4[A] (both are equivalent).
Definition: Expr.h:2683
clang::ArraySubscriptExpr::getRHS
Expr * getRHS()
Definition: Expr.h:2687
isBuiltinUnreachable
static bool isBuiltinUnreachable(const Stmt *S)
Definition: ReachableCode.cpp:61
clang::Preprocessor::getSourceManager
SourceManager & getSourceManager() const
Definition: Preprocessor.h:1069
clang::Expr::IgnoreParenCasts
Expr * IgnoreParenCasts() LLVM_READONLY
Skip past any parentheses and casts which might surround this expression until reaching a fixed point...
Definition: Expr.cpp:3040
clang::CStyleCastExpr
CStyleCastExpr - An explicit cast in C (C99 6.5.4) or a C-style cast in C++ (C++ [expr....
Definition: Expr.h:3740
clang::ParentMap
Definition: ParentMap.h:20
clang::UnaryOperator::getOperatorLoc
SourceLocation getOperatorLoc() const
getOperatorLoc - Return the location of the operator.
Definition: Expr.h:2223
clang::CFGBlock::back
CFGElement back() const
Definition: CFG.h:875
clang::CFGStmt
Definition: CFG.h:132
clang::AnalysisDeclContext::getCFGBuildOptions
CFG::BuildOptions & getCFGBuildOptions()
Definition: AnalysisDeclContext.h:110
isTrivialDoWhile
static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S)
Definition: ReachableCode.cpp:49
clang::CFGElement::getAs
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
clang::ValueDecl
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:701
clang::CFGBlock::succ_end
succ_iterator succ_end()
Definition: CFG.h:958
clang::BinaryOperator::getLHS
Expr * getLHS() const
Definition: Expr.h:3861
clang::ParenExpr
ParenExpr - This represents a parethesized expression, e.g.
Definition: Expr.h:2121
clang::reachable_code::Callback
Definition: ReachableCode.h:47
clang::CFGBlock::pred_begin
pred_iterator pred_begin()
Definition: CFG.h:939
clang::CXXFunctionalCastExpr
Represents an explicit C++ type conversion that uses "functional" notation (C++ [expr....
Definition: ExprCXX.h:1733
clang::ArraySubscriptExpr
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
Definition: Expr.h:2654
clang::DoStmt
DoStmt - This represents a 'do/while' stmt.
Definition: Stmt.h:2514
clang::BinaryOperator::getOperatorLoc
SourceLocation getOperatorLoc() const
Definition: Expr.h:3853
clang::CFG::getEntry
CFGBlock & getEntry()
Definition: CFG.h:1333
clang::ParentMap::getParent
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:134
clang::CompoundAssignOperator
CompoundAssignOperator - For compound assignments (e.g.
Definition: Expr.h:4059
clang::SourceLocation::isMacroID
bool isMacroID() const
Definition: SourceLocation.h:103
isTrivialExpression
static bool isTrivialExpression(const Expr *Ex)
Definition: ReachableCode.cpp:41
clang::CFGElement
Represents a top-level expression in a basic block.
Definition: CFG.h:55
clang::reachable_code::UK_Return
@ UK_Return
Definition: ReachableCode.h:41
isBuiltinAssumeFalse
static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S, ASTContext &C)
Definition: ReachableCode.cpp:69
clang::BinaryOperator::isLogicalOp
static bool isLogicalOp(Opcode Opc)
Definition: Expr.h:3944
ParentMap.h
clang::reachable_code::Callback::HandleUnreachable
virtual void HandleUnreachable(UnreachableKind UK, SourceLocation L, SourceRange ConditionVal, SourceRange R1, SourceRange R2)=0
clang::ArraySubscriptExpr::getRBracketLoc
SourceLocation getRBracketLoc() const
Definition: Expr.h:2702
isEnumConstant
static bool isEnumConstant(const Expr *Ex)
Definition: ReachableCode.cpp:34
clang::UnaryOperator::getSubExpr
Expr * getSubExpr() const
Definition: Expr.h:2219
clang
Definition: CalledOnceCheck.h:17
clang::reachable_code::UK_Other
@ UK_Other
Definition: ReachableCode.h:44
CFG.h
clang::DeclaratorContext::Block
@ Block
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:71
clang::ComparisonCategoryType::Last
@ Last
clang::UnaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:2214
clang::BinaryOperator::getRHS
Expr * getRHS() const
Definition: Expr.h:3863
clang::CFG::try_blocks
try_block_range try_blocks() const
Definition: CFG.h:1352
clang::CFGBlock::getTerminatorStmt
Stmt * getTerminatorStmt()
Definition: CFG.h:1052
clang::reachable_code::UK_Break
@ UK_Break
Definition: ReachableCode.h:42
scanMaybeReachableFromBlock
static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start, Preprocessor &PP, llvm::BitVector &Reachable)
Definition: ReachableCode.cpp:380
clang::MemberExpr
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:3169
isConfigurationValue
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP)
Definition: ReachableCode.cpp:271
clang::AbstractConditionalOperator::getQuestionLoc
SourceLocation getQuestionLoc() const
Definition: Expr.h:4139
clang::AnalysisDeclContext::getCFG
CFG * getCFG()
Definition: AnalysisDeclContext.cpp:213
clang::Expr::IgnoreCasts
Expr * IgnoreCasts() LLVM_READONLY
Skip past any casts which might surround this expression until reaching a fixed point.
Definition: Expr.cpp:3019
clang::Expr
This represents one expression.
Definition: Expr.h:109
isDeadReturn
static bool isDeadReturn(const CFGBlock *B, const Stmt *S)
Definition: ReachableCode.cpp:84
clang::Preprocessor
Engages in a tight little dance with the lexer to efficiently preprocess tokens.
Definition: Preprocessor.h:129
SM
#define SM(sm)
Definition: Cuda.cpp:79
clang::DeclRefExpr
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1232
clang::FunctionDecl
Represents a function declaration or definition.
Definition: Decl.h:1904
clang::reachable_code::ScanReachableFromBlock
unsigned ScanReachableFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable)
ScanReachableFromBlock - Mark all blocks reachable from Start.
Definition: ReachableCode.cpp:678
getTopMostMacro
static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM)
Definition: ReachableCode.cpp:136
StmtCXX.h
GetUnreachableLoc
static SourceLocation GetUnreachableLoc(const Stmt *S, SourceRange &R1, SourceRange &R2)
Definition: ReachableCode.cpp:550
clang::ReturnStmt
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Definition: Stmt.h:2796
clang::CFGBlock::pred_end
pred_iterator pred_end()
Definition: CFG.h:940
clang::CFGBlock::const_pred_iterator
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:926
clang::ObjCBridgedCastExpr::getLParenLoc
SourceLocation getLParenLoc() const
Definition: ExprObjC.h:1649