1//===- GCNMinRegStrategy.cpp ----------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file defines and implements the class GCNMinRegScheduler, which
11/// implements an experimental, simple scheduler whose main goal is to learn
12/// ways about consuming less possible registers for a region.
13///
14//===----------------------------------------------------------------------===//
15
16#include "llvm/CodeGen/ScheduleDAG.h"
17using namespace llvm;
18
19#define DEBUG_TYPE "machine-scheduler"
20
21namespace {
22
23class GCNMinRegScheduler {
24 struct Candidate : ilist_node<Candidate> {
25 const SUnit *SU;
26 int Priority;
27
28 Candidate(const SUnit *SU_, int Priority_ = 0)
29 : SU(SU_), Priority(Priority_) {}
30 };
31
32 SpecificBumpPtrAllocator<Candidate> Alloc;
33 using Queue = simple_ilist<Candidate>;
34 Queue RQ; // Ready queue
35
36 std::vector<unsigned> NumPreds;
37
38 bool isScheduled(const SUnit *SU) const {
39 assert(!SU->isBoundaryNode());
40 return NumPreds[SU->NodeNum] == std::numeric_limits<unsigned>::max();
41 }
42
43 void setIsScheduled(const SUnit *SU) {
44 assert(!SU->isBoundaryNode());
45 NumPreds[SU->NodeNum] = std::numeric_limits<unsigned>::max();
46 }
47
48 unsigned getNumPreds(const SUnit *SU) const {
49 assert(!SU->isBoundaryNode());
50 assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
51 return NumPreds[SU->NodeNum];
52 }
53
54 unsigned decNumPreds(const SUnit *SU) {
55 assert(!SU->isBoundaryNode());
56 assert(NumPreds[SU->NodeNum] != std::numeric_limits<unsigned>::max());
57 return --NumPreds[SU->NodeNum];
58 }
59
60 void initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits);
61
62 int getReadySuccessors(const SUnit *SU) const;
63 int getNotReadySuccessors(const SUnit *SU) const;
64
65 template <typename Calc> size_t findMax(size_t Num, Calc C);
66
67 Candidate* pickCandidate();
68
69 void bumpPredsPriority(const SUnit *SchedSU, int Priority);
70 void releaseSuccessors(const SUnit* SU, int Priority);
71
72public:
73 std::vector<const SUnit*> schedule(ArrayRef<const SUnit*> TopRoots,
74 const ScheduleDAG &DAG);
75};
76
77} // end anonymous namespace
78
79void GCNMinRegScheduler::initNumPreds(const decltype(ScheduleDAG::SUnits) &SUnits) {
80 NumPreds.resize(new_size: SUnits.size());
81 for (unsigned I = 0; I < SUnits.size(); ++I)
82 NumPreds[I] = SUnits[I].NumPredsLeft;
83}
84
85int GCNMinRegScheduler::getReadySuccessors(const SUnit *SU) const {
86 unsigned NumSchedSuccs = 0;
87 for (auto SDep : SU->Succs) {
88 bool wouldBeScheduled = true;
89 for (auto PDep : SDep.getSUnit()->Preds) {
90 auto *PSU = PDep.getSUnit();
91 assert(!PSU->isBoundaryNode());
92 if (PSU != SU && !isScheduled(SU: PSU)) {
93 wouldBeScheduled = false;
94 break;
95 }
96 }
97 NumSchedSuccs += wouldBeScheduled ? 1 : 0;
98 }
99 return NumSchedSuccs;
100}
101
102int GCNMinRegScheduler::getNotReadySuccessors(const SUnit *SU) const {
103 return static_cast<int>(SU->Succs.size()) - getReadySuccessors(SU);
104}
105
106template <typename Calc>
107size_t GCNMinRegScheduler::findMax(size_t Num, Calc C) {
108 assert(!RQ.empty() && Num <= RQ.size());
109
110 using T = decltype(C(*RQ.begin())) ;
111
112 T Max = std::numeric_limits<T>::min();
113 size_t NumMax = 0;
114 for (auto I = RQ.begin(); Num; --Num) {
115 T Cur = C(*I);
116 if (Cur >= Max) {
117 if (Cur > Max) {
118 Max = Cur;
119 NumMax = 1;
120 } else
121 ++NumMax;
122 auto &Cand = *I++;
123 RQ.remove(N&: Cand);
124 RQ.push_front(Node&: Cand);
125 continue;
126 }
127 ++I;
128 }
129 return NumMax;
130}
131
132GCNMinRegScheduler::Candidate* GCNMinRegScheduler::pickCandidate() {
133 do {
134 size_t Num = RQ.size();
135 if (Num == 1) break;
136
137 LLVM_DEBUG(dbgs() << "\nSelecting max priority candidates among " << Num
138 << '\n');
139 Num = findMax(Num, C: [=](const Candidate &C) { return C.Priority; });
140 if (Num == 1) break;
141
142 LLVM_DEBUG(dbgs() << "\nSelecting min non-ready producing candidate among "
143 << Num << '\n');
144 Num = findMax(Num, C: [=](const Candidate &C) {
145 const auto *SU = C.SU;
146 int Res = getNotReadySuccessors(SU);
147 LLVM_DEBUG(dbgs() << *SU << " would left non-ready " << Res
148 << " successors, metric = " << -Res << '\n');
149 return -Res;
150 });
151 if (Num == 1) break;
152
153 LLVM_DEBUG(dbgs() << "\nSelecting most producing candidate among " << Num
154 << '\n');
155 Num = findMax(Num, C: [=](const Candidate &C) {
156 const auto *SU = C.SU;
157 auto Res = getReadySuccessors(SU);
158 LLVM_DEBUG(dbgs() << *SU << " would make ready " << Res
159 << " successors, metric = " << Res << '\n');
160 return Res;
161 });
162 if (Num == 1) break;
163
164 Num = Num ? Num : RQ.size();
165 LLVM_DEBUG(
166 dbgs()
167 << "\nCan't find best candidate, selecting in program order among "
168 << Num << '\n');
169 Num = findMax(Num, C: [=](const Candidate &C) { return -(int64_t)C.SU->NodeNum; });
170 assert(Num == 1);
171 } while (false);
172
173 return &RQ.front();
174}
175
176void GCNMinRegScheduler::bumpPredsPriority(const SUnit *SchedSU, int Priority) {
177 SmallPtrSet<const SUnit*, 32> Set;
178 for (const auto &S : SchedSU->Succs) {
179 if (S.getSUnit()->isBoundaryNode() || isScheduled(SU: S.getSUnit()) ||
180 S.getKind() != SDep::Data)
181 continue;
182 for (const auto &P : S.getSUnit()->Preds) {
183 auto *PSU = P.getSUnit();
184 assert(!PSU->isBoundaryNode());
185 if (PSU != SchedSU && !isScheduled(SU: PSU)) {
186 Set.insert(Ptr: PSU);
187 }
188 }
189 }
190 SmallVector<const SUnit*, 32> Worklist(Set.begin(), Set.end());
191 while (!Worklist.empty()) {
192 const auto *SU = Worklist.pop_back_val();
193 assert(!SU->isBoundaryNode());
194 for (const auto &P : SU->Preds) {
195 if (!P.getSUnit()->isBoundaryNode() && !isScheduled(SU: P.getSUnit()) &&
196 Set.insert(Ptr: P.getSUnit()).second)
197 Worklist.push_back(Elt: P.getSUnit());
198 }
199 }
200 LLVM_DEBUG(dbgs() << "Make the predecessors of " << *SchedSU
201 << "'s non-ready successors of " << Priority
202 << " priority in ready queue: ");
203 for (auto &C : RQ) {
204 if (Set.count(Ptr: C.SU)) {
205 C.Priority = Priority;
206 LLVM_DEBUG(dbgs() << ' ' << *C.SU);
207 }
208 }
209 LLVM_DEBUG(dbgs() << '\n');
210}
211
212void GCNMinRegScheduler::releaseSuccessors(const SUnit* SU, int Priority) {
213 for (const auto &S : SU->Succs) {
214 auto *SuccSU = S.getSUnit();
215 if (S.isWeak())
216 continue;
217 assert(SuccSU->isBoundaryNode() || getNumPreds(SuccSU) > 0);
218 if (!SuccSU->isBoundaryNode() && decNumPreds(SU: SuccSU) == 0)
219 RQ.push_front(Node&: *new (Alloc.Allocate()) Candidate(SuccSU, Priority));
220 }
221}
222
223std::vector<const SUnit*>
224GCNMinRegScheduler::schedule(ArrayRef<const SUnit*> TopRoots,
225 const ScheduleDAG &DAG) {
226 const auto &SUnits = DAG.SUnits;
227 std::vector<const SUnit*> Schedule;
228 Schedule.reserve(n: SUnits.size());
229
230 initNumPreds(SUnits);
231
232 int StepNo = 0;
233
234 for (const auto *SU : TopRoots) {
235 RQ.push_back(Node&: *new (Alloc.Allocate()) Candidate(SU, StepNo));
236 }
237 releaseSuccessors(SU: &DAG.EntrySU, Priority: StepNo);
238
239 while (!RQ.empty()) {
240 LLVM_DEBUG(dbgs() << "\n=== Picking candidate, Step = " << StepNo
241 << "\n"
242 "Ready queue:";
243 for (auto &C : RQ) dbgs()
244 << ' ' << *C.SU << "(P" << C.Priority << ')';
245 dbgs() << '\n';);
246
247 auto *C = pickCandidate();
248 assert(C);
249 RQ.remove(N&: *C);
250 const auto *SU = C->SU;
251 LLVM_DEBUG(dbgs() << "Selected "; DAG.dumpNode(*SU));
252
253 releaseSuccessors(SU, Priority: StepNo);
254 Schedule.push_back(x: SU);
255 setIsScheduled(SU);
256
257 if (getReadySuccessors(SU) == 0)
258 bumpPredsPriority(SchedSU: SU, Priority: StepNo);
259
260 ++StepNo;
261 }
262 assert(SUnits.size() == Schedule.size());
263
264 return Schedule;
265}
266
267namespace llvm {
268
269std::vector<const SUnit*> makeMinRegSchedule(ArrayRef<const SUnit*> TopRoots,
270 const ScheduleDAG &DAG) {
271 GCNMinRegScheduler S;
272 return S.schedule(TopRoots, DAG);
273}
274
275} // end namespace llvm
276