PseudoConstantAnalysis.cpp revision 9c378f705405d37f49795d5e915989de774fe11f 
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
67// Returns a Decl from a (Block)DeclRefExpr (if any)
68const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) {
69  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
70    return DR->getDecl();
71  else if (const BlockDeclRefExpr *BDR = dyn_cast<BlockDeclRefExpr>(E))
72    return BDR->getDecl();
73  else
74    return 0;
75}
76
77void PseudoConstantAnalysis::RunAnalysis() {
78  std::deque<const Stmt *> WorkList;
79  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
80  VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
81
82  // Start with the top level statement of the function
83  WorkList.push_back(DeclBody);
84
85  while (!WorkList.empty()) {
86    const Stmt *Head = WorkList.front();
87    WorkList.pop_front();
88
89    if (const Expr *Ex = dyn_cast<Expr>(Head))
90      Head = Ex->IgnoreParenCasts();
91
92    switch (Head->getStmtClass()) {
93    // Case 1: Assignment operators modifying VarDecls
94    case Stmt::BinaryOperatorClass: {
95      const BinaryOperator *BO = cast<BinaryOperator>(Head);
96      // Look for a Decl on the LHS
97      const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts());
98      if (!LHSDecl)
99        break;
100
101      // We found a binary operator with a DeclRefExpr on the LHS. We now check
102      // for any of the assignment operators, implying that this Decl is being
103      // written to.
104      switch (BO->getOpcode()) {
105      // Self-assignments don't count as use of a variable
106      case BO_Assign: {
107        // Look for a DeclRef on the RHS
108        const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts());
109
110        // If the Decls match, we have self-assignment
111        if (LHSDecl == RHSDecl)
112          // Do not visit the children
113          continue;
114
115      }
116      case BO_AddAssign:
117      case BO_SubAssign:
118      case BO_MulAssign:
119      case BO_DivAssign:
120      case BO_AndAssign:
121      case BO_OrAssign:
122      case BO_XorAssign:
123      case BO_ShlAssign:
124      case BO_ShrAssign: {
125        const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl);
126        // The DeclRefExpr is being assigned to - mark it as non-constant
127        if (VD)
128          NonConstants->insert(VD);
129        break;
130      }
131
132      default:
133        break;
134      }
135      break;
136    }
137
138    // Case 2: Pre/post increment/decrement and address of
139    case Stmt::UnaryOperatorClass: {
140      const UnaryOperator *UO = cast<UnaryOperator>(Head);
141
142      // Look for a DeclRef in the subexpression
143      const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts());
144      if (!D)
145        break;
146
147      // We found a unary operator with a DeclRef as a subexpression. We now
148      // check for any of the increment/decrement operators, as well as
149      // addressOf.
150      switch (UO->getOpcode()) {
151      case UO_PostDec:
152      case UO_PostInc:
153      case UO_PreDec:
154      case UO_PreInc:
155        // The DeclRef is being changed - mark it as non-constant
156      case UO_AddrOf: {
157        // If we are taking the address of the DeclRefExpr, assume it is
158        // non-constant.
159        const VarDecl *VD = dyn_cast<VarDecl>(D);
160        if (VD)
161          NonConstants->insert(VD);
162        break;
163      }
164
165      default:
166        break;
167      }
168      break;
169    }
170
171    // Case 3: Reference Declarations
172    case Stmt::DeclStmtClass: {
173      const DeclStmt *DS = cast<DeclStmt>(Head);
174      // Iterate over each decl and see if any of them contain reference decls
175      for (DeclStmt::const_decl_iterator I = DS->decl_begin(),
176          E = DS->decl_end(); I != E; ++I) {
177        // We only care about VarDecls
178        const VarDecl *VD = dyn_cast<VarDecl>(*I);
179        if (!VD)
180          continue;
181
182        // We found a VarDecl; make sure it is a reference type
183        if (!VD->getType().getTypePtr()->isReferenceType())
184          continue;
185
186        // Try to find a Decl in the initializer
187        const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts());
188        if (!D)
189          break;
190
191        // If the reference is to another var, add the var to the non-constant
192        // list
193        if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) {
194          NonConstants->insert(RefVD);
195          continue;
196        }
197      }
198      break;
199    }
200
201    // Case 4: Block variable references
202    case Stmt::BlockDeclRefExprClass: {
203      const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(Head);
204      if (const VarDecl *VD = dyn_cast<VarDecl>(BDR->getDecl())) {
205        // Add the Decl to the used list
206        UsedVars->insert(VD);
207        continue;
208      }
209      break;
210    }
211
212    // Case 5: Variable references
213    case Stmt::DeclRefExprClass: {
214      const DeclRefExpr *DR = cast<DeclRefExpr>(Head);
215      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
216        // Add the Decl to the used list
217        UsedVars->insert(VD);
218        continue;
219      }
220      break;
221    }
222
223    // Case 6: Block expressions
224    case Stmt::BlockExprClass: {
225      const BlockExpr *B = cast<BlockExpr>(Head);
226      // Add the body of the block to the list
227      WorkList.push_back(B->getBody());
228      continue;
229    }
230
231    default:
232      break;
233    } // switch (head->getStmtClass())
234
235    // Add all substatements to the worklist
236    for (Stmt::const_child_range I = Head->children(); I; ++I)
237      if (*I)
238        WorkList.push_back(*I);
239  } // while (!WorkList.empty())
240}
241