Coverage Report

Created: 2019-02-20 00:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ADT/BitVector.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- 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
// This file implements the BitVector class.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_ADT_BITVECTOR_H
14
#define LLVM_ADT_BITVECTOR_H
15
16
#include "llvm/ADT/ArrayRef.h"
17
#include "llvm/ADT/iterator_range.h"
18
#include "llvm/Support/MathExtras.h"
19
#include <algorithm>
20
#include <cassert>
21
#include <climits>
22
#include <cstdint>
23
#include <cstdlib>
24
#include <cstring>
25
#include <utility>
26
27
namespace llvm {
28
29
/// ForwardIterator for the bits that are set.
30
/// Iterators get invalidated when resize / reserve is called.
31
template <typename BitVectorT> class const_set_bits_iterator_impl {
32
  const BitVectorT &Parent;
33
  int Current = 0;
34
35
208M
  void advance() {
36
208M
    assert(Current != -1 && "Trying to advance past end.");
37
208M
    Current = Parent.find_next(Current);
38
208M
  }
llvm::const_set_bits_iterator_impl<llvm::BitVector>::advance()
Line
Count
Source
35
203M
  void advance() {
36
203M
    assert(Current != -1 && "Trying to advance past end.");
37
203M
    Current = Parent.find_next(Current);
38
203M
  }
llvm::const_set_bits_iterator_impl<llvm::SmallBitVector>::advance()
Line
Count
Source
35
4.79M
  void advance() {
36
4.79M
    assert(Current != -1 && "Trying to advance past end.");
37
4.79M
    Current = Parent.find_next(Current);
38
4.79M
  }
39
40
public:
41
  const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
42
40.5M
      : Parent(Parent), Current(Current) {}
llvm::const_set_bits_iterator_impl<llvm::BitVector>::const_set_bits_iterator_impl(llvm::BitVector const&, int)
Line
Count
Source
42
34.4M
      : Parent(Parent), Current(Current) {}
llvm::const_set_bits_iterator_impl<llvm::SmallBitVector>::const_set_bits_iterator_impl(llvm::SmallBitVector const&, int)
Line
Count
Source
42
6.05M
      : Parent(Parent), Current(Current) {}
43
  explicit const_set_bits_iterator_impl(const BitVectorT &Parent)
44
20.2M
      : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
llvm::const_set_bits_iterator_impl<llvm::BitVector>::const_set_bits_iterator_impl(llvm::BitVector const&)
Line
Count
Source
44
17.2M
      : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
llvm::const_set_bits_iterator_impl<llvm::SmallBitVector>::const_set_bits_iterator_impl(llvm::SmallBitVector const&)
Line
Count
Source
44
3.02M
      : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
45
  const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default;
46
47
  const_set_bits_iterator_impl operator++(int) {
48
    auto Prev = *this;
49
    advance();
50
    return Prev;
51
  }
52
53
208M
  const_set_bits_iterator_impl &operator++() {
54
208M
    advance();
55
208M
    return *this;
56
208M
  }
llvm::const_set_bits_iterator_impl<llvm::BitVector>::operator++()
Line
Count
Source
53
203M
  const_set_bits_iterator_impl &operator++() {
54
203M
    advance();
55
203M
    return *this;
56
203M
  }
llvm::const_set_bits_iterator_impl<llvm::SmallBitVector>::operator++()
Line
Count
Source
53
4.79M
  const_set_bits_iterator_impl &operator++() {
54
4.79M
    advance();
55
4.79M
    return *this;
56
4.79M
  }
57
58
208M
  unsigned operator*() const { return Current; }
llvm::const_set_bits_iterator_impl<llvm::BitVector>::operator*() const
Line
Count
Source
58
203M
  unsigned operator*() const { return Current; }
llvm::const_set_bits_iterator_impl<llvm::SmallBitVector>::operator*() const
Line
Count
Source
58
4.79M
  unsigned operator*() const { return Current; }
59
60
  bool operator==(const const_set_bits_iterator_impl &Other) const {
61
    assert(&Parent == &Other.Parent &&
62
           "Comparing iterators from different BitVectors");
63
    return Current == Other.Current;
64
  }
65
66
229M
  bool operator!=(const const_set_bits_iterator_impl &Other) const {
67
229M
    assert(&Parent == &Other.Parent &&
68
229M
           "Comparing iterators from different BitVectors");
69
229M
    return Current != Other.Current;
70
229M
  }
llvm::const_set_bits_iterator_impl<llvm::BitVector>::operator!=(llvm::const_set_bits_iterator_impl<llvm::BitVector> const&) const
Line
Count
Source
66
221M
  bool operator!=(const const_set_bits_iterator_impl &Other) const {
67
221M
    assert(&Parent == &Other.Parent &&
68
221M
           "Comparing iterators from different BitVectors");
69
221M
    return Current != Other.Current;
70
221M
  }
llvm::const_set_bits_iterator_impl<llvm::SmallBitVector>::operator!=(llvm::const_set_bits_iterator_impl<llvm::SmallBitVector> const&) const
Line
Count
Source
66
7.82M
  bool operator!=(const const_set_bits_iterator_impl &Other) const {
67
7.82M
    assert(&Parent == &Other.Parent &&
68
7.82M
           "Comparing iterators from different BitVectors");
69
7.82M
    return Current != Other.Current;
70
7.82M
  }
71
};
72
73
class BitVector {
74
  typedef unsigned long BitWord;
75
76
  enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
77
78
  static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
79
                "Unsupported word size");
80
81
  MutableArrayRef<BitWord> Bits; // Actual bits.
82
  unsigned Size;                 // Size of bitvector in bits.
83
84
public:
85
  typedef unsigned size_type;
86
  // Encapsulation of a single bit.
87
  class reference {
88
    friend class BitVector;
89
90
    BitWord *WordRef;
91
    unsigned BitPos;
92
93
  public:
94
734M
    reference(BitVector &b, unsigned Idx) {
95
734M
      WordRef = &b.Bits[Idx / BITWORD_SIZE];
96
734M
      BitPos = Idx % BITWORD_SIZE;
97
734M
    }
98
99
    reference() = delete;
100
    reference(const reference&) = default;
101
102
    reference &operator=(reference t) {
103
      *this = bool(t);
104
      return *this;
105
    }
106
107
7.28M
    reference& operator=(bool t) {
108
7.28M
      if (t)
109
3.65M
        *WordRef |= BitWord(1) << BitPos;
110
3.63M
      else
111
3.63M
        *WordRef &= ~(BitWord(1) << BitPos);
112
7.28M
      return *this;
113
7.28M
    }
114
115
727M
    operator bool() const {
116
727M
      return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
117
727M
    }
118
  };
119
120
  typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator;
121
  typedef const_set_bits_iterator set_iterator;
122
123
17.2M
  const_set_bits_iterator set_bits_begin() const {
124
17.2M
    return const_set_bits_iterator(*this);
125
17.2M
  }
126
17.2M
  const_set_bits_iterator set_bits_end() const {
127
17.2M
    return const_set_bits_iterator(*this, -1);
128
17.2M
  }
129
17.2M
  iterator_range<const_set_bits_iterator> set_bits() const {
130
17.2M
    return make_range(set_bits_begin(), set_bits_end());
131
17.2M
  }
132
133
  /// BitVector default ctor - Creates an empty bitvector.
134
36.6M
  BitVector() : Size(0) {}
135
136
  /// BitVector ctor - Creates a bitvector of specified number of bits. All
137
  /// bits are initialized to the specified value.
138
44.5M
  explicit BitVector(unsigned s, bool t = false) : Size(s) {
139
44.5M
    size_t Capacity = NumBitWords(s);
140
44.5M
    Bits = allocate(Capacity);
141
44.5M
    init_words(Bits, t);
142
44.5M
    if (t)
143
89.0k
      clear_unused_bits();
144
44.5M
  }
145
146
  /// BitVector copy ctor.
147
9.35M
  BitVector(const BitVector &RHS) : Size(RHS.size()) {
148
9.35M
    if (Size == 0) {
149
447k
      Bits = MutableArrayRef<BitWord>();
150
447k
      return;
151
447k
    }
152
8.90M
153
8.90M
    size_t Capacity = NumBitWords(RHS.size());
154
8.90M
    Bits = allocate(Capacity);
155
8.90M
    std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord));
