38 #include "llvm/Config/llvm-config.h" 62 #define DEBUG_TYPE "pre-RA-sched" 64 STATISTIC(NumBacktracks,
"Number of times scheduler backtracked");
65 STATISTIC(NumUnfolds,
"Number of nodes unfolded");
66 STATISTIC(NumDups,
"Number of duplicated nodes");
67 STATISTIC(NumPRCopies,
"Number of physical register copies");
71 "Bottom-up register reduction list scheduling",
76 "Similar to list-burr but schedules in source " 77 "order when possible",
82 "Bottom-up register pressure aware list scheduling " 83 "which tries to balance latency and register pressure",
88 "Bottom-up register pressure aware list scheduling " 89 "which tries to balance ILP and register pressure",
94 cl::desc(
"Disable cycle-level precision during preRA scheduling"));
100 cl::desc(
"Disable regpressure priority in sched=list-ilp"));
103 cl::desc(
"Disable live use priority in sched=list-ilp"));
106 cl::desc(
"Disable virtual register cycle interference checks"));
109 cl::desc(
"Disable physreg def-use affinity"));
112 cl::desc(
"Disable no-stall priority in sched=list-ilp"));
115 cl::desc(
"Disable critical path priority in sched=list-ilp"));
118 cl::desc(
"Disable scheduled-height priority in sched=list-ilp"));
121 cl::desc(
"Disable scheduler's two-address hack"));
125 cl::desc(
"Number of instructions to allow ahead of the critical path " 126 "in sched=list-ilp"));
130 cl::desc(
"Average inst/cycle whan no target itinerary exists."));
150 std::vector<SUnit *> PendingQueue;
156 unsigned CurCycle = 0;
159 unsigned MinAvailableCycle;
168 unsigned NumLiveRegs;
169 std::unique_ptr<SUnit*[]> LiveRegDefs;
170 std::unique_ptr<SUnit*[]> LiveRegGens;
193 NeedLatency(needlatency), AvailableQueue(availqueue),
194 Topo(SUnits, nullptr) {
202 ~ScheduleDAGRRList()
override {
204 delete AvailableQueue;
207 void Schedule()
override;
212 bool IsReachable(
const SUnit *SU,
const SUnit *TargetSU) {
218 bool WillCreateCycle(
SUnit *SU,
SUnit *TargetSU) {
225 void AddPredQueued(
SUnit *SU,
const SDep &
D) {
241 void RemovePred(
SUnit *SU,
const SDep &D) {
247 bool isReady(
SUnit *SU) {
252 void ReleasePred(
SUnit *SU,
const SDep *PredEdge);
253 void ReleasePredecessors(
SUnit *SU);
254 void ReleasePending();
255 void AdvanceToCycle(
unsigned NextCycle);
256 void AdvancePastStalls(
SUnit *SU);
257 void EmitNode(
SUnit *SU);
258 void ScheduleNodeBottomUp(
SUnit*);
259 void CapturePred(
SDep *PredEdge);
260 void UnscheduleNodeBottomUp(
SUnit*);
261 void RestoreHazardCheckerBottomUp();
265 void InsertCopiesAndMoveSuccs(
SUnit*,
unsigned,
271 void releaseInterferences(
unsigned Reg = 0);
273 SUnit *PickNodeToScheduleBottomUp();
274 void ListScheduleBottomUp();
278 unsigned NumSUnits = SUnits.size();
279 SUnit *NewNode = newSUnit(N);
281 if (NewNode->
NodeNum >= NumSUnits)
288 unsigned NumSUnits = SUnits.size();
289 SUnit *NewNode = Clone(N);
291 if (NewNode->
NodeNum >= NumSUnits)
298 bool forceUnitLatencies()
const override {
313 unsigned &RegClass,
unsigned &Cost,
326 RegClass = RC->
getID();
332 if (Opcode == TargetOpcode::REG_SEQUENCE) {
333 unsigned DstRCIdx = cast<ConstantSDNode>(Node->
getOperand(0))->getZExtValue();
335 RegClass = RC->
getID();
340 unsigned Idx = RegDefPos.
GetIdx();
343 RegClass = RC->
getID();
354 void ScheduleDAGRRList::Schedule() {
356 <<
" '" << BB->getName() <<
"' **********\n");
365 LiveRegDefs.reset(
new SUnit*[
TRI->getNumRegs() + 1]());
366 LiveRegGens.reset(
new SUnit*[
TRI->getNumRegs() + 1]());
367 CallSeqEndForStart.
clear();
368 assert(Interferences.
empty() && LRegsMap.empty() &&
"stale Interferences");
371 BuildSchedGraph(
nullptr);
381 ListScheduleBottomUp();
386 dbgs() <<
"*** Final schedule ***\n";
398 void ScheduleDAGRRList::ReleasePred(
SUnit *SU,
const SDep *PredEdge) {
403 dbgs() <<
"*** Scheduling failed! ***\n";
405 dbgs() <<
" has been released too many times!\n";
411 if (!forceUnitLatencies()) {
423 if (Height < MinAvailableCycle)
424 MinAvailableCycle = Height;
426 if (isReady(PredSU)) {
427 AvailableQueue->
push(PredSU);
433 PendingQueue.push_back(PredSU);
470 goto found_chain_operand;
473 found_chain_operand:;
497 unsigned BestMaxNest = MaxNest;
499 unsigned MyNestLevel = NestLevel;
500 unsigned MyMaxNest = MaxNest;
502 MyNestLevel, MyMaxNest,
TII))
503 if (!Best || (MyMaxNest > BestMaxNest)) {
505 BestMaxNest = MyMaxNest;
509 MaxNest = BestMaxNest;
516 MaxNest =
std::max(MaxNest, NestLevel);
528 goto found_chain_operand;
531 found_chain_operand:;
554 void ScheduleDAGRRList::ReleasePredecessors(
SUnit *SU) {
557 ReleasePred(SU, &Pred);
563 SUnit *RegDef = LiveRegDefs[Pred.
getReg()]; (void)RegDef;
565 "interference on register dependence");
567 if (!LiveRegGens[Pred.
getReg()]) {
569 LiveRegGens[Pred.
getReg()] = SU;
577 unsigned CallResource =
TRI->getNumRegs();
578 if (!LiveRegDefs[CallResource])
579 for (
SDNode *Node = SU->
getNode(); Node; Node = Node->getGluedNode())
580 if (Node->isMachineOpcode() &&
581 Node->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
582 unsigned NestLevel = 0;
583 unsigned MaxNest = 0;
585 assert(N &&
"Must find call sequence start");
588 CallSeqEndForStart[
Def] = SU;
591 LiveRegDefs[CallResource] =
Def;
592 LiveRegGens[CallResource] = SU;
599 void ScheduleDAGRRList::ReleasePending() {
601 assert(PendingQueue.empty() &&
"pending instrs not allowed in this mode");
606 if (AvailableQueue->
empty())
611 for (
unsigned i = 0,
e = PendingQueue.size(); i !=
e; ++i) {
612 unsigned ReadyCycle = PendingQueue[i]->getHeight();
613 if (ReadyCycle < MinAvailableCycle)
614 MinAvailableCycle = ReadyCycle;
617 if (!isReady(PendingQueue[i]))
619 AvailableQueue->
push(PendingQueue[i]);
621 PendingQueue[i]->isPending =
false;
622 PendingQueue[i] = PendingQueue.back();
623 PendingQueue.pop_back();
629 void ScheduleDAGRRList::AdvanceToCycle(
unsigned NextCycle) {
630 if (NextCycle <= CurCycle)
637 CurCycle = NextCycle;
640 for (; CurCycle != NextCycle; ++CurCycle) {
651 void ScheduleDAGRRList::AdvancePastStalls(
SUnit *SU) {
668 AdvanceToCycle(ReadyCycle);
688 AdvanceToCycle(CurCycle + Stalls);
693 void ScheduleDAGRRList::EmitNode(
SUnit *SU) {
704 "This target-independent node should not be scheduled.");
736 void ScheduleDAGRRList::ScheduleNodeBottomUp(
SUnit *SU) {
741 if (CurCycle < SU->getHeight())
743 <<
"] pipeline stall!\n");
763 AdvanceToCycle(CurCycle + 1);
767 ReleasePredecessors(SU);
773 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
775 LiveRegDefs[Succ.
getReg()] =
nullptr;
776 LiveRegGens[Succ.
getReg()] =
nullptr;
777 releaseInterferences(Succ.
getReg());
782 unsigned CallResource =
TRI->getNumRegs();
783 if (LiveRegDefs[CallResource] == SU)
786 if (SUNode->isMachineOpcode() &&
787 SUNode->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
788 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
790 LiveRegDefs[CallResource] =
nullptr;
791 LiveRegGens[CallResource] =
nullptr;
792 releaseInterferences(CallResource);
813 AdvanceToCycle(CurCycle + 1);
820 void ScheduleDAGRRList::CapturePred(
SDep *PredEdge) {
825 AvailableQueue->
remove(PredSU);
829 "NumSuccsLeft will overflow!");
835 void ScheduleDAGRRList::UnscheduleNodeBottomUp(
SUnit *SU) {
842 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
844 "Physical register dependency violated?");
846 LiveRegDefs[Pred.
getReg()] =
nullptr;
847 LiveRegGens[Pred.
getReg()] =
nullptr;
848 releaseInterferences(Pred.
getReg());
854 unsigned CallResource =
TRI->getNumRegs();
857 if (SUNode->isMachineOpcode() &&
858 SUNode->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
859 SUnit *SeqEnd = CallSeqEndForStart[SU];
860 assert(SeqEnd &&
"Call sequence start/end must be known");
861 assert(!LiveRegDefs[CallResource]);
862 assert(!LiveRegGens[CallResource]);
864 LiveRegDefs[CallResource] = SU;
865 LiveRegGens[CallResource] = SeqEnd;
871 if (LiveRegGens[CallResource] == SU)
874 if (SUNode->isMachineOpcode() &&
875 SUNode->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
876 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
877 assert(LiveRegDefs[CallResource]);
878 assert(LiveRegGens[CallResource]);
880 LiveRegDefs[CallResource] =
nullptr;
881 LiveRegGens[CallResource] =
nullptr;
882 releaseInterferences(CallResource);
886 for (
auto &Succ : SU->
Succs) {
887 if (Succ.isAssignedRegDep()) {
888 auto Reg = Succ.getReg();
889 if (!LiveRegDefs[
Reg])
893 LiveRegDefs[
Reg] = SU;
897 if (!LiveRegGens[Reg]) {
899 LiveRegGens[
Reg] = Succ.getSUnit();
900 for (
auto &Succ2 : SU->
Succs) {
901 if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
902 Succ2.getSUnit()->getHeight() < LiveRegGens[
Reg]->getHeight())
903 LiveRegGens[Reg] = Succ2.getSUnit();
917 PendingQueue.push_back(SU);
920 AvailableQueue->
push(SU);
927 void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {
930 unsigned LookAhead = std::min((
unsigned)
Sequence.size(),
935 std::vector<SUnit *>::const_iterator
I = (
Sequence.end() - LookAhead);
936 unsigned HazardCycle = (*I)->getHeight();
939 for (; SU->
getHeight() > HazardCycle; ++HazardCycle) {
948 void ScheduleDAGRRList::BacktrackBottomUp(
SUnit *SU,
SUnit *BtSU) {
954 UnscheduleNodeBottomUp(OldSU);
963 RestoreHazardCheckerBottomUp();
973 if (SUNode->isOperandOf(N))
980 SUnit *ScheduleDAGRRList::TryUnfoldSU(
SUnit *SU) {
984 if (!
TII->unfoldMemoryOperand(*DAG, N, NewNodes))
989 if (NewNodes.
size() == 3)
992 assert(NewNodes.
size() == 2 &&
"Expected a load folding node!");
995 SDNode *LoadNode = NewNodes[0];
996 unsigned NumVals = N->getNumValues();
1002 bool isNewLoad =
true;
1005 LoadSU = &SUnits[LoadNode->
getNodeId()];
1012 LoadSU = CreateNewSUnit(LoadNode);
1015 InitNumRegDefsLeft(LoadSU);
1016 computeLatency(LoadSU);
1022 if (N->getNodeId() != -1) {
1023 NewSU = &SUnits[N->getNodeId()];
1031 NewSU = CreateNewSUnit(N);
1044 InitNumRegDefsLeft(NewSU);
1045 computeLatency(NewSU);
1051 for (
unsigned i = 0; i != NumVals; ++i)
1053 DAG->ReplaceAllUsesOfValueWith(
SDValue(SU->
getNode(), OldNumVals - 1),
1078 for (
const SDep &Pred : ChainPreds) {
1079 RemovePred(SU, Pred);
1081 AddPredQueued(LoadSU, Pred);
1083 for (
const SDep &Pred : LoadPreds) {
1084 RemovePred(SU, Pred);
1086 AddPredQueued(LoadSU, Pred);
1088 for (
const SDep &Pred : NodePreds) {
1089 RemovePred(SU, Pred);
1090 AddPredQueued(NewSU, Pred);
1092 for (
SDep D : NodeSuccs) {
1095 RemovePred(SuccDep, D);
1097 AddPredQueued(SuccDep, D);
1103 for (
SDep D : ChainSuccs) {
1106 RemovePred(SuccDep, D);
1109 AddPredQueued(SuccDep, D);
1117 AddPredQueued(NewSU, D);
1120 AvailableQueue->
addNode(LoadSU);
1122 AvailableQueue->
addNode(NewSU);
1134 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(
SUnit *SU) {
1143 !
TII->canCopyGluedNodeDuringSchedule(N)) {
1146 <<
"Giving up because it has incoming glue and the target does not " 1147 "want to copy it\n");
1152 bool TryUnfold =
false;
1156 LLVM_DEBUG(
dbgs() <<
"Giving up because it has outgoing glue\n");
1162 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
1163 if (VT ==
MVT::Glue && !
TII->canCopyGluedNodeDuringSchedule(N)) {
1165 dbgs() <<
"Giving up because it one of the operands is glue and " 1166 "the target does not want to copy it\n");
1173 SUnit *UnfoldSU = TryUnfoldSU(SU);
1184 NewSU = CreateClone(SU);
1189 AddPredQueued(NewSU, Pred);
1205 AddPredQueued(SuccSU, D);
1207 DelDeps.
push_back(std::make_pair(SuccSU, D));
1210 for (
auto &DelDep : DelDeps)
1211 RemovePred(DelDep.first, DelDep.second);
1214 AvailableQueue->
addNode(NewSU);
1222 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(
SUnit *SU,
unsigned Reg,
1226 SUnit *CopyFromSU = CreateNewSUnit(
nullptr);
1230 SUnit *CopyToSU = CreateNewSUnit(
nullptr);
1244 AddPredQueued(SuccSU, D);
1245 DelDeps.
push_back(std::make_pair(SuccSU, Succ));
1254 for (
auto &DelDep : DelDeps)
1255 RemovePred(DelDep.first, DelDep.second);
1259 AddPredQueued(CopyFromSU, FromDep);
1262 AddPredQueued(CopyToSU, ToDep);
1265 AvailableQueue->
addNode(CopyFromSU);
1266 AvailableQueue->
addNode(CopyToSU);
1298 SUnit **LiveRegDefs,
1305 if (!LiveRegDefs[*AliasI])
continue;
1308 if (LiveRegDefs[*AliasI] == SU)
continue;
1311 if (RegAdded.
insert(*AliasI).second) {
1324 for (
unsigned i = 1,
e = LiveRegDefs.
size()-1; i !=
e; ++i) {
1325 if (!LiveRegDefs[i])
continue;
1326 if (LiveRegDefs[i] == SU)
continue;
1328 if (RegAdded.
insert(i).second)
1336 if (
const auto *RegOp = dyn_cast<RegisterMaskSDNode>(
Op.getNode()))
1337 return RegOp->getRegMask();
1345 bool ScheduleDAGRRList::
1347 if (NumLiveRegs == 0)
1358 RegAdded, LRegs,
TRI);
1361 for (
SDNode *Node = SU->
getNode(); Node; Node = Node->getGluedNode()) {
1365 unsigned NumOps = Node->getNumOperands();
1366 if (Node->getOperand(NumOps-1).getValueType() ==
MVT::Glue)
1371 cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
1379 for (; NumVals; --NumVals, ++i) {
1380 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->
getReg();
1390 if (!Node->isMachineOpcode())
1395 if (Node->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
1397 unsigned CallResource =
TRI->getNumRegs();
1398 if (LiveRegDefs[CallResource]) {
1399 SDNode *Gen = LiveRegGens[CallResource]->getNode();
1403 RegAdded.
insert(CallResource).second)
1418 for (
unsigned i = 0; i < MCID.
getNumDefs(); ++i)
1431 return !LRegs.
empty();
1434 void ScheduleDAGRRList::releaseInterferences(
unsigned Reg) {
1436 for (
unsigned i = Interferences.
size(); i > 0; --i) {
1437 SUnit *SU = Interferences[i-1];
1438 LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);
1450 AvailableQueue->
push(SU);
1452 if (i < Interferences.
size())
1453 Interferences[i-1] = Interferences.
back();
1455 LRegsMap.erase(LRegsPos);
1463 SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
1464 SUnit *CurSU = AvailableQueue->
empty() ? nullptr : AvailableQueue->
pop();
1465 auto FindAvailableNode = [&]() {
1468 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
1471 if (LRegs[0] ==
TRI->getNumRegs())
dbgs() <<
"CallResource";
1474 std::pair<LRegsMapT::iterator, bool> LRegsPair =
1475 LRegsMap.insert(std::make_pair(CurSU, LRegs));
1476 if (LRegsPair.second) {
1483 LRegsPair.first->second = LRegs;
1485 CurSU = AvailableQueue->
pop();
1488 FindAvailableNode();
1500 for (
SUnit *TrySU : Interferences) {
1505 SUnit *BtSU =
nullptr;
1507 for (
unsigned Reg : LRegs) {
1508 if (LiveRegGens[Reg]->getHeight() < LiveCycle) {
1509 BtSU = LiveRegGens[
Reg];
1513 if (!WillCreateCycle(TrySU, BtSU)) {
1515 BacktrackBottomUp(TrySU, BtSU);
1522 AvailableQueue->
remove(BtSU);
1525 <<
") to SU(" << TrySU->NodeNum <<
")\n");
1530 if (!TrySU->isAvailable || !TrySU->NodeQueueId) {
1531 LLVM_DEBUG(
dbgs() <<
"TrySU not available; choosing node from queue\n");
1532 CurSU = AvailableQueue->
pop();
1536 AvailableQueue->
remove(TrySU);
1539 FindAvailableNode();
1551 SUnit *TrySU = Interferences[0];
1553 assert(LRegs.
size() == 1 &&
"Can't handle this yet!");
1554 unsigned Reg = LRegs[0];
1558 TRI->getMinimalPhysRegClass(Reg, VT);
1568 SUnit *NewDef =
nullptr;
1570 NewDef = CopyAndMoveSuccessors(LRDef);
1571 if (!DestRC && !NewDef)
1577 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
1579 <<
" to SU #" << Copies.
front()->NodeNum <<
"\n");
1581 NewDef = Copies.
back();
1585 <<
" to SU #" << TrySU->
NodeNum <<
"\n");
1586 LiveRegDefs[
Reg] = NewDef;
1591 assert(CurSU &&
"Unable to resolve live physical register dependencies!");
1597 void ScheduleDAGRRList::ListScheduleBottomUp() {
1599 ReleasePredecessors(&ExitSU);
1602 if (!SUnits.empty()) {
1603 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
1604 assert(RootSU->
Succs.empty() &&
"Graph root shouldn't have successors!");
1606 AvailableQueue->
push(RootSU);
1612 while (!AvailableQueue->
empty() || !Interferences.
empty()) {
1614 AvailableQueue->
dump(
this));
1618 SUnit *SU = PickNodeToScheduleBottomUp();
1620 AdvancePastStalls(SU);
1622 ScheduleNodeBottomUp(SU);
1624 while (AvailableQueue->
empty() && !PendingQueue.empty()) {
1627 "MinAvailableCycle uninitialized");
1628 AdvanceToCycle(
std::max(CurCycle + 1, MinAvailableCycle));
1636 VerifyScheduledSequence(
true);
1642 class RegReductionPQBase;
1645 bool isReady(
SUnit* SU,
unsigned CurCycle)
const {
return true; }
1650 struct reverse_sort :
public queue_sort {
1653 reverse_sort(SF &sf) : SortFunc(sf) {}
1655 bool operator()(
SUnit* left,
SUnit* right)
const {
1658 return SortFunc(right, left);
1665 struct bu_ls_rr_sort :
public queue_sort {
1668 HasReadyFilter =
false 1671 RegReductionPQBase *SPQ;
1673 bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1675 bool operator()(
SUnit* left,
SUnit* right)
const;
1679 struct src_ls_rr_sort :
public queue_sort {
1682 HasReadyFilter =
false 1685 RegReductionPQBase *SPQ;
1687 src_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1689 bool operator()(
SUnit* left,
SUnit* right)
const;
1693 struct hybrid_ls_rr_sort :
public queue_sort {
1696 HasReadyFilter =
false 1699 RegReductionPQBase *SPQ;
1701 hybrid_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1703 bool isReady(
SUnit *SU,
unsigned CurCycle)
const;
1705 bool operator()(
SUnit* left,
SUnit* right)
const;
1710 struct ilp_ls_rr_sort :
public queue_sort {
1713 HasReadyFilter =
false 1716 RegReductionPQBase *SPQ;
1718 ilp_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1720 bool isReady(
SUnit *SU,
unsigned CurCycle)
const;
1722 bool operator()(
SUnit* left,
SUnit* right)
const;
1727 std::vector<SUnit *> Queue;
1728 unsigned CurQueueId = 0;
1729 bool TracksRegPressure;
1733 std::vector<SUnit> *SUnits;
1739 ScheduleDAGRRList *scheduleDAG =
nullptr;
1742 std::vector<unsigned> SethiUllmanNumbers;
1749 std::vector<unsigned> RegLimit;
1753 bool hasReadyFilter,
1760 SrcOrder(srcorder), MF(mf),
TII(tii),
TRI(tri), TLI(tli) {
1761 if (TracksRegPressure) {
1763 RegLimit.resize(NumRC);
1764 RegPressure.resize(NumRC);
1765 std::fill(RegLimit.begin(), RegLimit.end(), 0);
1766 std::fill(RegPressure.begin(), RegPressure.end(), 0);
1772 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1773 scheduleDAG = scheduleDag;
1777 return scheduleDAG->getHazardRec();
1780 void initNodes(std::vector<SUnit> &sunits)
override;
1782 void addNode(
const SUnit *SU)
override;
1784 void updateNode(
const SUnit *SU)
override;
1786 void releaseState()
override {
1788 SethiUllmanNumbers.clear();
1789 std::fill(RegPressure.begin(), RegPressure.end(), 0);
1792 unsigned getNodePriority(
const SUnit *SU)
const;
1794 unsigned getNodeOrdering(
const SUnit *SU)
const {
1800 bool empty()
const override {
return Queue.empty(); }
1808 void remove(
SUnit *SU)
override {
1809 assert(!Queue.empty() &&
"Queue is empty!");
1811 std::vector<SUnit *>::iterator
I =
llvm::find(Queue, SU);
1812 if (I != std::prev(Queue.end()))
1818 bool tracksRegPressure()
const override {
return TracksRegPressure; }
1820 void dumpRegPressure()
const;
1822 bool HighRegPressure(
const SUnit *SU)
const;
1824 bool MayReduceRegPressure(
SUnit *SU)
const;
1826 int RegPressureDiff(
SUnit *SU,
unsigned &LiveUses)
const;
1828 void scheduledNode(
SUnit *SU)
override;
1830 void unscheduledNode(
SUnit *SU)
override;
1834 void AddPseudoTwoAddrDeps();
1835 void PrescheduleNodesWithMultipleUses();
1836 void CalculateSethiUllmanNumbers();
1840 static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1841 std::vector<SUnit *>::iterator Best = Q.begin();
1842 for (
auto I = std::next(Q.begin()),
E = Q.end();
I !=
E; ++
I)
1843 if (Picker(*Best, *
I))
1846 if (Best != std::prev(Q.end()))
1853 SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker,
ScheduleDAG *DAG) {
1856 reverse_sort<SF> RPicker(Picker);
1857 return popFromQueueImpl(Q, RPicker);
1861 return popFromQueueImpl(Q, Picker);
1872 class RegReductionPriorityQueue :
public RegReductionPQBase {
1882 : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
1886 bool isBottomUp()
const override {
return SF::IsBottomUp; }
1888 bool isReady(
SUnit *U)
const override {
1889 return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
1892 SUnit *pop()
override {
1893 if (Queue.empty())
return nullptr;
1895 SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1900 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1903 std::vector<SUnit *> DumpQueue = Queue;
1904 SF DumpPicker = Picker;
1905 while (!DumpQueue.empty()) {
1906 SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
1914 using BURegReductionPriorityQueue = RegReductionPriorityQueue<bu_ls_rr_sort>;
1915 using SrcRegReductionPriorityQueue = RegReductionPriorityQueue<src_ls_rr_sort>;
1916 using HybridBURRPriorityQueue = RegReductionPriorityQueue<hybrid_ls_rr_sort>;
1917 using ILPBURRPriorityQueue = RegReductionPriorityQueue<ilp_ls_rr_sort>;
1934 if (LSchedLow != RSchedLow)
1935 return LSchedLow < RSchedLow ? 1 : -1;
1943 if (SUNumbers[SU->
NodeNum] != 0)
1944 return SUNumbers[SU->
NodeNum];
1948 WorkState(
const SUnit *SU) : SU(SU) {}
1950 unsigned PredsProcessed = 0;
1955 while (!WorkList.
empty()) {
1956 auto &Temp = WorkList.
back();
1957 auto *TempSU = Temp.SU;
1958 bool AllPredsKnown =
true;
1960 for (
unsigned P = Temp.PredsProcessed; P < TempSU->Preds.size(); ++
P) {
1961 auto &Pred = TempSU->Preds[
P];
1962 if (Pred.isCtrl())
continue;
1963 SUnit *PredSU = Pred.getSUnit();
1964 if (SUNumbers[PredSU->
NodeNum] == 0) {
1967 for (
auto It : WorkList)
1968 assert(It.SU != PredSU &&
"Trying to push an element twice?");
1971 Temp.PredsProcessed =
P + 1;
1972 WorkList.push_back(PredSU);
1973 AllPredsKnown =
false;
1982 unsigned SethiUllmanNumber = 0;
1984 for (
const SDep &Pred : TempSU->Preds) {
1985 if (Pred.
isCtrl())
continue;
1987 unsigned PredSethiUllman = SUNumbers[PredSU->
NodeNum];
1988 assert(PredSethiUllman > 0 &&
"We should have evaluated this pred!");
1989 if (PredSethiUllman > SethiUllmanNumber) {
1990 SethiUllmanNumber = PredSethiUllman;
1992 }
else if (PredSethiUllman == SethiUllmanNumber)
1996 SethiUllmanNumber += Extra;
1997 if (SethiUllmanNumber == 0)
1998 SethiUllmanNumber = 1;
1999 SUNumbers[TempSU->NodeNum] = SethiUllmanNumber;
2003 assert(SUNumbers[SU->
NodeNum] > 0 &&
"SethiUllman should never be zero!");
2004 return SUNumbers[SU->
NodeNum];
2009 void RegReductionPQBase::CalculateSethiUllmanNumbers() {
2010 SethiUllmanNumbers.assign(SUnits->size(), 0);
2012 for (
const SUnit &SU : *SUnits)
2016 void RegReductionPQBase::addNode(
const SUnit *SU) {
2017 unsigned SUSize = SethiUllmanNumbers.size();
2018 if (SUnits->size() > SUSize)
2019 SethiUllmanNumbers.resize(SUSize*2, 0);
2023 void RegReductionPQBase::updateNode(
const SUnit *SU) {
2024 SethiUllmanNumbers[SU->
NodeNum] = 0;
2030 unsigned RegReductionPQBase::getNodePriority(
const SUnit *SU)
const {
2037 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2038 Opc == TargetOpcode::SUBREG_TO_REG ||
2039 Opc == TargetOpcode::INSERT_SUBREG)
2055 return SethiUllmanNumbers[SU->
NodeNum];
2057 unsigned Priority = SethiUllmanNumbers[SU->
NodeNum];
2061 return (NP > 0) ? NP : 0;
2071 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 2074 unsigned Id = RC->getID();
2078 << RegLimit[
Id] <<
'\n');
2083 bool RegReductionPQBase::HighRegPressure(
const SUnit *SU)
const {
2097 RegDefPos.
IsValid(); RegDefPos.Advance()) {
2098 unsigned RCId, Cost;
2108 bool RegReductionPQBase::MayReduceRegPressure(
SUnit *SU)
const {
2115 for (
unsigned i = 0; i != NumDefs; ++i) {
2119 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2133 int RegReductionPQBase::RegPressureDiff(
SUnit *SU,
unsigned &LiveUses)
const {
2148 RegDefPos.
IsValid(); RegDefPos.Advance()) {
2149 MVT VT = RegDefPos.GetValue();
2150 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2161 for (
unsigned i = 0; i != NumDefs; ++i) {
2165 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2172 void RegReductionPQBase::scheduledNode(
SUnit *SU) {
2173 if (!TracksRegPressure)
2206 RegDefPos.
IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2210 unsigned RCId, Cost;
2222 RegDefPos.
IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2223 if (SkipRegDefs > 0)
2225 unsigned RCId, Cost;
2231 <<
") has too many regdefs\n");
2241 void RegReductionPQBase::unscheduledNode(
SUnit *SU) {
2242 if (!TracksRegPressure)
2253 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2254 Opc == TargetOpcode::INSERT_SUBREG ||
2255 Opc == TargetOpcode::SUBREG_TO_REG ||
2256 Opc == TargetOpcode::REG_SEQUENCE ||
2257 Opc == TargetOpcode::IMPLICIT_DEF)
2273 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2274 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2279 if (POpc == TargetOpcode::IMPLICIT_DEF)
2281 if (POpc == TargetOpcode::EXTRACT_SUBREG ||
2282 POpc == TargetOpcode::INSERT_SUBREG ||
2283 POpc == TargetOpcode::SUBREG_TO_REG) {
2285 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2286 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2290 for (
unsigned i = 0; i != NumDefs; ++i) {
2294 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2295 if (
RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
2299 RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
2313 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2314 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2328 unsigned MaxHeight = 0;
2330 if (Succ.
isCtrl())
continue;
2337 if (Height > MaxHeight)
2346 unsigned Scratches = 0;
2348 if (Pred.
isCtrl())
continue;
2357 bool RetVal =
false;
2359 if (Pred.
isCtrl())
continue;
2379 bool RetVal =
false;
2381 if (Succ.
isCtrl())
continue;
2418 if (Pred.
isCtrl())
continue;
2430 if (Pred.
isCtrl())
continue;
2434 "VRegCycle def must be CopyFromReg");
2448 if (Pred.
isCtrl())
continue;
2462 if ((
int)SPQ->getCurCycle() < Height)
return true;
2463 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2472 RegReductionPQBase *SPQ) {
2477 int LHeight = (int)left->
getHeight() + LPenalty;
2478 int RHeight = (int)right->
getHeight() + RPenalty;
2491 if (LHeight != RHeight)
2492 return LHeight > RHeight ? 1 : -1;
2504 if (!SPQ->getHazardRec()->isEnabled()) {
2505 if (LHeight != RHeight)
2506 return LHeight > RHeight ? 1 : -1;
2508 int LDepth = left->
getDepth() - LPenalty;
2509 int RDepth = right->
getDepth() - RPenalty;
2510 if (LDepth != RDepth) {
2512 <<
") depth " << LDepth <<
" vs SU (" << right->
NodeNum 2513 <<
") depth " << RDepth <<
"\n");
2514 return LDepth < RDepth ? 1 : -1;
2530 if (LHasPhysReg != RHasPhysReg) {
2532 static const char *
const PhysRegMsg[] = {
" has no physreg",
2533 " defines a physreg" };
2536 << PhysRegMsg[LHasPhysReg] <<
" SU(" << right->
NodeNum 2537 <<
") " << PhysRegMsg[RHasPhysReg] <<
"\n");
2538 return LHasPhysReg < RHasPhysReg;
2543 unsigned LPriority = SPQ->getNodePriority(left);
2544 unsigned RPriority = SPQ->getNodePriority(right);
2550 RPriority = (RPriority > RNumVals) ? (RPriority - RNumVals) : 0;
2554 LPriority = (LPriority > LNumVals) ? (LPriority - LNumVals) : 0;
2557 if (LPriority != RPriority)
2558 return LPriority > RPriority;
2563 unsigned LOrder = SPQ->getNodeOrdering(left);
2564 unsigned ROrder = SPQ->getNodeOrdering(right);
2568 if ((LOrder || ROrder) && LOrder != ROrder)
2569 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2592 return LDist < RDist;
2597 if (LScratch != RScratch)
2598 return LScratch > RScratch;
2602 if ((left->
isCall && RPriority > 0) || (right->
isCall && LPriority > 0))
2621 "NodeQueueId cannot be zero");
2626 bool bu_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2634 bool src_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2638 unsigned LOrder = SPQ->getNodeOrdering(left);
2639 unsigned ROrder = SPQ->getNodeOrdering(right);
2643 if ((LOrder || ROrder) && LOrder != ROrder)
2644 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2653 bool hybrid_ls_rr_sort::isReady(
SUnit *SU,
unsigned CurCycle)
const {
2654 static const unsigned ReadyDelay = 3;
2656 if (SPQ->MayReduceRegPressure(SU))
return true;
2658 if (SU->
getHeight() > (CurCycle + ReadyDelay))
return false;
2660 if (SPQ->getHazardRec()->getHazardType(SU, -ReadyDelay)
2668 bool hybrid_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2676 bool LHigh = SPQ->HighRegPressure(left);
2677 bool RHigh = SPQ->HighRegPressure(right);
2680 if (LHigh && !RHigh) {
2685 else if (!LHigh && RHigh) {
2690 if (!LHigh && !RHigh) {
2700 bool ilp_ls_rr_sort::isReady(
SUnit *SU,
unsigned CurCycle)
const {
2701 if (SU->
getHeight() > CurCycle)
return false;
2703 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2717 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2718 Opc == TargetOpcode::SUBREG_TO_REG ||
2719 Opc == TargetOpcode::INSERT_SUBREG)
2734 bool ilp_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2742 unsigned LLiveUses = 0, RLiveUses = 0;
2743 int LPDiff = 0, RPDiff = 0;
2745 LPDiff = SPQ->RegPressureDiff(left, LLiveUses);
2746 RPDiff = SPQ->RegPressureDiff(right, RLiveUses);
2750 <<
"): " << LPDiff <<
" != SU(" << right->
NodeNum 2751 <<
"): " << RPDiff <<
"\n");
2752 return LPDiff > RPDiff;
2758 if (LReduce && !RReduce)
return false;
2759 if (RReduce && !LReduce)
return true;
2764 <<
" != SU(" << right->
NodeNum <<
"): " << RLiveUses
2766 return LLiveUses < RLiveUses;
2772 if (LStall != RStall)
2781 <<
"): " << right->
getDepth() <<
"\n");
2795 void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
2799 AddPseudoTwoAddrDeps();
2801 if (!TracksRegPressure && !SrcOrder)
2802 PrescheduleNodesWithMultipleUses();
2804 CalculateSethiUllmanNumbers();
2807 if (scheduleDAG->BB->isSuccessor(scheduleDAG->BB))
2808 for (
SUnit &SU : sunits)
2816 bool RegReductionPQBase::canClobber(
const SUnit *SU,
const SUnit *
Op) {
2822 for (
unsigned i = 0; i != NumOps; ++i) {
2838 ScheduleDAGRRList *scheduleDAG,
2844 if(!ImpDefs && !RegMask)
2849 for (
const SDep &SuccPred : SuccSU->
Preds) {
2855 scheduleDAG->IsReachable(DepSU, SuccPred.
getSUnit()))
2859 for (
const MCPhysReg *ImpDef = ImpDefs; *ImpDef; ++ImpDef)
2864 scheduleDAG->IsReachable(DepSU, SuccPred.
getSUnit()))
2879 assert(ImpDefs &&
"Caller should check hasPhysRegDefs");
2882 if (!SUNode->isMachineOpcode())
2885 TII->
get(SUNode->getMachineOpcode()).getImplicitDefs();
2887 if (!SUImpDefs && !SURegMask)
2895 unsigned Reg = ImpDefs[i - NumDefs];
2900 for (;*SUImpDefs; ++SUImpDefs) {
2901 unsigned SUReg = *SUImpDefs;
2940 void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {
2942 for (
SUnit &SU : *SUnits) {
2956 cast<RegisterSDNode>(N->getOperand(1))->
getReg()))
2959 SDNode *PredFrameSetup =
nullptr;
2974 PredFrameSetup = PredND;
2979 if (PredFrameSetup !=
nullptr)
2983 SUnit *PredSU =
nullptr;
3003 cast<RegisterSDNode>(N->getOperand(1))->
getReg()))
3007 for (
const SDep &PredSucc : PredSU->
Succs) {
3009 if (PredSuccSU == &SU)
continue;
3013 goto outer_loop_continue;
3017 goto outer_loop_continue;
3019 if (scheduleDAG->IsReachable(&SU, PredSuccSU))
3020 goto outer_loop_continue;
3026 dbgs() <<
" Prescheduling SU #" << SU.
NodeNum <<
" next to PredSU #" 3028 <<
" to guide scheduling in the presence of multiple uses\n");
3029 for (
unsigned i = 0; i != PredSU->
Succs.size(); ++i) {
3033 if (SuccSU != &SU) {
3035 scheduleDAG->RemovePred(SuccSU, Edge);
3036 scheduleDAG->AddPredQueued(&SU, Edge);
3038 scheduleDAG->AddPredQueued(SuccSU, Edge);
3042 outer_loop_continue:;
3053 void RegReductionPQBase::AddPseudoTwoAddrDeps() {
3054 for (
SUnit &SU : *SUnits) {
3067 for (
unsigned j = 0; j != NumOps; ++j) {
3091 while (SuccSU->
Succs.size() == 1 &&
3094 TargetOpcode::COPY_TO_REGCLASS)
3095 SuccSU = SuccSU->
Succs.front().getSUnit();
3108 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
3109 SuccOpc == TargetOpcode::INSERT_SUBREG ||
3110 SuccOpc == TargetOpcode::SUBREG_TO_REG)
3113 (!canClobber(SuccSU, DUSU) ||
3116 !scheduleDAG->IsReachable(SuccSU, &SU)) {
3118 <<
" Adding a pseudo-two-addr edge from SU #" 3138 BURegReductionPriorityQueue *PQ =
3139 new BURegReductionPriorityQueue(*IS->
MF,
false,
false, TII, TRI,
nullptr);
3140 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
false, PQ, OptLevel);
3141 PQ->setScheduleDAG(SD);
3152 SrcRegReductionPriorityQueue *PQ =
3153 new SrcRegReductionPriorityQueue(*IS->
MF,
false,
true, TII, TRI,
nullptr);
3154 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
false, PQ, OptLevel);
3155 PQ->setScheduleDAG(SD);
3167 HybridBURRPriorityQueue *PQ =
3168 new HybridBURRPriorityQueue(*IS->
MF,
true,
false, TII, TRI, TLI);
3170 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
true, PQ, OptLevel);
3171 PQ->setScheduleDAG(SD);
3183 ILPBURRPriorityQueue *PQ =
3184 new ILPBURRPriorityQueue(*IS->
MF,
true,
false, TII, TRI, TLI);
3185 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
true, PQ, OptLevel);
3186 PQ->setScheduleDAG(SD);
virtual void initNodes(std::vector< SUnit > &SUnits)=0
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
unsigned NumPreds
of SDep::Data preds.
virtual void updateNode(const SUnit *SU)=0
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
This class represents lattice values for constants.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref, RegReductionPQBase *SPQ)
static bool canEnableCoalescing(SUnit *SU)
virtual const TargetRegisterClass * getRepRegClassFor(MVT VT) const
Return the 'representative' register class for the specified value type.
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z, ..."), which produces the same result if Y and Z are exchanged.
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned getIROrder() const
Return the node ordering.
static cl::opt< bool > DisableSchedRegPressure("disable-sched-reg-pressure", cl::Hidden, cl::init(false), cl::desc("Disable regpressure priority in sched=list-ilp"))
virtual bool tracksRegPressure() const
static cl::opt< unsigned > AvgIPC("sched-avg-ipc", cl::Hidden, cl::init(1), cl::desc("Average inst/cycle whan no target itinerary exists."))
void push_back(const T &Elt)
bool isTwoAddress
Is a two-address instruction.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
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...
Describe properties that are true of each instruction in the target description file.
static void GetCostForDef(const ScheduleDAGSDNodes::RegDefIter &RegDefPos, const TargetLowering *TLI, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, unsigned &RegClass, unsigned &Cost, const MachineFunction &MF)
GetCostForDef - Looks up the register class and cost for a given definition.
virtual void dumpNode(const SUnit &SU) const =0
virtual void push(SUnit *U)=0
static bool isClobberKind(unsigned Flag)
static bool canClobberReachingPhysRegUse(const SUnit *DepSU, const SUnit *SU, ScheduleDAGRRList *scheduleDAG, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
canClobberReachingPhysRegUse - True if SU would clobber one of it's successor's explicit physregs who...
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
MVT getSimpleValueType(unsigned ResNo) const
Return the type of a specified result as a simple type.
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
static cl::opt< bool > DisableSchedVRegCycle("disable-sched-vrcycle", cl::Hidden, cl::init(false), cl::desc("Disable virtual register cycle interference checks"))
unsigned getCallFrameDestroyOpcode() const
void setNodeId(int Id)
Set unique node id.
unsigned getReg() const
Returns the register associated with this edge.
SDNode * getNode() const
get the SDNode which holds the desired result
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
static unsigned CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector< unsigned > &SUNumbers)
CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
static RegisterScheduler burrListDAGScheduler("list-burr", "Bottom-up register reduction list scheduling", createBURRListDAGScheduler)
static bool hasVRegCycleUse(const SUnit *SU)
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
virtual void dump(ScheduleDAG *) const
virtual unsigned getRegPressureLimit(const TargetRegisterClass *RC, MachineFunction &MF) const
Return the register pressure "high water mark" for the specific register class.
EntryToken - This is the marker used to indicate the start of a region.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
ScheduleDAGSDNodes * createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level)
createHybridListDAGScheduler - This creates a bottom up register pressure aware list scheduler that m...
const TargetRegisterClass * getRegClass(unsigned i) const
Returns the register class associated with the enumeration value.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
static SDNode * FindCallSeqStart(SDNode *N, unsigned &NestLevel, unsigned &MaxNest, const TargetInstrInfo *TII)
FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate the corresponding (lowered) C...
bool isScheduled
True once scheduled.
This interface is used to plug different priorities computation algorithms into the list scheduler...
static int checkSpecialNodes(const SUnit *left, const SUnit *right)
unsigned NumSuccs
of SDep::Data sucss.
virtual void unscheduledNode(SUnit *)
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.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
const HexagonInstrInfo * TII
virtual void releaseState()=0
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
static RegisterScheduler sourceListDAGScheduler("source", "Similar to list-burr but schedules in source " "order when possible", createSourceListDAGScheduler)
virtual const TargetRegisterClass * getRegClass(const MCInstrDesc &MCID, unsigned OpNum, const TargetRegisterInfo *TRI, const MachineFunction &MF) const
Given a machine instruction descriptor, returns the register class constraint for OpNum...
const TargetLowering * TLI
virtual uint8_t getRepRegClassCostFor(MVT VT) const
Return the cost of the 'representative' register class for the specified value type.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Regular data dependence (aka true-dependence).
CopyToReg - This node has three operands: a chain, a register number to set to this value...
iterator_range< regclass_iterator > regclasses() const
bool hasPhysRegDefs
Has physreg defs that are being used.
void setCurCycle(unsigned Cycle)
static bool isRegDefEarlyClobberKind(unsigned Flag)
static void CheckForLiveRegDef(SUnit *SU, unsigned Reg, SUnit **LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs, const TargetRegisterInfo *TRI)
CheckForLiveRegDef - Return true and update live register vector if the specified register def of the...
static const uint32_t * getNodeRegMask(const SDNode *N)
getNodeRegMask - Returns the register mask attached to an SDNode, if any.
unsigned getID() const
Return the register class ID number.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
INLINEASM - Represents an inline asm block.
unsigned getNumRegClasses() const
bool regsOverlap(Register regA, Register regB) const
Returns true if the two registers are equal or alias each other.
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
SUnit * OrigNode
If not this, the node from which this node was cloned.
virtual void RecedeCycle()
RecedeCycle - This callback is invoked whenever the next bottom-up instruction to be scheduled cannot...
ScheduleDAGSDNodes * createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createBURRListDAGScheduler - This creates a bottom up register usage reduction list scheduler...
bool isPending
True once pending.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
virtual const TargetInstrInfo * getInstrInfo() const
static bool isRegDefKind(unsigned Flag)
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
TargetInstrInfo - Interface to description of machine instruction set.
static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask, ArrayRef< SUnit *> LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs)
CheckForLiveRegDefMasked - Check for any live physregs that are clobbered by RegMask, and add them to LRegs.
This corresponds to the llvm.lifetime.
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value...
initializer< Ty > init(const Ty &Val)
bool isCall
Is a function call.
const MCPhysReg * getImplicitDefs() const
Return a list of registers that are potentially written by any instance of this machine instruction...
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
unsigned getMaxLookAhead() const
static cl::opt< bool > DisableSchedStalls("disable-sched-stalls", cl::Hidden, cl::init(true), cl::desc("Disable no-stall priority in sched=list-ilp"))
HazardRecognizer - This determines whether or not an instruction can be issued this cycle...
bool isOptionalDef() const
Set if this operand is a optional def.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool hasOptionalDef() const
Set if this instruction has an optional definition, e.g.
unsigned short Latency
Node latency.
virtual void addNode(const SUnit *SU)=0
bool hasAnyUseOfValue(unsigned Value) const
Return true if there are any use of the indicated value.
virtual bool empty() const =0
size_t size() const
size - Get the array size.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
iterator_range< value_op_iterator > op_values() const
static RegisterScheduler ILPListDAGScheduler("list-ilp", "Bottom-up register pressure aware list scheduling " "which tries to balance ILP and register pressure", createILPListDAGScheduler)
const SDValue & getOperand(unsigned Num) const
ScheduleDAGSDNodes * createILPListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level)
createILPListDAGScheduler - This creates a bottom up register pressure aware list scheduler that trie...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
static bool isOperandOf(const SUnit *SU, SDNode *N)
static unsigned calcMaxScratches(const SUnit *SU)
calcMaxScratches - Returns an cost estimate of the worse case requirement for scratch registers...
static bool IsChainDependent(SDNode *Outer, SDNode *Inner, unsigned NestLevel, const TargetInstrInfo *TII)
IsChainDependent - Test if Outer is reachable from Inner through chain dependencies.
static bool BUHasStall(SUnit *SU, int Height, RegReductionPQBase *SPQ)
const MCPhysReg * ImplicitDefs
const SDNode * GetNode() const
static unsigned getNumOperandRegisters(unsigned Flag)
getNumOperandRegisters - Extract the number of registers field from the inline asm operand flag...
static cl::opt< bool > DisableSchedCriticalPath("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp"))
bool isVRegCycle
May use and def the same vreg.
unsigned getCallFrameSetupOpcode() const
These methods return the opcode of the frame setup/destroy instructions if they exist (-1 otherwise)...
MCRegAliasIterator enumerates all registers aliasing Reg.
static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
canClobberPhysRegDefs - True if SU would clobber one of SuccSU's physical register defs...
static void resetVRegCycle(SUnit *SU)
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
static cl::opt< bool > DisableSchedLiveUses("disable-sched-live-uses", cl::Hidden, cl::init(true), cl::desc("Disable live use priority in sched=list-ilp"))
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
void RemovePred(SUnit *M, SUnit *N)
Updates the topological ordering to accommodate an an edge to be removed from the specified node N fr...
static bool hasOnlyLiveInOpers(const SUnit *SU)
hasOnlyLiveInOpers - Return true if SU has only value predecessors that are CopyFromReg from a virtua...
static unsigned closestSucc(const SUnit *SU)
closestSucc - Returns the scheduled cycle of the successor which is closest to the current cycle...
Sched::Preference SchedulingPref
Scheduling preference.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
RegDefIter - In place iteration over the values defined by an SUnit.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
EH_LABEL - Represents a label in mid basic block used to track locations needed for debug and excepti...
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
static bool BURRSort(SUnit *left, SUnit *right, RegReductionPQBase *SPQ)
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specific constraint if it is set.
TokenFactor - This node takes multiple tokens as input and produces a single token result...
bool isCommutable
Is a commutable instruction.
ScheduleDAGSDNodes * createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createBURRListDAGScheduler - This creates a bottom up list scheduler that schedules nodes in source c...
virtual void EmitInstruction(SUnit *)
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
static cl::opt< bool > DisableSchedHeight("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp"))
virtual void remove(SUnit *SU)=0
Align max(MaybeAlign Lhs, Align Rhs)
static void initVRegCycle(SUnit *SU)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
void AddPredQueued(SUnit *Y, SUnit *X)
Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Represents one node in the SelectionDAG.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
const TargetRegisterClass * CopySrcRC
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static bool clobbersPhysReg(const uint32_t *RegMask, unsigned PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
virtual void Reset()
Reset - This callback is invoked when a new block of instructions is about to be schedule.
virtual void scheduledNode(SUnit *)
As each node is scheduled, this method is invoked.
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
bool isCallOp
Is a function call operand.
void setLatency(unsigned Lat)
Sets the latency for this edge.
TargetSubtargetInfo - Generic base class for all target subtargets.
int getNodeId() const
Return the unique node id.
bool isAvailable
True once available.
unsigned NodeQueueId
Queue id of node.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
static RegisterScheduler hybridListDAGScheduler("list-hybrid", "Bottom-up register pressure aware list scheduling " "which tries to balance latency and register pressure", createHybridListDAGScheduler)
virtual ScheduleHazardRecognizer * CreateTargetHazardRecognizer(const TargetSubtargetInfo *STI, const ScheduleDAG *DAG) const
Allocate and return a hazard recognizer to use for this target when scheduling the machine instructio...
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static bool hasOnlyLiveOutUses(const SUnit *SU)
hasOnlyLiveOutUses - Return true if SU has only value successors that are CopyToReg to a virtual regi...
LLVM_NODISCARD bool empty() const
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
static cl::opt< bool > DisableSchedPhysRegJoin("disable-sched-physreg-join", cl::Hidden, cl::init(false), cl::desc("Disable physreg def-use affinity"))
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
unsigned short NumRegDefsLeft
of reg defs with no scheduled use.
static cl::opt< bool > Disable2AddrHack("disable-2addr-hack", cl::Hidden, cl::init(true), cl::desc("Disable scheduler's two-address hack"))
static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, const TargetInstrInfo *TII)
getPhysicalRegisterVT - Returns the ValueType of the physical register definition of the specified no...
static cl::opt< bool > DisableSchedCycles("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling"))
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
unsigned NodeNum
Entry # of node in the node vector.
void setHeightDirty()
Sets a flag in this node to indicate that its stored Height value will require recomputation the next...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
INLINEASM_BR - Terminator version of inline asm. Used by asm-goto.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
static cl::opt< int > MaxReorderWindow("max-sched-reorder", cl::Hidden, cl::init(6), cl::desc("Number of instructions to allow ahead of the critical path " "in sched=list-ilp"))
virtual bool isReady(SUnit *) const
bool hasReadyFilter() const
unsigned getMachineOpcode() const
This may only be called if isMachineOpcode returns true.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
SmallVector< SDep, 4 > Succs
All sunit successors.
const MCOperandInfo * OpInfo
Arbitrary strong DAG edge (no real dependence).
void AddPred(SUnit *Y, SUnit *X)
Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y...
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
bool isScheduleLow
True if preferable to schedule low.
MERGE_VALUES - This node takes multiple discrete operands and returns them all as its individual resu...
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...
bool hasPhysRegClobbers
Has any physreg defs, used or not.
bool isSucc(const SUnit *N) const
Tests if node N is a successor of this node.
virtual HazardType getHazardType(SUnit *m, int Stalls=0)
getHazardType - Return the hazard type of emitting this node.
Scheduling unit. This is a node in the scheduling DAG.
This file describes how to lower LLVM code to machine code.
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
virtual bool atIssueLimit() const
atIssueLimit - Return true if no more instructions may be issued in this cycle.