Refactor ArenaBitVector to create more general BitVector

Change-Id: Ib26f2884de9ce7d620048bdf5ed6dec639622e41

11 files changed, 532 insertions, 204 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 4c658a2bb7..22abba170b 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -23,6 +23,7 @@ TEST_COMMON_SRC_FILES := \
 	compiler/jni/jni_compiler_test.cc \
 	compiler/oat_test.cc \
 	compiler/output_stream_test.cc \
+	compiler/utils/bit_vector_test.cc \
 	compiler/utils/dedupe_set_test.cc \
 	compiler/utils/arm/managed_register_arm_test.cc \
 	compiler/utils/x86/managed_register_x86_test.cc \
diff --git a/compiler/Android.mk b/compiler/Android.mk
index fc2f02b59e..0d3acbdb71 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -79,6 +79,8 @@ LIBART_COMPILER_SRC_FILES := \
 	utils/arm/assembler_arm.cc \
 	utils/arm/managed_register_arm.cc \
 	utils/assembler.cc \
+	utils/allocator.cc \
+	utils/bit_vector.cc \
 	utils/mips/assembler_mips.cc \
 	utils/mips/managed_register_mips.cc \
 	utils/x86/assembler_x86.cc \
diff --git a/compiler/dex/arena_bit_vector.cc b/compiler/dex/arena_bit_vector.cc
index b921f615b6..b567ae8d8a 100644
--- a/compiler/dex/arena_bit_vector.cc
+++ b/compiler/dex/arena_bit_vector.cc
@@ -19,119 +19,29 @@
 
 namespace art {
 
-// TODO: profile to make sure this is still a win relative to just using shifted masks.
-static uint32_t check_masks[32] = {
-  0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010,
-  0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200,
-  0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
-  0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000,
-  0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000,
-  0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
-  0x40000000, 0x80000000 };
+class ArenaBitVectorAllocator : public Allocator {
+ public:
+  explicit ArenaBitVectorAllocator(ArenaAllocator* arena) : arena_(arena) {}
+  ~ArenaBitVectorAllocator() {}
 
-ArenaBitVector::ArenaBitVector(ArenaAllocator* arena, unsigned int start_bits,
-                               bool expandable, OatBitMapKind kind)
-  :  arena_(arena),
-     expandable_(expandable),
-     kind_(kind),
-     storage_size_((start_bits + 31) >> 5),
-     storage_(static_cast<uint32_t*>(arena_->Alloc(storage_size_ * sizeof(uint32_t),
-                                                   ArenaAllocator::kAllocGrowableBitMap))) {
-  DCHECK_EQ(sizeof(storage_[0]), 4U);    // Assuming 32-bit units.
-}
-
-/*
- * Determine whether or not the specified bit is set.
- */
-bool ArenaBitVector::IsBitSet(unsigned int num) {
-  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
-
-  unsigned int val = storage_[num >> 5] & check_masks[num & 0x1f];
-  return (val != 0);
-}
-
-// Mark all bits bit as "clear".
-void ArenaBitVector::ClearAllBits() {
-  memset(storage_, 0, storage_size_ * sizeof(uint32_t));
-}
-
-// Mark the specified bit as "set".
-/*
- * TUNING: this could have pathologically bad growth/expand behavior.  Make sure we're
- * not using it badly or change resize mechanism.
- */
-void ArenaBitVector::SetBit(unsigned int num) {
-  if (num >= storage_size_ * sizeof(uint32_t) * 8) {
-    DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num;
-
-    /* Round up to word boundaries for "num+1" bits */
-    unsigned int new_size = (num + 1 + 31) >> 5;
-    DCHECK_GT(new_size, storage_size_);
-    uint32_t *new_storage =
-        static_cast<uint32_t*>(arena_->Alloc(new_size * sizeof(uint32_t),
-                                             ArenaAllocator::kAllocGrowableBitMap));
-    memcpy(new_storage, storage_, storage_size_ * sizeof(uint32_t));
-    // Zero out the new storage words.
-    memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(uint32_t));
-    // TOTO: collect stats on space wasted because of resize.
-    storage_ = new_storage;
-    storage_size_ = new_size;
+  virtual void* Alloc(size_t size) {
+    return arena_->Alloc(size, ArenaAllocator::kAllocGrowableBitMap);
   }
 
-  storage_[num >> 5] |= check_masks[num & 0x1f];
-}
-
-// Mark the specified bit as "unset".
-void ArenaBitVector::ClearBit(unsigned int num) {
-  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
-  storage_[num >> 5] &= ~check_masks[num & 0x1f];
-}
+  virtual void Free(void*) {}  // Nop.
 
-// Intersect with another bit vector.  Sizes and expandability must be the same.
-void ArenaBitVector::Intersect(const ArenaBitVector* src) {
-  DCHECK_EQ(storage_size_, src->GetStorageSize());
-  DCHECK_EQ(expandable_, src->IsExpandable());
-  for (unsigned int idx = 0; idx < storage_size_; idx++) {
-    storage_[idx] &= src->GetRawStorageWord(idx);
+  static void* operator new(size_t size, ArenaAllocator* arena) {
+    return arena->Alloc(sizeof(ArenaBitVectorAllocator), ArenaAllocator::kAllocGrowableBitMap);
   }
-}
+  static void operator delete(void* p) {}  // Nop.
 
-/*
- * Union with another bit vector.  Sizes and expandability must be the same.
- */
-void ArenaBitVector::Union(const ArenaBitVector* src) {
-  DCHECK_EQ(storage_size_, src->GetStorageSize());
-  DCHECK_EQ(expandable_, src->IsExpandable());
-  for (unsigned int idx = 0; idx < storage_size_; idx++) {
-    storage_[idx] |= src->GetRawStorageWord(idx);
-  }
-}
-
-// Count the number of bits that are set.
-int ArenaBitVector::NumSetBits() {
-  unsigned int count = 0;
-
-  for (unsigned int word = 0; word < storage_size_; word++) {
-    count += __builtin_popcount(storage_[word]);
-  }
-  return count;
-}
+ private:
+  ArenaAllocator* arena_;
+  DISALLOW_COPY_AND_ASSIGN(ArenaBitVectorAllocator);
+};
 
-/*
- * Mark specified number of bits as "set". Cannot set all bits like ClearAll
- * since there might be unused bits - setting those to one will confuse the
- * iterator.
- */
-void ArenaBitVector::SetInitialBits(unsigned int num_bits) {
-  DCHECK_LE(((num_bits + 31) >> 5), storage_size_);
-  unsigned int idx;
-  for (idx = 0; idx < (num_bits >> 5); idx++) {
-    storage_[idx] = -1;
-  }
-  unsigned int rem_num_bits = num_bits & 0x1f;
-  if (rem_num_bits) {
-    storage_[idx] = (1 << rem_num_bits) - 1;
-  }
-}
+ArenaBitVector::ArenaBitVector(ArenaAllocator* arena, unsigned int start_bits,
+                               bool expandable, OatBitMapKind kind)
+  :  BitVector(start_bits, expandable, new (arena) ArenaBitVectorAllocator(arena)), kind_(kind) {}
 
 }  // namespace art
diff --git a/compiler/dex/arena_bit_vector.h b/compiler/dex/arena_bit_vector.h
index 53e6eb6512..7d2f3ffa5e 100644
--- a/compiler/dex/arena_bit_vector.h
+++ b/compiler/dex/arena_bit_vector.h
@@ -17,109 +17,28 @@
 #ifndef ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_
 #define ART_COMPILER_DEX_ARENA_BIT_VECTOR_H_
 
-#include <stdint.h>
-#include <stddef.h>
-#include "compiler_enums.h"
 #include "arena_allocator.h"
+#include "compiler_enums.h"
+#include "utils/bit_vector.h"
 
 namespace art {
 
 /*
- * Expanding bitmap, used for tracking resources.  Bits are numbered starting
- * from zero.  All operations on a BitVector are unsynchronized.
+ * A BitVector implementation that uses Arena allocation.
  */
-class ArenaBitVector {
+class ArenaBitVector : public BitVector {
   public:
-    class Iterator {
-      public:
-        explicit Iterator(ArenaBitVector* bit_vector)
-          : p_bits_(bit_vector),
-            bit_storage_(bit_vector->GetRawStorage()),
-            bit_index_(0),
-            bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {}
-
-        // Return the position of the next set bit.  -1 means end-of-element reached.
-        int32_t Next() {
-          // Did anything obviously change since we started?
-          DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8);
-          DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage());
-
-          if (UNLIKELY(bit_index_ >= bit_size_)) return -1;
-
-          uint32_t word_index = bit_index_ / 32;
-          uint32_t word = bit_storage_[word_index];
-          // Mask out any bits in the first word we've already considered.
-          word >>= bit_index_ & 0x1f;
-          if (word == 0) {
-            bit_index_ &= ~0x1f;
-            do {
-              word_index++;
-              if (UNLIKELY((word_index * 32) >= bit_size_)) {
-                bit_index_ = bit_size_;
-                return -1;
-              }
-              word = bit_storage_[word_index];
-              bit_index_ += 32;
-            } while (word == 0);
-          }
-          bit_index_ += CTZ(word) + 1;
-          return bit_index_ - 1;
-        }
-
-        static void* operator new(size_t size, ArenaAllocator* arena) {
-          return arena->Alloc(sizeof(ArenaBitVector::Iterator),
-                              ArenaAllocator::kAllocGrowableBitMap);
-        };
-        static void operator delete(void* p) {}  // Nop.
-
-      private:
-        ArenaBitVector* const p_bits_;
-        uint32_t* const bit_storage_;
-        uint32_t bit_index_;              // Current index (size in bits).
-        const uint32_t bit_size_;       // Size of vector in bits.
-    };
-
     ArenaBitVector(ArenaAllocator* arena, uint32_t start_bits, bool expandable,
                    OatBitMapKind kind = kBitMapMisc);
     ~ArenaBitVector() {}
 
-    static void* operator new(size_t size, ArenaAllocator* arena) {
-      return arena->Alloc(sizeof(ArenaBitVector), ArenaAllocator::kAllocGrowableBitMap);
-    }
-    static void operator delete(void* p) {}  // Nop.
-
-    void SetBit(uint32_t num);
-    void ClearBit(uint32_t num);
-    void MarkAllBits(bool set);
-    void DebugBitVector(char* msg, int length);
-    bool IsBitSet(uint32_t num);
-    void ClearAllBits();
-    void SetInitialBits(uint32_t num_bits);
-    void Copy(ArenaBitVector* src) {
-      memcpy(storage_, src->GetRawStorage(), sizeof(uint32_t) * storage_size_);
-    }
-    void Intersect(const ArenaBitVector* src2);
-    void Union(const ArenaBitVector* src);
-    // Are we equal to another bit vector?  Note: expandability attributes must also match.
-    bool Equal(const ArenaBitVector* src) {
-      return (storage_size_ == src->GetStorageSize()) &&
-        (expandable_ == src->IsExpandable()) &&
-        (memcmp(storage_, src->GetRawStorage(), storage_size_ * 4) == 0);
-    }
-    int32_t NumSetBits();
-
-    uint32_t GetStorageSize() const { return storage_size_; }
-    bool IsExpandable() const { return expandable_; }
-    uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; }
-    uint32_t* GetRawStorage() { return storage_; }
-    const uint32_t* GetRawStorage() const { return storage_; }
+  static void* operator new(size_t size, ArenaAllocator* arena) {
+     return arena->Alloc(sizeof(ArenaBitVector), ArenaAllocator::kAllocGrowableBitMap);
+  }
+  static void operator delete(void* p) {}  // Nop.
 
   private:
-    ArenaAllocator* const arena_;
-    const bool expandable_;         // expand bitmap if we run out?
-    const OatBitMapKind kind_;      // for memory use tuning.
-    uint32_t   storage_size_;       // current size, in 32-bit words.
-    uint32_t*  storage_;
+    const OatBitMapKind kind_;      // for memory use tuning. TODO: currently unused.
 };
 
 
