Index: tools/llvm-exegesis/lib/Analysis.h =================================================================== --- tools/llvm-exegesis/lib/Analysis.h +++ tools/llvm-exegesis/lib/Analysis.h @@ -58,6 +58,13 @@ std::unordered_map 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> computeIdealizedProcResPressure( + const llvm::MCSchedModel &SM, + llvm::SmallVector WPRS); + } // namespace exegesis #endif // LLVM_TOOLS_LLVM_EXEGESIS_CLUSTERING_H Index: tools/llvm-exegesis/lib/Analysis.cpp =================================================================== --- tools/llvm-exegesis/lib/Analysis.cpp +++ tools/llvm-exegesis/lib/Analysis.cpp @@ -9,6 +9,7 @@ #include "Analysis.h" #include "BenchmarkResult.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Support/FormatVariadic.h" #include #include @@ -172,11 +173,11 @@ assert(!PointIds.empty()); // Sort the points by cluster id so that we can display them grouped by // cluster. - std::sort(PointIds.begin(), PointIds.end(), - [this](const size_t A, const size_t B) { - return Clustering_.getClusterIdForPoint(A) < - Clustering_.getClusterIdForPoint(B); - }); + 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 << ""; OS << ""; @@ -303,8 +304,11 @@ llvm::raw_ostream &OS) const { OS << "
ClusterIdOpcode/Config
"; OS << ""; + "th>"; if (SCDesc.isValid()) { + const auto &SM = SubtargetInfo_->getSchedModel(); OS << ""; OS << ""; OS << ""; @@ -323,13 +327,24 @@ OS << ""; // WriteProcRes. OS << ""; + // Idealized port pressure. + OS << ""; OS << ""; @@ -446,4 +461,118 @@ 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 bidget to distribute. +void distributePressure(float RemainingPressure, + llvm::SmallVector Subunits, + llvm::SmallVector &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; + } + break; + } + // 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; + } + break; + } + // 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> computeIdealizedProcResPressure( + const llvm::MCSchedModel &SM, + llvm::SmallVector WPRS) { + // DensePressure[I] is the port pressure for Proc Resource I. + llvm::SmallVector 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 Subunits(ProcResDesc->SubUnitsIdxBegin, + ProcResDesc->SubUnitsIdxBegin + + ProcResDesc->NumUnits); + distributePressure(WPR.Cycles, Subunits, DensePressure); + } + } + // Turn dense pressure into sparse pressure by removing zero entries. + std::vector> 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 Index: unittests/tools/llvm-exegesis/X86/AnalysisTest.cpp =================================================================== --- /dev/null +++ unittests/tools/llvm-exegesis/X86/AnalysisTest.cpp @@ -0,0 +1,102 @@ +#include "Analysis.h" + +#include +#include + +#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 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 Index: unittests/tools/llvm-exegesis/X86/CMakeLists.txt =================================================================== --- unittests/tools/llvm-exegesis/X86/CMakeLists.txt +++ unittests/tools/llvm-exegesis/X86/CMakeLists.txt @@ -16,5 +16,6 @@ add_llvm_unittest(LLVMExegesisX86Tests RegisterAliasingTest.cpp AssemblerTest.cpp + AnalysisTest.cpp ) target_link_libraries(LLVMExegesisX86Tests PRIVATE LLVMExegesis)
ValidVariantuOpsLatencyWriteProcRes
WriteProcResIdealized " + "Resource Pressure
✔" << (SCDesc.isVariant() ? "✔" : "✕") << "" << SCDesc.NumMicroOps << "
    "; - for (const auto &WPR : - getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_)) { + const auto ProcRes = getNonRedundantWriteProcRes(SCDesc, *SubtargetInfo_); + for (const auto &WPR : ProcRes) { + OS << "
  • "; + writeEscaped(OS, + SM.getProcResource(WPR.ProcResourceIdx)->Name); + OS << ": " << WPR.Cycles << "
    • "; + } + OS << "
    "; + for (const auto &Pressure : computeIdealizedProcResPressure(SM, ProcRes)) { OS << "
  • "; writeEscaped(OS, SubtargetInfo_->getSchedModel() - .getProcResource(WPR.ProcResourceIdx) + .getProcResource(Pressure.first) ->Name); - OS << ": " << WPR.Cycles << "
    • "; + OS << ": "; + writeMeasurementValue(OS, Pressure.second); + OS << ""; } OS << "