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"
19#include "clang/Basic/SourceManager.h"
20#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
21#include "clang/StaticAnalyzer/Core/Checker.h"
22#include "clang/StaticAnalyzer/Core/CheckerManager.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
26#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
27#include "llvm/ADT/SmallSet.h"
28
29using namespace clang;
30using namespace ento;
31
32namespace {
33class UnreachableCodeChecker : public Checker<check::EndAnalysis> {
34public:
35  void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,
36                        ExprEngine &Eng) const;
37private:
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
49void 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)
74      C = LC->getAnalysisDeclContext()->getUnoptimizedCFG();
75    if (!PM)
76      PM = &LC->getParentMap();
77
78    if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
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 (CB->size() > 0 && 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;
147    PathDiagnosticLocation DL;
148    SourceLocation SL;
149    if (const Stmt *S = getUnreachableStmt(CB)) {
150      SR = S->getSourceRange();
151      DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
152      SL = DL.asLocation();
153      if (SR.isInvalid() || !SL.isValid())
154        continue;
155    }
156    else
157      continue;
158
159    // Check if the SourceLocation is in a system header
160    const SourceManager &SM = B.getSourceManager();
161    if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
162      continue;
163
164    B.EmitBasicReport(D, this, "Unreachable code", "Dead code",
165                      "This statement is never executed", DL, SR);
166  }
167}
168
169// Recursively finds the entry point(s) for this dead CFGBlock.
170void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB,
171                                                        CFGBlocksSet &reachable,
172                                                        CFGBlocksSet &visited) {
173  visited.insert(CB->getBlockID());
174
175  for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
176      I != E; ++I) {
177    if (!*I)
178      continue;
179
180    if (!reachable.count((*I)->getBlockID())) {
181      // If we find an unreachable predecessor, mark this block as reachable so
182      // we don't report this block
183      reachable.insert(CB->getBlockID());
184      if (!visited.count((*I)->getBlockID()))
185        // If we haven't previously visited the unreachable predecessor, recurse
186        FindUnreachableEntryPoints(*I, reachable, visited);
187    }
188  }
189}
190
191// Find the Stmt* in a CFGBlock for reporting a warning
192const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
193  for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
194    if (Optional<CFGStmt> S = I->getAs<CFGStmt>())
195      return S->getStmt();
196  }
197  if (const Stmt *S = CB->getTerminator())
198    return S;
199  else
200    return nullptr;
201}
202
203// Determines if the path to this CFGBlock contained an element that infers this
204// block is a false positive. We assume that FindUnreachableEntryPoints has
205// already marked only the entry points to any dead code, so we need only to
206// find the condition that led to this block (the predecessor of this block.)
207// There will never be more than one predecessor.
208bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
209                                           const ParentMap &PM) {
210  // We only expect a predecessor size of 0 or 1. If it is >1, then an external
211  // condition has broken our assumption (for example, a sink being placed by
212  // another check). In these cases, we choose not to report.
213  if (CB->pred_size() > 1)
214    return true;
215
216  // If there are no predecessors, then this block is trivially unreachable
217  if (CB->pred_size() == 0)
218    return false;
219
220  const CFGBlock *pred = *CB->pred_begin();
221  if (!pred)
222    return false;
223
224  // Get the predecessor block's terminator conditon
225  const Stmt *cond = pred->getTerminatorCondition();
226
227  //assert(cond && "CFGBlock's predecessor has a terminator condition");
228  // The previous assertion is invalid in some cases (eg do/while). Leaving
229  // reporting of these situations on at the moment to help triage these cases.
230  if (!cond)
231    return false;
232
233  // Run each of the checks on the conditions
234  return containsMacro(cond) || containsEnum(cond) ||
235         containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) ||
236         containsStmt<UnaryExprOrTypeTraitExpr>(cond);
237}
238
239// Returns true if the given CFGBlock is empty
240bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
241  return CB->getLabel() == nullptr // No labels
242      && CB->size() == 0           // No statements
243      && !CB->getTerminator();     // No terminator
244}
245
246void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
247  mgr.registerChecker<UnreachableCodeChecker>();
248}
249