LLVM 24.0.0git
VLIWMachineScheduler.cpp
Go to the documentation of this file.
1//===- VLIWMachineScheduler.cpp - VLIW-Focused Scheduling Pass ------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// MachineScheduler schedules machine instructions after phi elimination. It
10// preserves LiveIntervals so it can be invoked before register allocation.
11//
12//===----------------------------------------------------------------------===//
13
15#include "CodeGenOptions.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/Format.h"
34#include <algorithm>
35#include <cassert>
36#include <iomanip>
37#include <limits>
38#include <sstream>
39
40using namespace llvm;
41
42#define DEBUG_TYPE "machine-scheduler"
43
45 const TargetSchedModel *SM)
46 : TII(STI.getInstrInfo()), SchedModel(SM) {
48
49 // This hard requirement could be relaxed,
50 // but for now do not let it proceed.
51 assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
52
53 Packet.reserve(SchedModel->getIssueWidth());
54 Packet.clear();
55 ResourcesModel->clearResources();
56}
57
59 Packet.clear();
60 ResourcesModel->clearResources();
61}
62
64
65/// Return true if there is a dependence between SUd and SUu.
66bool VLIWResourceModel::hasDependence(const SUnit *SUd, const SUnit *SUu) {
67 if (SUd->Succs.size() == 0)
68 return false;
69
70 for (const auto &S : SUd->Succs) {
71 // Since we do not add pseudos to packets, might as well
72 // ignore order dependencies.
73 if (S.isCtrl())
74 continue;
75
76 if (S.getSUnit() == SUu && S.getLatency() > 0)
77 return true;
78 }
79 return false;
80}
81
82/// Check if scheduling of this SU is possible
83/// in the current packet.
84/// It is _not_ precise (statefull), it is more like
85/// another heuristic. Many corner cases are figured
86/// empirically.
88 if (!SU || !SU->getInstr())
89 return false;
90
91 // First see if the pipeline could receive this instruction
92 // in the current cycle.
93 switch (SU->getInstr()->getOpcode()) {
94 default:
95 if (!ResourcesModel->canReserveResources(*SU->getInstr()))
96 return false;
97 break;
98 case TargetOpcode::EXTRACT_SUBREG:
99 case TargetOpcode::INSERT_SUBREG:
100 case TargetOpcode::SUBREG_TO_REG:
101 case TargetOpcode::REG_SEQUENCE:
102 case TargetOpcode::IMPLICIT_DEF:
103 case TargetOpcode::COPY:
104 case TargetOpcode::INLINEASM:
105 case TargetOpcode::INLINEASM_BR:
106 break;
107 }
108
109 // Now see if there are no other dependencies to instructions already
110 // in the packet.
111 if (IsTop) {
112 for (const SUnit *U : Packet)
113 if (hasDependence(U, SU))
114 return false;
115 } else {
116 for (const SUnit *U : Packet)
117 if (hasDependence(SU, U))
118 return false;
119 }
120 return true;
121}
122
123/// Keep track of available resources.
125 bool startNewCycle = false;
126 // Artificially reset state.
127 if (!SU) {
128 reset();
129 TotalPackets++;
130 return false;
131 }
132 // If this SU does not fit in the packet or the packet is now full
133 // start a new one.
134 if (!isResourceAvailable(SU, IsTop) ||
135 Packet.size() >= SchedModel->getIssueWidth()) {
136 reset();
137 TotalPackets++;
138 startNewCycle = true;
139 }
140
141 switch (SU->getInstr()->getOpcode()) {
142 default:
143 ResourcesModel->reserveResources(*SU->getInstr());
144 break;
145 case TargetOpcode::EXTRACT_SUBREG:
146 case TargetOpcode::INSERT_SUBREG:
147 case TargetOpcode::SUBREG_TO_REG:
148 case TargetOpcode::REG_SEQUENCE:
149 case TargetOpcode::IMPLICIT_DEF:
150 case TargetOpcode::KILL:
151 case TargetOpcode::CFI_INSTRUCTION:
152 case TargetOpcode::EH_LABEL:
153 case TargetOpcode::COPY:
154 case TargetOpcode::INLINEASM:
155 case TargetOpcode::INLINEASM_BR:
156 break;
157 }
158 Packet.push_back(SU);
159
160#ifndef NDEBUG
161 LLVM_DEBUG(dbgs() << "Packet[" << TotalPackets << "]:\n");
162 for (unsigned i = 0, e = Packet.size(); i != e; ++i) {
163 LLVM_DEBUG(dbgs() << "\t[" << i << "] " << *Packet[i] << "\t");
164 LLVM_DEBUG(Packet[i]->getInstr()->dump());
165 }
166#endif
167
168 return startNewCycle;
169}
170
175
176/// schedule - Called back from MachineScheduler::runOnMachineFunction
177/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
178/// only includes instructions that have DAG nodes, not scheduling boundaries.
180 LLVM_DEBUG(dbgs() << "********** MI Converging Scheduling VLIW "
181 << printMBBReference(*BB) << " " << BB->getName()
182 << " in_func " << BB->getParent()->getName()
183 << " at loop depth " << MLI->getLoopDepth(BB) << " \n");
184
186
187 Topo.InitDAGTopologicalSorting();
188
189 // Postprocess the DAG to add platform-specific artificial dependencies.
191
192 SmallVector<SUnit *, 8> TopRoots, BotRoots;
193 findRootsAndBiasEdges(TopRoots, BotRoots);
194
195 // Initialize the strategy before modifying the DAG.
196 SchedImpl->initialize(this);
197
198 LLVM_DEBUG({
199 unsigned maxH = 0;
200 for (const SUnit &SU : SUnits)
201 if (SU.getHeight() > maxH)
202 maxH = SU.getHeight();
203 dbgs() << "Max Height " << maxH << "\n";
204 });
205 LLVM_DEBUG({
206 unsigned maxD = 0;
207 for (const SUnit &SU : SUnits)
208 if (SU.getDepth() > maxD)
209 maxD = SU.getDepth();
210 dbgs() << "Max Depth " << maxD << "\n";
211 });
212 LLVM_DEBUG(dump());
214 viewGraph();
215
216 initQueues(TopRoots, BotRoots);
217
218 bool IsTopNode = false;
219 while (true) {
221 dbgs() << "** VLIWMachineScheduler::schedule picking next node\n");
222 SUnit *SU = SchedImpl->pickNode(IsTopNode);
223 if (!SU)
224 break;
225
226 if (!checkSchedLimit())
227 break;
228
229 scheduleMI(SU, IsTopNode);
230
231 // Notify the scheduling strategy after updating the DAG.
232 SchedImpl->schedNode(SU, IsTopNode);
233
234 updateQueues(SU, IsTopNode);
235 }
236 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
237
239
240 LLVM_DEBUG({
241 dbgs() << "*** Final schedule for "
242 << printMBBReference(*begin()->getParent()) << " ***\n";
243 dumpSchedule();
244 dbgs() << '\n';
245 });
246}
247
249 DAG = static_cast<VLIWMachineScheduler *>(dag);
250 SchedModel = DAG->getSchedModel();
251
252 Top.init(DAG, SchedModel);
253 Bot.init(DAG, SchedModel);
254
255 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
256 // are disabled, then these HazardRecs will be disabled.
257 const InstrItineraryData *Itin = DAG->getSchedModel()->getInstrItineraries();
258 const TargetSubtargetInfo &STI = DAG->MF.getSubtarget();
259 const TargetInstrInfo *TII = STI.getInstrInfo();
260 delete Top.HazardRec;
261 delete Bot.HazardRec;
262 Top.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
263 Bot.HazardRec = TII->CreateTargetMIHazardRecognizer(Itin, DAG);
264
265 delete Top.ResourceModel;
266 delete Bot.ResourceModel;
267 Top.ResourceModel = createVLIWResourceModel(STI, DAG->getSchedModel());
268 Bot.ResourceModel = createVLIWResourceModel(STI, DAG->getSchedModel());
269
270 const std::vector<unsigned> &MaxPressure =
271 DAG->getRegPressure().MaxSetPressure;
272 HighPressureSets.assign(MaxPressure.size(), false);
273 for (unsigned i = 0, e = MaxPressure.size(); i < e; ++i) {
274 unsigned Limit = DAG->getRegClassInfo()->getRegPressureSetLimit(i);
276 ((float)MaxPressure[i] >
277 ((float)Limit * DAG->Opts.vliw_misched_reg_pressure));
278 }
279}
280
285
287 for (const SDep &PI : SU->Preds) {
288 unsigned PredReadyCycle = PI.getSUnit()->TopReadyCycle;
289 unsigned MinLatency = PI.getLatency();
290#ifndef NDEBUG
291 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
292#endif
293 if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
294 SU->TopReadyCycle = PredReadyCycle + MinLatency;
295 }
296
297 if (!SU->isScheduled)
298 Top.releaseNode(SU, SU->TopReadyCycle);
299}
300
302 assert(SU->getInstr() && "Scheduled SUnit must have instr");
303
304 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); I != E;
305 ++I) {
306 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
307 unsigned MinLatency = I->getLatency();
308#ifndef NDEBUG
309 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
310#endif
311 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
312 SU->BotReadyCycle = SuccReadyCycle + MinLatency;
313 }
314
315 if (!SU->isScheduled)
316 Bot.releaseNode(SU, SU->BotReadyCycle);
317}
318
323
324/// Does this SU have a hazard within the current instruction group.
325///
326/// The scheduler supports two modes of hazard recognition. The first is the
327/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
328/// supports highly complicated in-order reservation tables
329/// (ScoreboardHazardRecognizer) and arbitrary target-specific logic.
330///
331/// The second is a streamlined mechanism that checks for hazards based on
332/// simple counters that the scheduler itself maintains. It explicitly checks
333/// for instruction dispatch limitations, including the number of micro-ops that
334/// can dispatch per cycle.
335///
336/// TODO: Also check whether the SU must start a new group.
338 if (HazardRec->isEnabled())
339 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
340
341 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
342 if (IssueCount + uops > SchedModel->getIssueWidth())
343 return true;
344
345 return false;
346}
347
349 SUnit *SU, unsigned ReadyCycle) {
350 if (ReadyCycle < MinReadyCycle)
351 MinReadyCycle = ReadyCycle;
352
353 // Check for interlocks first. For the purpose of other heuristics, an
354 // instruction that cannot issue appears as if it's not in the ReadyQueue.
355 if (ReadyCycle > CurrCycle || checkHazard(SU))
356
357 Pending.push(SU);
358 else
359 Available.push(SU);
360}
361
362/// Move the boundary of scheduled code by one cycle.
364 unsigned Width = SchedModel->getIssueWidth();
365 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
366
367 assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
368 "MinReadyCycle uninitialized");
369 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
370
371 if (!HazardRec->isEnabled()) {
372 // Bypass HazardRec virtual calls.
373 CurrCycle = NextCycle;
374 } else {
375 // Bypass getHazardType calls in case of long latency.
376 for (; CurrCycle != NextCycle; ++CurrCycle) {
377 if (isTop())
378 HazardRec->AdvanceCycle();
379 else
380 HazardRec->RecedeCycle();
381 }
382 }
383 CheckPending = true;
384
385 LLVM_DEBUG(dbgs() << "*** Next cycle " << Available.getName() << " cycle "
386 << CurrCycle << '\n');
387}
388
389/// Move the boundary of scheduled code by one SUnit.
391 bool startNewCycle = false;
392
393 // Update the reservation table.
394 if (HazardRec->isEnabled()) {
395 if (!isTop() && SU->isCall) {
396 // Calls are scheduled with their preceding instructions. For bottom-up
397 // scheduling, clear the pipeline state before emitting.
398 HazardRec->Reset();
399 }
400 HazardRec->EmitInstruction(SU);
401 }
402
403 // Update DFA model.
404 startNewCycle = ResourceModel->reserveResources(SU, isTop());
405
406 // Check the instruction group dispatch limit.
407 // TODO: Check if this SU must end a dispatch group.
408 IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
409 if (startNewCycle) {
410 LLVM_DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
411 bumpCycle();
412 } else
413 LLVM_DEBUG(dbgs() << "*** IssueCount " << IssueCount << " at cycle "
414 << CurrCycle << '\n');
415}
416
417/// Release pending ready nodes in to the available queue. This makes them
418/// visible to heuristics.
420 // If the available queue is empty, it is safe to reset MinReadyCycle.
421 if (Available.empty())
422 MinReadyCycle = std::numeric_limits<unsigned>::max();
423
424 // Check to see if any of the pending instructions are ready to issue. If
425 // so, add them to the available queue.
426 for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
427 SUnit *SU = *(Pending.begin() + i);
428 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
429
430 if (ReadyCycle < MinReadyCycle)
431 MinReadyCycle = ReadyCycle;
432
433 if (ReadyCycle > CurrCycle)
434 continue;
435
436 if (checkHazard(SU))
437 continue;
438
439 Available.push(SU);
440 Pending.remove(Pending.begin() + i);
441 --i;
442 --e;
443 }
444 CheckPending = false;
445}
446
447/// Remove SU from the ready set for this boundary.
449 if (Available.isInQueue(SU))
450 Available.remove(Available.find(SU));
451 else {
452 assert(Pending.isInQueue(SU) && "bad ready count");
453 Pending.remove(Pending.find(SU));
454 }
455}
456
457/// If this queue only has one ready candidate, return it. As a side effect,
458/// advance the cycle until at least one node is ready. If multiple instructions
459/// are ready, return NULL.
461 if (CheckPending)
463
464 auto AdvanceCycle = [this]() {
465 if (Available.empty())
466 return true;
467 if (Available.size() == 1 && Pending.size() > 0)
468 return !ResourceModel->isResourceAvailable(*Available.begin(), isTop()) ||
469 getWeakLeft(*Available.begin(), isTop()) != 0;
470 return false;
471 };
472 for (unsigned i = 0; AdvanceCycle(); ++i) {
473 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
474 "permanent hazard");
475 (void)i;
476 ResourceModel->reserveResources(nullptr, isTop());
477 bumpCycle();
479 }
480 if (Available.size() == 1)
481 return *Available.begin();
482 return nullptr;
483}
484
485#ifndef NDEBUG
487 const ReadyQueue &Q, SUnit *SU,
488 int Cost, PressureChange P) {
489 dbgs() << Label << " " << Q.getName() << " ";
490 if (P.isValid())
491 dbgs() << DAG->TRI->getRegPressureSetName(P.getPSet()) << ":"
492 << P.getUnitInc() << " ";
493 else
494 dbgs() << " ";
495 dbgs() << "cost(" << Cost << ")\t";
496 DAG->dumpNode(*SU);
497}
498
499// Very detailed queue dump, to be used with higher verbosity levels.
501 const RegPressureTracker &RPTracker, SchedCandidate &Candidate,
502 ReadyQueue &Q) {
503 RegPressureTracker &TempTracker = const_cast<RegPressureTracker &>(RPTracker);
504
505 dbgs() << ">>> " << Q.getName() << "\n";
506 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
507 RegPressureDelta RPDelta;
508 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
509 DAG->getRegionCriticalPSets(),
510 DAG->getRegPressure().MaxSetPressure);
511 std::string SUStr;
512 raw_string_ostream(SUStr) << **I;
513 dbgs() << left_justify(SUStr, 7);
514 SchedulingCost(Q, *I, Candidate, RPDelta, true);
515 dbgs() << "\t";
516 (*I)->getInstr()->dump();
517 }
518 dbgs() << "\n";
519}
520#endif
521
522/// isSingleUnscheduledPred - If SU2 is the only unscheduled predecessor
523/// of SU, return true (we may have duplicates)
524static inline bool isSingleUnscheduledPred(SUnit *SU, SUnit *SU2) {
525 if (SU->NumPredsLeft == 0)
526 return false;
527
528 for (auto &Pred : SU->Preds) {
529 // We found an available, but not scheduled, predecessor.
530 if (!Pred.getSUnit()->isScheduled && (Pred.getSUnit() != SU2))
531 return false;
532 }
533
534 return true;
535}
536
537/// isSingleUnscheduledSucc - If SU2 is the only unscheduled successor
538/// of SU, return true (we may have duplicates)
539static inline bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2) {
540 if (SU->NumSuccsLeft == 0)
541 return false;
542
543 for (auto &Succ : SU->Succs) {
544 // We found an available, but not scheduled, successor.
545 if (!Succ.getSUnit()->isScheduled && (Succ.getSUnit() != SU2))
546 return false;
547 }
548 return true;
549}
550
551/// Check if the instruction changes the register pressure of a register in the
552/// high pressure set. The function returns a negative value if the pressure
553/// decreases and a positive value is the pressure increases. If the instruction
554/// doesn't use a high pressure register or doesn't change the register
555/// pressure, then return 0.
556int ConvergingVLIWScheduler::pressureChange(const SUnit *SU, bool isBotUp) {
557 PressureDiff &PD = DAG->getPressureDiff(SU);
558 for (const auto &P : PD) {
559 if (!P.isValid())
560 continue;
561 // The pressure differences are computed bottom-up, so the comparison for
562 // an increase is positive in the bottom direction, but negative in the
563 // top-down direction.
564 if (HighPressureSets[P.getPSet()])
565 return (isBotUp ? P.getUnitInc() : -P.getUnitInc());
566 }
567 return 0;
568}
569
570/// Single point to compute overall scheduling cost.
571/// TODO: More heuristics will be used soon.
573 SchedCandidate &Candidate,
574 RegPressureDelta &Delta,
575 bool verbose) {
576 // Initial trivial priority.
577 int ResCount = 1;
578
579 // Do not waste time on a node that is already scheduled.
580 if (!SU || SU->isScheduled)
581 return ResCount;
582
583 LLVM_DEBUG(if (verbose) dbgs()
584 << ((Q.getID() == TopQID) ? "(top|" : "(bot|"));
585 // Forced priority is high.
586 if (SU->isScheduleHigh) {
587 ResCount += PriorityOne;
588 LLVM_DEBUG(dbgs() << "H|");
589 }
590
591 unsigned IsAvailableAmt = 0;
592 // Critical path first.
593 if (Q.getID() == TopQID) {
594 if (Top.isLatencyBound(SU)) {
595 LLVM_DEBUG(if (verbose) dbgs() << "LB|");
596 ResCount += (SU->getHeight() * ScaleTwo);
597 }
598
599 LLVM_DEBUG(if (verbose) {
600 std::stringstream dbgstr;
601 dbgstr << "h" << std::setw(3) << SU->getHeight() << "|";
602 dbgs() << dbgstr.str();
603 });
604
605 // If resources are available for it, multiply the
606 // chance of scheduling.
607 if (Top.ResourceModel->isResourceAvailable(SU, true)) {
608 IsAvailableAmt = (PriorityTwo + PriorityThree);
609 ResCount += IsAvailableAmt;
610 LLVM_DEBUG(if (verbose) dbgs() << "A|");
611 } else
612 LLVM_DEBUG(if (verbose) dbgs() << " |");
613 } else {
614 if (Bot.isLatencyBound(SU)) {
615 LLVM_DEBUG(if (verbose) dbgs() << "LB|");
616 ResCount += (SU->getDepth() * ScaleTwo);
617 }
618
619 LLVM_DEBUG(if (verbose) {
620 std::stringstream dbgstr;
621 dbgstr << "d" << std::setw(3) << SU->getDepth() << "|";
622 dbgs() << dbgstr.str();
623 });
624
625 // If resources are available for it, multiply the
626 // chance of scheduling.
627 if (Bot.ResourceModel->isResourceAvailable(SU, false)) {
628 IsAvailableAmt = (PriorityTwo + PriorityThree);
629 ResCount += IsAvailableAmt;
630 LLVM_DEBUG(if (verbose) dbgs() << "A|");
631 } else
632 LLVM_DEBUG(if (verbose) dbgs() << " |");
633 }
634
635 unsigned NumNodesBlocking = 0;
636 if (Q.getID() == TopQID) {
637 // How many SUs does it block from scheduling?
638 // Look at all of the successors of this node.
639 // Count the number of nodes that
640 // this node is the sole unscheduled node for.
641 if (Top.isLatencyBound(SU))
642 for (const SDep &SI : SU->Succs)
643 if (isSingleUnscheduledPred(SI.getSUnit(), SU))
644 ++NumNodesBlocking;
645 } else {
646 // How many unscheduled predecessors block this node?
647 if (Bot.isLatencyBound(SU))
648 for (const SDep &PI : SU->Preds)
649 if (isSingleUnscheduledSucc(PI.getSUnit(), SU))
650 ++NumNodesBlocking;
651 }
652 ResCount += (NumNodesBlocking * ScaleTwo);
653
654 LLVM_DEBUG(if (verbose) {
655 std::stringstream dbgstr;
656 dbgstr << "blk " << std::setw(2) << NumNodesBlocking << ")|";
657 dbgs() << dbgstr.str();
658 });
659
660 // Factor in reg pressure as a heuristic.
661 if (!DAG->Opts.vliw_misched_ignore_bb_reg_pressure) {
662 // Decrease priority by the amount that register pressure exceeds the limit.
663 ResCount -= (Delta.Excess.getUnitInc() * PriorityOne);
664 // Decrease priority if register pressure exceeds the limit.
665 ResCount -= (Delta.CriticalMax.getUnitInc() * PriorityOne);
666 // Decrease priority slightly if register pressure would increase over the
667 // current maximum.
668 ResCount -= (Delta.CurrentMax.getUnitInc() * PriorityTwo);
669 // If there are register pressure issues, then we remove the value added for
670 // the instruction being available. The rationale is that we really don't
671 // want to schedule an instruction that causes a spill.
672 if (IsAvailableAmt && pressureChange(SU, Q.getID() != TopQID) > 0 &&
673 (Delta.Excess.getUnitInc() || Delta.CriticalMax.getUnitInc() ||
674 Delta.CurrentMax.getUnitInc()))
675 ResCount -= IsAvailableAmt;
676 LLVM_DEBUG(if (verbose) {
677 dbgs() << "RP " << Delta.Excess.getUnitInc() << "/"
678 << Delta.CriticalMax.getUnitInc() << "/"
679 << Delta.CurrentMax.getUnitInc() << ")|";
680 });
681 }
682
683 // Give preference to a zero latency instruction if the dependent
684 // instruction is in the current packet.
685 if (Q.getID() == TopQID && getWeakLeft(SU, true) == 0) {
686 for (const SDep &PI : SU->Preds) {
687 if (!PI.getSUnit()->getInstr()->isPseudo() && PI.isAssignedRegDep() &&
688 PI.getLatency() == 0 &&
689 Top.ResourceModel->isInPacket(PI.getSUnit())) {
690 ResCount += PriorityThree;
691 LLVM_DEBUG(if (verbose) dbgs() << "Z|");
692 }
693 }
694 } else if (Q.getID() == BotQID && getWeakLeft(SU, false) == 0) {
695 for (const SDep &SI : SU->Succs) {
696 if (!SI.getSUnit()->getInstr()->isPseudo() && SI.isAssignedRegDep() &&
697 SI.getLatency() == 0 &&
698 Bot.ResourceModel->isInPacket(SI.getSUnit())) {
699 ResCount += PriorityThree;
700 LLVM_DEBUG(if (verbose) dbgs() << "Z|");
701 }
702 }
703 }
704
705 // If the instruction has a non-zero latency dependence with an instruction in
706 // the current packet, then it should not be scheduled yet. The case occurs
707 // when the dependent instruction is scheduled in a new packet, so the
708 // scheduler updates the current cycle and pending instructions become
709 // available.
710 if (DAG->Opts.vliw_misched_check_early_avail) {
711 if (Q.getID() == TopQID) {
712 for (const auto &PI : SU->Preds) {
713 if (PI.getLatency() > 0 &&
714 Top.ResourceModel->isInPacket(PI.getSUnit())) {
715 ResCount -= PriorityOne;
716 LLVM_DEBUG(if (verbose) dbgs() << "D|");
717 }
718 }
719 } else {
720 for (const auto &SI : SU->Succs) {
721 if (SI.getLatency() > 0 &&
722 Bot.ResourceModel->isInPacket(SI.getSUnit())) {
723 ResCount -= PriorityOne;
724 LLVM_DEBUG(if (verbose) dbgs() << "D|");
725 }
726 }
727 }
728 }
729
730 LLVM_DEBUG(if (verbose) {
731 std::stringstream dbgstr;
732 dbgstr << "Total " << std::setw(4) << ResCount << ")";
733 dbgs() << dbgstr.str();
734 });
735
736 return ResCount;
737}
738
739/// Pick the best candidate from the top queue.
740///
741/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
742/// DAG building. To adjust for the current scheduling location we need to
743/// maintain the number of vreg uses remaining to be top-scheduled.
746 const RegPressureTracker &RPTracker,
747 SchedCandidate &Candidate) {
748 ReadyQueue &Q = Zone.Available;
749 LLVM_DEBUG(if (DAG->Opts.vliw_misched_verbose_level > 1)
750 readyQueueVerboseDump(RPTracker, Candidate, Q);
751 else Q.dump(););
752
753 // getMaxPressureDelta temporarily modifies the tracker.
754 RegPressureTracker &TempTracker = const_cast<RegPressureTracker &>(RPTracker);
755
756 // BestSU remains NULL if no top candidates beat the best existing candidate.
757 CandResult FoundCandidate = NoCand;
758 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
759 RegPressureDelta RPDelta;
760 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
761 DAG->getRegionCriticalPSets(),
762 DAG->getRegPressure().MaxSetPressure);
763
764 int CurrentCost = SchedulingCost(Q, *I, Candidate, RPDelta, false);
765
766 // Initialize the candidate if needed.
767 if (!Candidate.SU) {
768 LLVM_DEBUG(traceCandidate("DCAND", Q, *I, CurrentCost));
769 Candidate.SU = *I;
770 Candidate.RPDelta = RPDelta;
771 Candidate.SCost = CurrentCost;
772 FoundCandidate = NodeOrder;
773 continue;
774 }
775
776 // Choose node order for negative cost candidates. There is no good
777 // candidate in this case.
778 if (CurrentCost < 0 && Candidate.SCost < 0) {
779 if ((Q.getID() == TopQID && (*I)->NodeNum < Candidate.SU->NodeNum) ||
780 (Q.getID() == BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) {
781 LLVM_DEBUG(traceCandidate("NCAND", Q, *I, CurrentCost));
782 Candidate.SU = *I;
783 Candidate.RPDelta = RPDelta;
784 Candidate.SCost = CurrentCost;
785 FoundCandidate = NodeOrder;
786 }
787 continue;
788 }
789
790 // Best cost.
791 if (CurrentCost > Candidate.SCost) {
792 LLVM_DEBUG(traceCandidate("CCAND", Q, *I, CurrentCost));
793 Candidate.SU = *I;
794 Candidate.RPDelta = RPDelta;
795 Candidate.SCost = CurrentCost;
796 FoundCandidate = BestCost;
797 continue;
798 }
799
800 // Choose an instruction that does not depend on an artificial edge.
801 unsigned CurrWeak = getWeakLeft(*I, (Q.getID() == TopQID));
802 unsigned CandWeak = getWeakLeft(Candidate.SU, (Q.getID() == TopQID));
803 if (CurrWeak != CandWeak) {
804 if (CurrWeak < CandWeak) {
805 LLVM_DEBUG(traceCandidate("WCAND", Q, *I, CurrentCost));
806 Candidate.SU = *I;
807 Candidate.RPDelta = RPDelta;
808 Candidate.SCost = CurrentCost;
809 FoundCandidate = Weak;
810 }
811 continue;
812 }
813
814 if (CurrentCost == Candidate.SCost && Zone.isLatencyBound(*I)) {
815 unsigned CurrSize, CandSize;
816 if (Q.getID() == TopQID) {
817 CurrSize = (*I)->Succs.size();
818 CandSize = Candidate.SU->Succs.size();
819 } else {
820 CurrSize = (*I)->Preds.size();
821 CandSize = Candidate.SU->Preds.size();
822 }
823 if (CurrSize > CandSize) {
824 LLVM_DEBUG(traceCandidate("SPCAND", Q, *I, CurrentCost));
825 Candidate.SU = *I;
826 Candidate.RPDelta = RPDelta;
827 Candidate.SCost = CurrentCost;
828 FoundCandidate = BestCost;
829 }
830 // Keep the old candidate if it's a better candidate. That is, don't use
831 // the subsequent tie breaker.
832 if (CurrSize != CandSize)
833 continue;
834 }
835
836 // Tie breaker.
837 // To avoid scheduling indeterminism, we need a tie breaker
838 // for the case when cost is identical for two nodes.
839 if (DAG->Opts.vliw_misched_use_newer_candidate &&
840 CurrentCost == Candidate.SCost) {
841 if ((Q.getID() == TopQID && (*I)->NodeNum < Candidate.SU->NodeNum) ||
842 (Q.getID() == BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) {
843 LLVM_DEBUG(traceCandidate("TCAND", Q, *I, CurrentCost));
844 Candidate.SU = *I;
845 Candidate.RPDelta = RPDelta;
846 Candidate.SCost = CurrentCost;
847 FoundCandidate = NodeOrder;
848 continue;
849 }
850 }
851
852 // Fall through to original instruction order.
853 // Only consider node order if Candidate was chosen from this Q.
854 if (FoundCandidate == NoCand)
855 continue;
856 }
857 return FoundCandidate;
858}
859
860/// Pick the best candidate node from either the top or bottom queue.
862 // Schedule as far as possible in the direction of no choice. This is most
863 // efficient, but also provides the best heuristics for CriticalPSets.
864 if (SUnit *SU = Bot.pickOnlyChoice()) {
865 LLVM_DEBUG(dbgs() << "Picked only Bottom\n");
866 IsTopNode = false;
867 return SU;
868 }
869 if (SUnit *SU = Top.pickOnlyChoice()) {
870 LLVM_DEBUG(dbgs() << "Picked only Top\n");
871 IsTopNode = true;
872 return SU;
873 }
874 SchedCandidate BotCand;
875 // Prefer bottom scheduling when heuristics are silent.
876 CandResult BotResult =
877 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
878 assert(BotResult != NoCand && "failed to find the first candidate");
879
880 // If either Q has a single candidate that provides the least increase in
881 // Excess pressure, we can immediately schedule from that Q.
882 //
883 // RegionCriticalPSets summarizes the pressure within the scheduled region and
884 // affects picking from either Q. If scheduling in one direction must
885 // increase pressure for one of the excess PSets, then schedule in that
886 // direction first to provide more freedom in the other direction.
887 if (BotResult == SingleExcess || BotResult == SingleCritical) {
888 LLVM_DEBUG(dbgs() << "Prefered Bottom Node\n");
889 IsTopNode = false;
890 return BotCand.SU;
891 }
892 // Check if the top Q has a better candidate.
893 SchedCandidate TopCand;
894 CandResult TopResult =
895 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
896 assert(TopResult != NoCand && "failed to find the first candidate");
897
898 if (TopResult == SingleExcess || TopResult == SingleCritical) {
899 LLVM_DEBUG(dbgs() << "Prefered Top Node\n");
900 IsTopNode = true;
901 return TopCand.SU;
902 }
903 // If either Q has a single candidate that minimizes pressure above the
904 // original region's pressure pick it.
905 if (BotResult == SingleMax) {
906 LLVM_DEBUG(dbgs() << "Prefered Bottom Node SingleMax\n");
907 IsTopNode = false;
908 return BotCand.SU;
909 }
910 if (TopResult == SingleMax) {
911 LLVM_DEBUG(dbgs() << "Prefered Top Node SingleMax\n");
912 IsTopNode = true;
913 return TopCand.SU;
914 }
915 if (TopCand.SCost > BotCand.SCost) {
916 LLVM_DEBUG(dbgs() << "Prefered Top Node Cost\n");
917 IsTopNode = true;
918 return TopCand.SU;
919 }
920 // Otherwise prefer the bottom candidate in node order.
921 LLVM_DEBUG(dbgs() << "Prefered Bottom in Node order\n");
922 IsTopNode = false;
923 return BotCand.SU;
924}
925
926/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
928 if (DAG->top() == DAG->bottom()) {
929 assert(Top.Available.empty() && Top.Pending.empty() &&
930 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
931 return nullptr;
932 }
933 SUnit *SU;
934 if (DAG->Opts.misched_prera_direction == MISched::TopDown) {
935 SU = Top.pickOnlyChoice();
936 if (!SU) {
937 SchedCandidate TopCand;
938 CandResult TopResult =
939 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
940 assert(TopResult != NoCand && "failed to find the first candidate");
941 (void)TopResult;
942 SU = TopCand.SU;
943 }
944 IsTopNode = true;
945 } else if (DAG->Opts.misched_prera_direction == MISched::BottomUp) {
946 SU = Bot.pickOnlyChoice();
947 if (!SU) {
948 SchedCandidate BotCand;
949 CandResult BotResult =
950 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
951 assert(BotResult != NoCand && "failed to find the first candidate");
952 (void)BotResult;
953 SU = BotCand.SU;
954 }
955 IsTopNode = false;
956 } else {
957 SU = pickNodeBidrectional(IsTopNode);
958 }
959 if (SU->isTopReady())
960 Top.removeReady(SU);
961 if (SU->isBottomReady())
962 Bot.removeReady(SU);
963
964 LLVM_DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
965 << " Scheduling instruction in cycle "
966 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << " ("
967 << reportPackets() << ")\n";
968 DAG->dumpNode(*SU));
969 return SU;
970}
971
972/// Update the scheduler's state after scheduling a node. This is the same node
973/// that was just returned by pickNode(). However, VLIWMachineScheduler needs
974/// to update it's state based on the current cycle before MachineSchedStrategy
975/// does.
976void ConvergingVLIWScheduler::schedNode(SUnit *SU, bool IsTopNode) {
977 if (IsTopNode) {
978 Top.bumpNode(SU);
979 SU->TopReadyCycle = Top.CurrCycle;
980 } else {
981 Bot.bumpNode(SU);
982 SU->BotReadyCycle = Bot.CurrCycle;
983 }
984}
SDValue Pred
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static const Function * getParent(const Value *V)
const HexagonInstrInfo * TII
#define I(x, y, z)
Definition MD5.cpp:57
#define P(N)
This file defines the SmallVector class.
#define LLVM_DEBUG(...)
Definition Debug.h:119
static bool isSingleUnscheduledPred(SUnit *SU, SUnit *SU2)
isSingleUnscheduledPred - If SU2 is the only unscheduled predecessor of SU, return true (we may have ...
static bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2)
isSingleUnscheduledSucc - If SU2 is the only unscheduled successor of SU, return true (we may have du...
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
static constexpr unsigned PriorityOne
SUnit * pickNode(bool &IsTopNode) override
Pick the best node to balance the schedule. Implements MachineSchedStrategy.
virtual VLIWResourceModel * createVLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SchedModel) const
int pressureChange(const SUnit *SU, bool isBotUp)
Check if the instruction changes the register pressure of a register in the high pressure set.
SmallVector< bool > HighPressureSets
List of pressure sets that have a high pressure level in the region.
static constexpr unsigned ScaleTwo
CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the top queue.
void schedNode(SUnit *SU, bool IsTopNode) override
Update the scheduler's state after scheduling a node.
void readyQueueVerboseDump(const RegPressureTracker &RPTracker, SchedCandidate &Candidate, ReadyQueue &Q)
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
SUnit * pickNodeBidrectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
static constexpr unsigned PriorityTwo
static constexpr unsigned PriorityThree
const TargetSchedModel * SchedModel
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU, SchedCandidate &Candidate, RegPressureDelta &Delta, bool verbose)
Single point to compute overall scheduling cost.
void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P=PressureChange())
CandResult
Represent the type of SchedCandidate found within a single queue.
Itinerary data supplied by a subtarget to be used by a target.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
bool isPseudo(QueryType Type=IgnoreBundle) const
Return true if this is a pseudo instruction that doesn't correspond to a real machine instruction.
Capture a change in pressure for a single pressure set.
List of PressureChanges in order of increasing, unique PSetID.
Helpers for implementing custom MachineSchedStrategy classes.
LLVM_ABI void dump() const
std::vector< SUnit * >::iterator iterator
StringRef getName() const
unsigned getID() const
Track the current register pressure at some position in the instruction stream, and remember the high...
void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
Find the pressure set with the most change beyond its pressure limit after traversing this instructio...
Scheduling dependency.
Definition ScheduleDAG.h:54
SUnit * getSUnit() const
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Scheduling unit. This is a node in the scheduling DAG.
bool isCall
Is a function call.
unsigned TopReadyCycle
Cycle relative to start when node is ready.
unsigned NodeNum
Entry # of node in the node vector.
unsigned NumSuccsLeft
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
bool isScheduleHigh
True if preferable to schedule high.
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
bool isScheduled
True once scheduled.
unsigned NumPredsLeft
unsigned BotReadyCycle
Cycle relative to end when node is ready.
SmallVector< SDep, 4 > Succs
All sunit successors.
bool isBottomReady() const
bool isTopReady() const
SmallVector< SDep, 4 > Preds
All sunit predecessors.
SmallVectorImpl< SDep >::iterator succ_iterator
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
MachineBasicBlock * BB
The block in which to insert instructions.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
const MachineLoopInfo * MLI
void scheduleMI(SUnit *SU, bool IsTopNode)
Move an instruction and update register pressure.
void initQueues(ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)
Release ExitSU predecessors and setup scheduler queues.
void buildDAGWithRegPressure()
Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking enabled.
void dump() const override
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
void dumpSchedule() const
dump the scheduled Sequence.
std::unique_ptr< MachineSchedStrategy > SchedImpl
void postProcessDAG()
Apply each ScheduleDAGMutation step in order.
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
void viewGraph() override
Out-of-line implementation with no arguments is handy for gdb.
void updateQueues(SUnit *SU, bool IsTopNode)
Update scheduler DAG and queues after scheduling an instruction.
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
MachineBasicBlock::iterator CurrentTop
The top of the unscheduled zone.
std::vector< SUnit > SUnits
The scheduling units.
MachineFunction & MF
Machine function.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
Provide an instruction scheduling machine model to CodeGen passes.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetInstrInfo * getInstrInfo() const
Extend the standard ScheduleDAGMILive to provide more context and override the top-level schedule() d...
void schedule() override
Schedule - This is called back from ScheduleDAGInstrs::Run() when it's time to do some work.
unsigned TotalPackets
Total packets created.
virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu)
Return true if there is a dependence between SUd and SUu.
virtual DFAPacketizer * createPacketizer(const TargetSubtargetInfo &STI) const
virtual bool reserveResources(SUnit *SU, bool IsTop)
Keep track of available resources.
DFAPacketizer * ResourcesModel
ResourcesModel - Represents VLIW state.
SmallVector< SUnit * > Packet
Local packet/bundle model.
const TargetSchedModel * SchedModel
VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
virtual bool isResourceAvailable(SUnit *SU, bool IsTop)
Check if scheduling of this SU is possible in the current packet.
const TargetInstrInfo * TII
A raw_ostream that writes to an std::string.
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
LLVM_ABI unsigned getWeakLeft(const SUnit *SU, bool isTop)
InstructionCost Cost
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
FormattedString left_justify(StringRef Str, unsigned Width)
left_justify - append spaces after string so total output is Width characters.
Definition Format.h:123
LLVM_ABI bool shouldViewMISchedDAGs(const MachineFunction &MF)
Return -misched-view-dags, which is false in a build without assertions.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Store the state used by ConvergingVLIWScheduler heuristics, required for the lifetime of one invocati...
Each Scheduling boundary is associated with ready queues.
LLVM_ABI void releaseNode(SUnit *SU, unsigned ReadyCycle)
LLVM_ABI void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
LLVM_ABI void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
unsigned MinReadyCycle
MinReadyCycle - Cycle of the soonest available instruction.
LLVM_ABI void releasePending()
Release pending ready nodes in to the available queue.
LLVM_ABI SUnit * pickOnlyChoice()
If this queue only has one ready candidate, return it.
LLVM_ABI void bumpCycle()
Move the boundary of scheduled code by one cycle.
LLVM_ABI bool checkHazard(SUnit *SU)
Does this SU have a hazard within the current instruction group.
Store the effects of a change in pressure on things that MI scheduler cares about.