HexagonMachineScheduler.h revision cd81d94322a39503e4a3e87b6ee03d4fcb3465fb
158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger//===-- HexagonMachineScheduler.h - Custom Hexagon MI scheduler. ----===// 258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// 358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// The LLVM Compiler Infrastructure 458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// 558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// This file is distributed under the University of Illinois Open Source 658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// License. See LICENSE.TXT for details. 758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// 858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger//===----------------------------------------------------------------------===// 958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// 1058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// Custom Hexagon MI scheduler. 1158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// 1258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger//===----------------------------------------------------------------------===// 1358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 1458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#ifndef HEXAGONASMPRINTER_H 1558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#define HEXAGONASMPRINTER_H 1658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 1758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/ADT/PriorityQueue.h" 1858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/Analysis/AliasAnalysis.h" 1958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/CodeGen/MachineScheduler.h" 2158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/CodeGen/Passes.h" 2258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/CodeGen/RegisterClassInfo.h" 2358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/CodeGen/RegisterPressure.h" 2458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/CodeGen/ResourcePriorityQueue.h" 2558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/CodeGen/ScheduleDAGInstrs.h" 2658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 2758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/Support/CommandLine.h" 2858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/Support/Debug.h" 2958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "llvm/Support/ErrorHandling.h" 30910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger#include "llvm/Support/raw_ostream.h" 31910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger#include "llvm/Target/TargetInstrInfo.h" 32910f694aefb0b671dd8522a9afe9b6be645701c1Derek Sollenberger 3358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerusing namespace llvm; 3458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 3558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergernamespace llvm { 3658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger//===----------------------------------------------------------------------===// 3758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// ConvergingVLIWScheduler - Implementation of the standard 3858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger// MachineSchedStrategy. 3958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger//===----------------------------------------------------------------------===// 4058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 4158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergerclass VLIWResourceModel { 4258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger /// ResourcesModel - Represents VLIW state. 4358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger /// Not limited to VLIW targets per say, but assumes 4458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger /// definition of DFA by a target. 4558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger DFAPacketizer *ResourcesModel; 4658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 4758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger const TargetSchedModel *SchedModel; 4858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 4958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger /// Local packet/bundle model. Purely 50 /// internal to the MI schedulre at the time. 51 std::vector<SUnit*> Packet; 52 53 /// Total packets created. 54 unsigned TotalPackets; 55 56public: 57VLIWResourceModel(const TargetMachine &TM, const TargetSchedModel *SM) : 58 SchedModel(SM), TotalPackets(0) { 59 ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM, nullptr); 60 61 // This hard requirement could be relaxed, 62 // but for now do not let it proceed. 63 assert(ResourcesModel && "Unimplemented CreateTargetScheduleState."); 64 65 Packet.resize(SchedModel->getIssueWidth()); 66 Packet.clear(); 67 ResourcesModel->clearResources(); 68 } 69 70 ~VLIWResourceModel() { 71 delete ResourcesModel; 72 } 73 74 void resetPacketState() { 75 Packet.clear(); 76 } 77 78 void resetDFA() { 79 ResourcesModel->clearResources(); 80 } 81 82 void reset() { 83 Packet.clear(); 84 ResourcesModel->clearResources(); 85 } 86 87 bool isResourceAvailable(SUnit *SU); 88 bool reserveResources(SUnit *SU); 89 unsigned getTotalPackets() const { return TotalPackets; } 90}; 91 92/// Extend the standard ScheduleDAGMI to provide more context and override the 93/// top-level schedule() driver. 94class VLIWMachineScheduler : public ScheduleDAGMILive { 95public: 96 VLIWMachineScheduler(MachineSchedContext *C, 97 std::unique_ptr<MachineSchedStrategy> S) 98 : ScheduleDAGMILive(C, std::move(S)) {} 99 100 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's 101 /// time to do some work. 102 virtual void schedule() override; 103 /// Perform platform-specific DAG postprocessing. 104 void postprocessDAG(); 105}; 106 107/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics 108/// to balance the schedule. 109class ConvergingVLIWScheduler : public MachineSchedStrategy { 110 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; 116 117 // Register pressure values for the best candidate. 118 RegPressureDelta RPDelta; 119 120 // Best scheduling cost. 121 int SCost; 122 123 SchedCandidate(): SU(nullptr), SCost(0) {} 124 }; 125 /// Represent the type of SchedCandidate found within a single queue. 126 enum CandResult { 127 NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure, 128 BestCost}; 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; 135 const TargetSchedModel *SchedModel; 136 137 ReadyQueue Available; 138 ReadyQueue Pending; 139 bool CheckPending; 140 141 ScheduleHazardRecognizer *HazardRec; 142 VLIWResourceModel *ResourceModel; 143 144 unsigned CurrCycle; 145 unsigned IssueCount; 146 147 /// MinReadyCycle - Cycle of the soonest available instruction. 148 unsigned MinReadyCycle; 149 150 // Remember the greatest min operand latency. 151 unsigned MaxMinLatency; 152 153 /// Pending queues extend the ready queues with the same ID and the 154 /// PendingFlag set. 155 VLIWSchedBoundary(unsigned ID, const Twine &Name): 156 DAG(nullptr), SchedModel(nullptr), Available(ID, Name+".A"), 157 Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"), 158 CheckPending(false), HazardRec(nullptr), ResourceModel(nullptr), 159 CurrCycle(0), IssueCount(0), 160 MinReadyCycle(UINT_MAX), MaxMinLatency(0) {} 161 162 ~VLIWSchedBoundary() { 163 delete ResourceModel; 164 delete HazardRec; 165 } 166 167 void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) { 168 DAG = dag; 169 SchedModel = smodel; 170 } 171 172 bool isTop() const { 173 return Available.getID() == ConvergingVLIWScheduler::TopQID; 174 } 175 176 bool checkHazard(SUnit *SU); 177 178 void releaseNode(SUnit *SU, unsigned ReadyCycle); 179 180 void bumpCycle(); 181 182 void bumpNode(SUnit *SU); 183 184 void releasePending(); 185 186 void removeReady(SUnit *SU); 187 188 SUnit *pickOnlyChoice(); 189 }; 190 191 VLIWMachineScheduler *DAG; 192 const TargetSchedModel *SchedModel; 193 194 // State of the top and bottom scheduled instruction boundaries. 195 VLIWSchedBoundary Top; 196 VLIWSchedBoundary Bot; 197 198public: 199 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 200 enum { 201 TopQID = 1, 202 BotQID = 2, 203 LogMaxQID = 2 204 }; 205 206 ConvergingVLIWScheduler() 207 : DAG(nullptr), SchedModel(nullptr), Top(TopQID, "TopQ"), 208 Bot(BotQID, "BotQ") {} 209 210 virtual void initialize(ScheduleDAGMI *dag) override; 211 212 virtual SUnit *pickNode(bool &IsTopNode) override; 213 214 virtual void schedNode(SUnit *SU, bool IsTopNode) override; 215 216 virtual void releaseTopNode(SUnit *SU) override; 217 218 virtual void releaseBottomNode(SUnit *SU) override; 219 220 unsigned ReportPackets() { 221 return Top.ResourceModel->getTotalPackets() + 222 Bot.ResourceModel->getTotalPackets(); 223 } 224 225protected: 226 SUnit *pickNodeBidrectional(bool &IsTopNode); 227 228 int SchedulingCost(ReadyQueue &Q, 229 SUnit *SU, SchedCandidate &Candidate, 230 RegPressureDelta &Delta, bool verbose); 231 232 CandResult pickNodeFromQueue(ReadyQueue &Q, 233 const RegPressureTracker &RPTracker, 234 SchedCandidate &Candidate); 235#ifndef NDEBUG 236 void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, 237 PressureChange P = PressureChange()); 238#endif 239}; 240 241} // namespace 242 243 244#endif 245