Go to the documentation of this file.
15 #ifndef LLVM_ADT_COALESCINGBITVECTOR_H
16 #define LLVM_ADT_COALESCINGBITVECTOR_H
25 #include <initializer_list>
39 static_assert(std::is_unsigned<IndexT>::value,
40 "Index must be an unsigned integer.");
49 using IntervalT = std::pair<IndexT, IndexT>;
57 : Alloc(&Alloc), Intervals(Alloc) {}
63 : Alloc(
Other.Alloc), Intervals(*
Other.Alloc) {
87 for (
auto It = Intervals.
begin(), End = Intervals.
end(); It != End; ++It)
88 Bits += 1 + It.stop() - It.start();
98 assert(!
test(
Index) &&
"Setting already-set bits not supported/efficient, "
99 "IntervalMap will assert");
108 for (
auto It =
Other.Intervals.begin(), End =
Other.Intervals.end();
110 insert(It.start(), It.stop());
114 void set(std::initializer_list<IndexT> Indices) {
115 for (IndexT
Index : Indices)
122 if (It == Intervals.
end())
124 assert(It.stop() >=
Index &&
"Interval must end after Index");
125 return It.start() <=
Index;
137 if (It == Intervals.
end())
144 IndexT Start = It.start();
148 IndexT Stop = It.stop();
149 assert(
Index <= Stop &&
"Wrong interval for index");
152 insert(Start,
Index - 1);
154 insert(
Index + 1, Stop);
162 getOverlaps(
RHS, Overlaps);
165 for (
auto It =
RHS.Intervals.begin(), End =
RHS.Intervals.end();
167 IndexT Start = It.start();
168 IndexT Stop = It.stop();
170 getNonOverlappingParts(Start, Stop, Overlaps, NonOverlappingParts);
171 for (IntervalT AdditivePortion : NonOverlappingParts)
172 insert(AdditivePortion.first, AdditivePortion.second);
180 getOverlaps(
RHS, Overlaps);
183 for (IntervalT Overlap : Overlaps)
184 insert(Overlap.first, Overlap.second);
190 if (!getOverlaps(
Other, Overlaps)) {
197 for (IntervalT Overlap : Overlaps) {
198 IndexT OlapStart, OlapStop;
199 std::tie(OlapStart, OlapStop) = Overlap;
201 auto It = Intervals.
find(OlapStart);
202 IndexT CurrStart = It.start();
203 IndexT CurrStop = It.stop();
204 assert(CurrStart <= OlapStart && OlapStop <= CurrStop &&
205 "Expected some intersection!");
212 if (CurrStart < OlapStart)
213 insert(CurrStart, OlapStart - 1);
214 if (OlapStop < CurrStop)
215 insert(OlapStop + 1, CurrStop);
223 auto ItL = Intervals.
begin();
224 auto ItR =
RHS.Intervals.begin();
225 while (ItL != Intervals.
end() && ItR !=
RHS.Intervals.end() &&
226 ItL.start() == ItR.start() && ItL.stop() == ItR.stop()) {
230 return ItL == Intervals.
end() && ItR ==
RHS.Intervals.end();
248 static constexpr
unsigned kIteratorAtTheEndOffset = ~0u;
250 UnderlyingIterator MapIterator;
251 unsigned OffsetIntoMapIterator = 0;
255 IndexT CachedStart = IndexT();
256 IndexT CachedStop = IndexT();
259 OffsetIntoMapIterator = kIteratorAtTheEndOffset;
260 CachedStart = IndexT();
261 CachedStop = IndexT();
267 if (MapIterator.valid()) {
268 OffsetIntoMapIterator = 0;
269 CachedStart = MapIterator.start();
270 CachedStop = MapIterator.stop();
280 assert(
Index <= CachedStop &&
"Cannot advance to OOB index");
281 if (
Index < CachedStart)
284 OffsetIntoMapIterator =
Index - CachedStart;
297 return std::tie(OffsetIntoMapIterator, CachedStart, CachedStop) ==
298 std::tie(
RHS.OffsetIntoMapIterator,
RHS.CachedStart,
306 IndexT
operator*()
const {
return CachedStart + OffsetIntoMapIterator; }
309 if (CachedStart + OffsetIntoMapIterator < CachedStop) {
311 ++OffsetIntoMapIterator;
331 if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
335 while (
Index > CachedStop) {
338 if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
355 auto UnderlyingIt = Intervals.
find(
Index);
356 if (UnderlyingIt == Intervals.
end())
367 assert(Start < End &&
"Not a valid range");
368 auto StartIt =
find(Start);
369 if (StartIt ==
end() || *StartIt >= End)
371 auto EndIt = StartIt;
373 return {StartIt, EndIt};
378 for (
auto It = Intervals.
begin(), End = Intervals.
end(); It != End;
380 OS <<
"[" << It.start();
381 if (It.start() != It.stop())
382 OS <<
", " << It.stop();
388 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
399 void insert(IndexT Start, IndexT End) { Intervals.
insert(Start, End, 0); }
403 bool getOverlaps(
const ThisT &
Other,
404 SmallVectorImpl<IntervalT> &Overlaps)
const {
405 for (IntervalMapOverlaps<MapT, MapT>
I(Intervals,
Other.Intervals);
407 Overlaps.emplace_back(
I.start(),
I.stop());
409 [](IntervalT
LHS, IntervalT
RHS) {
410 return LHS.second <
RHS.first;
412 "Overlaps must be sorted");
413 return !Overlaps.empty();
419 void getNonOverlappingParts(IndexT Start, IndexT Stop,
420 const SmallVectorImpl<IntervalT> &Overlaps,
421 SmallVectorImpl<IntervalT> &NonOverlappingParts) {
422 IndexT NextUncoveredBit = Start;
423 for (IntervalT Overlap : Overlaps) {
424 IndexT OlapStart, OlapStop;
425 std::tie(OlapStart, OlapStop) = Overlap;
429 bool DoesOverlap = OlapStart <= Stop && Start <= OlapStop;
435 if (NextUncoveredBit < OlapStart)
436 NonOverlappingParts.emplace_back(NextUncoveredBit, OlapStart - 1);
437 NextUncoveredBit = OlapStop + 1;
438 if (NextUncoveredBit > Stop)
441 if (NextUncoveredBit <= Stop)
442 NonOverlappingParts.emplace_back(NextUncoveredBit, Stop);
451 #endif // LLVM_ADT_COALESCINGBITVECTOR_H
A bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals.
void set(std::initializer_list< IndexT > Indices)
Set the bits at Indices. Used for testing, primarily.
const_iterator & operator++()
void clear()
clear - Remove all entries.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This is an optimization pass for GlobalISel generic memory operations.
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
void set(const ThisT &Other)
Set the bits set in Other.
CoalescingBitVector(const ThisT &Other)
void print(raw_ostream &OS) const
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
std::ptrdiff_t difference_type
const_iterator end() const
bool operator!=(const const_iterator &RHS) const
void operator&=(const ThisT &RHS)
Set intersection.
bool empty() const
empty - Return true when no intervals are mapped.
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
void set(IndexT Index)
Set the bit at Index.
bool operator!=(const ThisT &RHS) const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
const_iterator find(IndexT Index) const
Return an iterator pointing to the first set bit AT, OR AFTER, Index.
bool operator==(const const_iterator &RHS) const
ThisT & operator=(const ThisT &Other)
const_iterator begin() const
void test_and_set(IndexT Index)
Set the bit at Index. Supports setting an already-set bit.
This class implements an extremely fast bulk output stream that can only output to a stream.
void intersectWithComplement(const ThisT &Other)
Reset all bits present in Other.
typename Sizer::Allocator Allocator
static void advanceTo(StringRef &Str, StringRef::iterator Pos)
void advanceToLowerBound(IndexT Index)
Advance the iterator to the first set bit AT, OR AFTER, Index.
bool test(IndexT Index) const
Check whether the bit at Index is set.
LLVM_DUMP_METHOD void dump() const
bool operator==(const ThisT &RHS) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end().
typename MapT::Allocator Allocator
void reset(IndexT Index)
Reset the bit at Index. Supports resetting an already-unset bit.
const_iterator end() const
std::forward_iterator_tag iterator_category
CoalescingBitVector(Allocator &Alloc)
Construct by passing in a CoalescingBitVector<IndexT>::Allocator reference.
const_iterator operator++(int)
void operator|=(const ThisT &RHS)
Set union.
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,...
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...
void clear()
Clear all the bits.
unsigned count() const
Count the number of set bits.
std::optional< std::vector< StOtherPiece > > Other
const_iterator begin() const
A range adaptor for a pair of iterators.
friend class const_iterator
bool empty() const
Check whether no bits are set.