blob: bf7fe2d484a220a24b9a9f8ac1c8a5cc974722d6 [file] [log] [blame]
Eugene Zelenko3b873362017-09-28 22:27:31 +00001//===- HexagonMachineScheduler.h - Custom Hexagon MI scheduler --*- C++ -*-===//
Sergei Larin4d8986a2012-09-04 14:49:56 +00002//
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
Benjamin Kramera7c40ef2014-08-13 16:26:38 +000014#ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
15#define LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H
Sergei Larin4d8986a2012-09-04 14:49:56 +000016
Eugene Zelenko3b873362017-09-28 22:27:31 +000017#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/Twine.h"
19#include "llvm/CodeGen/DFAPacketizer.h"
Sergei Larin4d8986a2012-09-04 14:49:56 +000020#include "llvm/CodeGen/MachineScheduler.h"
Sergei Larin4d8986a2012-09-04 14:49:56 +000021#include "llvm/CodeGen/RegisterPressure.h"
Sergei Larin4d8986a2012-09-04 14:49:56 +000022#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
David Blaikie3f833ed2017-11-08 01:01:31 +000023#include "llvm/CodeGen/TargetInstrInfo.h"
Eugene Zelenko3b873362017-09-28 22:27:31 +000024#include "llvm/CodeGen/TargetSchedule.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000025#include "llvm/CodeGen/TargetSubtargetInfo.h"
Eugene Zelenko3b873362017-09-28 22:27:31 +000026#include <algorithm>
27#include <cassert>
28#include <limits>
29#include <memory>
30#include <vector>
Sergei Larin4d8986a2012-09-04 14:49:56 +000031
Sergei Larin4d8986a2012-09-04 14:49:56 +000032namespace llvm {
Sergei Larin4d8986a2012-09-04 14:49:56 +000033
Eugene Zelenko3b873362017-09-28 22:27:31 +000034class SUnit;
35
Sergei Larinef4cc112012-09-10 17:31:34 +000036class VLIWResourceModel {
37 /// ResourcesModel - Represents VLIW state.
Krzysztof Parzyszek14f10e02017-04-27 14:38:21 +000038 /// Not limited to VLIW targets per se, but assumes
Sergei Larinef4cc112012-09-10 17:31:34 +000039 /// definition of DFA by a target.
40 DFAPacketizer *ResourcesModel;
41
Andrew Trickdd79f0f2012-10-10 05:43:09 +000042 const TargetSchedModel *SchedModel;
Sergei Larinef4cc112012-09-10 17:31:34 +000043
44 /// Local packet/bundle model. Purely
45 /// internal to the MI schedulre at the time.
Eugene Zelenko3b873362017-09-28 22:27:31 +000046 std::vector<SUnit *> Packet;
Sergei Larinef4cc112012-09-10 17:31:34 +000047
48 /// Total packets created.
Eugene Zelenko3b873362017-09-28 22:27:31 +000049 unsigned TotalPackets = 0;
Sergei Larinef4cc112012-09-10 17:31:34 +000050
51public:
Krzysztof Parzyszek6c715e12016-07-15 20:16:03 +000052 /// Save the last formed packet.
Eugene Zelenko3b873362017-09-28 22:27:31 +000053 std::vector<SUnit *> OldPacket;
Krzysztof Parzyszek6c715e12016-07-15 20:16:03 +000054
Eric Christopherf8b8e4a2015-02-02 22:11:40 +000055 VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
Eugene Zelenko3b873362017-09-28 22:27:31 +000056 : SchedModel(SM) {
57 ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI);
Sergei Larinef4cc112012-09-10 17:31:34 +000058
59 // This hard requirement could be relaxed,
60 // but for now do not let it proceed.
61 assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
62
Andrew Trickdd79f0f2012-10-10 05:43:09 +000063 Packet.resize(SchedModel->getIssueWidth());
Sergei Larinef4cc112012-09-10 17:31:34 +000064 Packet.clear();
Krzysztof Parzyszek6c715e12016-07-15 20:16:03 +000065 OldPacket.resize(SchedModel->getIssueWidth());
66 OldPacket.clear();
Sergei Larinef4cc112012-09-10 17:31:34 +000067 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);
Krzysztof Parzyszek6c715e12016-07-15 20:16:03 +000089 void savePacket();
Sergei Larinef4cc112012-09-10 17:31:34 +000090 unsigned getTotalPackets() const { return TotalPackets; }
David Majnemer0d955d02016-08-11 22:21:41 +000091 bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); }
Sergei Larinef4cc112012-09-10 17:31:34 +000092};
93
Andrew Trick7a8e1002012-09-11 00:39:15 +000094/// Extend the standard ScheduleDAGMI to provide more context and override the
95/// top-level schedule() driver.
Andrew Trickd7f890e2013-12-28 21:56:47 +000096class VLIWMachineScheduler : public ScheduleDAGMILive {
Sergei Larinef4cc112012-09-10 17:31:34 +000097public:
David Blaikie422b93d2014-04-21 20:32:32 +000098 VLIWMachineScheduler(MachineSchedContext *C,
99 std::unique_ptr<MachineSchedStrategy> S)
100 : ScheduleDAGMILive(C, std::move(S)) {}
Sergei Larinef4cc112012-09-10 17:31:34 +0000101
102 /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
103 /// time to do some work.
Craig Topperfd38cbe2014-08-30 16:48:34 +0000104 void schedule() override;
Sergei Larinef4cc112012-09-10 17:31:34 +0000105};
106
Krzysztof Parzyszek14f10e02017-04-27 14:38:21 +0000107//===----------------------------------------------------------------------===//
108// ConvergingVLIWScheduler - Implementation of the standard
109// MachineSchedStrategy.
110//===----------------------------------------------------------------------===//
111
Sergei Larinef4cc112012-09-10 17:31:34 +0000112/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
113/// to balance the schedule.
Sergei Larin4d8986a2012-09-04 14:49:56 +0000114class ConvergingVLIWScheduler : public MachineSchedStrategy {
Sergei Larinef4cc112012-09-10 17:31:34 +0000115 /// Store the state used by ConvergingVLIWScheduler heuristics, required
116 /// for the lifetime of one invocation of pickNode().
Sergei Larin4d8986a2012-09-04 14:49:56 +0000117 struct SchedCandidate {
118 // The best SUnit candidate.
Eugene Zelenko3b873362017-09-28 22:27:31 +0000119 SUnit *SU = nullptr;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000120
121 // Register pressure values for the best candidate.
122 RegPressureDelta RPDelta;
123
124 // Best scheduling cost.
Eugene Zelenko3b873362017-09-28 22:27:31 +0000125 int SCost = 0;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000126
Eugene Zelenko3b873362017-09-28 22:27:31 +0000127 SchedCandidate() = default;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000128 };
129 /// Represent the type of SchedCandidate found within a single queue.
130 enum CandResult {
131 NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
132 BestCost};
133
134 /// Each Scheduling boundary is associated with ready queues. It tracks the
135 /// current cycle in whichever direction at has moved, and maintains the state
136 /// of "hazards" and other interlocks at the current cycle.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000137 struct VLIWSchedBoundary {
Eugene Zelenko3b873362017-09-28 22:27:31 +0000138 VLIWMachineScheduler *DAG = nullptr;
139 const TargetSchedModel *SchedModel = nullptr;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000140
141 ReadyQueue Available;
142 ReadyQueue Pending;
Eugene Zelenko3b873362017-09-28 22:27:31 +0000143 bool CheckPending = false;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000144
Eugene Zelenko3b873362017-09-28 22:27:31 +0000145 ScheduleHazardRecognizer *HazardRec = nullptr;
146 VLIWResourceModel *ResourceModel = nullptr;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000147
Eugene Zelenko3b873362017-09-28 22:27:31 +0000148 unsigned CurrCycle = 0;
149 unsigned IssueCount = 0;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000150
151 /// MinReadyCycle - Cycle of the soonest available instruction.
Eugene Zelenko3b873362017-09-28 22:27:31 +0000152 unsigned MinReadyCycle = std::numeric_limits<unsigned>::max();
Sergei Larin4d8986a2012-09-04 14:49:56 +0000153
154 // Remember the greatest min operand latency.
Eugene Zelenko3b873362017-09-28 22:27:31 +0000155 unsigned MaxMinLatency = 0;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000156
157 /// Pending queues extend the ready queues with the same ID and the
158 /// PendingFlag set.
Eugene Zelenko3b873362017-09-28 22:27:31 +0000159 VLIWSchedBoundary(unsigned ID, const Twine &Name)
160 : Available(ID, Name+".A"),
161 Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {}
Sergei Larin4d8986a2012-09-04 14:49:56 +0000162
Andrew Trickd7f890e2013-12-28 21:56:47 +0000163 ~VLIWSchedBoundary() {
Sergei Larinef4cc112012-09-10 17:31:34 +0000164 delete ResourceModel;
165 delete HazardRec;
166 }
Sergei Larin4d8986a2012-09-04 14:49:56 +0000167
Andrew Trickdd79f0f2012-10-10 05:43:09 +0000168 void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) {
169 DAG = dag;
170 SchedModel = smodel;
Krzysztof Parzyszek6c715e12016-07-15 20:16:03 +0000171 IssueCount = 0;
Andrew Trickdd79f0f2012-10-10 05:43:09 +0000172 }
173
Sergei Larin4d8986a2012-09-04 14:49:56 +0000174 bool isTop() const {
175 return Available.getID() == ConvergingVLIWScheduler::TopQID;
176 }
177
178 bool checkHazard(SUnit *SU);
179
180 void releaseNode(SUnit *SU, unsigned ReadyCycle);
181
182 void bumpCycle();
183
184 void bumpNode(SUnit *SU);
185
186 void releasePending();
187
188 void removeReady(SUnit *SU);
189
190 SUnit *pickOnlyChoice();
191 };
192
Eugene Zelenko3b873362017-09-28 22:27:31 +0000193 VLIWMachineScheduler *DAG = nullptr;
194 const TargetSchedModel *SchedModel = nullptr;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000195
196 // State of the top and bottom scheduled instruction boundaries.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000197 VLIWSchedBoundary Top;
198 VLIWSchedBoundary Bot;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000199
200public:
201 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
202 enum {
203 TopQID = 1,
204 BotQID = 2,
205 LogMaxQID = 2
206 };
207
Eugene Zelenko3b873362017-09-28 22:27:31 +0000208 ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
Sergei Larin4d8986a2012-09-04 14:49:56 +0000209
Craig Topperfd38cbe2014-08-30 16:48:34 +0000210 void initialize(ScheduleDAGMI *dag) override;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000211
Craig Topperfd38cbe2014-08-30 16:48:34 +0000212 SUnit *pickNode(bool &IsTopNode) override;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000213
Craig Topperfd38cbe2014-08-30 16:48:34 +0000214 void schedNode(SUnit *SU, bool IsTopNode) override;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000215
Craig Topperfd38cbe2014-08-30 16:48:34 +0000216 void releaseTopNode(SUnit *SU) override;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000217
Craig Topperfd38cbe2014-08-30 16:48:34 +0000218 void releaseBottomNode(SUnit *SU) override;
Sergei Larin4d8986a2012-09-04 14:49:56 +0000219
Sergei Larin2db64a72012-09-14 15:07:59 +0000220 unsigned ReportPackets() {
221 return Top.ResourceModel->getTotalPackets() +
222 Bot.ResourceModel->getTotalPackets();
223 }
224
Sergei Larin4d8986a2012-09-04 14:49:56 +0000225protected:
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,
Krzysztof Parzyszekf05dc4d2016-07-18 15:47:25 +0000237 int Cost, PressureChange P = PressureChange());
238
239 void readyQueueVerboseDump(const RegPressureTracker &RPTracker,
240 SchedCandidate &Candidate, ReadyQueue &Q);
Sergei Larin4d8986a2012-09-04 14:49:56 +0000241#endif
242};
243
Eugene Zelenko3b873362017-09-28 22:27:31 +0000244} // end namespace llvm
Sergei Larin4d8986a2012-09-04 14:49:56 +0000245
Eugene Zelenko3b873362017-09-28 22:27:31 +0000246#endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H