LLVM  7.0.0svn
HexagonMachineScheduler.h
Go to the documentation of this file.
1 //===- HexagonMachineScheduler.h - Custom Hexagon MI scheduler --*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Custom Hexagon MI scheduler.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
15 #define LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
16 
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/Twine.h"
26 #include <algorithm>
27 #include <cassert>
28 #include <limits>
29 #include <memory>
30 #include <vector>
31 
32 namespace llvm {
33 
34 class SUnit;
35 
37  /// ResourcesModel - Represents VLIW state.
38  /// Not limited to VLIW targets per se, but assumes
39  /// definition of DFA by a target.
40  DFAPacketizer *ResourcesModel;
41 
42  const TargetSchedModel *SchedModel;
43 
44  /// Local packet/bundle model. Purely
45  /// internal to the MI schedulre at the time.
46  std::vector<SUnit *> Packet;
47 
48  /// Total packets created.
49  unsigned TotalPackets = 0;
50 
51 public:
53  : SchedModel(SM) {
54  ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
55 
56  // This hard requirement could be relaxed,
57  // but for now do not let it proceed.
58  assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
59 
60  Packet.resize(SchedModel->getIssueWidth());
61  Packet.clear();
62  ResourcesModel->clearResources();
63  }
64 
66  delete ResourcesModel;
67  }
68 
70  Packet.clear();
71  }
72 
73  void resetDFA() {
74  ResourcesModel->clearResources();
75  }
76 
77  void reset() {
78  Packet.clear();
79  ResourcesModel->clearResources();
80  }
81 
82  bool isResourceAvailable(SUnit *SU, bool IsTop);
83  bool reserveResources(SUnit *SU, bool IsTop);
84  unsigned getTotalPackets() const { return TotalPackets; }
85  bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
86 };
87 
88 /// Extend the standard ScheduleDAGMI to provide more context and override the
89 /// top-level schedule() driver.
91 public:
93  std::unique_ptr<MachineSchedStrategy> S)
94  : ScheduleDAGMILive(C, std::move(S)) {}
95 
96  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
97  /// time to do some work.
98  void schedule() override;
99 
100  RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
101  int getBBSize() { return BB->size(); }
102 };
103 
104 //===----------------------------------------------------------------------===//
105 // ConvergingVLIWScheduler - Implementation of the standard
106 // MachineSchedStrategy.
107 //===----------------------------------------------------------------------===//
108 
109 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
110 /// to balance the schedule.
112  /// Store the state used by ConvergingVLIWScheduler heuristics, required
113  /// for the lifetime of one invocation of pickNode().
114  struct SchedCandidate {
115  // The best SUnit candidate.
116  SUnit *SU = nullptr;
117 
118  // Register pressure values for the best candidate.
119  RegPressureDelta RPDelta;
120 
121  // Best scheduling cost.
122  int SCost = 0;
123 
124  SchedCandidate() = default;
125  };
126  /// Represent the type of SchedCandidate found within a single queue.
127  enum CandResult {
128  NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
129  BestCost, Weak};
130 
131  /// Each Scheduling boundary is associated with ready queues. It tracks the
132  /// current cycle in whichever direction at has moved, and maintains the state
133  /// of "hazards" and other interlocks at the current cycle.
134  struct VLIWSchedBoundary {
135  VLIWMachineScheduler *DAG = nullptr;
136  const TargetSchedModel *SchedModel = nullptr;
137 
138  ReadyQueue Available;
139  ReadyQueue Pending;
140  bool CheckPending = false;
141 
142  ScheduleHazardRecognizer *HazardRec = nullptr;
143  VLIWResourceModel *ResourceModel = nullptr;
144 
145  unsigned CurrCycle = 0;
146  unsigned IssueCount = 0;
147  unsigned CriticalPathLength = 0;
148 
149  /// MinReadyCycle - Cycle of the soonest available instruction.
150  unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
151 
152  // Remember the greatest min operand latency.
153  unsigned MaxMinLatency = 0;
154 
155  /// Pending queues extend the ready queues with the same ID and the
156  /// PendingFlag set.
157  VLIWSchedBoundary(unsigned ID, const Twine &Name)
158  : Available(ID, Name+".A"),
159  Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {}
160 
161  ~VLIWSchedBoundary() {
162  delete ResourceModel;
163  delete HazardRec;
164  }
165 
166  void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
167  DAG = dag;
168  SchedModel = smodel;
169  CurrCycle = 0;
170  IssueCount = 0;
171  // Initialize the critical path length limit, which used by the scheduling
172  // cost model to determine the value for scheduling an instruction. We use
173  // a slightly different heuristic for small and large functions. For small
174  // functions, it's important to use the height/depth of the instruction.
175  // For large functions, prioritizing by height or depth increases spills.
176  CriticalPathLength = DAG->getBBSize() / SchedModel->getIssueWidth();
177  if (DAG->getBBSize() < 50)
178  // We divide by two as a cheap and simple heuristic to reduce the
179  // critcal path length, which increases the priority of using the graph
180  // height/depth in the scheduler's cost computation.
181  CriticalPathLength >>= 1;
182  else {
183  // For large basic blocks, we prefer a larger critical path length to
184  // decrease the priority of using the graph height/depth.
185  unsigned MaxPath = 0;
186  for (auto &SU : DAG->SUnits)
187  MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
188  CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
189  }
190  }
191 
192  bool isTop() const {
193  return Available.getID() == ConvergingVLIWScheduler::TopQID;
194  }
195 
196  bool checkHazard(SUnit *SU);
197 
198  void releaseNode(SUnit *SU, unsigned ReadyCycle);
199 
200  void bumpCycle();
201 
202  void bumpNode(SUnit *SU);
203 
204  void releasePending();
205 
206  void removeReady(SUnit *SU);
207 
208  SUnit *pickOnlyChoice();
209 
210  bool isLatencyBound(SUnit *SU) {
211  if (CurrCycle >= CriticalPathLength)
212  return true;
213  unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
214  return CriticalPathLength - CurrCycle <= PathLength;
215  }
216  };
217 
218  VLIWMachineScheduler *DAG = nullptr;
219  const TargetSchedModel *SchedModel = nullptr;
220 
221  // State of the top and bottom scheduled instruction boundaries.
222  VLIWSchedBoundary Top;
223  VLIWSchedBoundary Bot;
224 
225  /// List of pressure sets that have a high pressure level in the region.
226  std::vector<bool> HighPressureSets;
227 
228 public:
229  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
230  enum {
231  TopQID = 1,
232  BotQID = 2,
233  LogMaxQID = 2
234  };
235 
236  ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
237 
238  void initialize(ScheduleDAGMI *dag) override;
239 
240  SUnit *pickNode(bool &IsTopNode) override;
241 
242  void schedNode(SUnit *SU, bool IsTopNode) override;
243 
244  void releaseTopNode(SUnit *SU) override;
245 
246  void releaseBottomNode(SUnit *SU) override;
247 
248  unsigned reportPackets() {
249  return Top.ResourceModel->getTotalPackets() +
250  Bot.ResourceModel->getTotalPackets();
251  }
252 
253 protected:
254  SUnit *pickNodeBidrectional(bool &IsTopNode);
255 
256  int pressureChange(const SUnit *SU, bool isBotUp);
257 
258  int SchedulingCost(ReadyQueue &Q,
259  SUnit *SU, SchedCandidate &Candidate,
260  RegPressureDelta &Delta, bool verbose);
261 
262  CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,
263  const RegPressureTracker &RPTracker,
264  SchedCandidate &Candidate);
265 #ifndef NDEBUG
266  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
267  int Cost, PressureChange P = PressureChange());
268 
269  void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
270  SchedCandidate &Candidate, ReadyQueue &Q);
271 #endif
272 };
273 
274 } // end namespace llvm
275 
276 #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)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Extend the standard ScheduleDAGMI to provide more context and override the top-level schedule() drive...
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:403
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:921
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
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:410
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:411
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:572
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:247
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:967