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