51#include "llvm/Config/llvm-config.h"
74#define DEBUG_TYPE "machine-scheduler"
76STATISTIC(NumClustered,
"Number of load/store pairs clustered");
81 cl::desc(
"Force top-down list scheduling"));
83 cl::desc(
"Force bottom-up list scheduling"));
84namespace MISchedPostRASched {
92 cl::desc(
"Post reg-alloc list scheduling direction"),
97 "Force top-down post reg-alloc list scheduling"),
99 "Force bottom-up post reg-alloc list scheduling")));
102 cl::desc(
"Print critical path length to stdout"));
106 cl::desc(
"Verify machine instrs before and after machine scheduling"));
111 cl::desc(
"Pop up a window to show MISched dags after they are processed"));
116 cl::desc(
"Dump resource usage at schedule boundary."));
119 cl::desc(
"Show details of invoking getNextResoufceCycle."));
124#ifdef LLVM_ENABLE_DUMP
135 cl::desc(
"Hide nodes with more predecessor/successor than cutoff"));
141 cl::desc(
"Only schedule this function"));
143 cl::desc(
"Only schedule this MBB#"));
158 cl::desc(
"Enable memop clustering."),
162 cl::desc(
"Switch to fast cluster algorithm with the lost "
163 "of some fusion opportunities"),
167 cl::desc(
"The threshold for fast cluster"),
170#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
173 cl::desc(
"Dump resource usage at schedule boundary."));
176 cl::desc(
"Set width of the columns with "
177 "the resources and schedule units"),
181 cl::desc(
"Set width of the columns showing resource booking."),
185 cl::desc(
"Sort the resources printed in the dump trace"));
196void MachineSchedStrategy::anchor() {}
198void ScheduleDAGMutation::anchor() {}
227class MachineScheduler :
public MachineSchedulerBase {
242class PostMachineScheduler :
public MachineSchedulerBase {
244 PostMachineScheduler();
258char MachineScheduler::ID = 0;
263 "Machine Instruction Scheduler",
false,
false)
272MachineScheduler::MachineScheduler() : MachineSchedulerBase(
ID) {
276void MachineScheduler::getAnalysisUsage(
AnalysisUsage &AU)
const {
289char PostMachineScheduler::ID = 0;
294 "PostRA Machine Instruction Scheduler",
false,
false)
301PostMachineScheduler::PostMachineScheduler() : MachineSchedulerBase(
ID) {
305void PostMachineScheduler::getAnalysisUsage(
AnalysisUsage &AU)
const {
328 cl::desc(
"Machine instruction scheduler to use"));
336 cl::desc(
"Enable the machine instruction scheduling pass."),
cl::init(
true),
340 "enable-post-misched",
341 cl::desc(
"Enable the post-ra machine instruction scheduling pass."),
348 assert(
I != Beg &&
"reached the top of the region, cannot decrement");
350 if (!
I->isDebugOrPseudoInstr())
369 for(;
I !=
End; ++
I) {
370 if (!
I->isDebugOrPseudoInstr())
443 MLI = &getAnalysis<MachineLoopInfo>();
444 MDT = &getAnalysis<MachineDominatorTree>();
445 PassConfig = &getAnalysis<TargetPassConfig>();
446 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
448 LIS = &getAnalysis<LiveIntervals>();
452 MF->verify(
this,
"Before machine scheduling.");
454 RegClassInfo->runOnMachineFunction(*MF);
458 std::unique_ptr<ScheduleDAGInstrs>
Scheduler(createMachineScheduler());
471 MF->verify(
this,
"After machine scheduling.");
490 MLI = &getAnalysis<MachineLoopInfo>();
491 PassConfig = &getAnalysis<TargetPassConfig>();
492 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
495 MF->verify(
this,
"Before post machine scheduling.");
499 std::unique_ptr<ScheduleDAGInstrs>
Scheduler(createPostMachineScheduler());
509 MF->verify(
this,
"After post machine scheduling.");
540 unsigned NumRegionInstrs;
544 RegionBegin(
B), RegionEnd(
E), NumRegionInstrs(
N) {}
553 bool RegionsTopDown) {
559 RegionEnd !=
MBB->
begin(); RegionEnd =
I) {
562 if (RegionEnd !=
MBB->
end() ||
569 unsigned NumRegionInstrs = 0;
575 if (!
MI.isDebugOrPseudoInstr()) {
584 if (NumRegionInstrs != 0)
585 Regions.
push_back(SchedRegion(
I, RegionEnd, NumRegionInstrs));
589 std::reverse(Regions.
begin(), Regions.
end());
628 for (
const SchedRegion &R : MBBRegions) {
631 unsigned NumRegionInstrs =
R.NumRegionInstrs;
638 if (
I == RegionEnd ||
I == std::prev(RegionEnd)) {
649 else dbgs() <<
"End\n";
650 dbgs() <<
" RegionInstrs: " << NumRegionInstrs <<
'\n');
652 errs() << MF->getName();
678#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
680 dbgs() <<
"Queue " << Name <<
": ";
681 for (
const SUnit *SU : Queue)
682 dbgs() << SU->NodeNum <<
" ";
711 dbgs() <<
"*** Scheduling failed! ***\n";
713 dbgs() <<
" has been released too many times!\n";
748 dbgs() <<
"*** Scheduling failed! ***\n";
750 dbgs() <<
" has been released too many times!\n";
787 unsigned regioninstrs)
815#if LLVM_ENABLE_ABI_BREAKING_CHECKS && !defined(NDEBUG)
820 ++NumInstrsScheduled;
852 bool IsTopNode =
false;
854 LLVM_DEBUG(
dbgs() <<
"** ScheduleDAGMI::schedule picking next node\n");
895 dbgs() <<
"*** Final schedule for "
912 assert(!SU.isBoundaryNode() &&
"Boundary node should not be in SUnits");
915 SU.biasCriticalPath();
918 if (!SU.NumPredsLeft)
921 if (!SU.NumSuccsLeft)
937 for (
SUnit *SU : TopRoots)
976 for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator
978 std::pair<MachineInstr *, MachineInstr *>
P = *std::prev(DI);
989#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1001 dbgs() <<
" * Schedule table (TopDown):\n";
1019 for (
unsigned C = FirstCycle;
C <= LastCycle; ++
C)
1026 dbgs() <<
"Missing SUnit\n";
1029 std::string NodeName(
"SU(");
1030 NodeName += std::to_string(SU->
NodeNum) +
")";
1032 unsigned C = FirstCycle;
1033 for (;
C <= LastCycle; ++
C) {
1050 return LHS.AcquireAtCycle <
RHS.AcquireAtCycle ||
1051 (
LHS.AcquireAtCycle ==
RHS.AcquireAtCycle &&
1052 LHS.ReleaseAtCycle <
RHS.ReleaseAtCycle);
1056 const std::string ResName =
1062 for (
unsigned I = 0,
E = PI.ReleaseAtCycle - PI.AcquireAtCycle;
I !=
E;
1065 while (
C++ <= LastCycle)
1082 dbgs() <<
" * Schedule table (BottomUp):\n";
1095 if ((
int)SU->
BotReadyCycle - PI->ReleaseAtCycle + 1 < LastCycle)
1096 LastCycle = (int)SU->
BotReadyCycle - PI->ReleaseAtCycle + 1;
1101 for (
int C = FirstCycle;
C >= LastCycle; --
C)
1108 dbgs() <<
"Missing SUnit\n";
1111 std::string NodeName(
"SU(");
1112 NodeName += std::to_string(SU->
NodeNum) +
")";
1115 for (;
C >= LastCycle; --
C) {
1131 return LHS.AcquireAtCycle <
RHS.AcquireAtCycle ||
1132 (
LHS.AcquireAtCycle ==
RHS.AcquireAtCycle &&
1133 LHS.ReleaseAtCycle <
RHS.ReleaseAtCycle);
1137 const std::string ResName =
1143 for (
unsigned I = 0,
E = PI.ReleaseAtCycle - PI.AcquireAtCycle;
I !=
E;
1146 while (
C-- >= LastCycle)
1155#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1163 dbgs() <<
"* Schedule table (Bidirectional): not implemented\n";
1165 dbgs() <<
"* Schedule table: DumpDirection not set.\n";
1173 dbgs() <<
"Missing SUnit\n";
1198 if (!Reg.isVirtual())
1203 bool FoundDef =
false;
1205 if (MO2.getReg() == Reg && !MO2.isDead()) {
1232 unsigned regioninstrs)
1246 "ShouldTrackLaneMasks requires ShouldTrackPressure");
1297 dbgs() <<
"Bottom Pressure:\n";
1303 "Can't find the region bottom");
1327 const std::vector<unsigned> &NewMaxPressure) {
1333 unsigned ID = PC.getPSet();
1338 && NewMaxPressure[
ID] <= (
unsigned)std::numeric_limits<int16_t>::max())
1342 if (NewMaxPressure[
ID] >= Limit - 2) {
1344 << NewMaxPressure[
ID]
1345 << ((NewMaxPressure[
ID] > Limit) ?
" > " :
" <= ")
1359 if (!Reg.isVirtual())
1367 bool Decrement =
P.LaneMask.any();
1371 SUnit &SU = *V2SU.SU;
1400 assert(VNI &&
"No live value at use.");
1403 SUnit *SU = V2SU.SU;
1423#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1429 dbgs() <<
" Pressure Diff : ";
1432 dbgs() <<
" Single Issue : ";
1476 bool IsTopNode =
false;
1478 LLVM_DEBUG(
dbgs() <<
"** ScheduleDAGMILive::schedule picking next node\n");
1507 dbgs() <<
"*** Final schedule for "
1579 unsigned MaxCyclicLatency = 0;
1583 if (!Reg.isVirtual())
1595 unsigned LiveOutHeight = DefSU->
getHeight();
1600 SUnit *SU = V2SU.SU;
1612 unsigned CyclicLatency = 0;
1614 CyclicLatency = LiveOutDepth - SU->
getDepth();
1617 if (LiveInHeight > LiveOutHeight) {
1618 if (LiveInHeight - LiveOutHeight < CyclicLatency)
1619 CyclicLatency = LiveInHeight - LiveOutHeight;
1624 << SU->
NodeNum <<
") = " << CyclicLatency <<
"c\n");
1625 if (CyclicLatency > MaxCyclicLatency)
1626 MaxCyclicLatency = CyclicLatency;
1629 LLVM_DEBUG(
dbgs() <<
"Cyclic Critical Path: " << MaxCyclicLatency <<
"c\n");
1630 return MaxCyclicLatency;
1682 if (&*priorII ==
MI)
1733 bool OffsetIsScalable;
1737 : SU(SU), BaseOps(BaseOps.begin(), BaseOps.end()),
Offset(
Offset),
1738 Width(Width), OffsetIsScalable(OffsetIsScalable) {}
1742 if (
A->getType() !=
B->getType())
1743 return A->getType() <
B->getType();
1745 return A->getReg() <
B->getReg();
1751 return StackGrowsDown ?
A->getIndex() >
B->getIndex()
1752 :
A->getIndex() <
B->getIndex();
1762 if (std::lexicographical_compare(BaseOps.
begin(), BaseOps.
end(),
1763 RHS.BaseOps.begin(),
RHS.BaseOps.end(),
1766 if (std::lexicographical_compare(
RHS.BaseOps.begin(),
RHS.BaseOps.end(),
1767 BaseOps.
begin(), BaseOps.
end(), Compare))
1778 bool ReorderWhileClustering;
1783 bool ReorderWhileClustering)
1784 :
TII(tii),
TRI(tri), IsLoad(IsLoad),
1785 ReorderWhileClustering(ReorderWhileClustering) {}
1792 void collectMemOpRecords(std::vector<SUnit> &SUnits,
1798class StoreClusterMutation :
public BaseMemOpClusterMutation {
1802 bool ReorderWhileClustering)
1803 : BaseMemOpClusterMutation(tii, tri,
false, ReorderWhileClustering) {}
1806class LoadClusterMutation :
public BaseMemOpClusterMutation {
1809 bool ReorderWhileClustering)
1810 : BaseMemOpClusterMutation(tii, tri,
true, ReorderWhileClustering) {}
1817std::unique_ptr<ScheduleDAGMutation>
1820 bool ReorderWhileClustering) {
1822 TII,
TRI, ReorderWhileClustering)
1826std::unique_ptr<ScheduleDAGMutation>
1829 bool ReorderWhileClustering) {
1831 TII,
TRI, ReorderWhileClustering)
1842void BaseMemOpClusterMutation::clusterNeighboringMemOps(
1852 auto MemOpa = MemOpRecords[
Idx];
1855 unsigned NextIdx =
Idx + 1;
1856 for (; NextIdx <
End; ++NextIdx)
1859 if (!SUnit2ClusterInfo.
count(MemOpRecords[NextIdx].SU->NodeNum) &&
1861 (!DAG->
IsReachable(MemOpRecords[NextIdx].SU, MemOpa.SU) &&
1862 !DAG->
IsReachable(MemOpa.SU, MemOpRecords[NextIdx].SU))))
1867 auto MemOpb = MemOpRecords[NextIdx];
1868 unsigned ClusterLength = 2;
1869 unsigned CurrentClusterBytes = MemOpa.Width.getValue().getKnownMinValue() +
1870 MemOpb.Width.getValue().getKnownMinValue();
1871 if (SUnit2ClusterInfo.
count(MemOpa.SU->NodeNum)) {
1872 ClusterLength = SUnit2ClusterInfo[MemOpa.SU->NodeNum].first + 1;
1873 CurrentClusterBytes = SUnit2ClusterInfo[MemOpa.SU->NodeNum].second +
1874 MemOpb.Width.getValue().getKnownMinValue();
1877 if (!
TII->shouldClusterMemOps(MemOpa.BaseOps, MemOpa.Offset,
1878 MemOpa.OffsetIsScalable, MemOpb.BaseOps,
1879 MemOpb.Offset, MemOpb.OffsetIsScalable,
1880 ClusterLength, CurrentClusterBytes))
1883 SUnit *SUa = MemOpa.SU;
1884 SUnit *SUb = MemOpb.SU;
1924 SUnit2ClusterInfo[MemOpb.SU->NodeNum] = {ClusterLength,
1925 CurrentClusterBytes};
1928 <<
", Curr cluster bytes: " << CurrentClusterBytes
1933void BaseMemOpClusterMutation::collectMemOpRecords(
1935 for (
auto &SU : SUnits) {
1943 bool OffsetIsScalable;
1946 OffsetIsScalable, Width,
TRI)) {
1948 MemOpInfo(&SU, BaseOps,
Offset, OffsetIsScalable, Width));
1951 <<
Offset <<
", OffsetIsScalable: " << OffsetIsScalable
1952 <<
", Width: " << Width <<
"\n");
1955 for (
const auto *
Op : BaseOps)
1961bool BaseMemOpClusterMutation::groupMemOps(
1968 for (
const auto &
MemOp : MemOps) {
1969 unsigned ChainPredID = DAG->
SUnits.size();
1971 for (
const SDep &Pred :
MemOp.SU->Preds) {
1995 collectMemOpRecords(DAG->
SUnits, MemOpRecords);
1997 if (MemOpRecords.
size() < 2)
2004 bool FastCluster = groupMemOps(MemOpRecords, DAG,
Groups);
2006 for (
auto &Group :
Groups) {
2012 clusterNeighboringMemOps(Group.second, FastCluster, DAG);
2046std::unique_ptr<ScheduleDAGMutation>
2049 return std::make_unique<CopyConstrain>(
TII,
TRI);
2094 unsigned LocalReg = SrcReg;
2095 unsigned GlobalReg = DstReg;
2097 if (!LocalLI->
isLocal(RegionBeginIdx, RegionEndIdx)) {
2101 if (!LocalLI->
isLocal(RegionBeginIdx, RegionEndIdx))
2112 if (GlobalSegment == GlobalLI->
end())
2119 if (GlobalSegment->contains(LocalLI->
beginIndex()))
2122 if (GlobalSegment == GlobalLI->
end())
2126 if (GlobalSegment != GlobalLI->
begin()) {
2129 GlobalSegment->start)) {
2140 assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&
2141 "Disconnected LRG within the scheduling region.");
2157 for (
const SDep &Succ : LastLocalSU->
Succs) {
2172 for (
const SDep &Pred : GlobalSU->
Preds) {
2175 if (Pred.
getSUnit() == FirstLocalSU)
2183 for (
SUnit *LU : LocalUses) {
2184 LLVM_DEBUG(
dbgs() <<
" Local use SU(" << LU->NodeNum <<
") -> SU("
2185 << GlobalSU->
NodeNum <<
")\n");
2188 for (
SUnit *GU : GlobalUses) {
2189 LLVM_DEBUG(
dbgs() <<
" Global use SU(" << GU->NodeNum <<
") -> SU("
2190 << FirstLocalSU->
NodeNum <<
")\n");
2202 if (FirstPos == DAG->
end())
2230 unsigned Latency,
bool AfterSchedNode) {
2231 int ResCntFactor = (int)(Count - (
Latency * LFactor));
2233 return ResCntFactor >= (int)LFactor;
2235 return ResCntFactor > (int)LFactor;
2248 CheckPending =
false;
2251 MinReadyCycle = std::numeric_limits<unsigned>::max();
2252 ExpectedLatency = 0;
2253 DependentLatency = 0;
2255 MaxExecutedResCount = 0;
2257 IsResourceLimited =
false;
2258 ReservedCycles.clear();
2259 ReservedResourceSegments.clear();
2260 ReservedCyclesIndex.
clear();
2261 ResourceGroupSubUnitMasks.clear();
2262#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2266 MaxObservedStall = 0;
2269 ExecutedResCounts.
resize(1);
2270 assert(!ExecutedResCounts[0] &&
"nonzero count for bad resource");
2286 unsigned PIdx = PI->ProcResourceIdx;
2288 assert(PI->ReleaseAtCycle >= PI->AcquireAtCycle);
2290 (Factor * (PI->ReleaseAtCycle - PI->AcquireAtCycle));
2303 ReservedCyclesIndex.
resize(ResourceCount);
2304 ExecutedResCounts.
resize(ResourceCount);
2305 ResourceGroupSubUnitMasks.resize(ResourceCount,
APInt(ResourceCount, 0));
2306 unsigned NumUnits = 0;
2308 for (
unsigned i = 0; i < ResourceCount; ++i) {
2309 ReservedCyclesIndex[i] = NumUnits;
2315 ResourceGroupSubUnitMasks[i].setBit(SubUnits[U]);
2335 if (ReadyCycle > CurrCycle)
2336 return ReadyCycle - CurrCycle;
2343 unsigned ReleaseAtCycle,
2344 unsigned AcquireAtCycle) {
2347 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromTop(
2348 CurrCycle, AcquireAtCycle, ReleaseAtCycle);
2350 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromBottom(
2351 CurrCycle, AcquireAtCycle, ReleaseAtCycle);
2354 unsigned NextUnreserved = ReservedCycles[InstanceIdx];
2360 NextUnreserved = std::max(CurrCycle, NextUnreserved + ReleaseAtCycle);
2361 return NextUnreserved;
2367std::pair<unsigned, unsigned>
2369 unsigned ReleaseAtCycle,
2370 unsigned AcquireAtCycle) {
2372 LLVM_DEBUG(
dbgs() <<
" Resource booking (@" << CurrCycle <<
"c): \n");
2374 LLVM_DEBUG(
dbgs() <<
" getNextResourceCycle (@" << CurrCycle <<
"c): \n");
2377 unsigned InstanceIdx = 0;
2378 unsigned StartIndex = ReservedCyclesIndex[PIdx];
2380 assert(NumberOfInstances > 0 &&
2381 "Cannot have zero instances of a ProcResource");
2398 if (ResourceGroupSubUnitMasks[PIdx][PE.ProcResourceIdx])
2400 StartIndex, ReleaseAtCycle, AcquireAtCycle),
2404 for (
unsigned I = 0,
End = NumberOfInstances;
I <
End; ++
I) {
2405 unsigned NextUnreserved, NextInstanceIdx;
2406 std::tie(NextUnreserved, NextInstanceIdx) =
2408 if (MinNextUnreserved > NextUnreserved) {
2409 InstanceIdx = NextInstanceIdx;
2410 MinNextUnreserved = NextUnreserved;
2413 return std::make_pair(MinNextUnreserved, InstanceIdx);
2416 for (
unsigned I = StartIndex,
End = StartIndex + NumberOfInstances;
I <
End;
2418 unsigned NextUnreserved =
2422 << NextUnreserved <<
"c\n");
2423 if (MinNextUnreserved > NextUnreserved) {
2425 MinNextUnreserved = NextUnreserved;
2430 <<
"[" << InstanceIdx - StartIndex <<
"]"
2431 <<
" available @" << MinNextUnreserved <<
"c"
2433 return std::make_pair(MinNextUnreserved, InstanceIdx);
2466 << (
isTop() ?
"begin" :
"end") <<
" group\n");
2475 unsigned ResIdx = PE.ProcResourceIdx;
2476 unsigned ReleaseAtCycle = PE.ReleaseAtCycle;
2477 unsigned AcquireAtCycle = PE.AcquireAtCycle;
2478 unsigned NRCycle, InstanceIdx;
2479 std::tie(NRCycle, InstanceIdx) =
2481 if (NRCycle > CurrCycle) {
2482#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2483 MaxObservedStall = std::max(ReleaseAtCycle, MaxObservedStall);
2487 <<
'[' << InstanceIdx - ReservedCyclesIndex[ResIdx] <<
']'
2488 <<
"=" << NRCycle <<
"c\n");
2499 SUnit *LateSU =
nullptr;
2500 unsigned RemLatency = 0;
2501 for (
SUnit *SU : ReadySUs) {
2503 if (L > RemLatency) {
2510 << LateSU->
NodeNum <<
") " << RemLatency <<
"c\n");
2529 PIdx != PEnd; ++PIdx) {
2531 if (OtherCount > OtherCritCount) {
2532 OtherCritCount = OtherCount;
2533 OtherCritIdx = PIdx;
2542 return OtherCritCount;
2549#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2553 if (ReadyCycle > CurrCycle)
2554 MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);
2557 if (ReadyCycle < MinReadyCycle)
2558 MinReadyCycle = ReadyCycle;
2563 bool HazardDetected = (!IsBuffered && ReadyCycle > CurrCycle) ||
2566 if (!HazardDetected) {
2581 assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
2582 "MinReadyCycle uninitialized");
2583 if (MinReadyCycle > NextCycle)
2584 NextCycle = MinReadyCycle;
2588 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
2591 if ((NextCycle - CurrCycle) > DependentLatency)
2592 DependentLatency = 0;
2594 DependentLatency -= (NextCycle - CurrCycle);
2598 CurrCycle = NextCycle;
2601 for (; CurrCycle != NextCycle; ++CurrCycle) {
2608 CheckPending =
true;
2618 ExecutedResCounts[PIdx] += Count;
2619 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
2620 MaxExecutedResCount = ExecutedResCounts[PIdx];
2634 unsigned ReleaseAtCycle,
2636 unsigned AcquireAtCycle) {
2638 unsigned Count = Factor * (ReleaseAtCycle- AcquireAtCycle);
2640 << ReleaseAtCycle <<
"x" << Factor <<
"u\n");
2650 ZoneCritResIdx = PIdx;
2657 unsigned NextAvailable, InstanceIdx;
2658 std::tie(NextAvailable, InstanceIdx) =
2660 if (NextAvailable > CurrCycle) {
2663 <<
'[' << InstanceIdx - ReservedCyclesIndex[PIdx] <<
']'
2664 <<
" reserved until @" << NextAvailable <<
"\n");
2666 return NextAvailable;
2680 CheckPending =
true;
2688 "Cannot schedule this instruction's MicroOps in the current cycle.");
2693 unsigned NextCycle = CurrCycle;
2696 assert(ReadyCycle <= CurrCycle &&
"Broken PendingQueue");
2699 if (ReadyCycle > NextCycle) {
2700 NextCycle = ReadyCycle;
2701 LLVM_DEBUG(
dbgs() <<
" *** Stall until: " << ReadyCycle <<
"\n");
2710 NextCycle = ReadyCycle;
2713 RetiredMOps += IncMOps;
2720 if (ZoneCritResIdx) {
2722 unsigned ScaledMOps =
2739 countResource(SC, PI->ProcResourceIdx, PI->ReleaseAtCycle, NextCycle,
2740 PI->AcquireAtCycle);
2741 if (RCycle > NextCycle)
2752 unsigned PIdx = PI->ProcResourceIdx;
2756 unsigned ReservedUntil, InstanceIdx;
2758 SC, PIdx, PI->ReleaseAtCycle, PI->AcquireAtCycle);
2760 ReservedResourceSegments[InstanceIdx].add(
2762 NextCycle, PI->AcquireAtCycle, PI->ReleaseAtCycle),
2765 ReservedResourceSegments[InstanceIdx].add(
2767 NextCycle, PI->AcquireAtCycle, PI->ReleaseAtCycle),
2772 unsigned ReservedUntil, InstanceIdx;
2774 SC, PIdx, PI->ReleaseAtCycle, PI->AcquireAtCycle);
2776 ReservedCycles[InstanceIdx] =
2777 std::max(ReservedUntil, NextCycle + PI->ReleaseAtCycle);
2779 ReservedCycles[InstanceIdx] = NextCycle;
2786 unsigned &TopLatency =
isTop() ? ExpectedLatency : DependentLatency;
2787 unsigned &BotLatency =
isTop() ? DependentLatency : ExpectedLatency;
2791 << SU->
NodeNum <<
") " << TopLatency <<
"c\n");
2796 << SU->
NodeNum <<
") " << BotLatency <<
"c\n");
2799 if (NextCycle > CurrCycle)
2812 CurrMOps += IncMOps;
2826 LLVM_DEBUG(
dbgs() <<
" *** Max MOps " << CurrMOps <<
" at cycle "
2827 << CurrCycle <<
'\n');
2838 MinReadyCycle = std::numeric_limits<unsigned>::max();
2846 if (ReadyCycle < MinReadyCycle)
2847 MinReadyCycle = ReadyCycle;
2858 CheckPending =
false;
2904#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2914 unsigned StartIdx = 0;
2916 for (
unsigned ResIdx = 0; ResIdx < ResourceCount; ++ResIdx) {
2919 for (
unsigned UnitIdx = 0; UnitIdx < NumUnits; ++UnitIdx) {
2920 dbgs() << ResName <<
"(" << UnitIdx <<
") = ";
2922 if (ReservedResourceSegments.count(StartIdx + UnitIdx))
2923 dbgs() << ReservedResourceSegments.at(StartIdx + UnitIdx);
2927 dbgs() << ReservedCycles[StartIdx + UnitIdx] <<
"\n";
2929 StartIdx += NumUnits;
2938 if (ZoneCritResIdx) {
2943 ResCount = RetiredMOps * ResFactor;
2947 <<
" Retired: " << RetiredMOps;
2949 dbgs() <<
"\n Critical: " << ResCount / LFactor <<
"c, "
2950 << ResCount / ResFactor <<
" "
2952 <<
"\n ExpectedLatency: " << ExpectedLatency <<
"c\n"
2953 << (IsResourceLimited ?
" - Resource" :
" - Latency")
2999 RemLatency = std::max(RemLatency,
3001 RemLatency = std::max(RemLatency,
3008bool GenericSchedulerBase::shouldReduceLatency(
const CandPolicy &Policy,
3010 bool ComputeRemLatency,
3011 unsigned &RemLatency)
const {
3021 if (ComputeRemLatency)
3037 unsigned OtherCritIdx = 0;
3038 unsigned OtherCount =
3041 bool OtherResLimited =
false;
3042 unsigned RemLatency = 0;
3043 bool RemLatencyComputed =
false;
3046 RemLatencyComputed =
true;
3048 OtherCount, RemLatency,
false);
3054 if (!OtherResLimited &&
3055 (IsPostRA || shouldReduceLatency(Policy, CurrZone, !RemLatencyComputed,
3059 <<
" RemainingLatency " << RemLatency <<
" + "
3068 dbgs() <<
" " << CurrZone.Available.getName() <<
" ResourceLimited: "
3069 << SchedModel->getResourceName(CurrZone.getZoneCritResIdx()) <<
"\n";
3070 }
if (OtherResLimited)
dbgs()
3071 <<
" RemainingLimit: "
3074 <<
" Latency limited both directions.\n");
3079 if (OtherResLimited)
3087 case NoCand:
return "NOCAND ";
3088 case Only1:
return "ONLY1 ";
3089 case PhysReg:
return "PHYS-REG ";
3092 case Stall:
return "STALL ";
3093 case Cluster:
return "CLUSTER ";
3094 case Weak:
return "WEAK ";
3095 case RegMax:
return "REG-MAX ";
3110 unsigned ResIdx = 0;
3146 <<
":" <<
P.getUnitInc() <<
" ";
3169 if (TryVal < CandVal) {
3173 if (TryVal > CandVal) {
3174 if (Cand.
Reason > Reason)
3185 if (TryVal > CandVal) {
3189 if (TryVal < CandVal) {
3190 if (Cand.
Reason > Reason)
3242 "(PreRA)GenericScheduler needs vreg liveness");
3247 if (RegionPolicy.ComputeDFSResult)
3248 DAG->computeDFSResult();
3259 if (!Top.HazardRec) {
3264 if (!Bot.HazardRec) {
3269 TopCand.SU =
nullptr;
3270 BotCand.SU =
nullptr;
3276 unsigned NumRegionInstrs) {
3283 RegionPolicy.ShouldTrackPressure =
true;
3284 for (
unsigned VT = MVT::i32; VT > (
unsigned)MVT::i1; --VT) {
3289 RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
3295 RegionPolicy.OnlyBottomUp =
true;
3302 RegionPolicy.ShouldTrackPressure =
false;
3303 RegionPolicy.ShouldTrackLaneMasks =
false;
3309 "-misched-topdown incompatible with -misched-bottomup");
3312 if (RegionPolicy.OnlyBottomUp)
3313 RegionPolicy.OnlyTopDown =
false;
3317 if (RegionPolicy.OnlyTopDown)
3318 RegionPolicy.OnlyBottomUp =
false;
3324#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3325 dbgs() <<
"GenericScheduler RegionPolicy: "
3326 <<
" ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure
3327 <<
" OnlyTopDown=" << RegionPolicy.OnlyTopDown
3328 <<
" OnlyBottomUp=" << RegionPolicy.OnlyBottomUp
3347 unsigned IterCount =
3353 unsigned InFlightCount =
3355 unsigned BufferLimit =
3361 dbgs() <<
"IssueCycles="
3364 <<
"c NumIters=" << (AcyclicCount + IterCount - 1) / IterCount
3374 for (
const SUnit *SU : Bot.Available) {
3385 checkAcyclicLatency();
3412 if (TryPSet == CandPSet) {
3417 int TryRank = TryP.
isValid() ?
TRI->getRegPressureSetScore(MF, TryPSet) :
3418 std::numeric_limits<int>::max();
3420 int CandRank = CandP.
isValid() ?
TRI->getRegPressureSetScore(MF, CandPSet) :
3421 std::numeric_limits<int>::max();
3426 return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);
3444 unsigned ScheduledOper = isTop ? 1 : 0;
3445 unsigned UnscheduledOper = isTop ? 0 : 1;
3448 if (
MI->getOperand(ScheduledOper).getReg().isPhysical())
3453 if (
MI->getOperand(UnscheduledOper).getReg().isPhysical())
3454 return AtBoundary ? -1 : 1;
3457 if (
MI->isMoveImmediate()) {
3463 if (
Op.isReg() && !
Op.getReg().isPhysical()) {
3470 return isTop ? -1 : 1;
3483 if (DAG->isTrackingPressure()) {
3488 DAG->getRegionCriticalPSets(),
3489 DAG->getRegPressure().MaxSetPressure);
3494 &DAG->getPressureDiff(Cand.
SU),
3496 DAG->getRegionCriticalPSets(),
3497 DAG->getRegPressure().MaxSetPressure);
3501 DAG->getPressureDiff(Cand.
SU),
3503 DAG->getRegionCriticalPSets(),
3504 DAG->getRegPressure().MaxSetPressure);
3509 <<
" Try SU(" << Cand.
SU->
NodeNum <<
") "
3558 bool SameBoundary = Zone !=
nullptr;
3579 const SUnit *CandNextClusterSU =
3581 const SUnit *TryCandNextClusterSU =
3584 Cand.
SU == CandNextClusterSU,
3592 TryCand, Cand,
Weak))
3644 for (
SUnit *SU : Q) {
3647 initCandidate(TryCand, SU, Zone.
isTop(), RPTracker, TempTracker);
3650 if (tryCandidate(Cand, TryCand, ZoneArg)) {
3664 if (
SUnit *SU = Bot.pickOnlyChoice()) {
3669 if (
SUnit *SU = Top.pickOnlyChoice()) {
3685 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
3686 BotCand.Policy != BotPolicy) {
3688 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);
3689 assert(BotCand.Reason !=
NoCand &&
"failed to find the first candidate");
3696 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);
3698 "Last pick result should correspond to re-picking right now");
3705 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
3706 TopCand.Policy != TopPolicy) {
3708 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);
3709 assert(TopCand.Reason !=
NoCand &&
"failed to find the first candidate");
3716 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);
3718 "Last pick result should correspond to re-picking right now");
3724 assert(BotCand.isValid());
3725 assert(TopCand.isValid());
3728 if (tryCandidate(Cand, TopCand,
nullptr)) {
3733 IsTopNode = Cand.
AtTop;
3741 assert(Top.Available.empty() && Top.Pending.empty() &&
3742 Bot.Available.empty() && Bot.Pending.empty() &&
"ReadyQ garbage");
3747 if (RegionPolicy.OnlyTopDown) {
3748 SU = Top.pickOnlyChoice();
3751 TopCand.reset(NoPolicy);
3752 pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);
3753 assert(TopCand.Reason !=
NoCand &&
"failed to find a candidate");
3758 }
else if (RegionPolicy.OnlyBottomUp) {
3759 SU = Bot.pickOnlyChoice();
3762 BotCand.reset(NoPolicy);
3763 pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);
3764 assert(BotCand.Reason !=
NoCand &&
"failed to find a candidate");
3770 SU = pickNodeBidirectional(IsTopNode);
3775 Top.removeReady(SU);
3777 Bot.removeReady(SU);
3792 for (
SDep &Dep : Deps) {
3796 SUnit *DepSU = Dep.getSUnit();
3797 if (isTop ? DepSU->
Succs.size() > 1 : DepSU->
Preds.size() > 1)
3800 if (!Copy->isCopy() && !Copy->isMoveImmediate())
3820 reschedulePhysReg(SU,
true);
3825 reschedulePhysReg(SU,
false);
3844 if (!MacroFusions.empty())
3873 if (!Top.HazardRec) {
3878 if (!Bot.HazardRec) {
3887 unsigned NumRegionInstrs) {
3889 RegionPolicy.OnlyTopDown =
true;
3890 RegionPolicy.OnlyBottomUp =
false;
3892 RegionPolicy.OnlyTopDown =
false;
3893 RegionPolicy.OnlyBottomUp =
true;
3901 for (
const SUnit *SU : Bot.Available) {
3925 if (
tryLess(Top.getLatencyStallCycles(TryCand.
SU),
3926 Top.getLatencyStallCycles(Cand.
SU), TryCand, Cand,
Stall))
3961 for (
SUnit *SU : Q) {
3966 if (tryCandidate(Cand, TryCand)) {
3976 assert(Top.Available.empty() && Top.Pending.empty() &&
3977 Bot.Available.empty() && Bot.Pending.empty() &&
"ReadyQ garbage");
3982 if (RegionPolicy.OnlyBottomUp) {
3983 assert(!RegionPolicy.OnlyTopDown);
3984 SU = Bot.pickOnlyChoice();
3993 pickNodeFromQueue(Bot, BotCand);
4001 assert(RegionPolicy.OnlyTopDown);
4002 SU = Top.pickOnlyChoice();
4011 pickNodeFromQueue(Top, TopCand);
4021 Top.removeReady(SU);
4023 Bot.removeReady(SU);
4049 if (!MacroFusions.empty())
4063 const BitVector *ScheduledTrees =
nullptr;
4066 ILPOrder(
bool MaxILP) : MaximizeILP(MaxILP) {}
4071 bool operator()(
const SUnit *
A,
const SUnit *
B)
const {
4074 if (SchedTreeA != SchedTreeB) {
4076 if (ScheduledTrees->
test(SchedTreeA) != ScheduledTrees->
test(SchedTreeB))
4077 return ScheduledTrees->
test(SchedTreeB);
4098 std::vector<SUnit*> ReadyQ;
4101 ILPScheduler(
bool MaximizeILP) :
Cmp(MaximizeILP) {}
4112 void registerRoots()
override {
4114 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
4121 SUnit *pickNode(
bool &IsTopNode)
override {
4122 if (ReadyQ.empty())
return nullptr;
4123 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
4124 SUnit *SU = ReadyQ.back();
4128 <<
"SU(" << SU->
NodeNum <<
") "
4135 <<
"Scheduling " << *SU->
getInstr());
4140 void scheduleTree(
unsigned SubtreeID)
override {
4141 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
4146 void schedNode(
SUnit *SU,
bool IsTopNode)
override {
4147 assert(!IsTopNode &&
"SchedDFSResult needs bottom-up");
4150 void releaseTopNode(
SUnit *)
override { }
4152 void releaseBottomNode(
SUnit *SU)
override {
4153 ReadyQ.push_back(SU);
4154 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
4181template<
bool IsReverse>
4185 return A->NodeNum >
B->NodeNum;
4187 return A->NodeNum <
B->NodeNum;
4207 InstructionShuffler(
bool alternate,
bool topdown)
4208 : IsAlternating(alternate), IsTopDown(topdown) {}
4218 SUnit *pickNode(
bool &IsTopNode)
override {
4222 if (TopQ.empty())
return nullptr;
4229 if (BottomQ.empty())
return nullptr;
4236 IsTopDown = !IsTopDown;
4240 void schedNode(
SUnit *SU,
bool IsTopNode)
override {}
4242 void releaseTopNode(
SUnit *SU)
override {
4245 void releaseBottomNode(
SUnit *SU)
override {
4256 "-misched-topdown incompatible with -misched-bottomup");
4258 C, std::make_unique<InstructionShuffler>(Alternate, TopDown));
4262 "shuffle",
"Shuffle machine instructions alternating directions",
4281 return std::string(
G->MF.getName());
4301 return "color=cyan,style=dashed";
4303 return "color=blue,style=dashed";
4320 return G->getGraphNodeLabel(SU);
4324 std::string Str(
"shape=Mrecord");
4329 Str +=
",style=filled,fillcolor=\"#";
4346 errs() <<
"ScheduleDAGMI::viewGraph is only available in debug builds on "
4347 <<
"systems with Graphviz or gv!\n";
4353 viewGraph(getDAGName(),
"Scheduling-Units Graph for " + getDAGName());
4362 return A.first <
B.first;
4365unsigned ResourceSegments::getFirstAvailableAt(
4366 unsigned CurrCycle,
unsigned AcquireAtCycle,
unsigned ReleaseAtCycle,
4368 IntervalBuilder)
const {
4369 assert(std::is_sorted(std::begin(_Intervals), std::end(_Intervals),
4371 "Cannot execute on an un-sorted set of intervals.");
4375 if (AcquireAtCycle == ReleaseAtCycle)
4378 unsigned RetCycle = CurrCycle;
4380 IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);
4381 for (
auto &
Interval : _Intervals) {
4388 "Invalid intervals configuration.");
4390 NewInterval = IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);
4396 const unsigned CutOff) {
4397 assert(
A.first <=
A.second &&
"Cannot add negative resource usage");
4398 assert(CutOff > 0 &&
"0-size interval history has no use.");
4404 if (
A.first ==
A.second)
4411 "A resource is being overwritten");
4412 _Intervals.push_back(
A);
4418 while (_Intervals.size() > CutOff)
4419 _Intervals.pop_front();
4424 assert(
A.first <=
A.second &&
"Invalid interval");
4425 assert(
B.first <=
B.second &&
"Invalid interval");
4428 if ((
A.first ==
B.first) || (
A.second ==
B.second))
4433 if ((
A.first >
B.first) && (
A.second <
B.second))
4438 if ((
A.first >
B.first) && (
A.first <
B.second) && (
A.second >
B.second))
4443 if ((
A.first <
B.first) && (
B.first <
A.second) && (
B.second >
B.first))
4449void ResourceSegments::sortAndMerge() {
4450 if (_Intervals.size() <= 1)
4457 auto next = std::next(std::begin(_Intervals));
4458 auto E = std::end(_Intervals);
4459 for (; next !=
E; ++next) {
4460 if (std::prev(next)->second >= next->first) {
4461 next->first = std::prev(next)->first;
4462 _Intervals.erase(std::prev(next));
MachineInstrBuilder MachineInstrBuilder & DefMI
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
static const Function * getParent(const Value *V)
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
COFF::MachineTypes Machine
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static std::optional< ArrayRef< InsnRange >::iterator > intersects(const MachineInstr *StartMI, const MachineInstr *EndMI, const ArrayRef< InsnRange > &Ranges, const InstructionOrdering &Ordering)
Check if the instruction range [StartMI, EndMI] intersects any instruction range in Ranges.
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
const HexagonInstrInfo * TII
A common definition of LaneBitmask for use in TableGen and CodeGen.
static bool isSchedBoundary(MachineBasicBlock::iterator MI, MachineBasicBlock *MBB, MachineFunction *MF, const TargetInstrInfo *TII)
Return true of the given instruction should not be included in a scheduling region.
static MachineSchedRegistry ILPMaxRegistry("ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler)
static void tracePick(GenericSchedulerBase::CandReason Reason, bool IsTop)
static cl::opt< bool > EnableMemOpCluster("misched-cluster", cl::Hidden, cl::desc("Enable memop clustering."), cl::init(true))
Machine Instruction Scheduler
static MachineBasicBlock::const_iterator nextIfDebug(MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator End)
If this iterator is a debug value, increment until reaching the End or a non-debug instruction.
static const unsigned MinSubtreeSize
static const unsigned InvalidCycle
static cl::opt< bool > MISchedSortResourcesInTrace("misched-sort-resources-in-trace", cl::Hidden, cl::init(true), cl::desc("Sort the resources printed in the dump trace"))
static cl::opt< bool > EnableCyclicPath("misched-cyclicpath", cl::Hidden, cl::desc("Enable cyclic critical path analysis."), cl::init(true))
static MachineBasicBlock::const_iterator priorNonDebug(MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator Beg)
Decrement this iterator until reaching the top or a non-debug instr.
static cl::opt< MachineSchedRegistry::ScheduleDAGCtor, false, RegisterPassParser< MachineSchedRegistry > > MachineSchedOpt("misched", cl::init(&useDefaultMachineSched), cl::Hidden, cl::desc("Machine instruction scheduler to use"))
MachineSchedOpt allows command line selection of the scheduler.
static cl::opt< bool > EnableMachineSched("enable-misched", cl::desc("Enable the machine instruction scheduling pass."), cl::init(true), cl::Hidden)
static unsigned computeRemLatency(SchedBoundary &CurrZone)
Compute remaining latency.
static cl::opt< unsigned > MISchedCutoff("misched-cutoff", cl::Hidden, cl::desc("Stop scheduling after N instructions"), cl::init(~0U))
static cl::opt< unsigned > SchedOnlyBlock("misched-only-block", cl::Hidden, cl::desc("Only schedule this MBB#"))
static cl::opt< bool > EnableRegPressure("misched-regpressure", cl::Hidden, cl::desc("Enable register pressure scheduling."), cl::init(true))
static MachineSchedRegistry GenericSchedRegistry("converge", "Standard converging scheduler.", createConvergingSched)
static cl::opt< unsigned > HeaderColWidth("misched-dump-schedule-trace-col-header-width", cl::Hidden, cl::desc("Set width of the columns with " "the resources and schedule units"), cl::init(19))
static cl::opt< bool > ForceFastCluster("force-fast-cluster", cl::Hidden, cl::desc("Switch to fast cluster algorithm with the lost " "of some fusion opportunities"), cl::init(false))
static cl::opt< unsigned > FastClusterThreshold("fast-cluster-threshold", cl::Hidden, cl::desc("The threshold for fast cluster"), cl::init(1000))
static bool checkResourceLimit(unsigned LFactor, unsigned Count, unsigned Latency, bool AfterSchedNode)
Given a Count of resource usage and a Latency value, return true if a SchedBoundary becomes resource ...
static ScheduleDAGInstrs * createInstructionShuffler(MachineSchedContext *C)
static ScheduleDAGInstrs * useDefaultMachineSched(MachineSchedContext *C)
A dummy default scheduler factory indicates whether the scheduler is overridden on the command line.
static bool sortIntervals(const ResourceSegments::IntervalTy &A, const ResourceSegments::IntervalTy &B)
Sort predicate for the intervals stored in an instance of ResourceSegments.
static cl::opt< unsigned > ColWidth("misched-dump-schedule-trace-col-width", cl::Hidden, cl::desc("Set width of the columns showing resource booking."), cl::init(5))
static MachineSchedRegistry DefaultSchedRegistry("default", "Use the target's default scheduler choice.", useDefaultMachineSched)
static cl::opt< std::string > SchedOnlyFunc("misched-only-func", cl::Hidden, cl::desc("Only schedule this function"))
static const char * scheduleTableLegend
static ScheduleDAGInstrs * createConvergingSched(MachineSchedContext *C)
static cl::opt< unsigned > ViewMISchedCutoff("view-misched-cutoff", cl::Hidden, cl::desc("Hide nodes with more predecessor/successor than cutoff"))
In some situations a few uninteresting nodes depend on nearly all other nodes in the graph,...
static MachineSchedRegistry ShufflerRegistry("shuffle", "Shuffle machine instructions alternating directions", createInstructionShuffler)
static cl::opt< bool > EnablePostRAMachineSched("enable-post-misched", cl::desc("Enable the post-ra machine instruction scheduling pass."), cl::init(true), cl::Hidden)
static void getSchedRegions(MachineBasicBlock *MBB, MBBRegionsVector &Regions, bool RegionsTopDown)
static cl::opt< unsigned > MIResourceCutOff("misched-resource-cutoff", cl::Hidden, cl::desc("Number of intervals to track"), cl::init(10))
static ScheduleDAGInstrs * createILPMaxScheduler(MachineSchedContext *C)
static cl::opt< unsigned > ReadyListLimit("misched-limit", cl::Hidden, cl::desc("Limit ready list to N instructions"), cl::init(256))
Avoid quadratic complexity in unusually large basic blocks by limiting the size of the ready lists.
static ScheduleDAGInstrs * createILPMinScheduler(MachineSchedContext *C)
static cl::opt< bool > MISchedDumpScheduleTrace("misched-dump-schedule-trace", cl::Hidden, cl::init(false), cl::desc("Dump resource usage at schedule boundary."))
static MachineSchedRegistry ILPMinRegistry("ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler)
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the PriorityQueue class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isSimple(Instruction *I)
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringLiteral > StandardNames)
Initialize the set of available library functions based on the specified target triple.
This file describes how to lower LLVM code to machine code.
Target-Independent Code Generator Pass Configuration Options pass.
static const X86InstrFMA3Group Groups[]
Class recording the (high level) value of a variable.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
reverse_iterator rend() const
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
reverse_iterator rbegin() const
bool test(unsigned Idx) const
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void clear()
clear - Removes all bits from the bitvector.
This class represents an Operation in the Expression.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
void traceCandidate(const SchedCandidate &Cand)
void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone, SchedBoundary *OtherZone)
Set the CandPolicy given a scheduling zone given the current resources and latencies inside and outsi...
const TargetSchedModel * SchedModel
static const char * getReasonStr(GenericSchedulerBase::CandReason Reason)
const MachineSchedContext * Context
CandReason
Represent the type of SchedCandidate found within a single queue.
const TargetRegisterInfo * TRI
void checkAcyclicLatency()
Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic critical path by more cycle...
virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand, SchedBoundary *Zone) const
Apply a set of heuristics to a new candidate.
void dumpPolicy() const override
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop, const RegPressureTracker &RPTracker, RegPressureTracker &TempTracker)
void registerRoots() override
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Initialize the per-region scheduling policy.
void reschedulePhysReg(SUnit *SU, bool isTop)
SUnit * pickNode(bool &IsTopNode) override
Pick the best node to balance the schedule. Implements MachineSchedStrategy.
void pickNodeFromQueue(SchedBoundary &Zone, const CandPolicy &ZonePolicy, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the queue.
void schedNode(SUnit *SU, bool IsTopNode) override
Update the scheduler's state after scheduling a node.
SUnit * pickNodeBidirectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
bool getMemOperandsWithOffsetWidth(const MachineInstr &LdSt, SmallVectorImpl< const MachineOperand * > &BaseOps, int64_t &Offset, bool &OffsetIsScalable, LocationSize &Width, const TargetRegisterInfo *TRI) const override
Get the base register and byte offset of a load/store instr.
bool isSchedulingBoundary(const MachineInstr &MI, const MachineBasicBlock *MBB, const MachineFunction &MF) const override
Test if the given instruction should be considered a scheduling boundary.
Itinerary data supplied by a subtarget to be used by a target.
Interval Class - An Interval is a set of nodes defined such that every node in the interval has all o...
LiveInterval - This class represents the liveness of a register, or stack slot.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
void handleMove(MachineInstr &MI, bool UpdateFlags=false)
Call this method to notify LiveIntervals that instruction MI has been moved within a basic block.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const
Return the last index in the given basic block.
LiveInterval & getInterval(Register Reg)
Result of a LiveRange query.
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx,...
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
bool isLocal(SlotIndex Start, SlotIndex End) const
True iff this segment is a single segment that lies between the specified boundaries,...
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Function & getFunction()
Return the LLVM function that this machine code represents.
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
nonconst_iterator getNonConstIterator() const
Representation of each machine instruction.
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
MachineOperand class - Representation of each machine instruction operand.
MachinePassRegistry - Track the registration of machine passes.
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
MachineSchedRegistry provides a selection of available machine instruction schedulers.
static MachinePassRegistry< ScheduleDAGCtor > Registry
ScheduleDAGInstrs *(*)(MachineSchedContext *) ScheduleDAGCtor
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
A Module instance is used to store all the information related to an LLVM module.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Optionally override the per-region scheduling policy.
virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand)
Apply a set of heuristics to a new candidate for PostRA scheduling.
void schedNode(SUnit *SU, bool IsTopNode) override
Called after ScheduleDAGMI has scheduled an instruction and updated scheduled/remaining flags in the ...
void pickNodeFromQueue(SchedBoundary &Zone, SchedCandidate &Cand)
void initialize(ScheduleDAGMI *Dag) override
Initialize the strategy after building the DAG for a new region.
void registerRoots() override
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
SUnit * pickNode(bool &IsTopNode) override
Pick the next node to schedule.
Capture a change in pressure for a single pressure set.
unsigned getPSetOrMax() const
List of PressureChanges in order of increasing, unique PSetID.
void dump(const TargetRegisterInfo &TRI) const
void addPressureChange(Register RegUnit, bool IsDec, const MachineRegisterInfo *MRI)
Add a change in pressure to the pressure diff of a given instruction.
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
void clear()
clear - Erase all elements from the queue.
Helpers for implementing custom MachineSchedStrategy classes.
ArrayRef< SUnit * > elements()
bool isInQueue(SUnit *SU) const
std::vector< SUnit * >::iterator iterator
StringRef getName() const
iterator remove(iterator I)
Track the current register pressure at some position in the instruction stream, and remember the high...
void closeRegion()
Finalize the region boundaries and recored live ins and live outs.
void recede(SmallVectorImpl< RegisterMaskPair > *LiveUses=nullptr)
Recede across the previous instruction.
void setPos(MachineBasicBlock::const_iterator Pos)
ArrayRef< unsigned > getLiveThru() const
void closeBottom()
Set the boundary for the bottom of the region and summarize live outs.
RegisterPressure & getPressure()
Get the resulting register pressure over the traversed region.
void recedeSkipDebugValues()
Recede until we find an instruction which is not a DebugValue.
void getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
Consider the pressure increase caused by traversing this instruction bottom-up.
void initLiveThru(const RegPressureTracker &RPTracker)
Initialize the LiveThru pressure set based on the untied defs found in RPTracker.
void init(const MachineFunction *mf, const RegisterClassInfo *rci, const LiveIntervals *lis, const MachineBasicBlock *mbb, MachineBasicBlock::const_iterator pos, bool TrackLaneMasks, bool TrackUntiedDefs)
Setup the RegPressureTracker.
MachineBasicBlock::const_iterator getPos() const
Get the MI position corresponding to this register pressure.
void closeTop()
Set the boundary for the top of the region and summarize live ins.
void getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
Consider the pressure increase caused by traversing this instruction top-down.
void advance()
Advance across the current instruction.
const std::vector< unsigned > & getRegSetPressureAtPos() const
Get the register set pressure at the current position, which may be less than the pressure across the...
void addLiveRegs(ArrayRef< RegisterMaskPair > Regs)
Force liveness of virtual registers or physical register units.
void getUpwardPressureDelta(const MachineInstr *MI, PressureDiff &PDiff, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit) const
This is the fast version of querying register pressure that does not directly depend on current liven...
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
unsigned getRegPressureSetLimit(unsigned Idx) const
Get the register unit limit for the given pressure set index.
List of registers defined and used by a machine instruction.
void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
void adjustLaneLiveness(const LiveIntervals &LIS, const MachineRegisterInfo &MRI, SlotIndex Pos, MachineInstr *AddFlagsMI=nullptr)
Use liveness information to find out which uses/defs are partially undefined/dead and adjust the Regi...
void detectDeadDefs(const MachineInstr &MI, const LiveIntervals &LIS)
Use liveness information to find dead defs not marked with a dead flag and move them to the DeadDefs ...
RegisterPassParser class - Handle the addition of new machine passes.
Wrapper class representing virtual and physical registers.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
void add(IntervalTy A, const unsigned CutOff=10)
Adds an interval [a, b) to the collection of the instance.
static IntervalTy getResourceIntervalBottom(unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)
These function return the interval used by a resource in bottom and top scheduling.
static bool intersects(IntervalTy A, IntervalTy B)
Checks whether intervals intersect.
std::pair< int64_t, int64_t > IntervalTy
Represents an interval of discrete integer values closed on the left and open on the right: [a,...
static IntervalTy getResourceIntervalTop(unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)
Kind getKind() const
Returns an enum value representing the kind of the dependence.
@ Anti
A register anti-dependence (aka WAR).
@ Data
Regular data dependence (aka true-dependence).
bool isWeak() const
Tests if this a weak dependence.
@ Cluster
Weak DAG edge linking a chain of clustered instrs.
@ Artificial
Arbitrary strong DAG edge (no real dependence).
@ Weak
Arbitrary weak DAG edge.
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
unsigned getReg() const
Returns the register associated with this edge.
bool isCluster() const
Tests if this is an Order dependence that is marked as "cluster", meaning it is artificial and wants ...
bool isArtificialDep() const
bool isCtrlDep() const
Tests if this is not an SDep::Data dependence.
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.
void biasCriticalPath()
Orders this node's predecessor edges such that the critical path edge occurs first.
bool isUnbuffered
Uses an unbuffered resource.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
unsigned short Latency
Node latency.
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.
bool hasPhysRegDefs
Has physreg defs that are being used.
unsigned BotReadyCycle
Cycle relative to end when node is ready.
SmallVector< SDep, 4 > Succs
All sunit successors.
bool hasReservedResource
Uses a reserved resource.
bool isBottomReady() const
bool hasPhysRegUses
Has physreg uses.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Each Scheduling boundary is associated with ready queues.
unsigned getNextResourceCycleByInstance(unsigned InstanceIndex, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)
Compute the next cycle at which the given processor resource unit can be scheduled.
void releasePending()
Release pending ready nodes in to the available queue.
unsigned getDependentLatency() const
unsigned getScheduledLatency() const
Get the number of latency cycles "covered" by the scheduled instructions.
void incExecutedResources(unsigned PIdx, unsigned Count)
bool isResourceLimited() const
const TargetSchedModel * SchedModel
unsigned getExecutedCount() const
Get a scaled count for the minimum execution time of the scheduled micro-ops that are ready to execut...
unsigned getLatencyStallCycles(SUnit *SU)
Get the difference between the given SUnit's ready time and the current cycle.
unsigned findMaxLatency(ArrayRef< SUnit * > ReadySUs)
void dumpReservedCycles() const
Dump the state of the information that tracks resource usage.
unsigned getOtherResourceCount(unsigned &OtherCritIdx)
void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
unsigned getCriticalCount() const
Get the scaled count of scheduled micro-ops and resources, including executed resources.
SUnit * pickOnlyChoice()
Call this before applying any other heuristics to the Available queue.
void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue, unsigned Idx=0)
Release SU to make it ready.
unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx, unsigned Cycles, unsigned ReadyCycle, unsigned StartAtCycle)
Add the given processor resource to this scheduled zone.
ScheduleHazardRecognizer * HazardRec
bool isUnbufferedGroup(unsigned PIdx) const
void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem)
unsigned getResourceCount(unsigned ResIdx) const
void bumpCycle(unsigned NextCycle)
Move the boundary of scheduled code by one cycle.
unsigned getCurrMOps() const
Micro-ops issued in the current cycle.
unsigned getCurrCycle() const
Number of cycles to issue the instructions scheduled in this zone.
bool checkHazard(SUnit *SU)
Does this SU have a hazard within the current instruction group.
std::pair< unsigned, unsigned > getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)
Compute the next cycle at which the given processor resource can be scheduled.
void dumpScheduledState() const
void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
unsigned getZoneCritResIdx() const
unsigned getUnscheduledLatency(SUnit *SU) const
Compute the values of each DAG node for various metrics during DFS.
unsigned getNumInstrs(const SUnit *SU) const
Get the number of instructions in the given subtree and its children.
unsigned getSubtreeID(const SUnit *SU) const
Get the ID of the subtree the given DAG node belongs to.
void clear()
Clear the results.
ILPValue getILP(const SUnit *SU) const
Get the ILP value for a DAG node.
void compute(ArrayRef< SUnit > SUnits)
Compute various metrics for the DAG with given roots.
unsigned getNumSubtrees() const
The number of subtrees detected in this DAG.
unsigned getSubtreeLevel(unsigned SubtreeID) const
Get the connection level of a subtree.
void resize(unsigned NumSUnits)
Initialize the result data with the size of the DAG.
void scheduleTree(unsigned SubtreeID)
Scheduler callback to update SubtreeConnectLevels when a tree is initially scheduled.
A ScheduleDAG for scheduling lists of MachineInstr.
virtual void finishBlock()
Cleans up after scheduling in the given block.
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
MachineBasicBlock * BB
The block in which to insert instructions.
MachineInstr * FirstDbgValue
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
const TargetSchedModel * getSchedModel() const
Gets the machine model for instruction scheduling.
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
bool addEdge(SUnit *SuccSU, const SDep &PredDep)
Add a DAG edge to the given SU with the given predecessor dependence data.
DumpDirection
The direction that should be used to dump the scheduled Sequence.
bool TrackLaneMasks
Whether lane masks should get tracked.
void dumpNode(const SUnit &SU) const override
bool IsReachable(SUnit *SU, SUnit *TargetSU)
IsReachable - Checks if SU is reachable from TargetSU.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
SUnit * getSUnit(MachineInstr *MI) const
Returns an existing SUnit for this MI, or nullptr.
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)
True if an edge can be added from PredSU to SuccSU without creating a cycle.
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
void dump() const override
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
void scheduleMI(SUnit *SU, bool IsTopNode)
Move an instruction and update register pressure.
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
VReg2SUnitMultiMap VRegUses
Maps vregs to the SUnits of their uses in the current scheduling region.
void computeDFSResult()
Compute a DFSResult after DAG building is complete, and before any queue comparisons.
PressureDiff & getPressureDiff(const SUnit *SU)
SchedDFSResult * DFSResult
Information about DAG subtrees.
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
void initQueues(ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)
Release ExitSU predecessors and setup scheduler queues.
void updatePressureDiffs(ArrayRef< RegisterMaskPair > LiveUses)
Update the PressureDiff array for liveness after scheduling this instruction.
bool ShouldTrackLaneMasks
RegPressureTracker BotRPTracker
void buildDAGWithRegPressure()
Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking enabled.
std::vector< PressureChange > RegionCriticalPSets
List of pressure sets that exceed the target's pressure limit before scheduling, listed in increasing...
void updateScheduledPressure(const SUnit *SU, const std::vector< unsigned > &NewMaxPressure)
PressureDiffs SUPressureDiffs
unsigned computeCyclicCriticalPath()
Compute the cyclic critical path through the DAG.
void collectVRegUses(SUnit &SU)
RegisterClassInfo * RegClassInfo
const SchedDFSResult * getDFSResult() const
Return a non-null DFS result if the scheduling strategy initialized it.
RegPressureTracker RPTracker
bool ShouldTrackPressure
Register pressure in this region computed by initRegPressure.
~ScheduleDAGMILive() override
void dump() const override
BitVector & getScheduledTrees()
MachineBasicBlock::iterator LiveRegionEnd
RegPressureTracker TopRPTracker
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 startBlock(MachineBasicBlock *bb) override
Prepares to perform scheduling in the given block.
void releasePred(SUnit *SU, SDep *PredEdge)
ReleasePred - Decrement the NumSuccsLeft count of a predecessor.
void initQueues(ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)
Release ExitSU predecessors and setup scheduler queues.
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
Add a postprocessing step to the DAG builder.
void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos)
Change the position of an instruction within the basic block and update live ranges and region bounda...
void releasePredecessors(SUnit *SU)
releasePredecessors - Call releasePred on each of SU's predecessors.
void postProcessDAG()
Apply each ScheduleDAGMutation step in order.
const SUnit * NextClusterSucc
void dumpScheduleTraceTopDown() const
Print execution trace of the schedule top-down or bottom-up.
const SUnit * NextClusterPred
Record the next node in a scheduled cluster.
MachineBasicBlock::iterator top() const
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
MachineBasicBlock::iterator bottom() const
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
virtual bool hasVRegLiveness() const
Return true if this DAG supports VReg liveness and RegPressure.
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
LiveIntervals * getLIS() const
void viewGraph() override
Out-of-line implementation with no arguments is handy for gdb.
void releaseSucc(SUnit *SU, SDep *SuccEdge)
ReleaseSucc - Decrement the NumPredsLeft count of a successor.
void dumpScheduleTraceBottomUp() const
~ScheduleDAGMI() override
void finishBlock() override
Cleans up after scheduling in the given block.
const SUnit * getNextClusterPred() const
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.
void releaseSuccessors(SUnit *SU)
releaseSuccessors - Call releaseSucc on each of SU's successors.
const SUnit * getNextClusterSucc() const
std::vector< std::unique_ptr< ScheduleDAGMutation > > Mutations
Ordered list of DAG postprocessing steps.
Mutate the DAG as a postpass after normal DAG building.
MachineRegisterInfo & MRI
Virtual/real register map.
const TargetInstrInfo * TII
Target instruction information.
std::vector< SUnit > SUnits
The scheduling units.
const TargetRegisterInfo * TRI
Target processor register info.
SUnit EntrySU
Special node for the region entry.
MachineFunction & MF
Machine function.
void dumpNodeAll(const SUnit &SU) const
SUnit ExitSU
Special node for the region exit.
virtual void RecedeCycle()
RecedeCycle - This callback is invoked whenever the next bottom-up instruction to be scheduled cannot...
virtual void Reset()
Reset - This callback is invoked when a new block of instructions is about to be schedule.
virtual void EmitInstruction(SUnit *)
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
virtual void AdvanceCycle()
AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...
virtual HazardType getHazardType(SUnit *, int Stalls=0)
getHazardType - Return the hazard type of emitting this node.
SlotIndex - An opaque wrapper around machine indexes.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
std::reverse_iterator< const_iterator > const_reverse_iterator
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
iterator find(const KeyT &Key)
Find an element by its key.
void clear()
Clears the set.
iterator end()
Returns an iterator past this container.
iterator insert(const ValueT &Val)
Insert a new element at the tail of the subset list.
iterator_base< SparseMultiSet * > iterator
void setUniverse(unsigned U)
Set the universe size which determines the largest key the set can hold.
Information about stack frame layout on the target.
StackDirection getStackGrowthDirection() const
getStackGrowthDirection - Return the direction the stack grows
TargetInstrInfo - Interface to description of machine instruction set.
virtual ScheduleHazardRecognizer * CreateTargetMIHazardRecognizer(const InstrItineraryData *, const ScheduleDAGMI *DAG) const
Allocate and return a hazard recognizer to use for this target when scheduling the machine instructio...
virtual const TargetRegisterClass * getRegClassFor(MVT VT, bool isDivergent=false) const
Return the register class that should be used for the specified value type.
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Target-Independent Code Generator Pass Configuration Options.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const char * getRegPressureSetName(unsigned Idx) const =0
Get the name of this register unit pressure set.
Provide an instruction scheduling machine model to CodeGen passes.
const char * getResourceName(unsigned PIdx) const
bool mustEndGroup(const MachineInstr *MI, const MCSchedClassDesc *SC=nullptr) const
Return true if current group must end.
unsigned getIssueWidth() const
Maximum number of micro-ops that may be scheduled per cycle.
unsigned getMicroOpFactor() const
Multiply number of micro-ops by this factor to normalize it relative to other resources.
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model.
bool mustBeginGroup(const MachineInstr *MI, const MCSchedClassDesc *SC=nullptr) const
Return true if new group must begin.
unsigned getLatencyFactor() const
Multiply cycle count by this factor to normalize it relative to other resources.
unsigned getResourceFactor(unsigned ResIdx) const
Multiply the number of units consumed for a resource by this factor to normalize it relative to other...
unsigned getMicroOpBufferSize() const
Number of micro-ops that may be buffered for OOO execution.
unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC=nullptr) const
Return the number of issue slots required for this MI.
const MCProcResourceDesc * getProcResource(unsigned PIdx) const
Get a processor resource by ID for convenience.
unsigned getNumProcResourceKinds() const
Get the number of kinds of resources for this target.
const InstrItineraryData * getInstrItineraries() const
bool enableIntervals() const
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual std::vector< MacroFusionPredTy > getMacroFusions() const
Get the list of MacroFusion predicates.
virtual bool enableMachineScheduler() const
True if the subtarget should run MachineScheduler after aggressive coalescing.
virtual void overrideSchedPolicy(MachineSchedPolicy &Policy, unsigned NumRegionInstrs) const
Override generic scheduling policy within a region.
virtual bool enablePostRAMachineScheduler() const
True if the subtarget should run a machine scheduler after register allocation.
virtual const TargetFrameLowering * getFrameLowering() const
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetLowering * getTargetLowering() const
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
VNInfo - Value Number Information.
SlotIndex def
The index of the defining instruction.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
StringRef getColorString(unsigned NodeNumber)
Get a color string for this node number.
void apply(Opt *O, const Mod &M, const Mods &... Ms)
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool operator<(int64_t V1, const APSInt &V2)
void stable_sort(R &&Range)
cl::opt< MISchedPostRASched::Direction > PostRADirection("misched-postra-direction", cl::Hidden, cl::desc("Post reg-alloc list scheduling direction"), cl::init(MISchedPostRASched::TopDown), cl::values(clEnumValN(MISchedPostRASched::TopDown, "topdown", "Force top-down post reg-alloc list scheduling"), clEnumValN(MISchedPostRASched::BottomUp, "bottomup", "Force bottom-up post reg-alloc list scheduling")))
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
cl::opt< bool > PrintDAGs
unsigned getWeakLeft(const SUnit *SU, bool isTop)
std::unique_ptr< ScheduleDAGMutation > createMacroFusionDAGMutation(ArrayRef< MacroFusionPredTy > Predicates, bool BranchOnly=false)
Create a DAG scheduling mutation to pair instructions back to back for instructions that benefit acco...
FormattedString right_justify(StringRef Str, unsigned Width)
right_justify - add spaces before string so total output is Width characters.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
cl::opt< bool > MISchedDumpReservedCycles("misched-dump-reserved-cycles", cl::Hidden, cl::init(false), cl::desc("Dump resource usage at schedule boundary."))
void initializePostMachineSchedulerPass(PassRegistry &)
cl::opt< bool > VerifyScheduling
char & MachineSchedulerID
MachineScheduler - This pass schedules machine instructions.
char & PostMachineSchedulerID
PostMachineScheduler - This pass schedules machine instructions postRA.
ScheduleDAGMILive * createGenericSchedLive(MachineSchedContext *C)
Create the standard converging machine scheduler.
cl::opt< bool > ViewMISchedDAGs
bool tryPressure(const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason, const TargetRegisterInfo *TRI, const MachineFunction &MF)
void sort(IteratorTy Start, IteratorTy End)
Printable printVRegOrUnit(unsigned VRegOrUnit, const TargetRegisterInfo *TRI)
Create Printable object to print virtual registers and physical registers on a raw_ostream.
std::unique_ptr< ScheduleDAGMutation > createStoreClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ReorderWhileClustering=false)
If ReorderWhileClustering is set to true, no attempt will be made to reduce reordering due to store c...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
cl::opt< bool > DumpCriticalPathLength("misched-dcpl", cl::Hidden, cl::desc("Print critical path length to stdout"))
bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)
cl::opt< bool > ForceBottomUp
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void initializeMachineSchedulerPass(PassRegistry &)
ScheduleDAGMI * createGenericSchedPostRA(MachineSchedContext *C)
Create a generic scheduler with no vreg liveness or DAG mutation passes.
FormattedString left_justify(StringRef Str, unsigned Width)
left_justify - append spaces after string so total output is Width characters.
std::unique_ptr< ScheduleDAGMutation > createLoadClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ReorderWhileClustering=false)
If ReorderWhileClustering is set to true, no attempt will be made to reduce reordering due to store c...
bool tryGreater(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)
ViewGraph - Emit a dot graph, run 'dot', run gv on the postscript file, then cleanup.
cl::opt< bool > ForceTopDown
void dumpRegSetPressure(ArrayRef< unsigned > SetPressure, const TargetRegisterInfo *TRI)
bool tryLess(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
Return true if this heuristic determines order.
std::unique_ptr< ScheduleDAGMutation > createCopyConstrainDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
cl::opt< bool > MischedDetailResourceBooking("misched-detail-resource-booking", cl::Hidden, cl::init(false), cl::desc("Show details of invoking getNextResoufceCycle."))
int biasPhysReg(const SUnit *SU, bool isTop)
Minimize physical register live ranges.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G)
static std::string getEdgeAttributes(const SUnit *Node, SUnitIterator EI, const ScheduleDAG *Graph)
If you want to override the dot attributes printed for a particular edge, override this method.
static std::string getGraphName(const ScheduleDAG *G)
static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G)
static bool isNodeHidden(const SUnit *Node, const ScheduleDAG *G)
DOTGraphTraits(bool isSimple=false)
static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G)
static bool renderGraphFromBottomUp()
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
Policy for scheduling the next instruction in the candidate's zone.
Store the state used by GenericScheduler heuristics, required for the lifetime of one invocation of p...
void setBest(SchedCandidate &Best)
void reset(const CandPolicy &NewPolicy)
void initResourceDelta(const ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)
SchedResourceDelta ResDelta
Status of an instruction's critical resource consumption.
unsigned DemandedResources
static constexpr LaneBitmask getNone()
const unsigned * SubUnitsIdxBegin
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
RegisterClassInfo * RegClassInfo
virtual ~MachineSchedContext()
PressureChange CriticalMax
PressureChange CurrentMax
RegisterPressure computed within a region of instructions delimited by TopPos and BottomPos.
SmallVector< RegisterMaskPair, 8 > LiveInRegs
List of live in virtual registers or physical register units.
std::vector< unsigned > MaxSetPressure
Map of max reg pressure indexed by pressure set ID, not class ID.
SmallVector< RegisterMaskPair, 8 > LiveOutRegs
Summarize the unscheduled region.
void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)
SmallVector< unsigned, 16 > RemainingCounts
bool IsAcyclicLatencyLimited
An individual mapping from virtual register number to SUnit.