DeadStoresChecker.cpp revision 9b663716449b618ba0390b1dbebc54fa8e971124 
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
31class DeadStoreObs : public LiveVariables::ObserverTy {
32  ASTContext &Ctx;
33  BugReporter& BR;
34  ParentMap& Parents;
35  llvm::SmallPtrSet<VarDecl*, 20> Escaped;
36
37  enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
38
39public:
40  DeadStoreObs(ASTContext &ctx, BugReporter& br, ParentMap& parents,
41               llvm::SmallPtrSet<VarDecl*, 20> &escaped)
42    : Ctx(ctx), BR(br), Parents(parents), Escaped(escaped) {}
43
44  virtual ~DeadStoreObs() {}
45
46  void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) {
47    if (Escaped.count(V))
48      return;
49
50    std::string name = V->getNameAsString();
51
52    const char* BugType = 0;
53    std::string msg;
54
55    switch (dsk) {
56      default:
57        assert(false && "Impossible dead store type.");
58
59      case DeadInit:
60        BugType = "Dead initialization";
61        msg = "Value stored to '" + name +
62          "' during its initialization is never read";
63        break;
64
65      case DeadIncrement:
66        BugType = "Dead increment";
67      case Standard:
68        if (!BugType) BugType = "Dead assignment";
69        msg = "Value stored to '" + name + "' is never read";
70        break;
71
72      case Enclosing:
73        // Don't report issues in this case, e.g.: "if (x = foo())",
74        // where 'x' is unused later.  We have yet to see a case where
75        // this is a real bug.
76        return;
77    }
78
79    BR.EmitBasicReport(BugType, "Dead store", msg, L, R);
80  }
81
82  void CheckVarDecl(VarDecl* VD, Expr* Ex, Expr* Val,
83                    DeadStoreKind dsk,
84                    const LiveVariables::AnalysisDataTy& AD,
85                    const LiveVariables::ValTy& Live) {
86
87    if (!VD->hasLocalStorage())
88      return;
89    // Reference types confuse the dead stores checker.  Skip them
90    // for now.
91    if (VD->getType()->getAs<ReferenceType>())
92      return;
93
94    if (!Live(VD, AD) &&
95        !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()))
96      Report(VD, dsk, Ex->getSourceRange().getBegin(),
97             Val->getSourceRange());
98  }
99
100  void CheckDeclRef(DeclRefExpr* DR, Expr* Val, DeadStoreKind dsk,
101                    const LiveVariables::AnalysisDataTy& AD,
102                    const LiveVariables::ValTy& Live) {
103    if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
104      CheckVarDecl(VD, DR, Val, dsk, AD, Live);
105  }
106
107  bool isIncrement(VarDecl* VD, BinaryOperator* B) {
108    if (B->isCompoundAssignmentOp())
109      return true;
110
111    Expr* RHS = B->getRHS()->IgnoreParenCasts();
112    BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
113
114    if (!BRHS)
115      return false;
116
117    DeclRefExpr *DR;
118
119    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
120      if (DR->getDecl() == VD)
121        return true;
122
123    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
124      if (DR->getDecl() == VD)
125        return true;
126
127    return false;
128  }
129
130  virtual void ObserveStmt(Stmt* S,
131                           const LiveVariables::AnalysisDataTy& AD,
132                           const LiveVariables::ValTy& Live) {
133
134    // Skip statements in macros.
135    if (S->getLocStart().isMacroID())
136      return;
137
138    if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
139      if (!B->isAssignmentOp()) return; // Skip non-assignments.
140
141      if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()))
142        if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
143          // Special case: check for assigning null to a pointer.
144          //  This is a common form of defensive programming.
145          QualType T = VD->getType();
146          if (T->isPointerType() || T->isObjCObjectPointerType()) {
147            if (B->getRHS()->isNullPointerConstant(Ctx,
148                                              Expr::NPC_ValueDependentIsNull))
149              return;
150          }
151
152          Expr* RHS = B->getRHS()->IgnoreParenCasts();
153          // Special case: self-assignments.  These are often used to shut up
154          //  "unused variable" compiler warnings.
155          if (DeclRefExpr* RhsDR = dyn_cast<DeclRefExpr>(RHS))
156            if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
157              return;
158
159          // Otherwise, issue a warning.
160          DeadStoreKind dsk = Parents.isConsumedExpr(B)
161                              ? Enclosing
162                              : (isIncrement(VD,B) ? DeadIncrement : Standard);
163
164          CheckVarDecl(VD, DR, B->getRHS(), dsk, AD, Live);
165        }
166    }
167    else if (UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
168      if (!U->isIncrementOp())
169        return;
170
171      // Handle: ++x within a subexpression.  The solution is not warn
172      //  about preincrements to dead variables when the preincrement occurs
173      //  as a subexpression.  This can lead to false negatives, e.g. "(++x);"
174      //  A generalized dead code checker should find such issues.
175      if (U->isPrefix() && Parents.isConsumedExpr(U))
176        return;
177
178      Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
179
180      if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex))
181        CheckDeclRef(DR, U, DeadIncrement, AD, Live);
182    }
183    else if (DeclStmt* DS = dyn_cast<DeclStmt>(S))
184      // Iterate through the decls.  Warn if any initializers are complex
185      // expressions that are not live (never used).
186      for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
187           DI != DE; ++DI) {
188
189        VarDecl* V = dyn_cast<VarDecl>(*DI);
190
191        if (!V)
192          continue;
193
194        if (V->hasLocalStorage()) {
195          // Reference types confuse the dead stores checker.  Skip them
196          // for now.
197          if (V->getType()->getAs<ReferenceType>())
198            return;
199
200          if (Expr* E = V->getInit()) {
201            // Don't warn on C++ objects (yet) until we can show that their
202            // constructors/destructors don't have side effects.
203            if (isa<CXXConstructExpr>(E))
204              return;
205
206            if (isa<ExprWithCleanups>(E))
207              return;
208
209            // A dead initialization is a variable that is dead after it
210            // is initialized.  We don't flag warnings for those variables
211            // marked 'unused'.
212            if (!Live(V, AD) && V->getAttr<UnusedAttr>() == 0) {
213              // Special case: check for initializations with constants.
214              //
215              //  e.g. : int x = 0;
216              //
217              // If x is EVER assigned a new value later, don't issue
218              // a warning.  This is because such initialization can be
219              // due to defensive programming.
220              if (E->isConstantInitializer(Ctx, false))
221                return;
222
223              if (DeclRefExpr *DRE=dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
224                if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
225                  // Special case: check for initialization from constant
226                  //  variables.
227                  //
228                  //  e.g. extern const int MyConstant;
229                  //       int x = MyConstant;
230                  //
231                  if (VD->hasGlobalStorage() &&
232                      VD->getType().isConstQualified())
233                    return;
234                  // Special case: check for initialization from scalar
235                  //  parameters.  This is often a form of defensive
236                  //  programming.  Non-scalars are still an error since
237                  //  because it more likely represents an actual algorithmic
238                  //  bug.
239                  if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
240                    return;
241                }
242
243              Report(V, DeadInit, V->getLocation(), E->getSourceRange());
244            }
245          }
246        }
247      }
248  }
249};
250
251} // end anonymous namespace
252
253//===----------------------------------------------------------------------===//
254// Driver function to invoke the Dead-Stores checker on a CFG.
255//===----------------------------------------------------------------------===//
256
257namespace {
258class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
259  CFG *cfg;
260public:
261  FindEscaped(CFG *c) : cfg(c) {}
262
263  CFG& getCFG() { return *cfg; }
264
265  llvm::SmallPtrSet<VarDecl*, 20> Escaped;
266
267  void VisitUnaryOperator(UnaryOperator* U) {
268    // Check for '&'.  Any VarDecl whose value has its address-taken we
269    // treat as escaped.
270    Expr* E = U->getSubExpr()->IgnoreParenCasts();
271    if (U->getOpcode() == UO_AddrOf)
272      if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E))
273        if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
274          Escaped.insert(VD);
275          return;
276        }
277    Visit(E);
278  }
279};
280} // end anonymous namespace
281
282
283void ento::CheckDeadStores(CFG &cfg, LiveVariables &L, ParentMap &pmap,
284                            BugReporter& BR) {
285  FindEscaped FS(&cfg);
286  FS.getCFG().VisitBlockStmts(FS);
287  DeadStoreObs A(BR.getContext(), BR, pmap, FS.Escaped);
288  L.runOnAllBlocks(cfg, &A);
289}
290