1 //===- VLIWMachineScheduler.h - VLIW-Focused Scheduling Pass ----*- 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 //===----------------------------------------------------------------------===// 10 11 #ifndef LLVM_CODEGEN_VLIWMACHINESCHEDULER_H 12 #define LLVM_CODEGEN_VLIWMACHINESCHEDULER_H 13 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/ADT/Twine.h" 16 #include "llvm/CodeGen/MachineScheduler.h" 17 #include "llvm/CodeGen/TargetSchedule.h" 18 #include <limits> 19 #include <memory> 20 #include <utility> 21 22 namespace llvm { 23 24 class DFAPacketizer; 25 class RegisterClassInfo; 26 class ScheduleHazardRecognizer; 27 class SUnit; 28 class TargetInstrInfo; 29 class TargetSubtargetInfo; 30 31 class VLIWResourceModel { 32 protected: 33 const TargetInstrInfo *TII; 34 35 /// ResourcesModel - Represents VLIW state. 36 /// Not limited to VLIW targets per se, but assumes definition of resource 37 /// model by a target. 38 DFAPacketizer *ResourcesModel; 39 40 const TargetSchedModel *SchedModel; 41 42 /// Local packet/bundle model. Purely 43 /// internal to the MI scheduler at the time. 44 SmallVector<SUnit *> Packet; 45 46 /// Total packets created. 47 unsigned TotalPackets = 0; 48 49 public: 50 VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM); 51 VLIWResourceModel &operator=(const VLIWResourceModel &other) = delete; 52 VLIWResourceModel(const VLIWResourceModel &other) = delete; 53 virtual ~VLIWResourceModel(); 54 55 virtual void reset(); 56 57 virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu); 58 virtual bool isResourceAvailable(SUnit *SU, bool IsTop); 59 virtual bool reserveResources(SUnit *SU, bool IsTop); 60 unsigned getTotalPackets() const { return TotalPackets; } 61 size_t getPacketInstCount() const { return Packet.size(); } 62 bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); } 63 64 protected: 65 virtual DFAPacketizer *createPacketizer(const TargetSubtargetInfo &STI) const; 66 }; 67 68 /// Extend the standard ScheduleDAGMILive to provide more context and override 69 /// the top-level schedule() driver. 70 class VLIWMachineScheduler : public ScheduleDAGMILive { 71 public: 72 VLIWMachineScheduler(MachineSchedContext *C, 73 std::unique_ptr<MachineSchedStrategy> S) 74 : ScheduleDAGMILive(C, std::move(S)) {} 75 76 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 77 /// time to do some work. 78 void schedule() override; 79 80 RegisterClassInfo *getRegClassInfo() { return RegClassInfo; } 81 int getBBSize() { return BB->size(); } 82 }; 83 84 //===----------------------------------------------------------------------===// 85 // ConvergingVLIWScheduler - Implementation of a VLIW-aware 86 // MachineSchedStrategy. 87 //===----------------------------------------------------------------------===// 88 89 class ConvergingVLIWScheduler : public MachineSchedStrategy { 90 protected: 91 /// Store the state used by ConvergingVLIWScheduler heuristics, required 92 /// for the lifetime of one invocation of pickNode(). 93 struct SchedCandidate { 94 // The best SUnit candidate. 95 SUnit *SU = nullptr; 96 97 // Register pressure values for the best candidate. 98 RegPressureDelta RPDelta; 99 100 // Best scheduling cost. 101 int SCost = 0; 102 103 SchedCandidate() = default; 104 }; 105 /// Represent the type of SchedCandidate found within a single queue. 106 enum CandResult { 107 NoCand, 108 NodeOrder, 109 SingleExcess, 110 SingleCritical, 111 SingleMax, 112 MultiPressure, 113 BestCost, 114 Weak 115 }; 116 117 // Constants used to denote relative importance of 118 // heuristic components for cost computation. 119 static constexpr unsigned PriorityOne = 200; 120 static constexpr unsigned PriorityTwo = 50; 121 static constexpr unsigned PriorityThree = 75; 122 static constexpr unsigned ScaleTwo = 10; 123 124 /// Each Scheduling boundary is associated with ready queues. It tracks the 125 /// current cycle in whichever direction at has moved, and maintains the state 126 /// of "hazards" and other interlocks at the current cycle. 127 struct VLIWSchedBoundary { 128 VLIWMachineScheduler *DAG = nullptr; 129 const TargetSchedModel *SchedModel = nullptr; 130 131 ReadyQueue Available; 132 ReadyQueue Pending; 133 bool CheckPending = false; 134 135 ScheduleHazardRecognizer *HazardRec = nullptr; 136 VLIWResourceModel *ResourceModel = nullptr; 137 138 unsigned CurrCycle = 0; 139 unsigned IssueCount = 0; 140 unsigned CriticalPathLength = 0; 141 142 /// MinReadyCycle - Cycle of the soonest available instruction. 143 unsigned MinReadyCycle = std::numeric_limits<unsigned>::max(); 144 145 // Remember the greatest min operand latency. 146 unsigned MaxMinLatency = 0; 147 148 /// Pending queues extend the ready queues with the same ID and the 149 /// PendingFlag set. 150 VLIWSchedBoundary(unsigned ID, const Twine &Name) 151 : Available(ID, Name + ".A"), 152 Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name + ".P") {} 153 154 ~VLIWSchedBoundary(); 155 VLIWSchedBoundary &operator=(const VLIWSchedBoundary &other) = delete; 156 VLIWSchedBoundary(const VLIWSchedBoundary &other) = delete; 157 158 void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) { 159 DAG = dag; 160 SchedModel = smodel; 161 CurrCycle = 0; 162 IssueCount = 0; 163 // Initialize the critical path length limit, which used by the scheduling 164 // cost model to determine the value for scheduling an instruction. We use 165 // a slightly different heuristic for small and large functions. For small 166 // functions, it's important to use the height/depth of the instruction. 167 // For large functions, prioritizing by height or depth increases spills. 168 const auto BBSize = DAG->getBBSize(); 169 CriticalPathLength = BBSize / SchedModel->getIssueWidth(); 170 if (BBSize < 50) 171 // We divide by two as a cheap and simple heuristic to reduce the 172 // critcal path length, which increases the priority of using the graph 173 // height/depth in the scheduler's cost computation. 174 CriticalPathLength >>= 1; 175 else { 176 // For large basic blocks, we prefer a larger critical path length to 177 // decrease the priority of using the graph height/depth. 178 unsigned MaxPath = 0; 179 for (auto &SU : DAG->SUnits) 180 MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth()); 181 CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1; 182 } 183 } 184 185 bool isTop() const { 186 return Available.getID() == ConvergingVLIWScheduler::TopQID; 187 } 188 189 bool checkHazard(SUnit *SU); 190 191 void releaseNode(SUnit *SU, unsigned ReadyCycle); 192 193 void bumpCycle(); 194 195 void bumpNode(SUnit *SU); 196 197 void releasePending(); 198 199 void removeReady(SUnit *SU); 200 201 SUnit *pickOnlyChoice(); 202 203 bool isLatencyBound(SUnit *SU) { 204 if (CurrCycle >= CriticalPathLength) 205 return true; 206 unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth(); 207 return CriticalPathLength - CurrCycle <= PathLength; 208 } 209 }; 210 211 VLIWMachineScheduler *DAG = nullptr; 212 const TargetSchedModel *SchedModel = nullptr; 213 214 // State of the top and bottom scheduled instruction boundaries. 215 VLIWSchedBoundary Top; 216 VLIWSchedBoundary Bot; 217 218 /// List of pressure sets that have a high pressure level in the region. 219 SmallVector<bool> HighPressureSets; 220 221 public: 222 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 223 enum { TopQID = 1, BotQID = 2, LogMaxQID = 2 }; 224 225 ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} 226 virtual ~ConvergingVLIWScheduler() = default; 227 228 void initialize(ScheduleDAGMI *dag) override; 229 230 SUnit *pickNode(bool &IsTopNode) override; 231 232 void schedNode(SUnit *SU, bool IsTopNode) override; 233 234 void releaseTopNode(SUnit *SU) override; 235 236 void releaseBottomNode(SUnit *SU) override; 237 238 unsigned reportPackets() { 239 return Top.ResourceModel->getTotalPackets() + 240 Bot.ResourceModel->getTotalPackets(); 241 } 242 243 protected: 244 virtual VLIWResourceModel * 245 createVLIWResourceModel(const TargetSubtargetInfo &STI, 246 const TargetSchedModel *SchedModel) const; 247 248 SUnit *pickNodeBidrectional(bool &IsTopNode); 249 250 int pressureChange(const SUnit *SU, bool isBotUp); 251 252 virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU, 253 SchedCandidate &Candidate, RegPressureDelta &Delta, 254 bool verbose); 255 256 CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, 257 const RegPressureTracker &RPTracker, 258 SchedCandidate &Candidate); 259 #ifndef NDEBUG 260 void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, 261 int Cost, PressureChange P = PressureChange()); 262 263 void readyQueueVerboseDump(const RegPressureTracker &RPTracker, 264 SchedCandidate &Candidate, ReadyQueue &Q); 265 #endif 266 }; 267 268 } // end namespace llvm 269 270 #endif // LLVM_CODEGEN_VLIWMACHINESCHEDULER_H 271