15ffd83dbSDimitry Andric //===- llvm/ADT/CoalescingBitVector.h - A coalescing bitvector --*- C++ -*-===// 25ffd83dbSDimitry Andric // 35ffd83dbSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 45ffd83dbSDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 55ffd83dbSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 65ffd83dbSDimitry Andric // 75ffd83dbSDimitry Andric //===----------------------------------------------------------------------===// 85ffd83dbSDimitry Andric /// 91fd87a68SDimitry Andric /// \file 101fd87a68SDimitry Andric /// A bitvector that uses an IntervalMap to coalesce adjacent elements 115ffd83dbSDimitry Andric /// into intervals. 125ffd83dbSDimitry Andric /// 135ffd83dbSDimitry Andric //===----------------------------------------------------------------------===// 145ffd83dbSDimitry Andric 155ffd83dbSDimitry Andric #ifndef LLVM_ADT_COALESCINGBITVECTOR_H 165ffd83dbSDimitry Andric #define LLVM_ADT_COALESCINGBITVECTOR_H 175ffd83dbSDimitry Andric 185ffd83dbSDimitry Andric #include "llvm/ADT/IntervalMap.h" 1904eeddc0SDimitry Andric #include "llvm/ADT/STLExtras.h" 205ffd83dbSDimitry Andric #include "llvm/ADT/SmallVector.h" 215ffd83dbSDimitry Andric #include "llvm/ADT/iterator_range.h" 225ffd83dbSDimitry Andric #include "llvm/Support/Debug.h" 235ffd83dbSDimitry Andric #include "llvm/Support/raw_ostream.h" 245ffd83dbSDimitry Andric 255ffd83dbSDimitry Andric #include <initializer_list> 265ffd83dbSDimitry Andric 275ffd83dbSDimitry Andric namespace llvm { 285ffd83dbSDimitry Andric 295ffd83dbSDimitry Andric /// A bitvector that, under the hood, relies on an IntervalMap to coalesce 305ffd83dbSDimitry Andric /// elements into intervals. Good for representing sets which predominantly 315ffd83dbSDimitry Andric /// contain contiguous ranges. Bad for representing sets with lots of gaps 325ffd83dbSDimitry Andric /// between elements. 335ffd83dbSDimitry Andric /// 345ffd83dbSDimitry Andric /// Compared to SparseBitVector, CoalescingBitVector offers more predictable 355ffd83dbSDimitry Andric /// performance for non-sequential find() operations. 365ffd83dbSDimitry Andric /// 375ffd83dbSDimitry Andric /// \tparam IndexT - The type of the index into the bitvector. 38031db28bSDimitry Andric template <typename IndexT> class CoalescingBitVector { 395ffd83dbSDimitry Andric static_assert(std::is_unsigned<IndexT>::value, 405ffd83dbSDimitry Andric "Index must be an unsigned integer."); 415ffd83dbSDimitry Andric 42031db28bSDimitry Andric using ThisT = CoalescingBitVector<IndexT>; 435ffd83dbSDimitry Andric 445ffd83dbSDimitry Andric /// An interval map for closed integer ranges. The mapped values are unused. 45031db28bSDimitry Andric using MapT = IntervalMap<IndexT, char>; 465ffd83dbSDimitry Andric 475ffd83dbSDimitry Andric using UnderlyingIterator = typename MapT::const_iterator; 485ffd83dbSDimitry Andric 495ffd83dbSDimitry Andric using IntervalT = std::pair<IndexT, IndexT>; 505ffd83dbSDimitry Andric 515ffd83dbSDimitry Andric public: 525ffd83dbSDimitry Andric using Allocator = typename MapT::Allocator; 535ffd83dbSDimitry Andric 545ffd83dbSDimitry Andric /// Construct by passing in a CoalescingBitVector<IndexT>::Allocator 555ffd83dbSDimitry Andric /// reference. CoalescingBitVector(Allocator & Alloc)565ffd83dbSDimitry Andric CoalescingBitVector(Allocator &Alloc) 575ffd83dbSDimitry Andric : Alloc(&Alloc), Intervals(Alloc) {} 585ffd83dbSDimitry Andric 595ffd83dbSDimitry Andric /// \name Copy/move constructors and assignment operators. 605ffd83dbSDimitry Andric /// @{ 615ffd83dbSDimitry Andric CoalescingBitVector(const ThisT & Other)625ffd83dbSDimitry Andric CoalescingBitVector(const ThisT &Other) 635ffd83dbSDimitry Andric : Alloc(Other.Alloc), Intervals(*Other.Alloc) { 645ffd83dbSDimitry Andric set(Other); 655ffd83dbSDimitry Andric } 665ffd83dbSDimitry Andric 675ffd83dbSDimitry Andric ThisT &operator=(const ThisT &Other) { 685ffd83dbSDimitry Andric clear(); 695ffd83dbSDimitry Andric set(Other); 705ffd83dbSDimitry Andric return *this; 715ffd83dbSDimitry Andric } 725ffd83dbSDimitry Andric 735ffd83dbSDimitry Andric CoalescingBitVector(ThisT &&Other) = delete; 745ffd83dbSDimitry Andric ThisT &operator=(ThisT &&Other) = delete; 755ffd83dbSDimitry Andric 765ffd83dbSDimitry Andric /// @} 775ffd83dbSDimitry Andric 785ffd83dbSDimitry Andric /// Clear all the bits. clear()795ffd83dbSDimitry Andric void clear() { Intervals.clear(); } 805ffd83dbSDimitry Andric 815ffd83dbSDimitry Andric /// Check whether no bits are set. empty()825ffd83dbSDimitry Andric bool empty() const { return Intervals.empty(); } 835ffd83dbSDimitry Andric 845ffd83dbSDimitry Andric /// Count the number of set bits. count()855ffd83dbSDimitry Andric unsigned count() const { 865ffd83dbSDimitry Andric unsigned Bits = 0; 875ffd83dbSDimitry Andric for (auto It = Intervals.begin(), End = Intervals.end(); It != End; ++It) 885ffd83dbSDimitry Andric Bits += 1 + It.stop() - It.start(); 895ffd83dbSDimitry Andric return Bits; 905ffd83dbSDimitry Andric } 915ffd83dbSDimitry Andric 925ffd83dbSDimitry Andric /// Set the bit at \p Index. 935ffd83dbSDimitry Andric /// 945ffd83dbSDimitry Andric /// This method does /not/ support setting a bit that has already been set, 955ffd83dbSDimitry Andric /// for efficiency reasons. If possible, restructure your code to not set the 965ffd83dbSDimitry Andric /// same bit multiple times, or use \ref test_and_set. set(IndexT Index)975ffd83dbSDimitry Andric void set(IndexT Index) { 985ffd83dbSDimitry Andric assert(!test(Index) && "Setting already-set bits not supported/efficient, " 995ffd83dbSDimitry Andric "IntervalMap will assert"); 1005ffd83dbSDimitry Andric insert(Index, Index); 1015ffd83dbSDimitry Andric } 1025ffd83dbSDimitry Andric 1035ffd83dbSDimitry Andric /// Set the bits set in \p Other. 1045ffd83dbSDimitry Andric /// 1055ffd83dbSDimitry Andric /// This method does /not/ support setting already-set bits, see \ref set 1065ffd83dbSDimitry Andric /// for the rationale. For a safe set union operation, use \ref operator|=. set(const ThisT & Other)1075ffd83dbSDimitry Andric void set(const ThisT &Other) { 1085ffd83dbSDimitry Andric for (auto It = Other.Intervals.begin(), End = Other.Intervals.end(); 1095ffd83dbSDimitry Andric It != End; ++It) 1105ffd83dbSDimitry Andric insert(It.start(), It.stop()); 1115ffd83dbSDimitry Andric } 1125ffd83dbSDimitry Andric 1135ffd83dbSDimitry Andric /// Set the bits at \p Indices. Used for testing, primarily. set(std::initializer_list<IndexT> Indices)1145ffd83dbSDimitry Andric void set(std::initializer_list<IndexT> Indices) { 1155ffd83dbSDimitry Andric for (IndexT Index : Indices) 1165ffd83dbSDimitry Andric set(Index); 1175ffd83dbSDimitry Andric } 1185ffd83dbSDimitry Andric 1195ffd83dbSDimitry Andric /// Check whether the bit at \p Index is set. test(IndexT Index)1205ffd83dbSDimitry Andric bool test(IndexT Index) const { 1215ffd83dbSDimitry Andric const auto It = Intervals.find(Index); 1225ffd83dbSDimitry Andric if (It == Intervals.end()) 1235ffd83dbSDimitry Andric return false; 1245ffd83dbSDimitry Andric assert(It.stop() >= Index && "Interval must end after Index"); 1255ffd83dbSDimitry Andric return It.start() <= Index; 1265ffd83dbSDimitry Andric } 1275ffd83dbSDimitry Andric 1285ffd83dbSDimitry Andric /// Set the bit at \p Index. Supports setting an already-set bit. test_and_set(IndexT Index)1295ffd83dbSDimitry Andric void test_and_set(IndexT Index) { 1305ffd83dbSDimitry Andric if (!test(Index)) 1315ffd83dbSDimitry Andric set(Index); 1325ffd83dbSDimitry Andric } 1335ffd83dbSDimitry Andric 1345ffd83dbSDimitry Andric /// Reset the bit at \p Index. Supports resetting an already-unset bit. reset(IndexT Index)1355ffd83dbSDimitry Andric void reset(IndexT Index) { 1365ffd83dbSDimitry Andric auto It = Intervals.find(Index); 1375ffd83dbSDimitry Andric if (It == Intervals.end()) 1385ffd83dbSDimitry Andric return; 1395ffd83dbSDimitry Andric 1405ffd83dbSDimitry Andric // Split the interval containing Index into up to two parts: one from 1415ffd83dbSDimitry Andric // [Start, Index-1] and another from [Index+1, Stop]. If Index is equal to 1425ffd83dbSDimitry Andric // either Start or Stop, we create one new interval. If Index is equal to 1435ffd83dbSDimitry Andric // both Start and Stop, we simply erase the existing interval. 1445ffd83dbSDimitry Andric IndexT Start = It.start(); 1455ffd83dbSDimitry Andric if (Index < Start) 1465ffd83dbSDimitry Andric // The index was not set. 1475ffd83dbSDimitry Andric return; 1485ffd83dbSDimitry Andric IndexT Stop = It.stop(); 1495ffd83dbSDimitry Andric assert(Index <= Stop && "Wrong interval for index"); 1505ffd83dbSDimitry Andric It.erase(); 1515ffd83dbSDimitry Andric if (Start < Index) 1525ffd83dbSDimitry Andric insert(Start, Index - 1); 1535ffd83dbSDimitry Andric if (Index < Stop) 1545ffd83dbSDimitry Andric insert(Index + 1, Stop); 1555ffd83dbSDimitry Andric } 1565ffd83dbSDimitry Andric 1575ffd83dbSDimitry Andric /// Set union. If \p RHS is guaranteed to not overlap with this, \ref set may 1585ffd83dbSDimitry Andric /// be a faster alternative. 1595ffd83dbSDimitry Andric void operator|=(const ThisT &RHS) { 1605ffd83dbSDimitry Andric // Get the overlaps between the two interval maps. 1615ffd83dbSDimitry Andric SmallVector<IntervalT, 8> Overlaps; 1625ffd83dbSDimitry Andric getOverlaps(RHS, Overlaps); 1635ffd83dbSDimitry Andric 1645ffd83dbSDimitry Andric // Insert the non-overlapping parts of all the intervals from RHS. 1655ffd83dbSDimitry Andric for (auto It = RHS.Intervals.begin(), End = RHS.Intervals.end(); 1665ffd83dbSDimitry Andric It != End; ++It) { 1675ffd83dbSDimitry Andric IndexT Start = It.start(); 1685ffd83dbSDimitry Andric IndexT Stop = It.stop(); 1695ffd83dbSDimitry Andric SmallVector<IntervalT, 8> NonOverlappingParts; 1705ffd83dbSDimitry Andric getNonOverlappingParts(Start, Stop, Overlaps, NonOverlappingParts); 1715ffd83dbSDimitry Andric for (IntervalT AdditivePortion : NonOverlappingParts) 1725ffd83dbSDimitry Andric insert(AdditivePortion.first, AdditivePortion.second); 1735ffd83dbSDimitry Andric } 1745ffd83dbSDimitry Andric } 1755ffd83dbSDimitry Andric 1765ffd83dbSDimitry Andric /// Set intersection. 1775ffd83dbSDimitry Andric void operator&=(const ThisT &RHS) { 1785ffd83dbSDimitry Andric // Get the overlaps between the two interval maps (i.e. the intersection). 1795ffd83dbSDimitry Andric SmallVector<IntervalT, 8> Overlaps; 1805ffd83dbSDimitry Andric getOverlaps(RHS, Overlaps); 1815ffd83dbSDimitry Andric // Rebuild the interval map, including only the overlaps. 1825ffd83dbSDimitry Andric clear(); 1835ffd83dbSDimitry Andric for (IntervalT Overlap : Overlaps) 1845ffd83dbSDimitry Andric insert(Overlap.first, Overlap.second); 1855ffd83dbSDimitry Andric } 1865ffd83dbSDimitry Andric 1875ffd83dbSDimitry Andric /// Reset all bits present in \p Other. intersectWithComplement(const ThisT & Other)1885ffd83dbSDimitry Andric void intersectWithComplement(const ThisT &Other) { 1895ffd83dbSDimitry Andric SmallVector<IntervalT, 8> Overlaps; 1905ffd83dbSDimitry Andric if (!getOverlaps(Other, Overlaps)) { 1915ffd83dbSDimitry Andric // If there is no overlap with Other, the intersection is empty. 1925ffd83dbSDimitry Andric return; 1935ffd83dbSDimitry Andric } 1945ffd83dbSDimitry Andric 1955ffd83dbSDimitry Andric // Delete the overlapping intervals. Split up intervals that only partially 1965ffd83dbSDimitry Andric // intersect an overlap. 1975ffd83dbSDimitry Andric for (IntervalT Overlap : Overlaps) { 1985ffd83dbSDimitry Andric IndexT OlapStart, OlapStop; 1995ffd83dbSDimitry Andric std::tie(OlapStart, OlapStop) = Overlap; 2005ffd83dbSDimitry Andric 2015ffd83dbSDimitry Andric auto It = Intervals.find(OlapStart); 2025ffd83dbSDimitry Andric IndexT CurrStart = It.start(); 2035ffd83dbSDimitry Andric IndexT CurrStop = It.stop(); 2045ffd83dbSDimitry Andric assert(CurrStart <= OlapStart && OlapStop <= CurrStop && 2055ffd83dbSDimitry Andric "Expected some intersection!"); 2065ffd83dbSDimitry Andric 2075ffd83dbSDimitry Andric // Split the overlap interval into up to two parts: one from [CurrStart, 2085ffd83dbSDimitry Andric // OlapStart-1] and another from [OlapStop+1, CurrStop]. If OlapStart is 2095ffd83dbSDimitry Andric // equal to CurrStart, the first split interval is unnecessary. Ditto for 2105ffd83dbSDimitry Andric // when OlapStop is equal to CurrStop, we omit the second split interval. 2115ffd83dbSDimitry Andric It.erase(); 2125ffd83dbSDimitry Andric if (CurrStart < OlapStart) 2135ffd83dbSDimitry Andric insert(CurrStart, OlapStart - 1); 2145ffd83dbSDimitry Andric if (OlapStop < CurrStop) 2155ffd83dbSDimitry Andric insert(OlapStop + 1, CurrStop); 2165ffd83dbSDimitry Andric } 2175ffd83dbSDimitry Andric } 2185ffd83dbSDimitry Andric 2195ffd83dbSDimitry Andric bool operator==(const ThisT &RHS) const { 2205ffd83dbSDimitry Andric // We cannot just use std::equal because it checks the dereferenced values 2215ffd83dbSDimitry Andric // of an iterator pair for equality, not the iterators themselves. In our 2225ffd83dbSDimitry Andric // case that results in comparison of the (unused) IntervalMap values. 2235ffd83dbSDimitry Andric auto ItL = Intervals.begin(); 2245ffd83dbSDimitry Andric auto ItR = RHS.Intervals.begin(); 2255ffd83dbSDimitry Andric while (ItL != Intervals.end() && ItR != RHS.Intervals.end() && 2265ffd83dbSDimitry Andric ItL.start() == ItR.start() && ItL.stop() == ItR.stop()) { 2275ffd83dbSDimitry Andric ++ItL; 2285ffd83dbSDimitry Andric ++ItR; 2295ffd83dbSDimitry Andric } 2305ffd83dbSDimitry Andric return ItL == Intervals.end() && ItR == RHS.Intervals.end(); 2315ffd83dbSDimitry Andric } 2325ffd83dbSDimitry Andric 2335ffd83dbSDimitry Andric bool operator!=(const ThisT &RHS) const { return !operator==(RHS); } 2345ffd83dbSDimitry Andric 235fe6060f1SDimitry Andric class const_iterator { 2365ffd83dbSDimitry Andric friend class CoalescingBitVector; 2375ffd83dbSDimitry Andric 238fe6060f1SDimitry Andric public: 239fe6060f1SDimitry Andric using iterator_category = std::forward_iterator_tag; 240fe6060f1SDimitry Andric using value_type = IndexT; 241fe6060f1SDimitry Andric using difference_type = std::ptrdiff_t; 242fe6060f1SDimitry Andric using pointer = value_type *; 243fe6060f1SDimitry Andric using reference = value_type &; 244fe6060f1SDimitry Andric 245fe6060f1SDimitry Andric private: 2465ffd83dbSDimitry Andric // For performance reasons, make the offset at the end different than the 2475ffd83dbSDimitry Andric // one used in \ref begin, to optimize the common `It == end()` pattern. 2485ffd83dbSDimitry Andric static constexpr unsigned kIteratorAtTheEndOffset = ~0u; 2495ffd83dbSDimitry Andric 2505ffd83dbSDimitry Andric UnderlyingIterator MapIterator; 2515ffd83dbSDimitry Andric unsigned OffsetIntoMapIterator = 0; 2525ffd83dbSDimitry Andric 2535ffd83dbSDimitry Andric // Querying the start/stop of an IntervalMap iterator can be very expensive. 2545ffd83dbSDimitry Andric // Cache these values for performance reasons. 2555ffd83dbSDimitry Andric IndexT CachedStart = IndexT(); 2565ffd83dbSDimitry Andric IndexT CachedStop = IndexT(); 2575ffd83dbSDimitry Andric setToEnd()2585ffd83dbSDimitry Andric void setToEnd() { 2595ffd83dbSDimitry Andric OffsetIntoMapIterator = kIteratorAtTheEndOffset; 2605ffd83dbSDimitry Andric CachedStart = IndexT(); 2615ffd83dbSDimitry Andric CachedStop = IndexT(); 2625ffd83dbSDimitry Andric } 2635ffd83dbSDimitry Andric 2645ffd83dbSDimitry Andric /// MapIterator has just changed, reset the cached state to point to the 2655ffd83dbSDimitry Andric /// start of the new underlying iterator. resetCache()2665ffd83dbSDimitry Andric void resetCache() { 2675ffd83dbSDimitry Andric if (MapIterator.valid()) { 2685ffd83dbSDimitry Andric OffsetIntoMapIterator = 0; 2695ffd83dbSDimitry Andric CachedStart = MapIterator.start(); 2705ffd83dbSDimitry Andric CachedStop = MapIterator.stop(); 2715ffd83dbSDimitry Andric } else { 2725ffd83dbSDimitry Andric setToEnd(); 2735ffd83dbSDimitry Andric } 2745ffd83dbSDimitry Andric } 2755ffd83dbSDimitry Andric 2765ffd83dbSDimitry Andric /// Advance the iterator to \p Index, if it is contained within the current 2775ffd83dbSDimitry Andric /// interval. The public-facing method which supports advancing past the 2785ffd83dbSDimitry Andric /// current interval is \ref advanceToLowerBound. advanceTo(IndexT Index)2795ffd83dbSDimitry Andric void advanceTo(IndexT Index) { 2805ffd83dbSDimitry Andric assert(Index <= CachedStop && "Cannot advance to OOB index"); 2815ffd83dbSDimitry Andric if (Index < CachedStart) 2825ffd83dbSDimitry Andric // We're already past this index. 2835ffd83dbSDimitry Andric return; 2845ffd83dbSDimitry Andric OffsetIntoMapIterator = Index - CachedStart; 2855ffd83dbSDimitry Andric } 2865ffd83dbSDimitry Andric const_iterator(UnderlyingIterator MapIt)2875ffd83dbSDimitry Andric const_iterator(UnderlyingIterator MapIt) : MapIterator(MapIt) { 2885ffd83dbSDimitry Andric resetCache(); 2895ffd83dbSDimitry Andric } 2905ffd83dbSDimitry Andric 2915ffd83dbSDimitry Andric public: const_iterator()2925ffd83dbSDimitry Andric const_iterator() { setToEnd(); } 2935ffd83dbSDimitry Andric 2945ffd83dbSDimitry Andric bool operator==(const const_iterator &RHS) const { 2955ffd83dbSDimitry Andric // Do /not/ compare MapIterator for equality, as this is very expensive. 2965ffd83dbSDimitry Andric // The cached start/stop values make that check unnecessary. 2975ffd83dbSDimitry Andric return std::tie(OffsetIntoMapIterator, CachedStart, CachedStop) == 2985ffd83dbSDimitry Andric std::tie(RHS.OffsetIntoMapIterator, RHS.CachedStart, 2995ffd83dbSDimitry Andric RHS.CachedStop); 3005ffd83dbSDimitry Andric } 3015ffd83dbSDimitry Andric 3025ffd83dbSDimitry Andric bool operator!=(const const_iterator &RHS) const { 3035ffd83dbSDimitry Andric return !operator==(RHS); 3045ffd83dbSDimitry Andric } 3055ffd83dbSDimitry Andric 3065ffd83dbSDimitry Andric IndexT operator*() const { return CachedStart + OffsetIntoMapIterator; } 3075ffd83dbSDimitry Andric 3085ffd83dbSDimitry Andric const_iterator &operator++() { // Pre-increment (++It). 3095ffd83dbSDimitry Andric if (CachedStart + OffsetIntoMapIterator < CachedStop) { 3105ffd83dbSDimitry Andric // Keep going within the current interval. 3115ffd83dbSDimitry Andric ++OffsetIntoMapIterator; 3125ffd83dbSDimitry Andric } else { 3135ffd83dbSDimitry Andric // We reached the end of the current interval: advance. 3145ffd83dbSDimitry Andric ++MapIterator; 3155ffd83dbSDimitry Andric resetCache(); 3165ffd83dbSDimitry Andric } 3175ffd83dbSDimitry Andric return *this; 3185ffd83dbSDimitry Andric } 3195ffd83dbSDimitry Andric 3205ffd83dbSDimitry Andric const_iterator operator++(int) { // Post-increment (It++). 3215ffd83dbSDimitry Andric const_iterator tmp = *this; 3225ffd83dbSDimitry Andric operator++(); 3235ffd83dbSDimitry Andric return tmp; 3245ffd83dbSDimitry Andric } 3255ffd83dbSDimitry Andric 3265ffd83dbSDimitry Andric /// Advance the iterator to the first set bit AT, OR AFTER, \p Index. If 3275ffd83dbSDimitry Andric /// no such set bit exists, advance to end(). This is like std::lower_bound. 3285ffd83dbSDimitry Andric /// This is useful if \p Index is close to the current iterator position. 3295ffd83dbSDimitry Andric /// However, unlike \ref find(), this has worst-case O(n) performance. advanceToLowerBound(IndexT Index)3305ffd83dbSDimitry Andric void advanceToLowerBound(IndexT Index) { 3315ffd83dbSDimitry Andric if (OffsetIntoMapIterator == kIteratorAtTheEndOffset) 3325ffd83dbSDimitry Andric return; 3335ffd83dbSDimitry Andric 3345ffd83dbSDimitry Andric // Advance to the first interval containing (or past) Index, or to end(). 3355ffd83dbSDimitry Andric while (Index > CachedStop) { 3365ffd83dbSDimitry Andric ++MapIterator; 3375ffd83dbSDimitry Andric resetCache(); 3385ffd83dbSDimitry Andric if (OffsetIntoMapIterator == kIteratorAtTheEndOffset) 3395ffd83dbSDimitry Andric return; 3405ffd83dbSDimitry Andric } 3415ffd83dbSDimitry Andric 3425ffd83dbSDimitry Andric advanceTo(Index); 3435ffd83dbSDimitry Andric } 3445ffd83dbSDimitry Andric }; 3455ffd83dbSDimitry Andric begin()3465ffd83dbSDimitry Andric const_iterator begin() const { return const_iterator(Intervals.begin()); } 3475ffd83dbSDimitry Andric end()3485ffd83dbSDimitry Andric const_iterator end() const { return const_iterator(); } 3495ffd83dbSDimitry Andric 3505ffd83dbSDimitry Andric /// Return an iterator pointing to the first set bit AT, OR AFTER, \p Index. 3515ffd83dbSDimitry Andric /// If no such set bit exists, return end(). This is like std::lower_bound. 3525ffd83dbSDimitry Andric /// This has worst-case logarithmic performance (roughly O(log(gaps between 3535ffd83dbSDimitry Andric /// contiguous ranges))). find(IndexT Index)3545ffd83dbSDimitry Andric const_iterator find(IndexT Index) const { 3555ffd83dbSDimitry Andric auto UnderlyingIt = Intervals.find(Index); 3565ffd83dbSDimitry Andric if (UnderlyingIt == Intervals.end()) 3575ffd83dbSDimitry Andric return end(); 3585ffd83dbSDimitry Andric auto It = const_iterator(UnderlyingIt); 3595ffd83dbSDimitry Andric It.advanceTo(Index); 3605ffd83dbSDimitry Andric return It; 3615ffd83dbSDimitry Andric } 3625ffd83dbSDimitry Andric 3635ffd83dbSDimitry Andric /// Return a range iterator which iterates over all of the set bits in the 3645ffd83dbSDimitry Andric /// half-open range [Start, End). half_open_range(IndexT Start,IndexT End)3655ffd83dbSDimitry Andric iterator_range<const_iterator> half_open_range(IndexT Start, 3665ffd83dbSDimitry Andric IndexT End) const { 3675ffd83dbSDimitry Andric assert(Start < End && "Not a valid range"); 3685ffd83dbSDimitry Andric auto StartIt = find(Start); 3695ffd83dbSDimitry Andric if (StartIt == end() || *StartIt >= End) 3705ffd83dbSDimitry Andric return {end(), end()}; 3715ffd83dbSDimitry Andric auto EndIt = StartIt; 3725ffd83dbSDimitry Andric EndIt.advanceToLowerBound(End); 3735ffd83dbSDimitry Andric return {StartIt, EndIt}; 3745ffd83dbSDimitry Andric } 3755ffd83dbSDimitry Andric print(raw_ostream & OS)3765ffd83dbSDimitry Andric void print(raw_ostream &OS) const { 3775ffd83dbSDimitry Andric OS << "{"; 3785ffd83dbSDimitry Andric for (auto It = Intervals.begin(), End = Intervals.end(); It != End; 3795ffd83dbSDimitry Andric ++It) { 3805ffd83dbSDimitry Andric OS << "[" << It.start(); 3815ffd83dbSDimitry Andric if (It.start() != It.stop()) 3825ffd83dbSDimitry Andric OS << ", " << It.stop(); 3835ffd83dbSDimitry Andric OS << "]"; 3845ffd83dbSDimitry Andric } 3855ffd83dbSDimitry Andric OS << "}"; 3865ffd83dbSDimitry Andric } 3875ffd83dbSDimitry Andric 3885ffd83dbSDimitry Andric #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) dump()3895ffd83dbSDimitry Andric LLVM_DUMP_METHOD void dump() const { 3905ffd83dbSDimitry Andric // LLDB swallows the first line of output after callling dump(). Add 3915ffd83dbSDimitry Andric // newlines before/after the braces to work around this. 3925ffd83dbSDimitry Andric dbgs() << "\n"; 3935ffd83dbSDimitry Andric print(dbgs()); 3945ffd83dbSDimitry Andric dbgs() << "\n"; 3955ffd83dbSDimitry Andric } 3965ffd83dbSDimitry Andric #endif 3975ffd83dbSDimitry Andric 3985ffd83dbSDimitry Andric private: insert(IndexT Start,IndexT End)3995ffd83dbSDimitry Andric void insert(IndexT Start, IndexT End) { Intervals.insert(Start, End, 0); } 4005ffd83dbSDimitry Andric 4015ffd83dbSDimitry Andric /// Record the overlaps between \p this and \p Other in \p Overlaps. Return 4025ffd83dbSDimitry Andric /// true if there is any overlap. getOverlaps(const ThisT & Other,SmallVectorImpl<IntervalT> & Overlaps)4035ffd83dbSDimitry Andric bool getOverlaps(const ThisT &Other, 4045ffd83dbSDimitry Andric SmallVectorImpl<IntervalT> &Overlaps) const { 4055ffd83dbSDimitry Andric for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals); 4065ffd83dbSDimitry Andric I.valid(); ++I) 4075ffd83dbSDimitry Andric Overlaps.emplace_back(I.start(), I.stop()); 4085ffd83dbSDimitry Andric assert(llvm::is_sorted(Overlaps, 4095ffd83dbSDimitry Andric [](IntervalT LHS, IntervalT RHS) { 4105ffd83dbSDimitry Andric return LHS.second < RHS.first; 4115ffd83dbSDimitry Andric }) && 4125ffd83dbSDimitry Andric "Overlaps must be sorted"); 4135ffd83dbSDimitry Andric return !Overlaps.empty(); 4145ffd83dbSDimitry Andric } 4155ffd83dbSDimitry Andric 4165ffd83dbSDimitry Andric /// Given the set of overlaps between this and some other bitvector, and an 4175ffd83dbSDimitry Andric /// interval [Start, Stop] from that bitvector, determine the portions of the 4185ffd83dbSDimitry Andric /// interval which do not overlap with this. getNonOverlappingParts(IndexT Start,IndexT Stop,const SmallVectorImpl<IntervalT> & Overlaps,SmallVectorImpl<IntervalT> & NonOverlappingParts)4195ffd83dbSDimitry Andric void getNonOverlappingParts(IndexT Start, IndexT Stop, 4205ffd83dbSDimitry Andric const SmallVectorImpl<IntervalT> &Overlaps, 4215ffd83dbSDimitry Andric SmallVectorImpl<IntervalT> &NonOverlappingParts) { 4225ffd83dbSDimitry Andric IndexT NextUncoveredBit = Start; 4235ffd83dbSDimitry Andric for (IntervalT Overlap : Overlaps) { 4245ffd83dbSDimitry Andric IndexT OlapStart, OlapStop; 4255ffd83dbSDimitry Andric std::tie(OlapStart, OlapStop) = Overlap; 4265ffd83dbSDimitry Andric 4275ffd83dbSDimitry Andric // [Start;Stop] and [OlapStart;OlapStop] overlap iff OlapStart <= Stop 4285ffd83dbSDimitry Andric // and Start <= OlapStop. 4295ffd83dbSDimitry Andric bool DoesOverlap = OlapStart <= Stop && Start <= OlapStop; 4305ffd83dbSDimitry Andric if (!DoesOverlap) 4315ffd83dbSDimitry Andric continue; 4325ffd83dbSDimitry Andric 4335ffd83dbSDimitry Andric // Cover the range [NextUncoveredBit, OlapStart). This puts the start of 4345ffd83dbSDimitry Andric // the next uncovered range at OlapStop+1. 4355ffd83dbSDimitry Andric if (NextUncoveredBit < OlapStart) 4365ffd83dbSDimitry Andric NonOverlappingParts.emplace_back(NextUncoveredBit, OlapStart - 1); 4375ffd83dbSDimitry Andric NextUncoveredBit = OlapStop + 1; 4385ffd83dbSDimitry Andric if (NextUncoveredBit > Stop) 4395ffd83dbSDimitry Andric break; 4405ffd83dbSDimitry Andric } 4415ffd83dbSDimitry Andric if (NextUncoveredBit <= Stop) 4425ffd83dbSDimitry Andric NonOverlappingParts.emplace_back(NextUncoveredBit, Stop); 4435ffd83dbSDimitry Andric } 4445ffd83dbSDimitry Andric 4455ffd83dbSDimitry Andric Allocator *Alloc; 4465ffd83dbSDimitry Andric MapT Intervals; 4475ffd83dbSDimitry Andric }; 4485ffd83dbSDimitry Andric 4495ffd83dbSDimitry Andric } // namespace llvm 4505ffd83dbSDimitry Andric 4515ffd83dbSDimitry Andric #endif // LLVM_ADT_COALESCINGBITVECTOR_H 452