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);
getTotalPackets()60   unsigned getTotalPackets() const { return TotalPackets; }
getPacketInstCount()61   size_t getPacketInstCount() const { return Packet.size(); }
isInPacket(SUnit * SU)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:
VLIWMachineScheduler(MachineSchedContext * C,std::unique_ptr<MachineSchedStrategy> S)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 
getRegClassInfo()80   RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
getBBSize()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.
VLIWSchedBoundaryVLIWSchedBoundary150     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 
initVLIWSchedBoundary158     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       const auto BBSize = DAG->getBBSize();
169       CriticalPathLength = BBSize / SchedModel->getIssueWidth();
170       if (BBSize < 50)
171         // We divide by two as a cheap and simple heuristic to reduce the
172         // critcal path length, which increases the priority of using the graph
173         // height/depth in the scheduler's cost computation.
174         CriticalPathLength >>= 1;
175       else {
176         // For large basic blocks, we prefer a larger critical path length to
177         // decrease the priority of using the graph height/depth.
178         unsigned MaxPath = 0;
179         for (auto &SU : DAG->SUnits)
180           MaxPath = std::max(MaxPath, isTop() ? SU.getHeight() : SU.getDepth());
181         CriticalPathLength = std::max(CriticalPathLength, MaxPath) + 1;
182       }
183     }
184 
isTopVLIWSchedBoundary185     bool isTop() const {
186       return Available.getID() == ConvergingVLIWScheduler::TopQID;
187     }
188 
189     bool checkHazard(SUnit *SU);
190 
191     void releaseNode(SUnit *SU, unsigned ReadyCycle);
192 
193     void bumpCycle();
194 
195     void bumpNode(SUnit *SU);
196 
197     void releasePending();
198 
199     void removeReady(SUnit *SU);
200 
201     SUnit *pickOnlyChoice();
202 
isLatencyBoundVLIWSchedBoundary203     bool isLatencyBound(SUnit *SU) {
204       if (CurrCycle >= CriticalPathLength)
205         return true;
206       unsigned PathLength = isTop() ? SU->getHeight() : SU->getDepth();
207       return CriticalPathLength - CurrCycle <= PathLength;
208     }
209   };
210 
211   VLIWMachineScheduler *DAG = nullptr;
212   const TargetSchedModel *SchedModel = nullptr;
213 
214   // State of the top and bottom scheduled instruction boundaries.
215   VLIWSchedBoundary Top;
216   VLIWSchedBoundary Bot;
217 
218   /// List of pressure sets that have a high pressure level in the region.
219   SmallVector<bool> HighPressureSets;
220 
221 public:
222   /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
223   enum { TopQID = 1, BotQID = 2, LogMaxQID = 2 };
224 
ConvergingVLIWScheduler()225   ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
226   virtual ~ConvergingVLIWScheduler() = default;
227 
228   void initialize(ScheduleDAGMI *dag) override;
229 
230   SUnit *pickNode(bool &IsTopNode) override;
231 
232   void schedNode(SUnit *SU, bool IsTopNode) override;
233 
234   void releaseTopNode(SUnit *SU) override;
235 
236   void releaseBottomNode(SUnit *SU) override;
237 
reportPackets()238   unsigned reportPackets() {
239     return Top.ResourceModel->getTotalPackets() +
240            Bot.ResourceModel->getTotalPackets();
241   }
242 
243 protected:
244   virtual VLIWResourceModel *
245   createVLIWResourceModel(const TargetSubtargetInfo &STI,
246                           const TargetSchedModel *SchedModel) const;
247 
248   SUnit *pickNodeBidrectional(bool &IsTopNode);
249 
250   int pressureChange(const SUnit *SU, bool isBotUp);
251 
252   virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU,
253                              SchedCandidate &Candidate, RegPressureDelta &Delta,
254                              bool verbose);
255 
256   CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone,
257                                const RegPressureTracker &RPTracker,
258                                SchedCandidate &Candidate);
259 #ifndef NDEBUG
260   void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
261                       int Cost, PressureChange P = PressureChange());
262 
263   void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
264                              SchedCandidate &Candidate, ReadyQueue &Q);
265 #endif
266 };
267 
268 } // end namespace llvm
269 
270 #endif // LLVM_CODEGEN_VLIWMACHINESCHEDULER_H
271