40#include "llvm/Config/llvm-config.h"
63#define DEBUG_TYPE "pre-RA-sched"
65STATISTIC(NumBacktracks,
"Number of times scheduler backtracked");
68STATISTIC(NumPRCopies,
"Number of physical register copies");
72 "Bottom-up register reduction list scheduling",
77 "Similar to list-burr but schedules in source "
78 "order when possible",
83 "Bottom-up register pressure aware list scheduling "
84 "which tries to balance latency and register pressure",
89 "Bottom-up register pressure aware list scheduling "
90 "which tries to balance ILP and register pressure",
95 cl::desc(
"Disable cycle-level precision during preRA scheduling"));
101 cl::desc(
"Disable regpressure priority in sched=list-ilp"));
104 cl::desc(
"Disable live use priority in sched=list-ilp"));
107 cl::desc(
"Disable virtual register cycle interference checks"));
110 cl::desc(
"Disable physreg def-use affinity"));
113 cl::desc(
"Disable no-stall priority in sched=list-ilp"));
116 cl::desc(
"Disable critical path priority in sched=list-ilp"));
119 cl::desc(
"Disable scheduled-height priority in sched=list-ilp"));
122 cl::desc(
"Disable scheduler's two-address hack"));
126 cl::desc(
"Number of instructions to allow ahead of the critical path "
127 "in sched=list-ilp"));
131 cl::desc(
"Average inst/cycle when no target itinerary exists."));
151 std::vector<SUnit *> PendingQueue;
157 unsigned CurCycle = 0;
160 unsigned MinAvailableCycle = ~0u;
164 unsigned IssueCount = 0u;
171 SUnit *Def =
nullptr;
173 SUnit *Gen =
nullptr;
175 explicit LiveReg(
unsigned Reg) :
Reg(
Reg) {}
176 unsigned getSparseSetIndex()
const {
return Reg; }
183 SparseSet<LiveReg> LiveRegs;
189 using LRegsMapT = DenseMap<SUnit *, SmallVector<unsigned, 4>>;
195 ScheduleDAGTopologicalSort Topo;
199 SmallDenseMap<SUnit *, SUnit *, 16> CallSeqEndForStart;
203 SchedulingPriorityQueue *availqueue,
205 : ScheduleDAGSDNodes(mf), NeedLatency(needlatency),
206 AvailableQueue(availqueue), Topo(SUnits, nullptr) {
209 HazardRec =
new ScheduleHazardRecognizer();
211 HazardRec = STI.
getInstrInfo()->CreateTargetHazardRecognizer(&STI,
this);
214 ~ScheduleDAGRRList()
override {
216 delete AvailableQueue;
219 void Schedule()
override;
221 LiveReg *findLiveReg(
unsigned Reg) {
223 if (LiveRegs.empty())
225 auto I = LiveRegs.find(
Reg);
226 return I == LiveRegs.end() ? nullptr : &*
I;
229 SUnit *getLiveRegDef(
unsigned Reg) {
230 LiveReg *LR = findLiveReg(
Reg);
231 return LR ? LR->Def :
nullptr;
234 SUnit *getLiveRegGen(
unsigned Reg) {
235 LiveReg *LR = findLiveReg(
Reg);
236 return LR ? LR->Gen :
nullptr;
241 LiveReg &addLiveReg(
unsigned Reg) {
243 if (LiveRegs.empty())
244 LiveRegs.setUniverse(
TRI->getNumRegs() + 1);
245 return *LiveRegs.insert(LiveReg(
Reg)).first;
248 void removeLiveReg(
unsigned Reg) {
249 if (!LiveRegs.erase(
Reg))
253 ScheduleHazardRecognizer *getHazardRec() {
return HazardRec; }
256 bool IsReachable(
const SUnit *SU,
const SUnit *TargetSU) {
257 return Topo.IsReachable(SU, TargetSU);
262 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
263 return Topo.WillCreateCycle(SU, TargetSU);
269 void AddPredQueued(SUnit *SU,
const SDep &
D) {
270 Topo.AddPredQueued(SU,
D.getSUnit());
277 void RemovePred(SUnit *SU,
const SDep &
D) {
278 Topo.RemovePred(SU,
D.getSUnit());
283 bool isReady(SUnit *SU) {
285 AvailableQueue->isReady(SU);
288 void ReleasePred(SUnit *SU,
const SDep *PredEdge);
289 void ReleasePredecessors(SUnit *SU);
290 void ReleasePending();
291 void AdvanceToCycle(
unsigned NextCycle);
292 void AdvancePastStalls(SUnit *SU);
293 void EmitNode(SUnit *SU);
294 void ScheduleNodeBottomUp(SUnit*);
295 void CapturePred(SDep *PredEdge);
296 void UnscheduleNodeBottomUp(SUnit*);
297 void RestoreHazardCheckerBottomUp();
298 void BacktrackBottomUp(SUnit*, SUnit*);
299 SUnit *TryUnfoldSU(SUnit *);
300 SUnit *CopyAndMoveSuccessors(SUnit*);
301 void InsertCopiesAndMoveSuccs(SUnit*,
unsigned,
304 SmallVectorImpl<SUnit*>&);
305 bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
307 SmallSet<unsigned, 4> &RegAdded,
308 SmallVectorImpl<unsigned> &LRegs,
309 const SDNode *Node =
nullptr);
310 void CheckForLiveRegDefMasked(SUnit *SU,
const uint32_t *RegMask,
311 SmallSet<unsigned, 4> &RegAdded,
312 SmallVectorImpl<unsigned> &LRegs);
314 void releaseInterferences(
unsigned Reg = 0);
316 SUnit *PickNodeToScheduleBottomUp();
317 void ListScheduleBottomUp();
320 SUnit *CreateNewSUnit(SDNode *
N) {
321 unsigned NumSUnits = SUnits.size();
322 SUnit *NewNode = newSUnit(
N);
324 if (NewNode->
NodeNum >= NumSUnits)
325 Topo.AddSUnitWithoutPredecessors(NewNode);
330 SUnit *CreateClone(SUnit *
N) {
331 unsigned NumSUnits = SUnits.size();
332 SUnit *NewNode = Clone(
N);
334 if (NewNode->
NodeNum >= NumSUnits)
335 Topo.AddSUnitWithoutPredecessors(NewNode);
341 bool forceUnitLatencies()
const override {
358 unsigned &RegClass,
unsigned &Cost,
364 if (VT == MVT::Untyped) {
371 RegClass = RC->
getID();
376 unsigned Opcode =
Node->getMachineOpcode();
377 if (Opcode == TargetOpcode::REG_SEQUENCE) {
378 unsigned DstRCIdx =
Node->getConstantOperandVal(0);
380 RegClass = RC->
getID();
385 unsigned Idx = RegDefPos.
GetIdx();
388 assert(RC &&
"Not a valid register class");
389 RegClass = RC->
getID();
394 RegClass =
TLI->getRepRegClassFor(VT)->getID();
395 Cost =
TLI->getRepRegClassCostFor(VT);
400void ScheduleDAGRRList::Schedule() {
402 <<
" '" << BB->getName() <<
"' **********\n");
409 CallSeqEndForStart.
clear();
410 assert(Interferences.
empty() && LRegsMap.empty() &&
"stale Interferences");
423 ListScheduleBottomUp();
428 dbgs() <<
"*** Final schedule ***\n";
440void ScheduleDAGRRList::ReleasePred(SUnit *SU,
const SDep *PredEdge) {
441 SUnit *PredSU = PredEdge->
getSUnit();
445 dbgs() <<
"*** Scheduling failed! ***\n";
447 dbgs() <<
" has been released too many times!\n";
453 if (!forceUnitLatencies()) {
465 if (Height < MinAvailableCycle)
466 MinAvailableCycle = Height;
468 if (isReady(PredSU)) {
469 AvailableQueue->
push(PredSU);
475 PendingQueue.push_back(PredSU);
499 if (
N->isMachineOpcode()) {
500 if (
N->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
502 }
else if (
N->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
510 if (
Op.getValueType() == MVT::Other) {
512 goto found_chain_operand;
515 found_chain_operand:;
539 unsigned BestMaxNest = MaxNest;
541 unsigned MyNestLevel = NestLevel;
542 unsigned MyMaxNest = MaxNest;
544 MyNestLevel, MyMaxNest,
TII))
545 if (!Best || (MyMaxNest > BestMaxNest)) {
547 BestMaxNest = MyMaxNest;
551 MaxNest = BestMaxNest;
555 if (
N->isMachineOpcode()) {
556 if (
N->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
558 MaxNest = std::max(MaxNest, NestLevel);
559 }
else if (
N->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
568 if (
Op.getValueType() == MVT::Other) {
570 goto found_chain_operand;
573 found_chain_operand:;
596void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
599 ReleasePred(SU, &
Pred);
600 if (
Pred.isAssignedRegDep()) {
605 LiveReg &LR = addLiveReg(
Pred.getReg());
606 assert((!LR.Def || LR.Def == SU || LR.Def ==
Pred.getSUnit()) &&
607 "interference on register dependence");
608 LR.Def =
Pred.getSUnit();
617 unsigned CallResource =
TRI->getNumRegs();
618 if (!getLiveRegDef(CallResource))
619 for (SDNode *Node = SU->
getNode(); Node; Node =
Node->getGluedNode())
620 if (
Node->isMachineOpcode() &&
621 Node->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
622 unsigned NestLevel = 0;
623 unsigned MaxNest = 0;
625 assert(
N &&
"Must find call sequence start");
627 SUnit *
Def = &SUnits[
N->getNodeId()];
628 CallSeqEndForStart[
Def] = SU;
630 LiveReg &LR = addLiveReg(CallResource);
639void ScheduleDAGRRList::ReleasePending() {
641 assert(PendingQueue.empty() &&
"pending instrs not allowed in this mode");
646 if (AvailableQueue->
empty())
647 MinAvailableCycle = std::numeric_limits<unsigned>::max();
651 for (
unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
652 unsigned ReadyCycle = PendingQueue[i]->getHeight();
653 if (ReadyCycle < MinAvailableCycle)
654 MinAvailableCycle = ReadyCycle;
656 if (PendingQueue[i]->isAvailable) {
657 if (!isReady(PendingQueue[i]))
659 AvailableQueue->
push(PendingQueue[i]);
661 PendingQueue[i]->isPending =
false;
662 PendingQueue[i] = PendingQueue.back();
663 PendingQueue.pop_back();
669void ScheduleDAGRRList::AdvanceToCycle(
unsigned NextCycle) {
670 if (NextCycle <= CurCycle)
677 CurCycle = NextCycle;
680 for (; CurCycle != NextCycle; ++CurCycle) {
691void ScheduleDAGRRList::AdvancePastStalls(SUnit *SU) {
708 AdvanceToCycle(ReadyCycle);
728 AdvanceToCycle(CurCycle + Stalls);
733void ScheduleDAGRRList::EmitNode(SUnit *SU) {
744 "This target-independent node should not be scheduled.");
777void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU) {
782 if (CurCycle < SU->getHeight())
784 <<
"] pipeline stall!\n");
804 AdvanceToCycle(CurCycle + 1);
808 ReleasePredecessors(SU);
811 for (SDep &Succ : SU->
Succs) {
814 removeLiveReg(Succ.
getReg());
815 releaseInterferences(Succ.
getReg());
820 unsigned CallResource =
TRI->getNumRegs();
821 if (getLiveRegDef(CallResource) == SU)
822 for (
const SDNode *SUNode = SU->
getNode(); SUNode;
824 if (SUNode->isMachineOpcode() &&
825 SUNode->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
826 removeLiveReg(CallResource);
827 releaseInterferences(CallResource);
848 AdvanceToCycle(CurCycle + 1);
855void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
856 SUnit *PredSU = PredEdge->
getSUnit();
860 AvailableQueue->
remove(PredSU);
864 "NumSuccsLeft will overflow!");
870void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
876 if (
Pred.isAssignedRegDep() && SU == getLiveRegGen(
Pred.getReg())) {
878 "Physical register dependency violated?");
879 removeLiveReg(
Pred.getReg());
880 releaseInterferences(
Pred.getReg());
886 unsigned CallResource =
TRI->getNumRegs();
887 for (
const SDNode *SUNode = SU->
getNode(); SUNode;
889 if (SUNode->isMachineOpcode() &&
890 SUNode->getMachineOpcode() ==
TII->getCallFrameSetupOpcode()) {
891 SUnit *SeqEnd = CallSeqEndForStart[SU];
892 assert(SeqEnd &&
"Call sequence start/end must be known");
893 assert(!findLiveReg(CallResource));
894 LiveReg &LR = addLiveReg(CallResource);
902 if (getLiveRegGen(CallResource) == SU)
903 for (
const SDNode *SUNode = SU->
getNode(); SUNode;
905 if (SUNode->isMachineOpcode() &&
906 SUNode->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
907 assert(getLiveRegDef(CallResource));
908 removeLiveReg(CallResource);
909 releaseInterferences(CallResource);
913 for (
auto &Succ : SU->
Succs) {
916 LiveReg &LR = addLiveReg(
Reg);
926 for (
auto &Succ2 : SU->
Succs) {
927 if (Succ2.isAssignedRegDep() && Succ2.getReg() ==
Reg &&
928 Succ2.getSUnit()->getHeight() < LR.Gen->getHeight())
929 LR.Gen = Succ2.getSUnit();
943 PendingQueue.push_back(SU);
946 AvailableQueue->
push(SU);
953void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {
956 unsigned LookAhead = std::min((
unsigned)
Sequence.size(),
961 std::vector<SUnit *>::const_iterator
I = (
Sequence.end() - LookAhead);
962 unsigned HazardCycle = (*I)->getHeight();
965 for (; SU->
getHeight() > HazardCycle; ++HazardCycle) {
974void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, SUnit *BtSU) {
980 UnscheduleNodeBottomUp(OldSU);
989 RestoreHazardCheckerBottomUp();
999 if (SUNode->isOperandOf(
N))
1006SUnit *ScheduleDAGRRList::TryUnfoldSU(SUnit *SU) {
1010 if (!
TII->unfoldMemoryOperand(*DAG,
N, NewNodes))
1013 assert(NewNodes.
size() == 2 &&
"Expected a load folding node!");
1016 SDNode *LoadNode = NewNodes[0];
1017 unsigned NumVals =
N->getNumValues();
1028 assert(
N->getNodeId() == -1 &&
"Node using a new load can't exist yet!");
1030 SUnit *LoadSU = CreateNewSUnit(LoadNode);
1032 InitNumRegDefsLeft(LoadSU);
1033 computeLatency(LoadSU);
1035 SUnit *NewSU = CreateNewSUnit(
N);
1038 const MCInstrDesc &MCID =
TII->get(
N->getMachineOpcode());
1048 InitNumRegDefsLeft(NewSU);
1049 computeLatency(NewSU);
1054 for (
unsigned i = 0; i != NumVals; ++i)
1056 DAG->ReplaceAllUsesOfValueWith(
SDValue(SU->
getNode(), OldNumVals - 1),
1073 for (SDep &Succ : SU->
Succs) {
1081 for (
const SDep &
Pred : ChainPreds) {
1082 RemovePred(SU,
Pred);
1083 AddPredQueued(LoadSU,
Pred);
1085 for (
const SDep &
Pred : LoadPreds) {
1086 RemovePred(SU,
Pred);
1087 AddPredQueued(LoadSU,
Pred);
1089 for (
const SDep &
Pred : NodePreds) {
1090 RemovePred(SU,
Pred);
1091 AddPredQueued(NewSU,
Pred);
1093 for (SDep &
D : NodeSuccs) {
1094 SUnit *SuccDep =
D.getSUnit();
1096 RemovePred(SuccDep,
D);
1098 AddPredQueued(SuccDep,
D);
1104 for (SDep &
D : ChainSuccs) {
1105 SUnit *SuccDep =
D.getSUnit();
1107 RemovePred(SuccDep,
D);
1109 AddPredQueued(SuccDep,
D);
1116 AddPredQueued(NewSU,
D);
1118 AvailableQueue->
addNode(LoadSU);
1119 AvailableQueue->
addNode(NewSU);
1131SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
1139 if (
N->getGluedNode() &&
1140 !
TII->canCopyGluedNodeDuringSchedule(
N)) {
1143 <<
"Giving up because it has incoming glue and the target does not "
1144 "want to copy it\n");
1149 bool TryUnfold =
false;
1150 for (
unsigned i = 0, e =
N->getNumValues(); i != e; ++i) {
1151 MVT VT =
N->getSimpleValueType(i);
1152 if (VT == MVT::Glue) {
1153 LLVM_DEBUG(
dbgs() <<
"Giving up because it has outgoing glue\n");
1155 }
else if (VT == MVT::Other)
1159 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
1160 if (VT == MVT::Glue && !
TII->canCopyGluedNodeDuringSchedule(
N)) {
1162 dbgs() <<
"Giving up because it one of the operands is glue and "
1163 "the target does not want to copy it\n");
1170 SUnit *UnfoldSU = TryUnfoldSU(SU);
1181 NewSU = CreateClone(SU);
1185 if (!
Pred.isArtificial())
1186 AddPredQueued(NewSU,
Pred);
1195 for (SDep &Succ : SU->
Succs) {
1202 AddPredQueued(SuccSU,
D);
1207 for (
const auto &[DelSU, DelD] : DelDeps)
1208 RemovePred(DelSU, DelD);
1211 AvailableQueue->
addNode(NewSU);
1219void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU,
unsigned Reg,
1222 SmallVectorImpl<SUnit*> &
Copies) {
1223 SUnit *CopyFromSU = CreateNewSUnit(
nullptr);
1227 SUnit *CopyToSU = CreateNewSUnit(
nullptr);
1234 for (SDep &Succ : SU->
Succs) {
1241 AddPredQueued(SuccSU,
D);
1251 for (
const auto &[DelSU, DelD] : DelDeps)
1252 RemovePred(DelSU, DelD);
1255 FromDep.setLatency(SU->
Latency);
1256 AddPredQueued(CopyFromSU, FromDep);
1258 ToDep.setLatency(CopyFromSU->
Latency);
1259 AddPredQueued(CopyToSU, ToDep);
1262 AvailableQueue->
addNode(CopyFromSU);
1263 AvailableQueue->
addNode(CopyToSU);
1264 Copies.push_back(CopyFromSU);
1265 Copies.push_back(CopyToSU);
1272void ScheduleDAGRRList::CheckForLiveRegDef(SUnit *SU, MCRegister
Reg,
1273 SmallSet<unsigned, 4> &RegAdded,
1274 SmallVectorImpl<unsigned> &LRegs,
1275 const SDNode *Node) {
1276 for (MCRegAliasIterator AliasI(
Reg,
TRI,
true); AliasI.isValid(); ++AliasI) {
1277 SUnit *
Def = getLiveRegDef(*AliasI);
1288 if (Node &&
Def->getNode() == Node)
1292 if (RegAdded.
insert(*AliasI).second) {
1300void ScheduleDAGRRList::CheckForLiveRegDefMasked(
1301 SUnit *SU,
const uint32_t *RegMask, SmallSet<unsigned, 4> &RegAdded,
1302 SmallVectorImpl<unsigned> &LRegs) {
1305 unsigned CallResource =
TRI->getNumRegs();
1306 SmallVector<unsigned, 8> Clobbered;
1307 for (
const LiveReg &LR : LiveRegs) {
1308 if (LR.Reg == CallResource || LR.Def == SU)
1314 for (
unsigned Reg : Clobbered)
1323 return RegOp->getRegMask();
1331bool ScheduleDAGRRList::
1332DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl<unsigned> &LRegs) {
1333 if (LiveRegs.empty())
1336 SmallSet<unsigned, 4> RegAdded;
1342 if (
Pred.isAssignedRegDep() && getLiveRegDef(
Pred.getReg()) != SU)
1346 for (SDNode *Node = SU->
getNode(); Node; Node =
Node->getGluedNode()) {
1351 if (
Node->getOperand(
NumOps-1).getValueType() == MVT::Glue)
1355 unsigned Flags =
Node->getConstantOperandVal(i);
1356 const InlineAsm::Flag
F(Flags);
1357 unsigned NumVals =
F.getNumOperandRegisters();
1360 if (
F.isRegDefKind() ||
F.isRegDefEarlyClobberKind() ||
1361 F.isClobberKind()) {
1363 for (; NumVals; --NumVals, ++i) {
1377 SDNode *SrcNode =
Node->getOperand(2).getNode();
1382 if (!
Node->isMachineOpcode())
1387 if (
Node->getMachineOpcode() ==
TII->getCallFrameDestroyOpcode()) {
1389 unsigned CallResource =
TRI->getNumRegs();
1390 if (LiveReg *LR = findLiveReg(CallResource)) {
1391 SDNode *Gen = LR->Gen->getNode();
1395 RegAdded.
insert(CallResource).second)
1400 CheckForLiveRegDefMasked(SU, RegMask, RegAdded, LRegs);
1402 const MCInstrDesc &MCID =
TII->get(
Node->getMachineOpcode());
1408 for (
unsigned i = 0; i < MCID.
getNumDefs(); ++i)
1409 if (MCID.
operands()[i].isOptionalDef()) {
1419 return !LRegs.
empty();
1422void ScheduleDAGRRList::releaseInterferences(
unsigned Reg) {
1424 for (
unsigned i = Interferences.
size(); i > 0; --i) {
1425 SUnit *SU = Interferences[i-1];
1426 LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);
1428 SmallVectorImpl<unsigned> &LRegs = LRegsPos->second;
1438 AvailableQueue->
push(SU);
1440 if (i < Interferences.
size())
1441 Interferences[i-1] = Interferences.
back();
1443 LRegsMap.erase(LRegsPos);
1451SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
1452 SUnit *CurSU = AvailableQueue->
empty() ? nullptr : AvailableQueue->
pop();
1453 auto FindAvailableNode = [&]() {
1455 SmallVector<unsigned, 4> LRegs;
1456 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
1459 if (LRegs[0] ==
TRI->getNumRegs())
dbgs() <<
"CallResource";
1461 dbgs() <<
" " << *CurSU <<
'\n');
1462 auto [LRegsIter, LRegsInserted] = LRegsMap.try_emplace(CurSU, LRegs);
1463 if (LRegsInserted) {
1470 LRegsIter->second = LRegs;
1472 CurSU = AvailableQueue->
pop();
1475 FindAvailableNode();
1487 for (SUnit *TrySU : Interferences) {
1488 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
1492 SUnit *BtSU =
nullptr;
1493 unsigned LiveCycle = std::numeric_limits<unsigned>::max();
1494 for (
unsigned Reg : LRegs) {
1495 SUnit *Gen = getLiveRegGen(
Reg);
1501 if (!WillCreateCycle(TrySU, BtSU)) {
1503 BacktrackBottomUp(TrySU, BtSU);
1510 AvailableQueue->
remove(BtSU);
1512 LLVM_DEBUG(
dbgs() <<
"ARTIFICIAL edge from " << *BtSU <<
" to " << *TrySU
1518 if (!TrySU->isAvailable || !TrySU->NodeQueueId) {
1519 LLVM_DEBUG(
dbgs() <<
"TrySU not available; choosing node from queue\n");
1520 CurSU = AvailableQueue->
pop();
1524 AvailableQueue->
remove(TrySU);
1527 FindAvailableNode();
1539 SUnit *TrySU = Interferences[0];
1540 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
1541 assert(LRegs.
size() == 1 &&
"Can't handle this yet!");
1542 unsigned Reg = LRegs[0];
1543 SUnit *LRDef = getLiveRegDef(
Reg);
1554 SUnit *NewDef =
nullptr;
1556 NewDef = CopyAndMoveSuccessors(LRDef);
1557 if (!DestRC && !NewDef)
1563 InsertCopiesAndMoveSuccs(LRDef,
Reg, DestRC, RC,
Copies);
1565 << *
Copies.front() <<
"\n");
1570 LLVM_DEBUG(
dbgs() <<
" Adding an edge from " << *NewDef <<
" to "
1572 findLiveReg(
Reg)->Def = NewDef;
1577 assert(CurSU &&
"Unable to resolve live physical register dependencies!");
1583void ScheduleDAGRRList::ListScheduleBottomUp() {
1585 ReleasePredecessors(&ExitSU);
1588 if (!SUnits.empty()) {
1589 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
1590 assert(RootSU->
Succs.empty() &&
"Graph root shouldn't have successors!");
1592 AvailableQueue->
push(RootSU);
1598 while (!AvailableQueue->
empty() || !Interferences.empty()) {
1600 AvailableQueue->
dump(
this));
1604 SUnit *SU = PickNodeToScheduleBottomUp();
1606 AdvancePastStalls(SU);
1608 ScheduleNodeBottomUp(SU);
1610 while (AvailableQueue->
empty() && !PendingQueue.empty()) {
1612 assert(MinAvailableCycle < std::numeric_limits<unsigned>::max() &&
1613 "MinAvailableCycle uninitialized");
1614 AdvanceToCycle(std::max(CurCycle + 1, MinAvailableCycle));
1622 VerifyScheduledSequence(
true);
1628class RegReductionPQBase;
1631 bool isReady(SUnit* SU,
unsigned CurCycle)
const {
return true; }
1636struct reverse_sort :
public queue_sort {
1639 reverse_sort(SF &sf) : SortFunc(sf) {}
1641 bool operator()(SUnit* left, SUnit* right)
const {
1644 return SortFunc(right, left);
1651struct bu_ls_rr_sort :
public queue_sort {
1654 HasReadyFilter =
false
1657 RegReductionPQBase *SPQ;
1659 bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1661 bool operator()(SUnit* left, SUnit* right)
const;
1665struct src_ls_rr_sort :
public queue_sort {
1668 HasReadyFilter =
false
1671 RegReductionPQBase *SPQ;
1673 src_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1675 bool operator()(SUnit* left, SUnit* right)
const;
1679struct hybrid_ls_rr_sort :
public queue_sort {
1682 HasReadyFilter =
false
1685 RegReductionPQBase *SPQ;
1687 hybrid_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1689 bool isReady(SUnit *SU,
unsigned CurCycle)
const;
1691 bool operator()(SUnit* left, SUnit* right)
const;
1696struct ilp_ls_rr_sort :
public queue_sort {
1699 HasReadyFilter =
false
1702 RegReductionPQBase *SPQ;
1704 ilp_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1706 bool isReady(SUnit *SU,
unsigned CurCycle)
const;
1708 bool operator()(SUnit* left, SUnit* right)
const;
1711class RegReductionPQBase :
public SchedulingPriorityQueue {
1713 std::vector<SUnit *> Queue;
1714 unsigned CurQueueId = 0;
1715 bool TracksRegPressure;
1719 std::vector<SUnit> *SUnits =
nullptr;
1722 const TargetInstrInfo *
TII =
nullptr;
1723 const TargetRegisterInfo *
TRI =
nullptr;
1724 const TargetLowering *
TLI =
nullptr;
1725 ScheduleDAGRRList *scheduleDAG =
nullptr;
1728 std::vector<unsigned> SethiUllmanNumbers;
1731 std::vector<unsigned> RegPressure;
1735 std::vector<unsigned> RegLimit;
1739 bool hasReadyFilter,
1742 const TargetInstrInfo *tii,
1743 const TargetRegisterInfo *tri,
1744 const TargetLowering *tli)
1745 : SchedulingPriorityQueue(hasReadyFilter), TracksRegPressure(tracksrp),
1746 SrcOrder(srcorder), MF(mf),
TII(tii),
TRI(tri),
TLI(tli) {
1747 if (TracksRegPressure) {
1748 unsigned NumRC =
TRI->getNumRegClasses();
1749 RegLimit.resize(NumRC);
1758 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1759 scheduleDAG = scheduleDag;
1762 ScheduleHazardRecognizer* getHazardRec() {
1763 return scheduleDAG->getHazardRec();
1766 void initNodes(std::vector<SUnit> &sunits)
override;
1768 void addNode(
const SUnit *SU)
override;
1770 void updateNode(
const SUnit *SU)
override;
1772 void releaseState()
override {
1774 SethiUllmanNumbers.clear();
1778 unsigned getNodePriority(
const SUnit *SU)
const;
1780 unsigned getNodeOrdering(
const SUnit *SU)
const {
1786 bool empty()
const override {
return Queue.empty(); }
1788 void push(SUnit *U)
override {
1789 assert(!
U->NodeQueueId &&
"Node in the queue already");
1790 U->NodeQueueId = ++CurQueueId;
1794 void remove(SUnit *SU)
override {
1797 std::vector<SUnit *>::iterator
I =
llvm::find(Queue, SU);
1798 if (
I != std::prev(
Queue.end()))
1804 bool tracksRegPressure()
const override {
return TracksRegPressure; }
1806 void dumpRegPressure()
const;
1808 bool HighRegPressure(
const SUnit *SU)
const;
1810 bool MayReduceRegPressure(SUnit *SU)
const;
1812 int RegPressureDiff(SUnit *SU,
unsigned &LiveUses)
const;
1814 void scheduledNode(SUnit *SU)
override;
1816 void unscheduledNode(SUnit *SU)
override;
1819 bool canClobber(
const SUnit *SU,
const SUnit *
Op);
1820 void AddPseudoTwoAddrDeps();
1821 void PrescheduleNodesWithMultipleUses();
1822 void CalculateSethiUllmanNumbers();
1826static SUnit *popFromQueueImpl(std::vector<SUnit *> &Q, SF &Picker) {
1827 unsigned BestIdx = 0;
1830 for (
unsigned I = 1,
E = std::min(Q.size(), (
decltype(Q.size()))1000);
I !=
E;
1832 if (Picker(Q[BestIdx], Q[
I]))
1834 SUnit *
V = Q[BestIdx];
1835 if (BestIdx + 1 != Q.size())
1842SUnit *popFromQueue(std::vector<SUnit *> &Q, SF &Picker, ScheduleDAG *DAG) {
1845 reverse_sort<SF> RPicker(Picker);
1846 return popFromQueueImpl(Q, RPicker);
1850 return popFromQueueImpl(Q, Picker);
1861class RegReductionPriorityQueue :
public RegReductionPQBase {
1868 const TargetInstrInfo *tii,
1869 const TargetRegisterInfo *tri,
1870 const TargetLowering *tli)
1871 : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
1875 bool isBottomUp()
const override {
return SF::IsBottomUp; }
1877 bool isReady(SUnit *U)
const override {
1878 return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
1881 SUnit *pop()
override {
1882 if (
Queue.empty())
return nullptr;
1884 SUnit *
V = popFromQueue(Queue, Picker, scheduleDAG);
1889#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1892 std::vector<SUnit *> DumpQueue =
Queue;
1893 SF DumpPicker = Picker;
1894 while (!DumpQueue.empty()) {
1895 SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
1903using BURegReductionPriorityQueue = RegReductionPriorityQueue<bu_ls_rr_sort>;
1904using SrcRegReductionPriorityQueue = RegReductionPriorityQueue<src_ls_rr_sort>;
1905using HybridBURRPriorityQueue = RegReductionPriorityQueue<hybrid_ls_rr_sort>;
1906using ILPBURRPriorityQueue = RegReductionPriorityQueue<ilp_ls_rr_sort>;
1923 if (LSchedLow != RSchedLow)
1924 return LSchedLow < RSchedLow ? 1 : -1;
1932 if (SUNumbers[SU->
NodeNum] != 0)
1933 return SUNumbers[SU->
NodeNum];
1937 WorkState(
const SUnit *SU) : SU(SU) {}
1939 unsigned PredsProcessed = 0;
1944 while (!WorkList.
empty()) {
1945 auto &Temp = WorkList.
back();
1946 auto *TempSU = Temp.SU;
1947 bool AllPredsKnown =
true;
1949 for (
unsigned P = Temp.PredsProcessed;
P < TempSU->Preds.size(); ++
P) {
1950 auto &
Pred = TempSU->Preds[
P];
1951 if (
Pred.isCtrl())
continue;
1953 if (SUNumbers[PredSU->
NodeNum] == 0) {
1956 for (
auto It : WorkList)
1957 assert(It.SU != PredSU &&
"Trying to push an element twice?");
1960 Temp.PredsProcessed =
P + 1;
1961 WorkList.push_back(PredSU);
1962 AllPredsKnown =
false;
1971 unsigned SethiUllmanNumber = 0;
1973 for (
const SDep &
Pred : TempSU->Preds) {
1974 if (
Pred.isCtrl())
continue;
1976 unsigned PredSethiUllman = SUNumbers[PredSU->
NodeNum];
1977 assert(PredSethiUllman > 0 &&
"We should have evaluated this pred!");
1978 if (PredSethiUllman > SethiUllmanNumber) {
1979 SethiUllmanNumber = PredSethiUllman;
1981 }
else if (PredSethiUllman == SethiUllmanNumber)
1985 SethiUllmanNumber += Extra;
1986 if (SethiUllmanNumber == 0)
1987 SethiUllmanNumber = 1;
1988 SUNumbers[TempSU->NodeNum] = SethiUllmanNumber;
1992 assert(SUNumbers[SU->
NodeNum] > 0 &&
"SethiUllman should never be zero!");
1993 return SUNumbers[SU->
NodeNum];
1998void RegReductionPQBase::CalculateSethiUllmanNumbers() {
1999 SethiUllmanNumbers.assign(SUnits->size(), 0);
2001 for (
const SUnit &SU : *SUnits)
2005void RegReductionPQBase::addNode(
const SUnit *SU) {
2006 unsigned SUSize = SethiUllmanNumbers.size();
2007 if (SUnits->size() > SUSize)
2008 SethiUllmanNumbers.resize(SUSize*2, 0);
2012void RegReductionPQBase::updateNode(
const SUnit *SU) {
2013 SethiUllmanNumbers[SU->
NodeNum] = 0;
2019unsigned RegReductionPQBase::getNodePriority(
const SUnit *SU)
const {
2026 if (
Opc == TargetOpcode::EXTRACT_SUBREG ||
2027 Opc == TargetOpcode::SUBREG_TO_REG ||
2028 Opc == TargetOpcode::INSERT_SUBREG)
2044 return SethiUllmanNumbers[SU->
NodeNum];
2046 unsigned Priority = SethiUllmanNumbers[SU->
NodeNum];
2050 return (NP > 0) ? NP : 0;
2060#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2067 << RegLimit[Id] <<
'\n');
2072bool RegReductionPQBase::HighRegPressure(
const SUnit *SU)
const {
2079 SUnit *PredSU =
Pred.getSUnit();
2085 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2086 RegDefPos.IsValid(); RegDefPos.Advance()) {
2087 unsigned RCId,
Cost;
2090 if ((RegPressure[RCId] +
Cost) >= RegLimit[RCId])
2097bool RegReductionPQBase::MayReduceRegPressure(SUnit *SU)
const {
2100 if (!
N->isMachineOpcode() || !SU->
NumSuccs)
2103 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2104 for (
unsigned i = 0; i != NumDefs; ++i) {
2105 MVT VT =
N->getSimpleValueType(i);
2106 if (!
N->hasAnyUseOfValue(i))
2109 if (RegPressure[RCId] >= RegLimit[RCId])
2122int RegReductionPQBase::RegPressureDiff(SUnit *SU,
unsigned &LiveUses)
const {
2128 SUnit *PredSU =
Pred.getSUnit();
2136 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2137 RegDefPos.IsValid(); RegDefPos.Advance()) {
2138 MVT VT = RegDefPos.GetValue();
2140 if (RegPressure[RCId] >= RegLimit[RCId])
2146 if (!
N || !
N->isMachineOpcode() || !SU->
NumSuccs)
2149 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2150 for (
unsigned i = 0; i != NumDefs; ++i) {
2151 MVT VT =
N->getSimpleValueType(i);
2152 if (!
N->hasAnyUseOfValue(i))
2155 if (RegPressure[RCId] >= RegLimit[RCId])
2161void RegReductionPQBase::scheduledNode(SUnit *SU) {
2162 if (!TracksRegPressure)
2171 SUnit *PredSU =
Pred.getSUnit();
2194 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2195 RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2199 unsigned RCId,
Cost;
2210 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(SU, scheduleDAG);
2211 RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2212 if (SkipRegDefs > 0)
2214 unsigned RCId,
Cost;
2216 if (RegPressure[RCId] <
Cost) {
2229void RegReductionPQBase::unscheduledNode(SUnit *SU) {
2230 if (!TracksRegPressure)
2236 if (!
N->isMachineOpcode()) {
2240 unsigned Opc =
N->getMachineOpcode();
2241 if (
Opc == TargetOpcode::EXTRACT_SUBREG ||
2242 Opc == TargetOpcode::INSERT_SUBREG ||
2243 Opc == TargetOpcode::SUBREG_TO_REG ||
2244 Opc == TargetOpcode::REG_SEQUENCE ||
2245 Opc == TargetOpcode::IMPLICIT_DEF)
2252 SUnit *PredSU =
Pred.getSUnit();
2257 const SDNode *PN = PredSU->
getNode();
2267 if (POpc == TargetOpcode::IMPLICIT_DEF)
2269 if (POpc == TargetOpcode::EXTRACT_SUBREG ||
2270 POpc == TargetOpcode::INSERT_SUBREG ||
2271 POpc == TargetOpcode::SUBREG_TO_REG) {
2277 if (POpc == TargetOpcode::REG_SEQUENCE) {
2280 unsigned RCId = RC->
getID();
2287 for (
unsigned i = 0; i != NumDefs; ++i) {
2302 if (SU->
NumSuccs &&
N->isMachineOpcode()) {
2303 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2304 for (
unsigned i = NumDefs, e =
N->getNumValues(); i != e; ++i) {
2305 MVT VT =
N->getSimpleValueType(i);
2306 if (VT == MVT::Glue || VT == MVT::Other)
2308 if (!
N->hasAnyUseOfValue(i))
2325 unsigned MaxHeight = 0;
2327 if (Succ.
isCtrl())
continue;
2334 if (Height > MaxHeight)
2343 unsigned Scratches = 0;
2345 if (
Pred.isCtrl())
continue;
2354 bool RetVal =
false;
2356 if (
Pred.isCtrl())
continue;
2362 if (
Reg.isVirtual()) {
2376 bool RetVal =
false;
2378 if (Succ.
isCtrl())
continue;
2383 if (
Reg.isVirtual()) {
2415 if (
Pred.isCtrl())
continue;
2416 Pred.getSUnit()->isVRegCycle =
true;
2427 if (
Pred.isCtrl())
continue;
2431 "VRegCycle def must be CopyFromReg");
2432 Pred.getSUnit()->isVRegCycle =
false;
2445 if (
Pred.isCtrl())
continue;
2446 if (
Pred.getSUnit()->isVRegCycle &&
2459 if ((
int)SPQ->getCurCycle() < Height)
return true;
2460 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2469 RegReductionPQBase *SPQ) {
2474 int LHeight = (int)left->
getHeight() + LPenalty;
2475 int RHeight = (int)right->
getHeight() + RPenalty;
2488 if (LHeight != RHeight)
2489 return LHeight > RHeight ? 1 : -1;
2501 if (!SPQ->getHazardRec()->isEnabled()) {
2502 if (LHeight != RHeight)
2503 return LHeight > RHeight ? 1 : -1;
2505 int LDepth = left->
getDepth() - LPenalty;
2506 int RDepth = right->
getDepth() - RPenalty;
2507 if (LDepth != RDepth) {
2508 LLVM_DEBUG(
dbgs() <<
" Comparing latency of " << *left <<
" depth "
2509 << LDepth <<
" vs " << *right <<
" depth " << RDepth
2511 return LDepth < RDepth ? 1 : -1;
2527 if (LHasPhysReg != RHasPhysReg) {
2529 static const char *
const PhysRegMsg[] = {
" has no physreg",
2530 " defines a physreg" };
2532 LLVM_DEBUG(
dbgs() <<
" " << *left <<
" " << PhysRegMsg[LHasPhysReg]
2533 <<
" " << *right <<
" " << PhysRegMsg[RHasPhysReg]
2535 return LHasPhysReg < RHasPhysReg;
2540 unsigned LPriority = SPQ->getNodePriority(left);
2541 unsigned RPriority = SPQ->getNodePriority(right);
2547 RPriority = (RPriority > RNumVals) ? (RPriority - RNumVals) : 0;
2551 LPriority = (LPriority > LNumVals) ? (LPriority - LNumVals) : 0;
2554 if (LPriority != RPriority)
2555 return LPriority > RPriority;
2560 unsigned LOrder = SPQ->getNodeOrdering(left);
2561 unsigned ROrder = SPQ->getNodeOrdering(right);
2565 if ((LOrder || ROrder) && LOrder != ROrder)
2566 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2589 return LDist < RDist;
2594 if (LScratch != RScratch)
2595 return LScratch > RScratch;
2599 if ((left->
isCall && RPriority > 0) || (right->
isCall && LPriority > 0))
2618 "NodeQueueId cannot be zero");
2623bool bu_ls_rr_sort::operator()(SUnit *left, SUnit *right)
const {
2631bool src_ls_rr_sort::operator()(SUnit *left, SUnit *right)
const {
2635 unsigned LOrder = SPQ->getNodeOrdering(left);
2636 unsigned ROrder = SPQ->getNodeOrdering(right);
2640 if ((LOrder || ROrder) && LOrder != ROrder)
2641 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2650bool hybrid_ls_rr_sort::isReady(SUnit *SU,
unsigned CurCycle)
const {
2651 static const unsigned ReadyDelay = 3;
2653 if (SPQ->MayReduceRegPressure(SU))
return true;
2655 if (SU->
getHeight() > (CurCycle + ReadyDelay))
return false;
2657 if (SPQ->getHazardRec()->getHazardType(SU, -ReadyDelay)
2665bool hybrid_ls_rr_sort::operator()(SUnit *left, SUnit *right)
const {
2673 bool LHigh = SPQ->HighRegPressure(left);
2674 bool RHigh = SPQ->HighRegPressure(right);
2677 if (LHigh && !RHigh) {
2678 LLVM_DEBUG(
dbgs() <<
" pressure " << *left <<
" > " << *right <<
"\n");
2681 else if (!LHigh && RHigh) {
2682 LLVM_DEBUG(
dbgs() <<
" pressure " << *right <<
" > " << *left <<
"\n");
2685 if (!LHigh && !RHigh) {
2695bool ilp_ls_rr_sort::isReady(SUnit *SU,
unsigned CurCycle)
const {
2696 if (SU->
getHeight() > CurCycle)
return false;
2698 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2712 if (
Opc == TargetOpcode::EXTRACT_SUBREG ||
2713 Opc == TargetOpcode::SUBREG_TO_REG ||
2714 Opc == TargetOpcode::INSERT_SUBREG)
2729bool ilp_ls_rr_sort::operator()(SUnit *left, SUnit *right)
const {
2737 unsigned LLiveUses = 0, RLiveUses = 0;
2738 int LPDiff = 0, RPDiff = 0;
2740 LPDiff = SPQ->RegPressureDiff(left, LLiveUses);
2741 RPDiff = SPQ->RegPressureDiff(right, RLiveUses);
2744 LLVM_DEBUG(
dbgs() <<
"RegPressureDiff " << *left <<
": " << LPDiff
2745 <<
" != " << *right <<
": " << RPDiff <<
"\n");
2746 return LPDiff > RPDiff;
2752 if (LReduce && !RReduce)
return false;
2753 if (RReduce && !LReduce)
return true;
2758 <<
" != " << *right <<
": " << RLiveUses <<
"\n");
2759 return LLiveUses < RLiveUses;
2765 if (LStall != RStall)
2773 <<
" != " << *right <<
": " << right->
getDepth()
2788void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
2792 AddPseudoTwoAddrDeps();
2794 if (!TracksRegPressure && !SrcOrder)
2795 PrescheduleNodesWithMultipleUses();
2797 CalculateSethiUllmanNumbers();
2800 if (scheduleDAG->BB->isSuccessor(scheduleDAG->BB))
2801 for (SUnit &SU : sunits)
2809bool RegReductionPQBase::canClobber(
const SUnit *SU,
const SUnit *
Op) {
2812 const MCInstrDesc &MCID =
TII->get(
Opc);
2815 for (
unsigned i = 0; i !=
NumOps; ++i) {
2831 ScheduleDAGRRList *scheduleDAG,
2837 if (ImpDefs.
empty() && !RegMask)
2842 for (
const SDep &SuccPred : SuccSU->
Preds) {
2848 scheduleDAG->IsReachable(DepSU, SuccPred.
getSUnit()))
2855 if (
TRI->regsOverlap(ImpDef, SuccPred.
getReg()) &&
2856 scheduleDAG->IsReachable(DepSU, SuccPred.
getSUnit()))
2870 unsigned NumDefs =
TII->get(
N->getMachineOpcode()).getNumDefs();
2872 assert(!ImpDefs.
empty() &&
"Caller should check hasPhysRegDefs");
2875 if (!SUNode->isMachineOpcode())
2878 TII->get(SUNode->getMachineOpcode()).implicit_defs();
2880 if (SUImpDefs.
empty() && !SURegMask)
2882 for (
unsigned i = NumDefs, e =
N->getNumValues(); i != e; ++i) {
2883 MVT VT =
N->getSimpleValueType(i);
2884 if (VT == MVT::Glue || VT == MVT::Other)
2886 if (!
N->hasAnyUseOfValue(i))
2892 if (
TRI->regsOverlap(
Reg, SUReg))
2930void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {
2932 for (SUnit &SU : *SUnits) {
2948 SDNode *PredFrameSetup =
nullptr;
2950 if (
Pred.isCtrl() &&
Pred.getSUnit()) {
2952 SDNode *PredND =
Pred.getSUnit()->getNode();
2963 PredFrameSetup = PredND;
2968 if (PredFrameSetup !=
nullptr)
2972 SUnit *PredSU =
nullptr;
2974 if (!
Pred.isCtrl()) {
2975 PredSU =
Pred.getSUnit();
2995 for (
const SDep &PredSucc : PredSU->
Succs) {
2996 SUnit *PredSuccSU = PredSucc.
getSUnit();
2997 if (PredSuccSU == &SU)
continue;
3001 goto outer_loop_continue;
3005 goto outer_loop_continue;
3007 if (scheduleDAG->IsReachable(&SU, PredSuccSU))
3008 goto outer_loop_continue;
3014 dbgs() <<
" Prescheduling " << SU <<
" next to PredSU " << *PredSU
3015 <<
" to guide scheduling in the presence of multiple uses\n");
3016 for (
unsigned i = 0; i != PredSU->
Succs.size(); ++i) {
3019 SUnit *SuccSU =
Edge.getSUnit();
3020 if (SuccSU != &SU) {
3021 Edge.setSUnit(PredSU);
3022 scheduleDAG->RemovePred(SuccSU,
Edge);
3023 scheduleDAG->AddPredQueued(&SU,
Edge);
3025 scheduleDAG->AddPredQueued(SuccSU,
Edge);
3029 outer_loop_continue:;
3040void RegReductionPQBase::AddPseudoTwoAddrDeps() {
3041 for (SUnit &SU : *SUnits) {
3050 unsigned Opc =
Node->getMachineOpcode();
3051 const MCInstrDesc &MCID =
TII->get(
Opc);
3054 for (
unsigned j = 0;
j !=
NumOps; ++
j) {
3060 const SUnit *DUSU = &(*SUnits)[DU->
getNodeId()];
3063 for (
const SDep &Succ : DUSU->
Succs) {
3078 while (SuccSU->
Succs.size() == 1 &&
3081 TargetOpcode::COPY_TO_REGCLASS)
3082 SuccSU = SuccSU->
Succs.front().getSUnit();
3095 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
3096 SuccOpc == TargetOpcode::INSERT_SUBREG ||
3097 SuccOpc == TargetOpcode::SUBREG_TO_REG)
3100 (!canClobber(SuccSU, DUSU) ||
3103 !scheduleDAG->IsReachable(SuccSU, &SU)) {
3104 LLVM_DEBUG(
dbgs() <<
" Adding a pseudo-two-addr edge from " << SU
3105 <<
" to " << *SuccSU <<
"\n");
3123 BURegReductionPriorityQueue *PQ =
3124 new BURegReductionPriorityQueue(*IS->MF,
false,
false,
TII,
TRI,
nullptr);
3125 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->MF,
false, PQ, OptLevel);
3126 PQ->setScheduleDAG(SD);
3137 SrcRegReductionPriorityQueue *PQ =
3138 new SrcRegReductionPriorityQueue(*IS->MF,
false,
true,
TII,
TRI,
nullptr);
3139 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->MF,
false, PQ, OptLevel);
3140 PQ->setScheduleDAG(SD);
3152 HybridBURRPriorityQueue *PQ =
3153 new HybridBURRPriorityQueue(*IS->MF,
true,
false,
TII,
TRI,
TLI);
3155 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->MF,
true, PQ, OptLevel);
3156 PQ->setScheduleDAG(SD);
3167 ILPBURRPriorityQueue *PQ =
3168 new ILPBURRPriorityQueue(*IS->MF,
true,
false,
TII,
TRI,
TLI);
3169 ScheduleDAGRRList *SD =
new ScheduleDAGRRList(*IS->MF,
true, PQ, OptLevel);
3170 PQ->setScheduleDAG(SD);
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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.
This file defines the DenseMap class.
const HexagonInstrInfo * TII
const size_t AbstractManglingParser< Derived, Alloc >::NumOps
Register const TargetRegisterInfo * TRI
Promote Memory to Register
static bool isLiveOut(const MachineBasicBlock &MBB, unsigned Reg)
std::pair< BasicBlock *, BasicBlock * > Edge
static bool CheckForLiveRegDef(SUnit *SU, MCRegister Reg, std::vector< 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 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 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 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 cl::opt< unsigned > AvgIPC("sched-avg-ipc", cl::Hidden, cl::init(1), cl::desc("Average inst/cycle when no target itinerary exists."))
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 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)
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the SparseSet class derived from the version described in Briggs,...
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.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool empty() const
Check if the array is empty.
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,...
unsigned getID() const
getID() - Return the register class ID number.
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.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
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
uint64_t getConstantOperandVal(unsigned Num) const
Helper method returns the integer value of a ConstantSDNode operand.
LLVM_ABI 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.
Register 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.
LLVM_ABI 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...
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI 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.
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
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 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...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
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 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...
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 TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
#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...
@ ANNOTATION_LABEL
ANNOTATION_LABEL - Represents a mid basic block label used by annotations.
@ 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.
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
NodeAddr< NodeBase * > Node
LLVM_ABI std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
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.
void fill(R &&Range, T &&Value)
Provide wrappers to std::fill which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI ScheduleDAGSDNodes * createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createBURRListDAGScheduler - This creates a bottom up register usage reduction list scheduler.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI ScheduleDAGSDNodes * createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel)
createHybridListDAGScheduler - This creates a bottom up register pressure aware list scheduler that m...
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI void report_fatal_error(Error Err, bool gen_crash_diag=true)
CodeGenOptLevel
Code generation optimization level.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI ScheduleDAGSDNodes * createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createSourceListDAGScheduler - This creates a bottom up list scheduler that schedules nodes in source...
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
DWARFExpression::Operation Op
LLVM_ABI ScheduleDAGSDNodes * createILPListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel)
createILPListDAGScheduler - This creates a bottom up register pressure aware list scheduler that trie...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
LLVM_ABI 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.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
MCRegisterClass TargetRegisterClass
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.