contrib/llvm/tools/clang/lib/StaticAnalyzer/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 "ClangSACheckers.h"
  17 #include "clang/AST/ParentMap.h"
  18 #include "clang/Basic/Builtins.h"
  19 #include "clang/Basic/SourceManager.h"
  20 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  21 #include "clang/StaticAnalyzer/Core/Checker.h"
  22 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  27 #include "llvm/ADT/SmallSet.h"
  28
  29 // The number of CFGBlock pointers we want to reserve memory for. This is used
  30 // once for each function we analyze.
  31 #define DEFAULT_CFGBLOCKS 256
  32
  33 using namespace clang;
  34 using namespace ento;
  35
  36 namespace {
  37 class UnreachableCodeChecker : public Checker<check::EndAnalysis> {
  38 public:
  39   void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,
  40                         ExprEngine &Eng) const;
  41 private:
  42   typedef llvm::SmallSet<unsigned, DEFAULT_CFGBLOCKS> CFGBlocksSet;
  43
  44   static inline const Stmt *getUnreachableStmt(const CFGBlock *CB);
  45   static void FindUnreachableEntryPoints(const CFGBlock *CB,
  46                                          CFGBlocksSet &reachable,
  47                                          CFGBlocksSet &visited);
  48   static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM);
  49   static inline bool isEmptyCFGBlock(const CFGBlock *CB);
  50 };
  51 }
  52
  53 void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G,
  54                                               BugReporter &B,
  55                                               ExprEngine &Eng) const {
  56   CFGBlocksSet reachable, visited;
  57
  58   if (Eng.hasWorkRemaining())
  59     return;
  60
  61   const Decl *D = 0;
  62   CFG *C = 0;
  63   ParentMap *PM = 0;
  64   const LocationContext *LC = 0;
  65   // Iterate over ExplodedGraph
  66   for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
  67       I != E; ++I) {
  68     const ProgramPoint &P = I->getLocation();
  69     LC = P.getLocationContext();
  70     if (!LC->inTopFrame())
  71       continue;
  72
  73     if (!D)
  74       D = LC->getAnalysisDeclContext()->getDecl();
  75
  76     // Save the CFG if we don't have it already
  77     if (!C)
  78       C = LC->getAnalysisDeclContext()->getUnoptimizedCFG();
  79     if (!PM)
  80       PM = &LC->getParentMap();
  81
  82     if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) {
  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 (!D || !C || !PM)
  90     return;
  91
  92   // Don't do anything for template instantiations.  Proving that code
  93   // in a template instantiation is unreachable means proving that it is
  94   // unreachable in all instantiations.
  95   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
  96     if (FD->isTemplateInstantiation())
  97       return;
  98
  99   // Find CFGBlocks that were not covered by any node
 100   for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) {
 101     const CFGBlock *CB = *I;
 102     // Check if the block is unreachable
 103     if (reachable.count(CB->getBlockID()))
 104       continue;
 105
 106     // Check if the block is empty (an artificial block)
 107     if (isEmptyCFGBlock(CB))
 108       continue;
 109
 110     // Find the entry points for this block
 111     if (!visited.count(CB->getBlockID()))
 112       FindUnreachableEntryPoints(CB, reachable, visited);
 113
 114     // This block may have been pruned; check if we still want to report it
 115     if (reachable.count(CB->getBlockID()))
 116       continue;
 117
 118     // Check for false positives
 119     if (CB->size() > 0 && isInvalidPath(CB, *PM))
 120       continue;
 121
 122     // It is good practice to always have a "default" label in a "switch", even
 123     // if we should never get there. It can be used to detect errors, for
 124     // instance. Unreachable code directly under a "default" label is therefore
 125     // likely to be a false positive.
 126     if (const Stmt *label = CB->getLabel())
 127       if (label->getStmtClass() == Stmt::DefaultStmtClass)
 128         continue;
 129
 130     // Special case for __builtin_unreachable.
 131     // FIXME: This should be extended to include other unreachable markers,
 132     // such as llvm_unreachable.
 133     if (!CB->empty()) {
 134       bool foundUnreachable = false;
 135       for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
 136            ci != ce; ++ci) {
 137         if (Optional<CFGStmt> S = (*ci).getAs<CFGStmt>())
 138           if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
 139             if (CE->isBuiltinCall() == Builtin::BI__builtin_unreachable) {
 140               foundUnreachable = true;
 141               break;
 142             }
 143           }
 144       }
 145       if (foundUnreachable)
 146         continue;
 147     }
 148
 149     // We found a block that wasn't covered - find the statement to report
 150     SourceRange SR;
 151     PathDiagnosticLocation DL;
 152     SourceLocation SL;
 153     if (const Stmt *S = getUnreachableStmt(CB)) {
 154       SR = S->getSourceRange();
 155       DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
 156       SL = DL.asLocation();
 157       if (SR.isInvalid() || !SL.isValid())
 158         continue;
 159     }
 160     else
 161       continue;
 162
 163     // Check if the SourceLocation is in a system header
 164     const SourceManager &SM = B.getSourceManager();
 165     if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
 166       continue;
 167
 168     B.EmitBasicReport(D, "Unreachable code", "Dead code",
 169                       "This statement is never executed", DL, SR);
 170   }
 171 }
 172
 173 // Recursively finds the entry point(s) for this dead CFGBlock.
 174 void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB,
 175                                                         CFGBlocksSet &reachable,
 176                                                         CFGBlocksSet &visited) {
 177   visited.insert(CB->getBlockID());
 178
 179   for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
 180       I != E; ++I) {
 181     if (!reachable.count((*I)->getBlockID())) {
 182       // If we find an unreachable predecessor, mark this block as reachable so
 183       // we don't report this block
 184       reachable.insert(CB->getBlockID());
 185       if (!visited.count((*I)->getBlockID()))
 186         // If we haven't previously visited the unreachable predecessor, recurse
 187         FindUnreachableEntryPoints(*I, reachable, visited);
 188     }
 189   }
 190 }
 191
 192 // Find the Stmt* in a CFGBlock for reporting a warning
 193 const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
 194   for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
 195     if (Optional<CFGStmt> S = I->getAs<CFGStmt>())
 196       return S->getStmt();
 197   }
 198   if (const Stmt *S = CB->getTerminator())
 199     return S;
 200   else
 201     return 0;
 202 }
 203
 204 // Determines if the path to this CFGBlock contained an element that infers this
 205 // block is a false positive. We assume that FindUnreachableEntryPoints has
 206 // already marked only the entry points to any dead code, so we need only to
 207 // find the condition that led to this block (the predecessor of this block.)
 208 // There will never be more than one predecessor.
 209 bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
 210                                            const ParentMap &PM) {
 211   // We only expect a predecessor size of 0 or 1. If it is >1, then an external
 212   // condition has broken our assumption (for example, a sink being placed by
 213   // another check). In these cases, we choose not to report.
 214   if (CB->pred_size() > 1)
 215     return true;
 216
 217   // If there are no predecessors, then this block is trivially unreachable
 218   if (CB->pred_size() == 0)
 219     return false;
 220
 221   const CFGBlock *pred = *CB->pred_begin();
 222
 223   // Get the predecessor block's terminator conditon
 224   const Stmt *cond = pred->getTerminatorCondition();
 225
 226   //assert(cond && "CFGBlock's predecessor has a terminator condition");
 227   // The previous assertion is invalid in some cases (eg do/while). Leaving
 228   // reporting of these situations on at the moment to help triage these cases.
 229   if (!cond)
 230     return false;
 231
 232   // Run each of the checks on the conditions
 233   if (containsMacro(cond) || containsEnum(cond)
 234       || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond)
 235       || containsStmt<UnaryExprOrTypeTraitExpr>(cond))
 236     return true;
 237
 238   return false;
 239 }
 240
 241 // Returns true if the given CFGBlock is empty
 242 bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
 243   return CB->getLabel() == 0       // No labels
 244       && CB->size() == 0           // No statements
 245       && CB->getTerminator() == 0; // No terminator
 246 }
 247
 248 void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
 249   mgr.registerChecker<UnreachableCodeChecker>();
 250 }