/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/SelectionDAG/ResourcePriorityQueue.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- ResourcePriorityQueue.cpp - A DFA-oriented priority queue -*- C++ -*-==// |
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 | | // This file implements the ResourcePriorityQueue class, which is a |
11 | | // SchedulingPriorityQueue that prioritizes instructions using DFA state to |
12 | | // reduce the length of the critical path through the basic block |
13 | | // on VLIW platforms. |
14 | | // The scheduler is basically a top-down adaptable list scheduler with DFA |
15 | | // resource tracking added to the cost function. |
16 | | // DFA is queried as a state machine to model "packets/bundles" during |
17 | | // schedule. Currently packets/bundles are discarded at the end of |
18 | | // scheduling, affecting only order of instructions. |
19 | | // |
20 | | //===----------------------------------------------------------------------===// |
21 | | |
22 | | #include "llvm/CodeGen/ResourcePriorityQueue.h" |
23 | | #include "llvm/CodeGen/MachineInstr.h" |
24 | | #include "llvm/CodeGen/SelectionDAGNodes.h" |
25 | | #include "llvm/Support/CommandLine.h" |
26 | | #include "llvm/Support/Debug.h" |
27 | | #include "llvm/Support/raw_ostream.h" |
28 | | #include "llvm/Target/TargetLowering.h" |
29 | | #include "llvm/Target/TargetMachine.h" |
30 | | #include "llvm/Target/TargetSubtargetInfo.h" |
31 | | |
32 | | using namespace llvm; |
33 | | |
34 | | #define DEBUG_TYPE "scheduler" |
35 | | |
36 | | static cl::opt<bool> DisableDFASched("disable-dfa-sched", cl::Hidden, |
37 | | cl::ZeroOrMore, cl::init(false), |
38 | | cl::desc("Disable use of DFA during scheduling")); |
39 | | |
40 | | static cl::opt<int> RegPressureThreshold( |
41 | | "dfa-sched-reg-pressure-threshold", cl::Hidden, cl::ZeroOrMore, cl::init(5), |
42 | | cl::desc("Track reg pressure and switch priority to in-depth")); |
43 | | |
44 | | ResourcePriorityQueue::ResourcePriorityQueue(SelectionDAGISel *IS) |
45 | 0 | : Picker(this), InstrItins(IS->MF->getSubtarget().getInstrItineraryData()) { |
46 | 0 | const TargetSubtargetInfo &STI = IS->MF->getSubtarget(); |
47 | 0 | TRI = STI.getRegisterInfo(); |
48 | 0 | TLI = IS->TLI; |
49 | 0 | TII = STI.getInstrInfo(); |
50 | 0 | ResourcesModel.reset(TII->CreateTargetScheduleState(STI)); |
51 | 0 | // This hard requirement could be relaxed, but for now |
52 | 0 | // do not let it proceed. |
53 | 0 | assert(ResourcesModel && "Unimplemented CreateTargetScheduleState."); |
54 | 0 |
|
55 | 0 | unsigned NumRC = TRI->getNumRegClasses(); |
56 | 0 | RegLimit.resize(NumRC); |
57 | 0 | RegPressure.resize(NumRC); |
58 | 0 | std::fill(RegLimit.begin(), RegLimit.end(), 0); |
59 | 0 | std::fill(RegPressure.begin(), RegPressure.end(), 0); |
60 | 0 | for (const TargetRegisterClass *RC : TRI->regclasses()) |
61 | 0 | RegLimit[RC->getID()] = TRI->getRegPressureLimit(RC, *IS->MF); |
62 | 0 |
|
63 | 0 | ParallelLiveRanges = 0; |
64 | 0 | HorizontalVerticalBalance = 0; |
65 | 0 | } |
66 | | |
67 | | unsigned |
68 | 0 | ResourcePriorityQueue::numberRCValPredInSU(SUnit *SU, unsigned RCId) { |
69 | 0 | unsigned NumberDeps = 0; |
70 | 0 | for (SDep &Pred : SU->Preds) { |
71 | 0 | if (Pred.isCtrl()) |
72 | 0 | continue; |
73 | 0 |
|
74 | 0 | SUnit *PredSU = Pred.getSUnit(); |
75 | 0 | const SDNode *ScegN = PredSU->getNode(); |
76 | 0 |
|
77 | 0 | if (!ScegN) |
78 | 0 | continue; |
79 | 0 |
|
80 | 0 | // If value is passed to CopyToReg, it is probably |
81 | 0 | // live outside BB. |
82 | 0 | switch (ScegN->getOpcode()) { |
83 | 0 | default: break; |
84 | 0 | case ISD::TokenFactor: break; |
85 | 0 | case ISD::CopyFromReg: NumberDeps++; break; |
86 | 0 | case ISD::CopyToReg: break; |
87 | 0 | case ISD::INLINEASM: break; |
88 | 0 | } |
89 | 0 | if (0 !ScegN->isMachineOpcode()0 ) |
90 | 0 | continue; |
91 | 0 |
|
92 | 0 | for (unsigned i = 0, e = ScegN->getNumValues(); 0 i != e0 ; ++i0 ) { |
93 | 0 | MVT VT = ScegN->getSimpleValueType(i); |
94 | 0 | if (TLI->isTypeLegal(VT) |
95 | 0 | && (TLI->getRegClassFor(VT)->getID() == RCId)0 ) { |
96 | 0 | NumberDeps++; |
97 | 0 | break; |
98 | 0 | } |
99 | 0 | } |
100 | 0 | } |
101 | 0 | return NumberDeps; |
102 | 0 | } |
103 | | |
104 | | unsigned ResourcePriorityQueue::numberRCValSuccInSU(SUnit *SU, |
105 | 0 | unsigned RCId) { |
106 | 0 | unsigned NumberDeps = 0; |
107 | 0 | for (const SDep &Succ : SU->Succs) { |
108 | 0 | if (Succ.isCtrl()) |
109 | 0 | continue; |
110 | 0 |
|
111 | 0 | SUnit *SuccSU = Succ.getSUnit(); |
112 | 0 | const SDNode *ScegN = SuccSU->getNode(); |
113 | 0 | if (!ScegN) |
114 | 0 | continue; |
115 | 0 |
|
116 | 0 | // If value is passed to CopyToReg, it is probably |
117 | 0 | // live outside BB. |
118 | 0 | switch (ScegN->getOpcode()) { |
119 | 0 | default: break; |
120 | 0 | case ISD::TokenFactor: break; |
121 | 0 | case ISD::CopyFromReg: break; |
122 | 0 | case ISD::CopyToReg: NumberDeps++; break; |
123 | 0 | case ISD::INLINEASM: break; |
124 | 0 | } |
125 | 0 | if (0 !ScegN->isMachineOpcode()0 ) |
126 | 0 | continue; |
127 | 0 |
|
128 | 0 | for (unsigned i = 0, e = ScegN->getNumOperands(); 0 i != e0 ; ++i0 ) { |
129 | 0 | const SDValue &Op = ScegN->getOperand(i); |
130 | 0 | MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); |
131 | 0 | if (TLI->isTypeLegal(VT) |
132 | 0 | && (TLI->getRegClassFor(VT)->getID() == RCId)0 ) { |
133 | 0 | NumberDeps++; |
134 | 0 | break; |
135 | 0 | } |
136 | 0 | } |
137 | 0 | } |
138 | 0 | return NumberDeps; |
139 | 0 | } |
140 | | |
141 | 0 | static unsigned numberCtrlDepsInSU(SUnit *SU) { |
142 | 0 | unsigned NumberDeps = 0; |
143 | 0 | for (const SDep &Succ : SU->Succs) |
144 | 0 | if (0 Succ.isCtrl()0 ) |
145 | 0 | NumberDeps++; |
146 | 0 |
|
147 | 0 | return NumberDeps; |
148 | 0 | } |
149 | | |
150 | 0 | static unsigned numberCtrlPredInSU(SUnit *SU) { |
151 | 0 | unsigned NumberDeps = 0; |
152 | 0 | for (SDep &Pred : SU->Preds) |
153 | 0 | if (0 Pred.isCtrl()0 ) |
154 | 0 | NumberDeps++; |
155 | 0 |
|
156 | 0 | return NumberDeps; |
157 | 0 | } |
158 | | |
159 | | /// |
160 | | /// Initialize nodes. |
161 | | /// |
162 | 0 | void ResourcePriorityQueue::initNodes(std::vector<SUnit> &sunits) { |
163 | 0 | SUnits = &sunits; |
164 | 0 | NumNodesSolelyBlocking.resize(SUnits->size(), 0); |
165 | 0 |
|
166 | 0 | for (unsigned i = 0, e = SUnits->size(); i != e0 ; ++i0 ) { |
167 | 0 | SUnit *SU = &(*SUnits)[i]; |
168 | 0 | initNumRegDefsLeft(SU); |
169 | 0 | SU->NodeQueueId = 0; |
170 | 0 | } |
171 | 0 | } |
172 | | |
173 | | /// This heuristic is used if DFA scheduling is not desired |
174 | | /// for some VLIW platform. |
175 | 0 | bool resource_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { |
176 | 0 | // The isScheduleHigh flag allows nodes with wraparound dependencies that |
177 | 0 | // cannot easily be modeled as edges with latencies to be scheduled as |
178 | 0 | // soon as possible in a top-down schedule. |
179 | 0 | if (LHS->isScheduleHigh && 0 !RHS->isScheduleHigh0 ) |
180 | 0 | return false; |
181 | 0 |
|
182 | 0 | if (0 !LHS->isScheduleHigh && 0 RHS->isScheduleHigh0 ) |
183 | 0 | return true; |
184 | 0 |
|
185 | 0 | unsigned LHSNum = LHS->NodeNum; |
186 | 0 | unsigned RHSNum = RHS->NodeNum; |
187 | 0 |
|
188 | 0 | // The most important heuristic is scheduling the critical path. |
189 | 0 | unsigned LHSLatency = PQ->getLatency(LHSNum); |
190 | 0 | unsigned RHSLatency = PQ->getLatency(RHSNum); |
191 | 0 | if (LHSLatency < RHSLatency0 ) return true0 ; |
192 | 0 | if (0 LHSLatency > RHSLatency0 ) return false0 ; |
193 | 0 |
|
194 | 0 | // After that, if two nodes have identical latencies, look to see if one will |
195 | 0 | // unblock more other nodes than the other. |
196 | 0 | unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); |
197 | 0 | unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); |
198 | 0 | if (LHSBlocked < RHSBlocked0 ) return true0 ; |
199 | 0 | if (0 LHSBlocked > RHSBlocked0 ) return false0 ; |
200 | 0 |
|
201 | 0 | // Finally, just to provide a stable ordering, use the node number as a |
202 | 0 | // deciding factor. |
203 | 0 | return LHSNum < RHSNum; |
204 | 0 | } |
205 | | |
206 | | |
207 | | /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor |
208 | | /// of SU, return it, otherwise return null. |
209 | 0 | SUnit *ResourcePriorityQueue::getSingleUnscheduledPred(SUnit *SU) { |
210 | 0 | SUnit *OnlyAvailablePred = nullptr; |
211 | 0 | for (const SDep &Pred : SU->Preds) { |
212 | 0 | SUnit &PredSU = *Pred.getSUnit(); |
213 | 0 | if (!PredSU.isScheduled0 ) { |
214 | 0 | // We found an available, but not scheduled, predecessor. If it's the |
215 | 0 | // only one we have found, keep track of it... otherwise give up. |
216 | 0 | if (OnlyAvailablePred && 0 OnlyAvailablePred != &PredSU0 ) |
217 | 0 | return nullptr; |
218 | 0 | OnlyAvailablePred = &PredSU; |
219 | 0 | } |
220 | 0 | } |
221 | 0 | return OnlyAvailablePred; |
222 | 0 | } |
223 | | |
224 | 0 | void ResourcePriorityQueue::push(SUnit *SU) { |
225 | 0 | // Look at all of the successors of this node. Count the number of nodes that |
226 | 0 | // this node is the sole unscheduled node for. |
227 | 0 | unsigned NumNodesBlocking = 0; |
228 | 0 | for (const SDep &Succ : SU->Succs) |
229 | 0 | if (0 getSingleUnscheduledPred(Succ.getSUnit()) == SU0 ) |
230 | 0 | ++NumNodesBlocking; |
231 | 0 |
|
232 | 0 | NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; |
233 | 0 | Queue.push_back(SU); |
234 | 0 | } |
235 | | |
236 | | /// Check if scheduling of this SU is possible |
237 | | /// in the current packet. |
238 | 0 | bool ResourcePriorityQueue::isResourceAvailable(SUnit *SU) { |
239 | 0 | if (!SU || 0 !SU->getNode()0 ) |
240 | 0 | return false; |
241 | 0 |
|
242 | 0 | // If this is a compound instruction, |
243 | 0 | // it is likely to be a call. Do not delay it. |
244 | 0 | if (0 SU->getNode()->getGluedNode()0 ) |
245 | 0 | return true; |
246 | 0 |
|
247 | 0 | // First see if the pipeline could receive this instruction |
248 | 0 | // in the current cycle. |
249 | 0 | if (0 SU->getNode()->isMachineOpcode()0 ) |
250 | 0 | switch (SU->getNode()->getMachineOpcode()) { |
251 | 0 | default: |
252 | 0 | if (!ResourcesModel->canReserveResources(&TII->get( |
253 | 0 | SU->getNode()->getMachineOpcode()))) |
254 | 0 | return false; |
255 | 0 | case TargetOpcode::EXTRACT_SUBREG: |
256 | 0 | case TargetOpcode::INSERT_SUBREG: |
257 | 0 | case TargetOpcode::SUBREG_TO_REG: |
258 | 0 | case TargetOpcode::REG_SEQUENCE: |
259 | 0 | case TargetOpcode::IMPLICIT_DEF: |
260 | 0 | break; |
261 | 0 | } |
262 | 0 |
|
263 | 0 | // Now see if there are no other dependencies |
264 | 0 | // to instructions already in the packet. |
265 | 0 | for (unsigned i = 0, e = Packet.size(); 0 i != e0 ; ++i0 ) |
266 | 0 | for (const SDep &Succ : Packet[i]->Succs) 0 { |
267 | 0 | // Since we do not add pseudos to packets, might as well |
268 | 0 | // ignore order deps. |
269 | 0 | if (Succ.isCtrl()) |
270 | 0 | continue; |
271 | 0 |
|
272 | 0 | if (0 Succ.getSUnit() == SU0 ) |
273 | 0 | return false; |
274 | 0 | } |
275 | 0 |
|
276 | 0 | return true; |
277 | 0 | } |
278 | | |
279 | | /// Keep track of available resources. |
280 | 0 | void ResourcePriorityQueue::reserveResources(SUnit *SU) { |
281 | 0 | // If this SU does not fit in the packet |
282 | 0 | // start a new one. |
283 | 0 | if (!isResourceAvailable(SU) || 0 SU->getNode()->getGluedNode()0 ) { |
284 | 0 | ResourcesModel->clearResources(); |
285 | 0 | Packet.clear(); |
286 | 0 | } |
287 | 0 |
|
288 | 0 | if (SU->getNode() && 0 SU->getNode()->isMachineOpcode()0 ) { |
289 | 0 | switch (SU->getNode()->getMachineOpcode()) { |
290 | 0 | default: |
291 | 0 | ResourcesModel->reserveResources(&TII->get( |
292 | 0 | SU->getNode()->getMachineOpcode())); |
293 | 0 | break; |
294 | 0 | case TargetOpcode::EXTRACT_SUBREG: |
295 | 0 | case TargetOpcode::INSERT_SUBREG: |
296 | 0 | case TargetOpcode::SUBREG_TO_REG: |
297 | 0 | case TargetOpcode::REG_SEQUENCE: |
298 | 0 | case TargetOpcode::IMPLICIT_DEF: |
299 | 0 | break; |
300 | 0 | } |
301 | 0 | Packet.push_back(SU); |
302 | 0 | } |
303 | 0 | // Forcefully end packet for PseudoOps. |
304 | 0 | else { |
305 | 0 | ResourcesModel->clearResources(); |
306 | 0 | Packet.clear(); |
307 | 0 | } |
308 | 0 |
|
309 | 0 | // If packet is now full, reset the state so in the next cycle |
310 | 0 | // we start fresh. |
311 | 0 | if (0 Packet.size() >= InstrItins->SchedModel.IssueWidth0 ) { |
312 | 0 | ResourcesModel->clearResources(); |
313 | 0 | Packet.clear(); |
314 | 0 | } |
315 | 0 | } |
316 | | |
317 | 0 | int ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) { |
318 | 0 | int RegBalance = 0; |
319 | 0 |
|
320 | 0 | if (!SU || 0 !SU->getNode()0 || !SU->getNode()->isMachineOpcode()0 ) |
321 | 0 | return RegBalance; |
322 | 0 |
|
323 | 0 | // Gen estimate. |
324 | 0 | for (unsigned i = 0, e = SU->getNode()->getNumValues(); 0 i != e0 ; ++i0 ) { |
325 | 0 | MVT VT = SU->getNode()->getSimpleValueType(i); |
326 | 0 | if (TLI->isTypeLegal(VT) |
327 | 0 | && TLI->getRegClassFor(VT) |
328 | 0 | && TLI->getRegClassFor(VT)->getID() == RCId) |
329 | 0 | RegBalance += numberRCValSuccInSU(SU, RCId); |
330 | 0 | } |
331 | 0 | // Kill estimate. |
332 | 0 | for (unsigned i = 0, e = SU->getNode()->getNumOperands(); i != e0 ; ++i0 ) { |
333 | 0 | const SDValue &Op = SU->getNode()->getOperand(i); |
334 | 0 | MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); |
335 | 0 | if (isa<ConstantSDNode>(Op.getNode())) |
336 | 0 | continue; |
337 | 0 |
|
338 | 0 | if (0 TLI->isTypeLegal(VT) && 0 TLI->getRegClassFor(VT)0 |
339 | 0 | && TLI->getRegClassFor(VT)->getID() == RCId) |
340 | 0 | RegBalance -= numberRCValPredInSU(SU, RCId); |
341 | 0 | } |
342 | 0 | return RegBalance; |
343 | 0 | } |
344 | | |
345 | | /// Estimates change in reg pressure from this SU. |
346 | | /// It is achieved by trivial tracking of defined |
347 | | /// and used vregs in dependent instructions. |
348 | | /// The RawPressure flag makes this function to ignore |
349 | | /// existing reg file sizes, and report raw def/use |
350 | | /// balance. |
351 | 0 | int ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) { |
352 | 0 | int RegBalance = 0; |
353 | 0 |
|
354 | 0 | if (!SU || 0 !SU->getNode()0 || !SU->getNode()->isMachineOpcode()0 ) |
355 | 0 | return RegBalance; |
356 | 0 |
|
357 | 0 | if (0 RawPressure0 ) { |
358 | 0 | for (const TargetRegisterClass *RC : TRI->regclasses()) |
359 | 0 | RegBalance += rawRegPressureDelta(SU, RC->getID()); |
360 | 0 | } |
361 | 0 | else { |
362 | 0 | for (const TargetRegisterClass *RC : TRI->regclasses()) { |
363 | 0 | if ((RegPressure[RC->getID()] + |
364 | 0 | rawRegPressureDelta(SU, RC->getID()) > 0) && |
365 | 0 | (RegPressure[RC->getID()] + |
366 | 0 | rawRegPressureDelta(SU, RC->getID()) >= RegLimit[RC->getID()])) |
367 | 0 | RegBalance += rawRegPressureDelta(SU, RC->getID()); |
368 | 0 | } |
369 | 0 | } |
370 | 0 |
|
371 | 0 | return RegBalance; |
372 | 0 | } |
373 | | |
374 | | // Constants used to denote relative importance of |
375 | | // heuristic components for cost computation. |
376 | | static const unsigned PriorityOne = 200; |
377 | | static const unsigned PriorityTwo = 50; |
378 | | static const unsigned PriorityThree = 15; |
379 | | static const unsigned PriorityFour = 5; |
380 | | static const unsigned ScaleOne = 20; |
381 | | static const unsigned ScaleTwo = 10; |
382 | | static const unsigned ScaleThree = 5; |
383 | | static const unsigned FactorOne = 2; |
384 | | |
385 | | /// Returns single number reflecting benefit of scheduling SU |
386 | | /// in the current cycle. |
387 | 0 | int ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) { |
388 | 0 | // Initial trivial priority. |
389 | 0 | int ResCount = 1; |
390 | 0 |
|
391 | 0 | // Do not waste time on a node that is already scheduled. |
392 | 0 | if (SU->isScheduled) |
393 | 0 | return ResCount; |
394 | 0 |
|
395 | 0 | // Forced priority is high. |
396 | 0 | if (0 SU->isScheduleHigh0 ) |
397 | 0 | ResCount += PriorityOne; |
398 | 0 |
|
399 | 0 | // Adaptable scheduling |
400 | 0 | // A small, but very parallel |
401 | 0 | // region, where reg pressure is an issue. |
402 | 0 | if (HorizontalVerticalBalance > RegPressureThreshold0 ) { |
403 | 0 | // Critical path first |
404 | 0 | ResCount += (SU->getHeight() * ScaleTwo); |
405 | 0 | // If resources are available for it, multiply the |
406 | 0 | // chance of scheduling. |
407 | 0 | if (isResourceAvailable(SU)) |
408 | 0 | ResCount <<= FactorOne; |
409 | 0 |
|
410 | 0 | // Consider change to reg pressure from scheduling |
411 | 0 | // this SU. |
412 | 0 | ResCount -= (regPressureDelta(SU,true) * ScaleOne); |
413 | 0 | } |
414 | 0 | // Default heuristic, greeady and |
415 | 0 | // critical path driven. |
416 | 0 | else { |
417 | 0 | // Critical path first. |
418 | 0 | ResCount += (SU->getHeight() * ScaleTwo); |
419 | 0 | // Now see how many instructions is blocked by this SU. |
420 | 0 | ResCount += (NumNodesSolelyBlocking[SU->NodeNum] * ScaleTwo); |
421 | 0 | // If resources are available for it, multiply the |
422 | 0 | // chance of scheduling. |
423 | 0 | if (isResourceAvailable(SU)) |
424 | 0 | ResCount <<= FactorOne; |
425 | 0 |
|
426 | 0 | ResCount -= (regPressureDelta(SU) * ScaleTwo); |
427 | 0 | } |
428 | 0 |
|
429 | 0 | // These are platform-specific things. |
430 | 0 | // Will need to go into the back end |
431 | 0 | // and accessed from here via a hook. |
432 | 0 | for (SDNode *N = SU->getNode(); N0 ; N = N->getGluedNode()0 ) { |
433 | 0 | if (N->isMachineOpcode()0 ) { |
434 | 0 | const MCInstrDesc &TID = TII->get(N->getMachineOpcode()); |
435 | 0 | if (TID.isCall()) |
436 | 0 | ResCount += (PriorityTwo + (ScaleThree*N->getNumValues())); |
437 | 0 | } |
438 | 0 | else |
439 | 0 | switch (N->getOpcode()) { |
440 | 0 | default: break; |
441 | 0 | case ISD::TokenFactor: |
442 | 0 | case ISD::CopyFromReg: |
443 | 0 | case ISD::CopyToReg: |
444 | 0 | ResCount += PriorityFour; |
445 | 0 | break; |
446 | 0 |
|
447 | 0 | case ISD::INLINEASM: |
448 | 0 | ResCount += PriorityThree; |
449 | 0 | break; |
450 | 0 | } |
451 | 0 | } |
452 | 0 | return ResCount; |
453 | 0 | } |
454 | | |
455 | | |
456 | | /// Main resource tracking point. |
457 | 0 | void ResourcePriorityQueue::scheduledNode(SUnit *SU) { |
458 | 0 | // Use NULL entry as an event marker to reset |
459 | 0 | // the DFA state. |
460 | 0 | if (!SU0 ) { |
461 | 0 | ResourcesModel->clearResources(); |
462 | 0 | Packet.clear(); |
463 | 0 | return; |
464 | 0 | } |
465 | 0 |
|
466 | 0 | const SDNode *ScegN = SU->getNode(); |
467 | 0 | // Update reg pressure tracking. |
468 | 0 | // First update current node. |
469 | 0 | if (ScegN->isMachineOpcode()0 ) { |
470 | 0 | // Estimate generated regs. |
471 | 0 | for (unsigned i = 0, e = ScegN->getNumValues(); i != e0 ; ++i0 ) { |
472 | 0 | MVT VT = ScegN->getSimpleValueType(i); |
473 | 0 |
|
474 | 0 | if (TLI->isTypeLegal(VT)0 ) { |
475 | 0 | const TargetRegisterClass *RC = TLI->getRegClassFor(VT); |
476 | 0 | if (RC) |
477 | 0 | RegPressure[RC->getID()] += numberRCValSuccInSU(SU, RC->getID()); |
478 | 0 | } |
479 | 0 | } |
480 | 0 | // Estimate killed regs. |
481 | 0 | for (unsigned i = 0, e = ScegN->getNumOperands(); i != e0 ; ++i0 ) { |
482 | 0 | const SDValue &Op = ScegN->getOperand(i); |
483 | 0 | MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); |
484 | 0 |
|
485 | 0 | if (TLI->isTypeLegal(VT)0 ) { |
486 | 0 | const TargetRegisterClass *RC = TLI->getRegClassFor(VT); |
487 | 0 | if (RC0 ) { |
488 | 0 | if (RegPressure[RC->getID()] > |
489 | 0 | (numberRCValPredInSU(SU, RC->getID()))) |
490 | 0 | RegPressure[RC->getID()] -= numberRCValPredInSU(SU, RC->getID()); |
491 | 0 | else RegPressure[RC->getID()] = 0; |
492 | 0 | } |
493 | 0 | } |
494 | 0 | } |
495 | 0 | for (SDep &Pred : SU->Preds) { |
496 | 0 | if (Pred.isCtrl() || 0 (Pred.getSUnit()->NumRegDefsLeft == 0)0 ) |
497 | 0 | continue; |
498 | 0 | --Pred.getSUnit()->NumRegDefsLeft; |
499 | 0 | } |
500 | 0 | } |
501 | 0 |
|
502 | 0 | // Reserve resources for this SU. |
503 | 0 | reserveResources(SU); |
504 | 0 |
|
505 | 0 | // Adjust number of parallel live ranges. |
506 | 0 | // Heuristic is simple - node with no data successors reduces |
507 | 0 | // number of live ranges. All others, increase it. |
508 | 0 | unsigned NumberNonControlDeps = 0; |
509 | 0 |
|
510 | 0 | for (const SDep &Succ : SU->Succs) { |
511 | 0 | adjustPriorityOfUnscheduledPreds(Succ.getSUnit()); |
512 | 0 | if (!Succ.isCtrl()) |
513 | 0 | NumberNonControlDeps++; |
514 | 0 | } |
515 | 0 |
|
516 | 0 | if (!NumberNonControlDeps0 ) { |
517 | 0 | if (ParallelLiveRanges >= SU->NumPreds) |
518 | 0 | ParallelLiveRanges -= SU->NumPreds; |
519 | 0 | else |
520 | 0 | ParallelLiveRanges = 0; |
521 | 0 |
|
522 | 0 | } |
523 | 0 | else |
524 | 0 | ParallelLiveRanges += SU->NumRegDefsLeft; |
525 | 0 |
|
526 | 0 | // Track parallel live chains. |
527 | 0 | HorizontalVerticalBalance += (SU->Succs.size() - numberCtrlDepsInSU(SU)); |
528 | 0 | HorizontalVerticalBalance -= (SU->Preds.size() - numberCtrlPredInSU(SU)); |
529 | 0 | } |
530 | | |
531 | 0 | void ResourcePriorityQueue::initNumRegDefsLeft(SUnit *SU) { |
532 | 0 | unsigned NodeNumDefs = 0; |
533 | 0 | for (SDNode *N = SU->getNode(); N0 ; N = N->getGluedNode()0 ) |
534 | 0 | if (0 N->isMachineOpcode()0 ) { |
535 | 0 | const MCInstrDesc &TID = TII->get(N->getMachineOpcode()); |
536 | 0 | // No register need be allocated for this. |
537 | 0 | if (N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF0 ) { |
538 | 0 | NodeNumDefs = 0; |
539 | 0 | break; |
540 | 0 | } |
541 | 0 | NodeNumDefs = std::min(N->getNumValues(), TID.getNumDefs()); |
542 | 0 | } |
543 | 0 | else |
544 | 0 | switch(N->getOpcode()) { |
545 | 0 | default: break; |
546 | 0 | case ISD::CopyFromReg: |
547 | 0 | NodeNumDefs++; |
548 | 0 | break; |
549 | 0 | case ISD::INLINEASM: |
550 | 0 | NodeNumDefs++; |
551 | 0 | break; |
552 | 0 | } |
553 | 0 |
|
554 | 0 | SU->NumRegDefsLeft = NodeNumDefs; |
555 | 0 | } |
556 | | |
557 | | /// adjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just |
558 | | /// scheduled. If SU is not itself available, then there is at least one |
559 | | /// predecessor node that has not been scheduled yet. If SU has exactly ONE |
560 | | /// unscheduled predecessor, we want to increase its priority: it getting |
561 | | /// scheduled will make this node available, so it is better than some other |
562 | | /// node of the same priority that will not make a node available. |
563 | 0 | void ResourcePriorityQueue::adjustPriorityOfUnscheduledPreds(SUnit *SU) { |
564 | 0 | if (SU->isAvailable0 ) return0 ; // All preds scheduled. |
565 | 0 |
|
566 | 0 | SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); |
567 | 0 | if (!OnlyAvailablePred || 0 !OnlyAvailablePred->isAvailable0 ) |
568 | 0 | return; |
569 | 0 |
|
570 | 0 | // Okay, we found a single predecessor that is available, but not scheduled. |
571 | 0 | // Since it is available, it must be in the priority queue. First remove it. |
572 | 0 | remove(OnlyAvailablePred); |
573 | 0 |
|
574 | 0 | // Reinsert the node into the priority queue, which recomputes its |
575 | 0 | // NumNodesSolelyBlocking value. |
576 | 0 | push(OnlyAvailablePred); |
577 | 0 | } |
578 | | |
579 | | |
580 | | /// Main access point - returns next instructions |
581 | | /// to be placed in scheduling sequence. |
582 | 0 | SUnit *ResourcePriorityQueue::pop() { |
583 | 0 | if (empty()) |
584 | 0 | return nullptr; |
585 | 0 |
|
586 | 0 | std::vector<SUnit *>::iterator Best = Queue.begin(); |
587 | 0 | if (!DisableDFASched0 ) { |
588 | 0 | int BestCost = SUSchedulingCost(*Best); |
589 | 0 | for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E0 ; ++I0 ) { |
590 | 0 |
|
591 | 0 | if (SUSchedulingCost(*I) > BestCost0 ) { |
592 | 0 | BestCost = SUSchedulingCost(*I); |
593 | 0 | Best = I; |
594 | 0 | } |
595 | 0 | } |
596 | 0 | } |
597 | 0 | // Use default TD scheduling mechanism. |
598 | 0 | else { |
599 | 0 | for (auto I = std::next(Queue.begin()), E = Queue.end(); I != E0 ; ++I0 ) |
600 | 0 | if (0 Picker(*Best, *I)0 ) |
601 | 0 | Best = I; |
602 | 0 | } |
603 | 0 |
|
604 | 0 | SUnit *V = *Best; |
605 | 0 | if (Best != std::prev(Queue.end())) |
606 | 0 | std::swap(*Best, Queue.back()); |
607 | 0 |
|
608 | 0 | Queue.pop_back(); |
609 | 0 |
|
610 | 0 | return V; |
611 | 0 | } |
612 | | |
613 | | |
614 | 0 | void ResourcePriorityQueue::remove(SUnit *SU) { |
615 | 0 | assert(!Queue.empty() && "Queue is empty!"); |
616 | 0 | std::vector<SUnit *>::iterator I = find(Queue, SU); |
617 | 0 | if (I != std::prev(Queue.end())) |
618 | 0 | std::swap(*I, Queue.back()); |
619 | 0 |
|
620 | 0 | Queue.pop_back(); |
621 | 0 | } |