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