156
8.90M
  }
157
158
5.95M
  BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) {
159
5.95M
    RHS.Bits = MutableArrayRef<BitWord>();
160
5.95M
    RHS.Size = 0;
161
5.95M
  }
162
163
96.4M
  ~BitVector() { std::free(Bits.data()); }
164
165
  /// empty - Tests whether there are no bits in this bitvector.
166
118M
  bool empty() const { return Size == 0; }
167
168
  /// size - Returns the number of bits in this bitvector.
169
498M
  size_type size() const { return Size; }
170
171
  /// count - Returns the number of bits which are set.
172
1.53M
  size_type count() const {
173
1.53M
    unsigned NumBits = 0;
174
11.3M
    for (unsigned i = 0; i < NumBitWords(size()); 
++i9.78M
)
175
9.78M
      NumBits += countPopulation(Bits[i]);
176
1.53M
    return NumBits;
177
1.53M
  }
178
179
  /// any - Returns true if any bit is set.
180
7.33M
  bool any() const {
181
12.7M
    for (unsigned i = 0; i < NumBitWords(size()); 
++i5.36M
)
182
9.10M
      if (Bits[i] != 0)
183
3.73M
        return true;
184
7.33M
    
return false3.59M
;
185
7.33M
  }
186
187
  /// all - Returns true if all bits are set.
188
2.49k
  bool all() const {
189
2.50k
    for (unsigned i = 0; i < Size / BITWORD_SIZE; 
++i7
)
190
11
      if (Bits[i] != ~0UL)
191
4
        return false;
192
2.49k
193
2.49k
    // If bits remain check that they are ones. The unused bits are always zero.
194
2.49k
    
if (unsigned 2.49k
Remainder2.49k
= Size % BITWORD_SIZE)
195
2.48k
      return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1;
196
11
197
11
    return true;
198
11
  }
199
200
  /// none - Returns true if none of the bits are set.
201
763k
  bool none() const {
202
763k
    return !any();
203
763k
  }
204
205
  /// find_first_in - Returns the index of the first set bit in the range
206
  /// [Begin, End).  Returns -1 if all bits in the range are unset.
207
236M
  int find_first_in(unsigned Begin, unsigned End) const {
208
236M
    assert(Begin <= End && End <= Size);
209
236M
    if (Begin == End)
210
3.39M
      return -1;
211
233M
212
233M
    unsigned FirstWord = Begin / BITWORD_SIZE;
213
233M
    unsigned LastWord = (End - 1) / BITWORD_SIZE;
214
233M
215
233M
    // Check subsequent words.
216
300M
    for (unsigned i = FirstWord; i <= LastWord; 
++i67.1M
) {
217
284M
      BitWord Copy = Bits[i];
218
284M
219
284M
      if (i == FirstWord) {
220
233M
        unsigned FirstBit = Begin % BITWORD_SIZE;
221
233M
        Copy &= maskTrailingZeros<BitWord>(FirstBit);
222
233M
      }
223
284M
224
284M
      if (i == LastWord) {
225
105M
        unsigned LastBit = (End - 1) % BITWORD_SIZE;
226
105M
        Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
227
105M
      }
228
284M
      if (Copy != 0)
229
217M
        return i * BITWORD_SIZE + countTrailingZeros(Copy);
230
284M
    }
231
233M
    
return -116.0M
;
232
233M
  }
