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