[llvm-exegesis] Analysis: Display idealized sched class port pressure.

[courbet]

Summary

Screenshot in phabricator diff.

[courbet]

[mgrang]

tools/llvm-exegesis/lib/Analysis.cpp

175–176

Please use llvm::sort instead of std::sort. See https://llvm.org/docs/CodingStandards.html#beware-of-non-deterministic-sorting-order-of-equal-elements.

469

Please use llvm::sort instead of std::sort. See https://llvm.org/docs/CodingStandards.html#beware-of-non-deterministic-sorting-order-of-equal-elements.

492

Same here.

[courbet]

use llvm::sort instead of std::sort

[gchatelet]

tools/llvm-exegesis/lib/Analysis.cpp

309

Bring last word on the same line.

468

Can you describe what Dense and Sparse pressure are?

485

algorithm

489

Running an example of help understand the algorithm here.

500

This pattern appears quite often in the next few lines DensePressure[Subunits[XXX]].
Maybe a lambda would help.

const auto getPressureForSubUnit = [](...){...};

Or an object to encapsulate the logic?

510

How about using a function instead of this big body?
It would make the return path easier to understand.

[courbet]

Address review comments.

[courbet]

Thanks, PTAL.

[courbet]

rebase

[courbet]

fix typo, use return instead of break.

[gchatelet]

tools/llvm-exegesis/lib/Analysis.cpp

494

budget

[courbet]

Thanks !

tools/llvm-exegesis/lib/Analysis.h

private:
   makePointsPerSchedClass() const;
 
   const InstructionBenchmarkClustering &Clustering_;
   std::unique_ptr<llvm::MCSubtargetInfo> SubtargetInfo_;
   std::unique_ptr<llvm::MCInstrInfo> InstrInfo_;
   std::unordered_map<std::string, unsigned> MnemonicToOpcode_;
 };
 