233
234
  /// find_last_in - Returns the index of the last set bit in the range
235
  /// [Begin, End).  Returns -1 if all bits in the range are unset.
236
  int find_last_in(unsigned Begin, unsigned End) const {
237
    assert(Begin <= End && End <= Size);
238
    if (Begin == End)
239
      return -1;
240
241
    unsigned LastWord = (End - 1) / BITWORD_SIZE;
242
    unsigned FirstWord = Begin / BITWORD_SIZE;
243
244
    for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
245
      unsigned CurrentWord = i - 1;
246
247
      BitWord Copy = Bits[CurrentWord];
248
      if (CurrentWord == LastWord) {
249
        unsigned LastBit = (End - 1) % BITWORD_SIZE;
250
        Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
251
      }
252
253
      if (CurrentWord == FirstWord) {
254
        unsigned FirstBit = Begin % BITWORD_SIZE;
255
        Copy &= maskTrailingZeros<BitWord>(FirstBit);
256
      }
257
258
      if (Copy != 0)
259
        return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1;
260
    }
261
262
    return -1;
263
  }
264
265
  /// find_first_unset_in - Returns the index of the first unset bit in the
266
  /// range [Begin, End).  Returns -1 if all bits in the range are set.
267
  int find_first_unset_in(unsigned Begin, unsigned End) const {
268
    assert(Begin <= End && End <= Size);
269
    if (Begin == End)
270
      return -1;
271
272
    unsigned FirstWord = Begin / BITWORD_SIZE;
273
    unsigned LastWord = (End - 1) / BITWORD_SIZE;
274
275
    // Check subsequent words.
276
    for (unsigned i = FirstWord; i <= LastWord; ++i) {
277
      BitWord Copy = Bits[i];
278
279
      if (i == FirstWord) {
280
        unsigned FirstBit = Begin % BITWORD_SIZE;
281
        Copy |= maskTrailingOnes<BitWord>(FirstBit);
282
      }
283
284
      if (i == LastWord) {
285
        unsigned LastBit = (End - 1) % BITWORD_SIZE;
286
        Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
287
      }
288
      if (Copy != ~0UL) {
289
        unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy);
290
        return Result < size() ? Result : -1;
291
      }
292
    }
293
    return -1;
294
  }
295
296
  /// find_last_unset_in - Returns the index of the last unset bit in the
297
  /// range [Begin, End).  Returns -1 if all bits in the range are set.
298
  int find_last_unset_in(unsigned Begin, unsigned End) const {
299
    assert(Begin <= End && End <= Size);
300
    if (Begin == End)
301
      return -1;
302
303
    unsigned LastWord = (End - 1) / BITWORD_SIZE;
304
    unsigned FirstWord = Begin / BITWORD_SIZE;
305
306
    for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
307
      unsigned CurrentWord = i - 1;
308
309
      BitWord Copy = Bits[CurrentWord];
310
      if (CurrentWord == LastWord) {
311
        unsigned LastBit = (End - 1) % BITWORD_SIZE;
312
        Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
313
      }
314
315
      if (CurrentWord == FirstWord) {
316
        unsigned FirstBit = Begin % BITWORD_SIZE;
317
        Copy |= maskTrailingOnes<BitWord>(FirstBit);
318
      }
319
320
      if (Copy != ~0UL) {
321
        unsigned Result =
322
            (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
323
        return Result < Size ? Result : -1;
324
      }
325
    }
326
    return -1;
327
  }
328
329
  /// find_first - Returns the index of the first set bit, -1 if none
330
  /// of the bits are set.
331
21.1M
  int find_first() const { return find_first_in(0, Size); }
332
333
  /// find_last - Returns the index of the last set bit, -1 if none of the bits
334
  /// are set.
335
  int find_last() const { return find_last_in(0, Size); }
336
337
  /// find_next - Returns the index of the next set bit following the
338
  /// "Prev" bit. Returns -1 if the next set bit is not found.
339
215M
  int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); }
340
341
  /// find_prev - Returns the index of the first set bit that precedes the
342
  /// the bit at \p PriorTo.  Returns -1 if all previous bits are unset.
343
  int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); }
344
345
  /// find_first_unset - Returns the index of the first unset bit, -1 if all
346
  /// of the bits are set.
347
  int find_first_unset() const { return find_first_unset_in(0, Size); }
348
349
  /// find_next_unset - Returns the index of the next unset bit following the
350
  /// "Prev" bit.  Returns -1 if all remaining bits are set.
351
  int find_next_unset(unsigned Prev) const {
352
    return find_first_unset_in(Prev + 1, Size);
353
  }
354
355
  /// find_last_unset - Returns the index of the last unset bit, -1 if all of
356
  /// the bits are set.
357
  int find_last_unset() const { return find_last_unset_in(0, Size); }
358
359
  /// find_prev_unset - Returns the index of the first unset bit that precedes
360
  /// the bit at \p PriorTo.  Returns -1 if all previous bits are set.
361
  int find_prev_unset(unsigned PriorTo) {
362
    return find_last_unset_in(0, PriorTo);
363
  }
364
365
  /// clear - Removes all bits from the bitvector. Does not change capacity.
366
64.4M
  void clear() {
367
64.4M
    Size = 0;
368
64.4M
  }
369
370
  /// resize - Grow or shrink the bitvector.
