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 "llvm/CodeGen/MachineLoopInfo.h"
17 #include "llvm/IR/Function.h"
21 #define DEBUG_TYPE "misched"
23 /// Platform-specific modifications to DAG.
24 void VLIWMachineScheduler::postprocessDAG() {
25 SUnit* LastSequentialCall = nullptr;
26 // Currently we only catch the situation when compare gets scheduled
27 // before preceding call.
28 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
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));
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
43 bool VLIWResourceModel::isResourceAvailable(SUnit *SU) {
44 if (!SU || !SU->getInstr())
47 // First see if the pipeline could receive this instruction
48 // in the current cycle.
49 switch (SU->getInstr()->getOpcode()) {
51 if (!ResourcesModel->canReserveResources(SU->getInstr()))
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:
63 // Now see if there are no other dependencies to instructions already
65 for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
66 if (Packet[i]->Succs.size() == 0)
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.
75 if (I->getSUnit() == SU)
82 /// Keep track of available resources.
83 bool VLIWResourceModel::reserveResources(SUnit *SU) {
84 bool startNewCycle = false;
85 // Artificially reset state.
87 ResourcesModel->clearResources();
92 // If this SU does not fit in the packet
94 if (!isResourceAvailable(SU)) {
95 ResourcesModel->clearResources();
101 switch (SU->getInstr()->getOpcode()) {
103 ResourcesModel->reserveResources(SU->getInstr());
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:
117 Packet.push_back(SU);
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());
128 // If packet is now full, reset the state so in the next cycle
130 if (Packet.size() >= SchedModel->getIssueWidth()) {
131 ResourcesModel->clearResources();
134 startNewCycle = true;
137 return startNewCycle;
140 /// schedule - Called back from MachineScheduler::runOnMachineFunction
141 /// after setting up the current scheduling region. [RegionBegin, RegionEnd)
142 /// only includes instructions that have DAG nodes, not scheduling boundaries.
143 void VLIWMachineScheduler::schedule() {
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)
151 buildDAGWithRegPressure();
153 // Postprocess the DAG to add platform-specific artificial dependencies.
156 SmallVector<SUnit*, 8> TopRoots, BotRoots;
157 findRootsAndBiasEdges(TopRoots, BotRoots);
159 // Initialize the strategy before modifying the DAG.
160 SchedImpl->initialize(this);
162 // To view Height/Depth correctly, they should be accessed at least once.
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));
179 initQueues(TopRoots, BotRoots);
181 bool IsTopNode = false;
183 DEBUG(dbgs() << "** VLIWMachineScheduler::schedule picking next node\n");
184 SUnit *SU = SchedImpl->pickNode(IsTopNode);
187 if (!checkSchedLimit())
190 scheduleMI(SU, IsTopNode);
192 updateQueues(SU, IsTopNode);
194 // Notify the scheduling strategy after updating the DAG.
195 SchedImpl->schedNode(SU, IsTopNode);
197 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
202 void ConvergingVLIWScheduler::initialize(ScheduleDAGMI *dag) {
203 DAG = static_cast<VLIWMachineScheduler*>(dag);
204 SchedModel = DAG->getSchedModel();
206 Top.init(DAG, SchedModel);
207 Bot.init(DAG, SchedModel);
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);
219 delete Top.ResourceModel;
220 delete Bot.ResourceModel;
221 Top.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
222 Bot.ResourceModel = new VLIWResourceModel(STI, DAG->getSchedModel());
224 assert((!llvm::ForceTopDown || !llvm::ForceBottomUp) &&
225 "-misched-topdown incompatible with -misched-bottomup");
228 void ConvergingVLIWScheduler::releaseTopNode(SUnit *SU) {
232 for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
234 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
235 unsigned MinLatency = I->getLatency();
237 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
239 if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
240 SU->TopReadyCycle = PredReadyCycle + MinLatency;
242 Top.releaseNode(SU, SU->TopReadyCycle);
245 void ConvergingVLIWScheduler::releaseBottomNode(SUnit *SU) {
249 assert(SU->getInstr() && "Scheduled SUnit must have instr");
251 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
253 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
254 unsigned MinLatency = I->getLatency();
256 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
258 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
259 SU->BotReadyCycle = SuccReadyCycle + MinLatency;
261 Bot.releaseNode(SU, SU->BotReadyCycle);
264 /// Does this SU have a hazard within the current instruction group.
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.
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.
276 /// TODO: Also check whether the SU must start a new group.
277 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(SUnit *SU) {
278 if (HazardRec->isEnabled())
279 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
281 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
282 if (IssueCount + uops > SchedModel->getIssueWidth())
288 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(SUnit *SU,
289 unsigned ReadyCycle) {
290 if (ReadyCycle < MinReadyCycle)
291 MinReadyCycle = ReadyCycle;
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))
302 /// Move the boundary of scheduled code by one cycle.
303 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
304 unsigned Width = SchedModel->getIssueWidth();
305 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
307 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
308 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
310 if (!HazardRec->isEnabled()) {
311 // Bypass HazardRec virtual calls.
312 CurrCycle = NextCycle;
314 // Bypass getHazardType calls in case of long latency.
315 for (; CurrCycle != NextCycle; ++CurrCycle) {
317 HazardRec->AdvanceCycle();
319 HazardRec->RecedeCycle();
324 DEBUG(dbgs() << "*** " << Available.getName() << " cycle "
325 << CurrCycle << '\n');
328 /// Move the boundary of scheduled code by one SUnit.
329 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(SUnit *SU) {
330 bool startNewCycle = false;
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.
339 HazardRec->EmitInstruction(SU);
343 startNewCycle = ResourceModel->reserveResources(SU);
345 // Check the instruction group dispatch limit.
346 // TODO: Check if this SU must end a dispatch group.
347 IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
349 DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
353 DEBUG(dbgs() << "*** IssueCount " << IssueCount
354 << " at cycle " << CurrCycle << '\n');
357 /// Release pending ready nodes in to the available queue. This makes them
358 /// visible to heuristics.
359 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
360 // If the available queue is empty, it is safe to reset MinReadyCycle.
361 if (Available.empty())
362 MinReadyCycle = UINT_MAX;
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;
370 if (ReadyCycle < MinReadyCycle)
371 MinReadyCycle = ReadyCycle;
373 if (ReadyCycle > CurrCycle)
380 Pending.remove(Pending.begin()+i);
383 CheckPending = false;
386 /// Remove SU from the ready set for this boundary.
387 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(SUnit *SU) {
388 if (Available.isInQueue(SU))
389 Available.remove(Available.find(SU));
391 assert(Pending.isInQueue(SU) && "bad ready count");
392 Pending.remove(Pending.find(SU));
396 /// If this queue only has one ready candidate, return it. As a side effect,
397 /// advance the cycle until at least one node is ready. If multiple instructions
398 /// are ready, return NULL.
399 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
403 for (unsigned i = 0; Available.empty(); ++i) {
404 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
405 "permanent hazard"); (void)i;
406 ResourceModel->reserveResources(nullptr);
410 if (Available.size() == 1)
411 return *Available.begin();
416 void ConvergingVLIWScheduler::traceCandidate(const char *Label,
418 SUnit *SU, PressureChange P) {
419 dbgs() << Label << " " << Q.getName() << " ";
421 dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
422 << P.getUnitInc() << " ";
429 /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
430 /// of SU, return it, otherwise return null.
431 static SUnit *getSingleUnscheduledPred(SUnit *SU) {
432 SUnit *OnlyAvailablePred = nullptr;
433 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
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)
441 OnlyAvailablePred = &Pred;
444 return OnlyAvailablePred;
447 /// getSingleUnscheduledSucc - If there is exactly one unscheduled successor
448 /// of SU, return it, otherwise return null.
449 static SUnit *getSingleUnscheduledSucc(SUnit *SU) {
450 SUnit *OnlyAvailableSucc = nullptr;
451 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
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)
459 OnlyAvailableSucc = &Succ;
462 return OnlyAvailableSucc;
465 // Constants used to denote relative importance of
466 // heuristic components for cost computation.
467 static const unsigned PriorityOne = 200;
468 static const unsigned PriorityTwo = 50;
469 static const unsigned ScaleTwo = 10;
470 static const unsigned FactorOne = 2;
472 /// Single point to compute overall scheduling cost.
473 /// TODO: More heuristics will be used soon.
474 int ConvergingVLIWScheduler::SchedulingCost(ReadyQueue &Q, SUnit *SU,
475 SchedCandidate &Candidate,
476 RegPressureDelta &Delta,
478 // Initial trivial priority.
481 // Do not waste time on a node that is already scheduled.
482 if (!SU || SU->isScheduled)
485 // Forced priority is high.
486 if (SU->isScheduleHigh)
487 ResCount += PriorityOne;
489 // Critical path first.
490 if (Q.getID() == TopQID) {
491 ResCount += (SU->getHeight() * ScaleTwo);
493 // If resources are available for it, multiply the
494 // chance of scheduling.
495 if (Top.ResourceModel->isResourceAvailable(SU))
496 ResCount <<= FactorOne;
498 ResCount += (SU->getDepth() * ScaleTwo);
500 // If resources are available for it, multiply the
501 // chance of scheduling.
502 if (Bot.ResourceModel->isResourceAvailable(SU))
503 ResCount <<= FactorOne;
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();
514 if (getSingleUnscheduledPred(I->getSUnit()) == SU)
517 // How many unscheduled predecessors block this node?
518 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
520 if (getSingleUnscheduledSucc(I->getSUnit()) == SU)
523 ResCount += (NumNodesBlocking * ScaleTwo);
525 // Factor in reg pressure as a heuristic.
526 ResCount -= (Delta.Excess.getUnitInc()*PriorityTwo);
527 ResCount -= (Delta.CriticalMax.getUnitInc()*PriorityTwo);
529 DEBUG(if (verbose) dbgs() << " Total(" << ResCount << ")");
534 /// Pick the best candidate from the top queue.
536 /// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
537 /// DAG building. To adjust for the current scheduling location we need to
538 /// maintain the number of vreg uses remaining to be top-scheduled.
539 ConvergingVLIWScheduler::CandResult ConvergingVLIWScheduler::
540 pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
541 SchedCandidate &Candidate) {
544 // getMaxPressureDelta temporarily modifies the tracker.
545 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
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);
555 int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
557 // Initialize the candidate if needed.
560 Candidate.RPDelta = RPDelta;
561 Candidate.SCost = CurrentCost;
562 FoundCandidate = NodeOrder;
567 if (CurrentCost > Candidate.SCost) {
568 DEBUG(traceCandidate("CCAND", Q, *I));
570 Candidate.RPDelta = RPDelta;
571 Candidate.SCost = CurrentCost;
572 FoundCandidate = BestCost;
576 // Fall through to original instruction order.
577 // Only consider node order if Candidate was chosen from this Q.
578 if (FoundCandidate == NoCand)
581 return FoundCandidate;
584 /// Pick the best candidate node from either the top or bottom queue.
585 SUnit *ConvergingVLIWScheduler::pickNodeBidrectional(bool &IsTopNode) {
586 // Schedule as far as possible in the direction of no choice. This is most
587 // efficient, but also provides the best heuristics for CriticalPSets.
588 if (SUnit *SU = Bot.pickOnlyChoice()) {
592 if (SUnit *SU = Top.pickOnlyChoice()) {
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");
602 // If either Q has a single candidate that provides the least increase in
603 // Excess pressure, we can immediately schedule from that Q.
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) {
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");
619 if (TopResult == SingleExcess || TopResult == SingleCritical) {
623 // If either Q has a single candidate that minimizes pressure above the
624 // original region's pressure pick it.
625 if (BotResult == SingleMax) {
629 if (TopResult == SingleMax) {
633 if (TopCand.SCost > BotCand.SCost) {
637 // Otherwise prefer the bottom candidate in node order.
642 /// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
643 SUnit *ConvergingVLIWScheduler::pickNode(bool &IsTopNode) {
644 if (DAG->top() == DAG->bottom()) {
645 assert(Top.Available.empty() && Top.Pending.empty() &&
646 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
650 if (llvm::ForceTopDown) {
651 SU = Top.pickOnlyChoice();
653 SchedCandidate TopCand;
654 CandResult TopResult =
655 pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
656 assert(TopResult != NoCand && "failed to find the first candidate");
661 } else if (llvm::ForceBottomUp) {
662 SU = Bot.pickOnlyChoice();
664 SchedCandidate BotCand;
665 CandResult BotResult =
666 pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
667 assert(BotResult != NoCand && "failed to find the first candidate");
673 SU = pickNodeBidrectional(IsTopNode);
675 if (SU->isTopReady())
677 if (SU->isBottomReady())
680 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
681 << " Scheduling Instruction in cycle "
682 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
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
691 void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
693 SU->TopReadyCycle = Top.CurrCycle;
696 SU->BotReadyCycle = Bot.CurrCycle;