Subzero. Liveness memory management.

src/IceBitVector.h

 //===- subzero/src/IceBitVector.h - Inline bit vector. ----------*- C++ -*-===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 228 matching lines @@
       Bits[Pos] ^= ~ElementType(0);
     } else {
       const ElementType Mask =
           (ElementType(1) << (size() - (Pos * NumBitsPerPos))) - 1;
       Bits[Pos] ^= Mask;
     }
     invert<Pos + 1>();
   }
 };
 
-class BitVector {
+template <template <typename> class AT> class BitVectorTmpl {
   typedef unsigned long BitWord;
-  using Allocator = CfgLocalAllocator<BitWord>;
+  using Allocator = AT<BitWord>;
 
   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
 
   static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
                 "Unsupported word size");
 
   BitWord *Bits;     // Actual bits.
   unsigned Size;     // Size of bitvector in bits.
   unsigned Capacity; // Size of allocated memory in BitWord.
   Allocator Alloc;
 
 public:
   typedef unsigned size_type;
   // Encapsulation of a single bit.
   class reference {
-    friend class BitVector;
+    friend class BitVectorTmpl;
 
     BitWord *WordRef;
     unsigned BitPos;
 
     reference(); // Undefined
 
   public:
-    reference(BitVector &b, unsigned Idx) {
+    reference(BitVectorTmpl &b, unsigned Idx) {
       WordRef = &b.Bits[Idx / BITWORD_SIZE];
       BitPos = Idx % BITWORD_SIZE;
     }
 
     reference(const reference &) = default;
 
     reference &operator=(reference t) {
       *this = bool(t);
       return *this;
     }
 
     reference &operator=(bool t) {
       if (t)
         *WordRef |= BitWord(1) << BitPos;
       else
         *WordRef &= ~(BitWord(1) << BitPos);
       return *this;
     }
 
     operator bool() const {
       return ((*WordRef) & (BitWord(1) << BitPos)) ? true : false;
     }
   };
 
-  /// BitVector default ctor - Creates an empty bitvector.
-  BitVector(Allocator A = Allocator())
+  /// BitVectorTmpl default ctor - Creates an empty bitvector.
+  BitVectorTmpl(Allocator A = Allocator())
       : Size(0), Capacity(0), Alloc(std::move(A)) {
     Bits = nullptr;
   }
 
-  /// BitVector ctor - Creates a bitvector of specified number of bits. All
+  /// BitVectorTmpl ctor - Creates a bitvector of specified number of bits. All
   /// bits are initialized to the specified value.
-  explicit BitVector(unsigned s, bool t = false, Allocator A = Allocator())
+  explicit BitVectorTmpl(unsigned s, bool t = false, Allocator A = Allocator())
       : Size(s), Alloc(std::move(A)) {
     Capacity = NumBitWords(s);
     Bits = Alloc.allocate(Capacity);
     init_words(Bits, Capacity, t);
     if (t)
       clear_unused_bits();
   }
 
-  /// BitVector copy ctor.
-  BitVector(const BitVector &RHS) : Size(RHS.size()), Alloc(RHS.Alloc) {
+  /// BitVectorTmpl copy ctor.
+  BitVectorTmpl(const BitVectorTmpl &RHS) : Size(RHS.size()), Alloc(RHS.Alloc) {
     if (Size == 0) {
       Bits = nullptr;
       Capacity = 0;
       return;
     }
 
     Capacity = NumBitWords(RHS.size());
     Bits = Alloc.allocate(Capacity);
     std::memcpy(Bits, RHS.Bits, Capacity * sizeof(BitWord));
   }
 
-  BitVector(BitVector &&RHS)
+  BitVectorTmpl(BitVectorTmpl &&RHS)
       : Bits(RHS.Bits), Size(RHS.Size), Capacity(RHS.Capacity),
         Alloc(std::move(RHS.Alloc)) {
     RHS.Bits = nullptr;
   }
 
-  ~BitVector() {
+  ~BitVectorTmpl() {
     if (Bits != nullptr) {
       Alloc.deallocate(Bits, Capacity);
     }
   }
 
   /// empty - Tests whether there are no bits in this bitvector.
   bool empty() const { return Size == 0; }
 
   /// size - Returns the number of bits in this bitvector.
   size_type size() const { return Size; }
@@ skipping 66 matching lines @@
   void clear() { Size = 0; }
 
   /// resize - Grow or shrink the bitvector.
   void resize(unsigned N, bool t = false) {
     if (N > Capacity * BITWORD_SIZE) {
       unsigned OldCapacity = Capacity;
       grow(N);
       init_words(&Bits[OldCapacity], (Capacity - OldCapacity), t);
     }
 
-    // Set any old unused bits that are now included in the BitVector. This
+    // Set any old unused bits that are now included in the BitVectorTmpl. This
     // may set bits that are not included in the new vector, but we will clear
     // them back out below.
     if (N > Size)
       set_unused_bits(t);
 
     // Update the size, and clear out any bits that are now unused
     unsigned OldSize = Size;
     Size = N;
     if (t || N < OldSize)
       clear_unused_bits();
   }
 
   void reserve(unsigned N) {
     if (N > Capacity * BITWORD_SIZE)
       grow(N);
   }
 
   // Set, reset, flip
-  BitVector &set() {
+  BitVectorTmpl &set() {
     init_words(Bits, Capacity, true);
     clear_unused_bits();
     return *this;
   }
 
-  BitVector &set(unsigned Idx) {
+  BitVectorTmpl &set(unsigned Idx) {
     assert(Bits && "Bits never allocated");
     Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
     return *this;
   }
 
   /// set - Efficiently set a range of bits in [I, E)
-  BitVector &set(unsigned I, unsigned E) {
+  BitVectorTmpl &set(unsigned I, unsigned E) {
     assert(I <= E && "Attempted to set backwards range!");
     assert(E <= size() && "Attempted to set out-of-bounds range!");
 
     if (I == E)
       return *this;
 
     if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
       BitWord EMask = 1UL << (E % BITWORD_SIZE);
       BitWord IMask = 1UL << (I % BITWORD_SIZE);
       BitWord Mask = EMask - IMask;
       Bits[I / BITWORD_SIZE] |= Mask;
       return *this;
     }
 
     BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
     Bits[I / BITWORD_SIZE] |= PrefixMask;
     I = llvm::RoundUpToAlignment(I, BITWORD_SIZE);
 
     for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
       Bits[I / BITWORD_SIZE] = ~0UL;
 
     BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
     if (I < E)
       Bits[I / BITWORD_SIZE] |= PostfixMask;
 
     return *this;
   }
 
-  BitVector &reset() {
+  BitVectorTmpl &reset() {
     init_words(Bits, Capacity, false);
     return *this;
   }
 
-  BitVector &reset(unsigned Idx) {
+  BitVectorTmpl &reset(unsigned Idx) {
     Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
     return *this;
   }
 
   /// reset - Efficiently reset a range of bits in [I, E)
-  BitVector &reset(unsigned I, unsigned E) {
+  BitVectorTmpl &reset(unsigned I, unsigned E) {
     assert(I <= E && "Attempted to reset backwards range!");
     assert(E <= size() && "Attempted to reset out-of-bounds range!");
 
     if (I == E)
       return *this;
 
     if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
       BitWord EMask = 1UL << (E % BITWORD_SIZE);
       BitWord IMask = 1UL << (I % BITWORD_SIZE);
       BitWord Mask = EMask - IMask;
       Bits[I / BITWORD_SIZE] &= ~Mask;
       return *this;
     }
 
     BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
     Bits[I / BITWORD_SIZE] &= ~PrefixMask;
     I = llvm::RoundUpToAlignment(I, BITWORD_SIZE);
 
     for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
       Bits[I / BITWORD_SIZE] = 0UL;
 
     BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
     if (I < E)
       Bits[I / BITWORD_SIZE] &= ~PostfixMask;
 
     return *this;
   }
 
-  BitVector &flip() {
+  BitVectorTmpl &flip() {
     for (unsigned i = 0; i < NumBitWords(size()); ++i)
       Bits[i] = ~Bits[i];
     clear_unused_bits();
     return *this;
   }
 
-  BitVector &flip(unsigned Idx) {
+  BitVectorTmpl &flip(unsigned Idx) {
     Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
     return *this;
   }
 
   // Indexing.
   reference operator[](unsigned Idx) {
     assert(Idx < Size && "Out-of-bounds Bit access.");
     return reference(*this, Idx);
   }
 
   bool operator[](unsigned Idx) const {
     assert(Idx < Size && "Out-of-bounds Bit access.");
     BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
     return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
   }
 
   bool test(unsigned Idx) const { return (*this)[Idx]; }
 
   /// Test if any common bits are set.
-  bool anyCommon(const BitVector &RHS) const {
+  bool anyCommon(const BitVectorTmpl &RHS) const {
     unsigned ThisWords = NumBitWords(size());
     unsigned RHSWords = NumBitWords(RHS.size());
     for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
       if (Bits[i] & RHS.Bits[i])
         return true;
     return false;
   }
 
   // Comparison operators.
-  bool operator==(const BitVector &RHS) const {
+  bool operator==(const BitVectorTmpl &RHS) const {
     unsigned ThisWords = NumBitWords(size());
     unsigned RHSWords = NumBitWords(RHS.size());
     unsigned i;
     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
       if (Bits[i] != RHS.Bits[i])
         return false;
 
     // Verify that any extra words are all zeros.
     if (i != ThisWords) {
       for (; i != ThisWords; ++i)
         if (Bits[i])
           return false;
     } else if (i != RHSWords) {
       for (; i != RHSWords; ++i)
         if (RHS.Bits[i])
           return false;
     }
     return true;
   }
 
-  bool operator!=(const BitVector &RHS) const { return !(*this == RHS); }
+  bool operator!=(const BitVectorTmpl &RHS) const { return !(*this == RHS); }
 
   /// Intersection, union, disjoint union.
-  BitVector &operator&=(const BitVector &RHS) {
+  BitVectorTmpl &operator&=(const BitVectorTmpl &RHS) {
     unsigned ThisWords = NumBitWords(size());
     unsigned RHSWords = NumBitWords(RHS.size());
     unsigned i;
     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
       Bits[i] &= RHS.Bits[i];
 
     // Any bits that are just in this bitvector become zero, because they aren't
     // in the RHS bit vector.  Any words only in RHS are ignored because they
     // are already zero in the LHS.
     for (; i != ThisWords; ++i)
       Bits[i] = 0;
 
     return *this;
   }
 
   /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
-  BitVector &reset(const BitVector &RHS) {
+  BitVectorTmpl &reset(const BitVectorTmpl &RHS) {
     unsigned ThisWords = NumBitWords(size());
     unsigned RHSWords = NumBitWords(RHS.size());
     unsigned i;
     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
       Bits[i] &= ~RHS.Bits[i];
     return *this;
   }
 
   /// test - Check if (This - RHS) is zero.
   /// This is the same as reset(RHS) and any().
-  bool test(const BitVector &RHS) const {
+  bool test(const BitVectorTmpl &RHS) const {
     unsigned ThisWords = NumBitWords(size());
     unsigned RHSWords = NumBitWords(RHS.size());
     unsigned i;
     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
       if ((Bits[i] & ~RHS.Bits[i]) != 0)
         return true;
 
     for (; i != ThisWords; ++i)
       if (Bits[i] != 0)
         return true;
 
     return false;
   }
 
-  BitVector &operator|=(const BitVector &RHS) {
+  BitVectorTmpl &operator|=(const BitVectorTmpl &RHS) {
     if (size() < RHS.size())
       resize(RHS.size());
     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
       Bits[i] |= RHS.Bits[i];
     return *this;
   }
 
-  BitVector &operator^=(const BitVector &RHS) {
+  BitVectorTmpl &operator^=(const BitVectorTmpl &RHS) {
     if (size() < RHS.size())
       resize(RHS.size());
     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
       Bits[i] ^= RHS.Bits[i];
     return *this;
   }
 
   // Assignment operator.
-  const BitVector &operator=(const BitVector &RHS) {
+  const BitVectorTmpl &operator=(const BitVectorTmpl &RHS) {
     if (this == &RHS)
       return *this;
 
     Size = RHS.size();
     unsigned RHSWords = NumBitWords(Size);
     if (Size <= Capacity * BITWORD_SIZE) {
       if (Size)
         std::memcpy(Bits, RHS.Bits, RHSWords * sizeof(BitWord));
       clear_unused_bits();
       return *this;
     }
 
-    // Currently, BitVector is only used by liveness analysis.  With the
-    // following assert, we make sure BitVectors grow in a single step from 0 to
+    // Currently, BitVectorTmpl is only used by liveness analysis.  With the
+    // following assert, we make sure BitVectorTmpls grow in a single step from

[Jim Stichnoth, 2016/03/31 16:23:20]

reflow comment

[John, 2016/04/01 13:52:04]

Done.

+    // 0 to
     // their final capacity, rather than growing slowly and "leaking" memory in
     // the process.
     assert(Capacity == 0);
 
     // Grow the bitvector to have enough elements.
     const auto OldCapacity = Capacity;
     Capacity = RHSWords;
     assert(Capacity > 0 && "negative capacity?");
     BitWord *NewBits = Alloc.allocate(Capacity);
     std::memcpy(NewBits, RHS.Bits, Capacity * sizeof(BitWord));
 
     // Destroy the old bits.
     Alloc.deallocate(Bits, OldCapacity);
     Bits = NewBits;
 
     return *this;
   }
 
-  const BitVector &operator=(BitVector &&RHS) {
+  const BitVectorTmpl &operator=(BitVectorTmpl &&RHS) {
     if (this == &RHS)
       return *this;
 
     Alloc.deallocate(Bits, Capacity);
     Bits = RHS.Bits;
     Size = RHS.Size;
     Capacity = RHS.Capacity;
 
     RHS.Bits = nullptr;
 
     return *this;
   }
 
-  void swap(BitVector &RHS) {
+  void swap(BitVectorTmpl &RHS) {
     std::swap(Bits, RHS.Bits);
     std::swap(Size, RHS.Size);
     std::swap(Capacity, RHS.Capacity);
   }
 
   //===--------------------------------------------------------------------===//
   // Portable bit mask operations.
   //===--------------------------------------------------------------------===//
   //
   // These methods all operate on arrays of uint32_t, each holding 32 bits. The
   // fixed word size makes it easier to work with literal bit vector constants
   // in portable code.
   //
   // The LSB in each word is the lowest numbered bit.  The size of a portable
   // bit mask is always a whole multiple of 32 bits.  If no bit mask size is
-  // given, the bit mask is assumed to cover the entire BitVector.
+  // given, the bit mask is assumed to cover the entire BitVectorTmpl.
 
   /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
   /// This computes "*this |= Mask".
   void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
     applyMask<true, false>(Mask, MaskWords);
   }
 
   /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
   /// Don't resize. This computes "*this &= ~Mask".
   void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
@@ skipping 81 matching lines @@
       if (AddBits)
         Bits[i] |= BitWord(M) << b;
       else
         Bits[i] &= ~(BitWord(M) << b);
     }
     if (AddBits)
       clear_unused_bits();
   }
 };
 
+using BitVector = BitVectorTmpl<CfgLocalAllocator>;
+
 } // end of namespace Ice
 
 namespace std {
-/// Implement std::swap in terms of BitVector swap.
-inline void swap(Ice::BitVector &LHS, Ice::BitVector &RHS) { LHS.swap(RHS); }
+/// Implement std::swap in terms of BitVectorTmpl swap.
+template <template <typename> class AT>
+inline void swap(Ice::BitVectorTmpl<AT> &LHS, Ice::BitVectorTmpl<AT> &RHS) {
+  LHS.swap(RHS);
+}
 }
 
 #endif // SUBZERO_SRC_ICEBITVECTOR_H