summaryrefslogtreecommitdiff
path: root/clang/lib/Analysis/PseudoConstantAnalysis.cpp
blob: c8b491a21682cc07ecaa0462dc007a7d25fe4a3e (about) (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
//== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- C++ -*-==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file tracks the usage of variables in a Decl body to see if they are
// never written to, implying that they constant. This is useful in static
// analysis to see if a developer might have intended a variable to be const.
//
//===----------------------------------------------------------------------===//

#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
#include "clang/AST/Decl.h"
#include "clang/AST/Expr.h"
#include "clang/AST/Stmt.h"
#include <deque>

using namespace clang;

// The number of ValueDecls we want to keep track of by default (per-function)
#define VARDECL_SET_SIZE 256
typedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet;

PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) :
      DeclBody(DeclBody), Analyzed(false) {
  NonConstantsImpl = new VarDeclSet;
  UsedVarsImpl = new VarDeclSet;
}

PseudoConstantAnalysis::~PseudoConstantAnalysis() {
  delete (VarDeclSet*)NonConstantsImpl;
  delete (VarDeclSet*)UsedVarsImpl;
}

// Returns true if the given ValueDecl is never written to in the given DeclBody
bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) {
  // Only local and static variables can be pseudoconstants
  if (!VD->hasLocalStorage() && !VD->isStaticLocal())
    return false;

  if (!Analyzed) {
    RunAnalysis();
    Analyzed = true;
  }

  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;

  return !NonConstants->count(VD);
}

// Returns true if the variable was used (self assignments don't count)
bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) {
  if (!Analyzed) {
    RunAnalysis();
    Analyzed = true;
  }

  VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;

  return UsedVars->count(VD);
}

// Returns a Decl from a (Block)DeclRefExpr (if any)
const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) {
  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
    return DR->getDecl();
  else
    return 0;
}

void PseudoConstantAnalysis::RunAnalysis() {
  std::deque<const Stmt *> WorkList;
  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
  VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;

  // Start with the top level statement of the function
  WorkList.push_back(DeclBody);

  while (!WorkList.empty()) {
    const Stmt *Head = WorkList.front();
    WorkList.pop_front();

    if (const Expr *Ex = dyn_cast<Expr>(Head))
      Head = Ex->IgnoreParenCasts();

    switch (Head->getStmtClass()) {
    // Case 1: Assignment operators modifying VarDecls
    case Stmt::BinaryOperatorClass: {
      const BinaryOperator *BO = cast<BinaryOperator>(Head);
      // Look for a Decl on the LHS
      const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts());
      if (!LHSDecl)
        break;

      // We found a binary operator with a DeclRefExpr on the LHS. We now check
      // for any of the assignment operators, implying that this Decl is being
      // written to.
      switch (BO->getOpcode()) {
      // Self-assignments don't count as use of a variable
      case BO_Assign: {
        // Look for a DeclRef on the RHS
        const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts());

        // If the Decls match, we have self-assignment
        if (LHSDecl == RHSDecl)
          // Do not visit the children
          continue;

      }
      case BO_AddAssign:
      case BO_SubAssign:
      case BO_MulAssign:
      case BO_DivAssign:
      case BO_AndAssign:
      case BO_OrAssign:
      case BO_XorAssign:
      case BO_ShlAssign:
      case BO_ShrAssign: {
        const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl);
        // The DeclRefExpr is being assigned to - mark it as non-constant
        if (VD)
          NonConstants->insert(VD);
        break;
      }

      default:
        break;
      }
      break;
    }

    // Case 2: Pre/post increment/decrement and address of
    case Stmt::UnaryOperatorClass: {
      const UnaryOperator *UO = cast<UnaryOperator>(Head);

      // Look for a DeclRef in the subexpression
      const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts());
      if (!D)
        break;

      // We found a unary operator with a DeclRef as a subexpression. We now
      // check for any of the increment/decrement operators, as well as
      // addressOf.
      switch (UO->getOpcode()) {
      case UO_PostDec:
      case UO_PostInc:
      case UO_PreDec:
      case UO_PreInc:
        // The DeclRef is being changed - mark it as non-constant
      case UO_AddrOf: {
        // If we are taking the address of the DeclRefExpr, assume it is
        // non-constant.
        const VarDecl *VD = dyn_cast<VarDecl>(D);
        if (VD)
          NonConstants->insert(VD);
        break;
      }

      default:
        break;
      }
      break;
    }

    // Case 3: Reference Declarations
    case Stmt::DeclStmtClass: {
      const DeclStmt *DS = cast<DeclStmt>(Head);
      // Iterate over each decl and see if any of them contain reference decls
      for (DeclStmt::const_decl_iterator I = DS->decl_begin(),
          E = DS->decl_end(); I != E; ++I) {
        // We only care about VarDecls
        const VarDecl *VD = dyn_cast<VarDecl>(*I);
        if (!VD)
          continue;

        // We found a VarDecl; make sure it is a reference type
        if (!VD->getType().getTypePtr()->isReferenceType())
          continue;

        // Try to find a Decl in the initializer
        const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts());
        if (!D)
          break;

        // If the reference is to another var, add the var to the non-constant
        // list
        if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) {
          NonConstants->insert(RefVD);
          continue;
        }
      }
      break;
    }

    // Case 4: Variable references
    case Stmt::DeclRefExprClass: {
      const DeclRefExpr *DR = cast<DeclRefExpr>(Head);
      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
        // Add the Decl to the used list
        UsedVars->insert(VD);
        continue;
      }
      break;
    }

    // Case 5: Block expressions
    case Stmt::BlockExprClass: {
      const BlockExpr *B = cast<BlockExpr>(Head);
      // Add the body of the block to the list
      WorkList.push_back(B->getBody());
      continue;
    }

    default:
      break;
    } // switch (head->getStmtClass())

    // Add all substatements to the worklist
    for (Stmt::const_child_range I = Head->children(); I; ++I)
      if (*I)
        WorkList.push_back(*I);
  } // while (!WorkList.empty())
}