DeadStoresChecker.cpp revision 251662
117658Sjulian//==- DeadStoresChecker.cpp - Check for stores to dead variables -*- C++ -*-==// 217658Sjulian// 317658Sjulian// The LLVM Compiler Infrastructure 417658Sjulian// 517658Sjulian// This file is distributed under the University of Illinois Open Source 617658Sjulian// License. See LICENSE.TXT for details. 717658Sjulian// 817658Sjulian//===----------------------------------------------------------------------===// 917658Sjulian// 1017658Sjulian// This file defines a DeadStores, a flow-sensitive checker that looks for 1117658Sjulian// stores to variables that are no longer live. 1217658Sjulian// 1317658Sjulian//===----------------------------------------------------------------------===// 1417658Sjulian 1517658Sjulian#include "ClangSACheckers.h" 1617658Sjulian#include "clang/AST/ASTContext.h" 1717658Sjulian#include "clang/AST/Attr.h" 1817658Sjulian#include "clang/AST/ParentMap.h" 1917658Sjulian#include "clang/AST/RecursiveASTVisitor.h" 2017658Sjulian#include "clang/Analysis/Analyses/LiveVariables.h" 2117658Sjulian#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 2217658Sjulian#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 2317658Sjulian#include "clang/StaticAnalyzer/Core/Checker.h" 2417658Sjulian#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 2517658Sjulian#include "llvm/ADT/BitVector.h" 2617658Sjulian#include "llvm/ADT/SmallString.h" 2717658Sjulian#include "llvm/Support/SaveAndRestore.h" 2817658Sjulian 2917658Sjulianusing namespace clang; 3017658Sjulianusing namespace ento; 3117658Sjulian 3217658Sjuliannamespace { 3317658Sjulian 3417658Sjulian/// A simple visitor to record what VarDecls occur in EH-handling code. 3517658Sjulianclass EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> { 3617658Sjulianpublic: 37116182Sobrien bool inEH; 38116182Sobrien llvm::DenseSet<const VarDecl *> &S; 39116182Sobrien 40174921Srwatson bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) { 41131927Smarcel SaveAndRestore<bool> inFinally(inEH, true); 4228976Sbde return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S); 43134649Sscottl } 44221173Sattilio 4517658Sjulian bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) { 4617658Sjulian SaveAndRestore<bool> inCatch(inEH, true); 4717658Sjulian return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S); 4860041Sphk } 4931275Sbde 5078767Sjhb bool TraverseCXXCatchStmt(CXXCatchStmt *S) { 5178767Sjhb SaveAndRestore<bool> inCatch(inEH, true); 5278767Sjhb return TraverseStmt(S->getHandlerBlock()); 53193066Sjamie } 54131927Smarcel 5517658Sjulian bool VisitDeclRefExpr(DeclRefExpr *DR) { 56183527Speter if (inEH) 5755539Sluoqi if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 58243980Salfred S.insert(D); 5989601Ssobomax return true; 6021776Sbde } 61164033Srwatson 6278767Sjhb EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) : 6378767Sjhb inEH(false), S(S) {} 6478767Sjhb}; 65248084Sattilio 66137263Speter// FIXME: Eventually migrate into its own file, and have it managed by 67206878Sattilio// AnalysisManager. 6817658Sjulianclass ReachableCode { 6917658Sjulian const CFG &cfg; 70225448Sattilio llvm::BitVector reachable; 71221173Sattiliopublic: 7217658Sjulian ReachableCode(const CFG &cfg) 73174921Srwatson : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {} 74174921Srwatson 75118990Smarcel void computeReachableBlocks(); 76276772Smarkj 7794169Sphk bool isReachable(const CFGBlock *block) const { 7891778Sjake return reachable[block->getBlockID()]; 7917658Sjulian } 80163606Srwatson}; 81163606Srwatson} 82157628Spjd 83157628Spjdvoid ReachableCode::computeReachableBlocks() { 84157628Spjd if (!cfg.getNumBlockIDs()) 85157628Spjd return; 86157628Spjd 87157628Spjd SmallVector<const CFGBlock*, 10> worklist; 8817658Sjulian worklist.push_back(&cfg.getEntry()); 8917658Sjulian 9017658Sjulian while (!worklist.empty()) { 9117658Sjulian const CFGBlock *block = worklist.back(); 9217658Sjulian worklist.pop_back(); 93258956Scperciva llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; 94267992Shselasky if (isReachable) 95258893Scperciva continue; 96258893Scperciva isReachable = true; 9717658Sjulian for (CFGBlock::const_succ_iterator i = block->succ_begin(), 9817658Sjulian e = block->succ_end(); i != e; ++i) 9917658Sjulian if (const CFGBlock *succ = *i) 10017658Sjulian worklist.push_back(succ); 10117658Sjulian } 10217658Sjulian} 10317658Sjulian 104131927Smarcelstatic const Expr * 105131927SmarcelLookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) { 10642135Smsmith while (Ex) { 10717658Sjulian const BinaryOperator *BO = 10842135Smsmith dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts()); 10917658Sjulian if (!BO) 110228475Sobrien break; 111267992Shselasky if (BO->getOpcode() == BO_Assign) { 112228487Sobrien Ex = BO->getRHS(); 113103647Sjhb continue; 114131927Smarcel } 115213322Savg if (BO->getOpcode() == BO_Comma) { 116103647Sjhb Ex = BO->getRHS(); 117213322Savg continue; 11817658Sjulian } 119228475Sobrien break; 120267992Shselasky } 121228487Sobrien return Ex; 122131927Smarcel} 12317658Sjulian 124213322Savgnamespace { 125267992Shselaskyclass DeadStoreObs : public LiveVariables::Observer { 12685202Speter const CFG &cfg; 12785202Speter ASTContext &Ctx; 128227309Sed BugReporter& BR; 129227309Sed AnalysisDeclContext* AC; 13043436Smsmith ParentMap& Parents; 131225448Sattilio llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 132225448Sattilio OwningPtr<ReachableCode> reachableCode; 133225448Sattilio const CFGBlock *currentBlock; 134225448Sattilio OwningPtr<llvm::DenseSet<const VarDecl *> > InEH; 135225448Sattilio 136225448Sattilio enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 137225448Sattilio 138225448Sattiliopublic: 13917658Sjulian DeadStoreObs(const CFG &cfg, ASTContext &ctx, 14017658Sjulian BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents, 14117658Sjulian llvm::SmallPtrSet<const VarDecl*, 20> &escaped) 14217658Sjulian : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents), 14317658Sjulian Escaped(escaped), currentBlock(0) {} 14417658Sjulian 14593496Sphk virtual ~DeadStoreObs() {} 146155383Sjeff 14793496Sphk bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) { 14867093Sps if (Live.isLive(D)) 149131927Smarcel return true; 150131927Smarcel // Lazily construct the set that records which VarDecls are in 151235777Sharti // EH code. 152131927Smarcel if (!InEH.get()) { 15365395Speter InEH.reset(new llvm::DenseSet<const VarDecl *>()); 15465395Speter EHCodeVisitor V(*InEH.get()); 15565395Speter V.TraverseStmt(AC->getBody()); 15665395Speter } 15717658Sjulian // Treat all VarDecls that occur in EH code as being "always live" 15850107Smsmith // when considering to suppress dead stores. Frequently stores 159110859Salfred // are followed by reads in EH code, but we don't have the ability 16050107Smsmith // to analyze that yet. 16150107Smsmith return InEH->count(D); 162110859Salfred } 163110859Salfred 164214279Sbrucec void Report(const VarDecl *V, DeadStoreKind dsk, 165110859Salfred PathDiagnosticLocation L, SourceRange R) { 166110859Salfred if (Escaped.count(V)) 167110859Salfred return; 168110859Salfred 169110859Salfred // Compute reachable blocks within the CFG for trivial cases 170110859Salfred // where a bogus dead store can be reported because itself is unreachable. 17150107Smsmith if (!reachableCode.get()) { 17248868Sphk reachableCode.reset(new ReachableCode(cfg)); 173177253Srwatson reachableCode->computeReachableBlocks(); 17450107Smsmith } 17517658Sjulian 176167211Srwatson if (!reachableCode->isReachable(currentBlock)) 17717658Sjulian return; 17882749Sdillon 17917658Sjulian SmallString<64> buf; 180225617Skmacy llvm::raw_svector_ostream os(buf); 18117658Sjulian const char *BugType = 0; 18217658Sjulian 18317658Sjulian switch (dsk) { 184106024Srwatson case DeadInit: 185106024Srwatson BugType = "Dead initialization"; 186172930Srwatson os << "Value stored to '" << *V 187106024Srwatson << "' during its initialization is never read"; 188106024Srwatson break; 189164033Srwatson 190106024Srwatson case DeadIncrement: 191106024Srwatson BugType = "Dead increment"; 192214004Smarcel case Standard: 193106024Srwatson if (!BugType) BugType = "Dead assignment"; 194106024Srwatson os << "Value stored to '" << *V << "' is never read"; 19582749Sdillon break; 19617658Sjulian 19717658Sjulian case Enclosing: 19817658Sjulian // Don't report issues in this case, e.g.: "if (x = foo())", 19917658Sjulian // where 'x' is unused later. We have yet to see a case where 20017658Sjulian // this is a real bug. 20117658Sjulian return; 20265268Smsmith } 20317658Sjulian 204110859Salfred BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R); 20517658Sjulian } 206264237Sed 20773913Sjhb void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val, 208264237Sed DeadStoreKind dsk, 209264237Sed const LiveVariables::LivenessValues &Live) { 210264237Sed 211264237Sed if (!VD->hasLocalStorage()) 212264237Sed return; 213264237Sed // Reference types confuse the dead stores checker. Skip them 21473913Sjhb // for now. 21517658Sjulian if (VD->getType()->getAs<ReferenceType>()) 216264237Sed return; 217264240Sed 21817658Sjulian if (!isLive(Live, VD) && 21917658Sjulian !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) { 22017658Sjulian 22154233Sphk PathDiagnosticLocation ExLoc = 22265395Speter PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); 22354233Sphk Report(VD, dsk, ExLoc, Val->getSourceRange()); 22454233Sphk } 22554233Sphk } 22654233Sphk 22754233Sphk void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk, 22854233Sphk const LiveVariables::LivenessValues& Live) { 22954233Sphk if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 23054233Sphk CheckVarDecl(VD, DR, Val, dsk, Live); 23165764Sjhb } 23254233Sphk 23354233Sphk bool isIncrement(VarDecl *VD, const BinaryOperator* B) { 23454233Sphk if (B->isCompoundAssignmentOp()) 23554233Sphk return true; 23665764Sjhb 23754233Sphk const Expr *RHS = B->getRHS()->IgnoreParenCasts(); 23854233Sphk const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); 23954233Sphk 24054233Sphk if (!BRHS) 24165764Sjhb return false; 24254233Sphk 24354233Sphk const DeclRefExpr *DR; 24454233Sphk 24565764Sjhb if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 24654233Sphk if (DR->getDecl() == VD) 24754233Sphk return true; 248222801Smarcel 249222801Smarcel if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) 25094169Sphk if (DR->getDecl() == VD) 251222801Smarcel return true; 252269105Sgavin 253110859Salfred return false; 254269105Sgavin } 255222801Smarcel 256222801Smarcel virtual void observeStmt(const Stmt *S, const CFGBlock *block, 257222801Smarcel const LiveVariables::LivenessValues &Live) { 258222801Smarcel 259132412Sjulian currentBlock = block; 26094169Sphk 261131927Smarcel // Skip statements in macros. 26294169Sphk if (S->getLocStart().isMacroID()) 263222801Smarcel return; 264222801Smarcel 265174921Srwatson // Only cover dead stores from regular assignments. ++/-- dead stores 266222801Smarcel // have never flagged a real bug. 267222801Smarcel if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 268174921Srwatson if (!B->isAssignmentOp()) return; // Skip non-assignments. 269222801Smarcel 270174921Srwatson if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) 271222801Smarcel if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 272269105Sgavin // Special case: check for assigning null to a pointer. 273222801Smarcel // This is a common form of defensive programming. 274176788Sru const Expr *RHS = 275269105Sgavin LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS()); 27694169Sphk RHS = RHS->IgnoreParenCasts(); 27794169Sphk 278149875Struckman QualType T = VD->getType(); 279149875Struckman if (T->isPointerType() || T->isObjCObjectPointerType()) { 280149875Struckman if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull)) 281149875Struckman return; 282175486Sattilio } 283149875Struckman 284149875Struckman // Special case: self-assignments. These are often used to shut up 285149875Struckman // "unused variable" compiler warnings. 286149875Struckman if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS)) 287149875Struckman if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 28817658Sjulian return; 289137329Snjl 29017658Sjulian // Otherwise, issue a warning. 291214004Smarcel DeadStoreKind dsk = Parents.isConsumedExpr(B) 292214004Smarcel ? Enclosing 29317658Sjulian : (isIncrement(VD,B) ? DeadIncrement : Standard); 294133763Struckman 295264237Sed CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); 29617658Sjulian } 297137375Smarcel } 298137329Snjl else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 299137329Snjl if (!U->isIncrementOp() || U->isPrefix()) 300137329Snjl return; 301137329Snjl 302137329Snjl const Stmt *parent = Parents.getParentIgnoreParenCasts(U); 303228424Savg if (!parent || !isa<ReturnStmt>(parent)) 304228424Savg return; 305228424Savg 306228424Savg const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 307228424Savg 308228424Savg if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) 309137263Speter CheckDeclRef(DR, U, DeadIncrement, Live); 310155383Sjeff } 311155383Sjeff else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) 312137263Speter // Iterate through the decls. Warn if any initializers are complex 31382119Sjhb // expressions that are not live (never used). 314131927Smarcel for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); 31582119Sjhb DI != DE; ++DI) { 31627997Sjulian 31727997Sjulian VarDecl *V = dyn_cast<VarDecl>(*DI); 31827997Sjulian 31950107Smsmith if (!V) 32027997Sjulian continue; 32127997Sjulian 32227997Sjulian if (V->hasLocalStorage()) { 32327997Sjulian // Reference types confuse the dead stores checker. Skip them 32417658Sjulian // for now. 32517658Sjulian if (V->getType()->getAs<ReferenceType>()) 32665707Sjasone return; 327131481Sjhb 32865707Sjasone if (const Expr *E = V->getInit()) { 329131481Sjhb while (const ExprWithCleanups *exprClean = 33017658Sjulian dyn_cast<ExprWithCleanups>(E)) 33117658Sjulian E = exprClean->getSubExpr(); 33217658Sjulian 333221173Sattilio // Look through transitive assignments, e.g.: 334225617Skmacy // int x = y = 0; 33517658Sjulian E = LookThroughTransitiveAssignmentsAndCommaOperators(E); 33634266Sjulian 33734266Sjulian // Don't warn on C++ objects (yet) until we can show that their 33834266Sjulian // constructors/destructors don't have side effects. 33934266Sjulian if (isa<CXXConstructExpr>(E)) 34034266Sjulian return; 34165707Sjasone 34217658Sjulian // A dead initialization is a variable that is dead after it 343149875Struckman // is initialized. We don't flag warnings for those variables 344149875Struckman // marked 'unused'. 34517658Sjulian if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) { 346133763Struckman // Special case: check for initializations with constants. 347133763Struckman // 348136115Sphk // e.g. : int x = 0; 34917658Sjulian // 350133763Struckman // If x is EVER assigned a new value later, don't issue 351133763Struckman // a warning. This is because such initialization can be 352133763Struckman // due to defensive programming. 353133763Struckman if (E->isEvaluatable(Ctx)) 354133763Struckman return; 35517658Sjulian 35665707Sjasone if (const DeclRefExpr *DRE = 35765707Sjasone dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) 35865707Sjasone if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { 359236503Savg // Special case: check for initialization from constant 360221173Sattilio // variables. 361225617Skmacy // 362131481Sjhb // e.g. extern const int MyConstant; 363131481Sjhb // int x = MyConstant; 364131481Sjhb // 365131481Sjhb if (VD->hasGlobalStorage() && 366131481Sjhb VD->getType().isConstQualified()) 367131481Sjhb return; 368131481Sjhb // Special case: check for initialization from scalar 36934266Sjulian // parameters. This is often a form of defensive 370131481Sjhb // programming. Non-scalars are still an error since 371131481Sjhb // because it more likely represents an actual algorithmic 372131481Sjhb // bug. 373131481Sjhb if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) 374131481Sjhb return; 375131481Sjhb } 376131481Sjhb 377131481Sjhb PathDiagnosticLocation Loc = 378170307Sjeff PathDiagnosticLocation::create(V, BR.getSourceManager()); 379131481Sjhb Report(V, DeadInit, Loc, E->getSourceRange()); 380170307Sjeff } 381131481Sjhb } 382131481Sjhb } 383131481Sjhb } 384131481Sjhb } 38517658Sjulian}; 386133418Snjl 38741137Smsmith} // end anonymous namespace 38841137Smsmith 38941137Smsmith//===----------------------------------------------------------------------===// 39041137Smsmith// Driver function to invoke the Dead-Stores checker on a CFG. 39141137Smsmith//===----------------------------------------------------------------------===// 39241137Smsmith 393149875Struckmannamespace { 394137186Sphkclass FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{ 395137186Sphk CFG *cfg; 396130640Sphkpublic: 39753452Sphk FindEscaped(CFG *c) : cfg(c) {} 39848225Smckusick 39953023Sphk CFG& getCFG() { return *cfg; } 40053023Sphk 401137186Sphk llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 40253023Sphk 403225448Sattilio void VisitUnaryOperator(UnaryOperator* U) { 404225448Sattilio // Check for '&'. Any VarDecl whose value has its address-taken we 405225448Sattilio // treat as escaped. 406225448Sattilio Expr *E = U->getSubExpr()->IgnoreParenCasts(); 407225448Sattilio if (U->getOpcode() == UO_AddrOf) 408225448Sattilio if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 409225448Sattilio if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 410225448Sattilio Escaped.insert(VD); 411225448Sattilio return; 412225448Sattilio } 413225448Sattilio Visit(E); 41446568Speter } 41541137Smsmith}; 41617658Sjulian} // end anonymous namespace 41717658Sjulian 41817658Sjulian 41917658Sjulian//===----------------------------------------------------------------------===// 42017658Sjulian// DeadStoresChecker 421133763Struckman//===----------------------------------------------------------------------===// 42217658Sjulian 42317658Sjuliannamespace { 424133763Struckmanclass DeadStoresChecker : public Checker<check::ASTCodeBody> { 425133763Struckmanpublic: 42617658Sjulian void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, 42717658Sjulian BugReporter &BR) const { 42817658Sjulian 42917658Sjulian // Don't do anything for template instantiations. 43017658Sjulian // Proving that code in a template instantiation is "dead" 43117658Sjulian // means proving that it is dead in all instantiations. 432157628Spjd // This same problem exists with -Wunreachable-code. 43339237Sgibbs if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) 43417658Sjulian if (FD->isTemplateInstantiation()) 43527997Sjulian return; 43654233Sphk 43754233Sphk if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) { 438228632Savg CFG &cfg = *mgr.getCFG(D); 439228632Savg AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D); 44027997Sjulian ParentMap &pmap = mgr.getParentMap(D); 44127997Sjulian FindEscaped FS(&cfg); 44227997Sjulian FS.getCFG().VisitBlockStmts(FS); 44327997Sjulian DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped); 44450107Smsmith L->runOnAllBlocks(A); 445137329Snjl } 446132412Sjulian } 447222801Smarcel}; 44839237Sgibbs} 44939237Sgibbs 45050107Smsmithvoid ento::registerDeadStoresChecker(CheckerManager &mgr) { 45139237Sgibbs mgr.registerChecker<DeadStoresChecker>(); 45250107Smsmith} 45350107Smsmith