LLVM  mainline
HexagonMachineScheduler.cpp
Go to the documentation of this file.
00001 //===- HexagonMachineScheduler.cpp - MI Scheduler for Hexagon -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // MachineScheduler schedules machine instructions after phi elimination. It
00011 // preserves LiveIntervals so it can be invoked before register allocation.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "HexagonMachineScheduler.h"
00016 #include "llvm/CodeGen/MachineLoopInfo.h"
00017 #include "llvm/IR/Function.h"
00018 
00019 using namespace llvm;
00020 
00021 #define DEBUG_TYPE "misched"
00022 
00023 /// Platform-specific modifications to DAG.
00024 void VLIWMachineScheduler::postprocessDAG() {
00025   SUnit* LastSequentialCall = nullptr;
00026   // Currently we only catch the situation when compare gets scheduled
00027   // before preceding call.
00028   for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
00029     // Remember the call.
00030     if (SUnits[su].getInstr()->isCall())
00031       LastSequentialCall = &(SUnits[su]);
00032     // Look for a compare that defines a predicate.
00033     else if (SUnits[su].getInstr()->isCompare() && LastSequentialCall)
00034       SUnits[su].addPred(SDep(LastSequentialCall, SDep::Barrier));
00035   }
00036 }
00037 
00038 /// Check if scheduling of this SU is possible
00039 /// in the current packet.
00040 /// It is _not_ precise (statefull), it is more like
00041 /// another heuristic. Many corner cases are figured
00042 /// empirically.
00043 bool VLIWResourceModel::isResourceAvailable(SUnit *SU) {
00044   if (!SU || !SU->getInstr())
00045     return false;
00046 
00047   // First see if the pipeline could receive this instruction
00048   // in the current cycle.
00049   switch (SU->getInstr()->getOpcode()) {
00050   default:
00051     if (!ResourcesModel->canReserveResources(SU->getInstr()))
00052       return false;
00053   case TargetOpcode::EXTRACT_SUBREG:
00054   case TargetOpcode::INSERT_SUBREG:
00055   case TargetOpcode::SUBREG_TO_REG:
00056   case TargetOpcode::REG_SEQUENCE:
00057   case TargetOpcode::IMPLICIT_DEF:
00058   case TargetOpcode::COPY:
00059   case TargetOpcode::INLINEASM:
00060     break;
00061   }
00062 
00063   // Now see if there are no other dependencies to instructions already
00064   // in the packet.
00065   for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
00066     if (Packet[i]->Succs.size() == 0)
00067       continue;
00068     for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(),
00069          E = Packet[i]->Succs.end(); I != E; ++I) {
00070       // Since we do not add pseudos to packets, might as well
00071       // ignore order dependencies.
00072       if (I->isCtrl())
00073         continue;
00074 
00075       if (I->getSUnit() == SU)
00076         return false;
00077     }
00078   }
00079   return true;
00080 }
00081 
00082 /// Keep track of available resources.
00083 bool VLIWResourceModel::reserveResources(SUnit *SU) {
00084   bool startNewCycle = false;
00085   // Artificially reset state.
00086   if (!SU) {
00087     ResourcesModel->clearResources();
00088     Packet.clear();
00089     TotalPackets++;
00090     return false;
00091   }
00092   // If this SU does not fit in the packet
00093   // start a new one.
00094   if (!isResourceAvailable(SU)) {
00095     ResourcesModel->clearResources();
00096     Packet.clear();
00097     TotalPackets++;
00098     startNewCycle = true;
00099   }
00100 
00101   switch (SU->getInstr()->getOpcode()) {
00102   default:
00103     ResourcesModel->reserveResources(SU->getInstr());
00104     break;
00105   case TargetOpcode::EXTRACT_SUBREG:
00106   case TargetOpcode::INSERT_SUBREG:
00107   case TargetOpcode::SUBREG_TO_REG:
00108   case TargetOpcode::REG_SEQUENCE:
00109   case TargetOpcode::IMPLICIT_DEF:
00110   case TargetOpcode::KILL:
00111   case TargetOpcode::CFI_INSTRUCTION:
00112   case TargetOpcode::EH_LABEL:
00113   case TargetOpcode::COPY:
00114   case TargetOpcode::INLINEASM:
00115     break;
00116   }
00117   Packet.push_back(SU);
00118 
00119 #ifndef NDEBUG
00120   DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
00121   for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
00122     DEBUG(dbgs() << "\t[" << i << "] SU(");
00123     DEBUG(dbgs() << Packet[i]->NodeNum << ")\t");
00124     DEBUG(Packet[i]->getInstr()->dump());
00125   }
00126 #endif
00127 
00128   // If packet is now full, reset the state so in the next cycle
00129   // we start fresh.
00130   if (Packet.size() >= SchedModel->getIssueWidth()) {
00131     ResourcesModel->clearResources();
00132     Packet.clear();
00133     TotalPackets++;
00134     startNewCycle = true;
00135   }
00136 
00137   return startNewCycle;
00138 }
00139 
00140 /// schedule - Called back from MachineScheduler::runOnMachineFunction
00141 /// after setting up the current scheduling region. [RegionBegin, RegionEnd)
00142 /// only includes instructions that have DAG nodes, not scheduling boundaries.
00143 void VLIWMachineScheduler::schedule() {
00144   DEBUG(dbgs()
00145         << "********** MI Converging Scheduling VLIW BB#" << BB->getNumber()
00146         << " " << BB->getName()
00147         << " in_func " << BB->getParent()->getFunction()->getName()
00148         << " at loop depth "  << MLI->getLoopDepth(BB)
00149         << " \n");
00150 
00151   buildDAGWithRegPressure();
00152 
00153   // Postprocess the DAG to add platform-specific artificial dependencies.
00154   postprocessDAG();
00155 
00156   SmallVector<SUnit*, 8> TopRoots, BotRoots;
00157   findRootsAndBiasEdges(TopRoots, BotRoots);
00158 
00159   // Initialize the strategy before modifying the DAG.
00160   SchedImpl->initialize(this);
00161 
00162   // To view Height/Depth correctly, they should be accessed at least once.
00163   //
00164   // FIXME: SUnit::dumpAll always recompute depth and height now. The max
00165   // depth/height could be computed directly from the roots and leaves.
00166   DEBUG(unsigned maxH = 0;
00167         for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
00168           if (SUnits[su].getHeight() > maxH)
00169             maxH = SUnits[su].getHeight();
00170         dbgs() << "Max Height " << maxH << "\n";);
00171   DEBUG(unsigned maxD = 0;
00172         for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
00173           if (SUnits[su].getDepth() > maxD)
00174             maxD = SUnits[su].getDepth();
00175         dbgs() << "Max Depth " << maxD << "\n";);
00176   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
00177           SUnits[su].dumpAll(this));
00178 
00179   initQueues(TopRoots, BotRoots);
00180 
00181   bool IsTopNode = false;
00182   while (true) {
00183     DEBUG(dbgs() << "** VLIWMachineScheduler::schedule picking next node\n");
00184     SUnit *SU = SchedImpl->pickNode(IsTopNode);
00185     if (!SU) break;
00186 
00187     if (!checkSchedLimit())
00188       break;
00189 
00190     scheduleMI(SU, IsTopNode);
00191 
00192     updateQueues(SU, IsTopNode);
00193 
00194     // Notify the scheduling strategy after updating the DAG.
00195     SchedImpl->schedNode(SU, IsTopNode);
00196   }
00197   assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
00198 
00199   placeDebugValues();
00200 }
00201 
00202 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
00203   DAG = static_cast<VLIWMachineScheduler*>(dag);
00204   SchedModel = DAG->getSchedModel();
00205 
00206   Top.init(DAG, SchedModel);
00207   Bot.init(DAG, SchedModel);
00208 
00209   // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
00210   // are disabled, then these HazardRecs will be disabled.
00211   const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
00212   const TargetSubtargetInfo &STI = DAG->MF.getSubtarget();
00213   const TargetInstrInfo *TII = STI.getInstrInfo();
00214   delete Top.HazardRec;
00215   delete Bot.HazardRec;
00216   Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
00217   Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
00218 
00219   delete Top.ResourceModel;
00220   delete Bot.ResourceModel;
00221   Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
00222   Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
00223 
00224   assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) &&
00225          "-misched-topdown incompatible with -misched-bottomup");
00226 }
00227 
00228 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
00229   if (SU->isScheduled)
00230     return;
00231 
00232   for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00233        I != E; ++I) {
00234     unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
00235     unsigned MinLatency = I->getLatency();
00236 #ifndef NDEBUG
00237     Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
00238 #endif
00239     if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
00240       SU->TopReadyCycle = PredReadyCycle + MinLatency;
00241   }
00242   Top.releaseNode(SU, SU->TopReadyCycle);
00243 }
00244 
00245 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
00246   if (SU->isScheduled)
00247     return;
00248 
00249   assert(SU->getInstr() && "Scheduled SUnit must have instr");
00250 
00251   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00252        I != E; ++I) {
00253     unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
00254     unsigned MinLatency = I->getLatency();
00255 #ifndef NDEBUG
00256     Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
00257 #endif
00258     if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
00259       SU->BotReadyCycle = SuccReadyCycle + MinLatency;
00260   }
00261   Bot.releaseNode(SU, SU->BotReadyCycle);
00262 }
00263 
00264 /// Does this SU have a hazard within the current instruction group.
00265 ///
00266 /// The scheduler supports two modes of hazard recognition. The first is the
00267 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
00268 /// supports highly complicated in-order reservation tables
00269 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
00270 ///
00271 /// The second is a streamlined mechanism that checks for hazards based on
00272 /// simple counters that the scheduler itself maintains. It explicitly checks
00273 /// for instruction dispatch limitations, including the number of micro-ops that
00274 /// can dispatch per cycle.
00275 ///
00276 /// TODO: Also check whether the SU must start a new group.
00277 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) {
00278   if (HazardRec->isEnabled())
00279     return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
00280 
00281   unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
00282   if (IssueCount + uops > SchedModel->getIssueWidth())
00283     return true;
00284 
00285   return false;
00286 }
00287 
00288 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU,
00289                                                      unsigned ReadyCycle) {
00290   if (ReadyCycle < MinReadyCycle)
00291     MinReadyCycle = ReadyCycle;
00292 
00293   // Check for interlocks first. For the purpose of other heuristics, an
00294   // instruction that cannot issue appears as if it's not in the ReadyQueue.
00295   if (ReadyCycle > CurrCycle || checkHazard(SU))
00296 
00297     Pending.push(SU);
00298   else
00299     Available.push(SU);
00300 }
00301 
00302 /// Move the boundary of scheduled code by one cycle.
00303 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
00304   unsigned Width = SchedModel->getIssueWidth();
00305   IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
00306 
00307   assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
00308   unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
00309 
00310   if (!HazardRec->isEnabled()) {
00311     // Bypass HazardRec virtual calls.
00312     CurrCycle = NextCycle;
00313   } else {
00314     // Bypass getHazardType calls in case of long latency.
00315     for (; CurrCycle != NextCycle; ++CurrCycle) {
00316       if (isTop())
00317         HazardRec->AdvanceCycle();
00318       else
00319         HazardRec->RecedeCycle();
00320     }
00321   }
00322   CheckPending = true;
00323 
00324   DEBUG(dbgs() << "*** " << Available.getName() << " cycle "
00325         << CurrCycle << '\n');
00326 }
00327 
00328 /// Move the boundary of scheduled code by one SUnit.
00329 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) {
00330   bool startNewCycle = false;
00331 
00332   // Update the reservation table.
00333   if (HazardRec->isEnabled()) {
00334     if (!isTop() && SU->isCall) {
00335       // Calls are scheduled with their preceding instructions. For bottom-up
00336       // scheduling, clear the pipeline state before emitting.
00337       HazardRec->Reset();
00338     }
00339     HazardRec->EmitInstruction(SU);
00340   }
00341 
00342   // Update DFA model.
00343   startNewCycle = ResourceModel->reserveResources(SU);
00344 
00345   // Check the instruction group dispatch limit.
00346   // TODO: Check if this SU must end a dispatch group.
00347   IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
00348   if (startNewCycle) {
00349     DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
00350     bumpCycle();
00351   }
00352   else
00353     DEBUG(dbgs() << "*** IssueCount " << IssueCount
00354           << " at cycle " << CurrCycle << '\n');
00355 }
00356 
00357 /// Release pending ready nodes in to the available queue. This makes them
00358 /// visible to heuristics.
00359 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
00360   // If the available queue is empty, it is safe to reset MinReadyCycle.
00361   if (Available.empty())
00362     MinReadyCycle = UINT_MAX;
00363 
00364   // Check to see if any of the pending instructions are ready to issue.  If
00365   // so, add them to the available queue.
00366   for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
00367     SUnit *SU = *(Pending.begin()+i);
00368     unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
00369 
00370     if (ReadyCycle < MinReadyCycle)
00371       MinReadyCycle = ReadyCycle;
00372 
00373     if (ReadyCycle > CurrCycle)
00374       continue;
00375 
00376     if (checkHazard(SU))
00377       continue;
00378 
00379     Available.push(SU);
00380     Pending.remove(Pending.begin()+i);
00381     --i; --e;
00382   }
00383   CheckPending = false;
00384 }
00385 
00386 /// Remove SU from the ready set for this boundary.
00387 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) {
00388   if (Available.isInQueue(SU))
00389     Available.remove(Available.find(SU));
00390   else {
00391     assert(Pending.isInQueue(SU) && "bad ready count");
00392     Pending.remove(Pending.find(SU));
00393   }
00394 }
00395 
00396 /// If this queue only has one ready candidate, return it. As a side effect,
00397 /// advance the cycle until at least one node is ready. If multiple instructions
00398 /// are ready, return NULL.
00399 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
00400   if (CheckPending)
00401     releasePending();
00402 
00403   for (unsigned i = 0; Available.empty(); ++i) {
00404     assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
00405            "permanent hazard"); (void)i;
00406     ResourceModel->reserveResources(nullptr);
00407     bumpCycle();
00408     releasePending();
00409   }
00410   if (Available.size() == 1)
00411     return *Available.begin();
00412   return nullptr;
00413 }
00414 
00415 #ifndef NDEBUG
00416 void ConvergingVLIWScheduler::traceCandidate(const char *Label,
00417                                              const ReadyQueue &Q,
00418                                              SUnit *SU, PressureChange P) {
00419   dbgs() << Label << " " << Q.getName() << " ";
00420   if (P.isValid())
00421     dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
00422            << P.getUnitInc() << " ";
00423   else
00424     dbgs() << "     ";
00425   SU->dump(DAG);
00426 }
00427 #endif
00428 
00429 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
00430 /// of SU, return it, otherwise return null.
00431 static SUnit *getSingleUnscheduledPred(SUnit *SU) {
00432   SUnit *OnlyAvailablePred = nullptr;
00433   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00434        I != E; ++I) {
00435     SUnit &Pred = *I->getSUnit();
00436     if (!Pred.isScheduled) {
00437       // We found an available, but not scheduled, predecessor.  If it's the
00438       // only one we have found, keep track of it... otherwise give up.
00439       if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
00440         return nullptr;
00441       OnlyAvailablePred = &Pred;
00442     }
00443   }
00444   return OnlyAvailablePred;
00445 }
00446 
00447 /// getSingleUnscheduledSucc - If there is exactly one unscheduled successor
00448 /// of SU, return it, otherwise return null.
00449 static SUnit *getSingleUnscheduledSucc(SUnit *SU) {
00450   SUnit *OnlyAvailableSucc = nullptr;
00451   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00452        I != E; ++I) {
00453     SUnit &Succ = *I->getSUnit();
00454     if (!Succ.isScheduled) {
00455       // We found an available, but not scheduled, successor.  If it's the
00456       // only one we have found, keep track of it... otherwise give up.
00457       if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ)
00458         return nullptr;
00459       OnlyAvailableSucc = &Succ;
00460     }
00461   }
00462   return OnlyAvailableSucc;
00463 }
00464 
00465 // Constants used to denote relative importance of
00466 // heuristic components for cost computation.
00467 static const unsigned PriorityOne = 200;
00468 static const unsigned PriorityTwo = 50;
00469 static const unsigned ScaleTwo = 10;
00470 static const unsigned FactorOne = 2;
00471 
00472 /// Single point to compute overall scheduling cost.
00473 /// TODO: More heuristics will be used soon.
00474 int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
00475                                             SchedCandidate &Candidate,
00476                                             RegPressureDelta &Delta,
00477                                             bool verbose) {
00478   // Initial trivial priority.
00479   int ResCount = 1;
00480 
00481   // Do not waste time on a node that is already scheduled.
00482   if (!SU || SU->isScheduled)
00483     return ResCount;
00484 
00485   // Forced priority is high.
00486   if (SU->isScheduleHigh)
00487     ResCount += PriorityOne;
00488 
00489   // Critical path first.
00490   if (Q.getID() == TopQID) {
00491     ResCount += (SU->getHeight() * ScaleTwo);
00492 
00493     // If resources are available for it, multiply the
00494     // chance of scheduling.
00495     if (Top.ResourceModel->isResourceAvailable(SU))
00496       ResCount <<= FactorOne;
00497   } else {
00498     ResCount += (SU->getDepth() * ScaleTwo);
00499 
00500     // If resources are available for it, multiply the
00501     // chance of scheduling.
00502     if (Bot.ResourceModel->isResourceAvailable(SU))
00503       ResCount <<= FactorOne;
00504   }
00505 
00506   unsigned NumNodesBlocking = 0;
00507   if (Q.getID() == TopQID) {
00508     // How many SUs does it block from scheduling?
00509     // Look at all of the successors of this node.
00510     // Count the number of nodes that
00511     // this node is the sole unscheduled node for.
00512     for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00513          I != E; ++I)
00514       if (getSingleUnscheduledPred(I->getSUnit()) == SU)
00515         ++NumNodesBlocking;
00516   } else {
00517     // How many unscheduled predecessors block this node?
00518     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00519          I != E; ++I)
00520       if (getSingleUnscheduledSucc(I->getSUnit()) == SU)
00521         ++NumNodesBlocking;
00522   }
00523   ResCount += (NumNodesBlocking * ScaleTwo);
00524 
00525   // Factor in reg pressure as a heuristic.
00526   ResCount -= (Delta.Excess.getUnitInc()*PriorityTwo);
00527   ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityTwo);
00528 
00529   DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")");
00530 
00531   return ResCount;
00532 }
00533 
00534 /// Pick the best candidate from the top queue.
00535 ///
00536 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
00537 /// DAG building. To adjust for the current scheduling location we need to
00538 /// maintain the number of vreg uses remaining to be top-scheduled.
00539 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
00540 pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
00541                   SchedCandidate &Candidate) {
00542   DEBUG(Q.dump());
00543 
00544   // getMaxPressureDelta temporarily modifies the tracker.
00545   RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
00546 
00547   // BestSU remains NULL if no top candidates beat the best existing candidate.
00548   CandResult FoundCandidate = NoCand;
00549   for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
00550     RegPressureDelta RPDelta;
00551     TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
00552                                     DAG->getRegionCriticalPSets(),
00553                                     DAG->getRegPressure().MaxSetPressure);
00554 
00555     int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
00556 
00557     // Initialize the candidate if needed.
00558     if (!Candidate.SU) {
00559       Candidate.SU = *I;
00560       Candidate.RPDelta = RPDelta;
00561       Candidate.SCost = CurrentCost;
00562       FoundCandidate = NodeOrder;
00563       continue;
00564     }
00565 
00566     // Best cost.
00567     if (CurrentCost > Candidate.SCost) {
00568       DEBUG(traceCandidate("CCAND", Q, *I));
00569       Candidate.SU = *I;
00570       Candidate.RPDelta = RPDelta;
00571       Candidate.SCost = CurrentCost;
00572       FoundCandidate = BestCost;
00573       continue;
00574     }
00575 
00576     // Fall through to original instruction order.
00577     // Only consider node order if Candidate was chosen from this Q.
00578     if (FoundCandidate == NoCand)
00579       continue;
00580   }
00581   return FoundCandidate;
00582 }
00583 
00584 /// Pick the best candidate node from either the top or bottom queue.
00585 SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) {
00586   // Schedule as far as possible in the direction of no choice. This is most
00587   // efficient, but also provides the best heuristics for CriticalPSets.
00588   if (SUnit *SU = Bot.pickOnlyChoice()) {
00589     IsTopNode = false;
00590     return SU;
00591   }
00592   if (SUnit *SU = Top.pickOnlyChoice()) {
00593     IsTopNode = true;
00594     return SU;
00595   }
00596   SchedCandidate BotCand;
00597   // Prefer bottom scheduling when heuristics are silent.
00598   CandResult BotResult = pickNodeFromQueue(Bot.Available,
00599                                            DAG->getBotRPTracker(), BotCand);
00600   assert(BotResult != NoCand && "failed to find the first candidate");
00601 
00602   // If either Q has a single candidate that provides the least increase in
00603   // Excess pressure, we can immediately schedule from that Q.
00604   //
00605   // RegionCriticalPSets summarizes the pressure within the scheduled region and
00606   // affects picking from either Q. If scheduling in one direction must
00607   // increase pressure for one of the excess PSets, then schedule in that
00608   // direction first to provide more freedom in the other direction.
00609   if (BotResult == SingleExcess || BotResult == SingleCritical) {
00610     IsTopNode = false;
00611     return BotCand.SU;
00612   }
00613   // Check if the top Q has a better candidate.
00614   SchedCandidate TopCand;
00615   CandResult TopResult = pickNodeFromQueue(Top.Available,
00616                                            DAG->getTopRPTracker(), TopCand);
00617   assert(TopResult != NoCand && "failed to find the first candidate");
00618 
00619   if (TopResult == SingleExcess || TopResult == SingleCritical) {
00620     IsTopNode = true;
00621     return TopCand.SU;
00622   }
00623   // If either Q has a single candidate that minimizes pressure above the
00624   // original region's pressure pick it.
00625   if (BotResult == SingleMax) {
00626     IsTopNode = false;
00627     return BotCand.SU;
00628   }
00629   if (TopResult == SingleMax) {
00630     IsTopNode = true;
00631     return TopCand.SU;
00632   }
00633   if (TopCand.SCost > BotCand.SCost) {
00634     IsTopNode = true;
00635     return TopCand.SU;
00636   }
00637   // Otherwise prefer the bottom candidate in node order.
00638   IsTopNode = false;
00639   return BotCand.SU;
00640 }
00641 
00642 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
00643 SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
00644   if (DAG->top() == DAG->bottom()) {
00645     assert(Top.Available.empty() && Top.Pending.empty() &&
00646            Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
00647     return nullptr;
00648   }
00649   SUnit *SU;
00650   if (llvm::ForceTopDown) {
00651     SU = Top.pickOnlyChoice();
00652     if (!SU) {
00653       SchedCandidate TopCand;
00654       CandResult TopResult =
00655         pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
00656       assert(TopResult != NoCand && "failed to find the first candidate");
00657       (void)TopResult;
00658       SU = TopCand.SU;
00659     }
00660     IsTopNode = true;
00661   } else if (llvm::ForceBottomUp) {
00662     SU = Bot.pickOnlyChoice();
00663     if (!SU) {
00664       SchedCandidate BotCand;
00665       CandResult BotResult =
00666         pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
00667       assert(BotResult != NoCand && "failed to find the first candidate");
00668       (void)BotResult;
00669       SU = BotCand.SU;
00670     }
00671     IsTopNode = false;
00672   } else {
00673     SU = pickNodeBidrectional(IsTopNode);
00674   }
00675   if (SU->isTopReady())
00676     Top.removeReady(SU);
00677   if (SU->isBottomReady())
00678     Bot.removeReady(SU);
00679 
00680   DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
00681         << " Scheduling Instruction in cycle "
00682         << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
00683         SU->dump(DAG));
00684   return SU;
00685 }
00686 
00687 /// Update the scheduler's state after scheduling a node. This is the same node
00688 /// that was just returned by pickNode(). However, VLIWMachineScheduler needs
00689 /// to update it's state based on the current cycle before MachineSchedStrategy
00690 /// does.
00691 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
00692   if (IsTopNode) {
00693     SU->TopReadyCycle = Top.CurrCycle;
00694     Top.bumpNode(SU);
00695   } else {
00696     SU->BotReadyCycle = Bot.CurrCycle;
00697     Bot.bumpNode(SU);
00698   }
00699 }