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