Coverage Report

Created: 2018-07-12 09:57

/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
130M
    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
69.8M
    reference& operator=(bool t) {
82
69.8M
      if (t)
83
4.50M
        TheVector.set(BitPos);
84
65.3M
      else
85
65.3M
        TheVector.reset(BitPos);
86
69.8M
      return *this;
87
69.8M
    }
88
89
60.2M
    operator bool() const {
90
60.2M
      return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
91
60.2M
    }
92
  };
93
94
private:
95
554M
  bool isSmall() const {
96
554M
    return X & uintptr_t(1);
97
554M
  }
98
99
206M
  BitVector *getPointer() const {
100
206M
    assert(!isSmall());
101
206M
    return reinterpret_cast<BitVector *>(X);
102
206M
  }
103
104
15.9M
  void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
105
15.9M
    X = 1;
106
15.9M
    setSmallSize(NewSize);
107
15.9M
    setSmallBits(NewSmallBits);
108
15.9M
  }
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
899M
  uintptr_t getSmallRawBits() const {
118
899M
    assert(isSmall());
119
899M
    return X >> 1;
120
899M
  }
121
122
203M
  void setSmallRawBits(uintptr_t NewRawBits) {
123
203M
    assert(isSmall());
124
203M
    X = (NewRawBits << 1) | uintptr_t(1);
125
203M
  }
126
127
  // Return the size.
128
652M
  size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
129
130
60.3M
  void setSmallSize(size_t Size) {
131
60.3M
    setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
132
60.3M
  }
133
134
  // Return the element bits.
135
247M
  uintptr_t getSmallBits() const {
136
247M
    return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
137
247M
  }
138
139
143M
  void setSmallBits(uintptr_t NewBits) {
140
143M
    setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
141
143M
                    (getSmallSize() << SmallNumDataBits));
142
143M
  }
143
144
public:
145
  /// Creates an empty bitvector.
146
17.6M
  SmallBitVector() = default;
147
148
  /// Creates a bitvector of specified number of bits. All bits are initialized
149
  /// to the specified value.
150
14.1M
  explicit SmallBitVector(unsigned s, bool t = false) {
151
14.1M
    if (s <= SmallNumDataBits)
152
14.1M
      switchToSmall(t ? 
~uintptr_t(0)882k
:
013.2M
, s);
153
1.38k
    else
154
1.38k
      switchToLarge(new BitVector(s, t));
155
14.1M
  }
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.2M
  SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
166
11.2M
    RHS.X = 1;
167
11.2M
  }
168
169
43.2M
  ~SmallBitVector() {
170
43.2M
    if (!isSmall())
171
517k
      delete getPointer();
172
43.2M
  }
173
174
  using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
175
  using set_iterator = const_set_bits_iterator;
176
177
2.98M
  const_set_bits_iterator set_bits_begin() const {
178
2.98M
    return const_set_bits_iterator(*this);
179
2.98M
  }
180
181
2.98M
  const_set_bits_iterator set_bits_end() const {
182
2.98M
    return const_set_bits_iterator(*this, -1);
183
2.98M
  }
184
185
2.98M
  iterator_range<const_set_bits_iterator> set_bits() const {
186
2.98M
    return make_range(set_bits_begin(), set_bits_end());
187
2.98M
  }
188
189
  /// Tests whether there are no bits in this bitvector.
190
137k
  bool empty() const {
191
137k
    return isSmall() ? 
getSmallSize() == 0137k
:
getPointer()->empty()4
;
192
137k
  }
193
194
  /// Returns the number of bits in this bitvector.
195
218M
  size_t size() const {
196
218M
    return isSmall() ? 
getSmallSize()115M
:
getPointer()->size()103M
;
197
218M
  }
198
199
  /// Returns the number of bits which are set.
200
1.72M
  size_type count() const {
201
1.72M
    if (isSmall()) {
202
1.20M
      uintptr_t Bits = getSmallBits();
203
1.20M
      return countPopulation(Bits);
204
1.20M
    }
205
521k
    return getPointer()->count();
206
521k
  }
207
208
  /// Returns true if any bit is set.
209
1.18M
  bool any() const {
210
1.18M
    if (isSmall())
211
1.18M
      return getSmallBits() != 0;
212
4
    return getPointer()->any();
213
4
  }
214
215
  /// Returns true if all bits are set.
