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