lib/Target/Hexagon/HexagonMachineScheduler.cpp

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