clang  6.0.0svn
PseudoConstantAnalysis.cpp
Go to the documentation of this file.
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 
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 
23 using namespace clang;
24 
25 typedef llvm::SmallPtrSet<const VarDecl*, 32> VarDeclSet;
26 
28  DeclBody(DeclBody), Analyzed(false) {
29  NonConstantsImpl = new VarDeclSet;
30  UsedVarsImpl = new VarDeclSet;
31 }
32 
34  delete (VarDeclSet*)NonConstantsImpl;
35  delete (VarDeclSet*)UsedVarsImpl;
36 }
37 
38 // Returns true if the given ValueDecl is never written to in the given DeclBody
40  // Only local and static variables can be pseudoconstants
41  if (!VD->hasLocalStorage() && !VD->isStaticLocal())
42  return false;
43 
44  if (!Analyzed) {
45  RunAnalysis();
46  Analyzed = true;
47  }
48 
49  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
50 
51  return !NonConstants->count(VD);
52 }
53 
54 // Returns true if the variable was used (self assignments don't count)
56  if (!Analyzed) {
57  RunAnalysis();
58  Analyzed = true;
59  }
60 
61  VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
62 
63  return UsedVars->count(VD);
64 }
65 
66 // Returns a Decl from a (Block)DeclRefExpr (if any)
67 const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) {
68  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
69  return DR->getDecl();
70  else
71  return nullptr;
72 }
73 
74 void PseudoConstantAnalysis::RunAnalysis() {
75  std::deque<const Stmt *> WorkList;
76  VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
77  VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
78 
79  // Start with the top level statement of the function
80  WorkList.push_back(DeclBody);
81 
82  while (!WorkList.empty()) {
83  const Stmt *Head = WorkList.front();
84  WorkList.pop_front();
85 
86  if (const Expr *Ex = dyn_cast<Expr>(Head))
87  Head = Ex->IgnoreParenCasts();
88 
89  switch (Head->getStmtClass()) {
90  // Case 1: Assignment operators modifying VarDecls
91  case Stmt::BinaryOperatorClass: {
92  const BinaryOperator *BO = cast<BinaryOperator>(Head);
93  // Look for a Decl on the LHS
94  const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts());
95  if (!LHSDecl)
96  break;
97 
98  // We found a binary operator with a DeclRefExpr on the LHS. We now check
99  // for any of the assignment operators, implying that this Decl is being
100  // written to.
101  switch (BO->getOpcode()) {
102  // Self-assignments don't count as use of a variable
103  case BO_Assign: {
104  // Look for a DeclRef on the RHS
105  const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts());
106 
107  // If the Decls match, we have self-assignment
108  if (LHSDecl == RHSDecl)
109  // Do not visit the children
110  continue;
111 
112  LLVM_FALLTHROUGH;
113  }
114  case BO_AddAssign:
115  case BO_SubAssign:
116  case BO_MulAssign:
117  case BO_DivAssign:
118  case BO_AndAssign:
119  case BO_OrAssign:
120  case BO_XorAssign:
121  case BO_ShlAssign:
122  case BO_ShrAssign: {
123  const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl);
124  // The DeclRefExpr is being assigned to - mark it as non-constant
125  if (VD)
126  NonConstants->insert(VD);
127  break;
128  }
129 
130  default:
131  break;
132  }
133  break;
134  }
135 
136  // Case 2: Pre/post increment/decrement and address of
137  case Stmt::UnaryOperatorClass: {
138  const UnaryOperator *UO = cast<UnaryOperator>(Head);
139 
140  // Look for a DeclRef in the subexpression
141  const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts());
142  if (!D)
143  break;
144 
145  // We found a unary operator with a DeclRef as a subexpression. We now
146  // check for any of the increment/decrement operators, as well as
147  // addressOf.
148  switch (UO->getOpcode()) {
149  case UO_PostDec:
150  case UO_PostInc:
151  case UO_PreDec:
152  case UO_PreInc:
153  // The DeclRef is being changed - mark it as non-constant
154  case UO_AddrOf: {
155  // If we are taking the address of the DeclRefExpr, assume it is
156  // non-constant.
157  const VarDecl *VD = dyn_cast<VarDecl>(D);
158  if (VD)
159  NonConstants->insert(VD);
160  break;
161  }
162 
163  default:
164  break;
165  }
166  break;
167  }
168 
169  // Case 3: Reference Declarations
170  case Stmt::DeclStmtClass: {
171  const DeclStmt *DS = cast<DeclStmt>(Head);
172  // Iterate over each decl and see if any of them contain reference decls
173  for (const auto *I : DS->decls()) {
174  // We only care about VarDecls
175  const VarDecl *VD = dyn_cast<VarDecl>(I);
176  if (!VD)
177  continue;
178 
179  // We found a VarDecl; make sure it is a reference type
180  if (!VD->getType().getTypePtr()->isReferenceType())
181  continue;
182 
183  // Try to find a Decl in the initializer
184  const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts());
185  if (!D)
186  break;
187 
188  // If the reference is to another var, add the var to the non-constant
189  // list
190  if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) {
191  NonConstants->insert(RefVD);
192  continue;
193  }
194  }
195  break;
196  }
197 
198  // Case 4: Variable references
199  case Stmt::DeclRefExprClass: {
200  const DeclRefExpr *DR = cast<DeclRefExpr>(Head);
201  if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
202  // Add the Decl to the used list
203  UsedVars->insert(VD);
204  continue;
205  }
206  break;
207  }
208 
209  // Case 5: Block expressions
210  case Stmt::BlockExprClass: {
211  const BlockExpr *B = cast<BlockExpr>(Head);
212  // Add the body of the block to the list
213  WorkList.push_back(B->getBody());
214  continue;
215  }
216 
217  default:
218  break;
219  } // switch (head->getStmtClass())
220 
221  // Add all substatements to the worklist
222  for (const Stmt *SubStmt : Head->children())
223  if (SubStmt)
224  WorkList.push_back(SubStmt);
225  } // while (!WorkList.empty())
226 }
Stmt - This represents one statement.
Definition: Stmt.h:60
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:81
Opcode getOpcode() const
Definition: Expr.h:3027
VarDecl - An instance of this class is created to represent a variable declaration or definition...
Definition: Decl.h:771
bool isReferenceType() const
Definition: Type.h:5775
child_range children()
Definition: Stmt.cpp:208
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:2986
Expr * IgnoreParenCasts() LLVM_READONLY
IgnoreParenCasts - Ignore parentheses and casts.
Definition: Expr.cpp:2463
const Type * getTypePtr() const
Retrieves a pointer to the underlying (unqualified) type.
Definition: Type.h:5543
const Stmt * getBody() const
Definition: Expr.cpp:2012
Expr - This represents one expression.
Definition: Expr.h:106
bool hasLocalStorage() const
hasLocalStorage - Returns true if a variable with function scope is a non-static local variable...
Definition: Decl.h:976
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
Definition: Expr.h:4852
UnaryOperator - This represents the unary-expression&#39;s (except sizeof and alignof), the postinc/postdec operators from postfix-expression, and various extensions.
Definition: Expr.h:1717
PseudoConstantAnalysis(const Stmt *DeclBody)
bool wasReferenced(const VarDecl *VD)
ValueDecl * getDecl()
Definition: Expr.h:1041
#define false
Definition: stdbool.h:33
Expr * getSubExpr() const
Definition: Expr.h:1744
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:467
llvm::SmallPtrSet< const VarDecl *, 32 > VarDeclSet
Expr * getLHS() const
Definition: Expr.h:3030
Dataflow Directional Tag Classes.
const Expr * getInit() const
Definition: Decl.h:1159
StmtClass getStmtClass() const
Definition: Stmt.h:361
bool isPseudoConstant(const VarDecl *VD)
bool isStaticLocal() const
isStaticLocal - Returns true if a variable with function scope is a static local variable.
Definition: Decl.h:1000
Opcode getOpcode() const
Definition: Expr.h:1741
decl_range decls()
Definition: Stmt.h:515
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:956
Expr * getRHS() const
Definition: Expr.h:3032
QualType getType() const
Definition: Decl.h:602