LLVM  6.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:
52  /// Save the last formed packet.
53  std::vector<SUnit *> OldPacket;
54 
56  : SchedModel(SM) {
57  ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
58 
59  // This hard requirement could be relaxed,
60  // but for now do not let it proceed.
61  assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
62 
63  Packet.resize(SchedModel->getIssueWidth());
64  Packet.clear();
65  OldPacket.resize(SchedModel->getIssueWidth());
66  OldPacket.clear();
67  ResourcesModel->clearResources();
68  }
69 
71  delete ResourcesModel;
72  }
73 
75  Packet.clear();
76  }
77 
78  void resetDFA() {
79  ResourcesModel->clearResources();
80  }
81 
82  void reset() {
83  Packet.clear();
84  ResourcesModel->clearResources();
85  }
86 
87  bool isResourceAvailable(SUnit *SU);
88  bool reserveResources(SUnit *SU);
89  void savePacket();
90  unsigned getTotalPackets() const { return TotalPackets; }
91  bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
92 };
93 
94 /// Extend the standard ScheduleDAGMI to provide more context and override the
95 /// top-level schedule() driver.
97 public:
99  std::unique_ptr<MachineSchedStrategy> S)
100  : ScheduleDAGMILive(C, std::move(S)) {}
101 
102  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
103  /// time to do some work.
104  void schedule() override;
105 };
106 
107 //===----------------------------------------------------------------------===//
108 // ConvergingVLIWScheduler - Implementation of the standard
109 // MachineSchedStrategy.
110 //===----------------------------------------------------------------------===//
111 
112 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
113 /// to balance the schedule.
115  /// Store the state used by ConvergingVLIWScheduler heuristics, required
116  /// for the lifetime of one invocation of pickNode().
117  struct SchedCandidate {
118  // The best SUnit candidate.
119  SUnit *SU = nullptr;
120 
121  // Register pressure values for the best candidate.
122  RegPressureDelta RPDelta;
123 
124  // Best scheduling cost.
125  int SCost = 0;
126 
127  SchedCandidate() = default;
128  };
129  /// Represent the type of SchedCandidate found within a single queue.
130  enum CandResult {
131  NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
132  BestCost};
133 
134  /// Each Scheduling boundary is associated with ready queues. It tracks the
135  /// current cycle in whichever direction at has moved, and maintains the state
136  /// of "hazards" and other interlocks at the current cycle.
137  struct VLIWSchedBoundary {
138  VLIWMachineScheduler *DAG = nullptr;
139  const TargetSchedModel *SchedModel = nullptr;
140 
141  ReadyQueue Available;
142  ReadyQueue Pending;
143  bool CheckPending = false;
144 
145  ScheduleHazardRecognizer *HazardRec = nullptr;
146  VLIWResourceModel *ResourceModel = nullptr;
147 
148  unsigned CurrCycle = 0;
149  unsigned IssueCount = 0;
150 
151  /// MinReadyCycle - Cycle of the soonest available instruction.
152  unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
153 
154  // Remember the greatest min operand latency.
155  unsigned MaxMinLatency = 0;
156 
157  /// Pending queues extend the ready queues with the same ID and the
158  /// PendingFlag set.
159  VLIWSchedBoundary(unsigned ID, const Twine &Name)
160  : Available(ID, Name+".A"),
161  Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {}
162 
163  ~VLIWSchedBoundary() {
164  delete ResourceModel;
165  delete HazardRec;
166  }
167 
168  void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
169  DAG = dag;
170  SchedModel = smodel;
171  IssueCount = 0;
172  }
173 
174  bool isTop() const {
175  return Available.getID() == ConvergingVLIWScheduler::TopQID;
176  }
177 
178  bool checkHazard(SUnit *SU);
179 
180  void releaseNode(SUnit *SU, unsigned ReadyCycle);
181 
182  void bumpCycle();
183 
184  void bumpNode(SUnit *SU);
185 
186  void releasePending();
187 
188  void removeReady(SUnit *SU);
189 
190  SUnit *pickOnlyChoice();
191  };
192 
193  VLIWMachineScheduler *DAG = nullptr;
194  const TargetSchedModel *SchedModel = nullptr;
195 
196  // State of the top and bottom scheduled instruction boundaries.
197  VLIWSchedBoundary Top;
198  VLIWSchedBoundary Bot;
199 
200 public:
201  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
202  enum {
203  TopQID = 1,
204  BotQID = 2,
205  LogMaxQID = 2
206  };
207 
208  ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
209 
210  void initialize(ScheduleDAGMI *dag) override;
211 
212  SUnit *pickNode(bool &IsTopNode) override;
213 
214  void schedNode(SUnit *SU, bool IsTopNode) override;
215 
216  void releaseTopNode(SUnit *SU) override;
217 
218  void releaseBottomNode(SUnit *SU) override;
219 
220  unsigned ReportPackets() {
221  return Top.ResourceModel->getTotalPackets() +
222  Bot.ResourceModel->getTotalPackets();
223  }
224 
225 protected:
226  SUnit *pickNodeBidrectional(bool &IsTopNode);
227 
228  int SchedulingCost(ReadyQueue &Q,
229  SUnit *SU, SchedCandidate &Candidate,
230  RegPressureDelta &Delta, bool verbose);
231 
232  CandResult pickNodeFromQueue(ReadyQueue &Q,
233  const RegPressureTracker &RPTracker,
234  SchedCandidate &Candidate);
235 #ifndef NDEBUG
236  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
237  int Cost, PressureChange P = PressureChange());
238 
239  void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
240  SchedCandidate &Candidate, ReadyQueue &Q);
241 #endif
242 };
243 
244 } // end namespace llvm
245 
246 #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...
std::vector< SUnit * > OldPacket
Save the last formed packet.
void savePacket()
Save the last formed packet.
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:920
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)
bool isInPacket(SUnit *SU) const
virtual const TargetInstrInfo * getInstrInfo() const
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
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 isResourceAvailable(SUnit *SU)
Check if scheduling of this SU is possible in the current packet.
ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics to balance the schedule...
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
initialize - Initialize the set of available library functions based on the specified target triple...
TargetSubtargetInfo - Generic base class for all target subtargets.
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.
bool reserveResources(SUnit *SU)
Keep track of available resources.
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.
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:867