Index: src/IceBitVector.h |
diff --git a/src/IceBitVector.h b/src/IceBitVector.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..9c99e8aebd9d801d65961329faef612a0af5aae0 |
--- /dev/null |
+++ b/src/IceBitVector.h |
@@ -0,0 +1,245 @@ |
+//===- 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 |
+/// \brief Defines and implements a bit vector with inline storage. It is a drop |
+/// in replacement for llvm::SmallBitVector in subzero -- i.e., not all of |
+/// llvm::SmallBitVector interface is implemented. |
+/// |
+//===----------------------------------------------------------------------===// |
+ |
+#ifndef SUBZERO_SRC_ICEBITVECTOR_H |
+#define SUBZERO_SRC_ICEBITVECTOR_H |
+ |
+#include "IceDefs.h" |
+#include "IceOperand.h" |
+ |
+#include "llvm/Support/MathExtras.h" |
+ |
+#include <algorithm> |
+#include <climits> |
+#include <memory> |
+#include <type_traits> |
+ |
+namespace Ice { |
+class SmallBitVector { |
+public: |
+ using ElementType = uint64_t; |
+ static constexpr SizeT BitIndexSize = 6; // log2(NumBitsPerPos); |
+ static constexpr SizeT NumBitsPerPos = sizeof(ElementType) * CHAR_BIT; |
+ static_assert(1 << BitIndexSize == NumBitsPerPos, "Invalid BitIndexSize."); |
+ |
+ SmallBitVector(const SmallBitVector &BV) { *this = BV; } |
+ |
+ SmallBitVector &operator=(const SmallBitVector &BV) { |
+ if (&BV != this) { |
+ resize(BV.size()); |
+ memcpy(Bits, BV.Bits, sizeof(Bits)); |
+ } |
+ return *this; |
+ } |
+ |
+ SmallBitVector() { reset(); } |
+ |
+ explicit SmallBitVector(SizeT S) : SmallBitVector() { |
+ assert(S <= MaxBits); |
+ resize(S); |
+ } |
+ |
+ class Reference { |
+ Reference() = delete; |
+ |
+ public: |
+ Reference(const Reference &) = default; |
+ Reference &operator=(const Reference &Rhs) { return *this = (bool)Rhs; } |
+ Reference &operator=(bool t) { |
+ if (t) { |
+ *Data |= _1 << Bit; |
+ } else { |
+ *Data &= ~(_1 << Bit); |
+ } |
+ return *this; |
+ } |
+ operator bool() const { return (*Data & (_1 << Bit)) != 0; } |
+ |
+ private: |
+ friend class SmallBitVector; |
+ Reference(ElementType *D, SizeT B) : Data(D), Bit(B) { |
+ assert(B < NumBitsPerPos); |
+ } |
+ |
+ ElementType *const Data; |
+ const SizeT Bit; |
+ }; |
+ |
+ Reference operator[](unsigned Idx) { |
+ assert(Idx < size()); |
+ return Reference(Bits + (Idx >> BitIndexSize), |
+ Idx & ((_1 << BitIndexSize) - 1)); |
+ } |
+ |
+ bool operator[](unsigned Idx) const { |
+ assert(Idx < size()); |
+ return Bits[Idx >> BitIndexSize] & |
+ (_1 << (Idx & ((_1 << BitIndexSize) - 1))); |
+ } |
+ |
+ int find_first() const { return find_first<0>(); } |
+ |
+ int find_next(unsigned Prev) const { return find_next<0>(Prev); } |
+ |
+ bool any() const { |
+ for (SizeT i = 0; i < BitsElements; ++i) { |
+ if (Bits[i]) { |
+ return true; |
+ } |
+ } |
+ return false; |
+ } |
+ |
+ SizeT size() const { return Size; } |
+ |
+ void resize(SizeT Size) { |
+ assert(Size <= MaxBits); |
+ this->Size = Size; |
+ } |
+ |
+ void reserve(SizeT Size) { |
+ assert(Size <= MaxBits); |
+ (void)Size; |
+ } |
+ |
+ void set(unsigned Idx) { (*this)[Idx] = true; } |
+ |
+ void set() { |
+ for (SizeT ii = 0; ii < size(); ++ii) { |
+ (*this)[ii] = true; |
+ } |
+ } |
+ |
+ SizeT count() const { |
+ SizeT Count = 0; |
+ for (SizeT i = 0; i < BitsElements; ++i) { |
+ Count += llvm::countPopulation(Bits[i]); |
+ } |
+ return Count; |
+ } |
+ |
+ SmallBitVector operator&(const SmallBitVector &Rhs) const { |
+ assert(size() == Rhs.size()); |
+ SmallBitVector Ret(std::max(size(), Rhs.size())); |
+ for (SizeT i = 0; i < BitsElements; ++i) { |
+ Ret.Bits[i] = Bits[i] & Rhs.Bits[i]; |
+ } |
+ return Ret; |
+ } |
+ |
+ SmallBitVector operator~() const { |
+ SmallBitVector Ret = *this; |
+ Ret.invert<0>(); |
+ return Ret; |
+ } |
+ |
+ SmallBitVector &operator|=(const SmallBitVector &Rhs) { |
+ assert(size() == Rhs.size()); |
+ resize(std::max(size(), Rhs.size())); |
+ for (SizeT i = 0; i < BitsElements; ++i) { |
+ Bits[i] |= Rhs.Bits[i]; |
+ } |
+ return *this; |
+ } |
+ |
+ SmallBitVector operator|(const SmallBitVector &Rhs) const { |
+ assert(size() == Rhs.size()); |
+ SmallBitVector Ret(std::max(size(), Rhs.size())); |
+ for (SizeT i = 0; i < BitsElements; ++i) { |
+ Ret.Bits[i] = Bits[i] | Rhs.Bits[i]; |
+ } |
+ return Ret; |
+ } |
+ |
+ void reset() { memset(Bits, 0, sizeof(Bits)); } |
+ |
+ void reset(const SmallBitVector &Mask) { |
+ for (const auto V : RegNumBVIter(Mask)) { |
+ (*this)[unsigned(V)] = false; |
+ } |
+ } |
+ |
+private: |
+ // _1 is the constant 1 of type ElementType. |
+ static constexpr ElementType _1 = ElementType(1); |
+ |
+ static constexpr SizeT BitsElements = 2; |
+ ElementType Bits[BitsElements]; |
+ |
+ // MaxBits is defined here because it needs Bits to be defined. |
+ static constexpr SizeT MaxBits = sizeof(Bits) * CHAR_BIT; |
+ static_assert(sizeof(Bits) == 16, "Bits must be 16 bytes wide."); |
+ SizeT Size = 0; |
+ |
+ template <SizeT Pos> |
+ typename std::enable_if<Pos == sizeof(Bits) / sizeof(Bits[0]), int>::type |
+ find_first() const { |
+ return -1; |
+ } |
+ |
+ template <SizeT Pos> |
+ typename std::enable_if < |
+ Pos<sizeof(Bits) / sizeof(Bits[0]), int>::type find_first() const { |
+ if (Bits[Pos] != 0) { |
+ return NumBitsPerPos * Pos + llvm::countTrailingZeros(Bits[Pos]); |
+ } |
+ return find_first<Pos + 1>(); |
+ } |
+ |
+ template <SizeT Pos> |
+ typename std::enable_if<Pos == sizeof(Bits) / sizeof(Bits[0]), int>::type |
+ find_next(unsigned) const { |
+ return -1; |
+ } |
+ |
+ template <SizeT Pos> |
+ typename std::enable_if < Pos<sizeof(Bits) / sizeof(Bits[0]), int>::type |
+ find_next(unsigned Prev) const { |
+ if (Prev + 1 < (Pos + 1) * NumBitsPerPos) { |
+ const ElementType Mask = |
+ (ElementType(1) << ((Prev + 1) - Pos * NumBitsPerPos)) - 1; |
+ const ElementType B = Bits[Pos] & ~Mask; |
+ if (B != 0) { |
+ return NumBitsPerPos * Pos + llvm::countTrailingZeros(B); |
+ } |
+ Prev = (1 + Pos) * NumBitsPerPos - 1; |
+ } |
+ return find_next<Pos + 1>(Prev); |
+ } |
+ |
+ template <SizeT Pos> |
+ typename std::enable_if<Pos == sizeof(Bits) / sizeof(Bits[0]), void>::type |
+ invert() {} |
+ |
+ template <SizeT Pos> |
+ typename std::enable_if < |
+ Pos<sizeof(Bits) / sizeof(Bits[0]), void>::type invert() { |
+ if (size() < Pos * NumBitsPerPos) { |
+ Bits[Pos] = 0; |
+ } else if ((Pos + 1) * NumBitsPerPos < size()) { |
+ Bits[Pos] ^= ~ElementType(0); |
+ } else { |
+ const ElementType Mask = |
+ (ElementType(1) << (size() - (Pos * NumBitsPerPos))) - 1; |
+ Bits[Pos] ^= Mask; |
+ } |
+ invert<Pos + 1>(); |
+ } |
+}; |
+ |
+} // end of namespace Ice |
+ |
+#endif // SUBZERO_SRC_ICEBITVECTOR_H |