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