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 {
93 cl::desc(
"Post reg-alloc list scheduling direction"),
99 "Force top-down post reg-alloc list scheduling"),
101 "Force bottom-up post reg-alloc list scheduling"),
103 "Force bidirectional post reg-alloc list scheduling")));
106 cl::desc(
"Print critical path length to stdout"));
110 cl::desc(
"Verify machine instrs before and after machine scheduling"));
115 cl::desc(
"Pop up a window to show MISched dags after they are processed"));
120 cl::desc(
"Dump resource usage at schedule boundary."));
123 cl::desc(
"Show details of invoking getNextResoufceCycle."));
128#ifdef LLVM_ENABLE_DUMP
139 cl::desc(
"Hide nodes with more predecessor/successor than cutoff"));
145 cl::desc(
"Only schedule this function"));
147 cl::desc(
"Only schedule this MBB#"));
162 cl::desc(
"Enable memop clustering."),
166 cl::desc(
"Switch to fast cluster algorithm with the lost "
167 "of some fusion opportunities"),
171 cl::desc(
"The threshold for fast cluster"),
174#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
177 cl::desc(
"Dump resource usage at schedule boundary."));
180 cl::desc(
"Set width of the columns with "
181 "the resources and schedule units"),
185 cl::desc(
"Set width of the columns showing resource booking."),
189 cl::desc(
"Sort the resources printed in the dump trace"));
200void MachineSchedStrategy::anchor() {}
202void ScheduleDAGMutation::anchor() {}
231class MachineScheduler :
public MachineSchedulerBase {
246class PostMachineScheduler :
public MachineSchedulerBase {
248 PostMachineScheduler();
262char MachineScheduler::ID = 0;
267 "Machine Instruction Scheduler",
false,
false)
276MachineScheduler::MachineScheduler() : MachineSchedulerBase(
ID) {
280void MachineScheduler::getAnalysisUsage(
AnalysisUsage &AU)
const {
293char PostMachineScheduler::ID = 0;
298 "PostRA Machine Instruction Scheduler",
false,
false)
305PostMachineScheduler::PostMachineScheduler() : MachineSchedulerBase(
ID) {
309void PostMachineScheduler::getAnalysisUsage(
AnalysisUsage &AU)
const {
332 cl::desc(
"Machine instruction scheduler to use"));
340 cl::desc(
"Enable the machine instruction scheduling pass."),
cl::init(
true),
344 "enable-post-misched",
345 cl::desc(
"Enable the post-ra machine instruction scheduling pass."),
352 assert(
I != Beg &&
"reached the top of the region, cannot decrement");
354 if (!
I->isDebugOrPseudoInstr())
373 for(;
I !=
End; ++
I) {
374 if (!
I->isDebugOrPseudoInstr())
447 MLI = &getAnalysis<MachineLoopInfo>();
448 MDT = &getAnalysis<MachineDominatorTree>();
449 PassConfig = &getAnalysis<TargetPassConfig>();
450 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
452 LIS = &getAnalysis<LiveIntervals>();
456 MF->verify(
this,
"Before machine scheduling.");
458 RegClassInfo->runOnMachineFunction(*MF);
462 std::unique_ptr<ScheduleDAGInstrs>
Scheduler(createMachineScheduler());
475 MF->verify(
this,
"After machine scheduling.");
494 MLI = &getAnalysis<MachineLoopInfo>();
495 PassConfig = &getAnalysis<TargetPassConfig>();
496 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
499 MF->verify(
this,
"Before post machine scheduling.");
503 std::unique_ptr<ScheduleDAGInstrs>
Scheduler(createPostMachineScheduler());
515 MF->verify(
this,
"After post machine scheduling.");
546 unsigned NumRegionInstrs;
550 RegionBegin(
B), RegionEnd(
E), NumRegionInstrs(
N) {}
559 bool RegionsTopDown) {
565 RegionEnd !=
MBB->
begin(); RegionEnd =
I) {
568 if (RegionEnd !=
MBB->
end() ||
575 unsigned NumRegionInstrs = 0;
581 if (!
MI.isDebugOrPseudoInstr()) {
590 if (NumRegionInstrs != 0)
591 Regions.
push_back(SchedRegion(
I, RegionEnd, NumRegionInstrs));
595 std::reverse(Regions.
begin(), Regions.
end());
634 for (
const SchedRegion &R : MBBRegions) {
637 unsigned NumRegionInstrs =
R.NumRegionInstrs;
644 if (
I == RegionEnd ||
I == std::prev(RegionEnd)) {
655 else dbgs() <<
"End\n";
656 dbgs() <<
" RegionInstrs: " << NumRegionInstrs <<
'\n');
658 errs() << MF->getName();
684#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
686 dbgs() <<
"Queue " << Name <<
": ";
687 for (
const SUnit *SU : Queue)
688 dbgs() << SU->NodeNum <<
" ";
717 dbgs() <<
"*** Scheduling failed! ***\n";
719 dbgs() <<
" has been released too many times!\n";
754 dbgs() <<
"*** Scheduling failed! ***\n";
756 dbgs() <<
" has been released too many times!\n";
793 unsigned regioninstrs)
821#if LLVM_ENABLE_ABI_BREAKING_CHECKS && !defined(NDEBUG)
826 ++NumInstrsScheduled;
858 bool IsTopNode =
false;
860 LLVM_DEBUG(
dbgs() <<
"** ScheduleDAGMI::schedule picking next node\n");
901 dbgs() <<
"*** Final schedule for "
918 assert(!SU.isBoundaryNode() &&
"Boundary node should not be in SUnits");
921 SU.biasCriticalPath();
924 if (!SU.NumPredsLeft)
927 if (!SU.NumSuccsLeft)
943 for (
SUnit *SU : TopRoots)
982 for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator
984 std::pair<MachineInstr *, MachineInstr *>
P = *std::prev(DI);
995#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1007 dbgs() <<
" * Schedule table (TopDown):\n";
1025 for (
unsigned C = FirstCycle;
C <= LastCycle; ++
C)
1032 dbgs() <<
"Missing SUnit\n";
1035 std::string NodeName(
"SU(");
1036 NodeName += std::to_string(SU->
NodeNum) +
")";
1038 unsigned C = FirstCycle;
1039 for (;
C <= LastCycle; ++
C) {
1056 return LHS.AcquireAtCycle <
RHS.AcquireAtCycle ||
1057 (
LHS.AcquireAtCycle ==
RHS.AcquireAtCycle &&
1058 LHS.ReleaseAtCycle <
RHS.ReleaseAtCycle);
1062 const std::string ResName =
1068 for (
unsigned I = 0, E = PI.ReleaseAtCycle - PI.AcquireAtCycle;
I != E;
1071 while (
C++ <= LastCycle)
1088 dbgs() <<
" * Schedule table (BottomUp):\n";
1101 if ((
int)SU->
BotReadyCycle - PI->ReleaseAtCycle + 1 < LastCycle)
1102 LastCycle = (int)SU->
BotReadyCycle - PI->ReleaseAtCycle + 1;
1107 for (
int C = FirstCycle;
C >= LastCycle; --
C)
1114 dbgs() <<
"Missing SUnit\n";
1117 std::string NodeName(
"SU(");
1118 NodeName += std::to_string(SU->
NodeNum) +
")";
1121 for (;
C >= LastCycle; --
C) {
1137 return LHS.AcquireAtCycle <
RHS.AcquireAtCycle ||
1138 (
LHS.AcquireAtCycle ==
RHS.AcquireAtCycle &&
1139 LHS.ReleaseAtCycle <
RHS.ReleaseAtCycle);
1143 const std::string ResName =
1149 for (
unsigned I = 0, E = PI.ReleaseAtCycle - PI.AcquireAtCycle;
I != E;
1152 while (
C-- >= LastCycle)
1161#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1169 dbgs() <<
"* Schedule table (Bidirectional): not implemented\n";
1171 dbgs() <<
"* Schedule table: DumpDirection not set.\n";
1179 dbgs() <<
"Missing SUnit\n";
1204 if (!Reg.isVirtual())
1209 bool FoundDef =
false;
1211 if (MO2.getReg() == Reg && !MO2.isDead()) {
1238 unsigned regioninstrs)
1252 "ShouldTrackLaneMasks requires ShouldTrackPressure");
1303 dbgs() <<
"Bottom Pressure:\n";
1309 "Can't find the region bottom");
1333 const std::vector<unsigned> &NewMaxPressure) {
1339 unsigned ID = PC.getPSet();
1344 && NewMaxPressure[
ID] <= (
unsigned)std::numeric_limits<int16_t>::max())
1348 if (NewMaxPressure[
ID] >= Limit - 2) {
1350 << NewMaxPressure[
ID]
1351 << ((NewMaxPressure[
ID] > Limit) ?
" > " :
" <= ")
1365 if (!Reg.isVirtual())
1373 bool Decrement =
P.LaneMask.any();
1377 SUnit &SU = *V2SU.SU;
1406 assert(VNI &&
"No live value at use.");
1409 SUnit *SU = V2SU.SU;
1429#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1435 dbgs() <<
" Pressure Diff : ";
1438 dbgs() <<
" Single Issue : ";
1482 bool IsTopNode =
false;
1484 LLVM_DEBUG(
dbgs() <<
"** ScheduleDAGMILive::schedule picking next node\n");
1513 dbgs() <<
"*** Final schedule for "
1585 unsigned MaxCyclicLatency = 0;
1589 if (!Reg.isVirtual())
1601 unsigned LiveOutHeight = DefSU->
getHeight();
1606 SUnit *SU = V2SU.SU;
1618 unsigned CyclicLatency = 0;
1620 CyclicLatency = LiveOutDepth - SU->
getDepth();
1623 if (LiveInHeight > LiveOutHeight) {
1624 if (LiveInHeight - LiveOutHeight < CyclicLatency)
1625 CyclicLatency = LiveInHeight - LiveOutHeight;
1630 << SU->
NodeNum <<
") = " << CyclicLatency <<
"c\n");
1631 if (CyclicLatency > MaxCyclicLatency)
1632 MaxCyclicLatency = CyclicLatency;
1635 LLVM_DEBUG(
dbgs() <<
"Cyclic Critical Path: " << MaxCyclicLatency <<
"c\n");
1636 return MaxCyclicLatency;
1688 if (&*priorII ==
MI)
1739 bool OffsetIsScalable;
1743 : SU(SU), BaseOps(BaseOps.begin(), BaseOps.end()),
Offset(
Offset),
1744 Width(Width), OffsetIsScalable(OffsetIsScalable) {}
1748 if (
A->getType() !=
B->getType())
1749 return A->getType() <
B->getType();
1751 return A->getReg() <
B->getReg();
1757 return StackGrowsDown ?
A->getIndex() >
B->getIndex()
1758 :
A->getIndex() <
B->getIndex();
1768 if (std::lexicographical_compare(BaseOps.
begin(), BaseOps.
end(),
1769 RHS.BaseOps.begin(),
RHS.BaseOps.end(),
1772 if (std::lexicographical_compare(
RHS.BaseOps.begin(),
RHS.BaseOps.end(),
1773 BaseOps.
begin(), BaseOps.
end(), Compare))
1784 bool ReorderWhileClustering;
1789 bool ReorderWhileClustering)
1790 :
TII(tii),
TRI(tri), IsLoad(IsLoad),
1791 ReorderWhileClustering(ReorderWhileClustering) {}
1798 void collectMemOpRecords(std::vector<SUnit> &SUnits,
1804class StoreClusterMutation :
public BaseMemOpClusterMutation {
1808 bool ReorderWhileClustering)
1809 : BaseMemOpClusterMutation(tii, tri,
false, ReorderWhileClustering) {}
1812class LoadClusterMutation :
public BaseMemOpClusterMutation {
1815 bool ReorderWhileClustering)
1816 : BaseMemOpClusterMutation(tii, tri,
true, ReorderWhileClustering) {}
1823std::unique_ptr<ScheduleDAGMutation>
1826 bool ReorderWhileClustering) {
1828 TII,
TRI, ReorderWhileClustering)
1832std::unique_ptr<ScheduleDAGMutation>
1835 bool ReorderWhileClustering) {
1837 TII,
TRI, ReorderWhileClustering)
1848void BaseMemOpClusterMutation::clusterNeighboringMemOps(
1858 auto MemOpa = MemOpRecords[
Idx];
1861 unsigned NextIdx =
Idx + 1;
1862 for (; NextIdx <
End; ++NextIdx)
1865 if (!SUnit2ClusterInfo.
count(MemOpRecords[NextIdx].SU->NodeNum) &&
1867 (!DAG->
IsReachable(MemOpRecords[NextIdx].SU, MemOpa.SU) &&
1868 !DAG->
IsReachable(MemOpa.SU, MemOpRecords[NextIdx].SU))))
1873 auto MemOpb = MemOpRecords[NextIdx];
1874 unsigned ClusterLength = 2;
1875 unsigned CurrentClusterBytes = MemOpa.Width.getValue().getKnownMinValue() +
1876 MemOpb.Width.getValue().getKnownMinValue();
1877 if (SUnit2ClusterInfo.
count(MemOpa.SU->NodeNum)) {
1878 ClusterLength = SUnit2ClusterInfo[MemOpa.SU->NodeNum].first + 1;
1879 CurrentClusterBytes = SUnit2ClusterInfo[MemOpa.SU->NodeNum].second +
1880 MemOpb.Width.getValue().getKnownMinValue();
1883 if (!
TII->shouldClusterMemOps(MemOpa.BaseOps, MemOpa.Offset,
1884 MemOpa.OffsetIsScalable, MemOpb.BaseOps,
1885 MemOpb.Offset, MemOpb.OffsetIsScalable,
1886 ClusterLength, CurrentClusterBytes))
1889 SUnit *SUa = MemOpa.SU;
1890 SUnit *SUb = MemOpb.SU;
1930 SUnit2ClusterInfo[MemOpb.SU->NodeNum] = {ClusterLength,
1931 CurrentClusterBytes};
1934 <<
", Curr cluster bytes: " << CurrentClusterBytes
1939void BaseMemOpClusterMutation::collectMemOpRecords(
1941 for (
auto &SU : SUnits) {
1949 bool OffsetIsScalable;
1952 OffsetIsScalable, Width,
TRI)) {
1954 MemOpInfo(&SU, BaseOps,
Offset, OffsetIsScalable, Width));
1957 <<
Offset <<
", OffsetIsScalable: " << OffsetIsScalable
1958 <<
", Width: " << Width <<
"\n");
1961 for (
const auto *
Op : BaseOps)
1967bool BaseMemOpClusterMutation::groupMemOps(
1974 for (
const auto &
MemOp : MemOps) {
1975 unsigned ChainPredID = DAG->
SUnits.size();
1977 for (
const SDep &Pred :
MemOp.SU->Preds) {
2001 collectMemOpRecords(DAG->
SUnits, MemOpRecords);
2003 if (MemOpRecords.
size() < 2)
2010 bool FastCluster = groupMemOps(MemOpRecords, DAG,
Groups);
2012 for (
auto &Group :
Groups) {
2018 clusterNeighboringMemOps(Group.second, FastCluster, DAG);
2052std::unique_ptr<ScheduleDAGMutation>
2055 return std::make_unique<CopyConstrain>(
TII,
TRI);
2100 unsigned LocalReg = SrcReg;
2101 unsigned GlobalReg = DstReg;
2103 if (!LocalLI->
isLocal(RegionBeginIdx, RegionEndIdx)) {
2107 if (!LocalLI->
isLocal(RegionBeginIdx, RegionEndIdx))
2118 if (GlobalSegment == GlobalLI->
end())
2125 if (GlobalSegment->contains(LocalLI->
beginIndex()))
2128 if (GlobalSegment == GlobalLI->
end())
2132 if (GlobalSegment != GlobalLI->
begin()) {
2135 GlobalSegment->start)) {
2146 assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&
2147 "Disconnected LRG within the scheduling region.");
2163 for (
const SDep &Succ : LastLocalSU->
Succs) {
2178 for (
const SDep &Pred : GlobalSU->
Preds) {
2181 if (Pred.
getSUnit() == FirstLocalSU)
2189 for (
SUnit *LU : LocalUses) {
2190 LLVM_DEBUG(
dbgs() <<
" Local use SU(" << LU->NodeNum <<
") -> SU("
2191 << GlobalSU->
NodeNum <<
")\n");
2194 for (
SUnit *GU : GlobalUses) {
2195 LLVM_DEBUG(
dbgs() <<
" Global use SU(" << GU->NodeNum <<
") -> SU("
2196 << FirstLocalSU->
NodeNum <<
")\n");
2208 if (FirstPos == DAG->
end())
2236 unsigned Latency,
bool AfterSchedNode) {
2237 int ResCntFactor = (int)(Count - (
Latency * LFactor));
2239 return ResCntFactor >= (int)LFactor;
2241 return ResCntFactor > (int)LFactor;
2254 CheckPending =
false;
2257 MinReadyCycle = std::numeric_limits<unsigned>::max();
2258 ExpectedLatency = 0;
2259 DependentLatency = 0;
2261 MaxExecutedResCount = 0;
2263 IsResourceLimited =
false;
2264 ReservedCycles.clear();
2265 ReservedResourceSegments.clear();
2266 ReservedCyclesIndex.
clear();
2267 ResourceGroupSubUnitMasks.clear();
2268#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2272 MaxObservedStall = 0;
2275 ExecutedResCounts.
resize(1);
2276 assert(!ExecutedResCounts[0] &&
"nonzero count for bad resource");
2292 unsigned PIdx = PI->ProcResourceIdx;
2294 assert(PI->ReleaseAtCycle >= PI->AcquireAtCycle);
2296 (Factor * (PI->ReleaseAtCycle - PI->AcquireAtCycle));
2309 ReservedCyclesIndex.
resize(ResourceCount);
2310 ExecutedResCounts.
resize(ResourceCount);
2311 ResourceGroupSubUnitMasks.resize(ResourceCount,
APInt(ResourceCount, 0));
2312 unsigned NumUnits = 0;
2314 for (
unsigned i = 0; i < ResourceCount; ++i) {
2315 ReservedCyclesIndex[i] = NumUnits;
2321 ResourceGroupSubUnitMasks[i].setBit(SubUnits[U]);
2341 if (ReadyCycle > CurrCycle)
2342 return ReadyCycle - CurrCycle;
2349 unsigned ReleaseAtCycle,
2350 unsigned AcquireAtCycle) {
2353 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromTop(
2354 CurrCycle, AcquireAtCycle, ReleaseAtCycle);
2356 return ReservedResourceSegments[InstanceIdx].getFirstAvailableAtFromBottom(
2357 CurrCycle, AcquireAtCycle, ReleaseAtCycle);
2360 unsigned NextUnreserved = ReservedCycles[InstanceIdx];
2366 NextUnreserved = std::max(CurrCycle, NextUnreserved + ReleaseAtCycle);
2367 return NextUnreserved;
2373std::pair<unsigned, unsigned>
2375 unsigned ReleaseAtCycle,
2376 unsigned AcquireAtCycle) {
2378 LLVM_DEBUG(
dbgs() <<
" Resource booking (@" << CurrCycle <<
"c): \n");
2380 LLVM_DEBUG(
dbgs() <<
" getNextResourceCycle (@" << CurrCycle <<
"c): \n");
2383 unsigned InstanceIdx = 0;
2384 unsigned StartIndex = ReservedCyclesIndex[PIdx];
2386 assert(NumberOfInstances > 0 &&
2387 "Cannot have zero instances of a ProcResource");
2404 if (ResourceGroupSubUnitMasks[PIdx][PE.ProcResourceIdx])
2406 StartIndex, ReleaseAtCycle, AcquireAtCycle),
2410 for (
unsigned I = 0,
End = NumberOfInstances;
I <
End; ++
I) {
2411 unsigned NextUnreserved, NextInstanceIdx;
2412 std::tie(NextUnreserved, NextInstanceIdx) =
2414 if (MinNextUnreserved > NextUnreserved) {
2415 InstanceIdx = NextInstanceIdx;
2416 MinNextUnreserved = NextUnreserved;
2419 return std::make_pair(MinNextUnreserved, InstanceIdx);
2422 for (
unsigned I = StartIndex,
End = StartIndex + NumberOfInstances;
I <
End;
2424 unsigned NextUnreserved =
2428 << NextUnreserved <<
"c\n");
2429 if (MinNextUnreserved > NextUnreserved) {
2431 MinNextUnreserved = NextUnreserved;
2436 <<
"[" << InstanceIdx - StartIndex <<
"]"
2437 <<
" available @" << MinNextUnreserved <<
"c"
2439 return std::make_pair(MinNextUnreserved, InstanceIdx);
2472 << (
isTop() ?
"begin" :
"end") <<
" group\n");
2481 unsigned ResIdx = PE.ProcResourceIdx;
2482 unsigned ReleaseAtCycle = PE.ReleaseAtCycle;
2483 unsigned AcquireAtCycle = PE.AcquireAtCycle;
2484 unsigned NRCycle, InstanceIdx;
2485 std::tie(NRCycle, InstanceIdx) =
2487 if (NRCycle > CurrCycle) {
2488#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2489 MaxObservedStall = std::max(ReleaseAtCycle, MaxObservedStall);
2493 <<
'[' << InstanceIdx - ReservedCyclesIndex[ResIdx] <<
']'
2494 <<
"=" << NRCycle <<
"c\n");
2505 SUnit *LateSU =
nullptr;
2506 unsigned RemLatency = 0;
2507 for (
SUnit *SU : ReadySUs) {
2509 if (L > RemLatency) {
2516 << LateSU->
NodeNum <<
") " << RemLatency <<
"c\n");
2535 PIdx != PEnd; ++PIdx) {
2537 if (OtherCount > OtherCritCount) {
2538 OtherCritCount = OtherCount;
2539 OtherCritIdx = PIdx;
2548 return OtherCritCount;
2555#if LLVM_ENABLE_ABI_BREAKING_CHECKS
2559 if (ReadyCycle > CurrCycle)
2560 MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);
2563 if (ReadyCycle < MinReadyCycle)
2564 MinReadyCycle = ReadyCycle;
2569 bool HazardDetected = (!IsBuffered && ReadyCycle > CurrCycle) ||
2572 if (!HazardDetected) {
2587 assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
2588 "MinReadyCycle uninitialized");
2589 if (MinReadyCycle > NextCycle)
2590 NextCycle = MinReadyCycle;
2594 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
2597 if ((NextCycle - CurrCycle) > DependentLatency)
2598 DependentLatency = 0;
2600 DependentLatency -= (NextCycle - CurrCycle);
2604 CurrCycle = NextCycle;
2607 for (; CurrCycle != NextCycle; ++CurrCycle) {
2614 CheckPending =
true;
2624 ExecutedResCounts[PIdx] += Count;
2625 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
2626 MaxExecutedResCount = ExecutedResCounts[PIdx];
2640 unsigned ReleaseAtCycle,
2642 unsigned AcquireAtCycle) {
2644 unsigned Count = Factor * (ReleaseAtCycle- AcquireAtCycle);
2646 << ReleaseAtCycle <<
"x" << Factor <<
"u\n");
2656 ZoneCritResIdx = PIdx;
2663 unsigned NextAvailable, InstanceIdx;
2664 std::tie(NextAvailable, InstanceIdx) =
2666 if (NextAvailable > CurrCycle) {
2669 <<
'[' << InstanceIdx - ReservedCyclesIndex[PIdx] <<
']'
2670 <<
" reserved until @" << NextAvailable <<
"\n");
2672 return NextAvailable;
2686 CheckPending =
true;
2694 "Cannot schedule this instruction's MicroOps in the current cycle.");
2699 unsigned NextCycle = CurrCycle;
2702 assert(ReadyCycle <= CurrCycle &&
"Broken PendingQueue");
2705 if (ReadyCycle > NextCycle) {
2706 NextCycle = ReadyCycle;
2707 LLVM_DEBUG(
dbgs() <<
" *** Stall until: " << ReadyCycle <<
"\n");
2716 NextCycle = ReadyCycle;
2719 RetiredMOps += IncMOps;
2726 if (ZoneCritResIdx) {
2728 unsigned ScaledMOps =
2745 countResource(SC, PI->ProcResourceIdx, PI->ReleaseAtCycle, NextCycle,
2746 PI->AcquireAtCycle);
2747 if (RCycle > NextCycle)
2758 unsigned PIdx = PI->ProcResourceIdx;
2762 unsigned ReservedUntil, InstanceIdx;
2764 SC, PIdx, PI->ReleaseAtCycle, PI->AcquireAtCycle);
2766 ReservedResourceSegments[InstanceIdx].add(
2768 NextCycle, PI->AcquireAtCycle, PI->ReleaseAtCycle),
2771 ReservedResourceSegments[InstanceIdx].add(
2773 NextCycle, PI->AcquireAtCycle, PI->ReleaseAtCycle),
2778 unsigned ReservedUntil, InstanceIdx;
2780 SC, PIdx, PI->ReleaseAtCycle, PI->AcquireAtCycle);
2782 ReservedCycles[InstanceIdx] =
2783 std::max(ReservedUntil, NextCycle + PI->ReleaseAtCycle);
2785 ReservedCycles[InstanceIdx] = NextCycle;
2792 unsigned &TopLatency =
isTop() ? ExpectedLatency : DependentLatency;
2793 unsigned &BotLatency =
isTop() ? DependentLatency : ExpectedLatency;
2797 << SU->
NodeNum <<
") " << TopLatency <<
"c\n");
2802 << SU->
NodeNum <<
") " << BotLatency <<
"c\n");
2805 if (NextCycle > CurrCycle)
2818 CurrMOps += IncMOps;
2832 LLVM_DEBUG(
dbgs() <<
" *** Max MOps " << CurrMOps <<
" at cycle "
2833 << CurrCycle <<
'\n');
2844 MinReadyCycle = std::numeric_limits<unsigned>::max();
2852 if (ReadyCycle < MinReadyCycle)
2853 MinReadyCycle = ReadyCycle;
2864 CheckPending =
false;
2910#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2920 unsigned StartIdx = 0;
2922 for (
unsigned ResIdx = 0; ResIdx < ResourceCount; ++ResIdx) {
2925 for (
unsigned UnitIdx = 0; UnitIdx < NumUnits; ++UnitIdx) {
2926 dbgs() << ResName <<
"(" << UnitIdx <<
") = ";
2928 if (ReservedResourceSegments.count(StartIdx + UnitIdx))
2929 dbgs() << ReservedResourceSegments.at(StartIdx + UnitIdx);
2933 dbgs() << ReservedCycles[StartIdx + UnitIdx] <<
"\n";
2935 StartIdx += NumUnits;
2944 if (ZoneCritResIdx) {
2949 ResCount = RetiredMOps * ResFactor;
2953 <<
" Retired: " << RetiredMOps;
2955 dbgs() <<
"\n Critical: " << ResCount / LFactor <<
"c, "
2956 << ResCount / ResFactor <<
" "
2958 <<
"\n ExpectedLatency: " << ExpectedLatency <<
"c\n"
2959 << (IsResourceLimited ?
" - Resource" :
" - Latency")
3005 RemLatency = std::max(RemLatency,
3007 RemLatency = std::max(RemLatency,
3014bool GenericSchedulerBase::shouldReduceLatency(
const CandPolicy &Policy,
3016 bool ComputeRemLatency,
3017 unsigned &RemLatency)
const {
3027 if (ComputeRemLatency)
3043 unsigned OtherCritIdx = 0;
3044 unsigned OtherCount =
3047 bool OtherResLimited =
false;
3048 unsigned RemLatency = 0;
3049 bool RemLatencyComputed =
false;
3052 RemLatencyComputed =
true;
3054 OtherCount, RemLatency,
false);
3060 if (!OtherResLimited &&
3061 (IsPostRA || shouldReduceLatency(Policy, CurrZone, !RemLatencyComputed,
3065 <<
" RemainingLatency " << RemLatency <<
" + "
3074 dbgs() <<
" " << CurrZone.Available.getName() <<
" ResourceLimited: "
3075 << SchedModel->getResourceName(CurrZone.getZoneCritResIdx()) <<
"\n";
3076 }
if (OtherResLimited)
dbgs()
3077 <<
" RemainingLimit: "
3080 <<
" Latency limited both directions.\n");
3085 if (OtherResLimited)
3093 case NoCand:
return "NOCAND ";
3094 case Only1:
return "ONLY1 ";
3095 case PhysReg:
return "PHYS-REG ";
3098 case Stall:
return "STALL ";
3099 case Cluster:
return "CLUSTER ";
3100 case Weak:
return "WEAK ";
3101 case RegMax:
return "REG-MAX ";
3116 unsigned ResIdx = 0;
3152 <<
":" <<
P.getUnitInc() <<
" ";
3175 if (TryVal < CandVal) {
3179 if (TryVal > CandVal) {
3180 if (Cand.
Reason > Reason)
3191 if (TryVal > CandVal) {
3195 if (TryVal < CandVal) {
3196 if (Cand.
Reason > Reason)
3248 "(PreRA)GenericScheduler needs vreg liveness");
3253 if (RegionPolicy.ComputeDFSResult)
3254 DAG->computeDFSResult();
3265 if (!Top.HazardRec) {
3268 if (!Bot.HazardRec) {
3271 TopCand.SU =
nullptr;
3272 BotCand.SU =
nullptr;
3278 unsigned NumRegionInstrs) {
3286 RegionPolicy.ShouldTrackPressure =
true;
3287 for (
unsigned VT = MVT::i64; VT > (
unsigned)MVT::i1; --VT) {
3292 RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
3299 RegionPolicy.OnlyBottomUp =
true;
3306 RegionPolicy.ShouldTrackPressure =
false;
3307 RegionPolicy.ShouldTrackLaneMasks =
false;
3313 "-misched-topdown incompatible with -misched-bottomup");
3316 if (RegionPolicy.OnlyBottomUp)
3317 RegionPolicy.OnlyTopDown =
false;
3321 if (RegionPolicy.OnlyTopDown)
3322 RegionPolicy.OnlyBottomUp =
false;
3328#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3329 dbgs() <<
"GenericScheduler RegionPolicy: "
3330 <<
" ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure
3331 <<
" OnlyTopDown=" << RegionPolicy.OnlyTopDown
3332 <<
" OnlyBottomUp=" << RegionPolicy.OnlyBottomUp
3351 unsigned IterCount =
3357 unsigned InFlightCount =
3359 unsigned BufferLimit =
3365 dbgs() <<
"IssueCycles="
3368 <<
"c NumIters=" << (AcyclicCount + IterCount - 1) / IterCount
3378 for (
const SUnit *SU : Bot.Available) {
3389 checkAcyclicLatency();
3416 if (TryPSet == CandPSet) {
3421 int TryRank = TryP.
isValid() ?
TRI->getRegPressureSetScore(MF, TryPSet) :
3422 std::numeric_limits<int>::max();
3424 int CandRank = CandP.
isValid() ?
TRI->getRegPressureSetScore(MF, CandPSet) :
3425 std::numeric_limits<int>::max();
3430 return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);
3448 unsigned ScheduledOper = isTop ? 1 : 0;
3449 unsigned UnscheduledOper = isTop ? 0 : 1;
3452 if (
MI->getOperand(ScheduledOper).getReg().isPhysical())
3457 if (
MI->getOperand(UnscheduledOper).getReg().isPhysical())
3458 return AtBoundary ? -1 : 1;
3461 if (
MI->isMoveImmediate()) {
3467 if (
Op.isReg() && !
Op.getReg().isPhysical()) {
3474 return isTop ? -1 : 1;
3487 if (DAG->isTrackingPressure()) {
3492 DAG->getRegionCriticalPSets(),
3493 DAG->getRegPressure().MaxSetPressure);
3498 &DAG->getPressureDiff(Cand.
SU),
3500 DAG->getRegionCriticalPSets(),
3501 DAG->getRegPressure().MaxSetPressure);
3505 DAG->getPressureDiff(Cand.
SU),
3507 DAG->getRegionCriticalPSets(),
3508 DAG->getRegPressure().MaxSetPressure);
3513 <<
" Try SU(" << Cand.
SU->
NodeNum <<
") "
3562 bool SameBoundary = Zone !=
nullptr;
3583 const SUnit *CandNextClusterSU =
3585 const SUnit *TryCandNextClusterSU =
3588 Cand.
SU == CandNextClusterSU,
3596 TryCand, Cand,
Weak))
3648 for (
SUnit *SU : Q) {
3651 initCandidate(TryCand, SU, Zone.
isTop(), RPTracker, TempTracker);
3654 if (tryCandidate(Cand, TryCand, ZoneArg)) {
3668 if (
SUnit *SU = Bot.pickOnlyChoice()) {
3673 if (
SUnit *SU = Top.pickOnlyChoice()) {
3689 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
3690 BotCand.Policy != BotPolicy) {
3692 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);
3693 assert(BotCand.Reason !=
NoCand &&
"failed to find the first candidate");
3700 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);
3702 "Last pick result should correspond to re-picking right now");
3709 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
3710 TopCand.Policy != TopPolicy) {
3712 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);
3713 assert(TopCand.Reason !=
NoCand &&
"failed to find the first candidate");
3720 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);
3722 "Last pick result should correspond to re-picking right now");
3728 assert(BotCand.isValid());
3729 assert(TopCand.isValid());
3732 if (tryCandidate(Cand, TopCand,
nullptr)) {
3737 IsTopNode = Cand.
AtTop;
3745 assert(Top.Available.empty() && Top.Pending.empty() &&
3746 Bot.Available.empty() && Bot.Pending.empty() &&
"ReadyQ garbage");
3751 if (RegionPolicy.OnlyTopDown) {
3752 SU = Top.pickOnlyChoice();
3755 TopCand.reset(NoPolicy);
3756 pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);
3757 assert(TopCand.Reason !=
NoCand &&
"failed to find a candidate");
3762 }
else if (RegionPolicy.OnlyBottomUp) {
3763 SU = Bot.pickOnlyChoice();
3766 BotCand.reset(NoPolicy);
3767 pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);
3768 assert(BotCand.Reason !=
NoCand &&
"failed to find a candidate");
3774 SU = pickNodeBidirectional(IsTopNode);
3779 Top.removeReady(SU);
3781 Bot.removeReady(SU);
3796 for (
SDep &Dep : Deps) {
3800 SUnit *DepSU = Dep.getSUnit();
3801 if (isTop ? DepSU->
Succs.size() > 1 : DepSU->
Preds.size() > 1)
3804 if (!Copy->isCopy() && !Copy->isMoveImmediate())
3824 reschedulePhysReg(SU,
true);
3829 reschedulePhysReg(SU,
false);
3848 if (!MacroFusions.empty())
3877 if (!Top.HazardRec) {
3880 if (!Bot.HazardRec) {
3887 unsigned NumRegionInstrs) {
3889 RegionPolicy.OnlyTopDown =
true;
3890 RegionPolicy.OnlyBottomUp =
false;
3892 RegionPolicy.OnlyTopDown =
false;
3893 RegionPolicy.OnlyBottomUp =
true;
3895 RegionPolicy.OnlyBottomUp =
false;
3896 RegionPolicy.OnlyTopDown =
false;
3904 for (
const SUnit *SU : Bot.Available) {
3928 if (
tryLess(Top.getLatencyStallCycles(TryCand.
SU),
3929 Top.getLatencyStallCycles(Cand.
SU), TryCand, Cand,
Stall))
3964 for (
SUnit *SU : Q) {
3969 if (tryCandidate(Cand, TryCand)) {
3983 if (
SUnit *SU = Bot.pickOnlyChoice()) {
3988 if (
SUnit *SU = Top.pickOnlyChoice()) {
4004 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
4005 BotCand.Policy != BotPolicy) {
4007 pickNodeFromQueue(Bot, BotCand);
4008 assert(BotCand.Reason !=
NoCand &&
"failed to find the first candidate");
4015 pickNodeFromQueue(Bot, BotCand);
4017 "Last pick result should correspond to re-picking right now");
4024 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
4025 TopCand.Policy != TopPolicy) {
4027 pickNodeFromQueue(Top, TopCand);
4028 assert(TopCand.Reason !=
NoCand &&
"failed to find the first candidate");
4035 pickNodeFromQueue(Top, TopCand);
4037 "Last pick result should correspond to re-picking right now");
4043 assert(BotCand.isValid());
4044 assert(TopCand.isValid());
4047 if (tryCandidate(Cand, TopCand)) {
4052 IsTopNode = Cand.
AtTop;
4060 assert(Top.Available.empty() && Top.Pending.empty() &&
4061 Bot.Available.empty() && Bot.Pending.empty() &&
"ReadyQ garbage");
4066 if (RegionPolicy.OnlyBottomUp) {
4067 SU = Bot.pickOnlyChoice();
4072 BotCand.reset(NoPolicy);
4075 setPolicy(BotCand.Policy,
true, Bot,
nullptr);
4076 pickNodeFromQueue(Bot, BotCand);
4077 assert(BotCand.Reason !=
NoCand &&
"failed to find a candidate");
4082 }
else if (RegionPolicy.OnlyTopDown) {
4083 SU = Top.pickOnlyChoice();
4088 TopCand.reset(NoPolicy);
4091 setPolicy(TopCand.Policy,
true, Top,
nullptr);
4092 pickNodeFromQueue(Top, TopCand);
4093 assert(TopCand.Reason !=
NoCand &&
"failed to find a candidate");
4099 SU = pickNodeBidirectional(IsTopNode);
4104 Top.removeReady(SU);
4106 Bot.removeReady(SU);
4132 if (!MacroFusions.empty())
4146 const BitVector *ScheduledTrees =
nullptr;
4149 ILPOrder(
bool MaxILP) : MaximizeILP(MaxILP) {}
4154 bool operator()(
const SUnit *
A,
const SUnit *
B)
const {
4157 if (SchedTreeA != SchedTreeB) {
4159 if (ScheduledTrees->
test(SchedTreeA) != ScheduledTrees->
test(SchedTreeB))
4160 return ScheduledTrees->
test(SchedTreeB);
4181 std::vector<SUnit*> ReadyQ;
4184 ILPScheduler(
bool MaximizeILP) :
Cmp(MaximizeILP) {}
4195 void registerRoots()
override {
4197 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
4204 SUnit *pickNode(
bool &IsTopNode)
override {
4205 if (ReadyQ.empty())
return nullptr;
4206 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
4207 SUnit *SU = ReadyQ.back();
4211 <<
"SU(" << SU->
NodeNum <<
") "
4218 <<
"Scheduling " << *SU->
getInstr());
4223 void scheduleTree(
unsigned SubtreeID)
override {
4224 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
4229 void schedNode(
SUnit *SU,
bool IsTopNode)
override {
4230 assert(!IsTopNode &&
"SchedDFSResult needs bottom-up");
4233 void releaseTopNode(
SUnit *)
override { }
4235 void releaseBottomNode(
SUnit *SU)
override {
4236 ReadyQ.push_back(SU);
4237 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
4264template<
bool IsReverse>
4268 return A->NodeNum >
B->NodeNum;
4270 return A->NodeNum <
B->NodeNum;
4290 InstructionShuffler(
bool alternate,
bool topdown)
4291 : IsAlternating(alternate), IsTopDown(topdown) {}
4301 SUnit *pickNode(
bool &IsTopNode)
override {
4305 if (TopQ.empty())
return nullptr;
4312 if (BottomQ.empty())
return nullptr;
4319 IsTopDown = !IsTopDown;
4323 void schedNode(
SUnit *SU,
bool IsTopNode)
override {}
4325 void releaseTopNode(
SUnit *SU)
override {
4328 void releaseBottomNode(
SUnit *SU)
override {
4339 "-misched-topdown incompatible with -misched-bottomup");
4341 C, std::make_unique<InstructionShuffler>(Alternate, TopDown));
4345 "shuffle",
"Shuffle machine instructions alternating directions",
4364 return std::string(
G->MF.getName());
4384 return "color=cyan,style=dashed";
4386 return "color=blue,style=dashed";
4403 return G->getGraphNodeLabel(SU);
4407 std::string Str(
"shape=Mrecord");
4412 Str +=
",style=filled,fillcolor=\"#";
4429 errs() <<
"ScheduleDAGMI::viewGraph is only available in debug builds on "
4430 <<
"systems with Graphviz or gv!\n";
4436 viewGraph(getDAGName(),
"Scheduling-Units Graph for " + getDAGName());
4445 return A.first <
B.first;
4448unsigned ResourceSegments::getFirstAvailableAt(
4449 unsigned CurrCycle,
unsigned AcquireAtCycle,
unsigned ReleaseAtCycle,
4451 IntervalBuilder)
const {
4452 assert(std::is_sorted(std::begin(_Intervals), std::end(_Intervals),
4454 "Cannot execute on an un-sorted set of intervals.");
4458 if (AcquireAtCycle == ReleaseAtCycle)
4461 unsigned RetCycle = CurrCycle;
4463 IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);
4464 for (
auto &
Interval : _Intervals) {
4471 "Invalid intervals configuration.");
4473 NewInterval = IntervalBuilder(RetCycle, AcquireAtCycle, ReleaseAtCycle);
4479 const unsigned CutOff) {
4480 assert(
A.first <=
A.second &&
"Cannot add negative resource usage");
4481 assert(CutOff > 0 &&
"0-size interval history has no use.");
4487 if (
A.first ==
A.second)
4494 "A resource is being overwritten");
4495 _Intervals.push_back(
A);
4501 while (_Intervals.size() > CutOff)
4502 _Intervals.pop_front();
4507 assert(
A.first <=
A.second &&
"Invalid interval");
4508 assert(
B.first <=
B.second &&
"Invalid interval");
4511 if ((
A.first ==
B.first) || (
A.second ==
B.second))
4516 if ((
A.first >
B.first) && (
A.second <
B.second))
4521 if ((
A.first >
B.first) && (
A.first <
B.second) && (
A.second >
B.second))
4526 if ((
A.first <
B.first) && (
B.first <
A.second) && (
B.second >
B.first))
4532void ResourceSegments::sortAndMerge() {
4533 if (_Intervals.size() <= 1)
4540 auto next = std::next(std::begin(_Intervals));
4541 auto E = std::end(_Intervals);
4542 for (; next !=
E; ++next) {
4543 if (std::prev(next)->second >= next->first) {
4544 next->first = std::prev(next)->first;
4545 _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
std::pair< uint64_t, uint64_t > Interval
#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.
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.
SUnit * pickNodeBidirectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
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)
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< 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"), clEnumValN(MISchedPostRASched::Bidirectional, "bidirectional", "Force bidirectional post reg-alloc list scheduling")))
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.