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