Several small changes to PseudoConstantAnalysis and the way IdempotentOperationChecker uses it.
- Psuedo -> Pseudo (doh...)
- C++ reference support
- Added pseudoconstant test case for __block vars
- Separated out static local checking from pseudoconstant analysis and generalized to non-local checking
- Added missing test cases for storage false positives
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@111832 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp
index 934a031..2c337f0 100644
--- a/lib/Analysis/AnalysisContext.cpp
+++ b/lib/Analysis/AnalysisContext.cpp
@@ -18,7 +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/Analyses/PseudoConstantAnalysis.h"
#include "clang/Analysis/AnalysisContext.h"
#include "clang/Analysis/CFG.h"
#include "clang/Analysis/Support/BumpVector.h"
@@ -84,9 +84,9 @@
return *PM;
}
-PsuedoConstantAnalysis *AnalysisContext::getPsuedoConstantAnalysis() {
+PseudoConstantAnalysis *AnalysisContext::getPseudoConstantAnalysis() {
if (!PCA)
- PCA = new PsuedoConstantAnalysis(getBody());
+ PCA = new PseudoConstantAnalysis(getBody());
return PCA;
}
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index 514042b..850e9b4 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -7,7 +7,7 @@
FormatString.cpp
LiveVariables.cpp
PrintfFormatString.cpp
- PsuedoConstantAnalysis.cpp
+ PseudoConstantAnalysis.cpp
ReachableCode.cpp
ScanfFormatString.cpp
UninitializedValues.cpp
diff --git a/lib/Analysis/PsuedoConstantAnalysis.cpp b/lib/Analysis/PseudoConstantAnalysis.cpp
similarity index 60%
rename from lib/Analysis/PsuedoConstantAnalysis.cpp
rename to lib/Analysis/PseudoConstantAnalysis.cpp
index a169f89..7a2fa8a 100644
--- a/lib/Analysis/PsuedoConstantAnalysis.cpp
+++ b/lib/Analysis/PseudoConstantAnalysis.cpp
@@ -1,4 +1,4 @@
-//== PsuedoConstantAnalysis.cpp - Find Psuedoconstants in the AST-*- C++ -*-==//
+//== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- C++ -*-==//
//
// The LLVM Compiler Infrastructure
//
@@ -13,7 +13,7 @@
//
//===----------------------------------------------------------------------===//
-#include "clang/Analysis/Analyses/PsuedoConstantAnalysis.h"
+#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
#include "clang/AST/Decl.h"
#include "clang/AST/Expr.h"
#include "clang/AST/Stmt.h"
@@ -21,18 +21,38 @@
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;
+}
+
+PseudoConstantAnalysis::~PseudoConstantAnalysis() {
+ delete (VarDeclSet*)NonConstantsImpl;
+}
+
// Returns true if the given ValueDecl is never written to in the given DeclBody
-bool PsuedoConstantAnalysis::isPsuedoConstant(const ValueDecl *VD) {
+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;
}
- return !NonConstants.count(VD);
+ VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
+
+ return !NonConstants->count(VD);
}
-void PsuedoConstantAnalysis::RunAnalysis() {
+void PseudoConstantAnalysis::RunAnalysis() {
std::deque<const Stmt *> WorkList;
+ VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl;
// Start with the top level statement of the function
WorkList.push_back(DeclBody);
@@ -65,10 +85,13 @@
case BinaryOperator::OrAssign:
case BinaryOperator::XorAssign:
case BinaryOperator::ShlAssign:
- case BinaryOperator::ShrAssign:
+ case BinaryOperator::ShrAssign: {
// The DeclRefExpr is being assigned to - mark it as non-constant
- NonConstants.insert(DR->getDecl());
- continue; // Continue without looking at children
+ const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
+ if (VD)
+ NonConstants->insert(VD);
+ break;
+ }
default:
break;
@@ -95,10 +118,14 @@
case UnaryOperator::PreDec:
case UnaryOperator::PreInc:
// The DeclRefExpr is being changed - mark it as non-constant
- case UnaryOperator::AddrOf:
+ case UnaryOperator::AddrOf: {
// If we are taking the address of the DeclRefExpr, assume it is
// non-constant.
- NonConstants.insert(DR->getDecl());
+ const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
+ if (VD)
+ NonConstants->insert(VD);
+ break;
+ }
default:
break;
@@ -106,6 +133,33 @@
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;
+
+ // Ignore VarDecls without a body
+ if (!VD->getBody())
+ continue;
+
+ // If the reference is to another var, add the var to the non-constant
+ // list
+ if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(VD->getBody()))
+ if (const VarDecl *RefVD = dyn_cast<VarDecl>(DR->getDecl()))
+ NonConstants->insert(RefVD);
+ }
+ }
+
default:
break;
} // switch (head->getStmtClass())
diff --git a/lib/Checker/IdempotentOperationChecker.cpp b/lib/Checker/IdempotentOperationChecker.cpp
index 885123a..2cfcaa4 100644
--- a/lib/Checker/IdempotentOperationChecker.cpp
+++ b/lib/Checker/IdempotentOperationChecker.cpp
@@ -44,7 +44,7 @@
#include "GRExprEngineExperimentalChecks.h"
#include "clang/Analysis/CFGStmtMap.h"
-#include "clang/Analysis/Analyses/PsuedoConstantAnalysis.h"
+#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
#include "clang/Checker/BugReporter/BugType.h"
#include "clang/Checker/PathSensitive/CheckerHelpers.h"
#include "clang/Checker/PathSensitive/CheckerVisitor.h"
@@ -83,6 +83,7 @@
static bool CanVary(const Expr *Ex, AnalysisContext *AC);
static bool isConstantOrPseudoConstant(const DeclRefExpr *DR,
AnalysisContext *AC);
+ static bool containsNonLocalVarDecl(const Stmt *S);
// Hash table
typedef llvm::DenseMap<const BinaryOperator *,
@@ -122,12 +123,17 @@
const Expr *LHS = B->getLHS();
const Expr *RHS = B->getRHS();
- // Check if either side can vary. We only need to calculate this when we have
- // no assumption.
- bool LHSCanVary = true, RHSCanVary = true;
+ // At this stage we can calculate whether each side contains a false positive
+ // that applies to all operators. We only need to calculate this the first
+ // time.
+ bool LHSContainsFalsePositive = false, RHSContainsFalsePositive = false;
if (A == Possible) {
- LHSCanVary = CanVary(LHS, AC);
- RHSCanVary = CanVary(RHS, AC);
+ // An expression contains a false positive if it can't vary, or if it
+ // contains a known false positive VarDecl.
+ LHSContainsFalsePositive = !CanVary(LHS, AC)
+ || containsNonLocalVarDecl(LHS);
+ RHSContainsFalsePositive = !CanVary(RHS, AC)
+ || containsNonLocalVarDecl(RHS);
}
const GRState *state = C.getState();
@@ -195,7 +201,8 @@
case BinaryOperator::Xor:
case BinaryOperator::LOr:
case BinaryOperator::LAnd:
- if (LHSVal != RHSVal || !LHSCanVary || !RHSCanVary)
+ if (LHSVal != RHSVal || LHSContainsFalsePositive
+ || RHSContainsFalsePositive)
break;
UpdateAssumption(A, Equal);
return;
@@ -213,7 +220,7 @@
case BinaryOperator::Div:
case BinaryOperator::LOr:
case BinaryOperator::LAnd:
- if (!RHSVal.isConstant(1) || !RHSCanVary)
+ if (!RHSVal.isConstant(1) || RHSContainsFalsePositive)
break;
UpdateAssumption(A, RHSis1);
return;
@@ -229,7 +236,7 @@
case BinaryOperator::Mul:
case BinaryOperator::LOr:
case BinaryOperator::LAnd:
- if (!LHSVal.isConstant(1) || !LHSCanVary)
+ if (!LHSVal.isConstant(1) || LHSContainsFalsePositive)
break;
UpdateAssumption(A, LHSis1);
return;
@@ -257,7 +264,7 @@
case BinaryOperator::Shr:
case BinaryOperator::LOr:
case BinaryOperator::LAnd:
- if (!RHSVal.isConstant(0) || !RHSCanVary)
+ if (!RHSVal.isConstant(0) || RHSContainsFalsePositive)
break;
UpdateAssumption(A, RHSis0);
return;
@@ -289,7 +296,7 @@
case BinaryOperator::Shr:
case BinaryOperator::LOr:
case BinaryOperator::LAnd:
- if (!LHSVal.isConstant(0) || !LHSCanVary)
+ if (!LHSVal.isConstant(0) || LHSContainsFalsePositive)
break;
UpdateAssumption(A, LHSis0);
return;
@@ -578,16 +585,35 @@
if (isa<EnumConstantDecl>(DR->getDecl()))
return true;
- // Check for a static variable
- // FIXME: Analysis should model static vars
- if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
- if (VD->isStaticLocal())
- return true;
-
- // Check if the Decl behaves like a constant
- PsuedoConstantAnalysis *PCA = AC->getPsuedoConstantAnalysis();
- if (PCA->isPsuedoConstant(DR->getDecl()))
+ const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
+ if (!VD)
return true;
+ // Check if the Decl behaves like a constant. This check also takes care of
+ // static variables, which can only change between function calls if they are
+ // modified in the AST.
+ PseudoConstantAnalysis *PCA = AC->getPseudoConstantAnalysis();
+ if (PCA->isPseudoConstant(VD))
+ return true;
+
+ return false;
+}
+
+// Recursively find any substatements containing VarDecl's with storage other
+// than local
+bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) {
+ const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S);
+
+ if (DR)
+ if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
+ if (!VD->hasLocalStorage())
+ return true;
+
+ for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
+ ++I)
+ if (const Stmt *child = *I)
+ if (containsNonLocalVarDecl(child))
+ return true;
+
return false;
}