aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Analysis/AnalysisContext.cpp8
-rw-r--r--lib/Analysis/CMakeLists.txt1
-rw-r--r--lib/Analysis/PsuedoConstantAnalysis.cpp119
-rw-r--r--lib/Checker/IdempotentOperationChecker.cpp52
4 files changed, 165 insertions, 15 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())
+}
diff --git a/lib/Checker/IdempotentOperationChecker.cpp b/lib/Checker/IdempotentOperationChecker.cpp
index 4f2810ea94..885123ae24 100644
--- a/lib/Checker/IdempotentOperationChecker.cpp
+++ b/lib/Checker/IdempotentOperationChecker.cpp
@@ -44,6 +44,7 @@
#include "GRExprEngineExperimentalChecks.h"
#include "clang/Analysis/CFGStmtMap.h"
+#include "clang/Analysis/Analyses/PsuedoConstantAnalysis.h"
#include "clang/Checker/BugReporter/BugType.h"
#include "clang/Checker/PathSensitive/CheckerHelpers.h"
#include "clang/Checker/PathSensitive/CheckerVisitor.h"
@@ -72,16 +73,16 @@ class IdempotentOperationChecker
void UpdateAssumption(Assumption &A, const Assumption &New);
- /// contains* - Useful recursive methods to see if a statement contains an
- /// element somewhere. Used in static analysis to reduce false positives.
+ // False positive reduction methods
static bool isParameterSelfAssign(const Expr *LHS, const Expr *RHS);
static bool isTruncationExtensionAssignment(const Expr *LHS,
const Expr *RHS);
static bool PathWasCompletelyAnalyzed(const CFG *C,
const CFGBlock *CB,
const GRCoreEngine &CE);
- static bool CanVary(const Expr *Ex, ASTContext &Ctx);
- static bool isPseudoConstant(const DeclRefExpr *D);
+ static bool CanVary(const Expr *Ex, AnalysisContext *AC);
+ static bool isConstantOrPseudoConstant(const DeclRefExpr *DR,
+ AnalysisContext *AC);
// Hash table
typedef llvm::DenseMap<const BinaryOperator *,
@@ -108,7 +109,8 @@ void IdempotentOperationChecker::PreVisitBinaryOperator(
// 'Possible'.
std::pair<Assumption, AnalysisContext *> &Data = hash[B];
Assumption &A = Data.first;
- Data.second = C.getCurrentAnalysisContext();
+ AnalysisContext *AC = C.getCurrentAnalysisContext();
+ Data.second = AC;
// If we already have visited this node on a path that does not contain an
// idempotent operation, return immediately.
@@ -119,8 +121,14 @@ void IdempotentOperationChecker::PreVisitBinaryOperator(
// may mean this is a false positive.
const Expr *LHS = B->getLHS();
const Expr *RHS = B->getRHS();
- bool LHSCanVary = CanVary(LHS, C.getASTContext());
- bool RHSCanVary = CanVary(RHS, C.getASTContext());
+
+ // Check if either side can vary. We only need to calculate this when we have
+ // no assumption.
+ bool LHSCanVary = true, RHSCanVary = true;
+ if (A == Possible) {
+ LHSCanVary = CanVary(LHS, AC);
+ RHSCanVary = CanVary(RHS, AC);
+ }
const GRState *state = C.getState();
@@ -486,7 +494,8 @@ bool IdempotentOperationChecker::PathWasCompletelyAnalyzed(
// that varies. This could be due to a compile-time constant like sizeof. An
// expression may also involve a variable that behaves like a constant. The
// function returns true if the expression varies, and false otherwise.
-bool IdempotentOperationChecker::CanVary(const Expr *Ex, ASTContext &Ctx) {
+bool IdempotentOperationChecker::CanVary(const Expr *Ex,
+ AnalysisContext *AC) {
// Parentheses and casts are irrelevant here
Ex = Ex->IgnoreParenCasts();
@@ -531,12 +540,13 @@ bool IdempotentOperationChecker::CanVary(const Expr *Ex, ASTContext &Ctx) {
return SE->getTypeOfArgument()->isVariableArrayType();
}
case Stmt::DeclRefExprClass:
- return !isPseudoConstant(cast<DeclRefExpr>(Ex));
+ return !isConstantOrPseudoConstant(cast<DeclRefExpr>(Ex), AC);
// The next cases require recursion for subexpressions
case Stmt::BinaryOperatorClass: {
const BinaryOperator *B = cast<const BinaryOperator>(Ex);
- return CanVary(B->getRHS(), Ctx) || CanVary(B->getLHS(), Ctx);
+ return CanVary(B->getRHS(), AC)
+ || CanVary(B->getLHS(), AC);
}
case Stmt::UnaryOperatorClass: {
const UnaryOperator *U = cast<const UnaryOperator>(Ex);
@@ -545,18 +555,25 @@ bool IdempotentOperationChecker::CanVary(const Expr *Ex, ASTContext &Ctx) {
case UnaryOperator::Extension:
return false;
default:
- return CanVary(U->getSubExpr(), Ctx);
+ return CanVary(U->getSubExpr(), AC);
}
}
case Stmt::ChooseExprClass:
- return CanVary(cast<const ChooseExpr>(Ex)->getChosenSubExpr(Ctx), Ctx);
+ return CanVary(cast<const ChooseExpr>(Ex)->getChosenSubExpr(
+ AC->getASTContext()), AC);
case Stmt::ConditionalOperatorClass:
- return CanVary(cast<const ConditionalOperator>(Ex)->getCond(), Ctx);
+ return CanVary(cast<const ConditionalOperator>(Ex)->getCond(), AC);
}
}
-// Returns true if a DeclRefExpr behaves like a constant.
-bool IdempotentOperationChecker::isPseudoConstant(const DeclRefExpr *DR) {
+// Returns true if a DeclRefExpr is or behaves like a constant.
+bool IdempotentOperationChecker::isConstantOrPseudoConstant(
+ const DeclRefExpr *DR,
+ AnalysisContext *AC) {
+ // Check if the type of the Decl is const-qualified
+ if (DR->getType().isConstQualified())
+ return true;
+
// Check for an enum
if (isa<EnumConstantDecl>(DR->getDecl()))
return true;
@@ -567,5 +584,10 @@ bool IdempotentOperationChecker::isPseudoConstant(const DeclRefExpr *DR) {
if (VD->isStaticLocal())
return true;
+ // Check if the Decl behaves like a constant
+ PsuedoConstantAnalysis *PCA = AC->getPsuedoConstantAnalysis();
+ if (PCA->isPsuedoConstant(DR->getDecl()))
+ return true;
+
return false;
}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-24 22:25:12 +0000