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