+// Computes the idealized ProcRes Unit pressure. This is the expected
+// distribution if the CPU scheduler can distribute the load as evenly as
+// possible.
+std::vector<std::pair<uint16_t, float>> computeIdealizedProcResPressure(
+    const llvm::MCSchedModel &SM,
+    llvm::SmallVector<llvm::MCWriteProcResEntry, 8> WPRS);
+
 } // 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 "Analysis.h"
 #include "BenchmarkResult.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/FormatVariadic.h"
 #include <unordered_set>
 #include <vector>
 
 namespace exegesis {
 
 static const char kCsvSep = ',';
 
Analysis::makePointsPerSchedClass() const {
   }
   return PointsPerSchedClass;
 }
 
 void Analysis::printSchedClassClustersHtml(std::vector<size_t> PointIds,
                                            llvm::raw_ostream &OS) const {
   assert(!PointIds.empty());
   // Sort the points by cluster id so that we can display them grouped by
   // cluster.
-  std::sort(PointIds.begin(), PointIds.end(),
+  llvm::sort(PointIds.begin(), PointIds.end(),
              [this](const size_t A, const size_t B) {
                return Clustering_.getClusterIdForPoint(A) <
                       Clustering_.getClusterIdForPoint(B);
              });
   const auto &Points = Clustering_.getPoints();
   OS << "<table class=\"sched-class-clusters\">";
   OS << "<tr><th>ClusterId</th><th>Opcode/Config</th>";
   for (const auto &Measurement : Points[PointIds[0]].Measurements) {
     OS << "<th>";
     if (Measurement.DebugString.empty())
       writeEscaped<kEscapeHtml>(OS, Measurement.Key);
     else
getNonRedundantWriteProcRes(const llvm::MCSchedClassDesc &SCDesc,
   }
   return Result;
 }
 
 void Analysis::printSchedClassDescHtml(const llvm::MCSchedClassDesc &SCDesc,
                                        llvm::raw_ostream &OS) const {
   OS << "<table class=\"sched-class-desc\">";
   OS << "<tr><th>Valid</th><th>Variant</th><th>uOps</th><th>Latency</"
-        "th><th>WriteProcRes</th></tr>";
+        "th><th>WriteProcRes</th><th title=\"This is the idealized unit "
+        "resource (port) pressure assuming ideal distribution\">Idealized "
+        "Resource "
+        "Pressure</th></tr>";
   if (SCDesc.isValid()) {
+    const auto &SM = SubtargetInfo_->getSchedModel();
     OS << "<tr><td>&#10004;</td>";
     OS << "<td>" << (SCDesc.isVariant() ? "&#10004;" : "&#10005;") << "</td>";
     OS << "<td>" << SCDesc.NumMicroOps << "</td>";
     // Latencies.
     OS << "<td><ul>";
     for (int I = 0, E = SCDesc.NumWriteLatencyEntries; I < E; ++I) {
       const auto *const Entry =
           SubtargetInfo_->getWriteLatencyEntry(&SCDesc, I);
       OS << "<li>" << Entry->Cycles;
       if (SCDesc.NumWriteLatencyEntries > 1) {
         // Dismabiguate if more than 1 latency.
         OS << " (WriteResourceID " << Entry->WriteResourceID << ")";
       }
       OS << "</li>";
     }
     OS << "</ul></td>";
     // WriteProcRes.
     OS << "<td><ul>";
-    for (const auto &WPR :
-         getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_)) {
+    const auto ProcRes = getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_);
+    for (const auto &WPR : ProcRes) {
+      OS << "<li><span class=\"mono\">";
+      writeEscaped<kEscapeHtml>(OS,
+                                SM.getProcResource(WPR.ProcResourceIdx)->Name);
+      OS << "</span>: " << WPR.Cycles << "</li>";
+    }
+    OS << "</ul></td>";
+    // Idealized port pressure.
+    OS << "<td><ul>";
+    for (const auto &Pressure : computeIdealizedProcResPressure(SM, ProcRes)) {
       OS << "<li><span class=\"mono\">";
       writeEscaped<kEscapeHtml>(OS, SubtargetInfo_->getSchedModel()
-                                        .getProcResource(WPR.ProcResourceIdx)
+                                        .getProcResource(Pressure.first)
                                         ->Name);
-      OS << "</span>: " << WPR.Cycles << "</li>";
+      OS << "</span>: ";
+      writeMeasurementValue<kEscapeHtml>(OS, Pressure.second);
+      OS << "</li>";
     }
     OS << "</ul></td>";
     OS << "</tr>";
   } else {
     OS << "<tr><td>&#10005;</td><td></td><td></td></tr>";
   }
   OS << "</table>";
 }
#endif
     printSchedClassDescHtml(*SCDesc, OS);
     OS << "</div>";
   }
 
   OS << "</body></html>";
   return llvm::Error::success();
 }
 
