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