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