contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp

   1 //==- DeadStoresChecker.cpp - Check for stores to dead variables -*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines a DeadStores, a flow-sensitive checker that looks for
  11 //  stores to variables that are no longer live.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  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 DeadStoreObs : public LiveVariables::Observer {
 124   const CFG &cfg;
 125   ASTContext &Ctx;
 126   BugReporter& BR;
 127   const CheckerBase *Checker;
 128   AnalysisDeclContext* AC;
 129   ParentMap& Parents;
 130   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
 131   std::unique_ptr<ReachableCode> reachableCode;
 132   const CFGBlock *currentBlock;
 133   std::unique_ptr<llvm::DenseSet<const VarDecl *>> InEH;
 134
 135   enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
 136
 137 public:
 138   DeadStoreObs(const CFG &cfg, ASTContext &ctx, BugReporter &br,
 139                const CheckerBase *checker, AnalysisDeclContext *ac,
 140                ParentMap &parents,
 141                llvm::SmallPtrSet<const VarDecl *, 20> &escaped)
 142       : cfg(cfg), Ctx(ctx), BR(br), Checker(checker), AC(ac), Parents(parents),
 143         Escaped(escaped), currentBlock(nullptr) {}
 144
 145   ~DeadStoreObs() override {}
 146
 147   bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) {
 148     if (Live.isLive(D))
 149       return true;
 150     // Lazily construct the set that records which VarDecls are in
 151     // EH code.
 152     if (!InEH.get()) {
 153       InEH.reset(new llvm::DenseSet<const VarDecl *>());
 154       EHCodeVisitor V(*InEH.get());
 155       V.TraverseStmt(AC->getBody());
 156     }
 157     // Treat all VarDecls that occur in EH code as being "always live"
 158     // when considering to suppress dead stores.  Frequently stores
 159     // are followed by reads in EH code, but we don't have the ability
 160     // to analyze that yet.
 161     return InEH->count(D);
 162   }
 163
 164   void Report(const VarDecl *V, DeadStoreKind dsk,
 165               PathDiagnosticLocation L, SourceRange R) {
 166     if (Escaped.count(V))
 167       return;
 168
 169     // Compute reachable blocks within the CFG for trivial cases
 170     // where a bogus dead store can be reported because itself is unreachable.
 171     if (!reachableCode.get()) {
 172       reachableCode.reset(new ReachableCode(cfg));
 173       reachableCode->computeReachableBlocks();
 174     }
 175
 176     if (!reachableCode->isReachable(currentBlock))
 177       return;
 178
 179     SmallString<64> buf;
 180     llvm::raw_svector_ostream os(buf);
 181     const char *BugType = nullptr;
 182
 183     switch (dsk) {
 184       case DeadInit:
 185         BugType = "Dead initialization";
 186         os << "Value stored to '" << *V
 187            << "' during its initialization is never read";
 188         break;
 189
 190       case DeadIncrement:
 191         BugType = "Dead increment";
 192         LLVM_FALLTHROUGH;
 193       case Standard:
 194         if (!BugType) BugType = "Dead assignment";
 195         os << "Value stored to '" << *V << "' is never read";
 196         break;
 197
 198       case Enclosing:
 199         // Don't report issues in this case, e.g.: "if (x = foo())",
 200         // where 'x' is unused later.  We have yet to see a case where
 201         // this is a real bug.
 202         return;
 203     }
 204
 205     BR.EmitBasicReport(AC->getDecl(), Checker, BugType, "Dead store", os.str(),
 206                        L, R);
 207   }
 208
 209   void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
 210                     DeadStoreKind dsk,
 211                     const LiveVariables::LivenessValues &Live) {
 212
 213     if (!VD->hasLocalStorage())
 214       return;
 215     // Reference types confuse the dead stores checker.  Skip them
 216     // for now.
 217     if (VD->getType()->getAs<ReferenceType>())
 218       return;
 219
 220     if (!isLive(Live, VD) &&
 221         !(VD->hasAttr<UnusedAttr>() || VD->hasAttr<BlocksAttr>() ||
 222           VD->hasAttr<ObjCPreciseLifetimeAttr>())) {
 223
 224       PathDiagnosticLocation ExLoc =
 225         PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC);
 226       Report(VD, dsk, ExLoc, Val->getSourceRange());
 227     }
 228   }
 229
 230   void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
 231                     const LiveVariables::LivenessValues& Live) {
 232     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
 233       CheckVarDecl(VD, DR, Val, dsk, Live);
 234   }
 235
 236   bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
 237     if (B->isCompoundAssignmentOp())
 238       return true;
 239
 240     const Expr *RHS = B->getRHS()->IgnoreParenCasts();
 241     const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
 242
 243     if (!BRHS)
 244       return false;
 245
 246     const DeclRefExpr *DR;
 247
 248     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
 249       if (DR->getDecl() == VD)
 250         return true;
 251
 252     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
 253       if (DR->getDecl() == VD)
 254         return true;
 255
 256     return false;
 257   }
 258
 259   void observeStmt(const Stmt *S, const CFGBlock *block,
 260                    const LiveVariables::LivenessValues &Live) override {
 261
 262     currentBlock = block;
 263
 264     // Skip statements in macros.
 265     if (S->getBeginLoc().isMacroID())
 266       return;
 267
 268     // Only cover dead stores from regular assignments.  ++/-- dead stores
 269     // have never flagged a real bug.
 270     if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
 271       if (!B->isAssignmentOp()) return; // Skip non-assignments.
 272
 273       if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
 274         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 275           // Special case: check for assigning null to a pointer.
 276           //  This is a common form of defensive programming.
 277           const Expr *RHS =
 278             LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS());
 279           RHS = RHS->IgnoreParenCasts();
 280
 281           QualType T = VD->getType();
 282           if (T.isVolatileQualified())
 283             return;
 284           if (T->isPointerType() || T->isObjCObjectPointerType()) {
 285             if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
 286               return;
 287           }
 288
 289           // Special case: self-assignments.  These are often used to shut up
 290           //  "unused variable" compiler warnings.
 291           if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
 292             if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
 293               return;
 294
 295           // Otherwise, issue a warning.
 296           DeadStoreKind dsk = Parents.isConsumedExpr(B)
 297                               ? Enclosing
 298                               : (isIncrement(VD,B) ? DeadIncrement : Standard);
 299
 300           CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
 301         }
 302     }
 303     else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
 304       if (!U->isIncrementOp() || U->isPrefix())
 305         return;
 306
 307       const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
 308       if (!parent || !isa<ReturnStmt>(parent))
 309         return;
 310
 311       const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
 312
 313       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
 314         CheckDeclRef(DR, U, DeadIncrement, Live);
 315     }
 316     else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
 317       // Iterate through the decls.  Warn if any initializers are complex
 318       // expressions that are not live (never used).
 319       for (const auto *DI : DS->decls()) {
 320         const auto *V = dyn_cast<VarDecl>(DI);
 321
 322         if (!V)
 323           continue;
 324
 325         if (V->hasLocalStorage()) {
 326           // Reference types confuse the dead stores checker.  Skip them
 327           // for now.
 328           if (V->getType()->getAs<ReferenceType>())
 329             return;
 330
 331           if (const Expr *E = V->getInit()) {
 332             while (const FullExpr *FE = dyn_cast<FullExpr>(E))
 333               E = FE->getSubExpr();
 334
 335             // Look through transitive assignments, e.g.:
 336             // int x = y = 0;
 337             E = LookThroughTransitiveAssignmentsAndCommaOperators(E);
 338
 339             // Don't warn on C++ objects (yet) until we can show that their
 340             // constructors/destructors don't have side effects.
 341             if (isa<CXXConstructExpr>(E))
 342               return;
 343
 344             // A dead initialization is a variable that is dead after it
 345             // is initialized.  We don't flag warnings for those variables
 346             // marked 'unused' or 'objc_precise_lifetime'.
 347             if (!isLive(Live, V) &&
 348                 !V->hasAttr<UnusedAttr>() &&
 349                 !V->hasAttr<ObjCPreciseLifetimeAttr>()) {
 350               // Special case: check for initializations with constants.
 351               //
 352               //  e.g. : int x = 0;
 353               //
 354               // If x is EVER assigned a new value later, don't issue
 355               // a warning.  This is because such initialization can be
 356               // due to defensive programming.
 357               if (E->isEvaluatable(Ctx))
 358                 return;
 359
 360               if (const DeclRefExpr *DRE =
 361                   dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
 362                 if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
 363                   // Special case: check for initialization from constant
 364                   //  variables.
 365                   //
 366                   //  e.g. extern const int MyConstant;
 367                   //       int x = MyConstant;
 368                   //
 369                   if (VD->hasGlobalStorage() &&
 370                       VD->getType().isConstQualified())
 371                     return;
 372                   // Special case: check for initialization from scalar
 373                   //  parameters.  This is often a form of defensive
 374                   //  programming.  Non-scalars are still an error since
 375                   //  because it more likely represents an actual algorithmic
 376                   //  bug.
 377                   if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
 378                     return;
 379                 }
 380
 381               PathDiagnosticLocation Loc =
 382                 PathDiagnosticLocation::create(V, BR.getSourceManager());
 383               Report(V, DeadInit, Loc, E->getSourceRange());
 384             }
 385           }
 386         }
 387       }
 388   }
 389 };
 390
 391 } // end anonymous namespace
 392
 393 //===----------------------------------------------------------------------===//
 394 // Driver function to invoke the Dead-Stores checker on a CFG.
 395 //===----------------------------------------------------------------------===//
 396
 397 namespace {
 398 class FindEscaped {
 399 public:
 400   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
 401
 402   void operator()(const Stmt *S) {
 403     // Check for '&'. Any VarDecl whose address has been taken we treat as
 404     // escaped.
 405     // FIXME: What about references?
 406     if (auto *LE = dyn_cast<LambdaExpr>(S)) {
 407       findLambdaReferenceCaptures(LE);
 408       return;
 409     }
 410
 411     const UnaryOperator *U = dyn_cast<UnaryOperator>(S);
 412     if (!U)
 413       return;
 414     if (U->getOpcode() != UO_AddrOf)
 415       return;
 416
 417     const Expr *E = U->getSubExpr()->IgnoreParenCasts();
 418     if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
 419       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
 420         Escaped.insert(VD);
 421   }
 422
 423   // Treat local variables captured by reference in C++ lambdas as escaped.
 424   void findLambdaReferenceCaptures(const LambdaExpr *LE)  {
 425     const CXXRecordDecl *LambdaClass = LE->getLambdaClass();
 426     llvm::DenseMap<const VarDecl *, FieldDecl *> CaptureFields;
 427     FieldDecl *ThisCaptureField;
 428     LambdaClass->getCaptureFields(CaptureFields, ThisCaptureField);
 429
 430     for (const LambdaCapture &C : LE->captures()) {
 431       if (!C.capturesVariable())
 432         continue;
 433
 434       VarDecl *VD = C.getCapturedVar();
 435       const FieldDecl *FD = CaptureFields[VD];
 436       if (!FD)
 437         continue;
 438
 439       // If the capture field is a reference type, it is capture-by-reference.
 440       if (FD->getType()->isReferenceType())
 441         Escaped.insert(VD);
 442     }
 443   }
 444 };
 445 } // end anonymous namespace
 446
 447
 448 //===----------------------------------------------------------------------===//
 449 // DeadStoresChecker
 450 //===----------------------------------------------------------------------===//
 451
 452 namespace {
 453 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
 454 public:
 455   void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
 456                         BugReporter &BR) const {
 457
 458     // Don't do anything for template instantiations.
 459     // Proving that code in a template instantiation is "dead"
 460     // means proving that it is dead in all instantiations.
 461     // This same problem exists with -Wunreachable-code.
 462     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
 463       if (FD->isTemplateInstantiation())
 464         return;
 465
 466     if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
 467       CFG &cfg = *mgr.getCFG(D);
 468       AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
 469       ParentMap &pmap = mgr.getParentMap(D);
 470       FindEscaped FS;
 471       cfg.VisitBlockStmts(FS);
 472       DeadStoreObs A(cfg, BR.getContext(), BR, this, AC, pmap, FS.Escaped);
 473       L->runOnAllBlocks(A);
 474     }
 475   }
 476 };
 477 }
 478
 479 void ento::registerDeadStoresChecker(CheckerManager &mgr) {
 480   mgr.registerChecker<DeadStoresChecker>();
 481 }