lib/CodeGen/SelectionDAG/ResourcePriorityQueue.cpp

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