DeadStoresChecker.cpp revision 579ee4f9f5c7b8f939621c8008337a3c1c679957 
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
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  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::Observer {
72  const CFG &cfg;
73  ASTContext &Ctx;
74  BugReporter& BR;
75  AnalysisDeclContext* 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
83public:
84  DeadStoreObs(const CFG &cfg, ASTContext &ctx,
85               BugReporter& br, AnalysisDeclContext* 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
316namespace {
317class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
318  CFG *cfg;
319public:
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
346namespace {
347class DeadStoresChecker : public Checker<check::ASTCodeBody> {
348public:
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      AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(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
364void ento::registerDeadStoresChecker(CheckerManager &mgr) {
365  mgr.registerChecker<DeadStoresChecker>();
366}
367