[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

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

109

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/docs/ProgrammersManual.rst

 (each insertion requires a malloc) and very non-portable.
 
 std::multimap is useful if you want to map a key to multiple values, but has all
 the drawbacks of std::map.  A sorted vector or some other approach is almost
 always better.
 
 .. _ds_bit:
 
-Bit storage containers (BitVector, SparseBitVector)
----------------------------------------------------
+Bit storage containers (BitVector, SparseBitVector, CoalescingBitVector)
+------------------------------------------------------------------------
 
-Unlike the other containers, there are only two bit storage containers, and
-choosing when to use each is relatively straightforward.
+There are four bit storage containers, and choosing when to use each is
+relatively straightforward.
 
 One additional option is ``std::vector<bool>``: we discourage its use for two
 reasons 1) the implementation in many common compilers (e.g.  commonly
 available versions of GCC) is extremely inefficient and 2) the C++ standards
 committee is likely to deprecate this container and/or change it significantly
 somehow.  In any case, please don't use it.
 
 .. _dss_bitvector:

 set operations O(number of set bits) instead of O(size of universe).  The
 downside to the SparseBitVector is that setting and testing of random bits is
 O(N), and on large SparseBitVectors, this can be slower than BitVector.  In our
 implementation, setting or testing bits in sorted order (either forwards or
 reverse) is O(1) worst case.  Testing and setting bits within 128 bits (depends
 on size) of the current bit is also O(1).  As a general statement,
 testing/setting bits in a SparseBitVector is O(distance away from last set bit).
 
