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