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/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

#include <initializer_list>

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.
///
/// \tparam IndexT - The type of the index into the bitvector.
template <typename IndexT> class CoalescingBitVector {
  static_assert(std::is_unsigned<IndexT>::value,
                "Index must be an unsigned integer.");

  using ThisT = CoalescingBitVector<IndexT>;

  /// An interval map for closed integer ranges. The mapped values are unused.
  using MapT = IntervalMap<IndexT, char>;

  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(Alloc) {}

  /// \name Copy/move constructors and assignment operators.
  /// @{

  CoalescingBitVector(const ThisT &Other)
      : Alloc(Other.Alloc), Intervals(*Other.Alloc) {
    set(Other);
  }

  ThisT &operator=(const ThisT &Other) {
    clear();
    set(Other);
    return *this;
  }

  CoalescingBitVector(ThisT &&Other) = delete;
  ThisT &operator=(ThisT &&Other) = delete;

  /// @}

  /// 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) {
    assert(!test(Index) && "Setting already-set bits not supported/efficient, "
                           "IntervalMap will assert");
    insert(Index, Index);
  }

  /// Set the bits set in \p Other.
  ///
  /// 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 &Other) {
    for (auto It = Other.Intervals.begin(), End = Other.Intervals.end();
         It != End; ++It)
      insert(It.start(), It.stop());
  }

  /// 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 the non-overlapping parts of all the intervals from RHS.
    for (auto It = RHS.Intervals.begin(), End = RHS.Intervals.end();
         It != End; ++It) {
      IndexT Start = It.start();
      IndexT Stop = It.stop();
      SmallVector<IntervalT, 8> NonOverlappingParts;
      getNonOverlappingParts(Start, Stop, Overlaps, NonOverlappingParts);
      for (IntervalT AdditivePortion : NonOverlappingParts)
        insert(AdditivePortion.first, AdditivePortion.second);
    }
  }

  /// 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 Other.
  void intersectWithComplement(const ThisT &Other) {
    SmallVector<IntervalT, 8> Overlaps;
    if (!getOverlaps(Other, Overlaps)) {
      // If there is no overlap with Other, 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 {
    friend class CoalescingBitVector;

  public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = IndexT;
    using difference_type = std::ptrdiff_t;
    using pointer = value_type *;
    using reference = value_type &;

  private:
    // 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. The public-facing method which supports advancing past the
    /// current interval is \ref advanceToLowerBound.
    void advanceTo(IndexT Index) {
      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;
    }

    /// Advance the iterator to the first set bit AT, OR AFTER, \p Index. If
    /// no such set bit exists, advance to end(). This is like std::lower_bound.
    /// This is useful if \p Index is close to the current iterator position.
    /// However, unlike \ref find(), this has worst-case O(n) performance.
    void advanceToLowerBound(IndexT Index) {
      if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
        return;

      // Advance to the first interval containing (or past) Index, or to end().
      while (Index > CachedStop) {
        ++MapIterator;
        resetCache();
        if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
          return;
      }

      advanceTo(Index);
    }
  };

  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.
  /// This has worst-case logarithmic performance (roughly O(log(gaps between
  /// contiguous ranges))).
  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;
  }

  /// Return a range iterator which iterates over all of the set bits in the
  /// half-open range [Start, End).
  iterator_range<const_iterator> half_open_range(IndexT Start,
                                                 IndexT End) const {
    assert(Start < End && "Not a valid range");
    auto StartIt = find(Start);
    if (StartIt == end() || *StartIt >= End)
      return {end(), end()};
    auto EndIt = StartIt;
    EndIt.advanceToLowerBound(End);
    return {StartIt, EndIt};
  }

  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 insert(IndexT Start, IndexT End) { Intervals.insert(Start, End, 0); }

  /// Record the overlaps between \p this and \p Other in \p Overlaps. Return
  /// true if there is any overlap.
  bool getOverlaps(const ThisT &Other,
                   SmallVectorImpl<IntervalT> &Overlaps) const {
    for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals);
         I.valid(); ++I)
      Overlaps.emplace_back(I.start(), I.stop());
    assert(llvm::is_sorted(Overlaps,
                           [](IntervalT LHS, IntervalT RHS) {
                             return LHS.second < RHS.first;
                           }) &&
           "Overlaps must be sorted");
    return !Overlaps.empty();
  }

  /// Given the set of overlaps between this and some other bitvector, and an
  /// interval [Start, Stop] from that bitvector, determine the portions of the
  /// interval which do not overlap with this.
  void getNonOverlappingParts(IndexT Start, IndexT Stop,
                              const SmallVectorImpl<IntervalT> &Overlaps,
                              SmallVectorImpl<IntervalT> &NonOverlappingParts) {
    IndexT NextUncoveredBit = Start;
    for (IntervalT Overlap : Overlaps) {
      IndexT OlapStart, OlapStop;
      std::tie(OlapStart, OlapStop) = Overlap;

      // [Start;Stop] and [OlapStart;OlapStop] overlap iff OlapStart <= Stop
      // and Start <= OlapStop.
      bool DoesOverlap = OlapStart <= Stop && Start <= OlapStop;
      if (!DoesOverlap)
        continue;

      // Cover the range [NextUncoveredBit, OlapStart). This puts the start of
      // the next uncovered range at OlapStop+1.
      if (NextUncoveredBit < OlapStart)
        NonOverlappingParts.emplace_back(NextUncoveredBit, OlapStart - 1);
      NextUncoveredBit = OlapStop + 1;
      if (NextUncoveredBit > Stop)
        break;
    }
    if (NextUncoveredBit <= Stop)
      NonOverlappingParts.emplace_back(NextUncoveredBit, Stop);
  }

  Allocator *Alloc;
  MapT Intervals;
};

} // namespace llvm

#endif // LLVM_ADT_COALESCINGBITVECTOR_H