Added an path-sensitive unreachable code checker to the experimental analyzer checks.
- Created a new class to do post-analysis
- Updated several test cases with unreachable code to expect a warning
- Added some general tests
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@109286 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Checker/UnreachableCodeChecker.cpp b/lib/Checker/UnreachableCodeChecker.cpp
new file mode 100644
index 0000000..0af49a3
--- /dev/null
+++ b/lib/Checker/UnreachableCodeChecker.cpp
@@ -0,0 +1,143 @@
+//==- 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/UnreachableCode.cpp
+//===----------------------------------------------------------------------===//
+
+#include "clang/Checker/PathSensitive/CheckerVisitor.h"
+#include "clang/Checker/PathSensitive/ExplodedGraph.h"
+#include "clang/Checker/PathSensitive/SVals.h"
+#include "clang/Checker/BugReporter/BugReporter.h"
+#include "GRExprEngineExperimentalChecks.h"
+#include "clang/AST/StmtCXX.h"
+#include "llvm/ADT/SmallPtrSet.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;
+
+namespace {
+class UnreachableCodeChecker : public CheckerVisitor<UnreachableCodeChecker> {
+public:
+ static void *getTag();
+ void VisitEndAnalysis(ExplodedGraph &G, BugReporter &B,
+ bool hasWorkRemaining);
+private:
+ static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R);
+ void FindUnreachableEntryPoints(const CFGBlock *CB);
+ void MarkSuccessorsReachable(const CFGBlock *CB);
+
+ llvm::SmallPtrSet<const CFGBlock*, DEFAULT_CFGBLOCKS> reachable;
+ llvm::SmallPtrSet<const CFGBlock*, DEFAULT_CFGBLOCKS> visited;
+};
+}
+
+void *UnreachableCodeChecker::getTag() {
+ static int x = 0;
+ return &x;
+}
+
+void clang::RegisterUnreachableCodeChecker(GRExprEngine &Eng) {
+ Eng.registerCheck(new UnreachableCodeChecker());
+}
+
+void UnreachableCodeChecker::VisitEndAnalysis(ExplodedGraph &G,
+ BugReporter &B,
+ bool hasWorkRemaining) {
+ // Bail out if we didn't cover all paths
+ if (hasWorkRemaining)
+ return;
+
+ CFG *C = 0;
+ // Iterate over ExplodedGraph
+ for (ExplodedGraph::node_iterator I = G.nodes_begin(); I != G.nodes_end();
+ ++I) {
+ const ProgramPoint &P = I->getLocation();
+
+ // Save the CFG if we don't have it already
+ if (!C)
+ C = P.getLocationContext()->getCFG();
+
+ if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
+ const CFGBlock *CB = BE->getBlock();
+ reachable.insert(CB);
+ }
+ }
+
+ // Bail out if we didn't get the CFG
+ if (!C)
+ return;
+
+ // Find CFGBlocks that were not covered by any node
+ for (CFG::const_iterator I = C->begin(); I != C->end(); ++I) {
+ const CFGBlock *CB = *I;
+ // Check if the block is unreachable
+ if (!reachable.count(CB)) {
+ // Find the entry points for this block
+ FindUnreachableEntryPoints(CB);
+ // This block may have been pruned; check if we still want to report it
+ if (reachable.count(CB))
+ continue;
+
+ // We found a statement that wasn't covered
+ SourceRange S;
+ SourceLocation SL = GetUnreachableLoc(*CB, S);
+ if (S.getBegin().isMacroID() || S.getEnd().isMacroID() || S.isInvalid()
+ || SL.isInvalid())
+ continue;
+ B.EmitBasicReport("Unreachable code", "This statement is never executed",
+ SL, S);
+ }
+ }
+}
+
+// Recursively finds the entry point(s) for this dead CFGBlock.
+void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB) {
+ bool allPredecessorsReachable = true;
+
+ visited.insert(CB);
+
+ for (CFGBlock::const_pred_iterator I = CB->pred_begin(); I != CB->pred_end();
+ ++I) {
+ // Recurse over all unreachable blocks
+ if (!reachable.count(*I) && !visited.count(*I)) {
+ FindUnreachableEntryPoints(*I);
+ allPredecessorsReachable = false;
+ }
+ }
+
+ // If at least one predecessor is unreachable, mark this block as reachable
+ // so we don't report this block.
+ if (!allPredecessorsReachable) {
+ reachable.insert(CB);
+ }
+}
+
+// Find the SourceLocation and SourceRange to report this CFGBlock
+SourceLocation UnreachableCodeChecker::GetUnreachableLoc(const CFGBlock &b,
+ SourceRange &R) {
+ const Stmt *S = 0;
+ unsigned sn = 0;
+ R = SourceRange();
+
+ if (sn < b.size())
+ S = b[sn].getStmt();
+ else if (b.getTerminator())
+ S = b.getTerminator();
+ else
+ return SourceLocation();
+
+ R = S->getSourceRange();
+ return S->getLocStart();
+}