UnreachableCodeChecker.cpp revision f8906794f439643b688c2857f5543c9e2499f476
1c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care//==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==// 2c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// 3c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// The LLVM Compiler Infrastructure 4c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// 5c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// This file is distributed under the University of Illinois Open Source 6c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// License. See LICENSE.TXT for details. 7c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// 8c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care//===----------------------------------------------------------------------===// 9c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// This file implements a generalized unreachable code checker using a 10c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// path-sensitive analysis. We mark any path visited, and then walk the CFG as a 11c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// post-analysis to determine what was never visited. 12c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// 135e04bdde8e74d991feffe9cf95d731f7e473dbb7Jordy Rose// A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp 14c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care//===----------------------------------------------------------------------===// 15c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 167bce3a122296eba0e74f401c188e55c71935132fTom Care#include "clang/AST/ParentMap.h" 177bce3a122296eba0e74f401c188e55c71935132fTom Care#include "clang/Basic/Builtins.h" 18f8906794f439643b688c2857f5543c9e2499f476Tom Care#include "clang/Basic/SourceManager.h" 19c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care#include "clang/Checker/PathSensitive/CheckerVisitor.h" 20c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care#include "clang/Checker/PathSensitive/ExplodedGraph.h" 21c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care#include "clang/Checker/PathSensitive/SVals.h" 227bce3a122296eba0e74f401c188e55c71935132fTom Care#include "clang/Checker/PathSensitive/CheckerHelpers.h" 23c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care#include "clang/Checker/BugReporter/BugReporter.h" 24c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care#include "GRExprEngineExperimentalChecks.h" 25c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care#include "llvm/ADT/SmallPtrSet.h" 26c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 27c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// The number of CFGBlock pointers we want to reserve memory for. This is used 28c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// once for each function we analyze. 29c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care#define DEFAULT_CFGBLOCKS 256 30c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 31c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Careusing namespace clang; 32c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 33c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Carenamespace { 34c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Careclass UnreachableCodeChecker : public CheckerVisitor<UnreachableCodeChecker> { 35c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Carepublic: 36c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care static void *getTag(); 37bc42c533e7d3d946704a49e242939dd232f33072Tom Care void VisitEndAnalysis(ExplodedGraph &G, 38bc42c533e7d3d946704a49e242939dd232f33072Tom Care BugReporter &B, 39bc42c533e7d3d946704a49e242939dd232f33072Tom Care GRExprEngine &Eng); 40c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Careprivate: 41f8906794f439643b688c2857f5543c9e2499f476Tom Care static inline const Stmt *getUnreachableStmt(const CFGBlock *CB); 42c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care void FindUnreachableEntryPoints(const CFGBlock *CB); 437bce3a122296eba0e74f401c188e55c71935132fTom Care static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM); 44c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 45f8906794f439643b688c2857f5543c9e2499f476Tom Care llvm::SmallSet<unsigned, DEFAULT_CFGBLOCKS> reachable; 46f8906794f439643b688c2857f5543c9e2499f476Tom Care llvm::SmallSet<unsigned, DEFAULT_CFGBLOCKS> visited; 47c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care}; 48c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care} 49c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 50c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Carevoid *UnreachableCodeChecker::getTag() { 51c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care static int x = 0; 52c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care return &x; 53c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care} 54c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 55c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Carevoid clang::RegisterUnreachableCodeChecker(GRExprEngine &Eng) { 56c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care Eng.registerCheck(new UnreachableCodeChecker()); 57c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care} 58c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 59c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Carevoid UnreachableCodeChecker::VisitEndAnalysis(ExplodedGraph &G, 60c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care BugReporter &B, 61bc42c533e7d3d946704a49e242939dd232f33072Tom Care GRExprEngine &Eng) { 62c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care // Bail out if we didn't cover all paths 63bc42c533e7d3d946704a49e242939dd232f33072Tom Care if (Eng.hasWorkRemaining()) 64c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care return; 65c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 66c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care CFG *C = 0; 677bce3a122296eba0e74f401c188e55c71935132fTom Care ParentMap *PM = 0; 68c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care // Iterate over ExplodedGraph 69c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care for (ExplodedGraph::node_iterator I = G.nodes_begin(); I != G.nodes_end(); 70c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care ++I) { 71c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care const ProgramPoint &P = I->getLocation(); 727bce3a122296eba0e74f401c188e55c71935132fTom Care const LocationContext *LC = P.getLocationContext(); 73c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 74c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care // Save the CFG if we don't have it already 75c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care if (!C) 76f8906794f439643b688c2857f5543c9e2499f476Tom Care C = LC->getAnalysisContext()->getUnoptimizedCFG(); 777bce3a122296eba0e74f401c188e55c71935132fTom Care if (!PM) 787bce3a122296eba0e74f401c188e55c71935132fTom Care PM = &LC->getParentMap(); 79c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 80c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) { 81c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care const CFGBlock *CB = BE->getBlock(); 82f8906794f439643b688c2857f5543c9e2499f476Tom Care reachable.insert(CB->getBlockID()); 83c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care } 84c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care } 85c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 867bce3a122296eba0e74f401c188e55c71935132fTom Care // Bail out if we didn't get the CFG or the ParentMap. 877bce3a122296eba0e74f401c188e55c71935132fTom Care if (!C || !PM) 88c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care return; 89c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 905e04bdde8e74d991feffe9cf95d731f7e473dbb7Jordy Rose ASTContext &Ctx = B.getContext(); 915e04bdde8e74d991feffe9cf95d731f7e473dbb7Jordy Rose 92c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care // Find CFGBlocks that were not covered by any node 93c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care for (CFG::const_iterator I = C->begin(); I != C->end(); ++I) { 94c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care const CFGBlock *CB = *I; 95c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care // Check if the block is unreachable 96f8906794f439643b688c2857f5543c9e2499f476Tom Care if (reachable.count(CB->getBlockID())) 977bce3a122296eba0e74f401c188e55c71935132fTom Care continue; 987bce3a122296eba0e74f401c188e55c71935132fTom Care 997bce3a122296eba0e74f401c188e55c71935132fTom Care // Find the entry points for this block 1007bce3a122296eba0e74f401c188e55c71935132fTom Care FindUnreachableEntryPoints(CB); 1017bce3a122296eba0e74f401c188e55c71935132fTom Care 1027bce3a122296eba0e74f401c188e55c71935132fTom Care // This block may have been pruned; check if we still want to report it 103f8906794f439643b688c2857f5543c9e2499f476Tom Care if (reachable.count(CB->getBlockID())) 1047bce3a122296eba0e74f401c188e55c71935132fTom Care continue; 1057bce3a122296eba0e74f401c188e55c71935132fTom Care 1067bce3a122296eba0e74f401c188e55c71935132fTom Care // Check for false positives 1077bce3a122296eba0e74f401c188e55c71935132fTom Care if (CB->size() > 0 && isInvalidPath(CB, *PM)) 1087bce3a122296eba0e74f401c188e55c71935132fTom Care continue; 1097bce3a122296eba0e74f401c188e55c71935132fTom Care 1107bce3a122296eba0e74f401c188e55c71935132fTom Care // Special case for __builtin_unreachable. 1117bce3a122296eba0e74f401c188e55c71935132fTom Care // FIXME: This should be extended to include other unreachable markers, 1127bce3a122296eba0e74f401c188e55c71935132fTom Care // such as llvm_unreachable. 1137bce3a122296eba0e74f401c188e55c71935132fTom Care if (!CB->empty()) { 1147bce3a122296eba0e74f401c188e55c71935132fTom Care const Stmt *First = CB->front(); 1157bce3a122296eba0e74f401c188e55c71935132fTom Care if (const CallExpr *CE = dyn_cast<CallExpr>(First)) { 1167bce3a122296eba0e74f401c188e55c71935132fTom Care if (CE->isBuiltinCall(Ctx) == Builtin::BI__builtin_unreachable) 1177bce3a122296eba0e74f401c188e55c71935132fTom Care continue; 1185e04bdde8e74d991feffe9cf95d731f7e473dbb7Jordy Rose } 119c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care } 1207bce3a122296eba0e74f401c188e55c71935132fTom Care 121f8906794f439643b688c2857f5543c9e2499f476Tom Care // We found a block that wasn't covered - find the statement to report 122f8906794f439643b688c2857f5543c9e2499f476Tom Care SourceRange SR; 123f8906794f439643b688c2857f5543c9e2499f476Tom Care SourceLocation SL; 124f8906794f439643b688c2857f5543c9e2499f476Tom Care if (const Stmt *S = getUnreachableStmt(CB)) { 125f8906794f439643b688c2857f5543c9e2499f476Tom Care SR = S->getSourceRange(); 126f8906794f439643b688c2857f5543c9e2499f476Tom Care SL = S->getLocStart(); 127f8906794f439643b688c2857f5543c9e2499f476Tom Care if (SR.isInvalid() || SL.isInvalid()) 128f8906794f439643b688c2857f5543c9e2499f476Tom Care continue; 129f8906794f439643b688c2857f5543c9e2499f476Tom Care } 130f8906794f439643b688c2857f5543c9e2499f476Tom Care else 131f8906794f439643b688c2857f5543c9e2499f476Tom Care continue; 132f8906794f439643b688c2857f5543c9e2499f476Tom Care 133f8906794f439643b688c2857f5543c9e2499f476Tom Care // Check if the SourceLocation is in a system header 134f8906794f439643b688c2857f5543c9e2499f476Tom Care const SourceManager &SM = B.getSourceManager(); 135f8906794f439643b688c2857f5543c9e2499f476Tom Care if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL)) 136f8906794f439643b688c2857f5543c9e2499f476Tom Care continue; 137f8906794f439643b688c2857f5543c9e2499f476Tom Care 138f8906794f439643b688c2857f5543c9e2499f476Tom Care B.EmitBasicReport("Unreachable code", "Dead code", "This statement is never" 139f8906794f439643b688c2857f5543c9e2499f476Tom Care " executed", SL, SR); 140c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care } 141c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care} 142c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 143c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care// Recursively finds the entry point(s) for this dead CFGBlock. 144c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Carevoid UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB) { 145c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care bool allPredecessorsReachable = true; 146c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 147f8906794f439643b688c2857f5543c9e2499f476Tom Care visited.insert(CB->getBlockID()); 148c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 149c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care for (CFGBlock::const_pred_iterator I = CB->pred_begin(); I != CB->pred_end(); 150c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care ++I) { 151c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care // Recurse over all unreachable blocks 152f8906794f439643b688c2857f5543c9e2499f476Tom Care if (!reachable.count((*I)->getBlockID()) 153f8906794f439643b688c2857f5543c9e2499f476Tom Care && !visited.count((*I)->getBlockID())) { 154c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care FindUnreachableEntryPoints(*I); 155c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care allPredecessorsReachable = false; 156c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care } 157c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care } 158c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 159c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care // If at least one predecessor is unreachable, mark this block as reachable 160c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care // so we don't report this block. 161c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care if (!allPredecessorsReachable) { 162f8906794f439643b688c2857f5543c9e2499f476Tom Care reachable.insert(CB->getBlockID()); 163c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care } 164c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care} 165c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care 166f8906794f439643b688c2857f5543c9e2499f476Tom Care// Find the Stmt* in a CFGBlock for reporting a warning 167f8906794f439643b688c2857f5543c9e2499f476Tom Careconst Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) { 168f8906794f439643b688c2857f5543c9e2499f476Tom Care if (CB->size() > 0) 169f8906794f439643b688c2857f5543c9e2499f476Tom Care return CB->front().getStmt(); 170f8906794f439643b688c2857f5543c9e2499f476Tom Care else if (const Stmt *S = CB->getTerminator()) 171f8906794f439643b688c2857f5543c9e2499f476Tom Care return S; 172c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care else 173f8906794f439643b688c2857f5543c9e2499f476Tom Care return 0; 174c4b5bd89e1ef611c7a31b767763030acc45274c8Tom Care} 1757bce3a122296eba0e74f401c188e55c71935132fTom Care 176f8906794f439643b688c2857f5543c9e2499f476Tom Care// Determines if the path to this CFGBlock contained an element that infers this 177f8906794f439643b688c2857f5543c9e2499f476Tom Care// block is a false positive. We assume that FindUnreachableEntryPoints has 178f8906794f439643b688c2857f5543c9e2499f476Tom Care// already marked only the entry points to any dead code, so we need only to 179f8906794f439643b688c2857f5543c9e2499f476Tom Care// find the condition that led to this block (the predecessor of this block.) 180f8906794f439643b688c2857f5543c9e2499f476Tom Care// There will never be more than one predecessor. 1817bce3a122296eba0e74f401c188e55c71935132fTom Carebool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB, 1827bce3a122296eba0e74f401c188e55c71935132fTom Care const ParentMap &PM) { 183f8906794f439643b688c2857f5543c9e2499f476Tom Care // Assert this CFGBlock only has one or zero predecessors 184f8906794f439643b688c2857f5543c9e2499f476Tom Care assert(CB->pred_size() == 0 || CB->pred_size() == 1); 1857bce3a122296eba0e74f401c188e55c71935132fTom Care 186f8906794f439643b688c2857f5543c9e2499f476Tom Care // If there are no predecessors, then this block is trivially unreachable 187f8906794f439643b688c2857f5543c9e2499f476Tom Care if (CB->pred_size() == 0) 188f8906794f439643b688c2857f5543c9e2499f476Tom Care return false; 189f8906794f439643b688c2857f5543c9e2499f476Tom Care 190f8906794f439643b688c2857f5543c9e2499f476Tom Care const CFGBlock *pred = *CB->pred_begin(); 191f8906794f439643b688c2857f5543c9e2499f476Tom Care 192f8906794f439643b688c2857f5543c9e2499f476Tom Care // Get the predecessor block's terminator conditon 193f8906794f439643b688c2857f5543c9e2499f476Tom Care const Stmt *cond = pred->getTerminatorCondition(); 194f8906794f439643b688c2857f5543c9e2499f476Tom Care assert(cond && "CFGBlock's predecessor has a terminator condition"); 195f8906794f439643b688c2857f5543c9e2499f476Tom Care 196f8906794f439643b688c2857f5543c9e2499f476Tom Care // Run each of the checks on the conditions 197f8906794f439643b688c2857f5543c9e2499f476Tom Care if (containsMacro(cond) || containsEnum(cond) 198f8906794f439643b688c2857f5543c9e2499f476Tom Care || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) 199f8906794f439643b688c2857f5543c9e2499f476Tom Care || containsStmt<SizeOfAlignOfExpr>(cond)) 200f8906794f439643b688c2857f5543c9e2499f476Tom Care return true; 2017bce3a122296eba0e74f401c188e55c71935132fTom Care 2027bce3a122296eba0e74f401c188e55c71935132fTom Care return false; 2037bce3a122296eba0e74f401c188e55c71935132fTom Care} 204