1 //===-- Clustering.h --------------------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// Utilities to compute benchmark result clusters.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H
15 #define LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H
16 
17 #include "BenchmarkResult.h"
18 #include "llvm/ADT/Optional.h"
19 #include "llvm/Support/Error.h"
20 #include <limits>
21 #include <vector>
22 
23 namespace llvm {
24 namespace exegesis {
25 
26 class InstructionBenchmarkClustering {
27 public:
28   enum ModeE { Dbscan, Naive };
29 
30   // Clusters `Points` using DBSCAN with the given parameters. See the cc file
31   // for more explanations on the algorithm.
32   static Expected<InstructionBenchmarkClustering>
33   create(const std::vector<InstructionBenchmark> &Points, ModeE Mode,
34          size_t DbscanMinPts, double AnalysisClusteringEpsilon,
35          const MCSubtargetInfo *SubtargetInfo = nullptr,
36          const MCInstrInfo *InstrInfo = nullptr);
37 
38   class ClusterId {
39   public:
noise()40     static ClusterId noise() { return ClusterId(kNoise); }
error()41     static ClusterId error() { return ClusterId(kError); }
42     static ClusterId makeValid(size_t Id, bool IsUnstable = false) {
43       return ClusterId(Id, IsUnstable);
44     }
makeValidUnstable(size_t Id)45     static ClusterId makeValidUnstable(size_t Id) {
46       return makeValid(Id, /*IsUnstable=*/true);
47     }
48 
ClusterId()49     ClusterId() : Id_(kUndef), IsUnstable_(false) {}
50 
51     // Compare id's, ignoring the 'unstability' bit.
52     bool operator==(const ClusterId &O) const { return Id_ == O.Id_; }
53     bool operator<(const ClusterId &O) const { return Id_ < O.Id_; }
54 
isValid()55     bool isValid() const { return Id_ <= kMaxValid; }
isUnstable()56     bool isUnstable() const { return IsUnstable_; }
isNoise()57     bool isNoise() const { return Id_ == kNoise; }
isError()58     bool isError() const { return Id_ == kError; }
isUndef()59     bool isUndef() const { return Id_ == kUndef; }
60 
61     // Precondition: isValid().
getId()62     size_t getId() const {
63       assert(isValid());
64       return Id_;
65     }
66 
67   private:
68     ClusterId(size_t Id, bool IsUnstable = false)
Id_(Id)69         : Id_(Id), IsUnstable_(IsUnstable) {}
70 
71     static constexpr const size_t kMaxValid =
72         (std::numeric_limits<size_t>::max() >> 1) - 4;
73     static constexpr const size_t kNoise = kMaxValid + 1;
74     static constexpr const size_t kError = kMaxValid + 2;
75     static constexpr const size_t kUndef = kMaxValid + 3;
76 
77     size_t Id_ : (std::numeric_limits<size_t>::digits - 1);
78     size_t IsUnstable_ : 1;
79   };
80   static_assert(sizeof(ClusterId) == sizeof(size_t), "should be a bit field.");
81 
82   struct Cluster {
83     Cluster() = delete;
ClusterCluster84     explicit Cluster(const ClusterId &Id) : Id(Id) {}
85 
86     const ClusterId Id;
87     // Indices of benchmarks within the cluster.
88     std::vector<int> PointIndices;
89   };
90 
getClusterIdForPoint(size_t P)91   ClusterId getClusterIdForPoint(size_t P) const {
92     return ClusterIdForPoint_[P];
93   }
94 
getPoints()95   const std::vector<InstructionBenchmark> &getPoints() const { return Points_; }
96 
getCluster(ClusterId Id)97   const Cluster &getCluster(ClusterId Id) const {
98     assert(!Id.isUndef() && "unlabeled cluster");
99     if (Id.isNoise()) {
100       return NoiseCluster_;
101     }
102     if (Id.isError()) {
103       return ErrorCluster_;
104     }
105     return Clusters_[Id.getId()];
106   }
107 
getValidClusters()108   const std::vector<Cluster> &getValidClusters() const { return Clusters_; }
109 
110   // Returns true if the given point is within a distance Epsilon of each other.
isNeighbour(const std::vector<BenchmarkMeasure> & P,const std::vector<BenchmarkMeasure> & Q,const double EpsilonSquared_)111   bool isNeighbour(const std::vector<BenchmarkMeasure> &P,
112                    const std::vector<BenchmarkMeasure> &Q,
113                    const double EpsilonSquared_) const {
114     double DistanceSquared = 0.0;
115     for (size_t I = 0, E = P.size(); I < E; ++I) {
116       const auto Diff = P[I].PerInstructionValue - Q[I].PerInstructionValue;
117       DistanceSquared += Diff * Diff;
118     }
119     return DistanceSquared <= EpsilonSquared_;
120   }
121 
122 private:
123   InstructionBenchmarkClustering(
124       const std::vector<InstructionBenchmark> &Points,
125       double AnalysisClusteringEpsilonSquared);
126 
127   Error validateAndSetup();
128 
129   void clusterizeDbScan(size_t MinPts);
130   void clusterizeNaive(const MCSubtargetInfo &SubtargetInfo,
131                        const MCInstrInfo &InstrInfo);
132 
133   // Stabilization is only needed if dbscan was used to clusterize.
134   void stabilize(unsigned NumOpcodes);
135 
136   void rangeQuery(size_t Q, std::vector<size_t> &Scratchpad) const;
137 
138   bool areAllNeighbours(ArrayRef<size_t> Pts) const;
139 
140   const std::vector<InstructionBenchmark> &Points_;
141   const double AnalysisClusteringEpsilonSquared_;
142 
143   int NumDimensions_ = 0;
144   // ClusterForPoint_[P] is the cluster id for Points[P].
145   std::vector<ClusterId> ClusterIdForPoint_;
146   std::vector<Cluster> Clusters_;
147   Cluster NoiseCluster_;
148   Cluster ErrorCluster_;
149 };
150 
151 class SchedClassClusterCentroid {
152 public:
getStats()153   const std::vector<PerInstructionStats> &getStats() const {
154     return Representative;
155   }
156 
157   std::vector<BenchmarkMeasure> getAsPoint() const;
158 
159   void addPoint(ArrayRef<BenchmarkMeasure> Point);
160 
161   bool validate(InstructionBenchmark::ModeE Mode) const;
162 
163 private:
164   // Measurement stats for the points in the SchedClassCluster.
165   std::vector<PerInstructionStats> Representative;
166 };
167 
168 } // namespace exegesis
169 } // namespace llvm
170 
171 #endif // LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H
172