Author: baloghadamsoftware Date: Thu Jun 28 00:35:23 2018 New Revision: 335814
URL: http://llvm.org/viewvc/llvm-project?rev=335814&view=rev Log: [Analyzer] Constraint Manager Negates Difference If range [m .. n] is stored for symbolic expression A - B, then we can deduce the range for B - A which is [-n .. -m]. This is only true for signed types, unless the range is [0 .. 0]. Differential Revision: https://reviews.llvm.org/D35110 Added: cfe/trunk/test/Analysis/constraint_manager_negate_difference.c Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp cfe/trunk/test/Analysis/ptr-arith.c Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h?rev=335814&r1=335813&r2=335814&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h Thu Jun 28 00:35:23 2018 @@ -115,6 +115,8 @@ public: RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, llvm::APSInt Upper) const; + RangeSet Negate(BasicValueFactory &BV, Factory &F) const; + void print(raw_ostream &os) const; bool operator==(const RangeSet &other) const { Modified: cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp?rev=335814&r1=335813&r2=335814&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp Thu Jun 28 00:35:23 2018 @@ -174,6 +174,38 @@ RangeSet RangeSet::Intersect(BasicValueF return newRanges; } +// Turn all [A, B] ranges to [-B, -A]. Ranges [MIN, B] are turned to range set +// [MIN, MIN] U [-B, MAX], when MIN and MAX are the minimal and the maximal +// signed values of the type. +RangeSet RangeSet::Negate(BasicValueFactory &BV, Factory &F) const { + PrimRangeSet newRanges = F.getEmptySet(); + + for (iterator i = begin(), e = end(); i != e; ++i) { + const llvm::APSInt &from = i->From(), &to = i->To(); + const llvm::APSInt &newTo = (from.isMinSignedValue() ? + BV.getMaxValue(from) : + BV.getValue(- from)); + if (to.isMaxSignedValue() && !newRanges.isEmpty() && + newRanges.begin()->From().isMinSignedValue()) { + assert(newRanges.begin()->To().isMinSignedValue() && + "Ranges should not overlap"); + assert(!from.isMinSignedValue() && "Ranges should not overlap"); + const llvm::APSInt &newFrom = newRanges.begin()->From(); + newRanges = + F.add(F.remove(newRanges, *newRanges.begin()), Range(newFrom, newTo)); + } else if (!to.isMinSignedValue()) { + const llvm::APSInt &newFrom = BV.getValue(- to); + newRanges = F.add(newRanges, Range(newFrom, newTo)); + } + if (from.isMinSignedValue()) { + newRanges = F.add(newRanges, Range(BV.getMinValue(from), + BV.getMinValue(from))); + } + } + + return newRanges; +} + void RangeSet::print(raw_ostream &os) const { bool isFirst = true; os << "{ "; @@ -252,6 +284,8 @@ private: RangeSet::Factory F; RangeSet getRange(ProgramStateRef State, SymbolRef Sym); + const RangeSet* getRangeForMinusSymbol(ProgramStateRef State, + SymbolRef Sym); RangeSet getSymLTRange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, @@ -268,6 +302,7 @@ private: RangeSet getSymGERange(ProgramStateRef St, SymbolRef Sym, const llvm::APSInt &Int, const llvm::APSInt &Adjustment); + }; } // end anonymous namespace @@ -423,9 +458,15 @@ RangeSet RangeConstraintManager::getRang if (ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym)) return *V; + BasicValueFactory &BV = getBasicVals(); + + // If Sym is a difference of symbols A - B, then maybe we have range set + // stored for B - A. + if (const RangeSet *R = getRangeForMinusSymbol(State, Sym)) + return R->Negate(BV, F); + // Lazily generate a new RangeSet representing all possible values for the // given symbol type. - BasicValueFactory &BV = getBasicVals(); QualType T = Sym->getType(); RangeSet Result(F, BV.getMinValue(T), BV.getMaxValue(T)); @@ -441,6 +482,32 @@ RangeSet RangeConstraintManager::getRang return Result; } +// FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to +// obtain the negated symbolic expression instead of constructing the +// symbol manually. This will allow us to support finding ranges of not +// only negated SymSymExpr-type expressions, but also of other, simpler +// expressions which we currently do not know how to negate. +const RangeSet* +RangeConstraintManager::getRangeForMinusSymbol(ProgramStateRef State, + SymbolRef Sym) { + if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) { + if (SSE->getOpcode() == BO_Sub) { + QualType T = Sym->getType(); + SymbolManager &SymMgr = State->getSymbolManager(); + SymbolRef negSym = SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, + SSE->getLHS(), T); + if (const RangeSet *negV = State->get<ConstraintRange>(negSym)) { + // Unsigned range set cannot be negated, unless it is [0, 0]. + if ((negV->getConcreteValue() && + (*negV->getConcreteValue() == 0)) || + T->isSignedIntegerOrEnumerationType()) + return negV; + } + } + } + return nullptr; +} + //===------------------------------------------------------------------------=== // assumeSymX methods: protected interface for RangeConstraintManager. //===------------------------------------------------------------------------===/ Added: cfe/trunk/test/Analysis/constraint_manager_negate_difference.c URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/constraint_manager_negate_difference.c?rev=335814&view=auto ============================================================================== --- cfe/trunk/test/Analysis/constraint_manager_negate_difference.c (added) +++ cfe/trunk/test/Analysis/constraint_manager_negate_difference.c Thu Jun 28 00:35:23 2018 @@ -0,0 +1,98 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection,core.builtin -analyzer-config aggressive-relational-comparison-simplification=true -verify %s + +void clang_analyzer_eval(int); + +void exit(int); + +#define UINT_MAX (~0U) +#define INT_MAX (UINT_MAX & (UINT_MAX >> 1)) +#define INT_MIN (UINT_MAX & ~(UINT_MAX >> 1)) + +extern void __assert_fail (__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__ ((__noreturn__)); +#define assert(expr) \ + ((expr) ? (void)(0) : __assert_fail (#expr, __FILE__, __LINE__, __func__)) + +void assert_in_range(int x) { + assert(x <= ((int)INT_MAX / 4)); + assert(x >= -(((int)INT_MAX) / 4)); +} + +void assert_in_wide_range(int x) { + assert(x <= ((int)INT_MAX / 2)); + assert(x >= -(((int)INT_MAX) / 2)); +} + +void assert_in_range_2(int m, int n) { + assert_in_range(m); + assert_in_range(n); +} + +void equal(int m, int n) { + assert_in_range_2(m, n); + if (m != n) + return; + assert_in_wide_range(m - n); + clang_analyzer_eval(n == m); // expected-warning{{TRUE}} +} + +void non_equal(int m, int n) { + assert_in_range_2(m, n); + if (m == n) + return; + assert_in_wide_range(m - n); + clang_analyzer_eval(n != m); // expected-warning{{TRUE}} +} + +void less_or_equal(int m, int n) { + assert_in_range_2(m, n); + if (m < n) + return; + assert_in_wide_range(m - n); + clang_analyzer_eval(n <= m); // expected-warning{{TRUE}} +} + +void less(int m, int n) { + assert_in_range_2(m, n); + if (m <= n) + return; + assert_in_wide_range(m - n); + clang_analyzer_eval(n < m); // expected-warning{{TRUE}} +} + +void greater_or_equal(int m, int n) { + assert_in_range_2(m, n); + if (m > n) + return; + assert_in_wide_range(m - n); + clang_analyzer_eval(n >= m); // expected-warning{{TRUE}} +} + +void greater(int m, int n) { + assert_in_range_2(m, n); + if (m >= n) + return; + assert_in_wide_range(m - n); + clang_analyzer_eval(n > m); // expected-warning{{TRUE}} +} + +void negate_positive_range(int m, int n) { + if (m - n <= 0) + return; + clang_analyzer_eval(n - m < 0); // expected-warning{{TRUE}} + clang_analyzer_eval(n - m > INT_MIN); // expected-warning{{TRUE}} + clang_analyzer_eval(n - m == INT_MIN); // expected-warning{{FALSE}} +} + +void negate_int_min(int m, int n) { + if (m - n != INT_MIN) + return; + clang_analyzer_eval(n - m == INT_MIN); // expected-warning{{TRUE}} +} + +void negate_mixed(int m, int n) { + if (m -n > INT_MIN && m - n <= 0) + return; + clang_analyzer_eval(n - m <= 0); // expected-warning{{TRUE}} +} Modified: cfe/trunk/test/Analysis/ptr-arith.c URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/ptr-arith.c?rev=335814&r1=335813&r2=335814&view=diff ============================================================================== --- cfe/trunk/test/Analysis/ptr-arith.c (original) +++ cfe/trunk/test/Analysis/ptr-arith.c Thu Jun 28 00:35:23 2018 @@ -265,49 +265,26 @@ void size_implies_comparison(int *lhs, i clang_analyzer_eval((rhs - lhs) > 0); // expected-warning{{TRUE}} } -//------------------------------- -// False positives -//------------------------------- - void zero_implies_reversed_equal(int *lhs, int *rhs) { clang_analyzer_eval((rhs - lhs) == 0); // expected-warning{{UNKNOWN}} if ((rhs - lhs) == 0) { -#ifdef ANALYZER_CM_Z3 clang_analyzer_eval(rhs != lhs); // expected-warning{{FALSE}} clang_analyzer_eval(rhs == lhs); // expected-warning{{TRUE}} -#else - clang_analyzer_eval(rhs != lhs); // expected-warning{{UNKNOWN}} - clang_analyzer_eval(rhs == lhs); // expected-warning{{UNKNOWN}} -#endif return; } clang_analyzer_eval((rhs - lhs) == 0); // expected-warning{{FALSE}} -#ifdef ANALYZER_CM_Z3 clang_analyzer_eval(rhs == lhs); // expected-warning{{FALSE}} clang_analyzer_eval(rhs != lhs); // expected-warning{{TRUE}} -#else - clang_analyzer_eval(rhs == lhs); // expected-warning{{UNKNOWN}} - clang_analyzer_eval(rhs != lhs); // expected-warning{{UNKNOWN}} -#endif } void canonical_equal(int *lhs, int *rhs) { clang_analyzer_eval(lhs == rhs); // expected-warning{{UNKNOWN}} if (lhs == rhs) { -#ifdef ANALYZER_CM_Z3 clang_analyzer_eval(rhs == lhs); // expected-warning{{TRUE}} -#else - clang_analyzer_eval(rhs == lhs); // expected-warning{{UNKNOWN}} -#endif return; } clang_analyzer_eval(lhs == rhs); // expected-warning{{FALSE}} - -#ifdef ANALYZER_CM_Z3 clang_analyzer_eval(rhs == lhs); // expected-warning{{FALSE}} -#else - clang_analyzer_eval(rhs == lhs); // expected-warning{{UNKNOWN}} -#endif } void compare_element_region_and_base(int *p) { _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
