Subzero. Performance tweaks.

src/IceBitVector.h

Index: src/IceBitVector.h
diff --git a/src/IceBitVector.h b/src/IceBitVector.h
new file mode 100644
index 0000000000000000000000000000000000000000..37dbc663e11f3ca418c9a42b59e0e5c58cebdf72
--- /dev/null
+++ b/src/IceBitVector.h
@@ -0,0 +1,251 @@
+

[Jim Stichnoth, 2016/02/24 23:11:39]

remove leading blank line

[John, 2016/02/24 23:46:05]

Done.

+//===- 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

[Jim Stichnoth, 2016/02/24 23:11:38]

reflow comment

[John, 2016/02/24 23:46:05]

Done.

+/// drop in replacement for llvm::SmallSmallBitVector in subzero -- i.e., not

[Jim Stichnoth, 2016/02/24 23:11:39]

SmallSmall
here and below

[John, 2016/02/24 23:46:05]

Done.

+/// all of
+/// llvm::SmallSmallBitVector 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 NumBitsPerPos = sizeof(ElementType) * CHAR_BIT;
+
+  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() {
+    static_assert(sizeof(Bits) == 16, "");

[Jim Stichnoth, 2016/02/24 23:11:38]

Can you remove this?  Seems to be also tested below.

[John, 2016/02/24 23:46:05]

Done.

+    memset(Bits, 0, sizeof(Bits));
+  }
+
+  explicit SmallBitVector(SizeT S) : SmallBitVector() {
+    resize(S);
+    assert(Size <= sizeof(Bits) * CHAR_BIT);

[Jim Stichnoth, 2016/02/24 23:11:39]

constexpr

[John, 2016/02/24 23:46:05]

Done.

+  }
+
+  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 |= 1ull << Bit;
+      } else {
+        *Data &= ~(1ull << Bit);
+      }
+      return *this;
+    }
+    operator bool() const { return (*Data & (1ull << Bit)) != 0; }
+
+  private:
+    friend class SmallBitVector;
+    Reference(uint64_t *D, SizeT B) : Data(D), Bit(B) {

[Jim Stichnoth, 2016/02/24 23:11:38]

ElementType instead of uint64_t ?

[John, 2016/02/24 23:46:05]

Done.

+      assert(B < CHAR_BIT * sizeof(*D));
+    }
+
+    uint64_t *const Data;
+    const SizeT Bit;
+  };
+
+  Reference operator[](unsigned Idx) {
+    assert(Idx < size());
+    // return Reference(Bits + (Idx >> llvm::Log2_64(NumBitsPerPos)),

[Jim Stichnoth, 2016/02/24 23:11:39]

remove commented code

[John, 2016/02/24 23:46:05]

Done.

+    //                Idx & ((1ull << llvm::Log2_64(NumBitsPerPos))-1));
+    return Reference(Bits + (Idx >> 6), Idx & ((1ull << 6) - 1));

[Jim Stichnoth, 2016/02/24 23:11:39]

All these "6" should be constexpr, with a static_assert to validate.

[John, 2016/02/24 23:46:05]

Done.

+  }
+
+  bool operator[](unsigned Idx) const {
+    assert(Idx < size());
+    return Bits[Idx >> 6] & (1ull << (Idx & ((1ull << 6) - 1)));

[Jim Stichnoth, 2016/02/24 23:11:39]

I think it would be nicer for the 1ull to be a constexpr.

[John, 2016/02/24 23:46:05]

Done.

+  }
+
+  int find_first() const { return find_first<0>(); }
+
+  int find_next(unsigned Prev) const { return find_next<0>(Prev); }
+
+  bool any() const { return Bits[0] != 0 || Bits[1] != 0; }

[Jim Stichnoth, 2016/02/24 23:11:39]

Either unroll this automatically like above, or static_assert.

[John, 2016/02/24 23:46:05]

Done.

+
+  SizeT size() const { return Size; }
+
+  void resize(SizeT Size) {
+    assert(Size <= sizeof(Bits) * CHAR_BIT);
+    this->Size = Size;
+  }
+
+  void reserve(SizeT Size) {
+    assert(Size <= sizeof(Bits) * CHAR_BIT);
+    (void)Size;
+  }
+
+  void set(unsigned Idx) {
+    // TODO(jpp): improve.
+    (*this)[Idx] = true;
+  }
+
+  void set() {
+    // TODO(jpp): improve.
+    for (SizeT ii = 0; ii < size(); ++ii) {
+      (*this)[ii] = true;
+    }
+    // set_all<0>();

[Jim Stichnoth, 2016/02/24 23:11:38]

remove comment

[John, 2016/02/24 23:46:05]

Done.

+  }
+
+  SizeT count() const {
+    return llvm::countPopulation(Bits[0]) + llvm::countPopulation(Bits[1]);

[Jim Stichnoth, 2016/02/24 23:11:39]

inline/static_assert
here and below

[John, 2016/02/24 23:46:05]

Done.

+  }
+
+  SmallBitVector operator&(const SmallBitVector &Rhs) const {
+    assert(size() == Rhs.size());
+    SmallBitVector Ret(std::max(size(), Rhs.size()));
+    Ret.Bits[0] = Bits[0] & Rhs.Bits[0];
+    Ret.Bits[1] = Bits[1] & Rhs.Bits[1];
+    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()));
+    Bits[0] |= Rhs.Bits[0];
+    Bits[1] |= Rhs.Bits[1];
+    return *this;
+  }
+
+  SmallBitVector operator|(const SmallBitVector &Rhs) const {
+    assert(size() == Rhs.size());
+    SmallBitVector Ret(std::max(size(), Rhs.size()));
+    Ret.Bits[0] = Bits[0] | Rhs.Bits[0];
+    Ret.Bits[1] = Bits[1] | Rhs.Bits[1];
+    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:
+  ElementType Bits[2];
+  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>();
+  }
+
+  template <SizeT Pos>
+  typename std::enable_if<Pos == sizeof(Bits) / sizeof(Bits[0]), void>::type
+  set_all() {}
+
+  template <SizeT Pos>
+      typename std::enable_if <
+      Pos<sizeof(Bits) / sizeof(Bits[0]), void>::type set_all() {
+    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;
+    }
+    set_all<Pos + 1>();
+  }
+};
+
+} // end of namespace Ice
+
+#endif // SUBZERO_SRC_ICEBITVECTOR_H