Index: include/llvm/ADT/SetVector.h
===================================================================
--- include/llvm/ADT/SetVector.h
+++ include/llvm/ADT/SetVector.h
@@ -52,6 +52,13 @@
   /// \brief Construct an empty SetVector
   SetVector() {}
 
+  /// \brief Construct en empty SetVector given instances of the underlying
+  /// vector and set.
+  SetVector(Vector &&NewVector, Set &&NewSet)
+      : set_(std::move(NewSet)), vector_(std::move(NewVector)) {
+    assert(set_.empty() && vector_.empty() && "Expect empty set/vector.");
+  }
+
   /// \brief Initialize a SetVector with a range of elements
   template<typename It>
   SetVector(It Start, It End) {
@@ -116,6 +123,12 @@
     return vector_.back();
   }
 
+  /// Return the first element of the SetVector.
+  const T &front() const {
+    assert(!empty() && "Cannot call front() on empty SetVector!");
+    return vector_.front();
+  }
+
   /// \brief Index into the SetVector.
   const_reference operator[](size_type n) const {
     assert(n < vector_.size() && "SetVector access out of range!");
@@ -218,6 +231,20 @@
     return Ret;
   }
 
+  /// \brief Remove the first element of the SetVector, only available if the
+  /// underlying vector type supports the pop_front() operation.
+  void pop_front() {
+    assert(!empty() && "Cannot remove an element from an empty SetVector!");
+    set_.erase(front());
+    vector_.pop_front();
+  }
+
+  T LLVM_ATTRIBUTE_UNUSED_RESULT pop_front_val() {
+    T Ret = front();
+    pop_front();
+    return Ret;
+  }
+
   bool operator==(const SetVector &that) const {
     return vector_ == that.vector_;
   }
Index: unittests/ADT/SetVectorTest.cpp
===================================================================
--- unittests/ADT/SetVectorTest.cpp
+++ unittests/ADT/SetVectorTest.cpp
@@ -11,11 +11,126 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include <iterator>
+#include <deque>
 #include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/BitSet.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
+template<typename T> void BasicTest(T &X) {
+  EXPECT_EQ(X.size(), 0u);
+  EXPECT_TRUE(X.empty());
+
+  EXPECT_TRUE(X.insert(8));
+  EXPECT_TRUE(X.insert(0));
+  EXPECT_TRUE(X.insert(7));
+  EXPECT_FALSE(X.insert(0));
+  EXPECT_FALSE(X.insert(8));
+  EXPECT_TRUE(X.insert(9));
+  EXPECT_FALSE(X.insert(7));
+
+  EXPECT_EQ(X.size(), 4u);
+  EXPECT_FALSE(X.empty());
+
+  EXPECT_EQ(X.count(7), 1u);
+  EXPECT_EQ(X.count(8), 1u);
+  EXPECT_EQ(X.count(0), 1u);
+  EXPECT_EQ(X.count(9), 1u);
+  EXPECT_EQ(X.count(3), 0u);
+  EXPECT_EQ(X.count(12), 0u);
+
+  static unsigned const NElements = 4;
+  static int long const Elements[NElements] = { 8, 0, 7, 9 };
+  typename T::iterator I = X.begin();
+  typename T::reverse_iterator R = X.rbegin();
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(*I, Elements[E]);
+    EXPECT_EQ(*R, Elements[NElements - 1 - E]);
+    EXPECT_EQ(X[E], Elements[E]);
+    typename T::iterator P = I;
+    ++I;
+    EXPECT_EQ(std::next(P), I);
+    EXPECT_EQ(std::prev(I), P);
+
+    typename T::reverse_iterator RP = R;
+    ++R;
+    EXPECT_EQ(std::next(RP), R);
+    EXPECT_EQ(std::prev(R), RP);
+  }
+  EXPECT_EQ(I, X.end());
+  EXPECT_EQ(R, X.rend());
+
+  EXPECT_TRUE(X.front() == 8);
+  EXPECT_TRUE(X.back() == 9);
+
+  T Y = X;
+  T Z = X;
+  X.clear();
+
+  EXPECT_EQ(X.begin(), X.end());
+  EXPECT_EQ(X.rbegin(), X.rend());
+  EXPECT_TRUE(X.empty());
+  EXPECT_EQ(X.size(), 0u);
+
+  EXPECT_EQ(Y.size(), 4u);
+  EXPECT_FALSE(Y.empty());
+
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(Y.back(), Elements[NElements - 1 - E]);
+    Y.pop_back();
+    EXPECT_EQ(Y.size(), NElements - E - 1);
+
+    EXPECT_EQ(Z.pop_back_val(), Elements[NElements - 1 - E]);
+    EXPECT_EQ(Z.size(), NElements - E - 1);
+  }
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(Y.count(Elements[E]), 0u);
+    EXPECT_EQ(Z.count(Elements[E]), 0u);
+  }
+  EXPECT_TRUE(Y.empty());
+  EXPECT_TRUE(Z.empty());
+}
+
+TEST(SetVector, BasicTestLongLongDefault) {
+  SetVector<long long> X;
+  BasicTest(X);
+}
+
+TEST(SetVector, BasicTestDoubleEndedQueueBitSet) {
+  SetVector<unsigned, std::deque<unsigned>, BitSet> X(std::deque<unsigned>(),
+                                                      BitSet(13));
+  BasicTest(X);
+}
+
+TEST(SetVector, PopFront) {
+  SetVector<unsigned, std::deque<unsigned>, BitSet> X(std::deque<unsigned>(),
+                                                      BitSet(83));
+
+  static unsigned const NElements = 4;
+  static int long const Elements[NElements] = { 8, 0, 7, 9 };
+  for (unsigned E = 0; E < NElements; ++E)
+    X.insert(Elements[E]);
+
+  auto Y = X;
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(X.front(), Elements[E]);
+    X.pop_front();
+    EXPECT_EQ(X.size(), NElements - E - 1);
+
+    EXPECT_EQ(Y.pop_front_val(), Elements[E]);
+    EXPECT_EQ(Y.size(), NElements - E - 1);
+  }
+  for (unsigned E = 0; E < NElements; ++E) {
+    EXPECT_EQ(X.count(Elements[E]), 0u);
+    EXPECT_EQ(Y.count(Elements[E]), 0u);
+  }
+  EXPECT_TRUE(X.empty());
+  EXPECT_TRUE(Y.empty());
+}
+
 TEST(SetVector, EraseTest) {
   SetVector<int> S;
   S.insert(0);
@@ -31,4 +146,3 @@
   EXPECT_EQ(0, *S.begin());
   EXPECT_EQ(2, *std::next(S.begin()));
 }
-