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/ParentMap.h"
17#include "clang/AST/RecursiveASTVisitor.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"
28
29using namespace clang;
30using namespace ento;
31
32namespace {
33
34/// A simple visitor to record what VarDecls occur in EH-handling code.
35class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> {
36public:
37 bool inEH;
38 llvm::DenseSet<const VarDecl *> &S;
39
40 bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) {
41 SaveAndRestore inFinally(inEH, true);
42 return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S);
43 }
44
45 bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) {
46 SaveAndRestore inCatch(inEH, true);
47 return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S);
48 }
49
50 bool TraverseCXXCatchStmt(CXXCatchStmt *S) {
51 SaveAndRestore inCatch(inEH, true);
52 return TraverseStmt(S: S->getHandlerBlock());
53 }
54
55 bool VisitDeclRefExpr(DeclRefExpr *DR) {
56 if (inEH)
57 if (const VarDecl *D = dyn_cast<VarDecl>(Val: DR->getDecl()))
58 S.insert(V: D);
59 return true;
60 }
61
62 EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) :
63 inEH(false), S(S) {}
64};
65
66// FIXME: Eventually migrate into its own file, and have it managed by
67// AnalysisManager.
68class ReachableCode {
69 const CFG &cfg;
70 llvm::BitVector reachable;
71public:
72 ReachableCode(const CFG &cfg)
73 : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
74
75 void computeReachableBlocks();
76
77 bool isReachable(const CFGBlock *block) const {
78 return reachable[block->getBlockID()];
79 }
80};
81}
82
83void ReachableCode::computeReachableBlocks() {
84 if (!cfg.getNumBlockIDs())
85 return;
86
87 SmallVector<const CFGBlock*, 10> worklist;
88 worklist.push_back(Elt: &cfg.getEntry());
89
90 while (!worklist.empty()) {
91 const CFGBlock *block = worklist.pop_back_val();
92 llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
93 if (isReachable)
94 continue;
95 isReachable = true;
96
97 for (const CFGBlock *succ : block->succs())
98 if (succ)
99 worklist.push_back(Elt: succ);
100 }
101}
102
103static const Expr *
104LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) {
105 while (Ex) {
106 Ex = Ex->IgnoreParenCasts();
107 const BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: Ex);
108 if (!BO)
109 break;
110 BinaryOperatorKind Op = BO->getOpcode();
111 if (Op == BO_Assign || Op == BO_Comma) {
112 Ex = BO->getRHS();
113 continue;
114 }
115 break;
116 }
117 return Ex;
118}
119
120namespace {
121class DeadStoresChecker : public Checker<check::ASTCodeBody> {
122public:
123 bool ShowFixIts = false;
124 bool WarnForDeadNestedAssignments = true;
125
126 void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
127 BugReporter &BR) const;
128};
129
130class DeadStoreObs : public LiveVariables::Observer {
131 const CFG &cfg;
132 ASTContext &Ctx;
133 BugReporter& BR;
134 const DeadStoresChecker *Checker;
135 AnalysisDeclContext* AC;
136 ParentMap& Parents;
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;
141
142 enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
143
144public:
145 DeadStoreObs(const CFG &cfg, ASTContext &ctx, BugReporter &br,
146 const DeadStoresChecker *checker, AnalysisDeclContext *ac,
147 ParentMap &parents,
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) {}
152
153 ~DeadStoreObs() override {}
154
155 bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) {
156 if (Live.isLive(D))
157 return true;
158 // Lazily construct the set that records which VarDecls are in
159 // EH code.
160 if (!InEH.get()) {
161 InEH.reset(p: new llvm::DenseSet<const VarDecl *>());
162 EHCodeVisitor V(*InEH.get());
163 V.TraverseStmt(S: AC->getBody());
164 }
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(V: D);
170 }
171
172 bool isSuppressed(SourceRange R) {
173 SourceManager &SMgr = Ctx.getSourceManager();
174 SourceLocation Loc = R.getBegin();
175 if (!Loc.isValid())
176 return false;
177
178 FileID FID = SMgr.getFileID(SpellingLoc: Loc);
179 bool Invalid = false;
180 StringRef Data = SMgr.getBufferData(FID, Invalid: &Invalid);
181 if (Invalid)
182 return false;
183
184 // Files autogenerated by DriverKit IIG contain some dead stores that
185 // we don't want to report.
186 if (Data.starts_with(Prefix: "/* iig"))
187 return true;
188
189 return false;
190 }
191
192 void Report(const VarDecl *V, DeadStoreKind dsk,
193 PathDiagnosticLocation L, SourceRange R) {
194 if (Escaped.count(Ptr: V))
195 return;
196
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(p: new ReachableCode(cfg));
201 reachableCode->computeReachableBlocks();
202 }
203
204 if (!reachableCode->isReachable(block: currentBlock))
205 return;
206
207 if (isSuppressed(R))
208 return;
209
210 SmallString<64> buf;
211 llvm::raw_svector_ostream os(buf);
212 const char *BugType = nullptr;
213
214 SmallVector<FixItHint, 1> Fixits;
215
216 switch (dsk) {
217 case DeadInit: {
218 BugType = "Dead initialization";
219 os << "Value stored to '" << *V
220 << "' during its initialization is never read";
221
222 ASTContext &ACtx = V->getASTContext();
223 if (Checker->ShowFixIts) {
224 if (V->getInit()->HasSideEffects(Ctx: ACtx,
225 /*IncludePossibleEffects=*/true)) {
226 break;
227 }
228 SourceManager &SM = ACtx.getSourceManager();
229 const LangOptions &LO = ACtx.getLangOpts();
230 SourceLocation L1 =
231 Lexer::findNextToken(
232 Loc: V->getTypeSourceInfo()->getTypeLoc().getEndLoc(),
233 SM, LangOpts: LO)->getEndLoc();
234 SourceLocation L2 =
235 Lexer::getLocForEndOfToken(Loc: V->getInit()->getEndLoc(), Offset: 1, SM, LangOpts: LO);
236 Fixits.push_back(Elt: FixItHint::CreateRemoval(RemoveRange: {L1, L2}));
237 }
238 break;
239 }
240
241 case DeadIncrement:
242 BugType = "Dead increment";
243 [[fallthrough]];
244 case Standard:
245 if (!BugType) BugType = "Dead assignment";
246 os << "Value stored to '" << *V << "' is never read";
247 break;
248
249 // eg.: f((x = foo()))
250 case Enclosing:
251 if (!Checker->WarnForDeadNestedAssignments)
252 return;
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 '"
257 << *V << "'";
258 break;
259 }
260
261 BR.EmitBasicReport(DeclWithIssue: AC->getDecl(), Checker, BugName: BugType, BugCategory: categories::UnusedCode,
262 BugStr: os.str(), Loc: L, Ranges: R, Fixits);
263 }
264
265 void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
266 DeadStoreKind dsk,
267 const LiveVariables::LivenessValues &Live) {
268
269 if (!VD->hasLocalStorage())
270 return;
271 // Reference types confuse the dead stores checker. Skip them
272 // for now.
273 if (VD->getType()->getAs<ReferenceType>())
274 return;
275
276 if (!isLive(Live, D: VD) &&
277 !(VD->hasAttr<UnusedAttr>() || VD->hasAttr<BlocksAttr>() ||
278 VD->hasAttr<ObjCPreciseLifetimeAttr>())) {
279
280 PathDiagnosticLocation ExLoc =
281 PathDiagnosticLocation::createBegin(S: Ex, SM: BR.getSourceManager(), LAC: AC);
282 Report(V: VD, dsk, L: ExLoc, R: Val->getSourceRange());
283 }
284 }
285
286 void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
287 const LiveVariables::LivenessValues& Live) {
288 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: DR->getDecl()))
289 CheckVarDecl(VD, Ex: DR, Val, dsk, Live);
290 }
291
292 bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
293 if (B->isCompoundAssignmentOp())
294 return true;
295
296 const Expr *RHS = B->getRHS()->IgnoreParenCasts();
297 const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(Val: RHS);
298
299 if (!BRHS)
300 return false;
301
302 const DeclRefExpr *DR;
303
304 if ((DR = dyn_cast<DeclRefExpr>(Val: BRHS->getLHS()->IgnoreParenCasts())))
305 if (DR->getDecl() == VD)
306 return true;
307
308 if ((DR = dyn_cast<DeclRefExpr>(Val: BRHS->getRHS()->IgnoreParenCasts())))
309 if (DR->getDecl() == VD)
310 return true;
311
312 return false;
313 }
314
315 void observeStmt(const Stmt *S, const CFGBlock *block,
316 const LiveVariables::LivenessValues &Live) override {
317
318 currentBlock = block;
319
320 // Skip statements in macros.
321 if (S->getBeginLoc().isMacroID())
322 return;
323
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>(Val: S)) {
327 if (!B->isAssignmentOp()) return; // Skip non-assignments.
328
329 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Val: B->getLHS()))
330 if (VarDecl *VD = dyn_cast<VarDecl>(Val: DR->getDecl())) {
331 // Special case: check for assigning null to a pointer.
332 // This is a common form of defensive programming.
333 const Expr *RHS =
334 LookThroughTransitiveAssignmentsAndCommaOperators(Ex: B->getRHS());
335
336 QualType T = VD->getType();
337 if (T.isVolatileQualified())
338 return;
339 if (T->isPointerType() || T->isObjCObjectPointerType()) {
340 if (RHS->isNullPointerConstant(Ctx, NPC: Expr::NPC_ValueDependentIsNull))
341 return;
342 }
343
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>(Val: RHS))
347 if (VD == dyn_cast<VarDecl>(Val: RhsDR->getDecl()))
348 return;
349
350 // Otherwise, issue a warning.
351 DeadStoreKind dsk = Parents.isConsumedExpr(E: B)
352 ? Enclosing
353 : (isIncrement(VD,B) ? DeadIncrement : Standard);
354
355 CheckVarDecl(VD, Ex: DR, Val: B->getRHS(), dsk, Live);
356 }
357 }
358 else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(Val: S)) {
359 if (!U->isIncrementOp() || U->isPrefix())
360 return;
361
362 const Stmt *parent = Parents.getParentIgnoreParenCasts(S: U);
363 if (!parent || !isa<ReturnStmt>(Val: parent))
364 return;
365
366 const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
367
368 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Val: Ex))
369 CheckDeclRef(DR, Val: U, dsk: DeadIncrement, Live);
370 }
371 else if (const DeclStmt *DS = dyn_cast<DeclStmt>(Val: 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>(Val: DI);
376
377 if (!V)
378 continue;
379
380 if (V->hasLocalStorage()) {
381 // Reference types confuse the dead stores checker. Skip them
382 // for now.
383 if (V->getType()->getAs<ReferenceType>())
384 return;
385
386 if (const Expr *E = V->getInit()) {
387 while (const FullExpr *FE = dyn_cast<FullExpr>(Val: E))
388 E = FE->getSubExpr();
389
390 // Look through transitive assignments, e.g.:
391 // int x = y = 0;
392 E = LookThroughTransitiveAssignmentsAndCommaOperators(Ex: E);
393
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>(Val: E))
397 return;
398
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, D: V) &&
403 !V->hasAttr<UnusedAttr>() &&
404 !V->hasAttr<ObjCPreciseLifetimeAttr>()) {
405 // Special case: check for initializations with constants.
406 //
407 // e.g. : int x = 0;
408 // struct A = {0, 1};
409 // struct B = {{0}, {1, 2}};
410 //
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.
414 if (isConstant(E))
415 return;
416
417 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Val: E))
418 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: DRE->getDecl())) {
419 // Special case: check for initialization from constant
420 // variables.
421 //
422 // e.g. extern const int MyConstant;
423 // int x = MyConstant;
424 //
425 if (VD->hasGlobalStorage() &&
426 VD->getType().isConstQualified())
427 return;
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
432 // bug.
433 if (isa<ParmVarDecl>(Val: VD) && VD->getType()->isScalarType())
434 return;
435 }
436
437 PathDiagnosticLocation Loc =
438 PathDiagnosticLocation::create(D: V, SM: BR.getSourceManager());
439 Report(V, dsk: DeadInit, L: Loc, R: V->getInit()->getSourceRange());
440 }
441 }
442 }
443 }
444 }
445
446private:
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(Range: Candidate->inits(), P: [this](const Expr *Init) {
452 return isConstant(E: Init->IgnoreParenCasts());
453 });
454 }
455
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))
460 return true;
461
462 // We should also allow defensive initialization of structs, i.e. { 0 }
463 if (const auto *ILE = dyn_cast<InitListExpr>(Val: E)) {
464 return isConstant(Candidate: ILE);
465 }
466
467 return false;
468 }
469};
470
471} // end anonymous namespace
472
473//===----------------------------------------------------------------------===//
474// Driver function to invoke the Dead-Stores checker on a CFG.
475//===----------------------------------------------------------------------===//
476
477namespace {
478class FindEscaped {
479public:
480 llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
481
482 void operator()(const Stmt *S) {
483 // Check for '&'. Any VarDecl whose address has been taken we treat as
484 // escaped.
485 // FIXME: What about references?
486 if (auto *LE = dyn_cast<LambdaExpr>(Val: S)) {
487 findLambdaReferenceCaptures(LE);
488 return;
489 }
490
491 const UnaryOperator *U = dyn_cast<UnaryOperator>(Val: S);
492 if (!U)
493 return;
494 if (U->getOpcode() != UO_AddrOf)
495 return;
496
497 const Expr *E = U->getSubExpr()->IgnoreParenCasts();
498 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Val: E))
499 if (const VarDecl *VD = dyn_cast<VarDecl>(Val: DR->getDecl()))
500 Escaped.insert(Ptr: VD);
501 }
502
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(Captures&: CaptureFields, ThisCapture&: ThisCaptureField);
509
510 for (const LambdaCapture &C : LE->captures()) {
511 if (!C.capturesVariable())
512 continue;
513
514 ValueDecl *VD = C.getCapturedVar();
515 const FieldDecl *FD = CaptureFields[VD];
516 if (!FD || !isa<VarDecl>(Val: VD))
517 continue;
518
519 // If the capture field is a reference type, it is capture-by-reference.
520 if (FD->getType()->isReferenceType())
521 Escaped.insert(Ptr: cast<VarDecl>(Val: VD));
522 }
523 }
524};
525} // end anonymous namespace
526
527
528//===----------------------------------------------------------------------===//
529// DeadStoresChecker
530//===----------------------------------------------------------------------===//
531
532void DeadStoresChecker::checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
533 BugReporter &BR) const {
534
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>(Val: D))
540 if (FD->isTemplateInstantiation())
541 return;
542
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);
547 FindEscaped FS;
548 cfg.VisitBlockStmts(O&: FS);
549 DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped,
550 WarnForDeadNestedAssignments);
551 L->runOnAllBlocks(obs&: A);
552 }
553}
554
555void ento::registerDeadStoresChecker(CheckerManager &Mgr) {
556 auto *Chk = Mgr.registerChecker<DeadStoresChecker>();
557
558 const AnalyzerOptions &AnOpts = Mgr.getAnalyzerOptions();
559 Chk->WarnForDeadNestedAssignments =
560 AnOpts.getCheckerBooleanOption(C: Chk, OptionName: "WarnForDeadNestedAssignments");
561 Chk->ShowFixIts =
562 AnOpts.getCheckerBooleanOption(C: Chk, OptionName: "ShowFixIts");
563}
564
565bool ento::shouldRegisterDeadStoresChecker(const CheckerManager &mgr) {
566 return true;
567}
568