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 HEXAGONASMPRINTER_H
15 #define HEXAGONASMPRINTER_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 = 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
~VLIWResourceModel()70 ~VLIWResourceModel() {
71 delete ResourcesModel;
72 }
73
resetPacketState()74 void resetPacketState() {
75 Packet.clear();
76 }
77
resetDFA()78 void resetDFA() {
79 ResourcesModel->clearResources();
80 }
81
reset()82 void reset() {
83 Packet.clear();
84 ResourcesModel->clearResources();
85 }
86
87 bool isResourceAvailable(SUnit *SU);
88 bool reserveResources(SUnit *SU);
getTotalPackets()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.
94 class VLIWMachineScheduler : public ScheduleDAGMILive {
95 public:
VLIWMachineScheduler(MachineSchedContext * C,std::unique_ptr<MachineSchedStrategy> S)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.
109 class 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
SchedCandidateSchedCandidate123 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.
VLIWSchedBoundaryVLIWSchedBoundary155 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
~VLIWSchedBoundaryVLIWSchedBoundary162 ~VLIWSchedBoundary() {
163 delete ResourceModel;
164 delete HazardRec;
165 }
166
initVLIWSchedBoundary167 void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
168 DAG = dag;
169 SchedModel = smodel;
170 }
171
isTopVLIWSchedBoundary172 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
198 public:
199 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
200 enum {
201 TopQID = 1,
202 BotQID = 2,
203 LogMaxQID = 2
204 };
205
ConvergingVLIWScheduler()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
ReportPackets()220 unsigned ReportPackets() {
221 return Top.ResourceModel->getTotalPackets() +
222 Bot.ResourceModel->getTotalPackets();
223 }
224
225 protected:
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