Coverage Report

Created: 2018-12-11 00:00

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ADT/SmallBitVector.h
Line
Count
Source (jump to first uncovered line)
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
131M
    reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
73
74
    reference(const reference&) = default;
75
76
    reference& operator=(reference t) {
77
      *this = bool(t);
78
      return *this;
79
    }
80
81
70.6M
    reference& operator=(bool t) {
82
70.6M
      if (t)
83
5.09M
        TheVector.set(BitPos);
84
65.5M
      else
85
65.5M
        TheVector.reset(BitPos);
86
70.6M
      return *this;
87
70.6M
    }
88
89
61.0M
    operator bool() const {
90
61.0M
      return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
91
61.0M
    }
92
  };
93
94
private:
95
562M
  bool isSmall() const {
96
562M
    return X & uintptr_t(1);
97
562M
  }
98
99
206M
  BitVector *getPointer() const {
100
206M
    assert(!isSmall());
101
206M
    return reinterpret_cast<BitVector *>(X);
102
206M
  }
103
104
16.6M
  void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
105
16.6M
    X = 1;
106
16.6M
    setSmallSize(NewSize);
107
16.6M
    setSmallBits(NewSmallBits);
108
16.6M
  }
109
110
517k
  void switchToLarge(BitVector *BV) {
111
517k
    X = reinterpret_cast<uintptr_t>(BV);
112
517k
    assert(!isSmall() && "Tried to use an unaligned pointer");
113
517k
  }
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
921M
  uintptr_t getSmallRawBits() const {
118
921M
    assert(isSmall());
119
921M
    return X >> 1;
120
921M
  }
121
122
209M
  void setSmallRawBits(uintptr_t NewRawBits) {
123
209M
    assert(isSmall());
124
209M
    X = (NewRawBits << 1) | uintptr_t(1);
125
209M
  }
126
127
  // Return the size.
128
668M
  size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
129
130
61.6M
  void setSmallSize(size_t Size) {
131
61.6M
    setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
132
61.6M
  }
133
134
  // Return the element bits.
135
253M
  uintptr_t getSmallBits() const {
136
253M
    return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
137
253M
  }
138
139
147M
  void setSmallBits(uintptr_t NewBits) {
140
147M
    setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
141
147M
                    (getSmallSize() << SmallNumDataBits));
142
147M
  }
143
144
public:
145
  /// Creates an empty bitvector.
146
18.2M
  SmallBitVector() = default;
147
148
  /// Creates a bitvector of specified number of bits. All bits are initialized
149
  /// to the specified value.
150
14.8M
  explicit SmallBitVector(unsigned s, bool t = false) {
151
14.8M
    if (s <= SmallNumDataBits)
152
14.8M
      switchToSmall(t ? 
~uintptr_t(0)924k
:
013.9M
, s);
153
1.48k
    else
154
1.48k
      switchToLarge(new BitVector(s, t));
155
14.8M
  }
156
157
  /// SmallBitVector copy ctor.
158
193k
  SmallBitVector(const SmallBitVector &RHS) {
159
193k
    if (RHS.isSmall())
160
193k
      X = RHS.X;
161
7
    else
162
7
      switchToLarge(new BitVector(*RHS.getPointer()));
163
193k
  }
164
165
11.7M
  SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
166
11.7M
    RHS.X = 1;
167
11.7M
  }
168
169
45.1M
  ~SmallBitVector() {
170
45.1M
    if (!isSmall())
171
517k
      delete getPointer();
172
45.1M
  }
173
174
  using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
175
  using set_iterator = const_set_bits_iterator;
176
177
3.00M
  const_set_bits_iterator set_bits_begin() const {
178
3.00M
    return const_set_bits_iterator(*this);
179
3.00M
  }
180
181
3.00M
  const_set_bits_iterator set_bits_end() const {
182
3.00M
    return const_set_bits_iterator(*this, -1);
183
3.00M
  }
184
185
3.00M
  iterator_range<const_set_bits_iterator> set_bits() const {
186
3.00M
    return make_range(set_bits_begin(), set_bits_end());
187
3.00M
  }
188
189
  /// Tests whether there are no bits in this bitvector.
190
95.2k
  bool empty() const {
191
95.2k
    return isSmall() ? 
getSmallSize() == 095.2k
:
getPointer()->empty()4
;
192
95.2k
  }
193
194
  /// Returns the number of bits in this bitvector.
