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