Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
Line
Count
Source (jump to first uncovered line)
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
15
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16
#include "clang/AST/ParentMap.h"
17
#include "clang/Basic/Builtins.h"
18
#include "clang/Basic/SourceManager.h"
19
#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
20
#include "clang/StaticAnalyzer/Core/Checker.h"
21
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
22
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
23
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
24
#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
25
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.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
340
                                              ExprEngine &Eng) const {
51
340
  CFGBlocksSet reachable, visited;
52
340
53
340
  if (Eng.hasWorkRemaining())
54
5
    return;
55
335
56
335
  const Decl *D = nullptr;
57
335
  CFG *C = nullptr;
58
335
  ParentMap *PM = nullptr;
59
335
  const LocationContext *LC = nullptr;
60
335
  // Iterate over ExplodedGraph
61
335
  for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
62
15.0k
      I != E; 
++I14.7k
) {
63
14.7k
    const ProgramPoint &P = I->getLocation();
64
14.7k
    LC = P.getLocationContext();
65
14.7k
    if (!LC->inTopFrame())
66
1.22k
      continue;
67
13.4k
68
13.4k
    if (!D)
69
335
      D = LC->getAnalysisDeclContext()->getDecl();
70
13.4k
71
13.4k
    // Save the CFG if we don't have it already
72
13.4k
    if (!C)
73
335
      C = LC->getAnalysisDeclContext()->getUnoptimizedCFG();
74
13.4k
    if (!PM)
75
335
      PM = &LC->getParentMap();
76
13.4k
77
13.4k
    if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
78
542
      const CFGBlock *CB = BE->getBlock();
79
542
      reachable.insert(CB->getBlockID());
80
542
    }
81
13.4k
  }
82
335
83
335
  // Bail out if we didn't get the CFG or the ParentMap.
84
335
  if (!D || !C || !PM)
85
0
    return;
86
335
87
335
  // Don't do anything for template instantiations.  Proving that code
88
335
  // in a template instantiation is unreachable means proving that it is
89
335
  // unreachable in all instantiations.
90
335
  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
91
335
    if (FD->isTemplateInstantiation())
92
0
      return;
93
335
94
335
  // Find CFGBlocks that were not covered by any node
95
1.54k
  
for (CFG::const_iterator I = C->begin(), E = C->end(); 335
I != E;
++I1.21k
) {
96
1.21k
    const CFGBlock *CB = *I;
97
1.21k
    // Check if the block is unreachable
98
1.21k
    if (reachable.count(CB->getBlockID()))
99
508
      continue;
100
703
101
703
    // Check if the block is empty (an artificial block)
102
703
    if (isEmptyCFGBlock(CB))
103
672
      continue;
104
31
105
31
    // Find the entry points for this block
106
31
    if (!visited.count(CB->getBlockID()))
107
24
      FindUnreachableEntryPoints(CB, reachable, visited);
108
31
109
31
    // This block may have been pruned; check if we still want to report it
110
31
    if (reachable.count(CB->getBlockID()))
111
7
      continue;
112
24
113
24
    // Check for false positives
114
24
    if (isInvalidPath(CB, *PM))
115
4
      continue;
116
20
117
20
    // It is good practice to always have a "default" label in a "switch", even
118
20
    // if we should never get there. It can be used to detect errors, for
119
20
    // instance. Unreachable code directly under a "default" label is therefore
120
20
    // likely to be a false positive.
121
20
    if (const Stmt *label = CB->getLabel())
122
2
      if (label->getStmtClass() == Stmt::DefaultStmtClass)
123
1
        continue;
124
19
125
19
    // Special case for __builtin_unreachable.
126
19
    // FIXME: This should be extended to include other unreachable markers,
127
19
    // such as llvm_unreachable.
128
19
    if (!CB->empty()) {
129
16
      bool foundUnreachable = false;
130
16
      for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
131
76
           ci != ce; 
++ci60
) {
132
62
        if (Optional<CFGStmt> S = (*ci).getAs<CFGStmt>())
133
62
          if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
134
8
            if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable ||
135
8
                
CE->isBuiltinAssumeFalse(Eng.getContext())7
) {
136
2
              foundUnreachable = true;
137
2
              break;
138
2
            }
139
8
          }
140
62
      }
141
16
      if (foundUnreachable)
142
2
        continue;
143
17
    }
144
17
145
17
    // We found a block that wasn't covered - find the statement to report
146
17
    SourceRange SR;
147
17
    PathDiagnosticLocation DL;
148
17
    SourceLocation SL;
