PseudoConstantAnalysis.cpp revision f4b88a45902af1802a1cb42ba48b1c474474f228
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 72 return 0; 73} 74 75void PseudoConstantAnalysis::RunAnalysis() { 76 std::deque<const Stmt *> WorkList; 77 VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 78 VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 79 80 // Start with the top level statement of the function 81 WorkList.push_back(DeclBody); 82 83 while (!WorkList.empty()) { 84 const Stmt *Head = WorkList.front(); 85 WorkList.pop_front(); 86 87 if (const Expr *Ex = dyn_cast<Expr>(Head)) 88 Head = Ex->IgnoreParenCasts(); 89 90 switch (Head->getStmtClass()) { 91 // Case 1: Assignment operators modifying VarDecls 92 case Stmt::BinaryOperatorClass: { 93 const BinaryOperator *BO = cast<BinaryOperator>(Head); 94 // Look for a Decl on the LHS 95 const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts()); 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 if (!D) 143 break; 144 145 // We found a unary operator with a DeclRef as a subexpression. We now 146 // check for any of the increment/decrement operators, as well as 147 // addressOf. 148 switch (UO->getOpcode()) { 149 case UO_PostDec: 150 case UO_PostInc: 151 case UO_PreDec: 152 case UO_PreInc: 153 // The DeclRef is being changed - mark it as non-constant 154 case UO_AddrOf: { 155 // If we are taking the address of the DeclRefExpr, assume it is 156 // non-constant. 157 const VarDecl *VD = dyn_cast<VarDecl>(D); 158 if (VD) 159 NonConstants->insert(VD); 160 break; 161 } 162 163 default: 164 break; 165 } 166 break; 167 } 168 169 // Case 3: Reference Declarations 170 case Stmt::DeclStmtClass: { 171 const DeclStmt *DS = cast<DeclStmt>(Head); 172 // Iterate over each decl and see if any of them contain reference decls 173 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), 174 E = DS->decl_end(); I != E; ++I) { 175 // We only care about VarDecls 176 const VarDecl *VD = dyn_cast<VarDecl>(*I); 177 if (!VD) 178 continue; 179 180 // We found a VarDecl; make sure it is a reference type 181 if (!VD->getType().getTypePtr()->isReferenceType()) 182 continue; 183 184 // Try to find a Decl in the initializer 185 const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts()); 186 if (!D) 187 break; 188 189 // If the reference is to another var, add the var to the non-constant 190 // list 191 if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) { 192 NonConstants->insert(RefVD); 193 continue; 194 } 195 } 196 break; 197 } 198 199 // Case 4: Variable references 200 case Stmt::DeclRefExprClass: { 201 const DeclRefExpr *DR = cast<DeclRefExpr>(Head); 202 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 203 // Add the Decl to the used list 204 UsedVars->insert(VD); 205 continue; 206 } 207 break; 208 } 209 210 // Case 5: Block expressions 211 case Stmt::BlockExprClass: { 212 const BlockExpr *B = cast<BlockExpr>(Head); 213 // Add the body of the block to the list 214 WorkList.push_back(B->getBody()); 215 continue; 216 } 217 218 default: 219 break; 220 } // switch (head->getStmtClass()) 221 222 // Add all substatements to the worklist 223 for (Stmt::const_child_range I = Head->children(); I; ++I) 224 if (*I) 225 WorkList.push_back(*I); 226 } // while (!WorkList.empty()) 227} 228