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