John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 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 |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 11 | /// \brief Defines and implements a bit vector classes. |
| 12 | /// |
| 13 | /// SmallBitVector is a drop in replacement for llvm::SmallBitVector. It uses |
| 14 | /// inline storage, at the expense of limited, static size. |
| 15 | /// |
| 16 | /// BitVector is a allocator aware version of llvm::BitVector. Its |
| 17 | /// implementation was copied ipsis literis from llvm. |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 18 | /// |
| 19 | //===----------------------------------------------------------------------===// |
| 20 | |
| 21 | #ifndef SUBZERO_SRC_ICEBITVECTOR_H |
| 22 | #define SUBZERO_SRC_ICEBITVECTOR_H |
| 23 | |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 24 | #include "IceMemory.h" |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 25 | #include "IceOperand.h" |
| 26 | |
| 27 | #include "llvm/Support/MathExtras.h" |
| 28 | |
| 29 | #include <algorithm> |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 30 | #include <cassert> |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 31 | #include <climits> |
| 32 | #include <memory> |
| 33 | #include <type_traits> |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 34 | #include <utility> |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 35 | |
| 36 | namespace Ice { |
| 37 | class SmallBitVector { |
| 38 | public: |
| 39 | using ElementType = uint64_t; |
| 40 | static constexpr SizeT BitIndexSize = 6; // log2(NumBitsPerPos); |
| 41 | static constexpr SizeT NumBitsPerPos = sizeof(ElementType) * CHAR_BIT; |
| 42 | static_assert(1 << BitIndexSize == NumBitsPerPos, "Invalid BitIndexSize."); |
| 43 | |
| 44 | SmallBitVector(const SmallBitVector &BV) { *this = BV; } |
| 45 | |
| 46 | SmallBitVector &operator=(const SmallBitVector &BV) { |
| 47 | if (&BV != this) { |
| 48 | resize(BV.size()); |
| 49 | memcpy(Bits, BV.Bits, sizeof(Bits)); |
| 50 | } |
| 51 | return *this; |
| 52 | } |
| 53 | |
| 54 | SmallBitVector() { reset(); } |
| 55 | |
| 56 | explicit SmallBitVector(SizeT S) : SmallBitVector() { |
| 57 | assert(S <= MaxBits); |
| 58 | resize(S); |
| 59 | } |
| 60 | |
| 61 | class Reference { |
| 62 | Reference() = delete; |
| 63 | |
| 64 | public: |
| 65 | Reference(const Reference &) = default; |
| 66 | Reference &operator=(const Reference &Rhs) { return *this = (bool)Rhs; } |
| 67 | Reference &operator=(bool t) { |
| 68 | if (t) { |
| 69 | *Data |= _1 << Bit; |
| 70 | } else { |
| 71 | *Data &= ~(_1 << Bit); |
| 72 | } |
| 73 | return *this; |
| 74 | } |
| 75 | operator bool() const { return (*Data & (_1 << Bit)) != 0; } |
| 76 | |
| 77 | private: |
| 78 | friend class SmallBitVector; |
| 79 | Reference(ElementType *D, SizeT B) : Data(D), Bit(B) { |
| 80 | assert(B < NumBitsPerPos); |
| 81 | } |
| 82 | |
| 83 | ElementType *const Data; |
| 84 | const SizeT Bit; |
| 85 | }; |
| 86 | |
| 87 | Reference operator[](unsigned Idx) { |
| 88 | assert(Idx < size()); |
| 89 | return Reference(Bits + (Idx >> BitIndexSize), |
| 90 | Idx & ((_1 << BitIndexSize) - 1)); |
| 91 | } |
| 92 | |
| 93 | bool operator[](unsigned Idx) const { |
| 94 | assert(Idx < size()); |
| 95 | return Bits[Idx >> BitIndexSize] & |
| 96 | (_1 << (Idx & ((_1 << BitIndexSize) - 1))); |
| 97 | } |
| 98 | |
| 99 | int find_first() const { return find_first<0>(); } |
| 100 | |
| 101 | int find_next(unsigned Prev) const { return find_next<0>(Prev); } |
| 102 | |
| 103 | bool any() const { |
| 104 | for (SizeT i = 0; i < BitsElements; ++i) { |
| 105 | if (Bits[i]) { |
| 106 | return true; |
| 107 | } |
| 108 | } |
| 109 | return false; |
| 110 | } |
| 111 | |
| 112 | SizeT size() const { return Size; } |
| 113 | |
| 114 | void resize(SizeT Size) { |
| 115 | assert(Size <= MaxBits); |
| 116 | this->Size = Size; |
| 117 | } |
| 118 | |
| 119 | void reserve(SizeT Size) { |
| 120 | assert(Size <= MaxBits); |
| 121 | (void)Size; |
| 122 | } |
| 123 | |
| 124 | void set(unsigned Idx) { (*this)[Idx] = true; } |
| 125 | |
| 126 | void set() { |
| 127 | for (SizeT ii = 0; ii < size(); ++ii) { |
| 128 | (*this)[ii] = true; |
| 129 | } |
| 130 | } |
| 131 | |
| 132 | SizeT count() const { |
| 133 | SizeT Count = 0; |
| 134 | for (SizeT i = 0; i < BitsElements; ++i) { |
| 135 | Count += llvm::countPopulation(Bits[i]); |
| 136 | } |
| 137 | return Count; |
| 138 | } |
| 139 | |
| 140 | SmallBitVector operator&(const SmallBitVector &Rhs) const { |
| 141 | assert(size() == Rhs.size()); |
| 142 | SmallBitVector Ret(std::max(size(), Rhs.size())); |
| 143 | for (SizeT i = 0; i < BitsElements; ++i) { |
| 144 | Ret.Bits[i] = Bits[i] & Rhs.Bits[i]; |
| 145 | } |
| 146 | return Ret; |
| 147 | } |
| 148 | |
| 149 | SmallBitVector operator~() const { |
| 150 | SmallBitVector Ret = *this; |
| 151 | Ret.invert<0>(); |
| 152 | return Ret; |
| 153 | } |
| 154 | |
| 155 | SmallBitVector &operator|=(const SmallBitVector &Rhs) { |
| 156 | assert(size() == Rhs.size()); |
| 157 | resize(std::max(size(), Rhs.size())); |
| 158 | for (SizeT i = 0; i < BitsElements; ++i) { |
| 159 | Bits[i] |= Rhs.Bits[i]; |
| 160 | } |
| 161 | return *this; |
| 162 | } |
| 163 | |
| 164 | SmallBitVector operator|(const SmallBitVector &Rhs) const { |
| 165 | assert(size() == Rhs.size()); |
| 166 | SmallBitVector Ret(std::max(size(), Rhs.size())); |
| 167 | for (SizeT i = 0; i < BitsElements; ++i) { |
| 168 | Ret.Bits[i] = Bits[i] | Rhs.Bits[i]; |
| 169 | } |
| 170 | return Ret; |
| 171 | } |
| 172 | |
| 173 | void reset() { memset(Bits, 0, sizeof(Bits)); } |
| 174 | |
| 175 | void reset(const SmallBitVector &Mask) { |
| 176 | for (const auto V : RegNumBVIter(Mask)) { |
| 177 | (*this)[unsigned(V)] = false; |
| 178 | } |
| 179 | } |
| 180 | |
| 181 | private: |
| 182 | // _1 is the constant 1 of type ElementType. |
| 183 | static constexpr ElementType _1 = ElementType(1); |
| 184 | |
| 185 | static constexpr SizeT BitsElements = 2; |
| 186 | ElementType Bits[BitsElements]; |
| 187 | |
| 188 | // MaxBits is defined here because it needs Bits to be defined. |
Nicolas Capens | 17f04f0 | 2016-09-01 16:22:36 -0400 | [diff] [blame] | 189 | static constexpr SizeT MaxBits = sizeof(SmallBitVector::Bits) * CHAR_BIT; |
| 190 | static_assert(sizeof(SmallBitVector::Bits) == 16, |
| 191 | "Bits must be 16 bytes wide."); |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 192 | SizeT Size = 0; |
| 193 | |
| 194 | template <SizeT Pos> |
Nicolas Capens | 17f04f0 | 2016-09-01 16:22:36 -0400 | [diff] [blame] | 195 | typename std::enable_if<Pos == BitsElements, int>::type find_first() const { |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 196 | return -1; |
| 197 | } |
| 198 | |
| 199 | template <SizeT Pos> |
| 200 | typename std::enable_if < |
Nicolas Capens | 17f04f0 | 2016-09-01 16:22:36 -0400 | [diff] [blame] | 201 | Pos<BitsElements, int>::type find_first() const { |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 202 | if (Bits[Pos] != 0) { |
| 203 | return NumBitsPerPos * Pos + llvm::countTrailingZeros(Bits[Pos]); |
| 204 | } |
| 205 | return find_first<Pos + 1>(); |
| 206 | } |
| 207 | |
| 208 | template <SizeT Pos> |
Nicolas Capens | 17f04f0 | 2016-09-01 16:22:36 -0400 | [diff] [blame] | 209 | typename std::enable_if<Pos == BitsElements, int>::type |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 210 | find_next(unsigned) const { |
| 211 | return -1; |
| 212 | } |
| 213 | |
| 214 | template <SizeT Pos> |
Nicolas Capens | 17f04f0 | 2016-09-01 16:22:36 -0400 | [diff] [blame] | 215 | typename std::enable_if < |
| 216 | Pos<BitsElements, int>::type find_next(unsigned Prev) const { |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 217 | if (Prev + 1 < (Pos + 1) * NumBitsPerPos) { |
| 218 | const ElementType Mask = |
| 219 | (ElementType(1) << ((Prev + 1) - Pos * NumBitsPerPos)) - 1; |
| 220 | const ElementType B = Bits[Pos] & ~Mask; |
| 221 | if (B != 0) { |
| 222 | return NumBitsPerPos * Pos + llvm::countTrailingZeros(B); |
| 223 | } |
| 224 | Prev = (1 + Pos) * NumBitsPerPos - 1; |
| 225 | } |
| 226 | return find_next<Pos + 1>(Prev); |
| 227 | } |
| 228 | |
| 229 | template <SizeT Pos> |
Nicolas Capens | 17f04f0 | 2016-09-01 16:22:36 -0400 | [diff] [blame] | 230 | typename std::enable_if<Pos == BitsElements, void>::type invert() {} |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 231 | |
| 232 | template <SizeT Pos> |
Nicolas Capens | 17f04f0 | 2016-09-01 16:22:36 -0400 | [diff] [blame] | 233 | typename std::enable_if < Pos<BitsElements, void>::type invert() { |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 234 | if (size() < Pos * NumBitsPerPos) { |
| 235 | Bits[Pos] = 0; |
| 236 | } else if ((Pos + 1) * NumBitsPerPos < size()) { |
| 237 | Bits[Pos] ^= ~ElementType(0); |
| 238 | } else { |
| 239 | const ElementType Mask = |
| 240 | (ElementType(1) << (size() - (Pos * NumBitsPerPos))) - 1; |
| 241 | Bits[Pos] ^= Mask; |
| 242 | } |
| 243 | invert<Pos + 1>(); |
| 244 | } |
| 245 | }; |
| 246 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 247 | template <template <typename> class AT> class BitVectorTmpl { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 248 | typedef unsigned long BitWord; |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 249 | using Allocator = AT<BitWord>; |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 250 | |
| 251 | enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT }; |
| 252 | |
| 253 | static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32, |
| 254 | "Unsupported word size"); |
| 255 | |
| 256 | BitWord *Bits; // Actual bits. |
| 257 | unsigned Size; // Size of bitvector in bits. |
| 258 | unsigned Capacity; // Size of allocated memory in BitWord. |
| 259 | Allocator Alloc; |
| 260 | |
Jim Stichnoth | f5fdd23 | 2016-05-09 12:24:36 -0700 | [diff] [blame] | 261 | uint64_t alignTo(uint64_t Value, uint64_t Align) { |
| 262 | #ifdef PNACL_LLVM |
| 263 | return llvm::RoundUpToAlignment(Value, Align); |
Jim Stichnoth | a5b16ab | 2016-05-10 11:20:41 -0700 | [diff] [blame] | 264 | #else // !PNACL_LLVM |
Jim Stichnoth | f5fdd23 | 2016-05-09 12:24:36 -0700 | [diff] [blame] | 265 | return llvm::alignTo(Value, Align); |
| 266 | #endif // !PNACL_LLVM |
| 267 | } |
| 268 | |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 269 | public: |
| 270 | typedef unsigned size_type; |
| 271 | // Encapsulation of a single bit. |
| 272 | class reference { |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 273 | friend class BitVectorTmpl; |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 274 | |
| 275 | BitWord *WordRef; |
| 276 | unsigned BitPos; |
| 277 | |
| 278 | reference(); // Undefined |
| 279 | |
| 280 | public: |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 281 | reference(BitVectorTmpl &b, unsigned Idx) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 282 | WordRef = &b.Bits[Idx / BITWORD_SIZE]; |
| 283 | BitPos = Idx % BITWORD_SIZE; |
| 284 | } |
| 285 | |
| 286 | reference(const reference &) = default; |
| 287 | |
| 288 | reference &operator=(reference t) { |
| 289 | *this = bool(t); |
| 290 | return *this; |
| 291 | } |
| 292 | |
| 293 | reference &operator=(bool t) { |
| 294 | if (t) |
| 295 | *WordRef |= BitWord(1) << BitPos; |
| 296 | else |
| 297 | *WordRef &= ~(BitWord(1) << BitPos); |
| 298 | return *this; |
| 299 | } |
| 300 | |
| 301 | operator bool() const { |
| 302 | return ((*WordRef) & (BitWord(1) << BitPos)) ? true : false; |
| 303 | } |
| 304 | }; |
| 305 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 306 | /// BitVectorTmpl default ctor - Creates an empty bitvector. |
| 307 | BitVectorTmpl(Allocator A = Allocator()) |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 308 | : Size(0), Capacity(0), Alloc(std::move(A)) { |
| 309 | Bits = nullptr; |
| 310 | } |
| 311 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 312 | /// BitVectorTmpl ctor - Creates a bitvector of specified number of bits. All |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 313 | /// bits are initialized to the specified value. |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 314 | explicit BitVectorTmpl(unsigned s, bool t = false, Allocator A = Allocator()) |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 315 | : Size(s), Alloc(std::move(A)) { |
| 316 | Capacity = NumBitWords(s); |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 317 | Bits = Alloc.allocate(Capacity); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 318 | init_words(Bits, Capacity, t); |
| 319 | if (t) |
| 320 | clear_unused_bits(); |
| 321 | } |
| 322 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 323 | /// BitVectorTmpl copy ctor. |
| 324 | BitVectorTmpl(const BitVectorTmpl &RHS) : Size(RHS.size()), Alloc(RHS.Alloc) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 325 | if (Size == 0) { |
| 326 | Bits = nullptr; |
| 327 | Capacity = 0; |
| 328 | return; |
| 329 | } |
| 330 | |
| 331 | Capacity = NumBitWords(RHS.size()); |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 332 | Bits = Alloc.allocate(Capacity); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 333 | std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord)); |
| 334 | } |
| 335 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 336 | BitVectorTmpl(BitVectorTmpl &&RHS) |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 337 | : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity), |
| 338 | Alloc(std::move(RHS.Alloc)) { |
| 339 | RHS.Bits = nullptr; |
| 340 | } |
| 341 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 342 | ~BitVectorTmpl() { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 343 | if (Bits != nullptr) { |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 344 | Alloc.deallocate(Bits, Capacity); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 345 | } |
| 346 | } |
| 347 | |
| 348 | /// empty - Tests whether there are no bits in this bitvector. |
| 349 | bool empty() const { return Size == 0; } |
| 350 | |
| 351 | /// size - Returns the number of bits in this bitvector. |
| 352 | size_type size() const { return Size; } |
| 353 | |
| 354 | /// count - Returns the number of bits which are set. |
| 355 | size_type count() const { |
| 356 | unsigned NumBits = 0; |
| 357 | for (unsigned i = 0; i < NumBitWords(size()); ++i) |
| 358 | NumBits += llvm::countPopulation(Bits[i]); |
| 359 | return NumBits; |
| 360 | } |
| 361 | |
| 362 | /// any - Returns true if any bit is set. |
| 363 | bool any() const { |
| 364 | for (unsigned i = 0; i < NumBitWords(size()); ++i) |
| 365 | if (Bits[i] != 0) |
| 366 | return true; |
| 367 | return false; |
| 368 | } |
| 369 | |
| 370 | /// all - Returns true if all bits are set. |
| 371 | bool all() const { |
| 372 | for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i) |
| 373 | if (Bits[i] != ~0UL) |
| 374 | return false; |
| 375 | |
| 376 | // If bits remain check that they are ones. The unused bits are always zero. |
| 377 | if (unsigned Remainder = Size % BITWORD_SIZE) |
| 378 | return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1; |
| 379 | |
| 380 | return true; |
| 381 | } |
| 382 | |
| 383 | /// none - Returns true if none of the bits are set. |
| 384 | bool none() const { return !any(); } |
| 385 | |
| 386 | /// find_first - Returns the index of the first set bit, -1 if none |
| 387 | /// of the bits are set. |
| 388 | int find_first() const { |
| 389 | for (unsigned i = 0; i < NumBitWords(size()); ++i) |
| 390 | if (Bits[i] != 0) |
| 391 | return i * BITWORD_SIZE + llvm::countTrailingZeros(Bits[i]); |
| 392 | return -1; |
| 393 | } |
| 394 | |
| 395 | /// find_next - Returns the index of the next set bit following the |
| 396 | /// "Prev" bit. Returns -1 if the next set bit is not found. |
| 397 | int find_next(unsigned Prev) const { |
| 398 | ++Prev; |
| 399 | if (Prev >= Size) |
| 400 | return -1; |
| 401 | |
| 402 | unsigned WordPos = Prev / BITWORD_SIZE; |
| 403 | unsigned BitPos = Prev % BITWORD_SIZE; |
| 404 | BitWord Copy = Bits[WordPos]; |
| 405 | // Mask off previous bits. |
| 406 | Copy &= ~0UL << BitPos; |
| 407 | |
| 408 | if (Copy != 0) |
| 409 | return WordPos * BITWORD_SIZE + llvm::countTrailingZeros(Copy); |
| 410 | |
| 411 | // Check subsequent words. |
| 412 | for (unsigned i = WordPos + 1; i < NumBitWords(size()); ++i) |
| 413 | if (Bits[i] != 0) |
| 414 | return i * BITWORD_SIZE + llvm::countTrailingZeros(Bits[i]); |
| 415 | return -1; |
| 416 | } |
| 417 | |
| 418 | /// clear - Clear all bits. |
| 419 | void clear() { Size = 0; } |
| 420 | |
| 421 | /// resize - Grow or shrink the bitvector. |
| 422 | void resize(unsigned N, bool t = false) { |
| 423 | if (N > Capacity * BITWORD_SIZE) { |
| 424 | unsigned OldCapacity = Capacity; |
| 425 | grow(N); |
| 426 | init_words(&Bits[OldCapacity], (Capacity - OldCapacity), t); |
| 427 | } |
| 428 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 429 | // Set any old unused bits that are now included in the BitVectorTmpl. This |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 430 | // may set bits that are not included in the new vector, but we will clear |
| 431 | // them back out below. |
| 432 | if (N > Size) |
| 433 | set_unused_bits(t); |
| 434 | |
| 435 | // Update the size, and clear out any bits that are now unused |
| 436 | unsigned OldSize = Size; |
| 437 | Size = N; |
| 438 | if (t || N < OldSize) |
| 439 | clear_unused_bits(); |
| 440 | } |
| 441 | |
| 442 | void reserve(unsigned N) { |
| 443 | if (N > Capacity * BITWORD_SIZE) |
| 444 | grow(N); |
| 445 | } |
| 446 | |
| 447 | // Set, reset, flip |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 448 | BitVectorTmpl &set() { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 449 | init_words(Bits, Capacity, true); |
| 450 | clear_unused_bits(); |
| 451 | return *this; |
| 452 | } |
| 453 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 454 | BitVectorTmpl &set(unsigned Idx) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 455 | assert(Bits && "Bits never allocated"); |
| 456 | Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE); |
| 457 | return *this; |
| 458 | } |
| 459 | |
| 460 | /// set - Efficiently set a range of bits in [I, E) |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 461 | BitVectorTmpl &set(unsigned I, unsigned E) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 462 | assert(I <= E && "Attempted to set backwards range!"); |
| 463 | assert(E <= size() && "Attempted to set out-of-bounds range!"); |
| 464 | |
| 465 | if (I == E) |
| 466 | return *this; |
| 467 | |
| 468 | if (I / BITWORD_SIZE == E / BITWORD_SIZE) { |
| 469 | BitWord EMask = 1UL << (E % BITWORD_SIZE); |
| 470 | BitWord IMask = 1UL << (I % BITWORD_SIZE); |
| 471 | BitWord Mask = EMask - IMask; |
| 472 | Bits[I / BITWORD_SIZE] |= Mask; |
| 473 | return *this; |
| 474 | } |
| 475 | |
| 476 | BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); |
| 477 | Bits[I / BITWORD_SIZE] |= PrefixMask; |
Jim Stichnoth | f5fdd23 | 2016-05-09 12:24:36 -0700 | [diff] [blame] | 478 | I = alignTo(I, BITWORD_SIZE); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 479 | |
| 480 | for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) |
| 481 | Bits[I / BITWORD_SIZE] = ~0UL; |
| 482 | |
| 483 | BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; |
| 484 | if (I < E) |
| 485 | Bits[I / BITWORD_SIZE] |= PostfixMask; |
| 486 | |
| 487 | return *this; |
| 488 | } |
| 489 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 490 | BitVectorTmpl &reset() { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 491 | init_words(Bits, Capacity, false); |
| 492 | return *this; |
| 493 | } |
| 494 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 495 | BitVectorTmpl &reset(unsigned Idx) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 496 | Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE)); |
| 497 | return *this; |
| 498 | } |
| 499 | |
| 500 | /// reset - Efficiently reset a range of bits in [I, E) |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 501 | BitVectorTmpl &reset(unsigned I, unsigned E) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 502 | assert(I <= E && "Attempted to reset backwards range!"); |
| 503 | assert(E <= size() && "Attempted to reset out-of-bounds range!"); |
| 504 | |
| 505 | if (I == E) |
| 506 | return *this; |
| 507 | |
| 508 | if (I / BITWORD_SIZE == E / BITWORD_SIZE) { |
| 509 | BitWord EMask = 1UL << (E % BITWORD_SIZE); |
| 510 | BitWord IMask = 1UL << (I % BITWORD_SIZE); |
| 511 | BitWord Mask = EMask - IMask; |
| 512 | Bits[I / BITWORD_SIZE] &= ~Mask; |
| 513 | return *this; |
| 514 | } |
| 515 | |
| 516 | BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE); |
| 517 | Bits[I / BITWORD_SIZE] &= ~PrefixMask; |
Jim Stichnoth | f5fdd23 | 2016-05-09 12:24:36 -0700 | [diff] [blame] | 518 | I = alignTo(I, BITWORD_SIZE); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 519 | |
| 520 | for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE) |
| 521 | Bits[I / BITWORD_SIZE] = 0UL; |
| 522 | |
| 523 | BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1; |
| 524 | if (I < E) |
| 525 | Bits[I / BITWORD_SIZE] &= ~PostfixMask; |
| 526 | |
| 527 | return *this; |
| 528 | } |
| 529 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 530 | BitVectorTmpl &flip() { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 531 | for (unsigned i = 0; i < NumBitWords(size()); ++i) |
| 532 | Bits[i] = ~Bits[i]; |
| 533 | clear_unused_bits(); |
| 534 | return *this; |
| 535 | } |
| 536 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 537 | BitVectorTmpl &flip(unsigned Idx) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 538 | Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE); |
| 539 | return *this; |
| 540 | } |
| 541 | |
| 542 | // Indexing. |
| 543 | reference operator[](unsigned Idx) { |
| 544 | assert(Idx < Size && "Out-of-bounds Bit access."); |
| 545 | return reference(*this, Idx); |
| 546 | } |
| 547 | |
| 548 | bool operator[](unsigned Idx) const { |
| 549 | assert(Idx < Size && "Out-of-bounds Bit access."); |
| 550 | BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE); |
| 551 | return (Bits[Idx / BITWORD_SIZE] & Mask) != 0; |
| 552 | } |
| 553 | |
| 554 | bool test(unsigned Idx) const { return (*this)[Idx]; } |
| 555 | |
| 556 | /// Test if any common bits are set. |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 557 | bool anyCommon(const BitVectorTmpl &RHS) const { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 558 | unsigned ThisWords = NumBitWords(size()); |
| 559 | unsigned RHSWords = NumBitWords(RHS.size()); |
| 560 | for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) |
| 561 | if (Bits[i] & RHS.Bits[i]) |
| 562 | return true; |
| 563 | return false; |
| 564 | } |
| 565 | |
| 566 | // Comparison operators. |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 567 | bool operator==(const BitVectorTmpl &RHS) const { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 568 | unsigned ThisWords = NumBitWords(size()); |
| 569 | unsigned RHSWords = NumBitWords(RHS.size()); |
| 570 | unsigned i; |
| 571 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |
| 572 | if (Bits[i] != RHS.Bits[i]) |
| 573 | return false; |
| 574 | |
| 575 | // Verify that any extra words are all zeros. |
| 576 | if (i != ThisWords) { |
| 577 | for (; i != ThisWords; ++i) |
| 578 | if (Bits[i]) |
| 579 | return false; |
| 580 | } else if (i != RHSWords) { |
| 581 | for (; i != RHSWords; ++i) |
| 582 | if (RHS.Bits[i]) |
| 583 | return false; |
| 584 | } |
| 585 | return true; |
| 586 | } |
| 587 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 588 | bool operator!=(const BitVectorTmpl &RHS) const { return !(*this == RHS); } |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 589 | |
| 590 | /// Intersection, union, disjoint union. |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 591 | BitVectorTmpl &operator&=(const BitVectorTmpl &RHS) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 592 | unsigned ThisWords = NumBitWords(size()); |
| 593 | unsigned RHSWords = NumBitWords(RHS.size()); |
| 594 | unsigned i; |
| 595 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |
| 596 | Bits[i] &= RHS.Bits[i]; |
| 597 | |
| 598 | // Any bits that are just in this bitvector become zero, because they aren't |
| 599 | // in the RHS bit vector. Any words only in RHS are ignored because they |
| 600 | // are already zero in the LHS. |
| 601 | for (; i != ThisWords; ++i) |
| 602 | Bits[i] = 0; |
| 603 | |
| 604 | return *this; |
| 605 | } |
| 606 | |
| 607 | /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 608 | BitVectorTmpl &reset(const BitVectorTmpl &RHS) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 609 | unsigned ThisWords = NumBitWords(size()); |
| 610 | unsigned RHSWords = NumBitWords(RHS.size()); |
| 611 | unsigned i; |
| 612 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |
| 613 | Bits[i] &= ~RHS.Bits[i]; |
| 614 | return *this; |
| 615 | } |
| 616 | |
| 617 | /// test - Check if (This - RHS) is zero. |
| 618 | /// This is the same as reset(RHS) and any(). |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 619 | bool test(const BitVectorTmpl &RHS) const { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 620 | unsigned ThisWords = NumBitWords(size()); |
| 621 | unsigned RHSWords = NumBitWords(RHS.size()); |
| 622 | unsigned i; |
| 623 | for (i = 0; i != std::min(ThisWords, RHSWords); ++i) |
| 624 | if ((Bits[i] & ~RHS.Bits[i]) != 0) |
| 625 | return true; |
| 626 | |
| 627 | for (; i != ThisWords; ++i) |
| 628 | if (Bits[i] != 0) |
| 629 | return true; |
| 630 | |
| 631 | return false; |
| 632 | } |
| 633 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 634 | BitVectorTmpl &operator|=(const BitVectorTmpl &RHS) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 635 | if (size() < RHS.size()) |
| 636 | resize(RHS.size()); |
| 637 | for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) |
| 638 | Bits[i] |= RHS.Bits[i]; |
| 639 | return *this; |
| 640 | } |
| 641 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 642 | BitVectorTmpl &operator^=(const BitVectorTmpl &RHS) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 643 | if (size() < RHS.size()) |
| 644 | resize(RHS.size()); |
| 645 | for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i) |
| 646 | Bits[i] ^= RHS.Bits[i]; |
| 647 | return *this; |
| 648 | } |
| 649 | |
| 650 | // Assignment operator. |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 651 | const BitVectorTmpl &operator=(const BitVectorTmpl &RHS) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 652 | if (this == &RHS) |
| 653 | return *this; |
| 654 | |
| 655 | Size = RHS.size(); |
| 656 | unsigned RHSWords = NumBitWords(Size); |
| 657 | if (Size <= Capacity * BITWORD_SIZE) { |
| 658 | if (Size) |
| 659 | std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord)); |
| 660 | clear_unused_bits(); |
| 661 | return *this; |
| 662 | } |
| 663 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 664 | // Currently, BitVectorTmpl is only used by liveness analysis. With the |
| 665 | // following assert, we make sure BitVectorTmpls grow in a single step from |
| 666 | // 0 to their final capacity, rather than growing slowly and "leaking" |
| 667 | // memory in the process. |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 668 | assert(Capacity == 0); |
| 669 | |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 670 | // Grow the bitvector to have enough elements. |
| 671 | const auto OldCapacity = Capacity; |
| 672 | Capacity = RHSWords; |
| 673 | assert(Capacity > 0 && "negative capacity?"); |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 674 | BitWord *NewBits = Alloc.allocate(Capacity); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 675 | std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord)); |
| 676 | |
| 677 | // Destroy the old bits. |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 678 | Alloc.deallocate(Bits, OldCapacity); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 679 | Bits = NewBits; |
| 680 | |
| 681 | return *this; |
| 682 | } |
| 683 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 684 | const BitVectorTmpl &operator=(BitVectorTmpl &&RHS) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 685 | if (this == &RHS) |
| 686 | return *this; |
| 687 | |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 688 | Alloc.deallocate(Bits, Capacity); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 689 | Bits = RHS.Bits; |
| 690 | Size = RHS.Size; |
| 691 | Capacity = RHS.Capacity; |
| 692 | |
| 693 | RHS.Bits = nullptr; |
| 694 | |
| 695 | return *this; |
| 696 | } |
| 697 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 698 | void swap(BitVectorTmpl &RHS) { |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 699 | std::swap(Bits, RHS.Bits); |
| 700 | std::swap(Size, RHS.Size); |
| 701 | std::swap(Capacity, RHS.Capacity); |
| 702 | } |
| 703 | |
| 704 | //===--------------------------------------------------------------------===// |
| 705 | // Portable bit mask operations. |
| 706 | //===--------------------------------------------------------------------===// |
| 707 | // |
| 708 | // These methods all operate on arrays of uint32_t, each holding 32 bits. The |
| 709 | // fixed word size makes it easier to work with literal bit vector constants |
| 710 | // in portable code. |
| 711 | // |
| 712 | // The LSB in each word is the lowest numbered bit. The size of a portable |
| 713 | // bit mask is always a whole multiple of 32 bits. If no bit mask size is |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 714 | // given, the bit mask is assumed to cover the entire BitVectorTmpl. |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 715 | |
| 716 | /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. |
| 717 | /// This computes "*this |= Mask". |
| 718 | void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
| 719 | applyMask<true, false>(Mask, MaskWords); |
| 720 | } |
| 721 | |
| 722 | /// clearBitsInMask - Clear any bits in this vector that are set in Mask. |
| 723 | /// Don't resize. This computes "*this &= ~Mask". |
| 724 | void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
| 725 | applyMask<false, false>(Mask, MaskWords); |
| 726 | } |
| 727 | |
| 728 | /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. |
| 729 | /// Don't resize. This computes "*this |= ~Mask". |
| 730 | void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
| 731 | applyMask<true, true>(Mask, MaskWords); |
| 732 | } |
| 733 | |
| 734 | /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. |
| 735 | /// Don't resize. This computes "*this &= Mask". |
| 736 | void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { |
| 737 | applyMask<false, true>(Mask, MaskWords); |
| 738 | } |
| 739 | |
| 740 | private: |
| 741 | unsigned NumBitWords(unsigned S) const { |
| 742 | return (S + BITWORD_SIZE - 1) / BITWORD_SIZE; |
| 743 | } |
| 744 | |
| 745 | // Set the unused bits in the high words. |
| 746 | void set_unused_bits(bool t = true) { |
| 747 | // Set high words first. |
| 748 | unsigned UsedWords = NumBitWords(Size); |
| 749 | if (Capacity > UsedWords) |
| 750 | init_words(&Bits[UsedWords], (Capacity - UsedWords), t); |
| 751 | |
| 752 | // Then set any stray high bits of the last used word. |
| 753 | unsigned ExtraBits = Size % BITWORD_SIZE; |
| 754 | if (ExtraBits) { |
| 755 | BitWord ExtraBitMask = ~0UL << ExtraBits; |
| 756 | if (t) |
| 757 | Bits[UsedWords - 1] |= ExtraBitMask; |
| 758 | else |
| 759 | Bits[UsedWords - 1] &= ~ExtraBitMask; |
| 760 | } |
| 761 | } |
| 762 | |
| 763 | // Clear the unused bits in the high words. |
| 764 | void clear_unused_bits() { set_unused_bits(false); } |
| 765 | |
| 766 | void grow(unsigned NewSize) { |
| 767 | const auto OldCapacity = Capacity; |
| 768 | Capacity = std::max(NumBitWords(NewSize), Capacity * 2); |
| 769 | assert(Capacity > 0 && "realloc-ing zero space"); |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 770 | auto *NewBits = Alloc.allocate(Capacity); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 771 | std::memcpy(Bits, NewBits, OldCapacity * sizeof(BitWord)); |
Jim Stichnoth | 1bdb735 | 2016-02-29 16:58:15 -0800 | [diff] [blame] | 772 | Alloc.deallocate(Bits, OldCapacity); |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 773 | Bits = NewBits; |
| 774 | |
| 775 | clear_unused_bits(); |
| 776 | } |
| 777 | |
| 778 | void init_words(BitWord *B, unsigned NumWords, bool t) { |
| 779 | memset(B, 0 - (int)t, NumWords * sizeof(BitWord)); |
| 780 | } |
| 781 | |
| 782 | template <bool AddBits, bool InvertMask> |
| 783 | void applyMask(const uint32_t *Mask, unsigned MaskWords) { |
| 784 | static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size."); |
| 785 | MaskWords = std::min(MaskWords, (size() + 31) / 32); |
| 786 | const unsigned Scale = BITWORD_SIZE / 32; |
| 787 | unsigned i; |
| 788 | for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) { |
| 789 | BitWord BW = Bits[i]; |
| 790 | // This inner loop should unroll completely when BITWORD_SIZE > 32. |
| 791 | for (unsigned b = 0; b != BITWORD_SIZE; b += 32) { |
| 792 | uint32_t M = *Mask++; |
| 793 | if (InvertMask) |
| 794 | M = ~M; |
| 795 | if (AddBits) |
| 796 | BW |= BitWord(M) << b; |
| 797 | else |
| 798 | BW &= ~(BitWord(M) << b); |
| 799 | } |
| 800 | Bits[i] = BW; |
| 801 | } |
| 802 | for (unsigned b = 0; MaskWords; b += 32, --MaskWords) { |
| 803 | uint32_t M = *Mask++; |
| 804 | if (InvertMask) |
| 805 | M = ~M; |
| 806 | if (AddBits) |
| 807 | Bits[i] |= BitWord(M) << b; |
| 808 | else |
| 809 | Bits[i] &= ~(BitWord(M) << b); |
| 810 | } |
| 811 | if (AddBits) |
| 812 | clear_unused_bits(); |
| 813 | } |
| 814 | }; |
| 815 | |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 816 | using BitVector = BitVectorTmpl<CfgLocalAllocator>; |
| 817 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 818 | } // end of namespace Ice |
| 819 | |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 820 | namespace std { |
John Porto | 7bb9cab | 2016-04-01 05:43:09 -0700 | [diff] [blame] | 821 | /// Implement std::swap in terms of BitVectorTmpl swap. |
| 822 | template <template <typename> class AT> |
| 823 | inline void swap(Ice::BitVectorTmpl<AT> &LHS, Ice::BitVectorTmpl<AT> &RHS) { |
| 824 | LHS.swap(RHS); |
| 825 | } |
John Porto | 36d6aa6 | 2016-02-26 07:19:59 -0800 | [diff] [blame] | 826 | } |
| 827 | |
John Porto | e82b560 | 2016-02-24 15:58:55 -0800 | [diff] [blame] | 828 | #endif // SUBZERO_SRC_ICEBITVECTOR_H |