1 //==- DeadStoresChecker.cpp - Check for stores to dead variables -*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a DeadStores, a flow-sensitive checker that looks for
11 // stores to variables that are no longer live.
13 //===----------------------------------------------------------------------===//
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"
29 using namespace clang;
34 /// A simple visitor to record what VarDecls occur in EH-handling code.
35 class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> {
38 llvm::DenseSet<const VarDecl *> &S;
40 bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) {
41 SaveAndRestore<bool> inFinally(inEH, true);
42 return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S);
45 bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) {
46 SaveAndRestore<bool> inCatch(inEH, true);
47 return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S);
50 bool TraverseCXXCatchStmt(CXXCatchStmt *S) {
51 SaveAndRestore<bool> inCatch(inEH, true);
52 return TraverseStmt(S->getHandlerBlock());
55 bool VisitDeclRefExpr(DeclRefExpr *DR) {
57 if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
62 EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) :
66 // FIXME: Eventually migrate into its own file, and have it managed by
70 llvm::BitVector reachable;
72 ReachableCode(const CFG &cfg)
73 : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
75 void computeReachableBlocks();
77 bool isReachable(const CFGBlock *block) const {
78 return reachable[block->getBlockID()];
83 void ReachableCode::computeReachableBlocks() {
84 if (!cfg.getNumBlockIDs())
87 SmallVector<const CFGBlock*, 10> worklist;
88 worklist.push_back(&cfg.getEntry());
90 while (!worklist.empty()) {
91 const CFGBlock *block = worklist.back();
93 llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
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);
105 LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) {
107 const BinaryOperator *BO =
108 dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts());
111 if (BO->getOpcode() == BO_Assign) {
115 if (BO->getOpcode() == BO_Comma) {
125 class DeadStoreObs : public LiveVariables::Observer {
129 AnalysisDeclContext* AC;
131 llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
132 OwningPtr<ReachableCode> reachableCode;
133 const CFGBlock *currentBlock;
134 OwningPtr<llvm::DenseSet<const VarDecl *> > InEH;
136 enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
139 DeadStoreObs(const CFG &cfg, ASTContext &ctx,
140 BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents,
141 llvm::SmallPtrSet<const VarDecl*, 20> &escaped)
142 : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents),
143 Escaped(escaped), currentBlock(0) {}
145 virtual ~DeadStoreObs() {}
147 bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) {
150 // Lazily construct the set that records which VarDecls are in
153 InEH.reset(new llvm::DenseSet<const VarDecl *>());
154 EHCodeVisitor V(*InEH.get());
155 V.TraverseStmt(AC->getBody());
157 // Treat all VarDecls that occur in EH code as being "always live"
158 // when considering to suppress dead stores. Frequently stores
159 // are followed by reads in EH code, but we don't have the ability
160 // to analyze that yet.
161 return InEH->count(D);
164 void Report(const VarDecl *V, DeadStoreKind dsk,
165 PathDiagnosticLocation L, SourceRange R) {
166 if (Escaped.count(V))
169 // Compute reachable blocks within the CFG for trivial cases
170 // where a bogus dead store can be reported because itself is unreachable.
171 if (!reachableCode.get()) {
172 reachableCode.reset(new ReachableCode(cfg));
173 reachableCode->computeReachableBlocks();
176 if (!reachableCode->isReachable(currentBlock))
180 llvm::raw_svector_ostream os(buf);
181 const char *BugType = 0;
185 BugType = "Dead initialization";
186 os << "Value stored to '" << *V
187 << "' during its initialization is never read";
191 BugType = "Dead increment";
193 if (!BugType) BugType = "Dead assignment";
194 os << "Value stored to '" << *V << "' is never read";
198 // Don't report issues in this case, e.g.: "if (x = foo())",
199 // where 'x' is unused later. We have yet to see a case where
200 // this is a real bug.
204 BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R);
207 void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
209 const LiveVariables::LivenessValues &Live) {
211 if (!VD->hasLocalStorage())
213 // Reference types confuse the dead stores checker. Skip them
215 if (VD->getType()->getAs<ReferenceType>())
218 if (!isLive(Live, VD) &&
219 !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) {
221 PathDiagnosticLocation ExLoc =
222 PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC);
223 Report(VD, dsk, ExLoc, Val->getSourceRange());
227 void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
228 const LiveVariables::LivenessValues& Live) {
229 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
230 CheckVarDecl(VD, DR, Val, dsk, Live);
233 bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
234 if (B->isCompoundAssignmentOp())
237 const Expr *RHS = B->getRHS()->IgnoreParenCasts();
238 const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
243 const DeclRefExpr *DR;
245 if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
246 if (DR->getDecl() == VD)
249 if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
250 if (DR->getDecl() == VD)
256 virtual void observeStmt(const Stmt *S, const CFGBlock *block,
257 const LiveVariables::LivenessValues &Live) {
259 currentBlock = block;
261 // Skip statements in macros.
262 if (S->getLocStart().isMacroID())
265 // Only cover dead stores from regular assignments. ++/-- dead stores
266 // have never flagged a real bug.
267 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
268 if (!B->isAssignmentOp()) return; // Skip non-assignments.
270 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
271 if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
272 // Special case: check for assigning null to a pointer.
273 // This is a common form of defensive programming.
275 LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS());
276 RHS = RHS->IgnoreParenCasts();
278 QualType T = VD->getType();
279 if (T->isPointerType() || T->isObjCObjectPointerType()) {
280 if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
284 // Special case: self-assignments. These are often used to shut up
285 // "unused variable" compiler warnings.
286 if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
287 if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
290 // Otherwise, issue a warning.
291 DeadStoreKind dsk = Parents.isConsumedExpr(B)
293 : (isIncrement(VD,B) ? DeadIncrement : Standard);
295 CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
298 else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
299 if (!U->isIncrementOp() || U->isPrefix())
302 const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
303 if (!parent || !isa<ReturnStmt>(parent))
306 const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
308 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
309 CheckDeclRef(DR, U, DeadIncrement, Live);
311 else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
312 // Iterate through the decls. Warn if any initializers are complex
313 // expressions that are not live (never used).
314 for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
317 VarDecl *V = dyn_cast<VarDecl>(*DI);
322 if (V->hasLocalStorage()) {
323 // Reference types confuse the dead stores checker. Skip them
325 if (V->getType()->getAs<ReferenceType>())
328 if (const Expr *E = V->getInit()) {
329 while (const ExprWithCleanups *exprClean =
330 dyn_cast<ExprWithCleanups>(E))
331 E = exprClean->getSubExpr();
333 // Look through transitive assignments, e.g.:
335 E = LookThroughTransitiveAssignmentsAndCommaOperators(E);
337 // Don't warn on C++ objects (yet) until we can show that their
338 // constructors/destructors don't have side effects.
339 if (isa<CXXConstructExpr>(E))
342 // A dead initialization is a variable that is dead after it
343 // is initialized. We don't flag warnings for those variables
345 if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) {
346 // Special case: check for initializations with constants.
350 // If x is EVER assigned a new value later, don't issue
351 // a warning. This is because such initialization can be
352 // due to defensive programming.
353 if (E->isEvaluatable(Ctx))
356 if (const DeclRefExpr *DRE =
357 dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
358 if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
359 // Special case: check for initialization from constant
362 // e.g. extern const int MyConstant;
363 // int x = MyConstant;
365 if (VD->hasGlobalStorage() &&
366 VD->getType().isConstQualified())
368 // Special case: check for initialization from scalar
369 // parameters. This is often a form of defensive
370 // programming. Non-scalars are still an error since
371 // because it more likely represents an actual algorithmic
373 if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
377 PathDiagnosticLocation Loc =
378 PathDiagnosticLocation::create(V, BR.getSourceManager());
379 Report(V, DeadInit, Loc, E->getSourceRange());
387 } // end anonymous namespace
389 //===----------------------------------------------------------------------===//
390 // Driver function to invoke the Dead-Stores checker on a CFG.
391 //===----------------------------------------------------------------------===//
394 class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
397 FindEscaped(CFG *c) : cfg(c) {}
399 CFG& getCFG() { return *cfg; }
401 llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
403 void VisitUnaryOperator(UnaryOperator* U) {
404 // Check for '&'. Any VarDecl whose value has its address-taken we
406 Expr *E = U->getSubExpr()->IgnoreParenCasts();
407 if (U->getOpcode() == UO_AddrOf)
408 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
409 if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
416 } // end anonymous namespace
419 //===----------------------------------------------------------------------===//
421 //===----------------------------------------------------------------------===//
424 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
426 void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
427 BugReporter &BR) const {
429 // Don't do anything for template instantiations.
430 // Proving that code in a template instantiation is "dead"
431 // means proving that it is dead in all instantiations.
432 // This same problem exists with -Wunreachable-code.
433 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
434 if (FD->isTemplateInstantiation())
437 if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
438 CFG &cfg = *mgr.getCFG(D);
439 AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
440 ParentMap &pmap = mgr.getParentMap(D);
441 FindEscaped FS(&cfg);
442 FS.getCFG().VisitBlockStmts(FS);
443 DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped);
444 L->runOnAllBlocks(A);
450 void ento::registerDeadStoresChecker(CheckerManager &mgr) {
451 mgr.registerChecker<DeadStoresChecker>();