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

1 files changed, 54 insertions, 3 deletions

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.