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