summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/liveness_test.cc10
-rw-r--r--compiler/optimizing/register_allocation_resolver.cc8
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.cc57
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.h48
-rw-r--r--libartbase/base/bit_vector-inl.h33
-rw-r--r--libartbase/base/bit_vector.h7
-rw-r--r--libartbase/base/bit_vector_test.cc122
7 files changed, 229 insertions, 56 deletions
diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc
index 0b421cf9e6..1e4ef8f867 100644
--- a/compiler/optimizing/liveness_test.cc
+++ b/compiler/optimizing/liveness_test.cc
@@ -33,14 +33,14 @@ class LivenessTest : public CommonCompilerTest, public OptimizingUnitTestHelper
void TestCode(const std::vector<uint16_t>& data, const char* expected);
};
-static void DumpBitVector(BitVector* vector,
+static void DumpBitVector(BitVectorView<size_t> vector,
std::ostream& buffer,
size_t count,
const char* prefix) {
buffer << prefix;
buffer << '(';
for (size_t i = 0; i < count; ++i) {
- buffer << vector->IsBitSet(i);
+ buffer << vector.IsBitSet(i);
}
buffer << ")\n";
}
@@ -59,11 +59,11 @@ void LivenessTest::TestCode(const std::vector<uint16_t>& data, const char* expec
for (HBasicBlock* block : graph->GetBlocks()) {
buffer << "Block " << block->GetBlockId() << std::endl;
size_t ssa_values = liveness.GetNumberOfSsaValues();
- BitVector* live_in = liveness.GetLiveInSet(*block);
+ BitVectorView<size_t> live_in = liveness.GetLiveInSet(*block);
DumpBitVector(live_in, buffer, ssa_values, " live in: ");
- BitVector* live_out = liveness.GetLiveOutSet(*block);
+ BitVectorView<size_t> live_out = liveness.GetLiveOutSet(*block);
DumpBitVector(live_out, buffer, ssa_values, " live out: ");
- BitVector* kill = liveness.GetKillSet(*block);
+ BitVectorView<size_t> kill = liveness.GetKillSet(*block);
DumpBitVector(kill, buffer, ssa_values, " kill: ");
}
ASSERT_STREQ(expected, buffer.str().c_str());
diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc
index a4b1698b8d..e847755978 100644
--- a/compiler/optimizing/register_allocation_resolver.cc
+++ b/compiler/optimizing/register_allocation_resolver.cc
@@ -155,8 +155,8 @@ void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoint
// Instructions live at the top of catch blocks or irreducible loop header
// were forced to spill.
if (kIsDebugBuild) {
- BitVector* live = liveness_.GetLiveInSet(*block);
- for (uint32_t idx : live->Indexes()) {
+ BitVectorView<size_t> live = liveness_.GetLiveInSet(*block);
+ for (uint32_t idx : live.Indexes()) {
LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
LiveInterval* sibling = interval->GetSiblingAt(block->GetLifetimeStart());
// `GetSiblingAt` returns the sibling that contains a position, but there could be
@@ -168,8 +168,8 @@ void RegisterAllocationResolver::Resolve(ArrayRef<HInstruction* const> safepoint
}
}
} else {
- BitVector* live = liveness_.GetLiveInSet(*block);
- for (uint32_t idx : live->Indexes()) {
+ BitVectorView<size_t> live = liveness_.GetLiveInSet(*block);
+ for (uint32_t idx : live.Indexes()) {
LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval();
for (HBasicBlock* predecessor : block->GetPredecessors()) {
ConnectSplitSiblings(interval, predecessor, block);
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 317e0999d7..8d727a660a 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -105,7 +105,7 @@ void SsaLivenessAnalysis::ComputeLiveness() {
void SsaLivenessAnalysis::RecursivelyProcessInputs(HInstruction* current,
HInstruction* actual_user,
- BitVector* live_in) {
+ BitVectorView<size_t> live_in) {
HInputsRef inputs = current->GetInputs();
for (size_t i = 0; i < inputs.size(); ++i) {
HInstruction* input = inputs[i];
@@ -121,7 +121,7 @@ void SsaLivenessAnalysis::RecursivelyProcessInputs(HInstruction* current,
// `input` generates a result used by `current`. Add use and update
// the live-in set.
input->GetLiveInterval()->AddUse(current, /* environment= */ nullptr, i, actual_user);
- live_in->SetBit(input->GetSsaIndex());
+ live_in.SetBit(input->GetSsaIndex());
} else if (has_out_location) {
// `input` generates a result but it is not used by `current`.
} else {
@@ -139,7 +139,7 @@ void SsaLivenessAnalysis::RecursivelyProcessInputs(HInstruction* current,
void SsaLivenessAnalysis::ProcessEnvironment(HInstruction* current,
HInstruction* actual_user,
- BitVector* live_in) {
+ BitVectorView<size_t> live_in) {
for (HEnvironment* environment = current->GetEnvironment();
environment != nullptr;
environment = environment->GetParent()) {
@@ -155,7 +155,7 @@ void SsaLivenessAnalysis::ProcessEnvironment(HInstruction* current,
// affect the live range of that instruction.
if (should_be_live) {
CHECK(instruction->HasSsaIndex()) << instruction->DebugName();
- live_in->SetBit(instruction->GetSsaIndex());
+ live_in.SetBit(instruction->GetSsaIndex());
instruction->GetLiveInterval()->AddUse(current,
environment,
i,
@@ -169,13 +169,13 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
// Do a post order visit, adding inputs of instructions live in the block where
// that instruction is defined, and killing instructions that are being visited.
for (HBasicBlock* block : ReverseRange(graph_->GetLinearOrder())) {
- BitVector* kill = GetKillSet(*block);
- BitVector* live_in = GetLiveInSet(*block);
+ BitVectorView kill = GetKillSet(*block);
+ BitVectorView live_in = GetLiveInSet(*block);
// Set phi inputs of successors of this block corresponding to this block
// as live_in.
for (HBasicBlock* successor : block->GetSuccessors()) {
- live_in->Union(GetLiveInSet(*successor));
+ live_in.Union(GetLiveInSet(*successor));
if (successor->IsCatchBlock()) {
// Inputs of catch phis will be kept alive through their environment
// uses, allowing the runtime to copy their values to the corresponding
@@ -193,14 +193,14 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
input->GetLiveInterval()->AddPhiUse(phi, phi_input_index, block);
// A phi input whose last user is the phi dies at the end of the predecessor block,
// and not at the phi's lifetime position.
- live_in->SetBit(input->GetSsaIndex());
+ live_in.SetBit(input->GetSsaIndex());
}
}
}
// Add a range that covers this block to all instructions live_in because of successors.
// Instructions defined in this block will have their start of the range adjusted.
- for (uint32_t idx : live_in->Indexes()) {
+ for (uint32_t idx : live_in.Indexes()) {
HInstruction* current = GetInstructionFromSsaIndex(idx);
current->GetLiveInterval()->AddRange(block->GetLifetimeStart(), block->GetLifetimeEnd());
}
@@ -210,8 +210,8 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
HInstruction* current = back_it.Current();
if (current->HasSsaIndex()) {
// Kill the instruction and shorten its interval.
- kill->SetBit(current->GetSsaIndex());
- live_in->ClearBit(current->GetSsaIndex());
+ kill.SetBit(current->GetSsaIndex());
+ live_in.ClearBit(current->GetSsaIndex());
current->GetLiveInterval()->SetFrom(current->GetLifetimePosition());
}
@@ -245,8 +245,8 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) {
HInstruction* current = inst_it.Current();
if (current->HasSsaIndex()) {
- kill->SetBit(current->GetSsaIndex());
- live_in->ClearBit(current->GetSsaIndex());
+ kill.SetBit(current->GetSsaIndex());
+ live_in.ClearBit(current->GetSsaIndex());
LiveInterval* interval = current->GetLiveInterval();
DCHECK((interval->GetFirstRange() == nullptr)
|| (interval->GetStart() == current->GetLifetimePosition()));
@@ -261,7 +261,7 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
size_t last_position = block->GetLoopInformation()->GetLifetimeEnd();
// For all live_in instructions at the loop header, we need to create a range
// that covers the full loop.
- for (uint32_t idx : live_in->Indexes()) {
+ for (uint32_t idx : live_in.Indexes()) {
HInstruction* current = GetInstructionFromSsaIndex(idx);
current->GetLiveInterval()->AddLoopRange(block->GetLifetimeStart(), last_position);
}
@@ -289,26 +289,41 @@ void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() {
}
bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) {
- BitVector* live_out = GetLiveOutSet(block);
+ BitVectorView<size_t> live_out = GetLiveOutSet(block);
bool changed = false;
// The live_out set of a block is the union of live_in sets of its successors.
for (HBasicBlock* successor : block.GetSuccessors()) {
- if (live_out->Union(GetLiveInSet(*successor))) {
+ if (live_out.Union(GetLiveInSet(*successor))) {
changed = true;
}
}
return changed;
}
-
bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) {
- BitVector* live_out = GetLiveOutSet(block);
- BitVector* kill = GetKillSet(block);
- BitVector* live_in = GetLiveInSet(block);
+ BitVectorView<size_t> live_out = GetLiveOutSet(block);
+ BitVectorView<size_t> kill = GetKillSet(block);
+ BitVectorView<size_t> live_in = GetLiveInSet(block);
// If live_out is updated (because of backward branches), we need to make
// sure instructions in live_out are also in live_in, unless they are killed
// by this block.
- return live_in->UnionIfNotIn(live_out, kill);
+ return live_in.UnionIfNotIn(live_out, kill);
+}
+
+void SsaLivenessAnalysis::DoCheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const {
+ DCHECK(block.IsLoopHeader());
+ DCHECK(block.GetLoopInformation()->IsIrreducible());
+ BitVectorView<size_t> live_in = GetLiveInSet(block);
+ // To satisfy our liveness algorithm, we need to ensure loop headers of
+ // irreducible loops do not have any live-in instructions, except constants
+ // and the current method, which can be trivially re-materialized.
+ for (uint32_t idx : live_in.Indexes()) {
+ HInstruction* instruction = GetInstructionFromSsaIndex(idx);
+ DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
+ DCHECK(!instruction->IsParameterValue());
+ DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
+ << instruction->DebugName();
+ }
}
void LiveInterval::DumpWithContext(std::ostream& stream,
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 21b7831f10..5a6ad84915 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -19,7 +19,8 @@
#include <iostream>
-#include "base/bit_vector-inl.h"
+#include "base/arena_bit_vector.h"
+#include "base/bit_vector.h"
#include "base/intrusive_forward_list.h"
#include "base/iteration_range.h"
#include "base/macros.h"
@@ -38,17 +39,20 @@ class BlockInfo : public ArenaObject<kArenaAllocSsaLiveness> {
public:
BlockInfo(ScopedArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
: block_(block),
- live_in_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness),
- live_out_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness),
- kill_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness) {
+ live_in_(ArenaBitVector::CreateFixedSize(
+ allocator, number_of_ssa_values, kArenaAllocSsaLiveness)),
+ live_out_(ArenaBitVector::CreateFixedSize(
+ allocator, number_of_ssa_values, kArenaAllocSsaLiveness)),
+ kill_(ArenaBitVector::CreateFixedSize(
+ allocator, number_of_ssa_values, kArenaAllocSsaLiveness)) {
UNUSED(block_);
}
private:
const HBasicBlock& block_;
- ArenaBitVector live_in_;
- ArenaBitVector live_out_;
- ArenaBitVector kill_;
+ BitVectorView<size_t> live_in_;
+ BitVectorView<size_t> live_out_;
+ BitVectorView<size_t> kill_;
friend class SsaLivenessAnalysis;
@@ -1185,16 +1189,16 @@ class SsaLivenessAnalysis : public ValueObject {
void Analyze();
- BitVector* GetLiveInSet(const HBasicBlock& block) const {
- return &block_infos_[block.GetBlockId()]->live_in_;
+ BitVectorView<size_t> GetLiveInSet(const HBasicBlock& block) const {
+ return block_infos_[block.GetBlockId()]->live_in_;
}
- BitVector* GetLiveOutSet(const HBasicBlock& block) const {
- return &block_infos_[block.GetBlockId()]->live_out_;
+ BitVectorView<size_t> GetLiveOutSet(const HBasicBlock& block) const {
+ return block_infos_[block.GetBlockId()]->live_out_;
}
- BitVector* GetKillSet(const HBasicBlock& block) const {
- return &block_infos_[block.GetBlockId()]->kill_;
+ BitVectorView<size_t> GetKillSet(const HBasicBlock& block) const {
+ return block_infos_[block.GetBlockId()]->kill_;
}
HInstruction* GetInstructionFromSsaIndex(size_t index) const {
@@ -1267,10 +1271,10 @@ class SsaLivenessAnalysis : public ValueObject {
static void ProcessEnvironment(HInstruction* instruction,
HInstruction* actual_user,
- BitVector* live_in);
+ BitVectorView<size_t> live_in);
static void RecursivelyProcessInputs(HInstruction* instruction,
HInstruction* actual_user,
- BitVector* live_in);
+ BitVectorView<size_t> live_in);
// Returns whether `instruction` in an HEnvironment held by `env_holder`
// should be kept live by the HEnvironment.
@@ -1295,19 +1299,11 @@ class SsaLivenessAnalysis : public ValueObject {
if (!block.IsLoopHeader() || !block.GetLoopInformation()->IsIrreducible()) {
return;
}
- BitVector* live_in = GetLiveInSet(block);
- // To satisfy our liveness algorithm, we need to ensure loop headers of
- // irreducible loops do not have any live-in instructions, except constants
- // and the current method, which can be trivially re-materialized.
- for (uint32_t idx : live_in->Indexes()) {
- HInstruction* instruction = GetInstructionFromSsaIndex(idx);
- DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName();
- DCHECK(!instruction->IsParameterValue());
- DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant())
- << instruction->DebugName();
- }
+ DoCheckNoLiveInIrreducibleLoop(block);
}
+ void DoCheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const;
+
HGraph* const graph_;
CodeGenerator* const codegen_;
diff --git a/libartbase/base/bit_vector-inl.h b/libartbase/base/bit_vector-inl.h
index dd9071df5c..60d905717c 100644
--- a/libartbase/base/bit_vector-inl.h
+++ b/libartbase/base/bit_vector-inl.h
@@ -51,6 +51,39 @@ inline void BitVectorView<StorageType>::SetInitialBits(uint32_t num_bits) {
}
template <typename StorageType>
+inline bool BitVectorView<StorageType>::Union(BitVectorView<const StorageType> union_with) {
+ DCHECK_EQ(SizeInBits(), union_with.SizeInBits());
+ DCheckTrailingBitsClear();
+ union_with.DCheckTrailingBitsClear();
+ StorageType added_bits = 0u;
+ for (size_t i = 0, size = SizeInWords(); i != size; ++i) {
+ StorageType word = storage_[i];
+ StorageType union_with_word = union_with.storage_[i];
+ storage_[i] = union_with_word | word;
+ added_bits |= union_with_word & ~word;
+ }
+ return added_bits != 0u;
+}
+
+template <typename StorageType>
+inline bool BitVectorView<StorageType>::UnionIfNotIn(BitVectorView<const StorageType> union_with,
+ BitVectorView<const StorageType> not_in) {
+ DCHECK_EQ(SizeInBits(), union_with.SizeInBits());
+ DCHECK_EQ(SizeInBits(), not_in.SizeInBits());
+ DCheckTrailingBitsClear();
+ union_with.DCheckTrailingBitsClear();
+ not_in.DCheckTrailingBitsClear();
+ StorageType added_bits = 0u;
+ for (size_t i = 0, size = SizeInWords(); i != size; ++i) {
+ StorageType word = storage_[i];
+ StorageType union_with_word = union_with.storage_[i] & ~not_in.storage_[i];
+ storage_[i] = union_with_word | word;
+ added_bits |= union_with_word & ~word;
+ }
+ return added_bits != 0u;
+}
+
+template <typename StorageType>
inline bool BitVectorIndexIterator<StorageType>::operator==(
const BitVectorIndexIterator<StorageType>& other) const {
DCHECK_EQ(bit_vector_view_.storage_, other.bit_vector_view_.storage_);
diff --git a/libartbase/base/bit_vector.h b/libartbase/base/bit_vector.h
index 56a8f0f612..369f9171a2 100644
--- a/libartbase/base/bit_vector.h
+++ b/libartbase/base/bit_vector.h
@@ -112,6 +112,13 @@ class BitVectorView {
return std::any_of(storage_, storage_ + SizeInWords(), [](WordType w) { return w != 0u; });
}
+ // Union with another bit vector view of the same size.
+ bool Union(BitVectorView<const StorageType> union_with);
+
+ // Union with the bits in `union_with` but not in `not_in`. All views must have the same size.
+ bool UnionIfNotIn(BitVectorView<const StorageType> union_with,
+ BitVectorView<const StorageType> not_in);
+
// `BitVectorView` wrapper class for iteration across indexes of set bits.
class IndexContainerImpl;
using IndexContainer = BitVectorView<const StorageType>::IndexContainerImpl;
diff --git a/libartbase/base/bit_vector_test.cc b/libartbase/base/bit_vector_test.cc
index d846b8403f..33a8aac873 100644
--- a/libartbase/base/bit_vector_test.cc
+++ b/libartbase/base/bit_vector_test.cc
@@ -228,6 +228,128 @@ TEST(BitVectorView, IndexesSizeT) {
static_cast<size_t>(UINT64_C(0x1234567890abcdef))>();
}
+template <typename StorageType>
+void TestBitVectorViewUnion() {
+ // Truncated if the constants do not fit in `StorageType`.
+ static constexpr StorageType kInitWord0 = static_cast<StorageType>(UINT64_C(0xfedcba0987654321));
+ static constexpr StorageType kInitWord1 = static_cast<StorageType>(UINT64_C(0x1234567890abcdef));
+ StorageType storage[] = { kInitWord0, kInitWord1 };
+ size_t size = 2u * BitSizeOf<StorageType>();
+ BitVectorView<StorageType> bvv(storage, size);
+
+ StorageType equal_storage[] = { kInitWord0, kInitWord1 };
+ BitVectorView<StorageType> equal_bvv(equal_storage, size);
+ ASSERT_FALSE(bvv.Union(equal_bvv));
+ ASSERT_EQ(kInitWord0, storage[0]);
+ ASSERT_EQ(kInitWord1, storage[1]);
+
+ StorageType mask = static_cast<StorageType>(UINT64_C(0x5555555555555555));
+ StorageType subset_storage[] = { kInitWord0 & mask, kInitWord1 & mask };
+ BitVectorView<StorageType> subset_bvv(subset_storage, size);
+ ASSERT_FALSE(bvv.Union(subset_bvv));
+ ASSERT_EQ(kInitWord0, storage[0]);
+ ASSERT_EQ(kInitWord1, storage[1]);
+
+ static constexpr StorageType kOtherWord0 = kInitWord1;
+ static constexpr StorageType kOtherWord1 = kInitWord0;
+ StorageType other_storage[] = { kOtherWord0, kOtherWord1 };
+ BitVectorView<StorageType> other_bvv(other_storage, size);
+ ASSERT_TRUE(bvv.Union(other_bvv));
+ ASSERT_EQ(kInitWord0 | kOtherWord0, storage[0]);
+ ASSERT_EQ(kInitWord1 | kOtherWord1, storage[1]);
+}
+
+TEST(BitVectorView, UnionUint32T) {
+ TestBitVectorViewUnion<uint32_t>();
+}
+
+TEST(BitVectorView, UnionUint64T) {
+ TestBitVectorViewUnion<uint64_t>();
+}
+
+TEST(BitVectorView, UnionSizeT) {
+ // Note: The constants below are truncated on 32-bit architectures.
+ TestBitVectorViewUnion<size_t>();
+}
+
+template <typename StorageType>
+void TestBitVectorViewUnionIfNotIn() {
+ // Truncated if the constants do not fit in `StorageType`.
+ static constexpr StorageType kInitWord0 = static_cast<StorageType>(UINT64_C(0xfedcba0987654321));
+ static constexpr StorageType kInitWord1 = static_cast<StorageType>(UINT64_C(0x1234567890abcdef));
+ StorageType storage[] = { kInitWord0, kInitWord1 };
+ size_t size = 2u * BitSizeOf<StorageType>();
+ BitVectorView<StorageType> bvv(storage, size);
+ StorageType equal_storage[] = { kInitWord0, kInitWord1 };
+ BitVectorView<StorageType> equal_bvv(equal_storage, size);
+ StorageType mask = static_cast<StorageType>(UINT64_C(0x5555555555555555));
+ StorageType subset_storage[] = { kInitWord0 & mask, kInitWord1 & mask };
+ BitVectorView<StorageType> subset_bvv(subset_storage, size);
+ StorageType empty_storage[] = { 0u, 0u };
+ BitVectorView<StorageType> empty_bvv(subset_storage, size);
+ static constexpr StorageType kOtherWord0 = kInitWord1;
+ static constexpr StorageType kOtherWord1 = kInitWord0;
+ StorageType other_storage[] = { kOtherWord0, kOtherWord1 };
+ BitVectorView<StorageType> other_bvv(other_storage, size);
+ StorageType mask_storage[] = { mask, mask };
+ BitVectorView<StorageType> mask_bvv(mask_storage, size);
+
+ // Test cases where we add bits and the `not_in` is relevant.
+ ASSERT_TRUE(bvv.UnionIfNotIn(other_bvv, mask_bvv));
+ ASSERT_EQ(kInitWord0 | (kOtherWord0 & ~mask), storage[0]);
+ ASSERT_EQ(kInitWord1 | (kOtherWord1 & ~mask), storage[1]);
+ storage[0] = kInitWord0; // Reset `bvv` storage.
+ storage[1] = kInitWord1;
+ ASSERT_TRUE(bvv.UnionIfNotIn(mask_bvv, other_bvv));
+ ASSERT_EQ(kInitWord0 | (mask & ~kOtherWord0), storage[0]);
+ ASSERT_EQ(kInitWord1 | (mask & ~kOtherWord1), storage[1]);
+ storage[0] = kInitWord0; // Reset `bvv` storage.
+ storage[1] = kInitWord1;
+
+ // Test cases where we add bits but the `not_in` is irrelevant because it's a subset of `bvv`.
+ for (BitVectorView<StorageType> not_in : { equal_bvv, subset_bvv, empty_bvv }) {
+ ASSERT_TRUE(bvv.UnionIfNotIn(other_bvv, not_in));
+ ASSERT_EQ(kInitWord0 | kOtherWord0, storage[0]);
+ ASSERT_EQ(kInitWord1 | kOtherWord1, storage[1]);
+ storage[0] = kInitWord0; // Reset `bvv` storage.
+ storage[1] = kInitWord1;
+ ASSERT_TRUE(bvv.UnionIfNotIn(mask_bvv, not_in));
+ ASSERT_EQ(kInitWord0 | mask, storage[0]);
+ ASSERT_EQ(kInitWord1 | mask, storage[1]);
+ storage[0] = kInitWord0; // Reset `bvv` storage.
+ storage[1] = kInitWord1;
+ }
+
+ // Test various cases where we add no bits.
+ for (BitVectorView<StorageType> union_with : { equal_bvv, subset_bvv, empty_bvv }) {
+ for (BitVectorView<StorageType> not_in :
+ { equal_bvv, subset_bvv, empty_bvv, other_bvv, mask_bvv }) {
+ ASSERT_FALSE(bvv.UnionIfNotIn(union_with, not_in));
+ ASSERT_EQ(kInitWord0, storage[0]);
+ ASSERT_EQ(kInitWord1, storage[1]);
+ }
+ }
+ ASSERT_FALSE(bvv.UnionIfNotIn(other_bvv, other_bvv));
+ ASSERT_EQ(kInitWord0, storage[0]);
+ ASSERT_EQ(kInitWord1, storage[1]);
+ ASSERT_FALSE(bvv.UnionIfNotIn(mask_bvv, mask_bvv));
+ ASSERT_EQ(kInitWord0, storage[0]);
+ ASSERT_EQ(kInitWord1, storage[1]);
+}
+
+TEST(BitVectorView, UnionIfNotInUint32T) {
+ TestBitVectorViewUnionIfNotIn<uint32_t>();
+}
+
+TEST(BitVectorView, UnionIfNotInUint64T) {
+ TestBitVectorViewUnionIfNotIn<uint64_t>();
+}
+
+TEST(BitVectorView, UnionIfNotInSizeT) {
+ // Note: The constants below are truncated on 32-bit architectures.
+ TestBitVectorViewUnionIfNotIn<size_t>();
+}
+
TEST(BitVector, Test) {
const size_t kBits = 32;
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-20 05:58:56 +0000