Home | History | Annotate | Download | only in SelectionDAG 
      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
    656