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" 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()); 88263508Sdim 89218887Sdim while (!worklist.empty()) { 90263508Sdim const CFGBlock *block = worklist.pop_back_val(); 91218887Sdim llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; 92218887Sdim if (isReachable) 93218887Sdim continue; 94218887Sdim isReachable = true; 95218887Sdim for (CFGBlock::const_succ_iterator i = block->succ_begin(), 96218887Sdim e = block->succ_end(); i != e; ++i) 97218887Sdim if (const CFGBlock *succ = *i) 98218887Sdim worklist.push_back(succ); 99218887Sdim } 100218887Sdim} 101218887Sdim 102251662Sdimstatic const Expr * 103251662SdimLookThroughTransitiveAssignmentsAndCommaOperators(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 } 113251662Sdim if (BO->getOpcode() == BO_Comma) { 114251662Sdim Ex = BO->getRHS(); 115251662Sdim continue; 116251662Sdim } 117234353Sdim break; 118234353Sdim } 119234353Sdim return Ex; 120234353Sdim} 121234353Sdim 122218887Sdimnamespace { 123226633Sdimclass DeadStoreObs : public LiveVariables::Observer { 124218887Sdim const CFG &cfg; 125218887Sdim ASTContext &Ctx; 126218887Sdim BugReporter& BR; 127234353Sdim AnalysisDeclContext* AC; 128218887Sdim ParentMap& Parents; 129226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 130234353Sdim OwningPtr<ReachableCode> reachableCode; 131218887Sdim const CFGBlock *currentBlock; 132249423Sdim OwningPtr<llvm::DenseSet<const VarDecl *> > InEH; 133218887Sdim 134218887Sdim enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 135218887Sdim 136218887Sdimpublic: 137218887Sdim DeadStoreObs(const CFG &cfg, ASTContext &ctx, 138234353Sdim BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents, 139226633Sdim llvm::SmallPtrSet<const VarDecl*, 20> &escaped) 140226633Sdim : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents), 141218887Sdim Escaped(escaped), currentBlock(0) {} 142218887Sdim 143218887Sdim virtual ~DeadStoreObs() {} 144218887Sdim 145243830Sdim bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) { 146243830Sdim if (Live.isLive(D)) 147243830Sdim return true; 148243830Sdim // Lazily construct the set that records which VarDecls are in 149243830Sdim // EH code. 150243830Sdim if (!InEH.get()) { 151243830Sdim InEH.reset(new llvm::DenseSet<const VarDecl *>()); 152243830Sdim EHCodeVisitor V(*InEH.get()); 153243830Sdim V.TraverseStmt(AC->getBody()); 154243830Sdim } 155243830Sdim // Treat all VarDecls that occur in EH code as being "always live" 156243830Sdim // when considering to suppress dead stores. Frequently stores 157243830Sdim // are followed by reads in EH code, but we don't have the ability 158243830Sdim // to analyze that yet. 159243830Sdim return InEH->count(D); 160243830Sdim } 161243830Sdim 162226633Sdim void Report(const VarDecl *V, DeadStoreKind dsk, 163226633Sdim PathDiagnosticLocation L, SourceRange R) { 164218887Sdim if (Escaped.count(V)) 165218887Sdim return; 166218887Sdim 167218887Sdim // Compute reachable blocks within the CFG for trivial cases 168218887Sdim // where a bogus dead store can be reported because itself is unreachable. 169218887Sdim if (!reachableCode.get()) { 170218887Sdim reachableCode.reset(new ReachableCode(cfg)); 171218887Sdim reachableCode->computeReachableBlocks(); 172218887Sdim } 173218887Sdim 174218887Sdim if (!reachableCode->isReachable(currentBlock)) 175218887Sdim return; 176218887Sdim 177234353Sdim SmallString<64> buf; 178226633Sdim llvm::raw_svector_ostream os(buf); 179226633Sdim const char *BugType = 0; 180218887Sdim 181218887Sdim switch (dsk) { 182218887Sdim case DeadInit: 183218887Sdim BugType = "Dead initialization"; 184226633Sdim os << "Value stored to '" << *V 185226633Sdim << "' during its initialization is never read"; 186218887Sdim break; 187218887Sdim 188218887Sdim case DeadIncrement: 189218887Sdim BugType = "Dead increment"; 190218887Sdim case Standard: 191218887Sdim if (!BugType) BugType = "Dead assignment"; 192226633Sdim os << "Value stored to '" << *V << "' is never read"; 193218887Sdim break; 194218887Sdim 195218887Sdim case Enclosing: 196218887Sdim // Don't report issues in this case, e.g.: "if (x = foo())", 197218887Sdim // where 'x' is unused later. We have yet to see a case where 198218887Sdim // this is a real bug. 199218887Sdim return; 200218887Sdim } 201218887Sdim 202234353Sdim BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R); 203218887Sdim } 204218887Sdim 205226633Sdim void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val, 206218887Sdim DeadStoreKind dsk, 207226633Sdim const LiveVariables::LivenessValues &Live) { 208218887Sdim 209218887Sdim if (!VD->hasLocalStorage()) 210218887Sdim return; 211218887Sdim // Reference types confuse the dead stores checker. Skip them 212218887Sdim // for now. 213218887Sdim if (VD->getType()->getAs<ReferenceType>()) 214218887Sdim return; 215218887Sdim 216243830Sdim if (!isLive(Live, VD) && 217226633Sdim !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) { 218226633Sdim 219226633Sdim PathDiagnosticLocation ExLoc = 220226633Sdim PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); 221226633Sdim Report(VD, dsk, ExLoc, Val->getSourceRange()); 222226633Sdim } 223218887Sdim } 224218887Sdim 225226633Sdim void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk, 226226633Sdim const LiveVariables::LivenessValues& Live) { 227226633Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 228226633Sdim CheckVarDecl(VD, DR, Val, dsk, Live); 229218887Sdim } 230218887Sdim 231226633Sdim bool isIncrement(VarDecl *VD, const BinaryOperator* B) { 232218887Sdim if (B->isCompoundAssignmentOp()) 233218887Sdim return true; 234218887Sdim 235226633Sdim const Expr *RHS = B->getRHS()->IgnoreParenCasts(); 236226633Sdim const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); 237218887Sdim 238218887Sdim if (!BRHS) 239218887Sdim return false; 240218887Sdim 241226633Sdim const DeclRefExpr *DR; 242218887Sdim 243218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 244218887Sdim if (DR->getDecl() == VD) 245218887Sdim return true; 246218887Sdim 247218887Sdim if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) 248218887Sdim if (DR->getDecl() == VD) 249218887Sdim return true; 250218887Sdim 251218887Sdim return false; 252218887Sdim } 253218887Sdim 254226633Sdim virtual void observeStmt(const Stmt *S, const CFGBlock *block, 255226633Sdim const LiveVariables::LivenessValues &Live) { 256218887Sdim 257218887Sdim currentBlock = block; 258218887Sdim 259218887Sdim // Skip statements in macros. 260218887Sdim if (S->getLocStart().isMacroID()) 261218887Sdim return; 262218887Sdim 263218887Sdim // Only cover dead stores from regular assignments. ++/-- dead stores 264218887Sdim // have never flagged a real bug. 265226633Sdim if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 266218887Sdim if (!B->isAssignmentOp()) return; // Skip non-assignments. 267218887Sdim 268226633Sdim if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) 269218887Sdim if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 270218887Sdim // Special case: check for assigning null to a pointer. 271218887Sdim // This is a common form of defensive programming. 272251662Sdim const Expr *RHS = 273251662Sdim LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS()); 274251662Sdim RHS = RHS->IgnoreParenCasts(); 275234353Sdim 276218887Sdim QualType T = VD->getType(); 277218887Sdim if (T->isPointerType() || T->isObjCObjectPointerType()) { 278234353Sdim if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull)) 279218887Sdim return; 280218887Sdim } 281218887Sdim 282218887Sdim // Special case: self-assignments. These are often used to shut up 283218887Sdim // "unused variable" compiler warnings. 284234353Sdim if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS)) 285218887Sdim if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 286218887Sdim return; 287218887Sdim 288218887Sdim // Otherwise, issue a warning. 289218887Sdim DeadStoreKind dsk = Parents.isConsumedExpr(B) 290218887Sdim ? Enclosing 291218887Sdim : (isIncrement(VD,B) ? DeadIncrement : Standard); 292218887Sdim 293226633Sdim CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); 294218887Sdim } 295218887Sdim } 296226633Sdim else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 297218887Sdim if (!U->isIncrementOp() || U->isPrefix()) 298218887Sdim return; 299218887Sdim 300226633Sdim const Stmt *parent = Parents.getParentIgnoreParenCasts(U); 301218887Sdim if (!parent || !isa<ReturnStmt>(parent)) 302218887Sdim return; 303218887Sdim 304226633Sdim const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 305218887Sdim 306226633Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) 307226633Sdim CheckDeclRef(DR, U, DeadIncrement, Live); 308218887Sdim } 309226633Sdim else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) 310218887Sdim // Iterate through the decls. Warn if any initializers are complex 311218887Sdim // expressions that are not live (never used). 312226633Sdim for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); 313218887Sdim DI != DE; ++DI) { 314218887Sdim 315226633Sdim VarDecl *V = dyn_cast<VarDecl>(*DI); 316218887Sdim 317218887Sdim if (!V) 318218887Sdim continue; 319218887Sdim 320218887Sdim if (V->hasLocalStorage()) { 321218887Sdim // Reference types confuse the dead stores checker. Skip them 322218887Sdim // for now. 323218887Sdim if (V->getType()->getAs<ReferenceType>()) 324218887Sdim return; 325218887Sdim 326234353Sdim if (const Expr *E = V->getInit()) { 327234353Sdim while (const ExprWithCleanups *exprClean = 328234353Sdim dyn_cast<ExprWithCleanups>(E)) 329224145Sdim E = exprClean->getSubExpr(); 330224145Sdim 331234353Sdim // Look through transitive assignments, e.g.: 332234353Sdim // int x = y = 0; 333251662Sdim E = LookThroughTransitiveAssignmentsAndCommaOperators(E); 334234353Sdim 335218887Sdim // Don't warn on C++ objects (yet) until we can show that their 336218887Sdim // constructors/destructors don't have side effects. 337218887Sdim if (isa<CXXConstructExpr>(E)) 338218887Sdim return; 339218887Sdim 340218887Sdim // A dead initialization is a variable that is dead after it 341218887Sdim // is initialized. We don't flag warnings for those variables 342218887Sdim // marked 'unused'. 343243830Sdim if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) { 344218887Sdim // Special case: check for initializations with constants. 345218887Sdim // 346218887Sdim // e.g. : int x = 0; 347218887Sdim // 348218887Sdim // If x is EVER assigned a new value later, don't issue 349218887Sdim // a warning. This is because such initialization can be 350218887Sdim // due to defensive programming. 351234353Sdim if (E->isEvaluatable(Ctx)) 352218887Sdim return; 353218887Sdim 354234353Sdim if (const DeclRefExpr *DRE = 355234353Sdim dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) 356234353Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { 357218887Sdim // Special case: check for initialization from constant 358218887Sdim // variables. 359218887Sdim // 360218887Sdim // e.g. extern const int MyConstant; 361218887Sdim // int x = MyConstant; 362218887Sdim // 363218887Sdim if (VD->hasGlobalStorage() && 364218887Sdim VD->getType().isConstQualified()) 365218887Sdim return; 366218887Sdim // Special case: check for initialization from scalar 367218887Sdim // parameters. This is often a form of defensive 368218887Sdim // programming. Non-scalars are still an error since 369218887Sdim // because it more likely represents an actual algorithmic 370218887Sdim // bug. 371218887Sdim if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) 372218887Sdim return; 373218887Sdim } 374218887Sdim 375226633Sdim PathDiagnosticLocation Loc = 376226633Sdim PathDiagnosticLocation::create(V, BR.getSourceManager()); 377226633Sdim Report(V, DeadInit, Loc, E->getSourceRange()); 378218887Sdim } 379218887Sdim } 380218887Sdim } 381218887Sdim } 382218887Sdim } 383218887Sdim}; 384218887Sdim 385218887Sdim} // end anonymous namespace 386218887Sdim 387218887Sdim//===----------------------------------------------------------------------===// 388218887Sdim// Driver function to invoke the Dead-Stores checker on a CFG. 389218887Sdim//===----------------------------------------------------------------------===// 390218887Sdim 391218887Sdimnamespace { 392263508Sdimclass FindEscaped { 393218887Sdimpublic: 394263508Sdim llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 395218887Sdim 396263508Sdim void operator()(const Stmt *S) { 397263508Sdim // Check for '&'. Any VarDecl whose address has been taken we treat as 398263508Sdim // escaped. 399263508Sdim // FIXME: What about references? 400263508Sdim const UnaryOperator *U = dyn_cast<UnaryOperator>(S); 401263508Sdim if (!U) 402263508Sdim return; 403263508Sdim if (U->getOpcode() != UO_AddrOf) 404263508Sdim return; 405218887Sdim 406263508Sdim const Expr *E = U->getSubExpr()->IgnoreParenCasts(); 407263508Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 408263508Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 409263508Sdim Escaped.insert(VD); 410218887Sdim } 411218887Sdim}; 412218887Sdim} // end anonymous namespace 413218887Sdim 414218887Sdim 415218887Sdim//===----------------------------------------------------------------------===// 416218887Sdim// DeadStoresChecker 417218887Sdim//===----------------------------------------------------------------------===// 418218887Sdim 419218887Sdimnamespace { 420221345Sdimclass DeadStoresChecker : public Checker<check::ASTCodeBody> { 421218887Sdimpublic: 422218887Sdim void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, 423218887Sdim BugReporter &BR) const { 424249423Sdim 425249423Sdim // Don't do anything for template instantiations. 426249423Sdim // Proving that code in a template instantiation is "dead" 427249423Sdim // means proving that it is dead in all instantiations. 428249423Sdim // This same problem exists with -Wunreachable-code. 429249423Sdim if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) 430249423Sdim if (FD->isTemplateInstantiation()) 431249423Sdim return; 432249423Sdim 433226633Sdim if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) { 434218887Sdim CFG &cfg = *mgr.getCFG(D); 435234353Sdim AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D); 436218887Sdim ParentMap &pmap = mgr.getParentMap(D); 437263508Sdim FindEscaped FS; 438263508Sdim cfg.VisitBlockStmts(FS); 439226633Sdim DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped); 440226633Sdim L->runOnAllBlocks(A); 441218887Sdim } 442218887Sdim } 443218887Sdim}; 444218887Sdim} 445218887Sdim 446218887Sdimvoid ento::registerDeadStoresChecker(CheckerManager &mgr) { 447218887Sdim mgr.registerChecker<DeadStoresChecker>(); 448218887Sdim} 449