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