xref: /freebsd/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp (revision e32fecd0c2c3ee37c47ee100f169e7eb0282a873)
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 
29 using namespace clang;
30 using namespace ento;
31 
32 namespace {
33 
34 /// A simple visitor to record what VarDecls occur in EH-handling code.
35 class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> {
36 public:
37   bool inEH;
38   llvm::DenseSet<const VarDecl *> &S;
39 
40   bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) {
41     SaveAndRestore<bool> inFinally(inEH, true);
42     return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S);
43   }
44 
45   bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) {
46     SaveAndRestore<bool> inCatch(inEH, true);
47     return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S);
48   }
49 
50   bool TraverseCXXCatchStmt(CXXCatchStmt *S) {
51     SaveAndRestore<bool> 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.
68 class ReachableCode {
69   const CFG &cfg;
70   llvm::BitVector reachable;
71 public:
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 
83 void 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 
103 static const Expr *
104 LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) {
105   while (Ex) {
106     const BinaryOperator *BO =
107       dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts());
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 
120 namespace {
121 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
122 public:
123   bool ShowFixIts = false;
124   bool WarnForDeadNestedAssignments = true;
125 
126   void checkASTCodeBody(const Decl *D, AnalysisManager &Mgr,
127                         BugReporter &BR) const;
128 };
129 
130 class 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 
144 public:
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         LLVM_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           RHS = RHS->IgnoreParenCasts();
336 
337           QualType T = VD->getType();
338           if (T.isVolatileQualified())
339             return;
340           if (T->isPointerType() || T->isObjCObjectPointerType()) {
341             if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
342               return;
343           }
344 
345           // Special case: self-assignments.  These are often used to shut up
346           //  "unused variable" compiler warnings.
347           if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
348             if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
349               return;
350 
351           // Otherwise, issue a warning.
352           DeadStoreKind dsk = Parents.isConsumedExpr(B)
353                               ? Enclosing
354                               : (isIncrement(VD,B) ? DeadIncrement : Standard);
355 
356           CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
357         }
358     }
359     else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
360       if (!U->isIncrementOp() || U->isPrefix())
361         return;
362 
363       const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
364       if (!parent || !isa<ReturnStmt>(parent))
365         return;
366 
367       const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
368 
369       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
370         CheckDeclRef(DR, U, DeadIncrement, Live);
371     }
372     else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
373       // Iterate through the decls.  Warn if any initializers are complex
374       // expressions that are not live (never used).
375       for (const auto *DI : DS->decls()) {
376         const auto *V = dyn_cast<VarDecl>(DI);
377 
378         if (!V)
379           continue;
380 
381         if (V->hasLocalStorage()) {
382           // Reference types confuse the dead stores checker.  Skip them
383           // for now.
384           if (V->getType()->getAs<ReferenceType>())
385             return;
386 
387           if (const Expr *E = V->getInit()) {
388             while (const FullExpr *FE = dyn_cast<FullExpr>(E))
389               E = FE->getSubExpr();
390 
391             // Look through transitive assignments, e.g.:
392             // int x = y = 0;
393             E = LookThroughTransitiveAssignmentsAndCommaOperators(E);
394 
395             // Don't warn on C++ objects (yet) until we can show that their
396             // constructors/destructors don't have side effects.
397             if (isa<CXXConstructExpr>(E))
398               return;
399 
400             // A dead initialization is a variable that is dead after it
401             // is initialized.  We don't flag warnings for those variables
402             // marked 'unused' or 'objc_precise_lifetime'.
403             if (!isLive(Live, V) &&
404                 !V->hasAttr<UnusedAttr>() &&
405                 !V->hasAttr<ObjCPreciseLifetimeAttr>()) {
406               // Special case: check for initializations with constants.
407               //
408               //  e.g. : int x = 0;
409               //         struct A = {0, 1};
410               //         struct B = {{0}, {1, 2}};
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 (isConstant(E))
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 private:
449   /// Return true if the given init list can be interpreted as constant
450   bool isConstant(const InitListExpr *Candidate) const {
451     // We consider init list to be constant if each member of the list can be
452     // interpreted as constant.
453     return llvm::all_of(Candidate->inits(),
454                         [this](const Expr *Init) { return isConstant(Init); });
455   }
456 
457   /// Return true if the given expression can be interpreted as constant
458   bool isConstant(const Expr *E) const {
459     // It looks like E itself is a constant
460     if (E->isEvaluatable(Ctx))
461       return true;
462 
463     // We should also allow defensive initialization of structs, i.e. { 0 }
464     if (const auto *ILE = dyn_cast<InitListExpr>(E->IgnoreParenCasts())) {
465       return isConstant(ILE);
466     }
467 
468     return false;
469   }
470 };
471 
472 } // end anonymous namespace
473 
474 //===----------------------------------------------------------------------===//
475 // Driver function to invoke the Dead-Stores checker on a CFG.
476 //===----------------------------------------------------------------------===//
477 
478 namespace {
479 class FindEscaped {
480 public:
481   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
482 
483   void operator()(const Stmt *S) {
484     // Check for '&'. Any VarDecl whose address has been taken we treat as
485     // escaped.
486     // FIXME: What about references?
487     if (auto *LE = dyn_cast<LambdaExpr>(S)) {
488       findLambdaReferenceCaptures(LE);
489       return;
490     }
491 
492     const UnaryOperator *U = dyn_cast<UnaryOperator>(S);
493     if (!U)
494       return;
495     if (U->getOpcode() != UO_AddrOf)
496       return;
497 
498     const Expr *E = U->getSubExpr()->IgnoreParenCasts();
499     if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
500       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
501         Escaped.insert(VD);
502   }
503 
504   // Treat local variables captured by reference in C++ lambdas as escaped.
505   void findLambdaReferenceCaptures(const LambdaExpr *LE)  {
506     const CXXRecordDecl *LambdaClass = LE->getLambdaClass();
507     llvm::DenseMap<const VarDecl *, FieldDecl *> CaptureFields;
508     FieldDecl *ThisCaptureField;
509     LambdaClass->getCaptureFields(CaptureFields, ThisCaptureField);
510 
511     for (const LambdaCapture &C : LE->captures()) {
512       if (!C.capturesVariable())
513         continue;
514 
515       VarDecl *VD = C.getCapturedVar();
516       const FieldDecl *FD = CaptureFields[VD];
517       if (!FD)
518         continue;
519 
520       // If the capture field is a reference type, it is capture-by-reference.
521       if (FD->getType()->isReferenceType())
522         Escaped.insert(VD);
523     }
524   }
525 };
526 } // end anonymous namespace
527 
528 
529 //===----------------------------------------------------------------------===//
530 // DeadStoresChecker
531 //===----------------------------------------------------------------------===//
532 
533 void DeadStoresChecker::checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
534                                          BugReporter &BR) const {
535 
536   // Don't do anything for template instantiations.
537   // Proving that code in a template instantiation is "dead"
538   // means proving that it is dead in all instantiations.
539   // This same problem exists with -Wunreachable-code.
540   if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
541     if (FD->isTemplateInstantiation())
542       return;
543 
544   if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
545     CFG &cfg = *mgr.getCFG(D);
546     AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
547     ParentMap &pmap = mgr.getParentMap(D);
548     FindEscaped FS;
549     cfg.VisitBlockStmts(FS);
550     DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped,
551                    WarnForDeadNestedAssignments);
552     L->runOnAllBlocks(A);
553   }
554 }
555 
556 void ento::registerDeadStoresChecker(CheckerManager &Mgr) {
557   auto *Chk = Mgr.registerChecker<DeadStoresChecker>();
558 
559   const AnalyzerOptions &AnOpts = Mgr.getAnalyzerOptions();
560   Chk->WarnForDeadNestedAssignments =
561       AnOpts.getCheckerBooleanOption(Chk, "WarnForDeadNestedAssignments");
562   Chk->ShowFixIts =
563       AnOpts.getCheckerBooleanOption(Chk, "ShowFixIts");
564 }
565 
566 bool ento::shouldRegisterDeadStoresChecker(const CheckerManager &mgr) {
567   return true;
568 }
569