clang  9.0.0svn
DeadStoresChecker.cpp
Go to the documentation of this file.
1 //==- DeadStoresChecker.cpp - Check for stores to dead variables -*- C++ -*-==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines a DeadStores, a flow-sensitive checker that looks for
10 // stores to variables that are no longer live.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/Attr.h"
17 #include "clang/AST/ParentMap.h"
23 #include "llvm/ADT/BitVector.h"
24 #include "llvm/ADT/SmallString.h"
25 #include "llvm/Support/SaveAndRestore.h"
26 
27 using namespace clang;
28 using namespace ento;
29 
30 namespace {
31 
32 /// A simple visitor to record what VarDecls occur in EH-handling code.
33 class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> {
34 public:
35  bool inEH;
37 
38  bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) {
39  SaveAndRestore<bool> inFinally(inEH, true);
40  return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S);
41  }
42 
43  bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) {
44  SaveAndRestore<bool> inCatch(inEH, true);
45  return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S);
46  }
47 
48  bool TraverseCXXCatchStmt(CXXCatchStmt *S) {
49  SaveAndRestore<bool> inCatch(inEH, true);
50  return TraverseStmt(S->getHandlerBlock());
51  }
52 
53  bool VisitDeclRefExpr(DeclRefExpr *DR) {
54  if (inEH)
55  if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
56  S.insert(D);
57  return true;
58  }
59 
60  EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) :
61  inEH(false), S(S) {}
62 };
63 
64 // FIXME: Eventually migrate into its own file, and have it managed by
65 // AnalysisManager.
66 class ReachableCode {
67  const CFG &cfg;
68  llvm::BitVector reachable;
69 public:
70  ReachableCode(const CFG &cfg)
71  : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
72 
73  void computeReachableBlocks();
74 
75  bool isReachable(const CFGBlock *block) const {
76  return reachable[block->getBlockID()];
77  }
78 };
79 }
80 
81 void ReachableCode::computeReachableBlocks() {
82  if (!cfg.getNumBlockIDs())
83  return;
84 
86  worklist.push_back(&cfg.getEntry());
87 
88  while (!worklist.empty()) {
89  const CFGBlock *block = worklist.pop_back_val();
90  llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
91  if (isReachable)
92  continue;
93  isReachable = true;
94  for (CFGBlock::const_succ_iterator i = block->succ_begin(),
95  e = block->succ_end(); i != e; ++i)
96  if (const CFGBlock *succ = *i)
97  worklist.push_back(succ);
98  }
99 }
100 
101 static const Expr *
103  while (Ex) {
104  const BinaryOperator *BO =
105  dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts());
106  if (!BO)
107  break;
108  if (BO->getOpcode() == BO_Assign) {
109  Ex = BO->getRHS();
110  continue;
111  }
112  if (BO->getOpcode() == BO_Comma) {
113  Ex = BO->getRHS();
114  continue;
115  }
116  break;
117  }
118  return Ex;
119 }
120 
121 namespace {
122 class DeadStoreObs : public LiveVariables::Observer {
123  const CFG &cfg;
124  ASTContext &Ctx;
125  BugReporter& BR;
126  const CheckerBase *Checker;
128  ParentMap& Parents;
129  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
130  std::unique_ptr<ReachableCode> reachableCode;
131  const CFGBlock *currentBlock;
132  std::unique_ptr<llvm::DenseSet<const VarDecl *>> InEH;
133 
134  enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
135 
136 public:
137  DeadStoreObs(const CFG &cfg, ASTContext &ctx, BugReporter &br,
138  const CheckerBase *checker, AnalysisDeclContext *ac,
139  ParentMap &parents,
140  llvm::SmallPtrSet<const VarDecl *, 20> &escaped)
141  : cfg(cfg), Ctx(ctx), BR(br), Checker(checker), AC(ac), Parents(parents),
142  Escaped(escaped), currentBlock(nullptr) {}
143 
144  ~DeadStoreObs() override {}
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 = nullptr;
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  LLVM_FALLTHROUGH;
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->getBeginLoc().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 =
278  RHS = RHS->IgnoreParenCasts();
279 
280  QualType T = VD->getType();
281  if (T.isVolatileQualified())
282  return;
283  if (T->isPointerType() || T->isObjCObjectPointerType()) {
284  if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
285  return;
286  }
287 
288  // Special case: self-assignments. These are often used to shut up
289  // "unused variable" compiler warnings.
290  if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
291  if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
292  return;
293 
294  // Otherwise, issue a warning.
295  DeadStoreKind dsk = Parents.isConsumedExpr(B)
296  ? Enclosing
297  : (isIncrement(VD,B) ? DeadIncrement : Standard);
298 
299  CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
300  }
301  }
302  else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
303  if (!U->isIncrementOp() || U->isPrefix())
304  return;
305 
306  const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
307  if (!parent || !isa<ReturnStmt>(parent))
308  return;
309 
310  const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
311 
312  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
313  CheckDeclRef(DR, U, DeadIncrement, Live);
314  }
315  else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
316  // Iterate through the decls. Warn if any initializers are complex
317  // expressions that are not live (never used).
318  for (const auto *DI : DS->decls()) {
319  const auto *V = dyn_cast<VarDecl>(DI);
320 
321  if (!V)
322  continue;
323 
324  if (V->hasLocalStorage()) {
325  // Reference types confuse the dead stores checker. Skip them
326  // for now.
327  if (V->getType()->getAs<ReferenceType>())
328  return;
329 
330  if (const Expr *E = V->getInit()) {
331  while (const FullExpr *FE = dyn_cast<FullExpr>(E))
332  E = FE->getSubExpr();
333 
334  // Look through transitive assignments, e.g.:
335  // int x = y = 0;
337 
338  // Don't warn on C++ objects (yet) until we can show that their
339  // constructors/destructors don't have side effects.
340  if (isa<CXXConstructExpr>(E))
341  return;
342 
343  // A dead initialization is a variable that is dead after it
344  // is initialized. We don't flag warnings for those variables
345  // marked 'unused' or 'objc_precise_lifetime'.
346  if (!isLive(Live, V) &&
347  !V->hasAttr<UnusedAttr>() &&
348  !V->hasAttr<ObjCPreciseLifetimeAttr>()) {
349  // Special case: check for initializations with constants.
350  //
351  // e.g. : int x = 0;
352  //
353  // If x is EVER assigned a new value later, don't issue
354  // a warning. This is because such initialization can be
355  // due to defensive programming.
356  if (E->isEvaluatable(Ctx))
357  return;
358 
359  if (const DeclRefExpr *DRE =
360  dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
361  if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
362  // Special case: check for initialization from constant
363  // variables.
364  //
365  // e.g. extern const int MyConstant;
366  // int x = MyConstant;
367  //
368  if (VD->hasGlobalStorage() &&
369  VD->getType().isConstQualified())
370  return;
371  // Special case: check for initialization from scalar
372  // parameters. This is often a form of defensive
373  // programming. Non-scalars are still an error since
374  // because it more likely represents an actual algorithmic
375  // bug.
376  if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
377  return;
378  }
379 
380  PathDiagnosticLocation Loc =
381  PathDiagnosticLocation::create(V, BR.getSourceManager());
382  Report(V, DeadInit, Loc, E->getSourceRange());
383  }
384  }
385  }
386  }
387  }
388 };
389 
390 } // end anonymous namespace
391 
392 //===----------------------------------------------------------------------===//
393 // Driver function to invoke the Dead-Stores checker on a CFG.
394 //===----------------------------------------------------------------------===//
395 
396 namespace {
397 class FindEscaped {
398 public:
399  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
400 
401  void operator()(const Stmt *S) {
402  // Check for '&'. Any VarDecl whose address has been taken we treat as
403  // escaped.
404  // FIXME: What about references?
405  if (auto *LE = dyn_cast<LambdaExpr>(S)) {
406  findLambdaReferenceCaptures(LE);
407  return;
408  }
409 
410  const UnaryOperator *U = dyn_cast<UnaryOperator>(S);
411  if (!U)
412  return;
413  if (U->getOpcode() != UO_AddrOf)
414  return;
415 
416  const Expr *E = U->getSubExpr()->IgnoreParenCasts();
417  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
418  if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
419  Escaped.insert(VD);
420  }
421 
422  // Treat local variables captured by reference in C++ lambdas as escaped.
423  void findLambdaReferenceCaptures(const LambdaExpr *LE) {
424  const CXXRecordDecl *LambdaClass = LE->getLambdaClass();
425  llvm::DenseMap<const VarDecl *, FieldDecl *> CaptureFields;
426  FieldDecl *ThisCaptureField;
427  LambdaClass->getCaptureFields(CaptureFields, ThisCaptureField);
428 
429  for (const LambdaCapture &C : LE->captures()) {
430  if (!C.capturesVariable())
431  continue;
432 
433  VarDecl *VD = C.getCapturedVar();
434  const FieldDecl *FD = CaptureFields[VD];
435  if (!FD)
436  continue;
437 
438  // If the capture field is a reference type, it is capture-by-reference.
439  if (FD->getType()->isReferenceType())
440  Escaped.insert(VD);
441  }
442  }
443 };
444 } // end anonymous namespace
445 
446 
447 //===----------------------------------------------------------------------===//
448 // DeadStoresChecker
449 //===----------------------------------------------------------------------===//
450 
451 namespace {
452 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
453 public:
454  void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
455  BugReporter &BR) const {
456 
457  // Don't do anything for template instantiations.
458  // Proving that code in a template instantiation is "dead"
459  // means proving that it is dead in all instantiations.
460  // This same problem exists with -Wunreachable-code.
461  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
462  if (FD->isTemplateInstantiation())
463  return;
464 
465  if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
466  CFG &cfg = *mgr.getCFG(D);
467  AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
468  ParentMap &pmap = mgr.getParentMap(D);
469  FindEscaped FS;
470  cfg.VisitBlockStmts(FS);
471  DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped);
472  L->runOnAllBlocks(A);
473  }
474  }
475 };
476 }
477 
478 void ento::registerDeadStoresChecker(CheckerManager &mgr) {
479  mgr.registerChecker<DeadStoresChecker>();
480 }
481 
482 bool ento::shouldRegisterDeadStoresChecker(const LangOptions &LO) {
483  return true;
484 }
Defines the clang::ASTContext interface.
Represents a function declaration or definition.
Definition: Decl.h:1737
A (possibly-)qualified type.
Definition: Type.h:634
Stmt * getBody() const
Get the body of the Declaration.
succ_iterator succ_begin()
Definition: CFG.h:750
Stmt - This represents one statement.
Definition: Stmt.h:65
unsigned getBlockID() const
Definition: CFG.h:855
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
Stmt * getHandlerBlock() const
Definition: StmtCXX.h:51
Opcode getOpcode() const
Definition: Expr.h:3348
Describes the capture of a variable or of this, or of a C++1y init-capture.
Definition: LambdaCapture.h:25
bool isConsumedExpr(Expr *E) const
Definition: ParentMap.cpp:159
Represents a variable declaration or definition.
Definition: Decl.h:812
const T * getAs() const
Member-template getAs<specific type>&#39;.
Definition: Type.h:6761
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3436
CXXRecordDecl * getLambdaClass() const
Retrieve the class that corresponds to the lambda.
Definition: ExprCXX.cpp:1195
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
FullExpr - Represents a "full-expression" node.
Definition: Expr.h:910
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: Stmt.cpp:263
Represents a member of a struct/union/class.
Definition: Decl.h:2578
AnalysisDeclContext contains the context data for the function or method under analysis.
bool isReferenceType() const
Definition: Type.h:6313
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:49
Represents Objective-C&#39;s @catch statement.
Definition: StmtObjC.h:73
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:726
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3313
bool isVolatileQualified() const
Determine whether this type is volatile-qualified.
Definition: Type.h:6147
Expr * IgnoreParenCasts() LLVM_READONLY
Skip past any parentheses and casts which might surround this expression until reaching a fixed point...
Definition: Expr.cpp:2628
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:1648
bool isScalarType() const
Definition: Type.h:6642
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
bool hasAttr() const
Definition: DeclBase.h:533
Represents a single basic block in a source-level CFG.
Definition: CFG.h:551
This represents one expression.
Definition: Expr.h:108
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1002
bool hasLocalStorage() const
Returns true if a variable with function scope is a non-static local variable.
Definition: Decl.h:1035
Specifies that a value-dependent expression of integral or dependent type should be considered a null...
Definition: Expr.h:723
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:1929
ValueDecl * getDecl()
Definition: Expr.h:1147
bool isConstQualified() const
Determine whether this type is const-qualified.
Definition: Type.h:6136
static PathDiagnosticLocation createBegin(const Decl *D, const SourceManager &SM)
Create a location for the beginning of the declaration.
#define false
Definition: stdbool.h:33
Expr * getSubExpr() const
Definition: Expr.h:1959
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1139
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition: Decl.h:1077
const Decl * getDecl() const
bool isObjCObjectPointerType() const
Definition: Type.h:6398
SourceRange getSourceRange() const override LLVM_READONLY
Source range that this declaration covers.
Definition: Decl.cpp:1957
succ_iterator succ_end()
Definition: CFG.h:751
Expr * getLHS() const
Definition: Expr.h:3353
Dataflow Directional Tag Classes.
void VisitBlockStmts(CALLBACK &O) const
Definition: CFG.h:1154
static const Expr * LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex)
bool isLive(const Stmt *S) const
const Expr * getInit() const
Definition: Decl.h:1219
bool isMacroID() const
Opcode getOpcode() const
Definition: Expr.h:1954
Base for LValueReferenceType and RValueReferenceType.
Definition: Type.h:2678
Represents Objective-C&#39;s @finally statement.
Definition: StmtObjC.h:119
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:1404
Represents a C++ struct/union/class.
Definition: DeclCXX.h:299
static bool isCompoundAssignmentOp(Opcode Opc)
Definition: Expr.h:3441
CXXCatchStmt - This represents a C++ catch block.
Definition: StmtCXX.h:28
capture_range captures() const
Retrieve this lambda&#39;s captures.
Definition: ExprCXX.cpp:1165
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
Definition: Stmt.cpp:251
Stmt * getParentIgnoreParenCasts(Stmt *) const
Definition: ParentMap.cpp:133
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1074
Expr * getRHS() const
Definition: Expr.h:3355
bool isPointerType() const
Definition: Type.h:6301
QualType getType() const
Definition: Decl.h:647
A trivial tuple used to represent a source range.