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