summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/gvn.cc17
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.h1
-rw-r--r--libartbase/base/bit_vector-inl.h110
-rw-r--r--libartbase/base/bit_vector.h130
-rw-r--r--libartbase/base/bit_vector_test.cc53
5 files changed, 196 insertions, 115 deletions
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index a82d6c4325..188bfa473d 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -41,7 +41,7 @@ class ValueSet : public ArenaObject<kArenaAllocGvn> {
: allocator_(allocator),
num_buckets_(kMinimumNumberOfBuckets),
buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)),
- buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn),
+ buckets_owned_(ArenaBitVector::CreateFixedSize(allocator, num_buckets_, kArenaAllocGvn)),
num_entries_(0u) {
DCHECK(IsPowerOfTwo(num_buckets_));
std::fill_n(buckets_, num_buckets_, nullptr);
@@ -54,7 +54,7 @@ class ValueSet : public ArenaObject<kArenaAllocGvn> {
: allocator_(allocator),
num_buckets_(other.IdealBucketCount()),
buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)),
- buckets_owned_(allocator, num_buckets_, false, kArenaAllocGvn),
+ buckets_owned_(ArenaBitVector::CreateFixedSize(allocator, num_buckets_, kArenaAllocGvn)),
num_entries_(0u) {
DCHECK(IsPowerOfTwo(num_buckets_));
PopulateFromInternal(other);
@@ -342,7 +342,7 @@ class ValueSet : public ArenaObject<kArenaAllocGvn> {
// Flags specifying which buckets were copied into the set from its parent.
// If a flag is not set, the corresponding bucket points to entries in the
// parent and must be cloned prior to making changes.
- ArenaBitVector buckets_owned_;
+ BitVectorView<size_t> buckets_owned_;
// The number of entries in the set.
size_t num_entries_;
@@ -364,9 +364,10 @@ class GlobalValueNumberer : public ValueObject {
sets_(graph->GetBlocks().size(), nullptr, allocator_.Adapter(kArenaAllocGvn)),
dominated_to_visit_(graph->GetBlocks().size(), allocator_.Adapter(kArenaAllocGvn)),
successors_to_visit_(graph->GetBlocks().size(), allocator_.Adapter(kArenaAllocGvn)),
- free_sets_(&allocator_, graph->GetBlocks().size(), /* expandable= */ false, kArenaAllocGvn),
- visited_blocks_(
- &allocator_, graph->GetBlocks().size(), /* expandable= */ false, kArenaAllocGvn),
+ free_sets_(ArenaBitVector::CreateFixedSize(
+ &allocator_, graph->GetBlocks().size(), kArenaAllocGvn)),
+ visited_blocks_(ArenaBitVector::CreateFixedSize(
+ &allocator_, graph->GetBlocks().size(), kArenaAllocGvn)),
did_optimization_(false) {
for (HBasicBlock* block : graph->GetReversePostOrder()) {
dominated_to_visit_[block->GetBlockId()] = block->GetDominatedBlocks().size();
@@ -418,11 +419,11 @@ class GlobalValueNumberer : public ValueObject {
// Number of successor blocks left to visit.
ScopedArenaVector<uint32_t> successors_to_visit_;
// True iff the block's ValueSet is free to be reused by another block.
- ArenaBitVector free_sets_;
+ BitVectorView<size_t> free_sets_;
// BitVector which serves as a fast-access map from block id to
// visited/unvisited Boolean.
- ArenaBitVector visited_blocks_;
+ BitVectorView<size_t> visited_blocks_;
// True if GVN did at least one removal.
bool did_optimization_;
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index e9422edb15..21b7831f10 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -19,6 +19,7 @@
#include <iostream>
+#include "base/bit_vector-inl.h"
#include "base/intrusive_forward_list.h"
#include "base/iteration_range.h"
#include "base/macros.h"
diff --git a/libartbase/base/bit_vector-inl.h b/libartbase/base/bit_vector-inl.h
index 03cab63ea1..dd9071df5c 100644
--- a/libartbase/base/bit_vector-inl.h
+++ b/libartbase/base/bit_vector-inl.h
@@ -50,64 +50,100 @@ inline void BitVectorView<StorageType>::SetInitialBits(uint32_t num_bits) {
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_);
+template <typename StorageType>
+inline bool BitVectorIndexIterator<StorageType>::operator==(
+ const BitVectorIndexIterator<StorageType>& other) const {
+ DCHECK_EQ(bit_vector_view_.storage_, other.bit_vector_view_.storage_);
+ DCHECK_EQ(bit_vector_view_.size_in_bits_, other.bit_vector_view_.size_in_bits_);
return bit_index_ == other.bit_index_;
}
-inline uint32_t BitVector::IndexIterator::operator*() const {
- DCHECK_LT(bit_index_, BitSize());
+template <typename StorageType>
+inline bool BitVectorIndexIterator<StorageType>::operator!=(
+ const BitVectorIndexIterator<StorageType>& other) const {
+ return !(*this == other);
+}
+
+template <typename StorageType>
+inline size_t BitVectorIndexIterator<StorageType>::operator*() const {
+ DCHECK_LT(bit_index_, bit_vector_view_.size_in_bits_);
return bit_index_;
}
-inline BitVector::IndexIterator& BitVector::IndexIterator::operator++() {
- DCHECK_LT(bit_index_, BitSize());
+template <typename StorageType>
+inline BitVectorIndexIterator<StorageType>& BitVectorIndexIterator<StorageType>::operator++() {
+ DCHECK_LT(bit_index_, bit_vector_view_.size_in_bits_);
bit_index_ = FindIndex(bit_index_ + 1u);
return *this;
}
-inline BitVector::IndexIterator BitVector::IndexIterator::operator++(int) {
- IndexIterator result(*this);
+template <typename StorageType>
+inline BitVectorIndexIterator<StorageType> BitVectorIndexIterator<StorageType>::operator++(int) {
+ BitVectorIndexIterator result(*this);
++*this;
return result;
}
-inline uint32_t BitVector::IndexIterator::FindIndex(uint32_t start_index) const {
- DCHECK_LE(start_index, BitSize());
- uint32_t word_index = start_index / kWordBits;
- if (UNLIKELY(word_index == storage_size_)) {
+template <typename StorageType>
+inline size_t BitVectorIndexIterator<StorageType>::FindIndex(size_t start_index) const {
+ DCHECK_LE(start_index, bit_vector_view_.size_in_bits_);
+ bit_vector_view_.DCheckTrailingBitsClear();
+ if (UNLIKELY(start_index == bit_vector_view_.size_in_bits_)) {
return start_index;
}
- uint32_t word = bit_storage_[word_index];
+ size_t word_index = start_index / kWordBits;
+ DCHECK_LT(word_index, bit_vector_view_.SizeInWords());
+ std::remove_const_t<StorageType> word = bit_vector_view_.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];
+ word &= std::numeric_limits<StorageType>::max() << (start_index % kWordBits);
+ if (word == 0u) {
+ size_t size_in_words = bit_vector_view_.SizeInWords();
+ do {
+ ++word_index;
+ if (UNLIKELY(word_index == size_in_words)) {
+ return bit_vector_view_.size_in_bits_;
+ }
+ word = bit_vector_view_.storage_[word_index];
+ } while (word == 0u);
}
- return word_index * 32u + CTZ(word);
+ return word_index * kWordBits + CTZ(word);
}
-inline BitVector::IndexIterator::IndexIterator(const BitVector* bit_vector, begin_tag)
- : bit_storage_(bit_vector->GetRawStorage()),
- storage_size_(bit_vector->storage_size_),
- bit_index_(FindIndex(0u)) { }
+template <typename StorageType>
+inline BitVectorIndexIterator<StorageType>::BitVectorIndexIterator(
+ BitVectorView<StorageType> bit_vector_view, begin_tag)
+ : bit_vector_view_(bit_vector_view),
+ bit_index_(FindIndex(0u)) { }
-inline BitVector::IndexIterator::IndexIterator(const BitVector* bit_vector, end_tag)
- : bit_storage_(bit_vector->GetRawStorage()),
- storage_size_(bit_vector->storage_size_),
- bit_index_(BitSize()) { }
+template <typename StorageType>
+inline BitVectorIndexIterator<StorageType>::BitVectorIndexIterator(
+ BitVectorView<StorageType> bit_vector_view, end_tag)
+ : bit_vector_view_(bit_vector_view),
+ bit_index_(bit_vector_view_.size_in_bits_) { }
-inline BitVector::IndexIterator BitVector::IndexContainer::begin() const {
- return IndexIterator(bit_vector_, IndexIterator::begin_tag());
-}
+template <typename StorageType>
+class BitVectorView<StorageType>::IndexContainerImpl {
+ static_assert(std::is_const_v<StorageType>);
+
+ public:
+ explicit IndexContainerImpl(BitVectorView<StorageType> bit_vector_view)
+ : bit_vector_view_(bit_vector_view) { }
+
+ BitVectorIndexIterator<StorageType> begin() const {
+ return {bit_vector_view_, typename BitVectorIndexIterator<StorageType>::begin_tag()};
+ }
+
+ BitVectorIndexIterator<StorageType> end() const {
+ return {bit_vector_view_, typename BitVectorIndexIterator<StorageType>::end_tag()};
+ }
+
+ private:
+ BitVectorView<StorageType> bit_vector_view_;
+};
-inline BitVector::IndexIterator BitVector::IndexContainer::end() const {
- return IndexIterator(bit_vector_, IndexIterator::end_tag());
+template <typename StorageType>
+BitVectorView<StorageType>::IndexContainer BitVectorView<StorageType>::Indexes() const {
+ return BitVectorView<StorageType>::IndexContainer(*this);
}
inline void BitVector::ClearAllBits() {
@@ -120,6 +156,10 @@ inline bool BitVector::Equal(const BitVector* src) const {
(memcmp(storage_, src->GetRawStorage(), storage_size_ * sizeof(uint32_t)) == 0);
}
+inline BitVector::IndexContainer BitVector::Indexes() const {
+ return AsView().Indexes();
+}
+
} // namespace art
#endif // ART_LIBARTBASE_BASE_BIT_VECTOR_INL_H_
diff --git a/libartbase/base/bit_vector.h b/libartbase/base/bit_vector.h
index ad81edf0bc..56a8f0f612 100644
--- a/libartbase/base/bit_vector.h
+++ b/libartbase/base/bit_vector.h
@@ -112,6 +112,12 @@ class BitVectorView {
return std::any_of(storage_, storage_ + SizeInWords(), [](WordType w) { return w != 0u; });
}
+ // `BitVectorView` wrapper class for iteration across indexes of set bits.
+ class IndexContainerImpl;
+ using IndexContainer = BitVectorView<const StorageType>::IndexContainerImpl;
+
+ IndexContainer Indexes() const;
+
private:
static constexpr size_t WordIndex(size_t index) {
return index >> WhichPowerOf2(kWordBits);
@@ -129,91 +135,75 @@ class BitVectorView {
WordType* storage_;
size_t size_in_bits_;
- // For implicit conversion to a view with constant storage.
+ template <typename ST> friend class BitVectorIndexIterator;
template <typename ST> friend class BitVectorView;
};
-/*
- * Expanding bitmap. Bits are numbered starting from zero. All operations on a BitVector are
- * unsynchronized. New BitVectors are not necessarily zeroed out. If the used allocator doesn't do
- * clear the vector (e.g. ScopedArenaAllocator), the responsibility of clearing it relies on the
- * caller (e.g. ArenaBitVector).
+/**
+ * @brief Convenient iterator across the indexes of the bits in `BitVector` or `BitVectorView<>`.
+ *
+ * @details BitVectorIndexIterator 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{,View}::Indexes()` which return an index container wrapper
+ * object with begin() and end() suitable for range-based loops:
+ * for (uint32_t idx : bit_vector.Indexes()) {
+ * // Use idx.
+ * }
*/
-class BitVector {
- public:
- static constexpr uint32_t kWordBytes = sizeof(uint32_t);
- static constexpr uint32_t kWordBits = kWordBytes * 8;
+template <typename StorageType>
+class BitVectorIndexIterator {
+ static_assert(std::is_const_v<StorageType>);
- 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 {
- public:
- using iterator_category = std::forward_iterator_tag;
- using value_type = uint32_t;
- using difference_type = ptrdiff_t;
- using pointer = void;
- using reference = void;
-
- bool operator==(const IndexIterator& other) const;
-
- bool operator!=(const IndexIterator& other) const {
- return !(*this == other);
- }
+ public:
+ using iterator_category = std::forward_iterator_tag;
+ using value_type = size_t;
+ using difference_type = ptrdiff_t;
+ using pointer = void;
+ using reference = void;
- uint32_t operator*() const;
+ bool operator==(const BitVectorIndexIterator& other) const;
+ bool operator!=(const BitVectorIndexIterator& other) const;
- IndexIterator& operator++();
+ size_t operator*() const;
- IndexIterator operator++(int);
+ BitVectorIndexIterator& operator++();
+ BitVectorIndexIterator operator++(int);
- // Helper function to check for end without comparing with bit_vector.Indexes().end().
- bool Done() const {
- return bit_index_ == BitSize();
- }
+ // Helper function to check for end without comparing with bit_vector.Indexes().end().
+ bool Done() const {
+ return bit_index_ == bit_vector_view_.SizeInBits();
+ }
- private:
- struct begin_tag { };
- struct end_tag { };
+ private:
+ struct begin_tag { };
+ struct end_tag { };
- IndexIterator(const BitVector* bit_vector, begin_tag);
- IndexIterator(const BitVector* bit_vector, end_tag);
+ BitVectorIndexIterator(BitVectorView<StorageType> bit_vector_view, begin_tag);
+ BitVectorIndexIterator(BitVectorView<StorageType> bit_vector_view, end_tag);
- uint32_t BitSize() const {
- return storage_size_ * kWordBits;
- }
+ size_t FindIndex(size_t start_index) const;
- uint32_t FindIndex(uint32_t start_index) const;
- 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).
+ static constexpr size_t kWordBits = BitVectorView<StorageType>::kWordBits;
- friend class BitVector::IndexContainer;
- };
+ const BitVectorView<StorageType> bit_vector_view_;
+ size_t bit_index_; // Current index (size in bits).
- /**
- * @brief BitVector wrapper class for iteration across indexes of set bits.
- */
- class IndexContainer {
- public:
- explicit IndexContainer(const BitVector* bit_vector) : bit_vector_(bit_vector) { }
+ template <typename ST>
+ friend class BitVectorView;
+};
- IndexIterator begin() const;
- IndexIterator end() const;
+/*
+ * Expanding bitmap. Bits are numbered starting from zero. All operations on a BitVector are
+ * unsynchronized. New BitVectors are not necessarily zeroed out. If the used allocator doesn't do
+ * clear the vector (e.g. ScopedArenaAllocator), the responsibility of clearing it relies on the
+ * caller (e.g. ArenaBitVector).
+ */
+class BitVector {
+ public:
+ static constexpr uint32_t kWordBytes = sizeof(uint32_t);
+ static constexpr uint32_t kWordBits = kWordBytes * 8;
- private:
- const BitVector* const bit_vector_;
- };
+ using IndexContainer = BitVectorView<uint32_t>::IndexContainer;
// MoveConstructible but not MoveAssignable, CopyConstructible or CopyAssignable.
@@ -314,9 +304,7 @@ class BitVector {
// Count the number of bits that are set in range [0, end).
uint32_t NumSetBits(uint32_t end) const;
- IndexContainer Indexes() const {
- return IndexContainer(this);
- }
+ IndexContainer Indexes() const;
uint32_t GetStorageSize() const {
return storage_size_;
diff --git a/libartbase/base/bit_vector_test.cc b/libartbase/base/bit_vector_test.cc
index 2e9c252473..d846b8403f 100644
--- a/libartbase/base/bit_vector_test.cc
+++ b/libartbase/base/bit_vector_test.cc
@@ -16,6 +16,7 @@
#include <memory>
#include <random>
+#include <vector>
#include "allocator.h"
#include "base/stl_util.h"
@@ -177,6 +178,56 @@ TEST(BitVectorView, SetInitialBits) {
ASSERT_EQ(1u, storage[2]);
}
+template <typename StorageType, StorageType kWord0, StorageType kWord1>
+void TestBitVectorViewIndexes() {
+ StorageType storage[] = {kWord0, kWord1};
+ size_t size = 2u * BitSizeOf<StorageType>();
+ BitVectorView bvv(storage, size);
+
+ std::vector<size_t> indexes1;
+ for (size_t index = 0; index != size; ++index) {
+ if (bvv.IsBitSet(index)) {
+ indexes1.push_back(index);
+ }
+ }
+
+ std::vector<size_t> indexes2;
+ for (size_t index : bvv.Indexes()) {
+ indexes2.push_back(index);
+ }
+ ASSERT_EQ(indexes1, indexes2);
+
+ std::vector<size_t> indexes3;
+ for (auto it = bvv.Indexes().begin(); !it.Done(); ++it) {
+ indexes3.push_back(*it);
+ }
+ ASSERT_EQ(indexes1, indexes3);
+
+ StorageType empty_storage[] = {0u, 0u, 0u};
+ BitVectorView empty(empty_storage, 3 * BitSizeOf<StorageType>() - 1u);
+ for (size_t index : empty.Indexes()) {
+ FAIL();
+ }
+ ASSERT_TRUE(empty.Indexes().begin().Done());
+}
+
+TEST(BitVectorView, IndexesUint32T) {
+ TestBitVectorViewIndexes<uint32_t, 0x12345678u, 0x87654321u>();
+}
+
+TEST(BitVectorView, IndexesUint64T) {
+ TestBitVectorViewIndexes<uint64_t,
+ UINT64_C(0x1234567890abcdef),
+ UINT64_C(0xfedcba0987654321)>();
+}
+
+TEST(BitVectorView, IndexesSizeT) {
+ // Note: The constants below are truncated on 32-bit architectures.
+ TestBitVectorViewIndexes<size_t,
+ static_cast<size_t>(UINT64_C(0xfedcba0987654321)),
+ static_cast<size_t>(UINT64_C(0x1234567890abcdef))>();
+}
+
TEST(BitVector, Test) {
const size_t kBits = 32;
@@ -210,7 +261,7 @@ TEST(BitVector, Test) {
EXPECT_EQ(0x80000001U, bv.GetRawStorageWord(0));
EXPECT_EQ(0x80000001U, *bv.GetRawStorage());
- BitVector::IndexIterator iterator = bv.Indexes().begin();
+ BitVectorIndexIterator<const uint32_t> iterator = bv.Indexes().begin();
EXPECT_TRUE(iterator != bv.Indexes().end());
EXPECT_EQ(0u, *iterator);
++iterator;
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2026-01-08 16:27:09 +0000