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