1 //===-- HexagonMachineScheduler.h - Custom Hexagon MI scheduler. ----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Custom Hexagon MI scheduler.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
15 #define LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
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/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/ErrorHandling.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include "llvm/Target/TargetInstrInfo.h"
36 //===----------------------------------------------------------------------===//
37 // ConvergingVLIWScheduler - Implementation of the standard
38 // MachineSchedStrategy.
39 //===----------------------------------------------------------------------===//
41 class VLIWResourceModel {
42 /// ResourcesModel - Represents VLIW state.
43 /// Not limited to VLIW targets per say, but assumes
44 /// definition of DFA by a target.
45 DFAPacketizer *ResourcesModel;
47 const TargetSchedModel *SchedModel;
49 /// Local packet/bundle model. Purely
50 /// internal to the MI schedulre at the time.
51 std::vector<SUnit*> Packet;
53 /// Total packets created.
54 unsigned TotalPackets;
57 VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
58 : SchedModel(SM), TotalPackets(0) {
59 ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
61 // This hard requirement could be relaxed,
62 // but for now do not let it proceed.
63 assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
65 Packet.resize(SchedModel->getIssueWidth());
67 ResourcesModel->clearResources();
70 ~VLIWResourceModel() {
71 delete ResourcesModel;
74 void resetPacketState() {
79 ResourcesModel->clearResources();
84 ResourcesModel->clearResources();
87 bool isResourceAvailable(SUnit *SU);
88 bool reserveResources(SUnit *SU);
89 unsigned getTotalPackets() const { return TotalPackets; }
92 /// Extend the standard ScheduleDAGMI to provide more context and override the
93 /// top-level schedule() driver.
94 class VLIWMachineScheduler : public ScheduleDAGMILive {
96 VLIWMachineScheduler(MachineSchedContext *C,
97 std::unique_ptr<MachineSchedStrategy> S)
98 : ScheduleDAGMILive(C, std::move(S)) {}
100 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
101 /// time to do some work.
102 void schedule() override;
103 /// Perform platform-specific DAG postprocessing.
104 void postprocessDAG();
107 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
108 /// to balance the schedule.
109 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.
117 // Register pressure values for the best candidate.
118 RegPressureDelta RPDelta;
120 // Best scheduling cost.
123 SchedCandidate(): SU(nullptr), SCost(0) {}
125 /// Represent the type of SchedCandidate found within a single queue.
127 NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
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;
137 ReadyQueue Available;
141 ScheduleHazardRecognizer *HazardRec;
142 VLIWResourceModel *ResourceModel;
147 /// MinReadyCycle - Cycle of the soonest available instruction.
148 unsigned MinReadyCycle;
150 // Remember the greatest min operand latency.
151 unsigned MaxMinLatency;
153 /// Pending queues extend the ready queues with the same ID and the
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) {}
162 ~VLIWSchedBoundary() {
163 delete ResourceModel;
167 void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
173 return Available.getID() == ConvergingVLIWScheduler::TopQID;
176 bool checkHazard(SUnit *SU);
178 void releaseNode(SUnit *SU, unsigned ReadyCycle);
182 void bumpNode(SUnit *SU);
184 void releasePending();
186 void removeReady(SUnit *SU);
188 SUnit *pickOnlyChoice();
191 VLIWMachineScheduler *DAG;
192 const TargetSchedModel *SchedModel;
194 // State of the top and bottom scheduled instruction boundaries.
195 VLIWSchedBoundary Top;
196 VLIWSchedBoundary Bot;
199 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
206 ConvergingVLIWScheduler()
207 : DAG(nullptr), SchedModel(nullptr), Top(TopQID, "TopQ"),
208 Bot(BotQID, "BotQ") {}
210 void initialize(ScheduleDAGMI *dag) override;
212 SUnit *pickNode(bool &IsTopNode) override;
214 void schedNode(SUnit *SU, bool IsTopNode) override;
216 void releaseTopNode(SUnit *SU) override;
218 void releaseBottomNode(SUnit *SU) override;
220 unsigned ReportPackets() {
221 return Top.ResourceModel->getTotalPackets() +
222 Bot.ResourceModel->getTotalPackets();
226 SUnit *pickNodeBidrectional(bool &IsTopNode);
228 int SchedulingCost(ReadyQueue &Q,
229 SUnit *SU, SchedCandidate &Candidate,
230 RegPressureDelta &Delta, bool verbose);
232 CandResult pickNodeFromQueue(ReadyQueue &Q,
233 const RegPressureTracker &RPTracker,
234 SchedCandidate &Candidate);
236 void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
237 PressureChange P = PressureChange());