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 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->getHandlerBlock()); 53 } 54 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 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: 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 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 97 for (const CFGBlock *succ : block->succs()) 98 if (succ) 99 worklist.push_back(succ); 100 } 101 } 102 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; 114 } 115 break; 116 } 117 return Ex; 118 } 119 120 namespace { 121 class DeadStoresChecker : public Checker<check::ASTCodeBody> { 122 public: 123 bool ShowFixIts = false; 124 bool WarnForDeadNestedAssignments = true; 125 126 void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr, 127 BugReporter &BR) const; 128 }; 129 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; 141 142 enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 143 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) {} 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(new llvm::DenseSet<const VarDecl *>()); 162 EHCodeVisitor V(*InEH.get()); 163 V.TraverseStmt(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(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(Loc); 179 bool Invalid = false; 180 StringRef Data = SMgr.getBufferData(FID, &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("/* 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(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(new ReachableCode(cfg)); 201 reachableCode->computeReachableBlocks(); 202 } 203 204 if (!reachableCode->isReachable(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(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 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})); 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(AC->getDecl(), Checker, BugType, categories::UnusedCode, 262 os.str(), L, 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, VD) && 277 !(VD->hasAttr<UnusedAttr>() || VD->hasAttr<BlocksAttr>() || 278 VD->hasAttr<ObjCPreciseLifetimeAttr>())) { 279 280 PathDiagnosticLocation ExLoc = 281 PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); 282 Report(VD, dsk, ExLoc, 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>(DR->getDecl())) 289 CheckVarDecl(VD, 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>(RHS); 298 299 if (!BRHS) 300 return false; 301 302 const DeclRefExpr *DR; 303 304 if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 305 if (DR->getDecl() == VD) 306 return true; 307 308 if ((DR = dyn_cast<DeclRefExpr>(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>(S)) { 327 if (!B->isAssignmentOp()) return; // Skip non-assignments. 328 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()); 335 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; 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>(RHS)) 347 if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 348 return; 349 350 // Otherwise, issue a warning. 351 DeadStoreKind dsk = Parents.isConsumedExpr(B) 352 ? Enclosing 353 : (isIncrement(VD,B) ? DeadIncrement : Standard); 354 355 CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); 356 } 357 } 358 else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 359 if (!U->isIncrementOp() || U->isPrefix()) 360 return; 361 362 const Stmt *parent = Parents.getParentIgnoreParenCasts(U); 363 if (!parent || !isa<ReturnStmt>(parent)) 364 return; 365 366 const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 367 368 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) 369 CheckDeclRef(DR, U, DeadIncrement, Live); 370 } 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); 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>(E)) 388 E = FE->getSubExpr(); 389 390 // Look through transitive assignments, e.g.: 391 // int x = y = 0; 392 E = LookThroughTransitiveAssignmentsAndCommaOperators(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>(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, 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>(E)) 418 if (const VarDecl *VD = dyn_cast<VarDecl>(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>(VD) && VD->getType()->isScalarType()) 434 return; 435 } 436 437 PathDiagnosticLocation Loc = 438 PathDiagnosticLocation::create(V, BR.getSourceManager()); 439 Report(V, DeadInit, Loc, V->getInit()->getSourceRange()); 440 } 441 } 442 } 443 } 444 } 445 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()); 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>(E)) { 464 return isConstant(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 477 namespace { 478 class FindEscaped { 479 public: 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>(S)) { 487 findLambdaReferenceCaptures(LE); 488 return; 489 } 490 491 const UnaryOperator *U = dyn_cast<UnaryOperator>(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>(E)) 499 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 500 Escaped.insert(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(CaptureFields, 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>(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(cast<VarDecl>(VD)); 522 } 523 } 524 }; 525 } // end anonymous namespace 526 527 528 //===----------------------------------------------------------------------===// 529 // DeadStoresChecker 530 //===----------------------------------------------------------------------===// 531 532 void 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>(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(FS); 549 DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped, 550 WarnForDeadNestedAssignments); 551 L->runOnAllBlocks(A); 552 } 553 } 554 555 void ento::registerDeadStoresChecker(CheckerManager &Mgr) { 556 auto *Chk = Mgr.registerChecker<DeadStoresChecker>(); 557 558 const AnalyzerOptions &AnOpts = Mgr.getAnalyzerOptions(); 559 Chk->WarnForDeadNestedAssignments = 560 AnOpts.getCheckerBooleanOption(Chk, "WarnForDeadNestedAssignments"); 561 Chk->ShowFixIts = 562 AnOpts.getCheckerBooleanOption(Chk, "ShowFixIts"); 563 } 564 565 bool ento::shouldRegisterDeadStoresChecker(const CheckerManager &mgr) { 566 return true; 567 } 568