From 2566e0498cdfb5aaa4f69a549be49d1122b3e863 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Fri, 7 Jun 2013 14:14:38 +0000 Subject: [PATCH] Optimize BitVector::all(). llvm-svn: 183521 --- llvm/include/llvm/ADT/BitVector.h | 12 ++++++++++-- llvm/unittests/ADT/BitVectorTest.cpp | 8 ++++++++ 2 files changed, 18 insertions(+), 2 deletions(-) diff --git a/llvm/include/llvm/ADT/BitVector.h b/llvm/include/llvm/ADT/BitVector.h index 3789db4e45d3..8f512f5c2ca6 100644 --- a/llvm/include/llvm/ADT/BitVector.h +++ b/llvm/include/llvm/ADT/BitVector.h @@ -138,8 +138,16 @@ public: /// all - Returns true if all bits are set. bool all() const { - // TODO: Optimize this. - return count() == size(); + if (empty()) + return true; + + for (unsigned i = 0; i < NumBitWords(size()) - 1; ++i) + if (Bits[i] != ~0UL) + return false; + + // For the last word check that the lower bits are ones. The unused bits are + // always zero. + return Bits[NumBitWords(size()) - 1] == ~(~0UL << (Size % BITWORD_SIZE)); } /// none - Returns true if none of the bits are set. diff --git a/llvm/unittests/ADT/BitVectorTest.cpp b/llvm/unittests/ADT/BitVectorTest.cpp index dc298a83d571..f97be22fd275 100644 --- a/llvm/unittests/ADT/BitVectorTest.cpp +++ b/llvm/unittests/ADT/BitVectorTest.cpp @@ -141,6 +141,14 @@ TYPED_TEST(BitVectorTest, TrivialOperation) { EXPECT_TRUE(Vec.none()); EXPECT_FALSE(Vec.empty()); + Vec.flip(); + EXPECT_EQ(130U, Vec.count()); + EXPECT_EQ(130U, Vec.size()); + EXPECT_TRUE(Vec.any()); + EXPECT_TRUE(Vec.all()); + EXPECT_FALSE(Vec.none()); + EXPECT_FALSE(Vec.empty()); + Inv = TypeParam().flip(); EXPECT_EQ(0U, Inv.count()); EXPECT_EQ(0U, Inv.size()); -- 2.34.1