Home | History | Annotate | Download | only in Hexagon
      1 //===- HexagonMachineScheduler.cpp - MI Scheduler for Hexagon -------------===//
      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 // MachineScheduler schedules machine instructions after phi elimination. It
     11 // preserves LiveIntervals so it can be invoked before register allocation.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "HexagonMachineScheduler.h"
     16 #include "llvm/CodeGen/MachineLoopInfo.h"
     17 #include "llvm/IR/Function.h"
     18 
     19 using namespace llvm;
     20 
     21 #define DEBUG_TYPE "misched"
     22 
     23 /// Platform-specific modifications to DAG.
     24 void VLIWMachineScheduler::postprocessDAG() {
     25   SUnit* LastSequentialCall = nullptr;
     26   // Currently we only catch the situation when compare gets scheduled
     27   // before preceding call.
     28   for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
     29     // Remember the call.
     30     if (SUnits[su].getInstr()->isCall())
     31       LastSequentialCall = &(SUnits[su]);
     32     // Look for a compare that defines a predicate.
     33     else if (SUnits[su].getInstr()->isCompare() && LastSequentialCall)
     34       SUnits[su].addPred(SDep(LastSequentialCall, SDep::Barrier));
     35   }
     36 }
     37 
     38 /// Check if scheduling of this SU is possible
     39 /// in the current packet.
     40 /// It is _not_ precise (statefull), it is more like
     41 /// another heuristic. Many corner cases are figured
     42 /// empirically.
     43 bool VLIWResourceModel::isResourceAvailable(SUnit *SU) {
     44   if (!SU || !SU->getInstr())
     45     return false;
     46 
     47   // First see if the pipeline could receive this instruction
     48   // in the current cycle.
     49   switch (SU->getInstr()->getOpcode()) {
     50   default:
     51     if (!ResourcesModel->canReserveResources(SU->getInstr()))
     52       return false;
     53   case TargetOpcode::EXTRACT_SUBREG:
     54   case TargetOpcode::INSERT_SUBREG:
     55   case TargetOpcode::SUBREG_TO_REG:
     56   case TargetOpcode::REG_SEQUENCE:
     57   case TargetOpcode::IMPLICIT_DEF:
     58   case TargetOpcode::COPY:
     59   case TargetOpcode::INLINEASM:
     60     break;
     61   }
     62 
     63   // Now see if there are no other dependencies to instructions already
     64   // in the packet.
     65   for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
     66     if (Packet[i]->Succs.size() == 0)
     67       continue;
     68     for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(),
     69          E = Packet[i]->Succs.end(); I != E; ++I) {
     70       // Since we do not add pseudos to packets, might as well
     71       // ignore order dependencies.
     72       if (I->isCtrl())
     73         continue;
     74 
     75       if (I->getSUnit() == SU)
     76         return false;
     77     }
     78   }
     79   return true;
     80 }
     81 
     82 /// Keep track of available resources.
     83 bool VLIWResourceModel::reserveResources(SUnit *SU) {
     84   bool startNewCycle = false;
     85   // Artificially reset state.
     86   if (!SU) {
     87     ResourcesModel->clearResources();
     88     Packet.clear();
     89     TotalPackets++;
     90     return false;
     91   }
     92   // If this SU does not fit in the packet
     93   // start a new one.
     94   if (!isResourceAvailable(SU)) {
     95     ResourcesModel->clearResources();
     96     Packet.clear();
     97     TotalPackets++;
     98     startNewCycle = true;
     99   }
    100 
    101   switch (SU->getInstr()->getOpcode()) {
    102   default:
    103     ResourcesModel->reserveResources(SU->getInstr());
    104     break;
    105   case TargetOpcode::EXTRACT_SUBREG:
    106   case TargetOpcode::INSERT_SUBREG:
    107   case TargetOpcode::SUBREG_TO_REG:
    108   case TargetOpcode::REG_SEQUENCE:
    109   case TargetOpcode::IMPLICIT_DEF:
    110   case TargetOpcode::KILL:
    111   case TargetOpcode::CFI_INSTRUCTION:
    112   case TargetOpcode::EH_LABEL:
    113   case TargetOpcode::COPY:
    114   case TargetOpcode::INLINEASM:
    115     break;
    116   }
    117   Packet.push_back(SU);
    118 
    119 #ifndef NDEBUG
    120   DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
    121   for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
    122     DEBUG(dbgs() << "\t[" << i << "] SU(");
    123     DEBUG(dbgs() << Packet[i]->NodeNum << ")\t");
    124     DEBUG(Packet[i]->getInstr()->dump());
    125   }
    126 #endif
    127 
    128   // If packet is now full, reset the state so in the next cycle
    129   // we start fresh.
    130   if (Packet.size() >= SchedModel->getIssueWidth()) {
    131     ResourcesModel->clearResources();
    132     Packet.clear();
    133     TotalPackets++;
    134     startNewCycle = true;
    135   }
    136 
    137   return startNewCycle;
    138 }
    139 
    140 /// schedule - Called back from MachineScheduler::runOnMachineFunction
    141 /// after setting up the current scheduling region. [RegionBegin, RegionEnd)
    142 /// only includes instructions that have DAG nodes, not scheduling boundaries.
    143 void VLIWMachineScheduler::schedule() {
    144   DEBUG(dbgs()
    145         << "********** MI Converging Scheduling VLIW BB#" << BB->getNumber()
    146         << " " << BB->getName()
    147         << " in_func " << BB->getParent()->getFunction()->getName()
    148         << " at loop depth "  << MLI->getLoopDepth(BB)
    149         << " \n");
    150 
    151   buildDAGWithRegPressure();
    152 
    153   // Postprocess the DAG to add platform-specific artificial dependencies.
    154   postprocessDAG();
    155 
    156   SmallVector<SUnit*, 8> TopRoots, BotRoots;
    157   findRootsAndBiasEdges(TopRoots, BotRoots);
    158 
    159   // Initialize the strategy before modifying the DAG.
    160   SchedImpl->initialize(this);
    161 
    162   // To view Height/Depth correctly, they should be accessed at least once.
    163   //
    164   // FIXME: SUnit::dumpAll always recompute depth and height now. The max
    165   // depth/height could be computed directly from the roots and leaves.
    166   DEBUG(unsigned maxH = 0;
    167         for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
    168           if (SUnits[su].getHeight() > maxH)
    169             maxH = SUnits[su].getHeight();
    170         dbgs() << "Max Height " << maxH << "\n";);
    171   DEBUG(unsigned maxD = 0;
    172         for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
    173           if (SUnits[su].getDepth() > maxD)
    174             maxD = SUnits[su].getDepth();
    175         dbgs() << "Max Depth " << maxD << "\n";);
    176   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
    177           SUnits[su].dumpAll(this));
    178 
    179   initQueues(TopRoots, BotRoots);
    180 
    181   bool IsTopNode = false;
    182   while (true) {
    183     DEBUG(dbgs() << "** VLIWMachineScheduler::schedule picking next node\n");
    184     SUnit *SU = SchedImpl->pickNode(IsTopNode);
    185     if (!SU) break;
    186 
    187     if (!checkSchedLimit())
    188       break;
    189 
    190     scheduleMI(SU, IsTopNode);
    191 
    192     updateQueues(SU, IsTopNode);
    193 
    194     // Notify the scheduling strategy after updating the DAG.
    195     SchedImpl->schedNode(SU, IsTopNode);
    196   }
    197   assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
    198 
    199   placeDebugValues();
    200 }
    201 
    202 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
    203   DAG = static_cast<VLIWMachineScheduler*>(dag);
    204   SchedModel = DAG->getSchedModel();
    205 
    206   Top.init(DAG, SchedModel);
    207   Bot.init(DAG, SchedModel);
    208 
    209   // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
    210   // are disabled, then these HazardRecs will be disabled.
    211   const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
    212   const TargetSubtargetInfo &STI = DAG->MF.getSubtarget();
    213   const TargetInstrInfo *TII = STI.getInstrInfo();
    214   delete Top.HazardRec;
    215   delete Bot.HazardRec;
    216   Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
    217   Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
    218 
    219   delete Top.ResourceModel;
    220   delete Bot.ResourceModel;
    221   Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
    222   Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
    223 
    224   assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) &&
    225          "-misched-topdown incompatible with -misched-bottomup");
    226 }
    227 
    228 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
    229   if (SU->isScheduled)
    230     return;
    231 
    232   for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
    233        I != E; ++I) {
    234     unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
    235     unsigned MinLatency = I->getLatency();
    236 #ifndef NDEBUG
    237     Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
    238 #endif
    239     if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
    240       SU->TopReadyCycle = PredReadyCycle + MinLatency;
    241   }
    242   Top.releaseNode(SU, SU->TopReadyCycle);
    243 }
    244 
    245 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
    246   if (SU->isScheduled)
    247     return;
    248 
    249   assert(SU->getInstr() && "Scheduled SUnit must have instr");
    250 
    251   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
    252        I != E; ++I) {
    253     unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
    254     unsigned MinLatency = I->getLatency();
    255 #ifndef NDEBUG
    256     Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
    257 #endif
    258     if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
    259       SU->BotReadyCycle = SuccReadyCycle + MinLatency;
    260   }
    261   Bot.releaseNode(SU, SU->BotReadyCycle);
    262 }
    263 
    264 /// Does this SU have a hazard within the current instruction group.
    265 ///
    266 /// The scheduler supports two modes of hazard recognition. The first is the
    267 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
    268 /// supports highly complicated in-order reservation tables
    269 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
    270 ///
    271 /// The second is a streamlined mechanism that checks for hazards based on
    272 /// simple counters that the scheduler itself maintains. It explicitly checks
    273 /// for instruction dispatch limitations, including the number of micro-ops that
    274 /// can dispatch per cycle.
    275 ///
    276 /// TODO: Also check whether the SU must start a new group.
    277 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) {
    278   if (HazardRec->isEnabled())
    279     return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
    280 
    281   unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
    282   if (IssueCount + uops > SchedModel->getIssueWidth())
    283     return true;
    284 
    285   return false;
    286 }
    287 
    288 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU,
    289                                                      unsigned ReadyCycle) {
    290   if (ReadyCycle < MinReadyCycle)
    291     MinReadyCycle = ReadyCycle;
    292 
    293   // Check for interlocks first. For the purpose of other heuristics, an
    294   // instruction that cannot issue appears as if it's not in the ReadyQueue.
    295   if (ReadyCycle > CurrCycle || checkHazard(SU))
    296 
    297     Pending.push(SU);
    298   else
    299     Available.push(SU);
    300 }
    301 
    302 /// Move the boundary of scheduled code by one cycle.
    303 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
    304   unsigned Width = SchedModel->getIssueWidth();
    305   IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
    306 
    307   assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
    308   unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
    309 
    310   if (!HazardRec->isEnabled()) {
    311     // Bypass HazardRec virtual calls.
    312     CurrCycle = NextCycle;
    313   } else {
    314     // Bypass getHazardType calls in case of long latency.
    315     for (; CurrCycle != NextCycle; ++CurrCycle) {
    316       if (isTop())
    317         HazardRec->AdvanceCycle();
    318       else
    319         HazardRec->RecedeCycle();
    320     }
    321   }
    322   CheckPending = true;
    323 
    324   DEBUG(dbgs() << "*** " << Available.getName() << " cycle "
    325         << CurrCycle << '\n');
    326 }
    327 
    328 /// Move the boundary of scheduled code by one SUnit.
    329 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) {
    330   bool startNewCycle = false;
    331 
    332   // Update the reservation table.
    333   if (HazardRec->isEnabled()) {
    334     if (!isTop() && SU->isCall) {
    335       // Calls are scheduled with their preceding instructions. For bottom-up
    336       // scheduling, clear the pipeline state before emitting.
    337       HazardRec->Reset();
    338     }
    339     HazardRec->EmitInstruction(SU);
    340   }
    341 
    342   // Update DFA model.
    343   startNewCycle = ResourceModel->reserveResources(SU);
    344 
    345   // Check the instruction group dispatch limit.
    346   // TODO: Check if this SU must end a dispatch group.
    347   IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
    348   if (startNewCycle) {
    349     DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
    350     bumpCycle();
    351   }
    352   else
    353     DEBUG(dbgs() << "*** IssueCount " << IssueCount
    354           << " at cycle " << CurrCycle << '\n');
    355 }
    356 
    357 /// Release pending ready nodes in to the available queue. This makes them
    358 /// visible to heuristics.
    359 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
    360   // If the available queue is empty, it is safe to reset MinReadyCycle.
    361   if (Available.empty())
    362     MinReadyCycle = UINT_MAX;
    363 
    364   // Check to see if any of the pending instructions are ready to issue.  If
    365   // so, add them to the available queue.
    366   for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
    367     SUnit *SU = *(Pending.begin()+i);
    368     unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
    369 
    370     if (ReadyCycle < MinReadyCycle)
    371       MinReadyCycle = ReadyCycle;
    372 
    373     if (ReadyCycle > CurrCycle)
    374       continue;
    375 
    376     if (checkHazard(SU))
    377       continue;
    378 
    379     Available.push(SU);
    380     Pending.remove(Pending.begin()+i);
    381     --i; --e;
    382   }
    383   CheckPending = false;
    384 }
    385 
    386 /// Remove SU from the ready set for this boundary.
    387 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) {
    388   if (Available.isInQueue(SU))
    389     Available.remove(Available.find(SU));
    390   else {
    391     assert(Pending.isInQueue(SU) && "bad ready count");
    392     Pending.remove(Pending.find(SU));
    393   }
    394 }
    395 
    396 /// If this queue only has one ready candidate, return it. As a side effect,
    397 /// advance the cycle until at least one node is ready. If multiple instructions
    398 /// are ready, return NULL.
    399 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
    400   if (CheckPending)
    401     releasePending();
    402 
    403   for (unsigned i = 0; Available.empty(); ++i) {
    404     assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
    405            "permanent hazard"); (void)i;
    406     ResourceModel->reserveResources(nullptr);
    407     bumpCycle();
    408     releasePending();
    409   }
    410   if (Available.size() == 1)
    411     return *Available.begin();
    412   return nullptr;
    413 }
    414 
    415 #ifndef NDEBUG
    416 void ConvergingVLIWScheduler::traceCandidate(const char *Label,
    417                                              const ReadyQueue &Q,
    418                                              SUnit *SU, PressureChange P) {
    419   dbgs() << Label << " " << Q.getName() << " ";
    420   if (P.isValid())
    421     dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
    422            << P.getUnitInc() << " ";
    423   else
    424     dbgs() << "     ";
    425   SU->dump(DAG);
    426 }
    427 #endif
    428 
    429 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
    430 /// of SU, return it, otherwise return null.
    431 static SUnit *getSingleUnscheduledPred(SUnit *SU) {
    432   SUnit *OnlyAvailablePred = nullptr;
    433   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
    434        I != E; ++I) {
    435     SUnit &Pred = *I->getSUnit();
    436     if (!Pred.isScheduled) {
    437       // We found an available, but not scheduled, predecessor.  If it's the
    438       // only one we have found, keep track of it... otherwise give up.
    439       if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
    440         return nullptr;
    441       OnlyAvailablePred = &Pred;
    442     }
    443   }
    444   return OnlyAvailablePred;
    445 }
    446 
    447 /// getSingleUnscheduledSucc - If there is exactly one unscheduled successor
    448 /// of SU, return it, otherwise return null.
    449 static SUnit *getSingleUnscheduledSucc(SUnit *SU) {
    450   SUnit *OnlyAvailableSucc = nullptr;
    451   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
    452        I != E; ++I) {
    453     SUnit &Succ = *I->getSUnit();
    454     if (!Succ.isScheduled) {
    455       // We found an available, but not scheduled, successor.  If it's the
    456       // only one we have found, keep track of it... otherwise give up.
    457       if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ)
    458         return nullptr;
    459       OnlyAvailableSucc = &Succ;
    460     }
    461   }
    462   return OnlyAvailableSucc;
    463 }
    464 
    465 // Constants used to denote relative importance of
    466 // heuristic components for cost computation.
    467 static const unsigned PriorityOne = 200;
    468 static const unsigned PriorityTwo = 50;
    469 static const unsigned ScaleTwo = 10;
    470 static const unsigned FactorOne = 2;
    471 
    472 /// Single point to compute overall scheduling cost.
    473 /// TODO: More heuristics will be used soon.
    474 int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
    475                                             SchedCandidate &Candidate,
    476                                             RegPressureDelta &Delta,
    477                                             bool verbose) {
    478   // Initial trivial priority.
    479   int ResCount = 1;
    480 
    481   // Do not waste time on a node that is already scheduled.
    482   if (!SU || SU->isScheduled)
    483     return ResCount;
    484 
    485   // Forced priority is high.
    486   if (SU->isScheduleHigh)
    487     ResCount += PriorityOne;
    488 
    489   // Critical path first.
    490   if (Q.getID() == TopQID) {
    491     ResCount += (SU->getHeight() * ScaleTwo);
    492 
    493     // If resources are available for it, multiply the
    494     // chance of scheduling.
    495     if (Top.ResourceModel->isResourceAvailable(SU))
    496       ResCount <<= FactorOne;
    497   } else {
    498     ResCount += (SU->getDepth() * ScaleTwo);
    499 
    500     // If resources are available for it, multiply the
    501     // chance of scheduling.
    502     if (Bot.ResourceModel->isResourceAvailable(SU))
    503       ResCount <<= FactorOne;
    504   }
    505 
    506   unsigned NumNodesBlocking = 0;
    507   if (Q.getID() == TopQID) {
    508     // How many SUs does it block from scheduling?
    509     // Look at all of the successors of this node.
    510     // Count the number of nodes that
    511     // this node is the sole unscheduled node for.
    512     for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
    513          I != E; ++I)
    514       if (getSingleUnscheduledPred(I->getSUnit()) == SU)
    515         ++NumNodesBlocking;
    516   } else {
    517     // How many unscheduled predecessors block this node?
    518     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
    519          I != E; ++I)
    520       if (getSingleUnscheduledSucc(I->getSUnit()) == SU)
    521         ++NumNodesBlocking;
    522   }
    523   ResCount += (NumNodesBlocking * ScaleTwo);
    524 
    525   // Factor in reg pressure as a heuristic.
    526   ResCount -= (Delta.Excess.getUnitInc()*PriorityTwo);
    527   ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityTwo);
    528 
    529   DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")");
    530 
    531   return ResCount;
    532 }
    533 
    534 /// Pick the best candidate from the top queue.
    535 ///
    536 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
    537 /// DAG building. To adjust for the current scheduling location we need to
    538 /// maintain the number of vreg uses remaining to be top-scheduled.
    539 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
    540 pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
    541                   SchedCandidate &Candidate) {
    542   DEBUG(Q.dump());
    543 
    544   // getMaxPressureDelta temporarily modifies the tracker.
    545   RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
    546 
    547   // BestSU remains NULL if no top candidates beat the best existing candidate.
    548   CandResult FoundCandidate = NoCand;
    549   for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
    550     RegPressureDelta RPDelta;
    551     TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
    552                                     DAG->getRegionCriticalPSets(),
    553                                     DAG->getRegPressure().MaxSetPressure);
    554 
    555     int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
    556 
    557     // Initialize the candidate if needed.
    558     if (!Candidate.SU) {
    559       Candidate.SU = *I;
    560       Candidate.RPDelta = RPDelta;
    561       Candidate.SCost = CurrentCost;
    562       FoundCandidate = NodeOrder;
    563       continue;
    564     }
    565 
    566     // Best cost.
    567     if (CurrentCost > Candidate.SCost) {
    568       DEBUG(traceCandidate("CCAND", Q, *I));
    569       Candidate.SU = *I;
    570       Candidate.RPDelta = RPDelta;
    571       Candidate.SCost = CurrentCost;
    572       FoundCandidate = BestCost;
    573       continue;
    574     }
    575 
    576     // Fall through to original instruction order.
    577     // Only consider node order if Candidate was chosen from this Q.
    578     if (FoundCandidate == NoCand)
    579       continue;
    580   }
    581   return FoundCandidate;
    582 }
    583 
    584 /// Pick the best candidate node from either the top or bottom queue.
    585 SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) {
    586   // Schedule as far as possible in the direction of no choice. This is most
    587   // efficient, but also provides the best heuristics for CriticalPSets.
    588   if (SUnit *SU = Bot.pickOnlyChoice()) {
    589     IsTopNode = false;
    590     return SU;
    591   }
    592   if (SUnit *SU = Top.pickOnlyChoice()) {
    593     IsTopNode = true;
    594     return SU;
    595   }
    596   SchedCandidate BotCand;
    597   // Prefer bottom scheduling when heuristics are silent.
    598   CandResult BotResult = pickNodeFromQueue(Bot.Available,
    599                                            DAG->getBotRPTracker(), BotCand);
    600   assert(BotResult != NoCand && "failed to find the first candidate");
    601 
    602   // If either Q has a single candidate that provides the least increase in
    603   // Excess pressure, we can immediately schedule from that Q.
    604   //
    605   // RegionCriticalPSets summarizes the pressure within the scheduled region and
    606   // affects picking from either Q. If scheduling in one direction must
    607   // increase pressure for one of the excess PSets, then schedule in that
    608   // direction first to provide more freedom in the other direction.
    609   if (BotResult == SingleExcess || BotResult == SingleCritical) {
    610     IsTopNode = false;
    611     return BotCand.SU;
    612   }
    613   // Check if the top Q has a better candidate.
    614   SchedCandidate TopCand;
    615   CandResult TopResult = pickNodeFromQueue(Top.Available,
    616                                            DAG->getTopRPTracker(), TopCand);
    617   assert(TopResult != NoCand && "failed to find the first candidate");
    618 
    619   if (TopResult == SingleExcess || TopResult == SingleCritical) {
    620     IsTopNode = true;
    621     return TopCand.SU;
    622   }
    623   // If either Q has a single candidate that minimizes pressure above the
    624   // original region's pressure pick it.
    625   if (BotResult == SingleMax) {
    626     IsTopNode = false;
    627     return BotCand.SU;
    628   }
    629   if (TopResult == SingleMax) {
    630     IsTopNode = true;
    631     return TopCand.SU;
    632   }
    633   if (TopCand.SCost > BotCand.SCost) {
    634     IsTopNode = true;
    635     return TopCand.SU;
    636   }
    637   // Otherwise prefer the bottom candidate in node order.
    638   IsTopNode = false;
    639   return BotCand.SU;
    640 }
    641 
    642 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
    643 SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
    644   if (DAG->top() == DAG->bottom()) {
    645     assert(Top.Available.empty() && Top.Pending.empty() &&
    646            Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
    647     return nullptr;
    648   }
    649   SUnit *SU;
    650   if (llvm::ForceTopDown) {
    651     SU = Top.pickOnlyChoice();
    652     if (!SU) {
    653       SchedCandidate TopCand;
    654       CandResult TopResult =
    655         pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
    656       assert(TopResult != NoCand && "failed to find the first candidate");
    657       (void)TopResult;
    658       SU = TopCand.SU;
    659     }
    660     IsTopNode = true;
    661   } else if (llvm::ForceBottomUp) {
    662     SU = Bot.pickOnlyChoice();
    663     if (!SU) {
    664       SchedCandidate BotCand;
    665       CandResult BotResult =
    666         pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
    667       assert(BotResult != NoCand && "failed to find the first candidate");
    668       (void)BotResult;
    669       SU = BotCand.SU;
    670     }
    671     IsTopNode = false;
    672   } else {
    673     SU = pickNodeBidrectional(IsTopNode);
    674   }
    675   if (SU->isTopReady())
    676     Top.removeReady(SU);
    677   if (SU->isBottomReady())
    678     Bot.removeReady(SU);
    679 
    680   DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
    681         << " Scheduling Instruction in cycle "
    682         << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
    683         SU->dump(DAG));
    684   return SU;
    685 }
    686 
    687 /// Update the scheduler's state after scheduling a node. This is the same node
    688 /// that was just returned by pickNode(). However, VLIWMachineScheduler needs
    689 /// to update it's state based on the current cycle before MachineSchedStrategy
    690 /// does.
    691 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
    692   if (IsTopNode) {
    693     SU->TopReadyCycle = Top.CurrCycle;
    694     Top.bumpNode(SU);
    695   } else {
    696     SU->BotReadyCycle = Bot.CurrCycle;
    697     Bot.bumpNode(SU);
    698   }
    699 }
    700