Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 1 | //== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- C++ -*-==// |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 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 | |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 16 | #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 17 | #include "clang/AST/Decl.h" |
| 18 | #include "clang/AST/Expr.h" |
| 19 | #include "clang/AST/Stmt.h" |
Benjamin Kramer | 478851c | 2012-07-04 17:04:04 +0000 | [diff] [blame] | 20 | #include "llvm/ADT/SmallPtrSet.h" |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 21 | #include <deque> |
| 22 | |
| 23 | using namespace clang; |
| 24 | |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 25 | // The number of ValueDecls we want to keep track of by default (per-function) |
| 26 | #define VARDECL_SET_SIZE 256 |
| 27 | typedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet; |
| 28 | |
| 29 | PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) : |
| 30 | DeclBody(DeclBody), Analyzed(false) { |
| 31 | NonConstantsImpl = new VarDeclSet; |
Tom Care | ef52bcb | 2010-08-24 21:09:07 +0000 | [diff] [blame] | 32 | UsedVarsImpl = new VarDeclSet; |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 33 | } |
| 34 | |
| 35 | PseudoConstantAnalysis::~PseudoConstantAnalysis() { |
| 36 | delete (VarDeclSet*)NonConstantsImpl; |
Tom Care | ef52bcb | 2010-08-24 21:09:07 +0000 | [diff] [blame] | 37 | delete (VarDeclSet*)UsedVarsImpl; |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 38 | } |
| 39 | |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 40 | // Returns true if the given ValueDecl is never written to in the given DeclBody |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 41 | bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) { |
| 42 | // Only local and static variables can be pseudoconstants |
| 43 | if (!VD->hasLocalStorage() && !VD->isStaticLocal()) |
| 44 | return false; |
| 45 | |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 46 | if (!Analyzed) { |
| 47 | RunAnalysis(); |
| 48 | Analyzed = true; |
| 49 | } |
| 50 | |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 51 | VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; |
| 52 | |
| 53 | return !NonConstants->count(VD); |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 54 | } |
| 55 | |
Tom Care | ef52bcb | 2010-08-24 21:09:07 +0000 | [diff] [blame] | 56 | // Returns true if the variable was used (self assignments don't count) |
| 57 | bool 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 | |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 68 | // Returns a Decl from a (Block)DeclRefExpr (if any) |
| 69 | const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) { |
| 70 | if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) |
| 71 | return DR->getDecl(); |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 72 | else |
| 73 | return 0; |
| 74 | } |
| 75 | |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 76 | void PseudoConstantAnalysis::RunAnalysis() { |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 77 | std::deque<const Stmt *> WorkList; |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 78 | VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; |
Tom Care | ef52bcb | 2010-08-24 21:09:07 +0000 | [diff] [blame] | 79 | VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 80 | |
| 81 | // Start with the top level statement of the function |
| 82 | WorkList.push_back(DeclBody); |
| 83 | |
| 84 | while (!WorkList.empty()) { |
Ted Kremenek | 9c378f7 | 2011-08-12 23:37:29 +0000 | [diff] [blame] | 85 | const Stmt *Head = WorkList.front(); |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 86 | WorkList.pop_front(); |
| 87 | |
Ted Kremenek | 892697d | 2010-12-16 07:46:53 +0000 | [diff] [blame] | 88 | if (const Expr *Ex = dyn_cast<Expr>(Head)) |
| 89 | Head = Ex->IgnoreParenCasts(); |
| 90 | |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 91 | switch (Head->getStmtClass()) { |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 92 | // Case 1: Assignment operators modifying VarDecls |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 93 | case Stmt::BinaryOperatorClass: { |
| 94 | const BinaryOperator *BO = cast<BinaryOperator>(Head); |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 95 | // Look for a Decl on the LHS |
| 96 | const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts()); |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 97 | if (!LHSDecl) |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 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()) { |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 104 | // Self-assignments don't count as use of a variable |
John McCall | 2de56d1 | 2010-08-25 11:45:40 +0000 | [diff] [blame] | 105 | case BO_Assign: { |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 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; |
Tom Care | ef52bcb | 2010-08-24 21:09:07 +0000 | [diff] [blame] | 113 | |
| 114 | } |
John McCall | 2de56d1 | 2010-08-25 11:45:40 +0000 | [diff] [blame] | 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: { |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 124 | const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl); |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 125 | // The DeclRefExpr is being assigned to - mark it as non-constant |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 126 | if (VD) |
| 127 | NonConstants->insert(VD); |
| 128 | break; |
| 129 | } |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 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); |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 140 | |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 141 | // Look for a DeclRef in the subexpression |
| 142 | const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts()); |
Tom Care | 916d054 | 2010-08-25 22:46:03 +0000 | [diff] [blame] | 143 | if (!D) |
| 144 | break; |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 145 | |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 146 | // We found a unary operator with a DeclRef as a subexpression. We now |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 147 | // check for any of the increment/decrement operators, as well as |
| 148 | // addressOf. |
| 149 | switch (UO->getOpcode()) { |
John McCall | 2de56d1 | 2010-08-25 11:45:40 +0000 | [diff] [blame] | 150 | case UO_PostDec: |
| 151 | case UO_PostInc: |
| 152 | case UO_PreDec: |
| 153 | case UO_PreInc: |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 154 | // The DeclRef is being changed - mark it as non-constant |
John McCall | 2de56d1 | 2010-08-25 11:45:40 +0000 | [diff] [blame] | 155 | case UO_AddrOf: { |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 156 | // If we are taking the address of the DeclRefExpr, assume it is |
| 157 | // non-constant. |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 158 | const VarDecl *VD = dyn_cast<VarDecl>(D); |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 159 | if (VD) |
| 160 | NonConstants->insert(VD); |
| 161 | break; |
| 162 | } |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 163 | |
| 164 | default: |
| 165 | break; |
| 166 | } |
| 167 | break; |
| 168 | } |
| 169 | |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 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 |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 174 | for (DeclStmt::const_decl_iterator I = DS->decl_begin(), |
| 175 | E = DS->decl_end(); I != E; ++I) { |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 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 | |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 185 | // Try to find a Decl in the initializer |
| 186 | const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts()); |
Tom Care | 916d054 | 2010-08-25 22:46:03 +0000 | [diff] [blame] | 187 | if (!D) |
| 188 | break; |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 189 | |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 190 | // If the reference is to another var, add the var to the non-constant |
| 191 | // list |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 192 | if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) { |
| 193 | NonConstants->insert(RefVD); |
| 194 | continue; |
| 195 | } |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 196 | } |
Tom Care | ef52bcb | 2010-08-24 21:09:07 +0000 | [diff] [blame] | 197 | break; |
| 198 | } |
| 199 | |
John McCall | f4b88a4 | 2012-03-10 09:33:50 +0000 | [diff] [blame] | 200 | // Case 4: Variable references |
Tom Care | ef52bcb | 2010-08-24 21:09:07 +0000 | [diff] [blame] | 201 | case Stmt::DeclRefExprClass: { |
| 202 | const DeclRefExpr *DR = cast<DeclRefExpr>(Head); |
| 203 | if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 204 | // Add the Decl to the used list |
Tom Care | ef52bcb | 2010-08-24 21:09:07 +0000 | [diff] [blame] | 205 | UsedVars->insert(VD); |
| 206 | continue; |
| 207 | } |
| 208 | break; |
Tom Care | db34ab7 | 2010-08-23 19:51:57 +0000 | [diff] [blame] | 209 | } |
| 210 | |
John McCall | f4b88a4 | 2012-03-10 09:33:50 +0000 | [diff] [blame] | 211 | // Case 5: Block expressions |
Tom Care | 967fea6 | 2010-08-25 22:37:26 +0000 | [diff] [blame] | 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 | |
Ted Kremenek | 892697d | 2010-12-16 07:46:53 +0000 | [diff] [blame] | 219 | default: |
| 220 | break; |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 221 | } // switch (head->getStmtClass()) |
| 222 | |
| 223 | // Add all substatements to the worklist |
John McCall | 7502c1d | 2011-02-13 04:07:26 +0000 | [diff] [blame] | 224 | for (Stmt::const_child_range I = Head->children(); I; ++I) |
Tom Care | 245adab | 2010-08-18 21:17:24 +0000 | [diff] [blame] | 225 | if (*I) |
| 226 | WorkList.push_back(*I); |
| 227 | } // while (!WorkList.empty()) |
| 228 | } |