Index: tools/llvm-exegesis/lib/Analysis.h =================================================================== --- tools/llvm-exegesis/lib/Analysis.h +++ 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 #include #include @@ -40,11 +41,55 @@ template 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 + NonRedundantWriteProcRes; + const std::vector> IdealizedProcResPressure; + }; + + // Represents the intersection of a sched class and a cluster. + class SchedClassCluster { + public: + const InstructionBenchmarkClustering::ClusterId &id() const { + return ClusterId; + } + + const std::vector &getPointIds() const { return PointIds; } + + // Return the cluster centroid. + const std::vector &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 PointIds; + // Measurement stats for the points in the SchedClassCluster. + std::vector Representative; + }; + void printInstructionRowCsv(size_t PointId, llvm::raw_ostream &OS) const; - void printSchedClassClustersHtml(std::vector PointIds, - llvm::raw_ostream &OS) const; - void printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc, + void + printSchedClassClustersHtml(const std::vector &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 Index: tools/llvm-exegesis/lib/Analysis.cpp =================================================================== --- tools/llvm-exegesis/lib/Analysis.cpp +++ tools/llvm-exegesis/lib/Analysis.cpp @@ -168,20 +168,15 @@ return PointsPerSchedClass; } -void Analysis::printSchedClassClustersHtml(std::vector 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 &Clusters, const SchedClass &SC, + llvm::raw_ostream &OS) const { const auto &Points = Clustering_.getPoints(); OS << ""; OS << ""; - for (const auto &Measurement : Points[PointIds[0]].Measurements) { + assert(!Clusters.empty()); + for (const auto &Measurement : + Points[Clusters[0].getPointIds()[0]].Measurements) { OS << ""; } OS << ""; - for (size_t I = 0, E = PointIds.size(); I < E;) { - const auto &CurrentClusterId = - Clustering_.getClusterIdForPoint(PointIds[I]); - OS << ""; - for (const auto &Stats : MeasurementStats) { + for (const auto &Stats : Cluster.getRepresentative()) { OS << "
ClusterIdOpcode/Config"; if (Measurement.DebugString.empty()) writeEscaped(OS, Measurement.Key); @@ -190,29 +185,24 @@ OS << "
"; - writeClusterId(OS, CurrentClusterId); + for (const SchedClassCluster &Cluster : Clusters) { + OS << "
"; + writeClusterId(OS, Cluster.id()); OS << "
    "; - std::vector 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 << "
  • "; writeEscaped(OS, Point.Key.OpcodeName); OS << " "; writeEscaped(OS, Point.Key.Config); OS << "
  • "; - for (size_t J = 0, F = Point.Measurements.size(); J < F; ++J) { - MeasurementStats[J].push(Point.Measurements[J]); - } } OS << "
