[llvm-exegesis] Analysis: Show inconsistencies between checked-in and measured data.

Summary:
We now highlight any sched classes whose measurements do not match the
LLVM SchedModel. "bad" clusters are marked in red.

Screenshot in phabricator diff.

Reviewers: gchatelet

Subscribers: tschuett, mgrang, RKSimon, llvm-commits

Differential Revision: https://reviews.llvm.org/D47639

llvm-svn: 333884

5 files changed, 241 insertions, 93 deletions

diff --git a/llvm/tools/llvm-exegesis/lib/Analysis.cpp b/llvm/tools/llvm-exegesis/lib/Analysis.cpp
index 713c2b7e3fa..0eb9cf20378 100644
--- a/llvm/tools/llvm-exegesis/lib/Analysis.cpp
+++ b/llvm/tools/llvm-exegesis/lib/Analysis.cpp
@@ -168,20 +168,15 @@ Analysis::makePointsPerSchedClass() const {
   return PointsPerSchedClass;
 }
 
-void Analysis::printSchedClassClustersHtml(std::vector<size_t> PointIds,
-                                           llvm::raw_ostream &OS) const {
-  assert(!PointIds.empty());
-  // Sort the points by cluster id so that we can display them grouped by
-  // cluster.
-  llvm::sort(PointIds.begin(), PointIds.end(),
-             [this](const size_t A, const size_t B) {
-               return Clustering_.getClusterIdForPoint(A) <
-                      Clustering_.getClusterIdForPoint(B);
-             });
+void Analysis::printSchedClassClustersHtml(
+    const std::vector<SchedClassCluster> &Clusters, const SchedClass &SC,
+    llvm::raw_ostream &OS) const {
   const auto &Points = Clustering_.getPoints();
   OS << "<table class=\"sched-class-clusters\">";
   OS << "<tr><th>ClusterId</th><th>Opcode/Config</th>";
-  for (const auto &Measurement : Points[PointIds[0]].Measurements) {
+  assert(!Clusters.empty());
+  for (const auto &Measurement :
+       Points[Clusters[0].getPointIds()[0]].Measurements) {
     OS << "<th>";
     if (Measurement.DebugString.empty())
       writeEscaped<kEscapeHtml>(OS, Measurement.Key);
@@ -190,29 +185,24 @@ void Analysis::printSchedClassClustersHtml(std::vector<size_t> PointIds,
     OS << "</th>";
   }
   OS << "</tr>";
-  for (size_t I = 0, E = PointIds.size(); I < E;) {
-    const auto &CurrentClusterId =
-        Clustering_.getClusterIdForPoint(PointIds[I]);
-    OS << "<tr><td>";
-    writeClusterId<kEscapeHtml>(OS, CurrentClusterId);
+  for (const SchedClassCluster &Cluster : Clusters) {
+    OS << "<tr class=\""
+       << (Cluster.measurementsMatch(*SubtargetInfo_, SC, Clustering_)
+               ? "good-cluster"
+               : "bad-cluster")
+       << "\"><td>";
+    writeClusterId<kEscapeHtml>(OS, Cluster.id());
     OS << "</td><td><ul>";
-    std::vector<BenchmarkMeasureStats> MeasurementStats(
-        Points[PointIds[I]].Measurements.size());
-    for (; I < E &&
-           Clustering_.getClusterIdForPoint(PointIds[I]) == CurrentClusterId;
-         ++I) {
-      const auto &Point = Points[PointIds[I]];
+    for (const size_t PointId : Cluster.getPointIds()) {
+      const auto &Point = Points[PointId];
       OS << "<li><span class=\"mono\">";
       writeEscaped<kEscapeHtml>(OS, Point.Key.OpcodeName);
       OS << "</span> <span class=\"mono\">";
       writeEscaped<kEscapeHtml>(OS, Point.Key.Config);
       OS << "</span></li>";
-      for (size_t J = 0, F = Point.Measurements.size(); J < F; ++J) {
-        MeasurementStats[J].push(Point.Measurements[J]);
-      }
     }
     OS << "</ul></td>";
-    for (const auto &Stats : MeasurementStats) {
+    for (const auto &Stats : Cluster.getRepresentative()) {
       OS << "<td class=\"measurement\">";
       writeMeasurementValue<kEscapeHtml>(OS, Stats.avg());
       OS << "<br><span class=\"minmax\">[";
@@ -300,25 +290,101 @@ getNonRedundantWriteProcRes(const llvm::MCSchedClassDesc &SCDesc,
   return Result;
 }
 
-void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
+Analysis::SchedClass::SchedClass(const llvm::MCSchedClassDesc &SD,
+                                 const llvm::MCSubtargetInfo &STI)
+    : SCDesc(SD),
+      NonRedundantWriteProcRes(getNonRedundantWriteProcRes(SD, STI)),
+      IdealizedProcResPressure(computeIdealizedProcResPressure(
+          STI.getSchedModel(), NonRedundantWriteProcRes)) {}
+
+void Analysis::SchedClassCluster::addPoint(
+    size_t PointId, const InstructionBenchmarkClustering &Clustering) {
+  PointIds.push_back(PointId);
+  const auto &Point = Clustering.getPoints()[PointId];
+  if (ClusterId.isUndef()) {
+    ClusterId = Clustering.getClusterIdForPoint(PointId);
+    Representative.resize(Point.Measurements.size());
+  }
+  for (size_t I = 0, E = Point.Measurements.size(); I < E; ++I) {
+    Representative[I].push(Point.Measurements[I]);
+  }
+  assert(ClusterId == Clustering.getClusterIdForPoint(PointId));
+}
+
+bool Analysis::SchedClassCluster::measurementsMatch(
+    const llvm::MCSubtargetInfo &STI, const SchedClass &SC,
+    const InstructionBenchmarkClustering &Clustering) const {
+  const size_t NumMeasurements = Representative.size();
+  std::vector<BenchmarkMeasure> ClusterCenterPoint(NumMeasurements);
+  std::vector<BenchmarkMeasure> SchedClassPoint(NumMeasurements);
+  // Latency case.
+  assert(!Clustering.getPoints().empty());
+  const std::string &Mode = Clustering.getPoints()[0].Key.Mode;
+  if (Mode == "latency") { // FIXME: use an enum.
+    if (NumMeasurements != 1) {
+      llvm::errs()
+          << "invalid number of measurements in latency mode: expected 1, got "
+          << NumMeasurements << "\n";
+      return false;
+    }
+    // Find the latency.
+    SchedClassPoint[0].Value = 0.0;
+    for (unsigned I = 0; I < SC.SCDesc.NumWriteLatencyEntries; ++I) {
+      const llvm::MCWriteLatencyEntry *const WLE =
+          STI.getWriteLatencyEntry(&SC.SCDesc, I);
+      SchedClassPoint[0].Value =
+          std::max<double>(SchedClassPoint[0].Value, WLE->Cycles);
+    }
+    ClusterCenterPoint[0].Value = Representative[0].avg();
+  } else if (Mode == "uops") {
+    for (int I = 0, E = Representative.size(); I < E; ++I) {
+      // Find the pressure on ProcResIdx `Key`.
+      uint16_t ProcResIdx = 0;
+      if (!llvm::to_integer(Representative[I].key(), ProcResIdx, 10)) {
+        llvm::errs() << "expected ProcResIdx key, got "
+                     << Representative[I].key() << "\n";
+        return false;
+      }
+      const auto ProcResPressureIt =
+          std::find_if(SC.IdealizedProcResPressure.begin(),
+                       SC.IdealizedProcResPressure.end(),
+                       [ProcResIdx](const std::pair<uint16_t, float> &WPR) {
+                         return WPR.first == ProcResIdx;
+                       });
+      SchedClassPoint[I].Value =
+          ProcResPressureIt == SC.IdealizedProcResPressure.end()
+              ? 0.0
+              : ProcResPressureIt->second;
+      ClusterCenterPoint[I].Value = Representative[I].avg();
+    }
+  } else {
+    llvm::errs() << "unimplemented measurement matching for mode ''" << Mode
+                 << "''\n";
+    return false;
+  }
+  return Clustering.isNeighbour(ClusterCenterPoint, SchedClassPoint);
+}
+
+void Analysis::printSchedClassDescHtml(const SchedClass &SC,
                                        llvm::raw_ostream &OS) const {
   OS << "<table class=\"sched-class-desc\">";
   OS << "<tr><th>Valid</th><th>Variant</th><th>uOps</th><th>Latency</"
         "th><th>WriteProcRes</th><th title=\"This is the idealized unit "
         "resource (port) pressure assuming ideal distribution\">Idealized "
         "Resource Pressure</th></tr>";
-  if (SCDesc.isValid()) {
+  if (SC.SCDesc.isValid()) {
     const auto &SM = SubtargetInfo_->getSchedModel();
     OS << "<tr><td>&#10004;</td>";
-    OS << "<td>" << (SCDesc.isVariant() ? "&#10004;" : "&#10005;") << "</td>";
-    OS << "<td>" << SCDesc.NumMicroOps << "</td>";
+    OS << "<td>" << (SC.SCDesc.isVariant() ? "&#10004;" : "&#10005;")
+       << "</td>";
+    OS << "<td>" << SC.SCDesc.NumMicroOps << "</td>";
     // Latencies.
     OS << "<td><ul>";
-    for (int I = 0, E = SCDesc.NumWriteLatencyEntries; I < E; ++I) {
+    for (int I = 0, E = SC.SCDesc.NumWriteLatencyEntries; I < E; ++I) {
       const auto *const Entry =
-          SubtargetInfo_->getWriteLatencyEntry(&SCDesc, I);
+          SubtargetInfo_->getWriteLatencyEntry(&SC.SCDesc, I);
       OS << "<li>" << Entry->Cycles;
-      if (SCDesc.NumWriteLatencyEntries > 1) {
+      if (SC.SCDesc.NumWriteLatencyEntries > 1) {
         // Dismabiguate if more than 1 latency.
         OS << " (WriteResourceID " << Entry->WriteResourceID << ")";
       }
@@ -327,8 +393,7 @@ void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
     OS << "</ul></td>";
     // WriteProcRes.
     OS << "<td><ul>";
-    const auto ProcRes = getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_);
-    for (const auto &WPR : ProcRes) {
+    for (const auto &WPR : SC.NonRedundantWriteProcRes) {
       OS << "<li><span class=\"mono\">";
       writeEscaped<kEscapeHtml>(OS,
                                 SM.getProcResource(WPR.ProcResourceIdx)->Name);
@@ -337,7 +402,7 @@ void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
     OS << "</ul></td>";
     // Idealized port pressure.
     OS << "<td><ul>";
-    for (const auto &Pressure : computeIdealizedProcResPressure(SM, ProcRes)) {
+    for (const auto &Pressure : SC.IdealizedProcResPressure) {
       OS << "<li><span class=\"mono\">";
       writeEscaped<kEscapeHtml>(OS, SubtargetInfo_->getSchedModel()
                                         .getProcResource(Pressure.first)
@@ -401,12 +466,21 @@ table.sched-class-desc td {
 span.mono {
   font-family: monospace;
 }
-span.minmax {
-  color: #888;
-}
 td.measurement {
   text-align: center;
 }
+tr.good-cluster td.measurement {
+  color: #292
+}
+tr.bad-cluster td.measurement {
+  color: #922
+}
+tr.good-cluster td.measurement span.minmax {
+  color: #888;
+}
+tr.bad-cluster td.measurement span.minmax {
+  color: #888;
+}
 </style>
 </head>
 )";
@@ -414,46 +488,65 @@ td.measurement {
 template <>
 llvm::Error Analysis::run<Analysis::PrintSchedClassInconsistencies>(
     llvm::raw_ostream &OS) const {
+  const auto &FirstPoint = Clustering_.getPoints()[0];
   // Print the header.
   OS << "<!DOCTYPE html><html>" << kHtmlHead << "<body>";
   OS << "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>";
   OS << "<h3>Triple: <span class=\"mono\">";
-  writeEscaped<kEscapeHtml>(OS, Clustering_.getPoints()[0].LLVMTriple);
+  writeEscaped<kEscapeHtml>(OS, FirstPoint.LLVMTriple);
   OS << "</span></h3><h3>Cpu: <span class=\"mono\">";
-  writeEscaped<kEscapeHtml>(OS, Clustering_.getPoints()[0].CpuName);
+  writeEscaped<kEscapeHtml>(OS, FirstPoint.CpuName);
   OS << "</span></h3>";
 
-  // All the points in a scheduling class should be in the same cluster.
-  // Print any scheduling class for which this is not the case.
   for (const auto &SchedClassAndPoints : makePointsPerSchedClass()) {
-    std::unordered_set<size_t> ClustersForSchedClass;
-    for (const size_t PointId : SchedClassAndPoints.second) {
+    const auto SchedClassId = SchedClassAndPoints.first;
+    const std::vector<size_t> &SchedClassPoints = SchedClassAndPoints.second;
+    const auto &SchedModel = SubtargetInfo_->getSchedModel();
+    const llvm::MCSchedClassDesc *const SCDesc =
+        SchedModel.getSchedClassDesc(SchedClassId);
+    if (!SCDesc)
+      continue;
+    const SchedClass SC(*SCDesc, *SubtargetInfo_);
+
+    // Bucket sched class points into sched class clusters.
+    std::vector<SchedClassCluster> SchedClassClusters;
+    for (const size_t PointId : SchedClassPoints) {
       const auto &ClusterId = Clustering_.getClusterIdForPoint(PointId);
       if (!ClusterId.isValid())
-        continue; // Ignore noise and errors.
-      ClustersForSchedClass.insert(ClusterId.getId());
+        continue; // Ignore noise and errors. FIXME: take noise into account ?
+      auto SchedClassClusterIt =
+          std::find_if(SchedClassClusters.begin(), SchedClassClusters.end(),
+                       [ClusterId](const SchedClassCluster &C) {
+                         return C.id() == ClusterId;
+                       });
+      if (SchedClassClusterIt == SchedClassClusters.end()) {
+        SchedClassClusters.emplace_back();
+        SchedClassClusterIt = std::prev(SchedClassClusters.end());
+      }
+      SchedClassClusterIt->addPoint(PointId, Clustering_);
     }
-    if (ClustersForSchedClass.size() <= 1)
+
+    // Print any scheduling class that has at least one cluster that does not
+    // match the checked-in data.
+    if (std::all_of(SchedClassClusters.begin(), SchedClassClusters.end(),
+                    [this, &SC](const SchedClassCluster &C) {
+                      return C.measurementsMatch(*SubtargetInfo_, SC,
+                                                 Clustering_);
+                    }))
       continue; // Nothing weird.
 
-    const auto &SchedModel = SubtargetInfo_->getSchedModel();
-    const llvm::MCSchedClassDesc *const SCDesc =
-        SchedModel.getSchedClassDesc(SchedClassAndPoints.first);
-    if (!SCDesc)
-      continue;
     OS << "<div class=\"inconsistency\"><p>Sched Class <span "
           "class=\"sched-class-name\">";
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     writeEscaped<kEscapeHtml>(OS, SCDesc->Name);
 #else
-    OS << SchedClassAndPoints.first;
+    OS << SchedClassId;
 #endif
-    OS << "</span> contains instructions with distinct performance "
-          "characteristics, falling into "
-       << ClustersForSchedClass.size() << " clusters:</p>";
-    printSchedClassClustersHtml(SchedClassAndPoints.second, OS);
-    OS << "<p>llvm data:</p>";
-    printSchedClassDescHtml(*SCDesc, OS);
+    OS << "</span> contains instructions whose performance characteristics do"
+          " not match that of LLVM:</p>";
+    printSchedClassClustersHtml(SchedClassClusters, SC, OS);
+    OS << "<p>llvm SchedModel data:</p>";
+    printSchedClassDescHtml(SC, OS);
     OS << "</div>";
   }
 
diff --git a/llvm/tools/llvm-exegesis/lib/Analysis.h b/llvm/tools/llvm-exegesis/lib/Analysis.h
index 36110076a12..c6218052fae 100644
--- a/llvm/tools/llvm-exegesis/lib/Analysis.h
+++ b/llvm/tools/llvm-exegesis/lib/Analysis.h
@@ -21,6 +21,7 @@
 #include "llvm/Support/Error.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
+#include <set>
 #include <string>
 #include <unordered_map>
 
@@ -40,11 +41,55 @@ public:
   template <typename Pass> llvm::Error run(llvm::raw_ostream &OS) const;
 
 private:
+  using ClusterId = InstructionBenchmarkClustering::ClusterId;
+
+  // An llvm::MCSchedClassDesc augmented with some additional data.
+  struct SchedClass {
+    SchedClass(const llvm::MCSchedClassDesc &SD,
+               const llvm::MCSubtargetInfo &STI);
+
+    const llvm::MCSchedClassDesc &SCDesc;
+    const llvm::SmallVector<llvm::MCWriteProcResEntry, 8>
+        NonRedundantWriteProcRes;
+    const std::vector<std::pair<uint16_t, float>> IdealizedProcResPressure;
+  };
+
+  // Represents the intersection of a sched class and a cluster.
+  class SchedClassCluster {
+  public:
+    const InstructionBenchmarkClustering::ClusterId &id() const {
+      return ClusterId;
+    }
+
+    const std::vector<size_t> &getPointIds() const { return PointIds; }
+
+    // Return the cluster centroid.
+    const std::vector<BenchmarkMeasureStats> &getRepresentative() const {
+      return Representative;
+    }
+
+    // Returns true if the cluster representative measurements match that of SC.
+    bool
+    measurementsMatch(const llvm::MCSubtargetInfo &STI, const SchedClass &SC,
+                      const InstructionBenchmarkClustering &Clustering) const;
+
+    void addPoint(size_t PointId,
+                  const InstructionBenchmarkClustering &Clustering);
+
+  private:
+    InstructionBenchmarkClustering::ClusterId ClusterId;
+    std::vector<size_t> PointIds;
+    // Measurement stats for the points in the SchedClassCluster.
+    std::vector<BenchmarkMeasureStats> Representative;
+  };
+
   void printInstructionRowCsv(size_t PointId, llvm::raw_ostream &OS) const;
 
-  void printSchedClassClustersHtml(std::vector<size_t> PointIds,
-                                   llvm::raw_ostream &OS) const;
-  void printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
+  void
+  printSchedClassClustersHtml(const std::vector<SchedClassCluster> &Clusters,
+                              const SchedClass &SC,
+                              llvm::raw_ostream &OS) const;
+  void printSchedClassDescHtml(const SchedClass &SC,
                                llvm::raw_ostream &OS) const;
 
   // Builds a map of Sched Class -> indices of points that belong to the sched
diff --git a/llvm/tools/llvm-exegesis/lib/BenchmarkResult.h b/llvm/tools/llvm-exegesis/lib/BenchmarkResult.h
index 4362df86df6..41d631eca4b 100644
--- a/llvm/tools/llvm-exegesis/lib/BenchmarkResult.h
+++ b/llvm/tools/llvm-exegesis/lib/BenchmarkResult.h
@@ -77,6 +77,8 @@ public:
   double min() const { return MinValue; }
   double max() const { return MaxValue; }
 
+  const std::string &key() const { return Key; }
+
 private:
   std::string Key;
   double SumValues = 0.0;
diff --git a/llvm/tools/llvm-exegesis/lib/Clustering.cpp b/llvm/tools/llvm-exegesis/lib/Clustering.cpp
index acd2276260b..a966c722a78 100644
--- a/llvm/tools/llvm-exegesis/lib/Clustering.cpp
+++ b/llvm/tools/llvm-exegesis/lib/Clustering.cpp
@@ -29,38 +29,41 @@ namespace exegesis {
 // [1] https://en.wikipedia.org/wiki/DBSCAN
 // [2] https://en.wikipedia.org/wiki/OPTICS_algorithm
 
-namespace {
-
 // Finds the points at distance less than sqrt(EpsilonSquared) of Q (not
 // including Q).
-std::vector<size_t> rangeQuery(const std::vector<InstructionBenchmark> &Points,
-                               const size_t Q, const double EpsilonSquared) {
+std::vector<size_t>
+InstructionBenchmarkClustering::rangeQuery(const size_t Q) const {
   std::vector<size_t> Neighbors;
-  const auto &QMeasurements = Points[Q].Measurements;
-  for (size_t P = 0, NumPoints = Points.size(); P < NumPoints; ++P) {
+  const auto &QMeasurements = Points_[Q].Measurements;
+  for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     if (P == Q)
       continue;
-    const auto &PMeasurements = Points[P].Measurements;
+    const auto &PMeasurements = Points_[P].Measurements;
     if (PMeasurements.empty()) // Error point.
       continue;
-    double DistanceSquared = 0;
-    for (size_t I = 0, E = QMeasurements.size(); I < E; ++I) {
-      const auto Diff = PMeasurements[I].Value - QMeasurements[I].Value;
-      DistanceSquared += Diff * Diff;
-    }
-    if (DistanceSquared <= EpsilonSquared) {
+    if (isNeighbour(PMeasurements, QMeasurements)) {
       Neighbors.push_back(P);
     }
   }
   return Neighbors;
 }
 
-} // namespace
+bool InstructionBenchmarkClustering::isNeighbour(
+    const std::vector<BenchmarkMeasure> &P,
+    const std::vector<BenchmarkMeasure> &Q) const {
+  double DistanceSquared = 0.0;
+  for (size_t I = 0, E = P.size(); I < E; ++I) {
+    const auto Diff = P[I].Value - Q[I].Value;
+    DistanceSquared += Diff * Diff;
+  }
+  return DistanceSquared <= EpsilonSquared_;
+}
 
 InstructionBenchmarkClustering::InstructionBenchmarkClustering(
-    const std::vector<InstructionBenchmark> &Points)
-    : Points_(Points), NoiseCluster_(ClusterId::noise()),
-      ErrorCluster_(ClusterId::error()) {}
+    const std::vector<InstructionBenchmark> &Points,
+    const double EpsilonSquared)
+    : Points_(Points), EpsilonSquared_(EpsilonSquared),
+      NoiseCluster_(ClusterId::noise()), ErrorCluster_(ClusterId::error()) {}
 
 llvm::Error InstructionBenchmarkClustering::validateAndSetup() {
   ClusterIdForPoint_.resize(Points_.size());
@@ -97,12 +100,11 @@ llvm::Error InstructionBenchmarkClustering::validateAndSetup() {
   return llvm::Error::success();
 }
 
-void InstructionBenchmarkClustering::dbScan(const size_t MinPts,
-                                            const double EpsilonSquared) {
+void InstructionBenchmarkClustering::dbScan(const size_t MinPts) {
   for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     if (!ClusterIdForPoint_[P].isUndef())
       continue; // Previously processed in inner loop.
-    const auto Neighbors = rangeQuery(Points_, P, EpsilonSquared);
+    const auto Neighbors = rangeQuery(P);
     if (Neighbors.size() + 1 < MinPts) { // Density check.
       // The region around P is not dense enough to create a new cluster, mark
       // as noise for now.
@@ -136,7 +138,7 @@ void InstructionBenchmarkClustering::dbScan(const size_t MinPts,
       ClusterIdForPoint_[Q] = CurrentCluster.Id;
       CurrentCluster.PointIndices.push_back(Q);
       // And extend to the neighbors of Q if the region is dense enough.
-      const auto Neighbors = rangeQuery(Points_, Q, EpsilonSquared);
+      const auto Neighbors = rangeQuery(Q);
       if (Neighbors.size() + 1 >= MinPts) {
         ToProcess.insert(Neighbors.begin(), Neighbors.end());
       }
@@ -155,7 +157,7 @@ llvm::Expected<InstructionBenchmarkClustering>
 InstructionBenchmarkClustering::create(
     const std::vector<InstructionBenchmark> &Points, const size_t MinPts,
     const double Epsilon) {
-  InstructionBenchmarkClustering Clustering(Points);
+  InstructionBenchmarkClustering Clustering(Points, Epsilon * Epsilon);
   if (auto Error = Clustering.validateAndSetup()) {
     return std::move(Error);
   }
@@ -163,7 +165,7 @@ InstructionBenchmarkClustering::create(
     return Clustering; // Nothing to cluster.
   }
 
-  Clustering.dbScan(MinPts, Epsilon * Epsilon);
+  Clustering.dbScan(MinPts);
   return Clustering;
 }
 
diff --git a/llvm/tools/llvm-exegesis/lib/Clustering.h b/llvm/tools/llvm-exegesis/lib/Clustering.h
index 3d6413d2256..c811020e0fe 100644
--- a/llvm/tools/llvm-exegesis/lib/Clustering.h
+++ b/llvm/tools/llvm-exegesis/lib/Clustering.h
@@ -33,12 +33,10 @@ public:
   public:
     static ClusterId noise() { return ClusterId(kNoise); }
     static ClusterId error() { return ClusterId(kError); }
-    static ClusterId makeValid(size_t Id) {
-      return ClusterId(Id);
-    }
+    static ClusterId makeValid(size_t Id) { return ClusterId(Id); }
     ClusterId() : Id_(kUndef) {}
     bool operator==(const ClusterId &O) const { return Id_ == O.Id_; }
-    bool operator<(const ClusterId &O) const {return Id_ < O.Id_; }
+    bool operator<(const ClusterId &O) const { return Id_ < O.Id_; }
 
     bool isValid() const { return Id_ <= kMaxValid; }
     bool isUndef() const { return Id_ == kUndef; }
@@ -53,7 +51,8 @@ public:
 
   private:
     explicit ClusterId(size_t Id) : Id_(Id) {}
-    static constexpr const size_t kMaxValid = std::numeric_limits<size_t>::max() - 4;
+    static constexpr const size_t kMaxValid =
+        std::numeric_limits<size_t>::max() - 4;
     static constexpr const size_t kNoise = kMaxValid + 1;
     static constexpr const size_t kError = kMaxValid + 2;
     static constexpr const size_t kUndef = kMaxValid + 3;
@@ -88,12 +87,19 @@ public:
 
   const std::vector<Cluster> &getValidClusters() const { return Clusters_; }
 
+  // Returns true if the given point is within a distance Epsilon of each other.
+  bool isNeighbour(const std::vector<BenchmarkMeasure> &P,
+                   const std::vector<BenchmarkMeasure> &Q) const;
+
 private:
   InstructionBenchmarkClustering(
-      const std::vector<InstructionBenchmark> &Points);
+      const std::vector<InstructionBenchmark> &Points, double EpsilonSquared);
   llvm::Error validateAndSetup();
-  void dbScan(size_t MinPts, double EpsilonSquared);
+  void dbScan(size_t MinPts);
+  std::vector<size_t> rangeQuery(size_t Q) const;
+
   const std::vector<InstructionBenchmark> &Points_;
+  const double EpsilonSquared_;
   int NumDimensions_ = 0;
   // ClusterForPoint_[P] is the cluster id for Points[P].
   std::vector<ClusterId> ClusterIdForPoint_;