1 //== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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"
23 using namespace clang;
25 typedef llvm::SmallPtrSet<const VarDecl*, 32> VarDeclSet;
27 PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) :
28 DeclBody(DeclBody), Analyzed(false) {
29 NonConstantsImpl = new VarDeclSet;
30 UsedVarsImpl = new VarDeclSet;
33 PseudoConstantAnalysis::~PseudoConstantAnalysis() {
34 delete (VarDeclSet*)NonConstantsImpl;
35 delete (VarDeclSet*)UsedVarsImpl;
38 // Returns true if the given ValueDecl is never written to in the given DeclBody
39 bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) {
40 // Only local and static variables can be pseudoconstants
41 if (!VD->hasLocalStorage() && !VD->isStaticLocal())
49 VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
51 return !NonConstants->count(VD);
54 // Returns true if the variable was used (self assignments don't count)
55 bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) {
61 VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
63 return UsedVars->count(VD);
66 // Returns a Decl from a (Block)DeclRefExpr (if any)
67 const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) {
68 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
74 void PseudoConstantAnalysis::RunAnalysis() {
75 std::deque<const Stmt *> WorkList;
76 VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
77 VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
79 // Start with the top level statement of the function
80 WorkList.push_back(DeclBody);
82 while (!WorkList.empty()) {
83 const Stmt *Head = WorkList.front();
86 if (const Expr *Ex = dyn_cast<Expr>(Head))
87 Head = Ex->IgnoreParenCasts();
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());
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
101 switch (BO->getOpcode()) {
102 // Self-assignments don't count as use of a variable
104 // Look for a DeclRef on the RHS
105 const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts());
107 // If the Decls match, we have self-assignment
108 if (LHSDecl == RHSDecl)
109 // Do not visit the children
122 const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl);
123 // The DeclRefExpr is being assigned to - mark it as non-constant
125 NonConstants->insert(VD);
135 // Case 2: Pre/post increment/decrement and address of
136 case Stmt::UnaryOperatorClass: {
137 const UnaryOperator *UO = cast<UnaryOperator>(Head);
139 // Look for a DeclRef in the subexpression
140 const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts());
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
147 switch (UO->getOpcode()) {
152 // The DeclRef is being changed - mark it as non-constant
154 // If we are taking the address of the DeclRefExpr, assume it is
156 const VarDecl *VD = dyn_cast<VarDecl>(D);
158 NonConstants->insert(VD);
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);
178 // We found a VarDecl; make sure it is a reference type
179 if (!VD->getType().getTypePtr()->isReferenceType())
182 // Try to find a Decl in the initializer
183 const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts());
187 // If the reference is to another var, add the var to the non-constant
189 if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) {
190 NonConstants->insert(RefVD);
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);
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());
218 } // switch (head->getStmtClass())
220 // Add all substatements to the worklist
221 for (const Stmt *SubStmt : Head->children())
223 WorkList.push_back(SubStmt);
224 } // while (!WorkList.empty())