Speed up `HGraph::BuildDominatorTree()`.

Add some functions from `BitVector` to `BitVectorView<>`
and use this to speed up `HGraph::BuildDominatorTree()`.

Also clean up code sinking. This was a missed opportunity in
    https://android-review.googlesource.com/3500455 .

Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 331194861
Change-Id: Iec03db8b44af38c549447ccfa0bf8dab731b550d

7 files changed, 183 insertions, 41 deletions

diff --git a/compiler/optimizing/code_sinking.cc b/compiler/optimizing/code_sinking.cc
index b1d14132c4..9ba5416697 100644
--- a/compiler/optimizing/code_sinking.cc
+++ b/compiler/optimizing/code_sinking.cc
@@ -409,8 +409,8 @@ void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) {
   HBasicBlock* common_dominator = finder.Get();
 
   // Step (2): iterate over the worklist to find sinking candidates.
-  ArenaBitVector instructions_that_can_move(
-      &allocator, number_of_instructions, /* expandable= */ false);
+  BitVectorView<size_t> instructions_that_can_move =
+      ArenaBitVector::CreateFixedSize(&allocator, number_of_instructions);
   ScopedArenaVector<ScopedArenaVector<HInstruction*>> instructions_to_move(
       graph_->GetBlocks().size(),
       ScopedArenaVector<HInstruction*>(allocator.Adapter(kArenaAllocMisc)),
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 9b5cc50e93..752e8b10d1 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -61,14 +61,14 @@ inline int32_t HGraph::AllocateInstructionId() {
   return current_instruction_id_++;
 }
 
-void HGraph::FindBackEdges(ArenaBitVector* visited) {
+void HGraph::FindBackEdges(/*out*/ BitVectorView<size_t> visited) {
   // "visited" must be empty on entry, it's an output argument for all visited (i.e. live) blocks.
-  DCHECK_EQ(visited->GetHighestBitSet(), -1);
+  DCHECK(!visited.IsAnyBitSet());
 
   // Allocate memory from local ScopedArenaAllocator.
   ScopedArenaAllocator allocator(GetArenaStack());
   // Nodes that we're currently visiting, indexed by block id.
-  BitVectorView visiting =
+  BitVectorView<size_t> visiting =
       ArenaBitVector::CreateFixedSize(&allocator, blocks_.size(), kArenaAllocGraphBuilder);
   // Number of successors visited from a given node, indexed by block id.
   ScopedArenaVector<size_t> successors_visited(blocks_.size(),
@@ -78,7 +78,7 @@ void HGraph::FindBackEdges(ArenaBitVector* visited) {
   ScopedArenaVector<HBasicBlock*> worklist(allocator.Adapter(kArenaAllocGraphBuilder));
   constexpr size_t kDefaultWorklistSize = 8;
   worklist.reserve(kDefaultWorklistSize);
-  visited->SetBit(entry_block_->GetBlockId());
+  visited.SetBit(entry_block_->GetBlockId());
   visiting.SetBit(entry_block_->GetBlockId());
   worklist.push_back(entry_block_);
 
@@ -94,8 +94,8 @@ void HGraph::FindBackEdges(ArenaBitVector* visited) {
       if (visiting.IsBitSet(successor_id)) {
         DCHECK(ContainsElement(worklist, successor));
         successor->AddBackEdge(current);
-      } else if (!visited->IsBitSet(successor_id)) {
-        visited->SetBit(successor_id);
+      } else if (!visited.IsBitSet(successor_id)) {
+        visited.SetBit(successor_id);
         visiting.SetBit(successor_id);
         worklist.push_back(successor);
       }
@@ -150,7 +150,8 @@ static void RemoveAsUser(HInstruction* instruction) {
   RemoveEnvironmentUses(instruction);
 }
 
-void HGraph::RemoveDeadBlocksInstructionsAsUsersAndDisconnect(const ArenaBitVector& visited) const {
+void HGraph::RemoveDeadBlocksInstructionsAsUsersAndDisconnect(
+    BitVectorView<const size_t> visited) const {
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
       HBasicBlock* block = blocks_[i];
@@ -165,7 +166,7 @@ void HGraph::RemoveDeadBlocksInstructionsAsUsersAndDisconnect(const ArenaBitVect
       }
 
       // Remove non-catch phi uses, and disconnect the block.
-      block->DisconnectFromSuccessors(&visited);
+      block->DisconnectFromSuccessors(visited);
     }
   }
 }
@@ -188,7 +189,7 @@ static void RemoveCatchPhiUsesOfDeadInstruction(HInstruction* insn) {
   }
 }
 
-void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) {
+void HGraph::RemoveDeadBlocks(BitVectorView<const size_t> visited) {
   DCHECK(reverse_post_order_.empty()) << "We shouldn't have dominance information.";
   for (size_t i = 0; i < blocks_.size(); ++i) {
     if (!visited.IsBitSet(i)) {
@@ -215,10 +216,11 @@ GraphAnalysisResult HGraph::BuildDominatorTree() {
   // Allocate memory from local ScopedArenaAllocator.
   ScopedArenaAllocator allocator(GetArenaStack());
 
-  ArenaBitVector visited(&allocator, blocks_.size(), false, kArenaAllocGraphBuilder);
+  BitVectorView<size_t> visited =
+      ArenaBitVector::CreateFixedSize(&allocator, blocks_.size(), kArenaAllocGraphBuilder);
 
   // (1) Find the back edges in the graph doing a DFS traversal.
-  FindBackEdges(&visited);
+  FindBackEdges(visited);
 
   // (2) Remove instructions and phis from blocks not visited during
   //     the initial DFS as users from other instructions, so that
@@ -2505,13 +2507,14 @@ void HBasicBlock::DisconnectAndDelete() {
   graph_->DeleteDeadEmptyBlock(this);
 }
 
-void HBasicBlock::DisconnectFromSuccessors(const ArenaBitVector* visited) {
+void HBasicBlock::DisconnectFromSuccessors(BitVectorView<const size_t> visited) {
+  DCHECK_IMPLIES(visited.SizeInBits() != 0u, visited.SizeInBits() == graph_->GetBlocks().size());
   for (HBasicBlock* successor : successors_) {
     // Delete this block from the list of predecessors.
     size_t this_index = successor->GetPredecessorIndexOf(this);
     successor->predecessors_.erase(successor->predecessors_.begin() + this_index);
 
-    if (visited != nullptr && !visited->IsBitSet(successor->GetBlockId())) {
+    if (visited.SizeInBits() != 0u && !visited.IsBitSet(successor->GetBlockId())) {
       // `successor` itself is dead. Therefore, there is no need to update its phis.
       continue;
     }
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index e59dcf26c1..772828d9ef 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -289,7 +289,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
   void ComputeDominanceInformation();
   void ClearDominanceInformation();
   void ClearLoopInformation();
-  void FindBackEdges(ArenaBitVector* visited);
+  void FindBackEdges(/*out*/ BitVectorView<size_t> visited);
   GraphAnalysisResult BuildDominatorTree();
   GraphAnalysisResult RecomputeDominatorTree();
   void SimplifyCFG();
@@ -545,8 +545,8 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
   bool IsUsefulOptimizing() const { return useful_optimizing_; }
 
  private:
-  void RemoveDeadBlocksInstructionsAsUsersAndDisconnect(const ArenaBitVector& visited) const;
-  void RemoveDeadBlocks(const ArenaBitVector& visited);
+  void RemoveDeadBlocksInstructionsAsUsersAndDisconnect(BitVectorView<const size_t> visited) const;
+  void RemoveDeadBlocks(BitVectorView<const size_t> visited);
 
   template <class InstructionType, typename ValueType>
   InstructionType* CreateConstant(ValueType value,
@@ -1133,7 +1133,7 @@ class HBasicBlock : public ArenaObject<kArenaAllocBasicBlock> {
   // Disconnects `this` from all its successors and updates their phis, if the successors have them.
   // If `visited` is provided, it will use the information to know if a successor is reachable and
   // skip updating those phis.
-  void DisconnectFromSuccessors(const ArenaBitVector* visited = nullptr);
+  void DisconnectFromSuccessors(BitVectorView<const size_t> visited = {});
 
   // Removes the catch phi uses of the instructions in `this`, and then remove the instruction
   // itself. If `building_dominator_tree` is true, it will not remove the instruction as user, since
diff --git a/libartbase/base/arena_bit_vector.h b/libartbase/base/arena_bit_vector.h
index 41d4ff7458..757f481b24 100644
--- a/libartbase/base/arena_bit_vector.h
+++ b/libartbase/base/arena_bit_vector.h
@@ -18,7 +18,6 @@
 #define ART_LIBARTBASE_BASE_ARENA_BIT_VECTOR_H_
 
 #include <algorithm>
-#include <cstring>
 
 #include "arena_object.h"
 #include "base/arena_allocator.h"
@@ -63,13 +62,13 @@ class ArenaBitVector : public BitVector, public ArenaObject<kArenaAllocGrowableB
                   std::is_same_v<Allocator, ScopedArenaAllocator>);
     size_t num_elements = BitVectorView<StorageType>::BitsToWords(bits);
     StorageType* storage = allocator->template AllocArray<StorageType>(num_elements, kind);
+    BitVectorView<StorageType> result(storage, bits);
     if (std::is_same_v<Allocator, ScopedArenaAllocator>) {
-      memset(storage, 0, num_elements * sizeof(StorageType));
+      result.ClearAllBits();
     } else {
-      DCHECK_EQ(std::count(storage, storage + num_elements, static_cast<StorageType>(0)),
-                num_elements);
+      DCHECK(!result.IsAnyBitSet());
     }
-    return {storage, bits};
+    return result;
   }
 };
 
diff --git a/libartbase/base/bit_vector-inl.h b/libartbase/base/bit_vector-inl.h
index 2bdc14ebe9..03cab63ea1 100644
--- a/libartbase/base/bit_vector-inl.h
+++ b/libartbase/base/bit_vector-inl.h
@@ -20,11 +20,36 @@
 #include "bit_vector.h"
 
 #include <android-base/logging.h>
+#include <cstring>
 
 #include "bit_utils.h"
 
 namespace art {
 
+template <typename StorageType>
+inline void BitVectorView<StorageType>::ClearAllBits() {
+  // Note: We do not `DCheckTrailingBitsClear()` here as this may be the initial call
+  // to clear the storage and the trailing bits may not be clear after allocation.
+  memset(storage_, 0, SizeInWords() * sizeof(WordType));
+}
+
+template <typename StorageType>
+inline void BitVectorView<StorageType>::SetInitialBits(uint32_t num_bits) {
+  // Note: We do not `DCheckTrailingBitsClear()` here as this may be the initial call
+  // to clear the storage and the trailing bits may not be clear after allocation.
+  DCHECK_LE(num_bits, SizeInBits());
+  size_t words = WordIndex(num_bits);
+  // Set initial full words.
+  std::fill_n(storage_, words, std::numeric_limits<WordType>::max());
+  if (num_bits % kWordBits != 0) {
+    // Set all bits below the first clear bit in the boundary storage word.
+    storage_[words] = BitMask(num_bits) - static_cast<StorageType>(1u);
+    ++words;
+  }
+  // Set clear words if any.
+  std::fill_n(storage_ + words, SizeInWords() - words, static_cast<StorageType>(0));
+}
+
 inline bool BitVector::IndexIterator::operator==(const IndexIterator& other) const {
   DCHECK(bit_storage_ == other.bit_storage_);
   DCHECK_EQ(storage_size_, other.storage_size_);
@@ -86,7 +111,7 @@ inline BitVector::IndexIterator BitVector::IndexContainer::end() const {
 }
 
 inline void BitVector::ClearAllBits() {
-  memset(storage_, 0, storage_size_ * kWordBytes);
+  AsView().ClearAllBits();
 }
 
 inline bool BitVector::Equal(const BitVector* src) const {
diff --git a/libartbase/base/bit_vector.h b/libartbase/base/bit_vector.h
index 35a5e7c95b..ad81edf0bc 100644
--- a/libartbase/base/bit_vector.h
+++ b/libartbase/base/bit_vector.h
@@ -19,17 +19,27 @@
 
 #include <stdint.h>
 
+#include <algorithm>
 #include <iterator>
 #include <limits>
 
 #include "bit_utils.h"
 #include "globals.h"
+#include "logging.h"
 
 namespace art {
 
 class Allocator;
 
 // A bit vector view encapsulating externally-provided fixed-size storage for bits.
+//
+// The size in bits does not need to specify whole number of storage words but the view
+// is intended to work only on the specified number of bits. Single-bit functions
+// `SetBit()`, `ClearBit()` and `IsBitSet()` verify the passed index with `DCHECK()`
+// and do not care about trailing bits in the last storage word, if any. Multi-bit
+// functions require that the trailing bits are cleared on entry, except for functions
+// `ClearAllBits()` and `SetInitialBits()` that are used for storage initialization
+// and clear the trailing bits, if any.
 template <typename StorageType = size_t>
 class BitVectorView {
  public:
@@ -43,6 +53,11 @@ class BitVectorView {
     return (bits + /* round up */ (kWordBits - 1)) / kWordBits;
   }
 
+  // Construct an empty `BitVectorView`.
+  constexpr BitVectorView()
+      : storage_(nullptr), size_in_bits_(0u) {}
+
+  // Construct a `BitVectorView` referencing the provided backing storage.
   constexpr BitVectorView(WordType* storage, size_t size_in_bits)
       : storage_(storage), size_in_bits_(size_in_bits) {}
 
@@ -50,25 +65,53 @@ class BitVectorView {
   // The new copy shall reference the same underlying data, similarly to `std::string_view`.
   BitVectorView(const BitVectorView& src) = default;
 
+  // Implicit conversion to a view with constant storage.
+  template <typename ST,
+            typename = std::enable_if_t<std::is_const_v<StorageType> &&
+                                        std::is_same_v<ST, std::remove_const_t<StorageType>>>>
+  BitVectorView(const BitVectorView<ST>& src)
+      : storage_(src.storage_), size_in_bits_(src.size_in_bits_) {}
+
+  // Get the size of the bit vector view in bits.
   constexpr size_t SizeInBits() const {
     return size_in_bits_;
   }
 
+  // Get the size of the bit vector view in storage words.
+  constexpr size_t SizeInWords() const {
+    return BitsToWords(SizeInBits());
+  }
+
+  // Mark the specified bit as "set".
   void SetBit(size_t index) {
     DCHECK_LT(index, size_in_bits_);
     storage_[WordIndex(index)] |= BitMask(index);
   }
 
+  // Mark the specified bit as "clear".
   void ClearBit(size_t index) {
     DCHECK_LT(index, size_in_bits_);
     storage_[WordIndex(index)] &= ~BitMask(index);
   }
 
+  // Determine whether or not the specified bit is set.
   constexpr bool IsBitSet(size_t index) const {
     DCHECK_LT(index, size_in_bits_);
     return (storage_[WordIndex(index)] & BitMask(index)) != 0u;
   }
 
+  // Mark all bits as "clear".
+  void ClearAllBits();
+
+  // Mark specified number of initial bits as "set" and clear all bits after that.
+  void SetInitialBits(uint32_t num_bits);
+
+  // Return true if there are any bits set, false otherwise.
+  bool IsAnyBitSet() const {
+    DCheckTrailingBitsClear();
+    return std::any_of(storage_, storage_ + SizeInWords(), [](WordType w) { return w != 0u; });
+  }
+
  private:
   static constexpr size_t WordIndex(size_t index) {
     return index >> WhichPowerOf2(kWordBits);
@@ -78,8 +121,16 @@ class BitVectorView {
     return static_cast<WordType>(1) << (index % kWordBits);
   }
 
+  constexpr void DCheckTrailingBitsClear() const {
+    DCHECK_IMPLIES(SizeInBits() % kWordBits != 0u,
+                   (storage_[WordIndex(SizeInBits())] & ~(BitMask(SizeInBits()) - 1u)) == 0u);
+  }
+
   WordType* storage_;
   size_t size_in_bits_;
+
+  // For implicit conversion to a view with constant storage.
+  template <typename ST> friend class BitVectorView;
 };
 
 /*
@@ -210,7 +261,7 @@ class BitVector {
     AsView().SetBit(idx);
   }
 
-  // Mark the specified bit as "unset".
+  // Mark the specified bit as "clear".
   void ClearBit(uint32_t idx) {
     // If the index is over the size, we don't have to do anything, it is cleared.
     if (idx < storage_size_ * kWordBits) {
@@ -226,7 +277,7 @@ class BitVector {
     return (idx < (storage_size_ * kWordBits)) && AsView().IsBitSet(idx);
   }
 
-  // Mark all bits bit as "clear".
+  // Mark all bits as "clear".
   void ClearAllBits();
 
   // Mark specified number of bits as "set". Cannot set all bits like ClearAll since there might
@@ -304,7 +355,7 @@ class BitVector {
    * @return true if there are any bits set, false otherwise.
    */
   bool IsAnyBitSet() const {
-    return GetHighestBitSet() != -1;
+    return AsView().IsAnyBitSet();
   }
 
   // Minimum number of bits required to store this vector, 0 if none are set.
diff --git a/libartbase/base/bit_vector_test.cc b/libartbase/base/bit_vector_test.cc
index 15803edd17..2e9c252473 100644
--- a/libartbase/base/bit_vector_test.cc
+++ b/libartbase/base/bit_vector_test.cc
@@ -29,7 +29,7 @@ template <typename StorageType, StorageType kWord0, StorageType kWord1>
 void TestBitVectorViewSetBitAndClearBit() {
   static constexpr StorageType kStorage[2] = { kWord0, kWord1 };
   static constexpr size_t kSizeInBits = 2 * BitSizeOf<StorageType>();
-  static constexpr BitVectorView<const StorageType> kRbv(kStorage, kSizeInBits);
+  static constexpr BitVectorView<const StorageType> kBvv(kStorage, kSizeInBits);
   auto get_bit_from_params = [](size_t index) constexpr {
     StorageType word = (index < BitSizeOf<StorageType>()) ? kWord0 : kWord1;
     size_t shift = index % BitSizeOf<StorageType>();
@@ -38,42 +38,46 @@ void TestBitVectorViewSetBitAndClearBit() {
   auto verify_is_bit_set = [get_bit_from_params]() constexpr {
     for (size_t index = 0; index != kSizeInBits; ++index) {
       // If the `CHECK_EQ()` fails, the `static_assert` evaluation fails at compile time.
-      CHECK_EQ(get_bit_from_params(index), kRbv.IsBitSet(index)) << index;
+      CHECK_EQ(get_bit_from_params(index), kBvv.IsBitSet(index)) << index;
     }
     return true;
   };
   static_assert(verify_is_bit_set());
 
-  auto verify_size_in_bits = []() constexpr {
+  auto verify_size = []() constexpr {
     for (size_t size = 0; size != kSizeInBits; ++size) {
       // If the `CHECK_EQ()` fails, the `static_assert` evaluation fails at compile time.
       CHECK_EQ(size, BitVectorView(kStorage, size).SizeInBits());
+      size_t words = RoundUp(size, BitSizeOf<StorageType>()) / BitSizeOf<StorageType>();
+      CHECK_EQ(words, BitVectorView(kStorage, size).SizeInWords());
     }
     return true;
   };
-  static_assert(verify_size_in_bits());
+  static_assert(verify_size());
 
   StorageType storage[2] = {0u, 0u};
   size_t size_in_bits = 2 * BitSizeOf<StorageType>();
-  BitVectorView<StorageType> rbv(storage, size_in_bits);
+  BitVectorView<StorageType> bvv(storage, size_in_bits);
   for (size_t index = 0; index != size_in_bits; ++index) {
-    ASSERT_FALSE(rbv.IsBitSet(index));
+    ASSERT_FALSE(bvv.IsBitSet(index));
   }
   // Set one bit at a time, then clear it.
   for (size_t bit_to_set = 0; bit_to_set != size_in_bits; ++bit_to_set) {
-    rbv.SetBit(bit_to_set);
+    bvv.SetBit(bit_to_set);
     for (size_t index = 0; index != size_in_bits; ++index) {
-      ASSERT_EQ(index == bit_to_set, rbv.IsBitSet(index));
+      ASSERT_EQ(index == bit_to_set, bvv.IsBitSet(index));
     }
-    rbv.ClearBit(bit_to_set);
+    ASSERT_TRUE(bvv.IsAnyBitSet());
+    bvv.ClearBit(bit_to_set);
     for (size_t index = 0; index != size_in_bits; ++index) {
-      ASSERT_FALSE(rbv.IsBitSet(index));
+      ASSERT_FALSE(bvv.IsBitSet(index));
     }
+    ASSERT_FALSE(bvv.IsAnyBitSet());
   }
   // Set bits for `kWord0` and `kWord1`.
   for (size_t index = 0; index != size_in_bits; ++index) {
     if (get_bit_from_params(index)) {
-      rbv.SetBit(index);
+      bvv.SetBit(index);
     }
   }
   ASSERT_EQ(kWord0, storage[0]);
@@ -81,7 +85,7 @@ void TestBitVectorViewSetBitAndClearBit() {
   // Clear all bits that are already clear.
   for (size_t index = 0; index != size_in_bits; ++index) {
     if (!get_bit_from_params(index)) {
-      rbv.ClearBit(index);
+      bvv.ClearBit(index);
     }
   }
   ASSERT_EQ(kWord0, storage[0]);
@@ -89,7 +93,7 @@ void TestBitVectorViewSetBitAndClearBit() {
   // Clear all bits that are set.
   for (size_t index = 0; index != size_in_bits; ++index) {
     if (get_bit_from_params(index)) {
-      rbv.ClearBit(index);
+      bvv.ClearBit(index);
     }
   }
   ASSERT_EQ(0u, storage[0]);
@@ -113,6 +117,66 @@ TEST(BitVectorView, SizeT) {
                                      static_cast<size_t>(UINT64_C(0x1234567890abcdef))>();
 }
 
+TEST(BitVectorView, ConversionToConstStorage) {
+  uint32_t storage[] = {1u, 2u, 3u};
+  size_t size = 2 * BitSizeOf<uint32_t>() + MinimumBitsToStore(storage[2]);
+  BitVectorView<uint32_t> bvv(storage, size);
+  auto is_bit_set = [](BitVectorView<const uint32_t> cbvv, size_t index) {
+    return cbvv.IsBitSet(index);
+  };
+  for (size_t index = 0; index != size; ++index) {
+    ASSERT_EQ(bvv.IsBitSet(index), is_bit_set(bvv, index));
+  }
+}
+
+TEST(BitVectorView, DefaultConstructor) {
+  BitVectorView<> bvv;
+  ASSERT_EQ(0u, bvv.SizeInBits());
+  ASSERT_EQ(0u, bvv.SizeInWords());
+}
+
+TEST(BitVectorView, ClearAllBits) {
+  uint32_t storage[] = {1u, 2u, 0xffffffffu};
+  size_t size = 2 * BitSizeOf<uint32_t>() + 1u;
+  BitVectorView<uint32_t> bvv(storage, size);  // Construction allowed with bogus trailing bits.
+  ASSERT_EQ(1u, storage[0]);
+  ASSERT_EQ(2u, storage[1]);
+  ASSERT_EQ(0xffffffffu, storage[2]);
+  bvv.ClearAllBits();
+  ASSERT_EQ(0u, storage[0]);
+  ASSERT_EQ(0u, storage[1]);
+  ASSERT_EQ(0u, storage[2]);
+}
+
+TEST(BitVectorView, SetInitialBits) {
+  uint32_t storage[] = {1u, 2u, 0xffffffffu};
+  size_t size = 2 * BitSizeOf<uint32_t>() + 1u;
+  BitVectorView<uint32_t> bvv(storage, size);  // Construction allowed with bogus trailing bits.
+  ASSERT_EQ(1u, storage[0]);
+  ASSERT_EQ(2u, storage[1]);
+  ASSERT_EQ(0xffffffffu, storage[2]);
+  bvv.SetInitialBits(40u);
+  ASSERT_EQ(0xffffffffu, storage[0]);
+  ASSERT_EQ(0xffu, storage[1]);
+  ASSERT_EQ(0u, storage[2]);
+  bvv.SetInitialBits(0u);
+  ASSERT_EQ(0u, storage[0]);
+  ASSERT_EQ(0u, storage[1]);
+  ASSERT_EQ(0u, storage[2]);
+  bvv.SetInitialBits(17u);
+  ASSERT_EQ(0x1ffffu, storage[0]);
+  ASSERT_EQ(0u, storage[1]);
+  ASSERT_EQ(0u, storage[2]);
+  bvv.SetInitialBits(64u);
+  ASSERT_EQ(0xffffffffu, storage[0]);
+  ASSERT_EQ(0xffffffffu, storage[1]);
+  ASSERT_EQ(0u, storage[2]);
+  bvv.SetInitialBits(65u);
+  ASSERT_EQ(0xffffffffu, storage[0]);
+  ASSERT_EQ(0xffffffffu, storage[1]);
+  ASSERT_EQ(1u, storage[2]);
+}
+
 TEST(BitVector, Test) {
   const size_t kBits = 32;