1//===-- GCNSchedStrategy.h - GCN Scheduler 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//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_LIB_TARGET_AMDGPU_GCNSCHEDSTRATEGY_H
14#define LLVM_LIB_TARGET_AMDGPU_GCNSCHEDSTRATEGY_H
15
16#include "GCNRegPressure.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/CodeGen/MachineBasicBlock.h"
19#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
20#include "llvm/CodeGen/MachineInstr.h"
21#include "llvm/CodeGen/MachineScheduler.h"
22#include "llvm/CodeGen/Rematerializer.h"
23#include "llvm/Support/CommandLine.h"
24
25namespace llvm {
26
27struct VGPRThresholdParser : public cl::parser<unsigned> {
28 VGPRThresholdParser(cl::Option &O) : cl::parser<unsigned>(O) {}
29 bool parse(cl::Option &O, StringRef ArgName, StringRef Arg, unsigned &Value);
30};
31
32extern cl::opt<unsigned, false, VGPRThresholdParser> VGPRThresholdPercentOpt;
33
34class SIMachineFunctionInfo;
35class SIRegisterInfo;
36class GCNSubtarget;
37class GCNSchedStage;
38
39enum class GCNSchedStageID : unsigned {
40 OccInitialSchedule = 0,
41 RewriteMFMAForm = 1,
42 UnclusteredHighRPReschedule = 2,
43 ClusteredLowOccupancyReschedule = 3,
44 PreRARematerialize = 4,
45 ILPInitialSchedule = 5,
46 MemoryClauseInitialSchedule = 6,
47 LiveIntervalRPReschedule = 7
48};
49
50#ifndef NDEBUG
51raw_ostream &operator<<(raw_ostream &OS, const GCNSchedStageID &StageID);
52#endif
53
54/// This is a minimal scheduler strategy. The main difference between this
55/// and the GenericScheduler is that GCNSchedStrategy uses different
56/// heuristics to determine excess/critical pressure sets.
57class GCNSchedStrategy : public GenericScheduler {
58protected:
59 SUnit *pickNodeBidirectional(bool &IsTopNode, bool &PickedPending);
60
61 void pickNodeFromQueue(SchedBoundary &Zone, const CandPolicy &ZonePolicy,
62 const RegPressureTracker &RPTracker,
63 SchedCandidate &Cand, bool &IsPending,
64 bool IsBottomUp);
65
66 void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
67 const RegPressureTracker &RPTracker,
68 const SIRegisterInfo *SRI, unsigned SGPRPressure,
69 unsigned VGPRPressure, unsigned AGPRPressure,
70 bool IsBottomUp);
71
72 /// Evaluates instructions in the pending queue using a subset of scheduling
73 /// heuristics.
74 ///
75 /// Instructions that cannot be issued due to hardware constraints are placed
76 /// in the pending queue rather than the available queue, making them normally
77 /// invisible to scheduling heuristics. However, in certain scenarios (such as
78 /// avoiding register spilling), it may be beneficial to consider scheduling
79 /// these not-yet-ready instructions.
80 bool tryPendingCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
81 SchedBoundary *Zone) const;
82
83 void printCandidateDecision(const SchedCandidate &Current,
84 const SchedCandidate &Preferred);
85
86 void getRegisterPressures(bool AtTop, const RegPressureTracker &RPTracker,
87 SUnit *SU, std::vector<unsigned> &Pressure,
88 std::vector<unsigned> &MaxPressure,
89 GCNDownwardRPTracker &DownwardTracker,
90 GCNUpwardRPTracker &UpwardTracker,
91 ScheduleDAGMI *DAG, const SIRegisterInfo *SRI);
92
93 std::vector<unsigned> Pressure;
94
95 std::vector<unsigned> MaxPressure;
96
97 unsigned TargetOccupancy;
98
99 MachineFunction *MF;
100
101 // Scheduling stages for this strategy.
102 SmallVector<GCNSchedStageID, 4> SchedStages;
103
104 // Pointer to the current SchedStageID.
105 SmallVectorImpl<GCNSchedStageID>::iterator CurrentStage = nullptr;
106
107 // GCN RP Tracker for top-down scheduling
108 mutable GCNDownwardRPTracker DownwardTracker;
109
110 // GCN RP Tracker for botttom-up scheduling
111 mutable GCNUpwardRPTracker UpwardTracker;
112
113 bool UseGCNTrackers = false;
114
115 std::optional<bool> GCNTrackersOverride;
116
117public:
118 // schedule() have seen register pressure over the critical limits and had to
119 // track register pressure for actual scheduling heuristics.
120 bool HasHighPressure;
121
122 // Schedule known to have excess register pressure. Be more conservative in
123 // increasing ILP and preserving VGPRs.
124 bool KnownExcessRP = false;
125
126 // An error margin is necessary because of poor performance of the generic RP
127 // tracker and can be adjusted up for tuning heuristics to try and more
128 // aggressively reduce register pressure.
129 unsigned ErrorMargin = 3;
130
131 // Bias for SGPR limits under a high register pressure.
132 const unsigned HighRPSGPRBias = 7;
133
134 // Bias for VGPR limits under a high register pressure.
135 const unsigned HighRPVGPRBias = 7;
136
137 unsigned SGPRExcessLimit = 0;
138
139 unsigned VGPRExcessLimit = 0;
140
141 unsigned AGPRExcessLimit = 0;
142
143 unsigned SGPRCriticalLimit = 0;
144
145 unsigned VGPRCriticalLimit = 0;
146
147 unsigned AGPRCriticalLimit = 0;
148
149 unsigned SGPRLimitBias = 0;
150
151 unsigned VGPRLimitBias = 0;
152
153 unsigned VGPRThresholdPercent = 0;
154
155 GCNSchedStrategy(const MachineSchedContext *C);
156
157 SUnit *pickNode(bool &IsTopNode) override;
158
159 void schedNode(SUnit *SU, bool IsTopNode) override;
160
161 void initialize(ScheduleDAGMI *DAG) override;
162
163 unsigned getTargetOccupancy() { return TargetOccupancy; }
164
165 void setTargetOccupancy(unsigned Occ) { TargetOccupancy = Occ; }
166
167 GCNSchedStageID getCurrentStage();
168
169 // Advances stage. Returns true if there are remaining stages.
170 bool advanceStage();
171
172 bool hasNextStage() const;
173
174 bool useGCNTrackers() const {
175 return GCNTrackersOverride.value_or(u: UseGCNTrackers);
176 }
177
178 GCNDownwardRPTracker *getDownwardTracker() { return &DownwardTracker; }
179
180 GCNUpwardRPTracker *getUpwardTracker() { return &UpwardTracker; }
181};
182
183/// The goal of this scheduling strategy is to maximize kernel occupancy (i.e.
184/// maximum number of waves per simd).
185class GCNMaxOccupancySchedStrategy final : public GCNSchedStrategy {
186public:
187 GCNMaxOccupancySchedStrategy(const MachineSchedContext *C,
188 bool IsLegacyScheduler = false);
189};
190
191/// The goal of this scheduling strategy is to maximize ILP for a single wave
192/// (i.e. latency hiding).
193class GCNMaxILPSchedStrategy final : public GCNSchedStrategy {
194protected:
195 bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
196 SchedBoundary *Zone) const override;
197
198public:
199 GCNMaxILPSchedStrategy(const MachineSchedContext *C);
200};
201
202/// The goal of this scheduling strategy is to maximize memory clause for a
203/// single wave.
204class GCNMaxMemoryClauseSchedStrategy final : public GCNSchedStrategy {
205protected:
206 bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
207 SchedBoundary *Zone) const override;
208
209public:
210 GCNMaxMemoryClauseSchedStrategy(const MachineSchedContext *C);
211};
212
213class ScheduleMetrics {
214 unsigned ScheduleLength;
215 unsigned BubbleCycles;
216
217public:
218 ScheduleMetrics() = default;
219 ScheduleMetrics(unsigned L, unsigned BC)
220 : ScheduleLength(L), BubbleCycles(BC) {}
221 unsigned getLength() const { return ScheduleLength; }
222 unsigned getBubbles() const { return BubbleCycles; }
223 unsigned getMetric() const {
224 unsigned Metric = (BubbleCycles * ScaleFactor) / ScheduleLength;
225 // Metric is zero if the amount of bubbles is less than 1% which is too
226 // small. So, return 1.
227 return Metric ? Metric : 1;
228 }
229 static const unsigned ScaleFactor;
230};
231
232inline raw_ostream &operator<<(raw_ostream &OS, const ScheduleMetrics &Sm) {
233 dbgs() << "\n Schedule Metric (scaled by " << ScheduleMetrics::ScaleFactor
234 << " ) is: " << Sm.getMetric() << " [ " << Sm.getBubbles() << "/"
235 << Sm.getLength() << " ]\n";
236 return OS;
237}
238
239class GCNScheduleDAGMILive;
240class RegionPressureMap {
241 GCNScheduleDAGMILive *DAG;
242 // The live in/out pressure as indexed by the first or last MI in the region
243 // before scheduling.
244 DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet> RegionLiveRegMap;
245 // The mapping of RegionIDx to key instruction
246 DenseMap<unsigned, MachineInstr *> IdxToInstruction;
247 // Whether we are calculating LiveOuts or LiveIns
248 bool IsLiveOut;
249
250public:
251 RegionPressureMap() = default;
252 RegionPressureMap(GCNScheduleDAGMILive *GCNDAG, bool LiveOut)
253 : DAG(GCNDAG), IsLiveOut(LiveOut) {}
254 // Build the Instr->LiveReg and RegionIdx->Instr maps
255 void buildLiveRegMap();
256
257 // Retrieve the LiveReg for a given RegionIdx
258 GCNRPTracker::LiveRegSet &getLiveRegsForRegionIdx(unsigned RegionIdx) {
259 assert(IdxToInstruction.contains(RegionIdx));
260 MachineInstr *Key = IdxToInstruction[RegionIdx];
261 return RegionLiveRegMap[Key];
262 }
263};
264
265/// A region's boundaries i.e. a pair of instruction bundle iterators. The lower
266/// boundary is inclusive, the upper boundary is exclusive.
267using RegionBoundaries =
268 std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>;
269
270class GCNScheduleDAGMILive final : public ScheduleDAGMILive {
271 friend class GCNSchedStage;
272 friend class OccInitialScheduleStage;
273 friend class RewriteMFMAFormStage;
274 friend class UnclusteredHighRPStage;
275 friend class ClusteredLowOccStage;
276 friend class PreRARematStage;
277 friend class ILPInitialScheduleStage;
278 friend class LiveIntervalRPStage;
279 friend class RegionPressureMap;
280
281 const GCNSubtarget &ST;
282
283 SIMachineFunctionInfo &MFI;
284
285 // Occupancy target at the beginning of function scheduling cycle.
286 unsigned StartingOccupancy;
287
288 // Minimal real occupancy recorder for the function.
289 unsigned MinOccupancy;
290
291 // Vector of regions recorder for later rescheduling
292 SmallVector<RegionBoundaries, 32> Regions;
293
294 // Record regions with high register pressure.
295 BitVector RegionsWithHighRP;
296
297 // Record regions with excess register pressure over the physical register
298 // limit. Register pressure in these regions usually will result in spilling.
299 BitVector RegionsWithExcessRP;
300
301 // Regions that have IGLP instructions (SCHED_GROUP_BARRIER or IGLP_OPT).
302 BitVector RegionsWithIGLPInstrs;
303
304 // Region live-in cache.
305 SmallVector<GCNRPTracker::LiveRegSet, 32> LiveIns;
306
307 // Region pressure cache.
308 SmallVector<GCNRegPressure, 32> Pressure;
309
310 // Temporary basic block live-in cache.
311 DenseMap<const MachineBasicBlock *, GCNRPTracker::LiveRegSet> MBBLiveIns;
312
313 // The map of the initial first region instruction to region live in registers
314 DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet> BBLiveInMap;
315
316 // Calculate the map of the initial first region instruction to region live in
317 // registers
318 DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet> getRegionLiveInMap() const;
319
320 // Calculate the map of the initial last region instruction to region live out
321 // registers
322 DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet>
323 getRegionLiveOutMap() const;
324
325 // The live out registers per region. These are internally stored as a map of
326 // the initial last region instruction to region live out registers, but can
327 // be retreived with the regionIdx by calls to getLiveRegsForRegionIdx.
328 RegionPressureMap RegionLiveOuts;
329
330 // Return current region pressure.
331 GCNRegPressure getRealRegPressure(unsigned RegionIdx) const;
332
333 // Compute and cache live-ins and pressure for all regions in block.
334 void computeBlockPressure(unsigned RegionIdx, const MachineBasicBlock *MBB);
335
336 /// Makes the scheduler try to achieve an occupancy of \p TargetOccupancy.
337 void setTargetOccupancy(unsigned TargetOccupancy);
338
339 void runSchedStages();
340
341 std::unique_ptr<GCNSchedStage> createSchedStage(GCNSchedStageID SchedStageID);
342
343public:
344 GCNScheduleDAGMILive(MachineSchedContext *C,
345 std::unique_ptr<MachineSchedStrategy> S);
346
347 void schedule() override;
348
349 void finalizeSchedule() override;
350};
351
352// GCNSchedStrategy applies multiple scheduling stages to a function.
353class GCNSchedStage {
354protected:
355 GCNScheduleDAGMILive &DAG;
356
357 GCNSchedStrategy &S;
358
359 MachineFunction &MF;
360
361 SIMachineFunctionInfo &MFI;
362
363 const GCNSubtarget &ST;
364
365 const GCNSchedStageID StageID;
366
367 // The current block being scheduled.
368 MachineBasicBlock *CurrentMBB = nullptr;
369
370 // Current region index.
371 unsigned RegionIdx = 0;
372
373 // Record the original order of instructions before scheduling.
374 std::vector<MachineInstr *> Unsched;
375
376 // RP before scheduling the current region.
377 GCNRegPressure PressureBefore;
378
379 // RP after scheduling the current region.
380 GCNRegPressure PressureAfter;
381
382 std::vector<std::unique_ptr<ScheduleDAGMutation>> SavedMutations;
383
384 GCNSchedStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG);
385
386public:
387 // Initialize state for a scheduling stage. Returns false if the current stage
388 // should be skipped.
389 virtual bool initGCNSchedStage();
390
391 // Finalize state after finishing a scheduling pass on the function.
392 virtual void finalizeGCNSchedStage();
393
394 // Setup for scheduling a region. Returns false if the current region should
395 // be skipped.
396 virtual bool initGCNRegion();
397
398 // Finalize state after scheduling a region.
399 virtual void finalizeGCNRegion();
400
401 // Track whether a new region is also a new MBB.
402 void setupNewBlock();
403
404 // Check result of scheduling.
405 void checkScheduling();
406
407 // computes the given schedule virtual execution time in clocks
408 ScheduleMetrics getScheduleMetrics(const std::vector<SUnit> &InputSchedule);
409 ScheduleMetrics getScheduleMetrics(const GCNScheduleDAGMILive &DAG);
410 unsigned computeSUnitReadyCycle(const SUnit &SU, unsigned CurrCycle,
411 DenseMap<unsigned, unsigned> &ReadyCycles,
412 const TargetSchedModel &SM);
413
414 // Returns true if scheduling should be reverted.
415 virtual bool shouldRevertScheduling(unsigned WavesAfter);
416
417 // Returns true if current region has known excess pressure.
418 bool isRegionWithExcessRP() const {
419 return DAG.RegionsWithExcessRP[RegionIdx];
420 }
421
422 // The region number this stage is currently working on
423 unsigned getRegionIdx() { return RegionIdx; }
424
425 // Returns true if the new schedule may result in more spilling.
426 bool mayCauseSpilling(unsigned WavesAfter);
427
428 /// Sets the schedule of region \p RegionIdx to \p MIOrder. The MIs in \p
429 /// MIOrder must be exactly the same as the ones currently existing inside the
430 /// region, only in a different order that honors def-use chains.
431 void modifyRegionSchedule(unsigned RegionIdx,
432 ArrayRef<MachineInstr *> MIOrder);
433
434 void advanceRegion() { RegionIdx++; }
435
436 virtual ~GCNSchedStage() = default;
437};
438
439class OccInitialScheduleStage : public GCNSchedStage {
440public:
441 bool shouldRevertScheduling(unsigned WavesAfter) override;
442
443 OccInitialScheduleStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)
444 : GCNSchedStage(StageID, DAG) {}
445};
446
447class RewriteMFMAFormStage : public GCNSchedStage {
448private:
449 // Record regions with excess archvgpr register pressure over the physical
450 // register limit. Register pressure in these regions usually will result in
451 // spilling.
452 BitVector RegionsWithExcessArchVGPR;
453
454 const SIInstrInfo *TII;
455 const SIRegisterInfo *SRI;
456
457 /// Per-candidate cache of the src2 "needs VGPR" decision, computed once
458 /// and reused on-demand.
459 DenseMap<const MachineInstr *, bool> Src2NeedsVGPRCache;
460
461 /// Do a speculative rewrite and collect copy locations. The speculative
462 /// rewrite allows us to calculate the RP of the code after the rewrite, and
463 /// the copy locations allow us to calculate the total cost of copies required
464 /// for the rewrite. Stores the rewritten instructions in \p RewriteCands ,
465 /// the copy locations for uses (of the MFMA result) in \p CopyForUse and the
466 /// copy locations for defs (of the MFMA operands) in \p CopyForDef
467 bool
468 initHeuristics(std::vector<std::pair<MachineInstr *, unsigned>> &RewriteCands,
469 DenseMap<MachineBasicBlock *, std::set<Register>> &CopyForUse,
470 SmallPtrSetImpl<MachineInstr *> &CopyForDef);
471
472 /// Calculate the rewrite cost and undo the state change (e.g. rewriting) done
473 /// in initHeuristics. Uses \p CopyForUse and \p CopyForDef to calculate copy
474 /// costs, and \p RewriteCands to undo rewriting.
475 int64_t getRewriteCost(
476 ArrayRef<std::pair<MachineInstr *, unsigned>> RewriteCands,
477 const DenseMap<MachineBasicBlock *, std::set<Register>> &CopyForUse,
478 const SmallPtrSetImpl<MachineInstr *> &CopyForDef);
479
480 /// Do the final rewrite on \p RewriteCands and insert any needed copies.
481 bool rewrite(ArrayRef<std::pair<MachineInstr *, unsigned>> RewriteCands);
482
483 /// \returns true if this MI is a rewrite candidate.
484 bool isRewriteCandidate(MachineInstr *MI) const;
485
486 /// Resets all candidates in \p RewriteCands back to VGPR form.
487 void resetRewriteCandsToVGPR(
488 ArrayRef<std::pair<MachineInstr *, unsigned>> RewriteCands);
489
490 /// Finds all the reaching defs of \p UseMO and stores the SlotIndexes into \p
491 /// DefIdxs
492 void findReachingDefs(MachineOperand &UseMO, LiveIntervals *LIS,
493 SmallVectorImpl<SlotIndex> &DefIdxs);
494
495 /// Finds all the reaching uses of \p DefMI and stores the use operands in \p
496 /// ReachingUses
497 void findReachingUses(const MachineInstr *DefMI, LiveIntervals *LIS,
498 SmallVectorImpl<MachineOperand *> &ReachingUses);
499
500 /// Returns true if the src2 register with reaching defs \p Src2ReachingDefs
501 /// has a use other than a group MFMA (in \p RewriteSet) or a copy, which
502 /// would keep it in VGPR form rather than let it be reclassified to AGPR.
503 bool hasUseRequiringVGPR(ArrayRef<SlotIndex> Src2ReachingDefs,
504 const SmallPtrSetImpl<MachineInstr *> &RewriteSet);
505
506public:
507 bool initGCNSchedStage() override;
508
509 RewriteMFMAFormStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)
510 : GCNSchedStage(StageID, DAG) {}
511};
512
513class UnclusteredHighRPStage : public GCNSchedStage {
514private:
515 // Save the initial occupancy before starting this stage.
516 unsigned InitialOccupancy;
517 // Save the temporary target occupancy before starting this stage.
518 unsigned TempTargetOccupancy;
519 // Track whether any region was scheduled by this stage.
520 bool IsAnyRegionScheduled;
521
522public:
523 bool initGCNSchedStage() override;
524
525 void finalizeGCNSchedStage() override;
526
527 bool initGCNRegion() override;
528
529 bool shouldRevertScheduling(unsigned WavesAfter) override;
530
531 UnclusteredHighRPStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)
532 : GCNSchedStage(StageID, DAG) {}
533};
534
535// Retry function scheduling if we found resulting occupancy and it is
536// lower than used for other scheduling passes. This will give more freedom
537// to schedule low register pressure blocks.
538class ClusteredLowOccStage : public GCNSchedStage {
539public:
540 bool initGCNSchedStage() override;
541
542 bool initGCNRegion() override;
543
544 bool shouldRevertScheduling(unsigned WavesAfter) override;
545
546 ClusteredLowOccStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)
547 : GCNSchedStage(StageID, DAG) {}
548};
549
550/// Attempts to reduce function spilling or, if there is no spilling, to
551/// increase function occupancy by one with respect to register usage by sinking
552/// rematerializable instructions to their use. When the stage estimates that
553/// reducing spilling or increasing occupancy is possible, it tries to
554/// rematerialize as few registers as possible to reduce potential negative
555/// effects on function latency.
556///
557/// The stage only supports rematerializing registers that meet all of the
558/// following constraints.
559/// 1. The register is virtual and has a single defining instruction.
560/// 2. The single defining instruction is either deemed rematerializable by the
561/// target-independent logic, or if not, has no non-constant and
562/// non-ignorable physical register use.
563/// 3 The register has no virtual register use whose live range would be
564/// extended by the rematerialization.
565/// 4. The register has a single non-debug user in a different region from its
566/// defining region.
567/// 5. The register is not used by or using another register that is going to be
568/// rematerialized.
569class PreRARematStage : public GCNSchedStage {
570private:
571 using RegisterIdx = Rematerializer::RegisterIdx;
572
573 /// A scored rematerialization candidate. Higher scores indicate more
574 /// beneficial rematerializations. A null score indicate the rematerialization
575 /// is not helpful to reduce RP in target regions.
576 struct ScoredRemat {
577 /// The register index handle in the rematerializer.
578 RegisterIdx RegIdx;
579 /// Regions in which the register is live-in/live-out/live anywhere.
580 BitVector LiveIn, LiveOut, Live;
581 /// Subset of \ref Live regions in which the rematerialization is not
582 /// guaranteed to reduce RP (i.e., regions in which the register is not
583 /// live-through and unused).
584 BitVector UnpredictableRPSave;
585 /// Expected register pressure decrease induced by rematerializing this
586 /// candidate.
587 GCNRegPressure RPSave;
588
589 ScoredRemat(RegisterIdx RegIdx, unsigned NumRegions)
590 : RegIdx(RegIdx), LiveIn(NumRegions), LiveOut(NumRegions),
591 Live(NumRegions), UnpredictableRPSave(NumRegions) {}
592
593 /// Execution frequency information required by scoring heuristics.
594 /// Frequencies are scaled down if they are high to avoid overflow/underflow
595 /// when combining them.
596 struct FreqInfo {
597 /// Per-region execution frequencies. 0 when unknown.
598 SmallVector<uint64_t> Regions;
599 /// Minimum and maximum observed frequencies.
600 uint64_t MinFreq, MaxFreq;
601
602 FreqInfo(MachineFunction &MF, const GCNScheduleDAGMILive &DAG);
603
604 private:
605 static const uint64_t ScaleFactor = 1024;
606 };
607
608 /// Initializes the candidate with state-independent characteristics.
609 /// This doesn't update the actual score (call \ref update for this).
610 /// Note: LiveIn/LiveOut must be pre-populated before calling this.
611 void init(const FreqInfo &Freq, const Rematerializer &Remater,
612 GCNScheduleDAGMILive &DAG);
613
614 /// Rematerializes the candidate using the \p Remater.
615 void rematerialize(Rematerializer &Remater) const;
616
617 /// Determines whether this rematerialization may be beneficial in at least
618 /// one target region.
619 bool maybeBeneficial(const BitVector &TargetRegions,
620 ArrayRef<GCNRPTarget> RPTargets) const;
621
622 /// Updates the rematerialization's score w.r.t. the current \p RPTargets.
623 /// \p RegionFreq indicates the frequency of each region.
624 void update(const BitVector &TargetRegions, ArrayRef<GCNRPTarget> RPTargets,
625 const FreqInfo &Freq, bool ReduceSpill);
626
627 /// Returns whether the current score is null, indicating the
628 /// rematerialization is useless.
629 bool hasNullScore() const { return !RegionImpact; }
630
631 /// Compare score components of non-null scores pair-wise. Scores shouldn't
632 /// be null (as defined by \ref hasNullScore).
633 bool operator<(const ScoredRemat &O) const {
634 assert(!hasNullScore() && "this has null score");
635 assert(!O.hasNullScore() && "other has null score");
636 if (MaxFreq != O.MaxFreq)
637 return MaxFreq < O.MaxFreq;
638 if (FreqDiff != O.FreqDiff)
639 return FreqDiff < O.FreqDiff;
640 if (RegionImpact != O.RegionImpact)
641 return RegionImpact < O.RegionImpact;
642 // Break ties using register index handles. If the two registers are
643 // connected in some dependency DAG of rematerializable registers, this
644 // will tend to give a higher score to the register further from the
645 // dependency DAG's root. If the two registers are disconnected, this will
646 // give a higher score to the register with lower virtual register index.
647 // In general, within a region, this should prefer registers defined
648 // earlier that have longer live ranges in their defining region (since
649 // the registers we consider are always live-out in their defining
650 // region).
651 return RegIdx > O.RegIdx;
652 }
653
654#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
655 Printable print() const;
656#endif
657
658 private:
659 // The three members below are the scoring components, top to bottom from
660 // most important to least important when comparing candidates.
661
662 /// Frequency of impacted target region with highest known frequency. This
663 /// only matters when the stage is trying to reduce spilling, so it is
664 /// always 0 when it is not.
665 uint64_t MaxFreq;
666 /// Frequency difference between defining and using regions. Negative values
667 /// indicate we are rematerializing to higher frequency regions; positive
668 /// values indicate the contrary.
669 int64_t FreqDiff;
670 /// Expected number of target regions impacted by the rematerialization,
671 /// scaled by the size of the register being rematerialized.
672 unsigned RegionImpact;
673 };
674
675 /// Register pressure targets for all regions.
676 SmallVector<GCNRPTarget> RPTargets;
677 /// Regions which are above the stage's RP target.
678 BitVector TargetRegions;
679 /// The target occupancy the set is trying to achieve. Empty when the
680 /// objective is spilling reduction.
681 std::optional<unsigned> TargetOcc;
682 /// Achieved occupancy *only* through rematerializations (pre-rescheduling).
683 unsigned AchievedOcc;
684 /// After successful stage initialization, indicates which regions should be
685 /// rescheduled.
686 BitVector RescheduleRegions;
687
688 /// Underlying utilities to identify and perform rematerializations.
689 Rematerializer Remater;
690
691 struct RollbackSupport {
692 struct LiveMapUpdate {
693 /// The register index handle in the rematerializer.
694 RegisterIdx RegIdx;
695 /// Regions in which the original register was live-in or live-out.
696 BitVector LiveIn, LiveOut;
697
698 LiveMapUpdate(RegisterIdx RegIdx, const BitVector &LiveIn,
699 const BitVector &LiveOut)
700 : RegIdx(RegIdx), LiveIn(LiveIn), LiveOut(LiveOut) {}
701 };
702
703 /// Rollback listener.
704 Rollbacker Listener;
705 /// Registers removed from live-maps along with bitvectors indicationg the
706 /// regions in which they were live-ins and live-outs.
707 SmallVector<LiveMapUpdate> LiveMapUpdates;
708
709 /// Attaches the rollback listener to the rematerializer.
710 RollbackSupport(Rematerializer &Remater) { Remater.addListener(Listen: &Listener); }
711 };
712
713 /// Rollback support. Maintained through a unique pointer because it is
714 /// optional and needs to persist between stage initialization and
715 /// finalization.
716 std::unique_ptr<RollbackSupport> Rollback;
717
718 /// State of a region pre-re-scheduling but post-rematerializations that we
719 /// must keep to be able to revert re-scheduling effects.
720 struct RegionSchedRevert {
721 /// Region number;
722 unsigned RegionIdx;
723 /// Original instruction order (both debug and non-debug MIs).
724 std::vector<MachineInstr *> OrigMIOrder;
725 /// Maximum pressure recorded in the region.
726 GCNRegPressure MaxPressure;
727
728 RegionSchedRevert(unsigned RegionIdx, ArrayRef<MachineInstr *> OrigMIOrder,
729 const GCNRegPressure &MaxPressure)
730 : RegionIdx(RegionIdx), OrigMIOrder(OrigMIOrder),
731 MaxPressure(MaxPressure) {}
732 };
733 /// After re-scheduling, contains pre-re-scheduling data for all re-scheduled
734 /// regions.
735 SmallVector<RegionSchedRevert> RegionReverts;
736 /// Whether we should revert all re-scheduled regions.
737 bool RevertAllRegions = false;
738
739 /// Returns the occupancy the stage is trying to achieve.
740 unsigned getStageTargetOccupancy() const;
741
742 /// Determines the stage's objective (increasing occupancy or reducing
743 /// spilling, set in \ref TargetOcc). Defines \ref RPTargets in all regions to
744 /// achieve that objective and mark those that don't achieve it in \ref
745 /// TargetRegions. Returns whether there is any target region.
746 bool setObjective();
747
748 /// In all regions set in \p Regions, saves pressure \p RPSave and clear it as
749 /// a target if its RP target has been reached.
750 void updateRPTargets(const BitVector &Regions, const GCNRegPressure &RPSave);
751
752 /// Fully recomputes RP from the DAG in \p Regions. Among those regions, sets
753 /// again all \ref TargetRegions that were optimistically marked as satisfied
754 /// but are actually not, and returns whether there were any such regions.
755 bool updateAndVerifyRPTargets(const BitVector &Regions);
756
757 /// Removes register \p Reg from the live-ins of regions set in \p LiveIn and
758 /// the live-outs of regions set in \p LiveOut.
759 void removeFromLiveMaps(Register Reg, const BitVector &LiveIn,
760 const BitVector &LiveOut);
761
762 /// Adds register \p Reg with mask \p Mask to the live-ins of regions set in
763 /// \p LiveIn and the live-outs of regions set in \p LiveOut.
764 void addToLiveMaps(Register Reg, LaneBitmask Mask, const BitVector &LiveIn,
765 const BitVector &LiveOut);
766
767 /// If remat alone did not increase occupancy to the target one, rollbacks all
768 /// rematerializations and resets live-ins/RP in all regions impacted by the
769 /// stage to their pre-stage values.
770 void finalizeGCNSchedStage() override;
771
772public:
773 bool initGCNSchedStage() override;
774
775 bool initGCNRegion() override;
776
777 void finalizeGCNRegion() override;
778
779 bool shouldRevertScheduling(unsigned WavesAfter) override;
780
781 PreRARematStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)
782 : GCNSchedStage(StageID, DAG), TargetRegions(DAG.Regions.size()),
783 RescheduleRegions(DAG.Regions.size()),
784 Remater(MF, DAG.Regions, *DAG.LIS) {
785 const unsigned NumRegions = DAG.Regions.size();
786 RPTargets.reserve(N: NumRegions);
787 }
788};
789
790class ILPInitialScheduleStage : public GCNSchedStage {
791public:
792 bool shouldRevertScheduling(unsigned WavesAfter) override;
793
794 ILPInitialScheduleStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)
795 : GCNSchedStage(StageID, DAG) {}
796};
797
798class MemoryClauseInitialScheduleStage : public GCNSchedStage {
799public:
800 bool shouldRevertScheduling(unsigned WavesAfter) override;
801
802 MemoryClauseInitialScheduleStage(GCNSchedStageID StageID,
803 GCNScheduleDAGMILive &DAG)
804 : GCNSchedStage(StageID, DAG) {}
805};
806
807// Live interval register pressure stage:
808// estimates register pressure accounting for live interval interference,
809// optionally reschedules the region with tigher register bounds.
810class LiveIntervalRPStage : public GCNSchedStage {
811public:
812 bool initGCNSchedStage() override;
813 bool initGCNRegion() override;
814 void finalizeGCNRegion() override;
815
816 LiveIntervalRPStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)
817 : GCNSchedStage(StageID, DAG) {}
818
819private:
820 unsigned SavedVGPRThresholdPercent = 0;
821 unsigned SavedVGPRExcessLimit = 0;
822 unsigned SavedVGPRCriticalLimit = 0;
823};
824
825class GCNPostScheduleDAGMILive final : public ScheduleDAGMI {
826private:
827 std::vector<std::unique_ptr<ScheduleDAGMutation>> SavedMutations;
828
829 bool HasIGLPInstrs = false;
830
831public:
832 void schedule() override;
833
834 void finalizeSchedule() override;
835
836 GCNPostScheduleDAGMILive(MachineSchedContext *C,
837 std::unique_ptr<MachineSchedStrategy> S,
838 bool RemoveKillFlags);
839};
840
841} // End namespace llvm
842
843#endif // LLVM_LIB_TARGET_AMDGPU_GCNSCHEDSTRATEGY_H
844