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 PseudoConstantAnalysis(const Stmt * DeclBody)29PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) : 30 DeclBody(DeclBody), Analyzed(false) { 31 NonConstantsImpl = new VarDeclSet; 32 UsedVarsImpl = new VarDeclSet; 33 } 34 ~PseudoConstantAnalysis()35PseudoConstantAnalysis::~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 isPseudoConstant(const VarDecl * VD)41bool 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) wasReferenced(const VarDecl * VD)57bool 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) getDecl(const Expr * E)69const 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 RunAnalysis()76void 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 } 229