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