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"
19 #include "llvm/CodeGen/DFAPacketizer.h"
20 #include "llvm/CodeGen/MachineScheduler.h"
21 #include "llvm/CodeGen/RegisterPressure.h"
22 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
23 #include "llvm/CodeGen/TargetInstrInfo.h"
24 #include "llvm/CodeGen/TargetSchedule.h"
25 #include "llvm/CodeGen/TargetSubtargetInfo.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 
36 class VLIWResourceModel {
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:
VLIWResourceModel(const TargetSubtargetInfo & STI,const TargetSchedModel * SM)52   VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
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 
~VLIWResourceModel()65   ~VLIWResourceModel() {
66     delete ResourcesModel;
67   }
68 
resetPacketState()69   void resetPacketState() {
70     Packet.clear();
71   }
72 
resetDFA()73   void resetDFA() {
74     ResourcesModel->clearResources();
75   }
76 
reset()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);
getTotalPackets()84   unsigned getTotalPackets() const { return TotalPackets; }
isInPacket(SUnit * SU)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.
90 class VLIWMachineScheduler : public ScheduleDAGMILive {
91 public:
VLIWMachineScheduler(MachineSchedContext * C,std::unique_ptr<MachineSchedStrategy> S)92   VLIWMachineScheduler(MachineSchedContext *C,
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 
getRegClassInfo()100   RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
getBBSize()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.
111 class ConvergingVLIWScheduler : public MachineSchedStrategy {
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.
VLIWSchedBoundaryVLIWSchedBoundary157     VLIWSchedBoundary(unsigned ID, const Twine &Name)
158         : Available(ID, Name+".A"),
159           Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {}
160 
~VLIWSchedBoundaryVLIWSchedBoundary161     ~VLIWSchedBoundary() {
162       delete ResourceModel;
163       delete HazardRec;
164     }
165 
initVLIWSchedBoundary166     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 
isTopVLIWSchedBoundary192     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 
isLatencyBoundVLIWSchedBoundary210     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 
ConvergingVLIWScheduler()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 
reportPackets()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
277