contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp

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