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