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