PseudoConstantAnalysis.cpp revision 2de56d1d0c3a504ad1529de2677628bdfbb95cd4 
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 <deque>
21
22using namespace clang;
23
24// The number of ValueDecls we want to keep track of by default (per-function)
25#define VARDECL_SET_SIZE 256
26typedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet;
27
28PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) :
29      DeclBody(DeclBody), Analyzed(false) {
30  NonConstantsImpl = new VarDeclSet;
31  UsedVarsImpl = new VarDeclSet;
32}
33
34PseudoConstantAnalysis::~PseudoConstantAnalysis() {
35  delete (VarDeclSet*)NonConstantsImpl;
36  delete (VarDeclSet*)UsedVarsImpl;
37}
38
39// Returns true if the given ValueDecl is never written to in the given DeclBody
40bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) {
41  // Only local and static variables can be pseudoconstants
42  if (!VD->hasLocalStorage() && !VD->isStaticLocal())
43    return false;
44
45  if (!Analyzed) {
46    RunAnalysis();
47    Analyzed = true;
48  }
49
50  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
51
52  return !NonConstants->count(VD);
53}
54
55// Returns true if the variable was used (self assignments don't count)
56bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) {
57  if (!Analyzed) {
58    RunAnalysis();
59    Analyzed = true;
60  }
61
62  VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
63
64  return UsedVars->count(VD);
65}
66
67void PseudoConstantAnalysis::RunAnalysis() {
68  std::deque<const Stmt *> WorkList;
69  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
70  VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
71
72  // Start with the top level statement of the function
73  WorkList.push_back(DeclBody);
74
75  while (!WorkList.empty()) {
76    const Stmt* Head = WorkList.front();
77    WorkList.pop_front();
78
79    switch (Head->getStmtClass()) {
80    // Case 1: Assignment operators modifying ValueDecl
81    case Stmt::BinaryOperatorClass: {
82      const BinaryOperator *BO = cast<BinaryOperator>(Head);
83      const Expr *LHS = BO->getLHS()->IgnoreParenCasts();
84      const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS);
85
86      // We only care about DeclRefExprs on the LHS
87      if (!DR)
88        break;
89
90      // We found a binary operator with a DeclRefExpr on the LHS. We now check
91      // for any of the assignment operators, implying that this Decl is being
92      // written to.
93      switch (BO->getOpcode()) {
94      case BO_Assign: {
95        const Expr *RHS = BO->getRHS()->IgnoreParenCasts();
96        if (const DeclRefExpr *RHSDecl = dyn_cast<DeclRefExpr>(RHS)) {
97          // Self-assignments don't count as use of a variable
98          if (DR->getDecl() == RHSDecl->getDecl())
99            // Do not visit the children
100            continue;
101        }
102
103      }
104      case BO_AddAssign:
105      case BO_SubAssign:
106      case BO_MulAssign:
107      case BO_DivAssign:
108      case BO_AndAssign:
109      case BO_OrAssign:
110      case BO_XorAssign:
111      case BO_ShlAssign:
112      case BO_ShrAssign: {
113        // The DeclRefExpr is being assigned to - mark it as non-constant
114        const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
115        if (VD)
116          NonConstants->insert(VD);
117        break;
118      }
119
120      default:
121        break;
122      }
123      break;
124    }
125
126    // Case 2: Pre/post increment/decrement and address of
127    case Stmt::UnaryOperatorClass: {
128      const UnaryOperator *UO = cast<UnaryOperator>(Head);
129      const Expr *SubExpr = UO->getSubExpr()->IgnoreParenImpCasts();
130      const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(SubExpr);
131
132      // We only care about DeclRefExprs in the subexpression
133      if (!DR)
134        break;
135
136      // We found a unary operator with a DeclRefExpr as a subexpression. We now
137      // check for any of the increment/decrement operators, as well as
138      // addressOf.
139      switch (UO->getOpcode()) {
140      case UO_PostDec:
141      case UO_PostInc:
142      case UO_PreDec:
143      case UO_PreInc:
144        // The DeclRefExpr is being changed - mark it as non-constant
145      case UO_AddrOf: {
146        // If we are taking the address of the DeclRefExpr, assume it is
147        // non-constant.
148        const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
149        if (VD)
150          NonConstants->insert(VD);
151        break;
152      }
153
154      default:
155        break;
156      }
157      break;
158    }
159
160    // Case 3: Reference Declarations
161    case Stmt::DeclStmtClass: {
162      const DeclStmt *DS = cast<DeclStmt>(Head);
163      // Iterate over each decl and see if any of them contain reference decls
164      for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
165          I != E; ++I) {
166        // We only care about VarDecls
167        const VarDecl *VD = dyn_cast<VarDecl>(*I);
168        if (!VD)
169          continue;
170
171        // We found a VarDecl; make sure it is a reference type
172        if (!VD->getType().getTypePtr()->isReferenceType())
173          continue;
174
175        // If the reference is to another var, add the var to the non-constant
176        // list
177        if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(VD->getInit()))
178          if (const VarDecl *RefVD = dyn_cast<VarDecl>(DR->getDecl())) {
179            NonConstants->insert(RefVD);
180            continue;
181          }
182      }
183      break;
184    }
185
186    // Case 4: Block variable references
187    case Stmt::BlockDeclRefExprClass: {
188      // Any block variables are assumed to be non-constant
189      const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(Head);
190      if (const VarDecl *VD = dyn_cast<VarDecl>(BDR->getDecl())) {
191        NonConstants->insert(VD);
192        UsedVars->insert(VD);
193        continue;
194      }
195      break;
196    }
197
198    // Case 5: Variable references
199    case Stmt::DeclRefExprClass: {
200      const DeclRefExpr *DR = cast<DeclRefExpr>(Head);
201      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
202        UsedVars->insert(VD);
203        continue;
204      }
205      break;
206    }
207
208      default:
209        break;
210    } // switch (head->getStmtClass())
211
212    // Add all substatements to the worklist
213    for (Stmt::const_child_iterator I = Head->child_begin(),
214        E = Head->child_end(); I != E; ++I)
215      if (*I)
216        WorkList.push_back(*I);
217  } // while (!WorkList.empty())
218}
219