1 //===-- HexagonMachineScheduler.h - Custom Hexagon MI scheduler. ----===// 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/PriorityQueue.h" 18 #include "llvm/Analysis/AliasAnalysis.h" 19 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 20 #include "llvm/CodeGen/MachineScheduler.h" 21 #include "llvm/CodeGen/Passes.h" 22 #include "llvm/CodeGen/RegisterClassInfo.h" 23 #include "llvm/CodeGen/RegisterPressure.h" 24 #include "llvm/CodeGen/ResourcePriorityQueue.h" 25 #include "llvm/CodeGen/ScheduleDAGInstrs.h" 26 #include "llvm/CodeGen/ScheduleHazardRecognizer.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/Support/ErrorHandling.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include "llvm/Target/TargetInstrInfo.h" 31 32 using namespace llvm; 33 34 namespace llvm { 35 //===----------------------------------------------------------------------===// 36 // ConvergingVLIWScheduler - Implementation of the standard 37 // MachineSchedStrategy. 38 //===----------------------------------------------------------------------===// 39 40 class VLIWResourceModel { 41 /// ResourcesModel - Represents VLIW state. 42 /// Not limited to VLIW targets per say, but assumes 43 /// definition of DFA by a target. 44 DFAPacketizer *ResourcesModel; 45 46 const TargetSchedModel *SchedModel; 47 48 /// Local packet/bundle model. Purely 49 /// internal to the MI schedulre at the time. 50 std::vector<SUnit*> Packet; 51 52 /// Total packets created. 53 unsigned TotalPackets; 54 55 public: VLIWResourceModel(const TargetSubtargetInfo & STI,const TargetSchedModel * SM)56 VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM) 57 : SchedModel(SM), TotalPackets(0) { 58 ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI); 59 60 // This hard requirement could be relaxed, 61 // but for now do not let it proceed. 62 assert(ResourcesModel && "Unimplemented CreateTargetScheduleState."); 63 64 Packet.resize(SchedModel->getIssueWidth()); 65 Packet.clear(); 66 ResourcesModel->clearResources(); 67 } 68 ~VLIWResourceModel()69 ~VLIWResourceModel() { 70 delete ResourcesModel; 71 } 72 resetPacketState()73 void resetPacketState() { 74 Packet.clear(); 75 } 76 resetDFA()77 void resetDFA() { 78 ResourcesModel->clearResources(); 79 } 80 reset()81 void reset() { 82 Packet.clear(); 83 ResourcesModel->clearResources(); 84 } 85 86 bool isResourceAvailable(SUnit *SU); 87 bool reserveResources(SUnit *SU); getTotalPackets()88 unsigned getTotalPackets() const { return TotalPackets; } 89 }; 90 91 /// Extend the standard ScheduleDAGMI to provide more context and override the 92 /// top-level schedule() driver. 93 class VLIWMachineScheduler : public ScheduleDAGMILive { 94 public: VLIWMachineScheduler(MachineSchedContext * C,std::unique_ptr<MachineSchedStrategy> S)95 VLIWMachineScheduler(MachineSchedContext *C, 96 std::unique_ptr<MachineSchedStrategy> S) 97 : ScheduleDAGMILive(C, std::move(S)) {} 98 99 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 100 /// time to do some work. 101 void schedule() override; 102 /// Perform platform-specific DAG postprocessing. 103 void postprocessDAG(); 104 }; 105 106 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics 107 /// to balance the schedule. 108 class ConvergingVLIWScheduler : public MachineSchedStrategy { 109 110 /// Store the state used by ConvergingVLIWScheduler heuristics, required 111 /// for the lifetime of one invocation of pickNode(). 112 struct SchedCandidate { 113 // The best SUnit candidate. 114 SUnit *SU; 115 116 // Register pressure values for the best candidate. 117 RegPressureDelta RPDelta; 118 119 // Best scheduling cost. 120 int SCost; 121 SchedCandidateSchedCandidate122 SchedCandidate(): SU(nullptr), SCost(0) {} 123 }; 124 /// Represent the type of SchedCandidate found within a single queue. 125 enum CandResult { 126 NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure, 127 BestCost}; 128 129 /// Each Scheduling boundary is associated with ready queues. It tracks the 130 /// current cycle in whichever direction at has moved, and maintains the state 131 /// of "hazards" and other interlocks at the current cycle. 132 struct VLIWSchedBoundary { 133 VLIWMachineScheduler *DAG; 134 const TargetSchedModel *SchedModel; 135 136 ReadyQueue Available; 137 ReadyQueue Pending; 138 bool CheckPending; 139 140 ScheduleHazardRecognizer *HazardRec; 141 VLIWResourceModel *ResourceModel; 142 143 unsigned CurrCycle; 144 unsigned IssueCount; 145 146 /// MinReadyCycle - Cycle of the soonest available instruction. 147 unsigned MinReadyCycle; 148 149 // Remember the greatest min operand latency. 150 unsigned MaxMinLatency; 151 152 /// Pending queues extend the ready queues with the same ID and the 153 /// PendingFlag set. VLIWSchedBoundaryVLIWSchedBoundary154 VLIWSchedBoundary(unsigned ID, const Twine &Name): 155 DAG(nullptr), SchedModel(nullptr), Available(ID, Name+".A"), 156 Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"), 157 CheckPending(false), HazardRec(nullptr), ResourceModel(nullptr), 158 CurrCycle(0), IssueCount(0), 159 MinReadyCycle(UINT_MAX), MaxMinLatency(0) {} 160 ~VLIWSchedBoundaryVLIWSchedBoundary161 ~VLIWSchedBoundary() { 162 delete ResourceModel; 163 delete HazardRec; 164 } 165 initVLIWSchedBoundary166 void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) { 167 DAG = dag; 168 SchedModel = smodel; 169 } 170 isTopVLIWSchedBoundary171 bool isTop() const { 172 return Available.getID() == ConvergingVLIWScheduler::TopQID; 173 } 174 175 bool checkHazard(SUnit *SU); 176 177 void releaseNode(SUnit *SU, unsigned ReadyCycle); 178 179 void bumpCycle(); 180 181 void bumpNode(SUnit *SU); 182 183 void releasePending(); 184 185 void removeReady(SUnit *SU); 186 187 SUnit *pickOnlyChoice(); 188 }; 189 190 VLIWMachineScheduler *DAG; 191 const TargetSchedModel *SchedModel; 192 193 // State of the top and bottom scheduled instruction boundaries. 194 VLIWSchedBoundary Top; 195 VLIWSchedBoundary Bot; 196 197 public: 198 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 199 enum { 200 TopQID = 1, 201 BotQID = 2, 202 LogMaxQID = 2 203 }; 204 ConvergingVLIWScheduler()205 ConvergingVLIWScheduler() 206 : DAG(nullptr), SchedModel(nullptr), Top(TopQID, "TopQ"), 207 Bot(BotQID, "BotQ") {} 208 209 void initialize(ScheduleDAGMI *dag) override; 210 211 SUnit *pickNode(bool &IsTopNode) override; 212 213 void schedNode(SUnit *SU, bool IsTopNode) override; 214 215 void releaseTopNode(SUnit *SU) override; 216 217 void releaseBottomNode(SUnit *SU) override; 218 ReportPackets()219 unsigned ReportPackets() { 220 return Top.ResourceModel->getTotalPackets() + 221 Bot.ResourceModel->getTotalPackets(); 222 } 223 224 protected: 225 SUnit *pickNodeBidrectional(bool &IsTopNode); 226 227 int SchedulingCost(ReadyQueue &Q, 228 SUnit *SU, SchedCandidate &Candidate, 229 RegPressureDelta &Delta, bool verbose); 230 231 CandResult pickNodeFromQueue(ReadyQueue &Q, 232 const RegPressureTracker &RPTracker, 233 SchedCandidate &Candidate); 234 #ifndef NDEBUG 235 void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, 236 PressureChange P = PressureChange()); 237 #endif 238 }; 239 240 } // namespace 241 242 243 #endif 244