[ADT][BitVector] Add push_back()

[RKSimon]

Summary

Add a higher performance alternative to calling resize() every time which performs a lot of clearing to zero - when we're adding a single bit most of the time this will be completely unnecessary.

Converting CodeGenDAGPatterns::GenerateVariants() to use this saves 10secs in debug builds of x86 -gen-dag-isel

[vsk]

LGTM. As this is somewhat fundamental change another +1 would be nice.

[zturner]

lgtm as well

llvm/trunk/include/llvm/ADT/BitVector.h

bool operator[](unsigned Idx) const {
     BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
     return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
   }
 
   bool test(unsigned Idx) const {
     return (*this)[Idx];
   }
 
+  // Push single bit to end of vector.
+  void push_back(bool Val) {
+    unsigned OldSize = Size;
+    unsigned NewSize = Size + 1;
+
+    // Resize, which will insert zeros.
+    // If we already fit then the unused bits will be already zero.
+    if (NewSize > getBitCapacity())
+      resize(NewSize, false);
+    else
+      Size = NewSize;
+
+    // If true, set single bit.
+    if (Val)
+      set(OldSize);
+  }
+
   /// 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;

llvm/trunk/include/llvm/ADT/SmallBitVector.h

if (isSmall())
       return ((getSmallBits() >> Idx) & 1) != 0;
     return getPointer()->operator[](Idx);
   }
 
   bool test(unsigned Idx) const {
     return (*this)[Idx];
   }
 
+  // Push single bit to end of vector.
+  void push_back(bool Val) {
+    resize(size() + 1, Val);
+  }
+
   /// Test if any common bits are set.
   bool anyCommon(const SmallBitVector &RHS) const {
     if (isSmall() && RHS.isSmall())
       return (getSmallBits() & RHS.getSmallBits()) != 0;
     if (!isSmall() && !RHS.isSmall())
       return getPointer()->anyCommon(*RHS.getPointer());
 
     for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)

llvm/trunk/unittests/ADT/BitVectorTest.cpp

TYPED_TEST(BitVectorTest, Iterators) {
 
   const unsigned List[] = {1, 10, 25, 99};
   for (unsigned Num : List)
     ToFill.set(Num);
   unsigned i = 0;
   for (unsigned Bit : ToFill.set_bits())
     EXPECT_EQ(List[i++], Bit);
 }
+
+TYPED_TEST(BitVectorTest, PushBack) {
+  TypeParam Vec(10, false);
+  EXPECT_EQ(-1, Vec.find_first());
+  EXPECT_EQ(10, Vec.size());
+  EXPECT_EQ(0, Vec.count());
+
+  Vec.push_back(true);
+  EXPECT_EQ(10, Vec.find_first());
+  EXPECT_EQ(11, Vec.size());
+  EXPECT_EQ(1, Vec.count());
+
+  Vec.push_back(false);
+  EXPECT_EQ(10, Vec.find_first());
+  EXPECT_EQ(12, Vec.size());
+  EXPECT_EQ(1, Vec.count());
+
+  Vec.push_back(true);
+  EXPECT_EQ(10, Vec.find_first());
+  EXPECT_EQ(13, Vec.size());
+  EXPECT_EQ(2, Vec.count());
+
+  // Add a lot of values to cause reallocation.
+  for (int i = 0; i != 100; ++i) {
+    Vec.push_back(true);
+    Vec.push_back(false);
+  }
+  EXPECT_EQ(10, Vec.find_first());
+  EXPECT_EQ(213, Vec.size());
+  EXPECT_EQ(102, Vec.count());
+}
 }
 #endif