PseudoConstantAnalysis.cpp revision 967fea6cd9ae60ea31d27d440967990d2c705729
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 22using namespace clang; 23 24// The number of ValueDecls we want to keep track of by default (per-function) 25#define VARDECL_SET_SIZE 256 26typedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet; 27 28PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) : 29 DeclBody(DeclBody), Analyzed(false) { 30 NonConstantsImpl = new VarDeclSet; 31 UsedVarsImpl = new VarDeclSet; 32} 33 34PseudoConstantAnalysis::~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 40bool 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) 56bool 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) 68const 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 77void 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 switch (Head->getStmtClass()) { 90 // Case 1: Assignment operators modifying VarDecls 91 case Stmt::BinaryOperatorClass: { 92 const BinaryOperator *BO = cast<BinaryOperator>(Head); 93 // Look for a Decl on the LHS 94 const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts()); 95 96 if (!LHSDecl) 97 break; 98 99 // We found a binary operator with a DeclRefExpr on the LHS. We now check 100 // for any of the assignment operators, implying that this Decl is being 101 // written to. 102 switch (BO->getOpcode()) { 103 // Self-assignments don't count as use of a variable 104 case BO_Assign: { 105 // Look for a DeclRef on the RHS 106 const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts()); 107 108 // If the Decls match, we have self-assignment 109 if (LHSDecl == RHSDecl) 110 // Do not visit the children 111 continue; 112 113 } 114 case BO_AddAssign: 115 case BO_SubAssign: 116 case BO_MulAssign: 117 case BO_DivAssign: 118 case BO_AndAssign: 119 case BO_OrAssign: 120 case BO_XorAssign: 121 case BO_ShlAssign: 122 case BO_ShrAssign: { 123 const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl); 124 // The DeclRefExpr is being assigned to - mark it as non-constant 125 if (VD) 126 NonConstants->insert(VD); 127 break; 128 } 129 130 default: 131 break; 132 } 133 break; 134 } 135 136 // Case 2: Pre/post increment/decrement and address of 137 case Stmt::UnaryOperatorClass: { 138 const UnaryOperator *UO = cast<UnaryOperator>(Head); 139 140 // Look for a DeclRef in the subexpression 141 const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts()); 142 143 // We found a unary operator with a DeclRef as a subexpression. We now 144 // check for any of the increment/decrement operators, as well as 145 // addressOf. 146 switch (UO->getOpcode()) { 147 case UO_PostDec: 148 case UO_PostInc: 149 case UO_PreDec: 150 case UO_PreInc: 151 // The DeclRef is being changed - mark it as non-constant 152 case UO_AddrOf: { 153 // If we are taking the address of the DeclRefExpr, assume it is 154 // non-constant. 155 const VarDecl *VD = dyn_cast<VarDecl>(D); 156 if (VD) 157 NonConstants->insert(VD); 158 break; 159 } 160 161 default: 162 break; 163 } 164 break; 165 } 166 167 // Case 3: Reference Declarations 168 case Stmt::DeclStmtClass: { 169 const DeclStmt *DS = cast<DeclStmt>(Head); 170 // Iterate over each decl and see if any of them contain reference decls 171 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), 172 E = DS->decl_end(); I != E; ++I) { 173 // We only care about VarDecls 174 const VarDecl *VD = dyn_cast<VarDecl>(*I); 175 if (!VD) 176 continue; 177 178 // We found a VarDecl; make sure it is a reference type 179 if (!VD->getType().getTypePtr()->isReferenceType()) 180 continue; 181 182 // Try to find a Decl in the initializer 183 const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts()); 184 185 // If the reference is to another var, add the var to the non-constant 186 // list 187 if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) { 188 NonConstants->insert(RefVD); 189 continue; 190 } 191 } 192 break; 193 } 194 195 // Case 4: Block variable references 196 case Stmt::BlockDeclRefExprClass: { 197 const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(Head); 198 if (const VarDecl *VD = dyn_cast<VarDecl>(BDR->getDecl())) { 199 // Add the Decl to the used list 200 UsedVars->insert(VD); 201 continue; 202 } 203 break; 204 } 205 206 // Case 5: Variable references 207 case Stmt::DeclRefExprClass: { 208 const DeclRefExpr *DR = cast<DeclRefExpr>(Head); 209 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 210 // Add the Decl to the used list 211 UsedVars->insert(VD); 212 continue; 213 } 214 break; 215 } 216 217 // Case 6: Block expressions 218 case Stmt::BlockExprClass: { 219 const BlockExpr *B = cast<BlockExpr>(Head); 220 // Add the body of the block to the list 221 WorkList.push_back(B->getBody()); 222 continue; 223 } 224 225 default: 226 break; 227 } // switch (head->getStmtClass()) 228 229 // Add all substatements to the worklist 230 for (Stmt::const_child_iterator I = Head->child_begin(), 231 E = Head->child_end(); I != E; ++I) 232 if (*I) 233 WorkList.push_back(*I); 234 } // while (!WorkList.empty()) 235} 236