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/StaticAnalyzer/Core/Checker.h"
     18 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
     19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
     20 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
     21 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
     22 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
     23 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
     24 #include "clang/AST/ParentMap.h"
     25 #include "clang/Basic/Builtins.h"
     26 #include "clang/Basic/SourceManager.h"
     27 #include "llvm/ADT/SmallPtrSet.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   CFG *C = 0;
     62   ParentMap *PM = 0;
     63   const LocationContext *LC = 0;
     64   // Iterate over ExplodedGraph
     65   for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end();
     66       I != E; ++I) {
     67     const ProgramPoint &P = I->getLocation();
     68     LC = P.getLocationContext();
     69 
     70     // Save the CFG if we don't have it already
     71     if (!C)
     72       C = LC->getAnalysisContext()->getUnoptimizedCFG();
     73     if (!PM)
     74       PM = &LC->getParentMap();
     75 
     76     if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) {
     77       const CFGBlock *CB = BE->getBlock();
     78       reachable.insert(CB->getBlockID());
     79     }
     80   }
     81 
     82   // Bail out if we didn't get the CFG or the ParentMap.
     83   if (!C || !PM)
     84     return;
     85 
     86   ASTContext &Ctx = B.getContext();
     87 
     88   // Find CFGBlocks that were not covered by any node
     89   for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) {
     90     const CFGBlock *CB = *I;
     91     // Check if the block is unreachable
     92     if (reachable.count(CB->getBlockID()))
     93       continue;
     94 
     95     // Check if the block is empty (an artificial block)
     96     if (isEmptyCFGBlock(CB))
     97       continue;
     98 
     99     // Find the entry points for this block
    100     if (!visited.count(CB->getBlockID()))
    101       FindUnreachableEntryPoints(CB, reachable, visited);
    102 
    103     // This block may have been pruned; check if we still want to report it
    104     if (reachable.count(CB->getBlockID()))
    105       continue;
    106 
    107     // Check for false positives
    108     if (CB->size() > 0 && isInvalidPath(CB, *PM))
    109       continue;
    110 
    111     // Special case for __builtin_unreachable.
    112     // FIXME: This should be extended to include other unreachable markers,
    113     // such as llvm_unreachable.
    114     if (!CB->empty()) {
    115       bool foundUnreachable = false;
    116       for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
    117            ci != ce; ++ci) {
    118         if (const CFGStmt *S = (*ci).getAs<CFGStmt>())
    119           if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
    120             if (CE->isBuiltinCall(Ctx) == Builtin::BI__builtin_unreachable) {
    121               foundUnreachable = true;
    122               break;
    123             }
    124           }
    125       }
    126       if (foundUnreachable)
    127         continue;
    128     }
    129 
    130     // We found a block that wasn't covered - find the statement to report
    131     SourceRange SR;
    132     PathDiagnosticLocation DL;
    133     SourceLocation SL;
    134     if (const Stmt *S = getUnreachableStmt(CB)) {
    135       SR = S->getSourceRange();
    136       DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC);
    137       SL = DL.asLocation();
    138       if (SR.isInvalid() || !SL.isValid())
    139         continue;
    140     }
    141     else
    142       continue;
    143 
    144     // Check if the SourceLocation is in a system header
    145     const SourceManager &SM = B.getSourceManager();
    146     if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL))
    147       continue;
    148 
    149     B.EmitBasicReport("Unreachable code", "Dead code", "This statement is never"
    150         " executed", DL, SR);
    151   }
    152 }
    153 
    154 // Recursively finds the entry point(s) for this dead CFGBlock.
    155 void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB,
    156                                                         CFGBlocksSet &reachable,
    157                                                         CFGBlocksSet &visited) {
    158   visited.insert(CB->getBlockID());
    159 
    160   for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end();
    161       I != E; ++I) {
    162     if (!reachable.count((*I)->getBlockID())) {
    163       // If we find an unreachable predecessor, mark this block as reachable so
    164       // we don't report this block
    165       reachable.insert(CB->getBlockID());
    166       if (!visited.count((*I)->getBlockID()))
    167         // If we haven't previously visited the unreachable predecessor, recurse
    168         FindUnreachableEntryPoints(*I, reachable, visited);
    169     }
    170   }
    171 }
    172 
    173 // Find the Stmt* in a CFGBlock for reporting a warning
    174 const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) {
    175   for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) {
    176     if (const CFGStmt *S = I->getAs<CFGStmt>())
    177       return S->getStmt();
    178   }
    179   if (const Stmt *S = CB->getTerminator())
    180     return S;
    181   else
    182     return 0;
    183 }
    184 
    185 // Determines if the path to this CFGBlock contained an element that infers this
    186 // block is a false positive. We assume that FindUnreachableEntryPoints has
    187 // already marked only the entry points to any dead code, so we need only to
    188 // find the condition that led to this block (the predecessor of this block.)
    189 // There will never be more than one predecessor.
    190 bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB,
    191                                            const ParentMap &PM) {
    192   // We only expect a predecessor size of 0 or 1. If it is >1, then an external
    193   // condition has broken our assumption (for example, a sink being placed by
    194   // another check). In these cases, we choose not to report.
    195   if (CB->pred_size() > 1)
    196     return true;
    197 
    198   // If there are no predecessors, then this block is trivially unreachable
    199   if (CB->pred_size() == 0)
    200     return false;
    201 
    202   const CFGBlock *pred = *CB->pred_begin();
    203 
    204   // Get the predecessor block's terminator conditon
    205   const Stmt *cond = pred->getTerminatorCondition();
    206 
    207   //assert(cond && "CFGBlock's predecessor has a terminator condition");
    208   // The previous assertion is invalid in some cases (eg do/while). Leaving
    209   // reporting of these situations on at the moment to help triage these cases.
    210   if (!cond)
    211     return false;
    212 
    213   // Run each of the checks on the conditions
    214   if (containsMacro(cond) || containsEnum(cond)
    215       || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond)
    216       || containsStmt<UnaryExprOrTypeTraitExpr>(cond))
    217     return true;
    218 
    219   return false;
    220 }
    221 
    222 // Returns true if the given CFGBlock is empty
    223 bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) {
    224   return CB->getLabel() == 0       // No labels
    225       && CB->size() == 0           // No statements
    226       && CB->getTerminator() == 0; // No terminator
    227 }
    228 
    229 void ento::registerUnreachableCodeChecker(CheckerManager &mgr) {
    230   mgr.registerChecker<UnreachableCodeChecker>();
    231 }
    232