Line data Source code
1 : //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the SmallBitVector class.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #ifndef LLVM_ADT_SMALLBITVECTOR_H
15 : #define LLVM_ADT_SMALLBITVECTOR_H
16 :
17 : #include "llvm/ADT/BitVector.h"
18 : #include "llvm/ADT/iterator_range.h"
19 : #include "llvm/Support/MathExtras.h"
20 : #include <algorithm>
21 : #include <cassert>
22 : #include <climits>
23 : #include <cstddef>
24 : #include <cstdint>
25 : #include <limits>
26 : #include <utility>
27 :
28 : namespace llvm {
29 :
30 : /// This is a 'bitvector' (really, a variable-sized bit array), optimized for
31 : /// the case when the array is small. It contains one pointer-sized field, which
32 : /// is directly used as a plain collection of bits when possible, or as a
33 : /// pointer to a larger heap-allocated array when necessary. This allows normal
34 : /// "small" cases to be fast without losing generality for large inputs.
35 : class SmallBitVector {
36 : // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
37 : // unnecessary level of indirection. It would be more efficient to use a
38 : // pointer to memory containing size, allocation size, and the array of bits.
39 : uintptr_t X = 1;
40 :
41 : enum {
42 : // The number of bits in this class.
43 : NumBaseBits = sizeof(uintptr_t) * CHAR_BIT,
44 :
45 : // One bit is used to discriminate between small and large mode. The
46 : // remaining bits are used for the small-mode representation.
47 : SmallNumRawBits = NumBaseBits - 1,
48 :
49 : // A few more bits are used to store the size of the bit set in small mode.
50 : // Theoretically this is a ceil-log2. These bits are encoded in the most
51 : // significant bits of the raw bits.
52 : SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
53 : NumBaseBits == 64 ? 6 :
54 : SmallNumRawBits),
55 :
56 : // The remaining bits are used to store the actual set in small mode.
57 : SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
58 : };
59 :
60 : static_assert(NumBaseBits == 64 || NumBaseBits == 32,
61 : "Unsupported word size");
62 :
63 : public:
64 : using size_type = unsigned;
65 :
66 : // Encapsulation of a single bit.
67 : class reference {
68 : SmallBitVector &TheVector;
69 : unsigned BitPos;
70 :
71 : public:
72 : reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
73 :
74 : reference(const reference&) = default;
75 :
76 0 : reference& operator=(reference t) {
77 4 : *this = bool(t);
78 0 : return *this;
79 : }
80 :
81 31811777 : reference& operator=(bool t) {
82 31811777 : if (t)
83 29895957 : TheVector.set(BitPos);
84 : else
85 1915822 : TheVector.reset(BitPos);
86 31811777 : return *this;
87 : }
88 :
89 0 : operator bool() const {
90 744136 : return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
91 : }
92 : };
93 :
94 : private:
95 0 : bool isSmall() const {
96 161632158 : return X & uintptr_t(1);
97 : }
98 :
99 0 : BitVector *getPointer() const {
100 : assert(!isSmall());
101 424339 : return reinterpret_cast<BitVector *>(X);
102 : }
103 :
104 : void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
105 : X = 1;
106 : setSmallSize(NewSize);
107 : setSmallBits(NewSmallBits);
108 : }
109 :
110 0 : void switchToLarge(BitVector *BV) {
111 62319 : X = reinterpret_cast<uintptr_t>(BV);
112 : assert(!isSmall() && "Tried to use an unaligned pointer");
113 0 : }
114 :
115 : // Return all the bits used for the "small" representation; this includes
116 : // bits for the size as well as the element bits.
117 0 : uintptr_t getSmallRawBits() const {
118 : assert(isSmall());
119 100705747 : return X >> 1;
120 : }
121 :
122 0 : void setSmallRawBits(uintptr_t NewRawBits) {
123 : assert(isSmall());
124 53487414 : X = (NewRawBits << 1) | uintptr_t(1);
125 0 : }
126 :
127 : // Return the size.
128 64805613 : size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
129 :
130 : void setSmallSize(size_t Size) {
131 17861678 : setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
132 : }
133 :
134 : // Return the element bits.
135 : uintptr_t getSmallBits() const {
136 31476339 : return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
137 : }
138 :
139 : void setSmallBits(uintptr_t NewBits) {
140 142999354 : setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
141 49814492 : (getSmallSize() << SmallNumDataBits));
142 : }
143 :
144 : public:
145 : /// Creates an empty bitvector.
146 20993432 : SmallBitVector() = default;
147 :
148 : /// Creates a bitvector of specified number of bits. All bits are initialized
149 : /// to the specified value.
150 18616282 : explicit SmallBitVector(unsigned s, bool t = false) {
151 18252846 : if (s <= SmallNumDataBits)
152 18252579 : switchToSmall(t ? ~uintptr_t(0) : 0, s);
153 : else
154 269 : switchToLarge(new BitVector(s, t));
155 18252846 : }
156 :
157 : /// SmallBitVector copy ctor.
158 5768 : SmallBitVector(const SmallBitVector &RHS) {
159 5768 : if (RHS.isSmall())
160 5761 : X = RHS.X;
161 : else
162 7 : switchToLarge(new BitVector(*RHS.getPointer()));
163 5768 : }
164 :
165 214049 : SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
166 81186 : RHS.X = 1;
167 : }
168 :
169 114849640 : ~SmallBitVector() {
170 57424820 : if (!isSmall())
171 62318 : delete getPointer();
172 57424820 : }
173 :
174 : using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
175 : using set_iterator = const_set_bits_iterator;
176 :
177 : const_set_bits_iterator set_bits_begin() const {
178 : return const_set_bits_iterator(*this);
179 : }
180 :
181 : const_set_bits_iterator set_bits_end() const {
182 : return const_set_bits_iterator(*this, -1);
183 : }
184 :
185 : iterator_range<const_set_bits_iterator> set_bits() const {
186 : return make_range(set_bits_begin(), set_bits_end());
187 : }
188 :
189 : /// Tests whether there are no bits in this bitvector.
190 : bool empty() const {
191 442313 : return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
192 : }
193 :
194 : /// Returns the number of bits in this bitvector.
195 : size_t size() const {
196 11087815 : return isSmall() ? getSmallSize() : getPointer()->size();
197 : }
198 :
199 : /// Returns the number of bits which are set.
200 72191 : size_type count() const {
201 72191 : if (isSmall()) {
202 : uintptr_t Bits = getSmallBits();
203 72159 : return countPopulation(Bits);
204 : }
205 : return getPointer()->count();
206 : }
207 :
208 : /// Returns true if any bit is set.
209 14495847 : bool any() const {
210 14495847 : if (isSmall())
211 14495843 : return getSmallBits() != 0;
212 : return getPointer()->any();
213 : }
214 :
215 : /// Returns true if all bits are set.
216 1889198 : bool all() const {
217 1889198 : if (isSmall())
218 1889194 : return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
219 4 : return getPointer()->all();
220 : }
221 :
222 : /// Returns true if none of the bits are set.
223 21 : bool none() const {
224 21 : if (isSmall())
225 16 : return getSmallBits() == 0;
226 5 : return getPointer()->none();
227 : }
228 :
229 : /// Returns the index of the first set bit, -1 if none of the bits are set.
230 1047423 : int find_first() const {
231 1047423 : if (isSmall()) {
232 : uintptr_t Bits = getSmallBits();
233 1047406 : if (Bits == 0)
234 : return -1;
235 1034730 : return countTrailingZeros(Bits);
236 : }
237 17 : return getPointer()->find_first();
238 : }
239 :
240 5 : int find_last() const {
241 5 : if (isSmall()) {
242 : uintptr_t Bits = getSmallBits();
243 1 : if (Bits == 0)
244 : return -1;
245 0 : return NumBaseBits - countLeadingZeros(Bits);
246 : }
247 4 : return getPointer()->find_last();
248 : }
249 :
250 : /// Returns the index of the first unset bit, -1 if all of the bits are set.
251 5 : int find_first_unset() const {
252 5 : if (isSmall()) {
253 1 : if (count() == getSmallSize())
254 : return -1;
255 :
256 : uintptr_t Bits = getSmallBits();
257 0 : return countTrailingOnes(Bits);
258 : }
259 4 : return getPointer()->find_first_unset();
260 : }
261 :
262 5 : int find_last_unset() const {
263 5 : if (isSmall()) {
264 1 : if (count() == getSmallSize())
265 1 : return -1;
266 :
267 : uintptr_t Bits = getSmallBits();
268 : return NumBaseBits - countLeadingOnes(Bits);
269 : }
270 4 : return getPointer()->find_last_unset();
271 : }
272 :
273 : /// Returns the index of the next set bit following the "Prev" bit.
274 : /// Returns -1 if the next set bit is not found.
275 999223 : int find_next(unsigned Prev) const {
276 999223 : if (isSmall()) {
277 : uintptr_t Bits = getSmallBits();
278 : // Mask off previous bits.
279 999168 : Bits &= ~uintptr_t(0) << (Prev + 1);
280 999168 : if (Bits == 0 || Prev + 1 >= getSmallSize())
281 : return -1;
282 53119 : return countTrailingZeros(Bits);
283 : }
284 55 : return getPointer()->find_next(Prev);
285 : }
286 :
287 : /// Returns the index of the next unset bit following the "Prev" bit.
288 : /// Returns -1 if the next unset bit is not found.
289 12 : int find_next_unset(unsigned Prev) const {
290 12 : if (isSmall()) {
291 0 : ++Prev;
292 : uintptr_t Bits = getSmallBits();
293 : // Mask in previous bits.
294 0 : uintptr_t Mask = (1 << Prev) - 1;
295 0 : Bits |= Mask;
296 :
297 0 : if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
298 : return -1;
299 0 : return countTrailingOnes(Bits);
300 : }
301 12 : return getPointer()->find_next_unset(Prev);
302 : }
303 :
304 : /// find_prev - Returns the index of the first set bit that precedes the
305 : /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
306 8 : int find_prev(unsigned PriorTo) const {
307 8 : if (isSmall()) {
308 0 : if (PriorTo == 0)
309 : return -1;
310 :
311 : --PriorTo;
312 : uintptr_t Bits = getSmallBits();
313 0 : Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
314 0 : if (Bits == 0)
315 : return -1;
316 :
317 0 : return NumBaseBits - countLeadingZeros(Bits) - 1;
318 : }
319 8 : return getPointer()->find_prev(PriorTo);
320 : }
321 :
322 : /// Clear all bits.
323 1298098 : void clear() {
324 1298098 : if (!isSmall())
325 2 : delete getPointer();
326 : switchToSmall(0, 0);
327 1298098 : }
328 :
329 : /// Grow or shrink the bitvector.
330 17965119 : void resize(unsigned N, bool t = false) {
331 17965119 : if (!isSmall()) {
332 41398 : getPointer()->resize(N, t);
333 17923721 : } else if (SmallNumDataBits >= N) {
334 17861678 : uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
335 17861678 : setSmallSize(N);
336 17861678 : setSmallBits(NewBits | getSmallBits());
337 : } else {
338 62043 : BitVector *BV = new BitVector(N, t);
339 : uintptr_t OldBits = getSmallBits();
340 62251 : for (size_t i = 0, e = getSmallSize(); i != e; ++i)
341 208 : (*BV)[i] = (OldBits >> i) & 1;
342 : switchToLarge(BV);
343 : }
344 17965119 : }
345 :
346 : void reserve(unsigned N) {
347 : if (isSmall()) {
348 : if (N > SmallNumDataBits) {
349 : uintptr_t OldBits = getSmallRawBits();
350 : size_t SmallSize = getSmallSize();
351 : BitVector *BV = new BitVector(SmallSize);
352 : for (size_t i = 0; i < SmallSize; ++i)
353 : if ((OldBits >> i) & 1)
354 : BV->set(i);
355 : BV->reserve(N);
356 : switchToLarge(BV);
357 : }
358 : } else {
359 : getPointer()->reserve(N);
360 : }
361 : }
362 :
363 : // Set, reset, flip
364 6 : SmallBitVector &set() {
365 6 : if (isSmall())
366 : setSmallBits(~uintptr_t(0));
367 : else
368 2 : getPointer()->set();
369 6 : return *this;
370 : }
371 :
372 30504465 : SmallBitVector &set(unsigned Idx) {
373 30504465 : if (isSmall()) {
374 : assert(Idx <= static_cast<unsigned>(
375 : std::numeric_limits<uintptr_t>::digits) &&
376 : "undefined behavior");
377 30401419 : setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
378 : }
379 : else
380 : getPointer()->set(Idx);
381 30504465 : return *this;
382 : }
383 :
384 : /// Efficiently set a range of bits in [I, E)
385 232076 : SmallBitVector &set(unsigned I, unsigned E) {
386 : assert(I <= E && "Attempted to set backwards range!");
387 : assert(E <= size() && "Attempted to set out-of-bounds range!");
388 232076 : if (I == E) return *this;
389 232076 : if (isSmall()) {
390 231993 : uintptr_t EMask = ((uintptr_t)1) << E;
391 231993 : uintptr_t IMask = ((uintptr_t)1) << I;
392 231993 : uintptr_t Mask = EMask - IMask;
393 231993 : setSmallBits(getSmallBits() | Mask);
394 : } else
395 83 : getPointer()->set(I, E);
396 : return *this;
397 : }
398 :
399 1884699 : SmallBitVector &reset() {
400 1884699 : if (isSmall())
401 : setSmallBits(0);
402 : else
403 : getPointer()->reset();
404 1884699 : return *this;
405 : }
406 :
407 4009893 : SmallBitVector &reset(unsigned Idx) {
408 4009893 : if (isSmall())
409 3874312 : setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
410 : else
411 : getPointer()->reset(Idx);
412 4009893 : return *this;
413 : }
414 :
415 : /// Efficiently reset a range of bits in [I, E)
416 298042 : SmallBitVector &reset(unsigned I, unsigned E) {
417 : assert(I <= E && "Attempted to reset backwards range!");
418 : assert(E <= size() && "Attempted to reset out-of-bounds range!");
419 298042 : if (I == E) return *this;
420 298042 : if (isSmall()) {
421 298039 : uintptr_t EMask = ((uintptr_t)1) << E;
422 298039 : uintptr_t IMask = ((uintptr_t)1) << I;
423 298039 : uintptr_t Mask = EMask - IMask;
424 298039 : setSmallBits(getSmallBits() & ~Mask);
425 : } else
426 3 : getPointer()->reset(I, E);
427 : return *this;
428 : }
429 :
430 12531 : SmallBitVector &flip() {
431 12531 : if (isSmall())
432 : setSmallBits(~getSmallBits());
433 : else
434 3 : getPointer()->flip();
435 12531 : return *this;
436 : }
437 :
438 2 : SmallBitVector &flip(unsigned Idx) {
439 2 : if (isSmall())
440 0 : setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
441 : else
442 : getPointer()->flip(Idx);
443 2 : return *this;
444 : }
445 :
446 : // No argument flip.
447 : SmallBitVector operator~() const {
448 : return SmallBitVector(*this).flip();
449 : }
450 :
451 : // Indexing.
452 : reference operator[](unsigned Idx) {
453 : assert(Idx < size() && "Out-of-bounds Bit access.");
454 : return reference(*this, Idx);
455 : }
456 :
457 6990948 : bool operator[](unsigned Idx) const {
458 : assert(Idx < size() && "Out-of-bounds Bit access.");
459 6990948 : if (isSmall())
460 6890740 : return ((getSmallBits() >> Idx) & 1) != 0;
461 : return getPointer()->operator[](Idx);
462 : }
463 :
464 : bool test(unsigned Idx) const {
465 5106 : return (*this)[Idx];
466 : }
467 :
468 : // Push single bit to end of vector.
469 203 : void push_back(bool Val) {
470 406 : resize(size() + 1, Val);
471 203 : }
472 :
473 : /// Test if any common bits are set.
474 10 : bool anyCommon(const SmallBitVector &RHS) const {
475 10 : if (isSmall() && RHS.isSmall())
476 1 : return (getSmallBits() & RHS.getSmallBits()) != 0;
477 9 : if (!isSmall() && !RHS.isSmall())
478 8 : return getPointer()->anyCommon(*RHS.getPointer());
479 :
480 3 : for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
481 0 : if (test(i) && RHS.test(i))
482 : return true;
483 : return false;
484 : }
485 :
486 : // Comparison operators.
487 1871994 : bool operator==(const SmallBitVector &RHS) const {
488 1871994 : if (size() != RHS.size())
489 : return false;
490 1871994 : if (isSmall())
491 1786641 : return getSmallBits() == RHS.getSmallBits();
492 : else
493 85353 : return *getPointer() == *RHS.getPointer();
494 : }
495 :
496 : bool operator!=(const SmallBitVector &RHS) const {
497 1871969 : return !(*this == RHS);
498 : }
499 :
500 : // Intersection, union, disjoint union.
501 59 : SmallBitVector &operator&=(const SmallBitVector &RHS) {
502 118 : resize(std::max(size(), RHS.size()));
503 59 : if (isSmall())
504 59 : setSmallBits(getSmallBits() & RHS.getSmallBits());
505 0 : else if (!RHS.isSmall())
506 0 : getPointer()->operator&=(*RHS.getPointer());
507 : else {
508 0 : SmallBitVector Copy = RHS;
509 0 : Copy.resize(size());
510 0 : getPointer()->operator&=(*Copy.getPointer());
511 : }
512 59 : return *this;
513 : }
514 :
515 : /// Reset bits that are set in RHS. Same as *this &= ~RHS.
516 7 : SmallBitVector &reset(const SmallBitVector &RHS) {
517 7 : if (isSmall() && RHS.isSmall())
518 3 : setSmallBits(getSmallBits() & ~RHS.getSmallBits());
519 4 : else if (!isSmall() && !RHS.isSmall())
520 1 : getPointer()->reset(*RHS.getPointer());
521 : else
522 157 : for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
523 150 : if (RHS.test(i))
524 100 : reset(i);
525 :
526 7 : return *this;
527 : }
528 :
529 : /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
530 44 : bool test(const SmallBitVector &RHS) const {
531 44 : if (isSmall() && RHS.isSmall())
532 4 : return (getSmallBits() & ~RHS.getSmallBits()) != 0;
533 40 : if (!isSmall() && !RHS.isSmall())
534 34 : return getPointer()->test(*RHS.getPointer());
535 :
536 : unsigned i, e;
537 214 : for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
538 202 : if (test(i) && !RHS.test(i))
539 : return true;
540 :
541 4 : for (e = size(); i != e; ++i)
542 1 : if (test(i))
543 : return true;
544 :
545 : return false;
546 : }
547 :
548 608283 : SmallBitVector &operator|=(const SmallBitVector &RHS) {
549 1254285 : resize(std::max(size(), RHS.size()));
550 608283 : if (isSmall())
551 567051 : setSmallBits(getSmallBits() | RHS.getSmallBits());
552 41232 : else if (!RHS.isSmall())
553 41232 : getPointer()->operator|=(*RHS.getPointer());
554 : else {
555 0 : SmallBitVector Copy = RHS;
556 0 : Copy.resize(size());
557 0 : getPointer()->operator|=(*Copy.getPointer());
558 : }
559 608283 : return *this;
560 : }
561 :
562 1 : SmallBitVector &operator^=(const SmallBitVector &RHS) {
563 3 : resize(std::max(size(), RHS.size()));
564 1 : if (isSmall())
565 0 : setSmallBits(getSmallBits() ^ RHS.getSmallBits());
566 1 : else if (!RHS.isSmall())
567 1 : getPointer()->operator^=(*RHS.getPointer());
568 : else {
569 0 : SmallBitVector Copy = RHS;
570 0 : Copy.resize(size());
571 0 : getPointer()->operator^=(*Copy.getPointer());
572 : }
573 1 : return *this;
574 : }
575 :
576 6 : SmallBitVector &operator<<=(unsigned N) {
577 6 : if (isSmall())
578 3 : setSmallBits(getSmallBits() << N);
579 : else
580 3 : getPointer()->operator<<=(N);
581 6 : return *this;
582 : }
583 :
584 6 : SmallBitVector &operator>>=(unsigned N) {
585 6 : if (isSmall())
586 4 : setSmallBits(getSmallBits() >> N);
587 : else
588 2 : getPointer()->operator>>=(N);
589 6 : return *this;
590 : }
591 :
592 : // Assignment operator.
593 3657823 : const SmallBitVector &operator=(const SmallBitVector &RHS) {
594 3657823 : if (isSmall()) {
595 3491175 : if (RHS.isSmall())
596 3491175 : X = RHS.X;
597 : else
598 0 : switchToLarge(new BitVector(*RHS.getPointer()));
599 : } else {
600 166648 : if (!RHS.isSmall())
601 166648 : *getPointer() = *RHS.getPointer();
602 : else {
603 0 : delete getPointer();
604 0 : X = RHS.X;
605 : }
606 : }
607 3657823 : return *this;
608 : }
609 :
610 : const SmallBitVector &operator=(SmallBitVector &&RHS) {
611 : if (this != &RHS) {
612 3 : clear();
613 : swap(RHS);
614 : }
615 : return *this;
616 : }
617 :
618 : void swap(SmallBitVector &RHS) {
619 : std::swap(X, RHS.X);
620 : }
621 :
622 : /// Add '1' bits from Mask to this vector. Don't resize.
623 : /// This computes "*this |= Mask".
624 6 : void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
625 6 : if (isSmall())
626 : applyMask<true, false>(Mask, MaskWords);
627 : else
628 : getPointer()->setBitsInMask(Mask, MaskWords);
629 6 : }
630 :
631 : /// Clear any bits in this vector that are set in Mask. Don't resize.
632 : /// This computes "*this &= ~Mask".
633 : void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
634 : if (isSmall())
635 : applyMask<false, false>(Mask, MaskWords);
636 : else
637 : getPointer()->clearBitsInMask(Mask, MaskWords);
638 : }
639 :
640 : /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
641 : /// This computes "*this |= ~Mask".
642 3 : void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
643 3 : if (isSmall())
644 : applyMask<true, true>(Mask, MaskWords);
645 : else
646 : getPointer()->setBitsNotInMask(Mask, MaskWords);
647 3 : }
648 :
649 : /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
650 : /// This computes "*this &= Mask".
651 1 : void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
652 1 : if (isSmall())
653 : applyMask<false, true>(Mask, MaskWords);
654 : else
655 : getPointer()->clearBitsNotInMask(Mask, MaskWords);
656 1 : }
657 :
658 : private:
659 : template <bool AddBits, bool InvertMask>
660 0 : void applyMask(const uint32_t *Mask, unsigned MaskWords) {
661 : assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
662 5 : uintptr_t M = Mask[0];
663 : if (NumBaseBits == 64)
664 5 : M |= uint64_t(Mask[1]) << 32;
665 : if (InvertMask)
666 0 : M = ~M;
667 : if (AddBits)
668 5 : setSmallBits(getSmallBits() | M);
669 : else
670 0 : setSmallBits(getSmallBits() & ~M);
671 0 : }
672 0 : };
673 :
674 0 : inline SmallBitVector
675 : operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
676 0 : SmallBitVector Result(LHS);
677 : Result &= RHS;
678 : return Result;
679 : }
680 :
681 : inline SmallBitVector
682 0 : operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
683 2905 : SmallBitVector Result(LHS);
684 2905 : Result |= RHS;
685 : return Result;
686 0 : }
687 :
688 0 : inline SmallBitVector
689 : operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
690 0 : SmallBitVector Result(LHS);
691 : Result ^= RHS;
692 0 : return Result;
693 : }
694 :
695 0 : } // end namespace llvm
696 0 :
697 : namespace std {
698 0 :
699 : /// Implement std::swap in terms of BitVector swap.
700 0 : inline void
701 : swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
702 : LHS.swap(RHS);
703 : }
704 0 :
705 : } // end namespace std
706 :
707 0 : #endif // LLVM_ADT_SMALLBITVECTOR_H
|