195
220M
  size_t size() const {
196
220M
    return isSmall() ? 
getSmallSize()116M
:
getPointer()->size()103M
;
197
220M
  }
198
199
  /// Returns the number of bits which are set.
200
1.77M
  size_type count() const {
201
1.77M
    if (isSmall()) {
202
1.27M
      uintptr_t Bits = getSmallBits();
203
1.27M
      return countPopulation(Bits);
204
1.27M
    }
205
502k
    return getPointer()->count();
206
502k
  }
207
208
  /// Returns true if any bit is set.
209
1.51M
  bool any() const {
210
1.51M
    if (isSmall())
211
1.51M
      return getSmallBits() != 0;
212
4
    return getPointer()->any();
213
4
  }
214
215
  /// Returns true if all bits are set.
216
166k
  bool all() const {
217
166k
    if (isSmall())
218
166k
      return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
219
4
    return getPointer()->all();
220
4
  }
221
222
  /// Returns true if none of the bits are set.
223
  bool none() const {
224
    if (isSmall())
225
      return getSmallBits() == 0;
226
    return getPointer()->none();
227
  }
228
229
  /// Returns the index of the first set bit, -1 if none of the bits are set.
230
11.1M
  int find_first() const {
231
11.1M
    if (isSmall()) {
232
8.31M
      uintptr_t Bits = getSmallBits();
233
8.31M
      if (Bits == 0)
234
41.5k
        return -1;
235
8.27M
      return countTrailingZeros(Bits);
236
8.27M
    }
237
2.82M
    return getPointer()->find_first();
238
2.82M
  }
239
240
  int find_last() const {
241
    if (isSmall()) {
242
      uintptr_t Bits = getSmallBits();
243
      if (Bits == 0)
244
        return -1;
245
      return NumBaseBits - countLeadingZeros(Bits);
246
    }
247
    return getPointer()->find_last();
248
  }
249
250
  /// Returns the index of the first unset bit, -1 if all of the bits are set.
251
  int find_first_unset() const {
252
    if (isSmall()) {
253
      if (count() == getSmallSize())
254
        return -1;
255
256
      uintptr_t Bits = getSmallBits();
257
      return countTrailingOnes(Bits);
258
    }
259
    return getPointer()->find_first_unset();
260
  }
