Index: tools/llvm-exegesis/lib/BitVectorVector.h
===================================================================
--- /dev/null
+++ tools/llvm-exegesis/lib/BitVectorVector.h
@@ -0,0 +1,102 @@
+//===- BitVectorVector.h - BitVector plus Vector ----------------*- 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 BitVectorVector, that is much like a SetVector,
+// but uses BitVector instead of a Set.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_EXEGESIS_BITVECTORVECTOR_H
+#define LLVM_TOOLS_LLVM_EXEGESIS_BITVECTORVECTOR_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Compiler.h"
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <vector>
+
+namespace llvm {
+namespace exegesis {
+
+template <typename T, typename Vector = std::vector<T>,
+          typename BitVector = BitVector>
+class BitVectorVector {
+public:
+  using value_type = T;
+  using key_type = T;
+  using reference = T &;
+  using const_reference = const T &;
+  using bitvector_type = BitVector;
+  using vector_type = Vector;
+  using iterator = typename vector_type::const_iterator;
+  using const_iterator = typename vector_type::const_iterator;
+  using reverse_iterator = typename vector_type::const_reverse_iterator;
+  using const_reverse_iterator = typename vector_type::const_reverse_iterator;
+  using size_type = typename vector_type::size_type;
+
+  /// Construct an empty BitVectorVector
+  BitVectorVector() = default;
+
+  /// Construct an empty BitVectorVector with size Size.
+  BitVectorVector(size_t Size) : bitvector_(Size), vector_(Size) {}
+
+  /// Determine if the BitVectorVector is empty or not.
+  bool empty() const { return vector_.empty(); }
+
+  /// Get an iterator to the beginning of the BitVectorVector.
+  iterator begin() { return vector_.begin(); }
+
+  /// Get a const_iterator to the beginning of the BitVectorVector.
+  const_iterator begin() const { return vector_.begin(); }
+
+  /// Insert a range of elements into the BitVectorVector.
+  template <typename It> void insert(It Start, It End) {
+    for (; Start != End; ++Start) {
+      if (bitvector_.test(*Start))
+        continue;
+      bitvector_.set(*Start);
+      vector_.push_back(*Start);
+    }
+  }
+
+  /// Erase a single element from the bitvector vector.
+  /// \returns an iterator pointing to the next element that followed the
+  /// element erased. This is the end of the BitVectorVector if the last element
+  /// is erased.
+  iterator erase(iterator I) {
+    const key_type &V = *I;
+    assert(bitvector_.test(V) && "Corrupted BitVectorVector instances!");
+    bitvector_.reset(V);
+
+    // FIXME: No need to use the non-const iterator when built with
+    // std:vector.erase(const_iterator) as defined in C++11. This is for
+    // compatibility with non-standard libstdc++ up to 4.8 (fixed in 4.9).
+    auto NI = vector_.begin();
+    std::advance(NI, std::distance<iterator>(NI, I));
+
+    return vector_.erase(NI);
+  }
+
+  /// Completely clear the BitVectorVector
+  void clear() {
+    bitvector_.reset();
+    vector_.clear();
+  }
+
+private:
+  bitvector_type bitvector_; ///< The bitvector.
+  vector_type vector_;       ///< The vector.
+};
+
+} // end namespace exegesis
+} // end namespace llvm
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_BITVECTORVECTOR_H
Index: tools/llvm-exegesis/lib/Clustering.cpp
===================================================================
--- tools/llvm-exegesis/lib/Clustering.cpp
+++ tools/llvm-exegesis/lib/Clustering.cpp
@@ -8,7 +8,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "Clustering.h"
-#include "llvm/ADT/SetVector.h"
+#include "BitVectorVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include <string>
 
@@ -93,6 +93,7 @@
 
 void InstructionBenchmarkClustering::dbScan(const size_t MinPts) {
   std::vector<size_t> Neighbors; // Persistent buffer to avoid allocs.
+  BitVectorVector<size_t, std::deque<size_t>> ToProcess(Points_.size());
   for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     if (!ClusterIdForPoint_[P].isUndef())
       continue; // Previously processed in inner loop.
@@ -111,7 +112,7 @@
     CurrentCluster.PointIndices.push_back(P);
 
     // Process P's neighbors.
-    llvm::SetVector<size_t, std::deque<size_t>> ToProcess;
+    ToProcess.clear();
     ToProcess.insert(Neighbors.begin(), Neighbors.end());
     while (!ToProcess.empty()) {
       // Retrieve a point from the set.