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