xref: /openbsd-src/gnu/llvm/llvm/tools/llvm-exegesis/lib/SchedClassResolution.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
1 //===-- SchedClassResolution.cpp --------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "SchedClassResolution.h"
10 #include "BenchmarkResult.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/MC/MCAsmInfo.h"
13 #include "llvm/MCA/Support.h"
14 #include "llvm/Support/FormatVariadic.h"
15 #include <limits>
16 #include <unordered_set>
17 #include <vector>
18 
19 namespace llvm {
20 namespace exegesis {
21 
22 // Return the non-redundant list of WriteProcRes used by the given sched class.
23 // The scheduling model for LLVM is such that each instruction has a certain
24 // number of uops which consume resources which are described by WriteProcRes
25 // entries. Each entry describe how many cycles are spent on a specific ProcRes
26 // kind.
27 // For example, an instruction might have 3 uOps, one dispatching on P0
28 // (ProcResIdx=1) and two on P06 (ProcResIdx = 7).
29 // Note that LLVM additionally denormalizes resource consumption to include
30 // usage of super resources by subresources. So in practice if there exists a
31 // P016 (ProcResIdx=10), then the cycles consumed by P0 are also consumed by
32 // P06 (ProcResIdx = 7) and P016 (ProcResIdx = 10), and the resources consumed
33 // by P06 are also consumed by P016. In the figure below, parenthesized cycles
34 // denote implied usage of superresources by subresources:
35 //            P0      P06    P016
36 //     uOp1    1      (1)     (1)
37 //     uOp2            1      (1)
38 //     uOp3            1      (1)
39 //     =============================
40 //             1       3       3
41 // Eventually we end up with three entries for the WriteProcRes of the
42 // instruction:
43 //    {ProcResIdx=1,  Cycles=1}  // P0
44 //    {ProcResIdx=7,  Cycles=3}  // P06
45 //    {ProcResIdx=10, Cycles=3}  // P016
46 //
47 // Note that in this case, P016 does not contribute any cycles, so it would
48 // be removed by this function.
49 // FIXME: Merge this with the equivalent in llvm-mca.
50 static SmallVector<MCWriteProcResEntry, 8>
getNonRedundantWriteProcRes(const MCSchedClassDesc & SCDesc,const MCSubtargetInfo & STI)51 getNonRedundantWriteProcRes(const MCSchedClassDesc &SCDesc,
52                             const MCSubtargetInfo &STI) {
53   SmallVector<MCWriteProcResEntry, 8> Result;
54   const auto &SM = STI.getSchedModel();
55   const unsigned NumProcRes = SM.getNumProcResourceKinds();
56 
57   // Collect resource masks.
58   SmallVector<uint64_t> ProcResourceMasks(NumProcRes);
59   mca::computeProcResourceMasks(SM, ProcResourceMasks);
60 
61   // Sort entries by smaller resources for (basic) topological ordering.
62   using ResourceMaskAndEntry = std::pair<uint64_t, const MCWriteProcResEntry *>;
63   SmallVector<ResourceMaskAndEntry, 8> ResourceMaskAndEntries;
64   for (const auto *WPR = STI.getWriteProcResBegin(&SCDesc),
65                   *const WPREnd = STI.getWriteProcResEnd(&SCDesc);
66        WPR != WPREnd; ++WPR) {
67     uint64_t Mask = ProcResourceMasks[WPR->ProcResourceIdx];
68     ResourceMaskAndEntries.push_back({Mask, WPR});
69   }
70   sort(ResourceMaskAndEntries,
71        [](const ResourceMaskAndEntry &A, const ResourceMaskAndEntry &B) {
72          unsigned popcntA = llvm::popcount(A.first);
73          unsigned popcntB = llvm::popcount(B.first);
74          if (popcntA < popcntB)
75            return true;
76          if (popcntA > popcntB)
77            return false;
78          return A.first < B.first;
79        });
80 
81   SmallVector<float, 32> ProcResUnitUsage(NumProcRes);
82   for (const ResourceMaskAndEntry &Entry : ResourceMaskAndEntries) {
83     const MCWriteProcResEntry *WPR = Entry.second;
84     const MCProcResourceDesc *const ProcResDesc =
85         SM.getProcResource(WPR->ProcResourceIdx);
86     if (ProcResDesc->SubUnitsIdxBegin == nullptr) {
87       // This is a ProcResUnit.
88       Result.push_back({WPR->ProcResourceIdx, WPR->Cycles});
89       ProcResUnitUsage[WPR->ProcResourceIdx] += WPR->Cycles;
90     } else {
91       // This is a ProcResGroup. First see if it contributes any cycles or if
92       // it has cycles just from subunits.
93       float RemainingCycles = WPR->Cycles;
94       for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin;
95            SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits;
96            ++SubResIdx) {
97         RemainingCycles -= ProcResUnitUsage[*SubResIdx];
98       }
99       if (RemainingCycles < 0.01f) {
100         // The ProcResGroup contributes no cycles of its own.
101         continue;
102       }
103       // The ProcResGroup contributes `RemainingCycles` cycles of its own.
104       Result.push_back({WPR->ProcResourceIdx,
105                         static_cast<uint16_t>(std::round(RemainingCycles))});
106       // Spread the remaining cycles over all subunits.
107       for (const auto *SubResIdx = ProcResDesc->SubUnitsIdxBegin;
108            SubResIdx != ProcResDesc->SubUnitsIdxBegin + ProcResDesc->NumUnits;
109            ++SubResIdx) {
110         ProcResUnitUsage[*SubResIdx] += RemainingCycles / ProcResDesc->NumUnits;
111       }
112     }
113   }
114   return Result;
115 }
116 
117 // Distributes a pressure budget as evenly as possible on the provided subunits
118 // given the already existing port pressure distribution.
119 //
120 // The algorithm is as follows: while there is remaining pressure to
121 // distribute, find the subunits with minimal pressure, and distribute
122 // remaining pressure equally up to the pressure of the unit with
123 // second-to-minimal pressure.
124 // For example, let's assume we want to distribute 2*P1256
125 // (Subunits = [P1,P2,P5,P6]), and the starting DensePressure is:
126 //     DensePressure =        P0   P1   P2   P3   P4   P5   P6   P7
127 //                           0.1  0.3  0.2  0.0  0.0  0.5  0.5  0.5
128 //     RemainingPressure = 2.0
129 // We sort the subunits by pressure:
130 //     Subunits = [(P2,p=0.2), (P1,p=0.3), (P5,p=0.5), (P6, p=0.5)]
131 // We'll first start by the subunits with minimal pressure, which are at
132 // the beginning of the sorted array. In this example there is one (P2).
133 // The subunit with second-to-minimal pressure is the next one in the
134 // array (P1). So we distribute 0.1 pressure to P2, and remove 0.1 cycles
135 // from the budget.
136 //     Subunits = [(P2,p=0.3), (P1,p=0.3), (P5,p=0.5), (P5,p=0.5)]
137 //     RemainingPressure = 1.9
138 // We repeat this process: distribute 0.2 pressure on each of the minimal
139 // P2 and P1, decrease budget by 2*0.2:
140 //     Subunits = [(P2,p=0.5), (P1,p=0.5), (P5,p=0.5), (P5,p=0.5)]
141 //     RemainingPressure = 1.5
142 // There are no second-to-minimal subunits so we just share the remaining
143 // budget (1.5 cycles) equally:
144 //     Subunits = [(P2,p=0.875), (P1,p=0.875), (P5,p=0.875), (P5,p=0.875)]
145 //     RemainingPressure = 0.0
146 // We stop as there is no remaining budget to distribute.
distributePressure(float RemainingPressure,SmallVector<uint16_t,32> Subunits,SmallVector<float,32> & DensePressure)147 static void distributePressure(float RemainingPressure,
148                                SmallVector<uint16_t, 32> Subunits,
149                                SmallVector<float, 32> &DensePressure) {
150   // Find the number of subunits with minimal pressure (they are at the
151   // front).
152   sort(Subunits, [&DensePressure](const uint16_t A, const uint16_t B) {
153     return DensePressure[A] < DensePressure[B];
154   });
155   const auto getPressureForSubunit = [&DensePressure,
156                                       &Subunits](size_t I) -> float & {
157     return DensePressure[Subunits[I]];
158   };
159   size_t NumMinimalSU = 1;
160   while (NumMinimalSU < Subunits.size() &&
161          getPressureForSubunit(NumMinimalSU) == getPressureForSubunit(0)) {
162     ++NumMinimalSU;
163   }
164   while (RemainingPressure > 0.0f) {
165     if (NumMinimalSU == Subunits.size()) {
166       // All units are minimal, just distribute evenly and be done.
167       for (size_t I = 0; I < NumMinimalSU; ++I) {
168         getPressureForSubunit(I) += RemainingPressure / NumMinimalSU;
169       }
170       return;
171     }
172     // Distribute the remaining pressure equally.
173     const float MinimalPressure = getPressureForSubunit(NumMinimalSU - 1);
174     const float SecondToMinimalPressure = getPressureForSubunit(NumMinimalSU);
175     assert(MinimalPressure < SecondToMinimalPressure);
176     const float Increment = SecondToMinimalPressure - MinimalPressure;
177     if (RemainingPressure <= NumMinimalSU * Increment) {
178       // There is not enough remaining pressure.
179       for (size_t I = 0; I < NumMinimalSU; ++I) {
180         getPressureForSubunit(I) += RemainingPressure / NumMinimalSU;
181       }
182       return;
183     }
184     // Bump all minimal pressure subunits to `SecondToMinimalPressure`.
185     for (size_t I = 0; I < NumMinimalSU; ++I) {
186       getPressureForSubunit(I) = SecondToMinimalPressure;
187       RemainingPressure -= SecondToMinimalPressure;
188     }
189     while (NumMinimalSU < Subunits.size() &&
190            getPressureForSubunit(NumMinimalSU) == SecondToMinimalPressure) {
191       ++NumMinimalSU;
192     }
193   }
194 }
195 
196 std::vector<std::pair<uint16_t, float>>
computeIdealizedProcResPressure(const MCSchedModel & SM,SmallVector<MCWriteProcResEntry,8> WPRS)197 computeIdealizedProcResPressure(const MCSchedModel &SM,
198                                 SmallVector<MCWriteProcResEntry, 8> WPRS) {
199   // DensePressure[I] is the port pressure for Proc Resource I.
200   SmallVector<float, 32> DensePressure(SM.getNumProcResourceKinds());
201   sort(WPRS, [](const MCWriteProcResEntry &A, const MCWriteProcResEntry &B) {
202     return A.ProcResourceIdx < B.ProcResourceIdx;
203   });
204   for (const MCWriteProcResEntry &WPR : WPRS) {
205     // Get units for the entry.
206     const MCProcResourceDesc *const ProcResDesc =
207         SM.getProcResource(WPR.ProcResourceIdx);
208     if (ProcResDesc->SubUnitsIdxBegin == nullptr) {
209       // This is a ProcResUnit.
210       DensePressure[WPR.ProcResourceIdx] += WPR.Cycles;
211     } else {
212       // This is a ProcResGroup.
213       SmallVector<uint16_t, 32> Subunits(ProcResDesc->SubUnitsIdxBegin,
214                                          ProcResDesc->SubUnitsIdxBegin +
215                                              ProcResDesc->NumUnits);
216       distributePressure(WPR.Cycles, Subunits, DensePressure);
217     }
218   }
219   // Turn dense pressure into sparse pressure by removing zero entries.
220   std::vector<std::pair<uint16_t, float>> Pressure;
221   for (unsigned I = 0, E = SM.getNumProcResourceKinds(); I < E; ++I) {
222     if (DensePressure[I] > 0.0f)
223       Pressure.emplace_back(I, DensePressure[I]);
224   }
225   return Pressure;
226 }
227 
ResolvedSchedClass(const MCSubtargetInfo & STI,unsigned ResolvedSchedClassId,bool WasVariant)228 ResolvedSchedClass::ResolvedSchedClass(const MCSubtargetInfo &STI,
229                                        unsigned ResolvedSchedClassId,
230                                        bool WasVariant)
231     : SchedClassId(ResolvedSchedClassId),
232       SCDesc(STI.getSchedModel().getSchedClassDesc(ResolvedSchedClassId)),
233       WasVariant(WasVariant),
234       NonRedundantWriteProcRes(getNonRedundantWriteProcRes(*SCDesc, STI)),
235       IdealizedProcResPressure(computeIdealizedProcResPressure(
236           STI.getSchedModel(), NonRedundantWriteProcRes)) {
237   assert((SCDesc == nullptr || !SCDesc->isVariant()) &&
238          "ResolvedSchedClass should never be variant");
239 }
240 
ResolveVariantSchedClassId(const MCSubtargetInfo & STI,const MCInstrInfo & InstrInfo,unsigned SchedClassId,const MCInst & MCI)241 static unsigned ResolveVariantSchedClassId(const MCSubtargetInfo &STI,
242                                            const MCInstrInfo &InstrInfo,
243                                            unsigned SchedClassId,
244                                            const MCInst &MCI) {
245   const auto &SM = STI.getSchedModel();
246   while (SchedClassId && SM.getSchedClassDesc(SchedClassId)->isVariant()) {
247     SchedClassId = STI.resolveVariantSchedClass(SchedClassId, &MCI, &InstrInfo,
248                                                 SM.getProcessorID());
249   }
250   return SchedClassId;
251 }
252 
253 std::pair<unsigned /*SchedClassId*/, bool /*WasVariant*/>
resolveSchedClassId(const MCSubtargetInfo & SubtargetInfo,const MCInstrInfo & InstrInfo,const MCInst & MCI)254 ResolvedSchedClass::resolveSchedClassId(const MCSubtargetInfo &SubtargetInfo,
255                                         const MCInstrInfo &InstrInfo,
256                                         const MCInst &MCI) {
257   unsigned SchedClassId = InstrInfo.get(MCI.getOpcode()).getSchedClass();
258   const bool WasVariant = SchedClassId && SubtargetInfo.getSchedModel()
259                                               .getSchedClassDesc(SchedClassId)
260                                               ->isVariant();
261   SchedClassId =
262       ResolveVariantSchedClassId(SubtargetInfo, InstrInfo, SchedClassId, MCI);
263   return std::make_pair(SchedClassId, WasVariant);
264 }
265 
266 // Returns a ProxResIdx by id or name.
findProcResIdx(const MCSubtargetInfo & STI,const StringRef NameOrId)267 static unsigned findProcResIdx(const MCSubtargetInfo &STI,
268                                const StringRef NameOrId) {
269   // Interpret the key as an ProcResIdx.
270   unsigned ProcResIdx = 0;
271   if (to_integer(NameOrId, ProcResIdx, 10))
272     return ProcResIdx;
273   // Interpret the key as a ProcRes name.
274   const auto &SchedModel = STI.getSchedModel();
275   for (int I = 0, E = SchedModel.getNumProcResourceKinds(); I < E; ++I) {
276     if (NameOrId == SchedModel.getProcResource(I)->Name)
277       return I;
278   }
279   return 0;
280 }
281 
getAsPoint(InstructionBenchmark::ModeE Mode,const MCSubtargetInfo & STI,ArrayRef<PerInstructionStats> Representative) const282 std::vector<BenchmarkMeasure> ResolvedSchedClass::getAsPoint(
283     InstructionBenchmark::ModeE Mode, const MCSubtargetInfo &STI,
284     ArrayRef<PerInstructionStats> Representative) const {
285   const size_t NumMeasurements = Representative.size();
286 
287   std::vector<BenchmarkMeasure> SchedClassPoint(NumMeasurements);
288 
289   if (Mode == InstructionBenchmark::Latency) {
290     assert(NumMeasurements == 1 && "Latency is a single measure.");
291     BenchmarkMeasure &LatencyMeasure = SchedClassPoint[0];
292 
293     // Find the latency.
294     LatencyMeasure.PerInstructionValue = 0.0;
295 
296     for (unsigned I = 0; I < SCDesc->NumWriteLatencyEntries; ++I) {
297       const MCWriteLatencyEntry *const WLE =
298           STI.getWriteLatencyEntry(SCDesc, I);
299       LatencyMeasure.PerInstructionValue =
300           std::max<double>(LatencyMeasure.PerInstructionValue, WLE->Cycles);
301     }
302   } else if (Mode == InstructionBenchmark::Uops) {
303     for (auto I : zip(SchedClassPoint, Representative)) {
304       BenchmarkMeasure &Measure = std::get<0>(I);
305       const PerInstructionStats &Stats = std::get<1>(I);
306 
307       StringRef Key = Stats.key();
308       uint16_t ProcResIdx = findProcResIdx(STI, Key);
309       if (ProcResIdx > 0) {
310         // Find the pressure on ProcResIdx `Key`.
311         const auto ProcResPressureIt =
312             llvm::find_if(IdealizedProcResPressure,
313                           [ProcResIdx](const std::pair<uint16_t, float> &WPR) {
314                             return WPR.first == ProcResIdx;
315                           });
316         Measure.PerInstructionValue =
317             ProcResPressureIt == IdealizedProcResPressure.end()
318                 ? 0.0
319                 : ProcResPressureIt->second;
320       } else if (Key == "NumMicroOps") {
321         Measure.PerInstructionValue = SCDesc->NumMicroOps;
322       } else {
323         errs() << "expected `key` to be either a ProcResIdx or a ProcRes "
324                   "name, got "
325                << Key << "\n";
326         return {};
327       }
328     }
329   } else if (Mode == InstructionBenchmark::InverseThroughput) {
330     assert(NumMeasurements == 1 && "Inverse Throughput is a single measure.");
331     BenchmarkMeasure &RThroughputMeasure = SchedClassPoint[0];
332 
333     RThroughputMeasure.PerInstructionValue =
334         MCSchedModel::getReciprocalThroughput(STI, *SCDesc);
335   } else {
336     llvm_unreachable("unimplemented measurement matching mode");
337   }
338 
339   return SchedClassPoint;
340 }
341 
342 } // namespace exegesis
343 } // namespace llvm
344