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 typedef llvm::SmallPtrSet<const VarDecl*, 32> VarDeclSet; 26 PseudoConstantAnalysis(const Stmt * DeclBody)27PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) : 28 DeclBody(DeclBody), Analyzed(false) { 29 NonConstantsImpl = new VarDeclSet; 30 UsedVarsImpl = new VarDeclSet; 31 } 32 ~PseudoConstantAnalysis()33PseudoConstantAnalysis::~PseudoConstantAnalysis() { 34 delete (VarDeclSet*)NonConstantsImpl; 35 delete (VarDeclSet*)UsedVarsImpl; 36 } 37 38 // Returns true if the given ValueDecl is never written to in the given DeclBody isPseudoConstant(const VarDecl * VD)39bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) { 40 // Only local and static variables can be pseudoconstants 41 if (!VD->hasLocalStorage() && !VD->isStaticLocal()) 42 return false; 43 44 if (!Analyzed) { 45 RunAnalysis(); 46 Analyzed = true; 47 } 48 49 VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 50 51 return !NonConstants->count(VD); 52 } 53 54 // Returns true if the variable was used (self assignments don't count) wasReferenced(const VarDecl * VD)55bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) { 56 if (!Analyzed) { 57 RunAnalysis(); 58 Analyzed = true; 59 } 60 61 VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 62 63 return UsedVars->count(VD); 64 } 65 66 // Returns a Decl from a (Block)DeclRefExpr (if any) getDecl(const Expr * E)67const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) { 68 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 69 return DR->getDecl(); 70 else 71 return nullptr; 72 } 73 RunAnalysis()74void PseudoConstantAnalysis::RunAnalysis() { 75 std::deque<const Stmt *> WorkList; 76 VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 77 VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 78 79 // Start with the top level statement of the function 80 WorkList.push_back(DeclBody); 81 82 while (!WorkList.empty()) { 83 const Stmt *Head = WorkList.front(); 84 WorkList.pop_front(); 85 86 if (const Expr *Ex = dyn_cast<Expr>(Head)) 87 Head = Ex->IgnoreParenCasts(); 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 (const auto *I : DS->decls()) { 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 if (!D) 185 break; 186 187 // If the reference is to another var, add the var to the non-constant 188 // list 189 if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) { 190 NonConstants->insert(RefVD); 191 continue; 192 } 193 } 194 break; 195 } 196 197 // Case 4: Variable references 198 case Stmt::DeclRefExprClass: { 199 const DeclRefExpr *DR = cast<DeclRefExpr>(Head); 200 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 201 // Add the Decl to the used list 202 UsedVars->insert(VD); 203 continue; 204 } 205 break; 206 } 207 208 // Case 5: Block expressions 209 case Stmt::BlockExprClass: { 210 const BlockExpr *B = cast<BlockExpr>(Head); 211 // Add the body of the block to the list 212 WorkList.push_back(B->getBody()); 213 continue; 214 } 215 216 default: 217 break; 218 } // switch (head->getStmtClass()) 219 220 // Add all substatements to the worklist 221 for (const Stmt *SubStmt : Head->children()) 222 if (SubStmt) 223 WorkList.push_back(SubStmt); 224 } // while (!WorkList.empty()) 225 } 226