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