Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 1 | //===- HexagonMachineScheduler.h - Custom Hexagon MI scheduler --*- C++ -*-===// |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 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 | |
Benjamin Kramer | a7c40ef | 2014-08-13 16:26:38 +0000 | [diff] [blame] | 14 | #ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H |
| 15 | #define LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 16 | |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 17 | #include "llvm/ADT/STLExtras.h" |
| 18 | #include "llvm/ADT/Twine.h" |
| 19 | #include "llvm/CodeGen/DFAPacketizer.h" |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/MachineScheduler.h" |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 21 | #include "llvm/CodeGen/RegisterPressure.h" |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/ScheduleHazardRecognizer.h" |
David Blaikie | 3f833ed | 2017-11-08 01:01:31 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/TargetInstrInfo.h" |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/TargetSchedule.h" |
David Blaikie | b3bde2e | 2017-11-17 01:07:10 +0000 | [diff] [blame] | 25 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 26 | #include <algorithm> |
| 27 | #include <cassert> |
| 28 | #include <limits> |
| 29 | #include <memory> |
| 30 | #include <vector> |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 31 | |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 32 | namespace llvm { |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 33 | |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 34 | class SUnit; |
| 35 | |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 36 | class VLIWResourceModel { |
| 37 | /// ResourcesModel - Represents VLIW state. |
Krzysztof Parzyszek | 14f10e0 | 2017-04-27 14:38:21 +0000 | [diff] [blame] | 38 | /// Not limited to VLIW targets per se, but assumes |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 39 | /// definition of DFA by a target. |
| 40 | DFAPacketizer *ResourcesModel; |
| 41 | |
Andrew Trick | dd79f0f | 2012-10-10 05:43:09 +0000 | [diff] [blame] | 42 | const TargetSchedModel *SchedModel; |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 43 | |
| 44 | /// Local packet/bundle model. Purely |
| 45 | /// internal to the MI schedulre at the time. |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 46 | std::vector<SUnit *> Packet; |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 47 | |
| 48 | /// Total packets created. |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 49 | unsigned TotalPackets = 0; |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 50 | |
| 51 | public: |
Krzysztof Parzyszek | 6c715e1 | 2016-07-15 20:16:03 +0000 | [diff] [blame] | 52 | /// Save the last formed packet. |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 53 | std::vector<SUnit *> OldPacket; |
Krzysztof Parzyszek | 6c715e1 | 2016-07-15 20:16:03 +0000 | [diff] [blame] | 54 | |
Eric Christopher | f8b8e4a | 2015-02-02 22:11:40 +0000 | [diff] [blame] | 55 | VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM) |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 56 | : SchedModel(SM) { |
| 57 | ResourcesModel = STI.getInstrInfo()->CreateTargetScheduleState(STI); |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 58 | |
| 59 | // This hard requirement could be relaxed, |
| 60 | // but for now do not let it proceed. |
| 61 | assert(ResourcesModel && "Unimplemented CreateTargetScheduleState."); |
| 62 | |
Andrew Trick | dd79f0f | 2012-10-10 05:43:09 +0000 | [diff] [blame] | 63 | Packet.resize(SchedModel->getIssueWidth()); |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 64 | Packet.clear(); |
Krzysztof Parzyszek | 6c715e1 | 2016-07-15 20:16:03 +0000 | [diff] [blame] | 65 | OldPacket.resize(SchedModel->getIssueWidth()); |
| 66 | OldPacket.clear(); |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 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); |
Krzysztof Parzyszek | 6c715e1 | 2016-07-15 20:16:03 +0000 | [diff] [blame] | 89 | void savePacket(); |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 90 | unsigned getTotalPackets() const { return TotalPackets; } |
David Majnemer | 0d955d0 | 2016-08-11 22:21:41 +0000 | [diff] [blame] | 91 | bool isInPacket(SUnit *SU) const { return is_contained(Packet, SU); } |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 92 | }; |
| 93 | |
Andrew Trick | 7a8e100 | 2012-09-11 00:39:15 +0000 | [diff] [blame] | 94 | /// Extend the standard ScheduleDAGMI to provide more context and override the |
| 95 | /// top-level schedule() driver. |
Andrew Trick | d7f890e | 2013-12-28 21:56:47 +0000 | [diff] [blame] | 96 | class VLIWMachineScheduler : public ScheduleDAGMILive { |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 97 | public: |
David Blaikie | 422b93d | 2014-04-21 20:32:32 +0000 | [diff] [blame] | 98 | VLIWMachineScheduler(MachineSchedContext *C, |
| 99 | std::unique_ptr<MachineSchedStrategy> S) |
| 100 | : ScheduleDAGMILive(C, std::move(S)) {} |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 101 | |
| 102 | /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's |
| 103 | /// time to do some work. |
Craig Topper | fd38cbe | 2014-08-30 16:48:34 +0000 | [diff] [blame] | 104 | void schedule() override; |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 105 | }; |
| 106 | |
Krzysztof Parzyszek | 14f10e0 | 2017-04-27 14:38:21 +0000 | [diff] [blame] | 107 | //===----------------------------------------------------------------------===// |
| 108 | // ConvergingVLIWScheduler - Implementation of the standard |
| 109 | // MachineSchedStrategy. |
| 110 | //===----------------------------------------------------------------------===// |
| 111 | |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 112 | /// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics |
| 113 | /// to balance the schedule. |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 114 | class ConvergingVLIWScheduler : public MachineSchedStrategy { |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 115 | /// Store the state used by ConvergingVLIWScheduler heuristics, required |
| 116 | /// for the lifetime of one invocation of pickNode(). |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 117 | struct SchedCandidate { |
| 118 | // The best SUnit candidate. |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 119 | SUnit *SU = nullptr; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 120 | |
| 121 | // Register pressure values for the best candidate. |
| 122 | RegPressureDelta RPDelta; |
| 123 | |
| 124 | // Best scheduling cost. |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 125 | int SCost = 0; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 126 | |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 127 | SchedCandidate() = default; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 128 | }; |
| 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 Trick | d7f890e | 2013-12-28 21:56:47 +0000 | [diff] [blame] | 137 | struct VLIWSchedBoundary { |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 138 | VLIWMachineScheduler *DAG = nullptr; |
| 139 | const TargetSchedModel *SchedModel = nullptr; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 140 | |
| 141 | ReadyQueue Available; |
| 142 | ReadyQueue Pending; |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 143 | bool CheckPending = false; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 144 | |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 145 | ScheduleHazardRecognizer *HazardRec = nullptr; |
| 146 | VLIWResourceModel *ResourceModel = nullptr; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 147 | |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 148 | unsigned CurrCycle = 0; |
| 149 | unsigned IssueCount = 0; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 150 | |
| 151 | /// MinReadyCycle - Cycle of the soonest available instruction. |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 152 | unsigned MinReadyCycle = std::numeric_limits<unsigned>::max(); |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 153 | |
| 154 | // Remember the greatest min operand latency. |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 155 | unsigned MaxMinLatency = 0; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 156 | |
| 157 | /// Pending queues extend the ready queues with the same ID and the |
| 158 | /// PendingFlag set. |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 159 | VLIWSchedBoundary(unsigned ID, const Twine &Name) |
| 160 | : Available(ID, Name+".A"), |
| 161 | Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P") {} |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 162 | |
Andrew Trick | d7f890e | 2013-12-28 21:56:47 +0000 | [diff] [blame] | 163 | ~VLIWSchedBoundary() { |
Sergei Larin | ef4cc11 | 2012-09-10 17:31:34 +0000 | [diff] [blame] | 164 | delete ResourceModel; |
| 165 | delete HazardRec; |
| 166 | } |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 167 | |
Andrew Trick | dd79f0f | 2012-10-10 05:43:09 +0000 | [diff] [blame] | 168 | void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel) { |
| 169 | DAG = dag; |
| 170 | SchedModel = smodel; |
Krzysztof Parzyszek | 6c715e1 | 2016-07-15 20:16:03 +0000 | [diff] [blame] | 171 | IssueCount = 0; |
Andrew Trick | dd79f0f | 2012-10-10 05:43:09 +0000 | [diff] [blame] | 172 | } |
| 173 | |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 174 | 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 Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 193 | VLIWMachineScheduler *DAG = nullptr; |
| 194 | const TargetSchedModel *SchedModel = nullptr; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 195 | |
| 196 | // State of the top and bottom scheduled instruction boundaries. |
Andrew Trick | d7f890e | 2013-12-28 21:56:47 +0000 | [diff] [blame] | 197 | VLIWSchedBoundary Top; |
| 198 | VLIWSchedBoundary Bot; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 199 | |
| 200 | public: |
| 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 Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 208 | ConvergingVLIWScheduler() : Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 209 | |
Craig Topper | fd38cbe | 2014-08-30 16:48:34 +0000 | [diff] [blame] | 210 | void initialize(ScheduleDAGMI *dag) override; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 211 | |
Craig Topper | fd38cbe | 2014-08-30 16:48:34 +0000 | [diff] [blame] | 212 | SUnit *pickNode(bool &IsTopNode) override; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 213 | |
Craig Topper | fd38cbe | 2014-08-30 16:48:34 +0000 | [diff] [blame] | 214 | void schedNode(SUnit *SU, bool IsTopNode) override; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 215 | |
Craig Topper | fd38cbe | 2014-08-30 16:48:34 +0000 | [diff] [blame] | 216 | void releaseTopNode(SUnit *SU) override; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 217 | |
Craig Topper | fd38cbe | 2014-08-30 16:48:34 +0000 | [diff] [blame] | 218 | void releaseBottomNode(SUnit *SU) override; |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 219 | |
Sergei Larin | 2db64a7 | 2012-09-14 15:07:59 +0000 | [diff] [blame] | 220 | unsigned ReportPackets() { |
| 221 | return Top.ResourceModel->getTotalPackets() + |
| 222 | Bot.ResourceModel->getTotalPackets(); |
| 223 | } |
| 224 | |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 225 | protected: |
| 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 Parzyszek | f05dc4d | 2016-07-18 15:47:25 +0000 | [diff] [blame] | 237 | int Cost, PressureChange P = PressureChange()); |
| 238 | |
| 239 | void readyQueueVerboseDump(const RegPressureTracker &RPTracker, |
| 240 | SchedCandidate &Candidate, ReadyQueue &Q); |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 241 | #endif |
| 242 | }; |
| 243 | |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 244 | } // end namespace llvm |
Sergei Larin | 4d8986a | 2012-09-04 14:49:56 +0000 | [diff] [blame] | 245 | |
Eugene Zelenko | 3b87336 | 2017-09-28 22:27:31 +0000 | [diff] [blame] | 246 | #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONMACHINESCHEDULER_H |