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/Lex/Lexer.h"
15#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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
28using namespace clang;
29using namespace ento;
30
31namespace {
32
33/// A simple visitor to record what VarDecls occur in EH-handling code.
34class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> {
35public:
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.
67class ReachableCode {
68  const CFG &cfg;
69  llvm::BitVector reachable;
70public:
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
82void 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
102static const Expr *
103LookThroughTransitiveAssignmentsAndCommaOperators(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
122namespace {
123class DeadStoresChecker : public Checker<check::ASTCodeBody> {
124public:
125  bool ShowFixIts = false;
126  bool WarnForDeadNestedAssignments = true;
127
128  void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
129                        BugReporter &BR) const;
130};
131
132class DeadStoreObs : public LiveVariables::Observer {
133  const CFG &cfg;
134  ASTContext &Ctx;
135  BugReporter& BR;
136  const DeadStoresChecker *Checker;
137  AnalysisDeclContext* AC;
138  ParentMap& Parents;
139  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
140  std::unique_ptr<ReachableCode> reachableCode;
141  const CFGBlock *currentBlock;
142  std::unique_ptr<llvm::DenseSet<const VarDecl *>> InEH;
143
144  enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
145
146public:
147  DeadStoreObs(const CFG &cfg, ASTContext &ctx, BugReporter &br,
148               const DeadStoresChecker *checker, AnalysisDeclContext *ac,
149               ParentMap &parents,
150               llvm::SmallPtrSet<const VarDecl *, 20> &escaped,
151               bool warnForDeadNestedAssignments)
152      : cfg(cfg), Ctx(ctx), BR(br), Checker(checker), AC(ac), Parents(parents),
153        Escaped(escaped), currentBlock(nullptr) {}
154
155  ~DeadStoreObs() override {}
156
157  bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) {
158    if (Live.isLive(D))
159      return true;
160    // Lazily construct the set that records which VarDecls are in
161    // EH code.
162    if (!InEH.get()) {
163      InEH.reset(new llvm::DenseSet<const VarDecl *>());
164      EHCodeVisitor V(*InEH.get());
165      V.TraverseStmt(AC->getBody());
166    }
167    // Treat all VarDecls that occur in EH code as being "always live"
168    // when considering to suppress dead stores.  Frequently stores
169    // are followed by reads in EH code, but we don't have the ability
170    // to analyze that yet.
171    return InEH->count(D);
172  }
173
174  bool isSuppressed(SourceRange R) {
175    SourceManager &SMgr = Ctx.getSourceManager();
176    SourceLocation Loc = R.getBegin();
177    if (!Loc.isValid())
178      return false;
179
180    FileID FID = SMgr.getFileID(Loc);
181    bool Invalid = false;
182    StringRef Data = SMgr.getBufferData(FID, &Invalid);
183    if (Invalid)
184      return false;
185
186    // Files autogenerated by DriverKit IIG contain some dead stores that
187    // we don't want to report.
188    if (Data.startswith("/* iig"))
189      return true;
190
191    return false;
192  }
193
194  void Report(const VarDecl *V, DeadStoreKind dsk,
195              PathDiagnosticLocation L, SourceRange R) {
196    if (Escaped.count(V))
197      return;
198
199    // Compute reachable blocks within the CFG for trivial cases
200    // where a bogus dead store can be reported because itself is unreachable.
201    if (!reachableCode.get()) {
202      reachableCode.reset(new ReachableCode(cfg));
203      reachableCode->computeReachableBlocks();
204    }
205
206    if (!reachableCode->isReachable(currentBlock))
207      return;
208
209    if (isSuppressed(R))
210      return;
211
212    SmallString<64> buf;
213    llvm::raw_svector_ostream os(buf);
214    const char *BugType = nullptr;
215
216    SmallVector<FixItHint, 1> Fixits;
217
218    switch (dsk) {
219      case DeadInit: {
220        BugType = "Dead initialization";
221        os << "Value stored to '" << *V
222           << "' during its initialization is never read";
223
224        ASTContext &ACtx = V->getASTContext();
225        if (Checker->ShowFixIts) {
226          if (V->getInit()->HasSideEffects(ACtx,
227                                           /*IncludePossibleEffects=*/true)) {
228            break;
229          }
230          SourceManager &SM = ACtx.getSourceManager();
231          const LangOptions &LO = ACtx.getLangOpts();
232          SourceLocation L1 =
233              Lexer::findNextToken(
234                  V->getTypeSourceInfo()->getTypeLoc().getEndLoc(),
235                  SM, LO)->getEndLoc();
236          SourceLocation L2 =
237              Lexer::getLocForEndOfToken(V->getInit()->getEndLoc(), 1, SM, LO);
238          Fixits.push_back(FixItHint::CreateRemoval({L1, L2}));
239        }
240        break;
241      }
242
243      case DeadIncrement:
244        BugType = "Dead increment";
245        LLVM_FALLTHROUGH;
246      case Standard:
247        if (!BugType) BugType = "Dead assignment";
248        os << "Value stored to '" << *V << "' is never read";
249        break;
250
251      // eg.: f((x = foo()))
252      case Enclosing:
253        if (!Checker->WarnForDeadNestedAssignments)
254          return;
255        BugType = "Dead nested assignment";
256        os << "Although the value stored to '" << *V
257           << "' is used in the enclosing expression, the value is never "
258              "actually read from '"
259           << *V << "'";
260        break;
261    }
262
263    BR.EmitBasicReport(AC->getDecl(), Checker, BugType, "Dead store", os.str(),
264                       L, R, Fixits);
265  }
266
267  void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
268                    DeadStoreKind dsk,
269                    const LiveVariables::LivenessValues &Live) {
270
271    if (!VD->hasLocalStorage())
272      return;
273    // Reference types confuse the dead stores checker.  Skip them
274    // for now.
275    if (VD->getType()->getAs<ReferenceType>())
276      return;
277
278    if (!isLive(Live, VD) &&
279        !(VD->hasAttr<UnusedAttr>() || VD->hasAttr<BlocksAttr>() ||
280          VD->hasAttr<ObjCPreciseLifetimeAttr>())) {
281
282      PathDiagnosticLocation ExLoc =
283        PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC);
284      Report(VD, dsk, ExLoc, Val->getSourceRange());
285    }
286  }
287
288  void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
289                    const LiveVariables::LivenessValues& Live) {
290    if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
291      CheckVarDecl(VD, DR, Val, dsk, Live);
292  }
293
294  bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
295    if (B->isCompoundAssignmentOp())
296      return true;
297
298    const Expr *RHS = B->getRHS()->IgnoreParenCasts();
299    const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
300
301    if (!BRHS)
302      return false;
303
304    const DeclRefExpr *DR;
305
306    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
307      if (DR->getDecl() == VD)
308        return true;
309
310    if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
311      if (DR->getDecl() == VD)
312        return true;
313
314    return false;
315  }
316
317  void observeStmt(const Stmt *S, const CFGBlock *block,
318                   const LiveVariables::LivenessValues &Live) override {
319
320    currentBlock = block;
321
322    // Skip statements in macros.
323    if (S->getBeginLoc().isMacroID())
324      return;
325
326    // Only cover dead stores from regular assignments.  ++/-- dead stores
327    // have never flagged a real bug.
328    if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
329      if (!B->isAssignmentOp()) return; // Skip non-assignments.
330
331      if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
332        if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
333          // Special case: check for assigning null to a pointer.
334          //  This is a common form of defensive programming.
335          const Expr *RHS =
336            LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS());
337          RHS = RHS->IgnoreParenCasts();
338
339          QualType T = VD->getType();
340          if (T.isVolatileQualified())
341            return;
342          if (T->isPointerType() || T->isObjCObjectPointerType()) {
343            if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
344              return;
345          }
346
347          // Special case: self-assignments.  These are often used to shut up
348          //  "unused variable" compiler warnings.
349          if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
350            if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
351              return;
352
353          // Otherwise, issue a warning.
354          DeadStoreKind dsk = Parents.isConsumedExpr(B)
355                              ? Enclosing
356                              : (isIncrement(VD,B) ? DeadIncrement : Standard);
357
358          CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
359        }
360    }
361    else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
362      if (!U->isIncrementOp() || U->isPrefix())
363        return;
364
365      const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
366      if (!parent || !isa<ReturnStmt>(parent))
367        return;
368
369      const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
370
371      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
372        CheckDeclRef(DR, U, DeadIncrement, Live);
373    }
374    else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
375      // Iterate through the decls.  Warn if any initializers are complex
376      // expressions that are not live (never used).
377      for (const auto *DI : DS->decls()) {
378        const auto *V = dyn_cast<VarDecl>(DI);
379
380        if (!V)
381          continue;
382
383        if (V->hasLocalStorage()) {
384          // Reference types confuse the dead stores checker.  Skip them
385          // for now.
386          if (V->getType()->getAs<ReferenceType>())
387            return;
388
389          if (const Expr *E = V->getInit()) {
390            while (const FullExpr *FE = dyn_cast<FullExpr>(E))
391              E = FE->getSubExpr();
392
393            // Look through transitive assignments, e.g.:
394            // int x = y = 0;
395            E = LookThroughTransitiveAssignmentsAndCommaOperators(E);
396
397            // Don't warn on C++ objects (yet) until we can show that their
398            // constructors/destructors don't have side effects.
399            if (isa<CXXConstructExpr>(E))
400              return;
401
402            // A dead initialization is a variable that is dead after it
403            // is initialized.  We don't flag warnings for those variables
404            // marked 'unused' or 'objc_precise_lifetime'.
405            if (!isLive(Live, V) &&
406                !V->hasAttr<UnusedAttr>() &&
407                !V->hasAttr<ObjCPreciseLifetimeAttr>()) {
408              // Special case: check for initializations with constants.
409              //
410              //  e.g. : int x = 0;
411              //
412              // If x is EVER assigned a new value later, don't issue
413              // a warning.  This is because such initialization can be
414              // due to defensive programming.
415              if (E->isEvaluatable(Ctx))
416                return;
417
418              if (const DeclRefExpr *DRE =
419                  dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
420                if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
421                  // Special case: check for initialization from constant
422                  //  variables.
423                  //
424                  //  e.g. extern const int MyConstant;
425                  //       int x = MyConstant;
426                  //
427                  if (VD->hasGlobalStorage() &&
428                      VD->getType().isConstQualified())
429                    return;
430                  // Special case: check for initialization from scalar
431                  //  parameters.  This is often a form of defensive
432                  //  programming.  Non-scalars are still an error since
433                  //  because it more likely represents an actual algorithmic
434                  //  bug.
435                  if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
436                    return;
437                }
438
439              PathDiagnosticLocation Loc =
440                PathDiagnosticLocation::create(V, BR.getSourceManager());
441              Report(V, DeadInit, Loc, E->getSourceRange());
442            }
443          }
444        }
445      }
446  }
447};
448
449} // end anonymous namespace
450
451//===----------------------------------------------------------------------===//
452// Driver function to invoke the Dead-Stores checker on a CFG.
453//===----------------------------------------------------------------------===//
454
455namespace {
456class FindEscaped {
457public:
458  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
459
460  void operator()(const Stmt *S) {
461    // Check for '&'. Any VarDecl whose address has been taken we treat as
462    // escaped.
463    // FIXME: What about references?
464    if (auto *LE = dyn_cast<LambdaExpr>(S)) {
465      findLambdaReferenceCaptures(LE);
466      return;
467    }
468
469    const UnaryOperator *U = dyn_cast<UnaryOperator>(S);
470    if (!U)
471      return;
472    if (U->getOpcode() != UO_AddrOf)
473      return;
474
475    const Expr *E = U->getSubExpr()->IgnoreParenCasts();
476    if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
477      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
478        Escaped.insert(VD);
479  }
480
481  // Treat local variables captured by reference in C++ lambdas as escaped.
482  void findLambdaReferenceCaptures(const LambdaExpr *LE)  {
483    const CXXRecordDecl *LambdaClass = LE->getLambdaClass();
484    llvm::DenseMap<const VarDecl *, FieldDecl *> CaptureFields;
485    FieldDecl *ThisCaptureField;
486    LambdaClass->getCaptureFields(CaptureFields, ThisCaptureField);
487
488    for (const LambdaCapture &C : LE->captures()) {
489      if (!C.capturesVariable())
490        continue;
491
492      VarDecl *VD = C.getCapturedVar();
493      const FieldDecl *FD = CaptureFields[VD];
494      if (!FD)
495        continue;
496
497      // If the capture field is a reference type, it is capture-by-reference.
498      if (FD->getType()->isReferenceType())
499        Escaped.insert(VD);
500    }
501  }
502};
503} // end anonymous namespace
504
505
506//===----------------------------------------------------------------------===//
507// DeadStoresChecker
508//===----------------------------------------------------------------------===//
509
510void DeadStoresChecker::checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
511                                         BugReporter &BR) const {
512
513  // Don't do anything for template instantiations.
514  // Proving that code in a template instantiation is "dead"
515  // means proving that it is dead in all instantiations.
516  // This same problem exists with -Wunreachable-code.
517  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
518    if (FD->isTemplateInstantiation())
519      return;
520
521  if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
522    CFG &cfg = *mgr.getCFG(D);
523    AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
524    ParentMap &pmap = mgr.getParentMap(D);
525    FindEscaped FS;
526    cfg.VisitBlockStmts(FS);
527    DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped,
528                   WarnForDeadNestedAssignments);
529    L->runOnAllBlocks(A);
530  }
531}
532
533void ento::registerDeadStoresChecker(CheckerManager &Mgr) {
534  auto *Chk = Mgr.registerChecker<DeadStoresChecker>();
535
536  const AnalyzerOptions &AnOpts = Mgr.getAnalyzerOptions();
537  Chk->WarnForDeadNestedAssignments =
538      AnOpts.getCheckerBooleanOption(Chk, "WarnForDeadNestedAssignments");
539  Chk->ShowFixIts =
540      AnOpts.getCheckerBooleanOption(Chk, "ShowFixIts");
541}
542
543bool ento::shouldRegisterDeadStoresChecker(const LangOptions &LO) {
544  return true;
545}
546