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