clang  8.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
62  for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
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  CE->isBuiltinAssumeFalse(Eng.getContext())) {
137  foundUnreachable = true;
138  break;
139  }
140  }
141  }
142  if (foundUnreachable)
143  continue;
144  }
145 
146  // We found a block that wasn't covered - find the statement to report
147  SourceRange SR;
148  PathDiagnosticLocation DL;
149  SourceLocation SL;
150  if (const Stmt *S = getUnreachableStmt(CB)) {
151  // In macros, 'do {...} while (0)' is often used. Don't warn about the
152  // condition 0 when it is unreachable.
153  if (S->getBeginLoc().isMacroID())
154  if (const auto *I = dyn_cast<IntegerLiteral>(S))
155  if (I->getValue() == 0ULL)
156  if (const Stmt *Parent = PM->getParent(S))
157  if (isa<DoStmt>(Parent))
158  continue;
159  SR = S->getSourceRange();
160  DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
161  SL = DL.asLocation();
162  if (SR.isInvalid() || !SL.isValid())
163  continue;
164  }
165  else
166  continue;
167 
168  // Check if the SourceLocation is in a system header
169  const SourceManager &SM = B.getSourceManager();
170  if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
171  continue;
172 
173  B.EmitBasicReport(D, this, "Unreachable code", "Dead code",
174  "This statement is never executed", DL, SR);
175  }
176 }
177 
178 // Recursively finds the entry point(s) for this dead CFGBlock.
179 void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB,
180  CFGBlocksSet &reachable,
181  CFGBlocksSet &visited) {
182  visited.insert(CB->getBlockID());
183 
184  for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
185  I != E; ++I) {
186  if (!*I)
187  continue;
188 
189  if (!reachable.count((*I)->getBlockID())) {
190  // If we find an unreachable predecessor, mark this block as reachable so
191  // we don't report this block
192  reachable.insert(CB->getBlockID());
193  if (!visited.count((*I)->getBlockID()))
194  // If we haven't previously visited the unreachable predecessor, recurse
195  FindUnreachableEntryPoints(*I, reachable, visited);
196  }
197  }
198 }
199 
200 // Find the Stmt* in a CFGBlock for reporting a warning
201 const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
202  for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
203  if (Optional<CFGStmt> S = I->getAs<CFGStmt>()) {
204  if (!isa<DeclStmt>(S->getStmt()))
205  return S->getStmt();
206  }
207  }
208  if (const Stmt *S = CB->getTerminator())
209  return S;
210  else
211  return nullptr;
212 }
213 
214 // Determines if the path to this CFGBlock contained an element that infers this
215 // block is a false positive. We assume that FindUnreachableEntryPoints has
216 // already marked only the entry points to any dead code, so we need only to
217 // find the condition that led to this block (the predecessor of this block.)
218 // There will never be more than one predecessor.
219 bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
220  const ParentMap &PM) {
221  // We only expect a predecessor size of 0 or 1. If it is >1, then an external
222  // condition has broken our assumption (for example, a sink being placed by
223  // another check). In these cases, we choose not to report.
224  if (CB->pred_size() > 1)
225  return true;
226 
227  // If there are no predecessors, then this block is trivially unreachable
228  if (CB->pred_size() == 0)
229  return false;
230 
231  const CFGBlock *pred = *CB->pred_begin();
232  if (!pred)
233  return false;
234 
235  // Get the predecessor block's terminator conditon
236  const Stmt *cond = pred->getTerminatorCondition();
237 
238  //assert(cond && "CFGBlock's predecessor has a terminator condition");
239  // The previous assertion is invalid in some cases (eg do/while). Leaving
240  // reporting of these situations on at the moment to help triage these cases.
241  if (!cond)
242  return false;
243 
244  // Run each of the checks on the conditions
245  return containsMacro(cond) || containsEnum(cond) ||
247  containsStmt<UnaryExprOrTypeTraitExpr>(cond);
248 }
249 
250 // Returns true if the given CFGBlock is empty
251 bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
252  return CB->getLabel() == nullptr // No labels
253  && CB->size() == 0 // No statements
254  && !CB->getTerminator(); // No terminator
255 }
256 
257 void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
258  mgr.registerChecker<UnreachableCodeChecker>();
259 }
Represents a function declaration or definition.
Definition: Decl.h:1722
bool empty() const
Definition: CFG.h:714
pred_iterator pred_end()
Definition: CFG.h:734
bool containsStaticLocal(const Stmt *S)
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:720
Stmt - This represents one statement.
Definition: Stmt.h:66
Defines the SourceManager interface.
unsigned getBlockID() const
Definition: CFG.h:856
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
StringRef P
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:123
iterator begin()
Definition: CFG.h:703
bool containsBuiltinOffsetOf(const Stmt *S)
iterator end()
Definition: CFG.h:1079
virtual bool inTopFrame() const
Return true if the current LocationContext has no caller context.
unsigned size() const
Definition: CFG.h:713
CFGBlockListTy::const_iterator const_iterator
Definition: CFG.h:1071
NodeId Parent
Definition: ASTDiff.cpp:192
Represents a single basic block in a source-level CFG.
Definition: CFG.h:552
AllNodesTy::iterator node_iterator
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:5441
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1003
bool isInSystemHeader(SourceLocation Loc) const
Returns if a SourceLocation is in a system header.
ElementList::const_iterator const_iterator
Definition: CFG.h:696
bool isInvalid() const
const SourceManager & SM
Definition: Format.cpp:1475
ParentMap & getParentMap() const
CFG * getUnoptimizedCFG()
Return a version of the CFG without any edges pruned.
CFGTerminator getTerminator()
Definition: CFG.h:840
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
Encodes a location in the source.
Stmt * getLabel()
Definition: CFG.h:851
const Decl * getDecl() const
iterator begin()
Definition: CFG.h:1078
bool isInExternCSystemHeader(SourceLocation Loc) const
Returns if a SourceLocation is in an "extern C" system header.
pred_iterator pred_begin()
Definition: CFG.h:733
Dataflow Directional Tag Classes.
unsigned pred_size() const
Definition: CFG.h:772
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:180
bool containsMacro(const Stmt *S)
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2406
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:152
iterator end()
Definition: CFG.h:704
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.