DeadStoresChecker.cpp revision 19948ac84f145b9ea576db2faefda1927c249e44 
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/AST/ASTContext.h"
17#include "clang/AST/ParentMap.h"
18#include "clang/AST/RecursiveASTVisitor.h"
19#include "clang/Analysis/Analyses/LiveVariables.h"
20#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
21#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
22#include "clang/StaticAnalyzer/Core/Checker.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
24#include "llvm/ADT/BitVector.h"
25#include "llvm/ADT/SmallString.h"
26#include "llvm/Support/SaveAndRestore.h"
27
28using namespace clang;
29using namespace ento;
30
31namespace {
32
33/// A simple visitor to record what VarDecls occur in EH-handling code.
34class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> {
35public:
36  bool inEH;
37  llvm::DenseSet<const VarDecl *> &S;
38
39  bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) {
40    SaveAndRestore<bool> inFinally(inEH, true);
41    return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S);
42  }
43
44  bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) {
45    SaveAndRestore<bool> inCatch(inEH, true);
46    return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S);
47  }
48
49  bool TraverseCXXCatchStmt(CXXCatchStmt *S) {
50    SaveAndRestore<bool> inCatch(inEH, true);
51    return TraverseStmt(S->getHandlerBlock());
52  }
53
54  bool VisitDeclRefExpr(DeclRefExpr *DR) {
55    if (inEH)
56      if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
57        S.insert(D);
58    return true;
59  }
60
61  EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) :
62  inEH(false), S(S) {}
63};
64
65// FIXME: Eventually migrate into its own file, and have it managed by
66// AnalysisManager.
67class ReachableCode {
68  const CFG &cfg;
69  llvm::BitVector reachable;
70public:
71  ReachableCode(const CFG &cfg)
72    : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
73
74  void computeReachableBlocks();
75
76  bool isReachable(const CFGBlock *block) const {
77    return reachable[block->getBlockID()];
78  }
79};
80}
81
82void ReachableCode::computeReachableBlocks() {
83  if (!cfg.getNumBlockIDs())
84    return;
85
86  SmallVector<const CFGBlock*, 10> worklist;
87  worklist.push_back(&cfg.getEntry());
88
89  while (!worklist.empty()) {
90    const CFGBlock *block = worklist.back();
91    worklist.pop_back();
92    llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
93    if (isReachable)
94      continue;
95    isReachable = true;
96    for (CFGBlock::const_succ_iterator i = block->succ_begin(),
97                                       e = block->succ_end(); i != e; ++i)
98      if (const CFGBlock *succ = *i)
99        worklist.push_back(succ);
100  }
101}
102
103static const Expr *LookThroughTransitiveAssignments(const Expr *Ex) {
104  while (Ex) {
105    const BinaryOperator *BO =
106      dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts());
107    if (!BO)
108      break;
109    if (BO->getOpcode() == BO_Assign) {
110      Ex = BO->getRHS();
111      continue;
112    }
113    break;
114  }
115  return Ex;
116}
117
118namespace {
119class DeadStoreObs : public LiveVariables::Observer {
120  const CFG &cfg;
121  ASTContext &Ctx;
122  BugReporter& BR;
123  AnalysisDeclContext* AC;
124  ParentMap& Parents;
125  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
126  OwningPtr<ReachableCode> reachableCode;
127  const CFGBlock *currentBlock;
128  llvm::OwningPtr<llvm::DenseSet<const VarDecl *> > InEH;
129
130  enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
131
132public:
133  DeadStoreObs(const CFG &cfg, ASTContext &ctx,
134               BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents,
135               llvm::SmallPtrSet<const VarDecl*, 20> &escaped)
136    : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents),
137      Escaped(escaped), currentBlock(0) {}
138
139  virtual ~DeadStoreObs() {}
140
141  bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) {
142    if (Live.isLive(D))
143      return true;
144    // Lazily construct the set that records which VarDecls are in
145    // EH code.
146    if (!InEH.get()) {
147      InEH.reset(new llvm::DenseSet<const VarDecl *>());
148      EHCodeVisitor V(*InEH.get());
149      V.TraverseStmt(AC->getBody());
150    }
151    // Treat all VarDecls that occur in EH code as being "always live"
152    // when considering to suppress dead stores.  Frequently stores
153    // are followed by reads in EH code, but we don't have the ability
154    // to analyze that yet.
155    return InEH->count(D);
156  }
157
158  void Report(const VarDecl *V, DeadStoreKind dsk,
159              PathDiagnosticLocation L, SourceRange R) {
160    if (Escaped.count(V))
161      return;
162
163    // Compute reachable blocks within the CFG for trivial cases
164    // where a bogus dead store can be reported because itself is unreachable.
165    if (!reachableCode.get()) {
166      reachableCode.reset(new ReachableCode(cfg));
167      reachableCode->computeReachableBlocks();
168    }
169
170    if (!reachableCode->isReachable(currentBlock))
171      return;
172
173    SmallString<64> buf;
174    llvm::raw_svector_ostream os(buf);
175    const char *BugType = 0;
176
177    switch (dsk) {
178      case DeadInit:
179        BugType = "Dead initialization";
180        os << "Value stored to '" << *V
181           << "' during its initialization is never read";
182        break;
183
184      case DeadIncrement:
185        BugType = "Dead increment";
186      case Standard:
187        if (!BugType) BugType = "Dead assignment";
188        os << "Value stored to '" << *V << "' is never read";
189        break;
190
191      case Enclosing:
192        // Don't report issues in this case, e.g.: "if (x = foo())",
193        // where 'x' is unused later.  We have yet to see a case where
194        // this is a real bug.
195        return;
196    }
197
198    BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R);
199  }
200
201  void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
202                    DeadStoreKind dsk,
203                    const LiveVariables::LivenessValues &Live) {
204
205    if (!VD->hasLocalStorage())
206      return;
207    // Reference types confuse the dead stores checker.  Skip them
208    // for now.
209    if (VD->getType()->getAs<ReferenceType>())
210      return;
211
212    if (!isLive(Live, VD) &&
213        !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) {
214
215      PathDiagnosticLocation ExLoc =
216        PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC);
217      Report(VD, dsk, ExLoc, Val->getSourceRange());
218    }
219  }
220
221  void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
222                    const LiveVariables::LivenessValues& Live) {
223    if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
224      CheckVarDecl(VD, DR, Val, dsk, Live);
225  }
226
227  bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
228    if (B->isCompoundAssignmentOp())
229      return true;
230
231    const Expr *RHS = B->getRHS()->IgnoreParenCasts();
232    const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
233
234    if (!BRHS)
235      return false;
236
237    const DeclRefExpr *DR;
238
239    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
240      if (DR->getDecl() == VD)
241        return true;
242
243    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
244      if (DR->getDecl() == VD)
245        return true;
246
247    return false;
248  }
249
250  virtual void observeStmt(const Stmt *S, const CFGBlock *block,
251                           const LiveVariables::LivenessValues &Live) {
252
253    currentBlock = block;
254
255    // Skip statements in macros.
256    if (S->getLocStart().isMacroID())
257      return;
258
259    // Only cover dead stores from regular assignments.  ++/-- dead stores
260    // have never flagged a real bug.
261    if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
262      if (!B->isAssignmentOp()) return; // Skip non-assignments.
263
264      if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
265        if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
266          // Special case: check for assigning null to a pointer.
267          //  This is a common form of defensive programming.
268          const Expr *RHS = LookThroughTransitiveAssignments(B->getRHS());
269
270          QualType T = VD->getType();
271          if (T->isPointerType() || T->isObjCObjectPointerType()) {
272            if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
273              return;
274          }
275
276          RHS = RHS->IgnoreParenCasts();
277          // Special case: self-assignments.  These are often used to shut up
278          //  "unused variable" compiler warnings.
279          if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
280            if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
281              return;
282
283          // Otherwise, issue a warning.
284          DeadStoreKind dsk = Parents.isConsumedExpr(B)
285                              ? Enclosing
286                              : (isIncrement(VD,B) ? DeadIncrement : Standard);
287
288          CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
289        }
290    }
291    else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
292      if (!U->isIncrementOp() || U->isPrefix())
293        return;
294
295      const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
296      if (!parent || !isa<ReturnStmt>(parent))
297        return;
298
299      const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
300
301      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
302        CheckDeclRef(DR, U, DeadIncrement, Live);
303    }
304    else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
305      // Iterate through the decls.  Warn if any initializers are complex
306      // expressions that are not live (never used).
307      for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
308           DI != DE; ++DI) {
309
310        VarDecl *V = dyn_cast<VarDecl>(*DI);
311
312        if (!V)
313          continue;
314
315        if (V->hasLocalStorage()) {
316          // Reference types confuse the dead stores checker.  Skip them
317          // for now.
318          if (V->getType()->getAs<ReferenceType>())
319            return;
320
321          if (const Expr *E = V->getInit()) {
322            while (const ExprWithCleanups *exprClean =
323                    dyn_cast<ExprWithCleanups>(E))
324              E = exprClean->getSubExpr();
325
326            // Look through transitive assignments, e.g.:
327            // int x = y = 0;
328            E = LookThroughTransitiveAssignments(E);
329
330            // Don't warn on C++ objects (yet) until we can show that their
331            // constructors/destructors don't have side effects.
332            if (isa<CXXConstructExpr>(E))
333              return;
334
335            // A dead initialization is a variable that is dead after it
336            // is initialized.  We don't flag warnings for those variables
337            // marked 'unused'.
338            if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) {
339              // Special case: check for initializations with constants.
340              //
341              //  e.g. : int x = 0;
342              //
343              // If x is EVER assigned a new value later, don't issue
344              // a warning.  This is because such initialization can be
345              // due to defensive programming.
346              if (E->isEvaluatable(Ctx))
347                return;
348
349              if (const DeclRefExpr *DRE =
350                  dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
351                if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
352                  // Special case: check for initialization from constant
353                  //  variables.
354                  //
355                  //  e.g. extern const int MyConstant;
356                  //       int x = MyConstant;
357                  //
358                  if (VD->hasGlobalStorage() &&
359                      VD->getType().isConstQualified())
360                    return;
361                  // Special case: check for initialization from scalar
362                  //  parameters.  This is often a form of defensive
363                  //  programming.  Non-scalars are still an error since
364                  //  because it more likely represents an actual algorithmic
365                  //  bug.
366                  if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
367                    return;
368                }
369
370              PathDiagnosticLocation Loc =
371                PathDiagnosticLocation::create(V, BR.getSourceManager());
372              Report(V, DeadInit, Loc, E->getSourceRange());
373            }
374          }
375        }
376      }
377  }
378};
379
380} // end anonymous namespace
381
382//===----------------------------------------------------------------------===//
383// Driver function to invoke the Dead-Stores checker on a CFG.
384//===----------------------------------------------------------------------===//
385
386namespace {
387class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
388  CFG *cfg;
389public:
390  FindEscaped(CFG *c) : cfg(c) {}
391
392  CFG& getCFG() { return *cfg; }
393
394  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
395
396  void VisitUnaryOperator(UnaryOperator* U) {
397    // Check for '&'.  Any VarDecl whose value has its address-taken we
398    // treat as escaped.
399    Expr *E = U->getSubExpr()->IgnoreParenCasts();
400    if (U->getOpcode() == UO_AddrOf)
401      if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
402        if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
403          Escaped.insert(VD);
404          return;
405        }
406    Visit(E);
407  }
408};
409} // end anonymous namespace
410
411
412//===----------------------------------------------------------------------===//
413// DeadStoresChecker
414//===----------------------------------------------------------------------===//
415
416namespace {
417class DeadStoresChecker : public Checker<check::ASTCodeBody> {
418public:
419  void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
420                        BugReporter &BR) const {
421    if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
422      CFG &cfg = *mgr.getCFG(D);
423      AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
424      ParentMap &pmap = mgr.getParentMap(D);
425      FindEscaped FS(&cfg);
426      FS.getCFG().VisitBlockStmts(FS);
427      DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped);
428      L->runOnAllBlocks(A);
429    }
430  }
431};
432}
433
434void ento::registerDeadStoresChecker(CheckerManager &mgr) {
435  mgr.registerChecker<DeadStoresChecker>();
436}
437