565 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file10//11//===----------------------------------------------------------------------===//12 13#ifndef LLVM_LIB_TARGET_AMDGPU_GCNSCHEDSTRATEGY_H14#define LLVM_LIB_TARGET_AMDGPU_GCNSCHEDSTRATEGY_H15 16#include "GCNRegPressure.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/MapVector.h"19#include "llvm/CodeGen/MachineInstr.h"20#include "llvm/CodeGen/MachineScheduler.h"21 22namespace llvm {23 24class SIMachineFunctionInfo;25class SIRegisterInfo;26class GCNSubtarget;27class GCNSchedStage;28 29enum class GCNSchedStageID : unsigned {30 OccInitialSchedule = 0,31 UnclusteredHighRPReschedule = 1,32 ClusteredLowOccupancyReschedule = 2,33 PreRARematerialize = 3,34 ILPInitialSchedule = 4,35 MemoryClauseInitialSchedule = 536};37 38#ifndef NDEBUG39raw_ostream &operator<<(raw_ostream &OS, const GCNSchedStageID &StageID);40#endif41 42/// This is a minimal scheduler strategy. The main difference between this43/// and the GenericScheduler is that GCNSchedStrategy uses different44/// heuristics to determine excess/critical pressure sets.45class GCNSchedStrategy : public GenericScheduler {46protected:47 SUnit *pickNodeBidirectional(bool &IsTopNode, bool &PickedPending);48 49 void pickNodeFromQueue(SchedBoundary &Zone, const CandPolicy &ZonePolicy,50 const RegPressureTracker &RPTracker,51 SchedCandidate &Cand, bool &IsPending,52 bool IsBottomUp);53 54 void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,55 const RegPressureTracker &RPTracker,56 const SIRegisterInfo *SRI, unsigned SGPRPressure,57 unsigned VGPRPressure, bool IsBottomUp);58 59 /// Evaluates instructions in the pending queue using a subset of scheduling60 /// heuristics.61 ///62 /// Instructions that cannot be issued due to hardware constraints are placed63 /// in the pending queue rather than the available queue, making them normally64 /// invisible to scheduling heuristics. However, in certain scenarios (such as65 /// avoiding register spilling), it may be beneficial to consider scheduling66 /// these not-yet-ready instructions.67 bool tryPendingCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,68 SchedBoundary *Zone) const;69 70 void printCandidateDecision(const SchedCandidate &Current,71 const SchedCandidate &Preferred);72 73 std::vector<unsigned> Pressure;74 75 std::vector<unsigned> MaxPressure;76 77 unsigned SGPRExcessLimit;78 79 unsigned VGPRExcessLimit;80 81 unsigned TargetOccupancy;82 83 MachineFunction *MF;84 85 // Scheduling stages for this strategy.86 SmallVector<GCNSchedStageID, 4> SchedStages;87 88 // Pointer to the current SchedStageID.89 SmallVectorImpl<GCNSchedStageID>::iterator CurrentStage = nullptr;90 91 // GCN RP Tracker for top-down scheduling92 mutable GCNDownwardRPTracker DownwardTracker;93 94 // GCN RP Tracker for botttom-up scheduling95 mutable GCNUpwardRPTracker UpwardTracker;96 97public:98 // schedule() have seen register pressure over the critical limits and had to99 // track register pressure for actual scheduling heuristics.100 bool HasHighPressure;101 102 // Schedule known to have excess register pressure. Be more conservative in103 // increasing ILP and preserving VGPRs.104 bool KnownExcessRP = false;105 106 // An error margin is necessary because of poor performance of the generic RP107 // tracker and can be adjusted up for tuning heuristics to try and more108 // aggressively reduce register pressure.109 unsigned ErrorMargin = 3;110 111 // Bias for SGPR limits under a high register pressure.112 const unsigned HighRPSGPRBias = 7;113 114 // Bias for VGPR limits under a high register pressure.115 const unsigned HighRPVGPRBias = 7;116 117 unsigned SGPRCriticalLimit;118 119 unsigned VGPRCriticalLimit;120 121 unsigned SGPRLimitBias = 0;122 123 unsigned VGPRLimitBias = 0;124 125 GCNSchedStrategy(const MachineSchedContext *C);126 127 SUnit *pickNode(bool &IsTopNode) override;128 129 void schedNode(SUnit *SU, bool IsTopNode) override;130 131 void initialize(ScheduleDAGMI *DAG) override;132 133 unsigned getTargetOccupancy() { return TargetOccupancy; }134 135 void setTargetOccupancy(unsigned Occ) { TargetOccupancy = Occ; }136 137 GCNSchedStageID getCurrentStage();138 139 // Advances stage. Returns true if there are remaining stages.140 bool advanceStage();141 142 bool hasNextStage() const;143 144 GCNSchedStageID getNextStage() const;145 146 GCNDownwardRPTracker *getDownwardTracker() { return &DownwardTracker; }147 148 GCNUpwardRPTracker *getUpwardTracker() { return &UpwardTracker; }149};150 151/// The goal of this scheduling strategy is to maximize kernel occupancy (i.e.152/// maximum number of waves per simd).153class GCNMaxOccupancySchedStrategy final : public GCNSchedStrategy {154public:155 GCNMaxOccupancySchedStrategy(const MachineSchedContext *C,156 bool IsLegacyScheduler = false);157};158 159/// The goal of this scheduling strategy is to maximize ILP for a single wave160/// (i.e. latency hiding).161class GCNMaxILPSchedStrategy final : public GCNSchedStrategy {162protected:163 bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,164 SchedBoundary *Zone) const override;165 166public:167 GCNMaxILPSchedStrategy(const MachineSchedContext *C);168};169 170/// The goal of this scheduling strategy is to maximize memory clause for a171/// single wave.172class GCNMaxMemoryClauseSchedStrategy final : public GCNSchedStrategy {173protected:174 bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,175 SchedBoundary *Zone) const override;176 177public:178 GCNMaxMemoryClauseSchedStrategy(const MachineSchedContext *C);179};180 181class ScheduleMetrics {182 unsigned ScheduleLength;183 unsigned BubbleCycles;184 185public:186 ScheduleMetrics() = default;187 ScheduleMetrics(unsigned L, unsigned BC)188 : ScheduleLength(L), BubbleCycles(BC) {}189 unsigned getLength() const { return ScheduleLength; }190 unsigned getBubbles() const { return BubbleCycles; }191 unsigned getMetric() const {192 unsigned Metric = (BubbleCycles * ScaleFactor) / ScheduleLength;193 // Metric is zero if the amount of bubbles is less than 1% which is too194 // small. So, return 1.195 return Metric ? Metric : 1;196 }197 static const unsigned ScaleFactor;198};199 200inline raw_ostream &operator<<(raw_ostream &OS, const ScheduleMetrics &Sm) {201 dbgs() << "\n Schedule Metric (scaled by "202 << ScheduleMetrics::ScaleFactor203 << " ) is: " << Sm.getMetric() << " [ " << Sm.getBubbles() << "/"204 << Sm.getLength() << " ]\n";205 return OS;206}207 208class GCNScheduleDAGMILive;209class RegionPressureMap {210 GCNScheduleDAGMILive *DAG;211 // The live in/out pressure as indexed by the first or last MI in the region212 // before scheduling.213 DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet> RegionLiveRegMap;214 // The mapping of RegionIDx to key instruction215 DenseMap<unsigned, MachineInstr *> IdxToInstruction;216 // Whether we are calculating LiveOuts or LiveIns217 bool IsLiveOut;218 219public:220 RegionPressureMap() = default;221 RegionPressureMap(GCNScheduleDAGMILive *GCNDAG, bool LiveOut)222 : DAG(GCNDAG), IsLiveOut(LiveOut) {}223 // Build the Instr->LiveReg and RegionIdx->Instr maps224 void buildLiveRegMap();225 226 // Retrieve the LiveReg for a given RegionIdx227 GCNRPTracker::LiveRegSet &getLiveRegsForRegionIdx(unsigned RegionIdx) {228 assert(IdxToInstruction.contains(RegionIdx));229 MachineInstr *Key = IdxToInstruction[RegionIdx];230 return RegionLiveRegMap[Key];231 }232};233 234/// A region's boundaries i.e. a pair of instruction bundle iterators. The lower235/// boundary is inclusive, the upper boundary is exclusive.236using RegionBoundaries =237 std::pair<MachineBasicBlock::iterator, MachineBasicBlock::iterator>;238 239class GCNScheduleDAGMILive final : public ScheduleDAGMILive {240 friend class GCNSchedStage;241 friend class OccInitialScheduleStage;242 friend class UnclusteredHighRPStage;243 friend class ClusteredLowOccStage;244 friend class PreRARematStage;245 friend class ILPInitialScheduleStage;246 friend class RegionPressureMap;247 248 const GCNSubtarget &ST;249 250 SIMachineFunctionInfo &MFI;251 252 // Occupancy target at the beginning of function scheduling cycle.253 unsigned StartingOccupancy;254 255 // Minimal real occupancy recorder for the function.256 unsigned MinOccupancy;257 258 // Vector of regions recorder for later rescheduling259 SmallVector<RegionBoundaries, 32> Regions;260 261 // Record regions with high register pressure.262 BitVector RegionsWithHighRP;263 264 // Record regions with excess register pressure over the physical register265 // limit. Register pressure in these regions usually will result in spilling.266 BitVector RegionsWithExcessRP;267 268 // Regions that have IGLP instructions (SCHED_GROUP_BARRIER or IGLP_OPT).269 BitVector RegionsWithIGLPInstrs;270 271 // Region live-in cache.272 SmallVector<GCNRPTracker::LiveRegSet, 32> LiveIns;273 274 // Region pressure cache.275 SmallVector<GCNRegPressure, 32> Pressure;276 277 // Temporary basic block live-in cache.278 DenseMap<const MachineBasicBlock *, GCNRPTracker::LiveRegSet> MBBLiveIns;279 280 // The map of the initial first region instruction to region live in registers281 DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet> BBLiveInMap;282 283 // Calculate the map of the initial first region instruction to region live in284 // registers285 DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet> getRegionLiveInMap() const;286 287 // Calculate the map of the initial last region instruction to region live out288 // registers289 DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet>290 getRegionLiveOutMap() const;291 292 // The live out registers per region. These are internally stored as a map of293 // the initial last region instruction to region live out registers, but can294 // be retreived with the regionIdx by calls to getLiveRegsForRegionIdx.295 RegionPressureMap RegionLiveOuts;296 297 // Return current region pressure.298 GCNRegPressure getRealRegPressure(unsigned RegionIdx) const;299 300 // Compute and cache live-ins and pressure for all regions in block.301 void computeBlockPressure(unsigned RegionIdx, const MachineBasicBlock *MBB);302 303 /// If necessary, updates a region's boundaries following insertion ( \p NewMI304 /// != nullptr) or removal ( \p NewMI == nullptr) of a \p MI in the region.305 /// For an MI removal, this must be called before the MI is actually erased306 /// from its parent MBB.307 void updateRegionBoundaries(RegionBoundaries &RegionBounds,308 MachineBasicBlock::iterator MI,309 MachineInstr *NewMI);310 311 void runSchedStages();312 313 std::unique_ptr<GCNSchedStage> createSchedStage(GCNSchedStageID SchedStageID);314 315public:316 GCNScheduleDAGMILive(MachineSchedContext *C,317 std::unique_ptr<MachineSchedStrategy> S);318 319 void schedule() override;320 321 void finalizeSchedule() override;322};323 324// GCNSchedStrategy applies multiple scheduling stages to a function.325class GCNSchedStage {326protected:327 GCNScheduleDAGMILive &DAG;328 329 GCNSchedStrategy &S;330 331 MachineFunction &MF;332 333 SIMachineFunctionInfo &MFI;334 335 const GCNSubtarget &ST;336 337 const GCNSchedStageID StageID;338 339 // The current block being scheduled.340 MachineBasicBlock *CurrentMBB = nullptr;341 342 // Current region index.343 unsigned RegionIdx = 0;344 345 // Record the original order of instructions before scheduling.346 std::vector<MachineInstr *> Unsched;347 348 // RP before scheduling the current region.349 GCNRegPressure PressureBefore;350 351 // RP after scheduling the current region.352 GCNRegPressure PressureAfter;353 354 std::vector<std::unique_ptr<ScheduleDAGMutation>> SavedMutations;355 356 GCNSchedStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG);357 358public:359 // Initialize state for a scheduling stage. Returns false if the current stage360 // should be skipped.361 virtual bool initGCNSchedStage();362 363 // Finalize state after finishing a scheduling pass on the function.364 virtual void finalizeGCNSchedStage();365 366 // Setup for scheduling a region. Returns false if the current region should367 // be skipped.368 virtual bool initGCNRegion();369 370 // Track whether a new region is also a new MBB.371 void setupNewBlock();372 373 // Finalize state after scheudling a region.374 void finalizeGCNRegion();375 376 // Check result of scheduling.377 void checkScheduling();378 379 // computes the given schedule virtual execution time in clocks380 ScheduleMetrics getScheduleMetrics(const std::vector<SUnit> &InputSchedule);381 ScheduleMetrics getScheduleMetrics(const GCNScheduleDAGMILive &DAG);382 unsigned computeSUnitReadyCycle(const SUnit &SU, unsigned CurrCycle,383 DenseMap<unsigned, unsigned> &ReadyCycles,384 const TargetSchedModel &SM);385 386 // Returns true if scheduling should be reverted.387 virtual bool shouldRevertScheduling(unsigned WavesAfter);388 389 // Returns true if current region has known excess pressure.390 bool isRegionWithExcessRP() const {391 return DAG.RegionsWithExcessRP[RegionIdx];392 }393 394 // The region number this stage is currently working on395 unsigned getRegionIdx() { return RegionIdx; }396 397 // Returns true if the new schedule may result in more spilling.398 bool mayCauseSpilling(unsigned WavesAfter);399 400 // Attempt to revert scheduling for this region.401 void revertScheduling();402 403 void advanceRegion() { RegionIdx++; }404 405 virtual ~GCNSchedStage() = default;406};407 408class OccInitialScheduleStage : public GCNSchedStage {409public:410 bool shouldRevertScheduling(unsigned WavesAfter) override;411 412 OccInitialScheduleStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)413 : GCNSchedStage(StageID, DAG) {}414};415 416class UnclusteredHighRPStage : public GCNSchedStage {417private:418 // Save the initial occupancy before starting this stage.419 unsigned InitialOccupancy;420 // Save the temporary target occupancy before starting this stage.421 unsigned TempTargetOccupancy;422 // Track whether any region was scheduled by this stage.423 bool IsAnyRegionScheduled;424 425public:426 bool initGCNSchedStage() override;427 428 void finalizeGCNSchedStage() override;429 430 bool initGCNRegion() override;431 432 bool shouldRevertScheduling(unsigned WavesAfter) override;433 434 UnclusteredHighRPStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)435 : GCNSchedStage(StageID, DAG) {}436};437 438// Retry function scheduling if we found resulting occupancy and it is439// lower than used for other scheduling passes. This will give more freedom440// to schedule low register pressure blocks.441class ClusteredLowOccStage : public GCNSchedStage {442public:443 bool initGCNSchedStage() override;444 445 bool initGCNRegion() override;446 447 bool shouldRevertScheduling(unsigned WavesAfter) override;448 449 ClusteredLowOccStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)450 : GCNSchedStage(StageID, DAG) {}451};452 453/// Attempts to reduce function spilling or, if there is no spilling, to454/// increase function occupancy by one with respect to ArchVGPR usage by sinking455/// rematerializable instructions to their use. When the stage456/// estimates reducing spilling or increasing occupancy is possible, as few457/// instructions as possible are rematerialized to reduce potential negative458/// effects on function latency.459class PreRARematStage : public GCNSchedStage {460private:461 /// Useful information about a rematerializable instruction.462 struct RematInstruction {463 /// Single use of the rematerializable instruction's defined register,464 /// located in a different block.465 MachineInstr *UseMI;466 /// Rematerialized version of \p DefMI, set in467 /// PreRARematStage::rematerialize. Used for reverting rematerializations.468 MachineInstr *RematMI;469 /// Set of regions in which the rematerializable instruction's defined470 /// register is a live-in.471 SmallDenseSet<unsigned, 4> LiveInRegions;472 473 RematInstruction(MachineInstr *UseMI) : UseMI(UseMI) {}474 };475 476 /// Maps all MIs to their parent region. MI terminators are considered to be477 /// outside the region they delimitate, and as such are not stored in the map.478 DenseMap<MachineInstr *, unsigned> MIRegion;479 /// Parent MBB to each region, in region order.480 SmallVector<MachineBasicBlock *> RegionBB;481 /// Collects instructions to rematerialize.482 MapVector<MachineInstr *, RematInstruction> Rematerializations;483 /// Collects regions whose live-ins or register pressure will change due to484 /// rematerializations.485 DenseMap<unsigned, GCNRegPressure> ImpactedRegions;486 /// In case we need to rollback rematerializations, save lane masks for all487 /// rematerialized registers in all regions in which they are live-ins.488 DenseMap<std::pair<unsigned, Register>, LaneBitmask> RegMasks;489 /// After successful stage initialization, indicates which regions should be490 /// rescheduled.491 BitVector RescheduleRegions;492 /// The target occupancy the stage is trying to achieve. Empty when the493 /// objective is spilling reduction.494 std::optional<unsigned> TargetOcc;495 /// Achieved occupancy *only* through rematerializations (pre-rescheduling).496 /// Smaller than or equal to the target occupancy.497 unsigned AchievedOcc;498 499 /// Returns whether remat can reduce spilling or increase function occupancy500 /// by 1 through rematerialization. If it can do one, collects instructions in501 /// PreRARematStage::Rematerializations and sets the target occupancy in502 /// PreRARematStage::TargetOccupancy.503 bool canIncreaseOccupancyOrReduceSpill();504 505 /// Whether the MI is rematerializable506 bool isReMaterializable(const MachineInstr &MI);507 508 /// Rematerializes all instructions in PreRARematStage::Rematerializations509 /// and stores the achieved occupancy after remat in510 /// PreRARematStage::AchievedOcc.511 void rematerialize();512 513 /// If remat alone did not increase occupancy to the target one, rollbacks all514 /// rematerializations and resets live-ins/RP in all regions impacted by the515 /// stage to their pre-stage values.516 void finalizeGCNSchedStage() override;517 518public:519 bool initGCNSchedStage() override;520 521 bool initGCNRegion() override;522 523 bool shouldRevertScheduling(unsigned WavesAfter) override;524 525 PreRARematStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)526 : GCNSchedStage(StageID, DAG), RescheduleRegions(DAG.Regions.size()) {}527};528 529class ILPInitialScheduleStage : public GCNSchedStage {530public:531 bool shouldRevertScheduling(unsigned WavesAfter) override;532 533 ILPInitialScheduleStage(GCNSchedStageID StageID, GCNScheduleDAGMILive &DAG)534 : GCNSchedStage(StageID, DAG) {}535};536 537class MemoryClauseInitialScheduleStage : public GCNSchedStage {538public:539 bool shouldRevertScheduling(unsigned WavesAfter) override;540 541 MemoryClauseInitialScheduleStage(GCNSchedStageID StageID,542 GCNScheduleDAGMILive &DAG)543 : GCNSchedStage(StageID, DAG) {}544};545 546class GCNPostScheduleDAGMILive final : public ScheduleDAGMI {547private:548 std::vector<std::unique_ptr<ScheduleDAGMutation>> SavedMutations;549 550 bool HasIGLPInstrs = false;551 552public:553 void schedule() override;554 555 void finalizeSchedule() override;556 557 GCNPostScheduleDAGMILive(MachineSchedContext *C,558 std::unique_ptr<MachineSchedStrategy> S,559 bool RemoveKillFlags);560};561 562} // End namespace llvm563 564#endif // LLVM_LIB_TARGET_AMDGPU_GCNSCHEDSTRATEGY_H565