[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 change

[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

show more ...

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/412

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

show more ...

[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 Interval

[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

show more ...

[ADT] CoalescingBitVector: Avoid initial heap allocation, NFC

Avoid making a heap allocation when constructing a CoalescingBitVector.

This reduces time spent in LiveDebugValues when compiling sqlit

[ADT] CoalescingBitVector: Avoid initial heap allocation, NFC

Avoid making a heap allocation when constructing a CoalescingBitVector.

This reduces time spent in LiveDebugValues when compiling sqlite3 by
700ms (0.5% of the total User Time).

rdar://60046261

Differential Revision: https://reviews.llvm.org/D76465

show more ...

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/1338

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) {
^

show more ...

unittest: Disable checks to work around compiler errors

On some bots, using gtest asserts to compare iterators does not compile,
and I'm not sure why (this certainly compiles with clang). Disable th

unittest: Disable checks to work around compiler errors

On some bots, using gtest asserts to compare iterators does not compile,
and I'm not sure why (this certainly compiles with clang). Disable the
checks for now :/.

```
C:\buildbot\as-builder-3\llvm-clang-x86_64-win-fast\llvm-project\llvm\utils\unittest\googletest\include\gtest/gtest-printers.h(377): error C2039: 'begin': is not a member of 'llvm::CoalescingBitVector<unsigned int,16>::const_iterator'
C:\buildbot\as-builder-3\llvm-clang-x86_64-win-fast\llvm-project\llvm\include\llvm/ADT/CoalescingBitVector.h(243): note: see declaration of 'llvm::CoalescingBitVector<unsigned int,16>::const_iterator'
C:\buildbot\as-builder-3\llvm-clang-x86_64-win-fast\llvm-project\llvm\utils\unittest\googletest\include\gtest/gtest-printers.h(478): note: see reference to function template instantiation 'void testing::internal::DefaultPrintTo<T>(testing::internal::IsContainer,testing::internal::false_type,const C &,std::ostream *)' being compiled
with
[
T=T1,
C=T1
]
```

http://lab.llvm.org:8011/builders/llvm-clang-x86_64-win-fast/builds/12006/steps/test-check-llvm-unit/logs/stdio
http://lab.llvm.org:8011/builders/clang-cmake-x86_64-sde-avx512-linux/builds/34521/steps/ninja%20check%201/logs/stdio

show more ...

[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.

--

[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

show more ...