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"
22 /// Platform specific modifications to DAG.
23 void VLIWMachineScheduler::postprocessDAG() {
24 SUnit* LastSequentialCall = NULL;
25 // Currently we only catch the situation when compare gets scheduled
26 // before preceding call.
27 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
29 if (SUnits[su].getInstr()->isCall())
30 LastSequentialCall = &(SUnits[su]);
31 // Look for a compare that defines a predicate.
32 else if (SUnits[su].getInstr()->isCompare() && LastSequentialCall)
33 SUnits[su].addPred(SDep(LastSequentialCall, SDep::Barrier));
37 /// Check if scheduling of this SU is possible
38 /// in the current packet.
39 /// It is _not_ precise (statefull), it is more like
40 /// another heuristic. Many corner cases are figured
42 bool VLIWResourceModel::isResourceAvailable(SUnit *SU) {
43 if (!SU || !SU->getInstr())
46 // First see if the pipeline could receive this instruction
47 // in the current cycle.
48 switch (SU->getInstr()->getOpcode()) {
50 if (!ResourcesModel->canReserveResources(SU->getInstr()))
52 case TargetOpcode::EXTRACT_SUBREG:
53 case TargetOpcode::INSERT_SUBREG:
54 case TargetOpcode::SUBREG_TO_REG:
55 case TargetOpcode::REG_SEQUENCE:
56 case TargetOpcode::IMPLICIT_DEF:
57 case TargetOpcode::COPY:
58 case TargetOpcode::INLINEASM:
62 // Now see if there are no other dependencies to instructions already
64 for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
65 if (Packet[i]->Succs.size() == 0)
67 for (SUnit::const_succ_iterator I = Packet[i]->Succs.begin(),
68 E = Packet[i]->Succs.end(); I != E; ++I) {
69 // Since we do not add pseudos to packets, might as well
70 // ignore order dependencies.
74 if (I->getSUnit() == SU)
81 /// Keep track of available resources.
82 bool VLIWResourceModel::reserveResources(SUnit *SU) {
83 bool startNewCycle = false;
84 // Artificially reset state.
86 ResourcesModel->clearResources();
91 // If this SU does not fit in the packet
93 if (!isResourceAvailable(SU)) {
94 ResourcesModel->clearResources();
100 switch (SU->getInstr()->getOpcode()) {
102 ResourcesModel->reserveResources(SU->getInstr());
104 case TargetOpcode::EXTRACT_SUBREG:
105 case TargetOpcode::INSERT_SUBREG:
106 case TargetOpcode::SUBREG_TO_REG:
107 case TargetOpcode::REG_SEQUENCE:
108 case TargetOpcode::IMPLICIT_DEF:
109 case TargetOpcode::KILL:
110 case TargetOpcode::PROLOG_LABEL:
111 case TargetOpcode::EH_LABEL:
112 case TargetOpcode::COPY:
113 case TargetOpcode::INLINEASM:
116 Packet.push_back(SU);
119 DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
120 for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
121 DEBUG(dbgs() << "\t[" << i << "] SU(");
122 DEBUG(dbgs() << Packet[i]->NodeNum << ")\t");
123 DEBUG(Packet[i]->getInstr()->dump());
127 // If packet is now full, reset the state so in the next cycle
129 if (Packet.size() >= SchedModel->getIssueWidth()) {
130 ResourcesModel->clearResources();
133 startNewCycle = true;
136 return startNewCycle;
139 /// schedule - Called back from MachineScheduler::runOnMachineFunction
140 /// after setting up the current scheduling region. [RegionBegin, RegionEnd)
141 /// only includes instructions that have DAG nodes, not scheduling boundaries.
142 void VLIWMachineScheduler::schedule() {
144 << "********** MI Converging Scheduling VLIW BB#" << BB->getNumber()
145 << " " << BB->getName()
146 << " in_func " << BB->getParent()->getFunction()->getName()
147 << " at loop depth " << MLI.getLoopDepth(BB)
150 buildDAGWithRegPressure();
152 // Postprocess the DAG to add platform specific artificial dependencies.
155 SmallVector<SUnit*, 8> TopRoots, BotRoots;
156 findRootsAndBiasEdges(TopRoots, BotRoots);
158 // Initialize the strategy before modifying the DAG.
159 SchedImpl->initialize(this);
161 // To view Height/Depth correctly, they should be accessed at least once.
163 // FIXME: SUnit::dumpAll always recompute depth and height now. The max
164 // depth/height could be computed directly from the roots and leaves.
165 DEBUG(unsigned maxH = 0;
166 for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
167 if (SUnits[su].getHeight() > maxH)
168 maxH = SUnits[su].getHeight();
169 dbgs() << "Max Height " << maxH << "\n";);
170 DEBUG(unsigned maxD = 0;
171 for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
172 if (SUnits[su].getDepth() > maxD)
173 maxD = SUnits[su].getDepth();
174 dbgs() << "Max Depth " << maxD << "\n";);
175 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
176 SUnits[su].dumpAll(this));
178 initQueues(TopRoots, BotRoots);
180 bool IsTopNode = false;
181 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
182 if (!checkSchedLimit())
185 scheduleMI(SU, IsTopNode);
187 updateQueues(SU, IsTopNode);
189 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
194 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
195 DAG = static_cast<VLIWMachineScheduler*>(dag);
196 SchedModel = DAG->getSchedModel();
199 Top.init(DAG, SchedModel);
200 Bot.init(DAG, SchedModel);
202 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
203 // are disabled, then these HazardRecs will be disabled.
204 const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
205 const TargetMachine &TM = DAG->MF.getTarget();
206 delete Top.HazardRec;
207 delete Bot.HazardRec;
208 Top.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG);
209 Bot.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG);
211 Top.ResourceModel = new VLIWResourceModel(TM, DAG->getSchedModel());
212 Bot.ResourceModel = new VLIWResourceModel(TM, DAG->getSchedModel());
214 assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) &&
215 "-misched-topdown incompatible with -misched-bottomup");
218 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
222 for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
224 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
225 unsigned MinLatency = I->getMinLatency();
227 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
229 if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
230 SU->TopReadyCycle = PredReadyCycle + MinLatency;
232 Top.releaseNode(SU, SU->TopReadyCycle);
235 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
239 assert(SU->getInstr() && "Scheduled SUnit must have instr");
241 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
243 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
244 unsigned MinLatency = I->getMinLatency();
246 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
248 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
249 SU->BotReadyCycle = SuccReadyCycle + MinLatency;
251 Bot.releaseNode(SU, SU->BotReadyCycle);
254 /// Does this SU have a hazard within the current instruction group.
256 /// The scheduler supports two modes of hazard recognition. The first is the
257 /// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
258 /// supports highly complicated in-order reservation tables
259 /// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
261 /// The second is a streamlined mechanism that checks for hazards based on
262 /// simple counters that the scheduler itself maintains. It explicitly checks
263 /// for instruction dispatch limitations, including the number of micro-ops that
264 /// can dispatch per cycle.
266 /// TODO: Also check whether the SU must start a new group.
267 bool ConvergingVLIWScheduler::SchedBoundary::checkHazard(SUnit *SU) {
268 if (HazardRec->isEnabled())
269 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
271 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
272 if (IssueCount + uops > SchedModel->getIssueWidth())
278 void ConvergingVLIWScheduler::SchedBoundary::releaseNode(SUnit *SU,
279 unsigned ReadyCycle) {
280 if (ReadyCycle < MinReadyCycle)
281 MinReadyCycle = ReadyCycle;
283 // Check for interlocks first. For the purpose of other heuristics, an
284 // instruction that cannot issue appears as if it's not in the ReadyQueue.
285 if (ReadyCycle > CurrCycle || checkHazard(SU))
292 /// Move the boundary of scheduled code by one cycle.
293 void ConvergingVLIWScheduler::SchedBoundary::bumpCycle() {
294 unsigned Width = SchedModel->getIssueWidth();
295 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
297 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
298 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
300 if (!HazardRec->isEnabled()) {
301 // Bypass HazardRec virtual calls.
302 CurrCycle = NextCycle;
304 // Bypass getHazardType calls in case of long latency.
305 for (; CurrCycle != NextCycle; ++CurrCycle) {
307 HazardRec->AdvanceCycle();
309 HazardRec->RecedeCycle();
314 DEBUG(dbgs() << "*** " << Available.getName() << " cycle "
315 << CurrCycle << '\n');
318 /// Move the boundary of scheduled code by one SUnit.
319 void ConvergingVLIWScheduler::SchedBoundary::bumpNode(SUnit *SU) {
320 bool startNewCycle = false;
322 // Update the reservation table.
323 if (HazardRec->isEnabled()) {
324 if (!isTop() && SU->isCall) {
325 // Calls are scheduled with their preceding instructions. For bottom-up
326 // scheduling, clear the pipeline state before emitting.
329 HazardRec->EmitInstruction(SU);
333 startNewCycle = ResourceModel->reserveResources(SU);
335 // Check the instruction group dispatch limit.
336 // TODO: Check if this SU must end a dispatch group.
337 IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
339 DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
343 DEBUG(dbgs() << "*** IssueCount " << IssueCount
344 << " at cycle " << CurrCycle << '\n');
347 /// Release pending ready nodes in to the available queue. This makes them
348 /// visible to heuristics.
349 void ConvergingVLIWScheduler::SchedBoundary::releasePending() {
350 // If the available queue is empty, it is safe to reset MinReadyCycle.
351 if (Available.empty())
352 MinReadyCycle = UINT_MAX;
354 // Check to see if any of the pending instructions are ready to issue. If
355 // so, add them to the available queue.
356 for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
357 SUnit *SU = *(Pending.begin()+i);
358 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
360 if (ReadyCycle < MinReadyCycle)
361 MinReadyCycle = ReadyCycle;
363 if (ReadyCycle > CurrCycle)
370 Pending.remove(Pending.begin()+i);
373 CheckPending = false;
376 /// Remove SU from the ready set for this boundary.
377 void ConvergingVLIWScheduler::SchedBoundary::removeReady(SUnit *SU) {
378 if (Available.isInQueue(SU))
379 Available.remove(Available.find(SU));
381 assert(Pending.isInQueue(SU) && "bad ready count");
382 Pending.remove(Pending.find(SU));
386 /// If this queue only has one ready candidate, return it. As a side effect,
387 /// advance the cycle until at least one node is ready. If multiple instructions
388 /// are ready, return NULL.
389 SUnit *ConvergingVLIWScheduler::SchedBoundary::pickOnlyChoice() {
393 for (unsigned i = 0; Available.empty(); ++i) {
394 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
395 "permanent hazard"); (void)i;
396 ResourceModel->reserveResources(0);
400 if (Available.size() == 1)
401 return *Available.begin();
406 void ConvergingVLIWScheduler::traceCandidate(const char *Label,
408 SUnit *SU, PressureElement P) {
409 dbgs() << Label << " " << Q.getName() << " ";
411 dbgs() << TRI->getRegPressureSetName(P.PSetID) << ":" << P.UnitIncrease
419 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
420 /// of SU, return it, otherwise return null.
421 static SUnit *getSingleUnscheduledPred(SUnit *SU) {
422 SUnit *OnlyAvailablePred = 0;
423 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
425 SUnit &Pred = *I->getSUnit();
426 if (!Pred.isScheduled) {
427 // We found an available, but not scheduled, predecessor. If it's the
428 // only one we have found, keep track of it... otherwise give up.
429 if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
431 OnlyAvailablePred = &Pred;
434 return OnlyAvailablePred;
437 /// getSingleUnscheduledSucc - If there is exactly one unscheduled successor
438 /// of SU, return it, otherwise return null.
439 static SUnit *getSingleUnscheduledSucc(SUnit *SU) {
440 SUnit *OnlyAvailableSucc = 0;
441 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
443 SUnit &Succ = *I->getSUnit();
444 if (!Succ.isScheduled) {
445 // We found an available, but not scheduled, successor. If it's the
446 // only one we have found, keep track of it... otherwise give up.
447 if (OnlyAvailableSucc && OnlyAvailableSucc != &Succ)
449 OnlyAvailableSucc = &Succ;
452 return OnlyAvailableSucc;
455 // Constants used to denote relative importance of
456 // heuristic components for cost computation.
457 static const unsigned PriorityOne = 200;
458 static const unsigned PriorityTwo = 100;
459 static const unsigned PriorityThree = 50;
460 static const unsigned PriorityFour = 20;
461 static const unsigned ScaleTwo = 10;
462 static const unsigned FactorOne = 2;
464 /// Single point to compute overall scheduling cost.
465 /// TODO: More heuristics will be used soon.
466 int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
467 SchedCandidate &Candidate,
468 RegPressureDelta &Delta,
470 // Initial trivial priority.
473 // Do not waste time on a node that is already scheduled.
474 if (!SU || SU->isScheduled)
477 // Forced priority is high.
478 if (SU->isScheduleHigh)
479 ResCount += PriorityOne;
481 // Critical path first.
482 if (Q.getID() == TopQID) {
483 ResCount += (SU->getHeight() * ScaleTwo);
485 // If resources are available for it, multiply the
486 // chance of scheduling.
487 if (Top.ResourceModel->isResourceAvailable(SU))
488 ResCount <<= FactorOne;
490 ResCount += (SU->getDepth() * ScaleTwo);
492 // If resources are available for it, multiply the
493 // chance of scheduling.
494 if (Bot.ResourceModel->isResourceAvailable(SU))
495 ResCount <<= FactorOne;
498 unsigned NumNodesBlocking = 0;
499 if (Q.getID() == TopQID) {
500 // How many SUs does it block from scheduling?
501 // Look at all of the successors of this node.
502 // Count the number of nodes that
503 // this node is the sole unscheduled node for.
504 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
506 if (getSingleUnscheduledPred(I->getSUnit()) == SU)
509 // How many unscheduled predecessors block this node?
510 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
512 if (getSingleUnscheduledSucc(I->getSUnit()) == SU)
515 ResCount += (NumNodesBlocking * ScaleTwo);
517 // Factor in reg pressure as a heuristic.
518 ResCount -= (Delta.Excess.UnitIncrease*PriorityThree);
519 ResCount -= (Delta.CriticalMax.UnitIncrease*PriorityThree);
521 DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")");
526 /// Pick the best candidate from the top queue.
528 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
529 /// DAG building. To adjust for the current scheduling location we need to
530 /// maintain the number of vreg uses remaining to be top-scheduled.
531 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
532 pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
533 SchedCandidate &Candidate) {
536 // getMaxPressureDelta temporarily modifies the tracker.
537 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
539 // BestSU remains NULL if no top candidates beat the best existing candidate.
540 CandResult FoundCandidate = NoCand;
541 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
542 RegPressureDelta RPDelta;
543 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
544 DAG->getRegionCriticalPSets(),
545 DAG->getRegPressure().MaxSetPressure);
547 int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
549 // Initialize the candidate if needed.
552 Candidate.RPDelta = RPDelta;
553 Candidate.SCost = CurrentCost;
554 FoundCandidate = NodeOrder;
559 if (CurrentCost > Candidate.SCost) {
560 DEBUG(traceCandidate("CCAND", Q, *I));
562 Candidate.RPDelta = RPDelta;
563 Candidate.SCost = CurrentCost;
564 FoundCandidate = BestCost;
568 // Fall through to original instruction order.
569 // Only consider node order if Candidate was chosen from this Q.
570 if (FoundCandidate == NoCand)
573 return FoundCandidate;
576 /// Pick the best candidate node from either the top or bottom queue.
577 SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) {
578 // Schedule as far as possible in the direction of no choice. This is most
579 // efficient, but also provides the best heuristics for CriticalPSets.
580 if (SUnit *SU = Bot.pickOnlyChoice()) {
584 if (SUnit *SU = Top.pickOnlyChoice()) {
588 SchedCandidate BotCand;
589 // Prefer bottom scheduling when heuristics are silent.
590 CandResult BotResult = pickNodeFromQueue(Bot.Available,
591 DAG->getBotRPTracker(), BotCand);
592 assert(BotResult != NoCand && "failed to find the first candidate");
594 // If either Q has a single candidate that provides the least increase in
595 // Excess pressure, we can immediately schedule from that Q.
597 // RegionCriticalPSets summarizes the pressure within the scheduled region and
598 // affects picking from either Q. If scheduling in one direction must
599 // increase pressure for one of the excess PSets, then schedule in that
600 // direction first to provide more freedom in the other direction.
601 if (BotResult == SingleExcess || BotResult == SingleCritical) {
605 // Check if the top Q has a better candidate.
606 SchedCandidate TopCand;
607 CandResult TopResult = pickNodeFromQueue(Top.Available,
608 DAG->getTopRPTracker(), TopCand);
609 assert(TopResult != NoCand && "failed to find the first candidate");
611 if (TopResult == SingleExcess || TopResult == SingleCritical) {
615 // If either Q has a single candidate that minimizes pressure above the
616 // original region's pressure pick it.
617 if (BotResult == SingleMax) {
621 if (TopResult == SingleMax) {
625 if (TopCand.SCost > BotCand.SCost) {
629 // Otherwise prefer the bottom candidate in node order.
634 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
635 SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
636 if (DAG->top() == DAG->bottom()) {
637 assert(Top.Available.empty() && Top.Pending.empty() &&
638 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
642 if (llvm::ForceTopDown) {
643 SU = Top.pickOnlyChoice();
645 SchedCandidate TopCand;
646 CandResult TopResult =
647 pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
648 assert(TopResult != NoCand && "failed to find the first candidate");
653 } else if (llvm::ForceBottomUp) {
654 SU = Bot.pickOnlyChoice();
656 SchedCandidate BotCand;
657 CandResult BotResult =
658 pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
659 assert(BotResult != NoCand && "failed to find the first candidate");
665 SU = pickNodeBidrectional(IsTopNode);
667 if (SU->isTopReady())
669 if (SU->isBottomReady())
672 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
673 << " Scheduling Instruction in cycle "
674 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
679 /// Update the scheduler's state after scheduling a node. This is the same node
680 /// that was just returned by pickNode(). However, VLIWMachineScheduler needs
681 /// to update it's state based on the current cycle before MachineSchedStrategy
683 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
685 SU->TopReadyCycle = Top.CurrCycle;
688 SU->BotReadyCycle = Bot.CurrCycle;