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/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.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
 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 }