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