1//===- MCSchedule.cpp - Scheduling ------------------------------*- 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// This file defines the default scheduling model.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/MC/MCSchedule.h"
14#include "MCCLOptions.h"
15#include "llvm/ADT/APFloat.h"
16#include "llvm/ADT/APSInt.h"
17#include "llvm/MC/MCInst.h"
18#include "llvm/MC/MCInstrDesc.h"
19#include "llvm/MC/MCInstrInfo.h"
20#include "llvm/MC/MCSubtargetInfo.h"
21#include <optional>
22#include <type_traits>
23
24using namespace llvm;
25
26static constexpr float DefaultReservationStationScaleFactor = 1.0f;
27
28static_assert(std::is_trivial_v<MCSchedModel>,
29 "MCSchedModel is required to be a trivial type");
30const MCSchedModel MCSchedModel::Default = {.IssueWidth: DefaultIssueWidth,
31 .MicroOpBufferSize: DefaultMicroOpBufferSize,
32 .LoopMicroOpBufferSize: DefaultLoopMicroOpBufferSize,
33 .LoadLatency: DefaultLoadLatency,
34 .HighLatency: DefaultHighLatency,
35 .MispredictPenalty: DefaultMispredictPenalty,
36 .PostRAScheduler: false,
37 .CompleteModel: true,
38 /*EnableIntervals=*/false,
39 .ProcID: 0,
40 .ProcResourceTable: nullptr,
41 .SchedClassTable: nullptr,
42 .NumProcResourceKinds: 0,
43 .NumSchedClasses: 0,
44 .SchedClassNames: nullptr,
45 .InstrItineraries: nullptr,
46 .ExtraProcessorInfo: nullptr};
47
48int MCSchedModel::computeInstrLatency(const MCSubtargetInfo &STI,
49 const MCSchedClassDesc &SCDesc) {
50 int Latency = 0;
51 for (unsigned DefIdx = 0, DefEnd = SCDesc.NumWriteLatencyEntries;
52 DefIdx != DefEnd; ++DefIdx) {
53 // Lookup the definition's write latency in SubtargetInfo.
54 const MCWriteLatencyEntry *WLEntry =
55 STI.getWriteLatencyEntry(SC: &SCDesc, DefIdx);
56 // Early exit if we found an invalid latency.
57 if (WLEntry->Cycles < 0)
58 return WLEntry->Cycles;
59 Latency = std::max(a: Latency, b: static_cast<int>(WLEntry->Cycles));
60 }
61 return Latency;
62}
63
64int MCSchedModel::computeInstrLatency(const MCSubtargetInfo &STI,
65 unsigned SchedClass) const {
66 const MCSchedClassDesc &SCDesc = *getSchedClassDesc(SchedClassIdx: SchedClass);
67 if (!SCDesc.isValid())
68 return 0;
69 if (!SCDesc.isVariant())
70 return MCSchedModel::computeInstrLatency(STI, SCDesc);
71
72 llvm_unreachable("unsupported variant scheduling class");
73}
74
75int MCSchedModel::computeInstrLatency(const MCSubtargetInfo &STI,
76 const MCInstrInfo &MCII,
77 const MCInst &Inst) const {
78 return MCSchedModel::computeInstrLatency<MCSubtargetInfo, MCInstrInfo,
79 InstrItineraryData, MCInst>(
80 STI, MCII, Inst,
81 ResolveVariantSchedClass: [&](const MCSchedClassDesc *SCDesc) -> const MCSchedClassDesc * {
82 if (!SCDesc->isValid())
83 return nullptr;
84
85 unsigned CPUID = getProcessorID();
86 unsigned SchedClass = 0;
87 while (SCDesc->isVariant()) {
88 SchedClass =
89 STI.resolveVariantSchedClass(SchedClass, MI: &Inst, MCII: &MCII, CPUID);
90 SCDesc = getSchedClassDesc(SchedClassIdx: SchedClass);
91 }
92
93 if (!SchedClass) {
94 assert(false && "unsupported variant scheduling class");
95 return nullptr;
96 }
97
98 return SCDesc;
99 });
100}
101
102double
103MCSchedModel::getReciprocalThroughput(const MCSubtargetInfo &STI,
104 const MCSchedClassDesc &SCDesc) {
105 std::optional<double> MinThroughput;
106 const MCSchedModel &SM = STI.getSchedModel();
107 const MCWriteProcResEntry *I = STI.getWriteProcResBegin(SC: &SCDesc);
108 const MCWriteProcResEntry *E = STI.getWriteProcResEnd(SC: &SCDesc);
109 for (; I != E; ++I) {
110 if (!I->ReleaseAtCycle || I->ReleaseAtCycle == I->AcquireAtCycle)
111 continue;
112 assert(I->ReleaseAtCycle > I->AcquireAtCycle && "invalid resource segment");
113 unsigned NumUnits = SM.getProcResource(ProcResourceIdx: I->ProcResourceIdx)->NumUnits;
114 double Throughput =
115 double(NumUnits) / double(I->ReleaseAtCycle - I->AcquireAtCycle);
116 MinThroughput =
117 MinThroughput ? std::min(a: *MinThroughput, b: Throughput) : Throughput;
118 }
119 if (MinThroughput)
120 return 1.0 / *MinThroughput;
121
122 // If no throughput value was calculated, assume that we can execute at the
123 // maximum issue width scaled by number of micro-ops for the schedule class.
124 return ((double)SCDesc.NumMicroOps) / SM.IssueWidth;
125}
126
127double
128MCSchedModel::getReciprocalThroughput(const MCSubtargetInfo &STI,
129 const MCInstrInfo &MCII,
130 const MCInst &Inst) const {
131 unsigned SchedClass = MCII.get(Opcode: Inst.getOpcode()).getSchedClass();
132 const MCSchedClassDesc *SCDesc = getSchedClassDesc(SchedClassIdx: SchedClass);
133
134 // If there's no valid class, assume that the instruction executes/completes
135 // at the maximum issue width.
136 if (!SCDesc->isValid())
137 return 1.0 / IssueWidth;
138
139 unsigned CPUID = getProcessorID();
140 while (SCDesc->isVariant()) {
141 SchedClass = STI.resolveVariantSchedClass(SchedClass, MI: &Inst, MCII: &MCII, CPUID);
142 SCDesc = getSchedClassDesc(SchedClassIdx: SchedClass);
143 }
144
145 if (SchedClass)
146 return MCSchedModel::getReciprocalThroughput(STI, SCDesc: *SCDesc);
147
148 llvm_unreachable("unsupported variant scheduling class");
149}
150
151double
152MCSchedModel::getReciprocalThroughput(unsigned SchedClass,
153 const InstrItineraryData &IID) {
154 std::optional<double> Throughput;
155 const InstrStage *I = IID.beginStage(ItinClassIndx: SchedClass);
156 const InstrStage *E = IID.endStage(ItinClassIndx: SchedClass);
157 for (; I != E; ++I) {
158 if (!I->getCycles())
159 continue;
160 double Temp = llvm::popcount(Value: I->getUnits()) * 1.0 / I->getCycles();
161 Throughput = Throughput ? std::min(a: *Throughput, b: Temp) : Temp;
162 }
163 if (Throughput)
164 return 1.0 / *Throughput;
165
166 // If there are no execution resources specified for this class, then assume
167 // that it can execute at the maximum default issue width.
168 return 1.0 / DefaultIssueWidth;
169}
170
171unsigned
172MCSchedModel::getForwardingDelayCycles(ArrayRef<MCReadAdvanceEntry> Entries,
173 unsigned WriteResourceID) {
174 if (Entries.empty())
175 return 0;
176
177 int DelayCycles = 0;
178 for (const MCReadAdvanceEntry &E : Entries) {
179 if (E.WriteResourceID != WriteResourceID)
180 continue;
181 DelayCycles = std::min(a: DelayCycles, b: E.Cycles);
182 }
183
184 return std::abs(x: DelayCycles);
185}
186
187unsigned MCSchedModel::getBypassDelayCycles(const MCSubtargetInfo &STI,
188 const MCSchedClassDesc &SCDesc) {
189
190 ArrayRef<MCReadAdvanceEntry> Entries = STI.getReadAdvanceEntries(SC: SCDesc);
191 if (Entries.empty())
192 return 0;
193
194 unsigned MaxLatency = 0;
195 unsigned WriteResourceID = 0;
196 unsigned DefEnd = SCDesc.NumWriteLatencyEntries;
197
198 for (unsigned DefIdx = 0; DefIdx != DefEnd; ++DefIdx) {
199 // Lookup the definition's write latency in SubtargetInfo.
200 const MCWriteLatencyEntry *WLEntry =
201 STI.getWriteLatencyEntry(SC: &SCDesc, DefIdx);
202 unsigned Cycles = 0;
203 // If latency is Invalid (<0), consider 0 cycle latency
204 if (WLEntry->Cycles > 0)
205 Cycles = (unsigned)WLEntry->Cycles;
206 if (Cycles > MaxLatency) {
207 MaxLatency = Cycles;
208 WriteResourceID = WLEntry->WriteResourceID;
209 }
210 }
211
212 for (const MCReadAdvanceEntry &E : Entries) {
213 if (E.WriteResourceID == WriteResourceID)
214 return E.Cycles;
215 }
216
217 // Unable to find WriteResourceID in MCReadAdvanceEntry Entries
218 return 0;
219}
220
221/// Return the buffer size of the resource. If a positive scale factor
222/// is provided and the original buffer size is > 1, the size is scaled
223/// accordingly.
224int MCSchedModel::getResourceBufferSize(
225 unsigned ProcResourceIdx, float ReservationStationScaleFactor) const {
226 int BufferSize = getProcResource(ProcResourceIdx)->BufferSize;
227
228 // Skip scaling when factor is 1 (the default).
229 // Use native float comparison to avoid overhead on the hot fast
230 // path, as 1.0f is exactly representable
231 if (LLVM_LIKELY(ReservationStationScaleFactor ==
232 DefaultReservationStationScaleFactor))
233 return BufferSize;
234
235 // Skip scaling for special buffer sizes (-1,0,1)
236 if (BufferSize <= 1)
237 return BufferSize;
238
239 // Skip invalid (non-positive) scale factors
240 APFloat Scale(ReservationStationScaleFactor);
241 if (Scale.isNegative() || Scale.isZero())
242 return BufferSize;
243
244 // Scale and truncate the positive computed size towards zero
245 APFloat Product(static_cast<float>(BufferSize));
246 Product.multiply(RHS: Scale, RM: APFloat::rmTowardZero);
247 APSInt Result(32, /*IsUnsigned=*/false);
248 bool IsExact;
249 if (Product.convertToInteger(Result, RM: APFloat::rmTowardZero, IsExact: &IsExact) &
250 APFloat::opInvalidOp)
251 return BufferSize;
252 int Scaled = static_cast<int>(Result.getExtValue());
253
254 // Avoid producing special buffer sizes (-1,0,1)
255 if (Scaled <= 1)
256 return BufferSize;
257
258 return Scaled;
259}
260
261float MCSchedModel::getReservationStationScaleFactor(
262 const MCTargetOptions &Options) {
263 return getMCCLOptions(Options).sched_model_reservation_station_scale_factor;
264}
265