Index: include/llvm/ADT/OrderedSet.h
===================================================================
--- /dev/null
+++ include/llvm/ADT/OrderedSet.h
@@ -0,0 +1,85 @@
+//===- OrderedSet.h - Hash table --------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a hash table with constant-time insertion and removal,
+// and iteration in some consistent order across runs. Two copies of each
+// element are kept, one is stored in a std::vector for random access iteration,
+// and one is used as a key in a DenseMap, which contains indexes to the vector.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_ORDEREDSET_H
+#define LLVM_ADT_ORDEREDSET_H
+
+#include "llvm/ADT/DenseMap.h"
+#include <vector>
+
+namespace llvm {
+
+template <class ValueT>
+class OrderedSet {
+  DenseMap<ValueT, size_t> Map;
+  std::vector<ValueT> Vec;
+
+public:
+  using iterator = typename std::vector<ValueT>::iterator;
+
+  // Insert an element in the OrderedSet unless it's already
+  // present. Return a pair indicating its position in the vector
+  // and the whether the insertion happend or not.
+  std::pair<iterator, bool> insert(ValueT value) {
+    auto SetIns = Map.insert(std::make_pair(value, Vec.size()));
+    if (SetIns.second) {
+      Vec.push_back(value);
+      return { Vec.end()-1, true };
+    }
+    return { Vec.begin()+SetIns.first->second, false };
+  }
+
+  // Random access iterators.
+  iterator begin() { return Vec.begin(); }
+  iterator end() { return Vec.end(); }
+
+  // Clear all the entries from the OrderedSet.
+  void clear() {
+    Vec.clear();
+    Map.clear();
+  }
+
+  // Return the size of the underlying container.
+  size_t size() const { return Vec.size(); }
+
+  // Is an element present in the OrderedSet?
+  size_t count(ValueT value) const {
+    return Map.find(value) != Map.end() ? 1 : 0;
+  }
+
+  // Erase an element from the OrderedSet if it's present.
+  // Replace it with the last element of the vector and
+  // update the DenseMap for that entry.
+  bool erase(ValueT value) {
+    auto MapFind = Map.find(value);
+    if (MapFind != Map.end()) {
+      size_t Index = MapFind->second;
+      Map.erase(MapFind);
+      if (Index != Vec.size()-1) {
+        std::swap(Vec[Index], Vec.back());
+        Map.find(Vec[Index])->second = Index;
+      }
+      Vec.pop_back();
+      return true;
+    }
+    return false;
+  }
+
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_ORDEREDSET_H
Index: unittests/ADT/CMakeLists.txt
===================================================================
--- unittests/ADT/CMakeLists.txt
+++ unittests/ADT/CMakeLists.txt
@@ -36,6 +36,7 @@
   MappedIteratorTest.cpp
   MapVectorTest.cpp
   OptionalTest.cpp
+  OrderedSetTest.cpp
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
Index: unittests/ADT/OrderedSetTest.cpp
===================================================================
--- /dev/null
+++ unittests/ADT/OrderedSetTest.cpp
@@ -0,0 +1,95 @@
+//===- unittest/ADT/OrderedSetTest.cpp - OrderedSet 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 "llvm/ADT/OrderedSet.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+TEST(OrderedSetTest, insert) {
+  OrderedSet<unsigned> OS;
+  std::pair<OrderedSet<unsigned>::iterator, bool> R;
+
+  // The element was not present upon insertion.
+  for (unsigned i=0; i<10; ++i) {
+    EXPECT_EQ(OS.count(i), 0u);
+    R = OS.insert(i);
+    ASSERT_EQ(R.first, OS.end()-1);
+    EXPECT_EQ(*R.first, i);
+    EXPECT_TRUE(R.second);
+    ASSERT_EQ(OS.size(), i+1);
+  }
+
+  // The element was already present upon insertion.
+  for (unsigned i=0; i<10; ++i) {
+    EXPECT_EQ(OS.count(i), 1u);
+    R = OS.insert(i);
+    ASSERT_EQ(R.first, OS.begin()+i);
+    EXPECT_EQ(*R.first, i);
+    EXPECT_FALSE(R.second);
+    ASSERT_EQ(OS.size(), 10u);
+  }
+}
+
+TEST(OrderedSetTest, erase) {
+  OrderedSet<unsigned> OS;
+
+  for (unsigned i=0; i<10; ++i)
+    OS.insert(i);
+  ASSERT_EQ(OS.size(), 10u);
+
+  // The element was present upon deletion.
+  for (unsigned i=0; i<10; ++i) {
+    EXPECT_EQ(OS.count(i), 1u);
+    EXPECT_TRUE(OS.erase(i));
+    ASSERT_EQ(OS.size(), (10-i)-1);
+  }
+
+  // The element was not present upon deletion.
+  for (unsigned i=0; i<10; ++i) {
+    EXPECT_EQ(OS.count(i), 0u);
+    EXPECT_FALSE(OS.erase(i));
+    ASSERT_EQ(OS.size(), 0u);
+  }
+}
+
+TEST(OrderedSetTest, iterate) {
+  OrderedSet<unsigned> OS;
+
+  // Insert {0,1,2,3,4,5,6,7,8,9}
+  for (unsigned i=0; i<10; ++i)
+    OS.insert(i);
+  ASSERT_EQ(OS.size(), 10u);
+
+  // The iteration order is same as insertion order
+  // as long as no removals have occured.
+  unsigned count=0;
+  for (auto I : make_range(OS.begin(), OS.end())) {
+    ASSERT_EQ(I, count);
+    ++count;
+  }
+
+  // Removing elements from the OrderedSet can
+  // reposition other elements.
+  for (unsigned i=0; i<5; ++i)
+    EXPECT_TRUE(OS.erase(i));
+  ASSERT_EQ(OS.size(), 5u);
+
+  // The iteration order is now {9,8,7,6,5}
+  count=9;
+  for (auto I : make_range(OS.begin(), OS.end())) {
+    ASSERT_EQ(I, count);
+    --count;
+  }
+
+  // Erase everything.
+  OS.clear();
+  ASSERT_EQ(OS.size(), 0u);
+  ASSERT_EQ(std::distance(OS.begin(), OS.end()), 0u);
+}