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 #define DEBUG_TYPE "misched"
17 #include "HexagonMachineScheduler.h"
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) {
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,
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
44 bool VLIWResourceModel::isResourceAvailable(SUnit *SU) {
45 if (!SU || !SU->getInstr())
48 // First see if the pipeline could receive this instruction
49 // in the current cycle.
50 switch (SU->getInstr()->getOpcode()) {
52 if (!ResourcesModel->canReserveResources(SU->getInstr()))
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:
64 // Now see if there are no other dependencies to instructions already
66 for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
67 if (Packet[i]->Succs.size() == 0)
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.
76 if (I->getSUnit() == SU)
83 /// Keep track of available resources.
84 bool VLIWResourceModel::reserveResources(SUnit *SU) {
85 bool startNewCycle = false;
86 // Artificially reset state.
88 ResourcesModel->clearResources();
93 // If this SU does not fit in the packet
95 if (!isResourceAvailable(SU)) {
96 ResourcesModel->clearResources();
102 switch (SU->getInstr()->getOpcode()) {
104 ResourcesModel->reserveResources(SU->getInstr());
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:
118 Packet.push_back(SU);
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());
129 // If packet is now full, reset the state so in the next cycle
131 if (Packet.size() >= InstrItins->SchedModel->IssueWidth) {
132 ResourcesModel->clearResources();
135 startNewCycle = true;
138 return startNewCycle;
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() {
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)
152 buildDAGWithRegPressure();
154 // Postprocess the DAG to add platform specific artificial dependencies.
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));
173 bool IsTopNode = false;
174 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
175 if (!checkSchedLimit())
178 scheduleMI(SU, IsTopNode);
180 updateQueues(SU, IsTopNode);
182 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
187 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
188 DAG = static_cast<VLIWMachineScheduler*>(dag);
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);
199 Top.ResourceModel = new VLIWResourceModel(TM);
200 Bot.ResourceModel = new VLIWResourceModel(TM);
202 assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) &&
203 "-misched-topdown incompatible with -misched-bottomup");
206 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
210 for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
212 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
213 unsigned MinLatency = I->getMinLatency();
215 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
217 if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
218 SU->TopReadyCycle = PredReadyCycle + MinLatency;
220 Top.releaseNode(SU, SU->TopReadyCycle);
223 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
227 assert(SU->getInstr() && "Scheduled SUnit must have instr");
229 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
231 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
232 unsigned MinLatency = I->getMinLatency();
234 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
236 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
237 SU->BotReadyCycle = SuccReadyCycle + MinLatency;
239 Bot.releaseNode(SU, SU->BotReadyCycle);
242 /// Does this SU have a hazard within the current instruction group.
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.
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.
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;
259 if (IssueCount + DAG->getNumMicroOps(SU->getInstr()) > DAG->getIssueWidth())
265 void ConvergingVLIWScheduler::SchedBoundary::releaseNode(SUnit *SU,
266 unsigned ReadyCycle) {
267 if (ReadyCycle < MinReadyCycle)
268 MinReadyCycle = ReadyCycle;
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))
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;
284 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
285 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
287 if (!HazardRec->isEnabled()) {
288 // Bypass HazardRec virtual calls.
289 CurrCycle = NextCycle;
291 // Bypass getHazardType calls in case of long latency.
292 for (; CurrCycle != NextCycle; ++CurrCycle) {
294 HazardRec->AdvanceCycle();
296 HazardRec->RecedeCycle();
301 DEBUG(dbgs() << "*** " << Available.getName() << " cycle "
302 << CurrCycle << '\n');
305 /// Move the boundary of scheduled code by one SUnit.
306 void ConvergingVLIWScheduler::SchedBoundary::bumpNode(SUnit *SU) {
307 bool startNewCycle = false;
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.
316 HazardRec->EmitInstruction(SU);
320 startNewCycle = ResourceModel->reserveResources(SU);
322 // Check the instruction group dispatch limit.
323 // TODO: Check if this SU must end a dispatch group.
324 IssueCount += DAG->getNumMicroOps(SU->getInstr());
326 DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
330 DEBUG(dbgs() << "*** IssueCount " << IssueCount
331 << " at cycle " << CurrCycle << '\n');
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;
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;
347 if (ReadyCycle < MinReadyCycle)
348 MinReadyCycle = ReadyCycle;
350 if (ReadyCycle > CurrCycle)
357 Pending.remove(Pending.begin()+i);
360 CheckPending = false;
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));
368 assert(Pending.isInQueue(SU) && "bad ready count");
369 Pending.remove(Pending.find(SU));
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() {
380 for (unsigned i = 0; Available.empty(); ++i) {
381 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
382 "permanent hazard"); (void)i;
383 ResourceModel->reserveResources(0);
387 if (Available.size() == 1)
388 return *Available.begin();
393 void ConvergingVLIWScheduler::traceCandidate(const char *Label,
395 SUnit *SU, PressureElement P) {
396 dbgs() << Label << " " << Q.getName() << " ";
398 dbgs() << TRI->getRegPressureSetName(P.PSetID) << ":" << P.UnitIncrease
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();
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)
418 OnlyAvailablePred = &Pred;
421 return OnlyAvailablePred;
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();
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)
436 OnlyAvailableSucc = &Succ;
439 return OnlyAvailableSucc;
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;
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,
457 // Initial trivial priority.
460 // Do not waste time on a node that is already scheduled.
461 if (!SU || SU->isScheduled)
464 // Forced priority is high.
465 if (SU->isScheduleHigh)
466 ResCount += PriorityOne;
468 // Critical path first.
469 if (Q.getID() == TopQID) {
470 ResCount += (SU->getHeight() * ScaleTwo);
472 // If resources are available for it, multiply the
473 // chance of scheduling.
474 if (Top.ResourceModel->isResourceAvailable(SU))
475 ResCount <<= FactorOne;
477 ResCount += (SU->getDepth() * ScaleTwo);
479 // If resources are available for it, multiply the
480 // chance of scheduling.
481 if (Bot.ResourceModel->isResourceAvailable(SU))
482 ResCount <<= FactorOne;
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();
493 if (getSingleUnscheduledPred(I->getSUnit()) == SU)
496 // How many unscheduled predecessors block this node?
497 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
499 if (getSingleUnscheduledSucc(I->getSUnit()) == SU)
502 ResCount += (NumNodesBlocking * ScaleTwo);
504 // Factor in reg pressure as a heuristic.
505 ResCount -= (Delta.Excess.UnitIncrease*PriorityThree);
506 ResCount -= (Delta.CriticalMax.UnitIncrease*PriorityThree);
508 DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")");
513 /// Pick the best candidate from the top queue.
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) {
523 // getMaxPressureDelta temporarily modifies the tracker.
524 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
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);
534 int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
536 // Initialize the candidate if needed.
539 Candidate.RPDelta = RPDelta;
540 Candidate.SCost = CurrentCost;
541 FoundCandidate = NodeOrder;
546 if (CurrentCost > Candidate.SCost) {
547 DEBUG(traceCandidate("CCAND", Q, *I));
549 Candidate.RPDelta = RPDelta;
550 Candidate.SCost = CurrentCost;
551 FoundCandidate = BestCost;
555 // Fall through to original instruction order.
556 // Only consider node order if Candidate was chosen from this Q.
557 if (FoundCandidate == NoCand)
560 return FoundCandidate;
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()) {
571 if (SUnit *SU = Top.pickOnlyChoice()) {
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");
581 // If either Q has a single candidate that provides the least increase in
582 // Excess pressure, we can immediately schedule from that Q.
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) {
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");
598 if (TopResult == SingleExcess || TopResult == SingleCritical) {
602 // If either Q has a single candidate that minimizes pressure above the
603 // original region's pressure pick it.
604 if (BotResult == SingleMax) {
608 if (TopResult == SingleMax) {
612 if (TopCand.SCost > BotCand.SCost) {
616 // Otherwise prefer the bottom candidate in node order.
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");
629 if (llvm::ForceTopDown) {
630 SU = Top.pickOnlyChoice();
632 SchedCandidate TopCand;
633 CandResult TopResult =
634 pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
635 assert(TopResult != NoCand && "failed to find the first candidate");
640 } else if (llvm::ForceBottomUp) {
641 SU = Bot.pickOnlyChoice();
643 SchedCandidate BotCand;
644 CandResult BotResult =
645 pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
646 assert(BotResult != NoCand && "failed to find the first candidate");
652 SU = pickNodeBidrectional(IsTopNode);
654 if (SU->isTopReady())
656 if (SU->isBottomReady())
659 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
660 << " Scheduling Instruction in cycle "
661 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
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
670 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
672 SU->TopReadyCycle = Top.CurrCycle;
675 SU->BotReadyCycle = Bot.CurrCycle;