DeadStoresChecker.cpp revision 218887
1218887Sdim//==- DeadStoresChecker.cpp - Check for stores to dead variables -*- C++ -*-==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines a DeadStores, a flow-sensitive checker that looks for 11218887Sdim// stores to variables that are no longer live. 12218887Sdim// 13218887Sdim//===----------------------------------------------------------------------===// 14218887Sdim 15218887Sdim#include "ClangSACheckers.h" 16218887Sdim#include "clang/StaticAnalyzer/Core/CheckerV2.h" 17218887Sdim#include "clang/StaticAnalyzer/Checkers/LocalCheckers.h" 18218887Sdim#include "clang/Analysis/Analyses/LiveVariables.h" 19218887Sdim#include "clang/Analysis/Visitors/CFGRecStmtVisitor.h" 20218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 21218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 22218887Sdim#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 23218887Sdim#include "clang/Basic/Diagnostic.h" 24218887Sdim#include "clang/AST/ASTContext.h" 25218887Sdim#include "clang/AST/ParentMap.h" 26218887Sdim#include "llvm/ADT/SmallPtrSet.h" 27218887Sdim 28218887Sdimusing namespace clang; 29218887Sdimusing namespace ento; 30218887Sdim 31218887Sdimnamespace { 32218887Sdim 33218887Sdim// FIXME: Eventually migrate into its own file, and have it managed by 34218887Sdim// AnalysisManager. 35218887Sdimclass ReachableCode { 36218887Sdim const CFG &cfg; 37218887Sdim llvm::BitVector reachable; 38218887Sdimpublic: 39218887Sdim ReachableCode(const CFG &cfg) 40218887Sdim : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {} 41218887Sdim 42218887Sdim void computeReachableBlocks(); 43218887Sdim 44218887Sdim bool isReachable(const CFGBlock *block) const { 45218887Sdim return reachable[block->getBlockID()]; 46218887Sdim } 47218887Sdim}; 48218887Sdim} 49218887Sdim 50218887Sdimvoid ReachableCode::computeReachableBlocks() { 51218887Sdim if (!cfg.getNumBlockIDs()) 52218887Sdim return; 53218887Sdim 54218887Sdim llvm::SmallVector<const CFGBlock*, 10> worklist; 55218887Sdim worklist.push_back(&cfg.getEntry()); 56218887Sdim 57218887Sdim while (!worklist.empty()) { 58218887Sdim const CFGBlock *block = worklist.back(); 59218887Sdim worklist.pop_back(); 60218887Sdim llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; 61218887Sdim if (isReachable) 62218887Sdim continue; 63218887Sdim isReachable = true; 64218887Sdim for (CFGBlock::const_succ_iterator i = block->succ_begin(), 65218887Sdim e = block->succ_end(); i != e; ++i) 66218887Sdim if (const CFGBlock *succ = *i) 67218887Sdim worklist.push_back(succ); 68218887Sdim } 69218887Sdim} 70218887Sdim 71218887Sdimnamespace { 72218887Sdimclass DeadStoreObs : public LiveVariables::ObserverTy { 73218887Sdim const CFG &cfg; 74218887Sdim ASTContext &Ctx; 75218887Sdim BugReporter& BR; 76218887Sdim ParentMap& Parents; 77218887Sdim llvm::SmallPtrSet<VarDecl*, 20> Escaped; 78218887Sdim llvm::OwningPtr<ReachableCode> reachableCode; 79218887Sdim const CFGBlock *currentBlock; 80218887Sdim 81218887Sdim enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 82218887Sdim 83218887Sdimpublic: 84218887Sdim DeadStoreObs(const CFG &cfg, ASTContext &ctx, 85218887Sdim BugReporter& br, ParentMap& parents, 86218887Sdim llvm::SmallPtrSet<VarDecl*, 20> &escaped) 87218887Sdim : cfg(cfg), Ctx(ctx), BR(br), Parents(parents), 88218887Sdim Escaped(escaped), currentBlock(0) {} 89218887Sdim 90218887Sdim virtual ~DeadStoreObs() {} 91218887Sdim 92218887Sdim void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) { 93218887Sdim if (Escaped.count(V)) 94218887Sdim return; 95218887Sdim 96218887Sdim // Compute reachable blocks within the CFG for trivial cases 97218887Sdim // where a bogus dead store can be reported because itself is unreachable. 98218887Sdim if (!reachableCode.get()) { 99218887Sdim reachableCode.reset(new ReachableCode(cfg)); 100218887Sdim reachableCode->computeReachableBlocks(); 101218887Sdim } 102218887Sdim 103218887Sdim if (!reachableCode->isReachable(currentBlock)) 104218887Sdim return; 105218887Sdim 106218887Sdim const std::string &name = V->getNameAsString(); 107218887Sdim 108218887Sdim const char* BugType = 0; 109218887Sdim std::string msg; 110218887Sdim 111218887Sdim switch (dsk) { 112218887Sdim default: 113218887Sdim assert(false && "Impossible dead store type."); 114218887Sdim 115218887Sdim case DeadInit: 116218887Sdim BugType = "Dead initialization"; 117218887Sdim msg = "Value stored to '" + name + 118218887Sdim "' during its initialization is never read"; 119218887Sdim break; 120218887Sdim 121218887Sdim case DeadIncrement: 122218887Sdim BugType = "Dead increment"; 123218887Sdim case Standard: 124218887Sdim if (!BugType) BugType = "Dead assignment"; 125218887Sdim msg = "Value stored to '" + name + "' is never read"; 126218887Sdim break; 127218887Sdim 128218887Sdim case Enclosing: 129218887Sdim // Don't report issues in this case, e.g.: "if (x = foo())", 130218887Sdim // where 'x' is unused later. We have yet to see a case where 131218887Sdim // this is a real bug. 132218887Sdim return; 133218887Sdim } 134218887Sdim 135218887Sdim BR.EmitBasicReport(BugType, "Dead store", msg, L, R); 136218887Sdim } 137218887Sdim 138218887Sdim void CheckVarDecl(VarDecl* VD, Expr* Ex, Expr* Val, 139218887Sdim DeadStoreKind dsk, 140218887Sdim const LiveVariables::AnalysisDataTy& AD, 141218887Sdim const LiveVariables::ValTy& Live) { 142218887Sdim 143218887Sdim if (!VD->hasLocalStorage()) 144218887Sdim return; 145218887Sdim // Reference types confuse the dead stores checker. Skip them 146218887Sdim // for now. 147218887Sdim if (VD->getType()->getAs<ReferenceType>()) 148218887Sdim return; 149218887Sdim 150218887Sdim if (!Live(VD, AD) && 151218887Sdim !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) 152218887Sdim Report(VD, dsk, Ex->getSourceRange().getBegin(), 153218887Sdim Val->getSourceRange()); 154218887Sdim } 155218887Sdim 156218887Sdim void CheckDeclRef(DeclRefExpr* DR, Expr* Val, DeadStoreKind dsk, 157218887Sdim const LiveVariables::AnalysisDataTy& AD, 158218887Sdim const LiveVariables::ValTy& Live) { 159218887Sdim if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) 160218887Sdim CheckVarDecl(VD, DR, Val, dsk, AD, Live); 161218887Sdim } 162218887Sdim 163218887Sdim bool isIncrement(VarDecl* VD, BinaryOperator* B) { 164218887Sdim if (B->isCompoundAssignmentOp()) 165218887Sdim return true; 166218887Sdim 167218887Sdim Expr* RHS = B->getRHS()->IgnoreParenCasts(); 168218887Sdim BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); 169218887Sdim 170218887Sdim if (!BRHS) 171218887Sdim return false; 172218887Sdim 173218887Sdim DeclRefExpr *DR; 174218887Sdim 175218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 176218887Sdim if (DR->getDecl() == VD) 177218887Sdim return true; 178218887Sdim 179218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) 180218887Sdim if (DR->getDecl() == VD) 181218887Sdim return true; 182218887Sdim 183218887Sdim return false; 184218887Sdim } 185218887Sdim 186218887Sdim virtual void ObserveStmt(Stmt* S, const CFGBlock *block, 187218887Sdim const LiveVariables::AnalysisDataTy& AD, 188218887Sdim const LiveVariables::ValTy& Live) { 189218887Sdim 190218887Sdim currentBlock = block; 191218887Sdim 192218887Sdim // Skip statements in macros. 193218887Sdim if (S->getLocStart().isMacroID()) 194218887Sdim return; 195218887Sdim 196218887Sdim // Only cover dead stores from regular assignments. ++/-- dead stores 197218887Sdim // have never flagged a real bug. 198218887Sdim if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 199218887Sdim if (!B->isAssignmentOp()) return; // Skip non-assignments. 200218887Sdim 201218887Sdim if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS())) 202218887Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 203218887Sdim // Special case: check for assigning null to a pointer. 204218887Sdim // This is a common form of defensive programming. 205218887Sdim QualType T = VD->getType(); 206218887Sdim if (T->isPointerType() || T->isObjCObjectPointerType()) { 207218887Sdim if (B->getRHS()->isNullPointerConstant(Ctx, 208218887Sdim Expr::NPC_ValueDependentIsNull)) 209218887Sdim return; 210218887Sdim } 211218887Sdim 212218887Sdim Expr* RHS = B->getRHS()->IgnoreParenCasts(); 213218887Sdim // Special case: self-assignments. These are often used to shut up 214218887Sdim // "unused variable" compiler warnings. 215218887Sdim if (DeclRefExpr* RhsDR = dyn_cast<DeclRefExpr>(RHS)) 216218887Sdim if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 217218887Sdim return; 218218887Sdim 219218887Sdim // Otherwise, issue a warning. 220218887Sdim DeadStoreKind dsk = Parents.isConsumedExpr(B) 221218887Sdim ? Enclosing 222218887Sdim : (isIncrement(VD,B) ? DeadIncrement : Standard); 223218887Sdim 224218887Sdim CheckVarDecl(VD, DR, B->getRHS(), dsk, AD, Live); 225218887Sdim } 226218887Sdim } 227218887Sdim else if (UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 228218887Sdim if (!U->isIncrementOp() || U->isPrefix()) 229218887Sdim return; 230218887Sdim 231218887Sdim Stmt *parent = Parents.getParentIgnoreParenCasts(U); 232218887Sdim if (!parent || !isa<ReturnStmt>(parent)) 233218887Sdim return; 234218887Sdim 235218887Sdim Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 236218887Sdim 237218887Sdim if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex)) 238218887Sdim CheckDeclRef(DR, U, DeadIncrement, AD, Live); 239218887Sdim } 240218887Sdim else if (DeclStmt* DS = dyn_cast<DeclStmt>(S)) 241218887Sdim // Iterate through the decls. Warn if any initializers are complex 242218887Sdim // expressions that are not live (never used). 243218887Sdim for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); 244218887Sdim DI != DE; ++DI) { 245218887Sdim 246218887Sdim VarDecl* V = dyn_cast<VarDecl>(*DI); 247218887Sdim 248218887Sdim if (!V) 249218887Sdim continue; 250218887Sdim 251218887Sdim if (V->hasLocalStorage()) { 252218887Sdim // Reference types confuse the dead stores checker. Skip them 253218887Sdim // for now. 254218887Sdim if (V->getType()->getAs<ReferenceType>()) 255218887Sdim return; 256218887Sdim 257218887Sdim if (Expr* E = V->getInit()) { 258218887Sdim // Don't warn on C++ objects (yet) until we can show that their 259218887Sdim // constructors/destructors don't have side effects. 260218887Sdim if (isa<CXXConstructExpr>(E)) 261218887Sdim return; 262218887Sdim 263218887Sdim if (isa<ExprWithCleanups>(E)) 264218887Sdim return; 265218887Sdim 266218887Sdim // A dead initialization is a variable that is dead after it 267218887Sdim // is initialized. We don't flag warnings for those variables 268218887Sdim // marked 'unused'. 269218887Sdim if (!Live(V, AD) && V->getAttr<UnusedAttr>() == 0) { 270218887Sdim // Special case: check for initializations with constants. 271218887Sdim // 272218887Sdim // e.g. : int x = 0; 273218887Sdim // 274218887Sdim // If x is EVER assigned a new value later, don't issue 275218887Sdim // a warning. This is because such initialization can be 276218887Sdim // due to defensive programming. 277218887Sdim if (E->isConstantInitializer(Ctx, false)) 278218887Sdim return; 279218887Sdim 280218887Sdim if (DeclRefExpr *DRE=dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) 281218887Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { 282218887Sdim // Special case: check for initialization from constant 283218887Sdim // variables. 284218887Sdim // 285218887Sdim // e.g. extern const int MyConstant; 286218887Sdim // int x = MyConstant; 287218887Sdim // 288218887Sdim if (VD->hasGlobalStorage() && 289218887Sdim VD->getType().isConstQualified()) 290218887Sdim return; 291218887Sdim // Special case: check for initialization from scalar 292218887Sdim // parameters. This is often a form of defensive 293218887Sdim // programming. Non-scalars are still an error since 294218887Sdim // because it more likely represents an actual algorithmic 295218887Sdim // bug. 296218887Sdim if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) 297218887Sdim return; 298218887Sdim } 299218887Sdim 300218887Sdim Report(V, DeadInit, V->getLocation(), E->getSourceRange()); 301218887Sdim } 302218887Sdim } 303218887Sdim } 304218887Sdim } 305218887Sdim } 306218887Sdim}; 307218887Sdim 308218887Sdim} // end anonymous namespace 309218887Sdim 310218887Sdim//===----------------------------------------------------------------------===// 311218887Sdim// Driver function to invoke the Dead-Stores checker on a CFG. 312218887Sdim//===----------------------------------------------------------------------===// 313218887Sdim 314218887Sdimnamespace { 315218887Sdimclass FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{ 316218887Sdim CFG *cfg; 317218887Sdimpublic: 318218887Sdim FindEscaped(CFG *c) : cfg(c) {} 319218887Sdim 320218887Sdim CFG& getCFG() { return *cfg; } 321218887Sdim 322218887Sdim llvm::SmallPtrSet<VarDecl*, 20> Escaped; 323218887Sdim 324218887Sdim void VisitUnaryOperator(UnaryOperator* U) { 325218887Sdim // Check for '&'. Any VarDecl whose value has its address-taken we 326218887Sdim // treat as escaped. 327218887Sdim Expr* E = U->getSubExpr()->IgnoreParenCasts(); 328218887Sdim if (U->getOpcode() == UO_AddrOf) 329218887Sdim if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E)) 330218887Sdim if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { 331218887Sdim Escaped.insert(VD); 332218887Sdim return; 333218887Sdim } 334218887Sdim Visit(E); 335218887Sdim } 336218887Sdim}; 337218887Sdim} // end anonymous namespace 338218887Sdim 339218887Sdim 340218887Sdim//===----------------------------------------------------------------------===// 341218887Sdim// DeadStoresChecker 342218887Sdim//===----------------------------------------------------------------------===// 343218887Sdim 344218887Sdimnamespace { 345218887Sdimclass DeadStoresChecker : public CheckerV2<check::ASTCodeBody> { 346218887Sdimpublic: 347218887Sdim void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, 348218887Sdim BugReporter &BR) const { 349218887Sdim if (LiveVariables *L = mgr.getLiveVariables(D)) { 350218887Sdim CFG &cfg = *mgr.getCFG(D); 351218887Sdim ParentMap &pmap = mgr.getParentMap(D); 352218887Sdim FindEscaped FS(&cfg); 353218887Sdim FS.getCFG().VisitBlockStmts(FS); 354218887Sdim DeadStoreObs A(cfg, BR.getContext(), BR, pmap, FS.Escaped); 355218887Sdim L->runOnAllBlocks(cfg, &A); 356218887Sdim } 357218887Sdim } 358218887Sdim}; 359218887Sdim} 360218887Sdim 361218887Sdimvoid ento::registerDeadStoresChecker(CheckerManager &mgr) { 362218887Sdim mgr.registerChecker<DeadStoresChecker>(); 363218887Sdim} 364