371
96.1M
  void resize(unsigned N, bool t = false) {
372
96.1M
    if (N > getBitCapacity()) {
373
12.7M
      unsigned OldCapacity = Bits.size();
374
12.7M
      grow(N);
375
12.7M
      init_words(Bits.drop_front(OldCapacity), t);
376
12.7M
    }
377
96.1M
378
96.1M
    // Set any old unused bits that are now included in the BitVector. This
379
96.1M
    // may set bits that are not included in the new vector, but we will clear
380
96.1M
    // them back out below.
381
96.1M
    if (N > Size)
382
56.3M
      set_unused_bits(t);
383
96.1M
384
96.1M
    // Update the size, and clear out any bits that are now unused
385
96.1M
    unsigned OldSize = Size;
386
96.1M
    Size = N;
387
96.1M
    if (t || 
N < OldSize93.6M
)
388
27.7M
      clear_unused_bits();
389
96.1M
  }
390
391
  void reserve(unsigned N) {
392
    if (N > getBitCapacity())
393
      grow(N);
394
  }
395
396
  // Set, reset, flip
397
16
  BitVector &set() {
398
16
    init_words(Bits, true);
399
16
    clear_unused_bits();
400
16
    return *this;
401
16
  }
402
403
883M
  BitVector &set(unsigned Idx) {
404
883M
    assert(Bits.data() && "Bits never allocated");
405
883M
    Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
406
883M
    return *this;
407
883M
  }
408
409
  /// set - Efficiently set a range of bits in [I, E)
410
2.27k
  BitVector &set(unsigned I, unsigned E) {
411
2.27k
    assert(I <= E && "Attempted to set backwards range!");
412
2.27k
    assert(E <= size() && "Attempted to set out-of-bounds range!");
413
2.27k
414
2.27k
    if (I == E) 
return *this0
;
415
2.27k
416
2.27k
    if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
417
2.17k
      BitWord EMask = 1UL << (E % BITWORD_SIZE);
418
2.17k
      BitWord IMask = 1UL << (I % BITWORD_SIZE);
419
2.17k
      BitWord Mask = EMask - IMask;
420
2.17k
      Bits[I / BITWORD_SIZE] |= Mask;
421
2.17k
      return *this;
422
2.17k
    }
423
101
424
101
    BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
425
101
    Bits[I / BITWORD_SIZE] |= PrefixMask;
426
101
    I = alignTo(I, BITWORD_SIZE);
427
101
428
166
    for (; I + BITWORD_SIZE <= E; 
I += BITWORD_SIZE65
)
429
65
      Bits[I / BITWORD_SIZE] = ~0UL;
430
101
431
101
    BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
432
101
    if (I < E)
433
25
      Bits[I / BITWORD_SIZE] |= PostfixMask;
434
101
435
101
    return *this;
436
101
  }
437
438
32.8M
  BitVector &reset() {
439
32.8M
    init_words(Bits, false);
440
32.8M
    return *this;
441
32.8M
  }
442
443
222M
  BitVector &reset(unsigned Idx) {
444
222M
    Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
445
222M
    return *this;
446
222M
  }
447
448
  /// reset - Efficiently reset a range of bits in [I, E)
449
1.04k
  BitVector &reset(unsigned I, unsigned E) {
450
1.04k
    assert(I <= E && "Attempted to reset backwards range!");
451
1.04k
    assert(E <= size() && "Attempted to reset out-of-bounds range!");
452
1.04k
453
1.04k
    if (I == E) 
return *this0
;
454
1.04k
455
1.04k
    if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
456
1.00k
      BitWord EMask = 1UL << (E % BITWORD_SIZE);
457
1.00k
      BitWord IMask = 1UL << (I % BITWORD_SIZE);
458
1.00k
      BitWord Mask = EMask - IMask;
459
1.00k
      Bits[I / BITWORD_SIZE] &= ~Mask;
460
1.00k
      return *this;
461
1.00k
    }
462
39
463
39
    BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
464
39
    Bits[I / BITWORD_SIZE] &= ~PrefixMask;
465
39
    I = alignTo(I, BITWORD_SIZE);
466
39
467
48
    for (; I + BITWORD_SIZE <= E; 
I += BITWORD_SIZE9
)
468
9
      Bits[I / BITWORD_SIZE] = 0UL;
469
39
470
39
    BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
471
39
    if (I < E)
472
6
      Bits[I / BITWORD_SIZE] &= ~PostfixMask;
473
39
474
39
    return *this;
475
39
  }
476
477
10.2k
  BitVector &flip() {
478
57.6k
    for (unsigned i = 0; i < NumBitWords(size()); 
++i47.3k
)
479
47.3k
      Bits[i] = ~Bits[i];
480
10.2k
    clear_unused_bits();
481
10.2k
    return *this;
482
10.2k
  }
483
484
  BitVector &flip(unsigned Idx) {
485
    Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
486
    return *this;
487
  }
488
489
  // Indexing.
490
734M
  reference operator[](unsigned Idx) {
491
734M
    assert (Idx < Size && "Out-of-bounds Bit access.");
492
734M
    return reference(*this, Idx);
493
734M
  }
494
495
2.52G
  bool operator[](unsigned Idx) const {
496
2.52G
    assert (Idx < Size && "Out-of-bounds Bit access.");
497
2.52G
    BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
498
2.52G
    return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
499
2.52G
  }
500
501
1.64G
  bool test(unsigned Idx) const {
502
1.64G
    return (*this)[Idx];
503
1.64G
  }
504
505
  // Push single bit to end of vector.
506
  void push_back(bool Val) {
507
    unsigned OldSize = Size;
508
    unsigned NewSize = Size + 1;
509
510
    // Resize, which will insert zeros.
511
    // If we already fit then the unused bits will be already zero.
512
    if (NewSize > getBitCapacity())
513
      resize(NewSize, false);
514
    else
515
      Size = NewSize;
516
517
    // If true, set single bit.
518
    if (Val)
519
      set(OldSize);
520
  }
521
522
  /// Test if any common bits are set.
