1 files changed, 227 insertions, 0 deletions
diff --git a/clang/lib/Analysis/PseudoConstantAnalysis.cpp b/clang/lib/Analysis/PseudoConstantAnalysis.cpp
new file mode 100644
index 0000000..c8b491a
--- /dev/null
+++ b/clang/lib/Analysis/PseudoConstantAnalysis.cpp
@@ -0,0 +1,227 @@
+//== 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
+    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: 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 5: 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())
+}