1212795Sdim//== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- C++ -*-==// 2212795Sdim// 3212795Sdim// The LLVM Compiler Infrastructure 4212795Sdim// 5212795Sdim// This file is distributed under the University of Illinois Open Source 6212795Sdim// License. See LICENSE.TXT for details. 7212795Sdim// 8212795Sdim//===----------------------------------------------------------------------===// 9212795Sdim// 10212795Sdim// This file tracks the usage of variables in a Decl body to see if they are 11212795Sdim// never written to, implying that they constant. This is useful in static 12212795Sdim// analysis to see if a developer might have intended a variable to be const. 13212795Sdim// 14212795Sdim//===----------------------------------------------------------------------===// 15212795Sdim 16212795Sdim#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" 17212795Sdim#include "clang/AST/Decl.h" 18212795Sdim#include "clang/AST/Expr.h" 19212795Sdim#include "clang/AST/Stmt.h" 20239462Sdim#include "llvm/ADT/SmallPtrSet.h" 21212795Sdim#include <deque> 22212795Sdim 23212795Sdimusing namespace clang; 24212795Sdim 25212795Sdim// The number of ValueDecls we want to keep track of by default (per-function) 26212795Sdim#define VARDECL_SET_SIZE 256 27212795Sdimtypedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet; 28212795Sdim 29212795SdimPseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) : 30212795Sdim DeclBody(DeclBody), Analyzed(false) { 31212795Sdim NonConstantsImpl = new VarDeclSet; 32212795Sdim UsedVarsImpl = new VarDeclSet; 33212795Sdim} 34212795Sdim 35212795SdimPseudoConstantAnalysis::~PseudoConstantAnalysis() { 36212795Sdim delete (VarDeclSet*)NonConstantsImpl; 37212795Sdim delete (VarDeclSet*)UsedVarsImpl; 38212795Sdim} 39212795Sdim 40212795Sdim// Returns true if the given ValueDecl is never written to in the given DeclBody 41212795Sdimbool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) { 42212795Sdim // Only local and static variables can be pseudoconstants 43212795Sdim if (!VD->hasLocalStorage() && !VD->isStaticLocal()) 44212795Sdim return false; 45212795Sdim 46212795Sdim if (!Analyzed) { 47212795Sdim RunAnalysis(); 48212795Sdim Analyzed = true; 49212795Sdim } 50212795Sdim 51212795Sdim VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 52212795Sdim 53212795Sdim return !NonConstants->count(VD); 54212795Sdim} 55212795Sdim 56212795Sdim// Returns true if the variable was used (self assignments don't count) 57212795Sdimbool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) { 58212795Sdim if (!Analyzed) { 59212795Sdim RunAnalysis(); 60212795Sdim Analyzed = true; 61212795Sdim } 62212795Sdim 63212795Sdim VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 64212795Sdim 65212795Sdim return UsedVars->count(VD); 66212795Sdim} 67212795Sdim 68212795Sdim// Returns a Decl from a (Block)DeclRefExpr (if any) 69212795Sdimconst Decl *PseudoConstantAnalysis::getDecl(const Expr *E) { 70212795Sdim if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 71212795Sdim return DR->getDecl(); 72212795Sdim else 73276479Sdim return nullptr; 74212795Sdim} 75212795Sdim 76212795Sdimvoid PseudoConstantAnalysis::RunAnalysis() { 77212795Sdim std::deque<const Stmt *> WorkList; 78212795Sdim VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 79212795Sdim VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 80212795Sdim 81212795Sdim // Start with the top level statement of the function 82212795Sdim WorkList.push_back(DeclBody); 83212795Sdim 84212795Sdim while (!WorkList.empty()) { 85226633Sdim const Stmt *Head = WorkList.front(); 86212795Sdim WorkList.pop_front(); 87212795Sdim 88218893Sdim if (const Expr *Ex = dyn_cast<Expr>(Head)) 89218893Sdim Head = Ex->IgnoreParenCasts(); 90218893Sdim 91212795Sdim switch (Head->getStmtClass()) { 92212795Sdim // Case 1: Assignment operators modifying VarDecls 93212795Sdim case Stmt::BinaryOperatorClass: { 94212795Sdim const BinaryOperator *BO = cast<BinaryOperator>(Head); 95212795Sdim // Look for a Decl on the LHS 96212795Sdim const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts()); 97212795Sdim if (!LHSDecl) 98212795Sdim break; 99212795Sdim 100212795Sdim // We found a binary operator with a DeclRefExpr on the LHS. We now check 101212795Sdim // for any of the assignment operators, implying that this Decl is being 102212795Sdim // written to. 103212795Sdim switch (BO->getOpcode()) { 104212795Sdim // Self-assignments don't count as use of a variable 105212795Sdim case BO_Assign: { 106212795Sdim // Look for a DeclRef on the RHS 107212795Sdim const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts()); 108212795Sdim 109212795Sdim // If the Decls match, we have self-assignment 110212795Sdim if (LHSDecl == RHSDecl) 111212795Sdim // Do not visit the children 112212795Sdim continue; 113212795Sdim 114212795Sdim } 115212795Sdim case BO_AddAssign: 116212795Sdim case BO_SubAssign: 117212795Sdim case BO_MulAssign: 118212795Sdim case BO_DivAssign: 119212795Sdim case BO_AndAssign: 120212795Sdim case BO_OrAssign: 121212795Sdim case BO_XorAssign: 122212795Sdim case BO_ShlAssign: 123212795Sdim case BO_ShrAssign: { 124212795Sdim const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl); 125212795Sdim // The DeclRefExpr is being assigned to - mark it as non-constant 126212795Sdim if (VD) 127212795Sdim NonConstants->insert(VD); 128212795Sdim break; 129212795Sdim } 130212795Sdim 131212795Sdim default: 132212795Sdim break; 133212795Sdim } 134212795Sdim break; 135212795Sdim } 136212795Sdim 137212795Sdim // Case 2: Pre/post increment/decrement and address of 138212795Sdim case Stmt::UnaryOperatorClass: { 139212795Sdim const UnaryOperator *UO = cast<UnaryOperator>(Head); 140212795Sdim 141212795Sdim // Look for a DeclRef in the subexpression 142212795Sdim const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts()); 143212795Sdim if (!D) 144212795Sdim break; 145212795Sdim 146212795Sdim // We found a unary operator with a DeclRef as a subexpression. We now 147212795Sdim // check for any of the increment/decrement operators, as well as 148212795Sdim // addressOf. 149212795Sdim switch (UO->getOpcode()) { 150212795Sdim case UO_PostDec: 151212795Sdim case UO_PostInc: 152212795Sdim case UO_PreDec: 153212795Sdim case UO_PreInc: 154212795Sdim // The DeclRef is being changed - mark it as non-constant 155212795Sdim case UO_AddrOf: { 156212795Sdim // If we are taking the address of the DeclRefExpr, assume it is 157212795Sdim // non-constant. 158212795Sdim const VarDecl *VD = dyn_cast<VarDecl>(D); 159212795Sdim if (VD) 160212795Sdim NonConstants->insert(VD); 161212795Sdim break; 162212795Sdim } 163212795Sdim 164212795Sdim default: 165212795Sdim break; 166212795Sdim } 167212795Sdim break; 168212795Sdim } 169212795Sdim 170212795Sdim // Case 3: Reference Declarations 171212795Sdim case Stmt::DeclStmtClass: { 172212795Sdim const DeclStmt *DS = cast<DeclStmt>(Head); 173212795Sdim // Iterate over each decl and see if any of them contain reference decls 174276479Sdim for (const auto *I : DS->decls()) { 175212795Sdim // We only care about VarDecls 176276479Sdim const VarDecl *VD = dyn_cast<VarDecl>(I); 177212795Sdim if (!VD) 178212795Sdim continue; 179212795Sdim 180212795Sdim // We found a VarDecl; make sure it is a reference type 181212795Sdim if (!VD->getType().getTypePtr()->isReferenceType()) 182212795Sdim continue; 183212795Sdim 184212795Sdim // Try to find a Decl in the initializer 185212795Sdim const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts()); 186212795Sdim if (!D) 187212795Sdim break; 188212795Sdim 189212795Sdim // If the reference is to another var, add the var to the non-constant 190212795Sdim // list 191212795Sdim if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) { 192212795Sdim NonConstants->insert(RefVD); 193212795Sdim continue; 194212795Sdim } 195212795Sdim } 196212795Sdim break; 197212795Sdim } 198212795Sdim 199234353Sdim // Case 4: Variable references 200212795Sdim case Stmt::DeclRefExprClass: { 201212795Sdim const DeclRefExpr *DR = cast<DeclRefExpr>(Head); 202212795Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 203212795Sdim // Add the Decl to the used list 204212795Sdim UsedVars->insert(VD); 205212795Sdim continue; 206212795Sdim } 207212795Sdim break; 208212795Sdim } 209212795Sdim 210234353Sdim // Case 5: Block expressions 211212795Sdim case Stmt::BlockExprClass: { 212212795Sdim const BlockExpr *B = cast<BlockExpr>(Head); 213212795Sdim // Add the body of the block to the list 214212795Sdim WorkList.push_back(B->getBody()); 215212795Sdim continue; 216212795Sdim } 217212795Sdim 218218893Sdim default: 219218893Sdim break; 220212795Sdim } // switch (head->getStmtClass()) 221212795Sdim 222212795Sdim // Add all substatements to the worklist 223288943Sdim for (const Stmt *SubStmt : Head->children()) 224288943Sdim if (SubStmt) 225288943Sdim WorkList.push_back(SubStmt); 226212795Sdim } // while (!WorkList.empty()) 227212795Sdim} 228