523
4.06M
  bool anyCommon(const BitVector &RHS) const {
524
4.06M
    unsigned ThisWords = NumBitWords(size());
525
4.06M
    unsigned RHSWords  = NumBitWords(RHS.size());
526
7.81M
    for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; 
++i3.74M
)
527
4.08M
      if (Bits[i] & RHS.Bits[i])
528
337k
        return true;
529
4.06M
    
return false3.72M
;
530
4.06M
  }
531
532
  // Comparison operators.
533
2.40M
  bool operator==(const BitVector &RHS) const {
534
2.40M
    unsigned ThisWords = NumBitWords(size());
535
2.40M
    unsigned RHSWords  = NumBitWords(RHS.size());
536
2.40M
    unsigned i;
537
22.8M
    for (i = 0; i != std::min(ThisWords, RHSWords); 
++i20.4M
)
538
20.5M
      if (Bits[i] != RHS.Bits[i])
539
63.0k
        return false;
540
2.40M
541
2.40M
    // Verify that any extra words are all zeros.
542
2.40M
    
if (2.34M
i != ThisWords2.34M
) {
543
0
      for (; i != ThisWords; ++i)
544
0
        if (Bits[i])
545
0
          return false;
546
2.34M
    } else if (i != RHSWords) {
547
0
      for (; i != RHSWords; ++i)
548
0
        if (RHS.Bits[i])
549
0
          return false;
550
0
    }
551
2.34M
    return true;
552
2.34M
  }
553
554
2.36M
  bool operator!=(const BitVector &RHS) const {
555
2.36M
    return !(*this == RHS);
556
2.36M
  }
557
558
  /// Intersection, union, disjoint union.
559
44.3k
  BitVector &operator&=(const BitVector &RHS) {
560
44.3k
    unsigned ThisWords = NumBitWords(size());
561
44.3k
    unsigned RHSWords  = NumBitWords(RHS.size());
562
44.3k
    unsigned i;
563
184k
    for (i = 0; i != std::min(ThisWords, RHSWords); 
++i139k
)
564
139k
      Bits[i] &= RHS.Bits[i];
565
44.3k
566
44.3k
    // Any bits that are just in this bitvector become zero, because they aren't
567
44.3k
    // in the RHS bit vector.  Any words only in RHS are ignored because they
568
44.3k
    // are already zero in the LHS.
569
44.3k
    for (; i != ThisWords; 
++i0
)
570
0
      Bits[i] = 0;
571
44.3k
572
44.3k
    return *this;
573
44.3k
  }
574
575
  /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
576
50.6M
  BitVector &reset(const BitVector &RHS) {
577
50.6M
    unsigned ThisWords = NumBitWords(size());
578
50.6M
    unsigned RHSWords  = NumBitWords(RHS.size());
579
50.6M
    unsigned i;
580
101M
    for (i = 0; i != std::min(ThisWords, RHSWords); 
++i50.4M
)
581
50.4M
      Bits[i] &= ~RHS.Bits[i];
582
50.6M
    return *this;
583
50.6M
  }
584
585
  /// test - Check if (This - RHS) is zero.
586
  /// This is the same as reset(RHS) and any().
587
2.42M
  bool test(const BitVector &RHS) const {
588
2.42M
    unsigned ThisWords = NumBitWords(size());
589
2.42M
    unsigned RHSWords  = NumBitWords(RHS.size());
590
2.42M
    unsigned i;
591
3.36M
    for (i = 0; i != std::min(ThisWords, RHSWords); 
++i945k
)
592
959k
      if ((Bits[i] & ~RHS.Bits[i]) != 0)
593
13.2k
        return true;
594
2.42M
595
2.84M
    
for (; 2.40M
i != ThisWords ;
++i440k
)
596
1.11M
      if (Bits[i] != 0)
597
677k
        return true;
598
2.40M
599
2.40M
    
return false1.73M
;
600
2.40M
  }
601
602
55.6M
  BitVector &operator|=(const BitVector &RHS) {
603
55.6M
    if (size() < RHS.size())
604
2.87M
      resize(RHS.size());
605
111M
    for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; 
++i55.8M
)
606
55.8M
      Bits[i] |= RHS.Bits[i];
607
55.6M
    return *this;
608
55.6M
  }
609
610
  BitVector &operator^=(const BitVector &RHS) {
611
    if (size() < RHS.size())
612
      resize(RHS.size());
613
    for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
614
      Bits[i] ^= RHS.Bits[i];
615
    return *this;
616
  }
617
618
  BitVector &operator>>=(unsigned N) {
619
    assert(N <= Size);
620
    if (LLVM_UNLIKELY(empty() || N == 0))
621
      return *this;
622
623
    unsigned NumWords = NumBitWords(Size);
624
    assert(NumWords >= 1);
625
626
    wordShr(N / BITWORD_SIZE);
627
628
    unsigned BitDistance = N % BITWORD_SIZE;
629
    if (BitDistance == 0)
630
      return *this;
631
632
    // When the shift size is not a multiple of the word size, then we have
633
    // a tricky situation where each word in succession needs to extract some
634
    // of the bits from the next word and or them into this word while
635
    // shifting this word to make room for the new bits.  This has to be done
636
    // for every word in the array.
637
638
    // Since we're shifting each word right, some bits will fall off the end
639
    // of each word to the right, and empty space will be created on the left.
640
    // The final word in the array will lose bits permanently, so starting at
641
    // the beginning, work forwards shifting each word to the right, and
642
    // OR'ing in the bits from the end of the next word to the beginning of
643
    // the current word.
644
645
    // Example:
646
    //   Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
647
    //   by 4 bits.
648
    // Step 1: Word[0] >>= 4           ; 0x0ABBCCDD
649
    // Step 2: Word[0] |= 0x10000000   ; 0x1ABBCCDD
650
    // Step 3: Word[1] >>= 4           ; 0x0EEFF001
651
    // Step 4: Word[1] |= 0x50000000   ; 0x5EEFF001
652
    // Step 5: Word[2] >>= 4           ; 0x02334455
653
    // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
654
    const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
655
    const unsigned LSH = BITWORD_SIZE - BitDistance;
656
657
    for (unsigned I = 0; I < NumWords - 1; ++I) {
658
      Bits[I] >>= BitDistance;
659
      Bits[I] |= (Bits[I + 1] & Mask) << LSH;
660
    }
661
662
    Bits[NumWords - 1] >>= BitDistance;
663
664
    return *this;
665
  }
