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
22namespace llvm {
23
24class DFAPacketizer;
25class RegisterClassInfo;
26class ScheduleHazardRecognizer;
27class SUnit;
28class TargetInstrInfo;
29class TargetSubtargetInfo;
30
31class VLIWResourceModel {
32protected:
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
49public:
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
64protected:
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.
70class VLIWMachineScheduler : public ScheduleDAGMILive {
71public:
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
89class ConvergingVLIWScheduler : public MachineSchedStrategy {
90protected:
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
221public:
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
243protected:
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