1db34ab70961ca4b24b600eb47053d7af304659f5Tom Care//== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- C++ -*-==// 2245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// 3245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// The LLVM Compiler Infrastructure 4245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// 5245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// This file is distributed under the University of Illinois Open Source 6245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// License. See LICENSE.TXT for details. 7245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// 8245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care//===----------------------------------------------------------------------===// 9245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// 10245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// This file tracks the usage of variables in a Decl body to see if they are 11245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// never written to, implying that they constant. This is useful in static 12245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// analysis to see if a developer might have intended a variable to be const. 13245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// 14245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care//===----------------------------------------------------------------------===// 15245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 16db34ab70961ca4b24b600eb47053d7af304659f5Tom Care#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" 17245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care#include "clang/AST/Decl.h" 18245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care#include "clang/AST/Expr.h" 19245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care#include "clang/AST/Stmt.h" 20478851c3ed6bd784e7377dffd8e57b200c1b9ba9Benjamin Kramer#include "llvm/ADT/SmallPtrSet.h" 21245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care#include <deque> 22245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 23245adabd97c8c770c13935a9075f2243cc6f1d57Tom Careusing namespace clang; 24245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 25db34ab70961ca4b24b600eb47053d7af304659f5Tom Care// The number of ValueDecls we want to keep track of by default (per-function) 26db34ab70961ca4b24b600eb47053d7af304659f5Tom Care#define VARDECL_SET_SIZE 256 27db34ab70961ca4b24b600eb47053d7af304659f5Tom Caretypedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet; 28db34ab70961ca4b24b600eb47053d7af304659f5Tom Care 29db34ab70961ca4b24b600eb47053d7af304659f5Tom CarePseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) : 30db34ab70961ca4b24b600eb47053d7af304659f5Tom Care DeclBody(DeclBody), Analyzed(false) { 31db34ab70961ca4b24b600eb47053d7af304659f5Tom Care NonConstantsImpl = new VarDeclSet; 32ef52bcb606c73950139a775af61495f63fbc3603Tom Care UsedVarsImpl = new VarDeclSet; 33db34ab70961ca4b24b600eb47053d7af304659f5Tom Care} 34db34ab70961ca4b24b600eb47053d7af304659f5Tom Care 35db34ab70961ca4b24b600eb47053d7af304659f5Tom CarePseudoConstantAnalysis::~PseudoConstantAnalysis() { 36db34ab70961ca4b24b600eb47053d7af304659f5Tom Care delete (VarDeclSet*)NonConstantsImpl; 37ef52bcb606c73950139a775af61495f63fbc3603Tom Care delete (VarDeclSet*)UsedVarsImpl; 38db34ab70961ca4b24b600eb47053d7af304659f5Tom Care} 39db34ab70961ca4b24b600eb47053d7af304659f5Tom Care 40245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care// Returns true if the given ValueDecl is never written to in the given DeclBody 41db34ab70961ca4b24b600eb47053d7af304659f5Tom Carebool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) { 42db34ab70961ca4b24b600eb47053d7af304659f5Tom Care // Only local and static variables can be pseudoconstants 43db34ab70961ca4b24b600eb47053d7af304659f5Tom Care if (!VD->hasLocalStorage() && !VD->isStaticLocal()) 44db34ab70961ca4b24b600eb47053d7af304659f5Tom Care return false; 45db34ab70961ca4b24b600eb47053d7af304659f5Tom Care 46245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care if (!Analyzed) { 47245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care RunAnalysis(); 48245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care Analyzed = true; 49245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care } 50245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 51db34ab70961ca4b24b600eb47053d7af304659f5Tom Care VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 52db34ab70961ca4b24b600eb47053d7af304659f5Tom Care 53db34ab70961ca4b24b600eb47053d7af304659f5Tom Care return !NonConstants->count(VD); 54245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care} 55245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 56ef52bcb606c73950139a775af61495f63fbc3603Tom Care// Returns true if the variable was used (self assignments don't count) 57ef52bcb606c73950139a775af61495f63fbc3603Tom Carebool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) { 58ef52bcb606c73950139a775af61495f63fbc3603Tom Care if (!Analyzed) { 59ef52bcb606c73950139a775af61495f63fbc3603Tom Care RunAnalysis(); 60ef52bcb606c73950139a775af61495f63fbc3603Tom Care Analyzed = true; 61ef52bcb606c73950139a775af61495f63fbc3603Tom Care } 62ef52bcb606c73950139a775af61495f63fbc3603Tom Care 63ef52bcb606c73950139a775af61495f63fbc3603Tom Care VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 64ef52bcb606c73950139a775af61495f63fbc3603Tom Care 65ef52bcb606c73950139a775af61495f63fbc3603Tom Care return UsedVars->count(VD); 66ef52bcb606c73950139a775af61495f63fbc3603Tom Care} 67ef52bcb606c73950139a775af61495f63fbc3603Tom Care 68967fea6cd9ae60ea31d27d440967990d2c705729Tom Care// Returns a Decl from a (Block)DeclRefExpr (if any) 69967fea6cd9ae60ea31d27d440967990d2c705729Tom Careconst Decl *PseudoConstantAnalysis::getDecl(const Expr *E) { 70967fea6cd9ae60ea31d27d440967990d2c705729Tom Care if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) 71967fea6cd9ae60ea31d27d440967990d2c705729Tom Care return DR->getDecl(); 72967fea6cd9ae60ea31d27d440967990d2c705729Tom Care else 73967fea6cd9ae60ea31d27d440967990d2c705729Tom Care return 0; 74967fea6cd9ae60ea31d27d440967990d2c705729Tom Care} 75967fea6cd9ae60ea31d27d440967990d2c705729Tom Care 76db34ab70961ca4b24b600eb47053d7af304659f5Tom Carevoid PseudoConstantAnalysis::RunAnalysis() { 77245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care std::deque<const Stmt *> WorkList; 78db34ab70961ca4b24b600eb47053d7af304659f5Tom Care VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; 79ef52bcb606c73950139a775af61495f63fbc3603Tom Care VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; 80245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 81245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // Start with the top level statement of the function 82245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care WorkList.push_back(DeclBody); 83245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 84245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care while (!WorkList.empty()) { 859c378f705405d37f49795d5e915989de774fe11fTed Kremenek const Stmt *Head = WorkList.front(); 86245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care WorkList.pop_front(); 87245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 88892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek if (const Expr *Ex = dyn_cast<Expr>(Head)) 89892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek Head = Ex->IgnoreParenCasts(); 90892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek 91245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care switch (Head->getStmtClass()) { 92967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Case 1: Assignment operators modifying VarDecls 93245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care case Stmt::BinaryOperatorClass: { 94245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care const BinaryOperator *BO = cast<BinaryOperator>(Head); 95967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Look for a Decl on the LHS 96967fea6cd9ae60ea31d27d440967990d2c705729Tom Care const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts()); 97967fea6cd9ae60ea31d27d440967990d2c705729Tom Care if (!LHSDecl) 98245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care break; 99245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 100245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // We found a binary operator with a DeclRefExpr on the LHS. We now check 101245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // for any of the assignment operators, implying that this Decl is being 102245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // written to. 103245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care switch (BO->getOpcode()) { 104967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Self-assignments don't count as use of a variable 1052de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_Assign: { 106967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Look for a DeclRef on the RHS 107967fea6cd9ae60ea31d27d440967990d2c705729Tom Care const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts()); 108967fea6cd9ae60ea31d27d440967990d2c705729Tom Care 109967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // If the Decls match, we have self-assignment 110967fea6cd9ae60ea31d27d440967990d2c705729Tom Care if (LHSDecl == RHSDecl) 111967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Do not visit the children 112967fea6cd9ae60ea31d27d440967990d2c705729Tom Care continue; 113ef52bcb606c73950139a775af61495f63fbc3603Tom Care 114ef52bcb606c73950139a775af61495f63fbc3603Tom Care } 1152de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_AddAssign: 1162de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_SubAssign: 1172de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_MulAssign: 1182de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_DivAssign: 1192de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_AndAssign: 1202de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_OrAssign: 1212de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_XorAssign: 1222de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_ShlAssign: 1232de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case BO_ShrAssign: { 124967fea6cd9ae60ea31d27d440967990d2c705729Tom Care const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl); 125245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // The DeclRefExpr is being assigned to - mark it as non-constant 126db34ab70961ca4b24b600eb47053d7af304659f5Tom Care if (VD) 127db34ab70961ca4b24b600eb47053d7af304659f5Tom Care NonConstants->insert(VD); 128db34ab70961ca4b24b600eb47053d7af304659f5Tom Care break; 129db34ab70961ca4b24b600eb47053d7af304659f5Tom Care } 130245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 131245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care default: 132245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care break; 133245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care } 134245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care break; 135245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care } 136245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 137245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // Case 2: Pre/post increment/decrement and address of 138245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care case Stmt::UnaryOperatorClass: { 139245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care const UnaryOperator *UO = cast<UnaryOperator>(Head); 140245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 141967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Look for a DeclRef in the subexpression 142967fea6cd9ae60ea31d27d440967990d2c705729Tom Care const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts()); 143916d0541fa1723e3055d78f65dede844007989c3Tom Care if (!D) 144916d0541fa1723e3055d78f65dede844007989c3Tom Care break; 145245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 146967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // We found a unary operator with a DeclRef as a subexpression. We now 147245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // check for any of the increment/decrement operators, as well as 148245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // addressOf. 149245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care switch (UO->getOpcode()) { 1502de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PostDec: 1512de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PostInc: 1522de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PreDec: 1532de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_PreInc: 154967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // The DeclRef is being changed - mark it as non-constant 1552de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall case UO_AddrOf: { 156245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // If we are taking the address of the DeclRefExpr, assume it is 157245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // non-constant. 158967fea6cd9ae60ea31d27d440967990d2c705729Tom Care const VarDecl *VD = dyn_cast<VarDecl>(D); 159db34ab70961ca4b24b600eb47053d7af304659f5Tom Care if (VD) 160db34ab70961ca4b24b600eb47053d7af304659f5Tom Care NonConstants->insert(VD); 161db34ab70961ca4b24b600eb47053d7af304659f5Tom Care break; 162db34ab70961ca4b24b600eb47053d7af304659f5Tom Care } 163245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 164245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care default: 165245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care break; 166245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care } 167245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care break; 168245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care } 169245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 170db34ab70961ca4b24b600eb47053d7af304659f5Tom Care // Case 3: Reference Declarations 171db34ab70961ca4b24b600eb47053d7af304659f5Tom Care case Stmt::DeclStmtClass: { 172db34ab70961ca4b24b600eb47053d7af304659f5Tom Care const DeclStmt *DS = cast<DeclStmt>(Head); 173db34ab70961ca4b24b600eb47053d7af304659f5Tom Care // Iterate over each decl and see if any of them contain reference decls 174967fea6cd9ae60ea31d27d440967990d2c705729Tom Care for (DeclStmt::const_decl_iterator I = DS->decl_begin(), 175967fea6cd9ae60ea31d27d440967990d2c705729Tom Care E = DS->decl_end(); I != E; ++I) { 176db34ab70961ca4b24b600eb47053d7af304659f5Tom Care // We only care about VarDecls 177db34ab70961ca4b24b600eb47053d7af304659f5Tom Care const VarDecl *VD = dyn_cast<VarDecl>(*I); 178db34ab70961ca4b24b600eb47053d7af304659f5Tom Care if (!VD) 179db34ab70961ca4b24b600eb47053d7af304659f5Tom Care continue; 180db34ab70961ca4b24b600eb47053d7af304659f5Tom Care 181db34ab70961ca4b24b600eb47053d7af304659f5Tom Care // We found a VarDecl; make sure it is a reference type 182db34ab70961ca4b24b600eb47053d7af304659f5Tom Care if (!VD->getType().getTypePtr()->isReferenceType()) 183db34ab70961ca4b24b600eb47053d7af304659f5Tom Care continue; 184db34ab70961ca4b24b600eb47053d7af304659f5Tom Care 185967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Try to find a Decl in the initializer 186967fea6cd9ae60ea31d27d440967990d2c705729Tom Care const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts()); 187916d0541fa1723e3055d78f65dede844007989c3Tom Care if (!D) 188916d0541fa1723e3055d78f65dede844007989c3Tom Care break; 189967fea6cd9ae60ea31d27d440967990d2c705729Tom Care 190db34ab70961ca4b24b600eb47053d7af304659f5Tom Care // If the reference is to another var, add the var to the non-constant 191db34ab70961ca4b24b600eb47053d7af304659f5Tom Care // list 192967fea6cd9ae60ea31d27d440967990d2c705729Tom Care if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) { 193967fea6cd9ae60ea31d27d440967990d2c705729Tom Care NonConstants->insert(RefVD); 194967fea6cd9ae60ea31d27d440967990d2c705729Tom Care continue; 195967fea6cd9ae60ea31d27d440967990d2c705729Tom Care } 196ef52bcb606c73950139a775af61495f63fbc3603Tom Care } 197ef52bcb606c73950139a775af61495f63fbc3603Tom Care break; 198ef52bcb606c73950139a775af61495f63fbc3603Tom Care } 199ef52bcb606c73950139a775af61495f63fbc3603Tom Care 200f4b88a45902af1802a1cb42ba48b1c474474f228John McCall // Case 4: Variable references 201ef52bcb606c73950139a775af61495f63fbc3603Tom Care case Stmt::DeclRefExprClass: { 202ef52bcb606c73950139a775af61495f63fbc3603Tom Care const DeclRefExpr *DR = cast<DeclRefExpr>(Head); 203ef52bcb606c73950139a775af61495f63fbc3603Tom Care if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 204967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Add the Decl to the used list 205ef52bcb606c73950139a775af61495f63fbc3603Tom Care UsedVars->insert(VD); 206ef52bcb606c73950139a775af61495f63fbc3603Tom Care continue; 207ef52bcb606c73950139a775af61495f63fbc3603Tom Care } 208ef52bcb606c73950139a775af61495f63fbc3603Tom Care break; 209db34ab70961ca4b24b600eb47053d7af304659f5Tom Care } 210db34ab70961ca4b24b600eb47053d7af304659f5Tom Care 211f4b88a45902af1802a1cb42ba48b1c474474f228John McCall // Case 5: Block expressions 212967fea6cd9ae60ea31d27d440967990d2c705729Tom Care case Stmt::BlockExprClass: { 213967fea6cd9ae60ea31d27d440967990d2c705729Tom Care const BlockExpr *B = cast<BlockExpr>(Head); 214967fea6cd9ae60ea31d27d440967990d2c705729Tom Care // Add the body of the block to the list 215967fea6cd9ae60ea31d27d440967990d2c705729Tom Care WorkList.push_back(B->getBody()); 216967fea6cd9ae60ea31d27d440967990d2c705729Tom Care continue; 217967fea6cd9ae60ea31d27d440967990d2c705729Tom Care } 218967fea6cd9ae60ea31d27d440967990d2c705729Tom Care 219892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek default: 220892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek break; 221245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care } // switch (head->getStmtClass()) 222245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care 223245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care // Add all substatements to the worklist 2247502c1d3ce8bb97bcc4f7bebef507040bd93b26fJohn McCall for (Stmt::const_child_range I = Head->children(); I; ++I) 225245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care if (*I) 226245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care WorkList.push_back(*I); 227245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care } // while (!WorkList.empty()) 228245adabd97c8c770c13935a9075f2243cc6f1d57Tom Care} 229