LLVM  10.0.0svn
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 
99  RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
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 
137  ReadyQueue Available;
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,
232  LogMaxQID = 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
uint64_t CallInst * C
VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Extend the standard ScheduleDAGMI to provide more context and override the top-level schedule() drive...
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
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
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
unsigned getID() const
Definition: BitVector.h:937
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
Provide an instruction scheduling machine model to CodeGen passes.
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
VLIWMachineScheduler(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S)
RegisterClassInfo * getRegClassInfo()
bool isInPacket(SUnit *SU) const
virtual const TargetInstrInfo * getInstrInfo() const
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
Helpers for implementing custom MachineSchedStrategy classes.
HazardRecognizer - This determines whether or not an instruction can be issued this cycle...
Track the current register pressure at some position in the instruction stream, and remember the high...
bool reserveResources(SUnit *SU, bool IsTop)
Keep track of available resources.
ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics to balance the schedule...
bool isResourceAvailable(SUnit *SU, bool IsTop)
Check if scheduling of this SU is possible in the current packet.
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
TargetSubtargetInfo - Generic base class for all target subtargets.
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
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
Capture a change in pressure for a single pressure set.
Store the effects of a change in pressure on things that MI scheduler cares about.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getIssueWidth() const
Maximum number of micro-ops that may be scheduled per cycle.
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
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:1251