1 //==- DeadStoresChecker.cpp - Check for stores to dead variables -*- C++ -*-==//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines a DeadStores, a flow-sensitive checker that looks for
10 // stores to variables that are no longer live.
12 //===----------------------------------------------------------------------===//
14 #include "clang/AST/ASTContext.h"
15 #include "clang/AST/Attr.h"
16 #include "clang/AST/DynamicRecursiveASTVisitor.h"
17 #include "clang/AST/ParentMap.h"
18 #include "clang/Analysis/Analyses/LiveVariables.h"
19 #include "clang/Lex/Lexer.h"
20 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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/STLExtras.h"
26 #include "llvm/ADT/SmallString.h"
27 #include "llvm/Support/SaveAndRestore.h"
29 using namespace clang
;
34 /// A simple visitor to record what VarDecls occur in EH-handling code.
35 class EHCodeVisitor
: public DynamicRecursiveASTVisitor
{
38 llvm::DenseSet
<const VarDecl
*> &S
;
40 bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt
*S
) override
{
41 SaveAndRestore
inFinally(inEH
, true);
42 return DynamicRecursiveASTVisitor::TraverseObjCAtFinallyStmt(S
);
45 bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt
*S
) override
{
46 SaveAndRestore
inCatch(inEH
, true);
47 return DynamicRecursiveASTVisitor::TraverseObjCAtCatchStmt(S
);
50 bool TraverseCXXCatchStmt(CXXCatchStmt
*S
) override
{
51 SaveAndRestore
inCatch(inEH
, true);
52 return TraverseStmt(S
->getHandlerBlock());
55 bool VisitDeclRefExpr(DeclRefExpr
*DR
) override
{
57 if (const VarDecl
*D
= dyn_cast
<VarDecl
>(DR
->getDecl()))
62 EHCodeVisitor(llvm::DenseSet
<const VarDecl
*> &S
) :
66 // FIXME: Eventually migrate into its own file, and have it managed by
70 llvm::BitVector reachable
;
72 ReachableCode(const CFG
&cfg
)
73 : cfg(cfg
), reachable(cfg
.getNumBlockIDs(), false) {}
75 void computeReachableBlocks();
77 bool isReachable(const CFGBlock
*block
) const {
78 return reachable
[block
->getBlockID()];
83 void ReachableCode::computeReachableBlocks() {
84 if (!cfg
.getNumBlockIDs())
87 SmallVector
<const CFGBlock
*, 10> worklist
;
88 worklist
.push_back(&cfg
.getEntry());
90 while (!worklist
.empty()) {
91 const CFGBlock
*block
= worklist
.pop_back_val();
92 llvm::BitVector::reference isReachable
= reachable
[block
->getBlockID()];
97 for (const CFGBlock
*succ
: block
->succs())
99 worklist
.push_back(succ
);
104 LookThroughTransitiveAssignmentsAndCommaOperators(const Expr
*Ex
) {
106 Ex
= Ex
->IgnoreParenCasts();
107 const BinaryOperator
*BO
= dyn_cast
<BinaryOperator
>(Ex
);
110 BinaryOperatorKind Op
= BO
->getOpcode();
111 if (Op
== BO_Assign
|| Op
== BO_Comma
) {
121 class DeadStoresChecker
: public Checker
<check::ASTCodeBody
> {
123 bool ShowFixIts
= false;
124 bool WarnForDeadNestedAssignments
= true;
126 void checkASTCodeBody(const Decl
*D
, AnalysisManager
&Mgr
,
127 BugReporter
&BR
) const;
130 class DeadStoreObs
: public LiveVariables::Observer
{
134 const DeadStoresChecker
*Checker
;
135 AnalysisDeclContext
* AC
;
137 llvm::SmallPtrSet
<const VarDecl
*, 20> Escaped
;
138 std::unique_ptr
<ReachableCode
> reachableCode
;
139 const CFGBlock
*currentBlock
;
140 std::unique_ptr
<llvm::DenseSet
<const VarDecl
*>> InEH
;
142 enum DeadStoreKind
{ Standard
, Enclosing
, DeadIncrement
, DeadInit
};
145 DeadStoreObs(const CFG
&cfg
, ASTContext
&ctx
, BugReporter
&br
,
146 const DeadStoresChecker
*checker
, AnalysisDeclContext
*ac
,
148 llvm::SmallPtrSet
<const VarDecl
*, 20> &escaped
,
149 bool warnForDeadNestedAssignments
)
150 : cfg(cfg
), Ctx(ctx
), BR(br
), Checker(checker
), AC(ac
), Parents(parents
),
151 Escaped(escaped
), currentBlock(nullptr) {}
153 ~DeadStoreObs() override
{}
155 bool isLive(const LiveVariables::LivenessValues
&Live
, const VarDecl
*D
) {
158 // Lazily construct the set that records which VarDecls are in
161 InEH
.reset(new llvm::DenseSet
<const VarDecl
*>());
162 EHCodeVisitor
V(*InEH
.get());
163 V
.TraverseStmt(AC
->getBody());
165 // Treat all VarDecls that occur in EH code as being "always live"
166 // when considering to suppress dead stores. Frequently stores
167 // are followed by reads in EH code, but we don't have the ability
168 // to analyze that yet.
169 return InEH
->count(D
);
172 bool isSuppressed(SourceRange R
) {
173 SourceManager
&SMgr
= Ctx
.getSourceManager();
174 SourceLocation Loc
= R
.getBegin();
178 FileID FID
= SMgr
.getFileID(Loc
);
179 bool Invalid
= false;
180 StringRef Data
= SMgr
.getBufferData(FID
, &Invalid
);
184 // Files autogenerated by DriverKit IIG contain some dead stores that
185 // we don't want to report.
186 if (Data
.starts_with("/* iig"))
192 void Report(const VarDecl
*V
, DeadStoreKind dsk
,
193 PathDiagnosticLocation L
, SourceRange R
) {
194 if (Escaped
.count(V
))
197 // Compute reachable blocks within the CFG for trivial cases
198 // where a bogus dead store can be reported because itself is unreachable.
199 if (!reachableCode
.get()) {
200 reachableCode
.reset(new ReachableCode(cfg
));
201 reachableCode
->computeReachableBlocks();
204 if (!reachableCode
->isReachable(currentBlock
))
211 llvm::raw_svector_ostream
os(buf
);
212 const char *BugType
= nullptr;
214 SmallVector
<FixItHint
, 1> Fixits
;
218 BugType
= "Dead initialization";
219 os
<< "Value stored to '" << *V
220 << "' during its initialization is never read";
222 ASTContext
&ACtx
= V
->getASTContext();
223 if (Checker
->ShowFixIts
) {
224 if (V
->getInit()->HasSideEffects(ACtx
,
225 /*IncludePossibleEffects=*/true)) {
228 SourceManager
&SM
= ACtx
.getSourceManager();
229 const LangOptions
&LO
= ACtx
.getLangOpts();
231 Lexer::findNextToken(
232 V
->getTypeSourceInfo()->getTypeLoc().getEndLoc(),
233 SM
, LO
)->getEndLoc();
235 Lexer::getLocForEndOfToken(V
->getInit()->getEndLoc(), 1, SM
, LO
);
236 Fixits
.push_back(FixItHint::CreateRemoval({L1
, L2
}));
242 BugType
= "Dead increment";
245 if (!BugType
) BugType
= "Dead assignment";
246 os
<< "Value stored to '" << *V
<< "' is never read";
249 // eg.: f((x = foo()))
251 if (!Checker
->WarnForDeadNestedAssignments
)
253 BugType
= "Dead nested assignment";
254 os
<< "Although the value stored to '" << *V
255 << "' is used in the enclosing expression, the value is never "
256 "actually read from '"
261 BR
.EmitBasicReport(AC
->getDecl(), Checker
, BugType
, categories::UnusedCode
,
262 os
.str(), L
, R
, Fixits
);
265 void CheckVarDecl(const VarDecl
*VD
, const Expr
*Ex
, const Expr
*Val
,
267 const LiveVariables::LivenessValues
&Live
) {
269 if (!VD
->hasLocalStorage())
271 // Reference types confuse the dead stores checker. Skip them
273 if (VD
->getType()->getAs
<ReferenceType
>())
276 if (!isLive(Live
, VD
) &&
277 !(VD
->hasAttr
<UnusedAttr
>() || VD
->hasAttr
<BlocksAttr
>() ||
278 VD
->hasAttr
<ObjCPreciseLifetimeAttr
>())) {
280 PathDiagnosticLocation ExLoc
=
281 PathDiagnosticLocation::createBegin(Ex
, BR
.getSourceManager(), AC
);
282 Report(VD
, dsk
, ExLoc
, Val
->getSourceRange());
286 void CheckDeclRef(const DeclRefExpr
*DR
, const Expr
*Val
, DeadStoreKind dsk
,
287 const LiveVariables::LivenessValues
& Live
) {
288 if (const VarDecl
*VD
= dyn_cast
<VarDecl
>(DR
->getDecl()))
289 CheckVarDecl(VD
, DR
, Val
, dsk
, Live
);
292 bool isIncrement(VarDecl
*VD
, const BinaryOperator
* B
) {
293 if (B
->isCompoundAssignmentOp())
296 const Expr
*RHS
= B
->getRHS()->IgnoreParenCasts();
297 const BinaryOperator
* BRHS
= dyn_cast
<BinaryOperator
>(RHS
);
302 const DeclRefExpr
*DR
;
304 if ((DR
= dyn_cast
<DeclRefExpr
>(BRHS
->getLHS()->IgnoreParenCasts())))
305 if (DR
->getDecl() == VD
)
308 if ((DR
= dyn_cast
<DeclRefExpr
>(BRHS
->getRHS()->IgnoreParenCasts())))
309 if (DR
->getDecl() == VD
)
315 void observeStmt(const Stmt
*S
, const CFGBlock
*block
,
316 const LiveVariables::LivenessValues
&Live
) override
{
318 currentBlock
= block
;
320 // Skip statements in macros.
321 if (S
->getBeginLoc().isMacroID())
324 // Only cover dead stores from regular assignments. ++/-- dead stores
325 // have never flagged a real bug.
326 if (const BinaryOperator
* B
= dyn_cast
<BinaryOperator
>(S
)) {
327 if (!B
->isAssignmentOp()) return; // Skip non-assignments.
329 if (DeclRefExpr
*DR
= dyn_cast
<DeclRefExpr
>(B
->getLHS()))
330 if (VarDecl
*VD
= dyn_cast
<VarDecl
>(DR
->getDecl())) {
331 // Special case: check for assigning null to a pointer.
332 // This is a common form of defensive programming.
334 LookThroughTransitiveAssignmentsAndCommaOperators(B
->getRHS());
336 QualType T
= VD
->getType();
337 if (T
.isVolatileQualified())
339 if (T
->isPointerType() || T
->isObjCObjectPointerType()) {
340 if (RHS
->isNullPointerConstant(Ctx
, Expr::NPC_ValueDependentIsNull
))
344 // Special case: self-assignments. These are often used to shut up
345 // "unused variable" compiler warnings.
346 if (const DeclRefExpr
*RhsDR
= dyn_cast
<DeclRefExpr
>(RHS
))
347 if (VD
== dyn_cast
<VarDecl
>(RhsDR
->getDecl()))
350 // Otherwise, issue a warning.
351 DeadStoreKind dsk
= Parents
.isConsumedExpr(B
)
353 : (isIncrement(VD
,B
) ? DeadIncrement
: Standard
);
355 CheckVarDecl(VD
, DR
, B
->getRHS(), dsk
, Live
);
358 else if (const UnaryOperator
* U
= dyn_cast
<UnaryOperator
>(S
)) {
359 if (!U
->isIncrementOp() || U
->isPrefix())
362 const Stmt
*parent
= Parents
.getParentIgnoreParenCasts(U
);
363 if (!parent
|| !isa
<ReturnStmt
>(parent
))
366 const Expr
*Ex
= U
->getSubExpr()->IgnoreParenCasts();
368 if (const DeclRefExpr
*DR
= dyn_cast
<DeclRefExpr
>(Ex
))
369 CheckDeclRef(DR
, U
, DeadIncrement
, Live
);
371 else if (const DeclStmt
*DS
= dyn_cast
<DeclStmt
>(S
))
372 // Iterate through the decls. Warn if any initializers are complex
373 // expressions that are not live (never used).
374 for (const auto *DI
: DS
->decls()) {
375 const auto *V
= dyn_cast
<VarDecl
>(DI
);
380 if (V
->hasLocalStorage()) {
381 // Reference types confuse the dead stores checker. Skip them
383 if (V
->getType()->getAs
<ReferenceType
>())
386 if (const Expr
*E
= V
->getInit()) {
387 while (const FullExpr
*FE
= dyn_cast
<FullExpr
>(E
))
388 E
= FE
->getSubExpr();
390 // Look through transitive assignments, e.g.:
392 E
= LookThroughTransitiveAssignmentsAndCommaOperators(E
);
394 // Don't warn on C++ objects (yet) until we can show that their
395 // constructors/destructors don't have side effects.
396 if (isa
<CXXConstructExpr
>(E
))
399 // A dead initialization is a variable that is dead after it
400 // is initialized. We don't flag warnings for those variables
401 // marked 'unused' or 'objc_precise_lifetime'.
402 if (!isLive(Live
, V
) &&
403 !V
->hasAttr
<UnusedAttr
>() &&
404 !V
->hasAttr
<ObjCPreciseLifetimeAttr
>()) {
405 // Special case: check for initializations with constants.
408 // struct A = {0, 1};
409 // struct B = {{0}, {1, 2}};
411 // If x is EVER assigned a new value later, don't issue
412 // a warning. This is because such initialization can be
413 // due to defensive programming.
417 if (const DeclRefExpr
*DRE
= dyn_cast
<DeclRefExpr
>(E
))
418 if (const VarDecl
*VD
= dyn_cast
<VarDecl
>(DRE
->getDecl())) {
419 // Special case: check for initialization from constant
422 // e.g. extern const int MyConstant;
423 // int x = MyConstant;
425 if (VD
->hasGlobalStorage() &&
426 VD
->getType().isConstQualified())
428 // Special case: check for initialization from scalar
429 // parameters. This is often a form of defensive
430 // programming. Non-scalars are still an error since
431 // because it more likely represents an actual algorithmic
433 if (isa
<ParmVarDecl
>(VD
) && VD
->getType()->isScalarType())
437 PathDiagnosticLocation Loc
=
438 PathDiagnosticLocation::create(V
, BR
.getSourceManager());
439 Report(V
, DeadInit
, Loc
, V
->getInit()->getSourceRange());
447 /// Return true if the given init list can be interpreted as constant
448 bool isConstant(const InitListExpr
*Candidate
) const {
449 // We consider init list to be constant if each member of the list can be
450 // interpreted as constant.
451 return llvm::all_of(Candidate
->inits(), [this](const Expr
*Init
) {
452 return isConstant(Init
->IgnoreParenCasts());
456 /// Return true if the given expression can be interpreted as constant
457 bool isConstant(const Expr
*E
) const {
458 // It looks like E itself is a constant
459 if (E
->isEvaluatable(Ctx
))
462 // We should also allow defensive initialization of structs, i.e. { 0 }
463 if (const auto *ILE
= dyn_cast
<InitListExpr
>(E
)) {
464 return isConstant(ILE
);
471 } // end anonymous namespace
473 //===----------------------------------------------------------------------===//
474 // Driver function to invoke the Dead-Stores checker on a CFG.
475 //===----------------------------------------------------------------------===//
480 llvm::SmallPtrSet
<const VarDecl
*, 20> Escaped
;
482 void operator()(const Stmt
*S
) {
483 // Check for '&'. Any VarDecl whose address has been taken we treat as
485 // FIXME: What about references?
486 if (auto *LE
= dyn_cast
<LambdaExpr
>(S
)) {
487 findLambdaReferenceCaptures(LE
);
491 const UnaryOperator
*U
= dyn_cast
<UnaryOperator
>(S
);
494 if (U
->getOpcode() != UO_AddrOf
)
497 const Expr
*E
= U
->getSubExpr()->IgnoreParenCasts();
498 if (const DeclRefExpr
*DR
= dyn_cast
<DeclRefExpr
>(E
))
499 if (const VarDecl
*VD
= dyn_cast
<VarDecl
>(DR
->getDecl()))
503 // Treat local variables captured by reference in C++ lambdas as escaped.
504 void findLambdaReferenceCaptures(const LambdaExpr
*LE
) {
505 const CXXRecordDecl
*LambdaClass
= LE
->getLambdaClass();
506 llvm::DenseMap
<const ValueDecl
*, FieldDecl
*> CaptureFields
;
507 FieldDecl
*ThisCaptureField
;
508 LambdaClass
->getCaptureFields(CaptureFields
, ThisCaptureField
);
510 for (const LambdaCapture
&C
: LE
->captures()) {
511 if (!C
.capturesVariable())
514 ValueDecl
*VD
= C
.getCapturedVar();
515 const FieldDecl
*FD
= CaptureFields
[VD
];
516 if (!FD
|| !isa
<VarDecl
>(VD
))
519 // If the capture field is a reference type, it is capture-by-reference.
520 if (FD
->getType()->isReferenceType())
521 Escaped
.insert(cast
<VarDecl
>(VD
));
525 } // end anonymous namespace
528 //===----------------------------------------------------------------------===//
530 //===----------------------------------------------------------------------===//
532 void DeadStoresChecker::checkASTCodeBody(const Decl
*D
, AnalysisManager
&mgr
,
533 BugReporter
&BR
) const {
535 // Don't do anything for template instantiations.
536 // Proving that code in a template instantiation is "dead"
537 // means proving that it is dead in all instantiations.
538 // This same problem exists with -Wunreachable-code.
539 if (const FunctionDecl
*FD
= dyn_cast
<FunctionDecl
>(D
))
540 if (FD
->isTemplateInstantiation())
543 if (LiveVariables
*L
= mgr
.getAnalysis
<LiveVariables
>(D
)) {
544 CFG
&cfg
= *mgr
.getCFG(D
);
545 AnalysisDeclContext
*AC
= mgr
.getAnalysisDeclContext(D
);
546 ParentMap
&pmap
= mgr
.getParentMap(D
);
548 cfg
.VisitBlockStmts(FS
);
549 DeadStoreObs
A(cfg
, BR
.getContext(), BR
, this, AC
, pmap
, FS
.Escaped
,
550 WarnForDeadNestedAssignments
);
551 L
->runOnAllBlocks(A
);
555 void ento::registerDeadStoresChecker(CheckerManager
&Mgr
) {
556 auto *Chk
= Mgr
.registerChecker
<DeadStoresChecker
>();
558 const AnalyzerOptions
&AnOpts
= Mgr
.getAnalyzerOptions();
559 Chk
->WarnForDeadNestedAssignments
=
560 AnOpts
.getCheckerBooleanOption(Chk
, "WarnForDeadNestedAssignments");
562 AnOpts
.getCheckerBooleanOption(Chk
, "ShowFixIts");
565 bool ento::shouldRegisterDeadStoresChecker(const CheckerManager
&mgr
) {