Home | History | Annotate | Download | only in Checkers 
      1 //==- DeadStoresChecker.cpp - Check for stores to dead variables -*- 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 //
     10 //  This file defines a DeadStores, a flow-sensitive checker that looks for
     11 //  stores to variables that are no longer live.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "ClangSACheckers.h"
     16 #include "clang/StaticAnalyzer/Core/Checker.h"
     17 #include "clang/Analysis/Analyses/LiveVariables.h"
     18 #include "clang/Analysis/Visitors/CFGRecStmtVisitor.h"
     19 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
     20 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
     21 #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
     22 #include "clang/Basic/Diagnostic.h"
     23 #include "clang/AST/ASTContext.h"
     24 #include "clang/AST/ParentMap.h"
     25 #include "llvm/ADT/SmallPtrSet.h"
     26 
     27 using namespace clang;
     28 using namespace ento;
     29 
     30 namespace {
     31 
     32 // FIXME: Eventually migrate into its own file, and have it managed by
     33 // AnalysisManager.
     34 class ReachableCode {
     35   const CFG &cfg;
     36   llvm::BitVector reachable;
     37 public:
     38   ReachableCode(const CFG &cfg)
     39     : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
     40 
     41   void computeReachableBlocks();
     42 
     43   bool isReachable(const CFGBlock *block) const {
     44     return reachable[block->getBlockID()];
     45   }
     46 };
     47 }
     48 
     49 void ReachableCode::computeReachableBlocks() {
     50   if (!cfg.getNumBlockIDs())
     51     return;
     52 
     53   SmallVector<const CFGBlock*, 10> worklist;
     54   worklist.push_back(&cfg.getEntry());
     55 
     56   while (!worklist.empty()) {
     57     const CFGBlock *block = worklist.back();
     58     worklist.pop_back();
     59     llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
     60     if (isReachable)
     61       continue;
     62     isReachable = true;
     63     for (CFGBlock::const_succ_iterator i = block->succ_begin(),
     64                                        e = block->succ_end(); i != e; ++i)
     65       if (const CFGBlock *succ = *i)
     66         worklist.push_back(succ);
     67   }
     68 }
     69 
     70 namespace {
     71 class DeadStoreObs : public LiveVariables::Observer {
     72   const CFG &cfg;
     73   ASTContext &Ctx;
     74   BugReporter& BR;
     75   AnalysisContext* AC;
     76   ParentMap& Parents;
     77   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
     78   llvm::OwningPtr<ReachableCode> reachableCode;
     79   const CFGBlock *currentBlock;
     80 
     81   enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
     82 
     83 public:
     84   DeadStoreObs(const CFG &cfg, ASTContext &ctx,
     85                BugReporter& br, AnalysisContext* ac, ParentMap& parents,
     86                llvm::SmallPtrSet<const VarDecl*, 20> &escaped)
     87     : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents),
     88       Escaped(escaped), currentBlock(0) {}
     89 
     90   virtual ~DeadStoreObs() {}
     91 
     92   void Report(const VarDecl *V, DeadStoreKind dsk,
     93               PathDiagnosticLocation L, SourceRange R) {
     94     if (Escaped.count(V))
     95       return;
     96 
     97     // Compute reachable blocks within the CFG for trivial cases
     98     // where a bogus dead store can be reported because itself is unreachable.
     99     if (!reachableCode.get()) {
    100       reachableCode.reset(new ReachableCode(cfg));
    101       reachableCode->computeReachableBlocks();
    102     }
    103 
    104     if (!reachableCode->isReachable(currentBlock))
    105       return;
    106 
    107     llvm::SmallString<64> buf;
    108     llvm::raw_svector_ostream os(buf);
    109     const char *BugType = 0;
    110 
    111     switch (dsk) {
    112       default:
    113         llvm_unreachable("Impossible dead store type.");
    114 
    115       case DeadInit:
    116         BugType = "Dead initialization";
    117         os << "Value stored to '" << *V
    118            << "' during its initialization is never read";
    119         break;
    120 
    121       case DeadIncrement:
    122         BugType = "Dead increment";
    123       case Standard:
    124         if (!BugType) BugType = "Dead assignment";
    125         os << "Value stored to '" << *V << "' is never read";
    126         break;
    127 
    128       case Enclosing:
    129         // Don't report issues in this case, e.g.: "if (x = foo())",
    130         // where 'x' is unused later.  We have yet to see a case where
    131         // this is a real bug.
    132         return;
    133     }
    134 
    135     BR.EmitBasicReport(BugType, "Dead store", os.str(), L, R);
    136   }
    137 
    138   void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
    139                     DeadStoreKind dsk,
    140                     const LiveVariables::LivenessValues &Live) {
    141 
    142     if (!VD->hasLocalStorage())
    143       return;
    144     // Reference types confuse the dead stores checker.  Skip them
    145     // for now.
    146     if (VD->getType()->getAs<ReferenceType>())
    147       return;
    148 
    149     if (!Live.isLive(VD) &&
    150         !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) {
    151 
    152       PathDiagnosticLocation ExLoc =
    153         PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC);
    154       Report(VD, dsk, ExLoc, Val->getSourceRange());
    155     }
    156   }
    157 
    158   void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
    159                     const LiveVariables::LivenessValues& Live) {
    160     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
    161       CheckVarDecl(VD, DR, Val, dsk, Live);
    162   }
    163 
    164   bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
    165     if (B->isCompoundAssignmentOp())
    166       return true;
    167 
    168     const Expr *RHS = B->getRHS()->IgnoreParenCasts();
    169     const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
    170 
    171     if (!BRHS)
    172       return false;
    173 
    174     const DeclRefExpr *DR;
    175 
    176     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
    177       if (DR->getDecl() == VD)
    178         return true;
    179 
    180     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
    181       if (DR->getDecl() == VD)
    182         return true;
    183 
    184     return false;
    185   }
    186 
    187   virtual void observeStmt(const Stmt *S, const CFGBlock *block,
    188                            const LiveVariables::LivenessValues &Live) {
    189 
    190     currentBlock = block;
    191 
    192     // Skip statements in macros.
    193     if (S->getLocStart().isMacroID())
    194       return;
    195 
    196     // Only cover dead stores from regular assignments.  ++/-- dead stores
    197     // have never flagged a real bug.
    198     if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
    199       if (!B->isAssignmentOp()) return; // Skip non-assignments.
    200 
    201       if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
    202         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
    203           // Special case: check for assigning null to a pointer.
    204           //  This is a common form of defensive programming.
    205           QualType T = VD->getType();
    206           if (T->isPointerType() || T->isObjCObjectPointerType()) {
    207             if (B->getRHS()->isNullPointerConstant(Ctx,
    208                                               Expr::NPC_ValueDependentIsNull))
    209               return;
    210           }
    211 
    212           Expr *RHS = B->getRHS()->IgnoreParenCasts();
    213           // Special case: self-assignments.  These are often used to shut up
    214           //  "unused variable" compiler warnings.
    215           if (DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
    216             if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
    217               return;
    218 
    219           // Otherwise, issue a warning.
    220           DeadStoreKind dsk = Parents.isConsumedExpr(B)
    221                               ? Enclosing
    222                               : (isIncrement(VD,B) ? DeadIncrement : Standard);
    223 
    224           CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
    225         }
    226     }
    227     else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
    228       if (!U->isIncrementOp() || U->isPrefix())
    229         return;
    230 
    231       const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
    232       if (!parent || !isa<ReturnStmt>(parent))
    233         return;
    234 
    235       const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
    236 
    237       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
    238         CheckDeclRef(DR, U, DeadIncrement, Live);
    239     }
    240     else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
    241       // Iterate through the decls.  Warn if any initializers are complex
    242       // expressions that are not live (never used).
    243       for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
    244            DI != DE; ++DI) {
    245 
    246         VarDecl *V = dyn_cast<VarDecl>(*DI);
    247 
    248         if (!V)
    249           continue;
    250 
    251         if (V->hasLocalStorage()) {
    252           // Reference types confuse the dead stores checker.  Skip them
    253           // for now.
    254           if (V->getType()->getAs<ReferenceType>())
    255             return;
    256 
    257           if (Expr *E = V->getInit()) {
    258             while (ExprWithCleanups *exprClean = dyn_cast<ExprWithCleanups>(E))
    259               E = exprClean->getSubExpr();
    260 
    261             // Don't warn on C++ objects (yet) until we can show that their
    262             // constructors/destructors don't have side effects.
    263             if (isa<CXXConstructExpr>(E))
    264               return;
    265 
    266             // A dead initialization is a variable that is dead after it
    267             // is initialized.  We don't flag warnings for those variables
    268             // marked 'unused'.
    269             if (!Live.isLive(V) && V->getAttr<UnusedAttr>() == 0) {
    270               // Special case: check for initializations with constants.
    271               //
    272               //  e.g. : int x = 0;
    273               //
    274               // If x is EVER assigned a new value later, don't issue
    275               // a warning.  This is because such initialization can be
    276               // due to defensive programming.
    277               if (E->isConstantInitializer(Ctx, false))
    278                 return;
    279 
    280               if (DeclRefExpr *DRE=dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
    281                 if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
    282                   // Special case: check for initialization from constant
    283                   //  variables.
    284                   //
    285                   //  e.g. extern const int MyConstant;
    286                   //       int x = MyConstant;
    287                   //
    288                   if (VD->hasGlobalStorage() &&
    289                       VD->getType().isConstQualified())
    290                     return;
    291                   // Special case: check for initialization from scalar
    292                   //  parameters.  This is often a form of defensive
    293                   //  programming.  Non-scalars are still an error since
    294                   //  because it more likely represents an actual algorithmic
    295                   //  bug.
    296                   if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
    297                     return;
    298                 }
    299 
    300               PathDiagnosticLocation Loc =
    301                 PathDiagnosticLocation::create(V, BR.getSourceManager());
    302               Report(V, DeadInit, Loc, E->getSourceRange());
    303             }
    304           }
    305         }
    306       }
    307   }
    308 };
    309 
    310 } // end anonymous namespace
    311 
    312 //===----------------------------------------------------------------------===//
    313 // Driver function to invoke the Dead-Stores checker on a CFG.
    314 //===----------------------------------------------------------------------===//
    315 
    316 namespace {
    317 class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
    318   CFG *cfg;
    319 public:
    320   FindEscaped(CFG *c) : cfg(c) {}
    321 
    322   CFG& getCFG() { return *cfg; }
    323 
    324   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
    325 
    326   void VisitUnaryOperator(UnaryOperator* U) {
    327     // Check for '&'.  Any VarDecl whose value has its address-taken we
    328     // treat as escaped.
    329     Expr *E = U->getSubExpr()->IgnoreParenCasts();
    330     if (U->getOpcode() == UO_AddrOf)
    331       if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
    332         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
    333           Escaped.insert(VD);
    334           return;
    335         }
    336     Visit(E);
    337   }
    338 };
    339 } // end anonymous namespace
    340 
    341 
    342 //===----------------------------------------------------------------------===//
    343 // DeadStoresChecker
    344 //===----------------------------------------------------------------------===//
    345 
    346 namespace {
    347 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
    348 public:
    349   void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
    350                         BugReporter &BR) const {
    351     if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
    352       CFG &cfg = *mgr.getCFG(D);
    353       AnalysisContext *AC = mgr.getAnalysisContext(D);
    354       ParentMap &pmap = mgr.getParentMap(D);
    355       FindEscaped FS(&cfg);
    356       FS.getCFG().VisitBlockStmts(FS);
    357       DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped);
    358       L->runOnAllBlocks(A);
    359     }
    360   }
    361 };
    362 }
    363 
    364 void ento::registerDeadStoresChecker(CheckerManager &mgr) {
    365   mgr.registerChecker<DeadStoresChecker>();
    366 }
    367