261
262
  int find_last_unset() const {
263
    if (isSmall()) {
264
      if (count() == getSmallSize())
265
        return -1;
266
267
      uintptr_t Bits = getSmallBits();
268
      return NumBaseBits - countLeadingOnes(Bits);
269
    }
270
    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
9.13M
  int find_next(unsigned Prev) const {
276
9.13M
    if (isSmall()) {
277
7.05M
      uintptr_t Bits = getSmallBits();
278
7.05M
      // Mask off previous bits.
279
7.05M
      Bits &= ~uintptr_t(0) << (Prev + 1);
280
7.05M
      if (Bits == 0 || 
Prev + 1 >= getSmallSize()1.86M
)
281
5.19M
        return -1;
282
1.86M
      return countTrailingZeros(Bits);
283
1.86M
    }
284
2.07M
    return getPointer()->find_next(Prev);
285
2.07M
  }
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
  int find_next_unset(unsigned Prev) const {
290
    if (isSmall()) {
291
      ++Prev;
292
      uintptr_t Bits = getSmallBits();
293
      // Mask in previous bits.
294
      uintptr_t Mask = (1 << Prev) - 1;
295
      Bits |= Mask;
296
297
      if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
298
        return -1;
299
      return countTrailingOnes(Bits);
300
    }
301
    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
  int find_prev(unsigned PriorTo) const {
307
    if (isSmall()) {
308
      if (PriorTo == 0)
309
        return -1;
310
311
      --PriorTo;
312
      uintptr_t Bits = getSmallBits();
313
      Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
314
      if (Bits == 0)
315
        return -1;
316
317
      return NumBaseBits - countLeadingZeros(Bits) - 1;
318
    }
319
    return getPointer()->find_prev(PriorTo);
320
  }
321
322
  /// Clear all bits.
323
1.78M
  void clear() {
324
1.78M
    if (!isSmall())
325
2
      delete getPointer();
326
1.78M
    switchToSmall(0, 0);
327
1.78M
  }
328
329
  /// Grow or shrink the bitvector.
330
80.8M
  void resize(unsigned N, bool t = false) {
331
80.8M
    if (!isSmall()) {
332
35.3M
      getPointer()->resize(N, t);
333
45.4M
    } else if (SmallNumDataBits >= N) {
334
44.9M
      uintptr_t NewBits = t ? 
~uintptr_t(0) << getSmallSize()80
:
044.9M
;
335
44.9M
      setSmallSize(N);
336
44.9M
      setSmallBits(NewBits | getSmallBits());
337
44.9M
    } else {
338
515k
      BitVector *BV = new BitVector(N, t);
339
515k
      uintptr_t OldBits = getSmallBits();
340
6.38M
      for (size_t i = 0, e = getSmallSize(); i != e; 
++i5.87M
)
341
5.87M
        (*BV)[i] = (OldBits >> i) & 1;
342
515k
      switchToLarge(BV);
343
515k
    }
344
80.8M
  }
345
346
0
  void reserve(unsigned N) {
347
0
    if (isSmall()) {
348
0
      if (N > SmallNumDataBits) {
349
0
        uintptr_t OldBits = getSmallRawBits();
350
0
        size_t SmallSize = getSmallSize();
351
0
        BitVector *BV = new BitVector(SmallSize);
352
0
        for (size_t i = 0; i < SmallSize; ++i)
353
0
          if ((OldBits >> i) & 1)
354
0
            BV->set(i);
355
0
        BV->reserve(N);
356
0
        switchToLarge(BV);
357
0
      }
358
0
    } else {
359
0
      getPointer()->reserve(N);
360
0
    }
361
0
  }
362
363
  // Set, reset, flip
364
  SmallBitVector &set() {
365
    if (isSmall())
366
      setSmallBits(~uintptr_t(0));
367
    else
368
      getPointer()->set();
369
    return *this;
370
  }
371
372
31.1M
  SmallBitVector &set(unsigned Idx) {
373
31.1M
    if (isSmall()) {
374
28.4M
      assert(Idx <= static_cast<unsigned>(
375
28.4M
                        std::numeric_limits<uintptr_t>::digits) &&
376
28.4M
             "undefined behavior");
377
28.4M
      setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
378
28.4M
    }
379
2.67M
    else
380
2.67M
      getPointer()->set(Idx);
381
31.1M
    return *this;
382
31.1M
  }
383
384
  /// Efficiently set a range of bits in [I, E)
385
232k
  SmallBitVector &set(unsigned I, unsigned E) {
386
232k
    assert(I <= E && "Attempted to set backwards range!");
387
232k
    assert(E <= size() && "Attempted to set out-of-bounds range!");
388
232k
    if (I == E) 
return *this0
;
389
232k
    if (isSmall()) {
390
232k
      uintptr_t EMask = ((uintptr_t)1) << E;
391
232k
      uintptr_t IMask = ((uintptr_t)1) << I;
392
232k
      uintptr_t Mask = EMask - IMask;
393
232k
      setSmallBits(getSmallBits() | Mask);
394
232k
    } else
395
83
      getPointer()->set(I, E);
396
232k
    return *this;
397
232k
  }
398
399
782k
  SmallBitVector &reset() {
400
782k
    if (isSmall())
401
741k
      setSmallBits(0);
402
41.3k
    else
403
41.3k
      getPointer()->reset();
404
782k
    return *this;
405
782k
  }
406
407
87.5M
  SmallBitVector &reset(unsigned Idx) {
408
87.5M
    if (isSmall())
409
54.2M
      setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
410
33.3M
    else
411
33.3M
      getPointer()->reset(Idx);
412
87.5M
    return *this;
413
87.5M
  }
414
415
  /// Efficiently reset a range of bits in [I, E)
416
298k
  SmallBitVector &reset(unsigned I, unsigned E) {
417
298k
    assert(I <= E && "Attempted to reset backwards range!");
418
298k
    assert(E <= size() && "Attempted to reset out-of-bounds range!");
419
298k
    if (I == E) 
return *this0
;
420
298k
    if (isSmall()) {
421
298k
      uintptr_t EMask = ((uintptr_t)1) << E;
422
298k
      uintptr_t IMask = ((uintptr_t)1) << I;
423
298k
      uintptr_t Mask = EMask - IMask;
424
298k
      setSmallBits(getSmallBits() & ~Mask);
425
298k
    } else
426
3
      getPointer()->reset(I, E);
427
298k
    return *this;
428
298k
  }
429
430
41.5k
  SmallBitVector &flip() {
431
41.5k
    if (isSmall())
432
41.5k
      setSmallBits(~getSmallBits());
433
3
    else
434
3
      getPointer()->flip();
435
41.5k
    return *this;
436
41.5k
  }
437
438
  SmallBitVector &flip(unsigned Idx) {
439
    if (isSmall())
440
      setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
441
    else
442
      getPointer()->flip(Idx);
443
    return *this;
444
  }
445
446
  // No argument flip.
447
0
  SmallBitVector operator~() const {
448
0
    return SmallBitVector(*this).flip();
449
0
  }
450
451
  // Indexing.
452
131M
  reference operator[](unsigned Idx) {
453
131M
    assert(Idx < size() && "Out-of-bounds Bit access.");
454
131M
    return reference(*this, Idx);
455
131M
  }
456
457
64.3M
  bool operator[](unsigned Idx) const {
458
64.3M
    assert(Idx < size() && "Out-of-bounds Bit access.");
459
64.3M
    if (isSmall())
460
39.6M
      return ((getSmallBits() >> Idx) & 1) != 0;
461
24.7M
    return getPointer()->operator[](Idx);
462
24.7M
  }
463
464
5.57k
  bool test(unsigned Idx) const {
465
5.57k
    return (*this)[Idx];
466
5.57k
  }
467
468
  // Push single bit to end of vector.
469
  void push_back(bool Val) {
470
    resize(size() + 1, Val);
471
  }
472
473
  /// Test if any common bits are set.
474
  bool anyCommon(const SmallBitVector &RHS) const {
475
    if (isSmall() && RHS.isSmall())
476
      return (getSmallBits() & RHS.getSmallBits()) != 0;
477
    if (!isSmall() && !RHS.isSmall())
478
      return getPointer()->anyCommon(*RHS.getPointer());
479
480
    for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
481
      if (test(i) && RHS.test(i))
482
        return true;
483
    return false;
484
  }
485
486
  // Comparison operators.
487
741k
  bool operator==(const SmallBitVector &RHS) const {
488
741k
    if (size() != RHS.size())
489
0
      return false;
490
741k
    if (isSmall())
491
699k
      return getSmallBits() == RHS.getSmallBits();
492
41.3k
    else
493
41.3k
      return *getPointer() == *RHS.getPointer();
494
741k
  }
495
496
741k
  bool operator!=(const SmallBitVector &RHS) const {
497
741k
    return !(*this == RHS);
498
741k
  }
499
500
  // Intersection, union, disjoint union.
501
59
  SmallBitVector &operator&=(const SmallBitVector &RHS) {
502
59
    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
0
    else {
508
0
      SmallBitVector Copy = RHS;
509
0
      Copy.resize(size());
510
0
      getPointer()->operator&=(*Copy.getPointer());
511
0
    }
512
59
    return *this;
513
59
  }
514
515
  /// Reset bits that are set in RHS. Same as *this &= ~RHS.
516
  SmallBitVector &reset(const SmallBitVector &RHS) {
517
    if (isSmall() && RHS.isSmall())
518
      setSmallBits(getSmallBits() & ~RHS.getSmallBits());
519
    else if (!isSmall() && !RHS.isSmall())
520
      getPointer()->reset(*RHS.getPointer());
521
    else
522
      for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
523
        if (RHS.test(i))
524
          reset(i);
525
526
    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()8
)
532
4
      return (getSmallBits() & ~RHS.getSmallBits()) != 0;
533
40
    if (!isSmall() && 
!RHS.isSmall()36
)
534
34
      return getPointer()->test(*RHS.getPointer());
535
6
536
6
    unsigned i, e;
537
206
    for (i = 0, e = std::min(size(), RHS.size()); i != e; 
++i200
)
538
202
      if (test(i) && 
!RHS.test(i)102
)
539
2
        return true;
540
6
541
6
    
for (e = size(); 4
i != e4
;
++i0
)
542
1
      if (test(i))
543
1
        return true;
544
4
545
4
    
return false3
;
546
4
  }
547
548
2.40M
  SmallBitVector &operator|=(const SmallBitVector &RHS) {
549
2.40M
    resize(std::max(size(), RHS.size()));
550
2.40M
    if (isSmall())
551
1.92M
      setSmallBits(getSmallBits() | RHS.getSmallBits());
552
482k
    else if (!RHS.isSmall())
553
294k
      getPointer()->operator|=(*RHS.getPointer());
554
187k
    else {
555
187k
      SmallBitVector Copy = RHS;
556
187k
      Copy.resize(size());
557
187k
      getPointer()->operator|=(*Copy.getPointer());
558
187k
    }
559
2.40M
    return *this;
560
2.40M
  }
561
562
  SmallBitVector &operator^=(const SmallBitVector &RHS) {
563
    resize(std::max(size(), RHS.size()));
564
    if (isSmall())
565
      setSmallBits(getSmallBits() ^ RHS.getSmallBits());
566
    else if (!RHS.isSmall())
567
      getPointer()->operator^=(*RHS.getPointer());
568
    else {
569
      SmallBitVector Copy = RHS;
570
      Copy.resize(size());
571
      getPointer()->operator^=(*Copy.getPointer());
572
    }
573
    return *this;
574
  }
575
576
  SmallBitVector &operator<<=(unsigned N) {
577
    if (isSmall())
578
      setSmallBits(getSmallBits() << N);
579
    else
580
      getPointer()->operator<<=(N);
581
    return *this;
582
  }
583
584
  SmallBitVector &operator>>=(unsigned N) {
585
    if (isSmall())
586
      setSmallBits(getSmallBits() >> N);
587
    else
588
      getPointer()->operator>>=(N);
589
    return *this;
590
  }
591
592
  // Assignment operator.
593
1.45M
  const SmallBitVector &operator=(const SmallBitVector &RHS) {
594
1.45M
    if (isSmall()) {
595
1.37M
      if (RHS.isSmall())
596
1.37M
        X = RHS.X;
597
0
      else
598
0
        switchToLarge(new BitVector(*RHS.getPointer()));
599
1.37M
    } else {
600
79.7k
      if (!RHS.isSmall())
601
79.7k
        *getPointer() = *RHS.getPointer();
602
0
      else {
603
0
        delete getPointer();
604
0
        X = RHS.X;
605
0
      }
606
79.7k
    }
607
1.45M
    return *this;
608
1.45M
  }
609
610
  const SmallBitVector &operator=(SmallBitVector &&RHS) {
611
    if (this != &RHS) {
612
      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
  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
625
    if (isSmall())
626
      applyMask<true, false>(Mask, MaskWords);
627
    else
628
      getPointer()->setBitsInMask(Mask, MaskWords);
629
  }
630
631
  /// Clear any bits in this vector that are set in Mask. Don't resize.
632
  /// This computes "*this &= ~Mask".
633
0
  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
634
0
    if (isSmall())
635
0
      applyMask<false, false>(Mask, MaskWords);
636
0
    else
637
0
      getPointer()->clearBitsInMask(Mask, MaskWords);
638
0
  }
639
640
  /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
641
  /// This computes "*this |= ~Mask".
642
  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
643
    if (isSmall())
644
      applyMask<true, true>(Mask, MaskWords);
645
    else
646
      getPointer()->setBitsNotInMask(Mask, MaskWords);
647
  }
