DeadStoresChecker.cpp revision 243830
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" 16243830Sdim#include "clang/AST/ASTContext.h" 17243830Sdim#include "clang/AST/ParentMap.h" 18243830Sdim#include "clang/AST/RecursiveASTVisitor.h" 19218887Sdim#include "clang/Analysis/Analyses/LiveVariables.h" 20243830Sdim#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 21218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 22243830Sdim#include "clang/StaticAnalyzer/Core/Checker.h" 23243830Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 24243830Sdim#include "llvm/ADT/BitVector.h" 25234353Sdim#include "llvm/ADT/SmallString.h" 26243830Sdim#include "llvm/Support/SaveAndRestore.h" 27218887Sdim 28218887Sdimusing namespace clang; 29218887Sdimusing namespace ento; 30218887Sdim 31243830Sdimnamespace { 32243830Sdim 33243830Sdim/// A simple visitor to record what VarDecls occur in EH-handling code. 34243830Sdimclass EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> { 35243830Sdimpublic: 36243830Sdim bool inEH; 37243830Sdim llvm::DenseSet<const VarDecl *> &S; 38243830Sdim 39243830Sdim bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) { 40243830Sdim SaveAndRestore<bool> inFinally(inEH, true); 41243830Sdim return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S); 42243830Sdim } 43243830Sdim 44243830Sdim bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) { 45243830Sdim SaveAndRestore<bool> inCatch(inEH, true); 46243830Sdim return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S); 47243830Sdim } 48243830Sdim 49243830Sdim bool TraverseCXXCatchStmt(CXXCatchStmt *S) { 50243830Sdim SaveAndRestore<bool> inCatch(inEH, true); 51243830Sdim return TraverseStmt(S->getHandlerBlock()); 52243830Sdim } 53243830Sdim 54243830Sdim bool VisitDeclRefExpr(DeclRefExpr *DR) { 55243830Sdim if (inEH) 56243830Sdim if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 57243830Sdim S.insert(D); 58243830Sdim return true; 59243830Sdim } 60243830Sdim 61243830Sdim EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) : 62243830Sdim inEH(false), S(S) {} 63243830Sdim}; 64218887Sdim 65218887Sdim// FIXME: Eventually migrate into its own file, and have it managed by 66218887Sdim// AnalysisManager. 67218887Sdimclass ReachableCode { 68218887Sdim const CFG &cfg; 69218887Sdim llvm::BitVector reachable; 70218887Sdimpublic: 71218887Sdim ReachableCode(const CFG &cfg) 72218887Sdim : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {} 73218887Sdim 74218887Sdim void computeReachableBlocks(); 75218887Sdim 76218887Sdim bool isReachable(const CFGBlock *block) const { 77218887Sdim return reachable[block->getBlockID()]; 78218887Sdim } 79218887Sdim}; 80218887Sdim} 81218887Sdim 82218887Sdimvoid ReachableCode::computeReachableBlocks() { 83218887Sdim if (!cfg.getNumBlockIDs()) 84218887Sdim return; 85218887Sdim 86226633Sdim SmallVector<const CFGBlock*, 10> worklist; 87218887Sdim worklist.push_back(&cfg.getEntry()); 88218887Sdim 89218887Sdim while (!worklist.empty()) { 90218887Sdim const CFGBlock *block = worklist.back(); 91218887Sdim worklist.pop_back(); 92218887Sdim llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; 93218887Sdim if (isReachable) 94218887Sdim continue; 95218887Sdim isReachable = true; 96218887Sdim for (CFGBlock::const_succ_iterator i = block->succ_begin(), 97218887Sdim e = block->succ_end(); i != e; ++i) 98218887Sdim if (const CFGBlock *succ = *i) 99218887Sdim worklist.push_back(succ); 100218887Sdim } 101218887Sdim} 102218887Sdim 103234353Sdimstatic const Expr *LookThroughTransitiveAssignments(const Expr *Ex) { 104234353Sdim while (Ex) { 105234353Sdim const BinaryOperator *BO = 106234353Sdim dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts()); 107234353Sdim if (!BO) 108234353Sdim break; 109234353Sdim if (BO->getOpcode() == BO_Assign) { 110234353Sdim Ex = BO->getRHS(); 111234353Sdim continue; 112234353Sdim } 113234353Sdim break; 114234353Sdim } 115234353Sdim return Ex; 116234353Sdim} 117234353Sdim 118218887Sdimnamespace { 119226633Sdimclass DeadStoreObs : public LiveVariables::Observer { 120218887Sdim const CFG &cfg; 121218887Sdim ASTContext &Ctx; 122218887Sdim BugReporter& BR; 123234353Sdim AnalysisDeclContext* AC; 124218887Sdim ParentMap& Parents; 125226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 126234353Sdim OwningPtr<ReachableCode> reachableCode; 127218887Sdim const CFGBlock *currentBlock; 128243830Sdim llvm::OwningPtr<llvm::DenseSet<const VarDecl *> > InEH; 129218887Sdim 130218887Sdim enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 131218887Sdim 132218887Sdimpublic: 133218887Sdim DeadStoreObs(const CFG &cfg, ASTContext &ctx, 134234353Sdim BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents, 135226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> &escaped) 136226633Sdim : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents), 137218887Sdim Escaped(escaped), currentBlock(0) {} 138218887Sdim 139218887Sdim virtual ~DeadStoreObs() {} 140218887Sdim 141243830Sdim bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) { 142243830Sdim if (Live.isLive(D)) 143243830Sdim return true; 144243830Sdim // Lazily construct the set that records which VarDecls are in 145243830Sdim // EH code. 146243830Sdim if (!InEH.get()) { 147243830Sdim InEH.reset(new llvm::DenseSet<const VarDecl *>()); 148243830Sdim EHCodeVisitor V(*InEH.get()); 149243830Sdim V.TraverseStmt(AC->getBody()); 150243830Sdim } 151243830Sdim // Treat all VarDecls that occur in EH code as being "always live" 152243830Sdim // when considering to suppress dead stores. Frequently stores 153243830Sdim // are followed by reads in EH code, but we don't have the ability 154243830Sdim // to analyze that yet. 155243830Sdim return InEH->count(D); 156243830Sdim } 157243830Sdim 158226633Sdim void Report(const VarDecl *V, DeadStoreKind dsk, 159226633Sdim PathDiagnosticLocation L, SourceRange R) { 160218887Sdim if (Escaped.count(V)) 161218887Sdim return; 162218887Sdim 163218887Sdim // Compute reachable blocks within the CFG for trivial cases 164218887Sdim // where a bogus dead store can be reported because itself is unreachable. 165218887Sdim if (!reachableCode.get()) { 166218887Sdim reachableCode.reset(new ReachableCode(cfg)); 167218887Sdim reachableCode->computeReachableBlocks(); 168218887Sdim } 169218887Sdim 170218887Sdim if (!reachableCode->isReachable(currentBlock)) 171218887Sdim return; 172218887Sdim 173234353Sdim SmallString<64> buf; 174226633Sdim llvm::raw_svector_ostream os(buf); 175226633Sdim const char *BugType = 0; 176218887Sdim 177218887Sdim switch (dsk) { 178218887Sdim case DeadInit: 179218887Sdim BugType = "Dead initialization"; 180226633Sdim os << "Value stored to '" << *V 181226633Sdim << "' during its initialization is never read"; 182218887Sdim break; 183218887Sdim 184218887Sdim case DeadIncrement: 185218887Sdim BugType = "Dead increment"; 186218887Sdim case Standard: 187218887Sdim if (!BugType) BugType = "Dead assignment"; 188226633Sdim os << "Value stored to '" << *V << "' is never read"; 189218887Sdim break; 190218887Sdim 191218887Sdim case Enclosing: 192218887Sdim // Don't report issues in this case, e.g.: "if (x = foo())", 193218887Sdim // where 'x' is unused later. We have yet to see a case where 194218887Sdim // this is a real bug. 195218887Sdim return; 196218887Sdim } 197218887Sdim 198234353Sdim BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R); 199218887Sdim } 200218887Sdim 201226633Sdim void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val, 202218887Sdim DeadStoreKind dsk, 203226633Sdim const LiveVariables::LivenessValues &Live) { 204218887Sdim 205218887Sdim if (!VD->hasLocalStorage()) 206218887Sdim return; 207218887Sdim // Reference types confuse the dead stores checker. Skip them 208218887Sdim // for now. 209218887Sdim if (VD->getType()->getAs<ReferenceType>()) 210218887Sdim return; 211218887Sdim 212243830Sdim if (!isLive(Live, VD) && 213226633Sdim !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) { 214226633Sdim 215226633Sdim PathDiagnosticLocation ExLoc = 216226633Sdim PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); 217226633Sdim Report(VD, dsk, ExLoc, Val->getSourceRange()); 218226633Sdim } 219218887Sdim } 220218887Sdim 221226633Sdim void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk, 222226633Sdim const LiveVariables::LivenessValues& Live) { 223226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 224226633Sdim CheckVarDecl(VD, DR, Val, dsk, Live); 225218887Sdim } 226218887Sdim 227226633Sdim bool isIncrement(VarDecl *VD, const BinaryOperator* B) { 228218887Sdim if (B->isCompoundAssignmentOp()) 229218887Sdim return true; 230218887Sdim 231226633Sdim const Expr *RHS = B->getRHS()->IgnoreParenCasts(); 232226633Sdim const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); 233218887Sdim 234218887Sdim if (!BRHS) 235218887Sdim return false; 236218887Sdim 237226633Sdim const DeclRefExpr *DR; 238218887Sdim 239218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 240218887Sdim if (DR->getDecl() == VD) 241218887Sdim return true; 242218887Sdim 243218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) 244218887Sdim if (DR->getDecl() == VD) 245218887Sdim return true; 246218887Sdim 247218887Sdim return false; 248218887Sdim } 249218887Sdim 250226633Sdim virtual void observeStmt(const Stmt *S, const CFGBlock *block, 251226633Sdim const LiveVariables::LivenessValues &Live) { 252218887Sdim 253218887Sdim currentBlock = block; 254218887Sdim 255218887Sdim // Skip statements in macros. 256218887Sdim if (S->getLocStart().isMacroID()) 257218887Sdim return; 258218887Sdim 259218887Sdim // Only cover dead stores from regular assignments. ++/-- dead stores 260218887Sdim // have never flagged a real bug. 261226633Sdim if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 262218887Sdim if (!B->isAssignmentOp()) return; // Skip non-assignments. 263218887Sdim 264226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) 265218887Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 266218887Sdim // Special case: check for assigning null to a pointer. 267218887Sdim // This is a common form of defensive programming. 268234353Sdim const Expr *RHS = LookThroughTransitiveAssignments(B->getRHS()); 269234353Sdim 270218887Sdim QualType T = VD->getType(); 271218887Sdim if (T->isPointerType() || T->isObjCObjectPointerType()) { 272234353Sdim if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull)) 273218887Sdim return; 274218887Sdim } 275218887Sdim 276234353Sdim RHS = RHS->IgnoreParenCasts(); 277218887Sdim // Special case: self-assignments. These are often used to shut up 278218887Sdim // "unused variable" compiler warnings. 279234353Sdim if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS)) 280218887Sdim if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 281218887Sdim return; 282218887Sdim 283218887Sdim // Otherwise, issue a warning. 284218887Sdim DeadStoreKind dsk = Parents.isConsumedExpr(B) 285218887Sdim ? Enclosing 286218887Sdim : (isIncrement(VD,B) ? DeadIncrement : Standard); 287218887Sdim 288226633Sdim CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); 289218887Sdim } 290218887Sdim } 291226633Sdim else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 292218887Sdim if (!U->isIncrementOp() || U->isPrefix()) 293218887Sdim return; 294218887Sdim 295226633Sdim const Stmt *parent = Parents.getParentIgnoreParenCasts(U); 296218887Sdim if (!parent || !isa<ReturnStmt>(parent)) 297218887Sdim return; 298218887Sdim 299226633Sdim const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 300218887Sdim 301226633Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) 302226633Sdim CheckDeclRef(DR, U, DeadIncrement, Live); 303218887Sdim } 304226633Sdim else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) 305218887Sdim // Iterate through the decls. Warn if any initializers are complex 306218887Sdim // expressions that are not live (never used). 307226633Sdim for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); 308218887Sdim DI != DE; ++DI) { 309218887Sdim 310226633Sdim VarDecl *V = dyn_cast<VarDecl>(*DI); 311218887Sdim 312218887Sdim if (!V) 313218887Sdim continue; 314218887Sdim 315218887Sdim if (V->hasLocalStorage()) { 316218887Sdim // Reference types confuse the dead stores checker. Skip them 317218887Sdim // for now. 318218887Sdim if (V->getType()->getAs<ReferenceType>()) 319218887Sdim return; 320218887Sdim 321234353Sdim if (const Expr *E = V->getInit()) { 322234353Sdim while (const ExprWithCleanups *exprClean = 323234353Sdim dyn_cast<ExprWithCleanups>(E)) 324224145Sdim E = exprClean->getSubExpr(); 325224145Sdim 326234353Sdim // Look through transitive assignments, e.g.: 327234353Sdim // int x = y = 0; 328234353Sdim E = LookThroughTransitiveAssignments(E); 329234353Sdim 330218887Sdim // Don't warn on C++ objects (yet) until we can show that their 331218887Sdim // constructors/destructors don't have side effects. 332218887Sdim if (isa<CXXConstructExpr>(E)) 333218887Sdim return; 334218887Sdim 335218887Sdim // A dead initialization is a variable that is dead after it 336218887Sdim // is initialized. We don't flag warnings for those variables 337218887Sdim // marked 'unused'. 338243830Sdim if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) { 339218887Sdim // Special case: check for initializations with constants. 340218887Sdim // 341218887Sdim // e.g. : int x = 0; 342218887Sdim // 343218887Sdim // If x is EVER assigned a new value later, don't issue 344218887Sdim // a warning. This is because such initialization can be 345218887Sdim // due to defensive programming. 346234353Sdim if (E->isEvaluatable(Ctx)) 347218887Sdim return; 348218887Sdim 349234353Sdim if (const DeclRefExpr *DRE = 350234353Sdim dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) 351234353Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { 352218887Sdim // Special case: check for initialization from constant 353218887Sdim // variables. 354218887Sdim // 355218887Sdim // e.g. extern const int MyConstant; 356218887Sdim // int x = MyConstant; 357218887Sdim // 358218887Sdim if (VD->hasGlobalStorage() && 359218887Sdim VD->getType().isConstQualified()) 360218887Sdim return; 361218887Sdim // Special case: check for initialization from scalar 362218887Sdim // parameters. This is often a form of defensive 363218887Sdim // programming. Non-scalars are still an error since 364218887Sdim // because it more likely represents an actual algorithmic 365218887Sdim // bug. 366218887Sdim if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) 367218887Sdim return; 368218887Sdim } 369218887Sdim 370226633Sdim PathDiagnosticLocation Loc = 371226633Sdim PathDiagnosticLocation::create(V, BR.getSourceManager()); 372226633Sdim Report(V, DeadInit, Loc, E->getSourceRange()); 373218887Sdim } 374218887Sdim } 375218887Sdim } 376218887Sdim } 377218887Sdim } 378218887Sdim}; 379218887Sdim 380218887Sdim} // end anonymous namespace 381218887Sdim 382218887Sdim//===----------------------------------------------------------------------===// 383218887Sdim// Driver function to invoke the Dead-Stores checker on a CFG. 384218887Sdim//===----------------------------------------------------------------------===// 385218887Sdim 386218887Sdimnamespace { 387218887Sdimclass FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{ 388218887Sdim CFG *cfg; 389218887Sdimpublic: 390218887Sdim FindEscaped(CFG *c) : cfg(c) {} 391218887Sdim 392218887Sdim CFG& getCFG() { return *cfg; } 393218887Sdim 394226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 395218887Sdim 396218887Sdim void VisitUnaryOperator(UnaryOperator* U) { 397218887Sdim // Check for '&'. Any VarDecl whose value has its address-taken we 398218887Sdim // treat as escaped. 399226633Sdim Expr *E = U->getSubExpr()->IgnoreParenCasts(); 400218887Sdim if (U->getOpcode() == UO_AddrOf) 401226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 402226633Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 403218887Sdim Escaped.insert(VD); 404218887Sdim return; 405218887Sdim } 406218887Sdim Visit(E); 407218887Sdim } 408218887Sdim}; 409218887Sdim} // end anonymous namespace 410218887Sdim 411218887Sdim 412218887Sdim//===----------------------------------------------------------------------===// 413218887Sdim// DeadStoresChecker 414218887Sdim//===----------------------------------------------------------------------===// 415218887Sdim 416218887Sdimnamespace { 417221345Sdimclass DeadStoresChecker : public Checker<check::ASTCodeBody> { 418218887Sdimpublic: 419218887Sdim void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, 420218887Sdim BugReporter &BR) const { 421226633Sdim if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) { 422218887Sdim CFG &cfg = *mgr.getCFG(D); 423234353Sdim AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D); 424218887Sdim ParentMap &pmap = mgr.getParentMap(D); 425218887Sdim FindEscaped FS(&cfg); 426218887Sdim FS.getCFG().VisitBlockStmts(FS); 427226633Sdim DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped); 428226633Sdim L->runOnAllBlocks(A); 429218887Sdim } 430218887Sdim } 431218887Sdim}; 432218887Sdim} 433218887Sdim 434218887Sdimvoid ento::registerDeadStoresChecker(CheckerManager &mgr) { 435218887Sdim mgr.registerChecker<DeadStoresChecker>(); 436218887Sdim} 437