clang  14.0.0git
UnreachableCodeChecker.cpp
Go to the documentation of this file.
1 //==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==//
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 // This file implements a generalized unreachable code checker using a
9 // path-sensitive analysis. We mark any path visited, and then walk the CFG as a
10 // post-analysis to determine what was never visited.
11 //
12 // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp
13 //===----------------------------------------------------------------------===//
14 
16 #include "clang/AST/ParentMap.h"
17 #include "clang/Basic/Builtins.h"
26 #include "llvm/ADT/SmallSet.h"
27 
28 using namespace clang;
29 using namespace ento;
30 
31 namespace {
32 class UnreachableCodeChecker : public Checker<check::EndAnalysis> {
33 public:
34  void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,
35  ExprEngine &Eng) const;
36 private:
37  typedef llvm::SmallSet<unsigned, 32> CFGBlocksSet;
38 
39  static inline const Stmt *getUnreachableStmt(const CFGBlock *CB);
40  static void FindUnreachableEntryPoints(const CFGBlock *CB,
41  CFGBlocksSet &reachable,
42  CFGBlocksSet &visited);
43  static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM);
44  static inline bool isEmptyCFGBlock(const CFGBlock *CB);
45 };
46 }
47 
48 void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G,
49  BugReporter &B,
50  ExprEngine &Eng) const {
51  CFGBlocksSet reachable, visited;
52 
53  if (Eng.hasWorkRemaining())
54  return;
55 
56  const Decl *D = nullptr;
57  CFG *C = nullptr;
58  const ParentMap *PM = nullptr;
59  const LocationContext *LC = nullptr;
60  // Iterate over ExplodedGraph
61  for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
62  I != E; ++I) {
63  const ProgramPoint &P = I->getLocation();
64  LC = P.getLocationContext();
65  if (!LC->inTopFrame())
66  continue;
67 
68  if (!D)
69  D = LC->getAnalysisDeclContext()->getDecl();
70 
71  // Save the CFG if we don't have it already
72  if (!C)
74  if (!PM)
75  PM = &LC->getParentMap();
76 
77  if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
78  const CFGBlock *CB = BE->getBlock();
79  reachable.insert(CB->getBlockID());
80  }
81  }
82 
83  // Bail out if we didn't get the CFG or the ParentMap.
84  if (!D || !C || !PM)
85  return;
86 
87  // Don't do anything for template instantiations. Proving that code
88  // in a template instantiation is unreachable means proving that it is
89  // unreachable in all instantiations.
90  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
91  if (FD->isTemplateInstantiation())
92  return;
93 
94  // Find CFGBlocks that were not covered by any node
95  for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) {
96  const CFGBlock *CB = *I;
97  // Check if the block is unreachable
98  if (reachable.count(CB->getBlockID()))
99  continue;
100 
101  // Check if the block is empty (an artificial block)
102  if (isEmptyCFGBlock(CB))
103  continue;
104 
105  // Find the entry points for this block
106  if (!visited.count(CB->getBlockID()))
107  FindUnreachableEntryPoints(CB, reachable, visited);
108 
109  // This block may have been pruned; check if we still want to report it
110  if (reachable.count(CB->getBlockID()))
111  continue;
112 
113  // Check for false positives
114  if (isInvalidPath(CB, *PM))
115  continue;
116 
117  // It is good practice to always have a "default" label in a "switch", even
118  // if we should never get there. It can be used to detect errors, for
119  // instance. Unreachable code directly under a "default" label is therefore
120  // likely to be a false positive.
121  if (const Stmt *label = CB->getLabel())
122  if (label->getStmtClass() == Stmt::DefaultStmtClass)
123  continue;
124 
125  // Special case for __builtin_unreachable.
126  // FIXME: This should be extended to include other unreachable markers,
127  // such as llvm_unreachable.
128  if (!CB->empty()) {
129  bool foundUnreachable = false;
130  for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
131  ci != ce; ++ci) {
132  if (Optional<CFGStmt> S = (*ci).getAs<CFGStmt>())
133  if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
134  if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable ||
135  CE->isBuiltinAssumeFalse(Eng.getContext())) {
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;
147  PathDiagnosticLocation DL;
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->getBeginLoc().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();
159  DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
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", categories::UnusedCode,
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->getTerminatorStmt())
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 condition
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->getTerminatorStmt(); // No terminator
254 }
255 
256 void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
257  mgr.registerChecker<UnreachableCodeChecker>();
258 }
259 
260 bool ento::shouldRegisterUnreachableCodeChecker(const CheckerManager &mgr) {
261  return true;
262 }
Builtins.h
clang::SourceRange::isInvalid
bool isInvalid() const
Definition: SourceLocation.h:228
clang::LocationContext
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
Definition: AnalysisDeclContext.h:215
clang::CFGBlock::begin
iterator begin()
Definition: CFG.h:875
SVals.h
clang::SourceRange
A trivial tuple used to represent a source range.
Definition: SourceLocation.h:212
clang::CFGBlock::empty
bool empty() const
Definition: CFG.h:918
clang::SourceLocation
Encodes a location in the source.
Definition: SourceLocation.h:88
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1074
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:54
llvm::Optional
Definition: LLVM.h:40
clang::ento::containsStaticLocal
bool containsStaticLocal(const Stmt *S)
Definition: CheckerHelpers.cpp:52
SourceManager.h
clang::ento::containsBuiltinOffsetOf
bool containsBuiltinOffsetOf(const Stmt *S)
Definition: CheckerHelpers.cpp:68
clang::CFG
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1225
clang::SourceManager
This class handles loading and caching of source files into memory.
Definition: SourceManager.h:626
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
BuiltinCheckerRegistration.h
clang::LocationContext::getAnalysisDeclContext
AnalysisDeclContext * getAnalysisDeclContext() const
Definition: AnalysisDeclContext.h:241
CheckerManager.h
BugReporter.h
clang::LocationContext::inTopFrame
virtual bool inTopFrame() const
Definition: AnalysisDeclContext.cpp:473
clang::CFGBlock::size
unsigned size() const
Definition: CFG.h:917
clang::CFGBlock::const_iterator
ElementList::const_iterator const_iterator
Definition: CFG.h:866
clang::CFGBlock::getTerminatorCondition
Stmt * getTerminatorCondition(bool StripParens=true)
Definition: CFG.cpp:6077
clang::ento::categories::UnusedCode
const char *const UnusedCode
Definition: CommonBugCategories.cpp:25
ExplodedGraph.h
clang::AnalysisDeclContext::getUnoptimizedCFG
CFG * getUnoptimizedCFG()
Definition: AnalysisDeclContext.cpp:232
clang::ento::ExplodedGraph::node_iterator
AllNodesTy::iterator node_iterator
Definition: ExplodedGraph.h:397
clang::BlockEntrance
Definition: ProgramPoint.h:225
clang::ParentMap
Definition: ParentMap.h:20
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::CFGStmt
Definition: CFG.h:132
clang::CFGBlock::getLabel
Stmt * getLabel()
Definition: CFG.h:1069
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
clang::CFGBlock::pred_begin
pred_iterator pred_begin()
Definition: CFG.h:937
clang::CFGBlock::pred_size
unsigned pred_size() const
Definition: CFG.h:976
clang::ParentMap::getParent
Stmt * getParent(Stmt *) const
Definition: ParentMap.cpp:134
CheckerContext.h
Checker.h
ParentMap.h
clang
Definition: CalledOnceCheck.h:17
clang::ento::containsEnum
bool containsEnum(const Stmt *S)
Definition: CheckerHelpers.cpp:38
clang::AnalysisDeclContext::getDecl
const Decl * getDecl() const
Definition: AnalysisDeclContext.h:106
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:69
clang::CFGBlock::getTerminatorStmt
Stmt * getTerminatorStmt()
Definition: CFG.h:1050
CheckerHelpers.h
clang::SourceLocation::isValid
bool isValid() const
Return true if this is a valid SourceLocation object.
Definition: SourceLocation.h:112
clang::ento::PathDiagnosticLocation::createBegin
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
Definition: PathDiagnostic.cpp:580
Parent
NodeId Parent
Definition: ASTDiff.cpp:192
clang::CFGBlock::end
iterator end()
Definition: CFG.h:876
SM
#define SM(sm)
Definition: Cuda.cpp:78
clang::ento::containsMacro
bool containsMacro(const Stmt *S)
Definition: CheckerHelpers.cpp:23
clang::FunctionDecl
Represents a function declaration or definition.
Definition: Decl.h:1856
clang::ProgramPoint
Definition: ProgramPoint.h:59
clang::CallExpr
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2795
clang::CFGBlock::pred_end
pred_iterator pred_end()
Definition: CFG.h:938
clang::LocationContext::getParentMap
const ParentMap & getParentMap() const
Definition: AnalysisDeclContext.h:253
clang::CFGBlock::const_pred_iterator
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:924