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