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