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 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 }
    226