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