3 files changed, 128 insertions, 0 deletions

diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp
index ced4f1dd2e..934a031b3a 100644
--- a/lib/Analysis/AnalysisContext.cpp
+++ b/lib/Analysis/AnalysisContext.cpp
@@ -18,6 +18,7 @@
 #include "clang/AST/ParentMap.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Analysis/Analyses/LiveVariables.h"
+#include "clang/Analysis/Analyses/PsuedoConstantAnalysis.h"
 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/Support/BumpVector.h"
@@ -83,6 +84,12 @@ ParentMap &AnalysisContext::getParentMap() {
   return *PM;
 }
 
+PsuedoConstantAnalysis *AnalysisContext::getPsuedoConstantAnalysis() {
+  if (!PCA)
+    PCA = new PsuedoConstantAnalysis(getBody());
+  return PCA;
+}
+
 LiveVariables *AnalysisContext::getLiveVariables() {
   if (!liveness) {
     CFG *c = getCFG();
@@ -314,6 +321,7 @@ AnalysisContext::~AnalysisContext() {
   delete completeCFG;
   delete liveness;
   delete PM;
+  delete PCA;
   delete ReferencedBlockVars;
 }
 
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index 8d576a9386..514042bf9a 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -7,6 +7,7 @@ add_clang_library(clangAnalysis
   FormatString.cpp
   LiveVariables.cpp
   PrintfFormatString.cpp
+  PsuedoConstantAnalysis.cpp
   ReachableCode.cpp
   ScanfFormatString.cpp
   UninitializedValues.cpp
diff --git a/lib/Analysis/PsuedoConstantAnalysis.cpp b/lib/Analysis/PsuedoConstantAnalysis.cpp
new file mode 100644
index 0000000000..a169f89fe1
--- /dev/null
+++ b/lib/Analysis/PsuedoConstantAnalysis.cpp
@@ -0,0 +1,119 @@
+//== PsuedoConstantAnalysis.cpp - Find Psuedoconstants 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/PsuedoConstantAnalysis.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/Stmt.h"
+#include <deque>
+
+using namespace clang;
+
+// Returns true if the given ValueDecl is never written to in the given DeclBody
+bool PsuedoConstantAnalysis::isPsuedoConstant(const ValueDecl *VD) {
+  if (!Analyzed) {
+    RunAnalysis();
+    Analyzed = true;
+  }
+
+  return !NonConstants.count(VD);
+}
+
+void PsuedoConstantAnalysis::RunAnalysis() {
+  std::deque<const Stmt *> WorkList;
+
+  // Start with the top level statement of the function
+  WorkList.push_back(DeclBody);
+
+  while (!WorkList.empty()) {
+    const Stmt* Head = WorkList.front();
+    WorkList.pop_front();
+
+    switch (Head->getStmtClass()) {
+    // Case 1: Assignment operators modifying ValueDecl
+    case Stmt::BinaryOperatorClass: {
+      const BinaryOperator *BO = cast<BinaryOperator>(Head);
+      const Expr *LHS = BO->getLHS()->IgnoreParenImpCasts();
+      const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS);
+
+      // We only care about DeclRefExprs on the LHS
+      if (!DR)
+        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()) {
+      case BinaryOperator::Assign:
+      case BinaryOperator::AddAssign:
+      case BinaryOperator::SubAssign:
+      case BinaryOperator::MulAssign:
+      case BinaryOperator::DivAssign:
+      case BinaryOperator::AndAssign:
+      case BinaryOperator::OrAssign:
+      case BinaryOperator::XorAssign:
+      case BinaryOperator::ShlAssign:
+      case BinaryOperator::ShrAssign:
+        // The DeclRefExpr is being assigned to - mark it as non-constant
+        NonConstants.insert(DR->getDecl());
+        continue; // Continue without looking at children
+
+      default:
+        break;
+      }
+      break;
+    }
+
+    // Case 2: Pre/post increment/decrement and address of
+    case Stmt::UnaryOperatorClass: {
+      const UnaryOperator *UO = cast<UnaryOperator>(Head);
+      const Expr *SubExpr = UO->getSubExpr()->IgnoreParenImpCasts();
+      const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(SubExpr);
+
+      // We only care about DeclRefExprs in the subexpression
+      if (!DR)
+        break;
+
+      // We found a unary operator with a DeclRefExpr as a subexpression. We now
+      // check for any of the increment/decrement operators, as well as
+      // addressOf.
+      switch (UO->getOpcode()) {
+      case UnaryOperator::PostDec:
+      case UnaryOperator::PostInc:
+      case UnaryOperator::PreDec:
+      case UnaryOperator::PreInc:
+        // The DeclRefExpr is being changed - mark it as non-constant
+      case UnaryOperator::AddrOf:
+        // If we are taking the address of the DeclRefExpr, assume it is
+        // non-constant.
+        NonConstants.insert(DR->getDecl());
+
+      default:
+        break;
+      }
+      break;
+    }
+
+      default:
+        break;
+    } // switch (head->getStmtClass())
+
+    // Add all substatements to the worklist
+    for (Stmt::const_child_iterator I = Head->child_begin(),
+        E = Head->child_end(); I != E; ++I)
+      if (*I)
+        WorkList.push_back(*I);
+  } // while (!WorkList.empty())
+}