+std::vector<std::pair<uint16_t, float>> computeIdealizedProcResPressure(
+    const llvm::MCSchedModel &SM,
+    llvm::SmallVector<llvm::MCWriteProcResEntry, 8> WPRS) {
+  llvm::SmallVector<float, 32> DensePressure(SM.getNumProcResourceKinds());
+  llvm::sort(WPRS.begin(), WPRS.end(),
+             [](const llvm::MCWriteProcResEntry &A,
+                const llvm::MCWriteProcResEntry &B) {
+               return A.ProcResourceIdx < B.ProcResourceIdx;
+             });
+  for (const llvm::MCWriteProcResEntry &WPR : WPRS) {
+    // Get units for the entry.
+    const llvm::MCProcResourceDesc *const ProcResDesc =
+        SM.getProcResource(WPR.ProcResourceIdx);
+    if (ProcResDesc->SubUnitsIdxBegin == nullptr) {
+      // This is a ProcResUnit.
+      DensePressure[WPR.ProcResourceIdx] += WPR.Cycles;
+    } else {
+      // This is a ProcResGroup. Distribute as evenly as possible given the
+      // already existing distribution.
+      float RemainingPressure = WPR.Cycles;
+      // The algorith is as follows: while there is remaining pressure to
+      // distribute, find the subunits with minimal pressure, and distribute
+      // remaining pressure equally up to the pressure of the unit with
+      // second-to-minimal pressure.
+      llvm::SmallVector<uint16_t, 32> Subunits(ProcResDesc->SubUnitsIdxBegin,
+                                               ProcResDesc->SubUnitsIdxBegin +
+                                                   ProcResDesc->NumUnits);
+      llvm::sort(Subunits.begin(), Subunits.end(),
+                 [&DensePressure](const uint16_t A, const uint16_t B) {
+                   return DensePressure[A] < DensePressure[B];
+                 });
+      // Find the number of subunits with minimal pressure (they are at the
+      // front).
+      size_t NumMinimalSU = 1;
+      while (NumMinimalSU < Subunits.size() &&
+             DensePressure[Subunits[NumMinimalSU]] ==
+                 DensePressure[Subunits[0]]) {
+        ++NumMinimalSU;
+      }
+      while (RemainingPressure > 0.0f) {
+        if (NumMinimalSU == ProcResDesc->NumUnits) {
+          // All units are minimal, just distribute evenly and be done.
+          for (size_t I = 0; I < NumMinimalSU; ++I) {
+            DensePressure[Subunits[I]] += RemainingPressure / NumMinimalSU;
+          }
+          break;
+        }
+        // Distribute the remaining pressure equally.
+        const float MinimalPressure = DensePressure[Subunits[NumMinimalSU - 1]];
+        const float SecondToMinimalPressure =
+            DensePressure[Subunits[NumMinimalSU]];
+        assert(MinimalPressure < SecondToMinimalPressure);
+        const float Increment = SecondToMinimalPressure - MinimalPressure;
+        if (RemainingPressure <= NumMinimalSU * Increment) {
+          // There is not enough remaining pressure.
+          for (size_t I = 0; I < NumMinimalSU; ++I) {
+            DensePressure[Subunits[I]] += RemainingPressure / NumMinimalSU;
+          }
+          break;
+        }
+        // Bump all minimal pressure subunits to `SecondToMinimalPressure`.
+        for (size_t I = 0; I < NumMinimalSU; ++I) {
+          DensePressure[Subunits[I]] = SecondToMinimalPressure;
+          RemainingPressure -= SecondToMinimalPressure;
+        }
+        while (NumMinimalSU < Subunits.size() &&
+               DensePressure[Subunits[NumMinimalSU]] ==
+                   SecondToMinimalPressure) {
+          ++NumMinimalSU;
+        }
+      }
+    }
+  }
+  // Turn dense pressure into sparse pressure.
+  std::vector<std::pair<uint16_t, float>> Pressure;
+  for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
+    if (DensePressure[I] > 0.0f)
+      Pressure.emplace_back(I, DensePressure[I]);
+  }
+  return Pressure;
+}
+
 } // namespace exegesis

unittests/tools/llvm-exegesis/X86/AnalysisTest.cpp

