xref: /freebsd/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp (revision 7fdf597e96a02165cfe22ff357b857d5fa15ed8a)
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 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.
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 
97     for (const CFGBlock *succ : block->succs())
98       if (succ)
99         worklist.push_back(succ);
100   }
101 }
102 
103 static const Expr *
104 LookThroughTransitiveAssignmentsAndCommaOperators(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 
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.starts_with("/* 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 
446 private:
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 
477 namespace {
478 class FindEscaped {
479 public:
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 
532 void 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 
555 void 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 
565 bool ento::shouldRegisterDeadStoresChecker(const CheckerManager &mgr) {
566   return true;
567 }
568