ASDenysPetrov updated this revision to Diff 257617. ASDenysPetrov edited the summary of this revision. ASDenysPetrov added a comment. Herald added a subscriber: mgorny.
Improved Negate function in terms of handling `[MIN,A]U[B,MAX] => [MIN,-B]U[-A,MAX]` (previously was `[MIN,MIN]U[MIN+1,-B]U[-A,MAX]`). Added unit test for Negate function. 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,138 @@ +//===- 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 "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; + } +}; + +class RangeSetTest : public testing::Test { +protected: + // init block + DiagnosticsEngine Diag{new DiagnosticIDs, new DiagnosticOptions}; + FileSystemOptions FileSystemOpts; + FileManager FileMgr{FileSystemOpts}; + SourceManager SM{Diag, FileMgr}; + LangOptions LOpts; + IdentifierTable idents; + SelectorTable sels; + Builtin::Context builtins; + ASTContext context{LOpts, SM, idents, sels, builtins}; + 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); + RangeSet negatedBackward = c.expected.Negate(BVF, F); + EXPECT_EQ(negatedBackward, c.original); + + // c.original.print(llvm::dbgs()); + // llvm::dbgs() << " => "; + // c.expected.print(llvm::dbgs()); + // llvm::dbgs() << " => "; + // negatedFromOriginal.print(llvm::dbgs()); + // llvm::dbgs() << " => "; + // negatedBackward.print(llvm::dbgs()); + // llvm::dbgs() << "\n"; + } + } +}; + +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 @@ -9,6 +9,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 @@ -110,3 +110,9 @@ 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 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}} + 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,32 +190,74 @@ 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]. +// example: 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(); + if (isEmpty()) + return newRanges; + + const llvm::APSInt sampleValue = getMinValue(); + const bool isUnsigned = sampleValue.isUnsigned(); + const llvm::APSInt &MIN = BV.getMinValue(sampleValue); + const llvm::APSInt &MAX = BV.getMaxValue(sampleValue); + bool hasNewRangesMinValue = false; + 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))); + const llvm::APSInt &from = i->From(); + const llvm::APSInt &to = i->To(); + + const bool isFromMinValue = + isUnsigned ? from.isMinValue() : from.isMinSignedValue(); + const bool isToMinValue = + isUnsigned ? to.isMinValue() : to.isMinSignedValue(); + const bool isToMaxValue = + isUnsigned ? to.isMaxValue() : to.isMaxSignedValue(); + + // handle a special case for MIN value + if (isFromMinValue) { + // if [from, to] are [MIN, MAX], then just return the same [MIN, MAX] + if (isToMaxValue) { + newRanges = ranges; + } else { + // add separate range for the lowest value + newRanges = F.add(newRanges, Range(MIN, MIN)); + hasNewRangesMinValue = true; + // skip adding the second range in case when [from, to] are [MIN, MIN] + if (!isToMinValue) { + newRanges = F.add(newRanges, Range(BV.getValue(-to), MAX)); + } + } + } else { + const llvm::APSInt &newFrom = BV.getValue(-to); + const llvm::APSInt &newTo = BV.getValue(-from); + + // unite ranges [MIN, MIN] & [MIN + 1, N] => [MIN, N] + if (hasNewRangesMinValue && (newFrom - 1) == MIN) { + hasNewRangesMinValue = false; + newRanges = F.remove(newRanges, *newRanges.begin()); + newRanges = F.add(newRanges, Range(MIN, newTo)); + } else { + // otherwise add an negated range + newRanges = F.add(newRanges, Range(newFrom, newTo)); + } } } @@ -527,9 +569,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
