lib/Checker/UnreachableCodeChecker.cpp

   1 //==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 // This file implements a generalized unreachable code checker using a
  10 // path-sensitive analysis. We mark any path visited, and then walk the CFG as a
  11 // post-analysis to determine what was never visited.
  12 //
  13 // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "clang/AST/ParentMap.h"
  17 #include "clang/Basic/Builtins.h"
  18 #include "clang/Basic/SourceManager.h"
  19 #include "clang/GR/PathSensitive/CheckerVisitor.h"
  20 #include "clang/GR/PathSensitive/ExplodedGraph.h"
  21 #include "clang/GR/PathSensitive/SVals.h"
  22 #include "clang/GR/PathSensitive/CheckerHelpers.h"
  23 #include "clang/GR/BugReporter/BugReporter.h"
  24 #include "GRExprEngineExperimentalChecks.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26
  27 // The number of CFGBlock pointers we want to reserve memory for. This is used
  28 // once for each function we analyze.
  29 #define DEFAULT_CFGBLOCKS 256
  30
  31 using namespace clang;
  32
  33 namespace {
  34 class UnreachableCodeChecker : public Checker {
  35 public:
  36   static void *getTag();
  37   void VisitEndAnalysis(ExplodedGraph &G,
  38                         BugReporter &B,
  39                         GRExprEngine &Eng);
  40 private:
  41   static inline const Stmt *getUnreachableStmt(const CFGBlock *CB);
  42   void FindUnreachableEntryPoints(const CFGBlock *CB);
  43   static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM);
  44   static inline bool isEmptyCFGBlock(const CFGBlock *CB);
  45
  46   llvm::SmallSet<unsigned, DEFAULT_CFGBLOCKS> reachable;
  47   llvm::SmallSet<unsigned, DEFAULT_CFGBLOCKS> visited;
  48 };
  49 }
  50
  51 void *UnreachableCodeChecker::getTag() {
  52   static int x = 0;
  53   return &x;
  54 }
  55
  56 void clang::RegisterUnreachableCodeChecker(GRExprEngine &Eng) {
  57   Eng.registerCheck(new UnreachableCodeChecker());
  58 }
  59
  60 void UnreachableCodeChecker::VisitEndAnalysis(ExplodedGraph &G,
  61                                               BugReporter &B,
  62                                               GRExprEngine &Eng) {
  63   // Bail out if we didn't cover all paths
  64   if (Eng.hasWorkRemaining())
  65     return;
  66
  67   CFG *C = 0;
  68   ParentMap *PM = 0;
  69   // Iterate over ExplodedGraph
  70   for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
  71       I != E; ++I) {
  72     const ProgramPoint &P = I->getLocation();
  73     const LocationContext *LC = P.getLocationContext();
  74
  75     // Save the CFG if we don't have it already
  76     if (!C)
  77       C = LC->getAnalysisContext()->getUnoptimizedCFG();
  78     if (!PM)
  79       PM = &LC->getParentMap();
  80
  81     if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
  82       const CFGBlock *CB = BE->getBlock();
  83       reachable.insert(CB->getBlockID());
  84     }
  85   }
  86
  87   // Bail out if we didn't get the CFG or the ParentMap.
  88   if (!C || !PM)
  89     return;
  90
  91   ASTContext &Ctx = B.getContext();
  92
  93   // Find CFGBlocks that were not covered by any node
  94   for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) {
  95     const CFGBlock *CB = *I;
  96     // Check if the block is unreachable
  97     if (reachable.count(CB->getBlockID()))
  98       continue;
  99
 100     // Check if the block is empty (an artificial block)
 101     if (isEmptyCFGBlock(CB))
 102       continue;
 103
 104     // Find the entry points for this block
 105     if (!visited.count(CB->getBlockID()))
 106       FindUnreachableEntryPoints(CB);
 107
 108     // This block may have been pruned; check if we still want to report it
 109     if (reachable.count(CB->getBlockID()))
 110       continue;
 111
 112     // Check for false positives
 113     if (CB->size() > 0 && isInvalidPath(CB, *PM))
 114       continue;
 115
 116     // Special case for __builtin_unreachable.
 117     // FIXME: This should be extended to include other unreachable markers,
 118     // such as llvm_unreachable.
 119     if (!CB->empty()) {
 120       CFGElement First = CB->front();
 121       if (CFGStmt S = First.getAs<CFGStmt>()) {
 122         if (const CallExpr *CE = dyn_cast<CallExpr>(S.getStmt())) {
 123           if (CE->isBuiltinCall(Ctx) == Builtin::BI__builtin_unreachable)
 124             continue;
 125         }
 126       }
 127     }
 128
 129     // We found a block that wasn't covered - find the statement to report
 130     SourceRange SR;
 131     SourceLocation SL;
 132     if (const Stmt *S = getUnreachableStmt(CB)) {
 133       SR = S->getSourceRange();
 134       SL = S->getLocStart();
 135       if (SR.isInvalid() || SL.isInvalid())
 136         continue;
 137     }
 138     else
 139       continue;
 140
 141     // Check if the SourceLocation is in a system header
 142     const SourceManager &SM = B.getSourceManager();
 143     if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
 144       continue;
 145
 146     B.EmitBasicReport("Unreachable code", "Dead code", "This statement is never"
 147         " executed", SL, SR);
 148   }
 149 }
 150
 151 // Recursively finds the entry point(s) for this dead CFGBlock.
 152 void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB) {
 153   visited.insert(CB->getBlockID());
 154
 155   for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
 156       I != E; ++I) {
 157     if (!reachable.count((*I)->getBlockID())) {
 158       // If we find an unreachable predecessor, mark this block as reachable so
 159       // we don't report this block
 160       reachable.insert(CB->getBlockID());
 161       if (!visited.count((*I)->getBlockID()))
 162         // If we haven't previously visited the unreachable predecessor, recurse
 163         FindUnreachableEntryPoints(*I);
 164     }
 165   }
 166 }
 167
 168 // Find the Stmt* in a CFGBlock for reporting a warning
 169 const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
 170   for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
 171     if (CFGStmt S = I->getAs<CFGStmt>())
 172       return S;
 173   }
 174   if (const Stmt *S = CB->getTerminator())
 175     return S;
 176   else
 177     return 0;
 178 }
 179
 180 // Determines if the path to this CFGBlock contained an element that infers this
 181 // block is a false positive. We assume that FindUnreachableEntryPoints has
 182 // already marked only the entry points to any dead code, so we need only to
 183 // find the condition that led to this block (the predecessor of this block.)
 184 // There will never be more than one predecessor.
 185 bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
 186                                            const ParentMap &PM) {
 187   // We only expect a predecessor size of 0 or 1. If it is >1, then an external
 188   // condition has broken our assumption (for example, a sink being placed by
 189   // another check). In these cases, we choose not to report.
 190   if (CB->pred_size() > 1)
 191     return true;
 192
 193   // If there are no predecessors, then this block is trivially unreachable
 194   if (CB->pred_size() == 0)
 195     return false;
 196
 197   const CFGBlock *pred = *CB->pred_begin();
 198
 199   // Get the predecessor block's terminator conditon
 200   const Stmt *cond = pred->getTerminatorCondition();
 201
 202   //assert(cond && "CFGBlock's predecessor has a terminator condition");
 203   // The previous assertion is invalid in some cases (eg do/while). Leaving
 204   // reporting of these situations on at the moment to help triage these cases.
 205   if (!cond)
 206     return false;
 207
 208   // Run each of the checks on the conditions
 209   if (containsMacro(cond) || containsEnum(cond)
 210       || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond)
 211       || containsStmt<SizeOfAlignOfExpr>(cond))
 212     return true;
 213
 214   return false;
 215 }
 216
 217 // Returns true if the given CFGBlock is empty
 218 bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
 219   return CB->getLabel() == 0       // No labels
 220       && CB->size() == 0           // No statements
 221       && CB->getTerminator() == 0; // No terminator
 222 }