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

1 files changed, 18 insertions, 21 deletions

diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc
index a3e2b15232..7dad55ec46 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -45,10 +45,11 @@ BitVector::BitVector(uint32_t start_bits,
     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 @@ BitVector::~BitVector() {
  */
 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 @@ bool BitVector::IsBitSet(uint32_t num) const {
 
 // 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 @@ void BitVector::ClearAllBits() {
  * 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 @@ void BitVector::SetBit(uint32_t num) {
 // 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 @@ bool BitVector::SameBitsSet(const BitVector *src) {
   //   - 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 @@ bool BitVector::Union(const BitVector* src) {
     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 @@ bool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_i
     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 @@ uint32_t BitVector::NumSetBits() const {
 
 // 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 @@ int BitVector::GetHighestBitSet() const {
       }
 
       // 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 @@ void BitVector::Copy(const BitVector *src) {
   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);
   }
 }