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

[courbet]

Summary

Screenshot in phabricator diff.

[courbet]

[mgrang]

tools/llvm-exegesis/lib/Analysis.cpp

175 ↗

(On Diff #148410)

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

468 ↗

(On Diff #148410)

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

491 ↗

(On Diff #148410)

Same here.

[courbet]

use llvm::sort instead of std::sort

[gchatelet]

tools/llvm-exegesis/lib/Analysis.cpp

309 ↗

(On Diff #148552)

Bring last word on the same line.

468 ↗

(On Diff #148552)

Can you describe what Dense and Sparse pressure are?

485 ↗

(On Diff #148552)

algorithm

489 ↗

(On Diff #148552)

Running an example of help understand the algorithm here.

500 ↗

(On Diff #148552)

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 ↗

(On Diff #148552)

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

493 ↗

(On Diff #149458)

budget

[courbet]

Thanks !

llvm/trunk/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

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/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();
 }
 
+// Distributes a pressure budget as evenly as possible on the provided subunits
+// given the already existing port pressure distribution.
+//
+// The algorithm 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.
+// For example, let's assume we want to distribute 2*P1256
+// (Subunits = [P1,P2,P5,P6]), and the starting DensePressure is:
+//     DensePressure =        P0   P1   P2   P3   P4   P5   P6   P7
+//                           0.1  0.3  0.2  0.0  0.0  0.5  0.5  0.5
+//     RemainingPressure = 2.0
+// We sort the subunits by pressure:
+//     Subunits = [(P2,p=0.2), (P1,p=0.3), (P5,p=0.5), (P6, p=0.5)]
+// We'll first start by the subunits with minimal pressure, which are at
+// the beginning of the sorted array. In this example there is one (P2).
+// The subunit with second-to-minimal pressure is the next one in the
+// array (P1). So we distribute 0.1 pressure to P2, and remove 0.1 cycles
+// from the budget.
+//     Subunits = [(P2,p=0.3), (P1,p=0.3), (P5,p=0.5), (P5,p=0.5)]
+//     RemainingPressure = 1.9
+// We repeat this process: distribute 0.2 pressure on each of the minimal
+// P2 and P1, decrease budget by 2*0.2:
+//     Subunits = [(P2,p=0.5), (P1,p=0.5), (P5,p=0.5), (P5,p=0.5)]
+//     RemainingPressure = 1.5
+// There are no second-to-minimal subunits so we just share the remaining
+// budget (1.5 cycles) equally:
+//     Subunits = [(P2,p=0.875), (P1,p=0.875), (P5,p=0.875), (P5,p=0.875)]
+//     RemainingPressure = 0.0
+// We stop as there is no remaining budget to distribute.
+void distributePressure(float RemainingPressure,
+                        llvm::SmallVector<uint16_t, 32> Subunits,
+                        llvm::SmallVector<float, 32> &DensePressure) {
+  // Find the number of subunits with minimal pressure (they are at the
+  // front).
+  llvm::sort(Subunits.begin(), Subunits.end(),
+             [&DensePressure](const uint16_t A, const uint16_t B) {
+               return DensePressure[A] < DensePressure[B];
+             });
+  const auto getPressureForSubunit = [&DensePressure,
+                                      &Subunits](size_t I) -> float & {
+    return DensePressure[Subunits[I]];
+  };
+  size_t NumMinimalSU = 1;
+  while (NumMinimalSU < Subunits.size() &&
+         getPressureForSubunit(NumMinimalSU) == getPressureForSubunit(0)) {
+    ++NumMinimalSU;
+  }
+  while (RemainingPressure > 0.0f) {
+    if (NumMinimalSU == Subunits.size()) {
+      // All units are minimal, just distribute evenly and be done.
+      for (size_t I = 0; I < NumMinimalSU; ++I) {
+        getPressureForSubunit(I) += RemainingPressure / NumMinimalSU;
+      }
+      return;
+    }
+    // Distribute the remaining pressure equally.
+    const float MinimalPressure = getPressureForSubunit(NumMinimalSU - 1);
+    const float SecondToMinimalPressure = getPressureForSubunit(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) {
+        getPressureForSubunit(I) += RemainingPressure / NumMinimalSU;
+      }
+      return;
+    }
+    // Bump all minimal pressure subunits to `SecondToMinimalPressure`.
+    for (size_t I = 0; I < NumMinimalSU; ++I) {
+      getPressureForSubunit(I) = SecondToMinimalPressure;
+      RemainingPressure -= SecondToMinimalPressure;
+    }
+    while (NumMinimalSU < Subunits.size() &&
+           getPressureForSubunit(NumMinimalSU) == SecondToMinimalPressure) {
+      ++NumMinimalSU;
+    }
+  }
+}
+
+std::vector<std::pair<uint16_t, float>> computeIdealizedProcResPressure(
+    const llvm::MCSchedModel &SM,
+    llvm::SmallVector<llvm::MCWriteProcResEntry, 8> WPRS) {
+  // DensePressure[I] is the port pressure for Proc Resource I.
+  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.
+      llvm::SmallVector<uint16_t, 32> Subunits(ProcResDesc->SubUnitsIdxBegin,
+                                               ProcResDesc->SubUnitsIdxBegin +
+                                                   ProcResDesc->NumUnits);
+      distributePressure(WPR.Cycles, Subunits, DensePressure);
+    }
+  }
+  // Turn dense pressure into sparse pressure by removing zero entries.
+  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

llvm/trunk/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

llvm/trunk/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)