[llvm-exegesis] Add an analysis mode.

[courbet]

Summary

The analysis mode gives the user a clustered view of the measurement results.
Next steps are (requires the split ok AsmTemplate.Name into {mnemonic, mode}):

• Show the sched class.
• Highlight any inconsistencies with the checked-in data.

[courbet]

• add missing file header.

[courbet]

cosmetics + clang-format

[gchatelet]

tools/llvm-exegesis/lib/Analysis.cpp

21

Technically CSV is comma separated and not semicolon separated.
Semicolon seems to be a popular variant in French but not necessarily in other locales.
Also strings should be quoted to prevent interpretation of comma (semicolon) within them.

tools/llvm-exegesis/lib/Clustering.cpp

22

?

[courbet]

Escape csv strings if needed.

[courbet]

tools/llvm-exegesis/lib/Clustering.cpp

22

Bad merge. Fixed.

tools/llvm-exegesis/lib/Analysis.h

+//===-- Analysis.h ----------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// Analysis output for benchmark results.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TOOLS_LLVM_EXEGESIS_ANALYSIS_H
+#define LLVM_TOOLS_LLVM_EXEGESIS_ANALYSIS_H
+
+#include "Clustering.h"
+#include "llvm/MC/MCSubtargetInfo.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace exegesis {
+
+// Prints a csv of instructions for each cluster.
+llvm::Error
+printAnalysisClusters(const InstructionBenchmarkClustering &Clustering,
+                      const llvm::MCSubtargetInfo &STI, llvm::raw_ostream &OS);
+
+} // namespace exegesis
+
+#endif // LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H

tools/llvm-exegesis/lib/Analysis.cpp

+//===-- Analysis.cpp --------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BenchmarkResult.h"
+#include "Analysis.h"
+#include "llvm/Support/FormatVariadic.h"
+#include <vector>
+
+namespace exegesis {
+
+static const char kCsvSep = ',';
+
+static void writeCsvEscaped(llvm::raw_ostream& OS, const std::string& S) {
+  if (std::find(S.begin(), S.end(), kCsvSep) == S.end()) {
+    OS << S;
+  } else {
+    // Needs escaping.
+    OS << '"';
+    for (const char C : S) {
+      if (C == '"')
+        OS << "\"\"";
+      else
+        OS << C;
+    }
+    OS << '"';
+  }
+}
+
+// Prints a row representing an instruction, along with scheduling info and
+// point coordinates (measurements).
+static void printInstructionRow(const InstructionBenchmark &Point,
+                         const llvm::MCSubtargetInfo &STI,
+                         const size_t ClusterId, llvm::raw_ostream &OS) {
+  OS << ClusterId << kCsvSep;
+  writeCsvEscaped(OS, Point.AsmTmpl.Name);
+  // FIXME: Print the sched class once InstructionBenchmark separates key into
+  // (mnemonic, mode, opaque).
+  for (const auto &Measurement : Point.Measurements) {
+    OS << kCsvSep;
+    writeCsvEscaped(OS, llvm::formatv("{0:F}", Measurement.Value));
+  }
+  OS << "\n";
+}
+
+static void printCluster(const std::vector<InstructionBenchmark> &Points,
+                  const llvm::MCSubtargetInfo &STI, const size_t ClusterId,
+                  const InstructionBenchmarkClustering::Cluster &Cluster,
+                  llvm::raw_ostream &OS) {
+  // Print all points.
+  for (const auto &PointId : Cluster.PointIndices) {
+    printInstructionRow(Points[PointId], STI, ClusterId, OS);
+  }
+}
+
+llvm::Error
+printAnalysisClusters(const InstructionBenchmarkClustering &Clustering,
+                      const llvm::MCSubtargetInfo &STI, llvm::raw_ostream &OS) {
+  if (Clustering.getPoints().empty())
+    return llvm::Error::success();
+
+  // Write the header.
+  OS << "cluster_id;key,sched_class";
+  for (const auto &Measurement : Clustering.getPoints().front().Measurements) {
+    OS << kCsvSep;
+    writeCsvEscaped(OS, Measurement.Key);
+  }
+  OS << "\n";
+
+  // Write the points.
+  for (size_t I = 0, E = Clustering.getValidClusters().size(); I < E; ++I) {
+    printCluster(Clustering.getPoints(), STI, I,
+                 Clustering.getValidClusters()[I], OS);
+    OS << "\n\n";
+  }
+  return llvm::Error::success();
+}
+
+} // namespace exegesis

