PseudoConstantAnalysis.cpp revision 2c497ccd842431b6d143be0fefb45821ad1940a7 
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}
32
33PseudoConstantAnalysis::~PseudoConstantAnalysis() {
34  delete (VarDeclSet*)NonConstantsImpl;
35}
36
37// Returns true if the given ValueDecl is never written to in the given DeclBody
38bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) {
39  // Only local and static variables can be pseudoconstants
40  if (!VD->hasLocalStorage() && !VD->isStaticLocal())
41    return false;
42
43  if (!Analyzed) {
44    RunAnalysis();
45    Analyzed = true;
46  }
47
48  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
49
50  return !NonConstants->count(VD);
51}
52
53void PseudoConstantAnalysis::RunAnalysis() {
54  std::deque<const Stmt *> WorkList;
55  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
56
57  // Start with the top level statement of the function
58  WorkList.push_back(DeclBody);
59
60  while (!WorkList.empty()) {
61    const Stmt* Head = WorkList.front();
62    WorkList.pop_front();
63
64    switch (Head->getStmtClass()) {
65    // Case 1: Assignment operators modifying ValueDecl
66    case Stmt::BinaryOperatorClass: {
67      const BinaryOperator *BO = cast<BinaryOperator>(Head);
68      const Expr *LHS = BO->getLHS()->IgnoreParenImpCasts();
69      const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS);
70
71      // We only care about DeclRefExprs on the LHS
72      if (!DR)
73        break;
74
75      // We found a binary operator with a DeclRefExpr on the LHS. We now check
76      // for any of the assignment operators, implying that this Decl is being
77      // written to.
78      switch (BO->getOpcode()) {
79      case BinaryOperator::Assign:
80      case BinaryOperator::AddAssign:
81      case BinaryOperator::SubAssign:
82      case BinaryOperator::MulAssign:
83      case BinaryOperator::DivAssign:
84      case BinaryOperator::AndAssign:
85      case BinaryOperator::OrAssign:
86      case BinaryOperator::XorAssign:
87      case BinaryOperator::ShlAssign:
88      case BinaryOperator::ShrAssign: {
89        // The DeclRefExpr is being assigned to - mark it as non-constant
90        const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
91        if (VD)
92          NonConstants->insert(VD);
93        break;
94      }
95
96      default:
97        break;
98      }
99      break;
100    }
101
102    // Case 2: Pre/post increment/decrement and address of
103    case Stmt::UnaryOperatorClass: {
104      const UnaryOperator *UO = cast<UnaryOperator>(Head);
105      const Expr *SubExpr = UO->getSubExpr()->IgnoreParenImpCasts();
106      const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(SubExpr);
107
108      // We only care about DeclRefExprs in the subexpression
109      if (!DR)
110        break;
111
112      // We found a unary operator with a DeclRefExpr as a subexpression. We now
113      // check for any of the increment/decrement operators, as well as
114      // addressOf.
115      switch (UO->getOpcode()) {
116      case UnaryOperator::PostDec:
117      case UnaryOperator::PostInc:
118      case UnaryOperator::PreDec:
119      case UnaryOperator::PreInc:
120        // The DeclRefExpr is being changed - mark it as non-constant
121      case UnaryOperator::AddrOf: {
122        // If we are taking the address of the DeclRefExpr, assume it is
123        // non-constant.
124        const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
125        if (VD)
126          NonConstants->insert(VD);
127        break;
128      }
129
130      default:
131        break;
132      }
133      break;
134    }
135
136    // Case 3: Reference Declarations
137    case Stmt::DeclStmtClass: {
138      const DeclStmt *DS = cast<DeclStmt>(Head);
139      // Iterate over each decl and see if any of them contain reference decls
140      for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
141          I != E; ++I) {
142        // We only care about VarDecls
143        const VarDecl *VD = dyn_cast<VarDecl>(*I);
144        if (!VD)
145          continue;
146
147        // We found a VarDecl; make sure it is a reference type
148        if (!VD->getType().getTypePtr()->isReferenceType())
149          continue;
150
151        // Ignore VarDecls without a body
152        if (!VD->getBody())
153          continue;
154
155        // If the reference is to another var, add the var to the non-constant
156        // list
157        if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(VD->getBody()))
158          if (const VarDecl *RefVD = dyn_cast<VarDecl>(DR->getDecl()))
159            NonConstants->insert(RefVD);
160      }
161    }
162
163      default:
164        break;
165    } // switch (head->getStmtClass())
166
167    // Add all substatements to the worklist
168    for (Stmt::const_child_iterator I = Head->child_begin(),
169        E = Head->child_end(); I != E; ++I)
170      if (*I)
171        WorkList.push_back(*I);
172  } // while (!WorkList.empty())
173}
174