From 245adabd97c8c770c13935a9075f2243cc6f1d57 Mon Sep 17 00:00:00 2001 From: Tom Care Date: Wed, 18 Aug 2010 21:17:24 +0000 Subject: [PATCH] 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 --- .../Analyses/PsuedoConstantAnalysis.h | 44 +++++++ include/clang/Analysis/AnalysisContext.h | 5 +- lib/Analysis/AnalysisContext.cpp | 8 ++ lib/Analysis/CMakeLists.txt | 1 + lib/Analysis/PsuedoConstantAnalysis.cpp | 119 ++++++++++++++++++ lib/Checker/IdempotentOperationChecker.cpp | 52 +++++--- test/Analysis/constant-folding.c | 10 +- test/Analysis/idempotent-operations.c | 30 ++++- test/Analysis/null-deref-ps.c | 2 +- 9 files changed, 247 insertions(+), 24 deletions(-) create mode 100644 include/clang/Analysis/Analyses/PsuedoConstantAnalysis.h create mode 100644 lib/Analysis/PsuedoConstantAnalysis.cpp diff --git a/include/clang/Analysis/Analyses/PsuedoConstantAnalysis.h b/include/clang/Analysis/Analyses/PsuedoConstantAnalysis.h new file mode 100644 index 0000000000..080f6c1587 --- /dev/null +++ b/include/clang/Analysis/Analyses/PsuedoConstantAnalysis.h @@ -0,0 +1,44 @@ +//== PsuedoConstantAnalysis.h - Find Psuedo-constants 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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_PSUEDOCONSTANTANALYSIS +#define LLVM_CLANG_ANALYSIS_PSUEDOCONSTANTANALYSIS + +#include "clang/AST/Stmt.h" + +// The number of ValueDecls we want to keep track of by default (per-function) +#define VALUEDECL_SET_SIZE 256 + +namespace clang { + +class PsuedoConstantAnalysis { +public: + PsuedoConstantAnalysis(const Stmt *DeclBody) : + DeclBody(DeclBody), Analyzed(false) {} + bool isPsuedoConstant(const ValueDecl *VD); + +private: + void RunAnalysis(); + + // for storing the result of analyzed ValueDecls + llvm::SmallPtrSet NonConstants; + + const Stmt *DeclBody; + bool Analyzed; +}; + +} + +#endif diff --git a/include/clang/Analysis/AnalysisContext.h b/include/clang/Analysis/AnalysisContext.h index 2b595b99cb..124a08e073 100644 --- a/include/clang/Analysis/AnalysisContext.h +++ b/include/clang/Analysis/AnalysisContext.h @@ -30,6 +30,7 @@ class CFG; class CFGBlock; class LiveVariables; class ParentMap; +class PsuedoConstantAnalysis; class ImplicitParamDecl; class LocationContextManager; class StackFrameContext; @@ -49,6 +50,7 @@ class AnalysisContext { bool builtCFG, builtCompleteCFG; LiveVariables *liveness; ParentMap *PM; + PsuedoConstantAnalysis *PCA; llvm::DenseMap *ReferencedBlockVars; llvm::BumpPtrAllocator A; bool UseUnoptimizedCFG; @@ -59,7 +61,7 @@ public: bool addehedges = false) : D(d), TU(tu), cfg(0), completeCFG(0), builtCFG(false), builtCompleteCFG(false), - liveness(0), PM(0), + liveness(0), PM(0), PCA(0), ReferencedBlockVars(0), UseUnoptimizedCFG(useUnoptimizedCFG), AddEHEdges(addehedges) {} @@ -85,6 +87,7 @@ public: CFG *getUnoptimizedCFG(); ParentMap &getParentMap(); + PsuedoConstantAnalysis *getPsuedoConstantAnalysis(); LiveVariables *getLiveVariables(); typedef const VarDecl * const * referenced_decls_iterator; 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 + +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 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(Head); + const Expr *LHS = BO->getLHS()->IgnoreParenImpCasts(); + const DeclRefExpr *DR = dyn_cast(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(Head); + const Expr *SubExpr = UO->getSubExpr()->IgnoreParenImpCasts(); + const DeclRefExpr *DR = dyn_cast(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 &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(Ex)); + return !isConstantOrPseudoConstant(cast(Ex), AC); // The next cases require recursion for subexpressions case Stmt::BinaryOperatorClass: { const BinaryOperator *B = cast(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(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(Ex)->getChosenSubExpr(Ctx), Ctx); + return CanVary(cast(Ex)->getChosenSubExpr( + AC->getASTContext()), AC); case Stmt::ConditionalOperatorClass: - return CanVary(cast(Ex)->getCond(), Ctx); + return CanVary(cast(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(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; } diff --git a/test/Analysis/constant-folding.c b/test/Analysis/constant-folding.c index 85e47c8dea..9191a9e057 100644 --- a/test/Analysis/constant-folding.c +++ b/test/Analysis/constant-folding.c @@ -18,10 +18,10 @@ void testComparisons (int a) { } void testSelfOperations (int a) { - if ((a|a) != a) WARN; // expected-warning{{Both operands to '|' always have the same value}} expected-warning{{never executed}} - if ((a&a) != a) WARN; // expected-warning{{Both operands to '&' always have the same value}} expected-warning{{never executed}} - if ((a^a) != 0) WARN; // expected-warning{{Both operands to '^' always have the same value}} expected-warning{{never executed}} - if ((a-a) != 0) WARN; // expected-warning{{Both operands to '-' always have the same value}} expected-warning{{never executed}} + if ((a|a) != a) WARN; // expected-warning{{never executed}} + if ((a&a) != a) WARN; // expected-warning{{never executed}} + if ((a^a) != 0) WARN; // expected-warning{{never executed}} + if ((a-a) != 0) WARN; // expected-warning{{never executed}} } void testIdempotent (int a) { @@ -68,5 +68,5 @@ void testLocations (char *a) { if (b!=a) WARN; // expected-warning{{never executed}} if (b>a) WARN; // expected-warning{{never executed}} if (b> x); // expected-warning {{The left operand to '>>' is always 0}} + + // Overwrite the values so these aren't marked as psuedoconstants + x = 1; + zero = 2; + one = 3; + + return x + zero + one; } void floats(float x) { @@ -84,4 +91,23 @@ unsigned false2() { return enum1 + a; // no-warning } -extern unsigned foo(); +// Self assignments of parameters are common false positives +unsigned false3(int param) { + param = param; // no-warning + + unsigned nonparam = 5; + + nonparam = nonparam; // expected-warning{{Assigned value is always the same as the existing value}} + + return nonparam; +} + +// Psuedo-constants (vars only read) and constants should not be reported +unsigned false4() { + // Trivial constant + const int height = 1; // no-warning + // Psuedo-constant (never changes after decl) + int width = height; // no-warning + + return width * 10; // no-warning +} diff --git a/test/Analysis/null-deref-ps.c b/test/Analysis/null-deref-ps.c index 1ae94c709b..356e2b4d0f 100644 --- a/test/Analysis/null-deref-ps.c +++ b/test/Analysis/null-deref-ps.c @@ -260,7 +260,7 @@ void f12(HF12ITEM i, char *q) { // Test handling of translating between integer "pointers" and back. void f13() { int *x = 0; - if (((((int) x) << 2) + 1) >> 1) *x = 1; // expected-warning{{The left operand to '<<' is always 0}} expected-warning{{The left operand to '+' is always 0}} + if (((((int) x) << 2) + 1) >> 1) *x = 1; } // PR 4759 - Attribute non-null checking by the analyzer was not correctly -- 2.40.0