lib/Checker/CheckDeadStores.cpp

   1 //==- DeadStores.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/GR/Checkers/LocalCheckers.h"
  16 #include "clang/Analysis/Analyses/LiveVariables.h"
  17 #include "clang/Analysis/Visitors/CFGRecStmtVisitor.h"
  18 #include "clang/GR/BugReporter/BugReporter.h"
  19 #include "clang/GR/PathSensitive/GRExprEngine.h"
  20 #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
  21 #include "clang/Basic/Diagnostic.h"
  22 #include "clang/AST/ASTContext.h"
  23 #include "clang/AST/ParentMap.h"
  24 #include "llvm/ADT/SmallPtrSet.h"
  25
  26 using namespace clang;
  27
  28 namespace {
  29
  30 class DeadStoreObs : public LiveVariables::ObserverTy {
  31   ASTContext &Ctx;
  32   BugReporter& BR;
  33   ParentMap& Parents;
  34   llvm::SmallPtrSet<VarDecl*, 20> Escaped;
  35
  36   enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit };
  37
  38 public:
  39   DeadStoreObs(ASTContext &ctx, BugReporter& br, ParentMap& parents,
  40                llvm::SmallPtrSet<VarDecl*, 20> &escaped)
  41     : Ctx(ctx), BR(br), Parents(parents), Escaped(escaped) {}
  42
  43   virtual ~DeadStoreObs() {}
  44
  45   void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) {
  46     if (Escaped.count(V))
  47       return;
  48
  49     std::string name = V->getNameAsString();
  50
  51     const char* BugType = 0;
  52     std::string msg;
  53
  54     switch (dsk) {
  55       default:
  56         assert(false && "Impossible dead store type.");
  57
  58       case DeadInit:
  59         BugType = "Dead initialization";
  60         msg = "Value stored to '" + name +
  61           "' during its initialization is never read";
  62         break;
  63
  64       case DeadIncrement:
  65         BugType = "Dead increment";
  66       case Standard:
  67         if (!BugType) BugType = "Dead assignment";
  68         msg = "Value stored to '" + name + "' is never read";
  69         break;
  70
  71       case Enclosing:
  72         BugType = "Dead nested assignment";
  73         msg = "Although the value stored to '" + name +
  74           "' is used in the enclosing expression, the value is never actually"
  75           " read from '" + name + "'";
  76         break;
  77     }
  78
  79     BR.EmitBasicReport(BugType, "Dead store", msg, L, R);
  80   }
  81
  82   void CheckVarDecl(VarDecl* VD, Expr* Ex, Expr* Val,
  83                     DeadStoreKind dsk,
  84                     const LiveVariables::AnalysisDataTy& AD,
  85                     const LiveVariables::ValTy& Live) {
  86
  87     if (!VD->hasLocalStorage())
  88       return;
  89     // Reference types confuse the dead stores checker.  Skip them
  90     // for now.
  91     if (VD->getType()->getAs<ReferenceType>())
  92       return;
  93
  94     if (!Live(VD, AD) &&
  95         !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()))
  96       Report(VD, dsk, Ex->getSourceRange().getBegin(),
  97              Val->getSourceRange());
  98   }
  99
 100   void CheckDeclRef(DeclRefExpr* DR, Expr* Val, DeadStoreKind dsk,
 101                     const LiveVariables::AnalysisDataTy& AD,
 102                     const LiveVariables::ValTy& Live) {
 103     if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
 104       CheckVarDecl(VD, DR, Val, dsk, AD, Live);
 105   }
 106
 107   bool isIncrement(VarDecl* VD, BinaryOperator* B) {
 108     if (B->isCompoundAssignmentOp())
 109       return true;
 110
 111     Expr* RHS = B->getRHS()->IgnoreParenCasts();
 112     BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
 113
 114     if (!BRHS)
 115       return false;
 116
 117     DeclRefExpr *DR;
 118
 119     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
 120       if (DR->getDecl() == VD)
 121         return true;
 122
 123     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts())))
 124       if (DR->getDecl() == VD)
 125         return true;
 126
 127     return false;
 128   }
 129
 130   virtual void ObserveStmt(Stmt* S,
 131                            const LiveVariables::AnalysisDataTy& AD,
 132                            const LiveVariables::ValTy& Live) {
 133
 134     // Skip statements in macros.
 135     if (S->getLocStart().isMacroID())
 136       return;
 137
 138     if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
 139       if (!B->isAssignmentOp()) return; // Skip non-assignments.
 140
 141       if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()))
 142         if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 143           // Special case: check for assigning null to a pointer.
 144           //  This is a common form of defensive programming.
 145           QualType T = VD->getType();
 146           if (T->isPointerType() || T->isObjCObjectPointerType()) {
 147             if (B->getRHS()->isNullPointerConstant(Ctx,
 148                                               Expr::NPC_ValueDependentIsNull))
 149               return;
 150           }
 151
 152           Expr* RHS = B->getRHS()->IgnoreParenCasts();
 153           // Special case: self-assignments.  These are often used to shut up
 154           //  "unused variable" compiler warnings.
 155           if (DeclRefExpr* RhsDR = dyn_cast<DeclRefExpr>(RHS))
 156             if (VD == dyn_cast<VarDecl>(RhsDR->getDecl()))
 157               return;
 158
 159           // Otherwise, issue a warning.
 160           DeadStoreKind dsk = Parents.isConsumedExpr(B)
 161                               ? Enclosing
 162                               : (isIncrement(VD,B) ? DeadIncrement : Standard);
 163
 164           CheckVarDecl(VD, DR, B->getRHS(), dsk, AD, Live);
 165         }
 166     }
 167     else if (UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
 168       if (!U->isIncrementOp())
 169         return;
 170
 171       // Handle: ++x within a subexpression.  The solution is not warn
 172       //  about preincrements to dead variables when the preincrement occurs
 173       //  as a subexpression.  This can lead to false negatives, e.g. "(++x);"
 174       //  A generalized dead code checker should find such issues.
 175       if (U->isPrefix() && Parents.isConsumedExpr(U))
 176         return;
 177
 178       Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
 179
 180       if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex))
 181         CheckDeclRef(DR, U, DeadIncrement, AD, Live);
 182     }
 183     else if (DeclStmt* DS = dyn_cast<DeclStmt>(S))
 184       // Iterate through the decls.  Warn if any initializers are complex
 185       // expressions that are not live (never used).
 186       for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
 187            DI != DE; ++DI) {
 188
 189         VarDecl* V = dyn_cast<VarDecl>(*DI);
 190
 191         if (!V)
 192           continue;
 193
 194         if (V->hasLocalStorage()) {
 195           // Reference types confuse the dead stores checker.  Skip them
 196           // for now.
 197           if (V->getType()->getAs<ReferenceType>())
 198             return;
 199
 200           if (Expr* E = V->getInit()) {
 201             // Don't warn on C++ objects (yet) until we can show that their
 202             // constructors/destructors don't have side effects.
 203             if (isa<CXXConstructExpr>(E))
 204               return;
 205
 206             if (isa<ExprWithCleanups>(E))
 207               return;
 208
 209             // A dead initialization is a variable that is dead after it
 210             // is initialized.  We don't flag warnings for those variables
 211             // marked 'unused'.
 212             if (!Live(V, AD) && V->getAttr<UnusedAttr>() == 0) {
 213               // Special case: check for initializations with constants.
 214               //
 215               //  e.g. : int x = 0;
 216               //
 217               // If x is EVER assigned a new value later, don't issue
 218               // a warning.  This is because such initialization can be
 219               // due to defensive programming.
 220               if (E->isConstantInitializer(Ctx, false))
 221                 return;
 222
 223               if (DeclRefExpr *DRE=dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
 224                 if (VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) {
 225                   // Special case: check for initialization from constant
 226                   //  variables.
 227                   //
 228                   //  e.g. extern const int MyConstant;
 229                   //       int x = MyConstant;
 230                   //
 231                   if (VD->hasGlobalStorage() &&
 232                       VD->getType().isConstQualified())
 233                     return;
 234                   // Special case: check for initialization from scalar
 235                   //  parameters.  This is often a form of defensive
 236                   //  programming.  Non-scalars are still an error since
 237                   //  because it more likely represents an actual algorithmic
 238                   //  bug.
 239                   if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType())
 240                     return;
 241                 }
 242
 243               Report(V, DeadInit, V->getLocation(), E->getSourceRange());
 244             }
 245           }
 246         }
 247       }
 248   }
 249 };
 250
 251 } // end anonymous namespace
 252
 253 //===----------------------------------------------------------------------===//
 254 // Driver function to invoke the Dead-Stores checker on a CFG.
 255 //===----------------------------------------------------------------------===//
 256
 257 namespace {
 258 class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{
 259   CFG *cfg;
 260 public:
 261   FindEscaped(CFG *c) : cfg(c) {}
 262
 263   CFG& getCFG() { return *cfg; }
 264
 265   llvm::SmallPtrSet<VarDecl*, 20> Escaped;
 266
 267   void VisitUnaryOperator(UnaryOperator* U) {
 268     // Check for '&'.  Any VarDecl whose value has its address-taken we
 269     // treat as escaped.
 270     Expr* E = U->getSubExpr()->IgnoreParenCasts();
 271     if (U->getOpcode() == UO_AddrOf)
 272       if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E))
 273         if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
 274           Escaped.insert(VD);
 275           return;
 276         }
 277     Visit(E);
 278   }
 279 };
 280 } // end anonymous namespace
 281
 282
 283 void clang::CheckDeadStores(CFG &cfg, LiveVariables &L, ParentMap &pmap,
 284                             BugReporter& BR) {
 285   FindEscaped FS(&cfg);
 286   FS.getCFG().VisitBlockStmts(FS);
 287   DeadStoreObs A(BR.getContext(), BR, pmap, FS.Escaped);
 288   L.runOnAllBlocks(cfg, &A);
 289 }