contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp

   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
  27 PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) :
  28       DeclBody(DeclBody), Analyzed(false) {
  29   NonConstantsImpl = new VarDeclSet;
  30   UsedVarsImpl = new VarDeclSet;
  31 }
  32
  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
  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)
  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)
  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       }
 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 }