Index: llvm/trunk/include/llvm/ADT/BitVector.h
===================================================================
--- llvm/trunk/include/llvm/ADT/BitVector.h
+++ llvm/trunk/include/llvm/ADT/BitVector.h
@@ -161,6 +161,17 @@
     return -1;
   }
 
+  /// find_first_unset - Returns the index of the first unset bit, -1 if all
+  /// of the bits are set.
+  int find_first_unset() const {
+    for (unsigned i = 0; i < NumBitWords(size()); ++i)
+      if (Bits[i] != ~0UL) {
+        unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Bits[i]);
+        return Result < size() ? Result : -1;
+      }
+    return -1;
+  }
+
   /// find_next - Returns the index of the next set bit following the
   /// "Prev" bit. Returns -1 if the next set bit is not found.
   int find_next(unsigned Prev) const {
@@ -184,6 +195,30 @@
     return -1;
   }
 
+  /// find_next_unset - Returns the index of the next usnet bit following the
+  /// "Prev" bit.  Returns -1 if all remaining bits are set.
+  int find_next_unset(unsigned Prev) const {
+    ++Prev;
+    if (Prev >= Size)
+      return -1;
+
+    unsigned WordPos = Prev / BITWORD_SIZE;
+    unsigned BitPos = Prev % BITWORD_SIZE;
+    BitWord Copy = Bits[WordPos];
+    // Mask in previous bits.
+    BitWord Mask = (1 << BitPos) - 1;
+    Copy |= Mask;
+
+    if (Copy != ~0UL)
+      return next_unset_in_word(WordPos, Copy);
+
+    // Check subsequent words.
+    for (unsigned i = WordPos + 1; i < NumBitWords(size()); ++i)
+      if (Bits[i] != ~0UL)
+        return next_unset_in_word(i, Bits[i]);
+    return -1;
+  }
+
   /// clear - Clear all bits.
   void clear() {
     Size = 0;
@@ -503,6 +538,11 @@
   }
 
 private:
+  int next_unset_in_word(int WordIndex, BitWord Word) const {
+    unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
+    return Result < size() ? Result : -1;
+  }
+
   unsigned NumBitWords(unsigned S) const {
     return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
   }
Index: llvm/trunk/include/llvm/ADT/SmallBitVector.h
===================================================================
--- llvm/trunk/include/llvm/ADT/SmallBitVector.h
+++ llvm/trunk/include/llvm/ADT/SmallBitVector.h
@@ -216,6 +216,18 @@
     return getPointer()->find_first();
   }
 
+  /// Returns the index of the first unset bit, -1 if all of the bits are set.
+  int find_first_unset() const {
+    if (isSmall()) {
+      if (count() == getSmallSize())
+        return -1;
+
+      uintptr_t Bits = getSmallBits();
+      return countTrailingOnes(Bits);
+    }
+    return getPointer()->find_first_unset();
+  }
+
   /// Returns the index of the next set bit following the "Prev" bit.
   /// Returns -1 if the next set bit is not found.
   int find_next(unsigned Prev) const {
@@ -230,6 +242,23 @@
     return getPointer()->find_next(Prev);
   }
 
+  /// Returns the index of the next unset bit following the "Prev" bit.
+  /// Returns -1 if the next unset bit is not found.
+  int find_next_unset(unsigned Prev) const {
+    if (isSmall()) {
+      ++Prev;
+      uintptr_t Bits = getSmallBits();
+      // Mask in previous bits.
+      uintptr_t Mask = (1 << Prev) - 1;
+      Bits |= Mask;
+
+      if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
+        return -1;
+      return countTrailingOnes(Bits);
+    }
+    return getPointer()->find_next_unset(Prev);
+  }
+
   /// Clear all bits.
   void clear() {
     if (!isSmall())
Index: llvm/trunk/unittests/ADT/BitVectorTest.cpp
===================================================================
--- llvm/trunk/unittests/ADT/BitVectorTest.cpp
+++ llvm/trunk/unittests/ADT/BitVectorTest.cpp
@@ -182,6 +182,45 @@
   EXPECT_TRUE(Vec.empty());
 }
 
+TYPED_TEST(BitVectorTest, FindOperations) {
+  // Test finding in an empty BitVector.
+  TypeParam A;
+  EXPECT_EQ(-1, A.find_first());
+  EXPECT_EQ(-1, A.find_first_unset());
+  EXPECT_EQ(-1, A.find_next(0));
+  EXPECT_EQ(-1, A.find_next_unset(0));
+
+  // Test finding next set and unset bits in a BitVector with multiple words
+  A.resize(100);
+  A.set(12);
+  A.set(13);
+  A.set(75);
+
+  EXPECT_EQ(12, A.find_first());
+  EXPECT_EQ(13, A.find_next(12));
+  EXPECT_EQ(75, A.find_next(13));
+  EXPECT_EQ(-1, A.find_next(75));
+
+  EXPECT_EQ(0, A.find_first_unset());
+  EXPECT_EQ(14, A.find_next_unset(11));
+  EXPECT_EQ(14, A.find_next_unset(12));
+  EXPECT_EQ(14, A.find_next_unset(13));
+  EXPECT_EQ(16, A.find_next_unset(15));
+  EXPECT_EQ(76, A.find_next_unset(74));
+  EXPECT_EQ(76, A.find_next_unset(75));
+  EXPECT_EQ(-1, A.find_next_unset(99));
+
+  A.set(0, 100);
+  EXPECT_EQ(100, A.count());
+  EXPECT_EQ(0, A.find_first());
+  EXPECT_EQ(-1, A.find_first_unset());
+
+  A.reset(0, 100);
+  EXPECT_EQ(0, A.count());
+  EXPECT_EQ(-1, A.find_first());
+  EXPECT_EQ(0, A.find_first_unset());
+}
+
 TYPED_TEST(BitVectorTest, CompoundAssignment) {
   TypeParam A;
   A.resize(10);