216
154k
  bool all() const {
217
154k
    if (isSmall())
218
154k
      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
10.6M
  int find_first() const {
231
10.6M
    if (isSmall()) {
232
7.84M
      uintptr_t Bits = getSmallBits();
233
7.84M
      if (Bits == 0)
234
41.2k
        return -1;
235
7.80M
      return countTrailingZeros(Bits);
236
7.80M
    }
237
2.77M
    return getPointer()->find_first();
238
2.77M
  }
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
8.76M
  int find_next(unsigned Prev) const {
276
8.76M
    if (isSmall()) {
277
6.71M
      uintptr_t Bits = getSmallBits();
278
6.71M
      // Mask off previous bits.
279
6.71M
      Bits &= ~uintptr_t(0) << (Prev + 1);
280
6.71M
      if (Bits == 0 || 
Prev + 1 >= getSmallSize()1.79M
)
281
4.92M
        return -1;
282
1.79M
      return countTrailingZeros(Bits);
283
1.79M
    }
284
2.05M
    return getPointer()->find_next(Prev);
285
2.05M
  }
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.73M
  void clear() {
324
1.73M
    if (!isSmall())
325
2
      delete getPointer();
326
1.73M
    switchToSmall(0, 0);
327
1.73M
  }
328
329
  /// Grow or shrink the bitvector.
330
80.2M
  void resize(unsigned N, bool t = false) {
331
80.2M
    if (!isSmall()) {
332
35.3M
      getPointer()->resize(N, t);
333
44.9M
    } else if (SmallNumDataBits >= N) {
334
44.4M
      uintptr_t NewBits = t ? 
~uintptr_t(0) << getSmallSize()54
:
044.4M
;
335
44.4M
      setSmallSize(N);
336
44.4M
      setSmallBits(NewBits | getSmallBits());
337
44.4M
    } else {
338
515k
      BitVector *BV = new BitVector(N, t);
339
515k
      uintptr_t OldBits = getSmallBits();
340
6.43M
      for (size_t i = 0, e = getSmallSize(); i != e; 
++i5.91M
)
341
5.91M
        (*BV)[i] = (OldBits >> i) & 1;
342
515k
      switchToLarge(BV);
343
515k
    }
344
80.2M
  }
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
29.6M
  SmallBitVector &set(unsigned Idx) {
373
29.6M
    if (isSmall()) {
374
26.9M
      assert(Idx <= static_cast<unsigned>(
375
26.9M
                        std::numeric_limits<uintptr_t>::digits) &&
376
26.9M
             "undefined behavior");
377
26.9M
      setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
378
26.9M
    }
379
2.62M
    else
380
2.62M
      getPointer()->set(Idx);
381
29.6M
    return *this;
382
29.6M
  }
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
231k
      uintptr_t EMask = ((uintptr_t)1) << E;
391
231k
      uintptr_t IMask = ((uintptr_t)1) << I;
392
231k
      uintptr_t Mask = EMask - IMask;
393
231k
      setSmallBits(getSmallBits() | Mask);
394
231k
    } else
395
83
      getPointer()->set(I, E);
396
232k
    return *this;
397
232k
  }
398
399
825k
  SmallBitVector &reset() {
400
825k
    if (isSmall())
401
785k
      setSmallBits(0);
402
39.6k
    else
403
39.6k
      getPointer()->reset();
404
825k
    return *this;
405
825k
  }
406
407
86.3M
  SmallBitVector &reset(unsigned Idx) {
408
86.3M
    if (isSmall())
409
53.0M
      setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
410
33.2M
    else
411
33.2M
      getPointer()->reset(Idx);
412
86.3M
    return *this;
413
86.3M
  }
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.2k
  SmallBitVector &flip() {
431
41.2k
    if (isSmall())
432
41.2k
      setSmallBits(~getSmallBits());
433
3
    else
434
3
      getPointer()->flip();
435
41.2k
    return *this;
436
41.2k
  }
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
130M
  reference operator[](unsigned Idx) {
453
130M
    assert(Idx < size() && "Out-of-bounds Bit access.");
454
130M
    return reference(*this, Idx);
455
130M
  }
456
457
63.5M
  bool operator[](unsigned Idx) const {
458
63.5M
    assert(Idx < size() && "Out-of-bounds Bit access.");
459
63.5M
    if (isSmall())
460
38.8M
      return ((getSmallBits() >> Idx) & 1) != 0;
461
24.6M
    return getPointer()->operator[](Idx);
462
24.6M
  }
