15 #define DEBUG_TYPE "misched"
41 cl::desc(
"Force top-down list scheduling"));
43 cl::desc(
"Force bottom-up list scheduling"));
48 cl::desc(
"Pop up a window to show MISched dags after they are processed"));
70 cl::desc(
"Verify machine instrs before and after machine scheduling"));
76 void MachineSchedStrategy::anchor() {}
77 void ScheduleDAGMutation::anchor() {}
84 MF(0), MLI(0), MDT(0), PassConfig(0), AA(0), LIS(0) {
101 virtual void releaseMemory() {}
119 "Machine Instruction Scheduler",
false,
false)
126 MachineScheduler::MachineScheduler()
131 void MachineScheduler::getAnalysisUsage(
AnalysisUsage &AU)
const {
157 cl::desc(
"Machine instruction scheduler to use"));
172 assert(I != Beg &&
"reached the top of the region, cannot decrement");
174 if (!I->isDebugValue())
193 for(; I != End; ++
I) {
194 if (!I->isDebugValue())
208 const_cast<MachineInstr*>(
249 MLI = &getAnalysis<MachineLoopInfo>();
250 MDT = &getAnalysis<MachineDominatorTree>();
251 PassConfig = &getAnalysis<TargetPassConfig>();
252 AA = &getAnalysis<AliasAnalysis>();
254 LIS = &getAnalysis<LiveIntervals>();
259 MF->verify(
this,
"Before machine scheduling.");
261 RegClassInfo->runOnMachineFunction(*MF);
272 MBB != MBBEnd; ++MBB) {
286 unsigned RemainingInstrs = MBB->size();
288 RegionEnd != MBB->begin(); RegionEnd = Scheduler->
begin()) {
291 if (RegionEnd != MBB->end()
292 || TII->isSchedulingBoundary(
llvm::prior(RegionEnd), MBB, *MF)) {
300 unsigned NumRegionInstrs = 0;
302 for(;I != MBB->begin(); --
I, --RemainingInstrs, ++NumRegionInstrs) {
303 if (TII->isSchedulingBoundary(
llvm::prior(I), MBB, *MF))
308 Scheduler->
enterRegion(MBB, I, RegionEnd, NumRegionInstrs);
311 if (I == RegionEnd || I ==
llvm::prior(RegionEnd)) {
317 DEBUG(
dbgs() <<
"********** MI Scheduling **********\n");
319 <<
":BB#" << MBB->getNumber() <<
" " << MBB->getName()
320 <<
"\n From: " << *I <<
" To: ";
321 if (RegionEnd != MBB->end())
dbgs() << *RegionEnd;
322 else dbgs() <<
"End";
323 dbgs() <<
" RegionInstrs: " << NumRegionInstrs
324 <<
" Remaining: " << RemainingInstrs <<
"\n");
335 RegionEnd = Scheduler->
begin();
337 assert(RemainingInstrs == 0 &&
"Instruction count mismatch!");
343 MF->verify(
this,
"After machine scheduling.");
351 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
353 dbgs() << Name <<
": ";
354 for (
unsigned i = 0, e = Queue.size(); i < e; ++i)
355 dbgs() << Queue[i]->NodeNum <<
" ";
403 dbgs() <<
"*** Scheduling failed! ***\n";
405 dbgs() <<
" has been released too many times!\n";
437 dbgs() <<
"*** Scheduling failed! ***\n";
439 dbgs() <<
" has been released too many times!\n";
468 LIS->handleMove(MI,
true);
493 unsigned regioninstrs)
554 for (
unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
556 if (RegionPressure[i] > Limit) {
558 <<
" Limit " << Limit
559 <<
" Actual " << RegionPressure[i] <<
"\n");
572 const std::vector<unsigned> &NewMaxPressure) {
579 unsigned ID = I->getPSet();
584 && NewMaxPressure[ID] <= INT16_MAX)
588 if (NewMaxPressure[ID] >= Limit - 2) {
590 << NewMaxPressure[
ID] <<
" > " << Limit <<
"(+ "
599 for (
unsigned LUIdx = 0, LUEnd = LiveUses.
size(); LUIdx != LUEnd; ++LUIdx) {
601 unsigned Reg = LiveUses[LUIdx];
621 assert(VNI &&
"No live value at use.");
663 DEBUG(
for (
unsigned su = 0, e =
SUnits.size(); su != e; ++su)
664 SUnits[su].dumpAll(
this));
670 bool IsTopNode =
false;
672 assert(!SU->isScheduled &&
"Node already scheduled");
685 unsigned BBNum =
begin()->getParent()->getNumber();
686 dbgs() <<
"*** Final schedule for BB#" << BBNum <<
" ***\n";
718 for (
unsigned i = 0, e =
Mutations.size(); i < e; ++i) {
735 for (std::vector<SUnit>::iterator
738 assert(!SU->
isBoundaryNode() &&
"Boundary node should not be in SUnits");
744 if (!I->NumPredsLeft)
747 if (!I->NumSuccsLeft)
781 unsigned MaxCyclicLatency = 0;
799 unsigned LiveOutHeight = DefSU->
getHeight();
809 LI.
Query(LIS->getInstructionIndex(UI->SU->getInstr()));
816 unsigned CyclicLatency = 0;
817 if (LiveOutDepth > UI->SU->getDepth())
818 CyclicLatency = LiveOutDepth - UI->SU->getDepth();
820 unsigned LiveInHeight = UI->SU->getHeight() + DefSU->
Latency;
821 if (LiveInHeight > LiveOutHeight) {
822 if (LiveInHeight - LiveOutHeight < CyclicLatency)
823 CyclicLatency = LiveInHeight - LiveOutHeight;
829 << UI->SU->NodeNum <<
") = " << CyclicLatency <<
"c\n");
830 if (CyclicLatency > MaxCyclicLatency)
831 MaxCyclicLatency = CyclicLatency;
834 DEBUG(
dbgs() <<
"Cyclic Critical Path: " << MaxCyclicLatency <<
"c\n");
835 return MaxCyclicLatency;
849 I = TopRoots.
begin(), E = TopRoots.
end(); I != E; ++
I) {
855 I = BotRoots.
rbegin(), E = BotRoots.
rend(); I != E; ++
I) {
880 assert(SU->
isTopReady() &&
"node still has unscheduled dependencies");
896 assert(SU->
isBottomReady() &&
"node still has unscheduled dependencies");
951 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
953 std::pair<MachineInstr *, MachineInstr *>
P = *
prior(DI);
966 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
972 dbgs() <<
"Missing SUnit\n";
989 LoadInfo(
SUnit *su,
unsigned reg,
unsigned ofs)
990 : SU(su), BaseReg(reg), Offset(ofs) {}
992 static bool LoadInfoLess(
const LoadClusterMutation::LoadInfo &LHS,
993 const LoadClusterMutation::LoadInfo &RHS);
1000 : TII(tii), TRI(tri) {}
1008 bool LoadClusterMutation::LoadInfoLess(
1009 const LoadClusterMutation::LoadInfo &LHS,
1010 const LoadClusterMutation::LoadInfo &RHS) {
1011 if (LHS.BaseReg != RHS.BaseReg)
1012 return LHS.BaseReg < RHS.BaseReg;
1013 return LHS.Offset < RHS.Offset;
1019 for (
unsigned Idx = 0, End = Loads.
size(); Idx != End; ++Idx) {
1020 SUnit *SU = Loads[Idx];
1023 if (TII->getLdStBaseRegImmOfs(SU->
getInstr(), BaseReg, Offset, TRI))
1024 LoadRecords.
push_back(LoadInfo(SU, BaseReg, Offset));
1026 if (LoadRecords.
size() < 2)
1028 std::sort(LoadRecords.
begin(), LoadRecords.
end(), LoadInfoLess);
1029 unsigned ClusterLength = 1;
1030 for (
unsigned Idx = 0, End = LoadRecords.
size(); Idx < (End - 1); ++Idx) {
1031 if (LoadRecords[Idx].BaseReg != LoadRecords[Idx+1].BaseReg) {
1036 SUnit *SUa = LoadRecords[Idx].SU;
1037 SUnit *SUb = LoadRecords[Idx+1].SU;
1038 if (TII->shouldClusterLoads(SUa->
getInstr(), SUb->
getInstr(), ClusterLength)
1048 SI = SUa->
Succs.begin(), SE = SUa->
Succs.end(); SI != SE; ++SI) {
1049 if (SI->getSUnit() == SUb)
1051 DEBUG(
dbgs() <<
" Copy Succ SU(" << SI->getSUnit()->NodeNum <<
")\n");
1067 for (
unsigned Idx = 0, End = DAG->
SUnits.size(); Idx != End; ++Idx) {
1071 unsigned ChainPredID = DAG->
SUnits.size();
1073 PI = SU->
Preds.begin(), PE = SU->
Preds.end(); PI != PE; ++PI) {
1075 ChainPredID = PI->getSUnit()->NodeNum;
1081 unsigned NumChains = StoreChainDependents.
size();
1082 std::pair<DenseMap<unsigned, unsigned>::iterator,
bool> Result =
1083 StoreChainIDs.
insert(std::make_pair(ChainPredID, NumChains));
1085 StoreChainDependents.
resize(NumChains + 1);
1086 StoreChainDependents[Result.first->second].
push_back(SU);
1089 for (
unsigned Idx = 0, End = StoreChainDependents.
size(); Idx != End; ++Idx)
1090 clusterNeighboringLoads(StoreChainDependents[Idx], DAG);
1117 for (
unsigned Idx = DAG->
SUnits.size(); Idx > 0;) {
1130 assert(Success &&
"No DAG nodes should be reachable from ExitSU");
1196 unsigned LocalReg = DstReg;
1197 unsigned GlobalReg = SrcReg;
1199 if (!LocalLI->
isLocal(RegionBeginIdx, RegionEndIdx)) {
1203 if (!LocalLI->
isLocal(RegionBeginIdx, RegionEndIdx))
1214 if (GlobalSegment == GlobalLI->
end())
1221 if (GlobalSegment->contains(LocalLI->
beginIndex()))
1224 if (GlobalSegment == GlobalLI->
end())
1228 if (GlobalSegment != GlobalLI->
begin()) {
1231 GlobalSegment->start)) {
1242 assert(
llvm::prior(GlobalSegment)->start < LocalLI->beginIndex() &&
1243 "Disconnected LRG within the scheduling region.");
1260 I = LastLocalSU->
Succs.begin(), E = LastLocalSU->
Succs.end();
1262 if (I->getKind() !=
SDep::Data || I->getReg() != LocalReg)
1264 if (I->getSUnit() == GlobalSU)
1266 if (!DAG->
canAddEdge(GlobalSU, I->getSUnit()))
1277 I = GlobalSU->
Preds.begin(), E = GlobalSU->
Preds.end(); I != E; ++
I) {
1278 if (I->getKind() !=
SDep::Anti || I->getReg() != GlobalReg)
1280 if (I->getSUnit() == FirstLocalSU)
1282 if (!DAG->
canAddEdge(FirstLocalSU, I->getSUnit()))
1289 I = LocalUses.
begin(), E = LocalUses.
end(); I != E; ++
I) {
1290 DEBUG(
dbgs() <<
" Local use SU(" << (*I)->NodeNum <<
") -> SU("
1291 << GlobalSU->
NodeNum <<
")\n");
1295 I = GlobalUses.
begin(), E = GlobalUses.
end(); I != E; ++
I) {
1296 DEBUG(
dbgs() <<
" Global use SU(" << (*I)->NodeNum <<
") -> SU("
1297 << FirstLocalSU->
NodeNum <<
")\n");
1306 if (FirstPos == DAG->
end())
1312 for (
unsigned Idx = 0, End = DAG->
SUnits.size(); Idx != End; ++Idx) {
1317 constrainLocalCopy(SU, DAG);
1333 NoCand, PhysRegCopy, RegExcess, RegCritical, Cluster, Weak, RegMax,
1334 ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
1335 TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
1338 static const char *getReasonStr(GenericScheduler::CandReason Reason);
1344 unsigned ReduceResIdx;
1345 unsigned DemandResIdx;
1347 CandPolicy(): ReduceLatency(
false), ReduceResIdx(0), DemandResIdx(0) {}
1351 struct SchedResourceDelta {
1353 unsigned CritResources;
1356 unsigned DemandedResources;
1358 SchedResourceDelta(): CritResources(0), DemandedResources(0) {}
1360 bool operator==(
const SchedResourceDelta &RHS)
const {
1361 return CritResources == RHS.CritResources
1362 && DemandedResources == RHS.DemandedResources;
1364 bool operator!=(
const SchedResourceDelta &RHS)
const {
1371 struct SchedCandidate {
1381 uint32_t RepeatReasonSet;
1387 SchedResourceDelta ResDelta;
1389 SchedCandidate(
const CandPolicy &policy)
1390 : Policy(policy), SU(NULL), Reason(NoCand), RepeatReasonSet(0) {}
1392 bool isValid()
const {
return SU; }
1395 void setBest(SchedCandidate &Best) {
1396 assert(Best.Reason != NoCand &&
"uninitialized Sched candidate");
1398 Reason = Best.Reason;
1399 RPDelta = Best.RPDelta;
1400 ResDelta = Best.ResDelta;
1403 bool isRepeat(CandReason R) {
return RepeatReasonSet & (1 << R); }
1404 void setRepeat(CandReason R) { RepeatReasonSet |= (1 << R); }
1411 struct SchedRemainder {
1413 unsigned CriticalPath;
1414 unsigned CyclicCritPath;
1417 unsigned RemIssueCount;
1419 bool IsAcyclicLatencyLimited;
1428 IsAcyclicLatencyLimited =
false;
1429 RemainingCounts.
clear();
1432 SchedRemainder() { reset(); }
1440 struct SchedBoundary {
1443 SchedRemainder *Rem;
1464 unsigned MinReadyCycle;
1467 unsigned ExpectedLatency;
1472 unsigned DependentLatency;
1476 unsigned RetiredMOps;
1486 unsigned MaxExecutedResCount;
1489 unsigned ZoneCritResIdx;
1492 bool IsResourceLimited;
1497 unsigned MaxObservedLatency;
1504 if (HazardRec && HazardRec->isEnabled()) {
1510 CheckPending =
false;
1514 MinReadyCycle = UINT_MAX;
1515 ExpectedLatency = 0;
1516 DependentLatency = 0;
1518 MaxExecutedResCount = 0;
1520 IsResourceLimited =
false;
1522 MaxObservedLatency = 0;
1525 ExecutedResCounts.resize(1);
1526 assert(!ExecutedResCounts[0] &&
"nonzero count for bad resource");
1532 DAG(0), SchedModel(0), Rem(0), Available(ID, Name+
".A"),
1533 Pending(ID << GenericScheduler::LogMaxQID, Name+
".P"),
1538 ~SchedBoundary() {
delete HazardRec; }
1541 SchedRemainder *rem);
1543 bool isTop()
const {
1544 return Available.getID() == GenericScheduler::TopQID;
1548 const char *getResourceName(
unsigned PIdx) {
1551 return SchedModel->getProcResource(PIdx)->Name;
1558 unsigned getScheduledLatency()
const {
1559 return std::max(ExpectedLatency, CurrCycle);
1562 unsigned getUnscheduledLatency(
SUnit *SU)
const {
1566 unsigned getResourceCount(
unsigned ResIdx)
const {
1567 return ExecutedResCounts[ResIdx];
1572 unsigned getCriticalCount()
const {
1573 if (!ZoneCritResIdx)
1574 return RetiredMOps * SchedModel->getMicroOpFactor();
1575 return getResourceCount(ZoneCritResIdx);
1581 unsigned getExecutedCount()
const {
1582 return std::max(CurrCycle * SchedModel->getLatencyFactor(),
1583 MaxExecutedResCount);
1586 bool checkHazard(
SUnit *SU);
1590 unsigned getOtherResourceCount(
unsigned &OtherCritIdx);
1592 void setPolicy(CandPolicy &Policy, SchedBoundary &OtherZone);
1594 void releaseNode(
SUnit *SU,
unsigned ReadyCycle);
1596 void bumpCycle(
unsigned NextCycle);
1598 void incExecutedResources(
unsigned PIdx,
unsigned Count);
1600 unsigned countResource(
unsigned PIdx,
unsigned Cycles,
unsigned ReadyCycle);
1602 void bumpNode(
SUnit *SU);
1604 void releasePending();
1606 void removeReady(
SUnit *SU);
1608 SUnit *pickOnlyChoice();
1611 void dumpScheduledState();
1636 Context(C), DAG(0), SchedModel(0), TRI(0),
1637 Top(TopQID,
"TopQ"), Bot(BotQID,
"BotQ") {}
1641 unsigned NumRegionInstrs);
1643 bool shouldTrackPressure()
const {
return RegionPolicy.ShouldTrackPressure; }
1647 virtual SUnit *pickNode(
bool &IsTopNode);
1649 virtual void schedNode(
SUnit *SU,
bool IsTopNode);
1651 virtual void releaseTopNode(
SUnit *SU);
1653 virtual void releaseBottomNode(
SUnit *SU);
1655 virtual void registerRoots();
1658 void checkAcyclicLatency();
1660 void tryCandidate(SchedCandidate &Cand,
1661 SchedCandidate &TryCand,
1662 SchedBoundary &Zone,
1666 SUnit *pickNodeBidirectional(
bool &IsTopNode);
1668 void pickNodeFromQueue(SchedBoundary &Zone,
1670 SchedCandidate &Candidate);
1672 void reschedulePhysRegCopies(
SUnit *SU,
bool isTop);
1675 void traceCandidate(
const SchedCandidate &Cand);
1686 for (std::vector<SUnit>::iterator
1687 I = DAG->
SUnits.begin(), E = DAG->
SUnits.end(); I != E; ++
I) {
1694 unsigned PIdx = PI->ProcResourceIdx;
1696 RemainingCounts[PIdx] += (Factor * PI->Cycles);
1705 SchedModel = smodel;
1714 unsigned NumRegionInstrs) {
1720 unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs(
1723 RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
1727 RegionPolicy.OnlyBottomUp =
true;
1735 RegionPolicy.ShouldTrackPressure =
false;
1740 "-misched-topdown incompatible with -misched-bottomup");
1743 if (RegionPolicy.OnlyBottomUp)
1744 RegionPolicy.OnlyTopDown =
false;
1748 if (RegionPolicy.OnlyTopDown)
1749 RegionPolicy.OnlyBottomUp =
false;
1758 Rem.init(DAG, SchedModel);
1759 Top.init(DAG, SchedModel, &Rem);
1760 Bot.init(DAG, SchedModel, &Rem);
1768 if (!Top.HazardRec) {
1772 if (!Bot.HazardRec) {
1778 void GenericScheduler::releaseTopNode(
SUnit *SU) {
1786 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
1787 unsigned Latency = I->getLatency();
1789 Top.MaxObservedLatency = std::max(Latency, Top.MaxObservedLatency);
1797 void GenericScheduler::releaseBottomNode(
SUnit *SU) {
1801 assert(SU->
getInstr() &&
"Scheduled SUnit must have instr");
1807 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
1808 unsigned Latency = I->getLatency();
1810 Bot.MaxObservedLatency = std::max(Latency, Bot.MaxObservedLatency);
1827 void GenericScheduler::checkAcyclicLatency() {
1828 if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)
1832 unsigned IterCount =
1838 unsigned InFlightCount =
1839 (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;
1840 unsigned BufferLimit =
1843 Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;
1848 <<
"c NumIters=" << (AcyclicCount + IterCount-1) / IterCount
1851 if (Rem.IsAcyclicLatencyLimited)
1852 dbgs() <<
" ACYCLIC LATENCY LIMIT\n");
1855 void GenericScheduler::registerRoots() {
1859 for (std::vector<SUnit*>::const_iterator
1860 I = Bot.Available.begin(), E = Bot.Available.end(); I != E; ++
I) {
1861 if ((*I)->getDepth() > Rem.CriticalPath)
1862 Rem.CriticalPath = (*I)->getDepth();
1864 DEBUG(
dbgs() <<
"Critical Path: " << Rem.CriticalPath <<
'\n');
1868 checkAcyclicLatency();
1885 bool GenericScheduler::SchedBoundary::checkHazard(
SUnit *SU) {
1886 if (HazardRec->isEnabled())
1890 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->
getIssueWidth())) {
1899 unsigned GenericScheduler::SchedBoundary::
1902 unsigned RemLatency = 0;
1905 unsigned L = getUnscheduledLatency(*I);
1906 if (L > RemLatency) {
1912 DEBUG(
dbgs() << Available.getName() <<
" RemLatency SU("
1913 << LateSU->
NodeNum <<
") " << RemLatency <<
"c\n");
1921 unsigned GenericScheduler::SchedBoundary::
1922 getOtherResourceCount(
unsigned &OtherCritIdx) {
1927 unsigned OtherCritCount = Rem->RemIssueCount
1929 DEBUG(
dbgs() <<
" " << Available.getName() <<
" + Remain MOps: "
1932 PIdx != PEnd; ++PIdx) {
1933 unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx];
1934 if (OtherCount > OtherCritCount) {
1935 OtherCritCount = OtherCount;
1936 OtherCritIdx = PIdx;
1940 DEBUG(
dbgs() <<
" " << Available.getName() <<
" + Remain CritRes: "
1942 <<
" " << getResourceName(OtherCritIdx) <<
"\n");
1944 return OtherCritCount;
1949 void GenericScheduler::SchedBoundary::setPolicy(CandPolicy &Policy,
1950 SchedBoundary &OtherZone) {
1968 unsigned RemLatency = DependentLatency;
1969 RemLatency = std::max(RemLatency, findMaxLatency(Available.elements()));
1970 RemLatency = std::max(RemLatency, findMaxLatency(Pending.elements()));
1973 unsigned OtherCritIdx;
1974 unsigned OtherCount = OtherZone.getOtherResourceCount(OtherCritIdx);
1976 bool OtherResLimited =
false;
1979 OtherResLimited = (int)(OtherCount - (RemLatency * LFactor)) > (
int)LFactor;
1981 if (!OtherResLimited && (RemLatency + CurrCycle > Rem->CriticalPath)) {
1982 Policy.ReduceLatency |=
true;
1983 DEBUG(
dbgs() <<
" " << Available.getName() <<
" RemainingLatency "
1984 << RemLatency <<
" + " << CurrCycle <<
"c > CritPath "
1985 << Rem->CriticalPath <<
"\n");
1988 if (ZoneCritResIdx == OtherCritIdx)
1992 if (IsResourceLimited) {
1993 dbgs() <<
" " << Available.getName() <<
" ResourceLimited: "
1994 << getResourceName(ZoneCritResIdx) <<
"\n";
1996 if (OtherResLimited)
1997 dbgs() <<
" RemainingLimit: " << getResourceName(OtherCritIdx) <<
"\n";
1998 if (!IsResourceLimited && !OtherResLimited)
1999 dbgs() <<
" Latency limited both directions.\n");
2001 if (IsResourceLimited && !Policy.ReduceResIdx)
2002 Policy.ReduceResIdx = ZoneCritResIdx;
2004 if (OtherResLimited)
2005 Policy.DemandResIdx = OtherCritIdx;
2008 void GenericScheduler::SchedBoundary::releaseNode(
SUnit *SU,
2009 unsigned ReadyCycle) {
2010 if (ReadyCycle < MinReadyCycle)
2011 MinReadyCycle = ReadyCycle;
2016 if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU))
2026 void GenericScheduler::SchedBoundary::bumpCycle(
unsigned NextCycle) {
2028 assert(MinReadyCycle < UINT_MAX &&
"MinReadyCycle uninitialized");
2029 if (MinReadyCycle > NextCycle)
2030 NextCycle = MinReadyCycle;
2033 unsigned DecMOps = SchedModel->
getIssueWidth() * (NextCycle - CurrCycle);
2034 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
2037 if ((NextCycle - CurrCycle) > DependentLatency)
2038 DependentLatency = 0;
2040 DependentLatency -= (NextCycle - CurrCycle);
2042 if (!HazardRec->isEnabled()) {
2044 CurrCycle = NextCycle;
2048 for (; CurrCycle != NextCycle; ++CurrCycle) {
2050 HazardRec->AdvanceCycle();
2052 HazardRec->RecedeCycle();
2055 CheckPending =
true;
2058 (int)(getCriticalCount() - (getScheduledLatency() * LFactor))
2061 DEBUG(
dbgs() <<
"Cycle: " << CurrCycle <<
' ' << Available.getName() <<
'\n');
2064 void GenericScheduler::SchedBoundary::incExecutedResources(
unsigned PIdx,
2066 ExecutedResCounts[PIdx] += Count;
2067 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
2068 MaxExecutedResCount = ExecutedResCounts[PIdx];
2078 unsigned GenericScheduler::SchedBoundary::
2079 countResource(
unsigned PIdx,
unsigned Cycles,
unsigned ReadyCycle) {
2081 unsigned Count = Factor * Cycles;
2082 DEBUG(
dbgs() <<
" " << getResourceName(PIdx)
2083 <<
" +" << Cycles <<
"x" << Factor <<
"u\n");
2086 incExecutedResources(PIdx, Count);
2087 assert(Rem->RemainingCounts[PIdx] >= Count &&
"resource double counted");
2088 Rem->RemainingCounts[PIdx] -= Count;
2092 if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) {
2093 ZoneCritResIdx = PIdx;
2094 DEBUG(
dbgs() <<
" *** Critical resource "
2095 << getResourceName(PIdx) <<
": "
2103 void GenericScheduler::SchedBoundary::bumpNode(
SUnit *SU) {
2105 if (HazardRec->isEnabled()) {
2106 if (!isTop() && SU->
isCall) {
2111 HazardRec->EmitInstruction(SU);
2115 CurrMOps += IncMOps;
2123 unsigned NextCycle = CurrCycle;
2126 DEBUG(
dbgs() <<
" *** Max MOps " << CurrMOps
2127 <<
" at cycle " << CurrCycle <<
'\n');
2130 DEBUG(
dbgs() <<
" Ready @" << ReadyCycle <<
"c\n");
2134 assert(ReadyCycle <= CurrCycle &&
"Broken PendingQueue");
2137 if (ReadyCycle > NextCycle) {
2138 NextCycle = ReadyCycle;
2139 DEBUG(
dbgs() <<
" *** Stall until: " << ReadyCycle <<
"\n");
2147 RetiredMOps += IncMOps;
2152 assert(Rem->RemIssueCount >= DecRemIssue &&
"MOps double counted");
2153 Rem->RemIssueCount -= DecRemIssue;
2154 if (ZoneCritResIdx) {
2156 unsigned ScaledMOps =
2161 if ((
int)(ScaledMOps - getResourceCount(ZoneCritResIdx))
2164 DEBUG(
dbgs() <<
" *** Critical resource NumMicroOps: "
2172 countResource(PI->ProcResourceIdx, PI->Cycles, ReadyCycle);
2173 if (RCycle > NextCycle)
2178 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
2179 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
2182 DEBUG(
dbgs() <<
" " << Available.getName()
2183 <<
" TopLatency SU(" << SU->
NodeNum <<
") " << TopLatency <<
"c\n");
2187 DEBUG(
dbgs() <<
" " << Available.getName()
2188 <<
" BotLatency SU(" << SU->
NodeNum <<
") " << BotLatency <<
"c\n");
2191 if (NextCycle > CurrCycle) {
2192 bumpCycle(NextCycle);
2199 (int)(getCriticalCount() - (getScheduledLatency() * LFactor))
2202 DEBUG(dumpScheduledState());
2207 void GenericScheduler::SchedBoundary::releasePending() {
2209 if (Available.empty())
2210 MinReadyCycle = UINT_MAX;
2215 for (
unsigned i = 0, e = Pending.size(); i != e; ++i) {
2216 SUnit *SU = *(Pending.begin()+i);
2219 if (ReadyCycle < MinReadyCycle)
2220 MinReadyCycle = ReadyCycle;
2222 if (!IsBuffered && ReadyCycle > CurrCycle)
2225 if (checkHazard(SU))
2229 Pending.remove(Pending.begin()+i);
2232 DEBUG(
if (!Pending.empty()) Pending.dump());
2233 CheckPending =
false;
2237 void GenericScheduler::SchedBoundary::removeReady(
SUnit *SU) {
2238 if (Available.isInQueue(SU))
2239 Available.remove(Available.find(SU));
2241 assert(Pending.isInQueue(SU) &&
"bad ready count");
2242 Pending.remove(Pending.find(SU));
2249 SUnit *GenericScheduler::SchedBoundary::pickOnlyChoice() {
2256 if (checkHazard(*I)) {
2258 I = Available.remove(I);
2264 for (
unsigned i = 0; Available.empty(); ++i) {
2265 assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedLatency) &&
2266 "permanent hazard"); (void)i;
2267 bumpCycle(CurrCycle + 1);
2270 if (Available.size() == 1)
2271 return *Available.begin();
2278 void GenericScheduler::SchedBoundary::dumpScheduledState() {
2281 if (ZoneCritResIdx) {
2283 ResCount = getResourceCount(ZoneCritResIdx);
2290 dbgs() << Available.getName() <<
" @" << CurrCycle <<
"c\n"
2291 <<
" Retired: " << RetiredMOps;
2292 dbgs() <<
"\n Executed: " << getExecutedCount() / LFactor <<
"c";
2293 dbgs() <<
"\n Critical: " << ResCount / LFactor <<
"c, "
2294 << ResCount / ResFactor <<
" " << getResourceName(ZoneCritResIdx)
2295 <<
"\n ExpectedLatency: " << ExpectedLatency <<
"c\n"
2296 << (IsResourceLimited ?
" - Resource" :
" - Latency")
2301 void GenericScheduler::SchedCandidate::
2304 if (!Policy.ReduceResIdx && !Policy.DemandResIdx)
2311 if (PI->ProcResourceIdx == Policy.ReduceResIdx)
2312 ResDelta.CritResources += PI->Cycles;
2313 if (PI->ProcResourceIdx == Policy.DemandResIdx)
2314 ResDelta.DemandedResources += PI->Cycles;
2321 GenericScheduler::SchedCandidate &TryCand,
2322 GenericScheduler::SchedCandidate &Cand,
2323 GenericScheduler::CandReason Reason) {
2324 if (TryVal < CandVal) {
2325 TryCand.Reason = Reason;
2328 if (TryVal > CandVal) {
2329 if (Cand.Reason > Reason)
2330 Cand.Reason = Reason;
2333 Cand.setRepeat(Reason);
2338 GenericScheduler::SchedCandidate &TryCand,
2339 GenericScheduler::SchedCandidate &Cand,
2340 GenericScheduler::CandReason Reason) {
2341 if (TryVal > CandVal) {
2342 TryCand.Reason = Reason;
2345 if (TryVal < CandVal) {
2346 if (Cand.Reason > Reason)
2347 Cand.Reason = Reason;
2350 Cand.setRepeat(Reason);
2356 GenericScheduler::SchedCandidate &TryCand,
2357 GenericScheduler::SchedCandidate &Cand,
2358 GenericScheduler::CandReason Reason) {
2362 if (TryRank == CandRank) {
2375 return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);
2394 unsigned ScheduledOper = isTop ? 1 : 0;
2395 unsigned UnscheduledOper = isTop ? 0 : 1;
2406 return AtBoundary ? -1 : 1;
2410 static bool tryLatency(GenericScheduler::SchedCandidate &TryCand,
2411 GenericScheduler::SchedCandidate &Cand,
2412 GenericScheduler::SchedBoundary &Zone) {
2414 if (Cand.SU->getDepth() > Zone.getScheduledLatency()) {
2415 if (
tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(),
2416 TryCand, Cand, GenericScheduler::TopDepthReduce))
2419 if (
tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(),
2420 TryCand, Cand, GenericScheduler::TopPathReduce))
2424 if (Cand.SU->getHeight() > Zone.getScheduledLatency()) {
2425 if (
tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(),
2426 TryCand, Cand, GenericScheduler::BotHeightReduce))
2429 if (
tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(),
2430 TryCand, Cand, GenericScheduler::BotPathReduce))
2447 void GenericScheduler::tryCandidate(SchedCandidate &Cand,
2448 SchedCandidate &TryCand,
2449 SchedBoundary &Zone,
2457 TryCand.SU->getInstr(),
2465 TryCand.SU->getInstr(),
2473 TryCand.SU->getInstr(),
2481 DEBUG(
if (TryCand.RPDelta.Excess.isValid())
2482 dbgs() <<
" SU(" << TryCand.SU->NodeNum <<
") "
2483 << TRI->getRegPressureSetName(TryCand.RPDelta.Excess.getPSet())
2484 <<
":" << TryCand.RPDelta.Excess.getUnitInc() <<
"\n");
2487 if (!Cand.isValid()) {
2488 TryCand.Reason = NodeOrder;
2494 TryCand, Cand, PhysRegCopy))
2500 Cand.RPDelta.Excess,
2501 TryCand, Cand, RegExcess))
2506 Cand.RPDelta.CriticalMax,
2507 TryCand, Cand, RegCritical))
2513 if (Rem.IsAcyclicLatencyLimited && !Zone.CurrMOps
2523 const SUnit *NextClusterSU =
2525 if (
tryGreater(TryCand.SU == NextClusterSU, Cand.SU == NextClusterSU,
2526 TryCand, Cand, Cluster))
2532 TryCand, Cand, Weak)) {
2537 Cand.RPDelta.CurrentMax,
2538 TryCand, Cand, RegMax))
2542 TryCand.initResourceDelta(DAG, SchedModel);
2543 if (
tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
2544 TryCand, Cand, ResourceReduce))
2546 if (
tryGreater(TryCand.ResDelta.DemandedResources,
2547 Cand.ResDelta.DemandedResources,
2548 TryCand, Cand, ResourceDemand))
2553 if (Cand.Policy.ReduceLatency && !Rem.IsAcyclicLatencyLimited
2561 if (
tryGreater(Zone.NextSUs.count(TryCand.SU), Zone.NextSUs.count(Cand.SU),
2562 TryCand, Cand, NextDefUse))
2566 if ((Zone.isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)
2567 || (!Zone.isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
2568 TryCand.Reason = NodeOrder;
2573 const char *GenericScheduler::getReasonStr(
2574 GenericScheduler::CandReason Reason) {
2576 case NoCand:
return "NOCAND ";
2577 case PhysRegCopy:
return "PREG-COPY";
2578 case RegExcess:
return "REG-EXCESS";
2579 case RegCritical:
return "REG-CRIT ";
2580 case Cluster:
return "CLUSTER ";
2581 case Weak:
return "WEAK ";
2582 case RegMax:
return "REG-MAX ";
2583 case ResourceReduce:
return "RES-REDUCE";
2584 case ResourceDemand:
return "RES-DEMAND";
2585 case TopDepthReduce:
return "TOP-DEPTH ";
2586 case TopPathReduce:
return "TOP-PATH ";
2587 case BotHeightReduce:
return "BOT-HEIGHT";
2588 case BotPathReduce:
return "BOT-PATH ";
2589 case NextDefUse:
return "DEF-USE ";
2590 case NodeOrder:
return "ORDER ";
2595 void GenericScheduler::traceCandidate(
const SchedCandidate &Cand) {
2597 unsigned ResIdx = 0;
2598 unsigned Latency = 0;
2599 switch (Cand.Reason) {
2603 P = Cand.RPDelta.Excess;
2606 P = Cand.RPDelta.CriticalMax;
2609 P = Cand.RPDelta.CurrentMax;
2611 case ResourceReduce:
2612 ResIdx = Cand.Policy.ReduceResIdx;
2614 case ResourceDemand:
2615 ResIdx = Cand.Policy.DemandResIdx;
2617 case TopDepthReduce:
2618 Latency = Cand.SU->getDepth();
2621 Latency = Cand.SU->getHeight();
2623 case BotHeightReduce:
2624 Latency = Cand.SU->getHeight();
2627 Latency = Cand.SU->getDepth();
2630 dbgs() <<
" SU(" << Cand.SU->NodeNum <<
") " << getReasonStr(Cand.Reason);
2632 dbgs() <<
" " << TRI->getRegPressureSetName(P.
getPSet())
2641 dbgs() <<
" " << Latency <<
" cycles ";
2653 void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
2655 SchedCandidate &Cand) {
2665 SchedCandidate TryCand(Cand.Policy);
2667 tryCandidate(Cand, TryCand, Zone, RPTracker, TempTracker);
2668 if (TryCand.Reason != NoCand) {
2670 if (TryCand.ResDelta == SchedResourceDelta())
2671 TryCand.initResourceDelta(DAG, SchedModel);
2672 Cand.setBest(TryCand);
2673 DEBUG(traceCandidate(Cand));
2678 static void tracePick(
const GenericScheduler::SchedCandidate &Cand,
2680 DEBUG(
dbgs() <<
"Pick " << (IsTop ?
"Top " :
"Bot ")
2681 << GenericScheduler::getReasonStr(Cand.Reason) <<
'\n');
2685 SUnit *GenericScheduler::pickNodeBidirectional(
bool &IsTopNode) {
2688 if (
SUnit *SU = Bot.pickOnlyChoice()) {
2693 if (
SUnit *SU = Top.pickOnlyChoice()) {
2698 CandPolicy NoPolicy;
2699 SchedCandidate BotCand(NoPolicy);
2700 SchedCandidate TopCand(NoPolicy);
2701 Bot.setPolicy(BotCand.Policy, Top);
2702 Top.setPolicy(TopCand.Policy, Bot);
2706 assert(BotCand.Reason != NoCand &&
"failed to find the first candidate");
2715 if ((BotCand.Reason == RegExcess && !BotCand.isRepeat(RegExcess))
2716 || (BotCand.Reason == RegCritical
2717 && !BotCand.isRepeat(RegCritical)))
2725 assert(TopCand.Reason != NoCand &&
"failed to find the first candidate");
2728 if (TopCand.Reason < BotCand.Reason) {
2740 SUnit *GenericScheduler::pickNode(
bool &IsTopNode) {
2742 assert(Top.Available.empty() && Top.Pending.empty() &&
2743 Bot.Available.empty() && Bot.Pending.empty() &&
"ReadyQ garbage");
2748 if (RegionPolicy.OnlyTopDown) {
2749 SU = Top.pickOnlyChoice();
2751 CandPolicy NoPolicy;
2752 SchedCandidate TopCand(NoPolicy);
2754 assert(TopCand.Reason != NoCand &&
"failed to find a candidate");
2760 else if (RegionPolicy.OnlyBottomUp) {
2761 SU = Bot.pickOnlyChoice();
2763 CandPolicy NoPolicy;
2764 SchedCandidate BotCand(NoPolicy);
2766 assert(BotCand.Reason != NoCand &&
"failed to find a candidate");
2773 SU = pickNodeBidirectional(IsTopNode);
2778 Top.removeReady(SU);
2780 Bot.removeReady(SU);
2786 void GenericScheduler::reschedulePhysRegCopies(
SUnit *SU,
bool isTop) {
2797 if (I->getKind() !=
SDep::Data || !TRI->isPhysicalRegister(I->getReg()))
2799 SUnit *DepSU = I->getSUnit();
2800 if (isTop ? DepSU->
Succs.size() > 1 : DepSU->
Preds.size() > 1)
2805 DEBUG(
dbgs() <<
" Rescheduling physreg copy ";
2806 I->getSUnit()->dump(DAG));
2817 void GenericScheduler::schedNode(
SUnit *SU,
bool IsTopNode) {
2822 reschedulePhysRegCopies(SU,
true);
2828 reschedulePhysRegCopies(SU,
false);
2863 ILPOrder(
bool MaxILP): DFSResult(0), ScheduledTrees(0), MaximizeILP(MaxILP) {}
2868 bool operator()(
const SUnit *
A,
const SUnit *B)
const {
2869 unsigned SchedTreeA = DFSResult->getSubtreeID(A);
2870 unsigned SchedTreeB = DFSResult->getSubtreeID(B);
2871 if (SchedTreeA != SchedTreeB) {
2873 if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB))
2874 return ScheduledTrees->test(SchedTreeB);
2877 if (DFSResult->getSubtreeLevel(SchedTreeA)
2878 != DFSResult->getSubtreeLevel(SchedTreeB)) {
2879 return DFSResult->getSubtreeLevel(SchedTreeA)
2880 < DFSResult->getSubtreeLevel(SchedTreeB);
2884 return DFSResult->getILP(A) < DFSResult->getILP(B);
2886 return DFSResult->getILP(A) > DFSResult->getILP(B);
2895 std::vector<SUnit*> ReadyQ;
2897 ILPScheduler(
bool MaximizeILP): DAG(0), Cmp(MaximizeILP) {}
2907 virtual void registerRoots() {
2909 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
2916 virtual SUnit *pickNode(
bool &IsTopNode) {
2917 if (ReadyQ.empty())
return NULL;
2918 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
2919 SUnit *SU = ReadyQ.back();
2922 DEBUG(
dbgs() <<
"Pick node " <<
"SU(" << SU->NodeNum <<
") "
2927 <<
"Scheduling " << *SU->getInstr());
2932 virtual void scheduleTree(
unsigned SubtreeID) {
2933 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
2938 virtual void schedNode(
SUnit *SU,
bool IsTopNode) {
2939 assert(!IsTopNode &&
"SchedDFSResult needs bottom-up");
2942 virtual void releaseTopNode(
SUnit *) { }
2944 virtual void releaseBottomNode(
SUnit *SU) {
2945 ReadyQ.push_back(SU);
2946 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
2970 template<
bool IsReverse>
2994 InstructionShuffler(
bool alternate,
bool topdown)
2995 : IsAlternating(alternate), IsTopDown(topdown) {}
3005 virtual SUnit *pickNode(
bool &IsTopNode) {
3009 if (TopQ.empty())
return NULL;
3017 if (BottomQ.empty())
return NULL;
3024 IsTopDown = !IsTopDown;
3028 virtual void schedNode(
SUnit *SU,
bool IsTopNode) {}
3030 virtual void releaseTopNode(
SUnit *SU) {
3033 virtual void releaseBottomNode(
SUnit *SU) {
3043 "-misched-topdown incompatible with -misched-bottomup");
3044 return new ScheduleDAGMI(C,
new InstructionShuffler(Alternate, TopDown));
3047 "shuffle",
"Shuffle machine instructions alternating directions",
3075 return (Node->
Preds.size() > 10 || Node->
Succs.size() > 10);
3089 return "color=cyan,style=dashed";
3091 return "color=blue,style=dashed";
3111 std::string Str(
"shape=Mrecord");
3115 Str +=
",style=filled,fillcolor=\"#";
3132 errs() <<
"ScheduleDAGMI::viewGraph is only available in debug builds on "
3133 <<
"systems with Graphviz or gv!\n";
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
virtual ScheduleHazardRecognizer * CreateTargetMIHazardRecognizer(const InstrItineraryData *, const ScheduleDAG *DAG) const
void DeleteContainerPointers(Container &C)
void releaseSucc(SUnit *SU, SDep *SuccEdge)
static int biasPhysRegCopy(const SUnit *SU, bool isTop)
Weak DAG edge linking a chain of clustered instrs.
void push_back(const T &Elt)
static ScheduleDAGInstrs * createGenericSched(MachineSchedContext *C)
const_iterator end(StringRef path)
Get end iterator over path.
virtual void finishBlock()
finishBlock - Clean up after scheduling in the given block.
virtual void initialize(ScheduleDAGMI *DAG)=0
Initialize the strategy after building the DAG for a new region.
bool advance()
Advance across the current instruction.
virtual const TargetLowering * getTargetLowering() const
AnalysisUsage & addPreserved()
static cl::opt< bool > ViewMISchedDAGs("view-misched-dags", cl::Hidden, cl::desc("Pop up a window to show MISched dags after they are processed"))
void clear()
Clear the results.
static PassRegistry * getPassRegistry()
Segments::iterator iterator
bool isArtificialDep() const
virtual ~MachineSchedContext()
SlotIndex def
The index of the defining instruction.
void addMutation(ScheduleDAGMutation *Mutation)
void addPressureChange(unsigned RegUnit, bool IsDec, const MachineRegisterInfo *MRI)
Add a change in pressure to the pressure diff of a given instruction.
virtual void releaseTopNode(SUnit *SU)=0
The main container class for the LLVM Intermediate Representation.
static MachineSchedRegistry ILPMaxRegistry("ilpmax","Schedule bottom-up for max ILP", createILPMaxScheduler)
ScheduleDAGTopologicalSort Topo
void print(raw_ostream &OS, SlotIndexes *=0) const
unsigned getSubtreeLevel(unsigned SubtreeID) const
Get the connection level of a subtree.
MachineBasicBlock::iterator CurrentTop
The top of the unscheduled zone.
unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC=0) const
Return the number of issue slots required for this MI.
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
MachineInstr * getInstr() const
SlotIndex getInstructionIndex(const MachineInstr *instr) const
Returns the base index of the given instruction.
static bool isVirtualRegister(unsigned Reg)
void buildDAGWithRegPressure()
Build the DAG and setup three register pressure trackers.
static bool renderGraphFromBottomUp()
bool isLocal(SlotIndex Start, SlotIndex End) const
MachineBasicBlock::iterator begin() const
begin - Return an iterator to the top of the current scheduling region.
unsigned getMicroOpBufferSize() const
Number of micro-ops that may be buffered for OOO execution.
Mutate the DAG as a postpass after normal DAG building.
const_iterator begin(StringRef path)
Get begin iterator over path.
static ScheduleDAGInstrs * createILPMaxScheduler(MachineSchedContext *C)
virtual std::string getGraphNodeLabel(const SUnit *SU) const =0
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolve and cache a resolved scheduling class for an SUnit.
static ScheduleDAGInstrs * createInstructionShuffler(MachineSchedContext *C)
char & MachineSchedulerID
MachineScheduler - This pass schedules machine instructions.
void closeRegion()
Finalize the region boundaries and recored live ins and live outs.
unsigned getResourceFactor(unsigned ResIdx) const
Multiply the number of units consumed for a resource by this factor to normalize it relative to other...
virtual bool shouldTrackPressure() const
virtual std::string getDAGName() const
Return a label for the region of code covered by the DAG.
MachineBasicBlock::iterator top() const
Instructions::iterator instr_iterator
static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G)
bool isArtificial() const
void updateQueues(SUnit *SU, bool IsTopNode)
Update scheduler DAG and queues after scheduling an instruction.
virtual void schedNode(SUnit *SU, bool IsTopNode)=0
SmallVector< SDep, 4 > Preds
virtual void startBlock(MachineBasicBlock *BB)
startBlock - Prepare to perform scheduling in the given block.
LoopInfoBase< BlockT, LoopT > * LI
MachineBasicBlock::const_iterator getPos() const
Get the MI position corresponding to this register pressure.
const RegPressureTracker & getTopRPTracker() const
A register anti-dependedence (aka WAR).
static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *Graph)
iterator_base< SparseMultiSet * > iterator
const TargetSchedModel * getSchedModel() const
Get the machine model for instruction scheduling.
unsigned NumInstrsScheduled
static const SCEV * apply(const SCEV *Scev, LoopToScevMapT &Map, ScalarEvolution &SE)
Applies the Map (Loop -> SCEV) to the given Scev.
unsigned getNumSubtrees() const
The number of subtrees detected in this DAG.
unsigned getHeight() const
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
void clear()
clear - Clear all bits.
void viewGraph() LLVM_OVERRIDE
Out-of-line implementation with no arguments is handy for gdb.
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
BitVector & getScheduledTrees()
void closeBottom()
Set the boundary for the bottom of the region and summarize live outs.
Provide an instruction scheduling machine model to CodeGen passes.
const HexagonInstrInfo * TII
static std::string getEdgeAttributes(const SUnit *Node, SUnitIterator EI, const ScheduleDAG *Graph)
static MachineSchedRegistry DefaultSchedRegistry("default","Use the target's default scheduler choice.", useDefaultMachineSched)
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.
#define llvm_unreachable(msg)
virtual const char * getRegPressureSetName(unsigned Idx) const =0
Get the name of this register unit pressure set.
static unsigned getWeakLeft(const SUnit *SU, bool isTop)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Regular data dependence (aka true-dependence).
bool mayLoad(QueryType Type=AnyInBundle) const
void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs) LLVM_OVERRIDE
static void tracePick(const GenericScheduler::SchedCandidate &Cand, bool IsTop)
void InitDAGTopologicalSorting()
ID
LLVM Calling Convention Representation.
static MachineSchedRegistry ShufflerRegistry("shuffle","Shuffle machine instructions alternating directions", createInstructionShuffler)
bool recede(SmallVectorImpl< unsigned > *LiveUses=0, PressureDiff *PDiff=0)
Recede across the previous instruction.
Compute the values of each DAG node for various metrics during DFS.
static cl::opt< bool > VerifyScheduling("verify-misched", cl::Hidden, cl::desc("Verify machine instrs before and after machine scheduling"))
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.
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
reverse_iterator rbegin() const
static std::string getGraphName(const ScheduleDAG *G)
virtual void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs)
Optionally override the per-region scheduling policy.
COFF::MachineTypes Machine
bool isTrackingPressure() const
Return true if register pressure tracking is enabled.
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the scheduler state for the next scheduling region.
size_t size() const
size - Get the array size.
virtual bool enableClusterLoads() const
static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G)
virtual void registerRoots()
static cl::opt< bool > EnableLoadCluster("misched-cluster", cl::Hidden, cl::desc("Enable load clustering."), cl::init(true))
void resize(unsigned NumSUnits)
Initialize the result data with the size of the DAG.
std::vector< SUnit * >::iterator iterator
static bool tryLess(int TryVal, int CandVal, GenericScheduler::SchedCandidate &TryCand, GenericScheduler::SchedCandidate &Cand, GenericScheduler::CandReason Reason)
Return true if this heuristic determines order.
MachineSchedStrategy * SchedImpl
reverse_iterator rend() const
RegisterClassInfo * RegClassInfo
bundle_iterator< MachineInstr, instr_iterator > iterator
void getMaxDownwardPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
virtual void overrideSchedPolicy(MachineSchedPolicy &Policy, MachineInstr *begin, MachineInstr *end, unsigned NumRegionInstrs) const
Override generic scheduling policy within a region.
initializer< Ty > init(const Ty &Val)
std::vector< ScheduleDAGMutation * > Mutations
Ordered list of DAG postprocessing steps.
LiveQueryResult Query(SlotIndex Idx) const
ArrayRef< unsigned > getLiveThru() const
void updatePressureDiffs(ArrayRef< unsigned > LiveUses)
const InstrItineraryData * getInstrItineraries() const
static const unsigned MinSubtreeSize
static void initialize(TargetLibraryInfo &TLI, const Triple &T, const char **StandardNames)
void dumpSchedule() const
dump the scheduled Sequence.
const MachineOperand & getOperand(unsigned i) const
unsigned getLatencyFactor() const
Multiply cycle count by this factor to normalize it relative to other resources. This is the number o...
PressureDiff & getPressureDiff(const SUnit *SU)
bool addEdge(SUnit *SuccSU, const SDep &PredDep)
Add a DAG edge to the given SU with the given predecessor dependence data.
ItTy next(ItTy it, Dist n)
static MachinePassRegistry Registry
void releasePred(SUnit *SU, SDep *PredEdge)
virtual void releaseBottomNode(SUnit *SU)=0
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
SmallVector< unsigned, 8 > LiveOutRegs
static ScheduleDAGInstrs * useDefaultMachineSched(MachineSchedContext *C)
virtual void exitRegion()
Notify that the scheduler has finished scheduling the current region.
void updateScheduledPressure(const SUnit *SU, const std::vector< unsigned > &NewMaxPressure)
unsigned getRegPressureSetLimit(unsigned Idx) const
void ViewGraph(const GraphType &G, const Twine &Name, bool ShortNames=false, const Twine &Title="", GraphProgram::Name Program=GraphProgram::DOT)
DOTGraphTraits(bool isSimple=false)
void dumpRegSetPressure(ArrayRef< unsigned > SetPressure, const TargetRegisterInfo *TRI)
unsigned getNumProcResourceKinds() const
Get the number of kinds of resources for this target.
static MachineBasicBlock::const_iterator nextIfDebug(MachineBasicBlock::const_iterator I, MachineBasicBlock::const_iterator End)
#define INITIALIZE_AG_DEPENDENCY(depName)
LiveIntervals * getLIS() const
Expose LiveIntervals for use in DAG mutators and such.
static cl::opt< bool > EnableMacroFusion("misched-fusion", cl::Hidden, cl::desc("Enable scheduling for macro fusion."), cl::init(true))
Machine Instruction false
void releaseSuccessors(SUnit *SU)
releaseSuccessors - Call releaseSucc on each of SU's successors.
const SUnit * NextClusterSucc
void initLiveThru(const RegPressureTracker &RPTracker)
void scheduleMI(SUnit *SU, bool IsTopNode)
Move an instruction and update register pressure.
static cl::opt< bool > EnableRegPressure("misched-regpressure", cl::Hidden, cl::desc("Enable register pressure scheduling."), cl::init(true))
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
iterator find(const KeyT &Key)
MachineBasicBlock::iterator LiveRegionEnd
iterator find(SlotIndex Pos)
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model. ...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
std::vector< unsigned > MaxSetPressure
Map of max reg pressure indexed by pressure set ID, not class ID.
virtual const TargetInstrInfo * getInstrInfo() const
static MachineSchedRegistry GenericSchedRegistry("converge","Standard converging scheduler.", createGenericSched)
const STC & getSubtarget() const
const SUnit * NextClusterPred
Record the next node in a scheduled cluster.
const MCProcResourceDesc * getProcResource(unsigned PIdx) const
Get a processor resource by ID for convenience.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
void compute(ArrayRef< SUnit > SUnits)
Compute various metrics for the DAG with given roots.
AnalysisUsage & addRequiredID(const void *ID)
ScheduleDAGInstrs *(* ScheduleDAGCtor)(MachineSchedContext *)
unsigned computeCyclicCriticalPath()
Compute the cyclic critical path through the DAG.
static cl::opt< unsigned > MISchedCutoff("misched-cutoff", cl::Hidden, cl::desc("Stop scheduling after N instructions"), cl::init(~0U))
static ScheduleDAGInstrs * createILPMinScheduler(MachineSchedContext *C)
bool test(unsigned Idx) const
bool isCtrlDep() const
isCtrlDep - Test if this is not an SDep::Data dependence.
std::reverse_iterator< const_iterator > const_reverse_iterator
bool isSuccessor(const MachineBasicBlock *MBB) const
const std::vector< PressureChange > & getRegionCriticalPSets() const
StringRef getColorString(unsigned NodeNumber)
Get a color string for this node number. Simply round-robin selects from a reasonable number of color...
LiveInterval & getInterval(unsigned Reg)
PressureDiffs SUPressureDiffs
static cl::opt< bool > EnableCyclicPath("misched-cyclicpath", cl::Hidden, cl::desc("Enable cyclic critical path analysis."), cl::init(true))
void initializeMachineSchedulerPass(PassRegistry &)
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
virtual void finalizeSchedule()
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
IsReachable - Checks if SU is reachable from TargetSU.
void biasCriticalPath()
Order this node's predecessor edges such that the critical path edge occurs first.
virtual void schedule()=0
ILPValue getILP(const SUnit *SU) const
Get the ILP value for a DAG node.
virtual const TargetRegisterClass * getRegClassFor(MVT VT) const
MachineBasicBlock::iterator bottom() const
void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos)
MachineBasicBlock::iterator end() const
end - Return an iterator to the bottom of the current scheduling region.
static bool tryGreater(int TryVal, int CandVal, GenericScheduler::SchedCandidate &TryCand, GenericScheduler::SchedCandidate &Cand, GenericScheduler::CandReason Reason)
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
unsigned getDepth() const
const SUnit * getNextClusterSucc() const
virtual void scheduleTree(unsigned SubtreeID)
Scheduler callback to notify that a new subtree is scheduled.
void init(const MachineFunction *mf, const RegisterClassInfo *rci, const LiveIntervals *lis, const MachineBasicBlock *mbb, MachineBasicBlock::const_iterator pos, bool ShouldTrackUntiedDefs=false)
void closeTop()
Set the boundary for the top of the region and summarize live ins.
RegPressureTracker BotRPTracker
void releasePredecessors(SUnit *SU)
releasePredecessors - Call releasePred on each of SU's predecessors.
unsigned getSubtreeID(const SUnit *SU) const
Get the ID of the subtree the given DAG node belongs to.
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
SUnit * getSUnit(MachineInstr *MI) const
getSUnit - Return an existing SUnit for this MI, or NULL.
virtual SUnit * pickNode(bool &IsTopNode)=0
bool operator!=(uint64_t V1, const APInt &V2)
bundle_iterator< const MachineInstr, const_instr_iterator > const_iterator
RegPressureTracker RPTracker
static bool isPhysicalRegister(unsigned Reg)
const TargetRegisterInfo * TRI
INITIALIZE_PASS_BEGIN(MachineScheduler,"misched","Machine Instruction Scheduler", false, false) INITIALIZE_PASS_END(MachineScheduler
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
cl::opt< bool > ForceBottomUp
virtual void getAnalysisUsage(AnalysisUsage &AU) const
SlotIndex endIndex() const
unsigned getNumInstrs(const SUnit *SU) const
Get the number of instructions in the given subtree and its children.
static bool tryPressure(const PressureChange &TryP, const PressureChange &CandP, GenericScheduler::SchedCandidate &TryCand, GenericScheduler::SchedCandidate &Cand, GenericScheduler::CandReason Reason)
void getMaxUpwardPressureDelta(const MachineInstr *MI, PressureDiff *PDiff, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
const TargetMachine & getTarget() const
static bool hasNodeAddressLabel(const SUnit *Node, const ScheduleDAG *Graph)
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
RegisterClassInfo * RegClassInfo
static bool tryLatency(GenericScheduler::SchedCandidate &TryCand, GenericScheduler::SchedCandidate &Cand, GenericScheduler::SchedBoundary &Zone)
SchedDFSResult * DFSResult
const TargetInstrInfo * TII
static bool isNodeHidden(const SUnit *Node)
std::vector< PressureChange > RegionCriticalPSets
unsigned getPSetOrMax() const
unsigned getReg() const
getReg - Returns the register number.
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
void addLiveRegs(ArrayRef< unsigned > Regs)
Force liveness of registers.
bool addPred(const SDep &D, bool Required=true)
void initQueues(ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)
Release ExitSU predecessors and setup scheduler queues.
unsigned getMicroOpFactor() const
Multiply number of micro-ops by this factor to normalize it relative to other resources.
void postprocessDAG()
Apply each ScheduleDAGMutation step in order.
bool ShouldTrackPressure
Register pressure in this region computed by initRegPressure.
SmallVector< SDep, 4 > Succs
unsigned getIssueWidth() const
Maximum number of micro-ops that may be scheduled per cycle.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction associated with the given index.
RegPressureTracker TopRPTracker
bool isBottomReady() const
SmallVector< unsigned, 8 > LiveInRegs
List of live in virtual registers or physical register units.
static MachineSchedRegistry ILPMinRegistry("ilpmin","Schedule bottom-up for min ILP", createILPMinScheduler)
Arbitrary strong DAG edge (no real dependence).
void scheduleTree(unsigned SubtreeID)
Scheduler callback to update SubtreeConnectLevels when a tree is initially scheduled.
BasicBlockListType::iterator iterator
const SUnit * getNextClusterPred() const
ItTy prior(ItTy it, Dist n)
void AddPred(SUnit *Y, SUnit *X)
MachineInstr * FirstDbgValue
Machine Instruction Scheduler
MachineBasicBlock * BB
The block in which to insert instructions.
bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)
True if an edge can be added from PredSU to SuccSU without creating a cycle.
const RegPressureTracker & getBotRPTracker() const
void setPos(MachineBasicBlock::const_iterator Pos)
bool operator==(uint64_t V1, const APInt &V2)
StringRef getName() const
RegisterPressure & getPressure()
MachineRegisterInfo & MRI
std::vector< SUnit > SUnits
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
SlotIndex - An opaque wrapper around machine indexes.
void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker=0, PressureDiffs *PDiffs=0)
const SchedDFSResult * getDFSResult() const
Return a non-null DFS result if the scheduling strategy initialized it.
void dump(const ScheduleDAG *G) const
void getUpwardPressureDelta(const MachineInstr *MI, PressureDiff &PDiff, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit) const
VNInfo * getVNInfoBefore(SlotIndex Idx) const
SUnit - Scheduling unit. This is a node in the scheduling DAG.
cl::opt< bool > ForceTopDown