DeadStoresChecker.cpp revision 848ec83483ca4ba52ed72c7e29ebc330f8c87252 
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 "clang/StaticAnalyzer/Checkers/LocalCheckers.h"
16#include "clang/Analysis/Analyses/LiveVariables.h"
17#include "clang/Analysis/Visitors/CFGRecStmtVisitor.h"
18#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
20#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
21#include "clang/Basic/Diagnostic.h"
22#include "clang/AST/ASTContext.h"
23#include "clang/AST/ParentMap.h"
24#include "llvm/ADT/SmallPtrSet.h"
25
26using namespace clang;
27using namespace ento;
28
29namespace {
30
31// FIXME: Eventually migrate into its own file, and have it managed by
32// AnalysisManager.
33class ReachableCode {
34  const CFG &cfg;
35  llvm::BitVector reachable;
36public:
37  ReachableCode(const CFG &cfg)
38    : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
39
40  void computeReachableBlocks();
41
42  bool isReachable(const CFGBlock *block) const {
43    return reachable[block->getBlockID()];
44  }
45};
46}
47
48void ReachableCode::computeReachableBlocks() {
49  if (!cfg.getNumBlockIDs())
50    return;
51
52  llvm::SmallVector<const CFGBlock*, 10> worklist;
53  worklist.push_back(&cfg.getEntry());
54
55  while (!worklist.empty()) {
56    const CFGBlock *block = worklist.back();
57    worklist.pop_back();
58    llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
59    if (isReachable)
60      continue;
61    isReachable = true;
62    for (CFGBlock::const_succ_iterator i = block->succ_begin(),
63                                       e = block->succ_end(); i != e; ++i)
64      if (const CFGBlock *succ = *i)
65        worklist.push_back(succ);
66  }
67}
68
69namespace {
70class DeadStoreObs : public LiveVariables::ObserverTy {
71  const CFG &cfg;
72  ASTContext &Ctx;
73  BugReporter& BR;
74  ParentMap& Parents;
75  llvm::SmallPtrSet<VarDecl*, 20> Escaped;
76  llvm::OwningPtr<ReachableCode> reachableCode;
77  const CFGBlock *currentBlock;
78
79  enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
80
81public:
82  DeadStoreObs(const CFG &cfg, ASTContext &ctx,
83               BugReporter& br, ParentMap& parents,
84               llvm::SmallPtrSet<VarDecl*, 20> &escaped)
85    : cfg(cfg), Ctx(ctx), BR(br), Parents(parents),
86      Escaped(escaped), currentBlock(0) {}
87
88  virtual ~DeadStoreObs() {}
89
90  void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) {
91    if (Escaped.count(V))
92      return;
93
94    // Compute reachable blocks within the CFG for trivial cases
95    // where a bogus dead store can be reported because itself is unreachable.
96    if (!reachableCode.get()) {
97      reachableCode.reset(new ReachableCode(cfg));
98      reachableCode->computeReachableBlocks();
99    }
100
101    if (!reachableCode->isReachable(currentBlock))
102      return;
103
104    const std::string &name = V->getNameAsString();
105
106    const char* BugType = 0;
107    std::string msg;
108
109    switch (dsk) {
110      default:
111        assert(false && "Impossible dead store type.");
112
113      case DeadInit:
114        BugType = "Dead initialization";
115        msg = "Value stored to '" + name +
116          "' during its initialization is never read";
117        break;
118
119      case DeadIncrement:
120        BugType = "Dead increment";
121      case Standard:
122        if (!BugType) BugType = "Dead assignment";
123        msg = "Value stored to '" + name + "' is never read";
124        break;
125
126      case Enclosing:
127        // Don't report issues in this case, e.g.: "if (x = foo())",
128        // where 'x' is unused later.  We have yet to see a case where
129        // this is a real bug.
130        return;
131    }
132
133    BR.EmitBasicReport(BugType, "Dead store", msg, L, R);
134  }
135
136  void CheckVarDecl(VarDecl* VD, Expr* Ex, Expr* Val,
137                    DeadStoreKind dsk,
138                    const LiveVariables::AnalysisDataTy& AD,
139                    const LiveVariables::ValTy& 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(VD, AD) &&
149        !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()))
150      Report(VD, dsk, Ex->getSourceRange().getBegin(),
151             Val->getSourceRange());
152  }
153
154  void CheckDeclRef(DeclRefExpr* DR, Expr* Val, DeadStoreKind dsk,
155                    const LiveVariables::AnalysisDataTy& AD,
156                    const LiveVariables::ValTy& Live) {
157    if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
158      CheckVarDecl(VD, DR, Val, dsk, AD, Live);
159  }
160
161  bool isIncrement(VarDecl* VD, BinaryOperator* B) {
162    if (B->isCompoundAssignmentOp())
163      return true;
164
165    Expr* RHS = B->getRHS()->IgnoreParenCasts();
166    BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
167
168    if (!BRHS)
169      return false;
170
171    DeclRefExpr *DR;
172
173    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
174      if (DR->getDecl() == VD)
175        return true;
176
177    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
178      if (DR->getDecl() == VD)
179        return true;
180
181    return false;
182  }
183
184  virtual void ObserveStmt(Stmt* S, const CFGBlock *block,
185                           const LiveVariables::AnalysisDataTy& AD,
186                           const LiveVariables::ValTy& Live) {
187
188    currentBlock = block;
189
190    // Skip statements in macros.
191    if (S->getLocStart().isMacroID())
192      return;
193
194    if (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, AD, Live);
221        }
222    }
223    else if (UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
224      if (!U->isIncrementOp())
225        return;
226
227      // Handle: ++x within a subexpression.  The solution is not warn
228      //  about preincrements to dead variables when the preincrement occurs
229      //  as a subexpression.  This can lead to false negatives, e.g. "(++x);"
230      //  A generalized dead code checker should find such issues.
231      if (U->isPrefix() && Parents.isConsumedExpr(U))
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
339void ento::CheckDeadStores(CFG &cfg, LiveVariables &L, ParentMap &pmap,
340                            BugReporter& BR) {
341  FindEscaped FS(&cfg);
342  FS.getCFG().VisitBlockStmts(FS);
343  DeadStoreObs A(cfg, BR.getContext(), BR, pmap, FS.Escaped);
344  L.runOnAllBlocks(cfg, &A);
345}
346