RPCS3/llvm-mirror
1
0
Fork 0
mirror of https://github.com/RPCS3/llvm-mirror.git synced 2024-11-22 02:33:06 +01:00
Code Issues Projects Releases Wiki Activity
master
llvm-mirror/unittests/ADT/CoalescingBitVectorTest.cpp

562 lines
18 KiB
C++
Raw Permalink Normal View History

[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
//=== CoalescingBitVectorTest.cpp - CoalescingBitVector unit tests --------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "llvm/ADT/CoalescingBitVector.h"
#include "gtest/gtest.h"
using namespace llvm;
namespace {
using UBitVec = CoalescingBitVector<unsigned>;
using U64BitVec = CoalescingBitVector<uint64_t>;
bool elementsMatch(const UBitVec &BV, std::initializer_list<unsigned> List) {
if (!std::equal(BV.begin(), BV.end(), List.begin(), List.end())) {
UBitVec::Allocator Alloc;
UBitVec Expected(Alloc);
Expected.set(List);
dbgs() << "elementsMatch:\n"
<< " Expected: ";
Expected.print(dbgs());
dbgs() << " Got: ";
BV.print(dbgs());
return false;
}
return true;
}
[LiveDebugValues] Speed up removeEntryValue, NFC Summary: Instead of iterating over all VarLoc IDs in removeEntryValue(), just iterate over the interval reserved for entry value VarLocs. This changes the iteration order, hence the test update -- otherwise this is NFC. This appears to give an ~8.5x wall time speed-up for LiveDebugValues when compiling sqlite3.c 3.30.1 with a Release clang (on my machine): ``` ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name --- Before: 2.5402 ( 18.8%) 0.0050 ( 0.4%) 2.5452 ( 17.3%) 2.5452 ( 17.3%) Live DEBUG_VALUE analysis After: 0.2364 ( 2.1%) 0.0034 ( 0.3%) 0.2399 ( 2.0%) 0.2398 ( 2.0%) Live DEBUG_VALUE analysis ``` The change in removeEntryValue() is the only one that appears to affect wall time, but for consistency (and to resolve a pending TODO), I made the analogous changes for iterating over SpillLocKind VarLocs. Reviewers: nikic, aprantl, jmorse, djtodoro Subscribers: hiraditya, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D80684
2020-05-28 03:19:54 +02:00
bool rangesMatch(iterator_range<UBitVec::const_iterator> R,
std::initializer_list<unsigned> List) {
return std::equal(R.begin(), R.end(), List.begin(), List.end());
}
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
TEST(CoalescingBitVectorTest, Set) {
UBitVec::Allocator Alloc;
UBitVec BV1(Alloc);
UBitVec BV2(Alloc);
BV1.set(0);
EXPECT_TRUE(BV1.test(0));
EXPECT_FALSE(BV1.test(1));
BV2.set(BV1);
EXPECT_TRUE(BV2.test(0));
}
TEST(CoalescingBitVectorTest, Count) {
UBitVec::Allocator Alloc;
UBitVec BV(Alloc);
EXPECT_EQ(BV.count(), 0u);
BV.set(0);
EXPECT_EQ(BV.count(), 1u);
BV.set({11, 12, 13, 14, 15});
EXPECT_EQ(BV.count(), 6u);
}
TEST(CoalescingBitVectorTest, ClearAndEmpty) {
UBitVec::Allocator Alloc;
UBitVec BV(Alloc);
EXPECT_TRUE(BV.empty());
BV.set(1);
EXPECT_FALSE(BV.empty());
BV.clear();
EXPECT_TRUE(BV.empty());
}
TEST(CoalescingBitVector, Copy) {
UBitVec::Allocator Alloc;
UBitVec BV1(Alloc);
BV1.set(0);
UBitVec BV2 = BV1;
EXPECT_TRUE(elementsMatch(BV1, {0}));
EXPECT_TRUE(elementsMatch(BV2, {0}));
BV2.set(5);
BV2 = BV1;
EXPECT_TRUE(elementsMatch(BV1, {0}));
EXPECT_TRUE(elementsMatch(BV2, {0}));
}
TEST(CoalescingBitVectorTest, Iterators) {
UBitVec::Allocator Alloc;
UBitVec BV(Alloc);
BV.set({0, 1, 2});
auto It = BV.begin();
unittest: Convert EXPECT_EQ iterator checks to use EXPECT_TRUE instead Hopefully fixes compile errors on some bots, like: http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/13383/steps/ninja%20check%201/logs/stdio /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/unittests/ADT/CoalescingBitVectorTest.cpp:452:3: required from here /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:377:56: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘begin’ for (typename C::const_iterator it = container.begin(); ^ /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:378:11: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘end’ it != container.end(); ++it, ++count) { ^
2020-02-27 23:19:42 +01:00
EXPECT_TRUE(It == BV.begin());
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
EXPECT_EQ(*It, 0u);
++It;
EXPECT_EQ(*It, 1u);
++It;
EXPECT_EQ(*It, 2u);
++It;
unittest: Convert EXPECT_EQ iterator checks to use EXPECT_TRUE instead Hopefully fixes compile errors on some bots, like: http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/13383/steps/ninja%20check%201/logs/stdio /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/unittests/ADT/CoalescingBitVectorTest.cpp:452:3: required from here /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:377:56: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘begin’ for (typename C::const_iterator it = container.begin(); ^ /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:378:11: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘end’ it != container.end(); ++it, ++count) { ^
2020-02-27 23:19:42 +01:00
EXPECT_TRUE(It == BV.end());
EXPECT_TRUE(BV.end() == BV.end());
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
It = BV.begin();
unittest: Convert EXPECT_EQ iterator checks to use EXPECT_TRUE instead Hopefully fixes compile errors on some bots, like: http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/13383/steps/ninja%20check%201/logs/stdio /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/unittests/ADT/CoalescingBitVectorTest.cpp:452:3: required from here /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:377:56: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘begin’ for (typename C::const_iterator it = container.begin(); ^ /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:378:11: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘end’ it != container.end(); ++it, ++count) { ^
2020-02-27 23:19:42 +01:00
EXPECT_TRUE(It == BV.begin());
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
auto ItCopy = It++;
unittest: Convert EXPECT_EQ iterator checks to use EXPECT_TRUE instead Hopefully fixes compile errors on some bots, like: http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/13383/steps/ninja%20check%201/logs/stdio /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/unittests/ADT/CoalescingBitVectorTest.cpp:452:3: required from here /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:377:56: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘begin’ for (typename C::const_iterator it = container.begin(); ^ /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:378:11: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘end’ it != container.end(); ++it, ++count) { ^
2020-02-27 23:19:42 +01:00
EXPECT_TRUE(ItCopy == BV.begin());
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
EXPECT_EQ(*ItCopy, 0u);
EXPECT_EQ(*It, 1u);
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2}));
BV.set({4, 5, 6});
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6}));
BV.set(3);
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6}));
BV.set(10);
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6, 10}));
// Should be able to reset unset bits.
BV.reset(3);
BV.reset(3);
BV.reset(20000);
BV.set({1000, 1001, 1002});
EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6, 10, 1000, 1001, 1002}));
auto It1 = BV.begin();
unittest: Convert EXPECT_EQ iterator checks to use EXPECT_TRUE instead Hopefully fixes compile errors on some bots, like: http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/13383/steps/ninja%20check%201/logs/stdio /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/unittests/ADT/CoalescingBitVectorTest.cpp:452:3: required from here /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:377:56: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘begin’ for (typename C::const_iterator it = container.begin(); ^ /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:378:11: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘end’ it != container.end(); ++it, ++count) { ^
2020-02-27 23:19:42 +01:00
EXPECT_TRUE(It1 == BV.begin());
EXPECT_TRUE(++It1 == ++BV.begin());
EXPECT_TRUE(It1 != BV.begin());
EXPECT_TRUE(It1 != BV.end());
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
}
TEST(CoalescingBitVectorTest, Reset) {
UBitVec::Allocator Alloc;
UBitVec BV(Alloc);
BV.set(0);
EXPECT_TRUE(BV.test(0));
BV.reset(0);
EXPECT_FALSE(BV.test(0));
BV.clear();
BV.set({1, 2, 3});
BV.reset(1);
EXPECT_TRUE(elementsMatch(BV, {2, 3}));
BV.clear();
BV.set({1, 2, 3});
BV.reset(2);
EXPECT_TRUE(elementsMatch(BV, {1, 3}));
BV.clear();
BV.set({1, 2, 3});
BV.reset(3);
EXPECT_TRUE(elementsMatch(BV, {1, 2}));
}
TEST(CoalescingBitVectorTest, Comparison) {
UBitVec::Allocator Alloc;
UBitVec BV1(Alloc);
UBitVec BV2(Alloc);
// Single interval.
BV1.set({1, 2, 3});
BV2.set({1, 2, 3});
EXPECT_EQ(BV1, BV2);
EXPECT_FALSE(BV1 != BV2);
// Different number of intervals.
BV1.clear();
BV2.clear();
BV1.set({1, 2, 3});
EXPECT_NE(BV1, BV2);
// Multiple intervals.
BV1.clear();
BV2.clear();
BV1.set({1, 2, 11, 12});
BV2.set({1, 2, 11, 12});
EXPECT_EQ(BV1, BV2);
BV2.reset(1);
EXPECT_NE(BV1, BV2);
BV2.set(1);
BV2.reset(11);
EXPECT_NE(BV1, BV2);
}
// A simple implementation of set union, used to double-check the human
// "expected" answer.
unittest: Work around build failure on MSVC builders MSVC insists on using the deleted move constructor instead of the copy constructor: http://lab.llvm.org:8011/builders/lld-x86_64-win7/builds/41203 C:\ps4-buildslave2\lld-x86_64-win7\llvm-project\llvm\unittests\ADT\CoalescingBitVectorTest.cpp(193): error C2280: 'llvm::CoalescingBitVector<unsigned int,16>::CoalescingBitVector(llvm::CoalescingBitVector<unsigned int,16> &&)': attempting to reference a deleted function
2020-03-20 20:37:58 +01:00
void simpleUnion(UBitVec &Union, const UBitVec &LHS,
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
const UBitVec &RHS) {
for (unsigned Bit : LHS)
Union.test_and_set(Bit);
for (unsigned Bit : RHS)
Union.test_and_set(Bit);
}
TEST(CoalescingBitVectorTest, Union) {
UBitVec::Allocator Alloc;
// Check that after doing LHS |= RHS, LHS == Expected.
auto unionIs = [&](std::initializer_list<unsigned> LHS,
std::initializer_list<unsigned> RHS,
std::initializer_list<unsigned> Expected) {
UBitVec BV1(Alloc);
BV1.set(LHS);
UBitVec BV2(Alloc);
BV2.set(RHS);
unittest: Work around build failure on MSVC builders MSVC insists on using the deleted move constructor instead of the copy constructor: http://lab.llvm.org:8011/builders/lld-x86_64-win7/builds/41203 C:\ps4-buildslave2\lld-x86_64-win7\llvm-project\llvm\unittests\ADT\CoalescingBitVectorTest.cpp(193): error C2280: 'llvm::CoalescingBitVector<unsigned int,16>::CoalescingBitVector(llvm::CoalescingBitVector<unsigned int,16> &&)': attempting to reference a deleted function
2020-03-20 20:37:58 +01:00
UBitVec DoubleCheckedExpected(Alloc);
simpleUnion(DoubleCheckedExpected, BV1, BV2);
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
BV1 |= BV2;
ASSERT_TRUE(elementsMatch(BV1, Expected));
};
// Check that "LHS |= RHS" and "RHS |= LHS" both produce the expected result.
auto testUnionSymmetrically = [&](std::initializer_list<unsigned> LHS,
std::initializer_list<unsigned> RHS,
std::initializer_list<unsigned> Expected) {
unionIs(LHS, RHS, Expected);
unionIs(RHS, LHS, Expected);
};
// Empty LHS.
testUnionSymmetrically({}, {1, 2, 3}, {1, 2, 3});
// Empty RHS.
testUnionSymmetrically({1, 2, 3}, {}, {1, 2, 3});
// Full overlap.
testUnionSymmetrically({1}, {1}, {1});
testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12});
// Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
// it. Repeat this swapping LHS and RHS.
testUnionSymmetrically({2, 3, 4}, {1, 2, 3}, {1, 2, 3, 4});
testUnionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
testUnionSymmetrically({2, 3, 4}, {3, 4, 5}, {2, 3, 4, 5});
testUnionSymmetrically({1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4});
testUnionSymmetrically({3, 4, 5}, {2, 3, 4}, {2, 3, 4, 5});
// Multiple overlaps, but at least one of the overlaps forces us to split an
// interval (and possibly both do). For ease of understanding, fix LHS to be
// {1, 2, 11, 12}, but vary RHS.
testUnionSymmetrically({1, 2, 11, 12}, {1}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {2}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {11}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {12}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {2, 11}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {2, 12}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {0, 1, 2, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {1, 2, 3, 11, 12});
testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 2, 11, 12, 13});
testUnionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 2, 10, 11, 12});
// Partial overlap, but the existing interval covers future overlaps.
testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
{1, 2, 3, 4, 5, 6, 7, 8});
testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 7, 8, 9},
{1, 2, 3, 4, 5, 6, 7, 8, 9});
// More partial overlaps.
testUnionSymmetrically({1, 2, 3, 4, 5}, {0, 1, 2, 4, 5, 6},
{0, 1, 2, 3, 4, 5, 6});
testUnionSymmetrically({2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4});
testUnionSymmetrically({3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4});
testUnionSymmetrically({1, 2}, {1, 2, 3, 4}, {1, 2, 3, 4});
testUnionSymmetrically({0, 1}, {1, 2, 3, 4}, {0, 1, 2, 3, 4});
// Merge non-overlapping.
testUnionSymmetrically({0, 1}, {2, 3}, {0, 1, 2, 3});
testUnionSymmetrically({0, 3}, {1, 2}, {0, 1, 2, 3});
}
// A simple implementation of set intersection, used to double-check the
// human "expected" answer.
unittest: Work around build failure on MSVC builders MSVC insists on using the deleted move constructor instead of the copy constructor: http://lab.llvm.org:8011/builders/lld-x86_64-win7/builds/41203 C:\ps4-buildslave2\lld-x86_64-win7\llvm-project\llvm\unittests\ADT\CoalescingBitVectorTest.cpp(193): error C2280: 'llvm::CoalescingBitVector<unsigned int,16>::CoalescingBitVector(llvm::CoalescingBitVector<unsigned int,16> &&)': attempting to reference a deleted function
2020-03-20 20:37:58 +01:00
void simpleIntersection(UBitVec &Intersection, const UBitVec &LHS,
const UBitVec &RHS) {
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
for (unsigned Bit : LHS)
if (RHS.test(Bit))
Intersection.set(Bit);
}
TEST(CoalescingBitVectorTest, Intersection) {
UBitVec::Allocator Alloc;
// Check that after doing LHS &= RHS, LHS == Expected.
auto intersectionIs = [&](std::initializer_list<unsigned> LHS,
std::initializer_list<unsigned> RHS,
std::initializer_list<unsigned> Expected) {
UBitVec BV1(Alloc);
BV1.set(LHS);
UBitVec BV2(Alloc);
BV2.set(RHS);
unittest: Work around build failure on MSVC builders MSVC insists on using the deleted move constructor instead of the copy constructor: http://lab.llvm.org:8011/builders/lld-x86_64-win7/builds/41203 C:\ps4-buildslave2\lld-x86_64-win7\llvm-project\llvm\unittests\ADT\CoalescingBitVectorTest.cpp(193): error C2280: 'llvm::CoalescingBitVector<unsigned int,16>::CoalescingBitVector(llvm::CoalescingBitVector<unsigned int,16> &&)': attempting to reference a deleted function
2020-03-20 20:37:58 +01:00
UBitVec DoubleCheckedExpected(Alloc);
simpleIntersection(DoubleCheckedExpected, BV1, BV2);
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
BV1 &= BV2;
ASSERT_TRUE(elementsMatch(BV1, Expected));
};
// Check that "LHS &= RHS" and "RHS &= LHS" both produce the expected result.
auto testIntersectionSymmetrically = [&](std::initializer_list<unsigned> LHS,
std::initializer_list<unsigned> RHS,
std::initializer_list<unsigned> Expected) {
intersectionIs(LHS, RHS, Expected);
intersectionIs(RHS, LHS, Expected);
};
// Empty case, one-element case.
testIntersectionSymmetrically({}, {}, {});
testIntersectionSymmetrically({1}, {1}, {1});
testIntersectionSymmetrically({1}, {2}, {});
// Exact overlaps cases: single overlap and multiple overlaps.
testIntersectionSymmetrically({1, 2}, {1, 2}, {1, 2});
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12});
// Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
// it.
testIntersectionSymmetrically({2, 3, 4}, {1, 2, 3}, {2, 3});
testIntersectionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
testIntersectionSymmetrically({2, 3, 4}, {3, 4, 5}, {3, 4});
// No overlap, but we have multiple intervals.
testIntersectionSymmetrically({1, 2, 11, 12}, {3, 4, 13, 14}, {});
// Multiple overlaps, but at least one of the overlaps forces us to split an
// interval (and possibly both do). For ease of understanding, fix LHS to be
// {1, 2, 11, 12}, but vary RHS.
testIntersectionSymmetrically({1, 2, 11, 12}, {1}, {1});
testIntersectionSymmetrically({1, 2, 11, 12}, {2}, {2});
testIntersectionSymmetrically({1, 2, 11, 12}, {11}, {11});
testIntersectionSymmetrically({1, 2, 11, 12}, {12}, {12});
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 11});
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 12});
testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11}, {2, 11});
testIntersectionSymmetrically({1, 2, 11, 12}, {2, 12}, {2, 12});
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11});
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 12});
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 11, 12});
testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {2, 11, 12});
testIntersectionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {11, 12});
testIntersectionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {11, 12});
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 11});
testIntersectionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 11});
// Partial overlap, but the existing interval covers future overlaps.
testIntersectionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
{2, 3, 4, 6, 7});
}
// A simple implementation of set intersection-with-complement, used to
// double-check the human "expected" answer.
unittest: Work around build failure on MSVC builders MSVC insists on using the deleted move constructor instead of the copy constructor: http://lab.llvm.org:8011/builders/lld-x86_64-win7/builds/41203 C:\ps4-buildslave2\lld-x86_64-win7\llvm-project\llvm\unittests\ADT\CoalescingBitVectorTest.cpp(193): error C2280: 'llvm::CoalescingBitVector<unsigned int,16>::CoalescingBitVector(llvm::CoalescingBitVector<unsigned int,16> &&)': attempting to reference a deleted function
2020-03-20 20:37:58 +01:00
void simpleIntersectionWithComplement(UBitVec &Intersection, const UBitVec &LHS,
const UBitVec &RHS) {
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
for (unsigned Bit : LHS)
if (!RHS.test(Bit))
Intersection.set(Bit);
}
TEST(CoalescingBitVectorTest, IntersectWithComplement) {
UBitVec::Allocator Alloc;
// Check that after doing LHS.intersectWithComplement(RHS), LHS == Expected.
auto intersectionWithComplementIs =
[&](std::initializer_list<unsigned> LHS,
std::initializer_list<unsigned> RHS,
std::initializer_list<unsigned> Expected) {
UBitVec BV1(Alloc);
BV1.set(LHS);
UBitVec BV2(Alloc);
BV2.set(RHS);
unittest: Work around build failure on MSVC builders MSVC insists on using the deleted move constructor instead of the copy constructor: http://lab.llvm.org:8011/builders/lld-x86_64-win7/builds/41203 C:\ps4-buildslave2\lld-x86_64-win7\llvm-project\llvm\unittests\ADT\CoalescingBitVectorTest.cpp(193): error C2280: 'llvm::CoalescingBitVector<unsigned int,16>::CoalescingBitVector(llvm::CoalescingBitVector<unsigned int,16> &&)': attempting to reference a deleted function
2020-03-20 20:37:58 +01:00
UBitVec DoubleCheckedExpected(Alloc);
simpleIntersectionWithComplement(DoubleCheckedExpected, BV1, BV2);
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
BV1.intersectWithComplement(BV2);
ASSERT_TRUE(elementsMatch(BV1, Expected));
};
// Empty case, one-element case.
intersectionWithComplementIs({}, {}, {});
intersectionWithComplementIs({1}, {1}, {});
intersectionWithComplementIs({1}, {2}, {1});
// Exact overlaps cases: single overlap and multiple overlaps.
intersectionWithComplementIs({1, 2}, {1, 2}, {});
intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11, 12}, {});
// Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
// it. Repeat this swapping LHS and RHS.
intersectionWithComplementIs({2, 3, 4}, {1, 2, 3}, {4});
intersectionWithComplementIs({2, 3, 4}, {2, 3, 4}, {});
intersectionWithComplementIs({2, 3, 4}, {3, 4, 5}, {2});
intersectionWithComplementIs({1, 2, 3}, {2, 3, 4}, {1});
intersectionWithComplementIs({3, 4, 5}, {2, 3, 4}, {5});
// No overlap, but we have multiple intervals.
intersectionWithComplementIs({1, 2, 11, 12}, {3, 4, 13, 14}, {1, 2, 11, 12});
// Multiple overlaps. For ease of understanding, fix LHS to be
// {1, 2, 11, 12}, but vary RHS.
intersectionWithComplementIs({1, 2, 11, 12}, {1}, {2, 11, 12});
intersectionWithComplementIs({1, 2, 11, 12}, {2}, {1, 11, 12});
intersectionWithComplementIs({1, 2, 11, 12}, {11}, {1, 2, 12});
intersectionWithComplementIs({1, 2, 11, 12}, {12}, {1, 2, 11});
intersectionWithComplementIs({1, 2, 11, 12}, {1, 11}, {2, 12});
intersectionWithComplementIs({1, 2, 11, 12}, {1, 12}, {2, 11});
intersectionWithComplementIs({1, 2, 11, 12}, {2, 11}, {1, 12});
intersectionWithComplementIs({1, 2, 11, 12}, {2, 12}, {1, 11});
intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11}, {12});
intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 12}, {11});
intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 12}, {2});
intersectionWithComplementIs({1, 2, 11, 12}, {2, 11, 12}, {1});
intersectionWithComplementIs({1, 2, 11, 12}, {0, 11, 12}, {1, 2});
intersectionWithComplementIs({1, 2, 11, 12}, {3, 11, 12}, {1, 2});
intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 13}, {2, 12});
intersectionWithComplementIs({1, 2, 11, 12}, {1, 10, 11}, {2, 12});
// Partial overlap, but the existing interval covers future overlaps.
intersectionWithComplementIs({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
{1, 5, 8});
}
TEST(CoalescingBitVectorTest, FindLowerBound) {
U64BitVec::Allocator Alloc;
U64BitVec BV(Alloc);
uint64_t BigNum1 = uint64_t(1) << 32;
uint64_t BigNum2 = (uint64_t(1) << 33) + 1;
unittest: Convert EXPECT_EQ iterator checks to use EXPECT_TRUE instead Hopefully fixes compile errors on some bots, like: http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/13383/steps/ninja%20check%201/logs/stdio /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/unittests/ADT/CoalescingBitVectorTest.cpp:452:3: required from here /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:377:56: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘begin’ for (typename C::const_iterator it = container.begin(); ^ /home/ssglocal/clang-cmake-x86_64-avx2-linux/clang-cmake-x86_64-avx2-linux/llvm/llvm/utils/unittest/googletest/include/gtest/gtest-printers.h:378:11: error: ‘const class llvm::CoalescingBitVector<long unsigned int>::const_iterator’ has no member named ‘end’ it != container.end(); ++it, ++count) { ^
2020-02-27 23:19:42 +01:00
EXPECT_TRUE(BV.find(BigNum1) == BV.end());
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
BV.set(BigNum1);
auto Find1 = BV.find(BigNum1);
EXPECT_EQ(*Find1, BigNum1);
BV.set(BigNum2);
auto Find2 = BV.find(BigNum1);
EXPECT_EQ(*Find2, BigNum1);
auto Find3 = BV.find(BigNum2);
EXPECT_EQ(*Find3, BigNum2);
BV.reset(BigNum1);
auto Find4 = BV.find(BigNum1);
EXPECT_EQ(*Find4, BigNum2);
BV.clear();
BV.set({1, 2, 3});
EXPECT_EQ(*BV.find(2), 2u);
EXPECT_EQ(*BV.find(3), 3u);
}
[ADT] CoalescingBitVector: Add advanceToLowerBound iterator operation advanceToLowerBound moves an iterator to the first bit set at, or after, the given index. This can be faster than doing IntervalMap::find. rdar://60046261 Differential Revision: https://reviews.llvm.org/D76466
2020-03-20 00:40:58 +01:00
TEST(CoalescingBitVectorTest, AdvanceToLowerBound) {
U64BitVec::Allocator Alloc;
U64BitVec BV(Alloc);
uint64_t BigNum1 = uint64_t(1) << 32;
uint64_t BigNum2 = (uint64_t(1) << 33) + 1;
auto advFromBegin = [&](uint64_t To) -> U64BitVec::const_iterator {
auto It = BV.begin();
It.advanceToLowerBound(To);
return It;
};
EXPECT_TRUE(advFromBegin(BigNum1) == BV.end());
BV.set(BigNum1);
auto Find1 = advFromBegin(BigNum1);
EXPECT_EQ(*Find1, BigNum1);
BV.set(BigNum2);
auto Find2 = advFromBegin(BigNum1);
EXPECT_EQ(*Find2, BigNum1);
auto Find3 = advFromBegin(BigNum2);
EXPECT_EQ(*Find3, BigNum2);
BV.reset(BigNum1);
auto Find4 = advFromBegin(BigNum1);
EXPECT_EQ(*Find4, BigNum2);
BV.clear();
BV.set({1, 2, 3});
EXPECT_EQ(*advFromBegin(2), 2u);
EXPECT_EQ(*advFromBegin(3), 3u);
auto It = BV.begin();
It.advanceToLowerBound(0);
EXPECT_EQ(*It, 1u);
It.advanceToLowerBound(100);
EXPECT_TRUE(It == BV.end());
It.advanceToLowerBound(100);
EXPECT_TRUE(It == BV.end());
}
[LiveDebugValues] Speed up removeEntryValue, NFC Summary: Instead of iterating over all VarLoc IDs in removeEntryValue(), just iterate over the interval reserved for entry value VarLocs. This changes the iteration order, hence the test update -- otherwise this is NFC. This appears to give an ~8.5x wall time speed-up for LiveDebugValues when compiling sqlite3.c 3.30.1 with a Release clang (on my machine): ``` ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name --- Before: 2.5402 ( 18.8%) 0.0050 ( 0.4%) 2.5452 ( 17.3%) 2.5452 ( 17.3%) Live DEBUG_VALUE analysis After: 0.2364 ( 2.1%) 0.0034 ( 0.3%) 0.2399 ( 2.0%) 0.2398 ( 2.0%) Live DEBUG_VALUE analysis ``` The change in removeEntryValue() is the only one that appears to affect wall time, but for consistency (and to resolve a pending TODO), I made the analogous changes for iterating over SpillLocKind VarLocs. Reviewers: nikic, aprantl, jmorse, djtodoro Subscribers: hiraditya, dexonsmith, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D80684
2020-05-28 03:19:54 +02:00
TEST(CoalescingBitVectorTest, HalfOpenRange) {
UBitVec::Allocator Alloc;
{
UBitVec BV(Alloc);
BV.set({1, 2, 3});
EXPECT_EQ(*BV.find(0), 1U); // find(Start) > Start
EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2, 3}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 4), {1, 2, 3}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 3), {1, 2}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 3), {2}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 4), {2, 3}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(4, 5), {}));
}
{
UBitVec BV(Alloc);
BV.set({1, 2, 11, 12});
EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 15), {1, 2, 11, 12}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 13), {1, 2, 11, 12}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 12), {1, 2, 11}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 5), {1, 2}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 5), {2}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 2), {1}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(13, 14), {}));
EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 10), {2}));
}
{
UBitVec BV(Alloc);
BV.set({1});
EXPECT_EQ(*BV.find(0), 1U); // find(Start) == End
EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 1), {}));
}
{
UBitVec BV(Alloc);
BV.set({5});
EXPECT_EQ(*BV.find(3), 5U); // find(Start) > End
EXPECT_TRUE(rangesMatch(BV.half_open_range(3, 4), {}));
}
}
[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3] Add CoalescingBitVector to ADT. This is part 1 of a 3-part series to address a compile-time explosion issue in LiveDebugValues. --- CoalescingBitVector is a bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals. CoalescingBitVector efficiently represents sets which predominantly contain contiguous ranges (e.g. the VarLocSets in LiveDebugValues, which are very long sequences that look like {1, 2, 3, ...}). OTOH, CoalescingBitVector isn't good at representing sets with lots of gaps between elements. The first N coalesced intervals of set bits are stored in-place (in the initial heap allocation). Compared to SparseBitVector, CoalescingBitVector offers more predictable performance for non-sequential find() operations. This provides a crucial speedup in LiveDebugValues. Differential Revision: https://reviews.llvm.org/D74984
2020-02-18 14:41:55 +01:00
TEST(CoalescingBitVectorTest, Print) {
std::string S;
{
raw_string_ostream OS(S);
UBitVec::Allocator Alloc;
UBitVec BV(Alloc);
BV.set({1});
BV.print(OS);
BV.clear();
BV.set({1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20});
BV.print(OS);
}
EXPECT_EQ(S, "{[1]}"
"{[1][11, 20]}");
}
} // namespace
Reference in New Issue Copy Permalink