1 //===- HexagonMachineScheduler.cpp - MI Scheduler for Hexagon -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // MachineScheduler schedules machine instructions after phi elimination. It
11 // preserves LiveIntervals so it can be invoked before register allocation.
13 //===----------------------------------------------------------------------===//
15 #include "HexagonMachineScheduler.h"
16 #include "HexagonSubtarget.h"
17 #include "llvm/CodeGen/MachineLoopInfo.h"
18 #include "llvm/CodeGen/ScheduleDAGMutation.h"
19 #include "llvm/IR/Function.h"
24 static cl::opt<bool> IgnoreBBRegPressure("ignore-bb-reg-pressure",
25 cl::Hidden, cl::ZeroOrMore, cl::init(false));
27 static cl::opt<bool> SchedPredsCloser("sched-preds-closer",
28 cl::Hidden, cl::ZeroOrMore, cl::init(true));
30 static cl::opt<unsigned> SchedDebugVerboseLevel("misched-verbose-level",
31 cl::Hidden, cl::ZeroOrMore, cl::init(1));
33 static cl::opt<bool> TopUseShorterTie("top-use-shorter-tie",
34 cl::Hidden, cl::ZeroOrMore, cl::init(false));
36 static cl::opt<bool> BotUseShorterTie("bot-use-shorter-tie",
37 cl::Hidden, cl::ZeroOrMore, cl::init(false));
39 static cl::opt<bool> DisableTCTie("disable-tc-tie",
40 cl::Hidden, cl::ZeroOrMore, cl::init(false));
42 static cl::opt<bool> SchedRetvalOptimization("sched-retval-optimization",
43 cl::Hidden, cl::ZeroOrMore, cl::init(true));
45 // Check if the scheduler should penalize instructions that are available to
46 // early due to a zero-latency dependence.
47 static cl::opt<bool> CheckEarlyAvail("check-early-avail", cl::Hidden,
48 cl::ZeroOrMore, cl::init(true));
52 #define DEBUG_TYPE "misched"
54 class HexagonCallMutation : public ScheduleDAGMutation {
56 void apply(ScheduleDAGInstrs *DAG) override;
58 bool shouldTFRICallBind(const HexagonInstrInfo &HII,
59 const SUnit &Inst1, const SUnit &Inst2) const;
62 // Check if a call and subsequent A2_tfrpi instructions should maintain
63 // scheduling affinity. We are looking for the TFRI to be consumed in
64 // the next instruction. This should help reduce the instances of
65 // double register pairs being allocated and scheduled before a call
66 // when not used until after the call. This situation is exacerbated
67 // by the fact that we allocate the pair from the callee saves list,
68 // leading to excess spills and restores.
69 bool HexagonCallMutation::shouldTFRICallBind(const HexagonInstrInfo &HII,
70 const SUnit &Inst1, const SUnit &Inst2) const {
71 if (Inst1.getInstr()->getOpcode() != Hexagon::A2_tfrpi)
74 // TypeXTYPE are 64 bit operations.
75 if (HII.getType(Inst2.getInstr()) == HexagonII::TypeXTYPE)
80 void HexagonCallMutation::apply(ScheduleDAGInstrs *DAG) {
81 SUnit* LastSequentialCall = nullptr;
82 unsigned VRegHoldingRet = 0;
84 SUnit* LastUseOfRet = nullptr;
85 auto &TRI = *DAG->MF.getSubtarget().getRegisterInfo();
86 auto &HII = *DAG->MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
88 // Currently we only catch the situation when compare gets scheduled
89 // before preceding call.
90 for (unsigned su = 0, e = DAG->SUnits.size(); su != e; ++su) {
92 if (DAG->SUnits[su].getInstr()->isCall())
93 LastSequentialCall = &DAG->SUnits[su];
94 // Look for a compare that defines a predicate.
95 else if (DAG->SUnits[su].getInstr()->isCompare() && LastSequentialCall)
96 DAG->SUnits[su].addPred(SDep(LastSequentialCall, SDep::Barrier));
97 // Look for call and tfri* instructions.
98 else if (SchedPredsCloser && LastSequentialCall && su > 1 && su < e-1 &&
99 shouldTFRICallBind(HII, DAG->SUnits[su], DAG->SUnits[su+1]))
100 DAG->SUnits[su].addPred(SDep(&DAG->SUnits[su-1], SDep::Barrier));
101 // Prevent redundant register copies between two calls, which are caused by
102 // both the return value and the argument for the next call being in %R0.
105 // 2: %VregX = COPY %R0
106 // 3: <use of %VregX>
109 // The scheduler would often swap 3 and 4, so an additional register is
110 // needed. This code inserts a Barrier dependence between 3 & 4 to prevent
111 // this. The same applies for %D0 and %V0/%W0, which are also handled.
112 else if (SchedRetvalOptimization) {
113 const MachineInstr *MI = DAG->SUnits[su].getInstr();
114 if (MI->isCopy() && (MI->readsRegister(Hexagon::R0, &TRI) ||
115 MI->readsRegister(Hexagon::V0, &TRI))) {
117 VRegHoldingRet = MI->getOperand(0).getReg();
118 RetRegister = MI->getOperand(1).getReg();
119 LastUseOfRet = nullptr;
120 } else if (VRegHoldingRet && MI->readsVirtualRegister(VRegHoldingRet))
122 LastUseOfRet = &DAG->SUnits[su];
123 else if (LastUseOfRet && MI->definesRegister(RetRegister, &TRI))
125 DAG->SUnits[su].addPred(SDep(LastUseOfRet, SDep::Barrier));
131 /// Save the last formed packet
132 void VLIWResourceModel::savePacket() {
136 /// Check if scheduling of this SU is possible
137 /// in the current packet.
138 /// It is _not_ precise (statefull), it is more like
139 /// another heuristic. Many corner cases are figured
141 bool VLIWResourceModel::isResourceAvailable(SUnit *SU) {
142 if (!SU || !SU->getInstr())
145 // First see if the pipeline could receive this instruction
146 // in the current cycle.
147 switch (SU->getInstr()->getOpcode()) {
149 if (!ResourcesModel->canReserveResources(*SU->getInstr()))
151 case TargetOpcode::EXTRACT_SUBREG:
152 case TargetOpcode::INSERT_SUBREG:
153 case TargetOpcode::SUBREG_TO_REG:
154 case TargetOpcode::REG_SEQUENCE:
155 case TargetOpcode::IMPLICIT_DEF:
156 case TargetOpcode::COPY:
157 case TargetOpcode::INLINEASM:
161 MachineFunction &MF = *SU->getInstr()->getParent()->getParent();
162 auto &QII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
164 // Now see if there are no other dependencies to instructions already
166 for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
167 if (Packet[i]->Succs.size() == 0)
170 // Enable .cur formation.
171 if (QII.mayBeCurLoad(Packet[i]->getInstr()))
174 for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(),
175 E = Packet[i]->Succs.end(); I != E; ++I) {
176 // Since we do not add pseudos to packets, might as well
177 // ignore order dependencies.
181 if (I->getSUnit() == SU)
188 /// Keep track of available resources.
189 bool VLIWResourceModel::reserveResources(SUnit *SU) {
190 bool startNewCycle = false;
191 // Artificially reset state.
193 ResourcesModel->clearResources();
199 // If this SU does not fit in the packet
201 if (!isResourceAvailable(SU)) {
202 ResourcesModel->clearResources();
206 startNewCycle = true;
209 switch (SU->getInstr()->getOpcode()) {
211 ResourcesModel->reserveResources(*SU->getInstr());
213 case TargetOpcode::EXTRACT_SUBREG:
214 case TargetOpcode::INSERT_SUBREG:
215 case TargetOpcode::SUBREG_TO_REG:
216 case TargetOpcode::REG_SEQUENCE:
217 case TargetOpcode::IMPLICIT_DEF:
218 case TargetOpcode::KILL:
219 case TargetOpcode::CFI_INSTRUCTION:
220 case TargetOpcode::EH_LABEL:
221 case TargetOpcode::COPY:
222 case TargetOpcode::INLINEASM:
225 Packet.push_back(SU);
228 DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
229 for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
230 DEBUG(dbgs() << "\t[" << i << "] SU(");
231 DEBUG(dbgs() << Packet[i]->NodeNum << ")\t");
232 DEBUG(Packet[i]->getInstr()->dump());
236 // If packet is now full, reset the state so in the next cycle
238 if (Packet.size() >= SchedModel->getIssueWidth()) {
239 ResourcesModel->clearResources();
243 startNewCycle = true;
246 return startNewCycle;
249 /// schedule - Called back from MachineScheduler::runOnMachineFunction
250 /// after setting up the current scheduling region. [RegionBegin, RegionEnd)
251 /// only includes instructions that have DAG nodes, not scheduling boundaries.
252 void VLIWMachineScheduler::schedule() {
254 << "********** MI Converging Scheduling VLIW BB#" << BB->getNumber()
255 << " " << BB->getName()
256 << " in_func " << BB->getParent()->getFunction()->getName()
257 << " at loop depth " << MLI->getLoopDepth(BB)
260 buildDAGWithRegPressure();
262 SmallVector<SUnit*, 8> TopRoots, BotRoots;
263 findRootsAndBiasEdges(TopRoots, BotRoots);
265 // Initialize the strategy before modifying the DAG.
266 SchedImpl->initialize(this);
268 DEBUG(unsigned maxH = 0;
269 for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
270 if (SUnits[su].getHeight() > maxH)
271 maxH = SUnits[su].getHeight();
272 dbgs() << "Max Height " << maxH << "\n";);
273 DEBUG(unsigned maxD = 0;
274 for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
275 if (SUnits[su].getDepth() > maxD)
276 maxD = SUnits[su].getDepth();
277 dbgs() << "Max Depth " << maxD << "\n";);
278 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
279 SUnits[su].dumpAll(this));
281 initQueues(TopRoots, BotRoots);
283 bool IsTopNode = false;
285 DEBUG(dbgs() << "** VLIWMachineScheduler::schedule picking next node\n");
286 SUnit *SU = SchedImpl->pickNode(IsTopNode);
289 if (!checkSchedLimit())
292 scheduleMI(SU, IsTopNode);
294 updateQueues(SU, IsTopNode);
296 // Notify the scheduling strategy after updating the DAG.
297 SchedImpl->schedNode(SU, IsTopNode);
299 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
304 unsigned BBNum = begin()->getParent()->getNumber();
305 dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
311 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
312 DAG = static_cast<VLIWMachineScheduler*>(dag);
313 SchedModel = DAG->getSchedModel();
315 Top.init(DAG, SchedModel);
316 Bot.init(DAG, SchedModel);
318 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
319 // are disabled, then these HazardRecs will be disabled.
320 const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
321 const TargetSubtargetInfo &STI = DAG->MF.getSubtarget();
322 const TargetInstrInfo *TII = STI.getInstrInfo();
323 delete Top.HazardRec;
324 delete Bot.HazardRec;
325 Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
326 Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
328 delete Top.ResourceModel;
329 delete Bot.ResourceModel;
330 Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
331 Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
333 assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) &&
334 "-misched-topdown incompatible with -misched-bottomup");
336 DAG->addMutation(make_unique<HexagonSubtarget::HexagonDAGMutation>());
337 DAG->addMutation(make_unique<HexagonCallMutation>());
340 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
344 for (const SDep &PI : SU->Preds) {
345 unsigned PredReadyCycle = PI.getSUnit()->TopReadyCycle;
346 unsigned MinLatency = PI.getLatency();
348 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
350 if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
351 SU->TopReadyCycle = PredReadyCycle + MinLatency;
353 Top.releaseNode(SU, SU->TopReadyCycle);
356 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
360 assert(SU->getInstr() && "Scheduled SUnit must have instr");
362 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
364 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
365 unsigned MinLatency = I->getLatency();
367 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
369 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
370 SU->BotReadyCycle = SuccReadyCycle + MinLatency;
372 Bot.releaseNode(SU, SU->BotReadyCycle);
375 /// Does this SU have a hazard within the current instruction group.
377 /// The scheduler supports two modes of hazard recognition. The first is the
378 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
379 /// supports highly complicated in-order reservation tables
380 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
382 /// The second is a streamlined mechanism that checks for hazards based on
383 /// simple counters that the scheduler itself maintains. It explicitly checks
384 /// for instruction dispatch limitations, including the number of micro-ops that
385 /// can dispatch per cycle.
387 /// TODO: Also check whether the SU must start a new group.
388 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) {
389 if (HazardRec->isEnabled())
390 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
392 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
393 if (IssueCount + uops > SchedModel->getIssueWidth())
399 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU,
400 unsigned ReadyCycle) {
401 if (ReadyCycle < MinReadyCycle)
402 MinReadyCycle = ReadyCycle;
404 // Check for interlocks first. For the purpose of other heuristics, an
405 // instruction that cannot issue appears as if it's not in the ReadyQueue.
406 if (ReadyCycle > CurrCycle || checkHazard(SU))
413 /// Move the boundary of scheduled code by one cycle.
414 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
415 unsigned Width = SchedModel->getIssueWidth();
416 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
418 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
419 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
421 if (!HazardRec->isEnabled()) {
422 // Bypass HazardRec virtual calls.
423 CurrCycle = NextCycle;
425 // Bypass getHazardType calls in case of long latency.
426 for (; CurrCycle != NextCycle; ++CurrCycle) {
428 HazardRec->AdvanceCycle();
430 HazardRec->RecedeCycle();
435 DEBUG(dbgs() << "*** Next cycle " << Available.getName() << " cycle "
436 << CurrCycle << '\n');
439 /// Move the boundary of scheduled code by one SUnit.
440 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) {
441 bool startNewCycle = false;
443 // Update the reservation table.
444 if (HazardRec->isEnabled()) {
445 if (!isTop() && SU->isCall) {
446 // Calls are scheduled with their preceding instructions. For bottom-up
447 // scheduling, clear the pipeline state before emitting.
450 HazardRec->EmitInstruction(SU);
454 startNewCycle = ResourceModel->reserveResources(SU);
456 // Check the instruction group dispatch limit.
457 // TODO: Check if this SU must end a dispatch group.
458 IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
460 DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
464 DEBUG(dbgs() << "*** IssueCount " << IssueCount
465 << " at cycle " << CurrCycle << '\n');
468 /// Release pending ready nodes in to the available queue. This makes them
469 /// visible to heuristics.
470 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
471 // If the available queue is empty, it is safe to reset MinReadyCycle.
472 if (Available.empty())
473 MinReadyCycle = UINT_MAX;
475 // Check to see if any of the pending instructions are ready to issue. If
476 // so, add them to the available queue.
477 for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
478 SUnit *SU = *(Pending.begin()+i);
479 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
481 if (ReadyCycle < MinReadyCycle)
482 MinReadyCycle = ReadyCycle;
484 if (ReadyCycle > CurrCycle)
491 Pending.remove(Pending.begin()+i);
494 CheckPending = false;
497 /// Remove SU from the ready set for this boundary.
498 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) {
499 if (Available.isInQueue(SU))
500 Available.remove(Available.find(SU));
502 assert(Pending.isInQueue(SU) && "bad ready count");
503 Pending.remove(Pending.find(SU));
507 /// If this queue only has one ready candidate, return it. As a side effect,
508 /// advance the cycle until at least one node is ready. If multiple instructions
509 /// are ready, return NULL.
510 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
514 for (unsigned i = 0; Available.empty(); ++i) {
515 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
516 "permanent hazard"); (void)i;
517 ResourceModel->reserveResources(nullptr);
521 if (Available.size() == 1)
522 return *Available.begin();
527 void ConvergingVLIWScheduler::traceCandidate(const char *Label,
528 const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P) {
529 dbgs() << Label << " " << Q.getName() << " ";
531 dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
532 << P.getUnitInc() << " ";
535 dbgs() << "cost(" << Cost << ")\t";
539 // Very detailed queue dump, to be used with higher verbosity levels.
540 void ConvergingVLIWScheduler::readyQueueVerboseDump(
541 const RegPressureTracker &RPTracker, SchedCandidate &Candidate,
543 RegPressureTracker &TempTracker = const_cast<RegPressureTracker &>(RPTracker);
545 dbgs() << ">>> " << Q.getName() << "\n";
546 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
547 RegPressureDelta RPDelta;
548 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
549 DAG->getRegionCriticalPSets(),
550 DAG->getRegPressure().MaxSetPressure);
551 std::stringstream dbgstr;
552 dbgstr << "SU(" << std::setw(3) << (*I)->NodeNum << ")";
553 dbgs() << dbgstr.str();
554 SchedulingCost(Q, *I, Candidate, RPDelta, true);
556 (*I)->getInstr()->dump();
562 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
563 /// of SU, return it, otherwise return null.
564 static SUnit *getSingleUnscheduledPred(SUnit *SU) {
565 SUnit *OnlyAvailablePred = nullptr;
566 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
568 SUnit &Pred = *I->getSUnit();
569 if (!Pred.isScheduled) {
570 // We found an available, but not scheduled, predecessor. If it's the
571 // only one we have found, keep track of it... otherwise give up.
572 if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
574 OnlyAvailablePred = &Pred;
577 return OnlyAvailablePred;
580 /// getSingleUnscheduledSucc - If there is exactly one unscheduled successor
581 /// of SU, return it, otherwise return null.
582 static SUnit *getSingleUnscheduledSucc(SUnit *SU) {
583 SUnit *OnlyAvailableSucc = nullptr;
584 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
586 SUnit &Succ = *I->getSUnit();
587 if (!Succ.isScheduled) {
588 // We found an available, but not scheduled, successor. If it's the
589 // only one we have found, keep track of it... otherwise give up.
590 if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ)
592 OnlyAvailableSucc = &Succ;
595 return OnlyAvailableSucc;
598 // Constants used to denote relative importance of
599 // heuristic components for cost computation.
600 static const unsigned PriorityOne = 200;
601 static const unsigned PriorityTwo = 50;
602 static const unsigned PriorityThree = 75;
603 static const unsigned ScaleTwo = 10;
604 static const unsigned FactorOne = 2;
606 /// Single point to compute overall scheduling cost.
607 /// TODO: More heuristics will be used soon.
608 int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
609 SchedCandidate &Candidate,
610 RegPressureDelta &Delta,
612 // Initial trivial priority.
615 // Do not waste time on a node that is already scheduled.
616 if (!SU || SU->isScheduled)
619 MachineInstr *Instr = SU->getInstr();
621 DEBUG(if (verbose) dbgs() << ((Q.getID() == TopQID) ? "(top|" : "(bot|"));
622 // Forced priority is high.
623 if (SU->isScheduleHigh) {
624 ResCount += PriorityOne;
625 DEBUG(dbgs() << "H|");
628 // Critical path first.
629 if (Q.getID() == TopQID) {
630 ResCount += (SU->getHeight() * ScaleTwo);
633 std::stringstream dbgstr;
634 dbgstr << "h" << std::setw(3) << SU->getHeight() << "|";
635 dbgs() << dbgstr.str();
638 // If resources are available for it, multiply the
639 // chance of scheduling.
640 if (Top.ResourceModel->isResourceAvailable(SU)) {
641 ResCount <<= FactorOne;
642 ResCount += PriorityThree;
643 DEBUG(if (verbose) dbgs() << "A|");
645 DEBUG(if (verbose) dbgs() << " |");
647 ResCount += (SU->getDepth() * ScaleTwo);
650 std::stringstream dbgstr;
651 dbgstr << "d" << std::setw(3) << SU->getDepth() << "|";
652 dbgs() << dbgstr.str();
655 // If resources are available for it, multiply the
656 // chance of scheduling.
657 if (Bot.ResourceModel->isResourceAvailable(SU)) {
658 ResCount <<= FactorOne;
659 ResCount += PriorityThree;
660 DEBUG(if (verbose) dbgs() << "A|");
662 DEBUG(if (verbose) dbgs() << " |");
665 unsigned NumNodesBlocking = 0;
666 if (Q.getID() == TopQID) {
667 // How many SUs does it block from scheduling?
668 // Look at all of the successors of this node.
669 // Count the number of nodes that
670 // this node is the sole unscheduled node for.
671 for (const SDep &SI : SU->Succs)
672 if (getSingleUnscheduledPred(SI.getSUnit()) == SU)
675 // How many unscheduled predecessors block this node?
676 for (const SDep &PI : SU->Preds)
677 if (getSingleUnscheduledSucc(PI.getSUnit()) == SU)
680 ResCount += (NumNodesBlocking * ScaleTwo);
683 std::stringstream dbgstr;
684 dbgstr << "blk " << std::setw(2) << NumNodesBlocking << ")|";
685 dbgs() << dbgstr.str();
688 // Factor in reg pressure as a heuristic.
689 if (!IgnoreBBRegPressure) {
690 // Decrease priority by the amount that register pressure exceeds the limit.
691 ResCount -= (Delta.Excess.getUnitInc()*PriorityOne);
692 // Decrease priority if register pressure exceeds the limit.
693 ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityOne);
694 // Decrease priority slightly if register pressure would increase over the
696 ResCount -= (Delta.CurrentMax.getUnitInc()*PriorityTwo);
698 dbgs() << "RP " << Delta.Excess.getUnitInc() << "/"
699 << Delta.CriticalMax.getUnitInc() <<"/"
700 << Delta.CurrentMax.getUnitInc() << ")|";
704 // Give a little extra priority to a .cur instruction if there is a resource
706 auto &QST = DAG->MF.getSubtarget<HexagonSubtarget>();
707 auto &QII = *QST.getInstrInfo();
708 if (SU->isInstr() && QII.mayBeCurLoad(SU->getInstr())) {
709 if (Q.getID() == TopQID && Top.ResourceModel->isResourceAvailable(SU)) {
710 ResCount += PriorityTwo;
711 DEBUG(if (verbose) dbgs() << "C|");
712 } else if (Q.getID() == BotQID &&
713 Bot.ResourceModel->isResourceAvailable(SU)) {
714 ResCount += PriorityTwo;
715 DEBUG(if (verbose) dbgs() << "C|");
719 // Give preference to a zero latency instruction if the dependent
720 // instruction is in the current packet.
721 if (Q.getID() == TopQID) {
722 for (const SDep &PI : SU->Preds) {
723 if (!PI.getSUnit()->getInstr()->isPseudo() && PI.isAssignedRegDep() &&
724 PI.getLatency() == 0 &&
725 Top.ResourceModel->isInPacket(PI.getSUnit())) {
726 ResCount += PriorityThree;
727 DEBUG(if (verbose) dbgs() << "Z|");
731 for (const SDep &SI : SU->Succs) {
732 if (!SI.getSUnit()->getInstr()->isPseudo() && SI.isAssignedRegDep() &&
733 SI.getLatency() == 0 &&
734 Bot.ResourceModel->isInPacket(SI.getSUnit())) {
735 ResCount += PriorityThree;
736 DEBUG(if (verbose) dbgs() << "Z|");
741 // Give less preference to an instruction that will cause a stall with
742 // an instruction in the previous packet.
743 if (QII.isV60VectorInstruction(Instr)) {
744 // Check for stalls in the previous packet.
745 if (Q.getID() == TopQID) {
746 for (auto J : Top.ResourceModel->OldPacket)
747 if (QII.producesStall(J->getInstr(), Instr))
748 ResCount -= PriorityOne;
750 for (auto J : Bot.ResourceModel->OldPacket)
751 if (QII.producesStall(Instr, J->getInstr()))
752 ResCount -= PriorityOne;
756 // If the instruction has a non-zero latency dependence with an instruction in
757 // the current packet, then it should not be scheduled yet. The case occurs
758 // when the dependent instruction is scheduled in a new packet, so the
759 // scheduler updates the current cycle and pending instructions become
761 if (CheckEarlyAvail) {
762 if (Q.getID() == TopQID) {
763 for (const auto &PI : SU->Preds) {
764 if (PI.getLatency() > 0 &&
765 Top.ResourceModel->isInPacket(PI.getSUnit())) {
766 ResCount -= PriorityOne;
767 DEBUG(if (verbose) dbgs() << "D|");
771 for (const auto &SI : SU->Succs) {
772 if (SI.getLatency() > 0 &&
773 Bot.ResourceModel->isInPacket(SI.getSUnit())) {
774 ResCount -= PriorityOne;
775 DEBUG(if (verbose) dbgs() << "D|");
782 std::stringstream dbgstr;
783 dbgstr << "Total " << std::setw(4) << ResCount << ")";
784 dbgs() << dbgstr.str();
790 /// Pick the best candidate from the top queue.
792 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
793 /// DAG building. To adjust for the current scheduling location we need to
794 /// maintain the number of vreg uses remaining to be top-scheduled.
795 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
796 pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
797 SchedCandidate &Candidate) {
798 DEBUG(if (SchedDebugVerboseLevel > 1)
799 readyQueueVerboseDump(RPTracker, Candidate, Q);
802 // getMaxPressureDelta temporarily modifies the tracker.
803 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
805 // BestSU remains NULL if no top candidates beat the best existing candidate.
806 CandResult FoundCandidate = NoCand;
807 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
808 RegPressureDelta RPDelta;
809 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
810 DAG->getRegionCriticalPSets(),
811 DAG->getRegPressure().MaxSetPressure);
813 int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
815 // Initialize the candidate if needed.
817 DEBUG(traceCandidate("DCAND", Q, *I, CurrentCost));
819 Candidate.RPDelta = RPDelta;
820 Candidate.SCost = CurrentCost;
821 FoundCandidate = NodeOrder;
826 if (CurrentCost > Candidate.SCost) {
827 DEBUG(traceCandidate("CCAND", Q, *I, CurrentCost));
829 Candidate.RPDelta = RPDelta;
830 Candidate.SCost = CurrentCost;
831 FoundCandidate = BestCost;
835 // Tie breaker using Timing Class.
837 auto &QST = DAG->MF.getSubtarget<HexagonSubtarget>();
838 auto &QII = *QST.getInstrInfo();
840 const MachineInstr *MI = (*I)->getInstr();
841 const MachineInstr *CandI = Candidate.SU->getInstr();
842 const InstrItineraryData *InstrItins = QST.getInstrItineraryData();
844 unsigned InstrLatency = QII.getInstrTimingClassLatency(InstrItins, MI);
845 unsigned CandLatency = QII.getInstrTimingClassLatency(InstrItins, CandI);
846 DEBUG(dbgs() << "TC Tie Breaker Cand: "
847 << CandLatency << " Instr:" << InstrLatency << "\n"
848 << *MI << *CandI << "\n");
849 if (Q.getID() == TopQID && CurrentCost == Candidate.SCost) {
850 if (InstrLatency < CandLatency && TopUseShorterTie) {
852 Candidate.RPDelta = RPDelta;
853 Candidate.SCost = CurrentCost;
854 FoundCandidate = BestCost;
855 DEBUG(dbgs() << "Used top shorter tie breaker\n");
857 } else if (InstrLatency > CandLatency && !TopUseShorterTie) {
859 Candidate.RPDelta = RPDelta;
860 Candidate.SCost = CurrentCost;
861 FoundCandidate = BestCost;
862 DEBUG(dbgs() << "Used top longer tie breaker\n");
865 } else if (Q.getID() == BotQID && CurrentCost == Candidate.SCost) {
866 if (InstrLatency < CandLatency && BotUseShorterTie) {
868 Candidate.RPDelta = RPDelta;
869 Candidate.SCost = CurrentCost;
870 FoundCandidate = BestCost;
871 DEBUG(dbgs() << "Used Bot shorter tie breaker\n");
873 } else if (InstrLatency > CandLatency && !BotUseShorterTie) {
875 Candidate.RPDelta = RPDelta;
876 Candidate.SCost = CurrentCost;
877 FoundCandidate = BestCost;
878 DEBUG(dbgs() << "Used Bot longer tie breaker\n");
884 if (CurrentCost == Candidate.SCost) {
885 if ((Q.getID() == TopQID &&
886 (*I)->Succs.size() > Candidate.SU->Succs.size()) ||
887 (Q.getID() == BotQID &&
888 (*I)->Preds.size() < Candidate.SU->Preds.size())) {
889 DEBUG(traceCandidate("SPCAND", Q, *I, CurrentCost));
891 Candidate.RPDelta = RPDelta;
892 Candidate.SCost = CurrentCost;
893 FoundCandidate = BestCost;
898 // Fall through to original instruction order.
899 // Only consider node order if Candidate was chosen from this Q.
900 if (FoundCandidate == NoCand)
903 return FoundCandidate;
906 /// Pick the best candidate node from either the top or bottom queue.
907 SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) {
908 // Schedule as far as possible in the direction of no choice. This is most
909 // efficient, but also provides the best heuristics for CriticalPSets.
910 if (SUnit *SU = Bot.pickOnlyChoice()) {
911 DEBUG(dbgs() << "Picked only Bottom\n");
915 if (SUnit *SU = Top.pickOnlyChoice()) {
916 DEBUG(dbgs() << "Picked only Top\n");
920 SchedCandidate BotCand;
921 // Prefer bottom scheduling when heuristics are silent.
922 CandResult BotResult = pickNodeFromQueue(Bot.Available,
923 DAG->getBotRPTracker(), BotCand);
924 assert(BotResult != NoCand && "failed to find the first candidate");
926 // If either Q has a single candidate that provides the least increase in
927 // Excess pressure, we can immediately schedule from that Q.
929 // RegionCriticalPSets summarizes the pressure within the scheduled region and
930 // affects picking from either Q. If scheduling in one direction must
931 // increase pressure for one of the excess PSets, then schedule in that
932 // direction first to provide more freedom in the other direction.
933 if (BotResult == SingleExcess || BotResult == SingleCritical) {
934 DEBUG(dbgs() << "Prefered Bottom Node\n");
938 // Check if the top Q has a better candidate.
939 SchedCandidate TopCand;
940 CandResult TopResult = pickNodeFromQueue(Top.Available,
941 DAG->getTopRPTracker(), TopCand);
942 assert(TopResult != NoCand && "failed to find the first candidate");
944 if (TopResult == SingleExcess || TopResult == SingleCritical) {
945 DEBUG(dbgs() << "Prefered Top Node\n");
949 // If either Q has a single candidate that minimizes pressure above the
950 // original region's pressure pick it.
951 if (BotResult == SingleMax) {
952 DEBUG(dbgs() << "Prefered Bottom Node SingleMax\n");
956 if (TopResult == SingleMax) {
957 DEBUG(dbgs() << "Prefered Top Node SingleMax\n");
961 if (TopCand.SCost > BotCand.SCost) {
962 DEBUG(dbgs() << "Prefered Top Node Cost\n");
966 // Otherwise prefer the bottom candidate in node order.
967 DEBUG(dbgs() << "Prefered Bottom in Node order\n");
972 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
973 SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
974 if (DAG->top() == DAG->bottom()) {
975 assert(Top.Available.empty() && Top.Pending.empty() &&
976 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
980 if (llvm::ForceTopDown) {
981 SU = Top.pickOnlyChoice();
983 SchedCandidate TopCand;
984 CandResult TopResult =
985 pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
986 assert(TopResult != NoCand && "failed to find the first candidate");
991 } else if (llvm::ForceBottomUp) {
992 SU = Bot.pickOnlyChoice();
994 SchedCandidate BotCand;
995 CandResult BotResult =
996 pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
997 assert(BotResult != NoCand && "failed to find the first candidate");
1003 SU = pickNodeBidrectional(IsTopNode);
1005 if (SU->isTopReady())
1006 Top.removeReady(SU);
1007 if (SU->isBottomReady())
1008 Bot.removeReady(SU);
1010 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
1011 << " Scheduling Instruction in cycle "
1012 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
1017 /// Update the scheduler's state after scheduling a node. This is the same node
1018 /// that was just returned by pickNode(). However, VLIWMachineScheduler needs
1019 /// to update it's state based on the current cycle before MachineSchedStrategy
1021 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
1023 SU->TopReadyCycle = Top.CurrCycle;
1026 SU->BotReadyCycle = Bot.CurrCycle;