LCOV - code coverage report
Current view: top level - include/llvm/ADT - BitVector.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 333 338 98.5 %
Date: 2017-09-14 15:23:50 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    79396047 :     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     2158896 :   explicit const_set_bits_iterator_impl(const BitVectorT &Parent)
      45     2177961 :       : 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    39713366 :     advance();
      56             :     return *this;
      57             :   }
      58             : 
      59    39713607 :   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     7282856 :       WordRef = &b.Bits[Idx / BITWORD_SIZE];
      97     3034562 :       BitPos = Idx % BITWORD_SIZE;
      98             :     }
      99             : 
     100             :     reference() = delete;
     101             :     reference(const reference&) = default;
     102             : 
     103             :     reference &operator=(reference t) {
     104           8 :       *this = bool(t);
     105             :       return *this;
     106             :     }
     107             : 
     108             :     reference& operator=(bool t) {
     109         200 :       if (t)
     110      642807 :         *WordRef |= BitWord(1) << BitPos;
     111             :       else
     112      262689 :         *WordRef &= ~(BitWord(1) << BitPos);
     113             :       return *this;
     114             :     }
     115             : 
     116             :     operator bool() const {
     117     2736337 :       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     2158896 :     return const_set_bits_iterator(*this);
     126             :   }
     127             :   const_set_bits_iterator set_bits_end() const {
     128     2158895 :     return const_set_bits_iterator(*this, -1);
     129             :   }
     130             :   iterator_range<const_set_bits_iterator> set_bits() const {
     131     6476670 :     return make_range(set_bits_begin(), set_bits_end());
     132             :   }
     133             : 
     134             :   /// BitVector default ctor - Creates an empty bitvector.
     135    19444632 :   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    25222708 :   explicit BitVector(unsigned s, bool t = false) : Size(s) {
     140    25222708 :     size_t Capacity = NumBitWords(s);
     141    25222708 :     Bits = allocate(Capacity);
     142    25222708 :     init_words(Bits, t);
     143    12611354 :     if (t)
     144             :       clear_unused_bits();
     145    12611354 :   }
     146             : 
     147             :   /// BitVector copy ctor.
     148     3745226 :   BitVector(const BitVector &RHS) : Size(RHS.size()) {
     149     1872613 :     if (Size == 0) {
     150       18340 :       Bits = MutableArrayRef<BitWord>();
     151       18340 :       return;
     152             :     }
     153             : 
     154     3708546 :     size_t Capacity = NumBitWords(RHS.size());
     155     3708546 :     Bits = allocate(Capacity);
     156     5562819 :     std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord));
     157             :   }
     158             : 
     159      500033 :   BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) {
     160      500033 :     RHS.Bits = MutableArrayRef<BitWord>();
     161      341342 :     RHS.Size = 0;
     162             :   }
     163             : 
     164    49348372 :   ~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        4180 :     unsigned NumBits = 0;
     175      910046 :     for (unsigned i = 0; i < NumBitWords(size()); ++i)
     176      665061 :       NumBits += countPopulation(Bits[i]);
     177             :     return NumBits;
     178             :   }
     179             : 
     180             :   /// any - Returns true if any bit is set.
     181             :   bool any() const {
     182     1392608 :     for (unsigned i = 0; i < NumBitWords(size()); ++i)
     183      932520 :       if (Bits[i] != 0)
     184             :         return true;
     185             :     return false;
     186             :   }
     187             : 
     188             :   /// all - Returns true if all bits are set.
     189        2163 :   bool all() const {
     190        2169 :     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        2159 :     if (unsigned Remainder = Size % BITWORD_SIZE)
     196        4296 :       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      107741 :     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    44186964 :   int find_first_in(unsigned Begin, unsigned End) const {
     209             :     assert(Begin <= End && End <= Size);
     210    44186964 :     if (Begin == End)
     211             :       return -1;
     212             : 
     213    43976653 :     unsigned FirstWord = Begin / BITWORD_SIZE;
     214    43976653 :     unsigned LastWord = (End - 1) / BITWORD_SIZE;
     215             : 
     216             :     // Check subsequent words.
     217    86549097 :     for (unsigned i = FirstWord; i <= LastWord; ++i) {
     218   168792562 :       BitWord Copy = Bits[i];
     219             : 
     220    84396270 :       if (i == FirstWord) {
     221    43976651 :         unsigned FirstBit = Begin % BITWORD_SIZE;
     222    43976651 :         Copy &= maskTrailingZeros<BitWord>(FirstBit);
     223             :       }
     224             : 
     225    84396270 :       if (i == LastWord) {
     226    11787192 :         unsigned LastBit = (End - 1) % BITWORD_SIZE;
     227    23574384 :         Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
     228             :       }
     229    84396281 :       if (Copy != 0)
     230    83647668 :         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          39 :     unsigned LastWord = (End - 1) / BITWORD_SIZE;
     243          39 :     unsigned FirstWord = Begin / BITWORD_SIZE;
     244             : 
     245          39 :     for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
     246          44 :       unsigned CurrentWord = i - 1;
     247             : 
     248          88 :       BitWord Copy = Bits[CurrentWord];
     249          33 :       if (CurrentWord == LastWord) {
     250          39 :         unsigned LastBit = (End - 1) % BITWORD_SIZE;
     251          78 :         Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
     252             :       }
     253             : 
     254          33 :       if (CurrentWord == FirstWord) {
     255          26 :         unsigned FirstBit = Begin % BITWORD_SIZE;
     256          26 :         Copy &= maskTrailingZeros<BitWord>(FirstBit);
     257             :       }
     258             : 
     259          44 :       if (Copy != 0)
     260          58 :         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          58 :     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     2386827 :   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    41800137 :   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     8195737 :     Size = 0;
     369             :   }
     370             : 
     371             :   /// resize - Grow or shrink the bitvector.
     372     8737382 :   void resize(unsigned N, bool t = false) {
     373    17474764 :     if (N > getBitCapacity()) {
     374     2637913 :       unsigned OldCapacity = Bits.size();
     375     2637913 :       grow(N);
     376     5275826 :       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     8737382 :     if (N > Size)
     383     8525742 :       set_unused_bits(t);
     384             : 
     385             :     // Update the size, and clear out any bits that are now unused
     386     8737382 :     unsigned OldSize = Size;
     387     8737382 :     Size = N;
     388     8737382 :     if (t || N < OldSize)
     389             :       clear_unused_bits();
     390     8737382 :   }
     391             : 
     392             :   void reserve(unsigned N) {
     393             :     if (N > getBitCapacity())
     394             :       grow(N);
     395             :   }
     396             : 
     397             :   // Set, reset, flip
     398          16 :   BitVector &set() {
     399          16 :     init_words(Bits, true);
     400          16 :     clear_unused_bits();
     401          16 :     return *this;
     402             :   }
     403             : 
     404             :   BitVector &set(unsigned Idx) {
     405             :     assert(Bits.data() && "Bits never allocated");
     406   135596529 :     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        1734 :   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        1734 :     if (I == E) return *this;
     416             : 
     417        1734 :     if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
     418        1636 :       BitWord EMask = 1UL << (E % BITWORD_SIZE);
     419        1636 :       BitWord IMask = 1UL << (I % BITWORD_SIZE);
     420        1636 :       BitWord Mask = EMask - IMask;
     421        3272 :       Bits[I / BITWORD_SIZE] |= Mask;
     422        1636 :       return *this;
     423             :     }
     424             : 
     425          98 :     BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
     426         196 :     Bits[I / BITWORD_SIZE] |= PrefixMask;
     427         196 :     I = alignTo(I, BITWORD_SIZE);
     428             : 
     429         214 :     for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
     430         116 :       Bits[I / BITWORD_SIZE] = ~0UL;
     431             : 
     432          98 :     BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
     433          98 :     if (I < E)
     434          50 :       Bits[I / BITWORD_SIZE] |= PostfixMask;
     435             : 
     436             :     return *this;
     437             :   }
     438             : 
     439             :   BitVector &reset() {
     440      548010 :     init_words(Bits, false);
     441             :     return *this;
     442             :   }
     443             : 
     444             :   BitVector &reset(unsigned Idx) {
     445    65344930 :     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         366 :   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         366 :     if (I == E) return *this;
     455             : 
     456         366 :     if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
     457         353 :       BitWord EMask = 1UL << (E % BITWORD_SIZE);
     458         353 :       BitWord IMask = 1UL << (I % BITWORD_SIZE);
     459         353 :       BitWord Mask = EMask - IMask;
     460         706 :       Bits[I / BITWORD_SIZE] &= ~Mask;
     461         353 :       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       13974 :   BitVector &flip() {
     479      151768 :     for (unsigned i = 0; i < NumBitWords(size()); ++i)
     480      185730 :       Bits[i] = ~Bits[i];
     481       13974 :     clear_unused_bits();
     482       13974 :     return *this;
     483             :   }
     484             : 
     485             :   BitVector &flip(unsigned Idx) {
     486           8 :     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     3641428 :     return reference(*this, Idx);
     494             :   }
     495             : 
     496             :   bool operator[](unsigned Idx) const {
     497             :     assert (Idx < Size && "Out-of-bounds Bit access.");
     498   228038351 :     BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
     499   456076702 :     return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
     500             :   }
     501             : 
     502             :   bool test(unsigned Idx) const {
     503   106878765 :     return (*this)[Idx];
     504             :   }
     505             : 
     506             :   /// Test if any common bits are set.
     507     1859036 :   bool anyCommon(const BitVector &RHS) const {
     508     3718072 :     unsigned ThisWords = NumBitWords(size());
     509     3718072 :     unsigned RHSWords  = NumBitWords(RHS.size());
     510     5335271 :     for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
     511     5586099 :       if (Bits[i] & RHS.Bits[i])
     512             :         return true;
     513             :     return false;
     514             :   }
     515             : 
     516             :   // Comparison operators.
     517      704421 :   bool operator==(const BitVector &RHS) const {
     518     1408842 :     unsigned ThisWords = NumBitWords(size());
     519     1408842 :     unsigned RHSWords  = NumBitWords(RHS.size());
     520             :     unsigned i;
     521    15003438 :     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
     522    20501367 :       if (Bits[i] != RHS.Bits[i])
     523             :         return false;
     524             : 
     525             :     // Verify that any extra words are all zeros.
     526      667930 :     if (i != ThisWords) {
     527           0 :       for (; i != ThisWords; ++i)
     528           0 :         if (Bits[i])
     529             :           return false;
     530      667930 :     } 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      682818 :     return !(*this == RHS);
     540             :   }
     541             : 
     542             :   /// Intersection, union, disjoint union.
     543       19616 :   BitVector &operator&=(const BitVector &RHS) {
     544       39232 :     unsigned ThisWords = NumBitWords(size());
     545       39232 :     unsigned RHSWords  = NumBitWords(RHS.size());
     546             :     unsigned i;
     547      201832 :     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
     548      243900 :       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       19616 :     for (; i != ThisWords; ++i)
     554           0 :       Bits[i] = 0;
     555             : 
     556       19616 :     return *this;
     557             :   }
     558             : 
     559             :   /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
     560    14294436 :   BitVector &reset(const BitVector &RHS) {
     561    28588872 :     unsigned ThisWords = NumBitWords(size());
     562    28588872 :     unsigned RHSWords  = NumBitWords(RHS.size());
     563             :     unsigned i;
     564    57548924 :     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
     565    43440078 :       Bits[i] &= ~RHS.Bits[i];
     566    14294436 :     return *this;
     567             :   }
     568             : 
     569             :   /// test - Check if (This - RHS) is zero.
     570             :   /// This is the same as reset(RHS) and any().
     571      482420 :   bool test(const BitVector &RHS) const {
     572      964840 :     unsigned ThisWords = NumBitWords(size());
     573      964840 :     unsigned RHSWords  = NumBitWords(RHS.size());
     574             :     unsigned i;
     575     1800974 :     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
     576     1263570 :       if ((Bits[i] & ~RHS.Bits[i]) != 0)
     577             :         return true;
     578             : 
     579      513751 :     for (; i != ThisWords ; ++i)
     580      379424 :       if (Bits[i] != 0)
     581             :         return true;
     582             : 
     583             :     return false;
     584             :   }
     585             : 
     586    15131499 :   BitVector &operator|=(const BitVector &RHS) {
     587    15131499 :     if (size() < RHS.size())
     588      537485 :       resize(RHS.size());
     589    46206228 :     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
     590    47829684 :       Bits[i] |= RHS.Bits[i];
     591    15131500 :     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          12 :       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          16 :     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           6 :     const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
     639           6 :     const unsigned LSH = BITWORD_SIZE - BitDistance;
     640             : 
     641          14 :     for (unsigned I = 0; I < NumWords - 1; ++I) {
     642          16 :       Bits[I] >>= BitDistance;
     643          24 :       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          18 :     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           7 :     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          48 :       Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
     694             :     }
     695          14 :     Bits[0] <<= BitDistance;
     696           7 :     clear_unused_bits();
     697             : 
     698           7 :     return *this;
     699             :   }
     700             : 
     701             :   // Assignment operator.
     702     1883899 :   const BitVector &operator=(const BitVector &RHS) {
     703     1883899 :     if (this == &RHS) return *this;
     704             : 
     705     1883812 :     Size = RHS.size();
     706     3767624 :     unsigned RHSWords = NumBitWords(Size);
     707     3767624 :     if (Size <= getBitCapacity()) {
     708      629368 :       if (Size)
     709     1888038 :         std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord));
     710      629368 :       clear_unused_bits();
     711      629368 :       return *this;
     712             :     }
     713             : 
     714             :     // Grow the bitvector to have enough elements.
     715     1254444 :     unsigned NewCapacity = RHSWords;
     716             :     assert(NewCapacity > 0 && "negative capacity?");
     717     2508888 :     auto NewBits = allocate(NewCapacity);
     718     3763332 :     std::memcpy(NewBits.data(), RHS.Bits.data(), NewCapacity * sizeof(BitWord));
     719             : 
     720             :     // Destroy the old bits.
     721     2508888 :     std::free(Bits.data());
     722     1254444 :     Bits = NewBits;
     723             : 
     724     1254444 :     return *this;
     725             :   }
     726             : 
     727             :   const BitVector &operator=(BitVector &&RHS) {
     728        3283 :     if (this == &RHS) return *this;
     729             : 
     730     9953978 :     std::free(Bits.data());
     731     4976989 :     Bits = RHS.Bits;
     732     4976989 :     Size = RHS.Size;
     733             : 
     734     4976989 :     RHS.Bits = MutableArrayRef<BitWord>();
     735         699 :     RHS.Size = 0;
     736             : 
     737             :     return *this;
     738             :   }
     739             : 
     740             :   void swap(BitVector &RHS) {
     741           4 :     std::swap(Bits, RHS.Bits);
     742           4 :     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     1115601 :     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      315857 :     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     3130843 :     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           5 :       return;
     799             : 
     800           8 :     uint32_t NumWords = NumBitWords(Size);
     801             : 
     802          12 :     auto Src = Bits.take_front(NumWords).drop_back(Count);
     803          12 :     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          12 :     std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
     809           8 :     std::memset(Bits.data(), 0, Count * sizeof(BitWord));
     810           4 :     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           4 :       return;
     819             : 
     820           8 :     uint32_t NumWords = NumBitWords(Size);
     821             : 
     822          12 :     auto Src = Bits.take_front(NumWords).drop_front(Count);
     823          12 :     auto Dest = Bits.take_front(NumWords).drop_back(Count);
     824             :     assert(Dest.size() == Src.size());
     825             : 
     826          12 :     std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
     827           8 :     std::memset(Dest.end(), 0, Count * sizeof(BitWord));
     828             :   }
     829             : 
     830             :   MutableArrayRef<BitWord> allocate(size_t NumWords) {
     831    15720071 :     BitWord *RawBits = (BitWord *)std::malloc(NumWords * sizeof(BitWord));
     832    15720071 :     return MutableArrayRef<BitWord>(RawBits, NumWords);
     833             :   }
     834             : 
     835             :   int next_unset_in_word(int WordIndex, BitWord Word) const {
     836             :     unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
     837             :     return Result < size() ? Result : -1;
     838             :   }
     839             : 
     840             :   unsigned NumBitWords(unsigned S) const {
     841    83370943 :     return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
     842             :   }
     843             : 
     844             :   // Set the unused bits in the high words.
     845    13482259 :   void set_unused_bits(bool t = true) {
     846             :     //  Set high words first.
     847    26964518 :     unsigned UsedWords = NumBitWords(Size);
     848    13482259 :     if (Bits.size() > UsedWords)
     849    22087110 :       init_words(Bits.drop_front(UsedWords), t);
     850             : 
     851             :     //  Then set any stray high bits of the last used word.
     852    13482259 :     unsigned ExtraBits = Size % BITWORD_SIZE;
     853    13482259 :     if (ExtraBits) {
     854     2459358 :       BitWord ExtraBitMask = ~0UL << ExtraBits;
     855     2459358 :       if (t)
     856        1430 :         Bits[UsedWords-1] |= ExtraBitMask;
     857             :       else
     858     4917286 :         Bits[UsedWords-1] &= ~ExtraBitMask;
     859             :     }
     860    13482259 :   }
     861             : 
     862             :   // Clear the unused bits in the high words.
     863             :   void clear_unused_bits() {
     864     4956517 :     set_unused_bits(false);
     865             :   }
     866             : 
     867     2637913 :   void grow(unsigned NewSize) {
     868     7913739 :     size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize), Bits.size() * 2);
     869             :     assert(NewCapacity > 0 && "realloc-ing zero space");
     870             :     BitWord *NewBits =
     871     5275826 :         (BitWord *)std::realloc(Bits.data(), NewCapacity * sizeof(BitWord));
     872     2637913 :     Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
     873     2637913 :     clear_unused_bits();
     874     2637913 :   }
     875             : 
     876             :   void init_words(MutableArrayRef<BitWord> B, bool t) {
     877    26866037 :     if (B.size() > 0)
     878    53721034 :       memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord));
     879             :   }
     880             : 
     881             :   template<bool AddBits, bool InvertMask>
     882     4562301 :   void applyMask(const uint32_t *Mask, unsigned MaskWords) {
     883             :     static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
     884     9124602 :     MaskWords = std::min(MaskWords, (size() + 31) / 32);
     885     4562301 :     const unsigned Scale = BITWORD_SIZE / 32;
     886             :     unsigned i;
     887    20084503 :     for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
     888    31044404 :       BitWord BW = Bits[i];
     889             :       // This inner loop should unroll completely when BITWORD_SIZE > 32.
     890    46566606 :       for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
     891    31044404 :         uint32_t M = *Mask++;
     892    28262188 :         if (InvertMask) M = ~M;
     893     5410342 :         if (AddBits) BW |=   BitWord(M) << b;
     894    25634062 :         else         BW &= ~(BitWord(M) << b);
     895             :       }
     896    31044404 :       Bits[i] = BW;
     897             :     }
     898     5496421 :     for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
     899      467060 :       uint32_t M = *Mask++;
     900        6891 :       if (InvertMask) M = ~M;
     901      922794 :       if (AddBits) Bits[i] |=   BitWord(M) << b;
     902       11326 :       else         Bits[i] &= ~(BitWord(M) << b);
     903             :     }
     904             :     if (AddBits)
     905     1431458 :       clear_unused_bits();
     906     4562301 :   }
     907             : 
     908             : public:
     909             :   /// Return the size (in bytes) of the bit vector.
     910           1 :   size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
     911    10621194 :   size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
     912             : };
     913             : 
     914             : static inline size_t capacity_in_bytes(const BitVector &X) {
     915           1 :   return X.getMemorySize();
     916             : }
     917             : 
     918             : } // end namespace llvm
     919             : 
     920             : namespace std {
     921             :   /// Implement std::swap in terms of BitVector swap.
     922             :   inline void
     923             :   swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
     924           2 :     LHS.swap(RHS);
     925             :   }
     926             : } // end namespace std
     927             : 
     928             : #endif // LLVM_ADT_BITVECTOR_H

Generated by: LCOV version 1.13