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
19using namespace llvm;
20
21#define DEBUG_TYPE "misched"
22
23/// Platform-specific modifications to DAG.
24void 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.
43bool 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.
83bool 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.
143void 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
202void 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
228void 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
245void 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.
277bool 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
288void 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.
303void 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.
329void 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.
359void 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.
387void 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.
399SUnit *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
416void 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.
431static 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.
449static 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.
467static const unsigned PriorityOne = 200;
468static const unsigned PriorityTwo = 50;
469static const unsigned ScaleTwo = 10;
470static const unsigned FactorOne = 2;
471
472/// Single point to compute overall scheduling cost.
473/// TODO: More heuristics will be used soon.
474int 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.
539ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
540pickNodeFromQueue(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.
585SUnit *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.
643SUnit *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.
691void 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}
700