• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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:
ReachableCode(const CFG & cfg)38   ReachableCode(const CFG &cfg)
39     : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
40 
41   void computeReachableBlocks();
42 
isReachable(const CFGBlock * block) const43   bool isReachable(const CFGBlock *block) const {
44     return reachable[block->getBlockID()];
45   }
46 };
47 }
48 
computeReachableBlocks()49 void ReachableCode::computeReachableBlocks() {
50   if (!cfg.getNumBlockIDs())
51     return;
52 
53   llvm::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::ObserverTy {
72   const CFG &cfg;
73   ASTContext &Ctx;
74   BugReporter& BR;
75   ParentMap& Parents;
76   llvm::SmallPtrSet<VarDecl*, 20> Escaped;
77   llvm::OwningPtr<ReachableCode> reachableCode;
78   const CFGBlock *currentBlock;
79 
80   enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
81 
82 public:
DeadStoreObs(const CFG & cfg,ASTContext & ctx,BugReporter & br,ParentMap & parents,llvm::SmallPtrSet<VarDecl *,20> & escaped)83   DeadStoreObs(const CFG &cfg, ASTContext &ctx,
84                BugReporter& br, ParentMap& parents,
85                llvm::SmallPtrSet<VarDecl*, 20> &escaped)
86     : cfg(cfg), Ctx(ctx), BR(br), Parents(parents),
87       Escaped(escaped), currentBlock(0) {}
88 
~DeadStoreObs()89   virtual ~DeadStoreObs() {}
90 
Report(VarDecl * V,DeadStoreKind dsk,SourceLocation L,SourceRange R)91   void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) {
92     if (Escaped.count(V))
93       return;
94 
95     // Compute reachable blocks within the CFG for trivial cases
96     // where a bogus dead store can be reported because itself is unreachable.
97     if (!reachableCode.get()) {
98       reachableCode.reset(new ReachableCode(cfg));
99       reachableCode->computeReachableBlocks();
100     }
101 
102     if (!reachableCode->isReachable(currentBlock))
103       return;
104 
105     const std::string &name = V->getNameAsString();
106 
107     const char* BugType = 0;
108     std::string msg;
109 
110     switch (dsk) {
111       default:
112         assert(false && "Impossible dead store type.");
113 
114       case DeadInit:
115         BugType = "Dead initialization";
116         msg = "Value stored to '" + name +
117           "' during its initialization is never read";
118         break;
119 
120       case DeadIncrement:
121         BugType = "Dead increment";
122       case Standard:
123         if (!BugType) BugType = "Dead assignment";
124         msg = "Value stored to '" + name + "' is never read";
125         break;
126 
127       case Enclosing:
128         // Don't report issues in this case, e.g.: "if (x = foo())",
129         // where 'x' is unused later.  We have yet to see a case where
130         // this is a real bug.
131         return;
132     }
133 
134     BR.EmitBasicReport(BugType, "Dead store", msg, L, R);
135   }
136 
CheckVarDecl(VarDecl * VD,Expr * Ex,Expr * Val,DeadStoreKind dsk,const LiveVariables::AnalysisDataTy & AD,const LiveVariables::ValTy & Live)137   void CheckVarDecl(VarDecl* VD, Expr* Ex, Expr* Val,
138                     DeadStoreKind dsk,
139                     const LiveVariables::AnalysisDataTy& AD,
140                     const LiveVariables::ValTy& Live) {
141 
142     if (!VD->hasLocalStorage())
143       return;
144     // Reference types confuse the dead stores checker.  Skip them
145     // for now.
146     if (VD->getType()->getAs<ReferenceType>())
147       return;
148 
149     if (!Live(VD, AD) &&
150         !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()))
151       Report(VD, dsk, Ex->getSourceRange().getBegin(),
152              Val->getSourceRange());
153   }
154 
CheckDeclRef(DeclRefExpr * DR,Expr * Val,DeadStoreKind dsk,const LiveVariables::AnalysisDataTy & AD,const LiveVariables::ValTy & Live)155   void CheckDeclRef(DeclRefExpr* DR, Expr* Val, DeadStoreKind dsk,
156                     const LiveVariables::AnalysisDataTy& AD,
157                     const LiveVariables::ValTy& Live) {
158     if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
159       CheckVarDecl(VD, DR, Val, dsk, AD, Live);
160   }
161 
isIncrement(VarDecl * VD,BinaryOperator * B)162   bool isIncrement(VarDecl* VD, BinaryOperator* B) {
163     if (B->isCompoundAssignmentOp())
164       return true;
165 
166     Expr* RHS = B->getRHS()->IgnoreParenCasts();
167     BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
168 
169     if (!BRHS)
170       return false;
171 
172     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 
ObserveStmt(Stmt * S,const CFGBlock * block,const LiveVariables::AnalysisDataTy & AD,const LiveVariables::ValTy & Live)185   virtual void ObserveStmt(Stmt* S, const CFGBlock *block,
186                            const LiveVariables::AnalysisDataTy& AD,
187                            const LiveVariables::ValTy& Live) {
188 
189     currentBlock = block;
190 
191     // Skip statements in macros.
192     if (S->getLocStart().isMacroID())
193       return;
194 
195     // Only cover dead stores from regular assignments.  ++/-- dead stores
196     // have never flagged a real bug.
197     if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
198       if (!B->isAssignmentOp()) return; // Skip non-assignments.
199 
200       if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()))
201         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
202           // Special case: check for assigning null to a pointer.
203           //  This is a common form of defensive programming.
204           QualType T = VD->getType();
205           if (T->isPointerType() || T->isObjCObjectPointerType()) {
206             if (B->getRHS()->isNullPointerConstant(Ctx,
207                                               Expr::NPC_ValueDependentIsNull))
208               return;
209           }
210 
211           Expr* RHS = B->getRHS()->IgnoreParenCasts();
212           // Special case: self-assignments.  These are often used to shut up
213           //  "unused variable" compiler warnings.
214           if (DeclRefExpr* RhsDR = dyn_cast<DeclRefExpr>(RHS))
215             if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
216               return;
217 
218           // Otherwise, issue a warning.
219           DeadStoreKind dsk = Parents.isConsumedExpr(B)
220                               ? Enclosing
221                               : (isIncrement(VD,B) ? DeadIncrement : Standard);
222 
223           CheckVarDecl(VD, DR, B->getRHS(), dsk, AD, Live);
224         }
225     }
226     else if (UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
227       if (!U->isIncrementOp() || U->isPrefix())
228         return;
229 
230       Stmt *parent = Parents.getParentIgnoreParenCasts(U);
231       if (!parent || !isa<ReturnStmt>(parent))
232         return;
233 
234       Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
235 
236       if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex))
237         CheckDeclRef(DR, U, DeadIncrement, AD, Live);
238     }
239     else if (DeclStmt* DS = dyn_cast<DeclStmt>(S))
240       // Iterate through the decls.  Warn if any initializers are complex
241       // expressions that are not live (never used).
242       for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
243            DI != DE; ++DI) {
244 
245         VarDecl* V = dyn_cast<VarDecl>(*DI);
246 
247         if (!V)
248           continue;
249 
250         if (V->hasLocalStorage()) {
251           // Reference types confuse the dead stores checker.  Skip them
252           // for now.
253           if (V->getType()->getAs<ReferenceType>())
254             return;
255 
256           if (Expr* E = V->getInit()) {
257             while (ExprWithCleanups *exprClean = dyn_cast<ExprWithCleanups>(E))
258               E = exprClean->getSubExpr();
259 
260             // Don't warn on C++ objects (yet) until we can show that their
261             // constructors/destructors don't have side effects.
262             if (isa<CXXConstructExpr>(E))
263               return;
264 
265             // A dead initialization is a variable that is dead after it
266             // is initialized.  We don't flag warnings for those variables
267             // marked 'unused'.
268             if (!Live(V, AD) && V->getAttr<UnusedAttr>() == 0) {
269               // Special case: check for initializations with constants.
270               //
271               //  e.g. : int x = 0;
272               //
273               // If x is EVER assigned a new value later, don't issue
274               // a warning.  This is because such initialization can be
275               // due to defensive programming.
276               if (E->isConstantInitializer(Ctx, false))
277                 return;
278 
279               if (DeclRefExpr *DRE=dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
280                 if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
281                   // Special case: check for initialization from constant
282                   //  variables.
283                   //
284                   //  e.g. extern const int MyConstant;
285                   //       int x = MyConstant;
286                   //
287                   if (VD->hasGlobalStorage() &&
288                       VD->getType().isConstQualified())
289                     return;
290                   // Special case: check for initialization from scalar
291                   //  parameters.  This is often a form of defensive
292                   //  programming.  Non-scalars are still an error since
293                   //  because it more likely represents an actual algorithmic
294                   //  bug.
295                   if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
296                     return;
297                 }
298 
299               Report(V, DeadInit, V->getLocation(), 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:
FindEscaped(CFG * c)317   FindEscaped(CFG *c) : cfg(c) {}
318 
getCFG()319   CFG& getCFG() { return *cfg; }
320 
321   llvm::SmallPtrSet<VarDecl*, 20> Escaped;
322 
VisitUnaryOperator(UnaryOperator * U)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:
checkASTCodeBody(const Decl * D,AnalysisManager & mgr,BugReporter & BR) const346   void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
347                         BugReporter &BR) const {
348     if (LiveVariables *L = mgr.getLiveVariables(D)) {
349       CFG &cfg = *mgr.getCFG(D);
350       ParentMap &pmap = mgr.getParentMap(D);
351       FindEscaped FS(&cfg);
352       FS.getCFG().VisitBlockStmts(FS);
353       DeadStoreObs A(cfg, BR.getContext(), BR, pmap, FS.Escaped);
354       L->runOnAllBlocks(cfg, &A);
355     }
356   }
357 };
358 }
359 
registerDeadStoresChecker(CheckerManager & mgr)360 void ento::registerDeadStoresChecker(CheckerManager &mgr) {
361   mgr.registerChecker<DeadStoresChecker>();
362 }
363