• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
23 using namespace clang;
24 
25 typedef llvm::SmallPtrSet<const VarDecl*, 32> VarDeclSet;
26 
PseudoConstantAnalysis(const Stmt * DeclBody)27 PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) :
28       DeclBody(DeclBody), Analyzed(false) {
29   NonConstantsImpl = new VarDeclSet;
30   UsedVarsImpl = new VarDeclSet;
31 }
32 
~PseudoConstantAnalysis()33 PseudoConstantAnalysis::~PseudoConstantAnalysis() {
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
isPseudoConstant(const VarDecl * VD)39 bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) {
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)
wasReferenced(const VarDecl * VD)55 bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) {
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)
getDecl(const Expr * E)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 
RunAnalysis()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       }
113       case BO_AddAssign:
114       case BO_SubAssign:
115       case BO_MulAssign:
116       case BO_DivAssign:
117       case BO_AndAssign:
118       case BO_OrAssign:
119       case BO_XorAssign:
120       case BO_ShlAssign:
121       case BO_ShrAssign: {
122         const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl);
123         // The DeclRefExpr is being assigned to - mark it as non-constant
124         if (VD)
125           NonConstants->insert(VD);
126         break;
127       }
128 
129       default:
130         break;
131       }
132       break;
133     }
134 
135     // Case 2: Pre/post increment/decrement and address of
136     case Stmt::UnaryOperatorClass: {
137       const UnaryOperator *UO = cast<UnaryOperator>(Head);
138 
139       // Look for a DeclRef in the subexpression
140       const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts());
141       if (!D)
142         break;
143 
144       // We found a unary operator with a DeclRef as a subexpression. We now
145       // check for any of the increment/decrement operators, as well as
146       // addressOf.
147       switch (UO->getOpcode()) {
148       case UO_PostDec:
149       case UO_PostInc:
150       case UO_PreDec:
151       case UO_PreInc:
152         // The DeclRef is being changed - mark it as non-constant
153       case UO_AddrOf: {
154         // If we are taking the address of the DeclRefExpr, assume it is
155         // non-constant.
156         const VarDecl *VD = dyn_cast<VarDecl>(D);
157         if (VD)
158           NonConstants->insert(VD);
159         break;
160       }
161 
162       default:
163         break;
164       }
165       break;
166     }
167 
168     // Case 3: Reference Declarations
169     case Stmt::DeclStmtClass: {
170       const DeclStmt *DS = cast<DeclStmt>(Head);
171       // Iterate over each decl and see if any of them contain reference decls
172       for (const auto *I : DS->decls()) {
173         // We only care about VarDecls
174         const VarDecl *VD = dyn_cast<VarDecl>(I);
175         if (!VD)
176           continue;
177 
178         // We found a VarDecl; make sure it is a reference type
179         if (!VD->getType().getTypePtr()->isReferenceType())
180           continue;
181 
182         // Try to find a Decl in the initializer
183         const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts());
184         if (!D)
185           break;
186 
187         // If the reference is to another var, add the var to the non-constant
188         // list
189         if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) {
190           NonConstants->insert(RefVD);
191           continue;
192         }
193       }
194       break;
195     }
196 
197     // Case 4: Variable references
198     case Stmt::DeclRefExprClass: {
199       const DeclRefExpr *DR = cast<DeclRefExpr>(Head);
200       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
201         // Add the Decl to the used list
202         UsedVars->insert(VD);
203         continue;
204       }
205       break;
206     }
207 
208     // Case 5: Block expressions
209     case Stmt::BlockExprClass: {
210       const BlockExpr *B = cast<BlockExpr>(Head);
211       // Add the body of the block to the list
212       WorkList.push_back(B->getBody());
213       continue;
214     }
215 
216     default:
217       break;
218     } // switch (head->getStmtClass())
219 
220     // Add all substatements to the worklist
221     for (const Stmt *SubStmt : Head->children())
222       if (SubStmt)
223         WorkList.push_back(SubStmt);
224   } // while (!WorkList.empty())
225 }
226