DeadStoresChecker.cpp revision 7dd445ec20e704846cfbdb132e56539280d71311 
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/CheckerV2.h"
17#include "clang/StaticAnalyzer/Checkers/LocalCheckers.h"
18#include "clang/Analysis/Analyses/LiveVariables.h"
19#include "clang/Analysis/Visitors/CFGRecStmtVisitor.h"
20#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
22#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
23#include "clang/Basic/Diagnostic.h"
24#include "clang/AST/ASTContext.h"
25#include "clang/AST/ParentMap.h"
26#include "llvm/ADT/SmallPtrSet.h"
27
28using namespace clang;
29using namespace ento;
30
31namespace {
32
33// FIXME: Eventually migrate into its own file, and have it managed by
34// AnalysisManager.
35class ReachableCode {
36  const CFG &cfg;
37  llvm::BitVector reachable;
38public:
39  ReachableCode(const CFG &cfg)
40    : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
41
42  void computeReachableBlocks();
43
44  bool isReachable(const CFGBlock *block) const {
45    return reachable[block->getBlockID()];
46  }
47};
48}
49
50void ReachableCode::computeReachableBlocks() {
51  if (!cfg.getNumBlockIDs())
52    return;
53
54  llvm::SmallVector<const CFGBlock*, 10> worklist;
55  worklist.push_back(&cfg.getEntry());
56
57  while (!worklist.empty()) {
58    const CFGBlock *block = worklist.back();
59    worklist.pop_back();
60    llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
61    if (isReachable)
62      continue;
63    isReachable = true;
64    for (CFGBlock::const_succ_iterator i = block->succ_begin(),
65                                       e = block->succ_end(); i != e; ++i)
66      if (const CFGBlock *succ = *i)
67        worklist.push_back(succ);
68  }
69}
70
71namespace {
72class DeadStoreObs : public LiveVariables::ObserverTy {
73  const CFG &cfg;
74  ASTContext &Ctx;
75  BugReporter& BR;
76  ParentMap& Parents;
77  llvm::SmallPtrSet<VarDecl*, 20> Escaped;
78  llvm::OwningPtr<ReachableCode> reachableCode;
79  const CFGBlock *currentBlock;
80
81  enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
82
83public:
84  DeadStoreObs(const CFG &cfg, ASTContext &ctx,
85               BugReporter& br, ParentMap& parents,
86               llvm::SmallPtrSet<VarDecl*, 20> &escaped)
87    : cfg(cfg), Ctx(ctx), BR(br), Parents(parents),
88      Escaped(escaped), currentBlock(0) {}
89
90  virtual ~DeadStoreObs() {}
91
92  void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) {
93    if (Escaped.count(V))
94      return;
95
96    // Compute reachable blocks within the CFG for trivial cases
97    // where a bogus dead store can be reported because itself is unreachable.
98    if (!reachableCode.get()) {
99      reachableCode.reset(new ReachableCode(cfg));
100      reachableCode->computeReachableBlocks();
101    }
102
103    if (!reachableCode->isReachable(currentBlock))
104      return;
105
106    const std::string &name = V->getNameAsString();
107
108    const char* BugType = 0;
109    std::string msg;
110
111    switch (dsk) {
112      default:
113        assert(false && "Impossible dead store type.");
114
115      case DeadInit:
116        BugType = "Dead initialization";
117        msg = "Value stored to '" + name +
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        msg = "Value stored to '" + name + "' 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", msg, L, R);
136  }
137
138  void CheckVarDecl(VarDecl* VD, Expr* Ex, Expr* Val,
139                    DeadStoreKind dsk,
140                    const LiveVariables::AnalysisDataTy& AD,
141                    const LiveVariables::ValTy& Live) {
142
143    if (!VD->hasLocalStorage())
144      return;
145    // Reference types confuse the dead stores checker.  Skip them
146    // for now.
147    if (VD->getType()->getAs<ReferenceType>())
148      return;
149
150    if (!Live(VD, AD) &&
151        !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()))
152      Report(VD, dsk, Ex->getSourceRange().getBegin(),
153             Val->getSourceRange());
154  }
155
156  void CheckDeclRef(DeclRefExpr* DR, Expr* Val, DeadStoreKind dsk,
157                    const LiveVariables::AnalysisDataTy& AD,
158                    const LiveVariables::ValTy& Live) {
159    if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
160      CheckVarDecl(VD, DR, Val, dsk, AD, Live);
161  }
162
163  bool isIncrement(VarDecl* VD, BinaryOperator* B) {
164    if (B->isCompoundAssignmentOp())
165      return true;
166
167    Expr* RHS = B->getRHS()->IgnoreParenCasts();
168    BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
169
170    if (!BRHS)
171      return false;
172
173    DeclRefExpr *DR;
174
175    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
176      if (DR->getDecl() == VD)
177        return true;
178
179    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
180      if (DR->getDecl() == VD)
181        return true;
182
183    return false;
184  }
185
186  virtual void ObserveStmt(Stmt* S, const CFGBlock *block,
187                           const LiveVariables::AnalysisDataTy& AD,
188                           const LiveVariables::ValTy& 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 (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, AD, Live);
225        }
226    }
227    else if (UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
228      if (!U->isIncrementOp() || U->isPrefix())
229        return;
230
231      Stmt *parent = Parents.getParentIgnoreParenCasts(U);
232      if (!parent || !isa<ReturnStmt>(parent))
233        return;
234
235      Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
236
237      if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex))
238        CheckDeclRef(DR, U, DeadIncrement, AD, Live);
239    }
240    else if (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::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            // Don't warn on C++ objects (yet) until we can show that their
259            // constructors/destructors don't have side effects.
260            if (isa<CXXConstructExpr>(E))
261              return;
262
263            if (isa<ExprWithCleanups>(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(V, AD) && 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              Report(V, DeadInit, V->getLocation(), E->getSourceRange());
301            }
302          }
303        }
304      }
305  }
306};
307
308} // end anonymous namespace
309
310//===----------------------------------------------------------------------===//
311// Driver function to invoke the Dead-Stores checker on a CFG.
312//===----------------------------------------------------------------------===//
313
314namespace {
315class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
316  CFG *cfg;
317public:
318  FindEscaped(CFG *c) : cfg(c) {}
319
320  CFG& getCFG() { return *cfg; }
321
322  llvm::SmallPtrSet<VarDecl*, 20> Escaped;
323
324  void VisitUnaryOperator(UnaryOperator* U) {
325    // Check for '&'.  Any VarDecl whose value has its address-taken we
326    // treat as escaped.
327    Expr* E = U->getSubExpr()->IgnoreParenCasts();
328    if (U->getOpcode() == UO_AddrOf)
329      if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E))
330        if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
331          Escaped.insert(VD);
332          return;
333        }
334    Visit(E);
335  }
336};
337} // end anonymous namespace
338
339
340//===----------------------------------------------------------------------===//
341// DeadStoresChecker
342//===----------------------------------------------------------------------===//
343
344namespace {
345class DeadStoresChecker : public CheckerV2<check::ASTCodeBody> {
346public:
347  void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
348                        BugReporter &BR) const {
349    if (LiveVariables *L = mgr.getLiveVariables(D)) {
350      CFG &cfg = *mgr.getCFG(D);
351      ParentMap &pmap = mgr.getParentMap(D);
352      FindEscaped FS(&cfg);
353      FS.getCFG().VisitBlockStmts(FS);
354      DeadStoreObs A(cfg, BR.getContext(), BR, pmap, FS.Escaped);
355      L->runOnAllBlocks(cfg, &A);
356    }
357  }
358};
359}
360
361void ento::registerDeadStoresChecker(CheckerManager &mgr) {
362  mgr.registerChecker<DeadStoresChecker>();
363}
364