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