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 #include <optional>
  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   const ParentMap *PM = nullptr;
  60   const LocationContext *LC = nullptr;
  61   // Iterate over ExplodedGraph
  62   for (const ExplodedNode &N : G.nodes()) {
  63     const ProgramPoint &P = N.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 (std::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 (const CFGBlock *CB : *C) {
  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, reachable, visited);
 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 (isInvalidPath(CB, *PM))
 114       continue;
 115
 116     // It is good practice to always have a "default" label in a "switch", even
 117     // if we should never get there. It can be used to detect errors, for
 118     // instance. Unreachable code directly under a "default" label is therefore
 119     // likely to be a false positive.
 120     if (const Stmt *label = CB->getLabel())
 121       if (label->getStmtClass() == Stmt::DefaultStmtClass)
 122         continue;
 123
 124     // Special case for __builtin_unreachable.
 125     // FIXME: This should be extended to include other unreachable markers,
 126     // such as llvm_unreachable.
 127     if (!CB->empty()) {
 128       bool foundUnreachable = false;
 129       for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
 130            ci != ce; ++ci) {
 131         if (std::optional<CFGStmt> S = (*ci).getAs<CFGStmt>())
 132           if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
 133             if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable ||
 134                 CE->isBuiltinAssumeFalse(Eng.getContext())) {
 135               foundUnreachable = true;
 136               break;
 137             }
 138           }
 139       }
 140       if (foundUnreachable)
 141         continue;
 142     }
 143
 144     // We found a block that wasn't covered - find the statement to report
 145     SourceRange SR;
 146     PathDiagnosticLocation DL;
 147     SourceLocation SL;
 148     if (const Stmt *S = getUnreachableStmt(CB)) {
 149       // In macros, 'do {...} while (0)' is often used. Don't warn about the
 150       // condition 0 when it is unreachable.
 151       if (S->getBeginLoc().isMacroID())
 152         if (const auto *I = dyn_cast<IntegerLiteral>(S))
 153           if (I->getValue() == 0ULL)
 154             if (const Stmt *Parent = PM->getParent(S))
 155               if (isa<DoStmt>(Parent))
 156                 continue;
 157       SR = S->getSourceRange();
 158       DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
 159       SL = DL.asLocation();
 160       if (SR.isInvalid() || !SL.isValid())
 161         continue;
 162       if (isa<CXXTryStmt>(S))
 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", categories::UnusedCode,
 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 (const CFGBlock *PredBlock : CB->preds()) {
 185     if (!PredBlock)
 186       continue;
 187
 188     if (!reachable.count(PredBlock->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(PredBlock->getBlockID()))
 193         // If we haven't previously visited the unreachable predecessor, recurse
 194         FindUnreachableEntryPoints(PredBlock, 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 (const CFGElement &Elem : *CB) {
 202     if (std::optional<CFGStmt> S = Elem.getAs<CFGStmt>()) {
 203       if (!isa<DeclStmt>(S->getStmt()))
 204         return S->getStmt();
 205     }
 206   }
 207   return CB->getTerminatorStmt();
 208 }
 209
 210 // Determines if the path to this CFGBlock contained an element that infers this
 211 // block is a false positive. We assume that FindUnreachableEntryPoints has
 212 // already marked only the entry points to any dead code, so we need only to
 213 // find the condition that led to this block (the predecessor of this block.)
 214 // There will never be more than one predecessor.
 215 bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
 216                                            const ParentMap &PM) {
 217   // We only expect a predecessor size of 0 or 1. If it is >1, then an external
 218   // condition has broken our assumption (for example, a sink being placed by
 219   // another check). In these cases, we choose not to report.
 220   if (CB->pred_size() > 1)
 221     return true;
 222
 223   // If there are no predecessors, then this block is trivially unreachable
 224   if (CB->pred_size() == 0)
 225     return false;
 226
 227   const CFGBlock *pred = *CB->pred_begin();
 228   if (!pred)
 229     return false;
 230
 231   // Get the predecessor block's terminator condition
 232   const Stmt *cond = pred->getTerminatorCondition();
 233
 234   //assert(cond && "CFGBlock's predecessor has a terminator condition");
 235   // The previous assertion is invalid in some cases (eg do/while). Leaving
 236   // reporting of these situations on at the moment to help triage these cases.
 237   if (!cond)
 238     return false;
 239
 240   // Run each of the checks on the conditions
 241   return containsMacro(cond) || containsEnum(cond) ||
 242          containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) ||
 243          containsStmt<UnaryExprOrTypeTraitExpr>(cond);
 244 }
 245
 246 // Returns true if the given CFGBlock is empty
 247 bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
 248   return CB->getLabel() == nullptr // No labels
 249       && CB->size() == 0           // No statements
 250       && !CB->getTerminatorStmt(); // No terminator
 251 }
 252
 253 void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
 254   mgr.registerChecker<UnreachableCodeChecker>();
 255 }
 256
 257 bool ento::shouldRegisterUnreachableCodeChecker(const CheckerManager &mgr) {
 258   return true;
 259 }