OLD | NEW |
(Empty) | |
| 1 //===- subzero/src/IceBitVector.h - Inline bit vector. ----------*- C++ -*-===// |
| 2 // |
| 3 // The Subzero Code Generator |
| 4 // |
| 5 // This file is distributed under the University of Illinois Open Source |
| 6 // License. See LICENSE.TXT for details. |
| 7 // |
| 8 //===----------------------------------------------------------------------===// |
| 9 /// |
| 10 /// \file |
| 11 /// \brief Defines and implements a bit vector with inline storage. It is a drop |
| 12 /// in replacement for llvm::SmallBitVector in subzero -- i.e., not all of |
| 13 /// llvm::SmallBitVector interface is implemented. |
| 14 /// |
| 15 //===----------------------------------------------------------------------===// |
| 16 |
| 17 #ifndef SUBZERO_SRC_ICEBITVECTOR_H |
| 18 #define SUBZERO_SRC_ICEBITVECTOR_H |
| 19 |
| 20 #include "IceDefs.h" |
| 21 #include "IceOperand.h" |
| 22 |
| 23 #include "llvm/Support/MathExtras.h" |
| 24 |
| 25 #include <algorithm> |
| 26 #include <climits> |
| 27 #include <memory> |
| 28 #include <type_traits> |
| 29 |
| 30 namespace Ice { |
| 31 class SmallBitVector { |
| 32 public: |
| 33 using ElementType = uint64_t; |
| 34 static constexpr SizeT BitIndexSize = 6; // log2(NumBitsPerPos); |
| 35 static constexpr SizeT NumBitsPerPos = sizeof(ElementType) * CHAR_BIT; |
| 36 static_assert(1 << BitIndexSize == NumBitsPerPos, "Invalid BitIndexSize."); |
| 37 |
| 38 SmallBitVector(const SmallBitVector &BV) { *this = BV; } |
| 39 |
| 40 SmallBitVector &operator=(const SmallBitVector &BV) { |
| 41 if (&BV != this) { |
| 42 resize(BV.size()); |
| 43 memcpy(Bits, BV.Bits, sizeof(Bits)); |
| 44 } |
| 45 return *this; |
| 46 } |
| 47 |
| 48 SmallBitVector() { reset(); } |
| 49 |
| 50 explicit SmallBitVector(SizeT S) : SmallBitVector() { |
| 51 assert(S <= MaxBits); |
| 52 resize(S); |
| 53 } |
| 54 |
| 55 class Reference { |
| 56 Reference() = delete; |
| 57 |
| 58 public: |
| 59 Reference(const Reference &) = default; |
| 60 Reference &operator=(const Reference &Rhs) { return *this = (bool)Rhs; } |
| 61 Reference &operator=(bool t) { |
| 62 if (t) { |
| 63 *Data |= _1 << Bit; |
| 64 } else { |
| 65 *Data &= ~(_1 << Bit); |
| 66 } |
| 67 return *this; |
| 68 } |
| 69 operator bool() const { return (*Data & (_1 << Bit)) != 0; } |
| 70 |
| 71 private: |
| 72 friend class SmallBitVector; |
| 73 Reference(ElementType *D, SizeT B) : Data(D), Bit(B) { |
| 74 assert(B < NumBitsPerPos); |
| 75 } |
| 76 |
| 77 ElementType *const Data; |
| 78 const SizeT Bit; |
| 79 }; |
| 80 |
| 81 Reference operator[](unsigned Idx) { |
| 82 assert(Idx < size()); |
| 83 return Reference(Bits + (Idx >> BitIndexSize), |
| 84 Idx & ((_1 << BitIndexSize) - 1)); |
| 85 } |
| 86 |
| 87 bool operator[](unsigned Idx) const { |
| 88 assert(Idx < size()); |
| 89 return Bits[Idx >> BitIndexSize] & |
| 90 (_1 << (Idx & ((_1 << BitIndexSize) - 1))); |
| 91 } |
| 92 |
| 93 int find_first() const { return find_first<0>(); } |
| 94 |
| 95 int find_next(unsigned Prev) const { return find_next<0>(Prev); } |
| 96 |
| 97 bool any() const { |
| 98 for (SizeT i = 0; i < BitsElements; ++i) { |
| 99 if (Bits[i]) { |
| 100 return true; |
| 101 } |
| 102 } |
| 103 return false; |
| 104 } |
| 105 |
| 106 SizeT size() const { return Size; } |
| 107 |
| 108 void resize(SizeT Size) { |
| 109 assert(Size <= MaxBits); |
| 110 this->Size = Size; |
| 111 } |
| 112 |
| 113 void reserve(SizeT Size) { |
| 114 assert(Size <= MaxBits); |
| 115 (void)Size; |
| 116 } |
| 117 |
| 118 void set(unsigned Idx) { (*this)[Idx] = true; } |
| 119 |
| 120 void set() { |
| 121 for (SizeT ii = 0; ii < size(); ++ii) { |
| 122 (*this)[ii] = true; |
| 123 } |
| 124 } |
| 125 |
| 126 SizeT count() const { |
| 127 SizeT Count = 0; |
| 128 for (SizeT i = 0; i < BitsElements; ++i) { |
| 129 Count += llvm::countPopulation(Bits[i]); |
| 130 } |
| 131 return Count; |
| 132 } |
| 133 |
| 134 SmallBitVector operator&(const SmallBitVector &Rhs) const { |
| 135 assert(size() == Rhs.size()); |
| 136 SmallBitVector Ret(std::max(size(), Rhs.size())); |
| 137 for (SizeT i = 0; i < BitsElements; ++i) { |
| 138 Ret.Bits[i] = Bits[i] & Rhs.Bits[i]; |
| 139 } |
| 140 return Ret; |
| 141 } |
| 142 |
| 143 SmallBitVector operator~() const { |
| 144 SmallBitVector Ret = *this; |
| 145 Ret.invert<0>(); |
| 146 return Ret; |
| 147 } |
| 148 |
| 149 SmallBitVector &operator|=(const SmallBitVector &Rhs) { |
| 150 assert(size() == Rhs.size()); |
| 151 resize(std::max(size(), Rhs.size())); |
| 152 for (SizeT i = 0; i < BitsElements; ++i) { |
| 153 Bits[i] |= Rhs.Bits[i]; |
| 154 } |
| 155 return *this; |
| 156 } |
| 157 |
| 158 SmallBitVector operator|(const SmallBitVector &Rhs) const { |
| 159 assert(size() == Rhs.size()); |
| 160 SmallBitVector Ret(std::max(size(), Rhs.size())); |
| 161 for (SizeT i = 0; i < BitsElements; ++i) { |
| 162 Ret.Bits[i] = Bits[i] | Rhs.Bits[i]; |
| 163 } |
| 164 return Ret; |
| 165 } |
| 166 |
| 167 void reset() { memset(Bits, 0, sizeof(Bits)); } |
| 168 |
| 169 void reset(const SmallBitVector &Mask) { |
| 170 for (const auto V : RegNumBVIter(Mask)) { |
| 171 (*this)[unsigned(V)] = false; |
| 172 } |
| 173 } |
| 174 |
| 175 private: |
| 176 // _1 is the constant 1 of type ElementType. |
| 177 static constexpr ElementType _1 = ElementType(1); |
| 178 |
| 179 static constexpr SizeT BitsElements = 2; |
| 180 ElementType Bits[BitsElements]; |
| 181 |
| 182 // MaxBits is defined here because it needs Bits to be defined. |
| 183 static constexpr SizeT MaxBits = sizeof(Bits) * CHAR_BIT; |
| 184 static_assert(sizeof(Bits) == 16, "Bits must be 16 bytes wide."); |
| 185 SizeT Size = 0; |
| 186 |
| 187 template <SizeT Pos> |
| 188 typename std::enable_if<Pos == sizeof(Bits) / sizeof(Bits[0]), int>::type |
| 189 find_first() const { |
| 190 return -1; |
| 191 } |
| 192 |
| 193 template <SizeT Pos> |
| 194 typename std::enable_if < |
| 195 Pos<sizeof(Bits) / sizeof(Bits[0]), int>::type find_first() const { |
| 196 if (Bits[Pos] != 0) { |
| 197 return NumBitsPerPos * Pos + llvm::countTrailingZeros(Bits[Pos]); |
| 198 } |
| 199 return find_first<Pos + 1>(); |
| 200 } |
| 201 |
| 202 template <SizeT Pos> |
| 203 typename std::enable_if<Pos == sizeof(Bits) / sizeof(Bits[0]), int>::type |
| 204 find_next(unsigned) const { |
| 205 return -1; |
| 206 } |
| 207 |
| 208 template <SizeT Pos> |
| 209 typename std::enable_if < Pos<sizeof(Bits) / sizeof(Bits[0]), int>::type |
| 210 find_next(unsigned Prev) const { |
| 211 if (Prev + 1 < (Pos + 1) * NumBitsPerPos) { |
| 212 const ElementType Mask = |
| 213 (ElementType(1) << ((Prev + 1) - Pos * NumBitsPerPos)) - 1; |
| 214 const ElementType B = Bits[Pos] & ~Mask; |
| 215 if (B != 0) { |
| 216 return NumBitsPerPos * Pos + llvm::countTrailingZeros(B); |
| 217 } |
| 218 Prev = (1 + Pos) * NumBitsPerPos - 1; |
| 219 } |
| 220 return find_next<Pos + 1>(Prev); |
| 221 } |
| 222 |
| 223 template <SizeT Pos> |
| 224 typename std::enable_if<Pos == sizeof(Bits) / sizeof(Bits[0]), void>::type |
| 225 invert() {} |
| 226 |
| 227 template <SizeT Pos> |
| 228 typename std::enable_if < |
| 229 Pos<sizeof(Bits) / sizeof(Bits[0]), void>::type invert() { |
| 230 if (size() < Pos * NumBitsPerPos) { |
| 231 Bits[Pos] = 0; |
| 232 } else if ((Pos + 1) * NumBitsPerPos < size()) { |
| 233 Bits[Pos] ^= ~ElementType(0); |
| 234 } else { |
| 235 const ElementType Mask = |
| 236 (ElementType(1) << (size() - (Pos * NumBitsPerPos))) - 1; |
| 237 Bits[Pos] ^= Mask; |
| 238 } |
| 239 invert<Pos + 1>(); |
| 240 } |
| 241 }; |
| 242 |
| 243 } // end of namespace Ice |
| 244 |
| 245 #endif // SUBZERO_SRC_ICEBITVECTOR_H |
OLD | NEW |