LLVM  15.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 
18 #include "llvm/ADT/IntervalMap.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/Support/Debug.h"
24 
25 #include <initializer_list>
26 
27 namespace 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.
38 template <typename IndexT> class CoalescingBitVector {
39  static_assert(std::is_unsigned<IndexT>::value,
40  "Index must be an unsigned integer.");
41 
43 
44  /// An interval map for closed integer ranges. The mapped values are unused.
46 
47  using UnderlyingIterator = typename MapT::const_iterator;
48 
49  using IntervalT = std::pair<IndexT, IndexT>;
50 
51 public:
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 
62  CoalescingBitVector(const ThisT &Other)
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.
161  SmallVector<IntervalT, 8> Overlaps;
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).
179  SmallVector<IntervalT, 8> Overlaps;
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) {
189  SmallVector<IntervalT, 8> Overlaps;
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 (IntervalT Overlap : Overlaps) {
198  IndexT OlapStart, OlapStop;
199  std::tie(OlapStart, OlapStop) = Overlap;
200 
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!");
206 
207  // Split the overlap interval into up to two parts: one from [CurrStart,
208  // OlapStart-1] and another from [OlapStop+1, CurrStop]. If OlapStart is
209  // equal to CurrStart, the first split interval is unnecessary. Ditto for
210  // when OlapStop is equal to CurrStop, we omit the second split interval.
211  It.erase();
212  if (CurrStart < OlapStart)
213  insert(CurrStart, OlapStart - 1);
214  if (OlapStop < CurrStop)
215  insert(OlapStop + 1, CurrStop);
216  }
217  }
218 
219  bool operator==(const ThisT &RHS) const {
220  // We cannot just use std::equal because it checks the dereferenced values
221  // of an iterator pair for equality, not the iterators themselves. In our
222  // case that results in comparison of the (unused) IntervalMap values.
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()) {
227  ++ItL;
228  ++ItR;
229  }
230  return ItL == Intervals.end() && ItR == RHS.Intervals.end();
231  }
232 
233  bool operator!=(const ThisT &RHS) const { return !operator==(RHS); }
234 
236  friend class CoalescingBitVector;
237 
238  public:
239  using iterator_category = std::forward_iterator_tag;
240  using value_type = IndexT;
241  using difference_type = std::ptrdiff_t;
242  using pointer = value_type *;
244 
245  private:
246  // For performance reasons, make the offset at the end different than the
247  // one used in \ref begin, to optimize the common `It == end()` pattern.
248  static constexpr unsigned kIteratorAtTheEndOffset = ~0u;
249 
250  UnderlyingIterator MapIterator;
251  unsigned OffsetIntoMapIterator = 0;
252 
253  // Querying the start/stop of an IntervalMap iterator can be very expensive.
254  // Cache these values for performance reasons.
255  IndexT CachedStart = IndexT();
256  IndexT CachedStop = IndexT();
257 
258  void setToEnd() {
259  OffsetIntoMapIterator = kIteratorAtTheEndOffset;
260  CachedStart = IndexT();
261  CachedStop = IndexT();
262  }
263 
264  /// MapIterator has just changed, reset the cached state to point to the
265  /// start of the new underlying iterator.
266  void resetCache() {
267  if (MapIterator.valid()) {
268  OffsetIntoMapIterator = 0;
269  CachedStart = MapIterator.start();
270  CachedStop = MapIterator.stop();
271  } else {
272  setToEnd();
273  }
274  }
275 
276  /// Advance the iterator to \p Index, if it is contained within the current
277  /// interval. The public-facing method which supports advancing past the
278  /// current interval is \ref advanceToLowerBound.
279  void advanceTo(IndexT Index) {
280  assert(Index <= CachedStop && "Cannot advance to OOB index");
281  if (Index < CachedStart)
282  // We're already past this index.
283  return;
284  OffsetIntoMapIterator = Index - CachedStart;
285  }
286 
287  const_iterator(UnderlyingIterator MapIt) : MapIterator(MapIt) {
288  resetCache();
289  }
290 
291  public:
292  const_iterator() { setToEnd(); }
293 
294  bool operator==(const const_iterator &RHS) const {
295  // Do /not/ compare MapIterator for equality, as this is very expensive.
296  // The cached start/stop values make that check unnecessary.
297  return std::tie(OffsetIntoMapIterator, CachedStart, CachedStop) ==
298  std::tie(RHS.OffsetIntoMapIterator, RHS.CachedStart,
299  RHS.CachedStop);
300  }
301 
302  bool operator!=(const const_iterator &RHS) const {
303  return !operator==(RHS);
304  }
305 
306  IndexT operator*() const { return CachedStart + OffsetIntoMapIterator; }
307 
308  const_iterator &operator++() { // Pre-increment (++It).
309  if (CachedStart + OffsetIntoMapIterator < CachedStop) {
310  // Keep going within the current interval.
311  ++OffsetIntoMapIterator;
312  } else {
313  // We reached the end of the current interval: advance.
314  ++MapIterator;
315  resetCache();
316  }
317  return *this;
318  }
319 
320  const_iterator operator++(int) { // Post-increment (It++).
321  const_iterator tmp = *this;
322  operator++();
323  return tmp;
324  }
325 
326  /// Advance the iterator to the first set bit AT, OR AFTER, \p Index. If
327  /// no such set bit exists, advance to end(). This is like std::lower_bound.
328  /// This is useful if \p Index is close to the current iterator position.
329  /// However, unlike \ref find(), this has worst-case O(n) performance.
330  void advanceToLowerBound(IndexT Index) {
331  if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
332  return;
333 
334  // Advance to the first interval containing (or past) Index, or to end().
335  while (Index > CachedStop) {
336  ++MapIterator;
337  resetCache();
338  if (OffsetIntoMapIterator == kIteratorAtTheEndOffset)
339  return;
340  }
341 
342  advanceTo(Index);
343  }
344  };
345 
346  const_iterator begin() const { return const_iterator(Intervals.begin()); }
347 
348  const_iterator end() const { return const_iterator(); }
349 
350  /// Return an iterator pointing to the first set bit AT, OR AFTER, \p Index.
351  /// If no such set bit exists, return end(). This is like std::lower_bound.
352  /// This has worst-case logarithmic performance (roughly O(log(gaps between
353  /// contiguous ranges))).
354  const_iterator find(IndexT Index) const {
355  auto UnderlyingIt = Intervals.find(Index);
356  if (UnderlyingIt == Intervals.end())
357  return end();
358  auto It = const_iterator(UnderlyingIt);
359  It.advanceTo(Index);
360  return It;
361  }
362 
363  /// Return a range iterator which iterates over all of the set bits in the
364  /// half-open range [Start, End).
366  IndexT End) const {
367  assert(Start < End && "Not a valid range");
368  auto StartIt = find(Start);
369  if (StartIt == end() || *StartIt >= End)
370  return {end(), end()};
371  auto EndIt = StartIt;
372  EndIt.advanceToLowerBound(End);
373  return {StartIt, EndIt};
374  }
375 
376  void print(raw_ostream &OS) const {
377  OS << "{";
378  for (auto It = Intervals.begin(), End = Intervals.end(); It != End;
379  ++It) {
380  OS << "[" << It.start();
381  if (It.start() != It.stop())
382  OS << ", " << It.stop();
383  OS << "]";
384  }
385  OS << "}";
386  }
387 
388 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
389  LLVM_DUMP_METHOD void dump() const {
390  // LLDB swallows the first line of output after callling dump(). Add
391  // newlines before/after the braces to work around this.
392  dbgs() << "\n";
393  print(dbgs());
394  dbgs() << "\n";
395  }
396 #endif
397 
398 private:
399  void insert(IndexT Start, IndexT End) { Intervals.insert(Start, End, 0); }
400 
401  /// Record the overlaps between \p this and \p Other in \p Overlaps. Return
402  /// true if there is any overlap.
403  bool getOverlaps(const ThisT &Other,
404  SmallVectorImpl<IntervalT> &Overlaps) const {
405  for (IntervalMapOverlaps<MapT, MapT> I(Intervals, Other.Intervals);
406  I.valid(); ++I)
407  Overlaps.emplace_back(I.start(), I.stop());
408  assert(llvm::is_sorted(Overlaps,
409  [](IntervalT LHS, IntervalT RHS) {
410  return LHS.second < RHS.first;
411  }) &&
412  "Overlaps must be sorted");
413  return !Overlaps.empty();
414  }
415 
416  /// Given the set of overlaps between this and some other bitvector, and an
417  /// interval [Start, Stop] from that bitvector, determine the portions of the
418  /// interval which do not overlap with this.
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;
426 
427  // [Start;Stop] and [OlapStart;OlapStop] overlap iff OlapStart <= Stop
428  // and Start <= OlapStop.
429  bool DoesOverlap = OlapStart <= Stop && Start <= OlapStop;
430  if (!DoesOverlap)
431  continue;
432 
433  // Cover the range [NextUncoveredBit, OlapStart). This puts the start of
434  // the next uncovered range at OlapStop+1.
435  if (NextUncoveredBit < OlapStart)
436  NonOverlappingParts.emplace_back(NextUncoveredBit, OlapStart - 1);
437  NextUncoveredBit = OlapStop + 1;
438  if (NextUncoveredBit > Stop)
439  break;
440  }
441  if (NextUncoveredBit <= Stop)
442  NonOverlappingParts.emplace_back(NextUncoveredBit, Stop);
443  }
444 
445  Allocator *Alloc;
446  MapT Intervals;
447 };
448 
449 } // namespace llvm
450 
451 #endif // LLVM_ADT_COALESCINGBITVECTOR_H
llvm::CoalescingBitVector
A bitvector that, under the hood, relies on an IntervalMap to coalesce elements into intervals.
Definition: CoalescingBitVector.h:38
llvm::CoalescingBitVector::set
void set(std::initializer_list< IndexT > Indices)
Set the bits at Indices. Used for testing, primarily.
Definition: CoalescingBitVector.h:114
llvm::CoalescingBitVector::const_iterator::operator++
const_iterator & operator++()
Definition: CoalescingBitVector.h:308
llvm::IntervalMap::clear
void clear()
clear - Remove all entries.
Definition: IntervalMap.h:1291
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::IntervalMap::insert
void insert(KeyT a, KeyT b, ValT y)
insert - Add a mapping of [a;b] to y, coalesce with adjacent intervals.
Definition: IntervalMap.h:1090
llvm::CoalescingBitVector::set
void set(const ThisT &Other)
Set the bits set in Other.
Definition: CoalescingBitVector.h:107
llvm::CoalescingBitVector::CoalescingBitVector
CoalescingBitVector(const ThisT &Other)
Definition: CoalescingBitVector.h:62
llvm::CoalescingBitVector::print
void print(raw_ostream &OS) const
Definition: CoalescingBitVector.h:376
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::CoalescingBitVector::const_iterator::difference_type
std::ptrdiff_t difference_type
Definition: CoalescingBitVector.h:241
llvm::CoalescingBitVector::end
const_iterator end() const
Definition: CoalescingBitVector.h:348
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::CoalescingBitVector::const_iterator::operator!=
bool operator!=(const const_iterator &RHS) const
Definition: CoalescingBitVector.h:302
llvm::CoalescingBitVector::operator&=
void operator&=(const ThisT &RHS)
Set intersection.
Definition: CoalescingBitVector.h:177
llvm::IntervalMap::empty
bool empty() const
empty - Return true when no intervals are mapped.
Definition: IntervalMap.h:1062
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
tmp
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
Definition: README.txt:1347
llvm::CoalescingBitVector::set
void set(IndexT Index)
Set the bit at Index.
Definition: CoalescingBitVector.h:97
llvm::CoalescingBitVector::operator!=
bool operator!=(const ThisT &RHS) const
Definition: CoalescingBitVector.h:233
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::CoalescingBitVector::find
const_iterator find(IndexT Index) const
Return an iterator pointing to the first set bit AT, OR AFTER, Index.
Definition: CoalescingBitVector.h:354
llvm::CoalescingBitVector::const_iterator::pointer
value_type * pointer
Definition: CoalescingBitVector.h:242
llvm::CoalescingBitVector::const_iterator::operator==
bool operator==(const const_iterator &RHS) const
Definition: CoalescingBitVector.h:294
llvm::CoalescingBitVector::operator=
ThisT & operator=(const ThisT &Other)
Definition: CoalescingBitVector.h:67
llvm::CoalescingBitVector::begin
const_iterator begin() const
Definition: CoalescingBitVector.h:346
llvm::CoalescingBitVector::const_iterator::operator*
IndexT operator*() const
Definition: CoalescingBitVector.h:306
llvm::CoalescingBitVector::test_and_set
void test_and_set(IndexT Index)
Set the bit at Index. Supports setting an already-set bit.
Definition: CoalescingBitVector.h:129
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::CoalescingBitVector::intersectWithComplement
void intersectWithComplement(const ThisT &Other)
Reset all bits present in Other.
Definition: CoalescingBitVector.h:188
llvm::IntervalMap< IndexT, char >::Allocator
typename Sizer::Allocator Allocator
Definition: IntervalMap.h:962
llvm::CoalescingBitVector::const_iterator::advanceToLowerBound
void advanceToLowerBound(IndexT Index)
Advance the iterator to the first set bit AT, OR AFTER, Index.
Definition: CoalescingBitVector.h:330
Index
uint32_t Index
Definition: ELFObjHandler.cpp:82
llvm::CoalescingBitVector::test
bool test(IndexT Index) const
Check whether the bit at Index is set.
Definition: CoalescingBitVector.h:120
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::CoalescingBitVector::dump
LLVM_DUMP_METHOD void dump() const
Definition: CoalescingBitVector.h:389
llvm::CoalescingBitVector::operator==
bool operator==(const ThisT &RHS) const
Definition: CoalescingBitVector.h:219
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::IntervalMap::find
const_iterator find(KeyT x) const
find - Return an iterator pointing to the first interval ending at or after x, or end().
Definition: IntervalMap.h:1133
llvm::CoalescingBitVector::Allocator
typename MapT::Allocator Allocator
Definition: CoalescingBitVector.h:52
iterator_range.h
llvm::CoalescingBitVector::reset
void reset(IndexT Index)
Reset the bit at Index. Supports resetting an already-unset bit.
Definition: CoalescingBitVector.h:135
llvm::IntervalMap::end
const_iterator end() const
Definition: IntervalMap.h:1119
llvm::CoalescingBitVector::const_iterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: CoalescingBitVector.h:239
llvm::CoalescingBitVector::CoalescingBitVector
CoalescingBitVector(Allocator &Alloc)
Construct by passing in a CoalescingBitVector<IndexT>::Allocator reference.
Definition: CoalescingBitVector.h:56
llvm::CoalescingBitVector::const_iterator::operator++
const_iterator operator++(int)
Definition: CoalescingBitVector.h:320
llvm::CoalescingBitVector::operator|=
void operator|=(const ThisT &RHS)
Set union.
Definition: CoalescingBitVector.h:159
llvm::CoalescingBitVector::half_open_range
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,...
Definition: CoalescingBitVector.h:365
llvm::is_sorted
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:1687
llvm::CoalescingBitVector::clear
void clear()
Clear all the bits.
Definition: CoalescingBitVector.h:79
llvm::CoalescingBitVector::const_iterator::const_iterator
const_iterator()
Definition: CoalescingBitVector.h:292
llvm::CoalescingBitVector::count
unsigned count() const
Count the number of set bits.
Definition: CoalescingBitVector.h:85
SmallVector.h
IntervalMap.h
llvm::IntervalMap::begin
const_iterator begin() const
Definition: IntervalMap.h:1107
llvm::IntervalMap< IndexT, char >
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::IntervalMap< IndexT, char >::const_iterator
friend class const_iterator
Definition: IntervalMap.h:1103
llvm::CoalescingBitVector::empty
bool empty() const
Check whether no bits are set.
Definition: CoalescingBitVector.h:82
llvm::CoalescingBitVector::const_iterator::reference
value_type & reference
Definition: CoalescingBitVector.h:243
raw_ostream.h
llvm::CoalescingBitVector::const_iterator::value_type
IndexT value_type
Definition: CoalescingBitVector.h:240
llvm::CoalescingBitVector::const_iterator
Definition: CoalescingBitVector.h:235
Debug.h
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1236