DeadStoresChecker.cpp revision 226633
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/StaticAnalyzer/Core/Checker.h" 1717658Sjulian#include "clang/Analysis/Analyses/LiveVariables.h" 1817658Sjulian#include "clang/Analysis/Visitors/CFGRecStmtVisitor.h" 1917658Sjulian#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 2017658Sjulian#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 2117658Sjulian#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 2217658Sjulian#include "clang/Basic/Diagnostic.h" 2317658Sjulian#include "clang/AST/ASTContext.h" 2417658Sjulian#include "clang/AST/ParentMap.h" 2517658Sjulian#include "llvm/ADT/SmallPtrSet.h" 2617658Sjulian 2717658Sjulianusing namespace clang; 2817658Sjulianusing namespace ento; 2917658Sjulian 3017658Sjuliannamespace { 3117658Sjulian 3217658Sjulian// FIXME: Eventually migrate into its own file, and have it managed by 3317658Sjulian// AnalysisManager. 3417658Sjulianclass ReachableCode { 3517658Sjulian const CFG &cfg; 3617658Sjulian llvm::BitVector reachable; 37116182Sobrienpublic: 38116182Sobrien ReachableCode(const CFG &cfg) 39116182Sobrien : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {} 40174921Srwatson 41131927Smarcel void computeReachableBlocks(); 4228976Sbde 43134649Sscottl bool isReachable(const CFGBlock *block) const { 44221173Sattilio return reachable[block->getBlockID()]; 4517658Sjulian } 4617658Sjulian}; 4717658Sjulian} 4860041Sphk 4931275Sbdevoid ReachableCode::computeReachableBlocks() { 5078767Sjhb if (!cfg.getNumBlockIDs()) 5178767Sjhb return; 5278767Sjhb 53287964Strasz SmallVector<const CFGBlock*, 10> worklist; 54193066Sjamie worklist.push_back(&cfg.getEntry()); 55131927Smarcel 5617658Sjulian while (!worklist.empty()) { 57183527Speter const CFGBlock *block = worklist.back(); 5855539Sluoqi worklist.pop_back(); 59243980Salfred llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; 6089601Ssobomax if (isReachable) 6121776Sbde continue; 62164033Srwatson isReachable = true; 6378767Sjhb for (CFGBlock::const_succ_iterator i = block->succ_begin(), 6478767Sjhb e = block->succ_end(); i != e; ++i) 6578767Sjhb if (const CFGBlock *succ = *i) 66248084Sattilio worklist.push_back(succ); 67137263Speter } 68206878Sattilio} 6917658Sjulian 7017658Sjuliannamespace { 71225448Sattilioclass DeadStoreObs : public LiveVariables::Observer { 72221173Sattilio const CFG &cfg; 7317658Sjulian ASTContext &Ctx; 74174921Srwatson BugReporter& BR; 75174921Srwatson AnalysisContext* AC; 76118990Smarcel ParentMap& Parents; 77276772Smarkj llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 7894169Sphk llvm::OwningPtr<ReachableCode> reachableCode; 7991778Sjake const CFGBlock *currentBlock; 8017658Sjulian 81163606Srwatson enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 82163606Srwatson 83157628Spjdpublic: 84157628Spjd DeadStoreObs(const CFG &cfg, ASTContext &ctx, 85157628Spjd BugReporter& br, AnalysisContext* ac, ParentMap& parents, 86157628Spjd llvm::SmallPtrSet<const VarDecl*, 20> &escaped) 87157628Spjd : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents), 88157628Spjd Escaped(escaped), currentBlock(0) {} 8917658Sjulian 9017658Sjulian virtual ~DeadStoreObs() {} 9117658Sjulian 9217658Sjulian void Report(const VarDecl *V, DeadStoreKind dsk, 9317658Sjulian PathDiagnosticLocation L, SourceRange R) { 94258956Scperciva if (Escaped.count(V)) 95267992Shselasky return; 96258893Scperciva 97258893Scperciva // Compute reachable blocks within the CFG for trivial cases 9817658Sjulian // where a bogus dead store can be reported because itself is unreachable. 9917658Sjulian if (!reachableCode.get()) { 10017658Sjulian reachableCode.reset(new ReachableCode(cfg)); 10117658Sjulian reachableCode->computeReachableBlocks(); 10217658Sjulian } 10317658Sjulian 10417658Sjulian if (!reachableCode->isReachable(currentBlock)) 105131927Smarcel return; 106131927Smarcel 10742135Smsmith llvm::SmallString<64> buf; 10817658Sjulian llvm::raw_svector_ostream os(buf); 10942135Smsmith const char *BugType = 0; 11017658Sjulian 111228475Sobrien switch (dsk) { 112267992Shselasky default: 113228487Sobrien llvm_unreachable("Impossible dead store type."); 114103647Sjhb 115131927Smarcel case DeadInit: 116213322Savg BugType = "Dead initialization"; 117103647Sjhb os << "Value stored to '" << *V 118213322Savg << "' during its initialization is never read"; 11917658Sjulian break; 120228475Sobrien 121267992Shselasky case DeadIncrement: 122228487Sobrien BugType = "Dead increment"; 123131927Smarcel case Standard: 12417658Sjulian if (!BugType) BugType = "Dead assignment"; 125213322Savg os << "Value stored to '" << *V << "' is never read"; 126267992Shselasky break; 12785202Speter 12885202Speter case Enclosing: 129227309Sed // Don't report issues in this case, e.g.: "if (x = foo())", 130227309Sed // where 'x' is unused later. We have yet to see a case where 13143436Smsmith // this is a real bug. 132225448Sattilio return; 133225448Sattilio } 134225448Sattilio 135225448Sattilio BR.EmitBasicReport(BugType, "Dead store", os.str(), L, R); 136225448Sattilio } 137225448Sattilio 138225448Sattilio void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val, 139225448Sattilio DeadStoreKind dsk, 140288446Scperciva const LiveVariables::LivenessValues &Live) { 141288446Scperciva 142288446Scperciva if (!VD->hasLocalStorage()) 143288446Scperciva return; 14417658Sjulian // Reference types confuse the dead stores checker. Skip them 14517658Sjulian // for now. 14617658Sjulian if (VD->getType()->getAs<ReferenceType>()) 14717658Sjulian return; 14817658Sjulian 14917658Sjulian if (!Live.isLive(VD) && 15093496Sphk !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) { 151155383Sjeff 15293496Sphk PathDiagnosticLocation ExLoc = 15367093Sps PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); 154131927Smarcel Report(VD, dsk, ExLoc, Val->getSourceRange()); 155131927Smarcel } 156235777Sharti } 157131927Smarcel 158287964Strasz void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk, 159287964Strasz const LiveVariables::LivenessValues& Live) { 160287964Strasz if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 161287964Strasz CheckVarDecl(VD, DR, Val, dsk, Live); 162287964Strasz } 16365395Speter 16465395Speter bool isIncrement(VarDecl *VD, const BinaryOperator* B) { 16565395Speter if (B->isCompoundAssignmentOp()) 16665395Speter return true; 167287964Strasz 16817658Sjulian const Expr *RHS = B->getRHS()->IgnoreParenCasts(); 16950107Smsmith const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); 170110859Salfred 17150107Smsmith if (!BRHS) 17250107Smsmith return false; 173110859Salfred 174110859Salfred const DeclRefExpr *DR; 175214279Sbrucec 176110859Salfred if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 177110859Salfred if (DR->getDecl() == VD) 178110859Salfred return true; 179110859Salfred 180110859Salfred if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) 181110859Salfred if (DR->getDecl() == VD) 18250107Smsmith return true; 18348868Sphk 184177253Srwatson return false; 18550107Smsmith } 18617658Sjulian 187287964Strasz virtual void observeStmt(const Stmt *S, const CFGBlock *block, 188287964Strasz const LiveVariables::LivenessValues &Live) { 189287964Strasz 190287964Strasz currentBlock = block; 191287964Strasz 192287964Strasz // Skip statements in macros. 193287964Strasz if (S->getLocStart().isMacroID()) 194287964Strasz return; 195287964Strasz 196287964Strasz // Only cover dead stores from regular assignments. ++/-- dead stores 197287964Strasz // have never flagged a real bug. 198287964Strasz if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 199287964Strasz if (!B->isAssignmentOp()) return; // Skip non-assignments. 200287964Strasz 201287964Strasz if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) 202287964Strasz if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 203287964Strasz // Special case: check for assigning null to a pointer. 204287964Strasz // This is a common form of defensive programming. 205287964Strasz QualType T = VD->getType(); 206287964Strasz if (T->isPointerType() || T->isObjCObjectPointerType()) { 207167211Srwatson if (B->getRHS()->isNullPointerConstant(Ctx, 20817658Sjulian Expr::NPC_ValueDependentIsNull)) 20982749Sdillon return; 21017658Sjulian } 211225617Skmacy 21217658Sjulian Expr *RHS = B->getRHS()->IgnoreParenCasts(); 21317658Sjulian // Special case: self-assignments. These are often used to shut up 21417658Sjulian // "unused variable" compiler warnings. 215106024Srwatson if (DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS)) 216106024Srwatson if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 217172930Srwatson return; 218106024Srwatson 219106024Srwatson // Otherwise, issue a warning. 220164033Srwatson DeadStoreKind dsk = Parents.isConsumedExpr(B) 221106024Srwatson ? Enclosing 222287964Strasz : (isIncrement(VD,B) ? DeadIncrement : Standard); 223287964Strasz 224287964Strasz CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); 225287964Strasz } 226287964Strasz } 227287964Strasz else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 228287964Strasz if (!U->isIncrementOp() || U->isPrefix()) 229106024Srwatson return; 23082749Sdillon 23117658Sjulian const Stmt *parent = Parents.getParentIgnoreParenCasts(U); 23217658Sjulian if (!parent || !isa<ReturnStmt>(parent)) 23317658Sjulian return; 23417658Sjulian 23517658Sjulian const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 23617658Sjulian 23765268Smsmith if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) 23817658Sjulian CheckDeclRef(DR, U, DeadIncrement, Live); 239110859Salfred } 24017658Sjulian else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) 241264237Sed // Iterate through the decls. Warn if any initializers are complex 24273913Sjhb // expressions that are not live (never used). 243264237Sed for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); 244264237Sed DI != DE; ++DI) { 245264237Sed 246264237Sed VarDecl *V = dyn_cast<VarDecl>(*DI); 247264237Sed 248264237Sed if (!V) 24973913Sjhb continue; 25017658Sjulian 251264237Sed if (V->hasLocalStorage()) { 252264240Sed // Reference types confuse the dead stores checker. Skip them 25317658Sjulian // for now. 25417658Sjulian if (V->getType()->getAs<ReferenceType>()) 25517658Sjulian return; 25654233Sphk 25765395Speter if (Expr *E = V->getInit()) { 25854233Sphk while (ExprWithCleanups *exprClean = dyn_cast<ExprWithCleanups>(E)) 25954233Sphk E = exprClean->getSubExpr(); 26054233Sphk 26154233Sphk // Don't warn on C++ objects (yet) until we can show that their 26254233Sphk // constructors/destructors don't have side effects. 26354233Sphk if (isa<CXXConstructExpr>(E)) 26454233Sphk return; 26554233Sphk 26665764Sjhb // A dead initialization is a variable that is dead after it 26754233Sphk // is initialized. We don't flag warnings for those variables 26854233Sphk // marked 'unused'. 26954233Sphk if (!Live.isLive(V) && V->getAttr<UnusedAttr>() == 0) { 27054233Sphk // Special case: check for initializations with constants. 27165764Sjhb // 27254233Sphk // e.g. : int x = 0; 27354233Sphk // 27454233Sphk // If x is EVER assigned a new value later, don't issue 27554233Sphk // a warning. This is because such initialization can be 27665764Sjhb // due to defensive programming. 27754233Sphk if (E->isConstantInitializer(Ctx, false)) 27854233Sphk return; 27954233Sphk 28065764Sjhb if (DeclRefExpr *DRE=dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) 28154233Sphk if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { 28254233Sphk // Special case: check for initialization from constant 283222801Smarcel // variables. 284222801Smarcel // 28594169Sphk // e.g. extern const int MyConstant; 286222801Smarcel // int x = MyConstant; 287269105Sgavin // 288110859Salfred if (VD->hasGlobalStorage() && 289269105Sgavin VD->getType().isConstQualified()) 290222801Smarcel return; 291222801Smarcel // Special case: check for initialization from scalar 292222801Smarcel // parameters. This is often a form of defensive 293222801Smarcel // programming. Non-scalars are still an error since 294132412Sjulian // because it more likely represents an actual algorithmic 29594169Sphk // bug. 296131927Smarcel if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) 29794169Sphk return; 298222801Smarcel } 299222801Smarcel 300174921Srwatson PathDiagnosticLocation Loc = 301222801Smarcel PathDiagnosticLocation::create(V, BR.getSourceManager()); 302222801Smarcel Report(V, DeadInit, Loc, E->getSourceRange()); 303174921Srwatson } 304222801Smarcel } 305174921Srwatson } 306222801Smarcel } 307269105Sgavin } 308222801Smarcel}; 309176788Sru 310269105Sgavin} // end anonymous namespace 31194169Sphk 31294169Sphk//===----------------------------------------------------------------------===// 31317658Sjulian// Driver function to invoke the Dead-Stores checker on a CFG. 314137329Snjl//===----------------------------------------------------------------------===// 31517658Sjulian 316214004Smarcelnamespace { 317214004Smarcelclass FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{ 31817658Sjulian CFG *cfg; 319285993Sjeffpublic: 32017658Sjulian FindEscaped(CFG *c) : cfg(c) {} 321137375Smarcel 322137329Snjl CFG& getCFG() { return *cfg; } 323137329Snjl 324137329Snjl llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 325137329Snjl 326137329Snjl void VisitUnaryOperator(UnaryOperator* U) { 327228424Savg // Check for '&'. Any VarDecl whose value has its address-taken we 328228424Savg // treat as escaped. 329228424Savg Expr *E = U->getSubExpr()->IgnoreParenCasts(); 330228424Savg if (U->getOpcode() == UO_AddrOf) 331228424Savg if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 332228424Savg if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 333137263Speter Escaped.insert(VD); 334155383Sjeff return; 335155383Sjeff } 336137263Speter Visit(E); 33782119Sjhb } 338131927Smarcel}; 33982119Sjhb} // end anonymous namespace 34027997Sjulian 34127997Sjulian 34227997Sjulian//===----------------------------------------------------------------------===// 34350107Smsmith// DeadStoresChecker 34427997Sjulian//===----------------------------------------------------------------------===// 34527997Sjulian 34627997Sjuliannamespace { 34727997Sjulianclass DeadStoresChecker : public Checker<check::ASTCodeBody> { 348285993Sjeffpublic: 349285993Sjeff void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, 350285993Sjeff BugReporter &BR) const { 35117658Sjulian if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) { 35227997Sjulian CFG &cfg = *mgr.getCFG(D); 35354233Sphk AnalysisContext *AC = mgr.getAnalysisContext(D); 35454233Sphk ParentMap &pmap = mgr.getParentMap(D); 355228632Savg FindEscaped FS(&cfg); 356228632Savg FS.getCFG().VisitBlockStmts(FS); 35727997Sjulian DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped); 35827997Sjulian L->runOnAllBlocks(A); 35927997Sjulian } 36027997Sjulian } 36150107Smsmith}; 362137329Snjl} 363132412Sjulian 364222801Smarcelvoid ento::registerDeadStoresChecker(CheckerManager &mgr) { 36539237Sgibbs mgr.registerChecker<DeadStoresChecker>(); 36639237Sgibbs} 36750107Smsmith