summaryrefslogtreecommitdiffstats
path: root/lib/Checker/IdempotentOperationChecker.cpp
diff options
context:
space:
mode:
authorrdivacky <rdivacky@FreeBSD.org>2010-07-13 17:21:42 +0000
committerrdivacky <rdivacky@FreeBSD.org>2010-07-13 17:21:42 +0000
commit1928da94b55683957759d5c5ff4593a118773394 (patch)
tree48b44512b5db8ced345df4a1a56b5065cf2a14d9 /lib/Checker/IdempotentOperationChecker.cpp
parent53992adde3eda3ccf9da63bc7e45673f043de18f (diff)
downloadFreeBSD-src-1928da94b55683957759d5c5ff4593a118773394.zip
FreeBSD-src-1928da94b55683957759d5c5ff4593a118773394.tar.gz
Update clang to r108243.
Diffstat (limited to 'lib/Checker/IdempotentOperationChecker.cpp')
-rw-r--r--lib/Checker/IdempotentOperationChecker.cpp454
1 files changed, 454 insertions, 0 deletions
diff --git a/lib/Checker/IdempotentOperationChecker.cpp b/lib/Checker/IdempotentOperationChecker.cpp
new file mode 100644
index 0000000..6ed1841
--- /dev/null
+++ b/lib/Checker/IdempotentOperationChecker.cpp
@@ -0,0 +1,454 @@
+//==- IdempotentOperationChecker.cpp - Idempotent Operations ----*- C++ -*-==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a set of path-sensitive checks for idempotent and/or
+// tautological operations. Each potential operation is checked along all paths
+// to see if every path results in a pointless operation.
+// +-------------------------------------------+
+// |Table of idempotent/tautological operations|
+// +-------------------------------------------+
+//+--------------------------------------------------------------------------+
+//|Operator | x op x | x op 1 | 1 op x | x op 0 | 0 op x | x op ~0 | ~0 op x |
+//+--------------------------------------------------------------------------+
+// +, += | | | | x | x | |
+// -, -= | | | | x | -x | |
+// *, *= | | x | x | 0 | 0 | |
+// /, /= | 1 | x | | N/A | 0 | |
+// &, &= | x | | | 0 | 0 | x | x
+// |, |= | x | | | x | x | ~0 | ~0
+// ^, ^= | 0 | | | x | x | |
+// <<, <<= | | | | x | 0 | |
+// >>, >>= | | | | x | 0 | |
+// || | 1 | 1 | 1 | x | x | 1 | 1
+// && | 1 | x | x | 0 | 0 | x | x
+// = | x | | | | | |
+// == | 1 | | | | | |
+// >= | 1 | | | | | |
+// <= | 1 | | | | | |
+// > | 0 | | | | | |
+// < | 0 | | | | | |
+// != | 0 | | | | | |
+//===----------------------------------------------------------------------===//
+//
+// Ways to reduce false positives (that need to be implemented):
+// - Don't flag downsizing casts
+// - Improved handling of static/global variables
+// - Per-block marking of incomplete analysis
+// - Handling ~0 values
+// - False positives involving silencing unused variable warnings
+//
+// Other things TODO:
+// - Improved error messages
+// - Handle mixed assumptions (which assumptions can belong together?)
+// - Finer grained false positive control (levels)
+
+#include "GRExprEngineExperimentalChecks.h"
+#include "clang/Checker/BugReporter/BugType.h"
+#include "clang/Checker/PathSensitive/CheckerVisitor.h"
+#include "clang/Checker/PathSensitive/SVals.h"
+#include "clang/AST/Stmt.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/ErrorHandling.h"
+
+using namespace clang;
+
+namespace {
+class IdempotentOperationChecker
+ : public CheckerVisitor<IdempotentOperationChecker> {
+ public:
+ static void *getTag();
+ void PreVisitBinaryOperator(CheckerContext &C, const BinaryOperator *B);
+ void VisitEndAnalysis(ExplodedGraph &G, BugReporter &B,
+ bool hasWorkRemaining);
+
+ private:
+ // Our assumption about a particular operation.
+ enum Assumption { Possible, Impossible, Equal, LHSis1, RHSis1, LHSis0,
+ RHSis0 };
+
+ 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.
+ static bool containsMacro(const Stmt *S);
+ static bool containsEnum(const Stmt *S);
+ static bool containsBuiltinOffsetOf(const Stmt *S);
+ static bool containsZeroConstant(const Stmt *S);
+ static bool containsOneConstant(const Stmt *S);
+ template <class T> static bool containsStmt(const Stmt *S) {
+ if (isa<T>(S))
+ return true;
+
+ for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
+ ++I)
+ if (const Stmt *child = *I)
+ if (containsStmt<T>(child))
+ return true;
+
+ return false;
+ }
+
+ // Hash table
+ typedef llvm::DenseMap<const BinaryOperator *, Assumption> AssumptionMap;
+ AssumptionMap hash;
+};
+}
+
+void *IdempotentOperationChecker::getTag() {
+ static int x = 0;
+ return &x;
+}
+
+void clang::RegisterIdempotentOperationChecker(GRExprEngine &Eng) {
+ Eng.registerCheck(new IdempotentOperationChecker());
+}
+
+void IdempotentOperationChecker::PreVisitBinaryOperator(
+ CheckerContext &C,
+ const BinaryOperator *B) {
+ // Find or create an entry in the hash for this BinaryOperator instance
+ AssumptionMap::iterator i = hash.find(B);
+ Assumption &A = i == hash.end() ? hash[B] : i->second;
+
+ // If we had to create an entry, initialise the value to Possible
+ if (i == hash.end())
+ A = Possible;
+
+ // If we already have visited this node on a path that does not contain an
+ // idempotent operation, return immediately.
+ if (A == Impossible)
+ return;
+
+ // Skip binary operators containing common false positives
+ if (containsMacro(B) || containsEnum(B) || containsStmt<SizeOfAlignOfExpr>(B)
+ || containsZeroConstant(B) || containsOneConstant(B)
+ || containsBuiltinOffsetOf(B)) {
+ A = Impossible;
+ return;
+ }
+
+ const Expr *LHS = B->getLHS();
+ const Expr *RHS = B->getRHS();
+
+ const GRState *state = C.getState();
+
+ SVal LHSVal = state->getSVal(LHS);
+ SVal RHSVal = state->getSVal(RHS);
+
+ // If either value is unknown, we can't be 100% sure of all paths.
+ if (LHSVal.isUnknownOrUndef() || RHSVal.isUnknownOrUndef()) {
+ A = Impossible;
+ return;
+ }
+ BinaryOperator::Opcode Op = B->getOpcode();
+
+ // Dereference the LHS SVal if this is an assign operation
+ switch (Op) {
+ default:
+ break;
+
+ // Fall through intentional
+ 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:
+ case BinaryOperator::Assign:
+ // Assign statements have one extra level of indirection
+ if (!isa<Loc>(LHSVal)) {
+ A = Impossible;
+ return;
+ }
+ LHSVal = state->getSVal(cast<Loc>(LHSVal));
+ }
+
+
+ // We now check for various cases which result in an idempotent operation.
+
+ // x op x
+ switch (Op) {
+ default:
+ break; // We don't care about any other operators.
+
+ // Fall through intentional
+ case BinaryOperator::SubAssign:
+ case BinaryOperator::DivAssign:
+ case BinaryOperator::AndAssign:
+ case BinaryOperator::OrAssign:
+ case BinaryOperator::XorAssign:
+ case BinaryOperator::Assign:
+ case BinaryOperator::Sub:
+ case BinaryOperator::Div:
+ case BinaryOperator::And:
+ case BinaryOperator::Or:
+ case BinaryOperator::Xor:
+ case BinaryOperator::LOr:
+ case BinaryOperator::LAnd:
+ if (LHSVal != RHSVal)
+ break;
+ UpdateAssumption(A, Equal);
+ return;
+ }
+
+ // x op 1
+ switch (Op) {
+ default:
+ break; // We don't care about any other operators.
+
+ // Fall through intentional
+ case BinaryOperator::MulAssign:
+ case BinaryOperator::DivAssign:
+ case BinaryOperator::Mul:
+ case BinaryOperator::Div:
+ case BinaryOperator::LOr:
+ case BinaryOperator::LAnd:
+ if (!RHSVal.isConstant(1))
+ break;
+ UpdateAssumption(A, RHSis1);
+ return;
+ }
+
+ // 1 op x
+ switch (Op) {
+ default:
+ break; // We don't care about any other operators.
+
+ // Fall through intentional
+ case BinaryOperator::MulAssign:
+ case BinaryOperator::Mul:
+ case BinaryOperator::LOr:
+ case BinaryOperator::LAnd:
+ if (!LHSVal.isConstant(1))
+ break;
+ UpdateAssumption(A, LHSis1);
+ return;
+ }
+
+ // x op 0
+ switch (Op) {
+ default:
+ break; // We don't care about any other operators.
+
+ // Fall through intentional
+ case BinaryOperator::AddAssign:
+ case BinaryOperator::SubAssign:
+ case BinaryOperator::MulAssign:
+ case BinaryOperator::AndAssign:
+ case BinaryOperator::OrAssign:
+ case BinaryOperator::XorAssign:
+ case BinaryOperator::Add:
+ case BinaryOperator::Sub:
+ case BinaryOperator::Mul:
+ case BinaryOperator::And:
+ case BinaryOperator::Or:
+ case BinaryOperator::Xor:
+ case BinaryOperator::Shl:
+ case BinaryOperator::Shr:
+ case BinaryOperator::LOr:
+ case BinaryOperator::LAnd:
+ if (!RHSVal.isConstant(0))
+ break;
+ UpdateAssumption(A, RHSis0);
+ return;
+ }
+
+ // 0 op x
+ switch (Op) {
+ default:
+ break; // We don't care about any other operators.
+
+ // Fall through intentional
+ //case BinaryOperator::AddAssign: // Common false positive
+ case BinaryOperator::SubAssign: // Check only if unsigned
+ case BinaryOperator::MulAssign:
+ case BinaryOperator::DivAssign:
+ case BinaryOperator::AndAssign:
+ //case BinaryOperator::OrAssign: // Common false positive
+ //case BinaryOperator::XorAssign: // Common false positive
+ case BinaryOperator::ShlAssign:
+ case BinaryOperator::ShrAssign:
+ case BinaryOperator::Add:
+ case BinaryOperator::Sub:
+ case BinaryOperator::Mul:
+ case BinaryOperator::Div:
+ case BinaryOperator::And:
+ case BinaryOperator::Or:
+ case BinaryOperator::Xor:
+ case BinaryOperator::Shl:
+ case BinaryOperator::Shr:
+ case BinaryOperator::LOr:
+ case BinaryOperator::LAnd:
+ if (!LHSVal.isConstant(0))
+ break;
+ UpdateAssumption(A, LHSis0);
+ return;
+ }
+
+ // If we get to this point, there has been a valid use of this operation.
+ A = Impossible;
+}
+
+void IdempotentOperationChecker::VisitEndAnalysis(ExplodedGraph &G,
+ BugReporter &B,
+ bool hasWorkRemaining) {
+ // If there is any work remaining we cannot be 100% sure about our warnings
+ if (hasWorkRemaining)
+ return;
+
+ // Iterate over the hash to see if we have any paths with definite
+ // idempotent operations.
+ for (AssumptionMap::const_iterator i =
+ hash.begin(); i != hash.end(); ++i) {
+ if (i->second != Impossible) {
+ // Select the error message.
+ const char *msg = 0;
+ switch (i->second) {
+ case Equal:
+ msg = "idempotent operation; both operands are always equal in value";
+ break;
+ case LHSis1:
+ msg = "idempotent operation; the left operand is always 1";
+ break;
+ case RHSis1:
+ msg = "idempotent operation; the right operand is always 1";
+ break;
+ case LHSis0:
+ msg = "idempotent operation; the left operand is always 0";
+ break;
+ case RHSis0:
+ msg = "idempotent operation; the right operand is always 0";
+ break;
+ case Possible:
+ llvm_unreachable("Operation was never marked with an assumption");
+ case Impossible:
+ llvm_unreachable(0);
+ }
+
+ // Create the SourceRange Arrays
+ SourceRange S[2] = { i->first->getLHS()->getSourceRange(),
+ i->first->getRHS()->getSourceRange() };
+ B.EmitBasicReport("Idempotent operation", msg, i->first->getOperatorLoc(),
+ S, 2);
+ }
+ }
+}
+
+// Updates the current assumption given the new assumption
+inline void IdempotentOperationChecker::UpdateAssumption(Assumption &A,
+ const Assumption &New) {
+ switch (A) {
+ // If we don't currently have an assumption, set it
+ case Possible:
+ A = New;
+ return;
+
+ // If we have determined that a valid state happened, ignore the new
+ // assumption.
+ case Impossible:
+ return;
+
+ // Any other case means that we had a different assumption last time. We don't
+ // currently support mixing assumptions for diagnostic reasons, so we set
+ // our assumption to be impossible.
+ default:
+ A = Impossible;
+ return;
+ }
+}
+
+// Recursively find any substatements containing macros
+bool IdempotentOperationChecker::containsMacro(const Stmt *S) {
+ if (S->getLocStart().isMacroID())
+ return true;
+
+ if (S->getLocEnd().isMacroID())
+ return true;
+
+ for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
+ ++I)
+ if (const Stmt *child = *I)
+ if (containsMacro(child))
+ return true;
+
+ return false;
+}
+
+// Recursively find any substatements containing enum constants
+bool IdempotentOperationChecker::containsEnum(const Stmt *S) {
+ const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S);
+
+ if (DR && isa<EnumConstantDecl>(DR->getDecl()))
+ return true;
+
+ for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
+ ++I)
+ if (const Stmt *child = *I)
+ if (containsEnum(child))
+ return true;
+
+ return false;
+}
+
+// Recursively find any substatements containing __builtin_offset_of
+bool IdempotentOperationChecker::containsBuiltinOffsetOf(const Stmt *S) {
+ const UnaryOperator *UO = dyn_cast<UnaryOperator>(S);
+
+ if (UO && UO->getOpcode() == UnaryOperator::OffsetOf)
+ return true;
+
+ for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
+ ++I)
+ if (const Stmt *child = *I)
+ if (containsBuiltinOffsetOf(child))
+ return true;
+
+ return false;
+}
+
+bool IdempotentOperationChecker::containsZeroConstant(const Stmt *S) {
+ const IntegerLiteral *IL = dyn_cast<IntegerLiteral>(S);
+ if (IL && IL->getValue() == 0)
+ return true;
+
+ const FloatingLiteral *FL = dyn_cast<FloatingLiteral>(S);
+ if (FL && FL->getValue().isZero())
+ return true;
+
+ for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
+ ++I)
+ if (const Stmt *child = *I)
+ if (containsZeroConstant(child))
+ return true;
+
+ return false;
+}
+
+bool IdempotentOperationChecker::containsOneConstant(const Stmt *S) {
+ const IntegerLiteral *IL = dyn_cast<IntegerLiteral>(S);
+ if (IL && IL->getValue() == 1)
+ return true;
+
+ const FloatingLiteral *FL = dyn_cast<FloatingLiteral>(S);
+ const llvm::APFloat one(1.0);
+ if (FL && FL->getValue().compare(one) == llvm::APFloat::cmpEqual)
+ return true;
+
+ for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
+ ++I)
+ if (const Stmt *child = *I)
+ if (containsOneConstant(child))
+ return true;
+
+ return false;
+}
+
OpenPOWER on IntegriCloud