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 "ClangSACheckers.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/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
  22 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  23 #include "clang/StaticAnalyzer/Core/Checker.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  25 #include "llvm/ADT/BitVector.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<bool> inFinally(inEH, true);
  42     return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S);
  43   }
  44
  45   bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) {
  46     SaveAndRestore<bool> inCatch(inEH, true);
  47     return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S);
  48   }
  49
  50   bool TraverseCXXCatchStmt(CXXCatchStmt *S) {
  51     SaveAndRestore<bool> 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.back();
  92     worklist.pop_back();
  93     llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
  94     if (isReachable)
  95       continue;
  96     isReachable = true;
  97     for (CFGBlock::const_succ_iterator i = block->succ_begin(),
  98                                        e = block->succ_end(); i != e; ++i)
  99       if (const CFGBlock *succ = *i)
 100         worklist.push_back(succ);
 101   }
 102 }
 103
 104 static const Expr *
 105 LookThroughTransitiveAssignmentsAndCommaOperators(const Expr *Ex) {
 106   while (Ex) {
 107     const BinaryOperator *BO =
 108       dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts());
 109     if (!BO)
 110       break;
 111     if (BO->getOpcode() == BO_Assign) {
 112       Ex = BO->getRHS();
 113       continue;
 114     }
 115     if (BO->getOpcode() == BO_Comma) {
 116       Ex = BO->getRHS();
 117       continue;
 118     }
 119     break;
 120   }
 121   return Ex;
 122 }
 123
 124 namespace {
 125 class DeadStoreObs : public LiveVariables::Observer {
 126   const CFG &cfg;
 127   ASTContext &Ctx;
 128   BugReporter& BR;
 129   AnalysisDeclContext* AC;
 130   ParentMap& Parents;
 131   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
 132   OwningPtr<ReachableCode> reachableCode;
 133   const CFGBlock *currentBlock;
 134   OwningPtr<llvm::DenseSet<const VarDecl *> > InEH;
 135
 136   enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
 137
 138 public:
 139   DeadStoreObs(const CFG &cfg, ASTContext &ctx,
 140                BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents,
 141                llvm::SmallPtrSet<const VarDecl*, 20> &escaped)
 142     : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents),
 143       Escaped(escaped), currentBlock(0) {}
 144
 145   virtual ~DeadStoreObs() {}
 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 = 0;
 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       case Standard:
 193         if (!BugType) BugType = "Dead assignment";
 194         os << "Value stored to '" << *V << "' is never read";
 195         break;
 196
 197       case Enclosing:
 198         // Don't report issues in this case, e.g.: "if (x = foo())",
 199         // where 'x' is unused later.  We have yet to see a case where
 200         // this is a real bug.
 201         return;
 202     }
 203
 204     BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R);
 205   }
 206
 207   void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
 208                     DeadStoreKind dsk,
 209                     const LiveVariables::LivenessValues &Live) {
 210
 211     if (!VD->hasLocalStorage())
 212       return;
 213     // Reference types confuse the dead stores checker.  Skip them
 214     // for now.
 215     if (VD->getType()->getAs<ReferenceType>())
 216       return;
 217
 218     if (!isLive(Live, VD) &&
 219         !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) {
 220
 221       PathDiagnosticLocation ExLoc =
 222         PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC);
 223       Report(VD, dsk, ExLoc, Val->getSourceRange());
 224     }
 225   }
 226
 227   void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
 228                     const LiveVariables::LivenessValues& Live) {
 229     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
 230       CheckVarDecl(VD, DR, Val, dsk, Live);
 231   }
 232
 233   bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
 234     if (B->isCompoundAssignmentOp())
 235       return true;
 236
 237     const Expr *RHS = B->getRHS()->IgnoreParenCasts();
 238     const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
 239
 240     if (!BRHS)
 241       return false;
 242
 243     const DeclRefExpr *DR;
 244
 245     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
 246       if (DR->getDecl() == VD)
 247         return true;
 248
 249     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
 250       if (DR->getDecl() == VD)
 251         return true;
 252
 253     return false;
 254   }
 255
 256   virtual void observeStmt(const Stmt *S, const CFGBlock *block,
 257                            const LiveVariables::LivenessValues &Live) {
 258
 259     currentBlock = block;
 260
 261     // Skip statements in macros.
 262     if (S->getLocStart().isMacroID())
 263       return;
 264
 265     // Only cover dead stores from regular assignments.  ++/-- dead stores
 266     // have never flagged a real bug.
 267     if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
 268       if (!B->isAssignmentOp()) return; // Skip non-assignments.
 269
 270       if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
 271         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 272           // Special case: check for assigning null to a pointer.
 273           //  This is a common form of defensive programming.
 274           const Expr *RHS =
 275             LookThroughTransitiveAssignmentsAndCommaOperators(B->getRHS());
 276           RHS = RHS->IgnoreParenCasts();
 277
 278           QualType T = VD->getType();
 279           if (T->isPointerType() || T->isObjCObjectPointerType()) {
 280             if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull))
 281               return;
 282           }
 283
 284           // Special case: self-assignments.  These are often used to shut up
 285           //  "unused variable" compiler warnings.
 286           if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
 287             if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
 288               return;
 289
 290           // Otherwise, issue a warning.
 291           DeadStoreKind dsk = Parents.isConsumedExpr(B)
 292                               ? Enclosing
 293                               : (isIncrement(VD,B) ? DeadIncrement : Standard);
 294
 295           CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
 296         }
 297     }
 298     else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
 299       if (!U->isIncrementOp() || U->isPrefix())
 300         return;
 301
 302       const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
 303       if (!parent || !isa<ReturnStmt>(parent))
 304         return;
 305
 306       const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
 307
 308       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
 309         CheckDeclRef(DR, U, DeadIncrement, Live);
 310     }
 311     else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
 312       // Iterate through the decls.  Warn if any initializers are complex
 313       // expressions that are not live (never used).
 314       for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
 315            DI != DE; ++DI) {
 316
 317         VarDecl *V = dyn_cast<VarDecl>(*DI);
 318
 319         if (!V)
 320           continue;
 321
 322         if (V->hasLocalStorage()) {
 323           // Reference types confuse the dead stores checker.  Skip them
 324           // for now.
 325           if (V->getType()->getAs<ReferenceType>())
 326             return;
 327
 328           if (const Expr *E = V->getInit()) {
 329             while (const ExprWithCleanups *exprClean =
 330                     dyn_cast<ExprWithCleanups>(E))
 331               E = exprClean->getSubExpr();
 332
 333             // Look through transitive assignments, e.g.:
 334             // int x = y = 0;
 335             E = LookThroughTransitiveAssignmentsAndCommaOperators(E);
 336
 337             // Don't warn on C++ objects (yet) until we can show that their
 338             // constructors/destructors don't have side effects.
 339             if (isa<CXXConstructExpr>(E))
 340               return;
 341
 342             // A dead initialization is a variable that is dead after it
 343             // is initialized.  We don't flag warnings for those variables
 344             // marked 'unused'.
 345             if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) {
 346               // Special case: check for initializations with constants.
 347               //
 348               //  e.g. : int x = 0;
 349               //
 350               // If x is EVER assigned a new value later, don't issue
 351               // a warning.  This is because such initialization can be
 352               // due to defensive programming.
 353               if (E->isEvaluatable(Ctx))
 354                 return;
 355
 356               if (const DeclRefExpr *DRE =
 357                   dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
 358                 if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
 359                   // Special case: check for initialization from constant
 360                   //  variables.
 361                   //
 362                   //  e.g. extern const int MyConstant;
 363                   //       int x = MyConstant;
 364                   //
 365                   if (VD->hasGlobalStorage() &&
 366                       VD->getType().isConstQualified())
 367                     return;
 368                   // Special case: check for initialization from scalar
 369                   //  parameters.  This is often a form of defensive
 370                   //  programming.  Non-scalars are still an error since
 371                   //  because it more likely represents an actual algorithmic
 372                   //  bug.
 373                   if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
 374                     return;
 375                 }
 376
 377               PathDiagnosticLocation Loc =
 378                 PathDiagnosticLocation::create(V, BR.getSourceManager());
 379               Report(V, DeadInit, Loc, E->getSourceRange());
 380             }
 381           }
 382         }
 383       }
 384   }
 385 };
 386
 387 } // end anonymous namespace
 388
 389 //===----------------------------------------------------------------------===//
 390 // Driver function to invoke the Dead-Stores checker on a CFG.
 391 //===----------------------------------------------------------------------===//
 392
 393 namespace {
 394 class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
 395   CFG *cfg;
 396 public:
 397   FindEscaped(CFG *c) : cfg(c) {}
 398
 399   CFG& getCFG() { return *cfg; }
 400
 401   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
 402
 403   void VisitUnaryOperator(UnaryOperator* U) {
 404     // Check for '&'.  Any VarDecl whose value has its address-taken we
 405     // treat as escaped.
 406     Expr *E = U->getSubExpr()->IgnoreParenCasts();
 407     if (U->getOpcode() == UO_AddrOf)
 408       if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
 409         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 410           Escaped.insert(VD);
 411           return;
 412         }
 413     Visit(E);
 414   }
 415 };
 416 } // end anonymous namespace
 417
 418
 419 //===----------------------------------------------------------------------===//
 420 // DeadStoresChecker
 421 //===----------------------------------------------------------------------===//
 422
 423 namespace {
 424 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
 425 public:
 426   void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
 427                         BugReporter &BR) const {
 428
 429     // Don't do anything for template instantiations.
 430     // Proving that code in a template instantiation is "dead"
 431     // means proving that it is dead in all instantiations.
 432     // This same problem exists with -Wunreachable-code.
 433     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
 434       if (FD->isTemplateInstantiation())
 435         return;
 436
 437     if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
 438       CFG &cfg = *mgr.getCFG(D);
 439       AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D);
 440       ParentMap &pmap = mgr.getParentMap(D);
 441       FindEscaped FS(&cfg);
 442       FS.getCFG().VisitBlockStmts(FS);
 443       DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped);
 444       L->runOnAllBlocks(A);
 445     }
 446   }
 447 };
 448 }
 449
 450 void ento::registerDeadStoresChecker(CheckerManager &mgr) {
 451   mgr.registerChecker<DeadStoresChecker>();
 452 }