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