1//===- AMDGPUCoExecSchedStrategy.h - CoExec Scheduling Strategy -*- 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/// \file
10/// Coexecution-focused scheduling strategy for AMDGPU.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIB_TARGET_AMDGPU_AMDGPUCOEXECSCHEDSTRATEGY_H
15#define LLVM_LIB_TARGET_AMDGPU_AMDGPUCOEXECSCHEDSTRATEGY_H
16
17#include "AMDGPUCoExecInfo.h"
18#include "GCNSchedStrategy.h"
19#include "llvm/CodeGen/MachineScheduler.h"
20
21namespace llvm {
22
23namespace AMDGPU {
24namespace DefaultBufferSizes {
25constexpr unsigned DS = 16;
26} // namespace DefaultBufferSizes
27
28/// AMDGPU-specific scheduling decision reasons. These provide more granularity
29/// than the generic CandReason enum for debugging purposes.
30enum class AMDGPUSchedReason : uint8_t {
31 None,
32 Stall,
33 MemoryPipeline,
34 CritResourceBalance, // tryCriticalResource chose based on resource pressure
35 CritResourceDep, // tryCriticalResourceDependency chose based on enabling
36 NUM_REASONS
37};
38
39inline StringRef getReasonName(AMDGPUSchedReason R) {
40 switch (R) {
41 case AMDGPUSchedReason::None:
42 return "None";
43 case AMDGPUSchedReason::Stall:
44 return "Stall";
45 case AMDGPUSchedReason::MemoryPipeline:
46 return "MemoryPipeline";
47 case AMDGPUSchedReason::CritResourceBalance:
48 return "CritResource";
49 case AMDGPUSchedReason::CritResourceDep:
50 return "CritResourceDep";
51 case AMDGPUSchedReason::NUM_REASONS:
52 llvm_unreachable("Unknown AMDGPUSchedReason");
53 }
54 llvm_unreachable("Unknown AMDGPUSchedReason");
55}
56
57} // End namespace AMDGPU
58
59//===----------------------------------------------------------------------===//
60// Hardware Unit Information
61//===----------------------------------------------------------------------===//
62
63/// HardwareUnitInfo is a wrapper class which maps to some real hardware
64/// resource. This is used to model hardware resource pressure per region, and
65/// guide scheduling heuristics.
66class HardwareUnitInfo {
67private:
68 /// PrioritySUs maintains a list of the SUs we want to prioritize scheduling
69 /// for this HardwareUnit. This is used for agreement between
70 /// tryCriticalResourceDependency and tryCriticalResource: we schedule the
71 /// dependencies for a SU on critical resource, then schedule that same SU on
72 /// the critical resource. This agreement results in shorter live ranges and
73 /// more regular HardwareUnit access patterns. SUs are prioritized based on
74 /// depth for top-down scheduling.
75 SmallSetVector<SUnit *, 16> PrioritySUs;
76 /// All the SUs in the region that consume this resource.
77 SmallSetVector<SUnit *, 16> AllSUs;
78 /// All the SUs for this HardwareUnit that have already been scheduled.
79 SmallVector<SUnit *, 16> ScheduledSUs;
80 /// The total number of busy cycles for this HardwareUnit for a given region.
81 unsigned TotalCycles = 0;
82 /// InstructionFlavor mapping.
83 AMDGPU::InstructionFlavor Type;
84 /// Whether or not instructions on this HardwareUnit may produce a window in
85 /// which instructions in other HardwareUnits can coexecute. For example, WMMA
86 /// / MFMA instructions may take multiple cycles, which may be overlapped with
87 /// instructions on other HardwareUnits.
88 bool ProducesCoexecWindow = false;
89 /// How many instructions can be held simultaneously for this HardwareUnit.
90 /// A value of 0 means there is no limit. A value of 1 models an unbuffered
91 /// resource with a single in-flight instruction.
92 ///
93 /// This may approximate the hardware. For example, for LDS instructions
94 /// it is a well-known phenomena that oversubscribing the LDS unit results in
95 /// longer latency for the LDS instructions. While it is true that there is a
96 /// hard limit to the amount of simulatenous in-flight LDS instructions, good
97 /// scheduling would also cool off the LDS to avoid other forms of hardware
98 /// contention and increasing LDS latency. Thus, we limit the amount of LDS
99 /// instructions we are willing to schedule close together, though this does
100 /// not correspond 1:1 with a hardware mechanism.
101 unsigned BufferSize = 0;
102 /// How many cycles it takes for an instruction to clear the buffer.
103 ///
104 /// Again, this may be an apprxoimation. For example, for memory FIFOs, the
105 /// actual amount of cycles it will take to clear it is dependent on how
106 /// quickly prior instructions evacuate the FIFO, which is based on runtime
107 /// behavior which is not modelled in the compiler.
108 unsigned BufferCycles = 0;
109
110public:
111 HardwareUnitInfo() {}
112
113 unsigned size() { return AllSUs.size(); }
114
115 unsigned getTotalCycles() { return TotalCycles; }
116
117 void setType(unsigned TheType) {
118 assert(TheType < (unsigned)AMDGPU::InstructionFlavor::NUM_FLAVORS);
119 Type = (AMDGPU::InstructionFlavor)(TheType);
120 }
121
122 AMDGPU::InstructionFlavor getType() const { return Type; }
123
124 bool producesCoexecWindow() const { return ProducesCoexecWindow; }
125
126 void setProducesCoexecWindow(bool Val) { ProducesCoexecWindow = Val; }
127
128 bool contains(SUnit *SU) const { return AllSUs.contains(key: SU); }
129
130 void setBufferSize(unsigned Size) { BufferSize = Size; }
131
132 unsigned getBufferSize() { return BufferSize; }
133
134 /// \returns the next cycle where there is space in the buffer.
135 unsigned getBufferAvailableCycle(unsigned CurrCycle) {
136 // An unlimited buffer is always available.
137 if (BufferSize == 0)
138 return CurrCycle;
139
140 // Buffer is available now.
141 if (ScheduledSUs.size() < BufferSize)
142 return CurrCycle;
143
144 return BufferCycles +
145 ScheduledSUs[ScheduledSUs.size() - BufferSize]->TopReadyCycle;
146 }
147
148 /// \returns the most recently scheduled SU for this HardwareUnit.
149 SUnit *getLastScheduledSU() {
150 unsigned ScheduledCount = ScheduledSUs.size();
151 if (!ScheduledCount)
152 return nullptr;
153
154 return ScheduledSUs[ScheduledCount - 1];
155 }
156
157 /// \returns the SUnit with higher priority or nullptr if they are the same.
158 /// This method looks through the PrioritySUs to determine if one SU is more
159 /// prioritized than the other. If neither are in the PrioritySUs list, then
160 /// neither have priority over each other.
161 SUnit *getHigherPriority(SUnit *SU, SUnit *Other) const {
162 for (SUnit *SUOrder : PrioritySUs) {
163 if (SUOrder == SU)
164 return SU;
165
166 if (SUOrder == Other)
167 return Other;
168 }
169 return nullptr;
170 }
171
172 void reset() {
173 AllSUs.clear();
174 PrioritySUs.clear();
175 ScheduledSUs.clear();
176 TotalCycles = 0;
177 Type = AMDGPU::InstructionFlavor::Other;
178 ProducesCoexecWindow = false;
179 BufferSize = 0;
180 BufferCycles = 0;
181 }
182
183 /// \returns the next SU in PrioritySUs that is not ready. If \p LookDeep is
184 /// set, we will look beyond the PrioritySUs (if all the PrioritySUs are
185 /// ready) to AllSUs to attempt to find a target SU. When looking through
186 /// AllSUs we sort pick the target SU by minimal depth for top-down
187 /// scheduling. getNextTargetSU is useful for determining which SU on this
188 /// HardwareUnit we are trying to schedule - this info helps us determine
189 /// which dependencies to schedule. LookDeep is useful if the dependencies are
190 /// long latency (e.g. memory instructions). If we have many long latency
191 /// dependencies, it is beneficial to enable SUs multiple levels ahead.
192 SUnit *getNextTargetSU(bool LookDeep = false) const;
193 /// Insert the \p SU into AllSUs and account its \p BlockingCycles into
194 /// the TotalCycles. This maintains the list of PrioritySUs.
195 void insert(SUnit *SU, unsigned BlockingCycles);
196 /// Update the state for \p SU being scheduled by removing it from the AllSUs
197 /// and reducing its \p BlockingCycles from the TotalCycles. This maintains
198 /// the list of PrioritySUs.
199 void markScheduled(SUnit *SU, unsigned BlockingCycles);
200 /// After we've collected all the region pressure for this HWUI, correct for
201 /// any specifics of the behavior of this resource. For example, if the
202 /// HardwareUnit can hold N instructions simultaneously, then there is no
203 /// penalty for scheduling N instructions back to back.
204 void finalizeCycles();
205};
206
207//===----------------------------------------------------------------------===//
208// Candidate Heuristics
209//===----------------------------------------------------------------------===//
210
211/// CandidateHeuristics contains state and implementations to facilitate making
212/// per instruction scheduling decisions; it contains methods used in
213/// tryCandidate to decide which instruction to schedule next.
214class CandidateHeuristics {
215protected:
216 struct StallCosts {
217 unsigned Ready = 0;
218 unsigned Structural = 0;
219 unsigned Latency = 0;
220 unsigned Carried = 0;
221 unsigned Buffer = 0;
222 unsigned Fence = 0;
223 unsigned Effective = 0;
224 };
225
226 ScheduleDAGMI *DAG;
227 const SIInstrInfo *SII;
228 const SIRegisterInfo *SRI;
229 const TargetSchedModel *SchedModel;
230 SmallVector<HardwareUnitInfo, 8> HWUInfo;
231 DenseMap<MachineInstr *, unsigned> CarriedLatencies;
232
233 /// Walk over the region and collect characteristics for the various
234 /// heuristics.
235 void collectRegionSummary();
236
237 /// \returns the maximum blocking cycles according to the SchedModel for a
238 /// given MCSchedClassDesc \p SC.
239 unsigned getMaxBlockingCycles(const MCSchedClassDesc *SC,
240 const MachineInstr *MI);
241
242 /// Compute the blocking cycles for the appropriate HardwareUnit given an \p
243 /// MI.
244 unsigned getHWUICyclesForMI(MachineInstr *MI);
245
246 /// Estimate the block carried latency from loads for a given \p SU. This is
247 /// essentially global scheduling info that our local scheduling
248 /// infrastructure lacks the necessary infrastructure to accurately measure.
249 /// Thus, this method just attempts to find a reasonable upper bound for
250 /// carried load latency to avoid long stalls.
251 unsigned getCarriedLatency(SUnit *SU);
252
253 StallCosts getStallCosts(SUnit *SU, SchedBoundary &Zone);
254
255public:
256 CandidateHeuristics() = default;
257
258 void initialize(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel,
259 const TargetRegisterInfo *TRI);
260
261 /// Update the state to reflect that \p SU is going to be scheduled.
262 void updateForScheduling(SUnit *SU);
263
264 /// Given a \p Flavor , find the corresponding HardwareUnit. \returns the
265 /// mapped HardwareUnit.
266 HardwareUnitInfo *getHWUIFromFlavor(AMDGPU::InstructionFlavor Flavor);
267
268 /// Sort the HardwarUnitInfo vector. After sorting, the HWUI that are highest
269 /// priority are first. Priority is determined by maximizing coexecution and
270 /// keeping the critical HardwareUnit busy.
271 void sortHWUIResources();
272
273 unsigned getStructuralStallCycles(SchedBoundary &Zone, SUnit *SU);
274
275 bool tryEffectiveStall(GenericSchedulerBase::SchedCandidate &TryCand,
276 GenericSchedulerBase::SchedCandidate &Cand,
277 SchedBoundary &Zone);
278
279 /// Prioritize instructions involved the memory pipeline. Currently we don't
280 /// have any modelling of pipelined loads, so we control the layout of the
281 /// pipeline per iteration by giving the user some control over the stalls
282 /// (e.g. between s_barrier_signal and s_barrier_wait) and scheduling the
283 /// pipeline instructions as soon as they are ready.
284 ///
285 /// TODO -- add better modelling and heuristics for pipelining based
286 /// scheduling.
287 bool tryMemoryPipeline(GenericSchedulerBase::SchedCandidate &TryCand,
288 GenericSchedulerBase::SchedCandidate &Cand,
289 SchedBoundary &Zone);
290
291 /// Check for critical resource consumption. Prefer the candidate that uses
292 /// the most prioritized HardwareUnit. If both candidates use the same
293 /// HarwareUnit, prefer the candidate with higher priority on that
294 /// HardwareUnit.
295 bool tryCriticalResource(GenericSchedulerBase::SchedCandidate &TryCand,
296 GenericSchedulerBase::SchedCandidate &Cand,
297 SchedBoundary *Zone) const;
298
299 /// Check for dependencies of instructions that use prioritized HardwareUnits.
300 /// Prefer the candidate that is a dependency of an instruction that uses the
301 /// most prioritized HardwareUnit. If both candidates enable the same
302 /// HardwareUnit, prefer the candidate that enables the higher priority
303 /// instruction on that HardwareUnit.
304 bool
305 tryCriticalResourceDependency(GenericSchedulerBase::SchedCandidate &TryCand,
306 GenericSchedulerBase::SchedCandidate &Cand,
307 SchedBoundary *Zone) const;
308
309 void dumpRegionSummary();
310};
311
312class AMDGPUCoExecSchedStrategy final : public GCNSchedStrategy {
313protected:
314 AMDGPU::AMDGPUSchedReason LastAMDGPUReason = AMDGPU::AMDGPUSchedReason::None;
315 CandidateHeuristics Heurs;
316
317#ifndef NDEBUG
318 void dumpPickSummary(SUnit *SU, bool IsTopNode, SchedCandidate &Cand);
319#endif
320
321 bool tryCandidateCoexec(SchedCandidate &Cand, SchedCandidate &TryCand,
322 SchedBoundary *Zone);
323 void pickNodeFromQueue(SchedBoundary &Zone, const CandPolicy &ZonePolicy,
324 const RegPressureTracker &RPTracker,
325 SchedCandidate &Cand, bool &PickedPending,
326 bool IsBottomUp);
327
328public:
329 AMDGPUCoExecSchedStrategy(const MachineSchedContext *C);
330
331 void initPolicy(MachineBasicBlock::iterator Begin,
332 MachineBasicBlock::iterator End,
333 unsigned NumRegionInstrs) override;
334 void initialize(ScheduleDAGMI *DAG) override;
335 SUnit *pickNode(bool &IsTopNode) override;
336 void schedNode(SUnit *SU, bool IsTopNode) override;
337};
338
339ScheduleDAGInstrs *createGCNCoExecMachineScheduler(MachineSchedContext *C);
340ScheduleDAGInstrs *createGCNNoopPostMachineScheduler(MachineSchedContext *C);
341
342} // End namespace llvm
343
344#endif // LLVM_LIB_TARGET_AMDGPU_AMDGPUCOEXECSCHEDSTRATEGY_H
345