1//===-- SIMachineScheduler.h - SI Scheduler Interface -----------*- 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/// SI Machine Scheduler interface
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIB_TARGET_AMDGPU_SIMACHINESCHEDULER_H
15#define LLVM_LIB_TARGET_AMDGPU_SIMACHINESCHEDULER_H
16
17#include "llvm/CodeGen/MachineScheduler.h"
18#include "llvm/CodeGen/RegisterPressure.h"
19#include "llvm/CodeGen/ScheduleDAG.h"
20#include <cstdint>
21#include <set>
22#include <vector>
23
24namespace llvm {
25
26class SIInstrInfo;
27class SIRegisterInfo;
28class SIScheduleDAGMI;
29class SIScheduleBlockCreator;
30
31enum SIScheduleCandReason {
32 NoCand,
33 RegUsage,
34 Latency,
35 Successor,
36 Depth,
37 NodeOrder
38};
39
40struct SISchedulerCandidate {
41 // The reason for this candidate.
42 SIScheduleCandReason Reason = NoCand;
43
44 // Set of reasons that apply to multiple candidates.
45 uint32_t RepeatReasonSet = 0;
46
47 SISchedulerCandidate() = default;
48
49 void setRepeat(SIScheduleCandReason R) { RepeatReasonSet |= (1 << R); }
50};
51
52enum SIScheduleBlockLinkKind {
53 NoData,
54 Data
55};
56
57class SIScheduleBlock {
58 SIScheduleDAGMI *DAG;
59 SIScheduleBlockCreator *BC;
60
61 std::vector<SUnit*> SUnits;
62 std::map<unsigned, unsigned> NodeNum2Index;
63 std::vector<SUnit*> TopReadySUs;
64 std::vector<SUnit*> ScheduledSUnits;
65
66 /// The top of the unscheduled zone.
67 IntervalPressure TopPressure;
68 RegPressureTracker TopRPTracker;
69
70 // Pressure: number of said class of registers needed to
71 // store the live virtual and real registers.
72 // We do care only of SGPR32 and VGPR32 and do track only virtual registers.
73 // Pressure of additional registers required inside the block.
74 std::vector<unsigned> InternalAdditionalPressure;
75 // Pressure of input and output registers
76 std::vector<unsigned> LiveInPressure;
77 std::vector<unsigned> LiveOutPressure;
78 // Registers required by the block, and outputs.
79 // We do track only virtual registers.
80 // Note that some registers are not 32 bits,
81 // and thus the pressure is not equal
82 // to the number of live registers.
83 std::set<Register> LiveInRegs;
84 std::set<Register> LiveOutRegs;
85
86 bool Scheduled = false;
87 bool HighLatencyBlock = false;
88
89 std::vector<unsigned> HasLowLatencyNonWaitedParent;
90
91 // Unique ID, the index of the Block in the SIScheduleDAGMI Blocks table.
92 unsigned ID;
93
94 std::vector<SIScheduleBlock*> Preds; // All blocks predecessors.
95 // All blocks successors, and the kind of link
96 std::vector<std::pair<SIScheduleBlock*, SIScheduleBlockLinkKind>> Succs;
97 unsigned NumHighLatencySuccessors = 0;
98
99public:
100 SIScheduleBlock(SIScheduleDAGMI *DAG, SIScheduleBlockCreator *BC,
101 unsigned ID):
102 DAG(DAG), BC(BC), TopRPTracker(TopPressure), ID(ID) {}
103
104 ~SIScheduleBlock() = default;
105
106 unsigned getID() const { return ID; }
107
108 /// Functions for Block construction.
109 void addUnit(SUnit *SU);
110
111 // When all SUs have been added.
112 void finalizeUnits();
113
114 // Add block pred, which has instruction predecessor of SU.
115 void addPred(SIScheduleBlock *Pred);
116 void addSucc(SIScheduleBlock *Succ, SIScheduleBlockLinkKind Kind);
117
118 const std::vector<SIScheduleBlock*>& getPreds() const { return Preds; }
119 ArrayRef<std::pair<SIScheduleBlock*, SIScheduleBlockLinkKind>>
120 getSuccs() const { return Succs; }
121
122 unsigned Height = 0; // Maximum topdown path length to block without outputs
123 unsigned Depth = 0; // Maximum bottomup path length to block without inputs
124
125 unsigned getNumHighLatencySuccessors() const {
126 return NumHighLatencySuccessors;
127 }
128
129 bool isHighLatencyBlock() { return HighLatencyBlock; }
130
131 // This is approximative.
132 // Ideally should take into accounts some instructions (rcp, etc)
133 // are 4 times slower.
134 int getCost() { return SUnits.size(); }
135
136 // The block Predecessors and Successors must be all registered
137 // before fastSchedule().
138 // Fast schedule with no particular requirement.
139 void fastSchedule();
140
141 std::vector<SUnit*> getScheduledUnits() { return ScheduledSUnits; }
142
143 // Complete schedule that will try to minimize reg pressure and
144 // low latencies, and will fill liveins and liveouts.
145 // Needs all MIs to be grouped between BeginBlock and EndBlock.
146 // The MIs can be moved after the scheduling,
147 // it is just used to allow correct track of live registers.
148 void schedule(MachineBasicBlock::iterator BeginBlock,
149 MachineBasicBlock::iterator EndBlock);
150
151 bool isScheduled() { return Scheduled; }
152
153 std::set<Register> &getInRegs() { return LiveInRegs; }
154 std::set<Register> &getOutRegs() { return LiveOutRegs; }
155
156 void printDebug(bool Full);
157
158private:
159 struct SISchedCandidate : SISchedulerCandidate {
160 // The best SUnit candidate.
161 SUnit *SU = nullptr;
162
163 unsigned SGPRUsage;
164 unsigned VGPRUsage;
165 bool IsLowLatency;
166 unsigned LowLatencyOffset;
167 bool HasLowLatencyNonWaitedParent;
168
169 SISchedCandidate() = default;
170
171 bool isValid() const { return SU; }
172
173 // Copy the status of another candidate without changing policy.
174 void setBest(SISchedCandidate &Best) {
175 assert(Best.Reason != NoCand && "uninitialized Sched candidate");
176 SU = Best.SU;
177 Reason = Best.Reason;
178 SGPRUsage = Best.SGPRUsage;
179 VGPRUsage = Best.VGPRUsage;
180 IsLowLatency = Best.IsLowLatency;
181 LowLatencyOffset = Best.LowLatencyOffset;
182 HasLowLatencyNonWaitedParent = Best.HasLowLatencyNonWaitedParent;
183 }
184 };
185
186 void undoSchedule();
187
188 void undoReleaseSucc(SUnit *SU, SDep *SuccEdge);
189 void releaseSucc(SUnit *SU, SDep *SuccEdge);
190 // InOrOutBlock: restrict to links pointing inside the block (true),
191 // or restrict to links pointing outside the block (false).
192 void releaseSuccessors(SUnit *SU, bool InOrOutBlock);
193
194 void nodeScheduled(SUnit *SU);
195 void tryCandidateTopDown(SISchedCandidate &Cand, SISchedCandidate &TryCand);
196 SUnit* pickNode();
197 void traceCandidate(const SISchedCandidate &Cand);
198 void initRegPressure(MachineBasicBlock::iterator BeginBlock,
199 MachineBasicBlock::iterator EndBlock);
200};
201
202struct SIScheduleBlocks {
203 std::vector<SIScheduleBlock*> Blocks;
204 std::vector<int> TopDownIndex2Block;
205 std::vector<int> TopDownBlock2Index;
206};
207
208enum SISchedulerBlockCreatorVariant {
209 LatenciesAlone,
210 LatenciesGrouped,
211 LatenciesAlonePlusConsecutive
212};
213
214class SIScheduleBlockCreator {
215 SIScheduleDAGMI *DAG;
216 // unique_ptr handles freeing memory for us.
217 std::vector<std::unique_ptr<SIScheduleBlock>> BlockPtrs;
218 std::map<SISchedulerBlockCreatorVariant,
219 SIScheduleBlocks> Blocks;
220 std::vector<SIScheduleBlock*> CurrentBlocks;
221 std::vector<int> Node2CurrentBlock;
222
223 // Topological sort
224 // Maps topological index to the node number.
225 std::vector<int> TopDownIndex2Block;
226 std::vector<int> TopDownBlock2Index;
227 std::vector<int> BottomUpIndex2Block;
228
229 // 0 -> Color not given.
230 // 1 to SUnits.size() -> Reserved group (you should only add elements to them).
231 // Above -> Other groups.
232 int NextReservedID;
233 int NextNonReservedID;
234 std::vector<int> CurrentColoring;
235 std::vector<int> CurrentTopDownReservedDependencyColoring;
236 std::vector<int> CurrentBottomUpReservedDependencyColoring;
237
238public:
239 SIScheduleBlockCreator(SIScheduleDAGMI *DAG);
240
241 SIScheduleBlocks
242 getBlocks(SISchedulerBlockCreatorVariant BlockVariant);
243
244 bool isSUInBlock(SUnit *SU, unsigned ID);
245
246private:
247 // Give a Reserved color to every high latency.
248 void colorHighLatenciesAlone();
249
250 // Create groups of high latencies with a Reserved color.
251 void colorHighLatenciesGroups();
252
253 // Compute coloring for topdown and bottom traversals with
254 // different colors depending on dependencies on Reserved colors.
255 void colorComputeReservedDependencies();
256
257 // Give color to all non-colored SUs according to Reserved groups dependencies.
258 void colorAccordingToReservedDependencies();
259
260 // Divides Blocks having no bottom up or top down dependencies on Reserved groups.
261 // The new colors are computed according to the dependencies on the other blocks
262 // formed with colorAccordingToReservedDependencies.
263 void colorEndsAccordingToDependencies();
264
265 // Cut groups into groups with SUs in consecutive order (except for Reserved groups).
266 void colorForceConsecutiveOrderInGroup();
267
268 // Merge Constant loads that have all their users into another group to the group.
269 // (TODO: else if all their users depend on the same group, put them there)
270 void colorMergeConstantLoadsNextGroup();
271
272 // Merge SUs that have all their users into another group to the group,
273 // but only for Reserved groups.
274 void colorMergeIfPossibleNextGroupOnlyForReserved();
275
276 // Put in one group all instructions with no users in this scheduling region
277 // (we'd want these groups be at the end).
278 void regroupNoUserInstructions();
279
280 // Give Reserved color to export instructions
281 void colorExports();
282
283 void createBlocksForVariant(SISchedulerBlockCreatorVariant BlockVariant);
284
285 void topologicalSort();
286
287 void scheduleInsideBlocks();
288
289 void fillStats();
290};
291
292enum SISchedulerBlockSchedulerVariant {
293 BlockLatencyRegUsage,
294 BlockRegUsageLatency,
295 BlockRegUsage
296};
297
298class SIScheduleBlockScheduler {
299 SIScheduleDAGMI *DAG;
300 SISchedulerBlockSchedulerVariant Variant;
301 std::vector<SIScheduleBlock*> Blocks;
302
303 std::vector<std::map<Register, unsigned>> LiveOutRegsNumUsages;
304 std::set<Register> LiveRegs;
305 // Num of schedulable unscheduled blocks reading the register.
306 std::map<Register, unsigned> LiveRegsConsumers;
307
308 std::vector<unsigned> LastPosHighLatencyParentScheduled;
309 int LastPosWaitedHighLatency;
310
311 std::vector<SIScheduleBlock*> BlocksScheduled;
312 unsigned NumBlockScheduled;
313 std::vector<SIScheduleBlock*> ReadyBlocks;
314
315 unsigned VregCurrentUsage;
316 unsigned SregCurrentUsage;
317
318 // Currently is only approximation.
319 unsigned maxVregUsage;
320 unsigned maxSregUsage;
321
322 std::vector<unsigned> BlockNumPredsLeft;
323 std::vector<unsigned> BlockNumSuccsLeft;
324
325public:
326 SIScheduleBlockScheduler(SIScheduleDAGMI *DAG,
327 SISchedulerBlockSchedulerVariant Variant,
328 SIScheduleBlocks BlocksStruct);
329 ~SIScheduleBlockScheduler() = default;
330
331 std::vector<SIScheduleBlock*> getBlocks() { return BlocksScheduled; }
332
333 unsigned getVGPRUsage() { return maxVregUsage; }
334 unsigned getSGPRUsage() { return maxSregUsage; }
335
336private:
337 struct SIBlockSchedCandidate : SISchedulerCandidate {
338 // The best Block candidate.
339 SIScheduleBlock *Block = nullptr;
340
341 bool IsHighLatency;
342 int VGPRUsageDiff;
343 unsigned NumSuccessors;
344 unsigned NumHighLatencySuccessors;
345 unsigned LastPosHighLatParentScheduled;
346 unsigned Height;
347
348 SIBlockSchedCandidate() = default;
349
350 bool isValid() const { return Block; }
351
352 // Copy the status of another candidate without changing policy.
353 void setBest(SIBlockSchedCandidate &Best) {
354 assert(Best.Reason != NoCand && "uninitialized Sched candidate");
355 Block = Best.Block;
356 Reason = Best.Reason;
357 IsHighLatency = Best.IsHighLatency;
358 VGPRUsageDiff = Best.VGPRUsageDiff;
359 NumSuccessors = Best.NumSuccessors;
360 NumHighLatencySuccessors = Best.NumHighLatencySuccessors;
361 LastPosHighLatParentScheduled = Best.LastPosHighLatParentScheduled;
362 Height = Best.Height;
363 }
364 };
365
366 bool tryCandidateLatency(SIBlockSchedCandidate &Cand,
367 SIBlockSchedCandidate &TryCand);
368 bool tryCandidateRegUsage(SIBlockSchedCandidate &Cand,
369 SIBlockSchedCandidate &TryCand);
370 SIScheduleBlock *pickBlock();
371
372 void addLiveRegs(std::set<VirtRegOrUnit> &Regs);
373 void decreaseLiveRegs(SIScheduleBlock *Block, std::set<Register> &Regs);
374 void releaseBlockSuccs(SIScheduleBlock *Parent);
375 void blockScheduled(SIScheduleBlock *Block);
376
377 // Check register pressure change
378 // by scheduling a block with these LiveIn and LiveOut.
379 std::vector<int> checkRegUsageImpact(std::set<Register> &InRegs,
380 std::set<Register> &OutRegs);
381};
382
383struct SIScheduleBlockResult {
384 std::vector<unsigned> SUs;
385 unsigned MaxSGPRUsage;
386 unsigned MaxVGPRUsage;
387};
388
389class SIScheduler {
390 SIScheduleDAGMI *DAG;
391 SIScheduleBlockCreator BlockCreator;
392
393public:
394 SIScheduler(SIScheduleDAGMI *DAG) : DAG(DAG), BlockCreator(DAG) {}
395
396 ~SIScheduler() = default;
397
398 struct SIScheduleBlockResult
399 scheduleVariant(SISchedulerBlockCreatorVariant BlockVariant,
400 SISchedulerBlockSchedulerVariant ScheduleVariant);
401};
402
403class SIScheduleDAGMI final : public ScheduleDAGMILive {
404 const SIInstrInfo *SITII;
405 const SIRegisterInfo *SITRI;
406
407 std::vector<SUnit> SUnitsLinksBackup;
408
409 // For moveLowLatencies. After all Scheduling variants are tested.
410 std::vector<unsigned> ScheduledSUnits;
411 std::vector<unsigned> ScheduledSUnitsInv;
412
413public:
414 SIScheduleDAGMI(MachineSchedContext *C);
415
416 ~SIScheduleDAGMI() override;
417
418 // Entry point for the schedule.
419 void schedule() override;
420
421 // To init Block's RPTracker.
422 void initRPTracker(RegPressureTracker &RPTracker) {
423 RPTracker.init(mf: &MF, rci: RegClassInfo, lis: LIS, mbb: BB, pos: RegionBegin, TrackLaneMasks: false, TrackUntiedDefs: false);
424 }
425
426 MachineBasicBlock *getBB() { return BB; }
427 MachineBasicBlock::iterator getCurrentTop() { return CurrentTop; }
428 MachineBasicBlock::iterator getCurrentBottom() { return CurrentBottom; }
429 LiveIntervals *getLIS() { return LIS; }
430 MachineRegisterInfo *getMRI() { return &MRI; }
431 const TargetRegisterInfo *getTRI() { return TRI; }
432 ScheduleDAGTopologicalSort *GetTopo() { return &Topo; }
433
434 void restoreSULinksLeft();
435
436 template<typename _Iterator> void fillVgprSgprCost(_Iterator First,
437 _Iterator End,
438 unsigned &VgprUsage,
439 unsigned &SgprUsage);
440
441 std::set<VirtRegOrUnit> getInRegs() {
442 std::set<VirtRegOrUnit> InRegs;
443 for (const auto &RegMaskPair : RPTracker.getPressure().LiveInRegs) {
444 InRegs.insert(x: RegMaskPair.VRegOrUnit);
445 }
446 return InRegs;
447 }
448
449 std::set<VirtRegOrUnit> getOutRegs() {
450 std::set<VirtRegOrUnit> OutRegs;
451 for (const auto &RegMaskPair : RPTracker.getPressure().LiveOutRegs) {
452 OutRegs.insert(x: RegMaskPair.VRegOrUnit);
453 }
454 return OutRegs;
455 };
456
457private:
458 void topologicalSort();
459 // After scheduling is done, improve low latency placements.
460 void moveLowLatencies();
461
462public:
463 // Some stats for scheduling inside blocks.
464 std::vector<unsigned> IsLowLatencySU;
465 std::vector<unsigned> LowLatencyOffset;
466 std::vector<unsigned> IsHighLatencySU;
467 // Topological sort
468 // Maps topological index to the node number.
469 std::vector<int> TopDownIndex2SU;
470 std::vector<int> BottomUpIndex2SU;
471};
472
473} // end namespace llvm
474
475#endif // LLVM_LIB_TARGET_AMDGPU_SIMACHINESCHEDULER_H
476