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 } 241