tools/llvm-exegesis/lib/CMakeLists.txt

 add_library(LLVMExegesis
   STATIC
+  Analysis.cpp
   BenchmarkResult.cpp
   BenchmarkRunner.cpp
   Clustering.cpp
   InMemoryAssembler.cpp
   InstructionSnippetGenerator.cpp
   Latency.cpp
   LlvmState.cpp
   OperandGraph.cpp

tools/llvm-exegesis/lib/Clustering.h

struct Cluster {
     // Indices of benchmarks within the cluster.
     std::vector<int> PointIndices;
   };
 
   ClusterId getClusterIdForPoint(size_t P) const {
     return ClusterIdForPoint_[P];
   }
 
+  const std::vector<InstructionBenchmark> &getPoints() const { return Points_; }
+
   const Cluster &getCluster(ClusterId Id) const {
     assert(!Id.isUndef() && "unlabeled cluster");
     if (Id.isNoise()) {
       return NoiseCluster_;
     }
     if (Id.isError()) {
       return ErrorCluster_;
     }
     return Clusters_[Id.getId()];
   }
 
   const std::vector<Cluster> &getValidClusters() const { return Clusters_; }
 
 private:
-  InstructionBenchmarkClustering();
-  llvm::Error validateAndSetup(const std::vector<InstructionBenchmark> &Points);
-  void dbScan(const std::vector<InstructionBenchmark> &Points, size_t MinPts,
-              double EpsilonSquared);
+  InstructionBenchmarkClustering(
+      const std::vector<InstructionBenchmark> &Points);
+  llvm::Error validateAndSetup();
+  void dbScan(size_t MinPts, double EpsilonSquared);
+  const std::vector<InstructionBenchmark> &Points_;
   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

 namespace exegesis {
 
 // The clustering problem has the following characteristics:
 //  (A) - Low dimension (dimensions are typically proc resource units,
 //    typically < 10).
 //  (B) - Number of points : ~thousands (points are measurements of an MCInst)
 //  (C) - Number of clusters: ~tens.
 //  (D) - The number of clusters is not known /a priory/.
 //  (E) - The amount of noise is relatively small.
 // The problem is rather small. In terms of algorithms, (D) disqualifies
 // 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
if (DistanceSquared <= EpsilonSquared) {
       Neighbors.push_back(P);
     }
   }
   return Neighbors;
 }
 
 } // namespace
 
-InstructionBenchmarkClustering::InstructionBenchmarkClustering()
-    : NoiseCluster_(ClusterId::noise()), ErrorCluster_(ClusterId::error()) {}
+InstructionBenchmarkClustering::InstructionBenchmarkClustering(
+    const std::vector<InstructionBenchmark> &Points)
+    : Points_(Points), NoiseCluster_(ClusterId::noise()),
+      ErrorCluster_(ClusterId::error()) {}
 