+#include "Analysis.h"
+
+#include <cassert>
+#include <memory>
+
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Support/TargetSelect.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace exegesis {
+namespace {
+
+using testing::Pair;
+using testing::UnorderedElementsAre;
+
+class AnalysisTest : public ::testing::Test {
+protected:
+  AnalysisTest() {
+    const std::string TT = "x86_64-unknown-linux";
+    std::string error;
+    const llvm::Target *const TheTarget =
+        llvm::TargetRegistry::lookupTarget(TT, error);
+    if (!TheTarget) {
+      llvm::errs() << error << "\n";
+      return;
+    }
+    STI.reset(TheTarget->createMCSubtargetInfo(TT, "haswell", ""));
+
+    // Compute the ProxResIdx of ports unes in tests.
+    const auto &SM = STI->getSchedModel();
+    for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
+      const std::string Name = SM.getProcResource(I)->Name;
+      if (Name == "HWPort0") {
+        P0Idx = I;
+      } else if (Name == "HWPort1") {
+        P1Idx = I;
+      } else if (Name == "HWPort5") {
+        P5Idx = I;
+      } else if (Name == "HWPort6") {
+        P6Idx = I;
+      } else if (Name == "HWPort05") {
+        P05Idx = I;
+      } else if (Name == "HWPort0156") {
+        P0156Idx = I;
+      }
+    }
+    EXPECT_NE(P0Idx, 0);
+    EXPECT_NE(P1Idx, 0);
+    EXPECT_NE(P5Idx, 0);
+    EXPECT_NE(P6Idx, 0);
+    EXPECT_NE(P05Idx, 0);
+    EXPECT_NE(P0156Idx, 0);
+  }
+
+  static void SetUpTestCase() {
+    LLVMInitializeX86TargetInfo();
+    LLVMInitializeX86Target();
+    LLVMInitializeX86TargetMC();
+  }
+
+protected:
+  std::unique_ptr<const llvm::MCSubtargetInfo> STI;
+  uint16_t P0Idx = 0;
+  uint16_t P1Idx = 0;
+  uint16_t P5Idx = 0;
+  uint16_t P6Idx = 0;
+  uint16_t P05Idx = 0;
+  uint16_t P0156Idx = 0;
+};
+
+TEST_F(AnalysisTest, ComputeIdealizedProcResPressure_2P0) {
+  const auto Pressure =
+      computeIdealizedProcResPressure(STI->getSchedModel(), {{P0Idx, 2}});
+  EXPECT_THAT(Pressure, UnorderedElementsAre(Pair(P0Idx, 2.0)));
+}
+
+TEST_F(AnalysisTest, ComputeIdealizedProcResPressure_2P05) {
+  const auto Pressure =
+      computeIdealizedProcResPressure(STI->getSchedModel(), {{P05Idx, 2}});
+  EXPECT_THAT(Pressure,
+              UnorderedElementsAre(Pair(P0Idx, 1.0), Pair(P5Idx, 1.0)));
+}
+
+TEST_F(AnalysisTest, ComputeIdealizedProcResPressure_2P05_2P0156) {
+  const auto Pressure = computeIdealizedProcResPressure(
+      STI->getSchedModel(), {{P05Idx, 2}, {P0156Idx, 2}});
+  EXPECT_THAT(Pressure,
+              UnorderedElementsAre(Pair(P0Idx, 1.0), Pair(P1Idx, 1.0),
+                                   Pair(P5Idx, 1.0), Pair(P6Idx, 1.0)));
+}
+
+TEST_F(AnalysisTest, ComputeIdealizedProcResPressure_1P1_1P05_2P0156) {
+  const auto Pressure = computeIdealizedProcResPressure(
+      STI->getSchedModel(), {{P1Idx, 1}, {P05Idx, 1}, {P0156Idx, 2}});
+  EXPECT_THAT(Pressure,
+              UnorderedElementsAre(Pair(P0Idx, 1.0), Pair(P1Idx, 1.0),
+                                   Pair(P5Idx, 1.0), Pair(P6Idx, 1.0)));
+}
+
+} // namespace
+} // namespace exegesis

unittests/tools/llvm-exegesis/X86/CMakeLists.txt

set(LLVM_LINK_COMPONENTS
   Support
   Symbolize
   X86
   )
 
 add_llvm_unittest(LLVMExegesisX86Tests
   RegisterAliasingTest.cpp
   AssemblerTest.cpp
+  AnalysisTest.cpp
   )
 target_link_libraries(LLVMExegesisX86Tests PRIVATE LLVMExegesis)