clang  6.0.0svn
UnreachableCodeChecker.cpp
Go to the documentation of this file.
1 //==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- 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 // This file implements a generalized unreachable code checker using a
10 // path-sensitive analysis. We mark any path visited, and then walk the CFG as a
11 // post-analysis to determine what was never visited.
12 //
13 // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp
14 //===----------------------------------------------------------------------===//
15 
16 #include "ClangSACheckers.h"
17 #include "clang/AST/ParentMap.h"
18 #include "clang/Basic/Builtins.h"
27 #include "llvm/ADT/SmallSet.h"
28 
29 using namespace clang;
30 using namespace ento;
31 
32 namespace {
33 class UnreachableCodeChecker : public Checker<check::EndAnalysis> {
34 public:
35  void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,
36  ExprEngine &Eng) const;
37 private:
38  typedef llvm::SmallSet<unsigned, 32> CFGBlocksSet;
39 
40  static inline const Stmt *getUnreachableStmt(const CFGBlock *CB);
41  static void FindUnreachableEntryPoints(const CFGBlock *CB,
42  CFGBlocksSet &reachable,
43  CFGBlocksSet &visited);
44  static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM);
45  static inline bool isEmptyCFGBlock(const CFGBlock *CB);
46 };
47 }
48 
49 void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G,
50  BugReporter &B,
51  ExprEngine &Eng) const {
52  CFGBlocksSet reachable, visited;
53 
54  if (Eng.hasWorkRemaining())
55  return;
56 
57  const Decl *D = nullptr;
58  CFG *C = nullptr;
59  ParentMap *PM = nullptr;
60  const LocationContext *LC = nullptr;
61  // Iterate over ExplodedGraph
63  I != E; ++I) {
64  const ProgramPoint &P = I->getLocation();
65  LC = P.getLocationContext();
66  if (!LC->inTopFrame())
67  continue;
68 
69  if (!D)
70  D = LC->getAnalysisDeclContext()->getDecl();
71 
72  // Save the CFG if we don't have it already
73  if (!C)
75  if (!PM)
76  PM = &LC->getParentMap();
77 
79  const CFGBlock *CB = BE->getBlock();
80  reachable.insert(CB->getBlockID());
81  }
82  }
83 
84  // Bail out if we didn't get the CFG or the ParentMap.
85  if (!D || !C || !PM)
86  return;
87 
88  // Don't do anything for template instantiations. Proving that code
89  // in a template instantiation is unreachable means proving that it is
90  // unreachable in all instantiations.
91  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
92  if (FD->isTemplateInstantiation())
93  return;
94 
95  // Find CFGBlocks that were not covered by any node
96  for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) {
97  const CFGBlock *CB = *I;
98  // Check if the block is unreachable
99  if (reachable.count(CB->getBlockID()))
100  continue;
101 
102  // Check if the block is empty (an artificial block)
103  if (isEmptyCFGBlock(CB))
104  continue;
105 
106  // Find the entry points for this block
107  if (!visited.count(CB->getBlockID()))
108  FindUnreachableEntryPoints(CB, reachable, visited);
109 
110  // This block may have been pruned; check if we still want to report it
111  if (reachable.count(CB->getBlockID()))
112  continue;
113 
114  // Check for false positives
115  if (isInvalidPath(CB, *PM))
116  continue;
117 
118  // It is good practice to always have a "default" label in a "switch", even
119  // if we should never get there. It can be used to detect errors, for
120  // instance. Unreachable code directly under a "default" label is therefore
121  // likely to be a false positive.
122  if (const Stmt *label = CB->getLabel())
123  if (label->getStmtClass() == Stmt::DefaultStmtClass)
124  continue;
125 
126  // Special case for __builtin_unreachable.
127  // FIXME: This should be extended to include other unreachable markers,
128  // such as llvm_unreachable.
129  if (!CB->empty()) {
130  bool foundUnreachable = false;
131  for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
132  ci != ce; ++ci) {
133  if (Optional<CFGStmt> S = (*ci).getAs<CFGStmt>())
134  if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
135  if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable) {
136  foundUnreachable = true;
137  break;
138  }
139  }
140  }
141  if (foundUnreachable)
142  continue;
143  }
144 
145  // We found a block that wasn't covered - find the statement to report
146  SourceRange SR;
148  SourceLocation SL;
149  if (const Stmt *S = getUnreachableStmt(CB)) {
150  // In macros, 'do {...} while (0)' is often used. Don't warn about the
151  // condition 0 when it is unreachable.
152  if (S->getLocStart().isMacroID())
153  if (const auto *I = dyn_cast<IntegerLiteral>(S))
154  if (I->getValue() == 0ULL)
155  if (const Stmt *Parent = PM->getParent(S))
156  if (isa<DoStmt>(Parent))
157  continue;
158  SR = S->getSourceRange();
160  SL = DL.asLocation();
161  if (SR.isInvalid() || !SL.isValid())
162  continue;
163  }
164  else
165  continue;
166 
167  // Check if the SourceLocation is in a system header
168  const SourceManager &SM = B.getSourceManager();
169  if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
170  continue;
171 
172  B.EmitBasicReport(D, this, "Unreachable code", "Dead code",
173  "This statement is never executed", DL, SR);
174  }
175 }
176 
177 // Recursively finds the entry point(s) for this dead CFGBlock.
178 void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB,
179  CFGBlocksSet &reachable,
180  CFGBlocksSet &visited) {
181  visited.insert(CB->getBlockID());
182 
183  for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
184  I != E; ++I) {
185  if (!*I)
186  continue;
187 
188  if (!reachable.count((*I)->getBlockID())) {
189  // If we find an unreachable predecessor, mark this block as reachable so
190  // we don't report this block
191  reachable.insert(CB->getBlockID());
192  if (!visited.count((*I)->getBlockID()))
193  // If we haven't previously visited the unreachable predecessor, recurse
194  FindUnreachableEntryPoints(*I, reachable, visited);
195  }
196  }
197 }
198 
199 // Find the Stmt* in a CFGBlock for reporting a warning
200 const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
201  for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
202  if (Optional<CFGStmt> S = I->getAs<CFGStmt>()) {
203  if (!isa<DeclStmt>(S->getStmt()))
204  return S->getStmt();
205  }
206  }
207  if (const Stmt *S = CB->getTerminator())
208  return S;
209  else
210  return nullptr;
211 }
212 
213 // Determines if the path to this CFGBlock contained an element that infers this
214 // block is a false positive. We assume that FindUnreachableEntryPoints has
215 // already marked only the entry points to any dead code, so we need only to
216 // find the condition that led to this block (the predecessor of this block.)
217 // There will never be more than one predecessor.
218 bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
219  const ParentMap &PM) {
220  // We only expect a predecessor size of 0 or 1. If it is >1, then an external
221  // condition has broken our assumption (for example, a sink being placed by
222  // another check). In these cases, we choose not to report.
223  if (CB->pred_size() > 1)
224  return true;
225 
226  // If there are no predecessors, then this block is trivially unreachable
227  if (CB->pred_size() == 0)
228  return false;
229 
230  const CFGBlock *pred = *CB->pred_begin();
231  if (!pred)
232  return false;
233 
234  // Get the predecessor block's terminator conditon
235  const Stmt *cond = pred->getTerminatorCondition();
236 
237  //assert(cond && "CFGBlock's predecessor has a terminator condition");
238  // The previous assertion is invalid in some cases (eg do/while). Leaving
239  // reporting of these situations on at the moment to help triage these cases.
240  if (!cond)
241  return false;
242 
243  // Run each of the checks on the conditions
244  return containsMacro(cond) || containsEnum(cond) ||
246  containsStmt<UnaryExprOrTypeTraitExpr>(cond);
247 }
248 
249 // Returns true if the given CFGBlock is empty
250 bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
251  return CB->getLabel() == nullptr // No labels
252  && CB->size() == 0 // No statements
253  && !CB->getTerminator(); // No terminator
254 }
255 
256 void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
257  mgr.registerChecker<UnreachableCodeChecker>();
258 }
FunctionDecl - An instance of this class is created to represent a function declaration or definition...
Definition: Decl.h:1698
bool empty() const
Definition: CFG.h:587
pred_iterator pred_end()
Definition: CFG.h:607
bool containsStaticLocal(const Stmt *S)
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:593
Stmt - This represents one statement.
Definition: Stmt.h:66
Defines the SourceManager interface.
unsigned getBlockID() const
Definition: CFG.h:729
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
StringRef P
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:122
iterator begin()
Definition: CFG.h:576
bool containsBuiltinOffsetOf(const Stmt *S)
iterator end()
Definition: CFG.h:907
virtual bool inTopFrame() const
Return true if the current LocationContext has no caller context.
unsigned size() const
Definition: CFG.h:586
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:899
NodeId Parent
Definition: ASTDiff.cpp:192
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:422
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
bool isInSystemHeader(SourceLocation Loc) const
Returns if a SourceLocation is in a system header.
ElementList::const_iterator const_iterator
Definition: CFG.h:569
bool isInvalid() const
const SourceManager & SM
Definition: Format.cpp:1337
ParentMap & getParentMap() const
CFG * getUnoptimizedCFG()
Return a version of the CFG without any edges pruned.
BugReporter is a utility class for generating PathDiagnostics for analysis.
Definition: BugReporter.h:403
CFGTerminator getTerminator()
Definition: CFG.h:713
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
CHECKER * registerChecker()
Used to register checkers.
node_iterator nodes_begin()
Encodes a location in the source.
void EmitBasicReport(const Decl *DeclWithIssue, const CheckerBase *Checker, StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc, ArrayRef< SourceRange > Ranges=None)
Stmt * getLabel()
Definition: CFG.h:724
const Decl * getDecl() const
iterator begin()
Definition: CFG.h:906
bool isInExternCSystemHeader(SourceLocation Loc) const
Returns if a SourceLocation is in an "extern C" system header.
pred_iterator pred_begin()
Definition: CFG.h:606
Dataflow Directional Tag Classes.
unsigned pred_size() const
Definition: CFG.h:645
bool hasWorkRemaining() const
Definition: ExprEngine.h:325
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:179
SourceManager & getSourceManager()
Definition: BugReporter.h:463
bool containsMacro(const Stmt *S)
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2209
AllNodesTy::iterator node_iterator
A trivial tuple used to represent a source range.
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:151
iterator end()
Definition: CFG.h:577
AnalysisDeclContext * getAnalysisDeclContext() const
bool containsEnum(const Stmt *S)
This class handles loading and caching of source files into memory.
Defines enum values for all the target-independent builtin functions.