LLVM 18.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.
169 if (DAG->getBBSize() < 50)
170 // We divide by two as a cheap and simple heuristic to reduce the
171 // critcal path length, which increases the priority of using the graph
172 // height/depth in the scheduler's cost computation.
173 CriticalPathLength >>= 1;
174 else {
175 // For large basic blocks, we prefer a larger critical path length to
176 // decrease the priority of using the graph height/depth.
177 unsigned MaxPath = 0;
178 for (auto &SU : DAG->SUnits)
179 MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
180 CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
181 }
182 }
183
184 bool isTop() const {
186 }
187
188 bool checkHazard(SUnit *SU);
189
190 void releaseNode(SUnit *SU, unsigned ReadyCycle);
191
192 void bumpCycle();
193
194 void bumpNode(SUnit *SU);
195
196 void releasePending();
197
198 void removeReady(SUnit *SU);
199
201
204 return true;
205 unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
206 return CriticalPathLength - CurrCycle <= PathLength;
207 }
208 };
209
211 const TargetSchedModel *SchedModel = nullptr;
212
213 // State of the top and bottom scheduled instruction boundaries.
216
217 /// List of pressure sets that have a high pressure level in the region.
219
220public:
221 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
222 enum { TopQID = 1, BotQID = 2, LogMaxQID = 2 };
223
224 ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
225 virtual ~ConvergingVLIWScheduler() = default;
226
227 void initialize(ScheduleDAGMI *dag) override;
228
229 SUnit *pickNode(bool &IsTopNode) override;
230
231 void schedNode(SUnit *SU, bool IsTopNode) override;
232
233 void releaseTopNode(SUnit *SU) override;
234
235 void releaseBottomNode(SUnit *SU) override;
236
237 unsigned reportPackets() {
240 }
241
242protected:
243 virtual VLIWResourceModel *
245 const TargetSchedModel *SchedModel) const;
246
247 SUnit *pickNodeBidrectional(bool &IsTopNode);
248
249 int pressureChange(const SUnit *SU, bool isBotUp);
250
251 virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU,
252 SchedCandidate &Candidate, RegPressureDelta &Delta,
253 bool verbose);
254
255 CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,
256 const RegPressureTracker &RPTracker,
257 SchedCandidate &Candidate);
258#ifndef NDEBUG
259 void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
261
262 void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
263 SchedCandidate &Candidate, ReadyQueue &Q);
264#endif
265};
266
267} // end namespace llvm
268
269#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:1200
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:1854
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1884
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.