39#include "llvm/Config/llvm-config.h"
62#define DEBUG_TYPE "pre-RA-sched"
64STATISTIC(NumBacktracks,
"Number of times scheduler backtracked");
67STATISTIC(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 = ~0u;
163 unsigned IssueCount = 0u;
168 unsigned NumLiveRegs = 0u;
169 std::unique_ptr<SUnit*[]> LiveRegDefs;
170 std::unique_ptr<SUnit*[]> LiveRegGens;
193 AvailableQueue(availqueue), Topo(SUnits, nullptr) {
201 ~ScheduleDAGRRList()
override {
203 delete AvailableQueue;
211 bool IsReachable(
const SUnit *SU,
const SUnit *TargetSU) {
217 bool WillCreateCycle(
SUnit *SU,
SUnit *TargetSU) {
224 void AddPredQueued(
SUnit *SU,
const SDep &
D) {
246 bool isReady(
SUnit *SU) {
251 void ReleasePred(
SUnit *SU,
const SDep *PredEdge);
252 void ReleasePredecessors(
SUnit *SU);
253 void ReleasePending();
254 void AdvanceToCycle(
unsigned NextCycle);
255 void AdvancePastStalls(
SUnit *SU);
256 void EmitNode(
SUnit *SU);
257 void ScheduleNodeBottomUp(
SUnit*);
258 void CapturePred(
SDep *PredEdge);
259 void UnscheduleNodeBottomUp(
SUnit*);
260 void RestoreHazardCheckerBottomUp();
264 void InsertCopiesAndMoveSuccs(
SUnit*,
unsigned,
270 void releaseInterferences(
unsigned Reg = 0);
272 SUnit *PickNodeToScheduleBottomUp();
273 void ListScheduleBottomUp();
277 unsigned NumSUnits = SUnits.size();
280 if (NewNode->
NodeNum >= NumSUnits)
287 unsigned NumSUnits = SUnits.size();
290 if (NewNode->
NodeNum >= NumSUnits)
314 unsigned &RegClass,
unsigned &
Cost,
320 if (VT == MVT::Untyped) {
325 Register Reg = cast<RegisterSDNode>(
Node->getOperand(1))->getReg();
327 RegClass = RC->
getID();
332 unsigned Opcode =
Node->getMachineOpcode();
333 if (Opcode == TargetOpcode::REG_SEQUENCE) {
334 unsigned DstRCIdx = cast<ConstantSDNode>(
Node->getOperand(0))->getZExtValue();
336 RegClass = RC->
getID();
344 assert(RC &&
"Not a valid register class");
345 RegClass = RC->
getID();
356void ScheduleDAGRRList::Schedule() {
358 <<
" '" << BB->getName() <<
"' **********\n");
367 LiveRegDefs.reset(
new SUnit*[
TRI->getNumRegs() + 1]());
368 LiveRegGens.reset(
new SUnit*[
TRI->getNumRegs() + 1]());
369 CallSeqEndForStart.
clear();
370 assert(Interferences.
empty() && LRegsMap.empty() &&
"stale Interferences");
373 BuildSchedGraph(
nullptr);
383 ListScheduleBottomUp();
388 dbgs() <<
"*** Final schedule ***\n";
400void ScheduleDAGRRList::ReleasePred(
SUnit *SU,
const SDep *PredEdge) {
405 dbgs() <<
"*** Scheduling failed! ***\n";
407 dbgs() <<
" has been released too many times!\n";
413 if (!forceUnitLatencies()) {
425 if (Height < MinAvailableCycle)
426 MinAvailableCycle = Height;
428 if (isReady(PredSU)) {
429 AvailableQueue->
push(PredSU);
435 PendingQueue.push_back(PredSU);
459 if (
N->isMachineOpcode()) {
460 if (
N->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
462 }
else if (
N->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
470 if (
Op.getValueType() == MVT::Other) {
472 goto found_chain_operand;
475 found_chain_operand:;
499 unsigned BestMaxNest = MaxNest;
501 unsigned MyNestLevel = NestLevel;
502 unsigned MyMaxNest = MaxNest;
504 MyNestLevel, MyMaxNest,
TII))
505 if (!Best || (MyMaxNest > BestMaxNest)) {
507 BestMaxNest = MyMaxNest;
511 MaxNest = BestMaxNest;
515 if (
N->isMachineOpcode()) {
516 if (
N->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
518 MaxNest = std::max(MaxNest, NestLevel);
519 }
else if (
N->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
528 if (
Op.getValueType() == MVT::Other) {
530 goto found_chain_operand;
533 found_chain_operand:;
556void ScheduleDAGRRList::ReleasePredecessors(
SUnit *SU) {
559 ReleasePred(SU, &Pred);
565 SUnit *RegDef = LiveRegDefs[Pred.
getReg()]; (void)RegDef;
567 "interference on register dependence");
569 if (!LiveRegGens[Pred.
getReg()]) {
571 LiveRegGens[Pred.
getReg()] = SU;
579 unsigned CallResource =
TRI->getNumRegs();
580 if (!LiveRegDefs[CallResource])
582 if (
Node->isMachineOpcode() &&
583 Node->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
584 unsigned NestLevel = 0;
585 unsigned MaxNest = 0;
587 assert(
N &&
"Must find call sequence start");
590 CallSeqEndForStart[
Def] = SU;
593 LiveRegDefs[CallResource] =
Def;
594 LiveRegGens[CallResource] = SU;
601void ScheduleDAGRRList::ReleasePending() {
603 assert(PendingQueue.empty() &&
"pending instrs not allowed in this mode");
608 if (AvailableQueue->
empty())
609 MinAvailableCycle = std::numeric_limits<unsigned>::max();
613 for (
unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
614 unsigned ReadyCycle = PendingQueue[i]->getHeight();
615 if (ReadyCycle < MinAvailableCycle)
616 MinAvailableCycle = ReadyCycle;
618 if (PendingQueue[i]->isAvailable) {
619 if (!isReady(PendingQueue[i]))
621 AvailableQueue->
push(PendingQueue[i]);
623 PendingQueue[i]->isPending =
false;
624 PendingQueue[i] = PendingQueue.back();
625 PendingQueue.pop_back();
631void ScheduleDAGRRList::AdvanceToCycle(
unsigned NextCycle) {
632 if (NextCycle <= CurCycle)
639 CurCycle = NextCycle;
642 for (; CurCycle != NextCycle; ++CurCycle) {
653void ScheduleDAGRRList::AdvancePastStalls(
SUnit *SU) {
670 AdvanceToCycle(ReadyCycle);
690 AdvanceToCycle(CurCycle + Stalls);
695void ScheduleDAGRRList::EmitNode(
SUnit *SU) {
706 "This target-independent node should not be scheduled.");
738void ScheduleDAGRRList::ScheduleNodeBottomUp(
SUnit *SU) {
743 if (CurCycle < SU->getHeight())
745 <<
"] pipeline stall!\n");
765 AdvanceToCycle(CurCycle + 1);
769 ReleasePredecessors(SU);
775 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
777 LiveRegDefs[Succ.
getReg()] =
nullptr;
778 LiveRegGens[Succ.
getReg()] =
nullptr;
779 releaseInterferences(Succ.
getReg());
784 unsigned CallResource =
TRI->getNumRegs();
785 if (LiveRegDefs[CallResource] == SU)
788 if (SUNode->isMachineOpcode() &&
789 SUNode->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
790 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
792 LiveRegDefs[CallResource] =
nullptr;
793 LiveRegGens[CallResource] =
nullptr;
794 releaseInterferences(CallResource);
815 AdvanceToCycle(CurCycle + 1);
822void ScheduleDAGRRList::CapturePred(
SDep *PredEdge) {
827 AvailableQueue->
remove(PredSU);
831 "NumSuccsLeft will overflow!");
837void ScheduleDAGRRList::UnscheduleNodeBottomUp(
SUnit *SU) {
844 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
846 "Physical register dependency violated?");
848 LiveRegDefs[Pred.
getReg()] =
nullptr;
849 LiveRegGens[Pred.
getReg()] =
nullptr;
850 releaseInterferences(Pred.
getReg());
856 unsigned CallResource =
TRI->getNumRegs();
859 if (SUNode->isMachineOpcode() &&
860 SUNode->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
861 SUnit *SeqEnd = CallSeqEndForStart[SU];
862 assert(SeqEnd &&
"Call sequence start/end must be known");
863 assert(!LiveRegDefs[CallResource]);
864 assert(!LiveRegGens[CallResource]);
866 LiveRegDefs[CallResource] = SU;
867 LiveRegGens[CallResource] = SeqEnd;
873 if (LiveRegGens[CallResource] == SU)
876 if (SUNode->isMachineOpcode() &&
877 SUNode->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
878 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
879 assert(LiveRegDefs[CallResource]);
880 assert(LiveRegGens[CallResource]);
882 LiveRegDefs[CallResource] =
nullptr;
883 LiveRegGens[CallResource] =
nullptr;
884 releaseInterferences(CallResource);
888 for (
auto &Succ : SU->
Succs) {
891 if (!LiveRegDefs[Reg])
895 LiveRegDefs[
Reg] = SU;
899 if (!LiveRegGens[Reg]) {
902 for (
auto &Succ2 : SU->
Succs) {
903 if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
904 Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())
905 LiveRegGens[
Reg] = Succ2.getSUnit();
919 PendingQueue.push_back(SU);
922 AvailableQueue->
push(SU);
929void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {
932 unsigned LookAhead = std::min((
unsigned)
Sequence.size(),
937 std::vector<SUnit *>::const_iterator
I = (
Sequence.end() - LookAhead);
938 unsigned HazardCycle = (*I)->getHeight();
941 for (; SU->
getHeight() > HazardCycle; ++HazardCycle) {
950void ScheduleDAGRRList::BacktrackBottomUp(
SUnit *SU,
SUnit *BtSU) {
956 UnscheduleNodeBottomUp(OldSU);
965 RestoreHazardCheckerBottomUp();
975 if (SUNode->isOperandOf(
N))
982SUnit *ScheduleDAGRRList::TryUnfoldSU(
SUnit *SU) {
986 if (!
TII->unfoldMemoryOperand(*DAG,
N, NewNodes))
991 if (NewNodes.
size() == 3)
994 assert(NewNodes.
size() == 2 &&
"Expected a load folding node!");
997 SDNode *LoadNode = NewNodes[0];
998 unsigned NumVals =
N->getNumValues();
1004 bool isNewLoad =
true;
1007 LoadSU = &SUnits[LoadNode->
getNodeId()];
1014 LoadSU = CreateNewSUnit(LoadNode);
1017 InitNumRegDefsLeft(LoadSU);
1018 computeLatency(LoadSU);
1024 if (
N->getNodeId() != -1) {
1025 NewSU = &SUnits[
N->getNodeId()];
1033 NewSU = CreateNewSUnit(
N);
1046 InitNumRegDefsLeft(NewSU);
1047 computeLatency(NewSU);
1053 for (
unsigned i = 0; i != NumVals; ++i)
1055 DAG->ReplaceAllUsesOfValueWith(
SDValue(SU->
getNode(), OldNumVals - 1),
1080 for (
const SDep &Pred : ChainPreds) {
1081 RemovePred(SU, Pred);
1083 AddPredQueued(LoadSU, Pred);
1085 for (
const SDep &Pred : LoadPreds) {
1086 RemovePred(SU, Pred);
1088 AddPredQueued(LoadSU, Pred);
1090 for (
const SDep &Pred : NodePreds) {
1091 RemovePred(SU, Pred);
1092 AddPredQueued(NewSU, Pred);
1094 for (
SDep &
D : NodeSuccs) {
1095 SUnit *SuccDep =
D.getSUnit();
1097 RemovePred(SuccDep,
D);
1099 AddPredQueued(SuccDep,
D);
1105 for (
SDep &
D : ChainSuccs) {
1106 SUnit *SuccDep =
D.getSUnit();
1108 RemovePred(SuccDep,
D);
1111 AddPredQueued(SuccDep,
D);
1119 AddPredQueued(NewSU,
D);
1122 AvailableQueue->
addNode(LoadSU);
1124 AvailableQueue->
addNode(NewSU);
1136SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(
SUnit *SU) {
1144 if (
N->getGluedNode() &&
1145 !
TII->canCopyGluedNodeDuringSchedule(
N)) {
1148 <<
"Giving up because it has incoming glue and the target does not "
1149 "want to copy it\n");
1154 bool TryUnfold =
false;
1155 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i) {
1156 MVT VT =
N->getSimpleValueType(i);
1157 if (VT == MVT::Glue) {
1158 LLVM_DEBUG(
dbgs() <<
"Giving up because it has outgoing glue\n");
1160 }
else if (VT == MVT::Other)
1164 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
1165 if (VT == MVT::Glue && !
TII->canCopyGluedNodeDuringSchedule(
N)) {
1167 dbgs() <<
"Giving up because it one of the operands is glue and "
1168 "the target does not want to copy it\n");
1175 SUnit *UnfoldSU = TryUnfoldSU(SU);
1186 NewSU = CreateClone(SU);
1191 AddPredQueued(NewSU, Pred);
1207 AddPredQueued(SuccSU,
D);
1212 for (
const auto &[DelSU, DelD] : DelDeps)
1213 RemovePred(DelSU, DelD);
1216 AvailableQueue->
addNode(NewSU);
1224void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(
SUnit *SU,
unsigned Reg,
1228 SUnit *CopyFromSU = CreateNewSUnit(
nullptr);
1232 SUnit *CopyToSU = CreateNewSUnit(
nullptr);
1245 D.setSUnit(CopyToSU);
1246 AddPredQueued(SuccSU,
D);
1256 for (
const auto &[DelSU, DelD] : DelDeps)
1257 RemovePred(DelSU, DelD);
1260 FromDep.setLatency(SU->
Latency);
1261 AddPredQueued(CopyFromSU, FromDep);
1263 ToDep.setLatency(CopyFromSU->
Latency);
1264 AddPredQueued(CopyToSU, ToDep);
1267 AvailableQueue->
addNode(CopyFromSU);
1268 AvailableQueue->
addNode(CopyToSU);
1269 Copies.push_back(CopyFromSU);
1270 Copies.push_back(CopyToSU);
1287 "Physical reg def must be in implicit def list!");
1295 return N->getSimpleValueType(NumRes);
1308 if (!LiveRegDefs[*AliasI])
continue;
1311 if (LiveRegDefs[*AliasI] == SU)
continue;
1314 if (
Node && LiveRegDefs[*AliasI]->getNode() ==
Node)
1318 if (RegAdded.
insert(*AliasI).second) {
1331 for (
unsigned i = 1, e = LiveRegDefs.
size()-1; i != e; ++i) {
1332 if (!LiveRegDefs[i])
continue;
1333 if (LiveRegDefs[i] == SU)
continue;
1335 if (RegAdded.
insert(i).second)
1343 if (
const auto *RegOp = dyn_cast<RegisterMaskSDNode>(
Op.getNode()))
1344 return RegOp->getRegMask();
1352bool ScheduleDAGRRList::
1354 if (NumLiveRegs == 0)
1365 RegAdded, LRegs,
TRI);
1372 unsigned NumOps =
Node->getNumOperands();
1373 if (
Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
1378 cast<ConstantSDNode>(
Node->getOperand(i))->getZExtValue();
1380 unsigned NumVals =
F.getNumOperandRegisters();
1383 if (
F.isRegDefKind() ||
F.isRegDefEarlyClobberKind() ||
1384 F.isClobberKind()) {
1386 for (; NumVals; --NumVals, ++i) {
1388 if (
Reg.isPhysical())
1399 if (
Reg.isPhysical()) {
1400 SDNode *SrcNode =
Node->getOperand(2).getNode();
1406 if (!
Node->isMachineOpcode())
1411 if (
Node->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
1413 unsigned CallResource =
TRI->getNumRegs();
1414 if (LiveRegDefs[CallResource]) {
1415 SDNode *Gen = LiveRegGens[CallResource]->getNode();
1419 RegAdded.
insert(CallResource).second)
1434 for (
unsigned i = 0; i < MCID.
getNumDefs(); ++i)
1435 if (MCID.
operands()[i].isOptionalDef()) {
1437 Register Reg = cast<RegisterSDNode>(OptionalDef)->getReg();
1445 return !LRegs.
empty();
1448void ScheduleDAGRRList::releaseInterferences(
unsigned Reg) {
1450 for (
unsigned i = Interferences.
size(); i > 0; --i) {
1451 SUnit *SU = Interferences[i-1];
1452 LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);
1464 AvailableQueue->
push(SU);
1466 if (i < Interferences.
size())
1467 Interferences[i-1] = Interferences.
back();
1469 LRegsMap.erase(LRegsPos);
1477SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
1478 SUnit *CurSU = AvailableQueue->
empty() ? nullptr : AvailableQueue->
pop();
1479 auto FindAvailableNode = [&]() {
1482 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
1485 if (LRegs[0] ==
TRI->getNumRegs())
dbgs() <<
"CallResource";
1488 auto [LRegsIter, LRegsInserted] = LRegsMap.try_emplace(CurSU, LRegs);
1489 if (LRegsInserted) {
1496 LRegsIter->second = LRegs;
1498 CurSU = AvailableQueue->
pop();
1501 FindAvailableNode();
1513 for (
SUnit *TrySU : Interferences) {
1518 SUnit *BtSU =
nullptr;
1519 unsigned LiveCycle = std::numeric_limits<unsigned>::max();
1520 for (
unsigned Reg : LRegs) {
1521 if (LiveRegGens[Reg]->getHeight() < LiveCycle) {
1522 BtSU = LiveRegGens[
Reg];
1526 if (!WillCreateCycle(TrySU, BtSU)) {
1528 BacktrackBottomUp(TrySU, BtSU);
1535 AvailableQueue->
remove(BtSU);
1538 <<
") to SU(" << TrySU->NodeNum <<
")\n");
1543 if (!TrySU->isAvailable || !TrySU->NodeQueueId) {
1544 LLVM_DEBUG(
dbgs() <<
"TrySU not available; choosing node from queue\n");
1545 CurSU = AvailableQueue->
pop();
1549 AvailableQueue->
remove(TrySU);
1552 FindAvailableNode();
1564 SUnit *TrySU = Interferences[0];
1566 assert(LRegs.
size() == 1 &&
"Can't handle this yet!");
1567 unsigned Reg = LRegs[0];
1571 TRI->getMinimalPhysRegClass(Reg, VT);
1581 SUnit *NewDef =
nullptr;
1583 NewDef = CopyAndMoveSuccessors(LRDef);
1584 if (!DestRC && !NewDef)
1590 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC,
Copies);
1592 <<
" to SU #" <<
Copies.front()->NodeNum <<
"\n");
1598 <<
" to SU #" << TrySU->
NodeNum <<
"\n");
1599 LiveRegDefs[
Reg] = NewDef;
1604 assert(CurSU &&
"Unable to resolve live physical register dependencies!");
1610void ScheduleDAGRRList::ListScheduleBottomUp() {
1612 ReleasePredecessors(&ExitSU);
1615 if (!SUnits.empty()) {
1616 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
1617 assert(RootSU->
Succs.empty() &&
"Graph root shouldn't have successors!");
1619 AvailableQueue->
push(RootSU);
1625 while (!AvailableQueue->
empty() || !Interferences.empty()) {
1627 AvailableQueue->
dump(
this));
1631 SUnit *SU = PickNodeToScheduleBottomUp();
1633 AdvancePastStalls(SU);
1635 ScheduleNodeBottomUp(SU);
1637 while (AvailableQueue->
empty() && !PendingQueue.empty()) {
1639 assert(MinAvailableCycle < std::numeric_limits<unsigned>::max() &&
1640 "MinAvailableCycle uninitialized");
1641 AdvanceToCycle(std::max(CurCycle + 1, MinAvailableCycle));
1649 VerifyScheduledSequence(
true);
1655class RegReductionPQBase;
1658 bool isReady(
SUnit* SU,
unsigned CurCycle)
const {
return true; }
1663struct reverse_sort :
public queue_sort {
1666 reverse_sort(SF &sf) : SortFunc(sf) {}
1668 bool operator()(
SUnit* left,
SUnit* right)
const {
1671 return SortFunc(right, left);
1678struct bu_ls_rr_sort :
public queue_sort {
1681 HasReadyFilter =
false
1684 RegReductionPQBase *SPQ;
1686 bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1688 bool operator()(
SUnit* left,
SUnit* right)
const;
1692struct src_ls_rr_sort :
public queue_sort {
1695 HasReadyFilter =
false
1698 RegReductionPQBase *SPQ;
1700 src_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1702 bool operator()(
SUnit* left,
SUnit* right)
const;
1706struct hybrid_ls_rr_sort :
public queue_sort {
1709 HasReadyFilter =
false
1712 RegReductionPQBase *SPQ;
1714 hybrid_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1716 bool isReady(
SUnit *SU,
unsigned CurCycle)
const;
1718 bool operator()(
SUnit* left,
SUnit* right)
const;
1723struct ilp_ls_rr_sort :
public queue_sort {
1726 HasReadyFilter =
false
1729 RegReductionPQBase *SPQ;
1731 ilp_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1733 bool isReady(
SUnit *SU,
unsigned CurCycle)
const;
1735 bool operator()(
SUnit* left,
SUnit* right)
const;
1740 std::vector<SUnit *>
Queue;
1741 unsigned CurQueueId = 0;
1742 bool TracksRegPressure;
1746 std::vector<SUnit> *SUnits =
nullptr;
1752 ScheduleDAGRRList *scheduleDAG =
nullptr;
1755 std::vector<unsigned> SethiUllmanNumbers;
1762 std::vector<unsigned> RegLimit;
1766 bool hasReadyFilter,
1773 SrcOrder(srcorder), MF(mf),
TII(tii),
TRI(tri), TLI(tli) {
1774 if (TracksRegPressure) {
1775 unsigned NumRC =
TRI->getNumRegClasses();
1776 RegLimit.resize(NumRC);
1778 std::fill(RegLimit.begin(), RegLimit.end(), 0);
1785 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1786 scheduleDAG = scheduleDag;
1790 return scheduleDAG->getHazardRec();
1793 void initNodes(std::vector<SUnit> &sunits)
override;
1801 SethiUllmanNumbers.clear();
1805 unsigned getNodePriority(
const SUnit *SU)
const;
1807 unsigned getNodeOrdering(
const SUnit *SU)
const {
1813 bool empty()
const override {
return Queue.empty(); }
1816 assert(!
U->NodeQueueId &&
"Node in the queue already");
1817 U->NodeQueueId = ++CurQueueId;
1824 std::vector<SUnit *>::iterator
I =
llvm::find(Queue, SU);
1825 if (
I != std::prev(
Queue.end()))
1833 void dumpRegPressure()
const;
1835 bool HighRegPressure(
const SUnit *SU)
const;
1837 bool MayReduceRegPressure(
SUnit *SU)
const;
1839 int RegPressureDiff(
SUnit *SU,
unsigned &LiveUses)
const;
1847 void AddPseudoTwoAddrDeps();
1848 void PrescheduleNodesWithMultipleUses();
1849 void CalculateSethiUllmanNumbers();
1853static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1854 unsigned BestIdx = 0;
1857 for (
unsigned I = 1,
E = std::min(Q.size(), (
decltype(Q.size()))1000);
I !=
E;
1859 if (Picker(Q[BestIdx], Q[
I]))
1862 if (BestIdx + 1 != Q.size())
1869SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker,
ScheduleDAG *DAG) {
1872 reverse_sort<SF> RPicker(Picker);
1873 return popFromQueueImpl(Q, RPicker);
1877 return popFromQueueImpl(Q, Picker);
1888class RegReductionPriorityQueue :
public RegReductionPQBase {
1898 : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
1902 bool isBottomUp()
const override {
return SF::IsBottomUp; }
1904 bool isReady(
SUnit *U)
const override {
1905 return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
1908 SUnit *pop()
override {
1909 if (
Queue.empty())
return nullptr;
1911 SUnit *
V = popFromQueue(Queue, Picker, scheduleDAG);
1916#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1919 std::vector<SUnit *> DumpQueue =
Queue;
1920 SF DumpPicker = Picker;
1921 while (!DumpQueue.empty()) {
1922 SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
1930using BURegReductionPriorityQueue = RegReductionPriorityQueue<bu_ls_rr_sort>;
1931using SrcRegReductionPriorityQueue = RegReductionPriorityQueue<src_ls_rr_sort>;
1932using HybridBURRPriorityQueue = RegReductionPriorityQueue<hybrid_ls_rr_sort>;
1933using ILPBURRPriorityQueue = RegReductionPriorityQueue<ilp_ls_rr_sort>;
1950 if (LSchedLow != RSchedLow)
1951 return LSchedLow < RSchedLow ? 1 : -1;
1959 if (SUNumbers[SU->
NodeNum] != 0)
1960 return SUNumbers[SU->
NodeNum];
1964 WorkState(
const SUnit *SU) : SU(SU) {}
1966 unsigned PredsProcessed = 0;
1971 while (!WorkList.
empty()) {
1972 auto &Temp = WorkList.
back();
1973 auto *TempSU = Temp.SU;
1974 bool AllPredsKnown =
true;
1976 for (
unsigned P = Temp.PredsProcessed; P < TempSU->Preds.size(); ++
P) {
1977 auto &Pred = TempSU->Preds[
P];
1978 if (Pred.
isCtrl())
continue;
1980 if (SUNumbers[PredSU->
NodeNum] == 0) {
1983 for (
auto It : WorkList)
1984 assert(It.SU != PredSU &&
"Trying to push an element twice?");
1987 Temp.PredsProcessed =
P + 1;
1988 WorkList.push_back(PredSU);
1989 AllPredsKnown =
false;
1998 unsigned SethiUllmanNumber = 0;
2000 for (
const SDep &Pred : TempSU->Preds) {
2001 if (Pred.
isCtrl())
continue;
2003 unsigned PredSethiUllman = SUNumbers[PredSU->
NodeNum];
2004 assert(PredSethiUllman > 0 &&
"We should have evaluated this pred!");
2005 if (PredSethiUllman > SethiUllmanNumber) {
2006 SethiUllmanNumber = PredSethiUllman;
2008 }
else if (PredSethiUllman == SethiUllmanNumber)
2012 SethiUllmanNumber += Extra;
2013 if (SethiUllmanNumber == 0)
2014 SethiUllmanNumber = 1;
2015 SUNumbers[TempSU->NodeNum] = SethiUllmanNumber;
2019 assert(SUNumbers[SU->
NodeNum] > 0 &&
"SethiUllman should never be zero!");
2020 return SUNumbers[SU->
NodeNum];
2025void RegReductionPQBase::CalculateSethiUllmanNumbers() {
2026 SethiUllmanNumbers.assign(SUnits->size(), 0);
2028 for (
const SUnit &SU : *SUnits)
2032void RegReductionPQBase::addNode(
const SUnit *SU) {
2033 unsigned SUSize = SethiUllmanNumbers.size();
2034 if (SUnits->size() > SUSize)
2035 SethiUllmanNumbers.resize(SUSize*2, 0);
2039void RegReductionPQBase::updateNode(
const SUnit *SU) {
2040 SethiUllmanNumbers[SU->
NodeNum] = 0;
2046unsigned RegReductionPQBase::getNodePriority(
const SUnit *SU)
const {
2053 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2054 Opc == TargetOpcode::SUBREG_TO_REG ||
2055 Opc == TargetOpcode::INSERT_SUBREG)
2071 return SethiUllmanNumbers[SU->
NodeNum];
2073 unsigned Priority = SethiUllmanNumbers[SU->
NodeNum];
2077 return (NP > 0) ? NP : 0;
2087#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2094 << RegLimit[Id] <<
'\n');
2099bool RegReductionPQBase::HighRegPressure(
const SUnit *SU)
const {
2113 RegDefPos.
IsValid(); RegDefPos.Advance()) {
2114 unsigned RCId,
Cost;
2117 if ((RegPressure[RCId] +
Cost) >= RegLimit[RCId])
2124bool RegReductionPQBase::MayReduceRegPressure(
SUnit *SU)
const {
2127 if (!
N->isMachineOpcode() || !SU->
NumSuccs)
2130 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2131 for (
unsigned i = 0; i != NumDefs; ++i) {
2132 MVT VT =
N->getSimpleValueType(i);
2133 if (!
N->hasAnyUseOfValue(i))
2136 if (RegPressure[RCId] >= RegLimit[RCId])
2149int RegReductionPQBase::RegPressureDiff(
SUnit *SU,
unsigned &LiveUses)
const {
2164 RegDefPos.
IsValid(); RegDefPos.Advance()) {
2165 MVT VT = RegDefPos.GetValue();
2167 if (RegPressure[RCId] >= RegLimit[RCId])
2173 if (!
N || !
N->isMachineOpcode() || !SU->
NumSuccs)
2176 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2177 for (
unsigned i = 0; i != NumDefs; ++i) {
2178 MVT VT =
N->getSimpleValueType(i);
2179 if (!
N->hasAnyUseOfValue(i))
2182 if (RegPressure[RCId] >= RegLimit[RCId])
2188void RegReductionPQBase::scheduledNode(
SUnit *SU) {
2189 if (!TracksRegPressure)
2222 RegDefPos.
IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2226 unsigned RCId,
Cost;
2238 RegDefPos.
IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2239 if (SkipRegDefs > 0)
2241 unsigned RCId,
Cost;
2243 if (RegPressure[RCId] <
Cost) {
2247 <<
") has too many regdefs\n");
2257void RegReductionPQBase::unscheduledNode(
SUnit *SU) {
2258 if (!TracksRegPressure)
2264 if (!
N->isMachineOpcode()) {
2268 unsigned Opc =
N->getMachineOpcode();
2269 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2270 Opc == TargetOpcode::INSERT_SUBREG ||
2271 Opc == TargetOpcode::SUBREG_TO_REG ||
2272 Opc == TargetOpcode::REG_SEQUENCE ||
2273 Opc == TargetOpcode::IMPLICIT_DEF)
2295 if (POpc == TargetOpcode::IMPLICIT_DEF)
2297 if (POpc == TargetOpcode::EXTRACT_SUBREG ||
2298 POpc == TargetOpcode::INSERT_SUBREG ||
2299 POpc == TargetOpcode::SUBREG_TO_REG) {
2305 if (POpc == TargetOpcode::REG_SEQUENCE) {
2307 cast<ConstantSDNode>(PN->
getOperand(0))->getZExtValue();
2309 unsigned RCId = RC->
getID();
2316 for (
unsigned i = 0; i != NumDefs; ++i) {
2331 if (SU->
NumSuccs &&
N->isMachineOpcode()) {
2332 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2333 for (
unsigned i = NumDefs, e =
N->getNumValues(); i != e; ++i) {
2334 MVT VT =
N->getSimpleValueType(i);
2335 if (VT == MVT::Glue || VT == MVT::Other)
2337 if (!
N->hasAnyUseOfValue(i))
2354 unsigned MaxHeight = 0;
2356 if (Succ.
isCtrl())
continue;
2363 if (Height > MaxHeight)
2372 unsigned Scratches = 0;
2374 if (Pred.
isCtrl())
continue;
2383 bool RetVal =
false;
2385 if (Pred.
isCtrl())
continue;
2391 if (Reg.isVirtual()) {
2405 bool RetVal =
false;
2407 if (Succ.
isCtrl())
continue;
2412 if (Reg.isVirtual()) {
2444 if (Pred.
isCtrl())
continue;
2456 if (Pred.
isCtrl())
continue;
2460 "VRegCycle def must be CopyFromReg");
2474 if (Pred.
isCtrl())
continue;
2488 if ((
int)SPQ->getCurCycle() < Height)
return true;
2489 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2498 RegReductionPQBase *SPQ) {
2503 int LHeight = (int)left->
getHeight() + LPenalty;
2504 int RHeight = (int)right->
getHeight() + RPenalty;
2517 if (LHeight != RHeight)
2518 return LHeight > RHeight ? 1 : -1;
2530 if (!SPQ->getHazardRec()->isEnabled()) {
2531 if (LHeight != RHeight)
2532 return LHeight > RHeight ? 1 : -1;
2534 int LDepth = left->
getDepth() - LPenalty;
2535 int RDepth = right->
getDepth() - RPenalty;
2536 if (LDepth != RDepth) {
2538 <<
") depth " << LDepth <<
" vs SU (" << right->
NodeNum
2539 <<
") depth " << RDepth <<
"\n");
2540 return LDepth < RDepth ? 1 : -1;
2556 if (LHasPhysReg != RHasPhysReg) {
2558 static const char *
const PhysRegMsg[] = {
" has no physreg",
2559 " defines a physreg" };
2562 << PhysRegMsg[LHasPhysReg] <<
" SU(" << right->
NodeNum
2563 <<
") " << PhysRegMsg[RHasPhysReg] <<
"\n");
2564 return LHasPhysReg < RHasPhysReg;
2569 unsigned LPriority = SPQ->getNodePriority(left);
2570 unsigned RPriority = SPQ->getNodePriority(right);
2576 RPriority = (RPriority > RNumVals) ? (RPriority - RNumVals) : 0;
2580 LPriority = (LPriority > LNumVals) ? (LPriority - LNumVals) : 0;
2583 if (LPriority != RPriority)
2584 return LPriority > RPriority;
2589 unsigned LOrder = SPQ->getNodeOrdering(left);
2590 unsigned ROrder = SPQ->getNodeOrdering(right);
2594 if ((LOrder || ROrder) && LOrder != ROrder)
2595 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2618 return LDist < RDist;
2623 if (LScratch != RScratch)
2624 return LScratch > RScratch;
2628 if ((left->
isCall && RPriority > 0) || (right->
isCall && LPriority > 0))
2647 "NodeQueueId cannot be zero");
2652bool bu_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2660bool src_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2664 unsigned LOrder = SPQ->getNodeOrdering(left);
2665 unsigned ROrder = SPQ->getNodeOrdering(right);
2669 if ((LOrder || ROrder) && LOrder != ROrder)
2670 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2679bool hybrid_ls_rr_sort::isReady(
SUnit *SU,
unsigned CurCycle)
const {
2680 static const unsigned ReadyDelay = 3;
2682 if (SPQ->MayReduceRegPressure(SU))
return true;
2684 if (SU->
getHeight() > (CurCycle + ReadyDelay))
return false;
2686 if (SPQ->getHazardRec()->getHazardType(SU, -ReadyDelay)
2694bool hybrid_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2702 bool LHigh = SPQ->HighRegPressure(left);
2703 bool RHigh = SPQ->HighRegPressure(right);
2706 if (LHigh && !RHigh) {
2711 else if (!LHigh && RHigh) {
2716 if (!LHigh && !RHigh) {
2726bool ilp_ls_rr_sort::isReady(
SUnit *SU,
unsigned CurCycle)
const {
2727 if (SU->
getHeight() > CurCycle)
return false;
2729 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2743 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2744 Opc == TargetOpcode::SUBREG_TO_REG ||
2745 Opc == TargetOpcode::INSERT_SUBREG)
2760bool ilp_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2768 unsigned LLiveUses = 0, RLiveUses = 0;
2769 int LPDiff = 0, RPDiff = 0;
2771 LPDiff = SPQ->RegPressureDiff(left, LLiveUses);
2772 RPDiff = SPQ->RegPressureDiff(right, RLiveUses);
2776 <<
"): " << LPDiff <<
" != SU(" << right->
NodeNum
2777 <<
"): " << RPDiff <<
"\n");
2778 return LPDiff > RPDiff;
2784 if (LReduce && !RReduce)
return false;
2785 if (RReduce && !LReduce)
return true;
2790 <<
" != SU(" << right->
NodeNum <<
"): " << RLiveUses
2792 return LLiveUses < RLiveUses;
2798 if (LStall != RStall)
2807 <<
"): " << right->
getDepth() <<
"\n");
2821void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
2825 AddPseudoTwoAddrDeps();
2827 if (!TracksRegPressure && !SrcOrder)
2828 PrescheduleNodesWithMultipleUses();
2830 CalculateSethiUllmanNumbers();
2833 if (scheduleDAG->BB->isSuccessor(scheduleDAG->BB))
2834 for (
SUnit &SU : sunits)
2842bool RegReductionPQBase::canClobber(
const SUnit *SU,
const SUnit *
Op) {
2848 for (
unsigned i = 0; i != NumOps; ++i) {
2864 ScheduleDAGRRList *scheduleDAG,
2870 if (ImpDefs.
empty() && !RegMask)
2875 for (
const SDep &SuccPred : SuccSU->
Preds) {
2881 scheduleDAG->IsReachable(DepSU, SuccPred.
getSUnit()))
2888 if (
TRI->regsOverlap(ImpDef, SuccPred.
getReg()) &&
2889 scheduleDAG->IsReachable(DepSU, SuccPred.
getSUnit()))
2903 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2905 assert(!ImpDefs.
empty() &&
"Caller should check hasPhysRegDefs");
2908 if (!SUNode->isMachineOpcode())
2911 TII->get(SUNode->getMachineOpcode()).implicit_defs();
2913 if (SUImpDefs.
empty() && !SURegMask)
2915 for (
unsigned i = NumDefs, e =
N->getNumValues(); i != e; ++i) {
2916 MVT VT =
N->getSimpleValueType(i);
2917 if (VT == MVT::Glue || VT == MVT::Other)
2919 if (!
N->hasAnyUseOfValue(i))
2925 if (
TRI->regsOverlap(Reg, SUReg))
2963void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {
2965 for (
SUnit &SU : *SUnits) {
2978 cast<RegisterSDNode>(
N->getOperand(1))->getReg().isVirtual())
2981 SDNode *PredFrameSetup =
nullptr;
2996 PredFrameSetup = PredND;
3001 if (PredFrameSetup !=
nullptr)
3005 SUnit *PredSU =
nullptr;
3024 cast<RegisterSDNode>(
N->getOperand(1))->getReg().isVirtual())
3028 for (
const SDep &PredSucc : PredSU->
Succs) {
3030 if (PredSuccSU == &SU)
continue;
3034 goto outer_loop_continue;
3038 goto outer_loop_continue;
3040 if (scheduleDAG->IsReachable(&SU, PredSuccSU))
3041 goto outer_loop_continue;
3047 dbgs() <<
" Prescheduling SU #" << SU.
NodeNum <<
" next to PredSU #"
3049 <<
" to guide scheduling in the presence of multiple uses\n");
3050 for (
unsigned i = 0; i != PredSU->
Succs.size(); ++i) {
3054 if (SuccSU != &SU) {
3056 scheduleDAG->RemovePred(SuccSU, Edge);
3057 scheduleDAG->AddPredQueued(&SU, Edge);
3059 scheduleDAG->AddPredQueued(SuccSU, Edge);
3063 outer_loop_continue:;
3074void RegReductionPQBase::AddPseudoTwoAddrDeps() {
3075 for (
SUnit &SU : *SUnits) {
3084 unsigned Opc =
Node->getMachineOpcode();
3088 for (
unsigned j = 0;
j != NumOps; ++
j) {
3112 while (SuccSU->
Succs.size() == 1 &&
3115 TargetOpcode::COPY_TO_REGCLASS)
3116 SuccSU = SuccSU->
Succs.front().getSUnit();
3129 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
3130 SuccOpc == TargetOpcode::INSERT_SUBREG ||
3131 SuccOpc == TargetOpcode::SUBREG_TO_REG)
3134 (!canClobber(SuccSU, DUSU) ||
3137 !scheduleDAG->IsReachable(SuccSU, &SU)) {
3139 <<
" Adding a pseudo-two-addr edge from SU #"
3158 BURegReductionPriorityQueue *PQ =
3159 new BURegReductionPriorityQueue(*IS->
MF,
false,
false,
TII,
TRI,
nullptr);
3160 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
false, PQ, OptLevel);
3161 PQ->setScheduleDAG(SD);
3172 SrcRegReductionPriorityQueue *PQ =
3173 new SrcRegReductionPriorityQueue(*IS->
MF,
false,
true,
TII,
TRI,
nullptr);
3174 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
false, PQ, OptLevel);
3175 PQ->setScheduleDAG(SD);
3187 HybridBURRPriorityQueue *PQ =
3188 new HybridBURRPriorityQueue(*IS->
MF,
true,
false,
TII,
TRI, TLI);
3190 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
true, PQ, OptLevel);
3191 PQ->setScheduleDAG(SD);
3202 ILPBURRPriorityQueue *PQ =
3203 new ILPBURRPriorityQueue(*IS->
MF,
true,
false,
TII,
TRI, TLI);
3204 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
true, PQ, OptLevel);
3205 PQ->setScheduleDAG(SD);
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
static bool canEnableCoalescing(SUnit *SU)
static RegisterScheduler sourceListDAGScheduler("source", "Similar to list-burr but schedules in source " "order when possible", createSourceListDAGScheduler)
static cl::opt< bool > DisableSchedCycles("disable-sched-cycles", cl::Hidden, cl::init(false), cl::desc("Disable cycle-level precision during preRA scheduling"))
static cl::opt< bool > DisableSchedStalls("disable-sched-stalls", cl::Hidden, cl::init(true), cl::desc("Disable no-stall priority in sched=list-ilp"))
static bool hasOnlyLiveInOpers(const SUnit *SU)
hasOnlyLiveInOpers - Return true if SU has only value predecessors that are CopyFromReg from a virtua...
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 hasOnlyLiveOutUses(const SUnit *SU)
hasOnlyLiveOutUses - Return true if SU has only value successors that are CopyToReg to a virtual regi...
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 > DisableSchedCriticalPath("disable-sched-critical-path", cl::Hidden, cl::init(false), cl::desc("Disable critical path priority in sched=list-ilp"))
static cl::opt< bool > Disable2AddrHack("disable-2addr-hack", cl::Hidden, cl::init(true), cl::desc("Disable scheduler's two-address hack"))
static void CheckForLiveRegDef(SUnit *SU, unsigned Reg, SUnit **LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs, const TargetRegisterInfo *TRI, const SDNode *Node=nullptr)
CheckForLiveRegDef - Return true and update live register vector if the specified register def of the...
static RegisterScheduler ILPListDAGScheduler("list-ilp", "Bottom-up register pressure aware list scheduling " "which tries to balance ILP and register pressure", createILPListDAGScheduler)
static void resetVRegCycle(SUnit *SU)
static RegisterScheduler hybridListDAGScheduler("list-hybrid", "Bottom-up register pressure aware list scheduling " "which tries to balance latency and register pressure", createHybridListDAGScheduler)
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...
static cl::opt< bool > DisableSchedPhysRegJoin("disable-sched-physreg-join", cl::Hidden, cl::init(false), cl::desc("Disable physreg def-use affinity"))
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 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.
static bool BURRSort(SUnit *left, SUnit *right, RegReductionPQBase *SPQ)
static cl::opt< bool > DisableSchedRegPressure("disable-sched-reg-pressure", cl::Hidden, cl::init(false), cl::desc("Disable regpressure priority in sched=list-ilp"))
static bool BUHasStall(SUnit *SU, int Height, RegReductionPQBase *SPQ)
static void initVRegCycle(SUnit *SU)
static constexpr unsigned RegSequenceCost
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"))
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...
static bool isOperandOf(const SUnit *SU, SDNode *N)
static cl::opt< bool > DisableSchedVRegCycle("disable-sched-vrcycle", cl::Hidden, cl::init(false), cl::desc("Disable virtual register cycle interference checks"))
static int checkSpecialNodes(const SUnit *left, const SUnit *right)
static cl::opt< bool > DisableSchedLiveUses("disable-sched-live-uses", cl::Hidden, cl::init(true), cl::desc("Disable live use priority in sched=list-ilp"))
static const uint32_t * getNodeRegMask(const SDNode *N)
getNodeRegMask - Returns the register mask attached to an SDNode, if any.
static unsigned closestSucc(const SUnit *SU)
closestSucc - Returns the scheduled cycle of the successor which is closest to the current cycle.
static cl::opt< unsigned > AvgIPC("sched-avg-ipc", cl::Hidden, cl::init(1), cl::desc("Average inst/cycle whan no target itinerary exists."))
static bool hasVRegCycleUse(const SUnit *SU)
static cl::opt< bool > DisableSchedHeight("disable-sched-height", cl::Hidden, cl::init(false), cl::desc("Disable scheduled-height priority in sched=list-ilp"))
static RegisterScheduler burrListDAGScheduler("list-burr", "Bottom-up register reduction list scheduling", createBURRListDAGScheduler)
static unsigned calcMaxScratches(const SUnit *SU)
calcMaxScratches - Returns an cost estimate of the worse case requirement for scratch registers,...
static unsigned CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector< unsigned > &SUNumbers)
CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref, RegReductionPQBase *SPQ)
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,...
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This file describes how to lower LLVM code to machine code.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
bool empty() const
empty - Check if the array is empty.
This class represents an Operation in the Expression.
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
ArrayRef< MCOperandInfo > operands() const
bool hasOptionalDef() const
Set if this instruction has an optional definition, e.g.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specified operand constraint if it is present.
ArrayRef< MCPhysReg > implicit_defs() const
Return a list of registers that are potentially written by any instance of this machine instruction.
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...
MCRegAliasIterator enumerates all registers aliasing Reg.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Wrapper class representing virtual and physical registers.
Represents one node in the SelectionDAG.
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode.
int getNodeId() const
Return the unique node id.
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
unsigned getIROrder() const
Return the node ordering.
void setNodeId(int Id)
Set unique node id.
MVT getSimpleValueType(unsigned ResNo) const
Return the type of a specified result as a simple type.
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
unsigned getMachineOpcode() const
This may only be called if isMachineOpcode returns true.
const SDValue & getOperand(unsigned Num) const
bool hasAnyUseOfValue(unsigned Value) const
Return true if there are any use of the indicated value.
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
SDNode * getNode() const
get the SDNode which holds the desired result
@ Data
Regular data dependence (aka true-dependence).
@ Artificial
Arbitrary strong DAG edge (no real dependence).
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
unsigned getReg() const
Returns the register associated with this edge.
Scheduling unit. This is a node in the scheduling DAG.
bool isCall
Is a function call.
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value.
unsigned NodeQueueId
Queue id of node.
unsigned NodeNum
Entry # of node in the node vector.
bool hasPhysRegClobbers
Has any physreg defs, used or not.
bool isCallOp
Is a function call operand.
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
void setHeightDirty()
Sets a flag in this node to indicate that its stored Height value will require recomputation the next...
bool isSucc(const SUnit *N) const
Tests if node N is a successor of this node.
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
unsigned short Latency
Node latency.
unsigned short NumRegDefsLeft
bool isPending
True once pending.
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
bool isScheduled
True once scheduled.
bool isAvailable
True once available.
bool isScheduleLow
True if preferable to schedule low.
bool hasPhysRegDefs
Has physreg defs that are being used.
SmallVector< SDep, 4 > Succs
All sunit successors.
Sched::Preference SchedulingPref
Scheduling preference.
const TargetRegisterClass * CopySrcRC
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
bool isTwoAddress
Is a two-address instruction.
bool isCommutable
Is a commutable instruction.
bool isVRegCycle
May use and def the same vreg.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
RegDefIter - In place iteration over the values defined by an SUnit.
const SDNode * GetNode() const
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
SUnit * newSUnit(SDNode *N)
NewSUnit - Creates a new SUnit and return a ptr to it.
virtual void Schedule()=0
Schedule - Order nodes according to selected style, filling in the Sequence member.
virtual bool forceUnitLatencies() const
ForceUnitLatencies - Return true if all scheduling edges should be given a latency value of one.
SUnit * Clone(SUnit *Old)
Clone - Creates a clone of the specified SUnit.
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
void RemovePred(SUnit *M, SUnit *N)
Updates the topological ordering to accommodate an edge to be removed from the specified node N from ...
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
void AddSUnitWithoutPredecessors(const SUnit *SU)
Add a SUnit without predecessors to the end of the topological order.
void AddPred(SUnit *Y, SUnit *X)
Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y.
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
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...
virtual void dumpNode(const SUnit &SU) const =0
HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...
unsigned getMaxLookAhead() const
virtual void RecedeCycle()
RecedeCycle - This callback is invoked whenever the next bottom-up instruction to be scheduled cannot...
virtual void Reset()
Reset - This callback is invoked when a new block of instructions is about to be schedule.
virtual void EmitInstruction(SUnit *)
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
virtual bool atIssueLimit() const
atIssueLimit - Return true if no more instructions may be issued in this cycle.
virtual HazardType getHazardType(SUnit *, int Stalls=0)
getHazardType - Return the hazard type of emitting this node.
This interface is used to plug different priorities computation algorithms into the list scheduler.
void setCurCycle(unsigned Cycle)
virtual void remove(SUnit *SU)=0
virtual void releaseState()=0
virtual void scheduledNode(SUnit *)
As each node is scheduled, this method is invoked.
virtual bool isReady(SUnit *) const
virtual bool tracksRegPressure() const
virtual void dump(ScheduleDAG *) const
bool hasReadyFilter() const
virtual void initNodes(std::vector< SUnit > &SUnits)=0
virtual bool empty() const =0
virtual void unscheduledNode(SUnit *)
virtual void addNode(const SUnit *SU)=0
virtual void updateNode(const SUnit *SU)=0
virtual void push(SUnit *U)=0
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
const TargetLowering * TLI
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
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...
virtual uint8_t getRepRegClassCostFor(MVT VT) const
Return the cost of the 'representative' register class for the specified value type.
virtual const TargetRegisterClass * getRepRegClassFor(MVT VT) const
Return the 'representative' register class for the specified value type.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
unsigned getID() const
Return the register class ID number.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual unsigned getRegPressureLimit(const TargetRegisterClass *RC, MachineFunction &MF) const
Return the register pressure "high water mark" for the specific register class.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ MERGE_VALUES
MERGE_VALUES - This node takes multiple discrete operands and returns them all as its individual resu...
@ EH_LABEL
EH_LABEL - Represents a label in mid basic block used to track locations needed for debug and excepti...
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
@ EntryToken
EntryToken - This is the marker used to indicate the start of a region.
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
@ LIFETIME_START
This corresponds to the llvm.lifetime.
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
@ TokenFactor
TokenFactor - This node takes multiple tokens as input and produces a single token result.
@ INLINEASM
INLINEASM - Represents an inline asm block.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
ScheduleDAGSDNodes * createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createBURRListDAGScheduler - This creates a bottom up register usage reduction list scheduler.
ScheduleDAGSDNodes * createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel)
createHybridListDAGScheduler - This creates a bottom up register pressure aware list scheduler that m...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
CodeGenOptLevel
Code generation optimization level.
ScheduleDAGSDNodes * createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createBURRListDAGScheduler - This creates a bottom up list scheduler that schedules nodes in source c...
ScheduleDAGSDNodes * createILPListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel)
createILPListDAGScheduler - This creates a bottom up register pressure aware list scheduler that trie...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Description of the encoding of one expression Op.