[llvm-exegesis] Analysis: detect clustering inconsistencies.

[courbet]

Summary

Warn on instructions that should have the same performance
characteristics according to the sched model but actually
differ in their benchmarks.

Next step: Make the display nicer to browse, I was thinking maybe html.

[courbet]

Sample output:

Sched Class MOVSX32rr16_MOVSX32rr8_MOVSX32rr8_NOREX_MOVSX64rr16_MOVSX64rr8_MOVZX32rr16_MOVZX32rr8_MOVZX32rr8_NOREX_MOVZX64rr16_MOVZX64rr8 contains instructions with distinct performance characteristics, falling into 2 clusters:
2,MOVSX32rr16,,1.01
3,MOVSX32rr8,,2.01
2,MOVSX32rr8_NOREX,,1.01
2,MOVSX64rr16,,1.01
2,MOVZX32rr16,,1.00
3,MOVZX32rr8,,2.01
3,MOVZX32rr8_NOREX,,2.01
2,MOVZX64rr16,,1.00

Sched Class ADC16ri_ADC16ri8_ADC32ri_ADC32ri8_ADC64ri32_ADC64ri8_ADC8ri_ADC8ri8_ADC16rr_ADC16rr_REV_ADC32rr_ADC32rr_REV_ADC64rr_ADC64rr_REV_ADC8rr_ADC8rr_REV_ADC16i16_ADC32i32_ADC64i32_ADC8i8_SBB16ri_SBB16ri8_SBB32ri_SBB32ri8_SBB64ri32_SBB64ri8_SBB8ri_SBB8ri8_SBB16rr_SBB16rr_REV_SBB32rr_SBB32rr_REV_SBB64rr_SBB64rr_REV_SBB8rr_SBB8rr_REV_SBB16i16_SBB32i32_SBB64i32_SBB8i8 contains instructions with distinct performance characteristics, falling into 2 clusters:
3,ADC8i8,,2.00
2,ADC8ri,,1.01
3,SBB8i8,,2.01
2,SBB8ri,,1.01

Sched Class EXTRACTPSrr_VEXTRACTPSrr contains instructions with distinct performance characteristics, falling into 2 clusters:
4,EXTRACTPSrr,,3.00
3,VEXTRACTPSrr,,2.01

Sched Class WriteVecExtract contains instructions with distinct performance characteristics, falling into 2 clusters:
9,VPEXTRBrr,,1.50
4,VPEXTRWrr,,3.01

Sched Class WriteCRC32 contains instructions with distinct performance characteristics, falling into 2 clusters:
4,CRC32r32r16,,3.01
4,CRC32r32r32,,3.00
11,CRC32r32r8,,4.01
4,CRC32r64r64,,3.01
4,CRC32r64r8,,3.00

Sched Class WritePMULLD contains instructions with distinct performance characteristics, falling into 2 clusters:
13,PMULLDrr,,10.01
14,VPMULLDrr,,11.01

llvm/trunk/tools/llvm-exegesis/lib/Analysis.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TOOLS_LLVM_EXEGESIS_ANALYSIS_H
 #define LLVM_TOOLS_LLVM_EXEGESIS_ANALYSIS_H
 
 #include "Clustering.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/MC/MCSubtargetInfo.h"
