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 104251662Sdimstatic const Expr * 105251662SdimLookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) { 106234353Sdim while (Ex) { 107234353Sdim const BinaryOperator *BO = 108234353Sdim dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts()); 109234353Sdim if (!BO) 110234353Sdim break; 111234353Sdim if (BO->getOpcode() == BO_Assign) { 112234353Sdim Ex = BO->getRHS(); 113234353Sdim continue; 114234353Sdim } 115251662Sdim if (BO->getOpcode() == BO_Comma) { 116251662Sdim Ex = BO->getRHS(); 117251662Sdim continue; 118251662Sdim } 119234353Sdim break; 120234353Sdim } 121234353Sdim return Ex; 122234353Sdim} 123234353Sdim 124218887Sdimnamespace { 125226633Sdimclass DeadStoreObs : public LiveVariables::Observer { 126218887Sdim const CFG &cfg; 127218887Sdim ASTContext &Ctx; 128218887Sdim BugReporter& BR; 129234353Sdim AnalysisDeclContext* AC; 130218887Sdim ParentMap& Parents; 131226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 132234353Sdim OwningPtr<ReachableCode> reachableCode; 133218887Sdim const CFGBlock *currentBlock; 134249423Sdim OwningPtr<llvm::DenseSet<const VarDecl *> > InEH; 135218887Sdim 136218887Sdim enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 137218887Sdim 138218887Sdimpublic: 139218887Sdim DeadStoreObs(const CFG &cfg, ASTContext &ctx, 140234353Sdim BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents, 141226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> &escaped) 142226633Sdim : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents), 143218887Sdim Escaped(escaped), currentBlock(0) {} 144218887Sdim 145218887Sdim virtual ~DeadStoreObs() {} 146218887Sdim 147243830Sdim bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) { 148243830Sdim if (Live.isLive(D)) 149243830Sdim return true; 150243830Sdim // Lazily construct the set that records which VarDecls are in 151243830Sdim // EH code. 152243830Sdim if (!InEH.get()) { 153243830Sdim InEH.reset(new llvm::DenseSet<const VarDecl *>()); 154243830Sdim EHCodeVisitor V(*InEH.get()); 155243830Sdim V.TraverseStmt(AC->getBody()); 156243830Sdim } 157243830Sdim // Treat all VarDecls that occur in EH code as being "always live" 158243830Sdim // when considering to suppress dead stores. Frequently stores 159243830Sdim // are followed by reads in EH code, but we don't have the ability 160243830Sdim // to analyze that yet. 161243830Sdim return InEH->count(D); 162243830Sdim } 163243830Sdim 164226633Sdim void Report(const VarDecl *V, DeadStoreKind dsk, 165226633Sdim PathDiagnosticLocation L, SourceRange R) { 166218887Sdim if (Escaped.count(V)) 167218887Sdim return; 168218887Sdim 169218887Sdim // Compute reachable blocks within the CFG for trivial cases 170218887Sdim // where a bogus dead store can be reported because itself is unreachable. 171218887Sdim if (!reachableCode.get()) { 172218887Sdim reachableCode.reset(new ReachableCode(cfg)); 173218887Sdim reachableCode->computeReachableBlocks(); 174218887Sdim } 175218887Sdim 176218887Sdim if (!reachableCode->isReachable(currentBlock)) 177218887Sdim return; 178218887Sdim 179234353Sdim SmallString<64> buf; 180226633Sdim llvm::raw_svector_ostream os(buf); 181226633Sdim const char *BugType = 0; 182218887Sdim 183218887Sdim switch (dsk) { 184218887Sdim case DeadInit: 185218887Sdim BugType = "Dead initialization"; 186226633Sdim os << "Value stored to '" << *V 187226633Sdim << "' during its initialization is never read"; 188218887Sdim break; 189218887Sdim 190218887Sdim case DeadIncrement: 191218887Sdim BugType = "Dead increment"; 192218887Sdim case Standard: 193218887Sdim if (!BugType) BugType = "Dead assignment"; 194226633Sdim os << "Value stored to '" << *V << "' is never read"; 195218887Sdim break; 196218887Sdim 197218887Sdim case Enclosing: 198218887Sdim // Don't report issues in this case, e.g.: "if (x = foo())", 199218887Sdim // where 'x' is unused later. We have yet to see a case where 200218887Sdim // this is a real bug. 201218887Sdim return; 202218887Sdim } 203218887Sdim 204234353Sdim BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R); 205218887Sdim } 206218887Sdim 207226633Sdim void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val, 208218887Sdim DeadStoreKind dsk, 209226633Sdim const LiveVariables::LivenessValues &Live) { 210218887Sdim 211218887Sdim if (!VD->hasLocalStorage()) 212218887Sdim return; 213218887Sdim // Reference types confuse the dead stores checker. Skip them 214218887Sdim // for now. 215218887Sdim if (VD->getType()->getAs<ReferenceType>()) 216218887Sdim return; 217218887Sdim 218243830Sdim if (!isLive(Live, VD) && 219226633Sdim !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) { 220226633Sdim 221226633Sdim PathDiagnosticLocation ExLoc = 222226633Sdim PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); 223226633Sdim Report(VD, dsk, ExLoc, Val->getSourceRange()); 224226633Sdim } 225218887Sdim } 226218887Sdim 227226633Sdim void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk, 228226633Sdim const LiveVariables::LivenessValues& Live) { 229226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 230226633Sdim CheckVarDecl(VD, DR, Val, dsk, Live); 231218887Sdim } 232218887Sdim 233226633Sdim bool isIncrement(VarDecl *VD, const BinaryOperator* B) { 234218887Sdim if (B->isCompoundAssignmentOp()) 235218887Sdim return true; 236218887Sdim 237226633Sdim const Expr *RHS = B->getRHS()->IgnoreParenCasts(); 238226633Sdim const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); 239218887Sdim 240218887Sdim if (!BRHS) 241218887Sdim return false; 242218887Sdim 243226633Sdim const DeclRefExpr *DR; 244218887Sdim 245218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 246218887Sdim if (DR->getDecl() == VD) 247218887Sdim return true; 248218887Sdim 249218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) 250218887Sdim if (DR->getDecl() == VD) 251218887Sdim return true; 252218887Sdim 253218887Sdim return false; 254218887Sdim } 255218887Sdim 256226633Sdim virtual void observeStmt(const Stmt *S, const CFGBlock *block, 257226633Sdim const LiveVariables::LivenessValues &Live) { 258218887Sdim 259218887Sdim currentBlock = block; 260218887Sdim 261218887Sdim // Skip statements in macros. 262218887Sdim if (S->getLocStart().isMacroID()) 263218887Sdim return; 264218887Sdim 265218887Sdim // Only cover dead stores from regular assignments. ++/-- dead stores 266218887Sdim // have never flagged a real bug. 267226633Sdim if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 268218887Sdim if (!B->isAssignmentOp()) return; // Skip non-assignments. 269218887Sdim 270226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) 271218887Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 272218887Sdim // Special case: check for assigning null to a pointer. 273218887Sdim // This is a common form of defensive programming. 274251662Sdim const Expr *RHS = 275251662Sdim LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS()); 276251662Sdim RHS = RHS->IgnoreParenCasts(); 277234353Sdim 278218887Sdim QualType T = VD->getType(); 279218887Sdim if (T->isPointerType() || T->isObjCObjectPointerType()) { 280234353Sdim if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull)) 281218887Sdim return; 282218887Sdim } 283218887Sdim 284218887Sdim // Special case: self-assignments. These are often used to shut up 285218887Sdim // "unused variable" compiler warnings. 286234353Sdim if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS)) 287218887Sdim if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 288218887Sdim return; 289218887Sdim 290218887Sdim // Otherwise, issue a warning. 291218887Sdim DeadStoreKind dsk = Parents.isConsumedExpr(B) 292218887Sdim ? Enclosing 293218887Sdim : (isIncrement(VD,B) ? DeadIncrement : Standard); 294218887Sdim 295226633Sdim CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); 296218887Sdim } 297218887Sdim } 298226633Sdim else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 299218887Sdim if (!U->isIncrementOp() || U->isPrefix()) 300218887Sdim return; 301218887Sdim 302226633Sdim const Stmt *parent = Parents.getParentIgnoreParenCasts(U); 303218887Sdim if (!parent || !isa<ReturnStmt>(parent)) 304218887Sdim return; 305218887Sdim 306226633Sdim const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 307218887Sdim 308226633Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) 309226633Sdim CheckDeclRef(DR, U, DeadIncrement, Live); 310218887Sdim } 311226633Sdim else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) 312218887Sdim // Iterate through the decls. Warn if any initializers are complex 313218887Sdim // expressions that are not live (never used). 314226633Sdim for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); 315218887Sdim DI != DE; ++DI) { 316218887Sdim 317226633Sdim VarDecl *V = dyn_cast<VarDecl>(*DI); 318218887Sdim 319218887Sdim if (!V) 320218887Sdim continue; 321218887Sdim 322218887Sdim if (V->hasLocalStorage()) { 323218887Sdim // Reference types confuse the dead stores checker. Skip them 324218887Sdim // for now. 325218887Sdim if (V->getType()->getAs<ReferenceType>()) 326218887Sdim return; 327218887Sdim 328234353Sdim if (const Expr *E = V->getInit()) { 329234353Sdim while (const ExprWithCleanups *exprClean = 330234353Sdim dyn_cast<ExprWithCleanups>(E)) 331224145Sdim E = exprClean->getSubExpr(); 332224145Sdim 333234353Sdim // Look through transitive assignments, e.g.: 334234353Sdim // int x = y = 0; 335251662Sdim E = LookThroughTransitiveAssignmentsAndCommaOperators(E); 336234353Sdim 337218887Sdim // Don't warn on C++ objects (yet) until we can show that their 338218887Sdim // constructors/destructors don't have side effects. 339218887Sdim if (isa<CXXConstructExpr>(E)) 340218887Sdim return; 341218887Sdim 342218887Sdim // A dead initialization is a variable that is dead after it 343218887Sdim // is initialized. We don't flag warnings for those variables 344218887Sdim // marked 'unused'. 345243830Sdim if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) { 346218887Sdim // Special case: check for initializations with constants. 347218887Sdim // 348218887Sdim // e.g. : int x = 0; 349218887Sdim // 350218887Sdim // If x is EVER assigned a new value later, don't issue 351218887Sdim // a warning. This is because such initialization can be 352218887Sdim // due to defensive programming. 353234353Sdim if (E->isEvaluatable(Ctx)) 354218887Sdim return; 355218887Sdim 356234353Sdim if (const DeclRefExpr *DRE = 357234353Sdim dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) 358234353Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { 359218887Sdim // Special case: check for initialization from constant 360218887Sdim // variables. 361218887Sdim // 362218887Sdim // e.g. extern const int MyConstant; 363218887Sdim // int x = MyConstant; 364218887Sdim // 365218887Sdim if (VD->hasGlobalStorage() && 366218887Sdim VD->getType().isConstQualified()) 367218887Sdim return; 368218887Sdim // Special case: check for initialization from scalar 369218887Sdim // parameters. This is often a form of defensive 370218887Sdim // programming. Non-scalars are still an error since 371218887Sdim // because it more likely represents an actual algorithmic 372218887Sdim // bug. 373218887Sdim if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) 374218887Sdim return; 375218887Sdim } 376218887Sdim 377226633Sdim PathDiagnosticLocation Loc = 378226633Sdim PathDiagnosticLocation::create(V, BR.getSourceManager()); 379226633Sdim Report(V, DeadInit, Loc, E->getSourceRange()); 380218887Sdim } 381218887Sdim } 382218887Sdim } 383218887Sdim } 384218887Sdim } 385218887Sdim}; 386218887Sdim 387218887Sdim} // end anonymous namespace 388218887Sdim 389218887Sdim//===----------------------------------------------------------------------===// 390218887Sdim// Driver function to invoke the Dead-Stores checker on a CFG. 391218887Sdim//===----------------------------------------------------------------------===// 392218887Sdim 393218887Sdimnamespace { 394218887Sdimclass FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{ 395218887Sdim CFG *cfg; 396218887Sdimpublic: 397218887Sdim FindEscaped(CFG *c) : cfg(c) {} 398218887Sdim 399218887Sdim CFG& getCFG() { return *cfg; } 400218887Sdim 401226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 402218887Sdim 403218887Sdim void VisitUnaryOperator(UnaryOperator* U) { 404218887Sdim // Check for '&'. Any VarDecl whose value has its address-taken we 405218887Sdim // treat as escaped. 406226633Sdim Expr *E = U->getSubExpr()->IgnoreParenCasts(); 407218887Sdim if (U->getOpcode() == UO_AddrOf) 408226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 409226633Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 410218887Sdim Escaped.insert(VD); 411218887Sdim return; 412218887Sdim } 413218887Sdim Visit(E); 414218887Sdim } 415218887Sdim}; 416218887Sdim} // end anonymous namespace 417218887Sdim 418218887Sdim 419218887Sdim//===----------------------------------------------------------------------===// 420218887Sdim// DeadStoresChecker 421218887Sdim//===----------------------------------------------------------------------===// 422218887Sdim 423218887Sdimnamespace { 424221345Sdimclass DeadStoresChecker : public Checker<check::ASTCodeBody> { 425218887Sdimpublic: 426218887Sdim void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, 427218887Sdim BugReporter &BR) const { 428249423Sdim 429249423Sdim // Don't do anything for template instantiations. 430249423Sdim // Proving that code in a template instantiation is "dead" 431249423Sdim // means proving that it is dead in all instantiations. 432249423Sdim // This same problem exists with -Wunreachable-code. 433249423Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) 434249423Sdim if (FD->isTemplateInstantiation()) 435249423Sdim return; 436249423Sdim 437226633Sdim if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) { 438218887Sdim CFG &cfg = *mgr.getCFG(D); 439234353Sdim AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D); 440218887Sdim ParentMap &pmap = mgr.getParentMap(D); 441218887Sdim FindEscaped FS(&cfg); 442218887Sdim FS.getCFG().VisitBlockStmts(FS); 443226633Sdim DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped); 444226633Sdim L->runOnAllBlocks(A); 445218887Sdim } 446218887Sdim } 447218887Sdim}; 448218887Sdim} 449218887Sdim 450218887Sdimvoid ento::registerDeadStoresChecker(CheckerManager &mgr) { 451218887Sdim mgr.registerChecker<DeadStoresChecker>(); 452218887Sdim} 453