contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp

   1 //== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- 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 tracks the usage of variables in a Decl body to see if they are
  11 // never written to, implying that they constant. This is useful in static
  12 // analysis to see if a developer might have intended a variable to be const.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
  17 #include "clang/AST/Decl.h"
  18 #include "clang/AST/Expr.h"
  19 #include "clang/AST/Stmt.h"
  20 #include <deque>
  21
  22 using namespace clang;
  23
  24 // The number of ValueDecls we want to keep track of by default (per-function)
  25 #define VARDECL_SET_SIZE 256
  26 typedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet;
  27
  28 PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) :
  29       DeclBody(DeclBody), Analyzed(false) {
  30   NonConstantsImpl = new VarDeclSet;
  31   UsedVarsImpl = new VarDeclSet;
  32 }
  33
  34 PseudoConstantAnalysis::~PseudoConstantAnalysis() {
  35   delete (VarDeclSet*)NonConstantsImpl;
  36   delete (VarDeclSet*)UsedVarsImpl;
  37 }
  38
  39 // Returns true if the given ValueDecl is never written to in the given DeclBody
  40 bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) {
  41   // Only local and static variables can be pseudoconstants
  42   if (!VD->hasLocalStorage() && !VD->isStaticLocal())
  43     return false;
  44
  45   if (!Analyzed) {
  46     RunAnalysis();
  47     Analyzed = true;
  48   }
  49
  50   VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
  51
  52   return !NonConstants->count(VD);
  53 }
  54
  55 // Returns true if the variable was used (self assignments don't count)
  56 bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) {
  57   if (!Analyzed) {
  58     RunAnalysis();
  59     Analyzed = true;
  60   }
  61
  62   VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
  63
  64   return UsedVars->count(VD);
  65 }
  66
  67 // Returns a Decl from a (Block)DeclRefExpr (if any)
  68 const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) {
  69   if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
  70     return DR->getDecl();
  71   else if (const BlockDeclRefExpr *BDR = dyn_cast<BlockDeclRefExpr>(E))
  72     return BDR->getDecl();
  73   else
  74     return 0;
  75 }
  76
  77 void PseudoConstantAnalysis::RunAnalysis() {
  78   std::deque<const Stmt *> WorkList;
  79   VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
  80   VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
  81
  82   // Start with the top level statement of the function
  83   WorkList.push_back(DeclBody);
  84
  85   while (!WorkList.empty()) {
  86     const Stmt *Head = WorkList.front();
  87     WorkList.pop_front();
  88
  89     if (const Expr *Ex = dyn_cast<Expr>(Head))
  90       Head = Ex->IgnoreParenCasts();
  91
  92     switch (Head->getStmtClass()) {
  93     // Case 1: Assignment operators modifying VarDecls
  94     case Stmt::BinaryOperatorClass: {
  95       const BinaryOperator *BO = cast<BinaryOperator>(Head);
  96       // Look for a Decl on the LHS
  97       const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts());
  98       if (!LHSDecl)
  99         break;
 100
 101       // We found a binary operator with a DeclRefExpr on the LHS. We now check
 102       // for any of the assignment operators, implying that this Decl is being
 103       // written to.
 104       switch (BO->getOpcode()) {
 105       // Self-assignments don't count as use of a variable
 106       case BO_Assign: {
 107         // Look for a DeclRef on the RHS
 108         const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts());
 109
 110         // If the Decls match, we have self-assignment
 111         if (LHSDecl == RHSDecl)
 112           // Do not visit the children
 113           continue;
 114
 115       }
 116       case BO_AddAssign:
 117       case BO_SubAssign:
 118       case BO_MulAssign:
 119       case BO_DivAssign:
 120       case BO_AndAssign:
 121       case BO_OrAssign:
 122       case BO_XorAssign:
 123       case BO_ShlAssign:
 124       case BO_ShrAssign: {
 125         const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl);
 126         // The DeclRefExpr is being assigned to - mark it as non-constant
 127         if (VD)
 128           NonConstants->insert(VD);
 129         break;
 130       }
 131
 132       default:
 133         break;
 134       }
 135       break;
 136     }
 137
 138     // Case 2: Pre/post increment/decrement and address of
 139     case Stmt::UnaryOperatorClass: {
 140       const UnaryOperator *UO = cast<UnaryOperator>(Head);
 141
 142       // Look for a DeclRef in the subexpression
 143       const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts());
 144       if (!D)
 145         break;
 146
 147       // We found a unary operator with a DeclRef as a subexpression. We now
 148       // check for any of the increment/decrement operators, as well as
 149       // addressOf.
 150       switch (UO->getOpcode()) {
 151       case UO_PostDec:
 152       case UO_PostInc:
 153       case UO_PreDec:
 154       case UO_PreInc:
 155         // The DeclRef is being changed - mark it as non-constant
 156       case UO_AddrOf: {
 157         // If we are taking the address of the DeclRefExpr, assume it is
 158         // non-constant.
 159         const VarDecl *VD = dyn_cast<VarDecl>(D);
 160         if (VD)
 161           NonConstants->insert(VD);
 162         break;
 163       }
 164
 165       default:
 166         break;
 167       }
 168       break;
 169     }
 170
 171     // Case 3: Reference Declarations
 172     case Stmt::DeclStmtClass: {
 173       const DeclStmt *DS = cast<DeclStmt>(Head);
 174       // Iterate over each decl and see if any of them contain reference decls
 175       for (DeclStmt::const_decl_iterator I = DS->decl_begin(),
 176           E = DS->decl_end(); I != E; ++I) {
 177         // We only care about VarDecls
 178         const VarDecl *VD = dyn_cast<VarDecl>(*I);
 179         if (!VD)
 180           continue;
 181
 182         // We found a VarDecl; make sure it is a reference type
 183         if (!VD->getType().getTypePtr()->isReferenceType())
 184           continue;
 185
 186         // Try to find a Decl in the initializer
 187         const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts());
 188         if (!D)
 189           break;
 190
 191         // If the reference is to another var, add the var to the non-constant
 192         // list
 193         if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) {
 194           NonConstants->insert(RefVD);
 195           continue;
 196         }
 197       }
 198       break;
 199     }
 200
 201     // Case 4: Block variable references
 202     case Stmt::BlockDeclRefExprClass: {
 203       const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(Head);
 204       if (const VarDecl *VD = dyn_cast<VarDecl>(BDR->getDecl())) {
 205         // Add the Decl to the used list
 206         UsedVars->insert(VD);
 207         continue;
 208       }
 209       break;
 210     }
 211
 212     // Case 5: Variable references
 213     case Stmt::DeclRefExprClass: {
 214       const DeclRefExpr *DR = cast<DeclRefExpr>(Head);
 215       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
 216         // Add the Decl to the used list
 217         UsedVars->insert(VD);
 218         continue;
 219       }
 220       break;
 221     }
 222
 223     // Case 6: Block expressions
 224     case Stmt::BlockExprClass: {
 225       const BlockExpr *B = cast<BlockExpr>(Head);
 226       // Add the body of the block to the list
 227       WorkList.push_back(B->getBody());
 228       continue;
 229     }
 230
 231     default:
 232       break;
 233     } // switch (head->getStmtClass())
 234
 235     // Add all substatements to the worklist
 236     for (Stmt::const_child_range I = Head->children(); I; ++I)
 237       if (*I)
 238         WorkList.push_back(*I);
 239   } // while (!WorkList.empty())
 240 }