include/llvm/ADT/SmallBitVector.h

   1 //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the SmallBitVector class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_ADT_SMALLBITVECTOR_H
  14 #define LLVM_ADT_SMALLBITVECTOR_H
  15
  16 #include "llvm/ADT/BitVector.h"
  17 #include "llvm/ADT/iterator_range.h"
  18 #include "llvm/Support/MathExtras.h"
  19 #include <algorithm>
  20 #include <cassert>
  21 #include <climits>
  22 #include <cstddef>
  23 #include <cstdint>
  24 #include <limits>
  25 #include <utility>
  26
  27 namespace llvm {
  28
  29 /// This is a 'bitvector' (really, a variable-sized bit array), optimized for
  30 /// the case when the array is small. It contains one pointer-sized field, which
  31 /// is directly used as a plain collection of bits when possible, or as a
  32 /// pointer to a larger heap-allocated array when necessary. This allows normal
  33 /// "small" cases to be fast without losing generality for large inputs.
  34 class SmallBitVector {
  35   // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
  36   // unnecessary level of indirection. It would be more efficient to use a
  37   // pointer to memory containing size, allocation size, and the array of bits.
  38   uintptr_t X = 1;
  39
  40   enum {
  41     // The number of bits in this class.
  42     NumBaseBits = sizeof(uintptr_t) * CHAR_BIT,
  43
  44     // One bit is used to discriminate between small and large mode. The
  45     // remaining bits are used for the small-mode representation.
  46     SmallNumRawBits = NumBaseBits - 1,
  47
  48     // A few more bits are used to store the size of the bit set in small mode.
  49     // Theoretically this is a ceil-log2. These bits are encoded in the most
  50     // significant bits of the raw bits.
  51     SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
  52                         NumBaseBits == 64 ? 6 :
  53                         SmallNumRawBits),
  54
  55     // The remaining bits are used to store the actual set in small mode.
  56     SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
  57   };
  58
  59   static_assert(NumBaseBits == 64 || NumBaseBits == 32,
  60                 "Unsupported word size");
  61
  62 public:
  63   using size_type = unsigned;
  64
  65   // Encapsulation of a single bit.
  66   class reference {
  67     SmallBitVector &TheVector;
  68     unsigned BitPos;
  69
  70   public:
  71     reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
  72
  73     reference(const reference&) = default;
  74
  75     reference& operator=(reference t) {
  76       *this = bool(t);
  77       return *this;
  78     }
  79
  80     reference& operator=(bool t) {
  81       if (t)
  82         TheVector.set(BitPos);
  83       else
  84         TheVector.reset(BitPos);
  85       return *this;
  86     }
  87
  88     operator bool() const {
  89       return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
  90     }
  91   };
  92
  93 private:
  94   BitVector *getPointer() const {
  95     assert(!isSmall());
  96     return reinterpret_cast<BitVector *>(X);
  97   }
  98
  99   void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
 100     X = 1;
 101     setSmallSize(NewSize);
 102     setSmallBits(NewSmallBits);
 103   }
 104
 105   void switchToLarge(BitVector *BV) {
 106     X = reinterpret_cast<uintptr_t>(BV);
 107     assert(!isSmall() && "Tried to use an unaligned pointer");
 108   }
 109
 110   // Return all the bits used for the "small" representation; this includes
 111   // bits for the size as well as the element bits.
 112   uintptr_t getSmallRawBits() const {
 113     assert(isSmall());
 114     return X >> 1;
 115   }
 116
 117   void setSmallRawBits(uintptr_t NewRawBits) {
 118     assert(isSmall());
 119     X = (NewRawBits << 1) | uintptr_t(1);
 120   }
 121
 122   // Return the size.
 123   size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
 124
 125   void setSmallSize(size_t Size) {
 126     setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
 127   }
 128
 129   // Return the element bits.
 130   uintptr_t getSmallBits() const {
 131     return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
 132   }
 133
 134   void setSmallBits(uintptr_t NewBits) {
 135     setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
 136                     (getSmallSize() << SmallNumDataBits));
 137   }
 138
 139 public:
 140   /// Creates an empty bitvector.
 141   SmallBitVector() = default;
 142
 143   /// Creates a bitvector of specified number of bits. All bits are initialized
 144   /// to the specified value.
 145   explicit SmallBitVector(unsigned s, bool t = false) {
 146     if (s <= SmallNumDataBits)
 147       switchToSmall(t ? ~uintptr_t(0) : 0, s);
 148     else
 149       switchToLarge(new BitVector(s, t));
 150   }
 151
 152   /// SmallBitVector copy ctor.
 153   SmallBitVector(const SmallBitVector &RHS) {
 154     if (RHS.isSmall())
 155       X = RHS.X;
 156     else
 157       switchToLarge(new BitVector(*RHS.getPointer()));
 158   }
 159
 160   SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
 161     RHS.X = 1;
 162   }
 163
 164   ~SmallBitVector() {
 165     if (!isSmall())
 166       delete getPointer();
 167   }
 168
 169   using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
 170   using set_iterator = const_set_bits_iterator;
 171
 172   const_set_bits_iterator set_bits_begin() const {
 173     return const_set_bits_iterator(*this);
 174   }
 175
 176   const_set_bits_iterator set_bits_end() const {
 177     return const_set_bits_iterator(*this, -1);
 178   }
 179
 180   iterator_range<const_set_bits_iterator> set_bits() const {
 181     return make_range(set_bits_begin(), set_bits_end());
 182   }
 183
 184   bool isSmall() const { return X & uintptr_t(1); }
 185
 186   /// Tests whether there are no bits in this bitvector.
 187   bool empty() const {
 188     return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
 189   }
 190
 191   /// Returns the number of bits in this bitvector.
 192   size_t size() const {
 193     return isSmall() ? getSmallSize() : getPointer()->size();
 194   }
 195
 196   /// Returns the number of bits which are set.
 197   size_type count() const {
 198     if (isSmall()) {
 199       uintptr_t Bits = getSmallBits();
 200       return countPopulation(Bits);
 201     }
 202     return getPointer()->count();
 203   }
 204
 205   /// Returns true if any bit is set.
 206   bool any() const {
 207     if (isSmall())
 208       return getSmallBits() != 0;
 209     return getPointer()->any();
 210   }
 211
 212   /// Returns true if all bits are set.
 213   bool all() const {
 214     if (isSmall())
 215       return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
 216     return getPointer()->all();
 217   }
 218
 219   /// Returns true if none of the bits are set.
 220   bool none() const {
 221     if (isSmall())
 222       return getSmallBits() == 0;
 223     return getPointer()->none();
 224   }
 225
 226   /// Returns the index of the first set bit, -1 if none of the bits are set.
 227   int find_first() const {
 228     if (isSmall()) {
 229       uintptr_t Bits = getSmallBits();
 230       if (Bits == 0)
 231         return -1;
 232       return countTrailingZeros(Bits);
 233     }
 234     return getPointer()->find_first();
 235   }
 236
 237   int find_last() const {
 238     if (isSmall()) {
 239       uintptr_t Bits = getSmallBits();
 240       if (Bits == 0)
 241         return -1;
 242       return NumBaseBits - countLeadingZeros(Bits) - 1;
 243     }
 244     return getPointer()->find_last();
 245   }
 246
 247   /// Returns the index of the first unset bit, -1 if all of the bits are set.
 248   int find_first_unset() const {
 249     if (isSmall()) {
 250       if (count() == getSmallSize())
 251         return -1;
 252
 253       uintptr_t Bits = getSmallBits();
 254       return countTrailingOnes(Bits);
 255     }
 256     return getPointer()->find_first_unset();
 257   }
 258
 259   int find_last_unset() const {
 260     if (isSmall()) {
 261       if (count() == getSmallSize())
 262         return -1;
 263
 264       uintptr_t Bits = getSmallBits();
 265       // Set unused bits.
 266       Bits |= ~uintptr_t(0) << getSmallSize();
 267       return NumBaseBits - countLeadingOnes(Bits) - 1;
 268     }
 269     return getPointer()->find_last_unset();
 270   }
 271
 272   /// Returns the index of the next set bit following the "Prev" bit.
 273   /// Returns -1 if the next set bit is not found.
 274   int find_next(unsigned Prev) const {
 275     if (isSmall()) {
 276       uintptr_t Bits = getSmallBits();
 277       // Mask off previous bits.
 278       Bits &= ~uintptr_t(0) << (Prev + 1);
 279       if (Bits == 0 || Prev + 1 >= getSmallSize())
 280         return -1;
 281       return countTrailingZeros(Bits);
 282     }
 283     return getPointer()->find_next(Prev);
 284   }
 285
 286   /// Returns the index of the next unset bit following the "Prev" bit.
 287   /// Returns -1 if the next unset bit is not found.
 288   int find_next_unset(unsigned Prev) const {
 289     if (isSmall()) {
 290       ++Prev;
 291       uintptr_t Bits = getSmallBits();
 292       // Mask in previous bits.
 293       uintptr_t Mask = (uintptr_t(1) << Prev) - 1;
 294       Bits |= Mask;
 295
 296       if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
 297         return -1;
 298       return countTrailingOnes(Bits);
 299     }
 300     return getPointer()->find_next_unset(Prev);
 301   }
 302
 303   /// find_prev - Returns the index of the first set bit that precedes the
 304   /// the bit at \p PriorTo.  Returns -1 if all previous bits are unset.
 305   int find_prev(unsigned PriorTo) const {
 306     if (isSmall()) {
 307       if (PriorTo == 0)
 308         return -1;
 309
 310       --PriorTo;
 311       uintptr_t Bits = getSmallBits();
 312       Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
 313       if (Bits == 0)
 314         return -1;
 315
 316       return NumBaseBits - countLeadingZeros(Bits) - 1;
 317     }
 318     return getPointer()->find_prev(PriorTo);
 319   }
 320
 321   /// Clear all bits.
 322   void clear() {
 323     if (!isSmall())
 324       delete getPointer();
 325     switchToSmall(0, 0);
 326   }
 327
 328   /// Grow or shrink the bitvector.
 329   void resize(unsigned N, bool t = false) {
 330     if (!isSmall()) {
 331       getPointer()->resize(N, t);
 332     } else if (SmallNumDataBits >= N) {
 333       uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
 334       setSmallSize(N);
 335       setSmallBits(NewBits | getSmallBits());
 336     } else {
 337       BitVector *BV = new BitVector(N, t);
 338       uintptr_t OldBits = getSmallBits();
 339       for (size_t i = 0, e = getSmallSize(); i != e; ++i)
 340         (*BV)[i] = (OldBits >> i) & 1;
 341       switchToLarge(BV);
 342     }
 343   }
 344
 345   void reserve(unsigned N) {
 346     if (isSmall()) {
 347       if (N > SmallNumDataBits) {
 348         uintptr_t OldBits = getSmallRawBits();
 349         size_t SmallSize = getSmallSize();
 350         BitVector *BV = new BitVector(SmallSize);
 351         for (size_t i = 0; i < SmallSize; ++i)
 352           if ((OldBits >> i) & 1)
 353             BV->set(i);
 354         BV->reserve(N);
 355         switchToLarge(BV);
 356       }
 357     } else {
 358       getPointer()->reserve(N);
 359     }
 360   }
 361
 362   // Set, reset, flip
 363   SmallBitVector &set() {
 364     if (isSmall())
 365       setSmallBits(~uintptr_t(0));
 366     else
 367       getPointer()->set();
 368     return *this;
 369   }
 370
 371   SmallBitVector &set(unsigned Idx) {
 372     if (isSmall()) {
 373       assert(Idx <= static_cast<unsigned>(
 374                         std::numeric_limits<uintptr_t>::digits) &&
 375              "undefined behavior");
 376       setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
 377     }
 378     else
 379       getPointer()->set(Idx);
 380     return *this;
 381   }
 382
 383   /// Efficiently set a range of bits in [I, E)
 384   SmallBitVector &set(unsigned I, unsigned E) {
 385     assert(I <= E && "Attempted to set backwards range!");
 386     assert(E <= size() && "Attempted to set out-of-bounds range!");
 387     if (I == E) return *this;
 388     if (isSmall()) {
 389       uintptr_t EMask = ((uintptr_t)1) << E;
 390       uintptr_t IMask = ((uintptr_t)1) << I;
 391       uintptr_t Mask = EMask - IMask;
 392       setSmallBits(getSmallBits() | Mask);
 393     } else
 394       getPointer()->set(I, E);
 395     return *this;
 396   }
 397
 398   SmallBitVector &reset() {
 399     if (isSmall())
 400       setSmallBits(0);
 401     else
 402       getPointer()->reset();
 403     return *this;
 404   }
 405
 406   SmallBitVector &reset(unsigned Idx) {
 407     if (isSmall())
 408       setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
 409     else
 410       getPointer()->reset(Idx);
 411     return *this;
 412   }
 413
 414   /// Efficiently reset a range of bits in [I, E)
 415   SmallBitVector &reset(unsigned I, unsigned E) {
 416     assert(I <= E && "Attempted to reset backwards range!");
 417     assert(E <= size() && "Attempted to reset out-of-bounds range!");
 418     if (I == E) return *this;
 419     if (isSmall()) {
 420       uintptr_t EMask = ((uintptr_t)1) << E;
 421       uintptr_t IMask = ((uintptr_t)1) << I;
 422       uintptr_t Mask = EMask - IMask;
 423       setSmallBits(getSmallBits() & ~Mask);
 424     } else
 425       getPointer()->reset(I, E);
 426     return *this;
 427   }
 428
 429   SmallBitVector &flip() {
 430     if (isSmall())
 431       setSmallBits(~getSmallBits());
 432     else
 433       getPointer()->flip();
 434     return *this;
 435   }
 436
 437   SmallBitVector &flip(unsigned Idx) {
 438     if (isSmall())
 439       setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
 440     else
 441       getPointer()->flip(Idx);
 442     return *this;
 443   }
 444
 445   // No argument flip.
 446   SmallBitVector operator~() const {
 447     return SmallBitVector(*this).flip();
 448   }
 449
 450   // Indexing.
 451   reference operator[](unsigned Idx) {
 452     assert(Idx < size() && "Out-of-bounds Bit access.");
 453     return reference(*this, Idx);
 454   }
 455
 456   bool operator[](unsigned Idx) const {
 457     assert(Idx < size() && "Out-of-bounds Bit access.");
 458     if (isSmall())
 459       return ((getSmallBits() >> Idx) & 1) != 0;
 460     return getPointer()->operator[](Idx);
 461   }
 462
 463   bool test(unsigned Idx) const {
 464     return (*this)[Idx];
 465   }
 466
 467   // Push single bit to end of vector.
 468   void push_back(bool Val) {
 469     resize(size() + 1, Val);
 470   }
 471
 472   /// Test if any common bits are set.
 473   bool anyCommon(const SmallBitVector &RHS) const {
 474     if (isSmall() && RHS.isSmall())
 475       return (getSmallBits() & RHS.getSmallBits()) != 0;
 476     if (!isSmall() && !RHS.isSmall())
 477       return getPointer()->anyCommon(*RHS.getPointer());
 478
 479     for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
 480       if (test(i) && RHS.test(i))
 481         return true;
 482     return false;
 483   }
 484
 485   // Comparison operators.
 486   bool operator==(const SmallBitVector &RHS) const {
 487     if (size() != RHS.size())
 488       return false;
 489     if (isSmall() && RHS.isSmall())
 490       return getSmallBits() == RHS.getSmallBits();
 491     else if (!isSmall() && !RHS.isSmall())
 492       return *getPointer() == *RHS.getPointer();
 493     else {
 494       for (size_t i = 0, e = size(); i != e; ++i) {
 495         if ((*this)[i] != RHS[i])
 496           return false;
 497       }
 498       return true;
 499     }
 500   }
 501
 502   bool operator!=(const SmallBitVector &RHS) const {
 503     return !(*this == RHS);
 504   }
 505
 506   // Intersection, union, disjoint union.
 507   // FIXME BitVector::operator&= does not resize the LHS but this does
 508   SmallBitVector &operator&=(const SmallBitVector &RHS) {
 509     resize(std::max(size(), RHS.size()));
 510     if (isSmall() && RHS.isSmall())
 511       setSmallBits(getSmallBits() & RHS.getSmallBits());
 512     else if (!isSmall() && !RHS.isSmall())
 513       getPointer()->operator&=(*RHS.getPointer());
 514     else {
 515       size_t i, e;
 516       for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
 517         (*this)[i] = test(i) && RHS.test(i);
 518       for (e = size(); i != e; ++i)
 519         reset(i);
 520     }
 521     return *this;
 522   }
 523
 524   /// Reset bits that are set in RHS. Same as *this &= ~RHS.
 525   SmallBitVector &reset(const SmallBitVector &RHS) {
 526     if (isSmall() && RHS.isSmall())
 527       setSmallBits(getSmallBits() & ~RHS.getSmallBits());
 528     else if (!isSmall() && !RHS.isSmall())
 529       getPointer()->reset(*RHS.getPointer());
 530     else
 531       for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
 532         if (RHS.test(i))
 533           reset(i);
 534
 535     return *this;
 536   }
 537
 538   /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
 539   bool test(const SmallBitVector &RHS) const {
 540     if (isSmall() && RHS.isSmall())
 541       return (getSmallBits() & ~RHS.getSmallBits()) != 0;
 542     if (!isSmall() && !RHS.isSmall())
 543       return getPointer()->test(*RHS.getPointer());
 544
 545     unsigned i, e;
 546     for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
 547       if (test(i) && !RHS.test(i))
 548         return true;
 549
 550     for (e = size(); i != e; ++i)
 551       if (test(i))
 552         return true;
 553
 554     return false;
 555   }
 556
 557   SmallBitVector &operator|=(const SmallBitVector &RHS) {
 558     resize(std::max(size(), RHS.size()));
 559     if (isSmall() && RHS.isSmall())
 560       setSmallBits(getSmallBits() | RHS.getSmallBits());
 561     else if (!isSmall() && !RHS.isSmall())
 562       getPointer()->operator|=(*RHS.getPointer());
 563     else {
 564       for (size_t i = 0, e = RHS.size(); i != e; ++i)
 565         (*this)[i] = test(i) || RHS.test(i);
 566     }
 567     return *this;
 568   }
 569
 570   SmallBitVector &operator^=(const SmallBitVector &RHS) {
 571     resize(std::max(size(), RHS.size()));
 572     if (isSmall() && RHS.isSmall())
 573       setSmallBits(getSmallBits() ^ RHS.getSmallBits());
 574     else if (!isSmall() && !RHS.isSmall())
 575       getPointer()->operator^=(*RHS.getPointer());
 576     else {
 577       for (size_t i = 0, e = RHS.size(); i != e; ++i)
 578         (*this)[i] = test(i) != RHS.test(i);
 579     }
 580     return *this;
 581   }
 582
 583   SmallBitVector &operator<<=(unsigned N) {
 584     if (isSmall())
 585       setSmallBits(getSmallBits() << N);
 586     else
 587       getPointer()->operator<<=(N);
 588     return *this;
 589   }
 590
 591   SmallBitVector &operator>>=(unsigned N) {
 592     if (isSmall())
 593       setSmallBits(getSmallBits() >> N);
 594     else
 595       getPointer()->operator>>=(N);
 596     return *this;
 597   }
 598
 599   // Assignment operator.
 600   const SmallBitVector &operator=(const SmallBitVector &RHS) {
 601     if (isSmall()) {
 602       if (RHS.isSmall())
 603         X = RHS.X;
 604       else
 605         switchToLarge(new BitVector(*RHS.getPointer()));
 606     } else {
 607       if (!RHS.isSmall())
 608         *getPointer() = *RHS.getPointer();
 609       else {
 610         delete getPointer();
 611         X = RHS.X;
 612       }
 613     }
 614     return *this;
 615   }
 616
 617   const SmallBitVector &operator=(SmallBitVector &&RHS) {
 618     if (this != &RHS) {
 619       clear();
 620       swap(RHS);
 621     }
 622     return *this;
 623   }
 624
 625   void swap(SmallBitVector &RHS) {
 626     std::swap(X, RHS.X);
 627   }
 628
 629   /// Add '1' bits from Mask to this vector. Don't resize.
 630   /// This computes "*this |= Mask".
 631   void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
 632     if (isSmall())
 633       applyMask<true, false>(Mask, MaskWords);
 634     else
 635       getPointer()->setBitsInMask(Mask, MaskWords);
 636   }
 637
 638   /// Clear any bits in this vector that are set in Mask. Don't resize.
 639   /// This computes "*this &= ~Mask".
 640   void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
 641     if (isSmall())
 642       applyMask<false, false>(Mask, MaskWords);
 643     else
 644       getPointer()->clearBitsInMask(Mask, MaskWords);
 645   }
 646
 647   /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
 648   /// This computes "*this |= ~Mask".
 649   void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
 650     if (isSmall())
 651       applyMask<true, true>(Mask, MaskWords);
 652     else
 653       getPointer()->setBitsNotInMask(Mask, MaskWords);
 654   }
 655
 656   /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
 657   /// This computes "*this &= Mask".
 658   void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
 659     if (isSmall())
 660       applyMask<false, true>(Mask, MaskWords);
 661     else
 662       getPointer()->clearBitsNotInMask(Mask, MaskWords);
 663   }
 664
 665 private:
 666   template <bool AddBits, bool InvertMask>
 667   void applyMask(const uint32_t *Mask, unsigned MaskWords) {
 668     assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
 669     uintptr_t M = Mask[0];
 670     if (NumBaseBits == 64)
 671       M |= uint64_t(Mask[1]) << 32;
 672     if (InvertMask)
 673       M = ~M;
 674     if (AddBits)
 675       setSmallBits(getSmallBits() | M);
 676     else
 677       setSmallBits(getSmallBits() & ~M);
 678   }
 679 };
 680
 681 inline SmallBitVector
 682 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 683   SmallBitVector Result(LHS);
 684   Result &= RHS;
 685   return Result;
 686 }
 687
 688 inline SmallBitVector
 689 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 690   SmallBitVector Result(LHS);
 691   Result |= RHS;
 692   return Result;
 693 }
 694
 695 inline SmallBitVector
 696 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
 697   SmallBitVector Result(LHS);
 698   Result ^= RHS;
 699   return Result;
 700 }
 701
 702 } // end namespace llvm
 703
 704 namespace std {
 705
 706 /// Implement std::swap in terms of BitVector swap.
 707 inline void
 708 swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
 709   LHS.swap(RHS);
 710 }
 711
 712 } // end namespace std
 713
 714 #endif // LLVM_ADT_SMALLBITVECTOR_H