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