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