From 03a3811ab48139f45cf47f1168788e630af0d40b Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Mon, 14 May 2012 15:01:19 +0000 Subject: [PATCH] Add BitVector::anyCommon(). The existing operation (A & B).any() is very slow. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@156760 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/BitVector.h | 10 ++++++++++ unittests/ADT/BitVectorTest.cpp | 30 +++++++++++++++++++++++++++++- 2 files changed, 39 insertions(+), 1 deletion(-) diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h index 7e0b5ba3719..bf6d76fbcc3 100644 --- a/include/llvm/ADT/BitVector.h +++ b/include/llvm/ADT/BitVector.h @@ -272,6 +272,16 @@ public: return (*this)[Idx]; } + /// Test if any common bits are set. + bool anyCommon(const BitVector &RHS) const { + unsigned ThisWords = NumBitWords(size()); + unsigned RHSWords = NumBitWords(RHS.size()); + for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i) + if (Bits[i] & RHS.Bits[i]) + return true; + return false; + } + // Comparison operators. bool operator==(const BitVector &RHS) const { unsigned ThisWords = NumBitWords(size()); diff --git a/unittests/ADT/BitVectorTest.cpp b/unittests/ADT/BitVectorTest.cpp index f733e13fdfc..24ce3dd22a2 100644 --- a/unittests/ADT/BitVectorTest.cpp +++ b/unittests/ADT/BitVectorTest.cpp @@ -242,6 +242,34 @@ TEST(BitVectorTest, PortableBitMask) { A.clearBitsNotInMask(Mask1, 1); EXPECT_EQ(64-4u, A.count()); } -} +TEST(BitVectorTest, BinOps) { + BitVector A; + BitVector B; + + A.resize(65); + EXPECT_FALSE(A.anyCommon(B)); + EXPECT_FALSE(B.anyCommon(B)); + + B.resize(64); + A.set(64); + EXPECT_FALSE(A.anyCommon(B)); + EXPECT_FALSE(B.anyCommon(A)); + + B.set(63); + EXPECT_FALSE(A.anyCommon(B)); + EXPECT_FALSE(B.anyCommon(A)); + + A.set(63); + EXPECT_TRUE(A.anyCommon(B)); + EXPECT_TRUE(B.anyCommon(A)); + + B.resize(70); + B.set(64); + B.reset(63); + A.resize(64); + EXPECT_FALSE(A.anyCommon(B)); + EXPECT_FALSE(B.anyCommon(A)); +} +} #endif -- 2.34.1