19 #define DEBUG_TYPE "machine-scheduler"
23 class GCNMinRegScheduler {
28 Candidate(
const SUnit *SU_,
int Priority_ = 0)
29 : SU(SU_), Priority(Priority_) {}
36 std::vector<unsigned> NumPreds;
38 bool isScheduled(
const SUnit *SU)
const {
43 void setIsScheduled(
const SUnit *SU) {
48 unsigned getNumPreds(
const SUnit *SU)
const {
54 unsigned decNumPreds(
const SUnit *SU) {
62 int getReadySuccessors(
const SUnit *SU)
const;
63 int getNotReadySuccessors(
const SUnit *SU)
const;
65 template <
typename Calc>
66 unsigned findMax(
unsigned Num, Calc
C);
68 Candidate* pickCandidate();
70 void bumpPredsPriority(
const SUnit *SchedSU,
int Priority);
71 void releaseSuccessors(
const SUnit* SU,
int Priority);
81 NumPreds.resize(SUnits.size());
82 for (
unsigned I = 0;
I < SUnits.size(); ++
I)
83 NumPreds[
I] = SUnits[
I].NumPredsLeft;
86 int GCNMinRegScheduler::getReadySuccessors(
const SUnit *SU)
const {
87 unsigned NumSchedSuccs = 0;
89 bool wouldBeScheduled =
true;
91 auto PSU = PDep.getSUnit();
92 assert(!PSU->isBoundaryNode());
93 if (PSU != SU && !isScheduled(PSU)) {
94 wouldBeScheduled =
false;
98 NumSchedSuccs += wouldBeScheduled ? 1 : 0;
100 return NumSchedSuccs;
103 int GCNMinRegScheduler::getNotReadySuccessors(
const SUnit *SU)
const {
104 return SU->
Succs.size() - getReadySuccessors(SU);
107 template <
typename Calc>
108 unsigned GCNMinRegScheduler::findMax(
unsigned Num, Calc
C) {
109 assert(!RQ.empty() && Num <= RQ.size());
111 using T = decltype(
C(*RQ.begin())) ;
115 for (
auto I = RQ.begin(); Num; --Num) {
133 GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() {
135 unsigned Num = RQ.size();
138 LLVM_DEBUG(
dbgs() <<
"\nSelecting max priority candidates among " << Num
140 Num = findMax(Num, [=](
const Candidate &
C) {
return C.Priority; });
143 LLVM_DEBUG(
dbgs() <<
"\nSelecting min non-ready producing candidate among "
145 Num = findMax(Num, [=](
const Candidate &
C) {
147 int Res = getNotReadySuccessors(SU);
149 << Res <<
" successors, metric = " << -Res <<
'\n');
154 LLVM_DEBUG(
dbgs() <<
"\nSelecting most producing candidate among " << Num
156 Num = findMax(Num, [=](
const Candidate &
C) {
158 auto Res = getReadySuccessors(SU);
160 <<
" successors, metric = " << Res <<
'\n');
165 Num = Num ? Num : RQ.size();
168 <<
"\nCan't find best candidate, selecting in program order among "
170 Num = findMax(Num, [=](
const Candidate &
C) {
return -(int64_t)
C.SU->NodeNum; });
177 void GCNMinRegScheduler::bumpPredsPriority(
const SUnit *SchedSU,
int Priority) {
179 for (
const auto &
S : SchedSU->
Succs) {
180 if (
S.getSUnit()->isBoundaryNode() || isScheduled(
S.getSUnit()) ||
183 for (
const auto &
P :
S.getSUnit()->Preds) {
184 auto PSU =
P.getSUnit();
185 assert(!PSU->isBoundaryNode());
186 if (PSU != SchedSU && !isScheduled(PSU)) {
192 while (!Worklist.empty()) {
193 auto SU = Worklist.pop_back_val();
195 for (
const auto &
P : SU->
Preds) {
196 if (!
P.getSUnit()->isBoundaryNode() && !isScheduled(
P.getSUnit()) &&
197 Set.
insert(
P.getSUnit()).second)
198 Worklist.push_back(
P.getSUnit());
202 <<
")'s non-ready successors of " << Priority
203 <<
" priority in ready queue: ");
206 C.Priority = Priority;
213 void GCNMinRegScheduler::releaseSuccessors(
const SUnit* SU,
int Priority) {
214 for (
const auto &
S : SU->
Succs) {
215 auto SuccSU =
S.getSUnit();
218 assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
219 if (!SuccSU->isBoundaryNode() && decNumPreds(SuccSU) == 0)
220 RQ.push_front(*
new (Alloc.
Allocate()) Candidate(SuccSU, Priority));
224 std::vector<const SUnit*>
227 const auto &SUnits = DAG.
SUnits;
228 std::vector<const SUnit*> Schedule;
229 Schedule.reserve(SUnits.size());
231 initNumPreds(SUnits);
235 for (
auto SU : TopRoots) {
236 RQ.push_back(*
new (Alloc.
Allocate()) Candidate(SU, StepNo));
238 releaseSuccessors(&DAG.
EntrySU, StepNo);
240 while (!RQ.empty()) {
246 <<
' ' <<
C.SU->NodeNum <<
"(P" <<
C.Priority <<
')';
249 auto C = pickCandidate();
255 releaseSuccessors(SU, StepNo);
256 Schedule.push_back(SU);
259 if (getReadySuccessors(SU) == 0)
260 bumpPredsPriority(SU, StepNo);
264 assert(SUnits.size() == Schedule.size());
273 GCNMinRegScheduler
S;
274 return S.schedule(TopRoots, DAG);