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 31namespace llvm { 32 33class SUnit; 34 35class 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 50public: 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 64 ~VLIWResourceModel() { 65 delete ResourcesModel; 66 } 67 68 void resetPacketState() { 69 Packet.clear(); 70 } 71 72 void resetDFA() { 73 ResourcesModel->clearResources(); 74 } 75 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); 83 unsigned getTotalPackets() const { return TotalPackets; } 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. 89class VLIWMachineScheduler : public ScheduleDAGMILive { 90public: 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 99 RegisterClassInfo *getRegClassInfo() { return RegClassInfo; } 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. 110class 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. 156 VLIWSchedBoundary(unsigned ID, const Twine &Name) 157 : Available(ID, Name+".A"), 158 Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {} 159 160 ~VLIWSchedBoundary() { 161 delete ResourceModel; 162 delete HazardRec; 163 } 164 165 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 191 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 209 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 227public: 228 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 229 enum { 230 TopQID = 1, 231 BotQID = 2, 232 LogMaxQID = 2 233 }; 234 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 247 unsigned reportPackets() { 248 return Top.ResourceModel->getTotalPackets() + 249 Bot.ResourceModel->getTotalPackets(); 250 } 251 252protected: 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