| //== 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 if (const BlockDeclRefExpr *BDR = dyn_cast<BlockDeclRefExpr>(E)) |
| return BDR->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: Block variable references |
| case Stmt::BlockDeclRefExprClass: { |
| const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(Head); |
| if (const VarDecl *VD = dyn_cast<VarDecl>(BDR->getDecl())) { |
| // Add the Decl to the used list |
| UsedVars->insert(VD); |
| continue; |
| } |
| break; |
| } |
| |
| // Case 5: 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 6: 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()) |
| } |