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 #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 }
    640