Optimize BitVector::all().

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183521 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 18 insertions, 2 deletions

diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h
index 3789db4e45..8f512f5c2c 100644
--- a/include/llvm/ADT/BitVector.h
+++ b/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/unittests/ADT/BitVectorTest.cpp b/unittests/ADT/BitVectorTest.cpp
index dc298a83d5..f97be22fd2 100644
--- a/unittests/ADT/BitVectorTest.cpp
+++ b/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());