PseudoConstantAnalysis.cpp revision 288943
1189251Ssam//== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- C++ -*-==// 2214734Srpaulo// 3214734Srpaulo// The LLVM Compiler Infrastructure 4189251Ssam// 5252726Srpaulo// This file is distributed under the University of Illinois Open Source 6252726Srpaulo// License. See LICENSE.TXT for details. 7189251Ssam// 8189251Ssam//===----------------------------------------------------------------------===// 9189251Ssam// 10189251Ssam// This file tracks the usage of variables in a Decl body to see if they are 11189251Ssam// never written to, implying that they constant. This is useful in static 12189251Ssam// analysis to see if a developer might have intended a variable to be const. 13189251Ssam// 14189251Ssam//===----------------------------------------------------------------------===// 15189251Ssam 16189251Ssam#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" 17189251Ssam#include "clang/AST/Decl.h" 18189251Ssam#include "clang/AST/Expr.h" 19189251Ssam#include "clang/AST/Stmt.h" 20189251Ssam#include "llvm/ADT/SmallPtrSet.h" 21189251Ssam#include <deque> 22189251Ssam 23214734Srpaulousing namespace clang; 24252726Srpaulo 25214734Srpaulo// The number of ValueDecls we want to keep track of by default (per-function) 26252726Srpaulo#define VARDECL_SET_SIZE 256 27252726Srpaulotypedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet; 28214734Srpaulo 29214734SrpauloPseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) : 30214734Srpaulo DeclBody(DeclBody), Analyzed(false) { 31214734Srpaulo NonConstantsImpl = new VarDeclSet; 32214734Srpaulo UsedVarsImpl = new VarDeclSet; 33214734Srpaulo} 34214734Srpaulo 35214734SrpauloPseudoConstantAnalysis::~PseudoConstantAnalysis() { 36214734Srpaulo delete (VarDeclSet*)NonConstantsImpl; 37214734Srpaulo delete (VarDeclSet*)UsedVarsImpl; 38214734Srpaulo} 39214734Srpaulo 40214734Srpaulo// Returns true if the given ValueDecl is never written to in the given DeclBody 41214734Srpaulobool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) { 42214734Srpaulo // Only local and static variables can be pseudoconstants 43214734Srpaulo if (!VD->hasLocalStorage() && !VD->isStaticLocal()) 44214734Srpaulo return false; 45214734Srpaulo 46214734Srpaulo if (!Analyzed) { 47214734Srpaulo RunAnalysis(); 48214734Srpaulo Analyzed = true; 49214734Srpaulo } 50214734Srpaulo 51214734Srpaulo VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 52214734Srpaulo 53214734Srpaulo return !NonConstants->count(VD); 54214734Srpaulo} 55214734Srpaulo 56214734Srpaulo// Returns true if the variable was used (self assignments don't count) 57214734Srpaulobool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) { 58214734Srpaulo if (!Analyzed) { 59214734Srpaulo RunAnalysis(); 60214734Srpaulo Analyzed = true; 61214734Srpaulo } 62252726Srpaulo 63252726Srpaulo VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 64252726Srpaulo 65252726Srpaulo return UsedVars->count(VD); 66252726Srpaulo} 67252726Srpaulo 68214734Srpaulo// Returns a Decl from a (Block)DeclRefExpr (if any) 69214734Srpauloconst Decl *PseudoConstantAnalysis::getDecl(const Expr *E) { 70189251Ssam if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 71189251Ssam return DR->getDecl(); 72189251Ssam else 73189251Ssam return nullptr; 74214734Srpaulo} 75252726Srpaulo 76214734Srpaulovoid PseudoConstantAnalysis::RunAnalysis() { 77214734Srpaulo std::deque<const Stmt *> WorkList; 78214734Srpaulo VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 79214734Srpaulo VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 80189251Ssam 81189251Ssam // Start with the top level statement of the function 82209158Srpaulo WorkList.push_back(DeclBody); 83209158Srpaulo 84252726Srpaulo while (!WorkList.empty()) { 85209158Srpaulo const Stmt *Head = WorkList.front(); 86189251Ssam WorkList.pop_front(); 87189251Ssam 88189251Ssam if (const Expr *Ex = dyn_cast<Expr>(Head)) 89189251Ssam Head = Ex->IgnoreParenCasts(); 90189251Ssam 91189251Ssam switch (Head->getStmtClass()) { 92189251Ssam // Case 1: Assignment operators modifying VarDecls 93189251Ssam case Stmt::BinaryOperatorClass: { 94189251Ssam const BinaryOperator *BO = cast<BinaryOperator>(Head); 95189251Ssam // Look for a Decl on the LHS 96189251Ssam const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts()); 97189251Ssam if (!LHSDecl) 98189251Ssam break; 99189251Ssam 100189251Ssam // We found a binary operator with a DeclRefExpr on the LHS. We now check 101189251Ssam // for any of the assignment operators, implying that this Decl is being 102189251Ssam // written to. 103189251Ssam switch (BO->getOpcode()) { 104189251Ssam // Self-assignments don't count as use of a variable 105189251Ssam case BO_Assign: { 106189251Ssam // Look for a DeclRef on the RHS 107189251Ssam const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts()); 108189251Ssam 109189251Ssam // If the Decls match, we have self-assignment 110189251Ssam if (LHSDecl == RHSDecl) 111189251Ssam // Do not visit the children 112189251Ssam continue; 113189251Ssam 114189251Ssam } 115189251Ssam case BO_AddAssign: 116189251Ssam case BO_SubAssign: 117189251Ssam case BO_MulAssign: 118189251Ssam case BO_DivAssign: 119209158Srpaulo case BO_AndAssign: 120189251Ssam case BO_OrAssign: 121189251Ssam case BO_XorAssign: 122189251Ssam case BO_ShlAssign: 123189251Ssam case BO_ShrAssign: { 124189251Ssam const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl); 125189251Ssam // The DeclRefExpr is being assigned to - mark it as non-constant 126189251Ssam if (VD) 127189251Ssam NonConstants->insert(VD); 128189251Ssam break; 129189251Ssam } 130189251Ssam 131189251Ssam default: 132189251Ssam break; 133189251Ssam } 134189251Ssam break; 135189251Ssam } 136189251Ssam 137189251Ssam // Case 2: Pre/post increment/decrement and address of 138189251Ssam case Stmt::UnaryOperatorClass: { 139189251Ssam const UnaryOperator *UO = cast<UnaryOperator>(Head); 140189251Ssam 141189251Ssam // Look for a DeclRef in the subexpression 142189251Ssam const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts()); 143189251Ssam if (!D) 144189251Ssam break; 145189251Ssam 146189251Ssam // We found a unary operator with a DeclRef as a subexpression. We now 147189251Ssam // check for any of the increment/decrement operators, as well as 148189251Ssam // addressOf. 149189251Ssam switch (UO->getOpcode()) { 150189251Ssam case UO_PostDec: 151189251Ssam case UO_PostInc: 152189251Ssam case UO_PreDec: 153189251Ssam case UO_PreInc: 154209158Srpaulo // The DeclRef is being changed - mark it as non-constant 155209158Srpaulo case UO_AddrOf: { 156189251Ssam // If we are taking the address of the DeclRefExpr, assume it is 157189251Ssam // non-constant. 158189251Ssam const VarDecl *VD = dyn_cast<VarDecl>(D); 159189251Ssam if (VD) 160189251Ssam NonConstants->insert(VD); 161189251Ssam break; 162189251Ssam } 163189251Ssam 164189251Ssam default: 165189251Ssam break; 166189251Ssam } 167189251Ssam break; 168189251Ssam } 169189251Ssam 170189251Ssam // Case 3: Reference Declarations 171189251Ssam case Stmt::DeclStmtClass: { 172189251Ssam const DeclStmt *DS = cast<DeclStmt>(Head); 173189251Ssam // Iterate over each decl and see if any of them contain reference decls 174189251Ssam for (const auto *I : DS->decls()) { 175189251Ssam // We only care about VarDecls 176189251Ssam const VarDecl *VD = dyn_cast<VarDecl>(I); 177189251Ssam if (!VD) 178189251Ssam continue; 179189251Ssam 180189251Ssam // We found a VarDecl; make sure it is a reference type 181189251Ssam if (!VD->getType().getTypePtr()->isReferenceType()) 182189251Ssam continue; 183189251Ssam 184189251Ssam // Try to find a Decl in the initializer 185189251Ssam const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts()); 186189251Ssam if (!D) 187189251Ssam break; 188189251Ssam 189189251Ssam // If the reference is to another var, add the var to the non-constant 190189251Ssam // list 191189251Ssam if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) { 192189251Ssam NonConstants->insert(RefVD); 193189251Ssam continue; 194189251Ssam } 195189251Ssam } 196189251Ssam break; 197189251Ssam } 198189251Ssam 199189251Ssam // Case 4: Variable references 200189251Ssam case Stmt::DeclRefExprClass: { 201189251Ssam const DeclRefExpr *DR = cast<DeclRefExpr>(Head); 202189251Ssam if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 203189251Ssam // Add the Decl to the used list 204189251Ssam UsedVars->insert(VD); 205189251Ssam continue; 206189251Ssam } 207189251Ssam break; 208189251Ssam } 209189251Ssam 210189251Ssam // Case 5: Block expressions 211189251Ssam case Stmt::BlockExprClass: { 212189251Ssam const BlockExpr *B = cast<BlockExpr>(Head); 213189251Ssam // Add the body of the block to the list 214189251Ssam WorkList.push_back(B->getBody()); 215189251Ssam continue; 216189251Ssam } 217189251Ssam 218189251Ssam default: 219189251Ssam break; 220189251Ssam } // switch (head->getStmtClass()) 221189251Ssam 222189251Ssam // Add all substatements to the worklist 223189251Ssam for (const Stmt *SubStmt : Head->children()) 224189251Ssam if (SubStmt) 225189251Ssam WorkList.push_back(SubStmt); 226189251Ssam } // while (!WorkList.empty()) 227189251Ssam} 228189251Ssam