LLVM 19.0.0git
VLIWMachineScheduler.h
Go to the documentation of this file.
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
15#include "llvm/ADT/Twine.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
32protected:
34
35 /// ResourcesModel - Represents VLIW state.
36 /// Not limited to VLIW targets per se, but assumes definition of resource
37 /// model by a target.
39
41
42 /// Local packet/bundle model. Purely
43 /// internal to the MI scheduler at the time.
45
46 /// Total packets created.
47 unsigned TotalPackets = 0;
48
49public:
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(Packet, 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.
71public:
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
81 int getBBSize() { return BB->size(); }
82};
83
84//===----------------------------------------------------------------------===//
85// ConvergingVLIWScheduler - Implementation of a VLIW-aware
86// MachineSchedStrategy.
87//===----------------------------------------------------------------------===//
88
90protected:
91 /// Store the state used by ConvergingVLIWScheduler heuristics, required
92 /// for the lifetime of one invocation of pickNode().
94 // The best SUnit candidate.
95 SUnit *SU = nullptr;
96
97 // Register pressure values for the best candidate.
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.
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.
129 const TargetSchedModel *SchedModel = nullptr;
130
133 bool CheckPending = false;
134
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"),
153
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();
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(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
181 CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
182 }
183 }
184
185 bool isTop() const {
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
202
205 return true;
206 unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
207 return CriticalPathLength - CurrCycle <= PathLength;
208 }
209 };
210
212 const TargetSchedModel *SchedModel = nullptr;
213
214 // State of the top and bottom scheduled instruction boundaries.
217
218 /// List of pressure sets that have a high pressure level in the region.
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() {
241 }
242
243protected:
244 virtual VLIWResourceModel *
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,
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
std::string Name
#define P(N)
This file defines the SmallVector class.
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
static constexpr unsigned PriorityOne
SUnit * pickNode(bool &IsTopNode) override
Pick the best node to balance the schedule. Implements MachineSchedStrategy.
virtual VLIWResourceModel * createVLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SchedModel) const
int pressureChange(const SUnit *SU, bool isBotUp)
Check if the instruction changes the register pressure of a register in the high pressure set.
SmallVector< bool > HighPressureSets
List of pressure sets that have a high pressure level in the region.
static constexpr unsigned ScaleTwo
virtual ~ConvergingVLIWScheduler()=default
CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the top queue.
void schedNode(SUnit *SU, bool IsTopNode) override
Update the scheduler's state after scheduling a node.
void readyQueueVerboseDump(const RegPressureTracker &RPTracker, SchedCandidate &Candidate, ReadyQueue &Q)
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
SUnit * pickNodeBidrectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
static constexpr unsigned PriorityTwo
static constexpr unsigned PriorityThree
const TargetSchedModel * SchedModel
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU, SchedCandidate &Candidate, RegPressureDelta &Delta, bool verbose)
Single point to compute overall scheduling cost.
void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P=PressureChange())
CandResult
Represent the type of SchedCandidate found within a single queue.
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
Capture a change in pressure for a single pressure set.
Helpers for implementing custom MachineSchedStrategy classes.
unsigned getID() const
Track the current register pressure at some position in the instruction stream, and remember the high...
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
Definition: ScheduleDAG.h:406
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:398
MachineBasicBlock * BB
The block in which to insert instructions.
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
RegisterClassInfo * RegClassInfo
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:561
HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
TargetInstrInfo - Interface to description of machine instruction set.
Provide an instruction scheduling machine model to CodeGen passes.
unsigned getIssueWidth() const
Maximum number of micro-ops that may be scheduled per cycle.
TargetSubtargetInfo - Generic base class for all target subtargets.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
Extend the standard ScheduleDAGMILive to provide more context and override the top-level schedule() d...
VLIWMachineScheduler(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S)
RegisterClassInfo * getRegClassInfo()
void schedule() override
Schedule - This is called back from ScheduleDAGInstrs::Run() when it's time to do some work.
unsigned TotalPackets
Total packets created.
virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu)
Return true if there is a dependence between SUd and SUu.
virtual DFAPacketizer * createPacketizer(const TargetSubtargetInfo &STI) const
virtual bool reserveResources(SUnit *SU, bool IsTop)
Keep track of available resources.
VLIWResourceModel & operator=(const VLIWResourceModel &other)=delete
bool isInPacket(SUnit *SU) const
DFAPacketizer * ResourcesModel
ResourcesModel - Represents VLIW state.
SmallVector< SUnit * > Packet
Local packet/bundle model.
const TargetSchedModel * SchedModel
VLIWResourceModel(const VLIWResourceModel &other)=delete
unsigned getTotalPackets() const
virtual bool isResourceAvailable(SUnit *SU, bool IsTop)
Check if scheduling of this SU is possible in the current packet.
const TargetInstrInfo * TII
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1858
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1888
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
Store the state used by ConvergingVLIWScheduler heuristics, required for the lifetime of one invocati...
Each Scheduling boundary is associated with ready queues.
VLIWSchedBoundary(unsigned ID, const Twine &Name)
Pending queues extend the ready queues with the same ID and the PendingFlag set.
void releaseNode(SUnit *SU, unsigned ReadyCycle)
void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
VLIWSchedBoundary & operator=(const VLIWSchedBoundary &other)=delete
void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
unsigned MinReadyCycle
MinReadyCycle - Cycle of the soonest available instruction.
void releasePending()
Release pending ready nodes in to the available queue.
SUnit * pickOnlyChoice()
If this queue only has one ready candidate, return it.
void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel)
void bumpCycle()
Move the boundary of scheduled code by one cycle.
bool checkHazard(SUnit *SU)
Does this SU have a hazard within the current instruction group.
VLIWSchedBoundary(const VLIWSchedBoundary &other)=delete
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
Store the effects of a change in pressure on things that MI scheduler cares about.