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