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