[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3]
authorVedant Kumar <vsk@apple.com>
Tue, 18 Feb 2020 13:41:55 +0000 (05:41 -0800)
committerVedant Kumar <vsk@apple.com>
Thu, 27 Feb 2020 20:39:46 +0000 (12:39 -0800)
commitb0142cd9867d720375008969fd9555cc1a17c098
tree99d7fdd0488bce239f6828304b32ae7ca7ec1df6
parent1d8fad44d301d04e2327a164b702a3fec87ee866
[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
llvm/docs/ProgrammersManual.rst
llvm/include/llvm/ADT/CoalescingBitVector.h [new file with mode: 0644]
llvm/unittests/ADT/CMakeLists.txt
llvm/unittests/ADT/CoalescingBitVectorTest.cpp [new file with mode: 0644]
llvm/unittests/ADT/IntervalMapTest.cpp