648
649
  /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
650
  /// This computes "*this &= Mask".
651
  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
652
    if (isSmall())
653
      applyMask<false, true>(Mask, MaskWords);
654
    else
655
      getPointer()->clearBitsNotInMask(Mask, MaskWords);
656
  }
657
658
private:
659
  template <bool AddBits, bool InvertMask>
660
  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
661
    assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
662
    uintptr_t M = Mask[0];
663
    if (NumBaseBits == 64)
664
      M |= uint64_t(Mask[1]) << 32;
665
    if (InvertMask)
666
      M = ~M;
667
    if (AddBits)
668
      setSmallBits(getSmallBits() | M);
669
    else
670
      setSmallBits(getSmallBits() & ~M);
671
  }
672
};
673
674
inline SmallBitVector
675
0
operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
676
0
  SmallBitVector Result(LHS);
677
0
  Result &= RHS;
678
0
  return Result;
679
0
}
680
681
inline SmallBitVector
682
3.00k
operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
683
3.00k
  SmallBitVector Result(LHS);
684
3.00k
  Result |= RHS;
685
3.00k
  return Result;
686
3.00k
}
687
688
inline SmallBitVector
689
0
operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
690
0
  SmallBitVector Result(LHS);
691
0
  Result ^= RHS;
692
0
  return Result;
693
0
}
694
695
} // end namespace llvm
696
697
namespace std {
698
699
/// Implement std::swap in terms of BitVector swap.
700
inline void
701
swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
702
  LHS.swap(RHS);
703
}
704
705
} // end namespace std
706
707
#endif // LLVM_ADT_SMALLBITVECTOR_H