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