LLVM 22.0.0git
CoalescingBitVector.h
Go to the documentation of this file.
1//===- llvm/ADT/CoalescingBitVector.h - A coalescing bitvector --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// A bitvector that uses an IntervalMap to coalesce adjacent elements
11/// into intervals.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_COALESCINGBITVECTOR_H
16#define LLVM_ADT_COALESCINGBITVECTOR_H
17
19#include "llvm/ADT/STLExtras.h"
22#include "llvm/Support/Debug.h"
24
25#include <initializer_list>
26
27namespace llvm {
28
29/// A bitvector that, under the hood, relies on an IntervalMap to coalesce
30/// elements into intervals. Good for representing sets which predominantly
31/// contain contiguous ranges. Bad for representing sets with lots of gaps
32/// between elements.
33///
34/// Compared to SparseBitVector, CoalescingBitVector offers more predictable
35/// performance for non-sequential find() operations.
36///
37/// \tparam IndexT - The type of the index into the bitvector.
38template <typename IndexT> class CoalescingBitVector {
39 static_assert(std::is_unsigned<IndexT>::value,
40 "Index must be an unsigned integer.");
41
42 using ThisT = CoalescingBitVector<IndexT>;
43
44 /// An interval map for closed integer ranges. The mapped values are unused.
45 using MapT = IntervalMap<IndexT, char>;
46
47 using UnderlyingIterator = typename MapT::const_iterator;
48
49 using IntervalT = std::pair<IndexT, IndexT>;
50
51public:
52 using Allocator = typename MapT::Allocator;
53
54 /// Construct by passing in a CoalescingBitVector<IndexT>::Allocator
55 /// reference.
57 : Alloc(&Alloc), Intervals(Alloc) {}
58
59 /// \name Copy/move constructors and assignment operators.
60 /// @{
61
63 : Alloc(Other.Alloc), Intervals(*Other.Alloc) {
64 set(Other);
65 }
66
67 ThisT &operator=(const ThisT &Other) {
68 clear();
69 set(Other);
70 return *this;
71 }
72
73 CoalescingBitVector(ThisT &&Other) = delete;
74 ThisT &operator=(ThisT &&Other) = delete;
75
76 /// @}
77
78 /// Clear all the bits.
79 void clear() { Intervals.clear(); }
80
81 /// Check whether no bits are set.
82 bool empty() const { return Intervals.empty(); }
83
84 /// Count the number of set bits.
85 unsigned count() const {
86 unsigned Bits = 0;
87 for (auto It = Intervals.begin(), End = Intervals.end(); It != End; ++It)
88 Bits += 1 + It.stop() - It.start();
89 return Bits;
90 }
91
92 /// Set the bit at \p Index.
93 ///
94 /// This method does /not/ support setting a bit that has already been set,
95 /// for efficiency reasons. If possible, restructure your code to not set the
96 /// same bit multiple times, or use \ref test_and_set.
97 void set(IndexT Index) {
98 assert(!test(Index) && "Setting already-set bits not supported/efficient, "
99 "IntervalMap will assert");
100 insert(Index, Index);
101 }
102
103 /// Set the bits set in \p Other.
104 ///
105 /// This method does /not/ support setting already-set bits, see \ref set
106 /// for the rationale. For a safe set union operation, use \ref operator|=.
107 void set(const ThisT &Other) {
108 for (auto It = Other.Intervals.begin(), End = Other.Intervals.end();
109 It != End; ++It)
110 insert(It.start(), It.stop());
111 }
112
113 /// Set the bits at \p Indices. Used for testing, primarily.
114 void set(std::initializer_list<IndexT> Indices) {
115 for (IndexT Index : Indices)
116 set(Index);
117 }
118
119 /// Check whether the bit at \p Index is set.
120 bool test(IndexT Index) const {
121 const auto It = Intervals.find(Index);
122 if (It == Intervals.end())
123 return false;
124 assert(It.stop() >= Index && "Interval must end after Index");
125 return It.start() <= Index;
126 }
127
128 /// Set the bit at \p Index. Supports setting an already-set bit.
129 void test_and_set(IndexT Index) {
130 if (!test(Index))
131 set(Index);
132 }
133
134 /// Reset the bit at \p Index. Supports resetting an already-unset bit.
135 void reset(IndexT Index) {
136 auto It = Intervals.find(Index);
137 if (It == Intervals.end())
138 return;
139
140 // Split the interval containing Index into up to two parts: one from
141 // [Start, Index-1] and another from [Index+1, Stop]. If Index is equal to
142 // either Start or Stop, we create one new interval. If Index is equal to
143 // both Start and Stop, we simply erase the existing interval.
144 IndexT Start = It.start();
145 if (Index < Start)
146 // The index was not set.
147 return;
148 IndexT Stop = It.stop();
149 assert(Index <= Stop && "Wrong interval for index");
150 It.erase();
151 if (Start < Index)
152 insert(Start, Index - 1);
153 if (Index < Stop)
154 insert(Index + 1, Stop);
155 }
156
157 /// Set union. If \p RHS is guaranteed to not overlap with this, \ref set may
158 /// be a faster alternative.
159 void operator|=(const ThisT &RHS) {
160 // Get the overlaps between the two interval maps.
162 getOverlaps(RHS, Overlaps);
163
164 // Insert the non-overlapping parts of all the intervals from RHS.
165 for (auto It = RHS.Intervals.begin(), End = RHS.Intervals.end();
166 It != End; ++It) {
167 IndexT Start = It.start();
168 IndexT Stop = It.stop();
169 SmallVector<IntervalT, 8> NonOverlappingParts;
170 getNonOverlappingParts(Start, Stop, Overlaps, NonOverlappingParts);
171 for (IntervalT AdditivePortion : NonOverlappingParts)
172 insert(AdditivePortion.first, AdditivePortion.second);
173 }
174 }
175
176 /// Set intersection.
177 void operator&=(const ThisT &RHS) {
178 // Get the overlaps between the two interval maps (i.e. the intersection).
180 getOverlaps(RHS, Overlaps);
181 // Rebuild the interval map, including only the overlaps.
182 clear();
183 for (IntervalT Overlap : Overlaps)
184 insert(Overlap.first, Overlap.second);
185 }
186
187 /// Reset all bits present in \p Other.
188 void intersectWithComplement(const ThisT &Other) {
190 if (!getOverlaps(Other, Overlaps)) {
191 // If there is no overlap with Other, the intersection is empty.
192 return;
193 }
194
195 // Delete the overlapping intervals. Split up intervals that only partially
196 // intersect an overlap.
197 for (auto [OlapStart, OlapStop] : Overlaps) {
198 auto It = Intervals.find(OlapStart);
199 IndexT CurrStart = It.start();
200 IndexT CurrStop = It.stop();
201 assert(CurrStart <= OlapStart && OlapStop <= CurrStop &&
202 "Expected some intersection!");
203
204 // Split the overlap interval into up to two parts: one from [CurrStart,
205 // OlapStart-1] and another from [OlapStop+1, CurrStop]. If OlapStart is
206 // equal to CurrStart, the first split interval is unnecessary. Ditto for
207 // when OlapStop is equal to CurrStop, we omit the second split interval.
208 It.erase();
209 if (CurrStart < OlapStart)
210 insert(CurrStart, OlapStart - 1);
211 if (OlapStop < CurrStop)
212 insert(OlapStop + 1, CurrStop);
213 }
214 }
215
216 bool operator==(const ThisT &RHS) const {
217 // We cannot just use std::equal because it checks the dereferenced values
218 // of an iterator pair for equality, not the iterators themselves. In our
219 // case that results in comparison of the (unused) IntervalMap values.
220 auto ItL = Intervals.begin();
221 auto ItR = RHS.Intervals.begin();
222 while (ItL != Intervals.end() && ItR != RHS.Intervals.end() &&
223 ItL.start() == ItR.start() && ItL.stop() == ItR.stop()) {
224 ++ItL;
225 ++ItR;
226 }
227 return ItL == Intervals.end() && ItR == RHS.Intervals.end();
228 }
229
230 bool operator!=(const ThisT &RHS) const { return !operator==(RHS); }
231
232 class const_iterator {
234
235 public:
236 using iterator_category = std::forward_iterator_tag;
237 using value_type = IndexT;
238 using difference_type = std::ptrdiff_t;
241
242 private:
243 // For performance reasons, make the offset at the end different than the
244 // one used in \ref begin, to optimize the common `It == end()` pattern.
245 static constexpr unsigned kIteratorAtTheEndOffset = ~0u;
246
247 UnderlyingIterator MapIterator;
248 unsigned OffsetIntoMapIterator = 0;
249
250 // Querying the start/stop of an IntervalMap iterator can be very expensive.
251 // Cache these values for performance reasons.
252 IndexT CachedStart = IndexT();
253 IndexT CachedStop = IndexT();
254
255 void setToEnd() {
256 OffsetIntoMapIterator = kIteratorAtTheEndOffset;
257 CachedStart = IndexT();
258 CachedStop = IndexT();
259 }
260
261 /// MapIterator has just changed, reset the cached state to point to the
262 /// start of the new underlying iterator.
263 void resetCache() {
264 if (MapIterator.valid()) {
265 OffsetIntoMapIterator = 0;
266 CachedStart = MapIterator.start();
267 CachedStop = MapIterator.stop();
268 } else {
269 setToEnd();
270 }
271 }
272
273 /// Advance the iterator to \p Index, if it is contained within the current
274 /// interval. The public-facing method which supports advancing past the
275 /// current interval is \ref advanceToLowerBound.
276 void advanceTo(IndexT Index) {
277 assert(Index <= CachedStop && "Cannot advance to OOB index");
278 if (Index < CachedStart)
279 // We're already past this index.
280 return;
281 OffsetIntoMapIterator = Index - CachedStart;
282 }
283
284 const_iterator(UnderlyingIterator MapIt) : MapIterator(MapIt) {
285 resetCache();
286 }
287
288 public:
289 const_iterator() { setToEnd(); }
290
291 bool operator==(const const_iterator &RHS) const {
292 // Do /not/ compare MapIterator for equality, as this is very expensive.
293 // The cached start/stop values make that check unnecessary.
294 return std::tie(OffsetIntoMapIterator, CachedStart, CachedStop) ==
295 std::tie(RHS.OffsetIntoMapIterator, RHS.CachedStart,
296 RHS.CachedStop);
297 }
298
299 bool operator!=(const const_iterator &RHS) const {
300 return !operator==(RHS);
301 }
302
303 IndexT operator*() const { return CachedStart + OffsetIntoMapIterator; }
304
305 const_iterator &operator++() { // Pre-increment (++It).
306 if (CachedStart + OffsetIntoMapIterator < CachedStop) {
307 // Keep going within the current interval.
308 ++OffsetIntoMapIterator;
309 } else {
310 // We reached the end of the current interval: advance.
311 ++MapIterator;
312 resetCache();
313 }
314 return *this;
315 }
316
317 const_iterator operator++(int) { // Post-increment (It++).
318 const_iterator tmp = *this;
319 operator++();
320 return tmp;
321 }
322
323 /// Advance the iterator to the first set bit AT, OR AFTER, \p Index. If
324 /// no such set bit exists, advance to end(). This is like std::lower_bound.
325 /// This is useful if \p Index is close to the current iterator position.
326 /// However, unlike \ref find(), this has worst-case O(n) performance.
327 void advanceToLowerBound(IndexT Index) {
328 if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
329 return;
330
331 // Advance to the first interval containing (or past) Index, or to end().
332 while (Index > CachedStop) {
333 ++MapIterator;
334 resetCache();
335 if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
336 return;
337 }
338
339 advanceTo(Index);
340 }
341 };
342
343 const_iterator begin() const { return const_iterator(Intervals.begin()); }
344
345 const_iterator end() const { return const_iterator(); }
346
347 /// Return an iterator pointing to the first set bit AT, OR AFTER, \p Index.
348 /// If no such set bit exists, return end(). This is like std::lower_bound.
349 /// This has worst-case logarithmic performance (roughly O(log(gaps between
350 /// contiguous ranges))).
351 const_iterator find(IndexT Index) const {
352 auto UnderlyingIt = Intervals.find(Index);
353 if (UnderlyingIt == Intervals.end())
354 return end();
355 auto It = const_iterator(UnderlyingIt);
356 It.advanceTo(Index);
357 return It;
358 }
359
360 /// Return a range iterator which iterates over all of the set bits in the
361 /// half-open range [Start, End).
363 IndexT End) const {
364 assert(Start < End && "Not a valid range");
365 auto StartIt = find(Start);
366 if (StartIt == end() || *StartIt >= End)
367 return {end(), end()};
368 auto EndIt = StartIt;
369 EndIt.advanceToLowerBound(End);
370 return {StartIt, EndIt};
371 }
372
373 void print(raw_ostream &OS) const {
374 OS << "{";
375 for (auto It = Intervals.begin(), End = Intervals.end(); It != End;
376 ++It) {
377 OS << "[" << It.start();
378 if (It.start() != It.stop())
379 OS << ", " << It.stop();
380 OS << "]";
381 }
382 OS << "}";
383 }
384
385#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
386 LLVM_DUMP_METHOD void dump() const {
387 // LLDB swallows the first line of output after callling dump(). Add
388 // newlines before/after the braces to work around this.
389 dbgs() << "\n";
390 print(dbgs());
391 dbgs() << "\n";
392 }
393#endif
394
395private:
396 void insert(IndexT Start, IndexT End) { Intervals.insert(Start, End, 0); }
397
398 /// Record the overlaps between \p this and \p Other in \p Overlaps. Return
399 /// true if there is any overlap.
400 bool getOverlaps(const ThisT &Other,
401 SmallVectorImpl<IntervalT> &Overlaps) const {
402 for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals);
403 I.valid(); ++I)
404 Overlaps.emplace_back(I.start(), I.stop());
405 assert(llvm::is_sorted(Overlaps,
406 [](IntervalT LHS, IntervalT RHS) {
407 return LHS.second < RHS.first;
408 }) &&
409 "Overlaps must be sorted");
410 return !Overlaps.empty();
411 }
412
413 /// Given the set of overlaps between this and some other bitvector, and an
414 /// interval [Start, Stop] from that bitvector, determine the portions of the
415 /// interval which do not overlap with this.
416 void getNonOverlappingParts(IndexT Start, IndexT Stop,
417 const SmallVectorImpl<IntervalT> &Overlaps,
418 SmallVectorImpl<IntervalT> &NonOverlappingParts) {
419 IndexT NextUncoveredBit = Start;
420 for (auto [OlapStart, OlapStop] : Overlaps) {
421 // [Start;Stop] and [OlapStart;OlapStop] overlap iff OlapStart <= Stop
422 // and Start <= OlapStop.
423 bool DoesOverlap = OlapStart <= Stop && Start <= OlapStop;
424 if (!DoesOverlap)
425 continue;
426
427 // Cover the range [NextUncoveredBit, OlapStart). This puts the start of
428 // the next uncovered range at OlapStop+1.
429 if (NextUncoveredBit < OlapStart)
430 NonOverlappingParts.emplace_back(NextUncoveredBit, OlapStart - 1);
431 NextUncoveredBit = OlapStop + 1;
432 if (NextUncoveredBit > Stop)
433 break;
434 }
435 if (NextUncoveredBit <= Stop)
436 NonOverlappingParts.emplace_back(NextUncoveredBit, Stop);
437 }
438
439 Allocator *Alloc;
440 MapT Intervals;
441};
442
443} // namespace llvm
444
445#endif // LLVM_ADT_COALESCINGBITVECTOR_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:638
This file implements a coalescing interval map for small objects.
#define I(x, y, z)
Definition MD5.cpp:58
modulo schedule test
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
Value * RHS
Value * LHS
bool operator!=(const const_iterator &RHS) const
bool operator==(const const_iterator &RHS) const
void advanceToLowerBound(IndexT Index)
Advance the iterator to the first set bit AT, OR AFTER, Index.
void set(IndexT Index)
Set the bit at Index.
bool operator==(const ThisT &RHS) const
LLVM_DUMP_METHOD void dump() const
iterator_range< const_iterator > half_open_range(IndexT Start, IndexT End) const
Return a range iterator which iterates over all of the set bits in the half-open range [Start,...
void operator|=(const ThisT &RHS)
Set union.
CoalescingBitVector(ThisT &&Other)=delete
bool operator!=(const ThisT &RHS) const
const_iterator end() const
bool test(IndexT Index) const
Check whether the bit at Index is set.
typename MapT::Allocator Allocator
const_iterator begin() const
void operator&=(const ThisT &RHS)
Set intersection.
bool empty() const
Check whether no bits are set.
CoalescingBitVector(Allocator &Alloc)
Construct by passing in a CoalescingBitVector<IndexT>::Allocator reference.
void intersectWithComplement(const ThisT &Other)
Reset all bits present in Other.
const_iterator find(IndexT Index) const
Return an iterator pointing to the first set bit AT, OR AFTER, Index.
void print(raw_ostream &OS) const
ThisT & operator=(const ThisT &Other)
void clear()
Clear all the bits.
CoalescingBitVector(const ThisT &Other)
unsigned count() const
Count the number of set bits.
ThisT & operator=(ThisT &&Other)=delete
void set(const ThisT &Other)
Set the bits set in Other.
void test_and_set(IndexT Index)
Set the bit at Index. Supports setting an already-set bit.
void reset(IndexT Index)
Reset the bit at Index. Supports resetting an already-unset bit.
void set(std::initializer_list< IndexT > Indices)
Set the bits at Indices. Used for testing, primarily.
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
typename Sizer::Allocator Allocator
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
Definition STLExtras.h:1900
@ Other
Any other memory.
Definition ModRef.h:68