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