-#include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/raw_ostream.h"
 #include <string>
 #include <unordered_map>
 
 namespace exegesis {
 
 // A helper class to analyze benchmark results for a target.
 class Analysis {
 public:
-  Analysis(const llvm::Target& Target, const InstructionBenchmarkClustering &Clustering);
+  Analysis(const llvm::Target &Target,
+           const InstructionBenchmarkClustering &Clustering);
 
   // Prints a csv of instructions for each cluster.
   llvm::Error printClusters(llvm::raw_ostream &OS) const;
 
- private:
-   void printInstructionRow(size_t ClusterId,  size_t PointId,
-                                   llvm::raw_ostream &OS) const;
+  // Find potential errors in the scheduling information given measurements.
+  llvm::Error printSchedClassInconsistencies(llvm::raw_ostream &OS) const;
+
+  void printInstructionRow(bool PrintSchedClass, size_t PointId,
 
-   const InstructionBenchmarkClustering & Clustering_;
-   std::unique_ptr<llvm::MCSubtargetInfo> SubtargetInfo_;
-   std::unique_ptr<llvm::MCInstrInfo> InstrInfo_;
-   std::unordered_map<std::string, unsigned> MnemonicToOpcode_;
+  // Builds a map of Sched Class -> indices of points that belong to the sched
+  // class.
+  std::unordered_map<unsigned, std::vector<size_t>>
+  makePointsPerSchedClass() const;
+
+  const InstructionBenchmarkClustering &Clustering_;
 };
 
 } // namespace exegesis
 
 #endif // LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H

llvm/trunk/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 "Analysis.h"
 #include "BenchmarkResult.h"
 #include "llvm/Support/FormatVariadic.h"
+#include <unordered_set>
 #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).
-void Analysis::printInstructionRow(const size_t ClusterId, const size_t PointId,
+void Analysis::printInstructionRow(const bool PrintSchedClass,
+                                   const size_t PointId,
                                    llvm::raw_ostream &OS) const {
   const InstructionBenchmark &Point = Clustering_.getPoints()[PointId];
-
-  OS << ClusterId << kCsvSep;
+  const auto &ClusterId = Clustering_.getClusterIdForPoint(PointId);
+  if (ClusterId.isNoise())
+    OS << "[noise]";
+  else if (ClusterId.isError())
+    OS << "[error]";
+  else
+    OS << ClusterId.getId();
+  OS << kCsvSep;
   writeCsvEscaped(OS, Point.Key.OpcodeName);
   OS << kCsvSep;
   writeCsvEscaped(OS, Point.Key.Config);
+  if (PrintSchedClass) {
     OS << kCsvSep;
     const auto OpcodeIt = MnemonicToOpcode_.find(Point.Key.OpcodeName);
     if (OpcodeIt != MnemonicToOpcode_.end()) {
-    const unsigned SchedClassId = InstrInfo_->get(OpcodeIt->second).getSchedClass();
+      const unsigned SchedClassId =
+          InstrInfo_->get(OpcodeIt->second).getSchedClass();
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
       const auto &SchedModel = SubtargetInfo_->getSchedModel();
       const llvm::MCSchedClassDesc *const SCDesc =
           SchedModel.getSchedClassDesc(SchedClassId);
       writeCsvEscaped(OS, SCDesc->Name);
 #else
       OS << SchedClassId;
 #endif
     }
+  }
   // 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";
 }
 
 Analysis::Analysis(const llvm::Target &Target,
                    const InstructionBenchmarkClustering &Clustering)
     : Clustering_(Clustering) {
   if (Clustering.getPoints().empty())
     return;
 
   InstrInfo_.reset(Target.createMCInstrInfo());
   const InstructionBenchmark &FirstPoint = Clustering.getPoints().front();
-  SubtargetInfo_.reset(Target.createMCSubtargetInfo(
-      FirstPoint.LLVMTriple, FirstPoint.CpuName, ""));
+  SubtargetInfo_.reset(Target.createMCSubtargetInfo(FirstPoint.LLVMTriple,
+                                                    FirstPoint.CpuName, ""));
 
   // Build an index of mnemonic->opcode.
   for (int I = 0, E = InstrInfo_->getNumOpcodes(); I < E; ++I)
     MnemonicToOpcode_.emplace(InstrInfo_->getName(I), I);
 }
 
 llvm::Error Analysis::printClusters(llvm::raw_ostream &OS) const {
   if (Clustering_.getPoints().empty())
     return llvm::Error::success();
 
   // Write the header.
   OS << "cluster_id" << kCsvSep << "opcode_name" << kCsvSep << "config"
      << kCsvSep << "sched_class";
   for (const auto &Measurement : Clustering_.getPoints().front().Measurements) {
     OS << kCsvSep;
     writeCsvEscaped(OS, Measurement.Key);
   }
   OS << "\n";
 
   // Write the points.
-  const auto& Clusters = Clustering_.getValidClusters();
+  const auto &Clusters = Clustering_.getValidClusters();
   for (size_t I = 0, E = Clusters.size(); I < E; ++I) {
     for (const size_t PointId : Clusters[I].PointIndices) {
-      printInstructionRow(I, PointId, OS);
+      printInstructionRow(/*PrintSchedClass*/ true, PointId, OS);
     }
     OS << "\n\n";
   }
   return llvm::Error::success();
 }
 
+std::unordered_map<unsigned, std::vector<size_t>>
+Analysis::makePointsPerSchedClass() const {
+  std::unordered_map<unsigned, std::vector<size_t>> PointsPerSchedClass;
+  const auto &Points = Clustering_.getPoints();
+  for (size_t PointId = 0, E = Points.size(); PointId < E; ++PointId) {
+    const InstructionBenchmark &Point = Points[PointId];
+    if (!Point.Error.empty())
+      continue;
+    const auto OpcodeIt = MnemonicToOpcode_.find(Point.Key.OpcodeName);
+    if (OpcodeIt == MnemonicToOpcode_.end())
+      continue;
+    const unsigned SchedClassId =
+        InstrInfo_->get(OpcodeIt->second).getSchedClass();
+    PointsPerSchedClass[SchedClassId].push_back(PointId);
+  }
+  return PointsPerSchedClass;
+}
+
+llvm::Error
+Analysis::printSchedClassInconsistencies(llvm::raw_ostream &OS) const {
+  // 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<size_t> ClustersForSchedClass;
+    for (const size_t PointId : SchedClassAndPoints.second) {
+      const auto &ClusterId = Clustering_.getClusterIdForPoint(PointId);
+      if (!ClusterId.isValid())
+        continue; // Ignore noise and errors.
+      ClustersForSchedClass.insert(ClusterId.getId());
+    }
+    if (ClustersForSchedClass.size() <= 1)
+      continue; // Nothing weird.
+
+    OS << "\nSched Class ";
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+    const auto &SchedModel = SubtargetInfo_->getSchedModel();
+    const llvm::MCSchedClassDesc *const SCDesc =
+        SchedModel.getSchedClassDesc(SchedClassAndPoints.first);
+    OS << SCDesc->Name;
+#else
+    OS << SchedClassAndPoints.first;
+#endif
+    OS << " contains instructions with distinct performance "
+          "characteristics, falling into "
+       << ClustersForSchedClass.size() << " clusters:\n";
+    for (const size_t PointId : SchedClassAndPoints.second) {
+      printInstructionRow(/*PrintSchedClass*/ false, PointId, OS);
+    }
+  }
+  return llvm::Error::success();
+}
+
 } // namespace exegesis

llvm/trunk/tools/llvm-exegesis/llvm-exegesis.cpp

void analysisMain() {
   std::error_code ErrorCode;
   llvm::raw_fd_ostream ClustersOS(AnalysisClustersFile, ErrorCode,
                                   llvm::sys::fs::F_RW);
   if (ErrorCode)
     llvm::report_fatal_error("cannot open out file: " + AnalysisClustersFile);
 
   if (auto Err = Analyzer.printClusters(ClustersOS))
     llvm::report_fatal_error(std::move(Err));
+
+  if (auto Err = Analyzer.printSchedClassInconsistencies(llvm::outs()))
+    llvm::report_fatal_error(std::move(Err));
 }
 
 } // namespace exegesis
 
 int main(int Argc, char **Argv) {
   llvm::cl::ParseCommandLineOptions(Argc, Argv, "");
 
   if (BenchmarkMode == BenchmarkModeE::Analysis) {
     exegesis::analysisMain();
   } else {
     exegesis::benchmarkMain();
   }
   return EXIT_SUCCESS;
 }