1 | //===- VLIWMachineScheduler.h - VLIW-Focused Scheduling Pass ----*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // // |
9 | //===----------------------------------------------------------------------===// |
10 | |
11 | #ifndef LLVM_CODEGEN_VLIWMACHINESCHEDULER_H |
12 | #define LLVM_CODEGEN_VLIWMACHINESCHEDULER_H |
13 | |
14 | #include "llvm/ADT/SmallVector.h" |
15 | #include "llvm/ADT/Twine.h" |
16 | #include "llvm/CodeGen/MachineScheduler.h" |
17 | #include "llvm/CodeGen/TargetSchedule.h" |
18 | #include <limits> |
19 | #include <memory> |
20 | #include <utility> |
21 | |
22 | namespace llvm { |
23 | |
24 | class DFAPacketizer; |
25 | class RegisterClassInfo; |
26 | class ScheduleHazardRecognizer; |
27 | class SUnit; |
28 | class TargetInstrInfo; |
29 | class TargetSubtargetInfo; |
30 | |
31 | class VLIWResourceModel { |
32 | protected: |
33 | const TargetInstrInfo *TII; |
34 | |
35 | /// ResourcesModel - Represents VLIW state. |
36 | /// Not limited to VLIW targets per se, but assumes definition of resource |
37 | /// model by a target. |
38 | DFAPacketizer *ResourcesModel; |
39 | |
40 | const TargetSchedModel *SchedModel; |
41 | |
42 | /// Local packet/bundle model. Purely |
43 | /// internal to the MI scheduler at the time. |
44 | SmallVector<SUnit *> Packet; |
45 | |
46 | /// Total packets created. |
47 | unsigned TotalPackets = 0; |
48 | |
49 | public: |
50 | VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM); |
51 | VLIWResourceModel &operator=(const VLIWResourceModel &other) = delete; |
52 | VLIWResourceModel(const VLIWResourceModel &other) = delete; |
53 | virtual ~VLIWResourceModel(); |
54 | |
55 | virtual void reset(); |
56 | |
57 | virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu); |
58 | virtual bool isResourceAvailable(SUnit *SU, bool IsTop); |
59 | virtual bool reserveResources(SUnit *SU, bool IsTop); |
60 | unsigned getTotalPackets() const { return TotalPackets; } |
61 | size_t getPacketInstCount() const { return Packet.size(); } |
62 | bool isInPacket(SUnit *SU) const { return is_contained(Range: Packet, Element: SU); } |
63 | |
64 | protected: |
65 | virtual DFAPacketizer *createPacketizer(const TargetSubtargetInfo &STI) const; |
66 | }; |
67 | |
68 | /// Extend the standard ScheduleDAGMILive to provide more context and override |
69 | /// the top-level schedule() driver. |
70 | class VLIWMachineScheduler : public ScheduleDAGMILive { |
71 | public: |
72 | VLIWMachineScheduler(MachineSchedContext *C, |
73 | std::unique_ptr<MachineSchedStrategy> S) |
74 | : ScheduleDAGMILive(C, std::move(S)) {} |
75 | |
76 | /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's |
77 | /// time to do some work. |
78 | void schedule() override; |
79 | |
80 | RegisterClassInfo *getRegClassInfo() { return RegClassInfo; } |
81 | int getBBSize() { return BB->size(); } |
82 | }; |
83 | |
84 | //===----------------------------------------------------------------------===// |
85 | // ConvergingVLIWScheduler - Implementation of a VLIW-aware |
86 | // MachineSchedStrategy. |
87 | //===----------------------------------------------------------------------===// |
88 | |
89 | class ConvergingVLIWScheduler : public MachineSchedStrategy { |
90 | protected: |
91 | /// Store the state used by ConvergingVLIWScheduler heuristics, required |
92 | /// for the lifetime of one invocation of pickNode(). |
93 | struct SchedCandidate { |
94 | // The best SUnit candidate. |
95 | SUnit *SU = nullptr; |
96 | |
97 | // Register pressure values for the best candidate. |
98 | RegPressureDelta RPDelta; |
99 | |
100 | // Best scheduling cost. |
101 | int SCost = 0; |
102 | |
103 | SchedCandidate() = default; |
104 | }; |
105 | /// Represent the type of SchedCandidate found within a single queue. |
106 | enum CandResult { |
107 | NoCand, |
108 | NodeOrder, |
109 | SingleExcess, |
110 | SingleCritical, |
111 | SingleMax, |
112 | MultiPressure, |
113 | BestCost, |
114 | Weak |
115 | }; |
116 | |
117 | // Constants used to denote relative importance of |
118 | // heuristic components for cost computation. |
119 | static constexpr unsigned PriorityOne = 200; |
120 | static constexpr unsigned PriorityTwo = 50; |
121 | static constexpr unsigned PriorityThree = 75; |
122 | static constexpr unsigned ScaleTwo = 10; |
123 | |
124 | /// Each Scheduling boundary is associated with ready queues. It tracks the |
125 | /// current cycle in whichever direction at has moved, and maintains the state |
126 | /// of "hazards" and other interlocks at the current cycle. |
127 | struct VLIWSchedBoundary { |
128 | VLIWMachineScheduler *DAG = nullptr; |
129 | const TargetSchedModel *SchedModel = nullptr; |
130 | |
131 | ReadyQueue Available; |
132 | ReadyQueue Pending; |
133 | bool CheckPending = false; |
134 | |
135 | ScheduleHazardRecognizer *HazardRec = nullptr; |
136 | VLIWResourceModel *ResourceModel = nullptr; |
137 | |
138 | unsigned CurrCycle = 0; |
139 | unsigned IssueCount = 0; |
140 | unsigned CriticalPathLength = 0; |
141 | |
142 | /// MinReadyCycle - Cycle of the soonest available instruction. |
143 | unsigned MinReadyCycle = std::numeric_limits<unsigned>::max(); |
144 | |
145 | // Remember the greatest min operand latency. |
146 | unsigned MaxMinLatency = 0; |
147 | |
148 | /// Pending queues extend the ready queues with the same ID and the |
149 | /// PendingFlag set. |
150 | VLIWSchedBoundary(unsigned ID, const Twine &Name) |
151 | : Available(ID, Name + ".A" ), |
152 | Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name + ".P" ) {} |
153 | |
154 | ~VLIWSchedBoundary(); |
155 | VLIWSchedBoundary &operator=(const VLIWSchedBoundary &other) = delete; |
156 | VLIWSchedBoundary(const VLIWSchedBoundary &other) = delete; |
157 | |
158 | void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) { |
159 | DAG = dag; |
160 | SchedModel = smodel; |
161 | CurrCycle = 0; |
162 | IssueCount = 0; |
163 | // Initialize the critical path length limit, which used by the scheduling |
164 | // cost model to determine the value for scheduling an instruction. We use |
165 | // a slightly different heuristic for small and large functions. For small |
166 | // functions, it's important to use the height/depth of the instruction. |
167 | // For large functions, prioritizing by height or depth increases spills. |
168 | const auto BBSize = DAG->getBBSize(); |
169 | CriticalPathLength = BBSize / SchedModel->getIssueWidth(); |
170 | if (BBSize < 50) |
171 | // We divide by two as a cheap and simple heuristic to reduce the |
172 | // critcal path length, which increases the priority of using the graph |
173 | // height/depth in the scheduler's cost computation. |
174 | CriticalPathLength >>= 1; |
175 | else { |
176 | // For large basic blocks, we prefer a larger critical path length to |
177 | // decrease the priority of using the graph height/depth. |
178 | unsigned MaxPath = 0; |
179 | for (auto &SU : DAG->SUnits) |
180 | MaxPath = std::max(a: MaxPath, b: isTop() ? SU.getHeight() : SU.getDepth()); |
181 | CriticalPathLength = std::max(a: CriticalPathLength, b: MaxPath) + 1; |
182 | } |
183 | } |
184 | |
185 | bool isTop() const { |
186 | return Available.getID() == ConvergingVLIWScheduler::TopQID; |
187 | } |
188 | |
189 | bool checkHazard(SUnit *SU); |
190 | |
191 | void releaseNode(SUnit *SU, unsigned ReadyCycle); |
192 | |
193 | void bumpCycle(); |
194 | |
195 | void bumpNode(SUnit *SU); |
196 | |
197 | void releasePending(); |
198 | |
199 | void removeReady(SUnit *SU); |
200 | |
201 | SUnit *pickOnlyChoice(); |
202 | |
203 | bool isLatencyBound(SUnit *SU) { |
204 | if (CurrCycle >= CriticalPathLength) |
205 | return true; |
206 | unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth(); |
207 | return CriticalPathLength - CurrCycle <= PathLength; |
208 | } |
209 | }; |
210 | |
211 | VLIWMachineScheduler *DAG = nullptr; |
212 | const TargetSchedModel *SchedModel = nullptr; |
213 | |
214 | // State of the top and bottom scheduled instruction boundaries. |
215 | VLIWSchedBoundary Top; |
216 | VLIWSchedBoundary Bot; |
217 | |
218 | /// List of pressure sets that have a high pressure level in the region. |
219 | SmallVector<bool> HighPressureSets; |
220 | |
221 | public: |
222 | /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) |
223 | enum { TopQID = 1, BotQID = 2, LogMaxQID = 2 }; |
224 | |
225 | ConvergingVLIWScheduler() : Top(TopQID, "TopQ" ), Bot(BotQID, "BotQ" ) {} |
226 | virtual ~ConvergingVLIWScheduler() = default; |
227 | |
228 | void initialize(ScheduleDAGMI *dag) override; |
229 | |
230 | SUnit *pickNode(bool &IsTopNode) override; |
231 | |
232 | void schedNode(SUnit *SU, bool IsTopNode) override; |
233 | |
234 | void releaseTopNode(SUnit *SU) override; |
235 | |
236 | void releaseBottomNode(SUnit *SU) override; |
237 | |
238 | unsigned reportPackets() { |
239 | return Top.ResourceModel->getTotalPackets() + |
240 | Bot.ResourceModel->getTotalPackets(); |
241 | } |
242 | |
243 | protected: |
244 | virtual VLIWResourceModel * |
245 | createVLIWResourceModel(const TargetSubtargetInfo &STI, |
246 | const TargetSchedModel *SchedModel) const; |
247 | |
248 | SUnit *pickNodeBidrectional(bool &IsTopNode); |
249 | |
250 | int pressureChange(const SUnit *SU, bool isBotUp); |
251 | |
252 | virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU, |
253 | SchedCandidate &Candidate, RegPressureDelta &Delta, |
254 | bool verbose); |
255 | |
256 | CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, |
257 | const RegPressureTracker &RPTracker, |
258 | SchedCandidate &Candidate); |
259 | #ifndef NDEBUG |
260 | void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, |
261 | int Cost, PressureChange P = PressureChange()); |
262 | |
263 | void readyQueueVerboseDump(const RegPressureTracker &RPTracker, |
264 | SchedCandidate &Candidate, ReadyQueue &Q); |
265 | #endif |
266 | }; |
267 | |
268 | } // end namespace llvm |
269 | |
270 | #endif // LLVM_CODEGEN_VLIWMACHINESCHEDULER_H |
271 | |