DeadStoresChecker.cpp revision 9ed6d8068f767819951bc4eebf6f4912087c442a
1//==- DeadStoresChecker.cpp - Check for stores to dead variables -*- C++ -*-==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines a DeadStores, a flow-sensitive checker that looks for 11// stores to variables that are no longer live. 12// 13//===----------------------------------------------------------------------===// 14 15#include "ClangSACheckers.h" 16#include "clang/AST/ASTContext.h" 17#include "clang/AST/Attr.h" 18#include "clang/AST/ParentMap.h" 19#include "clang/AST/RecursiveASTVisitor.h" 20#include "clang/Analysis/Analyses/LiveVariables.h" 21#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 22#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 23#include "clang/StaticAnalyzer/Core/Checker.h" 24#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 25#include "llvm/ADT/BitVector.h" 26#include "llvm/ADT/SmallString.h" 27#include "llvm/Support/SaveAndRestore.h" 28 29using namespace clang; 30using namespace ento; 31 32namespace { 33 34/// A simple visitor to record what VarDecls occur in EH-handling code. 35class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> { 36public: 37 bool inEH; 38 llvm::DenseSet<const VarDecl *> &S; 39 40 bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) { 41 SaveAndRestore<bool> inFinally(inEH, true); 42 return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S); 43 } 44 45 bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) { 46 SaveAndRestore<bool> inCatch(inEH, true); 47 return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S); 48 } 49 50 bool TraverseCXXCatchStmt(CXXCatchStmt *S) { 51 SaveAndRestore<bool> inCatch(inEH, true); 52 return TraverseStmt(S->getHandlerBlock()); 53 } 54 55 bool VisitDeclRefExpr(DeclRefExpr *DR) { 56 if (inEH) 57 if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 58 S.insert(D); 59 return true; 60 } 61 62 EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) : 63 inEH(false), S(S) {} 64}; 65 66// FIXME: Eventually migrate into its own file, and have it managed by 67// AnalysisManager. 68class ReachableCode { 69 const CFG &cfg; 70 llvm::BitVector reachable; 71public: 72 ReachableCode(const CFG &cfg) 73 : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {} 74 75 void computeReachableBlocks(); 76 77 bool isReachable(const CFGBlock *block) const { 78 return reachable[block->getBlockID()]; 79 } 80}; 81} 82 83void ReachableCode::computeReachableBlocks() { 84 if (!cfg.getNumBlockIDs()) 85 return; 86 87 SmallVector<const CFGBlock*, 10> worklist; 88 worklist.push_back(&cfg.getEntry()); 89 90 while (!worklist.empty()) { 91 const CFGBlock *block = worklist.back(); 92 worklist.pop_back(); 93 llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; 94 if (isReachable) 95 continue; 96 isReachable = true; 97 for (CFGBlock::const_succ_iterator i = block->succ_begin(), 98 e = block->succ_end(); i != e; ++i) 99 if (const CFGBlock *succ = *i) 100 worklist.push_back(succ); 101 } 102} 103 104static const Expr * 105LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) { 106 while (Ex) { 107 const BinaryOperator *BO = 108 dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts()); 109 if (!BO) 110 break; 111 if (BO->getOpcode() == BO_Assign) { 112 Ex = BO->getRHS(); 113 continue; 114 } 115 if (BO->getOpcode() == BO_Comma) { 116 Ex = BO->getRHS(); 117 continue; 118 } 119 break; 120 } 121 return Ex; 122} 123 124namespace { 125class DeadStoreObs : public LiveVariables::Observer { 126 const CFG &cfg; 127 ASTContext &Ctx; 128 BugReporter& BR; 129 AnalysisDeclContext* AC; 130 ParentMap& Parents; 131 llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 132 OwningPtr<ReachableCode> reachableCode; 133 const CFGBlock *currentBlock; 134 OwningPtr<llvm::DenseSet<const VarDecl *> > InEH; 135 136 enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; 137 138public: 139 DeadStoreObs(const CFG &cfg, ASTContext &ctx, 140 BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents, 141 llvm::SmallPtrSet<const VarDecl*, 20> &escaped) 142 : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents), 143 Escaped(escaped), currentBlock(0) {} 144 145 virtual ~DeadStoreObs() {} 146 147 bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) { 148 if (Live.isLive(D)) 149 return true; 150 // Lazily construct the set that records which VarDecls are in 151 // EH code. 152 if (!InEH.get()) { 153 InEH.reset(new llvm::DenseSet<const VarDecl *>()); 154 EHCodeVisitor V(*InEH.get()); 155 V.TraverseStmt(AC->getBody()); 156 } 157 // Treat all VarDecls that occur in EH code as being "always live" 158 // when considering to suppress dead stores. Frequently stores 159 // are followed by reads in EH code, but we don't have the ability 160 // to analyze that yet. 161 return InEH->count(D); 162 } 163 164 void Report(const VarDecl *V, DeadStoreKind dsk, 165 PathDiagnosticLocation L, SourceRange R) { 166 if (Escaped.count(V)) 167 return; 168 169 // Compute reachable blocks within the CFG for trivial cases 170 // where a bogus dead store can be reported because itself is unreachable. 171 if (!reachableCode.get()) { 172 reachableCode.reset(new ReachableCode(cfg)); 173 reachableCode->computeReachableBlocks(); 174 } 175 176 if (!reachableCode->isReachable(currentBlock)) 177 return; 178 179 SmallString<64> buf; 180 llvm::raw_svector_ostream os(buf); 181 const char *BugType = 0; 182 183 switch (dsk) { 184 case DeadInit: 185 BugType = "Dead initialization"; 186 os << "Value stored to '" << *V 187 << "' during its initialization is never read"; 188 break; 189 190 case DeadIncrement: 191 BugType = "Dead increment"; 192 case Standard: 193 if (!BugType) BugType = "Dead assignment"; 194 os << "Value stored to '" << *V << "' is never read"; 195 break; 196 197 case Enclosing: 198 // Don't report issues in this case, e.g.: "if (x = foo())", 199 // where 'x' is unused later. We have yet to see a case where 200 // this is a real bug. 201 return; 202 } 203 204 BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R); 205 } 206 207 void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val, 208 DeadStoreKind dsk, 209 const LiveVariables::LivenessValues &Live) { 210 211 if (!VD->hasLocalStorage()) 212 return; 213 // Reference types confuse the dead stores checker. Skip them 214 // for now. 215 if (VD->getType()->getAs<ReferenceType>()) 216 return; 217 218 if (!isLive(Live, VD) && 219 !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) { 220 221 PathDiagnosticLocation ExLoc = 222 PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); 223 Report(VD, dsk, ExLoc, Val->getSourceRange()); 224 } 225 } 226 227 void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk, 228 const LiveVariables::LivenessValues& Live) { 229 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 230 CheckVarDecl(VD, DR, Val, dsk, Live); 231 } 232 233 bool isIncrement(VarDecl *VD, const BinaryOperator* B) { 234 if (B->isCompoundAssignmentOp()) 235 return true; 236 237 const Expr *RHS = B->getRHS()->IgnoreParenCasts(); 238 const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); 239 240 if (!BRHS) 241 return false; 242 243 const DeclRefExpr *DR; 244 245 if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) 246 if (DR->getDecl() == VD) 247 return true; 248 249 if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) 250 if (DR->getDecl() == VD) 251 return true; 252 253 return false; 254 } 255 256 virtual void observeStmt(const Stmt *S, const CFGBlock *block, 257 const LiveVariables::LivenessValues &Live) { 258 259 currentBlock = block; 260 261 // Skip statements in macros. 262 if (S->getLocStart().isMacroID()) 263 return; 264 265 // Only cover dead stores from regular assignments. ++/-- dead stores 266 // have never flagged a real bug. 267 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 268 if (!B->isAssignmentOp()) return; // Skip non-assignments. 269 270 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) 271 if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 272 // Special case: check for assigning null to a pointer. 273 // This is a common form of defensive programming. 274 const Expr *RHS = 275 LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS()); 276 RHS = RHS->IgnoreParenCasts(); 277 278 QualType T = VD->getType(); 279 if (T->isPointerType() || T->isObjCObjectPointerType()) { 280 if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull)) 281 return; 282 } 283 284 // Special case: self-assignments. These are often used to shut up 285 // "unused variable" compiler warnings. 286 if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS)) 287 if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) 288 return; 289 290 // Otherwise, issue a warning. 291 DeadStoreKind dsk = Parents.isConsumedExpr(B) 292 ? Enclosing 293 : (isIncrement(VD,B) ? DeadIncrement : Standard); 294 295 CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); 296 } 297 } 298 else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { 299 if (!U->isIncrementOp() || U->isPrefix()) 300 return; 301 302 const Stmt *parent = Parents.getParentIgnoreParenCasts(U); 303 if (!parent || !isa<ReturnStmt>(parent)) 304 return; 305 306 const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); 307 308 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) 309 CheckDeclRef(DR, U, DeadIncrement, Live); 310 } 311 else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) 312 // Iterate through the decls. Warn if any initializers are complex 313 // expressions that are not live (never used). 314 for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); 315 DI != DE; ++DI) { 316 317 VarDecl *V = dyn_cast<VarDecl>(*DI); 318 319 if (!V) 320 continue; 321 322 if (V->hasLocalStorage()) { 323 // Reference types confuse the dead stores checker. Skip them 324 // for now. 325 if (V->getType()->getAs<ReferenceType>()) 326 return; 327 328 if (const Expr *E = V->getInit()) { 329 while (const ExprWithCleanups *exprClean = 330 dyn_cast<ExprWithCleanups>(E)) 331 E = exprClean->getSubExpr(); 332 333 // Look through transitive assignments, e.g.: 334 // int x = y = 0; 335 E = LookThroughTransitiveAssignmentsAndCommaOperators(E); 336 337 // Don't warn on C++ objects (yet) until we can show that their 338 // constructors/destructors don't have side effects. 339 if (isa<CXXConstructExpr>(E)) 340 return; 341 342 // A dead initialization is a variable that is dead after it 343 // is initialized. We don't flag warnings for those variables 344 // marked 'unused'. 345 if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) { 346 // Special case: check for initializations with constants. 347 // 348 // e.g. : int x = 0; 349 // 350 // If x is EVER assigned a new value later, don't issue 351 // a warning. This is because such initialization can be 352 // due to defensive programming. 353 if (E->isEvaluatable(Ctx)) 354 return; 355 356 if (const DeclRefExpr *DRE = 357 dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) 358 if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { 359 // Special case: check for initialization from constant 360 // variables. 361 // 362 // e.g. extern const int MyConstant; 363 // int x = MyConstant; 364 // 365 if (VD->hasGlobalStorage() && 366 VD->getType().isConstQualified()) 367 return; 368 // Special case: check for initialization from scalar 369 // parameters. This is often a form of defensive 370 // programming. Non-scalars are still an error since 371 // because it more likely represents an actual algorithmic 372 // bug. 373 if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) 374 return; 375 } 376 377 PathDiagnosticLocation Loc = 378 PathDiagnosticLocation::create(V, BR.getSourceManager()); 379 Report(V, DeadInit, Loc, E->getSourceRange()); 380 } 381 } 382 } 383 } 384 } 385}; 386 387} // end anonymous namespace 388 389//===----------------------------------------------------------------------===// 390// Driver function to invoke the Dead-Stores checker on a CFG. 391//===----------------------------------------------------------------------===// 392 393namespace { 394class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{ 395 CFG *cfg; 396public: 397 FindEscaped(CFG *c) : cfg(c) {} 398 399 CFG& getCFG() { return *cfg; } 400 401 llvm::SmallPtrSet<const VarDecl*, 20> Escaped; 402 403 void VisitUnaryOperator(UnaryOperator* U) { 404 // Check for '&'. Any VarDecl whose value has its address-taken we 405 // treat as escaped. 406 Expr *E = U->getSubExpr()->IgnoreParenCasts(); 407 if (U->getOpcode() == UO_AddrOf) 408 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 409 if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 410 Escaped.insert(VD); 411 return; 412 } 413 Visit(E); 414 } 415}; 416} // end anonymous namespace 417 418 419//===----------------------------------------------------------------------===// 420// DeadStoresChecker 421//===----------------------------------------------------------------------===// 422 423namespace { 424class DeadStoresChecker : public Checker<check::ASTCodeBody> { 425public: 426 void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, 427 BugReporter &BR) const { 428 429 // Don't do anything for template instantiations. 430 // Proving that code in a template instantiation is "dead" 431 // means proving that it is dead in all instantiations. 432 // This same problem exists with -Wunreachable-code. 433 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) 434 if (FD->isTemplateInstantiation()) 435 return; 436 437 if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) { 438 CFG &cfg = *mgr.getCFG(D); 439 AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D); 440 ParentMap &pmap = mgr.getParentMap(D); 441 FindEscaped FS(&cfg); 442 FS.getCFG().VisitBlockStmts(FS); 443 DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped); 444 L->runOnAllBlocks(A); 445 } 446 } 447}; 448} 449 450void ento::registerDeadStoresChecker(CheckerManager &mgr) { 451 mgr.registerChecker<DeadStoresChecker>(); 452} 453