vsavchenko updated this revision to Diff 288306.
vsavchenko marked 21 inline comments as done.
vsavchenko added a comment.
Fix review remarks
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D86465/new/
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.dump(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,31 @@
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;
+
+ return std::prev(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 +267,217 @@
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()));
- if (isEmpty())
- return newRanges;
+ iterator First = LHS.begin(), Second = RHS.begin(), FirstEnd = LHS.end(),
+ SecondEnd = RHS.end();
- const llvm::APSInt sampleValue = getMinValue();
- const llvm::APSInt &MIN = BV.getMinValue(sampleValue);
- const llvm::APSInt &MAX = BV.getMaxValue(sampleValue);
+ const auto SwapIterators = [&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())
+ SwapIterators();
+
+ // 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.
+ SwapIterators();
+ }
+
+ // At this point, we have the following situation:
+ //
+ // ---- First ]-------------------->
+ // ---- Second ]--[ Second+1 ---------->
+ //
+ // We don't know the relationship between First->From and
+ // Second->From and we don't know whether Second+1 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+1
+ // because First->From <= Second->To < (Second+1)->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);
+}
+
+RangeSet RangeSet::Factory::intersect(RangeSet LHS, llvm::APSInt Point) {
+ if (LHS.containsImpl(Point))
+ return getSet(ValueFactory.getValue(Point));
+
+ return getEmptySet();
+}
+
+RangeSet RangeSet::Factory::negate(RangeSet What) {
+ if (What.isEmpty())
+ return getEmptySet();
+
+ const llvm::APSInt SampleValue = What.getMinValue();
+ const llvm::APSInt &MIN = ValueFactory.getMinValue(SampleValue);
+ const llvm::APSInt &MAX = ValueFactory.getMaxValue(SampleValue);
+
+ ContainerType Result;
+ Result.reserve(What.getMinValue() == MIN ? What.size() + 1 : What.size());
// 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 the range [From, To] is [MIN, MAX], then result is also [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,22 +485,25 @@
--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::dump(raw_ostream &OS) const {
+ OS << '[' << From().toString(10) << ", " << To().toString(10) << ']';
}
-void RangeSet::print(raw_ostream &os) const {
+void RangeSet::dump(raw_ostream &OS) const {
bool isFirst = true;
- os << "{ ";
- for (iterator i = begin(), e = end(); i != e; ++i) {
+ OS << "{ ";
+ for (const Range &R : *this) {
if (isFirst)
isFirst = false;
else
- os << ", ";
+ OS << ", ";
- os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
- << ']';
+ R.dump(OS);
}
- os << " }";
+ OS << " }";
}
REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
@@ -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);
}
@@ -2272,7 +2393,7 @@
}
Indent(Out, Space, IsDot)
<< "{ \"symbol\": \"" << ClassMember << "\", \"range\": \"";
- P.second.print(Out);
+ P.second.dump(Out);
Out << "\" }";
}
}
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 {
@@ -24,21 +25,19 @@
/// A Range represents the closed range [from, to]. The caller must
/// guarantee that from <= to. Note that Range is immutable, so as not
/// to subvert RangeSet's immutability.
-class Range : public std::pair<const llvm::APSInt *, const llvm::APSInt *> {
+class Range {
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) : Impl(&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) : Range(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; }
+ const llvm::APSInt &From() const { return *Impl.first; }
+ const llvm::APSInt &To() const { return *Impl.second; }
const llvm::APSInt *getConcreteValue() const {
return &From() == &To() ? &From() : nullptr;
}
@@ -47,93 +46,256 @@
ID.AddPointer(&From());
ID.AddPointer(&To());
}
-};
+ void dump(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.
+ bool operator<(const Range &RHS) const { return From() < RHS.From(); }
+
+ bool operator==(const Range &RHS) const { return Impl == RHS.Impl; }
+ bool operator!=(const Range &RHS) const { return !(*this == RHS); }
+
+private:
+ std::pair<const llvm::APSInt *, const llvm::APSInt *> Impl;
};
-/// 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].
+ ///
+ /// Negate is a self-inverse function, i.e. negate(negate(R)) == R.
+ ///
+ /// Complexity: O(N)
+ /// where N = size(What)
+ RangeSet negate(RangeSet What);
+
+ private:
+ /// Return a persistent version of the given container.
+ RangeSet makePersistent(ContainerType &&From);
+ /// Construct a new persistent version of the given container.
+ ContainerType *construct(ContainerType &&From);
+
+ RangeSet intersect(const ContainerType &LHS, const ContainerType &RHS);
+
+ // Many operations include 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 container 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;
+ };
+
+ RangeSet(const RangeSet &) = default;
+ RangeSet &operator=(const RangeSet &) = default;
+ RangeSet(RangeSet &&) = default;
+ RangeSet &operator=(RangeSet &&) = default;
+ ~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
+ /// Get the 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
+ /// Get the 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 by any of the ranges.
+ ///
+ /// Complexity: O(logN)
+ /// where N = size(this)
+ bool contains(llvm::APSInt Point) const { return containsImpl(Point); }
+
+ void dump(raw_ostream &OS) const;
+
+ bool operator==(const RangeSet &Other) const { return *Impl == *Other.Impl; }
+ bool operator!=(const RangeSet &Other) const { return !(*this == Other); }
+private:
+ /* implicit */ RangeSet(ContainerType *RawContainer) : Impl(RawContainer) {}
+ /* implicit */ RangeSet(UnderlyingType Ptr) : Impl(Ptr) {}
+
+ /// Pin given points to the type represented by the current range set.
+ ///
+ /// This makes parameter points to be in-out parameters.
+ /// In order to maintain consistent types across all of the ranges in the set
+ /// and to keep all the operations to compare ONLY points of the same type, we
+ /// need to pin every point before any operation.
+ ///
+ /// @Returns true if the given points can be converted to the target type
+ /// without changing the values (i.e. trivially) and false otherwise.
+ /// @{
bool pin(llvm::APSInt &Lower, llvm::APSInt &Upper) const;
+ bool pin(llvm::APSInt &Point) 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;
-
- void print(raw_ostream &os) const;
-
- bool operator==(const RangeSet &other) const {
- return ranges == other.ranges;
- }
+ // This version of this function modifies its arguments (pins it).
+ bool containsImpl(llvm::APSInt &Point) const;
+
+ friend class Factory;
};
using ConstraintMap = llvm::ImmutableMap<SymbolRef, RangeSet>;
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