666
667
  BitVector &operator<<=(unsigned N) {
668
    assert(N <= Size);
669
    if (LLVM_UNLIKELY(empty() || N == 0))
670
      return *this;
671
672
    unsigned NumWords = NumBitWords(Size);
673
    assert(NumWords >= 1);
674
675
    wordShl(N / BITWORD_SIZE);
676
677
    unsigned BitDistance = N % BITWORD_SIZE;
678
    if (BitDistance == 0)
679
      return *this;
680
681
    // When the shift size is not a multiple of the word size, then we have
682
    // a tricky situation where each word in succession needs to extract some
683
    // of the bits from the previous word and or them into this word while
684
    // shifting this word to make room for the new bits.  This has to be done
685
    // for every word in the array.  This is similar to the algorithm outlined
686
    // in operator>>=, but backwards.
687
688
    // Since we're shifting each word left, some bits will fall off the end
689
    // of each word to the left, and empty space will be created on the right.
690
    // The first word in the array will lose bits permanently, so starting at
691
    // the end, work backwards shifting each word to the left, and OR'ing
692
    // in the bits from the end of the next word to the beginning of the
693
    // current word.
694
695
    // Example:
696
    //   Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
697
    //   by 4 bits.
698
    // Step 1: Word[2] <<= 4           ; 0x23344550
699
    // Step 2: Word[2] |= 0x0000000E   ; 0x2334455E
700
    // Step 3: Word[1] <<= 4           ; 0xEFF00110
701
    // Step 4: Word[1] |= 0x0000000A   ; 0xEFF0011A
702
    // Step 5: Word[0] <<= 4           ; 0xABBCCDD0
703
    // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
704
    const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
705
    const unsigned RSH = BITWORD_SIZE - BitDistance;
706
707
    for (int I = NumWords - 1; I > 0; --I) {
708
      Bits[I] <<= BitDistance;
709
      Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
710
    }
711
    Bits[0] <<= BitDistance;
712
    clear_unused_bits();
713
714
    return *this;
715
  }
716
717
  // Assignment operator.
718
7.66M
  const BitVector &operator=(const BitVector &RHS) {
719
7.66M
    if (this == &RHS) 
return *this0
;
720
7.66M
721
7.66M
    Size = RHS.size();
722
7.66M
    unsigned RHSWords = NumBitWords(Size);
723
7.66M
    if (Size <= getBitCapacity()) {
724
5.51M
      if (Size)
725
5.51M
        std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord));
726
5.51M
      clear_unused_bits();
727
5.51M
      return *this;
728
5.51M
    }
729
2.14M
730
2.14M
    // Grow the bitvector to have enough elements.
731
2.14M
    unsigned NewCapacity = RHSWords;
732
2.14M
    assert(NewCapacity > 0 && "negative capacity?");
733
2.14M
    auto NewBits = allocate(NewCapacity);
734
2.14M
    std::memcpy(NewBits.data(), RHS.Bits.data(), NewCapacity * sizeof(BitWord));
735
2.14M
736
2.14M
    // Destroy the old bits.
737
2.14M
    std::free(Bits.data());
738
2.14M
    Bits = NewBits;
739
2.14M
740
2.14M
    return *this;
741
2.14M
  }
742
743
10.9M
  const BitVector &operator=(BitVector &&RHS) {
744
10.9M
    if (this == &RHS) 
return *this0
;
745
10.9M
746
10.9M
    std::free(Bits.data());
747
10.9M
    Bits = RHS.Bits;
748
10.9M
    Size = RHS.Size;
749
10.9M
750
10.9M
    RHS.Bits = MutableArrayRef<BitWord>();
751
10.9M
    RHS.Size = 0;
752
10.9M
753
10.9M
    return *this;
754
10.9M
  }
755
756
  void swap(BitVector &RHS) {
757
    std::swap(Bits, RHS.Bits);
758
    std::swap(Size, RHS.Size);
759
  }
760
761
  //===--------------------------------------------------------------------===//
762
  // Portable bit mask operations.
763
  //===--------------------------------------------------------------------===//
764
  //
765
  // These methods all operate on arrays of uint32_t, each holding 32 bits. The
766
  // fixed word size makes it easier to work with literal bit vector constants
767
  // in portable code.
768
  //
769
  // The LSB in each word is the lowest numbered bit.  The size of a portable
770
  // bit mask is always a whole multiple of 32 bits.  If no bit mask size is
771
  // given, the bit mask is assumed to cover the entire BitVector.
772
773
  /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
774
  /// This computes "*this |= Mask".
775
3.32M
  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
776
3.32M
    applyMask<true, false>(Mask, MaskWords);
777
3.32M
  }
778
779
  /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
780
  /// Don't resize. This computes "*this &= ~Mask".
781
  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
782
    applyMask<false, false>(Mask, MaskWords);
783
  }
784
785
  /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
786
  /// Don't resize.  This computes "*this |= ~Mask".
787
2.00M
  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
788
2.00M
    applyMask<true, true>(Mask, MaskWords);
789
2.00M
  }
790
791
  /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
