vsavchenko created this revision.
vsavchenko added reviewers: NoQ, dcoughlin, xazax.hun, Szelethus,
ASDenysPetrov, steakhal.
Herald added subscribers: cfe-commits, martong, Charusso, dkrupp, donat.nagy,
mikhail.ramalho, a.sidorin, mgrang, rnkovacs, szepet, baloghadamsoftware.
Herald added a project: clang.
vsavchenko requested review of this revision.
ImmutableSet doesn't seem like the perfect fit for the RangeSet
data structure. It is good for saving memory in a persistent
setting, but not for the case when the population of the container
is tiny. This commit replaces RangeSet implementation and
redesigns the most common operations to be more efficient.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D86465
Files:
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp
clang/unittests/StaticAnalyzer/RangeSetTest.cpp
Index: clang/unittests/StaticAnalyzer/RangeSetTest.cpp
===================================================================
--- clang/unittests/StaticAnalyzer/RangeSetTest.cpp
+++ clang/unittests/StaticAnalyzer/RangeSetTest.cpp
@@ -11,120 +11,330 @@
#include "clang/Basic/SourceManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/APSInt.h"
+#include "llvm/Support/raw_ostream.h"
+#include "gtest/gtest-typed-test.h"
#include "gtest/gtest.h"
+using namespace clang;
+using namespace ento;
+
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;
- }
+template <class RangeOrSet> static std::string toString(const RangeOrSet &Obj) {
+ std::string ObjRepresentation;
+ llvm::raw_string_ostream SS(ObjRepresentation);
+ Obj.print(SS);
+ return SS.str();
+}
+LLVM_ATTRIBUTE_UNUSED static std::string toString(const llvm::APSInt &Point) {
+ return Point.toString(10);
+}
+// We need it here for better fail diagnostics from gtest.
+LLVM_ATTRIBUTE_UNUSED static std::ostream &operator<<(std::ostream &OS,
+ const RangeSet &Set) {
+ return OS << toString(Set);
+}
- void printNegate(const TestCase &TestCase) {
- TestCase.original.print(llvm::dbgs());
- llvm::dbgs() << " => ";
- TestCase.expected.print(llvm::dbgs());
- }
-};
+} // namespace ento
+} // namespace clang
+
+namespace {
-class RangeSetTest : public testing::Test {
-protected:
+template <typename BaseType> class RangeSetTest : public testing::Test {
+public:
// 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;
+ ASTContext &Context = AST->getASTContext();
+ llvm::BumpPtrAllocator Arena;
+ BasicValueFactory BVF{Context, Arena};
+ RangeSet::Factory F{BVF};
// 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);
+ using Self = RangeSetTest<BaseType>;
+ using RawRange = std::pair<BaseType, BaseType>;
+ using RawRangeSet = std::initializer_list<RawRange>;
+
+ static constexpr BaseType getMin() {
+ return std::numeric_limits<BaseType>::min();
+ }
+ static constexpr BaseType getMax() {
+ return std::numeric_limits<BaseType>::max();
+ }
+ static constexpr BaseType getMid() {
+ return isSigned() ? 0 : ~(fromInt(-1) / fromInt(2));
+ }
+
+ static constexpr bool isSigned() { return std::is_signed<BaseType>::value; }
+ static constexpr BaseType fromInt(int X) { return static_cast<BaseType>(X); }
+
+ static llvm::APSInt Base;
+ const llvm::APSInt &from(BaseType X) {
+ llvm::APSInt Dummy = Base;
+ Dummy = X;
+ return BVF.getValue(Dummy);
+ }
+
+ Range from(const RawRange &Init) {
+ return Range(from(Init.first), from(Init.second));
+ }
+
+ RangeSet from(const RawRangeSet &Init) {
+ RangeSet RangeSet = F.getEmptySet();
+ for (const auto &Raw : Init) {
+ RangeSet = F.add(RangeSet, from(Raw));
}
+ return RangeSet;
+ }
+
+ template <class F, class... RawArgTypes>
+ void wrap(F ActualFunction, RawArgTypes &&...Args) {
+ (this->*ActualFunction)(from(std::forward<RawArgTypes>(Args))...);
+ }
+
+ void checkNegateImpl(RangeSet Original, RangeSet Expected) {
+ RangeSet NegatedFromOriginal = F.negate(Original);
+ EXPECT_EQ(NegatedFromOriginal, Expected);
+ // Negate negated back and check with original.
+ RangeSet NegatedBackward = F.negate(NegatedFromOriginal);
+ EXPECT_EQ(NegatedBackward, Original);
+ }
+
+ void checkNegate(RawRangeSet RawOriginal, RawRangeSet RawExpected) {
+ wrap(&Self::checkNegateImpl, RawOriginal, RawExpected);
+ }
+
+ template <class PointOrSet>
+ void checkIntersectImpl(RangeSet LHS, PointOrSet RHS, RangeSet Expected) {
+ RangeSet Result = F.intersect(LHS, RHS);
+ EXPECT_EQ(Result, Expected)
+ << "while intersecting " << toString(LHS) << " and " << toString(RHS);
+ }
+
+ void checkIntersectRangeImpl(RangeSet LHS, const llvm::APSInt &Lower,
+ const llvm::APSInt &Upper, RangeSet Expected) {
+ RangeSet Result = F.intersect(LHS, Lower, Upper);
+ EXPECT_EQ(Result, Expected)
+ << "while intersecting " << toString(LHS) << " and [" << toString(Lower)
+ << ", " << toString(Upper) << "]";
+ }
+
+ void checkIntersect(RawRangeSet RawLHS, RawRangeSet RawRHS,
+ RawRangeSet RawExpected) {
+ wrap(&Self::checkIntersectImpl<RangeSet>, RawLHS, RawRHS, RawExpected);
+ }
+
+ void checkIntersect(RawRangeSet RawLHS, BaseType RawRHS,
+ RawRangeSet RawExpected) {
+ wrap(&Self::checkIntersectImpl<const llvm::APSInt &>, RawLHS, RawRHS,
+ RawExpected);
+ }
+
+ void checkIntersect(RawRangeSet RawLHS, BaseType RawLower, BaseType RawUpper,
+ RawRangeSet RawExpected) {
+ wrap(&Self::checkIntersectRangeImpl, RawLHS, RawLower, RawUpper,
+ RawExpected);
+ }
+
+ void checkContainsImpl(RangeSet LHS, const llvm::APSInt &RHS, bool Expected) {
+ bool Result = LHS.contains(RHS);
+ EXPECT_EQ(Result, Expected)
+ << toString(LHS) << (Result ? " contains " : " doesn't contain ")
+ << toString(RHS);
+ }
+
+ void checkContains(RawRangeSet RawLHS, BaseType RawRHS, bool Expected) {
+ checkContainsImpl(from(RawLHS), from(RawRHS), Expected);
+ }
+
+ template <class RHSType>
+ void checkAddImpl(RangeSet LHS, RHSType RHS, RangeSet Expected) {
+ RangeSet Result = F.add(LHS, RHS);
+ EXPECT_EQ(Result, Expected)
+ << "while adding " << toString(LHS) << " and " << toString(RHS);
+ }
+
+ void checkAdd(RawRangeSet RawLHS, RawRange RawRHS, RawRangeSet RawExpected) {
+ wrap(&Self::checkAddImpl<Range>, RawLHS, RawRHS, RawExpected);
+ }
+
+ void checkAdd(RawRangeSet RawLHS, RawRangeSet RawRHS,
+ RawRangeSet RawExpected) {
+ wrap(&Self::checkAddImpl<RangeSet>, RawRHS, RawLHS, RawExpected);
+ }
+
+ void checkDeleteImpl(const llvm::APSInt &Point, RangeSet From,
+ RangeSet Expected) {
+ RangeSet Result = F.deletePoint(Point, From);
+ EXPECT_EQ(Result, Expected)
+ << "while deleting " << toString(Point) << " from " << toString(From);
+ }
+
+ void checkDelete(BaseType Point, RawRangeSet RawFrom,
+ RawRangeSet RawExpected) {
+ wrap(&Self::checkDeleteImpl, Point, RawFrom, RawExpected);
}
};
-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
+
+template <typename BaseType>
+llvm::APSInt RangeSetTest<BaseType>::Base{sizeof(BaseType) * 8, !isSigned()};
+
+using IntTypes = ::testing::Types<int8_t, uint8_t, int16_t, uint16_t, int32_t,
+ uint32_t, int64_t, uint64_t>;
+TYPED_TEST_CASE(RangeSetTest, IntTypes);
+
+TYPED_TEST(RangeSetTest, RangeSetNegateTest) {
+ // Use next values of the range {MIN, A, B, MID, C, D, MAX}.
+
+ constexpr TypeParam MIN = TestFixture::getMin();
+ constexpr TypeParam MAX = TestFixture::getMax();
+ // 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 TypeParam MID = TestFixture::getMid();
+ constexpr TypeParam A = MID - TestFixture::fromInt(42 + 42);
+ constexpr TypeParam B = MID - TestFixture::fromInt(42);
+ constexpr TypeParam C = -B;
+ constexpr TypeParam D = -A;
+
+ static_assert(MIN < A && A < B && B < MID && MID < C && C < D && D < MAX,
+ "Values shall be in an ascending order");
+
+ this->checkNegate({{MIN, A}}, {{MIN, MIN}, {D, MAX}});
+ this->checkNegate({{MIN, C}}, {{MIN, MIN}, {B, MAX}});
+ this->checkNegate({{MIN, MID}}, {{MIN, MIN}, {MID, MAX}});
+ this->checkNegate({{MIN, MAX}}, {{MIN, MAX}});
+ this->checkNegate({{A, D}}, {{A, D}});
+ this->checkNegate({{A, B}}, {{C, D}});
+ this->checkNegate({{MIN, A}, {D, MAX}}, {{MIN, A}, {D, MAX}});
+ this->checkNegate({{MIN, B}, {MID, D}}, {{MIN, MIN}, {A, MID}, {C, MAX}});
+ this->checkNegate({{MIN, MID}, {C, D}}, {{MIN, MIN}, {A, B}, {MID, MAX}});
+ this->checkNegate({{MIN, MID}, {C, MAX}}, {{MIN, B}, {MID, MAX}});
+ this->checkNegate({{A, MID}, {D, MAX}}, {{MIN + 1, A}, {MID, D}});
+ this->checkNegate({{A, A}}, {{D, D}});
+ this->checkNegate({{MID, MID}}, {{MID, MID}});
+ this->checkNegate({{MAX, MAX}}, {{MIN + 1, MIN + 1}});
}
-} // namespace
-} // namespace ento
-} // namespace clang
+TYPED_TEST(RangeSetTest, RangeSetPointIntersectTest) {
+ // Check that we can correctly intersect empty sets.
+ this->checkIntersect({}, 42, {});
+ // Check that intersection with itself produces the same set.
+ this->checkIntersect({{42, 42}}, 42, {{42, 42}});
+ // Check more general cases.
+ this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 42, {});
+ this->checkIntersect({{0, 10}, {20, 30}, {30, 60}}, 42, {{42, 42}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetRangeIntersectTest) {
+ constexpr TypeParam MIN = TestFixture::getMin();
+ constexpr TypeParam MAX = TestFixture::getMax();
+
+ // Check that we can correctly intersect empty sets.
+ this->checkIntersect({}, 10, 20, {});
+ this->checkIntersect({}, 20, 10, {});
+ // Check that intersection with itself produces the same set.
+ this->checkIntersect({{10, 20}}, 10, 20, {{10, 20}});
+ this->checkIntersect({{MIN, 10}, {20, MAX}}, 20, 10, {{MIN, 10}, {20, MAX}});
+ // Check non-overlapping range intersections.
+ this->checkIntersect({{10, 20}}, 21, 9, {});
+ this->checkIntersect({{MIN, 9}, {21, MAX}}, 10, 20, {});
+ // Check more general cases.
+ this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 10, 35,
+ {{10, 10}, {20, 30}, {30, 35}});
+ this->checkIntersect({{0, 10}, {20, 30}, {30, 40}, {50, 60}}, 35, 10,
+ {{0, 10}, {35, 40}, {50, 60}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetGenericIntersectTest) {
+ // Check that we can correctly intersect empty sets.
+ this->checkIntersect({}, {}, {});
+ this->checkIntersect({}, {{0, 10}}, {});
+ this->checkIntersect({{0, 10}}, {}, {});
+
+ this->checkIntersect({{0, 10}}, {{4, 6}}, {{4, 6}});
+ this->checkIntersect({{0, 10}}, {{4, 20}}, {{4, 10}});
+ // Check that intersection with points works as expected.
+ this->checkIntersect({{0, 10}}, {{4, 4}}, {{4, 4}});
+ // All ranges are closed, check that intersection with edge points works as
+ // expected.
+ this->checkIntersect({{0, 10}}, {{10, 10}}, {{10, 10}});
+
+ // Let's check that we can skip some intervals and partially intersect
+ // other intervals.
+ this->checkIntersect({{0, 2}, {4, 5}, {6, 9}, {10, 11}, {12, 12}, {13, 15}},
+ {{8, 14}, {20, 30}},
+ {{8, 9}, {10, 11}, {12, 12}, {13, 14}});
+ // Check more generic case.
+ this->checkIntersect(
+ {{0, 1}, {2, 3}, {5, 6}, {7, 15}, {25, 30}},
+ {{4, 10}, {11, 11}, {12, 16}, {17, 17}, {19, 20}, {21, 23}, {24, 27}},
+ {{5, 6}, {7, 10}, {11, 11}, {12, 15}, {25, 27}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetContainsTest) {
+ // Check with an empty set.
+ this->checkContains({}, 10, false);
+ // Check contains with sets of size one:
+ // * when the whole range is less
+ this->checkContains({{0, 5}}, 10, false);
+ // * when the whole range is greater
+ this->checkContains({{20, 25}}, 10, false);
+ // * when the range is just the point we are looking for
+ this->checkContains({{10, 10}}, 10, true);
+ // * when the range starts with the point
+ this->checkContains({{10, 15}}, 10, true);
+ // * when the range ends with the point
+ this->checkContains({{5, 10}}, 10, true);
+ // * when the range has the point somewhere in the middle
+ this->checkContains({{0, 25}}, 10, true);
+ // Check similar cases, but with larger sets.
+ this->checkContains({{0, 5}, {10, 10}, {15, 20}}, 10, true);
+ this->checkContains({{0, 5}, {10, 12}, {15, 20}}, 10, true);
+ this->checkContains({{0, 5}, {5, 7}, {8, 10}, {12, 41}}, 10, true);
+
+ constexpr TypeParam MIN = TestFixture::getMin();
+ constexpr TypeParam MAX = TestFixture::getMax();
+ constexpr TypeParam MID = TestFixture::getMid();
+ this->checkContains({{MIN, MAX}}, 0, true);
+ this->checkContains({{MIN, MAX}}, MID, true);
+ this->checkContains({{MIN, MAX}}, -10, true);
+ this->checkContains({{MIN, MAX}}, 10, true);
+}
+
+TYPED_TEST(RangeSetTest, RangeSetAddTest) {
+ // Check adding single ranges.
+ this->checkAdd({}, {10, 20}, {{10, 20}});
+ this->checkAdd({{0, 5}}, {10, 20}, {{0, 5}, {10, 20}});
+ this->checkAdd({{0, 5}, {30, 40}}, {10, 20}, {{0, 5}, {10, 20}, {30, 40}});
+
+ // Check adding whole sets of ranges.
+ this->checkAdd({{0, 5}}, {{10, 20}}, {{0, 5}, {10, 20}});
+ // Check that ordering of ranges is as expected.
+ this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}}, {{0, 5}, {10, 20}, {30, 40}});
+ this->checkAdd({{0, 5}, {30, 40}}, {{10, 20}, {50, 60}},
+ {{0, 5}, {10, 20}, {30, 40}, {50, 60}});
+ this->checkAdd({{10, 20}, {50, 60}}, {{0, 5}, {30, 40}, {70, 80}},
+ {{0, 5}, {10, 20}, {30, 40}, {50, 60}, {70, 80}});
+}
+
+TYPED_TEST(RangeSetTest, RangeSetDeletePointTest) {
+ constexpr TypeParam MIN = TestFixture::getMin();
+ constexpr TypeParam MAX = TestFixture::getMax();
+ constexpr TypeParam MID = TestFixture::getMid();
+
+ this->checkDelete(MID, {{MIN, MAX}}, {{MIN, MID - 1}, {MID + 1, MAX}});
+ // Check that delete works with an empty set.
+ this->checkDelete(10, {}, {});
+ // Check that delete can remove entire ranges.
+ this->checkDelete(10, {{10, 10}}, {});
+ this->checkDelete(10, {{0, 5}, {10, 10}, {20, 30}}, {{0, 5}, {20, 30}});
+ // Check that delete can split existing ranges into two.
+ this->checkDelete(10, {{0, 5}, {7, 15}, {20, 30}},
+ {{0, 5}, {7, 9}, {11, 15}, {20, 30}});
+ // Check that delete of the point not from the range set works as expected.
+ this->checkDelete(10, {{0, 5}, {20, 30}}, {{0, 5}, {20, 30}});
+}
Index: clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangedConstraintManager.cpp
@@ -220,5 +220,4 @@
}
} // end of namespace ento
-
} // end of namespace clang
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -19,7 +19,10 @@
#include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/ImmutableSet.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <iterator>
using namespace clang;
using namespace ento;
@@ -97,47 +100,59 @@
return CmpOpTable[getIndexFromOp(CurrentOP)][CmpOpCount];
}
};
+
//===----------------------------------------------------------------------===//
// RangeSet implementation
//===----------------------------------------------------------------------===//
-void RangeSet::IntersectInRange(BasicValueFactory &BV, Factory &F,
- const llvm::APSInt &Lower,
- const llvm::APSInt &Upper,
- PrimRangeSet &newRanges,
- PrimRangeSet::iterator &i,
- PrimRangeSet::iterator &e) const {
- // There are six cases for each range R in the set:
- // 1. R is entirely before the intersection range.
- // 2. R is entirely after the intersection range.
- // 3. R contains the entire intersection range.
- // 4. R starts before the intersection range and ends in the middle.
- // 5. R starts in the middle of the intersection range and ends after it.
- // 6. R is entirely contained in the intersection range.
- // These correspond to each of the conditions below.
- for (/* i = begin(), e = end() */; i != e; ++i) {
- if (i->To() < Lower) {
- continue;
- }
- if (i->From() > Upper) {
- break;
- }
+RangeSet::ContainerType RangeSet::Factory::EmptySet{};
- if (i->Includes(Lower)) {
- if (i->Includes(Upper)) {
- newRanges =
- F.add(newRanges, Range(BV.getValue(Lower), BV.getValue(Upper)));
- break;
- } else
- newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To()));
- } else {
- if (i->Includes(Upper)) {
- newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper)));
- break;
- } else
- newRanges = F.add(newRanges, *i);
- }
+RangeSet RangeSet::Factory::add(RangeSet Original, Range Element) {
+ ContainerType Result;
+ Result.reserve(Original.size() + 1);
+
+ iterator Lower = llvm::lower_bound(Original, Element);
+ Result.insert(Result.end(), Original.begin(), Lower);
+ Result.push_back(Element);
+ Result.insert(Result.end(), Lower, Original.end());
+
+ return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::getSet(Range From) {
+ ContainerType Result;
+ Result.push_back(From);
+ return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::makePersistent(ContainerType &&From) {
+ llvm::FoldingSetNodeID ID;
+ void *InsertPos;
+
+ From.Profile(ID);
+ ContainerType *Result = Cache.FindNodeOrInsertPos(ID, InsertPos);
+
+ if (!Result) {
+ // It is cheaper to fully construct the resulting range on stack
+ // and move it to the freshly allocated buffer if we don't have
+ // a set like this already.
+ Result = construct(std::move(From));
+ Cache.InsertNode(Result, InsertPos);
}
+
+ return Result;
+}
+
+RangeSet::ContainerType *RangeSet::Factory::construct(ContainerType &&From) {
+ void *Buffer = Arena.Allocate();
+ return new (Buffer) ContainerType(std::move(From));
+}
+
+RangeSet RangeSet::Factory::add(RangeSet LHS, RangeSet RHS) {
+ ContainerType Result;
+ std::merge(LHS.begin(), LHS.end(), RHS.begin(), RHS.end(),
+ std::back_inserter(Result));
+ return makePersistent(std::move(Result));
}
const llvm::APSInt &RangeSet::getMinValue() const {
@@ -147,22 +162,32 @@
const llvm::APSInt &RangeSet::getMaxValue() const {
assert(!isEmpty());
- // NOTE: It's a shame that we can't implement 'getMaxValue' without scanning
- // the whole tree to get to the last element.
- // llvm::ImmutableSet should support decrement for 'end' iterators
- // or reverse order iteration.
- auto It = begin();
- for (auto End = end(); std::next(It) != End; ++It) {
- }
- return It->To();
+ return std::prev(end())->To();
}
-bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
- if (isEmpty()) {
- // This range is already infeasible.
+bool RangeSet::containsImpl(llvm::APSInt &Point) const {
+ if (isEmpty() || !pin(Point))
return false;
- }
+ Range Dummy(Point);
+ iterator It = llvm::upper_bound(*this, Dummy);
+ if (It == begin())
+ return false;
+
+ --It;
+ return It->Includes(Point);
+}
+
+bool RangeSet::pin(llvm::APSInt &Point) const {
+ APSIntType Type(getMinValue());
+ if (Type.testInRange(Point, true) != APSIntType::RTR_Within)
+ return false;
+
+ Type.apply(Point);
+ return true;
+}
+
+bool RangeSet::pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const {
// This function has nine cases, the cartesian product of range-testing
// both the upper and lower bounds against the symbol's type.
// Each case requires a different pinning operation.
@@ -243,129 +268,216 @@
return true;
}
-// Returns a set containing the values in the receiving set, intersected with
-// the closed range [Lower, Upper]. Unlike the Range type, this range uses
-// modular arithmetic, corresponding to the common treatment of C integer
-// overflow. Thus, if the Lower bound is greater than the Upper bound, the
-// range is taken to wrap around. This is equivalent to taking the
-// intersection with the two ranges [Min, Upper] and [Lower, Max],
-// or, alternatively, /removing/ all integers between Upper and Lower.
-RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
- llvm::APSInt Lower, llvm::APSInt Upper) const {
- 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);
- else {
- // The order of the next two statements is important!
- // IntersectInRange() does not reset the iteration state for i and e.
- // Therefore, the lower range most be handled first.
- IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e);
- IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e);
- }
-
- return newRanges;
-}
-
-// Returns a set containing the values in the receiving set, intersected with
-// the range set passed as parameter.
-RangeSet RangeSet::Intersect(BasicValueFactory &BV, Factory &F,
- const RangeSet &Other) const {
- PrimRangeSet newRanges = F.getEmptySet();
-
- for (iterator i = Other.begin(), e = Other.end(); i != e; ++i) {
- RangeSet newPiece = Intersect(BV, F, i->From(), i->To());
- for (iterator j = newPiece.begin(), ee = newPiece.end(); j != ee; ++j) {
- newRanges = F.add(newRanges, *j);
- }
+RangeSet RangeSet::Factory::intersect(RangeSet What, llvm::APSInt Lower,
+ llvm::APSInt Upper) {
+ if (What.isEmpty() || !What.pin(Lower, Upper))
+ return getEmptySet();
+
+ ContainerType DummyContainer;
+
+ if (Lower <= Upper) {
+ // [Lower, Upper] is a regular range.
+ //
+ // Shortcut: check that there is even a possibility of the intersection
+ // by checking the two following situations:
+ //
+ // <---[ What ]---[------]------>
+ // Lower Upper
+ // -or-
+ // <----[------]----[ What ]---->
+ // Lower Upper
+ if (What.getMaxValue() < Lower || Upper < What.getMinValue())
+ return getEmptySet();
+
+ DummyContainer.push_back(
+ Range(ValueFactory.getValue(Lower), ValueFactory.getValue(Upper)));
+ } else {
+ // [Lower, Upper] is an inverted range, i.e. [MIN, Upper] U [Lower, MAX]
+ //
+ // Shortcut: check that there is even a possibility of the intersection
+ // by checking the following situation:
+ //
+ // <------]---[ What ]---[------>
+ // Upper Lower
+ if (What.getMaxValue() < Lower && Upper < What.getMinValue())
+ return getEmptySet();
+
+ DummyContainer.push_back(
+ Range(ValueFactory.getMinValue(Upper), ValueFactory.getValue(Upper)));
+ DummyContainer.push_back(
+ Range(ValueFactory.getValue(Lower), ValueFactory.getMaxValue(Lower)));
}
- return newRanges;
+ return intersect(*What.Impl, DummyContainer);
}
-// 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();
+RangeSet RangeSet::Factory::intersect(const RangeSet::ContainerType &LHS,
+ const RangeSet::ContainerType &RHS) {
+ ContainerType Result;
+ Result.reserve(std::max(LHS.size(), RHS.size()));
+
+ iterator First = LHS.begin(), Second = RHS.begin(), FirstEnd = LHS.end(),
+ SecondEnd = RHS.end();
+
+ auto swap = [&First, &FirstEnd, &Second, &SecondEnd]() {
+ std::swap(First, Second);
+ std::swap(FirstEnd, SecondEnd);
+ };
+
+ // If we ran out of ranges in one set, but not the other,
+ // it means that those elements are definitely not in the
+ // intersection.
+ while (First != FirstEnd && Second != SecondEnd) {
+ // We want to keep the following invariant at all times:
+ //
+ // ----[ First ---------------------->
+ // --------[ Second ----------------->
+ if (Second->From() < First->From())
+ swap();
+
+ // Loop where the invariant holds:
+ do {
+ // Check for the following situation:
+ //
+ // ----[ First ]--------------------->
+ // ---------------[ Second ]--------->
+ //
+ // which means that...
+ if (Second->From() > First->To()) {
+ // ...First is not in the intersection.
+ //
+ // We should move on to the next range after First and break out of the
+ // loop because the invariant might not be true.
+ ++First;
+ break;
+ }
+
+ // We have a guaranteed intersection at this point!
+ // And this is the current situation:
+ //
+ // ----[ First ]----------------->
+ // -------[ Second ------------------>
+ //
+ // Additionally, it definitely starts with Second->From().
+ const llvm::APSInt &IntersectionStart = Second->From();
+
+ // It is important to know which of the two ranges' ends
+ // is greater. That "longer" range might have some other
+ // intersections, while the "shorter" range might not.
+ if (Second->To() > First->To())
+ // Here we make a decision to keep First as the "longer"
+ // range.
+ swap();
+
+ // At this point, we have the following situation:
+ //
+ // ---- First ]-------------------->
+ // ---- Second ]--[ ++Second ---------->
+ //
+ // We don't know the relationship between First->From and
+ // Second->From and we don't know whether ++Second intersects
+ // with First.
+ //
+ // However, we know that [IntersectionStart, Second->To] is
+ // a part of the intersection...
+ Result.push_back(Range(IntersectionStart, Second->To()));
+ ++Second;
+ // ...and that the invariant will hold for a valid ++Second
+ // because First->From <= Second->To < ++Second->From.
+ } while (Second != SecondEnd);
+ }
+
+ if (Result.empty())
+ return getEmptySet();
+
+ return makePersistent(std::move(Result));
+}
+
+RangeSet RangeSet::Factory::intersect(RangeSet LHS, RangeSet RHS) {
+ // Shortcut: let's see if the intersection is even possible.
+ if (LHS.isEmpty() || RHS.isEmpty() || LHS.getMaxValue() < RHS.getMinValue() ||
+ RHS.getMaxValue() < LHS.getMinValue())
+ return getEmptySet();
+
+ return intersect(*LHS.Impl, *RHS.Impl);
+}
- if (isEmpty())
- return newRanges;
+RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) {
+ if (LHS.containsImpl(Point))
+ return getSet(ValueFactory.getValue(Point));
- const llvm::APSInt sampleValue = getMinValue();
- const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
- const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
+ return getEmptySet();
+}
+
+RangeSet RangeSet::Factory::negate(RangeSet What) {
+ if (What.isEmpty())
+ return getEmptySet();
+
+ ContainerType Result;
+ Result.reserve(What.size());
+
+ const llvm::APSInt SampleValue = What.getMinValue();
+ const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
+ const llvm::APSInt &MAX = ValueFactory.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;
+ iterator It = What.begin();
+ iterator End = What.end();
+
+ const llvm::APSInt &From = It->From();
+ const llvm::APSInt &To = It->To();
+
+ if (From == MIN) {
+ // If [From, To] are [MIN, MAX], then just return the same [MIN, MAX].
+ if (To == MAX) {
+ Result.insert(Result.end(), What.begin(), What.end());
+ return makePersistent(std::move(Result));
+ }
+
+ iterator Last = std::prev(End);
+
+ // Try to find and unite the following ranges:
+ // [MIN, MIN] & [MIN + 1, N] => [MIN, N].
+ if (Last->To() == MAX) {
+ // It means that in the original range we have ranges
+ // [MIN, A], ... , [B, MAX]
+ // And the result should be [MIN, -B], ..., [-A, MAX]
+ Result.push_back(Range(MIN, ValueFactory.getValue(-Last->From())));
+ // We already negated Last, so we can skip it.
+ End = Last;
} 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));
- }
+ // Add a separate range for the lowest value.
+ Result.push_back(Range(MIN, MIN));
+ }
+
+ // Skip adding the second range in case when [From, To] are [MIN, MIN].
+ if (To != MIN) {
+ Result.push_back(Range(ValueFactory.getValue(-To), MAX));
}
+
// Skip the first range in the loop.
- ++i;
+ ++It;
}
// Negate all other ranges.
- for (iterator e = end(); i != e; ++i) {
+ for (; It != End; ++It) {
// 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;
+ const llvm::APSInt &NewFrom = ValueFactory.getValue(-It->To());
+ const llvm::APSInt &NewTo = ValueFactory.getValue(-It->From());
- // 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));
+ // Add a negated range.
+ Result.push_back(Range(NewFrom, NewTo));
}
- return newRanges;
+ llvm::sort(Result);
+ return makePersistent(std::move(Result));
}
-RangeSet RangeSet::Delete(BasicValueFactory &BV, Factory &F,
- const llvm::APSInt &Point) const {
+RangeSet RangeSet::Factory::deletePoint(const llvm::APSInt &Point,
+ RangeSet From) {
+ if (!From.contains(Point))
+ return From;
+
llvm::APSInt Upper = Point;
llvm::APSInt Lower = Point;
@@ -373,7 +485,11 @@
--Lower;
// Notice that the lower bound is greater than the upper bound.
- return Intersect(BV, F, Upper, Lower);
+ return intersect(From, Upper, Lower);
+}
+
+void Range::print(raw_ostream &os) const {
+ os << '[' << From().toString(10) << ", " << To().toString(10) << ']';
}
void RangeSet::print(raw_ostream &os) const {
@@ -385,8 +501,7 @@
else
os << ", ";
- os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
- << ']';
+ i->print(os);
}
os << " }";
}
@@ -651,7 +766,7 @@
RangeSet Second, RestTy... Tail) {
// Here we call either the <RangeSet,RangeSet,...> or <RangeSet,...> version
// of the function and can be sure that the result is RangeSet.
- return intersect(BV, F, Head.Intersect(BV, F, Second), Tail...);
+ return intersect(BV, F, F.intersect(Head, Second), Tail...);
}
template <class SecondTy, class... RestTy>
@@ -940,7 +1055,7 @@
/// Return a range set subtracting zero from \p Domain.
RangeSet assumeNonZero(RangeSet Domain, QualType T) {
APSIntType IntType = ValueFactory.getAPSIntType(T);
- return Domain.Delete(ValueFactory, RangeFactory, IntType.getZeroValue());
+ return RangeFactory.deletePoint(IntType.getZeroValue(), Domain);
}
// FIXME: Once SValBuilder supports unary minus, we should use SValBuilder to
@@ -963,7 +1078,7 @@
SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), T);
if (const RangeSet *NegatedRange = getConstraint(State, NegatedSym)) {
- return NegatedRange->Negate(ValueFactory, RangeFactory);
+ return RangeFactory.negate(*NegatedRange);
}
}
}
@@ -1257,7 +1372,7 @@
class RangeConstraintManager : public RangedConstraintManager {
public:
RangeConstraintManager(ExprEngine *EE, SValBuilder &SVB)
- : RangedConstraintManager(EE, SVB) {}
+ : RangedConstraintManager(EE, SVB), F(getBasicVals()) {}
//===------------------------------------------------------------------===//
// Implementation for interface from ConstraintManager.
@@ -1403,8 +1518,8 @@
// be simply a constant because we can't reason about range disequalities.
if (const llvm::APSInt *Point = Constraint.getConcreteValue())
for (EquivalenceClass DisequalClass : Class.getDisequalClasses(State)) {
- RangeSet UpdatedConstraint =
- getRange(State, DisequalClass).Delete(getBasicVals(), F, *Point);
+ RangeSet UpdatedConstraint = getRange(State, DisequalClass);
+ UpdatedConstraint = F.deletePoint(*Point, UpdatedConstraint);
Constraints = CF.add(Constraints, DisequalClass, UpdatedConstraint);
}
@@ -1703,7 +1818,7 @@
RangeSet FirstConstraint = SymbolicRangeInferrer::inferRange(
VF, RF, State, First.getRepresentativeSymbol());
- FirstConstraint = FirstConstraint.Delete(VF, RF, *Point);
+ FirstConstraint = RF.deletePoint(*Point, FirstConstraint);
Constraints = CRF.add(Constraints, First, FirstConstraint);
}
}
@@ -1854,7 +1969,7 @@
llvm::APSInt Zero = IntType.getZeroValue();
// Check if zero is in the set of possible values.
- if (Ranges->Intersect(BV, F, Zero, Zero).isEmpty())
+ if (!Ranges->contains(Zero))
return false;
// Zero is a possible value, but it is not the /only/ possible value.
@@ -2040,7 +2155,8 @@
llvm::APSInt Point = AdjustmentType.convert(Int) - Adjustment;
- RangeSet New = getRange(St, Sym).Delete(getBasicVals(), F, Point);
+ RangeSet New = getRange(St, Sym);
+ New = F.deletePoint(Point, New);
if (New.isEmpty())
// this is infeasible assumption
@@ -2061,7 +2177,8 @@
// [Int-Adjustment, Int-Adjustment]
llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
- RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
+ RangeSet New = getRange(St, Sym);
+ New = F.intersect(New, AdjInt);
if (New.isEmpty())
// this is infeasible assumption
@@ -2096,7 +2213,8 @@
llvm::APSInt Upper = ComparisonVal - Adjustment;
--Upper;
- return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+ RangeSet Result = getRange(St, Sym);
+ return F.intersect(Result, Lower, Upper);
}
ProgramStateRef
@@ -2132,7 +2250,8 @@
llvm::APSInt Upper = Max - Adjustment;
++Lower;
- return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+ RangeSet SymRange = getRange(St, Sym);
+ return F.intersect(SymRange, Lower, Upper);
}
ProgramStateRef
@@ -2168,7 +2287,8 @@
llvm::APSInt Lower = ComparisonVal - Adjustment;
llvm::APSInt Upper = Max - Adjustment;
- return getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+ RangeSet SymRange = getRange(St, Sym);
+ return F.intersect(SymRange, Lower, Upper);
}
ProgramStateRef
@@ -2204,7 +2324,8 @@
llvm::APSInt Lower = Min - Adjustment;
llvm::APSInt Upper = ComparisonVal - Adjustment;
- return RS().Intersect(getBasicVals(), F, Lower, Upper);
+ RangeSet Default = RS();
+ return F.intersect(Default, Lower, Upper);
}
RangeSet RangeConstraintManager::getSymLERange(ProgramStateRef St,
@@ -2237,7 +2358,7 @@
const llvm::APSInt &To, const llvm::APSInt &Adjustment) {
RangeSet RangeLT = getSymLTRange(State, Sym, From, Adjustment);
RangeSet RangeGT = getSymGTRange(State, Sym, To, Adjustment);
- RangeSet New(RangeLT.addRange(F, RangeGT));
+ RangeSet New(F.add(RangeLT, RangeGT));
return New.isEmpty() ? nullptr : setConstraint(State, Sym, New);
}
Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
===================================================================
--- clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
+++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
@@ -16,6 +16,7 @@
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h"
+#include "llvm/Support/Allocator.h"
namespace clang {
@@ -26,16 +27,16 @@
/// to subvert RangeSet's immutability.
class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
public:
- Range(const llvm::APSInt &from, const llvm::APSInt &to)
- : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&from, &to) {
- assert(from <= to);
+ Range(const llvm::APSInt &From, const llvm::APSInt &To)
+ : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&From, &To) {
+ assert(From <= To);
}
- Range(const llvm::APSInt &point)
- : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&point, &point) {}
+ Range(const llvm::APSInt &Point)
+ : std::pair<const llvm::APSInt *, const llvm::APSInt *>(&Point, &Point) {}
- bool Includes(const llvm::APSInt &v) const {
- return *first <= v && v <= *second;
+ bool Includes(const llvm::APSInt &Point) const {
+ return From() <= Point && Point <= To();
}
const llvm::APSInt &From() const { return *first; }
const llvm::APSInt &To() const { return *second; }
@@ -47,93 +48,235 @@
ID.AddPointer(&From());
ID.AddPointer(&To());
}
-};
+ void print(raw_ostream &OS) const;
-class RangeTrait : public llvm::ImutContainerInfo<Range> {
-public:
- // When comparing if one Range is less than another, we should compare
- // the actual APSInt values instead of their pointers. This keeps the order
- // consistent (instead of comparing by pointer values) and can potentially
- // be used to speed up some of the operations in RangeSet.
- static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
- return *lhs.first < *rhs.first ||
- (!(*rhs.first < *lhs.first) && *lhs.second < *rhs.second);
- }
+ // In order to keep non-overlapping ranges sorted, we can compare only From
+ // points.
+ inline bool operator<(const Range &RHS) const { return From() < RHS.From(); }
};
-/// RangeSet contains a set of ranges. If the set is empty, then
-/// there the value of a symbol is overly constrained and there are no
-/// possible values for that symbol.
+/// @class RangeSet is a persistent set of non-overlapping ranges.
+///
+/// New RangeSet objects can be ONLY produced by RangeSet::Factory object, which
+/// also supports the most common operations performed on range sets.
+///
+/// Empty set corresponds to an overly constrained symbol meaning that there
+/// are no possible values for that symbol.
class RangeSet {
- typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
- PrimRangeSet ranges; // no need to make const, since it is an
- // ImmutableSet - this allows default operator=
- // to work.
public:
- typedef PrimRangeSet::Factory Factory;
- typedef PrimRangeSet::iterator iterator;
-
- RangeSet(PrimRangeSet RS) : ranges(RS) {}
-
- /// Create a new set with all ranges of this set and RS.
- /// Possible intersections are not checked here.
- RangeSet addRange(Factory &F, const RangeSet &RS) {
- PrimRangeSet Ranges(RS.ranges);
- for (const auto &range : ranges)
- Ranges = F.add(Ranges, range);
- return RangeSet(Ranges);
- }
-
- iterator begin() const { return ranges.begin(); }
- iterator end() const { return ranges.end(); }
+ class Factory;
- bool isEmpty() const { return ranges.isEmpty(); }
+private:
+ // We use llvm::SmallVector as the underlying container for the following
+ // reasons:
+ //
+ // * Range sets are usually very simple, 1 or 2 ranges.
+ // That's why llvm::ImmutableSet is not perfect.
+ //
+ // * Ranges in sets are NOT overlapping, so it is natural to keep them
+ // sorted for efficient operations and queries. For this reason,
+ // llvm::SmallSet doesn't fit the requirements, it is not sorted when it
+ // is a vector.
+ //
+ // * Range set operations usually a bit harder than add/remove a range.
+ // Complex operations might do many of those for just one range set.
+ // This makes llvm::ImmutableSet inefficient for our purposes as we want
+ // to make these operations BOTH immutable AND efficient.
+ //
+ // * Iteration over ranges is widespread and a more cache-friendly
+ // structure is preferred.
+ using ImplType = llvm::SmallVector<Range, 4>;
+
+ struct ContainerType : public ImplType, public llvm::FoldingSetNode {
+ void Profile(llvm::FoldingSetNodeID &ID) const {
+ for (const Range &It : *this) {
+ It.Profile(ID);
+ }
+ }
+ };
+ // This is a non-owning pointer to an actual container.
+ // The memory is fully managed by the factory and is alive as long as the
+ // factory itself is alive.
+ // It is a pointer as opposed to a reference, so we can easily reassign
+ // RangeSet objects.
+ using UnderlyingType = const ContainerType *;
+ UnderlyingType Impl;
- /// Construct a new RangeSet representing '{ [from, to] }'.
- RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
- : ranges(F.add(F.getEmptySet(), Range(from, to))) {}
+public:
+ using iterator = ImplType::const_iterator;
+
+ iterator begin() const { return Impl->begin(); }
+ iterator end() const { return Impl->end(); }
+ size_t size() const { return Impl->size(); }
+
+ bool isEmpty() const { return Impl->empty(); }
+
+ class Factory {
+ public:
+ Factory(BasicValueFactory &BV) : ValueFactory(BV) {}
+
+ /// Create a new set with all ranges from both LHS and RHS.
+ /// Possible intersections are not checked here.
+ ///
+ /// Complexity: O(N + M)
+ /// where N = size(LHS), M = size(RHS)
+ RangeSet add(RangeSet LHS, RangeSet RHS);
+ /// Create a new set with all ranges from the original set plus the new one.
+ /// Possible intersections are not checked here.
+ ///
+ /// Complexity: O(N)
+ /// where N = size(Original)
+ RangeSet add(RangeSet Original, Range Element);
+
+ RangeSet getEmptySet() { return &EmptySet; }
+
+ /// Create a new set with just one range.
+ /// @{
+ RangeSet getSet(Range Origin);
+ RangeSet getSet(const llvm::APSInt &From, const llvm::APSInt &To) {
+ return getSet(Range(From, To));
+ }
+ RangeSet getSet(const llvm::APSInt &Origin) {
+ return getSet(Origin, Origin);
+ }
+ /// @}
+
+ /// Intersect the given range sets.
+ ///
+ /// Complexity: O(N + M)
+ /// where N = size(LHS), M = size(RHS)
+ RangeSet intersect(RangeSet LHS, RangeSet RHS);
+ /// Intersect the given set with the closed range [Lower, Upper].
+ ///
+ /// Unlike the Range type, this range uses modular arithmetic, corresponding
+ /// to the common treatment of C integer overflow. Thus, if the Lower bound
+ /// is greater than the Upper bound, the range is taken to wrap around. This
+ /// is equivalent to taking the intersection with the two ranges [Min,
+ /// Upper] and [Lower, Max], or, alternatively, /removing/ all integers
+ /// between Upper and Lower.
+ ///
+ /// Complexity: O(N)
+ /// where N = size(What)
+ RangeSet intersect(RangeSet What, llvm::APSInt Lower, llvm::APSInt Upper);
+ /// Intersect the given range with the given point.
+ ///
+ /// The result can be either an empty set or a set containing the given
+ /// point depending on whether the point is in the range set.
+ ///
+ /// Complexity: O(logN)
+ /// where N = size(What)
+ RangeSet intersect(RangeSet What, llvm::APSInt Point);
+
+ /// Delete the given point from the range set.
+ ///
+ /// Complexity: O(N)
+ /// where N = size(From)
+ RangeSet deletePoint(const llvm::APSInt &Point, RangeSet From);
+ /// Negate the given range set.
+ ///
+ /// 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].
+ ///
+ /// Complexity: O(N)
+ /// where N = size(What)
+ RangeSet negate(RangeSet What);
+
+ private:
+ RangeSet makePersistent(ContainerType &&From);
+ ContainerType *construct(ContainerType &&From);
+ void destroy(const ContainerType *);
+
+ RangeSet intersect(const RangeSet::ContainerType &LHS,
+ const RangeSet::ContainerType &RHS);
+
+ // Many operations inlcude producing new APSInt values and that's why
+ // we need this factory.
+ BasicValueFactory &ValueFactory;
+ // Allocator for all the created containers.
+ // Containers might own their own memory and that's why it is specific
+ // for the type, so it calls containter destructors upon deletion.
+ llvm::SpecificBumpPtrAllocator<ContainerType> Arena;
+ // Usually we deal with the same ranges and range sets over and over.
+ // Here we track all created containers and try not to repeat ourselves.
+ llvm::FoldingSet<ContainerType> Cache;
+ static ContainerType EmptySet;
+
+ friend class RangeSet;
+ };
+
+ RangeSet(const RangeSet &) = default;
+ RangeSet &operator=(const RangeSet &) = default;
+ RangeSet(RangeSet &&) = default;
+ RangeSet &operator=(RangeSet &&) = default;
+
+ /// Construct a new RangeSet representing '{ [From, To] }'.
+ RangeSet(Factory &F, const llvm::APSInt &From, const llvm::APSInt &To)
+ : RangeSet(F.getSet(From, To)) {}
/// Construct a new RangeSet representing the given point as a range.
- RangeSet(Factory &F, const llvm::APSInt &point) : RangeSet(F, point, point) {}
+ RangeSet(Factory &F, const llvm::APSInt &Point) : RangeSet(F.getSet(Point)) {}
+
+ static void Profile(llvm::FoldingSetNodeID &ID, const RangeSet &RS) {
+ ID.AddPointer(RS.Impl);
+ }
/// Profile - Generates a hash profile of this RangeSet for use
/// by FoldingSet.
- void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
+ void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, *this); }
/// getConcreteValue - If a symbol is contrained to equal a specific integer
/// constant then this method returns that value. Otherwise, it returns
/// NULL.
const llvm::APSInt *getConcreteValue() const {
- return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : nullptr;
+ return Impl->size() == 1 ? begin()->getConcreteValue() : nullptr;
}
/// Get a minimal value covered by the ranges in the set
+ ///
+ /// Complexity: O(1)
const llvm::APSInt &getMinValue() const;
/// Get a maximal value covered by the ranges in the set
+ ///
+ /// Complexity: O(1)
const llvm::APSInt &getMaxValue() const;
-private:
- void IntersectInRange(BasicValueFactory &BV, Factory &F,
- const llvm::APSInt &Lower, const llvm::APSInt &Upper,
- PrimRangeSet &newRanges, PrimRangeSet::iterator &i,
- PrimRangeSet::iterator &e) const;
+ /// Test whether the given point is contained in any of the ranges.
+ ///
+ /// Complexity: O(logN)
+ /// where N = size(this)
+ bool contains(llvm::APSInt Point) const { return containsImpl(Point); }
- bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
+ void print(raw_ostream &os) const;
-public:
- RangeSet Intersect(BasicValueFactory &BV, Factory &F, llvm::APSInt Lower,
- llvm::APSInt Upper) const;
- RangeSet Intersect(BasicValueFactory &BV, Factory &F,
- const RangeSet &Other) const;
- RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
- RangeSet Delete(BasicValueFactory &BV, Factory &F,
- const llvm::APSInt &Point) const;
+ bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; }
- void print(raw_ostream &os) const;
+private:
+ RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {}
+ RangeSet(UnderlyingType Ptr) : Impl(Ptr) {}
- bool operator==(const RangeSet &other) const {
- return ranges == other.ranges;
- }
+ bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
+ bool pin(llvm::APSInt &Point) const;
+ bool containsImpl(llvm::APSInt &Point) const;
+
+ friend class Factory;
};
using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
