[ADT] Add CoalescingBitVector, implemented using IntervalMap [1/3]

[vsk]

Summary

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.

[vsk]

Improve comments.

[jmorse]

Nice, I can think of a few other places where this could prove useful (the register coalescing code for variable locations for starters). Some comments inline, plus

• |= / set union could do with being covered in the unittests too,
• Maybe some allocations could be avoided by using things like IntervalMap iterator setStartUnchecked and similar, but this looks good regardless.

It looks like setting already-set bits and resetting not-set bits isn't a supported operation. set indicates not to do that in the doc comment, reset even goes as far as to assert-fail if the wrong interval is looked up. These are two things that, without any additional context, I would expect something acting like a bitvector to support, it's quite a common operation on flags integers for example, and these things are supported by BitVector and SparseBitVector. Are there technical reasons for these limits, or is it to discourage CoalescingBitVector from being used in scenarios where it won't be useful, or otherwise?

I see that the implementation of operator|= follows the same code path as plain set, i.e. insert(a, b), making it possible that operator|= will set already-set bits. Is that a supported operation for operator|= but not for set, or am I missing something?

llvm/include/llvm/ADT/CoalescingBitVector.h

31

Could we get a

static_assert(std::is_integral<EltT>::value, "Key must be an integer type.");

Plus documentation of the EltT type parameter -- if I understand correctly, it's the storage type for bitvector elements, that's used as the domain type for the interval map?

56–60

I'm not familiar with LLVMs approach to allocators, but is it alright that the RHS allocator isn't carried over into this? This happens for the rvalue assignment operator below.

82

Nit, can this be a range-based loop?

232–233

Just so that I understand: advanceTo is aiming for a small set of use cases (i.e.: just find), and these assertions are to discourage anyone from using advanceTo for other purposes?

[aprantl]

Is there any kind of "These are the ADT types in LLVM and when to use them" .rst document that this should be added to?

llvm/include/llvm/ADT/CoalescingBitVector.h

30

Given that this is a bitvector, I'm kind of wondering what EltT is supposed to be (bool?) Can you add that to the class comment?

39

Ah.. it's the *Index* type? Perhaps that's a better name?

80

Is this consistent with how the other bitvector types are naming this function? Then that's fine. In DenseSet, count(Elt) is a contains(Elt) function and I don't know if we want to be consistent with that.

83

So empty ranges are disallowed? Should we assert that? Or is that too slow?

143

document \return

298

Really? If anything should this be part of the dump method instead?

[dexonsmith]

In D74984#1889605, @aprantl wrote:

Is there any kind of "These are the ADT types in LLVM and when to use them" .rst document that this should be added to?

http://llvm.org/docs/ProgrammersManual.html#picking-the-right-data-structure-for-a-task

[vsk]

Address review feedback:

• Describe the new container in the programmer's manual.
• Relax reset. This can now be used to reset an already-unset bit.
• Relax operator|=. This can now be used to perform set-union when the sets overlap.
• Add suggested tests and address various other bits of feedback.

[vsk]

llvm/include/llvm/ADT/CoalescingBitVector.h

56–60

initFromRHS does a copy into a pre-existing IntervalMap, which has already been initialized with this->Alloc. I don't think changing the Alloc would be correct, as the lifetime of RHS.Alloc may end before the lifetime of this->Alloc.

80

Yeah, SparseBitVector::count() also counts the number of set bits.

82

I don't think so, as we'd be iterating over the unused mapped values in that case.

83

There isn't a way to construct an empty interval, AFAICT.

143

It looks like the return value from intersectWithComplement is generally ignored, so I've simply removed it.

232–233

Yes, exactly. Actually the OffsetIntoMapIterator == kIteratorAtTheEndOffset check is dead code, let me remove that.

298

Yeah, while debugging this p BV.dump() would result in:

(lldb) p BV.dump()
(lldb)1]}

or something. Incidentally, the same thing happens when doing p SM.dump(SourceLoc) in clang. I filed llvm.org/PR45011.

[vsk]

@jmorse set doesn't support setting already-set bits in order to discourage this sort of usage of the container. The reason for the behavior difference from BitVector/SparseBitVector is that the cost of a second IntervalMap find() operation is relatively high (compared to, say, indexing into an array). I've tried to document this and provide alternatives, like operator|= and the newly-added test_and_set method.

[aprantl]

llvm/docs/ProgrammersManual.rst

2347 ↗

