38#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;
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;
212 bool IsReachable(
const SUnit *SU,
const SUnit *TargetSU) {
218 bool WillCreateCycle(
SUnit *SU,
SUnit *TargetSU) {
225 void AddPredQueued(
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();
281 if (NewNode->
NodeNum >= NumSUnits)
288 unsigned NumSUnits = SUnits.size();
291 if (NewNode->
NodeNum >= NumSUnits)
315 unsigned &RegClass,
unsigned &Cost,
326 Register Reg = cast<RegisterSDNode>(
Node->getOperand(1))->getReg();
328 RegClass = RC->
getID();
333 unsigned Opcode =
Node->getMachineOpcode();
334 if (Opcode == TargetOpcode::REG_SEQUENCE) {
335 unsigned DstRCIdx = cast<ConstantSDNode>(
Node->getOperand(0))->getZExtValue();
337 RegClass = RC->
getID();
345 assert(RC &&
"Not a valid register class");
346 RegClass = RC->
getID();
357void ScheduleDAGRRList::Schedule() {
359 <<
" '" << BB->getName() <<
"' **********\n");
368 LiveRegDefs.reset(
new SUnit*[
TRI->getNumRegs() + 1]());
369 LiveRegGens.reset(
new SUnit*[
TRI->getNumRegs() + 1]());
370 CallSeqEndForStart.
clear();
371 assert(Interferences.
empty() && LRegsMap.empty() &&
"stale Interferences");
374 BuildSchedGraph(
nullptr);
384 ListScheduleBottomUp();
389 dbgs() <<
"*** Final schedule ***\n";
401void ScheduleDAGRRList::ReleasePred(
SUnit *SU,
const SDep *PredEdge) {
406 dbgs() <<
"*** Scheduling failed! ***\n";
408 dbgs() <<
" has been released too many times!\n";
414 if (!forceUnitLatencies()) {
426 if (Height < MinAvailableCycle)
427 MinAvailableCycle = Height;
429 if (isReady(PredSU)) {
430 AvailableQueue->
push(PredSU);
436 PendingQueue.push_back(PredSU);
454 for (
const SDValue &Op :
N->op_values())
460 if (
N->isMachineOpcode()) {
461 if (
N->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
463 }
else if (
N->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
470 for (
const SDValue &Op :
N->op_values())
473 goto found_chain_operand;
476 found_chain_operand:;
500 unsigned BestMaxNest = MaxNest;
501 for (
const SDValue &Op :
N->op_values()) {
502 unsigned MyNestLevel = NestLevel;
503 unsigned MyMaxNest = MaxNest;
505 MyNestLevel, MyMaxNest,
TII))
506 if (!Best || (MyMaxNest > BestMaxNest)) {
508 BestMaxNest = MyMaxNest;
512 MaxNest = BestMaxNest;
516 if (
N->isMachineOpcode()) {
517 if (
N->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
519 MaxNest = std::max(MaxNest, NestLevel);
520 }
else if (
N->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
528 for (
const SDValue &Op :
N->op_values())
531 goto found_chain_operand;
534 found_chain_operand:;
557void ScheduleDAGRRList::ReleasePredecessors(
SUnit *SU) {
560 ReleasePred(SU, &Pred);
566 SUnit *RegDef = LiveRegDefs[Pred.
getReg()]; (void)RegDef;
568 "interference on register dependence");
570 if (!LiveRegGens[Pred.
getReg()]) {
572 LiveRegGens[Pred.
getReg()] = SU;
580 unsigned CallResource =
TRI->getNumRegs();
581 if (!LiveRegDefs[CallResource])
583 if (
Node->isMachineOpcode() &&
584 Node->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
585 unsigned NestLevel = 0;
586 unsigned MaxNest = 0;
588 assert(
N &&
"Must find call sequence start");
591 CallSeqEndForStart[
Def] = SU;
594 LiveRegDefs[CallResource] =
Def;
595 LiveRegGens[CallResource] = SU;
602void ScheduleDAGRRList::ReleasePending() {
604 assert(PendingQueue.empty() &&
"pending instrs not allowed in this mode");
609 if (AvailableQueue->
empty())
610 MinAvailableCycle = std::numeric_limits<unsigned>::max();
614 for (
unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
615 unsigned ReadyCycle = PendingQueue[i]->getHeight();
616 if (ReadyCycle < MinAvailableCycle)
617 MinAvailableCycle = ReadyCycle;
619 if (PendingQueue[i]->isAvailable) {
620 if (!isReady(PendingQueue[i]))
622 AvailableQueue->
push(PendingQueue[i]);
624 PendingQueue[i]->isPending =
false;
625 PendingQueue[i] = PendingQueue.back();
626 PendingQueue.pop_back();
632void ScheduleDAGRRList::AdvanceToCycle(
unsigned NextCycle) {
633 if (NextCycle <= CurCycle)
640 CurCycle = NextCycle;
643 for (; CurCycle != NextCycle; ++CurCycle) {
654void ScheduleDAGRRList::AdvancePastStalls(
SUnit *SU) {
671 AdvanceToCycle(ReadyCycle);
691 AdvanceToCycle(CurCycle + Stalls);
696void ScheduleDAGRRList::EmitNode(
SUnit *SU) {
707 "This target-independent node should not be scheduled.");
739void ScheduleDAGRRList::ScheduleNodeBottomUp(
SUnit *SU) {
744 if (CurCycle < SU->getHeight())
746 <<
"] pipeline stall!\n");
766 AdvanceToCycle(CurCycle + 1);
770 ReleasePredecessors(SU);
776 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
778 LiveRegDefs[Succ.
getReg()] =
nullptr;
779 LiveRegGens[Succ.
getReg()] =
nullptr;
780 releaseInterferences(Succ.
getReg());
785 unsigned CallResource =
TRI->getNumRegs();
786 if (LiveRegDefs[CallResource] == SU)
789 if (SUNode->isMachineOpcode() &&
790 SUNode->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
791 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
793 LiveRegDefs[CallResource] =
nullptr;
794 LiveRegGens[CallResource] =
nullptr;
795 releaseInterferences(CallResource);
816 AdvanceToCycle(CurCycle + 1);
823void ScheduleDAGRRList::CapturePred(
SDep *PredEdge) {
828 AvailableQueue->
remove(PredSU);
832 "NumSuccsLeft will overflow!");
838void ScheduleDAGRRList::UnscheduleNodeBottomUp(
SUnit *SU) {
845 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
847 "Physical register dependency violated?");
849 LiveRegDefs[Pred.
getReg()] =
nullptr;
850 LiveRegGens[Pred.
getReg()] =
nullptr;
851 releaseInterferences(Pred.
getReg());
857 unsigned CallResource =
TRI->getNumRegs();
860 if (SUNode->isMachineOpcode() &&
861 SUNode->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
862 SUnit *SeqEnd = CallSeqEndForStart[SU];
863 assert(SeqEnd &&
"Call sequence start/end must be known");
864 assert(!LiveRegDefs[CallResource]);
865 assert(!LiveRegGens[CallResource]);
867 LiveRegDefs[CallResource] = SU;
868 LiveRegGens[CallResource] = SeqEnd;
874 if (LiveRegGens[CallResource] == SU)
877 if (SUNode->isMachineOpcode() &&
878 SUNode->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
879 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
880 assert(LiveRegDefs[CallResource]);
881 assert(LiveRegGens[CallResource]);
883 LiveRegDefs[CallResource] =
nullptr;
884 LiveRegGens[CallResource] =
nullptr;
885 releaseInterferences(CallResource);
889 for (
auto &Succ : SU->
Succs) {
892 if (!LiveRegDefs[Reg])
896 LiveRegDefs[
Reg] = SU;
900 if (!LiveRegGens[Reg]) {
903 for (
auto &Succ2 : SU->
Succs) {
904 if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
905 Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())
906 LiveRegGens[
Reg] = Succ2.getSUnit();
920 PendingQueue.push_back(SU);
923 AvailableQueue->
push(SU);
930void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {
933 unsigned LookAhead = std::min((
unsigned)
Sequence.size(),
938 std::vector<SUnit *>::const_iterator
I = (
Sequence.end() - LookAhead);
939 unsigned HazardCycle = (*I)->getHeight();
942 for (; SU->
getHeight() > HazardCycle; ++HazardCycle) {
951void ScheduleDAGRRList::BacktrackBottomUp(
SUnit *SU,
SUnit *BtSU) {
957 UnscheduleNodeBottomUp(OldSU);
966 RestoreHazardCheckerBottomUp();
976 if (SUNode->isOperandOf(
N))
983SUnit *ScheduleDAGRRList::TryUnfoldSU(
SUnit *SU) {
987 if (!
TII->unfoldMemoryOperand(*DAG,
N, NewNodes))
992 if (NewNodes.
size() == 3)
995 assert(NewNodes.
size() == 2 &&
"Expected a load folding node!");
998 SDNode *LoadNode = NewNodes[0];
999 unsigned NumVals =
N->getNumValues();
1005 bool isNewLoad =
true;
1008 LoadSU = &SUnits[LoadNode->
getNodeId()];
1015 LoadSU = CreateNewSUnit(LoadNode);
1018 InitNumRegDefsLeft(LoadSU);
1019 computeLatency(LoadSU);
1025 if (
N->getNodeId() != -1) {
1026 NewSU = &SUnits[
N->getNodeId()];
1034 NewSU = CreateNewSUnit(
N);
1047 InitNumRegDefsLeft(NewSU);
1048 computeLatency(NewSU);
1054 for (
unsigned i = 0; i != NumVals; ++i)
1056 DAG->ReplaceAllUsesOfValueWith(
SDValue(SU->
getNode(), OldNumVals - 1),
1081 for (
const SDep &Pred : ChainPreds) {
1082 RemovePred(SU, Pred);
1084 AddPredQueued(LoadSU, Pred);
1086 for (
const SDep &Pred : LoadPreds) {
1087 RemovePred(SU, Pred);
1089 AddPredQueued(LoadSU, Pred);
1091 for (
const SDep &Pred : NodePreds) {
1092 RemovePred(SU, Pred);
1093 AddPredQueued(NewSU, Pred);
1095 for (
SDep &
D : NodeSuccs) {
1096 SUnit *SuccDep =
D.getSUnit();
1098 RemovePred(SuccDep,
D);
1100 AddPredQueued(SuccDep,
D);
1106 for (
SDep &
D : ChainSuccs) {
1107 SUnit *SuccDep =
D.getSUnit();
1109 RemovePred(SuccDep,
D);
1112 AddPredQueued(SuccDep,
D);
1120 AddPredQueued(NewSU,
D);
1123 AvailableQueue->
addNode(LoadSU);
1125 AvailableQueue->
addNode(NewSU);
1137SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(
SUnit *SU) {
1145 if (
N->getGluedNode() &&
1146 !
TII->canCopyGluedNodeDuringSchedule(
N)) {
1149 <<
"Giving up because it has incoming glue and the target does not "
1150 "want to copy it\n");
1155 bool TryUnfold =
false;
1156 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i) {
1157 MVT VT =
N->getSimpleValueType(i);
1159 LLVM_DEBUG(
dbgs() <<
"Giving up because it has outgoing glue\n");
1164 for (
const SDValue &Op :
N->op_values()) {
1165 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
1166 if (VT ==
MVT::Glue && !
TII->canCopyGluedNodeDuringSchedule(
N)) {
1168 dbgs() <<
"Giving up because it one of the operands is glue and "
1169 "the target does not want to copy it\n");
1176 SUnit *UnfoldSU = TryUnfoldSU(SU);
1187 NewSU = CreateClone(SU);
1192 AddPredQueued(NewSU, Pred);
1208 AddPredQueued(SuccSU,
D);
1213 for (
const auto &[DelSU, DelD] : DelDeps)
1214 RemovePred(DelSU, DelD);
1217 AvailableQueue->
addNode(NewSU);
1225void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(
SUnit *SU,
unsigned Reg,
1229 SUnit *CopyFromSU = CreateNewSUnit(
nullptr);
1233 SUnit *CopyToSU = CreateNewSUnit(
nullptr);
1246 D.setSUnit(CopyToSU);
1247 AddPredQueued(SuccSU,
D);
1257 for (
const auto &[DelSU, DelD] : DelDeps)
1258 RemovePred(DelSU, DelD);
1261 FromDep.setLatency(SU->
Latency);
1262 AddPredQueued(CopyFromSU, FromDep);
1264 ToDep.setLatency(CopyFromSU->
Latency);
1265 AddPredQueued(CopyToSU, ToDep);
1268 AvailableQueue->
addNode(CopyFromSU);
1269 AvailableQueue->
addNode(CopyToSU);
1270 Copies.push_back(CopyFromSU);
1271 Copies.push_back(CopyToSU);
1288 "Physical reg def must be in implicit def list!");
1296 return N->getSimpleValueType(NumRes);
1309 if (!LiveRegDefs[*AliasI])
continue;
1312 if (LiveRegDefs[*AliasI] == SU)
continue;
1315 if (
Node && LiveRegDefs[*AliasI]->getNode() ==
Node)
1319 if (RegAdded.
insert(*AliasI).second) {
1332 for (
unsigned i = 1, e = LiveRegDefs.
size()-1; i != e; ++i) {
1333 if (!LiveRegDefs[i])
continue;
1334 if (LiveRegDefs[i] == SU)
continue;
1336 if (RegAdded.
insert(i).second)
1343 for (
const SDValue &Op :
N->op_values())
1344 if (
const auto *RegOp = dyn_cast<RegisterMaskSDNode>(Op.getNode()))
1345 return RegOp->getRegMask();
1353bool ScheduleDAGRRList::
1355 if (NumLiveRegs == 0)
1366 RegAdded, LRegs,
TRI);
1373 unsigned NumOps =
Node->getNumOperands();
1379 cast<ConstantSDNode>(
Node->getOperand(i))->getZExtValue();
1387 for (; NumVals; --NumVals, ++i) {
1389 if (
Reg.isPhysical())
1400 if (
Reg.isPhysical()) {
1401 SDNode *SrcNode =
Node->getOperand(2).getNode();
1407 if (!
Node->isMachineOpcode())
1412 if (
Node->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
1414 unsigned CallResource =
TRI->getNumRegs();
1415 if (LiveRegDefs[CallResource]) {
1416 SDNode *Gen = LiveRegGens[CallResource]->getNode();
1420 RegAdded.
insert(CallResource).second)
1435 for (
unsigned i = 0; i < MCID.
getNumDefs(); ++i)
1436 if (MCID.
operands()[i].isOptionalDef()) {
1438 Register Reg = cast<RegisterSDNode>(OptionalDef)->getReg();
1446 return !LRegs.
empty();
1449void ScheduleDAGRRList::releaseInterferences(
unsigned Reg) {
1451 for (
unsigned i = Interferences.
size(); i > 0; --i) {
1452 SUnit *SU = Interferences[i-1];
1453 LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);
1465 AvailableQueue->
push(SU);
1467 if (i < Interferences.
size())
1468 Interferences[i-1] = Interferences.
back();
1470 LRegsMap.erase(LRegsPos);
1478SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
1479 SUnit *CurSU = AvailableQueue->
empty() ? nullptr : AvailableQueue->
pop();
1480 auto FindAvailableNode = [&]() {
1483 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
1486 if (LRegs[0] ==
TRI->getNumRegs())
dbgs() <<
"CallResource";
1489 auto [LRegsIter, LRegsInserted] = LRegsMap.try_emplace(CurSU, LRegs);
1490 if (LRegsInserted) {
1497 LRegsIter->second = LRegs;
1499 CurSU = AvailableQueue->
pop();
1502 FindAvailableNode();
1514 for (
SUnit *TrySU : Interferences) {
1519 SUnit *BtSU =
nullptr;
1520 unsigned LiveCycle = std::numeric_limits<unsigned>::max();
1521 for (
unsigned Reg : LRegs) {
1522 if (LiveRegGens[Reg]->getHeight() < LiveCycle) {
1523 BtSU = LiveRegGens[
Reg];
1527 if (!WillCreateCycle(TrySU, BtSU)) {
1529 BacktrackBottomUp(TrySU, BtSU);
1536 AvailableQueue->
remove(BtSU);
1539 <<
") to SU(" << TrySU->NodeNum <<
")\n");
1544 if (!TrySU->isAvailable || !TrySU->NodeQueueId) {
1545 LLVM_DEBUG(
dbgs() <<
"TrySU not available; choosing node from queue\n");
1546 CurSU = AvailableQueue->
pop();
1550 AvailableQueue->
remove(TrySU);
1553 FindAvailableNode();
1565 SUnit *TrySU = Interferences[0];
1567 assert(LRegs.
size() == 1 &&
"Can't handle this yet!");
1568 unsigned Reg = LRegs[0];
1572 TRI->getMinimalPhysRegClass(Reg, VT);
1582 SUnit *NewDef =
nullptr;
1584 NewDef = CopyAndMoveSuccessors(LRDef);
1585 if (!DestRC && !NewDef)
1591 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC,
Copies);
1593 <<
" to SU #" <<
Copies.front()->NodeNum <<
"\n");
1599 <<
" to SU #" << TrySU->
NodeNum <<
"\n");
1600 LiveRegDefs[
Reg] = NewDef;
1605 assert(CurSU &&
"Unable to resolve live physical register dependencies!");
1611void ScheduleDAGRRList::ListScheduleBottomUp() {
1613 ReleasePredecessors(&ExitSU);
1616 if (!SUnits.empty()) {
1617 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
1618 assert(RootSU->
Succs.empty() &&
"Graph root shouldn't have successors!");
1620 AvailableQueue->
push(RootSU);
1626 while (!AvailableQueue->
empty() || !Interferences.empty()) {
1628 AvailableQueue->
dump(
this));
1632 SUnit *SU = PickNodeToScheduleBottomUp();
1634 AdvancePastStalls(SU);
1636 ScheduleNodeBottomUp(SU);
1638 while (AvailableQueue->
empty() && !PendingQueue.empty()) {
1640 assert(MinAvailableCycle < std::numeric_limits<unsigned>::max() &&
1641 "MinAvailableCycle uninitialized");
1642 AdvanceToCycle(std::max(CurCycle + 1, MinAvailableCycle));
1650 VerifyScheduledSequence(
true);
1656class RegReductionPQBase;
1659 bool isReady(
SUnit* SU,
unsigned CurCycle)
const {
return true; }
1664struct reverse_sort :
public queue_sort {
1667 reverse_sort(SF &sf) : SortFunc(sf) {}
1669 bool operator()(
SUnit* left,
SUnit* right)
const {
1672 return SortFunc(right, left);
1679struct bu_ls_rr_sort :
public queue_sort {
1682 HasReadyFilter =
false
1685 RegReductionPQBase *SPQ;
1687 bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1689 bool operator()(
SUnit* left,
SUnit* right)
const;
1693struct src_ls_rr_sort :
public queue_sort {
1696 HasReadyFilter =
false
1699 RegReductionPQBase *SPQ;
1701 src_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1703 bool operator()(
SUnit* left,
SUnit* right)
const;
1707struct hybrid_ls_rr_sort :
public queue_sort {
1710 HasReadyFilter =
false
1713 RegReductionPQBase *SPQ;
1715 hybrid_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1717 bool isReady(
SUnit *SU,
unsigned CurCycle)
const;
1719 bool operator()(
SUnit* left,
SUnit* right)
const;
1724struct ilp_ls_rr_sort :
public queue_sort {
1727 HasReadyFilter =
false
1730 RegReductionPQBase *SPQ;
1732 ilp_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1734 bool isReady(
SUnit *SU,
unsigned CurCycle)
const;
1736 bool operator()(
SUnit* left,
SUnit* right)
const;
1741 std::vector<SUnit *>
Queue;
1742 unsigned CurQueueId = 0;
1743 bool TracksRegPressure;
1747 std::vector<SUnit> *SUnits;
1753 ScheduleDAGRRList *scheduleDAG =
nullptr;
1756 std::vector<unsigned> SethiUllmanNumbers;
1763 std::vector<unsigned> RegLimit;
1767 bool hasReadyFilter,
1774 SrcOrder(srcorder), MF(mf),
TII(tii),
TRI(tri), TLI(tli) {
1775 if (TracksRegPressure) {
1776 unsigned NumRC =
TRI->getNumRegClasses();
1777 RegLimit.resize(NumRC);
1779 std::fill(RegLimit.begin(), RegLimit.end(), 0);
1786 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1787 scheduleDAG = scheduleDag;
1791 return scheduleDAG->getHazardRec();
1794 void initNodes(std::vector<SUnit> &sunits)
override;
1802 SethiUllmanNumbers.clear();
1806 unsigned getNodePriority(
const SUnit *SU)
const;
1808 unsigned getNodeOrdering(
const SUnit *SU)
const {
1814 bool empty()
const override {
return Queue.empty(); }
1817 assert(!
U->NodeQueueId &&
"Node in the queue already");
1818 U->NodeQueueId = ++CurQueueId;
1825 std::vector<SUnit *>::iterator
I =
llvm::find(Queue, SU);
1826 if (
I != std::prev(
Queue.end()))
1834 void dumpRegPressure()
const;
1836 bool HighRegPressure(
const SUnit *SU)
const;
1838 bool MayReduceRegPressure(
SUnit *SU)
const;
1840 int RegPressureDiff(
SUnit *SU,
unsigned &LiveUses)
const;
1847 bool canClobber(
const SUnit *SU,
const SUnit *Op);
1848 void AddPseudoTwoAddrDeps();
1849 void PrescheduleNodesWithMultipleUses();
1850 void CalculateSethiUllmanNumbers();
1854static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1855 unsigned BestIdx = 0;
1858 for (
unsigned I = 1,
E = std::min(Q.size(), (
decltype(Q.size()))1000);
I !=
E;
1860 if (Picker(Q[BestIdx], Q[
I]))
1863 if (BestIdx + 1 != Q.size())
1870SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker,
ScheduleDAG *DAG) {
1873 reverse_sort<SF> RPicker(Picker);
1874 return popFromQueueImpl(Q, RPicker);
1878 return popFromQueueImpl(Q, Picker);
1889class RegReductionPriorityQueue :
public RegReductionPQBase {
1899 : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
1903 bool isBottomUp()
const override {
return SF::IsBottomUp; }
1905 bool isReady(
SUnit *U)
const override {
1906 return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
1909 SUnit *pop()
override {
1910 if (
Queue.empty())
return nullptr;
1912 SUnit *
V = popFromQueue(Queue, Picker, scheduleDAG);
1917#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1920 std::vector<SUnit *> DumpQueue =
Queue;
1921 SF DumpPicker = Picker;
1922 while (!DumpQueue.empty()) {
1923 SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
1931using BURegReductionPriorityQueue = RegReductionPriorityQueue<bu_ls_rr_sort>;
1932using SrcRegReductionPriorityQueue = RegReductionPriorityQueue<src_ls_rr_sort>;
1933using HybridBURRPriorityQueue = RegReductionPriorityQueue<hybrid_ls_rr_sort>;
1934using ILPBURRPriorityQueue = RegReductionPriorityQueue<ilp_ls_rr_sort>;
1951 if (LSchedLow != RSchedLow)
1952 return LSchedLow < RSchedLow ? 1 : -1;
1960 if (SUNumbers[SU->
NodeNum] != 0)
1961 return SUNumbers[SU->
NodeNum];
1965 WorkState(
const SUnit *SU) : SU(SU) {}
1967 unsigned PredsProcessed = 0;
1972 while (!WorkList.
empty()) {
1973 auto &Temp = WorkList.
back();
1974 auto *TempSU = Temp.SU;
1975 bool AllPredsKnown =
true;
1977 for (
unsigned P = Temp.PredsProcessed; P < TempSU->Preds.size(); ++
P) {
1978 auto &Pred = TempSU->Preds[
P];
1979 if (Pred.
isCtrl())
continue;
1981 if (SUNumbers[PredSU->
NodeNum] == 0) {
1984 for (
auto It : WorkList)
1985 assert(It.SU != PredSU &&
"Trying to push an element twice?");
1988 Temp.PredsProcessed =
P + 1;
1989 WorkList.push_back(PredSU);
1990 AllPredsKnown =
false;
1999 unsigned SethiUllmanNumber = 0;
2001 for (
const SDep &Pred : TempSU->Preds) {
2002 if (Pred.
isCtrl())
continue;
2004 unsigned PredSethiUllman = SUNumbers[PredSU->
NodeNum];
2005 assert(PredSethiUllman > 0 &&
"We should have evaluated this pred!");
2006 if (PredSethiUllman > SethiUllmanNumber) {
2007 SethiUllmanNumber = PredSethiUllman;
2009 }
else if (PredSethiUllman == SethiUllmanNumber)
2013 SethiUllmanNumber += Extra;
2014 if (SethiUllmanNumber == 0)
2015 SethiUllmanNumber = 1;
2016 SUNumbers[TempSU->NodeNum] = SethiUllmanNumber;
2020 assert(SUNumbers[SU->
NodeNum] > 0 &&
"SethiUllman should never be zero!");
2021 return SUNumbers[SU->
NodeNum];
2026void RegReductionPQBase::CalculateSethiUllmanNumbers() {
2027 SethiUllmanNumbers.assign(SUnits->size(), 0);
2029 for (
const SUnit &SU : *SUnits)
2033void RegReductionPQBase::addNode(
const SUnit *SU) {
2034 unsigned SUSize = SethiUllmanNumbers.size();
2035 if (SUnits->size() > SUSize)
2036 SethiUllmanNumbers.resize(SUSize*2, 0);
2040void RegReductionPQBase::updateNode(
const SUnit *SU) {
2041 SethiUllmanNumbers[SU->
NodeNum] = 0;
2047unsigned RegReductionPQBase::getNodePriority(
const SUnit *SU)
const {
2054 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2055 Opc == TargetOpcode::SUBREG_TO_REG ||
2056 Opc == TargetOpcode::INSERT_SUBREG)
2072 return SethiUllmanNumbers[SU->
NodeNum];
2074 unsigned Priority = SethiUllmanNumbers[SU->
NodeNum];
2078 return (NP > 0) ? NP : 0;
2088#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2095 << RegLimit[Id] <<
'\n');
2100bool RegReductionPQBase::HighRegPressure(
const SUnit *SU)
const {
2114 RegDefPos.
IsValid(); RegDefPos.Advance()) {
2115 unsigned RCId,
Cost;
2118 if ((RegPressure[RCId] + Cost) >= RegLimit[RCId])
2125bool RegReductionPQBase::MayReduceRegPressure(
SUnit *SU)
const {
2128 if (!
N->isMachineOpcode() || !SU->
NumSuccs)
2131 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2132 for (
unsigned i = 0; i != NumDefs; ++i) {
2133 MVT VT =
N->getSimpleValueType(i);
2134 if (!
N->hasAnyUseOfValue(i))
2137 if (RegPressure[RCId] >= RegLimit[RCId])
2150int RegReductionPQBase::RegPressureDiff(
SUnit *SU,
unsigned &LiveUses)
const {
2165 RegDefPos.
IsValid(); RegDefPos.Advance()) {
2166 MVT VT = RegDefPos.GetValue();
2168 if (RegPressure[RCId] >= RegLimit[RCId])
2174 if (!
N || !
N->isMachineOpcode() || !SU->
NumSuccs)
2177 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2178 for (
unsigned i = 0; i != NumDefs; ++i) {
2179 MVT VT =
N->getSimpleValueType(i);
2180 if (!
N->hasAnyUseOfValue(i))
2183 if (RegPressure[RCId] >= RegLimit[RCId])
2189void RegReductionPQBase::scheduledNode(
SUnit *SU) {
2190 if (!TracksRegPressure)
2223 RegDefPos.
IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2227 unsigned RCId,
Cost;
2239 RegDefPos.
IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2240 if (SkipRegDefs > 0)
2242 unsigned RCId,
Cost;
2244 if (RegPressure[RCId] < Cost) {
2248 <<
") has too many regdefs\n");
2258void RegReductionPQBase::unscheduledNode(
SUnit *SU) {
2259 if (!TracksRegPressure)
2265 if (!
N->isMachineOpcode()) {
2269 unsigned Opc =
N->getMachineOpcode();
2270 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2271 Opc == TargetOpcode::INSERT_SUBREG ||
2272 Opc == TargetOpcode::SUBREG_TO_REG ||
2273 Opc == TargetOpcode::REG_SEQUENCE ||
2274 Opc == TargetOpcode::IMPLICIT_DEF)
2296 if (POpc == TargetOpcode::IMPLICIT_DEF)
2298 if (POpc == TargetOpcode::EXTRACT_SUBREG ||
2299 POpc == TargetOpcode::INSERT_SUBREG ||
2300 POpc == TargetOpcode::SUBREG_TO_REG) {
2306 if (POpc == TargetOpcode::REG_SEQUENCE) {
2308 cast<ConstantSDNode>(PN->
getOperand(0))->getZExtValue();
2310 unsigned RCId = RC->
getID();
2317 for (
unsigned i = 0; i != NumDefs; ++i) {
2332 if (SU->
NumSuccs &&
N->isMachineOpcode()) {
2333 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2334 for (
unsigned i = NumDefs, e =
N->getNumValues(); i != e; ++i) {
2335 MVT VT =
N->getSimpleValueType(i);
2338 if (!
N->hasAnyUseOfValue(i))
2355 unsigned MaxHeight = 0;
2357 if (Succ.
isCtrl())
continue;
2364 if (Height > MaxHeight)
2373 unsigned Scratches = 0;
2375 if (Pred.
isCtrl())
continue;
2384 bool RetVal =
false;
2386 if (Pred.
isCtrl())
continue;
2392 if (Reg.isVirtual()) {
2406 bool RetVal =
false;
2408 if (Succ.
isCtrl())
continue;
2413 if (Reg.isVirtual()) {
2445 if (Pred.
isCtrl())
continue;
2457 if (Pred.
isCtrl())
continue;
2461 "VRegCycle def must be CopyFromReg");
2475 if (Pred.
isCtrl())
continue;
2489 if ((
int)SPQ->getCurCycle() < Height)
return true;
2490 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2499 RegReductionPQBase *SPQ) {
2504 int LHeight = (int)left->
getHeight() + LPenalty;
2505 int RHeight = (int)right->
getHeight() + RPenalty;
2518 if (LHeight != RHeight)
2519 return LHeight > RHeight ? 1 : -1;
2531 if (!SPQ->getHazardRec()->isEnabled()) {
2532 if (LHeight != RHeight)
2533 return LHeight > RHeight ? 1 : -1;
2535 int LDepth = left->
getDepth() - LPenalty;
2536 int RDepth = right->
getDepth() - RPenalty;
2537 if (LDepth != RDepth) {
2539 <<
") depth " << LDepth <<
" vs SU (" << right->
NodeNum
2540 <<
") depth " << RDepth <<
"\n");
2541 return LDepth < RDepth ? 1 : -1;
2557 if (LHasPhysReg != RHasPhysReg) {
2559 static const char *
const PhysRegMsg[] = {
" has no physreg",
2560 " defines a physreg" };
2563 << PhysRegMsg[LHasPhysReg] <<
" SU(" << right->
NodeNum
2564 <<
") " << PhysRegMsg[RHasPhysReg] <<
"\n");
2565 return LHasPhysReg < RHasPhysReg;
2570 unsigned LPriority = SPQ->getNodePriority(left);
2571 unsigned RPriority = SPQ->getNodePriority(right);
2577 RPriority = (RPriority > RNumVals) ? (RPriority - RNumVals) : 0;
2581 LPriority = (LPriority > LNumVals) ? (LPriority - LNumVals) : 0;
2584 if (LPriority != RPriority)
2585 return LPriority > RPriority;
2590 unsigned LOrder = SPQ->getNodeOrdering(left);
2591 unsigned ROrder = SPQ->getNodeOrdering(right);
2595 if ((LOrder || ROrder) && LOrder != ROrder)
2596 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2619 return LDist < RDist;
2624 if (LScratch != RScratch)
2625 return LScratch > RScratch;
2629 if ((left->
isCall && RPriority > 0) || (right->
isCall && LPriority > 0))
2648 "NodeQueueId cannot be zero");
2653bool bu_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2661bool src_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2665 unsigned LOrder = SPQ->getNodeOrdering(left);
2666 unsigned ROrder = SPQ->getNodeOrdering(right);
2670 if ((LOrder || ROrder) && LOrder != ROrder)
2671 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2680bool hybrid_ls_rr_sort::isReady(
SUnit *SU,
unsigned CurCycle)
const {
2681 static const unsigned ReadyDelay = 3;
2683 if (SPQ->MayReduceRegPressure(SU))
return true;
2685 if (SU->
getHeight() > (CurCycle + ReadyDelay))
return false;
2687 if (SPQ->getHazardRec()->getHazardType(SU, -ReadyDelay)
2695bool hybrid_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2703 bool LHigh = SPQ->HighRegPressure(left);
2704 bool RHigh = SPQ->HighRegPressure(right);
2707 if (LHigh && !RHigh) {
2712 else if (!LHigh && RHigh) {
2717 if (!LHigh && !RHigh) {
2727bool ilp_ls_rr_sort::isReady(
SUnit *SU,
unsigned CurCycle)
const {
2728 if (SU->
getHeight() > CurCycle)
return false;
2730 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2744 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2745 Opc == TargetOpcode::SUBREG_TO_REG ||
2746 Opc == TargetOpcode::INSERT_SUBREG)
2761bool ilp_ls_rr_sort::operator()(
SUnit *left,
SUnit *right)
const {
2769 unsigned LLiveUses = 0, RLiveUses = 0;
2770 int LPDiff = 0, RPDiff = 0;
2772 LPDiff = SPQ->RegPressureDiff(left, LLiveUses);
2773 RPDiff = SPQ->RegPressureDiff(right, RLiveUses);
2777 <<
"): " << LPDiff <<
" != SU(" << right->
NodeNum
2778 <<
"): " << RPDiff <<
"\n");
2779 return LPDiff > RPDiff;
2785 if (LReduce && !RReduce)
return false;
2786 if (RReduce && !LReduce)
return true;
2791 <<
" != SU(" << right->
NodeNum <<
"): " << RLiveUses
2793 return LLiveUses < RLiveUses;
2799 if (LStall != RStall)
2808 <<
"): " << right->
getDepth() <<
"\n");
2822void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
2826 AddPseudoTwoAddrDeps();
2828 if (!TracksRegPressure && !SrcOrder)
2829 PrescheduleNodesWithMultipleUses();
2831 CalculateSethiUllmanNumbers();
2834 if (scheduleDAG->BB->isSuccessor(scheduleDAG->BB))
2835 for (
SUnit &SU : sunits)
2843bool RegReductionPQBase::canClobber(
const SUnit *SU,
const SUnit *Op) {
2849 for (
unsigned i = 0; i != NumOps; ++i) {
2865 ScheduleDAGRRList *scheduleDAG,
2871 if (ImpDefs.
empty() && !RegMask)
2876 for (
const SDep &SuccPred : SuccSU->
Preds) {
2882 scheduleDAG->IsReachable(DepSU, SuccPred.
getSUnit()))
2889 if (
TRI->regsOverlap(ImpDef, SuccPred.
getReg()) &&
2890 scheduleDAG->IsReachable(DepSU, SuccPred.
getSUnit()))
2904 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2906 assert(!ImpDefs.
empty() &&
"Caller should check hasPhysRegDefs");
2909 if (!SUNode->isMachineOpcode())
2912 TII->get(SUNode->getMachineOpcode()).implicit_defs();
2914 if (SUImpDefs.
empty() && !SURegMask)
2916 for (
unsigned i = NumDefs, e =
N->getNumValues(); i != e; ++i) {
2917 MVT VT =
N->getSimpleValueType(i);
2920 if (!
N->hasAnyUseOfValue(i))
2926 if (
TRI->regsOverlap(Reg, SUReg))
2964void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {
2966 for (
SUnit &SU : *SUnits) {
2979 cast<RegisterSDNode>(
N->getOperand(1))->getReg().isVirtual())
2982 SDNode *PredFrameSetup =
nullptr;
2997 PredFrameSetup = PredND;
3002 if (PredFrameSetup !=
nullptr)
3006 SUnit *PredSU =
nullptr;
3025 cast<RegisterSDNode>(
N->getOperand(1))->getReg().isVirtual())
3029 for (
const SDep &PredSucc : PredSU->
Succs) {
3031 if (PredSuccSU == &SU)
continue;
3035 goto outer_loop_continue;
3039 goto outer_loop_continue;
3041 if (scheduleDAG->IsReachable(&SU, PredSuccSU))
3042 goto outer_loop_continue;
3048 dbgs() <<
" Prescheduling SU #" << SU.
NodeNum <<
" next to PredSU #"
3050 <<
" to guide scheduling in the presence of multiple uses\n");
3051 for (
unsigned i = 0; i != PredSU->
Succs.size(); ++i) {
3055 if (SuccSU != &SU) {
3057 scheduleDAG->RemovePred(SuccSU, Edge);
3058 scheduleDAG->AddPredQueued(&SU, Edge);
3060 scheduleDAG->AddPredQueued(SuccSU, Edge);
3064 outer_loop_continue:;
3075void RegReductionPQBase::AddPseudoTwoAddrDeps() {
3076 for (
SUnit &SU : *SUnits) {
3085 unsigned Opc =
Node->getMachineOpcode();
3089 for (
unsigned j = 0;
j != NumOps; ++
j) {
3113 while (SuccSU->
Succs.size() == 1 &&
3116 TargetOpcode::COPY_TO_REGCLASS)
3117 SuccSU = SuccSU->
Succs.front().getSUnit();
3130 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
3131 SuccOpc == TargetOpcode::INSERT_SUBREG ||
3132 SuccOpc == TargetOpcode::SUBREG_TO_REG)
3135 (!canClobber(SuccSU, DUSU) ||
3138 !scheduleDAG->IsReachable(SuccSU, &SU)) {
3140 <<
" Adding a pseudo-two-addr edge from SU #"
3160 BURegReductionPriorityQueue *PQ =
3161 new BURegReductionPriorityQueue(*IS->
MF,
false,
false,
TII,
TRI,
nullptr);
3162 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
false, PQ, OptLevel);
3163 PQ->setScheduleDAG(SD);
3174 SrcRegReductionPriorityQueue *PQ =
3175 new SrcRegReductionPriorityQueue(*IS->
MF,
false,
true,
TII,
TRI,
nullptr);
3176 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
false, PQ, OptLevel);
3177 PQ->setScheduleDAG(SD);
3189 HybridBURRPriorityQueue *PQ =
3190 new HybridBURRPriorityQueue(*IS->
MF,
true,
false,
TII,
TRI, TLI);
3192 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
true, PQ, OptLevel);
3193 PQ->setScheduleDAG(SD);
3205 ILPBURRPriorityQueue *PQ =
3206 new ILPBURRPriorityQueue(*IS->
MF,
true,
false,
TII,
TRI, TLI);
3207 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->
MF,
true, PQ, OptLevel);
3208 PQ->setScheduleDAG(SD);
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.
static bool isClobberKind(unsigned Flag)
static bool isRegDefKind(unsigned Flag)
static unsigned getNumOperandRegisters(unsigned Flag)
getNumOperandRegisters - Extract the number of registers field from the inline asm operand flag.
static bool isRegDefEarlyClobberKind(unsigned Flag)
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 an edge to be removed from the specified node N fr...
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.
Level
Code generation optimization level.
@ 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...
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.
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.
ScheduleDAGSDNodes * createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createBURRListDAGScheduler - This creates a bottom up list scheduler that schedules nodes in source c...
ScheduleDAGSDNodes * createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createBURRListDAGScheduler - This creates a bottom up register usage reduction list scheduler.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
ScheduleDAGSDNodes * createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level)
createHybridListDAGScheduler - This creates a bottom up register pressure aware list scheduler that m...
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.
ScheduleDAGSDNodes * createILPListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level)
createILPListDAGScheduler - This creates a bottom up register pressure aware list scheduler that trie...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.