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 "llvm/ADT/SmallPtrSet.h"
     21 #include <deque>
     22 
     23 using namespace clang;
     24 
     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;
     32   UsedVarsImpl = new VarDeclSet;
     33 }
     34 
     35 PseudoConstantAnalysis::~PseudoConstantAnalysis() {
     36   delete (VarDeclSet*)NonConstantsImpl;
     37   delete (VarDeclSet*)UsedVarsImpl;
     38 }
     39 
     40 // Returns true if the given ValueDecl is never written to in the given DeclBody
     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 
     46   if (!Analyzed) {
     47     RunAnalysis();
     48     Analyzed = true;
     49   }
     50 
     51   VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
     52 
     53   return !NonConstants->count(VD);
     54 }
     55 
     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 
     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();
     72   else
     73     return 0;
     74 }
     75 
     76 void PseudoConstantAnalysis::RunAnalysis() {
     77   std::deque<const Stmt *> WorkList;
     78   VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
     79   VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl;
     80 
     81   // Start with the top level statement of the function
     82   WorkList.push_back(DeclBody);
     83 
     84   while (!WorkList.empty()) {
     85     const Stmt *Head = WorkList.front();
     86     WorkList.pop_front();
     87 
     88     if (const Expr *Ex = dyn_cast<Expr>(Head))
     89       Head = Ex->IgnoreParenCasts();
     90 
     91     switch (Head->getStmtClass()) {
     92     // Case 1: Assignment operators modifying VarDecls
     93     case Stmt::BinaryOperatorClass: {
     94       const BinaryOperator *BO = cast<BinaryOperator>(Head);
     95       // Look for a Decl on the LHS
     96       const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts());
     97       if (!LHSDecl)
     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()) {
    104       // Self-assignments don't count as use of a variable
    105       case BO_Assign: {
    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;
    113 
    114       }
    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: {
    124         const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl);
    125         // The DeclRefExpr is being assigned to - mark it as non-constant
    126         if (VD)
    127           NonConstants->insert(VD);
    128         break;
    129       }
    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);
    140 
    141       // Look for a DeclRef in the subexpression
    142       const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts());
    143       if (!D)
    144         break;
    145 
    146       // We found a unary operator with a DeclRef as a subexpression. We now
    147       // check for any of the increment/decrement operators, as well as
    148       // addressOf.
    149       switch (UO->getOpcode()) {
    150       case UO_PostDec:
    151       case UO_PostInc:
    152       case UO_PreDec:
    153       case UO_PreInc:
    154         // The DeclRef is being changed - mark it as non-constant
    155       case UO_AddrOf: {
    156         // If we are taking the address of the DeclRefExpr, assume it is
    157         // non-constant.
    158         const VarDecl *VD = dyn_cast<VarDecl>(D);
    159         if (VD)
    160           NonConstants->insert(VD);
    161         break;
    162       }
    163 
    164       default:
    165         break;
    166       }
    167       break;
    168     }
    169 
    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
    174       for (DeclStmt::const_decl_iterator I = DS->decl_begin(),
    175           E = DS->decl_end(); I != E; ++I) {
    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 
    185         // Try to find a Decl in the initializer
    186         const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts());
    187         if (!D)
    188           break;
    189 
    190         // If the reference is to another var, add the var to the non-constant
    191         // list
    192         if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) {
    193           NonConstants->insert(RefVD);
    194           continue;
    195         }
    196       }
    197       break;
    198     }
    199 
    200     // Case 4: Variable references
    201     case Stmt::DeclRefExprClass: {
    202       const DeclRefExpr *DR = cast<DeclRefExpr>(Head);
    203       if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
    204         // Add the Decl to the used list
    205         UsedVars->insert(VD);
    206         continue;
    207       }
    208       break;
    209     }
    210 
    211     // Case 5: Block expressions
    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 
    219     default:
    220       break;
    221     } // switch (head->getStmtClass())
    222 
    223     // Add all substatements to the worklist
    224     for (Stmt::const_child_range I = Head->children(); I; ++I)
    225       if (*I)
    226         WorkList.push_back(*I);
    227   } // while (!WorkList.empty())
    228 }
    229