diff --git a/compiler/dex/ssa_transformation.cc b/compiler/dex/ssa_transformation.cc
index eb0d412bae..b6c892212c 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -183,7 +183,7 @@ void MIRGraph::ComputeDomPostOrderTraversal(BasicBlock* bb) {
   ClearAllVisitedFlags();
   std::vector<std::pair<BasicBlock*, ArenaBitVector::Iterator*> > work_stack;
   bb->visited = true;
-  work_stack.push_back(std::make_pair(bb, new (arena_) ArenaBitVector::Iterator(bb->i_dominated)));
+  work_stack.push_back(std::make_pair(bb, bb->i_dominated->GetIterator()));
   while (!work_stack.empty()) {
     const std::pair<BasicBlock*, ArenaBitVector::Iterator*>& curr = work_stack.back();
     BasicBlock* curr_bb = curr.first;
@@ -196,7 +196,7 @@ void MIRGraph::ComputeDomPostOrderTraversal(BasicBlock* bb) {
       BasicBlock* new_bb = GetBasicBlock(bb_idx);
       new_bb->visited = true;
       work_stack.push_back(
-          std::make_pair(new_bb, new (arena_) ArenaBitVector::Iterator(new_bb->i_dominated)));
+          std::make_pair(new_bb, new_bb->i_dominated->GetIterator()));
     } else {
       // no successor/next
       if (curr_bb->id != NullBasicBlockId) {
diff --git a/compiler/utils/allocator.cc b/compiler/utils/allocator.cc
new file mode 100644
index 0000000000..4f7753d476
--- /dev/null
+++ b/compiler/utils/allocator.cc
@@ -0,0 +1,74 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "allocator.h"
+
+#include <inttypes.h>
+#include <stdlib.h>
+
+#include "base/logging.h"
+
+namespace art {
+
+class MallocAllocator : public Allocator {
+ public:
+  explicit MallocAllocator() {}
+  ~MallocAllocator() {}
+
+  virtual void* Alloc(size_t size) {
+    return calloc(sizeof(uint8_t), size);
+  }
+
+  virtual void Free(void* p) {
+    free(p);
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(MallocAllocator);
+};
+
+MallocAllocator g_malloc_allocator;
+
+class NoopAllocator : public Allocator {
+ public:
+  explicit NoopAllocator() {}
+  ~NoopAllocator() {}
+
+  virtual void* Alloc(size_t size) {
+    LOG(FATAL) << "NoopAllocator::Alloc should not be called";
+    return NULL;
+  }
+
+  virtual void Free(void* p) {
+    // Noop.
+  }
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(NoopAllocator);
+};
+
+NoopAllocator g_noop_allocator;
+
+Allocator* Allocator::GetMallocAllocator() {
+  return &g_malloc_allocator;
+}
+
+Allocator* Allocator::GetNoopAllocator() {
+  return &g_noop_allocator;
+}
+
+
+}  // namespace art
diff --git a/compiler/utils/allocator.h b/compiler/utils/allocator.h
new file mode 100644
index 0000000000..3482a7928e
--- /dev/null
+++ b/compiler/utils/allocator.h
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_UTILS_ALLOCATOR_H_
+#define ART_COMPILER_UTILS_ALLOCATOR_H_
+
+#include "base/macros.h"
+
+namespace art {
+
+class Allocator {
+ public:
+  static Allocator* GetMallocAllocator();
+  static Allocator* GetNoopAllocator();
+
+  Allocator() {}
+  virtual ~Allocator() {}
+
+  virtual void* Alloc(size_t) = 0;
+  virtual void Free(void*) = 0;
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(Allocator);
+};
+
+}  // namespace art
+
+#endif  // ART_COMPILER_UTILS_ALLOCATOR_H_
diff --git a/compiler/utils/bit_vector.cc b/compiler/utils/bit_vector.cc
new file mode 100644
index 0000000000..81a639a050
--- /dev/null
+++ b/compiler/utils/bit_vector.cc
@@ -0,0 +1,155 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "bit_vector.h"
+
+namespace art {
+
+// TODO: profile to make sure this is still a win relative to just using shifted masks.
+static uint32_t check_masks[32] = {
+  0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010,
+  0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200,
+  0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
+  0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000,
+  0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000,
+  0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
+  0x40000000, 0x80000000 };
+
+static inline uint32_t BitsToWords(unsigned int bits) {
+  return (bits + 31) >> 5;
+}
+
+// TODO: replace excessive argument defaulting when we are at gcc 4.7
+// or later on host with delegating constructor support. Specifically,
+// starts_bits and storage_size/storage are mutually exclusive.
+BitVector::BitVector(unsigned int start_bits,
+                     bool expandable,
+                     Allocator* allocator,
+                     uint32_t storage_size,
+                     uint32_t* storage)
+  : allocator_(allocator),
+    expandable_(expandable),
+    storage_size_(storage_size),
+    storage_(storage) {
+  DCHECK_EQ(sizeof(storage_[0]), 4U);  // Assuming 32-bit units.
+  if (storage_ == NULL) {
+    storage_size_ = BitsToWords(start_bits);
+    storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * sizeof(uint32_t)));
+  }
+}
+
+BitVector::~BitVector() {
+  allocator_->Free(storage_);
+}
+
+/*
+ * Determine whether or not the specified bit is set.
+ */
+bool BitVector::IsBitSet(unsigned int num) {
+  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
+
+  unsigned int val = storage_[num >> 5] & check_masks[num & 0x1f];
+  return (val != 0);
+}
+
+// Mark all bits bit as "clear".
+void BitVector::ClearAllBits() {
+  memset(storage_, 0, storage_size_ * sizeof(uint32_t));
+}
+
+// Mark the specified bit as "set".
+/*
+ * TUNING: this could have pathologically bad growth/expand behavior.  Make sure we're
+ * not using it badly or change resize mechanism.
+ */
+void BitVector::SetBit(unsigned int num) {
+  if (num >= storage_size_ * sizeof(uint32_t) * 8) {
+    DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num;
+
+    /* Round up to word boundaries for "num+1" bits */
+    unsigned int new_size = BitsToWords(num + 1);
+    DCHECK_GT(new_size, storage_size_);
+    uint32_t *new_storage =
+        static_cast<uint32_t*>(allocator_->Alloc(new_size * sizeof(uint32_t)));
+    memcpy(new_storage, storage_, storage_size_ * sizeof(uint32_t));
+    // Zero out the new storage words.
+    memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(uint32_t));
+    // TOTO: collect stats on space wasted because of resize.
+    storage_ = new_storage;
+    storage_size_ = new_size;
+  }
+
+  storage_[num >> 5] |= check_masks[num & 0x1f];
+}
+
+// Mark the specified bit as "unset".
+void BitVector::ClearBit(unsigned int num) {
+  DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
+  storage_[num >> 5] &= ~check_masks[num & 0x1f];
+}
+
+// Intersect with another bit vector.  Sizes and expandability must be the same.
+void BitVector::Intersect(const BitVector* src) {
+  DCHECK_EQ(storage_size_, src->GetStorageSize());
+  DCHECK_EQ(expandable_, src->IsExpandable());
+  for (unsigned int idx = 0; idx < storage_size_; idx++) {
+    storage_[idx] &= src->GetRawStorageWord(idx);
+  }
+}
+
+/*
+ * Union with another bit vector.  Sizes and expandability must be the same.
+ */
+void BitVector::Union(const BitVector* src) {
+  DCHECK_EQ(storage_size_, src->GetStorageSize());
+  DCHECK_EQ(expandable_, src->IsExpandable());
+  for (unsigned int idx = 0; idx < storage_size_; idx++) {
+    storage_[idx] |= src->GetRawStorageWord(idx);
+  }
+}
+
+// Count the number of bits that are set.
+int BitVector::NumSetBits() {
+  unsigned int count = 0;
+
+  for (unsigned int word = 0; word < storage_size_; word++) {
+    count += __builtin_popcount(storage_[word]);
+  }
+  return count;
+}
+
+BitVector::Iterator* BitVector::GetIterator() {
+  return new (allocator_) Iterator(this);
+}
+
+/*
+ * Mark specified number of bits as "set". Cannot set all bits like ClearAll
+ * since there might be unused bits - setting those to one will confuse the
+ * iterator.
+ */
+void BitVector::SetInitialBits(unsigned int num_bits) {
+  DCHECK_LE(BitsToWords(num_bits), storage_size_);
+  unsigned int idx;
+  for (idx = 0; idx < (num_bits >> 5); idx++) {
+    storage_[idx] = -1;
+  }
+  unsigned int rem_num_bits = num_bits & 0x1f;
+  if (rem_num_bits) {
+    storage_[idx] = (1 << rem_num_bits) - 1;
+  }
+}
+
+}  // namespace art
diff --git a/compiler/utils/bit_vector.h b/compiler/utils/bit_vector.h
new file mode 100644
index 0000000000..bf0f7c32e1
--- /dev/null
+++ b/compiler/utils/bit_vector.h
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_COMPILER_UTILS_BIT_VECTOR_H_
+#define ART_COMPILER_UTILS_BIT_VECTOR_H_
+
+#include <stdint.h>
+#include <stddef.h>
+
+#include "allocator.h"
+#include "base/logging.h"
+#include "utils.h"
+
+namespace art {
+
+/*
+ * Expanding bitmap, used for tracking resources.  Bits are numbered starting
+ * from zero.  All operations on a BitVector are unsynchronized.
+ */
+class BitVector {
+  public:
+    class Iterator {
+      public:
+        explicit Iterator(BitVector* bit_vector)
+          : p_bits_(bit_vector),
+            bit_storage_(bit_vector->GetRawStorage()),
+            bit_index_(0),
+            bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {}
+
+        // Return the position of the next set bit.  -1 means end-of-element reached.
+        int32_t Next() {
+          // Did anything obviously change since we started?
+          DCHECK_EQ(bit_size_, p_bits_->GetStorageSize() * sizeof(uint32_t) * 8);
+          DCHECK_EQ(bit_storage_, p_bits_->GetRawStorage());
+
+          if (UNLIKELY(bit_index_ >= bit_size_)) return -1;
+
+          uint32_t word_index = bit_index_ / 32;
+          uint32_t word = bit_storage_[word_index];
+          // Mask out any bits in the first word we've already considered.
+          word >>= bit_index_ & 0x1f;
+          if (word == 0) {
+            bit_index_ &= ~0x1f;
+            do {
+              word_index++;
+              if (UNLIKELY((word_index * 32) >= bit_size_)) {
+                bit_index_ = bit_size_;
+                return -1;
+              }
+              word = bit_storage_[word_index];
+              bit_index_ += 32;
+            } while (word == 0);
+          }
+          bit_index_ += CTZ(word) + 1;
+          return bit_index_ - 1;
+        }
+
+        static void* operator new(size_t size, Allocator* allocator) {
+          return allocator->Alloc(sizeof(BitVector::Iterator));
+        };
+        static void operator delete(void* p) {
+          Iterator* it = reinterpret_cast<Iterator*>(p);
+          it->p_bits_->allocator_->Free(p);
+        }
+
+      private:
+        BitVector* const p_bits_;
+        uint32_t* const bit_storage_;
+        uint32_t bit_index_;           // Current index (size in bits).
+        const uint32_t bit_size_;      // Size of vector in bits.
+
+        friend class BitVector;
+    };
+
+    BitVector(uint32_t start_bits,
+              bool expandable,
+              Allocator* allocator,
+              uint32_t storage_size = 0,
+              uint32_t* storage = NULL);
+
+    virtual ~BitVector();
+
+    void SetBit(uint32_t num);
+    void ClearBit(uint32_t num);
+    void MarkAllBits(bool set);
+    void DebugBitVector(char* msg, int length);
+    bool IsBitSet(uint32_t num);
+    void ClearAllBits();
+    void SetInitialBits(uint32_t num_bits);
+    void Copy(BitVector* src) {
+      memcpy(storage_, src->GetRawStorage(), sizeof(uint32_t) * storage_size_);
+    }
+    void Intersect(const BitVector* src2);
+    void Union(const BitVector* src);
+    // Are we equal to another bit vector?  Note: expandability attributes must also match.
+    bool Equal(const BitVector* src) {
+      return (storage_size_ == src->GetStorageSize()) &&
+        (expandable_ == src->IsExpandable()) &&
+        (memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0);
+    }
+    int32_t NumSetBits();
+
+    Iterator* GetIterator();
+
+    uint32_t GetStorageSize() const { return storage_size_; }
+    bool IsExpandable() const { return expandable_; }
+    uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; }
+    uint32_t* GetRawStorage() { return storage_; }
+    const uint32_t* GetRawStorage() const { return storage_; }
+
+  private:
+    Allocator* const allocator_;
+    const bool expandable_;         // expand bitmap if we run out?
+    uint32_t   storage_size_;       // current size, in 32-bit words.
+    uint32_t*  storage_;
+};
+
+
+}  // namespace art
+
+#endif  // ART_COMPILER_UTILS_BIT_VECTOR_H_
diff --git a/compiler/utils/bit_vector_test.cc b/compiler/utils/bit_vector_test.cc
new file mode 100644
index 0000000000..5c18ec53d3
--- /dev/null
+++ b/compiler/utils/bit_vector_test.cc
@@ -0,0 +1,96 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "common_test.h"
+#include "bit_vector.h"
+#include "UniquePtr.h"
+
+namespace art {
+
+TEST(BitVector, Test) {
+  const size_t kBits = 32;
+
+  BitVector bv(kBits, false, Allocator::GetMallocAllocator());
+  EXPECT_EQ(1U, bv.GetStorageSize());
+  EXPECT_FALSE(bv.IsExpandable());
+
+  EXPECT_EQ(0, bv.NumSetBits());
+  for (size_t i = 0; i < kBits; i++) {
+    EXPECT_FALSE(bv.IsBitSet(i));
+  }
+  EXPECT_EQ(0U, bv.GetRawStorageWord(0));
+  EXPECT_EQ(0U, *bv.GetRawStorage());
+
+  BitVector::Iterator empty_iterator(&bv);
+  EXPECT_EQ(-1, empty_iterator.Next());
+
+  UniquePtr<BitVector::Iterator> empty_iterator_on_heap(bv.GetIterator());
+  EXPECT_EQ(-1, empty_iterator_on_heap->Next());
+
+  bv.SetBit(0);
+  bv.SetBit(kBits - 1);
+  EXPECT_EQ(2, bv.NumSetBits());
+  EXPECT_TRUE(bv.IsBitSet(0));
+  for (size_t i = 1; i < kBits - 1; i++) {
+    EXPECT_FALSE(bv.IsBitSet(i));
+  }
+  EXPECT_TRUE(bv.IsBitSet(kBits - 1));
+  EXPECT_EQ(0x80000001U, bv.GetRawStorageWord(0));
+  EXPECT_EQ(0x80000001U, *bv.GetRawStorage());
+
+  BitVector::Iterator iterator(&bv);
+  EXPECT_EQ(0, iterator.Next());
+  EXPECT_EQ(static_cast<int>(kBits - 1), iterator.Next());
+  EXPECT_EQ(-1, iterator.Next());
+}
+
+TEST(BitVector, NoopAllocator) {
+  const uint32_t kWords = 2;
+
+  uint32_t bits[kWords];
+  memset(bits, 0, sizeof(bits));
+
+  BitVector bv(0U, false, Allocator::GetNoopAllocator(), kWords, bits);
+  EXPECT_EQ(kWords, bv.GetStorageSize());
+  EXPECT_EQ(bits, bv.GetRawStorage());
+  EXPECT_EQ(0, bv.NumSetBits());
+
+  bv.SetBit(8);
+  EXPECT_EQ(1, bv.NumSetBits());
+  EXPECT_EQ(0x00000100U, bv.GetRawStorageWord(0));
+  EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1));
+  EXPECT_EQ(1, bv.NumSetBits());
+
+  bv.SetBit(16);
+  EXPECT_EQ(2, bv.NumSetBits());
+  EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
+  EXPECT_EQ(0x00000000U, bv.GetRawStorageWord(1));
+  EXPECT_EQ(2, bv.NumSetBits());
+
+  bv.SetBit(32);
+  EXPECT_EQ(3, bv.NumSetBits());
+  EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
+  EXPECT_EQ(0x00000001U, bv.GetRawStorageWord(1));
+  EXPECT_EQ(3, bv.NumSetBits());
+
+  bv.SetBit(48);
+  EXPECT_EQ(4, bv.NumSetBits());
+  EXPECT_EQ(0x00010100U, bv.GetRawStorageWord(0));
+  EXPECT_EQ(0x00010001U, bv.GetRawStorageWord(1));
+  EXPECT_EQ(4, bv.NumSetBits());
+}
+
+}  // namespace art
diff --git a/compiler/utils/dedupe_set_test.cc b/compiler/utils/dedupe_set_test.cc
index 03d8b961fa..2c6787b8a6 100644
--- a/compiler/utils/dedupe_set_test.cc
+++ b/compiler/utils/dedupe_set_test.cc
@@ -19,10 +19,6 @@
 
 namespace art {
 
-class DedupeSetTest : public testing::Test {
- public:
-};
-
 class DedupeHashFunc {
  public:
   size_t operator()(const std::vector<uint8_t>& array) const {
@@ -35,7 +31,7 @@ class DedupeHashFunc {
     return hash;
   }
 };
-TEST_F(DedupeSetTest, Test) {
+TEST(DedupeSetTest, Test) {
   Thread* self = Thread::Current();
   typedef std::vector<uint8_t> ByteArray;
   DedupeSet<ByteArray, size_t, DedupeHashFunc> deduplicator("test");