1e5dd7070Spatrick //==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==//
2e5dd7070Spatrick //
3e5dd7070Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4e5dd7070Spatrick // See https://llvm.org/LICENSE.txt for license information.
5e5dd7070Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6e5dd7070Spatrick //
7e5dd7070Spatrick //===----------------------------------------------------------------------===//
8e5dd7070Spatrick // This file implements a generalized unreachable code checker using a
9e5dd7070Spatrick // path-sensitive analysis. We mark any path visited, and then walk the CFG as a
10e5dd7070Spatrick // post-analysis to determine what was never visited.
11e5dd7070Spatrick //
12e5dd7070Spatrick // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp
13e5dd7070Spatrick //===----------------------------------------------------------------------===//
14e5dd7070Spatrick
15e5dd7070Spatrick #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16e5dd7070Spatrick #include "clang/AST/ParentMap.h"
17e5dd7070Spatrick #include "clang/Basic/Builtins.h"
18e5dd7070Spatrick #include "clang/Basic/SourceManager.h"
19e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
20e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/Checker.h"
21e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/CheckerManager.h"
22e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
23e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
24e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
25e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
26e5dd7070Spatrick #include "llvm/ADT/SmallSet.h"
27*12c85518Srobert #include <optional>
28e5dd7070Spatrick
29e5dd7070Spatrick using namespace clang;
30e5dd7070Spatrick using namespace ento;
31e5dd7070Spatrick
32e5dd7070Spatrick namespace {
33e5dd7070Spatrick class UnreachableCodeChecker : public Checker<check::EndAnalysis> {
34e5dd7070Spatrick public:
35e5dd7070Spatrick void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,
36e5dd7070Spatrick ExprEngine &Eng) const;
37e5dd7070Spatrick private:
38e5dd7070Spatrick typedef llvm::SmallSet<unsigned, 32> CFGBlocksSet;
39e5dd7070Spatrick
40e5dd7070Spatrick static inline const Stmt *getUnreachableStmt(const CFGBlock *CB);
41e5dd7070Spatrick static void FindUnreachableEntryPoints(const CFGBlock *CB,
42e5dd7070Spatrick CFGBlocksSet &reachable,
43e5dd7070Spatrick CFGBlocksSet &visited);
44e5dd7070Spatrick static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM);
45e5dd7070Spatrick static inline bool isEmptyCFGBlock(const CFGBlock *CB);
46e5dd7070Spatrick };
47e5dd7070Spatrick }
48e5dd7070Spatrick
checkEndAnalysis(ExplodedGraph & G,BugReporter & B,ExprEngine & Eng) const49e5dd7070Spatrick void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G,
50e5dd7070Spatrick BugReporter &B,
51e5dd7070Spatrick ExprEngine &Eng) const {
52e5dd7070Spatrick CFGBlocksSet reachable, visited;
53e5dd7070Spatrick
54e5dd7070Spatrick if (Eng.hasWorkRemaining())
55e5dd7070Spatrick return;
56e5dd7070Spatrick
57e5dd7070Spatrick const Decl *D = nullptr;
58e5dd7070Spatrick CFG *C = nullptr;
59e5dd7070Spatrick const ParentMap *PM = nullptr;
60e5dd7070Spatrick const LocationContext *LC = nullptr;
61e5dd7070Spatrick // Iterate over ExplodedGraph
62e5dd7070Spatrick for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
63e5dd7070Spatrick I != E; ++I) {
64e5dd7070Spatrick const ProgramPoint &P = I->getLocation();
65e5dd7070Spatrick LC = P.getLocationContext();
66e5dd7070Spatrick if (!LC->inTopFrame())
67e5dd7070Spatrick continue;
68e5dd7070Spatrick
69e5dd7070Spatrick if (!D)
70e5dd7070Spatrick D = LC->getAnalysisDeclContext()->getDecl();
71e5dd7070Spatrick
72e5dd7070Spatrick // Save the CFG if we don't have it already
73e5dd7070Spatrick if (!C)
74e5dd7070Spatrick C = LC->getAnalysisDeclContext()->getUnoptimizedCFG();
75e5dd7070Spatrick if (!PM)
76e5dd7070Spatrick PM = &LC->getParentMap();
77e5dd7070Spatrick
78*12c85518Srobert if (std::optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
79e5dd7070Spatrick const CFGBlock *CB = BE->getBlock();
80e5dd7070Spatrick reachable.insert(CB->getBlockID());
81e5dd7070Spatrick }
82e5dd7070Spatrick }
83e5dd7070Spatrick
84e5dd7070Spatrick // Bail out if we didn't get the CFG or the ParentMap.
85e5dd7070Spatrick if (!D || !C || !PM)
86e5dd7070Spatrick return;
87e5dd7070Spatrick
88e5dd7070Spatrick // Don't do anything for template instantiations. Proving that code
89e5dd7070Spatrick // in a template instantiation is unreachable means proving that it is
90e5dd7070Spatrick // unreachable in all instantiations.
91e5dd7070Spatrick if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
92e5dd7070Spatrick if (FD->isTemplateInstantiation())
93e5dd7070Spatrick return;
94e5dd7070Spatrick
95e5dd7070Spatrick // Find CFGBlocks that were not covered by any node
96e5dd7070Spatrick for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) {
97e5dd7070Spatrick const CFGBlock *CB = *I;
98e5dd7070Spatrick // Check if the block is unreachable
99e5dd7070Spatrick if (reachable.count(CB->getBlockID()))
100e5dd7070Spatrick continue;
101e5dd7070Spatrick
102e5dd7070Spatrick // Check if the block is empty (an artificial block)
103e5dd7070Spatrick if (isEmptyCFGBlock(CB))
104e5dd7070Spatrick continue;
105e5dd7070Spatrick
106e5dd7070Spatrick // Find the entry points for this block
107e5dd7070Spatrick if (!visited.count(CB->getBlockID()))
108e5dd7070Spatrick FindUnreachableEntryPoints(CB, reachable, visited);
109e5dd7070Spatrick
110e5dd7070Spatrick // This block may have been pruned; check if we still want to report it
111e5dd7070Spatrick if (reachable.count(CB->getBlockID()))
112e5dd7070Spatrick continue;
113e5dd7070Spatrick
114e5dd7070Spatrick // Check for false positives
115e5dd7070Spatrick if (isInvalidPath(CB, *PM))
116e5dd7070Spatrick continue;
117e5dd7070Spatrick
118e5dd7070Spatrick // It is good practice to always have a "default" label in a "switch", even
119e5dd7070Spatrick // if we should never get there. It can be used to detect errors, for
120e5dd7070Spatrick // instance. Unreachable code directly under a "default" label is therefore
121e5dd7070Spatrick // likely to be a false positive.
122e5dd7070Spatrick if (const Stmt *label = CB->getLabel())
123e5dd7070Spatrick if (label->getStmtClass() == Stmt::DefaultStmtClass)
124e5dd7070Spatrick continue;
125e5dd7070Spatrick
126e5dd7070Spatrick // Special case for __builtin_unreachable.
127e5dd7070Spatrick // FIXME: This should be extended to include other unreachable markers,
128e5dd7070Spatrick // such as llvm_unreachable.
129e5dd7070Spatrick if (!CB->empty()) {
130e5dd7070Spatrick bool foundUnreachable = false;
131e5dd7070Spatrick for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
132e5dd7070Spatrick ci != ce; ++ci) {
133*12c85518Srobert if (std::optional<CFGStmt> S = (*ci).getAs<CFGStmt>())
134e5dd7070Spatrick if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
135e5dd7070Spatrick if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable ||
136e5dd7070Spatrick CE->isBuiltinAssumeFalse(Eng.getContext())) {
137e5dd7070Spatrick foundUnreachable = true;
138e5dd7070Spatrick break;
139e5dd7070Spatrick }
140e5dd7070Spatrick }
141e5dd7070Spatrick }
142e5dd7070Spatrick if (foundUnreachable)
143e5dd7070Spatrick continue;
144e5dd7070Spatrick }
145e5dd7070Spatrick
146e5dd7070Spatrick // We found a block that wasn't covered - find the statement to report
147e5dd7070Spatrick SourceRange SR;
148e5dd7070Spatrick PathDiagnosticLocation DL;
149e5dd7070Spatrick SourceLocation SL;
150e5dd7070Spatrick if (const Stmt *S = getUnreachableStmt(CB)) {
151e5dd7070Spatrick // In macros, 'do {...} while (0)' is often used. Don't warn about the
152e5dd7070Spatrick // condition 0 when it is unreachable.
153e5dd7070Spatrick if (S->getBeginLoc().isMacroID())
154e5dd7070Spatrick if (const auto *I = dyn_cast<IntegerLiteral>(S))
155e5dd7070Spatrick if (I->getValue() == 0ULL)
156e5dd7070Spatrick if (const Stmt *Parent = PM->getParent(S))
157e5dd7070Spatrick if (isa<DoStmt>(Parent))
158e5dd7070Spatrick continue;
159e5dd7070Spatrick SR = S->getSourceRange();
160e5dd7070Spatrick DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
161e5dd7070Spatrick SL = DL.asLocation();
162e5dd7070Spatrick if (SR.isInvalid() || !SL.isValid())
163e5dd7070Spatrick continue;
164e5dd7070Spatrick }
165e5dd7070Spatrick else
166e5dd7070Spatrick continue;
167e5dd7070Spatrick
168e5dd7070Spatrick // Check if the SourceLocation is in a system header
169e5dd7070Spatrick const SourceManager &SM = B.getSourceManager();
170e5dd7070Spatrick if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
171e5dd7070Spatrick continue;
172e5dd7070Spatrick
173a9ac8606Spatrick B.EmitBasicReport(D, this, "Unreachable code", categories::UnusedCode,
174e5dd7070Spatrick "This statement is never executed", DL, SR);
175e5dd7070Spatrick }
176e5dd7070Spatrick }
177e5dd7070Spatrick
178e5dd7070Spatrick // Recursively finds the entry point(s) for this dead CFGBlock.
FindUnreachableEntryPoints(const CFGBlock * CB,CFGBlocksSet & reachable,CFGBlocksSet & visited)179e5dd7070Spatrick void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB,
180e5dd7070Spatrick CFGBlocksSet &reachable,
181e5dd7070Spatrick CFGBlocksSet &visited) {
182e5dd7070Spatrick visited.insert(CB->getBlockID());
183e5dd7070Spatrick
184e5dd7070Spatrick for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
185e5dd7070Spatrick I != E; ++I) {
186e5dd7070Spatrick if (!*I)
187e5dd7070Spatrick continue;
188e5dd7070Spatrick
189e5dd7070Spatrick if (!reachable.count((*I)->getBlockID())) {
190e5dd7070Spatrick // If we find an unreachable predecessor, mark this block as reachable so
191e5dd7070Spatrick // we don't report this block
192e5dd7070Spatrick reachable.insert(CB->getBlockID());
193e5dd7070Spatrick if (!visited.count((*I)->getBlockID()))
194e5dd7070Spatrick // If we haven't previously visited the unreachable predecessor, recurse
195e5dd7070Spatrick FindUnreachableEntryPoints(*I, reachable, visited);
196e5dd7070Spatrick }
197e5dd7070Spatrick }
198e5dd7070Spatrick }
199e5dd7070Spatrick
200e5dd7070Spatrick // Find the Stmt* in a CFGBlock for reporting a warning
getUnreachableStmt(const CFGBlock * CB)201e5dd7070Spatrick const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
202e5dd7070Spatrick for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
203*12c85518Srobert if (std::optional<CFGStmt> S = I->getAs<CFGStmt>()) {
204e5dd7070Spatrick if (!isa<DeclStmt>(S->getStmt()))
205e5dd7070Spatrick return S->getStmt();
206e5dd7070Spatrick }
207e5dd7070Spatrick }
208e5dd7070Spatrick if (const Stmt *S = CB->getTerminatorStmt())
209e5dd7070Spatrick return S;
210e5dd7070Spatrick else
211e5dd7070Spatrick return nullptr;
212e5dd7070Spatrick }
213e5dd7070Spatrick
214e5dd7070Spatrick // Determines if the path to this CFGBlock contained an element that infers this
215e5dd7070Spatrick // block is a false positive. We assume that FindUnreachableEntryPoints has
216e5dd7070Spatrick // already marked only the entry points to any dead code, so we need only to
217e5dd7070Spatrick // find the condition that led to this block (the predecessor of this block.)
218e5dd7070Spatrick // There will never be more than one predecessor.
isInvalidPath(const CFGBlock * CB,const ParentMap & PM)219e5dd7070Spatrick bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
220e5dd7070Spatrick const ParentMap &PM) {
221e5dd7070Spatrick // We only expect a predecessor size of 0 or 1. If it is >1, then an external
222e5dd7070Spatrick // condition has broken our assumption (for example, a sink being placed by
223e5dd7070Spatrick // another check). In these cases, we choose not to report.
224e5dd7070Spatrick if (CB->pred_size() > 1)
225e5dd7070Spatrick return true;
226e5dd7070Spatrick
227e5dd7070Spatrick // If there are no predecessors, then this block is trivially unreachable
228e5dd7070Spatrick if (CB->pred_size() == 0)
229e5dd7070Spatrick return false;
230e5dd7070Spatrick
231e5dd7070Spatrick const CFGBlock *pred = *CB->pred_begin();
232e5dd7070Spatrick if (!pred)
233e5dd7070Spatrick return false;
234e5dd7070Spatrick
235e5dd7070Spatrick // Get the predecessor block's terminator condition
236e5dd7070Spatrick const Stmt *cond = pred->getTerminatorCondition();
237e5dd7070Spatrick
238e5dd7070Spatrick //assert(cond && "CFGBlock's predecessor has a terminator condition");
239e5dd7070Spatrick // The previous assertion is invalid in some cases (eg do/while). Leaving
240e5dd7070Spatrick // reporting of these situations on at the moment to help triage these cases.
241e5dd7070Spatrick if (!cond)
242e5dd7070Spatrick return false;
243e5dd7070Spatrick
244e5dd7070Spatrick // Run each of the checks on the conditions
245e5dd7070Spatrick return containsMacro(cond) || containsEnum(cond) ||
246e5dd7070Spatrick containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) ||
247e5dd7070Spatrick containsStmt<UnaryExprOrTypeTraitExpr>(cond);
248e5dd7070Spatrick }
249e5dd7070Spatrick
250e5dd7070Spatrick // Returns true if the given CFGBlock is empty
isEmptyCFGBlock(const CFGBlock * CB)251e5dd7070Spatrick bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
252e5dd7070Spatrick return CB->getLabel() == nullptr // No labels
253e5dd7070Spatrick && CB->size() == 0 // No statements
254e5dd7070Spatrick && !CB->getTerminatorStmt(); // No terminator
255e5dd7070Spatrick }
256e5dd7070Spatrick
registerUnreachableCodeChecker(CheckerManager & mgr)257e5dd7070Spatrick void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
258e5dd7070Spatrick mgr.registerChecker<UnreachableCodeChecker>();
259e5dd7070Spatrick }
260e5dd7070Spatrick
shouldRegisterUnreachableCodeChecker(const CheckerManager & mgr)261ec727ea7Spatrick bool ento::shouldRegisterUnreachableCodeChecker(const CheckerManager &mgr) {
262e5dd7070Spatrick return true;
263e5dd7070Spatrick }
264