Home | History | Annotate | Download | only in Checkers 
      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 = nullptr;
     62   CFG *C = nullptr;
     63   ParentMap *PM = nullptr;
     64   const LocationContext *LC = nullptr;
     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->getBuiltinCallee() == 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, this, "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 (!*I)
    182       continue;
    183 
    184     if (!reachable.count((*I)->getBlockID())) {
    185       // If we find an unreachable predecessor, mark this block as reachable so
    186       // we don't report this block
    187       reachable.insert(CB->getBlockID());
    188       if (!visited.count((*I)->getBlockID()))
    189         // If we haven't previously visited the unreachable predecessor, recurse
    190         FindUnreachableEntryPoints(*I, reachable, visited);
    191     }
    192   }
    193 }
    194 
    195 // Find the Stmt* in a CFGBlock for reporting a warning
    196 const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
    197   for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
    198     if (Optional<CFGStmt> S = I->getAs<CFGStmt>())
    199       return S->getStmt();
    200   }
    201   if (const Stmt *S = CB->getTerminator())
    202     return S;
    203   else
    204     return nullptr;
    205 }
    206 
    207 // Determines if the path to this CFGBlock contained an element that infers this
    208 // block is a false positive. We assume that FindUnreachableEntryPoints has
    209 // already marked only the entry points to any dead code, so we need only to
    210 // find the condition that led to this block (the predecessor of this block.)
    211 // There will never be more than one predecessor.
    212 bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
    213                                            const ParentMap &PM) {
    214   // We only expect a predecessor size of 0 or 1. If it is >1, then an external
    215   // condition has broken our assumption (for example, a sink being placed by
    216   // another check). In these cases, we choose not to report.
    217   if (CB->pred_size() > 1)
    218     return true;
    219 
    220   // If there are no predecessors, then this block is trivially unreachable
    221   if (CB->pred_size() == 0)
    222     return false;
    223 
    224   const CFGBlock *pred = *CB->pred_begin();
    225   if (!pred)
    226     return false;
    227 
    228   // Get the predecessor block's terminator conditon
    229   const Stmt *cond = pred->getTerminatorCondition();
    230 
    231   //assert(cond && "CFGBlock's predecessor has a terminator condition");
    232   // The previous assertion is invalid in some cases (eg do/while). Leaving
    233   // reporting of these situations on at the moment to help triage these cases.
    234   if (!cond)
    235     return false;
    236 
    237   // Run each of the checks on the conditions
    238   if (containsMacro(cond) || containsEnum(cond)
    239       || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond)
    240       || containsStmt<UnaryExprOrTypeTraitExpr>(cond))
    241     return true;
    242 
    243   return false;
    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->getTerminator();     // No terminator
    251 }
    252 
    253 void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
    254   mgr.registerChecker<UnreachableCodeChecker>();
    255 }
    256