LLVM  14.0.0git
HexagonMachineScheduler.h
Go to the documentation of this file.
1 //===- HexagonMachineScheduler.h - Custom Hexagon MI scheduler --*- 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 // Custom Hexagon MI scheduler.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
14 #define LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
15 
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/Twine.h"
25 #include <algorithm>
26 #include <cassert>
27 #include <limits>
28 #include <memory>
29 #include <vector>
30 
31 namespace llvm {
32 
33 class SUnit;
34 
36  /// ResourcesModel - Represents VLIW state.
37  /// Not limited to VLIW targets per se, but assumes
38  /// definition of DFA by a target.
39  DFAPacketizer *ResourcesModel;
40 
41  const TargetSchedModel *SchedModel;
42 
43  /// Local packet/bundle model. Purely
44  /// internal to the MI schedulre at the time.
45  std::vector<SUnit *> Packet;
46 
47  /// Total packets created.
48  unsigned TotalPackets = 0;
49 
50 public:
52  : SchedModel(SM) {
53  ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
54 
55  // This hard requirement could be relaxed,
56  // but for now do not let it proceed.
57  assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
58 
59  Packet.resize(SchedModel->getIssueWidth());
60  Packet.clear();
61  ResourcesModel->clearResources();
62  }
63 
65  delete ResourcesModel;
66  }
67 
69  Packet.clear();
70  }
71 
72  void resetDFA() {
73  ResourcesModel->clearResources();
74  }
75 
76  void reset() {
77  Packet.clear();
78  ResourcesModel->clearResources();
79  }
80 
81  bool isResourceAvailable(SUnit *SU, bool IsTop);
82  bool reserveResources(SUnit *SU, bool IsTop);
83  unsigned getTotalPackets() const { return TotalPackets; }
84  bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
85 };
86 
87 /// Extend the standard ScheduleDAGMI to provide more context and override the
88 /// top-level schedule() driver.
90 public:
92  std::unique_ptr<MachineSchedStrategy> S)
93  : ScheduleDAGMILive(C, std::move(S)) {}
94 
95  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
96  /// time to do some work.
97  void schedule() override;
98 
100  int getBBSize() { return BB->size(); }
101 };
102 
103 //===----------------------------------------------------------------------===//
104 // ConvergingVLIWScheduler - Implementation of the standard
105 // MachineSchedStrategy.
106 //===----------------------------------------------------------------------===//
107 
108 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
109 /// to balance the schedule.
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 = nullptr;
116 
117  // Register pressure values for the best candidate.
118  RegPressureDelta RPDelta;
119 
120  // Best scheduling cost.
121  int SCost = 0;
122 
123  SchedCandidate() = default;
124  };
125  /// Represent the type of SchedCandidate found within a single queue.
126  enum CandResult {
127  NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
128  BestCost, Weak};
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 = nullptr;
135  const TargetSchedModel *SchedModel = nullptr;
136 
138  ReadyQueue Pending;
139  bool CheckPending = false;
140 
141  ScheduleHazardRecognizer *HazardRec = nullptr;
142  VLIWResourceModel *ResourceModel = nullptr;
143 
144  unsigned CurrCycle = 0;
145  unsigned IssueCount = 0;
146  unsigned CriticalPathLength = 0;
147 
148  /// MinReadyCycle - Cycle of the soonest available instruction.
149  unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
150 
151  // Remember the greatest min operand latency.
152  unsigned MaxMinLatency = 0;
153 
154  /// Pending queues extend the ready queues with the same ID and the
155  /// PendingFlag set.
156  VLIWSchedBoundary(unsigned ID, const Twine &Name)
157  : Available(ID, Name+".A"),
158  Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {}
159 
160  ~VLIWSchedBoundary() {
161  delete ResourceModel;
162  delete HazardRec;
163  }
164 
165  void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
166  DAG = dag;
167  SchedModel = smodel;
168  CurrCycle = 0;
169  IssueCount = 0;
170  // Initialize the critical path length limit, which used by the scheduling
171  // cost model to determine the value for scheduling an instruction. We use
172  // a slightly different heuristic for small and large functions. For small
173  // functions, it's important to use the height/depth of the instruction.
174  // For large functions, prioritizing by height or depth increases spills.
175  CriticalPathLength = DAG->getBBSize() / SchedModel->getIssueWidth();
176  if (DAG->getBBSize() < 50)
177  // We divide by two as a cheap and simple heuristic to reduce the
178  // critcal path length, which increases the priority of using the graph
179  // height/depth in the scheduler's cost computation.
180  CriticalPathLength >>= 1;
181  else {
182  // For large basic blocks, we prefer a larger critical path length to
183  // decrease the priority of using the graph height/depth.
184  unsigned MaxPath = 0;
185  for (auto &SU : DAG->SUnits)
186  MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
187  CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
188  }
189  }
190 
191  bool isTop() const {
192  return Available.getID() == ConvergingVLIWScheduler::TopQID;
193  }
194 
195  bool checkHazard(SUnit *SU);
196 
197  void releaseNode(SUnit *SU, unsigned ReadyCycle);
198 
199  void bumpCycle();
200 
201  void bumpNode(SUnit *SU);
202 
203  void releasePending();
204 
205  void removeReady(SUnit *SU);
206 
207  SUnit *pickOnlyChoice();
208 
209  bool isLatencyBound(SUnit *SU) {
210  if (CurrCycle >= CriticalPathLength)
211  return true;
212  unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
213  return CriticalPathLength - CurrCycle <= PathLength;
214  }
215  };
216 
217  VLIWMachineScheduler *DAG = nullptr;
218  const TargetSchedModel *SchedModel = nullptr;
219 
220  // State of the top and bottom scheduled instruction boundaries.
221  VLIWSchedBoundary Top;
222  VLIWSchedBoundary Bot;
223 
224  /// List of pressure sets that have a high pressure level in the region.
225  std::vector<bool> HighPressureSets;
226 
227 public:
228  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
229  enum {
230  TopQID = 1,
231  BotQID = 2,
233  };
234 
235  ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
236 
237  void initialize(ScheduleDAGMI *dag) override;
238 
239  SUnit *pickNode(bool &IsTopNode) override;
240 
241  void schedNode(SUnit *SU, bool IsTopNode) override;
242 
243  void releaseTopNode(SUnit *SU) override;
244 
245  void releaseBottomNode(SUnit *SU) override;
246 
247  unsigned reportPackets() {
248  return Top.ResourceModel->getTotalPackets() +
249  Bot.ResourceModel->getTotalPackets();
250  }
251 
252 protected:
253  SUnit *pickNodeBidrectional(bool &IsTopNode);
254 
255  int pressureChange(const SUnit *SU, bool isBotUp);
256 
257  int SchedulingCost(ReadyQueue &Q,
258  SUnit *SU, SchedCandidate &Candidate,
259  RegPressureDelta &Delta, bool verbose);
260 
261  CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,
262  const RegPressureTracker &RPTracker,
263  SchedCandidate &Candidate);
264 #ifndef NDEBUG
265  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
266  int Cost, PressureChange P = PressureChange());
267 
268  void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
269  SchedCandidate &Candidate, ReadyQueue &Q);
270 #endif
271 };
272 
273 } // end namespace llvm
274 
275 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
llvm::ConvergingVLIWScheduler::initialize
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
Definition: HexagonMachineScheduler.cpp:253
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::VLIWMachineScheduler::getRegClassInfo
RegisterClassInfo * getRegClassInfo()
Definition: HexagonMachineScheduler.h:99
llvm::ConvergingVLIWScheduler::pickNode
SUnit * pickNode(bool &IsTopNode) override
Pick the best node to balance the schedule. Implements MachineSchedStrategy.
Definition: HexagonMachineScheduler.cpp:945
llvm::ConvergingVLIWScheduler::pickNodeBidrectional
SUnit * pickNodeBidrectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
Definition: HexagonMachineScheduler.cpp:879
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:92
llvm::ConvergingVLIWScheduler::readyQueueVerboseDump
void readyQueueVerboseDump(const RegPressureTracker &RPTracker, SchedCandidate &Candidate, ReadyQueue &Q)
Definition: HexagonMachineScheduler.cpp:497
llvm::RegPressureTracker
Track the current register pressure at some position in the instruction stream, and remember the high...
Definition: RegisterPressure.h:358
TargetInstrInfo.h
llvm::TargetInstrInfo::CreateTargetScheduleState
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
Definition: TargetInstrInfo.h:1774
llvm::VLIWMachineScheduler
Extend the standard ScheduleDAGMI to provide more context and override the top-level schedule() drive...
Definition: HexagonMachineScheduler.h:89
llvm::SUnit::getDepth
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
llvm::ConvergingVLIWScheduler::ConvergingVLIWScheduler
ConvergingVLIWScheduler()
Definition: HexagonMachineScheduler.h:235
STLExtras.h
RegisterPressure.h
llvm::ConvergingVLIWScheduler::traceCandidate
void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P=PressureChange())
Definition: HexagonMachineScheduler.cpp:484
llvm::ConvergingVLIWScheduler::releaseBottomNode
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
Definition: HexagonMachineScheduler.cpp:304
llvm::MachineSchedStrategy
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
Definition: MachineScheduler.h:201
ScheduleHazardRecognizer.h
llvm::TargetSchedModel::getIssueWidth
unsigned getIssueWidth() const
Maximum number of micro-ops that may be scheduled per cycle.
Definition: TargetSchedule.h:99
AvailabilityState::Available
@ Available
We know the block is fully available. This is a fixpoint.
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
Twine.h
llvm::ConvergingVLIWScheduler::pressureChange
int pressureChange(const SUnit *SU, bool isBotUp)
Check if the instruction changes the register pressure of a register in the high pressure set.
Definition: HexagonMachineScheduler.cpp:553
llvm::DFAPacketizer
Definition: DFAPacketizer.h:49
DFAPacketizer.h
llvm::SUnit::getHeight
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
llvm::ScheduleDAGMILive::RegClassInfo
RegisterClassInfo * RegClassInfo
Definition: MachineScheduler.h:387
llvm::VLIWResourceModel
Definition: HexagonMachineScheduler.h:35
llvm::VLIWMachineScheduler::schedule
void schedule() override
Schedule - This is called back from ScheduleDAGInstrs::Run() when it's time to do some work.
Definition: HexagonMachineScheduler.cpp:191
llvm::VLIWResourceModel::isResourceAvailable
bool isResourceAvailable(SUnit *SU, bool IsTop)
Check if scheduling of this SU is possible in the current packet.
Definition: HexagonMachineScheduler.cpp:97
TargetSchedule.h
llvm::VLIWResourceModel::isInPacket
bool isInPacket(SUnit *SU) const
Definition: HexagonMachineScheduler.h:84
llvm::TargetSchedModel
Provide an instruction scheduling machine model to CodeGen passes.
Definition: TargetSchedule.h:31
llvm::VLIWResourceModel::getTotalPackets
unsigned getTotalPackets() const
Definition: HexagonMachineScheduler.h:83
llvm::ConvergingVLIWScheduler::BotQID
@ BotQID
Definition: HexagonMachineScheduler.h:231
llvm::ConvergingVLIWScheduler::SchedulingCost
int SchedulingCost(ReadyQueue &Q, SUnit *SU, SchedCandidate &Candidate, RegPressureDelta &Delta, bool verbose)
Single point to compute overall scheduling cost.
Definition: HexagonMachineScheduler.cpp:576
llvm::MachineSchedContext
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
Definition: MachineScheduler.h:120
llvm::VLIWMachineScheduler::getBBSize
int getBBSize()
Definition: HexagonMachineScheduler.h:100
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1616
llvm::ConvergingVLIWScheduler
ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics to balance the schedule.
Definition: HexagonMachineScheduler.h:110
llvm::VLIWResourceModel::reserveResources
bool reserveResources(SUnit *SU, bool IsTop)
Keep track of available resources.
Definition: HexagonMachineScheduler.cpp:138
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::VLIWResourceModel::VLIWResourceModel
VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
Definition: HexagonMachineScheduler.h:51
llvm::move
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:1609
llvm::MachineBasicBlock::size
unsigned size() const
Definition: MachineBasicBlock.h:239
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:30
llvm::VLIWResourceModel::~VLIWResourceModel
~VLIWResourceModel()
Definition: HexagonMachineScheduler.h:64
llvm::ScheduleDAGMI
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
Definition: MachineScheduler.h:266
llvm::DFAPacketizer::clearResources
void clearResources()
Definition: DFAPacketizer.h:66
llvm::VLIWResourceModel::resetPacketState
void resetPacketState()
Definition: HexagonMachineScheduler.h:68
TargetSubtargetInfo.h
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::ConvergingVLIWScheduler::TopQID
@ TopQID
Definition: HexagonMachineScheduler.h:230
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:59
llvm::RegPressureDelta
Store the effects of a change in pressure on things that MI scheduler cares about.
Definition: RegisterPressure.h:239
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::ScheduleDAG::SUnits
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
std
Definition: BitVector.h:838
llvm::ConvergingVLIWScheduler::schedNode
void schedNode(SUnit *SU, bool IsTopNode) override
Update the scheduler's state after scheduling a node.
Definition: HexagonMachineScheduler.cpp:994
llvm::VLIWResourceModel::resetDFA
void resetDFA()
Definition: HexagonMachineScheduler.h:72
llvm::PressureChange
Capture a change in pressure for a single pressure set.
Definition: RegisterPressure.h:103
llvm::ConvergingVLIWScheduler::LogMaxQID
@ LogMaxQID
Definition: HexagonMachineScheduler.h:232
llvm::ConvergingVLIWScheduler::reportPackets
unsigned reportPackets()
Definition: HexagonMachineScheduler.h:247
llvm::ScheduleDAGInstrs::BB
MachineBasicBlock * BB
The block in which to insert instructions.
Definition: ScheduleDAGInstrs.h:145
MachineScheduler.h
llvm::ConvergingVLIWScheduler::releaseTopNode
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
Definition: HexagonMachineScheduler.cpp:288
llvm::ConvergingVLIWScheduler::pickNodeFromQueue
CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the top queue.
Definition: HexagonMachineScheduler.cpp:765
llvm::VLIWMachineScheduler::VLIWMachineScheduler
VLIWMachineScheduler(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S)
Definition: HexagonMachineScheduler.h:91
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
llvm::ScheduleDAGMILive
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
Definition: MachineScheduler.h:385
llvm::ReadyQueue
Helpers for implementing custom MachineSchedStrategy classes.
Definition: MachineScheduler.h:531
llvm::ScheduleHazardRecognizer
HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...
Definition: ScheduleHazardRecognizer.h:25
llvm::VLIWResourceModel::reset
void reset()
Definition: HexagonMachineScheduler.h:76
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37