792
  /// Don't resize.  This computes "*this &= Mask".
793
29.4M
  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
794
29.4M
    applyMask<false, true>(Mask, MaskWords);
795
29.4M
  }
796
797
private:
798
  /// Perform a logical left shift of \p Count words by moving everything
799
  /// \p Count words to the right in memory.
800
  ///
801
  /// While confusing, words are stored from least significant at Bits[0] to
802
  /// most significant at Bits[NumWords-1].  A logical shift left, however,
803
  /// moves the current least significant bit to a higher logical index, and
804
  /// fills the previous least significant bits with 0.  Thus, we actually
805
  /// need to move the bytes of the memory to the right, not to the left.
806
  /// Example:
807
  ///   Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
808
  /// represents a BitVector where 0xBBBBAAAA contain the least significant
809
  /// bits.  So if we want to shift the BitVector left by 2 words, we need to
810
  /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
811
  /// memmove which moves right, not left.
812
  void wordShl(uint32_t Count) {
813
    if (Count == 0)
814
      return;
815
816
    uint32_t NumWords = NumBitWords(Size);
817
818
    auto Src = Bits.take_front(NumWords).drop_back(Count);
819
    auto Dest = Bits.take_front(NumWords).drop_front(Count);
820
821
    // Since we always move Word-sized chunks of data with src and dest both
822
    // aligned to a word-boundary, we don't need to worry about endianness
823
    // here.
824
    std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
825
    std::memset(Bits.data(), 0, Count * sizeof(BitWord));
826
    clear_unused_bits();
827
  }
828
829
  /// Perform a logical right shift of \p Count words by moving those
830
  /// words to the left in memory.  See wordShl for more information.
831
  ///
832
  void wordShr(uint32_t Count) {
833
    if (Count == 0)
834
      return;
835
836
    uint32_t NumWords = NumBitWords(Size);
837
838
    auto Src = Bits.take_front(NumWords).drop_front(Count);
839
    auto Dest = Bits.take_front(NumWords).drop_back(Count);
840
    assert(Dest.size() == Src.size());
841
842
    std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
843
    std::memset(Dest.end(), 0, Count * sizeof(BitWord));
844
  }
845
846
55.6M
  MutableArrayRef<BitWord> allocate(size_t NumWords) {
847
55.6M
    BitWord *RawBits = static_cast<BitWord *>(
848
55.6M
        safe_malloc(NumWords * sizeof(BitWord)));
849
55.6M
    return MutableArrayRef<BitWord>(RawBits, NumWords);
850
55.6M
  }
851
852
  int next_unset_in_word(int WordIndex, BitWord Word) const {
853
    unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
854
    return Result < size() ? Result : -1;
855
  }
856
857
380M
  unsigned NumBitWords(unsigned S) const {
858
380M
    return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
859
380M
  }
860
861
  // Set the unused bits in the high words.
862
107M
  void set_unused_bits(bool t = true) {
863
107M
    //  Set high words first.
864
107M
    unsigned UsedWords = NumBitWords(Size);
865
107M
    if (Bits.size() > UsedWords)
866
83.2M
      init_words(Bits.drop_front(UsedWords), t);
867
107M
868
107M
    //  Then set any stray high bits of the last used word.
869
107M
    unsigned ExtraBits = Size % BITWORD_SIZE;
870
107M
    if (ExtraBits) {
871
39.6M
      BitWord ExtraBitMask = ~0UL << ExtraBits;
872
39.6M
      if (t)
873
1.58k
        Bits[UsedWords-1] |= ExtraBitMask;
874
39.6M
      else
875
39.6M
        Bits[UsedWords-1] &= ~ExtraBitMask;
876
39.6M
    }
877
107M
  }
878
879
  // Clear the unused bits in the high words.
880
51.4M
  void clear_unused_bits() {
881
51.4M
    set_unused_bits(false);
882
51.4M
  }
883
884
12.7M
  void grow(unsigned NewSize) {
885
12.7M
    size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize), Bits.size() * 2);
886
12.7M
    assert(NewCapacity > 0 && "realloc-ing zero space");
887
12.7M
    BitWord *NewBits = static_cast<BitWord *>(
888
12.7M
        safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord)));
889
12.7M
    Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
890
12.7M
    clear_unused_bits();
891
12.7M
  }
892
893
173M
  void init_words(MutableArrayRef<BitWord> B, bool t) {
894
173M
    if (B.size() > 0)
895
172M
      memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord));
896
173M
  }
897
898
  template<bool AddBits, bool InvertMask>
899
34.7M
  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
900
34.7M
    static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
901
34.7M
    MaskWords = std::min(MaskWords, (size() + 31) / 32);
902
34.7M
    const unsigned Scale = BITWORD_SIZE / 32;
903
34.7M
    unsigned i;
904
337M
    for (i = 0; MaskWords >= Scale; 
++i, MaskWords -= Scale302M
) {
905
302M
      BitWord BW = Bits[i];
906
302M
      // This inner loop should unroll completely when BITWORD_SIZE > 32.
907
907M
      for (unsigned b = 0; b != BITWORD_SIZE; 
b += 32605M
) {
908
605M
        uint32_t M = *Mask++;
909
605M
        if (InvertMask) 
M = ~M594M
;
910
605M
        if (AddBits) 
BW |= BitWord(M) << b46.6M
;
911
558M
        else         BW &= ~(BitWord(M) << b);
912
605M
      }
913
302M
      Bits[i] = BW;
914
302M
    }
915
36.9M
    for (unsigned b = 0; MaskWords; 
b += 32, --MaskWords2.22M
) {
916
2.22M
      uint32_t M = *Mask++;
917
2.22M
      if (InvertMask) 
M = ~M2.07M
;
918
2.22M
      if (AddBits) 
Bits[i] |= BitWord(M) << b443k
;
919
1.78M
      else         Bits[i] &= ~(BitWord(M) << b);
920
2.22M
    }
