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