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