"; writeMeasurementValue(OS, Stats.avg()); OS << "
["; @@ -300,25 +290,101 @@ 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 ClusterCenterPoint(NumMeasurements); + std::vector 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(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 &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 << ""; OS << ""; - if (SCDesc.isValid()) { + if (SC.SCDesc.isValid()) { const auto &SM = SubtargetInfo_->getSchedModel(); OS << ""; - OS << ""; - OS << ""; + OS << ""; + OS << ""; // Latencies. OS << ""; // WriteProcRes. OS << ""; // Idealized port pressure. OS << "
ValidVariantuOpsLatencyWriteProcResIdealized " "Resource Pressure
" << (SCDesc.isVariant() ? "✔" : "✕") << "" << SCDesc.NumMicroOps << "" << (SC.SCDesc.isVariant() ? "✔" : "✕") + << "" << SC.SCDesc.NumMicroOps << "
    "; - 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 << "
  • " << 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 @@ OS << "
    "; - const auto ProcRes = getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_); - for (const auto &WPR : ProcRes) { + for (const auto &WPR : SC.NonRedundantWriteProcRes) { OS << "
  • "; writeEscaped(OS, SM.getProcResource(WPR.ProcResourceIdx)->Name); @@ -337,7 +402,7 @@ OS << "
    "; - for (const auto &Pressure : computeIdealizedProcResPressure(SM, ProcRes)) { + for (const auto &Pressure : SC.IdealizedProcResPressure) { OS << "
  • "; writeEscaped(OS, SubtargetInfo_->getSchedModel() .getProcResource(Pressure.first) @@ -401,12 +466,21 @@ 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; +} )"; @@ -414,46 +488,65 @@ template <> llvm::Error Analysis::run( llvm::raw_ostream &OS) const { + const auto &FirstPoint = Clustering_.getPoints()[0]; // Print the header. OS << "" << kHtmlHead << ""; OS << "

    llvm-exegesis Analysis Results

    "; OS << "

    Triple: "; - writeEscaped(OS, Clustering_.getPoints()[0].LLVMTriple); + writeEscaped(OS, FirstPoint.LLVMTriple); OS << "

    Cpu: "; - writeEscaped(OS, Clustering_.getPoints()[0].CpuName); + writeEscaped(OS, FirstPoint.CpuName); OS << "

    "; - // 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 ClustersForSchedClass; - for (const size_t PointId : SchedClassAndPoints.second) { + const auto SchedClassId = SchedClassAndPoints.first; + const std::vector &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 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 << "

    Sched Class "; #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) writeEscaped(OS, SCDesc->Name); #else - OS << SchedClassAndPoints.first; + OS << SchedClassId; #endif - OS << " contains instructions with distinct performance " - "characteristics, falling into " - << ClustersForSchedClass.size() << " clusters:

    "; - printSchedClassClustersHtml(SchedClassAndPoints.second, OS); - OS << "

    llvm data:

    "; - printSchedClassDescHtml(*SCDesc, OS); + OS << " contains instructions whose performance characteristics do" + " not match that of LLVM:

    "; + printSchedClassClustersHtml(SchedClassClusters, SC, OS); + OS << "

    llvm SchedModel data:

    "; + printSchedClassDescHtml(SC, OS); OS << "
    "; } Index: tools/llvm-exegesis/lib/BenchmarkResult.h =================================================================== --- tools/llvm-exegesis/lib/BenchmarkResult.h +++ tools/llvm-exegesis/lib/BenchmarkResult.h @@ -77,6 +77,8 @@ 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; Index: tools/llvm-exegesis/lib/Clustering.h =================================================================== --- tools/llvm-exegesis/lib/Clustering.h +++ tools/llvm-exegesis/lib/Clustering.h @@ -33,12 +33,10 @@ 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 @@ private: explicit ClusterId(size_t Id) : Id_(Id) {} - static constexpr const size_t kMaxValid = std::numeric_limits::max() - 4; + static constexpr const size_t kMaxValid = + std::numeric_limits::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 @@ const std::vector &getValidClusters() const { return Clusters_; } + // Returns true if the given point is within a distance Epsilon of each other. + bool isNeighbour(const std::vector &P, + const std::vector &Q) const; + private: InstructionBenchmarkClustering( - const std::vector &Points); + const std::vector &Points, double EpsilonSquared); llvm::Error validateAndSetup(); - void dbScan(size_t MinPts, double EpsilonSquared); + void dbScan(size_t MinPts); + std::vector rangeQuery(size_t Q) const; + const std::vector &Points_; + const double EpsilonSquared_; int NumDimensions_ = 0; // ClusterForPoint_[P] is the cluster id for Points[P]. std::vector ClusterIdForPoint_; Index: tools/llvm-exegesis/lib/Clustering.cpp =================================================================== --- tools/llvm-exegesis/lib/Clustering.cpp +++ tools/llvm-exegesis/lib/Clustering.cpp @@ -29,38 +29,41 @@ // [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 rangeQuery(const std::vector &Points, - const size_t Q, const double EpsilonSquared) { +std::vector +InstructionBenchmarkClustering::rangeQuery(const size_t Q) const { std::vector 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 &P, + const std::vector &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 &Points) - : Points_(Points), NoiseCluster_(ClusterId::noise()), - ErrorCluster_(ClusterId::error()) {} + const std::vector &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 @@ 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 @@ 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 @@ InstructionBenchmarkClustering::create( const std::vector &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 @@ return Clustering; // Nothing to cluster. } - Clustering.dbScan(MinPts, Epsilon * Epsilon); + Clustering.dbScan(MinPts); return Clustering; }