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