LCOV - code coverage report
Current view: top level - include/llvm/ADT - BitVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 298 303 98.3 %
Date: 2018-02-23 15:42:53 Functions: 29 29 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13