[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.

468

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

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.

467

Can you describe what Dense and Sparse pressure are?

484

algorithm

488

Running an example of help understand the algorithm here.

499

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?

509

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

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();
 }
 
+// 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

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)