463
464
5.61k
  bool test(unsigned Idx) const {
465
5.61k
    return (*this)[Idx];
466
5.61k
  }
467
468
  /// Test if any common bits are set.
469
  bool anyCommon(const SmallBitVector &RHS) const {
470
    if (isSmall() && RHS.isSmall())
471
      return (getSmallBits() & RHS.getSmallBits()) != 0;
472
    if (!isSmall() && !RHS.isSmall())
473
      return getPointer()->anyCommon(*RHS.getPointer());
474
475
    for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
476
      if (test(i) && RHS.test(i))
477
        return true;
478
    return false;
479
  }
480
481
  // Comparison operators.
482
783k
  bool operator==(const SmallBitVector &RHS) const {
483
783k
    if (size() != RHS.size())
484
0
      return false;
485
783k
    if (isSmall())
486
743k
      return getSmallBits() == RHS.getSmallBits();
487
39.6k
    else
488
39.6k
      return *getPointer() == *RHS.getPointer();
489
783k
  }
490
491
783k
  bool operator!=(const SmallBitVector &RHS) const {
492
783k
    return !(*this == RHS);
493
783k
  }
494
495
  // Intersection, union, disjoint union.
496
59
  SmallBitVector &operator&=(const SmallBitVector &RHS) {
497
59
    resize(std::max(size(), RHS.size()));
498
59
    if (isSmall())
499
59
      setSmallBits(getSmallBits() & RHS.getSmallBits());
500
0
    else if (!RHS.isSmall())
501
0
      getPointer()->operator&=(*RHS.getPointer());
502
0
    else {
503
0
      SmallBitVector Copy = RHS;
504
0
      Copy.resize(size());
505
0
      getPointer()->operator&=(*Copy.getPointer());
506
0
    }
507
59
    return *this;
508
59
  }
509
510
  /// Reset bits that are set in RHS. Same as *this &= ~RHS.
511
  SmallBitVector &reset(const SmallBitVector &RHS) {
512
    if (isSmall() && RHS.isSmall())
513
      setSmallBits(getSmallBits() & ~RHS.getSmallBits());
514
    else if (!isSmall() && !RHS.isSmall())
515
      getPointer()->reset(*RHS.getPointer());
516
    else
517
      for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
518
        if (RHS.test(i))
519
          reset(i);
520
521
    return *this;
522
  }
523
524
  /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
525
44
  bool test(const SmallBitVector &RHS) const {
526
44
    if (isSmall() && 
RHS.isSmall()8
)
527
4
      return (getSmallBits() & ~RHS.getSmallBits()) != 0;
528
40
    if (!isSmall() && 
!RHS.isSmall()36
)
529
34
      return getPointer()->test(*RHS.getPointer());
530
6
531
6
    unsigned i, e;
532
206
    for (i = 0, e = std::min(size(), RHS.size()); i != e; 
++i200
)
533
202
      if (test(i) && 
!RHS.test(i)102
)
534
2
        return true;
535
6
536
6
    
for (e = size(); 4
i != e4
;
++i0
)
537
1
      if (test(i))
538
1
        return true;
539
4
540
4
    
return false3
;
541
4
  }
542
543
2.37M
  SmallBitVector &operator|=(const SmallBitVector &RHS) {
544
2.37M
    resize(std::max(size(), RHS.size()));
545
2.37M
    if (isSmall())
546
1.89M
      setSmallBits(getSmallBits() | RHS.getSmallBits());
547
482k
    else if (!RHS.isSmall())
548
294k
      getPointer()->operator|=(*RHS.getPointer());
549
187k
    else {
550
187k
      SmallBitVector Copy = RHS;
551
187k
      Copy.resize(size());
552
187k
      getPointer()->operator|=(*Copy.getPointer());
553
187k
    }
554
2.37M
    return *this;
555
2.37M
  }
556
557
  SmallBitVector &operator^=(const SmallBitVector &RHS) {
558
    resize(std::max(size(), RHS.size()));
559
    if (isSmall())
560
      setSmallBits(getSmallBits() ^ RHS.getSmallBits());
561
    else if (!RHS.isSmall())
562
      getPointer()->operator^=(*RHS.getPointer());
563
    else {
564
      SmallBitVector Copy = RHS;
565
      Copy.resize(size());
566
      getPointer()->operator^=(*Copy.getPointer());
567
    }
568
    return *this;
569
  }
