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/StaticAnalyzer/Core/Checker.h"
  17 #include "clang/Analysis/Analyses/LiveVariables.h"
  18 #include "clang/Analysis/Visitors/CFGRecStmtVisitor.h"
  19 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  21 #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
  22 #include "clang/Basic/Diagnostic.h"
  23 #include "clang/AST/ASTContext.h"
  24 #include "clang/AST/ParentMap.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26
  27 using namespace clang;
  28 using namespace ento;
  29
  30 namespace {
  31
  32 // FIXME: Eventually migrate into its own file, and have it managed by
  33 // AnalysisManager.
  34 class ReachableCode {
  35   const CFG &cfg;
  36   llvm::BitVector reachable;
  37 public:
  38   ReachableCode(const CFG &cfg)
  39     : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {}
  40
  41   void computeReachableBlocks();
  42
  43   bool isReachable(const CFGBlock *block) const {
  44     return reachable[block->getBlockID()];
  45   }
  46 };
  47 }
  48
  49 void ReachableCode::computeReachableBlocks() {
  50   if (!cfg.getNumBlockIDs())
  51     return;
  52
  53   SmallVector<const CFGBlock*, 10> worklist;
  54   worklist.push_back(&cfg.getEntry());
  55
  56   while (!worklist.empty()) {
  57     const CFGBlock *block = worklist.back();
  58     worklist.pop_back();
  59     llvm::BitVector::reference isReachable = reachable[block->getBlockID()];
  60     if (isReachable)
  61       continue;
  62     isReachable = true;
  63     for (CFGBlock::const_succ_iterator i = block->succ_begin(),
  64                                        e = block->succ_end(); i != e; ++i)
  65       if (const CFGBlock *succ = *i)
  66         worklist.push_back(succ);
  67   }
  68 }
  69
  70 namespace {
  71 class DeadStoreObs : public LiveVariables::Observer {
  72   const CFG &cfg;
  73   ASTContext &Ctx;
  74   BugReporter& BR;
  75   AnalysisContext* AC;
  76   ParentMap& Parents;
  77   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
  78   llvm::OwningPtr<ReachableCode> reachableCode;
  79   const CFGBlock *currentBlock;
  80
  81   enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
  82
  83 public:
  84   DeadStoreObs(const CFG &cfg, ASTContext &ctx,
  85                BugReporter& br, AnalysisContext* ac, ParentMap& parents,
  86                llvm::SmallPtrSet<const VarDecl*, 20> &escaped)
  87     : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents),
  88       Escaped(escaped), currentBlock(0) {}
  89
  90   virtual ~DeadStoreObs() {}
  91
  92   void Report(const VarDecl *V, DeadStoreKind dsk,
  93               PathDiagnosticLocation L, SourceRange R) {
  94     if (Escaped.count(V))
  95       return;
  96
  97     // Compute reachable blocks within the CFG for trivial cases
  98     // where a bogus dead store can be reported because itself is unreachable.
  99     if (!reachableCode.get()) {
 100       reachableCode.reset(new ReachableCode(cfg));
 101       reachableCode->computeReachableBlocks();
 102     }
 103
 104     if (!reachableCode->isReachable(currentBlock))
 105       return;
 106
 107     llvm::SmallString<64> buf;
 108     llvm::raw_svector_ostream os(buf);
 109     const char *BugType = 0;
 110
 111     switch (dsk) {
 112       default:
 113         llvm_unreachable("Impossible dead store type.");
 114
 115       case DeadInit:
 116         BugType = "Dead initialization";
 117         os << "Value stored to '" << *V
 118            << "' during its initialization is never read";
 119         break;
 120
 121       case DeadIncrement:
 122         BugType = "Dead increment";
 123       case Standard:
 124         if (!BugType) BugType = "Dead assignment";
 125         os << "Value stored to '" << *V << "' is never read";
 126         break;
 127
 128       case Enclosing:
 129         // Don't report issues in this case, e.g.: "if (x = foo())",
 130         // where 'x' is unused later.  We have yet to see a case where
 131         // this is a real bug.
 132         return;
 133     }
 134
 135     BR.EmitBasicReport(BugType, "Dead store", os.str(), L, R);
 136   }
 137
 138   void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val,
 139                     DeadStoreKind dsk,
 140                     const LiveVariables::LivenessValues &Live) {
 141
 142     if (!VD->hasLocalStorage())
 143       return;
 144     // Reference types confuse the dead stores checker.  Skip them
 145     // for now.
 146     if (VD->getType()->getAs<ReferenceType>())
 147       return;
 148
 149     if (!Live.isLive(VD) &&
 150         !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) {
 151
 152       PathDiagnosticLocation ExLoc =
 153         PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC);
 154       Report(VD, dsk, ExLoc, Val->getSourceRange());
 155     }
 156   }
 157
 158   void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk,
 159                     const LiveVariables::LivenessValues& Live) {
 160     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
 161       CheckVarDecl(VD, DR, Val, dsk, Live);
 162   }
 163
 164   bool isIncrement(VarDecl *VD, const BinaryOperator* B) {
 165     if (B->isCompoundAssignmentOp())
 166       return true;
 167
 168     const Expr *RHS = B->getRHS()->IgnoreParenCasts();
 169     const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
 170
 171     if (!BRHS)
 172       return false;
 173
 174     const DeclRefExpr *DR;
 175
 176     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
 177       if (DR->getDecl() == VD)
 178         return true;
 179
 180     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
 181       if (DR->getDecl() == VD)
 182         return true;
 183
 184     return false;
 185   }
 186
 187   virtual void observeStmt(const Stmt *S, const CFGBlock *block,
 188                            const LiveVariables::LivenessValues &Live) {
 189
 190     currentBlock = block;
 191
 192     // Skip statements in macros.
 193     if (S->getLocStart().isMacroID())
 194       return;
 195
 196     // Only cover dead stores from regular assignments.  ++/-- dead stores
 197     // have never flagged a real bug.
 198     if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
 199       if (!B->isAssignmentOp()) return; // Skip non-assignments.
 200
 201       if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS()))
 202         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 203           // Special case: check for assigning null to a pointer.
 204           //  This is a common form of defensive programming.
 205           QualType T = VD->getType();
 206           if (T->isPointerType() || T->isObjCObjectPointerType()) {
 207             if (B->getRHS()->isNullPointerConstant(Ctx,
 208                                               Expr::NPC_ValueDependentIsNull))
 209               return;
 210           }
 211
 212           Expr *RHS = B->getRHS()->IgnoreParenCasts();
 213           // Special case: self-assignments.  These are often used to shut up
 214           //  "unused variable" compiler warnings.
 215           if (DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS))
 216             if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
 217               return;
 218
 219           // Otherwise, issue a warning.
 220           DeadStoreKind dsk = Parents.isConsumedExpr(B)
 221                               ? Enclosing
 222                               : (isIncrement(VD,B) ? DeadIncrement : Standard);
 223
 224           CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
 225         }
 226     }
 227     else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
 228       if (!U->isIncrementOp() || U->isPrefix())
 229         return;
 230
 231       const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
 232       if (!parent || !isa<ReturnStmt>(parent))
 233         return;
 234
 235       const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
 236
 237       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex))
 238         CheckDeclRef(DR, U, DeadIncrement, Live);
 239     }
 240     else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
 241       // Iterate through the decls.  Warn if any initializers are complex
 242       // expressions that are not live (never used).
 243       for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
 244            DI != DE; ++DI) {
 245
 246         VarDecl *V = dyn_cast<VarDecl>(*DI);
 247
 248         if (!V)
 249           continue;
 250
 251         if (V->hasLocalStorage()) {
 252           // Reference types confuse the dead stores checker.  Skip them
 253           // for now.
 254           if (V->getType()->getAs<ReferenceType>())
 255             return;
 256
 257           if (Expr *E = V->getInit()) {
 258             while (ExprWithCleanups *exprClean = dyn_cast<ExprWithCleanups>(E))
 259               E = exprClean->getSubExpr();
 260
 261             // Don't warn on C++ objects (yet) until we can show that their
 262             // constructors/destructors don't have side effects.
 263             if (isa<CXXConstructExpr>(E))
 264               return;
 265
 266             // A dead initialization is a variable that is dead after it
 267             // is initialized.  We don't flag warnings for those variables
 268             // marked 'unused'.
 269             if (!Live.isLive(V) && V->getAttr<UnusedAttr>() == 0) {
 270               // Special case: check for initializations with constants.
 271               //
 272               //  e.g. : int x = 0;
 273               //
 274               // If x is EVER assigned a new value later, don't issue
 275               // a warning.  This is because such initialization can be
 276               // due to defensive programming.
 277               if (E->isConstantInitializer(Ctx, false))
 278                 return;
 279
 280               if (DeclRefExpr *DRE=dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
 281                 if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
 282                   // Special case: check for initialization from constant
 283                   //  variables.
 284                   //
 285                   //  e.g. extern const int MyConstant;
 286                   //       int x = MyConstant;
 287                   //
 288                   if (VD->hasGlobalStorage() &&
 289                       VD->getType().isConstQualified())
 290                     return;
 291                   // Special case: check for initialization from scalar
 292                   //  parameters.  This is often a form of defensive
 293                   //  programming.  Non-scalars are still an error since
 294                   //  because it more likely represents an actual algorithmic
 295                   //  bug.
 296                   if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
 297                     return;
 298                 }
 299
 300               PathDiagnosticLocation Loc =
 301                 PathDiagnosticLocation::create(V, BR.getSourceManager());
 302               Report(V, DeadInit, Loc, E->getSourceRange());
 303             }
 304           }
 305         }
 306       }
 307   }
 308 };
 309
 310 } // end anonymous namespace
 311
 312 //===----------------------------------------------------------------------===//
 313 // Driver function to invoke the Dead-Stores checker on a CFG.
 314 //===----------------------------------------------------------------------===//
 315
 316 namespace {
 317 class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
 318   CFG *cfg;
 319 public:
 320   FindEscaped(CFG *c) : cfg(c) {}
 321
 322   CFG& getCFG() { return *cfg; }
 323
 324   llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
 325
 326   void VisitUnaryOperator(UnaryOperator* U) {
 327     // Check for '&'.  Any VarDecl whose value has its address-taken we
 328     // treat as escaped.
 329     Expr *E = U->getSubExpr()->IgnoreParenCasts();
 330     if (U->getOpcode() == UO_AddrOf)
 331       if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
 332         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 333           Escaped.insert(VD);
 334           return;
 335         }
 336     Visit(E);
 337   }
 338 };
 339 } // end anonymous namespace
 340
 341
 342 //===----------------------------------------------------------------------===//
 343 // DeadStoresChecker
 344 //===----------------------------------------------------------------------===//
 345
 346 namespace {
 347 class DeadStoresChecker : public Checker<check::ASTCodeBody> {
 348 public:
 349   void checkASTCodeBody(const Decl *D, AnalysisManager& mgr,
 350                         BugReporter &BR) const {
 351     if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) {
 352       CFG &cfg = *mgr.getCFG(D);
 353       AnalysisContext *AC = mgr.getAnalysisContext(D);
 354       ParentMap &pmap = mgr.getParentMap(D);
 355       FindEscaped FS(&cfg);
 356       FS.getCFG().VisitBlockStmts(FS);
 357       DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped);
 358       L->runOnAllBlocks(A);
 359     }
 360   }
 361 };
 362 }
 363
 364 void ento::registerDeadStoresChecker(CheckerManager &mgr) {
 365   mgr.registerChecker<DeadStoresChecker>();
 366 }