149
17
    if (const Stmt *S = getUnreachableStmt(CB)) {
150
16
      // In macros, 'do {...} while (0)' is often used. Don't warn about the
151
16
      // condition 0 when it is unreachable.
152
16
      if (S->getBeginLoc().isMacroID())
153
1
        if (const auto *I = dyn_cast<IntegerLiteral>(S))
154
1
          if (I->getValue() == 0ULL)
155
1
            if (const Stmt *Parent = PM->getParent(S))
156
1
              if (isa<DoStmt>(Parent))
157
1
                continue;
158
15
      SR = S->getSourceRange();
159
15
      DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
160
15
      SL = DL.asLocation();
161
15
      if (SR.isInvalid() || !SL.isValid())
162
0
        continue;
163
1
    }
164
1
    else
165
1
      continue;
166
15
167
15
    // Check if the SourceLocation is in a system header
168
15
    const SourceManager &SM = B.getSourceManager();
169
15
    if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
170
0
      continue;
171
15
172
15
    B.EmitBasicReport(D, this, "Unreachable code", "Dead code",
173
15
                      "This statement is never executed", DL, SR);
174
15
  }
175
335
}
176
177
// Recursively finds the entry point(s) for this dead CFGBlock.
178
void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB,
179
                                                        CFGBlocksSet &reachable,
180
34
                                                        CFGBlocksSet &visited) {
181
34
  visited.insert(CB->getBlockID());
182
34
183
34
  for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
184
62
      I != E; 
++I28
) {
185
28
    if (!*I)
186
2
      continue;
187
26
188
26
    if (!reachable.count((*I)->getBlockID())) {
189
12
      // If we find an unreachable predecessor, mark this block as reachable so
190
12
      // we don't report this block
191
12
      reachable.insert(CB->getBlockID());
192
12
      if (!visited.count((*I)->getBlockID()))
193
10
        // If we haven't previously visited the unreachable predecessor, recurse
194
10
        FindUnreachableEntryPoints(*I, reachable, visited);
195
12
    }
196
26
  }
197
34
}
198
199
// Find the Stmt* in a CFGBlock for reporting a warning
200
17
const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
201
18
  for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; 
++I1
) {
202
14
    if (Optional<CFGStmt> S = I->getAs<CFGStmt>()) {
203
14
      if (!isa<DeclStmt>(S->getStmt()))
204
13
        return S->getStmt();
205
14
    }
206
14
  }
207
17
  
if (const Stmt *4
S4
= CB->getTerminatorStmt())
208
3
    return S;
209
1
  else
210
1
    return nullptr;
211
4
}
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
24
                                           const ParentMap &PM) {
220
24
  // We only expect a predecessor size of 0 or 1. If it is >1, then an external
221
24
  // condition has broken our assumption (for example, a sink being placed by
222
24
  // another check). In these cases, we choose not to report.
223
24
  if (CB->pred_size() > 1)
224
0
    return true;
225
24
226
24
  // If there are no predecessors, then this block is trivially unreachable
227
24
  if (CB->pred_size() == 0)
228
8
    return false;
229
16
230
16
  const CFGBlock *pred = *CB->pred_begin();
231
16
  if (!pred)
232
2
    return false;
233
14
234
14
  // Get the predecessor block's terminator condition
235
14
  const Stmt *cond = pred->getTerminatorCondition();
236
14
237
14
  //assert(cond && "CFGBlock's predecessor has a terminator condition");
238
14
  // The previous assertion is invalid in some cases (eg do/while). Leaving
239
14
  // reporting of these situations on at the moment to help triage these cases.
240
14
  if (!cond)
241
1
    return false;
242
13
243
13
  // Run each of the checks on the conditions
244
13
  return containsMacro(cond) || 
containsEnum(cond)11
||
245
13
         
containsStaticLocal(cond)11
||
containsBuiltinOffsetOf(cond)10
||
246
13
         
containsStmt<UnaryExprOrTypeTraitExpr>(cond)10
;
247
13
}
248
249
// Returns true if the given CFGBlock is empty
250
703
bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
251
703
  return CB->getLabel() == nullptr // No labels
252
703
      && 
CB->size() == 0699
// No statements
253
703
      && 
!CB->getTerminatorStmt()675
; // No terminator
254
703
}
255
256
9
void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
257
9
  mgr.registerChecker<UnreachableCodeChecker>();
258
9
}
259
260
9
bool ento::shouldRegisterUnreachableCodeChecker(const LangOptions &LO) {
261
9
  return true;
262
9
}