567 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines a DeadStores, a flow-sensitive checker that looks for10// 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->getHandlerBlock());52 }53 54 bool VisitDeclRefExpr(DeclRefExpr *DR) override {55 if (inEH)56 if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))57 S.insert(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 by66// 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(&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(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>(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 in158 // EH code.159 if (!InEH) {160 InEH.reset(new llvm::DenseSet<const VarDecl *>());161 EHCodeVisitor V(*InEH);162 V.TraverseStmt(AC->getBody());163 }164 // Treat all VarDecls that occur in EH code as being "always live"165 // when considering to suppress dead stores. Frequently stores166 // are followed by reads in EH code, but we don't have the ability167 // to analyze that yet.168 return InEH->count(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(Loc);178 bool Invalid = false;179 StringRef Data = SMgr.getBufferData(FID, &Invalid);180 if (Invalid)181 return false;182 183 // Files autogenerated by DriverKit IIG contain some dead stores that184 // we don't want to report.185 if (Data.starts_with("/* 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(V))194 return;195 196 // Compute reachable blocks within the CFG for trivial cases197 // where a bogus dead store can be reported because itself is unreachable.198 if (!reachableCode) {199 reachableCode.reset(new ReachableCode(cfg));200 reachableCode->computeReachableBlocks();201 }202 203 if (!reachableCode->isReachable(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 '" << *V219 << "' during its initialization is never read";220 221 ASTContext &ACtx = V->getASTContext();222 if (Checker->ShowFixIts) {223 if (V->getInit()->HasSideEffects(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 V->getTypeSourceInfo()->getTypeLoc().getEndLoc(),232 SM, LO)->getEndLoc();233 SourceLocation L2 =234 Lexer::getLocForEndOfToken(V->getInit()->getEndLoc(), 1, SM, LO);235 Fixits.push_back(FixItHint::CreateRemoval({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 '" << *V254 << "' is used in the enclosing expression, the value is never "255 "actually read from '"256 << *V << "'";257 break;258 }259 260 BR.EmitBasicReport(AC->getDecl(), Checker, BugType, categories::UnusedCode,261 os.str(), L, 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 them271 // for now.272 if (VD->getType()->getAs<ReferenceType>())273 return;274 275 if (!isLive(Live, VD) &&276 !(VD->hasAttr<UnusedAttr>() || VD->hasAttr<BlocksAttr>() ||277 VD->hasAttr<ObjCPreciseLifetimeAttr>())) {278 279 PathDiagnosticLocation ExLoc =280 PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC);281 Report(VD, dsk, ExLoc, 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>(DR->getDecl()))288 CheckVarDecl(VD, 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>(RHS);297 298 if (!BRHS)299 return false;300 301 const DeclRefExpr *DR;302 303 if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))304 if (DR->getDecl() == VD)305 return true;306 307 if ((DR = dyn_cast<DeclRefExpr>(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 stores324 // have never flagged a real bug.325 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {326 if (!B->isAssignmentOp()) return; // Skip non-assignments.327 328 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))329 if (VarDecl *VD = dyn_cast<VarDecl>(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(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, Expr::NPC_ValueDependentIsNull))340 return;341 }342 343 // Special case: self-assignments. These are often used to shut up344 // "unused variable" compiler warnings.345 if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))346 if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))347 return;348 349 // Otherwise, issue a warning.350 DeadStoreKind dsk = Parents.isConsumedExpr(B)351 ? Enclosing352 : (isIncrement(VD,B) ? DeadIncrement : Standard);353 354 CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);355 }356 }357 else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {358 if (!U->isIncrementOp() || U->isPrefix())359 return;360 361 const Stmt *parent = Parents.getParentIgnoreParenCasts(U);362 if (!parent || !isa<ReturnStmt>(parent))363 return;364 365 const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();366 367 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))368 CheckDeclRef(DR, U, DeadIncrement, Live);369 }370 else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))371 // Iterate through the decls. Warn if any initializers are complex372 // expressions that are not live (never used).373 for (const auto *DI : DS->decls()) {374 const auto *V = dyn_cast<VarDecl>(DI);375 376 if (!V)377 continue;378 379 if (V->hasLocalStorage()) {380 // Reference types confuse the dead stores checker. Skip them381 // 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>(E))387 E = FE->getSubExpr();388 389 // Look through transitive assignments, e.g.:390 // int x = y = 0;391 E = LookThroughTransitiveAssignmentsAndCommaOperators(E);392 393 // Don't warn on C++ objects (yet) until we can show that their394 // constructors/destructors don't have side effects.395 if (isa<CXXConstructExpr>(E))396 return;397 398 // A dead initialization is a variable that is dead after it399 // is initialized. We don't flag warnings for those variables400 // marked 'unused' or 'objc_precise_lifetime'.401 if (!isLive(Live, 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 issue411 // a warning. This is because such initialization can be412 // due to defensive programming.413 if (isConstant(E))414 return;415 416 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))417 if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {418 // Special case: check for initialization from constant419 // 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 scalar428 // parameters. This is often a form of defensive429 // programming. Non-scalars are still an error since430 // because it more likely represents an actual algorithmic431 // bug.432 if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())433 return;434 }435 436 PathDiagnosticLocation Loc =437 PathDiagnosticLocation::create(V, BR.getSourceManager());438 Report(V, DeadInit, Loc, V->getInit()->getSourceRange());439 }440 }441 }442 }443 }444 445private:446 /// Return true if the given init list can be interpreted as constant447 bool isConstant(const InitListExpr *Candidate) const {448 // We consider init list to be constant if each member of the list can be449 // interpreted as constant.450 return llvm::all_of(Candidate->inits(), [this](const Expr *Init) {451 return isConstant(Init->IgnoreParenCasts());452 });453 }454 455 /// Return true if the given expression can be interpreted as constant456 bool isConstant(const Expr *E) const {457 // It looks like E itself is a constant458 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>(E)) {463 return isConstant(ILE);464 }465 466 return false;467 }468};469 470} // end anonymous namespace471 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 as483 // escaped.484 // FIXME: What about references?485 if (auto *LE = dyn_cast<LambdaExpr>(S)) {486 findLambdaReferenceCaptures(LE);487 return;488 }489 490 const UnaryOperator *U = dyn_cast<UnaryOperator>(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>(E))498 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))499 Escaped.insert(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(CaptureFields, 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>(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(cast<VarDecl>(VD));521 }522 }523};524} // end anonymous namespace525 526 527//===----------------------------------------------------------------------===//528// DeadStoresChecker529//===----------------------------------------------------------------------===//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>(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(FS);548 DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped,549 WarnForDeadNestedAssignments);550 L->runOnAllBlocks(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(Chk, "WarnForDeadNestedAssignments");560 Chk->ShowFixIts =561 AnOpts.getCheckerBooleanOption(Chk, "ShowFixIts");562}563 564bool ento::shouldRegisterDeadStoresChecker(const CheckerManager &mgr) {565 return true;566}567