1 //===-- HexagonMachineScheduler.h - Custom Hexagon MI scheduler.      ----===//
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/PriorityQueue.h"
18 #include "llvm/Analysis/AliasAnalysis.h"
19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
20 #include "llvm/CodeGen/MachineScheduler.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/CodeGen/RegisterClassInfo.h"
23 #include "llvm/CodeGen/RegisterPressure.h"
24 #include "llvm/CodeGen/ResourcePriorityQueue.h"
25 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
26 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/ErrorHandling.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include "llvm/Target/TargetInstrInfo.h"
32 
33 using namespace llvm;
34 
35 namespace llvm {
36 //===----------------------------------------------------------------------===//
37 // ConvergingVLIWScheduler - Implementation of the standard
38 // MachineSchedStrategy.
39 //===----------------------------------------------------------------------===//
40 
41 class VLIWResourceModel {
42   /// ResourcesModel - Represents VLIW state.
43   /// Not limited to VLIW targets per say, but assumes
44   /// definition of DFA by a target.
45   DFAPacketizer *ResourcesModel;
46 
47   const TargetSchedModel *SchedModel;
48 
49   /// Local packet/bundle model. Purely
50   /// internal to the MI schedulre at the time.
51   std::vector<SUnit*> Packet;
52 
53   /// Total packets created.
54   unsigned TotalPackets;
55 
56 public:
VLIWResourceModel(const TargetSubtargetInfo & STI,const TargetSchedModel * SM)57   VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
58       : SchedModel(SM), TotalPackets(0) {
59   ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
60 
61     // This hard requirement could be relaxed,
62     // but for now do not let it proceed.
63     assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
64 
65     Packet.resize(SchedModel->getIssueWidth());
66     Packet.clear();
67     ResourcesModel->clearResources();
68   }
69 
~VLIWResourceModel()70   ~VLIWResourceModel() {
71     delete ResourcesModel;
72   }
73 
resetPacketState()74   void resetPacketState() {
75     Packet.clear();
76   }
77 
resetDFA()78   void resetDFA() {
79     ResourcesModel->clearResources();
80   }
81 
reset()82   void reset() {
83     Packet.clear();
84     ResourcesModel->clearResources();
85   }
86 
87   bool isResourceAvailable(SUnit *SU);
88   bool reserveResources(SUnit *SU);
getTotalPackets()89   unsigned getTotalPackets() const { return TotalPackets; }
90 };
91 
92 /// Extend the standard ScheduleDAGMI to provide more context and override the
93 /// top-level schedule() driver.
94 class VLIWMachineScheduler : public ScheduleDAGMILive {
95 public:
VLIWMachineScheduler(MachineSchedContext * C,std::unique_ptr<MachineSchedStrategy> S)96   VLIWMachineScheduler(MachineSchedContext *C,
97                        std::unique_ptr<MachineSchedStrategy> S)
98       : ScheduleDAGMILive(C, std::move(S)) {}
99 
100   /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
101   /// time to do some work.
102   void schedule() override;
103   /// Perform platform-specific DAG postprocessing.
104   void postprocessDAG();
105 };
106 
107 /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
108 /// to balance the schedule.
109 class ConvergingVLIWScheduler : public MachineSchedStrategy {
110 
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;
116 
117     // Register pressure values for the best candidate.
118     RegPressureDelta RPDelta;
119 
120     // Best scheduling cost.
121     int SCost;
122 
SchedCandidateSchedCandidate123     SchedCandidate(): SU(nullptr), SCost(0) {}
124   };
125   /// Represent the type of SchedCandidate found within a single queue.
126   enum CandResult {
127     NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
128     BestCost};
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;
135     const TargetSchedModel *SchedModel;
136 
137     ReadyQueue Available;
138     ReadyQueue Pending;
139     bool CheckPending;
140 
141     ScheduleHazardRecognizer *HazardRec;
142     VLIWResourceModel *ResourceModel;
143 
144     unsigned CurrCycle;
145     unsigned IssueCount;
146 
147     /// MinReadyCycle - Cycle of the soonest available instruction.
148     unsigned MinReadyCycle;
149 
150     // Remember the greatest min operand latency.
151     unsigned MaxMinLatency;
152 
153     /// Pending queues extend the ready queues with the same ID and the
154     /// PendingFlag set.
VLIWSchedBoundaryVLIWSchedBoundary155     VLIWSchedBoundary(unsigned ID, const Twine &Name):
156       DAG(nullptr), SchedModel(nullptr), Available(ID, Name+".A"),
157       Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
158       CheckPending(false), HazardRec(nullptr), ResourceModel(nullptr),
159       CurrCycle(0), IssueCount(0),
160       MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
161 
~VLIWSchedBoundaryVLIWSchedBoundary162     ~VLIWSchedBoundary() {
163       delete ResourceModel;
164       delete HazardRec;
165     }
166 
initVLIWSchedBoundary167     void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
168       DAG = dag;
169       SchedModel = smodel;
170     }
171 
isTopVLIWSchedBoundary172     bool isTop() const {
173       return Available.getID() == ConvergingVLIWScheduler::TopQID;
174     }
175 
176     bool checkHazard(SUnit *SU);
177 
178     void releaseNode(SUnit *SU, unsigned ReadyCycle);
179 
180     void bumpCycle();
181 
182     void bumpNode(SUnit *SU);
183 
184     void releasePending();
185 
186     void removeReady(SUnit *SU);
187 
188     SUnit *pickOnlyChoice();
189   };
190 
191   VLIWMachineScheduler *DAG;
192   const TargetSchedModel *SchedModel;
193 
194   // State of the top and bottom scheduled instruction boundaries.
195   VLIWSchedBoundary Top;
196   VLIWSchedBoundary Bot;
197 
198 public:
199   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
200   enum {
201     TopQID = 1,
202     BotQID = 2,
203     LogMaxQID = 2
204   };
205 
ConvergingVLIWScheduler()206   ConvergingVLIWScheduler()
207     : DAG(nullptr), SchedModel(nullptr), Top(TopQID, "TopQ"),
208       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 
ReportPackets()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                       PressureChange P = PressureChange());
238 #endif
239 };
240 
241 } // namespace
242 
243 
244 #endif
245