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