LLVM API Documentation

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 (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
00183     if (!checkSchedLimit())
00184       break;
00185 
00186     scheduleMI(SU, IsTopNode);
00187 
00188     updateQueues(SU, IsTopNode);
00189 
00190     // Notify the scheduling strategy after updating the DAG.
00191     SchedImpl->schedNode(SU, IsTopNode);
00192   }
00193   assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
00194 
00195   placeDebugValues();
00196 }
00197 
00198 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
00199   DAG = static_cast<VLIWMachineScheduler*>(dag);
00200   SchedModel = DAG->getSchedModel();
00201 
00202   Top.init(DAG, SchedModel);
00203   Bot.init(DAG, SchedModel);
00204 
00205   // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
00206   // are disabled, then these HazardRecs will be disabled.
00207   const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
00208   const TargetSubtargetInfo &STI = DAG->MF.getSubtarget();
00209   const TargetInstrInfo *TII = STI.getInstrInfo();
00210   delete Top.HazardRec;
00211   delete Bot.HazardRec;
00212   Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
00213   Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
00214 
00215   delete Top.ResourceModel;
00216   delete Bot.ResourceModel;
00217   Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
00218   Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
00219 
00220   assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) &&
00221          "-misched-topdown incompatible with -misched-bottomup");
00222 }
00223 
00224 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
00225   if (SU->isScheduled)
00226     return;
00227 
00228   for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00229        I != E; ++I) {
00230     unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
00231     unsigned MinLatency = I->getLatency();
00232 #ifndef NDEBUG
00233     Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
00234 #endif
00235     if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
00236       SU->TopReadyCycle = PredReadyCycle + MinLatency;
00237   }
00238   Top.releaseNode(SU, SU->TopReadyCycle);
00239 }
00240 
00241 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
00242   if (SU->isScheduled)
00243     return;
00244 
00245   assert(SU->getInstr() && "Scheduled SUnit must have instr");
00246 
00247   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00248        I != E; ++I) {
00249     unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
00250     unsigned MinLatency = I->getLatency();
00251 #ifndef NDEBUG
00252     Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
00253 #endif
00254     if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
00255       SU->BotReadyCycle = SuccReadyCycle + MinLatency;
00256   }
00257   Bot.releaseNode(SU, SU->BotReadyCycle);
00258 }
00259 
00260 /// Does this SU have a hazard within the current instruction group.
00261 ///
00262 /// The scheduler supports two modes of hazard recognition. The first is the
00263 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
00264 /// supports highly complicated in-order reservation tables
00265 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
00266 ///
00267 /// The second is a streamlined mechanism that checks for hazards based on
00268 /// simple counters that the scheduler itself maintains. It explicitly checks
00269 /// for instruction dispatch limitations, including the number of micro-ops that
00270 /// can dispatch per cycle.
00271 ///
00272 /// TODO: Also check whether the SU must start a new group.
00273 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) {
00274   if (HazardRec->isEnabled())
00275     return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
00276 
00277   unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
00278   if (IssueCount + uops > SchedModel->getIssueWidth())
00279     return true;
00280 
00281   return false;
00282 }
00283 
00284 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU,
00285                                                      unsigned ReadyCycle) {
00286   if (ReadyCycle < MinReadyCycle)
00287     MinReadyCycle = ReadyCycle;
00288 
00289   // Check for interlocks first. For the purpose of other heuristics, an
00290   // instruction that cannot issue appears as if it's not in the ReadyQueue.
00291   if (ReadyCycle > CurrCycle || checkHazard(SU))
00292 
00293     Pending.push(SU);
00294   else
00295     Available.push(SU);
00296 }
00297 
00298 /// Move the boundary of scheduled code by one cycle.
00299 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
00300   unsigned Width = SchedModel->getIssueWidth();
00301   IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
00302 
00303   assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
00304   unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
00305 
00306   if (!HazardRec->isEnabled()) {
00307     // Bypass HazardRec virtual calls.
00308     CurrCycle = NextCycle;
00309   } else {
00310     // Bypass getHazardType calls in case of long latency.
00311     for (; CurrCycle != NextCycle; ++CurrCycle) {
00312       if (isTop())
00313         HazardRec->AdvanceCycle();
00314       else
00315         HazardRec->RecedeCycle();
00316     }
00317   }
00318   CheckPending = true;
00319 
00320   DEBUG(dbgs() << "*** " << Available.getName() << " cycle "
00321         << CurrCycle << '\n');
00322 }
00323 
00324 /// Move the boundary of scheduled code by one SUnit.
00325 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) {
00326   bool startNewCycle = false;
00327 
00328   // Update the reservation table.
00329   if (HazardRec->isEnabled()) {
00330     if (!isTop() && SU->isCall) {
00331       // Calls are scheduled with their preceding instructions. For bottom-up
00332       // scheduling, clear the pipeline state before emitting.
00333       HazardRec->Reset();
00334     }
00335     HazardRec->EmitInstruction(SU);
00336   }
00337 
00338   // Update DFA model.
00339   startNewCycle = ResourceModel->reserveResources(SU);
00340 
00341   // Check the instruction group dispatch limit.
00342   // TODO: Check if this SU must end a dispatch group.
00343   IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
00344   if (startNewCycle) {
00345     DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
00346     bumpCycle();
00347   }
00348   else
00349     DEBUG(dbgs() << "*** IssueCount " << IssueCount
00350           << " at cycle " << CurrCycle << '\n');
00351 }
00352 
00353 /// Release pending ready nodes in to the available queue. This makes them
00354 /// visible to heuristics.
00355 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
00356   // If the available queue is empty, it is safe to reset MinReadyCycle.
00357   if (Available.empty())
00358     MinReadyCycle = UINT_MAX;
00359 
00360   // Check to see if any of the pending instructions are ready to issue.  If
00361   // so, add them to the available queue.
00362   for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
00363     SUnit *SU = *(Pending.begin()+i);
00364     unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
00365 
00366     if (ReadyCycle < MinReadyCycle)
00367       MinReadyCycle = ReadyCycle;
00368 
00369     if (ReadyCycle > CurrCycle)
00370       continue;
00371 
00372     if (checkHazard(SU))
00373       continue;
00374 
00375     Available.push(SU);
00376     Pending.remove(Pending.begin()+i);
00377     --i; --e;
00378   }
00379   CheckPending = false;
00380 }
00381 
00382 /// Remove SU from the ready set for this boundary.
00383 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) {
00384   if (Available.isInQueue(SU))
00385     Available.remove(Available.find(SU));
00386   else {
00387     assert(Pending.isInQueue(SU) && "bad ready count");
00388     Pending.remove(Pending.find(SU));
00389   }
00390 }
00391 
00392 /// If this queue only has one ready candidate, return it. As a side effect,
00393 /// advance the cycle until at least one node is ready. If multiple instructions
00394 /// are ready, return NULL.
00395 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
00396   if (CheckPending)
00397     releasePending();
00398 
00399   for (unsigned i = 0; Available.empty(); ++i) {
00400     assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
00401            "permanent hazard"); (void)i;
00402     ResourceModel->reserveResources(nullptr);
00403     bumpCycle();
00404     releasePending();
00405   }
00406   if (Available.size() == 1)
00407     return *Available.begin();
00408   return nullptr;
00409 }
00410 
00411 #ifndef NDEBUG
00412 void ConvergingVLIWScheduler::traceCandidate(const char *Label,
00413                                              const ReadyQueue &Q,
00414                                              SUnit *SU, PressureChange P) {
00415   dbgs() << Label << " " << Q.getName() << " ";
00416   if (P.isValid())
00417     dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
00418            << P.getUnitInc() << " ";
00419   else
00420     dbgs() << "     ";
00421   SU->dump(DAG);
00422 }
00423 #endif
00424 
00425 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
00426 /// of SU, return it, otherwise return null.
00427 static SUnit *getSingleUnscheduledPred(SUnit *SU) {
00428   SUnit *OnlyAvailablePred = nullptr;
00429   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00430        I != E; ++I) {
00431     SUnit &Pred = *I->getSUnit();
00432     if (!Pred.isScheduled) {
00433       // We found an available, but not scheduled, predecessor.  If it's the
00434       // only one we have found, keep track of it... otherwise give up.
00435       if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
00436         return nullptr;
00437       OnlyAvailablePred = &Pred;
00438     }
00439   }
00440   return OnlyAvailablePred;
00441 }
00442 
00443 /// getSingleUnscheduledSucc - If there is exactly one unscheduled successor
00444 /// of SU, return it, otherwise return null.
00445 static SUnit *getSingleUnscheduledSucc(SUnit *SU) {
00446   SUnit *OnlyAvailableSucc = nullptr;
00447   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00448        I != E; ++I) {
00449     SUnit &Succ = *I->getSUnit();
00450     if (!Succ.isScheduled) {
00451       // We found an available, but not scheduled, successor.  If it's the
00452       // only one we have found, keep track of it... otherwise give up.
00453       if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ)
00454         return nullptr;
00455       OnlyAvailableSucc = &Succ;
00456     }
00457   }
00458   return OnlyAvailableSucc;
00459 }
00460 
00461 // Constants used to denote relative importance of
00462 // heuristic components for cost computation.
00463 static const unsigned PriorityOne = 200;
00464 static const unsigned PriorityTwo = 50;
00465 static const unsigned ScaleTwo = 10;
00466 static const unsigned FactorOne = 2;
00467 
00468 /// Single point to compute overall scheduling cost.
00469 /// TODO: More heuristics will be used soon.
00470 int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
00471                                             SchedCandidate &Candidate,
00472                                             RegPressureDelta &Delta,
00473                                             bool verbose) {
00474   // Initial trivial priority.
00475   int ResCount = 1;
00476 
00477   // Do not waste time on a node that is already scheduled.
00478   if (!SU || SU->isScheduled)
00479     return ResCount;
00480 
00481   // Forced priority is high.
00482   if (SU->isScheduleHigh)
00483     ResCount += PriorityOne;
00484 
00485   // Critical path first.
00486   if (Q.getID() == TopQID) {
00487     ResCount += (SU->getHeight() * ScaleTwo);
00488 
00489     // If resources are available for it, multiply the
00490     // chance of scheduling.
00491     if (Top.ResourceModel->isResourceAvailable(SU))
00492       ResCount <<= FactorOne;
00493   } else {
00494     ResCount += (SU->getDepth() * ScaleTwo);
00495 
00496     // If resources are available for it, multiply the
00497     // chance of scheduling.
00498     if (Bot.ResourceModel->isResourceAvailable(SU))
00499       ResCount <<= FactorOne;
00500   }
00501 
00502   unsigned NumNodesBlocking = 0;
00503   if (Q.getID() == TopQID) {
00504     // How many SUs does it block from scheduling?
00505     // Look at all of the successors of this node.
00506     // Count the number of nodes that
00507     // this node is the sole unscheduled node for.
00508     for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00509          I != E; ++I)
00510       if (getSingleUnscheduledPred(I->getSUnit()) == SU)
00511         ++NumNodesBlocking;
00512   } else {
00513     // How many unscheduled predecessors block this node?
00514     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00515          I != E; ++I)
00516       if (getSingleUnscheduledSucc(I->getSUnit()) == SU)
00517         ++NumNodesBlocking;
00518   }
00519   ResCount += (NumNodesBlocking * ScaleTwo);
00520 
00521   // Factor in reg pressure as a heuristic.
00522   ResCount -= (Delta.Excess.getUnitInc()*PriorityTwo);
00523   ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityTwo);
00524 
00525   DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")");
00526 
00527   return ResCount;
00528 }
00529 
00530 /// Pick the best candidate from the top queue.
00531 ///
00532 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
00533 /// DAG building. To adjust for the current scheduling location we need to
00534 /// maintain the number of vreg uses remaining to be top-scheduled.
00535 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
00536 pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
00537                   SchedCandidate &Candidate) {
00538   DEBUG(Q.dump());
00539 
00540   // getMaxPressureDelta temporarily modifies the tracker.
00541   RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
00542 
00543   // BestSU remains NULL if no top candidates beat the best existing candidate.
00544   CandResult FoundCandidate = NoCand;
00545   for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
00546     RegPressureDelta RPDelta;
00547     TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
00548                                     DAG->getRegionCriticalPSets(),
00549                                     DAG->getRegPressure().MaxSetPressure);
00550 
00551     int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
00552 
00553     // Initialize the candidate if needed.
00554     if (!Candidate.SU) {
00555       Candidate.SU = *I;
00556       Candidate.RPDelta = RPDelta;
00557       Candidate.SCost = CurrentCost;
00558       FoundCandidate = NodeOrder;
00559       continue;
00560     }
00561 
00562     // Best cost.
00563     if (CurrentCost > Candidate.SCost) {
00564       DEBUG(traceCandidate("CCAND", Q, *I));
00565       Candidate.SU = *I;
00566       Candidate.RPDelta = RPDelta;
00567       Candidate.SCost = CurrentCost;
00568       FoundCandidate = BestCost;
00569       continue;
00570     }
00571 
00572     // Fall through to original instruction order.
00573     // Only consider node order if Candidate was chosen from this Q.
00574     if (FoundCandidate == NoCand)
00575       continue;
00576   }
00577   return FoundCandidate;
00578 }
00579 
00580 /// Pick the best candidate node from either the top or bottom queue.
00581 SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) {
00582   // Schedule as far as possible in the direction of no choice. This is most
00583   // efficient, but also provides the best heuristics for CriticalPSets.
00584   if (SUnit *SU = Bot.pickOnlyChoice()) {
00585     IsTopNode = false;
00586     return SU;
00587   }
00588   if (SUnit *SU = Top.pickOnlyChoice()) {
00589     IsTopNode = true;
00590     return SU;
00591   }
00592   SchedCandidate BotCand;
00593   // Prefer bottom scheduling when heuristics are silent.
00594   CandResult BotResult = pickNodeFromQueue(Bot.Available,
00595                                            DAG->getBotRPTracker(), BotCand);
00596   assert(BotResult != NoCand && "failed to find the first candidate");
00597 
00598   // If either Q has a single candidate that provides the least increase in
00599   // Excess pressure, we can immediately schedule from that Q.
00600   //
00601   // RegionCriticalPSets summarizes the pressure within the scheduled region and
00602   // affects picking from either Q. If scheduling in one direction must
00603   // increase pressure for one of the excess PSets, then schedule in that
00604   // direction first to provide more freedom in the other direction.
00605   if (BotResult == SingleExcess || BotResult == SingleCritical) {
00606     IsTopNode = false;
00607     return BotCand.SU;
00608   }
00609   // Check if the top Q has a better candidate.
00610   SchedCandidate TopCand;
00611   CandResult TopResult = pickNodeFromQueue(Top.Available,
00612                                            DAG->getTopRPTracker(), TopCand);
00613   assert(TopResult != NoCand && "failed to find the first candidate");
00614 
00615   if (TopResult == SingleExcess || TopResult == SingleCritical) {
00616     IsTopNode = true;
00617     return TopCand.SU;
00618   }
00619   // If either Q has a single candidate that minimizes pressure above the
00620   // original region's pressure pick it.
00621   if (BotResult == SingleMax) {
00622     IsTopNode = false;
00623     return BotCand.SU;
00624   }
00625   if (TopResult == SingleMax) {
00626     IsTopNode = true;
00627     return TopCand.SU;
00628   }
00629   if (TopCand.SCost > BotCand.SCost) {
00630     IsTopNode = true;
00631     return TopCand.SU;
00632   }
00633   // Otherwise prefer the bottom candidate in node order.
00634   IsTopNode = false;
00635   return BotCand.SU;
00636 }
00637 
00638 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
00639 SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
00640   if (DAG->top() == DAG->bottom()) {
00641     assert(Top.Available.empty() && Top.Pending.empty() &&
00642            Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
00643     return nullptr;
00644   }
00645   SUnit *SU;
00646   if (llvm::ForceTopDown) {
00647     SU = Top.pickOnlyChoice();
00648     if (!SU) {
00649       SchedCandidate TopCand;
00650       CandResult TopResult =
00651         pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
00652       assert(TopResult != NoCand && "failed to find the first candidate");
00653       (void)TopResult;
00654       SU = TopCand.SU;
00655     }
00656     IsTopNode = true;
00657   } else if (llvm::ForceBottomUp) {
00658     SU = Bot.pickOnlyChoice();
00659     if (!SU) {
00660       SchedCandidate BotCand;
00661       CandResult BotResult =
00662         pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
00663       assert(BotResult != NoCand && "failed to find the first candidate");
00664       (void)BotResult;
00665       SU = BotCand.SU;
00666     }
00667     IsTopNode = false;
00668   } else {
00669     SU = pickNodeBidrectional(IsTopNode);
00670   }
00671   if (SU->isTopReady())
00672     Top.removeReady(SU);
00673   if (SU->isBottomReady())
00674     Bot.removeReady(SU);
00675 
00676   DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
00677         << " Scheduling Instruction in cycle "
00678         << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
00679         SU->dump(DAG));
00680   return SU;
00681 }
00682 
00683 /// Update the scheduler's state after scheduling a node. This is the same node
00684 /// that was just returned by pickNode(). However, VLIWMachineScheduler needs
00685 /// to update it's state based on the current cycle before MachineSchedStrategy
00686 /// does.
00687 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
00688   if (IsTopNode) {
00689     SU->TopReadyCycle = Top.CurrCycle;
00690     Top.bumpNode(SU);
00691   } else {
00692     SU->BotReadyCycle = Bot.CurrCycle;
00693     Bot.bumpNode(SU);
00694   }
00695 }