Added psuedo-constant analysis and integrated it into the false positive reduction stage in IdempotentOperationChecker.
- Renamed IdempotentOperationChecker::isConstant to isConstantOrPseudoConstant to better reflect the function
- Changed IdempotentOperationChecker::PreVisitBinaryOperator to only run 'CanVary' once on undefined assumptions
- Created new PsuedoConstantAnalysis class and added it to AnalysisContext
- Changed IdempotentOperationChecker to exploit the new analysis
- Updated tests with psuedo-constants
- Added check to IdempotentOperationChecker to see if a Decl is const qualified
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@111426 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp
index ced4f1d..934a031 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 @@
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 @@
delete completeCFG;
delete liveness;
delete PM;
+ delete PCA;
delete ReferencedBlockVars;
}
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index 8d576a9..514042b 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -7,6 +7,7 @@
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 0000000..a169f89
--- /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())
+}