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

[courbet]

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.

[courbet]

[gchatelet]

tools/llvm-exegesis/lib/Analysis.cpp

178 ↗

(On Diff #149481)

Can you assert(!Clusters.empty());

305 ↗

(On Diff #149481)

Can you assert(!Clustering.getPoints().empty());?

314 ↗

(On Diff #149481)

I would just return an error here and not let the user think the tool ran correctly.

337 ↗

(On Diff #149481)

Add an error msg

476 ↗

(On Diff #149481)

Can you create variables for SchedClassAndPoints.first and SchedClassAndPoints.second?

tools/llvm-exegesis/lib/Analysis.h

45 ↗

(On Diff #149481)

line feed

63 ↗

(On Diff #149481)

doc?

72 ↗

(On Diff #149481)

Put the definition out of the declaration?

107 ↗

(On Diff #149481)

What is this doc for?

[courbet]

• Address review comments
• Implement latency matching.

[courbet]

Thanks PTAL.

tools/llvm-exegesis/lib/Analysis.cpp

314 ↗

(On Diff #149481)

Even better: implement it ! :)

[courbet]

rebase

[courbet]

more doc

[courbet]

more review comments

llvm/trunk/tools/llvm-exegesis/lib/Analysis.h

 #define LLVM_TOOLS_LLVM_EXEGESIS_ANALYSIS_H
 
 #include "Clustering.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/MC/MCSubtargetInfo.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
+#include <set>
 #include <string>
 #include <unordered_map>
 
 namespace exegesis {
 
 // A helper class to analyze benchmark results for a target.
 class Analysis {
 public:
   Analysis(const llvm::Target &Target,
            const InstructionBenchmarkClustering &Clustering);
 
   // Prints a csv of instructions for each cluster.
   struct PrintClusters {};
   // Find potential errors in the scheduling information given measurements.
   struct PrintSchedClassInconsistencies {};
 
   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,
+  void printSchedClassDescHtml(const SchedClass &SC,
                                llvm::raw_ostream &OS) const;
 
   // Builds a map of Sched Class -> indices of points that belong to the sched
   // class.
   std::unordered_map<unsigned, std::vector<size_t>>
   makePointsPerSchedClass() const;
 
   const InstructionBenchmarkClustering &Clustering_;

llvm/trunk/tools/llvm-exegesis/lib/Analysis.cpp

if (OpcodeIt == MnemonicToOpcode_.end())
       continue;
     const unsigned SchedClassId =
         InstrInfo_->get(OpcodeIt->second).getSchedClass();
     PointsPerSchedClass[SchedClassId].push_back(PointId);
   }
   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,
   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);
     else
       writeEscaped<kEscapeHtml>(OS, Measurement.DebugString);
     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\">[";
       writeMeasurementValue<kEscapeHtml>(OS, Stats.min());
       OS << ";";
       writeMeasurementValue<kEscapeHtml>(OS, Stats.max());
       OS << "]</span></td>";
     }
if (ProcResDesc->SubUnitsIdxBegin == nullptr) {
            ++SubResIdx) {
         ProcResUnitUsage[*SubResIdx] += RemainingCycles / ProcResDesc->NumUnits;
       }
     }
   }
   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 << ")";
       }
       OS << "</li>";
     }
     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);
       OS << "</span>: " << WPR.Cycles << "</li>";
     }
     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)
                                         ->Name);
       OS << "</span>: ";
       writeMeasurementValue<kEscapeHtml>(OS, Pressure.second);
       OS << "</li>";
     }
table.sched-class-desc td {
   padding-left: 10px;
   padding-right: 10px;
   padding-top: 2px;
   padding-bottom: 2px;
 }
 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>
 )";
 
 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>";
   }
 
   OS << "</body></html>";
   return llvm::Error::success();
 }
 
 // Distributes a pressure budget as evenly as possible on the provided subunits

llvm/trunk/tools/llvm-exegesis/lib/BenchmarkResult.h

public:
 
   double avg() const {
     assert(NumValues);
     return SumValues / NumValues;
   }
   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;
   int NumValues = 0;
   double MaxValue = std::numeric_limits<double>::min();
   double MinValue = std::numeric_limits<double>::max();
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_BENCHMARKRESULT_H

llvm/trunk/tools/llvm-exegesis/lib/Clustering.h

public:
   static llvm::Expected<InstructionBenchmarkClustering>
   create(const std::vector<InstructionBenchmark> &Points, size_t MinPts,
          double Epsilon);
 
   class ClusterId {
   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; }
     bool isNoise() const { return Id_ == kNoise; }
     bool isError() const { return Id_ == kError; }
 
     // Precondition: isValid().
     size_t getId() const {
       assert(isValid());
       return Id_;
     }
 
   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;
     size_t Id_;
   };
 
   struct Cluster {
     Cluster() = delete;
const Cluster &getCluster(ClusterId Id) const {
     if (Id.isError()) {
       return ErrorCluster_;
     }
     return Clusters_[Id.getId()];
   }
 
   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_;
   std::vector<Cluster> Clusters_;
   Cluster NoiseCluster_;
   Cluster ErrorCluster_;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H

llvm/trunk/tools/llvm-exegesis/lib/Clustering.cpp

 // k-means and makes algorithms such as DBSCAN[1] or OPTICS[2] more applicable.
 //
 // We've used DBSCAN here because it's simple to implement. This is a pretty
 // straightforward and inefficient implementation of the pseudocode in [2].
 //
 // [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());
   // Mark erroneous measurements out.
   // All points must have the same number of dimensions, in the same order.
   const std::vector<BenchmarkMeasure> *LastMeasurement = nullptr;
   for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     const auto &Point = Points_[P];
for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     LastMeasurement = CurMeasurement;
   }
   if (LastMeasurement) {
     NumDimensions_ = LastMeasurement->size();
   }
   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.
       ClusterIdForPoint_[P] = ClusterId::noise();
       continue;
     }
 
     // Create a new cluster, add P.
while (!ToProcess.empty()) {
       }
       if (!ClusterIdForPoint_[Q].isUndef()) {
         continue; // Previously processed.
       }
       // Add Q to the current custer.
       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());
       }
     }
   }
 
   // Add noisy points to noise cluster.
   for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
     if (ClusterIdForPoint_[P].isNoise()) {
       NoiseCluster_.PointIndices.push_back(P);
     }
   }
 }
 
 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);
   }
   if (Clustering.ErrorCluster_.PointIndices.size() == Points.size()) {
     return Clustering; // Nothing to cluster.
   }
 
-  Clustering.dbScan(MinPts, Epsilon * Epsilon);
+  Clustering.dbScan(MinPts);
   return Clustering;
 }
 
 } // namespace exegesis