Rewrite BitVector index iterator.
The BitVector::Iterator was not iterating over the bits but
rather over indexes of the set bits. Therefore, we rename it
to IndexIterator and provide a BitVector::Indexes() to get
a container-style interface with begin() and end() for range
based for loops.
Also, simplify InsertPhiNodes where the tmp_blocks isn't
needed since the phi_nodes and input_blocks cannot lose any
blocks in subsequent iterations, so we can do the Union()
directly in those bit vectors and we need to repeat the loop
only if we have new input_blocks, rather than on phi_nodes
change. And move the temporary bit vectors to scoped arena.
Change-Id: I6cb87a2f60724eeef67c6aaa34b36ed5acde6d43
diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index a3e2b15..7dad55e 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -45,10 +45,11 @@
storage_size_(storage_size),
storage_(storage),
number_of_bits_(start_bits) {
- DCHECK_EQ(sizeof(*storage_), 4U); // Assuming 32-bit units.
+ COMPILE_ASSERT(sizeof(*storage_) == kWordBytes, check_word_bytes);
+ COMPILE_ASSERT(sizeof(*storage_) * 8u == kWordBits, check_word_bits);
if (storage_ == nullptr) {
storage_size_ = BitsToWords(start_bits);
- storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * sizeof(*storage_)));
+ storage_ = static_cast<uint32_t*>(allocator_->Alloc(storage_size_ * kWordBytes));
}
}
@@ -61,7 +62,7 @@
*/
bool BitVector::IsBitSet(uint32_t num) const {
// If the index is over the size:
- if (num >= storage_size_ * sizeof(*storage_) * 8) {
+ if (num >= storage_size_ * kWordBits) {
// Whether it is expandable or not, this bit does not exist: thus it is not set.
return false;
}
@@ -71,7 +72,7 @@
// Mark all bits bit as "clear".
void BitVector::ClearAllBits() {
- memset(storage_, 0, storage_size_ * sizeof(*storage_));
+ memset(storage_, 0, storage_size_ * kWordBytes);
}
// Mark the specified bit as "set".
@@ -80,17 +81,17 @@
* not using it badly or change resize mechanism.
*/
void BitVector::SetBit(uint32_t num) {
- if (num >= storage_size_ * sizeof(*storage_) * 8) {
+ if (num >= storage_size_ * kWordBits) {
DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num;
/* Round up to word boundaries for "num+1" bits */
uint32_t new_size = BitsToWords(num + 1);
DCHECK_GT(new_size, storage_size_);
uint32_t *new_storage =
- static_cast<uint32_t*>(allocator_->Alloc(new_size * sizeof(*storage_)));
- memcpy(new_storage, storage_, storage_size_ * sizeof(*storage_));
+ static_cast<uint32_t*>(allocator_->Alloc(new_size * kWordBytes));
+ memcpy(new_storage, storage_, storage_size_ * kWordBytes);
// Zero out the new storage words.
- memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(*storage_));
+ memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * kWordBytes);
// TOTO: collect stats on space wasted because of resize.
storage_ = new_storage;
storage_size_ = new_size;
@@ -103,7 +104,7 @@
// Mark the specified bit as "unset".
void BitVector::ClearBit(uint32_t num) {
// If the index is over the size, we don't have to do anything, it is cleared.
- if (num < storage_size_ * sizeof(*storage_) * 8) {
+ if (num < storage_size_ * kWordBits) {
// Otherwise, go ahead and clear it.
storage_[num >> 5] &= ~check_masks[num & 0x1f];
}
@@ -132,7 +133,7 @@
// - Therefore, min_size goes up to at least that, we are thus comparing at least what we need to, but not less.
// ie. we are comparing all storage cells that could have difference, if both vectors have cells above our_highest_index,
// they are automatically at 0.
- return (memcmp(storage_, src->GetRawStorage(), our_highest_index * sizeof(*storage_)) == 0);
+ return (memcmp(storage_, src->GetRawStorage(), our_highest_index * kWordBytes) == 0);
}
// Intersect with another bit vector.
@@ -180,7 +181,7 @@
SetBit(highest_bit);
// Paranoid: storage size should be big enough to hold this bit now.
- DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * sizeof(*(storage_)) * 8);
+ DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits);
}
for (uint32_t idx = 0; idx < src_size; idx++) {
@@ -215,7 +216,7 @@
SetBit(highest_bit);
// Paranoid: storage size should be big enough to hold this bit now.
- DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * sizeof(*(storage_)) * 8);
+ DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * kWordBits);
}
uint32_t not_in_size = not_in->GetStorageSize();
@@ -268,14 +269,10 @@
// Count the number of bits that are set in range [0, end).
uint32_t BitVector::NumSetBits(uint32_t end) const {
- DCHECK_LE(end, storage_size_ * sizeof(*storage_) * 8);
+ DCHECK_LE(end, storage_size_ * kWordBits);
return NumSetBits(storage_, end);
}
-BitVector::Iterator* BitVector::GetIterator() const {
- 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
@@ -329,7 +326,7 @@
}
// Return cnt + how many storage units still remain * the number of bits per unit.
- int res = cnt + (idx * (sizeof(*storage_) * 8));
+ int res = cnt + (idx * kWordBits);
return res;
}
}
@@ -369,14 +366,14 @@
SetBit(highest_bit);
// Now set until highest bit's storage.
- uint32_t size = 1 + (highest_bit / (sizeof(*storage_) * 8));
- memcpy(storage_, src->GetRawStorage(), sizeof(*storage_) * size);
+ uint32_t size = 1 + (highest_bit / kWordBits);
+ memcpy(storage_, src->GetRawStorage(), kWordBytes * size);
// Set upper bits to 0.
uint32_t left = storage_size_ - size;
if (left > 0) {
- memset(storage_ + size, 0, sizeof(*storage_) * left);
+ memset(storage_ + size, 0, kWordBytes * left);
}
}
diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h
index 2a68396..43e98a7 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -32,59 +32,115 @@
*/
class BitVector {
public:
- class Iterator {
+ class IndexContainer;
+
+ /**
+ * @brief Convenient iterator across the indexes of the BitVector's set bits.
+ *
+ * @details IndexIterator is a Forward iterator (C++11: 24.2.5) from the lowest
+ * to the highest index of the BitVector's set bits. Instances can be retrieved
+ * only through BitVector::Indexes() which returns an IndexContainer wrapper
+ * object with begin() and end() suitable for range-based loops:
+ * for (uint32_t idx : bit_vector.Indexes()) {
+ * // Use idx.
+ * }
+ */
+ class IndexIterator
+ : std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, uint32_t> {
public:
- explicit Iterator(const 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;
+ bool operator==(const IndexIterator& other) const {
+ DCHECK(bit_storage_ == other.bit_storage_);
+ DCHECK_EQ(storage_size_, other.storage_size_);
+ return bit_index_ == other.bit_index_;
}
- 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);
+ bool operator!=(const IndexIterator& other) const {
+ return !(*this == other);
+ }
+
+ int operator*() const{
+ DCHECK_LT(bit_index_, BitSize());
+ return bit_index_;
+ }
+
+ IndexIterator& operator++() {
+ DCHECK_LT(bit_index_, BitSize());
+ bit_index_ = FindIndex(bit_index_ + 1u);
+ return *this;
+ }
+
+ IndexIterator operator++(int) {
+ IndexIterator result(*this);
+ ++*this;
+ return result;
+ }
+
+ // Helper function to check for end without comparing with bit_vector.Indexes().end().
+ bool Done() const {
+ return bit_index_ == BitSize();
}
private:
- const BitVector* const p_bits_;
- const uint32_t* const bit_storage_;
- uint32_t bit_index_; // Current index (size in bits).
- const uint32_t bit_size_; // Size of vector in bits.
+ struct begin_tag { };
+ struct end_tag { };
- friend class BitVector;
+ IndexIterator(const BitVector* bit_vector, begin_tag)
+ : bit_storage_(bit_vector->GetRawStorage()),
+ storage_size_(bit_vector->storage_size_),
+ bit_index_(FindIndex(0u)) { }
+
+ IndexIterator(const BitVector* bit_vector, end_tag)
+ : bit_storage_(bit_vector->GetRawStorage()),
+ storage_size_(bit_vector->storage_size_),
+ bit_index_(BitSize()) { }
+
+ uint32_t BitSize() const {
+ return storage_size_ * kWordBits;
+ }
+
+ uint32_t FindIndex(uint32_t start_index) const {
+ DCHECK_LE(start_index, BitSize());
+ uint32_t word_index = start_index / kWordBits;
+ if (UNLIKELY(word_index == storage_size_)) {
+ return start_index;
+ }
+ uint32_t word = bit_storage_[word_index];
+ // Mask out any bits in the first word we've already considered.
+ word &= static_cast<uint32_t>(-1) << (start_index & 0x1f);
+ while (word == 0u) {
+ ++word_index;
+ if (UNLIKELY(word_index == storage_size_)) {
+ return BitSize();
+ }
+ word = bit_storage_[word_index];
+ }
+ return word_index * 32u + CTZ(word);
+ }
+
+ const uint32_t* const bit_storage_;
+ const uint32_t storage_size_; // Size of vector in words.
+ uint32_t bit_index_; // Current index (size in bits).
+
+ friend class BitVector::IndexContainer;
+ };
+
+ /**
+ * @brief BitVector wrapper class for iteration across indexes of set bits.
+ */
+ class IndexContainer {
+ public:
+ explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { }
+
+ IndexIterator begin() const {
+ return IndexIterator(bit_vector_, IndexIterator::begin_tag());
+ }
+
+ IndexIterator end() const {
+ return IndexIterator(bit_vector_, IndexIterator::end_tag());
+ }
+
+ private:
+ const BitVector* const bit_vector_;
};
BitVector(uint32_t start_bits,
@@ -127,14 +183,16 @@
// Number of bits set in range [0, end).
uint32_t NumSetBits(uint32_t end) const;
- Iterator* GetIterator() const;
+ IndexContainer Indexes() const {
+ return IndexContainer(this);
+ }
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_; }
- size_t GetSizeOf() const { return storage_size_ * sizeof(uint32_t); }
+ size_t GetSizeOf() const { return storage_size_ * kWordBytes; }
/**
* @return the highest bit set, -1 if none are set
@@ -155,6 +213,9 @@
void DumpHelper(std::ostringstream& buffer, const char* prefix) const;
private:
+ static constexpr uint32_t kWordBytes = sizeof(uint32_t);
+ static constexpr uint32_t kWordBits = kWordBytes * 8;
+
Allocator* const allocator_;
const bool expandable_; // expand bitmap if we run out?
uint32_t storage_size_; // current size, in 32-bit words.
diff --git a/runtime/base/bit_vector_test.cc b/runtime/base/bit_vector_test.cc
index 0f866a4..1403f50 100644
--- a/runtime/base/bit_vector_test.cc
+++ b/runtime/base/bit_vector_test.cc
@@ -38,11 +38,8 @@
EXPECT_EQ(0U, bv.GetRawStorageWord(0));
EXPECT_EQ(0U, *bv.GetRawStorage());
- BitVector::Iterator empty_iterator(&bv);
- EXPECT_EQ(-1, empty_iterator.Next());
-
- std::unique_ptr<BitVector::Iterator> empty_iterator_on_heap(bv.GetIterator());
- EXPECT_EQ(-1, empty_iterator_on_heap->Next());
+ EXPECT_TRUE(bv.Indexes().begin().Done());
+ EXPECT_TRUE(bv.Indexes().begin() == bv.Indexes().end());
bv.SetBit(0);
bv.SetBit(kBits - 1);
@@ -57,10 +54,14 @@
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());
+ BitVector::IndexIterator iterator = bv.Indexes().begin();
+ EXPECT_TRUE(iterator != bv.Indexes().end());
+ EXPECT_EQ(0, *iterator);
+ ++iterator;
+ EXPECT_TRUE(iterator != bv.Indexes().end());
+ EXPECT_EQ(static_cast<int>(kBits - 1), *iterator);
+ ++iterator;
+ EXPECT_TRUE(iterator == bv.Indexes().end());
}
TEST(BitVector, NoopAllocator) {