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/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<signed> 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 (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
  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
 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
 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
 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 ///
 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.
 181 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.
 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
 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.
 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.
 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
 326 signed ResourcePriorityQueue::rawRegPressureDelta(SUnit *SU, unsigned RCId) {
 327   signed 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.
 360 signed ResourcePriorityQueue::regPressureDelta(SUnit *SU, bool RawPressure) {
 361   signed 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.
 401 signed ResourcePriorityQueue::SUSchedulingCost(SUnit *SU) {
 402   // Initial trivial priority.
 403   signed 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.
 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
 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.
 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.
 598 SUnit *ResourcePriorityQueue::pop() {
 599   if (empty())
 600     return nullptr;
 601
 602   std::vector<SUnit *>::iterator Best = Queue.begin();
 603   if (!DisableDFASched) {
 604     signed 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
 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 }