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
22namespace llvm {
23
24class DFAPacketizer;
25class RegisterClassInfo;
26class ScheduleHazardRecognizer;
27class SUnit;
28class TargetInstrInfo;
29class TargetSubtargetInfo;
30
31class VLIWResourceModel {
32protected:
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
49public:
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);
59  unsigned getTotalPackets() const { return TotalPackets; }
60  size_t getPacketInstCount() const { return Packet.size(); }
61  bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
62
63protected:
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.
69class VLIWMachineScheduler : public ScheduleDAGMILive {
70public:
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
79  RegisterClassInfo *getRegClassInfo() { return RegClassInfo; }
80  int getBBSize() { return BB->size(); }
81};
82
83//===----------------------------------------------------------------------===//
84// ConvergingVLIWScheduler - Implementation of a VLIW-aware
85// MachineSchedStrategy.
86//===----------------------------------------------------------------------===//
87
88class ConvergingVLIWScheduler : public MachineSchedStrategy {
89protected:
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.
149    VLIWSchedBoundary(unsigned ID, const Twine &Name)
150        : Available(ID, Name + ".A"),
151          Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name + ".P") {}
152
153    ~VLIWSchedBoundary();
154
155    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
181    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
199    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
217public:
218  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
219  enum { TopQID = 1, BotQID = 2, LogMaxQID = 2 };
220
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
234  unsigned reportPackets() {
235    return Top.ResourceModel->getTotalPackets() +
236           Bot.ResourceModel->getTotalPackets();
237  }
238
239protected:
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
264ScheduleDAGMILive *createVLIWSched(MachineSchedContext *C);
265
266} // end namespace llvm
267
268#endif // LLVM_CODEGEN_VLIWMACHINESCHEDULER_H
269