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