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