clang  6.0.0svn
DeadStoresChecker.cpp
Go to the documentation of this file.
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"
24 #include "llvm/ADT/BitVector.h"
25 #include "llvm/ADT/SmallString.h"
26 #include "llvm/Support/SaveAndRestore.h"
27 
28 using namespace clang;
29 using namespace ento;
30 
31 namespace {
32 
33 /// A simple visitor to record what VarDecls occur in EH-handling code.
34 class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> {
35 public:
36  bool inEH;
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.
67 class ReachableCode {
68  const CFG &cfg;
69  llvm::BitVector reachable;
70 public:
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 
82 void ReachableCode::computeReachableBlocks() {
83  if (!cfg.getNumBlockIDs())
84  return;
85 
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 
102 static const Expr *
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 
122 namespace {
123 class DeadStoreObs : public LiveVariables::Observer {
124  const CFG &cfg;
125  ASTContext &Ctx;
126  BugReporter& BR;
127  const CheckerBase *Checker;
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 
137 public:
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  ~DeadStoreObs() override {}
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,
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  LLVM_FALLTHROUGH;
193  case Standard:
194  if (!BugType) BugType = "Dead assignment";
195  os << "Value stored to '" << *V << "' is never read";
196  break;
197 
198  case Enclosing:
199  // Don't report issues in this case, e.g.: "if (x = foo())",
200  // where 'x' is unused later. We have yet to see a case where
201  // this is a real bug.
202  return;
203  }
204 
205  BR.EmitBasicReport(AC->getDecl(), Checker, BugType, "Dead store", os.str(),
206  L, R);
207  }
208 
209  void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
210  DeadStoreKind dsk,
211  const LiveVariables::LivenessValues &Live) {
212 
213  if (!VD->hasLocalStorage())
214  return;
215  // Reference types confuse the dead stores checker. Skip them
216  // for now.
217  if (VD->getType()->getAs<ReferenceType>())
218  return;
219 
220  if (!isLive(Live, VD) &&
221  !(VD->hasAttr<UnusedAttr>() || VD->hasAttr<BlocksAttr>() ||
222  VD->hasAttr<ObjCPreciseLifetimeAttr>())) {
223 
224  PathDiagnosticLocation ExLoc =
226  Report(VD, dsk, ExLoc, Val->getSourceRange());
227  }
228  }
229 
230  void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
231  const LiveVariables::LivenessValues& Live) {
232  if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
233  CheckVarDecl(VD, DR, Val, dsk, Live);
234  }
235 
236  bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
237  if (B->isCompoundAssignmentOp())
238  return true;
239 
240  const Expr *RHS = B->getRHS()->IgnoreParenCasts();
241  const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
242 
243  if (!BRHS)
244  return false;
245 
246  const DeclRefExpr *DR;
247 
248  if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
249  if (DR->getDecl() == VD)
250  return true;
251 
252  if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
253  if (DR->getDecl() == VD)
254  return true;
255 
256  return false;
257  }
258 
259  void observeStmt(const Stmt *S, const CFGBlock *block,
260  const LiveVariables::LivenessValues &Live) override {
261 
262  currentBlock = block;
263 
264  // Skip statements in macros.
265  if (S->getLocStart().isMacroID())
266  return;
267 
268  // Only cover dead stores from regular assignments. ++/-- dead stores
269  // have never flagged a real bug.
270  if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
271  if (!B->isAssignmentOp()) return; // Skip non-assignments.
272 
273  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
274  if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
275  // Special case: check for assigning null to a pointer.
276  // This is a common form of defensive programming.
277  const Expr *RHS =
279  RHS = RHS->IgnoreParenCasts();
280 
281  QualType T = VD->getType();
282  if (T.isVolatileQualified())
283  return;
284  if (T->isPointerType() || T->isObjCObjectPointerType()) {
285  if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
286  return;
287  }
288 
289  // Special case: self-assignments. These are often used to shut up
290  // "unused variable" compiler warnings.
291  if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
292  if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
293  return;
294 
295  // Otherwise, issue a warning.
296  DeadStoreKind dsk = Parents.isConsumedExpr(B)
297  ? Enclosing
298  : (isIncrement(VD,B) ? DeadIncrement : Standard);
299 
300  CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
301  }
302  }
303  else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
304  if (!U->isIncrementOp() || U->isPrefix())
305  return;
306 
307  const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
308  if (!parent || !isa<ReturnStmt>(parent))
309  return;
310 
311  const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
312 
313  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
314  CheckDeclRef(DR, U, DeadIncrement, Live);
315  }
316  else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
317  // Iterate through the decls. Warn if any initializers are complex
318  // expressions that are not live (never used).
319  for (const auto *DI : DS->decls()) {
320  const auto *V = dyn_cast<VarDecl>(DI);
321 
322  if (!V)
323  continue;
324 
325  if (V->hasLocalStorage()) {
326  // Reference types confuse the dead stores checker. Skip them
327  // for now.
328  if (V->getType()->getAs<ReferenceType>())
329  return;
330 
331  if (const Expr *E = V->getInit()) {
332  while (const ExprWithCleanups *exprClean =
333  dyn_cast<ExprWithCleanups>(E))
334  E = exprClean->getSubExpr();
335 
336  // Look through transitive assignments, e.g.:
337  // int x = y = 0;
339 
340  // Don't warn on C++ objects (yet) until we can show that their
341  // constructors/destructors don't have side effects.
342  if (isa<CXXConstructExpr>(E))
343  return;
344 
345  // A dead initialization is a variable that is dead after it
346  // is initialized. We don't flag warnings for those variables
347  // marked 'unused' or 'objc_precise_lifetime'.
348  if (!isLive(Live, V) &&
349  !V->hasAttr<UnusedAttr>() &&
350  !V->hasAttr<ObjCPreciseLifetimeAttr>()) {
351  // Special case: check for initializations with constants.
352  //
353  // e.g. : int x = 0;
354  //
355  // If x is EVER assigned a new value later, don't issue
356  // a warning. This is because such initialization can be
357  // due to defensive programming.
358  if (E->isEvaluatable(Ctx))
359  return;
360 
361  if (const DeclRefExpr *DRE =
362  dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
363  if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
364  // Special case: check for initialization from constant
365  // variables.
366  //
367  // e.g. extern const int MyConstant;
368  // int x = MyConstant;
369  //
370  if (VD->hasGlobalStorage() &&
371  VD->getType().isConstQualified())
372  return;
373  // Special case: check for initialization from scalar
374  // parameters. This is often a form of defensive
375  // programming. Non-scalars are still an error since
376  // because it more likely represents an actual algorithmic
377  // bug.
378  if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
379  return;
380  }
381 
384  Report(V, DeadInit, Loc, E->getSourceRange());
385  }
386  }
387  }
388  }
389  }
390 };
391 
392 } // end anonymous namespace
393 
394 //===----------------------------------------------------------------------===//
395 // Driver function to invoke the Dead-Stores checker on a CFG.
396 //===----------------------------------------------------------------------===//
397 
398 namespace {
399 class FindEscaped {
400 public:
401  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
402 
403  void operator()(const Stmt *S) {
404  // Check for '&'. Any VarDecl whose address has been taken we treat as
405  // escaped.
406  // FIXME: What about references?
407  if (auto *LE = dyn_cast<LambdaExpr>(S)) {
408  findLambdaReferenceCaptures(LE);
409  return;
410  }
411 
412  const UnaryOperator *U = dyn_cast<UnaryOperator>(S);
413  if (!U)
414  return;
415  if (U->getOpcode() != UO_AddrOf)
416  return;
417 
418  const Expr *E = U->getSubExpr()->IgnoreParenCasts();
419  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
420  if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
421  Escaped.insert(VD);
422  }
423 
424  // Treat local variables captured by reference in C++ lambdas as escaped.
425  void findLambdaReferenceCaptures(const LambdaExpr *LE) {
426  const CXXRecordDecl *LambdaClass = LE->getLambdaClass();
427  llvm::DenseMap<const VarDecl *, FieldDecl *> CaptureFields;
428  FieldDecl *ThisCaptureField;
429  LambdaClass->getCaptureFields(CaptureFields, ThisCaptureField);
430 
431  for (const LambdaCapture &C : LE->captures()) {
432  if (!C.capturesVariable())
433  continue;
434 
435  VarDecl *VD = C.getCapturedVar();
436  const FieldDecl *FD = CaptureFields[VD];
437  if (!FD)
438  continue;
439 
440  // If the capture field is a reference type, it is capture-by-reference.
441  if (FD->getType()->isReferenceType())
442  Escaped.insert(VD);
443  }
444  }
445 };
446 } // end anonymous namespace
447 
448 
449 //===----------------------------------------------------------------------===//
450 // DeadStoresChecker
451 //===----------------------------------------------------------------------===//
452 
453 namespace {
454 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
455 public:
456  void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
457  BugReporter &BR) const {
458 
459  // Don't do anything for template instantiations.
460  // Proving that code in a template instantiation is "dead"
461  // means proving that it is dead in all instantiations.
462  // This same problem exists with -Wunreachable-code.
463  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
464  if (FD->isTemplateInstantiation())
465  return;
466 
467  if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
468  CFG &cfg = *mgr.getCFG(D);
470  ParentMap &pmap = mgr.getParentMap(D);
471  FindEscaped FS;
472  cfg.VisitBlockStmts(FS);
473  DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped);
474  L->runOnAllBlocks(A);
475  }
476  }
477 };
478 }
479 
480 void ento::registerDeadStoresChecker(CheckerManager &mgr) {
481  mgr.registerChecker<DeadStoresChecker>();
482 }
Defines the clang::ASTContext interface.
An instance of this class is created to represent a function declaration or definition.
Definition: Decl.h:1697
A (possibly-)qualified type.
Definition: Type.h:653
Stmt * getBody() const
Get the body of the Declaration.
succ_iterator succ_begin()
Definition: CFG.h:624
Stmt - This represents one statement.
Definition: Stmt.h:66
unsigned getBlockID() const
Definition: CFG.h:729
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
Stmt * getHandlerBlock() const
Definition: StmtCXX.h:52
Opcode getOpcode() const
Definition: Expr.h:3026
Describes the capture of a variable or of this, or of a C++1y init-capture.
Definition: LambdaCapture.h:26
bool isConsumedExpr(Expr *E) const
Definition: ParentMap.cpp:159
VarDecl - An instance of this class is created to represent a variable declaration or definition...
Definition: Decl.h:806
const T * getAs() const
Member-template getAs<specific type>&#39;.
Definition: Type.h:6307
Represents an expression – generally a full-expression – that introduces cleanups to be run at the ...
Definition: ExprCXX.h:3000
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3108
CXXRecordDecl * getLambdaClass() const
Retrieve the class that corresponds to the lambda.
Definition: ExprCXX.cpp:999
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:149
FieldDecl - An instance of this class is created by Sema::ActOnField to represent a member of a struc...
Definition: Decl.h:2457
AnalysisDeclContext contains the context data for the function or method under analysis.
bool isReferenceType() const
Definition: Type.h:5956
Represents Objective-C&#39;s @catch statement.
Definition: StmtObjC.h:74
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:600
ASTContext & getContext()
Definition: BugReporter.h:461
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:2985
bool isVolatileQualified() const
Determine whether this type is volatile-qualified.
Definition: Type.h:5790
Expr * IgnoreParenCasts() LLVM_READONLY
IgnoreParenCasts - Ignore parentheses and casts.
Definition: Expr.cpp:2465
static PathDiagnosticLocation create(const Decl *D, const SourceManager &SM)
Create a location corresponding to the given declaration.
A C++ lambda expression, which produces a function object (of unspecified type) that can be invoked l...
Definition: ExprCXX.h:1580
bool isScalarType() const
Definition: Type.h:6206
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
AnalysisDeclContext * getAnalysisDeclContext(const Decl *D)
bool hasAttr() const
Definition: DeclBase.h:535
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:422
Expr - This represents one expression.
Definition: Expr.h:106
CFG - Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:834
bool hasLocalStorage() const
hasLocalStorage - Returns true if a variable with function scope is a non-static local variable...
Definition: Decl.h:1025
const FunctionProtoType * T
Specifies that a value-dependent expression of integral or dependent type should be considered a null...
Definition: Expr.h:702
UnaryOperator - This represents the unary-expression&#39;s (except sizeof and alignof), the postinc/postdec operators from postfix-expression, and various extensions.
Definition: Expr.h:1717
CFG * getCFG(Decl const *D)
ValueDecl * getDecl()
Definition: Expr.h:1041
bool isConstQualified() const
Determine whether this type is const-qualified.
Definition: Type.h:5779
BugReporter is a utility class for generating PathDiagnostics for analysis.
Definition: BugReporter.h:403
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
#define false
Definition: stdbool.h:33
CHECKER * registerChecker()
Used to register checkers.
void EmitBasicReport(const Decl *DeclWithIssue, const CheckerBase *Checker, StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc, ArrayRef< SourceRange > Ranges=None)
Expr * getSubExpr() const
Definition: Expr.h:1744
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:487
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition: Decl.h:1067
ParentMap & getParentMap(Decl const *D)
const Decl * getDecl() const
bool isObjCObjectPointerType() const
Definition: Type.h:6041
succ_iterator succ_end()
Definition: CFG.h:625
Expr * getLHS() const
Definition: Expr.h:3029
Dataflow Directional Tag Classes.
void VisitBlockStmts(CALLBACK &O) const
Definition: CFG.h:983
static const Expr * LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex)
bool isLive(const Stmt *S) const
const Expr * getInit() const
Definition: Decl.h:1212
bool isMacroID() const
Opcode getOpcode() const
Definition: Expr.h:1741
Base for LValueReferenceType and RValueReferenceType.
Definition: Type.h:2421
Represents Objective-C&#39;s @finally statement.
Definition: StmtObjC.h:120
void getCaptureFields(llvm::DenseMap< const VarDecl *, FieldDecl *> &Captures, FieldDecl *&ThisCapture) const
For a closure type, retrieve the mapping from captured variables and this to the non-static data memb...
Definition: DeclCXX.cpp:1153
SourceManager & getSourceManager()
Definition: BugReporter.h:463
Represents a C++ struct/union/class.
Definition: DeclCXX.h:299
static bool isCompoundAssignmentOp(Opcode Opc)
Definition: Expr.h:3113
CXXCatchStmt - This represents a C++ catch block.
Definition: StmtCXX.h:29
capture_range captures() const
Retrieve this lambda&#39;s captures.
Definition: ExprCXX.cpp:969
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:265
Stmt * getParentIgnoreParenCasts(Stmt *) const
Definition: ParentMap.cpp:133
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:956
Expr * getRHS() const
Definition: Expr.h:3031
bool isPointerType() const
Definition: Type.h:5944
QualType getType() const
Definition: Decl.h:638
A trivial tuple used to represent a source range.
T * getAnalysis(Decl const *D)
SourceLocation getLocStart() const LLVM_READONLY
Definition: Stmt.cpp:277