Index: include/llvm/ADT/BitSet.h
===================================================================
--- /dev/null
+++ include/llvm/ADT/BitSet.h
@@ -0,0 +1,149 @@
+//===- llvm/ADT/BitSet.h - Bit sets -----------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file.
+/// This file implements the BitSet class, a set for unsigned numbers backed
+/// by a BitVector.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_BITSET_H
+#define LLVM_ADT_BITSET_H
+
+namespace llvm {
+
+/// A set of unsigned numbers smaller than a previously given maximum. The set
+/// internally uses a BitVector for storage.
+template<typename BitVectorT>
+class BitSetBase {
+public:
+  typedef unsigned key_type;
+  typedef unsigned value_type;
+  typedef typename BitVectorT::size_type size_type;
+
+  class const_iterator
+  {
+  public:
+    const_iterator(const const_iterator&) = default;
+
+    const_iterator &operator=(const const_iterator &I) = default;
+
+    unsigned operator*() const { return E; }
+
+    bool operator==(const const_iterator &RHS) const {
+      return E == RHS.E && Vector == RHS.Vector;
+    }
+
+    bool operator !=(const const_iterator &RHS) const {
+      return !(*this == RHS);
+    }
+
+    const_iterator &operator++() {
+      ++E;
+      advance();
+      return *this;
+    }
+
+    const_iterator operator++(int) {
+      unsigned Prev = E;
+      ++E;
+      advance();
+      return const_iterator(Vector, Prev);
+    }
+
+  private:
+    friend class BitSetBase<BitVectorT>;
+    const_iterator(const BitVectorT *Vector, unsigned E)
+      : Vector(Vector), E(E) {
+      advance();
+    }
+
+    void advance() {
+      int next = Vector->find_next_at(E);
+      if (next == -1)
+        E = Vector->size();
+      else
+        E = (unsigned)next;
+    }
+
+    const BitVectorT *Vector;
+    unsigned E;
+  };
+  typedef const_iterator iterator;
+
+  /// Initializes an empty set for values smaller than \p Max.
+  BitSetBase(unsigned Max = 0) : Vector(Max) {}
+
+  /// Returns true if the set contains no elements.
+  bool empty() const { return Vector.none(); }
+
+  /// Returns the number of elements in the set.
+  size_type size() const { return Vector.count(); }
+
+  /// Change the size of the underlying bitvector so the set can hold elements
+  /// smaller than \p Max. Removes elements bigger than \p Max from the set.
+  void reserve(unsigned Max) { Vector.resize(Max); }
+
+  /// Removes all elements from the set.
+  void clear() { Vector.reset(); }
+
+  /// Returns iterator to first element in set or end() if set is empty.
+  const_iterator begin() const {
+    return const_iterator(&Vector);
+  }
+
+  /// Returns iterator pointing past the last element of the set.
+  const_iterator end() const {
+    return const_iterator(&Vector, Vector.size());
+  }
+
+  /// Insert element \p Idx into the set. \p Idx must be smaller than the number
+  /// used in the last reserve() or constructor call.
+  std::pair<iterator, bool> insert(unsigned Idx) {
+    bool Res = !Vector[Idx];
+    Vector[Idx] = true;
+    return std::make_pair(iterator(&Vector, Idx), Res);
+  }
+
+  /// Remove element \p Idx from the set. \p Idx must be smaller than the number
+  /// used in the last reserve() or constructor call. Does nothing if \p Idx is
+  /// not contained in the set.
+  size_type erase(unsigned Idx) {
+    size_type Res = Vector[Idx];
+    Vector[Idx] = false;
+    return Res;
+  }
+
+  /// Remove element pointed to by iterator \p I. Returns iterator to the
+  /// element following the removed element or end().
+  iterator erase(iterator I) {
+    iterator Res = I;
+    Vector[*I] = false;
+    return ++Res;
+  }
+
+  /// Returns 1 if \p Idx is contained in the set, 0 otherwise. \p Idx must be
+  /// smaller than the number used in the last reserve() or constructor call.
+  size_type count(unsigned Idx) const {
+    return Vector.test(Idx);
+  }
+
+private:
+  BitVectorT Vector;
+};
+
+class BitVector;
+typedef BitSetBase<BitVector> BitSet;
+
+class SmallBitVector;
+typedef BitSetBase<SmallBitVector> SmallBitSet;
+
+} // End llvm namespace
+
+#endif
Index: include/llvm/ADT/BitVector.h
===================================================================
--- include/llvm/ADT/BitVector.h
+++ include/llvm/ADT/BitVector.h
@@ -160,15 +160,14 @@
     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 {
-    ++Prev;
-    if (Prev >= Size)
+  /// Returns the index of the next set bit at bit \p Pos or following.
+  /// Returns -1 if the next set bit is not found.
+  int find_next_at(unsigned Pos) const {
+    if (Pos >= Size)
       return -1;
 
-    unsigned WordPos = Prev / BITWORD_SIZE;
-    unsigned BitPos = Prev % BITWORD_SIZE;
+    unsigned WordPos = Pos / BITWORD_SIZE;
+    unsigned BitPos = Pos % BITWORD_SIZE;
     BitWord Copy = Bits[WordPos];
     // Mask off previous bits.
     Copy &= ~0UL << BitPos;
@@ -183,6 +182,12 @@
     return -1;
   }
 
+  /// 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 {
+    return find_next_at(Prev + 1);
+  }
+
   /// clear - Clear all bits.
   void clear() {
     Size = 0;
Index: unittests/ADT/CMakeLists.txt
===================================================================
--- unittests/ADT/CMakeLists.txt
+++ unittests/ADT/CMakeLists.txt
@@ -11,7 +11,6 @@
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
-  DenseSetTest.cpp
   FoldingSet.cpp
   FunctionRefTest.cpp
   HashingTest.cpp
@@ -32,6 +31,7 @@
   PostOrderIteratorTest.cpp
   RangeAdapterTest.cpp
   SCCIteratorTest.cpp
+  SetTest.cpp
   SetVectorTest.cpp
   SmallPtrSetTest.cpp
   SmallStringTest.cpp
Index: unittests/ADT/DenseSetTest.cpp
===================================================================
--- unittests/ADT/DenseSetTest.cpp
+++ /dev/null
@@ -1,68 +0,0 @@
-//===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "gtest/gtest.h"
-#include "llvm/ADT/DenseSet.h"
-
-using namespace llvm;
-
-namespace {
-
-// Test fixture
-class DenseSetTest : public testing::Test {
-};
-
-// Test hashing with a set of only two entries.
-TEST_F(DenseSetTest, DoubleEntrySetTest) {
-  llvm::DenseSet<unsigned> set(2);
-  set.insert(0);
-  set.insert(1);
-  // Original failure was an infinite loop in this call:
-  EXPECT_EQ(0u, set.count(2));
-}
-
-struct TestDenseSetInfo {
-  static inline unsigned getEmptyKey() { return ~0; }
-  static inline unsigned getTombstoneKey() { return ~0U - 1; }
-  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
-  static unsigned getHashValue(const char* Val) {
-    return (unsigned)(Val[0] - 'a') * 37U;
-  }
-  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
-    return LHS == RHS;
-  }
-  static bool isEqual(const char* LHS, const unsigned& RHS) {
-    return (unsigned)(LHS[0] - 'a') == RHS;
-  }
-};
-
-TEST(DenseSetCustomTest, FindAsTest) {
-  DenseSet<unsigned, TestDenseSetInfo> set;
-  set.insert(0);
-  set.insert(1);
-  set.insert(2);
-
-  // Size tests
-  EXPECT_EQ(3u, set.size());
-
-  // Normal lookup tests
-  EXPECT_EQ(1u, set.count(1));
-  EXPECT_EQ(0u, *set.find(0));
-  EXPECT_EQ(1u, *set.find(1));
-  EXPECT_EQ(2u, *set.find(2));
-  EXPECT_TRUE(set.find(3) == set.end());
-
-  // find_as() tests
-  EXPECT_EQ(0u, *set.find_as("a"));
-  EXPECT_EQ(1u, *set.find_as("b"));
-  EXPECT_EQ(2u, *set.find_as("c"));
-  EXPECT_TRUE(set.find_as("d") == set.end());
-}
-
-}
Index: unittests/ADT/SetTest.cpp
===================================================================
--- /dev/null
+++ unittests/ADT/SetTest.cpp
@@ -0,0 +1,202 @@
+//===- llvm/unittest/ADT/DenseSetTest.cpp - DenseSet unit tests --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/SmallBitVector.h"
+#include "llvm/ADT/BitSet.h"
+
+using namespace llvm;
+
+namespace {
+
+// Test hashing with a set of only two entries.
+TEST(SetTest, DoubleEntrySetTest) {
+  llvm::DenseSet<unsigned> set(2);
+  set.insert(0);
+  set.insert(1);
+  // Original failure was an infinite loop in this call:
+  EXPECT_EQ(0u, set.count(2));
+}
+
+template<typename T>
+void testInsertErase(T &X) {
+  EXPECT_EQ(X.size(), 0u);
+  EXPECT_TRUE(X.empty());
+
+  EXPECT_TRUE(X.insert(7).second);
+  EXPECT_EQ(X.size(), 1u);
+  EXPECT_FALSE(X.insert(7).second);
+  EXPECT_EQ(X.size(), 1u);
+  EXPECT_EQ(X.count(7), 1u);
+
+  X.insert(10);
+  EXPECT_FALSE(X.insert(10).second);
+  EXPECT_EQ(X.count(10), 1u);
+  EXPECT_EQ(X.size(), 2u);
+
+  auto P0 = X.insert(12);
+  EXPECT_TRUE(P0.second);
+  EXPECT_EQ(X.count(12), 1u);
+  EXPECT_EQ(*P0.first, 12u);
+  EXPECT_EQ(X.size(), 3u);
+
+  auto P1 = X.insert(10);
+  EXPECT_FALSE(P1.second);
+  EXPECT_EQ(X.count(10), 1u);
+  EXPECT_EQ(*P1.first, 10u);
+  EXPECT_EQ(X.size(), 3u);
+
+  EXPECT_FALSE(X.erase(3));
+  EXPECT_EQ(X.size(), 3u);
+  X.insert(77);
+  EXPECT_TRUE(X.erase(77));
+  EXPECT_EQ(X.size(), 3u);
+  EXPECT_FALSE(X.erase(77));
+  EXPECT_EQ(X.size(), 3u);
+  EXPECT_FALSE(X.empty());
+}
+
+template<typename T>
+void testIterator(T &X) {
+  ASSERT_EQ(X.begin(), X.end());
+
+  X.insert(7);
+  X.insert(3);
+  X.insert(27);
+  X.insert(9);
+
+  bool found7 = false;
+  bool found3 = false;
+  bool found27 = false;
+  bool found9 = false;
+  for (typename T::iterator I = X.begin(); I != X.end(); ++I) {
+    switch (*I) {
+    case 3: ASSERT_FALSE(found3); found3 = true; break;
+    case 7: ASSERT_FALSE(found7); found7 = true; break;
+    case 9: ASSERT_FALSE(found9); found9 = true; break;
+    case 27: ASSERT_FALSE(found27); found27 = true; break;
+    default: ADD_FAILURE(); break;
+    }
+  }
+  ASSERT_TRUE(found3);
+  ASSERT_TRUE(found7);
+  ASSERT_TRUE(found9);
+  ASSERT_TRUE(found27);
+
+  X.clear();
+  ASSERT_EQ(X.begin(), X.end());
+}
+
+template<typename T>
+void testEraseIterator(T &X) {
+  ASSERT_EQ(X.begin(), X.end());
+
+  X.insert(7);
+  X.insert(3);
+  X.insert(27);
+  X.insert(9);
+
+  bool found7 = false;
+  bool found3 = false;
+  bool found27 = false;
+  bool found9 = false;
+  for (typename T::iterator I = X.begin(); I != X.end(); ) {
+    switch (*I) {
+    case 3: ASSERT_FALSE(found3); found3 = true; break;
+    case 7: ASSERT_FALSE(found7); found7 = true; break;
+    case 9: ASSERT_FALSE(found9); found9 = true; break;
+    case 27: ASSERT_FALSE(found27); found27 = true; break;
+    default: ADD_FAILURE(); break;
+    }
+    if (*I == 9)
+      I = X.erase(I);
+    else
+      ++I;
+  }
+  ASSERT_TRUE(found3);
+  ASSERT_TRUE(found7);
+  ASSERT_TRUE(found9);
+  ASSERT_TRUE(found27);
+
+  ASSERT_EQ(X.count(3), 1u);
+  ASSERT_EQ(X.count(7), 1u);
+  ASSERT_EQ(X.count(9), 0u);
+  ASSERT_EQ(X.count(27), 1u);
+  ASSERT_EQ(X.size(), 3u);
+}
+
+struct TestDenseSetInfo {
+  static inline unsigned getEmptyKey() { return ~0; }
+  static inline unsigned getTombstoneKey() { return ~0U - 1; }
+  static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
+  static unsigned getHashValue(const char* Val) {
+    return (unsigned)(Val[0] - 'a') * 37U;
+  }
+  static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
+    return LHS == RHS;
+  }
+  static bool isEqual(const char* LHS, const unsigned& RHS) {
+    return (unsigned)(LHS[0] - 'a') == RHS;
+  }
+};
+
+TEST(SetTest, FindAsTest) {
+  DenseSet<unsigned, TestDenseSetInfo> set;
+  set.insert(0);
+  set.insert(1);
+  set.insert(2);
+
+  // Size tests
+  EXPECT_EQ(3u, set.size());
+
+  // Normal lookup tests
+  EXPECT_EQ(1u, set.count(1));
+  EXPECT_EQ(0u, *set.find(0));
+  EXPECT_EQ(1u, *set.find(1));
+  EXPECT_EQ(2u, *set.find(2));
+  EXPECT_TRUE(set.find(3) == set.end());
+
+  // find_as() tests
+  EXPECT_EQ(0u, *set.find_as("a"));
+  EXPECT_EQ(1u, *set.find_as("b"));
+  EXPECT_EQ(2u, *set.find_as("c"));
+  EXPECT_TRUE(set.find_as("d") == set.end());
+}
+
+TEST(SetTest, InsertEraseDenseSetCustom) {
+  DenseSet<unsigned, TestDenseSetInfo> Set;
+  testInsertErase(Set);
+
+  DenseSet<unsigned, TestDenseSetInfo> Set2;
+  testIterator(Set2);
+}
+
+TEST(SetTest, TestBitSet) {
+  BitSet Set(89);
+  testInsertErase(Set);
+
+  BitSet Set2(29);
+  testIterator(Set2);
+  Set2.clear();
+  testEraseIterator(Set2);
+}
+
+TEST(SetTest, InsertEraseSmallBitSet) {
+  BitSet Set(89);
+  testInsertErase(Set);
+
+  SmallBitSet Set2(29);
+  testIterator(Set2);
+  Set2.clear();
+  testEraseIterator(Set2);
+}
+
+}