# Node ID 4a178c069ce3089e68f04d5a7d6924bcfce356ea
# Parent  9b5e6bf24743c2a095cd240c6a68aec5ca78ec62
diff --git a/src/base/SConscript b/src/base/SConscript
--- a/src/base/SConscript
+++ b/src/base/SConscript
@@ -1,6 +1,7 @@
 # -*- mode:python -*-
 
 # Copyright (c) 2006 The Regents of The University of Michigan
+# Copyright (c) 2013 Advanced Micro Devices, Inc.
 # All rights reserved.
 #
 # Redistribution and use in source and binary forms, with or without
@@ -36,6 +37,7 @@
 Source('atomicio.cc')
 Source('bigint.cc')
 Source('bitmap.cc')
+Source('bitset.cc')
 Source('callback.cc')
 Source('circlebuf.cc')
 Source('cprintf.cc')
diff --git a/src/base/bitset.hh b/src/base/bitset.hh
new file mode 100644
--- /dev/null
+++ b/src/base/bitset.hh
@@ -0,0 +1,475 @@
+/*
+ * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
+ * Copyright (c) 2013 Advanced Micro Devices, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+// Author: Derek Hower (Derek.Hower@amd.com)
+
+/* The difference between this class and std::bitset/VectorMask is that the
+ * bitset is sized dynamically (you don't need to know at compile time how
+ * many bits are in the bitset). This is like the template specialization for
+ * std::vector<bool>, but with some extra functionality to test/set membership
+ * in ranges, etc.
+ */
+
+#ifndef __BASE_BITSET_HH__
+#define __BASE_BITSET_HH__
+
+#include <cassert>
+#include <ostream>
+
+#include "base/types.hh"
+
+#define MAKE_MASK(mask_size)                 \
+  (((mask_size) == sizeof(T)*8) ?            \
+      static_cast<T>(~0) :                   \
+      (static_cast<T>(1) << (mask_size)) - 1)
+
+// T is the underlying storage type
+// when the bitset size is <= sizeof(T)*8, operations are fast [O(1)]
+// otherwise, operations are ~ O(sizeof(T))
+template <class T>
+class Bitset
+{
+  public:
+    // create a new bitset that holds 'size' bits
+    Bitset();
+    Bitset(int size);
+    Bitset(const Bitset<T>& obj);
+    ~Bitset();
+
+    void init(int size);
+
+    // set bit
+    void set(int pos);
+
+    // set bits from [start, start+size)
+    void setRange(int start, int size);
+
+    // set all bits
+    void setAll();
+
+    // returns true iff bit in 'pos' is set
+    bool test(int pos) const;
+
+    // returns true iff all bits from [start, start+size) are set
+    bool testRange(int start, int size) const;
+
+    // returns true iff all bits are set
+    bool testAll() const;
+
+    // clear bit in pos
+    void clear(int pos);
+
+    // clear bits from [start, start+size)
+    void clearRange(int start, int size);
+
+    // clear all bits
+    void clearAll();
+
+    // merge two sets (union operation)
+    // other must be the same size as this
+    void merge(const Bitset<T> & other);
+
+    // number of bits set
+    int count() const;
+
+    // returns the size of the bitset
+    int size() const { return _size; }
+
+    // only provide read access with []
+    const bool operator[](int pos) const { return test(pos); }
+
+    void print(std::ostream& out) const;
+
+  private:
+    union {
+        T *bits;
+        // when _size < sizeof(T), use opt_bits to avoid memory allocation
+        T opt_bits;
+    };
+    int _size;
+    int num_ints;
+};
+
+typedef Bitset<uint64_t> DefaultBitset;
+
+template <class T>
+Bitset<T>::Bitset()
+{
+    _size = -1;
+    bits = NULL;
+    num_ints = -1;
+}
+
+template <class T>
+Bitset<T>::Bitset(int size)
+{
+    init(size);
+}
+
+template <class T>
+Bitset<T>::Bitset(const Bitset<T>& obj)
+{
+  _size = obj._size;
+  num_ints = obj.num_ints;
+  if (num_ints == 1) {
+    opt_bits = obj.opt_bits;
+  } else if (num_ints > 0) {
+    bits = new T[num_ints];
+    memcpy(bits, obj.bits, obj.num_ints*sizeof(T));
+  } else {
+    bits = NULL;
+  }
+}
+
+template <class T>
+Bitset<T>::~Bitset()
+{
+  if (num_ints > 0) {
+    if (bits != NULL)
+      delete[] bits;
+  }
+}
+
+template <class T>
+void Bitset<T>::init(int size)
+{
+    assert(size > 0);
+    _size = size;
+    num_ints = (size + (sizeof(T)*8-1))/(sizeof(T)*8);
+    if (num_ints > 1) {
+      bits = new T[num_ints];
+      for (int i=0;i<num_ints;i++) {
+        bits[i] = 0;
+      }
+    } else {
+      opt_bits = 0;
+    }
+}
+
+template <class T>
+void
+Bitset<T>::set(int pos)
+{
+    assert(pos >= 0);
+    assert(pos < _size);
+
+    if (num_ints == 1) {
+        opt_bits |= static_cast<T>(1) << pos;
+    } else {
+        // find index
+        int offset = 0;
+        while ( (offset + sizeof(T)*8) <= static_cast<unsigned>(pos)) {
+            offset += sizeof(T)*8;
+        }
+        int idx = offset / (sizeof(T)*8);
+        bits[idx] |= static_cast<T>(1) << (pos - offset);
+    }
+}
+
+template <class T>
+void
+Bitset<T>::setRange(int start, int size)
+{
+  if (size == 0) return;
+  assert(start >= 0);
+  assert(size >= 0);
+  assert(start + size <= _size);
+
+  if (num_ints == 1) {
+      // fast path when there is one container int
+      opt_bits |= ((static_cast<T>(1) << size)-1) << start;
+  } else {
+      // iterate over all container ints
+      unsigned offset = 0;
+      while ( (offset + sizeof(T)*8) <= static_cast<unsigned>(start)) {
+          offset += sizeof(T)*8;
+      }
+      int cur_start = start - offset; // offset in current int
+      int end = start + size;
+
+      int cur_size =                  // number of bits set in this int
+        end - offset > sizeof(T)*8 ?
+        sizeof(T)*8 - cur_start:
+        end - offset - cur_start;
+
+      while (cur_start + offset < end) {
+          int idx = offset / (sizeof(T)*8);
+          cur_size =
+            end - offset > sizeof(T)*8 ?
+            sizeof(T)*8 - cur_start:
+            end - offset - cur_start;
+
+          assert(cur_size + cur_start <= sizeof(T)*8);
+          bits[idx] |= static_cast<T>(MAKE_MASK(cur_size)) << cur_start;
+          cur_start = 0;
+          offset += sizeof(T)*8;
+      }
+  }
+}
+
+template <class T>
+void
+Bitset<T>::setAll()
+{
+  if (num_ints == 1) {
+    opt_bits = static_cast<T>(~0);
+  } else {
+    for (int i=0;i<num_ints;i++) {
+      bits[i] = static_cast<T>(~0);
+    }
+  }
+}
+
+template <class T>
+bool
+Bitset<T>::test(int pos) const
+{
+    assert(pos >= 0);
+    assert(pos < _size);
+
+    if (num_ints == 1) {
+        return (opt_bits & (static_cast<T>(1) << pos)) != 0;
+    } else {
+        // find index
+        int offset = 0;
+        while ( (offset + sizeof(T)*8) <= static_cast<unsigned>(pos)) {
+            offset += sizeof(T)*8;
+        }
+        int idx = offset / (sizeof(T)*8);
+        return (bits[idx] & static_cast<T>(1) << (pos - offset)) != 0;
+    }
+}
+
+template <class T>
+bool
+Bitset<T>::testRange(int start, int size) const
+{
+  if (size == 0) return false;
+  assert(start >= 0);
+  assert(size >= 0);
+  assert(start + size <= _size);
+
+  if (num_ints == 1) {
+      // fast path when there is one container int
+      T mask = MAKE_MASK(size) << start;
+      return (opt_bits & mask) == mask;
+  } else {
+      // iterate over all container ints
+      unsigned offset = 0;
+      while ( (offset + sizeof(T)*8) <= static_cast<unsigned>(start)) {
+          offset += sizeof(T)*8;
+      }
+      int cur_start = start - offset; // offset in current int
+      int end = start + size;
+
+      int cur_size =                  // number of bits set in this int
+        end - offset > sizeof(T)*8 ?
+        sizeof(T)*8 - cur_start:
+        end - offset - cur_start;
+
+      while (cur_start + offset < end) {
+          int idx = offset / (sizeof(T)*8);
+          cur_size =
+            end - offset > sizeof(T)*8 ?
+            sizeof(T)*8 - cur_start:
+            end - offset - cur_start;
+
+          assert(cur_size + cur_start <= sizeof(T)*8);
+          T mask = MAKE_MASK(cur_size) << cur_start;
+          if ((bits[idx] & mask) != mask)
+            return false;
+          cur_start = 0;
+          offset += sizeof(T)*8;
+      }
+      return true;
+  }
+}
+
+template <class T>
+bool
+Bitset<T>::testAll() const
+{
+  if (num_ints == 1) {
+      T mask = MAKE_MASK(_size);
+      return (opt_bits & mask) == mask;
+  } else {
+      int acc_size = 0;
+      for (int idx=0;idx<num_ints;idx++) {
+          if (_size - acc_size > sizeof(T)*8) {
+            if (bits[idx] != static_cast<T>(~0)) {
+                  return false;
+            }
+          } else {
+              T mask = MAKE_MASK(_size - acc_size);
+              if ((bits[idx] & mask) != mask)
+                  return false;
+          }
+          acc_size += sizeof(T)*8;
+      }
+      return true;
+  }
+}
+
+
+template <class T>
+void
+Bitset<T>::clear(int pos)
+{
+    assert(pos >= 0);
+    assert(pos < _size);
+
+    if (num_ints == 1) {
+        opt_bits &= ~(static_cast<T>(1) << pos);
+    } else {
+        // find index
+        int offset = 0;
+        while ( (offset + sizeof(T)*8) <= static_cast<unsigned>(pos)) {
+            offset += sizeof(T)*8;
+        }
+        int idx = offset / (sizeof(T)*8);
+        bits[idx] &= ~(static_cast<T>(1) << (pos - offset));
+    }
+}
+
+template <class T>
+void
+Bitset<T>::clearRange(int start, int size)
+{
+  if (size == 0) return;
+  assert(start >= 0);
+  assert(size >= 0);
+  assert(start + size <= _size);
+
+  if (num_ints == 1) {
+      // fast path when there is one container int
+      opt_bits &= ~(MAKE_MASK(size) << start);
+  } else {
+    // iterate over all container ints
+      unsigned offset = 0;
+      while ( (offset + sizeof(T)*8) <= static_cast<unsigned>(start)) {
+          offset += sizeof(T)*8;
+      }
+      int cur_start = start - offset; // offset in current int
+      int end = start + size;
+
+      int cur_size =                  // number of bits set in this int
+        end - offset > sizeof(T)*8 ?
+        sizeof(T)*8 - cur_start:
+        end - offset - cur_start;
+
+      while (cur_start + offset < end) {
+          int idx = offset / (sizeof(T)*8);
+          cur_size =
+            end - offset > sizeof(T)*8 ?
+            sizeof(T)*8 - cur_start:
+            end - offset - cur_start;
+
+          assert(cur_size + cur_start <= sizeof(T)*8);
+          bits[idx] &= ~static_cast<T>(MAKE_MASK(cur_size) << cur_start);
+          cur_start = 0;
+          offset += sizeof(T)*8;
+      }
+  }
+}
+
+template <class T>
+void
+Bitset<T>::clearAll()
+{
+  if (num_ints == 1) {
+    opt_bits = static_cast<T>(0);
+  } else {
+    for (int i=0;i<num_ints;i++) {
+      bits[i] = static_cast<T>(0);
+    }
+  }
+}
+
+template <class T>
+void
+Bitset<T>::merge(const Bitset<T> & other)
+{
+  assert (other._size == this->_size);
+  if (this->num_ints == 1) {
+    this->opt_bits |= other.opt_bits;
+  } else {
+    for (int i=0; i<other.num_ints; i++) {
+      this->bits[i] |= other.bits[i];
+    }
+  }
+}
+
+template <class T>
+int
+Bitset<T>::count() const
+{
+    int count = 0;
+    if (this->num_ints == 1) {
+        for (int i = 0; i < this->size(); i++) {
+            if ((this->opt_bits >> i) & 1) count++;
+        }
+    } else {
+        for (int i=0; i < this->num_ints; i++) {
+            for (int j = 0; j < this->size(); j++) {
+                if ((this->bits[i] >> j) & 1) count++;
+            }
+        }
+    }
+    return count;
+}
+
+template <class T>
+void
+Bitset<T>::print(std::ostream& out) const
+{
+  if (num_ints <= 0) {
+    out << "[ UNINITIALIZED ]";
+  } else if (num_ints == 1) {
+    out << "[ ";
+    out << std::hex << opt_bits;
+    out << std::dec << " ]";
+  } else {
+    out << "[ ";
+    for (int i=0;i<num_ints;i++) {
+      out << std::hex << bits[i];
+    }
+    out << std::dec << " ]";
+  }
+}
+
+template <class T>
+inline std::ostream&
+operator<<(std::ostream& out, const Bitset<T>& obj)
+{
+    obj.print(out);
+    out << std::flush;
+    return out;
+}
+
+#endif
diff --git a/src/base/bitset.cc b/src/base/bitset.cc
new file mode 100644
--- /dev/null
+++ b/src/base/bitset.cc
@@ -0,0 +1,92 @@
+/*
+ * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
+ * Copyright (c) 2013 Advanced Micro Devices, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+// Author: Derek Hower (Derek.Hower@amd.com)
+
+#include "base/bitset.hh"
+
+template <>
+int
+Bitset<uint64_t>::count() const
+{
+    if (this->num_ints == 1) {
+        return __builtin_popcountll(this->opt_bits);
+    } else {
+        int count = 0;
+        for (int i=0; i < this->num_ints; i++) {
+            count += __builtin_popcountll(this->bits[i]);
+        }
+        return count;
+    }
+}
+
+template <>
+int
+Bitset<int64_t>::count() const
+{
+    if (this->num_ints == 1) {
+        return __builtin_popcountll(this->opt_bits);
+    } else {
+        int count = 0;
+        for (int i=0; i < this->num_ints; i++) {
+            count += __builtin_popcountll(this->bits[i]);
+        }
+        return count;
+    }
+}
+
+template <>
+int
+Bitset<uint32_t>::count() const
+{
+    if (this->num_ints == 1) {
+        return __builtin_popcountl(this->opt_bits);
+    } else {
+        int count = 0;
+        for (int i=0; i < this->num_ints; i++) {
+            count += __builtin_popcountl(this->bits[i]);
+        }
+        return count;
+    }
+}
+
+template <>
+int
+Bitset<int32_t>::count() const
+{
+    if (this->num_ints == 1) {
+        return __builtin_popcountl(this->opt_bits);
+    } else {
+        int count = 0;
+        for (int i=0; i < this->num_ints; i++) {
+            count += __builtin_popcountl(this->bits[i]);
+        }
+        return count;
+    }
+}