This revision was automatically updated to reflect the committed changes. Closed by commit rGba92b274225f: [analyzer] Improved RangeSet::Negate support of unsigned ranges (authored by ASDenysPetrov).
Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D77802/new/ https://reviews.llvm.org/D77802 Files: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp clang/test/Analysis/constraint_manager_negate_difference.c clang/unittests/StaticAnalyzer/CMakeLists.txt clang/unittests/StaticAnalyzer/RangeSetTest.cpp
Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp =================================================================== --- /dev/null +++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp @@ -0,0 +1,130 @@ +//===- unittests/StaticAnalyzer/RangeSetTest.cpp ----------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "clang/Basic/Builtins.h" +#include "clang/Basic/FileManager.h" +#include "clang/Basic/SourceManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h" +#include "clang/Tooling/Tooling.h" +#include "gtest/gtest.h" + +namespace clang { +namespace ento { +namespace { + +// TestCase contains to lists of ranges. +// Original one has to be negated. +// Expected one has to be compared to negated original range. +template <typename T> struct TestCase { + RangeSet original; + RangeSet expected; + + TestCase(BasicValueFactory &BVF, RangeSet::Factory &F, + const std::initializer_list<T> &originalList, + const std::initializer_list<T> &expectedList) + : original(createRangeSetFromList(BVF, F, originalList)), + expected(createRangeSetFromList(BVF, F, expectedList)) {} + +private: + RangeSet createRangeSetFromList(BasicValueFactory &BVF, RangeSet::Factory &F, + const std::initializer_list<T> rangeList) { + llvm::APSInt from(sizeof(T) * 8, std::is_unsigned<T>::value); + llvm::APSInt to = from; + RangeSet rangeSet = F.getEmptySet(); + for (auto it = rangeList.begin(); it != rangeList.end(); it += 2) { + from = *it; + to = *(it + 1); + rangeSet = rangeSet.addRange( + F, RangeSet(F, BVF.getValue(from), BVF.getValue(to))); + } + return rangeSet; + } + + void printNegate(const TestCase &TestCase) { + TestCase.original.print(llvm::dbgs()); + llvm::dbgs() << " => "; + TestCase.expected.print(llvm::dbgs()); + } +}; + +class RangeSetTest : public testing::Test { +protected: + // Init block + std::unique_ptr<ASTUnit> AST = tooling::buildASTFromCode("struct foo;"); + ASTContext &context = AST->getASTContext(); + llvm::BumpPtrAllocator alloc; + BasicValueFactory BVF{context, alloc}; + RangeSet::Factory F; + // End init block + + template <typename T> void checkNegate() { + using type = T; + + // Use next values of the range {MIN, A, B, MID, C, D, MAX}. + + // MID is a value in the middle of the range + // which unary minus does not affect on, + // e.g. int8/int32(0), uint8(128), uint32(2147483648). + + constexpr type MIN = std::numeric_limits<type>::min(); + constexpr type MAX = std::numeric_limits<type>::max(); + constexpr type MID = std::is_signed<type>::value + ? 0 + : ~(static_cast<type>(-1) / static_cast<type>(2)); + constexpr type A = MID - static_cast<type>(42 + 42); + constexpr type B = MID - static_cast<type>(42); + constexpr type C = -B; + constexpr type D = -A; + + static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX, + "Values shall be in an ascending order"); + + // Left {[x, y], [x, y]} is what shall be negated. + // Right {[x, y], [x, y]} is what shall be compared to a negation result. + TestCase<type> cases[] = { + {BVF, F, {MIN, A}, {MIN, MIN, D, MAX}}, + {BVF, F, {MIN, C}, {MIN, MIN, B, MAX}}, + {BVF, F, {MIN, MID}, {MIN, MIN, MID, MAX}}, + {BVF, F, {MIN, MAX}, {MIN, MAX}}, + {BVF, F, {A, D}, {A, D}}, + {BVF, F, {A, B}, {C, D}}, + {BVF, F, {MIN, A, D, MAX}, {MIN, A, D, MAX}}, + {BVF, F, {MIN, B, MID, D}, {MIN, MIN, A, MID, C, MAX}}, + {BVF, F, {MIN, MID, C, D}, {MIN, MIN, A, B, MID, MAX}}, + {BVF, F, {MIN, MID, C, MAX}, {MIN, B, MID, MAX}}, + {BVF, F, {A, MID, D, MAX}, {MIN + 1, A, MID, D}}, + {BVF, F, {A, A}, {D, D}}, + {BVF, F, {MID, MID}, {MID, MID}}, + {BVF, F, {MAX, MAX}, {MIN + 1, MIN + 1}}, + }; + + for (const auto &c : cases) { + // Negate original and check with expected. + RangeSet negatedFromOriginal = c.original.Negate(BVF, F); + EXPECT_EQ(negatedFromOriginal, c.expected); + // Negate negated back and check with original. + RangeSet negatedBackward = negatedFromOriginal.Negate(BVF, F); + EXPECT_EQ(negatedBackward, c.original); + } + } +}; + +TEST_F(RangeSetTest, RangeSetNegateTest) { + checkNegate<int8_t>(); + checkNegate<uint8_t>(); + checkNegate<int16_t>(); + checkNegate<uint16_t>(); + checkNegate<int32_t>(); + checkNegate<uint32_t>(); + checkNegate<int64_t>(); + checkNegate<uint64_t>(); +} + +} // namespace +} // namespace ento +} // namespace clang Index: clang/unittests/StaticAnalyzer/CMakeLists.txt =================================================================== --- clang/unittests/StaticAnalyzer/CMakeLists.txt +++ clang/unittests/StaticAnalyzer/CMakeLists.txt @@ -10,6 +10,7 @@ StoreTest.cpp RegisterCustomCheckersTest.cpp SymbolReaperTest.cpp + RangeSetTest.cpp ) clang_target_link_libraries(StaticAnalysisTests Index: clang/test/Analysis/constraint_manager_negate_difference.c =================================================================== --- clang/test/Analysis/constraint_manager_negate_difference.c +++ clang/test/Analysis/constraint_manager_negate_difference.c @@ -4,7 +4,9 @@ void exit(int); -#define UINT_MAX (~0U) +#define UINT_MIN (0U) +#define UINT_MAX (~UINT_MIN) +#define UINT_MID (UINT_MAX / 2 + 1) #define INT_MAX (UINT_MAX & (UINT_MAX >> 1)) #define INT_MIN (UINT_MAX & ~(UINT_MAX >> 1)) @@ -110,3 +112,48 @@ clang_analyzer_eval(m - n == 0); // expected-warning{{TRUE}} expected-warning{{FALSE}} clang_analyzer_eval(n - m == 0); // expected-warning{{TRUE}} expected-warning{{FALSE}} } + +void negate_unsigned_min(unsigned m, unsigned n) { + if (m - n == UINT_MIN) { + clang_analyzer_eval(n - m == UINT_MIN); // expected-warning{{TRUE}} + clang_analyzer_eval(n - m != UINT_MIN); // expected-warning{{FALSE}} + clang_analyzer_eval(n - m > UINT_MIN); // expected-warning{{FALSE}} + clang_analyzer_eval(n - m < UINT_MIN); // expected-warning{{FALSE}} + } +} + +void negate_unsigned_mid(unsigned m, unsigned n) { + if (m - n == UINT_MID) { + clang_analyzer_eval(n - m == UINT_MID); // expected-warning{{TRUE}} + clang_analyzer_eval(n - m != UINT_MID); // expected-warning{{FALSE}} + } +} + +void negate_unsigned_mid2(unsigned m, unsigned n) { + if (m - n < UINT_MID && m - n > UINT_MIN) { + clang_analyzer_eval(n - m > UINT_MID); // expected-warning{{TRUE}} + clang_analyzer_eval(n - m < UINT_MID); // expected-warning{{FALSE}} + } +} + +void negate_unsigned_max(unsigned m, unsigned n) { + if (m - n == UINT_MAX) { + clang_analyzer_eval(n - m == 1); // expected-warning{{TRUE}} + clang_analyzer_eval(n - m != 1); // expected-warning{{FALSE}} + } +} + +void negate_unsigned_one(unsigned m, unsigned n) { + if (m - n == 1) { + clang_analyzer_eval(n - m == UINT_MAX); // expected-warning{{TRUE}} + clang_analyzer_eval(n - m < UINT_MAX); // expected-warning{{FALSE}} + } +} + +// The next code is a repro for the bug PR41588 +void negated_unsigned_range(unsigned x, unsigned y) { + clang_analyzer_eval(x - y != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}} + clang_analyzer_eval(y - x != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}} + // expected no assertion on the next line + clang_analyzer_eval(x - y != 0); // expected-warning{{FALSE}} expected-warning{{TRUE}} +} Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp +++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp @@ -155,11 +155,11 @@ // or, alternatively, /removing/ all integers between Upper and Lower. RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower, llvm::APSInt Upper) const { - if (!pin(Lower, Upper)) - return F.getEmptySet(); - PrimRangeSet newRanges = F.getEmptySet(); + if (isEmpty() || !pin(Lower, Upper)) + return newRanges; + PrimRangeSet::iterator i = begin(), e = end(); if (Lower <= Upper) IntersectInRange(BV, F, Lower, Upper, newRanges, i, e); @@ -190,33 +190,78 @@ 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. +// Turn all [A, B] ranges to [-B, -A], when "-" is a C-like unary minus +// operation under the values of the type. +// +// We also handle MIN because applying unary minus to MIN does not change it. +// Example 1: +// char x = -128; // -128 is a MIN value in a range of 'char' +// char y = -x; // y: -128 +// Example 2: +// unsigned char x = 0; // 0 is a MIN value in a range of 'unsigned char' +// unsigned char y = -x; // y: 0 +// +// And it makes us to separate the range +// like [MIN, N] to [MIN, MIN] U [-N,MAX]. +// For instance, whole range is {-128..127} and subrange is [-128,-126], +// thus [-128,-127,-126,.....] negates to [-128,.....,126,127]. +// +// Negate restores disrupted ranges on bounds, +// e.g. [MIN, B] => [MIN, MIN] U [-B, MAX] => [MIN, B]. 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))); + if (isEmpty()) + return newRanges; + + const llvm::APSInt sampleValue = getMinValue(); + const llvm::APSInt &MIN = BV.getMinValue(sampleValue); + const llvm::APSInt &MAX = BV.getMaxValue(sampleValue); + + // Handle a special case for MIN value. + iterator i = begin(); + const llvm::APSInt &from = i->From(); + const llvm::APSInt &to = i->To(); + if (from == MIN) { + // If [from, to] are [MIN, MAX], then just return the same [MIN, MAX]. + if (to == MAX) { + newRanges = ranges; + } else { + // Add separate range for the lowest value. + newRanges = F.add(newRanges, Range(MIN, MIN)); + // Skip adding the second range in case when [from, to] are [MIN, MIN]. + if (to != MIN) { + newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX)); + } } + // Skip the first range in the loop. + ++i; + } + + // Negate all other ranges. + for (iterator e = end(); i != e; ++i) { + // Negate int values. + const llvm::APSInt &newFrom = BV.getValue(-i->To()); + const llvm::APSInt &newTo = BV.getValue(-i->From()); + // Add a negated range. + newRanges = F.add(newRanges, Range(newFrom, newTo)); + } + + if (newRanges.isSingleton()) + return newRanges; + + // Try to find and unite next ranges: + // [MIN, MIN] & [MIN + 1, N] => [MIN, N]. + iterator iter1 = newRanges.begin(); + iterator iter2 = std::next(iter1); + + if (iter1->To() == MIN && (iter2->From() - 1) == MIN) { + const llvm::APSInt &to = iter2->To(); + // remove adjacent ranges + newRanges = F.remove(newRanges, *iter1); + newRanges = F.remove(newRanges, *newRanges.begin()); + // add united range + newRanges = F.add(newRanges, Range(MIN, to)); } return newRanges; @@ -527,9 +572,7 @@ 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)) || + if (T->isUnsignedIntegerOrEnumerationType() || T->isSignedIntegerOrEnumerationType()) return negV; }
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
