Clang Project

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