570
571
  SmallBitVector &operator<<=(unsigned N) {
572
    if (isSmall())
573
      setSmallBits(getSmallBits() << N);
574
    else
575
      getPointer()->operator<<=(N);
576
    return *this;
577
  }
578
579
  SmallBitVector &operator>>=(unsigned N) {
580
    if (isSmall())
581
      setSmallBits(getSmallBits() >> N);
582
    else
583
      getPointer()->operator>>=(N);
584
    return *this;
585
  }
586
587
  // Assignment operator.
588
1.53M
  const SmallBitVector &operator=(const SmallBitVector &RHS) {
589
1.53M
    if (isSmall()) {
590
1.46M
      if (RHS.isSmall())
591
1.46M
        X = RHS.X;
592
0
      else
593
0
        switchToLarge(new BitVector(*RHS.getPointer()));
594
1.46M
    } else {
595
76.5k
      if (!RHS.isSmall())
596
76.5k
        *getPointer() = *RHS.getPointer();
597
0
      else {
598
0
        delete getPointer();
599
0
        X = RHS.X;
600
0
      }
601
76.5k
    }
602
1.53M
    return *this;
603
1.53M
  }
604
605
  const SmallBitVector &operator=(SmallBitVector &&RHS) {
606
    if (this != &RHS) {
607
      clear();
608
      swap(RHS);
609
    }
610
    return *this;
611
  }
612
613
0
  void swap(SmallBitVector &RHS) {
614
0
    std::swap(X, RHS.X);
615
0
  }
616
617
  /// Add '1' bits from Mask to this vector. Don't resize.
618
  /// This computes "*this |= Mask".
619
  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
620
    if (isSmall())
621
      applyMask<true, false>(Mask, MaskWords);
622
    else
623
      getPointer()->setBitsInMask(Mask, MaskWords);
624
  }
625
626
  /// Clear any bits in this vector that are set in Mask. Don't resize.
627
  /// This computes "*this &= ~Mask".
628
0
  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
629
0
    if (isSmall())
630
0
      applyMask<false, false>(Mask, MaskWords);
631
0
    else
632
0
      getPointer()->clearBitsInMask(Mask, MaskWords);
633
0
  }
634
635
  /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
636
  /// This computes "*this |= ~Mask".
637
  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
638
    if (isSmall())
639
      applyMask<true, true>(Mask, MaskWords);
640
    else
641
      getPointer()->setBitsNotInMask(Mask, MaskWords);
642
  }
643
644
  /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
645
  /// This computes "*this &= Mask".
646
  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
647
    if (isSmall())
648
      applyMask<false, true>(Mask, MaskWords);
649
    else
650
      getPointer()->clearBitsNotInMask(Mask, MaskWords);
651
  }
652
653
private:
654
  template <bool AddBits, bool InvertMask>
655
  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
656
    assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
657
    uintptr_t M = Mask[0];
658
    if (NumBaseBits == 64)
659
      M |= uint64_t(Mask[1]) << 32;
660
    if (InvertMask)
661
      M = ~M;
662
    if (AddBits)
663
      setSmallBits(getSmallBits() | M);
664
    else
665
      setSmallBits(getSmallBits() & ~M);
666
  }
667
};
668
669
inline SmallBitVector
670
0
operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
671
0
  SmallBitVector Result(LHS);
672
0
  Result &= RHS;
673
0
  return Result;
674
0
}
675
676
inline SmallBitVector
677
2.79k
operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
678
2.79k
  SmallBitVector Result(LHS);
679
2.79k
  Result |= RHS;
680
2.79k
  return Result;
681
2.79k
}
682
683
inline SmallBitVector
684
0
operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
685
0
  SmallBitVector Result(LHS);
686
0
  Result ^= RHS;
687
0
  return Result;
688
0
}
689
690
} // end namespace llvm
691
692
namespace std {
693
694
/// Implement std::swap in terms of BitVector swap.
695
inline void
696
0
swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
697
0
  LHS.swap(RHS);
698
0
}
699
700
} // end namespace std
701
702
#endif // LLVM_ADT_SMALLBITVECTOR_H