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

   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:
  40     static ClusterId noise() { return ClusterId(kNoise); }
  41     static ClusterId error() { return ClusterId(kError); }
  42     static ClusterId makeValid(size_t Id, bool IsUnstable = false) {
  43       return ClusterId(Id, IsUnstable);
  44     }
  45     static ClusterId makeValidUnstable(size_t Id) {
  46       return makeValid(Id, /*IsUnstable=*/true);
  47     }
  48
  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
  55     bool isValid() const { return Id_ <= kMaxValid; }
  56     bool isUnstable() const { return IsUnstable_; }
  57     bool isNoise() const { return Id_ == kNoise; }
  58     bool isError() const { return Id_ == kError; }
  59     bool isUndef() const { return Id_ == kUndef; }
  60
  61     // Precondition: isValid().
  62     size_t getId() const {
  63       assert(isValid());
  64       return Id_;
  65     }
  66
  67   private:
  68     ClusterId(size_t Id, bool IsUnstable = false)
  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;
  84     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
  91   ClusterId getClusterIdForPoint(size_t P) const {
  92     return ClusterIdForPoint_[P];
  93   }
  94
  95   const std::vector<InstructionBenchmark> &getPoints() const { return Points_; }
  96
  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
 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.
 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:
 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