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