[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

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

307

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

316

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

339

Add an error msg

501–502

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

tools/llvm-exegesis/lib/Analysis.h

45

line feed

63

doc?

72

Put the definition out of the declaration?

100

What is this doc for?

[courbet]

• Address review comments
• Implement latency matching.

[courbet]

Thanks PTAL.

tools/llvm-exegesis/lib/Analysis.cpp

316

Even better: implement it ! :)

[courbet]

rebase

[courbet]

more doc

[courbet]

more review comments

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;
 
+  // Returns true of the data for this cluster matches the checked-in llvm data
+  // for this class.
+
   const InstructionBenchmarkClustering &Clustering_;
   std::unique_ptr<llvm::MCSubtargetInfo> SubtargetInfo_;
   std::unique_ptr<llvm::MCInstrInfo> InstrInfo_;
   std::unordered_map<std::string, unsigned> MnemonicToOpcode_;
 };
 
 // Computes the idealized ProcRes Unit pressure. This is the expected
 // distribution if the CPU scheduler can distribute the load as evenly as
 // possible.
 std::vector<std::pair<uint16_t, float>> computeIdealizedProcResPressure(
     const llvm::MCSchedModel &SM,
     llvm::SmallVector<llvm::MCWriteProcResEntry, 8> WPRS);
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H

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

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

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

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