Skip to content

Commit 7228721

Browse files
legrosbufflelegrosbuffle
committedJun 4, 2018
[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
·
llvmorg-21-initllvmorg-7.0.0-rc1
1 parent b648087 commit 7228721

File tree

5 files changed

+241
-93
lines changed

5 files changed

+241
-93
lines changed
 

Diff for: ‎llvm/tools/llvm-exegesis/lib/Analysis.cpp

+153-60
Original file line numberDiff line numberDiff line change
@@ -168,20 +168,15 @@ Analysis::makePointsPerSchedClass() const {
168168
return PointsPerSchedClass;
169169
}
170170

171-
void Analysis::printSchedClassClustersHtml(std::vector<size_t> PointIds,
172-
llvm::raw_ostream &OS) const {
173-
assert(!PointIds.empty());
174-
// Sort the points by cluster id so that we can display them grouped by
175-
// cluster.
176-
llvm::sort(PointIds.begin(), PointIds.end(),
177-
[this](const size_t A, const size_t B) {
178-
return Clustering_.getClusterIdForPoint(A) <
179-
Clustering_.getClusterIdForPoint(B);
180-
});
171+
void Analysis::printSchedClassClustersHtml(
172+
const std::vector<SchedClassCluster> &Clusters, const SchedClass &SC,
173+
llvm::raw_ostream &OS) const {
181174
const auto &Points = Clustering_.getPoints();
182175
OS << "<table class=\"sched-class-clusters\">";
183176
OS << "<tr><th>ClusterId</th><th>Opcode/Config</th>";
184-
for (const auto &Measurement : Points[PointIds[0]].Measurements) {
177+
assert(!Clusters.empty());
178+
for (const auto &Measurement :
179+
Points[Clusters[0].getPointIds()[0]].Measurements) {
185180
OS << "<th>";
186181
if (Measurement.DebugString.empty())
187182
writeEscaped<kEscapeHtml>(OS, Measurement.Key);
@@ -190,29 +185,24 @@ void Analysis::printSchedClassClustersHtml(std::vector<size_t> PointIds,
190185
OS << "</th>";
191186
}
192187
OS << "</tr>";
193-
for (size_t I = 0, E = PointIds.size(); I < E;) {
194-
const auto &CurrentClusterId =
195-
Clustering_.getClusterIdForPoint(PointIds[I]);
196-
OS << "<tr><td>";
197-
writeClusterId<kEscapeHtml>(OS, CurrentClusterId);
188+
for (const SchedClassCluster &Cluster : Clusters) {
189+
OS << "<tr class=\""
190+
<< (Cluster.measurementsMatch(*SubtargetInfo_, SC, Clustering_)
191+
? "good-cluster"
192+
: "bad-cluster")
193+
<< "\"><td>";
194+
writeClusterId<kEscapeHtml>(OS, Cluster.id());
198195
OS << "</td><td><ul>";
199-
std::vector<BenchmarkMeasureStats> MeasurementStats(
200-
Points[PointIds[I]].Measurements.size());
201-
for (; I < E &&
202-
Clustering_.getClusterIdForPoint(PointIds[I]) == CurrentClusterId;
203-
++I) {
204-
const auto &Point = Points[PointIds[I]];
196+
for (const size_t PointId : Cluster.getPointIds()) {
197+
const auto &Point = Points[PointId];
205198
OS << "<li><span class=\"mono\">";
206199
writeEscaped<kEscapeHtml>(OS, Point.Key.OpcodeName);
207200
OS << "</span> <span class=\"mono\">";
208201
writeEscaped<kEscapeHtml>(OS, Point.Key.Config);
209202
OS << "</span></li>";
210-
for (size_t J = 0, F = Point.Measurements.size(); J < F; ++J) {
211-
MeasurementStats[J].push(Point.Measurements[J]);
212-
}
213203
}
214204
OS << "</ul></td>";
215-
for (const auto &Stats : MeasurementStats) {
205+
for (const auto &Stats : Cluster.getRepresentative()) {
216206
OS << "<td class=\"measurement\">";
217207
writeMeasurementValue<kEscapeHtml>(OS, Stats.avg());
218208
OS << "<br><span class=\"minmax\">[";
@@ -300,25 +290,101 @@ getNonRedundantWriteProcRes(const llvm::MCSchedClassDesc &SCDesc,
300290
return Result;
301291
}
302292

303-
void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
293+
Analysis::SchedClass::SchedClass(const llvm::MCSchedClassDesc &SD,
294+
const llvm::MCSubtargetInfo &STI)
295+
: SCDesc(SD),
296+
NonRedundantWriteProcRes(getNonRedundantWriteProcRes(SD, STI)),
297+
IdealizedProcResPressure(computeIdealizedProcResPressure(
298+
STI.getSchedModel(), NonRedundantWriteProcRes)) {}
299+
300+
void Analysis::SchedClassCluster::addPoint(
301+
size_t PointId, const InstructionBenchmarkClustering &Clustering) {
302+
PointIds.push_back(PointId);
303+
const auto &Point = Clustering.getPoints()[PointId];
304+
if (ClusterId.isUndef()) {
305+
ClusterId = Clustering.getClusterIdForPoint(PointId);
306+
Representative.resize(Point.Measurements.size());
307+
}
308+
for (size_t I = 0, E = Point.Measurements.size(); I < E; ++I) {
309+
Representative[I].push(Point.Measurements[I]);
310+
}
311+
assert(ClusterId == Clustering.getClusterIdForPoint(PointId));
312+
}
313+
314+
bool Analysis::SchedClassCluster::measurementsMatch(
315+
const llvm::MCSubtargetInfo &STI, const SchedClass &SC,
316+
const InstructionBenchmarkClustering &Clustering) const {
317+
const size_t NumMeasurements = Representative.size();
318+
std::vector<BenchmarkMeasure> ClusterCenterPoint(NumMeasurements);
319+
std::vector<BenchmarkMeasure> SchedClassPoint(NumMeasurements);
320+
// Latency case.
321+
assert(!Clustering.getPoints().empty());
322+
const std::string &Mode = Clustering.getPoints()[0].Key.Mode;
323+
if (Mode == "latency") { // FIXME: use an enum.
324+
if (NumMeasurements != 1) {
325+
llvm::errs()
326+
<< "invalid number of measurements in latency mode: expected 1, got "
327+
<< NumMeasurements << "\n";
328+
return false;
329+
}
330+
// Find the latency.
331+
SchedClassPoint[0].Value = 0.0;
332+
for (unsigned I = 0; I < SC.SCDesc.NumWriteLatencyEntries; ++I) {
333+
const llvm::MCWriteLatencyEntry *const WLE =
334+
STI.getWriteLatencyEntry(&SC.SCDesc, I);
335+
SchedClassPoint[0].Value =
336+
std::max<double>(SchedClassPoint[0].Value, WLE->Cycles);
337+
}
338+
ClusterCenterPoint[0].Value = Representative[0].avg();
339+
} else if (Mode == "uops") {
340+
for (int I = 0, E = Representative.size(); I < E; ++I) {
341+
// Find the pressure on ProcResIdx `Key`.
342+
uint16_t ProcResIdx = 0;
343+
if (!llvm::to_integer(Representative[I].key(), ProcResIdx, 10)) {
344+
llvm::errs() << "expected ProcResIdx key, got "
345+
<< Representative[I].key() << "\n";
346+
return false;
347+
}
348+
const auto ProcResPressureIt =
349+
std::find_if(SC.IdealizedProcResPressure.begin(),
350+
SC.IdealizedProcResPressure.end(),
351+
[ProcResIdx](const std::pair<uint16_t, float> &WPR) {
352+
return WPR.first == ProcResIdx;
353+
});
354+
SchedClassPoint[I].Value =
355+
ProcResPressureIt == SC.IdealizedProcResPressure.end()
356+
? 0.0
357+
: ProcResPressureIt->second;
358+
ClusterCenterPoint[I].Value = Representative[I].avg();
359+
}
360+
} else {
361+
llvm::errs() << "unimplemented measurement matching for mode ''" << Mode
362+
<< "''\n";
363+
return false;
364+
}
365+
return Clustering.isNeighbour(ClusterCenterPoint, SchedClassPoint);
366+
}
367+
368+
void Analysis::printSchedClassDescHtml(const SchedClass &SC,
304369
llvm::raw_ostream &OS) const {
305370
OS << "<table class=\"sched-class-desc\">";
306371
OS << "<tr><th>Valid</th><th>Variant</th><th>uOps</th><th>Latency</"
307372
"th><th>WriteProcRes</th><th title=\"This is the idealized unit "
308373
"resource (port) pressure assuming ideal distribution\">Idealized "
309374
"Resource Pressure</th></tr>";
310-
if (SCDesc.isValid()) {
375+
if (SC.SCDesc.isValid()) {
311376
const auto &SM = SubtargetInfo_->getSchedModel();
312377
OS << "<tr><td>&#10004;</td>";
313-
OS << "<td>" << (SCDesc.isVariant() ? "&#10004;" : "&#10005;") << "</td>";
314-
OS << "<td>" << SCDesc.NumMicroOps << "</td>";
378+
OS << "<td>" << (SC.SCDesc.isVariant() ? "&#10004;" : "&#10005;")
379+
<< "</td>";
380+
OS << "<td>" << SC.SCDesc.NumMicroOps << "</td>";
315381
// Latencies.
316382
OS << "<td><ul>";
317-
for (int I = 0, E = SCDesc.NumWriteLatencyEntries; I < E; ++I) {
383+
for (int I = 0, E = SC.SCDesc.NumWriteLatencyEntries; I < E; ++I) {
318384
const auto *const Entry =
319-
SubtargetInfo_->getWriteLatencyEntry(&SCDesc, I);
385+
SubtargetInfo_->getWriteLatencyEntry(&SC.SCDesc, I);
320386
OS << "<li>" << Entry->Cycles;
321-
if (SCDesc.NumWriteLatencyEntries > 1) {
387+
if (SC.SCDesc.NumWriteLatencyEntries > 1) {
322388
// Dismabiguate if more than 1 latency.
323389
OS << " (WriteResourceID " << Entry->WriteResourceID << ")";
324390
}
@@ -327,8 +393,7 @@ void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
327393
OS << "</ul></td>";
328394
// WriteProcRes.
329395
OS << "<td><ul>";
330-
const auto ProcRes = getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_);
331-
for (const auto &WPR : ProcRes) {
396+
for (const auto &WPR : SC.NonRedundantWriteProcRes) {
332397
OS << "<li><span class=\"mono\">";
333398
writeEscaped<kEscapeHtml>(OS,
334399
SM.getProcResource(WPR.ProcResourceIdx)->Name);
@@ -337,7 +402,7 @@ void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
337402
OS << "</ul></td>";
338403
// Idealized port pressure.
339404
OS << "<td><ul>";
340-
for (const auto &Pressure : computeIdealizedProcResPressure(SM, ProcRes)) {
405+
for (const auto &Pressure : SC.IdealizedProcResPressure) {
341406
OS << "<li><span class=\"mono\">";
342407
writeEscaped<kEscapeHtml>(OS, SubtargetInfo_->getSchedModel()
343408
.getProcResource(Pressure.first)
@@ -401,59 +466,87 @@ table.sched-class-desc td {
401466
span.mono {
402467
font-family: monospace;
403468
}
404-
span.minmax {
405-
color: #888;
406-
}
407469
td.measurement {
408470
text-align: center;
409471
}
472+
tr.good-cluster td.measurement {
473+
color: #292
474+
}
475+
tr.bad-cluster td.measurement {
476+
color: #922
477+
}
478+
tr.good-cluster td.measurement span.minmax {
479+
color: #888;
480+
}
481+
tr.bad-cluster td.measurement span.minmax {
482+
color: #888;
483+
}
410484
</style>
411485
</head>
412486
)";
413487

414488
template <>
415489
llvm::Error Analysis::run<Analysis::PrintSchedClassInconsistencies>(
416490
llvm::raw_ostream &OS) const {
491+
const auto &FirstPoint = Clustering_.getPoints()[0];
417492
// Print the header.
418493
OS << "<!DOCTYPE html><html>" << kHtmlHead << "<body>";
419494
OS << "<h1><span class=\"mono\">llvm-exegesis</span> Analysis Results</h1>";
420495
OS << "<h3>Triple: <span class=\"mono\">";
421-
writeEscaped<kEscapeHtml>(OS, Clustering_.getPoints()[0].LLVMTriple);
496+
writeEscaped<kEscapeHtml>(OS, FirstPoint.LLVMTriple);
422497
OS << "</span></h3><h3>Cpu: <span class=\"mono\">";
423-
writeEscaped<kEscapeHtml>(OS, Clustering_.getPoints()[0].CpuName);
498+
writeEscaped<kEscapeHtml>(OS, FirstPoint.CpuName);
424499
OS << "</span></h3>";
425500

426-
// All the points in a scheduling class should be in the same cluster.
427-
// Print any scheduling class for which this is not the case.
428501
for (const auto &SchedClassAndPoints : makePointsPerSchedClass()) {
429-
std::unordered_set<size_t> ClustersForSchedClass;
430-
for (const size_t PointId : SchedClassAndPoints.second) {
502+
const auto SchedClassId = SchedClassAndPoints.first;
503+
const std::vector<size_t> &SchedClassPoints = SchedClassAndPoints.second;
504+
const auto &SchedModel = SubtargetInfo_->getSchedModel();
505+
const llvm::MCSchedClassDesc *const SCDesc =
506+
SchedModel.getSchedClassDesc(SchedClassId);
507+
if (!SCDesc)
508+
continue;
509+
const SchedClass SC(*SCDesc, *SubtargetInfo_);
510+
511+
// Bucket sched class points into sched class clusters.
512+
std::vector<SchedClassCluster> SchedClassClusters;
513+
for (const size_t PointId : SchedClassPoints) {
431514
const auto &ClusterId = Clustering_.getClusterIdForPoint(PointId);
432515
if (!ClusterId.isValid())
433-
continue; // Ignore noise and errors.
434-
ClustersForSchedClass.insert(ClusterId.getId());
516+
continue; // Ignore noise and errors. FIXME: take noise into account ?
517+
auto SchedClassClusterIt =
518+
std::find_if(SchedClassClusters.begin(), SchedClassClusters.end(),
519+
[ClusterId](const SchedClassCluster &C) {
520+
return C.id() == ClusterId;
521+
});
522+
if (SchedClassClusterIt == SchedClassClusters.end()) {
523+
SchedClassClusters.emplace_back();
524+
SchedClassClusterIt = std::prev(SchedClassClusters.end());
525+
}
526+
SchedClassClusterIt->addPoint(PointId, Clustering_);
435527
}
436-
if (ClustersForSchedClass.size() <= 1)
528+
529+
// Print any scheduling class that has at least one cluster that does not
530+
// match the checked-in data.
531+
if (std::all_of(SchedClassClusters.begin(), SchedClassClusters.end(),
532+
[this, &SC](const SchedClassCluster &C) {
533+
return C.measurementsMatch(*SubtargetInfo_, SC,
534+
Clustering_);
535+
}))
437536
continue; // Nothing weird.
438537

439-
const auto &SchedModel = SubtargetInfo_->getSchedModel();
440-
const llvm::MCSchedClassDesc *const SCDesc =
441-
SchedModel.getSchedClassDesc(SchedClassAndPoints.first);
442-
if (!SCDesc)
443-
continue;
444538
OS << "<div class=\"inconsistency\"><p>Sched Class <span "
445539
"class=\"sched-class-name\">";
446540
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
447541
writeEscaped<kEscapeHtml>(OS, SCDesc->Name);
448542
#else
449-
OS << SchedClassAndPoints.first;
543+
OS << SchedClassId;
450544
#endif
451-
OS << "</span> contains instructions with distinct performance "
452-
"characteristics, falling into "
453-
<< ClustersForSchedClass.size() << " clusters:</p>";
454-
printSchedClassClustersHtml(SchedClassAndPoints.second, OS);
455-
OS << "<p>llvm data:</p>";
456-
printSchedClassDescHtml(*SCDesc, OS);
545+
OS << "</span> contains instructions whose performance characteristics do"
546+
" not match that of LLVM:</p>";
547+
printSchedClassClustersHtml(SchedClassClusters, SC, OS);
548+
OS << "<p>llvm SchedModel data:</p>";
549+
printSchedClassDescHtml(SC, OS);
457550
OS << "</div>";
458551
}
459552

Diff for: ‎llvm/tools/llvm-exegesis/lib/Analysis.h

+48-3
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@
2121
#include "llvm/Support/Error.h"
2222
#include "llvm/Support/TargetRegistry.h"
2323
#include "llvm/Support/raw_ostream.h"
24+
#include <set>
2425
#include <string>
2526
#include <unordered_map>
2627

@@ -40,11 +41,55 @@ class Analysis {
4041
template <typename Pass> llvm::Error run(llvm::raw_ostream &OS) const;
4142

4243
private:
44+
using ClusterId = InstructionBenchmarkClustering::ClusterId;
45+
46+
// An llvm::MCSchedClassDesc augmented with some additional data.
47+
struct SchedClass {
48+
SchedClass(const llvm::MCSchedClassDesc &SD,
49+
const llvm::MCSubtargetInfo &STI);
50+
51+
const llvm::MCSchedClassDesc &SCDesc;
52+
const llvm::SmallVector<llvm::MCWriteProcResEntry, 8>
53+
NonRedundantWriteProcRes;
54+
const std::vector<std::pair<uint16_t, float>> IdealizedProcResPressure;
55+
};
56+
57+
// Represents the intersection of a sched class and a cluster.
58+
class SchedClassCluster {
59+
public:
60+
const InstructionBenchmarkClustering::ClusterId &id() const {
61+
return ClusterId;
62+
}
63+
64+
const std::vector<size_t> &getPointIds() const { return PointIds; }
65+
66+
// Return the cluster centroid.
67+
const std::vector<BenchmarkMeasureStats> &getRepresentative() const {
68+
return Representative;
69+
}
70+
71+
// Returns true if the cluster representative measurements match that of SC.
72+
bool
73+
measurementsMatch(const llvm::MCSubtargetInfo &STI, const SchedClass &SC,
74+
const InstructionBenchmarkClustering &Clustering) const;
75+
76+
void addPoint(size_t PointId,
77+
const InstructionBenchmarkClustering &Clustering);
78+
79+
private:
80+
InstructionBenchmarkClustering::ClusterId ClusterId;
81+
std::vector<size_t> PointIds;
82+
// Measurement stats for the points in the SchedClassCluster.
83+
std::vector<BenchmarkMeasureStats> Representative;
84+
};
85+
4386
void printInstructionRowCsv(size_t PointId, llvm::raw_ostream &OS) const;
4487

45-
void printSchedClassClustersHtml(std::vector<size_t> PointIds,
46-
llvm::raw_ostream &OS) const;
47-
void printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
88+
void
89+
printSchedClassClustersHtml(const std::vector<SchedClassCluster> &Clusters,
90+
const SchedClass &SC,
91+
llvm::raw_ostream &OS) const;
92+
void printSchedClassDescHtml(const SchedClass &SC,
4893
llvm::raw_ostream &OS) const;
4994

5095
// Builds a map of Sched Class -> indices of points that belong to the sched

Diff for: ‎llvm/tools/llvm-exegesis/lib/BenchmarkResult.h

+2
Original file line numberDiff line numberDiff line change
@@ -77,6 +77,8 @@ class BenchmarkMeasureStats {
7777
double min() const { return MinValue; }
7878
double max() const { return MaxValue; }
7979

80+
const std::string &key() const { return Key; }
81+
8082
private:
8183
std::string Key;
8284
double SumValues = 0.0;

Diff for: ‎llvm/tools/llvm-exegesis/lib/Clustering.cpp

+25-23
Original file line numberDiff line numberDiff line change
@@ -29,38 +29,41 @@ namespace exegesis {
2929
// [1] https://en.wikipedia.org/wiki/DBSCAN
3030
// [2] https://en.wikipedia.org/wiki/OPTICS_algorithm
3131

32-
namespace {
33-
3432
// Finds the points at distance less than sqrt(EpsilonSquared) of Q (not
3533
// including Q).
36-
std::vector<size_t> rangeQuery(const std::vector<InstructionBenchmark> &Points,
37-
const size_t Q, const double EpsilonSquared) {
34+
std::vector<size_t>
35+
InstructionBenchmarkClustering::rangeQuery(const size_t Q) const {
3836
std::vector<size_t> Neighbors;
39-
const auto &QMeasurements = Points[Q].Measurements;
40-
for (size_t P = 0, NumPoints = Points.size(); P < NumPoints; ++P) {
37+
const auto &QMeasurements = Points_[Q].Measurements;
38+
for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
4139
if (P == Q)
4240
continue;
43-
const auto &PMeasurements = Points[P].Measurements;
41+
const auto &PMeasurements = Points_[P].Measurements;
4442
if (PMeasurements.empty()) // Error point.
4543
continue;
46-
double DistanceSquared = 0;
47-
for (size_t I = 0, E = QMeasurements.size(); I < E; ++I) {
48-
const auto Diff = PMeasurements[I].Value - QMeasurements[I].Value;
49-
DistanceSquared += Diff * Diff;
50-
}
51-
if (DistanceSquared <= EpsilonSquared) {
44+
if (isNeighbour(PMeasurements, QMeasurements)) {
5245
Neighbors.push_back(P);
5346
}
5447
}
5548
return Neighbors;
5649
}
5750

58-
} // namespace
51+
bool InstructionBenchmarkClustering::isNeighbour(
52+
const std::vector<BenchmarkMeasure> &P,
53+
const std::vector<BenchmarkMeasure> &Q) const {
54+
double DistanceSquared = 0.0;
55+
for (size_t I = 0, E = P.size(); I < E; ++I) {
56+
const auto Diff = P[I].Value - Q[I].Value;
57+
DistanceSquared += Diff * Diff;
58+
}
59+
return DistanceSquared <= EpsilonSquared_;
60+
}
5961

6062
InstructionBenchmarkClustering::InstructionBenchmarkClustering(
61-
const std::vector<InstructionBenchmark> &Points)
62-
: Points_(Points), NoiseCluster_(ClusterId::noise()),
63-
ErrorCluster_(ClusterId::error()) {}
63+
const std::vector<InstructionBenchmark> &Points,
64+
const double EpsilonSquared)
65+
: Points_(Points), EpsilonSquared_(EpsilonSquared),
66+
NoiseCluster_(ClusterId::noise()), ErrorCluster_(ClusterId::error()) {}
6467

6568
llvm::Error InstructionBenchmarkClustering::validateAndSetup() {
6669
ClusterIdForPoint_.resize(Points_.size());
@@ -97,12 +100,11 @@ llvm::Error InstructionBenchmarkClustering::validateAndSetup() {
97100
return llvm::Error::success();
98101
}
99102

100-
void InstructionBenchmarkClustering::dbScan(const size_t MinPts,
101-
const double EpsilonSquared) {
103+
void InstructionBenchmarkClustering::dbScan(const size_t MinPts) {
102104
for (size_t P = 0, NumPoints = Points_.size(); P < NumPoints; ++P) {
103105
if (!ClusterIdForPoint_[P].isUndef())
104106
continue; // Previously processed in inner loop.
105-
const auto Neighbors = rangeQuery(Points_, P, EpsilonSquared);
107+
const auto Neighbors = rangeQuery(P);
106108
if (Neighbors.size() + 1 < MinPts) { // Density check.
107109
// The region around P is not dense enough to create a new cluster, mark
108110
// as noise for now.
@@ -136,7 +138,7 @@ void InstructionBenchmarkClustering::dbScan(const size_t MinPts,
136138
ClusterIdForPoint_[Q] = CurrentCluster.Id;
137139
CurrentCluster.PointIndices.push_back(Q);
138140
// And extend to the neighbors of Q if the region is dense enough.
139-
const auto Neighbors = rangeQuery(Points_, Q, EpsilonSquared);
141+
const auto Neighbors = rangeQuery(Q);
140142
if (Neighbors.size() + 1 >= MinPts) {
141143
ToProcess.insert(Neighbors.begin(), Neighbors.end());
142144
}
@@ -155,15 +157,15 @@ llvm::Expected<InstructionBenchmarkClustering>
155157
InstructionBenchmarkClustering::create(
156158
const std::vector<InstructionBenchmark> &Points, const size_t MinPts,
157159
const double Epsilon) {
158-
InstructionBenchmarkClustering Clustering(Points);
160+
InstructionBenchmarkClustering Clustering(Points, Epsilon * Epsilon);
159161
if (auto Error = Clustering.validateAndSetup()) {
160162
return std::move(Error);
161163
}
162164
if (Clustering.ErrorCluster_.PointIndices.size() == Points.size()) {
163165
return Clustering; // Nothing to cluster.
164166
}
165167

166-
Clustering.dbScan(MinPts, Epsilon * Epsilon);
168+
Clustering.dbScan(MinPts);
167169
return Clustering;
168170
}
169171

Diff for: ‎llvm/tools/llvm-exegesis/lib/Clustering.h

+13-7
Original file line numberDiff line numberDiff line change
@@ -33,12 +33,10 @@ class InstructionBenchmarkClustering {
3333
public:
3434
static ClusterId noise() { return ClusterId(kNoise); }
3535
static ClusterId error() { return ClusterId(kError); }
36-
static ClusterId makeValid(size_t Id) {
37-
return ClusterId(Id);
38-
}
36+
static ClusterId makeValid(size_t Id) { return ClusterId(Id); }
3937
ClusterId() : Id_(kUndef) {}
4038
bool operator==(const ClusterId &O) const { return Id_ == O.Id_; }
41-
bool operator<(const ClusterId &O) const {return Id_ < O.Id_; }
39+
bool operator<(const ClusterId &O) const { return Id_ < O.Id_; }
4240

4341
bool isValid() const { return Id_ <= kMaxValid; }
4442
bool isUndef() const { return Id_ == kUndef; }
@@ -53,7 +51,8 @@ class InstructionBenchmarkClustering {
5351

5452
private:
5553
explicit ClusterId(size_t Id) : Id_(Id) {}
56-
static constexpr const size_t kMaxValid = std::numeric_limits<size_t>::max() - 4;
54+
static constexpr const size_t kMaxValid =
55+
std::numeric_limits<size_t>::max() - 4;
5756
static constexpr const size_t kNoise = kMaxValid + 1;
5857
static constexpr const size_t kError = kMaxValid + 2;
5958
static constexpr const size_t kUndef = kMaxValid + 3;
@@ -88,12 +87,19 @@ class InstructionBenchmarkClustering {
8887

8988
const std::vector<Cluster> &getValidClusters() const { return Clusters_; }
9089

90+
// Returns true if the given point is within a distance Epsilon of each other.
91+
bool isNeighbour(const std::vector<BenchmarkMeasure> &P,
92+
const std::vector<BenchmarkMeasure> &Q) const;
93+
9194
private:
9295
InstructionBenchmarkClustering(
93-
const std::vector<InstructionBenchmark> &Points);
96+
const std::vector<InstructionBenchmark> &Points, double EpsilonSquared);
9497
llvm::Error validateAndSetup();
95-
void dbScan(size_t MinPts, double EpsilonSquared);
98+
void dbScan(size_t MinPts);
99+
std::vector<size_t> rangeQuery(size_t Q) const;
100+
96101
const std::vector<InstructionBenchmark> &Points_;
102+
const double EpsilonSquared_;
97103
int NumDimensions_ = 0;
98104
// ClusterForPoint_[P] is the cluster id for Points[P].
99105
std::vector<ClusterId> ClusterIdForPoint_;

0 commit comments

Comments
 (0)
Please sign in to comment.