summaryrefslogtreecommitdiff
path: root/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp')
-rw-r--r--clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp247
1 files changed, 247 insertions, 0 deletions
diff --git a/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
new file mode 100644
index 0000000..5a13ed0
--- /dev/null
+++ b/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
@@ -0,0 +1,247 @@
+//==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This file implements a generalized unreachable code checker using a
+// path-sensitive analysis. We mark any path visited, and then walk the CFG as a
+// post-analysis to determine what was never visited.
+//
+// A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/AST/ParentMap.h"
+#include "clang/Basic/Builtins.h"
+#include "clang/Basic/SourceManager.h"
+#include "llvm/ADT/SmallSet.h"
+
+// The number of CFGBlock pointers we want to reserve memory for. This is used
+// once for each function we analyze.
+#define DEFAULT_CFGBLOCKS 256
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+class UnreachableCodeChecker : public Checker<check::EndAnalysis> {
+public:
+ void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,
+ ExprEngine &Eng) const;
+private:
+ typedef llvm::SmallSet<unsigned, DEFAULT_CFGBLOCKS> CFGBlocksSet;
+
+ static inline const Stmt *getUnreachableStmt(const CFGBlock *CB);
+ static void FindUnreachableEntryPoints(const CFGBlock *CB,
+ CFGBlocksSet &reachable,
+ CFGBlocksSet &visited);
+ static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM);
+ static inline bool isEmptyCFGBlock(const CFGBlock *CB);
+};
+}
+
+void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G,
+ BugReporter &B,
+ ExprEngine &Eng) const {
+ CFGBlocksSet reachable, visited;
+
+ if (Eng.hasWorkRemaining())
+ return;
+
+ const Decl *D = 0;
+ CFG *C = 0;
+ ParentMap *PM = 0;
+ const LocationContext *LC = 0;
+ // Iterate over ExplodedGraph
+ for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
+ I != E; ++I) {
+ const ProgramPoint &P = I->getLocation();
+ LC = P.getLocationContext();
+
+ if (!D)
+ D = LC->getAnalysisDeclContext()->getDecl();
+ // Save the CFG if we don't have it already
+ if (!C)
+ C = LC->getAnalysisDeclContext()->getUnoptimizedCFG();
+ if (!PM)
+ PM = &LC->getParentMap();
+
+ if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
+ const CFGBlock *CB = BE->getBlock();
+ reachable.insert(CB->getBlockID());
+ }
+ }
+
+ // Bail out if we didn't get the CFG or the ParentMap.
+ if (!D || !C || !PM)
+ return;
+
+ // Don't do anything for template instantiations. Proving that code
+ // in a template instantiation is unreachable means proving that it is
+ // unreachable in all instantiations.
+ if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
+ if (FD->isTemplateInstantiation())
+ return;
+
+ // Find CFGBlocks that were not covered by any node
+ for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) {
+ const CFGBlock *CB = *I;
+ // Check if the block is unreachable
+ if (reachable.count(CB->getBlockID()))
+ continue;
+
+ // Check if the block is empty (an artificial block)
+ if (isEmptyCFGBlock(CB))
+ continue;
+
+ // Find the entry points for this block
+ if (!visited.count(CB->getBlockID()))
+ FindUnreachableEntryPoints(CB, reachable, visited);
+
+ // This block may have been pruned; check if we still want to report it
+ if (reachable.count(CB->getBlockID()))
+ continue;
+
+ // Check for false positives
+ if (CB->size() > 0 && isInvalidPath(CB, *PM))
+ continue;
+
+ // It is good practice to always have a "default" label in a "switch", even
+ // if we should never get there. It can be used to detect errors, for
+ // instance. Unreachable code directly under a "default" label is therefore
+ // likely to be a false positive.
+ if (const Stmt *label = CB->getLabel())
+ if (label->getStmtClass() == Stmt::DefaultStmtClass)
+ continue;
+
+ // Special case for __builtin_unreachable.
+ // FIXME: This should be extended to include other unreachable markers,
+ // such as llvm_unreachable.
+ if (!CB->empty()) {
+ bool foundUnreachable = false;
+ for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
+ ci != ce; ++ci) {
+ if (const CFGStmt *S = (*ci).getAs<CFGStmt>())
+ if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
+ if (CE->isBuiltinCall() == Builtin::BI__builtin_unreachable) {
+ foundUnreachable = true;
+ break;
+ }
+ }
+ }
+ if (foundUnreachable)
+ continue;
+ }
+
+ // We found a block that wasn't covered - find the statement to report
+ SourceRange SR;
+ PathDiagnosticLocation DL;
+ SourceLocation SL;
+ if (const Stmt *S = getUnreachableStmt(CB)) {
+ SR = S->getSourceRange();
+ DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
+ SL = DL.asLocation();
+ if (SR.isInvalid() || !SL.isValid())
+ continue;
+ }
+ else
+ continue;
+
+ // Check if the SourceLocation is in a system header
+ const SourceManager &SM = B.getSourceManager();
+ if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
+ continue;
+
+ B.EmitBasicReport(D, "Unreachable code", "Dead code",
+ "This statement is never executed", DL, SR);
+ }
+}
+
+// Recursively finds the entry point(s) for this dead CFGBlock.
+void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB,
+ CFGBlocksSet &reachable,
+ CFGBlocksSet &visited) {
+ visited.insert(CB->getBlockID());
+
+ for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
+ I != E; ++I) {
+ if (!reachable.count((*I)->getBlockID())) {
+ // If we find an unreachable predecessor, mark this block as reachable so
+ // we don't report this block
+ reachable.insert(CB->getBlockID());
+ if (!visited.count((*I)->getBlockID()))
+ // If we haven't previously visited the unreachable predecessor, recurse
+ FindUnreachableEntryPoints(*I, reachable, visited);
+ }
+ }
+}
+
+// Find the Stmt* in a CFGBlock for reporting a warning
+const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
+ for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
+ if (const CFGStmt *S = I->getAs<CFGStmt>())
+ return S->getStmt();
+ }
+ if (const Stmt *S = CB->getTerminator())
+ return S;
+ else
+ return 0;
+}
+
+// Determines if the path to this CFGBlock contained an element that infers this
+// block is a false positive. We assume that FindUnreachableEntryPoints has
+// already marked only the entry points to any dead code, so we need only to
+// find the condition that led to this block (the predecessor of this block.)
+// There will never be more than one predecessor.
+bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
+ const ParentMap &PM) {
+ // We only expect a predecessor size of 0 or 1. If it is >1, then an external
+ // condition has broken our assumption (for example, a sink being placed by
+ // another check). In these cases, we choose not to report.
+ if (CB->pred_size() > 1)
+ return true;
+
+ // If there are no predecessors, then this block is trivially unreachable
+ if (CB->pred_size() == 0)
+ return false;
+
+ const CFGBlock *pred = *CB->pred_begin();
+
+ // Get the predecessor block's terminator conditon
+ const Stmt *cond = pred->getTerminatorCondition();
+
+ //assert(cond && "CFGBlock's predecessor has a terminator condition");
+ // The previous assertion is invalid in some cases (eg do/while). Leaving
+ // reporting of these situations on at the moment to help triage these cases.
+ if (!cond)
+ return false;
+
+ // Run each of the checks on the conditions
+ if (containsMacro(cond) || containsEnum(cond)
+ || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond)
+ || containsStmt<UnaryExprOrTypeTraitExpr>(cond))
+ return true;
+
+ return false;
+}
+
+// Returns true if the given CFGBlock is empty
+bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
+ return CB->getLabel() == 0 // No labels
+ && CB->size() == 0 // No statements
+ && CB->getTerminator() == 0; // No terminator
+}
+
+void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
+ mgr.registerChecker<UnreachableCodeChecker>();
+}