DeadStoresChecker.cpp revision 7df1234c2e62b2a23dc4417e527f941c20ebe858 
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  ParentMap& Parents;
76  llvm::SmallPtrSet<const 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<const 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(const VarDecl *V, DeadStoreKind dsk,
92              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    llvm::SmallString<64> buf;
107    llvm::raw_svector_ostream os(buf);
108    const char *BugType = 0;
109
110    switch (dsk) {
111      default:
112        llvm_unreachable("Impossible dead store type.");
113
114      case DeadInit:
115        BugType = "Dead initialization";
116        os << "Value stored to '" << V
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        os << "Value stored to '" << V << "' 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", os.str(), L, R);
135  }
136
137  void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
138                    DeadStoreKind dsk,
139                    const LiveVariables::LivenessValues &Live) {
140
141    if (!VD->hasLocalStorage())
142      return;
143    // Reference types confuse the dead stores checker.  Skip them
144    // for now.
145    if (VD->getType()->getAs<ReferenceType>())
146      return;
147
148    if (!Live.isLive(VD) &&
149        !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()))
150      Report(VD, dsk, Ex->getSourceRange().getBegin(),
151             Val->getSourceRange());
152  }
153
154  void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
155                    const LiveVariables::LivenessValues& Live) {
156    if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
157      CheckVarDecl(VD, DR, Val, dsk, Live);
158  }
159
160  bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
161    if (B->isCompoundAssignmentOp())
162      return true;
163
164    const Expr *RHS = B->getRHS()->IgnoreParenCasts();
165    const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
166
167    if (!BRHS)
168      return false;
169
170    const DeclRefExpr *DR;
171
172    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
173      if (DR->getDecl() == VD)
174        return true;
175
176    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
177      if (DR->getDecl() == VD)
178        return true;
179
180    return false;
181  }
182
183  virtual void observeStmt(const Stmt *S, const CFGBlock *block,
184                           const LiveVariables::LivenessValues &Live) {
185
186    currentBlock = block;
187
188    // Skip statements in macros.
189    if (S->getLocStart().isMacroID())
190      return;
191
192    // Only cover dead stores from regular assignments.  ++/-- dead stores
193    // have never flagged a real bug.
194    if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
195      if (!B->isAssignmentOp()) return; // Skip non-assignments.
196
197      if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
198        if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
199          // Special case: check for assigning null to a pointer.
200          //  This is a common form of defensive programming.
201          QualType T = VD->getType();
202          if (T->isPointerType() || T->isObjCObjectPointerType()) {
203            if (B->getRHS()->isNullPointerConstant(Ctx,
204                                              Expr::NPC_ValueDependentIsNull))
205              return;
206          }
207
208          Expr *RHS = B->getRHS()->IgnoreParenCasts();
209          // Special case: self-assignments.  These are often used to shut up
210          //  "unused variable" compiler warnings.
211          if (DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
212            if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
213              return;
214
215          // Otherwise, issue a warning.
216          DeadStoreKind dsk = Parents.isConsumedExpr(B)
217                              ? Enclosing
218                              : (isIncrement(VD,B) ? DeadIncrement : Standard);
219
220          CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
221        }
222    }
223    else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
224      if (!U->isIncrementOp() || U->isPrefix())
225        return;
226
227      const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
228      if (!parent || !isa<ReturnStmt>(parent))
229        return;
230
231      const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
232
233      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
234        CheckDeclRef(DR, U, DeadIncrement, Live);
235    }
236    else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
237      // Iterate through the decls.  Warn if any initializers are complex
238      // expressions that are not live (never used).
239      for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
240           DI != DE; ++DI) {
241
242        VarDecl *V = dyn_cast<VarDecl>(*DI);
243
244        if (!V)
245          continue;
246
247        if (V->hasLocalStorage()) {
248          // Reference types confuse the dead stores checker.  Skip them
249          // for now.
250          if (V->getType()->getAs<ReferenceType>())
251            return;
252
253          if (Expr *E = V->getInit()) {
254            while (ExprWithCleanups *exprClean = dyn_cast<ExprWithCleanups>(E))
255              E = exprClean->getSubExpr();
256
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            // A dead initialization is a variable that is dead after it
263            // is initialized.  We don't flag warnings for those variables
264            // marked 'unused'.
265            if (!Live.isLive(V) && V->getAttr<UnusedAttr>() == 0) {
266              // Special case: check for initializations with constants.
267              //
268              //  e.g. : int x = 0;
269              //
270              // If x is EVER assigned a new value later, don't issue
271              // a warning.  This is because such initialization can be
272              // due to defensive programming.
273              if (E->isConstantInitializer(Ctx, false))
274                return;
275
276              if (DeclRefExpr *DRE=dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
277                if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
278                  // Special case: check for initialization from constant
279                  //  variables.
280                  //
281                  //  e.g. extern const int MyConstant;
282                  //       int x = MyConstant;
283                  //
284                  if (VD->hasGlobalStorage() &&
285                      VD->getType().isConstQualified())
286                    return;
287                  // Special case: check for initialization from scalar
288                  //  parameters.  This is often a form of defensive
289                  //  programming.  Non-scalars are still an error since
290                  //  because it more likely represents an actual algorithmic
291                  //  bug.
292                  if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
293                    return;
294                }
295
296              Report(V, DeadInit, V->getLocation(), E->getSourceRange());
297            }
298          }
299        }
300      }
301  }
302};
303
304} // end anonymous namespace
305
306//===----------------------------------------------------------------------===//
307// Driver function to invoke the Dead-Stores checker on a CFG.
308//===----------------------------------------------------------------------===//
309
310namespace {
311class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
312  CFG *cfg;
313public:
314  FindEscaped(CFG *c) : cfg(c) {}
315
316  CFG& getCFG() { return *cfg; }
317
318  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
319
320  void VisitUnaryOperator(UnaryOperator* U) {
321    // Check for '&'.  Any VarDecl whose value has its address-taken we
322    // treat as escaped.
323    Expr *E = U->getSubExpr()->IgnoreParenCasts();
324    if (U->getOpcode() == UO_AddrOf)
325      if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
326        if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
327          Escaped.insert(VD);
328          return;
329        }
330    Visit(E);
331  }
332};
333} // end anonymous namespace
334
335
336//===----------------------------------------------------------------------===//
337// DeadStoresChecker
338//===----------------------------------------------------------------------===//
339
340namespace {
341class DeadStoresChecker : public Checker<check::ASTCodeBody> {
342public:
343  void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
344                        BugReporter &BR) const {
345    if (LiveVariables *L = mgr.getLiveVariables(D)) {
346      CFG &cfg = *mgr.getCFG(D);
347      ParentMap &pmap = mgr.getParentMap(D);
348      FindEscaped FS(&cfg);
349      FS.getCFG().VisitBlockStmts(FS);
350      DeadStoreObs A(cfg, BR.getContext(), BR, pmap, FS.Escaped);
351      L->runOnAllBlocks(A);
352    }
353  }
354};
355}
356
357void ento::registerDeadStoresChecker(CheckerManager &mgr) {
358  mgr.registerChecker<DeadStoresChecker>();
359}
360