1//===-- HexagonMachineScheduler.h - Custom Hexagon MI scheduler.      ----===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Custom Hexagon MI scheduler.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
15#define LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
16
17#include "llvm/ADT/PriorityQueue.h"
18#include "llvm/Analysis/AliasAnalysis.h"
19#include "llvm/CodeGen/LiveIntervalAnalysis.h"
20#include "llvm/CodeGen/MachineScheduler.h"
21#include "llvm/CodeGen/Passes.h"
22#include "llvm/CodeGen/RegisterClassInfo.h"
23#include "llvm/CodeGen/RegisterPressure.h"
24#include "llvm/CodeGen/ResourcePriorityQueue.h"
25#include "llvm/CodeGen/ScheduleDAGInstrs.h"
26#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/raw_ostream.h"
31#include "llvm/Target/TargetInstrInfo.h"
32
33using namespace llvm;
34
35namespace llvm {
36//===----------------------------------------------------------------------===//
37// ConvergingVLIWScheduler - Implementation of the standard
38// MachineSchedStrategy.
39//===----------------------------------------------------------------------===//
40
41class VLIWResourceModel {
42  /// ResourcesModel - Represents VLIW state.
43  /// Not limited to VLIW targets per say, but assumes
44  /// definition of DFA by a target.
45  DFAPacketizer *ResourcesModel;
46
47  const TargetSchedModel *SchedModel;
48
49  /// Local packet/bundle model. Purely
50  /// internal to the MI schedulre at the time.
51  std::vector<SUnit*> Packet;
52
53  /// Total packets created.
54  unsigned TotalPackets;
55
56public:
57  VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
58      : SchedModel(SM), TotalPackets(0) {
59  ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
60
61    // This hard requirement could be relaxed,
62    // but for now do not let it proceed.
63    assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
64
65    Packet.resize(SchedModel->getIssueWidth());
66    Packet.clear();
67    ResourcesModel->clearResources();
68  }
69
70  ~VLIWResourceModel() {
71    delete ResourcesModel;
72  }
73
74  void resetPacketState() {
75    Packet.clear();
76  }
77
78  void resetDFA() {
79    ResourcesModel->clearResources();
80  }
81
82  void reset() {
83    Packet.clear();
84    ResourcesModel->clearResources();
85  }
86
87  bool isResourceAvailable(SUnit *SU);
88  bool reserveResources(SUnit *SU);
89  unsigned getTotalPackets() const { return TotalPackets; }
90};
91
92/// Extend the standard ScheduleDAGMI to provide more context and override the
93/// top-level schedule() driver.
94class VLIWMachineScheduler : public ScheduleDAGMILive {
95public:
96  VLIWMachineScheduler(MachineSchedContext *C,
97                       std::unique_ptr<MachineSchedStrategy> S)
98      : ScheduleDAGMILive(C, std::move(S)) {}
99
100  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
101  /// time to do some work.
102  void schedule() override;
103  /// Perform platform-specific DAG postprocessing.
104  void postprocessDAG();
105};
106
107/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
108/// to balance the schedule.
109class ConvergingVLIWScheduler : public MachineSchedStrategy {
110
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;
116
117    // Register pressure values for the best candidate.
118    RegPressureDelta RPDelta;
119
120    // Best scheduling cost.
121    int SCost;
122
123    SchedCandidate(): SU(nullptr), SCost(0) {}
124  };
125  /// Represent the type of SchedCandidate found within a single queue.
126  enum CandResult {
127    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
128    BestCost};
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;
135    const TargetSchedModel *SchedModel;
136
137    ReadyQueue Available;
138    ReadyQueue Pending;
139    bool CheckPending;
140
141    ScheduleHazardRecognizer *HazardRec;
142    VLIWResourceModel *ResourceModel;
143
144    unsigned CurrCycle;
145    unsigned IssueCount;
146
147    /// MinReadyCycle - Cycle of the soonest available instruction.
148    unsigned MinReadyCycle;
149
150    // Remember the greatest min operand latency.
151    unsigned MaxMinLatency;
152
153    /// Pending queues extend the ready queues with the same ID and the
154    /// PendingFlag set.
155    VLIWSchedBoundary(unsigned ID, const Twine &Name):
156      DAG(nullptr), SchedModel(nullptr), Available(ID, Name+".A"),
157      Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
158      CheckPending(false), HazardRec(nullptr), ResourceModel(nullptr),
159      CurrCycle(0), IssueCount(0),
160      MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
161
162    ~VLIWSchedBoundary() {
163      delete ResourceModel;
164      delete HazardRec;
165    }
166
167    void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
168      DAG = dag;
169      SchedModel = smodel;
170    }
171
172    bool isTop() const {
173      return Available.getID() == ConvergingVLIWScheduler::TopQID;
174    }
175
176    bool checkHazard(SUnit *SU);
177
178    void releaseNode(SUnit *SU, unsigned ReadyCycle);
179
180    void bumpCycle();
181
182    void bumpNode(SUnit *SU);
183
184    void releasePending();
185
186    void removeReady(SUnit *SU);
187
188    SUnit *pickOnlyChoice();
189  };
190
191  VLIWMachineScheduler *DAG;
192  const TargetSchedModel *SchedModel;
193
194  // State of the top and bottom scheduled instruction boundaries.
195  VLIWSchedBoundary Top;
196  VLIWSchedBoundary Bot;
197
198public:
199  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
200  enum {
201    TopQID = 1,
202    BotQID = 2,
203    LogMaxQID = 2
204  };
205
206  ConvergingVLIWScheduler()
207    : DAG(nullptr), SchedModel(nullptr), Top(TopQID, "TopQ"),
208      Bot(BotQID, "BotQ") {}
209
210  void initialize(ScheduleDAGMI *dag) override;
211
212  SUnit *pickNode(bool &IsTopNode) override;
213
214  void schedNode(SUnit *SU, bool IsTopNode) override;
215
216  void releaseTopNode(SUnit *SU) override;
217
218  void releaseBottomNode(SUnit *SU) override;
219
220  unsigned ReportPackets() {
221    return Top.ResourceModel->getTotalPackets() +
222           Bot.ResourceModel->getTotalPackets();
223  }
224
225protected:
226  SUnit *pickNodeBidrectional(bool &IsTopNode);
227
228  int SchedulingCost(ReadyQueue &Q,
229                     SUnit *SU, SchedCandidate &Candidate,
230                     RegPressureDelta &Delta, bool verbose);
231
232  CandResult pickNodeFromQueue(ReadyQueue &Q,
233                               const RegPressureTracker &RPTracker,
234                               SchedCandidate &Candidate);
235#ifndef NDEBUG
236  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
237                      PressureChange P = PressureChange());
238#endif
239};
240
241} // namespace
242
243
244#endif
245