DeadStoresChecker.cpp revision 249423
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" 17249423Sdim#include "clang/AST/Attr.h" 18243830Sdim#include "clang/AST/ParentMap.h" 19243830Sdim#include "clang/AST/RecursiveASTVisitor.h" 20218887Sdim#include "clang/Analysis/Analyses/LiveVariables.h" 21243830Sdim#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 22218887Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 23243830Sdim#include "clang/StaticAnalyzer/Core/Checker.h" 24243830Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 25243830Sdim#include "llvm/ADT/BitVector.h" 26234353Sdim#include "llvm/ADT/SmallString.h" 27243830Sdim#include "llvm/Support/SaveAndRestore.h" 28218887Sdim 29218887Sdimusing namespace clang; 30218887Sdimusing namespace ento; 31218887Sdim 32243830Sdimnamespace { 33243830Sdim 34243830Sdim/// A simple visitor to record what VarDecls occur in EH-handling code. 35243830Sdimclass EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> { 36243830Sdimpublic: 37243830Sdim bool inEH; 38243830Sdim llvm::DenseSet<const VarDecl *> &S; 39243830Sdim 40243830Sdim bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) { 41243830Sdim SaveAndRestore<bool> inFinally(inEH, true); 42243830Sdim return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S); 43243830Sdim } 44243830Sdim 45243830Sdim bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) { 46243830Sdim SaveAndRestore<bool> inCatch(inEH, true); 47243830Sdim return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S); 48243830Sdim } 49243830Sdim 50243830Sdim bool TraverseCXXCatchStmt(CXXCatchStmt *S) { 51243830Sdim SaveAndRestore<bool> inCatch(inEH, true); 52243830Sdim return TraverseStmt(S->getHandlerBlock()); 53243830Sdim } 54243830Sdim 55243830Sdim bool VisitDeclRefExpr(DeclRefExpr *DR) { 56243830Sdim if (inEH) 57243830Sdim if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 58243830Sdim S.insert(D); 59243830Sdim return true; 60243830Sdim } 61243830Sdim 62243830Sdim EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) : 63243830Sdim inEH(false), S(S) {} 64243830Sdim}; 65218887Sdim 66218887Sdim// FIXME: Eventually migrate into its own file, and have it managed by 67218887Sdim// AnalysisManager. 68218887Sdimclass ReachableCode { 69218887Sdim const CFG &cfg; 70218887Sdim llvm::BitVector reachable; 71218887Sdimpublic: 72218887Sdim ReachableCode(const CFG &cfg) 73218887Sdim : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {} 74218887Sdim 75218887Sdim void computeReachableBlocks(); 76218887Sdim 77218887Sdim bool isReachable(const CFGBlock *block) const { 78218887Sdim return reachable[block->getBlockID()]; 79218887Sdim } 80218887Sdim}; 81218887Sdim} 82218887Sdim 83218887Sdimvoid ReachableCode::computeReachableBlocks() { 84218887Sdim if (!cfg.getNumBlockIDs()) 85218887Sdim return; 86218887Sdim 87226633Sdim SmallVector<const CFGBlock*, 10> worklist; 88218887Sdim worklist.push_back(&cfg.getEntry()); 89218887Sdim 90218887Sdim while (!worklist.empty()) { 91218887Sdim const CFGBlock *block = worklist.back(); 92218887Sdim worklist.pop_back(); 93218887Sdim llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; 94218887Sdim if (isReachable) 95218887Sdim continue; 96218887Sdim isReachable = true; 97218887Sdim for (CFGBlock::const_succ_iterator i = block->succ_begin(), 98218887Sdim e = block->succ_end(); i != e; ++i) 99218887Sdim if (const CFGBlock *succ = *i) 100218887Sdim worklist.push_back(succ); 101218887Sdim } 102218887Sdim} 103218887Sdim 104234353Sdimstatic const Expr *LookThroughTransitiveAssignments(const Expr *Ex) { 105234353Sdim while (Ex) { 106234353Sdim const BinaryOperator *BO = 107234353Sdim dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts()); 108234353Sdim if (!BO) 109234353Sdim break; 110234353Sdim if (BO->getOpcode() == BO_Assign) { 111234353Sdim Ex = BO->getRHS(); 112234353Sdim continue; 113234353Sdim } 114234353Sdim break; 115234353Sdim } 116234353Sdim return Ex; 117234353Sdim} 118234353Sdim 119218887Sdimnamespace { 120226633Sdimclass DeadStoreObs : public LiveVariables::Observer { 121218887Sdim const CFG &cfg; 122218887Sdim ASTContext &Ctx; 123218887Sdim BugReporter& BR; 124234353Sdim AnalysisDeclContext* AC; 125218887Sdim ParentMap& Parents; 126226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 127234353Sdim OwningPtr<ReachableCode> reachableCode; 128218887Sdim const CFGBlock *currentBlock; 129249423Sdim OwningPtr<llvm::DenseSet<const VarDecl *> > InEH; 130218887Sdim 131218887Sdim enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 132218887Sdim 133218887Sdimpublic: 134218887Sdim DeadStoreObs(const CFG &cfg, ASTContext &ctx, 135234353Sdim BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents, 136226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> &escaped) 137226633Sdim : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents), 138218887Sdim Escaped(escaped), currentBlock(0) {} 139218887Sdim 140218887Sdim virtual ~DeadStoreObs() {} 141218887Sdim 142243830Sdim bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) { 143243830Sdim if (Live.isLive(D)) 144243830Sdim return true; 145243830Sdim // Lazily construct the set that records which VarDecls are in 146243830Sdim // EH code. 147243830Sdim if (!InEH.get()) { 148243830Sdim InEH.reset(new llvm::DenseSet<const VarDecl *>()); 149243830Sdim EHCodeVisitor V(*InEH.get()); 150243830Sdim V.TraverseStmt(AC->getBody()); 151243830Sdim } 152243830Sdim // Treat all VarDecls that occur in EH code as being "always live" 153243830Sdim // when considering to suppress dead stores. Frequently stores 154243830Sdim // are followed by reads in EH code, but we don't have the ability 155243830Sdim // to analyze that yet. 156243830Sdim return InEH->count(D); 157243830Sdim } 158243830Sdim 159226633Sdim void Report(const VarDecl *V, DeadStoreKind dsk, 160226633Sdim PathDiagnosticLocation L, SourceRange R) { 161218887Sdim if (Escaped.count(V)) 162218887Sdim return; 163218887Sdim 164218887Sdim // Compute reachable blocks within the CFG for trivial cases 165218887Sdim // where a bogus dead store can be reported because itself is unreachable. 166218887Sdim if (!reachableCode.get()) { 167218887Sdim reachableCode.reset(new ReachableCode(cfg)); 168218887Sdim reachableCode->computeReachableBlocks(); 169218887Sdim } 170218887Sdim 171218887Sdim if (!reachableCode->isReachable(currentBlock)) 172218887Sdim return; 173218887Sdim 174234353Sdim SmallString<64> buf; 175226633Sdim llvm::raw_svector_ostream os(buf); 176226633Sdim const char *BugType = 0; 177218887Sdim 178218887Sdim switch (dsk) { 179218887Sdim case DeadInit: 180218887Sdim BugType = "Dead initialization"; 181226633Sdim os << "Value stored to '" << *V 182226633Sdim << "' during its initialization is never read"; 183218887Sdim break; 184218887Sdim 185218887Sdim case DeadIncrement: 186218887Sdim BugType = "Dead increment"; 187218887Sdim case Standard: 188218887Sdim if (!BugType) BugType = "Dead assignment"; 189226633Sdim os << "Value stored to '" << *V << "' is never read"; 190218887Sdim break; 191218887Sdim 192218887Sdim case Enclosing: 193218887Sdim // Don't report issues in this case, e.g.: "if (x = foo())", 194218887Sdim // where 'x' is unused later. We have yet to see a case where 195218887Sdim // this is a real bug. 196218887Sdim return; 197218887Sdim } 198218887Sdim 199234353Sdim BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R); 200218887Sdim } 201218887Sdim 202226633Sdim void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val, 203218887Sdim DeadStoreKind dsk, 204226633Sdim const LiveVariables::LivenessValues &Live) { 205218887Sdim 206218887Sdim if (!VD->hasLocalStorage()) 207218887Sdim return; 208218887Sdim // Reference types confuse the dead stores checker. Skip them 209218887Sdim // for now. 210218887Sdim if (VD->getType()->getAs<ReferenceType>()) 211218887Sdim return; 212218887Sdim 213243830Sdim if (!isLive(Live, VD) && 214226633Sdim !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) { 215226633Sdim 216226633Sdim PathDiagnosticLocation ExLoc = 217226633Sdim PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); 218226633Sdim Report(VD, dsk, ExLoc, Val->getSourceRange()); 219226633Sdim } 220218887Sdim } 221218887Sdim 222226633Sdim void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk, 223226633Sdim const LiveVariables::LivenessValues& Live) { 224226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 225226633Sdim CheckVarDecl(VD, DR, Val, dsk, Live); 226218887Sdim } 227218887Sdim 228226633Sdim bool isIncrement(VarDecl *VD, const BinaryOperator* B) { 229218887Sdim if (B->isCompoundAssignmentOp()) 230218887Sdim return true; 231218887Sdim 232226633Sdim const Expr *RHS = B->getRHS()->IgnoreParenCasts(); 233226633Sdim const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); 234218887Sdim 235218887Sdim if (!BRHS) 236218887Sdim return false; 237218887Sdim 238226633Sdim const DeclRefExpr *DR; 239218887Sdim 240218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 241218887Sdim if (DR->getDecl() == VD) 242218887Sdim return true; 243218887Sdim 244218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) 245218887Sdim if (DR->getDecl() == VD) 246218887Sdim return true; 247218887Sdim 248218887Sdim return false; 249218887Sdim } 250218887Sdim 251226633Sdim virtual void observeStmt(const Stmt *S, const CFGBlock *block, 252226633Sdim const LiveVariables::LivenessValues &Live) { 253218887Sdim 254218887Sdim currentBlock = block; 255218887Sdim 256218887Sdim // Skip statements in macros. 257218887Sdim if (S->getLocStart().isMacroID()) 258218887Sdim return; 259218887Sdim 260218887Sdim // Only cover dead stores from regular assignments. ++/-- dead stores 261218887Sdim // have never flagged a real bug. 262226633Sdim if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 263218887Sdim if (!B->isAssignmentOp()) return; // Skip non-assignments. 264218887Sdim 265226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) 266218887Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 267218887Sdim // Special case: check for assigning null to a pointer. 268218887Sdim // This is a common form of defensive programming. 269234353Sdim const Expr *RHS = LookThroughTransitiveAssignments(B->getRHS()); 270234353Sdim 271218887Sdim QualType T = VD->getType(); 272218887Sdim if (T->isPointerType() || T->isObjCObjectPointerType()) { 273234353Sdim if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull)) 274218887Sdim return; 275218887Sdim } 276218887Sdim 277234353Sdim RHS = RHS->IgnoreParenCasts(); 278218887Sdim // Special case: self-assignments. These are often used to shut up 279218887Sdim // "unused variable" compiler warnings. 280234353Sdim if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS)) 281218887Sdim if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 282218887Sdim return; 283218887Sdim 284218887Sdim // Otherwise, issue a warning. 285218887Sdim DeadStoreKind dsk = Parents.isConsumedExpr(B) 286218887Sdim ? Enclosing 287218887Sdim : (isIncrement(VD,B) ? DeadIncrement : Standard); 288218887Sdim 289226633Sdim CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); 290218887Sdim } 291218887Sdim } 292226633Sdim else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 293218887Sdim if (!U->isIncrementOp() || U->isPrefix()) 294218887Sdim return; 295218887Sdim 296226633Sdim const Stmt *parent = Parents.getParentIgnoreParenCasts(U); 297218887Sdim if (!parent || !isa<ReturnStmt>(parent)) 298218887Sdim return; 299218887Sdim 300226633Sdim const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 301218887Sdim 302226633Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) 303226633Sdim CheckDeclRef(DR, U, DeadIncrement, Live); 304218887Sdim } 305226633Sdim else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) 306218887Sdim // Iterate through the decls. Warn if any initializers are complex 307218887Sdim // expressions that are not live (never used). 308226633Sdim for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); 309218887Sdim DI != DE; ++DI) { 310218887Sdim 311226633Sdim VarDecl *V = dyn_cast<VarDecl>(*DI); 312218887Sdim 313218887Sdim if (!V) 314218887Sdim continue; 315218887Sdim 316218887Sdim if (V->hasLocalStorage()) { 317218887Sdim // Reference types confuse the dead stores checker. Skip them 318218887Sdim // for now. 319218887Sdim if (V->getType()->getAs<ReferenceType>()) 320218887Sdim return; 321218887Sdim 322234353Sdim if (const Expr *E = V->getInit()) { 323234353Sdim while (const ExprWithCleanups *exprClean = 324234353Sdim dyn_cast<ExprWithCleanups>(E)) 325224145Sdim E = exprClean->getSubExpr(); 326224145Sdim 327234353Sdim // Look through transitive assignments, e.g.: 328234353Sdim // int x = y = 0; 329234353Sdim E = LookThroughTransitiveAssignments(E); 330234353Sdim 331218887Sdim // Don't warn on C++ objects (yet) until we can show that their 332218887Sdim // constructors/destructors don't have side effects. 333218887Sdim if (isa<CXXConstructExpr>(E)) 334218887Sdim return; 335218887Sdim 336218887Sdim // A dead initialization is a variable that is dead after it 337218887Sdim // is initialized. We don't flag warnings for those variables 338218887Sdim // marked 'unused'. 339243830Sdim if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) { 340218887Sdim // Special case: check for initializations with constants. 341218887Sdim // 342218887Sdim // e.g. : int x = 0; 343218887Sdim // 344218887Sdim // If x is EVER assigned a new value later, don't issue 345218887Sdim // a warning. This is because such initialization can be 346218887Sdim // due to defensive programming. 347234353Sdim if (E->isEvaluatable(Ctx)) 348218887Sdim return; 349218887Sdim 350234353Sdim if (const DeclRefExpr *DRE = 351234353Sdim dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) 352234353Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { 353218887Sdim // Special case: check for initialization from constant 354218887Sdim // variables. 355218887Sdim // 356218887Sdim // e.g. extern const int MyConstant; 357218887Sdim // int x = MyConstant; 358218887Sdim // 359218887Sdim if (VD->hasGlobalStorage() && 360218887Sdim VD->getType().isConstQualified()) 361218887Sdim return; 362218887Sdim // Special case: check for initialization from scalar 363218887Sdim // parameters. This is often a form of defensive 364218887Sdim // programming. Non-scalars are still an error since 365218887Sdim // because it more likely represents an actual algorithmic 366218887Sdim // bug. 367218887Sdim if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) 368218887Sdim return; 369218887Sdim } 370218887Sdim 371226633Sdim PathDiagnosticLocation Loc = 372226633Sdim PathDiagnosticLocation::create(V, BR.getSourceManager()); 373226633Sdim Report(V, DeadInit, Loc, E->getSourceRange()); 374218887Sdim } 375218887Sdim } 376218887Sdim } 377218887Sdim } 378218887Sdim } 379218887Sdim}; 380218887Sdim 381218887Sdim} // end anonymous namespace 382218887Sdim 383218887Sdim//===----------------------------------------------------------------------===// 384218887Sdim// Driver function to invoke the Dead-Stores checker on a CFG. 385218887Sdim//===----------------------------------------------------------------------===// 386218887Sdim 387218887Sdimnamespace { 388218887Sdimclass FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{ 389218887Sdim CFG *cfg; 390218887Sdimpublic: 391218887Sdim FindEscaped(CFG *c) : cfg(c) {} 392218887Sdim 393218887Sdim CFG& getCFG() { return *cfg; } 394218887Sdim 395226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 396218887Sdim 397218887Sdim void VisitUnaryOperator(UnaryOperator* U) { 398218887Sdim // Check for '&'. Any VarDecl whose value has its address-taken we 399218887Sdim // treat as escaped. 400226633Sdim Expr *E = U->getSubExpr()->IgnoreParenCasts(); 401218887Sdim if (U->getOpcode() == UO_AddrOf) 402226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 403226633Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 404218887Sdim Escaped.insert(VD); 405218887Sdim return; 406218887Sdim } 407218887Sdim Visit(E); 408218887Sdim } 409218887Sdim}; 410218887Sdim} // end anonymous namespace 411218887Sdim 412218887Sdim 413218887Sdim//===----------------------------------------------------------------------===// 414218887Sdim// DeadStoresChecker 415218887Sdim//===----------------------------------------------------------------------===// 416218887Sdim 417218887Sdimnamespace { 418221345Sdimclass DeadStoresChecker : public Checker<check::ASTCodeBody> { 419218887Sdimpublic: 420218887Sdim void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, 421218887Sdim BugReporter &BR) const { 422249423Sdim 423249423Sdim // Don't do anything for template instantiations. 424249423Sdim // Proving that code in a template instantiation is "dead" 425249423Sdim // means proving that it is dead in all instantiations. 426249423Sdim // This same problem exists with -Wunreachable-code. 427249423Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) 428249423Sdim if (FD->isTemplateInstantiation()) 429249423Sdim return; 430249423Sdim 431226633Sdim if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) { 432218887Sdim CFG &cfg = *mgr.getCFG(D); 433234353Sdim AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D); 434218887Sdim ParentMap &pmap = mgr.getParentMap(D); 435218887Sdim FindEscaped FS(&cfg); 436218887Sdim FS.getCFG().VisitBlockStmts(FS); 437226633Sdim DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped); 438226633Sdim L->runOnAllBlocks(A); 439218887Sdim } 440218887Sdim } 441218887Sdim}; 442218887Sdim} 443218887Sdim 444218887Sdimvoid ento::registerDeadStoresChecker(CheckerManager &mgr) { 445218887Sdim mgr.registerChecker<DeadStoresChecker>(); 446218887Sdim} 447