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