From a7a8a450d908b34fa5f569f2e694ebd4b61aae2f Mon Sep 17 00:00:00 2001 From: Tom Care Date: Thu, 12 Aug 2010 22:45:47 +0000 Subject: [PATCH] Improved IdempotentOperationChecker false positives and false negatives. - Unfinished analysis may still report valid warnings if the path was completely analyzed - New 'CanVary' heuristic to recursively determine if a subexpression has a varying element - Updated test cases, including one known bug - Exposed GRCoreEngine through GRExprEngine git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@110970 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Checker/PathSensitive/Checker.h | 4 + .../Checker/PathSensitive/GRCoreEngine.h | 9 +- .../Checker/PathSensitive/GRExprEngine.h | 4 +- lib/Checker/IdempotentOperationChecker.cpp | 301 ++++++++++++------ test/Analysis/dead-stores.c | 2 +- test/Analysis/idempotent-operations.c | 27 +- test/Analysis/null-deref-ps-temp.c | 31 ++ test/Analysis/null-deref-ps.c | 24 +- 8 files changed, 268 insertions(+), 134 deletions(-) create mode 100644 test/Analysis/null-deref-ps-temp.c diff --git a/include/clang/Checker/PathSensitive/Checker.h b/include/clang/Checker/PathSensitive/Checker.h index 1c9f85b937..d34550aa27 100644 --- a/include/clang/Checker/PathSensitive/Checker.h +++ b/include/clang/Checker/PathSensitive/Checker.h @@ -165,6 +165,10 @@ public: Eng.getBugReporter().EmitReport(R); } + AnalysisContext *getCurrentAnalysisContext() const { + return Pred->getLocationContext()->getAnalysisContext(); + } + private: ExplodedNode *GenerateNodeImpl(const Stmt* stmt, const GRState *state, bool markAsSink) { diff --git a/include/clang/Checker/PathSensitive/GRCoreEngine.h b/include/clang/Checker/PathSensitive/GRCoreEngine.h index 0426194c5e..4f9f2d811c 100644 --- a/include/clang/Checker/PathSensitive/GRCoreEngine.h +++ b/include/clang/Checker/PathSensitive/GRCoreEngine.h @@ -43,6 +43,11 @@ class GRCoreEngine { friend class GRCallEnterNodeBuilder; friend class GRCallExitNodeBuilder; +public: + typedef std::vector > + BlocksAborted; +private: + GRSubEngine& SubEngine; /// G - The simulation graph. Each node is a (location,state) pair. @@ -57,10 +62,6 @@ class GRCoreEngine { /// These are used to record for key nodes in the ExplodedGraph the /// number of times different CFGBlocks have been visited along a path. GRBlockCounter::Factory BCounterFactory; - - - typedef std::vector > - BlocksAborted; /// The locations where we stopped doing work because we visited a location /// too many times. diff --git a/include/clang/Checker/PathSensitive/GRExprEngine.h b/include/clang/Checker/PathSensitive/GRExprEngine.h index f7b7d7012a..691e7f3605 100644 --- a/include/clang/Checker/PathSensitive/GRExprEngine.h +++ b/include/clang/Checker/PathSensitive/GRExprEngine.h @@ -254,10 +254,10 @@ public: // Functions for external checking of whether we have unfinished work bool wasBlockAborted() const { return CoreEngine.wasBlockAborted(); } bool hasWorkRemaining() const { - return wasBlockAborted() || getWorkList()->hasWork(); + return wasBlockAborted() || CoreEngine.getWorkList()->hasWork(); } - GRWorkList *getWorkList() const { return CoreEngine.getWorkList(); } + const GRCoreEngine &getCoreEngine() const { return CoreEngine; } protected: const GRState* GetState(ExplodedNode* N) { diff --git a/lib/Checker/IdempotentOperationChecker.cpp b/lib/Checker/IdempotentOperationChecker.cpp index 76f493e6b3..9866c6096e 100644 --- a/lib/Checker/IdempotentOperationChecker.cpp +++ b/lib/Checker/IdempotentOperationChecker.cpp @@ -36,26 +36,24 @@ // != | 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: +// Things TODO: // - Improved error messages // - Handle mixed assumptions (which assumptions can belong together?) // - Finer grained false positive control (levels) +// - Handling ~0 values #include "GRExprEngineExperimentalChecks.h" +#include "clang/Analysis/CFGStmtMap.h" #include "clang/Checker/BugReporter/BugType.h" #include "clang/Checker/PathSensitive/CheckerHelpers.h" #include "clang/Checker/PathSensitive/CheckerVisitor.h" +#include "clang/Checker/PathSensitive/GRCoreEngine.h" #include "clang/Checker/PathSensitive/SVals.h" #include "clang/AST/Stmt.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/Support/ErrorHandling.h" +#include using namespace clang; @@ -79,11 +77,15 @@ class IdempotentOperationChecker static bool isParameterSelfAssign(const Expr *LHS, const Expr *RHS); static bool isTruncationExtensionAssignment(const Expr *LHS, const Expr *RHS); - static bool containsZeroConstant(const Stmt *S); - static bool containsOneConstant(const Stmt *S); + static bool PathWasCompletelyAnalyzed(const CFG *C, + const CFGBlock *CB, + const GRCoreEngine &CE); + static bool CanVary(const Expr *Ex, ASTContext &Ctx); // Hash table - typedef llvm::DenseMap AssumptionMap; + typedef llvm::DenseMap > + AssumptionMap; AssumptionMap hash; }; } @@ -103,23 +105,21 @@ void IdempotentOperationChecker::PreVisitBinaryOperator( // Find or create an entry in the hash for this BinaryOperator instance. // If we haven't done a lookup before, it will get default initialized to // 'Possible'. - Assumption &A = hash[B]; + std::pair &Data = hash[B]; + Assumption &A = Data.first; + Data.second = C.getCurrentAnalysisContext(); // 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(B) - || containsZeroConstant(B) || containsOneConstant(B) - || containsBuiltinOffsetOf(B) || containsStaticLocal(B)) { - A = Impossible; - return; - } - + // Retrieve both sides of the operator and determine if they can vary (which + // 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()); const GRState *state = C.getState(); @@ -186,7 +186,7 @@ void IdempotentOperationChecker::PreVisitBinaryOperator( case BinaryOperator::Xor: case BinaryOperator::LOr: case BinaryOperator::LAnd: - if (LHSVal != RHSVal) + if (LHSVal != RHSVal || !LHSCanVary || !RHSCanVary) break; UpdateAssumption(A, Equal); return; @@ -204,7 +204,7 @@ void IdempotentOperationChecker::PreVisitBinaryOperator( case BinaryOperator::Div: case BinaryOperator::LOr: case BinaryOperator::LAnd: - if (!RHSVal.isConstant(1)) + if (!RHSVal.isConstant(1) || !RHSCanVary) break; UpdateAssumption(A, RHSis1); return; @@ -220,7 +220,7 @@ void IdempotentOperationChecker::PreVisitBinaryOperator( case BinaryOperator::Mul: case BinaryOperator::LOr: case BinaryOperator::LAnd: - if (!LHSVal.isConstant(1)) + if (!LHSVal.isConstant(1) || !LHSCanVary) break; UpdateAssumption(A, LHSis1); return; @@ -248,7 +248,7 @@ void IdempotentOperationChecker::PreVisitBinaryOperator( case BinaryOperator::Shr: case BinaryOperator::LOr: case BinaryOperator::LAnd: - if (!RHSVal.isConstant(0)) + if (!RHSVal.isConstant(0) || !RHSCanVary) break; UpdateAssumption(A, RHSis0); return; @@ -280,7 +280,7 @@ void IdempotentOperationChecker::PreVisitBinaryOperator( case BinaryOperator::Shr: case BinaryOperator::LOr: case BinaryOperator::LAnd: - if (!LHSVal.isConstant(0)) + if (!LHSVal.isConstant(0) || !LHSCanVary) break; UpdateAssumption(A, LHSis0); return; @@ -293,52 +293,68 @@ void IdempotentOperationChecker::PreVisitBinaryOperator( void IdempotentOperationChecker::VisitEndAnalysis(ExplodedGraph &G, BugReporter &BR, GRExprEngine &Eng) { - // If there is any work remaining we cannot be 100% sure about our warnings - if (Eng.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 BinaryOperator *B = i->first; - llvm::SmallString<128> buf; - llvm::raw_svector_ostream os(buf); - - switch (i->second) { - case Equal: - if (B->getOpcode() == BinaryOperator::Assign) - os << "Assigned value is always the same as the existing value"; - else - os << "Both operands to '" << B->getOpcodeStr() - << "' always have the same value"; - break; - case LHSis1: - os << "The left operand to '" << B->getOpcodeStr() << "' is always 1"; - break; - case RHSis1: - os << "The right operand to '" << B->getOpcodeStr() << "' is always 1"; - break; - case LHSis0: - os << "The left operand to '" << B->getOpcodeStr() << "' is always 0"; - break; - case RHSis0: - os << "The right operand to '" << B->getOpcodeStr() << "' 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() }; - BR.EmitBasicReport("Idempotent operation", "Dead code", - os.str(), i->first->getOperatorLoc(), S, 2); + for (AssumptionMap::const_iterator i = hash.begin(); i != hash.end(); ++i) { + // Unpack the hash contents + const std::pair &Data = i->second; + const Assumption &A = Data.first; + AnalysisContext *AC = Data.second; + + const BinaryOperator *B = i->first; + + if (A == Impossible) + continue; + + // If the analyzer did not finish, check to see if we can still emit this + // warning + if (Eng.hasWorkRemaining()) { + const CFGStmtMap *CBM = CFGStmtMap::Build(AC->getCFG(), + &AC->getParentMap()); + + // If we can trace back + if (!PathWasCompletelyAnalyzed(AC->getCFG(), + CBM->getBlock(B), + Eng.getCoreEngine())) + continue; + + delete CBM; + } + + // Select the error message. + llvm::SmallString<128> buf; + llvm::raw_svector_ostream os(buf); + switch (A) { + case Equal: + if (B->getOpcode() == BinaryOperator::Assign) + os << "Assigned value is always the same as the existing value"; + else + os << "Both operands to '" << B->getOpcodeStr() + << "' always have the same value"; + break; + case LHSis1: + os << "The left operand to '" << B->getOpcodeStr() << "' is always 1"; + break; + case RHSis1: + os << "The right operand to '" << B->getOpcodeStr() << "' is always 1"; + break; + case LHSis0: + os << "The left operand to '" << B->getOpcodeStr() << "' is always 0"; + break; + case RHSis0: + os << "The right operand to '" << B->getOpcodeStr() << "' 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() }; + BR.EmitBasicReport("Idempotent operation", "Dead code", + os.str(), i->first->getOperatorLoc(), S, 2); } } @@ -410,44 +426,133 @@ bool IdempotentOperationChecker::isTruncationExtensionAssignment( return dyn_cast(RHS->IgnoreParens()) == NULL; } -// Check for a integer or float constant of 0 -bool IdempotentOperationChecker::containsZeroConstant(const Stmt *S) { - const IntegerLiteral *IL = dyn_cast(S); - if (IL && IL->getValue() == 0) - return true; +// Returns false if a path to this block was not completely analyzed, or true +// otherwise. +bool IdempotentOperationChecker::PathWasCompletelyAnalyzed( + const CFG *C, + const CFGBlock *CB, + const GRCoreEngine &CE) { + std::deque WorkList; + llvm::SmallSet Aborted; + llvm::SmallSet Visited; + + // Create a set of all aborted blocks + typedef GRCoreEngine::BlocksAborted::const_iterator AbortedIterator; + for (AbortedIterator I = CE.blocks_aborted_begin(), + E = CE.blocks_aborted_end(); I != E; ++I) { + const BlockEdge &BE = I->first; + + // The destination block on the BlockEdge is the first block that was not + // analyzed. + Aborted.insert(BE.getDst()->getBlockID()); + } - const FloatingLiteral *FL = dyn_cast(S); - if (FL && FL->getValue().isZero()) - return true; + // Save the entry block ID for early exiting + unsigned EntryBlockID = C->getEntry().getBlockID(); - for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); - ++I) - if (const Stmt *child = *I) - if (containsZeroConstant(child)) - return true; + // Create initial node + WorkList.push_back(CB); - return false; + while (!WorkList.empty()) { + const CFGBlock *Head = WorkList.front(); + WorkList.pop_front(); + Visited.insert(Head->getBlockID()); + + // If we found the entry block, then there exists a path from the target + // node to the entry point of this function -> the path was completely + // analyzed. + if (Head->getBlockID() == EntryBlockID) + return true; + + // If any of the aborted blocks are on the path to the beginning, then all + // paths to this block were not analyzed. + if (Aborted.count(Head->getBlockID())) + return false; + + // Add the predecessors to the worklist unless we have already visited them + for (CFGBlock::const_pred_iterator I = Head->pred_begin(); + I != Head->pred_end(); ++I) + if (!Visited.count((*I)->getBlockID())) + WorkList.push_back(*I); + } + + // If we get to this point, there is no connection to the entry block or an + // aborted block. This path is unreachable and we can report the error. + return true; } -// Check for an integer or float constant of 1 -bool IdempotentOperationChecker::containsOneConstant(const Stmt *S) { - const IntegerLiteral *IL = dyn_cast(S); - if (IL && IL->getValue() == 1) +// Recursive function that determines whether an expression contains any element +// 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) { + // Parentheses and casts are irrelevant here + Ex = Ex->IgnoreParenCasts(); + + if (Ex->getLocStart().isMacroID()) + return false; + + switch (Ex->getStmtClass()) { + // Trivially true cases + case Stmt::ArraySubscriptExprClass: + case Stmt::MemberExprClass: + case Stmt::StmtExprClass: + case Stmt::CallExprClass: + case Stmt::VAArgExprClass: + case Stmt::ShuffleVectorExprClass: + return true; + default: return true; - if (const FloatingLiteral *FL = dyn_cast(S)) { - const llvm::APFloat &val = FL->getValue(); - const llvm::APFloat one(val.getSemantics(), 1); - if (val.compare(one) == llvm::APFloat::cmpEqual) - return true; - } + // Trivially false cases + case Stmt::IntegerLiteralClass: + case Stmt::CharacterLiteralClass: + case Stmt::FloatingLiteralClass: + case Stmt::PredefinedExprClass: + case Stmt::ImaginaryLiteralClass: + case Stmt::StringLiteralClass: + case Stmt::OffsetOfExprClass: + case Stmt::CompoundLiteralExprClass: + case Stmt::AddrLabelExprClass: + case Stmt::TypesCompatibleExprClass: + case Stmt::GNUNullExprClass: + case Stmt::InitListExprClass: + case Stmt::DesignatedInitExprClass: + case Stmt::BlockExprClass: + case Stmt::BlockDeclRefExprClass: + return false; - for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); - ++I) - if (const Stmt *child = *I) - if (containsOneConstant(child)) - return true; + // Cases requiring custom logic + case Stmt::SizeOfAlignOfExprClass: { + const SizeOfAlignOfExpr *SE = cast(Ex); + if (!SE->isSizeOf()) + return false; + return SE->getTypeOfArgument()->isVariableArrayType(); + } + case Stmt::DeclRefExprClass: + // return !IsPseudoConstant(cast(Ex)); + return true; - return false; + // The next cases require recursion for subexpressions + case Stmt::BinaryOperatorClass: { + const BinaryOperator *B = cast(Ex); + return CanVary(B->getRHS(), Ctx) || CanVary(B->getLHS(), Ctx); + } + case Stmt::UnaryOperatorClass: { + const UnaryOperator *U = cast(Ex); + // Handle two trivial cases first + switch (U->getOpcode()) { + case UnaryOperator::Extension: + case UnaryOperator::OffsetOf: + return false; + default: + return CanVary(U->getSubExpr(), Ctx); + } + } + case Stmt::ChooseExprClass: + return CanVary(cast(Ex)->getChosenSubExpr(Ctx), Ctx); + case Stmt::ConditionalOperatorClass: + return CanVary(cast(Ex)->getCond(), Ctx); + } } diff --git a/test/Analysis/dead-stores.c b/test/Analysis/dead-stores.c index cc8a3f5593..3cd061271f 100644 --- a/test/Analysis/dead-stores.c +++ b/test/Analysis/dead-stores.c @@ -150,7 +150,7 @@ void f15(unsigned x, unsigned y) { int f16(int x) { x = x * 2; - x = sizeof(int [x = (x || x + 1) * 2]) // expected-warning{{Although the value stored to 'x' is used}} + x = sizeof(int [x = (x || x + 1) * 2]) // expected-warning{{Although the value stored to 'x' is used}} expected-warning{{The left operand to '*' is always 1}} ? 5 : 8; return x; } diff --git a/test/Analysis/idempotent-operations.c b/test/Analysis/idempotent-operations.c index 2543b1a006..23401e8cdb 100644 --- a/test/Analysis/idempotent-operations.c +++ b/test/Analysis/idempotent-operations.c @@ -53,20 +53,33 @@ void basic() { } void floats(float x) { - test_f(x * 1.0); // no-warning + test_f(x * 1.0); // no-warning test_f(x * 1.0F); // no-warning } -// Ensure that we don't report false poitives on complex loops +// Ensure that we don't report false poitives in complex loops void bailout() { - int unused, result = 4; - int numbers[5] = { 0, 32, 'x', 128, 255 }; + int unused = 0, result = 4; + result = result; // expected-warning {{Assigned value is always the same as the existing value}} - for (int bg = 0; bg < 5; bg ++) { - result += numbers[bg]; // no-warning + for (unsigned bg = 0; bg < 1024; bg ++) { + result = bg * result; // no-warning for (int i = 0; i < 256; i++) { - unused = i; + unused *= i; // no-warning } } } + +// False positive tests + +unsigned false1() { + return (5 - 2 - 3); // no-warning +} + +enum testenum { enum1 = 0, enum2 }; +unsigned false2() { + return enum1; // no-warning +} + +extern unsigned foo(); diff --git a/test/Analysis/null-deref-ps-temp.c b/test/Analysis/null-deref-ps-temp.c new file mode 100644 index 0000000000..90b6ed3398 --- /dev/null +++ b/test/Analysis/null-deref-ps-temp.c @@ -0,0 +1,31 @@ +// RUN: %clang_cc1 -triple i386-apple-darwin10 -analyze -analyzer-experimental-internal-checks -std=gnu99 -analyzer-check-objc-mem -analyzer-store=region -analyzer-constraints=range -analyzer-no-purge-dead -verify %s -Wreturn-type + +// This is a temporary file to isolate a test case that would cause a failure +// only some of the time in null-deref-ps.c. The idempotent operations checker +// has revealed a bug on line 18 ('=' instead of '==') when the +// -analyzer-no-purge-dead flag is passed to cc1. Some fundamental design +// changes are needed to make this work without the -analyzer-no-purge-dead flag +// and this test will be integrated back into the main file when this happens. + +typedef unsigned uintptr_t; + +int f4_b() { + short array[2]; + uintptr_t x = array; // expected-warning{{incompatible pointer to integer conversion}} + short *p = x; // expected-warning{{incompatible integer to pointer conversion}} + + // The following branch should be infeasible. + if (!(p = &array[0])) { // expected-warning{{Assigned value is always the same as the existing value}} + p = 0; + *p = 1; // no-warning + } + + if (p) { + *p = 5; // no-warning + p = 0; + } + else return; // expected-warning {{non-void function 'f4_b' should return a value}} + + *p += 10; // expected-warning{{Dereference of null pointer}} + return 0; +} diff --git a/test/Analysis/null-deref-ps.c b/test/Analysis/null-deref-ps.c index 9be73a8c0f..1ae94c709b 100644 --- a/test/Analysis/null-deref-ps.c +++ b/test/Analysis/null-deref-ps.c @@ -60,27 +60,7 @@ int f4(int *p) { return *q; // expected-warning{{Dereference of null pointer (loaded from variable 'q')}} } -int f4_b() { - short array[2]; - uintptr_t x = array; // expected-warning{{incompatible pointer to integer conversion}} - short *p = x; // expected-warning{{incompatible integer to pointer conversion}} - - // The following branch should be infeasible. - if (!(p = &array[0])) { - p = 0; - *p = 1; // no-warning - } - - if (p) { - *p = 5; // no-warning - p = 0; - } - else return; // expected-warning {{non-void function 'f4_b' should return a value}} - - *p += 10; // expected-warning{{Dereference of null pointer}} - return 0; -} - +// Placeholder for f4_b, temporarily moved to null-deref-ps-temp.c int f5() { @@ -280,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{{he left operand to '<<' is always 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}} } // PR 4759 - Attribute non-null checking by the analyzer was not correctly -- 2.50.1