50 #include "llvm/Config/llvm-config.h" 73 #define DEBUG_TYPE "machine-scheduler" 78 cl::desc(
"Force top-down list scheduling"));
80 cl::desc(
"Force bottom-up list scheduling"));
83 cl::desc(
"Print critical path length to stdout"));
89 cl::desc(
"Pop up a window to show MISched dags after they are processed"));
94 cl::desc(
"Hide nodes with more predecessor/successor than cutoff"));
100 cl::desc(
"Only schedule this function"));
102 cl::desc(
"Only schedule this MBB#"));
106 static const bool ViewMISchedDAGs =
false;
107 static const bool PrintDAGs =
false;
122 cl::desc(
"Enable memop clustering."),
126 cl::desc(
"Verify machine instrs before and after machine scheduling"));
132 void MachineSchedStrategy::anchor() {}
134 void ScheduleDAGMutation::anchor() {}
163 class MachineScheduler :
public MachineSchedulerBase {
178 class PostMachineScheduler :
public MachineSchedulerBase {
180 PostMachineScheduler();
199 "Machine Instruction Scheduler",
false,
false)
207 MachineScheduler::MachineScheduler() : MachineSchedulerBase(
ID) {
211 void MachineScheduler::getAnalysisUsage(
AnalysisUsage &AU)
const {
229 "PostRA Machine Instruction Scheduler",
false,
false)
231 PostMachineScheduler::PostMachineScheduler() : MachineSchedulerBase(
ID) {
235 void PostMachineScheduler::getAnalysisUsage(
AnalysisUsage &AU)
const {
257 cl::desc(
"Machine instruction scheduler to use"));
265 cl::desc(
"Enable the machine instruction scheduling pass."),
cl::init(
true),
269 "enable-post-misched",
270 cl::desc(
"Enable the post-ra machine instruction scheduling pass."),
277 assert(I != Beg &&
"reached the top of the region, cannot decrement");
279 if (!I->isDebugInstr())
298 for(; I != End; ++
I) {
299 if (!I->isDebugInstr())
363 if (!EnableMachineSched)
372 MLI = &getAnalysis<MachineLoopInfo>();
373 MDT = &getAnalysis<MachineDominatorTree>();
374 PassConfig = &getAnalysis<TargetPassConfig>();
375 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
377 LIS = &getAnalysis<LiveIntervals>();
379 if (VerifyScheduling) {
381 MF->verify(
this,
"Before machine scheduling.");
383 RegClassInfo->runOnMachineFunction(*MF);
387 std::unique_ptr<ScheduleDAGInstrs>
Scheduler(createMachineScheduler());
388 scheduleRegions(*Scheduler,
false);
391 if (VerifyScheduling)
392 MF->verify(
this,
"After machine scheduling.");
401 if (!EnablePostRAMachineSched)
411 MLI = &getAnalysis<MachineLoopInfo>();
412 PassConfig = &getAnalysis<TargetPassConfig>();
414 if (VerifyScheduling)
415 MF->
verify(
this,
"Before post machine scheduling.");
419 std::unique_ptr<ScheduleDAGInstrs>
Scheduler(createPostMachineScheduler());
420 scheduleRegions(*Scheduler,
true);
422 if (VerifyScheduling)
423 MF->verify(
this,
"After post machine scheduling.");
454 unsigned NumRegionInstrs;
458 RegionBegin(B), RegionEnd(E), NumRegionInstrs(N) {}
467 bool RegionsTopDown) {
473 RegionEnd != MBB->
begin(); RegionEnd =
I) {
476 if (RegionEnd != MBB->
end() ||
483 unsigned NumRegionInstrs = 0;
485 for (;I != MBB->
begin(); --
I) {
495 Regions.
push_back(SchedRegion(I, RegionEnd, NumRegionInstrs));
510 MBB != MBBEnd; ++MBB) {
518 && (int)SchedOnlyBlock != MBB->getNumber())
539 R != MBBRegions.
end(); ++R) {
542 unsigned NumRegionInstrs = R->NumRegionInstrs;
546 Scheduler.
enterRegion(&*MBB, I, RegionEnd, NumRegionInstrs);
549 if (I == RegionEnd || I == std::prev(RegionEnd)) {
557 <<
" " << MBB->getName() <<
"\n From: " << *I
559 if (RegionEnd != MBB->end())
dbgs() << *RegionEnd;
560 else dbgs() <<
"End";
561 dbgs() <<
" RegionInstrs: " << NumRegionInstrs <<
'\n');
563 errs() << MF->getName();
564 errs() <<
":%bb. " << MBB->getNumber();
565 errs() <<
" " << MBB->getName() <<
" \n";
589 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 592 for (
const SUnit *SU : Queue)
593 dbgs() << SU->NodeNum <<
" ";
608 return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
612 if (SuccSU != &ExitSU) {
615 if (Topo.IsReachable(PredDep.
getSUnit(), SuccSU))
617 Topo.AddPred(SuccSU, PredDep.
getSUnit());
634 NextClusterSucc = SuccSU;
639 dbgs() <<
"*** Scheduling failed! ***\n";
641 dbgs() <<
" has been released too many times!\n";
652 SchedImpl->releaseTopNode(SuccSU);
658 releaseSucc(SU, &Succ);
671 NextClusterPred = PredSU;
676 dbgs() <<
"*** Scheduling failed! ***\n";
678 dbgs() <<
" has been released too many times!\n";
689 SchedImpl->releaseBottomNode(PredSU);
695 releasePred(SU, &Pred);
700 SchedImpl->enterMBB(bb);
704 SchedImpl->leaveMBB();
715 unsigned regioninstrs)
719 SchedImpl->initPolicy(begin, end, regioninstrs);
727 if (&*RegionBegin == MI)
731 BB->splice(InsertPos, BB, MI);
735 LIS->handleMove(*MI,
true);
738 if (RegionBegin == InsertPos)
744 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
745 CurrentTop = CurrentBottom;
748 ++NumInstrsScheduled;
764 Topo.InitDAGTopologicalSorting();
769 findRootsAndBiasEdges(TopRoots, BotRoots);
772 if (PrintDAGs)
dump();
773 if (ViewMISchedDAGs) viewGraph();
777 SchedImpl->initialize(
this);
780 initQueues(TopRoots, BotRoots);
782 bool IsTopNode =
false;
784 LLVM_DEBUG(
dbgs() <<
"** ScheduleDAGMI::schedule picking next node\n");
785 SUnit *SU = SchedImpl->pickNode(IsTopNode);
789 if (!checkSchedLimit())
795 if (&*CurrentTop == MI)
796 CurrentTop =
nextIfDebug(++CurrentTop, CurrentBottom);
798 moveInstruction(MI, CurrentTop);
804 CurrentBottom = priorII;
806 if (&*CurrentTop == MI)
808 moveInstruction(MI, CurrentBottom);
816 SchedImpl->schedNode(SU, IsTopNode);
818 updateQueues(SU, IsTopNode);
820 assert(CurrentTop == CurrentBottom &&
"Nonempty unscheduled zone.");
825 dbgs() <<
"*** Final schedule for " 834 for (
auto &m : Mutations)
841 for (
SUnit &SU : SUnits) {
842 assert(!SU.isBoundaryNode() &&
"Boundary node should not be in SUnits");
845 SU.biasCriticalPath();
848 if (!SU.NumPredsLeft)
851 if (!SU.NumSuccsLeft)
854 ExitSU.biasCriticalPath();
860 NextClusterSucc =
nullptr;
861 NextClusterPred =
nullptr;
867 for (
SUnit *SU : TopRoots)
868 SchedImpl->releaseTopNode(SU);
874 SchedImpl->releaseBottomNode(*
I);
877 releaseSuccessors(&EntrySU);
878 releasePredecessors(&ExitSU);
880 SchedImpl->registerRoots();
884 CurrentBottom = RegionEnd;
891 releaseSuccessors(SU);
893 releasePredecessors(SU);
902 BB->splice(RegionBegin, BB, FirstDbgValue);
903 RegionBegin = FirstDbgValue;
906 for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator
907 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
908 std::pair<MachineInstr *, MachineInstr *>
P = *std::prev(DI);
911 if (&*RegionBegin == DbgValue)
913 BB->splice(++OrigPrevMI, BB, DbgValue);
914 if (OrigPrevMI == std::prev(RegionEnd))
915 RegionEnd = DbgValue;
918 FirstDbgValue =
nullptr;
921 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 924 if (
SUnit *SU = getSUnit(&(*
MI)))
927 dbgs() <<
"Missing SUnit\n";
948 if (TrackLaneMasks && !MO.isUse())
951 unsigned Reg = MO.getReg();
956 if (TrackLaneMasks) {
957 bool FoundDef =
false;
959 if (MO2.isReg() && MO2.isDef() && MO2.getReg() == Reg && !MO2.isDead()) {
970 for (; UI != VRegUses.end(); ++UI) {
974 if (UI == VRegUses.end())
986 unsigned regioninstrs)
992 LiveRegionEnd = (RegionEnd == bb->
end()) ? RegionEnd : std::next(RegionEnd);
994 SUPressureDiffs.clear();
996 ShouldTrackPressure = SchedImpl->shouldTrackPressure();
997 ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks();
999 assert((!ShouldTrackLaneMasks || ShouldTrackPressure) &&
1000 "ShouldTrackLaneMasks requires ShouldTrackPressure");
1007 VRegUses.setUniverse(
MRI.getNumVirtRegs());
1008 for (
SUnit &SU : SUnits)
1009 collectVRegUses(SU);
1011 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin,
1012 ShouldTrackLaneMasks,
false);
1013 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
1014 ShouldTrackLaneMasks,
false);
1017 RPTracker.closeRegion();
1022 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
1023 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
1028 TopRPTracker.closeTop();
1029 BotRPTracker.closeBottom();
1031 BotRPTracker.initLiveThru(RPTracker);
1032 if (!BotRPTracker.getLiveThru().empty()) {
1033 TopRPTracker.initLiveThru(BotRPTracker.getLiveThru());
1040 updatePressureDiffs(RPTracker.getPressure().LiveOutRegs);
1043 if (LiveRegionEnd != RegionEnd) {
1045 BotRPTracker.recede(&LiveUses);
1046 updatePressureDiffs(LiveUses);
1051 dbgs() <<
"Bottom Pressure:\n";
1054 assert((BotRPTracker.getPos() == RegionEnd ||
1055 (RegionEnd->isDebugInstr() &&
1056 BotRPTracker.getPos() ==
priorNonDebug(RegionEnd, RegionBegin))) &&
1057 "Can't find the region bottom");
1061 RegionCriticalPSets.clear();
1064 for (
unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
1065 unsigned Limit = RegClassInfo->getRegPressureSetLimit(i);
1066 if (RegionPressure[i] > Limit) {
1068 <<
" Actual " << RegionPressure[i] <<
"\n");
1074 : RegionCriticalPSets)
dbgs()
1075 <<
TRI->getRegPressureSetName(RCPS.getPSet()) <<
" ";
1081 const std::vector<unsigned> &NewMaxPressure) {
1083 unsigned CritIdx = 0, CritEnd = RegionCriticalPSets.size();
1087 unsigned ID = PC.getPSet();
1088 while (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() < ID)
1090 if (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() == ID) {
1091 if ((
int)NewMaxPressure[ID] > RegionCriticalPSets[CritIdx].getUnitInc()
1093 RegionCriticalPSets[CritIdx].setUnitInc(NewMaxPressure[ID]);
1095 unsigned Limit = RegClassInfo->getRegPressureSetLimit(ID);
1096 if (NewMaxPressure[ID] >= Limit - 2) {
1098 << NewMaxPressure[
ID]
1099 << ((NewMaxPressure[
ID] > Limit) ?
" > " :
" <= ")
1100 << Limit <<
"(+ " << BotRPTracker.getLiveThru()[
ID]
1111 unsigned Reg =
P.RegUnit;
1113 if (!
TRI->isVirtualRegister(Reg))
1116 if (ShouldTrackLaneMasks) {
1121 bool Decrement =
P.LaneMask.any();
1124 :
make_range(VRegUses.find(Reg), VRegUses.end())) {
1125 SUnit &SU = *V2SU.SU;
1154 assert(VNI &&
"No live value at use.");
1156 :
make_range(VRegUses.find(Reg), VRegUses.end())) {
1157 SUnit *SU = V2SU.SU;
1177 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1178 if (EntrySU.getInstr() !=
nullptr)
1179 dumpNodeAll(EntrySU);
1180 for (
const SUnit &SU : SUnits) {
1182 if (ShouldTrackPressure) {
1183 dbgs() <<
" Pressure Diff : ";
1184 getPressureDiff(&SU).dump(*
TRI);
1186 dbgs() <<
" Single Issue : ";
1187 if (SchedModel.mustBeginGroup(SU.getInstr()) &&
1188 SchedModel.mustEndGroup(SU.getInstr()))
1194 if (ExitSU.getInstr() !=
nullptr)
1195 dumpNodeAll(ExitSU);
1212 buildDAGWithRegPressure();
1214 Topo.InitDAGTopologicalSorting();
1219 findRootsAndBiasEdges(TopRoots, BotRoots);
1223 SchedImpl->initialize(
this);
1226 if (PrintDAGs)
dump();
1227 if (ViewMISchedDAGs) viewGraph();
1230 initQueues(TopRoots, BotRoots);
1232 bool IsTopNode =
false;
1234 LLVM_DEBUG(
dbgs() <<
"** ScheduleDAGMILive::schedule picking next node\n");
1235 SUnit *SU = SchedImpl->pickNode(IsTopNode);
1239 if (!checkSchedLimit())
1242 scheduleMI(SU, IsTopNode);
1245 unsigned SubtreeID = DFSResult->getSubtreeID(SU);
1246 if (!ScheduledTrees.test(SubtreeID)) {
1247 ScheduledTrees.set(SubtreeID);
1248 DFSResult->scheduleTree(SubtreeID);
1249 SchedImpl->scheduleTree(SubtreeID);
1254 SchedImpl->schedNode(SU, IsTopNode);
1256 updateQueues(SU, IsTopNode);
1258 assert(CurrentTop == CurrentBottom &&
"Nonempty unscheduled zone.");
1263 dbgs() <<
"*** Final schedule for " 1272 if (!ShouldTrackPressure) {
1274 RegionCriticalPSets.clear();
1275 buildSchedGraph(AA);
1280 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
1281 ShouldTrackLaneMasks,
true);
1284 if (LiveRegionEnd != RegionEnd)
1288 buildSchedGraph(AA, &RPTracker, &SUPressureDiffs, LIS, ShouldTrackLaneMasks);
1298 ScheduledTrees.clear();
1299 DFSResult->resize(SUnits.size());
1300 DFSResult->compute(SUnits);
1301 ScheduledTrees.resize(DFSResult->getNumSubtrees());
1332 if (!BB->isSuccessor(BB))
1335 unsigned MaxCyclicLatency = 0;
1338 unsigned Reg =
P.RegUnit;
1339 if (!
TRI->isVirtualRegister(Reg))
1347 const SUnit *DefSU = getSUnit(DefMI);
1351 unsigned LiveOutHeight = DefSU->
getHeight();
1355 :
make_range(VRegUses.find(Reg), VRegUses.end())) {
1356 SUnit *SU = V2SU.SU;
1368 unsigned CyclicLatency = 0;
1370 CyclicLatency = LiveOutDepth - SU->
getDepth();
1373 if (LiveInHeight > LiveOutHeight) {
1374 if (LiveInHeight - LiveOutHeight < CyclicLatency)
1375 CyclicLatency = LiveInHeight - LiveOutHeight;
1380 << SU->
NodeNum <<
") = " << CyclicLatency <<
"c\n");
1381 if (CyclicLatency > MaxCyclicLatency)
1382 MaxCyclicLatency = CyclicLatency;
1385 LLVM_DEBUG(
dbgs() <<
"Cyclic Critical Path: " << MaxCyclicLatency <<
"c\n");
1386 return MaxCyclicLatency;
1394 if (ShouldTrackPressure) {
1395 assert(TopRPTracker.getPos() == RegionBegin &&
"bad initial Top tracker");
1396 TopRPTracker.setPos(CurrentTop);
1407 if (&*CurrentTop == MI)
1408 CurrentTop =
nextIfDebug(++CurrentTop, CurrentBottom);
1410 moveInstruction(MI, CurrentTop);
1411 TopRPTracker.setPos(MI);
1414 if (ShouldTrackPressure) {
1417 RegOpers.
collect(*MI, *
TRI,
MRI, ShouldTrackLaneMasks,
false);
1418 if (ShouldTrackLaneMasks) {
1427 TopRPTracker.advance(RegOpers);
1428 assert(TopRPTracker.getPos() == CurrentTop &&
"out of sync");
1430 TopRPTracker.getRegSetPressureAtPos(),
TRI););
1432 updateScheduledPressure(SU, TopRPTracker.getPressure().MaxSetPressure);
1438 if (&*priorII == MI)
1439 CurrentBottom = priorII;
1441 if (&*CurrentTop == MI) {
1443 TopRPTracker.setPos(CurrentTop);
1445 moveInstruction(MI, CurrentBottom);
1447 BotRPTracker.setPos(CurrentBottom);
1449 if (ShouldTrackPressure) {
1451 RegOpers.
collect(*MI, *
TRI,
MRI, ShouldTrackLaneMasks,
false);
1452 if (ShouldTrackLaneMasks) {
1461 if (BotRPTracker.getPos() != CurrentBottom)
1462 BotRPTracker.recedeSkipDebugValues();
1464 BotRPTracker.recede(RegOpers, &LiveUses);
1465 assert(BotRPTracker.getPos() == CurrentBottom &&
"out of sync");
1467 BotRPTracker.getRegSetPressureAtPos(),
TRI););
1469 updateScheduledPressure(SU, BotRPTracker.getPressure().MaxSetPressure);
1470 updatePressureDiffs(LiveUses);
1490 : SU(su), BaseOp(Op),
Offset(ofs) {}
1492 bool operator<(
const MemOpInfo &RHS)
const {
1493 if (BaseOp->
getType() != RHS.BaseOp->getType())
1494 return BaseOp->
getType() < RHS.BaseOp->getType();
1496 if (BaseOp->
isReg())
1498 std::make_tuple(RHS.BaseOp->getReg(), RHS.Offset,
1500 if (BaseOp->
isFI()) {
1508 if (BaseOp->
getIndex() != RHS.BaseOp->getIndex())
1509 return StackGrowsDown ? BaseOp->
getIndex() > RHS.BaseOp->getIndex()
1510 : BaseOp->
getIndex() < RHS.BaseOp->getIndex();
1512 if (Offset != RHS.Offset)
1513 return StackGrowsDown ? Offset > RHS.Offset : Offset < RHS.Offset;
1515 return SU->
NodeNum < RHS.SU->NodeNum;
1530 :
TII(tii),
TRI(tri), IsLoad(IsLoad) {}
1538 class StoreClusterMutation :
public BaseMemOpClusterMutation {
1542 : BaseMemOpClusterMutation(tii, tri,
false) {}
1545 class LoadClusterMutation :
public BaseMemOpClusterMutation {
1548 : BaseMemOpClusterMutation(tii, tri,
true) {}
1555 std::unique_ptr<ScheduleDAGMutation>
1558 return EnableMemOpCluster ? llvm::make_unique<LoadClusterMutation>(
TII,
TRI)
1562 std::unique_ptr<ScheduleDAGMutation>
1565 return EnableMemOpCluster ? llvm::make_unique<StoreClusterMutation>(
TII,
TRI)
1571 void BaseMemOpClusterMutation::clusterNeighboringMemOps(
1574 for (
SUnit *SU : MemOps) {
1578 MemOpRecords.
push_back(MemOpInfo(SU, BaseOp, Offset));
1580 if (MemOpRecords.
size() < 2)
1584 unsigned ClusterLength = 1;
1585 for (
unsigned Idx = 0, End = MemOpRecords.
size(); Idx < (End - 1); ++Idx) {
1586 SUnit *SUa = MemOpRecords[Idx].SU;
1587 SUnit *SUb = MemOpRecords[Idx+1].SU;
1588 if (
TII->shouldClusterMemOps(*MemOpRecords[Idx].BaseOp,
1589 *MemOpRecords[Idx + 1].BaseOp,
1624 unsigned ChainPredID = DAG->
SUnits.size();
1633 unsigned NumChains = StoreChainDependents.
size();
1634 std::pair<DenseMap<unsigned, unsigned>::iterator,
bool> Result =
1635 StoreChainIDs.
insert(std::make_pair(ChainPredID, NumChains));
1637 StoreChainDependents.
resize(NumChains + 1);
1638 StoreChainDependents[Result.first->second].
push_back(&SU);
1642 for (
auto &SCD : StoreChainDependents)
1643 clusterNeighboringMemOps(SCD, DAG);
1676 std::unique_ptr<ScheduleDAGMutation>
1679 return llvm::make_unique<CopyConstrain>(
TII,
TRI);
1709 unsigned SrcReg = SrcOp.
getReg();
1714 unsigned DstReg = DstOp.
getReg();
1724 unsigned LocalReg = SrcReg;
1725 unsigned GlobalReg = DstReg;
1727 if (!LocalLI->
isLocal(RegionBeginIdx, RegionEndIdx)) {
1731 if (!LocalLI->
isLocal(RegionBeginIdx, RegionEndIdx))
1742 if (GlobalSegment == GlobalLI->
end())
1749 if (GlobalSegment->contains(LocalLI->
beginIndex()))
1752 if (GlobalSegment == GlobalLI->
end())
1756 if (GlobalSegment != GlobalLI->
begin()) {
1759 GlobalSegment->start)) {
1770 assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&
1771 "Disconnected LRG within the scheduling region.");
1787 for (
const SDep &Succ : LastLocalSU->
Succs) {
1802 for (
const SDep &Pred : GlobalSU->
Preds) {
1805 if (Pred.
getSUnit() == FirstLocalSU)
1815 LLVM_DEBUG(
dbgs() <<
" Local use SU(" << (*I)->NodeNum <<
") -> SU(" 1816 << GlobalSU->
NodeNum <<
")\n");
1820 I = GlobalUses.
begin(),
E = GlobalUses.
end();
I !=
E; ++
I) {
1821 LLVM_DEBUG(
dbgs() <<
" Global use SU(" << (*I)->NodeNum <<
") -> SU(" 1822 << FirstLocalSU->
NodeNum <<
")\n");
1834 if (FirstPos == DAG->
end())
1844 constrainLocalCopy(&SU, static_cast<ScheduleDAGMILive*>(DAG));
1861 return (
int)(Count - (Latency * LFactor)) > (int)LFactor;
1868 if (HazardRec && HazardRec->isEnabled()) {
1870 HazardRec =
nullptr;
1874 CheckPending =
false;
1878 ExpectedLatency = 0;
1879 DependentLatency = 0;
1881 MaxExecutedResCount = 0;
1883 IsResourceLimited =
false;
1884 ReservedCycles.clear();
1889 MaxObservedStall = 0;
1892 ExecutedResCounts.resize(1);
1893 assert(!ExecutedResCounts[0] &&
"nonzero count for bad resource");
1909 unsigned PIdx = PI->ProcResourceIdx;
1911 RemainingCounts[PIdx] += (Factor * PI->Cycles);
1920 SchedModel = smodel;
1922 if (SchedModel->hasInstrSchedModel()) {
1923 ExecutedResCounts.resize(SchedModel->getNumProcResourceKinds());
1924 ReservedCycles.resize(SchedModel->getNumProcResourceKinds(),
InvalidCycle);
1940 if (ReadyCycle > CurrCycle)
1941 return ReadyCycle - CurrCycle;
1949 unsigned NextUnreserved = ReservedCycles[PIdx];
1951 if (NextUnreserved == InvalidCycle)
1955 NextUnreserved += Cycles;
1956 return NextUnreserved;
1973 if (HazardRec->isEnabled()
1978 unsigned uops = SchedModel->getNumMicroOps(SU->
getInstr());
1979 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {
1981 << SchedModel->getNumMicroOps(SU->
getInstr()) <<
'\n');
1986 ((isTop() && SchedModel->mustBeginGroup(SU->
getInstr())) ||
1987 (!isTop() && SchedModel->mustEndGroup(SU->
getInstr())))) {
1989 << (isTop() ?
"begin" :
"end") <<
" group\n");
1996 make_range(SchedModel->getWriteProcResBegin(SC),
1997 SchedModel->getWriteProcResEnd(SC))) {
1998 unsigned ResIdx = PE.ProcResourceIdx;
1999 unsigned Cycles = PE.Cycles;
2000 unsigned NRCycle = getNextResourceCycle(ResIdx, Cycles);
2001 if (NRCycle > CurrCycle) {
2003 MaxObservedStall =
std::max(Cycles, MaxObservedStall);
2006 << SchedModel->getResourceName(ResIdx) <<
"=" 2007 << NRCycle <<
"c\n");
2018 SUnit *LateSU =
nullptr;
2019 unsigned RemLatency = 0;
2020 for (
SUnit *SU : ReadySUs) {
2021 unsigned L = getUnscheduledLatency(SU);
2022 if (L > RemLatency) {
2029 << LateSU->
NodeNum <<
") " << RemLatency <<
"c\n");
2040 if (!SchedModel->hasInstrSchedModel())
2043 unsigned OtherCritCount = Rem->RemIssueCount
2044 + (RetiredMOps * SchedModel->getMicroOpFactor());
2045 LLVM_DEBUG(
dbgs() <<
" " << Available.getName() <<
" + Remain MOps: " 2046 << OtherCritCount / SchedModel->getMicroOpFactor() <<
'\n');
2047 for (
unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds();
2048 PIdx != PEnd; ++PIdx) {
2049 unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx];
2050 if (OtherCount > OtherCritCount) {
2051 OtherCritCount = OtherCount;
2052 OtherCritIdx = PIdx;
2057 dbgs() <<
" " << Available.getName() <<
" + Remain CritRes: " 2058 << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)
2059 <<
" " << SchedModel->getResourceName(OtherCritIdx) <<
"\n");
2061 return OtherCritCount;
2071 if (ReadyCycle > CurrCycle)
2072 MaxObservedStall =
std::max(ReadyCycle - CurrCycle, MaxObservedStall);
2075 if (ReadyCycle < MinReadyCycle)
2076 MinReadyCycle = ReadyCycle;
2080 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
2081 if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU) ||
2090 if (SchedModel->getMicroOpBufferSize() == 0) {
2092 "MinReadyCycle uninitialized");
2093 if (MinReadyCycle > NextCycle)
2094 NextCycle = MinReadyCycle;
2097 unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle);
2098 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
2101 if ((NextCycle - CurrCycle) > DependentLatency)
2102 DependentLatency = 0;
2104 DependentLatency -= (NextCycle - CurrCycle);
2106 if (!HazardRec->isEnabled()) {
2108 CurrCycle = NextCycle;
2111 for (; CurrCycle != NextCycle; ++CurrCycle) {
2113 HazardRec->AdvanceCycle();
2115 HazardRec->RecedeCycle();
2118 CheckPending =
true;
2121 getScheduledLatency());
2123 LLVM_DEBUG(
dbgs() <<
"Cycle: " << CurrCycle <<
' ' << Available.getName()
2128 ExecutedResCounts[PIdx] += Count;
2129 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
2130 MaxExecutedResCount = ExecutedResCounts[PIdx];
2142 unsigned Factor = SchedModel->getResourceFactor(PIdx);
2143 unsigned Count = Factor * Cycles;
2144 LLVM_DEBUG(
dbgs() <<
" " << SchedModel->getResourceName(PIdx) <<
" +" 2145 << Cycles <<
"x" << Factor <<
"u\n");
2148 incExecutedResources(PIdx, Count);
2149 assert(Rem->RemainingCounts[PIdx] >= Count &&
"resource double counted");
2150 Rem->RemainingCounts[PIdx] -= Count;
2154 if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) {
2155 ZoneCritResIdx = PIdx;
2157 << SchedModel->getResourceName(PIdx) <<
": " 2158 << getResourceCount(PIdx) / SchedModel->getLatencyFactor()
2162 unsigned NextAvailable = getNextResourceCycle(PIdx, Cycles);
2163 if (NextAvailable > CurrCycle) {
2165 << SchedModel->getProcResource(PIdx)->Name
2166 <<
" reserved until @" << NextAvailable <<
"\n");
2168 return NextAvailable;
2174 if (HazardRec->isEnabled()) {
2175 if (!isTop() && SU->
isCall) {
2180 HazardRec->EmitInstruction(SU);
2185 unsigned IncMOps = SchedModel->getNumMicroOps(SU->
getInstr());
2187 (CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) &&
2188 "Cannot schedule this instruction's MicroOps in the current cycle.");
2193 unsigned NextCycle = CurrCycle;
2194 switch (SchedModel->getMicroOpBufferSize()) {
2196 assert(ReadyCycle <= CurrCycle &&
"Broken PendingQueue");
2199 if (ReadyCycle > NextCycle) {
2200 NextCycle = ReadyCycle;
2201 LLVM_DEBUG(
dbgs() <<
" *** Stall until: " << ReadyCycle <<
"\n");
2210 NextCycle = ReadyCycle;
2213 RetiredMOps += IncMOps;
2216 if (SchedModel->hasInstrSchedModel()) {
2217 unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor();
2218 assert(Rem->RemIssueCount >= DecRemIssue &&
"MOps double counted");
2219 Rem->RemIssueCount -= DecRemIssue;
2220 if (ZoneCritResIdx) {
2222 unsigned ScaledMOps =
2223 RetiredMOps * SchedModel->getMicroOpFactor();
2227 if ((
int)(ScaledMOps - getResourceCount(ZoneCritResIdx))
2228 >= (
int)SchedModel->getLatencyFactor()) {
2231 << ScaledMOps / SchedModel->getLatencyFactor()
2236 PI = SchedModel->getWriteProcResBegin(SC),
2237 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2239 countResource(PI->ProcResourceIdx, PI->Cycles, NextCycle);
2240 if (RCycle > NextCycle)
2249 PI = SchedModel->getWriteProcResBegin(SC),
2250 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2251 unsigned PIdx = PI->ProcResourceIdx;
2252 if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {
2254 ReservedCycles[PIdx] =
2255 std::max(getNextResourceCycle(PIdx, 0), NextCycle + PI->Cycles);
2258 ReservedCycles[PIdx] = NextCycle;
2264 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
2265 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
2268 LLVM_DEBUG(
dbgs() <<
" " << Available.getName() <<
" TopLatency SU(" 2269 << SU->
NodeNum <<
") " << TopLatency <<
"c\n");
2273 LLVM_DEBUG(
dbgs() <<
" " << Available.getName() <<
" BotLatency SU(" 2274 << SU->
NodeNum <<
") " << BotLatency <<
"c\n");
2277 if (NextCycle > CurrCycle)
2278 bumpCycle(NextCycle);
2284 getScheduledLatency());
2290 CurrMOps += IncMOps;
2296 if ((isTop() && SchedModel->mustEndGroup(SU->
getInstr())) ||
2297 (!isTop() && SchedModel->mustBeginGroup(SU->
getInstr()))) {
2298 LLVM_DEBUG(
dbgs() <<
" Bump cycle to " << (isTop() ?
"end" :
"begin")
2300 bumpCycle(++NextCycle);
2303 while (CurrMOps >= SchedModel->getIssueWidth()) {
2304 LLVM_DEBUG(
dbgs() <<
" *** Max MOps " << CurrMOps <<
" at cycle " 2305 << CurrCycle <<
'\n');
2306 bumpCycle(++NextCycle);
2315 if (Available.empty())
2320 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
2321 for (
unsigned i = 0, e = Pending.size(); i != e; ++i) {
2322 SUnit *SU = *(Pending.begin()+i);
2325 if (ReadyCycle < MinReadyCycle)
2326 MinReadyCycle = ReadyCycle;
2328 if (!IsBuffered && ReadyCycle > CurrCycle)
2331 if (checkHazard(SU))
2338 Pending.remove(Pending.begin()+i);
2341 CheckPending =
false;
2346 if (Available.isInQueue(SU))
2347 Available.remove(Available.find(SU));
2349 assert(Pending.isInQueue(SU) &&
"bad ready count");
2350 Pending.remove(Pending.find(SU));
2364 if (checkHazard(*
I)) {
2366 I = Available.remove(
I);
2372 for (
unsigned i = 0; Available.empty(); ++i) {
2377 bumpCycle(CurrCycle + 1);
2384 if (Available.size() == 1)
2385 return *Available.begin();
2389 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 2395 if (ZoneCritResIdx) {
2396 ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx);
2397 ResCount = getResourceCount(ZoneCritResIdx);
2399 ResFactor = SchedModel->getMicroOpFactor();
2400 ResCount = RetiredMOps * ResFactor;
2402 unsigned LFactor = SchedModel->getLatencyFactor();
2403 dbgs() << Available.getName() <<
" @" << CurrCycle <<
"c\n" 2404 <<
" Retired: " << RetiredMOps;
2405 dbgs() <<
"\n Executed: " << getExecutedCount() / LFactor <<
"c";
2406 dbgs() <<
"\n Critical: " << ResCount / LFactor <<
"c, " 2407 << ResCount / ResFactor <<
" " 2408 << SchedModel->getResourceName(ZoneCritResIdx)
2409 <<
"\n ExpectedLatency: " << ExpectedLatency <<
"c\n" 2410 << (IsResourceLimited ?
" - Resource" :
" - Latency")
2422 if (!Policy.ReduceResIdx && !Policy.DemandResIdx)
2429 if (PI->ProcResourceIdx == Policy.ReduceResIdx)
2430 ResDelta.CritResources += PI->Cycles;
2431 if (PI->ProcResourceIdx == Policy.DemandResIdx)
2432 ResDelta.DemandedResources += PI->Cycles;
2463 bool GenericSchedulerBase::shouldReduceLatency(
const CandPolicy &Policy,
2465 bool ComputeRemLatency,
2466 unsigned &RemLatency)
const {
2476 if (ComputeRemLatency)
2479 return RemLatency + CurrZone.
getCurrCycle() > Rem.CriticalPath;
2492 unsigned OtherCritIdx = 0;
2493 unsigned OtherCount =
2496 bool OtherResLimited =
false;
2497 unsigned RemLatency = 0;
2498 bool RemLatencyComputed =
false;
2499 if (SchedModel->hasInstrSchedModel() && OtherCount != 0) {
2501 RemLatencyComputed =
true;
2503 OtherCount, RemLatency);
2509 if (!OtherResLimited &&
2510 (IsPostRA || shouldReduceLatency(Policy, CurrZone, !RemLatencyComputed,
2514 <<
" RemainingLatency " << RemLatency <<
" + " 2516 << Rem.CriticalPath <<
"\n");
2525 }
if (OtherResLimited)
dbgs()
2526 <<
" RemainingLimit: " 2527 << SchedModel->getResourceName(OtherCritIdx) <<
"\n";
2529 <<
" Latency limited both directions.\n");
2534 if (OtherResLimited)
2542 case NoCand:
return "NOCAND ";
2543 case Only1:
return "ONLY1 ";
2544 case PhysReg:
return "PHYS-REG ";
2545 case RegExcess:
return "REG-EXCESS";
2546 case RegCritical:
return "REG-CRIT ";
2547 case Stall:
return "STALL ";
2548 case Cluster:
return "CLUSTER ";
2549 case Weak:
return "WEAK ";
2550 case RegMax:
return "REG-MAX ";
2551 case ResourceReduce:
return "RES-REDUCE";
2552 case ResourceDemand:
return "RES-DEMAND";
2553 case TopDepthReduce:
return "TOP-DEPTH ";
2554 case TopPathReduce:
return "TOP-PATH ";
2555 case BotHeightReduce:
return "BOT-HEIGHT";
2556 case BotPathReduce:
return "BOT-PATH ";
2557 case NextDefUse:
return "DEF-USE ";
2565 unsigned ResIdx = 0;
2579 case ResourceReduce:
2582 case ResourceDemand:
2585 case TopDepthReduce:
2591 case BotHeightReduce:
2605 dbgs() <<
" " << SchedModel->getProcResource(ResIdx)->Name <<
" ";
2609 dbgs() <<
" " << Latency <<
" cycles ";
2622 if (TryVal < CandVal) {
2626 if (TryVal > CandVal) {
2627 if (Cand.
Reason > Reason)
2638 if (TryVal > CandVal) {
2642 if (TryVal < CandVal) {
2643 if (Cand.
Reason > Reason)
2687 "(PreRA)GenericScheduler needs vreg liveness");
2692 Rem.init(DAG, SchedModel);
2693 Top.init(DAG, SchedModel, &Rem);
2694 Bot.init(DAG, SchedModel, &Rem);
2701 if (!Top.HazardRec) {
2703 DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
2706 if (!Bot.HazardRec) {
2708 DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
2711 TopCand.SU =
nullptr;
2712 BotCand.SU =
nullptr;
2718 unsigned NumRegionInstrs) {
2725 RegionPolicy.ShouldTrackPressure =
true;
2729 unsigned NIntRegs =
Context->RegClassInfo->getNumAllocatableRegs(
2731 RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
2737 RegionPolicy.OnlyBottomUp =
true;
2743 if (!EnableRegPressure)
2744 RegionPolicy.ShouldTrackPressure =
false;
2749 "-misched-topdown incompatible with -misched-bottomup");
2752 if (RegionPolicy.OnlyBottomUp)
2753 RegionPolicy.OnlyTopDown =
false;
2757 if (RegionPolicy.OnlyTopDown)
2758 RegionPolicy.OnlyBottomUp =
false;
2764 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 2765 dbgs() <<
"GenericScheduler RegionPolicy: " 2766 <<
" ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure
2767 <<
" OnlyTopDown=" << RegionPolicy.OnlyTopDown
2768 <<
" OnlyBottomUp=" << RegionPolicy.OnlyBottomUp
2783 if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)
2787 unsigned IterCount =
2788 std::max(Rem.CyclicCritPath * SchedModel->getLatencyFactor(),
2791 unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor();
2793 unsigned InFlightCount =
2794 (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;
2795 unsigned BufferLimit =
2796 SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor();
2798 Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;
2801 dbgs() <<
"IssueCycles=" 2802 << Rem.RemIssueCount / SchedModel->getLatencyFactor() <<
"c " 2803 <<
"IterCycles=" << IterCount / SchedModel->getLatencyFactor()
2804 <<
"c NumIters=" << (AcyclicCount + IterCount - 1) / IterCount
2805 <<
" InFlight=" << InFlightCount / SchedModel->getMicroOpFactor()
2806 <<
"m BufferLim=" << SchedModel->getMicroOpBufferSize() <<
"m\n";
2807 if (Rem.IsAcyclicLatencyLimited)
dbgs() <<
" ACYCLIC LATENCY LIMIT\n");
2814 for (
const SUnit *SU : Bot.Available) {
2815 if (SU->
getDepth() > Rem.CriticalPath)
2818 LLVM_DEBUG(
dbgs() <<
"Critical Path(GS-RR ): " << Rem.CriticalPath <<
'\n');
2820 errs() <<
"Critical Path(GS-RR ): " << Rem.CriticalPath <<
" \n";
2823 if (EnableCyclicPath && SchedModel->getMicroOpBufferSize() > 0) {
2825 checkAcyclicLatency();
2845 if (Cand.AtTop != TryCand.
AtTop)
2852 if (TryPSet == CandPSet) {
2866 return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);
2884 unsigned ScheduledOper = isTop ? 1 : 0;
2885 unsigned UnscheduledOper = isTop ? 0 : 1;
2896 return AtBoundary ? -1 : 1;
2912 return isTop ? -1 : 1;
2933 if (VerifyScheduling) {
2951 <<
" Try SU(" << Cand.
SU->
NodeNum <<
") " 2983 TryCand, Cand, RegExcess,
TRI,
2990 TryCand, Cand, RegCritical,
TRI,
2999 bool SameBoundary = Zone !=
nullptr;
3004 if (Rem.IsAcyclicLatencyLimited && !Zone->
getCurrMOps() &&
3020 const SUnit *CandNextClusterSU =
3022 const SUnit *TryCandNextClusterSU =
3025 Cand.
SU == CandNextClusterSU,
3026 TryCand, Cand, Cluster))
3033 TryCand, Cand, Weak))
3040 TryCand, Cand, RegMax,
TRI,
3048 TryCand, Cand, ResourceReduce))
3052 TryCand, Cand, ResourceDemand))
3058 !Rem.IsAcyclicLatencyLimited &&
tryLatency(TryCand, Cand, *Zone))
3082 for (
SUnit *SU : Q) {
3085 initCandidate(TryCand, SU, Zone.
isTop(), RPTracker, TempTracker);
3088 tryCandidate(Cand, TryCand, ZoneArg);
3103 if (
SUnit *SU = Bot.pickOnlyChoice()) {
3108 if (
SUnit *SU = Top.pickOnlyChoice()) {
3116 setPolicy(BotPolicy,
false, Bot, &Top);
3120 setPolicy(TopPolicy,
false, Top, &Bot);
3124 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
3125 BotCand.Policy != BotPolicy) {
3128 assert(BotCand.Reason !=
NoCand &&
"failed to find the first candidate");
3132 if (VerifyScheduling) {
3137 "Last pick result should correspond to re-picking right now");
3144 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
3145 TopCand.Policy != TopPolicy) {
3148 assert(TopCand.Reason !=
NoCand &&
"failed to find the first candidate");
3152 if (VerifyScheduling) {
3157 "Last pick result should correspond to re-picking right now");
3163 assert(BotCand.isValid());
3164 assert(TopCand.isValid());
3167 tryCandidate(Cand, TopCand,
nullptr);
3168 if (TopCand.Reason !=
NoCand) {
3169 Cand.setBest(TopCand);
3173 IsTopNode = Cand.AtTop;
3181 assert(Top.Available.empty() && Top.Pending.empty() &&
3182 Bot.Available.empty() && Bot.Pending.empty() &&
"ReadyQ garbage");
3187 if (RegionPolicy.OnlyTopDown) {
3188 SU = Top.pickOnlyChoice();
3191 TopCand.reset(NoPolicy);
3193 assert(TopCand.Reason !=
NoCand &&
"failed to find a candidate");
3198 }
else if (RegionPolicy.OnlyBottomUp) {
3199 SU = Bot.pickOnlyChoice();
3202 BotCand.reset(NoPolicy);
3204 assert(BotCand.Reason !=
NoCand &&
"failed to find a candidate");
3210 SU = pickNodeBidirectional(IsTopNode);
3215 Top.removeReady(SU);
3217 Bot.removeReady(SU);
3232 for (
SDep &Dep : Deps) {
3233 if (Dep.getKind() !=
SDep::Data || !
TRI->isPhysicalRegister(Dep.getReg()))
3235 SUnit *DepSU = Dep.getSUnit();
3236 if (isTop ? DepSU->
Succs.size() > 1 : DepSU->
Preds.size() > 1)
3259 reschedulePhysReg(SU,
true);
3264 reschedulePhysReg(SU,
false);
3299 Rem.init(DAG, SchedModel);
3300 Top.init(DAG, SchedModel, &Rem);
3306 if (!Top.HazardRec) {
3317 for (
const SUnit *SU : BotRoots) {
3318 if (SU->getDepth() > Rem.CriticalPath)
3319 Rem.CriticalPath = SU->getDepth();
3321 LLVM_DEBUG(
dbgs() <<
"Critical Path: (PGS-RR) " << Rem.CriticalPath <<
'\n');
3323 errs() <<
"Critical Path(PGS-RR ): " << Rem.CriticalPath <<
" \n";
3340 if (
tryLess(Top.getLatencyStallCycles(TryCand.
SU),
3341 Top.getLatencyStallCycles(Cand.
SU), TryCand, Cand, Stall))
3347 TryCand, Cand, Cluster))
3352 TryCand, Cand, ResourceReduce))
3355 Cand.ResDelta.DemandedResources,
3356 TryCand, Cand, ResourceDemand))
3360 if (Cand.Policy.ReduceLatency &&
tryLatency(TryCand, Cand, Top)) {
3365 if (TryCand.
SU->
NodeNum < Cand.SU->NodeNum)
3371 for (
SUnit *SU : Q) {
3374 TryCand.
AtTop =
true;
3376 tryCandidate(Cand, TryCand);
3387 assert(Top.Available.empty() && Top.Pending.empty() &&
"ReadyQ garbage");
3392 SU = Top.pickOnlyChoice();
3400 setPolicy(TopCand.
Policy,
true, Top,
nullptr);
3401 pickNodeFromQueue(TopCand);
3409 Top.removeReady(SU);
3424 return new ScheduleDAGMI(C, llvm::make_unique<PostGenericScheduler>(C),
3437 const BitVector *ScheduledTrees =
nullptr;
3440 ILPOrder(
bool MaxILP) : MaximizeILP(MaxILP) {}
3445 bool operator()(
const SUnit *A,
const SUnit *
B)
const {
3448 if (SchedTreeA != SchedTreeB) {
3450 if (ScheduledTrees->
test(SchedTreeA) != ScheduledTrees->
test(SchedTreeB))
3451 return ScheduledTrees->
test(SchedTreeB);
3472 std::vector<SUnit*> ReadyQ;
3475 ILPScheduler(
bool MaximizeILP) : Cmp(MaximizeILP) {}
3481 Cmp.DFSResult = DAG->getDFSResult();
3482 Cmp.ScheduledTrees = &DAG->getScheduledTrees();
3488 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
3496 if (ReadyQ.empty())
return nullptr;
3497 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
3498 SUnit *SU = ReadyQ.back();
3502 <<
"SU(" << SU->NodeNum <<
") " 3509 <<
"Scheduling " << *SU->getInstr());
3515 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
3521 assert(!IsTopNode &&
"SchedDFSResult needs bottom-up");
3527 ReadyQ.push_back(SU);
3528 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
3555 template<
bool IsReverse>
3581 InstructionShuffler(
bool alternate,
bool topdown)
3582 : IsAlternating(alternate), IsTopDown(topdown) {}
3596 if (TopQ.empty())
return nullptr;
3603 if (BottomQ.empty())
return nullptr;
3610 IsTopDown = !IsTopDown;
3630 "-misched-topdown incompatible with -misched-bottomup");
3632 C, llvm::make_unique<InstructionShuffler>(Alternate, TopDown));
3636 "shuffle",
"Shuffle machine instructions alternating directions",
3663 if (ViewMISchedCutoff == 0)
3665 return (Node->
Preds.size() > ViewMISchedCutoff
3675 return "color=cyan,style=dashed";
3677 return "color=blue,style=dashed";
3698 std::string Str(
"shape=Mrecord");
3703 Str +=
",style=filled,fillcolor=\"#";
3720 errs() <<
"ScheduleDAGMI::viewGraph is only available in debug builds on " 3721 <<
"systems with Graphviz or gv!\n";
3727 viewGraph(getDAGName(),
"Scheduling-Units Graph for " + getDAGName());
void computeDFSResult()
Compute a DFSResult after DAG building is complete, and before any queue comparisons.
std::reverse_iterator< const_iterator > const_reverse_iterator
unsigned findMaxLatency(ArrayRef< SUnit *> ReadySUs)
void releaseSucc(SUnit *SU, SDep *SuccEdge)
ReleaseSucc - Decrement the NumPredsLeft count of a successor.
int biasPhysReg(const SUnit *SU, bool isTop)
Minimize physical register live ranges.
Weak DAG edge linking a chain of clustered instrs.
bool isPHIDef() const
Returns true if this value is defined by a PHI instruction (or was, PHI instructions may have been el...
unsigned getNumInstrs(const SUnit *SU) const
Get the number of instructions in the given subtree and its children.
void schedNode(SUnit *SU, bool IsTopNode) override
Called after ScheduleDAGMI has scheduled an instruction and updated scheduled/remaining flags in the ...
const_iterator end(StringRef path)
Get end iterator over path.
virtual void finishBlock()
Cleans up after scheduling in the given block.
virtual void initialize(ScheduleDAGMI *DAG)=0
Initialize the strategy after building the DAG for a new region.
A common definition of LaneBitmask for use in TableGen and CodeGen.
unsigned getZoneCritResIdx() const
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static cl::opt< bool > ViewMISchedDAGs("view-misched-dags", cl::Hidden, cl::desc("Pop up a window to show MISched dags after they are processed"))
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G)
static cl::opt< bool > EnablePostRAMachineSched("enable-post-misched", cl::desc("Enable the post-ra machine instruction scheduling pass."), cl::init(true), cl::Hidden)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
static MachinePassRegistry< ScheduleDAGCtor > Registry
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
iterator_base< SparseMultiSet *> iterator
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
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 ...
void dumpSchedule() const
dump the scheduled Sequence.
typename SuperClass::const_iterator const_iterator
virtual ~MachineSchedContext()
Each Scheduling boundary is associated with ready queues.
SlotIndex def
The index of the defining instruction.
This class represents lattice values for constants.
void addPressureChange(unsigned RegUnit, bool IsDec, const MachineRegisterInfo *MRI)
Add a change in pressure to the pressure diff of a given instruction.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
SUnit * pickNodeBidirectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
virtual void releaseTopNode(SUnit *SU)=0
When all predecessor dependencies have been resolved, free this node for top-down scheduling...
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)
A Module instance is used to store all the information related to an LLVM module. ...
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
Segments::iterator iterator
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
void push_back(const T &Elt)
void startBlock(MachineBasicBlock *bb) override
Prepares to perform scheduling in the given block.
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
unsigned getCurrCycle() const
Number of cycles to issue the instructions scheduled in this zone.
LiveInterval - This class represents the liveness of a register, or stack slot.
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...
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
static cl::opt< std::string > SchedOnlyFunc("misched-only-func", cl::Hidden, cl::desc("Only schedule this function"))
unsigned getReg() const
getReg - Returns the register number.
unsigned computeCyclicCriticalPath()
Compute the cyclic critical path through the DAG.
void dump() const override
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
void fixupKills(MachineBasicBlock &MBB)
Fixes register kill flags that scheduling has made invalid.
virtual const TargetLowering * getTargetLowering() const
void traceCandidate(const SchedCandidate &Cand)
unsigned DemandedResources
reverse_iterator rbegin() const
static bool renderGraphFromBottomUp()
bool test(unsigned Idx) const
ScheduleDAGMI * createGenericSchedPostRA(MachineSchedContext *C)
Create a generic scheduler with no vreg liveness or DAG mutation passes.
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
Mutate the DAG as a postpass after normal DAG building.
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
void initQueues(ArrayRef< SUnit *> TopRoots, ArrayRef< SUnit *> BotRoots)
Release ExitSU predecessors and setup scheduler queues.
static ScheduleDAGInstrs * createILPMaxScheduler(MachineSchedContext *C)
virtual std::string getGraphNodeLabel(const SUnit *SU) const =0
Returns a label for an SUnit node in a visualization of the ScheduleDAG.
virtual const TargetRegisterClass * getRegClassFor(MVT VT) const
Return the register class that should be used for the specified value type.
unsigned getDependentLatency() const
static ScheduleDAGInstrs * createInstructionShuffler(MachineSchedContext *C)
unsigned const TargetRegisterInfo * TRI
Printable PrintLaneMask(LaneBitmask LaneMask)
Create Printable object to print LaneBitmasks on a raw_ostream.
char & MachineSchedulerID
MachineScheduler - This pass schedules machine instructions.
Summarize the unscheduled region.
void reset(const CandPolicy &NewPolicy)
const SchedDFSResult * getDFSResult() const
Return a non-null DFS result if the scheduling strategy initialized it.
RegisterPassParser class - Handle the addition of new machine passes.
unsigned getReg() const
Returns the register associated with this edge.
MachineSchedRegistry provides a selection of available machine instruction schedulers.
bool isBottomReady() const
VNInfo - Value Number Information.
iterator_range< mop_iterator > operands()
static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G)
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
static MachineSchedRegistry ShufflerRegistry("shuffle", "Shuffle machine instructions alternating directions", createInstructionShuffler)
unsigned BotReadyCycle
Cycle relative to end when node is ready.
static MachineSchedRegistry ILPMaxRegistry("ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler)
void updateQueues(SUnit *SU, bool IsTopNode)
Update scheduler DAG and queues after scheduling an instruction.
virtual void schedNode(SUnit *SU, bool IsTopNode)=0
Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an instruction and updated scheduled/rem...
SmallVector< SDep, 4 > Preds
All sunit predecessors.
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)
static cl::opt< bool > PrintDAGs("misched-print-dags", cl::Hidden, cl::desc("Print schedule DAGs"))
bool isMoveImmediate(QueryType Type=IgnoreBundle) const
Return true if this instruction is a move immediate (including conditional moves) instruction...
A register anti-dependence (aka WAR).
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
*ViewGraph Emit a dot run run gv on the postscript *then cleanup For use from the debugger *void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)
virtual bool hasVRegLiveness() const
Return true if this DAG supports VReg liveness and RegPressure.
MachineFunction & MF
Machine function.
bool isScheduled
True once scheduled.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
ArrayRef< SUnit * > elements()
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
const RegPressureTracker & getBotRPTracker() const
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
unsigned NumSuccsLeft
of succs not scheduled.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Provide an instruction scheduling machine model to CodeGen passes.
const HexagonInstrInfo * TII
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...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
An individual mapping from virtual register number to SUnit.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
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.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Regular data dependence (aka true-dependence).
Result of a LiveRange query.
bool hasPhysRegUses
Has physreg uses.
void apply(Opt *O, const Mod &M, const Mods &... Ms)
StringRef getName() const
bool hasPhysRegDefs
Has physreg defs that are being used.
PressureDiff & getPressureDiff(const SUnit *SU)
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model. ...
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Target-Independent Code Generator Pass Configuration Options.
static constexpr LaneBitmask getNone()
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Initialize the per-region scheduling policy.
static bool isSimple(Instruction *I)
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
static const char * getReasonStr(SIScheduleCandReason Reason)
Compute the values of each DAG node for various metrics during DFS.
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
unsigned TopReadyCycle
Cycle relative to start when node is ready.
static const unsigned InvalidCycle
unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC=nullptr) const
Return the number of issue slots required for this MI.
static cl::opt< bool > VerifyScheduling("verify-misched", cl::Hidden, cl::desc("Verify machine instrs before and after machine scheduling"))
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register. ...
void bumpCycle(unsigned NextCycle)
Move the boundary of scheduled code by one cycle.
unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle)
Add the given processor resource to this scheduled zone.
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.
bool hasReservedResource
Uses a reserved resource.
void scheduleMI(SUnit *SU, bool IsTopNode)
Move an instruction and update register pressure.
virtual void overrideSchedPolicy(MachineSchedPolicy &Policy, unsigned NumRegionInstrs) const
Override generic scheduling policy within a region.
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
MachineBasicBlock::iterator top() const
void buildDAGWithRegPressure()
Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking enabled.
unsigned WeakSuccsLeft
of weak succs not scheduled.
static void getSchedRegions(MachineBasicBlock *MBB, MBBRegionsVector &Regions, bool RegionsTopDown)
static const char * getReasonStr(GenericSchedulerBase::CandReason Reason)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
static std::string getGraphName(const ScheduleDAG *G)
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Itinerary data supplied by a subtarget to be used by a target.
unsigned NumPredsLeft
of preds not scheduled.
static void tracePick(GenericSchedulerBase::CandReason Reason, bool IsTop)
void releasePending()
Release pending ready nodes in to the available queue.
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...
COFF::MachineTypes Machine
ScheduleDAGMILive * createGenericSchedLive(MachineSchedContext *C)
Create the standard converging machine scheduler.
MachinePassRegistry - Track the registration of machine passes.
List of registers defined and used by a machine instruction.
virtual const TargetInstrInfo * getInstrInfo() const
std::vector< SUnit * >::iterator iterator
void collectVRegUses(SUnit &SU)
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.
unsigned getCurrMOps() const
Micro-ops issued in the current cycle.
const SUnit * getNextClusterSucc() const
void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
SUnit * pickNode(bool &IsTopNode) override
Pick the next node to schedule.
unsigned getSubtreeID(const SUnit *SU) const
Get the ID of the subtree the given DAG node belongs to.
void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop, const RegPressureTracker &RPTracker, RegPressureTracker &TempTracker)
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
SUnit * getSUnit(MachineInstr *MI) const
Returns an existing SUnit for this MI, or nullptr.
void checkAcyclicLatency()
Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic critical path by more cycle...
static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G)
VNInfo * valueIn() const
Return the value that is live-in to the instruction.
void incExecutedResources(unsigned PIdx, unsigned Count)
LiveQueryResult Query(SlotIndex Idx) const
Query Liveness at Idx.
TargetInstrInfo - Interface to description of machine instruction set.
virtual void registerRoots()
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
bool isUnbuffered
Uses an unbuffered resource.
void getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
Consider the pressure increase caused by traversing this instruction top-down.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
unsigned getPSetOrMax() const
initializer< Ty > init(const Ty &Val)
bool isCall
Is a function call.
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
unsigned getNextResourceCycle(unsigned PIdx, unsigned Cycles)
Compute the next cycle at which the given processor resource can be scheduled.
CandReason
Represent the type of SchedCandidate found within a single queue.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Helpers for implementing custom MachineSchedStrategy classes.
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
unsigned const MachineRegisterInfo * MRI
PressureChange CurrentMax
bool tryGreater(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
unsigned short Latency
Node latency.
static const unsigned MinSubtreeSize
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
Summarize the scheduling resources required for an instruction of a particular scheduling class...
void updatePressureDiffs(ArrayRef< RegisterMaskPair > LiveUses)
Update the PressureDiff array for liveness after scheduling this instruction.
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...
StackDirection getStackGrowthDirection() const
getStackGrowthDirection - Return the direction the stack grows
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.
Printable printVRegOrUnit(unsigned VRegOrUnit, const TargetRegisterInfo *TRI)
Create Printable object to print virtual registers and physical registers on a raw_ostream.
RegisterPressure computed within a region of instructions delimited by TopPos and BottomPos...
int getNumOccurrences() const
virtual bool doMBBSchedRegionsTopDown() const
If this method returns true, handling of the scheduling regions themselves (in case of a scheduling b...
bool addEdge(SUnit *SuccSU, const SDep &PredDep)
Add a DAG edge to the given SU with the given predecessor dependence data.
Represent the analysis usage information of a pass.
Store the state used by GenericScheduler heuristics, required for the lifetime of one invocation of p...
bool checkHazard(SUnit *SU)
Does this SU have a hazard within the current instruction group.
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
void releasePred(SUnit *SU, SDep *PredEdge)
ReleasePred - Decrement the NumSuccsLeft count of a predecessor.
Track the current register pressure at some position in the instruction stream, and remember the high...
virtual void releaseBottomNode(SUnit *SU)=0
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
Policy for scheduling the next instruction in the candidate's zone.
static ScheduleDAGInstrs * useDefaultMachineSched(MachineSchedContext *C)
A dummy default scheduler factory indicates whether the scheduler is overridden on the command line...
const TargetSchedModel * getSchedModel() const
Gets the machine model for instruction scheduling.
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
unsigned getScheduledLatency() const
Get the number of latency cycles "covered" by the scheduled instructions.
List of PressureChanges in order of increasing, unique PSetID.
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
DOTGraphTraits(bool isSimple=false)
SchedResourceDelta ResDelta
ScheduleDAGInstrs *(*)(MachineSchedContext *) ScheduleDAGCtor
std::unique_ptr< ScheduleDAGMutation > createStoreClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
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...
void initQueues(ArrayRef< SUnit *> TopRoots, ArrayRef< SUnit *> BotRoots)
Release ExitSU predecessors and setup scheduler queues.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
unsigned getWeakLeft(const SUnit *SU, bool isTop)
bool isDebugInstr() const
void releaseSuccessors(SUnit *SU)
releaseSuccessors - Call releaseSucc on each of SU's successors.
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream...
std::string & str()
Flushes the stream contents to the target string and returns the string's reference.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void viewGraph() override
Out-of-line implementation with no arguments is handy for gdb.
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...
virtual bool enableMachineScheduler() const
True if the subtarget should run MachineScheduler after aggressive coalescing.
static cl::opt< bool > EnableRegPressure("misched-regpressure", cl::Hidden, cl::desc("Enable register pressure scheduling."), cl::init(true))
void sort(IteratorTy Start, IteratorTy End)
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
unsigned WeakPredsLeft
of weak preds not scheduled.
DOTGraphTraits - Template class that can be specialized to customize how graphs are converted to 'dot...
void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem)
static cl::opt< unsigned > SchedOnlyBlock("misched-only-block", cl::Hidden, cl::desc("Only schedule this MBB#"))
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
std::vector< unsigned > MaxSetPressure
Map of max reg pressure indexed by pressure set ID, not class ID.
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...
virtual bool isSchedulingBoundary(const MachineInstr &MI, const MachineBasicBlock *MBB, const MachineFunction &MF) const
Test if the given instruction should be considered a scheduling boundary.
Iterator for intrusive lists based on ilist_node.
std::unique_ptr< ScheduleDAGMutation > createLoadClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
void registerRoots() override
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
AnalysisUsage & addRequiredID(const void *ID)
MachineOperand class - Representation of each machine instruction operand.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
static cl::opt< unsigned > MISchedCutoff("misched-cutoff", cl::Hidden, cl::desc("Stop scheduling after N instructions"), cl::init(~0U))
static ScheduleDAGInstrs * createILPMinScheduler(MachineSchedContext *C)
MachineInstrBuilder MachineInstrBuilder & DefMI
static cl::opt< bool > EnableMachineSched("enable-misched", cl::desc("Enable the machine instruction scheduling pass."), cl::init(true), cl::Hidden)
Information about stack frame layout on the target.
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) override
Implement the ScheduleDAGInstrs interface for handling the next scheduling region.
cl::opt< bool > DumpCriticalPathLength("misched-dcpl", cl::Hidden, cl::desc("Print critical path length to stdout"))
void releaseNode(SUnit *SU, unsigned ReadyCycle)
unsigned getMicroOpFactor() const
Multiply number of micro-ops by this factor to normalize it relative to other resources.
CHAIN = SC CHAIN, Imm128 - System call.
const RegPressureTracker & getTopRPTracker() const
StringRef getColorString(unsigned NodeNumber)
Get a color string for this node number.
void updateScheduledPressure(const SUnit *SU, const std::vector< unsigned > &NewMaxPressure)
bool isResourceLimited() const
void setPreservesCFG()
This function should be called by the pass, iff they do not:
LiveInterval & getInterval(unsigned Reg)
std::unique_ptr< ScheduleDAGMutation > createCopyConstrainDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
static cl::opt< bool > EnableCyclicPath("misched-cyclicpath", cl::Hidden, cl::desc("Enable cyclic critical path analysis."), cl::init(true))
void initResourceDelta(const ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)
INITIALIZE_PASS(PostMachineScheduler, "postmisched", "PostRA Machine Instruction Scheduler", false, false) PostMachineScheduler
const Function & getFunction() const
Return the LLVM function that this machine code represents.
~ScheduleDAGMILive() override
void initializeMachineSchedulerPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
unsigned getOtherResourceCount(unsigned &OtherCritIdx)
void dumpPolicy() const override
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
VNInfo * getVNInfoBefore(SlotIndex Idx) const
getVNInfoBefore - Return the VNInfo that is live up to but not necessarilly including Idx...
virtual void finalizeSchedule()
Allow targets to perform final scheduling actions at the level of the whole MachineFunction.
void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand)
Apply a set of heuristics to a new candidate for PostRA scheduling.
bool tryLess(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
Return true if this heuristic determines order.
bool getMemOperandWithOffset(MachineInstr &LdSt, MachineOperand *&BaseOp, int64_t &Offset, const TargetRegisterInfo *TRI) const override
Get the base register and byte offset of a load/store instr.
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
PressureChange CriticalMax
virtual void schedule()=0
Orders nodes according to selected style.
unsigned getResourceFactor(unsigned ResIdx) const
Multiply the number of units consumed for a resource by this factor to normalize it relative to other...
typename SuperClass::iterator iterator
void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos)
Change the position of an instruction within the basic block and update live ranges and region bounda...
unsigned getNumProcResourceKinds() const
Get the number of kinds of resources for this target.
void dumpNode(const SUnit &SU) const override
static MachineSchedRegistry DefaultSchedRegistry("default", "Use the target's default scheduler choice.", useDefaultMachineSched)
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
void schedNode(SUnit *SU, bool IsTopNode) override
Update the scheduler's state after scheduling a node.
virtual void scheduleTree(unsigned SubtreeID)
Scheduler callback to notify that a new subtree is scheduled.
const MachineBasicBlock * getParent() const
void releasePredecessors(SUnit *SU)
releasePredecessors - Call releasePred on each of SU's predecessors.
unsigned getSubtreeLevel(unsigned SubtreeID) const
Get the connection level of a subtree.
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
virtual void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand, SchedBoundary *Zone) const
Apply a set of heuristics to a new candidate.
virtual SUnit * pickNode(bool &IsTopNode)=0
Pick the next node to schedule, or return NULL.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
void reschedulePhysReg(SUnit *SU, bool isTop)
A ScheduleDAG for scheduling lists of MachineInstr.
reverse_iterator rend() const
Representation of each machine instruction.
SUnit ExitSU
Special node for the region exit.
void initializePostMachineSchedulerPass(PassRegistry &)
void dump(const TargetRegisterInfo &TRI) const
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void initialize(ScheduleDAGMI *Dag) override
Initialize the strategy after building the DAG for a new region.
const TargetRegisterInfo * TRI
Target processor register info.
SUnit * pickOnlyChoice()
Call this before applying any other heuristics to the Available queue.
void findRootsAndBiasEdges(SmallVectorImpl< SUnit *> &TopRoots, SmallVectorImpl< SUnit *> &BotRoots)
void dumpRegSetPressure(ArrayRef< unsigned > SetPressure, const TargetRegisterInfo *TRI)
Status of an instruction's critical resource consumption.
~ScheduleDAGMI() override
LiveIntervals * getLIS() const
char & PostMachineSchedulerID
PostMachineScheduler - This pass schedules machine instructions postRA.
cl::opt< bool > ForceBottomUp
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use...
void dumpScheduledState() const
MachineBasicBlock::iterator bottom() const
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
Capture a change in pressure for a single pressure set.
virtual const TargetFrameLowering * getFrameLowering() const
bool isFI() const
isFI - Tests if this is a MO_FrameIndex operand.
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.
const SUnit * getNextClusterPred() const
static ScheduleDAGInstrs * createConveringSched(MachineSchedContext *C)
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
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...
unsigned getLatencyStallCycles(SUnit *SU)
Get the difference between the given SUnit's ready time and the current cycle.
void schedule() override
Implement ScheduleDAGInstrs interface for scheduling a sequence of reorderable instructions.
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.
const TargetInstrInfo * TII
Target instruction information.
static bool isNodeHidden(const SUnit *Node)
Kind getKind() const
Returns an enum value representing the kind of the dependence.
static MachineSchedRegistry GenericSchedRegistry("converge", "Standard converging scheduler.", createConveringSched)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
virtual bool enablePostRAScheduler() const
True if the subtarget should run a scheduler after register allocation.
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...
unsigned NodeNum
Entry # of node in the node vector.
const std::vector< PressureChange > & getRegionCriticalPSets() const
bool isCtrlDep() const
Tests if this is not an SDep::Data dependence.
void registerRoots() override
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
bool tryPressure(const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason, const TargetRegisterInfo *TRI, const MachineFunction &MF)
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
bool operator<(int64_t V1, const APSInt &V2)
A raw_ostream that writes to an std::string.
bool isTrackingPressure() const
Return true if register pressure tracking is enabled.
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
bool isLocal(SlotIndex Start, SlotIndex End) const
True iff this segment is a single segment that lies between the specified boundaries, exclusively.
static bool checkResourceLimit(unsigned LFactor, unsigned Count, unsigned Latency)
Given a Count of resource usage and a Latency value, return true if a SchedBoundary becomes resource ...
void postprocessDAG()
Apply each ScheduleDAGMutation step in order.
nonconst_iterator getNonConstIterator() const
virtual ScheduleHazardRecognizer * CreateTargetMIHazardRecognizer(const InstrItineraryData *, const ScheduleDAG *DAG) const
Allocate and return a hazard recognizer to use for this target when scheduling the machine instructio...
SmallVector< SDep, 4 > Succs
All sunit successors.
bool isCluster() const
Tests if this is an Order dependence that is marked as "cluster", meaning it is artificial and wants ...
static const Function * getParent(const Value *V)
Arbitrary strong DAG edge (no real dependence).
bool isWeak() const
Tests if this a weak dependence.
This class implements an extremely fast bulk output stream that can only output to a stream...
DefaultDOTGraphTraits - This class provides the default implementations of all of the DOTGraphTraits ...
Machine Instruction Scheduler
void clear()
clear - Erase all elements from the queue.
INITIALIZE_PASS_BEGIN(MachineScheduler, DEBUG_TYPE, "Machine Instruction Scheduler", false, false) INITIALIZE_PASS_END(MachineScheduler
bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)
True if an edge can be added from PredSU to SuccSU without creating a cycle.
static MachineSchedRegistry ILPMinRegistry("ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler)
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
std::vector< SUnit > SUnits
The scheduling units.
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
const MachineOperand & getOperand(unsigned i) const
SlotIndex - An opaque wrapper around machine indexes.
void finishBlock() override
Cleans up after scheduling in the given block.
MachineOperandType getType() const
getType - Returns the MachineOperandType for this operand.
void setBest(SchedCandidate &Best)
virtual unsigned getRegPressureSetScore(const MachineFunction &MF, unsigned PSetID) const
Return a heuristic for the machine scheduler to compare the profitability of increasing one register ...
void pickNodeFromQueue(SchedCandidate &Cand)
Scheduling unit. This is a node in the scheduling DAG.
This file describes how to lower LLVM code to machine code.
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
Add a postprocessing step to the DAG builder.
cl::opt< bool > ForceTopDown
static unsigned computeRemLatency(SchedBoundary &CurrZone)
Compute remaining latency.
ILPValue getILP(const SUnit *SU) const
Get the ILP value for a DAG node.
static cl::opt< bool > EnableMemOpCluster("misched-cluster", cl::Hidden, cl::desc("Enable memop clustering."), cl::init(true))
bool isArtificialDep() const