(On Diff #246287)

Even with the next paragraph I find anything but "three" confusing here given that the headline also mentions three.

llvm/include/llvm/ADT/CoalescingBitVector.h

110

Why not move the implementation of initFromRHS here and call set() everywhere where initFromRHS is called now? It feels weird to refer to an RHS in something that isn't an operator.

[vsk]

Address Adrian's comments.

[jmorse]

Looking good; I now see that IntervalMap will fire an assertion if an overlapping insert is made, I'd previously thought it would just be inefficient, this explains why CoalescingBitVector can't do it.

llvm/include/llvm/ADT/CoalescingBitVector.h

82

I wonder if I'm missing something here -- what are the unused mapped values? Isn't everything in the IntervalMap mapped to a value of zero, and so any interval that's present must correspond to an interval of set bits?

186

As this only considers one overlap at a time, won't this run into difficulties with two overlaps in one RHS interval? Such as:

RHS:       ---------------------------------
LHS:           --------         ---------

If I flip the final Union test in the unit tests:

unionIs({2, 3, 4, 6, 7}, {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8});

It coughs up an "Overlapping insert" assertion failure for me. Plus, if the second overlap is skipped, it would block any other overlap being considered, because we would never see the RHS interval it overlaps with and make progress.

(Maybe something less powerful/expressive than set union would be sufficient, if this proves painful to implement).

[aprantl]

llvm/include/llvm/ADT/CoalescingBitVector.h

101

What happens if I set an already-set bit? Will the data structure get inconsistent, less efficient, crash? Should there be an assert(!test(Index)) here?

[aprantl]

LGTM with all outstanding comments addressed.

[vsk]

Address latest round of review feedback:

• Fix a bug in operator|=, see inline comment for more discussion.
• Upgrade testing for set union and set intersection: each test case is now tested two ways ("LHS <op> RHS = Expected" and "RHS <op> LHS = Expected"), as the ops should be symmetric.

llvm/include/llvm/ADT/CoalescingBitVector.h

82

We're using an IntervalMap<IndexT, char>, so the unused mapped values are those chars. Every interval in the map does correspond to a non-empty range of set bits, yes, but writing for (auto It : *Intervals.get()) doesn't work because:

llvm/include/llvm/ADT/CoalescingBitVector.h:95:21: error: member reference base type 'char' is not a structure or union
      Bits += 1 + It.stop() - It.start();

101

IntervalMap asserts if you try to make an overlapping insert. I've added the suggested assert.

186

You're right, we'd need to consider multiple overlaps per interval borrowed from RHS. I've gone ahead and just fixed this for posterity (I introduced a getNonOverlappingParts helper to do this), but was/remain very tempted to just delete the operator|= implementation.

As LiveDebugValues doesn't require a general set union operation, it's tempting to just punt on this, but it feels like that would be cheating others who may be interested in evaluating the new container.

[aprantl]

llvm/include/llvm/ADT/CoalescingBitVector.h

186

but it feels like that would be cheating others who may be interested in evaluating the new container.

I think that when we're adding a new data structure to ADT it should be generally useful even if some of the functionality is only use in unit tests.

llvm/include/llvm/ADT/CoalescingBitVector.h

+//===- llvm/ADT/CoalescingBitVector.h - A coalescing bitvector --*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_COALESCINGBITVECTOR_H
+#define LLVM_ADT_COALESCINGBITVECTOR_H
+
+#include "llvm/ADT/IntervalMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <initializer_list>
+#include <memory>
+
+namespace llvm {
+
+/// A bitvector that, under the hood, relies on an IntervalMap to coalesce
+/// elements into intervals. Good for representing sets which predominantly
+/// contain contiguous ranges. Bad for 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.
+template <typename EltT, unsigned N = 16> class CoalescingBitVector {
+  using ThisT = CoalescingBitVector<EltT, N>;
+
+  /// An interval map for closed integer ranges. The mapped values are unused.
+  using MapT = IntervalMap<EltT, char, N>;
+
+  using UnderlyingIterator = typename MapT::const_iterator;
+
+  using IntervalT = std::pair<EltT, EltT>;
+
+public:
+  using Allocator = typename MapT::Allocator;
+
+  /// Construct by passing in a CoalescingBitVector<EltT>::Allocator reference.
+  CoalescingBitVector(Allocator &Alloc)
+      : Alloc(&Alloc), Intervals(std::make_unique<MapT>(Alloc)) {}
+
+  /// \name Copy/move constructors and assignment operators.
+  /// @{
+
+  CoalescingBitVector(const ThisT &RHS)
+      : Alloc(RHS.Alloc), Intervals(std::make_unique<MapT>(*RHS.Alloc)) {
+    initFromRHS(RHS);
+  }
+
+  ThisT &operator=(const ThisT &RHS) {
+    clear();
+    initFromRHS(RHS);
+    return *this;
+  }
+
+  CoalescingBitVector(ThisT &&RHS)
+      : Alloc(RHS.Alloc), Intervals(std::move(RHS.Intervals)) {}
+
+  CoalescingBitVector &operator=(ThisT &&RHS) {
+    Alloc = RHS.Alloc;
+    Intervals = std::move(RHS.Intervals);
+    return *this;
+  }
+
+  /// @}
+
+  /// Clear all the bits.
+  void clear() { Intervals->clear(); }
+
+  /// Check whether no bits are set.
+  bool empty() const { return Intervals->empty(); }
+
+  /// Count the number of set bits.
+  unsigned count() const {
+    unsigned Bits = 0;
+    for (auto It = Intervals->begin(), End = Intervals->end(); It != End; ++It)
+      Bits += 1 + It.stop() - It.start();
+    return Bits;
+  }
+
+  /// Set the bit at \p Index.
+  ///
+  /// This method does /not/ support setting a bit that has already been set,
+  /// for efficiency reasons. If possible, restructure your code to not set the
+  /// same bit multiple times, or use the test-and-set idiom.
+  void set(EltT Index) { insert(Index, Index); }
+
+  /// Set the bits at \p Indices. Used for testing, primarily.
+  void set(std::initializer_list<EltT> Indices) {
+    for (EltT Index : Indices)
+      set(Index);
+  }
+
+  /// Check whether the bit at \p Index is set.
+  bool test(EltT Index) const {
+    const auto It = Intervals->find(Index);
+    if (It == Intervals->end())
+      return false;
+    assert(It.stop() >= Index && "Interval must end after Index");
+    return It.start() <= Index;
+  }
+
+  /// Reset the bit at \p Index.
+  void reset(EltT Index) {
+    auto It = Intervals->find(Index);
+    if (It == Intervals->end())
+      return;
+
+    // Split the interval containing Index into up to two parts: one from
+    // [Start, Index-1] and another from [Index+1, Stop]. If Index is equal to
+    // either Start or Stop, we create one new interval. If Index is equal to
+    // both Start and Stop, we simply erase the existing interval.
+    EltT Start = It.start();
+    EltT Stop = It.stop();
+    assert(Start <= Index && Index <= Stop && "Wrong interval for index");
+    It.erase();
+    if (Start < Index)
+      insert(Start, Index - 1);
+    if (Index < Stop)
+      insert(Index + 1, Stop);
+  }
+
+  /// Set union.
+  void operator|=(const ThisT &RHS) { initFromRHS(RHS); }
+
+  /// Set intersection.
+  void operator&=(const ThisT &RHS) {
+    SmallVector<IntervalT, 8> Overlaps;
+    bool Overlap = getOverlaps(RHS, Overlaps);
+    clear();
+    if (Overlap)
+      for (IntervalT Overlap : Overlaps)
+        insert(Overlap.first, Overlap.second);
+  }
+
+  // Reset all bits present in \p RHS.
+  bool intersectWithComplement(const ThisT &RHS) {
+    SmallVector<IntervalT, 8> Overlaps;
+    if (!getOverlaps(RHS, Overlaps)) {
+      // If there is no overlap with RHS, the intersection is empty.
+      return false;
+    }
+
+    // Delete the overlapping intervals. Split up intervals that only partially
+    // intersect an overlap.
+    for (const auto &Overlap : Overlaps) {
+      EltT OlapStart, OlapStop;
+      std::tie(OlapStart, OlapStop) = Overlap;
+
+      auto It = Intervals->find(OlapStart);
+      EltT CurrStart = It.start();
+      EltT CurrStop = It.stop();
+      assert(CurrStart <= OlapStart && OlapStop <= CurrStop &&
+             "Expected some intersection!");
+
+      // Split the overlap interval into up to two parts: one from [CurrStart,
+      // OlapStart-1] and another from [OlapStop+1, CurrStop]. If OlapStart is
+      // equal to CurrStart, the first split interval is unnecessary. Ditto for
+      // when OlapStop is equal to CurrStop, we omit second split interval.
+      It.erase();
+      if (CurrStart < OlapStart)
+        insert(CurrStart, OlapStart - 1);
+      if (OlapStop < CurrStop)
+        insert(OlapStop + 1, CurrStop);
+    }
+    return true;
+  }
+
+  bool operator==(const ThisT &RHS) const {
+    // We cannot just use std::equal because it checks the dereferenced values
+    // of an iterator pair for equality, not the iterators themselves. In our
+    // case that results in comparison of the (unused) IntervalMap values.
+    auto ItL = Intervals->begin();
+    auto ItR = RHS.Intervals->begin();
+    while (ItL != Intervals->end() && ItR != RHS.Intervals->end() &&
+           ItL.start() == ItR.start() && ItL.stop() == ItR.stop()) {
+      ++ItL;
+      ++ItR;
+    }
+    return ItL == Intervals->end() && ItR == RHS.Intervals->end();
+  }
+
+  bool operator!=(const ThisT &RHS) const { return !operator==(RHS); }
+
+  class const_iterator : public std::iterator<std::forward_iterator_tag, EltT> {
+    friend class CoalescingBitVector;
+
+    // For performance reasons, make the offset at the end different than the
+    // one used in \ref begin, to optimize the common `It == end()` pattern.
+    static constexpr unsigned kIteratorAtTheEndOffset = ~0u;
+
+    UnderlyingIterator MapIterator;
+    unsigned OffsetIntoMapIterator = 0;
+
+    // Querying the start/stop of an IntervalMap iterator can be very expensive.
+    // Cache these values for performance reasons.
+    EltT CachedStart = EltT();
+    EltT CachedStop = EltT();
+
+    void setToEnd() {
+      OffsetIntoMapIterator = kIteratorAtTheEndOffset;
+      CachedStart = EltT();
+      CachedStop = EltT();
+    }
+
+    /// MapIterator has just been changed, reset the cached state to point to
+    /// the start of the new underlying iterator.
+    void resetCache() {
+      if (MapIterator.valid()) {
+        OffsetIntoMapIterator = 0;
+        CachedStart = MapIterator.start();
+        CachedStop = MapIterator.stop();
+      } else {
+        setToEnd();
+      }
+    }
+
+    /// Advance the iterator to \p Index, if it is contained within the current
+    /// interval.
+    void advanceTo(EltT Index) {
+      if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
+        // No such index found.
+        return;
+
+      assert(OffsetIntoMapIterator == 0 && "Not implemented");
+      assert(Index <= CachedStop && "Cannot advance to OOB index");
+      if (Index < CachedStart)
+        // We're already past this index.
+        return;
+      OffsetIntoMapIterator = Index - CachedStart;
+    }
+
+    const_iterator(UnderlyingIterator MapIt) : MapIterator(MapIt) {
+      resetCache();
+    }
+
+  public:
+    const_iterator() { setToEnd(); }
+
+    bool operator==(const const_iterator &RHS) const {
+      // Do /not/ compare MapIterator for equality, as this is very expensive.
+      // The cached start/stop values make that check unnecessary.
+      return std::tie(OffsetIntoMapIterator, CachedStart, CachedStop) ==
+             std::tie(RHS.OffsetIntoMapIterator, RHS.CachedStart,
+                      RHS.CachedStop);
+    }
+
+    bool operator!=(const const_iterator &RHS) const {
+      return !operator==(RHS);
+    }
+
+    EltT operator*() const {
+      return CachedStart + OffsetIntoMapIterator;
+    }
+
+    const_iterator &operator++() { // Pre-increment (++It).
+      if (CachedStart + OffsetIntoMapIterator < CachedStop) {
+        // Keep going within the current interval.
+        ++OffsetIntoMapIterator;
+      } else {
+        // We reached the end of the current interval: advance.
+        ++MapIterator;
+        resetCache();
+      }
+      return *this;
+    }
+
+    const_iterator operator++(int) { // Post-increment (It++).
+      const_iterator tmp = *this;
+      operator++();
+      return tmp;
+    }
+  };
+
+  const_iterator begin() const { return const_iterator(Intervals->begin()); }
+
+  const_iterator end() const { return const_iterator(); }
+
+  /// Return an iterator pointing to the first set bit AT, OR AFTER, \p Index.
+  /// If no such set bit exists, return end(). This is like std::lower_bound.
+  const_iterator find(EltT Index) const {
+    auto UnderlyingIt = Intervals->find(Index);
+    if (UnderlyingIt == Intervals->end())
+      return end();
+    auto It = const_iterator(UnderlyingIt);
+    It.advanceTo(Index);
+    return It;
+  }
+
+  void print(raw_ostream &OS) const {
+    // LLDB swallows the first line of output after callling dump(). Add
+    // newlines before/after the braces to work around this.
+    OS << "\n{";
+    for (auto It = Intervals->begin(), End = Intervals->end(); It != End;
+         ++It) {
+      OS << "[" << It.start();
+      if (It.start() != It.stop())
+        OS << ", " << It.stop();
+      OS << "]";
+    }
+    OS << "}\n";
+  }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
+#endif
+
+private:
+  void initFromRHS(const ThisT &RHS) {
+    for (auto It = RHS.Intervals->begin(), End = RHS.Intervals->end();
+         It != End; ++It)
+      insert(It.start(), It.stop());
+  }
+
+  void insert(EltT Start, EltT End) { Intervals->insert(Start, End, 0); }
+
+  /// Record the overlaps between \p this and \p RHS in \p Overlaps. Return
+  /// true if there is any overlap.
+  bool getOverlaps(const ThisT &RHS,
+                   SmallVectorImpl<IntervalT> &Overlaps) const {
+    for (IntervalMapOverlaps<MapT, MapT> I(*Intervals, *RHS.Intervals);
+         I.valid(); ++I)
+      Overlaps.emplace_back(I.start(), I.stop());
+    return !Overlaps.empty();
+  }
+
+  Allocator *Alloc;
+  std::unique_ptr<MapT> Intervals;
+};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_COALESCINGBITVECTOR_H

llvm/unittests/ADT/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_llvm_unittest(ADTTests
   AnyTest.cpp
   APFloatTest.cpp
   APIntTest.cpp
   APSIntTest.cpp
   ArrayRefTest.cpp
   BitmaskEnumTest.cpp
   BitVectorTest.cpp
   BreadthFirstIteratorTest.cpp
   BumpPtrListTest.cpp
+  CoalescingBitVectorTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
   DenseSetTest.cpp
   DepthFirstIteratorTest.cpp
   DirectedGraphTest.cpp
   EnumeratedArrayTest.cpp
   EquivalenceClassesTest.cpp

llvm/unittests/ADT/CoalescingBitVectorTest.cpp

+//=== 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;
+}
+
+TEST(CoalescingBitVectorTest, Set) {
+  UBitVec::Allocator Alloc;
+  UBitVec BV(Alloc);
+  BV.set(0);
+  EXPECT_TRUE(BV.test(0));
+  EXPECT_FALSE(BV.test(1));
+}
+
+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(CoalescingBitVector, Move) {
+  UBitVec::Allocator Alloc;
+  UBitVec BV1(Alloc);
+  BV1.set(0);
+  UBitVec BV2 = std::move(BV1);
+  EXPECT_TRUE(elementsMatch(BV2, {0}));
+  BV2.set(5);
+  BV1 = std::move(BV2);
+  EXPECT_TRUE(elementsMatch(BV1, {0, 5}));
+}
+
+TEST(CoalescingBitVectorTest, Iterators) {
+  UBitVec::Allocator Alloc;
+  UBitVec BV(Alloc);
+
+  BV.set({0, 1, 2});
+
+  auto It = BV.begin();
+  EXPECT_EQ(It, BV.begin());
+  EXPECT_EQ(*It, 0u);
+  ++It;
+  EXPECT_EQ(*It, 1u);
+  ++It;
+  EXPECT_EQ(*It, 2u);
+  ++It;
+  EXPECT_EQ(It, BV.end());
+  EXPECT_EQ(BV.end(), BV.end());
+
+  It = BV.begin();
+  EXPECT_EQ(It, BV.begin());
+  auto ItCopy = It++;
+  EXPECT_EQ(ItCopy, BV.begin());
+  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}));
+
+  BV.reset(3);
+  BV.set({1000, 1001, 1002});
+  EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6, 10, 1000, 1001, 1002}));
+
+  auto It1 = BV.begin();
+  EXPECT_EQ(It1, BV.begin());
+  EXPECT_EQ(++It1, ++BV.begin());
+  EXPECT_NE(It1, BV.begin());
+  EXPECT_NE(It1, BV.end());
+}
+
+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 intersection, used to double-check the
+// human "expected" answer.
+UBitVec simpleIntersection(UBitVec::Allocator &Alloc, const UBitVec &LHS,
+                           const UBitVec &RHS) {
+  UBitVec Intersection(Alloc);
+  for (unsigned Bit : LHS)
+    if (RHS.test(Bit))
+      Intersection.set(Bit);
+  return Intersection;
+}
+
+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);
+    const UBitVec &DoubleCheckedExpected = simpleIntersection(Alloc, BV1, BV2);
+    ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
+    BV1 &= BV2;
+    ASSERT_TRUE(elementsMatch(BV1, Expected));
+  };
+
+  // Empty case, one-element case.
+  intersectionIs({}, {}, {});
+  intersectionIs({1}, {1}, {1});
+  intersectionIs({1}, {2}, {});
+
+  // Exact overlaps cases: single overlap and multiple overlaps.
+  intersectionIs({1, 2}, {1, 2}, {1, 2});
+  intersectionIs({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.
+  intersectionIs({2, 3, 4}, {1, 2, 3}, {2, 3});
+  intersectionIs({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
+  intersectionIs({2, 3, 4}, {3, 4, 5}, {3, 4});
+  intersectionIs({1, 2, 3}, {2, 3, 4}, {2, 3});
+  intersectionIs({3, 4, 5}, {2, 3, 4}, {3, 4});
+
+  // No overlap, but we have multiple intervals.
+  intersectionIs({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.
+  intersectionIs({1, 2, 11, 12}, {1}, {1});
+  intersectionIs({1, 2, 11, 12}, {2}, {2});
+  intersectionIs({1, 2, 11, 12}, {11}, {11});
+  intersectionIs({1, 2, 11, 12}, {12}, {12});
+  intersectionIs({1, 2, 11, 12}, {1, 11}, {1, 11});
+  intersectionIs({1, 2, 11, 12}, {1, 12}, {1, 12});
+  intersectionIs({1, 2, 11, 12}, {2, 11}, {2, 11});
+  intersectionIs({1, 2, 11, 12}, {2, 12}, {2, 12});
+  intersectionIs({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11});
+  intersectionIs({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 12});
+  intersectionIs({1, 2, 11, 12}, {1, 11, 12}, {1, 11, 12});
+  intersectionIs({1, 2, 11, 12}, {2, 11, 12}, {2, 11, 12});
+  intersectionIs({1, 2, 11, 12}, {0, 11, 12}, {11, 12});
+  intersectionIs({1, 2, 11, 12}, {3, 11, 12}, {11, 12});
+  intersectionIs({1, 2, 11, 12}, {1, 11, 13}, {1, 11});
+  intersectionIs({1, 2, 11, 12}, {1, 10, 11}, {1, 11});
+
+  // Partial overlap, but the existing interval covers future overlaps.
+  intersectionIs({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.
+UBitVec simpleIntersectionWithComplement(UBitVec::Allocator &Alloc,
+                                         const UBitVec &LHS,
+                                         const UBitVec &RHS) {
+  UBitVec Intersection(Alloc);
+  for (unsigned Bit : LHS)
+    if (!RHS.test(Bit))
+      Intersection.set(Bit);
+  return Intersection;
+}
+
+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);
+        const UBitVec &DoubleCheckedExpected =
+            simpleIntersectionWithComplement(Alloc, BV1, BV2);
+        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;
+  EXPECT_EQ(BV.find(BigNum1), BV.end());
+  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);
+}
+
+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, "\n"
+               "{[1]}"
+               "\n\n"
+               "{[1][11, 20]}"
+               "\n");
+}
+
+} // namespace

llvm/unittests/ADT/IntervalMapTest.cpp

TEST(IntervalMapTest, EmptyMap) {
   UUMap::const_iterator CI;
   CI = map.begin();
   EXPECT_TRUE(CI == I);
   UUMap::iterator I2;
   I2 = map.end();
   EXPECT_TRUE(I2 == CI);
 }
 
+// Test one-element closed ranges.
+TEST(IntervalMapTest, OneElementRanges) {
+  UUMap::Allocator allocator;
+  UUMap map(allocator);
+  map.insert(1, 1, 1);
+  map.insert(2, 2, 2);
+  EXPECT_EQ(1u, map.lookup(1));
+  EXPECT_EQ(2u, map.lookup(2));
+}
+
 // Single entry map tests
 TEST(IntervalMapTest, SingleEntryMap) {
   UUMap::Allocator allocator;
   UUMap map(allocator);
   map.insert(100, 150, 1);
   EXPECT_FALSE(map.empty());
 
   // Lookup around interval.