921
34.7M
    if (AddBits)
922
5.33M
      clear_unused_bits();
923
34.7M
  }
void llvm::BitVector::applyMask<false, true>(unsigned int const*, unsigned int)
Line
Count
Source
899
29.4M
  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
900
29.4M
    static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
901
29.4M
    MaskWords = std::min(MaskWords, (size() + 31) / 32);
902
29.4M
    const unsigned Scale = BITWORD_SIZE / 32;
903
29.4M
    unsigned i;
904
308M
    for (i = 0; MaskWords >= Scale; 
++i, MaskWords -= Scale279M
) {
905
279M
      BitWord BW = Bits[i];
906
279M
      // This inner loop should unroll completely when BITWORD_SIZE > 32.
907
837M
      for (unsigned b = 0; b != BITWORD_SIZE; 
b += 32558M
) {
908
558M
        uint32_t M = *Mask++;
909
558M
        if (
InvertMask558M
) M = ~M;
910
558M
        if (AddBits) 
BW |= BitWord(M) << b0
;
911
558M
        else         BW &= ~(BitWord(M) << b);
912
558M
      }
913
279M
      Bits[i] = BW;
914
279M
    }
915
31.2M
    for (unsigned b = 0; MaskWords; 
b += 32, --MaskWords1.78M
) {
916
1.78M
      uint32_t M = *Mask++;
917
1.78M
      if (InvertMask) M = ~M;
918
1.78M
      if (AddBits) 
Bits[i] |= BitWord(M) << b0
;
919
1.78M
      else         Bits[i] &= ~(BitWord(M) << b);
920
1.78M
    }
921
29.4M
    if (AddBits)
922
0
      clear_unused_bits();
923
29.4M
  }
void llvm::BitVector::applyMask<true, false>(unsigned int const*, unsigned int)
Line
Count
Source
899
3.32M
  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
900
3.32M
    static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
901
3.32M
    MaskWords = std::min(MaskWords, (size() + 31) / 32);
902
3.32M
    const unsigned Scale = BITWORD_SIZE / 32;
903
3.32M
    unsigned i;
904
8.91M
    for (i = 0; MaskWords >= Scale; 
++i, MaskWords -= Scale5.58M
) {
905
5.58M
      BitWord BW = Bits[i];
906
5.58M
      // This inner loop should unroll completely when BITWORD_SIZE > 32.
907
16.7M
      for (unsigned b = 0; b != BITWORD_SIZE; 
b += 3211.1M
) {
908
11.1M
        uint32_t M = *Mask++;
909
11.1M
        if (InvertMask) 
M = ~M0
;
910
11.1M
        if (
AddBits11.1M
) BW |= BitWord(M) << b;
911
18.4E
        else         BW &= ~(BitWord(M) << b);
912
11.1M
      }
913
5.58M
      Bits[i] = BW;
914
5.58M
    }
915
3.47M
    for (unsigned b = 0; MaskWords; 
b += 32, --MaskWords148k
) {
916
148k
      uint32_t M = *Mask++;
917
148k
      if (InvertMask) 
M = ~M0
;
918
148k
      if (AddBits) Bits[i] |=   BitWord(M) << b;
919
0
      else         Bits[i] &= ~(BitWord(M) << b);
920
148k
    }
921
3.32M
    if (AddBits)
922
3.32M
      clear_unused_bits();
923
3.32M
  }
Unexecuted instantiation: void llvm::BitVector::applyMask<false, false>(unsigned int const*, unsigned int)
void llvm::BitVector::applyMask<true, true>(unsigned int const*, unsigned int)
Line
Count
Source
899
2.00M
  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
900
2.00M
    static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
901
2.00M
    MaskWords = std::min(MaskWords, (size() + 31) / 32);
902
2.00M
    const unsigned Scale = BITWORD_SIZE / 32;
903
2.00M
    unsigned i;
904
19.7M
    for (i = 0; MaskWords >= Scale; 
++i, MaskWords -= Scale17.7M
) {
905
17.7M
      BitWord BW = Bits[i];
906
17.7M
      // This inner loop should unroll completely when BITWORD_SIZE > 32.
907
53.2M
      for (unsigned b = 0; b != BITWORD_SIZE; 
b += 3235.4M
) {
908
35.4M
        uint32_t M = *Mask++;
909
35.4M
        if (InvertMask) M = ~M;
910
35.4M
        if (AddBits) BW |=   BitWord(M) << b;
911
0
        else         BW &= ~(BitWord(M) << b);
912
35.4M
      }
913
17.7M
      Bits[i] = BW;
914
17.7M
    }
915
2.30M
    for (unsigned b = 0; MaskWords; 
b += 32, --MaskWords294k
) {
916
294k
      uint32_t M = *Mask++;
917
294k
      if (InvertMask) M = ~M;
918
294k
      if (AddBits) Bits[i] |=   BitWord(M) << b;
919
0
      else         Bits[i] &= ~(BitWord(M) << b);
920
294k
    }
921
2.00M
    if (AddBits)
922
2.00M
      clear_unused_bits();
923
2.00M
  }
924
925
public:
926
  /// Return the size (in bytes) of the bit vector.
927
1
  size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
928
372M
  size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
929
};
930
931
1
inline size_t capacity_in_bytes(const BitVector &X) {
932
1
  return X.getMemorySize();
933
1
}
934
935
} // end namespace llvm
936
937
namespace std {
938
  /// Implement std::swap in terms of BitVector swap.
939
  inline void
940
  swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
941
    LHS.swap(RHS);
942
  }
943
} // end namespace std
944
945
#endif // LLVM_ADT_BITVECTOR_H