Home | History | Annotate | Download | only in Analysis 
      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 <deque>
     21 
     22 using namespace clang;
     23 
     24 // The number of ValueDecls we want to keep track of by default (per-function)
     25 #define VARDECL_SET_SIZE 256
     26 typedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet;
     27 
     28 PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) :
     29       DeclBody(DeclBody), Analyzed(false) {
     30   NonConstantsImpl = new VarDeclSet;
     31   UsedVarsImpl = new VarDeclSet;
     32 }
     33 
     34 PseudoConstantAnalysis::~PseudoConstantAnalysis() {
     35   delete (VarDeclSet*)NonConstantsImpl;
     36   delete (VarDeclSet*)UsedVarsImpl;
     37 }
     38 
     39 // Returns true if the given ValueDecl is never written to in the given DeclBody
     40 bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) {
     41   // Only local and static variables can be pseudoconstants
     42   if (!VD->hasLocalStorage() && !VD->isStaticLocal())
     43     return false;
     44 
     45   if (!Analyzed) {
     46     RunAnalysis();
     47     Analyzed = true;
     48   }
     49 
     50   VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
     51 
     52   return !NonConstants->count(VD);
     53 }
     54 
     55 // Returns true if the variable was used (self assignments don't count)
     56 bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) {
     57   if (!Analyzed) {
     58     RunAnalysis();
     59     Analyzed = true;
     60   }
     61 
     62   VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
     63 
     64   return UsedVars->count(VD);
     65 }
     66 
     67 // Returns a Decl from a (Block)DeclRefExpr (if any)
     68 const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) {
     69   if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
     70     return DR->getDecl();
     71   else if (const BlockDeclRefExpr *BDR = dyn_cast<BlockDeclRefExpr>(E))
     72     return BDR->getDecl();
     73   else
     74     return 0;
     75 }
     76 
     77 void PseudoConstantAnalysis::RunAnalysis() {
     78   std::deque<const Stmt *> WorkList;
     79   VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
     80   VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
     81 
     82   // Start with the top level statement of the function
     83   WorkList.push_back(DeclBody);
     84 
     85   while (!WorkList.empty()) {
     86     const Stmt *Head = WorkList.front();
     87     WorkList.pop_front();
     88 
     89     if (const Expr *Ex = dyn_cast<Expr>(Head))
     90       Head = Ex->IgnoreParenCasts();
     91 
     92     switch (Head->getStmtClass()) {
     93     // Case 1: Assignment operators modifying VarDecls
     94     case Stmt::BinaryOperatorClass: {
     95       const BinaryOperator *BO = cast<BinaryOperator>(Head);
     96       // Look for a Decl on the LHS
     97       const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts());
     98       if (!LHSDecl)
     99         break;
    100 
    101       // We found a binary operator with a DeclRefExpr on the LHS. We now check
    102       // for any of the assignment operators, implying that this Decl is being
    103       // written to.
    104       switch (BO->getOpcode()) {
    105       // Self-assignments don't count as use of a variable
    106       case BO_Assign: {
    107         // Look for a DeclRef on the RHS
    108         const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts());
    109 
    110         // If the Decls match, we have self-assignment
    111         if (LHSDecl == RHSDecl)
    112           // Do not visit the children
    113           continue;
    114 
    115       }
    116       case BO_AddAssign:
    117       case BO_SubAssign:
    118       case BO_MulAssign:
    119       case BO_DivAssign:
    120       case BO_AndAssign:
    121       case BO_OrAssign:
    122       case BO_XorAssign:
    123       case BO_ShlAssign:
    124       case BO_ShrAssign: {
    125         const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl);
    126         // The DeclRefExpr is being assigned to - mark it as non-constant
    127         if (VD)
    128           NonConstants->insert(VD);
    129         break;
    130       }
    131 
    132       default:
    133         break;
    134       }
    135       break;
    136     }
    137 
    138     // Case 2: Pre/post increment/decrement and address of
    139     case Stmt::UnaryOperatorClass: {
    140       const UnaryOperator *UO = cast<UnaryOperator>(Head);
    141 
    142       // Look for a DeclRef in the subexpression
    143       const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts());
    144       if (!D)
    145         break;
    146 
    147       // We found a unary operator with a DeclRef as a subexpression. We now
    148       // check for any of the increment/decrement operators, as well as
    149       // addressOf.
    150       switch (UO->getOpcode()) {
    151       case UO_PostDec:
    152       case UO_PostInc:
    153       case UO_PreDec:
    154       case UO_PreInc:
    155         // The DeclRef is being changed - mark it as non-constant
    156       case UO_AddrOf: {
    157         // If we are taking the address of the DeclRefExpr, assume it is
    158         // non-constant.
    159         const VarDecl *VD = dyn_cast<VarDecl>(D);
    160         if (VD)
    161           NonConstants->insert(VD);
    162         break;
    163       }
    164 
    165       default:
    166         break;
    167       }
    168       break;
    169     }
    170 
    171     // Case 3: Reference Declarations
    172     case Stmt::DeclStmtClass: {
    173       const DeclStmt *DS = cast<DeclStmt>(Head);
    174       // Iterate over each decl and see if any of them contain reference decls
    175       for (DeclStmt::const_decl_iterator I = DS->decl_begin(),
    176           E = DS->decl_end(); I != E; ++I) {
    177         // We only care about VarDecls
    178         const VarDecl *VD = dyn_cast<VarDecl>(*I);
    179         if (!VD)
    180           continue;
    181 
    182         // We found a VarDecl; make sure it is a reference type
    183         if (!VD->getType().getTypePtr()->isReferenceType())
    184           continue;
    185 
    186         // Try to find a Decl in the initializer
    187         const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts());
    188         if (!D)
    189           break;
    190 
    191         // If the reference is to another var, add the var to the non-constant
    192         // list
    193         if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) {
    194           NonConstants->insert(RefVD);
    195           continue;
    196         }
    197       }
    198       break;
    199     }
    200 
    201     // Case 4: Block variable references
    202     case Stmt::BlockDeclRefExprClass: {
    203       const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(Head);
    204       if (const VarDecl *VD = dyn_cast<VarDecl>(BDR->getDecl())) {
    205         // Add the Decl to the used list
    206         UsedVars->insert(VD);
    207         continue;
    208       }
    209       break;
    210     }
    211 
    212     // Case 5: Variable references
    213     case Stmt::DeclRefExprClass: {
    214       const DeclRefExpr *DR = cast<DeclRefExpr>(Head);
    215       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
    216         // Add the Decl to the used list
    217         UsedVars->insert(VD);
    218         continue;
    219       }
    220       break;
    221     }
    222 
    223     // Case 6: Block expressions
    224     case Stmt::BlockExprClass: {
    225       const BlockExpr *B = cast<BlockExpr>(Head);
    226       // Add the body of the block to the list
    227       WorkList.push_back(B->getBody());
    228       continue;
    229     }
    230 
    231     default:
    232       break;
    233     } // switch (head->getStmtClass())
    234 
    235     // Add all substatements to the worklist
    236     for (Stmt::const_child_range I = Head->children(); I; ++I)
    237       if (*I)
    238         WorkList.push_back(*I);
    239   } // while (!WorkList.empty())
    240 }
    241