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
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/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 DynamicRecursiveASTVisitor {
35public:
36 bool inEH;
37 llvm::DenseSet<const VarDecl *> &S;
38
39 bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) override {
40 SaveAndRestore inFinally(inEH, true);
41 return DynamicRecursiveASTVisitor::TraverseObjCAtFinallyStmt(S);
42 }
43
44 bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) override {
45 SaveAndRestore inCatch(inEH, true);
46 return DynamicRecursiveASTVisitor::TraverseObjCAtCatchStmt(S);
47 }
48
49 bool TraverseCXXCatchStmt(CXXCatchStmt *S) override {
50 SaveAndRestore inCatch(inEH, true);
51 return TraverseStmt(S: S->getHandlerBlock());
52 }
53
54 bool VisitDeclRefExpr(DeclRefExpr *DR) override {
55 if (inEH)
56 if (const VarDecl *D = dyn_cast<VarDecl>(Val: DR->getDecl()))
57 S.insert(V: 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(Elt: &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
96 for (const CFGBlock *succ : block->succs())
97 if (succ)
98 worklist.push_back(Elt: succ);
99 }
100}
101
102static const Expr *
103LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) {
104 while (Ex) {
105 Ex = Ex->IgnoreParenCasts();
106 const BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: Ex);
107 if (!BO)
108 break;
109 BinaryOperatorKind Op = BO->getOpcode();
110 if (Op == BO_Assign || Op == BO_Comma) {
111 Ex = BO->getRHS();
112 continue;
113 }
114 break;
115 }
116 return Ex;
117}
118
119namespace {
120class DeadStoresChecker : public Checker<check::ASTCodeBody> {
121public:
122 bool ShowFixIts = false;
123 bool WarnForDeadNestedAssignments = true;
124
125 void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
126 BugReporter &BR) const;
127};
128
129class DeadStoreObs : public LiveVariables::Observer {
130 const CFG &cfg;
131 ASTContext &Ctx;
132 BugReporter& BR;
133 const DeadStoresChecker *Checker;
134 AnalysisDeclContext* AC;
135 ParentMap& Parents;
136 llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
137 std::unique_ptr<ReachableCode> reachableCode;
138 const CFGBlock *currentBlock;
139 std::unique_ptr<llvm::DenseSet<const VarDecl *>> InEH;
140
141 enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
142
143public:
144 DeadStoreObs(const CFG &cfg, ASTContext &ctx, BugReporter &br,
145 const DeadStoresChecker *checker, AnalysisDeclContext *ac,
146 ParentMap &parents,
147 llvm::SmallPtrSet<const VarDecl *, 20> &escaped,
148 bool warnForDeadNestedAssignments)
149 : cfg(cfg), Ctx(ctx), BR(br), Checker(checker), AC(ac), Parents(parents),
150 Escaped(escaped), currentBlock(nullptr) {}
151
152 ~DeadStoreObs() override {}
153
154 bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) {
155 if (Live.isLive(D))
156 return true;
157 // Lazily construct the set that records which VarDecls are in
158 // EH code.
159 if (!InEH) {
160 InEH.reset(p: new llvm::DenseSet<const VarDecl *>());
161 EHCodeVisitor V(*InEH);
162 V.TraverseStmt(S: AC->getBody());
163 }
164 // Treat all VarDecls that occur in EH code as being "always live"
165 // when considering to suppress dead stores. Frequently stores
166 // are followed by reads in EH code, but we don't have the ability
167 // to analyze that yet.
168 return InEH->count(V: D);
169 }
170
171 bool isSuppressed(SourceRange R) {
172 SourceManager &SMgr = Ctx.getSourceManager();
173 SourceLocation Loc = R.getBegin();
174 if (!Loc.isValid())
175 return false;
176
177 FileID FID = SMgr.getFileID(SpellingLoc: Loc);
178 bool Invalid = false;
179 StringRef Data = SMgr.getBufferData(FID, Invalid: &Invalid);
180 if (Invalid)
181 return false;
182
183 // Files autogenerated by DriverKit IIG contain some dead stores that
184 // we don't want to report.
185 if (Data.starts_with(Prefix: "/* iig"))
186 return true;
187
188 return false;
189 }
190
191 void Report(const VarDecl *V, DeadStoreKind dsk,
192 PathDiagnosticLocation L, SourceRange R) {
193 if (Escaped.count(Ptr: V))
194 return;
195
196 // Compute reachable blocks within the CFG for trivial cases
197 // where a bogus dead store can be reported because itself is unreachable.
198 if (!reachableCode) {
199 reachableCode.reset(p: new ReachableCode(cfg));
200 reachableCode->computeReachableBlocks();
201 }
202
203 if (!reachableCode->isReachable(block: currentBlock))
204 return;
205
206 if (isSuppressed(R))
207 return;
208
209 SmallString<64> buf;
210 llvm::raw_svector_ostream os(buf);
211 const char *BugType = nullptr;
212
213 SmallVector<FixItHint, 1> Fixits;
214
215 switch (dsk) {
216 case DeadInit: {
217 BugType = "Dead initialization";
218 os << "Value stored to '" << *V
219 << "' during its initialization is never read";
220
221 ASTContext &ACtx = V->getASTContext();
222 if (Checker->ShowFixIts) {
223 if (V->getInit()->HasSideEffects(Ctx: ACtx,
224 /*IncludePossibleEffects=*/true)) {
225 break;
226 }
227 SourceManager &SM = ACtx.getSourceManager();
228 const LangOptions &LO = ACtx.getLangOpts();
229 SourceLocation L1 =
230 Lexer::findNextToken(
231 Loc: V->getTypeSourceInfo()->getTypeLoc().getEndLoc(),
232 SM, LangOpts: LO)->getEndLoc();
233 SourceLocation L2 =
234 Lexer::getLocForEndOfToken(Loc: V->getInit()->getEndLoc(), Offset: 1, SM, LangOpts: LO);
235 Fixits.push_back(Elt: FixItHint::CreateRemoval(RemoveRange: {L1, L2}));
236 }
237 break;
238 }
239
240 case DeadIncrement:
241 BugType = "Dead increment";
242 [[fallthrough]];
243 case Standard:
244 if (!BugType) BugType = "Dead assignment";
245 os << "Value stored to '" << *V << "' is never read";
246 break;
247
248 // eg.: f((x = foo()))
249 case Enclosing:
250 if (!Checker->WarnForDeadNestedAssignments)
251 return;
252 BugType = "Dead nested assignment";
253 os << "Although the value stored to '" << *V
254 << "' is used in the enclosing expression, the value is never "
255 "actually read from '"
256 << *V << "'";
257 break;
258 }
259
260 BR.EmitBasicReport(DeclWithIssue: AC->getDecl(), Checker, BugName: BugType, BugCategory: categories::UnusedCode,
261 BugStr: os.str(), Loc: L, Ranges: R, Fixits);
262 }
263
264 void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
265 DeadStoreKind dsk,
266 const LiveVariables::LivenessValues &Live) {
267
268 if (!VD->hasLocalStorage())
269 return;
270 // Reference types confuse the dead stores checker. Skip them
271 // for now.
272 if (VD->getType()->getAs<ReferenceType>())
273 return;
274
275 if (!isLive(Live, D: VD) &&
276 !(VD->hasAttr<UnusedAttr>() || VD->hasAttr<BlocksAttr>() ||
277 VD->hasAttr<ObjCPreciseLifetimeAttr>())) {
278
279 PathDiagnosticLocation ExLoc =
280 PathDiagnosticLocation::createBegin(S: Ex, SM: BR.getSourceManager(), LAC: AC);
281 Report(V: VD, dsk, L: ExLoc, R: Val->getSourceRange());
282 }
283 }
284
285 void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
286 const LiveVariables::LivenessValues& Live) {
287 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: DR->getDecl()))
288 CheckVarDecl(VD, Ex: DR, Val, dsk, Live);
289 }
290
291 bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
292 if (B->isCompoundAssignmentOp())
293 return true;
294
295 const Expr *RHS = B->getRHS()->IgnoreParenCasts();
296 const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(Val: RHS);
297
298 if (!BRHS)
299 return false;
300
301 const DeclRefExpr *DR;
302
303 if ((DR = dyn_cast<DeclRefExpr>(Val: BRHS->getLHS()->IgnoreParenCasts())))
304 if (DR->getDecl() == VD)
305 return true;
306
307 if ((DR = dyn_cast<DeclRefExpr>(Val: BRHS->getRHS()->IgnoreParenCasts())))
308 if (DR->getDecl() == VD)
309 return true;
310
311 return false;
312 }
313
314 void observeStmt(const Stmt *S, const CFGBlock *block,
315 const LiveVariables::LivenessValues &Live) override {
316
317 currentBlock = block;
318
319 // Skip statements in macros.
320 if (S->getBeginLoc().isMacroID())
321 return;
322
323 // Only cover dead stores from regular assignments. ++/-- dead stores
324 // have never flagged a real bug.
325 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(Val: S)) {
326 if (!B->isAssignmentOp()) return; // Skip non-assignments.
327
328 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Val: B->getLHS()))
329 if (VarDecl *VD = dyn_cast<VarDecl>(Val: DR->getDecl())) {
330 // Special case: check for assigning null to a pointer.
331 // This is a common form of defensive programming.
332 const Expr *RHS =
333 LookThroughTransitiveAssignmentsAndCommaOperators(Ex: B->getRHS());
334
335 QualType T = VD->getType();
336 if (T.isVolatileQualified())
337 return;
338 if (T->isPointerType() || T->isObjCObjectPointerType()) {
339 if (RHS->isNullPointerConstant(Ctx, NPC: Expr::NPC_ValueDependentIsNull))
340 return;
341 }
342
343 // Special case: self-assignments. These are often used to shut up
344 // "unused variable" compiler warnings.
345 if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(Val: RHS))
346 if (VD == dyn_cast<VarDecl>(Val: RhsDR->getDecl()))
347 return;
348
349 // Otherwise, issue a warning.
350 DeadStoreKind dsk = Parents.isConsumedExpr(E: B)
351 ? Enclosing
352 : (isIncrement(VD,B) ? DeadIncrement : Standard);
353
354 CheckVarDecl(VD, Ex: DR, Val: B->getRHS(), dsk, Live);
355 }
356 }
357 else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(Val: S)) {
358 if (!U->isIncrementOp() || U->isPrefix())
359 return;
360
361 const Stmt *parent = Parents.getParentIgnoreParenCasts(S: U);
362 if (!parent || !isa<ReturnStmt>(Val: parent))
363 return;
364
365 const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
366
367 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Val: Ex))
368 CheckDeclRef(DR, Val: U, dsk: DeadIncrement, Live);
369 }
370 else if (const DeclStmt *DS = dyn_cast<DeclStmt>(Val: S))
371 // Iterate through the decls. Warn if any initializers are complex
372 // expressions that are not live (never used).
373 for (const auto *DI : DS->decls()) {
374 const auto *V = dyn_cast<VarDecl>(Val: DI);
375
376 if (!V)
377 continue;
378
379 if (V->hasLocalStorage()) {
380 // Reference types confuse the dead stores checker. Skip them
381 // for now.
382 if (V->getType()->getAs<ReferenceType>())
383 return;
384
385 if (const Expr *E = V->getInit()) {
386 while (const FullExpr *FE = dyn_cast<FullExpr>(Val: E))
387 E = FE->getSubExpr();
388
389 // Look through transitive assignments, e.g.:
390 // int x = y = 0;
391 E = LookThroughTransitiveAssignmentsAndCommaOperators(Ex: E);
392
393 // Don't warn on C++ objects (yet) until we can show that their
394 // constructors/destructors don't have side effects.
395 if (isa<CXXConstructExpr>(Val: E))
396 return;
397
398 // A dead initialization is a variable that is dead after it
399 // is initialized. We don't flag warnings for those variables
400 // marked 'unused' or 'objc_precise_lifetime'.
401 if (!isLive(Live, D: V) &&
402 !V->hasAttr<UnusedAttr>() &&
403 !V->hasAttr<ObjCPreciseLifetimeAttr>()) {
404 // Special case: check for initializations with constants.
405 //
406 // e.g. : int x = 0;
407 // struct A = {0, 1};
408 // struct B = {{0}, {1, 2}};
409 //
410 // If x is EVER assigned a new value later, don't issue
411 // a warning. This is because such initialization can be
412 // due to defensive programming.
413 if (isConstant(E))
414 return;
415
416 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Val: E))
417 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: DRE->getDecl())) {
418 // Special case: check for initialization from constant
419 // variables.
420 //
421 // e.g. extern const int MyConstant;
422 // int x = MyConstant;
423 //
424 if (VD->hasGlobalStorage() &&
425 VD->getType().isConstQualified())
426 return;
427 // Special case: check for initialization from scalar
428 // parameters. This is often a form of defensive
429 // programming. Non-scalars are still an error since
430 // because it more likely represents an actual algorithmic
431 // bug.
432 if (isa<ParmVarDecl>(Val: VD) && VD->getType()->isScalarType())
433 return;
434 }
435
436 PathDiagnosticLocation Loc =
437 PathDiagnosticLocation::create(D: V, SM: BR.getSourceManager());
438 Report(V, dsk: DeadInit, L: Loc, R: V->getInit()->getSourceRange());
439 }
440 }
441 }
442 }
443 }
444
445private:
446 /// Return true if the given init list can be interpreted as constant
447 bool isConstant(const InitListExpr *Candidate) const {
448 // We consider init list to be constant if each member of the list can be
449 // interpreted as constant.
450 return llvm::all_of(Range: Candidate->inits(), P: [this](const Expr *Init) {
451 return isConstant(E: Init->IgnoreParenCasts());
452 });
453 }
454
455 /// Return true if the given expression can be interpreted as constant
456 bool isConstant(const Expr *E) const {
457 // It looks like E itself is a constant
458 if (E->isEvaluatable(Ctx))
459 return true;
460
461 // We should also allow defensive initialization of structs, i.e. { 0 }
462 if (const auto *ILE = dyn_cast<InitListExpr>(Val: E)) {
463 return isConstant(Candidate: ILE);
464 }
465
466 return false;
467 }
468};
469
470} // end anonymous namespace
471
472//===----------------------------------------------------------------------===//
473// Driver function to invoke the Dead-Stores checker on a CFG.
474//===----------------------------------------------------------------------===//
475
476namespace {
477class FindEscaped {
478public:
479 llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
480
481 void operator()(const Stmt *S) {
482 // Check for '&'. Any VarDecl whose address has been taken we treat as
483 // escaped.
484 // FIXME: What about references?
485 if (auto *LE = dyn_cast<LambdaExpr>(Val: S)) {
486 findLambdaReferenceCaptures(LE);
487 return;
488 }
489
490 const UnaryOperator *U = dyn_cast<UnaryOperator>(Val: S);
491 if (!U)
492 return;
493 if (U->getOpcode() != UO_AddrOf)
494 return;
495
496 const Expr *E = U->getSubExpr()->IgnoreParenCasts();
497 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Val: E))
498 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: DR->getDecl()))
499 Escaped.insert(Ptr: VD);
500 }
501
502 // Treat local variables captured by reference in C++ lambdas as escaped.
503 void findLambdaReferenceCaptures(const LambdaExpr *LE) {
504 const CXXRecordDecl *LambdaClass = LE->getLambdaClass();
505 llvm::DenseMap<const ValueDecl *, FieldDecl *> CaptureFields;
506 FieldDecl *ThisCaptureField;
507 LambdaClass->getCaptureFields(Captures&: CaptureFields, ThisCapture&: ThisCaptureField);
508
509 for (const LambdaCapture &C : LE->captures()) {
510 if (!C.capturesVariable())
511 continue;
512
513 ValueDecl *VD = C.getCapturedVar();
514 const FieldDecl *FD = CaptureFields[VD];
515 if (!FD || !isa<VarDecl>(Val: VD))
516 continue;
517
518 // If the capture field is a reference type, it is capture-by-reference.
519 if (FD->getType()->isReferenceType())
520 Escaped.insert(Ptr: cast<VarDecl>(Val: VD));
521 }
522 }
523};
524} // end anonymous namespace
525
526
527//===----------------------------------------------------------------------===//
528// DeadStoresChecker
529//===----------------------------------------------------------------------===//
530
531void DeadStoresChecker::checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
532 BugReporter &BR) const {
533
534 // Don't do anything for template instantiations.
535 // Proving that code in a template instantiation is "dead"
536 // means proving that it is dead in all instantiations.
537 // This same problem exists with -Wunreachable-code.
538 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(Val: D))
539 if (FD->isTemplateInstantiation())
540 return;
541
542 if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
543 CFG &cfg = *mgr.getCFG(D);
544 AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
545 ParentMap &pmap = mgr.getParentMap(D);
546 FindEscaped FS;
547 cfg.VisitBlockStmts(O&: FS);
548 DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped,
549 WarnForDeadNestedAssignments);
550 L->runOnAllBlocks(obs&: A);
551 }
552}
553
554void ento::registerDeadStoresChecker(CheckerManager &Mgr) {
555 auto *Chk = Mgr.registerChecker<DeadStoresChecker>();
556
557 const AnalyzerOptions &AnOpts = Mgr.getAnalyzerOptions();
558 Chk->WarnForDeadNestedAssignments =
559 AnOpts.getCheckerBooleanOption(C: Chk, OptionName: "WarnForDeadNestedAssignments");
560 Chk->ShowFixIts =
561 AnOpts.getCheckerBooleanOption(C: Chk, OptionName: "ShowFixIts");
562}
563
564bool ento::shouldRegisterDeadStoresChecker(const CheckerManager &mgr) {
565 return true;
566}
567