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