[memprof] Update YAML traits for writer purposes (#118720)
[llvm-project.git] / clang / lib / StaticAnalyzer / Checkers / DeadStoresChecker.cpp
blob4e3919ef0166747db0bcf70c345773cbdb5853da
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.
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;
30 using namespace ento;
32 namespace {
34 /// A simple visitor to record what VarDecls occur in EH-handling code.
35 class EHCodeVisitor : public DynamicRecursiveASTVisitor {
36 public:
37 bool inEH;
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 {
56 if (inEH)
57 if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
58 S.insert(D);
59 return true;
62 EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) :
63 inEH(false), S(S) {}
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:
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())
85 return;
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()];
93 if (isReachable)
94 continue;
95 isReachable = true;
97 for (const CFGBlock *succ : block->succs())
98 if (succ)
99 worklist.push_back(succ);
103 static const Expr *
104 LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) {
105 while (Ex) {
106 Ex = Ex->IgnoreParenCasts();
107 const BinaryOperator *BO = dyn_cast<BinaryOperator>(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;
115 break;
117 return Ex;
120 namespace {
121 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
122 public:
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 {
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;
142 enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
144 public:
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) {}
153 ~DeadStoreObs() override {}
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(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();
175 if (!Loc.isValid())
176 return false;
178 FileID FID = SMgr.getFileID(Loc);
179 bool Invalid = false;
180 StringRef Data = SMgr.getBufferData(FID, &Invalid);
181 if (Invalid)
182 return false;
184 // Files autogenerated by DriverKit IIG contain some dead stores that
185 // we don't want to report.
186 if (Data.starts_with("/* iig"))
187 return true;
189 return false;
192 void Report(const VarDecl *V, DeadStoreKind dsk,
193 PathDiagnosticLocation L, SourceRange R) {
194 if (Escaped.count(V))
195 return;
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))
205 return;
207 if (isSuppressed(R))
208 return;
210 SmallString<64> buf;
211 llvm::raw_svector_ostream os(buf);
212 const char *BugType = nullptr;
214 SmallVector<FixItHint, 1> Fixits;
216 switch (dsk) {
217 case DeadInit: {
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)) {
226 break;
228 SourceManager &SM = ACtx.getSourceManager();
229 const LangOptions &LO = ACtx.getLangOpts();
230 SourceLocation L1 =
231 Lexer::findNextToken(
232 V->getTypeSourceInfo()->getTypeLoc().getEndLoc(),
233 SM, LO)->getEndLoc();
234 SourceLocation L2 =
235 Lexer::getLocForEndOfToken(V->getInit()->getEndLoc(), 1, SM, LO);
236 Fixits.push_back(FixItHint::CreateRemoval({L1, L2}));
238 break;
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;
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;
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,
266 DeadStoreKind dsk,
267 const LiveVariables::LivenessValues &Live) {
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;
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())
294 return true;
296 const Expr *RHS = B->getRHS()->IgnoreParenCasts();
297 const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
299 if (!BRHS)
300 return false;
302 const DeclRefExpr *DR;
304 if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
305 if (DR->getDecl() == VD)
306 return true;
308 if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
309 if (DR->getDecl() == VD)
310 return true;
312 return false;
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())
322 return;
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.
333 const Expr *RHS =
334 LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS());
336 QualType T = VD->getType();
337 if (T.isVolatileQualified())
338 return;
339 if (T->isPointerType() || T->isObjCObjectPointerType()) {
340 if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
341 return;
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()))
348 return;
350 // Otherwise, issue a warning.
351 DeadStoreKind dsk = Parents.isConsumedExpr(B)
352 ? Enclosing
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())
360 return;
362 const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
363 if (!parent || !isa<ReturnStmt>(parent))
364 return;
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);
377 if (!V)
378 continue;
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;
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.:
391 // int x = y = 0;
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))
397 return;
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.
407 // e.g. : int x = 0;
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.
414 if (isConstant(E))
415 return;
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
420 // variables.
422 // e.g. extern const int MyConstant;
423 // int x = MyConstant;
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>(VD) && VD->getType()->isScalarType())
434 return;
437 PathDiagnosticLocation Loc =
438 PathDiagnosticLocation::create(V, BR.getSourceManager());
439 Report(V, DeadInit, Loc, V->getInit()->getSourceRange());
446 private:
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))
460 return true;
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);
467 return false;
471 } // end anonymous namespace
473 //===----------------------------------------------------------------------===//
474 // Driver function to invoke the Dead-Stores checker on a CFG.
475 //===----------------------------------------------------------------------===//
477 namespace {
478 class FindEscaped {
479 public:
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
484 // escaped.
485 // FIXME: What about references?
486 if (auto *LE = dyn_cast<LambdaExpr>(S)) {
487 findLambdaReferenceCaptures(LE);
488 return;
491 const UnaryOperator *U = dyn_cast<UnaryOperator>(S);
492 if (!U)
493 return;
494 if (U->getOpcode() != UO_AddrOf)
495 return;
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()))
500 Escaped.insert(VD);
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())
512 continue;
514 ValueDecl *VD = C.getCapturedVar();
515 const FieldDecl *FD = CaptureFields[VD];
516 if (!FD || !isa<VarDecl>(VD))
517 continue;
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 //===----------------------------------------------------------------------===//
529 // DeadStoresChecker
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())
541 return;
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(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");
561 Chk->ShowFixIts =
562 AnOpts.getCheckerBooleanOption(Chk, "ShowFixIts");
565 bool ento::shouldRegisterDeadStoresChecker(const CheckerManager &mgr) {
566 return true;