+.. _dss_coalescingbitvector:
+
+CoalescingBitVector
+^^^^^^^^^^^^^^^^^^^
+
+The CoalescingBitVector container is similar in principle to a SparseBitVector,
+but is optimized to represent large contiguous ranges of set bits compactly. It
+does this by coalescing contiguous ranges of set bits into intervals. Searching
+for a bit in a CoalescingBitVector is O(log(gaps between contiguous ranges)).
+
+CoalescingBitVector is a better choice than BitVector when gaps between ranges
+of set bits are large. It's a better choice than SparseBitVector when find()
+operations must have fast, predictable performance. However, it's not a good
+choice for representing sets which have lots of very short ranges. E.g. the set
+`{2*x : x \in [0, n)}` would be a pathological input.
+
 .. _debugging:
 
 Debugging
 =========
 
 A handful of `GDB pretty printers
 <https://sourceware.org/gdb/onlinedocs/gdb/Pretty-Printing.html>`__ are
 provided for some of the core LLVM libraries. To use them, execute the

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
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file A bitvector that uses an IntervalMap to coalesce adjacent elements
+/// into intervals.
+///
+//===----------------------------------------------------------------------===//
+
+#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.
+///
+/// Compared to SparseBitVector, CoalescingBitVector offers more predictable
+/// performance for non-sequential find() operations.
+///
+/// \param IndexT - The type of the index into the bitvector.
+/// \param N - The first N coalesced intervals of set bits are stored in-place
+/// (in the initial heap allocation).
+template <typename IndexT, unsigned N = 16> class CoalescingBitVector {
+  static_assert(std::is_unsigned<IndexT>::value,
+                "Index must be an unsigned integer.");
+
+  using ThisT = CoalescingBitVector<IndexT, N>;
+
+  /// An interval map for closed integer ranges. The mapped values are unused.
+  using MapT = IntervalMap<IndexT, char, N>;
+
+  using UnderlyingIterator = typename MapT::const_iterator;
+
+  using IntervalT = std::pair<IndexT, IndexT>;
+
+public:
+  using Allocator = typename MapT::Allocator;
+
+  /// Construct by passing in a CoalescingBitVector<IndexT>::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)) {}
+
+  ThisT &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 \ref test_and_set.
+  void set(IndexT Index) { insert(Index, Index); }
+
+  /// Set the bits set in \p RHS.
+  ///
+  /// This method does /not/ support setting already-set bits, see \ref set
+  /// for the rationale. For a safe set union operation, use \ref operator|=.
+  void set(const ThisT &RHS) { initFromRHS(RHS); }
+
+  /// Set the bits at \p Indices. Used for testing, primarily.
+  void set(std::initializer_list<IndexT> Indices) {
+    for (IndexT Index : Indices)
+      set(Index);
+  }
+
+  /// Check whether the bit at \p Index is set.
+  bool test(IndexT 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;
+  }
+
+  /// Set the bit at \p Index. Supports setting an already-set bit.
+  void test_and_set(IndexT Index) {
+    if (!test(Index))
+      set(Index);
+  }
+
+  /// Reset the bit at \p Index. Supports resetting an already-unset bit.
+  void reset(IndexT 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.
+    IndexT Start = It.start();
+    if (Index < Start)
+      // The index was not set.
+      return;
+    IndexT Stop = It.stop();
+    assert(Index <= Stop && "Wrong interval for index");
+    It.erase();
+    if (Start < Index)
+      insert(Start, Index - 1);
+    if (Index < Stop)
+      insert(Index + 1, Stop);
+  }
+
+  /// Set union. If \p RHS is guaranteed to not overlap with this, \ref set may
+  /// be a faster alternative.
+  void operator|=(const ThisT &RHS) {
+    // Get the overlaps between the two interval maps.
+    SmallVector<IntervalT, 8> Overlaps;
+    getOverlaps(RHS, Overlaps);
+    // Insert all intervals from RHS. If an interval from RHS would overlap
+    // with an existing interval, be careful to only insert the non-overlapping
+    // portions.
+    unsigned CurrentOlap = 0;
+    for (auto It = RHS.Intervals->begin(), End = RHS.Intervals->end();
+         It != End; ++It) {
+      IndexT Start = It.start();
+      IndexT Stop = It.stop();
+
+      // [Start;Stop] and [OlapStart;OlapStop] overlap iff OlapStart <= Stop
+      // and Start <= OlapStop.
+      if (CurrentOlap < Overlaps.size()) {
+        IndexT OlapStart, OlapStop;
+        std::tie(OlapStart, OlapStop) = Overlaps[CurrentOlap];
+        if (OlapStart <= Stop && Start <= OlapStop) {
+          if (Start < OlapStart)
+            insert(Start, OlapStart - 1);
+          if (OlapStop < Stop)
+            insert(OlapStop + 1, Stop);
+          ++CurrentOlap;
+          continue;
+        }
+      }
+
+      insert(Start, Stop);
+    }
+  }
+
+  /// Set intersection.
+  void operator&=(const ThisT &RHS) {
+    // Get the overlaps between the two interval maps (i.e. the intersection).
+    SmallVector<IntervalT, 8> Overlaps;
+    getOverlaps(RHS, Overlaps);
+    // Rebuild the interval map, including only the overlaps.
+    clear();
+    for (IntervalT Overlap : Overlaps)
+      insert(Overlap.first, Overlap.second);
+  }
+
+  /// Reset all bits present in \p RHS.
+  void intersectWithComplement(const ThisT &RHS) {
+    SmallVector<IntervalT, 8> Overlaps;
+    if (!getOverlaps(RHS, Overlaps)) {
+      // If there is no overlap with RHS, the intersection is empty.
+      return;
+    }
+
+    // Delete the overlapping intervals. Split up intervals that only partially
+    // intersect an overlap.
+    for (IntervalT Overlap : Overlaps) {
+      IndexT OlapStart, OlapStop;
+      std::tie(OlapStart, OlapStop) = Overlap;
+
+      auto It = Intervals->find(OlapStart);
+      IndexT CurrStart = It.start();
+      IndexT 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 the second split interval.
+      It.erase();
+      if (CurrStart < OlapStart)
+        insert(CurrStart, OlapStart - 1);
+      if (OlapStop < CurrStop)
+        insert(OlapStop + 1, CurrStop);
+    }
+  }
+
+  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, IndexT> {
+    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.
+    IndexT CachedStart = IndexT();
+    IndexT CachedStop = IndexT();
+
+    void setToEnd() {
+      OffsetIntoMapIterator = kIteratorAtTheEndOffset;
+      CachedStart = IndexT();
+      CachedStop = IndexT();
+    }
+
+    /// MapIterator has just 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(IndexT Index) {
+      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);
+    }
+
+    IndexT 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(IndexT 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 {
+    OS << "{";
+    for (auto It = Intervals->begin(), End = Intervals->end(); It != End;
+         ++It) {
+      OS << "[" << It.start();
+      if (It.start() != It.stop())
+        OS << ", " << It.stop();
+      OS << "]";
+    }
+    OS << "}";
+  }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const {
+    // LLDB swallows the first line of output after callling dump(). Add
+    // newlines before/after the braces to work around this.
+    dbgs() << "\n";
+    print(dbgs());
+    dbgs() << "\n";
+  }
+#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(IndexT Start, IndexT 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 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(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}));
+
+  // 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();
+  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 union, used to double-check the human
+// "expected" answer.
+UBitVec simpleUnion(UBitVec::Allocator &Alloc, const UBitVec &LHS,
+                    const UBitVec &RHS) {
+  UBitVec Union(Alloc);
+  for (unsigned Bit : LHS)
+    Union.test_and_set(Bit);
+  for (unsigned Bit : RHS)
+    Union.test_and_set(Bit);
+  return Union;
+}
+
+TEST(CoalescingBitVectorTest, Union) {
+  UBitVec::Allocator Alloc;
+
+  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);
+    const UBitVec &DoubleCheckedExpected = simpleUnion(Alloc, BV1, BV2);
+    ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
+    BV1 |= BV2;
+    ASSERT_TRUE(elementsMatch(BV1, Expected));
+  };
+
+  // Empty LHS.
+  unionIs({}, {1, 2, 3}, {1, 2, 3});
+
+  // Empty RHS.
+  unionIs({1, 2, 3}, {}, {1, 2, 3});
+
+  // Full overlap.
+  unionIs({1}, {1}, {1});
+  unionIs({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.
+  unionIs({2, 3, 4}, {1, 2, 3}, {1, 2, 3, 4});
+  unionIs({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
+  unionIs({2, 3, 4}, {3, 4, 5}, {2, 3, 4, 5});
+  unionIs({1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4});
+  unionIs({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.
+  unionIs({1, 2, 11, 12}, {1}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {2}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {11}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {12}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {1, 11}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {1, 12}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {2, 11}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {2, 12}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {1, 11, 12}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {2, 11, 12}, {1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {0, 11, 12}, {0, 1, 2, 11, 12});
+  unionIs({1, 2, 11, 12}, {3, 11, 12}, {1, 2, 3, 11, 12});
+  unionIs({1, 2, 11, 12}, {1, 11, 13}, {1, 2, 11, 12, 13});
+  unionIs({1, 2, 11, 12}, {1, 10, 11}, {1, 2, 10, 11, 12});
+
+  // Partial overlap, but the existing interval covers future overlaps.
+  unionIs({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7}, {1, 2, 3, 4, 5, 6, 7, 8});
+}
+
+// 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, "{[1]}"
+               "{[1][11, 20]}");
+}
+
+} // 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.