Refactor ArenaBitVector to create more general BitVector
Change-Id: Ib26f2884de9ce7d620048bdf5ed6dec639622e41
diff --git a/compiler/dex/arena_bit_vector.cc b/compiler/dex/arena_bit_vector.cc
index b921f61..b567ae8 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() {}
+
+ virtual void* Alloc(size_t size) {
+ return arena_->Alloc(size, ArenaAllocator::kAllocGrowableBitMap);
+ }
+
+ virtual void Free(void*) {} // Nop.
+
+ static void* operator new(size_t size, ArenaAllocator* arena) {
+ return arena->Alloc(sizeof(ArenaBitVectorAllocator), ArenaAllocator::kAllocGrowableBitMap);
+ }
+ static void operator delete(void* p) {} // Nop.
+
+ private:
+ ArenaAllocator* arena_;
+ DISALLOW_COPY_AND_ASSIGN(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;
- }
-
- 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];
-}
-
-// 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);
- }
-}
-
-/*
- * 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;
-}
-
-/*
- * 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;
- }
-}
+ : 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 53e6eb6..7d2f3ff 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 eb0d412..b6c8922 100644
--- a/compiler/dex/ssa_transformation.cc
+++ b/compiler/dex/ssa_transformation.cc
@@ -183,7 +183,7 @@
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 @@
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) {