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