-llvm::Error InstructionBenchmarkClustering::validateAndSetup(
-    const std::vector<InstructionBenchmark> &Points) {
-  ClusterIdForPoint_.resize(Points.size());
+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) {
+    const auto &Point = Points_[P];
     if (!Point.Error.empty()) {
       ClusterIdForPoint_[P] = ClusterId::error();
       ErrorCluster_.PointIndices.push_back(P);
       continue;
     }
     const auto *CurMeasurement = &Point.Measurements;
     if (LastMeasurement) {
       if (LastMeasurement->size() != CurMeasurement->size()) {
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 std::vector<InstructionBenchmark> &Points, const size_t MinPts,
+void InstructionBenchmarkClustering::dbScan(const size_t MinPts,
                                             const double EpsilonSquared) {
-  for (size_t P = 0, NumPoints = Points.size(); P < NumPoints; ++P) {
+  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(Points_, P, EpsilonSquared);
     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(Points_, Q, EpsilonSquared);
       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) {
+  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;
-  if (auto Error = Clustering.validateAndSetup(Points)) {
-    return std::move(Error);
+  InstructionBenchmarkClustering Clustering(Points);
+  if (auto Error = Clustering.validateAndSetup()) {
+    return Error;
   }
   if (Clustering.ErrorCluster_.PointIndices.size() == Points.size()) {
     return Clustering; // Nothing to cluster.
   }
 
-  Clustering.dbScan(Points, MinPts, Epsilon * Epsilon);
+  Clustering.dbScan(MinPts, Epsilon * Epsilon);
   return Clustering;
 }
 
 } // namespace exegesis

tools/llvm-exegesis/llvm-exegesis.cpp

 //===-- llvm-exegesis.cpp ---------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// Measures execution properties (latencies/uops) of an instruction.
 ///
 //===----------------------------------------------------------------------===//
 
+#include "lib/Analysis.h"
 #include "lib/BenchmarkResult.h"
 #include "lib/BenchmarkRunner.h"
+#include "lib/Clustering.h"
 #include "lib/Latency.h"
 #include "lib/LlvmState.h"
 #include "lib/PerfHelper.h"
 #include "lib/Uops.h"
 #include "lib/X86.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/MC/MCInstBuilder.h"
 #include "llvm/MC/MCRegisterInfo.h"
+#include "llvm/MC/MCSubtargetInfo.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Format.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include <algorithm>
 #include <random>
 #include <string>
 #include <unordered_map>
 
 static llvm::cl::opt<unsigned>
     OpcodeIndex("opcode-index", llvm::cl::desc("opcode to measure, by index"),
                 llvm::cl::init(0));
 
 static llvm::cl::opt<std::string>
     OpcodeName("opcode-name", llvm::cl::desc("opcode to measure, by name"),
                llvm::cl::init(""));
 
-enum class BenchmarkModeE { Latency, Uops };
-static llvm::cl::opt<BenchmarkModeE>
-    BenchmarkMode("benchmark-mode", llvm::cl::desc("the benchmark mode to run"),
-                  llvm::cl::values(clEnumValN(BenchmarkModeE::Latency,
-                                              "latency", "Instruction Latency"),
-                                   clEnumValN(BenchmarkModeE::Uops, "uops",
-                                              "Uop Decomposition")));
+static llvm::cl::opt<std::string>
+    BenchmarkFile("benchmarks-file", llvm::cl::desc(""), llvm::cl::init("-"));
+
+enum class BenchmarkModeE { Latency, Uops, Analysis };
+static llvm::cl::opt<BenchmarkModeE> BenchmarkMode(
+    "benchmark-mode", llvm::cl::desc("the benchmark mode to run"),
+    llvm::cl::values(
+        clEnumValN(BenchmarkModeE::Latency, "latency", "Instruction Latency"),
+        clEnumValN(BenchmarkModeE::Uops, "uops", "Uop Decomposition"),
+        clEnumValN(BenchmarkModeE::Analysis, "analysis", "Analysis")));
 
 static llvm::cl::opt<unsigned>
     NumRepetitions("num-repetitions",
                    llvm::cl::desc("number of time to repeat the asm snippet"),
                    llvm::cl::init(10000));
 
+static llvm::cl::opt<unsigned> AnalysisNumPoints(
+    "analysis-numpoints",
+    llvm::cl::desc("minimum number of points in an analysis cluster"),
+    llvm::cl::init(3));
+
+static llvm::cl::opt<float>
+    AnalysisEpsilon("analysis-epsilon",
+                    llvm::cl::desc("dbscan epsilon for analysis clustering"),
+                    llvm::cl::init(0.1));
+
 namespace exegesis {
 
-void main() {
-  if (OpcodeName.empty() == (OpcodeIndex == 0)) {
+void benchmarkMain() {
+  if (exegesis::pfm::pfmInitialize())
+    llvm::report_fatal_error("cannot initialize libpfm");
+
+  if (OpcodeName.empty() == (OpcodeIndex == 0))
     llvm::report_fatal_error(
         "please provide one and only one of 'opcode-index' or 'opcode-name'");
-  }
 
   llvm::InitializeNativeTarget();
   llvm::InitializeNativeTargetAsmPrinter();
 
   // FIXME: Target-specific filter.
   X86Filter Filter;
 
   const LLVMState State;
void benchmarkMain() {
   std::unique_ptr<BenchmarkRunner> Runner;
   switch (BenchmarkMode) {
   case BenchmarkModeE::Latency:
     Runner = llvm::make_unique<LatencyBenchmarkRunner>();
     break;
   case BenchmarkModeE::Uops:
     Runner = llvm::make_unique<UopsBenchmarkRunner>();
     break;
+  case BenchmarkModeE::Analysis:
+    llvm_unreachable("not a benchmark");
   }
 
   Runner->run(State, Opcode, NumRepetitions > 0 ? NumRepetitions : 1, Filter)
-      .writeYamlOrDie("-");
+      .writeYamlOrDie(BenchmarkFile);
+  exegesis::pfm::pfmTerminate();
+}
+
+void analysisMain() {
+  // Read benchmarks.
+  const std::vector<InstructionBenchmark> Points =
+      InstructionBenchmark::readYamlsOrDie(BenchmarkFile);
+  llvm::outs() << "Parsed " << Points.size() << " benchmark points\n";
+  if (Points.empty()) {
+    llvm::errs() << "no benchmarks to analyze\n";
+    return;
+  }
+  // FIXME: Check that all points have the same triple/cpu.
+  // FIXME: Merge points from several runs (latency and uops).
+
+  llvm::InitializeAllTargets();
+  std::string Error;
+  const auto *TheTarget =
+      llvm::TargetRegistry::lookupTarget(Points[0].LLVMTriple, Error);
+  if (!TheTarget) {
+    llvm::errs() << "unknown target '" << Points[0].LLVMTriple << "'\n";
+    return;
+  }
+  std::unique_ptr<llvm::MCSubtargetInfo> STI(TheTarget->createMCSubtargetInfo(
+      Points[0].LLVMTriple, Points[0].CpuName, ""));
+
+  const auto Clustering = llvm::cantFail(InstructionBenchmarkClustering::create(
+      Points, AnalysisNumPoints, AnalysisEpsilon));
+  if (auto Err = printAnalysisClusters(Clustering, *STI, llvm::outs()))
+    llvm::report_fatal_error(std::move(Err));
 }
 
 } // namespace exegesis
 
 int main(int Argc, char **Argv) {
   llvm::cl::ParseCommandLineOptions(Argc, Argv, "");
 
-  if (exegesis::pfm::pfmInitialize()) {
-    llvm::errs() << "cannot initialize libpfm\n";
-    return EXIT_FAILURE;
+  if (BenchmarkMode == BenchmarkModeE::Analysis) {
+    exegesis::analysisMain();
+  } else {
+    exegesis::benchmarkMain();
   }
-
-  exegesis::main();
-
-  exegesis::pfm::pfmTerminate();
   return EXIT_SUCCESS;
 }